Introduction

A plain assignment problem is already well understood: one worker, one task, minimum total cost. The difficulty starts when you add side conditions such as forbidden pairs, quotas, capacities, or dependency rules, because at that point the right solution is often no longer the classic Hungarian algorithm but a more general optimization model.

Start with the Basic Assignment Model

For the unconstrained one-to-one case, the input is a cost matrix. Each row is a worker, each column is a task, and the goal is to select one cell per row and one cell per column with minimum total cost.

1import numpy as np
2from scipy.optimize import linear_sum_assignment
3
4cost = np.array([
5    [9, 2, 7],
6    [6, 4, 3],
7    [5, 8, 1],
8], dtype=float)
9
10workers, tasks = linear_sum_assignment(cost)
11assignment = list(zip(workers.tolist(), tasks.tolist()))
12total_cost = cost[workers, tasks].sum()
13
14print("assignment:", assignment)
15print("total cost:", total_cost)

That is still the best tool when the structure remains truly one-to-one.

Some Constraints Fit the Classic Model

A few simple restrictions can be modeled without abandoning assignment entirely. If a worker-task pair is forbidden, you can remove that edge or assign it a prohibitively large cost.

cost[0, 2] = 10**9
workers, tasks = linear_sum_assignment(cost)

This is reasonable only when the problem is still one worker per task and one task per worker. The shape of the optimization has not changed. Only some edges became illegal.

Know When the Problem Has Changed

Many real constraints mean you no longer have a plain assignment problem. Examples include:

• one worker may take several tasks
• a task needs a certified worker type
• at least two tasks must go to a preferred group
• two tasks must be assigned to the same worker
• department quotas or capacity limits must be respected

Those rules change the structure of the model. Trying to force them into a cost matrix with large penalty constants usually creates brittle, hard-to-debug logic.

Use Binary Optimization for Constrained Cases

A common way to model the constrained version is to use a binary variable x[i, j] that equals 1 when worker i is assigned to task j. Then you write the assignment rules and the extra business rules explicitly.

OR-Tools makes this style straightforward:

1from ortools.sat.python import cp_model
2
3cost = [
4    [9, 2, 7],
5    [6, 4, 3],
6    [5, 8, 1],
7]
8
9model = cp_model.CpModel()
10x = {}
11
12for i in range(3):
13    for j in range(3):
14        x[i, j] = model.NewBoolVar(f"x_{i}_{j}")
15
16for i in range(3):
17    model.Add(sum(x[i, j] for j in range(3)) == 1)
18
19for j in range(3):
20    model.Add(sum(x[i, j] for i in range(3)) == 1)
21
22model.Add(x[0, 2] == 0)
23model.Add(x[1, 0] + x[1, 1] <= 1)
24
25model.Minimize(
26    sum(cost[i][j] * x[i, j] for i in range(3) for j in range(3))
27)
28
29solver = cp_model.CpSolver()
30status = solver.Solve(model)
31
32if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
33    for i in range(3):
34        for j in range(3):
35            if solver.Value(x[i, j]):
36                print(i, j)

This is longer than the classic assignment solver, but it tells the truth about the actual problem.

Feasibility Comes Before Optimality

With constraints, the first question is often not “what is the best assignment” but “is any assignment possible at all.” If too many pairs are forbidden or multiple quota rules conflict, the model can be infeasible.

That is why the solve status matters. During early modeling, it is often better to:

1. solve the unconstrained version
2. add one real-world rule at a time
3. rerun after each addition
4. stop as soon as the model becomes infeasible

This is much easier than introducing every business condition at once and then trying to guess which one broke the model.

Choose the Solver That Matches the Structure

If the problem remains a clean bipartite matching problem, use a dedicated assignment algorithm because it is simpler and usually faster. If the model contains capacities, dependencies, or grouped conditions, move to MILP or CP-SAT early.

That is the real modeling decision. The goal is not to keep using the Hungarian algorithm out of habit. The goal is to choose the smallest model that still expresses the true rules.

Keep Constraints Explicit

A maintainable optimization model is one where another engineer can read the code and understand why a rule exists. Penalty-heavy cost matrices often hide business logic in magic numbers. Explicit constraints are longer, but they are easier to review, test, and explain.

That trade-off is usually worth it in production systems.

Common Pitfalls

• Treating every constrained assignment problem as if the Hungarian method must still apply.
• Encoding business rules as huge penalty costs when the rule should be explicit.
• Forgetting to check feasibility before reading the objective value.
• Adding many constraints at once and then not knowing which one caused infeasibility.
• Optimizing performance too early instead of first making the model correct and understandable.

Summary

• Use a standard assignment solver only when the problem is still truly one-to-one.
• Forbidden pairs can often be handled inside the classic model.
• Capacity, quota, and dependency rules usually require MILP or CP-SAT.
• Check feasibility before worrying about the quality of the optimum.
• Prefer an explicit model that matches the business rules over a shorter but misleading cost matrix.