[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: Joey Rios
Subject: RE: [Help-glpk] Using branch and cut starting with relaxed solution
Date: Fri, 19 Dec 2008 11:04:18 -0800

Hi Michael,

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

I don't know that the relaxed solution is basic.  In fact, I'm pretty sure it isn't.  If I run my regular monolithic (non-decomposed) version of the problem I can (usually) get an integer solution from the glp_simplex call.  When I run the decomposed version, I get the same optimal value, but a non-integer solution.

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

I'm not sure how to use the tools you are talking about here.  How can I say anything about reduced costs if I don't have a basis yet?

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

At this point, I am probably just going to implement a rounding heuristic on the variables and see which constraints I 'break'.  I may end up being OK with a few unsatisfied constraints given the computational efficiency of my decompostion. 


It’s the same Hotmail®. If by “same” you mean up to 70% faster. Get your account now.

reply via email to

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