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