Relax everyone, if you ever feel stuck just… no, that’s all, that’s the answer. If you ever feel stuck, relax.

Constraints are often the first thing you should question, not the first thing you should obey. For example, imagine you’re optimizing an event seating chart based on the compatibility of people sitting next to each other. The real question is not “How do we compute the perfect seating chart?” It is “How do we reframe the problem so that we find the best solution for the things we actually care about?”

Constraint Relaxation

A seating chart looks simple until you figure out the constraints. Aunt Carol shouldn’t sit next to her ex. The client wants all sponsors visible. The couple’s college friends need one table. The shy coworkers shouldn’t be stranded with strangers. Suddenly, the chart is no longer a list of seats. It’s a messy constraint system with a social layer underneath it. The constraints we start with could look something like this:

  1. The space can hold 10 tables of 8
  2. The invite list has 80 guests
  3. Everyone at each table should be 95% compatible with each other (in this example you already magically calculated numeric compatibility scores for the algorithm)

After putting this into your algorithm, zero seating charts meet the requirements. This is where relaxation enters. In optimization, relaxation means solving a slightly easier version of the original problem by softening or removing some constraints. For a seating chart, that might mean lowering your expectations for how happy people will be with their tables. A simple way to do that is by lowering your “compatibility” metric requirement, but this is a manual process and leaves room for errors. A better way would be to replace the hard limit with a continuous range.

Continuous relaxation

Continuous relaxation replaces discrete yes-or-no choices with value ranges. Instead of deciding whether a table is compatible or not, we try to find the seating arrangement that maximizes overall compatibility, regardless of the score. This will produce a ranking of seating charts by the average compatibility of all tables. Much more useful. After going through this, what if you find that even the best seating chart has a low score? There might be something else going on.

Lagrangian relaxation

Lagrangian relaxation takes a different approach. Instead of turning hard constraints into ranges, it replaces hard constraints with penalties. You might think a table can’t have more than eight people, only 10 tables will fit, and all 80 guests must be invited; but that’s not true. Anything can change, for a price: in money, in comfort, in social stigma. Maybe there’s a group of 9 that only knows each other, so you make one crowded table for them, or there’s one person that’s incompatible with everyone, so you could make the choice to leave them off.

Mathematically, this is elegant because it converts “forbidden” behavior into “expensive” behavior. That’s often the difference between a dead-end model and a solvable one. In practice, Lagrangian relaxation gives you a way to negotiate with the constraints instead of feeling like there’s nothing you can do.

Visualizing the process

To visualize the process of refining this problem, see the chart below working from left to right. The hard constraints (in rectangles) are relaxed to soft constraints (in ovals) with the methods described above.

  ---
title: Event Seating Chart
---
graph TD
  Plan["Plan an event"] -->
  Choose{"Find a seating strategy"}
  
  Choose --"First pass"-->
  Tables["10 tables of 8"] -->
  Guests["80 guests"] -->
  Compatibility[">95% compatibility per table"] -->
  Result>"Result: No seating map fits the criteria"]
  
  Choose --"Constraint Relaxation"-->
  Tables2["10 tables of 8"] -->
  Guests2["80 guests"] -->
  CompMin[">50% compatibility per table"] -->
  Result2>"Result: Many suboptimal seating maps"]
  
  Choose --"Continuous Relaxation"-->
  Tables3["10 tables of 8"] -->
  Guests3["80 guests"] -->
  CompNext3(["Maximize the average compatibility of all tables"]) -->
  Result3>"Result: Ranked seating maps"]
  
  Choose --"Lagrangian Relaxation"-->
  Tables4(["10 tables, but you can add more with a penalty"]) -->
  Guests4(["80 guests, but you can remove guests with a penalty"]) -->
  CompNext4(["Maximize the average compatibility of all tables"]) -->
  Result4>"Result: Ranked seating maps with other options included"]

Why rethinking wins

The lesson is that many impossible problems are impossible only because they’re posed too rigidly. If you insist on solving every rule exactly, you may get stuck. You don’t always get the best answer by pushing harder on the original question. Sometimes you get it by asking for a better one. That’s how a hopeless dilemma becomes a manageable one.