|Subject:||RE: [Help-glpk] Using branch and cut starting with relaxed solution|
|Date:||Fri, 19 Dec 2008 11:04:18 -0800|
> 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.
Its the same Hotmail®. If by same you mean up to 70% faster. Get your account now.
|[Prev in Thread]||Current Thread||[Next in Thread]|