#20302: Meta-ticket: Improvements to MixedIntegerLinearProgram and its backends
-----------------------------+------------------------
Reporter: mkoeppe | Owner:
Type: task | Status: new
Priority: major | Milestone: sage-7.2
Component: numerical | Resolution:
Keywords: lp | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #20296 | Stopgaps:
-----------------------------+------------------------
Description changed by mkoeppe:
Old description:
> Frontend:
> - #20304: More error checking in `MixedIntegerLinearProgram`
>
> Backends:
> - #20303: Fixes for add_variables in CVXOPT, PPL, GLPK MIP backends and
> `add_linear_constraints` in CVXOPT
>
> Interactions with `InteractiveLinearProgram` and its dictionaries:
> - #18734: Construct an `interactive_simplex_method.LPDictionary` from a
> `MixedIntegerLinearProgram`
> - #20311: `interactive_simplex_method` enhancements
> - #20296: `MixedIntegerLinearProgram`: New backend using
> `InteractiveLPProblem`
> - #18735: `MixedIntegerLinearProgram`/`HybridBackend`: Reconstruct exact
> rational/algebraic basic solution
> - #20203: `LPCleanDictionary` - floating-point helper class for
> interactive simplex method
> - #18804: `LPBackendDictionary` - a debugging view of a MIP backend
> connected to `interactive_simplex_method`
>
> Interactions with polyhedra:
> - #20301 `Polyhedron.to_linear_program` should return the MIP variable
> used
>
> * * * *
>
> To be put on separate tickets:
>
> Clean up MILP backend interface:
>
> While implementing `InteractiveLPBackend` for #20296, I noticed several
> deficiencies in the design of the MILP backend interface.
>
> - `add_col` and `add_variable` both add a variable to the problem; but
> `add_col` only allows to add a column with no name; whereas
> `add_variable` only allows to add a column with no coefficients. There
> should be one function (`add_variable`, probably - see #20296 for a
> possible interface) that can do both; should then deprecate `add_col`.
> Note that `add_col` is not used by `MixedIntegerLinearProgram`; it is
> only used in doctests of the backends. (Also compare with
> `add_linear_constraint`, which takes a zipped index/coefficient list,
> whereas `add_col` takes two parallel lists.)
>
> - `add_variables` and `add_linear_constraints` should have a default
> implementation in `GenericBackend`, like `add_linear_constraint_vector`.
>
> - The doctest of `add_linear_constraint_vector` from generic_backend.pyx
> (which is never run for any real backend!), when applied to COIN or GLPK
> leads to segfaults:
> {{{
> sage: sage: coeffs = ([0, vector([1, 2])], [1, vector([2,
> 3])])
> sage: sage: upper = vector([5, 5])
> sage: sage: lower = vector([0, 0])
> sage: sage: from sage.numerical.backends.generic_backend
> import get_solver
> sage: sage: p = get_solver(solver = "Coin")
> # optional - cbc
> sage: p.add_linear_constraint_vector(2, coeffs, lower, upper, 'foo')
> ------------------------------------------------------------------------
> 0 signals.so 0x0000000109df05c5
> print_backtrace + 37
> ------------------------------------------------------------------------
> Unhandled SIGSEGV: A segmentation fault occurred.
> This probably occurred because a *compiled* module has a bug
> in it and is not properly wrapped with sig_on(), sig_off().
> Python will now terminate.
> ------------------------------------------------------------------------
> Segmentation fault: 11
> $ sage
> SageMath Version 7.2.beta0, Release Date: 2016-03-24
> sage: sage: sage: coeffs = ([0, vector([1, 2])], [1,
> vector([2, 3])])
> sage: sage: sage: upper = vector([5, 5])
> sage: sage: sage: lower = vector([0, 0])
> sage: sage: sage: from
> sage.numerical.backends.generic_backend import get_solver
> sage: sage: sage: p = get_solver(solver = "Coin")
> # optional - cbc
> sage: p.add_linear_constraint_vector(2, coeffs, lower, upper)
> ------------------------------------------------------------------------
> 0 signals.so 0x0000000109c8a5c5
> print_backtrace + 37
> ------------------------------------------------------------------------
> Unhandled SIGSEGV: A segmentation fault occurred.
> }}}
>
> Also, I think the backends should be tested using a common `TestSuite`.
> Right now each backend uses its own doctests, which have slightly
> diverged from each other, so there is nothing (other than the fact that
> they were the result of copy-paste from each other) that ensures
> consistency. (#20296 fixes several wrong doctests in `GenericBackend`,
> from which I tried to copy-paste, for example.)
New description:
Frontend:
- #20304: More error checking in `MixedIntegerLinearProgram`
- #19523: defect: Adding constraints for the wrong MILP crashes Sage
- #18733: enhancement: `MixedIntegerLinearProgram` should support
tableau-query methods
- #18688: task: `MixedIntegerLinearProgram` should support basis status
getting/setting
Backends:
- #20303: Fixes for `add_variables` in CVXOPT, PPL, GLPK MIP backends and
`add_linear_constraints` in CVXOPT
- #19525: enhancement: Improve GLPK error handling
- #20323: Common `TestSuite` for MIP backends
- #20324: MIP backends: Unify `add_col`, `add_variable`
- #20325: `GenericBackend`: Add default implementation of `add_variables`
and `add_linear_constraints`
- #20326: `GenericBackend`: Fix doctest of add_linear_constraint_vector
Interactions with `InteractiveLinearProgram` and its dictionaries:
- #18734: Construct an `interactive_simplex_method.LPDictionary` from a
`MixedIntegerLinearProgram`
- #20311: `interactive_simplex_method` enhancements
- #20296: `MixedIntegerLinearProgram`: New backend using
`InteractiveLPProblem`
- #18735: `MixedIntegerLinearProgram`/`HybridBackend`: Reconstruct exact
rational/algebraic basic solution
- #20203: `LPCleanDictionary` - floating-point helper class for
interactive simplex method
- #18804: `LPBackendDictionary` - a debugging view of a MIP backend
connected to `interactive_simplex_method`
Interactions with polyhedra:
- #20301 `Polyhedron.to_linear_program` should return the MIP variable
used
--
--
Ticket URL: <http://trac.sagemath.org/ticket/20302#comment:10>
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.
