عنوان

Logic-based methods for optimization :

شابک

1118033035

شابک

9781118033036

شماره

b540586

عنوان اصلي

Logic-based methods for optimization :

نام عام مواد

[Book]

ساير اطلاعات عنواني

combining optimization and constraint satisfaction

نام نخستين پديدآور

John Hooker.

محل نشرو پخش و غیره

New York

نام ناشر، پخش کننده و غيره

John Wiley & Sons

تاریخ نشرو بخش و غیره

©2000.

نام خاص و کميت اثر

(xvi, 495 pages) : illustrations

متن يادداشت

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.

متن يادداشت

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

متن يادداشت

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.

موضوع مستند نشده

Linear programming.

موضوع مستند نشده

Logic, Symbolic and mathematical.

موضوع مستند نشده

Mathematical optimization.

شماره رده

نشانه اثر

مستند نام اشخاص تاييد نشده

John Hooker.

مستند نام اشخاص تاييد نشده

John Hooker

نام الکترونيکي

نوع ماده

[Book]

تكميل شده

Y