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]

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]

Dependencies: #20296

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

[embray]

comment:89

Ticket retargeted after milestone closed

[mkoeppe]

comment:90

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:93

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

[maxale]

My two cents to add to the list: #34234 and #38799