Jünger, Michael and Kaibel, Volker (2000). On the SQAP-Polytope. SIAM Journal on Optimization, 11 (2). pp. 444-463. SIAM.

[img]
Preview
PDF
zpr96-241.pdf - Submitted Version

Download (376kB) | Preview

Abstract

The study of the QAP-Polytope was started by Rijal (1995), Padberg and Rijal (1996), and Jünger and Kaibel (1996), investigating the structure of the feasible points of a (Mixed) Integer Linear Programming formulation of the QAP that provides good lower bounds by its continious relaxation. Rijal (1995), Padberg and Rijal (1996) propose an alternative (Mixed) Integer Linear Programming formulation for the case that the QAP-instance is symmetric in a certain sense and define analogously the SQAP-Polytope. They give a conjecture about the dimension of that polytope, whose proof is one part of this paper. Moreover, we investigate the trivial faces of the SQAP-Polytope and present a first class of non-trivial facets of it. The polyhedral results are used to compute lower bounds for symmetric QAPs.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Jünger, MichaelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Kaibel, VolkerUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-547600
Journal or Publication Title: SIAM Journal on Optimization
Volume: 11
Number: 2
Page Range: pp. 444-463
Date: 2000
Publisher: SIAM
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54760

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item