Preface xi
Part 1. Programmation 1
Chapter 1. Linear Programming 3
1.1. Introduction 3
1.2. Definitions 3
1.3. Geometry of the linear program 5
1.3.1. Polyhedra 5
1.3.2. Extreme points and vertices 6
1.4. Graphical solving of a linear program 6
1.5. Simplex algorithm 9
1.5.1. Basic solutions and basic feasible solutions 9
1.5.2. Simplex tableau 10
1.5.3. Change of feasible basis 11
1.5.4. Existence and uniqueness of an optimal solution 14
1.6. Initialization of the simplex algorithm 15
1.6.1. Big M method 15
1.6.2. Auxiliary program or Phase I 17
1.6.3. Degeneracy and cycling 20
1.6.4. Geometric structure of realizable solutions 21
1.7. Interior-point algorithm 22
1.8. Duality 23
1.8.1. Duality theorem 25
1.9. Relaxation 27
1.9.1. Lagrangian relaxation 27
1.10. Postoptimal analysis 29
1.10.1. Effect of modifying b 31
1.10.2. Effect of modifying c 32
1.11. Application to an inventory problem 34
1.11.1. Optimal solution 34
1.11.2. Sensitivity to variation in stock 35
1.11.3. Dual problem of the competitor 36
1.12. Using Matlab 36
Chapter 2. Integer Programming 41
2.1. Introduction 41
2.2. Solving methods 41
2.2.1. Branch-and-bound method 42
2.2.2. The branch-and-cut method 44
2.3. Binary programming 49
2.3.1. Knapsack problem 49
2.3.2. Investment problem 50
2.4. Decomposition principle 57
2.4.1. Benders decomposition 58
2.5. Using Matlab 62
Chapter 3. Dynamic Programming 65
3.1. Introduction 65
3.2. Solving strategy 66
3.3. Discrete DP 68
3.3.1. Bellmanâs equation and the principle of optimality 68
3.3.2. Approach of the method 70
3.3.3. A few examples of DP 70
3.3.4. Solving an LP 73
3.3.5. Shortest path problem 74
3.3.6. Knapsack problem 79
3.3.7. Stock management problem 81
3.4. Continuous DP 83
3.4.1. Hamiltonâ"Jacobi equation 84
3.4.2. Application to a consumption-savings model 84
3.5. Stochastic DP 85
3.5.1. Decision-chance process 85
3.5.2. Solving method 86
3.5.3. Application to a contract problem 86
3.5.4. Optimal binary search tree 87
3.6. Using Matlab 91
Chapter 4. Stochastic Programming 93
4.1. Introduction 93
4.2. Presentation of the problem 94
4.3. Optimal feedback in an open loop 94
4.4. Stochastic linear programming 95
4.4.1. Models with probability thresholds on the constraints 96
4.5. Stochastic linear programs with recourse 96
4.5.1. L-shaped method 97
4.5.2. Multicut L-shaped method 99
4.5.3. Interior linearization method 100
4.6. Nonlinear stochastic programming 100
4.6.1. Approaches to two-step problems with recourse 100
4.6.2. Regularized decomposition method 101
4.6.3. Methods based on the Lagrangian 101
4.6.4. Frankâ"Wolfe method for problems with simple recourse 103
4.6.5. Approximation by sampling average: Monte Carlo method 105
4.6.6. Stochastic gradient method 106
4.7. Stochastic dynamic programming 107
4.7.1. Markov decision process 108
4.7.2. Scenario tree 109
4.8. Application to the reliability of mechanical systems 111
4.8.1. Position and modeling of the reliability problem 113
4.9. Using Matlab 121
Part 2. Optimization 127
Chapter 5. Combinatorial Optimization 129
5.1. Introduction 129
5.2. Symmetric TSP 131
5.2.1. Historical overview 132
5.2.2. Solving methods 134
5.3. Asymmetric traveling salesman problem 140
5.3.1. Variants of the ATSP 140
5.3.2. Mathematical formulations 142
5.3.3. Methods for solving the ATSP 144
5.4. Vehicle routing problem 148
5.4.1. Definition 148
5.4.2. Fields of application 149
5.4.3. Parameters of the VRP 150
5.4.4. Variants of the VRP 151
5.4.5. Mathematical formulation of the VRP 153
5.4.6. Algorithmic complexity 155
5.5. Selective routing problem 156
5.5.1. Problems similar to the VRP 157
5.5.2. Mathematical formulation 157
5.6. Using Matlab 158
Chapter 6. Unconstrained Nonlinear Programming 161
6.1. Introduction 161
6.2. Mathematical formulation 161
6.2.1. Existence and uniqueness results 162
6.3. Optimality conditions 162
6.4. Quadratic problems 163
6.4.1. Gradient method with optimal step size 163
6.4.2. Conjugate gradient method 164
6.5. Newtonâs algorithm 164
6.6. Methods of descent and linear search 165
6.6.1. Presentation of methods of descent 165
6.6.2. Method of greatest slope 167
6.6.3. Acceptable step size 168
6.6.4. Linear search 169
6.6.5. Newtonâs method with linear search 170
6.7. Quasi-Newton methods 171
6.7.1. DFP and BFGS methods 172
6.8. Relaxation method 173
6.9. Gradient method 175
6.10. Least squares problem 176
6.10.1. Gaussâ"Newton method 176
6.10.2. Levenbergâ"Marquardt algorithm 178
6.10.3. Kalman filter 179
6.11. Direct search methods 181
6.11.1. Nelderâ"Mead algorithm 181
6.11.2. Torczon method 183
6.12. Application to an identification problem 183
6.13. Using Matlab 185
6.13.1. The fminsearch function 187
6.13.2. The fminunc function 188
6.13.3. Relaxation method 190
Chapter 7. Constrained Nonlinear Optimization 193
7.1. Introduction 193
7.2. Mathematical formulation 193
7.3. Lagrange multipliers 194
7.4. Optimization with inequality constraints 195
7.4.1. First-order conditions of optimality 195
7.4.2. Presentation of saddle points 197
7.4.3. Saddle point and optimization 198
7.4.4. Convex case 201
7.5. Constrained minimization algorithms 201
7.5.1. Relaxation method 202
7.5.2. Projection method 202
7.5.3. Exterior penalty method 204
7.5.4. Uzawaâs algorithm 205
7.6. Newton algorithms: SQP method 206
7.6.1. Equality constraints 207
7.6.2. Inequality constraints 209
7.7. Application to structure optimization 210
7.8. Using Matlab 217
7.8.1. The fmincon function 219
7.8.2. The fminbnd function 220
7.8.3. Penalty method 221
Appendices 229
Appendix 1. Reminders from Linear Algebra 231
Appendix 2. Reminders about functions from Rn into R 241
Appendix 3. Optimization Toolbox 245
Appendix 4. Software 249
References 253
Index 261
