max planck institut informatik
mpii logo Minerva of the Max Planck Society

A Novel SDP Relaxation for the Quadratic Assignment Problem using Cut Pseudo Bases ISCO 2016


A Novel SDP Relaxation for the Quadratic Assignment Problem using Cut Pseudo Bases




Maximilian John1     Andreas Karrenbauer1    

1 MPI for Informatics, Germany    


Abstract

The quadratic assignment problem (QAP) is one of the hardest combinatorial optimization problems. Its range of applications is wide, including facility location, keyboard layout, and various other domains. The key success factor of specialized branch-and-bound frameworks for minimizing QAPs is an efficient implementation of a strong lower bound. In this paper, we propose a lower-bound-preserving transformation of a QAP to a different quadratic problem that allows for small and efficiently solvable SDP relaxations. This transformation is self-tightening in a branch-and-bound process. Our experimental evaluations show promising results, in particular for instances with a small width in one of the dimensions.

Materials for Download

 Conference Paper.
BibTeX.
Slides of talk at ISCO 2016.

Addditional Materials

  • Source Code: branch-and-bound framework for our SDP approach implemented in C++, used for the ISCO paper:
    		Mosek version out now
    		Gurobi version coming soon. This framework has lead to more promising results, so we will focus our support on this.
  • The QAP instances were all taken from the QAPLIB
  • The complete table of evaluation results is available as a csv file here. The readme file contains further explanations to the csv columns.

Citation

Maximilian John, Andreas Karrenbauer
A Novel SDP Relaxation for the Quadratic Assignment Problem using Cut Pseudo Bases
2016 Proceedings of the Fourth International Symposium on Combinatorial Optimization (ISCO) 

  @Inbook{John2016,
	author="John, Maximilian
	and Karrenbauer, Andreas",
	editor="Cerulli, Raffaele
	and Fujishige, Satoru
	and Mahjoub, Ridha A.",
	title="A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases",
	bookTitle="Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers",
	year="2016",
	publisher="Springer International Publishing",
	address="Cham",
	pages="414--425",
	isbn="978-3-319-45587-7",
	doi="10.1007/978-3-319-45587-7_36",
	url="http://dx.doi.org/10.1007/978-3-319-45587-7_36"
  }