| Document Type
|
:
|
BL
|
| Record Number
|
:
|
720886
|
| Doc. No
|
:
|
b540586
|
| Main Entry
|
:
|
John Hooker.
|
| Title & Author
|
:
|
Logic-based methods for optimization : : combining optimization and constraint satisfaction\ John Hooker.
|
| Publication Statement
|
:
|
New York: John Wiley & Sons, ©2000.
|
| Page. NO
|
:
|
(xvi, 495 pages) : illustrations
|
| ISBN
|
:
|
1118033035
|
|
|
:
|
: 9781118033036
|
| 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.
|
| Subject
|
:
|
Linear programming.
|
| Subject
|
:
|
Logic, Symbolic and mathematical.
|
| Subject
|
:
|
Mathematical optimization.
|
| LC Classification
|
:
|
T57.74J646 2000
|
| Added Entry
|
:
|
John Hooker
|