  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.

Artificial Intelligence;Data Structures and Algorithms