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

A Duality Viewpoint

Jean-Bernard Lasserre (Autor)

eBook Download: PDF

2009 | 2009
XIV, 168 Seiten
Springer New York (Verlag)
978-0-387-09414-4 (ISBN)

Infos

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.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 21.4.2009
• Reihe/Serie: Springer Series in Operations Research and Financial Engineering
• Reihe/Serie: Springer Series in Operations Research and Financial Engineering
• Zusatzinfo: XIV, 168 p. 2 illus.
• Verlagsort: New York
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik
• Themenwelt: Technik
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management
• Schlagworte: algorithms • Brion • interger programming • linear integration • linear optimization • Linear Programming • linear summation • Operations Research • Optimization • Vergne
• ISBN-10: 0-387-09414-8 / 0387094148
• ISBN-13: 978-0-387-09414-4 / 9780387094144