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

[Michael Hennebry]

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