Metaticket: Improvements to MixedIntegerLinearProgram and its backends
— at Version 38
Reported by: 
Matthias Köppe 
Owned by: 

Priority:

major

Milestone:

sage9.8

Component:

numerical

Keywords:

lp

Cc:

Dima Pasechnik, Vincent Delecroix, Volker Braun, Jeroen Demeyer, Frédéric Chapoton, François Bissey, Rudi Pendavingh, Andrey Novoseltsev, Moritz Firsching, JeanPhilippe Labbé, Marc Masdeu, Kwankyu Lee, Thierry Monteil, Marcelo Forets, Yuan Zhou

Merged in:


Authors:


Reviewers:


Report Upstream:

N/A

Work issues:


Branch:


Commit:


Dependencies:

#20296

Stopgaps:


Frontend defects:
 #20304: More error checking in
MixedIntegerLinearProgram
 #13696: process chained equalities with different signs correctly
 #14540: MILP constraints are silently misunderstood
 #15159: Segfault after deepcopy of
MixedIntegerLinearProgram
Frontend wishlist tickets:
 #20406:
get_solver
should allow passing a function (a solver factory) as the solver argument
 #19523: Raise an error when constraints are added to the wrong MILP
 #20331: A
MIPVariable
's repr should include some useful information
 #18733:
MixedIntegerLinearProgram
should support tableauquery methods
 #18688:
MixedIntegerLinearProgram
should support basis status getting/setting
 #7290: Dual method for linear programs (dup: #13141)
 #7300: Display tight constraints
 #7790: Setting a default max/min bound when calling
MixedIntegerLinearProgram.new_variable
 #15356: linear programming enhancements
 #15583:
sage.numerical.linear_functions.LinearConstraint
is not a hashable type
Improvements to backends:
 #18685: Add basis status functions
get_col_stat
, get_row_stat
to GLPK backend
 #18732: Add tableau query functions
glp_eval_tab_row
, glp_eval_tab_col
to GLPK backend
 #18763: COIN backend should support basis status and tableau data functions
 #18838: GLPK backend does not detect unboundedness in simplexonly mode
 #18764: Add
glp_exact
to Sage's GLPK bindings
 #19471: COIN backend: More basis status and tableau data functions
 #19472: GLPK backend: More basis status and tableau data functions
 #20303: Fixes for
add_variables
in CVXOPT, PPL, GLPK MIP backends and add_linear_constraints
in CVXOPT
 #19525: enhancement: Improve GLPK error handling
 #20332:
CVXOPTBackend
: Set initial problem_name
 #20361: PPL backend resolves the problem every time
get_variable_value
or get_objective_value
is called
 #10232: check GLPK bound errors
 #20354:
PPLBackend
: Add support for integer variables
 #20326:
GenericBackend
: Fix doctest of add_linear_constraint_vector
 #20414: Add
copy
/__copy__
methods to CVXOPT, PPL, InteractiveLP backends
 #18572: CVXOPT solver equations handling
 #20323: Common
TestSuite
for MIP backends
 #20325:
GenericBackend
: Add default implementation of add_variables
and add_linear_constraints
 #20328: tests related to cplex / gurobi
 #20360: Add
sig_on
/sig_off
to COINBackend
Improvements to the backend interface:
 #20337: MIP: Several fixes regarding constant terms in the objective function
 #20324: MIP backends: Unify
add_col
, add_variable
 #20362: MIP backends: Make variable type consistent between
add_variable
, set_variable_type
(with deprecation)
Improvements to underlying libraries:
 #19903 crash with
MIP_Problem
 #20351:
sage.libs.ppl.MIP_Problem
: Add support for integer variables
New backends:
 #20296:
MixedIntegerLinearProgram
: New backend using InteractiveLPProblem
 #20413: InteractiveLPProblem: Use standardform transformation, objective_constant_term
 #20376:
LoggingBackend
 delegating MIP backend class that logs input/output to backend methods
 #18735:
MixedIntegerLinearProgram
/HybridBackend
: Reconstruct exact rational/algebraic basic solution
 #19219: MILP: Add "CyLP" backend
 #18862: Interface to COIN
OpenSolverInterface
 #10879: add optional SCIP integer constraint solver (dup: #8672)
 #18766: Add bindings,
MixedIntegerLinearProgram
backend to qsopt_ex, a stateoftheart exact simplex solver
 #18765: Add Cython wrappers for GLPK's interface glpssx.h (exact rational simplex)
Interactions with InteractiveLinearProgram
and its dictionaries:
 #19097: Refactor run_[revised]_simplex_method; add run_dual_[revised]_simplex_method
 #18742: interactive_simplex_method: Support several styles corresponding to major textbooks
 #18852: interactive_simplex_method: Enable typesetting of run_simplex_method in SageMathCloud?
 #18734: Construct an
interactive_simplex_method.LPDictionary
from a MixedIntegerLinearProgram
 #20311:
interactive_simplex_method
enhancements
 #20203:
LPCleanDictionary
 floatingpoint helper class for interactive simplex method
 #18804:
LPBackendDictionary
 a debugging view of a MIP backend connected to interactive_simplex_method
 #18805: Add didactical implementation of tableau cutting planes to
interactive_simplex_method
Interactions with polyhedra:
 #20301
Polyhedron.to_linear_program
should return the MIP variable used
 #20415
Polyhedron.to_linear_program
should select solver by base_ring
Applications:
 #20367: fix integer option and a bug in Delsarte bounds code
 #20416: Various callers of
MixedIntegerLinearProgram
should accept and pass through a solver argument
Change History (38)
Description: 
modified (diff)

Description: 
modified (diff)

Cc: 
Vincent Delecroix added

Description: 
modified (diff)

Description: 
modified (diff)

Cc: 
Volker Braun added

Description: 
modified (diff)

Summary: 
Clean up MILP backend interface →
Metaticket: Improvements to MixedIntegerLinearProgram and its backends

Type: 
defect →
task

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

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