Context Navigation

← Previous Ticket
Next Ticket →

#20302 new task

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

Reported by:	mkoeppe	Owned by:
Priority:	major	Milestone:	sage-9.3
Component:	numerical	Keywords:	lp
Cc:	dimpase, vdelecroix, vbraun, jdemeyer, chapoton, fbissey, Rudi, novoselt, moritz, jipilab, mmasdeu, klee, tmonteil, mforets, yzh	Merged in:
Authors:		Reviewers:
Report Upstream:	N/A	Work issues:
Branch:		Commit:
Dependencies:	#20296	Stopgaps:

Status badges

Description (last modified by mkoeppe)

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
#20461: Fixes for copying a MIP and its variables
#20657: More fixes for copying a MIP and the MIPVariables created by new_variable
#20462: MixedIntegerLinearProgram/MIPVariable: get_min, set_min, get_max, set_max are broken
#20656: MixedIntegerLinearProgram: Remove _variables dictionary
#20602: MixedIntegerLinearProgram.gen() does not do anything useful

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 tableau-query 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 simplex-only 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 re-solves 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
#20548: py3 print in numerical folder
#18572: CVXOPT solver equations handling
#20323: Common TestSuite for MIP backends
#20424: More tests for common MIP TestSuite
#20325: GenericBackend: Add default implementation of add_variables and add_linear_constraints
#20328: tests related to cplex / gurobi
#20600: more failing tests related to cplex / gurobi
#20360: Add sig_on/sig_off to COINBackend
#20458: GLPKBackend/GLPKExactBackend: Support "glp_simplex followed by glp_exact"

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
#19592: PPL Variables cannot be saved

New backends:

#20296: MixedIntegerLinearProgram: New backend using InteractiveLPProblem
#20413: InteractiveLPBackend: Use standard-form transformation, objective_constant_term, change default base_ring to QQ
#20433: InteractiveLPBackend: Implement set_verbosity
#20376: LoggingBackend - delegating MIP backend class that logs input/output to backend methods
#20446: GLPKExactBackend - a variation on GLPKBackend that sets a solver parameter and signals errors on integer variables
#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 state-of-the-art exact simplex solver
#18765: Add Cython wrappers for GLPK's interface glpssx.h (exact rational simplex)
#18847 create an interface to Mosek optimisation software

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
#20500: LPAbstractDictionary: Refactor leaving_coefficients, entering_coefficients using new methods row_coefficients, column_coefficients
#20203: LPCleanDictionary - floating-point 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
#20447: Wrong result from delsarte_bound_additive_hamming_space with GLPK exact simplex

SDP:

#20506: dual variables handling in SDP solver(s)

Change History (52)

comment:1 Changed 5 years ago by mkoeppe

Description modified (diff)

comment:2 Changed 5 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 5 years ago by mkoeppe (previous) (diff)

comment:3 Changed 5 years ago by mkoeppe

Cc vdelecroix added

comment:4 Changed 5 years ago by mkoeppe

Dependencies set to #20296

comment:5 Changed 5 years ago by mkoeppe

Description modified (diff)

comment:6 Changed 5 years ago by mkoeppe

Description modified (diff)

comment:7 Changed 5 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 5 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