Add optional package cvxpy, update cylp, add CVXPY MIP backend #34251

mkoeppe · 2022-07-30T17:48:06Z

(split out from #31962)

We add cvxpy for disciplined convex programming and extensions as an optional package.

cvxpy (home · repo · releases · PyPI)
It can call many backend solvers -- 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 via the scipy cython interface to their vendored HiGHS
supports differentiable programming
PR: CBC.solve_via_data: Work around broken CyLP infeasibility detection cvxpy/cvxpy#1703 - Work around broken CyLP infeasibility detection

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
cvxpy's 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 · repo · PyPI)
ecos (embedded conic solver) (repo · PyPI)
SCS (splitting conic solver) (repo · PyPI)

In addition, osqp's requirements.txt lists:
numpy >= 1.7, scipy >= 0.13.2, qdldl

which adds:

qldl-python (interface to QDLDL, to factor quasi-definite linear systems) (repo · PyPI)

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

See also:

Meta-ticket: Use Python optimization interfaces: CVXPY, SCIP, or-tools, PuLP, Pyomo, cylp... #26511 Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...
Package ortools #33493 package ortools - provides some more backends

Follow-ups:

Upgrade optional package cbc to 2.10.x, remove sage_numerical_backends_coin #30644 Remove sage_numerical_backends_coin, Upgrade optional package cbc to 2.10.7

Depends 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

The text was updated successfully, but these errors were encountered:

mkoeppe · 2022-07-30T17:55:46Z

Branch: u/mkoeppe/add_optional_package_cvxpy

mkoeppe · 2022-07-30T17:56:54Z

Commit: 76d1208

mkoeppe · 2022-07-30T17:56:54Z

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`

mkoeppe · 2022-07-30T17:56:54Z

Changed author from Matthias Koeppe to Matthias Koeppe, Andrey Belgorodski

sagetrac-git · 2022-07-30T18:33:35Z

Changed commit from 76d1208 to 7d4dccb

sagetrac-git · 2022-07-30T18:33:35Z

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`

sagetrac-git · 2022-07-30T19:02:24Z

Changed commit from 7d4dccb to aab359f

sagetrac-git · 2022-07-30T19:02:24Z

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

`aab359f`	`build/pkgs/{ecos,osqp}_python: Renamed from ecos, osqp`

sagetrac-git · 2022-07-30T19:10:08Z

Changed commit from aab359f to 6d039ae

sagetrac-git · 2022-07-30T19:10:08Z

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

`468b2c5`	`build/pkgs/ecos_python/dependencies: Add suitesparse`
`6d039ae`	`build/pkgs/{ecos,osqp}_python: Use --no-build-isolation`

sagetrac-git · 2022-07-30T20:26:55Z

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

`763985d`	`src/sage/numerical/backends/cvxpy_backend.pyx: Make doctests pass`

sagetrac-git · 2022-07-30T20:26:55Z

Changed commit from 6d039ae to 763985d

sagetrac-git · 2022-07-30T20:57:07Z

Changed commit from 763985d to a079e6e

sagetrac-git · 2022-07-30T20:57:07Z

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

`a079e6e`	`build/pkgs/cylp/spkg-install.in: Use --no-build-isolation`

sagetrac-git · 2022-07-30T21:21:52Z

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`

sagetrac-git · 2022-07-30T21:21:52Z

Changed commit from a079e6e to 9f9b346

sheerluck · 2022-07-30T21:22:47Z

comment:16

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`

mkoeppe · 2022-07-30T21:24:00Z

comment:17

Here on this ticket, there's no SDP solver backend

mkoeppe · 2022-07-30T21:25:10Z

comment:18

We had that on #31962, but I have split out the present ticket

Kerl13 · 2022-10-02T16:14:46Z

Attachment: cvxpy.log

Kerl13 · 2022-10-02T16:16:58Z

comment:58

After rebasing on develop, I now get the attached errors when running sage -t --long --random-seed=262306895609334379547192037378099413502 src/sage/numerical/backends/cvxpy_backend.pyx

Don't know why the segfault occurred before but the new errors look minor now

sagetrac-git · 2022-10-02T22:43:17Z

Changed commit from c9f0b39 to 539c970

sagetrac-git · 2022-10-02T22:43:17Z

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

`55fc4fb`	`build/pkgs/{cvxpy,scs,osqp_python,ecos_python,qdldl_python}: Add distros/conda.txt`
`18e7434`	`build/pkgs/osqp_python/dependencies: Add cmake`
`11e4de8`	`build/pkgs/ecos_python/dependencies: Remove suitesparse`
`9a1eeec`	`build/pkgs/cylp/SPKG.rst: Add more detailed license info`
`b9c92ae`	`src/sage/numerical/backends/cvxpy_backend.pyx: Add doc for init args`
`5b840bd`	`src/sage/numerical/backends: Remove unnecessary imports, muffle unused variable warnings`
`7132302`	`src/sage/numerical/backends: Fix copy-pasted typos in documentation (binary/continuous/integer)`
`b5cbc5a`	`src/sage/numerical/backends/cvxpy_backend.pyx: Add to doc`
`83ce468`	`build/pkgs/scs/spkg-install.in: Use --no-build-isolation`
`539c970`	`src/sage/numerical/backends/cvxpy_backend.pyx: Update doctest output for bounds methods`

sagetrac-git · 2022-11-15T08:52:55Z

Changed commit from 539c970 to 7346fd1

sagetrac-git · 2022-11-15T08:52:55Z

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

`98c38c1`	`Merge tag '9.8.beta3' into t/34251/add_optional_package_cvxpy`
`7211f42`	`build/pkgs/cvxpy: Update to 1.2.2`
`7346fd1`	`build/pkgs/scs: Update to 3.2.2`

mkoeppe · 2022-11-16T04:51:37Z

comment:61

Tests at https://github.com/mkoeppe/sage/actions/runs/3476460100, https://github.com/mkoeppe/sage/actions/runs/3476460090

sheerluck · 2023-01-16T18:48:14Z

comment:63

we need this ticket for #31962

we need #31962 for #32053

mkoeppe · 2023-01-17T17:52:40Z

comment:64

We'll have to merge this with #21003, which touches the same files and will likely be in the next beta

sagetrac-git · 2023-01-19T06:46:09Z

Changed commit from 7346fd1 to 666e973

sagetrac-git · 2023-01-19T06:46:09Z

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

`666e973`	`Merge tag '9.8.beta7' into t/34251/add_optional_package_cvxpy`

sagetrac-git · 2023-01-19T07:28:52Z

Changed commit from 666e973 to 7ff5766

sagetrac-git · 2023-01-19T07:28:52Z

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

`ba9fcbc`	`build/pkgs/cvxpy: Update to 1.3.0`
`7515564`	`build/pkgs/osqp_python: Update to 0.6.2.post8`
`91cbc21`	`build/pkgs/ecos_python: Update to 2.0.12`
`7ff5766`	`build/pkgs/qdldl_python: Update to 0.1.5.post3`

sheerluck · 2023-01-20T18:13:23Z

comment:68

without this ticket I can do this

sage: from sage.combinat.designs.database import OA_10_469
sage: OA = OA_10_469()
sage: print(len(OA))
219961

this ticket just hangs (probably O(n²) while p.set_objective(p.sum(b[fe] for fe in L)), looks like every b[fe] creates new cvxpy.Problem with 1, 2, 3 ... 900 constraints)

mkoeppe · 2023-01-20T22:20:30Z

comment:69

Yes, we should definitely improve this

dimpase · 2023-01-30T11:43:16Z

comment:70

Replying to @sheerluck:

without this ticket I can do this
sage: from sage.combinat.designs.database import OA_10_469
sage: OA = OA_10_469()
sage: print(len(OA))
219961
this ticket just hangs (probably O(n²) while p.set_objective(p.sum(b[fe] for fe in L)), looks like every b[fe] creates new cvxpy.Problem with 1, 2, 3 ... 900 constraints)

I don't see where in OA_10_469() any optimisation problem is set up. It seems to be a simple
combinatorial construction, no solvers involved. OA is just a list.

sheerluck · 2023-01-30T13:08:47Z

comment:71

Replying to Dima Pasechnik:

I don't see where in OA_10_469() any optimisation problem is set up.

database.py:1693 -> 
    matrix = _reorder_matrix(symmetric_design)

orthogonal_arrays_build_recursive.py:1189 ->
    matching = g.matching(algorithm="LP")

graph.py:4210 ->
    p = MixedIntegerLinearProgram(maximization=True, solver=solver)

sheerluck · 2023-02-07T14:04:58Z

and now I can link a range of lines

mkoeppe · 2023-02-13T19:45:46Z

Removed branch from issue description; replaced by PR #35120

mkoeppe · 2023-02-13T19:47:36Z

this ticket just hangs (probably O(n2) while p.set_objective(p.sum(b[fe] for fe in L)), looks like every b[fe] creates new cvxpy.Problem with 1, 2, 3 ... 900 constraints)

I'd suggest that we improve performance in follow-up PRs

### 📚 Description Fixes #34251    ### 📝 Checklist    - [x] I have made sure that the title is self-explanatory and the description concisely explains the PR. - [x] I have linked an issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies   URL: #35120 Reported by: Matthias Köppe Reviewer(s): Dima Pasechnik

mkoeppe added this to the sage-9.7 milestone Jul 30, 2022

mkoeppe added c: packages: optional labels Jul 30, 2022

mkoeppe changed the title ~~Add optional package cvxpy~~ Add optional package cvxpy, update cylp Jul 30, 2022

This comment has been minimized.

Sign in to view

mkoeppe changed the title ~~Add optional package cvxpy, update cylp~~ Add optional package cvxpy, update cylp, add CVXPY MIP backend Jul 30, 2022

This comment has been minimized.

Sign in to view

mkoeppe added the s: needs review label Jul 30, 2022

This comment has been minimized.

Sign in to view

mkoeppe modified the milestones: sage-9.8, sage-9.9 Dec 31, 2022

mkoeppe added s: needs review and removed s: needs work labels Jan 19, 2023

Kerl13 mentioned this issue Sep 14, 2022

Usainboltz package: fast Boltzmann random generation of tree-like structures #27526

Open

seblabbe mentioned this issue Dec 31, 2022

Upgrade optional package cbc to 2.10.x, remove sage_numerical_backends_coin #30644

Open

sagetrac-tmonteil mannequin mentioned this issue Jan 29, 2023

Lot of broken doctests with Coin #33929

Closed

mkoeppe removed the s: needs review label Feb 13, 2023

vbraun closed this as completed in #35120 Mar 26, 2023

Add optional package cvxpy, update cylp, add CVXPY MIP backend #34251

Add optional package cvxpy, update cylp, add CVXPY MIP backend #34251

Comments

mkoeppe commented Jul 30, 2022 • edited Loading

mkoeppe commented Jul 30, 2022

This comment has been minimized.

mkoeppe commented Jul 30, 2022

mkoeppe commented Jul 30, 2022

mkoeppe commented Jul 30, 2022

This comment has been minimized.

sagetrac-git mannequin commented Jul 30, 2022

sagetrac-git mannequin commented Jul 30, 2022

This comment has been minimized.

sagetrac-git mannequin commented Jul 30, 2022

sagetrac-git mannequin commented Jul 30, 2022

sagetrac-git mannequin commented Jul 30, 2022

sagetrac-git mannequin commented Jul 30, 2022

sagetrac-git mannequin commented Jul 30, 2022

sagetrac-git mannequin commented Jul 30, 2022

This comment has been minimized.

sagetrac-git mannequin commented Jul 30, 2022

sagetrac-git mannequin commented Jul 30, 2022

sagetrac-git mannequin commented Jul 30, 2022

sagetrac-git mannequin commented Jul 30, 2022

sheerluck commented Jul 30, 2022

mkoeppe commented Jul 30, 2022

mkoeppe commented Jul 30, 2022

Kerl13 commented Oct 2, 2022

Kerl13 commented Oct 2, 2022

sagetrac-git mannequin commented Oct 2, 2022

sagetrac-git mannequin commented Oct 2, 2022

sagetrac-git mannequin commented Nov 15, 2022

sagetrac-git mannequin commented Nov 15, 2022

mkoeppe commented Nov 16, 2022

sheerluck commented Jan 16, 2023

mkoeppe commented Jan 17, 2023

sagetrac-git mannequin commented Jan 19, 2023

sagetrac-git mannequin commented Jan 19, 2023

sagetrac-git mannequin commented Jan 19, 2023

sagetrac-git mannequin commented Jan 19, 2023

sheerluck commented Jan 20, 2023

mkoeppe commented Jan 20, 2023

dimpase commented Jan 30, 2023

sheerluck commented Jan 30, 2023

sheerluck commented Feb 7, 2023

mkoeppe commented Feb 13, 2023

mkoeppe commented Feb 13, 2023

mkoeppe commented Jul 30, 2022 •

edited

Loading