search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.23k stars 429 forks source link

Add MILP solver backends for HiGHS via scipy.optimize.linprog #32282

Open mkoeppe opened 3 years ago

mkoeppe commented 3 years ago

scipy 1.6 added a vendored copy of the HiGHS LP solvers. https://github.com/scipy/scipy/tree/master/scipy/optimize/_highs/src

https://docs.scipy.org/doc/scipy/reference/optimize.linprog-highs.html

We should start using them.

scipy 1.7 makes dual values available - https://docs.scipy.org/doc/scipy/reference/release.1.7.0.html#scipy-optimize-improvements

https://www.maths.ed.ac.uk/hall/HiGHS/ also has MIP, but this is not yet exposed in scipy.optimize.

highs also has a rudimentary python interface in its own source tree - https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/highs_python_api.py

For an interface that provides access to tableau data, as of 2022-04, neither scipy nor the OsiHiGHSSolverInterface provides the necessary methods:

See also:

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

Depends on #34081

CC: @dimpase @seblabbe @dcoudert

Component: linear programming

Issue created by migration from https://trac.sagemath.org/ticket/32282

mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -4,5 +4,7 @@

 We should start using them.

+scipy 1.7 makes dual values available - https://docs.scipy.org/doc/scipy/reference/release.1.7.0.html#scipy-optimize-improvements
+
 https://www.maths.ed.ac.uk/hall/HiGHS/ also claims to have MIP, but this does not seem to be exposed in scipy.optimize.
mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -8,3 +8,4 @@

 https://www.maths.ed.ac.uk/hall/HiGHS/ also claims to have MIP, but this does not seem to be exposed in scipy.optimize.

+highs also has a rudimentary python interface in its own source tree - https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/highs_python_api.py
mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -6,6 +6,6 @@

 scipy 1.7 makes dual values available - https://docs.scipy.org/doc/scipy/reference/release.1.7.0.html#scipy-optimize-improvements

-https://www.maths.ed.ac.uk/hall/HiGHS/ also claims to have MIP, but this does not seem to be exposed in scipy.optimize.
+https://www.maths.ed.ac.uk/hall/HiGHS/ also claims to have MIP, but this does not seem to be exposed in scipy.optimize. Upstream issue https://github.com/scipy/scipy/issues/14455 tracks the task of adding a MIP interface.

 highs also has a rudimentary python interface in its own source tree - https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/highs_python_api.py
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -6,6 +6,7 @@

 scipy 1.7 makes dual values available - https://docs.scipy.org/doc/scipy/reference/release.1.7.0.html#scipy-optimize-improvements

-https://www.maths.ed.ac.uk/hall/HiGHS/ also claims to have MIP, but this does not seem to be exposed in scipy.optimize. Upstream issue https://github.com/scipy/scipy/issues/14455 tracks the task of adding a MIP interface.
+https://www.maths.ed.ac.uk/hall/HiGHS/ also has MIP, but this is not yet exposed in scipy.optimize. 
+- scipy 1.9 will add it - https://github.com/scipy/scipy/pull/15460 has been merged

 highs also has a rudimentary python interface in its own source tree - https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/highs_python_api.py
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -10,3 +10,5 @@
 - scipy 1.9 will add it - https://github.com/scipy/scipy/pull/15460 has been merged

 highs also has a rudimentary python interface in its own source tree - https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/highs_python_api.py
+
+A possible route goes through CVXPY (#31962)
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -11,4 +11,9 @@

 highs also has a rudimentary python interface in its own source tree - https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/highs_python_api.py

-A possible route goes through CVXPY (#31962)
+A possible route for a high-level interface goes through CVXPY (#31962)
+
+For an interface that provides access to tableau data, as of 2022-04, neither scipy nor the [OsiHiGHSSolverInterface](https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/OsiHiGHSSolverInterface.hpp) provides the necessary methods:
+- https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1038529096
+
+
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -17,3 +17,5 @@
 - https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1038529096

+Part of Meta-ticket #26511: Use Python optimization interfaces: CVXPY, or-tools, PuLP, Pyomo, cylp...
+
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -16,6 +16,10 @@
 For an interface that provides access to tableau data, as of 2022-04, neither scipy nor the [OsiHiGHSSolverInterface](https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/OsiHiGHSSolverInterface.hpp) provides the necessary methods:
 - https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1038529096

+HiGHS is developing its own Python interface in https://github.com/ERGO-Code/HiGHS/tree/highspy/highspy (using pybind11); tableau data access methods yet to be done
+- https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1086217397
+
+

 Part of Meta-ticket #26511: Use Python optimization interfaces: CVXPY, or-tools, PuLP, Pyomo, cylp...
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -15,6 +15,7 @@

 For an interface that provides access to tableau data, as of 2022-04, neither scipy nor the [OsiHiGHSSolverInterface](https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/OsiHiGHSSolverInterface.hpp) provides the necessary methods:
 - https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1038529096
+- https://github.com/scipy/scipy/issues/15915 (feature request)

 HiGHS is developing its own Python interface in https://github.com/ERGO-Code/HiGHS/tree/highspy/highspy (using pybind11); tableau data access methods yet to be done
 - https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1086217397
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -17,7 +17,7 @@
 - https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1038529096
 - https://github.com/scipy/scipy/issues/15915 (feature request)

-HiGHS is developing its own Python interface in https://github.com/ERGO-Code/HiGHS/tree/highspy/highspy (using pybind11); tableau data access methods yet to be done
+HiGHS is developing its own Python interface in https://github.com/ERGO-Code/HiGHS/tree/master/src/interfaces/highspy (using pybind11); tableau data access methods yet to be done
 - https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1086217397
mkoeppe commented 2 years ago

Description changed:

--- 
+++ 
@@ -11,16 +11,13 @@

 highs also has a rudimentary python interface in its own source tree - https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/highs_python_api.py

-A possible route for a high-level interface goes through CVXPY (#31962)
-
 For an interface that provides access to tableau data, as of 2022-04, neither scipy nor the [OsiHiGHSSolverInterface](https://github.com/ERGO-Code/HiGHS/blob/master/src/interfaces/OsiHiGHSSolverInterface.hpp) provides the necessary methods:
 - https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1038529096
 - https://github.com/scipy/scipy/issues/15915 (feature request)

-HiGHS is developing its own Python interface in https://github.com/ERGO-Code/HiGHS/tree/master/src/interfaces/highspy (using pybind11); tableau data access methods yet to be done
-- https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1086217397
-
-
+See also:
+- A possible route for a high-level interface goes through CVXPY (#31962)
+- #33919 Add MILP solver backends for HiGHS via highspy

 Part of Meta-ticket #26511: Use Python optimization interfaces: CVXPY, or-tools, PuLP, Pyomo, cylp...
mkoeppe commented 2 years ago

Dependencies: #34081