Hacker News Reader

Comment by saagarjha | Hacker News Reader

I’m a bit uncertain about what Google OR-Tools is…it seems to be some sort of framework for solving optimization problems, but based on the example here I am curious how general such a tool can be, as normally I find that a “drop in” algorithms framework is generally quite difficult to make or use. Is anyone using this for something useful? Does it perform faster than a hand-rolled implementation tailored to the problem? Is it easier to use?

View on HN

It is. The two main components is the CP-SAT solver and the routing library (CP + local search).

As with all discrete optimization problems, a large part of performance and scalability comes down to how well you model the problem. Using a framework gives you the flexibility to focus on modeling and the ability to easily extend your problem to satisfy new constraints without the burden of maintaining an optimization algorithm. Generally speaking, there's no point in reinventing what's more than likely a worse wheel.

OR-tools is a state of the art OR framework. The CP-SAT solver has consistently won the Minizinc challenge the last few years and the routing library is a great local search framework.

It's also worth mentioning the fantastic OscaR, a Scala CP/CBLS library which I've used extensively in my masters thesis on vehicle routing. Gecode is another solid CP solver. Minizinc is an interesting project that aims to create a unified language to interface with a lot of different solvers (CP, SAT, MIP)

It's a lot of fun to play with. I used it at work to solve a partition assignment problem (you have data preintersected by property sets and a boolean query that constrains various properties, which set of preintersections are smallest for executing the query and cover all possible respondent documents?). Unfortunately it was not quite fast enough for our use case (runtimes of 50-100ms on harder queries) but it was fascinating to see provably optimal solutions to the problem.

Did you use a wrapper or work directly with the solver? If you require runtimes that are that small the compilation time into the proto-model fed into the solver is likely a bottleneck.

Usually the time horizon for solving these kinds of problems is on the scale of minutes/hours so the tool chain isn't optimized for that time span.

I tried both ways: compiling into the proto model to use the newer solver, and also using the older solver directly. But the profiling in each case showed that the solving time dominated. I don't think it was an issue of what the library is optimized for so much as it was just too big of a problem to solve in too little time. Even my hand rolled solution that gives non-optimal answers can take 5-10ms on difficult queries.

We ended up requiring users to adjust their queries a little to make it easier to spot the targeted preintersections. This seemed like a decent trade-off considering the latency impact of the alternative.

Interesting. I imagine this was for exhaustive search? If 100ms is too long it sounds like a CP solver might be the wrong tool for the job.

Actually, we tried both exhaustive search and sufficient search (where we had a soft-deadline and accepted the best solution reached within the deadline). Even with this dark launch found queries in our stream that had unacceptable delays. We were in contact with the team through the development process, so we at least had some reason for belief that we were using best practices. And you're right that ultimately the CP solver wasn't the right tool for this job -- simplifying the problem and giving up some capabilities was the solution. We had hoped that a general solution would be feasible, as that would allow expressing some things efficiently which we couldn't in our existing setup. But it was not to be.

I have used the or-tools VRP (vehicle routing problem) solver to optimize the drawing order of a pen plotter [1]. The Python API is a bit ugly but once I got past that, I found it had enough flexibility (e.g. asymmetric costs, disjoint routes) to represent the problem neatly.

1. https://nb.paulbutler.org/optimizing-plots-with-tsp-solver/

It depends on how good your hand-rolled implementation is.

Will it find the shortest path in a graph faster than your Dijkstra implementation? No, leave the simple problems to hand-rolled code. Can it run e.g. TSP faster than a dedicated TSP solver written by an expert? No, but it sure will beat what you or I can code up of TSP over a week. These things have great heuristics and can solve/approximate a very wide of variety of NP-hard problems much better than you could yourself.

I've used the CP solver to plan sports tournament schedules (make sure everybody gets equal time on the streamed field, make sure that special team that arrives with the late train doesn't have the first game, nobody has to play two games in a row, etc.). I made the mistake of using the Python frontend (which is much worse documented than the C++ API), but otherwise, it was a good experience. Constraint programming feels a bit odd at first, though.

There are a lot of optimization software tools available. One of my favorite is GLPK which is a free software implementation of AMPL. I created a employee scheduling framework for GLPK. It's listed as one of the examples in the download.

https://www.gnu.org/software/glpk/

Exactly my thinking.

<disclaimer>I work in a company that deals exclusively with OR. This means that we might be overly specialized for this product.</disclaimer>

I see OR-Tools as an educational product. The tool is easy to start tinkering with and it has superb documentation - even for people not specialized in combinatorial optimization.

What do you work on?

Can you link to your company. I've always thought it would be cool to 100% work on LP, MIP, and Nonlinear models. Do y'all use CPLEX/GUROBI for the big stuff and Prolog for more discreet items?

I'm not either completely sure about what "OR-Tools" really is, I've considered it an API and packaging to different solvers.

I've used the LP solver [0] for real problems (not on a massive scale), but it worked very nice. Basically a scheduling problem where we very quickly could give the user a pretty decent solution as a starting point that they then could customise. Dramatically shortened the time for the user for that process, compared to the previous random/heuristic "solution" we give.

[0]: https://developers.google.com/optimization/lp/glop

For the part I have used, it is a common API over various solvers (free and commercial), plus some google own solvers. It is pretty neat, but because of licensing reasons requires you to recompile it yourself to access all the free solvers.

I've utilized OR-Tools in conjunction with the CBC (Coin Branch and Cut) solver to solve a mold distribution optimization problem of plastic mold injectors for a client of ours. It was free and it got the job done very well. We used it in C# and it's pretty well documented. We tried LPSolve (55) and it was a pain to use and super slow. Also, commercial options like Gurobi and IBM's CPLEX are super expensive for smaller projects.

Using solvers for Linear Programming (LP) and Mixed Integer Linear Programming (MILP) problems can be ridiculously effective and generalizes very widely.

It can't solve every problem, but it can solve many more than you think, and there's an active research area around using them for solving problems.

Reply on news.ycombinator.com