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

• Record Nr.: UNINA9910130965303321
• Autore: Hooker John <1949->
• Pubbl/distr/stampa: New York, New York : , : John Wiley & Sons, Inc., , 2000; ©2000
• ISBN: 1-283-28261-5; 9786613282613; 1-118-03128-8; 1-118-03303-5
• Descrizione fisica: 1 online resource (520 p.)
• Collana: Wiley-Interscience Series in Discrete Mathematics and Optimization
• Disciplina: 519.3; 519.72
• Soggetti: Linear programming; Mathematical optimization; Logic, Symbolic and mathematical; Electronic books.
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: "A Wiley-Interscience Publication."
• Nota di bibliografia: Includes bibliographical references at the end of each chapters and index.
• Nota di contenuto: Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction; Preface; Contents; 1 Introduction; 1.1 Logic and Optimization; 1.1.1 Optimization and Constraint Satisfaction; 1.1.2 Constraint Programming; 1.1.3 Development of Logic-Based Methods; 1.1.4 Recent Applications and Software; 1.2 Organization of the Book; 1.2.1 How Much to Read; 1.2.2 Background Material; 1.2.3 A Practical Logic-Based System; 1.2.4 A Deeper Analysis; 2 Some Examples; 2.1 Logic-Based Modeling; 2.1.1 The Traveling Salesman Problem; 2.1.2 The Assignment Problem; 2.1.3 The Quadratic Assignment Problem2.1.4 A Job Shop Scheduling Problem; 2.2 A Knapsack Problem; 2.2.1 An Integer Programming Model; 2.2.2 An Integer Programming Solution; 2.2.3 A Logic-Based Solution; 2.3 Processing Network Design; 2.3.1 An Integer Programming Approach; 2.3.2 A Logic-Based Approach; 2.4 Lot Sizing; ; 2.4.1 An Integer Programming Model; 2.4.2 A Logic-Based Model; 3 The Logic of Propositions; 3.1 The Idea of Propositional Logic; 3.1.1 Formulas; 3.1.2 Clauses; 3.1.3 Conversion to Clausal Form; 3.1.4 Horn Clauses; 3.1.5 Renamable Horn Clauses; 3.2 Resolution; 3.2.1 The Resolution Algorithm3.2.2 Projection; 3.2.3 Unit Resolution; 3.2.4 Constraint-Based Search; 4 The Logic of Discrete Variables; 4.1 Formulas of Discrete-Variable Logic; 4.1.1 Formulas and Semantics; 4.1.2 Multivalent Clauses; 4.2 Multivalent Resolution; 4.2.1 Full Resolution; 4.2.2 Projection; 4-2.3 Unit Resolution; 4.2.4 Constraint Generation; 4.3 Defined Predicates; 5 The Logic of 0-1 Inequalities; 5.1 Inequalities and Implication; 5.2 Resolution for 0-1 Inequalities; 5.2.1 The Algorithm; 5.2.2 Completeness of 0-1 Resolution; 5.2.3 Resolution and Cutting Planes; 5.3 Equivalent Inequalities5.3.1 Characterizing an Equivalence Class; 5.3.2 A Polar Approach to Checking Equivalence; 5.3.3 Polar Characterization of Equivalence Classes; 5.3.4 Canonical Inequalities; 6 Cardinality Clauses; 6.1 Resolution for Cardinality Clauses; 6.1.1 The Classical Resolution Step; 6.1.2 The Diagonal Summation Step; 6.2 Generating Cardinality Clauses; 6.2.1 Implied Cardinality Clauses; 6.2.2 Generating Nonredundant Implications; 6.2.3 Implied Contiguous Clauses; 7 Classical Boolean Methods; 7.1 Pseudoboolean Optimization; 7.1.1 The Basic Method; 7.1.2 The Basic Algorithm Revisited7.2 Roof Duality; 7.2.1 Roofs; 7.2.2 The Roof Dual; 7.3 Implied Constraints; 7.3.1 Implications of a Linear 0-1 Inequality; 7.3.2 Implications of a Nonlinear 0-1 Inequality; 7.4 Matching Problems; 8 Logic-Based Modeling; 8.1 A Modeling Framework; 8.1.1 The Basic Framework; 8.1.2 A Growing Lexicon of Global Constraints; 8.1.3 Element Constraints and Variable Subscripts; 8.1.4 Sum Constraints and Variable Index Sets; 8.1.5 Integer and Mixed Integer Modeling; 8.1.6 The Objective Function; 8.2 Some Modeling Examples Revisited; 8.2.1 Traveling Salesman, Assignment, and Job Shop Problems
• Sommario/riassunto: A pioneering look at the fundamental role of logic in optimization and constraint satisfactionWhile 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