This textbook for students and practitioners presents a practical approach to decomposition techniques in optimization. It provides an appropriate blend of theoretical background and practical applications in engineering and science, which makes the book interesting for practitioners, as well as engineering, operations research and applied economics graduate and postgraduate students. "Decomposition Techniques in Mathematical Programming" is based on clarifying, illustrative and computational examples and applications from electrical, mechanical, energy and civil engineering as well as applied mathematics and economics. It addresses decomposition in linear programming, mixed-integer linear programming, nonlinear programming, and mixed-integer nonlinear programming, and provides rigorous decomposition algorithms as well as heuristic ones. Practical applications are developed up to working algorithms that can be readily used. The theoretical background of the book is deep enough to be of interest to applied mathematicians. It includes end of chapter exercises and the solutions of the even numbered exercises are included as an appendix.
Author(s): Antonio .J. Conejo Enrique Castillo Roberto Minguez Raquel Garcia-Bertrand
Edition: 1
Year: 2006
Language: English
Pages: 557
3540276858......Page 1
Contents......Page 9
Part I: Motivation and Introduction......Page 15
1.1 Motivation......Page 16
1.2 Introduction......Page 20
1.3 Linear Programming: Complicating Constraints......Page 21
1.4 Linear Programming: Complicating Variables......Page 41
1.5 Nonlinear Programming: Complicating Constraints......Page 52
1.6 Nonlinear Programming: Complicating Variables......Page 66
1.7 Mixed-Integer Programming: Complicating Constraints......Page 68
1.8 Mixed-Integer Programming: Complicating Variables......Page 70
1.9 Concluding Remarks......Page 74
1.10 Exercises......Page 75
Part II: Decomposition Techniques......Page 78
2.1 Introduction......Page 79
2.2 Complicating Constraints: Problem Structure......Page 82
2.3 Decomposition......Page 85
2.4 The Dantzig-Wolfe Decomposition Algorithm......Page 89
2.5 Concluding Remarks......Page 111
2.6 Exercises......Page 112
3.1 Introduction......Page 119
3.2 Complicating Variables: Problem Structure......Page 122
3.3 Benders Decomposition......Page 123
3.4 Concluding Remarks......Page 147
3.5 Exercises......Page 148
4.1 Introduction......Page 152
4.2 Karush–Kuhn–Tucker First- and Second-Order Optimality Conditions......Page 153
4.3 Duality in Linear Programming......Page 160
4.4 Duality in Nonlinear Programming......Page 172
4.5 Illustration of Duality and Separability......Page 187
4.7 Exercises......Page 192
5.3 Lagrangian Relaxation......Page 197
5.4 Augmented Lagrangian Decomposition......Page 215
5.5 Optimality Condition Decomposition (OCD)......Page 220
5.6 Complicating Variables......Page 233
5.7 From Lagrangian Relaxation to Dantzig-Wolfe Decomposition......Page 243
5.8 Concluding Remarks......Page 248
5.9 Exercises......Page 249
6.1 Introduction......Page 253
6.2 Mixed-Integer Linear Programming......Page 254
6.4 Complicating Variables: Nonlinear Case......Page 261
6.5 Complicating Constraints: Nonlinear Case......Page 267
6.7 Exercises......Page 274
7.1 Bilevel Decomposition......Page 281
7.2 Bilevel Programming......Page 290
7.3 Equilibrium Problems......Page 292
7.4 Coordinate Descent Decomposition......Page 295
7.5 Exercises......Page 307
Part III: Local Sensitivity Analysis......Page 310
8.1 Introduction......Page 311
8.2 Statement of the Problem......Page 312
8.3 Sensitivities Based on Duality Theory......Page 313
8.4 A General Method for Obtaining All Sensitivities......Page 323
8.5 Particular Cases......Page 329
8.6 Sensitivities of Active Constraints......Page 347
8.7 Exercises......Page 349
Part IV: Applications......Page 355
9.1 The Wall Design......Page 356
9.2 The Bridge Crane Design......Page 368
9.3 Network Constrained Unit Commitment......Page 375
9.4 Production Costing......Page 381
9.5 Hydrothermal Coordination......Page 388
9.6 Multiarea Optimal Power Flow......Page 392
9.7 Sensitivity in Regression Models......Page 396
Part V: Computer Codes......Page 401
A.1 Dantzig-Wolfe Algorithm......Page 402
A.2 Benders Decomposition Algorithm......Page 408
A.3 GAMS Code for the Rubblemound Breakwater Example......Page 412
A.4 GAMS Code for the Wall Problem......Page 415
Part VI: Solution to Selected Exercises......Page 423
B.1 Exercises from Chapter 1......Page 424
B.2 Exercises from Chapter 2......Page 429
B.3 Exercises from Chapter 3......Page 438
B.4 Exercises from Chapter 4......Page 444
B.5 Exercises from Chapter 5......Page 454
B.6 Exercises from Chapter 6......Page 478
B.7 Exercises from Chapter 7......Page 503
B.8 Exercises from Chapter 8......Page 509
References......Page 533
B......Page 538
D......Page 539
M......Page 540
R......Page 541
W......Page 542
