Mathematics of Operational Research
Contents
Table of Contents i
Schedules v
1 Lagrangian Methods 1
1.1 Lagrangian methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The Lagrange dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Supporting hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Convex and Linear Optimization 6
2.1 Convexity and strong duality . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Linear programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Linear program duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Complementary slackness . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 Shadow prices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 The Simplex Algorithm 11
3.1 Basic solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Extreme points and optimal solutions . . . . . . . . . . . . . . . . . . . 12
3.3 The simplex tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 The simplex method in tableau form . . . . . . . . . . . . . . . . . . . . 14
3.5 Degeneracies and cycling . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Advanced Simplex Procedures 17
4.1 The two-phase simplex method . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 The dual simplex method . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Gomory’s cutting plane method . . . . . . . . . . . . . . . . . . . . . . . 20
5 Complexity of Algorithms 22
5.1 Theory of algorithmic complexity . . . . . . . . . . . . . . . . . . . . . . 22
5.2 P, NP, and polynomial-time reductions . . . . . . . . . . . . . . . . . . . 22
5.3 Some NP-complete problems . . . . . . . . . . . . . . . . . . . . . . . . 24
6 Computational Complexity of LP 26
6.1 A lower bound for the simplex method . . . . . . . . . . . . . . . . . . . 26
6.2 The idea for a new method . . . . . . . . . . . . . . . . . . . . . . . . . 27
7 Ellipsoid Method 30
7.1 Ellipsoid method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
i
, 7.2 Proof of correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.3 The running time of the ellipsoid method . . . . . . . . . . . . . . . . . 33
8 Optimization in Networks 34
8.1 Graph terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.2 Minimum cost flow problem . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.3 Spanning tree solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.4 The network simplex method . . . . . . . . . . . . . . . . . . . . . . . . 36
8.5 Integrality of optimal solutions . . . . . . . . . . . . . . . . . . . . . . . 38
8.6 Longest path problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
9 Transportation and Assignment Problems 40
9.1 Transportation problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
9.2 Network simplex method in tableau form . . . . . . . . . . . . . . . . . 41
9.3 Assignment problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
10 Maximum Flows and Perfect Matchings 44
10.1 Maximum flow problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10.2 Max-flow min-cut theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10.3 The Ford-Fulkerson algorithm . . . . . . . . . . . . . . . . . . . . . . . . 45
10.4 Applications of the max-flow min-cut theorem . . . . . . . . . . . . . . . 46
10.5 A polynomial-time algorithm for the assignment problem . . . . . . . . 48
11 Shortest Paths and Minimum Spanning Trees 50
11.1 Bellman’s equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
11.2 Bellman-Ford algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
11.3 Dijkstra’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
11.4 Minimal spanning tree problem . . . . . . . . . . . . . . . . . . . . . . . 53
12 Semidefinite Programming 54
12.1 Primal-dual interior-point methods . . . . . . . . . . . . . . . . . . . . . 54
12.2 Semidefinite programming problem . . . . . . . . . . . . . . . . . . . . . 54
12.3 Max-cut problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
12.4 Symmetric rendezvous search game . . . . . . . . . . . . . . . . . . . . . 57
13 Branch and Bound 59
13.1 Knapsack problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
13.2 Branch and bound technique . . . . . . . . . . . . . . . . . . . . . . . . 60
13.3 Dakin’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
14 Heuristic Algorithms 63
14.1 The travelling salesman problem . . . . . . . . . . . . . . . . . . . . . . 63
14.2 Heuristic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
14.3 Heuristics for the TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
14.4 Local search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
ii
, 14.5 Simulated annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
15 Non-cooperative Games 68
15.1 Games and solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
15.2 Minimax theorem for zero-sum games . . . . . . . . . . . . . . . . . . . 70
15.3 Equilibria of matrix games . . . . . . . . . . . . . . . . . . . . . . . . . . 71
16 Solution of Two-person Games 73
16.1 Nash’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
16.2 The complexity of finding an equilibrium . . . . . . . . . . . . . . . . . . 74
16.3 Symmetric games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
16.4 Lemke-Howson algorithm for a symmetric game . . . . . . . . . . . . . . 75
17 Linear complimentarity problem 78
17.1 Linear complementarity problem . . . . . . . . . . . . . . . . . . . . . . 78
17.2 Quadratic programming as a LCP . . . . . . . . . . . . . . . . . . . . . 78
17.3 Knapsack as a LCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
17.4 Lemke’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
17.5 Complementary pivoting . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
17.6 Sperner’s lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
18 Cooperative Games 83
18.1 Coalitional games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
18.2 The core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
18.3 The nucleolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
18.4 Nucleolus in terms of objections . . . . . . . . . . . . . . . . . . . . . . . 86
19 Bargaining problems 87
19.1 The Shapley value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
19.2 Shapley value in terms of objections . . . . . . . . . . . . . . . . . . . . 87
19.3 Bargaining theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
19.4 Nash’s bargaining solution . . . . . . . . . . . . . . . . . . . . . . . . . . 88
20 Social Choice 92
20.1 Social welfare functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
20.2 Social choice functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
20.3 Strategic manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
20.4 Alternative proof of Gibbard-Satterthwaithe theorem . . . . . . . . . . . 96
21 Auctions 99
21.1 Types of auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
21.2 The revenue equivalence theorem . . . . . . . . . . . . . . . . . . . . . . 100
21.3 Mechanism design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
22 Optimal Auctions 104
iii
, 22.1 Revelation principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
22.2 Vickrey-Clark-Groves mechanisms . . . . . . . . . . . . . . . . . . . . . 104
22.3 Optimal auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
22.4 Heterogenous bidders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
23 Mechanism Design for a Shared Facility 109
23.1 Paying for a club good . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
23.2 Ex-post budget balance . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
23.3 Refining a mechanism design . . . . . . . . . . . . . . . . . . . . . . . . 112
Index 114
Richard Weber, Michaelmas Term 2015
Last updated on March 15, 2016.
iv
Contents
Table of Contents i
Schedules v
1 Lagrangian Methods 1
1.1 Lagrangian methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The Lagrange dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Supporting hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Convex and Linear Optimization 6
2.1 Convexity and strong duality . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Linear programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Linear program duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Complementary slackness . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 Shadow prices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 The Simplex Algorithm 11
3.1 Basic solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Extreme points and optimal solutions . . . . . . . . . . . . . . . . . . . 12
3.3 The simplex tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 The simplex method in tableau form . . . . . . . . . . . . . . . . . . . . 14
3.5 Degeneracies and cycling . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Advanced Simplex Procedures 17
4.1 The two-phase simplex method . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 The dual simplex method . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Gomory’s cutting plane method . . . . . . . . . . . . . . . . . . . . . . . 20
5 Complexity of Algorithms 22
5.1 Theory of algorithmic complexity . . . . . . . . . . . . . . . . . . . . . . 22
5.2 P, NP, and polynomial-time reductions . . . . . . . . . . . . . . . . . . . 22
5.3 Some NP-complete problems . . . . . . . . . . . . . . . . . . . . . . . . 24
6 Computational Complexity of LP 26
6.1 A lower bound for the simplex method . . . . . . . . . . . . . . . . . . . 26
6.2 The idea for a new method . . . . . . . . . . . . . . . . . . . . . . . . . 27
7 Ellipsoid Method 30
7.1 Ellipsoid method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
i
, 7.2 Proof of correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.3 The running time of the ellipsoid method . . . . . . . . . . . . . . . . . 33
8 Optimization in Networks 34
8.1 Graph terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.2 Minimum cost flow problem . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.3 Spanning tree solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.4 The network simplex method . . . . . . . . . . . . . . . . . . . . . . . . 36
8.5 Integrality of optimal solutions . . . . . . . . . . . . . . . . . . . . . . . 38
8.6 Longest path problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
9 Transportation and Assignment Problems 40
9.1 Transportation problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
9.2 Network simplex method in tableau form . . . . . . . . . . . . . . . . . 41
9.3 Assignment problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
10 Maximum Flows and Perfect Matchings 44
10.1 Maximum flow problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10.2 Max-flow min-cut theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10.3 The Ford-Fulkerson algorithm . . . . . . . . . . . . . . . . . . . . . . . . 45
10.4 Applications of the max-flow min-cut theorem . . . . . . . . . . . . . . . 46
10.5 A polynomial-time algorithm for the assignment problem . . . . . . . . 48
11 Shortest Paths and Minimum Spanning Trees 50
11.1 Bellman’s equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
11.2 Bellman-Ford algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
11.3 Dijkstra’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
11.4 Minimal spanning tree problem . . . . . . . . . . . . . . . . . . . . . . . 53
12 Semidefinite Programming 54
12.1 Primal-dual interior-point methods . . . . . . . . . . . . . . . . . . . . . 54
12.2 Semidefinite programming problem . . . . . . . . . . . . . . . . . . . . . 54
12.3 Max-cut problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
12.4 Symmetric rendezvous search game . . . . . . . . . . . . . . . . . . . . . 57
13 Branch and Bound 59
13.1 Knapsack problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
13.2 Branch and bound technique . . . . . . . . . . . . . . . . . . . . . . . . 60
13.3 Dakin’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
14 Heuristic Algorithms 63
14.1 The travelling salesman problem . . . . . . . . . . . . . . . . . . . . . . 63
14.2 Heuristic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
14.3 Heuristics for the TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
14.4 Local search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
ii
, 14.5 Simulated annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
15 Non-cooperative Games 68
15.1 Games and solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
15.2 Minimax theorem for zero-sum games . . . . . . . . . . . . . . . . . . . 70
15.3 Equilibria of matrix games . . . . . . . . . . . . . . . . . . . . . . . . . . 71
16 Solution of Two-person Games 73
16.1 Nash’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
16.2 The complexity of finding an equilibrium . . . . . . . . . . . . . . . . . . 74
16.3 Symmetric games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
16.4 Lemke-Howson algorithm for a symmetric game . . . . . . . . . . . . . . 75
17 Linear complimentarity problem 78
17.1 Linear complementarity problem . . . . . . . . . . . . . . . . . . . . . . 78
17.2 Quadratic programming as a LCP . . . . . . . . . . . . . . . . . . . . . 78
17.3 Knapsack as a LCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
17.4 Lemke’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
17.5 Complementary pivoting . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
17.6 Sperner’s lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
18 Cooperative Games 83
18.1 Coalitional games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
18.2 The core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
18.3 The nucleolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
18.4 Nucleolus in terms of objections . . . . . . . . . . . . . . . . . . . . . . . 86
19 Bargaining problems 87
19.1 The Shapley value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
19.2 Shapley value in terms of objections . . . . . . . . . . . . . . . . . . . . 87
19.3 Bargaining theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
19.4 Nash’s bargaining solution . . . . . . . . . . . . . . . . . . . . . . . . . . 88
20 Social Choice 92
20.1 Social welfare functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
20.2 Social choice functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
20.3 Strategic manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
20.4 Alternative proof of Gibbard-Satterthwaithe theorem . . . . . . . . . . . 96
21 Auctions 99
21.1 Types of auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
21.2 The revenue equivalence theorem . . . . . . . . . . . . . . . . . . . . . . 100
21.3 Mechanism design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
22 Optimal Auctions 104
iii
, 22.1 Revelation principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
22.2 Vickrey-Clark-Groves mechanisms . . . . . . . . . . . . . . . . . . . . . 104
22.3 Optimal auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
22.4 Heterogenous bidders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
23 Mechanism Design for a Shared Facility 109
23.1 Paying for a club good . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
23.2 Ex-post budget balance . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
23.3 Refining a mechanism design . . . . . . . . . . . . . . . . . . . . . . . . 112
Index 114
Richard Weber, Michaelmas Term 2015
Last updated on March 15, 2016.
iv
