Integrated Methods for Optimization / Edition 1 available in Hardcover, Paperback
Integrated Methods for Optimization / Edition 1
- ISBN-10:
- 1441942580
- ISBN-13:
- 9781441942586
- Pub. Date:
- 11/23/2010
- Publisher:
- Springer US
- ISBN-10:
- 1441942580
- ISBN-13:
- 9781441942586
- Pub. Date:
- 11/23/2010
- Publisher:
- Springer US
Integrated Methods for Optimization / Edition 1
Buy New
$124.00Overview
John Hooker is a leading researcher in both the Optimization and Constraint Programming research communities. He has been an instrumental principal for this integration, and over the years, he has given numerous presentations and tutorials on the integration of these two areas. It is felt by many in the field that the future Optimization courses will increasingly be taught from this integrated framework.
Product Details
ISBN-13: | 9781441942586 |
---|---|
Publisher: | Springer US |
Publication date: | 11/23/2010 |
Series: | International Series in Operations Research & Management Science , #100 |
Edition description: | Softcover reprint of hardcover 1st ed. 2007 |
Pages: | 486 |
Product dimensions: | 6.10(w) x 9.20(h) x 1.20(d) |
About the Author
Prof. Hooker has published two earlier books on the methodologies of Optimization and Constraint Programming. The first was Optimization Methods for Logical Inference (Wiley 1999) and the second was Logic Based Methods for Optimization: Combining Optimization and Constraints Satisfaction (Wiley 2000). This book will be his third book in this evolving area and it is the book that completes the process of integrating these two methodologies into a single set of methods
Table of Contents
Preface xiii
Introduction 1
A Unifying Framework 3
Modeling to Reveal Problem Structure 5
The Role of Duality 7
Advantages of Integrated Methods 9
Some Applications 11
Plan of the Book 12
Bibliographic Notes 13
Search 15
The Solution Process 16
Search 17
Inference 18
Relaxation 19
Exercises 20
Branching Search 21
Branch and Infer 21
Branch and Relax 22
Example: Freight Transfer 24
Example: Production Planning 30
Example: Employee Scheduling 33
Example: Continuous Global Optimization 41
Example: Product Configuration 45
Branch and Price 51
Example: Airline Crew Scheduling 53
Exercises 59
Constraint-Directed Search 63
Constraint-Directed Branching 65
Example: Propositional Satisfiability 67
Partial-Order Dynamic Backtracking 72
Example:Propositional Satisfiability 74
Relaxation in Constraint-Directed Search 75
Logic-Based Benders Decomposition 76
Example: Machine Scheduling 78
Exercises 86
Local Search 88
Some Popular Metaheuristics 89
Local Search Conceived as Branching 90
Relaxation 93
Constraint-Directed Local Search 94
Example: Single-Vehicle Routing 95
Exercises 100
Bibliographic Notes 103
Inference 105
Completeness 106
Basic Definitions 107
Domain Completeness 108
Bounds Completeness 110
k-Completeness 110
k-Consistency 112
Backtracking and Width 112
Exercises 114
Inference Duality 115
Strong Duality and Completeness 116
Certificates and Problem Complexity 117
Sensitivity Analysis 118
Duality and Constraint-Directed Search 119
Exercises 121
Linear Inequalities 121
A Complete Inference Method 122
Domain and Bounds Completeness 124
k-Completeness 125
Linear Programming Duality 127
Sensitivity Analysis 130
Basic Solutions 131
More Sensitivity Analysis 133
Domain Reduction with Dual Multipliers 135
Classical Benders Cuts 136
Exercises 138
General Inequality Constraints 140
The Surrogate Dual 141
The Lagrangean Dual 143
Properties of the Lagrangean Dual 144
Domain Reduction with Lagrange Multipliers 146
Exercises 147
Propositional Logic 148
Logical Clauses 149
A Complete Inference Method 150
Unit Resolution and Horn Clauses 152
Domain Completeness and k-Completeness 152
Strong k-Consistency 154
Completeness of Parallel Resolution 155
Exercises 157
0-1 Linear Inequalities 158
Implication between Inequalities 159
Implication of Logical Clauses 161
Implication of Cardinality Clauses 163
0-1 Resolution 165
k-Completeness 167
Strong k-Consistency 168
Exercises 169
Integer Linear Inequalities 170
The Subadditive Dual 171
The Branching Dual 175
Benders Cuts 178
Exercises 181
The Element Constraint 182
Domain Completeness 183
Bounds Completeness 185
Exercises 187
The All-Different Constraint 187
Bipartite Matching 188
Domain Completeness 189
Bounds Completeness 191
Exercises 193
The Cardinality and Nvalues Constraints 194
The Cardinality Constraint 194
Network Flow Model 195
Domain Completeness for Cardinality 197
The Nvalues Constraint 198
Exercises 198
The Circuit Constraint 199
Modeling with Circuit 200
Elementary Filtering Methods 201
Filtering Based on Separators 202
Network Flow Model 204
Exercises 206
The Stretch Constraint 207
Dynamic Programming Model 208
Domain Completeness 210
Exercises 211
Disjunctive Scheduling 212
Edge Finding 213
Not-First, Not-Last Rules 217
Benders Cuts 222
Exercises 228
Cumulative Scheduling 230
Edge Finding 231
Extended Edge Finding 236
Not-First, Not-Last Rules 238
Energetic Reasoning 239
Benders Cuts 241
Exercises 244
Bibliographic Notes 245
Relaxation 249
Relaxation Duality 251
Linear Inequalities 252
Linear Optimization 252
Relaxation Dual 255
Exercises 257
Semicontinuous Piecewise Linear Functions 259
Convex Hull Relaxation 259
Exercises 260
0-1 Linear Inequalities 261
Chvatal-Gomory Cuts 262
0-1 Knapsack Cuts 266
Sequential Lifting 266
Sequence-Independent Lifting 269
Set Packing Inequalities 271
Exercises 273
Integer Linear Inequalities 275
Chvatal-Gomory Cuts 276
Gomory Cuts 278
Mixed Integer Rounding Cuts 282
Separating Mixed Integer Rounding Cuts 285
Integral Polyhedra 286
Exercises 290
Lagrangean and Surrogate Relaxations 291
Surrogate Relaxation and Duality 292
Lagrangean Relaxation and Duality 292
Lagrangean Relaxation for Linear Programming 293
Example: Generalized Assignment Problem 295
Solving the Lagrangean Dual 296
Exercises 297
Disjunctions of Linear Systems 298
Convex Hull Relaxation 298
Big-M Relaxation 300
Disjunctions of Linear Inequalities 303
Disjunctions of Linear Equations 306
Separating Disjunctive Cuts 307
Exercises 311
Disjunctions of Nonlinear Systems 313
Convex Hull Relaxation 313
Big-M Relaxation 316
Exercises 318
MILP Modeling 318
MILP Representability 319
Example: Fixed-Charge Function 321
Disjunctive Models 324
Knapsack Models 329
Exercises 333
Propositional Logic 335
Common Logical Formulas 335
Resolution as a Tightening Technique 340
Refutation by Linear Relaxation 343
Input Resolution and Rank 1 Cuts 344
Separating Resolvents 348
Exercises 350
The Element Constraint 352
Convex Hull Relaxations 353
Big-M Relaxations 357
Vector-Valued Element 358
Exercises 361
The All-Different Constraint 362
Convex Hull Relaxation 362
Convex Hull MILP Formulation 368
Modeling Costs with Alldiff 369
Example: Quadratic Assignment Problem 372
Exercises 374
The Cardinality Constraint 375
Convex Hull Relaxation 376
Convex Hull MILP Formulation 378
Exercises 378
The Circuit Constraint 379
0-1 Programming Model 379
Continuous Relaxations 380
Comb Inequalities 382
Exercises 385
Disjunctive Scheduling 385
Disjunctive Relaxations 386
MILP Relaxations 388
A Class of Valid Inequalities 390
Exercises 392
Cumulative Scheduling 393
MILP Models 394
A Class of Valid Inequalities 398
Relaxation of Benders Subproblems 400
Exercises 410
Bibliographic Notes 411
Dictionary of Constraints 415
0-1 linear 416
All-different 417
Among 418
Bin packing 419
Cardinality 420
Cardinality clause 421
Cardinality conditional 422
Change 422
Circuit 423
Clique 424
Conditional 424
Cumulative scheduling 425
Cutset 426
Cycle 426
Diffn 427
Disjunctive scheduling 428
Element 429
Flow 430
Indexed linear 431
Integer linear 432
Lex-greater 433
Linear disjunction 433
Logic 434
MILP 435
Min-n 436
Network design 437
Nonlinear disjunction 438
Nvalues 438
Path 439
Piecewise linear 440
Same 441
Set covering 441
Set packing 442
Soft alldiff 443
Stretch 444
Sum 444
Symmetric alldiff 445
Symmetric cardinality 446
Value precedence 446
References 449
Index 475