#18688: MixedIntegerLinearProgram should support basis status getting/setting
----------------------------------+------------------------
Reporter: mkoeppe | Owner:
Type: task | Status: new
Priority: minor | Milestone: sage-6.8
Component: numerical | Resolution:
Keywords: lp | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #18685, #18763 | Stopgaps:
----------------------------------+------------------------
Description changed by mkoeppe:
Old description:
> When Sage's `MixedIntegerLinearProgram` is used for solving an LP, one
> frequently needs to access further information about the current basis
> (often, the optimal basis after solving the LP), not just the numerical
> values of the solution; in particular, the combinatorial information:
> which variables are basic, nonbasic at-lower, nonbasic at-upper.
>
> #18685 adds the necessary backend functions for the GLPK backend.
> #18763 adds the necessary backend functions for the COIN (CBC/CLP)
> backend.
> This kind of information is available in most (simplex method based)
> solvers. (Exceptions: ppl does not seem to have a public interface to
> anything simplex tableau related.)
>
> The Sage interface should, of course, be designed to work consistently
> across all solvers. There are some subtleties here -- not all solvers
> mean the same thing with "at-lower" for cases such as ranged constraints.
> Best to look at a source that has already sorted it all out: In the COIN
> open solver interface, [https://projects.coin-
> or.org/Osi/browser/trunk/Osi/src?order=name] the function is called
> [https://projects.coin-
> or.org/Osi/browser/trunk/Osi/src/Osi/OsiSolverInterface.hpp#L1811
> getBasisStatus]
>
> And then there's setBasisStatus, of course. One needs this function if
> one wants to implement LP-based branch and bound with warmstarting.
>
> There are other important basis-related functions: [https://projects
> .coin-or.org/Osi/browser/trunk/Osi/src/Osi/OsiSolverInterface.hpp#L1860
> getBInvARow], getBInvRow, getBInvACol, getBInvCol -- but that's for
> another ticket -- see #18733.
New description:
When Sage's `MixedIntegerLinearProgram` is used for solving an LP, one
frequently needs to access further information about the current basis
(often, the optimal basis after solving the LP), not just the numerical
values of the solution; in particular, the combinatorial information:
which variables are basic, nonbasic at-lower, nonbasic at-upper.
#18685 adds the necessary backend functions for the GLPK backend.
#18763 adds the necessary backend functions for the COIN (CBC/CLP)
backend.
This kind of information is available in most (simplex method based)
solvers. (Exceptions: ppl does not seem to have a public interface to
anything simplex tableau related.)
The Sage interface should, of course, be designed to work consistently
across all solvers. There are some subtleties here -- not all solvers mean
the same thing with "at-lower" for cases such as ranged constraints. Best
to look at a source that has already sorted it all out: In the COIN open
solver interface, [https://projects.coin-
or.org/Osi/browser/trunk/Osi/src?order=name] the function is called
[https://projects.coin-
or.org/Osi/browser/trunk/Osi/src/Osi/OsiSolverInterface.hpp#L1811
getBasisStatus]
And then there's setBasisStatus, of course. One needs this function if one
wants to implement LP-based branch and bound with warmstarting.
There are other important basis-related functions: [https://projects.coin-
or.org/Osi/browser/trunk/Osi/src/Osi/OsiSolverInterface.hpp#L1860
getBInvARow], getBInvRow, getBInvACol, getBInvCol -- but that's for
another ticket -- see #18733.
See also #18804 (LPBackendDictionary).
--
--
Ticket URL: <http://trac.sagemath.org/ticket/18688#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
