Forbidden Assignment¶

Definition¶

A forbidden assignment is an agent-task pair that is not allowed. In the course's Hungarian cost matrix, represent this pair by $\infty$ and leave that entry infinite during all transformations.

Interpretation¶

A forbidden assignment excludes one agent-task pair. The infinite cost turns the pair into a prohibition rather than an expensive option: no complete assignment that uses it can compete with one that avoids it.

The entry for $A_2\to T_2$ is $\infty$ before and after the row and column reductions, since subtracting a finite number from $\infty$ leaves $\infty$. The highlighted optimal assignment avoids that cell: $A_1\to T_1$$T_1$, $A_2\to T_3$$T_3$, $A_3\to T_2$ with cost $2+4+6=12$$12$.

A large finite number $M$ works only if it is large enough: here the cheapest assignment through $A_2\to T_2$ costs $2+M+2$$2$, so $M$ must exceed $8$. In the Hungarian algorithm, an infinite entry is never a zero, so it is never selected; in the binary formulation, the same ban is the constraint $x_{ij}=0$$0$.

Key Results¶

• Do not apply finite row or column adjustments as if they made an infinite entry available.
• If no complete assignment avoiding forbidden pairs exists, the intended assignment problem is infeasible.
• In a binary formulation, the equivalent restriction is $x_{ij}=0$$0$.

Examples¶

In the figure, prohibiting $(2,2)$ gives the highlighted assignment $A_1\to T_1$$T_1$, $A_2\to T_3$$T_3$, $A_3\to T_2$ with cost $2+4+6=12$$12$. A finite penalty $M$ represents a prohibition only if it is sufficiently large and an allowed complete assignment exists; $x_{22}=0$ enforces the ban directly.

• A machine unable to process job 3 receives an infinite entry in that job's column.
• A feasible assignment must choose another machine for that job.

Prerequisites¶

• Assignment Problem

Related Concepts¶

• Hungarian Algorithm
• Infeasible Linear Program

Sources¶

• OR Modelling · Week 5

Symbols: infinity

Last updated: 20 October 2026 03:02