Linear and Integer Programming vs Linear Integration and Counting

by Lasserre, Jean-Bernard

• ISBN13: 9780387094137
• ISBN10: 038709413X
• Format: Hardcover
• Copyright: 2009-05-05
• Publisher: Springer Verlag

Summary

This book analyzes and compares four closely related problems, namely linear programming, integer programming, linear integration, and linear summation (or counting). The focus is on duality and the novel approach puts integer programming in perspective with three associated problems, and permits one to define discrete analogues of well-known continuous duality concepts, and the rationale behind them. Also, the approach highlights the difference between the discrete and continuous cases. Central in the analysis are the continuous and discrete Brion and Vergne's formulae for linear integration and counting which are not very well-known in the optimization community. This approach provides some new insights on duality concepts for integer programs, and also permits to retrieve and shed new light on some well-known results. For instance, Gomory relaxations and the abstract superadditive dual of integer programs are re-interpreted in this algebraic approach.This book will serve graduate students and researchers in applied mathematics, optimization, operations research and computer science. Due to the substantial practical importance of some presented problems, researchers in other areas will also find this book useful.

Table of Contents

Preface	p. vii
Introduction	p. 1
The four problems P,<$$$>,I,<$$$>	p. 2
Summary of content	p. 4
Linear Integration and Linear Programming
The Linear Integration Problem I	p. 9
Introduction	p. 9
Primal methods	p. 11
A dual approach	p. 15
A residue algorithm for problem I*	p. 18
Notes	p. 29
Comparing the Continuous Problems P and I	p. 31
Introduction	p. 31
Comparing P,P*,I and I*	p. 33
Notes	p. 37
Linear Counting and Integer Programming
The Linear Counting Problem <$$$>	p. 41
Introduction	p. 41
A primal approach: Barvinok's counting algorithm	p. 42
A dual approach	p. 45
Inversion of the <$$$>-transform by residues	p. 48
An algebraic method	p. 52
A simple explicit formula	p. 65
Notes	p. 69
Relating the Discrete Problems <$$$> and <$$$> with P	p. 71
Introduction	p. 71
Comparing the dual problems I* and <$$$>	p. 72
A dual comparison of P and <$$$>	p. 73
Proofs	p. 77
Notes	p. 79
Duality
Duality and Gomory Relaxations	p. 83
Introduction	p. 83
Gomory relaxations	p. 84
Brion and Vergne's formula and Gomory relaxations	p. 86
The Knapsack Problem	p. 94
A dual of <$$$>	p. 96
Proofs	p. 99
Notes	p. 106
Barvinok's Counting Algorithm and Gomory Relaxations	p. 107
Introduction	p. 107
Solving <$$$> via Barvinok's counting algorithm	p. 108
The link with Gomory relaxations	p. 111
Notes	p. 112
A Discrete Farkas Lemma	p. 115
Introduction	p. 115
A discrete Farkas lemma	p. 116
A discrete theorem of the alternative	p. 125
The knapsack equation	p. 127
Notes	p. 129
The Integer Hull of a Convex Rational Polytope	p. 131
Introduction	p. 131
The integer hull	p. 132
Notes	p. 137
Duality and Superadditive Functions	p. 139
Introduction	p. 139
Preliminaries	p. 140
Duality and superadditivity	p. 142
Notes	p. 147
Legendre-Fenchel, Laplace, Cramer, and <$$$> Transforms	p. 149
The Legendre-Fenchel transform	p. 149
Laplace transform	p. 151
The <$$$>-transform	p. 155
Notes	p. 157
References	p. 159
Glossary	p. 165
Index	p. 167
Table of Contents provided by Ingram. All Rights Reserved.