Jean-Marie Lagniez
email: lagniez@cril.frmarquis@cril.fr

Pierre Marquis

Enhanced Caching for #SAT Solving

Keywords: Model counting, #SAT, caching

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Caching turns out to be a key ingredient of propositional model counters and compilers targeting the Decision-DNNF language for knowledge compilation. In a context of model counting or top-down Decision-DNNF knowledge compilation, caching consists in storing a model count (or a Decision-DNNF representation) for each component ϕ found in the current CNF formula, so as to refrain from re-computing it if the component is encountered again during the search. Indeed, in such a case, it is enough to retrieve the associated model count / Decision-DNNF representation from the cache (and to link to the latter so as to produce a Decision-DNNF representation with shared subcircuits in the knowledge compilation case).

A caching scheme simply is a mapping making precise how each CNF formula ϕ considered during search is represented. The quality of a caching scheme can be measured as its ability to determine efficiently whether a given CNF formula ϕ has an equivalent representation already in the cache (the time efficiency), without missing it if this is the case, while ensuring that the cache remains of a reasonable size (the space efficiency). The two aspects (time and space) are clearly linked and have a direct impact on the (time and space) complexity of the model counter/compiler into which the caching scheme is exploited.

Since the size of the cache can become huge (especially in knowledge compilation scenarios, i.e., when Decision-DNNF representations are stored), it is of the utmost importance from the practical side to limit the memory consumption through the use of a cache cleaning strategy so as to avoid out-of-memory errors. Cache cleaning strategies aim to find out entries that should be removed from the cache because they are of large size and/or are seldom activated (trade-offs are looked for).

Because caching leads to enhance the performance of model counters and compilers, a cache manager is implemented in many state-of-the-art #sat solvers, including Cachet 3 [START_REF] Sang | Combining component caching and clause learning for effective model counting[END_REF] and sharpSAT 4 [START_REF] Thurley | sharpSAT -counting models with advanced component caching and implicit BCP[END_REF], and top-down compilers, including C2D 5 [START_REF] Darwiche | Decomposable negation normal form[END_REF][START_REF] Darwiche | New advances in compiling CNF into decomposable negation normal form[END_REF], Dsharp 6 [START_REF] Muise | Dsharp: Fast d-DNNF compilation with sharpSAT[END_REF], and D4 7 [START_REF] Lagniez | An Improved Decision-DNNF Compiler[END_REF].

In this paper, we present and evaluate a caching scheme that appears empirically as a good trade-off compared to the previous caching schemes pointed out so far in the literature. In this scheme, the clauses of the current CNF formula ϕ are represented explicitly as in the standard scheme used by Cachet [START_REF] Sang | Combining component caching and clause learning for effective model counting[END_REF], thus avoiding to recognize some entries that are missed by the hybrid scheme considered in sharpSAT [START_REF] Thurley | sharpSAT -counting models with advanced component caching and implicit BCP[END_REF]. Furthermore, the size of the cache is minimized by storing for each entry the corresponding set of variables and a restricted set of residual clauses. In this restricted set, not only the satisfied clauses of Σ are omitted, but also the binary clauses of Σ considered at start (as in sharpSAT) and, more generally, every input clause which has not been shortened by the current variable assignment. We prove the correction of the caching scheme. We also present a new cache cleaning strategy that refines the one used in sharpSAT, and takes account for the ages of the entries, with dynamic resets to reflect their activities, and but also for the proportion of entries of the same size that led to positive hits (so as to try and keep in the cache the most promising entries). Finally, the results of an empirical evaluation are reported, showing the caching scheme and the cleaning strategy presented in the paper as valuable for the model counting task when achieved by the compilation-based counter D4 [START_REF] Lagniez | An Improved Decision-DNNF Compiler[END_REF].

The rest of the paper is organized as follows. In Section 2, one starts with some formal preliminaries. In Section 3, our caching scheme is presented and proved correct. In Section 4, our cache cleaning strategy is described. In Section 5, some empirical results are provided. Finally, Section 6 concludes the paper.

Formal Preliminaries

We consider a propositional language L PS defined in the usual way from a finite set PS = {x 1 , . . . , x n } of propositional symbols and the standard connectives. One assumes a preset, strict and total ordering < over PS :

x 1 < x 2 < . . . < x n-1 < x n .
3 www.cs.rochester.edu/∼kautz/Cachet/index.htm 4 sites.google.com/site/marcthurley/sharpsat 5 reasoning.cs.ucla.edu/c2d/ 6 www.haz.ca/research/dsharp/ 7 www.cril.fr/kc/ Formulae from L PS are interpreted in a classical way. A formula is consistent when it has a model, i.e., a variable assignment that makes it true. Two formulae are equivalent when they have the same models. ≡ denotes logical equivalence.

For every formula Σ in L PS , Var (Σ) is the set of propositional variables occurring in Σ. Σ denotes the number of models over Var (Σ). |Σ| denotes the size of Σ.

A literal is either a propositional variable or a negated one. For every literal , var ( ) denotes the variable x of (var (x) = x and var (¬x) = x). ∼ denotes the complementary literal of (i.e., for every variable x, ∼x = ¬x and ∼¬x = x).

A clause is a finite disjunction of literals, and a term is a finite conjunction of literals. A CNF formula Σ is a finite conjunction of clauses. Every CNF is viewed as a set of clauses, and every clause is viewed as a set of literals. A clause is valid (tautologous) when it contains complementary literals. A subclause of a clause δ corresponds to a subset of the literals occurring in δ.

The set of canonical clauses of a formula ϕ consists of all the clauses δ implied by ϕ which are such that every variable of PS appears once in each δ; it is in normal form when the clauses are listed in increasing order w.r.t. the lexicographic ordering induced by the literal ordering

x 1 < ¬x 1 < x 2 < ¬x 2 < . . . < x n-1 < ¬x n-1 < x n < ¬x n when the variable ordering is such that x 1 < x 2 < . . . < x n-1 < x n . For instance, if PS = {x 1 , x 2 , x 3 }, and ϕ = (x 1 ∨ x 2 ) ∧ (¬x 2 ∨ x 3 ), the set of canonical clauses of ϕ in normal form is the ordered set {x 1 ∨ x 2 ∨ x 3 , x 1 ∨ x 2 ∨ ¬x 3 , x 1 ∨ ¬x 2 ∨ x 3 , ¬x 1 ∨ ¬x 2 ∨ x 3 }.
The canonical clauses of ϕ correspond in a bijective way (up to a negation) to the counter-models of ϕ, i.e., the variable assignments that make it false. Clearly enough, two equivalent formulae of L PS have the same set of canonical clauses in normal form.

A term is consistent when it does not contain complementary literals. The conditioning of a CNF formula ϕ by a consistent term γ is the CNF formula ϕ | γ obtained by removing from ϕ every clause containing a literal of γ and removing from the remaining clauses every occurrence of every ∼ when is a literal of γ.

For instance, if ϕ = (x 1 ∨x 2 )∧(¬x 2 ∨x 3 ) and γ = ¬x 1 , then ϕ | γ = x 2 ∧(¬x 2 ∨x 3 ).
BCP denotes a Boolean Constraint Propagator [START_REF] Zhang | An efficient algorithm for unit propagation[END_REF][START_REF] Moskewicz | Chaff: Engineering an efficient SAT solver[END_REF], which is a key component of many solvers. BCP(ϕ) returns {∅} if there exists a unit refutation from the clauses of the CNF formula ϕ, and it returns the set of literals (unit clauses) which are derived from ϕ using unit propagation in the remaining case. For instance, if

ϕ = (x 1 ∨ x 2 ) ∧ (¬x 2 ∨ x 3 ), then BCP(ϕ ∧ ¬x 1 ) = {¬x 1 , x 2 , x 3 }.
For efficiency reasons, the propagation is not "physically" performed on the CNF (instead the set of literals derived using unit propagation is maintained). On the previous example, ϕ ∧ ¬x 1 is simplified into the empty set of clauses once BCP has been applied on it.

The primal graph of a CNF formula ϕ is the (undirected) graph (V, E) where the vertices in V correspond to the variables of ϕ and an edge of E (i.e., a couple of vertices) connecting two variables exists whenever one can find a clause of ϕ where both variables occur. Every connected component of this graph (i.e., a maximal subset of vertices which are pairwise connected by a path) corresponds to a subset of clauses of ϕ, referred to as a connected component of the formula ϕ. For instance, the primal graph of (x 1 ∨ x 2 ) ∧ (¬x 2 ∨ x 3 ) is the graph ({x 1 , x 2 , x 3 }, {{x 1 , x 2 }, {x 2 , x 3 }). Since this graph has a single connected component {x 1 , x 2 , x 3 }, the formula has a single connected component (the set of all its clauses).

An Improved Caching Scheme

In the following, we assume without loss of generality that the input CNF formula Σ does not contain any valid clauses and any unit clauses (a polynomial-time preprocessing consisting of detecting and removing valid clauses, then applying BCP on the resulting set of clauses can be used to ensure that this condition is always satisfied).

As evoked in the introduction, model counters and top-down Decision-DNNF compilers consist of search procedures that decompose recursively the input formula Σ by assigning variables in it and identifying independent components. Each time a variable is assigned in the current CNF formula ϕ considered during search, BCP is run so as to possibly simplify further the current formula ϕ through the assignment of additional variables. Thus, the current variable assignment is completed and ϕ is simplified. Whenever the clauses of ϕ can be partitioned into (at least) two disjoint components ϕ 1 and ϕ 2 , the two CNF formulae ϕ 1 and ϕ 2 can be processed independently (ϕ ≡ ϕ 1 ∧ ϕ 2 is such that ϕ = ϕ 1 × ϕ 2 and a Decision-DNNF representation of ϕ can be obtained by conjoining a Decision-DNNF representation of ϕ 1 and a Decision-DNNF representation of ϕ 2 using a decomposable ∧-node).

Every CNF formula ϕ encountered during search corresponds to a subset of the clauses of Σ, some of them being shortened through its conditioning by the current variable assignment γ once augmented by BCP. Thus, all the clauses of Σ satisfied by γ are not in the subset of clauses representing ϕ, as well as those containing at least one variable not in the set of variables of the current component. In the remaining clauses of Σ, literals that are complementary to literals occurring in γ can be removed (the corresponding clauses of Σ are shortened), leading to the clauses of ϕ. Thus, when the input is a CNF formula Σ, the CNF formulae ϕ that are encountered during search (which are the candidates to be added into the cache when they are not already in) are elements of

S(Σ) = {δ ⊆ δ | δ ∈ Σ}.
What's in a caching scheme? Formally, a caching scheme c is a mapping associating with any ϕ ∈ S(Σ) for some CNF formula Σ a representation r c (ϕ) of ϕ (this representation can be any data structure). A cache for Σ given a caching scheme c is a mapping associating with representations r c (ϕ) of CNF formulae ϕ ∈ S(Σ) their number of models ϕ (or Decision-DNNF representations of those ϕ). As expected, the size of a cache given a caching scheme c is the sum for each entry of the size of the representation r c (ϕ) stored in it plus the size of the corresponding model count ( ϕ (in binary notation) or the size of the Decision-DNNF representation of ϕ associated with r c (ϕ)). Any ϕ 1 ∈ S(Σ) is considered to be stored in the cache whenever one can find in the cache an entry r c (ϕ 2 ) such that r c (ϕ 1 ) = r c (ϕ 2 ) holds. A correct caching scheme c is a caching scheme such that for any CNF formula Σ, ϕ 1 , ϕ 2 ∈ S(Σ), if r c (ϕ 1 ) = r c (ϕ 2 ) then ϕ 1 ≡ ϕ 2 . Stated otherwise, when the representations of ϕ 1 and ϕ 2 coincide, then the two CNF formulae ϕ 1 and ϕ 2 are equivalent. Because the equality of two representations ϕ 1 and ϕ 2 given a caching scheme c is syntactic, it can be achieved efficiently, i.e., in time linear in the size of r c (ϕ 1 ) plus the size of r c (ϕ 2 ). When the caching scheme is correct, this equality relation can be viewed as a lower approximation of the equivalence relation between CNF formulae. Obviously enough, considering logical equivalence between CNF formulae would lead to the best possible lookup operation (if a CNF formula equivalent to a given ϕ has already been added to the cache, then it will be found for sure), but this is no feasible in practice (one has to keep in mind that the lookup operation is to be achieved for each ϕ encountered during search, so for exponentially many formulae in the general case; given that full equivalence testing is a coNP-complete problem, solving exponentially many instances of a coNP-complete problem would be too demanding). For the same reason, one typically requires the representation mapping r c to be computable in polynomial time (observe that, without this assumption, full equivalence testing could be simulated by representing every CNF formula ϕ by its set of canonical clauses written in normal form, which is exponentially larger than |ϕ| in the general case).

Because of the syntactic nature of the approximate equivalence test, the performance of a caching scheme depends only on two key factors: the cumulated sizes of the entries and the quality of the approximation of equivalence that is achieved. Indeed, the cumulated sizes of the entries give the size of the cache, which is the most memory-demanding ingredient of a model counter / top-down Decision-DNNF compiler. The sizes of the entries also have a direct impact on the efficiency of the model counter / top-down Decision-DNNF compiler in term of computation time (just because the times required to write entries into the cache or for the lookup operation depends directly on the sizes of the entries). The quality of the approximation of equivalence that is achieved also has a great influence on the performance of a caching scheme. A first caching scheme associated with codes that are smaller than the codes of a second caching scheme cannot be considered as better when the equivalence relation over the representations associated with the first scheme is finer than the equivalence relation over the representations associated with the second scheme. Indeed, the time overhead that results from using the second scheme (with larger codes) can be balanced by the fact that it may avoid counting the models (or compiling) several times the same CNF formulae (which are not recognized as keys of the cache when the first scheme is used). If this was not the case, in the limit, not implementing any cache -the n "no cache" scheme -would be the best strategy). Some previous caching schemes. Let us now present some caching schemes introduced so far. We assume that unit clauses (even those obtained using BCP) are not represented in the cache (there is no need of doing so).

In the standard caching scheme s8 ), every CNF formula ϕ encountered during search is represented as a string gathering the identifiers (integers) of the literals of the clauses in it, separating the clauses by zeroes. The identifier of a positive literal x i is its index i in the enumeration x 1 < x 2 < . . . < x n-1 < x n , and the identifier of a negative literal ¬x i is -i.

In the hybrid caching scheme h considered in sharpSAT, the clauses of the input CNF formula Σ are indexed in an arbitrary way (the index of the first clause of Σ is 1, the index of the second clause of Σ is 2, etc.). Every CNF formula ϕ encountered during search is represented as a pair consisting of the set of indexes of the variables occurring in ϕ (again, the identifier of x i is i) in ascending order, and the set of indexes of the clauses of Σ that are "still alive" (non satisfied) and containing at least two unassigned literals), in ascending order. A variant of h, called o, consists in omitting in the set of indexes of the clauses every index of a binary clause. Indeed, as shown in [START_REF] Thurley | sharpSAT -counting models with advanced component caching and implicit BCP[END_REF], this set is redundant since it can be reconstructed knowing the indexes of the literals occurring in it. This leads to smaller sizes of the codes, hence to a more efficient cache management.

Let us illustrate those three caching schemes on a simple example. Let

Σ = (x 1 ∨ x 2 ∨ x 4 ) ∧ (x 2 ∨ x 3 ∨ x 4 ) ∧ (x 3 ∨ x 4 ∨ x 5 ) ∧ (x 1 ∨ ¬x 6 )
be a CNF formula. Let γ = x 2 , and let ϕ be the unique component of Σ | γ simplified using BCP. We have ϕ = (x 3 ∨ x 4 ∨ x 5 ) ∧ (x 1 ∨ ¬x 6 ). This formula ϕ is represented by the string r s (ϕ) = 3, 4, 5, 0, 1, -6, 0 using the standard caching scheme. It is represented by r h (ϕ) = ({1, 3, 4, 5, 6}, {3, 4}) using the hybrid caching scheme. It is represented by r o (ϕ) = ({1, 3, 4, 5, 6}, {3}) using the variant of the hybrid caching scheme where indexes of binary clauses are omitted.

For the sake of code conciseness, indexes are typically compressed, i.e., represented using as few bits as possible (and not using a fixed format for integers). The o scheme with such a code compression is referred to as the p scheme in [START_REF] Thurley | sharpSAT -counting models with advanced component caching and implicit BCP[END_REF] ("p" stands for "packing").

Clearly enough, representing clauses by their indexes in Σ (as with the h scheme, the o scheme or the p scheme) is more efficient in term of encoding sizes than representing them explicitly (as with the s scheme). However, explicitly representing the clauses leads to a finer equivalence relation between the clause sets. Thus, stepping back to the previous example, and considering two terms

γ 1 = ¬x 1 ∧x 3 and γ 2 = x 1 ∧¬x 3 ∧x 5 , one can observe that Σ | γ 1 is equivalent to Σ | γ 2 (the resulting CNF consists of the single clause x 2 ∨ x 4 ). Σ | γ 1 and Σ | γ 2 share the same r s representation: 2, 4, 0. Contrastingly, we have r h (Σ | γ 1 ) = ({x 2 , x 4 }, {1}) while r h (Σ | γ 2 ) = ({x 2 , x 4 }, {2}
). Thus, Σ | γ 1 is not viewed as equivalent to Σ | γ 2 when the scheme h is used (the same problem happens with o and p).

Our caching scheme i and its family. Let us now introduce the caching scheme denoted by i ("i" insists on the fact that, compared to the standard scheme, some clauses of the input formula Σ are handled implicitly, i.e., they are not represented as parts of the entries of the cache for Σ). It is the caching scheme implemented (by default) in D4, but to the best of our knowledge, it has not been described so far in any paper (especially, it is not presented in [START_REF] Lagniez | An Improved Decision-DNNF Compiler[END_REF]). Since i appears empirically as quite a good scheme in comparison to previous caching schemes (see Section 5), we believe that it makes sense to specify it so as to be in position to take advantage of it in other model counters and Decision-DNNF compilers.

Let us present i in a smooth way by starting with a basic caching scheme b, which is such that for any CNF formula Σ and any ϕ ∈ S(Σ), r b (ϕ) = (V, C) where V is the set of indexes of variables of Var (ϕ) ordered in ascending way and C is the set of residual clauses of ϕ given Σ (the clauses which are not satisfied by the assignment corresponding to ϕ). With b, C is sorted by increasing clause size first, and within each cluster of clause representations having the same size, the indexes of the literals of each clause are listed in increasing order w.r.t. the lexicographic ordering induced by the literal ordering x 1 < ¬x 1 < x 2 < ¬x 2 < . . . < x n-1 < ¬x n-1 < x n < ¬x n when the variable ordering is such that x 1 < x 2 < . . . < x n-1 < x n . Multi-occurrent clauses are removed (only one occurrence per clause is kept).

When the basic caching scheme b is used, the residual clauses are represented in an explicit way, as in the s scheme and not using indexes (unlike the schemes h, o, p presented above), but they are ordered in such a way that two sets of residual clauses that differ only as to the ordering of the clauses and/or as to the ordering of literals within clauses will have the same representation C (this ordering is maintained dynamically). The indexes used for representing clauses in C also use as few bits as possible, as in the p scheme.

A variant of b, noted 2, is obtained by avoiding to store the binary clauses as with o. What makes i different of b also is the notion of residual clause under consideration. With the i caching scheme, not only the binary clauses of Σ are not stored, but every clause of ϕ that is not shortened by the corresponding variable assignment is not represented as well. Finally, with the variant i of i, one considers the same set of residual clauses as in i, but represents those clauses using indexes as in the h scheme.

Considering the previous example again, let ϕ be the unique component of

Σ | ¬x 2 . We have ϕ = (x 1 ∨ x 4 ) ∧ (x 3 ∨ x 4 ) ∧ (x 3 ∨ x 4 ∨ x 5 ) ∧ (x 1 ∨ ¬x 6 ). This formula ϕ is represented by: -r b (ϕ) = ({1, 3, 4, 5, 6}, {{1, 4}, {1, -6}, {3, 4}, {3, 4, 5}}), -r 2 (ϕ) = ({1, 3, 4, 5, 6}, {{1, 4}, {3, 4}, {3, 4, 5}}), -r i (ϕ) = ({1, 3, 4, 5, 6}, {{1, 4}, {3, 4}}). -r i (ϕ) = ({1, 3, 4, 5, 6}, {1, 2}).
Thus, no representation of any of the two clauses x 3 ∨ x 4 ∨ x 5 and x 1 ∨ ¬x 6 is stored when i or i is considered.

Interestingly, refraining from storing the clauses of Σ that have not been shortened does not question the correctness of the approach, whatever clauses are represented explicitly (by the literals in them) or implicitly (by their indexes): Proposition 1. The caching schemes i and i are correct. Proof.

-Caching scheme i. In order to show that i is correct, it is enough to prove that for any CNF Σ and any ϕ ∈ S(Σ), ϕ is fully determined by r i (ϕ) = (V, C) given Σ. The proof is constructive: it consists in considering every clause δ of Σ and to decide using r i (ϕ) whether δ (or in some case, a subclause of it) belongs to ϕ. The first case is when Var (δ) ∩ V = ∅. In this case, δ does not belong to the component ϕ. In the remaining case, there are two possibilities:

(1) either Var (δ) ⊆ V or (2) Var (δ) \ V = ∅. In case (1), we conclude that δ belongs to ϕ (even if it is not represented explicitly in C). In case (2), there are still two possibilities: if there exists no clause δ represented in C such that Var (δ ) ⊆ V and δ is a subclause of δ, then δ does not belong to the component ϕ (it is satisfied by the current variable assignment), else δ belongs to ϕ (δ or another clause of Σ has been shortened to give rise to δ ). -Caching scheme i . In order to show that i is correct, one can use the same approach as for i. The only difference concerns case [START_REF] Darwiche | New advances in compiling CNF into decomposable negation normal form[END_REF]. In this case, if the index of δ belongs to the C part of r i (ϕ), then the subclause of δ containing only its literals over variables in the V part belongs to ϕ, else δ does not belong to ϕ (it is satisfied by the current variable assignment).

An Improved Cache Cleaning Strategy

As evoked previously, on hard formulas the cache size quickly exceeds any reasonable bound, which necessitates a good cache management, especially a good approach to cache cleaning.

What is a cache cleaning strategy? A cache cleaning strategy must make precise the entries that have to be removed from the cache and an agenda for the cleaning operations (i.e., the cleaning operations can be achieved periodically, or be triggered by some events like the number of entries or the fact that the quantity of memory that is available falls down a preset threshold).

Some previous cache cleaning strategies. Observing that the utility of the cached components typically declines dramatically with age, in Cachet [6] each cached component is given a sequence number and those components that are too old are removed from the cache (the age limit is considered as an input parameter). For efficiency reasons, age checking is not done frequently; when a new component is cached, age checking is achieved on the chain that contains the newly cached component. The cache is cleared whenever the number of entries exceeds 2 21 × 10 and only 25% of the entries are kept whenever a cleaning operation takes place.

In sharpSAT [START_REF] Thurley | sharpSAT -counting models with advanced component caching and implicit BCP[END_REF], the entries to be cleaned up do not depend only on their ages (i.e., the first time they are encountered), but also on their activity levels and on their sizes. A score score(e) is associated with each entry e. At start, score(e) is given by the age of the entry but it is reset during the search each time a positive hit corresponding to the entry is obtained. All scores are divided periodically so as to penalize the oldest entries. The cache is cleared only if its size exceeds a fixed fraction of the maximal allowed size (another input parameter). Entries are considered by increasing scores and removed from the cache until a sufficient amount of space (e.g., half of the maximal allowed size) has been recovered.

Our new cache cleaning strategy. With each entry e in the cache we associate an integer value score(e) as in sharpSAT, together with a Boolean value flag(e) that is set to true once the entry hits positively. Each time a cache hit occurs on an entry e, score(e) is reset and flag(e) is set to true. Moreover, we also store information about how many entries nbTotal [s] of any given size s the cache data structure contains, as well as how many entries nbHit[s] of size s have their flag variable set to true. Here, the size of an entry is measured as the number of variables in it.

Each time tc new entries have been added to the cache (where tc is a parameter of the strategy), some cleaning is performed. All the entries of the cache are visited in order to decide the ones that must be removed. Contrary to sharpSAT, our cleaning strategy does not remove half of the entries in a systematic way, and the cleaning operations are not triggered by how filled the cache is. For each entry e, the ratio

r(e) = nbHit[|Var (e)|] nbTotal [|Var (e)|]
is computed. For each entry size, during the search, this ratio evaluates the proportion of entries of this size having led to a positive hit. In our cache cleaning strategy, entries with a high ratio r(e) are promoted. Indeed, we have observed empirically that along the search, entries e with a high ratio r(e) are often the most promising ones, i.e., if entries of the same size led to many positive hits, it is likely that e will also lead to some positive hits (this observation can be explained by the presence of variables playing symmetric roles in the instances). Thus, as a rule of thumb, it makes sense to give a bonus to such entries. Accordingly, in our cache cleaning strategy, every entry e that has a ratio r(e) less that some fixed threshold rm (another parameter), with a score(e) equals to zero and a flag(e) set to false is flushed. The other entries e are kept and their score(e) are divided by two. Whenever score(e) falls to zero, flag(e) is set to false.

Empirical Evaluation

In order to evaluate the performance of the caching schemes and of the cache cleaning strategies, we performed a number of experiments.

Setting. All the experiments have been conducted on a cluster equipped with quadcore bi-processors Intel XEON E5-5637 v4 (3.5 GHz) and 128 GiB of memory. The kernel used was CentOS 7, Linux version 3.10.0-514.16.1.el7.x86 64.

The compiler used was gcc version 5.3.1. A time-out of 1h and a memory-out of 7.6 GiB has been considered for each instance.

We have considered 703 CNF instances from the sat LIBrary,9 and other repositories (for instance, the benchmarks from the BN family (Bayesian networks) come from http://reasoning.cs.ucla.edu/ace/). We removed from them all those instances which are easy enough to be solved by the compilation-based counter D4 in less that 3600s without using any caching technique. We retained only 225 instances. These instances are gathered in 8 datasets, as follows: BN (82), bmc [START_REF] Zhang | An efficient algorithm for unit propagation[END_REF], Circuit (12), Configuration (22), Handmade [START_REF] Sang | Combining component caching and clause learning for effective model counting[END_REF], Planning (85), Random (5), Qif (3), Scheduling [START_REF] Darwiche | New advances in compiling CNF into decomposable negation normal form[END_REF]. The number of variables (resp. clauses) in those "hard" instances vary in [100, 119003] (resp. [150,386342]) with an average value equal to 3314(±10304) (resp. 13904(±43864)).

Name Explicit / Implicit All residual clauses Not binary Not shortened n - - - - b E 2 E i E h I p I i I
Table 1: Seven caching schemes considered in the paper.

D4 has been used in the model counter mode: when invoked with option -mc, D4 explores the same search space as the one considered when it is used as a Decision-DNNF compiler, but stores in its cache model counts instead of Decision-DNNF representations [START_REF] Lagniez | An Improved Decision-DNNF Compiler[END_REF]. The branching heuristic that has been exploited is the one based on dynamic decomposition (DECOMP) used by default in D4 (see [START_REF] Lagniez | An Improved Decision-DNNF Compiler[END_REF] for details).

We have considered several caching schemes, namely n, b, 2, i, as well as h , the variant of h where indexes are compressed, p, and i . The features characterizing those schemes are summarized in Table 1. "(E)xplicit/(I)mplicit" makes precise whether residual clauses are represented explicitly (by their literals) in the scheme, or implicitly (by their indexes). When "All residual clauses" is activated, every residual clause is stored. When "Not binary" is activated, the binary clauses of Σ are not stored. Finally, when "Not shortened" is activated, the binary clauses of Σ and the clauses of Σ that have not been shortened are not stored. The hash function used in the implementation of the cache is MurMurHash2 (see https://en.wikipedia.org/wiki/MurmurHash).

We have also considered several cache cleaning strategies: no cache cleaning, the strategy used by Cachet, the one used by sharpSAT, and our own strategy.

The parameters used in the strategy implemented in Cachet and the ones used by sharpSAT were set to their default values. tc was set to 2 18 and rm to 1 2 . For each combination caching scheme/cache cleaning strategy and each benchmark, the performance of D4 has been assessed by measuring the model counting time, and the memory consumed by D4.

Results. Table 2 makes precise for each combination caching scheme / cache cleaning strategy, some empirical data of the form x(y) where x is the number of instances solved (out of 225) and y the number of memory-out that occurred. The leftmost column (n) corresponds to the cases when no caching takes place. The last three columns (b, 2, i) correspond to schemes for which residual clauses are represented by their literals (the difference between the three schemes lying in the sets of clauses explicitly represented, which by construction are never increasing w.r.t. ⊆ when switching from b to 2, and from 2 to i). The three remaining columns (h , p, i ) correspond respectively to b, 2, i in term of the clauses which are represented, but for any of those three schemes, clauses are represented implicitly by their indexes. In Table 2, the largest numbers of instances solved for each caching scheme are boldfaced, and the largest numbers of instances solved for each cache cleaning strategy are reported in lilac cells. One can observe that the lighter codes obtained by considering i (when compared to b and 2) permit to solve more instances. Indeed, whatever the cache cleaning strategy used, the caching scheme i dominates each other scheme as to the numbers of instances solved. The other way around, our new cache cleaning strategy appears as the best cleaning strategy most of the time, whatever the caching scheme under consideration. The single exception concerns the caching scheme b (for this scheme, the cache cleaning strategy used by sharpSAT led to solve two additional instances). The underlying principle (trying to learn what are the most promising entries) looks quite useful in this respect. Especially, it can be observed that our new cache cleaning strategy performs not bad in term of the numbers of memory-outs that are obtained (in particular when it is coupled to i or i ), despite the fact that the amount of available memory is not exploited in this strategy, while cleaning operations are triggered by the number of entries / amount of available memory in Cachet / sharpSAT. Empirically, the best combination turns out to be i together with the new cleaning strategy. Interestingly enough, this combination corresponds in our experiments to the virtual best solver (VBS): every instance solved by another combination has been solved as well by i and the new cleaning strategy.

In order to better figure out the savings (in terms of time and memory) which are feasible thanks to the various caching schemes and cleaning strategies considered in the paper, we have pairwise compared all the 28 combinations (7 caching schemes, 4 cache cleaning strategies) and drawn all the scatter plots corresponding to those comparisons. A selection of them is presented in the following. 10 In those plots, each dot represents an instance; each coordinate represents either the time (in seconds) needed to solve it or the memory used (in MiB) by D4 (provided that the computation terminated normally).

The scatter plots reported in Figure 1 shows the time/space trade-off achieved when D4 is used as a model counter and the scheme i is used vs. no caching is done (the n scheme). In both cases, no cache cleaning has been performed. On the one hand, Figure 1a clearly shows (as expected) that taking advantage of a cache usually leads to huge improvements in terms of solving times. On the other hand, Figure 1b shows that these benefits in terms of computation times are possible only if a sufficient amount of memory is available. The scatter plots reported in Figure 2 are useful to compare in term of computation time / memory consumption the "explicit" caching schemes (b, 2, i) to the corresponding "implicit" caching schemes (h , p, i , respectively). Again, no cache cleaning took place. As expected, each "explicit" caching scheme proves better than the corresponding "implicit" caching scheme as to computation times, provided that all clauses are not stored (indeed, their numbers have an impact not only on the memory used but also on the times needed to perform the cache 10 Due to space limitations, one cannot report all of them in the paper; the full set of plots can be downloaded on https://miniurl.be/r-31qh. operations), but it proves often worse in term of amount of memory used (just compare the numbers of dots above / below the diagonal).

The scatter plots reported in Figure 3 enable a pairwise comparison in term of computation times of the best "explicit" scheme i with the two other "explicit" caching schemes (b, 2) on the one hand, and of the best "implicit" scheme i with the two other "implicit" caching schemes (h , p) on the other hand. Again, no cache cleaning took place. These plots show that i (resp. i ) performs better than b, 2 (resp. h , p). This can be explained by the fact that they are associated with smaller codes (less clauses are stored in the cache). Finally, the scatter plots reported in Figure 4 enables to compare the computation times of D4 when the best cache cleaning strategy (our own strategy) has been used, with those obtained by D4 when the cleaning strategy of Cachet or of sharpSAT was used instead. Here, the caching scheme used was the best performer (i). Clearly enough, as Table 2 already pointed it out, using the new cache cleaning strategy leads to solve more instances.

Conclusion

We have presented an improved caching scheme that can be exploited for model counting or the Decision-DNNF compilation of CNF formulae Σ. We proved the correctness of this scheme i and of the corresponding scheme i obtained by considering implicit representations of clauses by indexes. We have also presented an improved cache cleaning strategy, which elaborates on the one used in sharpSAT, and takes account for the ages, activities, and on the proportion of entries of the same size that led to positive hits in order to decide which entries should be kept and which ones should be flushed. We have reported the results of an empirical evaluation showing the i scheme and the new cleaning strategy as useful for model counting when compared to caching schemes and cleaning strategies used in state-of-the-art #sat solvers. In light of our experiments, i associated with the new caching strategy is the best combination among those which have been considered. This combination corresponds empirically to the virtual best solver. The performance of i compared to the one of p, as illustrated by the empirical results that have been obtained and are reported above, is one of the factors explaining why D4 challenges Dsharp, the Decision-DNNF compiler associated with sharpSAT (see [START_REF] Lagniez | An Improved Decision-DNNF Compiler[END_REF] for an empirical comparison of D4 and Dsharp). Interestingly, the caching scheme i and the new cleaning strategy are not dedicated to D4 but can be used as well in other #sat solvers and compilers which are based on other branching rules. Especially, it can be noted that the implementation of D4 as presented in [START_REF] Lagniez | An Improved Decision-DNNF Compiler[END_REF] does not exploit any cache cleaning strategy, hence our new cleaning strategy can be leveraged to give rise to an improved release of D4.

As a perspective for further research, we plan to define and evaluate "mixed" caching schemes, i.e., schemes for which both explicit and implicit representations of clauses can be considered. The choice for an explicit vs. implicit representation of a clause may depend on the size of the clause under consideration and may change during search (depending on the number of hits for the corresponding entry).

Fig. 1 :

 1 Fig.1: Computation times and memory consumptions of D4 equipped with the caching scheme i with the computation times of D4 when no caching is done. No cache cleaning.

Fig. 2 :

 2 Fig. 2: Comparing the computation times and memory consumptions of D4 equipped with "explicit" caching schemes vs. "implicit" caching schemes. No cache cleaning.

Fig. 3 :

 3 Fig.3: Comparing the computation times of D4 equipped with i (resp. i ) with those obtained when using other "explicit" (resp. "implicit") caching schemes. No cache cleaning.

Fig. 4 :

 4 Fig.4: Comparing the computation times of D4 equipped with our new cleaning strategy with those obtained when using the cleaning strategy of Cachet or the one of sharpSAT. The cache scheme used is i.

Table 2 :

 2 Number of instances solved by D4 and number of memory-out reached for several combinations of caching scheme / cache cleaning strategy.

According to[START_REF] Thurley | sharpSAT -counting models with advanced component caching and implicit BCP[END_REF], it is the one used in Cachet ([START_REF] Sang | Combining component caching and clause learning for effective model counting[END_REF] do not make it precise).

www.cs.ubc.ca/∼hoos/SATLIB/index-ubc.html


Dominique Roux

Marie Schill

Waste prevention in practice: Confronting public discourses about reusing, reducing, and recycling with consumers' perceptions of wasting material possessions

Keywords: waste prevention, material possessions, public policy discourses Track: Consumer Behavior

Waste prevention in practice:

Confronting public discourses about reusing, reducing, and recycling with consumers' perceptions of wasting material possessions

Introduction

Waste prevention addresses the crucial issue of reducing the amount of waste generated at source and implies that measures are taken before a substance, material or product becomes waste. Waste prevention is thus intended to minimize end-of-life management that results in collecting, treating and recycling materials (European Commission, 2012). Broadly speaking, waste prevention encompasses various actions pertaining to the extraction, production, transport, distribution, purchase, use and re-use of products. Yet because the European Commission defines waste as "any substance or object which the holder discards or intends or is required to discard" (EU Waste Framework Directive, 2008, p.9), public policy discourses tend to target end-users by enticing them to both minimize their consumption and optimize the use and life span of objects (ADEME, 2016). Such emphasis put on the consumer is evidenced by [START_REF] Corvellec | A performative definition of waste prevention[END_REF] who shows that 90% of the 51 initiatives that have been singled out to participate in Swedish waste prevention competitions relate to consumption.

However, how consumers tackle the expectations of exemplarity that are placed on them by public authorities remains poorly understood.

In this study, we examine whether household mundane practices align with waste prevention discourses and how consumers conceive of wasting objects. More precisely, we try to uncover how individuals cope with three objectives that animate waste prevention: greater awareness about the need to prevent waste, increased material efficiency of products that they possess, and broader commitments in sustainable consumption [START_REF] Corvellec | A performative definition of waste prevention[END_REF]. In order to address our objectives, we explore how mundane objects that have been bought, received as gifts or inherited are dealt with over time. In particular, we focus on when and why objects are thrown away, resold or given, but also kept in cupboards, attics and garages because they are considered useless and disappointing or end up broken. We also explore if and how individuals refer to waste in such situations.

Conceptual background: From food waste to solid waste

The issue of household waste has been extensively examined in the context of food waste where it is associated with losses that occur during the retail or food consumption phases [START_REF] Porpino | Household food waste behavior: avenues for future research[END_REF][START_REF] Quested | Household Food and Drink Waste in the UK -Wrap Report[END_REF]. Various drivers of food waste have also been identified as well as motivations to minimize its impacts [START_REF] Graham-Rowe | Identifying motivations and barriers to minimising household food waste[END_REF][START_REF] Quested | Spaghetti soup: The complex world of food waste behaviours[END_REF]. However, behavioral, experimental and declarative approaches that are used in these studies fail to account for the complexity of the material, normative and social elements that shape a range of practices involved in food waste such as planning, shopping routines, buying (and overbuying), storing, cooking, processing food at home and gardening [START_REF] Ganglbauer | Negotiating food waste: Using a practice lens to inform design[END_REF]. From a different angle, practice theory offers a clearer understanding of how food becomes wasted. It shows that social norms, education standards, material infrastructures, household organization, inconstancies, unexpected situations as well as public discourses on environmental responsibility and food safety may conflict with each other, thus creating food losses [START_REF] Evans | Beyond the throwaway society: Ordinary domestic practice and a sociological approach to household food waste[END_REF][START_REF] Hebrok | Household food waste: Drivers and potential intervention points for design-An extensive review[END_REF][START_REF] Watson | Food, waste and safety: negotiating conflicting social anxieties into the practices of domestic provisioning[END_REF],

In contrast with food, objects are not affected by the problem of perishability deriving from a limited shelf life. Not do they seem to be subjected to the same moral condemnations that surround food waste [START_REF] Bolton | When less is more: Consumer aversion to unused utility[END_REF]. As a result, how material possessions may be conceived as wasted remains poorly understood. If evoked, this may result from technical, psychological or planned obsolescence that refers to the voluntary or involuntary loss of competitiveness, usefulness and value of objects because better and cheaper alternatives are introduced into the marketplace or because people themselves develop new preferences, requirements and tastes [START_REF] Cooper | Inadequate life? Evidence of consumer attitudes to product obsolescence[END_REF][START_REF] Guiltinan | Creative destruction and destructive creations: environmental ethics and planned obsolescence[END_REF][START_REF] Levinthal | Durable goods and product obsolescence[END_REF].

Obsolescence contributes to waste to the extent that objects that might still be used, for example by reselling, bartering, giving, renting and lending them, results in replacing them prior to their end-of-life.

From the opposite perspective, [START_REF] Bolton | When less is more: Consumer aversion to unused utility[END_REF] examine "consumer aversion to unused utility" as a psychological mechanism that is likely to minimize waste. Through a series of experiments, they demonstrate that people, when given a choice, try to avoid waste arising from unused utility. However, both a declarative methodology and a non-naturalistic approach obscure the actual circumstances in which objects enter the home in practice. Hence, in order to examine how consumers conceive of wasting objects and cope with public authorities' discourses, we adopt a qualitative and ethnographic method. Following previous approaches to food waste that draw on practice theory [START_REF] Evans | Beyond the throwaway society: Ordinary domestic practice and a sociological approach to household food waste[END_REF][START_REF] Ganglbauer | Negotiating food waste: Using a practice lens to inform design[END_REF][START_REF] Watson | Food, waste and safety: negotiating conflicting social anxieties into the practices of domestic provisioning[END_REF], we explore how objects are integrated in and disintegrated from mundane practices that prove out to be in tension with public discourses about waste prevention. We next detail our qualitative study that trace objects in the home and examine when, how and why people feel these are "wasted."

Context and methods

This research takes place in France where the national environment and energy management agency (ADEME) implements waste reduction campaigns that fully resonate with similar initiatives in developing countries [START_REF] Guerrero | Solid waste management challenges for cities in developing countries[END_REF][START_REF] Corvellec | A performative definition of waste prevention[END_REF]. ADEME (2016) seeks to raise awareness among consumers by pointing that waste has increased dramatically in recent years and that a 10% decrease in household waste per capita should be achieved by 2020. At the same time, adopting a circular economy approach, it promotes various solutions that should avoid destroying objects such as reselling, donating and reusing them. However, because ADEME aligns with the EU's definition of waste that semantically equates unwanted objects with rubbish (European Commission -Waste Framework Directive, 2008), its communication undermines its virtuous enticements.

The website that ADEME has createdreduisonsnosdechets.fr, meaning "let's reduce our waste"suggests that things that people want to get rid of are junk instead of "objects" or "products" that may be reused. Hence, while prompting people to make objects recirculate, public discourses assimilate useless objects to waste and hence normalize their destruction through curbside and bulky waste collections [START_REF] Shultz | In this Issue[END_REF].

To gain a comprehensive approach of how people conceive of waste, twenty-eight objectfocused interviews [START_REF] Miller | The Comfort of Things[END_REF] were conducted during a two-year qualitative study in different rooms and storage places of our 25 participants' houses. As a starting point, interviews began with grand tour questions about their favorite activities, e.g., clothing, books, childcare material, trinkets, dishes, CDs, DVDs, appliances, etc., and objects variously bought, received as gifts or inherited. We sought to understand what categories of objects and how many were frequently acquired and/or received, and where these were located. When duplicate or multiple purchases were found, we discussed the reasons for buying a new product and what the former had (was meant to) become. Places such as cupboards, garages, attics and basements were also explored to examine which objects are stored and why. Unless participants themselves introduced the topic of waste, there was no direct mention of it during the interviews. Of the 27 conversations that resulted, 18 were audio-recorded and 9 were conducted in video format. While the former aimed at gaining a general understanding of participants' consumption habits, purchasing practices, multiple possessions of objects, way of using products, reasons for stopping using them, and perceptions of waste in the house, the latter was more focused on particular practices and related spaces such as the kitchen as a place for cooking, the garage for DIY activities, the bathroom for dressing and making-up, or the living room for reading, listening to music, watching films, storing books, CDs, etc. We re-interviewed 3 participants to gain a broader knowledge of their consumption practices over time and took special care of informants' feelings about their practices and what they were themselves spontaneously considering as wasteful. We also explored in depth when their awareness of waste had begun, if this had led to any behavioral change and, if so, which one.

Profiles were selected gradually by introducing variance in practices but also in age ( 17to 82 years old, 38 on average), gender (10 men and 15 women), family situation (9 singles, 4 couples, 12 family), occupational status (4 students, 14 employees, 5 retired, 2 unemployed), geographical location (10 in the Paris region and 15 in various provinces), and socio-cultural origin (7 had their families outside France). Interviews and illustrations resulted in 411 singlespaced pages of transcripts and approximately 6 hours of video footage. They were then coded and analyzed through the theoretical grid of public policy discourses, i.e., awareness and representations of waste, practices that support or impede material efficiency and ways of conceiving sustainable consumption.

Waste prevention in practices

Our data first show that waste prevention is associated by our participants with avoiding destructing and non-using objects. However, except for unwanted products such as gifts and heirlooms that have been involuntarily received, acquiring them is less questioned as the primary trigger of waste. Second, participants allude to the difficulties optimizing the use and material efficiency of objects and they also elaborate on the lack of appropriate channels to recirculate objects. Third, while they show little engagement in reducing their levels of consumption as well as in lending or swapping their goods with others, they similarly often fail to repair products. As a result, our findings show that objects stagnate in the home, thus accounting for the hidden part of waste that is not collected nor reused or recycled.

Raising awareness of waste

Waste prevention initiatives first and foremost focus on "raising awareness that waste is a problem" (Corvellec, 2016, p.7). Our results show that participants are fully aware of wasting objects when these are destroyed. While they mostly refer to the end-of-life state of objects as a natural and valid reason to get rid of them, they however consider destroying them as the core cause of waste. In addition, participants refer to non-using objects as a second ground for waste. For example, Léa, a 26-year-old young mother, purchased a juice extractor that she does not use any more. Because she was pregnant, Léa deemed necessary to eat healthy but she has now given up this practice, not only because she delivered her baby but also because she was "a little disappointed with the quality of the product." However, she feels guilty for having bought an expensive kitchen appliance that she has used four or five months only, "on a whim." Disappointment with a purchase is also another reason to stop using products as Gisèle (F, 82, retired nurse) also illustrates. Because of mobility problems, she had to turn to Internet to purchase clothes, the poor quality of which leads her to donate those clothes without even having worn them. Third, people also refer to waste when they receive objects that they do not choose and that do not please them. This situation is particularly challenging, socially speaking, when it pertains to gifts. Commercial gifts such as goody bags, paper bags, small tokens, frequently end up in the trash and they are subjected to limited deliberation when they do not match the recipient's expectations or needs. Private "failed gifts" [START_REF] Roster | Moments of truth in gift exchanges: A critical incident analysis of communication indicators used to detect gift failure[END_REF]) also represent troublesome and ambiguous situations as destroying them would be felt as a profanity. Caroline (26, assistant professor) explains: "I got rid of all the things that friends gave me for my house warming party. I told people: I do not need anything. I hate trinkets!! But some still brought something, a photo frame, eggcups...I managed to pass them on to family members." Caroline's comment highlights that she is uncomfortable with both keeping things that she does not like in her house and sacrificing the use that others could make of these objects. Hence, waste prevention encompasses avoiding both destroying unwanted objects and making little use of them. Yet, the crucial point about awareness of waste relates to the reasons why objects enter the house, an issue that is examined below.

Promoting sustainable consumption

Sustainable consumption requires changing people's consumption habits, for example by forsaking the acquisition of products in favor of borrowing them from acquaintances or through renting/lending platforms. Yet, renting objects may be difficult as it implies relinquish what is considered essential, even for a short period of time. As for Léa, Maxime provides a basic example of such situation: "Imagine that you are at your friend's home and you see his blender: "Oh, that's cool! It would be nice if you could lend me your blender. I would be happy to make me a smoothie one of these days but I do not know when." The risk is that the person answers: "Yeah, sure! But I too would like to make me a smoothie one day but I do not know when." It might happen that we will want to make smoothies the same day!" Because objects are not only material supports but also magical tools that (re)activate desire, nurture the power to act and foster the ability to create (Sartre, 1943), the objective of making full use of products by lending or swapping them is practically unreachable for a number of items of everyday usage.

Informants may also be quite critical towards poor quality products that they buy involuntarily. Gisèle above says she is "disgusted" by the clothes that she buys through mail order catalogues and hence donates or even throws away. Likewise, participants refer to electronic objects that are not intended to last long because of so-called planned obsolescence.

For instance, Gaël (M, 44, cleaning person) indicates that "repair shops have difficulties to find replacing pieces because manufacturers do everything to encourage consumption, not sustainability." To avoid waste, some promotes more sustainability in participating, like Claire, in "a Facebook group that gives objects to people. Many are interested in acquiring things, so objects can really be useful for others. They can be reused even if they are old and a bit damaged."

While most participants emphasize that objects must be really unusable and not repairable to be thrown away, few of them make a real diagnosis of product failures. When in doubt that the object is really out of order, most of our participants keep objects that are broken down, like Maxime (M, 25, self-employed) who acknowledges that: "this blender, I got it from my mum's friend but it never worked, and hence I put it there, saying that I had to throw it away... but it's still there! I should have it repaired but I'm lazy, I think…" As a result, objects stagnate in closets, cupboards and remote places of the home like attics and garages when people ignore what to do with unusable products or how to fix them. Some participants like Philippe (M, 63, CRM executive) also refrain from throwing technically obsolete products to the binsuch as audio and video cassettesbecause "these are not properly recycled in France at the moment." Similarly, he explains that while he likes to put metal items on the sidewalk on bulky items collection days "because it makes poor people happy to retrieve recoverable materials," he avoids depositing whole electronic appliances "that they will destroy and hammer, putting plastic parts anywhere." Consequently, he prefers to keep useless objects than to imagine these ending in landfills. In short, while public discourses promote sustainability through reuse or repair [START_REF] Corvellec | A performative definition of waste prevention[END_REF], this seems not fully achieved by many consumers. Participants are torn between their awareness of waste and appropriate solutions to properly recycle or to make objects recirculate.

Practical difficulties to optimize objects' use

Corvellec (2016) shows that "increasing material efficiency" is one of the three main types of actions that are promoted by waste prevention initiatives. However, practical life situations raise various issues that render this objective inapplicable. As shown above, disappointment with products may lead to stop using them without knowing who could be interested in their reuse. This is all the more so when objects are costly because their poor performance prevents their holders from donating or reselling them as for Léa's expensive juice extractor. Also, ordinary situations may result in wasting products that are bought too impulsively. Jean (M, 62, doctor) for example acknowledges that when he needs materials to fix or tinker something in the house, "he wants the job to be done quickly so he runs to the store and buys. Whereas if he had taken five minutes and look in his toolbox, he would have realized that he had everything that he needed." Jean's comment illustrates that acquiring products without a full awareness of what he already possesses results in a failure in the optimization of the use of previously purchased products.

Differently, not fully using products may also result from duplicate purchases. This happens when participants fear a product failure as for Elisabeth and Patricia who both have a strong interest in cooking and respectively hold two fridges and two kitchen scales, because they "desperately need these materials in case of defects or breakdown." Elisabeth in particular has been affected by the loss all the food that was stored in her fridge that broke down few years ago. Likewise, Patricia, a 58-year old talented pastry cook, cannot imagine lacking a kitchen scale for her favorite practice. These cases provide evidence that matching production and use is not achieved, although public discourses promote such principle as an abstract motto [START_REF] Corvellec | A performative definition of waste prevention[END_REF].

Conclusions

Our research focuses on waste prevention through consumers' mundane practices. Based on a qualitative methodology involving 25 consumers, we show that these account for waste prevention and avoid destroying and throwing things away. However, at the same time findings also highlight that they express difficulties in optimizing the use of objects, e.g., recirculating, swapping, lending or repairing what they possess. Furthermore, our research bring to light that they barely conceive of waste as primarily deriving from the acquisition of objects, which may be done impulsively, for a temporary purpose or result from failed gifts.

In addition, how participants relate to waste appears closely associated with objects' trajectories in their daily activities [START_REF] Appadurai | The social life of things[END_REF][START_REF] Epp | The storied life of singularized objects: Forces of agency and network transformation[END_REF], e.g., dressing, wearing make-up, watching movies, having a child, cooking, that all require and entail consumption at particular "moments" (Warde, 2005, p. 137). Waste prevention is thus strongly dependent on the way objects are integrated in and (dis)integrated from practices.

Once objects are integrated in a practice, they may contribute to the waste phenomenon if they are not used or if they are cleared because they stop bringing utility and pleasure. Hence, waste occurs when objects are disintegrated from practices and/or spaces whatever public policy discourses may normatively urge consumers to do. In addition, the lack of naturalized infrastructures to make objects recirculate between people contradicts the so-called public objectives to foster sustainable consumption and circular economy. In other words, public policies encourage a "double waste disposal paradox" [START_REF] Shultz | In this Issue[END_REF] whereby infrastructures dedicated to garbage collection fail to address acquisition as the primary mechanisms of waste generation and waste reduction.


Elvin Muñoz

Johan Quispe

Pierre Lambert
email: pierre.lambert@ulb.ac.

Aude Bolopion
email: aude.bolopion@femto-st.fr

Ronald Terrazas
email: rterraza@ulb.ac.be

Emir Stéphane Régnier
email: stephane.regnier@upmc.fr

Emir Vela
email: evela@utec.edu.pe

Ronald Terrazas Bio-

Optimizing the speed of single infrared-laser-induced thermocapillary flows micromanipulation by using design of experiments

Keywords: Infrared Laser, Thermocapillary flows, Design of Experiments (DoE), Micromanipulation

Optimizing the Speed of Single Infrared-Laser-Induced Thermocapillary Flows Micromanipulation by using Design of Experiments

Introduction

Non contact actuation is now widely used to manipulate objects at the micrometer scale [START_REF] Gauthier | Intracorporeal Robotics. From Milliscale towards Nanoscale[END_REF]. Compared to classical approaches that use mainly tips, grippers or pipettes [START_REF] Xie | Atomic Force Microscopy Based Nanorobotics[END_REF][START_REF] Bøggild | Micro and Nano Techniques for the Handling of Biological Samples[END_REF] it is based on force fields produced by remote sources. These remotely actuated systems can be classified into three categories depending on how the force field is used to interact with the object: (i) the force fields are used to control remotely actuated tools that interact with the object, (ii) the force fields directly control the objects or (iii) the force fields are used to modify the environment in which the object is placed.

A few examples of each category are reviewed below.

Remotely controlled microtools have been developed to handle micrometer size objects. In [START_REF] Ongaro | [END_REF] closed-loop control of untethered grippers driven by magnetic fields and automated pick-and-place of biological material on porcine tissue in an unstructured environment are demonstrated. Magnetic fields are also used in [START_REF] Pieters | Microrobots for Active Object Manipulation[END_REF] to control microrobots fabricated from polymer (SU-8) with internal soft-magnetic posts having a maximum dimension of 50 × 200 × 600 µm 3 . Indirect pushing of biological cells using an optically trapped tool is demonstrated in [START_REF] Thakur | [END_REF] and [7]. The use of tools to push the cells minimizes their exposure to the laser beam and the related generated heat.

The second category of remotely actuated systems consists in using the remote force fields to directly control the object of interest, without intermediate manipulator. Electric fields are widely used for that purpose, especially for in vitro cell analysis. As reviewed in [8] and [9] electric fields can induce electrophoresis (movement of charged particles in an electric field), or dielectrophoresis (motion of polarizable particles in a time variant electric field). Electric fields can also modify the cell structure via electroporation (formation of aqueous pores in the cell membrane) or electrofusion (fusion of cells). Closed loop trajectory control of artificial objects is demonstrated using dielectrophoresis [START_REF] Kharboutly | IEEE International Conference on Robotics and Automation[END_REF][START_REF] Zemanek | IEEE/ASME International Conference on Advanced Intelligent Mechatronics[END_REF], as well as controlled orientation [START_REF] Jiang | [END_REF]. In addition to electrical fields, magnetic ones can also be used for micromanipulation. Important forces can be applied using electromagnetic coils. However the object to be manipulated must have magnetic properties [13]. Optical tweezers are demonstrated in [14] and [15]. This technique shows promising results for the independent control of several objects simultaneously. It is commonly used to manipulate biological cells [16], or to analyze them. In [17] the authors use optical tweezers to get information about the mechanisms of chemoattractant gradient induction of cell migration. However it proves to be difficult to manipulate objects larger than several tens of micrometers using optical tweezers. Other techniques, such as acoustic waves can be considered to manoeuvre cells as detailed in [18].

In the third category, manipulation via actuated flows is another option. In this type of manipulation, fluid motion generated through different methods (i.e. electroosmosis, electrohydrodynamics, thermocapillary pumping [19]) is used to displace the desired object. Among the different mechanisms to generate flows, surface tension gradients are very promising because the surface effects are significant at the micro-scale. Flows generated by surface tension gradients are named as Marangoni convection flows. However, if the surface tension gradient is generated by a temperature gradient parallel to the surface, these flows are known as thermocapillary convection flows [20]. Moreover, there are some variations in the manner of heating and as a consequence, it produces different types of instabilities and patterns. Nevertheless, if a laser is used as heat source to produce the thermocapillary flows, toroidal convection cells patterns are very likely to occur. Ther-mocapillary flows have been already successfully used for micro-object manipulation. In [21], the authors used thermocapillary convection flows generated around a bubble heated by a light pattern which was confined on a closed chamber. The generated flow repelled the object from the bubble if it was floating and attracted the object if it was sunken. By using this technique, different sized particles were manipulated such as 60 µmradius glass beads and SU-8 triangular-shaped components of 360 × 185 × 100 µm 3 . In [22] and [23], the authors generated the thermocapillary convection flows in a slightly different manner. A laser-light absorbent substrate is heated strongly enough to, first, create a bubble microrobot in the target illuminated position and, then, generate flows around those bubbles. In [START_REF] Vela | Non-contact microscale manipulation using laser-induced convection flows[END_REF], the bottom of a water layer was heated using a laser to generate Marangoni convection flows. Using this principle, glass beads with diameters 31, 62, 92 µm were displaced with speeds up to 2, 3, 4 mm/s respectively inside a 450 µm water layer. Recently, [START_REF] Quispe | [END_REF][START_REF] Quispe | Manipulation, Automation and Robotics at Small Scales (MARSS), International Conference on[END_REF] study laser-induced thermocapillary convection flows. The authors analyse the convection cell growth to manipulate micro-objects accurately [START_REF] Quispe | [END_REF]. They prove that it is possible to separate particles by controlling the motion of the desired particle with the convection cell without altering the position of other objects [START_REF] Quispe | Manipulation, Automation and Robotics at Small Scales (MARSS), International Conference on[END_REF]. However, none of these works study in detail the influence of the control parameters on the particle's position and speed. So that thermocapillary flows can be used for controlled micromanipulation, this issue is of utmost importance.

This paper provides a systematic analysis of the most influential parameters namely: the laser exposure time, the distance between the laser and the manipulated particles, the particle's diameter and the water layer thickness. Design of Experiments (DoE) method is conducted to analyze the impact on the particle's speed. This work paves the way toward fully controlled micromanipulation via thermocapillary flows.

Thermocapillary flows based micromanipulation

Thermocapillary flows physical principle

Marangoni convection flow is a phenomenon which is generated by a surface tension gradient on a fluid-fluid interface. The surface tension σ is a function of the pressure P and the temperature T on the interface as it is expressed in the following equation:

dσ = ∂σ dP dP + ∂σ ∂T dT (1)
Fig. 1 Recirculating flows can move sedimented objects toward the Infra-Red Laser Beam (IRLB). The velocity profile shows a geometric relation between the Upper Subsurface Flows (USF) and the Lower Subsurface Flows (LSF) (USF/LSF = 1/2) [START_REF] Costa | [END_REF]. This relation is kept even if there is a deformation of the interface caused by the relative viscosity on the interface (water-air in our case) [28,29]. (i) and (ii) are respectively the contribution of the dragging and the rolling movements to the particle's motion.

and if any of these physical parameters is altered, the surface tension will change. Moreover, if a fluid-fluid interface is only heated (dσ = ∂σ ∂T dT ) , it is more suitable to name this phenomenon as thermocapillary convection. Furthermore, if a laser is used in order to heat the interface we are referring to laser-induced thermocapillary flows. As it was mentioned, this phenomenon is initially produced on the interface. Due to the unbalanced shear stress produced on it, the fluid on the interface is pulled from the hot regions (low surface tension) to regions with higher values of surface tension. If we consider the heat source as a point, the phenomenon will become axisymmetric from this reference point. As a consequence of the mass conservation equation on the control volume, recirculation flows are generated and sedimented objects can be moved toward the laser beam center (see Figure 1). However, until this moment it is not established whether the particle is either dragged, rotated or both. A velocity model for thermocapillary flows was shown in Da Costa's work [START_REF] Costa | [END_REF]. It derives the velocity field from Levich's work [30]. Additionally, an interesting result appears in this work: a geometric relation between the Upper Subsurface Flows (USF) and the Lower Subsurface Flows (LSF) was found. LSF appears from z = 0 to z = 2H 3 and USF appears from z = 2H 3 to z = H. However, there is a local maximum for the velocity in z = H 3 and it can produce different effects on the particle's kinetics depending on its size and z-position.

Pulsed based manipulation strategy

In previous works [START_REF] Quispe | [END_REF][START_REF] Quispe | Manipulation, Automation and Robotics at Small Scales (MARSS), International Conference on[END_REF], the main outcome was the separation of particles. This task was achieved by characterizing the movement of a certain sedimented particle immersed into the fluid and by controlling the growth of the convection cell. These concepts brought into light a new micro manipulation technique. Selective manipulation of objects can also be performed by controlling the transient regime of single-IRLB-generated thermocapillary flows thus overcoming the toroidal shape of the flows; it means particles can be separated out of a group. In [31], it was shown the existence of stationary convection cells. However, at the micro-scale due to the prevalence of the surface forces, these convection cells, which are recirculating flows, undergo a transient regime. This transitory recirculating flow can be ex-ploited to move particles in a fast and accurate manner. These transitory convection cells are generated by heating the interface with an Infrared Laser Beam (IRLB) for a brief duration (IRLB pulses). IRLB pulses are thus a promising solution to move micro-objects by thermocapillary flows based micromanipulation. This strategy will be used in the rest of this paper.

To perform an efficient manipulation based on IRLB pulses the duration of the laser pulse should be tuned. The distance between the IRLB and the particle of interest is also an important parameter. When the convection cell is evolving the kinetics varies with respect to the position inside the convection cell. The force exerted by the flows on the particle is going to change rapidly. There is thus an optimal laser-particle distance in order to drag the particle strongly enough for a fixed pulse time.

Experimental Setup

The experimental setup is shown in Figure 2. The main components of the setup are labeled in the picture. The infrared laser (λ = 1470 nm, Laserglow) is used as the heat source. The output beam from the laser is reflected by two silver-coated mirrors (95% of reflectance on the IR range) mounted on a galvanometer scanner (Thorlabs GVS002). These mirrors, which are each attached to a high-precision and stable servo motors can be rotated from -12.5 • to 12.5 • from their neutral state. The reflected beam takes different output angles which makes the beam hit the Petri-dish in different XY positions. This beam is then magnify (1.5×) by a Keplerian arrange of lenses. The magnified beam is reflected by a dichroic mirror and directed toward a microscope objective (4×) which focalizes the laser at the bottom of the Petri-dish. This focalized laser beam heats the film of water inside the Petri-dish which generates thermocapillary convection flows. These flows are used in this work for the displacement of immersed particles. The dichroic mirror reflects all the infrared laser radiation but it lets the visible light pass through it, so a high speed camera (DALSA Genie HM1400) underneath can record images of what is occurring inside the film of water in the Petri-dish. The ON and OFF switching of the infrared laser to produce the pulses as well as the an- gular position of the mirrors of the galvanometer scanner are electronically controlled with a data acquisition card (NIDAQ-USB 6211).

Influence of the geometrical and control parameters on the manipulation speed

The manipulation strategy has been defined in Sec. 2.2. It consists in heating a water layer of thickness H using IRLB pulses. The laser is switched on during a time τ . It heats the water at a distance L from a particle of diameter D (see Figure 3). The manipulated particles were acid-washed glass beads ranging from 50 up to 150 microns, from Sigma-Aldrich. This work aims to find the optimal values of these parameters in order to achieve the shortest period of time for a particle to reach a desired position.

The influence of these parameters on the particle's speed is shown experimentally in Figure 4. This figure presents the particle's speed evolution for three different sets of parameters. The saw-shaped curve in each graphics is due to the pulse technique used in this work. Furthermore, it is clearly noticeable that the maximum speed reached in each case varies from one set of parameters to another. From these experiments it is hard to say which parameter influence the most the velocity of the particle. To do so a design of experiment is proposed in the next section.

3 Design of Experiments (DoE)

Brief Introduction

The design of experiments, or DoE for short, is an important tool to measure how the variations of some so-called factors affect the output of a process also called response [START_REF] Montgomery | Design and Analysis of Experiments[END_REF]. The values of these factors are varied systematically in a certain number of levels and the response for each combination is measured. Analyzing these responses makes possible to determine which factor impacts the most. Moreover a local linearapproximation, or a higher order approximation if required, can be done, giving a mathematical formula of the evolution of the response of the system with respect to the variation of the factors valid within the analyzed range which can served for future applications. Thus, in this work, it was proposed to use this method to analyze the contribution of each factor to the particle's speed. Specifically, a two-level full factorial design is performed.

Two-level full factorial design

A full factorial design means that all the combinations of all the levels for each factor are analyzed. More specifically, a two-level full factorial design involves just 2 levels: a minimum level and a maximum one for each factor. So if k represents the number of factors involved in the process then the number of runs would be 2 k . Plus these runs, some repetitive runs in the central point are added in order to see the lack-of-fit and depending on its significance, the experiments can be redesigned for a higher order approximation.

Since we have 4 factors (H, D, L and τ ), we need 2 4 = 16 runs plus 4 central points runs thus giving a total of 20 runs as shown in Table 1. The levels, minimum and maximum, are given due to the limitations of our system. For the water layer thickness (H), the minimum value that it can take is around 200 µm, since below this value the Petri-dish is not filled homogeneously, while the maximum value is about 300 µm since higher values do not allowed a proper heating of the film of water. In the case of the particles' diameter (D), the minimum value, 50 µm, and the maximum value, 150 µm, were taken as such since they were the most frequent sizes available in our samples. The range for the laser-particle distance (L) was chosen taking into account the size of our workspace (2 mm × 2 mm) and the maximum average particle's diameter (150 µm) found in our samples. Thus the minimum value of L was 225 µm, which is 1.5 times 150 µm, and the maximum value of L was 325 µm, which is ∼ 0.15 times 2 mm. For the pulse duration, the levels were found experimentally by trial and error testing if the particle moves or not for the chosen range of L. The central point for each level is given by adding the extreme values and dividing it by 2. A summary of the values of the levels for each factor is presented in Table 2. Table 1 Experiment table with each run where "-1" represents the minimum value, "0" represents the central value and "+1" represents the maximum value

H D L τ Response -1 -1 -1 -1 R 1 -1 -1 -1 +1 R 2 -1 -1 +1 -1 R 3 -1 -1 +1 +1 R 4 -1 +1 -1 -1 R 5 -1 +1 -1 +1 R 6 -1 +1 +1 -1 R 7 -1 +1 +1 +1 R 8 +1 -1 -1 -1 R 9 +1 -1 -1 +1 R 10 +1 -1 +1 -1 R 11 +1 -1 +1 +1 R 12 +1 +1 -1 -1 R 13 +1 +1 -1 +1 R 14 +1 +1 +1 -1 R 15 +1 +1 +1 +1 R 16 0 0 0 0 R 17 0 0 0 0 R 18 0 0 0 0 R 19 0 0 0 0 R 20

Analyzing the influence of all the parameters

Experiments are conducted for each run given in Table 1. Each run is repeated 3 times to see how repeatable our data are. In order to compare the contribution of each parameter and their interactions to the average speed, the data are standardized using the Z-score method [START_REF] Shirley Dowdy | Statistics for Research[END_REF]. Since we are comparing the influence of parameters with different orders of magnitudes and units of measure such as H [µm], which is in the order of 10 2 , and H * L [µm 2 ], which is in the order of 10 4 , it is impossible to analyze the given data as such. The Z-score method allows to compare their influence by transforming the data set from its original form to a standardized form. This transformation is done by the following equation:

X * = X - X σ (2)
where X * is the standardized data, X is the original data, X is the mean value of the data set and σ is the standard deviation. The standardized values are a measurement of how much each data is away from the mean value, but expressed in terms of sigma, therefore, the order of magnitudes as well as the units of measurements of the data does not matter.

A linear regression is applied to the original data and standardized data using the following model:

Speed = a 0 +a 1 H +a 2 D+a 3 L+a 4 τ +a 5 H * D+a 6 H * L + a 7 H * τ + a 8 D * L + a 9 D * τ + a 10 L * τ (3)
where the coefficients of each term a i are going to be determined by a linear regression.

The standardized coefficients obtained through this method are shown in Figure 5 and a brief summary of the linear regression's analysis is presented in Table 3. As it can be observed in the table, the p-values of some parameters and interactions are much greater than 0.05 which means that they are not contributing at all to the speed response [START_REF] Montgomery | Design and Analysis of Experiments[END_REF]. All the apparent variations on the response by varying these parameters can be considered as pure noise and do not represent a true effect. On the other hand, the parameter H and L and their interactions have p-values smaller than 0.05 which means that they indeed represent a true effect on the response. Moreover, the standardized coefficients (given in Figure 5) show that the major contributors to the speed are exactly the same terms that have the small p-values (< 0.05). The model could thus be simplified as it will be discussed in Sec. 4.2.

From this, it is deduced that neither D nor τ are factors that affect the particle's speed. However the physical explanation of thermocapillary manipulation presented in Sec. 2.1 highlights that there is undoubtedly an influence of the ratio between the particle's diameter and the water layer thickness on the particle's speed. A separate study is thus carried out to find this effect (Sec. 4.3).

Concerning τ , this factor indeed does not affect the particle's speed. For a given L, there is a given threshold time (τ 0 ) for which the particle starts moving [START_REF] Quispe | [END_REF]. For the selection of the levels the values of τ were taken so that the particle moves. In other words, all the values of τ are such that τ = τ 0 + where > 0. Therefore, slight variations of does not contribute at all to the particles' speed [START_REF] Vela | Non-contact microscale manipulation using laser-induced convection flows[END_REF]. According to the previous section H and L are the only factors that affect the particle's speed. Equation (3) can thus be simplified as:

Speed = a 0 + a 1 H + a 2 L + a 3 H * L (4)
where a i are the coefficients to be obtained by the linear regression. The same procedure as previously is carried out leading to the standardized coefficients obtained by linear regression shown in Figure 6. Table 4 shows a summary of the analysis of the linear regression. As it can be observed in the table, the p-values of all the terms in this model are less than 0.05 which means that all of them indeed have a true effect on the response. Moreover, as it can be seen from the impact of each factor in the speed, H has a negative contribution to the speed as well as L which means that in order to increase the speed, both parameters have to be decreased (the water layer thickness should be small, and the laser should heat the water close to the particle). Furthermore, the F-statistic value is greater than 5, and the upper tail probability of the F-distribution corresponding to the value of F-statistic is also much smaller than 0.05, both values indicate that the lack-of-fit is nonsignificant which means that a linear approximation is enough to model the particle's speed within the analyzed range. A 3D representation of the surface speed response is shown in Figure 7 which is plotted using the model: Speed = 2 × 10 4 -64.1 H -55.5 L + 0.2 H * L. It is also shown the experimental data (H, L, Speed) as scatter points. It is observed that these experimental points do not differ pretty much from the surface which means that the linear model is an enough approximation to model the experimental data. As mentioned before, the physical analysis of the manipulation technique underlines the influence of the ratio between the particle's diameter and the water layer thickness on the particles' speed. A specific attention is given to this ratio in this section. To do this, the other two parameters (L and τ ) are fixed at their central values and speed tests are conducted for several ratios D/H. The results are shown in Figure 8. The particle's speed is indeed affected; nevertheless, the variations on the particle's speed are less than 1000 µm/s. This maximum variation is the same order of magnitude than the noise. This is the reason why the influence of the diameter was unnoticed in the model section 4.1 as it was confused with noise. Moreover, Figure 8 indicates that there are 2 peaks that are located approximately at the ratios: 1 3 and 2 3 . The local maximum at those ratios are explained due to the shape of the flows' velocity profile (see Section 2). As it was shown in Figure 1, the ratio between the lower subsurface flows and the thickness of the water layer is 2 3 and due to the parabolic shape of the flows' velocity profile, the inflexion point of the lower subsurface flows occurs at 1 3 of the water layer thickness. Both values correspond to the two peaks found in the graphics. These results are in good agreement with the underlying physical phenomena.

Conclusion

This paper focuses on the determination of the most influential control parameters for thermocapillary pulse based manipulation. From the four parameters identified at first, a systematic analysis involving DoE highlights that just two of them significantly contribute to the particle's speed: the laser particle distance (L) and the water layer thickness (H). The water layer thickness H is indeed the one that is the most influential variable. Within the analyzed range, it was determined that in order to maximize the speed, both parameters have to take their minimum values in the explored range. This means that the water layer thickness should be small, and the laser should be closed to the object. Moreover, the speeds, obtained experimentally, presents a relatively high level of dispersion which is due to the uncertainty in the z-position of the manipulated beads. Even though this might cause a problem in the modeling, the multiple repetitions of the experiments showed that the trend remains. Furthermore, a separate study of whether the ratio D H influence or not on the particle's speed was done. The results showed that indeed, there is a dependency of the speed with the ratio D H and it reveals the existence of two peaks for which the speed is locally maximized. This work proposes a mathematical approximation of the velocity of the particle using DoE. This model is a first step toward future control strategies for pulse based thermocapillary manipulation.

Fig. 3

 3 Fig.3Parameters involved in the manipulation strategy. H: water layer thickness, D: particle's diameter, L: laser-particle distance, τ : pulse duration.

Fig. 4

 4 Fig.4Each curve represents the evolution of the particle's speed during the manipulation for different combination of water layer thickness (H), particle's diameter (D), laserparticle distance (L), pulse duration (τ ).

Fig. 2

 2 Fig. 2 Experimental setup presenting the main optical and electronic components. (a) Front view. (b) Top view. (c) Image acquired by the camera.

Fig. 5

 5 Fig. 5 Standardized coefficients obtained from the linear regression presented as bars. Model: Speed = a 0 +a 1 H +a 2 D + a 3 L + a 4 τ + a 5 H * D + a 6 H * L + a 7 H * τ + a 8 D * L + a 9 D * τ + a 10 L * τ . At this step all the interactions are considered.

Fig. 6

 6 Fig. 6 Standardized coefficients obtained from the linear regression presented as bars. Model: Speed = a 0 + a 1 H + a 2 L + a 3 H * L. Just H, L and the their interaction are consider in this model.

Fig. 7

 7 Fig. 7 Surface Speed Response along with the experimental data. Speed = 2 × 10 4 -64.1 H -55.5 L + 0.2 H * L.

Fig. 8

 8 Fig.8Variation of the particle's speed according to the ratio of the particle's diameter (D) and the water layer thickness (H). L = 275 µm and τ = 160 ms.

4. 2

 2 Redesigning the model: Speed(H, L)

Table 2

 2 Levels for each factor

	Factor Min. (-1) Central (0) Max. (+1)
	H	200 µm	250 µm	300 µm
	D	50 µm	100 µm	150 µm
	L	225 µm	275 µm	325 µm
	τ	100 ms	160 ms	220 ms
	4 Experimental Results

Table 3

 3 Summary of the analysis of the linear regression for the model:Speed = a 0 + a 1 H + a 2 D + a 3 L + a 4 τ + a 5 H * D + a 6 H * L + a 7 H * τ + a 8 D * L + a 9 D * τ + a 10 L * τ . F-statistic = 5, Prob(F-statistic) = 0.013.

		Coefficients	Standardized coefficients	Standard deviation	p-value
	Intercept 2.03 ×10 4	4.441 ×10 -16 4309	0.001
	H	-68.5	-0.54	14.7	0.001
	D	-19.9	0.069	17.9	0.295
	L	-55.5	-0.33	13.7	0.003
	τ	6.7	0.23	14.6	0.655
	H*D	0.07	0.2	0.045	0.131
	H*L	0.2	0.52	0.045	0.002
	H*τ	-0.02	-0.061	0.038	0.617
	D*L	0.6 ×10 -3	0.002	0.045	0.99
	D*τ	0.01	0.04	0.038	0.721
	L*τ	-6.6 ×10 -6	-2.1 ×10 -5	0.038	1

Table 4

 4 Summary of the analysis of the linear regression for the model:Speed = a 0 + a 1 H + a 2 L + a 3 H * L. F-statistic = 14.7, Prob(F-statistic) = 7.3 × 10 -5

		Coefficients	Standardized coefficients	Standard deviation	p-value
	Intercept 2 ×10 4	4.441 ×10 -16 3157	0.0001
	H	-64.1	-0.54	12.4	0.0001
	L	-55.5	-0.32	11.3	0.0001
	H*L	0.2	0.52	0.04	0.0001
	4.3 Analyzing the influence of the ratio: D H

Acknowledgements This work was supported by the Programa Nacional de Innovación para la Competitividad y Productividad (FINCyT), Ministerio de la Producción, Perú, with grant #394-PNICP-PIBA-2014.