M Minot
email: mael.minot@liris.cnrs.fr

S N Ndiaye

C Solnon

Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem

The Sum Colouring Problem is an N P-hard problem derived from the well-known graph colouring problem. It consists in finding a proper colouring which minimizes the sum of the assigned colours rather than the number of those colours. This problem often arises in scheduling and resource allocation. In this paper, we conduct an in-depth evaluation of ILP and CP's capabilities to solve this problem, with several improvements. Moreover, we propose to combine ILP and CP in a tree decomposition with a bounded height. Finally, those methods are combined in a portfolio approach to take advantage from their complementarity.

Introduction

The Sum Colouring Problem (SCP) is an N P-hard problem derived from the well-known graph colouring problem. It consists in finding a proper colouring (i.e. an assignment of colours to vertices such that neighbour vertices have different colours) which minimizes the sum of the assigned colours rather than the number of those colours. This problem arises in a variety of real-world problems, especially in scheduling and resources allocation [START_REF] Kubale | Graph colorings[END_REF]. Many incomplete approaches have been proposed [START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF], whereas only few complete approaches have been proposed: mainly Integer Linear Programming (ILP) in [START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF], Branch and Bound (B&B), SAT and Constraint Programming (CP) in [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF]. In this paper, we propose to conduct a more in-depth evaluation of ILP and CP's capabilities to solve the SCP, with several improvements. Moreover, we use tree decomposition to improve the solution process by decomposing SCPs into independent subproblems which are solved by ILP and CP, with promising results. Finally, we show that a portfolio approach can take advantage of the complementarity of the different approaches.

Section 2 defines the SCP and gives an overview of existing approaches. Sections 3 and 4 introduce improvements for CP and ILP models. Section 5 explains how CP and ILP may be combined by means of a tree decomposition, and Section 6 introduces a portfolio approach.

The sum colouring problem

An undirected graph G = (V, E) is defined by a set V of nodes and a set E ⊆ V × V of edges. Each edge of G is an undirected pair of nodes. We note deg(v) the degree of a vertex v, i.e. deg(v) = | u ∈ V, {u, v} ∈ E |, and ∆(G) the largest degree in the graph, i.e. ∆(G) = max{deg(v), v ∈ V }.

A legal (or "proper") k-colouring of a graph G = (V, E) is a mapping c : V → [1, k] such that ∀{x, y} ∈ E, c(x) = c(y). Classic graph colouring aims at finding a proper k-colouring that minimizes k, whereas the SCP aims at finding a proper k-colouring that minimizes the sum of assigned colours, i.e., x∈V c(x). The lowest achievable sum for G is called the chromatic sum and is denoted Σ(G).

Existing bounds. In [START_REF] Thomassen | Tight bounds on the chromatic sum of a connected graph[END_REF], it is shown that

8|E| ≤ Σ(G) ≤ 3(|E|+1) 2
. In [START_REF] Kubale | Graph colorings[END_REF], it is demonstrated that Σ(G) ≤ |V | + |E|, and that an optimal sum colouring will never use strictly more than ∆(G) + 1 colours. Finally, in [START_REF] Moukrim | Lower bounds for the minimal sum coloring problem[END_REF][START_REF] Wu | Improved lower bounds for sum coloring via clique decomposition[END_REF] a lower bound is defined with respect to a clique decomposition of the graph. Definition 1. A clique is a subset of nodes which are all linked pairwise. A clique decomposition of a graph is a partition C of its vertices such that, for each set C i ∈ C, the subgraph induced by C i is a clique.

Given a clique decomposition C of G, we have Σ(G) ≥ Ci∈C |C i |•(|C i |+1)/2, as all vertices in a same clique must have different colours. Dominant colourings. Dominant colourings were discussed in [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF]: a k-colouring may be seen as an ordered partition on the vertices of the coloured graph, such that the i-th set S i contains all vertices using colour i (with 1 ≤ i ≤ k). A colouring is dominated when the vertex colour sum can be lowered simply by reassigning the indices of these sets (i.e., swapping colours) without actually altering the partition. The dominant colouring of a k-colouring c is the colouring obtained by ordering the partition defined by c by decreasing size of sets, so that S 1 is the largest set, and S k the smallest. This dominant colouring has the lowest vertex colour sum among all possible colour swappings of c.

Incomplete approaches. Many incomplete approaches were used to find approximate solutions for the SCP. A review of most of these approaches may be found in [START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF]. It classifies main contributions in three classes: greedy algorithms [START_REF] Wu | An effective heuristic algorithm for sum coloring of graphs[END_REF][START_REF] Wu | Improved lower bounds for sum coloring via clique decomposition[END_REF], local search heuristics [START_REF] Benlic | A study of breakout local search for the minimum sum coloring problem[END_REF][START_REF] Helmar | A local search heuristic for chromatic sum[END_REF] and evolutionary algorithms [START_REF] Jin | A memetic algorithm for the minimum sum coloring problem[END_REF][START_REF] Moukrim | Upper and lower bounds for the minimum sum coloring problem[END_REF][START_REF] Jin | Hybrid evolutionary search for the minimum sum coloring problem of graphs, accepted to information sciences feb[END_REF]. None of these algorithms are able to reach all best known upper and lower bounds. The percentage of instances on which the best known upper bound is reached ranges from 46 % ( [START_REF] Wu | An effective heuristic algorithm for sum coloring of graphs[END_REF][START_REF] Wu | Improved lower bounds for sum coloring via clique decomposition[END_REF]) to 90 % ( [START_REF] Jin | Hybrid evolutionary search for the minimum sum coloring problem of graphs, accepted to information sciences feb[END_REF]) on tested graphs. Such approaches can prove the optimality of a solution if the lowest upper bound happens to reach the highest lower bound. However, such proofs were only made on 21 instances out of 94, even when using all the bounds found by every methods in [START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF] simultaneously.

CP.

A basic CSP model was proposed in [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF]. For each node u ∈ V , this model includes a variable x u whose domain is

D(x u ) = [1, ∆(G) + 1].
There is a disequality constraint for each edge of the graph, i.e., ∀{u, v} ∈ E, x u = x v . The objective is to minimize the sum of all variables, i.e., u∈V x u . This model was evaluated using Choco [START_REF] Jussien | Choco: an open source java constraint programming library[END_REF]. The results were not competitive with state-of-the-art approaches: solution times on rather easy instances were long [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF]. B&B. In [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF], a B&B approach is described. At each node of the search, a lower bound is obtained by computing a clique decomposition C of the subgraph induced by uncoloured vertices. However, instead of bounding the colour sum for each clique [START_REF] Moukrim | Lower bounds for the minimal sum coloring problem[END_REF][START_REF] Wu | Improved lower bounds for sum coloring via clique decomposition[END_REF]) the authors bound it by the sum of the |C i | smallest available colours among the vertices of C i . This new bound is tighter since it takes -to some degree -the availability of colours into account. Besides, each time a proper colouring is found, its corresponding dominant colouring is computed to improve the bound. This approach obtains better results than the basic CP model, but remains limited to small graphs.

C i ∈ C by |C i | • (|C i | + 1)/2 (as proposed in
SAT. Different SAT encodings for the SCP are described in [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF]. They are experimentally compared (using different SAT solvers) with B&B and CP, on randomly generated graphs and on six DIMACS instances. On these instances, the proposed B&B and CP approaches are not competitive with the SAT portfolio ISAC [START_REF] Kadioglu | Isac-instance-specific algorithm configuration[END_REF], which obtains the best results. In this paper, we introduce new CP models which are competitive with these SAT models, and an ILP model which outperforms them on the six DIMACS instances for which results were given.

ILP. An ILP model was proposed in [START_REF] Wang | Solving the minimum sum coloring problem via binary quadratic programming[END_REF]. It associates a binary variable x uk with every pair (u, k) ∈ V × [1, ∆(G) + 1], so that x uk equals 1 iff node u uses colour k. The objective is to minimize the sum of the integers corresponding to used colours, i.e.

|V | u=1

∆(G)+1 k=1 k • x uk so that each node u ∈ V is assigned one colour, i.e.,

∆(G)+1 k=1

x uk = 1, and for each edge {u, v} ∈ E, u and v have different colours, i.e., x uk +x vk ≤ 1, ∀k ∈ [1, ∆(G) + 1]. This model was evaluated with CPLEX, showing that it is very efficient for small graphs, but that the memory cost was too high for larger ones.

New CP models for the SCP

The CP model of [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF] is very limited, as it only propagates binary difference constraints, and bounds the objective function with the sum of minimal values in domains. In this section, we propose and compare several improvements.

Initial domain reduction

Instead of using the same domain [1, ∆(G) + 1] for all variables, we propose to tighten domains by using the following property: Property 1. For every optimal sum colouring c of a graph G = (V, E), we have

∀v ∈ V, c(v) ≤ deg(v) + 1.
To prove this property, let us suppose that it does not hold for a given optimal colouring c of a graph G. It follows that there exists a vertex v in V such that c(v) > deg(v) + 1. In such a case, there exists x ∈ [1, deg(v) + 1] such that every neighbour of v has a colour different from x (since v only has deg(v) neighbours). As a consequence, a better colouring than c can be obtained by colouring v with x instead of c(v). Therefore, c is not optimal, which contradicts our initial claim.

Hence, we define D(x u ) = [1, deg(u) + 1] for each u ∈ V . This is a minor but natural improvement, with a negligible cost.

Dominant colourings

As pointed out in [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF] and recalled in Section 2, colourings found during the search may be dominated, and can be improved simply by swapping colours. This makes the upper bound go down faster at a low computing cost. Besides, these swappings break symmetries by forbidding, thanks to the update of the upper bound, the computation of colourings that are dominated by the ones already found.

AllDifferent constraints

Instead of using only binary disequality constraints to prevent neighbour vertices from being assigned the same colour, we propose to use AllDifferent constraints. This may be done in several different ways. A first possibility is to compute a clique decomposition of the graph, as defined in Def. 1. In this case, we post a global AllDifferent constraint for each clique, and a binary disequality constraint for each edge such that no clique contains its two endpoints. A second possibility is to compute a set of maximal cliques such that, for each edge, there exists at least one clique that contains its two endpoints. In this case, we post a global AllDifferent constraint for each maximal clique. This introduces redundancies in AllDifferent constraints and may prune more values, but at a higher cost.

For both approaches, we may consider different heuristics to build cliques. Several tests (not reported due to lack of space) showed us that a simple greedy construction of maximal cliques yields a good tradeoff between the time spent building the cliques, the time spent to propagate AllDifferent constraints, and the reduction of the search space. More precisely, for each vertex of the graph, we build a maximal clique in a greedy way: starting from a clique that contains this vertex, we iteratively choose the vertex with the largest degree among the vertices that can correctly extend the clique, until no such vertex exists. We then post a global AllDifferent constraint for each of these maximal cliques.

Lower bound

The main drawback of the CP model proposed in [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF] is due to the poor lower bound, which is the sum of minimal values in domains. This lower bound does not take into account the disequality constraints. A better lower bound is obtained by using a clique decomposition C, as proposed in the B&B approach of [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF]: it is defined by the sum, for each clique C i of C, of the sum of the |C i | smallest values in the union of the domains of the variables associated with vertices of C i . This new bound takes into account some disequality constraints (those between pairs of variables that belong to a same clique). However, the sum of the Combining AllDifferent and sum constraints. Better bounds may be computed by considering the global constraint that combines an AllDifferent constraint with a sum constraint on the same set of variables [START_REF] Beldiceanu | An o (nlog n) bound consistency algorithm for the conjunction of an alldifferent and an inequality between a sum of variables and a constant, and its generalization[END_REF]. In particular, [START_REF] Beldiceanu | An o (nlog n) bound consistency algorithm for the conjunction of an alldifferent and an inequality between a sum of variables and a constant, and its generalization[END_REF] proposed a bound consistency algorithm for this global constraint. The main idea relies on the notion of "blocks" of variables, defined in such a way that, for a given AllDifferent constraint, variables of the same block are interchangeable. Each block also has a set of values. An initial lower bound is computed in O(n log(n)), where n is the number of variables in the AllDifferent contraint. During the search, if a variable of a block is assigned with a value of this block, the lower bound is left unchanged, otherwise, it is updated in O(1).

Note that the clique decomposition used to compute lower bounds is different from the set of maximal cliques used to propagate disequality constraints as proposed in Section 3.3. In the clique decomposition used to compute lower bounds, some disequality constraints are missing (those between vertices that belong to different cliques). Hence, the propagation of the conjunctions of All-Different and sum global constraints (to compute the lower bound) does not ensure a proper colouring. It must be combined either with binary disequality constraints between neighbour vertices that belong to different cliques, or with AllDifferent constraints as defined in Section 3.3.

Computation of the clique decomposition. We may consider different heuristics to build clique decompositions, and different clique decompositions may lead to different bounds. To build a clique decomposition, we consider a basic greedy approach very similar to the one described in Section 3.3 to compute a set of maximal cliques: the only difference is that each time a vertex is added to a clique, it is removed from the graph so that it cannot be selected for another clique. A key point to obtain a good tradeoff between the time spent to compute bounds and the reduction of the search space lies in the frequency of the computation of a clique decomposition. In the B&B approach of [START_REF] Lecat | Exact methods for the minimum sum coloring problem[END_REF], a new clique decomposition is computed at each node of the search tree, on the subgraph induced by uncoloured vertices. This allows to compute more accurate bounds, but clique decomposition computations are rather expensive. Hence, we propose to compute a clique decomposition only once, at the root of the search tree. This partition is then used at each node of the tree to compute a new bound.

Triggering of the bound computation. Trying too early to prune branches with bound computations often leads to a loss of efficiency: when only a few vertices are coloured, we do not have enough information as to how the colouring will turn out. The computed lower bound is thus too low to be of any use. To prevent unnecessary computations, we set a lower limit for the triggering of the bound computation: if the distance between the sum of currently assigned colours and the current upper bound amounts to more than gap %, we refrain from computing the lower bound. In addition to this lower triggering limit, we added an upper one: we refrain from using this bound when unc or less vertices are uncoloured. The reason behind this is that when only a few vertices are left uncoloured, it may be faster to explore what remains in this part of the search space rather than using a bound to try to prune this very small branch.

Experimental comparison

Experimental setup and benchmark. Programs are executed on an Intel R Xeon R CPU E5-2670 at 2.60 GHz processor, with 20,480 KB of cache memory and 4 GB of RAM. We consider 126 instances which are classically used for sum colouring, as in [START_REF] Wang | Solving the minimum sum coloring problem via binary quadratic programming[END_REF][START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF]. Some are from COLOR02/03/041 , but most of them are DIMACS instances designed for the classical colouring problem 2 . The timeout was set to 24 hours. For each instance, the reference solution is the best known upper bound, either available in the literature (mainly [START_REF] Wang | Solving the minimum sum coloring problem via binary quadratic programming[END_REF][START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF]), or previously computed by one of our approaches. It gives an overview of the state of the art. Tables also give detailed results for a set of ten instances that we chose to highlight the peculiarities of each approach.

Configurations. We implemented CP models in Gecode (version 4.2.1) [START_REF] Team | Gecode: Generic constraint development environment[END_REF]. We cannot report results for all possible combinations of the different improvements described in Sections 3.1-3.4. We have chosen the following configurations:

-Base: Basic model, with binary disequality constraints, a lower bound defined as the sum of smallest values in variable domains, and bound consistency ensured.

-AllDiff+Bound : Model with AllDifferent constraints (as defined in Section 3.3), a lower bound defined by using a clique partition and computing for each clique C i the sum of the |C i | smallest values in variables' domains, and bound consistency ensured. Parameters gap and unc are set to 20 % and 5, respectively. Experiments not detailed in this paper showed these values offer the best compromise.

-AllDiff+Bound+Swap: Same as AllDiff+Bound, but with colour swapping.

-AllDiff+Bound+Swap+Dom: Same as AllDiff+Bound+Swap, but with domain consistency instead of bound consistency.

-AllDiff+SumBound+Swap: Same as AllDiff+Bound+Swap, but lower bound computation is done by using the bound consistency algorithm of [START_REF] Beldiceanu | An o (nlog n) bound consistency algorithm for the conjunction of an alldifferent and an inequality between a sum of variables and a constant, and its generalization[END_REF]. gap and unc are respectively set to 50 % and 0 (the best setting for this configuration).

Table 1. Comparison of CP models. The first ten lines detail results for ten representative instances: best upper bound found within the time limit (UB), time needed to find UB (tUB) and to prove optimality (t proof ), if optimality has been proven. The last three lines give the average distance between UB and the reference solution (in percentage), and the number of instances for which the reference solution has been found (# Ref. sol.), and optimality has been proven (# Optim. proofs) for the 126 instances. For these five configurations, the Branch and Bound (BAB) search engine was selected. As the goal is to minimize the sum of the variables, the value ordering heuristic chooses the smallest value. We have designed and compared different variable ordering heuristics (including well-known ones such as Activity and wDeg) and the best results are obtained with minElim, that chooses the variable that has the smallest value in its domain, and break ties by choosing the variable for which this smallest value would be removed from the fewest domains. Luby was used as a restart policy, with a scale of 500.

Results. Table 1 compares CP models on 10 representative instances, and then gives global results for the whole benchmark. AllDiff+Bound outperforms Base on 6 instances out of the 10, and adding colour swapping (+Swap) allows an overall improvement of bounds and generally faster proofs. Replacing bound consistency (in AllDiff+Bound+Swap) with domain consistency (in AllDiff+Bound+Swap-+Dom) pays off on some instances, but degrades the solution process on some others. Finally, using the global constraint that combines a sum and an AllDifferent constraint improves the solution process on some instances, but also often degrades it. Actually, we noticed that, in many cases, all variables in the global constraint have very similar domains. Therefore, the bound computed for their sum is very close to the sum of the smallest values in the union of the domains.

As a conclusion, none of the proposed CP model appears to be competitive with state-of-the-art incomplete approaches, as the best model (AllDiff+Bound-+Swap) is able to reach the reference solution for only 49 instances.

Making proofs with CP. None of the configurations considered above are good at proving optimality, as proofs were only made for 11 instances. This may be due to the variable ordering heuristic minElim, which aims at quickly finding good solutions. Hence, we conducted experiments with a new CP configuration, designed to prioritize proof-making. It employs a hybrid restart policy, coupled with a scheduled heuristic change. In this configuration, we use the same setting as for AllDiff+Bound+Swap+Dom but we change the variable ordering heuristic during the search: as soon as the search endured 50 consecutive restarts without having improved the global upper bound, minElim is replaced by a heuristic that aims at proving optimality (it chooses the variable that has the highest number of uncoloured neighbours, and break ties by first choosing the variable that has the smallest value in its domain, and then the smallest current domain). When the variable ordering heuristic is changed, we also change the restart policy for a geometric policy, with a scale value of 100 and a base of 2.

Using this configuration, we are able to prove optimality for 15 instances instead of 11. Though this is an improvement of 36 %, this is still far from the state of the art. For example, using all known bounds computed with heuristic approaches, optimality was proven for 21 of the 94 instances considered in [START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF].

Integer Linear Programming

Two improvements introduced in the previous section for CP may be easily adapted to ILP. Firstly, initial domain reduction is enacted simply by declaring less variables and by removing difference constraints between nodes when the considered colour is not in the domains of both nodes. Secondly, AllDifferent constraints are modeled by adding the constraint v∈Ci x vk ≤ 1, for each clique C i and each colour k (instead of binary disequalities).

Implementation. We used ILOG CPLEX (version 12.6.2) [START_REF] Cplex | High-performance software for mathematical programming and optimization[END_REF]. To help CPLEX to avoid running out of memory, the two following parameters were added: Depth-First Search was forced as a node selection strategy, and the cuts factor was set to 1.5. Previous experiments showed us that these parameters did not significantly lessen CPLEX's ability to solve the instances we use.

Experimental results. Table 2 compares results of the initial ILP model as proposed in [START_REF] Wang | Solving the minimum sum coloring problem via binary quadratic programming[END_REF], denoted ILP, with the ILP model that includes the two improvements, denoted ILP+. The most notable improvement is due to domain reduction, since reducing domains for ILP also removes variables and constraints. Overall, improvements allowed us to increase the number of optimality proofs from 61 to 65, and the number of times the reference solution has been found from 66 to 73. Besides, the number of memory outs goes down from 28 to 23.

When comparing ILP+ to CP, we note that they perform very differently. For four instances (DSJC* and school*), ILP+ ran out of memory. Therefore, the best solution found is far from the reference solution, and from the best solution found with CP models. For qg.order60, the best solution found by ILP is far from optimality, whereas all CP models are able to reach the optimum, with two of them even proving optimality. However, for the five remaining instances, ILP either finds better solutions (ash331GPIA, le450_5b), proves optimality quicker (3-Insertions_3, r125.1), or proves optimality while CP cannot (inithx.i.3). When considering global results (on the whole benchmark), ILP+ is able to find reference solutions and to prove optimality much more often than CP, but the average distance to reference solutions is much larger, mostly because of the times it ran out of memory.

Combining CP and ILP

Experiments reported previously showed us that CP and ILP have complementary abilities: ILP is very efficient to solve small instances, but it runs out of memory for 23 instances; it never occurs with CP, but its solutions are often far from the optimum, despite a rather good average distance. We therefore propose to decompose the problem into smaller independent subproblems, and to combine CP and ILP to solve these subproblems. The goal is to identify a subset K r ⊆ V of nodes, for which we compute all proper colourings with CP. From each of these colourings, we derive an independent subproblem. Given the optimal sum colouring of each of these independent subproblems, we deduce the optimal solution of the original problem in a straightforward way. If the subproblems are small enough, they can be solved with ILP. Furthermore, when instances are well structured, we may choose the subset K r so that, for each colouring of K r , we obtain several independent subproblems (instead of a single one), even easier to solve with ILP. This idea is reminiscent of the approach called Backtracking on Tree Decomposition (BTD) [START_REF] Jégou | Hybrid backtracking bounded by tree-decomposition of constraint networks[END_REF].

In Section 5.1, we recall the basic principles of BTD and show how to use it to solve the SCP. In Section 5.2, we introduce a new decomposition, as well as a way to use it. This approach is called BFD, and can be employed to combine CP and ILP. Decomposition methods are experimentally compared in Section 5.3.

Tree decomposition Definition 2. [27]

A tree decomposition of a graph (V, E) is a couple (K, T ) where T = (I, F ) is a tree, and K : I → P(V ) is a function which associates a subset of variables K i ⊆ V (called a cluster) with every node i ∈ I such that the following conditions are satisfied:

(i) ∪ i∈I K i = V ; (ii) for each edge (v j , v k ) ∈ E, there exists a node i ∈ I such that {v j , v k } ⊆ K i ; and (iii) for all i, j, k ∈ I, if k is in a path from i to j in T , then K i ∩ K j ⊆ K k . The width of a tree decomposition is max i∈I |K i | -1. Intersections of neighbour clusters are called separators.
BTD is a generic approach that exploits a tree decomposition of the constraint (hyper)graph of a CSP to identify independent subproblems which are solved separately. More precisely, given a tree decomposition (K, T ) and a root node r ∈ I, BTD first assigns the variables of the root cluster K r . Then, BTD recursively solves, for each child i of r, the independent subproblem that contains all variables occurring in the clusters associated with the subtree rooted in i. To avoid the repeated exploration of same parts of the search space, BTD records structural (no)goods, that allow to reduce time complexity to O(nd w+1 ) with n the number of variables, d the maximum domain size and w the width of T . The space complexity is O(nsd s ) with s the size of the largest separator.

BTD may be used to solve optimization problems provided that the objective function is decomposable, i.e., once all variables of a root cluster r are assigned, the optimal solution that extends this partial assignment may be obtained by computing separately, for each child of r, the optimal solution of the subproblem associated with this child [START_REF] Jégou | Hybrid backtracking bounded by tree-decomposition of constraint networks[END_REF][START_REF] De Givry | Exploiting tree decomposition and soft local consistency in weighted csp[END_REF]. In this case, we have to record structural valued goods, i.e., pairs composed by an assignment of the variables of a separator and the optimal solution of the subproblem associated with this child for this assigment. To avoid solving to optimality a subproblem if it is obvious its optimal solution cannot be extended to a global solution, an upper bound is added to the subproblem. As soon as it is proved that the optimal solution of the subproblem cannot be lower than the upper bound, the solving of the subproblem is stopped.

BTD may be used to solve the SCP as its objective function is decomposable: given a tree decomposition of the graph to colour, once the nodes of a root cluster r are coloured, the best sum colouring that extends this partial colouring may be obtained by searching separately the best sum colouring of each child of r. Note that this is not the case, for example, of the classical colouring problem, as we cannot colour children separately when the goal is to minimize the number of used colours (as we must know the colours used by other clusters).

However, experiments on our 126 instances have shown us that many instances are poorly structured: when computing a tree decomposition with MinFill [START_REF] Kjaerulff | Triangulation of graphs -algorithms giving small total state space[END_REF], 65 instances are not decomposed at all (i.e., there is only one cluster, which contains all variables), and 103 instances have at least one cluster that contains more than 90 % of the variables. For these instances, BTD behaves poorly.

Backtracking with Flower Decomposition (BFD)

Even when the tree decomposition only contains one cluster, we may decompose it into two subsets (K r and V \ K r ): we use CP to enumerate all proper colouring of K r , and then, for each of these colourings, we use ILP to find the optimal sum colouring of V \ K r (given the colours assigned to K r ).

The idea of BFD is to exploit instance structure so that, for each colouring of K r , we may split V \K r into several subsets that may be solved to optimality with ILP independently. In other words, we propose to compute a tree decomposition with a height of 1, composed of a root cluster K r , and a set of leaf clusters which are all children of K r . The key point is to choose the nodes of K r so that we obtain leaves that are small enough to be solved to optimality with ILP. To this end, we introduce a parameter l, that enforces a limit on the size of the leaves. More precisely, for each leaf cluster K i , we ensure that

|K i \ K r | ≤ l × |V |.
Besides this hard constraint on the leaf sizes, we also aim at favoring small roots (as we have to enumerate all its proper colourings).

This flower decomposition is built as follows. We first build a tree decomposition (K, T = (I, F )) of the graph G = (V, E) with MinFill. Let S be the set of all separators, i.e., S = {K i1 ∩ K i2 |{i 1 , i 2 } ∈ F }. Given a subset S ⊆ S, we define a flower decomposition whose root is the cluster K r = ∪ s∈S s. The other clusters of the flower (the leaves) are defined by the connected components of the subgraph of G induced by V \ K r . Each leaf cluster K i is then extended by adding to it any vertex of K r adjacent to a vertex of K i . A similar process was employed in [START_REF] Jégou | An algorithmic framework for decomposing constraint networks[END_REF], where it was also demonstrated that it results in a correct tree decomposition. Of course, the quality of the obtained flower decomposition depends on the initial subset S . The goal is to find the subset S such that the resulting flower decomposition satisfies the size limit l on the leaf clusters while minimizing the size of K r . We use Gecode to solve this problem. As it is N P-hard, we limit the CPU time for computing it to 15 minutes, and use the best flower decomposition computed within this time limit. If Gecode has not found any flower decomposition that satisfies the size limit l on the leaf clusters, we build a flower decomposition which only contains two clusters and such that the root cluster contains the |V | × (1 -l) vertices with largest degrees.

As with BTD, we also enforce a limit on the size of cluster separators. In the context of BTD, this is done by merging clusters whose separators contain too many variables. In our case, however, we keep the clusters as they are: the only effect of the limit is that no valued good is recorded on the separators which exceed the limit, since doing so would be very likely to consume a large amount of memory. Moreover, if a separator corresponds to the full root cluster, there is no need to record any valued good on it, since affectations on such a separator cannot be produced more than once.

Experimental evaluation

We compare two approaches, denoted BTD and BFD. BTD refers to the classical BTD approach. In this case, the tree decomposition is built using the MinFill algorithm and CP is used to solve subproblems: leaf clusters are solved with the Gecode configuration AllDiff+Bound+Swap (that uses restarts), whereas non-leaf clusters are solved with the same configuration, but without restarts, as we need to enumerate all solutions.

BFD refers to our new approach, based on a flower decomposition. CP (All-Diff+Bound+Swap without restarts) is used to enumerate the solutions of the non-leaf clusters and ILP+ to solve the subproblems induced by the leaves for each assignment of the separators. The maximal size for the separators is set to 30. We report results with two values for the "l" parameter (that limits the size of leaf clusters): 75 % (denoted BFD 75) and 90 % (denoted BFD 90).

Table 2 reports experimental results of BTD, BFD 90 and BFD 75. When looking at the detailed results on our ten representative instances, we note that they have complementary results: BTD is better than BFD 90 and BFD 75 on DSJC250.5 and school1, BFD 90 is better on ash331GPIA, 3-Insertions_3, inithx.i.3, school1_nsh and r125.1, and BFD 75 is better on DSJC1000.1, le450_5b, qg.order60 and r125.1. For two of these instances (r125.1 and school1_nsh), the best results, over all considered approaches, are actually obtained by BFD 90.

When looking at global results over the whole benchmark, BTD is able to find the reference solution for only 17 instances (instead of 46 and 48 for BFD 90 Table 2. Comparison of ILP, ILP+, BTD, BFD 90 and BFD 75. The first ten lines detail results for as many representative instances. "#M#" in t proof means a memory out occurred. The last four lines give, for the 126 instances: the average distance from UB to the reference solution (in percentage of the reference solution); the number of instances for which the reference solution was found (# Ref. sol.); the number of instances for which optimality was proved (# Optim. proofs); the number of times search was aborted due to a lack of memory (# Out of memory). and BFD 75), and it proves optimality for 13 instances only (instead of 39 and 26). Actually, as pointed out previously, most instances have no structure at all, or only a very poor structure, and BTD is generally outperformed on them by the CP approaches introduced in Section 3. BFD 90 and BFD 75 are able to find reference solutions and to prove optimality for much more instances than BTD. Actually, even if the instance is not structured at all (i.e., there is only one cluster in the tree decomposition, which happens 40 times for our 126 instances), BFD is still able to build a flower decomposition with one root cluster (that contains |V | • (1 -l) nodes) and one leaf (that contains the remaining |V | • l variables). In this case, BFD often behaves much better than BTD. However, BFD also suffers from a relatively high average distance to reference solutions. Actually, on some instances, BFD spends a lot of time to enumerate colourings for the root cluster which cannot be extended to good solutions. However, for each of these colourings, BFD wastes a lot of time solving to optimality useless subproblems.

Comparing BFD 90 and BFD 75 proves that allowing larger leaf clusters increases the memory needs but also eases the computation of upper bounds, as it makes the root cluster smaller (less enumeration) and gives ILP a more global view of the problem, preventing it in some cases to spend too much time solving a useless subproblem to optimality. When comparing BFD with the CP approaches of Section 3, we note an increase in the number of proofs (39 and 26 instead of 11), but the average distance to the reference solution is larger. Compared with ILP+, BFD finds the reference solution less often, as with optimality proofs, but there also are less failures due to memory. Actually, BFD and ILP+ have complementary performance: BFD 90 (resp. BFD 75) performs strictly better than CPLEX on 21 (resp. 28) instances, and strictly worse on 91 (resp. 85) instances.

We have introduced different approaches for the SCP in the previous sections. Some of them are dominated, in the sense that, for each instance, there is always another approach that performs better on this instance (it finds the same solution quicker, or a better solution). This is the case of the CP configurations Base and AllDiff+Bound, as well as ILP, BTD and BFD 75. The five other approaches (namely, the three remaining CP configurations, BFD 90 and ILP+) are complementary, and we propose to combine them in a portfolio approach.

More precisely, given a solver portfolio [START_REF] Huberman | An economics approach to hard computational problems[END_REF][START_REF] Gomes | Algorithm portfolios[END_REF], the per-instance algorithm selection problem [START_REF] Rice | The algorithm selection problem[END_REF] consists in selecting the solver of the portfolio which is expected to perform best on a given instance. Algorithm selection systems usually build machine learning models to forecast which solver should be used in a particular context. Using the predictions, one or more solvers from the portfolio may be selected to be run sequentially or in parallel. In our SCP context, solver performance is highly constrained by memory bandwidth, in particular for ILP. Therefore, we cannot simply run our different solvers in parallel, and we consider the case where exactly one solver is selected.

One of the most prominent and successful systems that employs this approach is SATzilla [START_REF] Xu | SATzilla: Portfolio-based algorithm selection for SAT[END_REF], which defined the state of the art in SAT solving for a number of years. Other application areas include constraint solving [START_REF] O'mahony | Using casebased reasoning in an algorithm portfolio for constraint solving[END_REF], the travelling salesperson problem [START_REF] Kotthoff | Improving the state of the art in inexact TSP solving using per-instance algorithm selection[END_REF], subgraph isomorphism [START_REF] Kotthoff | Portfolios of subgraph isomorphism algorithms[END_REF] and AI planning [START_REF] Seipp | Learning portfolios of automatically tuned planners[END_REF]. The reader is referred to a survey [START_REF] Kotthoff | Algorithm selection for combinatorial search problems: A survey[END_REF] for additional information on algorithm selection.

The selection process is composed of two steps: given an SCP instance to be solved, we first extract features from instances; then, we run algorithm selection to choose a solver. Finally we run the selected solver on the instance.

Feature extraction. Given a graph = (V, E) for which we are looking for the chromatic sum, we compute the following features (a "*" denoting the use of the minimum, maximum, mean and standard deviation): number of nodes |V | and edges |E|, degrees of the vertices in V *, size of connected components in G*, number of constraints and variables in the ILP+ model, number of AllDifferent constraints (arity of more than 2) in the AllDiff+Bound CP model, arity of these AllDifferent constraints*. We also added features computed from the largest connected component G of G: density, theoretical upper and lower bounds of Σ(G ), number of clusters in the tree decomposition computed with MinFill. Moreover, this tree decomposition is used to compute a flower decomposition (with l = 90), which gives additional features: size of the root cluster, Cartesian product of the sizes of the domains in the root cluster, number of clusters, distance between the theoretical upper and lower bounds of the root cluster, density of the root cluster, density of leaf clusters*, number of proper variables in clusters*, separator density*, separator sizes*, the distance between theoretical upper and lower bounds on leaf clusters*, the number of binary variables* and constraints* in the ILP+ model associated with leaf clusters. Selection Model. We use Llama [START_REF] Kotthoff | LLAMA: Leveraging learning to automatically manage algorithms[END_REF] to build our solver selection model. Llama supports the most common algorithm selection approaches used in the literature. We performed a set of preliminary experiments to determine the approach that works best here, i.e., a pairwise regression approach with random forest regression. This approach trains a model that predicts the performance difference between every pair of solvers in the portfolio, similarly to what is done in [START_REF] Xu | SATzilla: Portfolio-based algorithm selection for SAT[END_REF]: if the first solver is better than the second, the difference is positive, otherwise negative. The solver with the highest cumulative performance difference (i.e., the most positive difference over all other solvers) is chosen to be run. As this approach already gives very good performance, we did not tune the parameters of the random forest machine learning algorithm. It is possible that overall performance can be improved by doing so, and we make no claims that the particular solver selection approach we use in this paper cannot be improved.

Experimental results. We use leave-one-out cross-validation to determine the performance of our portfolio approach, as we only have 126 instances in our benchmark (which is not much for training a learning model): for each instance i, we train the selection model on all instances but i, and evaluate it on i.

The set of features is computed in 5.4 minutes in average, with 110 of our instances actually being under 5 minutes. Some instances, such as latin_square_10, DSJC1000.9 or flat1000_50_0 take a prohibitive amount of time when computing our set of features, mostly because of the two decompositions needed.

Table 3 shows us that our portfolio approach obtains results that are close to those of the Virtual Best Solver (VBS), which considers the best solver for each instance separately. It often selects either the best solver, or a solver which behaves well. The VBS (resp. our portfolio approach) uses ILP+ for 67 (resp. 78) instances, BFD 90 for 10 (resp. 13) instances, AllDiff+Bound+Swap for 20 (resp. 11) instances, AllDiff+Bound+Swap+Dom for 14 (resp. 11) instances, and AllDiff+SumBound+Swap for 15 (resp. 13) instances. Even when the portfolio selects the best solver, the solving time is increased by the time needed to compute features (which may be large on some instances). Note that the time needed by the model to select a solver is negligible (0.15 seconds on average).

Our portfolio is able to prove optimality for more than half of the 126 instances. In [START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF], best upper and lower bounds are reported for a set of state-of-the-art heuristic approaches, on a subset of 92 instances. Using the best of these bounds (computed with different heuristic approaches), they can prove optimality for 21 of these instances, whereas our portfolio approach is able to prove optimality for 42 of these 92 instances, i.e., twice more. Finally, our portfolio approach has improved (resp. reached) the best upper bounds reported in [START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF] for 2 (resp. 48) of the 92 instances: for DSJR500.1 the new upper bound is 2,142 instead of 2,156, and for le450_25b it is 3,349 instead of 3,365.

Conclusion and future work

We proposed some improvements for solving the SCP with CP and ILP, and demonstrated that they have complementary advantages: ILP is efficient on small instances, but fails to solve large instances due to its large memory needs; CP never runs out of memory but is not able to compute as good solutions as ILP on small instances. We proposed a CP / ILP combination that may be used as a compromise between CP and ILP. Besides, since it makes use of tree decomposition, this combination is better than CP or ILP alone to solve some well-structured instances. We combined those methods in a portfolio approach which obtains results close to those of the virtual best solver. It has been able to prove optimality for more than half of the considered instances. It has also been able to improve the best known upper bounds for two instances.

In the future, the use of a dedicated decomposition algorithm might be studied, in order to build a flower decomposition from scratch rather than resorting to an initial tree decomposition. The goal would be to make it more straightforward to obtain a balanced decomposition. Being able to automatically fine-tune BFD's parameters (l as well as the maximal size of separators) could also prove useful.

A major drawback of BFD is that some subproblems are solved to optimality even if they are useless due to poor assignments in the root. An interesting improvement that we shall investigate in further research would be to prevent ILP from spending more that a set amount of time on a leaf cluster, and to ask for a new assignment on the root if necessary. It could be seen as another form of restarts, as seen in [START_REF] Allouche | Anytime hybrid best-first search with tree decomposition for weighted csp[END_REF].

  |C i | smallest values may be a bad approximation of the chromatic sum of the subgraph induced by C i when variables of C i have different domains. Let us consider for example a clique C i = {a, b, c} with D(a) = {1, 2, 3} and D(b) = D(c) = {7, 8}. The sum of the 3 smallest values in D(a) ∪ D(b) ∪ D(c) is 1 + 2 + 3 = 6, whereas the chromatic sum of the subgraph induced by {a, b, c} is 1 + 7 + 8 = 16.

Table 3 .

 3 Detailed results, for the virtual best solver and our portfolio approach. t feat. is the time needed to compute the features. For each method, "Algo" gives the chosen algorithm. Gec1 denotes AllDiff+Bound+Swap, Gec2 AllDiff+Bound+Swap+Dom, and Gec3 AllDiff+SumBound+Swap. Times tUB and t proof for the portfolio include t feat. .

		Virtual best solver		Portfolio approach
	Name Ref. sol. Algo	UB	tUB t proof t feat. Algo	UB	tUB t proof
	DSJC250.5	3,210 Gec2	3,540 51,076		6 Gec1	3,591	845
	DSJC1000.1	8,991 Gec3 10,295 66,842		126 Gec1 10,328 3,466
	ash331GPIA	1,432 ILP+ 1,432 29,870		20 ILP+ 1,432 29,890
	3-Insert._3	92 ILP+	92	0	0	0 ILP+	92	0	0
	le450_5b	1,350 ILP+ 1,398 22,554		4 ILP+ 1,398 22,558
	qg.order60 109,800 Gec2 109,800	138	139 4,866 Gec1 109,800 5,070 5,070
	r125.1	257 BFD	257	0	0	0 BFD	257	0	0
	inithx.i.3	1,986 ILP+ 1,986	9	20	8 BFD	1,986	114	694
	school1	2,674 Gec1	3,531 75,519		18 Gec3	3,648 1,149
	school1_nsh	2,392 BFD	2,539 86,400		10 Gec3	2,992 14,166
	Average dist. (%)	4.25			5.51
	# Ref. sol.		83				76
	# Optim. proofs	66				65
	# Out of memory	0				0

http://mat.gsia.cmu.edu/COLOR02

Acknowledgements This work has been supported by the ANR project SoLStiCe (ANR-13-BS02-0002-01).


Marie Bedon

Misa Milosavljevic

Virginie Morel

Jean-Pascal Solari

Guillaume Bourhis

Roland Dauphin

Design of a valuable Fuel Couple and engine compression ratio for an Octane-On-Demand SI Engine Concept: a simulation

Keywords: Octane requirement, Octane Booster, Research Octane Number, CO 2 tailpipe emission, low octane base fuel

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Based on this, the application of so-called Octane On demand concept, whereby the fuel anti knock quality is customized to match the real time requirement of a conventional spark ignition engine has been identified as highly promising.

The objective of this study is to define the best fuel couple for the dual fuel "Octane-On-Demand" concept, including a low RON based fuel and an octane booster for minimizing global CO 2 tailpipe emissions and the octane booster consumption.

The work covers 4 octane boosters: ethanol, reformate, di-isobutylene, and Superbutol™, and two fuel baseline: non-oxygenated gasoline RON 91 and naphtha based fuel RON 71.

The present activity uses 0D vehicle simulations, based on a M-segment vehicle equipped with an up-todate 1,6L turbocharged GDI engine, to guide the choice of the fuel couple together with the optimal engine compression ratio. Dedicated inputs, such as engine octane requirement map and fuel anti-knock properties of various blends, are given to properly run the model. 1 Corresponding author. Tel: +31 88 262 21 99. Email address: marie.bedon@aramcooverseas.com

Introduction and background

The worldwide annual demand for transport energy is increasing rapidly, driven by global economic and population growth, especially in non-OECD countries (Organization for Economic Co-operation and Development). Today, around 95% [START_REF] Exxonmobil | The outlook for energy: A view to[END_REF][START_REF]Energy Information Administration[END_REF] of all transport energy comes from petroleum based liquid fuels, mainly manufactured in refineries. Even though promising alternatives to conventional fossil fuels exist today (e.g. biofuels, fuel cells, electric vehicles, etc.), many studies indicate that around 90% of transport energy will still be derived from petroleum in 2040 [START_REF] Exxonmobil | The outlook for energy: A view to[END_REF][START_REF]Energy Information Administration[END_REF]3].

However, this predicted growth in oil demand is mainly driven by the expansion of commercial transport activities, including heavy-duty, air, marine, and rail traffic which all use distillate fuels like diesel, kerosene and marine fuels [START_REF]Energy Information Administration[END_REF][3][4][5]. The projected demand (Fig. 1) of light fuel (gasoline) is to remain flat, since technological improvements (engine downsizing, hybridization, etc.) are expected to enable considerable fuel economy savings. This will ultimately lead to an abundance of lighter-end oil fractions like naphtha, directly derived from the atmospheric crude oil distillation process.

The existing refinery network is not adapted to fulfill this expected imbalance in demand between light distillates and heavier fuels and considerable investments in refinery conversion units will be necessary.

In addition to economic considerations, more complex refinery process units also imply more CO 2 emissions. This scenario will probably lead to an unwanted increase in the well-to-tank carbon footprint of petroleum-based fuels.

In recent years, legislation for reducing CO 2 emissions emitted by passenger cars and light duty vehicles has been initiated in Europe. The 2020 target of 95 g CO 2 /km is very challenging and will require further technology improvements. To achieve this target, a lot of effort over the past decade has been put in place to develop compression ignition engine technology, given its higher intrinsic efficiency compared to spark-ignition engines. However, recent improvements in gasoline engine efficiency, mainly driven by the introduction of downsizing and its associated technologies, have demonstrated that there is still opportunity for this technology to contribute to the reduction of CO 2 emissions.

The efficiency of a spark ignition engine is often limited by the knock phenomenon which is intrinsically related to auto ignition properties of the fuel, commonly measured by RON (Research Octane Number), where a higher RON indicates better anti-knock properties. Indeed, without knock, the combustion phasing can be tuned optimally, regardless of the engine speed and load, leading to better cycle efficiency. Moreover, engine compression ratio can be increased for a further improvement in thermodynamic efficiency.

Nevertheless, a high RON is not necessary over the entire engine map, especially when running at low load.

Based on this principle, having a variable fuel RON quality and adjusting it as any other engine operating parameter has been identified as a promising engineering approach to increase the global engine efficiency and consequently reduce CO 2 tailpipe emissions.

Motivated by the existing energy landscape and outlooks, and with the initiative to promote a responsible use of petroleum products in the transportation sector, Saudi Aramco is pursuing collaborative research programs with IFP Energies nouvelles to develop and demonstrate novel fuel/engine solutions, capable of addressing modern technological and environmental challenges. One of the joint research initiatives aims at developing the "Octane on Demand" (OOD) concept on an SI engine by adapting the octane level of the fuel on an as-needed basis. This concept relies on a dual fuel system, using a low RON base fuel and an octane booster, blended in the cylinder in real time.

The present work is intended as a step toward proving the feasibility of the OOD concept. The objective is to identify the best combination of base fuel, octane booster, and engine compression ratio, to minimize both CO 2 emissions and octane booster consumption, which is considered as a high value product. In this respect, a 0D vehicle simulator has been built and validated, using the following results as relevant inputs: Bourhis et al. [START_REF] Bourhis | Measurement of RON Requirements for Turbocharged SI Engines: One Step to the Octane on Demand Concept[END_REF] characterized the octane requirement of a 1.6L turbocharged DI multi cylinder gasoline engine for three different compression ratios, using TRF (Toluene Reference Fuels).

Rankovic et al. [START_REF] Rankovic | Understanding octane number evolution for enabling alternative low RON refinery streams and octane boosters as transportation fuels[END_REF] identified experimentally, based on CFR engine measurements, RON blending rules of a complete fuel matrix when blending low RON based fuel (two baseline) with various octane boosters (four boosters).

Simulation Tool: set-up, validation and calculation matrix

AMESIM simulator set-up

In order to identify the benefit of the OOD concept on a vehicle over various driving cycles, a 0D simulator was built using LMS.Imagine.Lab Amesim® platform [8]. LMS Amesim DRIVE library [START_REF] Dabadie | A new tool for advanced vehicle simulation, 7th ICE[END_REF], developed by IFP Energies nouvelles, allows to build a complete vehicle physical model as well as its environment with the road profile, car dynamics, gearbox and the driver. The internal combustion engine model is based on fuel consumption map reading and the correction factors dependent on the driver solicitations as well as on the thermal conditions of the engine (as the real engine control unit). With that method the car model reproduces the resistive load taking into consideration its wheel and aerodynamic characteristics, wind speed and direction as well as the road slope. That resistive force is sent to the gearbox which adapts the engine speed to the desired vehicle velocity. Bearing in mind its gear efficiency and inertia, the torque demand and speed are communicated to the engine. Following the specified speed profile and norm specified gear shifting, the driver model requests the engine load to satisfy the speed request.

0D vehicle simulation based on engine bench and chassis-dyno tests allows the concept evaluation upstream of any prototype, thus shortening the project duration and decreasing the costs.

Simulation results should provide the best compromise among the different internal combustion engine (ICE) compression ratios and dual fuel combinations in order to take the best of the low octane fuel to improve engine efficiency and to decrease CO 2 emissions.

Amesim DRIVE library was used to build the vehicle model based on M-segment vehicle (Citroën Grand C4 Picasso) with the associated longitudinal dynamics.

Vehicle parameters are given in Table 1, and overall view of the simulator sketch in Fig 3 .    The internal combustion engine dedicated to the OOD concept is a GDI 1.6l turbocharged engine, modeled by its fuel consumption map coming from engine tests with three engine compression ratios (7.5, 10.5 -stock version and 12:1) running on four octane boosters (reformate -ethanol -DIB -SuperButolTM) and two base fuels (RON71 and RON 91 -see paragraph 3.1). At this stage of the program, the simulations did not consider cold operation and the driving cycles were run with engine coolant temperature of 90° C. A specific IFP-DRIVE library engine model was developed in order to take into account dual-fuel concepts.

The engine was linked to a vehicle drivetrain by a 6-gear manual gearbox modeled by the gear ratios and gear efficiencies. Gearbox parameters are given in Table 2 In order to cover a large vehicle operating range and test the concept in various dynamic conditions, two driving cycles were chosen: the New European Driving Cycle (NEDC) as current normative cycle, and the worldwide harmonized Light duty driving Test Cycle (WLTC) as expected future normative cycle (presented in paragraph 2.3).

The driving cycles target was followed by a driver model based on a Proportional-Integral-Derivative regulator (PID). This element manage load request and brake command to follow the vehicle speed specified by the driving cycle.

The simulator was also able to consider the ambient and road conditions as wind speed, air density and temperature as well as the road slope and the vehicle load. In the normative cycles, the conditions was considered as standard (ambient temperature: 20°C and air density: 1.185 kg/m3) without any supplementary vehicle load nor wind speed. Finally, constant auxiliary power taken from the engine was integrated in the simulator in order to consider electric consumers.

Simulator validation

Before assessing the potential of a new dual fuel concept, the vehicle model needs to be preliminary validated based on its in-field production version. To do so, an M-segment vehicle run on a roller bench over the NEDC driving cycle was used in order to fine tune the vehicle gear train and thus get the right torque demand and engine speed. Vehicle stopped, experimental engine load was fitted to find auxiliary torque demand. (See Fig. 2) Engine to vehicle speed experimental and simulation fitting was done by the wheel dynamic radius as the gear train ratios are known. Engine torque demand in steady conditions was adjusted with gear efficiencies. In vehicle speed transients, powertrain inertia was set in order to achieve similar torque overshoots.

The maximal engine speed and torque fitting error was found at the very beginning of the transient and was due to the driver controller anticipation capability and its controller sensitivity. Nevertheless, engine speed error remained under 200 rev/min during light transients. The torque demand error remained under 5 N.m out of harsher transients. In steady state operation, the error was near zero for speed and torque.

Zero load operation showed that electric consumers request 100W. These results were considered as acceptable for the purposes of the study.

The fuel consumption over the NEDC cycle for this specific vehicle is announced by the car maker at 6.0 L/100km. That result is obtained when the vehicle macerates at 20°C prior testing, and consequently with a cold powertrain operation (engine over-consumes during heating process). The simulator, which ran with the engine at 90°C (coolant temperature) over the entire cycle, consumes 5.9 L/100km of SP95 E5 fuel (reference fuel), which is equivalent to 138 gCO 2 /km. These results demonstrated the validity of the simulator and will be used as the reference for further comparisons.

Dual-fuel simulation: driving cycles and fuel/engine calculation matrix

The simulations were performed on two driving cycles (Fig. 4 & Fig. 5). WLTC cycle: a series of data points representing the speed of vehicle versus time). The first cycle is the homologation cycle commonly used in Europe (NEDC) (Fig. 4).

The second one is the upcoming homologation cycle, referred to as WLTC (Worldwide harmonized Light duty driving Test Cycle) (Fig. 5). WLTC is a more severe cycle than its predecessor NEDC, especially with regards to transient conditions and is considered to be more representative of real driving conditions.

As a result, when evaluating the benefit in fuel consumption and CO2 emissions of the OOD concept, results derived from the simulation on this cycle will be given greater weight.

24 engine/fuel configurations (detailed in the next paragraph) were run over the two driving cycles (Table 3)

Model inputs: fuel behavior & engine octane requirement map

Fuel presentation

As mentioned in the introduction, developing the Octane on Demand concept requires an appropriate selection of octane enhancers and a deep understanding of their behavior when blended with a low octane base fuel. Table 4 gives the properties of the fuels considered.

Base Fuels: Non-Oxygenated Gasoline (NOG) RON 91 corresponds to the exact RON of the non-oxygenated gasoline used in this study as low RON gasoline.

Naphtha-based fuel RON 71, which is a blend of pure straight-run, desulfurized whole boiling range naphtha RON 53 and non-oxygenated gasoline RON 91 with the respective volume rates of 56% and 44%. Naphtha is a generic term describing the fraction of crude oil distilled within the 30-180°C range. It is composed of C5 to C11 hydrocarbons and has a low RON, roughly within the 40-70 range. It is a refinery product that could potentially be beneficial for reducing the CO 2 footprint of fuel from well-totank as a result of lower refinery processing when compared to commercial gasoline. Naphtha is only processed in the crude atmospheric distillation tower and undergoes light hydrodesulphurization, in contrast to commercial gasoline which is a blend of streams coming from different conversion units such as catalytic reformers, Fluid-Catalytic-Cracking (FCC), Isomerization or Alkylation, all being energy intensive and costly processes dedicated to increase the octane number of the fuel. From the perspective of reducing CO2 emissions from tank-to-wheel, compared to gasoline fuel, naphtha also presents an intrinsic benefit. Indeed, with a higher H/C ratio along with a higher energy content (Lower Heating Value, LHV), naphtha can directly lead to tailpipe CO2 reduction benefits. Depending on the process unit parameters, naphtha can theoretically deliver a CO2 benefit of 4 to 7% assuming the same engine efficiency (Fig. 6). With these considerations, naphtha is identified as a promising low RON base fuel.

Octane boosters:

1. Reformate (RON 111) is the main product of catalytic reforming, a refinery process that transforms heavy naphtha (80-180 °C boiling range) into a pool rich in aromatics (mainly C7 to C10). In the present study, a generic Reformate has been used with 97 m. % of aromatic molecules (C7 to C10).

Compared to ethanol and SuperButol TM (presented below), Reformate has the highest RON, density and LHV (in MJ/L), but the lowest H/C ratio.

2. Ethanol (RON 108), is a well-known and widely used octane booster. Today, ethanol is present on the worldwide fuel market (mainly US, Europe and Brazil). Currently, most conventional gasoline engines are compatible with European unleaded RON95-E10 fuel which contains up to 10%vol ethanol blended with gasoline. Ethanol allows a natural CO 2 benefit in a combustion process because of its H/C ratio, despite its low LHV compared to conventional oil-derived fuels. Moreover, ethanol is a renewable energy fuel produced by a biochemical process and hence delivers a reduced fuel CO2 footprint when blended with gasoline. [START_REF] Dabadie | A new tool for advanced vehicle simulation, 7th ICE[END_REF][START_REF]Well-to-Wheels Report[END_REF][START_REF] Christensen | Renewable oxygenate blending effects on gasoline properties[END_REF].

3. SuperButol TM (RON 107), is an octane booster which is produced in a conversion process patented by Saudi Aramco [8, 9] by simultaneously dimerizing and hydrating a hydrocarbon stream rich in C4 olefin molecules. In terms of composition, SuperButolTM consists of variable proportions of butanols and diisobutylenes (DIB), with 2-butanol being the major component. Butanols have the advantage of high neat RON values (98 for 1-butanol, 105 for 2-butanol and iso-butanol [11]) and of lowering gasoline vapor pressure, making it easy to meet Reid Vapor Pressure (RVP) constrains of gasoline even without removing light-end molecules. In addition, incorporating C4 oxygenates produced from syngas or renewable sources could lead to substantial fossil energy savings and avoid significant amount of GHG emissions associated to gasoline [START_REF] Christensen | Renewable oxygenate blending effects on gasoline properties[END_REF].

DIB (RON 104

) is a mixture of 2,4,4-trimethyl-1-pentene and 2,4,4-trimethyl-2-pentene (3.75:1 mass ratio). This booster, with 104 RON, enables to lower the scale of RON value for booster pool.

-RON Characterisation of blended fuels

RON measurements on CFR engine tests were performed to define anti-knock properties of a wide range of fuel mixtures for various incorporation rates of octane booster [START_REF] Rankovic | Understanding octane number evolution for enabling alternative low RON refinery streams and octane boosters as transportation fuels[END_REF]. The results are displayed in Fig. 7.

Among multiple results, it is worth mentioning that for almost all blends, the effect of incorporating any of the studied boosters on a volumetric basis is non-linear, with the exception of reformate. In addition, the slope of RON evolution decreases with the incorporation rate, suggesting an improved 'boosting' effect at low concentrations of octane booster. Ethanol exhibits the strongest non-linear "boosting" effect, whilst reformate has the lowest one, in spite of its highest RON value.

These results also highlight the interesting potential for using a low RON base fuel. Indeed, starting with a RON of 71, an addition of 30 vol. % of ethanol is enough to almost reach the same anti-knock properties as a commercial RON 95 unleaded gasoline. The RON reached with 60 vol. % of ethanol is roughly the same whether using either a RON 71 or a RON 91 base-fuel. This shows the advantage and the potential of using less processed fuels.

As a conclusion, relatively high RON can be achieved by mixing small amounts of octane booster with a low RON base fuel, due to the non-linear behavior of RON with respect to the booster incorporation rate.

-Engine octane requirement map with TRF

In previous work, Bourhis et al. [START_REF] Bourhis | Measurement of RON Requirements for Turbocharged SI Engines: One Step to the Octane on Demand Concept[END_REF] characterized the anti-knock (or RON) requirements of a state-of-theart turbocharged SI engine. Dedicated tests were performed on this engine using surrogate fuels, referred to hereafter as TRF (Toluene Reference Fuels). RON was widely varied from 71 to 111 and tested on three different compression ratios of 7.5, 10.5 and 12. -Regardless of the engine compression ratio, the engine can be run at its optimal efficiency on its entire map when the RON of the fuel is adjusted to the engine needs (from 71 to 105); -The engine optimal efficiency can be maintained over a significant operating area at low and mid load with only pure RON 71.

Results and discussion

Octane requirement over driving cycles: towards demonstration of the OOD concept value

Fig. 11 and Fig. 12 depict the octane requirement of the engine when running at its optimal efficiency, over the two driving cycles NEDC and WLTC, for the three tested compression ratios. The black line represents the instantaneous octane requirement as a function of time while the green dashed lines depict volumetric average of the octane requirement during the whole driving cycle. Finally, the red dashed line positions the RON 95 of standard commercial gasoline. The pie graphs represent the required ratios (%vol.) of different octane ranges.

From these figures, it is interesting to note that:  On average, the driver's RON requirement is significantly lower than the octane quality of a standard RON 95 commercial gasoline fuel: green dashed lines (the average RON need) are always well below the (commercial RON 95 gasoline value (red dashed line).

 With CR 7.5:

-71 RON fuel represents roughly 100% of fuel consumed at optimal combustion phasing on the NEDC cycle and 94% on the WLTC cycle; -The RON needed to run the engine at optimal spark advance on WLTC does not exceed 95, even during the most demanding accelerations.

 With the CR 10.5 (stock engine configuration):

-RON 71 fuel represents 63% of fuel consumed at optimal combustion phasing on the NEDC cycle and 44% on the WLTC; -80% of NEDC cycle can be ran at optimal spark advance with a fuel having a RON under 90.8 whereas 61% of WLTC cycle runs with RON under 90.8.

-On the WLTC cycle, RON above 95 is only necessary to perform the most severe transient conditions at optimal combustion phasing. RON95 is rarely requested on the NEDC cycle.

 With CR 12:

-71 RON fuel represents 50% of the fuel consumed at optimal combustion phasing on the NEDC cycle and 40% on the WLTC cycle; -On both cycles, the full range of RON is used to maintain the optimal combustion phasing.

However, 89% and 74% of fuel consumed on NEDC and WLTC respectively have a RON lower or equal to 97.5. These simulation results point out the over RON quality of commercial gasoline fuel over a significant part of homologated or "real" driving cycles when driving an M-segment passenger car. Most of the time, a lower RON 71 fuel is sufficient to run the engine at its optimal efficiency. A fuel RON95 value is only needed for specific peak driver' request.

Selection of the best compression ratio (CR)

The complete CO 2 optimization of the OOD concept implies to define the best fuel couple (base fuel and booster) and the engine design through the compression ratio specification, as a whole. It can be seen that, regardless of the cycle and the fuel combination used, cycle CO 2 emissions are minimized with CR 10.5 and CR12 and maximized with CR7.5 (Fig. 13). This is consistent with the previous analysis directly made from engine test bed results with TRF [START_REF] Bourhis | Measurement of RON Requirements for Turbocharged SI Engines: One Step to the Octane on Demand Concept[END_REF]. Indeed:  When increasing the CR 7.5 to 10.5, significant decreasing of CO2 emissions are reported (8g average). Actually, the engine BSFC (Brake Specific Fuel Consumption) is increased over the entire map as illustrated in Fig. 14 mainly due to a better theoretical efficiency (in the reference Beau de Rochas cycle, higher the CR, higher the theoretical efficiency).

 When increasing the CR 10.5 to 12, CO2 benefits are still measured (~1-2 g of benefits) but significantly lower compared to the gap shown between CR7.5 and CR10.5. Indeed, the analysis of BSFC gap between CR10.5 and CR12, as illustrated Fig. 15, highlights that:  At load > 20% of maximum BMEP, increasing the CR from 10.5 to 12 leads to BSFC benefits (CR effect on the Beau de Rochas cycle),  At very low load (<20 % of maximum BMEP), on the points the "driving cycles" mainly operate, increasing CR from 10.5 to 12 leads to a lower engine efficiency. The major reason behind that is mainly attributable to the CR12 piston shape that is less flat than the CR10.5 one. Flame propagation is altered, which slows down the combustion speed, and wall heat losses are increased as well as exhaust temperature. Detailed and relevant explanation can be found in [START_REF] Bourhis | Measurement of RON Requirements for Turbocharged SI Engines: One Step to the Octane on Demand Concept[END_REF].

In light of these findings, engine in a CR10.5 configuration has been detected as the most relevant engine configuration due to a competitive fuel consumption (global CO 2 emissions) and reasonable octane booster consumption. Moreover, the fact that the CR 10.5 already exists as a basis of comparison (stock engine and stock vehicle tests), it allows to assess the impact of the OOD concept only, with no other hardware configuration change. As a conclusion, the CR 10.5 has been identified as the best CR for the Octane On Demand program.

Selection of the most valuable fuel combination with CR 10.5

Fig. 16 represents the consumption of the base fuels and octane boosters for each fuel combination, over the NEDC and WLTC cycles. Overall cycle CO 2 emissions are also reported. Fig. 17 represents the percentage of booster use on each driving cycle for each couple of fuels.

From these figures, it can be noticed that:  Regardless of the octane booster and the driving cycle, naphtha-based fuel offers roughly 1% less CO 2 emissions (except with reformate that has a very high carbon content). This is partly related to the fuel's higher H/C ratio and LHV (low carbon content compared to gasoline), and confirms the high potential of using low RON naphtha-based fuel as a base fuel.

 In all configurations, less base fuel is consumed with RON 71 naphtha-based fuel than with RON 91 non-oxygenated gasoline. This is due to the fact that when a lower RON base fuel is used, more octane booster is needed to fulfill the mean octane requirement.

 The comparison of the global (base fuel + octane booster) fuel consumptions between RON 91 nonoxygenated gasoline and RON 71 naphtha-based fuel highly depends on the energy content of their associated octane booster. If the octane booster has a higher energy content than the base fuel, the global fuel consumption will decrease when lowering the RON of the base fuel (because it shifts the consumption of base fuel towards octane booster which has a higher energy content in this case). This is typically the case when reformate is used as an octane booster. Conversely, if the octane booster has a lower energy content than the base fuel, the global fuel consumption will increase when lowering the RON of the base fuel. This is the case with ethanol and SuperButol™.

 For both NEDC and WLTC driving cycles, ethanol and DIB, combined with RON 71 naphtha, produce the lowest CO 2 emissions. (See Fig. 16). The global volumetric fuel consumption (including base fuel and booster) is slightly higher when using ethanol (NEDC: naphtha/ethanol (6.0 L/ 100 km) -naphtha/DIB (5.8L/100 km) -WLTC: naphtha/ethanol (6.1 L/ 100 km) -naphtha/DIB (5.6L/100 km)). This is related to the lower density and LHV of ethanol.

 Because of its high octane boosting power, ethanol has the lowest rate of booster consumption on both driving cycles (Fig. 17). Then, fig. 17 shows that the rate of RON71 consumption when blended with ethanol represents respectively 86% and 76% of the total volume consumption on NEDC and WLTC.

 Finally, RON71/Ethanol offers 4.4 % CO 2 benefit when compared to E5 fuel reference (138 g/km on the NEDC cycle compared to 132 g/km and 136 g/km on WLTC cycle compared to 130 g/km). In that case, this gains could be representative of OOD concept.

Based on these results, and also considering the availability of ethanol on the market, naphtha RON 71 along with ethanol is identified as the most valuable fuel combination for the OOD concept. This fuel couple allows minimizing CO2 emissions and maximizing the benefits of using a less process oil-based fuel. conditions on WLTC. Further optimization regarding the right level of downsizing/ upsizing of the engine altogether its design itself are currently being conducted to better improve CO2 benefits and maximize base fuel consumption. This paper describes a 0D vehicle simulator for identifying the best combination of base fuel, octane booster, and engine compression ratio, and it uses CO2 emissions and octane booster consumption as evaluation criterions. Results are interesting. However, there are problems in this manuscript. This manuscript may be acceptable for publication in Fuel after significant improvement.

1. Abstract should be rewritten; too much introduction in abstract should be avoided. Some key words should also be removed. I completely reduced and modified the former abstract. I hope that this introduction will be more acceptable for you.

2. CO2 emission is not the only parameter needed to be considered, other parameters including vapor pressure, flash point, corrosive properties should be also considered. I completely understand your point of view. Effectively, all this parameter should be investigated but at a later stage of a project development. This is not the case here, we are focusing on a very advanced engineering concept close to TRL3.

3. The writing of the manuscript can be improved to make it more concise and clear. We rearranged part of the script. 4. Some errors as following: In Page 10, line 18, "Reformate (RON)" is the first octane boosters which should be listed as NO.1, and line 23, "Ethanol" is the second one. Yes, sorry for this mistake, I corrected it. Thank you for this note. In Fig. 4 (Page 26), the distance, duration and average speed should be listed as Fig. 3 Yes, sorry for this mistake, I corrected it. Thank you for this note. In Fig. 12 (Page 35), the proportion of base fuels and octane boosters should be declared. In Page 14, line 22, "BSFC" should be defined as an abbreviation for the first time. Yes, sorry for this mistake. I corrected it and created a glossary with all the abbreviations. In Page 14, line 21, "When increasing the CR 7.5 to 10.5, significant decreasing of CO2 emissions are reported (8g average)", please give some references. The figure was mentioned up in the text, but as it was not clear I mentioned the reference Line21 as well. In Fig. 13 and Fig. 14, please illustrate the meaning of these colors. Yes I agree. I added color captions explaining the color equivalences In Page 15, line 19, "Fig. 16 represents the percentage of booster use on each driving cycle for each couple of fuels." Please illustrate the final RON of these global fuel. Thanks for reporting this point, however I do not fully understand your expectation. Actually, we cannot illustrate the final RON of this global fuel as the RON is fully related to the engine requirement over the time. So, the fuel RON value matches the fuel requirement of the engine. It is the same for all fuels couples. This is just the rate of fuel baseline and booster for each couple that change over the time to meet the RON requirement. In summary, this paper may be acceptable for publication in Fuel after the above comments/concerns have been addressed.

Reviewer #2: The paper is suitable for publication with minor amendments the work is novel, a useful contribution to knowledge and I am not aware of similar work in the literature.  The Title could be condensed. We considered your input. A new appealing title is then suggested.



It seems that the base fuel octane has been predetermined rather than emerging from the calculations. Yes, that's pretty much correct. Actually, the RON91 base fuel corresponds to the current RON baseline prior to mixing with ethanol to get RON95E5. The RON 71 base fuel was elected considering strategic view of the company and based on previous internal studies.



The term "CO2" is used several times without explaining whether tailpipe or well-to-wheels emissions are referred to. Yes, effectively you are right, I precised "CO2 tailpipe emission" in the abstract and introduction sections. Then, I did not repeat each time to avoid awkwardness.



Reducing tailpipe CO2 emissions through adjustments to the H/C ratio is a trivial result, since the carbon is simply emitted elsewhere. The focus should be on the improvements possible to engine efficiency using the boosted octane. For the scope of this paper, we reported that we have 4.5% of CO2 benefits with OOD concept when to conventional engine using E5. Further optimizations regarding the right downsizing/ upsizing of the engine altogether its design itself are currently leading to better improve CO 2 benefits and reduce booster consumption.



The 71RON + boosted is an alternative fuels approach for most of the world which presents a large barrier to implementation. Recognizing that this is a scoping study, some mention should be made of using the lowest octane available in major world regions e.g. EuroSuper 95RON -what benefits would be possible in that case? Thank you for asking this relevant question. However, considering that the boosting effect of ethanol is less important when increasing the RON value of the base fuel, we do not expect to change significantly the RON value of the blend between [RON91/ethanol] and [RON95/ethanol]. So, as a result, we do not expect to have significant difference of CO2 when using RON95/ethanol when compared [RON91/ethanol]. As a pure assumption we should be around 0.1 -0.2% CO 2 benefit.



The simulation technique needs more description, at least a brief step by step explanation of the calculation, plus a reference to a more detailed description, or a more detailed explanation is a reference is not available. I agree and the part has been modified and is more detailed now. I hope this is more understandable now.  p17 reference to unpublished work seems premature: the statement that octane requirement could be reduced is only meaningful if a statement is made about retaining efficiency. I understand and consequently, I removed the unpublished reference.  A glossary would be helpful. Done, I added a glossary. Please, excuse me for this oversight.



The text is fairly clear throughout, however I would suggest a review of the language for conciseness and clarity. All script has been re modified and re read. I hope this is clearer now.

Fig. 8 ,

 8 Fig. 8, Fig. 9, Fig.10 represent the octane requirement maps of the engine for the three compression ratios,

Fig. 13 represents

 13 Fig.[START_REF] Wu | Assessment of potential life-cycle energy and greenhouse gas emission effects from using corn-based butanol as a transportation fuel[END_REF] represents CO 2 emissions over the NEDC and WLTC cycles, for all fuel combinations, and the three different compression ratios.

Fig. 1 .

 1 Fig. 1. Projected gasoline, jet fuel, and diesel demand (left axis, Exa Joules, 10 18 J), together with the ratio of middle-to-light distillates (right axis) from the World Energy Council Freeway Scenario 2050 [4].

Fig 3 Fig. 2 .Fig. 4 .Fig. 5 .Fig. 6 .

 32456 Fig 3 Amesim OOD vehicle simulator

Fig. 7 .Fig. 9 .Fig. 10 . 2 Fig. 12 .Fig. 13 .Fig. 15 .Fig. 16 .

 7910212131516 Fig. 7. Experimental RON value for blending booster with RON 91 base fuel (left) / with RON71 (right) plotted as a function of the booster volumetric incorporation rate

Figure 17

 17 Figure 17 Comparison of bse fuel use on NEDC and WLTC driving cycle for each couple of fuels [%v/v]

Table 2

 2 Simulator gear box parameters

Acknowledgements

The authors would like to acknowledge collaborators from IFP Energies nouvelles and Aramco Research & Innovation in Paris for their fruitful inputs while performing this work.

Summary and Conclusion

The present study is an additional step towards the assessment and the validation of the Octane on Demand concept, in which spark ignition (SI) engine is operated in a dual-fuel mode, with an adjustable octane quality. In a previous paper, Rankovic et al. [START_REF] Rankovic | Understanding octane number evolution for enabling alternative low RON refinery streams and octane boosters as transportation fuels[END_REF] already showed the great interest of using a RON 71 naphtha-based fuel with ethanol, the latter having a strong specific octane boosting effect as soon it is incorporated in a low RON fuel. In another paper, Bourhis et al. [START_REF] Bourhis | Measurement of RON Requirements for Turbocharged SI Engines: One Step to the Octane on Demand Concept[END_REF] characterized the octane requirement of a modern turbocharged SI engine and showed that the engine can be run at MBTE conditions over a significant area of the engine map with RON71.

Using these past results as inputs, 0D driving cycle simulations, based on an M-segment vehicle, are performed over the NEDC and WLTC homologation cycles. Two base fuels (Non-Oxygenated-Gasoline