mkoeppe
commented
5 years ago 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
+
+
edd8e884-f507-429a-b577-5d554626c0fe
dcoudert
dimpase
sheerluck
tkralphs
The purpose of this ticket is to
SageMath status quo: Front end
add_constraint,set_integer,new_variableetc. and then re-solve)solver_parameter)sage.graphs,sage.coding,sage.combinat, ...SageMath status quo: Back ends
SageMath tickets and tasks
28175 Move sage optimization backends to separate Cython packages to remove
OptionalExtensionproblemsinteractivelp_backend.pyxis implemented in Cython just because a Cython template was available)19219 MILP: Add CyLP backend -- Replace basic Cython-based COIN backend by full-featured cylp backend (gives detailed access to CLP, including tableau data)
MixedIntegerLinearProgramby PuLP frontend or Pyomo frontendRelated:
20302 Meta-ticket: Improvements to
MixedIntegerLinearProgram, its backends, andInteractiveLinearProgramKey Python software (solver-independent)
Selection criteria for solver-independent interfaces:
cvxpy - Meta-ticket #33920
MathOptInterface.jlor-tools - #33493
conv_opt - https://github.com/KarrLab/conv_opt
PuLP - https://github.com/coin-or/pulp
sage -pip install pulpworksPyomo
sage -pip install pyomoworksYAPOSIB - Python interface to COIN OSI, using Boost::Python
sage -i boost && sage -pip install yaposibworksPython 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
36334
C, C++ solver abstractions
or-tools (#33493)
linear_solverwrapperCOIN-OR OSI
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)
32282 Add LP solver backends for HiGHS via scipy.optimize.linprog
highspy (pybind11-based interface to HiGHS)
33919 Add MILP solver backends for HiGHS via highspy
Interfaces to GLPK
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.
cbcpy (LGPL; new August 2019 according to https://pypi.org/project/cbcpy/; no activity since then)
Gurobi, CPLEX
python-qsoptex
SCIP, PySCIPOpt (now open source)
34726 Optional package
papilo: Parallel Presolve for Integer and Linear Optimization (https://github.com/scipopt/papilo/) - LGPL license34742 Optional package
soplex(dependency of scip)31329 Update
scipoptsuiteto 8.0.2 (now open source!)21003 Add package
pyscipopt(MIT license), add MIP backend34749 Package
scipsdp34750 Packages
gcg,PyGCGOptPossible integration routes via Julia
MathOptInterface- https://arxiv.org/pdf/2002.03447.pdfCC: 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