Can every preference be satisfied?

Sometimes, but the worked example shows why that need not be compatible with the hard constraints.

Does an optimal assignment have to be unique?

No. Different feasible assignments can share the same best preference score.

Is COP different from CSP?

It adds a preference-based comparison among solutions to the satisfaction requirements.

AI Glossary / Mathematics and optimization / Advanced

Constrained optimization problem

Definition

A constrained optimization problem, abbreviated COP in the supplied AIMA glossary, extends a constraint satisfaction problem with preferences. The task is to find an assignment that satisfies the mandatory constraints and is best according to the specified preferences. This entry focuses on that constraint-reasoning meaning, while recognizing its relationship to the broader mathematical optimization framework.

What it means

A timetable can be valid without being desirable. It might avoid every forbidden overlap yet place important activities at inconvenient times. A plain constraint satisfaction problem asks whether the requirements can be met. Adding preferences asks which acceptable timetable should be chosen.
Distinguish forbidden options from permissible but less preferred ones. Preferences must have an explicit comparison rule; an optimizer cannot infer how much one inconvenience should count relative to another.

How it works

Specify variables, their domains and the hard constraints governing allowable assignments. Represent preferences through an objective, often a sum of local cost functions called soft constraints. Each function assigns a cost to a combination of values in its scope. Under this additive interpretation, lower total cost means a more preferred feasible assignment.
A search procedure can build assignments incrementally, reject hard-constraint violations and use bounds to avoid exploring options that cannot beat the best known solution. Finding a feasible assignment is distinct from proving that no better feasible assignment exists. Other preference-combination rules are possible, so summing costs is a modeling choice rather than a universal definition of preference.

Three practical examples

A training coordinator assigns sessions to times. A trainer cannot teach two sessions simultaneously, while an early finish may merely be preferred. The first condition determines feasibility; the second helps rank feasible schedules.
A service team allocates workers to requests. Required qualifications are mandatory, while continuity with a previous customer may carry a preference cost. A familiar but unqualified worker should not win through a favorable preference score.
A household assistant arranges three activities across available periods. Some activities cannot overlap because they use the same room. Preferred times can then distinguish several valid arrangements without falsely declaring less convenient times impossible.

Think of it this way

Think of an application form with compulsory conditions and a separate wish list. First establish which applications meet the compulsory conditions. Then compare those remaining using an agreed interpretation of the wishes. A strong wish does not automatically turn a disallowed application into an allowed one.

Worked example

Consider an original scheduling example with activities A, B and C. Each must be assigned either morning or afternoon. The hard constraints are A ≠ B and B ≠ C: B shares a resource with each of the others, while A and C can occur together.
A prefers morning, with cost three otherwise. B prefers morning, with cost two otherwise. C prefers afternoon, with cost four otherwise. All satisfied preferences cost zero. The objective is the sum of these three costs.
There are eight possible assignments before applying hard constraints. Only two survive. Schedule one places A and C in the morning and B in the afternoon. Its cost is 0 + 2 + 4 = 6. Schedule two places A and C in the afternoon and B in the morning. Its cost is 3 + 0 + 0 = 3. Because these exhaust the feasible assignments, schedule two is globally optimal for this model.
The assignment A morning, B morning, C afternoon satisfies every preference, giving soft cost zero. It is nevertheless infeasible because A and B overlap. A low preference score does not remove the hard violation.

Illustrative case study

In a fictional learning center, the coordinator adopts schedule two from the example. A later review changes A's preference penalty from three to seven because its afternoon timing now causes substantially more disruption. The hard constraints and domains remain the same.
Schedule one's cost remains six, while schedule two now costs seven. The recommended schedule switches to the first. It violates two preferences, compared with one for the second, yet has the smaller agreed weighted cost. Minimizing the number of disappointed preferences would therefore solve a different problem from minimizing their stated costs.
The center records the changed weight and the reason for it. It also explains the trade-off to affected staff. The numerical weights are fictional planning assumptions, not a measured universal scale of inconvenience or a claim that one group's preferences objectively matter more.

Common misconceptions and mistakes

Soft constraints are not accidental errors that an implementation may ignore; they encode the preference criterion. Hard constraints, by contrast, must hold for a feasible answer.
An arbitrary large penalty may fail to enforce a hard rule. In the original example, assigning a penalty of two to an overlap makes the infeasible zero-preference-cost assignment score two, beating the best feasible score of three. Keeping hard feasibility explicit avoids that mistake. If penalties are used as an equivalent formulation, their bounds and assumptions must be justified.
Also avoid reporting the first feasible schedule as proven optimal or counting violated preferences when their weights differ.

Business use

COP formulations help teams explain recommendations through both requirements and trade-offs. Maintain a record of which rules are mandatory, how preference costs were elicited and which rules each proposed assignment satisfies. Test how recommendations change under plausible alternative weights. If mandatory requirements conflict, report that conflict rather than presenting the least-violating plan as fully feasible. A decision owner can then decide whether a requirement may be revised.

Check your understanding

Why is the zero-soft-cost assignment rejected?

Answer: A and B occupy the same period, violating a mandatory separation.

Which schedule wins with the original weights?

Answer: A and C afternoon, B morning, with cost three.

Why does the recommendation change when A's penalty becomes seven?

Answer: The alternative's cost of six is then lower, even though it disappoints more individual preferences.

Related terms

Constraint satisfaction problem
Preference elicitation
Objective function
hard constraint
soft constraint
weighted constraint satisfaction
branch-and-bound
feasible assignment

Learn next

Practice constructing small cost tables and enumerating feasible assignments. Then compare weighted sums with lexicographic preferences, where higher-priority criteria are considered before lower-priority ones, and study bounds used to certify optimality.

Sources

AIMA glossary, constrained optimization problem: CSP with preference constraints and the abbreviation COP. https://github.com/aimacode/aima-glossary/blob/master/glossary.md David Poole and Alan Mackworth, Artificial Intelligence: Foundations of Computational Agents, third edition, section 4.8: hard constraints, factored preference costs and systematic optimization. https://artint.info/3e/html/ArtInt3e.Ch4.S8.html The three-activity schedule, penalty counterexample and fictional learning-centre case are original illustrations.

Previous: Constrained optimization Next: Constraint Grammar