A Gentle Introduction to Optimization

Half Title Page......Page 2
Title Page......Page 4
Copyright......Page 5
Contents......Page 7
Preface......Page 12
1 Introduction......Page 16
1.1 A first example......Page 17
1.1.1 The formulation......Page 18
1.1.2 Correctness......Page 20
1.2 Linear programs......Page 22
1.2.1 Multiperiod models......Page 24
1.3 Integer programs......Page 35
1.3.1 Assignment problem......Page 36
1.3.2 Knapsack problem......Page 39
1.4.1 Shortest path problem......Page 52
1.4.2 Minimum cost perfect matching......Page 55
1.5.1 Minimum cost perfect matching......Page 57
1.5.2 Shortest path problem......Page 60
1.6.1 Pricing a tech gadget......Page 67
1.6.2 Finding a closest point feasible in an LP......Page 70
1.6.3 Finding a “central” feasible solution of an LP......Page 71
1.8 Further reading and notes......Page 75
2.1 Possible outcomes......Page 78
2.1.1 Infeasible linear programs......Page 79
2.1.2 Unbounded linear programs......Page 82
2.1.3 Linear programs with optimal solutions......Page 84
2.2 Standard equality form......Page 87
2.3 A simplex iteration......Page 93
2.4.1 Bases......Page 96
2.4.2 Canonical forms......Page 98
2.5.1 An example with an optimal solution......Page 107
2.5.2 An unbounded example......Page 111
2.5.3 Formalizing the procedure......Page 113
2.6 Finding feasible solutions......Page 123
2.6.1 General scheme......Page 124
2.6.2 The two phase simplex algorithm–an example......Page 128
2.6.3 Consequences......Page 130
2.7.1 Pivoting......Page 133
2.7.2 Tableaus......Page 135
2.8.1 Feasible region of LPs and polyhedra......Page 138
2.8.2 Convexity......Page 141
2.8.3 Extreme points......Page 143
2.8.4 Geometric interpretation of the simplex algorithm......Page 147
2.9 Further reading and notes......Page 155
3.1 The shortest path problem......Page 157
3.1.1 An intuitive lower bound......Page 159
3.1.2 A general argument – weak duality......Page 163
3.1.3 Revisiting the intuitive lower bound......Page 168
3.1.4 An algorithm......Page 175
3.1.5 Correctness of the algorithm......Page 180
3.2 Minimum cost perfect matching in bipartite graphs......Page 184
3.2.1 An intuitive lower bound......Page 185
3.2.2 A general argument–weak duality......Page 187
3.2.3 Revisiting the intuitive lower bound......Page 191
3.2.4 An algorithm......Page 196
3.2.5 Correctness of the algorithm......Page 202
3.2.6 Finding perfect matchings in bipartite graphs*......Page 207
3.3 Further reading and notes......Page 218
4.1 Weak duality......Page 219
4.2 Strong duality......Page 231
4.3 A geometric characterization of optimality......Page 235
4.3.1 Complementary slackness......Page 236
4.3.2 Geometry......Page 242
4.4 Farkas’ lemma*......Page 248
4.5 Further reading and notes......Page 252
5.1 Approximation algorithm for set-cover......Page 253
5.1.1 A primal–dual algorithm......Page 255
5.1.2 Greed is good ... at least sometimes......Page 259
5.1.3 Discussion......Page 263
5.2 Economic interpretation......Page 264
5.3 The maximum-flow–minimum-cut theorem......Page 268
5.3.1 Totally unimodular matrices......Page 271
5.3.2 Applications to st-flows......Page 273
6 Solving integer programs......Page 279
6.1 Integer programs versus linear programs......Page 280
6.2 Cutting planes......Page 287
6.2.1 Cutting planes and the simplex algorithm......Page 290
6.3 Branch and bound......Page 297
6.4 Traveling salesman problem and a separation algorithm*......Page 305
6.5 Further reading and notes......Page 310
7.1 Some examples......Page 312
7.2.1 NLP versus 0,1 integer programming......Page 315
7.2.2 Hard small-dimensional instances......Page 316
7.3 Convexity......Page 317
7.3.1 Convex functions and epigraphs......Page 318
7.3.2 Level sets and feasible region......Page 322
7.4 Relaxing convex NLPs......Page 325
7.4.1 Subgradients......Page 326
7.4.2 Supporting halfspaces......Page 327
7.5.1 Sufficient conditions for optimality......Page 330
7.5.2 Differentiability and gradients......Page 332
7.5.3 A Karush–Kuhn–Tucker theorem......Page 333
7.6 Optimality conditions based on Lagrangians......Page 336
7.7 Nonconvex optimization problems......Page 341
7.7.1 The Karush–Kuhn–Tucker theorem for nonconvex problems[sup(⋆)]......Page 342
7.7.2 Convex relaxation approach to nonconvex problems*......Page 345
7.8 Interior-point method for linear programs*......Page 352
7.8.1 A polynomial-time interior-point algorithm*......Page 358
7.9 Further reading and notes......Page 362
A.1 What is a fast (resp. slow) algorithm?......Page 365
A.1.1 The big “O” notation......Page 366
A.1.2 Input size and running time......Page 367
A.1.3 Polynomial and exponential algorithms......Page 369
A.2.1 Linear programming......Page 372
A.2.2 Other algorithms in this book......Page 375
A.3.1 Decision problems......Page 376
A.3.2 The class NP......Page 378
A.3.3 The class co-NP......Page 380
A.3.4 The class P......Page 382
A.4 Hard problems......Page 384
A.4.1 Reducibility......Page 385
A.4.2 NP-complete problems......Page 387
A.4.3 Complexity as guide......Page 388
A.4.4 Easy versus hard problems......Page 389
References......Page 392
Index......Page 397