This advanced text/reference presents the mathematical foundations of integer and combinatorial optimization models and the algorithms that can be used to solve a variety of problems in resource allocation, location, distribution, scheduling and production. Chapters on polyhedral theory and model formulation with integer variables are included. Part 1 covers linear programming, graphs and networks and computational complexity. Part 2 covers integer programming, including duality, relaxation and strong cutting planes, and presents algorithms. Part 3 addresses combinatorial optimization, including 0-1 matrices, matching, and submodular function optimization. The book contains many examples and applications.
Table of Contents:
FOUNDATIONS: The Scope of Integer and Combinatorial Optimization; Linear Programming; Graphs and Networks; Polyhedral Theory; Computational Complexity; Polynomial-Time Algorithms for Linear Programming; Integer Lattices; GENERAL INTEGER PROGRAMMING: The Theory of Valid Inequalities; Strong Valid Inequalities and Facets for Structured Integer Programs; Duality and Relaxation; General Algorithms; Special Purpose Algorithms; Applications of Special Purpose Algorithms; COMBINATORIAL OPTIMIZATION: Integral Polyhedra; The Matching Problem; Matroid and Submodular Function Optimization; Notes; Exercises.