Ortools

New directory structure in C++

We have changed the source/include structure of or-tools when using C++. The goal is to provide better encapsulation of the C++ include files. It also has the benefit of aligning the C++ and the python directory structures.
- src/ has been renamed ortools/.
- All include command in C++ files now have the prefix ortools added. include "constraint/constraint_solver.h" is now include "ortools/constraint/constraint_solver.h".

New features

Bazel support

You can now build or-tools with bazel, Google's build tool. It works on Linux and Mac OS X. After downloading bazel version 0.4.5 or later, change directory to or-tools and build the examples: bazel build examples/cpp/....

Routing

We have implemented the support for breaks (e.g., vehicle downtime due to drivers eating lunch)in the routing library. This feature is shown in the [cvrptw_with_breaks.cc](https://github.com/google/or-tools/blob/v6.0/examples/cpp/cvrptw_with_breaks.cc) example.

SCIP support

The linear solver wrapper now support SCIP 4.0. You now need to build SCIP first, and then tell or-tools that you will use it. Instructions are available [here](http://or-tools.blogspot.fr/2017/03/changing-way-we-link-with-scip.html).

GLPK support

We have also changed the way with build with [GLPK](http://or-tools.blogspot.fr/2017/03/linking-glpk-with-or-tools-on-unix.html). See here.

Cleanups

- We have removed all usage of hash_map, hash_set in the C++ codebase as they are deprecated. They were replaced by unordered_map and unordered_set from the STL.

- Cleanup of the C makefiles, courtesy of Michael Powell.

New Features

Installing
- Introduced simpler procedures for installing or-tools, either from binary distributions or from source code. See [Installing or-tools](https://developers.google.com/optimization/introduction/installing.html) for more information.

Routing
- Implemented an algorithm to compute the Held-Karp lower bound for symmetric Traveling Salesman Problems. This enables you to compute an upper bound to the gap between the cost of a potentially non-optimal solution and the cost of the optimal solution.
- Added a new method to the vehicle routing library, [`RoutingModel::SetBreakIntervalsOfVehicle`](https://developers.google.com/optimization/reference/constraint_solver/routing/RoutingDimension/), which lets you add _break_ intervals — time periods when a vehicle cannot perform any tasks (such as traveling or visiting a node). For an example that uses this option, see
[https://github.com/google/or-tools/blob/master/examples/cpp/cvrptw_with_breaks.cc](https://github.com/google/or-tools/blob/master/examples/cpp/cvrptw_with_breaks.cc).

Scheduling
- Added support for more data formats in the parser for the [Project Scheduling Library](https://github.com/google/or-tools/blob/master/src/util/rcpsp_parser.h).

Sat solver
- The Sat solver's cumulative constraint now accepts optional intervals, created with the [`NewOptionalInterval`](https://github.com/google/or-tools/blob/master/src/sat/intervals.h#L36) method. For an example, see
[https://github.com/google/or-tools/blob/master/examples/cpp/rcpsp_sat.cc](https://github.com/google/or-tools/blob/master/examples/cpp/rcpsp_sat.cc).
- You can now solve a maximum satisfiability problem by specifying the objective as a weighted sum of literals. It is no longer necessary to create an intermediate integer variable.

Performance improvements
- Sat solver — Improved performance of the Sat solver, particularly for the cumulative constraint.
- Glop solver— Improved numerical robustness of the Glop solver, which now returns even more accurate solutions to hard numerical problems.
- Flatzinc solver
- Greatly improved performance of the Sat backend for the flatzinc interpreter.
- Simplified the C flatzinc interface. For an example of the new interface, see
[https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs](https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs).

Bug Fixes
- Using the [`PathCheapestArc`](https://developers.google.com/optimization/reference/constraint_solver/routing/) heuristic on routing models with a single vehicle and side constraints would sometimes cause the solver to run for an excessively long time. This has been fixed by properly taking into account side-constraints.
- In Java, the routing solver would sometimes crash when solving vehicle routing problems. This has been fixed in the latest release.

</div>

November 2016

Running examples
- Introduced language specific targets to compile and run the examples. Please check this [page](/optimization/run_programs) for more details.

Sat
- Added support for constraint programming.
- Implemented the [diffn](http://web.emn.fr/x-info/sdemasse/gccat/Cdiffn.html), [cumulative](http://web.emn.fr/x-info/sdemasse/gccat/Ccumulative.html) , [circuit and subcircuit](http://web.emn.fr/x-info/sdemasse/gccat/Ccircuit.html) constraints.
- Implemented [the overlode checker](https://github.com/google/or-tools/blob/master/src/sat/overload_checker.h) on the basis of [Max Energy Filtering Algorithm for Discrete Cumulative Constraint.](http://vilim.eu/petr/cpaior2009.pdf)
- Implemented the [all different bound consistent propagator](https://github.com/google/or-tools/blob/master/src/sat/cp_constraints.h#L69) which implements better propagation for the AllDifferent constraint.

FlatZinc
- Implemented a [SAT solver](https://github.com/google/or-tools/blob/master/src/flatzinc/sat_fz_solver.h) for FlatZinc problems.

Constraint Solver
- Implemented the following constraints :
- [atMost](https://github.com/google/or-tools/blob/master/src/constraint_solver/constraint_solver.h#L1469): Sets an upper bound to the count of variables that are equal to a given value.
- [MakePathPrecedenceConstraint](https://github.com/google/or-tools/blob/master/src/constraint_solver/constraint_solver.h#L1680) and [MakePathTransitPrecedenceConstraint](https://github.com/google/or-tools/blob/master/src/constraint_solver/constraint_solver.h#L1684): Implement the precedence constraint for a set of pairs.

Routing
- Implemented [AddAtSolutionCallback](https://github.com/google/or-tools/blob/master/src/constraint_solver/routing.h#L653), which is a callback called each time a solution is found during the search.
- Removed the RoutingModel depot-less constructors. Specifying at least one depot in the routing model is now mandatory.

- Sat
- Extended scheduling API and modified examples (weighted_tardiness_sat, and jobshop_sat) to use it.
- Graph
- Added iterator traits to Graph classes.
- Or-tools distribution
- Nuget package is supported again.

Constraint solver
- solver
- Implemented NotBetween method to constrain a variable to be
outside a given interval.
- routing
- Added a parse of the model to check existing NotMember constraints as shown in this [example](https://github.com/google/or-tools/blob/master/examples/cpp/cvrp_disjoint_tw.cc#L125"), and use them in local search filters.
- Added local search profiling.
- Fix for local moves.

Linear solver
- Fixed SCIP status reporting.

Sat
- Implemented [SolveWithPresolve](https://github.com/google/or-tools/blob/master/src/sat/simplification.h# L373) method to simplify the usage of the SAT presolver.
- Regrouped search utils in src/sat/util.h|cc.
- Implemented SMT (Lazy Clause Generation) scheduling constraints: see [jobshop_sat.cc](https://github.com/google/or-tools/blob/master/examples/cpp/jobshop_sat.cc) and [weighted_tardiness_sat.cc](https://github.com/google/or-tools/blob/master/examples/cpp/weighted_tardiness_sat.cc).

Glop
- Improved performance by exploiting sparsity in more stages of computation.

Flatzinc
- Fixed bugs found by minizinc challenge.

Lp_data
- Continued simplification of templates in iterators.

Or-tools distribution
- C assemblies are now strongly named by default.
- Upgraded to Protobuf3.0.0.
- Added a Python [script](https://github.com/google/or-tools/blob/master/tools/check_python_deps.py) to check or-tools archive dependencies.