📈 #81 Where did the time go? Part III: structure (Part C)

The last time I found symmetries in a problem was a couple of years ago.

We were solving planning problems in Trucksters from a more tactical-strategic point of view.

In those planning problems, you don’t have specific constraints that apply to trucks or drivers. You deal with more generic things like “this should be a box trailer” without considering the specific one, or “a driver should take this load” but without considering the tachograph that applied in the near past to a specific driver.

So it’s a highly symmetric problem.

We needed to balance development time vs ROI, and we ended up adding some classical techniques to break them.

But I’ve been investigating a bit more, and as I’m more aligned over time with the integration of ML and OR techniques, I wanted to give it a try here too.

So today in Feasible we’ll see the last part about symmetry issues:

• 🔬 ML-guided techniques to break symmetries

• 🛠 Practical ways to dealing with it: when not to break symmetries and when to stop breaking them, tips for quick-wins, and techniques to try first

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.

Are you ready? Let’s dive in… 🪂

🔬 ML-guided techniques to break symmetries

Most "ML for optimization" is academic research that sounds impressive but has limited practical value.

However, there are a few ML approaches for symmetry breaking that actually work in practice.

Instead of hardcoding which technique to use, when, and how aggressively… ML can help you answer:

“What symmetry-breaking strategy should I try for this problem?”

Let’s break down how this works.

1️⃣ Pattern learning

This is the simplest and most practical idea.

You train a model to predict the best symmetry-breaking strategy based on features of your optimization instance.

What you feed the model:

• Problem characteristics: number of variables, constraint types, constraint density, problem structure.

• Historical technique performance: what happened when you used lex, precedence, orbitopal, etc., on similar problems?

• Solver behavior patterns: average nodes per second, gap closure rate, memory usage growth, time to first solution in past runs.

• Instance-specific features: symmetry group size, number of identical objects, constraint graph connectivity.

What the model learns:

A mapping from problem features to technique effectiveness. For example: "Problems with >200 variables + assignment structure + high constraint density → VR technique works best (0.8 probability of >50% speedup)".

Every time you solve a new instance, you first extract its features, then the model tells you which techniques are most likely to help.

This helps automate one of the hardest parts: making the right pre-solve decision.

This only works if you have enough historical data and solve similar problem types repeatedly. Don't expect magic from 5 training examples.

If you want to explore more, read Khalil et al. (2017)¹.

2️⃣ Adaptive constraint generation

This takes the previous idea a step further: instead of choosing a known technique, the ML model learns how to generate or adapt symmetry-breaking constraints themselves.

How does it work?

1. Start with constraint templates: you define families of constraints like x₁ ≤ x₂, if y then x, etc.

2. Monitor performance: test different constraint combinations and track results.

3. Learn constraint patterns: ML identifies which constraint types work for which problem characteristics, e.g., “for large vehicle routing problems, constraints forcing low-indexed vehicles to fill first help more than lex constraints.”

4. Generate new constraints: use decision trees, attention mechanisms, or symbolic learning to create novel, instance-specific constraints (e.g., x₂ ≤ x₄ but not x₁ ≤ x₃, based on data structure).

5. Iterate: after each solve, the model improves its constraint-generation logic.

What do you get? A concrete set of constraints to inject into your model before solving. This can be plugged into modeling pipelines to customize symmetry-breaking automatically per instance.

🚨 This is research-level complexity. Very few practitioners have implemented this successfully. Most attempts fail because it requires lots of data and compute, and isn’t plug-and-play.

This research-level approach is explored in Ding et al. (2019)² and Tang et al. (2020)³.

3️⃣ Historical performance data

This is the most realistic ML application: learning from your own solve history to make better decisions.

What you track:

• Technique effectiveness by problem type: like “for this problem with <100 customers, HC1 performed well, with >200 customers HC1 was the most effective technique”.

• Input ordering strategies: are lex sorted jobs, grouped locations, etc impacting solve time?

• Constraint combinations: which techniques work well together vs. which conflict.

• Problem characteristics that predict symmetry issues: variable count, constraint density, symmetry group size that correlate with performance problems.

The model learns your personalized "symmetry breaking playbook", and not only that: your optimization system gets smarter the more you use it.

Want a deep dive on algorithm selection for combinatorial search problems? Read Kotthoff (2012)⁴.

📌 Reality check: Pattern learning and historical tracking are essentially the same approach - historical tracking is just the simpler, more practical version that most people should start with.

The techniques above show what's possible. But which should you try first? When should you skip symmetry breaking entirely? What about previous classical techniques? Let’s see everything now: