Nonlinear Integer Programming

Raymond Hemmecke (), Matthias Köppe (), Jon Lee () and Robert Weismantel ()
Additional contact information
Raymond Hemmecke: FMA/IMO, Otto-von-Guericke-Universität Magdeburg
Matthias Köppe: University of California, Department of Mathematics
Jon Lee: IBM T.J. Watson Research Center, Yorktown Heights
Robert Weismantel: FMA/IMO, Otto-von-Guericke-Universität Magdeburg

Chapter Chapter 15 in 50 Years of Integer Programming 1958-2008, 2010, pp 561-618 from Springer

Abstract: Abstract Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. This chapter is dedicated to this topic. The primary goal is a study of a simple version of general nonlinear integer problems, where all constraints are still linear. Our focus is on the computational complexity of the problem, which varies significantly with the type of nonlinear objective function in combination with the underlying combinatorial structure. Numerous boundary cases of complexity emerge, which sometimes surprisingly lead even to polynomial time algorithms.We also cover recent successful approaches for more general classes of problems. Though no positive theoretical efficiency results are available, nor are they likely to ever be available, these seem to be the currently most successful and interesting approaches for solving practical problems. It is our belief that the study of algorithms motivated by theoretical considerations and those motivated by our desire to solve practical instances should and do inform one another. So it is with this viewpoint that we present the subject, and it is in this direction that we hope to spark further research.

Keywords: Integer Point; Convex Envelope; Fully Polynomial Time Approximation Scheme; Graver Basis; Independence System (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:sprchp:978-3-540-68279-0_15

Ordering information: This item can be ordered from
http://www.springer.com/9783540682790

DOI: 10.1007/978-3-540-68279-0_15

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().