Can a solution violate a preference?

Yes, if the preference is soft and the assignment still satisfies the hard constraints.

Do all preferences need numeric weights?

No. Some formalisms use qualitative orderings or priority levels.

Does changing a weight necessarily change feasibility?

No. In the example it changes ranking while leaving the six feasible assignments unchanged.

AI Glossary / Graphs and symbolic AI / Advanced

Preference constraints

Definition

Preference constraints express which assignments are more desirable in a constraint problem, rather than simply declaring which assignments are permitted. They are often represented as soft constraints with costs or scores. A solver can then seek a preferred feasible solution while respecting any hard requirements. The meaning of 'best' depends on how the preferences are represented and combined.

What it means

Many practical problems have several acceptable answers. A preference records that inconvenience without necessarily forbidding the meeting. This separates feasibility from desirability. If a requirement really must hold, it belongs among the hard constraints; representing it as a negotiable preference changes the problem.

How it works

Define variables and their possible values, specify mandatory constraints, and describe preferences over relevant variable combinations. One common representation assigns a nonnegative penalty when a preference is not met. The objective minimizes the sum of these penalties over feasible assignments.
The weights determine trade-offs. Violating one high-weight preference can cost more than violating several low-weight preferences. Other systems may use priority levels or different ways to compare alternatives, so a weighted sum is a modeling choice rather than the universal meaning of preference. A solver searches for a feasible assignment with a favorable objective value; demonstrating global optimality requires evidence beyond finding a satisfactory-looking assignment.

Three practical examples

A meeting scheduler treats room capacity as mandatory but a preferred time as negotiable. It can propose a less convenient time when that is the best feasible arrangement.
A production scheduler requires each operation to use compatible equipment while preferring fewer changes between product types. The preference guides selection among schedules that meet the equipment requirements.
A delivery planner requires each package to be assigned to a vehicle while preferring compact routes. The preference score must represent what the organization actually wants to trade off, rather than accidentally rewarding one convenient measurement at the expense of another objective.

Think of it this way

Imagine choosing a restaurant with a group. Having enough seats might be essential, while a short walk and a favored cuisine are preferences. An available restaurant can still be acceptable when it misses one preference.

Worked example

Two meetings, A and B, each occupy one of three time slots numbered 1, 2 and 3. They use the same room, so the hard constraint is A different from B. There are nine possible assignments before this constraint and six feasible assignments afterward.
Meeting A prefers slot 1, with a penalty of 4 if assigned elsewhere. Meeting B also prefers slot 1, with a penalty of 3 if assigned elsewhere. A third preference favors adjacent slots, adding a penalty of 2 when the absolute difference between their slot numbers is not 1. The objective is the sum of these three penalties.
For (A, B) = (1, 2), A's preference is met, B incurs 3, and adjacency is met: total 3. For (1, 3), the total is 0 + 3 + 2 = 5. For (2, 1), it is 4 + 0 + 0 = 4. For (2, 3), it is 4 + 3 + 0 = 7. For (3, 1), it is 4 + 0 + 2 = 6. For (3, 2), it is 4 + 3 + 0 = 7.
The minimum is 3 at (1, 2). This is globally optimal for the stated model because all six feasible assignments have been evaluated. It misses B's preferred slot but remains feasible. The assignment (1, 1) would satisfy both time preferences, but the hard room constraint excludes it regardless of its preference score.
Now increase B's time-preference penalty from 3 to 6. The six totals become 6, 8, 4, 10, 6 and 10 in the same order. The optimum changes to (2, 1), with cost 4. The feasible set has not changed; only the ranking has. Weights therefore encode decisions about whose inconvenience can be traded against whose, not merely computational tuning parameters.

Illustrative case study

In a fictional scheduling pilot, users complain that B repeatedly loses its requested time. The team reproduces the first calculation and confirms that the solver is following the supplied weights. It discusses those weights with the people responsible for scheduling and evaluates the revised values above.
The team also examines whether recurring allocations need a broader measure across several weeks. Optimizing each week's score independently would not automatically account for repeated inconvenience to the same group. It records the chosen objective and explains each proposal's unmet preferences. The process distinguishes a solver error from a preference model that does not yet express the organization's intentions.

Common misconceptions and mistakes

A soft constraint is not a hard requirement that the solver occasionally ignores by mistake. Its negotiability is part of the model. Nor does minimizing the number of violated preferences necessarily minimize weighted cost: different violations may have different penalties.
An arbitrary large penalty is not automatically equivalent to a hard constraint. Other costs may outweigh it unless the relevant bounds and feasibility assumptions are established. Another mistake is calling a returned solution optimal when the search only found a good candidate. Finally, a low aggregate cost can conceal an undesirable distribution of inconvenience across people or repeated decisions.

Business use

Preference constraints make operational trade-offs explicit and reviewable. Identify which requirements are mandatory, explain the meaning of each preference and document how scores combine. Test alternative weight choices on representative scenarios. Present a solution's unmet preferences alongside its overall score so users can understand the trade-offs. For repeated decisions, consider whether the objective needs to account for accumulated effects. Keep feasibility checks separate from preference scoring, and report whether optimality was established or whether the result is the best candidate found within the available search effort.

Check your understanding

Why is (1, 1) excluded?

Answer: Both meetings would occupy the same room at the same time.

What is the original optimum?

Answer: A in slot 1 and B in slot 2, with cost 3.

What changes after B's penalty becomes 6?

Answer: The optimum becomes A in slot 2 and B in slot 1, with cost 4.

Related terms

Constraint satisfaction problem
Constrained optimization
Objective function
Preference elicitation
Soft constraint
hard constraint
weighted penalty
feasibility
optimality

Learn next

Make adjacency mandatory instead of preferred. Recalculate the feasible set and compare the optimal assignments under both choices of B's time-preference penalty.

Sources

Poole and Mackworth, Optimization: https://artint.info/3e/html/ArtInt3e.Ch4.S8.html AIMA glossary, preference constraints: https://github.com/aimacode/aima-glossary/blob/master/glossary.md

Previous: Preference alignment Next: Preference elicitation