On the Applicability of Lower Bounds for Solving Rectilinear

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

    Research output: Contribution to journalJournal articleResearchpeer-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 languageEnglish
    JournalComputational Optimization and Applications
    Volume10
    Issue number2
    Pages (from-to)127-147
    ISSN0926-6003
    Publication statusPublished - 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