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.
http://windowslive.com/Tutorial/Hotmail/Mobile?ocid=TXT_TAGLM_WL_HM_Tutorial_Mobile1_052009
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
