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

[Joey Rios]

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. 

Joey

---

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