Opened 3 years ago
Last modified 7 months ago
#20302 new task
Meta-ticket: Improvements to MixedIntegerLinearProgram and its backends — at Version 9
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.5 |
Component: | numerical | Keywords: | lp |
Cc: | dimpase, vdelecroix, vbraun, jdemeyer, chapoton, fbissey, Rudi, novoselt, moritz, jipilab, mmasdeu, klee, tmonteil, mforets | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #20296 | Stopgaps: |
Description (last modified by )
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 aMixedIntegerLinearProgram
- #20311:
interactive_simplex_method
enhancements - #20296:
MixedIntegerLinearProgram
: New backend usingInteractiveLPProblem
- #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 tointeractive_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
andadd_variable
both add a variable to the problem; butadd_col
only allows to add a column with no name; whereasadd_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 deprecateadd_col
. Note thatadd_col
is not used byMixedIntegerLinearProgram
; it is only used in doctests of the backends. (Also compare withadd_linear_constraint
, which takes a zipped index/coefficient list, whereasadd_col
takes two parallel lists.)
add_variables
andadd_linear_constraints
should have a default implementation inGenericBackend
, likeadd_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.)
Change History (9)
comment:1 Changed 3 years ago by
- Description modified (diff)
comment:2 Changed 3 years ago by
- Description modified (diff)
comment:3 Changed 3 years ago by
- Cc vdelecroix added
comment:4 Changed 3 years ago by
- Dependencies set to #20296
comment:5 Changed 3 years ago by
- Description modified (diff)
comment:6 Changed 3 years ago by
- Description modified (diff)
comment:7 Changed 3 years ago by
comment:8 Changed 3 years ago by
- Cc vbraun added
- Description modified (diff)
- Summary changed from Clean up MILP backend interface to Meta-ticket: Improvements to MixedIntegerLinearProgram and its backends
- Type changed from defect to task
comment:9 Changed 3 years ago by
- Description modified (diff)
Description modified to remove my comments about
variable_upper_bound
andvariable_lower_bound
. I was misled by the interface description inGenericBackend
, which was out of sync with the real backends. Fixed in #20296