search

coin-or / python-mip

Python-MIP: collection of Python tools for the modeling and solution of Mixed-Integer Linear programs
Eclipse Public License 2.0
513 stars 88 forks source link

Add SolverHighs #332

Closed rschwarz closed 4 months ago

rschwarz commented 1 year ago

Fix #255.

This PR adds a new class SolverHighs implementing a wrapper of the LP + MIP solver HiGHS, based on the C API.

Not all features expected of the mip.Solver interface are supported. In most cases, this is because HiGHS (or the C API) don't provide support for it (eg callbacks, certain parameters). In a few other cases, I just haven't added the implementation, yet (eg changing columns or rows). Either way, a NotImplementedError is raised.

I tested this wrapper locally with GNU/Linux and also made sure that the tests in test/test_model.py pass. But I did not try to include the new solver in some of the other tests.

I have not yet made any attempt to test this on other operating systems.

rschwarz commented 1 year ago

cc @sebheger

During the implementation, I've also noticed some problems for which I will create separate issues and PRs.

rschwarz commented 1 year ago

See https://github.com/ERGO-Code/HiGHS/discussions/1138 for a discussion of the HiGHS C API triggered by this.

rschwarz commented 1 year ago

I added more tests and feel that getRowsByRange is not working properly, see https://github.com/ERGO-Code/HiGHS/issues/1140

sebheger commented 1 year ago

cc @sebheger

During the implementation, I've also noticed some problems for which I will create separate issues and PRs.

Thanks for this awesome work so far. I will review your work.

rschwarz commented 1 year ago

To be clear: I don't expect the tests to pass in the final commit:

rschwarz commented 1 year ago

I added a workaround for Highs_getRowsByRange and fixed the new test.

sebheger commented 1 year ago

@rschwarz How is progress going on? Code looks suitable. At least some tests should be working in CI. I guess, highspy should be added as optional dependency to the pyproject.toml

rschwarz commented 1 year ago

I had nothing else planned here, except for waiting for another release of highspy and then simplifying some of the code here dealing with str names of vars/cons and variable type. But these improvements could always be added later.

The (unit) tests pass locally and it makes sense to add them to CI. I'll give this a try. I will also run all of the other tests with HiGHS locally and see what happens.

Increasing test coverage overall could be done in a separate issue/PR.

One thing that I was a bit unsure of, in retrospect, is the topic of solution values in the case of infeasible or unbounded. Does python-mip expect/provide a Farkas ray or is it OK to only provide var.x and var.pi in the case of optimal / feasible solutions?

rschwarz commented 1 year ago

I made the suggested changes and tried to install highs to be executed as part of the CI on GitHub.

Note that I only tested on Linux so far.

I've also added HiGHS as a solver to all other tests (including the slow ones) and tried to run them locally. The summary is 156 failed, 382 passed, 547 deselected in 1299.79s (0:21:39), where I filtered out the CBC tests. Some of the failures can be explained with missing features (NotImplementedError), eg cut generation, but some others might point to actual problems, which I'll have to look at first.

rschwarz commented 1 year ago

So I was able to fix some more bugs and exclude the tests where I can explain the failure (mostly NotImplementedError but see also commit msg for https://github.com/coin-or/python-mip/pull/332/commits/d01a239d7186a50a5c7f6738053c53a26e8853f1).

In the current state, all HiGHS-related tests now pass on my machine.

rschwarz commented 1 year ago

OK, there are more tests passing than I expected. In particular, OS X seems to just work.

The failures come from two sources:

sebheger commented 1 year ago

Bildschirmfoto 2023-03-15 um 16 36 02

There are only distributions for mac os x at version 11 available, that's why the installation in the CI fails for windows and ubuntu. In their setup.py they are stating that it requires python >= 3.6.

@rschwarz Will you open an issue or should I do?

sebheger commented 1 year ago

@rschwarz And same for the windows missing symbols, do you or should i open an issue?

rschwarz commented 1 year ago

I think both of these are known issues, see:

sebheger commented 1 year ago

@rschwarz I guess we should wait until Highs Team has fixed the issues. It seems that they are working on the python side

rschwarz commented 1 year ago

A new version of the highspy package was released. I'll see if that fixes the CI issues with windows and/or Python 3.11.

UPDATE: The tests still pass with this new version on my local machine, but I didn't try any of the combinations that previously failed on GitHub CI.

rschwarz commented 1 year ago

So I looked briefly into the failing test configurations (not error messages) to compare them with the previous run.

Combinations that used to fail but work now:

test (3.7.9, windows-2019) test (3.7.9, windows-2022) test (3.8.10, windows-2019) test (3.8.10, windows-2022) test (3.9.13, windows-2019) test (3.9.13, windows-2022)

Combinations that still fail:

test (3.10.9, windows-2019) test (3.10.9, windows-2022) test (3.11.1, windows-2019) test (3.11.1, windows-2022)

Combinations that used to work, but fail now:

test (3.11.1, ubuntu-20.04) test (3.11.1, ubuntu-22.04) test (pypy3.9-v7.3.9, ubuntu-20.04)

So, we can maybe say that Windows support has improved, but Python 3.11 is still not working (although the OS X tests pass?!).

Also, the final failing config, with pypy is different (error code 2 instead of 1), and seems to fail already upon importing of numpy, because of some version conflict with glibc. So in this case, maybe the combination of pypy and ubuntu versions are just compatible?

jurasofish commented 1 year ago

although the OS X tests pass?!

I don't think the tests are using highs on osx - see osx runs 547 tests while ubuntu runs 719 and I can't see highs in any of the test names

rschwarz commented 1 year ago

Good catch! I can dive deeper into this (some other time) and figure out if these tests are skipped intentionally, or the HiGHS solver was just not found in these cases.

rschwarz commented 1 year ago

I looked again at all combinations of Python version and operating system in the GitHub actions to see where tests are actually run and what the different failure modes are, as summarized in this table:

|-----------+--------+---------+-------------+---------------|
| linux     | cp     |      37 |           1 | pass          |
| linux     | cp     |      38 |           1 | pass          |
| linux     | cp     |      39 |           1 | pass          |
| linux     | cp     |     310 |           1 | pass          |
| linux     | cp     |     311 |           1 | pass          |
| linux     | pypy   |      39 |           1 | not installed |
| macosx_11 | cp     |      37 |           ^ | skipped       |
| macosx_11 | cp     |      38 |           ^ | skipped       |
| macosx_11 | cp     |      39 |           ^ | skipped       |
| macosx_11 | cp     |     310 |           ^ | skipped       |
| macosx_11 | cp     |     311 |           ^ | skipped       |
| macosx_12 | cp     |      37 |           $ | skipped       |
| macosx_12 | cp     |      38 |           $ | skipped       |
| macosx_12 | cp     |      39 |           $ | skipped       |
| macosx_12 | cp     |     310 |           $ | skipped       |
| macosx_12 | cp     |     311 |           $ | skipped       |
| win       | cp     |      37 |           1 | fail!         |
| win       | cp     |      38 |           1 | fail          |
| win       | cp     |      39 |           1 | fail          |
| win       | cp     |     310 |           1 | fail          |
| win       | cp     |     311 |           1 | fail          |
| win       | pypy   |      39 |           1 | not installed |
|-----------+--------+---------+-------------+---------------|

The pypy runs can all be ignored: The action doesn't even install highspy, so the tests are not run with HiGHS.

For linux, we can always install an appropriate wheel for highspy and the tests run successfully.

For macosx, the situation is a bit more interesting: There are wheels available on PyPI for the combinations (OSX 10.9, x86_64) and (OSX 11.0, ARM64), while the GitHub actions seem to run (OS X 11, x86_64) and (OS X 11, x86_64). pip install is unfazed by this discrepancy any happily installs highspy-1.5.3-cp38-cp38-macosx_10_9_x86_64.whl (with appropriate python version) in all cases. But here, none of the tests are run, which suggests that cffi is unable to dlopen the shared library. Maybe this is because of the mismatch of OS and architecture?

For win, the wheels are available and installed in the appropriate version. But the tests all fail because of missing symbols. The error messages mention Highs_create and Highs_destroy, as in

function/symbol 'Highs_create' not found in library 'C:\hostedtoolcache\windows\Python\3.7.9\x64\lib\site-packages\highspy\highs_bindings.cp37-win_amd64.pyd': error 0x7f
rschwarz commented 1 year ago

The missing symbol error is the same that we had before, and was already raised in https://github.com/ERGO-Code/HiGHS/issues/1119.

It occured to me that the issue might actually be not with the highs_bindings shared library, but the fact that the highs shared library is not found.

rschwarz commented 1 year ago

I believe that the wheels for OS X are incomplete, explaining why the dlopen fails, see https://github.com/ERGO-Code/HiGHS/issues/1328.

kbrix2000 commented 8 months ago

Meanwhile, I have provided a PR that adds another handy feature: Pass row and column names to HiGHS.

rschwarz commented 7 months ago

Meanwhile, I have provided a PR that adds another handy feature: Pass row and column names to HiGHS.

Thanks. Haven't checked in detail, but if this now works, and the names can be retrieved as well, then we wouldn't need to store them (redundantly) in the Python wrapper, as is currently done, eg in

https://github.com/Doing-The-Math/python-mip/blob/9bd75e5103af6b3f22d6bc5281d57515f5bb5ec3/mip/highs.py#L204