Linear and Integer Programming vs Linear Integration and Counting

A Duality Viewpoint

Häftad, Engelska, 2010

Av Jean-Bernard Lasserre

1 409 kr

Beställningsvara. Skickas inom 10-15 vardagar

Fri frakt för medlemmar vid köp för minst 249 kr.

Finns i fler format (1)

Inbunden

1 409 kr

Skickas inom 10-15 vardagar

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.

Produktinformation

Utgivningsdatum2010-12-15
Mått178 x 235 x undefined mm
FormatHäftad
SpråkEngelska
SerieSpringer Series in Operations Research and Financial Engineering
Antal sidor168
FörlagSpringer-Verlag New York Inc.
ISBN9781441918536

Tillhör följande kategorier

Systemvetenskap och AI inom Data och it
Företagsekonomi inom Ekonomi och ledarskap
Matematik inom Naturvetenskap och teknik
Diskret matematik inom Naturvetenskap och teknik
Optimering inom Naturvetenskap och teknik

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.

From the reviews:“Lasserre has produced a fascinating slim … monograph (much of the work his own) looking at the parallels between linear (respectively integer) programming on the one hand and integration (respectively integer counting) problems on the other hand. … An appendix on various transforms a hundred references and a brief index complete the work which is a welcome addition to an important set of topics.” (J. Borwein, Mathematical Reviews, Issue 2010 f)“This book is devoted to analysing four important problems: integer programming problem, linear programming problem, linear integration problem, and linear counting problem. … a very specialized book on the integer programming problem and its dual variants. … can be very helpful for researchers working in developing algorithms for the integer programming problem which is a formidable challenging problem. This is a clear and well-written book … .” (E. Almehdawe, Journal of the Operational Research Society, Vol. 61 (12), 2010)