On the Applicability of Lower Bounds for Solving Rectilinear

Jens Clausen; Stefan E. Karisch; M. Perregaard; F. Rendl

On the Applicability of Lower Bounds for Solving Rectilinear

Jens Clausen, Stefan E. Karisch, M. Perregaard, F. Rendl

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.

Original language	English
Journal	Computational Optimization and Applications
Volume	10
Issue number	2
Pages (from-to)	127-147
ISSN	0926-6003
Publication status	Published - 1998

Fingerprint Dive into the research topics of 'On the Applicability of Lower Bounds for Solving Rectilinear'. Together they form a unique fingerprint.

Cite this

@article{3ee90cbd17b74a5881398527a48cc1cf,

title = "On the Applicability of Lower Bounds for Solving Rectilinear",

abstract = "The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.",

author = "Jens Clausen and Karisch, {Stefan E.} and M. Perregaard and F. Rendl",

year = "1998",

language = "English",

volume = "10",

pages = "127--147",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - On the Applicability of Lower Bounds for Solving Rectilinear

AU - Clausen, Jens

AU - Karisch, Stefan E.

AU - Perregaard, M.

AU - Rendl, F.

PY - 1998

Y1 - 1998

N2 - The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.

AB - The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.

M3 - Journal article

VL - 10

SP - 127

EP - 147

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

SN - 0926-6003

IS - 2

ER -