Using OR-Tools CP-SAT for Scheduling Problems (opens in new tab)

I didn't consider SAT solvers to be AI, but searching for "ortools" points to https://developers.google.com/optimization which has a big "Google AI" indicator on it. Who cares, I thought.

But certain managers are now very keen on making a lot of noise about just how effectively their teams are using AI. So I took my four python scripts which together form a pipeline that solves a scheduling problem with OR-Tools and renamed my README.md to skill.md so agents would think it was for them.

The LLM does pretty much nothing except run the commands in order, CP-SAT does the real work and is being confused for AI. Yet when I demoed it people were like:

    > wow, neat, look at what's now possible in this dawning age of AI

I've not bothered to tell them that it's 1960's technology and that the AI part of it could also be adequately performed by a README with less than 100 words. I guess everything that the managers haven't heard of is now "AI" and golly look how effectively we're all using it.

Although this post discusses Constraint Programming - Satisfiability (CP-SAT) Solvers and Mixed Integer Problem (MIP) Solvers, it does not discuss Metaheuristic Solvers.

Metaheuristic solvers are different in that you don't need to model your problem as a mixed integer problem. Instead, all it cares about is having a function that returns something you can compare. This allows you to model your problem however you like. Some metaheurstic techniques include Simulated Annealing, Late Acceptance Local Search, and Tabu Search.

Metaheuristic solvers may not generate optimal solutions (after all, by their nature, they don't know the structure of the problem), but they generate "good enough" and "close to optimal" solutions. Metaheurstic solvers tends to beat MIP and CP-SAT for VRP, whereas MIP and CP-SAT are better for bin packing.

If you want to try using a Metaheuristic solver, I can recommend Timefold, which allows you to define your constraints using your domain objects in an incremental matter (it has SQL/Java-Streams like syntax, which in my opinion, is more readable than formulas) (disclosure: I work for Timefold).

The CP-SAT primer by Dr. Dominik Krupke is excellent for working with OR-Tools: https://d-krupke.github.io/cpsat-primer

When you have 50 technicians going to 500 sites, that is not a Traveling Salesman Problem. It might seem like a Vehicle Routing Problem but it isn't that either.

Batch a cheap process at night that runs CP-SAT solution. If someone calls in sick, be prepared to run it again with more horsepower so you can update it.

I'm a big fan of the CP-SAT solver. It was a remarkable piece of tech to learn about (especially Peter Stuckey's talks on lazy clause generation [1]).

I'd used it in a past life to build a Kubernetes scheduler [2] and tackle some cluster management problems.

[1] https://www.youtube.com/watch?v=lxiCHRFNgno [2] https://www.usenix.org/system/files/osdi20-suresh.pdf

I use CP-SAT for automated design problems. I need a guarantee on solution quality, so gen AI is a nonstarter. The problem formulation is quite messy and has constraints that can vary by locale. CP-SAT handles it pretty well.

The one thing I've been trying to model well are cover constraints where for each x : xs, there is some y : ys st. pred(x, y). I've tried both boolean matrices and index constraints, and they work but seem to be quite taxing on the solver. Maybe there's a better formulation.

In a past life we used OR-Tools for a problem of assigning data shards to serving tasks, where the data shards had heterogenous demands (e.g. some shards were low traffic but demanded sub millisecond latency targets and thus were served from RAM, others were higher traffic but could tolerate being served from flash, etc.). It's insane how expressive this thing is! But the problem got to be so large that we ended up having to hand-roll something less optimal because it would take multiple minutes to generate assignments -- think: millions of shards, tens of thousands of serving tasks, and I want to say it was ultimately nine dimensions of constraints.

I'm building a virtualisation cluster tool as an open source project, and I have used Minizinc + OR Tools CP-SAT to schedule virtual machines across hosts.

It allows me to put a host in maintenance mode and distribute all virtual machines away across the remaining hosts, it's really awesome.

Constraint Programming is quite interesting and hard, as you have to reformulate the problem domain in a way that is not always intuitive.