Djamal Habet
email: djamal.habet@lis-lab.fr

Cyril Terrioux
email: cyril.terrioux@lis-lab.fr

The variable ordering heuristic is an important module in algorithms dedicated to solve Constraint Satisfaction Problems (CSP), while it impacts the efficiency of exploring the search space and the size of the search tree. It also exploits, often implicitly, the structure of the instances. In this paper, we propose Conflict-History Search (CHS), a dynamic and adaptive variable ordering heuristic for CSP solving. It is based on the search failures and considers the temporality of these failures throughout the solving steps. The exponential recency weighted average is used to estimate the evolution of the hardness of constraints throughout the search. The experimental evaluation on XCSP3 instances shows that integrating CHS to solvers based on MAC (Maintaining Arc Consistency) and BTD (Backtracking with Tree Decomposition) achieves competitive results and improvements compared to the state-of-the-art heuristics. Beyond the decision problem, we show empirically that the solving of the constraint optimization problem (COP) can also take advantage of this heuristic.

Introduction

The Constraint Satisfaction Problem (CSP) is an important formalism in Artificial Intelligence (AI) which allows to model and efficiently solve problems that occur in various fields, both academic and industrial (e.g. [START_REF] Cabon | Radio Link Frequency Assignment[END_REF][START_REF] Holland | Weighted Super Solutions for Constraint Programs[END_REF][START_REF] Rossi | Handbook of Constraint Programming[END_REF][START_REF] Simonin | Scheduling Scientific Experiments for Comet Exploration[END_REF]). A CSP instance is defined on a set of variables, which must be assigned in their respective finite domains. Variable assignments must satisfy a set of constraints, which express restrictions on assignments. A solution is an assignment of each variable, which satisfies all constraints.

CSP solving is often based on backtracking algorithms. In recent years, it has made significant progress thanks to research on several aspects. In particular, considerable effort is devoted to global constraints, filtering techniques, learning and restarts [START_REF] Rossi | Handbook of Constraint Programming[END_REF]. An important component in CSP solvers is the variable ordering heuristic. Indeed, the corresponding heuristics define, statically or dynamically, the order in which the variables will be assigned and, thus, the way that the search space will be explored and the size of the search tree. The problem of finding the best variable to assign (i.e. one which minimizes the search tree size) is NP-Hard [START_REF] Liberatore | On the complexity of choosing the branching literal in DPLL[END_REF].

Many heuristics have been proposed (e.g. [START_REF] Bessière | Neighborhood-based variable ordering heuristics for the constraint satisfaction problem[END_REF][START_REF] Bessière | MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems[END_REF][START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF][START_REF] Brélaz | New Methods to Color Vertices of a Graph[END_REF][START_REF] Geelen | Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems[END_REF][START_REF] Golomb | Backtrack programming[END_REF][START_REF] Hebrard | Explanation-Based Weighted Degree[END_REF][START_REF] Michel | Activity-based search for black-box constraint programming solvers[END_REF][START_REF] Refalo | Impact-based search strategies for constraint programming[END_REF]) aiming mainly to satisfy the first-fail principle [START_REF] Haralick | Increasing tree search efficiency for constraint satisfaction problems[END_REF] which advises "to succeed, try first where you are likely to fail". Nowadays, the most efficient heuristics are adaptive and dynamic [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF][START_REF] Geelen | Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems[END_REF][START_REF] Hebrard | Explanation-Based Weighted Degree[END_REF][START_REF] Michel | Activity-based search for black-box constraint programming solvers[END_REF][START_REF] Refalo | Impact-based search strategies for constraint programming[END_REF], where the variable ordering is defined according to the collected information since the beginning of the search. For instance, some heuristics consider the effect of filtering when decisions and propagations are applied [START_REF] Michel | Activity-based search for black-box constraint programming solvers[END_REF][START_REF] Refalo | Impact-based search strategies for constraint programming[END_REF]. dom/wdeg is one of the simplest, the most used and efficient variable ordering heuristic [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF]. It is based on the hardness of constraints and, more specifically, reflects how often a constraint fails. It uses a weighting process to focus on the variables appearing in constraints with high weights which are assumed to be hard to satisfy. In addition, some heuristics, such as LC [START_REF] Lecoutre | Last Conflict Based Reasoning[END_REF] and COS [START_REF] Gay | Conflict Ordering Search for Scheduling Problems[END_REF], attempt to consider the search history while they require the use of auxiliary heuristics.

In this paper, we propose Conflict-History Search (CHS), a new dynamic and adaptive variable ordering heuristic for CSP solving. It is based on the history of search failures, which happen as soon as a domain of a variable is emptied after constraint propagations. The goal is to reward the scores of constraints that have recently been involved in conflicts and therefore to favor the variables appearing in these constraints. The scores of constraints are estimated on the basis of the exponential recency weighted average technique, which comes from reinforcement learning [START_REF] Sutton | Reinforcement Learning: An Introduction, 1st edn[END_REF]. It was also recently used in defining powerful branching heuristics for solving the satisfiability problem (SAT) [START_REF] Liang | Exponential Recency Weighted Average Branching Heuristic for SAT Solvers[END_REF][START_REF] Liang | Learning Rate Based Branching Heuristic for SAT Solvers[END_REF]. We have integrated CHS in solvers based on MAC (Maintaining Arc Consistency) [START_REF] Sabin | Contradicting Conventional Wisdom in Constraint Satisfaction[END_REF] and BTD (Backtracking with Tree-Decomposition) [START_REF] Jégou | Hybrid backtracking bounded by tree-decomposition of constraint networks[END_REF]. The empirical evaluation on XCSP3 instances 1 shows that CHS is competitive and brings improvements to the state-of-the-art heuristics. In addition, this evaluation provides an extensive study of the performance of state-of-the-art search heuristics on more than 12,000 instances. Finally, we also study, from a practical viewpoint, the benefits of the proposed heuristic for solving constraint optimization problems (COP).

The paper is structured as follows. Section 2 includes some necessary definitions and notations. Section 3 presents and details our contribution, the CHS variable ordering heuristic. Section 4 describes related work on variable ordering heuristics for CSP and on branching heuristics for the satisfiability problem. CHS is evaluated experimentally and compared to the main powerful heuristics of the state-of-the-art on CSP instances in Section 5 and on COP ones in Section 6. Finally, we conclude and give some perspectives on extending the application of CHS.

Preliminaries

This section is dedicated to the definition of CSP and Exponential Recency Weighted Average, which we use to propose our heuristic.

Constraint Satisfaction Problem

An instance of a Constraint Satisfaction Problem (CSP) is given by a triple (X, D, C), such that: X = {x 1 , • • • , x n } is a set of n variables, D = {D 1 , ..., D n } is a set of finite domains, and C = {c 1 , • • • , c e } is a set of e constraints. The domain of each variable x i is D i . Each constraint c j is defined by its scope S(c j ) and its compatibility relation R(c j ), where S(c j ) = {x j1 , • • • , x j k } ⊆ X and R(c j ) ⊆ D j1 × • • • × D j k . The constraint satisfaction problem asks for an assignment of the variables x i ∈ X within their respective domains D i (1 ≤ i ≤ n) that satisfies each constraint in C. Such consistent assignment is a solution. Checking whether a CSP instance has a solution is NP-complete [START_REF] Rossi | Handbook of Constraint Programming[END_REF].

In the past decades, many solvers have been proposed for solving CSPs. Generally, from a practical viewpoint, they succeed in solving efficiently a large kind of instances despite of the NP-completeness of the CSP decision problem. In most cases, they rely on optimized backtracking algorithms whose time complexity is at least in O(e.d n ) where d denotes the size of the largest domain. In order to ensure an efficient solving, they commonly exploit jointly several techniques (see [START_REF] Rossi | Handbook of Constraint Programming[END_REF] for more details) among which we can cite:

• variable ordering heuristics which aim to guide the search by choosing the next variable to assign (we discuss about some state-of-the-art heuristics in Section 4),

• constraint learning and non-chronological backtracking which aim to avoid some redundancies during the exploration of the search space,

• filtering techniques enforcing some consistency level which aim to simplify the instance by removing some values from domains or tuples from constraint relations which cannot participate to a solution.

For instance, most state-of-the-art solvers maintain some consistency level at each step of the search, like MAC (Maintaining Arc-Consistency [START_REF] Sabin | Contradicting Conventional Wisdom in Constraint Satisfaction[END_REF]) or RFL (Real Full Look-ahead [START_REF] Nadel | Tree Search and Arc Consistency in Constraint-Satisfaction Algorithms[END_REF]) do for arc-consistency. This latter turns out to be a relevant tradeoff between the number of removed values and the runtime. We now recall MAC with more details. During the solving, MAC develops a binary search tree whose nodes correspond to decisions. More precisely, it can make two kinds of decisions: positive decisions x i = v i which assign the value v i to the variable x i and negative decisions x i = v i which ensure that x i cannot be assigned with v i . Let us consider Σ = δ 1 , . . . , δ i (where each δ j may be a positive or negative decision) as the current decision sequence. At each node of the search tree, MAC takes either a positive decision or negative one. When reaching a new level, it starts by a positive decision which requires to choose a variable among the unassigned variables and a value. Both choices are achieved thanks to heuristics. Then, once the decision made, MAC applies an arc-consistency filtering. This filtering deletes some values of unassigned variables which are not consistent with the last taken decision and Σ. By so doing, a domain may become empty. In such a case, we say that a dead-end or a conflict occurs. This means that the current set of decisions cannot lead to a solution. If no dead-end occurs, the search goes on to the next level by choosing a new positive decision. Otherwise, the current decision is called into question. If it is a positive decision x i = v i , MAC makes the corresponding negative decision x i = v i , that is the value v i is deleted from the domain D i . Otherwise, it is a negative decision and MAC backtracks to the last positive decision x = v in Σ and makes the decision x = v . If no such decision exists, it means that the instance has no solution. In contrast, if MAC succeeds in assigning all the variables, the corresponding assignment is, by construction, a solution of the considered instance.

More recently, restart techniques have been introduced in the CSP framework (e.g. in [START_REF] Lecoutre | Recording and Minimizing Nogoods from Restarts[END_REF]). They generally allow to reduce the impact of bad choices performed thanks to heuristics (like the variable ordering heuristic) or of the occurrence of heavy-tailed phenomena [START_REF] Gomes | Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems[END_REF]. For efficiency reasons, they are usually exploited with some learning techniques like recording of nld-nogoods in [START_REF] Lecoutre | Recording and Minimizing Nogoods from Restarts[END_REF]. These nogoods can be seen as a set of decisions which cannot be extended to a solution. They are used to avoid visiting again a part of the search space which has already been visited by MAC. These nogoods are recorded each time a restart occurs. Weighted Average (ERWA) [START_REF] Sutton | Reinforcement Learning: An Introduction, 1st edn[END_REF] takes into account such considerations by giving higher weights to the recent data than the older ones. More precisely, the exponential moving average ȳm is computed as follows:

Exponential Recency Weighted Average

ȳm = m i=1 α × (1 -α) m-i × y i
where 0 < α < 1 is a step-size parameter which controls the relative weights between recent and past data. The moving average can also be calculated incrementally by the formula:

ȳm = (1 -α) × ȳm-1 + α × y m .
The base case is ȳ0 = 0. ERWA is used to solve the bandit problem to estimate the expected reward of different actions in nonstationary environments [START_REF] Sutton | Reinforcement Learning: An Introduction, 1st edn[END_REF]. In bandit problems, the agent must select an action to play, from a given set of actions, while maximizing its long term expected reward.

Conflict-History Search for CSP

This section is dedicated to our contribution by defining and describing a new variable ordering heuristic for CSP solving, which we call Conflict-History Search (CHS). The main idea is to consider the history of constraint failures and favor the variables that often appear in recent failures. In this order, the conflicts are dated and the constraints are weighted on the basis of the exponential recency weighted average. These weights are coupled with the variable domains to calculate the Conflict-History scores of the variables.

CHS Description

Formally, CHS maintains for each constraint c j a score q(c j ) which is initialized to 0 at the beginning of the search. If c j leads to a failure during the search because the domain of a variable in S(c j ) is emptied then q(c j ) is updated by the formula below derived from ERWA [START_REF] Sutton | Reinforcement Learning: An Introduction, 1st edn[END_REF]:

q(c j ) = (1 -α) × q(c j ) + α × r(c j )
The parameter 0 < α < 1 is the step-size and r(c j ) is the reward value. The parameter α fixes the importance given to the old value of q at the expense of the reward r. The value of α decreases over time as it is applied in reinforcement learning to converge towards relevant values of q [START_REF] Sutton | Reinforcement Learning: An Introduction, 1st edn[END_REF]. In other words, decreasing the value of α amounts to giving more importance to the last value of q and considering that the values of q are more and more relevant as the search progresses. Furthermore, we are interested by the constraint failure to follow the first-fail principle [START_REF] Haralick | Increasing tree search efficiency for constraint satisfaction problems[END_REF]. CHS applies the decreasing policy of α, which is successfully used for designing efficient branching heuristic for the satisfiability problem [START_REF] Liang | Exponential Recency Weighted Average Branching Heuristic for SAT Solvers[END_REF][START_REF] Liang | Learning Rate Based Branching Heuristic for SAT Solvers[END_REF]. More precisely, starting from an initial value α 0 , α decreases by 10 -6 at each constraint failure to a minimum of 0.06. This minimum value of α controls the number of steps before considering that a convergence is reached.

The reward value r(c j ) is based on how recently c j occurred in conflicts. More precisely, it relies on the proximity between the previous conflict in which c j is involved and the current one. By so doing, we aim to give a higher reward to constraints that fail regularly over short periods of time during the search space exploration. The reward value is calculated according to the formula:

r(c j ) = 1 Conf licts -Conf lict(c j ) + 1
Initialized to 0, Conf licts is the number of conflicts which have occurred since the beginning of the search. Conf lict(c j ) is also initialized to 0 for each constraint c j ∈ C. When a conflict occurs on c j , r(c j ) and q(c j ) are computed. Then Conf licts is incremented by 1 and Conf lict(c j ) is updated to the new value of Conf licts.

At this stage, we define the Conflict-History score of a variable x i ∈ X as follows:

chv(x i ) = cj ∈C: xi∈S(cj )∧|U vars(S(cj ))|>1
q(c j )

|D i | (1)
U vars(Y ) is the set of unassigned variables in Y . D i is the current domain of x i and its size may be reduced by the propagation process in the current step of the search. CHS chooses the variable to assign with the highest chv value. In this manner, CHS focuses branching on the variables with a small domain size belonging to constraints which appear recently and repetitively in conflicts.

One can observe that at the beginning of the search, all the variables have the same score, which is equal to 0. To avoid random selection, we update Equation 1 to calculate chv as given below, where δ is a positive real number close to 0.

chv(x i ) = cj ∈C: xi∈S(cj )∧|U vars(S(cj ))|>1 (q(c j ) + δ) |D i | (2)
Thus, when the search starts, the branching will be oriented according to the degree of the variables without having a negative influence on the ERWA-based calculation later in the search. CHS selects the branching variable with the highest chv value calculated according to Equation 2. The heuristic CHS is described in Algorithm 1 with an event-driven approach. Lines 2-7 correspond to the initialization step. If a conflict occurs when enforcing the filtering with the constraint c j , the associated event is triggered and the score is update (Lines 8-14). The selection of a new variable is achieved thanks to Lines 15-16. q(c j ) ← q(c j ) × 0.995 Conf licts-Conf lict(cj )

CHS and Restarts

Restart techniques are known to be important for the efficiency of solving algorithms (see for example [START_REF] Lecoutre | Nogood recording from restarts[END_REF]). Restarts may allow to reduce the impact of irrelevant choices done during the search according to heuristics, such as variable selection.

As it will be detailed later, CHS is integrated into CSP solving algorithms, which include restarts. In the corresponding implementations, the Conf lict(c j ) value of each constraint c j is not reinitialized when a restart occurs. It is the same for q(c j ). However, a smoothing may be applied and will be explained below. Keeping this information unchanged reinforces learning from the search history.

Concerning the step-size α, which defines the importance given to the old value of q(c j ) at the expense of the reward r(c j ), CHS reinitializes the value of α to α 0 at each restart (Line 18 of Algorithm 1). This may guide the search through different parts of the search space.

CHS and Smoothing

At each conflict, CHS updates the chv score of one constraint at a time: the constraint c j which is used to wipe out the domain of a variable in S(c j ). As long as they do not appear in new conflicts, some constraints can have their weights unchanged for several search steps. These constraints may have high scores while their importance does not seem significant for the current part of the search. To avoid this situation, we propose to smooth the scores q(c j ) of all the constraints c j ∈ C at each restart by the following formula:

q(c j ) = q(c j ) × 0.995 Conf licts-Conf lict(cj )

Hence, the scores of constraints are decayed according to the date of their last appearances in conflicts (Lines 19-20 of Algorithm 1).

Related Work

Before providing a detailed experimental evaluation of CHS and its components, we present the most efficient and common variable ordering heuristics for CSP. As CHS, the recalled heuristics share the same behavior. In effect, the variables and/or constraints are weighted dynamically throughout the search by considering the collected information since its beginning. Some of these heuristics, such as Last Conflict [START_REF] Lecoutre | Last Conflict Based Reasoning[END_REF], require the use of an auxiliary heuristic as it will be explained later. We also recall briefly branching heuristics for the satisfiability problem. It should be recalled that ERWA was first used in the context of the satisfiability problem [START_REF] Liang | Exponential Recency Weighted Average Branching Heuristic for SAT Solvers[END_REF][START_REF] Liang | Learning Rate Based Branching Heuristic for SAT Solvers[END_REF].

Impact-Based Search (IBS)

This heuristic selects the variable which leads to the largest search space reduction [START_REF] Refalo | Impact-based search strategies for constraint programming[END_REF]. The impact on the search space size is approximated as the reduction of the product of the variable domain sizes. Formally, the impact of assigning the variable x i to the value v i ∈ D i is defined by:

I(x i = v i ) = 1 - P af ter P bef ore
P af ter and P bef ore are respectively the products of the domain cardinalities after and before branching on x i = v i and applying constraint propagations. By doing so, selecting the next branching variable requires the computation of the impact of each variable assignment, by simulating filtering at each node of the search tree. This can be very time consuming. Hence, IBS considers the impact of an assignment at a given node as the average of its observed impacts. More precisely, if K is the index set of impacts observed of x i = v i , IBS estimates an averaged impact of this assignment as follows, where I k is k th impact value:

Ī(x i = v i ) = k∈K I k (x i = v i )

|K|

Finally, the impact of a variable according to its current domain, which may be filtered, is defined as follows:

I(x i ) = v∈Di 1 -Ī(x i = v)
IBS selects the variable with the highest impact value I(x i ).

Conflict-Driven Heuristic

A popular variable ordering heuristic for CSP solving is dom/wdeg [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF]. It guides the search towards the variables appearing in the constraints which seem hard to satisfy. For each constraint c j , the dom/wdeg heuristic maintains a weight w(c j ), initially set to 1, counting the number of times that c j has led to a failure (i.e. the domain of a variable x i in S(c j ) is emptied during propagation from c j ). The weighted degree of a variable x i is defined as:

wdeg(x i ) = cj ∈C: xi∈S(cj )∧|U vars(S(cj ))|>1
w(c j )

The dom/wdeg heuristic selects the variable x i to assign with the smallest ratio |D i |/wdeg(x i ), such that D i is the current domain of x i (the size of D i may be reduced in the current search step). Note that the constraint weights are not smoothed in dom/wdeg. Also, variants of dom/wdeg were introduced, such as in [START_REF] Hebrard | Explanation-Based Weighted Degree[END_REF], but are not widely used in practice. Very recently, a refined version of wdeg (called wdeg ca.cd ) has been defined in [START_REF] Wattez | Refining Constraint Weighting[END_REF]. When a conflict occurs for a constraint c j , instead of increasing its weight by 1 as in dom/wdeg, wdeg ca.cd increases its weight by a value depending on the number of unassigned variables in the scope of c j and their current domain size.

Activity-Based Heuristic (ABS)

ABS is motivated by the prominent role of filtering techniques in CSP solving [START_REF] Michel | Activity-based search for black-box constraint programming solvers[END_REF]. It exploits this filtering information and maintains measures of how often the variable domains are reduced during the search. In practice, at each node of the search tree, constraint propagation may filter the domains of some variables after the decision process. Let X f be the set of such variables. Accordingly, the activities A(x i ), initially set to 0, of the variables x i ∈ X are updated as follows:

• A(x i ) = A(x i ) + 1 if x i ∈ X f • A(x i ) = γ × A(x i ) if x i ∈ X f γ is a decay parameter, such that 0 ≤ γ ≤ 1.
The ABS heuristic selects the variable x i with the highest ratio A(x i )/|D i |.

CHB in Gecode

Dedicated to constraint programming, Gecode solver implements Conflict-History based Branching (CHB) heuristic since version 5.1.0 released in April 2017 [START_REF] Schulte | Programming branchers[END_REF]. It follows the same steps of the first definition of CHB in the context of the satisfiability problem [START_REF] Liang | Exponential Recency Weighted Average Branching Heuristic for SAT Solvers[END_REF][START_REF] Liang | Learning Rate Based Branching Heuristic for SAT Solvers[END_REF]. In Gecode, the following parameters are used to update the Q-score of each variable x i of the CSP instance, denoted qs(x i ).

f is the number of failures encountered since the beginning of the search and lf (x i ) is the last failure number of x i , corresponding to the last time that D i is emptied. Initialized to 0.05 for each variable x i , CHB update the Q-score qs(x i ) of x i during the constraint propagation as follows:

• If D i is not reduced then qs(x i ) remains unchanged

• If D i is pruned and the search leads to a failure, lf (x i ) is set to f and qs(x i ) is updated by:

qs(x i ) = (1 -α) × qs(x i ) + α × r
The step-size α, initialized to 0.4, is updated to α -10 -6 if α > 0.06. The value of the reward r is given by:

r = 1 f -lf (x i ) + 1
• If D i is pruned and the search does not lead to a failure, qs(x i ) is also updated by:

qs(x i ) = (1 -α) × qs(x i ) + α × r
In this case, the reward value is defined by:

r = 0.9 f -lf (x i ) + 1
CHB in Gecode selects the variable with the highest Q-score.

Last Conflict (LC)

Last Conflict (LC) reasoning [START_REF] Lecoutre | Last Conflict Based Reasoning[END_REF] aims to better identify and exploit nogoods in a binary tree search, where each node has a first branch corresponding to a positive decision (x i = v i ) and eventually a second branch with a negative decision (x i = v i ).

If a positive decision x i = v i leads to a conflict then LC records the variable x i as a conflicting variable. The value v i is removed from the domain D i of x i . After developing the negative branch x i = v i , LC continues the search by assigning a new value v i to x i instead of choosing a new decision variable. This treatment is repeated until a successful assignment of x i is achieved. In this case, the variable x i is unrecorded as a conflicting one and the next decision variable is decided by an auxiliary variable ordering heuristic. Hence, this last one is used when no conflicting variable is recorded by LC.

Conflict Order Search (COS)

Conflict Order Search (COS) [START_REF] Gay | Conflict Ordering Search for Scheduling Problems[END_REF] is intended to focus the search on the variables which lead to recent conflicts. When a branching on a variable x i fails, x i is stamped by the total number of failures since the beginning of the search (the initial stamp value of each variable is 0). COS prefers the variable with the highest stamp value. An auxiliary heuristic is used if all the unassigned variables have the stamp value 0.

Branching Heuristics for the Satisfiability Problem

In the context of the satisfiability problem, modern solvers based on Conflict-Driven Clause Learning (CDCL) [START_REF] Eén | An Extensible SAT-solver[END_REF][START_REF] Marques-Silva | GRASP: A Search Algorithm for Propositional Satisfiability[END_REF][START_REF] Moskewicz | Chaff: Engineering an Efficient SAT Solver[END_REF] employ variable branching heuristics correlated to the ability of the variable to participate in producing learnt clauses when conflicts arise (a conflict is a clause falsification). The Variable State Independent Decaying Sum (VSIDS) heuristic [START_REF] Moskewicz | Chaff: Engineering an Efficient SAT Solver[END_REF] maintains an activity value for each Boolean variable. The activities are modified by two operations: the bump (increase the activity of variables appearing in the process of generating a new learnt clause when a conflict is analyzed) and the multiplicative decay of the activities (often applied at each conflict). VSIDS selects the variable with the highest activity to branch on.

Recently, a conflict history based branching heuristic (CHB) [START_REF] Liang | Exponential Recency Weighted Average Branching Heuristic for SAT Solvers[END_REF], based on the exponential recency weighted average, was introduced. It rewards the activities to favor the variables that were recently assigned by decision or propagation. The rewards are higher if a conflict is discovered. The Learning Rate Branching (LRB) heuristic [START_REF] Liang | Learning Rate Based Branching Heuristic for SAT Solvers[END_REF] extends CHB by exploiting locality and introducing the learning rate of the variables.

Discussion

Reinforcement learning techniques have already been studied in constraint programming. The multi-armed bandit framework is used to select adaptively the consistency level of propagation at each node of the search tree [START_REF] Balafrej | Multi-Armed Bandits for Adaptive Constraint Propagation[END_REF]. A linear regression method is used to learn the scoring function of value heuristics [START_REF] Chu | Learning value heuristics for constraint programming[END_REF]. Rewards are calculated and used to select adaptively the backtracking strategy [START_REF] Bachiri | RLBS: An Adaptive Backtracking Strategy Based on Reinforcement Learning for Combinatorial Optimization[END_REF]. Learning process based on Least Squares Policy Iteration technique is used to tune adaptively the parameters of stochastic local search algorithms [START_REF] Battiti | An Investigation of Reinforcement Learning for Reactive Search Optimization[END_REF].

More recently, upper confidence bound and Thompson Sampling techniques are employed to select automatically a variable ordering heuristic for CSP, among a set of candidate ones, at each node of the search tree [START_REF] Xia | Learning robust search strategies using a bandit-based approach[END_REF]. The considered candidate set contains notably IBS, ABS and dom/wdeg. Knowing that no heuristic always outperforms another, Xia and Yap exploit reinforcement learning (under the form of a multi-armed bandit) to choose the search heuristic to employ at each node of the search rather than choosing a particular heuristic before the solving. More recently, Wattez et al. have proposed another MAB approach [START_REF] Wattez | Learning Variable Ordering Heuristics with Multi-Armed Bandits and Restarts[END_REF]. Like in the work of Xia and Yap, each heuristic corresponds to an arm. In contrast, an new arm is chosen at each restart instead of each node. On the other hand, in CHS, reinforcement learning allows to select the branching variable based on ERWA. Note also that CHS can be used as an additional arm in the work of Xia and Yap while it is already exploited as an arm in [START_REF] Wattez | Learning Variable Ordering Heuristics with Multi-Armed Bandits and Restarts[END_REF].

To return to the heuristics detailed in this section, LC, COS and CHB are also conceptually interested in the search history as CHS. They act directly on the variable scores while CHS considers this history by weighting the constraints that are responsible for failures before scoring the variables. As an illustration, CHB in Gecode updates the Q-score values of variables according to ERWA while CHS uses ERWA to update the weight of constraints to calculate the score of the variables. The update of the α parameter is also different between CHS and CHB, especially during restarts.

Weight and score decaying is also used in other heuristics such as ABS. However, it is applied to the score of the variables and not that of the constraints such as in CHS. It is also important to note that there is no decaying in CHB. Furthermore, CHS and dom/wdeg calculate differently the score of the constraints leading to failures. In the first case, the score of the constraint is always incremented by a constant value 1. In the second case, the new score is a tradeoff between the current one and the reward that varies at each failure. Moreover, the scores of constraints are not decayed in dom/wdeg contrary to CHS. Finally, unlike LC and COS, CHS does not require the use of an auxiliary heuristic.

Experimental Evaluation on CSP Instances

This section is devoted to the evaluation of the behavior of our heuristic when solving CSP instances (decision problem). We first describe the experimental protocol we use. In subsection 5.2, we assess the sensitivity of our heuristic CHS to its parameters and the benefits of smoothing and resetting. Afterwards, we compare CHS with state-of-the-art variable ordering heuristics in subsection 5.3, before studying the behavior of CHS when it is used jointly with LC or COS in subsection 5.4. Finally, in subsection 5.5, we evaluate the practical interest of CHS in the particular case where the search is guided by a tree-decomposition.

Experimental Protocol

We consider all the CSP instances from the XCSP3 repository2 and the XCSP3 competition 2018 3 , resulting in 16,947 instances. XCSP3, for XML-CSP version 3, is an XML-based format to represent instances of combinatorial constrained problems. Our solvers are compliant with the rules of the competition except that the global constraints cumulative, circuit and some variants of the allDifferent constraint (namely except and list) or the noOverlap constraint are not supported yet. Consequently, from the 16,947 obtained instances, we first discard 1,233 unsupported instances. We also remove 2,813 instances which are detected as inconsistent by the initial arc-consistency preprocessing and having no interest for the present comparison. Finally, we have noted that some instances appear more than once. In such a case, we keep only one copy. In the end, our benchmark contains 12,829 instances, including notably structured instances and instances with global constraints.

Regarding the solving step, we exploit MAC with restarts [START_REF] Lecoutre | Recording and Minimizing Nogoods from Restarts[END_REF] before assessing the impact of our approach on a structural solving method, namely BTD-MAC+RST+Merge [START_REF] Jégou | Towards a Dynamic Decomposition of CSPs with Separators of Bounded Size[END_REF]. Roughly speaking, BTD-MAC+RST+Merge differs from MAC by the exploitation of the structure via the notion of tree-decomposition (i.e. a collection of subsets of variables, called clusters, which are arranged in the form of a tree [START_REF] Robertson | Graph minors II: Algorithmic aspects of treewidth[END_REF]). While the search performed by MAC considers at each step all the remaining variables, one performed by BTD-MAC+RST+Merge only takes into account the unassigned variables of the current cluster. The clusters of the computed tree-decomposition are processed according to a depth-first traversal of the tree-decomposition starting from a cluster called the root cluster (see [START_REF] Jégou | Towards a Dynamic Decomposition of CSPs with Separators of Bounded Size[END_REF] for more details). For BTD-MAC+RST+Merge, the tree-decompositions are computed with the heuristic H 5 -TD-WT [START_REF] Jégou | Towards a Dynamic Decomposition of CSPs with Separators of Bounded Size[END_REF]. The first root cluster is the cluster having the maximum ratio number of constraints to its size minus one. At each restart, the selected root cluster is one which maximizes the sum of the weights of the constraints whose scope intersects the cluster. The merging heuristic is the one provided in [START_REF] Jégou | Towards a Dynamic Decomposition of CSPs with Separators of Bounded Size[END_REF]. Note that these settings except the variable ordering heuristic correspond to those used for the XCSP3 competitions 2017 and 2018 [START_REF] Habet | BTD 12 and miniBTD 12[END_REF][START_REF] Jégou | BTD and miniBTD[END_REF][START_REF] Jégou | BTD and miniBTD[END_REF].

MAC and BTD-MAC+RST+Merge use a geometric restart strategy based on the number of backtracks with an initial cutoff set to 100 and an increasing factor set to 1.1. In order to make the comparison fair, the lexicographic ordering is used for the choice of the next value to assign. We consider the following heuristics dom/wdeg, wdeg ca.cd , ABS, IBS and CHB as implemented in Gecode. For ABS, we fix the decay parameter γ to 0.999 as in [START_REF] Michel | Activity-based search for black-box constraint programming solvers[END_REF]. Note that we do not exploit a probing step like one mentioned in [START_REF] Michel | Activity-based search for black-box constraint programming solvers[END_REF]. So all the weights are initially set to 0. For CHB, we use the value parameters as given in [START_REF] Schulte | Programming branchers[END_REF]. We also introduce a new variant dom/wdeg+s which we define as dom/wdeg where the weights of constraints are smoothed at each restart, exactly as in CHS. For all the heuristics, ties (if any) are broken by using the lexicographic ordering.

We have written our own C++ code to implement all the compared variable ordering heuristics in this section, as well as the solvers that exploit them (MAC and BTD). By so doing, we avoid any bias related to the way the heuristics and solvers are implemented. In particular, the variable ordering heuristics are all implemented with equal refinement and care. Moreover, when comparing the variable ordering heuristics for a given solver, the only thing which differs is the variable ordering heuristic. Indeed, we use exactly the same propagators, the same value heuristic, etc. This ensures that we make a fair comparison. Finally, given a solver and a CSP instance, we consider that a variable ordering heuristic h 1 is better than another one h 2 if h 1 allows the solver to solve the instance faster than h 2 . Indeed, the aim of variable ordering heuristic is to make a good tradeoff between the size of the explored search tree and the runtime spent for choosing a relevant variable (remember that finding the best one is an NP-Hard task [START_REF] Liberatore | On the complexity of choosing the branching literal in DPLL[END_REF]). Since all the other parts of the solver are identical, the solving runtime turns to be a relevant measure of the quality of this tradeoff. Thus, when the comparison relies on a collection of instances, h 1 is said better than h 2 if it leads the solver to solve more instances than h 2 . If both lead to solve the same number of instance, ties are broken by considering the smaller cumulative runtime. At the end, note that our protocol is consistent with the recommendations outlined in [START_REF] Hooker | Testing Heuristics: We Have It All Wrong[END_REF].

The experiments are performed on Dell PowerEdge R440 servers with Intel Xeon Silver 4112 processors (clocked at 2.6 GHz) under Ubuntu 18.04. Each solving process is allocated a slot of 30 minutes and at most 16 GB of memory per instance. In the following tables, #solved (abbreviated sometimes #solv.) denotes the number of solved instances for a given solver and time is the cumulative runtime, i.e. the sum of the runtime over all the considered instances.

Impact of CHS Settings

In this part, we assess the sensitivity of CHS with respect to the chosen values for α 0 or δ. First, we observe the impact of α 0 value. Hence, we fix δ to 10 -4 to start the search by considering the variable degrees then quickly exploit ERWA-based computation. We then vary the value of α 0 . 1 presents the number of instances solved by MAC depending on the initial value of α 0 and the corresponding cumulative runtime. Here, we first vary α 0 between 0.1 and 0.9 with a step of 0.1. We also provide the results of the Virtual Best Solver (VBS). The VBS is a theoretical/virtual solver that returns the best answer obtained by MAC with a given α 0 among those considered here. Roughly, it allows to count the number of the instances solved at least one time when varying the value of α 0 , while considering the smaller corresponding runtime. Table 1 shows that the results obtained for the different values of α 0 are relatively close to each others. However, we can observe that the value α 0 = 0.1 allows MAC to solve more instances (10,742 solved instances with a cumulative solving time of 1,038.89 hours) than the other considered values. More precisely, MAC with CHS and α 0 = 0.1 solves at least 31 additional instances. The worst cases are α 0 = 0.8 and α 0 = 0.9 with 10,676 instances solved respectively in 1,072 and 1,071 hours. If we discard the value 0.1 for α 0 , we observe that the results for the remaining considered values are quite close. This shows that CHS is relatively robust w.r.t. the α 0 parameter. Moreover, we can also remark that these observations are still valid if we focus on SAT instances (respectively on UNSAT instances). For example, the choice α 0 = 0.1 leads to solving the largest number of SAT instances (resp. UNSAT instances), exactly 6,530 instances (resp. 4,212 instances). Figures 1 and2 also show that α 0 = 0.1 is the best choice among the experimented values. Indeed, we can note that the curve corresponding to α 0 = 0.1 is almost always above the others in both figures. These two figures also highlight the robustness of CHS w.r.t. the value of α 0 since all the curves are quite close. Since the value α 0 = 0.1 leads to the best result, a natural question is what happens if we consider the value α 0 = 0 (which is normally a forbidden value since 0 < α < 1). So we run MAC+CHS with α 0 = 0. In this case, the number of solved instances decreases significantly since only 9,069 instances are solved. At the same time, the runtime is almost doubled with a cumulative runtime of 1,921.35 hours. Consequently, the benefit of CHS is highly related to the tradeoff between the rewards of the past conflicts and the reward of the last one and so choosing a positive value for α 0 is crucial. The impact of this tradeoff is reinforced by the fact that MAC+CHS with α 0 = 1 (a forbidden value too) performs worse than most of the combinations of MAC with α 0 between 0.1 and 0.9. Indeed, it only solves 10,667 instances while spending more time (1,089.37 h).

Likewise, we can wonder what happens if we choose a value slightly different from 0.1. Hence, we now vary α 0 between 0.025 and 0.15 with a step of 0.025 (see Table 2). Again, MAC+CHS with α 0 = 0.1 turns to be the best case by solving more instances and obtaining the smallest cumulative runtime. Furthermore, the robustness of CHS w.r.t. the α 0 parameter is strengthened since we can note that the other values of α 0 obtain close results.

Regarding the Virtual Best Solver (VBS) in Table 1, we note that it can solve 191 additional instances than MAC+CHS when α 0 = 0.1 with the best runtime of 940.21 h. We can also remark that most of these additional instances are consistent (161 SAT instances vs. 30 UNSAT). If we consider the results instance per instance, we observe that 10,478 instances are solved whatever the chosen value for α 0 , which shows again the robustness of CHS w.r.t. the value of α 0 . Furthermore, among the 455 remaining ones, there exists 106 instances which are only solved by MAC with a particular value for α 0 (of course this value depends on the considered instance) and for 32% of the instances, MAC needs more than 1,200 seconds in order to solve each of them. Accordingly, some instances seem to be harder to solve. Finally, we observe that these 455 instances belong to several families. Indeed, more than half of the considered families are involved here, which shows that this phenomenon is more related to the instances themselves than to a particular feature of their family. Now, we set α 0 to 0.1 and evaluate different values of δ (see Table 3). The observations are similar to those presented previously, showing the robustness of CHS regarding δ. Also, it is interesting to highlight that MAC+CHS with δ = 0 solves 10,683 instances while it solves 10,742 instances if δ = 10 -4 . This illustrates the relevance of introducing δ in CHS since it allows to solve 59 more instances with this last setting. 4 gives the results of MAC+CHS (α 0 = 0.1, δ = 10 -4 ) with smoothing (+s) the constraint scores or without (-s) and/or with resetting (+r) the value of α to 0.1 at each new restart or without (-r). The observed behaviors clearly support the importance of smoothing and restarts for CHS. For example, MAC+CHS+s-r solves 13 less instances than MAC+CHS, while MAC+CHS-s+r solves 84 instances less. Finally, these results are globally consistent with those presented in [START_REF] Habet | Conflict history based search for constraint satisfaction problem[END_REF]. Indeed, except that the best value of α 0 is now 0.1 instead of 0.4 in [START_REF] Habet | Conflict history based search for constraint satisfaction problem[END_REF], we observe the same trends. The benchmark used in [START_REF] Habet | Conflict history based search for constraint satisfaction problem[END_REF] was a subset of our initial benchmark. If we proceed similarly by removing arc-inconsistent instances, we obtain a benchmark with 7,916 instances. From this benchmark, MAC solved respectively 6,700 and 6,706 instances with 0.1 and 0.4 for α 0 in [START_REF] Habet | Conflict history based search for constraint satisfaction problem[END_REF], while in the current experiments, it succeeds in solving 6,837 and 6,829 instances. In both cases, the gap between the two values of α 0 is very small. Note that the increase in the number of solved instances is mainly related to some improvements in our implementation and the difference of hardware configurations. Both impact all the heuristics in the same manner.

CHS vs. Other Search Heuristics

Now, we compare CHS to other search strategies from the state-of-the-art, namely dom/wdeg, wdeg ca.cd , ABS, IBS and CHB. In the remaining part of the paper, by default, we consider CHS with α 0 = 0.1 and δ = 10 -4 . We also consider the variant dom/wdeg+s that we introduced for dom/wdeg. Figure 3 presents the number of solved instances as a function of the elapsed time for each considered heuristic. Since no heuristic outperforms another for all instances or families of instances, Tables 5678give some details for each family of instances. They allow to have a better insight of the kind of instances for which CHS is relevant. More accurately, for each family, they provide on rows C the number of instances solved by MAC with each considered heuristic (excluding IBS 4 ) and the cumulative runtime for solving them for each heuristic, and on rows T the total number of instances of the family, the number of solved instances and the corresponding cumulative runtime for each heuristic. For each row, we write in bold the result of the best heuristic. As mentioned in our experimental protocol and like the solver competitions, we first consider the number of solved instances and we break ties by considering the cumulative runtime (given in seconds, except for the total runtimes which are expressed in hours). We only provide two digits after the decimal dot when the runtime does not exceed 100 seconds. Beyond, such details do not bring a significant information. We divide the instance families into three categories: academic, real-world and XCSP3 2018 competition. For that, we use the labeling from the XCSP3 repository.

From Figure 3 and Tables 5678, it is clear that MAC with CHS performs better than any other heuristics whether in terms of the number of solved instances or runtime. Indeed, for example, dom/wdeg is the heuristic closest to CHS but leads to solve 92 instances less. At the same time, CHS solves 127 instances more than MAC+dom/wdeg+s and 174 more than MAC+wdeg ca.cd . Likewise, it solves 134 additional instances w.r.t. MAC+ABS. Now, if we consider the heuristic CHB which is based on conflict history like CHS, the gap with CHS is even greater (213 instances). This last result shows that the calculation of weights by ERWA on the constraints (as done in CHS) is more relevant than its calculation on the variables (as done in CHB). Note that the poor score of IBS is mainly related to the estimation of the size of the search tree (i.e. the product of the domain sizes [START_REF] Refalo | Impact-based search strategies for constraint programming[END_REF]). In fact, we observe that, for many instances, the value of the estimation exceeds the capacity of representation of long double in C++. Finally, these trends are still valid if we focus on SAT instances or UNSAT ones.

Interestingly, whatever the value of α 0 , MAC with CHS remains better than all its competitors. Indeed, the worst case is observed when the value of α 0 is equal to 0.8 or 0.9 with 10,676 solved instances. This observation also holds for the version of CHS in which we disable the smoothing or the resetting of α. This clearly highlights the practical interest of our approach.

If we look at the results more closely, i.e. for each family (see Tables 5678), we observe that no heuristic dominates the others. Indeed, if CHS is the heuristic that leads most often to the best results (for 13 families), the other heuristics are close (notably 10 families for wdeg ca.cd , ABS and CHB). This makes the choice of a particular heuristic difficult, as it is highly dependent on the instance or the family of instances to be processed. This probably explains the gap between VBS and MAC with any heuristic (e.g. 10,982 solved instances for the VBS against 10,812 for MAC with CHS). Curiously, dom/wdeg+s only ranks first for 3 families while being globally ranked at the third place. As CHS, it rarely performs significantly worse than the other heuristics.

To illustrate this phenomenon, let us consider the difference between the number of instances solved by the VBS and the corresponding number for MAC, for each family, with each heuristic. This number can be seen as a measure of the robustness of the heuristic. Table 9 provides the mean and the standard deviation of this difference for each heuristic. It shows that CHS is the most robust heuristic by obtaining the smallest mean and standard deviation. Finally, our observations are consistent with ones in [START_REF] Habet | Conflict history based search for constraint satisfaction problem[END_REF]. In particular, MAC clearly performs better with CHS than with any other heuristic, notably the two powerful and popular variable ordering heuristics dom/wdeg and ABS. The gap between CHS and the other heuristics has widened with the increase in the number of instances taken into account.

Combination with LC and COS

LC and COS are two branching strategies based on conflicts which require an auxiliary variable ordering heuristic in order to choose a variable when no conflict can be exploited. In this subsection, we study the behavior of CHS and some heuristics of the state-ofthe-art when they are used jointly with LC or COS. We only keep the three best heuristics according to the results of the previous subsection, namely dom/wdeg+s, dom/wdeg and ABS. First, we consider the case of LC. Figure 4 presents the number of solved instances as a function of the elapsed time for LC combined with each considered heuristic. As a first observation, we can note that using LC does not change the ranking obtained in the previous subsection. Namely, LC combined with CHS leads to the best results followed by dom/wdeg+s, dom/wdeg and ABS. Indeed, as we can see in Table 10, MAC with LC and CHS solves more instances and solves them more quickly than MAC with LC and any other heuristic. Moreover, for any considered heuristic h, we can also remark that MAC with LC and h performs better and faster than MAC with h. For instance, MAC with LC and CHS solves 10,812 in 1,017.03 hours against 10,742 instances solved in 1,038.89 hours for MAC with CHS. We can also observe that the gain in the number of solved instances thanks to MAC with LC and h w.r.t. MAC with h varies according to h (70 instances for CHS and 110 instances for ABS). This probably reflects the fact that the less efficient the heuristic is, the easier it is to solve additional instances. To this end, LC with CHS turns to be the most interesting variable ordering heuristic among all the heuristics we consider in our experiments. Now, we assess the behavior of MAC when using COS with any auxiliary heuristic among CHS, dom/wdeg+s, dom/wdeg and ABS. As shown in Figure 5 and Table 10, combining COS with any heuristic leads to decrease significantly the ability of MAC to solve instances. Indeed, we can observe that MAC using COS and any heuristic solves at least 346 instances less than MAC using solely the auxiliary heuristic. Thus, if the ranking remains the same, the gap between MAC with COS and CHS and MAC with COS and any other auxiliary heuristic is narrower (from 92 instances when the heuristics are exploited alone to 16 instances with COS). A possible explanation of this behavior is that MAC only exploits the auxiliary heuristic when there is no more variable appearing in conflicts. This occurs at the beginning of the search when no conflict has been encountered yet or when all the variables appearing in past conflicts are assigned. Clearly, the first case concerns few nodes in the search tree. For the second case, it may be the same too as soon as many variables are involved in the encountered conflicts. In addition, a potential drawback of COS is that the conflicts exploited by COS may be old and so have less sense at some steps of the search.

CHS and Tree-Decomposition

We now assess the behavior of CHS when the search is guided by a tree-decomposition. Studying this question is quite natural since CHS aims to exploit the structure of the instance, but in a way different from what the tree-decomposition does. With this aim in view, we consider BTD-MAC+RST+Merge [START_REF] Jégou | Towards a Dynamic Decomposition of CSPs with Separators of Bounded Size[END_REF] and the heuristics CHS, dom/wdeg+s, dom/wdeg and ABS combined or not with LC. As shown in Figure 6 and Table 11, the trends observed for MAC are still valid for BTD-MAC+RST+Merge. Indeed, the solving is more efficient with CHS than with any other used heuristic by at least 58 additional instances. For example, BTD-MAC+RST+Merge with CHS solves 10,770 instances (in 1,035 h) against 10,712 instances (in 1,065 h) for dom/wdeg+s. Moreover, we can note that using BTD-MAC+RST+Merge instead of MAC does not change the ranking of the heuristics in terms of the number of solved instances or the cumulative runtime.

Likewise, we can make the same observations if we exploit LC (see Figure 7 and Table 11). Above all, BTD-MAC+RST+Merge with LC and CHS turns out to be more efficient than MAC with LC and any auxiliary heuristic. For example, it solves 27 additional instances compared to MAC with LC and CHS. All these observations show that exploiting both CHS and tree-decomposition may be of interest and that these two strategies can be complementary. Finally, these results are consistent with the ones in [START_REF] Habet | Conflict history based search for constraint satisfaction problem[END_REF]. They are also consistent with ones of the XCSP3 competition 2018. For instance, BTD-MAC+RST+Merge participated in the mini-solvers track of the competition by using respectively dom/wdeg (for the solver miniBTD [START_REF] Jégou | BTD and miniBTD[END_REF]) and CHS (for the solver miniBTD 12 [START_REF] Habet | BTD 12 and miniBTD 12[END_REF]) as variable ordering heuristic. miniBTD 12 finished in the second place by solving 79 instances while miniBTD was ranked third with 74 solved instances.

Experimental Evaluation on COP Instances

This section is devoted to the evaluation of the behavior of our heuristic when solving COP instances (optimization problem). Note that the constraint optimization problem (COP) differs from the constraint satisfaction problem by only the addition of an objective function to optimize. So solving a COP instance consists in assigning all the variables while satisfying all the constraints and optimizing the objective function. It is an NP-hard task [START_REF] Rossi | Handbook of Constraint Programming[END_REF].

We first describe the experimental protocol we use. Then, in subsection 6.2, we assess the sensitivity of our heuristic CHS to its parameters and the benefits of smoothing and resetting. Finally, we compare CHS with state-of-the-art variable ordering heuristics in subsection 6.3.

Experimental Protocol

We consider the COP instances from the 2019 XCSP3 competition 5 . Like for CSP instances, we discard 36 instances containing some global constraints which are not handled by our library yet. In the end, our benchmark contains 264 instances, including notably structured ones and instances with global constraints.

The experiments are performed in the same conditions as for CSP instances. In particular, we use the same value heuristic, the same settings for variable ordering heuristics, restarts, . . . . Regarding the solving step, we exploit a branch and bound algorithm based on MAC with restarts and denoted MAC-BnB. We distinguish three statuses when solving a COP instance. If the solver finds an optimal solution and proves the optimality within the allocated time slot (30 minutes), the instance has the status OPT meaning that it is has been optimally solved. However, if the solver has found a solution but cannot establish its optimality, the instance has the status SAT meaning that a solution has been found in the CSP sense but with no guarantee with respect to the objective function. In such a case, the solver has only produced an upper bound (resp. a lower bound) if the instance aims to minimize (resp. maximize) the objective function. Finally, if the solver proves that the instance has no solution, the instance has the status UNSAT. In the following, an instance is said solved if it has the status OPT or UNSAT.

Impact of CHS Settings

In this part, we assess the sensitivity of CHS with respect to the chosen values for α 0 or δ when solving COP instances. First, we study the impact of α 0 value. With this aim in view, we set δ to 10 -4 and then vary the value of α 0 between 0.1 and 0.9 with a step of 0.1. Table 12 provides the number of instances having the status OPT, UNSAT or SAT depending on the initial value of α 0 and the corresponding cumulative runtime. We also provide the results of the Virtual Best Solver (VBS) built on the basis of this nine combinations of MAC-BnB and CHS. Table 12 shows that the results obtained for the different values of α 0 are relatively close to each others. Indeed, if we consider the number of solved instances, the best combination (α 0 = 0.4) solves in average 6 additional instances and the gap with the worst one is 13 instances. Regarding the runtime, MAC-BnB and CHS with α 0 = 0.4 correspond again to the best combination with a cumulative runtime of 62.38 h. The other combinations are generally 5% slower, except for the values 0.8 and 0.9 of α 0 for which the rate is about 10%. Globally, these results are consistent with ones obtained when solving CSP instances and show again the robustness of CHS with respect to the value of α 0 . This robustness is also highlighted by the fact that all the curves in Figure 8 are quite close. Moreover, from this figure, we can note that α 0 = 0.4 is the best choice among the experimented values. Indeed, the corresponding curve is almost always above the others.

Regarding the Virtual Best Solver (VBS) in Table 12, we note that it can solve 14 additional instances than MAC-BnB and CHS with α 0 = 0.4 while saving 3.34 hours. If we consider the results instance per instance, we observe that 103 instances among the ones solved by the VBS are solved whatever the chosen value for α 0 . Furthermore, 20 instances among the 38 remaining ones are solved by more than half of the combinations. Finally, the 18 remaining instances seem harder to solve with an average runtime for the VBS about 819 seconds. Now, we set α 0 to 0.4 and consider different values of δ (see Table 13). The observations are similar to those presented previously, showing the robustness of CHS regarding δ. It turns out that using a non-zero values for δ allows MAC-BnB to perform better. This shows the relevance of introducing δ in CHS. Finally, like for the CSP solving, the value 10 -4 leads to obtain the best results in terms of the number of solved instances as well as the runtime.

Table 14 gives the results of MAC-BnB+CHS (α 0 = 0.4, δ = 10 -4 ) with smoothing (+s) the constraint scores or without (-s) and/or with resetting (+r) the value of α to 0.4 at each new restart or without (-r). The observed behaviors clearly support the importance of smoothing and restarts for CHS. For example, MAC-BnB with CHS+s-r solves 5 less instances than MAC-BnB with CHS, while MAC-BnB with CHS-s-r solves 11 instances less. In addition, it can be noted that removing the smoothing or the resetting lead to an increase in runtime.

CHS vs. Other Search Heuristics

In this part, we compare CHS (with α 0 = 0.4 and δ = 10 -4 ) to other search strategies from the state-of-the-art, namely dom/wdeg, wdeg ca.cd , ABS and CHB. We also consider the variant dom/wdeg+s that we introduced for dom/wdeg. Figure 9 presents the number of solved instances as a function of the elapsed time for each considered heuristic. Clearly, CHS turns to be the more efficient heuristics. Indeed, MAC-BnB with CHS solves at least 13 additional instances than with any other considered heuristic while performing faster. More interestingly, CHS outperforms CHB with 49 additional solved instances. Nevertheless, no heuristic outperforms another for all instances or families of instances. So, Tables 15 and16 give some details for each family of instances considered in the competition. They allow to have a better insight of the kind of instances for which CHS is relevant. Note that we do not consider CHB in order to have a relevant comparison for instances which are solved with all the heuristics. Indeed, considering CHB dramatically reduces the number of instances solved by all the heuristics. Like for the decision problem, CHS is not always the better heuristic, but, it turns to be the more robust one. Finally, we can also remark that whatever the values chosen for α 0 or δ among the considered one, CHS performs better than the state-of-the-art heuristics. This observation still holds if CHS does not exploit smoothing and/or reset of α.

Conclusion

We have proposed CHS, a new variable ordering heuristic for CSP based on the search history and designed following techniques inspired from reinforcement learning. The experimental results confirm the relevance of CHS, which is competitive with the most powerful heuristics, when implemented in solvers based on MAC or tree-decomposition exploitation. Our experiments also shows that CHS turns to be relevant for solving COP instances.

The experimental study suggests that the initial value of α parameter value could be refined. We will explore the possibility of defining its value depending on the instance to be solved. For example, we will look for probing techniques to fix its appropriate value. Furthermore, similarly to the ABS heuristic, we will also consider including information provided by filtering operations in CHS. Finally, we will measure the impact of CHS on solving other problems under constraints, such as counting and optimization when modeled as weighted CSP.

1 m

 1 Given a time series of m numbers y = (y 1 , y 2 , • • • , y m ), the simple average of y is m i=1 y i where each y i has the same weight 1 m . There are situations where recent data are more relevant than old data to describe the current situation. The Exponential Recency

Algorithm 1: CHS Input: an event e 1 switch e do 2 case initialization do 3 α ← α 0 4 Conf licts ← 0 5 for c j ∈ C do 6 7 q(c j ) ← 0 8 case conf lict when f iltering with c j do 9 r(c j ) ← 1 1 12 17 case restart do 18 α ← α 0 19 for

 2345678911171819 Conf lict(cj ) ← 0 Conf licts-Conf lict(cj )+1 10 q(c j ) ← (1 -α) × q(c j ) + α × r(c j ) 11 Conf licts ← Conf licts + Conf lict(c j ) ← Conf licts13 if α > 0.06 then 14 α ← α -10 -6 15 case select a new variable do 16 return a variable x s.t. x ∈ arg min xi∈U vars(X) c j ∈C: x i ∈S(c j )∧|U vars(S(c j ))|>1 (q(cj )+δ) |Di| c j ∈ C do 20

Figure 1 :Figure 2 :

 12 Figure1: Number of solved instances as a function of the elapsed time for α0 varying between 0.1 and 0.9 and the VBS, for a runtime between 1 s and 60 s.

Figure 3 :

 3 Figure 3: Number of solved instances as a function of the elapsed time (with a logarithmic scale) for the considered heuristics (namely CHS, dom/wdeg+s, dom/wdeg, wdeg ca.cd , ABS, CHB and IBS) and the VBS based on these seven heuristics.

Figure 4 :

 4 Figure 4: Number of solved instances as a function of the elapsed time (with a logarithmic scale) for LC with the heuristics CHS, dom/wdeg+s, dom/wdeg or ABS.

Figure 5 :

 5 Figure 5: Number of solved instances as a function of the elapsed time (with a logarithmic scale) for COS with the heuristics CHS, dom/wdeg+s, dom/wdeg or ABS.

Figure 6 :Figure 7 :

 67 Figure 6: Number of instances solved by BTD-MAC+RST+Merge as a function of the elapsed time (with a logarithmic scale) with the heuristics CHS, dom/wdeg+s, dom/wdeg or ABS.

Figure 8 :

 8 Figure 8: Number of solved COP instances as a function of the elapsed time for α0 varying between 0.1 and 0.9 and the VBS.

Figure 9 :

 9 Figure 9: Number of solved instances as a function of the elapsed time for the considered heuristics (namely CHS, dom/wdeg+s, dom/wdeg, wdeg ca.cd , and ABS) and the VBS based on these five heuristics.

Table 1 :

 1 Number of instances solved by MAC+CHS depending on the value of α0 (between 0.1 and 0.9) for consistent instances (SAT), inconsistent ones (UNSAT), and all the instances (ALL) and the cumulative runtime (in hours) of MAC+CHS for all the instances.

	α 0	# solved instances SAT UNSAT ALL	time (h)
	0.1 6,530	4,212 10,742 1,038.89
	0.2 6,505	4,206 10,711 1,049.55
	0.3 6,505	4,203 10,708 1,052.04
	0.4 6,493	4,204 10,697 1,056.14
	0.5 6,509	4,202 10,711 1,058.13
	0.6 6,487	4,205 10,692 1,062.14
	0.7 6,504	4,207 10,711 1,055.46
	0.8 6,479	4,197 10,676 1,072.28
	0.9 6,473	4,203 10,676 1,071.43
	VBS 6,691	4,242 10,933	940.21
	Table

Table 2 :

 2 Number of instances solved by MAC+CHS depending on the value of α0 (between 0.025 and 0.15) for consistent instances (SAT), inconsistent ones (UNSAT), and all the instances (ALL). and the cumulative runtime (in hours) of MAC+CHS for all the instances.

	α 0	# solved instances SAT UNSAT ALL	time (h)
	0.025 6,507	4,202 10,709 1,061.07
	0.05	6,512	4,212 10,724 1,058.89
	0.075 6,500	4,204 10,704 1,064.61
	0.1	6,530	4,212 10,742 1,038.89
	0.125 6,519	4,203 10,722 1,078.10
	0.15	6,503	4,207 10,710 1,061.81

Table 3 :

 3 Impact of the value of δ on MAC+CHS regarding the number of solved instances and the cumulative runtime in hours.

	δ	SAT UNSAT	ALL	time (h)
	0	6,479	4,204 10,683 1,079.25
	10 -5 6,519	4,207 10,726 1,043.53
	10 -4 6,530	4,212 10,742 1,038.89
	10 -3 6,508	4,199 10,707 1,044.41
	Table

Table 4 :

 4 Number of instances solved by MAC with CHS with/without smoothing and reset of α and cumulative runtime in hours.

	Solver	SAT UNSAT	ALL	time (h)
	MAC+CHS (+s+r) 6,530	4,212 10,742 1,038.89
	MAC+CHS+s-r	6,520	4,209 10,729 1,043.95
	MAC+CHS-s-r	6,484	4,199 10,683 1,064.20
	MAC+CHS-s+r	6,482	4,176 10,658 1,067.72

Table 5 :

 5 Detailed results (number of instances and runtime) of MAC with CHS, dom/wdeg+s, dom/wdeg, wdeg ca.cd , ABS or CHB for each considered family.

Table 6 :

 6 Detailed results (number of instances and runtime) of MAC with CHS, dom/wdeg+s, dom/wdeg, wdeg ca.cd , ABS or CHB for each considered family (Table5continued).

	1,271
	237
	1,158

Table 7 :

 7 Detailed results (number of instances and runtime) of MAC with CHS, dom/wdeg+s, dom/wdeg, wdeg ca.cd , ABS or CHB for each considered family (Table6continued).

	CHB	#solv. time	2,967	135 354,105	21,394	609 33,109	622	24 205,826	7.17
	ABS	#solv. time	1,892	137 347,537	8,259	612 14,170	156	24 205,359	172.81
	wdeg ca.cd	#solv. time	1,195	121 399,516	13,907	613 18,716	499	24 223,707	9.50
	dom/wdeg	#solv. time	1,927	114 390,684	7,331	614 9,706	442	25 204,709	0.71
	dom/wdeg+s	#solv. time	1,793	129 385,566	7,697	613 11,569	528	26 222,532	22.46
	CHS	#solv. time	1,524	130 361,038	6,180	614 10,287	482	26 203,502	3.78
	# instances	C 109	T 337	C 607	T 614	C 24	T 148	C 4
	Family	PseudoBoolean	QRandom	QuasiGroups	QueenAttacking
									Academic

Table 8 :

 8 Detailed results (number of instances and runtime) of MAC with CHS, dom/wdeg+s, dom/wdeg, wdeg ca.cd , ABS or CHB for each considered family (Table7continued).

Table 9 :

 9 Mean and standard deviation of the difference between the number of instances solved by the VBS and the corresponding number for MAC with each heuristic.CHS dom/wdeg+s dom/wdeg wdeg ca.cd ABS CHB

	2,251
	23,687
	17,854

Table 10 :

 10 Number of instances solved by MAC with LC/COS with any auxiliary heuristic among CHS, dom/wdeg+s, dom/wdeg or ABS, and cumulative runtime in hours.

	Auxiliary	LC	COS
	heuristic	#solved time (h) #solved time (h)
	CHS	10,812 1,017.03	10,281 1,363.86
	dom/wdeg+s	10,752 1,057.91	10,265 1,368.66
	dom/wdeg	10,741 1,067.28	10,259 1,367.17
	ABS	10,718 1,090.23	10,262 1,368.99

Table 11 :

 11 Number of instances solved by BTD-MAC+RST+Merge with the heuristics CHS, dom/wdeg+s, dom/wdeg and ABS combined or not with LC , and cumulative runtime in hours.

	(Auxiliary)	without LC	with LC
	heuristic	#solved time (h) #solved time (h)
	CHS	10,770 1,035.59	10,839 1,011.22
	dom/wdeg+s	10,712 1,065.01	10,805 1,032.30
	dom/wdeg	10,672 1,089.00	10,767 1,061.63
	ABS	10,650 1,082.71	10,705 1,093.49

Table 12 :

 12 Number of instances having the status OPT, UNSAT or SAT depending on the value of α0 (between 0.1 and 0.9) and the cumulative runtime (in hours) for all the instances.

	α 0	# instances OPT UNSAT SAT	time (h)
	0.1	119	1	86	67.48
	0.2	121	1	83	66.75
	0.3	124	1	80	66.10
	0.4	126	1	78	62.38
	0.5	124	1	73	66.31
	0.6	120	1	84	68.18
	0.7	120	1	83	68.73
	0.8	113	1	91	70.65
	0.9	117	1	85	70.08
	VBS	140	1	66	59.04

Table 13 :

 13 Impact of the value of δ regarding the number of instances having the status OPT, UNSAT or SAT and the cumulative runtime in hours.

	δ	# instances OPT UNSAT SAT	time (h)
	0	120	1	84	67.89
	10 -5	123	1	82	67.21
	10 -4	126	1	78	62.38
	10 -3	121	1	84	68.47

Table 14 :

 14 Number of instances which are solved optimally (OPT), proved as inconsistent (UNSAT) or for which a solution is found (SAT) with CHS with/without smoothing and reset of α and the cumulative runtime (in hours) for all the instances.

	Variant	# instances OPT UNSAT SAT	time (h)
	CHS(+s+r)	126	1	78	62.38
	CHS+s-r	121	1	84	66.82
	CHS-s-r	115	1	81	69.73
	CHS-s+r	116	1	82	70.16

Table 15 :

 15 Detailed results (number of solved instances and runtime) with CHS, dom/wdeg+s, dom/wdeg, wdeg ca.cd

	or ABS

Table 16 :

 16 Detailed results (number of solved instances and runtime) with CHS, dom/wdeg+s, dom/wdeg, wdeg ca.cd or ABS for each considered family (Table 15 continued).

http://www.xcsp.org

http://www.xcsp.org/series

http://www.cril.univ-artois.fr/XCSP18/

Given the poor results of MAC with IBS, including IBS leads to a less relevant comparison on instances solved by MAC with each heuristic since it significantly decreases the number of such instances.

http://www.cril.univ-artois.fr/XCSP19

Acknowledgements

This work has been funded by the French Agence Nationale de la Recherche, reference ANR-16-CE40-0028.

Conflict History Based Heuristic for Constraint Satisfaction Problem Solving *


According to Walter Benjamin to "bring things spatially and humanly closer" is a social desire which the technical reproduction of art aims to satisfy (2003, p. 255). At least starting from The Work of Art in the Age of Its Technological Reproducibility, media can thus be conceived as technical forms capable of modulating temporal and spatial distance. Some media propose to bridge the divide between two or more remote subjects, while others underline the gap between here and elsewhere. Finally, others still -such as immersive technologiespromise to cancel distances and mediation itself.

The obligation of physical and social distancing imposed over the last few months, due to the Covid-19 pandemic, has subjected a large number of social, cultural, working and educational practices to digital remediation. This condition provides an opportunity to reflect analytically and critically on the very notion of 'distance' and its relationship to media and artistic practices. By proposing Remediating distances as the title of this issue of IMG journal, we have borrowed the successful term introduced by Jay David Bolter and Richard Grusin (1999) in the field of media studies, associating it with a notion that concerns our relationship with space and time. This project takes shape from the union of these terms and seeks to reflect on the ways in which physical distances are remediated. Why should we talk about remediation of distances and not simply about their mediation linked to emergency contingencies? Behind this choice lies the idea of not conceiving the media as something that comes a posteriori or subordinated to a pre-established physical and social reality. As previously noted by Marshall [START_REF] Mcluhan | Understanding Media: The Extensions of Man[END_REF], in his extended conception of communication technologies, and subsequently pointed out by Bolter and Grusin, the media do not represent or reproduce something immediate that precedes them, but participate in the continuous processes of remediation that characterize social practices: "just as there is nothing prior to the act of mediation, there is also a sense in which all mediation remediates the real. Mediation is the remediation of reality because media themselves are real and because the experience of media is the subject of remediation" (1999, p. 59).

In this sense, to speak of the remediation of distances means to reflect on the relationship that is established between technological tools and the dispositives of proxemics interaction characterizing the practices of everyday life: the architecture of a school, the seats of a cinema, road signs, behavioral norms of a given environment, etc. This process of remediation not only shapes spatial issues but also deeply affects our perception of time. Devices that punctuate the duration of the day model our understanding of time: the clock, the bells, the alternation of day and night, the lunar cycles, etc. From the invention of writing to digital devices, technology has influenced the perception of space and time [START_REF] Stiegler | La technique et le temps[END_REF]. Remediating distances thus means to consider the technical and formal infrastructures that are necessary to modulate the in-between, approaching distant subjects or objects, manipulating movement, and even allowing oneself the illusion of being able to stop, accelerate or reverse the process of an event. The recent industrialization of traces [START_REF] Jeanneret | The Trace Factory[END_REF] can therefore be seen as a tendency to compress or decompress spatial as well as temporal distances (Treleani, 2017). The tendency to propose virtual reconstructions of archaeological sites, for example, shows the will to be immersed in the past, thus abolishing temporal distances. Digital time machines [START_REF] Kaplan | The Venice Time Machine[END_REF] are devices offering immersive anachronistic experiences that bypass distance in its temporal shape. Following the further developments of Grusin's thought, we encounter a 'radical' conception of mediation, in which this term concerns more than just technologies. In a radical conception, mediation is always at work, in our encounter with others and, beyond us, as a natural process: "all bodies (whether human or nonhuman) are fundamentally media and life itself is a form of mediation" (2015, p. 132). According to this perspective, the need for physical distancing during the pandemic derives from a simple observation: in a globalized world that is characterized by the hyperstimulation of sensibilities and intersubjective relations, the medium does not coincide exclusively with a technological instrument of communication: any object or surface can be seen as a medium. We are media ourselves, in our ability to contract and spread the virus. In the context of the Covid-19 pandemic, the theoretical question of immunization, already recurrent in philosophical reflection [START_REF] Esposito | Immunitas: The protection and negation of life[END_REF][START_REF] Sloterdijk | Bubbles. Spheres I: Microspherology[END_REF]2014;2016), has therefore manifested its multiple links with the media. On closer inspection, even Giorgio Agamben's (2020) stances against political protocols and digital technologies used in the professional and educational field during the pandemic end up confirming how the biological problem of the spread of the virus intertwines with the social and media circulation of subjects and information. If our own bodies can be considered as the medium of the virus [START_REF] Maiello | Viralità postmediale. Quando il medium (del virus) siamo noi[END_REF], during the phases of greater spread of the pandemic, digital media have performed a function of community glue as well as biological and social immunization [START_REF] Zucconi | Mediazione e immunizzazione[END_REF]. In this sense, physical distancing and remote communication technologies have constituted a strategy aimed at limiting the circulation of the virus without completely annihilating intersubjective relationships and social space. If a radical network of mediations is a matter of fact in the analysis of social practices, the pandemic made visible what is at stake when digital devices replace other physical and social processes of mediation. Technical, industrial and economic structures intervene in our social relations and are strongly criticized. But it is precisely the attention paid to these technical devices that can offer us the opportunity to observe, understand and discuss the norms and practices that we have naturalized. In this sense, through the expression 'remediating distances' we intend to reflect on how the new media reconfigure preexisting communication devices already used to connect or disconnect physical environments, geographic spaces near or far. As mentioned above, the reflection goes so far as to investigate the way the interface of Zoom, Microsoft Teams, Skype or other forms of meeting at a distance reshapes but also represents and recalls the arrangement of in-person meetings. Summing up, the expression 'remediating distances' can be interpreted in two ways. On the one hand, it may be tempting to say that any technological device is a 'remedy': the lack of physical contact -that is, the fact of being in the same room-is achieved through audiovisual interaction, through a digital technology. Therefore in order to make contact possible through a media device, the latter will give us a sense of immediacy by hiding itself. Within this vision, both the live encounter and its technological remediation tend to be naturalized. On the other hand, distance is remediated precisely because it is represented by figures and elements that signify it within the media. The spatial and temporal coordinates, as well as the arrangement of the actors of the initial situation are here explicitly reconfigured according to the technical and sensorial characteristics of the new medium. On one side, thus, we could say that the notion of immediacy, the transparency of the medium, is meant to abolish distance, while on the other side, the presence of the medium reminds it in its new configurations.

The process of remediation of distances is therefore charged with environmental implications. The technologies do not simply connect two or more points on the map, they establish and exploit channels of contact, both material and immaterial; they install stations or at least define positions where the user can make their own media experience with variable forms of sensory involvement, and according to different standards of comfort. As expressed in Gilbert Simondon's thought, each technology enters into a relationship with an associated milieu that "mediates the relation between technical, fabricated elements and natural elements, at the heart of which the technical being functions" (2016, p. 57). Media and especially digital media reconfigure the public or private environment in which the spectator or user finds himself or herself when meeting others and the world. In this sense, any attempt to remediate distances seems to coincide with a "relocation" of the experience (Casetti, 2015). But speaking of environment, it becomes necessary to consider the impact on the Planet of any movement in space, the energy required to run the World Wide Web, and all the technological infrastructure through which we communicate remotely. It is no coincidence that some of the most important contemporary scholars highlighted the multiple links between the Covid-19 phenomenon and climate change [START_REF] Latour | Is This a Dress Rehearsal? The University of Chicago Press Journals[END_REF][START_REF] Mbembe | The Universal Right to Breathe[END_REF]. From our point of view, to open a reflection on the forms and techniques of distance management means to deal indirectly with the issue of the Anthropocene: to reflect on the forms of geographical dislocation and media aggregation that characterize the long and very long-term presence of man on Earth.

Long before Covid-19, words from biology and microbiology were used to describe and study the functioning of the media. The term 'viral' has been widely and freely employed as a metaphor to describe the dynamics of the dissemination of information and images on a large scale (Nahon & Hemsley, 2012;[START_REF] Mills | Virality in social media: the SPIN framework[END_REF][START_REF] Sampson | Virality: Contagion theory in the age of networks[END_REF]. At the same time, other studies have enriched the fields of media studies and visual studies by reconstructing the history of computer viruses [START_REF] Parikka | Digital contagions: A media archaeology of computer viruses[END_REF] or investigating the transformations of visual culture as biological processes [START_REF] Mitchell | Cloning terror: The war of Images, 9/11 to the Present[END_REF]. During 2020, numerous books, journal issues and essays were published to reflect on the social and political aspects of the pandemic and, therefore, on its media and visual implications. Given the impossibility of offering an exhaustive survey, we want to mention the supplement of Critical Inquiry focusing on the environmental, political, and economic consequences of the spread of the pandemic, with writings by Lorraine Daston, Catherine Malabou, Slavoj Žižek, N. Katherine Hayles and many others [START_REF] Scotch | Posts from the Pandemics[END_REF]. In the same months, some scholars used the lens of philosophy and social sciences to critically reflect on the biological but also aesthetic character of the pandemic (De Gaetano & Maiello, 2020), while a wide range of disciplinary perspectives investigated the complex relationships between face, mask and screen [START_REF] Carbone | Vi facciamo vedere noi (chi siamo). Gli schermi nella pandemia[END_REF]Leone, 2020;Lorusso, Marrone, & Jacoviello, 2020;[START_REF] Parikka | Masks: The Face Between Bodies and Networks[END_REF]. Other studies examined, from a technological and social point of view, how the media have operated and are becoming a response to the global crisis (Keidl, Hediger, Melamed, & Somaini, 2020;De Luca & Spalletta, 2020), or analyzed the impact of the pandemic on the theories, forms and practices of cinema (Baer & Hanich 2020; Barra & Noto 2020), and television [START_REF] Sala | L'altro virus. Comunicazione e disinformazione al tempo del Covid-19[END_REF]. Compared to such studies, the objective of this volume is not simply to analyze the functioning of the media during the pandemic. With the launch of the Remediating distances' Call for Papers in summer 2020, we referred to a vast and multifaceted theoretical and methodological framework, inviting the authors to draw inspiration from the pandemic contingency in order to push their gaze towards the future or towards the past. The response was extraordinary. The result is not a monograph on the pandemic but a relaunch of those research projects that, in recent years, have critically reflected on the forms of "real-time communication with a physically remote location" [START_REF] Manovich | The Language of New Media[END_REF], on the "logistics of perception" [START_REF] Virilio | War and cinema: The logistics of perception[END_REF], or on the "war at a distance" [START_REF] Farocki | Phantom images[END_REF]. The monographic session of this issue of Img Journal questions the dialectic between 'distance' and 'proximity' in the configurations and reconfigurations made possible by new media from a long-term historical and theoretical perspective. As Carlo Ginzburg (2019) pointed out, within Western culture the term 'distance' takes on both a concrete and a metaphorical meaning and its social, ethical and political implications need, today more than ever, to be investigated. To do so, we asked the various authors to extend the time horizon of the research beyond the limits of the recent discovery and diffusion of the virus to reflect on the mediatic character of architectural, military, artistic, cinematographic, performative, and educational projects that call into question the issue of distance. What emerges is a constellation of reflections that draw on current experience to analyze the ways in which different forms of media have stimulated the spectator's imagination, leading him to explore places near and far. The overall result is a reflection on the capacity of media to detach and approach, separate and join, screen and reveal. As in previous issues of the journal and due to the composite nature of the contributions, the index adopts an alphabetical order that leaves the reader the pleasure of choosing his or her own route, perhaps guided by the keywords that accompany each essay. To conclude this editorial, however, we would like to mention a possible path that winds it way through the monographic contributions of Remediating distances. The essays written by Bruno Bachimont and Pietro Montani set the theme of the issue from a philosophical point of view: the former adopts a phenomenological perspective to observe how the technical device modifies our being in the world; drawing inspiration from a neuroscientific experiment, the latter reflects on the importance of technical distancing for the emergence of a meta-operative agency as a key element of the anthropogenesis. A philosophical approach also characterizes the essay written by Cavallari, who observes how the social uses of digital media show that presence is the effect of the organization of several distances. Through different disciplinary perspectives, a series of papers bring out the infrastructural character of the mediations through which spatial distances are managed and temporal performances are optimized. From architecture to logistics, the effects of the pandemic make visible the mediations underlying daily practices. The mechanism through which Amazon managed its deliveries to customers in the first phase of the pandemic is an exemplary case study (Salles). The visual elements used to produce physical distancing in railway stations (Chevalier) and the interior architecture of houses, when the barriers between work and home space are broken by the pandemic, also show the emergence of architectural mediations that modulate physical communication in everyday environments (Charitonidou). The infrastructural processes of digital machines thus have to be questioned: Heiko Schmid looks at them through the lens of magic, arguing that the working structure of digital machines can be embedded within the long history of magic conceptions. The remediation of distances is loaded with geographical and political implications. Nicola Perugini shows how the notion of the human shield is a way to modulate the distance between different actors in war and to legitimize the use of violence. In particular, studying the human shield as a "human screen", it becomes possible to understand how what is usually called a human shield functions simultaneously as a human weapon and a media technology. According to Iain Chambers, distance is an eminently geographical and political fact. The bodies in motion of the migrants highlight the role of the Mediterranean as a medium that can be conceived both as a form of connection and as a barrier. Through a confrontation with artistic production and post-colonial theoretical debate, he invites us to reflect critically on pre-established and presumptively unchangeable cartographies and chronologies. Even the urban spaces of our cities are subject to practices of remediation. In this regard, Paola Puma investigates social distance through the notion of "nonplace", proposed by Marc Augé, and reconceives it in an original form in reference to the spaces and times of city life. In her essay, Karen Pinkus observes some spaces in New York City during Covid-19 and reflects on the pandemic as a form of anticipation of the effects of climate change. The investigation of urban spaces thus becomes a reflection on time; our present tends to coincide with a countdown of which we are impassive spectators. What emerges is the point of view of a media ecology capable of identifying the links between space and time management technologies and the sensitive topic of climate change. Francesco Casetti studies the specific media environments in which we have spent and are still spending these final months of 2020. The mask and the screen are therefore conceived as theoretical objects for a reflection on the mechanisms of creating "existential bubbles" that limit our actions and interactions with others but, at the same time, make us feel safe. Ways of constructing digital environments in which it is possible to meet or, in any case, to arouse and experience effects at a distance is central in a number of essays. Several authors test the distance/proximity dichotomy through a variety of case studies. We encounter an archaeological perspective aimed at describing the formal dispositives through which, in Western culture, distance and proximity have been produced as visual effects (Acquarelli). Emanuele Arielli focuses on a very specific aspect of digital remediation practices and remote interaction: the relationship between exposure and control of one's own image; the possibility of establishing how the other will see me, along with seeing myself being seen by the other; the redetermination of performative affordances of the spaces of communication. The functioning of immersive environments, where distances seem to be denied or reconfigured in the name of immediacy, is analysed using the tools of semiotics (Biggio).

The social and media practice of travel selfies is questioned by Kris Belden-Adams who argues that these photographs are driven by a different relational impulse than traditional travel images. Elena Moskatova reconceives the construction and functioning of media environments in relation to the philosophical question of immunization to which we made explicit reference in the first part of this editorial. The phenomenological experience of time, the problem of chronologies, and the countdown mechanism are at the center of many articles. Indeed, the remediation of time distances is the explicit focus of two contributions to the volume. Ferdinando Gizzi develops a history and archaeology of the technical representations of the divine. Pietro Conte analyzes the experiences in virtual reality that promise reunions with the dead. The remediation of distance arises here as a continuous desire to use increasingly advanced technologies to approach or cancel the threshold with the hereafter. Distance learning technologies and practices are expressly analyzed in the essay of Veronesi, Chizzoni, Raineri, Schmalz and Taferner. If the software and interfaces of remote interaction constitute the most explicit case study to investigate the relationship between media and pandemic, the understanding of these forms of communication is further enriched by the different historical and theoretical perspectives that characterize the volume. The archaeological investigation of the technical and formal dispositive through which people have interacted at a distance over time, allows us to reflect on the quality of mediations in contemporary educational and professional practices.

For this issue, we are also pleased to welcome two artistic projects. Farah Saleh approaches physical distance with an interactive dance video project featuring eleven Palestinian performers, some living in the diaspora, others in Palestine. This project underlines that distance is always a political issue. The performance re-conceives and re-appropriates the digital device as a tool for inclusion that challenges military and political barriers. Elsa Gomis interprets the topic of distance with a video installation that compares two anachronistic temporalities: through the reuse of family footage, she illustrates the feeling of grief and attempts to remediate the distance between present and past, the living and the dead. With the aim of elaborating this distance, she films herself watching images of her grandmother shot at the beginning of the 1960s. While watching these images, she mimics a connection that no longer exists, and creates a new relationship that can only be found now through fiction. The papers published in the following pages identify a theoretical and practical legacy of the terrible historical phase that we are facing in the problematic management of distances. The multidisciplinary and interdisciplinary character of the contributions, as well as the ethical and political positions that emerge in the essays, do nothing but restore the abstract and concrete, in a certain sense binding, character of the issue. The territories, temporalities and experiences investigated by the authors show how physical and social distances are linked to a series of practices, devices and norms capable of structuring spaces, times and forms of life. Our impression is that this kind of approach is the most suitable to continue to reflect on distances as mediation and therefore on the forms of remediating distances.