David Allouche

Christian Bessiere

Patrice Boizumault

Simon De Givry

Patricia Gutierrez

Samir Loudni

Jean-Philippe Metivier

Thomas Schiex

Jimmy H M Lee

Ka Lun Leung

Jean-Philippe Métivier

Yi Wu

Tractability-preserving Transformations of Global Cost Functions

Introduction

Cost Function Networks (CFNs) offer a simple and general framework for modeling and solving over-constrained and optimization problems. They capture a variety of problems that range from CSP, SAT and Max-SAT to maximization of likelihood in stochastic variants such as Markov Random Fields or Bayesian networks. They have been applied to a variety of real problems, in resource allocation, bioinformatics or machine learning among others [START_REF] Cabon | Radio link frequency assignment[END_REF][START_REF] Sánchez | Mendelian Error Detection in Complex Pedigrees using Weighted Constraint Satisfaction Techniques[END_REF][START_REF] Dibangoye | Optimally solving dec-pomdps as continuous-state mdps[END_REF][START_REF] Ermon | Embed and project: Discrete sampling with universal hashing[END_REF][START_REF] Simoncini | Guaranteed discrete energy optimization on large protein design problems[END_REF][START_REF] Allouche | Computational protein design as an optimization problem[END_REF][START_REF] Hurley | Multi-language evaluation in graphical model optimization[END_REF].

Besides being equipped with an efficient branch and bound procedure augmented with powerful local consistency techniques, a practical CFN solver should have a good library of global cost functions to model the often complex scenarios in real-life applications.

Enforcing local consistencies requires to apply Equivalence Preserving Transformations (EPTs) such as cost projection and extension [START_REF] Cooper | Arc Consistency for Soft Constraints[END_REF]. Most local consistencies require to compute minima of the cost function to determine the amount of cost to project/extend. By applying these operations, local consistencies may reduce domains and, more importantly, tighten a global lower bound on the criteria to optimize. This is crucial for branch and bound efficiency. Global cost functions have unbounded arity, but may have a specific semantics that makes available dedicated polynomial-time algorithms for minimization. However, when local consistencies apply EPTs, they modify the cost function and may break the properties that makes it polynomial-time minimizable. We say that a cost function is tractable if it can be minimized in polynomial time. The notion of tractable projection-safety captures precisely those functions that remain tractable even after EPTs.

In this paper, we prove that any tractable global cost function remains tractable after EPTs to/from the zero-arity cost function (W ∅ ), and cannot remain tractable if arbitrary EPTs to/from r-ary cost functions for r ≥ 2 are allowed. When r = 1, we show that the answer is indefinite. We describe a simple tractable global cost function and show how it becomes intractable after projections/extensions to/from unary cost functions. We also show that flow-based projection-safe cost functions [START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF] are positive examples of tractable projection-safe cost functions.

For r = 1, we introduce polynomially DAG-filterable global cost functions, which can be transformed into a filtering Directed Acyclic Graph with a polynomial number of simpler cost functions for (minimum) cost calculation. Computing minima of such cost functions, using a polynomial time dynamic programming algorithm, is tractable and remains tractable after projections/extensions. Thus, polynomially DAG-filterable cost functions are tractable projection-safe. Adding to the existing repertoire of global cost functions, cost function variants of existing global constraints such as Among, Regular, Grammar, and Max/Min, are proved to be polynomially DAG-filterable.

To avoid the need to implement dedicated dynamic programming algorithms, we also consider the possibility of directly using decompositions of global cost functions into polynomial size networks of cost functions with bounded arities, usually ternary cost functions. We show how such network-decompositions can be derived from known global constraint decompositions and how Berge-acyclicity allows soft local consistencies to emulate dynamic programming in this case. We prove that Berge-acyclic networkdecompositions can also be used to directly build polynomial filtering DAGs.

To demonstrate the feasibility of these approaches, we implement and embed various global cost functions using filtering DAG and network-decompositions in toulbar2, an open source cost function networks solver. We conduct experiments using different benchmarks to evaluate and to compare the performance of the DAG-based and network-based decomposition approaches.

The rest of the paper is organized as follows. Section 2 contains the necessary background to understand our contributions. Section 3 analyses the tractability of enforcing local consistencies on global cost functions and characterizes the conditions for preserving tractability after applying EPTs. In Section 4 we define DAG-filtering and in Section 5 we give an example of a polynomial DAG-filterable global cost function. Sections 6 and 7 present network-decomposability and the conditions for preserving the level of local consistency. Section 8 shows the relation between network-decompositions and DAGfiltering. Section 9 provides an experimental analysis of the two approaches on several classes of problems. Section 10 concludes the paper.

Background

We give preliminaries on cost function networks and global cost functions.

Cost Function Networks

A cost function network (CFN) is a special case of the valued constraint satisfaction problem [START_REF] Schiex | Valued Constraint Satisfaction Problems: Hard and Easy Problems[END_REF] with a specific cost structure ([0, . . . , ], ⊕, ≤). We give the formal definitions of the cost structure and CFN as follows.

Definition 1 (Cost Structure [START_REF] Schiex | Valued Constraint Satisfaction Problems: Hard and Easy Problems[END_REF]). The cost structure ([0, . . . , ], ⊕, ≤) is a tuple defined as:

• [0, . . . , ] is the interval of integers from 0 to ordered by the standard ordering ≤, where is either a positive integer or +∞.

• ⊕ is the addition operation defined as a ⊕ b = min( , a + b). We also define the subtraction operator for any a and b, where a ≥ b, as:

a b = a -b, if a = ; , otherwise
Note that more general additive cost structures have also been used. Specifically, VAC and OSAC [START_REF] Cooper | Soft Arc Consistency Revisited[END_REF] local consistencies are defined using a structure using non-negative rational instead of non-negative integer numbers. For ease of understanding, our discussion assumes integral costs. However, it can easily be generalized to rational costs. Definition 2 (Cost Function Network [START_REF] Schiex | Arc Consistency for Soft Constraints[END_REF]). A Cost Function Network (CFN) is a tuple (X , W, ), where:

• X is an ordered set of discrete domain variables {x 1 , x 2 , . . . , x n }. The domain of

x i ∈ X being denoted as D(x i );

• W is a set of cost functions W S each with a scope S = {x s1 , . . . , x sr } ⊆ X that maps tuples ∈ D S , where

D S = D(x s1 ) × • • • × D(x sr ), to [0, . . . , ].
When the context is clear, we abuse notation by denoting an assignment of a set of variables S ⊆ X as a tuple = (v s1 , . . . , v sr ) ∈ D S . The notation [x si ] denotes the value v si assigned to x si in , and [S ] denotes the tuple formed by projecting onto S ⊆ S. Without loss of generality, we assume W = {W ∅ } ∪ {W i | x i ∈ X } ∪ W + . W ∅ is a constant zero-arity cost function. W i is a unary cost function associated with each x i ∈ X . W + is a set of cost functions W S with scope S and |S| ≥ 2. If W ∅ and {W i } are not defined, we assume W i (v) = 0 for all v ∈ D(x i ) and W ∅ = 0. To simplify notation, we also denote by W s1,s2,...,sr the cost function on variables {x s1 , x s2 , . . . , x sr } when the context is clear. Definition 3. Given a CFN (X , W, ), the cost of a tuple ∈ D X is defined as cost( ) = W S ∈W W S ( [S]). A tuple ∈ D X is feasible if cost( ) < , and it is an optimal solution of the CFN if cost( ) is minimum among all tuples in D X .

We observe that a classical Constraint Network is merely a CFN where all cost functions W S ∈ W are such that ∀ ∈ D S , W S ( ) ∈ {0, }. The problem of the existence of a solution in a constraint network, called Constraint Satisfaction Problem (CSP), is NP-complete. Finding an optimal solution to a CFN is thus above NP. Restrictions to Boolean variables and binary constraints are known to be APX-hard [START_REF] Papadimitriou | Optimization, approximation, and complexity classes[END_REF]. In the terminology of stochastic graphical models, this problem is also equivalent to the Maximum A Posteriori (MAP/MRF) problem or the Maximum Probability Explanation (MPE) in Bayesian networks [START_REF] Hurley | Multi-language evaluation in graphical model optimization[END_REF]. CFNs can be solved exactly with depth-first branch-and-bound search using W ∅ as a lower bound. Search efficiency is enhanced by maintaining local consistencies that increase the lower bound by redistributing costs among W S , pushing costs into W ∅ and W i , and pruning values while preserving the equivalence of the problem (i.e., the cost of each tuple ∈ D X is unchanged).

Soft local consistencies and EPTs

Different consistency notions have been defined. Examples include NC* [START_REF] Larrosa | Solving Weighted CSP by Maintaining Arc Consistency[END_REF], (G)AC* [START_REF] Schiex | Arc Consistency for Soft Constraints[END_REF][START_REF] Larrosa | Solving Weighted CSP by Maintaining Arc Consistency[END_REF][START_REF] Cooper | Arc Consistency for Soft Constraints[END_REF][START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], FD(G)AC* [START_REF] Larrosa | Solving Weighted CSP by Maintaining Arc Consistency[END_REF][START_REF] Larrosa | In the Quest of the Best Form of Local Consistency for Weighted CSP[END_REF][START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], (weak) ED(G)AC* [START_REF] De Givry | Existential Arc Consistency: Getting Closer to Full Arc Consistency in Weighted CSPs[END_REF][START_REF] Lee | A Stronger Consistency for Soft Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], VAC and OSAC [START_REF] Cooper | Soft Arc Consistency Revisited[END_REF]. Enforcing such local consistencies requires applying equivalence preserving transformations (EPTs) that shift costs between different scopes. The main EPT is defined below and described as Algorithm 1. This is a compact version of the projection and extension defined in [START_REF] Cooper | High-Order Consistency in Valued Constraint Satisfaction[END_REF]. Definition 4 (EPTs [START_REF] Cooper | High-Order Consistency in Valued Constraint Satisfaction[END_REF]). Given two cost functions W S1 and W S2 , S 2 ⊂ S 1 , the EPT Project (S 1 , S 2 , , α) shifts an amount of cost α between a tuple ∈ D S2 of W S2 and the cost function W S1 . The direction of the shift is given by the sign of α. The precondition guarantees that costs remain non negative after the EPT has been applied.

Denoting by r = |S 2 |, the EPT is called an r-EPT. It is an r-projection when α ≥ 0 and an r-extension when α < 0.

It is now possible to introduce local consistency enforcing algorithms.

Definition 5 (Node Consistency [42]). A variable x

i is star node consistent (NC*) if each value v ∈ D(x i ) satisfies W i (v) ⊕ W ∅ < and there exists a value v ∈ D(x i ) such that W i (v ) = 0. A CFN is NC* iff all variables are NC*. Precondition: -W S2 ( ) ≤ α ≤ min ∈D S 1 , [S2]= W S1 ( ); Procedure Project(S 1 , S 2 , , α) W S2 ( ) ← W S2 ( ) ⊕ α; foreach ( ∈ D S1 such that [S 2 ] = ) do W S1 ( ) ← W S1 ( ) α;
Algorithm 1: A cost shifting EPT used to enforce soft local consistencies. The ⊕, operations are extended here to handle possibly negative costs as follows: for non-negative costs α, β, we have α

(-β) = α ⊕ β and for β ≤ α, α ⊕ (-β) = α β.
Procedure enforceNC*() Definition 6 ((Generalized) Arc Consistency [START_REF] Cooper | Arc Consistency for Soft Constraints[END_REF][START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF]). Given a CFN P = (X , W, ), a cost function W S ∈ W + and a variable x i ∈ S.

foreach x i ∈ X do unaryProject(x i ); 1 foreach x i ∈ X do pruneVar(x i ); 2 Procedure unaryProject(x i ) α := min{W i (v) | v ∈ D(x i )}; 3 Project({x i }, ∅, (), α); 4 Procedure pruneVar(x i ) foreach v ∈ D(x i ) s.t. W i (v) ⊕ W ∅ = do 5 D(x i ) := D(x i ) \ {v};
• A tuple ∈ D S is a simple support for v ∈ D(x i ) with respect to W S with x i ∈ S iff [x i ] = v and W S ( ) = 0. • A variable x i ∈ S is star generalized arc consistent (GAC*) with respect to W S iff -x i is NC*; -each value v i ∈ D(x i
) has a simple support with respect to W S .

• A CFN is GAC* iff all variables are GAC* with respect to all related non-unary cost functions.

To avoid exponential space complexity, the GAC* definition and the algorithm is slightly different from the one given by Cooper and Schiex [START_REF] Cooper | Arc Consistency for Soft Constraints[END_REF], which also requires for every tuple

∈ D S , W S ( ) = if W ∅ ⊕ xi∈S W i ( [x i ]) ⊕ W S ( ) = .
The procedure enforceGAC*() in Algorithm 3, enforces GAC* on a single variable x i ∈ X with respect to a cost function W S ∈ W + , where x i ∈ S in a CFN (X , W, ). The procedure first computes the minimum when x i = v for each v ∈ D(x i ) at line 2, then performs a 1-projection from W S to W i at line 3. Lines 4 and 5 enforce NC* on x i . In practice, projections and extensions can be performed in constant time using the ∆ data-structure introduced in Cooper and Schiex [START_REF] Cooper | Arc Consistency for Soft Constraints[END_REF]. For example, when we perform 1-projections or 1-extensions, instead of modifying the costs of all tuples, we store the projected and extended costs in ∆ - xi,v and ∆ + xi,v respectively. Whenever we compute the value of the cost function W S for a tuple with

Procedure enforceGAC*(W S , x i ) foreach v ∈ D(x i ) do 1 α := min{W S ( ) | ∈ D S ∧ [x i ] = v}; 2 Project(S, {x i }, (v), α) 3 unaryProject(x i );
[x i ] = v, we return W S ( ) ∆ - xi,v ⊕∆ + xi,v
(d • f min + d) = O(d • f min ).
In the general case, f min is in O(d r ) where r is the size of the scope and d the maximum domain size. However, a global cost function may have specialized algorithms which make the operation of finding minimum, and thus consistency enforcement, tractable.

Global Constraints, Soft Global Constraints and Global Cost Functions

Definition 7 (Global Constraint [START_REF] Beldiceanu | Global Constraint Catalog[END_REF][START_REF] Rossi | Handbook of Constraint Programming[END_REF]). A global constraint, denoted by GC(S, A 1 , . . . , A t ), is a family of hard constraints parameterized by a scope S, and possibly extra parameters A 1 , . . . , A t .

Examples of global constraints are AllDifferent [START_REF] Lauriere | A Language and a Program for Stating and Solving Combinatorial Problems[END_REF], GCC [START_REF] Régin | Generalized Arc Consistency for Global Cardinality Constraints[END_REF], Same [START_REF] Beldiceanu | Filtering Algorithms for the Same Constraints[END_REF], Among [START_REF] Beldiceanu | Introducing Global Constraints in CHIP[END_REF], Regular [START_REF] Pesant | A Regular Language Membership Constraint for Finite Sequences of Variables[END_REF], Grammar [START_REF] Kadioglu | Grammar Constraints[END_REF], and Maximum/Minimum constraints [START_REF] Beldiceanu | Pruning for the Minimum Constraint Family and for the Number of Distinct Values Constraint Family[END_REF]. Because of their unbounded scope, global constraints cannot be efficiently propagated by generic local consistency algorithms, which are exponential in the arity of the constraint. Specific propagation algorithms are designed to achieve polynomial time complexity in the size of the input, i.e. the scope, the domains and extra parameters.

To capture the idea of costs assigned to constraint violations, the notion of soft global constraint has been introduced. This is a traditional global constraint with one extra variable representing the cost of the assignment w.r.t. to an existing global constraint. The cost is given by a violation measure function.

Definition 8 (Soft Global Constraint [START_REF] Petit | Specific Filtering Algorithm for Over-Constrained Problems[END_REF]). A soft global constraint, denoted by Soft GC µ (S∪ {z}, A 1 , . . . , A t ), is a family of hard constraints parameterized by a violation measure µ, a scope S, a cost variable z, and possibly extra parameters A 1 , . . . , A t . The constraint is satisfied if and only if z = µ(S, A 1 , . . . , A t ).

Soft global constraints are used to introduce costs in the CSP framework, and therefore inside constraint programming solvers [START_REF] Petit | Specific filtering algorithms for over-constrained problems[END_REF]. It requires the introduction of extra cost variables and does not exploit the stronger propagation offered by some of the soft local consistencies. A possible alternative, when a sum of costs needs to be optimized, lies in the use of global cost functions.

Definition 9 (Global Cost Function [START_REF] Zytnicki | Bounds Arc Consistency for Weighted CSPs[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF]). A global cost function, denoted as W GCF(S, A 1 , . . . , A t ), is a family of cost functions parameterized by a scope S and possibly extra parameters A 1 , . . . , A t .

For example, if S is a set of variables with non-negative integer domains, it is easy to define the Global Cost Function W Sum(S) ≡ xi∈S min( , x i ).

It is possible to derive a global cost function from an existing soft global constraint Soft GC µ (S ∪ {z}, A 1 , . . . , A t ). In this case, we denote the corresponding global cost function as W GCF µ . Its value for a tuple ∈ D S is equal to min( , µ( )).

For example, global cost functions W AllDifferent var /W AllDifferent dec [START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF] can be derived from two different violation measures of AllDifferent, namely variable-based and decomposition-based [START_REF] Petit | Specific Filtering Algorithm for Over-Constrained Problems[END_REF][START_REF] Van Hoeve | On Global Warming: Flow-based Soft Global Constraints[END_REF], respectively. Other examples include W GCC var and W GCC val [START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], W Same var [START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], W SlidingSum var [START_REF] Lee | Modeling Soft Global Constraints as Linear Programs in Weighted Constraint Satisfaction[END_REF], W Regular var and W Regular edit [START_REF] Allouche | Decomposing Global Cost Functions[END_REF][START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], W EGCC var [START_REF] Lee | Modeling Soft Global Constraints as Linear Programs in Weighted Constraint Satisfaction[END_REF], W Disjunctive val and W Cumulative val [START_REF] Lee | Modeling Soft Global Constraints as Linear Programs in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Polytime Linear Global Cost Functions in Weighted Constraint Satisfaction[END_REF].

Tractable Projection-Safety

All soft local consistencies are based on the use of EPTs, shifting costs between two scopes. The size of the smallest scope used in a EPT is called the order (r) of the EPT. Such a EPT is called an r-EPT. It is directly related to the level of local consistency enforced: node consistency uses EPTs onto the empty scope (r = 0), arc consistencies use unary scopes (r = 1) whereas higher-order consistencies use larger scopes (r ≥ 2) [START_REF] Cooper | High-Order Consistency in Valued Constraint Satisfaction[END_REF]. In this section, we show that the order of the EPTs directly impacts the tractability of global cost function minimization.

To be able to analyze complexities in global cost functions, we first define the decision problem associated with the optimization problem min{W GCF (S, A 1 , . . . , A t )}.

IsBetterThan(W GCF(S, A 1 , . . . , A t ), m) Instance. A global cost function W GCF, a scope S with domains for the variables in S, values for the parameters A 1 , . . . , A t , and a fixed integer m. Question. Does there exist a tuple ∈ D S such that W GCF(S, A 1 , . . . , A t )( )<m?

We can then define the tractability of a global cost function. Definition 10. A global cost function W GCF(S, A 1 , . . . , A t ) is said to be tractable iff the problem IsBetterThan(W GCF(S, A 1 , . . . , A t ), m) is in P .

For a tractable global cost function W S =W GCF(S, A 1 , . . . , A t ), the time complexity of computing min{W S } is bounded above by a polynomial function in the size of the input, including the scope, the corresponding domains, the other parameters of the global cost function, and log(m).

We introduce tractable r-projection-safety global cost functions, which remain tractable after applying r-EPTs.

Definition 11. We say that a global cost function W GCF(S, A 1 , . . . , A t ) is tractable r-projection-safe iff:

• it is tractable and;

• any global cost functions that can be derived from W GCF(S, A 1 , . . . , A t ) by a series of r-EPTs is also tractable.

The tractability after r-EPTs depends on r. We divide the discussion of tractable r-projection-safety into three cases: r = 0, r ≥ 2 and r = 1. In the following, given a tractable global cost function W S , we denote by ∇ r (W S ) the global cost function resulting from the application of an arbitrary finite sequence of r-EPTs on W S .

Tractability and 0-EPTs

When r = 0, EPTs are performed to/from W ∅ . This kind of EPTs is used when enforcing Node Consistency (NC*) [START_REF] Larrosa | Solving Weighted CSP by Maintaining Arc Consistency[END_REF] but also in ∅-inverse consistency [START_REF] Zytnicki | Bounds Arc Consistency for Weighted CSPs[END_REF], and strong ∅-inverse consistency [START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF].

We show that if a global cost function is tractable, it remains tractable after applying such EPTs.

Theorem 1. Every tractable global cost function is tractable 0-projection-safe.

Proof. Consider a tractable global cost function W S = W GCF (S, A 1 , . . . , A t ). Clearly, W S and ∇ 0 (W S ) only differ by a constant, i.e. there exists α -and α + , where α -, α + ∈ {0, . . . , }, such that:

∇ 0 (W S )( ) = W S ( ) ⊕ α + α -, for all ∈ D S If W S ( ) = min{W S } for some ∈ D S , then ∇ 0 (W S )( ) = min{∇ 0 (W S )}. If W S is tractable, so is ∇ 0 (W S ).

Tractability and EPTs of order greater than 2

When r ≥ 2, EPTs are performed to/from r-arity cost functions. This is required for enforcing higher order consistencies and is used in practice in ternary cost functions processing [START_REF] Sánchez | Mendelian Error Detection in Complex Pedigrees using Weighted Constraint Satisfaction Techniques[END_REF] and complete k-consistency [START_REF] Cooper | High-Order Consistency in Valued Constraint Satisfaction[END_REF].

If arbitrary sequences of r-EPTs are allowed, we show that tractable global cost functions always become intractable after some sequence of r-EPT applications, where r ≥ 2.

Theorem 2. Any tractable global cost function W GCF(S, A 1 , . . . , A t ) returning finite costs is not tractable r-projection-safe for r ≥ 2, unless P = N P .

Proof. Let us first define the binary constraint satisfaction problem ArityTwoCSP as follows.

ArityTwoCSP(X , W h ) Instance. A CSP instance (X , W h ), where every constraint C h S ∈ W h involves two variables, i.e. |S| = 2. Question. Is the CSP (X , W h ) satisfiable?

ArityTwoCSP is NP-hard as graph coloring can be solved through a direct modeling into ArityTwoCSP. We reduce the problem ArityTwoCSP(X , W h ) to the problem IsBetterThan(∇ 2 (W X ), ), where W X = W GC(X , A 1 , . . . , A t ) is an arbitrary global cost function using only finite costs. We first construct a CFN (X , W ∪ {W X }, ). The upper bound is a sufficiently large integer such that > W X ( ) for every ∈ D S , which is always possible given that W X remains finite. This technical restriction is not significant: if a global cost function W S maps some tuples to infinity, we can transform it to another cost function W S such that the infinity costs are replaced by a sufficiently large integer p such that p max{W S ( ) | ∈ D S ∧ W S ( ) = +∞}. The cost functions W S ∈ W \ {W X } are defined as follows:

W S ( ) = 0, if is accepted by C h S ∈ W h ; , otherwise
From the CFN, ∇ 2 can be defined as follows: for each forbidden tuple [S] in each C h S ∈ W h , we add an extension of from W S to W X with respect to [S] into ∇ 2 . Under this construction, ∇ 2 (W X )( ) can be represented as:

∇ 2 (W X )( ) = W X ( ) ⊕ W S ∈W W S ( [S]) For a tuple ∈ D X , ∇ 2 (W X )( ) = iff is forbidden by some C h S in W h . As a result IsBetterThan(∇ 2 (W X ), ) is satisfiable iff ArityTwoCSP(X , W h ) is satisfiable. As ArityTwoCSP is NP-hard, IsBetterThan(∇ 2 (W GC),
) is not polynomial, unless P = N P . Hence, ∇ 2 (W GC) is not tractable, and then, W GC is not tractable 2projection-safe, unless P = N P .

Tractability and 1-EPTs

When r = 1, 1-EPTs cover 1-projections and 1-extensions, which are the backbone of the consistency algorithms of (G)AC* [START_REF] Larrosa | Solving Weighted CSP by Maintaining Arc Consistency[END_REF][START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], FD(G)AC* [START_REF] Larrosa | In the Quest of the Best Form of Local Consistency for Weighted CSP[END_REF][START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], (weak) ED(G)AC* [START_REF] De Givry | Existential Arc Consistency: Getting Closer to Full Arc Consistency in Weighted CSPs[END_REF][START_REF] Lee | A Stronger Consistency for Soft Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], VAC, and OSAC [START_REF] Cooper | Soft Arc Consistency Revisited[END_REF]. In these cases, tractable cost functions are tractable 1-projection-safe only under special conditions. For example, Lee and Leung define flow-based projection-safety based on a flow-based global cost function.

Definition 12 (Flow-based [START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF]). A global cost function W GCF (S, A 1 , . . . , A t ) is flow-based iff it can be represented as a flow network G such that the minimum cost among all maximum flows between a fixed source and a fixed destination is equal to min{W GCF (S, A 1 , . . . , A t )}.

Definition 13 (Flow-based projection safe [START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF]). A global cost function W GCF (S, A 1 , . . . , A t ) is flow-based projection-safe iff it is is flow-based, and is still flow-based following any sequence of 1-projections and 1-extensions.

Lee and Leung [START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF] further propose sufficient conditions for tractable cost functions to be flow-based projection-safe. Flow-based projection-safety implies tractable 1-projection-safety. We state the result in the following theorem. Proof. Follows directly from the tractability of the minimum cost flow algorithm.

However, tractable cost functions are not necessarily tractable 1-projection-safe. One example is W 2SAT, which is a global cost function derived from an instance of the polynomial 2SAT problem. Definition 14. Given a set of Boolean variables S, a set of binary clauses F , and a positive integer c, the global cost function W 2SAT(S, F, c) is defined as: [START_REF] Krom | The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary[END_REF]. However, it is not tractable 1-projection-safe.

W 2SAT (S, F, c)( ) = 0, if satisfies F c, otherwise W 2SAT is tractable, because the 2SAT problem is tractable
Theorem 4. W 2SAT is not tractable 1-projection-safe, unless P = N P .

Proof. Let us first define the WSAT-2-CNF problem.

WSAT-2-CNF

Instance. A 2-CNF formula F (a set of binary clauses) and a fixed integer k.

Question. Is there an assignment that satisfies all clauses in F with at most k variables set to true ?

WSAT-2-CNF was shown NP-hard in [31, page 69]. We reduce it to the problem IsBetterThan(∇ 1 (W 2SAT ), ). We construct a particular sequence of 1-projections and/or 1-extensions ∇ 1 such that the WSAT-2-CNF instance can be solved using W X = W 2SAT (X , F, k + 1) from the Boolean CFN N = (X , W ∪ {W X }, k + 1). W only contains unary cost functions W i , which are defined as follows:

W i (v) = 1, if v = true; 0, otherwise
Based on N , we construct ∇ 1 as follows: for each variable x i ∈ X , we add an extension of 1 from W i to W X with respect to the value true into ∇ 1 . As a result, a tuple with ∇ 1 (W X )( ) = k ≤ k contains exactly k variables set to true (because every x i = true incurs a cost of 1) and also satisfies F (or it would have cost k+1 = ). Thus, the WSAT-2-CNF instance with threshold k is satisfiable iff

IsBetterThan(∇ 1 (W X ), k + 1) is satisfiable. As WSAT-2-CNF is NP-hard, IsBetterThan(∇ 1 (W 2SAT ), k + 1) is not polynomial, unless P = N P . Hence, ∇ 1 (W 2SAT
) is not tractable, and then, W 2SAT is not tractable 1-projection-safe, unless P = N P .

When the context is clear, we use tractable projection-safety, projection and extension to refer to tractable 1-projection-safety, 1-projection and 1-extension respectively hereafter.

Polynomial DAG-Filtering

Beyond flow-based global cost functions [START_REF] Lee | Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], we introduce now an additional class of tractable projection-safe cost functions based on dynamic programming algorithms. As mentioned by Dasgupta et al. [START_REF] Dasgupta | Algorithms[END_REF], every dynamic programming algorithm has an underlying DAG structure.

Definition 15 (DAG).

A directed acylic graph (DAG) T = (V, E), where V is a set of vertices (or nodes) and E ⊆ V × V is a set of directed edges, is a directed graph with no directed cycles, and:

• An edge (u, v) ∈ E points from u to v, where u is the parent of v, and v is the child of u;

• A root of a DAG is a vertex with zero in-degree;

• A leaf of a DAG is a vertex with zero out-degree;

• An internal vertex of a DAG is any vertex which is not a leaf;

We now introduce the DAG filterability of a global cost function.

Definition 16 (DAG-filter).

A DAG-filter for a cost function W S is a DAG T = (V, E) such that:

• T is connected;

• V = {ω Si } i is a set of cost function vertices each with a scope S i , among which vertex W S is the root of T ;

• Each internal vertex ω Si in V is associated with an aggregation function f i that maps a multiset of costs {α j | α j ∈ [0 . . . ]} to [0 . . . ] and is based on an associative and commutative binary operator;

• For every internal ω Si ∈ V , the scope of ω Si is composed from its children's scopes:

S i = (ω S i ,ω S j )∈E S j
ω Si is the aggregation of its children:

ω Si ( ) = f i ({ω Sj ( [S j ]) | (ω Si , ω Sj ) ∈ E});
min is distributive over f i :

min{ω Si } = f i ({min{ω Sj } | (ω Si , ω Sj ) ∈ E}).
When a cost function W S has a DAG-filter T , we say that W S is DAG-filterable by T . Note that any cost function W S has a trivial DAG filter which is composed of a single vertex that defines W S as a cost table (with size exponential in the arity |S|).

In the general case, a DAG-filter (recursively) transforms a cost function into cost functions with smaller scopes until it reaches the ones at the leaves of a DAG, which may be trivial to solve. The (minimum) costs can then be aggregated using the f i functions at each internal vertex to get the resultant (minimum) cost, through dynamic programming. However, further properties on DAG-filters are required to allow for projections and extensions to operate on the DAG structure.

Definition 17 (Safe DAG-filter). A DAG-filter T = (V, E) for a cost function W S is safe iff:

• projection and extension are distributive over f i , i.e. for a variable x ∈ S, a cost α and a tuple ∈ D S ,

-ω Si ( [S i ]) ⊕ ν x,Si (α) = f i ({ω S k ( [S k ]) ⊕ ν x,S k (α) | (ω Si , ω S k ) ∈ E}), and; -ω Si ( [S i ]) ν x,Si (α) = f i ({ω S k ( [S k ]) ν x,S k (α) | (ω Si , ω S k ) ∈ E}),
where the function ν is defined as:

ν x,Sj (α) = α, if x ∈ S j , 0, otherwise.
The requirement of a distributive f i with respect to projection and extension at each vertex in T implies that the structure of the DAG is unchanged after projections and extensions. Both operations can be distributed down to the leaves. We formally state this as the following theorem. Given a variable x, with a value a ∈ D(x), and a cost function W S , we denote as W S the cost function obtained by the application of Project(S, {x}, (v), α) on W S if x ∈ S or W S otherwise.

Theorem 5. For a cost function W S with a safe DAG-filter T = (V, E), W S has a safe DAG-filter T = (V , E ), where each ω Si ∈ V is defined as:

ω Si = ω Si ν x,S k (α), if ω Si is a leaf of T , ω Si , otherwise.
and

(ω Si , ω S k ) ∈ E iff (ω Si , ω S k ) ∈ E, i.e.
T is isomorphic to T . Moreover, both ω Si ∈ V and ω Si ∈ V are associated with the same aggregation function f i .

Proof. Follows directly from Definition 17.

Two common choices for f i are ⊕ and min, with which distributivity depends on how scopes intersect. In the following, we show that the global cost function is safely DAG-filterable if the internal vertices that are associated with ⊕ have children with nonoverlapping scopes, and those associated with min have children with identical scopes. Proposition 2. Any DAG-filter T = (V, E) for a cost function W S such that

• each ω Si ∈ V is associated with the aggregation function f i = ; • for any distinct ω Sj , ω S k ∈ V , which are children of ω Si , S j ∩ S k = ∅. is safe.
Proof. We need to show that min, projection and extension are distributive over ⊕. Since the scopes of the cost functions do not overlap, min is distributive over ⊕. We further show the distributivity with respect to projection ( ), while extension (⊕) is similar. We consider an internal vertex ω Si ∈ V . Given a variable x ∈ S i , a cost α, and a tuple ∈ D S , since the scopes of the cost functions {ω S k | (ω Si , ω S k ) ∈ E} are disjoint, there must exist exactly one cost function ω Sj such that x ∈ S j , i.e.:

ω Si ( ) α = (ω Sj ( [S j ]) α) ⊕ k =j∧(ω S i ,ω S k )∈E ω S k ( [S k ]) = (ω S i ,ω S k )∈E (ω S k ( [S k ]) ν x,S k (α))
The result follows.

Proposition 3. Any DAG-filter T = (V, E) for a cost function W S such that • each ω Si ∈ V is associated with the aggregation function f i = min; • ∀ω Sj ∈ V , which are children of ω Si , S j = S i . is safe.
Proof. Since the scopes are completely overlapping, min{ω Si } = min

∈D S i { min (ω S i ,ω S k )∈E {ω S k ( )}} = min (ω S i ,ω S k )∈E { min ∈D S k {ω S k ( )}} = f i ({min{ω S k } | (ω Si , ω S k ) ∈ E})
It is trivial to see that projection and extension are distributive over f i . The result follows.

We are now ready to define polynomial DAG-filterability of global cost functions. As safe DAG-filters can be exponential in size, we need to restrict to safe DAG-filters of polynomial size by restricting the size of the DAG to be polynomial and by bounding the arity of the cost functions at the leaves of the DAG.

Definition 18 (Polynomial DAG-filterability). A global cost function

W GCF (S, A 1 , . . . , A t ) is polynomially DAG-filterable iff 1. any instance W S of W GCF (S, A 1 , . . . , A t ) has a safe DAG-filter T = (V, E) 2.
where |V | is polynomial in the size of the input parameters of W GCF (S, A 1 , . . . , A t ); 3. each leaf in V is a unary cost function, and 4. each aggregation function f i associated with each internal vertex is polynomial-time computable.

Dynamic programming can compute the minimum of a polynomially DAG-filterable cost function in a tractable way. Projections and extensions to/from such cost functions can also be distributed to the leaves in T . Thus, polynomially DAG-filterable global cost functions are tractable and also tractable projection-safe, as stated below. Theorem 6. A polynomially DAG-filterable global cost function W GCF (S, A 1 , . . . , A t ) is tractable.

Proof. Let W S be any instance of W GCF (S, A 1 , . . . , A t ), and T = (V, E) be a safe DAG-filter for W S . Algorithm 4 can be applied to compute min{W S }. The algorithm uses a bottom-up memoization approach. Algorithm 4 first sorts V topologically at line 2. After sorting, all the leaves will be grouped at the end of the sorted sequence, which is then processed in the reversed order at line 3. If the vertex is a leaf, the minimum is computed and stored in the table Min at line 5. Otherwise, its minimum is computed by aggregating {Min[ω S k ] | (ω Si , ω S k ) ∈ E}, which have been already computed, by the function f i at line 6. Line 7 returns the minimum of the root node.

The computation is tractable. Leaves being unary cost functions, line 5 is in O(d), where d is the maximum domain size. For other vertices, line 6 calls f i , which is assumed to be polynomial time. The result follows. Note that Algorithm 4 computes the minimum from scratch each time it is called. In practice, querying the minimum of cost function W S when x i is assigned to v for different values v can be done more efficiently with some pre-processing. We define

M in + [ω Sj , x i , v] that stores min{ω Sj ( ) | x i ∈ S j ∧ [x i ] = v}. M in + [ω Sj , x i , v]
can be computed similarly to Algorithm 4 by using the equation:

M in + [ω Sj , x i , v] =    ω Sj (v), if ω Sj is a leaf of T and S j = {x i } min{ω Sj }, if ω Sj is a leaf of T and S j = {x i } f j ({M in + [ω S k , x i , v]) | (ω Si , ω S k ) ∈ E}), otherwise
Whenever we have to compute the minimum for

x i = v, we simply return M in + [W S , x i , v]. Computing M in + [W S , x i , v
] is equivalent to running Algorithm 4 nd times, where n is the number of variables and d the maximum domain size. However, this can be reduced by incremental computations exploiting the global constraint semantics, as illustrated on the W Grammar var global cost function in Section 5.

14

We now show that a polynomially DAG-filterable cost function is tractable projectionsafe. The following lemma will be useful. For a variable x ∈ S and a value v ∈ D(x), we denote as W GCF (S, A 1 , . . . , A t ) the cost function obtained by applying Project(S, {x}, (v), α) to a global cost function W GCF (S, A 1 , . . . , A t ).

Lemma 1. If a global cost function W GCF (S, A 1 , . . . , A t ) is polynomially DAG-filterable, W GCF (S, A 1 , . . . , A t ) is polynomially DAG-filterable.
Proof. Suppose W GCF (S, A 1 , . . . , A t ) is polynomially DAG-filterable. Then any instance W S of it has a safe filtering DAG T = (V, E). By Theorem 5, we know that W S , the corresponding instance of W GCF (S, A 1 , . . . , A t ), has a safe DAG filter T , which is isomorphic to T , has polynomial size, and polynomial-time computable f i associated with each internal vertex. The leaves of T only differ from those of T by a constant. The result follows.

Theorem 7. A polynomially DAG-filterable global cost function W GCF (S, A 1 , . . . , A t ) is tractable projection-safe.

Proof. Follows directly from Theorem 6 and Lemma 1.

As shown by Theorem 7, a polynomially DAG-filterable cost function W S remains polynomially DAG-filterable after projection or extension. Algorithm 5 shows how the projection is performed from W S and W i , where x i ∈ S. Lines 2 to 4 modify the leaves of the filtering DAG, as suggested by Theorem 5.

Lines 4 to 8 in Algorithm 5 show how incrementality can be achieved. If W i or D(x i ), x i ∈ S, are changed we update the entry M in[ω Si ] at line 4, which corresponds to the leaf ω Si , where x i ∈ S i . The change propagates upwards in lines 7 and 8, updating all entries related to the leaf ω Si . The table F W can be updated similarly.

Precondition: W S is polynomially DAG-filterable with the filtering DAG We have presented a new class of tractable projection-safe global cost functions. Algorithm 4 gives an efficient algorithm to compute the minimum cost. In the next Section, we give an example of such a global cost function. More examples can be found in the associated technical report [START_REF] Allouche | Tractability and Decompositions of Global Cost Functions[END_REF].

T = (V, E); Procedure Project (S, {x i }, (v), α) W i (v) := W i (v) ⊕ α ; 1 foreach ω Sj ∈ V such that S j = {x i } and ω Sj is a leaf of T do 2 ω Sj (v) := ω Sj (v) α ; 3 Min[ω Sj ] := min{ω Sj } ; 4 Topologically sort V ; 5 foreach ω Sj ∈ V in reverse topological order do 6 if ω Sj is not a leaf and x i ∈ S j then 7 Min[ω Sj ] := f i ({Min[ω S k ] | (ω Sj , ω S k ) ∈ E}) ;

A Polynomially DAG-filterable Global Cost Function

In the following, we show that W Grammar var is polynomially DAG-filterable using the results from the previous section. Other examples of polynomially DAG-filterable global cost functions can be found in the extended version [START_REF] Allouche | Tractability and Decompositions of Global Cost Functions[END_REF].

W Grammar var is the cost function variant of the softened version of the hard global constraint Grammar [START_REF] Kadioglu | Grammar Constraints[END_REF] defined based on a context-free language. Definition 19. A context-free language L(G) is represented by a context-free grammar G = (Σ, N, P, A 0 ), where:

• Σ is a set of terminals; • N is a set of non-terminals; • P is a set of production rules from N to (Σ ∪ N ) * , where * is the Kleene star, and;

• A 0 ∈ N is a starting symbol.
A string τ belongs to L(G), written as τ ∈ L(G) iff τ can be derived from G.

Without loss of generality, we assume that (1) the context-free language L(G) does not contain cycles, and (2) the strings are always of fixed length, representing values in tuples.

Assume S = {x 1 , . . . , x n }. We define τ to be a string formed by a tuple ∈ D S , where the i th character of τ is [x i ]. The hard constraint grammar(S, G) authorizes a tuple ∈ D S if τ ∈ L(G) [START_REF] Kadioglu | Grammar Constraints[END_REF]. Using the violation measure var by Katsirelos et al. [START_REF] Katsirelos | The Weighted GRAMMAR Constraints[END_REF], the W Grammar var cost function is defined as follows.

Definition 20 (W Grammar var [START_REF] Katsirelos | The Weighted GRAMMAR Constraints[END_REF]). Given a context-free grammar G = (Σ, N, P, A 0 ). W Grammar var (S, G) returns min{H(τ , τ i ) | τ i ∈ L(G)} for each tuple ∈ D S , where H(τ 1 , τ 2 ) returns the Hamming distance between τ 1 and τ 2 .

Example 1.

Consider S = {x 1 , x 2 , x 3 , x 4 }, where D(x i ) = {a, b, c} for i = 1 . . . 4.
Given the grammar G = ({a, b, c}, {A 0 , A, B, C}, P, S) with the following production rules.

A 0 → AA A → a | AA | BC B → b | BB C → c | CC
The cost returned by W Grammar var (S, G)( ) is 1 if = (c, a, b, c). The assignment of x 1 needs to be changed so that L(M ) accepts the corresponding string aabc.

Theorem 8. W Grammar var (S, G) is a polynomially DAG-filterable and thus tractable projection-safe global cost function.

Proof. We adopt the dynamic programming approach similar to the modified CYK parser [START_REF] Katsirelos | The Weighted GRAMMAR Constraints[END_REF]. Without loss of generality, we assume G is in Chomsky normal form, i.e. each production rule always has the form A → α or A → BC, where A ∈ N , B, C ∈ N \ {A 0 } and α ∈ Σ. Define ω A Si,j = W Grammar var (S i,j , G A ), where i ≤ j, S i,j = {x i . . . x j } ⊆ S, and

G A = (Σ, N, P, A) for A ∈ N . By definition, W Grammar var (S, G)( ) = ω A0 S1,n ( )
The base cases ω A Si,i is defined as follows. Define Σ A = {α | A → α} to be the set of terminals that can be yielded from A.

ω A Si,i ( ) = min{U α i ( [x i ]) | (A → α) ∈ P }, if Σ A = ∅ , otherwise (1)
The unary cost function

U α i ( [x i ]
) is defined as follows.

U α i (v) = 0, if v = α; 1, otherwise (2)
Other cost functions ω A Si,j , where i < j, are defined as follows. Let N A = {(B, C) | A → BC} be the set of pairs of non-terminals that are yielded from A.

ω A Si,j ( ) = min k=i,...j-1 {ω B S i,k ( [S i,k ]) ⊕ ω C S k+1,j ( [S k+1,j ]) | (A → BC) ∈ P }, if N A = ∅ , otherwise (3)
The associated filtering DAG (V, E) is illustrated in Figure 1 on Example 1. In Figure 1, leaves are indicated by double circles, corresponding to the unary cost function in equation 2. Vertices with min or ⊕ aggregators are indicated by rectangles and circles respectively, corresponding to cost functions ω A Si,j in equation 3 if i = j, or equation 1 otherwise. As shown in Figure 1, the root node W Grammar is first split by the production rule A 0 → AA. One of its children ω A S1,1 leads to the leaf U a 1 according to the production rule A → a. The DAG uses only ⊕ or min as aggregations and they satisfy the preconditions that allow to apply propositions 2 and 3. The cost function is therefore safely DAG-filterable. Moreover, the corresponding DAG (V, E) has size 3 ) polynomial in the size of the input. The leaves are unary functions {U α i } and by Theorem 7, the result follows.

|V | = O(|P | • |S|
Note that Theorem 8 also gives a proof that W Regular var is tractable projectionsafe. Indeed, a finite state automaton, defining a regular language, can be transformed into a grammar with the number of non-terminals and production rules polynomial in the number of states in the automaton. Then, W Among var is also tractable projectionsafe since the tuples satisfying an Among global constraint can be represented using a compact finite state counting automaton [START_REF] Beldiceanu | Reformulation of global constraints based on constraints checkers[END_REF].

... U c 4 U b 2 ... ω A S2,4 ω B S1,1 ω A S1,1 ω B S2,2 ... ω A S3,4 U c 2 U b 3 U a 1 U b 1 ω C S2,2 ω C S4,4 ω B S3,3 ... ω A0 S1,4 = W Grammar var ω B S2,3 ω A S1,2
O(nd • |Σ| + n • |P | + n 3 • |P |) = O(nd • |Σ| + n 3 • |P |).
As for incrementality, Algorithm 7 gives the pre-processing performed on top of Algorithm 6, based on the weighted CYK propagator used in Katsirelos et al. [START_REF] Katsirelos | The Weighted GRAMMAR Constraints[END_REF]. We compute the table f at line 1 using Algorithm 6. Then we compute the table F at lines 8 to 16 using the top-down approach. For each production A → A 1 A 2 , lines 14 and 16 compute the maximum possible costs from their neighbors. An additional table marked[i, j, A] is used to record whether the symbol A is accessible when deriving substrings at positions i to j in G. Each time we need to compute the minimum for

x i = v, we just return min{U α i (v) F [i, i, A] ⊕ f [0, n -1, A 0 ] | (A → v) ∈ P ∧ marked[i, i, A]}, or if such production does not exist.
11 foreach A ∈ N do f [i, j, A] := ; 12 foreach (A, A 1 , A 2 ) such that (A → A 1 A 2 ) ∈ P do 13 for k := i to j -1 do 14 f [i, j, A] := min{f [i, j, A], f [i, k, A 1 ] ⊕ f [k + 1, j, A 2 ]} ; 15 return f [1, n, A 0 ]; 16
Algorithm 6: Finding the minimum of W Grammar var Algorithm 8 shows how projection is performed between W Grammar var and W p , and how incrementally can be achieved. Line 3 modifies the leaves U c p for each c ∈ Σ, while lines 4 and 5 update the corresponding entries in the tables u and f respectively. The change is propagated up in f at line 6, corresponding to derivation of sub-strings with positions from p to the end in G.

In this section, we have seen how the minimum of a polynomially DAG-filterable global cost function can be computed efficiently, leading to efficient soft local consistency enforcement. However, each newly implemented cost function requires to build a corresponding DAG structure with a dedicated dynamic programming algorithm.

In the next section, we show that, in some cases, it is also possible to avoid this by directly decomposing a global cost functions into a CFN in such a way that local consistency enforcement will emulate dynamic programming, avoiding the need for dedicated enforcement algorithms.

Decomposing Global Cost Functions into CFNs

In CSPs, some global constraints can be efficiently represented by a logically equivalent subnetwork of constraints of bounded arities [START_REF] Bessière | To be or not to be ... a global constraint[END_REF][START_REF] Bessière | Constraint propagation[END_REF], and are said to be decomposable. Similarly, we will show that some global cost functions can be encoded as a sum of bounded arity cost functions. The definition below applies to any cost function, including constraints, extending the definition in [START_REF] Bessière | To be or not to be ... a global constraint[END_REF] and [START_REF] Bessière | Constraint propagation[END_REF].

Procedure GrammarPreCompute(S, G)

F [1, n, A 0 ] := GrammarMin(S, G); for i := 1 to n -len + 1 do Definition 21 above allows for the use of extra variables E, which do not appear in the original cost function scope and are eliminated by minimization. We assume, without loss of generality, that every extra variable x ∈ E is involved in at least two cost functions in the decomposition. 1 Clearly, if W GCF (S, A 1 , . . . , A k ) appears in a CFN P = (X , W, ) and decomposes into (S ∪ E, F, ), the optimal solutions of P can directly be obtained by projecting the optimal solutions of the CFN P = (X ∪ E, W \ {W GCF (S, A 1 , . . . , A k )} ∪ F, ) on X .

9 j := i + len -1 ; 10 foreach (A, A 1 , A 2 ) such that (A → A 1 A 2 ) ∈ P ∧ marked[i, j, A] do 11 for k := i to j do 12 marked[i, k, A 1 ] := true; 13 F [i, k, A 1 ] := max(F [i, k, A 1 ], F [i, j, A] f [k + 1, j, A 2 ]); 14 marked[k + 1, j, A 2 ] := true; 15 F [k + 1, j, A 2 ] := max(F [k + 1, j, A 2 ], F [i, j, A] f [i, k, A 1 ]);

Building network-decomposable global cost functions

A global cost function can be shown to be network-decomposable by exhibiting a bounded arity network decomposition of the global cost function. There is a simple way of deriving network-decomposable cost functions from known decomposable global constraints. The process goes directly from a known decomposable global constraint to a network-decomposable global cost function and does not require to use an intermediate We say that the cost function W S is a relaxation of W S if for all ∈ D S , W S ( ) ≤ W S ( ). We then write W S ≤ W S . From a network-decomposable global constraint, it is possible to define an associated network-decomposable global cost function by relaxing every constraint in the decomposition.

Procedure GrammarProject (S, {x p }, (v), α) W p (v) := W p (v) ⊕ α ; 1 for c ∈ Σ do 2 U c p (v) := U c p (v) α;
Theorem 10. Let GC(S, A 1 , . . . , A k ) be a global constraint that p-network decomposes into a classical constraint network (S ∪ E, F, ) and f θ be a function parameterized by θ that maps every

C T ∈ F to a cost function f θ (C T ) such that f θ (C T ) ≤ C T . The global cost function W GCF (S, A 1 , ..., A k , f θ )( ) = min ∈D S∪E [S]= C T ∈F f θ (C T )( [T ])
is a relaxation of GC(S, A 1 , . . . , A n ), and is p-network-decomposable by construction.

Proof. Since (S ∪ E, F) is a network-decomposition of GC(S, A 1 , ..., A k ), for any tuple ∈ D S , GC(S, A 1 , ..., A k )( ) = 0 if and only if min ∈D S∪E , [S]= C T ∈F C T ( [T ]) = 0. Let ∈ D S∪E be a tuple where this minimum is reached. This implies that ∀C T ∈ F,

C T ( [T ]) = 0. Since f θ (C T ) ≤ C T , f θ (C T )( [T ]) = 0. Therefore C T ∈F f θ (C T )( [T ]) = 0 and W GCF (S, A 1 , . . . , A k , f θ )( ) = 0.
Moreover, the global cost function is p-networkdecomposable by construction.

Theorem 10 allows to immediately derive a long list of network decomposable global cost functions from existing network decompositions of global constraints such as AllDifferent, Regular [START_REF] Pesant | A Regular Language Membership Constraint for Finite Sequences of Variables[END_REF], Among and Stretch [START_REF] Bessière | Reformulating global constraints: the SLIDE and REGULAR constraints[END_REF]. The parameterization through f θ also allows a lot of flexibility.

Example 2. Consider the softened variant W AllDifferent dec (S) of the global constraint AllDifferent(S) constraint using the decomposition violation measure where the cost of an assignment is the number of pairs of variables taking the same value [START_REF] Petit | Specific Filtering Algorithm for Over-Constrained Problems[END_REF]. It is well known that AllDifferent decomposes into a set of n.(n-1) 2 binary difference constraints. Similarly, the W AllDifferent dec (S) cost function can be decomposed into a set of n.(n-1) cost 1 iff the two involved variables have the same value and 0 otherwise. In these cases, no extra variable is required.

AllDifferent can be softened in a different way. Take an arbitrary graph G = (V, E) over V , and consider the violation measure where the cost of an assignment is the number of pairs of variables in E taking the same value. This gives rise to a global cost function W AllDifferent f G (V ) that allows a zero cost assignment if and only if G is colorable, which is an NP-hard problem. Enforcing any soft arc consistency on that single global cost function will be intractable as well since it requires to compute the minimum of the cost function. Instead, enforcing soft arc consistencies on the networkdecomposition into binary cost functions will obviously be polynomial but will achieve a lower level of filtering.

Local Consistency and Network-Decompositions

As we have seen with the W AllDifferent(V, f G ) global cost function, the use of network-decompositions instead of a monolithic variant has both advantages and drawbacks. Thanks to local reasoning, a decomposition may be filtered more efficiently, but this may hinder the level of filtering achieved. In CSP, it was observed that the structure of the decomposition has an impact on the level of consistency achieved when filtering the decomposition.

Before going further, we give some extra definitions that are useful to characterize structure of decompositions. The hypergraph (X, E) of a CFN (X , W, ) has one vertex per variable x i ∈ X and one hyperedge for every scope S such that ∃W S ∈ W. The incidence graph of a hypergraph (X, E) is a bipartite graph G = (X ∪ E, E H ) where {x i , e j } ∈ E H iff x i ∈ X, e j ∈ E and x i belongs to the hyperedge e j . A hypergraph (X, E) is Berge-acyclic iff its incidence graph is acyclic.

In CSP, it is known that if the decomposition is Berge-acyclic, then enforcing GAC on the decomposition enforces GAC on the global constraint itself [START_REF] Beeri | On the Desirability of Acyclic Database Schemes[END_REF]. We now show that a similar result can be obtained for cost functions using either a variant of Directional Arc Consistency or Virtual Arc Consistency (VAC), whose definitions are given in the two subsections below.

Berge-acyclicity and directional arc consistency

In this section, we will show that enforcing directional arc consistency on a Bergeacyclic network-decomposition of a cost function or on the original global cost function yields the same cost distribution on the last variable and therefore the same lower bound (obtained by node consistency) provided a correct variable ordering is used.

Directional Arc Consistency has been originally defined on binary networks. We define Terminal DAC (or T-DAC) which generalizes Directional Arc Consistency [START_REF] Cooper | Reduction operations in fuzzy or valued constraint satisfaction[END_REF] by removing the requirement of having binary scopes.

Definition 22 (T-DAC).

Given a CFN N = (X , W, ) a total order ≺ over variables:

• For a cost function W S ∈ W + , a tuple ∈ D S is a full support for a value a ∈ D(x i ) of x i ∈ S iff W S ( ) xj ∈S,j =i W j ( [x j ]) = 0. • A variable x i ∈ S is star directional arc consistent (DAC*) for W S iff -x i is NC*; -each value v i ∈ D(x i ) has a full support for W S .
• N is Terminal Directional Arc Consistent (T-DAC) w.r.t. the order ≺ iff for all cost functions W S ∈ W + , the minimum variable in S is DAC* for W s .

To enforce T-DAC on a cost function W S , it suffices to first shift the cost of every unary cost function W i , i ∈ S inside W S by applying Project(S, {x i }, (a), -W i (a)) for every value a ∈ D i . Let x j be the minimum variable in S according to ≺, one can then apply Project(S, {x j }, (b), α) for every value b ∈ D(x j ) with α = min ∈D S , [xj ]=b W S ( ). Let be a tuple where this minimum is reached. Then either α = and the value will be deleted, or is a full support for b ∈ D(x j ): W S ( ) xi∈S,i =j W i ( [x i ]) = 0. This support can only be broken if for some unary cost function W i , i ∈ S, i = j, W i (a) increases for some value a ∈ D(x i ). Since j is minimum, i j.

To enforce T-DAC on a CFN (X , W, ), one can simply sort W in a decreasing order of the minimum variable in the scope of each cost function, and apply the previous process on each cost function, successively. When a cost function W S is processed, all the cost functions whose minimum variable is larger than the minimum variable of S have already been processed, which guarantees that none of the established full supports will be broken in the future. Proof. Consider the decomposed network N and I N = (S ∪ E ∪ F, E I ) its incidence graph. As N is Berge-acyclic we know that I N is a tree whose vertices are the variables and the cost functions of N . We root I N in a variable of S. The neighbors (parent and children, if any) of cost functions W T are the variables in T . The neighbors of a variable x i are the cost functions involving x i . Consider any topological ordering of the vertices of I N . This ordering induces a variable ordering (x i1 , . . . , x in ), x in ∈ S which is used to enforce T-DAC on N . Notice that for any cost function W T ∈ F, the parent variable of W T in I N appears after all the other variables of T .

Consider a value a ∈ D(x in ) of the root. Since NC* is enforced, W xi n (a) < . Let W T be any child of x in and a full support of value a on W T . We have

W xi n (a) = W T ( ) xi∈T W xi ( [x i ]), which proves that W T ( ) = 0 and ∀x i ∈ T, i = i n , W xi ( [x i ]) = 0.
I N being a tree, we can inductively apply the same argument on all the descendants of x in until leaves are reached, proving that the assignment (x in = a) can be extended to a complete assignment with cost W xi n (a) in N . In both cases, W xi n (a) is the cost of an optimal extension of (x in = a) in N .

Suppose now that we enforce T-DAC using the previous variable ordering on the undecomposed sub-network (S, {W GCF (S,

A 1 , . . . , A k )} ∪ {W xi } xi∈S ). Let be a full support of value a ∈ D(x in ) on W GCF(S, A 1 , . . . , A k ). By definition, W xi n (a) = W GCF (S, A 1 , . . . , A k )( ) xi∈S W xi ( [x i ]) which proves that W xi n (a)
is the cost of an optimal extension of (x in = a) on (S, {W GCF (S, A 1 , . . . , A k )} ∪ {W xi } xi∈S ). By definition of decomposition, and since x in ∈ E, this is equal to the cost of an optimal extension of (x in = a) in N .

T-DAC has therefore enough power to handle Berge-acyclic network-decompositions without losing any filtering strength, provided a correct order is used for applying EPTs. In this case, T-DAC emulates a simple form of dynamic programming on the networkdecomposition.

Example 3. Consider the Regular ({x 1 , . . . , x n }, M ) global constraint, defined by a (not necessarily deterministic) finite automaton M = (Q, Σ, δ, q 0 , F ), where Q is a set of states, Σ the emission alphabet, δ a transition function from Σ × Q → 2 Q , q 0 the initial state and F the set of final states. As shown in [START_REF] Bessière | SLIDE: A Useful Special Case of the CARDPATH Constraint[END_REF], this constraint decomposes into a constraint network ({x 1 , . . . , x n } ∪ {Q 0 , . . . , Q n }, C) where the extra variables Q i have Q as their domain. The set of constraints C in the network decomposition contains two unary constraints restricting Q 0 to {q 0 } and Q n to F and a sequence of identical ternary constraints c {Qi,xi+1,Qi+1} each of which authorizes a triple (q, s, q ) iff q ∈ δ(q, s), thus capturing δ. A relaxation of this decomposition may relax each of these constraints. The unary constraints on Q 0 and Q n would be replaced by unary cost functions λ Q0 and ρ Qn stating the cost for using every state as either an initial or final state while the ternary constraints would be relaxed to ternary cost functions σ {Qi,xi+1,Qi+1} stating the cost for using any (q, s, q ) transition.

This relaxation precisely corresponds to the use of a weighted automaton M W = (Q, Σ, λ, σ, ρ) where every transition, starting and finishing state has an associated, possibly intolerable, cost defined by the cost functions λ, σ and ρ [START_REF] Culik | Image Compression Using Weighted Finite Automata[END_REF]. The cost of an assignment in the decomposition is equal, by definition, to the cost of an optimal parse of the assignment by the weighted automaton. This defines a W Regular(S, M W ) global cost function which is parameterized by a weighted automaton. As shown in [START_REF] Katsirelos | The Weighted GRAMMAR Constraints[END_REF], a weighted automaton can encode the Hamming and Edit distances to the language of a classical automaton. We observe that the hypergraph of the decomposition of W Regular is Berge-acyclic. Thus, contrary to the AllDifferent example, where decomposition was hindering filtering, T-DAC on the W Regular network-decomposition achieves T-DAC on the original cost function.

It should be pointed out that T-DAC is closely related to mini-buckets [START_REF] Dechter | Mini-buckets: A general scheme for bounded inference[END_REF] and Theorem 11 can easily be adapted to this scheme. Mini-buckets perform a weakened form of variable elimination: when a variable x is eliminated, the cost functions linking x to the remaining variables are partitioned into sets containing at most i variables in their scopes and at most m functions (with arity > 1). If we compute mini-buckets using the same variable ordering, with m = 1 and unbounded i, we will obtain the same unary costs as T-DAC on the root variable r, with the same time and space complexity. Mini-buckets can be used along two main recipes: precomputed (static) mini-buckets do not require update during search but restrict search to one static variable ordering; dynamic mini-buckets allow for dynamic variable ordering (DVO) but suffer from a lack of incrementality. Soft local consistencies, being based on EPTs, always yield equivalent problems, providing incrementality during search and are compatible with DVO.

Berge-acyclicity and virtual arc consistency

Virtual Arc Consistency offers a simple and direct link between CSPs and CFNs which allows to directly lift CSP properties to CFNs, under simple conditions. Definition 23 (VAC [START_REF] Cooper | Soft Arc Consistency Revisited[END_REF]). Given a CFN N = (X , W, ), we define the constraint network Bool(N ) as the CSP with the same set X of variables with the same domains, and which contains, for each cost function W S ∈ W, |S| > 0, a constraint c S with the same scope, which exactly forbids all tuples ∈ D S such that W S ( ) = 0. A CFN N is said to be Virtual Arc Consistent (VAC) iff the arc consistent closure of the constraint network Bool(N ) is non empty. Proof. Enforcing VAC on the CFN N = (S ∪ E, F ∪ {W xi } xi∈S , ) does not modify the set of scopes as it only performs 1-EPTs (See Definition 4). Hence it yields an equivalent problem N such that Bool(N ) has the same hypergraph as Bool(N ). Since N has a Berge acyclic structure, this is also the case for Bool(N ) and Bool(N ). Now, Bergeacyclicity is a situation where arc consistency is a decision procedure. We can directly make use of Proposition 10.5 of [START_REF] Cooper | Soft Arc Consistency Revisited[END_REF], which states that if a CFN N is VAC and Bool(N ) is in a class of CSPs for which arc consistency is a decision procedure, N has an optimal solution of cost w ∅ .

Similarly, the network Q = (S, {W GCF (S, A 1 , . . . , A k )} ∪ {W xi } xi∈T , ) contains just one cost function with arity strictly above 1 and Bool(Q) will be decided by arc consistency. Enforcing VAC will therefore provide a CFN which also has an optimal solution of cost W ∅ . Finally, the networks N and Q have the same optimal cost by definition of a decomposition.

Given that VAC is both stronger and more expensive to enforce than DAC*, the added value of this theorem, compared to theorem 11, is that it does not rely on a variable ordering. Such order always exists but it is specific to each global cost function. Theorem 12 becomes interesting when a problem contains several global cost functions with intersecting scopes, for which theorem 11 may produce inconsistent orders.

Relation between DAG-filterability and Network-Decompositions

In this section, we show that Berge-acyclic network-decomposable global cost functions are also polynomially DAG-filterable.

Theorem 13. Let W GCF (S, A 1 , . . . , A k ) be a network-decomposable global cost function that decomposes into a CFN (S ∪ E, F, ) with a Berge-acyclic hypergraph. Then W GCF(S, A 1 , . . . , A k ) is polynomially DAG-filterable.

Proof. We consider the incidence graph of the Berge-acyclic hypergraph of the CFN (S ∪ E, F, ) and choose a root for it in the original variables S, defining a rooted tree denoted as I. This root orients the tree I with leaves being variables in S and E. In the rest of the proof, we denote by I(x i ) the subtree of I rooted in x i ∈ S ∪ E. Abusively, when the context is clear, I(x i ) will also be used to denote the set of all variables in the subtree.

The proof is constructive. We will transform I into a filtering DAG (actually a tree) of nodes that computes the correct cost min

∈D S∪E , [S]= W T ∈F W T ( [T ]
) and satisfies all the required properties of polynomial DAG-filters. To achieve this, we need to guarantee that the aggregation function f i = ⊕ is always used on cost functions of disjoint scopes, that f i = min is always applied on identically scoped functions and that sizes remain polynomial. We will be using three types of DAG nodes. A first type of node will be associated with every cost function W T ∈ F in the network-decomposition. Each cost function appears in I with a parent variable x i and a set of children variables among which some may be leaf variables. By the assumption that extra variables belong to at least two cost functions (see paragraph below Definition 21), leaf variables necessarily belong to S. We denote by leaf(T ) the set of leaf variables in the scope T . The first type of node aims at computing the value of the cost function W T combined with the unary cost functions on each leaf variable. This computation will be performed by a family of nodes U T , where ∈ D T -leaf(T ) is an assignment of non-leaf variables. Therefore, for a given cost function W T and a given assignment of non-leaf variables, we define a DAG node with scope leaf (T ):

U T ( ) = W T ( ∪ ) xj ∈leaf(T ) W xj ( [x j ])
These nodes will be leaf nodes of the filtering DAG. Given that all cost functions in I have bounded arity, these nodes have an overall polynomial size and can be computed in polynomial time in the size of the input global cost function.

Nodes of the second and third types are associated to every non-leaf variable x i in I. For every value a ∈ D(x i ), we will have a node ω a i with scope I(x i ) ∩ S. x i may have different children cost functions in I and we denote by W i the set of all the children cost functions of x i in I. For each W T ∈ W i , we will also have a DAG node ω i,a T with scope S i = (I(W T ) ∪ {x i }) ∩ S. Notice that even if these scopes may be large (ultimately equal to S for ω a i if x i is the root of I), these nodes are not leaf nodes of the filtering DAG and do not rely on an extensional definition, avoiding exponential space.

The aim of all these nodes is to compute the cost of an optimal extension of the assignment to the subtree I(W T ) (for ω i,a T ) or I(x i ) (for ω a i ). We therefore define:

ω a i ( ) = W T ∈Wi ω i,a T ( [S i ])
Indeed, if ω i,a T computes the cost of an optimal extension to the subtree rooted in W T , an optimal extension to I(x i ) is just the ⊕ of each optimal extension on each child, since the scopes S i do not intersect (I is a tree). The DAG node uses the ⊕ aggregation operator on non-intersecting scopes.

The definition of the DAG nodes ω i,a T is more involved. It essentially requires:

1. to combine the cost of W T with the unary cost functions on leaf variables in T (this is achieved by U T nodes) and costs of optimal extensions subtrees rooted in other non-leaf variables (this is achieved by ω b j nodes).

to eliminate in this function all extra variables in the scope

T except x i if x i ∈ E.
In this case, x i 's value will be set in and eliminated on higher levels.

If x i ∈ E or else if [x i ] = a, this leads to the following definition of ω i,a T ( ):

min ∈D T ∩E (x i ∈S∨ [x i ]=a) U ( ∪ )[T -leaf(T )] T ( [leaf(T )]) xj ∈(T -leaf(T )-{xi}) ω [xj ] j ( [S j ]) (4)
Otherwise (x i ∈ S and [x i ] = a), ω i,a T ( ) = . This captures the fact that there is no optimal extension of that extends (x i , a) since is inconsistent with x i = a.

If we consider the root variable x i ∈ S of I, the ω a i nodes provide the cost of a best extension of any assignment (if [x i ] = a) or otherwise. An ultimate root DAG node using the aggregation operator min over all these ω a i will therefore return the optimal extension of ∈ D S to all variables in I(x i ), including extra variables.

From equation 4, one can see that nodes ω i,a T use the aggregation operator min on intermediary nodes. These intermediary nodes combine the node U T and ω j with ⊕ which have non-intersecting scopes.

Overall all those nodes form a DAG (actually a tree). In this tree, every node with the aggregation operation ⊕ is applied to operands with non-intersecting scopes, as required in Property 2. Similarly, every node with the min aggregation operation is applied to functions whose scope is always identical, as required by Property 3. Note that the definitions of the ω a i and ω i,a T are linear respectively in the number of children of W T or x i respectively. So, we have a filtering DAG satisfying Definition 18.

For a global cost function which is Berge-acyclic network-decomposable, and therefore also polynomially DAG-filterable (as Theorem 13 shows), a natural question is which approach should be preferred. The main desired effect of enforcing local consistencies is that it may increase the lower bound W ∅ . From this point of view, Theorems 11 and 12 give a clear answer for a single global cost function.

• Since OSAC [START_REF] Cooper | Soft Arc Consistency Revisited[END_REF] is the strongest form of arc consistency (implying also VAC), the strongest possible lower bound will be obtained by enforcing OSAC on the network-decomposed global cost function. The size of the OSAC linear program being exponential in the arity of the cost functions, the bounded arities of the network decomposed version will define a polynomial-size linear program. This however requires an LP solver.

• If a network containing network-decomposed global cost functions is VAC, the underlying global cost functions are also VAC. As a result, good quality lower bounds can be obtained by enforcing VAC. These lower bounds are not as good as those obtained by OSAC, but VAC is usually much faster than OSAC.

• T-DAC is otherwise extremely efficient, easy to implement, offering good lower bounds and incrementality for little effort. However, when several global cost functions co-exist in a problem, a variable order that is a topological sort of all these global cost functions may not exist. In this case, using a topological order for each scope independently would lead to the creation of cycles leading to possibly infinite propagation. It may then be more attractive to use filtering DAGs to process these cost functions.

Finally, it should be noted that Theorem 11 only guarantees that T-DAC on a global cost function or its topologically sorted Berge-acyclic network-decomposition provide the same bound contribution. If a consistency stronger than DAC* is enforced (such as FDAC* or EDAC*), it may be more powerful when enforcedt on the global cost function itself than on its network-decomposition, thus giving an advantage to filtering DAGs.

In the end, the only truly informative answer will be provided by experimental results, as proposed in Section 9.

Experiments

In this section, we put theory into practice and demonstrate the practicality of the transformations described in the previous sections in solving over-constrained and optimization problems. We implemented cost functions with our transformations in toulbar2 v0.9.82 . For each cost function used in our benchmark problems, we implemented weak Existential Directional Generalized Arc Consistency (EDGAC*) [START_REF] De Givry | Existential Arc Consistency: Getting Closer to Full Arc Consistency in Weighted CSPs[END_REF][START_REF] Lee | A Stronger Consistency for Soft Global Constraints in Weighted Constraint Satisfaction[END_REF][START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], a local consistency combining AC, DAC and EAC, using DAG-filtering (called DAG-based approach in the sequel) with pre-computed tables (as described in Section 4). When possible, we also implemented a Berge-acyclic network-decomposition to be propagated using EDGAC* (called network-based approach). We ignore weaker forms of local consistency such as Arc Consistency or 0-inverse consistency [START_REF] Zytnicki | Bounds Arc Consistency for Weighted CSPs[END_REF] as previous experiments with global cost functions have shown that these weak local consistencies lead to much less efficient solving [START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF].

In the experiments, we used default options for toulbar2, including a new hybrid bestfirst search strategy introduced in [START_REF] Allouche | Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP[END_REF], which finds good solutions more rapidly compared to classical depth-first search. The default variable ordering strategy is dom/wdeg [START_REF] Boussemart | Boosting Systematic Search by Weighting Constraints[END_REF] with Last Conflict [START_REF] Lecoutre | Reasoning from Last Conflict(s) in Constraint Programming[END_REF], while the default value ordering consists, for each variable, in choosing first its fully supported value as defined by EDGAC*. At each node during search, including the root node, we eliminate dominated values using Dead End Elimination pruning [START_REF] Desmet | The dead-end elimination theorem and its use in protein side-chain positioning[END_REF][START_REF] Lecoutre | Wcsp integration of soft neighborhood substitutability[END_REF][START_REF] De Givry | Dead-End Elimination for Weighted CSP[END_REF] and we eliminate all variables having degree less than two using variable elimination [START_REF] Bertelé | Nonserial Dynamic Programming[END_REF][START_REF] Larrosa | Boosting Search with Variable Elimination[END_REF]. At the root node only, this is improved by pairwise decomposition [START_REF] Favier | Pairwise decomposition for combinatorial optimization in graphical models[END_REF] and we also eliminate all variables having a functional or bijective binary relation (e.g., an equality constraint) with another variable. The tests are conducted on a single core of an Intel Xeon E5-2680 (2.9GHz) machine with 256GB RAM.

We performed our experiments on four different benchmark problems. For the two first benchmarks (car sequencing and nonogram), we have a model with Berge-acyclic network-decompositions, whereas for the two others (well-formed parentheses and market split), we do not. Each benchmark has a 5-minute timeout. We randomly generate 30 instances for each parameter setting of each benchmark. We first compare the number of solved instances, i.e. finding the optimum and proving its optimality (no initial upper bound). We report the average run-time in seconds and consider that an unsolved problem requires the maximum available time (timeout). When all instances are solved, we also report the average number of backtracks (or '-' otherwise). The best results are marked in bold (taking first into account the number of solved instances in less than 5 minutes and secondly CPU time).

The Car Sequencing Problem

The car sequencing problem (prob001 in CSPLib, [START_REF] Parrello | Job-shop Scheduling Using Automated Reasoning: A Case Study of the Car-Sequence Problem[END_REF]) requires sequencing n cars of different types specified by a set of options. For any subsequence of c i consecutive cars on the assembly line, the option o i can be installed on at most m i of them. This is called the capacity constraint. The problem is to find a production sequence on the assembly line such that each car can be installed with all the required options without violating the capacity constraint. We use n variables with domain 1 to n to model this problem. The variable x i denotes the type of the i th car in the sequence. One GCC (global cardinality [START_REF] Oplobedu | CHARME: Un langage industriel de programmation par contraintes, illustré par une application chez Renault[END_REF]) constraint ensures all cars are scheduled on the assembly line. We post n -c i + 1 Among constraints [START_REF] Beldiceanu | Introducing Global Constraints in CHIP[END_REF] for each option o i to ensure the capacity constraint is not violated. We randomly generate 30 over-constrained instances, each of which has 5 possible options, and for each option o i , m i and c i are randomly generated in such a way that 1 ≤ m i < c i ≤ 7. Each car in each instance is randomly assigned to one type, and each type is randomly assigned to a set of options in such a way that each option has 1/2 chance to be included in each type. To introduce costs, we randomly assign unary costs (between 0 to 9) to each variable.

The problem is then modeled in three different ways. The first model is obtained by replacing each Among constraint by the W Among var cost function and the GCC constraint by the W GCC var cost function. W Among var returns a cost equal to the number of variables that need to be re-assigned to satisfy the Among constraint. W GCC var is used as a global constraint and returns on violation [START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF]. This model is called "flow&DAG-based" approach in Table 1.

The second model, identified as "DAG-based" in Table 1, uses a set of W Among var cost functions to encode GCC, i.e. replacing the single global cost function exploiting a flow network by a set of DAG-based global cost functions [START_REF] Allouche | Tractability and Decompositions of Global Cost Functions[END_REF].

In the third model, identified as "network-based" in Table 1, each of the W Among var in the previous DAG-based model is decomposed into a set of ternary cost functions with extra variables as described in Section 6.

Table 1 gives the experimental results. Column n indicates the sum of the number of original variables (n) and the number of extra variables added in the network-based approach. Column n gives the total number of unassigned variables after pre-processing. We observe that the network-based approach performed the worst among the three approaches. The DAG-based approach is up to six times faster than the flow&DAG-based approach on completely solved instances (n ≤ 13) and solves more instances within the 5-minute time limit. Surprisingly, it also develops the least number of backtracks on completely solved instances. We found that the initial lower bound produced by weak EDGAC on the flow&DAG-based approach can be lower than the one produced by the DAG-based approach. This is due to different orders of EPTs done by the two approaches resulting in different lower bounds. Finding an optimal order of integer arc-EPTs is NP-hard [START_REF] Cooper | Arc Consistency for Soft Constraints[END_REF]. Recall that EDGAC has a chaotic behavior compared to OSAC or VAC and encoding GCC into a set of W Among var will produce more EPTs (each W Among var moving unary costs differently) creating new opportunities for the overlapping W Amongs var to deduce a better lower bound.

The Nonogram Problem

The nonogram problem (prob012 in CSPLIB [START_REF] Ishida | Game "NONOGRAM[END_REF]) is a typical board puzzle on a board of size p × p. Each row and column has a specified sequence of shaded cells. For Table 1: Car sequencing problem (timeout=5min). For each approach, we give the number of instances solved (#), the mean number of backtracks only if all the instances have been completely solved (bt.), and the mean CPU time over all the instances (in seconds). example, a row specified (2, 3) contains two segments of shaded cells, one with length 2 and another with length 3. The problem is to find out which cells need to be shaded such that every row and every column contain the specific sequence of shaded cells. We model the problem by n = p 2 variables, in which x ij denotes whether the cell at the i th row and j th column needs to be shaded. In the experiments, we generate random instances from perturbed white noise images. A random solution grid, with each cell colored with probability 0.5, is generated. A feasible nonogram problem instance is created from the lengths of the segments observed in this random grid. To make it infeasible, for each row and each column, the list of segment lengths is randomly permuted, i.e., its elements are shuffled randomly. If a list is empty, then a segment of random length l is added (0 < l < p). We model and soften the restrictions on each row and column by W Regular var , resulting in three models: flow-based, DAG-based, and network-based. The flow-based model uses the W Regular var implementation based on minimum cost flows described in [START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF], the DAG-based version uses the filtering DAG (see [START_REF] Allouche | Tractability and Decompositions of Global Cost Functions[END_REF] for implementation details), and the network-based version uses the decomposition presented in Example 3.

Table 2 shows the results of the experiments. For medium-size problems (p ≤ 9, n ≤ 81), the network-based approach develops the least number of backtracks on average compared to the two other approaches. Value and variable elimination at pre-processing reduces the number of variables by a factor greater than two. The flow-based and DAGbased approaches develop the same number of backtracks, producing the same EPTs, but the dynamic programming algorithm implemented in the DAG-based approach is about one order-of-magnitude faster than the minimum cost flow algorithm used in the flow-based approach. Moreover, the network-based approach is at least one order-ofmagnitude faster than the DAG-based approach. On the largest instances, because of an exponential increase of the number of backtracks, the network-based approach becomes unable to solve all the instances in less than five minutes, but still outperforms the other two approaches.

The Well-formed Parentheses problem

In this experiment, we use a network-decomposition of the W Grammar constraint whose structure is depicted in Figure 2. It is obviously not Berge-acyclic. This experiment Given a set of 2p even length intervals within [1, . . . , 2p], the well-formed parentheses problem is to find a string of parentheses with length 2p such that substrings in each of the intervals are well-formed parentheses. We model this problem by a set of n = 2p variables. Domains of size 6 are composed of three different parenthesis types: ()[]{}. We post a W Grammar var cost function on each interval to represent the requirement of well-formed parentheses. We generate 2p -1 even length intervals by randomly picking their end points in [1, . . . , 2p], and add an interval covering the whole range to ensure that all variables are constrained. We also randomly assign unary costs (between 0 and 10) to each variable.

We compare two models. The first model, the DAG-based approach, is obtained by modeling each W Grammar var cost function using a filtering DAG approach.

In the second network-based model, we decompose each W Grammar var cost function involving m variables using m(m + 1)/2 extra variables P i,j (1 ≤ j ≤ m, 1 ≤ i ≤ m -j + 1) whose value corresponds to either a symbol value (for j = 1) or a pair of a symbol value S and a string length k (1 ≤ k < j, for j ≥ 2) associated to the substring (i, i + j -1), starting from i of length j. Ternary cost functions link every triplet P i,j , P i,k , P i+k,j-k so that there exists a compatible rule S->AB in order to get the substring (i, i + j -1) from the two substrings (i, i + k -1) and (i + k, i + j -1) when P i,j = (S, k), P i,k = (A, u), P i+k,j-k = (B, v) with u < k, v < j -k. Binary cost functions are used to encode the terminal rules between P i,1 (i ∈ [1, m]) and the original variables.

Results are shown in Table 3. The network-based approach is clearly inefficient. It has n = 1, 146 variables on average for p = 9 (n = 18). The number of backtracks increases very rapidly due to the poor propagation on a non Berge-acyclic network. The DAG-based approach clearly dominates here. Notice that the DAG-based propagation of W Grammar var can be very slow with around 1 backtrack per second for p = 9.

As a second experiment on well-formed parentheses, we generate new instances using only one hard global grammar constraint and a set of p(2p -1) binary cost functions corresponding to a complete graph. For each possible pair of positions, if a parentheses pair ((), [], or {}) is placed at these specific positions, then it incurs a randomly-generated cost (between 0 to 10). A single W Grammar var cost function is placed on all the n = 2p variables, which returns on violation (a Grammar constraint), ensuring that the whole string has well-formed parentheses. As in the experiments of Table 3, the two models are characterized by how the consistency is enforced on the W Grammar var cost function: a filtering DAG for the DAG-based approach, a network-decomposition for the network-based approach.

Results are shown in Table 4. The network-based approach still develops more backtracks on average for p ≥ 6 (n ≥ 12) than the DAG-based approach but the difference is less important than in the previous experiment because there is a single grammar constraint. Surprisingly, for p ≤ 5, the network-based approach develops less backtracks than the DAG-based approach. The network-based approach benefits from variable elimination that exploits bijective binary relations occurring in the decomposed hard grammar cost function. Moreover, having only one global constraint implies less extra variables for the network-based approach than in the previous experiment (n = 189 for p = 9 instead of n = 1, 146). The propagation speed of the network-based approach is much better than the DAG-based approach, with ∼4, 100 bt./sec instead of ∼23 bt./sec for p = 9, resulting in better overall time efficiency compared to the DAG-based approach, being up to 8 times faster for p = 7 to solve all the thirty instances.

The Market split problem

In some cases, problems may contain global cost functions which are not networkdecomposable because the bounded arity cost function decomposition is not polynomial Table 3: Soft well-formed parentheses (timeout=5min). For each approach, we give the number of instances solved (#), the mean number of backtracks only if all the instances have been completely solved (bt.), and the mean CPU time over all the instances (in seconds). a i x i = b (a and b being integer coefficients) can be easily decomposed by introducing n -3 intermediate sum variables q i and ternary sum constraints of the form q i-1 + a i x i = q i with i ∈ [3, n -2] and a 1 x 1 + a 2 x 2 = q 2 , q n-2 +a n-1 x n-1 +a n x n = b. More generally, ternary decompositions can be built for the more general case where the right hand side of the constraint uses any relational operator, including any Knapsack constraint. In this representation, the extra variables q i have b values in their domain, which is exponential in the size of the representation of b (in log(b)). As for the pseudo-polynomial Knapsack problem, if b is polynomially bounded by the size of the global constraint, propagation will be efficient. It may otherwise be exponential in it.

As an example, we consider a generalized version of the Knapsack problem, the Market Split problem defined in [START_REF] Cornuéjols | A Class of Hard Small 0-1 Programs[END_REF][START_REF] Trick | A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints[END_REF]. The goal is to minimize n i=1 o i x i such that n i=1 a i,j x i = b j for each j ∈ [1, m] and x i are Boolean variables in {0, 1} (o, a and b being positive integer coefficients). We compared the Berge-acyclic decomposition in toulbar2 (version 0.9.8) with a direct application of the Integer Linear Programming solver cplex (version 12.6.3.0). We used a depth-first search with a static variable ordering (in decreasing oi m j=1 ai,j order) and no pre-processing (options -hbfs: -svo -o -nopre) for toulbar2. We generated random instances with random integer coefficients in [0, 99] for o and a, and b j = 1 2 n i=1 a i,j . We used a sample of 30 problems with m = 4, n = 30 leading to max b j = 918. The mean number of nodes developed in toulbar2 was 29% higher than in cplex, which was on average 4.5 times faster than toulbar2 on these problems. The 0/1 knapsack problem probably represents a worst case situation for toulbar2, given that cplex embeds much of what is known about 0/1 knapsacks (and only part of these extend to more complicated domains). Possible avenues to improve toulbar2 results in this unfavorable situation would be to use a combination of the m knapsack constraints into one as suggested in [START_REF] Trick | A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints[END_REF].

Conclusion

Existing tools for solving optimization on graphical models are usually restricted to cost functions involving a reasonably small set of variables, often using an associated cost table. But problem modeling may require to express complex conditions on a nonbounded set of variables. This has been solved in Constraint Programming by using Global Constraints. Our results contribute to lift this approach to the more general framework of cost function networks, allowing to express and efficiently process both global constraints and global cost functions, using dedicated soft arc consistency filtering.

Our contributions are four-fold. First, we define the tractability of a global cost function, and study its behavior with respect to projections/extensions with different arities of cost functions. We show that tractable r-projection-safety is always possible for projections/extension to/from the nullary cost function, while it is always impossible for projections/extensions to/from r-ary cost functions for r ≥ 2. When r = 1, we show that a tractable cost function may or may not be tractable 1-projection-safe. Second, we define polynomially DAG-filterable cost functions and show them to be tractable 1-projectionsafe. We give also a polytime dynamic programming based algorithm to compute the minimum of this class of global cost functions. We also show that the cost function W Grammar var is polynomially DAG-filterable and tractable 1-projection-safe. The same results applies to W Among var , W Regular var , and W Max/W Min as shown in the associated technical report [START_REF] Allouche | Tractability and Decompositions of Global Cost Functions[END_REF]. Third, we show that dynamic programming can be emulated by soft consistencies such as DAC and VAC if a suitable network decomposition of the global cost function into a Berge-acyclic network of bounded arity cost functions exists. In this case, local consistency on the decomposed network is essentially as strong as on the global cost function. This approach is shown to be a specific case of the previous approach in the sense that any Berge-acyclic network-decomposable cost function is also polynomially DAG-filterable. Finally, we perform experiments and compare the DAGbased and network-based approaches, in terms of run-time and search space. The DAGbased approach dominates when there are several overlapping global cost functions. On the contrary, the network-based approach performs better if there are few global cost functions resulting in a reasonable number of extra variables. This is complexified by additional techniques such as boosting search by variable elimination [START_REF] Larrosa | Boosting Search with Variable Elimination[END_REF], Weighted Degree heuristics [START_REF] Boussemart | Boosting Systematic Search by Weighting Constraints[END_REF], and Dead-End Elimination [START_REF] De Givry | Dead-End Elimination for Weighted CSP[END_REF] which work better with the lowarity cost functions of the network-based approach. We also compare against the flowbased approach [START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF] and show that our approaches are usually more competitive. On Berge acyclic network-decomposable cost function just as W Regular var , this is not unexpected as the dynamic programming based propagation or its emulation by T-DAC essentially solves a shortest path problem, which can easily be reduced to the more general min-cost flow problem used in [START_REF] Lee | Consistency Techniques for Global Cost Functions in Weighted Constraint Satisfaction[END_REF] which can itself be reduced to LP [START_REF] Ahuja | Network flows: Theory, Algorithms and Applications[END_REF]. As problems become more specific, algorithmic efficiency can increase.

An immediate possible future work is to investigate other sufficient conditions for polynomially DAG-filterable and also tractable 1-projection-safety. Our results only provide a partial answer. Whether there exists necessary conditions for polynomially DAG-filterable is unknown. Besides polynomially DAG-filterable, we would like to investigate other form of tractable 1-projection-safety and techniques for enforcing typical consistency notions efficiently.

6 Algorithm 2 :

 62 Enforce NC* Procedure enforceNC*() in Algorithm 2 enforces NC*, where unaryProject() applies EPTs that move unary costs towards W ∅ while keeping the solution unchanged, and pruneVar(x i ) removes infeasible values.

4 pruneVar(x i ); 5 Algorithm 3 :

 453 Enforcing GAC* for x i with respect to W S Local consistency enforcement involves two types of operations: (1) finding the minimum cost returned by the cost functions among all (or part of the) tuples; (2) applying EPTs that shift costs to and from smaller-arity cost functions.Minimum cost computation corresponds to line 3 in Algorithm 2, and line 2 in Algorithm 3. For simplicity, we write min{W S ( ) | ∈ D S } as min{W S }.

Proposition 1 .

 1 . The time complexity of enforcing one of the previous consistencies is thus entirely defined by the time complexity of computing the minimum of a cost function during the enforcing. The procedure enforceGAC*() in Algorithm 3 requires O(d • f min ) time, where d is the maximum domain size and f min is the time complexity of minimizing W S . Proof. Line 2 requires O(f min ) time. We can replace the domain of x i by {v}, and run the minimum computation to get the minimum cost. Projection at line 3 can be performed in constant time. Thus, each iteration requires O(f min ). Since the procedure iterates d times, and the procedures unaryProject and pruneVar requires O(d), the overall complexity is O

Theorem 3 .

 3 Any flow-based projection-safe global cost function is tractable 1-projectionsafe.

Function 1 Topologically sort V ; 2 foreach 5 else 6 return 7 Algorithm 4 :

 125674 Minimum (WS) Form the corresponding filtering DAG T = (V, E); ωS i ∈ V in reverse topological order do 3 if ωS i is a leaf of T then 4 Min[ωS i ] := min{ωS i } ; Min[ωS i ] := fi({Min[ωS k ] | (ωS i , ωS k ) ∈ E}) ; Min[WS]; Computing min{W S }

8 Algorithm 5 :

 85 Projection from a polynomially DAG-filterable global cost functionThe time complexity of enforcing GAC* on a polynomially DAG-filterable global cost function heavily depends on preprocessing, as stated in the following corollary. Corollary 1. If the time complexity for pre-computing the table M in + for a polynomially DAG-filterable cost function W S is O(K(n, d)), where K is a function of n = |S| and maximum domain size d, then enforcing GAC* on a variable x i ∈ S with respect to W S requires O(K(n, d) + d) time. Proof. Computing the minimum of W S when x i = v, where x i ∈ S and v ∈ D(x i ), requires only constant time by looking up from M in + . By Proposition 1, the time complexity is O(K(n, d) + d) time.

Figure 1 :Theorem 9 .

 19 Figure 1: The DAG corresponding to W Grammar var

Corollary 2 . 1 for c ∈ Σ do 2 u; 3 for i := 1 to n do 4 foreach 6 f 7 return 8 Function

 21234678 Given W S = W Grammar var (S, G = (Σ, N, P, A 0 )). Enforcing GAC* on a variable x i ∈ S with respect to W Grammar requires O(nd • |Σ| + n 3 • |P |) time, where n = |S| and d is the maximum domain size. Proof. Using a similar argument to that in the proof of Theorem 9, Algorithm 7 requires O(nd•|Σ|+n 3 •|P |) time. The result follows directly from Corollary 1 and Theorem 9.Function GrammarMin(S, G)for i := 1 to n do [i, c] := min{U c i }A ∈ N do f [i, i, A] := ; 5 foreach (A, a) such that (A → a) ∈ P do [i, i, A] = min{f [i, i, A], u[i,a]} ; GrammarPartialMin(S, G, 1); GrammarPartialMin(S, G, start) for len := 2 to n do 9 for i := start to n -len + 1 do 10 j := i + len -1 ;

1 for i := 1 to n do 2 for j := i to n do 3 foreach A ∈ N do 4 F

 1234 [i, j, A] := -; 5 marked[i, j, A] := false; 6 marked[1, n, A 0 ] := true; 7 for len := n down to 2 do 8

16 Algorithm 7 :

 167 Pre-computation for W Grammar var Definition 21. For a given integer p, a p-network-decomposition of a global cost function W GCF (S, A 1 , . . . , A k ) is a polynomial transformation δ p that returns a CFN δ p (S, A 1 , . . . , A k ) = (S ∪ E, F, ), where S ∩ E = ∅, such that ∀W T ∈ F, |T | ≤ p and ∀ ∈ D S , W GCF (S, A 1 , . . . , A k )( ) = min ∈D S∪E , [S]= W S i ∈F W Si ( [S i ]).

3 u 5 GrammarPartialMin 7 Algorithm 8 :

 3578 [p, c] := min{U c p }; 4 foreach (A, a) such that (A → a) ∈ P do f [p, p, A] = min{f [p, p, A], u[i, a]} ; Projection from W Grammar var (S, G = (Σ, N, P, A 0 )) soft global constraint with an associated violation measure µ. Instead, the global cost function will use any relaxation of the decomposed global constraint.

  Enforcing T-DAC is therefore in O(ed r ) in time, where e = |W| and r = max W S ∈W |S|. Theorem 11. If a global cost function W GCF(S, A 1 , . . . , A k ) decomposes into a Bergeacyclic CFN N = (S ∪ E, F), there exists an ordering on S ∪ E such that the unary cost function W xi n on the last variable x in of S produced by enforcing T-DAC on the subnetwork (S, {W GCF (S, A 1 , . . . , A k )}∪{W xi } xi∈S ) is identical to the unary cost function W xi n produced by enforcing T-DAC on the decomposition N = (S ∪ E, F ∪ {W xi } xi∈S ).

Theorem 12 .

 12 If a global cost function W GCF(S, A 1 , . . . , A k ) decomposes into a Bergeacyclic CFN N = (S ∪ E, F, ) then enforcing VAC on either (S ∪ E, F ∪ {W xi } xi∈S , ) or on (S, {W GCF (S, A 1 , . . . , A k )} ∪ {W xi } i∈S , ) yields the same lower bound W ∅ .

Figure 2 :

 2 Figure 2: Network associated to the decomposition of W Grammar var (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ).

Table 2 :

 2 Nonogram (timeout=5min). For each approach, we give the number of instances solved (#), the mean number of backtracks only if all the instances have been completely solved (bt.), and the mean CPU time over all the instances (in seconds).

	n	flow-based	DAG-based	network-based
	# bt.	time # bt.	time n n # bt.	time
	36 30 11.4 0.09 30 11.4 0.01 96 18 30	4.4 0.00
	49 30 41.8 0.29 30 41.8 0.05 133 42 30	22.5 0.01
	64 30 186.4	2.3 30 186.4 0.26 176 64 30	90.3 0.01
	81 30 254.4	4.5 30 254.4 0.50 225 97 30 248.9 0.04
	100 25 -	86.0 30 3,581 10.8 280 131 30 3,861 0.47
	121 19 -	166.8 26 -	72.8 341 171 30 12,919	1.6
	144 3	-	279.6 9	-	233.2 408 224 28	-	44.1
	169 0	-	300.0 5	-	266.5 481 267 23	-	116.4
	196 0	-	300.0 1	-	297.1 560 330 7	-	257.1
	will allow us to see the behavior of network-decompositions when they are not Berge-
	acyclic.

Table 4 :

 4 Well-formed parentheses (single hard global constraint) with additional binary cost functions (timeout=5min). For each approach, we give the number of instances solved (#), the mean number of backtracks if available (bt.), and the mean CPU time (in seconds). However, if the network is Berge-acyclic, Theorem 11 still applies. With exponential size networks, filtering will take exponential time, but may yield strong lower bounds. The global constraint

	n	DAG-based		network-based
	# bt.	time	n	n	#	bt.	time
	8 30		3.5	0.06	145	131 30	676.8	0.21
	10 30		6.6	0.60	250	228 30 63,084	12.5
	12 30		9.1	3.8	392	361 7	-	260.3
	14 30 21.1	8.3	580	538 0	-	300
	16 29		-	48.9	841	785 0	-	300
	18 23		-	115.6 1,146 1,075 0	-	300
	n		DAG-based		network-based
	# bt.	time	n	n	#	bt.	time
	8 30	37.4	0.11	44	33 30	19.5 0.04
	10 30 105.5	0.51	65	51 30	100.5 0.12
	12 30 265.4	2.4	90	73 30	916.5 0.38
	14 30 887.7	14.0 119	99 30	6,623	1.7
	16 30 3,037	80.6 152 129 30	54,544 12.0
	18 13	-	257.9 189 163 30 394,391 95.7
	in size.

n i=1

Otherwise, such a variable can be removed by variable elimination: remove x from E and replace the W T involving x by the cost function minx W T on T \ {x}. This preserves the Berge-acyclicity of the network if it exists.

soft difference cost functions. A soft difference cost function takes

http://www.inra.fr/mia/T/toulbar2/

Acknowledgements

This work has been partly funded by the "Agence Nationale de la Recherche" (ANR-10-BLA-0214) and a PHC PROCORE project number 28680VH.