The Assignment Problem:
A Math Programming Case Study

Description of the assignment problem

In the classical assignment problem, the goal is to find an optimal assignment of agents to tasks without assigning an agent more than once and ensuring that all tasks are completed. The objective might be to minimize the total time to complete a set of tasks, or to maximize skill ratings, or to minimize the cost of the assignments.

The assignment problem is a particular class of transportation linear programming problems with the supplies and demands equal to integers (often 1). Since all supplies, demands, and bounds on variables are integral, the assignment problem relies on a nice property of transportation problems that the optimal solution will be entirely integral. As you will see, the goal of the objective of the assignment problem (unlike transportation problems) may not have anything to do at all with moving anything!

Applications of assignment problems are varied in the real world. Certainly it can be useful for the classic task of assigning employees to tasks or machines to production jobs, but its uses are more widespread. It could be used to assign fleets of aircrafts to particular trips, or assigning school buses to routes, or networking computers. In rare cases, it can even be used to determine marriage partners!

Formulation of the classical assignment problem as a linear program

Part 1: Forming a general model

Part 2: Solving an AMPL Model: The Camping Trip

Part 3: Additional Information

[ Assignment Problem Case Study | Formulation | Camping Trip | Marriage Theorem | Links and References ]

Comments or questions? Write to

Return to Julie's home page.