Closed mkoeppe closed 1 year ago
Description changed:
---
+++
@@ -1 +1,2 @@
(split out from #31962)
+
Last 10 new commits:
cff440e | adding some code from ppl_backend.pyx to cvxpy_backend.{pyx,pxd} |
8c6f323 | CVXPYBackend.is_variable_{boolean,integer,continuous}: Implement |
b497afc | src/sage/numerical/backends/cvxpy_backend.pyx: Fix up some doctests |
942d2ed | CVXPYBackend.objective_coefficient: Fix up |
5a5ab69 | build/pkgs/cylp: Add patch from https://github.com/coin-or/CyLP/pull/150 |
75f867d | build/pkgs/cvxpy: Use https://github.com/cvxpy/cvxpy/pull/1707 |
1fb2926 | build/pkgs/cylp: Add another commit from https://github.com/coin-or/CyLP/pull/150 |
4fd763a | src/sage/numerical/backends/cvxpy_backend_test.py: New |
8e482be | build/pkgs/cylp: Update to 0.91.5, remove patches |
76d1208 | build/pkgs/cvxpy/requirements.txt: Update git ref |
Changed author from Matthias Koeppe to Matthias Koeppe, Andrey Belgorodski
Description changed:
---
+++
@@ -1,2 +1,60 @@
(split out from #31962)
+We add `cvxpy` for disciplined convex programming and extensions as an optional package.
+
+- 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/))
+- 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)
+- PR: https://github.com/cvxpy/cvxpy/pull/1703 - Work around broken CyLP infeasibility detection
+
+When `cylp` is installed (from #33487, upgraded here), a new solver backend `"CVXPY/CBC"` becomes the default (unless Gurobi or CPLEX are available). This replaces
+
+
+Details about dependencies: Requirements listed in
+cvxpy's [setup.py](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"],
+```
+
+So the new dependencies are:
+
+- osqp (operator splitting quadratic program)
+ ([home](https://osqp.org/)
+ · [repo](https://github.com/osqp/osqp-python)
+ · [PyPI](https://pypi.org/project/osqp/))
+- ecos (embedded conic solver)
+ ([repo](https://github.com/embotech/ecos-python)
+ · [PyPI](https://pypi.org/project/ecos/))
+- SCS (splitting conic solver)
+ ([repo](https://github.com/bodono/scs-python)
+ · [PyPI](https://pypi.org/project/scs/))
+
+In addition, osqp's [requirements.txt](https://github.com/osqp/osqp-python/blob/master/requirements.txt) lists:
+`numpy >= 1.7`, `scipy >= 0.13.2`, `qdldl`
+
+which adds:
+
+- qldl-python (interface
+ to [QDLDL](https://github.com/osqp/qdldl), to factor quasi-definite linear systems)
+ ([repo](https://github.com/osqp/qdldl-python)
+ · [PyPI](https://pypi.org/project/qdldl/))
+
+Finally, qldl-python depends on pybind11 (already an SPKG)
+
+See also:
+- #26511 Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...
+- #33493 package ortools - provides some more backends
+
+Follow-ups:
+- #30644 Remove `sage_numerical_backends_coin`, Upgrade optional package cbc to 2.10.7
+
Branch pushed to git repo; I updated commit sha1. New commits:
7d4dccb | build/pkgs/cvxpy: Make it a normal package, add dependencies qdldl_python, osqp, scs, ecos |
Description changed:
---
+++
@@ -11,7 +11,7 @@
- supports [differentiable programming](https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients)
- PR: https://github.com/cvxpy/cvxpy/pull/1703 - Work around broken CyLP infeasibility detection
-When `cylp` is installed (from #33487, upgraded here), a new solver backend `"CVXPY/CBC"` becomes the default (unless Gurobi or CPLEX are available). This replaces
+When `cylp` is installed (from #33487, upgraded here), a new solver backend `"CVXPY/CBC"` becomes the default (unless Gurobi or CPLEX are available). This replaces the backend provided by `sage_numerical_backend_coin`
Details about dependencies: Requirements listed in
Branch pushed to git repo; I updated commit sha1. New commits:
aab359f | build/pkgs/{ecos,osqp}_python: Renamed from ecos, osqp |
Branch pushed to git repo; I updated commit sha1. New commits:
763985d | src/sage/numerical/backends/cvxpy_backend.pyx: Make doctests pass |
Description changed:
---
+++
@@ -11,7 +11,9 @@
- supports [differentiable programming](https://www.cvxpy.org/tutorial/advanced/index.html#sensitivity-analysis-and-gradients)
- PR: https://github.com/cvxpy/cvxpy/pull/1703 - Work around broken CyLP infeasibility detection
-When `cylp` is installed (from #33487, upgraded here), a new solver backend `"CVXPY/CBC"` becomes the default (unless Gurobi or CPLEX are available). This replaces the backend provided by `sage_numerical_backend_coin`
+We add a new MIP backend `solver="CVXPY"`. Using `solver="CVXPY/ECOS"`, `solver="CVXPY/GLPK"`, etc., CVXPY can be asked to use a specific solver.
+
+When also `cylp` is installed (from #33487, upgraded here), the new solver backend `"CVXPY/CBC"` becomes the default (unless Gurobi or CPLEX are available), thus replacing the similar functionality of the CBC backend provided by `sage_numerical_backend_coin`.
Details about dependencies: Requirements listed in
Branch pushed to git repo; I updated commit sha1. New commits:
a079e6e | build/pkgs/cylp/spkg-install.in: Use --no-build-isolation |
Branch pushed to git repo; I updated commit sha1. New commits:
9f9207a | src/sage/numerical/backends/cvxpy_backend.pyx: Store constraint names |
7b1ee3f | src/sage/numerical/backends/cvxpy_backend.pyx: Use our column names when no name is given |
cbbc6ab | src/sage/numerical/backends/cvxpy_backend.pyx: Convert lower, upper variable bounds to float |
9f9b346 | src/sage/combinat/matrices/dancing_links.pyx: Make doctest more flexible |
I am not sure, but it feels like if default_sdp_solver()
is 'Cvxopt' then the tests in cvxpy_sdp_backend.py
are broken. And if default_sdp_solver()
is 'Cvxpy' then the tests in cvxopt_backend.pyx
are broken. Sorry if that is irrelevant to this ticket.
New commits:
9f9207a | src/sage/numerical/backends/cvxpy_backend.pyx: Store constraint names |
7b1ee3f | src/sage/numerical/backends/cvxpy_backend.pyx: Use our column names when no name is given |
cbbc6ab | src/sage/numerical/backends/cvxpy_backend.pyx: Convert lower, upper variable bounds to float |
9f9b346 | src/sage/combinat/matrices/dancing_links.pyx: Make doctest more flexible |
Here on this ticket, there's no SDP solver backend
We had that on #31962, but I have split out the present ticket
Branch pushed to git repo; I updated commit sha1. New commits:
a9eaae5 | tox.ini, build/bin/write-dockerfile.sh: Add 'tox -e docker-...-incremental' |
b9bfbf9 | tox.ini: Add comment |
4c0d7f5 | tox.ini: Use FROM_DOCKER_REPOSITORY |
a07874d | build/bin/write-dockerfile.sh: In incremental build, keep logs |
ae269d1 | tox.ini (docker-incremental): Do not include '-incremental' in the Docker image name |
b23439d | Merge #34228 |
2c8373e | src/sage/combinat/matrices/dancing_links.pyx: Make doctest more flexible (fixup) |
Dependencies: #34228
I have yet to package this stuff for Gentoo (I already did cylp). I am going to have a closer look for obvious mistakes shortly.
I was wondering about the dependency of qdldl on cmake. It vendors amd from suitesparse and build it with cmake. Lovely, but unvendoring it is out of scope of the ticket.
That's the only remark on the package added. They all look good, I'll have to test the sage bits later.
Branch pushed to git repo; I updated commit sha1. New commits:
eeec3e9 | build/pkgs/{cvxpy,scs,osqp_python,ecos_python,qdldl_python}: Add distros/conda.txt |
Added conda distro information. There doesn't appear to be a conda-forge package for cylp, so that will have to be taken via pip (#33613, needs review)
Note for other packagers: qdldl-python include suitesparse's amd sources and qdldl's c sources. The vendored amd source are customised to use the vendored qdldl. I don't recommend trying to unvendor. osqp-python similarly vendor osqp but it looks like it could be unvendored but I am not going to try that just yet.
osqp-python needs cmake, just like qdldl-python https://github.com/osqp/osqp-python/blob/master/setup.py#L222 so it must be added to the dependencies
file.
I very much doubt that ecos_python depend on suitesparse. It vendors its own copies of amd, ldl and suitesparse_config. And by the look of it there may be some customisation by macro definition and the copies themselves are ancient (more than 4 years old, possibly forked more than 8 years ago).
osqp also has its bits of suitesparse (amd+suitesparse_config) and so does scs (amd+suitesparse_config again). All at various stage of ageing. And the c version of qdldl shows up everywhere.
I agree with your analysis. I've made these changes
Waiting for review
Some test do not pass, most notably:
sage -t --long --random-seed=262306895609334379547192037378099413502 src/sage/numerical/backends/cvxpy_backend.pyx
Killed due to segmentation fault
**********************************************************************
Tests run before process (pid=287829) failed:
sage: import cvxpy ## line 42 ##
sage: cvxpy.installed_solvers() # random ## line 43 ##
['CVXOPT', 'ECOS', 'ECOS_BB', 'GLPK', 'GLPK_MI', 'OSQP', 'SCIPY', 'SCS']
sage: p = MixedIntegerLinearProgram(solver="CVXPY"); p.solve() ## line 47 ##
0.0
sage: p = MixedIntegerLinearProgram(solver="CVXPY/OSQP"); p.solve() ## line 52 ##
0.0
sage: p = MixedIntegerLinearProgram(solver="CVXPY/ECOS"); p.solve() ## line 54 ##
0.0
sage: p = MixedIntegerLinearProgram(solver="CVXPY/SCS"); p.solve() ## line 56 ##
0.0
sage: p = MixedIntegerLinearProgram(solver="CVXPY/SciPy/HiGHS"); p.solve() ## line 58 ##
0.0
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 90 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 98 ##
sage: p = get_solver(solver="CVXPY") ## line 99 ##
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 100 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 141 ##
sage: p = MixedIntegerLinearProgram(solver="CVXPY") ## line 142 ##
sage: b = p.new_variable() ## line 143 ##
sage: p.add_constraint(b[1] + b[2] <= 6) ## line 144 ##
sage: p.set_objective(b[1] + b[2]) ## line 145 ##
sage: cp = copy(p.get_backend()) ## line 146 ##
sage: cp.solve() ## line 147 ##
0
sage: cp.get_objective_value() # abs tol 1e-7 ## line 149 ##
5.999999982049109
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 151 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 206 ##
sage: p = get_solver(solver="CVXPY") ## line 207 ##
sage: p.ncols() ## line 208 ##
0
sage: p.add_variable() ## line 210 ##
0
sage: p.ncols() ## line 212 ##
1
sage: p.add_variable(continuous=True, integer=True) ## line 214 ##
sage: p.add_variable(name='x',obj=1) ## line 218 ##
1
sage: p.col_name(1) ## line 220 ##
'x'
sage: p.objective_coefficient(1) ## line 222 ##
1.0
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 224 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 287 ##
sage: p = get_solver(solver="CVXPY") ## line 288 ##
sage: p.set_verbosity(2) ## line 289 ##
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 290 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 313 ##
sage: p = get_solver(solver="CVXPY") ## line 314 ##
sage: p.add_variables(5) ## line 315 ##
4
sage: index = p.nrows() ## line 317 ##
sage: p.add_linear_constraint( zip(range(5), range(5)), 2, 2) ## line 318 ##
sage: p.row(index) ## line 319 ##
([1, 2, 3, 4], [1, 2, 3, 4])
sage: p.row_bounds(index) ## line 321 ##
(2, 2)
sage: p.add_linear_constraint( zip(range(5), range(5)), 1, 1, name='foo') ## line 323 ##
sage: p.row_name(1) ## line 324 ##
'constraint_1'
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 326 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 375 ##
sage: p = get_solver(solver="CVXPY") ## line 376 ##
sage: p.ncols() ## line 377 ##
0
sage: p.nrows() ## line 379 ##
0
sage: p.add_linear_constraints(5, 0, None) ## line 381 ##
sage: p.add_col(list(range(5)), list(range(5))) ## line 382 ##
sage: p.nrows() ## line 386 ##
5
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 388 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 412 ##
sage: p = get_solver(solver="CVXPY") ## line 413 ##
sage: p.add_variables(5) ## line 414 ##
4
sage: p.set_objective([1, 1, 2, 1, 3]) ## line 416 ##
sage: [p.objective_coefficient(x) for x in range(5)] ## line 417 ##
[1.0, 1.0, 2.0, 1.0, 3.0]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 419 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 444 ##
sage: p = get_solver(solver="CVXPY") ## line 445 ##
sage: p.is_maximization() ## line 446 ##
True
sage: p.set_sense(-1) ## line 448 ##
sage: p.is_maximization() ## line 449 ##
False
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 451 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 472 ##
sage: p = get_solver(solver="CVXPY") ## line 473 ##
sage: p.add_variable() ## line 474 ##
0
sage: p.objective_coefficient(0) ## line 476 ##
0.0
sage: p.objective_coefficient(0, 2) ## line 478 ##
sage: p.objective_coefficient(0) ## line 479 ##
2
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 481 ##
0
sage: from sage.numerical.backends.generic_backend import get_solver ## line 506 ##
sage: p = get_solver(solver="CVXPY") ## line 507 ##
sage: p.add_linear_constraints(5, 0, None) ## line 508 ##
sage: p.add_col(list(range(5)), list(range(5))) ## line 509 ##
sage: p.solve() ## line 513 ##
0
sage: p.objective_coefficient(0,1) ## line 515 ##
sage: p.solve() ## line 516 ##
But also some seemingly unrelated stuff:
sage -t --long --random-seed=262306895609334379547192037378099413502 src/sage/doctest/test.py # 2 doctests failed
sage -t --long --random-seed=262306895609334379547192037378099413502 src/sage/interfaces/octave.py # 1 doctest failed
sage -t --long --random-seed=262306895609334379547192037378099413502 src/sage/numerical/backends/cvxpy_backend.pyx # Killed due to segmentation fault
sage -t --long --random-seed=262306895609334379547192037378099413502 src/sage/plot/plot3d/tachyon.py # 2 doctests failed
sage -t --long --random-seed=262306895609334379547192037378099413502 src/sage/rings/integer.pyx # 1 doctest failed
The GH CI also reports coverage-related issues, which I think will be fixed by rebasing the branch on develop
I'm not familiar with the numerical backend logic yet, so it will take a bit more time to review. Here are few first remarks on the new packages:
cvxpy requires numpy to run, but also to build, shouldn't numpy be an order dependency as well?
Same question for ecos and scs.
The pyproject.toml file for cvxpy 1.2.1 specifies an upper bound for numpy that we don't comply with. I saw your comment in spkg-install.in about this. Are you sure it's okay to ignore it? What are the implication of setting --no-build-isolation
there?
Also, why adding this flag in osqp's spkg-install.in
file as well? And ecos?
qdldl requires pybind11 at build time, shouldn't it be an order dependency?
cylp is released under EPL version 2 (not just EPL)
More importantly, EPL (version 1 and 2) are incompatible with GPLv3 according to https://www.gnu.org/licenses/license-list.html#EPL2 . Cylp should be should explicitly double-licenced to be compatible with GPL.
I'm not an expert of the numerical backend stuff, but here are a few remarks on the code.
Aside from that, I've been able to run some examples from https://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html without an issue. So I guess it looks good!
file generic_backend.pyx, line 1650:
from sage.numerical.backends.cvxpy_backend import CVXPYBackend
It is possible to avoid the Unused entry 'CVXPYBackend'
cython warning using:
__import__("sage.numerical.backends.cvxpy_backend.CVXPYBackend")
file generic_backend.pyx, line 1824: the partial
function is imported but unused
In CVXPYBackend.cinit: the arguments of the __cinit__
method of CVXPYBackend are not documented. In particular, I have no idea what cvxpy_solver_args
might be. Also I don't get why base_ring
is an argument if the only legal value for it is RDF
.
file cvxpy_backend.pyx, line 114:
import cvxpy as cp
cvxpy_solver = getattr(cp, cvxpy_solver)
cvxpy is already imported at the top of the module, you could replace these two lines by:
cvxpy_solver = getattr(cvxpy, cvxpy_solver)
file cvxpy_backend.pyx, line 152, in __copy__
:
why type(self)(base_ring=...)
and not simply CVXPYBackend(base_ring=...)
.
In cvxpy_backend.pyx I get the following cython warning:
[cython] FutureWarning: Cython directive 'language_level' not set, using 2 for now
(Py2). This will change in a later release!
Shouldn't we write # cython: language_level = 3
at the top of every new cython file?
file cvxpy_backend.pyx, line 188:
- ``binary`` - ``True`` if the variable is binary (default: ``False``).
- ``continuous`` - ``True`` if the variable is binary (default: ``True``).
- ``integer`` - ``True`` if the variable is binary (default: ``False``).
This looks like the same docstring have been copy-pasted but not modified. This problem seems present in all the backends, I guess because it comes from the generic backend.
CVXPYBackend.set_verbosity: maybe the docstring for set_verbosity
should state that this method is only here for compatibility and ignores its argument?
CVXPYBackend.solve: the .solve
method in CVXPYBackend only has examples where solving fails, maybe it would be nice to have an example of normal usage of the function, where it succeeds?
Reviewer: MartinPepin
Replying to Martin Pépin:
I'm not familiar with the numerical backend logic yet, so it will take a bit more time to review. Here are few first remarks on the new packages:
- cvxpy requires numpy to run, but also to build, shouldn't numpy be an order dependency as well?
"order-only prerequisites" are strictly weaker than normal prerequisites, so one does not have to declare both. https://www.gnu.org/software/make/manual/html_node/Prerequisite-Types.html
Replying to Martin Pépin:
- cylp is released under EPL version 2 (not just EPL)
- More importantly, EPL (version 1 and 2) are incompatible with GPLv3 according to https://www.gnu.org/licenses/license-list.html#EPL2 . Cylp should be should explicitly double-licenced to be compatible with GPL.
Thanks, I've added something along these lines. We actually had a discussion on this problematic situation in #26511 not too long ago.
New commits:
effa9db | Merge tag '9.7' into t/34251/add_optional_package_cvxpy |
0bb4309 | build/pkgs/cylp/SPKG.rst: Add more detailed license info |
Replying to Martin Pépin:
- The pyproject.toml file for cvxpy 1.2.1 specifies an upper bound for numpy that we don't comply with. I saw your comment in spkg-install.in about this. Are you sure it's okay to ignore it?
Note that the documentation https://github.com/cvxpy/cvxpy#installation does not mention such upper bounds.
In https://github.com/cvxpy/cvxpy/blob/master/pyproject.toml, they are following numpy's recommendations, which are (to my understanding) motivated by setting a standard for compatibility of wheels, by building platform wheels against the minimum supported numpy version for each Python version (and platform). This is irrelevant for the Sage distribution.
What are the implication of setting
--no-build-isolation
there?
We sacrifice a small bit of build robustness that comes with the build isolation.
Using --no-build-isolation
used to be the default for all packages in Sage until I changed it in #33789 (in the Sage 9.7 cycle).
Thanks for the careful reading of the docstrings! I'll make changes later today.
Changed reviewer from MartinPepin to Martin Pépin
Replying to Martin Pépin:
In cvxpy_backend.pyx I get the following cython warning:
[cython] FutureWarning: Cython directive 'language_level' not set, using 2 for now (Py2). This will change in a later release!
Shouldn't we write
# cython: language_level = 3
at the top of every new cython file?
Since #33544, we set this globally (in src/sage_setup/cython_options.py
).
(split out from #31962)
We add
cvxpy
for disciplined convex programming and extensions as an optional package.We add a new MIP backend
solver="CVXPY"
. Usingsolver="CVXPY/ECOS"
,solver="CVXPY/GLPK"
, etc., CVXPY can be asked to use a specific solver.When also
cylp
is installed (from #33487, upgraded here), the new solver backend"CVXPY/CBC"
becomes the default (unless Gurobi or CPLEX are available), thus replacing the similar functionality of the CBC backend provided bysage_numerical_backend_coin
.Details about dependencies: Requirements listed in cvxpy's setup.py:
So the new dependencies are:
In addition, osqp's requirements.txt lists:
numpy >= 1.7
,scipy >= 0.13.2
,qdldl
which adds:
Finally, qldl-python depends on pybind11 (already an SPKG)
See also:
26511 Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...
33493 package ortools - provides some more backends
Follow-ups:
30644 Remove
sage_numerical_backends_coin
, Upgrade optional package cbc to 2.10.7Depends on #34228
CC: @dimpase @yuan-zhou @sheerluck @dcoudert @seblabbe @maxale @kiwifb @isuruf @tkralphs
Component: packages: optional
Author: Matthias Koeppe, Andrey Belgorodski
Reviewer: Martin Pépin
Issue created by migration from https://trac.sagemath.org/ticket/34251