A Math Programming Case Study

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!

- The Verbal formulation
- The Basic formulation
- The Mathematical formulation
- The AMPL Code
- The Network formulation
- Algorithms for solving

- Watching the clock
- Three-Sigma Quality
- Everybody Be Happy
- Brownie Points
- Bits and Pieces
AMPL Model file

`camping.mod`

AMPL Data file`camping.dat`

- The Marriage Theorem, An Assignment Problem
- A few Web resources for mathematical programming
- References for this case study

LAST MODIFIED 21 MARCH 1997