Re: [Help-glpk] Min. problem with reduced costs < 0, but simplex fails to progress

[Andrew Makhorin]

>> >> (Do you
>> >> check the return code from glp_simplex?)
>> >> 
>> 
>> > I just added that due to your suggestion.  It's returning 0 everytime.
>> 

>> Please make sure that:
>> 
>> a) column(s) added to the current formulation have correct type,
>>    bounds, and constraint coefficients;
>> 
>> b) glp_simplex returns 0;
>> 
>> c) glp_get_status returns GLP_OPT (note that if glp_simplex detects
>>    infeasibility or unboundedness, it returns 0; and if it detects
>>    this on the very first iteration, it performs no pivots).

> Here are the return codes I'm getting on each iteration after the first:

> glp_get_status() returns 4.  
> glp_get_prim_stat() returns 4.
> glp_get_dual_stat() returns 3.

> 4 == GLP_NOFEAS
> 3 == GLP_INFEAS

> It does this for 4 of my algorithm's iterations, but simplex
> iterations are taking place during each of those except the last.  On the
> last of my iterations, I sense that there was no simplex iteration
> completed and bail (as described in an earlier message).

> On other decompositions of this same problem (i.e., when I have more
> than 8 subproblems), I am getting the following return codes at each of
> my iterations after the first:

> glp_get_status() returns 5.
> glp_get_prim_stat() returns 2.
> glp_get_dual_stat() returns 2.

> 5 == GLP_OPT
> 2 == GLP_FEAS

> These return codes are more reasonable and what I would expect from
> any number of subproblems I might use.  And ultimately all of these
> decompositions lead to the correct/same optimal value.

> My C code is the same for any number of subproblems.  And the column
> generation algorithm is the same for any number of subproblems.  I know
> it might be hard to do so based on the information I've provided, but if
> you have any other suggestions on what to look for/at to figure out what
> is going on, I'd appreciate it.

GLP_NOFEAS reported by glp_get_status means that LP has no primal
feasible solution, and the final basic solution on exit from glp_simplex
is primal infeasible. Note that basic solution components returned by
glp_simplex always correspond to the original objectve, but in this case
you need to generate columns which improve the sum of infeasibilities,
not the original objective. In other word, reduced costs for the original
objective are useless until the basis is primal feasible.

Though the basic solution returned by glp_simplex is primal infeasible,
it is extremal in the sense that it minimizes the sum of infeasibilities.
So you can determine auxiliary objective coefficients as follows:

       / -1, if x[k] < l[k]
       |
c[k] = <  0, if l[k] <= x[k] <= u[k]
       |
       \ +1, if x[k] > u[k]

and use them instead of the original objective coefficients for computing
reduced costs of columns to be generated. Note that -1 and +1 may be
replaced by any positive and negative weights, if necessary. Note also
that if x[k] above is an auxiliary variable, you should substitute it to
express the auxiliary objective only through structural variables.