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.

[dimpase]

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

[git]

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

​aef3b0b

added the missing cvxopt backend files

[dimpase]

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

[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

[ncohen]

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

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

Nathann

[dimpase]

Replying to ncohen:

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!

[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]

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]

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

[git]

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

​1c71941

doc for cvxopt

[git]

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

​6ee5ef3

added test to show the uniqueness of cvxopt

[ncohen]

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

Nathann

[git]

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

​f361042

fixed the indentation for generic_backend.pyx

[dimpase]

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.

[dimpase]

Ingo, did you try building docs? I get

[numerical] docstring of sage.numerical.backends.cvxopt_backend.CVXOPTBackend.add_col:16: ERROR: Unexpected indentation.
[numerical] docstring of sage.numerical.backends.cvxopt_backend.CVXOPTBackend.add_col:17: WARNING: Block quote ends without a blank line; unexpected unindent.
[numerical] docstring of sage.numerical.backends.cvxopt_backend.CVXOPTBackend.add_col:24: WARNING: Block quote ends without a blank line; unexpected unindent.
[numerical] docstring of sage.numerical.backends.cvxopt_backend.CVXOPTBackend.add_col:26: WARNING: Block quote ends without a blank line; unexpected unindent.

(there is some silly formatting error in cvxopt_backend, apparently)

[git]

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

​2fc6f05

added ppl to a few places in generic_backend

[ncohen]

Yo !

You put cvxopt before gurobi in the ordering of LP solvers: this list is meant to be "use the fastest solver available installed on this computer". Is CVXOPT faster than Gurobi ?

Besides:

1) It is useless to put anything after a solver which is installed by default

2) PPL cannot really be a "default solver" as it misses the important feature of being able to solve integer linear programs.

Nathann

[dimpase]

Replying to ncohen:

You put cvxopt before gurobi in the ordering of LP solvers: this list is meant to be "use the fastest solver available installed on this computer". Is CVXOPT faster than Gurobi ?

This list for making the most suitable for the task solver the default. For the duration of a Sage session. E.g. it can be PPL, if you need to solve badly conditioned LPs with huge coefficients, or it can be CVXOPT, if you need an interior point solver as opposed to a simplex algorithm solver.

Besides:

1) It is useless to put anything after a solver which is installed by default

huh?

2) PPL cannot really be a "default solver" as it misses the important feature of being able to solve integer linear programs.

We have discussed this in April: let me quote your email dated 22.04.14:

DP 1) I'd like this:

DP sage: sage.numerical.backends.generic_backend.default_mip_solver(solver='PPL')

DP to work...

NC Well. PPL is just missing from the list of keywords, it should only be

NC added there. Can you write the patch ? I will review it, it takes ten

NC seconds.

[ncohen]

Yo !

You put cvxopt before gurobi in the ordering of LP solvers: this list is meant to be "use the fastest solver available installed on this computer". Is CVXOPT faster than Gurobi ?

This list for making the most suitable for the task solver the default.

No, this list is a linear ordering that makes Sage's default the first solver that can be called and that appears in the list. If CVXOPT is the second, and as it is available by default, then none of the others will ever become the default. And unless you tell me that CVXOPT is faster than gurobi it should appear afterwards.

1) It is useless to put anything after a solver which is installed by default

huh?

2) PPL cannot really be a "default solver" as it misses the important feature of being able to solve integer linear programs.

We have discussed this in April: let me quote your email dated 22.04.14:

DP 1) I'd like this:

DP sage: sage.numerical.backends.generic_backend.default_mip_solver(solver='PPL')

DP to work...

NC Well. PPL is just missing from the list of keywords, it should only be

NC added there. Can you write the patch ? I will review it, it takes ten

NC seconds.

I don't see what you intend by quoting me against myself. Just read the code :

    if solver is None:

        if default_solver is not None:
            return default_solver

        else:
            for s in ["Cplex", "Cvxopt", "Gurobi", "Coin", "Glpk", "Ppl"]:
                try:
                    default_mip_solver(s)
                    return s
                except ValueError:
                    pass

If CPLEX is available, Cplex will be used. If CVXOPT is available, it will be used. And CVXOPT is always available, so none of the others LP will ever be used.

If you want to be able to make CVXOPT the default solver all you need is this part of your branch

    elif solver == "Cvxopt":
        try:
            from sage.numerical.backends.cvxopt_backend import CVXOPTBackend
            default_solver = solver
        except ImportError:
            raise ValueError("CVXOPT is not available. Please refer to the documentation to install it.")

Touching the list changes the "automatically defined" default solver of Sage. And as the code shows, by puting cvxopt second you may as well remove anything that appears after it. Similarly, it's useless to put anything after Glpk. In the current state the function will only test Cplex and CVXOPT.

Nathann

[dimpase]

Replying to ncohen:

Yo !

right, sorry, I should have read the code. We'll fix this, thanks!

[git]

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

​d0cdab2

fixing links in generic_backend - finally docs build

[git]

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

​6d17e00

giving the correct description of CVXOPT in the thematic tute

[dimpase]

I hope the last commits fix all the remaining issues. Review?

[dimpase]

I'm trying to finish this off now, and I get

sage -t src/sage/numerical/backends/cvxopt_backend.pyx
**********************************************************************
File "src/sage/numerical/backends/cvxopt_backend.pyx", line 467, 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
         1: -7.8209e+00 -1.0635e+01  1e+00  1e-16  3e-01  2e-01
         2: -8.4714e+00 -1.0546e+01  1e+00  4e-16  2e-01  2e-01
         3: -8.7876e+00 -8.8459e+00  3e-02  1e-16  6e-03  4e-03
         4: -8.7999e+00 -8.8005e+00  3e-04  2e-16  6e-05  4e-05
         5: -8.8000e+00 -8.8000e+00  3e-06  2e-16  6e-07  4e-07
         6: -8.8000e+00 -8.8000e+00  3e-08  1e-16  6e-09  4e-09
        Optimal solution found.
        8.8
Got:
         pcost       dcost       gap    pres   dres   k/t
     0: -7.3165e+00 -2.3038e+01  6e+00  0e+00  2e+00  1e+00
     1: -7.8209e+00 -1.0635e+01  1e+00  1e-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  6e-17  6e-03  4e-03
     4: -8.7999e+00 -8.8005e+00  3e-04  2e-16  6e-05  4e-05
     5: -8.8000e+00 -8.8000e+00  3e-06  2e-16  6e-07  4e-07
     6: -8.8000e+00 -8.8000e+00  3e-08  1e-16  6e-09  4e-09
    Optimal solution found.
    8.8
**********************************************************************
1 item had failures:
   1 of  53 in sage.numerical.backends.cvxopt_backend.CVXOPTBackend.solve
    [201 tests, 1 failure, 0.11 s]

when I merge with the latest version, 6.3.beta6. Any idea why? (It's of course easy to fix, looks like spacing has changed for some reason).

---

New commits:

​470d0cb

Refactored the tests for solve in cvxopt_backend

[dimpase]

and another easy to fix thing:

sage -t src/sage/numerical/backends/generic_backend.pyx
**********************************************************************
File "src/sage/numerical/backends/generic_backend.pyx", line 913, in sage.numerical.backends.generic_backend.default_mip_solver
Failed example:
    default_mip_solver("Yeahhhhhhhhhhh")
Expected:
    Traceback (most recent call last):
    ...
    ValueError: 'solver' should be set to 'GLPK', 'Coin', 'CPLEX', 'CVXOPT', 'Gurobi', 'PPL' or None.
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/home/scratch/dimpase/sage/sage-6.3.beta2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/home/scratch/dimpase/sage/sage-6.3.beta2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.numerical.backends.generic_backend.default_mip_solver[3]>", line 1, in <module>
        default_mip_solver("Yeahhhhhhhhhhh")
      File "generic_backend.pyx", line 975, in sage.numerical.backends.generic_backend.default_mip_solver (build/cythonized/sage/numerical/backends/generic_backend.c:7373)
    ValueError: 'solver' should be set to 'GLPK', 'Coin', 'CPLEX', 'Gurobi', 'CVXOPT', 'PPL' or None.

here the problem is that the output does not match the doctest, as in the doctest the order of solvers is different : CVXOPT and Gurobi are swapped.

The best way to create a proper docstring is to run the command, in this case default_mip_solver("Yeahhhhhhhhhhh"), at the Sage prompt and then paste the output into the source.

[dimpase]

Ingo, and please add your full name to the copyright notices, not just your given name. (Risan, my student from Indonesia, who wrote PPL interface, officially has just one name, and this might have confused you).

[git]

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

​fb45d8b

in generic_backend, ppl fixed, test added and another test fixed

[dimpase]

Replying to dimpase:

I'm trying to finish this off now, and I get

sage -t src/sage/numerical/backends/cvxopt_backend.pyx
**********************************************************************
File "src/sage/numerical/backends/cvxopt_backend.pyx", line 467, 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
         1: -7.8209e+00 -1.0635e+01  1e+00  1e-16  3e-01  2e-01
         2: -8.4714e+00 -1.0546e+01  1e+00  4e-16  2e-01  2e-01
         3: -8.7876e+00 -8.8459e+00  3e-02  1e-16  6e-03  4e-03
         4: -8.7999e+00 -8.8005e+00  3e-04  2e-16  6e-05  4e-05
         5: -8.8000e+00 -8.8000e+00  3e-06  2e-16  6e-07  4e-07
         6: -8.8000e+00 -8.8000e+00  3e-08  1e-16  6e-09  4e-09
        Optimal solution found.
        8.8
Got:
         pcost       dcost       gap    pres   dres   k/t
     0: -7.3165e+00 -2.3038e+01  6e+00  0e+00  2e+00  1e+00
     1: -7.8209e+00 -1.0635e+01  1e+00  1e-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  6e-17  6e-03  4e-03
     4: -8.7999e+00 -8.8005e+00  3e-04  2e-16  6e-05  4e-05
     5: -8.8000e+00 -8.8000e+00  3e-06  2e-16  6e-07  4e-07
     6: -8.8000e+00 -8.8000e+00  3e-08  1e-16  6e-09  4e-09
    Optimal solution found.
    8.8
**********************************************************************
1 item had failures:
   1 of  53 in sage.numerical.backends.cvxopt_backend.CVXOPTBackend.solve
    [201 tests, 1 failure, 0.11 s]

when I merge with the latest version, 6.3.beta6. Any idea why? (It's of course easy to fix, looks like spacing has changed for some reason).

The latest commit (​fb45d8b in generic_backend, ppl fixed, test added and another test fixed ) fixes all the problems, except this one (indeed, it doesn't even touch the cvxopt backend). Please look into it.

[git]

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

​a5c5613

potential fix for the test in cvxopt_backend.pyx

[dimpase]

OK, looks good now. Tested by merging over 6.3.beta6.

[vbraun]

Author & Reviewer name

[ncohen]

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

[ncohen]

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

[git]

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

​3f13333

fixed the doc for set_verbosity and set_variable_type

[ingolfured]

Replying to ncohen:

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]

Replying to ingolfured:

Replying to ncohen:

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... :-)

[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

[ncohen]

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]

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]

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.

[git]

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

​6e95304

removed a line for a doctest solve cvxopt

[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... :-(

[dimpase]

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