Meta-ticket: Use Python optimization interfaces: 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.

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

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, and InteractiveLinearProgram

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

• #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.
• 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

• ​https://github.com/jonls/python-qsoptex (see #18766)

PySCIPOpt

• #21003

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

[tmonteil]

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]

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]

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]

Added Python-MIP

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

[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?

[mkoeppe]

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

[mkoeppe]

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.

[mkoeppe]

Moving some tickets to 9.2. This is not a promise that I will be working on them.

[mkoeppe]

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.

[gh-sheerluck]

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.

[gh-sheerluck]

In Python3.10 they ​removed use_tracing and I can not build ​https://github.com/coin-or/CyLP anymore :(

[mkoeppe]

Reported upstream?

[gh-sheerluck]

​https://github.com/coin-or/CyLP/issues/132

[gh-sheerluck]

if installing CyLP for CBC is cumbersome, one can use ​https://github.com/coin-or/python-mip for CBC (​https://docs.python-mip.com/en/latest/examples.html)

[mkoeppe]

Unfortunately python-mip is encumbered with the same incompatible license as CBC itself. My plan is to target cvxpy as our main solver interface. It's well-maintained and supports lots of solver backends.

[gh-tkralphs]

Hi all, I had lost track of this discussion after the IMA workshop and am now re-engaging. @mkoeppe, I looked back at some e-mail correspondence on this topic, but didn't really find a substantive answer there as to why license compatibility is an issue here. I understand that this is something probably prescribed by the Sage organization itself and this may not be the forum for this discussion. If not, I'd be happy to engage somewhere else.

It looks to me like this is a pretty conservative interpretation. It is certainly true that you cannot distribute a single binary that mixes GPL'd and EPL'd code, or a binary that calls a shared library where the two have different licenses (although one might claim it's OK if the main binary is GPL and it's the library that is EPL). But something like python-mip is a self-contained program in the Python programming language and it's not being distributed in binary form, but source form. Yes, when it uses Cbc, it calls a shared library that is under the EPL, but since python-mip itself is also under the EPL, this doesn't create any issue. I can't really see how re-distributing python-mip is a problem, regardless of what it is being re-distributed with. It is well-known that "EPL and GPL are incomatible," but I think this incompatibility is referring to a completely different context than we have here. Can someone say exactly which license is being violated and exactly how the violation is occurring?

PuLP is even more clear cut, since it is in pure Python and only needs a self-contained Cbc binary to work. It is certainly no problem to re-distribute a statically linked Cbc binary in combination with anything. It doesn't link to anything and is itself a completely self-contained program, which can be freely re-distributed. We wouldn't claim PuLP cannot be distributed because it has the capability to use CPLEX. Further, PuLP is itself under a compatible license (MIT?).

Cvxpy may have a compatible license, but it's not useful on its own for solving LPs/MILPs without installing some solver and the open-source solver it uses for solving MILPs is Cbc through CyLP. Effectively, this just puts the onus on the user, then, to install CyLP. This doesn't really seem to be a solution.

In any case, wouldn't the legal liability derive from an owner of a GPL'd code complaining that said code was mixed illegally with non-GPL'd code? I guess that Sage itself is the entity with the GPL'd code and I would think that this could simply be allowed. There is no issue from the EPL side and in any case, the risk of legal action stemming from the re-distribution of COIN-OR code is extremely small.

Why is Sage different than, e.g., anaconda or even SciPy?? Anaconda seems to mix all kinds of licenses and as far as I can tell, the onus is on the user to makes sure that the combination of packages installed on their own machine is OK. Anaconda can really be interpreted as an installer of other people's packages. But I didn't research this extensively or dig into whether anaconda actually re-distributes or just installs packages pulled from Pypi and other sources. Another data point would be Linux distros, which obviously do redistribute combinations of self-contained software packages under many different licenses, including both GPL and EPL.

It would be a shame if this license stuff gets in the way here when I think it is clear that all the players involved would approve of what is being done.

[mkoeppe]

Hi Ted, thanks for joining the discussion here!

Replying to gh-tkralphs:

Why is Sage different than, e.g., anaconda [.... or ....] Linux distros, which obviously do redistribute combinations of self-contained software packages under many different licenses, including both GPL and EPL.

Yes, this would be "mere aggregation" ​https://www.gnu.org/licenses/old-licenses/gpl-2.0-faq.en.html#MereAggregation

[mkoeppe]

Replying to gh-tkralphs:

Why is Sage different than, e.g., anaconda or even SciPy??

No difference to SciPy? really. SciPy? vendors a lot of packages, but all of them use a permissive license that is compatible with SciPy?'s own license, BSD 3-clause (​https://github.com/scipy/scipy/blob/main/LICENSE.txt). It certainly does not vendor libraries with copyleft licenses such as GPL or EPL.

[mkoeppe]

Replying to gh-tkralphs:

something like python-mip is a self-contained program in the Python programming language and it's not being distributed in binary form, but source form. Yes, when it uses Cbc, it calls a shared library that is under the EPL, but since python-mip itself is also under the EPL, this doesn't create any issue.

It would not be a problem for Sage if we just included python-mip as a package in the Sage distribution, for users to install and use.

But if we were to make substantial use of it in the Sage library, replacing our home-grown (wasn't me!) MIP interface (​https://github.com/sagemath/sage/blob/develop/src/sage/numerical/mip.pyx), then this use would definitely rise above "mere aggregation" of software, making the result non-distributable in binary form.

[mkoeppe]

Replying to gh-tkralphs:

Yes, when it uses Cbc, it calls a shared library that is under the EPL, but since python-mip itself is also under the EPL, this doesn't create any issue.

Yes, there is no new problem of using python-mip as an interface to Cbc when one is already using Cbc.

However, as I wrote in our earlier discussion (with Haroldo and Túlio) in July 2021:

For Sage, I am shopping for an API offering pivot-level control over solvers that can support several backends, with the goal of replacing our home-grown (wasn't me) design. Given that Python-MIP already supports CBC and Gurobi, it is a viable candidate for this; if it weren't for the license situation [...]

[mkoeppe]

Replying to gh-tkralphs:

PuLP is even more clear cut, since it is in pure Python and only needs a self-contained Cbc binary to work. It is certainly no problem to re-distribute a statically linked Cbc binary in combination with anything. It doesn't link to anything and is itself a completely self-contained program, which can be freely re-distributed. We wouldn't claim PuLP cannot be distributed because it has the capability to use CPLEX. Further, PuLP is itself under a compatible license (MIT?).

Yes, permissive licenses such as the one that PuLP uses (and the one that python-mip used to use...) do not create such compatibility problems. It is unproblematic to distribute PuLP with Cbc in binary form. (Obviously, you can't redistribute the combination of PuLP with CPLEX.)

It is specifically the switch of python-mip from a permissive license to the incompatible copyleft license (EPL without "secondary license notice") that created the incompatibility with GPL software.

[mkoeppe]

Replying to gh-tkralphs:

Cvxpy may have a compatible license, but it's not useful on its own for solving LPs/MILPs without installing some solver and the open-source solver it uses for solving MILPs is Cbc through CyLP. Effectively, this just puts the onus on the user, then, to install CyLP. This doesn't really seem to be a solution.

That's not a problem for the Sage distribution, we have a working packaging infrastructure that already vendors hundreds of packages - ​https://repology.org/projects/?inrepo=sagemath_develop

[gh-tkralphs]

OK, thanks for clarifying, but it still looks to me like the GPL actually doesn't restrict things in the way you (and many others) are interpreting. Every argument I find that claims Python modules under incompatible licenses cannot be combined in this way takes as given that "importing a module" in Python is equivalent to "linking to a library" in a compiled language and this just isn't true in any sense. "Importing" in Python is functionally the same as "including" a source file in C/C++. You are allowed to combine GPL'd source code with other source code, no matter what the license and re-distribute the combination in source form, just not in binary form.

If you think about the philosophical underpinnings, what the GPL tries to prevent is that I modify the source code of a GPL'd code (or something linked to a GPL'd code) and then re-distribute it only in binary form, thereby profiting from a work that is derived from a GPL'd work, but not sharing the source of that derived work. The viral nature is just meant to try to ensure that everyone plays by these rules to the extent possible by preventing anyone from linking to GPL'd code in binary form without playing by the rules. But unless you distribute only a .pyc file and not a .py, this simply can't happen in Python. Although it would be possible to distribute a Python package in byte-compiled form without source (or even in some obfuscated form of source), this is not what you would be planning to do and it just doesn't run afoul of the GPL, either by the letter of the law or in spirit.

Of course, I am not a lawyer, but in my opinion, you can take python-mip, modify it as you wish, and re-distribute the modified version as an integrated part of Sage without any license issues. Here is an answer on Open Source Stack Exchange that I think is correct and supports this point of view, although everyone else seems to miss the point and disagree.

​https://opensource.stackexchange.com/a/8472

[mkoeppe]

I'd say this narrow view on what "linking" is amounts to wishful thinking. It's pretty clear from ​https://www.gnu.org/licenses/old-licenses/gpl-2.0-faq.en.html#TOCMereAggregation that the intention of the license is broader.

[mkoeppe]

More importantly, as an author of GPL-protected Python software myself, I would certainly not want this interpretation to be used when a vendor of proprietary software wanted to build their product on top of my software.

[gh-sheerluck]

Thanks to both of you for detailed explanation. I was trying to use cvxpy with CBC without CyLP and ended up injecting code from ​https://github.com/jurasofish/mip_cvxpy/blob/develop/mip_cvxpy/__init__.py inside ​https://github.com/cvxpy/cvxpy/blob/master/cvxpy/reductions/solvers/conic_solvers/cbc_conif.py

[mkoeppe]

I've opened #33487 for adding a package cylp