#20302: Meta-ticket: Improvements to MixedIntegerLinearProgram, its backends,
and
InteractiveLinearProgram
-----------------------------+------------------------
Reporter: mkoeppe | Owner:
Type: task | Status: new
Priority: major | Milestone: sage-7.3
Component: numerical | Resolution:
Keywords: lp | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #20296 | Stopgaps:
-----------------------------+------------------------
Description changed by mkoeppe:
Old description:
> 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 `MIPVariable`s 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
>
> 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
> - #20876: GLPK: glp_exact ignores verbosity level
>
> 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)
> - #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
>
> 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)
New description:
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 `MIPVariable`s 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
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
- #20876: GLPK: glp_exact ignores verbosity level
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)
- #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)
--
--
Ticket URL: <https://trac.sagemath.org/ticket/20302#comment:68>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
