Norm bounds and underestimators for unconstrained polynomial integer minimization

Sönke Behrends (), Ruth Hübner and Anita Schöbel
Additional contact information
Sönke Behrends: University of Göttingen
Ruth Hübner: University of Göttingen
Anita Schöbel: University of Göttingen

Mathematical Methods of Operations Research, 2018, vol. 87, issue 1, No 4, 73-107

Abstract: Abstract We consider the problem of minimizing a polynomial function over the integer lattice. Though impossible in general, we use a known sufficient condition for the existence of continuous minimizers to guarantee the existence of integer minimizers as well. In case this condition holds, we use sos programming to compute the radius of a p-norm ball which contains all integer minimizers. We prove that this radius is smaller than the radius known from the literature. Our numerical results show that the number of potentially optimal solutions is reduced by several orders of magnitude. Furthermore, we derive a new class of underestimators of the polynomial function. Using a Stellensatz from real algebraic geometry and again sos programming, we optimize over this class to get a strong lower bound on the integer minimum. Also our lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.

Keywords: Integer optimization; Polynomials; Lower bounds; Branch and bound (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/s00186-017-0608-y 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:mathme:v:87:y:2018:i:1:d:10.1007_s00186-017-0608-y

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-017-0608-y

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().