Lasserre Linear and Integer Programming vs Linear Integration and Counting

A Duality Viewpoint
1. Auflage 2009
ISBN: 978-0-387-09414-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 168 Seiten

Reihe: Springer Series in Operations Research and Financial Engineering

This book analyzes and compares four closely related problems, namely linear programming, integer programming, linear integration, and linear summation (or counting). The book provides some new insights on duality concepts for integer programs.

Autoren/Hrsg.

Lasserre, Jean-Bernard

Inhaltsverzeichnis

1;Springer Series in Operations Researchand Financial Engineering;2
2;Preface;7
3;Contents;10
4;Introduction;13
4.1;The four problems P,Pd,I,Id;14
4.2;Summary of content;16
5;Part I Linear Integration and Linear Programming;18
5.1;The Linear Integration Problem I ;19
5.1.1;Introduction;19
5.1.2;Primal methods;21
5.1.3;A dual approach;25
5.1.4;A residue algorithm for problem I*;28
5.1.5;Notes;39
5.2;Comparing the Continuous Problems P and I ;40
5.2.1;Introduction;40
5.2.2;Comparing P,P*,I, and I;42
5.2.3;Notes;46
6;Part II Linear Counting and Integer Programming;47
6.1;The Linear Counting Problem Id;48
6.1.1;Introduction;48
6.1.2;A primal approach: Barvinok's counting algorithm;49
6.1.3;A dual approach;52
6.1.4;Inversion of the Z-transform by residues;55
6.1.5;An algebraic method;59
6.1.6;A simple explicit formula;72
6.1.7;Notes;76
6.2;Relating the Discrete Problems ¶d and Id with ¶;77
6.2.1;Introduction;77
6.2.2;Comparing the dual problems I* and Id*;78
6.2.3;A dual comparison of P and Pd;79
6.2.4;Proofs;83
6.2.5;Notes;85
7;Part III Duality;86
7.1;Duality and Gomory Relaxations;87
7.1.1;Introduction;87
7.1.2;Gomory relaxations;88
7.1.3;Brion and Vergne's formula and Gomory relaxations;90
7.1.4;The knapsack problem;98
7.1.5;A dual of Pd;100
7.1.6;Proofs;103
7.1.7;Notes;110
7.2;Barvinok's Counting Algorithm and Gomory Relaxations;111
7.2.1;Introduction;111
7.2.2;Solving Pd via Barvinok's counting algorithm;112
7.2.3;The link with Gomory relaxations;115
7.2.4;Notes;116
7.3;A Discrete Farkas Lemma;118
7.3.1;Introduction;118
7.3.2;A discrete Farkas lemma;119
7.3.3;A discrete theorem of the alternative;128
7.3.4;The knapsack equation;130
7.3.5;Notes;132
7.4;The Integer Hull of a Convex Rational Polytope;133
7.4.1;Introduction;133
7.4.2;The integer hull;134
7.4.3;Notes;139
7.5;Duality and Superadditive Functions;141
7.5.1;Introduction;141
7.5.2;Preliminaries;142
7.5.3;Duality and superadditivity;144
7.5.4;Notes;149
7.6;Appendix Legendre--Fenchel, Laplace, Cramer, and Z-Transforms;150
7.6.1;The Legendre--Fenchel transform;150
7.6.2;Laplace transform;152
7.6.3;The Z-transform;156
7.6.4;Notes;158
7.7;References;159
7.8;Glossary;159
7.9;Index;166