VT Paschos
John Wiley & Sons
0e druk, 2010
9781848211476
Concepts of Combinatorial Optimization – Concepts and Fundamentals
Specificaties
Gebonden, 380 blz.
|
Engels
John Wiley & Sons |
0e druk, 2010
ISBN13: 9781848211476
Rubricering
Onderdeel van serie
ISTE
Levertijd ongeveer 15 werkdagen
Samenvatting
Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management.
The three volumes of the Combinatorial Optimization series aims to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization.
Concepts of Combinatorial Optimization, is divided into three parts:
On the complexity of combinatorial optimization problems, that presents basics about worst–case and randomized complexity;
Classical solution methods, that presents the two most–known methods for solving hard combinatorial optimization problems, that are Branch–and–Bound and Dynamic Programming;
Elements from mathematical programming, that presents fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this field.
Specificaties
ISBN13:9781848211476
Taal:Engels
Bindwijze:gebonden
Aantal pagina's:380
Uitgever:John Wiley & Sons
Druk:0
Serie:ISTE
Inhoudsopgave
<p>Preface xiii<br /> Vangelis Th. PASCHOS</p>
<p>PART I. COMPLEXITY OF COMBINATORIAL OPTIMIZATION PROBLEMS 1</p>
<p>Chapter 1. Basic Concepts in Algorithms and Complexity Theory 3<br /> Vangelis Th. PASCHOS</p>
<p>1.1. Algorithmic complexity 3</p>
<p>1.2. Problem complexity 4</p>
<p>1.3. The classes P, NP and NPO 7</p>
<p>1.4. Karp and Turing reductions 9</p>
<p>1.5. NP–completeness 10</p>
<p>1.6. Two examples of NP–complete problems 13</p>
<p>1.7. A few words on strong and weak NP–completeness 16</p>
<p>1.8. A few other well–known complexity classes 17</p>
<p>1.9. Bibliography 18</p>
<p>Chapter 2. Randomized Complexity 21<br /> Jérémy BARBAY</p>
<p>2.1. Deterministic and probabilistic algorithms 22</p>
<p>2.2. Lower bound technique 28</p>
<p>2.3. Elementary intersection problem 35</p>
<p>2.4. Conclusion 37</p>
<p>2.5 Bibliography 37</p>
<p>PART II. CLASSICAL SOLUTION METHODS 39</p>
<p>Chapter 3. Branch–and–Bound Methods 41<br /> Irène CHARON and Olivier HUDRY</p>
<p>3.1. Introduction 41</p>
<p>3.2. Branch–and–bound method principles 43</p>
<p>3.3. A detailed example: the binary knapsack problem 54</p>
<p>3.4. Conclusion 67</p>
<p>3.5. Bibliography 68</p>
<p>Chapter 4. Dynamic Programming 71<br /> Bruno ESCOFFIER and Olivier SPANJAARD</p>
<p>4.1. Introduction 71</p>
<p>4.2. A first example: crossing the bridge 72</p>
<p>4.3. Formalization 75</p>
<p>4.4. Some other examples 79</p>
<p>4.5. Solution 83</p>
<p>4.6. Solution of the examples 88</p>
<p>4.7. A few extensions 90</p>
<p>4.8. Conclusion 98</p>
<p>4.9. Bibliography 98</p>
<p>PART III. ELEMENTS FROM MATHEMATICAL PROGRAMMING 101</p>
<p>Chapter 5. Mixed Integer Linear Programming Models for Combinatorial Optimization Problems 103<br /> Frédérico DELLA CROCE</p>
<p>5.1. Introduction 103</p>
<p>5.2. General modeling techniques 111</p>
<p>5.3. More advanced MILP models 117</p>
<p>5.4. Conclusions 132</p>
<p>5.5. Bibliography 133</p>
<p>Chapter 6. Simplex Algorithms for Linear Programming 135<br /> Frédérico DELLA CROCE and Andrea GROSSO</p>
<p>6.1. Introduction 135</p>
<p>6.2. Primal and dual programs 135</p>
<p>6.3. The primal simplex method 140</p>
<p>6.4. Bland s rule 145</p>
<p>6.5. Simplex methods for the dual problem 147</p>
<p>6.6. Using reduced costs and pseudo–costs for integer programming 152</p>
<p>6.7. Bibliography 155</p>
<p>Chapter 7. A Survey of some Linear Programming Methods 157<br /> Pierre TOLLA</p>
<p>7.1. Introduction 157</p>
<p>7.2. Dantzig s simplex method 158</p>
<p>7.3. Duality 162</p>
<p>7.4. Khachiyan s algorithm 162</p>
<p>7.5. Interior methods 165</p>
<p>7.6. Conclusion 186</p>
<p>7.7. Bibliography 187</p>
<p>Chapter 8. Quadratic Optimization in 0 1 Variables 189<br /> Alain BILLIONNET</p>
<p>8.1. Introduction 189</p>
<p>8.2. Pseudo–Boolean functions and set functions 190</p>
<p>8.3. Formalization using pseudo–Boolean functions 191</p>
<p>8.4. Quadratic pseudo–Boolean functions (qpBf) 192</p>
<p>8.5. Integer optimum and continuous optimum of qpBfs 194</p>
<p>8.6. Derandomization 195</p>
<p>8.7. Posiforms and quadratic posiforms 196</p>
<p>8.8. Optimizing a qpBf: special cases and polynomial cases 198</p>
<p>8.9. Reductions, relaxations, linearizations, bound calculation and persistence 200</p>
<p>8.10. Local optimum 206</p>
<p>8.11. Exact algorithms and heuristic methods for optimizing qpBfs 208</p>
<p>8.12. Approximation algorithms 211</p>
<p>8.13. Optimizing a quadratic pseudo–Boolean function with linear constraints 213</p>
<p>8.14. Linearization, convexification and Lagrangian relaxation for optimizing a qpBf with linear constraints 220</p>
<p>8.15. –Approximation algorithms for optimizing a qpBf with linear constraints 223</p>
<p>8.16. Bibliography 224</p>
<p>Chapter 9. Column Generation in Integer Linear Programming 235<br /> Irène LOISEAU, Alberto CESELLI, Nelson MACULAN and Matteo SALANI</p>
<p>9.1. Introduction 235</p>
<p>9.2. A column generation method for a bounded variable linear programming problem 236</p>
<p>9.3. An inequality to eliminate the generation of a 0 1 column 238</p>
<p>9.4. Formulations for an integer linear program 240</p>
<p>9.5. Solving an integer linear program using column generation 243</p>
<p>9.6. Applications 247</p>
<p>9.7. Bibliography 255</p>
<p>Chapter 10. Polyhedral Approaches 261<br /> Ali Ridha MAHJOUB</p>
<p>10.1. Introduction 261</p>
<p>10.2. Polyhedra, faces and facets 265</p>
<p>10.3. Combinatorial optimization and linear programming 276</p>
<p>10.4. Proof techniques 282</p>
<p>10.5. Integer polyhedra and min max relations 293</p>
<p>10.6. Cutting–plane method 301</p>
<p>10.7. The maximum cut problem 308</p>
<p>10.8. The survivable network design problem 313</p>
<p>10.9. Conclusion 319</p>
<p>10.10. Bibliography 320</p>
<p>Chapter 11. Constraint Programming 325<br /> Claude LE PAPE</p>
<p>11.1. Introduction 325</p>
<p>11.2. Problem definition 327</p>
<p>11.3. Decision operators 328</p>
<p>11.4. Propagation 330</p>
<p>11.5. Heuristics 333</p>
<p>11.6. Conclusion 336</p>
<p>11.7. Bibliography 336</p>
<p>List of Authors 339</p>
<p>Index 343</p>
<p>Summary of Other Volumes in the Series 347</p>
<p>PART I. COMPLEXITY OF COMBINATORIAL OPTIMIZATION PROBLEMS 1</p>
<p>Chapter 1. Basic Concepts in Algorithms and Complexity Theory 3<br /> Vangelis Th. PASCHOS</p>
<p>1.1. Algorithmic complexity 3</p>
<p>1.2. Problem complexity 4</p>
<p>1.3. The classes P, NP and NPO 7</p>
<p>1.4. Karp and Turing reductions 9</p>
<p>1.5. NP–completeness 10</p>
<p>1.6. Two examples of NP–complete problems 13</p>
<p>1.7. A few words on strong and weak NP–completeness 16</p>
<p>1.8. A few other well–known complexity classes 17</p>
<p>1.9. Bibliography 18</p>
<p>Chapter 2. Randomized Complexity 21<br /> Jérémy BARBAY</p>
<p>2.1. Deterministic and probabilistic algorithms 22</p>
<p>2.2. Lower bound technique 28</p>
<p>2.3. Elementary intersection problem 35</p>
<p>2.4. Conclusion 37</p>
<p>2.5 Bibliography 37</p>
<p>PART II. CLASSICAL SOLUTION METHODS 39</p>
<p>Chapter 3. Branch–and–Bound Methods 41<br /> Irène CHARON and Olivier HUDRY</p>
<p>3.1. Introduction 41</p>
<p>3.2. Branch–and–bound method principles 43</p>
<p>3.3. A detailed example: the binary knapsack problem 54</p>
<p>3.4. Conclusion 67</p>
<p>3.5. Bibliography 68</p>
<p>Chapter 4. Dynamic Programming 71<br /> Bruno ESCOFFIER and Olivier SPANJAARD</p>
<p>4.1. Introduction 71</p>
<p>4.2. A first example: crossing the bridge 72</p>
<p>4.3. Formalization 75</p>
<p>4.4. Some other examples 79</p>
<p>4.5. Solution 83</p>
<p>4.6. Solution of the examples 88</p>
<p>4.7. A few extensions 90</p>
<p>4.8. Conclusion 98</p>
<p>4.9. Bibliography 98</p>
<p>PART III. ELEMENTS FROM MATHEMATICAL PROGRAMMING 101</p>
<p>Chapter 5. Mixed Integer Linear Programming Models for Combinatorial Optimization Problems 103<br /> Frédérico DELLA CROCE</p>
<p>5.1. Introduction 103</p>
<p>5.2. General modeling techniques 111</p>
<p>5.3. More advanced MILP models 117</p>
<p>5.4. Conclusions 132</p>
<p>5.5. Bibliography 133</p>
<p>Chapter 6. Simplex Algorithms for Linear Programming 135<br /> Frédérico DELLA CROCE and Andrea GROSSO</p>
<p>6.1. Introduction 135</p>
<p>6.2. Primal and dual programs 135</p>
<p>6.3. The primal simplex method 140</p>
<p>6.4. Bland s rule 145</p>
<p>6.5. Simplex methods for the dual problem 147</p>
<p>6.6. Using reduced costs and pseudo–costs for integer programming 152</p>
<p>6.7. Bibliography 155</p>
<p>Chapter 7. A Survey of some Linear Programming Methods 157<br /> Pierre TOLLA</p>
<p>7.1. Introduction 157</p>
<p>7.2. Dantzig s simplex method 158</p>
<p>7.3. Duality 162</p>
<p>7.4. Khachiyan s algorithm 162</p>
<p>7.5. Interior methods 165</p>
<p>7.6. Conclusion 186</p>
<p>7.7. Bibliography 187</p>
<p>Chapter 8. Quadratic Optimization in 0 1 Variables 189<br /> Alain BILLIONNET</p>
<p>8.1. Introduction 189</p>
<p>8.2. Pseudo–Boolean functions and set functions 190</p>
<p>8.3. Formalization using pseudo–Boolean functions 191</p>
<p>8.4. Quadratic pseudo–Boolean functions (qpBf) 192</p>
<p>8.5. Integer optimum and continuous optimum of qpBfs 194</p>
<p>8.6. Derandomization 195</p>
<p>8.7. Posiforms and quadratic posiforms 196</p>
<p>8.8. Optimizing a qpBf: special cases and polynomial cases 198</p>
<p>8.9. Reductions, relaxations, linearizations, bound calculation and persistence 200</p>
<p>8.10. Local optimum 206</p>
<p>8.11. Exact algorithms and heuristic methods for optimizing qpBfs 208</p>
<p>8.12. Approximation algorithms 211</p>
<p>8.13. Optimizing a quadratic pseudo–Boolean function with linear constraints 213</p>
<p>8.14. Linearization, convexification and Lagrangian relaxation for optimizing a qpBf with linear constraints 220</p>
<p>8.15. –Approximation algorithms for optimizing a qpBf with linear constraints 223</p>
<p>8.16. Bibliography 224</p>
<p>Chapter 9. Column Generation in Integer Linear Programming 235<br /> Irène LOISEAU, Alberto CESELLI, Nelson MACULAN and Matteo SALANI</p>
<p>9.1. Introduction 235</p>
<p>9.2. A column generation method for a bounded variable linear programming problem 236</p>
<p>9.3. An inequality to eliminate the generation of a 0 1 column 238</p>
<p>9.4. Formulations for an integer linear program 240</p>
<p>9.5. Solving an integer linear program using column generation 243</p>
<p>9.6. Applications 247</p>
<p>9.7. Bibliography 255</p>
<p>Chapter 10. Polyhedral Approaches 261<br /> Ali Ridha MAHJOUB</p>
<p>10.1. Introduction 261</p>
<p>10.2. Polyhedra, faces and facets 265</p>
<p>10.3. Combinatorial optimization and linear programming 276</p>
<p>10.4. Proof techniques 282</p>
<p>10.5. Integer polyhedra and min max relations 293</p>
<p>10.6. Cutting–plane method 301</p>
<p>10.7. The maximum cut problem 308</p>
<p>10.8. The survivable network design problem 313</p>
<p>10.9. Conclusion 319</p>
<p>10.10. Bibliography 320</p>
<p>Chapter 11. Constraint Programming 325<br /> Claude LE PAPE</p>
<p>11.1. Introduction 325</p>
<p>11.2. Problem definition 327</p>
<p>11.3. Decision operators 328</p>
<p>11.4. Propagation 330</p>
<p>11.5. Heuristics 333</p>
<p>11.6. Conclusion 336</p>
<p>11.7. Bibliography 336</p>
<p>List of Authors 339</p>
<p>Index 343</p>
<p>Summary of Other Volumes in the Series 347</p>