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.
http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_hotmail_acq_broad1_122008
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
