# Arc-consistency and linear programming duality: an analysis of reduced cost based filtering

Guillaume Claus, Hadrien Cambazard, Vincent Jost

<figure><img src="image_1.png" /></figure>

## To cite this version:

Guillaume Claus, Hadrien Cambazard, Vincent Jost. Arc-consistency and linear programming duality: an analysis of reduced cost based filtering. 2022. hal-03728504

HAL Id: hal-03728504

https://hal.univ-grenoble-alpes.fr/hal-03728504

Preprint submitted on 20 Jul 2022

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Arc-consistency and linear programming duality: an analysis of reduced cost based filtering

Guillaume Claus¹, Hadrien Cambazard¹, and Vincent Jost¹

¹ Univ. Grenoble Alpes, CNRS, Grenoble INP G-SCOP, 38000 Grenoble, France

**Abstract.** In Constraint Programming (CP), achieving arc-consistency (AC) of a global constraint with costs consists in removing from the domains of the variables all the values that do not belong to any solution whose cost is below a fixed bound. We analyse how linear duality and reduced costs can be used to find all such inconsistent values. In particular, when the constraint has an ideal Linear Programming (LP) formulation, we show that *n* dual solutions are always enough to achieve AC (where *n* is the number of variables). This analysis leads to a simple algorithm with *n* calls to an LP solver to achieve AC, as opposed to the naive approach based on one call for each value of each domain. It extends the work presented in [German et al., 2017] for satisfaction problems and in [Claus et al., 2020] for the specific case of the minimum weighted alldifferent constraint. We propose some answers to the following questions: does there always exists a dual solution that can prove a value consistent/inconsistent ? given a dual solution, how do we know which values are proved consistent/inconsistent ? can we identify simple conditions for a family of dual solutions to ensure arc-consistency ?

## 1 Introduction

Mixed Integer Programming (MIP) and Constraint Programming (CP) have often been combined in the past to take advantage of the complementary strengths of the two frameworks. Many approaches have been proposed to benefit from their modelling and solving capabilities [Bockmayr and Kasper, 1998; Rodosek et al., 1999; Refalo, 2000; Aron et al., 2004; Achterberg et al., 2008]. A typical integration of the two approaches is to use the linear relaxation of the entire problem in addition to the local consistencies enforced by the CP solver. The relaxation can detect infeasibility and is often added to provide a bound on the objective.

A number of previous works have also proposed to use the linear relaxation for filtering the domains in a constraint programming framework [Refalo, 1999; Refalo, 2000; Aron et al., 2004; Achterberg et al., 2008; Focacci et al., 2002]. Based on the relaxation, filtering can be performed using a technique referred to as reduced cost based filtering [Focacci et al., 2002; Hooker, 2006]. It is a specific case of cost-based filtering [Focacci et al., 1999] that aims at filtering out values leading to non-improving solutions. It originates from *variable fixing* [Nemhauser and Wolsey, 1988] which is performed in MIP to detect some 0/1 variables that must be fixed to either 0 or 1 in any solution improving the best known. *Variable fixing* relies on the
reduced costs of the variables given by an optimal dual solution of the linear relaxation. It is known to be incomplete because it strongly depends on the specific dual solution used. Alternatively, it was recently shown in [German et al., 2017] that a complete filtering, namely arc-consistency, can be achieved by solving a single linear relaxation when the problem considered is a satisfaction problem with an ideal integer programming formulation. Such formulations can be found for a number of common global constraints such as ELEMENT, ALLDIFFERENT, GLOBALCARDINALITY or GEN-SEQUENCE [Refalo, 2000, German et al., 2017]. The approach does not apply to global constraints involving a cost variable such as MINIMUMWEIGHTALLDIFFERENT [Caseau and Laburthe, 2000, Focacci et al., 2002] even though it has an ideal LP formulation. A natural extension to the work [German et al., 2017] is to handle an objective function i.e. a cost variable from the constraint point of view. We are therefore interested in the design of filtering algorithms based on linear programming for polynomial global constraints with a cost variable. Note that when an ideal LP formulation is available for the constraint, a naive approach, typically used in practice when checking or designing propagators is to solve one LP for each variable-value pair.

Since the approach of [German et al., 2017] does not easily extend, we go back to reduced cost based filtering to generalize the work of [Claus et al., 2020] which was done in the case of the MINIMUMWEIGHTALLDIFFERENT constraint. We consider global constraints with assignment costs. More precisely, assigning a value $j$ to a variable $X_i$ incurs a cost $c_{ij} \in \mathbb{N}$ and the overall cost is the sum of all individual assignment costs. The optimal (minimal) overall cost, with respect to the constraint, is denoted $z^*$. Note that soft global constraints might have alternative costs definition but assignment costs are very common. In general, the consistency of a given value $j$ of a variable $X_i$ is established by computing the minimum value of the problem restricted with $X_i = j$ which is referred to as the *ij*-optimal value and denoted $z_{ij}^*$. Value $j$ of $X_i$ is inconsistent if $z_{ij}^*$ is greater than the maximum cost allowed denoted $\bar{Z}$. A typical lower bound of $z_{ij}^*$ is given by the LP reduced cost, $r_{ij,u^*}$ available from an optimal dual solution $u^*$ of the linear relaxation (namely $z^*+r_{ij,u^*} \le z_{ij}^*$). It was used to perform an incomplete filtering in [Focacci et al., 2002] for the assignment problem. However, the value of $r_{ij,u^*}$ depends on the dual solution $u^*$ found and greatly varies in practice from one solution to another. We prove that there always exists an optimal dual solution $u^*$ such that the reduced cost $r_{ij,u^*}$ provides the *ij*-optimal value (i.e. such that $z^* + r_{ij,u^*} = z_{ij}^*$). Multiple *ij*-optimal values can be provided by a single optimal dual solution and we give a necessary and sufficient condition to identify the *ij*-values that are optimal. Eventually, given a set $S$ of variable-value pairs, we give a sufficient condition for the existence of a single optimal dual solution providing all *ij*-optimal values for $S$. This condition gives an upper bound on the number of dual solutions needed to ensure AC.

The reasoning is illustrated with two global constraints : MINIMUMWEIGHTALLDIFFERENT (referred to as MINWALLDIFF for short in the rest of the paper), and SHORTESTPATH. The first one enforces *n* variables to be assigned to distinct values. This constraint is related to the assignment problem for which
a well-known LP ideal formulation is available. The second one, encodes a *s-t*-path in an acyclic directed graph of *n* vertices using *successor* variables: each variable is mapped to a variable whose value gives the index of the next vertex in the path (or its self index if the vertex doesn't belong to the path). In both cases, the cost of the solution must be below a given upper-bound.

Finally, we propose a simple algorithm based on LP to enforce AC. This generic algorithm applies to all global constraints with assignment costs that have an ideal LP formulation. It requires a dual solution for each variable which is significantly less than the naive solution that calls the simplex algorithm for each possible value of each variable. This extends [German et al., 2017] that did the filtering with a single simplex call for an unweighted constraint. Practically, an optimal dual solution is updated in such a way that all the exact reduced costs are enumerated to produce a filtering that can be interrupted even if it is incomplete. We believe such an anytime algorithm is key for very costly global constraints where arc-consistency is rarely worth a high runtime complexity such as $O(n^3)$. See for instance the discussion in [Cauwelaert and Schaus, 2017] where the arc-consistency algorithm for MINWALLDIFF is found too costly and the filtering of [Focacci et al., 2002] used as a baseline is too weak. Reduced costs based filtering techniques could be a very good framework to design anytime and adaptive consistency algorithms [Balafrej et al., 2016].

In section 2 we set the framework for our work and present the two constraints we will use as examples. The LP formulations used in this document and the relationship between filtering and reduced costs are explained in section 3. The main results on the possibility to achieve AC with reduced costs and the number of dual solutions needed to do so are detailed at section 4. Eventually our filtering algorithm is stated in section 5. All the proofs of our results are gathered in the annex to keep clear the thread of reasoning.

## 2 Arc-Consistency for global constraints with assignment costs

A **constraint satisfaction problem** (CSP) is made of a set of variables, each with a given **domain** i.e. a finite set of possible values, and a set of constraints specifying the allowed combinations of values for subset of variables. In the following, the variables, e.g. $X_i$, are written with upper case letters for the constraint programming models as opposed to the variables of linear programming models that are in lower case. $D(X_i) \subseteq \mathbb{Z}$ denotes the domain of $X_i$. A **constraint** $C$ over a set of variables $\langle X_1, \dots, X_n \rangle$ is defined by the allowed combinations of values (tuples) of its variables. Such tuples of values are also referred to as solutions of the constraint $C$. Given a constraint $C$ with a scope $\langle X_1, \dots, X_n \rangle$, a **support for C** is a tuple of values $\langle a_1, \dots, a_n \rangle$ that is a feasible solution of $C$ and such that $a_i \in D(X_i)$ for all variable $X_i$ in the scope of $C$. Consider a variable $X_i$ in the scope of $C$, the domain $D(X_i)$ is said **arc-consistent** for $C$ if and only if all the values of $D(X_i)$ belong to a support for $C$. A constraint $C$ is said arc-consistent if and only if all its variable's domains are arc-consistent.
For a constraint $C(X_1, \dots, X_n)$ with an ideal LP formulation, arc-consistency can be achieved by solving a single linear program [German et al., 2017].

A **weighted constraint WC** $(X_1, \dots, X_n, Z, c)$ is a constraint over $\langle X_1, \dots, X_n \rangle$ that considers a cost $c_{ij} \in \mathbb{N}$ for assigning variable $X_i$ to value $j$ and $Z$ is the cost variable. The cost of a support $\langle a_1, \dots, a_n \rangle$ is defined as $\sum_{i=1}^n c_{i,a_i}$. The constraint holds if $\langle a_1, \dots, a_n \rangle$ is a support of the constraint without cost $C$ and its cost remains below $Z$. In other words, $\langle a_1, \dots, a_n \rangle$ is a **support for WC** if it is a support for $C$ and $\sum_{i=1}^n c_{i,a_i} \le Z$.

A **support of minimal cost** is a support for $C$ such that its cost is no more than the cost of any other support for $C$. Such a support is also a support for $Z$, a lower bound for $Z$ in WC.

We consider here only constraint that have an ideal LP formulation i.e. an LP formulation whose solutions are integer and so are the solutions of its linear relaxation. More precisely, the problem of identifying a support can be stated using such an ideal LP formulation.

**Example 1.**

MINWALLDIFF $(X_1, \dots, X_n, Z, c)$

is equivalent to:

$$ALLDIFF (X_1, \dots, X_n) \quad \sum_{i=1}^{n} c_{i,X_i} \le Z$$

Where ALLDIFF ensures the $X$ variables take distinct values.

(see [Sellmann, 2002])

SHORTESTPATH $(X_1, \dots, X_n, Z, c)$ is

equivalent to

$$PATH (X_1, \dots, X_n) \quad \sum_{i=1}^{n} c_{i,X_i} \le Z$$

with $X_i = \begin{cases} j & \text{if } j \text{ is the successor of } i \\ i & \text{if } i \text{ is not in the path} \end{cases}$ and $c_{ii} = 0, \forall 1 \le i \le n$.

$PATH$ ensures the $X$ variables describe a path from vertex 1 to vertex $n+1$.

An other possible formulation for **SHORTESTPATH** constraint is to use 0/1 variables, one for each possible arc. Each of these variables equals to 1 if and only if the path pass through the corresponding arc.

In this paper, we will show that LP can be used to achieve arc-consistency in the context of constraints with costs. In the next section, we state the LP formulation used in our results and recall the link between dual formulations, reduced costs and filtering.

## 3 LP formulations

We consider a general constraint with costs WC that has an ideal LP formulation. In the scope of WC, the variables together with their domains can be represented
by a variable-value graph ($U \cup V, E$) where $U$ is the set of the variables and $V$ is the set of their possible values. Each edge $ij$ expresses that value $j$ belongs to the domain of $X_i$ and its assignment cost is $c_{ij}$.

A solution consists in choosing one edge for each vertex $i \in U$ such that the assignment satisfies the constraint. By extension, we call **support** the set of chosen edges in a feasible solution and **minimal cost support** the set of chosen edges in an optimal solution.

We assume that AC has been achieved on $C(X_1, \dots, X_n)$ (for instance using [German et al., 2017]). In other words, any edge belongs to at least one support of $C(X_1, \dots, X_n)$, ignoring the costs.

To find a support of minimal cost, the following LP can be used. It is formulated with 0/1 variables $x_{ij}$ such that $x_{ij} = 1 \iff X_i = j$ and the constraint $C$ is stated by a set $Q$ of additional linear constraints:

$$ (P) \left\{ \begin{array}{ll} \min z = \sum_{ij \in E} c_{ij} x_{ij} & \\ \text{s.t.} \quad \sum_{ij \in E} a_{q,ij} x_{ij} \ge b_q \quad \forall q \in Q & (u_q) \\ \phantom{\text{s.t.} \quad \sum_{ij \in E} a_{q,ij} x_{ij} \ge} \sum_{j | ij \in E} x_{ij} = 1 \quad \forall i \in U & (u_i) \\ \phantom{\text{s.t.} \quad \sum_{ij \in E} a_{q,ij} x_{ij} \ge} x_{ij} \ge 0 \quad \forall ij \in E & (3) \end{array} \right. $$

Constraint (1) states the constraint $C$ itself and constraint (2) enforces each variable to take a single value. Since we only consider ideal formulation and we have constraint (2), $x_{ij} \in \{0, 1\}$ is relaxed to inequality (3). $z$ is the cost of a solution and this solution is feasible for WC if $z \le \bar{z}$.

**Example 2 (continued: Linear Programs).**

Formulation (P) is given below for MINWALLDIFF and SHORTESTPATH. In both, recall the channeling between the CP variables/values and the LP variables: $x_{ij} = 1 \iff X_i = j$.

$$ (P_{\text{WAD}}) \left\{ \begin{array}{ll} \min z = \sum_{ij \in E} c_{ij} x_{ij} & \\ \text{s.t.} \quad \sum_{j | ij \in E} x_{ij} = 1 \quad \forall i \in U & (P_{\text{SP}}) \\ \phantom{\text{s.t.} \quad \sum_{j | ij \in E} x_{ij} =} \sum_{i | ij \in E} x_{ij} = 1 \quad \forall j \in V & \\ \phantom{\text{s.t.} \quad \sum_{j | ij \in E} x_{ij} =} x_{ij} \ge 0 \quad \forall ij \in E & \end{array} \right. \left\{ \begin{array}{ll} \min z = \sum_{ij \in A} c_{ij} x_{ij} & \\ \text{s.t.} \quad \sum_{j | kj \in A} x_{kj} - \sum_{i | ik \in A} x_{ik} = 0 \quad \forall k \in N \setminus \{s, t\} \\ \phantom{\text{s.t.} \quad \sum_{j | kj \in A} x_{kj} - \sum_{i | ik \in A} x_{ik} =} \sum_{j | sj \in A} x_{sj} = 1 & \\ \phantom{\text{s.t.} \quad \sum_{j | kj \in A} x_{kj} - \sum_{i | ik \in A} x_{ik} =} x_{ij} \ge 0 \quad \forall ij \in A & \end{array} \right. $$

Where $U$ is the set of the variables and $V$ the set of values, common for all the variables.

This LP has $O(|U|+|V|)$ constraints.

Where $N$ is the set of the vertices and $A$ is the set of the arcs. $s$ and $t$ respectively denotes the source and the sink ($s = 1$ and $t = n+1$ to match Example 1). This LP has $O(|N|)$ constraints.
Both these LP formulations are known to be ideal.

Let's denote ($P|_{kl}$) the LP similar to ($P$) in which $x_{kl}$ is forced to 1 (i.e. ($P|_{kl}$) is the restricted problem with $X_k = l$), and $z^*|_{kl}$ its optimal value. Note that the domains are AC when $z^*|_{kl} \le \bar{Z}$ for each edge $kl$ of $E$.

The dual of ($P$) is:

$$ (D) \left\{ \begin{array}{ll} \max w = \sum_{q \in Q} b_q u_q + \sum_{i \in U} u_i & \\ \text{s.t. } u_i + \sum_{q \in Q} a_{q,ij} u_q \le c_{ij} & \forall ij \in E \quad (x_{ij}) \\ u_q \ge 0 & \forall q \in Q \\ u_i \in \mathbb{R} & \forall i \in U \end{array} \right. \quad (4) $$

Example 3 (continued: dual linear programs).

Formulation (D) is given below for MINWALLDIFF and SHORTESTPATH.

$$ (D_{WAD}) \left\{ \begin{array}{ll} \max w = \sum_{i \in U} u_i + \sum_{j \in V} u_j & \\ \text{s.t. } u_i + u_j \le c_{ij} & \forall ij \in E \\ u_i \in \mathbb{R} & \forall i \in U \\ u_j \in \mathbb{R} & \forall j \in V \end{array} \right. \quad (D_{SP}) \left\{ \begin{array}{ll} \max w = u_s & \\ \text{s.t. } u_i - u_j \le c_{ij} & \forall ij \in A, j \ne t \\ u_i \le c_{it} & \forall it \in A \\ u_i \in \mathbb{R} & \forall i \in V \end{array} \right. $$

This LP has $O(|E|)$ constraints.

This LP has $O(|A|)$ constraints.

For the rest of this document, primal and dual solutions are called in reference to ($P$) and ($D$). Moreover, we denote ($D|_{kl}$) the dual of ($P|_{kl}$).

The reduced cost of an edge $ij \in E$ is the slack of the corresponding dual variable. For a feasible dual solution $u$, it is defined as :

$$ r_{ij,u} = c_{ij} - u_i - \sum_{q \in Q} a_{q,ij} u_q $$

We define the exact reduced cost $R_{ij}$ of an edge $ij \in E$ as follows :

$$ R_{ij} = z^*_{ij} - z^* $$

$R_{ij}$ is the increase of the optimal value $z^*$ when forcing the edge $ij$ in the solution i.e when $X_i$ is forced to take the value $j$ of its domain.

Example 4 (Continued: Reduced costs).

For MINWALLDIFF,

$$ r_{ij,u} = c_{ij} - u_i - u_j $$

For SHORTESTPATH,

$$ r_{ij,u} = c_{ij} - u_i + u_j $$
Reduced costs provide lower bounds of the increase of $z^*$ when variable $x_{ij}$ is forced to one. Since this is a corner stone of the filtering techniques based on LP and the present work, Property 1 states it explicitly.

**Property 1.** For any dual optimal solution $u^*$ and any edge $kl \in E$, we have

$$0 \le r_{kl,u^*} \le R_{kl}$$

*Proof.* – The first inequality is provided by the constraint (4) since $u^*$ is feasible.

– Let $\tilde{x}^*$ be an optimal solution of $(\mathcal{P}_{|kl})$, the problem restricted with $X_k = l$.

$$z^* = \sum_{q \in Q} b_q u_q^* + \sum_{i \in U} u_i^*$$

$$z^* \le \sum_{q \in Q} \left( \sum_{ij \in E} a_{q,ij} \tilde{x}_{ij}^* \right) u_q^* + \sum_{i \in U} u_i^* \quad \text{(by constraint (1))}$$

$$z^* \le \sum_{ij \in E} \tilde{x}_{ij}^* \left( \sum_{q \in Q} a_{q,ij} u_q^* + u_i^* \right) \quad \text{(by constraint (2))}$$

$$z^* \le \sum_{ij \in E} \tilde{x}_{ij}^* (c_{ij} - r_{ij,u^*}) \quad \text{(from the definition of the reduced cost)}$$

$$z^* \le z^*_{|kl} - \sum_{ij \in E} \tilde{x}_{ij}^* r_{ij,u^*} \quad \left( \sum_{ij \in E} \tilde{x}_{ij}^* c_{ij} = z^*_{|kl} \text{ since } \tilde{x}^* \text{ is optimal for } (\mathcal{P}_{|kl}) \right)$$

Recall that $R_{kl} = z^*_{|kl} - z^*$. Thus from the last inequality, we have:

$$R_{kl} \ge \sum_{ij \in E} \tilde{x}_{ij}^* r_{ij,u^*}$$

$$R_{kl} \ge r_{kl,u^*} \quad (\text{since } \tilde{x}_{kl}^* = 1 \text{ and } \forall ij \in E, r_{ij,u^*} \ge 0 \text{ and } \tilde{x}_{ij}^* \ge 0) \quad \square$$

Previous properties are the basis for variable fixing [Nemhauser and Wolsey, 1988] which is performed in Mixed Integer Program (MIP) to detect some 0/1 variables that must be fixed to either 0 or 1 in any solution improving the best known. This detection relies on the reduced costs of the variables given by an optimal dual solution of the linear relaxation. Since a reduced cost can be lower than the exact reduced cost, this technique gives an incomplete filtering. Let's give an example of such an incomplete filtering for our two illustrative constraints.

**Example 5 (continued: reduced cost filtering).**

Consider $\bar{Z} = 1$ and note that each edge is labelled with its original cost $c_{ij}$ as well as its reduced cost $r_{ij,u}$ in the proposed dual solutions:

<figure><img src="image_3.png" /><figcaption>(b)</figcaption></figure>

<figure><img src="image_4.png" /></figure>
(a): $r_{(0,1),u} = 2 > \bar{Z}$ and $r_{(1,2),u} = 3 > \bar{Z}$. Thus, there's no assignment of cost lower than $\bar{Z}$ containing one of the edges (0, 1) or (1, 2).

Remark 1: Note that, one of the reduced costs is exact ($r_{(1,2),u} = R_{(1,2)}$), whereas one other is not ($r_{(0,1),u} < R_{(0,1)} = 3$).

Remark 2: $R_{(1,0)} = 3$ thus edge (1,0) is inconsistent event though its reduced cost in $u$ is not high enough to detect it.

(b): $r_{(s,2),u} = 2 > \bar{Z}$; $r_{(1,t),u} = 2 > \bar{Z}$ and $r_{(3,4),u} = 2 > \bar{Z}$. Thus there's no path of cost lower than $\bar{Z}$ passing through one of the arcs (s, 2), (1, t) or (3, 4).

Remark: $R_{(s,3)} = 2$ thus the arc (s, 3) is inconsistent but $r_{(s,t),u} = 0$ so this dual solution doesn't filter this value.

In the following, we show how to find a set of dual solutions that gives the exact reduced costs, to perform a complete filtering (i.e. achieve AC).

# 4 Analysis

In [German et al., 2017], it was shown that AC can be achieved by solving a single linear program (for a constraint without cost). At the opposite, for a constraint with costs, AC requires identifying each edge $kl$ for which all the solutions of ($P|_{kl}$) has a value greater than the fixed upper bound *i.e.* if $z_{|kl}^*$ is greater than $\bar{Z}$. Since $z_{|kl}^*$ can be computed as $z^* + R_{kl}$, exact reduced cost of an edge tells us if the corresponding value is consistent. In this section, we'll prove that for any edge $kl$, there exists an optimal dual solution for which the reduced cost of this edge equals its exact reduced cost. Therefore, AC can be achieved by computing such dual solutions. Moreover, we show how exact reduced costs can be identified in a given dual optimal solution. Finally, some results about the number of dual solutions needed are also given.

For the rest of the document, $kl$ will denote an arbitrary edge and $u^*$ an optimal dual solution.

**Property 2 (Existence of an optimal dual solution $u^*$ s.t. $r_{kl,u^*} = R_{kl}$).**
For any edge $kl \in E$, that belongs to at least one feasible primal solution, there exists an optimal dual solution $u^*$ such that $r_{kl,u^*} = R_{kl}$.

See proof.

This property justifies that a complete filtering (i.e. achieve AC) is possible using reduced costs. Moreover, it's not necessary to use one dual solution per edge.

The previous property also gives a dual a point of view on the result of [German et al., 2017]:

The constraint without costs $C$ can be encoded as a constraint with costs $WC$. Let $Z$ be equal to 0. The domains of the variables in $WC$ are defined with a complete variable-value graph $BG_{01}$ in which the edges of the original variable-value graph of $C$ are given a cost of 0 and the remaining edges (encoding values not present in the initial domains of $C$) are given a cost of 1. An edge belong to
a solution of C if and only if it belongs to a support of cost 0 in $BG_{01}$. Therefore any positive reduced cost exhibits an inconsistent edge and a single dual solution can rule out all inconsistent edges. Let $\mathcal{F}$ the set of inconsistent edges i.e. the edges that does not belong to any support for C.

**Property 3 (AC for C with one dual solution).**

There exists an optimal dual solution $\tilde{u}$ for WC in $BG_{01}$ such that

$$ \forall ij \in \mathcal{F} \iff r_{ij, \tilde{u}} > 0 $$

See proof.

Let's go back to the weighted case WC. A single dual solution can exhibit the exact reduced costs of many edges. The following property shows how to know which reduced costs are exact given an optimal dual solution.

**Property 4 (Characterisation of $r_{kl,u^*} = R_{kl}$).**

For an optimal dual solution $u^*$ and an edge $kl \in E$, the following propositions are equivalent:

i. $r_{kl,u^*} = R_{kl}$;

ii. $kl$ belongs to a support of C for which all the other reduced costs, with respect to $u^*$, are null. Moreover, this support has a minimal cost;

iii. for any support of minimal cost that contains $kl$, the reduced costs of all edges except $kl$, with respect to $u^*$, are null.

See proof.

**Example 6 (Characterization of exact reduced costs).**

Consider $\overline{Z} = 1$. We apply the previous property by identifying the exact reduced costs of a given dual optimal solution. The two cases of MINWALLDIFF and SHORTESTPATH are illustrated.

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>
(a): $S = \{(X_0, 0); (X_1, 1); (X_2, 2)\}$ is a support of minimal cost (its cost is 0).
$S' = \{(X_0, 2); (X_1, 0); (X_2, 1)\}$ is a support (of minimal cost) containing $(X_1, 0)$
i.e. a perfect matching of minimum weight using edge $(X_1, 0)$. Moreover the re-
duced costs of two edges out of three are null: $r_{(0,2),u^*} = r_{(2,1),u^*} = 0$. Thus
$r_{(1,0),u^*}$ is exact i.e. $R_{(1,0)} = r_{(1,0),u^*} = 2$.

(b): $S = \{(s, 1); (1, 2); (2, t)\}$ is a support (of minimal cost) containing $(2, t)$ with $r_{(s,1),u^*} = r_{(1,2),u^*} = 0$. Thus $R_{(2,t)} = r_{(2,t),u^*} = 2$. In other words, a shortest path using edge $(2, t)$ has a cost of 2.

For the specific MINWALLDIFF constraint, the conditions of the previous
property are met if and only if there exists a cycle, alternating with respect to a
support of minimal cost, such that all its reduced costs are 0 except one which is
exact. Similarly for SHORTESTPATH, if a path from *s* to *t* can be built using the
arcs of the null reduced costs to the exception of a single additional arc, then
the reduced cost of this additional arc is exact.

Note that the **optimality** of the reduced cost is checked by solving a **feasibility** problem. This latter problem is stated by distinguishing the edges of null reduced costs from the remaining edges. In particular, it does not use the precise value of the costs themselves. Very similarly, optimality is reached in a primal dual algorithm when a feasible solution is obtained with the edges of null reduced costs alone. For instance, the Hungarian algorithm stops when a maximum matching of the graph of null reduced costs has a cardinality of *n*. The costs are not used when checking this condition, they have been *combinatorialized* as explain in [Papadimitriou and Steiglitz, 1998]. From this point of view, we believe property 4 extends complementary slackness very naturally to deal with arc-consistency.

For a given dual solution $u$, let's denote by $\mathcal{R}_u = \{ij \in E \mid r_{ij,u} = R_{ij}\}$, the set of edges whose reduce costs are exacts with respect to $u$. A set or a family $\{u^t\}_{t \in \mathcal{T}}$ of dual solutions is said to be **complete** if $\bigcup_{t \in \mathcal{T}} \mathcal{R}_{u^t} = E$ i.e. any exact reduced cost is available from at least one solution of this family. To minimize the number of calls to the simplex algorithm in order to compute arc-consistency, we are interested in minimal complete set of dual solutions family $\mathcal{T}$ of minimal cardinality. The next property exhibits sets of edges for which a single dual solution provides all the exact reduced costs.

Two edges are said **incompatible** if they do not belong together to a feasible
primal solution.

**Property 5 (Incompatible edges).**

For any set $\mathcal{I}$ of pairwise incompatible edges, there exists an optimal dual solution that provides the exact reduced cost of each edge of $\mathcal{I}$.

See proof.

Domains are simple examples of sets of incompatible edges since, in a feasible
solution, a variable takes a single value. Therefore no two values of its domain
can be used together and from the variable-value graph point of view, for each
$k \in U$, the set $S_k = \{kj \in E\} = \{kj \mid j \in D(X_k)\}$ is a set of incompatible edges.
Let $u_k^*$ be an optimal dual solution for which all reduced costs of $S_k$ are exact. Then, $S = \{u_k^* | k \in U\}$ is a complete set of dual solutions. This complete set is simply based on the domains and referred to as $S$. Note that there might be alternative ways to obtain a complete set of dual solutions and we illustrate it below with the case of SHORTESTPATH:

**Example 7 (Sets of incompatible edges).**

For MINWEIGHTEDALLDIFF, the sets $S_i$ are sets of incompatibles edges:

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

For each $S_i$ there exists a dual solution $u_i$ that gives all the exact reduced costs for edges in $S_i$. Thus $S = \{u_i | 0 \le i \le 3\}$ is a complete set of dual solutions of cardinality 4.

For SHORTESTPATH, the topological layers $T_i$ are sets of incompatibles edges:

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

For each $T_i$ there exists a dual solution $u_i$ that gives all the exact reduced costs for arcs in $T_i$. Thus $\{u_i | 0 \le i \le 2\}$ is a complete set of dual solutions of cardinality 3. Note that the complete set $S$ based on the domains would require 5 dual solutions.

In order to minimise the number of calls to the simplex algorithm, we are interested in complete families of minimum cardinality. An upper bound and a worst case lower bound of this cardinality are given in the following properties:

**Property 6 (Complete set of n dual solutions).**

There exists a complete set of $n$ dual optimal solutions (the complete set $S$). See proof.

This set is possibly not minimal as seen in example 7 for SHORTESTPATH where $n = 5$ and the set of layers $\{T_i\}$ is a complete family of cardinality 3. Finally, we can show that, in the worst case, the cardinality of such a family is at least $n$. We use the MINWALLDIFF to do the proof which was presented in [Claus et al., 2020] but can now be simplified:

**Property 7.** In the worst case, for WC, $n$ optimal dual solutions are needed to obtain all exact reduced costs.
*Proof.* If we consider the MINWALLDIFF constraint, and the instance where

$$c_{ij} = \begin{cases} 0 & \text{if } i \le j \\ 1 & \text{otherwise} \end{cases}$$

<figure><img src="image_11.png" /></figure>

Let $\mathcal{L} = \{(i, i-1) | \forall 1 \le i \le n\} \cup \{(0, n)\}$. Let's show that the reduced costs of the edges of $\mathcal{L}$ can not be pairwise exact for the same dual solution.

For any edge $kl \in \mathcal{L}$, $R_{kl} = 1$ and $\mathcal{L}$ is a support of minimal cost (its cost is 1) containing this edge. From property 4 iii, if $u^*$ is an optimal dual solution with $r_{kl,u^*} = R_{kl}$, the reduced costs for the edges of $\mathcal{L} \setminus \{kl\}$ must be null. Thus only one exact reduced cost of $\mathcal{L}$ can be given by an optimal dual solution and at least $|\mathcal{L}| = n$ dual solutions are needed to obtain all exact reduced costs. $\square$

Since, for any edge $kl$ and any optimal dual solution $u^*$, $r_{kl,u^*} \le R_{kl}$, for a set of incompatible edges $\mathcal{I}$, if we modify $u^*$ to maximize $\sum_{ij \in \mathcal{I}} r_{kl,u^*}$, keeping $u^*$ optimal, we will obtain an optimal dual solution that provides the exact reduced costs for all edges of $\mathcal{I}$. This technique is the foundation of the algorithm proposed in the next section.

# 5 An LP based algorithm

In [German et al., 2017], it was proved that arc-consistency can be reached by solving only one LP for a constraint without cost. For constraints with costs, if $\mathcal{T} = \{\mathcal{I}_i\}$ is a set of sets of pairwise incompatible edges s.t. $E = \cup_i \mathcal{I}_i$, we have shown that arc-consistency can be reached by computing $|\mathcal{T}|$ dual solutions.

For a given set of incompatibles edges, $\mathcal{I}$, we can modify $(\mathcal{D})$ to obtain such a solution which is appropriate for filtering.

$$ (\mathcal{D}_{\mathcal{I}}^{z}) \left\{ \begin{array}{ll} \max_{u} \omega_{\mathcal{I}}^{z} = \sum_{kl \in \mathcal{I}} r_{kl,u} & \\ \text{s.t.} \quad u_i + \sum_{q \in Q} a_{q,ij} u_q \le c_{ij} & \forall ij \in E \\ & \sum_{q \in Q} b_q u_q + \sum_{i \in U} u_i = z^* & \\ & u_q \ge 0 & \forall q \in Q \\ & u_i \in \mathbb{R} & \forall i \in U \end{array} \right. \quad (5) $$
All the constraints of (D) are included in (Dz) and the additional constraint (5) ensure the D-optimality of the obtained solution. Property 5 shows that there exists an optimal solution of (D) in which all exact reduced costs of I are reached. Thanks to the property 1, the maximality of the objective function, which is the sum of the reduced costs of I, ensures that such a solution is obtained.

A drawback of (Dz) is the preliminary computation of z* for constraint (5). Constraint (5) also considerably changes the formulation of the original dual (D) which might be inconvenient when a dedicated algorithm is available for solving (D). But (Dz) can be upgraded to (DI) in which the sum of the reduced costs for I and the objective function of (D) are gathered in a new objective function. The preliminary computation of z* is no more necessary.

$$ (D_I) \left\{ \begin{array}{ll} \max_{u} \omega_I = \sum_{q \in Q} b_q u_q + \sum_{i \in U} u_i + \frac{1}{|I|} \sum_{kl \in I} r_{kl,u} & \\ \text{s.t.} \quad u_i + \sum_{q \in Q} a_{q,ij} u_q \le c_{ij} & \forall ij \in E \quad (x_{ij}) \\ r_{kl,u} \le M & \forall kl \in I \quad \text{where } M > \max_{kl \in I} z_{kl}^* \text{ is fixed} \quad (x'_{kl}) \\ u_q \ge 0 & \forall q \in Q \\ u_i \in \mathbb{R} & \forall i \in U \end{array} \right. $$

**Property 8 (Usefulness of (DI)).**

If u* is an optimal solution for (DI), we have $\forall ij \in I$,

$$ \sum_{q \in Q} b_q u_q^* + \sum_{i \in U} u_i^* + r_{ij,u^*} = z_{ij}^* $$

See proof.

Moreover, the original optimal value z* is available as a side product when a set of incompatible edges is known to contain at least one edge of an optimal solution.

**Corollary 1.** If I contains at least an edge belonging to an optimal solution and u* is an optimal solution for (DI), then

$$ z^* = \sum_{q \in Q} b_q u_q^* + \sum_{i \in U} u_i^* + \min_{ij \in I} r_{ij,u^*} $$

Property 8 and its corollary gives a simple algorithm to compute a lower bound for Z and to achieve arc-consistency:
**Algorithm 1 ACbyLP**

1: Unmark all variable-value edges $ij \in E$

2: $Zlb = +\infty$

3: let $\mathcal{T}$ be a complete family of sets with incompatible edges

4: **for** each $I \in \mathcal{T}$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $I$ has unmarked edges **then**

6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute $\tilde{u}$ an optimal solution of $(\mathcal{D}_I)$

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;let $w = \sum_{q \in Q} b_q \tilde{u}_q + \sum_{i \in U} \tilde{u}_i$

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Zlb = \min \left\{ Zlb; w + \min_{ij \in I} r_{ij, \tilde{u}} \right\}$

9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $kl \in E$, $kl$ unmarked **do**

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $w + r_{kl, \tilde{u}} > \bar{Z}$ **then**

11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Mark $kl$ as inconsistent.

12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $kl \in I$, $kl$ unmarked **do**

13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $w + r_{kl, \tilde{u}} \le \bar{Z}$ **then**

14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Mark $kl$ as consistent.

15: Update $\bar{Z}$ with $Zlb$.

Algorithm 1 considers the sets $\mathcal{I}$ of incompatible edges, one by one. For each $\mathcal{I}$, $(\mathcal{D}_{\mathcal{I}})$ is solved to get the exact reduced cost of the edges of $\mathcal{I}$. Note that the dual solution obtained is used to filter the **entire** domains. The set of edges whose status consistent/inconsistent have been definitely established are marked. Algorithm 1 does not specify how the family of incompatible sets should be built but the set of domains can be used by default. Moreover, the algorithm can be stopped at any time providing valid filtering for the whole domains. The order to consider the sets of $\mathcal{T}$ is also left unspecified and many strategies can be imagined. An instance of such an algorithm was experimented in [Claus et al., 2020] for the MINWALLDIFF constraint.

## Conclusion

It was shown in [German et al., 2017], how arc-consistency could be achieved for a global constraint without cost (a satisfaction problem) with an ideal LP formulation by looking for an interior point. Such an interior point can be found by solving a single linear program. The present work extends this analysis to global constraints with assignment costs (an optimization problem) demonstrating that arc-consistency can be done by solving $n$ linear programs in the worst case, one for each variable.

The work of [German et al., 2017] had a primal view point and we chose to take a dual view point to generalize it by revisiting reduced cost based filtering. From this point of view, we established that the reduced cost of a single dual solution are needed to get arc-consistency for a satisfaction problem whereas $n$ dual solutions are needed for an optimization problem (always assuming that both have an ideal formulation). To our knowledge, it provides the first analysis
of reduced cost filtering which has often been used in the past starting with the work of [Focacci et al., 1999].

This analysis established a number of basic results relating reduced costs and arc-consistency by answering the following questions: does there always exist a dual solution that can prove a value consistent/inconsistent (property 2) ? Given a dual solution, how do we know which values are proved consistent/inconsistent (property 3) ? Can we identify simple conditions for a family of dual solutions to ensure arc-consistency (property 6) ? The key result of this paper is probably the characterization given by property 3 which states a complementary slackness condition for exact filtering (as opposed to just optimality). This might open a way to design a generic primal/dual filtering algorithm for a large class of global constraints with an ideal LP formulation. We intend to investigate further the algorithmic side as future work.
Annex: proofs

Proof (Prop. 2: Existence of an optimal dual solution that gives R$_{kl}$).

Let's build explicitly such a dual solution:

We call $(\tilde{P})$ the primal problem identical to $(\mathcal{P})$ except for the cost of the edge $kl$:

$$ \begin{cases} \tilde{c}_{kl} = c_{kl} - R_{kl} \\ \tilde{c}_{ij} = c_{ij} \quad \forall ij \in E \setminus \{kl\} \end{cases} $$

Since $kl$ belongs to at least one primal solution, $\tilde{c}_{kl}$ is finite. Let $\tilde{z}^*$ be the optimal value of $(\tilde{P})$, and $\tilde{u}^*$ any optimal solution of $(\tilde{D})$, the dual of $(\tilde{P})$. We show below that $\tilde{u}^*$ is also an optimal solution for $(\tilde{D})$ and gives the exact reduced cost for $kl$:

$$ - z_{|kl}^* \geq z^* \text{ implies } R_{kl} \geq 0 \text{ and } \tilde{c}_{kl} \leq c_{kl}. $$

$$ \text{Consequently, } \begin{cases} \tilde{u}_k^* + \sum_{q \in Q} a_{q,kl} \tilde{u}_q^* \leq \tilde{c}_{kl} \leq c_{kl} \\ \tilde{u}_i^* + \sum_{q \in Q} a_{q,ij} \tilde{u}_q^* \leq \tilde{c}_{ij} = c_{ij} \quad \forall ij \in E \setminus kl \end{cases} $$

and $\tilde{u}^*$ is a feasible solution for $(\mathcal{D})$.

- Since $(\tilde{P})$ is an ideal formulation, it has at least one optimal integer solution $\tilde{x}^*$. Suppose that the value of this solution is lower than $z^*$ ($\tilde{z}^* < z^*$) (it can't be greater since the costs are lower in $(\tilde{P})$).

• On one hand if $\tilde{x}_{kl}^* = 0$, this solution would have the same cost $\tilde{z}^*$ in $(\mathcal{P})$ and that contradicts the optimality of $z^*$

• On the other hand if $\tilde{x}_{kl}^* = 1$, since $\tilde{c}_{kl}$ is the only modified cost and is used exactly once in the objective function, the value of this solution in $(\mathcal{P})$ is $\tilde{z}^* + R_{kl} = \tilde{z}^* + z_{|kl}^* - z^*$
$$ \begin{aligned} & < z^* + z_{|kl}^* - z^* \\ & < z_{|kl}^* \end{aligned} $$

and that's in contradiction with the optimality of $z_{|kl}^*$ for a solution containing $kl$.

Therefore $\tilde{z}^* = z^*$ and $\tilde{u}^*$ is an optimal solution for $(\mathcal{D})$.

- Finally, an optimal solution for $(\mathcal{P}_{|kl})$ is a solution for $(\tilde{P})$ of value $z_{|kl}^* - R_{kl} = z^*$, thus it's an optimal solution for $(\tilde{P})$ with $x_{kl} = 1$. Thanks to the complementary slackness theorem, the constraint associated with $x_{kl}$ in $(\tilde{D})$ must be tight.

$$ \begin{align*} \text{Therefore} \quad & u_k + \sum_{q \in Q} a_{q,kl} \tilde{u}_q^* = \tilde{c}_{kl} \\ \iff & u_k + \sum_{q \in Q} a_{q,kl} \tilde{u}_q^* = c_{kl} - R_{kl} \\ \iff & c_{kl} - u_k - \sum_{q \in Q} a_{q,kl} \tilde{u}_q^* = R_{kl} \end{align*} $$

That means exactly $r_{kl}, \tilde{u}^* = R_{kl}$.
□

Proof (Prop. 3: AC for C with one dual solution).

Since the {0,1} encoding of (P) implies $R_{ij} \ge 1 \ \forall ij \in \mathcal{F}$, we can consider a set of optimal dual solutions $\{\tilde{u}^{ij} : ij \in \mathcal{F}\}$ with $r_{ij,\tilde{u}^{ij}} \ge 1$. One can remark that $\forall kl \notin \mathcal{F}$, $R_{kl} = 0$ and thus, $\forall ij \in \mathcal{F}$, $r_{kl,\tilde{u}^{ij}} = 0$

Let $\tilde{u}$ be the average solution of the previous set: $\tilde{u} = \frac{1}{|\mathcal{F}|} \sum_{ij \in \mathcal{F}} \tilde{u}^{ij}$.

This solution is feasible, optimal, and $r_{ij,\tilde{u}} \begin{cases} > 0 & \forall ij \in \mathcal{F} \\ = 0 & \forall ij \notin \mathcal{F} \end{cases}$

□

Proof (Prop. 4: Characterisation of $r_{kl,u^*} = R_{kl}$).

i. $\implies$ ii.: Consider $u^*$, an optimal dual solution s.t. $r_{kl,u^*} = R_{kl}$.

We have $R_{kl} = r_{kl,u^*} = c_{kl} - u_k^* - \sum_{q \in Q} a_{q,kl} u_q^*$.

Thus, with the notations from the previous proof,

$$\tilde{c}_{kl} = c_{kl} - R_{kl} = u_k^* + \sum_{q \in Q} a_{q,kl} u_q^*$$

Since the costs are unchanged for all other edges, $u^*$ respects the constraint (4) and is feasible for $(\tilde{D})$.

Moreover, we have $\tilde{z}^* = z^*$, and $u^*$ is optimal for $(\tilde{D})$.

Let $S$ be an optimal support for $(\tilde{P})$ that contains $kl$. From the complementary slackness theorem between $(\tilde{P})$ and $(\tilde{D})$, we have $\tilde{r}_{ij,u^*} = 0$, $\forall ij \in S$ which implies $r_{ij,u^*} = 0$, $\forall ij \in S \setminus \{kl\}$.

ii. $\implies$ iii.: if there exists a support $S$ containing $kl$ such that all its reduced costs are null except for $kl$, let $(\tilde{P})$ be the primal problem identical to $(P)$ except for the cost of the edge $kl$:

$$\begin{cases} \dot{c}_{kl} = c_{kl} - r_{kl,u^*} \\ \dot{c}_{ij} = c_{ij} \quad \forall ij \in E \setminus \{kl\} \end{cases}$$

By construction, $u^*$ is feasible for $(\tilde{D})$, the dual problem of $(\tilde{P})$ (and the constraint (4) is tight for $kl$). In $(\tilde{D})$, $\dot{r}_{ij,u^*} = 0$, $\forall ij \in S$ and thus, $u^*$ is an optimal dual solution for $(\tilde{D})$. Therefore, $S$ is an optimal support for $(P|_{kl})$ and $r_{kl,u^*} = R_{kl}$.

Let $S'$ be an other optimal support for $(P|_{kl})$. Then it's an optimal support for $(\tilde{P})$ and so, $\forall ij \in S' \setminus \{kl\}$, $r_{ij,u^*} = \dot{r}_{ij,u^*} = 0$.

iii. $\implies$ i.: Let $S$ be a support of minimal cost $z^*|_{kl}$ for $(P|_{kl})$ with all its reduced costs null except those of $kl$. $S$ is thus a support of minimal cost for $(\tilde{P})$. As we have shown previously, $u^*$ is optimal for $(\tilde{D})$, and the cost of $S$ in $(\tilde{P})$ is $z^*$. The difference between the costs of $S$ for $(P)$ and $(\tilde{P})$ equals the difference between $c_{kl}$ and $\dot{c}_{kl}$ since it's the only cost which differs. Eventually we have $R_{kl} = z^*|_{kl} - z^* = c_{kl} - \dot{c}_{kl} = r_{kl,u^*}$

□
Proof (Prop. 5: Incompatible edges).

We explicitly build $\tilde{u}_I^*$, the optimal dual solution that gives all exact reduced costs of the edges of $\mathcal{I}$ from the modified primal problem $(\tilde{\mathcal{P}}_I)$ which is identical to $(\mathcal{P})$ to the exception of the costs related to the edges in $\mathcal{I}$. More precisely,

$$ \tilde{c}_{ij} = \begin{cases} c_{ij} - R_{ij} & \forall ij \in \mathcal{I} \\ c_{ij} & \forall ij \in E \setminus \mathcal{I} \end{cases} $$

Let $\tilde{u}_I^*$ be an optimal solution for $(\tilde{\mathcal{D}}_I)$, the dual of $(\tilde{\mathcal{P}}_I)$, and $\tilde{z}_I^*$ its value. We must show that $\tilde{u}_I^*$ is feasible and optimal for $(\mathcal{D})$ while providing the exact reduced costs of all edges connected to $k$. The proof is nearly identical to the one of the property 2:

- Feasibility of $\tilde{u}^*$ for $(\mathcal{D})$: identical proof

- With lower costs in $(\tilde{\mathcal{P}}_I)$, $\tilde{z}^*$ can't be greater than $z^*$. We suppose that $\tilde{z}^* < z^*$.

In any primal optimal solution $\tilde{x}^*$ of $(\tilde{\mathcal{P}}_I)$, since two edges of $\mathcal{I}$ can't belong to such a solution, and in respect to constraint (2) all $\tilde{x}_{ij}^*$ for $ij \in \mathcal{I}$ are equal to zero except one, $\tilde{x}_{kl}^* = 1$. The value of $\tilde{x}^*$ in $(\mathcal{P})$ is therefore $\tilde{z}^{k*} + R_{kl} = \tilde{z}^* + z_{kl}^* - z^*$

$$ < z^* + z_{kl}^* - z^* $$

$$ < z_{kl}^* $$

That's impossible by definition of $z_{kl}^*$ and thus we have $\tilde{z}^* = z^*$.

- $\forall ij \in \mathcal{I}, r_{ij, \tilde{u}^*} = R_{ij}$: identical proof for each $ij \in \mathcal{I}$, replacing $(\tilde{\mathcal{P}})$ by $(\tilde{\mathcal{P}}_I)$ and $(\tilde{\mathcal{D}})$ by $(\tilde{\mathcal{D}}_I)$

□

Proof (Prop. 6: Complete set of dual solutions).

For each $k \in U$, we set $\mathcal{I}_k = \{kj \in E\}$. Thanks to the constraint (2), two edges of $\mathcal{I}_k$ can't belong to the same primal solution. Therefore, the prop. 5 proves that there exists an optimal dual solution $\tilde{u}_{\mathcal{I}_k}^*$ that gives all exact reduced costs for the edges of $\mathcal{I}_k$.

Since $E = \bigcup_{k \in U} \mathcal{I}_k$, $\{\tilde{u}_{\mathcal{I}_k}^*\}_{k \in U}$ is a complete set of optimal dual solutions of cardinality $|U| = n$. □

Proof (Prop. 8: Usefulness of $(\mathcal{D}_I)$).

- We firstly prove that $\omega_I^* = z^* + \frac{1}{|\mathcal{I}|} \sum_{kl \in \mathcal{I}} R_{kl}$:

• A $\mathcal{D}_I^z$-optimal solution, $u_1$, is also $\mathcal{D}_I$-feasible, and by construction, $\sum_{q \in Q} b_q u_{1q} + \sum_{i \in U} u_{1i} = z^*$ and $\forall kl \in \mathcal{I}, r_{kl, u_1} = R_{kj}$.

Therefore, $\omega_I^* \ge \sum_{q \in Q} b_q u_{1q} + \sum_{i \in U} u_{1i} + \frac{1}{|\mathcal{I}|} \sum_{kl \in \mathcal{I}} r_{kl, u_1}$
$$ \ge z^* + \frac{1}{|\mathcal{I}|} \sum_{kl \in \mathcal{I}} R_{kl} $$
• A $\mathcal{D}_I$-feasible solution, $u_2$, is also $\mathcal{D}$-feasible solution

$$
\begin{align*}
\text{Thus,} \quad & \sum_{q \in Q} b_q u_{2q} + \sum_{i \in U} u_{2i} + r_{kl, u_2} \le z^* + R_{kl} \quad \forall kl \in \mathcal{I} \\
\Rightarrow \quad & |\mathcal{I}| \left( \sum_{q \in Q} b_q u_{2q} + \sum_{i \in U} u_{2i} \right) + \sum_{kl \in \mathcal{I}} r_{kl, u_2} \le |\mathcal{I}| z^* + \sum_{kl \in \mathcal{I}} R_{kl} \\
\Rightarrow \quad & \sum_{q \in Q} b_q u_{2q} + \sum_{i \in U} u_{2i} + \frac{1}{|\mathcal{I}|} \sum_{kl \in \mathcal{I}} r_{kl, u_2} \le z^* + \frac{1}{|\mathcal{I}|} \sum_{kl \in \mathcal{I}} R_{kl} \\
\Rightarrow \quad & \omega_{\mathcal{I}} \le z^* + \frac{1}{|\mathcal{I}|} \sum_{kl \in \mathcal{I}} R_{kl} \\
\Rightarrow \quad & \omega_{\mathcal{I}}^* \le z^* + \frac{1}{|\mathcal{I}|} \sum_{kl \in \mathcal{I}} R_{kl}
\end{align*}
$$

$$
\text{Thus, } \omega_{\mathcal{I}}^{*} = z^{*} + \frac{1}{|\mathcal{I}|} \sum_{kl \in \mathcal{I}} R_{kl}
$$

- We can now prove the property:

$$
\text{Let } u_3 \text{ be an optimal solution for } (\mathcal{D}_I), \\
\forall ij \in E, \sum_{q \in Q} b_q u_{3q} + \sum_{i \in U} u_{3i} + r_{ij, u_3} \le z^* + R_{ij}.
$$

$$
\text{Suppose that } \exists \tilde{kl} \in \mathcal{I} \text{ s.t. } \sum_{q \in Q} b_q u_{3q} + \sum_{i \in U} u_{3i} + r_{\tilde{kl}, u_3} < z^* + R_{\tilde{kl}}.
$$

$$
\text{Since } |\mathcal{I}| \omega_{\mathcal{I}}^* = |\mathcal{I}| z^* + \sum_{kl \in \mathcal{I}} R_{kl},
$$

$$
\text{that implies } \sum_{kl \in \mathcal{I} \setminus \tilde{kl}} \left( \sum_{q \in Q} b_q u_{3q} + \sum_{i \in U} u_{3i} + r_{kl, u_3} \right) > \sum_{kl \in \mathcal{I} \setminus \tilde{kl}} (z^* + R_{kl}) \text{ which}
$$

is impossible.

$$
\begin{align*}
\text{Thus, } \forall kl \in \mathcal{I}, \quad & \sum_{q \in Q} b_q u_{3q} + \sum_{i \in U} u_{3i} + r_{kl, u_3} = z^* + R_{kl} \\
& = z^*_{|kl}
\end{align*}
$$

□

References

Achterberg et al., 2008. Achterberg, T., Berthold, T., Koch, T., and Wolter, K. (2008). Constraint integer programming: A new approach to integrate cp and mip. In *International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming*, pages 6–20. Springer.

Aron et al., 2004. Aron, I., Hooker, J. N., and Yunes, T. H. (2004). Simpl: A system for integrating optimization techniques. In *International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming*, pages 21–36. Springer.

Balafrej et al., 2016. Balafrej, A., Bessiere, C., Paparrizou, A., and Trombettoni, G. (2016). Adapting consistency in constraint solving. In *Data Mining and Constraint Programming*, pages 226–253. Springer.
Bockmayr and Kasper, 1998. Bockmayr, A. and Kasper, T. (1998). Branch and in-
fer: A unifying framework for integer and finite domain constraint programming.
*INFORMS Journal on Computing*, 10(3):287–300.

Caseau and Laburthe, 2000. Caseau, Y. and Laburthe, F. (2000). Solving various weighted matching problems with constraints. *Constraints*, 5(1/2):141–160.

Cauwelaert and Schaus, 2017. Cauwelaert, S. V. and Schaus, P. (2017). Efficient filtering for the resource-cost alldifferent constraint. *Constraints*, 22(4):493–511.

Claus et al., 2020. Claus, G., Cambazard, H., and Jost, V. (2020). Analysis of reduced costs filtering for alldifferent and minimum weight alldifferent global constraints. In Giacomo, G. D., Catalá, A., Dilkina, B., Milano, M., Barro, S., Bugarín, A., and Lang, J., editors, *ECAI 2020 - 24th European Conference on Artificial Intelligence*, volume 325 of *Frontiers in Artificial Intelligence and Applications*, pages 323–330. IOS Press.

Focacci et al., 1999. Focacci, F., Lodi, A., and Milano, M. (1999). Cost-based domain filtering. In *International conference on principles and practice of constraint programming*, pages 189–203. Springer.

Focacci et al., 2002. Focacci, F., Lodi, A., and Milano, M. (2002). Embedding relaxations in global constraints for solving tsp and tsptw. *Ann. Math. Artif. Intell.*, 34(4):291–311.

German et al., 2017. German, G., Briant, O., Cambazard, H., and Jost, V. (2017). Arc consistency via linear programming. In *International Conference on Principles and Practice of Constraint Programming*, pages 114–128. Springer.

Hooker, 2006. Hooker, J. N. (2006). Operations research methods in constraint programming. In Rossi, F., van Beek, P., and Walsh, T., editors, *Handbook of Constraint Programming*, chapter 15. Elsevier.

Nemhauser and Wolsey, 1988. Nemhauser, G. L. and Wolsey, L. A. (1988). *Integer and Combinatorial Optimization*. Wiley-Interscience, New York, NY, USA.

Papadimitriou and Steiglitz, 1998. Papadimitriou, C. H. and Steiglitz, K. (1998). *Combinatorial optimization: algorithms and complexity*. Courier Corporation.

Refalo, 1999. Refalo, P. (1999). Tight cooperation and its application in piecewise linear optimization. In *International Conference on Principles and Practice of Constraint Programming*, pages 375–389. Springer.

Refalo, 2000. Refalo, P. (2000). Linear formulation of constraint programming models and hybrid solvers. In *International Conference on Principles and Practice of Constraint Programming*, pages 369–383. Springer.

Rodosek et al., 1999. Rodosek, R., Wallace, M. G., and Hajian, M. T. (1999). A new approach to integrating mixed integer programming and constraint logicprogramming. *Annals of Operations Research*, 86(0):63–87.

Sellmann, 2002. Sellmann, M. (2002). An arc-consistency algorithm for the minimum weight all different constraint. In *International conference on principles and practice of constraint programming*. Springer.