Opened 11 months ago

Last modified 5 weeks ago

#2931 readytorelease feature request

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

Reported by: ddorfmei Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.16
Component: General Version: trunk
Keywords: depends-2520 Cc:

Description

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.

Change History (49)

comment:1 Changed 11 months ago by ddorfmei

  • Status changed from new to accepted

comment:2 Changed 9 months ago by ddorfmei

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

comment:3 Changed 9 months ago by 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

comment:4 Changed 9 months ago by ddorfmei

r16138: project upgrades and changes to building

comment:5 Changed 9 months ago by ddorfmei

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

comment:6 Changed 9 months ago by 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

comment:7 Changed 8 months ago by 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

comment:8 Changed 8 months ago by ddorfmei

r16234:

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

comment:9 Changed 8 months ago by ddorfmei

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

comment:10 Changed 6 months ago by 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

comment:11 Changed 6 months ago by 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

comment:12 Changed 6 months ago by ddorfmei

  • Owner changed from ddorfmei to abeham
  • Status changed from accepted to reviewing

comment:13 Changed 6 months ago by ddorfmei

r16417: added missing files

comment:14 Changed 6 months ago by ddorfmei

r16419:

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

comment:15 Changed 5 months ago by 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?
Last edited 5 months ago by abeham (previous) (diff)

comment:16 Changed 5 months ago by ddorfmei

  • Owner changed from abeham to ddorfmei
  • Status changed from reviewing to assigned

comment:17 Changed 5 months ago by ddorfmei

  • Status changed from assigned to accepted

comment:18 Changed 5 months ago by ddorfmei

  • Owner changed from ddorfmei to abeham
  • Status changed from accepted to reviewing

r16582: solved the issues found during the review

comment:19 Changed 3 months ago by ddorfmei

r16717: Upgraded OR-Tools to version 7.0

comment:20 Changed 3 months ago by ddorfmei

r16718: Cleanup, fixed spelling mistakes

comment:21 Changed 3 months ago by ddorfmei

r16719: removed file reference from project file

comment:22 Changed 3 months ago by ddorfmei

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

comment:23 Changed 3 months ago by ddorfmei

r16721: fixed HeuristicLab.ExtLibs.sln

comment:24 Changed 3 months ago by ddorfmei

r16736: Upgraded persistence to HEAL.Attic

comment:25 Changed 3 months ago by ddorfmei

r16745: Renamed MathematicalOptimization folders to ExactOptimization

comment:26 Changed 3 months ago by ddorfmei

r16746: Updated project reference in HeuristicLab.ExactOptimization.Views

comment:27 Changed 3 months ago by ddorfmei

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

comment:28 Changed 2 months ago by abeham

  • Version set to branch

comment:29 Changed 2 months ago by ddorfmei

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

comment:30 Changed 2 months ago by ddorfmei

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

comment:31 Changed 2 months ago by ddorfmei

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

comment:32 Changed 7 weeks ago by abeham

  • Status changed from reviewing to assigned

comment:33 Changed 7 weeks ago by abeham

  • Owner changed from abeham to ddorfmei

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)
  1. Glop says "SolverVersion: Glop-0.0" in the result.

comment:34 Changed 7 weeks ago by ddorfmei

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

comment:35 Changed 7 weeks ago by 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

comment:36 Changed 6 weeks ago by ddorfmei

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

comment:37 Changed 6 weeks ago by ddorfmei

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

comment:38 Changed 6 weeks ago by ddorfmei

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

comment:39 Changed 6 weeks ago by ddorfmei

  • Owner changed from ddorfmei to abeham
  • Status changed from assigned to reviewing

comment:40 Changed 6 weeks ago by 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

comment:41 Changed 6 weeks ago by abeham

  • Version changed from branch to trunk

comment:42 Changed 6 weeks ago by ddorfmei

  • Cc ddorfmei added

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

comment:43 Changed 6 weeks ago by ddorfmei

  • Cc ddorfmei removed

comment:44 Changed 6 weeks ago by 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

comment:45 Changed 6 weeks ago by gkronber

r16944: changed build output path for all configurations

comment:46 follow-up: Changed 6 weeks ago by 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.

comment:47 in reply to: ↑ 46 Changed 6 weeks ago by 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.

comment:48 Changed 5 weeks ago by abeham

  • Status changed from reviewing to readytorelease

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

comment:49 Changed 5 weeks ago by abeham

  • Keywords depends-2520 added
Note: See TracTickets for help on using tickets.