The quadratic assignment problem: Algorithmic developments and applications

Recent trends of globalization and increased customer responsiveness in the chemical processing industries has emphasized the need to optimally use limited resources to maintain the competitive advantage for the firm. Computer integrated process design and operations management using a model based framework promises an effective decision making strategy in this evolving scenario. The major challenges to the successful exploitation of this approach are the interactions between various decisions which leads to nonlinearities in the mathematical model and the discrete nature of the decision making process which gets manifested in the combinatorial complexity of the solution space. The Quadratic Assignment Problem (QAP) epitomizes both these difficulties thus serving as a good prototype for studying algorithmic aspects of nonlinear discrete optimization problems. New lower bounding procedures are derived for nonlinear assignment problems using lifting procedures. Computational results using an interior point method show that this formulation is tight for all problems solvable using the current linear programming technology. Dynamic matrix factorization methods are developed for specializing linear programming algorithms for computing the relaxation bounds for the QAP. Computational results demonstrate that dynamic matrix factorization greatly improves the algorithmic efficiency in terms of memory utilization and computational speed. Customized applications have also been developed based on these concepts for (i) Process Scheduling--Minimizing product grade changes subject to product due dates and release times and (ii) Protein Folding--Determining the minimum free energy conformations of lattice models of proteins