M/E 19

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. When error correction of a transmitted message is not possible, an automatic repeat request (ARQ) may be sent. For the case of PSK coding we describe 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. Combining these approaches we are able to solve this problem with moderate computational effort (2.5 million nodes and the equivalent of one week of computations on a standard PC). This is joint work with Domenico Salvagnin, University of Padova.

Prof. Dr. Hans Mittelmann

School of Mathematical and Statistical Sciences, Arizona State University