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

[Andrew Makhorin]

> I have a minimization problem that is not converging as it should. 
> I'm using a column generation technique with various numbers of
> subproblems to generate the columns for a master problem.  When I use
> over, say, 16 subproblems the master problem converges just fine.  If I
> use 8 or less subproblems, the master seems to 'stall out' (i.e., it
> doesn't make any progress despite hopeful-looking, non-basic columns).

> Some details... I've tried 16, 32, 64... etc subproblems and they all
> converge to the same optimal value for this problem instance.  This is
> the same optimal value one would get if he/she ran a standard
> optimization on a non-decomposed version.  This leads me to feel
> comfortable that the column generation is working correctly.

> When I use 8 or 4 or 2 subproblems, the algorithm reaches a point
> where there are columns with negative reduced cost, but the master's
> simplex call doesn't progress the problem.  No simplex iterations take
> place.  No negative reduced cost columns enter the basis.  What this
> implies for the column-generating subproblems is that they keep offering
> the same, redundant columns over and over and the master keeps doing
> nothing with them.

> I assume there is degeneracy in the master.  Because of this, at first
> I thought this might be some sort of cycling behavior, but I would think
> if there was cycling, we'd see some simplex iterations in the master.  Am
> I wrong about this?  I'm keeping track of simplex iterations using
> lpx_get_int_parm(master_lp, LPX_K_ITCNT).  I'm using GLPK 4.34.

> Overall, I expect this problem instance to converge to the same
> optimal value regardless of the number or subproblems I use.  Hence this
> call for help.

If the simplex made no iterations, the column you just added to the
formulation remains non-basic. On exit the simplex solver always
computes all basic solution components, even it has made no pivots.
So you can print the basic solution, say, with glp_print_sol or 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. (Do you
check the return code from glp_simplex?)

> Can I possibly force one of the negative reduced cost columns into the
> basis and see what happens?  How might I do this with the API?

Currently there is no api routine to change the basis in the same way
as the simplex solver does. You can explicitly change the column status
to GLP_BS with the routine glp_set_col_stat, however, to keep the basis
valid you also should remove some appropriate basic row/column from the
basis changing its status to GLP_NL or GLP_NU. This must work, but is
time-consuming because invalidates the basis factorization.

> I don't expect anyone to solve this problem for me, but if anyone has
> any insight or ideas as to where I could track down the problem or values
> I should peek at, I'd appreciate it.  I'd be happy to provide further
> details since I'm sure some of my descriptions aren't the best.