@inproceedings{b7b2bd6b3f0a40fabace8660c24b440b,

title = "Integer programming: Optimization and evaluation are equivalent",

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.",

author = "Orlin, {James B.} and Punnen, {Abraham P.} and Schulz, {Andreas S.}",

year = "2009",

doi = "10.1007/978-3-642-03367-4_45",

language = "English",

isbn = "3642033660",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "519--529",

booktitle = "Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings",

note = "11th International Symposium on Algorithms and Data Structures, WADS 2009 ; Conference date: 21-08-2009 Through 23-08-2009",

}