In a recent work, Schmitt and Singh propose a new quadratic facility location model to address ecological challenges faced by policymakers in Bavaria, Germany. Building on this previous work, we significantly extend our understanding of this new problem. We develop connections to traditional combinatorial optimization models and show the problem is NP-hard. We then develop … Read more
We present a coarse-grain (outer-loop) parallel implementation of RLT1/2/3 (Level 1, 2, and 3 Reformulation and Linearization Technique—in that order) bound calculations for the QAP within a branch-and-bound procedure. For a search tree node of size S, each RLT3 and RLT2 bound calculation iteration is parallelized S ways, with each of S processors performing O(S5) … Read more
We address the exact solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digital wireless communications. The paper describes the techniques developed to solve this instance to proven optimality, from the choice of an appropriate mixed-integer programming formulation, to cutting planes and symmetry handling. Using these techniques … Read more
We report on a growing class of assignment problems that are increasingly of interest and very challenging in terms of the difficulty they pose to attempts at exact solution. These problems address economic issues in the location and design of factories, hospitals, depots, transportation hubs and military bases. Others involve improvements in communication network design. … Read more
We apply the level-3 Reformulation Linearization Technique (RLT3) to the Quadratic Assignment Problem (QAP). We then present our experience in calculating lower bounds using an essentially new algorithm, based on this RLT3 formulation. This algorithm is not guaranteed to calculate the RLT3 lower bound exactly, but approximates it very closely and reaches it in some … Read more
In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for the … Read more
Semidefinite Programming (SDP) provides strong bounds for many NP-hard combinatorial problems. Arguably the most popular/efficient search direction for solving SDPs using a primal-dual interior point (p-d i-p) framework is the {\em HKM direction}. This direction is a Newton direction found from the linearization of a symmetrized version of the optimality conditions. For many of the … Read more