Logic-based methods for optimization : combining optimization and constraint satisfaction /

Bibliographic Details
Main Author:	Hooker, John, 1949-
Format:	eBook
Language:	English
Published:	New York : John Wiley & Sons, ©2000.
Subjects:	Linear programming. Mathematical optimization. Logic, Symbolic and mathematical. Programming, Linear Electronic books.
Online Access:	Connect to the full text of this electronic book

Table of Contents:

Front Matter
Introduction
Some Examples
The Logic of Propositions
The Logic of Discrete Variables
The Logic of 0-1 Inequalities
Cardinality Clauses
Classical Boolean Methods
Logic-Based Modeling
Logic-Based Branch and Bound
Constraint Generation
Domain Reduction
Constraint Programming
Continuous Relaxations
Decomposition Methods
Branching Rules
Relaxation Duality
Inference Duality
Search Strategies
Logic-Based Benders Decomposition
Nonserial Dynamic Programming
Discrete Relaxations
References
Index
Wiley-Interscience Series in Discrete Mathematics and Optimization.
1.1 Logic and Optimization 1
1.1.1 Optimization and Constraint Satisfaction 2
1.1.2 Constraint Programming 4
1.1.3 Development of Logic-Based Methods 6
1.1.4 Recent Applications and Software 8
1.2 Organization of the Book 9
1.2.1 How Much to Read 9
1.2.2 Background Material 11
1.2.3 A Practical Logic-Based System 12
1.2.4 A Deeper Analysis 12
2.1 Logic-Based Modeling 16
2.1.1 Traveling Salesman Problem 17
2.1.2 Assignment Problem 18
2.1.3 Quadratic Assignment Problem 19
2.1.4 A Job Shop Scheduling Problem 20
2.2 A Knapsack Problem 23
2.2.1 An Integer Programming Model 23
2.2.2 An Integer Programming Solution 24
2.2.3 A Logic-Based Solution 27
2.3 Processing Network Design 31
2.3.1 An Integer Programming Approach 32
2.3.2 A Logic-Based Approach 33
2.4 Lot Sizing 37
2.4.1 An Integer Programming Model 38
2.4.2 A Logic-Based Model 39
3 Logic of Propositions 43
3.1 Idea of Propositional Logic 44
3.1.1 Formulas 44
3.1.2 Clauses 45
3.1.3 Conversion to Clausal Form 47
3.1.4 Horn Clauses 48
3.1.5 Renamable Horn Clauses 50
3.2 Resolution 53
3.2.1 Resolution Algorithm 53
3.2.2 Projection 55
3.2.3 Unit Resolution 57
3.2.4 Constraint-Based Search 59
4 Logic of Discrete Variables 61
4.1 Formulas of Discrete-Variable Logic 62
4.1.1 Formulas and Semantics 62
4.1.2 Multivalent Clauses 62
4.2 Multivalent Resolution 63
4.2.1 Full Resolution 63
4.2.2 Projection 65
4.2.3 Unit Resolution 65
4.2.4 Constraint Generation 66
4.3 Defined Predicates 67
5 Logic of 0-1 Inequalities 69
5.1 Inequalities and Implication 70
5.2 Resolution for 0-1 Inequalities 73
5.2.1 Algorithm 73
5.2.2 Completeness of 0-1 Resolution 74
5.2.3 Resolution and Cutting Planes 76
5.3 Equivalent Inequalities 78
5.3.1 Characterizing an Equivalence Class 78
5.3.2 A Polar Approach to Checking Equivalence 79
5.3.3 Polar Characterization of Equivalence Classes 83
5.3.4 Canonical Inequalities 85
6 Cardinality Clauses 89
6.1 Resolution for Cardinality Clauses 90
6.1.1 Classical Resolution Step 90
6.1.2 Diagonal Summation Step 93
6.2 Generating Cardinality Clauses 95
6.2.1 Implied Cardinality Clauses 95
6.2.2 Generating Nonredundant Implications 97
6.2.3 Implied Contiguous Clauses 101
7 Classical Boolean Methods 105
7.1 Pseudoboolean Optimization 107
7.1.1 Basic Method 108
7.1.2 Basic Algorithm Revisited 110
7.2 Roof Duality 112
7.2.1 Roofs 112
7.2.2 Roof Dual 114
7.3 Implied Constraints 116
7.3.1 Implications of a Linear 0-1 Inequality 117
7.3.2 Implications of a Nonlinear 0-1 Inequality 118
7.4 Matching Problems 120
8 Logic-Based Modeling 127
8.1 A Modeling Framework 128
8.1.1 Basic Framework 129
8.1.2 A Growing Lexicon of Global Constraints 130
8.1.3 Element Constraints and Variable Subscripts 131
8.1.4 Sum Constraints and Variable Index Sets 133
8.1.5 Integer and Mixed Integer Modeling 133
8.1.6 Objective Function 136
8.2 Some Modeling Examples Revisited 137
8.2.1 Traveling Salesman, Assignment, and Job Shop Problems 137
8.2.2 Knapsack Problem 139
8.2.3 Processing Network Design 140
8.2.4 Lot-Sizing 141
8.3 Additional Examples 142
8.3.1 Progressive Party Problem 142
8.3.2 A Resource-Constrained Scheduling Problem 144
8.3.3 A Production Scheduling Problem 146
9 Logic-Based Branch and Bound 149
9.1 Solution Strategy 150
9.1.1 Inference 152
9.1.2 Solution of a Relaxation 155
9.1.3 Completion of the Solution 156
9.1.4 Branching 158
9.2 Statement of the Algorithm 159
10 Constraint Generation 163
10.1 Consistency and the Dependency Graph 165
10.1.1 Consistency 165
10.1.2 Dependency Graph 166
10.1.3 Constraints and Satisfaction 167
10.2 Consistency and Backtracking 167
10.2.1 k-Consistency 168
10.2.2 k-Consistency and Backtracking 170
10.2.3 Binary Problems 172
10.2.4 Achieving k-Consistency 172
10.3 Adaptive Consistency 175
10.3.1 Adaptive Consistency and Backtracking 175
10.3.2 Achieving Adaptive Consistency 176
10.3.3 Induced Width and k-Trees 177
10.3.4 Induced Width and Complexity 178
10.4 Minimum Width Orderings 179
10.4.1 Finding a Minimum-Width Ordering 179
10.4.2 Minimum Bandwidth Orderings 179
10.4.3 Finding a Minimum Bandwidth Ordering 180
11 Domain Reduction 185
11.1 Consistency 187
11.1.1 Arc and Hyperarc Consistency 187
11.1.2 Bounds Consistency 189
11.2 Element and Sum Constraints 190
11.2.1 Element Constraint 191
11.2.2 Sum Constraint 193
11.3 All-Different Constraint 196
11.3.1 A Combinatorial Algorithm 196
11.3.2 Domain Reduction as a Matching Problem 199
11.4 Constraint Propagation 201
12 Constraint Programming 203
12.1 Development of Constraint Programming 204
12.2 Logic Programming 206
12.2.1 Basic Idea 206
12.2.2 A Scheduling Problem 209
12.3 Constraint Logic Programming 211
12.3.1 Unification as Constraint Solving 212
12.3.2 A Scheduling Problem 216
12.4 Other Approaches 219
13 Continuous Relaxations 225
13.1 Relaxations of Discrete Constraints 227
13.1.1 Propositional Formulas 227
13.1.2 Cardinality Rules 229
13.1.3 All-different Constraints 231
13.2 Relaxations for Mixed Constraints 233
13.2.1 Weak Continuous Relaxations 234
13.2.2 Lifted versus Projected Relaxations 237
13.3 Lifted Relaxations 239
13.3.1 Jeroslow's Representability Theorem 240
13.3.2 Disjunctions: Big-M Relaxations 244
13.3.3 Disjunctions: Convex Hull Relaxation 248
13.4 Projected Relaxations 249
13.4.1 Projection Methods for Linear Systems 250
13.4.2 Disjunctions: Elementary Inequalities 252
13.4.3 Disjunctions: Supporting Inequalities 256
13.4.4 Disjunctions: Optimal Separating Inequalities 257
13.4.5 Fixed Charge Problems 260
13.4.6 Piecewise Linear Functions 263
13.4.7 Element Constraints 265
13.4.8 Extended Element Constraints 267
14 Decomposition Methods 271
14.1 Outer Approximation 272
14.1.1 Basic Algorithm 272
14.2 Benders Decomposition 276
14.2.1 Classical Method 276
14.2.2 Linear Disjunctions 278
14.2.3 Generalized Benders Decomposition 281
14.2.4 Nonlinear Disjunctions 282
15 Branching Rules 285
15.1 General-Purpose Branching Heuristics 286
15.1.1 Rationales for the Heuristics 286
15.2 Branching for Logical Clauses 292
15.2.1 Empirical Behavior of Branching Rules 293
15.2.2 Jeroslow-Wang Rule 294
15.2.3 Maximum Satisfiability Hypothesis 294
15.2.4 A Simplification Hypothesis 296
15.3 First-Fail Heuristics 299
15.3.1 An Elementary Analysis 300
15.3.2 A More Refined Analysis 302
16 Relaxation Duality 305
16.1 Strengthenings and Relaxations 306
16.1.1 A Strengthening Strategy 307
16.1.2 A Relaxation Strategy 309
16.2 Branching 310
16.3 Mixed Strategies 313
16.3.1 Relaxation of Strengthenings 313
16.3.2 Strengthenings of a Relaxation 315
16.4 Relaxation Duality 318
16.4.1 Relaxation Dual 320
16.4.2 Lagrangean and Surrogate Duals 321
17 Inference Duality 325
17.1 Constraint Generation 327
17.1.1 Constraints as Cuts 327
17.1.2 Constraint-Based Search 329
17.3 Linear Programming Duality 333
17.3.1 Linear Inference 333
17.3.2 Sensitivity Analysis 335
17.4 Duality for Logical Clauses 337
17.4.1 Dual Solution as a Resolution Proof 338
17.4.2 Recovering a Dual from a Primal Solution 340
17.5 Duality for Horn Clauses 343
17.6 0-1 Linear Programming Duality 347
17.6.1 Recovering an INdirect Optimality Proof 348
17.6.2 Recovering a Direct Optimality Proof 351
17.6.3 Sensitivity Analysis 355
18 Search Strategies 361
18.1 Branching and Constraint-Based Search 362
18.1.1 Search over
Partial Assignments 363
18.1.2 Branching as Constraint-Based Search 367
18.1.3 Parallel Resolution Search 369
18.2 Dependency-Directed Backtracking 376
18.2.1 Backjumping 376
18.2.2 Backchecking and Backmarking 380
18.3 Dynamic Backtracking 382
18.3.1 Partial-Order Dynamic Backtracking 384
18.3.2 Generalized Dynamic Backtracking 385
19 Logic-Based Benders Decomposition 389
19.1 Benders Decomposition in the Abstract 391
19.1.1 A Simple Example 392
19.1.2 Algorithm 394
19.1.3 Advantage of Benders Decomposition 396
19.1.4 Benders Decomposition as Projection 396
19.2 Classical Benders Decomposition 399
19.2.1 Convergence of Classical Benders 401
19.3 Propositional Satisfiability 402
19.4 0-1 Linear Programming 408
19.5 Optimization Plus Constraint Satisfaction 414
19.5.1 Basic Framework 414
19.5.2 Example: Machine Scheduling 415
19.6 Benders Decomposition for Branching 418
19.6.1 Mixed Integer Programming 419
19.6.2 Problems with Relaxation 419
20 Nonserial Dynamic Programming 423
20.1 Basic Recursion 424
20.1.1 A Feasibility Problem 424
20.1.2 Two Optimization Problems 427
20.1.3 Formal Development 429
20.2 State Space Transition 432
20.2.1 Serial Examples 433.