Meta-ticket: Use Python optimization interfaces: CVXPY, SCIP, or-tools, PuLP, Pyomo, cylp...

[mkoeppe]

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,
• provide an entry point for GSoC 2023 projects

SageMath status quo: Front end

• 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 library code for sage.graphs, sage.coding, sage.combinat, ...
  • MIPVariable - indexed by arbitrary objects
  • some connections to Polyhedron class and to InteractiveLPProblem (didactical code)

SageMath status quo: Back ends

• In-tree backends, using Cython, with varying degrees of implementation quality
  • GLPK backend - complete, includes support for tableau data and GLPK's exact rational mode
  • InteractiveLP backend - basic, provide LP only for algebraic LPs
  • CVXOPT backend
  • PPL backend - exact solver
• Separate distribution packages for optional packages (proprietary solvers, open-source solvers with incompatible licenses)
  • https://github.com/sagemath/sage-numerical-backends-coin: COIN backend (CBC) - very basic, no support for setting solver parameters such as time limit
  • https://github.com/sagemath/sage-numerical-backends-cplex: CPLEX backend
  • https://github.com/sagemath/sage-numerical-backends-gurobi: Gurobi backend
• Optimization interface is maintained by a very small part of the Sage developer community

SageMath tickets and tasks

• Move optional sage optimization backends (COIN, CPLEX, Gurobi) to separate Cython packages to remove OptionalExtension problems #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)
• MILP: Add CyLP backend #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:

• Meta-ticket: Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram #20302 Meta-ticket: Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram

Key Python software (solver-independent)

Selection criteria for solver-independent interfaces:

• Does it use a compatible, permissive, open source license?
• Does it provide detailed access to the solver that allows for updating problems and warmstarting?
• Is it under active development?

cvxpy - Meta-ticket #33920

• permissive open source license: Apache 2.0
• use CBC via cylp
• experimental CBC interface via python-mip - Using python-mip library with cvxpy syntax cvxpy/cvxpy#1265, https://pypi.org/project/mip-cvxpy/
• Interface to OR-Tools/PDLP cvxpy/cvxpy#1649 (comment): Link to OR-tools solver abstraction
• Link to MathOptInterface.jl cvxpy/cvxpy#1704: Link to MathOptInterface.jl
• as of 2022 under active development; maintainers appear to respond quickly to issues/PRs: cvxpy/cvxpy#1705, cvxpy/cvxpy#1707, cvxpy/cvxpy#1719

or-tools - #33493

• Upcoming ("soon" as of 2022-08) new MathOpt DSL (Python)

conv_opt - https://github.com/KarrLab/conv_opt

• MIT license
• Cbc, CVXOPT, FICO XPRESS, GLPK, Gurobi, IBM CPLEX, MINOS, Mosek, quadprog, SciPy, and SoPlex.

PuLP - https://github.com/coin-or/pulp

• permissive open source license (BSD?)
• 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 (Project not maintained well, looking for co-maintainer coin-or/pulp#183)

Pyomo

• permissive open source license: BSD
• 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)

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/

PAO

• Packages for parametric/bilevel/adversarial/stochastic optimization #36334

C, C++ solver abstractions

or-tools (#33493) ​linear_solver wrapper

• supporting CLP, CBC, GLPK, Gurobi, SCIP, XPRESS
• permissive open source license: Apache 2.0
• quick with "wontfix" - google/or-tools#3205

COIN-OR OSI

• incompatible copyleft license: Eclipse Public License 2.0

Key Python software (solver-dependent)

The Python interfaces that target only one solver are usually careful in not having more restrictive licenses than the targeted solver.

scipy.optimize (vendors HiGHS)

• Permissive open source licenses: SciPy: BSD 3-clause; HiGHS: MIT license
• Add MILP solver backends for HiGHS via scipy.optimize.linprog #32282 Add LP solver backends for HiGHS via scipy.optimize.linprog

highspy (pybind11-based interface to HiGHS)

• Add MILP solver backends for HiGHS via highspy #33919 Add MILP solver backends for HiGHS via highspy

Interfaces to 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

• Package CyLP #33487: 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.
• same license as CBC/CLP/CGL
• as of Mar 2022: many open issues, minimal maintenance mode by 1 maintainer who is cooperative on receiving PRs: coin-or/CyLP#153, coin-or/CyLP#155, coin-or/CyLP#156, coin-or/CyLP#157

cbcpy (LGPL; new August 2019 according to ​https://pypi.org/project/cbcpy/; no activity since then)

• upstream devs for cbc have published their own python interface ​https://gitlab.com/ikus-soft/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: Move optional sage optimization backends (COIN, CPLEX, Gurobi) to separate Cython packages to remove OptionalExtension problems #28175 - where we remove these cython modules from sagelib and ship them in separate packages instead

python-qsoptex

• https://github.com/jonls/python-qsoptex (see Add bindings, MixedIntegerLinearProgram backend to qsopt_ex, a state-of-the-art exact simplex solver #18766)

SCIP, PySCIPOpt (now open source)

• Optional package papilo (dependency of scip) #34726 Optional package papilo: Parallel Presolve for Integer and Linear Optimization (https://github.com/scipopt/papilo/) - LGPL license
• Optional package soplex (dependency of scip) #34742 Optional package soplex (dependency of scip)
• Update scipoptsuite to 8.0.2 (now open source!), rename to scip #31329 Update scipoptsuite to 8.0.2 (now open source!)
• Add package pyscipopt, add MIP backend #21003 Add package pyscipopt (MIT license), add MIP backend
• Packages dsdp, scip_sdp #34749 Package scipsdp
• Packages gcg, PyGCGOpt #34750 Packages gcg, PyGCGOpt

Possible integration routes via Julia

• MathOptInterface - https://arxiv.org/pdf/2002.03447.pdf

CC: a.mason@auckland.ac.nz @jiawei-wang-ucd @yuan-zhou @dimpase @dcoudert @sagetrac-tmonteil @kiwifb

Component: numerical

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

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,8 +1,74 @@
-https://github.com/coin-or/pulp
+The purpose of this ticket is to 
+- connect [SageMath](../wiki/SageMath) to interfaces to optimization solvers that are maintained outside of the Sage project,
+- integrate the related developer and user communities.
 
-It has 
-- some API-based and some file-based interfaces to various solvers (including COIN OSI via yaposib),
-- a basic modeling system (need to compare its capabilities with sage frontend)
+**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)
+- 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
 
-https://github.com/coin-or/yaposib
+**Tickets:**
 
+- 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, and InteractiveLinearProgram
+
+.  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
+
+References:
+
+**Key Python software (solver-independent):**
+
+**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](https://github.com/coin-or/pulp/blob/master/src/pulp/solvers.py)
+  - is it under active development??
+
+**Pyomo**
+- http://www.pyomo.org/ 
+- installation with `sage -pip install pyomo` works
+- some file-based, some API-based interfaces (direct/persistent) - see [solvers directory](https://github.com/Pyomo/pyomo/tree/master/pyomo/solvers/plugins/solvers)
+- 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
+
+**Key Python software (solver-dependent):**
+
+**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
+
+

[sagetrac-tmonteil]

comment:2

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).

[dcoudert]

comment:3

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/.

[mkoeppe]

comment:4

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.

[mkoeppe]

Description changed:

--- 
+++ 
@@ -50,7 +50,7 @@
    - COINMP_DLL (CBC via COINMP C library API), 
    - YAPOSIB (Python interface to COIN OSI, see below), 
    - see [solvers.py](https://github.com/coin-or/pulp/blob/master/src/pulp/solvers.py)
-  - is it under active development??
+  - **PuLP is currently looking for a co-maintainer** (https://github.com/coin-or/pulp/issues/183)
 
 **Pyomo**
 - http://www.pyomo.org/ 

[mkoeppe]

Description changed:

--- 
+++ 
@@ -32,7 +32,7 @@
 
 Related:
 - #20302 Meta-ticket: Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram
-
+- #28175 Move sage optimization backends to separate Cython packages to remove OptionalExtension problems
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 
 References:

[mkoeppe]

Description changed:

--- 
+++ 
@@ -65,6 +65,9 @@
 - 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**
+- https://pypi.org/project/mip/
+
 **Key Python software (solver-dependent):**
 
 **cylp**

[mkoeppe]

comment:7

Added Python-MIP

[mkoeppe]

Description changed:

--- 
+++ 
@@ -65,8 +65,10 @@
 - 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**
+**Python MIP (Mixed-Integer Linear Programming) Tools** (new 2018)
 - https://pypi.org/project/mip/
+- https://github.com/coin-or/python-mip
+- requires Python 3.5 or newer
 
 **Key Python software (solver-dependent):**
 

[mkoeppe]

Description changed:

--- 
+++ 
@@ -68,7 +68,8 @@
 **Python MIP (Mixed-Integer Linear Programming) Tools** (new 2018)
 - https://pypi.org/project/mip/
 - https://github.com/coin-or/python-mip
-- requires Python 3.5 or newer
+- Eclipse Public License 2.0 (considered **GPL**-incompatible https://www.gnu.org/licenses/license-list.en.html#GPLCompatibleLicenses)
+- **requires Python 3.5 or newer**
 
 **Key Python software (solver-dependent):**
 

[mkoeppe]

comment:10

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.

[dimpase]

comment:11

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?

[mkoeppe]

Description changed:

--- 
+++ 
@@ -73,8 +73,19 @@
 
 **Key Python software (solver-dependent):**
 
+**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
+

[mkoeppe]

comment:12

Added info on cbcpy and glpk from fbissey in #28175.

[mkoeppe]

comment:13

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.