In maintaining consistencies, such as GAC*, FDGAC* and weak EDGAC*, for global cost functions, Weighted CSP (WCSP) solvers rely on the projection and extension operations, which entail the computation of the cost functions' minima. Tractability of this minimum computation is essential for efficient execution. Since projections/extensions modify the cost functions, an important issue is tractable projection-safety, concerning whether minimum cost computation remains tractable after projections/extensions. In this paper, we prove that tractable projection-safety is always possible for projections/extensions to/from the nullary cost function (W0), and always impossible for projections/extensions to/from n-ary cost functions for n > = 2. When n = 1, the answer is indefinite. We give a simple negative example, while Lee and Leung's flow-based projection-safe cost functions are also tractable projection-safe. We propose polynomially decomposable cost functions, which are amenable to tractable minimum computation. We further prove that the polynomial decomposability property is unaffected by projections/extensionsto/from unary cost functions. Thus, polynomially decomposable cost functions are tractable projection-safe. We show that the SOFT_AMONG, SOFT_REGULAR, SOFT_GRAMMAR and MAX_WEIGHT/MIN_WEIGHT are polynomially decomposable. They are embedded in a WCSP solver for extensive experiments to confirm the feasibility and efficiency of our proposal.

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.

Many combinatorial problems deal with preferences and violations, the goal of which is to find solutions with the minimum cost. Weighted constraint satisfaction is a framework for modeling such problems, which consists of a set of cost functions to measure the degree of violation or preferences of different combinations of variable assignments. Typical solution methods for weighted constraint satisfaction problems (WCSPs) are based on branch-and-bound search, which are made practical through the use of powerful consistency techniques such as AC*, FDAC*, EDAC* to deduce hidden cost information and value pruning during search. These techniques, however, are designed to be efficient only on binary and ternary cost functions which are represented in table form. In tackling many real-life problems, high arity (or global) cost functions are required. We investigate efficient representation scheme and algorithms to bring the benefits of the consistency techniques to also high arity cost functions, which are often derived from hard global constraints from classical constraint satisfaction. The literature suggests some global cost functions can be represented as flow networks, and the minimum cost flow algorithm can be used to compute the minimum costs of such networks in polynomial time. We show that naive adoption of this flow-based algorithmic method for global cost functions can result in a stronger form of null-inverse consistency. We further show how the method can be modified to handle cost projections and extensions to maintain generalized versions of AC* and FDAC* for cost functions with more than two variables. Similar generalization for the stronger EDAC* is less straightforward. We reveal the oscillation problem when enforcing EDAC* on cost functions sharing more than one variable. To avoid oscillation, we propose a weak version of EDAC* and generalize it to weak EDGAC* for non-binary cost functions. Using various benchmarks involving the soft variants of hard global constraints ALLDIFFERENT, GCC, SAME, and REGULAR, empirical results demonstrate that our proposal gives improvements of up to an order of magnitude when compared with the traditional constraint optimization approach, both in terms of time and pruning.

Weighted Constraint Satisfaction is made practical by powerful consistency techniques, such as AC*, FDAC* and EDAC*, which reduce search space effectively and efficiently during search, but they are designed for only binary and ternary constraints. To allow soft global constraints, usually of high arity, to enjoy the same benefits, Lee and Leung give polynomial time algorithms to enforce generalized AC* (GAC*) and FDAC* (FDGAC*) for projection-safe soft non-binary constraints. Generalizing the stronger EDAC* is less straightforward. In this paper, we first reveal the oscillation problem when enforcing EDAC* on constraints sharing more than one variable. To avoid oscillation, we propose a weak version of EDAC* and generalize it to weak EDGAC* for non-binary constraints. Weak EDGAC* is stronger than FDGAC* and GAC*, but weaker than VAC and soft k-consistency for k > 2. We also show that weak EDGAC* can be enforced in polynomial time for projection-safe constraints. Extensive experimentation confirms the efficiency of our proposal.