Make HiGHS callable directly from CVXPY and document the availability of HiGHS more explicitly

[jajhall]

A user of HiGHS has observed that he is using "HiGHS v1.2.0 through SciPy in CVXPY".

The latest version of HiGHS is 1.7.2

For CVXPY to call HiGHS via SciPy was sensible in the past, since interfacing to HiGHS from Python was non-trivial.

However, HiGHS 1.7.2 is now available from PyPI and I assume that this would make it possible to interface HiGHS directly from CVXPY

It would be good to avoid being dependent on SciPy updates to update the version of HiGHS that is available to CVXPY users.

Also, in the CVXPY documentation, HiGHS is not listed explicitly so, to know that it can be used from CVXPY depends on knowing that it is the default LP and MIP solver in SciPy.

NB #1443 and #1721.

[Transurgeon]

Hello @jajhall thanks for raising this issue! This seems like an important new feature and I will try to work on it in the upcoming weeks. I had two questions for you (mostly out of curiosity):

• is the current SciPy not calling the updated version of HiGHS, or the user had an outdated version of SciPy?
• what changes have been added from version 1.2.0 to 1.7.2?

I think these are the tasks needed to close this issue:

• write a new interface for calling HiGHS directly
• write new tests in test_conic_solvers
• document HiGHS in various places, solver features, install, etc.

[Transurgeon]

Hello @jajhall I have made some progress on this issue in the referenced PR above (#2573). We are just missing the implementation for the solve_via_data method in the highs interface (see here). Since I am really not familiar with using HiGHS, I tried copy-pasting the code from the SciPy solver interface which also calls HiGHS. However, there seems to be many new changes in the new interface in highspy and it's not working properly.

I was wondering if you could help me in finishing up this PR for the interface by implementing this solve_via_data method?

[jajhall]

• is the current SciPy not calling the updated version of HiGHS, or the user had an outdated version of SciPy?

• what changes have been added from version 1.2.0 to 1.7.2?

The HiGHS LP solver entered SciPy in version 1.6. The MIP solver entered SciPy in version 1.9 - in July 2022 - using HiGHS v1.2.0. The most up-to-date version of SciPy I can get is 1.13.1, and it's still using HiGHS v1.2.0.

Between HiGHS 1.2.0 and 1.7.2, for SciPy users there are just bug fixes.

[jajhall]

Since I am really not familiar with using HiGHS, I tried copy-pasting the code from the SciPy solver interface which also calls HiGHS. However, there seems to be many new changes in the new interface in highspy and it's not working properly.

highspy reflects the C++ API, and has no methods like the highspy.linprog or highspy.milp that you'd like to use! Depending on what's upstream of this call, there's a lot of work to do for CVXPY to interface directly to highspy. In particular, highspy uses sparse compressed row/column storage of the constraint matrix.

None of the HiGHS team - other than a new PhD student - is a Python programmer, so it's hard to see how we can help.

However, let's keep up the dialogue, as there will be some major advances in HiGHS in the next 12 months, as well as the facility for multi-threading in Python, as discussed here

[PTNobel]

In particular, highspy uses sparse compressed row/column storage of the constraint matrix.

This is how we internally store the constraint matrix, so that's some good news :)

Our preferred API for a solver is we can specify:

• $n_{vars}$ the dimension of $x$, the variable in the problem
• $c$ a vector such that $c^T x$ is the objective
• $\ell, u$ such that $\ell \leq x \leq u$
• $A, b$ some CSR matrix $A$ and vector $b$ such that $Ax + s = b$ where $s$ is a slack variable
• A list of indices of $s$ that should be required to be $0$ and a list of indices of $s$ that should be required to be $\geq 0$
• A list of indices of $x$ that should be required to be integer

Going through your docs it wasn't obvious to me how to implement this without looping over every variable and and row of the constraints one-by-one.

[PTNobel]

Actually example 3 here: https://ergo-code.github.io/HiGHS/dev/interfaces/python/example-py/ shows addCols and addRows might be exactly what we want? I don't see any documentation of the integral variable support in the python interface tho. @Transurgeon feel free to schedule some time with me to go over how these function calls would work with our model.

[jajhall]

Great, it's easy for me to add a method to the C++ API to take a model in this form, and then create the Python binding that you'll need. It's quite a sensible format of MIP to accept. It's only inefficient if there are constraints L <= Ax <= U for finite L and U, since you'll need two copies of A to specify them.

I can't do anything before Wednesday, though

[jajhall]

Actually example 3 here: https://ergo-code.github.io/HiGHS/dev/interfaces/python/example-py/ shows addCols and addRows might be exactly what we want? I don't see any documentation of the integral variable support in the python interface tho. @Transurgeon feel free to schedule some time with me to go over how these function calls would work with our model.

Once you've defined all the columns using addCols, using changeColsIntegrality to indicate that a set of variables (columns) must take integer value, you could pass the constraints row-by row with the current version of HiGHS.

There is an example of the use of changeColsIntegrality in

https://github.com/ERGO-Code/HiGHS/blob/master/examples/branch-and-price.py

Sorry our documentation isn't better!

[PTNobel]

It's only inefficient if there are constraints L <= Ax <= U for finite L and U, since you'll need two copies of A to specify them.

We would have already lost any information about that structure in our standard reduction chain if I recall correctly; so, not a huge loss on our end.

I can't do anything before Wednesday, though

No worries on my end! I'm pretty time crunched this month, and I'm not sure how much time WIlliam has.

[jajhall]

The value in the interface I plan to add to HiGHS is that the expense of passing the model via calls to addCols and addRows in Python is avoided. Less processing is required, and will be done in C++.

[UweGensheimer]

Hello @jajhall In collaboration with @ghackebeil, we had implemented the cvxpy HiGHS interface which directly uses the C++ bindings provided in highspy. (PR #2580).

We think this might be a better interface choice to highs as it offers more flexibility in solver versioning as well as more functionality over the scipy interface.

[Transurgeon]

Closing this issue as PR mentioned above has been merged to master. @jajhall thank you for raising this issue. CVXPY plans to release version 1.6. in the next couple of weeks, the HiGHS interface will then be available to all users! @UweGensheimer thank you again for your great contribution!

[jajhall]

Great! I'll leave the creation of a EQ-UB CSR LP/MIP interface to HiGHS for now, but do let me know if there's a meaningful overhead of passing models row-by-row to HiGHS in Python