REFORMULATING QUADRATIC ASSIGNMENT PROBLEMS FOR EFFICIENT OPTIMIZATION

Abstract

Decision making problems in areas such as R&D project selection, facility layout design, capital budgeting, resource allocation, communication network design, and scheduling are more than often formulated as assignment problems with quadratic objective functions in 0-1 variables. Although quadratic assignment problems are formulated as mathematical optimization problems, the solution algorithms that have been suggested in the literature are usually heuristic. The scarcity of exact solution techniques is attributed to the presence of large numbers of 0-1 variables as well as to the optimization of a nonlinear objective function expressed in 0-1 variables. This paper suggests a reformulation method that linearizes the quadratic objective functions in assignment problems and reduces the number of 0-1 variables one has to deal with in the optimization process. The new reformulation leads to use of commercially available codes to solve the resulting mixed-integer linear programming problem. Computational experience with this new reformulation is also discussed.