Integer Programming

by Wolsey, Laurence A.

• ISBN13: 9780471283669
• ISBN10: 0471283665
• Edition: 1st
• Format: Hardcover
• Copyright: 1998-09-23
• Publisher: Wiley-Interscience

Summary

A practical, accessible guide to optimization problems with discrete or integer variables Integer Programming stands out from other textbooks by explaining in clear and simple terms how to construct custom-made algorithms or use existing commercial software to obtain optimal or near-optimal solutions for a variety of real-world problems, such as airline timetables, production line schedules, or electricity production on a regional or national scale. Incorporating recent developments that have made it possible to solve difficult optimization problems with greater accuracy, author Laurence A. Wolsey presents a number of state-of-the-art topics not covered in any other textbook. These include improved modeling, cutting plane theory and algorithms, heuristic methods, and branch-and-cut and integer programming decomposition algorithms. This self-contained text: * Distinguishes between good and bad formulations in integer programming problems * Applies lessons learned from easy integer programs to more difficult problems * Demonstrates with applications theoretical and practical aspects of problem solving * Includes useful notes and end-of-chapter exercises * Offers tremendous flexibility for tailoring material to different needs Integer Programming is an ideal text for courses in integer/mathematical programming-whether in operations research, mathematics, engineering, or computer science departments. It is also a valuable reference for industrial users of integer programming and researchers who would like to keep up with advances in the field.

Author Biography

LAURENCE A. WOLSEY is Professor of Applied Mathematics at the Center for Operations Research and Econometrics (CORE) at l'UniversitT Catholique de Louvain at Louvain-la-Neuve, Belgium. He is the author, with George Nemhauser, of Integer and Combinatorial Optimization (Wiley).

Table of Contents

Preface	xiii	(4)
Abbreviations and Notation	xvii
1 Formulations	1	(22)
1.1 Introduction	1	(2)
1.2 What Is an Integer Program?	3	(2)
1.3 Formulating IPs and BIPs	5	(3)
1.4 The Combinatorial Explosion	8	(1)
1.5 Mixed Integer Formulations	9	(3)
1.6 Alternative Formulations	12	(2)
1.7 Good and Ideal Formulations	14	(4)
1.8 Notes	18	(1)
1.9 Exercises	19	(4)
2 Optimality, Relaxation, and Bounds	23	(14)
2.1 Optimality and Relaxation	23	(2)
2.2 Linear Programming Relaxations	25	(1)
2.3 Combinatorial Relaxations	26	(1)
2.4 Lagrangian Relaxation	27	(1)
2.5 Duality	28	(2)
2.6 Primal Bounds: Greedy and Local Search	30	(3)
2.7 Notes	33	(1)
2.8 Exercises	33	(4)
3 Well-Solved Problems	37	(16)
3.1 Properties of Easy Problems	37	(1)
3.2 IPs with Totally Unimodular Matrices	38	(2)
3.3 Minimum Cost Network Flows	40	(2)
3.4 Special Minimum Cost Flows	42	(1)
3.4.1 Shortest Path	42	(1)
3.4.2 Maximum s - t Flow	43	(1)
3.5 Optimal Trees	43	(3)
3.6 Submodularity and Matroids*	46	(3)
3.7 Notes	49	(1)
3.8 Exercises	50	(3)
4 Matchings and Assignments	53	(14)
4.1 Augmenting Paths and Optimality	53	(2)
4.2 Bipartite Maximum Cardinality Matching	55	(2)
4.3 The Assignment Problem	57	(5)
4.4 Notes	62	(1)
4.5 Exercises	63	(4)
5 Dynamic Programming	67	(14)
5.1 Some Motivation: Shortest Paths	67	(1)
5.2 Uncapacitated Lot-Sizing	68	(3)
5.3 An Optimal Subtree of a Tree	71	(1)
5.4 Knapsack Problems	72	(5)
5.4.1 0-1 Knapsack	73	(1)
5.4.2 Integer Knapsack Problems	74	(3)
5.5 Notes	77	(1)
5.6 Exercises	78	(3)
6 Complexity and Problem Reductions	81	(10)
6.1 Complexity	81	(1)
6.2 Decision Problems, and Classes NP and P	82	(2)
6.3 Polynomial Reduction and the Class NPC	84	(3)
6.4 Consequences of P = NP or P (is not equal to) NP	87	(1)
6.5 Optimization and Separation	88	(1)
6.6 Notes	89	(1)
6.7 Exercises	89	(2)
7 Branch and Bound	91	(22)
7.1 Divide and Conquer	91	(1)
7.2 Implicit Enumeration	92	(3)
7.3 Branch and Bound: An Example	95	(3)
7.4 LP-based Branch and Bound	98	(3)
7.5 Using a Branch-and-Bound System	101	(2)
7.5.1 If All Else Fails	103	(1)
7.6 Preprocessing*	103	(4)
7.7 Notes	107	(1)
7.8 Exercises	108	(5)
8 Cutting Plane Algorithms	113	(26)
8.1 Introduction	113	(1)
8.2 Some Simple Valid Inequalities	114	(3)
8.3 Valid Inequalities	117	(4)
8.3.1 Valid Inequalities for Linear Programs	117	(1)
8.3.2 Valid Inequalities for Integer Programs	118	(3)
8.4 A Priori Addition of Constraints	121	(2)
8.5 Automatic Reformulation or Cutting Plane Algorithms	123	(1)
8.6 Gomory's Fractional Cutting Plane Algorithm	124	(3)
8.7 Mixed Integer Cuts	127	(3)
8.7.1 The Basic Mixed Integer Inequality	127	(2)
8.7.2 The Mixed Integer Rounding (MIR) Inequality	129	(1)
8.7.3 The Gomory Mixed Integer Cut*	129	(1)
8.8 Disjunctive Inequalities*	130	(3)
8.9 Notes	133	(1)
8.10 Exercises	134	(5)
9 Strong Valid Inequalities	139	(28)
9.1 Introduction	139	(1)
9.2 Strong Inequalities	140	(7)
9.2.1 Dominance	140	(2)
9.2.2 Polyhedra, Faces, and Facets	142	(2)
9.2.3 Facet and Convex Hull Proofs*	144	(3)
9.3 0-1 Knapsack Inequalities	147	(4)
9.3.1 Cover Inequalities	147	(1)
9.3.2 Strengthening Cover Inequalities	148	(2)
9.3.3 Separation for Cover Inequalities	150	(1)
9.4 Mixed 0-1 Inequalities	151	(3)
9.4.1 Flow Cover Inequalities	151	(2)
9.4.2 Separation for Flow Cover Inequalities	153	(1)
9.5 The Optimal Subtour Problem	154	(3)
9.5.1 Separation for Generalized Subtour Constraints	155	(2)
9.6 Branch-and-Cut	157	(3)
9.7 Notes	160	(1)
9.8 Exercises	161	(6)
10 Lagrangian Duality	167	(18)
10.1 Lagrangian Relaxation	167	(5)
10.2 The Strength of the Lagrangian Dual	172	(1)
10.3 Solving the Lagrangian Dual	173	(4)
10.4 Lagrangian Heuristics and Variable Fixing	177	(2)
10.5 Choosing a Lagrangian Dual	179	(1)
10.6 Notes	180	(1)
10.7 Exercises	181	(4)
11 Column Generation Algorithms	185	(18)
11.1 Introduction	185	(2)
11.2 Dantzig-Wolfe Reformulation of an IP	187	(1)
11.3 Solving the Master Linear Program	188	(5)
11.3.1 STSP by Column Generation	190	(2)
11.3.2 Strength of the Linear Programming Master	192	(1)
11.4 IP Column Generation for 0-1 IP	193	(1)
11.5 Implicit Partitioning/Packing Problems	194	(2)
11.6 Partitioning with Identical Subsets*	196	(4)
11.7 Notes	200	(1)
11.8 Exercises	201	(2)
12 Heuristic Algorithms	203	(18)
12.1 Introduction	203	(1)
12.2 Greedy and Local Search Revisited	204	(3)
12.3 Improved Local Search Heuristics	207	(4)
12.3.1 Tabu Search	207	(1)
12.3.2 Simulated Annealing	208	(2)
12.3.3 Genetic Algorithms	210	(1)
12.4 Worst-Case Analysis of Heuristics	211	(3)
12.5 MIP-based Heuristics	214	(3)
12.6 Notes	217	(1)
12.7 Exercises	218	(3)
13 From Theory to Solutions	221	(24)
13.1 Introduction	221	(1)
13.2 Software for Solving Integer Programs	221	(2)
13.3 How Do We Find an Improved Formulation?	223	(6)
13.3.1 Uncapacitated Lot-Sizing	223	(4)
13.3.2 Capacitated Lot-Sizing	227	(2)
13.4 Fixed Charge Networks: Reformulations	229	(3)
13.4.1 The Single Source Fixed Charge Network Flow Problem	229	(2)
13.4.2 The Directed Subtree Problem	231	(1)
13.5 Multi-Item Single Machine Lot-Sizing	232	(4)
13.6 A Multiplexer Assignment Problem	236	(4)
13.7 Notes	240	(1)
13.8 Exercises	241	(4)
References	245	(16)
Index	261