Opened 3 years ago
Last modified 6 weeks ago
#26511 new enhancement
Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.5 |
Component: | numerical | Keywords: | |
Cc: | a.mason@…, gh-jiawei-wang-ucd, yzh, dimpase, dcoudert, tmonteil, fbissey | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The purpose of this ticket is to
- connect SageMath to interfaces to optimization solvers that are maintained outside of the Sage project,
- integrate the related developer and user communities.
Status quo in Sage:
- Frontend class
MixedIntegerLinearProgram
- mutable (can call
add_constraint
,set_integer
,new_variable
etc. and then re-solve) - solver-independent and solver-specific parameters (solver_parameter)
- widely used in Sage code
MIPVariable
- indexed by arbitrary objects- some connections to Polyhedron class and to InteractiveLPProblem (didactical code)
- mutable (can call
- Backends, using Cython, with varying degrees of implementation quality
- GLPK backend - complete, includes support for tableau data and GLPK's exact rational mode
- COIN backend - very basic, no support for setting solver parameters such as time limit
- CPLEX backend, Gurobi backend, CVXOPT backend, PPL backend
- InteractiveLP backend - basic, provide LP only for algebraic LPs
- Very small developer community
Tickets:
- #28175 Move sage optimization backends to separate Cython packages to remove
OptionalExtension
problems - Template for minimal Python-based backends (
interactivelp_backend.pyx
is implemented in Cython just because a Cython template was available) - Replace basic Cython-based COIN backend by full-featured PuLP backend (gives access to many solvers)
- #19219 MILP: Add CyLP backend -- Replace basic Cython-based COIN backend by full-featured cylp backend (gives detailed access to CLP, including tableau data)
- PuLP backend implementation using Sage backends... to make exact backends such as InteractiveLP, PPL backend available to PuLP frontend users
- can PuLP handle non-floating point data (for example for exact computation over rationals or number fields if the backend allows it?
- this could be added to PuLP, rather than to Sage.
- Pyomo backend implementation using Sage backends... to make exact backends available to Pyomo frontend users
- see above
- Check feasibility of replacing front end
MixedIntegerLinearProgram
by PuLP frontend or Pyomo frontend- can PuLP handle Sage's number types such as RDF and ZZ?
- can Pyomo handle Sage's number types such as RDF and ZZ?
Related:
- #20302 Meta-ticket: Improvements to
MixedIntegerLinearProgram
, its backends, andInteractiveLinearProgram
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References:
Key Python software (solver-independent):
cvxpy - #31962
PuLP
- https://github.com/coin-or/pulp
- Installation with
sage -pip install pulp
works
- Frontend: a basic modeling system
- example: https://github.com/coin-or/pulp/blob/master/examples/WhiskasModel1.py
- need to compare its capabilities with the sage frontend
- Backends: some API-based and some file-based interfaces to various solvers, including:
- COIN_CMD (COIN CBC via command line),
- COINMP_DLL (CBC via COINMP C library API),
- YAPOSIB (Python interface to COIN OSI, see below),
- see solvers.py
- PuLP is currently looking for a co-maintainer (https://github.com/coin-or/pulp/issues/183)
Pyomo
- http://www.pyomo.org/
- installation with
sage -pip install pyomo
works - some file-based, some API-based interfaces (direct/persistent) - see solvers directory
- big system, under active development
YAPOSIB - Python interface to COIN OSI, using Boost::Python
- https://github.com/coin-or/yaposib
- Installation with
sage -i boost && sage -pip install yaposib
works - incompatible open source license - EPL 1.0
- therefore we cannot use it as the basis for our solver-independent code
- could still be useful to be used via PuLP for solvers that don't have a direct PuLP backend
Python MIP (Mixed-Integer Linear Programming) Tools (new 2018)
- https://pypi.org/project/mip/
- https://github.com/coin-or/python-mip
- Eclipse Public License 2.0 (considered GPL-incompatible https://www.gnu.org/licenses/license-list.en.html#GPLCompatibleLicenses)
- requires Python 3.5 or newer
PICOS - a user friendly Python API to several conic and integer programming solvers, very much like YALMIP or CVX under MATLAB.
- runs under both Python 2 and Python 3
- GNU GPL v3
- https://gitlab.com/picos-api/picos
- https://pypi.org/project/PICOS/
Key Python software (solver-dependent):
scipy.optimize
- #32282 Add LP solver backends for HiGHS via scipy.optimize.linprog
GLPK
- it looks like https://github.com/biosustain/swiglpk/releases is the best maintained. Excluding sage and cvxopt.
- see https://en.wikibooks.org/wiki/GLPK/Python for a list of other glpk bindings
cylp
- CyLP is a Python interface to COIN-OR’s Linear and mixed-integer program solvers (CLP, CBC, and CGL). CyLP’s unique feature is that you can use it to alter the solution process of the solvers from within Python. For example, you may define cut generators, branch-and-bound strategies, and primal/dual Simplex pivot rules completely in Python.
- is it maintained?? https://github.com/coin-or/CyLP/issues
cbcpy (new August 2019 according to https://pypi.org/project/cbcpy/)
- upstream devs for cbc have published their own python interface https://git.patrikdufresne.com/pdsl/cbcpy
- the fact that it uses swig may be an obstacle for immediate inclusion
Gurobi, CPLEX
- they come with their own standard Python APIs, which we could use instead of building our own cython interface
- related: #28175 - where we remove these cython modules from sagelib and ship them in separate packages instead
python-qsoptex
PySCIPOpt
Other relevant software
- PaPILO: Parallel Presolve for Integer and Linear Optimization (https://github.com/scipopt/papilo/) - LGPL license, C++ library; used in SCIP
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Possible integration routes via Julia
MathOptInterface
- https://arxiv.org/pdf/2002.03447.pdf
Change History (27)
comment:1 Changed 3 years ago by
- Cc a.mason@… gh-jiawei-wang-ucd yzh dimpase dcoudert tmonteil added
- Description modified (diff)
- Summary changed from MIP frontend/backend using PuLP; backend to OSI using yaposib to Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...
comment:2 Changed 3 years ago by
comment:3 Changed 3 years ago by
I have the same feeling that PuLP has only minimal maintenance these days. Also, there is a significant effort in the OR community with Julia http://www.juliaopt.org/.
comment:4 Changed 3 years ago by
Andrew Mason commented by email:
PuLP is actively developed. It had a release last week. https://github.com/coin-or/pulp I know the developer Stuart Mitchell if you have any questions.
comment:5 Changed 3 years ago by
- Description modified (diff)
comment:6 Changed 22 months ago by
- Description modified (diff)
comment:8 Changed 22 months ago by
- Description modified (diff)
comment:9 Changed 22 months ago by
- Description modified (diff)
comment:10 follow-up: ↓ 11 Changed 22 months ago by
https://pypi.org/project/mip/ looks good. Too bad we can't use it because its license, Eclipse Public License 2.0, is used without a Secondary Licenses Notice that would make it instantly GPL-compatible.
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 13 Changed 21 months ago by
Replying to mkoeppe:
https://pypi.org/project/mip/ looks good. Too bad we can't use it because its license, Eclipse Public License 2.0, is used without a Secondary Licenses Notice that would make it instantly GPL-compatible.
it's py3 only, by the way.
W.r.t. licenses, maybe we can ask the authors for a fix?
comment:12 Changed 21 months ago by
- Cc fbissey added
- Description modified (diff)
Added info on cbcpy and glpk from fbissey in #28175.
comment:13 in reply to: ↑ 11 Changed 21 months ago by
Replying to dimpase:
Replying to mkoeppe:
https://pypi.org/project/mip/ looks good. Too bad we can't use it because its license, Eclipse Public License 2.0, is used without a Secondary Licenses Notice that would make it instantly GPL-compatible.
it's py3 only, by the way.
W.r.t. licenses, maybe we can ask the authors for a fix?
Good idea... please go ahead.
comment:14 Changed 21 months ago by
- Description modified (diff)
comment:15 Changed 21 months ago by
- Description modified (diff)
comment:16 Changed 20 months ago by
- Description modified (diff)
comment:17 Changed 17 months ago by
- Milestone changed from sage-wishlist to sage-9.2
Moving some tickets to 9.2. This is not a promise that I will be working on them.
comment:18 Changed 15 months ago by
- Description modified (diff)
comment:19 Changed 15 months ago by
- Description modified (diff)
comment:20 Changed 13 months ago by
- Milestone changed from sage-9.2 to sage-9.3
comment:21 Changed 8 months ago by
- Description modified (diff)
comment:22 Changed 6 months ago by
- Milestone changed from sage-9.3 to sage-9.4
Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.
comment:23 Changed 3 months ago by
- Description modified (diff)
comment:24 Changed 2 months ago by
- Milestone changed from sage-9.4 to sage-9.5
comment:25 Changed 7 weeks ago by
- Description modified (diff)
comment:26 Changed 7 weeks ago by
- Description modified (diff)
comment:27 Changed 6 weeks ago by
Pyomo can use SHOT sover https://github.com/coin-or/SHOT
When SHOT is configured to use all cores of cpu, solving traveling salesman problem is pretty fast.
This was in my plans for sage days84 at Olot, but i did not go further since then. Also, there is Numberjack, which seems pretty general. Looking quickly at the repositories, it seems that neither Numberjack nor PuLP were modified recently (though we could contact the authors to see if they have plans for the future).