OR-Tools 9.0 with MiniZinc Priority Search, MiniZinc hot start, and random variable selection strategies
This repository contains modifications to Google's OR-Tools solver (version 9.0) I developed for my diploma thesis, Optimizing Constraint Programming for Real World Scheduling of Test Laboratories at TU Wien.
Extensions are:
- Implementing the MiniZinc priority_search annotation proposed by: Feydy, Thibaut, et al. "Priority search with MiniZinc." ModRef 2017: The Sixteenth International Workshop on Constraint Modelling and Reformulation.
- Hot start support for MiniZinc, allowing the solver to take solution hints as input through MiniZinc annotations.
- Random variable selection as a heuristic for custom search strategies.
To use priority search, add the following code to your MiniZinc model:
annotation priority_search(array[int] of var int, array[int] of ann, ann, ann);
And use it like:
solve
:: priority_search(
[var1, var2, ...],
[seq_search([...]), seq_search([...]), ...],
smallest,
complete
)
satisfy;
To hot start the solver with a known good variable assignment, use the following code:
annotation hot_start_ortools(array[int] of var int,array[int] of ann);
annotation hot_start_value(int);
solve
:: hot_start_ortools(
[var1, var2, ...],
[hot_start_value(val1), hot_start_value(val2), ...]
)
satisfy;
The syntax is a bit indirect as a workaround to avoid having to modify the flatzinc parser in OR-Tools.
Use random_order as the variable selection strategy in any search annotation.
My modifications to OR-Tools are released under the same Apache 2.0 license as OR-Tools itself.
This work was financially supported by the Austrian Federal Ministry for Digital and Economic Affairs, the National Foundation for Research, Technology and Development and the Christian Doppler Research Association. Their support is gratefully acknowledged.
Google's software suite for combinatorial optimization.
Google Optimization Tools (a.k.a., OR-Tools) is an open-source, fast and portable software suite for solving combinatorial optimization problems.
The suite contains:
- A constraint programming solver;
- A linear programming solver;
- Wrappers around commercial and other open source solvers, including mixed integer solvers;
- Bin packing and knapsack algorithms;
- Algorithms for the Traveling Salesman Problem and Vehicle Routing Problem;
- Graph algorithms (shortest paths, min cost flow, max flow, linear sum assignment).
We wrote OR-Tools in C++, but also provide wrappers in Python, C# and Java.
This software suite is composed of the following components:
- Makefile Top-level for GNU Make based build.
- makefiles Subsidiary Make files, CI and build system documentation.
- CMakeLists.txt Top-level for CMake based build.
- cmake Subsidiary CMake files, CI and build system documentation.
- bazel Subsidiary Bazel files, CI and build system documentation.
- ortools Root directory for source code.
- base Basic utilities.
- algorithms Basic algorithms.
- samples Carefully crafted samples.
- graph Graph algorithms.
- samples Carefully crafted samples.
- linear_solver Linear solver wrapper.
- samples Carefully crafted samples.
- glop Google linear solver.
- samples Carefully crafted samples.
- lp_data Data structures for linear models.
- constraint_solver Constraint and Routing solver.
- sat SAT solver.
- bop Boolean solver based on SAT.
- util Utilities needed by the constraint solver
- examples Root directory for all examples.
- tools Delivery Tools (e.g. Windows GNU binaries, scripts, release dockers)
This software suite has been tested under:
- Ubuntu 18.04 LTS and up (64-bit);
- Apple macOS Mojave with Xcode 9.x (64-bit);
- Microsoft Windows with Visual Studio 2019 (64-bit).
OR-Tools currently builds with a Makefile, but also provides Bazel and CMake support.
For installation instructions (both source and binary), please visit https://developers.google.com/optimization/introduction/installing.
We provide a Make based build.
Please check the
Make build instructions.
We provide a CMake based build.
Please check the
CMake build instructions.
We provide a Bazel based build.
Please check the
Bazel build instructions.
The best way to learn how to use OR-Tools is to follow the tutorials in our developer guide:
https://developers.google.com/optimization/introduction/get_started
If you want to learn from code examples, take a look at the examples in the examples directory.
The complete documentation for OR-Tools is available at: https://developers.google.com/optimization/
The CONTRIBUTING.md file contains instructions on how to submit the Contributor License Agreement before sending any pull requests (PRs). Of course, if you're new to the project, it's usually best to discuss any proposals and reach consensus before sending your first PR.
The OR-Tools software suite is licensed under the terms of the Apache License 2.0.
See LICENSE-2.0 for more information.