The Multi-Dimensional Assignment and Quadratic Assignment Problems

Authors

William P. Pierskalla

Document Type

Report

Publication Date

9-1-1967

Abstract

The multi-dimensional assignment problem is a higher dimensional version of the standard (two-dimensional) assignment problem in the literature. The higher dimensions can be though of as time or space dimensions or both. An algorithm is proposed for the solution of the multi-index assignment problem. The algorithm is based on a tree search technique of the branch and bound variety. It uses dual subproblems to provide easily computed bounds for the primal assignment problem. The same algorithm with appropriate modifications is used to find an optimal solution to the multi-dimensional quadratic assignment problem.

Keywords

Operations research, Assignment problem (Programming), Mathematical optimization, Algorithms, Branch and bound algorithms, Linear programming, Quadratic programming

Publication Title

Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University

Issue

Technical memorandum no. 93

Rights

This work is in the public domain and may be freely downloaded for personal or academic use

Recommended Citation

Pierskalla, William P., "The Multi-Dimensional Assignment and Quadratic Assignment Problems" (1967). Research Reports from the Department of Operations. 319.
https://commons.case.edu/wsom-ops-reports/319