Restricted / Prohibited Assignment Problem Calculator
Solve assignment problems with forbidden worker–task pairs. Detect infeasible cases, compute the optimal feasible assignment (Hungarian method), and view step tables + a bipartite matching graph. For the “perfect matching” explanation of feasibility/infeasibility, see: assignment feasibility / infeasibility.
Calculator type
Switching type updates the URL and preserves your current matrix via the share payload (?wt=…).
Quick intro (restricted / prohibited pairs)
A restricted assignment problem is a standard assignment model plus extra rules: some worker→task pairs are not allowed. In this calculator, you mark such cells as Forbidden. The solver then: (1) checks whether a complete one-to-one assignment is still possible, and (2) if feasible, finds the optimal assignment without using forbidden pairs. If you want the graph explanation (perfect matching), see: feasible vs infeasible assignment.
Practical reasons for forbidden pairs include missing certifications, incompatible skills, location restrictions, policy constraints, or safety requirements.
Key terms on this page
Short lessons that help with forbidden pairs, feasibility, and the graph viewpoint.
Inputs
Restricted problems can be solved for both Min and Max. Forbidden cells are never used in the final matching. (If you mainly need max-profit: maximization assignment calculator.)
Hungarian is optimal and supports step tables. Brute force verifies small n. Greedy is a baseline and may be suboptimal.
Cost / profit matrix (with Forbidden)
Results
Enter your matrix and click Solve.
Solution walkthrough (restricted-focused)
Format: ?wt=…&autocalc=1
Embed this calculator
Graph (bipartite matching)
Forbidden pairs remove edges from the bipartite graph. If the graph can’t support a perfect matching, the problem is infeasible. Learn the matching viewpoint: bipartite matching & assignment · feasible vs infeasible assignment.
Hungarian method step tables (optional)
Step-by-step tables are available only for Hungarian method. Key steps include covering zeros with minimum lines and the θ adjustment.
Steps will appear after you solve using Hungarian method.
On this page
Try this next
Continue inside the assignment-problem calculator cluster:
Related reading: Big‑M method · unbalanced assignment · linear programming
Worked examples (beginner → intermediate → hard → extreme)
These examples emphasize forbidden assignments, feasibility, and how restrictions change the optimal solution.
Beginner (forbidden cells, still feasible)
RB1 — Restricted but feasible (3×3): simple prohibited pairs
Practical story: not every worker is trained for every task. Forbidden pairs represent training gaps.
Intermediate (more restrictions, multiple options)
RI1 — 4×4 with prohibited pairs: classic restricted assignment
Practical story: drivers can’t drive certain routes due to licensing; those cells are forbidden.
Hard (diagnose infeasibility + recovery)
RH1 — Infeasible restricted assignment (3×3): no perfect matching exists
This example demonstrates a key real-world outcome: if restrictions are too strict, there is no feasible schedule.
RH2 — Make it feasible: remove just one forbidden constraint
Same as RH1 but with one restriction relaxed—this shows how feasibility can “snap back” with small policy changes.
Extreme (larger restricted matrix)
RX1 — 8×8 restricted: many forbidden pairs
Larger restricted problems are common in workforce planning. Hungarian is recommended for exact solutions.
Related: Big M method · Unbalanced assignment.
Questions people ask about restricted / prohibited assignment problems
Modeling forbidden pairs
What is a restricted (prohibited) assignment problem?
It’s the assignment problem plus constraints that forbid certain worker–task pairings. Those pairs cannot be chosen in the final one-to-one matching.
When should I mark a cell as Forbidden instead of using a very large cost?
Use Forbidden when the pair is truly impossible or disallowed (license, safety, policy). A very large cost is a “soft restriction” trick; it can still be chosen if no other feasible assignment exists.
How do forbidden pairs change the optimal assignment?
They remove options. The solver searches the remaining feasible matchings and selects the best one among them. This can increase cost (or reduce profit) compared to the unrestricted case.
Do forbidden pairs apply in both minimization and maximization?
Yes. Feasibility is about whether a perfect matching exists; the objective only chooses the best among feasible matchings.
Feasibility (the most important issue)
What does “Infeasible” mean in a restricted assignment?
It means there is no way to assign every worker to a distinct task (and every task to a distinct worker) without using forbidden pairs. In graph terms: no perfect matching exists.
How can I diagnose which restrictions cause infeasibility?
Start by un-forbidding a small number of pairs in bottleneck rows/columns (where almost everything is forbidden). If feasibility returns, those constraints were critical.
Can a restricted assignment be feasible but have a much worse total?
Yes. Removing high-quality options forces the solver to use lower-quality remaining pairs, increasing total cost (or reducing total profit).
What if I only need to assign as many tasks as possible (not all)?
That’s a different objective (maximum matching / partial assignment). This calculator targets full one-to-one assignments (after balancing).
Methods + verification
Does the Hungarian method handle forbidden cells?
Yes. This calculator excludes forbidden pairs from feasibility and treats them as not selectable during optimization.
How can I verify the restricted solution?
For small balanced sizes (n ≤ 8), use brute force to verify the Hungarian result. For larger problems, Hungarian is the recommended exact method.
Why can greedy fail more often with forbidden pairs?
Greedy may pick an early pair that blocks the remaining feasible completion. Restrictions reduce flexibility, increasing greedy’s chance of dead ends or suboptimal solutions.
What is the time complexity of the Hungarian algorithm?
O(n³). It scales far better than brute force (n!).
Methodology (how this restricted calculator works)
This page solves a restricted assignment problem by modeling forbidden cells as prohibited edges in a bipartite graph. The solver first checks feasibility (existence of a perfect matching), then optimizes among feasible assignments.
1) Balance the matrix (if rectangular)
If rows ≠ cols, the solver adds dummy rows/columns with value 0 to create an n×n problem, where n = max(rows, cols). Forbidden pairs remain forbidden; dummy cells are allowed by default.
2) Feasibility check (before optimization)
The solver builds the “allowed-edge” graph (all non-forbidden cells) and checks whether a perfect matching of size n exists. If the maximum matching size is < n, the problem is Infeasible and optimization is not attempted.
3) Optimization (Hungarian / brute force / greedy)
If feasible:
• Hungarian method finds the optimal assignment (and can show step tables).
• Brute force verifies small n (≤ 8).
• Greedy is fast but can be suboptimal, especially under restrictions.
4) Forbidden modeling note (Big-M vs truly forbidden)
In some textbooks, prohibited pairs are modeled by assigning a very large penalty (Big-M). This calculator treats Forbidden pairs as strictly disallowed (never selected).
Sources
- Kuhn (1955). The Hungarian method for the assignment problem
- Munkres (1957). Algorithms for the Assignment and Transportation Problems