Logic-based 0-1 constraint programming (Q1906223)

This book is an improvement of the Ph.D. thesis by the same author. Constraint Logic Programming is introduced and the case of pseudo-Boolean constraints (PBc, for short) is analyzed. In this case primitive constraints are: \(=\), \(<\), \(>\), \(\leq\), \(\geq\), and composite constraints are derived from primitive ones by and, or, neg. Terms subject to PBc are either 0 or 1, or variables, or sums of terms, or products of terms, or the opposite of a term. The author briefly reviews some of the methods presented in the literature for solving PBc problems. Then he presents a complete symbolic solver for linear pseudo-Boolean constraints which is based on their transformation into linear PB inequalities and then into `extended clauses'. This solver adds `logic cuts' to the current set of constraints as long as a suitable relaxation of the problem is not capable to answer the desired questions. Techniques for simplifying linear constraints and for detecting equalities between literals are illustrated. The authors also indicates how one may linearize constraints in case they are initially in a nonlinear form and how one may perform projections, that is, one may get rid of variables which do not appear in the given goal to solve. The book may serve as a useful introduction to the investigation of logical methods for the solution of 0-1 constraint problems. People interested in operations research will find useful to discover some parallels between these logical methods and those based on polyhedrals. Sometimes the thesis style is a bit too apparent and the reader may desire that a more didactic approach would have been followed. A list of the symbols used would have been opportune.