Assignment Problem: Feasible vs Infeasible (Perfect Matching Viewpoint)
“Feasible” means there exists at least one one-to-one assignment that respects all constraints (including forbidden pairs). In graph language, feasibility means the allowed bipartite graph contains a perfect matching. “Infeasible” means no perfect matching exists.
Check feasibility instantly in the Restricted / Prohibited Assignment Calculator. For rectangular matrices, see the Unbalanced Assignment Calculator.
On this page
- Quick takeaway (definition + graph intuition)
- Feasibility as a bipartite graph problem
- Fast feasibility checks (what to look for)
- Unbalanced (rectangular) case: how dummy nodes affect feasibility
- Forbidden pairs: why restrictions can break feasibility
- How to fix an infeasible assignment (practical steps)
- Worked examples (expandable)
- Questions people ask (feasible/infeasible)
- Check your case (calculators + next links)
- Glossary
Quick takeaway: An assignment problem is feasible if you can pick exactly one allowed cell in every row and every column (after balancing), with no repeats. It is infeasible if restrictions remove so many options that this becomes impossible. The cleanest way to think about it is a bipartite graph: allowed pairs are edges, and feasibility means a perfect matching exists.
Feasibility as a bipartite graph problem
Graph viewpoint
Workers and tasks are nodes; allowed pairs are edges
Convert your matrix into a bipartite graph: left side = workers, right side = tasks. A cell is allowed if it is not forbidden; that creates an edge. A perfect matching selects edges so every node is used exactly once.
Learn more: bipartite matching & assignment.
Fast feasibility checks (what to look for)
Fast checks
Quick “red flags” before you even solve
| Red flag | What it usually means | Why it can cause infeasibility |
|---|---|---|
| A row has all cells forbidden | That worker cannot do any task | No edge leaves that worker node ⇒ cannot match it |
| A column has all cells forbidden | No worker can do that task | No edge enters that task node ⇒ cannot match it |
| Too many workers depend on the same single task | Bottleneck column | At most one worker can take that task |
| Many forbidden pairs + small matrix | Low flexibility | Perfect matching often disappears quickly |
Unbalanced (rectangular) case: dummy nodes and feasibility
Unbalanced case
Balancing makes perfect matching well-defined—but doesn’t guarantee feasibility
If your matrix is rectangular, we add dummy rows/columns to make it square. Balancing fixes the shape problem, but if forbidden constraints are heavy, the balanced graph can still fail to contain a perfect matching.
Interpretation help: dummy row / dummy column.
Forbidden pairs: why restrictions can break feasibility
Restricted assignment
Forbidden cells remove edges from the graph
In restricted/prohibited assignment, a forbidden pair is not “very expensive”—it is not allowed. That means the edge is removed from the bipartite graph.
If your use case is “soft restriction” (avoid a pairing but allow if necessary), see Big‑M method.
How to fix an infeasible assignment (practical steps)
Fixes
What to try when the solver says “Infeasible”
- Find bottleneck rows/columns: look for workers/tasks with very few allowed options.
- Relax a small number of forbidden pairs: often 1–2 critical constraints restore feasibility.
- Re-check data entry: swapped rows/columns, wrong forbidden marks, or missing tasks are common.
- Use dummy penalties (if appropriate): if leaving tasks unfilled is allowed but undesirable, model that explicitly.
- Switch models if the real process isn’t one-to-one: consider transportation/flow or scheduling constraints.
Worked examples (expandable)
Worked examples
Expand only the example you need
These examples are written lecture-style: we explicitly construct a matching (feasible) or prove it cannot exist (infeasible).
Example 1 — Feasible restricted assignment (perfect matching exists)
Cost matrix (3×3): “X” means forbidden.
T1 T2 T3 W1 9 X 7 W2 6 4 3 W3 5 8 X
Step 1 — Convert to allowed options (edges)
W1 → {T1, T3}
W2 → {T1, T2, T3}
W3 → {T1, T2}
Step 2 — Construct a perfect matching (one-to-one)
Pick a row with few choices first:
Pick W1→T3 Now T3 is used. Pick W2→T2 Now T2 is used. Pick W3→T1 Now T1 is used.
Conclusion: Perfect matching found (W1→T3, W2→T2, W3→T1). The problem is feasible.
Example 2 — Infeasible restricted assignment (no perfect matching)
Cost matrix (3×3): all of column T1 is forbidden.
T1 T2 T3 W1 X 2 3 W2 X 5 1 W3 X 1 6
Lecture test (column has no allowed edges)
Task T1 cannot be assigned to any worker (the entire column is forbidden). A perfect matching must match every task exactly once, so this is impossible.
Conclusion: The problem is infeasible.
Example 3 — Unbalanced + forbidden (still infeasible after balancing)
Balancing (dummy rows/columns) fixes the shape, but cannot fix “impossible tasks” caused by forbidden pairs.
Original 4×3 (X = forbidden), where task T2 is impossible:
T1 T2 T3 W1 4 X 8 W2 6 X 3 W3 5 X 4 W4 9 X 2
Step 1 — Balance by adding dummy column D
T1 T2 T3 D W1 4 X 8 0 W2 6 X 3 0 W3 5 X 4 0 W4 9 X 2 0
Step 2 — Feasibility conclusion
Column T2 is still all forbidden, so no perfect matching exists (T2 has no allowed edge). Dummy column D cannot replace T2; it only absorbs the extra worker.
Conclusion: Still infeasible after balancing.
Questions people ask (feasible/infeasible)
People ask
What does “feasible” mean in an assignment problem?
Feasible means there exists at least one way to assign each worker to a distinct task (and each task to a distinct worker after balancing) using only allowed pairs. In graph terms, a perfect matching exists.
People ask
What does “infeasible” mean in a restricted assignment problem?
Infeasible means forbidden constraints remove so many options that no perfect matching exists. Often there is a bottleneck row/column with too few allowed options.
People ask
Does Hungarian method detect infeasibility?
Yes—when forbidden pairs block any complete assignment, the solver reports infeasible. For step tables and how the matching is extracted from zeros, see: Hungarian method solver.
People ask
Can I make an infeasible assignment feasible?
Often yes, by relaxing a small number of forbidden pairs (especially in bottleneck rows/columns), or by switching to a different model if your real process isn’t one-to-one.
People ask
What if I only need to assign as many tasks as possible?
That is a different objective (maximum matching / partial assignment). The calculators in this cluster focus on full one-to-one assignment after balancing.
Check your case (calculators + next links)
Tools
Use these pages next
Glossary
Glossary
- Allowed pair: not forbidden (edge exists).
- Forbidden pair: prohibited (edge removed).
- Perfect matching: one-to-one matching covering all nodes after balancing.
- Feasible: at least one perfect matching exists.
- Infeasible: no perfect matching exists.
Disclaimer
This page is for educational and planning purposes only. Real-world assignments often include constraints beyond a basic one-to-one model. Validate feasibility and operational rules with a production optimizer and domain review. Read our full disclaimer.
Sources
- Kuhn (1955). The Hungarian method for the assignment problem
- Munkres (1957). Algorithms for the Assignment and Transportation Problems