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

• Naming things
  • The namespace and plugin should be renamed to "HeuristicLab.ExactOptimization" instead of "HeuristicLab.MathematicalOptimization"
  • The ItemName of the file-based problem definition should be: "Problem Definition File (MPS, OR-Tools Proto Files)"
  • The ItemName of the programmable based definition should be: "Programmable Linear Problem Definition (LP, MIP)"
    • The description should not contain "and evaluates the solution"
  • The ItemName of the algorithm should be "Mixed-Integer Linear Programming (LP, MIP)"
  • The ItemName of the problem should be "Mixed-Integer Linear Programming Problem (LP, MIP)"

• Usage
  • MixedIntegerProgramming should be the default "ProblemType" for ILinearSolvers (if supported)
    • The only use case to set this to LinearProgramming is if you explicitly want to solve the LP relaxation instead of the ILP. This should not be the default case.
  • The ModelType is not shown in the run under Parameters, it should show which model type was used
    • In the case of the MPS model type it should also show the path to the file
    • In the case of the Programmable model type it should also show the name
  • Advanced parameters like "PrimalTolerance", "DualTolerance", "Scaling" should be hidden by default (Hidden = true)
  • A default timelimit of 1 minute should be set
  • Isn't LpAlgorithm a parameter of the solver, are these provided by all solvers? Same question regarding the presolve option (which should be true by default)
  • Export Model should be implemented as a button. The parameter should be removed. Please derive a custom algorithm view and add a button next to the prepare button, labeled "Export model to file". When this button is pressed a SaveFileDialog() should be opened where the user can choose the filename. After closing the dialog only the export should be performed.
    • Why is the option called "CPLEX LP File"? It also worked to export in combination with CBC
  • Can we offer an option to automatically include decision variables in the results (false by default)?
    • For instance when MPS files are solved, there's no way to get the actual solution
  • In the Problem type when selecting file-based model can we exclude Name and Data Type fields? They're readonly and are only confusing
  • We should not offer GPLK as option if it creates problems or crashes the application (does it still?)

• Code
  • The BasisStatus, DoubleParam, IncrementalityValues, IntegerParam enum are not referenced
  • ResultStatus: Do OR-Tools provide something similar to "OptimalWithinTolerance"? I hesitate to say "Optimal" when the BestObjectiveValue and the BestObjectiveBound are not equal
  • LinearProgrammingProblem.cs
    • ProblemDefinitionChanged event is not invoked from OnProblemDefinitionChanged, which in turn is not called from anywhere
    • The problem definition is not cloned in the cloning constructor (necessary to derive ILinearProgrammingProblemDefinition from IDeepCloneable)
  • LinearProgrammingAlgorithm.cs
    • I think it would be okay to seal this class (do we really want someone to derive from this?)
    • We should also expose getters for the parameters in addition to getters for the values as it allows registering change events. However, parameter properties should only expose getter no setter (e.g. LinearSolver and LinearSolverParameter, but remove setter for the latter).
    • Move Problem/ProblemType properties and Supports* properties to the top (similar style to other algorithms)
    • Is it really necessary to override Results?
    • An new event handler is attached to ExecutionTimeChanged each time the algorithm is started, is this really necessary? Also, it creates some complex reference structures as this timespan enters the solver class. If this is stored somewhere, then all previous solver instances may remain in memory as the algorithm holds references to each via the ExecutionTimeChanged event.
  • IncrementalLinearSolver.cs
    • The private variables bpcRow, qpcRow may be moved to just local variables of UpdateQuality
      • You can retrieve them from the IndexedDataTable when it exists (Rows has a string indexer)
      • Why is adding these rows to the indexed data table delayed to the check if they contain some values and not done right after instantiating them?

[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

[abeham]

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

[gkronber]

r16940 has not yet been merged to stable

[abeham]

r17173: merged r16940 to stable