About This Course

This book is about optimization problems in which some or all of the decisions are whole numbers: which arcs a route uses, which worker takes which job, how many pallets of each kind go on an aircraft, which items go into a knapsack. It is written for a reader working alone, an advanced undergraduate or beginning graduate student in mathematics, operations research, computer science, or engineering, who wants to be able to run each algorithm by hand on a small instance, prove that it is correct, and say what evidence accompanies its answer.

Three courses are assumed. From Discrete Mathematics you need graphs, paths, cycles, trees, counting, and proof by induction. From Linear Algebra you need linear systems, determinants, and inverse matrices. From Continuous Optimization you need linear programming: feasible regions, vertices and basic feasible solutions, the simplex method, and duality with complementary slackness. Those results are used here constantly and are not proved again; when one is needed it is stated with the hypotheses the argument uses and marked once with its library identifier. A little dynamic programming is used in Chapters 2 and 9, and its general theory belongs to Dynamic Programming and Optimal Control.

The ten chapters aim at a short list of things you can do afterwards with pencil, paper, and no reference at hand. Formulate a combinatorial decision as an integer program and compare two formulations by the bounds they give. Run Dijkstra’s algorithm, the Bellman–Ford recursion, augmenting-path algorithms for maximum flow and bipartite matching, the Hungarian method, branch-and-bound, Gomory and cover cuts, and the knapsack recursions on small instances, and explain every number produced. Prove the max-flow min-cut theorem, König’s theorem, and the integrality of polyhedra with totally unimodular constraint matrices. Recognize when a linear programming relaxation solves an integer problem exactly and when it cannot. Bound the error of a heuristic by an approximation ratio or a dual bound. Choose among these tools for a new problem and state what certificate the chosen method delivers.

Notation is standard. A directed graph is \(G=(V,A)\) with \(n=\lvert V\rvert\) nodes and \(m=\lvert A\rvert\) arcs; an arc from \(v\) to \(w\) is written \((v,w)\) . Arc costs or lengths are \(c_{vw}\) and arc capacities are \(u_{vw}\) , so the letter \(u\) is never used for a node. For a set \(S\) of nodes, \(\delta^+(S)\) is the set of arcs leaving \(S\) and \(\delta^-(S)\) the set of arcs entering it. The integers are \(\mathbb Z\) and the nonnegative integers \(\mathbb Z_+\) . Inequalities between vectors hold componentwise, \(\mathbf 1\) is a vector of ones, and for a vector \(x\) indexed by a set \(E\) and a subset \(F\subseteq E\) we write \(x(F)=\sum_{e\in F}x_e\) . The floor \(\lfloor a\rfloor\) is the largest integer not exceeding \(a\) , and \(\lceil a\rceil\) is the smallest integer not below it. Integer programs are written as maximization problems unless a chapter says otherwise; \(z^\star\) is the optimal value of the integer problem and \(z_{LP}\) the optimal value of its linear programming relaxation.

Each chapter ends with exercises that run from recall and hand computation to proof. Work the computational ones on paper first; the instances are small enough that every algorithm in the book can be traced by hand, and that tracing is where the algorithms are learned. The companion solutions give full arguments for some exercises, hints for others, and bare answers for a few. Several exercises present a plausible but wrong argument and ask for the flaw. The cumulative review at the end mixes the chapters without naming them, because in practice the first decision is which structure a problem has.