Constraint Satisfaction

Thinking Tools2.3 Establishing the Requirements

From the constraint-programming tradition, founded in the work of Ugo Montanari (1974) and Alan Mackworth (1977) and set out by Edward Tsang (Foundations of Constraint Satisfaction, 1993).

Lists every condition a solution must meet, separates hard limits from preferences, maps what is feasible, and only then looks for the best option within it.

An office move as three choices that must fit eight constraints at once

Pick a site, a month, and a layout. Every constraint the combination breaks shows under the rows: a hard limit rules the plan out, a soft one only costs something. Of the eighteen combinations, find the ones no hard limit touches, then choose among those on the soft costs. Illustrative.

Site

Move in

Layout

  • No constraint touches this combination.Hard: the old lease ends September 30, so an October move leaves the team two weeks with no office.Hard: the downtown floor is occupied until the end of July.Hard: the Riverside floor is too narrow for team rooms that seat 90; the fire exits will not allow it.Hard: the airport park's open floor exceeds the budget once its noise insulation is added.Soft: no transit, so the 22 staff without cars need a shuttle, about $60K a year.Soft: June is peak sales season; the move has to run over a weekend, at overtime rates.Soft: the engineers asked for quiet space, so an open floor costs goodwill and booths.Soft: downtown rent runs $8 a square foot above the others, inside the budget but the dearest.Feasible, and the cheapest plan that breaks no hard limit.Feasible, and the only plan that gives the engineers quiet rooms without a shuttle; the cost is the rent.
  • No constraint touches this combination.Hard: the old lease ends September 30, so an October move leaves the team two weeks with no office.Hard: the downtown floor is occupied until the end of July.Hard: the Riverside floor is too narrow for team rooms that seat 90; the fire exits will not allow it.Hard: the airport park's open floor exceeds the budget once its noise insulation is added.Soft: no transit, so the 22 staff without cars need a shuttle, about $60K a year.Soft: June is peak sales season; the move has to run over a weekend, at overtime rates.Soft: the engineers asked for quiet space, so an open floor costs goodwill and booths.Soft: downtown rent runs $8 a square foot above the others, inside the budget but the dearest.Feasible, and the cheapest plan that breaks no hard limit.Feasible, and the only plan that gives the engineers quiet rooms without a shuttle; the cost is the rent.
  • No constraint touches this combination.Hard: the old lease ends September 30, so an October move leaves the team two weeks with no office.Hard: the downtown floor is occupied until the end of July.Hard: the Riverside floor is too narrow for team rooms that seat 90; the fire exits will not allow it.Hard: the airport park's open floor exceeds the budget once its noise insulation is added.Soft: no transit, so the 22 staff without cars need a shuttle, about $60K a year.Soft: June is peak sales season; the move has to run over a weekend, at overtime rates.Soft: the engineers asked for quiet space, so an open floor costs goodwill and booths.Soft: downtown rent runs $8 a square foot above the others, inside the budget but the dearest.Feasible, and the cheapest plan that breaks no hard limit.Feasible, and the only plan that gives the engineers quiet rooms without a shuttle; the cost is the rent.
  • No constraint touches this combination.Hard: the old lease ends September 30, so an October move leaves the team two weeks with no office.Hard: the downtown floor is occupied until the end of July.Hard: the Riverside floor is too narrow for team rooms that seat 90; the fire exits will not allow it.Hard: the airport park's open floor exceeds the budget once its noise insulation is added.Soft: no transit, so the 22 staff without cars need a shuttle, about $60K a year.Soft: June is peak sales season; the move has to run over a weekend, at overtime rates.Soft: the engineers asked for quiet space, so an open floor costs goodwill and booths.Soft: downtown rent runs $8 a square foot above the others, inside the budget but the dearest.Feasible, and the cheapest plan that breaks no hard limit.Feasible, and the only plan that gives the engineers quiet rooms without a shuttle; the cost is the rent.
  • Hard: the old lease ends September 30, so an October move leaves the team two weeks with no office. (month: October)
  • Hard: the downtown floor is occupied until the end of July. (site: Downtown tower, month: June)
  • Hard: the Riverside floor is too narrow for team rooms that seat 90; the fire exits will not allow it. (site: Riverside, layout: Team rooms)
  • Hard: the airport park's open floor exceeds the budget once its noise insulation is added. (site: Airport park, layout: Open floor)
  • Soft: no transit, so the 22 staff without cars need a shuttle, about $60K a year. (site: Airport park)
  • Soft: June is peak sales season; the move has to run over a weekend, at overtime rates. (month: June)
  • Soft: the engineers asked for quiet space, so an open floor costs goodwill and booths. (layout: Open floor)
  • Soft: downtown rent runs $8 a square foot above the others, inside the budget but the dearest. (site: Downtown tower)
  • Feasible, and the cheapest plan that breaks no hard limit. (site: Riverside, month: August, layout: Open floor)
  • Feasible, and the only plan that gives the engineers quiet rooms without a shuttle; the cost is the rent. (site: Downtown tower, month: August, layout: Team rooms)

An example

A 90-person software company had to leave its building when the lease ended on September 30. The facilities manager was handed three sites, three possible move months, and two layouts, plus a stream of opinions: finance wanted the cheapest site, the engineers wanted quiet rooms, and sales wanted no disruption in June. Every meeting compared favorite plans, and each favorite turned out to break something someone else knew about.

She stopped comparing plans and listed constraints instead, eight in all, and asked each owner whether theirs was a limit or a preference. Four were limits. An October move left the team without an office. The downtown floor was occupied until August. The riverside floor was too narrow for team rooms under the fire code. The airport site's open floor broke the budget once insulation was added. That left six of the eighteen combinations. The other four constraints were costs, and only one feasible plan gave the engineers their rooms without paying for a shuttle. The team chose it in one meeting, knowing exactly what the higher rent bought.

Why it works

Asking which plan is best invites people to argue for whole plans, each built around the constraint its author cares about. The argument cannot converge, because nobody can see the full set of conditions at once. Listing the constraints first, and separating the limits from the preferences, turns the question around: first what is possible, then what is best among the possible.

The hard limits do most of the work. Each one strikes out whole groups of combinations, and checking them early saves the effort of polishing plans that could never happen. Once only feasible plans remain, the soft constraints become an honest tradeoff with prices attached. A preference that would have stalled the debate becomes one line item among the survivors.

The thinking behind it

Ugo Montanari Ugo Montanari, a computer scientist at the University of Pisa, laid the formal ground in Networks of Constraints (1974), a paper written for picture processing. He represented constraints as relations among variables, so that a problem becomes a network, and studied the minimal network, in which every allowed pair of values can be extended to a full solution. The idea that constraints can be stated, combined, and tightened on their own, before any solution is sought, runs through the whole field.

Alan Mackworth Alan Mackworth, an artificial intelligence researcher at the University of British Columbia, showed in Consistency in Networks of Relations (1977) why plain trial and error does badly on these problems: the search keeps rediscovering the same dead ends. His remedy was to prune first, removing values that cannot satisfy a single constraint, then pairs that clash, before attempting a full solution. Striking out the impossible before comparing the possible is that move at human scale.

Edward Tsang Edward Tsang, a computer science professor at the University of Essex, wrote Foundations of Constraint Satisfaction (1993), the first book to define the scope of the field: finding assignments to a set of variables that meet every one of a set of constraints. It gathered the search and pruning methods into one account. Scheduling, timetabling, and configuration problems all share its shape: many choices, each limited by the others.

How to run it

  1. List every constraint. Ask each owner (finance, legal, facilities, the teams affected) for theirs, and write each as a testable condition.
  2. Mark each hard or soft. Ask the owner whether the plan is dead if it breaks this, or only more expensive; a limit with a price is soft.
  3. Name the choices and their values. Write each decision to be made, such as site, date, and layout, with the values each can take.
  4. Strike out what a hard limit forbids. Remove every combination that breaks one, starting with the limits that remove the most.
  5. Go back to owners if nothing survives. Show each owner what their limit costs, and ask whether it can move.
  6. Trade off the soft constraints openly. Price each one among the survivors so the final choice says what it gives up.
  7. Ask what the list missed. Before deciding, show the shortlist to someone outside the group; a forgotten limit surfaces fast.

Where it goes wrong

The first failure is calling everything hard. Owners protect their preferences by calling them limits, and the feasible set comes out empty. When nothing survives, test each hard constraint by asking what breaking it would actually cost; most have a price.

The second is the missed constraint. A plan that passes every listed limit can still fail on one nobody wrote down, such as a union rule or a landlord's approval. Show the shortlist to the people who will carry out the plan before choosing.

The third is optimizing too early. A team that ranks plans before checking the hard limits spends its energy on a favorite that turns out to be impossible, and then defends it. Check feasibility first.

When to use something else

  • Binary Criteria Screen. When the options are already whole plans and each can be tested pass or fail on its own.
  • Linear Programming. When the constraints and the goal are all numbers, and the best mix of quantities can be computed.
  • Weighted Decision Matrix. When the feasible plans are known and the remaining question is how to weigh their soft differences.

Where it sits in SOLVE eX

Go to the source

  • Networks of Constraints: Fundamental Properties and Applications to Picture Processing, Information Sciences 7, 1974
  • Consistency in Networks of Relations, Artificial Intelligence 8, 1977
  • Foundations of Constraint Satisfaction, 1993

Back to the catalog