Opened 9 months ago

Last modified 5 days ago

#2931 reviewing 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: branch
Keywords: 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 (31)

comment:1 Changed 9 months ago by ddorfmei

  • Status changed from new to accepted

comment:2 Changed 7 months ago by ddorfmei

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

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

r16138: project upgrades and changes to building

comment:5 Changed 7 months ago by ddorfmei

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

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

r16234:

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

comment:9 Changed 6 months ago by ddorfmei

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

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

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

comment:13 Changed 4 months ago by ddorfmei

r16417: added missing files

comment:14 Changed 4 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 3 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 3 months ago by abeham (previous) (diff)

comment:16 Changed 3 months ago by ddorfmei

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

comment:17 Changed 3 months ago by ddorfmei

  • Status changed from assigned to accepted

comment:18 Changed 3 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 2 weeks ago by ddorfmei

r16717: Upgraded OR-Tools to version 7.0

comment:20 Changed 2 weeks ago by ddorfmei

r16718: Cleanup, fixed spelling mistakes

comment:21 Changed 2 weeks ago by ddorfmei

r16719: removed file reference from project file

comment:22 Changed 2 weeks ago by ddorfmei

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

comment:23 Changed 2 weeks ago by ddorfmei

r16721: fixed HeuristicLab.ExtLibs.sln

comment:24 Changed 2 weeks ago by ddorfmei

r16736: Upgraded persistence to HEAL.Attic

comment:25 Changed 2 weeks ago by ddorfmei

r16745: Renamed MathematicalOptimization folders to ExactOptimization

comment:26 Changed 2 weeks ago by ddorfmei

r16746: Updated project reference in HeuristicLab.ExactOptimization.Views

comment:27 Changed 2 weeks ago by ddorfmei

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

comment:28 Changed 10 days ago by abeham

  • Version set to branch

comment:29 Changed 5 days ago by ddorfmei

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

comment:30 Changed 5 days ago by ddorfmei

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

comment:31 Changed 5 days ago by ddorfmei

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

Note: See TracTickets for help on using tickets.