Back to the program.
On Solving Hard Quadratic 3-Dimensional Assignment Problems from Wireless Communications
Hans Mittelmann
School of Mathematical and Statistical Sciences
Arizona State University

Abstract

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.

The speaker is hosted by Martine Labbe and Thomas Stuetzle.
This seminar is a joint seminar between the CS department and IRIDIA.

Keywords

optimization, wireless communications, quadratic assignment