Opened 8 months ago

Last modified 7 months ago

#26511 new enhancement

Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-wishlist
Component: numerical Keywords:
Cc: a.mason@…, gh-jiawei-wang-ucd, yzh, dimpase, dcoudert, tmonteil Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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:

  • 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:

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

References:

Key Python software (solver-independent):

PuLP

Pyomo

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

Change History (5)

comment:1 Changed 8 months ago by mkoeppe

  • 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 8 months ago by 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).

comment:3 Changed 8 months ago by 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/.

comment:4 Changed 7 months ago by 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.

comment:5 Changed 7 months ago by mkoeppe

  • Description modified (diff)
Note: See TracTickets for help on using tickets.