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

[Michael Hennebry]

On Sat, 16 May 2009, Joey Rios wrote:

> > 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.

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.

> 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.

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."