Hans Mittelmann

Arizona State University

Thursday, June 25, 2015, 11:00 - 12:00

Room 01-012, Georges-Köhler-Allee 102, Freiburg 79110, Germany

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 we were able to solve the target instance with moderate computational effort (2.5 million nodes and one week of computations on a standard PC). Further such problems with different modulations and thus reduced symmetry are near optimally solved using metaheuristic and engineering ad hoc approaches.