The linear assignment problem is a classic problem in combinatorial optimization. We are given a collection of jobs to be performed and a group of workers that can be assigned to the various jobs. We assume that each worker can complete only one job, and that there is a known cost associated with having a worker perform a particular job. The objective is to find an assignment of jobs to workers that minimizes the total cost of completing the jobs. The problem can be generalized to include a quadratic objective function or multi-dimensional assignment constraints.
This book is a comprehensive reference on theory and algorithms for the solution of assignment problems. The book begins with an introductory chapter that defines the linear, quadratic, and multi-index assignment problems. This is followed by a chapter on theoretical foundations including the marriage theorem and the structure of the assignment polytope. In the remainder of the book, the authors deal with linear assignment problems, quadratic assignment problems (QAP), and mult-index assignment problems.
The linear assignment problem can be solved in polynomial time by a variety of methods. Since the linear assignment problem is a linear programming problem, the simplex method for LP can be specialized to deal with linear assignment problems. Algorithms for special cases of the linear assignment problem and general purpose primal, dual, and primal-dual methods are discussed in chapters three through six.
The quadratic assignment problem is much harder in theory and in practice to solve. In particular, the QAP is an NP-Hard problem. Formulations of the quadratic assignment problem and methods for bounding the value of a QAP are discussed in chapter seven. Algorithms for the QAP include branch and bound algorithms that are appropriate for smaller instances and heuristics that may be useful for larger instances. These algorithms are presented in chapter eight. Chapter nine covers variations on the quadratic assignment problem.
Although the linear and quadratic assignment problems have been well studied, comparatively little work has been done on the multi-index assignment problem. Most of the work in this area has been on the axial and planar variations of the three-index assignment problem. Some work has begun on more general multi-index assignment problems. The three-index and multi-index assignment problems are discussed in chapter ten.
The authors have done a good job of covering the breadth of research on the theory of assignment problems and algorithms for their solution. They have also provided pointers to available software implementations of the algorithms. This book will be a useful reference for researchers who need to solve assignment problems.
Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.