Meta-ticket: Improvements to MixedIntegerLinearProgram and its backends

[mkoeppe]

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

[mkoeppe]

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

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