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

[Andrew Makhorin]

>>
>> If the simplex made no iterations, the column you just added to the
>> formulation remains non-basic. ...  use
>> the routine glp_get_col_dual to see the column's reduced cost. If the
>> column has not been chosen to enter the basis, its reduced cost either
>> has wrong sign (i.e. dual feasible) or is close to zero (i.e. less
>> than tol_dj tolerance). Most probably this is the reason. 

> I have been using glp_get_col_dual().  Here's an example of what I
> print out when the master seems to not want to perform any simplex
> iterations despite promising (i.e. negative reduced cost and not near
> zero) non-basic columns:

> master_lp has 7209 cols.
> ######## In master_iteration().
> The simplex return code was 0.
> There was no simplex progress made.  Cycling?  Finishing now.
> Check reduced costs of non-basic vars.
>   Non-basic col 31 (su_31) has reduced cost -4.5517465169e+03 
>   Non-basic col 51 (su_51) has reduced cost 3.9463541573e+03 
>   Non-basic col 52 (su_52) has reduced cost 0.0000000000e+00 
>   Non-basic col 91 (su_91) has reduced cost -3.3083798050e+02 
>   Non-basic col 92 (su_92) has reduced cost 1.5307996302e+01 
>   Non-basic col 100 (su_100) has reduced cost -1.7927935642e+03 
>   Non-basic col 108 (su_108) has reduced cost -2.5481619451e+03 
>   Non-basic col 111 (su_111) has reduced cost -9.1211449832e+02 
>   Non-basic col 112 (su_112) has reduced cost 1.6952769502e+02 
>   Non-basic col 1770 (su_1770) has reduced cost -3.6789447191e+03 
>   Non-basic col 4458 (su_4458) has reduced cost -4.0260260674e+03 
>   Non-basic col 7180 (lambda_7_0) has reduced cost 6.9532474607e+04 
>   Non-basic col 7181 (lambda_4_0) has reduced cost 3.7384642697e+04 
>   Non-basic col 7194 (lambda_0_2) has reduced cost -4.8882577603e+04 
>   Non-basic col 7196 (lambda_2_2) has reduced cost 1.6000000000e+01 
>   Non-basic col 7197 (lambda_3_2) has reduced cost -1.9636770787e+04 
>   Non-basic col 7198 (lambda_7_2) has reduced cost -1.0458277753e+04 
>   Non-basic col 7199 (lambda_4_2) has reduced cost -7.8661177528e+03 
>   Non-basic col 7200 (lambda_5_2) has reduced cost -1.7841770787e+03 
>   Non-basic col 7202 (lambda_0_3) has reduced cost -5.0972437639e+04 
>   Non-basic col 7203 (lambda_1_3) has reduced cost -3.1950123124e+04 
>   Non-basic col 7206 (lambda_3_3) has reduced cost -2.3337715506e+04 
>   Non-basic col 7207 (lambda_4_3) has reduced cost -1.4707844494e+04 
>   Non-basic col 7208 (lambda_6_3) has reduced cost -7.4867924494e+04 
>   Non-basic col 7209 (lambda_5_3) has reduced cost -7.4100794607e+04 
>   Non-basic col 7210 (lambda_0_4) has reduced cost -5.1900552137e+04 
>   Non-basic col 7211 (lambda_1_4) has reduced cost -3.7260219555e+04 
>   Non-basic col 7212 (lambda_4_4) has reduced cost -2.2797896629e+04 
>   Non-basic col 7213 (lambda_3_4) has reduced cost -2.8977000268e+04 
>   Non-basic col 7214 (lambda_6_4) has reduced cost -1.0701213303e+05 
>   Non-basic col 7215 (lambda_2_4) has reduced cost -2.8411518740e+04 
>   Non-basic col 7216 (lambda_5_4) has reduced cost -9.4148924944e+04 
>   Non-basic col 7217 (lambda_7_4) has reduced cost -5.2412338876e+04 
> ################################################
> ####  Master objective value = 8.0693198819613899e+04 
> ################################################
> ######## Leaving master_iteration().

> To me, it looks like there are plenty of promising columns to bring
> into the basis, but if I run glp_simplex() again, there will be no
> simplex iterations, thus leaving the basis the same.  Just to note, the
> optimal value for this problem will ultimately be 477.

>> (Do you
>> check the return code from glp_simplex?)
>> 

> I just added that due to your suggestion.  It's returning 0 everytime.

> Any other suggestions?  It is a little tricky to test too many things
> as it takes over an hour to get to the output you see above, but I am
> willing to try anything at this point.

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).