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

[mkoeppe]

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.

• scipy 1.9 will add it - ENH: optimize: milp: mixed integer linear programming scipy/scipy#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

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

• OSI interface needs updating ERGO-Code/HiGHS#525 (comment)
• ENH: optimize: object-oriented interface to HiGHS scipy/scipy#15915 (feature request)

See also:

• A possible route for a high-level interface goes through CVXPY (Add SDP backend using CVXPY #31962)
• Add MILP solver backends for HiGHS via highspy #33919 Add MILP solver backends for HiGHS via highspy

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]

Dependencies: #34081