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

[Joey Rios]

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

Thanks again,
Joey

---

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