Combinatorial optimization has its roots in combinatorics, operations research,

and theoretical computer science. A main motivation is that thousands of real-life

problems can be formulated as abstract combinatorial optimization problems. We

focus on the detailed study of classical problems which occur in many different

contexts, together with the underlying theory.

Most combinatorial optimization problems can be formulated naturally in terms

of graphs and as (integer) linear programs. Therefore this book starts, after an

introduction, by reviewing basic graph theory and proving those results in linear

and integer programming which are most relevant for combinatorial optimization.

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Running Time of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Linear Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 Trees, Circuits, and Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.4 Eulerian and Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.5 Planarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.6 Planar Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.1 Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.2 The Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.3 Implementation of the Simplex Algorithm . . . . . . . . . . . . . . . . . . . . 57

3.4 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.5 Convex Hulls and Polytopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4 Linear Programming Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.1 Size of Vertices and Faces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.2 Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.3 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.4 The Ellipsoid Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4.5 Khachiyan’s Theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.6 Separation and Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

5 Integer Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

5.1 The Integer Hull of a Polyhedron . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

5.2 Unimodular Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

5.3 Total Dual Integrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5.4 Totally Unimodular Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5.5 Cutting Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

5.6 Lagrangean Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

6 Spanning Trees and Arborescences . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

6.1 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

6.2 Minimum Weight Arborescences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

6.3 Polyhedral Descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

6.4 Packing Spanning Trees and Arborescences . . . . . . . . . . . . . . . . . . . 140

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

7 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

7.1 Shortest Paths From One Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

7.2 Shortest Paths Between All Pairs of Vertices . . . . . . . . . . . . . . . . . . 156

7.3 Minimum Mean Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

8 Network Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

8.1 Max-Flow-Min-Cut Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

8.2 Menger’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

8.3 The Edmonds-Karp Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

8.4 Blocking Flows and Fujishige’s Algorithm . . . . . . . . . . . . . . . . . . . . 174

8.5 The Goldberg-Tarjan Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

8.6 Gomory-Hu Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

8.7 The Minimum Capacity of a Cut in an Undirected Graph . . . . . . . 186

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

9 Minimum Cost Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

9.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

9.2 An Optimality Criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

9.3 Minimum Mean Cycle-Cancelling Algorithm . . . . . . . . . . . . . . . . . . 203

9.4 Successive Shortest Path Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 207

9.5 Orlin’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

9.6 The Network Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

9.7 Flows Over Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224