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

[Joey Rios]

I just wanted to close out this thread for posterity and completeness' sakes.

> > I think I understand what you're talking about with column generation in general, but this algorithm (Dantzig-Wolfe Decomposition) maintains primal feasibility at each iteration. My implementation does this correctly for all instances when I have a larger number of subproblems, but not for the cases where I have 8 or fewer subproblems.
>
> How?
> My recollection is that DW does not provide
> an instant initial feasible solution.
> It might be the case that the more pieces into which yu divvy up the problem,
> the more likely it is that the first subproblem solutions
> will correspond to a feasible for the whole problem.
> With 8 subproblems, you have to work at finding a feasible solution.
>

The problem was indeed with my Phase I procedure.  It was incredibly broken.  But that broken-ness was overcome by sheer numbers of columns when I had instances with a larger number of subproblems.

I finally fixed the Phase I procedure and each instance regardless of the number of subproblems converges to the same optimal value.

Thanks to Andrew for pointing me to use the return values more effectively and to Michael for leading me to investigate my seemingly innocuous Phase I.

Joey

---

Hotmail® has ever-growing storage! Don’t worry about storage limits. Check it out.