A Decomposition Method for Quadratic Zero-One Programming

Pierre Chardaire and Alain Sutter
Additional contact information
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

Management Science, 1995, vol. 41, issue 4, 704-712

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).

Keywords: quadratic 0--1 programming; mixed integer programming; Lagrangean decomposition (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.41.4.704 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:41:y:1995:i:4:p:704-712

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().