Add support to the HiGHS solver MathOpt

[SanPen]

Hi,

HiGHS is a magnificent open-source solver that's able to run in parallel, clearly beating CBC in some of the tests I've done in python.

Is there any plan to integrate it into or-tools? (C++)

If not, I'd like to do it myself since the interface looks similar to CBC's. What would be the right way to start?

thanks, Santiago

Mizux's EDIT(to have task list need to edit the first message...):

• [x] Create github issue label
• [x] Incorporate it to CMake build (see below)
  • [x] Build HiGHS using a CMake based build (provided by project, need to test)
  • [x] BUILD_HIGHS using cmake fetch()
  • [ ] find_package() module
  • [ ] Test system wide install (https://repology.org/project/highs/badges)
• [x] Incorporate it to bazel build
  • [x] Build HIGHS using bazel
• [x] Integrate to MathOpt

note: my dev will be in [mizux/highs] (to create) branch and regularly rebased on top of [master]

[lperron]

Yes, but we do not have the time to write the interface for it. So we will wait from some contribution for it.

[lperron]

You can copy the cbc_inteface.cc file

[Mizux]

Todo list:

• [x] Add option in CMake to enable support (OFF by default maybe ON later) e.g. https://github.com/google/or-tools/blob/2cb85b4eead4c38e1c54b48044f92087cf165bce/CMakeLists.txt#L146-L153
• [x] Add FetchContent() section tot build it e.g. https://github.com/google/or-tools/blob/2cb85b4eead4c38e1c54b48044f92087cf165bce/cmake/dependencies/CMakeLists.txt#L155-L174 ref: https://github.com/ERGO-Code/HiGHS/blob/master/CMakeLists.txt note: need to patch their CMake (no CMake config and install rule, no CTest use etc...)
• [x] Add A FindHIGHS.cmake to find a system-wide installed version e.g. https://github.com/google/or-tools/blob/stable/cmake/FindGLPK.cmake
• [x] Add section in deps.cmake e.g. https://github.com/google/or-tools/blob/2cb85b4eead4c38e1c54b48044f92087cf165bce/cmake/deps.cmake#L61-L65
• [x] Add a define USE_HIGHS in cpp.cmake e.g. https://github.com/google/or-tools/blob/2cb85b4eead4c38e1c54b48044f92087cf165bce/cmake/cpp.cmake#L26-L28
• [x] Link MPSovler build to it e.g. https://github.com/google/or-tools/blob/2cb85b4eead4c38e1c54b48044f92087cf165bce/ortools/linear_solver/CMakeLists.txt#L26

[gregy4]

Any news about support of highs solver ? Do you work on it, SanPen ? Latest version 1.2.2 solved one of my unsolvable mip problems by any open source solver (I maybe tried them all) including scip. Since optimal solution was found under 3 seconds, I was very satisfied and maybe there’s time to think about usage of mip solver in some cases for me.

[SanPen]

My process was the following:

• I went through ortools code and discovered that ortools modelling in C++was not as simple as ortools in python (a + b <= 3, etc) which disappointed me.
• I thought that making my own ortools exactly the way I wanted was less hassle, so I did it. It took me about a week.
• I integrated Highs rather easily.

So, essentially I thought that fighting a code that I don't understand would be far more complicated than building everything from scratch, so I made my own solver interface with matrix-variable operations embedded.

If we find time to do a gathering with the authors and get dummy-proof guide, I might write the Highs interface, otherwise it is too much for me.

[jajhall]

Having first got in touch with @lperron in August of last year, the HiGHS team is now in a position to contribute to writing an OR-Tools interface to HiGHS. Not only will this get around the "not open-source to industry" issue of SCIP, but it will give OR-Tools a better MIP solver than SCIP - see http://plato.asu.edu/ftp/milp.html

That said, I'm interested to read about the experiences of @SanPen and @Mizux on this page, and it would be great if you were able to feed your knowledge into the process.

[lperron]

Hi,

first, thank you all for this discussion.

Here is some context/roadmap.

About OR-Tools interface:

• MPSolver is on maintenance mode, and will soon be deprecated.
• We are working on 2 interfaces:
  • No thrill no incrementality, no callbacks protobuf based modeling layer called model_builder ( https://github.com/google/or-tools/tree/master/ortools/model_builder).
  • A complete, precise, incremental modeling layer called math_opt. This one is geared towards column generation, benders, cut generation.

model_builder is available in Python, Java. I need to write the C# layer, and export the C++ layer to or-tools. math_opt is available in C++. Python is being worked on, but we are waiting on bugfixes to export it to or-tools. Java will come later. C# may never come.

I would love to import HiGHS in or-tools (and drop CBC/CLP).

There are 4 parts to it:

• add it as a CMake dependency
• add it as a bazel dependency
• write the needed glu
• write the interface.

I can ask Corentin (mizux) to look at the first 2. I will do the 3rd.

Julian, can you or somebody in your team implement the proto solver (one shot non incremental solve) when the first 3 items are done. There are multiple examples in ortools/linear_solver/*proto_solver.h/cc. We will obviously help you.

Thanks

Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le jeu. 28 avr. 2022 à 11:11, Julian Hall @.***> a écrit :

Having first got in touch with @lperron https://github.com/lperron in August of last year, the HiGHS team is now in a position to contribute to writing an OR-Tools interface to HiGHS. Not only will this get around the "not open-source to industry" issue of SCIP, but it will give OR-Tools a better MIP solver than SCIP - see http://plato.asu.edu/ftp/milp.html

That said, I'm interested to read about the experiences of @SanPen https://github.com/SanPen and @Mizux https://github.com/Mizux on this page, and it would be great if you were able to feed your knowledge into the process.

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/3116#issuecomment-1111953437, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3INSEDFA56MC2V3ZB3VHJI2PANCNFSM5NULJT6A . You are receiving this because you were mentioned.Message ID: @.***>

[jajhall]

I've flagged up this exchange with @galabovaa and she will have a look at what's involved to implement the proto solver.

With your help, I'm sure that we'll make this happen

[Mizux]

Dev Note:

current state

see https://github.com/google/or-tools/tree/mizux/highs

To Fix/Patch

• [ ] highs_interface.cc (currently only a copy/paste from scip_interface.cc)
• [ ] HiGHS CMake fix:
  • [ ] Use of include(CTEST) and get rid of enable_testing() etc...
  • [ ] Why using SHARED_BUILD option then set the CMake orignal one BUILD_SHARED_LIB ...
  • [ ] fast build/regular build code refactoring (add_subdirectory(src) x2 !!!)
  • [ ] Add install rules for config files and Target.cmake
  • [ ] Should use GNUInstallDir than reinventing a borked wheel
  • [ ] Check for target ALIAS and namespace
• [ ] Bazelify HiGHS build...

[jajhall]

Thanks. @galabovaa got Bazel to build HiGHS before, so can contribute. She's busy for the next couple of weeks, though

[frederikgeth]

This is a post to say hi and to confirm interest in this feature! We currently use CLP and GLOP through Java OR tools. We are grateful to everyone for all the existing contributions and excited about the opportunity to start using HiGHS soon. Let me know if there is an opportunity to help in testing.

[jajhall]

@galabovaa is now in a position to start work on an OR-Tools <-> HiGHS interface. Can't say how long it will take, but it's definitely happening!

[igrqb]

Awesome! Kudos for the great work :)

[wxinix]

any updates about ORTools + Highs?

[jajhall]

any updates about ORTools + Highs?

Progress has been made, and @galabovaa will continue now that highspy is available from PyPI

[FernandoMotkraft]

@Mizux Hello, I wonder if you folks are still working on this. I would like to move away from SCIP, due to speed on MIP, also due to potential memory leaks on SCIP. Do you folks still have plans to enable HiGHs within or-tools? Is there an approximate timing you could share?

[lperron]

We are, low priority though. Not in 9.8 (coming soon). Hopefully 9.9 Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le mar. 24 oct. 2023 à 16:16, FernandoMotkraft @.***> a écrit :

@Mizux https://github.com/Mizux Hello, I wonder if you folks are still working on this. I would like to move away from SCIP, due to speed on MIP, also due to potential memory leaks on SCIP. Do you folks still have plans to enable HiGHs within or-tools? Is there an approximate timing you could share?

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/3116#issuecomment-1777311709, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3MWEMQXICTHJBB2DTLYA7ESRAVCNFSM5NULJT6KU5DIOJSWCZC7NNSXTN2JONZXKZKDN5WW2ZLOOQ5TCNZXG4ZTCMJXGA4Q . You are receiving this because you were mentioned.Message ID: @.***>

[FernandoMotkraft]

Thanks for the info @lperron

[Mizux]

It seems we already have Highs support for mathopt internally (i.e. blaze only), I need to export and clean it asap. But as Laurent say we want to release the incoming v9.8 this week first so we won't integrate it before v9.9 (ETA around Christmas)

[FernandoMotkraft]

That would be a nice Xmas present @Mizux :)

[individ2016]

Hello! Any news about HiGHS integration? :)

[Mizux]

Currently cleaning HiGHs build system, the objective is to have HiGHS support working for 9.10 this week or next (finger crossed):

• https://github.com/ERGO-Code/HiGHS/pull/1701

[Mizux]

Currently some math_opt tests fail when using HiGHs 1.7.0 (internally we still use 1.4.1) trying to understand what happen

[jajhall]

Currently some math_opt tests fail when using HiGHs 1.7.0 (internally we still use 1.4.1) trying to understand what happen

Happy to help you understand why, if you'll share HiGHS output

[Mizux]

Currently some math_opt tests fail when using HiGHs 1.7.0 (internally we still use 1.4.1) trying to understand what happen

Happy to help you understand why, if you'll share HiGHS output

@jajhall Thanks, I've create this issue with all information I have (i.e. the potential HiGHs commit), I'm trying to investigate...

• 4203