Linear and Integer Programming vs Linear Integration and Counting (eBook)

Springer Series in Operations Researchand Financial Engineering 2
Preface 7
Contents 10
Introduction 13
The four problems P,Pd,I,Id 14
Summary of content 16
Part I Linear Integration and Linear Programming 18
The Linear Integration Problem I 19
Introduction 19
Primal methods 21
A dual approach 25
A residue algorithm for problem I* 28
Notes 39
Comparing the Continuous Problems P and I 40
Introduction 40
Comparing P,P*,I, and I 42
Notes 46
Part II Linear Counting and Integer Programming 47
The Linear Counting Problem Id 48
Introduction 48
A primal approach: Barvinok's counting algorithm 49
A dual approach 52
Inversion of the Z-transform by residues 55
An algebraic method 59
A simple explicit formula 72
Notes 76
Relating the Discrete Problems ¶d and Id with ¶ 77
Introduction 77
Comparing the dual problems I* and Id* 78
A dual comparison of P and Pd 79
Proofs 83
Notes 85
Part III Duality 86
Duality and Gomory Relaxations 87
Introduction 87
Gomory relaxations 88
Brion and Vergne's formula and Gomory relaxations 90
The knapsack problem 98
A dual of Pd 100
Proofs 103
Notes 110
Barvinok's Counting Algorithm and Gomory Relaxations 111
Introduction 111
Solving Pd via Barvinok's counting algorithm 112
The link with Gomory relaxations 115
Notes 116
A Discrete Farkas Lemma 118
Introduction 118
A discrete Farkas lemma 119
A discrete theorem of the alternative 128
The knapsack equation 130
Notes 132
The Integer Hull of a Convex Rational Polytope 133
Introduction 133
The integer hull 134
Notes 139
Duality and Superadditive Functions 141
Introduction 141
Preliminaries 142
Duality and superadditivity 144
Notes 149
Appendix Legendre--Fenchel, Laplace, Cramer, and Z-Transforms 150
The Legendre--Fenchel transform 150
Laplace transform 152
The Z-transform 156
Notes 158
References 159
Glossary 159
Index 166