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

[Joey Rios]

> GLP_NOFEAS reported by glp_get_status means that LP has no primal
> feasible solution, and the final basic solution on exit from glp_simplex
> is primal infeasible. Note that basic solution components returned by
> glp_simplex always correspond to the original objectve, but in this case
> you need to generate columns which improve the sum of infeasibilities,
> not the original objective. In other word, reduced costs for the original
> objective are useless until the basis is primal feasible.

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. 

It looks like I need to figure out why the instances with 8 subprobs give me this at each iteration:

>> glp_get_status() returns 4.  
>> glp_get_prim_stat() returns 4.

While those with greater subprobs correctly (according to the algorithm) give me this:

>> glp_get_status() returns 5.
>> glp_get_prim_stat() returns 2.

Where 4 == GLP_NOFEAS, 2 == GLP_FEAS, and 5 == GLP_OPT.

I've had some really bizarre bugs bite me up to this point with this implementation,
I'll just have to assume there is something odd in my code and keep hunting.

I can't think of a good question to ask at this point, so thanks for all
of the input thus far.  It has been appreciated.

---

Insert movie times and more without leaving Hotmail®. See how.