Meta-ticket: Audit/fix all uses of MixedIntegerLinearProgram

[mkoeppe]

See

• #23798 comment:23
• #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, Gurobi: https://www.gurobi.com/documentation/9.1/refman/grb_tolerances_and_the_lim.html), 1e-6 (GLPK), ...

Tickets:

• MixedIntegerLinearProgram.get_values: Add options convert, tolerance. #32197 MixedIntegerLinearProgram.get_values: Add options convert, tolerance

• Fractional Chromatic Index test fails with GLPK #23798 Fractional Chromatic Index test fails with GLPK

• doctests failures in sage/graphs when using COIN solver #30635 doctests failures in sage/graphs when using COIN solver

• Bug in edge disjoint spanning trees #32169 Bug in edge disjoint spanning trees

• sage.combinat.designs: Use MixedIntegerLinearProgram.get_values options convert, tolerance #32218 sage.combinat.designs: Use MixedIntegerLinearProgram.get_values options convert, tolerance

• SimplicialComplex.is_partitionable, Link.plot: Fix use of MixedIntegerLinearProgram #32219 SimplicialComplex.is_partitionable: Fix use of MixedIntegerLinearProgram

• sage.sat, sage.numerical: Fix use of MixedIntegerLinearProgram #32220 sage.sat, sage.numerical: Fix use of MixedIntegerLinearProgram

• sage.combinat, .matroids, .geometry: Fix use of MixedIntegerLinearProgram #32221 sage.combinat, .matroids, .geometry: Fix use of MixedIntegerLinearProgram

• Fix use of MixedIntegerLinearProgram in vertex_separation #32222 Fix use of MixedIntegerLinearProgram in sage.graphs.graph_decompositions.vertex_separation

• Fix use of MixedIntegerLinearProgram in cutwidth #32223 Fix use of MixedIntegerLinearProgram in sage.graphs.graph_decompositions.cutwidth

• Fix use of MixedIntegerLinearProgram in sage.graphs.domination #32224 Fix use of MixedIntegerLinearProgram in sage.graphs.domination

• Fix use of MixedIntegerLinearProgram in sage.graphs.connectivity #32225 Fix use of MixedIntegerLinearProgram in sage.graphs.connectivity

• Fix use of MixedIntegerLinearProgram in sage.graphs.digraph #32236 Fix use of MixedIntegerLinearProgram in sage.graphs.digraph

• Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 1 #32237 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 1

• Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 2 #32238 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 2

• Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 3 #32239 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 3

• Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 4 #32240 Fix use of MixedIntegerLinearProgram in sage.graphs.graph - part 4

• Fix use of MixedIntegerLinearProgram in sage.graphs.graph _coloring #32241 Fix use of MixedIntegerLinearProgram in sage.graphs.graph_coloring (except Fractional Chromatic Index test fails with GLPK #23798)

• Fix use of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 1 #32246 Fix use of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 1

• Fix use of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 2 #32247 Fix use of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 2

• Fix use of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 3 #32248 Fix use of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 3

• Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.connectivity #32428 Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.connectivity

• Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.digraph #32535 Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.digraph

• Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.graph_coloring #32536 Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.graph_coloring

• Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.graph #32537 Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.graph

• Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 1 #32538 Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 1

• Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 2 #32539 Another fix in the usage of MixedIntegerLinearProgram in sage.graphs.generic_graph - part 2

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

Component: graph theory

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

[dcoudert]

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.