REFORMULATING QUADRATIC ASSIGNMENT PROBLEMS FOR EFFICIENT OPTIMIZATION

Decision making problems in areas such as R&D project selection, facil ity layout design, capital budgeting, resource allocation, communicati on network design, and scheduling are more than often formulated as as signment 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 suggest ed in the literature are usually heuristic. The scarcity of exact solu tion techniques is attributed to the presence of large numbers of 0-1 variables as well as to the optimization of a nonlinear objective func tion expressed in 0-1 variables. This paper suggests a reformulation m ethod 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 com mercially available codes to solve the resulting mixed-integer linear programming problem. Computational experience with this new reformulat ion is also discussed.