Learning Implied Global Constraints

1 Introduction

Encoding a problem as a constraint network (called model) that will be solved efficiently by a constraint toolkit is a difficult task. This requires a strong expertise in Constraint Programming (CP), and this is known as one of the main bottlenecks to the widespread of CP technology [Puget, 2004]. CP experts often start by building a first model that expresses correctly the problem without any other requirement. Then, if the time to solve this model is too high, they refine it by adding new constraints that do not change the set of solutions but that increase the propagation capabilities of the solver. In Ilog Solver 5.0. user's manual, a Gcc constraint is added to improve the solving time of a graph coloring problem (page 279 in [Ilog, 2000]). In [R´egin, 2001], new constraints are added in a sports league scheduling problem. Such constraints are called implied constraints [Smith et al., 1999]. The community has studied automatic ways of generating implied constraints from a model. Colton and Miguel [Colton and Miguel, 2001] exploit a theory formation program to provide concepts and theorems which can be translated into implied constraints. In Hnich et al. [Hnich et al., 2001], some implied linear constraints are derived by using an extension of the Prolog Equation Solving System [Sterling et al., 1989]. In all these frameworks the new generated constraints are derived from structural properties of the original constraints. They do not depend on domains of variables.

This paper presents a framework based on ideas presented in [Bessiere et al., 2005]. This framework contains two original contributions in automatic generation of implied constraints: First, it permits to learn global constraints with parameters; Second, the implied constraints are learned according to the actual domains of the variables in the model.

Learning global constraints is important because global constraints are a key feature of constraint programming. They permit to reduce the search space with efficient propagators. Global constraints generally involve parameters. For instance, consider the NValue(k, [x1, . . . , xn]) constraint. It holds iff k is equal to the number of different values taken by x1, . . . , xn. k can be seen as the parameter, which leads to different sets of allowed tuples on the xi's depending on the value it takes. The increase of expressiveness provided by the parameters increases the chances to find implied constraints in a network. A learning algorithmwill try, for example, to learn the smallest range of possible values for k s.t. the NValue is an implied constraint. The tighter the range for k, the more the learned constraint can reduce the search space. Many constraints from [Beldiceanu et al., 2005] may be used as implied constraints involving parameters.

Learning implied constraints according to the actual domains is important because constraints learned that way take into account more than just the structure of the network and the constraints. They are closer to the real problem to be solved. For instance, if we know that X, Y and Z are 0/1 variables, we can derive X = Z from the set of constraints X nequal Y, Y nequal Z. Without knowledge on the domains, we cannot derive anything. Even an expert in CP has difficulties to find such constraints because they depend on complex interactions between domains and constraints.

2 Motivation Example

Let us focus on a simple problem where n tasks have to be scheduled. All tasks have the same duration d. Each task i requires a given amount mi of resource. Steps of time are represented by integers starting at 0. At any time, the amount of resource used by all tasks is bounded by maxR. The starting times of any two tasks must be separated by at least two steps of time. Random precedence constraints between start times of tasks are added. The makespan (maximum time) is equal to 2∗(n-1)+d (the best possible makespan w.r.t. the constraint on starting times). The question is to find a feasible schedule. We implemented a naive model with Choco [Choco, 2005]. The start time of task i is represented by a variable xi with domain [0..2 ∗ (n - 1)] (because of the makespan), and the resource capacity is represented at each unit of time t by an array R[t][1..n] of variables, where R[t][i] = mi if task i is active at time t, R[t][i] = 0 otherwise. Constraints ensuring consistency between xi and R[t][i] and constraints on separation of starting times are primitive ones. Sum constraints are used for expressing resource capacity (∑n i=1 R[t][i] ≤ maxR). We place us in the context of a non expert user, so we run the default search heuristics of Choco (the variable with minimum domain first, assigned with its smallest available value). We put a cutoff at 60 seconds. Table 1(left) reports results on instances where n = 4, d = 4 and nj is the number of tasks requiring j resources. Only two precedence constraints are added. It shows that even on these small instances, our naive model can be hard to solve with standard solving techniques. If we want to solve this problem with more tasks, we definitely need to improve the model. An expert-user will see that constraints on the starting time of tasks induce limits on the number of tasks that can start at each point of time. 1 The makespan is indeed equal to the minimal possible value for scheduling all the tasks if they are separated by at least two units. We therefore have to place tasks as soon as possible. This means that one task starts at time zero, one task at time 2, etc. This can be expressed explicitly with a global cardinality constraint (Gcc). Gcc([x1, . . . , xn], [pv1 , . . . , pvk ]) holds iff |{i | xi = vj}| = pvj for all j. So, we add to our model a Gcc constraint that involves all starting times x1, . . . , xn and guarantees that the n first even values of time are taken at least once: Gcc([x1, . . . , xn], [p0, . . . , p2n-1]), where pv ∈ 1 . . . n if v is even, pv ∈ 0 . . . n otherwise. As shown in Table 1(right), adding this simple Gcc constraint to the naive model leads to significant improvements. This example shows that for a nonexpert user, even very small problems can lead to bad performance of the solver. Adding simple implied constraints to the model can dramatically reduce the solving cost.

3 Basic Definitions

A constraint network N is defined by a set X = {x1, . . . , xn} of variables, a set D = {D(x1), . . . , D(xn)} of domains of values for the variables in X, and a set C of constraints. A constraint c is defined on its scope X(c) ⊆ X. c specifies which combinations of values (or tuples) are allowed on the variables in X(c). A solution to N is an assignment of values from their domain to all variables in X s.t. all constraints in C are satisfied. sol(N) denotes the set of solutions of N.

1 The automatic generation of robust search heuristics is out of the scope of this paper.

An implied constraint for a constraint network N is a constraint that does not change the solutions of N. That is, given the constraint network N = (X,D, C), the constraint c with X(c) ⊆ X is an implied constraint for N if sol(N) = sol(N + c) where N + c denotes the network (X, D, C ∪ {c}).

Global constraints are defined on any number of variables. For instance, alldifferent is a global constraint that can be instantiated on scopes of variables of any size. For most of the global constraints, the signature is not completely fixed. Some of their variables can be seen as parameters, that is, 'external' variables that are not involved in any other constraint of the problem. For instance, the Gcc constraint Gcc([x1, . . . , xn], [pv1 , . . . , pvk ]) involves xi's and pv's. The pv's can be variables of the problem (like in [Quimper et al., 2003]), or parameters that take a value in a range (like in [R´egin, 1996]). Another example is the Among constraint. Among([x1, . . . , xn], [v1, . . . , vk], N) holds iff |{i | ∃j ∈ 1..k, xi = vj}| = N. The vj's and N can be parameters or variables [Beldiceanu and Contejean, 1994; Bessiere et al., 2006]. So, a global constraint C defined on a scheme scheme(C) can be specified into different types of parametric constraints depending on which elements in scheme(C) are variables or parameters.

Definition 1 (Parametric constraint) Given a global constraint C defined on scheme(C), a parametric constraint derived fromC is a global constraint C[P] s.t. P = {p1, . . . , pm} is the set of parameters of C[P] with P ⊂ scheme(C), and X(C[P]) is the scope of C[P] with X(C[P]) = scheme(C) \ P.

So, in addition to its variables, a constraint can be defined by a set P of parameters. The set of tuples that are allowed by the constraint depends on the values the parameters can take.

Definition 2 (Instance of parametric constraint) Given a constraint network N = (X,D, C), an instance of a parametric constraint C[P] in N is a constraint C[P ← S ] s.t.:

• X(C[P ← S ]) = X(C[P]) ⊆ X,
• P∩X = ∅,
• S ⊆ |P| is a set of tuples on P,
• C[P ← S ] is satisfied by an instantiation e on X(C[P]) iff there exists t ∈ S s.t. the tuple (e+ t) on scheme(C) is a satisfying tuple for the global constraint C from which C[P] is derived.

Example 1 Let C[P] be the parametric constraint derived from Among([x1, . . . , x4], [v], N) with scope (x1, . . . , x4) and parameters P = (v, N). Let S = {(1, 3), (2, 1)} be a set of combinations for P. A tuple on (x1, . . . , x4) is accepted by the instance of constraint C[P ← S ] iff it has three occurrences of value 1 or one occurrence of value 2. Tuples (1, 1, 3, 1) and (1, 1, 2, 3) satisfy the constraint. Tuples (3, 2, 2, 2) and (2, 1, 1, 2) do not. We suppose that this parametric constraint allows us specifying combinations of parameters that are allowed. In practice, propagation algorithms often put restrictions on how parameters can be expressed.

Given a parametric constraint C[P], different sets S and S ′ of tuples for the parameters lead to different constraints C[P ← S ] and C[P ← S ′ ]. Hence, when adding an instance of parametric constraint C[P] as implied constraint in a network N, it is worth using a set S of tuples for the parameters which is as tight as possible and C[P ← S ] is implied in N.

4 Learning Implied Parametric Constraints

The objective is to learn a 'target' set T ⊆ |P| , as small as possible s.t. C[P] is still an implied constraint. Any s ∈ |P| which is not necessary to accept some solutions of N can be discarded from T. The tighter the learned constraint is, the more promising its filtering power is.

Definition 3 (Learning an implied parametric constraint) Given a constraint network N = (X, D, C) and a parametric constraint C[P] with P ∩ X = ∅ and X(C[P]) ⊆ X, learning an instance of the parametric constraint C[P] implied in N consists in finding a set S ⊆ |P| as tight as possible s.t. C[P ← S ] is implied in N.

A set of tuples T s.t. C[P ← T] is implied in N and there does not exist any S ⊂ T with C[P ← S ] implied in N is called a target set for C[P] in N.

We now give a general process to learn the parameters of implied global constraints. Since our goal is to deal with any type of constraint network, we focus on global constraints C and sets of parameters P ⊆ scheme(C) s.t. C[P ← |P| ] is the universal constraint. This means that if N contains the variables in scheme(C) \ P, C[P ← |P| ] is an implied constraint in N. The learning task is to find a small superset of a target set T (see Definition 3). Given a problem N = (X, D, C) and a parametric constraint C[P], we denote by:

• ubT a subset of |P| s.t. C[P ← ubT] is an implied constraint,
• lbT a subset of ubT s.t. for any t ∈ lbT , C[P ← ubT \ {t}] is not an implied constraint.

In other words, lbT represents those combinations of values for the parameters that are necessary in ubT to preserve the set of solutions of N, and ubT those for which we have not proved yet that we would not lose solutions without them. The following propositions give some general conditions on how to incrementally tighten the bounds lbT and ubT while keeping the invariant lbT ⊆ T ⊆ ubT , where T is a target.

Proposition 1 Let C[P ← ubT ] be an implied constraint in a network N. If there exists S ⊂ ubT s.t. sol(N) = sol(N + C[P ← S ]) then C[P ← S ] is an implied constraint in N. So ubT can be replaced by S .

Testing equivalence of the sets of solutions of two networks is coNP-complete. This cannot be handled by classical constraint solvers. Hence, we have to relax the condition to a condition that can more easily be checked by a solver.

Corollary 1 Let C[P ← ubT ] be an implied constraint in a network N. If there exists S ⊆ ubT s.t. N + C[P ← S ] is inconsistent then C[P ← ubT \ S ] is an implied constraint in N. So ubT can be replaced by ubT \ S .

The weakness of this corollary is that we have no clue on which subsets S of ubT to test for inconsistency. But we know that an implied constraint should not remove solutions when we add it to the network. Hence, solutions can help us.

Proposition 2 Let C[P ← ubT ] be an implied constraint in a network N and e be a solution of N. For any S ⊆ ubT s.t. C[P ← S ] is an implied constraint for N there exists t in S s.t. e satisfies C[P ← {t}].

If a given solution is accepted by a unique combination of values for the parameters, then this combination is necessary for having an implied constraint (i.e., it belongs to lbT ).

Corollary 2 Let C[P ← ubT ] be an implied constraint in a network N and e be a solution of N. If there is a unique t in ubT s.t. e satisfies C[P ← {t}] then t can be put in lbT .

By Corollaries 1 and 2 we can shrink the bounds of an initial set of possibilities for the parameters. Algorithm 1 performs a brute-force computation of a set ubT s.t. C[P ← ubT ] is an implied constraint for a network N. This algorithm works when no extra-information is known from the parameters. It uses corollaries 1 and 2. The input is a parametric constraint and a constraint network (and optionally an initial upper bound UB on the target set). The output is a set ubT of tuples for the parameters, s.t. no solution of the problem is lost if we add C[P ← ubT ] to the network.

Algorithm 1: Brute-force Learning Algorithm

Input: C[P],N (optionally UB); Output: ubT ; begin lbT ← ∅; ubT ← |P| ; /* or the tighter UB */ while lbT nequal ubT and not 'time-out' do Choose S ⊂ ubT \ lbT ; if sol(N + C[P ← S ]) = ∅ then 1 ubT ← ubT \ S ; /* Corollary 1 */ else pick e in sol(N + C[P ← S ]); if there is a unique t in ubT s.t. e satisfies 2 C[P ← {t}] then lbT ← lbT ∪ {t} ; /* Corollary 2 */ end

It is highly predictable that Algorithm 1 can be inefficient. The space of possible combinations of values to explore is exponential in the number of parameters. In addition, checking whether N + C[P ← S ] is inconsistent (line 1) is NPcomplete. Even if N in this learning phase should be only a subpart of the whole problem, it is necessary to use some heuristics to improve the process. Fortunately, in practice, constraints have characteristics that can be used. The next section studies some of these properties.

5 Using Properties on the Constraints

For a given parametric constraint C[P], different representations of parameters may exist. The complexity of associated filtering algorithms generally differs according to the representation used. The more general case studied in Section 4 consists in considering that allowed tuples of parameters for C[P] are given in extension as a set S ⊆ |P| .

5.1 Partitioning parameters

In practice, many parametric constraints satisfy the following property: any two different combinations of values in |P| for the parameters correspond to disjoint sets of solutions on X(C[P]). For instance, this is the case for the Gcc([x1, . . . , xn], [pv1 , . . . , pvk ]) constraint: Each combination of values for the parameters pv1 , . . . , pvk imposes a fixed number of occurrences for each value v1, . . . , vk in x1, . . . , xn.

Definition 4 A parametric constraint C[P] is called parameter-partitioning iff for any t, t ′ in |P| , if t nequal t ′ then C[P ← {t}] ∩ C[P ← {t ′ }] = ∅.

Given an instantiation e on X(C[P]), the unique tuple t on P s.t. e satisfies C[P ← {t}] is denoted by te.

When a constraint is parameter-partitioning, we have the nice property that there is a unique target set.

Lemma 1 Given a constraint network N, if a parametric constraint C[P] is parameter-partitioning then there exists a unique target set T for C[P] in N.

The next proposition tells us that when a constraint is parameter-partitioning, updating the lower bound on the target set is easier than in the general case.

Proposition 3 Let C[P ← ubT ] be an implied constraint in a network N and e be a solution of N. If C[P] is a parameterpartitioning constraint then the unique tuple te on P s.t. e satisfies C[P ← {t}] can be put in lbT .

This Proposition is a first way to improve Algorithm 1. It allows a faster construction of lbT because any solution of N contributes to the lower bound lbT in line 2.

5.2 Parameters as sets of integers

As far as we know, existing parametric constraints are defined by sets of possible values for their parameters p1, . . . , pm taken separately. This means that the target set T must be a Cartesian product T(p1) × · · · × T(pm), where T(pi) is the target set of values for parameter pi. In other words, T is derived from the sets of possible values of each parameter. This is less expressive than directly considering any subset of |P| , but the learning process is easier to handle. Let lbT (pi) and ubT(pi) be the required and possible values in T(pi). Corollaries 1 and 2 are specialized in Corollaries 3 and 4.

Corollary 3 Let C[P ← ubT] be an implied constraint in a constraint network N, with ubT = producttext1 pi∈P(ubT(pi)). Let pi ∈ P, S i ⊆ ubT(pi) \ lbT (pi) and S = producttext1 jnequali ubT (pj) × S i. If N + C[P ← S ] has no solution then values in S i can be removed from ubT (pi).

This corollary says that if a parametric constraint instance C[P ← S ] is inconsistent with a network whereas all its parameters except one (pi) can take all the values in their upper bound, then all values in S (pi) can be discarded from ubT (pi).

Corollary 4 Let C[P ← ubT ] be an implied constraint in a network N and e be a solution of N. Given a parameter pi ∈ P and a value v ∈ ubT(pi), if we have t[pi] = v for every tuple t in ubT s.t. e satisfies C[P ← {t}], then v can be put in lbT ( pi).

As in Section 5.1, Algorithm 1 can be modified to deal with the specific case where parameters are represented as sets of integers. Corollary 4 tells us when a value must go in lbT (pi) for some parameter pi. Corollary 3 tells us when a value can be removed from ubT (pi) for some parameter pi.

5.3 Parameters as ranges

The possible values for a parameter pi can be represented by a range of integers, that is, a special case of set where all values must be consecutive w.r.t. the total order on integers. The only possibility for modifying the sets lbT (pi) and ubT (pi) of a parameter pi is to shrink their bounds min(lbT(pi)), max(lbT(pi)), min(ubT(pi)) and max(ubT(pi)). This case restricts even more the possibilities for the combinations of parameters allowed, and simplifies the learning process. Corollaries 1 and 2 can be specialized as Corollaries 5 and 6.

Corollary 5 Let C[P ← ubT] be an implied constraint in a constraint network N, where parameters are represented as ranges. Let pi ∈ P and v < min(lbT(pi)) (resp. v > max(lbT(pi))) and S = producttext1 jnequali ub(pj) × (-∞..v] (resp. S = producttext1 jnequali ub(pj) × [v.. + ∞)). If N + C[P ← S ] has no solution then min(ubT (pi)) > v (resp. max(ubT (pi)) < v).

Corollary 6 Let C[P ← ubT ] be an implied constraint in a network N and e be a solution of N. Given a parameter pi ∈ P and a value v ∈ ubT(pi), if we have t[pi] = v for every tuple t in ubT s.t. e satisfies C[P ← {t}], then min(lbT(pi)) ≤ v ≤ max(lbT (pi)).

Thanks to Corollary 5, tightening the upper bounds for a given pi is simply done by checking if forcing it to take values smaller than the minimum (or greater than the maximum) value of its lower bound leads to an inconsistency in the network. If yes, we know that all these values smaller than the minimum of lbT (pi) (or greater than the maximum of lbT (pi)) can be removed from ubT (pi).

6 Making the Learning Process Tractable

One of the operations performed by the learning technique described in Sections 4 and 5 is a call to a solver to check if the network containing a given instance of parametric constraint is still consistent (line 1 in Algorithm 1). This is NPcomplete. A key idea to tackle this problem is that implied constraints learned on a relaxation of the original network are still implied constraints on the original network.

Proposition 4 Given a network N = (X,D, C) and a network N ′ = (X,D ′ , C ′ ), if a constraint c is implied in N ′ and sol(N) ⊆ sol(N ′ ) then c is implied in N.

Selecting a subset of the constraints.

Thanks to Proposition 4, we can select any subset of the constraints of the network on which we want to learn an implied constraint, and the constraint learned on that subnetwork will be implied in the original network. In the example of Section 2, the Gcc constraint is only posted on the variables representing tasks and is an implied constraint on the subnetwork where neither the resource constraints nor the precedence constraints are taken into account. Thus, the underlying network was a simple one that could easily be solved.

Optimization problems.

In an optimization problem, the set of solutions is the set of instantiations that satisfy all constraints and s.t. a cost function has minimal (or maximal) value. If N = (X,D, C) is the network and f is the cost function, let N ′ = (X, D, C∪ {c UB f })

where c UB f is a constraint accepting all tuples on X with cost below a fixed upper bound UB (we concentrate on minimization). If UB is greater than the minimal cost, then any implied constraint in N ′ accepts all solutions of N optimal wrt f . The idea is thus to run a branch and bound on N for a fixed (short) amount of time. UB is set to the value of the best solution found. Then, the classical learning process is launched on the network N + c UB f . Note that if the learned implied constraint improves the solving phase, it can permit to quickly find a bound UB ′ better than UB. Using this new bound UB ′ , we can continue the learning process on N +c UB ′ f instead of N + c UB f . The learned implied constraint will be tighter because N + c UB f is a relaxation of N + c UB ′ f . We observe a nice cooperation between the learning process and the solving process.

Time limit.

It can be the case that finding a subnetwork easy to solve is not possible. In this case, we have to find other ways to decrease the cost of the consistency test of line 1 in Algorithm 1. A simple way is to put a time limit to the consistency test. If the solver has not finished its search before the limit, ubT is not updated and the algorithm goes to the next loop.

7 Experiments

We evaluate our learning technique on the Gcc constraint (see Section 2). The Gcc global constraint is NP-hard to propagate when all elements in its scheme are variables [Quimper et al., 2003]. However, when the cardinalities of the values are parameters that take values in a range, efficient algorithms exist to propagate it [R´egin, 1996; Quimper et al., 2004]. In addition, the Gcc constraint can express many different features on the cardinalities of the values. This is thus a good candidate for being added as an implied constraint. In all these experiments we learn a Gcc where cardinalities are ranges of integers. Results in Sections 5.1 and 5.3 apply directly. We used the Choco constraint solver [Choco, 2005].

Satisfaction Problem.

The first experiment was performed on the problem of Section 2. The learning algorithm was run on the subnetwork where resource constraints and precedence constraints are discarded. The learning is thus fast (300 to 800 milliseconds for n = 4 or n = 5). We fixed to 30 the limit on the number of consistency tests of the subnetwork with the added Gcc (line

1 in Algorithm 1). Table 2 shows the results on a model containing the learned implied Gcc. The first time number corresponds to the learning process and the second to the solving time. Results in Table 2 are almost the same as results in Table 1, where the implied Gcc was added by the expert user. This shows that a short run of the learning algorithm gives some robustness to the model wrt the solving process: The problem is consistently easy to solve on all types of instances whereas some of them could not be solved on the naive model of Section 2. Tables 3 and 4 show the results when we increase the number of tasks and their length (n = d = 5 instead of 4) and the number of random precedence constraints (4 instead of 2). We stopped the search at 60 seconds. We were able to solve all problems with size n = 6 in a few seconds (including the learning time) while most of them are not solvable without the implied Gcc even after several minutes. This first experiment shows that when taking a naive model with a naive search strategy, our learning technique can improve the robustness of the model in terms of solving time. The effort asked to the user was just to have the intuition that "there is maybe some hidden Gcc related to the ordering of tasks". This is a much lower effort than studying by hand the possible implied constraints for each number of tasks and durations n and d.

Optimization Problem.

At the Institute of Technology of the University of Montpellier (IUT), n students provide a totally ordered list (u1, . . . , um) of the m projects they prefer: project ui is strictly preferred to project ui+1. The goal is to assign projects s.t. two students do not share a same project, while maximizing their satisfaction: a student is very satisfied if she obtains her first choice, less if she obtains the second one, etc. Obtaining no project of her list is the worst possible satisfaction. Additional constraints exist such as a limit of 6 projects selected in the set of projects proposed by a teacher. A first model was provided by students from that institute who are novices in constraint programming: students are variables, domains are their set of preferred projects plus an extra-value "0", which means that no project in the preferred list was found. Constraints "(xi nequal xj) ∨ (xi = xj = 0)" between each pair (xi, xj) of students express mutual exclusion on projects. Each student has a preference-variable measuring her satisfaction. Preferencevariables are linked to student-variables by table constraints {(u1, 0), . . . , (um, m - 1), (0, m)}. The objective is to minimize the sum of preference-variables. This model is referred as the initial model. We wish to learn an implied Gcc on student variables. The solver is first launched on the initial model for a short time (1 sec.) to get a first solution S 0 and an upper bound on the quality of solutions, as described in Section 6. We had only one real instance (with 60 students), so we derived from the real data some sub-instances with less students (preserving the ratio "number of projects/number of students" and the distribution of the choices).

Left hand side of Table 5 shows the time and number of nodes with the initial model according to the number of students n. Right hand side of Table 5 shows the results obtained when learning an implied Gcc on the student variables. We fixed to 10 × n the limit on the number of consistency tests (line 1 in Algorithm 1), with a cutoff of 0.5 seconds for each of them. Thus, the maximum learning time grows linearly with the size of the problem. The learning time includes the generation of an initial positive example. The results show a tremendous speed up on the model refined with a learned implied Gcc compared to the initial model. This shows that learning implied global constraints in an optimization problem can greatly pay off when the model has been designed by a non CP expert.

8 Conclusion

Global constraints are essential in improving the efficiency of solving constraint models. We proposed a generic framework for automatically learning implied global constraints with parameters. This is both the first approach that permits to derive implied global constraints and the first approach that learns implied constraints according to the actual domains, not just constraints derived from structural or syntactical properties. We applied the generic framework to special properties that global constraints often satisfy. Our experiments show that a very small effort spent learning implied constraints with our technique can dramatically improve the solving time.