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

[Joey Rios]

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.

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?

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.

Thanks,
Joey

---

Hotmail® goes with you. Get it on your BlackBerry or iPhone.