#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`
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.)
--
--
Ticket URL: <http://trac.sagemath.org/ticket/20302#comment:9>
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.
