Box-inequalities for quadratic assignment polytopes

Citation
M. Junger et V. Kaibel, Box-inequalities for quadratic assignment polytopes, MATH PROGR, 91(1), 2001, pp. 175-197
Citations number
34
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
91
Issue
1
Year of publication
2001
Pages
175 - 197
Database
ISI
SICI code
0025-5610(200110)91:1<175:BFQAP>2.0.ZU;2-O
Abstract
Linear Programming based lower bounds have been considered both for the gen eral as well as for the symmetric quadratic assignment problem several time s in the recent years, Their quality has turned out to be quite good in pra ctice, Investigations of the polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadr atic assignment polytope) have been started during the last decade \ 34.31, 21.22 \. They have lead to basic knowledge on these polytopes concerning q uestions like their dimensions. affine hulls. and trivial facets. However, no large class of(facet-defining) inequalities that Could be used in cuttin g plane procedures had been found. We present in this paper the first such class of inequalities, the box inequalities, which have an interesting orig in in some well-known hypermetric inequalities for the Cut polytope. Comput ational experiment, with a cutting plane algorithm based (in these inequali ties show that they are very useful with respect to the goal of solving qua dratic assignment problems to optimality or to compute tight lower bounds. The most effective ones among the new inequalities turn out to be indeed fa cet-defining for both the non-symmetric as well as for the symmetric quadra tic assignment polytope.