G Simonin
email: gsimonin@laas.fr

C Artigues
email: artigues@laas.fr

E Hebrard
email: hebrard@laas.fr

P Lopez
email: lopez@laas.fr

Scheduling Scientific Experiments on the Rosetta/Philae Mission

The Rosetta/Philae mission was launched in 2004 by the European Space Agency (ESA). It is scheduled to reach the comet 67P /Churyumov-Gerasimenko in 2014 after traveling more than six billion kilometers. The Philae module will then be separated from the orbiter (Rosetta) to attempt the first ever landing on the surface of a comet. If it succeeds, it will engage a sequence of scientific exploratory experiments on the comet. In this paper we describe a constraint programming model for scheduling the different experiments of the mission. A feasible plan must satisfy a number of constraints induced by energetic resources, precedence relations on activities, or incompatibility between instruments. Moreover, a very important aspect is related to the transfer (to the orbiter then to Earth) of all the data produced by the instruments. The capacity of inboard memories and the limitation of transfers within visibility windows between lander and orbiter, make the transfer policy implemented on the lander's CPU prone to data loss. We introduce a global constraint to handle data transfers. The goal of this constraint is to ensure that data-producing activities are scheduled in such a way that no data is lost. Thanks to this constraint and to the filtering rules we propose, mission control engineers are now able to compute feasible plans in a few seconds for scenarios where minutes or even hours were previously often required. Moreover, in many cases, data transfers are now much more accurately simulated, thus increasing the reliability of the plans.

Introduction

The international Rosetta/Philae project is an European consortium mission approved in 1993, and is under the leadership of the German Aerospace Research Institute (DLR) and ESA 1 . The spacecraft was launched in 2004 by Ariane 5, and is set to travel more than six billion kilometers to finally reach and land on the comet 67P /Churyumov-Gerasimenko in 2014 in order to analyze the comet structure. It will follow a complex trajectory which includes four gravity assist maneuvers (3 x Earth, 1 x Mars) before finally reaching the comet and enter its orbit. Then, the lander Philae will be deployed and will land on the surface of the comet. Philae features ten instruments, each developed by a European laboratory, to accomplish a given scientific experiment when approaching, or once landed on the comet. For instance, CIVA and ROLIS are two imaging instruments, used to take panoramic pictures of the comet and microscopic images. The Alpha Proton X-ray Spectrometer (APXS) experiment analyses the chemical composition of the landing site and its potential alteration during the comet's approach to the Sun. The data obtained will be used to characterize the surface of the comet, to determine the chemical composition of the dust component, and to compare the dust with known meteorite types.

The exploratory mission will have three phases. The first one, SDL (Separation-Descent-Landing), will run for 30 minutes during which many experiments will be done. For the second phase, FSS (First Science Sequence), the execution of experiments will last 5 days. This phase is critical because the execution of the most energetically greedy experiments requires battery power. The quality of this schedule conditions the longevity of the batteries and is therefore key to the sucess of the mission. Finally, during the LTS phase (Long Term Science), scientific activities will be resumed at a much slower pace, using the lander's own solar panels to partially reload the batteries. This phase will continue for months until the probe is destroyed due to the extreme temperatures of the Sun.

This project is a collaboration with CNES2 in Toulouse (France). The goal of the Scientific Operation and Navigation Centre (SONC) is to plan the sequence of experiments and maneuvers to be done in each of these phases while making the best use of the available resources. This project has many similarities with the (interrupted) Net-Lander program [START_REF] Mancel | Complex Optimization Problems in Space Systems[END_REF]. A first software (called MOST) has been developed on top of the Ilog-Scheduler/Solver library by an industrial subcontractor. Every instrument, subsystem and experiment has been modeled precisely in this framework, and it is therefore possible to check solutions with a high degree of confidence on their feasibility.

The main scientific experiments need to be scheduled to satisfy a number of constraints involving the concurrent use of energy (batteries), and of the main CPUs as well as each instrument's memory. Moreover, each experiment produces data that must be transferred to Earth. Each experiment has its own memory, collecting data as it is produced. This data is then transferred to a central mass-memory, then sent to Rosetta (the orbiter) when it is in visibility, i.e., above the horizon of the comet with respect to Philae. All transfers from the experiments to the mass memory, and from the mass memory to the orbiter are executed (that is, computed onboard) by the Command and Data Management System (CDMS). The transfer policy of the CDMS may lead to data loss when an experiment produces more data than its memory can store and its priority is not high enough to allow a transfer to the mass-memory. This is modeled within MOST using RESERVOIR constraints [START_REF] Laborie | Algorithms for propagating resource constraints in ai planning and scheduling: existing approaches and new results[END_REF]. Data-producing activities fill the reservoir, while multiple pre-defined data transfer tasks of variable duration empty it. There are numerous problems related to data transfers in spatial applications [START_REF] Morris | Planning and Scheduling for Fleets of Earth Observing Satellites[END_REF][START_REF] Beaumet | Feasibility of autonomous decision making on board an agile earth-observing satellite[END_REF], however the problem at hand is significantly different since plans are computed on the ground, and the data transfer policy is beyond our control.

This modeling choice has several drawbacks and it quickly became apparent that it was the critical aspect of the problem to tackle in order to find better solutions faster. The first problem with this model is that data transfers are not accurately represented. For each experiment, a sequence of tasks standing for data transfers are pre-defined.

Their duration is constrained so that the experiment with the highest priority is allowed to transfer as much as possible, and no overlap is allowed among transfers. In the current implementation there is a transfer task every 120 seconds over the horizon, with a maximum duration of 120 seconds. This is too few to accurately represent the policy of the CDMS, however, this is already too much for Ilog-Scheduler to handle (the planning horizon may be up to one day, i.e., about 700 transfer tasks for each experiment).

Instead we propose to encapsulate data transfers into a global constraint. The decision variables are start times of data-producing activities (data-producing rate and duration are known in advance) and the priority permutation. This allows us to very quickly check the satisfiability of a schedule with respect to data transfer. Moreover, we can compute bounds allowing to filter out the domain of the variables standing for start time of the data-producing activities. Unfortunately enforcing arc consistency or even bounds consistency on this constraint is NP-hard, so we do not give a complete filtering algorithm. However, our approach reduces the solving time dramatically: from hours in some cases to seconds in all scenarios currently considered by the SONC. Moreover, the result is much more accurate, to the point that some scenarios for which MOST could not show that transfers were feasible can now be solved efficiently.

In Section 2 we briefly outline the energetic aspect of the problem and more formally define the data transfer aspect. Then, in Section 3 we introduce our approach to modeling data transfers. In particular we give an efficient satisfiability checking procedure and two filtering rules for the introduced global constraint. Last in Section 5, we report experimental results and compare results between old and new models.

Problem Description

Each experiment and subsystem can be seen as a list of activities to be scheduled. Notwithstanding data transfers, the problem can be seen as a scheduling problem over a set of experiments with relatively standard constraints.

Precedences: Activities within the same experiment might have precedence constraints; for instance the Lander also carries a Sampling Drilling and Distribution device (SD2), which will drill more than 20 cm into the surface, collect samples and deposit them in an oven. The oven then rotates to a position whereby it can be connected to the inlet of the gas management system of another instrument: Ptolemy. At this point, sample volatiles can be released into the analytical system of Ptolemy by heating the oven, and the analysis can begin.

Cumulative Resources: Activities within the experiments concurrently use the energy from a centralized source, mainly from batteries. All the energy sources (batteries and solar panels) are centralized on a main power line. The energy needed to run each task is supplied by an auxiliary power line. Each auxiliary power linked to a converter, and each converter is linked to the main power line. At each level, the total instant power delivered (by a line or a converter) cannot exceed a given threshold. Each activity is therefore associated to a unique auxiliary power line and to a unique converter. For each auxiliary power line, all the activities supplied by this line are constrained by CUMULATIVE constraint [START_REF] Aggoun | Extending chip in order to solve complex scheduling and placement problems[END_REF] with capacity equal to this threshold. Similarly another a CUMULATIVE constraint is associated to each converter, and a last one is associated to the main power line, involving all activities of the problem.

State Resources: Each instrument can have multiple states along the schedule. Some activities can trigger the modification of the state of an instrument, and the processing of certain activities might be subject to some instruments being a given state. This is modeled using predefined state resources constraints in Ilog-Scheduler.

Data Transfer and Memory Constraints: Every experiment has its own memory. Some activities produce data, temporarily stored on the experiment's memory. Then this data will be transferred onto the mass-memory and subsequently to the orbiter.

The onboard CDMS controls all data transfers, from the experiments to the mass memory, and from the mass memory to the orbiter. Within a plan, experiments are (totally) ordered according to a priority function. Apart from this ordering, the CDMS is completely autonomous. It simply transfers data from the experiment with highest priority among those with transferable data. Moreover, it transfers data from the massmemory to the orbiter whenever possible, that is, when there is some visibility. However, it does not ensure that all produced data will eventually be transferred back to Earth. When too much data is produced simultaneously and not enough can be transferred on the mass-memory, or when there is no visibility with the orbiter and therefore the mass-memory cannot be emptied, the capacity of an experiment's memory may be overloaded and data is lost.

Data transfers must be taken into account accurately in order to ensure that activities are sequenced in such a way that no data will be lost with respect to the CDMS policy.

A Global Constraint for Data Transfer

Except for the data transfer aspect, all the constraints above can be modeled using the standard methods and algorithms [START_REF] Nuijten | Constraint Based Scheduling[END_REF] all available in Ilog-Scheduler. Hence, we focus on data transfers and propose a global constraint to reason about this aspect of the problem.

From now on, we consider a set {E 1 , . . . , E m } of m experiments. An experiment E k = {t k1 , . . . , t kn } is a set of data-producing tasks 3 , and is associated with a memory of capacity M k . A task t ki produces data which is sent during a time period p ki at a rate π ki to the experiment's memory. The lander possesses a mass memory of capacity M 0 , where data can be transferred from experiments.

The CDMS is given as input a priority ordering on experiments. For i ∈ [1, . . . , m], we denote by P (i) the experiment at rank i in this ordering and its dual R(k) standing for the rank of experiment E k in the priority ordering (

P (i) = k ⇔ R(k) = i).
We shall say that experiment E k has higher priority than experiment E j iff R(k) < R(j).

Data can only be transferred out to the orbiter when it is in visibility, that is in the line of sight of the lander over the horizon of the comet. Visibility is represented as a set of intervals {[a 1 , b 1 ], . . . , [a v , b v ]} in the scheduling horizon which lengths and frequencies depend on the chosen orbit. We shall use V (t) as a Boolean function which equals true iff time t is included in one of the visibility intervals. Moreover, data is transferred in and out memories by block units of 256 bytes.

We consider the following decision variables: s 11 , . . . , s mn , with domain in [0, . . . , H], standing for the start times of data-producing tasks {t 11 , . . . , t mn }, respectively. Here we will assume that the priority permutation is fixed. Indeed there are often few experiments and exploring all permutations would be easy.

The fact that data loss should be avoided can be seen as a relation (i.e., a constraint) between the decision variables above. It is relatively easy to understand this relation procedurally since the CDMS policy is deterministic. Given a priority ordering and a fixed schedule of the data-producing activities, one can unroll the rules outlined above to check whether the CDMS policy will lead to data loss or not.

In this section, we formally define the constraint DATATRANSFER([s 11 , . . . , s mn ]) ensuring that the schedule of tasks {t 11 , . . . , t mn }. is such that no data is lost.

First, in Section 3.1 we discuss an "exact" definition based on following the transfer of each block of data individually. However, this formulation is not practical, so we propose an alternative model in Section 3.2. The basic idea is to represent all the data produced by an activity as a continuous quantity. With this viewpoint, tasks that do not produce data as fast as it can be transferred are challenging to model. Indeed, the CDMS actually waits for a block of data to be completed before transferring it, and can therefore use this waiting time to transfer data from other experiments with lower priority. We approximate this "vertical" partition of the data bus, by a "horizontal" partition, i.e., we consider that the bandwidth can be divided over parallel transfers. This model allows us to represent memory usage very precisely, with a computational complexity independent on the time horizon and on the amount of data produced.

CDMS Policy

In this section we detail the policy of the CDMS, then we define what would be a constraint modeling exactly the relation between the start time of data-producing activities it induces.

The CDMS transfers data by blocks of 256 bytes. Its policy is relatively simple and can be described using a simple automated earliest transfer scheduling algorithm (AETS). AETS runs the two following processes in parallel:

-Repeat: Scan experiments by order of priority until one with at least one block of data on its memory is found. In that case, transfer one block from this experiment to the mass memory unless the mass memory is full. -Repeat: If the orbiter is visible, and there is at least one block of data on the mass memory, then dump one block (transfer from the mass memory to the orbiter).

So we can define the DATATRANSFER constraint as the relation allowing only assignments of start times and priorities such that given the CDMS policy (AETS), no block of data is produced while the memory of the experiment is full.

In order to specify this constraint as precisely as possible we would need to consider each block of data, and its associated transfer task, individually. More precisely, we need π ki p ki transfer tasks for each data-producing activity t ki . The release time of the j th block's transfer task is s ki + j(1/π ki ), where s ki is the start time of t ki . Moreover, the start times and durations of these transfer tasks are functionally dependent on the start times of data-producing activities and experiment priorities. This dependence relation is a consequence of the AETS procedure.

The DATATRANSFER constraint is NP-complete to satisfy, hence NP-hard to filter. Indeed, consider the particular case where memory capacities are all of exactly one block of data, and the mass-memory is unlimited. In this case, each activity must transfer a block to the mass-memory as soon as it is produced. In other words, we can see a transfer task as non-interruptible. However, since there is a single transfer channel to the mass-memory, no overlap is possible between these tasks. Since we have time windows on the variables s ki , this particular case is therefore equivalent to a disjunctive unary resource, i.e., it is strongly NP-hard.

Approximated Definition

It is difficult to capture very precisely the behavior of the CDMS. Moreover, it is not practical since it involves manipulating a very large number of transfer tasks. When we consider a data-producing activity in isolation, the number of transfer tasks and their frequency is easy to compute. However, when we consider several data-producing activities with different priorities and unknown start times, this viewpoint becomes impractical. We therefore propose an alternative model that approximate very closely the amount of transferred data with a reasonable time and space complexity.

The basic idea is straightforward. Consider a task t ki that produces more data than it can transfer τ r(k,t) ≤ π ki , with τ r(k,t) the transfer rate at time t from an experiment E k to mass-memory. Suppose first that there is no task with higher priority. The transfer can be seen as a continuous task of duration π ki p ki τ r(k,t) . However there are three difficulties. First, blocks are transferred from experiments memories to the mass memory at a constant rate. However, when seeking which experiment to transfer from, the length of the scanning process depends on the number of active experiments and on the priority of the experiment eventually selected. An experiment E k is active between the start of its first activity and the end time of its last activity, or if the experiment memory is not empty. The transfer rate is thus larger in practice for the higher priority experiments as they are scanned first. To emulate this, we use variable transfer rates. The potential transfer rate τ r(k,t) depends on the number x of active experiments and on its relative priority y among them. The actual value is read in a table which entries were measured experimentally. The rate above applies to non-visibility periods. According to the same principles, another table gives us the transfer rate τ r(k,t) while in visibility (it is lower due to the parallelism with memory dumps). Transfers between mass-memory and the orbiter have a constant rate denoted τ mm .

Second, transfer tasks can be interrupted, however, they are different from classic preemptive tasks in that we do not decide when the interruption occurs. When an experiment with higher priority starts producing data, it preempts any current transfer of lower priority. This is easy to model since this is the unique context where an interruption can happen. If there is no experiment with higher priority to interrupt the transfer, the usage of the experiment's memory increases at rate π ki -τ r(k,t) during p ki seconds. Similarly, during π ki p ki τ r(k,t) seconds the usage of the mass memory increases at rate τ r(k,t) . The third difficulty concerns tasks producing data at a lower rate than the possible transfer rate (i.e., τ r(k,t) > π ki ). In this case, data is transferred one block at a time, with a lag between each transfer to wait for the next block to be produced (see Fig. 1). Other tasks of lower priority with non-empty memory can use these gaps to begin the transfer of a block of data. In other words, the duration of the transfer of highest priority is still very close to π ki p ki τ r(k,t) seconds, however other transfer can be squeezed in that same period. In order to simulate this, we consider that the data bus has a capacity (bandwidth) normalized to 1. The demand of a task t ki at time t is min(1, π ki τ r(k,t) ). Bandwidth is allocated recursively, according to priority (see Figure 2). Let m t k stand for the quantity of data in the memory of experiment E k at time t (with t ∈ R) and m t 0 be the the quantity of data in the mass-memory. Moreover, let π t k stand for the data-producing rate on experiment E k at time t, p(τ t k ) stand for the potential transfer rate of experiment E k at time t if it was of highest priority and let τ t k stand for the actual transfer rate from experiment E k to the mass memory at time t.

Definition 1.

DATATRANSFER(s 11 , . . . , s mn ) ⇔ ∀t, k,

π t k = π ki if ∃i s.t. s ki ≤ t ≤ s ki + p ki 0 otherwise (1) ∀t, k, p(τ t k ) =    0 if m t 0 = M 0 ∨ (m t k = π t k = 0) τ r(k,t) if m t 0 < M 0 ∧ m t k > 0 min(π t k , τ r(k,t) ) otherwise (2) ∀t, k, τ t k = min(p(τ t k ), τ r(k,t) (1 - R(k)-1 i=1 τ t P (i) τ r(P (i),t) )) (3) ∀t, k, m t k = t 0 (π t k -τ t k )dt (4)
∀t,

m t 0 = t 0 ( m k=1 τ t k -V (t)τ mm )dt (5)
Equation 1 simply states that if a data-producing activity t ki is running at time t, then the data-producing rate π t k of an experiment k at that time is equal to the dataproducing rate of t ki , and it is null otherwise.

Equation 2 defines the expected transfer rate p(τ t k ) of experiment E k at time t if it is not trumped by other experiments of higher priority. If there is no data on the memory and no data being produced, or if the mass memory is full, this rate is null. Otherwise, if there is some data on memory, it can be transferred at the maximum available rate (τ r(k,t) ). If the memory is empty, but data is being produced, we assume that it cannot be transferred at a higher rate than it is produced.

Equation 3 gives the real transfer rate, i.e., taking into account experiments with higher priorities. The experiment with highest priority uses the bandwidth proportionally to the ratio between its expected transfer rate p(τ t k ) and the maximum transfer rate τ r(k,t) . Then the residual bandwidth is attributed using recursively the same rule.

Finally, equations 4 and 5 link the usage of the different memories to the sum of the in and out transfer rates (π k and τ k are used here as functions of t).

In Figure 3 we show the difference between the two models.

transfer

Fig. 3: Comparison of the two representations: two data-producing activities t 1 and t 2 (bottom); The "exact" view of the corresponding transfers, sharing the transfer bus because of gaps due to the low data-producing rate (middle); The alternative reformulation, where this is modeled as sharing the bandwidth (top).

Checking and Filtering Algorithms

In this section we introduce a filtering procedure for the DATATRANSFER constraint. We first introduce an efficient O(nm log(nm)) procedure for computing transfers and memory usage of a given schedule. This procedure execute a sweep of the horizon similar to that described in [START_REF] Beldiceanu | Sweep as a generic pruning technique applied to the non-overlapping rectangles constraint[END_REF]. Besides checking whether the constraint is violated we shall also use this algorithm to compute lower bounds in order to filter the domains.

Data Transfer Verification

Given a complete schedule of the data-producing activities, and a priority ordering, we now describe an algorithm that computes the effective transfer rate (in the sense of Definition 1) and the memory usage for each experiment over the whole horizon in time O(nm log(nm)). Notice that both are step functions, moreover we will see that there are at most O(nm) breaking points, so they can be stored on O(nm) bits. This algorithm can be used to verify whether an assignment is consistent by simply checking that the usage of all experiments remains within the memory's capacity. We shall also use it to compute bounds on the memory usage of extreme scenarios (e.g., all tasks set to their earliest start time). It sweeps the time horizon chronologically, computing variations of various parameters only when certain events occur. First, we build the list of events. Each event is time tagged and there are six types (for O(nm) events in total): Start/end of visibility; Start/end of a data-producing activity; Start/end of experiments. Then, we sort them in chronological order and explore them in that order. For each time point t where at least an event occurs, we go through all events occurring at t and update the following arrays accordingly:

visibility stands for whether there is a visibility line at time t. It is flipped whenever encountering a "Start of visibility" or "End of visibility" event; production(k) stands for the data-producing rate of experiment E k at time t. It is increased (resp. decreased) by the data-producing rate of the activity whenever encountering a "Start of production" (resp. "End of production") event; active stands for the number of active experiments at time t. It is increased (resp. decreased) by one whenever encountering a "Start of experiment" (resp. "End of experiment") event.

At each step of the loop, we therefore know the complete state (data-producing rate on each experiment, whether we are in visibility or not, and how many experiments are active). Moreover, we also keep track of the memory usage with another array: memory. We then compute what are the current transfers, and partition the bandwidth between them. For each experiment E k (visited by order of priority), if it has data on memory, or if it is currently producing data, and if the bandwidth is not null, we create a transfer. We first compute its potential transfer rate τ r(k,t) according to the rules described above. If it has some data on memory, all of the bandwidth is attributed to this transfer. Otherwise, its actual transfer rate is equal to the minimum between the nominal transfer rate and the current data-producing rate: τ = min(production(k), τ r(k,t) ). The ratio τ /τ r(k,t) of the bandwidth is allocated to this transfer.

Then, for each experiment currently in transfer, we compute a theoretical deadline, i.e., the date at which it will be emptied at this rate of transfer if nothing changes. Notice that it can be never. Similarly, we compute a theoretical deadline for filling the massmemory. If the earliest of all these deadlines happens earlier than the next scheduled event, we add it to the list of events. This type of events will do nothing on its own, however, it will allow the algorithm to recompute the transfers according to the new situation (the mass-memory being filled, or an experiment's memory being empty).

Finally, the usage of each memory at time t is updated according to the transfers. This algorithm has a worst case time complexity of O(nm log(nm)). The list of events has initially O(nm) elements. There are two for each data-producing task, two for each visibility window, and two for each experiment (we assume that the number of visibility windows is less than nm). Sorting them can therefore be done in O(nm log nm) time. In the main loop, events are processed only once, and this takes at most O(m) time. Moreover, in some cases, "deadline" events can be added during the exploration of the event list. However, at most one such event can be added for each event initially in the list. Indeed, consider a deadline event. It is added to the list only if no other event yet to process has an earlier date. In other words, transfer and dataproducing rates as well as visibility do not change. The experiment memory that was emptied will therefore stay empty at least until the next standard event. The same is true for deadline event triggered by filled mass-memory: it will stay full at least until the next visibility event. Therefore, the worst case time complexity of the main loop of this algorithm is O(nm).

Filtering Rules

In this section introduce two propagation rules for the DATATRANSFER constraint.

Minimal transfer span:

The first rule tries to guess a lower bound on the total span of a subset of activities of the same experiment E k . The intuition is that if data is produced at a higher rate than it can be transferred out, the capacity of a memory could be reached and data will be lost. In other words, given a set Ω ⊆ E k of data-producing activities of an experiment E k , the total amount of data produced by these activities, minus what can be stored on the memory of E k , need to be transferred out. The duration of this transfer is a lower bound on the span of this set of activities, i.e., the duration between the minimum start time and maximum end time of any activity in this set.

The total amount of data produced by activities in Ω is equal to t ki ∈Ω π ki p ki . At most M k can be stored on the experiment's own memory, hence at least t ki ∈Ω π ki p ki -M k has to be transferred out before the end of the last data-producing activity. Let τ be the highest possible transfer rate for data out of the experiment's own memory. We can use this rate to derive a lower bound on the total duration of Ω:

( max t ki ∈Ω (e ki ) -min t ki ∈Ω (s ki )) ≥ t ki ∈Ω π ki p ki -M k τ (6)
In real scenarios, data-producing activities of a given experiment cannot overlap, and in many cases the order is known a priori. Assuming that the activities in Ω are ordered, with t kf being the first task and t kl being the last task in Ω, we can often induce the simpler constraint:

e kl -s kf ≥ t ki ∈Ω π ki p ki -M k τ .
Example 1. Figure 4 depicts the application of this rule. We have two activities t 1 , t 2 , the former producing π 1 = 5 blocks/sec and the latter π 2 = 4 blocks/sec, both for 70 seconds. Therefore, π 1 p 1 + π 2 p 2 = 630 blocks are produced. Assume that the memory of this experiment has a capacity of 250 blocks. Consequently, 380 blocks need to be transferred out in order to avoid data loss. Since the maximum transfer rate is 2 blocks/seconds, this transfer will take at least 190 seconds. We can conclude that the end of t 2 is at least 190 seconds after the start of t 1 . The grey scale gives the evolution of the memory for t 2 finishing exactly 190 seconds after the start of t 1 .

min(|t ki ∩ [a, b]|) = min(|[a, b] ∩ [min(s ki ), min(s ki ) + p ki ]|, |[a, b] ∩ [max(s ki ), max(s ki ) + p ki ]|)
We can compute a lower bound T k (a, b) on the time required to transfer the data produced by experiments of higher priority than k on the interval [a, b] as a lower bound on the data produced, divided by the maximum transfer rate:

T k (a, b) = ( j<R(k) j=1 n i=1 |t P (j)i ∩ [a, b]| * π P (j)i )/τ
Given a subset Ω ⊆ E k of experiment E k , consider the time interval [a, b] between the latest start time of any task in Ω (a = max t ki ∈Ω (min(s ki ))) and the earliest end time of any task in Ω (b = min t ki ∈Ω (max(s ki ) + p ki )). The lower bound on the span given above assumes continuity of the transfer, and by definition this duration must include the interval [a, b]. Therefore, any interruption of the transfer during this period induces the same delay on the minimal span of Ω. In other words, any time taken to transfer data of experiments with higher priority during [a, b] (T k (a, b)) can be simply added to the lower bound above.

Hence we can tighten the constraint 6 as follows (with a = max t ki ∈Ω (min(s ki )) and b = min t ki ∈Ω (max(s ki ) + p ki )):

( max t ki ∈Ω (e ki ) -min t ki ∈Ω (s ki )) ≥ t ki ∈Ω π ki p ki -M k τ + T k (a, b) (7)
We apply this rule for every set of consecutive activities (with respect to their earliest start times) of every experiment. There are n 2 m such sets, and computing the lower bound takes at most O(nm) time. The whole procedure hence has a worst case time complexity of O(n 3 m 2 ).

Mass memory saturation: Since transfers from the lander to the orbiter are possible only during visibility, the data can only accumulate on the mass-memory while not in visibility. As a consequence, the period that precedes a visibility window is critical since the mass memory can be saturated hence blocking all transfers. When this happens, data produced by an experiment remains on its memory at least until the next visibility window, and it is possible to lose data when the experiment's memory itself is saturated.

We use this observation to deduce that data-producing activities that would generate too much data to hold on the mass memory and on their own memory should be either advanced or postponed. Suppose that we know that at time t, the mass-memory will necessarily be filled. It will remain so until the next visibility. Now, if an activity t ki produces more data in the interval between t and the next visibility window than its own memory can hold, it will be lost. Indeed, no data can be transferred onto the massmemory as long as it is full, and it will start to be emptied only when the visibility allows it. We can thus deduce that the activity t ki must start either early enough to produce before t or late enough so that the data in excess will be produced during the visibility period (in order to have a chance to be transferred).

First, we show how to compute an upper bound t on the time when the massmemory will reach its maximum before a given visibility window. We consider a single visibility cycle V = (a, v, b), where a < v < b denote, respectively, the end of the previous cycle, the start of a visibility window, and the end of that visibility window. Let Ω(V) be the set of data-producing activities that are necessarily scheduled within the interval [a, b].

Proposition 1. Scheduling all data-producing activities in Ω(V) to their latest start time minimizes the memory usage of the mass-memory (m t 0 ) for all t ∈ [a, b]. Proof (sketch). Clearly if we consider a data-producing activity t ki in isolation, setting its start time to the latest possible time point (max(s ki )) delays the transfer onto the mass memory hence its memory usage for any time point in [a, b].

When multiple data-producing activities can run in parallel, experiments of high priority can preempt transfer intervals of experiment of lower priority. Therefore, one could advance a data-producing activity t jl in time in order to use the resource and therefore delay the transfer of some of the data produced by t ki . However, since the transfer rate increases with the priority, for any time interval where the transfer of the data produced by t jl preempts that produced by t ki , data is being transferred to the mass memory at a higher rate. Thus, advancing a data-producing activity t ji of higher priority never helps minimizing the mass memory usage.

Given a visibility cycle V = (a, v, b), we can therefore get a lower bound on m t 0 on the usage of the mass memory for any t in the interval [a, b] using the sweep algorithm. For every task in Ω(V), we tentatively fix it to its latest start time and execute the sweep algorithm. Hence, we can easily compute t, the smallest value of t for which m t 0 = m v 0 . Given an experiment E k . We can bound the amount of data that can be produced by any task of this experiment in the period [t, v] and stored without loss. There are m t blocks of data already on the mass-memory, so M 0 -m t 0 is free. Moreover, up to M k can be stored on the experiment's own memory, for a total of δ k = M 0 + M k -m t 0 blocks. Above this threshold, data produced by activities of experiment E k between t and v will be lost.

|t ki ∩ [t, v]| ≤ (δ k - j =i∈[1,n] (min(|t kj ∩ [t, v]|) * π kj ))/π ki (8)
We run the sweep algorithm once to obtain the value of t. Then, for each experiment, we can compute δ k and in time O(n) the values of min(|t kj ∩[t, v]| for each activity t ki . Finally we compute the implied constraint also in time O(n) (it takes constant time for each activity, once min(|t kj ∩[t, v]| is known). Finally we apply it only when it collapses to a simple lower or upper bound on the start time s ki of an activity t ki . The total time complexity of this filtering rule is thus O(nm log(nm) + nm) = O(nm log(nm)).

Experimental Results

All the previous algorithms and filtering rules have been implemented on the latest version of MOST. We ran experimentations on different scenarios provided by the group SONC of CNES. Each scenario consists in one, two or three experiments which must be scheduled on a time window between 10 hours and 1 day. For each subset of experiments, several variations are tested in order to assess uncertain parameters. For instance, the visibility cycle depends on the exact mass and shape of the comet, the orbit selected by Rosetta, and the landing site chosen for Philae, all of which are unknown. Some scenarios have continuous visibility, while other have different periods for the visibility cycles. The hardware onboard the probe will have travelled in extreme temperatures for ten years, so the exact charge and efficiency of the batteries is also uncertain. Moreover, engineers of SONC test a range of variations on other parameters such as the memory capacity simply to stress-test the system (MOST).

Search effort

We ran 8 scenarios and compared the results of the current version of MOST against the ad-hoc propagator introduced in this paper. Both were run on quad-core Sun T 5120 running Solaris 2.10 with 8GB of RAM. The current version of MOST (denoted MOST+ILCRESERVOIR) models data transfers using Ilog-Scheduler ILCRESERVOIR constraints. In our version (denoted MOST+DATATRANSFER) we use only the first filtering rule described in Section 4.2. 4We report the results in Table 1. We present for each scenario the set of experiments involved, the memory capacities, and whether the visibility is continuous or not. Then We observe first that using our approach, solutions can be obtained without any fail, whereas the previous model explored a much larger search tree. The reformulation using ILCRESERVOIR constraints was indeed very loose, and did not allow to detect inconsistencies early. Moreover, to overcome this weakness, the scenarios produced by the group SONC are overly constrained in order to cut possibilities and allow the solver to converge more easily. Moreover, our propagator is relatively light and therefore more time effective, compared to the model using a large amount of transfer tasks throughout the horizon for each reservoir constraint.

In fact, the model was so large that the initialization time is very high. The few seconds of initialization time in our approach correspond to the rest of the model (cumulative and unary resources) which is common to both implementations.

In two cases, no solution was found by MOST+ILCRESERVOIR within the 600 seconds time cutoff. However, this is not explained (only) by performance issues. In fact, these two scenarios do not have a valid solution under the old model, whereas they are feasible.

A more accurate modeling

In MOST+ILCRESERVOIR, activities with very low data-producing rate are treated differently because of rounding issues: It is assumed that the data is produced all at once at the end of the activity. Therefore in these scenarios, transfers can be delayed by a substantial amount compared to the real behavior of the CDMS.

Moreover, since transfer tasks have a frequency of 120 seconds, they cannot accurately model situations where the CDMS frequently switches between different transfers. The scenario Consert/Romap highlights this problem on SONC's version of MOST. Both experiments have small data-producing activities and small memory capacities. Therefore, switches between transfers from these two experiments are extremely frequent. However, with MOST+ILCRESERVOIR it is not possible to switch frequently enough, hence there is no solution.

Figure 5 is a screenshot of the MOST's GUI showing a zoom on a plan (a solution) of the scenario SD2/Ptolemy. The bottom bars represents the transfer of Ptolemy, and the bars just above are data-producing activities. We can see that the transfer task does Fig. 5: Example of MOST+ILC-RESERVOIR not coincide with the data-producing. Indeed there is a gap, because data-producing rate is too low to trigger a transfer task earlier.

Conclusion

In this paper we have presented an application of constraint programming for the international spatial mission ROSETTA/PHILAE. We have identified that the main problem is the management of data transfers and in particular, data loss. We shown that the previous constraint programming approach was not well-adapted to this problem and we introduced a global constraint to forbbid data-loss. In particular we proposed an efficient sweep algorithm which checks and computes the feasibility of data transfers. We also have presented two propagation rules for the data transfer constraint. Overall, our approach greatly improves the results both for computing times, and accuracy of the solutions.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Example of exact data transfer

π ki p ki -M k τ en s1 Fig. 4 :

 s14 Fig. 4: Example of minimal span constraint.

  If |t ki ∩ [t, v]| stands for the length of the overlap between an activity t ki and the interval [t, v], an activity t ki produces |t ki ∩ [t, v]| * π ki blocks of data in the interval [t, v]. Therefore, the following relation must hold: n i=1 (min(|t ki ∩ [t, v]|) * π ki ) ≤ δ k from which we can deduce the following implied constraint:

Table 1 :

 1 Old vs. new version of MOST on 8 standard scenarios we give the number of fails calculated by Ilog-Scheduler during search, the initialization time and finally the solving time.

	Scenario	Parameters		MOST+ILC-RESERVOIR	MOST +DATATRANSFER
		M k	M0	Visi.	Fail Init. time Search time Fail Init. time Search time
	Consert	500	17456 Periodic 295	4, 06	20, 07	0	0, 88	0, 08
	Consert/Romap	500/250	17456 Periodic 7112 11, 13 Time out 0	1, 17	0, 1
	Consert/Romap	500/250	37456 Periodic 7051 11, 03 Time out 0	1, 17	0, 1
	SD2/Ptolemy	64/2000	17456 Periodic 234 26, 71	41, 72	0	3, 37	0, 09
	SD2/Ptolemy	64/2000	17456 Continuous 211 32, 78	79, 48	0	3, 25	0, 08
	SD2/Cosac/Civa 64/24000/4000 37456 Periodic 407 50, 20	181, 91	0	2, 75	0, 14
	SD2/Cosac/Civa 64/24000/4000 17456 Periodic 413 50, 84	179, 19	0	2, 95	0, 15
	SD2/Cosac/Civa 64/24000/4000 17456 Continuous 390 25, 12	91, 08	0	1, 82	0, 10

European Space Agency

Centre National d'Etudes Spatiales

To simplify the notations, we assume that all experiments have the same number of activities. This is of course not the case, however it does not affect the methods we introduce.

The second filtering rule was not implemented when the experiments were run.


Mohamed Siala
email: siala@laas.fr

Emmanuel Hebrard
email: hebrard@laas.fr

Marie-José Huguet
email: huguet@laas.fr

An Optimal Arc Consistency Algorithm for a Chain of Atmost Constraints with Cardinality

, two algorithms designed for the AMONGSEQ constraint were adapted to this constraint with a O(2 q n) and O(n 3 ) worst case time complexity, respectively. In [10], another algorithm with a O(n 2 log n) worst case time complexity and similarly adaptable to filter ATMOSTSEQCARD in O(n log n) was proposed. In this paper, we introduce an algorithm for achieving Arc Consistency on the ATMOSTSEQCARD constraint with a O(n) (hence optimal) worst case time complexity. We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problems.

Introduction

In many applications there are restrictions on the successions of decisions that can be taken. Some sequences are allowed or preferred while other are forbidden. For instance, in crew-rostering applications, it is often not recommended to have an employee work on an evening or a night shift and then again on the morning shift of the next day.

. This constraint ensures that all subsequences of size q have at least l but no more than u values in a set v. This constraint is often applied to car-sequencing and crew-rostering problems. However, the constraints in these two benchmarks do not correspond exactly to this definition. Indeed, there are often no lower bound restriction on the number of values (l = 0). Instead, the number of values in the set v is often constrained by an overall demand.

In this paper we consider the constraint ATMOSTSEQCARD. This constraint, posted on n variables x 1 , . . . , x n , ensures that, in every subsequence of length q, no more than u are set to a value in a set v, and that over all the sequence, exactly d are set to values in v. In car-sequencing, this constraint allows to state that given an option, no subsequence of length q can involve more than u classes of cars requiring this option, and that exactly d cars require it overall. In crew-rostering problems, one can state, for instance, that a worker must have at least a 16h break between two 8h shifts, or that a week should not involve more than 40h of working time, while enforcing a total number of worked hours over the scheduling period.

The rest of the paper is organized as follows: In Section 2 we give a brief state of the art of the sequence constraints. Then in Section 3, we give a linear time (hence optimal) algorithm for filtering this constraint. Last, in Section 4 we evaluate our new propagator on car-sequencing benchmarks, before concluding in Section 5.

CSP and SEQUENCE Constraints

A constraint satisfaction problem (CSP) is a triplet P = (X , D, C) where X is a set of variables, D is a set of domains and C is a set of constraints that specify allowed combinations of values for subsets of variables. We denote by min(x) and max(x) the minimum and maximum values in D(x), respectively. An assignment of a set of variables X is a tuple w, where w[i] denotes the value assigned to the variable x i . A constraint C ∈ C on a set of variables X defines a relation on the domains of variables in X . An assignment w is consistent for a constraint C iff it belongs to the corresponding relation. A constraint C is arc consistent (AC) iff, for every value j of every variable x i in its scope there exists a consistent assignment w such that w[i] = j, i.e., a support.

There are several variants of the SEQUENCE constraints, we first review them and then motivate the need for the variant proposed in this paper: ATMOSTSEQCARD. In the following definitions, v is a set of integers and l, u, q are integers. Sequence constraints are conjunctions of AMONG constraints, constraining the number of occurrences of a set of values in a set of variables. Definition 1. AMONG(l, u, [x 1 , . . . , x q ], v) ⇔ l ≤ |{i | x i ∈ v}| ≤ u Chains of AMONG Constraints: The AMONGSEQ constraint, first introduced in [START_REF] Beldiceanu | Introducing Global Constraints in CHIP[END_REF], is a chain of AMONG constraints of width q slid along a vector of n variables. Definition 2. AMONGSEQ(l, u, q, [x 1 , . . . , x n ], v) ⇔ n-q i=0 AMONG(l, u, [x i+1 , . . . , x i+q ], v) The first (incomplete) algorithm for filtering this constraint was proposed in 2001 [START_REF] Beldiceanu | Revisiting the Cardinality Operator and Introducing the Cardinality-Path Constraint Family[END_REF]. Then in [START_REF] Van Hoeve | Revisiting the Sequence Constraint[END_REF][START_REF] Van Hoeve | New Filtering Algorithms for Combinations of Among Constraints[END_REF], two complete algorithms for filtering the AMONGSEQ constraint were introduced. First, a reformulation using the REGULAR constraint using 2 q-1 states and hence achieving AC in O(2 q n) time. Second, an algorithm achieving AC with a worst case time complexity of O(n 3 ). Moreover, this last algorithm is able to handle arbitrary sets of AMONG constraints on consecutive variables (denoted GEN-SEQUENCE), however in O(n 4 ). Last, a flow-based algorithm achieving AC in O(n 2 ) was introduced in [START_REF] Maher | Flow-Based Propagators for the SEQUENCE and Related Global Constraints[END_REF]. Here again, the algorithm can be adapted, using more general linear programming tools to handle the GEN-SEQUENCE constraint in O(n 2 log n) in the worst case.

Chain of ATMOST Constraints: Although useful in both applications, the AMONGSEQ constraint does not model exactly the type of sequences useful in car-sequencing and crew-rostering applications.

First, there is often no lower bound for the cardinality of the sub-sequences, i.e., l = 0. Therefore AMONGSEQ is unnecessarily general in that respect. Moreover, the capacity constraint on subsequences is often paired with a cardinality requirement.

For instance, in car-sequencing, classes of car requiring a given option cannot be clustered together because a working station can only handle a fraction of the cars passing on the line (at most u times in any sequence of length q). The total number of occurrences of these classes is a requirement, and translates as an overall cardinality constraint rather than lower bounds on each sub-sequence.

In crew-rostering, allowed shift patterns can be complex, hence the REGULAR constraint is often used to model them. However, working in at most u shifts out of q is a useful particular case. If days are divided into three 8h shifts, ATMOSTSEQ with u = 1 and q = 3 makes sure that no employee work more than one shift per day and that there must be a 24h break when changing shifts. Moreover, similarly to car-sequencing, the lower bound on the number of worked shifts is global (monthly, for instance).

In other words, we often have a chain of ATMOST constraints, defined as follows:

Definition 3. ATMOST(u, [x 1 , . . . , x q ], v) ⇔ AMONG(0, u, [x 1 , . . . , x q ], v) Definition 4. ATMOSTSEQ(u, q, [x 1 , . . . , x n ], v) ⇔ n-q i=0 ATMOST(u, [x i+1 , . . . , x i+q ],
v) However, it is easy to maintain AC on this constraint. Indeed, the ATMOST constraint is monotone, i.e., the set of supports for value 0 is a super-set of the set of supports for value 1. Hence a ATMOSTSEQ constraint is AC iff each ATMOST is AC [START_REF] Bessiere | Slide: A Useful Special Case of the Cardpath Constraint[END_REF].

A good tradeoff between filtering power and complexity can be achieved by reasoning about the total number of occurrences of values from the set v together with the chain of ATMOST constraints. 1 We therefore introduce the ATMOSTSEQCARD constraint, defined as the conjunction of an ATMOSTSEQ with a cardinality constraint on the total number of occurrences of values in v:

Definition 5. ATMOSTSEQCARD(u, q, d, [x 1 , . . . , x n ], v) ⇔ ATMOSTSEQ(u, q, [x 1 , . . . , x n ], v) ∧ |{i | x i ∈ v}| = d
The two AC algorithms introduced in [START_REF] Van Hoeve | Revisiting the Sequence Constraint[END_REF] were adapted in [START_REF] Van Hoeve | New Filtering Algorithms for Combinations of Among Constraints[END_REF] to achieve AC on the ATMOSTSEQCARD constraint. First, in the same way that AMONGSEQ can be encoded with a REGULAR constraint, ATMOSTSEQCARD can be encoded with a COST-REGULAR constraint, where the cost stands for the overall demand, and it is increased on transitions labeled with the value 1. This procedure has the same worst case time complexity, i.e., O(2 q n). Second, the more general version of the polynomial algorithm (GEN-SEQUENCE) is used, to filter the following decomposition of the ATMOSTSEQCARD constraint into a conjunction of AMONG:

ATMOSTSEQCARD(u, q, d, [x 1 , . . . , x n ], v) ⇔ n-q i=0 AMONG(0, u, [x i+1 , . . . , x i+q ], v) ∧ AMONG(d, d, [x 1 , . . . , x n ], v)
Since the number of AMONG constraints is linear, the algorithm of van Hoeve et al. Global Sequencing Constraint: Finally, in the particular case of car-sequencing, not only we have an overall cardinality for the values in v, but each value corresponds to a class of car and has a required number of occurrences. Therefore, Puget and Régin proposed to consider the conjunction of a AMONGSEQ and a GCC constraint. Let c l and c u be two mapping on integers such that c l (j) ≤ c u (j) ∀j, and let D = n i=1 D(x i ). The Global Cardinality Constraint (GCC) is defined as follows:

Definition 6. GCC(c l , c u , [x 1 , . . . , x n ]) ⇔ j∈D c l (j) ≤ |{i | x i = j}| ≤ c u (j)
The Global Sequencing Constraint is defined as follows:

Definition 7. GSC(l, u, q, c l , c u , [x 1 , . . . , x n ], v) ⇔ AMONGSEQ(l, u, q, [x 1 , .., x n ], v) ∧ GCC(c l , c u , [x 1 , .., x n ])
The mappings c l and c u are defined so that for a value v, both c l (v) and c u (v) map to the number of occurrences of the corresponding class of car. A reformulation of this constraint into a set of GCC constraints was introduced in [START_REF] Régin | A Filtering Algorithm for Global Sequencing Constraints[END_REF]. However, achieving AC on this constraint is NP-hard [START_REF] Bessiere | The Slide Meta-Constraint[END_REF]. In fact, so is achieving bounds consistency. 2 3 The ATMOSTSEQCARD Constraint

In this section we introduce a linear filtering algorithm for the ATMOSTSEQCARD constraint. We first give a simple greedy algorithm for finding a support with a O(nq) time complexity. Then, we show that one can use two calls to this procedure to enforce AC. Last, we show that its worst case time complexity can be reduced to O(n).

It was observed in [START_REF] Van Hoeve | New Filtering Algorithms for Combinations of Among Constraints[END_REF] and [START_REF] Maher | Flow-Based Propagators for the SEQUENCE and Related Global Constraints[END_REF] that we can consider Boolean variables and v = {1}, since the following decomposition of AMONG (or ATMOST) does not hinder propagation as it is Berge-acyclic [START_REF] Brand | Encodings of the Sequence Constraint[END_REF]:

AMONG(l, u, [x 1 , . . . , x q ], v) ⇔ q i=1 (x i ∈ v ↔ x i = 1) ∧ l ≤ q i=1 x i ≤ u
Therefore, throughout the paper, we shall consider the following restriction of the ATMOSTSEQCARD constraint, defined on Boolean variables, and with v = {1}:

Definition 8. ATMOSTSEQCARD(u, q, d, [x 1 , . . . , x n ]) ⇔ n-q i=0 ( q l=1 x i+l ≤ u) ∧ ( n i=1 x i = d)
2 Comics note, Nina Narodytska.

Finding a Support

Let w be an n-tuple in {0, 1} n , w[i] denotes the i th element of w, |w| = n i=1 w[i] its cardinality, and w[i : j] the (|j -i| + 1)-tuple equal to w on the sub-sequence [x i , . . . , x j ].

We first show that one can find a support by greedily assigning variables in a lexicographical order to the value 1 whenever possible, that is, while taking care of not violating the ATMOSTSEQ constraint. More precisely, doing so leads to an assignment of maximal cardinality, which may easily be transformed into an assignment of cardinality d. This greedy rule, computing an assignment w maximizing the cardinality of the sequence (x 1 , . . . , x n ) subject to a ATMOSTSEQ constraint (with parameters u and q), is shown in Algorithm 1.

First, the tuple w is initialized to the minimum value in the domain of each variable in Line 1. Then, at each step i ∈ [1, . . . , n] of the main loop, c(j) is the cardinality of the j th subsequence involving the variable x i , i.e. at step i, c(j) = min(n,i+j-1)

l=max(1,i-q+j) w[l].
According to the greedy rule sketched above, we set w

[i] to 1 iff it is not yet assigned (D(x i ) = {0, 1}
) and if this does not violate the capacity constraints, that is, there is no subsequence involving x i of cardinality u or more. This is done by checking the maximum value of c(j) for j ∈ [1, . . . , q] (Condition 2). In that case, the cardinality of every subsequence involving x i is incremented (Line 3). Finally when moving to the next variable, the values of c(j) are shifted (Line 4), and the value of c(q) is obtained by adding the value of w[i + q] and subtracting w[i] to its previous value (Line 5). From now on, we shall denote -→ w the assignment found by leftmost on the sequence x 1 , . . . , x n . Moreover, we shall denote ←w the assignment found by the same algorithm, however on the sequence x n , . . . , x 1 , that is, right to left. Notice that, in order to simplify the notations, ←w [i] shall denote the value assigned by leftmost to the variable x i , and not x n-i+1 as it would really be if we gave the reversed sequence as input.

Lemma 1. leftmost maximizes n i=1 x i subject to ATMOSTSEQ(u, q, [x 1 , . . . , x n ]). Proof. Let -→ w be the assignment found by leftmost, and suppose that there exists w another assignment (consistent for ATMOSTSEQ(u, q, [x 1 , . . . ,

x n ])) such that |w| > | - → w |. Let i be the smallest index such that - → w [i] = w[i]. By definition of - → w , we know that - → w [i] = 1 hence w[i] = 0. Now let j be the smallest index such that - → w [j] < w[j] (it must exists since |w| > | - → w |).
We first argue that the assignment w equal to w except that w [i] = 1 and w [j] = 0 (as in -→ w ) is consistent for ATMOSTSEQ. Clearly, its cardinality is not affected by this swap, hence |w | = |w|. Now, we consider all the sum constraints whose scopes are changed by this swap, that is, the sums

a+q-1 l=a w [l] on intervals [a, a + q -1]
such that a ≤ i < a + q or a ≤ j < a + q. There are three cases:

1. Suppose first that a ≤ i < j < a + q: in this case, the value of the sum is the same in w and w , therefore it is lower than or equal to u. 2. Suppose now that i < a ≤ j < a + q: in this case, the value of the sum is decreased by 1 from w to w , therefore it is lower than or equal to u. 3. Last, suppose that a ≤ i < a + q ≤ j: in this case, for any l ∈ [a, a + q -1], we have w

[l] ≤ - → w [l] since j is the smallest integer such that - → w [j] < w[j]
, hence the sum is lower than or equal to u.

Algorithm 1: Therefore, given a sequence w of maximum cardinality and that differs with -→ w at rank i, we can build one of equal cardinality and that does not differs from -→ w until rank i + 1. By iteratively applying this argument, we can obtain a sequence identical to -→ w , albeit with cardinality |w|, therefore contradicting our hypothesis that |w| > | -→ w |.

leftmost count ← 0; 1 foreach i ∈ [1, . . . , n] do w[i] ← min(xi); foreach i ∈ [1, . . . , q] do w[n + i] ← 0; c(1) ← w[1]; foreach j ∈ [2, . . . , q] do c(j) ← c(j -1) + w[j]; foreach i ∈ [1, . . . , n] do 2 if |D(xi)| > 1 & max j∈[1,q] (c(j)) < u then w[i] ← 1; count ← count + 1; 3 foreach j ∈ [1, . . . , q] do c(j) ← c(j) + 1; 4 foreach j ∈ [2, . . . , q] do c(j -1) ← c(j); 5 c(q) ← c(q -1) + w[i + q] -w[i]; return w; xi w c max 1 2 3 4 . 1 0 0 0 1 1 0 0 1 1 2 1 2 . 0 1 2 1 1 2 1 1 2 1 1 1 2 . 1 1 1 1 0 1 . 0 2 2 1 0 2 . 0 2 1 0 0 2 0 0 1 0 0 1 1 . 1 0 0 1 1 1 0 0 0 2 2 1 2 1 1 2 2 1 2 2 . 0 2 1 2 1 2 . 0 1 2 1 1 2 1 1 2 1 1 1 2 . 1 1 1 1 0 1 . 0 2 2 1 0 2
Corollary 1. Let -→ w be the assignment returned by leftmost. There exists a solution of ATMOSTSEQCARD(u, q, d, [x 1 , . . . , x n ]) iff the three following propositions hold:

(1) ATMOSTSEQ(u, q, [x 1 , . . . ,

x n ]) is satisfiable (2) n i=1 min(x i ) ≤ d (3) | - → w | ≥ d.
Proof. It is easy to see that these conditions are all necessary: (1) and ( 2) come from the definition, and (3) is a direct application of Lemma 1. Now we prove that they are sufficient by showing that if these properties hold, then a solution exists. Since ATMOSTSEQ(u, q, [x 1 , . . . , x n ]) is satisfiable, -→ w does not violate the chain of ATMOST constraints as the value 1 is assigned to x i only if all subsequences involving x i have cardinality u -1 or less. Moreover, since

n i=1 min(x i ) ≤ d there are at least | - → w | -d variables such that min(x i ) = 0 and - → w [i] = 1.
Assigning them to 0 does not violate the ATMOSTSEQ constraint, hence there exists a support. Lemma 1 and Corollary 1 give us a polynomial support-seeking procedure for ATMOSTSEQCARD. Indeed, the worst case time complexity of Algorithm 1 is in O(nq). There are n steps and on each step, Lines 2, 3 and 4 involve O(q) operations. Therefore, for each variable x i , a support for x i = 0 or x i = 1 can be found in O(nq).

Consequently we have a naive AC procedure running in O(n 2 q) time.

Filtering the Domains

In this section, we show that we can filter out all the values inconsistent with respect to the ATMOSTSEQCARD constraint within the same time complexity as Algorithm 1.

First, we show that there can be inconsistent values only in the case where the cardinality | -→ w | of the assignment returned by leftmost is exactly d: in any other case, the constraint is either violated (when

| - → w | < d) or AC, (when | - → w | > d).
The following proposition formalises this: Consider a subsequence x j , . . . , x j+q-1 . If j + q ≤ i or j > i then j+q-1 l=j w [l] ≤ j+q-1 l=j w[l] ≤ u, so only indices j s.t. j ≤ i < j + q matter. There are two cases:

Proposition 1. The constraint ATMOSTSEQCARD(u, q, d, [x 1 , . . . , x n ]) is AC if the three following propositions hold: (1) ATMOSTSEQ(u, q, [x 1 , . . . , x n ]) is AC (2) n i=1 min(x i ) ≤ d (3) | - → w | > d Proof.
1. Either a or b or both are in the sub-sequence (j ≤ a < j + q or j ≤ b < j + q). In that case

i+q-1 l=j w [l] ≤ i+q-1 l=j w[l]. 2.
Neither a nor b are in the sub-sequence (a < j and j + q ≤ b). In that case, since D(x i ) = {0, 1} and since condition (1) holds, we know that i+q-1 l=j min(x l ) < u. Moreover, since a < j and j + q ≤ b, there is no variable x l in that sub-sequence such that w[l] = 1 and 0 ∈ D(x l ). Therefore, we have

i+q-1 l=j w[l] < u, hence i+q-1 l=j w [l] ≤ u.
In both cases w satisfies all capacity constraints.

Remember that achieving AC on ATMOSTSEQ is trivial since AMONG is monotone. Therefore we focus of the case where ATMOSTSEQ is AC, and | -→ w | = d. In particular, Propositions 2, 3, 4 and 5 only apply in that case. The equality | -→ w | = d is therefore implicitly assumed in all of them. By Lemma 1 on the sequence x 1 , . . . , x i-1 we know that

Proposition 2. If | - → w [1 : i -1]| + | ← - w [i + 1 : n]| < d then x i = 0 is not AC. Proof. Suppose that we have | - → w [1 : i -1]|+| ← - w [i + 1 : n]| < d
i-1 l=1 w[l] ≤ | - → w [1 : i -1]|.
By Lemma 1 on the sequence x n , . . . , x i+1 we know that

n l=i+1 w[l] ≤ | ← - w [i + 1 : n]|. Therefore, since w[i] = 0, we have |w| = n l=1 w[l] < d, thus contradicting the that |w| = d.
Hence, there is no support for x i = 0.

Proposition 3. If | - → w [1 : i]| + | ← - w [i : n]| ≤ d then x i = 1 is not AC.
Proof. Suppose that we have By Lemma 1 on the sequence x 1 , . . . , x i we know that

| - → w [1 : i]| + | ← - w [i : n]| ≤ d
i l=1 w [l] ≤ | - → w [1 : i]|.
By Lemma 1 on the sequence x n , . . . , x i we know that

n l=i w [l] ≤ | ← - w [i : n]|. Therefore, since w [i] = 1, we have |w | = i l=1 w [l] + n l=i w [l] -1 < d,

. , n]

are similarly computed by simply running the same procedure on the same sequence of variables, however reversed, i.e., from right to left. Using these values, one can then apply Proposition 2 and Proposition 3 to filter out the value 0 and 1, respectively. We detail this procedure in the next section.

We first show that these two rules are complete, that is, if ATMOSTSEQ is AC, and the overall cardinality constraint is AC then an assignment x i = 0 (resp. x i = 1) is inconsistent iff Proposition 2 (resp. Proposition 3) applies. The following Lemma shows that the greedy rule maximises the density of 1s on any subsequence starting on x 1 , and therefore minimises it on any subsequence finishing on x n . Let leftmost(k) denote the algorithm corresponding to applying leftmost, however stopping whenever the cardinality of the assignment reaches a given value k.

Lemma 2. Let w be a satisfying assignment of ATMOSTSEQ(u, q, [x 1 , . . . , x n ]). If k ≤ |w| then the assignment -→ w k computed by leftmost(k) is such that, for any

1 ≤ i ≤ n: n l=i - → w k [l] ≤ n l=i w[l].
Proof. Let m be the index at which leftmost(k) stops. We distinguish two cases.

If i > m, for any value l in [m + 1, . . . , n], - → w k [l] ≤ w[l] (since - → w k [l] = min(x l )), hence n l=i - → w k [l] ≤ n l=i w[l]. When i ≤ m, clearly for i = 1, n l=i - → w k [l] ≤ n l=i w[l] since | - → w k | ≤ |w|. Now consider the case of i = 1. Since | - → w k | ≤ |w|, then n l=i - → w k [l] ≤ |w| - i-1 l=1 - → w k [l]. Thus, n l=i - → w k [l] ≤ n l=i w[l] + ( i-1 l=1 w[l] - = = ≥ - → w 1 0 0 . . . 0 - → w L-1 0 0 0 . . . 1 ← - w d-L 0 0 . . . 0 ← - w d-L+1 0 0 0 . . . 1 xi xa x b L -1 d -L + 1
Fig. 3: Illustration of Proposition 5's proof. Horizontal arrows represent assignments.

i-1 l=1

- → w k [l]
). Moreover, by applying Lemma 1, we show that

i-1 l=1 - → w k [l] is maxi- mum, hence larger than or equal to i-1 l=1 w[l]. Therefore, n l=i - → w k [l] ≤ n l=i w[l]. Proposition 4. If ATMOSTSEQ(u, q, [x 1 , . . . , x n ]) is AC, and | - → w [1 : i -1]|+| ← - w [i + 1 : n]| ≥ d then x i = 0 has a support.
Proof. Let -→ w be the assignment found by leftmost. We consider, without loss of generality, a variable

x i such that D(x i ) = {0, 1} and | - → w [1 : i -1]| + | ← - w [i + 1 : n]| ≥ d and show that one can build a support for x i = 0. If - → w [i] = 0 or ← - w [i] = 0
then there exists a support for x i = 0, hence we only need to consider the case where

- → w [i] = ← - w [i] = 1. Let L = | - → w [1 : i -1]
|, and let ←w d-L be the result of leftmost(d-L) on the subsequence x n , . . . , x i . We will show that w, defined as the concatenation of -

→ w [1 : i -1]
and ← -

w d-L [i : n] is a support for x i = 0. First, we show that w[i] = 0, that is ← - w d-L [i] = 0. By hypothesis, since | - → w [1 : i -1]|+ | ← - w [i + 1 : n]| ≥ d, we have | ← - w [i + 1 : n]| ≥ d -L
. Now consider the sequence x i , . . . , x n , and let w be the assignment such that w [i] = 0, and w = ← -

w [i + 1 : n] otherwise. Since |w | = | ← - w [i + 1 : n]| ≥ d -L
, by Lemma 2, we know that w has a higher cardinality than ←w d-L on any subsequence starting in i, hence w

[i] = ← - w d-L [i] = w [i] = 0.
Now we show that w does not violate the ATMOSTSEQ constraint. Obviously, since it is the concatenation of two consistent assignments, it can violate the constraint only on the junction, i.e., on a sub-sequence x j , . . . , x j+q-1 such that j ≤ i and i < j + q.

We show that the sum of any such subsequence is less or equal to u by comparing with -→ w , as illustrated in Figure 2. We have

j+q-1 l=j - → w [l] ≤ u, and i-1 l=j - → w [l] = i-1 l=j w[l]. Moreover, by Lemma 2, since | - → w [i : n]| = | ← - w d-L | = d -L we have j+q-1 l=i ← - w d-L [l] ≤ j+q-1 l=i - → w [l] hence j+q-1 l=i w[l] ≤ j+q-1 l=i - → w [l]. Therefore, we can conclude that j+q-1 l=j w[l] ≤ u. Proposition 5. If ATMOSTSEQ(u, q, [x 1 , . . . , x n ]) is AC, |w[1 : i]| + |w[n : i]| > d then x i = 1 has a support.
Proof. Let -→ w and ←w be the assignments found by leftmost, on respectively x 1 , . . . , x n and x n , . . . , x 1 . We consider, without loss of generality, a variable

x i such that D(x i ) = {0, 1} and | - → w [1 : i]| + | ← - w [i : n]| > d and show that one can build a support for x i = 1. If - → w [i] = 1 or ← - w [i] = 1
then there exists a support for x i = 1, hence we only need to consider the case where -→ w

[i] = ← - w [i] = 0. Let L = | - → w [1 : i]| = | - → w [1 : i -1]| (this equality holds since - → w [i] = 0). Let - → w L-1
be the assignment obtained by using leftmost(L -1) on the subsequence x 1 , . . . , x i-1 , and let ←w d-L be the assignment returned by leftmost(d -L) on the subsequence x n , . . . , x i+1 .

We show that w such that w[i] = 1, equal to -→ w L-1 on x 1 , . . . , x i-1 and to ←w d-L on x i+1 , . . . , x n , is a support.

Clearly |w| = d, therefore we only have to make sure that all capacity constraints are satisfied. Moreover, since it is the concatenation of two consistent assignments, it can violate the constraint only on the junction, i.e., on a sub-sequence x j , . . . , x j+q-1 such that j ≤ i and i < j + q.

We show that the sum of any such subsequence is less or equal to u by comparing with -→ w and ←w d-L (see Figure 3). First, observe that on the subsequence x 1 , . . . , x i-1 , -→ w L-1 = -→ w , except for the largest index a such that -→ w [a] = 1 and w[a] = 0. Similarly on x n , . . . , x i+1 , we have ← -

w d-L = ← - w d-L+1 , except for the smallest b such that ← - w d-L+1 [b] = 1.
There are two cases:

Suppose first that j > a. In that case,

j+q-1 l=j w[l] = j+q-1 l=i ← - w d-L+1 [l] if j + q -1 ≥ b,
and otherwise it is equal to 1. It is therefore alway less than or equal to u since i ≥ j (and we assume u ≥ 1). Now suppose that j ≤ a. In that case, consider first the subsequence x j , . . . , x i . On this interval, the cardinality of w is the same as that of -→ w , i.e.,

i l=j w[l] = i-1 l=j - → w L-1 [l] + 1 = i l=j - → w [l].
On the subsequence x i+1 , . . . , x j+q-1 , observe that

|w[i + 1 : n]| = | - → w [i + 1 : n]| = d -L,

Algorithmic Complexity

Using Propositions 2, 3, 4 and 5 one can design a filtering algorithm with the same worst case time complexity as leftmost. In this section, we introduce a linear time implementation of leftmost, denoted leftmost count, that returns the values of -→ w [1 : i] for all values of i (Algorithm 2).

It is easy to see that leftmost count has a O(n) worst case time complexity. In order to prove its correctness, we will show that the assignment computed by leftmost count is the same as that computed by leftmost.

Proof (sketch). We only sketch the proof here. The following three invariants are true at the beginning of each step i of the main loop:

-The cardinality of the j th sub-sequence is given by c[(i+j -2) mod q]+count[i-1]. -The number of sub-sequences of cardinality k is given by occ

[n -count[i -1] + k].
-The cardinality maximum of any sub-sequence is given by max c.

1 st invariant: The value of c[j] is updated in two ways in leftmost. First, at each step of the loop the values in c [START_REF] Beldiceanu | Revisiting the Cardinality Operator and Introducing the Cardinality-Path Constraint Family[END_REF] through to c[q] are shifted to the left. Therefore,

Car-sequencing

In the car-sequencing problem [START_REF] Dincbas | Solving the Car-Sequencing Problem in Constraint Logic Programming[END_REF][START_REF] Solnon | The car sequencing problem : Overview of state-of-the-art methods and industrial case-study of the ROADEF'2005 challenge problem[END_REF], n vehicles have to be produced on an assembly line, subject to capacity and demand constraints.

We use a standard model, implemented in Ilog-Solver. We have n integer variables standing for the class of vehicles in each slot of the assembly line and nm boolean variables y j i standing for whether the vehicle in the i th slot requires option j. The demand for each class is enforced with a GCC [START_REF] Régin | Generalized Arc Consistency for Global Cardinality Constraint[END_REF]. We compare four models for the capacity constraints coupled with the demand on each option (derived from the demand on classes). In the first model (sum) a simple decomposition into a chain of sum constraints plus an extra sum for the demand is used. In the second (gsc), we use one GSC constraint per option. In the third, (amsc), we use the AC procedure introduced in this paper for the ATMOSTSEQCARD constraint. Finally, in the fourth (amsc+gsc) we combine the GSC constraint with our filtering algorithm.

We use 34 different heuristics, obtained by combining different ways of exploring the assembly line either in lexicographic order or from the middle to the sides); of branching on affectation of a class to a slot or of an option to a slot; of selecting the best class or option among a number of natural criteria (such as maximum demand, minimum u/q ratio, as well as other criteria described in or derived from [START_REF] Boivin | Résolution du Problème de Car-sequencing à l'Aide d'une Approche de Type FC[END_REF][START_REF] Smith | Succeed-first or Fail-first: A Case Study in Variable and Value Ordering[END_REF]).

We use benchmarks available in the CSPLib [START_REF] Gent | Csplib: a benchmark library for constraints[END_REF] divided into four sets of respectively 70, 4, 5 and 7 instances ranging from 100 to 400 cars. Instances of the third set are all unsatisfiable all other are satisfiable.

The results are given in Table 1. In all cases, the best number of solved problems is obtained either by amsc+gsc (for small or unsatisfiable instances), or by amsc alone (for larger instances of set2 and set4). Overall, we observe that the GSC constraint allows to prune much more values than ATMOSTSEQCARD. However, it slows down the search by a substantial amount (we observed a factor 12.5 on the number of nodes explored per second). Moreover, the amounts of filtering obtained by these two methods are incomparable. Therefore combining them is always better than using GSC alone.

In [START_REF] Van Hoeve | New Filtering Algorithms for Combinations of Among Constraints[END_REF] the authors applied their method to set1, set2 and set3 only. For their experiments, they considered the best result provided by 2 heuristics (σ and min domain). When using COST-REGULAR or GEN-SEQUENCE filtering alone, 50.7% of problems are solved and when combining either COST-REGULAR or GEN-SEQUENCE with GSC, 65.2% of problems are solved (with a time out of 1 hour). In our experiments, in average over the 34 heuristics and the 5 re-starts, ATMOSTSEQCARD and GSC solve respectively 82.5% and 86.11% of instances and combining ATMOSTSEQCARD with GSC solves 86.36% instances in a time out of 20 minutes.

Crew-rostering

In the crew-rostering problem, working shifts have to be attributed to employees over a period, so that there is enough employee to ensure the required service at any time and working regulations are respected. The latter condition can entail a wide variety of constraints. Previous works [START_REF] Menana | Sequencing and Counting with the multicost-regular Constraint[END_REF] [13] used allowed (or forbidden) patterns to express successive shift constraints. For example, with 3 shifts of 8 hours per day: D (day), E (evening) and N (night), ND can be forbidden since employees need some rest after night shifts. In this paper we consider a simple case involving 20 employees with 3 shifts of 8 hours per days where no employee can work more than one 8h shift per day, no more than 5 days a week, and the break between two worked shifts must be at least 16h. The planning horizon is of 28 days, and each employee must work 34 hours per week in average (17 shifts over the 4 weeks period). We use a model with one Boolean variable e ij for each of the m employees and each of the n shifts stating if employee i works on shift j. The demand d s j on each shift j is enforced through a sum constraint m i=1 e ij = d s j .The other constraints are stated using two ATMOSTSEQCARD constraints per employee, one with ratio u/q = 1/3, another with ratio 5/21, and both with the same demand d = 17 corresponding to 34 hours of work per week. We compare three models. In the first (sum), we use a decomposition in a chain of sum constraints. In the second (gsc), we use the GSC constraint to encode it. Observe that in this case, since the domains are Boolean, the GCC within the GSC constraint is in fact nothing more than a sum. Therefore, it cannot prune more than ATMOSTSEQCARD (however it is stronger than the simple sum decomposition). In the third model (amsc) we use the algorithm presented in this paper.

281 instances were generated, with employee unavailability ranging from from 18% to 46% by increment of 0.1. We partition the instances into three sets, with in the first 126 instances with lowest unavailability (all satisfiable), in the third, the 44 instances with highest unavailability (mostly unsatisfiable), and the rest in the second group.

We used two branching heuristic. In the first we chose the employee with minimum slack, and assign it to its possible shift of maximum demand. In the second we use the same criteria, but select the shift first and then the employee.

We report the results in Table 2. The AC algorithm achieves more filtering than the sum decomposition and the GSC decomposition. However, depending on the heuristic choices and the random seed, the size of the search tree is not always smaller. We observe that our propagator is only marginally slower in terms of nodes explored per second than the sum decomposition and much faster (by a factor 20.4 overall) than GSC.

It is able to solve 15.7% and 16.7% more problems within the 20 minutes cutoff in the "hard" set than the GSC and sum decompositions, respectively.

Conclusion

We introduced a linear optimal algorithm for achieving arc consistency on the constraint ATMOSTSEQCARD. The empirical evaluation on car-sequencing and crew-rostering benchmarks shows that this propagator is useful on these applications.

  (resp. Maher et al) runs in O(n 3 ) (resp. O(n log n)) on this decomposition.

Fig. 1 :

 1 Fig. 1: An algorithm to compute an assignment satisfying ATMOSTSEQ(2, 4, [x1, . . . , xn]) with maximal cardinality (left), and an example of its execution (right). Dots in the first column stand for unassigned variables. The second column shows the computed assignment w, and the next columns show the state of the variables c(1), c(2), c(3) and c(4) at the start of each iteration. The last column stands for the maximum value among c(1), c(2), c(3) and c(4).

  = 1 and D(x a ) = {0, 1} (resp. w[b] = 1 and D(x b ) = {0, 1}). Let w be the assignment such that w [i] = 1, w [a] = 0, w [b] = 0, and w = w otherwise. We have |w | = d, and we show that it satisfies ATMOSTSEQ(u, q, [x 1 , . . . , x n ]).

Fig. 2 :

 2 Fig. 2: Illustration of Proposition 4's proof. Horizontal arrows represent assignments.

  and suppose that there exists an assignment w such that w [i] = 1 and |w | = d.

  thus contradicting the hypothesis that |w | = d. Hence there is no support for x i = 1. Propositions 2 and 3 entail a pruning rule. In a first pass, from left to right, one can use an algorithm similar to leftmost to compute and store the values of | -→ w [1 : i]| for all i ∈ [1, . . . , n]. In a second pass, the values of | ←w [i : n]| for all i ∈ [1, . .

Table 1 :

 1 Evaluation of the filtering methods (averaged over all heuristics)

	Method	set1 (70 × 34 × 5) #sol avg bts time #sol avg bts set2 (4 × 34 × 5) time #sol avg bts set3 (5 × 34 × 5) time #sol avg bts time set4 (7 × 34 × 5)
	sum	8480 231.2K 13.93	95	1.4M 76.60	0	-> 1200	64 543.3K 43.81
	gsc	11218	1.7K 3.60 325 131.7K 110.99	31 55.3K	276.06 140 25.2K 56.61
	amsc	10702 39.1K 4.43 360 690.8K 72.00	16 40.3K	8.62 153 201.4K 33.56
	amsc+gsc 11243	1.2K 3.43 339 118.4K 106.53	32 57.7K	285.43 147 23.8K 66.45

Table 2 :

 2 Evaluation of the filtering methods (averaged over all heuristics)

	Benchmarks	underconstrained (5 × 2 × 126) #sol avg bts max bts time #sol avg bts max bts time #sol avg bts max bts time hard (5 × 2 × 111) overconstrained (5 × 2 × 44)
	sum	1229 110.5K 10.1M 12.72 574 370.7K 13.4M 38.45 272 52.1K	5.7M 5.56
	gsc	1210	6.2K 297.2K 29.19 579 23.5K 433.5K 77.78 276	7.7K	378.9 24.14
	amsc	1237 34.2K	7.5M	5.82 670 213.4K	7.5M 31.01 284 51.3K	7.5M 6.22

This modeling choice is used in[START_REF] Van Hoeve | New Filtering Algorithms for Combinations of Among Constraints[END_REF] on car-sequencing.

foreach i ∈ [0, . . . , n] do count[i] ← 0; c[0] ← w [START_REF] Beldiceanu | Revisiting the Cardinality Operator and Introducing the Cardinality-Path Constraint Family[END_REF];

return count;

The fifth and sixth lines correspond to the application of, respectively, Proposition 2 and 3. Last, the seventh line give the arc consistent closure of the domains.

there is only one really new value. By using the modulo operation, we can update only one of these values. Second, when w[i] takes the value 1, we increment c [START_REF] Beldiceanu | Revisiting the Cardinality Operator and Introducing the Cardinality-Path Constraint Family[END_REF] up to c[q]. Since this happened exactly count[i -1] times at the start of step i, we can simply add count[i -1] to obtain the same value as in leftmost.

2 nd invariant: The data structure occ is a table, storing at index n + k the number of subsequences involving x i with cardinality k for the current assignment w. Therefore, by decrementing the pointer to the first element of the table we in effect shift the entire table. Here again the value of count[i -1], or rather the expression (n -count[i -1]) points exactly to the required starting point of the table.

3 rd invariant: The maximum (or minimum) cardinality (of subsequences involving x i ) can change by a unit at the most from one step to the next. Therefore, when the variable max c needs to change, it can only be incremented (when occ[n -count[i -1] + max c + 1] goes from the value 0 to 1) or decremented (when occ[n -count[i -1] + max c] goes from the value 1 to 0).

Algorithm 3: AC(ATMOSTSEQCARD)

Data: [x1, . . . , xn], u, q, d Result: AC on ATMOSTSEQCARD(u, q, d, [x1, .., xn])

Algorithm 3 computes the AC closure of a constraint ATMOSTSEQCARD(u, q, d, [x 1 , . . . , x n ]). In the first line, the AC closure of ATMOSTSEQ(u, q, [x 1 , . . . , x n ]) is computed. It ensures that the filtering rules introduced in this paper hold. For lack of space, we do not give a pseudo-code for achieving AC on ATMOSTSEQ. However, it can be done in linear time using a procedure similar to leftmost count. We want to compute, for the assignment corresponding to the lower bound of each domain, if an unassigned variable is covered by a subsequence of cardinality u for the lower bounds of the domains. We do it using a truncated version of leftmost count: the values of w[i] are never updated, i.e., they are set to the minimum value in the domain and we never enter the if-then-else block starting at condition 1 in Algorithm 2. Moreover, we store the value of max c for each value of i in a table that we can subsequently use to achieve AC on ATMOSTSEQ, by going through it and assigning 0 to any unassigned variable covered by at least one subsequence of cardinality u.

The remainder is a straight application of Propositions 2, 3, 4 and 5. We give an example of its execution in Figure 4. The worst case time complexity of Algorithm 3 is therefore O(n), hence optimal.

Experimental Results

We tested our filtering algorithm on two benchmarks: car-sequencing and crew-rostering. All experiments ran on Intel Xeon CPUs 2.67GHz under Linux. For each instance, we launched 5 randomized runs with a 20 minutes time cutoff. 3 All models are implemented using Ilog-Solver.

Since we compare propagators, we averaged the results across several branching heuristics to reduce the bias that these can have on the outcome. For each considered data set, we report the total number of successful runs (#sol). Then, we report the CPU time (time) in seconds and number of backtracks (avg bts) both averaged over all successful runs, instances and branching heuristics. Moreover, we report the maximum number of backtracks (max bts) in the same scope. We emphasize the statistics of the best method (w.r.t. #sol) for each data set using bold face fonts.