search

sagemath / sage

Main repository of SageMath. Now open for Issues and Pull Requests.
https://www.sagemath.org
Other
1.22k stars 424 forks source link

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

Open mkoeppe opened 8 years ago

mkoeppe commented 8 years ago

Alternatives:

Proposed packaging change:

Frontend defects:

Frontend improvements:

Backend defects:

Improvements to backends:

Improvements to the backend interface:

Improvements to underlying libraries:

New backends:

Interactions with InteractiveLinearProgram and its dictionaries:

Interactions with polyhedra:

Applications:

SDP, MINLP, Manifolds:

Documentation:

Depends on #20296

CC: @dimpase @videlec @vbraun @jdemeyer @fchapoton @kiwifb @sagetrac-Rudi @novoselt @mo271 @jplab @mmasdeu @kwankyu @sagetrac-tmonteil @mforets @yuan-zhou

Component: numerical

Issue created by migration from https://trac.sagemath.org/ticket/20302

mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,6 +1,6 @@
 While implementing `InteractiveLPBackend` for #20296, I noticed several deficiencies in the design of the MILP backend interface.

-- `add_col` and `add_variable` both add a variable to the problem; but `add_col` only allows to add a column with no name; whereas `add_variable` only allows to add a column with no coefficients. There should be one function (`add_variable`, probably) that can do both; should then deprecate `add_col`. (Also compare with `add_linear_constraint`, which takes as zipped index/coefficient list, whereas `add_col` takes two parallel lists.)
+- `add_col` and `add_variable` both add a variable to the problem; but `add_col` only allows to add a column with no name; whereas `add_variable` only allows to add a column with no coefficients. There should be one function (`add_variable`, probably - see #20296 for a possible interface) that can do both; should then deprecate `add_col`. (Also compare with `add_linear_constraint`, which takes a zipped index/coefficient list, whereas `add_col` takes two parallel lists.)

 - `variable_upper_bound`: This interface is bizarre.  Can't remove an upper bound from a variable because `None` means both 'no upper bound' and 'get the upper bound'. Likewise `variable_lower_bound`. (Moreover, there's redundancy with `col_bounds`.)
mkoeppe commented 8 years ago
comment:2

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

mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,8 +1,6 @@
 While implementing `InteractiveLPBackend` for #20296, I noticed several deficiencies in the design of the MILP backend interface.

 - `add_col` and `add_variable` both add a variable to the problem; but `add_col` only allows to add a column with no name; whereas `add_variable` only allows to add a column with no coefficients. There should be one function (`add_variable`, probably - see #20296 for a possible interface) that can do both; should then deprecate `add_col`. (Also compare with `add_linear_constraint`, which takes a zipped index/coefficient list, whereas `add_col` takes two parallel lists.)
-
-- `variable_upper_bound`: This interface is bizarre.  Can't remove an upper bound from a variable because `None` means both 'no upper bound' and 'get the upper bound'. Likewise `variable_lower_bound`. (Moreover, there's redundancy with `col_bounds`.)

 - `add_variables` and `add_linear_constraints` should have a default implementation in `GenericBackend`, like `add_linear_constraint_vector`.
mkoeppe commented 8 years ago

Dependencies: #20296

mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,6 +1,6 @@
 While implementing `InteractiveLPBackend` for #20296, I noticed several deficiencies in the design of the MILP backend interface.

-- `add_col` and `add_variable` both add a variable to the problem; but `add_col` only allows to add a column with no name; whereas `add_variable` only allows to add a column with no coefficients. There should be one function (`add_variable`, probably - see #20296 for a possible interface) that can do both; should then deprecate `add_col`. (Also compare with `add_linear_constraint`, which takes a zipped index/coefficient list, whereas `add_col` takes two parallel lists.)
+- `add_col` and `add_variable` both add a variable to the problem; but `add_col` only allows to add a column with no name; whereas `add_variable` only allows to add a column with no coefficients. There should be one function (`add_variable`, probably - see #20296 for a possible interface) that can do both; should then deprecate `add_col`. Note that `add_col` is not used by `MixedIntegerLinearProgram`; it is only used in doctests of the backends.  (Also compare with `add_linear_constraint`, which takes a zipped index/coefficient list, whereas `add_col` takes two parallel lists.)

 - `add_variables` and `add_linear_constraints` should have a default implementation in `GenericBackend`, like `add_linear_constraint_vector`.
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -4,5 +4,37 @@

 - `add_variables` and `add_linear_constraints` should have a default implementation in `GenericBackend`, like `add_linear_constraint_vector`.

+- The doctest of `add_linear_constraint_vector` from generic_backend.pyx (which is never run for any real backend!), when applied to COIN or GLPK leads to segfaults:
+
+```
+sage:             sage: coeffs = ([0, vector([1, 2])], [1, vector([2, 3])])
+sage:             sage: upper = vector([5, 5])
+sage:             sage: lower = vector([0, 0])
+sage:             sage: from sage.numerical.backends.generic_backend import get_solver
+sage:             sage: p = get_solver(solver = "Coin")                         # optional - cbc
+sage: p.add_linear_constraint_vector(2, coeffs, lower, upper, 'foo')
+------------------------------------------------------------------------
+0   signals.so                          0x0000000109df05c5 print_backtrace + 37
+------------------------------------------------------------------------
+Unhandled SIGSEGV: A segmentation fault occurred.
+This probably occurred because a *compiled* module has a bug
+in it and is not properly wrapped with sig_on(), sig_off().
+Python will now terminate.
+------------------------------------------------------------------------
+Segmentation fault: 11
+$ sage
+SageMath Version 7.2.beta0, Release Date: 2016-03-24 
+sage: sage:             sage: coeffs = ([0, vector([1, 2])], [1, vector([2, 3])])
+sage: sage:             sage: upper = vector([5, 5])
+sage: sage:             sage: lower = vector([0, 0])
+sage: sage:             sage: from sage.numerical.backends.generic_backend import get_solver
+sage: sage:             sage: p = get_solver(solver = "Coin")                         # optional - cbc
+sage: p.add_linear_constraint_vector(2, coeffs, lower, upper)
+------------------------------------------------------------------------
+0   signals.so                          0x0000000109c8a5c5 print_backtrace + 37
+------------------------------------------------------------------------
+Unhandled SIGSEGV: A segmentation fault occurred.
+```
+
 Also, I think the backends should be tested using a common `TestSuite`. Right now each backend uses its own doctests, which have slightly diverged from each other, so there is nothing (other than the fact that they were the result of copy-paste from each other) that ensures consistency. (#20296 fixes several wrong doctests in `GenericBackend`, from which I tried to copy-paste, for example.)
videlec commented 8 years ago
comment:7

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.

mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,27 @@
+Frontend:
+- #20304: More error checking in MixedIntegerLinearProgram
+
+Backends:
+- #20303: Fixes for add_variables in CVXOPT, PPL, GLPK MIP backends and add_linear_constraints in CVXOPT
+
+
+Interactions with InteractiveLinearProgram and its dictionaries:
+- #18734: Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram
+- #20311: interactive_simplex_method enhancements
+- #20296: MixedIntegerLinearProgram: New backend using InteractiveLPProblem
+- #18735: MixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution
+- #20203: LPCleanDictionary - floating-point helper class for interactive simplex method
+- #18804: LPBackendDictionary - a debugging view of a MIP backend connected to interactive_simplex_method
+
+Interactions with polyhedra:
+- #20301 Polyhedron.to_linear_program should return the MIP variable used
+
+* * * * 
+
+To be put on separate tickets:
+
+Clean up MILP backend interface:
+
 While implementing `InteractiveLPBackend` for #20296, I noticed several deficiencies in the design of the MILP backend interface.

 - `add_col` and `add_variable` both add a variable to the problem; but `add_col` only allows to add a column with no name; whereas `add_variable` only allows to add a column with no coefficients. There should be one function (`add_variable`, probably - see #20296 for a possible interface) that can do both; should then deprecate `add_col`. Note that `add_col` is not used by `MixedIntegerLinearProgram`; it is only used in doctests of the backends.  (Also compare with `add_linear_constraint`, which takes a zipped index/coefficient list, whereas `add_col` takes two parallel lists.)
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,20 +1,20 @@
 Frontend:
-- #20304: More error checking in MixedIntegerLinearProgram
+- #20304: More error checking in `MixedIntegerLinearProgram`

 Backends:
-- #20303: Fixes for add_variables in CVXOPT, PPL, GLPK MIP backends and add_linear_constraints in CVXOPT
+- #20303: Fixes for add_variables in CVXOPT, PPL, GLPK MIP backends and `add_linear_constraints` in CVXOPT

-Interactions with InteractiveLinearProgram and its dictionaries:
-- #18734: Construct an interactive_simplex_method.LPDictionary from a MixedIntegerLinearProgram
-- #20311: interactive_simplex_method enhancements
-- #20296: MixedIntegerLinearProgram: New backend using InteractiveLPProblem
-- #18735: MixedIntegerLinearProgram/HybridBackend: Reconstruct exact rational/algebraic basic solution
-- #20203: LPCleanDictionary - floating-point helper class for interactive simplex method
-- #18804: LPBackendDictionary - a debugging view of a MIP backend connected to interactive_simplex_method
+Interactions with `InteractiveLinearProgram` and its dictionaries:
+- #18734: Construct an `interactive_simplex_method.LPDictionary` from a `MixedIntegerLinearProgram`
+- #20311: `interactive_simplex_method` enhancements
+- #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
+- #18735: `MixedIntegerLinearProgram`/`HybridBackend`: Reconstruct exact rational/algebraic basic solution
+- #20203: `LPCleanDictionary` - floating-point helper class for interactive simplex method
+- #18804: `LPBackendDictionary` - a debugging view of a MIP backend connected to `interactive_simplex_method`

 Interactions with polyhedra:
-- #20301 Polyhedron.to_linear_program should return the MIP variable used
+- #20301 `Polyhedron.to_linear_program` should return the MIP variable used

 * * * *
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,9 +1,16 @@
 Frontend:
 - #20304: More error checking in `MixedIntegerLinearProgram`
+- #19523: defect: Adding constraints for the wrong MILP crashes Sage
+- #18733: enhancement: `MixedIntegerLinearProgram` should support tableau-query methods
+- #18688: task: `MixedIntegerLinearProgram` should support basis status getting/setting

 Backends:
-- #20303: Fixes for add_variables in CVXOPT, PPL, GLPK MIP backends and `add_linear_constraints` in CVXOPT
-
+- #20303: Fixes for `add_variables` in CVXOPT, PPL, GLPK MIP backends and `add_linear_constraints` in CVXOPT
+- #19525: enhancement: Improve GLPK error handling
+- #20323: Common `TestSuite` for MIP backends
+- #20324: MIP backends: Unify `add_col`, `add_variable`
+- #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
+- #20326: `GenericBackend`: Fix doctest of add_linear_constraint_vector

 Interactions with `InteractiveLinearProgram` and its dictionaries:
 - #18734: Construct an `interactive_simplex_method.LPDictionary` from a `MixedIntegerLinearProgram`
@@ -16,49 +23,4 @@
 Interactions with polyhedra:
 - #20301 `Polyhedron.to_linear_program` should return the MIP variable used

-* * * * 

-To be put on separate tickets:
-
-Clean up MILP backend interface:
-
-While implementing `InteractiveLPBackend` for #20296, I noticed several deficiencies in the design of the MILP backend interface.
-
-- `add_col` and `add_variable` both add a variable to the problem; but `add_col` only allows to add a column with no name; whereas `add_variable` only allows to add a column with no coefficients. There should be one function (`add_variable`, probably - see #20296 for a possible interface) that can do both; should then deprecate `add_col`. Note that `add_col` is not used by `MixedIntegerLinearProgram`; it is only used in doctests of the backends.  (Also compare with `add_linear_constraint`, which takes a zipped index/coefficient list, whereas `add_col` takes two parallel lists.)
-
-- `add_variables` and `add_linear_constraints` should have a default implementation in `GenericBackend`, like `add_linear_constraint_vector`.
-
-- The doctest of `add_linear_constraint_vector` from generic_backend.pyx (which is never run for any real backend!), when applied to COIN or GLPK leads to segfaults:
-
-```
-sage:             sage: coeffs = ([0, vector([1, 2])], [1, vector([2, 3])])
-sage:             sage: upper = vector([5, 5])
-sage:             sage: lower = vector([0, 0])
-sage:             sage: from sage.numerical.backends.generic_backend import get_solver
-sage:             sage: p = get_solver(solver = "Coin")                         # optional - cbc
-sage: p.add_linear_constraint_vector(2, coeffs, lower, upper, 'foo')
-------------------------------------------------------------------------
-0   signals.so                          0x0000000109df05c5 print_backtrace + 37
-------------------------------------------------------------------------
-Unhandled SIGSEGV: A segmentation fault occurred.
-This probably occurred because a *compiled* module has a bug
-in it and is not properly wrapped with sig_on(), sig_off().
-Python will now terminate.
-------------------------------------------------------------------------
-Segmentation fault: 11
-$ sage
-SageMath Version 7.2.beta0, Release Date: 2016-03-24 
-sage: sage:             sage: coeffs = ([0, vector([1, 2])], [1, vector([2, 3])])
-sage: sage:             sage: upper = vector([5, 5])
-sage: sage:             sage: lower = vector([0, 0])
-sage: sage:             sage: from sage.numerical.backends.generic_backend import get_solver
-sage: sage:             sage: p = get_solver(solver = "Coin")                         # optional - cbc
-sage: p.add_linear_constraint_vector(2, coeffs, lower, upper)
-------------------------------------------------------------------------
-0   signals.so                          0x0000000109c8a5c5 print_backtrace + 37
-------------------------------------------------------------------------
-Unhandled SIGSEGV: A segmentation fault occurred.
-```
-
-Also, I think the backends should be tested using a common `TestSuite`. Right now each backend uses its own doctests, which have slightly diverged from each other, so there is nothing (other than the fact that they were the result of copy-paste from each other) that ensures consistency. (#20296 fixes several wrong doctests in `GenericBackend`, from which I tried to copy-paste, for example.)
-
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -4,7 +4,7 @@
 - #18733: enhancement: `MixedIntegerLinearProgram` should support tableau-query methods
 - #18688: task: `MixedIntegerLinearProgram` should support basis status getting/setting

-Backends:
+Improvements to backends:
 - #20303: Fixes for `add_variables` in CVXOPT, PPL, GLPK MIP backends and `add_linear_constraints` in CVXOPT
 - #19525: enhancement: Improve GLPK error handling
 - #20323: Common `TestSuite` for MIP backends
@@ -12,11 +12,15 @@
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
 - #20326: `GenericBackend`: Fix doctest of add_linear_constraint_vector

+New backends:
+- #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
+- #18735: `MixedIntegerLinearProgram`/`HybridBackend`: Reconstruct exact rational/algebraic basic solution
+- #19219: MILP: Add CyLP backend
+- #18862: Interface to COIN OpenSolverInterface
+
 Interactions with `InteractiveLinearProgram` and its dictionaries:
 - #18734: Construct an `interactive_simplex_method.LPDictionary` from a `MixedIntegerLinearProgram`
 - #20311: `interactive_simplex_method` enhancements
-- #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
-- #18735: `MixedIntegerLinearProgram`/`HybridBackend`: Reconstruct exact rational/algebraic basic solution
 - #20203: `LPCleanDictionary` - floating-point helper class for interactive simplex method
 - #18804: `LPBackendDictionary` - a debugging view of a MIP backend connected to `interactive_simplex_method`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -15,8 +15,11 @@
 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
 - #18735: `MixedIntegerLinearProgram`/`HybridBackend`: Reconstruct exact rational/algebraic basic solution
-- #19219: MILP: Add CyLP backend
-- #18862: Interface to COIN OpenSolverInterface
+- #19219: MILP: Add "CyLP" backend
+- #18862: Interface to COIN `OpenSolverInterface`
+- #8672 SCIP support
+- #10879: add optional SCIP integer constraint solver
+- #18766: Add bindings, `MixedIntegerLinearProgram` backend to qsopt_ex, a state-of-the-art exact simplex solver

 Interactions with `InteractiveLinearProgram` and its dictionaries:
 - #18734: Construct an `interactive_simplex_method.LPDictionary` from a `MixedIntegerLinearProgram`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -11,6 +11,7 @@
 - #20324: MIP backends: Unify `add_col`, `add_variable`
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
 - #20326: `GenericBackend`: Fix doctest of add_linear_constraint_vector
+- #20328: tests related to cplex / gurobi

 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -12,6 +12,7 @@
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
 - #20326: `GenericBackend`: Fix doctest of add_linear_constraint_vector
 - #20328: tests related to cplex / gurobi
+- #10232: MIP backends should perform bounds checks

 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -3,6 +3,10 @@
 - #19523: defect: Adding constraints for the wrong MILP crashes Sage
 - #18733: enhancement: `MixedIntegerLinearProgram` should support tableau-query methods
 - #18688: task: `MixedIntegerLinearProgram` should support basis status getting/setting
+
+Wishlist tickets:
+- #7290: Dual method for linear programs
+- #15356: linear programming enhancements

 Improvements to backends:
 - #20303: Fixes for `add_variables` in CVXOPT, PPL, GLPK MIP backends and `add_linear_constraints` in CVXOPT
@@ -19,8 +23,7 @@
 - #18735: `MixedIntegerLinearProgram`/`HybridBackend`: Reconstruct exact rational/algebraic basic solution
 - #19219: MILP: Add "CyLP" backend
 - #18862: Interface to COIN `OpenSolverInterface`
-- #8672 SCIP support
-- #10879: add optional SCIP integer constraint solver
+- #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

 Interactions with `InteractiveLinearProgram` and its dictionaries:
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,6 +1,7 @@
 Frontend:
 - #20304: More error checking in `MixedIntegerLinearProgram`
 - #19523: defect: Adding constraints for the wrong MILP crashes Sage
+- #20331: MIPVariable misreports its dimension (always 1)
 - #18733: enhancement: `MixedIntegerLinearProgram` should support tableau-query methods
 - #18688: task: `MixedIntegerLinearProgram` should support basis status getting/setting
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -12,6 +12,7 @@
 Improvements to backends:
 - #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`
 - #20323: Common `TestSuite` for MIP backends
 - #20324: MIP backends: Unify `add_col`, `add_variable`
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -13,6 +13,7 @@
 - #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`
+- #20337: `MIP backends: obj_constant_term` should be exposed by a backend method
 - #20323: Common `TestSuite` for MIP backends
 - #20324: MIP backends: Unify `add_col`, `add_variable`
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -13,7 +13,7 @@
 - #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`
-- #20337: `MIP backends: obj_constant_term` should be exposed by a backend method
+- #20337: MIP backends: `obj_constant_term` should be exposed by a backend method
 - #20323: Common `TestSuite` for MIP backends
 - #20324: MIP backends: Unify `add_col`, `add_variable`
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -13,7 +13,7 @@
 - #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`
-- #20337: MIP backends: `obj_constant_term` should be exposed by a backend method
+- #20337: MIP: Several fixes regarding constant terms in the objective function
 - #20323: Common `TestSuite` for MIP backends
 - #20324: MIP backends: Unify `add_col`, `add_variable`
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,7 +1,7 @@
 Frontend:
 - #20304: More error checking in `MixedIntegerLinearProgram`
 - #19523: defect: Adding constraints for the wrong MILP crashes Sage
-- #20331: MIPVariable misreports its dimension (always 1)
+- #20331: A `MIPVariable`'s repr should include some useful information
 - #18733: enhancement: `MixedIntegerLinearProgram` should support tableau-query methods
 - #18688: task: `MixedIntegerLinearProgram` should support basis status getting/setting
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -20,6 +20,7 @@
 - #20326: `GenericBackend`: Fix doctest of add_linear_constraint_vector
 - #20328: tests related to cplex / gurobi
 - #10232: MIP backends should perform bounds checks
+- #20351: `sage.libs.ppl.MIP_Problem` and `PPLBackend`: Add support for integer variables

 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -19,7 +19,7 @@
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
 - #20326: `GenericBackend`: Fix doctest of add_linear_constraint_vector
 - #20328: tests related to cplex / gurobi
-- #10232: MIP backends should perform bounds checks
+- #10232: check GLPK bound errors
 - #20351: `sage.libs.ppl.MIP_Problem` and `PPLBackend`: Add support for integer variables

 New backends:
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,18 +1,25 @@
-Frontend:
+Frontend defects:
 - #20304: More error checking in `MixedIntegerLinearProgram`
 - #19523: defect: Adding constraints for the wrong MILP crashes Sage
+- #13696: process chained equalities with different signs correctly
+- #14540: MILP constraints are silently misunderstood
+- #15159: Segfault after deepcopy of MixedIntegerLinearProgram
+
+Frontend wishlist tickets:
 - #20331: A `MIPVariable`'s repr should include some useful information
-- #18733: enhancement: `MixedIntegerLinearProgram` should support tableau-query methods
-- #18688: task: `MixedIntegerLinearProgram` should support basis status getting/setting
-
-Wishlist tickets:
-- #7290: Dual method for linear programs
+- #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:
 - #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`
+- #18572: CVXOPT solver equations handling
 - #20337: MIP: Several fixes regarding constant terms in the objective function
 - #20323: Common `TestSuite` for MIP backends
 - #20324: MIP backends: Unify `add_col`, `add_variable`
@@ -21,6 +28,9 @@
 - #20328: tests related to cplex / gurobi
 - #10232: check GLPK bound errors
 - #20351: `sage.libs.ppl.MIP_Problem` and `PPLBackend`: Add support for integer variables
+
+Improvements to underlying libraries:
+- #19903 crash with MIP_Problem

 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -3,7 +3,7 @@
 - #19523: defect: Adding constraints for the wrong MILP crashes Sage
 - #13696: process chained equalities with different signs correctly
 - #14540: MILP constraints are silently misunderstood
-- #15159: Segfault after deepcopy of MixedIntegerLinearProgram
+- #15159: Segfault after deepcopy of `MixedIntegerLinearProgram`

 Frontend wishlist tickets:
 - #20331: A `MIPVariable`'s repr should include some useful information
@@ -13,7 +13,7 @@
 - #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
+- #15583: `sage.numerical.linear_functions.LinearConstraint` is not a hashable type

 Improvements to backends:
 - #20303: Fixes for `add_variables` in CVXOPT, PPL, GLPK MIP backends and `add_linear_constraints` in CVXOPT
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -24,13 +24,14 @@
 - #20323: Common `TestSuite` for MIP backends
 - #20324: MIP backends: Unify `add_col`, `add_variable`
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
-- #20326: `GenericBackend`: Fix doctest of add_linear_constraint_vector
+- #20326: `GenericBackend`: Fix doctest of `add_linear_constraint_vector`
 - #20328: tests related to cplex / gurobi
 - #10232: check GLPK bound errors
-- #20351: `sage.libs.ppl.MIP_Problem` and `PPLBackend`: Add support for integer variables
+- #20354: `PPLBackend`: Add support for integer variables

 Improvements to underlying libraries:
-- #19903 crash with MIP_Problem
+- #19903 crash with `MIP_Problem`
+- #20351: `sage.libs.ppl.MIP_Problem`: Add support for integer variables

 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -28,6 +28,7 @@
 - #20328: tests related to cplex / gurobi
 - #10232: check GLPK bound errors
 - #20354: `PPLBackend`: Add support for integer variables
+- #20360: Add `sig_on`/`sig_off` to COINBackend

 Improvements to underlying libraries:
 - #19903 crash with `MIP_Problem`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -29,6 +29,7 @@
 - #10232: check GLPK bound errors
 - #20354: `PPLBackend`: Add support for integer variables
 - #20360: Add `sig_on`/`sig_off` to COINBackend
+- #20361: PPL backend re-solves the problem every time `get_variable_value` or `get_objective_value` is called

 Improvements to underlying libraries:
 - #19903 crash with `MIP_Problem`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -20,9 +20,7 @@
 - #19525: enhancement: Improve GLPK error handling
 - #20332: `CVXOPTBackend`: Set initial `problem_name`
 - #18572: CVXOPT solver equations handling
-- #20337: MIP: Several fixes regarding constant terms in the objective function
 - #20323: Common `TestSuite` for MIP backends
-- #20324: MIP backends: Unify `add_col`, `add_variable`
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
 - #20326: `GenericBackend`: Fix doctest of `add_linear_constraint_vector`
 - #20328: tests related to cplex / gurobi
@@ -30,6 +28,11 @@
 - #20354: `PPLBackend`: Add support for integer variables
 - #20360: Add `sig_on`/`sig_off` to COINBackend
 - #20361: PPL backend re-solves the problem every time `get_variable_value` or `get_objective_value` is called
+
+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`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,11 +1,11 @@
 Frontend defects:
 - #20304: More error checking in `MixedIntegerLinearProgram`
-- #19523: defect: Adding constraints for the wrong MILP crashes Sage
 - #13696: process chained equalities with different signs correctly
 - #14540: MILP constraints are silently misunderstood
 - #15159: Segfault after deepcopy of `MixedIntegerLinearProgram`

 Frontend wishlist tickets:
+- #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
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -16,6 +16,13 @@
 - #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`
@@ -45,14 +52,21 @@
 - #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)

 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` - 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

+Applications:
+- #20367: fix integer option and a bug in Delsarte bounds code
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -47,6 +47,7 @@

 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
+- #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`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -5,6 +5,7 @@
 - #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 tableau-query methods
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -48,6 +48,7 @@

 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
+- #20413: InteractiveLPProblem: Use standard-form 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
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -27,15 +27,16 @@
 - #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
 - #18572: CVXOPT solver equations handling
 - #20323: Common `TestSuite` for MIP backends
 - #20325: `GenericBackend`: Add default implementation of `add_variables` and `add_linear_constraints`
-- #20326: `GenericBackend`: Fix doctest of `add_linear_constraint_vector`
 - #20328: tests related to cplex / gurobi
-- #10232: check GLPK bound errors
-- #20354: `PPLBackend`: Add support for integer variables
 - #20360: Add `sig_on`/`sig_off` to COINBackend
-- #20361: PPL backend re-solves the problem every time `get_variable_value` or `get_objective_value` is called

 Improvements to the backend interface:
 - #20337: MIP: Several fixes regarding constant terms in the objective function
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -70,6 +70,7 @@

 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
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -41,7 +41,7 @@
 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)
+- #20362: MIP backends: Make variable type consistent between `add_variable`, `set_variable_type` (with deprecation)

 Improvements to underlying libraries:
 - #19903 crash with `MIP_Problem`
@@ -50,7 +50,7 @@
 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
 - #20413: InteractiveLPProblem: Use standard-form transformation, objective_constant_term
-- #20376: LoggingBackend - delegating MIP backend class that logs input/output to backend methods
+- #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`
@@ -74,4 +74,4 @@

 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
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -46,6 +46,7 @@
 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`
@@ -57,6 +58,7 @@
 - #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
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -34,6 +34,7 @@
 - #20414: Add `copy`/`__copy__` methods to CVXOPT, PPL, InteractiveLP backends
 - #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
 - #20360: Add `sig_on`/`sig_off` to COINBackend
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -51,7 +51,7 @@

 New backends:
 - #20296: `MixedIntegerLinearProgram`: New backend using `InteractiveLPProblem`
-- #20413: InteractiveLPProblem: Use standard-form transformation, objective_constant_term
+- #20413: `InteractiveLPBackend`: Use standard-form transformation, `objective_constant_term`, change default `base_ring` to `QQ`
 - #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
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -52,6 +52,7 @@
 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
 - #18735: `MixedIntegerLinearProgram`/`HybridBackend`: Reconstruct exact rational/algebraic basic solution
 - #19219: MILP: Add "CyLP" backend
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -54,6 +54,7 @@
 - #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`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -80,3 +80,4 @@
 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
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -38,6 +38,7 @@
 - #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
+- #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
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,6 @@
 Frontend defects:
 - #20304: More error checking in `MixedIntegerLinearProgram`
+- #20461: Fixes for copying a MIP and its variables
 - #13696: process chained equalities with different signs correctly
 - #14540: MILP constraints are silently misunderstood
 - #15159: Segfault after deepcopy of `MixedIntegerLinearProgram`
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,6 @@
 Frontend defects:
 - #20304: More error checking in `MixedIntegerLinearProgram`
+- #20462: `MixedIntegerLinearProgram`/`MIPVariable`: `get_min`, `set_min`, `get_max`, `set_max` are broken
 - #20461: Fixes for copying a MIP and its variables
 - #13696: process chained equalities with different signs correctly
 - #14540: MILP constraints are silently misunderstood
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -72,6 +72,7 @@
 - #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`
@@ -84,3 +85,6 @@
 - #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)
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -34,11 +34,13 @@
 - #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"
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,6 +1,7 @@
 Frontend defects:
 - #20304: More error checking in `MixedIntegerLinearProgram`
 - #20462: `MixedIntegerLinearProgram`/`MIPVariable`: `get_min`, `set_min`, `get_max`, `set_max` are broken
+- #20602: `MixedIntegerLinearProgram.gen()` does not do anything useful
 - #20461: Fixes for copying a MIP and its variables
 - #13696: process chained equalities with different signs correctly
 - #14540: MILP constraints are silently misunderstood
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -3,6 +3,7 @@
 - #20462: `MixedIntegerLinearProgram`/`MIPVariable`: `get_min`, `set_min`, `get_max`, `set_max` are broken
 - #20602: `MixedIntegerLinearProgram.gen()` does not do anything useful
 - #20461: Fixes for copying a MIP and its variables
+- #20656: `MixedIntegerLinearProgram`: Remove `_variables` dictionary
 - #13696: process chained equalities with different signs correctly
 - #14540: MILP constraints are silently misunderstood
 - #15159: Segfault after deepcopy of `MixedIntegerLinearProgram`