Version 1 (modified by ddorfmei, 2 years ago) (diff) |
---|
Exact Optimization
Google OR-Tools
According to Google, "OR-Tools is an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming." OR-Tools are available for C++, Python, Java and .NET, the latter API can be used in HeuristicLab.
OR-Tools includes solvers for
- Contraint Programming (CP, CP-SAT),
- Linear and Mixed-Integer Programming (BOP, Cbc, Clp, CPLEX, Glop, GLPK, Gurobi and SCIP),
- Routing,
- Scheduling and
- Network Flows.
For a complete overview, see https://developers.google.com/optimization/introduction/overview. You can use all solvers in HeuristicLab, just create a C# Script and make sure the Microsoft Visual C++ 2017 Redistributable (x64) is installed. Note that most linear and mixed-integer solvers must be installed (and licensed) separately, see the next section for details. the HeuristicLab.OrTools plugin is currently only available on 64-bit Windows.
Mixed-Integer (Linear) Programming (MIP, MILP)
OR-Tools contains a linear solver wrapper that can be used to define a MIP model once and solve it with a range of MIP solvers. Some solvers are already built into OR-Tools (BOP, Cbc, Clp, Glop) but for most solvers OR-Tools have to be built from source code, this version then has a dependency on the external solver. HeurisicLab includes a custom version of OR-Tools that allows users to simply install additional solvers without depending on them.
For a general introduction to MIP and a simple model implemented using the linear solver wrapper, see https://developers.google.com/optimization/mip/integer_opt. For further examples demonstrating more advanced usage of the linear solver wrapper using the C# API, see https://github.com/google/or-tools/tree/master/examples/dotnet.
The HeuristicLab.ExactOptimization plugin provides a GUI for MIP, just create a new Mixed-Integer Linear Programming (LP, MIP) algorithm, found under Algorithms, Exact. You can either load your model from a file (MPS, Google OR-Tools Protocol Buffers files) or define your model using a C# script and directly accessing the linear solver wrapper. The next two sections show the implementation of a Knapsack Problem (KSP) and a Travelling Salesman Problem (TSP).
Knapsack Problem (KSP)
Travelling Salesman Problem (TSP)
Implementing New Models in HeuristicLab
Attachments (2)
-
ExactOptimization.png
(31.2 KB) -
added by ddorfmei 2 years ago.
Simplified architecture of the HeuristicLab.ExactOptimization plugin
-
MixedIntegerLinearProgramming.png
(27.9 KB) -
added by ddorfmei 2 years ago.
Mixed-Integer Linear Programming (Algorithm View)
Download all attachments as: .zip