help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Michael Hennebry
Subject: RE: [Help-glpk] Min. problem with reduced costs < 0, but simplex fails to progress
Date: Mon, 18 May 2009 18:47:11 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]