Constraint satisfaction and optimization using sufficient conditions for constraint violation

The paper presents a new approach to combinatorial constraint satisfaction and optimization for problems that can be formulated with constraints represented in inequalities and equalities. It uses sufficient conditions for constraint violation, which the authors call nogood justifications or NJs, to prune the search space. An NJ is either an inequality or a conjunction of inequalities. An NJ is a sufficient condition for constraint violation in the sense that it any NJ holds, at least one constraint will be violated, no matter what values are assigned to variables that are not included in the NJ. They show an algorithm for constraint satisfaction, where NJs are generated during execution and used to cut off even unexplored parts of the search space. The authors make a new NJ with less variables out of existing NJs by eliminating a variable in focus, that is, each occurrence of the variable in focus in the NJs is replaced with values and they make a conjunction of those instantiated NJs. To optimize a criterion function, the algorithm iteratively applies itself to the corresponding constraint satisfaction problem. Experiments with a cutting-stock problem show that (1) NJs are useful for pruning the search space, (2) the approach can optimize more than ten times faster than the ones proposed in other papers, and (3) it is of practical use with the problem as long as performance is concerned. [In Japanese.]