12

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

  • for linear optimization Google's "in-house, open-source GLOP" is used
  • for network flow optimization an own solver seems to be used ("OR-Tools provides several solvers for network flow problems in its graph libraries.")
  • for mixed integer programming the open-source programm "COIN OR branch&cut" is used by default (but SCIP, GLPK and Gurobi can be integrated)

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?

Laurent Perron
  • 8,594
  • 1
  • 8
  • 22
javaguy
  • 149
  • 1
  • 6

1 Answers1

21

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

Laurent Perron
  • 8,594
  • 1
  • 8
  • 22