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.