[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."
- [Help-glpk] Using branch and cut starting with relaxed solution, Joey Rios, 2008/12/17
- Re: [Help-glpk] Using branch and cut starting with relaxed solution, Andrew Makhorin, 2008/12/19
- RE: [Help-glpk] Using branch and cut starting with relaxed solution, Joey Rios, 2008/12/19
- Re: [Help-glpk] Using branch and cut starting with relaxed solution, Ali Baharev, 2008/12/19
- RE: [Help-glpk] Using branch and cut starting with relaxed solution, Joey Rios, 2008/12/19
- RE: [Help-glpk] Using branch and cut starting with relaxed solution,
Michael Hennebry <=
- RE: [Help-glpk] Using branch and cut starting with relaxed solution, Joey Rios, 2008/12/19
- RE: [Help-glpk] Using branch and cut starting with relaxed solution, Michael Hennebry, 2008/12/19
- Re: [Help-glpk] Using branch and cut starting with relaxed solution, Andrew Makhorin, 2008/12/19
- RE: [Help-glpk] Using branch and cut starting with relaxed solution, Joey Rios, 2008/12/19