id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
20302 Meta-ticket: Improvements to MixedIntegerLinearProgram and its backends Matthias Köppe "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.)
" task new major sage-7.2 numerical lp Dima Pasechnik Nathann Cohen Vincent Delecroix Volker Braun N/A #20296