Re: [Help-glpk] Figure out the exiting variable after simplex iteration

[Joey Rios]

Thanks for the reply Andrew.  I thought I sent a reply email already, so if this is a duplicate, I apologize.

> >  I'd really like to know which variable left the basis to
> > understand why the entering variable isn't integer (ultimately in this
> > model all variables will be assigned binary values).
>
> If you introduce a non-negative variable into the model and then
> perform re-optimization, there may be many pivots needed to the primal
> simplex to reach the new optimum, so many variables may left/enter the
> basis.

> If you need to know what happens on the very first pivot, you may
> limit the number of simplex iterations by 1.

Based on your comments, I added a count to my iterations using:

it_cnt_begin = lpx_get_int_parm(master_lp, LPX_K_ITCNT);
glp_simplex(master_lp, simplex_control_params);
it_cnt_end = lpx_get_int_parm(master_lp, LPX_K_ITCNT);

And I now see what you mean about multiple pivots.  I must be missing/forgetting something rather fundamental.  If I introduce a new column that can improve the objective, why is it there are potentially multiple pivots?  I would just expect the new column to enter and some other column to exit.  Any brief (or detailed) explanation would be appreciated.

> Could you explain what exactly do you need? Are you trying to generate
> columns in such a way that keeps integrality of the basic solution?
>

I am trying to avoid maintaining integrality at each iteration.  Ultimately what I would like to show is that for my model and architecture, the final solution provided will be integral (given certain conditions), thus obviating the need to maintain integrality at each step.  My experimental evidence suggests this is the case, but proving it is tricky.  To gain some insight, I'd like to understand why my model would become non-integral at any given simplex call (and how it ultimately escapes this non-integral solution).  This is why I'd like to see what happens at a given simplex call when non-integrality is introduced (which variable(s) left and why the new variable isn't valued 1).

Hope this provides some clarification. I am happy to provide more if I'm still too vague.

Thanks again,
Joey

---

Windows Live™: Keep your life in sync. Check it out.