Opened 14 months ago
Last modified 3 weeks ago
#31962 new enhancement
Add SDP backend using CVXPY
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.8 |
Component: | linear programming | Keywords: | |
Cc: | dimpase, yzh, gh-sheerluck, dcoudert, slabbe | Merged in: | |
Authors: | Matthias Koeppe, Andrey Belgorodski | Reviewers: | |
Report Upstream: | N/A | Work issues: | Rebase on #34251 |
Branch: | u/mkoeppe/package_cvxpy (Commits, GitHub, GitLab) | Commit: | c4462bc75e51c74e1f26e613299faba35541d208 |
Dependencies: | #33487, #33504, #34251 | Stopgaps: |
Description (last modified by )
Attachments (3)
Change History (83)
comment:1 Changed 14 months ago by
- Description modified (diff)
comment:2 Changed 14 months ago by
- Branch set to u/mkoeppe/package_cvxpy
comment:3 Changed 14 months ago by
- Commit set to dd94452e7d030ee49e1551f4ea0914020f7188ff
- Description modified (diff)
comment:4 follow-up: ↓ 6 Changed 14 months ago by
can we get some examples/tests using it, too?
comment:5 Changed 14 months ago by
- Description modified (diff)
comment:6 in reply to: ↑ 4 Changed 14 months ago by
comment:7 Changed 13 months ago by
- Milestone changed from sage-9.4 to sage-9.5
comment:8 Changed 13 months ago by
- Summary changed from Package cvxpy to Package cvxpy, add SDP backend
comment:9 Changed 13 months ago by
- Commit changed from dd94452e7d030ee49e1551f4ea0914020f7188ff to de29f81e036d0638bb4b07bb41d434659dcdd545
comment:10 Changed 13 months ago by
- Commit changed from de29f81e036d0638bb4b07bb41d434659dcdd545 to 9391d0aa72a7cca4169fef8efdcfc60521d6caaf
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
|
comment:11 Changed 13 months ago by
- Commit changed from 9391d0aa72a7cca4169fef8efdcfc60521d6caaf to 8afe7b3805b0ca389935b0b40b5633bf1b10e3fe
Branch pushed to git repo; I updated commit sha1. New commits:
8afe7b3 | CVXPYSDPBackend.cvxpy_problem: New
|
comment:12 Changed 13 months ago by
- Commit changed from 8afe7b3805b0ca389935b0b40b5633bf1b10e3fe to 19c707a492046098ef653ab4281faf8e266570b8
comment:13 Changed 13 months ago by
- Commit changed from 19c707a492046098ef653ab4281faf8e266570b8 to e18f72ca6d9cdeef7b07fbb2a6bbcd85e02ac2f1
Branch pushed to git repo; I updated commit sha1. New commits:
e18f72c | CVXPYSDPBackend: Add more stubs
|
comment:15 Changed 13 months ago by
- Commit changed from e18f72ca6d9cdeef7b07fbb2a6bbcd85e02ac2f1 to 0ec2ccf3cb7adb93bad48edc1703df43aa31756e
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
|
comment:16 Changed 13 months ago by
- Description modified (diff)
comment:17 Changed 13 months ago by
- Commit changed from 0ec2ccf3cb7adb93bad48edc1703df43aa31756e to 050bde2bdba63cc6f5b58de1a3510928754aab02
Branch pushed to git repo; I updated commit sha1. New commits:
050bde2 | CVXPYSDPBackend.get_variable_value, dual_value: Implement
|
comment:18 Changed 8 months ago by
- Milestone changed from sage-9.5 to sage-9.6
comment:19 Changed 8 months ago by
- Description modified (diff)
comment:20 Changed 8 months ago by
- Description modified (diff)
comment:21 Changed 8 months ago by
- Description modified (diff)
comment:22 Changed 6 months ago by
- Milestone changed from sage-9.6 to sage-9.7
comment:23 Changed 5 months ago by
- Cc gh-sheerluck added
- Description modified (diff)
- Summary changed from Package cvxpy, add SDP backend to Package cvxpy, add SDP backend, add MIP backend
comment:24 Changed 5 months ago by
- Commit changed from 050bde2bdba63cc6f5b58de1a3510928754aab02 to c06f1d8ed5ec311e12056f376d0b030933a152ce
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
|
comment:25 Changed 5 months ago by
- Commit changed from c06f1d8ed5ec311e12056f376d0b030933a152ce to 07152073525fffa8a5eac0c700ff11143a9fdf32
Branch pushed to git repo; I updated commit sha1. New commits:
0715207 | sage.numerical.backends.cvxpy_backend: New
|
comment:26 Changed 5 months ago by
Here's a first, incomplete draft of CVXPYBackend
.
comment:27 Changed 5 months ago by
-
generic_backend.pyx
a b 1803 1803 if solver == "Cvxpy": 1804 1804 return CVXPYBackend() 1805 1805 if solver.startswith("Cvxpy/"): 1806 return CVXPYBackend(cvxpy_solver=solver[len("Cvxpy/") ])1806 return CVXPYBackend(cvxpy_solver=solver[len("Cvxpy/"):])
comment:28 Changed 5 months ago by
Thanks
comment:29 Changed 5 months ago by
- Description modified (diff)
comment:30 Changed 5 months ago by
- Commit changed from 07152073525fffa8a5eac0c700ff11143a9fdf32 to 8712d0a865cf8d93346d3e030bf06f720cdfee7d
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.
|
comment:31 Changed 5 months ago by
- Commit changed from 8712d0a865cf8d93346d3e030bf06f720cdfee7d to 73e30fb59ebf7096b28b01790f2912f763bfce73
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.
|
comment:32 Changed 5 months ago by
- Commit changed from 73e30fb59ebf7096b28b01790f2912f763bfce73 to 0c721a96dabf34fc71a8ee347ac82fc623aee10a
comment:33 Changed 5 months ago by
- Commit changed from 0c721a96dabf34fc71a8ee347ac82fc623aee10a to e4fb13d25af0b03654ee641b8ab866baaf372785
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
|
comment:34 Changed 5 months ago by
- Commit changed from e4fb13d25af0b03654ee641b8ab866baaf372785 to 156e78962ee8fccaab2797bd2ed24c4decdd972c
comment:35 Changed 5 months ago by
- Cc dcoudert slabbe added
- Dependencies set to #33487
- Description modified (diff)
comment:36 Changed 5 months ago by
- Description modified (diff)
comment:37 Changed 5 months ago by
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.
comment:38 Changed 5 months ago by
- Commit changed from 156e78962ee8fccaab2797bd2ed24c4decdd972c to f3b8d63f804e76cbd98550c01247cfe48bcdb501
comment:39 follow-up: ↓ 43 Changed 5 months ago by
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.
Changed 5 months ago by
Changed 5 months ago by
comment:40 Changed 5 months ago by
- Commit changed from f3b8d63f804e76cbd98550c01247cfe48bcdb501 to 7d74609a34853901d8f7801914ccb4482149b249
Branch pushed to git repo; I updated commit sha1. New commits:
7d74609 | adding some code from ppl_backend.pyx to cvxpy_backend.{pyx,pxd }
|
comment:41 Changed 5 months ago by
comment:42 Changed 5 months ago by
Thanks! I've committed your additions.
comment:43 in reply to: ↑ 39 Changed 5 months ago by
Replying to gh-sheerluck:
but in
mip.pyx
I gotvalue = 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
comment:44 Changed 5 months ago by
btw is_variable_binary
, is_variable_integer
, is_variable_continuous
should be properly implemented, return True
or return False
is inflexible :)
comment:45 Changed 5 months ago by
- Commit changed from 7d74609a34853901d8f7801914ccb4482149b249 to 193b78ca7b0d3f88992d8f3f5acabea2f92b1021
Branch pushed to git repo; I updated commit sha1. New commits:
193b78c | CVXPYBackend.is_variable_{boolean,integer,continuous}: Implement
|
comment:46 Changed 5 months ago by
- Commit changed from 193b78ca7b0d3f88992d8f3f5acabea2f92b1021 to 92af4da05d1707ae79630b155b73ee06a09b18ca
Branch pushed to git repo; I updated commit sha1. New commits:
92af4da | src/sage/numerical/backends/cvxpy_backend.pyx: Fix up some doctests
|
comment:47 Changed 5 months ago by
- Commit changed from 92af4da05d1707ae79630b155b73ee06a09b18ca to 979a9a91cae134299eb8548f5046733bd91122dd
Branch pushed to git repo; I updated commit sha1. New commits:
979a9a9 | CVXPYBackend.objective_coefficient: Fix up
|
comment:48 Changed 5 months ago by
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
comment:49 Changed 5 months ago by
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! ----------------------------------------------------------------------
Changed 5 months ago by
comment:50 Changed 5 months ago by
Any relation to https://pypi.org/project/mip-cvxpy/?
comment:51 Changed 5 months ago by
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'
comment:52 Changed 5 months ago by
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.
comment:53 Changed 5 months ago by
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)
comment:54 Changed 5 months ago by
- Description modified (diff)
comment:55 Changed 5 months ago by
Workaround: https://github.com/cvxpy/cvxpy/pull/1703
comment:56 Changed 5 months ago by
- Summary changed from Package cvxpy, add SDP backend, add MIP backend to Packages cvxpy, mip-cvxpy, mip, add SDP backend, add MIP backend
comment:57 follow-up: ↓ 59 Changed 5 months ago by
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 :)
comment:58 Changed 5 months ago by
- Commit changed from 979a9a91cae134299eb8548f5046733bd91122dd to 0804514f5a9b2dc5ce8044192dbe668b52abd40b
comment:59 in reply to: ↑ 57 Changed 5 months ago by
Replying to gh-sheerluck:
I realized that
python-mip
does not use my fresh localcbc
I guess one needs to install it as sage -pip install --no-binary :all: mip
comment:60 Changed 5 months ago by
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.
comment:61 follow-up: ↓ 65 Changed 5 months ago by
The build script for this vendored stuff are in https://github.com/coin-or/python-mip/tree/master/scripts
comment:62 Changed 5 months ago by
- Description modified (diff)
comment:63 Changed 5 months ago by
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.
comment:64 Changed 5 months ago by
- Commit changed from 0804514f5a9b2dc5ce8044192dbe668b52abd40b to 3ab590b553d8d6ab59b85dc63d410ec04c1ecdb4
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
|
comment:65 in reply to: ↑ 61 Changed 5 months ago by
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.
comment:66 Changed 5 months ago by
- Commit changed from 3ab590b553d8d6ab59b85dc63d410ec04c1ecdb4 to 444d1d087530e6a75042d580695d73a122459b25
comment:67 follow-up: ↓ 69 Changed 5 months ago by
Back to using Cvxpy/cbc.
The remaining failures are from unimplemented set_variable_type
comment:68 Changed 5 months ago by
- Description modified (diff)
comment:69 in reply to: ↑ 67 Changed 5 months ago by
comment:70 Changed 5 months ago by
- Dependencies changed from #33487 to #33487, #33504
comment:71 Changed 5 months ago by
- Commit changed from 444d1d087530e6a75042d580695d73a122459b25 to d0320b18798fc78957207ef37800d7c6fcfda705
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
|
comment:72 Changed 5 months ago by
- Description modified (diff)
comment:73 Changed 5 months ago by
- Commit changed from d0320b18798fc78957207ef37800d7c6fcfda705 to 6daae939c9ee40f8fa5643a85dc655c067a21525
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
|
comment:74 Changed 5 months ago by
- Commit changed from 6daae939c9ee40f8fa5643a85dc655c067a21525 to 3275a0e7a9a4ef4c8a6d512f6e328922092897d0
comment:75 Changed 5 months ago by
- Commit changed from 3275a0e7a9a4ef4c8a6d512f6e328922092897d0 to 7b30db41cae649e01b64f05f64e9fa4e9c43ddfe
Branch pushed to git repo; I updated commit sha1. New commits:
7b30db4 | build/pkgs/cvxpy/requirements.txt: Update git ref
|
comment:76 Changed 5 months ago by
- Commit changed from 7b30db41cae649e01b64f05f64e9fa4e9c43ddfe to c4462bc75e51c74e1f26e613299faba35541d208
Branch pushed to git repo; I updated commit sha1. New commits:
c4462bc | build/pkgs/mip/SPKG.rst: Add license
|
comment:77 Changed 5 months ago by
- Summary changed from Packages cvxpy, mip-cvxpy, mip, add SDP backend, add MIP backend to Update cylp, add packages cvxpy, mip-cvxpy, mip, add SDP backend, add MIP backend
comment:78 Changed 3 months ago by
- Milestone changed from sage-9.7 to sage-9.8
comment:79 Changed 3 weeks ago by
- Description modified (diff)
comment:80 Changed 3 weeks ago by
- Dependencies changed from #33487, #33504 to #33487, #33504, #34251
- Description modified (diff)
- Summary changed from Update cylp, add packages cvxpy, mip-cvxpy, mip, add SDP backend, add MIP backend to Add SDP backend using CVXPY
- Work issues set to Rebase on #34251
New commits:
build/pkgs/cvxpy: New pip package