search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.31k stars 449 forks source link

Add SDP backend using CVXPY #31962

Open mkoeppe opened 3 years ago

mkoeppe commented 3 years ago

34251 adds cvxpy and a MIP backend.

Here we add:

See also:

Depends on #33487 Depends on #33504 Depends on #34251

CC: @dimpase @yuan-zhou @sheerluck @dcoudert @seblabbe

Component: linear programming

Work Issues: Rebase on #34251

Author: Matthias Koeppe, Andrey Belgorodski

Branch/Commit: u/mkoeppe/package_cvxpy @ c4462bc

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

mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -6,7 +6,31 @@

 with differentiable programming - 
 https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients
+(see also https://github.com/cvxgrp/cvxpylayers)

-https://github.com/cvxgrp/cvxpylayers
+https://github.com/cvxpy/cvxpy/blob/master/setup.py:
+
+```
+    python_requires='>=3.6',
+    install_requires=["osqp >= 0.4.1",
+                      "ecos >= 2",
+                      "scs >= 1.1.6",
+                      "numpy >= 1.15",
+                      "scipy >= 1.1.0"],
+```
+
+osqp: https://github.com/osqp/osqp-python/blob/master/requirements.txt
+
+```
+numpy >= 1.7
+scipy >= 0.13.2
+qdldl
+```
+
+qdldl: depends on pybind11
+
+ecos: https://github.com/embotech/ecos-python
+
+scs: https://github.com/bodono/scs-python
mkoeppe commented 3 years ago

Branch: u/mkoeppe/package_cvxpy

slel commented 3 years ago

Description changed:

--- 
+++ 
@@ -1,36 +1,52 @@
-... for disciplined convex programming and extensions
+We add cvxpy for disciplined convex programming and extensions.

-https://www.cvxpy.org/index.html
+- cvxpy ([home](https://www.cvxpy.org/)
+  · [repo](https://github.com/cvxpy/cvxpy)
+  · [PyPI](https://pypi.org/project/cvxpy/))
+- can call [many backend solvers](https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver)
+- supports [differentiable programming](https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients)

-with many backend solvers - https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver
+See also [cvxpyplayers](https://github.com/cvxgrp/cvxpylayers).

-with differentiable programming - 
-https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients
-(see also https://github.com/cvxgrp/cvxpylayers)
-
-https://github.com/cvxpy/cvxpy/blob/master/setup.py:
+Requirements listed in
+cvxpy's [setup.py](https://github.com/cvxpy/cvxpy/blob/master/setup.py):

-osqp: https://github.com/osqp/osqp-python/blob/master/requirements.txt +So the new dependencies are:

- -numpy >= 1.7 -scipy >= 0.13.2 -qdldl - +- osqp (operator splitting quadratic program)

-qdldl: depends on pybind11 +In addition, osqp's requirements.txt lists: +numpy >= 1.7, scipy >= 0.13.2, qdldl

-ecos: https://github.com/embotech/ecos-python +which adds:

-scs: https://github.com/bodono/scs-python +- qldl-python (interface

+Finally, qldl-python depends on pybind11:

+- pybind11 (seamless operability between C++11 and Python)

slel commented 3 years ago

New commits:

dd94452build/pkgs/cvxpy: New pip package
slel commented 3 years ago

Commit: dd94452

dimpase commented 3 years ago
comment:4

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

mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -43,10 +43,6 @@
   ([repo](https://github.com/osqp/qdldl-python)
   · [PyPI](https://pypi.org/project/qldl/))

-Finally, qldl-python depends on pybind11:
+Finally, qldl-python depends on pybind11 (already an SPKG)

-- pybind11 (seamless operability between C++11 and Python)
-  ([repo](https://github.com/pybind/pybind11)
-  · [PyPI](https://pypi.org/project/pybind11/)
-  · [docs](https://pybind11.readthedocs.io/))
mkoeppe commented 3 years ago
comment:6

Replying to @dimpase:

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

see #31981

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

714ac44sage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
de29f81sage.numerical.backends.cvxpy_sdp_backend: New
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from dd94452 to de29f81

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from de29f81 to 9391d0a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

055838bbuild/pkgs/cvxpy: New pip package
001cba1sage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
22367cbsage.numerical.backends.cvxpy_sdp_backend: New
9391d0aReplace CVXPYSDPBackendFactory by functools.partial
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 9391d0a to 8afe7b3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

8afe7b3CVXPYSDPBackend.cvxpy_problem: New
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

c701cc2MatrixSDPBackend._update_problem: New
19c707aCVXPYSDPBackend.cvxpy_variables, solve, get_objective_value: New
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 8afe7b3 to 19c707a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 19c707a to e18f72c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

e18f72cCVXPYSDPBackend: Add more stubs
mkoeppe commented 3 years ago

Author: Matthias Koeppe, ...

mkoeppe commented 3 years ago
comment:14

Ready for a look by an SDP expert...

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

92dd31fMatrixSDPBackend._update_problem: New
1850188build/pkgs/cvxpy: New pip package
7aae0besage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
0ec2ccfCVXPYSDPBackend.cvxpy_problem: New
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from e18f72c to 0ec2ccf

mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -6,7 +6,7 @@
 - can call [many backend solvers](https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver)
 - supports [differentiable programming](https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients)

-See also [cvxpyplayers](https://github.com/cvxgrp/cvxpylayers).
+See also [cvxpylayers](https://github.com/cvxgrp/cvxpylayers).

 Requirements listed in
 cvxpy's [setup.py](https://github.com/cvxpy/cvxpy/blob/master/setup.py):
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 0ec2ccf to 050bde2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

050bde2CVXPYSDPBackend.get_variable_value, dual_value: Implement
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -2,6 +2,7 @@

 - cvxpy ([home](https://www.cvxpy.org/)
   · [repo](https://github.com/cvxpy/cvxpy)
+  · [releases](https://github.com/cvxpy/cvxpy/releases)
   · [PyPI](https://pypi.org/project/cvxpy/))
 - can call [many backend solvers](https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver)
 - supports [differentiable programming](https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients)
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -4,7 +4,7 @@
   · [repo](https://github.com/cvxpy/cvxpy)
   · [releases](https://github.com/cvxpy/cvxpy/releases)
   · [PyPI](https://pypi.org/project/cvxpy/))
-- can call [many backend solvers](https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver)
+- It can call [many backend solvers](https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver) -- including most that we currently have as MIP backends, so it may be suitable as a replacement for our homegrown backend code
 - supports [differentiable programming](https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients)

 See also [cvxpylayers](https://github.com/cvxgrp/cvxpylayers).
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -5,6 +5,7 @@
   · [releases](https://github.com/cvxpy/cvxpy/releases)
   · [PyPI](https://pypi.org/project/cvxpy/))
 - It can call [many backend solvers](https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver) -- including most that we currently have as MIP backends, so it may be suitable as a replacement for our homegrown backend code
+- Promising route to [add support for the HiGHS LP/MIP solvers](https://github.com/cvxpy/cvxpy/issues/1443) via the [scipy cython interface to their vendored HiGHS](https://github.com/scipy/scipy/issues/14455)
 - supports [differentiable programming](https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients)

 See also [cvxpylayers](https://github.com/cvxgrp/cvxpylayers).
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -47,4 +47,6 @@

 Finally, qldl-python depends on pybind11 (already an SPKG)

+See also:
+-  #33487 package cylp - needed for the CBC backend
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 050bde2 to c06f1d8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

14de5d0MatrixSDPBackend._update_problem: New
9ba6aa3build/pkgs/cvxpy: New pip package
bf78b23sage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
5b51484CVXPYSDPBackend.cvxpy_problem: New
c06f1d8CVXPYSDPBackend.get_variable_value, dual_value: Implement
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

0715207sage.numerical.backends.cvxpy_backend: New
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from c06f1d8 to 0715207

mkoeppe commented 2 years ago
comment:26

Here's a first, incomplete draft of CVXPYBackend.

sheerluck commented 2 years ago
comment:27
--- a/generic_backend.pyx
+++ b/generic_backend.pyx
@@ -1803,7 +1803,7 @@
         if solver == "Cvxpy":
             return CVXPYBackend()
         if solver.startswith("Cvxpy/"):
-            return CVXPYBackend(cvxpy_solver=solver[len("Cvxpy/")])
+            return CVXPYBackend(cvxpy_solver=solver[len("Cvxpy/"):])
mkoeppe commented 2 years ago
comment:28

Thanks

mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -48,5 +48,6 @@
 Finally, qldl-python depends on pybind11 (already an SPKG)

 See also:
--  #33487 package cylp - needed for the CBC backend
+- #33487 package cylp - needed for the CBC backend
+- #33493 package ortools - provides some more backends
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 0715207 to 8712d0a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

8712d0asrc/sage/numerical/backends/cvxpy_backend.pyx: Implement MixedIntegerLinearProgram(solver="CVXPY/SciPy/HiGHS") etc.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

109922cMatrixSDPBackend._update_problem: New
94c6f67build/pkgs/cvxpy: New pip package
a727933sage.numerical.backends.generic_sdp_backend.{get_solver,default_sdp_solver}: Refactor through new function resolve_sdp_solver
472d55aCVXPYSDPBackend.cvxpy_problem: New
20e9151CVXPYSDPBackend.get_variable_value, dual_value: Implement
372cb11sage.numerical.backends.cvxpy_backend: New
73e30fbsrc/sage/numerical/backends/cvxpy_backend.pyx: Implement MixedIntegerLinearProgram(solver="CVXPY/SciPy/HiGHS") etc.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 8712d0a to 73e30fb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

8d9f44fCVXPYBackend.set_objective: Fix up
0c721a9CVXPYBackend.get_variable_value: Convert array to float, fix doctests
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 73e30fb to 0c721a9

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 0c721a9 to e4fb13d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

e4fb13dsrc/sage/numerical/backends/generic_backend.pyx: Make Cvxpy/cbc the default solver if available
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from e4fb13d to 156e789

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

3edafecbuild/pkgs/cylp: New
8b27e69build/pkgs/cylp: Add megapatch 'Re-generating with Cython 0.29.27 for Python 3.10 compatibility', do not use CYLP_USE_CYTHON
156e789Merge #33487
mkoeppe commented 2 years ago

Dependencies: #33487

mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-We add cvxpy for disciplined convex programming and extensions.
+We add `cvxpy` for disciplined convex programming and extensions.

 - cvxpy ([home](https://www.cvxpy.org/)
   · [repo](https://github.com/cvxpy/cvxpy)
@@ -8,9 +8,13 @@
 - Promising route to [add support for the HiGHS LP/MIP solvers](https://github.com/cvxpy/cvxpy/issues/1443) via the [scipy cython interface to their vendored HiGHS](https://github.com/scipy/scipy/issues/14455)
 - supports [differentiable programming](https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients)

-See also [cvxpylayers](https://github.com/cvxgrp/cvxpylayers).
+As of this ticket:
+- we add `cvxpy` only as an optional "pip" package;
+- we add a new MIP backend and a new SDP backend;
+- when both `cvxpy` and `cylp` are installed, the solver `"CVXPY/CBC"` becomes the default (unless Gurobi or CPLEX are available).

-Requirements listed in
+
+Details about dependencies: Requirements listed in
 cvxpy's [setup.py](https://github.com/cvxpy/cvxpy/blob/master/setup.py):

@@ -47,6 +51,8 @@

Finally, qldl-python depends on pybind11 (already an SPKG)

+See also cvxpylayers. + See also:

mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -57,3 +57,7 @@
 - #33487 package cylp - needed for the CBC backend
 - #33493 package ortools - provides some more backends

+Follow-ups:
+- Retire `sage_numerical_backends_coin`
+- #30644 upgrade `cbc`
+