Skip to content

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

@mkoeppe

Description

@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

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:

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

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

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)

PICOS - a user friendly Python API to several conic and integer programming solvers, very much like YALMIP or
CVX under MATLAB.

PAO

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)

highspy (pybind11-based interface to HiGHS)

Interfaces to GLPK

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

python-qsoptex

SCIP, PySCIPOpt (now open source)

Possible integration routes via Julia

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

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions