search

sagemath / sage

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

Meta-ticket: Audit/fix all uses of MixedIntegerLinearProgram #32191

Open mkoeppe opened 2 years ago

mkoeppe commented 2 years ago

See

One class of bugs comes from using the raw solution values for integer or binary variables from numerical solvers. Using #32197, they can be converted to integers/booleans with integrality tolerance checking. The tolerance parameter depends on the model and the solver, but a rough guideline is that it should be greater than solvers' default integrality tolerances: 1e-5 (CPLEX: https://www.ibm.com/docs/en/icos/12.8.0.0?topic=parameters-integrality-tolerance, Gurobi: https://www.gurobi.com/documentation/9.1/refman/grb_tolerances_and_the_lim.html), 1e-6 (GLPK), ...

Tickets:

CC: @dcoudert @tscrim @seblabbe @dimpase @DaveWitteMorris

Component: graph theory

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

mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,8 @@
 See
 - [#23798 comment:23](https://github.com/sagemath/sage/issues/23798#comment:23)
 - [#30635 comment:20](https://github.com/sagemath/sage/issues/30635#comment:20)
+
+Tickets:
+- #23798 Fractional Chromatic Index test fails with GLPK
+- #32197 `MixedIntegerLinearProgram`: fix tests of binary variables in sage.graphs
+
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -3,6 +3,7 @@
 - [#30635 comment:20](https://github.com/sagemath/sage/issues/30635#comment:20)

 Tickets:
+- #32197 `MixedIntegerLinearProgram.get_values`: Add options `convert`, `tolerance`
 - #23798 Fractional Chromatic Index test fails with GLPK
-- #32197 `MixedIntegerLinearProgram`: fix tests of binary variables in sage.graphs
+- #32169 Bug in edge disjoint spanning trees
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -1,6 +1,8 @@
 See
 - [#23798 comment:23](https://github.com/sagemath/sage/issues/23798#comment:23)
 - [#30635 comment:20](https://github.com/sagemath/sage/issues/30635#comment:20)
+
+One class of bugs comes from using the raw solution values for integer or binary variables from numerical solvers. Using #32197, they can be converted to integers/booleans with integrality tolerance checking. The `tolerance` parameter depends on the model and the solver, but a rough guideline is that it should be greater than solvers' default integrality tolerances:  1e-5 (CPLEX: https://www.ibm.com/docs/en/icos/12.8.0.0?topic=parameters-integrality-tolerance), 1e-6 (GLPK), ...

 Tickets:
 - #32197 `MixedIntegerLinearProgram.get_values`: Add options `convert`, `tolerance`
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -2,7 +2,7 @@
 - [#23798 comment:23](https://github.com/sagemath/sage/issues/23798#comment:23)
 - [#30635 comment:20](https://github.com/sagemath/sage/issues/30635#comment:20)

-One class of bugs comes from using the raw solution values for integer or binary variables from numerical solvers. Using #32197, they can be converted to integers/booleans with integrality tolerance checking. The `tolerance` parameter depends on the model and the solver, but a rough guideline is that it should be greater than solvers' default integrality tolerances:  1e-5 (CPLEX: https://www.ibm.com/docs/en/icos/12.8.0.0?topic=parameters-integrality-tolerance), 1e-6 (GLPK), ...
+One class of bugs comes from using the raw solution values for integer or binary variables from numerical solvers. Using #32197, they can be converted to integers/booleans with integrality tolerance checking. The `tolerance` parameter depends on the model and the solver, but a rough guideline is that it should be greater than solvers' default integrality tolerances:  1e-5 (CPLEX: https://www.ibm.com/docs/en/icos/12.8.0.0?topic=parameters-integrality-tolerance, Gurobi: https://www.gurobi.com/documentation/9.1/refman/grb_tolerances_and_the_lim.html), 1e-6 (GLPK), ...

 Tickets:
 - #32197 `MixedIntegerLinearProgram.get_values`: Add options `convert`, `tolerance`
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -8,4 +8,4 @@
 - #32197 `MixedIntegerLinearProgram.get_values`: Add options `convert`, `tolerance`
 - #23798 Fractional Chromatic Index test fails with GLPK
 - #32169 Bug in edge disjoint spanning trees
-
+- #32218 `sage.combinat.designs`: Use `MixedIntegerLinearProgram.get_values` options `convert`, `tolerance`
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -9,3 +9,4 @@
 - #23798 Fractional Chromatic Index test fails with GLPK
 - #32169 Bug in edge disjoint spanning trees
 - #32218 `sage.combinat.designs`: Use `MixedIntegerLinearProgram.get_values` options `convert`, `tolerance`
+- #32219 `SimplicialComplex.is_partitionable`: Fix use of `MixedIntegerLinearProgram`
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -10,3 +10,4 @@
 - #32169 Bug in edge disjoint spanning trees
 - #32218 `sage.combinat.designs`: Use `MixedIntegerLinearProgram.get_values` options `convert`, `tolerance`
 - #32219 `SimplicialComplex.is_partitionable`: Fix use of `MixedIntegerLinearProgram`
+- #32220 `sage.sat`, `sage.numerical`: Fix use of `MixedIntegerLinearProgram`
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -11,3 +11,4 @@
 - #32218 `sage.combinat.designs`: Use `MixedIntegerLinearProgram.get_values` options `convert`, `tolerance`
 - #32219 `SimplicialComplex.is_partitionable`: Fix use of `MixedIntegerLinearProgram`
 - #32220 `sage.sat`, `sage.numerical`: Fix use of `MixedIntegerLinearProgram`
+- #32221 `sage.combinat`, `.matroids`, `.geometry`: Fix use of `MixedIntegerLinearProgram`
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -12,3 +12,5 @@
 - #32219 `SimplicialComplex.is_partitionable`: Fix use of `MixedIntegerLinearProgram`
 - #32220 `sage.sat`, `sage.numerical`: Fix use of `MixedIntegerLinearProgram`
 - #32221 `sage.combinat`, `.matroids`, `.geometry`: Fix use of `MixedIntegerLinearProgram`
+- #32222 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.vertex_separation.pyx`
+
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -13,4 +13,13 @@
 - #32220 `sage.sat`, `sage.numerical`: Fix use of `MixedIntegerLinearProgram`
 - #32221 `sage.combinat`, `.matroids`, `.geometry`: Fix use of `MixedIntegerLinearProgram`
 - #32222 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.vertex_separation.pyx`
+- #32223 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.cutwidth.pyx`

+To do in `sage.graphs`:
+- `connectivity.pyx`
+- `digraph.py`
+- `domination.py`
+- `generic_graph.py`
+- `graph.py`
+- `graph_coloring.pyx`
+
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -14,11 +14,11 @@
 - #32221 `sage.combinat`, `.matroids`, `.geometry`: Fix use of `MixedIntegerLinearProgram`
 - #32222 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.vertex_separation.pyx`
 - #32223 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.cutwidth.pyx`
+- #32224 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.domination.py`

 To do in `sage.graphs`:
 - `connectivity.pyx`
 - `digraph.py`
-- `domination.py`
 - `generic_graph.py`
 - `graph.py`
 - `graph_coloring.pyx`
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -12,14 +12,14 @@
 - #32219 `SimplicialComplex.is_partitionable`: Fix use of `MixedIntegerLinearProgram`
 - #32220 `sage.sat`, `sage.numerical`: Fix use of `MixedIntegerLinearProgram`
 - #32221 `sage.combinat`, `.matroids`, `.geometry`: Fix use of `MixedIntegerLinearProgram`
-- #32222 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.vertex_separation.pyx`
-- #32223 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.cutwidth.pyx`
-- #32224 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.domination.py`
+- #32222 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.vertex_separation`
+- #32223 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.cutwidth`
+- #32224 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.domination`
+- #32225 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.connectivity`

 To do in `sage.graphs`:
-- `connectivity.pyx`
 - `digraph.py`
 - `generic_graph.py`
 - `graph.py`
-- `graph_coloring.pyx`
+- `graph_coloring.pyx` (part in #23798)
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -16,6 +16,8 @@
 - #32223 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_decompositions.cutwidth`
 - #32224 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.domination`
 - #32225 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.connectivity`
+- #32236 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.digraph`
+

 To do in `sage.graphs`:
 - `digraph.py`
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -17,10 +17,11 @@
 - #32224 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.domination`
 - #32225 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.connectivity`
 - #32236 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.digraph`
+- #32237 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 1
+- #32238 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 2

 To do in `sage.graphs`:
-- `digraph.py`
 - `generic_graph.py`
 - `graph.py`
 - `graph_coloring.pyx` (part in #23798)
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -19,6 +19,7 @@
 - #32236 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.digraph`
 - #32237 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 1
 - #32238 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 2
+- #32239 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 3

 To do in `sage.graphs`:
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -20,10 +20,10 @@
 - #32237 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 1
 - #32238 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 2
 - #32239 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 3
+- #32240 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 4
+- #32241 Fix use of MixedIntegerLinearProgram in sage.graphs.graph_coloring (except #23798)

 To do in `sage.graphs`:
 - `generic_graph.py`
-- `graph.py`
-- `graph_coloring.pyx` (part in #23798)
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -17,11 +17,14 @@
 - #32224 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.domination`
 - #32225 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.connectivity`
 - #32236 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.digraph`
-- #32237 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 1
-- #32238 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 2
-- #32239 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 3
-- #32240 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 4
-- #32241 Fix use of MixedIntegerLinearProgram in sage.graphs.graph_coloring (except #23798)
+- #32237 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph` - part 1
+- #32238 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph` - part 2
+- #32239 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph` - part 3
+- #32240 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph` - part 4
+- #32241 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.graph_coloring` (except #23798)
+- #32246 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.generic_graph` - part 1
+- #32247 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.generic_graph` - part 2
+- #32248 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.generic_graph` - part 3

 To do in `sage.graphs`:
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -7,6 +7,7 @@
 Tickets:
 - #32197 `MixedIntegerLinearProgram.get_values`: Add options `convert`, `tolerance`
 - #23798 Fractional Chromatic Index test fails with GLPK
+- #30635 doctests failures in sage/graphs when using `COIN` solver
 - #32169 Bug in edge disjoint spanning trees
 - #32218 `sage.combinat.designs`: Use `MixedIntegerLinearProgram.get_values` options `convert`, `tolerance`
 - #32219 `SimplicialComplex.is_partitionable`: Fix use of `MixedIntegerLinearProgram`
@@ -27,6 +28,3 @@
 - #32248 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.generic_graph` - part 3

-To do in `sage.graphs`:
-- `generic_graph.py`
-
dcoudert commented 2 years ago
comment:21

Using our new way of converting variables, we can avoid some conversions of the objective values (using Integer(round(...))). See #32428 for a first attempt.

dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -27,4 +27,5 @@
 - #32247 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.generic_graph` - part 2
 - #32248 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.generic_graph` - part 3

+- #32428 Another fix in the usage of `MixedIntegerLinearProgram` in `sage.graphs.connectivity`
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -28,4 +28,9 @@
 - #32248 Fix use of `MixedIntegerLinearProgram` in `sage.graphs.generic_graph` - part 3

 - #32428 Another fix in the usage of `MixedIntegerLinearProgram` in `sage.graphs.connectivity`
+- #32535  Another fix in the usage of `MixedIntegerLinearProgram` in `sage.graphs.digraph`
+- #32536  Another fix in the usage of `MixedIntegerLinearProgram` in `sage.graphs.graph_coloring`
+- #32537  Another fix in the usage of `MixedIntegerLinearProgram` in `sage.graphs.graph` 
+- #32538  Another fix in the usage of `MixedIntegerLinearProgram` in `sage.graphs.generic_graph`  - part 1 
+- #32539  Another fix in the usage of `MixedIntegerLinearProgram` in `sage.graphs.generic_graph`  - part 2