IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v41y1995i4p704-712.html
   My bibliography  Save this article

A Decomposition Method for Quadratic Zero-One Programming

Author

Listed:
  • Pierre Chardaire

    (School of Information Systems, University of East Anglia, Norwich NR4 7TJ, United Kingdom)

  • Alain Sutter

    (France-Télécom, CNET, 38-40 rue du général Leclerc, F 92131 Issy Les Moulineaux, France)

Abstract

This paper proposes a decomposition method to compute a lower bound for unconstrained quadratic zero-one minimization. First, we show that any quadratic function can be expressed as a sum of particular quadratic functions whose minima can be computed by a simple branch and bound algorithm. Then, assuming some hypothesis, we prove that, among all possible decompositions, the best one can be found by a Lagrangian decomposition method. Moreover, we show that our algorithm gives at least the roof dual bound and should give better results in practice. Eventually, computational results and comparison with Pardalos and Rodgers' algorithm demonstrate the efficiency of our method for medium size problems (up to 100 variables).

Suggested Citation

  • Pierre Chardaire & Alain Sutter, 1995. "A Decomposition Method for Quadratic Zero-One Programming," Management Science, INFORMS, vol. 41(4), pages 704-712, April.
    • Handle: RePEc:inm:ormnsc:v:41:y:1995:i:4:p:704-712
    DOI: 10.1287/mnsc.41.4.704
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.41.4.704
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.41.4.704?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
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lodi, Andrea & Allemand, Kim & Liebling, Thomas M., 1999. "An evolutionary heuristic for quadratic 0-1 programming," European Journal of Operational Research, Elsevier, vol. 119(3), pages 662-670, December.
    2. Fred Glover & Gary A. Kochenberger & Bahram Alidaee, 1998. "Adaptive Memory Tabu Search for Binary Quadratic Programs," Management Science, INFORMS, vol. 44(3), pages 336-345, March.
    3. Serigne Gueye & Philippe Michelon, 2005. "“Miniaturized” Linearizations for Quadratic 0/1 Problems," Annals of Operations Research, Springer, vol. 140(1), pages 235-261, November.
    4. Goldengorin, Boris & Vink, Marius de, 1999. "Solving large instances of the quadratic cost of partition problem on dense graphs by data correcting algorithms," Research Report 99A50, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    5. Billionnet, Alain & Faye, Alain & Soutif, Eric, 1999. "A new upper bound for the 0-1 quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 112(3), pages 664-672, February.
    6. repec:dgr:rugsom:99a50 is not listed on IDEAS
    7. Gili Rosenberg & Mohammad Vazifeh & Brad Woods & Eldad Haber, 2016. "Building an iterative heuristic solver for a quantum annealer," Computational Optimization and Applications, Springer, vol. 65(3), pages 845-869, December.
    8. Neng Fan & Panos Pardalos, 2010. "Linear and quadratic programming approaches for the general graph partitioning problem," Journal of Global Optimization, Springer, vol. 48(1), pages 57-71, September.
    9. Billionnet, Alain & Soutif, Eric, 2004. "An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 157(3), pages 565-575, September.

    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:ormnsc:v:41:y:1995:i:4:p:704-712. 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.