Integration of LP and MIP Solvers based on Google OR-Tools in HeuristicLab

[ddorfmei]

Google OR-Tools provides an easy-to-use API for LP and MIP solvers including CPLEX and Gurobi. Using its Natural C# API, models can be defined similarly to OPL and AMPL and then be solved with several solvers without modifications.

A wrapper should be implemented to simplify the usage of the Solver class and add features missing from the C# API. This wrapper then can be used in a C# script or a programmable problem to use exact optimization in HeuristicLab.

Google OR-Tools currently does not support external solvers out of the box because load-time dynamic linking is used, which implies that all solvers supported must be installed on a system to run a custom build of OR-Tools that is linked against all solvers. Thus, load-time dynamic linking must be replaced by run-time dynamic linking (as described in ​this issue) to support all solvers independently.

[ddorfmei]

r16046: created branch for integration of LP and MIP solvers based on Google OR-Tools in HeuristicLab

[ddorfmei]

r16070:

• added ExtLib plugin for Google OR-Tools
• added empty plugin for mathematical optimization
• upgraded target framework of all projects to .NET Framework 4.6.1

[ddorfmei]

r16138: project upgrades and changes to building

[ddorfmei]

r16139: Merged [16046-16138/trunk] into branch

[ddorfmei]

r16172:

• created LinearProgrammingAlgorithm
  • created definitions for all LP/MIP solvers supported by OR-Tools
• created LinearProgrammingProblem
  • created classes required for scripting: LinearProgrammingProblemDefinition, LinearProgrammingProblemDefinitionScript, CompiledLinearProgrammingProblemDefinition
  • created views: LinearProgrammingProblemView, LinearProgrammingProblemDefinitionScriptView
• updated OR-Tools version in ExtLibs to 6.9

[ddorfmei]

r16233:

• added all available parameters OR-Tools's linear_solver to LinearProgrammingAlgorithm
  • added necessary parameter enums
• moved solving logic to Solver
  • created IncrementalSolver, ExternalSolver, ExternalIncrementalSolver
  • added logic for solvers that can be stopped and resumed
• added SupportsStop property to BasicAlgorithm
• added quality per time chart for incremental solvers

[ddorfmei]

r16234:

• updated plugin dependencies
• added solver library name defaults to settings

[ddorfmei]

r16235: Merged [16168-16232/trunk] into branch

[ddorfmei]

r16373:

• upgraded Google OR-Tools to version 6.10
• added TextValue and TextValueView to be able to display and edit a multiline string
• added parameter to set solver specific parameters for supported solvers
• added support for the Protocol Buffers representation of models (import/export)
• added import of MPS models
• added pause/stop functionality to CplexSolver and GlpkSolver
• refactored wrapper (LinearSolver and related enums)
• added new algorithm category Exact for LinearProgrammingAlgorithm

[ddorfmei]

r16405:

• moved views to separate plugin HeuristicLab.MathematicalOptimization.Views
• added button in LinearProgrammingProblemView to select the problem definition type
• added views for problem definitions
• added ExportFile parameter to LinearProgrammingAlgorithm
• extended FileValue and FileValueView by the option to save a file
• code cleanup

[ddorfmei]

r16417: added missing files

[ddorfmei]

r16419:

• removed unnecessary NuGet packages from HeuristicLab.OrTools
• updated commit ID in Google.OrTools_version.txt
• removed generated files from HeuristicLab.MathematicalOptimization.Views

[abeham]

Review

• The file-based problem definition should contain "MPS" in the item name: "Problem Definition File (MPS, OR-Tools Proto Files)"
• The programmable based definition should have the item name: "Programmable Linear Problem Definition (LP, MILP)"
  • The description should not contain "and evaluates the solution"
• I general I would support item names using some publicly agreed form such as "Mixed-Integer Linear Programming" (potentially add "(LP, MILP)" for the creatable in order to have the abbreviated forms) instead of "Linear/Mixed Integer Programming", because that term is not known in this form. Neither is 100% correct, but one is at least more widely known.

I want to get feedback from other architects on this also. Review is to be continued.

[ddorfmei]

r16582: solved the issues found during the review

[ddorfmei]

r16717: Upgraded OR-Tools to version 7.0

[ddorfmei]

r16718: Cleanup, fixed spelling mistakes

[ddorfmei]

r16719: removed file reference from project file

[ddorfmei]

r16720: Merged revision(s) 16235-16719 from trunk

[ddorfmei]

r16721: fixed HeuristicLab.ExtLibs.sln

[ddorfmei]

r16736: Upgraded persistence to HEAL.Attic

[ddorfmei]

r16745: Renamed MathematicalOptimization folders to ExactOptimization

[ddorfmei]

r16746: Updated project reference in HeuristicLab.ExactOptimization.Views

[ddorfmei]

r16748: Removed Google.Protobuf.dll from HeurisiticLb.OrTools (Assembly is already provided by HEAL.Attic)

[ddorfmei]

r16803: Merged revision(s) 16720-16802 from trunk

[ddorfmei]

r16804: Added dependency to HeuristicLab.Protobuf for HeuristicLab.OrTools

[ddorfmei]

r16805: Glop was listed as MIP solver but is only an LP solver

[abeham]

Review comments:

1. Export of the simple default program to MPS results in the following exception:

System.IO.InvalidDataException: Model could not be exported.
   at HeuristicLab.ExactOptimization.LinearProgramming.LinearProblem.ExportModel(String fileName) in C:\...\branches\2931_OR-Tools_LP_MIP\HeuristicLab.ExactOptimization\3.3\LinearProgramming\Problems\LinearProblem.cs:line 91
   at HeuristicLab.ExactOptimization.Views.LinearProgrammingAlgorithmView.exportModelButton_Click(Object sender, EventArgs e) in C:\...\branches\2931_OR-Tools_LP_MIP\HeuristicLab.ExactOptimization.Views\3.3\LinearProgrammingAlgorithmView.cs:line 55
   at System.Windows.Forms.Control.OnClick(EventArgs e)
   at System.Windows.Forms.Button.OnMouseUp(MouseEventArgs mevent)
   at System.Windows.Forms.Control.WmMouseUp(Message& m, MouseButtons button, Int32 clicks)
   at System.Windows.Forms.Control.WndProc(Message& m)
   at System.Windows.Forms.ButtonBase.WndProc(Message& m)
   at System.Windows.Forms.Button.WndProc(Message& m)
   at System.Windows.Forms.NativeWindow.Callback(IntPtr hWnd, Int32 msg, IntPtr wparam, IntPtr lparam)

2. Glop says "SolverVersion: Glop-0.0" in the result.

[ddorfmei]

r16889: Fixed wrong time used for BestObjectiveValueFoundAt and QualityPerClock in results

[ddorfmei]

r16891:

• Updated Google.OrTools (added InitLogging method to Solver interface)
• Initialize logging when plugin is loaded.
• When a file cannot be exported, the log directory is shown in the error message

[ddorfmei]

r16897: Added log directory to additional exceptions caused by OR-Tools

[ddorfmei]

r16902: Merged revision(s) 16803-16897 from trunk

[ddorfmei]

"Glop-0.0" is returned by OR-Tools so I guess Google does not use version numbers for Glop.

[abeham]

r16910: merged to trunk

• Fixed references in plugins
• Fixed output path
• Removed app.config from views plugin
• Reverted changes to PathValue and FileValue and their respective views

[ddorfmei]

r16939:

• removed branch 2931_OR-Tools_LP_MIP
• removed unused file Google.Protobuf.dll from HeuristicLab.OrTools-7.0.0
• corrected commit ID in Google.OrTools_version.txt

[ddorfmei]

r16940:

• Added StorableType attribute to interfaces and classes where it was missing
• Moved code from HeuristicLabOrToolsPlugin.OnUnload() to finalizer because native DLL was unloaded too early

[gkronber]

r16944: changed build output path for all configurations

[gkronber]

I'm not sure but based on the fact that there is only OrTools.runtime.win-x64.dll of the native dll I suspect that this will only work in x64 environments. Usually, we provide both (x86 and x64) versions for native dlls and dispatch to the correct native dll dynamically. If this is possible for this interface then I would recommend to do it similarly.

[ddorfmei]

Replying to gkronber:

I'm not sure but based on the fact that there is only OrTools.runtime.win-x64.dll of the native dll I suspect that this will only work in x64 environments. Usually, we provide both (x86 and x64) versions for native dlls and dispatch to the correct native dll dynamically. If this is possible for this interface then I would recommend to do it similarly.

Google does not support Windows 32-bit:

Note: OR-Tools only supports the x86_64 (also known as amd64) architecture. ​Source

The plugin HeuristicLab.OrTools is only loaded on Windows 64-bit machines. This is also noted in the plugin description.

[abeham]

I reviewed r16939:16940 and r16944. I tested saving and loading of the default instance.

[abeham]

It was found that since the integration of this ticket many System.*.dll files appear in the bin folder.

[abeham]

r17095: Compile ExactOptimization to private bin folder and move relevant files to common bin folder in post-build

[abeham]

r17117: merged to stable (16910, 16939, 16944, 17095)

[gkronber]

r16940 has not yet been merged to stable

[abeham]

r17173: merged r16940 to stable