Opened 5 years ago
Last modified 8 days ago
#20302 new task
Meta-ticket: Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.4 |
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: |
Description (last modified by )
Alternatives:
- #26511: Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...
Proposed packaging change:
- #28175: Move sage optimization backends to separate Cython packages to remove OptionalExtension? problems
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
- #20462:
MixedIntegerLinearProgram
/MIPVariable
:get_min
,set_min
,get_max
,set_max
are broken - #20602: Deprecate
MixedIntegerLinearProgram.gen()
,__call__
,linear_function
, which do not do anything useful; adddefault_variable
method
Frontend improvements:
- #7574: clean up of MIP interface
- #20406:
get_solver
should allow passing a function (a solver factory) as the solver argument - #15583:
sage.numerical.linear_functions.LinearConstraint
is not a hashable type - #20773:
MixedIntegerLinearProgram.new_variable
could optionally take a "static" list of component indices - #23681: Make _repr_ of MILP more informative
- #19523: Raise an error when constraints are added to the wrong MILP
- #20664: Meta-ticket:
MixedIntegerLinearProgram
/MIPVariable
API cleanup - #18733:
MixedIntegerLinearProgram
should support tableau-query methods - #18688:
MixedIntegerLinearProgram
should support basis status getting/setting - #7290: Dual method for linear programs (dup: #13141)
- #18466: Optimal dual solution of LP from
MixedIntegerLinearProgram
- #7300: Display tight constraints
- #15356: linear programming enhancements
- #26511: MIP frontend/backend using PuLP
Backend defects:
- #21825: memory leak in
MixedIntegerLinearProgram
coin backend - #21449:
CoinBackend
: _test_solve fails on 32-bit - #21550: Fix
CoinBackend
testsuite (32-bit failure) - #20303: Fixes for
add_variables
in CVXOPT, PPL, GLPK MIP backends andadd_linear_constraints
in CVXOPT - #18572: CVXOPT solver equations handling
- #20600: more failing tests related to cplex / gurobi
- #20360: Add
sig_on
/sig_off
toCOINBackend
- #28914: default_mip_solver: Allow solver = a callable
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
- #19525: enhancement: Improve GLPK error handling
- #20332:
CVXOPTBackend
: Set initialproblem_name
- #20361: PPL backend re-solves the problem every time
get_variable_value
orget_objective_value
is called - #10232: check GLPK bound errors
- #20354:
PPLBackend
: Add support for integer variables - #20326:
GenericBackend
: Fix doctest ofadd_linear_constraint_vector
- #20414: Add
copy
/__copy__
methods to CVXOPT, PPL, InteractiveLP backends - #20548: py3 print in numerical folder
- #20323: Common
TestSuite
for MIP backends - #20424: More tests for common MIP
TestSuite
- #20325:
GenericBackend
: Add default implementation ofadd_variables
andadd_linear_constraints
- #20328: tests related to cplex / gurobi
- #20458: GLPKBackend/GLPKExactBackend: Support "glp_simplex followed by glp_exact"
- #21563: Add scripts to install Gurobi, Cplex include and lib links in SAGE_LOCAL
- #23680: package Osi
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) - #21498: Unify/document write_lp, write_mps behavior regarding filenames and problem transformations
- #21499:
GenericBackend
: Add _test_sense method
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
- #20876: GLPK: glp_exact ignores verbosity level
- #14645: cvxopt 1.1.6.p0 fails to build with SAGE_SPKG_INSTALL_DOCS=yes
- #22006: CBC tries to use system's blas at runtime which creates an error
- #22380: update cvxopt to 1.1.9
New backends:
- #20296:
MixedIntegerLinearProgram
: New backend usingInteractiveLPProblem
- #20413:
InteractiveLPBackend
: Use standard-form transformation,objective_constant_term
, change defaultbase_ring
toQQ
- #20433:
InteractiveLPBackend
: Implementset_verbosity
- #20376:
LoggingBackend
- delegating MIP backend class that logs input/output to backend methods - #20446:
GLPKExactBackend
- a variation onGLPKBackend
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
- #21094: Sage package for SCIP integer programming solver
- #10879: add optional SCIP integer constraint solver (dup: #8672)
- #21003: Add SCIP backend using PySCIPOpt
- #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
- #21032: MIPCL solver: Add package, MIP backend
- #8661: add lpsolve spkg
- #26511: MIP frontend/backend using PuLP; backend to OSI using yaposib
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 aMixedIntegerLinearProgram
- #20311:
interactive_simplex_method
enhancements - #20500:
LPAbstractDictionary
: Refactorleaving_coefficients
,entering_coefficients
using new methodsrow_coefficients
,column_coefficients
- #20559:
InteractiveLPProblem
, dictionaries:add_constraint
/add_row
methods - #20874:
LPAbstractDictionary
: Addobjective_name
method - #20203:
LPCleanDictionary
- floating-point helper class for interactive simplex method - #18804:
LPBackendDictionary
- a debugging view of a MIP backend connected tointeractive_simplex_method
- #20570:
InteractiveLPProblem
: refactorplot
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 bybase_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 - #20766: avoid using maxima simplex algo in
lattice_polytope
SDP, MINLP, Manifolds:
- #20506: dual variables handling in SDP solver(s)
- #25116: Frontend for Mixed Integer Nonlinear Programming
- #31740: Meta-ticket: Families, posets, complexes of manifold subsets
Documentation:
- #22472: Numerical optimization section of the reference manual needs reorganization
Change History (95)
comment:1 Changed 5 years ago by
- Description modified (diff)
comment:2 Changed 5 years ago by
- Description modified (diff)
comment:3 Changed 5 years ago by
- Cc vdelecroix added
comment:4 Changed 5 years ago by
- Dependencies set to #20296
comment:5 Changed 5 years ago by
- Description modified (diff)
comment:6 Changed 5 years ago by
- Description modified (diff)
comment:7 Changed 5 years ago by
comment:8 Changed 5 years ago by
- 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
comment:9 Changed 5 years ago by
- Description modified (diff)
comment:10 Changed 5 years ago by
- Description modified (diff)
comment:11 Changed 5 years ago by
- Cc jdemeyer added
comment:12 Changed 5 years ago by
- Description modified (diff)
comment:13 Changed 5 years ago by
- Description modified (diff)
comment:14 Changed 5 years ago by
- Description modified (diff)
comment:15 Changed 5 years ago by
- Description modified (diff)
comment:16 Changed 5 years ago by
- Description modified (diff)
comment:17 Changed 5 years ago by
- Description modified (diff)
comment:18 Changed 5 years ago by
- Description modified (diff)
comment:19 Changed 5 years ago by
- Description modified (diff)
comment:20 Changed 5 years ago by
- Description modified (diff)
comment:21 Changed 5 years ago by
- Description modified (diff)
comment:22 Changed 5 years ago by
- Description modified (diff)
comment:23 Changed 5 years ago by
- Description modified (diff)
comment:24 Changed 5 years ago by
- Description modified (diff)
comment:25 Changed 5 years ago by
- Description modified (diff)
comment:26 Changed 5 years ago by
- Description modified (diff)
comment:27 Changed 5 years ago by
- Description modified (diff)
comment:28 Changed 5 years ago by
- Description modified (diff)
comment:29 Changed 5 years ago by
- Description modified (diff)
comment:30 Changed 5 years ago by
- Description modified (diff)
comment:31 Changed 5 years ago by
- Description modified (diff)
comment:32 Changed 5 years ago by
- Description modified (diff)
comment:33 Changed 5 years ago by
- Description modified (diff)
comment:34 Changed 5 years ago by
- Description modified (diff)
comment:35 Changed 5 years ago by
- Description modified (diff)
comment:36 Changed 5 years ago by
- Description modified (diff)
comment:37 Changed 5 years ago by
- Description modified (diff)
comment:38 Changed 5 years ago by
- Description modified (diff)
comment:39 Changed 5 years ago by
- Description modified (diff)
comment:40 Changed 5 years ago by
- Description modified (diff)
comment:41 Changed 5 years ago by
- Description modified (diff)
comment:42 Changed 5 years ago by
- Description modified (diff)
comment:43 Changed 5 years ago by
- Description modified (diff)
comment:44 Changed 5 years ago by
- Description modified (diff)
comment:45 Changed 5 years ago by
- Description modified (diff)
comment:46 Changed 5 years ago by
- Description modified (diff)
comment:47 Changed 5 years ago by
- Description modified (diff)
comment:48 Changed 5 years ago by
- Description modified (diff)
comment:49 Changed 5 years ago by
- Description modified (diff)
comment:50 Changed 5 years ago by
- Description modified (diff)
comment:51 Changed 5 years ago by
- Description modified (diff)
comment:52 Changed 5 years ago by
- Description modified (diff)
comment:53 Changed 5 years ago by
- Description modified (diff)
comment:54 Changed 5 years ago by
- Description modified (diff)
comment:55 Changed 5 years ago by
- Description modified (diff)
comment:56 Changed 5 years ago by
- Cc chapoton added
comment:57 Changed 5 years ago by
- Description modified (diff)
comment:58 Changed 5 years ago by
- Description modified (diff)
comment:59 Changed 5 years ago by
- Cc fbissey added
comment:60 Changed 5 years ago by
- Description modified (diff)
comment:61 Changed 5 years ago by
- Cc Rudi added
comment:62 Changed 5 years ago by
- Cc novoselt added
- Description modified (diff)
- Summary changed from Meta-ticket: Improvements to MixedIntegerLinearProgram and its backends to Meta-ticket: Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram
comment:63 Changed 5 years ago by
- Description modified (diff)
comment:64 Changed 5 years ago by
- Description modified (diff)
- Milestone changed from sage-7.2 to sage-7.3
comment:65 Changed 5 years ago by
- Description modified (diff)
comment:66 Changed 5 years ago by
- Description modified (diff)
comment:67 Changed 5 years ago by
- Description modified (diff)
comment:68 Changed 5 years ago by
- Description modified (diff)
comment:69 Changed 5 years ago by
- Description modified (diff)
comment:70 Changed 5 years ago by
- Description modified (diff)
comment:71 Changed 5 years ago by
- Description modified (diff)
- Milestone changed from sage-7.3 to sage-7.4
comment:72 Changed 5 years ago by
- Description modified (diff)
comment:73 Changed 5 years ago by
- Description modified (diff)
comment:74 Changed 5 years ago by
- Description modified (diff)
- Milestone changed from sage-7.4 to sage-7.5
comment:75 Changed 4 years ago by
- Cc moritz jipilab mmasdeu added
- Description modified (diff)
comment:76 Changed 4 years ago by
- Description modified (diff)
comment:77 Changed 4 years ago by
- Cc klee tmonteil added
- Description modified (diff)
- Milestone changed from sage-7.5 to sage-7.6
comment:78 Changed 4 years ago by
Perhaps I am not that klee
that you think I am. My name is Kwankyu Lee.
comment:79 Changed 4 years ago by
Yes, you wrote ticket #22472 regarding optimization documentation, so I copied you to make sure you are aware of other efforts regarding the optimization code.
comment:80 Changed 4 years ago by
Ok :-)
comment:81 Changed 4 years ago by
- Cc mforets added
comment:82 Changed 4 years ago by
- Cc ncohen removed
- Description modified (diff)
comment:83 Changed 4 years ago by
- Description modified (diff)
comment:84 Changed 3 years ago by
- Description modified (diff)
comment:85 Changed 3 years ago by
- Description modified (diff)
- Milestone changed from sage-7.6 to sage-8.5
comment:86 Changed 3 years ago by
- Description modified (diff)
comment:87 Changed 17 months ago by
- Description modified (diff)
- Milestone changed from sage-8.5 to sage-9.0
comment:88 Changed 17 months ago by
- Description modified (diff)
comment:89 Changed 16 months ago by
- Milestone changed from sage-9.0 to sage-9.1
Ticket retargeted after milestone closed
comment:90 Changed 13 months ago by
- Milestone changed from sage-9.1 to sage-9.2
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.
comment:91 Changed 8 months ago by
- Milestone changed from sage-9.2 to sage-9.3
comment:92 Changed 3 months ago by
- Cc yzh added
comment:93 Changed 6 weeks ago by
- Milestone changed from sage-9.3 to sage-9.4
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.
comment:94 Changed 8 days ago by
- Description modified (diff)
comment:95 Changed 8 days ago by
- 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