Release of or-tools : January 2017.
New Features
Installing
- Introduced simpler procedures for installing or-tools, either from binary distributions or from source code. See Installing or-tools 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, 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.
Scheduling
- Added support for more data formats in the parser for the Project Scheduling Library.
Sat solver
- The Sat solver's cumulative constraint now accepts optional intervals, created with the
NewOptionalIntervalmethod. For an example, see
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.
Bug Fixes
- Using the
PathCheapestArcheuristic 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.