3 ms·
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 pe
by cerved 7y ago
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)
- asdfasgasdgasdg 7y agoIt'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.
- cerved 7y agoDid 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.
- asdfasgasdgasdg 7y agoI 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.
- cerved 7y agoInteresting. 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.
- asdfasgasdgasdg 7y agoActually, 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.