[Top][All Lists]

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

RE: [Help-glpk] Using branch and cut starting with relaxed solution

From: Michael Hennebry
Subject: RE: [Help-glpk] Using branch and cut starting with relaxed solution
Date: Fri, 19 Dec 2008 11:35:53 -0600 (CST)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

On Fri, 19 Dec 2008, Joey Rios wrote:

You are completely correct.  Though, I'm finding the relaxed solution right now 
via a decomposition method (which is why I have no basis at the end) and I'm 
finding it up to 100X faster than glp_simplex would otherwise.  Since this is 
the case, I'd love to use that as a starting point for branching.  My problems 
are very big (up to several days to run using glp_simplex).

If the relaxed solution found is known to be basic,
the LP can be greatly reduced for the purpose of finding the basis.
Simply remove every constraint that is known to not be tight.
When you put them back, every added variable will be basic.

Finding a basis is trickier if the relaxed solution is not known to be basic.
Degeneracy and near degeneracy often present the
problem of how to tell something small from zero.
It's not always solvable.
Reduced costs can help.
If an optimal reduced cost is known to be nonzero,
the corresponding constraint must be tight.
If there is no optimal solution for which a constraint is tight,
that constraint may be dropped.

If the factor of 100 persists in the B&B subproblems,
you might want to consider rolling your own
so that you can take advantage of decomposition.

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]