Normal view MARC view

Integrated methods for optimization

Author: Hooker, John N. Series: International series in operations research and management science Publisher: Springer, 2007.Language: EnglishDescription: 486 p. : Graphs ; 24 cm.ISBN: 0387382720Type of document: BookBibliography/Index: Includes bibliographical references and index
Tags: No tags from this library for this title. Log in to add tags.
Item type Current location Collection Call number Status Date due Barcode Item holds
Book Europe Campus
Main Collection
Print QA402.5 .H66 2007
(Browse shelf)
001225626
Available 001225626
Total holds: 0

Includes bibliographical references and index

Digitized

Integrated Methods for Optimization Contents Preface 1. INTRODUCTION 1.1 A Unifying Framework 1.2 Modeling to Reveal Problem Structure 1.3 The Role of Duality 1.4 Advantages of Integrated Methods 1.5 Some Applications 1.6 Plan of the Book 1.7 Bibliographic Notes 2. SEARCH 2.1 The Solution Process 2.1.1 Search 2.1.2 Inference 2.1.3 Relaxation 2.1.4 Exercises 2.2 Branching Search 2.2.1 Branch and Infer 2.2.2 Branch and Relax 2.2.3 Example: Freight Transfer 2.2.4 Example: Production Planning 2.2.5 Example: Employee Scheduling 2.2.6 Example: Continuous Global Optimization 2.2.7 Example: Product Configuration 2.2.8 Branch and Price 2.2.9 Example: Airline Crew Scheduling xiii 1 3 5 7 9 11 12 13 15 16 17 18 19 20 21 21 22 24 30 33 41 45 51 53 vi INTEGRATED METHODS FOR OPTIMIZATION 2.2.10 Exercises 2.3 Constraint-Directed Search 2.3.1 Constraint-Directed Branching 2.3.2 Example: Propositional Satisfiability 2.3.3 Partial-Order Dynamic Backtracking 2.3.4 Example: Propositional Satisfiability 2.3.5 Relaxation in Constraint-Directed Search 2.3.6 Logic-Based Benders Decomposition 2.3.7 Example: Machine Scheduling 2.3.8 Exercises 2.4 Local Search 2.4.1 Some Popular Metaheuristics 2.4.2 Local Search Conceived as Branching 2.4.3 Relaxation 2.4.4 Constraint-Directed Local Search 2.4.5 Example: Single Vehicle Routing 2.4.6 Exercises 2.5 Bibliographic Notes 3. INFERENCE 3.1 Completeness 3.1.1 Basic Definitions 3.1.2 Domain Completeness 3.1.3 Bounds Completeness 3.1.4 k-Completeness 3.1.5 k-Consistency 3.1.6 Backtracking and Width 3.1.7 Exercises 3.2 Inference Duality 3.2.1 Strong Duality and Completeness 3.2.2 Certificates and Problem Complexity 3.2.3 Sensitivity Analysis 3.2.4 Duality and Constraint-Directed Search 3.2.5 Exercises 3.3 Linear Inequalities 3.3.1 A Complete Inference Method 3.3.2 Domain and Bounds Completeness 3.3.3 k-Completeness 3.3.4 Linear Programming Duality 59 63 65 67 72 74 75 76 78 86 88 89 90 93 94 95 100 103 105 106 107 108 110 110 112 112 114 115 116 117 118 119 121 121 122 124 125 127 Contents vii 130 131 133 135 136 138 140 141 143 144 146 147 148 149 150 152 152 154 155 157 158 159 161 163 165 167 168 169 170 171 175 178 181 182 183 185 187 187 3.3.5 Sensitivity Analysis 3.3.6 Basic Solutions 3.3.7 More Sensitivity Analysis 3.3.8 Domain Reduction with Dual Multipliers 3.3.9 Classical Benders Cuts 3.3.10 Exercises 3.4 General Inequality Constraints 3.4.1 The Surrogate Dual 3.4.2 The Lagrangean Dual 3.4.3 Properties of the Lagrangean Dual 3.4.4 Domain Reduction with Lagrange Multipliers 3.4.5 Exercises 3.5 Propositional Logic 3.5.1 Logical Clauses 3.5.2 A Complete Inference Method 3.5.3 Unit Resolution and Horn Clauses 3.5.4 Domain Completeness and k-Completeness 3.5.5 Strong k-Consistency 3.5.6 Completeness of Parallel Resolution 3.5.7 Exercises 3.6 0-1 Linear Inequalities 3.6.1 Implication between Inequalities 3.6.2 Implication of Logical Clauses 3.6.3 Implication of Cardinality Clauses 3.6.4 0-1 Resolution 3.6.5 k-Completeness 3.6.6 Strong k-Consistency 3.6.7 Exercises 3.7 Integer Linear Inequalities 3.7.1 The Subadditive Dual 3.7.2 The Branching Dual 3.7.3 Benders Cuts 3.7.4 Exercises 3.8 The Element Constraint 3.8.1 Domain Completeness 3.8.2 Bounds Completeness 3.8.3 Exercises 3.9 The All-Different Constraint viii INTEGRATED METHODS FOR OPTIMIZATION 3.9.1 Bipartite Matching 3.9.2 Domain Completeness 3.9.3 Bounds Completeness 3.9.4 Exercises 3.10 The Cardinality and Nvalues Constraints 3.10.1 The Cardinality Constraint 3.10.2 Network Flow Model 3.10.3 Domain Completeness for Cardinality 3.10.4 The Nvalues Constraint 3.10.5 Exercises 3.11 The Circuit Constraint 3.11.1 Modeling with Circuit 3.11.2 Elementary Filtering Methods 3.11.3 Filtering Based on Separators 3.11.4 Network Flow Model 3.11.5 Exercises 3.12 The Stretch Constraint 3.12.1 Dynamic Programming Model 3.12.2 Domain Completeness 3.12.3 Exercises 3.13 Disjunctive Scheduling 3.13.1 Edge Finding 3.13.2 Not-First, Not-Last Rules 3.13.3 Benders Cuts 3.13.4 Exercises 3.14 Cumulative Scheduling 3.14.1 Edge Finding 3.14.2 Extended Edge Finding 3.14.3 Not-First, Not-Last Rules 3.14.4 Energetic Reasoning 3.14.5 Benders Cuts 3.14.6 Exercises 3.15 Bibliographic Notes 4. RELAXATION 4.1 Relaxation Duality 4.2 Linear Inequalities 4.2.1 Linear Optimization 188 189 191 193 194 194 195 197 198 198 199 200 201 202 204 206 207 208 210 211 212 213 217 222 228 230 231 236 238 239 241 244 245 249 251 252 252 Contents ix 255 257 259 259 260 261 262 266 266 269 271 273 275 276 278 282 285 286 290 291 292 292 293 295 296 297 298 298 300 303 306 307 311 313 313 316 318 318 4.2.2 Relaxation Dual 4.2.3 Exercises 4.3 Semicontinuous Piecewise Linear Functions 4.3.1 Convex Hull Relaxation 4.3.2 Exercises 4.4 0-1 Linear Inequalities 4.4.1 Chvatal-Gomory Cuts 4.4.2 0-1 Knapsack Cuts 4.4.3 Sequential Lifting 4.4.4 Sequence-Independent Lifting 4.4.5 Set Packing Inequalities 4.4.6 Exercises 4.5 Integer Linear Inequalities 4.5.1 Chvatal-Gomory Cuts 4.5.2 Gomory Cuts 4.5.3 Mixed Integer Rounding Cuts 4.5.4 Separating Mixed Integer Rounding Cuts 4.5.5 Integral Polyhedra 4.5.6 Exercises 4.6 Lagrangean and Surrogate Relaxations 4.6.1 Surrogate Relaxation and Duality 4.6.2 Lagrangean Relaxation and Duality 4.6.3 Lagrangean Relaxation for Linear Programming 4.6.4 Example: Generalized Assignment Problem 4.6.5 Solving the Lagrangean Dual 4.6.6 Exercises 4.7 Disjunctions of Linear Systems 4.7.1 Convex Hull Relaxation 4.7.2 Big-M Relaxation 4.7.3 Disjunctions of Linear Inequalities 4.7.4 Disjunctions of Linear Equations 4.7.5 Separating Disjunctive Cuts 4.7.6 Exercises 4.8 Disjunctions of Nonlinear Systems 4.8.1 Convex Hull Relaxation 4.8.2 Big-M Relaxation 4.8.3 Exercises 4.9 MILP Modeling x INTEGRATED METHODS FOR OPTIMIZATION 4.9.1 MILP Representability 4.9.2 Example: Fixed-Charge Function 4.9.3 Disjunctive Models 4.9.4 Knapsack Models 4.9.5 Exercises 4.10 Propositional Logic 4.10.1 Common Logical Formulas 4.10.2 Resolution as a Tightening Technique 4.10.3 Refutation by Linear Relaxation 4.10.4 Input Resolution and Rank 1 Cuts 4.10.5 Separating Resolvents 4.10.6 Exercises 4.11 The Element Constraint 4.11.1 Convex Hull Relaxations 4.11.2 Big-M Relaxations 4.11.3 Vector-Valued Element 4.11.4 Exercises 4.12 The All-Different Constraint 4.12.1 Convex Hull Relaxation 4.12.2 Convex Hull MILP Formulation 4.12.3 Modeling Costs with Alldiff 4.12.4 Example: Quadratic Assignment Problem 4.12.5 Exercises 4.13 The Cardinality Constraint 4.13.1 Convex Hull Relaxation 4.13.2 Convex Hull MILP Formulation 4.13.3 Exercises 4.14 The Circuit Constraint 4.14.1 0-1 Programming Model 4.14.2 Continuous Relaxations 4.14.3 Comb Inequalities 4.14.4 Exercises 4.15 Disjunctive Scheduling 4.15.1 Disjunctive Relaxations 4.15.2 MILP Relaxations 4.15.3 A Class of Valid Inequalities 4.15.4 Exercises 4.16 Cumulative Scheduling 319 321 324 329 333 335 335 340 343 344 348 350 352 353 357 358 361 362 362 368 369 372 374 375 376 378 378 379 379 380 382 385 385 386 388 390 392 393 Contents xi 4.16.1 MILP Models 4.16.2 A Class of Valid Inequalities 4.16.3 Relaxation of Benders Subproblems 4.16.4 Exercises 394 398 400 410 411 415 416 417 418 419 420 421 422 422 423 424 424 425 426 426 427 428 429 430 431 432 433 433 434 435 436 437 438 438 4.17 Bibliographic Notes 5. DICTIONARY OF CONSTRAINTS 0-1 linear All-different Among Bin packing Cardinality Cardinality clause Cardinality conditional Change Circuit Clique Conditional Cumulative scheduling Cut set Cycle Diffn Disjunctive scheduling Element Flow Indexed linear Integer linear Lex-greater Linear disjunction Logic MILP Min-n Network design Nonlinear disjunction Nvalues xii Path Piecewise linear Same Set covering Set packing Soft alldiff Stretch Sum Symmetric alldiff INTEGRATED METHODS FOR OPTIMIZATION 439 440 441 441 442 443 444 444 445 446 446 449 475 Symmetric cardinality Value precedence References Index

There are no comments for this item.

Log in to your account to post a comment.
Koha 18.11 - INSEAD Catalogue
Home | Contact Us | What's Koha?