Plot knots, build knots documentation when CPLEX is installed - Githubissues

sagemath / sage

Main repository of SageMath

https://www.sagemath.org

Other

1.48k stars 488 forks source link

Plot knots, build knots documentation when CPLEX is installed #20315

Closed jhpalmieri closed 8 years ago

jhpalmieri commented 8 years ago

The presence of the solver CPLEX breaks plotting of knots and links: see sage-devel.

Minimal example

sage: L = Link([[2,1,4,5], [5,6,7,3], [6,4,1,9], [9,2,3,7]])
sage: L.plot()
Traceback (most recent call last):
...
MIPSolverException: 'CPLEX: The primal has no feasible solution'

The reason is that the code in Link.plot assumes that the optimization is over integer valued variables which is not the case by default.

We also simplify and optimize the usage of the MILP solver.

CC: @videlec

Component: algebraic topology

Author: Vincent Delecroix

Branch: 7b79579

Reviewer: Miguel Marco

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

jhpalmieri commented 8 years ago

Branch: u/jhpalmieri/knot-pix

jhpalmieri commented 8 years ago

Author: John Palmieri

jhpalmieri commented 8 years ago

New commits:

503211d Knot plotting: use MIP solver 'GLPK' always.

jhpalmieri commented 8 years ago

Commit: 503211d

videlec commented 8 years ago

Description changed:

--- 
+++ 
@@ -1 +1,22 @@
 The presence of the solver `CPLEX` breaks plotting of knots and links: see [sage-devel](https://groups.google.com/d/msg/sage-devel/ryq2Pmn_lRY/a3twFJNUDwAJ).
+
+Minimal example
+
+```
+sage: L = Link([[2,1,4,5], [5,6,7,3], [6,4,1,9], [9,2,3,7]])
+sage: L.plot()
+Traceback (most recent call last):
+...
+MIPSolverException: 'CPLEX: The primal has no feasible solution' 
+```
+the corresponding LP problem is
+
+```
+Maximization:
+  - x_0 - x_1 - x_2 - x_3 - x_4 - x_5 - x_6 - x_7 - x_8 - x_9 - x_10 - x_11
+Constraints:
+  2.0 <= x_2 - x_3 - x_8 + x_9 <= 2.0
+  2.0 <= - x_0 + x_1 + x_6 - x_7 <= 2.0
+  2.0 <= - x_4 + x_5 + x_10 - x_11 <= 2.0
+  1.0 <= x_0 - x_1 + x_4 - x_5 + x_8 - x_9 <= 1.0
+```

videlec commented 8 years ago

comment:4

Would be better to investigate the issue...

videlec commented 8 years ago

Description changed:

--- 
+++ 
@@ -12,11 +12,20 @@
 the corresponding LP problem is

-Maximization:

- x_0 - x_1 - x_2 - x_3 - x_4 - x_5 - x_6 - x_7 - x_8 - x_9 - x_10 - x_11
- x_0 - x_1 - x_2 - x_3 - x_4 - x_5 - x_6 - x_7 - x_8 - x_9 - x_10 - x_11 - x_12 - x_13 - x_14 - x_15 - x_16 - x_17 - x_18 - x_19 Constraints:
2.0 <= x_2 - x_3 - x_8 + x_9 <= 2.0
2.0 <= - x_0 + x_1 + x_6 - x_7 <= 2.0
2.0 <= - x_4 + x_5 + x_10 - x_11 <= 2.0
1.0 <= x_0 - x_1 + x_4 - x_5 + x_8 - x_9 <= 1.0
0.0 <= x_0 - x_4 <= 0.0
0.0 <= x_1 - x_5 <= 0.0
0.0 <= - x_10 + x_12 <= 0.0
0.0 <= - x_3 + x_11 <= 0.0
0.0 <= - x_2 + x_3 <= 0.0
0.0 <= x_6 <= 0.0
0.0 <= x_2 - x_14 <= 0.0
0.0 <= x_1 - x_15 + x_16 <= 0.0
0.0 <= x_0 - x_17 <= 0.0
0.0 <= x_13 - x_16 <= 0.0
0.0 <= x_7 - x_9 <= 0.0
0.0 <= - x_5 + x_8 - x_18 <= 0.0
0.0 <= x_6 - x_18 <= 0.0
0.0 <= - x_4 + x_19 <= 0.0

videlec commented 8 years ago

comment:6

Indeed, the polyhedron of constraints is empty!

videlec commented 8 years ago

Description changed:

--- 
+++ 
@@ -12,20 +12,20 @@
 the corresponding LP problem is

- x_0 - x_1 - x_2 - x_3 - x_4 - x_5 - x_6 - x_7 - x_8 - x_9 - x_10 - x_11 - x_12 - x_13 - x_14 - x_15 - x_16 - x_17 - x_18 - x_19 Constraints:
0.0 <= x_0 - x_4 <= 0.0
0.0 <= x_1 - x_5 <= 0.0
0.0 <= - x_10 + x_12 <= 0.0
0.0 <= - x_3 + x_11 <= 0.0
0.0 <= - x_2 + x_3 <= 0.0
0.0 <= x_6 <= 0.0
0.0 <= x_2 - x_14 <= 0.0
0.0 <= x_1 - x_15 + x_16 <= 0.0
0.0 <= x_0 - x_17 <= 0.0
0.0 <= x_13 - x_16 <= 0.0
0.0 <= x_7 - x_9 <= 0.0
0.0 <= - x_5 + x_8 - x_18 <= 0.0
0.0 <= x_6 - x_18 <= 0.0
0.0 <= - x_4 + x_19 <= 0.0
1 <= x_i <= infinity (for i = 0,...,19)
x_0 - x_4 = 0
x_1 - x_5 = 0
- x_10 + x_12 = 0
- x_3 + x_11 = 0
- x_2 + x_3 = 0
x_6 = 0
x_2 - x_14 = 0
x_1 - x_15 + x_16 = 0
x_0 - x_17 = 0
x_13 - x_16 = 0
x_7 - x_9 = 0
- x_5 + x_8 - x_18 = 0
x_6 - x_18 = 0
- x_4 + x_19 = 0

videlec commented 8 years ago

Changed branch from u/jhpalmieri/knot-pix to u/vdelecroix/20315

videlec commented 8 years ago

Changed commit from 503211d to 7b79579

videlec commented 8 years ago

Changed author from John Palmieri to Vincent Delecroix

videlec commented 8 years ago

comment:8

Now the code works with any solver... Curiously, the number of primitive in the graphics depends on the solution of the first optimization. Which also implies that the pictures in the documentation will depend on the MILP solver ;-)

New commits:

7b79579 Trac 20315: fix MILP usage in Link.plot

videlec commented 8 years ago

Description changed:

--- 
+++ 
@@ -9,23 +9,6 @@
 ...
 MIPSolverException: 'CPLEX: The primal has no feasible solution'

-the corresponding LP problem is +The reason is that the code in Link.plot assumes that the optimization is over integer valued variables which is not the case by default.

-``` -Constraints:

1 <= x_i <= infinity (for i = 0,...,19)
x_0 - x_4 = 0
x_1 - x_5 = 0
- x_10 + x_12 = 0
- x_3 + x_11 = 0
- x_2 + x_3 = 0
x_6 = 0
x_2 - x_14 = 0
x_1 - x_15 + x_16 = 0
x_0 - x_17 = 0
x_13 - x_16 = 0
x_7 - x_9 = 0
- x_5 + x_8 - x_18 = 0
x_6 - x_18 = 0
- x_4 + x_19 = 0 -``` +We also simplify and optimize the usage of the MILP solver.

videlec commented 8 years ago

comment:10

Just want to confirm that I was able to build the documentation with CPLEX backend!

miguelmarco commented 8 years ago

Reviewer: Miguel Marco.

miguelmarco commented 8 years ago

comment:11

Thanks for the fix. It looks good to me (and a bit more elegant too). Testing it now.

vbraun commented 8 years ago

Changed branch from u/vdelecroix/20315 to 7b79579

jdemeyer commented 8 years ago

Changed commit from 7b79579 to none

jdemeyer commented 8 years ago

Changed reviewer from Miguel Marco. to Miguel Marco