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 - ​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

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

• ​https://github.com/ERGO-Code/HiGHS/issues/525#issuecomment-1038529096
• ​https://github.com/scipy/scipy/issues/15915 (feature request)

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...