×

Linear and integer programming vs linear integration and counting. A duality viewpoint. (English) Zbl 1188.90170

Springer Series in Operations Research and Financial Engineering. New York, NY: Springer (ISBN 978-0-387-09413-7/hbk; 978-0-387-09414-4/ebook). xiii, 168 p. (2009).
In the present book, the author analyzes and compares four related problems: linear programming, integer programming, linear integration and linear counting. The author emphasises duality aspects concerning the above mentioned problems, which with the exception of linear programming are not well developed.
The book is structured on three main parts:
Part I: Linear integration and linear programming. In this part there are presented the linear integration problem and the linear programming problem and there are established comparisons between them from a duality point of view.
Part II: Linear counting and integer programming. Within this part of the book, the author describes the linear counting problem and establishes comparisons with linear programming. There are presented: a primal approach, Barvinok’s counting algorithm, a dual approach, the Brion and Vergne’s discrete formula. As well there are presented the relations between the discrete analogues of integration problem and linear programming with linear programming.
Part III: Duality. The last part of the book is concerned with duality results for the integer programming problem. The old algebraic concepts of Gomory relaxations are related with the results of the previous chapters. The author describes as well two integer programming algorithms based on Barvinok’s counting algorithm and links between the Barvinok’s counting algorithm and the Gomory relaxations. In the last part a discrete version of the Farkas lemma in linear algebra is presented.

MSC:

90C05 Linear programming
90C10 Integer programming
90C46 Optimality conditions and duality in mathematical programming

Software:

LattE
PDFBibTeX XMLCite
Full Text: DOI