Extensions on ellipsoid bounds for quadratic integer programming

Marcia Fampa () and Francisco Pinillos Nieto ()
Additional contact information
Marcia Fampa: Universidade Federal do Rio de Janeiro
Francisco Pinillos Nieto: Universidade Federal do Rio de Janeiro

Journal of Global Optimization, 2018, vol. 71, issue 3, No 3, 457-482

Abstract: Abstract Ellipsoid bounds for strictly convex quadratic integer programs have been proposed in the literature. The idea is to underestimate the strictly convex quadratic objective function q of the problem by another convex quadratic function with the same continuous minimizer as q and for which an integer minimizer can be easily computed. We initially propose in this paper a different way of constructing the quadratic underestimator for the same problem and then extend the idea to other quadratic integer problems, where the objective function is convex (not strictly convex), and where the objective function is nonconvex and box constraints are introduced. The quality of the bounds proposed is evaluated experimentally and compared to the related existing methodologies.

Keywords: Quadratic integer programming; Ellipsoid bound; Integer relaxation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-017-0557-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jglopt:v:71:y:2018:i:3:d:10.1007_s10898-017-0557-2

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-017-0557-2

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().