Constraints

Imagine you’re building a timetable for a school. No teacher can teach in two rooms at once. A class has at most six periods a day. The chemistry room is only free in the mornings. Such fixed conditions are called constraints. They don’t determine which timetable is the best one. They determine which timetables are allowed at all. Anything that violates a condition is thrown out immediately.

Why rules are often more important than the best solution

Many real-world tasks have an unfathomable number of possible solutions. With twenty classes and thirty teachers, there are more possible timetables than there are atoms in a piece of chalk. A computer simply cannot try them all. Constraints are what make the task solvable in the first place, because they rule out huge portions of these possibilities in one stroke.

There’s a second point on top of that: a computationally optimal solution is worthless if it breaks the rules. A delivery schedule that has drivers driving twelve hours straight isn’t clever, it’s illegal. In business and engineering, constraints are therefore often laws, safety regulations, or physical limits. They are not up for negotiation.

Experts distinguish between hard and soft constraints. Hard constraints must be satisfied, otherwise the solution doesn’t count. Soft constraints are preferences: avoid free periods where possible, don’t schedule sports in the first period. Soft constraints are scored with points, hard ones with a simple yes or no.

How a program narrows down the search space

Technically, such tasks are described using three ingredients. First, the variables, i.e. the open decisions, such as the time slot for each lesson. Second, the domains, i.e. which time slots are even possible in principle. Third, the constraints, which determine which combinations fit together. This combination is called a constraint satisfaction problem, or CSP for short.

A solver then works much like a person doing a sudoku. It tentatively fills in a value and looks at what follows from that. If it enters a seven in one cell, the seven disappears from all the cells in the same row. This passing on of consequences is called constraint propagation. It shrinks the set of options without a single case ever being fully computed out.

If a path leads into a dead end, the program takes a step back and tries a different assignment. This is called backtracking. A common misconception is to think of this as dumb trial and error. In fact, a good solver detects contradictions very early on and thereby saves itself billions of attempts.

From seating charts to restrictions in the chatbot

Constraints are embedded in many systems people use every day. Airlines use them to assign crews to flights, railway operators use them to schedule track occupancy, factories use them to plan machine time. Navigation services also compute with constraints, for instance a bridge that’s closed to trucks. In spreadsheets and databases, constraints ensure that nobody can store a birth date that lies in the future.

In current AI coverage, the word shows up in a second meaning. There it refers to limits a language model is supposed to stick to: no instructions for weapons, an answer only in JSON format, at most 200 words. Such stipulations, however, are less reliable than a genuine mathematical constraint. A language model can ignore them; a constraint solver cannot.

That’s why companies are increasingly combining both approaches. The language model makes a proposal, and a downstream program checks it against hard rules. If you read in the news that an assistant guarantees valid outputs, there’s usually exactly this kind of checking layer behind it.