Opened 3 years ago

Last modified 11 months ago

#20302 new task

Meta-ticket: Improvements to MixedIntegerLinearProgram and its backends — at Version 8

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 mkoeppe)

Frontend:

Backends:

  • #20303: Fixes for add_variables in CVXOPT, PPL, GLPK MIP backends and add_linear_constraints in CVXOPT

Interactions with InteractiveLinearProgram? and its dictionaries:

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.)

Change History (8)

comment:1 Changed 3 years ago by mkoeppe

  • Description modified (diff)

comment:2 Changed 3 years ago by mkoeppe

  • Description modified (diff)

Description modified to remove my comments about variable_upper_bound and variable_lower_bound. I was misled by the interface description in GenericBackend, which was out of sync with the real backends. Fixed in #20296

Last edited 3 years ago by mkoeppe (previous) (diff)

comment:3 Changed 3 years ago by mkoeppe

  • Cc vdelecroix added

comment:4 Changed 3 years ago by mkoeppe

  • Dependencies set to #20296

comment:5 Changed 3 years ago by mkoeppe

  • Description modified (diff)

comment:6 Changed 3 years ago by mkoeppe

  • Description modified (diff)

comment:7 Changed 3 years ago by vdelecroix

Hello,

I guess that you do not want to fix all of that in one ticket. One possibility is to use this one as a "task ticket" pointing to other tickets. See for example #18846, #17601 or #18333.

comment:8 Changed 3 years ago by mkoeppe

  • 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
Note: See TracTickets for help on using tickets.