An Exact Algorithm for Quadratic Integer Minimization using Nonconvex Relaxations

Christoph Buchheim (christoph.buchheim@tu-dortmund.de), Marianna De Santis (mdesantis@dis.uniroma1.it), Laura Palagi and Mauro Piacentini (piacentini@dis.uniroma1.it)
Additional contact information
Christoph Buchheim: Fakultat fur Mathematik, TU Dortmund
Marianna De Santis: Istituto di Analisi dei Sistemi e Informatica Antonio Ruberti – IASI CNR Roma
Mauro Piacentini: Department of Computer, Control, and Management Engineering Antonio Ruberti Sapienza Universita di Roma

No 2012-05, DIS Technical Reports from Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza"

Abstract: We propose a branch-and-bound algorithm for minimizing a not necessarily convex quadratic function over integer variables. The algorithm is based on lower bounds computed as continuous minima of the objective function over appropriate ellipsoids. In the nonconvex case, we use ellipsoids enclosing the feasible region of the problem. In spite of the nonconvexity, these minima can be computed quickly. We present several ideas that allow to accelerate the solution of the continuous relaxation within a branch-and-bound scheme and examine the performance of the overall algorithm by computational experiments.

Date: 2012
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.dis.uniroma1.it/~bibdis/RePEc/aeg/wpaper/2012-05.pdf First version, 2012 (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:aeg:wpaper:2012-5

Access Statistics for this paper

More papers in DIS Technical Reports from Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza" Contact information at EDIRC.
Bibliographic data for series maintained by Antonietta Angelica Zucconi (antonietta.zucconi@uniroma1.it this e-mail address is bad, please contact repec@repec.org).