Add SDP backend using CVXPY

[mkoeppe]

#34251 adds cvxpy and a MIP backend.

Here we add:

• ​python-mip

• ​mip-cvxpy · ​repo

• a new SDP backend;

See also:

• #26511 Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...
• #33487 package cylp - needed for the CBC backend
• #33493 package ortools - provides some more backends

[slelievre]

New commits:

​dd94452

build/pkgs/cvxpy: New pip package

[dimpase]

can we get some examples/tests using it, too?

[mkoeppe]

Replying to dimpase:

can we get some examples/tests using it, too?

see #31981

[git]

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

​714ac44	sage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
​de29f81	sage.numerical.backends.cvxpy_sdp_backend: New

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​055838b	build/pkgs/cvxpy: New pip package
​001cba1	sage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
​22367cb	sage.numerical.backends.cvxpy_sdp_backend: New
​9391d0a	Replace CVXPYSDPBackendFactory by functools.partial

[git]

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

​8afe7b3

CVXPYSDPBackend.cvxpy_problem: New

[git]

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

​c701cc2	MatrixSDPBackend._update_problem: New
​19c707a	CVXPYSDPBackend.cvxpy_variables, solve, get_objective_value: New

[git]

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

​e18f72c

CVXPYSDPBackend: Add more stubs

[mkoeppe]

Ready for a look by an SDP expert...

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​92dd31f	MatrixSDPBackend._update_problem: New
​1850188	build/pkgs/cvxpy: New pip package
​7aae0be	sage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
​0ec2ccf	CVXPYSDPBackend.cvxpy_problem: New

[git]

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

​050bde2

CVXPYSDPBackend.get_variable_value, dual_value: Implement

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​14de5d0	MatrixSDPBackend._update_problem: New
​9ba6aa3	build/pkgs/cvxpy: New pip package
​bf78b23	sage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
​5b51484	CVXPYSDPBackend.cvxpy_problem: New
​c06f1d8	CVXPYSDPBackend.get_variable_value, dual_value: Implement

[git]

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

​0715207

sage.numerical.backends.cvxpy_backend: New

[mkoeppe]

Here's a first, incomplete draft of CVXPYBackend.

[gh-sheerluck]

generic_backend.pyx

@@ -1803 +1803 @@
         if solver == "Cvxpy":
             return CVXPYBackend()
         if solver.startswith("Cvxpy/"):
-            return CVXPYBackend(cvxpy_solver=solver[len("Cvxpy/")])
+            return CVXPYBackend(cvxpy_solver=solver[len("Cvxpy/"):])

[mkoeppe]

Thanks

[git]

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

​8712d0a

src/sage/numerical/backends/cvxpy_backend.pyx: Implement MixedIntegerLinearProgram(solver="CVXPY/SciPy/HiGHS") etc.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​109922c	MatrixSDPBackend._update_problem: New
​94c6f67	build/pkgs/cvxpy: New pip package
​a727933	sage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
​472d55a	CVXPYSDPBackend.cvxpy_problem: New
​20e9151	CVXPYSDPBackend.get_variable_value, dual_value: Implement
​372cb11	sage.numerical.backends.cvxpy_backend: New
​73e30fb	src/sage/numerical/backends/cvxpy_backend.pyx: Implement MixedIntegerLinearProgram(solver="CVXPY/SciPy/HiGHS") etc.

[git]

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

​8d9f44f	CVXPYBackend.set_objective: Fix up
​0c721a9	CVXPYBackend.get_variable_value: Convert array to float, fix doctests

[git]

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

​e4fb13d

src/sage/numerical/backends/generic_backend.pyx: Make Cvxpy/cbc the default solver if available

[git]

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

​3edafec	build/pkgs/cylp: New
​8b27e69	build/pkgs/cylp: Add megapatch 'Re-generating with Cython 0.29.27 for Python 3.10 compatibility', do not use CYLP_USE_CYTHON
​156e789	Merge #33487

[mkoeppe]

Some methods are not implemented yet, but some things work already. After ./sage -i cvxpy cylp, the CVXPY/CBC solver is the default and ./sage -tp src/sage/graphs/ gives only a few errors.

[git]

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

​607b6d8	CVXPYBackend.add_variable: Handle coefficients
​f3b8d63	src/sage/numerical/backends/cvxpy_backend.pyx: Increase abs tol in doctests

[gh-sheerluck]

Thanks to this ticket I was able to solve #32053

sage: designs.steiner_triple_system(7).coloring(solver="cvxpy/CBC")
[[0, 2, 3, 6], [4, 5], [1]]

by adding some code from ppl_backend.pyx to cvxpy_backend.{pyx,pxd}

but in mip.pyx I got value = self._backend_variable_value(v, tolerance) of type <class 'numpy.ndarray'> and that is a bug.

[git]

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

​7d74609

adding some code from ppl_backend.pyx to cvxpy_backend.{pyx,pxd}

[mkoeppe]

Thanks! I've committed your additions.

[mkoeppe]

Replying to gh-sheerluck:

but in mip.pyx I got value = self._backend_variable_value(v, tolerance) of type <class 'numpy.ndarray'> and that is a bug.

I already fixed this one in one of my commits

[gh-sheerluck]

btw is_variable_binary, is_variable_integer, is_variable_continuous should be properly implemented, return True or return False is inflexible :)

[git]

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

​193b78c

CVXPYBackend.is_variable_{boolean,integer,continuous}: Implement

[git]

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

​92af4da

src/sage/numerical/backends/cvxpy_backend.pyx: Fix up some doctests

[git]

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

​979a9a9

CVXPYBackend.objective_coefficient: Fix up

[mkoeppe]

These failures indicate that the solver doesn't handle integer variables correctly. Not sure if it's the new interface or if the CyLP/CBC backend in CVXPY that is not in good shape.

sage -t --random-seed=200293476130791194302620065212091883890 src/sage/graphs/comparability.pyx
**********************************************************************
File "src/sage/graphs/comparability.pyx", line 417, in sage.graphs.comparability.is_comparability_MILP
Failed example:
    is_comparability(graphs.CycleGraph(5), certificate = True)
Exception raised:
    Traceback (most recent call last):
      File "/Users/mkoeppe/s/sage/sage-rebasing/worktree-gcc11/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/mkoeppe/s/sage/sage-rebasing/worktree-gcc11/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.comparability.is_comparability_MILP[1]>", line 1, in <module>
        is_comparability(graphs.CycleGraph(Integer(5)), certificate = True)
      File "sage/graphs/comparability.pyx", line 475, in sage.graphs.comparability.is_comparability_MILP (build/cythonized/sage/graphs/comparability.c:5404)
        o = p.get_values(o, convert=True, tolerance=tol)
      File "sage/numerical/mip.pyx", line 1770, in sage.numerical.mip.MixedIntegerLinearProgram.get_values (build/cythonized/sage/numerical/mip.c:12568)
        c[k] = get_backend_variable_value(v, tolerance)
      File "sage/numerical/mip.pyx", line 1523, in sage.numerical.mip.MixedIntegerLinearProgram._backend_variable_value_True (build/cythonized/sage/numerical/mip.c:11789)
        return self._backend_variable_value_ZZ(v, tolerance)
      File "sage/numerical/mip.pyx", line 1441, in sage.numerical.mip.MixedIntegerLinearProgram._backend_variable_value_ZZ (build/cythonized/sage/numerical/mip.c:11278)
        raise RuntimeError(f'variable {v} exceeds integrality tolerance {tolerance}')
    RuntimeError: variable x_0 exceeds integrality tolerance 1e-06

[gh-sheerluck]

I use patched cvxpy/reductions/solvers/conic_solvers/cbc_conif.py for import mip and I got

sage -t --random-seed=200293476130791194302620065212091883890 src/sage/graphs/comparability.pyx
    [52 tests, 11.50 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------

[mkoeppe]

Any relation to ​https://pypi.org/project/mip-cvxpy/?

[gh-sheerluck]

yes, my patch is full copy of mip-cvxpy with class class PYTHON_MIP renamed:

sage: from cvxpy import installed_solvers; installed_solvers()
['CBC', 'CVXOPT', 'DIFFCP', 'ECOS', 'ECOS_BB', 'GLPK', 'GLPK_MI', 'OSQP', 'SCIPY', 'SCS']

that 'CBC' is actually 'PYTHON_MIP'

[mkoeppe]

I also tested with default_mip_solver('CVXPY/GLPK_MI'), which works fine. So the problem is definitely in the CyLP/CBC backend or even in CyLP itself.

[mkoeppe]

This appears to be ​https://github.com/coin-or/CyLP/issues/81 - integer infeasibility is not handled correctly in cylp (and not covered by their testsuite)

[mkoeppe]

Workaround: ​https://github.com/cvxpy/cvxpy/pull/1703

[gh-sheerluck]

I was fighting with python-mip to get something like model.setNumberThreads(ncpus()) from coin_backend.pyx and then I realized that python-mip does not use my fresh local cbc, it has its own old binary mip/libraries/cbc-c-linux-x86-64.so stored in github. And CyLP tells me his CbcMain0 from cylp/cpp/ICbcModel.cpp is not compatible with my CbcMain0 from /usr/include/coin-or/CbcSolver.hpp. So I guess I have to find myself another library :)

[git]

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

​6f7eb15	build/pkgs/mip: New
​b0317ba	build/pkgs/mip_cvxpy: New
​0804514	default_mip_solver: Use Cvxpy/mip/cbc instead of Cvxpy/cbc

[mkoeppe]

Replying to gh-sheerluck:

I realized that python-mip does not use my fresh local cbc

I guess one needs to install it as sage -pip install --no-binary :all: mip

[mkoeppe]

Oh, I see, even the source tarball has these, and it can only be overridden using an environment variable. ​https://github.com/coin-or/python-mip/blob/master/mip/cbc.py#L63

That's of course highly problematic.

[mkoeppe]

The build script for this vendored stuff are in ​https://github.com/coin-or/python-mip/tree/master/scripts

[mkoeppe]

So far python-mip is not present in major distributions, ​https://repology.org/project/python:mip/versions, so we cannot see how they would be dealing with this type of vendoring.

[git]

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

​3ab590b

sage.numerical.backends.generic_backend.get_solver: For Cvxpy/mip/..., set SOLVER_NAME

[gh-sheerluck]

Replying to mkoeppe:

The build script for this vendored stuff are in ​https://github.com/coin-or/python-mip/tree/master/scripts

for now I manually run

g++ -shared -fPIC -march=native -mtune=native -O3 \
 -maes -mavx -mavx2 -mf16c -mfma -mmmx -mpclmul \
 -mpopcnt -msse -msse2 -msse3 -msse4.1 -msse4.2 \
 -o ./cbc-c-linux-x86-64.so \
 -I/usr/include/coin-or \
 -I/usr/include/coin/ThirdParty \
 -DCBC_THREAD \
 ./Cbc_C_Interface.cpp \
 -L/usr/lib64 \
 -lCbc -lpthread -lrt -lCgl \
 -lOsiClp -lClp -lOsi -lCoinUtils \
 -lgfortran -lquadmath -lm

strip ./cbc-c-linux-x86-64.so

Then I manually copy ./cbc-c-linux-x86-64.so to /usr/lib/python3.10/site-packages/mip/libraries

it's good enough for now. But coin_backend.pyx with model.setNumberThreads(ncpus()) is way better... if it wasn't broken.

[git]

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

​23518f4	build/pkgs/cylp: Add patch from https://github.com/coin-or/CyLP/pull/150
​a7416f0	default_mip_solver: Back to using Cvxpy/cbc, not Cvxpy/mip/cbc
​444d1d0	build/pkgs/cvxpy: Use https://github.com/cvxpy/cvxpy/pull/1707

[mkoeppe]

Back to using Cvxpy/cbc.

The remaining failures are from unimplemented set_variable_type

[mkoeppe]

Replying to mkoeppe:

The remaining failures are from unimplemented set_variable_type

I've opened #33504 sage.graphs, sage.numerical.mip: Remove unnecessary uses of set_binary, set_integer.

[git]

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

​cbfeef2	MIPVariable: Avoid using _backend.set_variable_type
​6c1a8f5	vertex_separation_MILP: Remove redundant call of set_binary
​44e219f	GenericGraph.multicommodity_flow: Directly create MIP variables as integers, do not use set_integer
​d0320b1	Merge #33504

[git]

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

​6daae93

build/pkgs/cylp: Add another commit from https://github.com/coin-or/CyLP/pull/150

[git]

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

​8bd5e04	src/sage/numerical/backends/cvxpy_backend_test.py: New
​3275a0e	build/pkgs/cylp: Update to 0.91.5, remove patches

[git]

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

​7b30db4

build/pkgs/cvxpy/requirements.txt: Update git ref

[git]

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

​c4462bc

build/pkgs/mip/SPKG.rst: Add license