The Assignment Problem, Explained with Examples

UPI Study › Courses › Quantitative Analysis › Free lessons › Lesson 13.1 Free with a free account

The Assignment Problem

Quantitative Analysis · Chapter 13: Assignment ModelsSection 13.1 · lesson 54 of 5512 min · free with a free account

← Starting Simple and ImprovingNext lesson: Step by Step Through the Hungarian Algorithm →

Earn 3 college credits for Quantitative AnalysisRecommended for credit by NCCRS · Math 250 · self-paced · one payment, lifetime access
Enroll in Quantitative Analysis · $250 →Download the syllabus (PDF)

In this lesson

What it is, where it appears, and why it matters.

  • Recognise it as a special case of transportation
  • Define its variables, constraints and objective
  • Explain why total unimodularity gives 0-1 answers
  • Formulate and solve a small binary LP

Transcript

Everything said in the video, section by section (1,641 words). Read along, or search it.

Assignment Problem · Section 13.1

The Assignment Problem

Welcome to section thirteen point one of Quantitative Analysis. This section is about the assignment problem. It answers one deceptively simple question. Who should do what? Four consultants and four projects. Four machines and four jobs. Each side matched exactly once, with nothing left over. That can sound more like a puzzle than a serious optimisation model. It is not. The assignment problem is a special case of the transportation problem. And it carries two beautiful properties that make it far easier to solve than it looks. By the end you will formulate one, solve one, and see exactly why greedy matching fails.

Definition

Matching Agents to Tasks, One to One

Start with the definition. The assignment problem matches a group of agents to an equal-sized group of tasks. The matching is strictly one to one. Every agent is assigned to exactly one task, and every task is done by exactly one agent. No agent sits idle, and no task is left uncovered. That is the whole structure, and it is remarkably clean. It is a special case of the transportation problem, and the word special is doing real work. A transportation problem allows any supplies and any demands. The assignment problem forces every supply and every demand to be exactly one. It also requires equal numbers of agents and tasks, which we call a balanced problem. What you get in return for those restrictions is a far easier problem to solve.

Four Ingredients

What Specifies an Assignment Problem

An assignment problem of a given size is specified by four ingredients. First, the agents. Workers, machines, salespeople, vehicles, consultants. Second, the tasks. Jobs, routes, territories, time slots, projects. Third, the cost matrix, written as a capital C. It is a square table with one row per agent and one column per task. The entry in row i, column j, is the cost of putting agent i on task j. That entry can be a cost, a profit, or a skill-fit score, depending on the question. Fourth, the decision variables, and these are purely binary. Each one equals one if that agent takes that task, and zero otherwise. Nothing in between is allowed. There is no such thing as half an assignment. Fix those four and the model writes itself, though in practice almost all the effort goes into the third ingredient.

Formal Model

The Minimisation Version

Here is the formal model, in its minimisation form. Minimise Z, the double sum over all agents and all tasks, of cost times variable. Only the cells you actually select contribute, because every other variable is zero. Then come two families of constraints. For every agent, that agent's row of variables sums to one. In words, each agent does exactly one task. For every task, that task's column of variables sums to one. In words, each task is done by exactly one agent. And every variable is restricted to zero or one. If your matrix holds profit, productivity or skill fit, simply replace minimise with maximise. Every other constraint stays exactly the same. One practical note. If agents and tasks are unequal in number, add dummy rows or columns at zero cost.

Where It Appears

Five Canonical Applications

So where does this template actually show up? Everywhere a manager must match a set of resources to a set of jobs. Personnel assignment matches employees to positions, maximising productivity or minimising training cost. Machine to job assignment matches machines to production jobs, minimising total setup plus processing time. Sales territory assignment matches salespeople to territories, maximising expected sales from existing relationships. Simplified vehicle routing matches delivery vehicles to pre-built routes, minimising distance or fuel cost. Project team formation matches specialists to project roles, maximising total skill fit across the team. The pattern to recognise is this. If a decision can be drawn as who does what, with each side matched exactly once, this is the model. The hard part is almost never the algebra. It is estimating the matrix. Choosing a metric, and filling in entries that genuinely separate good matches from bad.

Why Not General LP

Two Properties That Change Everything

At first glance this looks like any other binary integer program, to be thrown at branch and bound. Two properties make it dramatically easier than that. The first: integer solutions come for free. The constraint matrix of an assignment problem is totally unimodular. That means every square submatrix has a determinant of zero, plus one, or minus one. A classical result in polyhedral combinatorics applies here. An LP with a totally unimodular matrix and integer right-hand sides has integer-valued optimal corners. In plain language, drop the binary requirement, let each variable range between zero and one, and solve the LP. The answer comes back as zeros and ones anyway. No branch and bound, and no rounding. The second property is raw speed. The Hungarian algorithm, published by Kuhn in nineteen fifty-five, exploits this structure directly. It runs in order n cubed time, well ahead of general simplex on the same model. For a hundred agents the difference is academic. For ten thousand, the Hungarian method finishes in seconds where general solvers may take hours.

Worked Example

4 Consultants, 4 Client Projects

Time for a worked example. A consulting firm has four consultants and four client projects next month. The partner has rated each consultant's skill fit for each project, on a zero to one hundred scale. Higher means a better match. Consultant one scores eighty-five on A, ninety-two on B, seventy-eight on C, and eighty-eight on D. Consultant two scores seventy-six, eighty-one, ninety, and seventy-three. Consultant three scores eighty-nine, seventy, eighty-five, and ninety-five. Consultant four scores eighty-two, eighty-seven, ninety-four, and eighty. The firm wants each consultant on exactly one project, and each project staffed by exactly one consultant. The goal is to maximise total skill fit across all four matches. Because higher is better, this is a maximisation problem. The constraints do not change at all. Only the direction of the objective does.

Steps 1 and 2

Decision Variables and Objective

Step one. Define the decision variables. Let the variable for consultant i and project j equal one if that consultant takes that project. And zero otherwise. With four consultants and four projects, that is sixteen binary variables, one per cell. Step two. Write the objective function. Maximise Z as the sum of every score multiplied by its own variable. Consultant one contributes eighty-five, ninety-two, seventy-eight and eighty-eight. Consultant two contributes seventy-six, eighty-one, ninety and seventy-three. Consultant three contributes eighty-nine, seventy, eighty-five and ninety-five. Consultant four contributes eighty-two, eighty-seven, ninety-four and eighty. Each line is simply that consultant's row of the score matrix. Only four of those sixteen terms will survive, because the other twelve variables are zero.

Step 3

The Eight Equality Constraints

Step three. The constraints: eight equalities, in two families of four. The first family gives one equation per consultant. Consultant one's four variables must sum to one. The same holds for consultants two, three and four. The second family gives one equation per project. The four variables that could staff project A must sum to one. The same holds for projects B, C and D. Finally, every variable is binary. Zero or one, nothing else. Now, why do you need both families? Row sums alone would let two consultants pile onto the same project. Column sums alone would let one consultant take two projects at once. Together, they force a perfect one to one matching.

Step 4

The Optimal Assignment

Step four. Solve it. Whether you run the LP or the Hungarian algorithm, you get one unique best matching. Consultant one goes to project B, scoring ninety-two. Consultant two goes to project C, scoring ninety. Consultant three goes to project D, scoring ninety-five. Consultant four goes to project A, scoring eighty-two. The total skill fit is three hundred and fifty-nine, and every other variable is zero. Now, an important correction. The chapter's own answer table reports three hundred and fifty-seven. It pairs consultant two with project A, and consultant four with project C. That matching is two points short of the best one available. Enumerating all twenty-four possible matchings confirms that three hundred and fifty-nine is the true maximum. It is worth running that check yourself. Assignment answers are easy to eyeball, and easy to get wrong.

Why Greedy Fails

The Bigger Cell Can Lose the Bigger Total

That slip is not an accident. It is exactly the trap this chapter warns about. Look at project C. Consultant two rates it ninety, her own highest score. Consultant four rates it ninety-four, his own highest score. Only one of them can have it. The tempting move is to grab the biggest number, and give project C to consultant four. That wins ninety-four, but pushes consultant two down to project A at seventy-six, for a pair worth a hundred and seventy. The other way round, consultant two takes C for ninety and consultant four takes A for eighty-two. That pair is worth a hundred and seventy-two, which is better. The smaller single cell wins the bigger total, by two points. That is the whole lesson of the assignment problem. If you ignored the one-consultant-per-project rule, everyone would take their own favourite. That totals three hundred and seventy-one, but it is infeasible, because two consultants both want C.

Summary

What to Carry Forward

Let us gather the ideas worth keeping. The assignment problem matches agents to tasks one to one, to optimise a total cost or score. It is a special case of the transportation problem, with every supply and demand equal to one. The cost matrix is a square table whose entries rate each agent on each task. The decision variables are binary indicators of who does what. Two families of equality constraints, one per row and one per column, force the perfect matching. The constraint matrix is totally unimodular, so the relaxed LP returns zeros and ones by itself. No integer programming machinery is required at all. The Hungarian algorithm solves the problem in order n cubed, far faster than general simplex at scale. And greedy, pick-your-favourite matching is generally sub-optimal. The globally best combination is rarely the sum of the individually best choices. That gap, small as it looked here, is the entire reason this model exists.

About Quantitative Analysis at UPI Study

Quantitative Analysis (Math 250) is a self-paced online course of 55 video lessons in 13 chapters, from decision analysis and simulation to inventory and queuing models, project scheduling, linear programming and transportation models. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Math courses Every course with PRO →

Compare: Statistics vs Quantitative Analysis

Why take it here

Why students take Quantitative Analysis with UPI Study

Decide with numbersQuantitative Analysis teaches the models managers use to decide under uncertainty: decision trees, simulation, inventory and queuing models, project scheduling and linear programming. It is part of many business, management, operations and supply-chain programs.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Quantitative Analysis carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About The Assignment Problem

What is the assignment problem in operations research?
The assignment problem matches a set of agents, such as workers or machines, one to one with an equal number of tasks so as to minimize total cost or maximize total score. Each agent gets exactly one task and each task exactly one agent. It is a special case of the transportation problem in which every supply and every demand equals one. Common uses include staffing, machine-job matching and sales territories.
How do you formulate an assignment problem as a linear program?
Let x_{ij} = 1 if agent i takes task j and 0 otherwise. Minimize or maximize \sum_i \sum_j c_{ij} x_{ij}. Add one constraint per agent requiring its row of variables to sum to 1, and one per task requiring its column to sum to 1. Both families are needed: rows alone would let two agents share a task, and columns alone would let one agent take two tasks.
Why does the assignment problem give integer solutions without integer programming?
Its constraint matrix is totally unimodular, meaning every square submatrix has a determinant of 0, 1 or minus 1. A linear program with such a matrix and integer right-hand sides has integer-valued optimal corner points, so relaxing the 0-1 requirement to 0 \le x_{ij} \le 1 still returns zeros and ones. No branch and bound or rounding is needed, and the Hungarian algorithm solves it in O(n^3) time.
Why does picking the best match for each person fail in assignment problems?
Greedy choices ignore how one match constrains others. In a 4 by 4 skill-fit example, giving project C to the consultant scoring 94 pushes another consultant onto a 76 match, a pair worth 170, while the alternative pairing scores 90 + 82 = 172. The overall optimum totals 359. Letting every consultant take a favorite would total 371, but it is infeasible because two consultants want the same project.

About the Quantitative Analysis course

How many college credits is Quantitative Analysis?
Quantitative Analysis (Math 250) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Quantitative Analysis cost and what is included?
$250, paid once, with lifetime access: all 55 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Quantitative Analysis take?
It is self-paced with no deadlines. The 55 lessons total about 11 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Quantitative Analysis.

55 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Quantitative Analysis →Download the syllabusEvery course with PRO →
Quantitative Analysis
3 credits · NCCRSEnroll →