Menu
I am currently evaluating googles or-tools and just noticed that it's not really a solver on its own but mainly an interface to other solvers. What I'd like to know is which solvers this framework uses for constraint and routing problems.
I have already looked thoroughly through https://developers.google.com/optimization/, but only found that
But on the CP & VRP info/guide sites there is no indication as to what solver is used for these problems...
Does anyone happen to know which solver is used for CSP / VRP or have you found something I overread?
998
The primary OR-Tools linear optimization solver is Glop, Google's linear programming system. It's fast, memory efficient, and numerically stable.
Constraint optimization, or constraint programming (CP), is the name given to identifying feasible solutions out of a very large set of candidates, where the problem can be modeled in terms of arbitrary constraints.
About OR-Tools 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.
Google OR-Tools is a free and open-source software suite developed by Google for solving linear programming (LP), mixed integer programming (MIP), constraint programming (CP), vehicle routing (VRP), and related optimization problems.
To solve this VRP, you need to create a distance dimension, which computes the cumulative distance traveled by each vehicle along its route. You can then set a cost proportional to the maximum of the total distances along each route. Routing programs use dimensions to keep track of quantities that accumulate over a vehicle's route.
After modeling your problem in the programming language of your choice, you can use any of a half dozen solvers to solve it: commercial solvers such as Gurobi or CPLEX, or open-source solvers such as SCIP, GLPK, or Google's GLOP and award-winning CP-SAT.
OR-Tools offers two main tools for solving integer programming problems: The MPSolver, described in a previous section. The CP-SAT solver, which we describe next. For an example that solves an integer programming problem using both the CP-SAT solver and the MPSolver wrapper, see Solving an Assignment Problem.
For an example that solves an integer programming problem using both the CP-SAT solver and the MPSolver wrapper, see Solving an Assignment Problem. To increase computational speed, the CP-SAT solver works over the integers. This means you must define your optimization problem using integers only.
This was answered multiple times on the mailing list/github issues:
the routing library uses a CP solver with a Local Search implementation on top. See this Github issue
The CP-SAT solver uses a lazy clause generation solver on top of an SAT solver. The best description is a presentation from Peter Stuckey called Search is Dead. There is also a video on YouTube from the CPAIOR master class. https://youtu.be/lmy1ddn4cyw
65
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
