Unbalanced Assignment Problem Calculator (Rectangular Matrix)
Solve rectangular assignment problems (rows ≠ cols) by automatically adding dummy rows/columns. Includes Hungarian method steps, bipartite matching graph, forbidden pairs, share + embed, and lecture-style worked examples. For a short standalone lesson on interpretation, see: dummy row / dummy column.
Calculator type
Switching type updates the URL and preserves your current matrix via the share payload (?wt=…).
Quick intro (unbalanced / rectangular)
An unbalanced assignment problem happens when the number of workers and tasks are not equal (a rectangular matrix). The standard one-to-one assignment requires a square matrix, so the solver balances it by adding dummy workers or dummy tasks. A match to a dummy means something is left unused (an extra worker) or unfilled (an extra task). If you want the deeper interpretation rules, see: dummy rows/columns explained.
Practical meaning: “We have more staff than jobs today” or “We have more jobs than staff”, but still want the best one-to-one plan. If restrictions apply, the key question becomes feasibility (does a perfect matching exist?): feasible vs infeasible assignment.
Key terms on this page
Short lessons that help you interpret rectangular (unbalanced) outputs, dummy matches, and feasibility.
Inputs
Unbalanced problems can be solved for both Min and Max. Dummy rows/columns are added automatically. (For max-mode details, see 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
Results
Enter your matrix and click Solve.
Solution walkthrough (unbalanced-focused)
Format: ?wt=…&autocalc=1
Embed this calculator
Graph (bipartite matching)
Even in rectangular cases, the solver creates a square matching model using dummy nodes. The graph visualizes the final matching. If you want the matching viewpoint: bipartite matching & 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: assignment vs transportation · linear programming
Worked examples (beginner → intermediate → hard → extreme)
Unbalanced examples teach how to interpret dummy matches (unused worker / unfilled task). Each example has a “Load this example” button.
Beginner (rectangular basics)
UB1 — 4×3 (extra worker): one worker remains unused
Practical story: 4 technicians available, but only 3 jobs are needed today.
Interpretation note: the dummy task represents “no job assigned” (see dummy row / dummy column).
UB2 — 3×4 (extra tasks): one task remains unfilled
Practical story: 3 drivers are available but 4 routes exist; one route will not be assigned.
Intermediate (planning / staffing)
UI1 — 5×3 (staffing): two workers remain unused
Practical story: 5 nurses, 3 shifts. Dummy shift matches represent staff not scheduled today.
UI2 — 6×5 (operations): one worker remains unused
Practical story: 6 pickers and 5 warehouse zones—assign pickers to zones to minimize total walking time.
Hard (constraints + unbalanced)
UH1 — Unbalanced + forbidden pairs: feasibility risk
Practical story: not every worker is certified for every task. Too many forbidden pairs can make the whole problem infeasible (see feasible vs infeasible assignment).
Extreme (larger rectangular)
UX1 — 10×8 unbalanced: Hungarian recommended
Brute force becomes impractical at this size. Hungarian remains efficient (O(n³)).
Learn: unbalanced assignment problem · See also: restricted/prohibited assignment.
Questions people ask about unbalanced (rectangular) assignment problems
Core idea
What is an unbalanced assignment problem?
It’s an assignment problem where the cost/profit matrix is rectangular (rows ≠ cols). There are more workers than tasks, or more tasks than workers.
Why do we add dummy rows or dummy columns?
The one-to-one assignment model requires a square matrix. Adding dummy rows/columns converts a rectangular matrix into an equivalent square model so a perfect matching can be found. Learn: dummy row / dummy column.
How do I interpret a dummy assignment?
If you add a dummy task, a worker matched to dummy is effectively unused. If you add a dummy worker, a task matched to dummy remains unfilled.
Does Hungarian method require a square matrix?
In standard form, yes. But in practice you solve rectangular cases by first balancing them with dummy rows/columns—this page does that automatically.
Modeling choices
Should dummy costs be 0?
In this calculator, dummy cells are 0 by default (neutral). In real life you may want a penalty cost if leaving a task unfilled is undesirable (or a penalty profit if leaving a worker idle is undesirable).
What if I must fill all tasks even if I have fewer workers?
That’s not a one-to-one assignment anymore; it becomes a different model (e.g., workers can do multiple tasks, or tasks can be split). Consider a transportation/flow model (see assignment vs transportation).
Can unbalanced problems still include forbidden assignments?
Yes. Forbidden pairs can exist in rectangular matrices too. But too many forbidden edges can make the problem infeasible.
How do I know if my unbalanced assignment is infeasible?
If forbidden constraints block every perfect matching after balancing, the solver reports Infeasible. Learn the perfect-matching viewpoint: assignment feasibility/infeasibility.
Interpretation + validation
Does the total include dummy matches?
Dummy matches contribute 0 in this calculator (by design). The “real matches” count shows how many assignments are between actual workers and actual tasks.
Can I solve unbalanced maximization problems too?
Yes. Choose Maximize; the calculator balances the matrix the same way, then solves using the selected method.
How can I verify an unbalanced solution?
For small sizes (n ≤ 8 after balancing), use Brute force to verify the Hungarian result. For larger problems, Hungarian is the recommended exact method.
Methodology (how this unbalanced calculator works)
This calculator solves the assignment problem for rectangular matrices by converting them into a balanced (square) form using dummy rows/columns, then solving the balanced problem using Hungarian / brute force / greedy. For a dedicated interpretation note, see dummy row / dummy column.
1) Balance step (dummy rows/columns)
Let rows = number of workers and cols = number of tasks. Define n = max(rows, cols). The solver forms an n×n matrix by adding dummy rows or dummy columns filled with 0.
Interpretation:
• If rows > cols: dummy columns represent “no task assigned” (some workers remain idle).
• If cols > rows: dummy rows represent “no worker assigned” (some tasks remain unfilled).
2) Forbidden pairs + feasibility check
Forbidden cells are treated as prohibited edges. The solver checks if a full one-to-one assignment exists without using forbidden pairs. If not, it reports Infeasible. Learn the perfect-matching viewpoint: assignment feasibility / infeasibility.
3) Solve (Hungarian / brute force / greedy)
• Hungarian is exact and efficient (O(n³)) and can show step tables (see Hungarian algorithm explained).
• Brute force is exact but limited to small n (≤ 8).
• Greedy is fast but not guaranteed optimal.
4) Reporting (real vs dummy matches)
The output table labels matches as Real or Dummy. Real matches correspond to actual worker→task pairs from your original rectangle. Dummy matches explain what remained unused/unfilled due to imbalance.
Sources
- Kuhn (1955). The Hungarian method for the assignment problem
- Munkres (1957). Algorithms for the Assignment and Transportation Problems