Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
mkoeppe opened this issue Oct 19, 2018 · 98 comments

Comments

@mkoeppe
Copy link
Contributor

mkoeppe commented Oct 19, 2018

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

@mkoeppe

This comment has been minimized.

@mkoeppe mkoeppe changed the title MIP frontend/backend using PuLP; backend to OSI using yaposib Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp... Oct 31, 2018
@sagetrac-tmonteil
Copy link
Mannequin

sagetrac-tmonteil mannequin commented Oct 31, 2018

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
Copy link
Contributor

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
Copy link
Contributor Author

mkoeppe commented Nov 4, 2018

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

This comment has been minimized.

@mkoeppe

This comment has been minimized.

@mkoeppe

This comment has been minimized.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Nov 30, 2019

comment:7

Added Python-MIP

@mkoeppe

This comment has been minimized.

@mkoeppe

This comment has been minimized.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Nov 30, 2019

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
Copy link
Member

dimpase commented Dec 28, 2019

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

This comment has been minimized.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Dec 28, 2019

comment:12

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

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Dec 28, 2019

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.

@mkoeppe

This comment has been minimized.

@mkoeppe

This comment has been minimized.

@mkoeppe

This comment has been minimized.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented May 1, 2020

comment:17

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

@mkoeppe mkoeppe added this to the sage-9.2 milestone May 1, 2020
@mkoeppe

This comment has been minimized.

@mkoeppe

This comment has been minimized.

@mkoeppe mkoeppe modified the milestones: sage-9.2, sage-9.3 Aug 29, 2020
@mkoeppe

This comment has been minimized.

@mkoeppe mkoeppe modified the milestones: sage-9.7, sage-9.8 May 28, 2022
@mkoeppe

This comment has been minimized.

@mkoeppe

This comment has been minimized.

@mkoeppe

This comment has been minimized.

@mkoeppe mkoeppe changed the title Meta-ticket: Use Python optimization interfaces: CVXPY, or-tools, PuLP, Pyomo, cylp... Meta-ticket: Use Python optimization interfaces: CVXPY, SCIP, or-tools, PuLP, Pyomo, cylp... Nov 11, 2022
@mkoeppe

This comment has been minimized.

@mkoeppe mkoeppe modified the milestones: sage-9.8, sage-9.9 Jan 29, 2023
@crsdvaibhav
Copy link

@mkoeppe Hey, I am Vaibhav from IIT BHU. I was looking forward to working on this issue for GSoC. I contacted you earlier via the sage-gsoc group, where you pointed out literature by Vanderbei, which I have been studying. Can you point out which issue would be good to start working on here? Thanks!

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Feb 25, 2023

#35198 could be a good starting point

@ashutosh887
Copy link

I'm willing to contribute to this Project @mkoeppe Sir
Please guide me to some issues to start with
I'm really willing to contribute

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Feb 25, 2023

Try #31962

@ashutosh887
Copy link

Sure Thanks @mkoeppe Sir

@latifbhatti
Copy link

I want to contribute on this project. I have knowledge about manifold. Guide me more about good issue to start.

@jnash10
Copy link
Contributor

jnash10 commented Mar 19, 2023

Hi @mkoeppe ,

I'd like to work on this section for GSoC/23.

If it is okay, as my proof of concept on being able to contribute to this Meta-ticket, I'll be taking one of this issues: #15356 or #7300 as referenced in meta-ticket #20302.

I have moderate experience in optimization (eg. Simplex Method, Integer optimization, etc) and its applied side via OR-Tools as I'm currently crediting an applied optimization course in my Data Science and Engineering degree at the Indian Institute of Science Education and Research Bhopal. 6+ years in Python.

I currently have one PR with a positive review in SageMath: #35113

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Mar 19, 2023

I'll be taking one of this issues: #15356 or #7300

These are pretty old issues and possibly not very clear.
#35308 could be a good way to start

@jnash10
Copy link
Contributor

jnash10 commented Mar 19, 2023

I'll be taking one of this issues: #15356 or #7300

These are pretty old issues and possibly not very clear. #35308 could be a good way to start

Alright!

Thank you, on it!

@Carlxuzhl
Copy link

Hi @mkoeppe, I'm Zhongling Xu from UT-Austin ORIE program. I have experience in optimization (convex optimization, linear programming and integer programming) and Python development. I would like to contribute to the idea "Enhanced optimization solver interfaces for Sage", which aligns my knowledge and skill set. Could you guide me to some good issues to start with? Thanks!

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Mar 22, 2023

Hi @Carlxuzhl, thanks for your interest! To get started with the MixedIntegerLinearProgram class in Sage, it could be interesting to first explore the frontend form the user's point of view. Just as a suggestion, we may want to add some exposition of integer programming methods for geometric packing/covering problems to Sage, for example 2d bin packing. A nontechnical task, just to get started with our workflow & infrastructure, could be to improve the documentation of https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tiling.html by adding plots (using the Sphinx .. PLOT:: directive).

@Carlxuzhl
Copy link

Hi @Carlxuzhl, thanks for your interest! To get started with the MixedIntegerLinearProgram class in Sage, it could be interesting to first explore the frontend form the user's point of view. Just as a suggestion, we may want to add some exposition of integer programming methods for geometric packing/covering problems to Sage, for example 2d bin packing. A nontechnical task, just to get started with our workflow & infrastructure, could be to improve the documentation of https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tiling.html by adding plots (using the Sphinx .. PLOT:: directive).

Thank you for the guidance! I will work on improving the documentation to get started.

@jnash10
Copy link
Contributor

jnash10 commented Mar 25, 2023

I'll be taking one of this issues: #15356 or #7300

These are pretty old issues and possibly not very clear. #35308 could be a good way to start

Since #35329 (still awaiting approval) has made good progress to solve it, can you suggest some other issue?

Thanks!

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Mar 25, 2023

@jnash10 Try #31962

@yangtx7
Copy link

yangtx7 commented Mar 27, 2024

Hi @mkoeppe, I'd like to work on "Enhanced optimization solver interfaces for Sage" section for GSoC'24. I found this project aligns with my interest and technical skills because I am an incoming CS PhD student and my research focus on ML-based MILP solver and ML-based MILP instance generator. I am familiar with Python interface of SCIP, Gurobi and CPLEX. Could you please guide me on specific issues or tasks that I can start working on?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests