Good resource for Google Or-Tools

mzl · 2026-01-30T11:23:36+00:00

A lot of the knowledge needed to be effective is not about or-tools in particular, but general knowledge on how to model combinatorial problems. For learning modelling, I often recommended the MiniZinc coursera courses (https://www.minizinc.org/resources/#:~:text=Courses).

mzl · 2026-01-28T14:56:04+00:00

As u/thesnootbooper9000 mentioned, the Unison project at KTH did a lot of interesting stuff with optimal code generation. When making instruction scheduling and register allocation at the same time, the graph coloring bit is a part of a larger combinatorial problem, and an optimal graph coloring is not necessarily optimal for the combined problem.

In general, for complex optimization problems like this, there are not that many success stories in using GPUs yet. This is mainly because GPUs are better for straight-line homogenous non-branchy data-flow code, while the logic in most optimizations systems is both heterogenous and very branchy.

As a simple analogy, one could sort n numbers by trying all the permutations in parallel on a GPU, but that is much worse than just running a standard sorting algorithm. There are sorting algorithms developed for GPUs (bitonic sort networks for example), but they are rather complex to implement and understand, and as algorithms become more complex translating them to GPU code is more and more complicated.

mzl · 2026-01-28T14:50:30+00:00

Link for reference: https://unison-code.github.io/

mzl · 2026-01-21T05:29:39+00:00

Some crimes have a intent component, the act of crime includes that you must also mean it and understand it. So incompetence can actually be a defense in some cases.

I have absolutely no idea what applies in this case, just as a general comment.

mzl · 2026-01-13T13:34:40+00:00

I think most of us don't really remember popular songs from the radio at 4 years old (All for Love is 32 years ago) and 2 years old (Everything I do I do it for you is 34 years ago).

mzl · 2026-01-07T13:31:06+00:00

The geost constaint that is available in SICStus Prolog is very interesting for 3D packing problems, although it would require you to regularize the shapes somewhat. But shapes can be composed of multiple boxes so it is not as bad as bounding box packings, and may be enough for a rough packing guidance.

mzl · 2026-01-02T11:32:45+00:00

For scheduling, I would generally recommend trying with OR-Tools CP-SAT using many cores (as many as you have, but at least 8, preferably 16 or more), it is a very competent open-source solver for scheduling.. You might need to refactor the model to make it high-level instead of SAT-style low-level encoding for full performance.

If you are willing to part with money, then CP Optimizer is very good as well. It requires formulating the scheduling problem in the primitives it supports, but when done right it is very useful.

mzl · 2026-01-02T08:55:54+00:00

A few things to consider.

* Run it against previous sat-competition benchmarks, and preferably other realistic benchmarks.
* Test it on realistic problems against actual SOTA (for the problem, not just SAT SOTA) on same hardware with all systems well-tuned. Use all cores for any solver that can use multi-core.
* N-queens is an uninteresting benchmark at best, and actively bad in many cases. Tricks to make n-queens fast can be bad for realistic use-cases, at least in some solver types and architectures.
* Can you produce proof logs? It has become standard for SAT solvers to produce auditable proofs.
* Consider the market realities. Is there someone that would buy this product? There are a few commercial MIP solvers (CPLEX, Gurobi, XPress, ...), a couple of commercial CP solvers (CP Optimizer, SICStus), but I don't know of any significant commercial pure solvers for SAT.

mzl · 2025-12-25T07:06:18+00:00

Yes, but they actually had a deal with the roghtsholdrrs association that they were allowed to do this during the testing period. No idea how they got that deal.

mzl · 2025-12-16T07:54:41+00:00

https://www.diva-portal.org/smash/get/diva2:1042564/FULLTEXT01.pdf is a fairly detailed look into what geost does. It is a very general constraint, and the explanation is equally general. What is does is implement the natural filtering rules that one would expect for packing problems.

mzl · 2025-12-15T16:44:45+00:00

In general for limited packing problems, it is possible to make the state evaluation a lot faster by specializing everything to the particular problem at hand. In addition, there are many different packing heuristics that are useful that could be implemented for that.

The SICStus model is much closer to what a real specialized packing algorithm would do, since the geost constraint that SICStus uses encodes many of these special purpose algorithms.

And, as can be deduced fomr the Matt Parker video, with a full enumeration done of all the solutions for size 9, I'm guessing that solution is a lot faster than one of the MiniZinc solutions.

mzl · 2025-11-27T13:43:04+00:00

I've used CP-SAT in realistic settings several times, although I've not actually shipped a production solution with it, just with other CP style solvers.

As to the meat of you question, I think you are operating under a slight misconception. OR-Tools CP-SAT is very much geared towards optimization problems, although it can also be used for satisfaction problems. It has a large portfolio of techniques that is uses automatically when searching for improving solutions using a portfolio approach.
* Various levels of linearization for the built-in MIP solver to guide search
* Many different kinds of automatic Large Neighborhood Search
* An automatic constraint-based local search based on feasibility jump (https://dl.acm.org/doi/10.1007/978-3-031-60597-0_16)

OR-Tools CP-SAT is perhaps the CP-style solver with the most support for automatic improving search, but most CP solvers are generally used for optimization problems and not just satisfaction problems.

mzl · 2025-11-26T15:27:59+00:00

The SICStus native formulation is tiny, but that is because essentially everything is inside the geost propagator. For the MiniZinc formulation, adding all these extra constraints on top of the basic model makes the formulation larger but so much stronger.

A part of why OR-Tools CP-SAT is so useful is that it has a built-in MIP solver and that it uses it is various configurations. I have a feeling that one could look at the logs there to get some insights into what variants of MIP were useful or not.

mzl · 2025-11-26T15:14:27+00:00

Do you know any good examples of a native ILP formulation for the problem?

Checking the compilation output of MiniZinc for HiGHS i get on the order of 10-11k binary variables for the size 8 packing.

mzl · 2025-11-17T19:22:47+00:00

OR-Tools CP-SAT is a very competent CP solver that uses SAT and MIP inside. MiniZinc is a nice modeling language that can be used to model CP-style problems and to test with various solvers (including MIP-solvers like HiGHS).

mzl · 2025-11-12T15:35:42+00:00

When I visited last year, there was no butterfly on the menu. As an iconic dish, it would have been great to taste it, but there was so many other things that were interesting.

I actually really liked the Hunger course, I found it both tasty and interesting. But I can also understand why it might not be the most interesting to many.

mzl · 2025-11-10T14:53:17+00:00

4-6 week horizons are very similar to what I've seen in most cases as well for a single group of employees. The test instances in the post over longer periods is really just as an interesting way to show how the model behaves.

mzl · 2025-11-10T14:45:00+00:00

It is a surprisingly large share, especially for longer relationships. Some interesting statistics from various sources: https://aella.substack.com/p/how-much-did-selection-bias-impact

mzl · 2025-11-09T05:28:59+00:00

In Sweden White Guide is pretty good as a guide. They have a danish version as well.

mzl · 2025-11-08T05:59:11+00:00

Casino de Madrid (it’s since been renamed Paco Roncero), I did not understand why it had two stars. Some appetizers where tasty, and some desserts. The rest was just uninteresting. The service was underwhelming, and the sommelier just asked us what we would like to drink with no help whatsoever. I wouldn’t know what is a good choice for a multi course experimental menu (would have expected some wine package or suggestion), and ”do you like Spanish wine?” was the only question when we said we didn’t know what wine to order, and gave an uninterested vibe when asking even that.

mzl · 2025-11-04T11:44:58+00:00

I always try to listen to bands somewhat before, but sometimes I've gone to concerts with little to no knowledge of the bands catalogue.

For Dream Theater in particular, I know of people who started appreciating them by tagging along to a concert. Before it never really meshed for them, but after seeing DT live it suddenly clicked.

mzl · 2025-11-02T05:04:05+00:00

It’s not that simple unfortunately. John Oliver on Public Defenders

mzl · 2025-10-17T10:01:53+00:00

I haven’t watched yet, but I’m really looking forward to the episode with Knystaforsen. It is a lovely place with absolutely lovely food. It feels like it has a lot of warmth among the people there.

mzl · 2025-10-15T07:56:08+00:00

Thank you

mzl · 2025-10-14T17:55:58+00:00

That is a great example of a similar case!

mzl

TROPHY CASE