Buch, Englisch, 168 Seiten, Previously published in hardcover, Format (B × H): 178 mm x 254 mm, Gewicht: 358 g
Reihe: Springer Series in Operations Research and Financial Engineering
A Duality Viewpoint
Buch, Englisch, 168 Seiten, Previously published in hardcover, Format (B × H): 178 mm x 254 mm, Gewicht: 358 g
Reihe: Springer Series in Operations Research and Financial Engineering
ISBN: 978-1-4419-1853-6
Verlag: Springer
Integer programming (IP) is a fascinating topic. Indeed, while linear programming (LP), its c- tinuous analogue, is well understood and extremely ef?cient LP software packages exist, solving an integer program can remain a formidable challenge, even for some small size problems. For instance, the following small (5-variable) IP problem (called the unbounded knapsack problem) min{213x?1928x?11111x?2345x +9123x} 1 2 3 4 5 s.t. 12223x +12224x +36674x +61119x +85569x = 89643482, 1 2 3 4 5 x ,x ,x ,x ,x?N, 1 2 3 4 5 taken from a list of dif?cult knapsack problems in Aardal and Lenstra [2], is not solved even by hours of computing, using for instance the last version of the ef?cient software package CPLEX. However,thisisnotabookonintegerprogramming,asverygoodonesonthistopicalreadyexist. For standard references on the theory and practice of integer programming, the interested reader is referred to, e.g., Nemhauser and Wolsey [113], Schrijver [121], Wolsey [136], and the more recent Bertsimas and Weismantel [21]. On the other hand, this book could provide a complement to the above books as it develops a rather unusual viewpoint.
Zielgruppe
Research
Autoren/Hrsg.
Fachgebiete
- Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
- Mathematik | Informatik Mathematik Operations Research
- Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
- Mathematik | Informatik EDV | Informatik Informatik Theoretische Informatik
- Mathematik | Informatik Mathematik Mathematik Interdisziplinär Finanz- und Versicherungsmathematik
Weitere Infos & Material
I Linear Integration and Linear Programming.- The Linear Integration Problem I.- Comparing the Continuous Problems P and I.- II Linear Counting and Integer Programming.- The Linear Counting Problem I.- Relating the Discrete Problems P and I with P.- III Duality.- Duality and Gomory Relaxations.- Barvinok#x2019;s Counting Algorithm and Gomory Relaxations.- A Discrete Farkas Lemma.- The Integer Hull of a Convex Rational Polytope.- Duality and Superadditive Functions.
