Opened 17 months ago

Last modified 20 hours ago

#20302 new task

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

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

Description (last modified by jdemeyer)

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; add default_variable method
  • #20656: MixedIntegerLinearProgram: Remove _variables dictionary
  • #20657: More fixes for copying a MIP and the MIPVariables created by new_variable

Frontend wishlist tickets:

  • #7574: clean up of MIP interface
  • #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
  • #20664: MixedIntegerLinearProgram/MIPVariable API cleanup
  • #20773: MixedIntegerLinearProgram.new_variable could optionally take a "static" list of component indices
  • #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)
  • #18466: Optimal dual solution of LP from MixedIntegerLinearProgram
  • #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
  • #23681: Make _repr_ of MILP more informative

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 and add_linear_constraints in CVXOPT
  • #18572: CVXOPT solver equations handling
  • #20600: more failing tests related to cplex / gurobi
  • #20360: Add sig_on/sig_off to COINBackend

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 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
  • #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
  • #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 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
  • #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

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
  • #20559: InteractiveLPProblem, dictionaries: add_constraint / add_row methods
  • #20874: LPAbstractDictionary: Add objective_name method
  • #20203: LPCleanDictionary - floating-point helper class for interactive simplex method
  • #18804: LPBackendDictionary - a debugging view of a MIP backend connected to interactive_simplex_method
  • #20570: InteractiveLPProblem: refactor plot 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
  • #20766: avoid using maxima simplex algo in lattice_polytope

SDP:

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

Documentation:

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

Change History (83)

comment:1 Changed 17 months ago by mkoeppe

  • Description modified (diff)

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

comment:3 Changed 17 months ago by mkoeppe

  • Cc vdelecroix added

comment:4 Changed 17 months ago by mkoeppe

  • Dependencies set to #20296

comment:5 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:6 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:7 Changed 17 months 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 17 months 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

comment:9 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:10 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:11 Changed 17 months ago by mkoeppe

  • Cc jdemeyer added

comment:12 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:13 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:14 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:15 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:16 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:17 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:18 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:19 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:20 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:21 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:22 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:23 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:24 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:25 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:26 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:27 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:28 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:29 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:30 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:31 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:32 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:33 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:34 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:35 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:36 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:37 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:38 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:39 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:40 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:41 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:42 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:43 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:44 Changed 17 months ago by mkoeppe

  • Description modified (diff)

comment:45 Changed 16 months ago by mkoeppe

  • Description modified (diff)

comment:46 Changed 16 months ago by mkoeppe

  • Description modified (diff)

comment:47 Changed 16 months ago by mkoeppe

  • Description modified (diff)

comment:48 Changed 16 months ago by mkoeppe

  • Description modified (diff)

comment:49 Changed 16 months ago by mkoeppe

  • Description modified (diff)

comment:50 Changed 16 months ago by mkoeppe

  • Description modified (diff)

comment:51 Changed 15 months ago by mkoeppe

  • Description modified (diff)

comment:52 Changed 15 months ago by mkoeppe

  • Description modified (diff)

comment:53 Changed 15 months ago by mkoeppe

  • Description modified (diff)

comment:54 Changed 15 months ago by mkoeppe

  • Description modified (diff)

comment:55 Changed 15 months ago by mkoeppe

  • Description modified (diff)

comment:56 Changed 15 months ago by mkoeppe

  • Cc chapoton added

comment:57 Changed 15 months ago by mkoeppe

  • Description modified (diff)

comment:58 Changed 15 months ago by mkoeppe

  • Description modified (diff)

comment:59 Changed 15 months ago by mkoeppe

  • Cc fbissey added

comment:60 Changed 14 months ago by mkoeppe

  • Description modified (diff)

comment:61 Changed 14 months ago by mkoeppe

  • Cc Rudi added

comment:62 Changed 14 months ago by mkoeppe

  • 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 14 months ago by mkoeppe

  • Description modified (diff)

comment:64 Changed 14 months ago by mkoeppe

  • Description modified (diff)
  • Milestone changed from sage-7.2 to sage-7.3

comment:65 Changed 14 months ago by mkoeppe

  • Description modified (diff)

comment:66 Changed 14 months ago by mkoeppe

  • Description modified (diff)

comment:67 Changed 13 months ago by mkoeppe

  • Description modified (diff)

comment:68 Changed 13 months ago by mkoeppe

  • Description modified (diff)

comment:69 Changed 13 months ago by mkoeppe

  • Description modified (diff)

comment:70 Changed 13 months ago by mkoeppe

  • Description modified (diff)

comment:71 Changed 11 months ago by mkoeppe

  • Description modified (diff)
  • Milestone changed from sage-7.3 to sage-7.4

comment:72 Changed 11 months ago by mkoeppe

  • Description modified (diff)

comment:73 Changed 11 months ago by mkoeppe

  • Description modified (diff)

comment:74 Changed 10 months ago by dimpase

  • Description modified (diff)
  • Milestone changed from sage-7.4 to sage-7.5

comment:75 Changed 9 months ago by mkoeppe

  • Cc moritz jipilab mmasdeu added
  • Description modified (diff)

comment:76 Changed 6 months ago by dimpase

  • Description modified (diff)

comment:77 Changed 6 months ago by mkoeppe

  • Cc klee tmonteil added
  • Description modified (diff)
  • Milestone changed from sage-7.5 to sage-7.6

comment:78 Changed 6 months ago by klee

Perhaps I am not that klee that you think I am. My name is Kwankyu Lee.

comment:79 Changed 6 months ago by mkoeppe

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 6 months ago by klee

Ok :-)

comment:81 Changed 6 months ago by mkoeppe

  • Cc mforets added

comment:82 Changed 31 hours ago by vdelecroix

  • Cc ncohen removed
  • Description modified (diff)

comment:83 Changed 20 hours ago by jdemeyer

  • Description modified (diff)
Note: See TracTickets for help on using tickets.