Create a linear programming backend for cvxopt

[ingolfured]

CVXOPT gets a "regular" (MI)LP backend for its LP solver functionality; i.e. specifying solver="cvxopt" should turn this solver on. This gives Sage an OSS LP solver which uses an interior point method to solve LPs.

CC: @dimpase @nathanncohen

Component: linear programming

Author: Ingólfur Eðvarðsson

Branch: 6e95304

Reviewer: Dima Pasechnik

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

[ingolfured]

Branch: u/ingolfured/create_a_linear_programming_backend_for_cvxopt

[dimpase]

Commit: aefac98

[dimpase]

comment:4

Replying to @ingolfured:
this didn't seem to create anything on the trac git repo...

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

aef3b0b

added the missing cvxopt backend files

[sagetrac-git]

Changed commit from aefac98 to aef3b0b

[dimpase]

comment:6

you should add the remaining stuff too, there are more files, as you know:

$ git diff 2b1d88becbc8cb30962e0995cc78e429e0f5589f | grep ^diff
diff --git a/src/module_list.py b/src/module_list.py
diff --git a/src/sage/numerical/backends/cvxopt_backend.pxd b/src/sage/numerical/backends/cvxopt_backend.pxd
diff --git a/src/sage/numerical/backends/cvxopt_backend.pyx b/src/sage/numerical/backends/cvxopt_backend.pyx
diff --git a/src/sage/numerical/backends/generic_backend.pyx b/src/sage/numerical/backends/generic_backend.pyx
diff --git a/src/sage/numerical/backends/ppl_backend.pyx b/src/sage/numerical/backends/ppl_backend.pyx
diff --git a/src/sage/numerical/mip.pyx b/src/sage/numerical/mip.pyx

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d8ad86c	added cvxopt to the doc of mip
e3d56a8	added cvxopt to the module_list

[sagetrac-git]

Changed commit from aef3b0b to e3d56a8

[nathanncohen]

comment:8

could you add your new file to the doc index please ? :-)

SAGE_ROOT/src/doc/en/reference/numerical/index.rst

Nathann

[dimpase]

comment:9

Replying to @nathanncohen:

could you add your new file to the doc index please ? :-)

SAGE_ROOT/src/doc/en/reference/numerical/index.rst

and do not forget

src/sage/numerical/backends/generic_backend.pyx

(we are talking about stuff migrating from https://github.com/ingolfured/sageproject)

I am skeptical about the change to src/sage/numerical/backends/ppl_backend.pyx.
Why do you need this?! PPL does not work with floats, it works with arbitrary precision integers!

[sagetrac-git]

Changed commit from e3d56a8 to 36808b5

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b739867	added cvxopt to index.rst
36808b5	added cvxopt to the generic_backend.pyx

[dimpase]

comment:11

A couple of things:

# optional - CVXOPT tags should not be there, as CVXOPT is a standard part of Sage.

check the copyright notices on your .pxd and .pyx files - some of them list Nathann as the author :-)

[dimpase]

comment:12

please also add a mentioning of CVXOPT to src/doc/en/thematic_tutorials/linear_programming.rst

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

1c71941

doc for cvxopt

[sagetrac-git]

Changed commit from 36808b5 to 1c71941

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

6ee5ef3

added test to show the uniqueness of cvxopt

[sagetrac-git]

Changed commit from 1c71941 to 6ee5ef3

[nathanncohen]

comment:15

You do some damage to the documentation of generic_backend.pyx if I may say.

Nathann

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f361042

fixed the indentation for generic_backend.pyx

[sagetrac-git]

Changed commit from 6ee5ef3 to f361042

[dimpase]

comment:17

there is a little thing we never got around to fix in generic_backend:

+        ValueError: 'solver' should be set to 'GLPK', 'Coin', 'CPLEX', 'Gurobi', 'CVXOPT' or None.
         sage: default_mip_solver(former_solver)
     """
     global default_solver
@@ -917,7 +921,7 @@ def default_mip_solver(solver = None):
             return default_solver
 
         else:
-            for s in ["Cplex", "Gurobi", "Coin", "Glpk"]:
+            for s in ["Cplex", "Gurobi", "Coin", "Glpk", "Cvxopt"]:

here the lists of solvers (in both + lines) should mention PPL, too. Please fix this.

[nathanncohen]

comment:39

Hey guys, what the hell is this ?

def solve(self):
   ...
   return 0 # it should be the value of the objective function
def set_variable_type(...):
   ...
   pass

[nathanncohen]

comment:40

And the doc of set_verbosity is wrong if it does nothing. Even though that's nothing compared to the wrong results of the two functions above.

Nathann

[sagetrac-git]

Changed commit from a5c5613 to 3f13333

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3f13333

fixed the doc for set_verbosity and set_variable_type

[ingolfured]

comment:42

Replying to @nathanncohen:

Hey guys, what the hell is this ?

def solve(self):
   ...
   return 0 # it should be the value of the objective function
def set_variable_type(...):
   ...
   pass

set_variable_type is cont. by default and cannot be changed. I fixed the doc for that. The solve method in the backend returns 0 if everything went ok and the solve in mip.pyx returns the actual value. Therefore this is anormal behavior (see the ppl or glpk backends for further info) I also changed the doc for set_verbosity (does not apply for the cvxopt backend). Let me know if this is sufficient or not.

Best, Ingo

[dimpase]

comment:43

Replying to @ingolfured:

Replying to @nathanncohen:

Hey guys, what the hell is this ?

def solve(self):
   ...
   return 0 # it should be the value of the objective function
def set_variable_type(...):
   ...
   pass

set_variable_type is cont. by default and cannot be changed. I fixed the doc for that. The solve method in the backend returns 0 if everything went ok and the solve in mip.pyx returns the actual value. Therefore this is anormal behavior (see the ppl or glpk backends for further info) I also changed the doc for set_verbosity (does not apply for the cvxopt backend). Let me know if this is sufficient or not.

for consistency, set_variable_type() should behave as in ppl_backend, I think. Otherwise, it looks OK.

Regarding solve() in the backend returning 0, Nathann writes so much Sage code that he forgets what he wrote himself, e.g. in the GLPK backend... :-)

[sagetrac-git]

Changed commit from 3f13333 to f123734

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f123734

set_variable_type() is now like the one in the PPL backend

[nathanncohen]

comment:45

Yoooooooooooooooo !!

Yep, sorry for the "solve()" thing, it is my mistake. And indeed the set_variable_type is better with an exception, as the user could mistakingly believe that the solver supports integer variables if it reports nothing ^^;

Nathann

[vbraun]

comment:47

You should probably use # abs tol 1e-16 or so:

sage -t --long src/sage/numerical/backends/cvxopt_backend.pyx
**********************************************************************
File "src/sage/numerical/backends/cvxopt_backend.pyx", line 448, in sage.numerical.backends.cvxopt_backend.CVXOPTBackend.solve
Failed example:
    round(p.solve(), 2)
Expected:
             pcost       dcost       gap    pres   dres   k/t
         0: -7.3165e+00 -2.3038e+01  6e+00  0e+00  2e+00  1e+00
         ...
        8.8
Got:
         pcost       dcost       gap    pres   dres   k/t
     0: -7.3165e+00 -2.3038e+01  6e+00  5e-17  2e+00  1e+00
     1: -7.8209e+00 -1.0635e+01  1e+00  4e-16  3e-01  2e-01
     2: -8.4714e+00 -1.0546e+01  1e+00  3e-16  2e-01  2e-01
     3: -8.7876e+00 -8.8459e+00  3e-02  5e-16  6e-03  4e-03
     4: -8.7999e+00 -8.8005e+00  3e-04  7e-22  6e-05  4e-05
     5: -8.8000e+00 -8.8000e+00  3e-06  5e-16  6e-07  4e-07
     6: -8.8000e+00 -8.8000e+00  3e-08  2e-16  6e-09  4e-09
    Optimal solution found.
    8.8
**********************************************************************

[dimpase]

comment:48

Replying to @vbraun:

You should probably use # abs tol 1e-16 or so:

sage -t --long src/sage/numerical/backends/cvxopt_backend.pyx
**********************************************************************
File "src/sage/numerical/backends/cvxopt_backend.pyx", line 448, in sage.numerical.backends.cvxopt_backend.CVXOPTBackend.solve
Failed example:
    round(p.solve(), 2)
Expected:
             pcost       dcost       gap    pres   dres   k/t
         0: -7.3165e+00 -2.3038e+01  6e+00  0e+00  2e+00  1e+00
         ...
        8.8
Got:
         pcost       dcost       gap    pres   dres   k/t
     0: -7.3165e+00 -2.3038e+01  6e+00  5e-17  2e+00  1e+00

yeah, this line in the doctest

0: -7.3165e+00 -2.3038e+01  6e+00  0e+00  2e+00  1e+00

should be removed, as it is just output of the log of the convergence towards a solution, nothing important.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

6e95304

removed a line for a doctest solve cvxopt

[sagetrac-git]

Changed commit from f123734 to 6e95304

[vbraun]

Changed branch from u/ingolfured/create_a_linear_programming_backend_for_cvxopt to 6e95304

[dimpase]

comment:52

Replying to @dimpase:

A couple of things:

# optional - CVXOPT tags should not be there, as CVXOPT is a standard part of Sage.

This was never fixed... :-(

[dimpase]

Changed commit from 6e95304 to none

[dimpase]

comment:53

Replying to @dimpase:

Replying to @dimpase:

A couple of things:

# optional - CVXOPT tags should not be there, as CVXOPT is a standard part of Sage.

This was never fixed... :-(

fixed in #18569