Logic-Based 0–1 Constraint Programming (Operations Research/Computer Science Interfaces Series, 5)

A logic view of 0-1 integer programming problems, providing new insights into the structure of problems that can lead the researcher to more effective solution techniques depending on the problem class. Operations research techniques are integrated into a logic programming environment. The first monographic treatment that begins to unify these two methodological approaches. Logic-based methods for modelling and solving combinatorial problems have recently started to play a significant role in both theory and practice. The application of logic to combinatorial problems has a dual aspect. On one hand, __constraint logic programming__ allows one to declaratively model combinatorial problems over an appropriate constraint domain, the problems then being solved by a corresponding constraint solver. Besides being a high-level declarative interface to the constraint solver, the logic programming language allows one also to implement those subproblems that cannot be naturally expressed with constraints. On the other hand, logic-based methods can be used as a __constraint solving__ technique within a constraint solver for combinatorial problems modelled as 0-1 integer programs. Contents......Page 3 Foreword......Page 7 Preface......Page 9 CLP & COMBINATORIAL OPTIMIZATION......Page 13 LOGIC-based PSEUDO-BOOLEAN CONSTRAINT SOLVING......Page 16 2 Constraint Logic Programming......Page 21 CLP by EXAMPLE......Page 22 SEMANTICS......Page 26 CONSTRAINT SOLVING......Page 29 LOCAL CONSISTENCY & CLP......Page 31 LOGIC PROGRAMMING with PSEUDO-BOOLEAN CONSTRAINTS......Page 38 EXISTING CLP-SYSTEMS for COMBINATORIAL OPTIMIZATION......Page 46 PRELIMINARIES......Page 57 PREVIOUS WORK......Page 67 GENERALIZED RESOLUTION......Page 78 SOLVED FORM......Page 86 REACHING the SOLVED FORM......Page 87 5 Pseudo-Boolean Unit Resolution......Page 91 CLASSICAL DAVIS-PUTNAM PROCEDURE......Page 92 DAVIS-PUTNAM for LINEAR PSEUDO-BOOLEAN INEQUALITIES......Page 95 OPTIMIZING with PSEUDO-BOOLEAN DAVIS-PUTNAM......Page 98 IMPLEMENTATION......Page 100 HEURISTICS......Page 102 COMPUTATIONAL RESULTS......Page 103 PSEUDO-BOOLEAN DAVIS-PUTNAM for CLP......Page 106 VALID EXTENDED CLAUSES by ENUMERATION......Page 108 ENTAILMENT & LOGIC CUTS......Page 113 7 Linear Pseudo-Boolean Inequalities & Extended Clauses......Page 117 GENERATING VALID EXTENDED CLAUSES......Page 118 IDENTIFYING REDUNDANT EXTENDED CLAUSES......Page 124 IMPLEMENTATION......Page 132 SYMMETRIES......Page 136 DETECTION of FIXED LITERALS......Page 140 CONSTRAINED SIMPLIFICATION......Page 143 CUT GENERATION for 0-1 INTEGER PROGRAMMING......Page 158 IMPLEMENTING RESOLUTION......Page 167 8 Simplification......Page 171 ORDER for EXTENDED CLAUSES......Page 172 SIMPLIFYING DIAGONAL SUMS......Page 173 SIMPLIFYING RESOLVENTS......Page 187 EQUATIONS btw LITERALS......Page 208 PREVIOUS WORK......Page 213 LINEARIZATION METHOD......Page 214 DERIVING LOWER BOUNDS......Page 219 FURTHER IMPROVEMENTS......Page 224 10 Projection......Page 227 PROJECTION for PRIME EXTENDED CLAUSES......Page 228 PROJECTION for EXTENDED CLAUSES......Page 229 IMPROVEMENTS......Page 234 11 Conclusion......Page 236 SUMMARY of RESULTS......Page 237 RELATED & FUTURE RESEARCH......Page 238 Refs......Page 240 Index......Page 257

A logic view of 0-1 integer programming problems, providing new insights into the structure of problems that can lead the researcher to more effective solution techniques depending on the problem class. Operations research techniques are integrated into a logic programming environment. The first monographic treatment that begins to unify these two methodological approaches.
Logic-based methods for modelling and solving combinatorial problems have recently started to play a significant role in both theory and practice. The application of logic to combinatorial problems has a dual aspect. On one hand, constraint logic programming allows one to declaratively model combinatorial problems over an appropriate constraint domain, the problems then being solved by a corresponding constraint solver. Besides being a high-level declarative interface to the constraint solver, the logic programming language allows one also to implement those subproblems that cannot be naturally expressed with constraints. On the other hand, logic-based methods can be used as a constraint solving technique within a constraint solver for combinatorial problems modelled as 0-1 integer programs.