Propagating Polynomially (Integral) Linear Projection-Safe Global Cost Functions in WCSPs

Abstract

Lee and Shum consider cost functions that are Polynomially Linear Projection-Safe (PLPS), but whose minimum cost computation is usually NP-hard. They suggest how such cost functions can still be efficiently propagated using relaxed forms of common consistencies. In this paper, we show that conjunctions of PLPS cost functions are still PLPS, and Lee and Shumâs relaxed consistency method is applicable to give better runtime behavior. We further introduce Polynomially Integral Linear Projection-Safe (PILPS) cost functions, a subclass of PLPS cost functions, which have (a) linear formulations with size polynomial to the number of variables and domain sizes, (b) optimal solutions of the linear relaxation always being integral and (c) the last two conditions unaffected by projections/extensions, even though the operations modify the structure of cost functions. We show that conjunctions of PILPS cost functions are PLPS, which still satisfy conditions (a) and (c). Given a standard WCSP consistency α, we give theorems showing that maintaining relaxed α on a conjunction of PILPS cost functions is stronger than maintaining α on the individual cost functions. A useful application of our method is on some PILPS global cost functions, whose minimum cost computations are tractable and yet those for their conjunctions are not. Experiments are conducted to conï¬rm empirically that maintaining relaxed consistencies on the conjoined cost functions is orders of magnitude more efficient, both in runtime and search space reduction, than maintaining the corresponding standard consistencies on the individual cost functions.