Meta-ticket: Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram

[mkoeppe]

Alternatives:

• Meta-ticket: Use Python optimization interfaces: CVXPY, SCIP, or-tools, PuLP, Pyomo, cylp... #26511: Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...

Proposed packaging change:

• Move optional sage optimization backends (COIN, CPLEX, Gurobi) to separate Cython packages to remove OptionalExtension problems #28175: Move sage optimization backends to separate Cython packages to remove OptionalExtension problems

Frontend defects:

• More error checking in MixedIntegerLinearProgram #20304: More error checking in MixedIntegerLinearProgram
• process chained equalities with different signs correctly #13696: process chained equalities with different signs correctly
• Fix chaining of MILP constraints #14540: MILP constraints are silently misunderstood
• Segfault after deepcopy of MixedIntegerLinearProgram #15159: Segfault after deepcopy of MixedIntegerLinearProgram
• Fixes for copying a MIP and its variables #20461: Fixes for copying a MIP and its variables
• MixedIntegerLinearProgram/MIPVariable: set_min, set_max are broken #20462: MixedIntegerLinearProgram/MIPVariable: get_min, set_min, get_max, set_max are broken
• Deprecate MixedIntegerLinearProgram.gen(), __call__, linear_function, which do not do anything useful; add default_variable method #20602: Deprecate MixedIntegerLinearProgram.gen(), __call__, linear_function, which do not do anything useful; add default_variable method

Frontend improvements:

• clean up of MIP interface #7574: clean up of MIP interface
• get_solver should allow passing a function (a solver factory) as the solver argument #20406: get_solver should allow passing a function (a solver factory) as the solver argument
• sage.numerical.linear_functions.LinearConstraint is not a hashable type #15583: sage.numerical.linear_functions.LinearConstraint is not a hashable type
• MixedIntegerLinearProgram.new_variable could optionally take a "static" list of component indices #20773: MixedIntegerLinearProgram.new_variable could optionally take a "static" list of component indices
• Make _repr_ of MILP more informative #23681: Make _repr_ of MILP more informative
• Raise an error when constraints are added to the wrong MILP #19523: Raise an error when constraints are added to the wrong MILP
• Meta-ticket: MixedIntegerLinearProgram/MIPVariable API cleanup #20664: Meta-ticket: MixedIntegerLinearProgram/MIPVariable API cleanup
• MixedIntegerLinearProgram should support tableau-query methods getBInvARow, getBInvRow, getBInvACol, getBInvCol #18733: MixedIntegerLinearProgram should support tableau-query methods
• MixedIntegerLinearProgram should support basis status getting/setting #18688: MixedIntegerLinearProgram should support basis status getting/setting
• Dual method for linear programs #7290: Dual method for linear programs (dup: implement constructing the dual of a linear program #13141)
• Optimal dual solution of LP from MixedIntegerLinearProgram #18466: Optimal dual solution of LP from MixedIntegerLinearProgram
• Display tight constraints #7300: Display tight constraints
• linear programming enhancements #15356: linear programming enhancements
• Meta-ticket: Use Python optimization interfaces: CVXPY, SCIP, or-tools, PuLP, Pyomo, cylp... #26511: MIP frontend/backend using PuLP

Backend defects:

• memory leak in MixedIntegerLinearProgram coin backend #21825: memory leak in MixedIntegerLinearProgram coin backend
• CoinBackend: _test_solve fails on 32-bit #21449: CoinBackend: _test_solve fails on 32-bit
• Fix CoinBackend testsuite _test_solve on 32 bit #21550: Fix CoinBackend testsuite (32-bit failure)
• Fixes for add_variables in CVXOPT, PPL, GLPK MIP backends and add_linear_constraints in CVXOPT #20303: Fixes for add_variables in CVXOPT, PPL, GLPK MIP backends and add_linear_constraints in CVXOPT
• CVXOPT solver equations handling #18572: CVXOPT solver equations handling
• more failing tests related to cplex / gurobi #20600: more failing tests related to cplex / gurobi
• Add sig_on/sig_off to COINBackend #20360: Add sig_on/sig_off to COINBackend
• default_mip_solver: Allow solver = a callable #28914: default_mip_solver: Allow solver = a callable

Improvements to backends:

• Add basis status functions get_col_stat, get_row_stat to GLPK backend #18685: Add basis status functions get_col_stat, get_row_stat to GLPK backend
• Add tableau query functions glp_eval_tab_row, glp_eval_tab_col to GLPK backend #18732: Add tableau query functions glp_eval_tab_row, glp_eval_tab_col to GLPK backend
• COIN backend should support basis status and tableau data functions #18763: COIN backend should support basis status and tableau data functions
• GLPK backend does not detect unboundedness in simplex-only mode #18838: GLPK backend does not detect unboundedness in simplex-only mode
• Add glp_exact to Sage's GLPK bindings #18764: Add glp_exact to Sage's GLPK bindings
• COIN backend: More basis status and tableau data functions #19471: COIN backend: More basis status and tableau data functions
• GLPK backend: More basis status and tableau data functions #19472: GLPK backend: More basis status and tableau data functions
• Improve GLPK error handling #19525: enhancement: Improve GLPK error handling
• CVXOPTBackend: Set initial problem_name #20332: CVXOPTBackend: Set initial problem_name
• PPL backend re-solves the problem every time get_variable_value or get_objective_value is called #20361: PPL backend re-solves the problem every time get_variable_value or get_objective_value is called
• check GLPK bound errors #10232: check GLPK bound errors
• PPLBackend: Add support for integer variables #20354: PPLBackend: Add support for integer variables
• GenericBackend: Fix doctest of add_linear_constraint_vector #20326: GenericBackend: Fix doctest of add_linear_constraint_vector
• Add copy/__copy__ methods to CVXOPT, PPL, InteractiveLP backends, and __deepcopy__ to MixedIntegerLinearProgram and backends #20414: Add copy/__copy__ methods to CVXOPT, PPL, InteractiveLP backends
• py3 print in numerical folder #20548: py3 print in numerical folder
• Common TestSuite for MIP backends #20323: Common TestSuite for MIP backends
• More tests for common MIP TestSuite: add_col, solve; some fixes for backends #20424: More tests for common MIP TestSuite
• GenericBackend: Add default implementation of add_variables and add_linear_constraints #20325: GenericBackend: Add default implementation of add_variables and add_linear_constraints
• tests related to cplex / gurobi #20328: tests related to cplex / gurobi
• GLPKBackend/GLPKExactBackend: Support "glp_simplex followed by glp_exact" #20458: GLPKBackend/GLPKExactBackend: Support "glp_simplex followed by glp_exact"
• Add scripts to install Gurobi, Cplex include and lib links in SAGE_LOCAL #21563: Add scripts to install Gurobi, Cplex include and lib links in SAGE_LOCAL
• package Osi #23680: package Osi

Improvements to the backend interface:

• MIP: Several fixes regarding constant terms in the objective function #20337: MIP: Several fixes regarding constant terms in the objective function
• MIP backends: Unify add_col, add_variable; and clarify defaulting behavior of binary, continuous, integer #20324: MIP backends: Unify add_col, add_variable
• MIP backends: Make variable type consistent between add_variable, set_variable_type (with deprecation) #20362: MIP backends: Make variable type consistent between add_variable, set_variable_type (with deprecation)
• Unify/document write_lp, write_mps behavior regarding filenames and problem transformations #21498: Unify/document write_lp, write_mps behavior regarding filenames and problem transformations
• GenericBackend: Add _test_sense method #21499: GenericBackend: Add _test_sense method

Improvements to underlying libraries:

• crash with MIP_Problem #19903 crash with MIP_Problem
• sage.libs.ppl.MIP_Problem: Add support for integer variables #20351: sage.libs.ppl.MIP_Problem: Add support for integer variables
• PPL Variables cannot be saved #19592: PPL Variables cannot be saved
• GLPK: glp_exact ignores verbosity level #20876: GLPK: glp_exact ignores verbosity level
• cvxopt 1.1.8 fails to build with SAGE_SPKG_INSTALL_DOCS=yes #14645: cvxopt 1.1.6.p0 fails to build with SAGE_SPKG_INSTALL_DOCS=yes
• CBC tries to use system's blas at runtime which creates an error #22006: CBC tries to use system's blas at runtime which creates an error
• Upgrade to cvxopt 1.2.x #22380: update cvxopt to 1.1.9

New backends:

• MixedIntegerLinearProgram: New backend using InteractiveLPProblem #20296: MixedIntegerLinearProgram: New backend using InteractiveLPProblem
• InteractiveLPBackend: Use standard-form transformation, objective_constant_term, change default base_ring to QQ #20413: InteractiveLPBackend: Use standard-form transformation, objective_constant_term, change default base_ring to QQ
• InteractiveLPBackend: Implement set_verbosity #20433: InteractiveLPBackend: Implement set_verbosity
• LoggingBackend - delegating MIP backend class that logs input/output to backend methods #20376: LoggingBackend - delegating MIP backend class that logs input/output to backend methods
• GLPKExactBackend - a variation on GLPKBackend that sets a solver parameter and signals errors on integer variables #20446: GLPKExactBackend - a variation on GLPKBackend that sets a solver parameter and signals errors on integer variables
• MixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution #18735: MixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution
• MILP: Add CyLP backend #19219: MILP: Add "CyLP" backend
• Interface to COIN OpenSolverInterface #18862: Interface to COIN OpenSolverInterface
• Sage package for SCIP integer programming solver #21094: Sage package for SCIP integer programming solver
• add optional SCIP integer constraint solver #10879: add optional SCIP integer constraint solver (dup: SCIP support #8672)
• Add package pyscipopt, add MIP backend #21003: Add SCIP backend using PySCIPOpt
• Add bindings, MixedIntegerLinearProgram backend to qsopt_ex, a state-of-the-art exact simplex solver #18766: Add bindings, MixedIntegerLinearProgram backend to qsopt_ex, a state-of-the-art exact simplex solver
• Add Cython wrappers for GLPK's interface glpssx.h (exact rational simplex) #18765: Add Cython wrappers for GLPK's interface glpssx.h (exact rational simplex)
• create an interface to Mosek optimisation software #18847 create an interface to Mosek optimisation software
• MIPCL solver: Add package, MIP backend #21032: MIPCL solver: Add package, MIP backend
• add lpsolve spkg #8661: add lpsolve spkg
• Meta-ticket: Use Python optimization interfaces: CVXPY, SCIP, or-tools, PuLP, Pyomo, cylp... #26511: MIP frontend/backend using PuLP; backend to OSI using yaposib

Interactions with InteractiveLinearProgram and its dictionaries:

• Refactor run_[revised]_simplex_method; add run_dual_[revised]_simplex_method #19097: Refactor run_[revised]simplex_method; add run_dual[revised]_simplex_method
• interactive_simplex_method: Support several styles corresponding to major textbooks #18742: interactive_simplex_method: Support several styles corresponding to major textbooks
• interactive_simplex_method: Enable typesetting of run_simplex_method in SageMathCloud #18852: interactive_simplex_method: Enable typesetting of run_simplex_method in SageMathCloud
• Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram #18734: Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram
• interactive_simplex_method enhancements #20311: interactive_simplex_method enhancements
• LPAbstractDictionary: Refactor leaving_coefficients, entering_coefficients using new methods row_coefficients, column_coefficients #20500: LPAbstractDictionary: Refactor leaving_coefficients, entering_coefficients using new methods row_coefficients, column_coefficients
• InteractiveLPProblem, dictionaries: add_constraint / add_row methods #20559: InteractiveLPProblem, dictionaries: add_constraint / add_row methods
• LPAbstractDictionary: Add objective_name method #20874: LPAbstractDictionary: Add objective_name method
• LPCleanDictionary - floating-point helper class for interactive simplex method #20203: LPCleanDictionary - floating-point helper class for interactive simplex method
• LPBackendDictionary - a debugging view of a MIP backend connected to interactive_simplex_method #18804: LPBackendDictionary - a debugging view of a MIP backend connected to interactive_simplex_method
• InteractiveLPProblem: refactor plot method #20570: InteractiveLPProblem: refactor plot method
• Add didactical implementation of tableau cutting planes to interactive_simplex_method #18805: Add didactical implementation of tableau cutting planes to interactive_simplex_method

Interactions with polyhedra:

• Polyhedron.to_linear_program should return the MIP variable used #20301 Polyhedron.to_linear_program should return the MIP variable used
• Polyhedron.to_linear_program should select solver by base_ring #20415 Polyhedron.to_linear_program should select solver by base_ring

Applications:

• fix integer option and a bug in Delsarte bounds code #20367: fix integer option and a bug in Delsarte bounds code
• Various callers of MixedIntegerLinearProgram should accept and pass through a solver argument #20416: Various callers of MixedIntegerLinearProgram should accept and pass through a solver argument
• Wrong result from delsarte_bound_additive_hamming_space with GLPK exact simplex #20447: Wrong result from delsarte_bound_additive_hamming_space with GLPK exact simplex
• avoid using maxima simplex algo in lattice_polytope #20766: avoid using maxima simplex algo in lattice_polytope

SDP, MINLP, Manifolds:

• dual variables handling in SDP solver(s) #20506: dual variables handling in SDP solver(s)
• Frontend for Mixed Integer Nonlinear Programming #25116: Frontend for Mixed Integer Nonlinear Programming
• Meta-ticket: Families, posets, complexes of manifold subsets #31740: Meta-ticket: Families, posets, complexes of manifold subsets

Documentation:

• Numerical optimization section of the reference manual needs reorganization #22472: Numerical optimization section of the reference manual needs reorganization

Depends on #20296

CC: @dimpase @videlec @vbraun @jdemeyer @fchapoton @kiwifb @sagetrac-Rudi @novoselt @mo271 @jplab @mmasdeu @kwankyu @sagetrac-tmonteil @mforets @yuan-zhou

Component: numerical

Issue created by migration from https://trac.sagemath.org/ticket/20302

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,6 +1,6 @@
 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) that can do both; should then deprecate `add_col`. (Also compare with `add_linear_constraint`, which takes as zipped index/coefficient list, whereas `add_col` takes two parallel lists.)
+- `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`. (Also compare with `add_linear_constraint`, which takes a zipped index/coefficient list, whereas `add_col` takes two parallel lists.)
 
 - `variable_upper_bound`: This interface is bizarre.  Can't remove an upper bound from a variable because `None` means both 'no upper bound' and 'get the upper bound'. Likewise `variable_lower_bound`. (Moreover, there's redundancy with `col_bounds`.)
 

[mkoeppe]

comment:2

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

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,8 +1,6 @@
 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`. (Also compare with `add_linear_constraint`, which takes a zipped index/coefficient list, whereas `add_col` takes two parallel lists.)
-
-- `variable_upper_bound`: This interface is bizarre.  Can't remove an upper bound from a variable because `None` means both 'no upper bound' and 'get the upper bound'. Likewise `variable_lower_bound`. (Moreover, there's redundancy with `col_bounds`.)
 
 - `add_variables` and `add_linear_constraints` should have a default implementation in `GenericBackend`, like `add_linear_constraint_vector`.
 

[mkoeppe]

Dependencies: #20296

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,6 +1,6 @@
 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`. (Also compare with `add_linear_constraint`, which takes a zipped index/coefficient list, whereas `add_col` takes two parallel lists.)
+- `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`.
 

[mkoeppe]

Description changed:

--- 
+++ 
@@ -4,5 +4,37 @@
 
 - `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.)
 

[videlec]

comment:7

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.

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,3 +1,27 @@
+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.)