IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v42y1994i5p837-845.html
   My bibliography  Save this article

A Constructive Method for Improving Lower Bounds for a Class of Quadratic Assignment Problems

Author

Listed:
  • Jaishankar Chakrapani

    (Environmental Systems Research Institute, Redlands, California)

  • Jadranka Skorin-Kapov

    (State University of New York at Stony Brook, Stony Brook, New York)

Abstract

A new approach to evaluate lower bounds for a class of quadratic assignment problems ( QAP ) is presented. An instance of a QAP of size n is specified by two n × n matrices D and F , and is denoted by QAP ( D , F ). This approach is presented for QAPs where D is the matrix of rectilinear distances between points on a regular grid. However, it can easily be generalized to a wider class of problems. Two matrices F opt and F res are constructed such that F = F opt + F res , and the optimal solution to QAP ( D , F opt ) is known. Any existing lower bound can then be applied to QAP ( D , F res ), which in sum with the optimal value for QAP ( D , F opt ), provides a lower bound to QAP ( D , F ). Thus, this method could serve as a reduction process to possibly improve the results from a variety of bounding techniques. This approach is tested on two bounds from the literature, the Gilmore-Lawler bound (GLB) and an eigenvalue bound (PB), for various problems of size ranging from 6–49. Computational results show a good improvement in bounds for all the test problems. An extension of our method to a more general class of QAPs is also presented.

Suggested Citation

  • Jaishankar Chakrapani & Jadranka Skorin-Kapov, 1994. "A Constructive Method for Improving Lower Bounds for a Class of Quadratic Assignment Problems," Operations Research, INFORMS, vol. 42(5), pages 837-845, October.
    • Handle: RePEc:inm:oropre:v:42:y:1994:i:5:p:837-845
    DOI: 10.1287/opre.42.5.837
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.42.5.837
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.42.5.837?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:42:y:1994:i:5:p:837-845. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.