Optimization Online


On Solving a Hard Quadratic 3-Dimensional Assignment Problem

Hans D Mittelmann (mittelmann***at***asu.edu)
Domenico Salvagnin (salvagni***at***math.unipd.it)

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 eff ort (2.5 million nodes and one week of computations on a standard PC).

Keywords: Mixed-Integer Programming, Quadratic Assignment, Symmetry

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Applications -- OR and Management Sciences (Telecommunications )


Download: [PDF]

Entry Submitted: 09/27/2013
Entry Accepted: 09/28/2013
Entry Last Modified: 01/03/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society