Compact Extended Linear Programming Models
Textbook © 2018
 |
Lancia, Giuseppe, Serafini, Paolo This book provides a handy, unified introduction to the theory of compact extended formulations of exponential-size integer linear programming (ILP) models. Compact extended formulations are equally powerful, but polynomial-sized, models whose solutions do not require the implementation of separation and pricing procedures. The book is written in a general, didactic form, first developing the background theoretical concepts (polyhedra, projections, linear and integer programming) and then delving into the various techniques for compact extended reformulations. The techniques are illustrated through a wealth of examples touching on many application areas, such as classical combinatorial optimization, network design, timetabling, scheduling, routing, computational biology and bioinformatics. |
The book is intended for graduate or PhD students – either as an advanced course on selected topics or within a more general course on ILP and mathematical programming – as well as for practitioners and software engineers in industry exploring techniques for developing optimization models for their specific problems.
Keywords: ILP, combinatorial optimization, branch-and-cut, compact extended formulations, max-cut, bin packing, cutting-stock, knapsack, Steiner-tree, routing-cost
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 International License and the GNU Free Documentation License (unversioned, with no invariant sections, front-cover texts, or back-cover texts).
