Muutke küpsiste eelistusi

Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction [Kõva köide]

3.00/5 (4 hinnangut Goodreads-ist)
(Carnegie Mellon University)
Teised raamatud teemal:
Logic-Based Methods for Optimization: Combining Optimization and Constraint SatisfactionSuurem pilt
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780471385219.html
Märksõnad:
Well known for his work at the interface between operations research and computer science, Hooker (operations research and business ethics and social responsibility, Carnegie Mellon U.) here develops a conceptual framework for integrating optimization and constraint satisfaction, then goes a step further and shows how extending logical inference to optimization allows for more powerful as well as flexible modeling and solutions techniques. He strives to be accessible to both industry professionals and academics, and provides examples techniques and modeling frameworks ready for implementation. Annotation c. Book News, Inc., Portland, OR (booknews.com)

A pioneering look at the fundamental role of logic in optimization and constraint satisfaction
While recent efforts to combine optimization and constraint satisfaction have received considerable attention, little has been said about using logic in optimization as the key to unifying the two fields. Logic-Based Methods for Optimization develops for the first time a comprehensive conceptual framework for integrating optimization and constraint satisfaction, then goes a step further and shows how extending logical inference to optimization allows for more powerful as well as flexible modeling and solution techniques. Designed to be easily accessible to industry professionals and academics in both operations research and artificial intelligence, the book provides a wealth of examples as well as elegant techniques and modeling frameworks ready for implementation. Timely, original, and thought-provoking, Logic-Based Methods for Optimization:
* Demonstrates the advantages of combining the techniques in problem solving
* Offers tutorials in constraint satisfaction/constraint programming and logical inference
* Clearly explains such concepts as relaxation, cutting planes, nonserial dynamic programming, and Bender's decomposition
* Reviews the necessary technologies for software developers seeking to combine the two techniques
* Features extensive references to important computational studies
* And much more

Arvustused

"This is a book that should be widely read by graduate students and researchers in both the computer science and optimization communities." (Choice, Vol. 38, No. 7, March 2001) "Goal is to broaden the conceptual foundations of optimization to include logical and constraint based approaches to traditional optimization methods." (American Mathematical Monthly, November 2001) "The author combines a low-key, often conversational presentation with enthusiasm for a synthesis with traditional optimization methods..." (SIAM Review, Vol. 43, No. 4) "The book is for practitioners as well as theorists" (Zentralblatt Math, Vol.974, No.24, 2001)

Preface vii
Introduction
1(14)
Logic and Optimization
1(8)
Optimization and Constraint Satisfaction
2(2)
Constraint Programming
4(2)
Development of Logic-Based Methods
6(2)
Recent Applications and Software
8(1)
Organization of the Book
9(6)
How Much to Read
9(2)
Background Material
11(1)
A Practical Logic-Based System
12(1)
A Deeper Analysis
12(3)
Some Examples
15(28)
Logic-Based Modeling
16(7)
The Traveling Salesman Problem
17(1)
The Assignment Problem
18(1)
The Quadratic Assignment Problem
19(1)
A Job Shop Scheduling Problem
20(3)
A Knapsack Problem
23(8)
An Integer Programming Model
23(1)
An Integer Programming Solution
24(3)
A Logic-Based Solution
27(4)
Processing Network Design
31(6)
An Integer Programming Approach
32(1)
A Logic-Based Approach
33(4)
Lot Sizing
37(6)
An Integer Programming Model
38(1)
A Logic-Based Model
39(4)
The Logic of Propositions
43(18)
The Idea of Propositional Logic
44(9)
Formulas
44(1)
Clauses
45(2)
Conversion to Clausal Form
47(1)
Horn Clauses
48(2)
Renamable Horn Clauses
50(3)
Resolution
53(8)
The Resolution Algorithm
53(2)
Projection
55(2)
Unit Resolution
57(2)
Constraint-Based Search
59(2)
The Logic of Discrete Variables
61(8)
Formulas of Discrete-Variable Logic
62(1)
Formulas and Semantics
62(1)
Multivalent Clauses
62(1)
Multivalent Resolution
63(4)
Full Resolution
63(2)
Projection
65(1)
Unit Resolution
65(1)
Constraint Generation
66(1)
Defined Predicates
67(2)
The Logic of 0-1 Inequalities
69(20)
Inequalities and Implication
70(3)
Resolution for 0-1 Inequalities
73(5)
The Algorithm
73(1)
Completeness of 0-1 Resolution
74(2)
Resolution and Cutting Planes
76(2)
Equivalent Inequalities
78(11)
Characterizing an Equivalence Class
78(1)
A Polar Approach to Checking Equivalence
79(4)
Polar Characterization of Equivalence Classes
83(2)
Canonical Inequalities
85(4)
Cardinality Clauses
89(16)
Resolution for Cardinality Clauses
90(5)
The Classical Resolution Step
90(3)
The Diagonal Summation Step
93(2)
Generating Cardinality Clauses
95(10)
Implied Cardinality Clauses
95(2)
Generating Nonredundant Implications
97(4)
Implied Contiguous Clauses
101(4)
Classical Boolean Methods
105(22)
Pseudoboolean Optimization
107(5)
The Basic Method
108(2)
The Basic Algorithm Revisited
110(2)
Roof Duality
112(4)
Roofs
112(2)
The Roof Dual
114(2)
Implied Constraints
116(4)
Implications of a Linear 0-1 Inequality
117(1)
Implications of a Nonlinear 0-1 Inequality
118(2)
Matching Problems
120(7)
Logic-Based Modeling
127(22)
A Modeling Framework
128(9)
The Basic Framework
129(1)
A Growing Lexicon of Global Constraints
130(1)
Element Constraints and Variable Subscripts
131(2)
Sum Constraints and Variable Index Sets
133(1)
Integer and Mixed Integer Modeling
133(3)
The Objective Function
136(1)
Some Modeling Examples Revisited
137(5)
Traveling Salesman, Assignment, and Job Shop Problems
137(2)
Knapsack Problem
139(1)
Processing Network Design
140(1)
Lot-Sizing
141(1)
Additional Examples
142(7)
The Progressive Party Problem
142(2)
A Resource-Constrained Scheduling Problem
144(2)
A Production Scheduling Problem
146(3)
Logic-Based Branch and Bound
149(14)
The Solution Strategy
150(9)
Inference
152(3)
Solution of a Relaxation
155(1)
Completion of the Solution
156(2)
Branching
158(1)
Statement of the Algorithm
159(4)
Constraint Generation
163(22)
Consistency and the Dependency Graph
165(2)
Consistency
165(1)
The Dependency Graph
166(1)
Constraints and Satisfaction
167(1)
Consistency and Backtracking
167(8)
k-Consistency
168(2)
k-Consistency and Backtracking
170(2)
Binary Problems
172(1)
Achieving k-Consistency
172(3)
Adaptive Consistency
175(4)
Adaptive Consistency and Backtracking
175(1)
Achieving Adaptive Consistency
176(1)
Induced Width and k-Trees
177(1)
Induced Width and Complexity
178(1)
Minimum Width Orderings
179(6)
Finding a Minimum-Width Ordering
179(1)
Minimum Bandwidth Orderings
179(1)
Finding a Minimum Bandwidth Ordering
180(5)
Domain Reduction
185(18)
Consistency
187(3)
Arc and Hyperarc Consistency
187(2)
Bounds Consistency
189(1)
The Element and Sum Constraints
190(6)
The Element Constraint
191(2)
The Sum Constraint
193(3)
The All-Different Constraint
196(5)
A Combinatorial Algorithm
196(3)
Domain Reduction as a Matching Problem
199(2)
Constraint Propagation
201(2)
Constraint Programming
203(22)
Development of Constraint Programming
204(2)
Logic Programming
206(5)
Basic Idea
206(3)
A Scheduling Problem
209(2)
Constraint Logic Programming
211(8)
Unification as Constraint Solving
212(4)
A Scheduling Problem
216(3)
Other Approaches
219(6)
Continuous Relaxations
225(46)
Relaxations of Discrete Constraints
227(6)
Propositional Formulas
227(2)
Cardinality Rules
229(2)
All-different Constraints
231(2)
Relaxations for Mixed Constraints
233(6)
Weak Continuous Relaxations
234(3)
Lifted versus Projected Relaxations
237(2)
Lifted Relaxations
239(10)
Jeroslow's Representability Theorem
240(4)
Disjunctions: Big-M Relaxations
244(4)
Disjunctions: Convex Hull Relaxation
248(1)
Projected Relaxations
249(22)
Projection Methods for Linear Systems
250(2)
Disjunctions: Elementary Inequalities
252(4)
Disjunctions: Supporting Inequalities
256(1)
Disjunctions: Optimal Separating Inequalities
257(3)
Fixed Charge Problems
260(3)
Piecewise Linear Functions
263(2)
Element Constraints
265(2)
Extended Element Constraints
267(4)
Decomposition Methods
271(14)
Outer Approximation
272(4)
The Basic Algorithm
272(1)
Getting Started
273(3)
Benders Decomposition
276(9)
The Classical Method
276(2)
Linear Disjunctions
278(3)
Generalized Benders Decomposition
281(1)
Nonlinear Disjunctions
282(3)
Branching Rules
285(20)
General-Purpose Branching Heuristics
286(6)
Rationales for the Heuristics
286(6)
Conclusion
292(1)
Branching for Logical Clauses
292(7)
Empirical Behavior of Branching Rules
293(1)
The Jeroslow-Wang Rule
294(1)
The Maximum Satisfiability Hypothesis
294(2)
A Simplification Hypothesis
296(2)
Conclusions
298(1)
First-Fail Heuristics
299(6)
An Elementary Analysis
300(2)
A More Refined Analysis
302(3)
Relaxation Duality
305(20)
Strengthenings and Relaxations
306(4)
A Strengthening Strategy
307(2)
A Relaxation Strategy
309(1)
Branching
310(3)
Mixed Strategies
313(5)
Relaxation of Strengthenings
313(2)
Strengthenings of a Relaxation
315(3)
Relaxation Duality
318(7)
The Relaxation Dual
320(1)
The Lagrangean and Surrogate Duals
321(4)
Inference Duality
325(36)
Constraint Generation
327(4)
Constraints as Cuts
327(2)
Constraint-Based Search
329(2)
Basic Definition
331(2)
Linear Programming Duality
333(4)
Linear Inference
333(2)
Sensitivity Analysis
335(2)
Duality for Logical Clauses
337(6)
The Dual Solution as a Resolution Proof
338(2)
Recovering a Dual from a Primal Solution
340(3)
Duality for Horn Clauses
343(4)
0-1 Linear Programming Duality
347(14)
Recovering an Indirect Optimality Proof
348(3)
Recovering a Direct Optimality Proof
351(4)
Sensitivity Analysis
355(6)
Search Strategies
361(28)
Branching and Constraint-Based Search
362(14)
Search over Partial Assignments
363(4)
Branching as Constraint-Based Search
367(2)
Parallel Resolution Search
369(7)
Dependency-Directed Backtracking
376(6)
Backjumping
376(4)
Backchecking and Backmarking
380(2)
Dynamic Backtracking
382(7)
Partial-Order Dynamic Backtracking
384(1)
Generalized Dynamic Backtracking
385(4)
Logic-Based Benders Decomposition
389(34)
Benders Decomposition in the Abstract
391(8)
A Simple Example
392(2)
The Algorithm
394(2)
Advantage of Benders Decomposition
396(1)
Benders Decomposition as Projection
396(3)
Classical Benders Decomposition
399(3)
Convergence of Classical Benders
401(1)
An Example
401(1)
Propositional Satisfiability
402(6)
0-1 Linear Programming
408(6)
Optimization Plus Constraint Satisfaction
414(4)
The Basic Framework
414(1)
Example: Machine Scheduling
415(3)
Benders Decomposition for Branching
418(5)
Mixed Integer Programming
419(1)
Problems with Relaxation
419(4)
Nonserial Dynamic Programming
423(20)
The Basic Recursion
424(8)
A Feasibility Problem
424(3)
Two Optimization Problems
427(2)
Formal Development
429(3)
State Space Transition
432(11)
Serial Examples
433(3)
Nonserial Examples
436(7)
Discrete Relaxations
443(20)
Relaxation by Decoupling
444(10)
Decoupling by Projection
444(2)
Reducing the Induced Width
446(2)
Using Relaxations Based on Decoupling
448(6)
Discrete Relaxation Duals
454(9)
Duality for Relaxation by Decoupling
454(4)
A Discrete Lagrangean Relaxation
458(1)
Discrete Relaxation of the Traveling Salesman Problem
459(4)
References 463(20)
Index 483


JOHN HOOKER, PhD, is Professor of Operations Research and T. Jerome Holleran Professor of Business Ethics and Social Responsibility at the Graduate School of Industrial Administration, Carnegie Mellon University. Well-known for his work in the operations research/computer science interface, Dr. Hooker has published over 80 articles and coauthored (with Vijay Chandru) Optimization Methods for Logical Inference, also available from Wiley.