📈 #80 Where did the time go? Part III: structure (Part B)

Exploring advanced techniques to break symmetries.

The first time I found symmetries in a problem, at least that I’m aware of, was during my doctoral thesis.

The problem was highly symmetrical, I knew that. But one thing I didn’t know at that time? That those equivalent solutions had a specific name in the optimization field.

So I was blind in a sense, and I didn’t really take care of the issue.

I couldn’t even understand why another state-of-the-art algorithm was so good: it was breaking some symmetries that appeared in the problem.

Now everything is in place in my mind, and if I went back I said to my younger self:

Young Borja, you can get better solutions with not so much effort.

You’ll accelerate the search and won’t compare equivalent solutions

That way, you don’t have to develop a super sophisticated algorithm as you’re going to do to beat that state-of-the-art algorithm you found so difficult to beat.

(woah, that was a big relief) (no joke, real feelings here, this was the first time I said it to myself, and I struggled a lot finding a way to beat that algorithm)

Why the personal story matters here? Symmetry problems are often invisible until you know what to look for. Once you see them, you can't unsee them, and suddenly many "impossibly hard" problems become much more manageable.

Today in Feasible we’ll see Part B of symmetry issues in optimization problems, considering:

• 🔬 Advanced techniques to break symmetries

This topic deserves deeper exploration as I want to explain it in plain words that everyone can understand easily, so I’ll write a Part C (and the last one, I promise), to continue with the rest of the topic: ML-guided techniques and practical ways to dealing with symmetries.

Remember: this is the third part of the 6-part series of Where did the time go?; in case you missed it, here are Part I: benchmark before you fix and Part II: scale. And if you want to read Part A about symmetries, here you have it.

Are you ready? Let’s dive in… 🪂

🔬 Advanced techniques to break symmetries

These advanced techniques promise to solve previously impossible problems.

The reality? Most are research toys that sound impressive but rarely work in practice.

Here's what actually works (and what doesn't).

As these techniques require significant expertise, I suggest you try them if classical techniques aren’t providing enough speedup and you have development time for complex implementation, as they can enable previously unsolvable problems. The good news? Some of them are already implemented in solvers!

Let’s see them:

1️⃣ Orbital fixing and isomorphism pruning

This is a mathematically sophisticated technique that fixes variables based on symmetry group orbits.

And what are orbits? In group theory, an orbit is a set of elements that are equivalent under a group of symmetries. In optimization: variables are in the same orbit if you can swap them without affecting the problem structure or solution quality.

In this technique, the solver identifies orbits during solving and restricts them dynamically, eliminating redundant branching without the memory overhead of pre-generated constraints. This ends up speeding running time by 15% on MIPLIB instances and increases the number of instances solvable within time limits, according to research.

How does it work?

1. The solver detects symmetries in the model’s formulation, often using external graph tools that convert the constraint matrix into a bipartite graph where the left nodes are variables, the right nodes are constraints, and edges define the variables that appear in constraints.

2. It finds automorphisms, a way to relabel the graph that keeps all the connections identical. If you can swap variable labels without changing the graph structure, those variables are symmetric.

3. From the automorphisms, the solver builds symmetry groups… Or orbits.

4. During branch-and-bound, when the solver needs to branch on a variable, it chooses strategically from each orbit based on several predefined rules. For example, if truck1, truck2, truck3 are in the same orbit, it might always branch on truck1 first, then add constraints preventing truck2 and truck3 from taking the same values in this subtree. The rule to choose could be something like choose to branch on the largest orbit or branch on the orbit whose variables have the largest total solution value in the fractional solution.

5. It automatically adds constraints so that the solver doesn’t explore symmetric areas of the search space given the branching rule applied in the previous step.

Instead of adding all symmetry-breaking constraints upfront, it adds them only when needed during the search.

You have a great paper explaining it here¹.

This approach, while elegant in theory, can fail in practice for several reasons. Some of them:

• Subtle differences in data. 10.00 and 10.01 might seem identical, but they’re not, and the solver won’t know it in advance.

• Complex constraint structures. If you have conditional constraints that changes a property based on others (for example, reducing the capacity of a truck whenever it arrives to a specific warehouse because they introduce extra things into the truck), those constraints make the graph structure more complex and the automorphism detection might miss the symmetry.

• Computational limits. Automorphism detection becomes expensive at some point, and you cannot predict that upfront. In the paper, authors comment that “computing the automorphism group of the clique on 2000 nodes takes 85 seconds, while graphs of comparable size with little or no symmetry require fractions of a second.”.

📌 Takeaway: it may work automatically on simple, clean symmetric structures, benchmark problems, or small to medium-sized problems, but it may fail depending on your problem, so don’t trust them blindly.

At this point, things get trickier… and more exciting.

In the rest of this post, we’ll dive into two techniques that are less commonly known but could unlock serious performance in the right context.