Assignment Problem Solver (Hungarian Algorithm Calculator)

Last updated:  |  View sources  |  Methodology  |  OR calculators hub
Jump to Calculator

Assignment Problem Solver (Hungarian Algorithm)

Solve worker–task assignments to minimize cost or maximize profit. Includes Hungarian method steps, bipartite matching graph, share + embed, and worked examples.

Quick intro

The assignment problem is a one-to-one matching: each worker gets exactly one task and each task gets exactly one worker. If your matrix is rectangular (unbalanced), the solver automatically adds dummy rows/columns. Learn unbalanced cases here: unbalanced assignment problem.

Inputs

Hungarian shows step tables. Brute force verifies small n. Greedy is a baseline and may be suboptimal. See Hungarian algorithm explained.

Cost / profit matrix

Each cell is Worker i → Task j. Mark Forbidden for impossible pairs (see Big M method).
Objective: — Method: — Shape: — Balance: — Status: —

Results

Solution status
—
Total
—
Assignments (real)
—
Notes
—

Enter your matrix and click Solve.

Solution walkthrough (very detailed, current problem)
Solve a problem to generate a detailed explanation here.
Want more practice? Assignment problem examples. For automation: Hungarian algorithm in Python.

Format: ?wt=…&autocalc=1

Embed this calculator

Embedding uses the same wt payload.

Graph (bipartite matching)

Visualizing the assignment as a bipartite graph helps explain why this is a matching problem. Learn more: bipartite matching & assignment.

Solve a matrix to render the graph.
Hungarian method step tables (optional)

Step-by-step tables are available only for Hungarian method. Learn: Hungarian algorithm explained.

Steps will appear after you solve using Hungarian method.

On this page

Worked examples (beginner → intermediate → hard → extreme)

Each example includes a “Load this example” button so you can see how the solver behaves. Try different methods (Hungarian vs brute force vs greedy).

Beginner

B1 — Minimize cost (3×3): classic starter 
W1:  9  2  7
W2:  3  6  8
W3:  5  8  4
B2 — Maximize profit (3×3): shows max mode 
D: 12  8 15
E:  7 14  9
F: 10 11 13
B3 — Greedy trap (4×4): why local choices can fail

Intermediate

I1 — Rectangular / unbalanced (4×3): dummy column added

Learn: unbalanced assignment problem.

I2 — Forbidden assignments (4×4): infeasibility risk
I3 — Job scheduling style (5×5): practical scenario matrix

Learn modeling: job scheduling using assignment model.

Hard

H1 — Multiple optimal solutions (ties)
H2 — Negative costs (net savings)

Extreme (still browser-safe)

X1 — 8×8: max size for brute force
X2 — QAP concept demo (facility layout interaction costs)

In Quadratic Assignment Problem (QAP), the total cost depends on pairs of assignments. This calculator solves the linear assignment problem. 

Linear placement costs (Facility → Location)
F1:  9  2  7  8
F2:  6  4  3  7
F3:  5  8  1  8
F4:  7  6  9  4

Learn: quadratic assignment problem (QAP).

More solved problems: assignment problem examples. Glossary: operations research glossary.

Questions people ask about the assignment problem solver

Fundamentals

What is the assignment problem in operations research?

It’s a one-to-one matching problem where you assign n workers to n tasks to minimize total cost (or maximize profit). Each worker and task must be used exactly once (after balancing).

What is an assignment problem solver?

It’s a calculator that returns the optimal worker→task mapping from your matrix, plus the optimized total. This page can also show Hungarian step tables and a bipartite graph visualization.

Is the assignment problem a special case of linear programming?

Yes. It can be formulated as a 0–1 ILP. But the special structure allows faster matching-based methods than general ILP solvers for typical cases.

Hungarian method

What are the steps of the Hungarian algorithm?

Row reduction → column reduction → cover zeros with minimum lines → if lines < n, adjust by θ and repeat → pick independent zeros to read the assignment. Learn: Hungarian algorithm explained.

When do you stop iterating in the Hungarian algorithm?

Stop when the minimum number of covering lines equals n. Then a perfect matching exists among zeros.

Does this Hungarian algorithm calculator show step-by-step solution?

Yes—solve using Hungarian method and open the “step tables” section to see each reduction and iteration.

Maximization vs minimization

How do you solve a maximization assignment problem?

Choose Maximize. Hungarian converts internally; brute force and greedy evaluate profits directly. The total shown is always based on your original profit matrix.

Unbalanced / rectangular matrices

Can this solver handle rectangular assignment problems?

Yes. It adds dummy rows/columns to make the matrix square. Learn: unbalanced assignment problem.

What is a dummy row or dummy column?

A dummy row/column is added to balance the matrix. Matching to a dummy means a worker is unused or a task remains unfilled.

Forbidden assignments and feasibility

How do I model forbidden assignments?

Mark cells as Forbidden. If too many are forbidden, the problem may become infeasible (no perfect matching exists).

Can an assignment problem be infeasible?

Yes—especially with forbidden cells. The solver checks feasibility before computing a final assignment.

Multiple optima and verification

Can there be multiple optimal solutions?

Yes. Ties can create different matchings with the same total. Use brute force (n ≤ 8) to verify small cases.

How can I verify the Hungarian algorithm result?

Switch to Brute force for small matrices and compare the total and assignment to Hungarian.

Method selection

Why can greedy be wrong?

Greedy makes local choices early that can block better global solutions. Hungarian guarantees optimality for linear assignment.

What is the time complexity of the Hungarian algorithm?

O(n³), much faster than brute force (n!).

Related comparisons

Assignment problem vs transportation problem—what’s the difference?

Transportation moves quantities; assignment is one-to-one. See: assignment vs transportation problem.

How does this relate to bipartite matching?

Assignment is a weighted bipartite matching problem. Learn: bipartite matching & assignment.

Beyond this solver

What is the quadratic assignment problem (QAP)?

QAP includes interaction costs between assignments (harder than linear assignment). Learn: quadratic assignment problem.

Methodology (how this calculator works)

This calculator supports Hungarian (optimal + steps), brute force (optimal for n ≤ 8), and greedy (fast heuristic).

Learn more: Hungarian algorithm explained · Hungarian algorithm in Python · Unbalanced assignment · Solved examples · OR glossary

IMPORTANT DISCLAIMER (Read before using): This Assignment Problem Solver runs in your browser and is intended for learning, demonstrations, and planning. Real-world allocation and scheduling often require additional constraints (skills, certifications, availability windows, labor rules, multi-tasking, fairness, and priorities) that a basic assignment matrix does not capture. The results shown here may be incorrect or incomplete if the model is a poor fit for your real process, or if inputs are not scaled sensibly. Do not use this output as the sole basis for high-stakes decisions (financial, legal, safety, medical, compliance, or mission-critical operations). Always validate results with a production-grade optimizer and/or a qualified operations research professional. See our Disclaimer.
Sources