Integer programming: Optimization and evaluation are equivalent

James B. Orlin, Abraham P. Punnen, Andreas S. Schulz

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

We show that if one can find the optimal value of an integer linear programming problem in polynomial time, then one can find an optimal solution in polynomial time. We also present a proper generalization to (general) integer programs and to local search problems of the well-known result that optimization and augmentation are equivalent for 0/1-integer programs. Among other things, our results imply that PLS-complete problems cannot have "near-exact" neighborhoods, unless PLS = P.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings
PublisherSpringer Verlag
Pages519-529
Number of pages11
ISBN (Print)3642033660, 9783642033667
DOIs
StatePublished - 2009
Externally publishedYes
Event11th International Symposium on Algorithms and Data Structures, WADS 2009 - Banff, AB, Canada
Duration: 21 Aug 200923 Aug 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5664 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Symposium on Algorithms and Data Structures, WADS 2009
Country/TerritoryCanada
CityBanff, AB
Period21/08/0923/08/09

Fingerprint

Dive into the research topics of 'Integer programming: Optimization and evaluation are equivalent'. Together they form a unique fingerprint.

Cite this