Integrated Methods for Optimization Book

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