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

• Create github issue label
• Incorporate it to CMake build (see below)
  • Build HiGHS using a CMake based build (provided by project, need to test)
  • BUILD_HIGHS using cmake fetch()
  • find_package() module
    • Test system wide install (https://repology.org/project/highs/badges)
• Incorporate it to bazel build
  • Build HIGHS using bazel
• 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:

• Add option in CMake to enable support (OFF by default maybe ON later)
  e.g.
  

  or-tools/CMakeLists.txt

  Lines 146 to 153 in 2cb85b4

  	# Optional third party solvers (enabled by default)
  	CMAKE_DEPENDENT_OPTION(USE_SCIP "Use the Scip solver" ON "BUILD_CXX" OFF)
  	message(STATUS "SCIP support: ${USE_SCIP}")
  	if(USE_SCIP)
  	CMAKE_DEPENDENT_OPTION(BUILD_SCIP "Build the SCIP dependency Library" OFF
  	"NOT BUILD_DEPS" ON)
  	message(STATUS "Build SCIP: ${BUILD_SCIP}")
  	endif()

• Add FetchContent() section tot build it
  e.g.
  

  or-tools/cmake/dependencies/CMakeLists.txt

  Lines 155 to 174 in 2cb85b4

  	# ##############################################################################
  	# GLPK
  	# ##############################################################################
  	if(BUILD_GLPK)
  	message(CHECK_START "Fetching GLPK")
  	list(APPEND CMAKE_MESSAGE_INDENT " ")
  	set(BUILD_EXAMPLES OFF)
  	set(WITH_GMP OFF)
  	set(WITH_ODBC OFF)
  	set(WITH_MYSQL OFF)
  	FetchContent_Declare(
  	glpk
  	GIT_REPOSITORY https://github.com/Mizux/GLPK.git
  	GIT_TAG 5.0
  	)
  	FetchContent_MakeAvailable(glpk)
  	list(POP_BACK CMAKE_MESSAGE_INDENT)
  	message(CHECK_PASS "fetched")
  	endif()

  
  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...)
• Add A FindHIGHS.cmake to find a system-wide installed version
  e.g. https://github.com/google/or-tools/blob/stable/cmake/FindGLPK.cmake
• Add section in deps.cmake
  e.g.

  or-tools/cmake/deps.cmake

  Lines 61 to 65 in 2cb85b4

  	if(USE_SCIP)
  	if(NOT BUILD_SCIP)
  	find_package(SCIP REQUIRED)
  	endif()
  	endif()

• Add a define USE_HIGHS in cpp.cmake
  e.g.

  or-tools/cmake/cpp.cmake

  Lines 26 to 28 in 2cb85b4

  	if(USE_GLPK)
  	list(APPEND OR_TOOLS_COMPILE_DEFINITIONS "USE_GLPK")
  	endif()

• Link MPSovler build to it
  e.g.

  or-tools/ortools/linear_solver/CMakeLists.txt

  Line 26 in 2cb85b4

  $<$<BOOL:${USE_SCIP}>:libscip>

[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 <#3116 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3INSEDFA56MC2V3ZB3VHJI2PANCNFSM5NULJT6A> . You are receiving this because you were mentioned.Message ID: ***@***.***>