| Description |
1 online resource (xvi, 495 pages) : illustrations |
| Series |
Wiley-Interscience series in discrete mathematics and optimization |
|
Wiley-Interscience series in discrete mathematics and optimization.
|
| Contents |
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 |
| Notes |
"A Wiley-Interscience publication." |
| Bibliography |
Includes bibliographical references (pages 463-481) and index |
| Notes |
Description based on print version record |
| Subject |
Linear programming.
|
|
Mathematical optimization.
|
|
Logic, Symbolic and mathematical.
|
| Form |
Electronic book
|
| Author |
Wiley InterScience (Online service)
|
| ISBN |
9781118033036 electronic bk |
|
1118033035 electronic bk |
|
