Navigation

Foreword

We are glad to welcome you to the or-tools user’s manual. In this foreword, we try to answer most common questions a newcomer could have when discovering this manual or the library for the first time.

The or-tools library is a set of operations research tools developed at Google. If you have no idea what operations research is, you still can use our library to solve common small problems with the help of our Constraint Programming (CP) solver. If you do know what operations research is and how difficult it is sometimes to find efficient, easy to use and open source code, we hope you will enjoy using our library. We have put a lot of efforts in order to make it user friendly and continue to improve it on a daily basis. Furthermore, we encourage interactivity and are always open to suggestions. See the section How to reach us? below. If you have comments about this manual or the documentation in general, see the section Do you have comments?.

Content at a glance

This manual is divided in four parts:

If you are lost, use the links on the right sidebar .

What is or-tools?

The or-tools library is a set of operations research tools written in C++ at Google.

The main tools are:

  • A Constraint Programming solver.
  • A simple and unified interface to several linear programming and mixed integer programming solvers (CBC, CLP, GLOP, GLPK, Gurobi, SCIP and Sulum).
  • Knapsack algorithms.
  • Graph algorithms (shortest paths, min cost flow, max flow, linear sum assignment).
  • FlatZinc support.

In short, the or-tools library is:

  • Open source and free Everything, including the examples, the implementations of the algorithms, the various documentations, is licenced under the Apache License 2.0 and is available for download. If you make substantial improvements to our code, please share it with the whole community.

  • Alive The library is actively maintained and updates and improvements are made on an almost daily basis.

  • Documented OK, we just started to write the documentation but there are already numerous examples written in C++, Python, Java and C#!

  • Portable Because it is made by Google, the code conforms strictly to the Google coding styles. The code is known to compile on:

    • gcc 4.7.x and above on Ubuntu 12.04 and up (12.04, 12.10, 13.04, 13.10)
    • XCode >= 5.0 (clang++ with C++11 support)
    • Microsoft Visual Studio 2012 and 2013 (2010 is not supported as it lacks support for C++11)

    Both 32 bit and 64 bit architectures are supported, although the code is optimized to run in 64 bit mode.

  • Efficient All we can say is that we use it internally at Google.

  • Accessible Everything is coded in C++ but is available through SWIG in Python, Java, and .NET (using Mono on non-Windows platforms).

  • User-friendly We try to make our code as easy to use as possible (especially in Python and C#). Of course, there is a (small) learning curve to use our library but once you master several basic concepts, it is quite straightforward to code with the or-tools library.

  • Tested We use it internally at Google since a few years and the community of users is growing.

Optimization tools at Google

If you want to know more about optimization at Google, we refer the interested read to our Google Optimization page.

What you will learn in this document

This manual is intended to give you the necessary knowledge to use the library and explore the reference manual by yourself. We describe the basic concepts but also how to customize your search in Constraint Programming (CP). One of the strength of our library is its routing solver in CP to solve node- and vehicle routing problems with constraints. We describe how to customize your routing algorithms. After reading this manual, you will be able to understand our way of coding and how to use the full potential of our library.

We detail the content of the manual in the section The content of the manual.

What you will not learn in this document

This document is by no means a tutorial on Operations Research nor on Constraint Programming although we try to give you a glimpse of the best practices. It is also NOT a reference manual (refer to the documentation hub to find the reference manual). There are way too many methods, parameters, functions, etc. to explain them all in details. Once you understand the concepts and methods explained in this manual, you shouldn’t have any trouble scanning the reference manual and find the right method, parameter, function, . . . or code them yourselves!

We don’t document the non Constraint Programming (CP) part of the library. If you have any questions about the non-CP part of the library, don’t hesitate to ask them on the mailing list. See the section How to reach us? below.

We don’t discuss the flatzinc implementation nor the parallel solving process.

This document will not describe how to use the library (and the syntactic sugar introduced when possible) with Python, Java nor C#. This could possibly change in the future. The tutorial examples (see below) exist also in Python, Java and C# though.

How to read this document?

You could read this document from cover to cover but we have put a lot of efforts to make each chapter stands on its own. The best way to read this manual is to look for a specific answer, use the index or the table of contents to find a reference to that information. If you are missing some requirements to understand a section, you can always backtrack on prerequisite knowledge. For each chapter, we list those prerequisites. This non-linear way of reading is probably the most efficient and rewarding one!

That said, the manual is kept short so that you can read it in its entirety. The first part (Basics) is an introduction on how to use the CP solver to solve small problems. For real problems, you need to customize your search and this is explained in the second part (Customization). If you are interested in the routing part of the library, the third part is for you (Routing). Finally, some utilities and tricks are described in the last part (Technicalities).

Targeted audience

This manual is written with two types of readers in mind. First, someone who is not familiar with Constraint Programming nor is she a professional programmer. Second, an educated reader who masters Constraint Programming and is quite at ease without necessarily mastering one of the supported computer languages.

From time to time, we refer to scientific articles: you don’t need to read and understand them to follow the manual.

Did we succeed to write for such different profiles? You tell us!

Conventions used in this manual

All the code is systematically written in monospace font. Function and method’s names are followed by parentheses. The method MakeSomething() and the parameter something are two beautiful examples of this convention.

To draw your attention on important matters, we use a box with a danger warning sign.

Warning

You have been warned!

To explain some details that would break the flow of the text, we use a box with a light bulb.

This is an explanation that would break the flow of the text

This is why we prefer to put our explanation aside in a box with a light bulb.

To focus on some parts of the code, we omit non necessary code or code lines and replace them by ”...”.

namespace operations_research {
  IntVar* const MakeBaseLine2(...) {
    ...
  }
  ...
  void CPIsFun() {
    // Magic happens here!
  }
}  // namespace operations_research

In this example, the parameters of the function MakeBaseLine2() are stripped as are the content of this method and the code lines that follow the definition of this function. The purpose of this example is to show that the code is written inside the namespace operations_research.

All commands are issued from a Unix-like terminal:

./golomb1 --n=5 --cp_no_solve --cp_show_constraints

Adapt the command lines to your type of terminal and operating system.

Accompanying code for this manual

All the examples in this manual are coded in C++. For the most important code snippets, you can find complete examples on the documentation hub:

https://acrogenesis.com/or-tools/documentation/documentation_hub.html#tutorial_examples

or under the following directory of the or-tools library:

  • documentation/tutorials/C++

If you prefer to code in Python, Java or C#, we have translated (will translate) all the examples in your favourite language. You can find the complete examples on the documentation hub or under the directories:

  • documentation/tutorials/Python
  • documentation/tutorials/Java
  • documentation/tutorials/Csharp.

How to reach us?

The whole project or-tools is hosted on Google code:

http://code.google.com/p/or-tools/

You can follow us on Google+:

https://plus.google.com/u/0/108010024297451468877/posts

and post your questions, suggestions, remarks, . . . to the or-tools discussion group:

http://groups.google.com/group/or-tools-discuss

How to reference this document?

Refer to the written document like this:

  1. van Omme, L. Perron and V. Furnon, or-tools user’s manual, Google, 2014.

Here is a bibtex entry:

@TECHREPORT{or-tools-user-manual,
  author = {Nikolaj van Omme and Laurent Perron and Vincent Furnon},
  title = {or-tools user's manual},
  institution = {Google},
  year = {2014}
}

Do you have comments?

If you have comments, suggestions, corrections, feedback, ..., about this document or about the documentation of the or-tools library in general, please send them to

Thank you very much.

Happy reading!

The or-tools team

Google or-tools
open source library

User's Manual

Google search

Search:

Welcome

Tutorial examples

Chapters

Part I: Basics
Part II: Customization
Part III: Routing
Part IV: Technicalities
Appendices

Navigation

© Copyright 2012-2015, Google. Created using Sphinx 1.1.3.