Djamal Habet
email: djamal.habet@lsis.org

Michel Vasquez
email: michel.vasquez@ema.fr

Yannick Vimont
email: yannick.vimont@ema.fr

Bounding the optimum for the problem of scheduling the photographs of an Agile Earth Observing Satellite

Keywords: Tabu search, Consistent neighborhood, Scheduling, Agile satellite, Dynamic programming

The problem of managing an Agile Earth Observing Satellite consists of selecting and scheduling a subset of photographs among a set of candidate ones that satisfy imperative constraints and maximize a gain function. We propose a tabu search algorithm to solve this NP-hard problem. This one is formulated as a constrained optimization problem and involves stereoscopic and time window visibility constraints; and a convex evaluation function that increases its hardness. To obtain a wide-ranging and an efficient exploration of the search space, we sample it by consistent and saturated configurations. Our algorithm is also hybridized with a systematic search that uses partial enumerations. To increase the solution quality, we introduce and solve a secondary problem; the minimization of the sum of the transition durations between the acquisitions. Upper bounds are also calculated by a dynamic programming algorithm on a relaxed problem. The obtained results show the efficiency of our approach.

Introduction

The mission of an Earth Observing Satellite (EOS) is to acquire photographs on the Earth's surface, in response to observation requests. The management problem of an EOS is to select and to schedule a subset of weighted images among a set of candidate ones which must satisfy imperative constraints and at the same time maximize a given profit function.

The new generation of EOS, like those studied in the French PLEIADES project, are Agile Earth Observing Satellites (AEOS). This means that, while the single onboard camera remains fixed on the satellite, the whole satellite is mobile along three axes (roll, pitch and yaw). This mobility potentially increases the efficiency of the whole system. Indeed, the number of ways of acquiring a given area of the Earth's surface is potentially infinite, since the azimuth and the starting time of a given image acquisition are free. However, managing an AEOS becomes significantly more difficult because the search space is considerably larger.

Both EOS and AEOS management problems are NP-hard [START_REF] Bensana | Earth observation satellite management[END_REF][START_REF] Lemaître | Selecting and scheduling observations of agile satellites[END_REF] and several methods have been proposed to tackle them. Four methods for solving the AEOS management problem were investigated [START_REF] Lemaître | Selecting and scheduling observations of agile satellites[END_REF]: a fast greedy algorithm, a dynamic programming algorithm, a constraint programming method, and a local search algorithm based on the insertion and removal of images in a schedule. The selection and scheduling problem for a non-agile satellite, like SPOT5, is stated in [START_REF] Bensana | Earth observation satellite management[END_REF] and various methods have been used to solve it. The best results are obtained in [START_REF] Vasquez | A logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an Earth observation satellite[END_REF] by using a tabu search algorithm and very good upper bounds are calculated by an original partition method [START_REF] Vasquez | Upper bounds for the SPOT5 daily photograph scheduling problem[END_REF]. A scheduling problem involving a satellite equipped with a radar instrument, very agile on the pitch axis but slow on the roll axis, is stated and solved in [START_REF] Harrison | Task scheduling for satellite based imagery[END_REF] by a partial enumeration algorithm. We will present later more works related to the subject of our interest.

In this paper, we propose a tabu search algorithm to solve the problem of selecting and scheduling the photographs of an AEOS. The search space is based on consistent and possibly saturated configurations. On the one hand, we ensure the consistency of the configurations by propagating efficaciously the problem constraints. In the other hand, the saturation characterizes the optimal solutions. It deals with the fact that it is not possible to improve the quality of a configuration by the selection of a new image and at the same time without the removal of some already selected images. The saturation will be formally defined in Sect. 4.2. During the search, a partial enumeration algorithm is used to solve a large number of decisional problems. Furthermore, we introduce a secondary problem which is the minimization of the sum of the transition durations between two image acquisitions. This problem is handled by a second tabu search algorithm based on exchanging the image orders and also on the inversion of the acquisition direction of the images. Its resolution allows to the first tabu algorithm to improve the quality of the solutions that it produces as it will be explained later. Moreover, we calculate upper bounds by means of a dynamic programming algorithm for a relaxed problem and a linearized objective function. This algorithm is inspired by the work presented in [START_REF] Kohl | An optimization algorithm for the vehicle routing problem with time windows based on Lagrangean relaxation[END_REF] on the Vehicle Routing Problem with Time Windows (VRPTW).

The paper is structured as follows. It starts with a description of the AEOS management problem in Sect. 2. We report the related works on several satellite management problems in Sect. 3. The components of our tabu search algorithm are described in Sect. [START_REF] Cordeau | A unified tabu search heuristic for vehicle routing problems with time windows[END_REF]. The secondary optimization problem is handled in Sect. 5 and the computation method of the upper bounds is explained in Sect. [START_REF] Desrochers | A generalized permanent labelling algorithm or the shortest path problem with time windows[END_REF]. The obtained results are presented and compared in Sect. 7 and Sect. 8 concludes the paper.

AEOS problem description

Earth observing satellites are platforms that orbit the planet and are equipped with optical instruments. Over a period of several days they perform a cycle of orbits of the Earth. Each orbit is phased out with respect to the preceding one but the trajectory is cyclic in the sense that the satellite recovers its initial position after a number of orbits. A full cycle enables the satellite to view each area of the planet. In the course of their mission, satellites take photographs of specific areas of the Earth in function of requests from a number of users including governments, research institutes, and companies. Each request generates a profit or a gain. Typically, the number of requests exceeds what can be feasibly be accomplished during a mission. The problem is to select and schedule a subset of requests yielding a maximal gain, subject to operational constraints. The present work focuses on maximizing the profit associated with a single orbit of the satellite.

A request can either be a target or a polygon. A target consists of a single strip (rectangular shape) whereas a polygon may cover a wide geographical area. Because of their size, polygons cannot usually be photographed in a single shot. For this reason, they are partitioned into strips of equal width but possibly unequal lengths and the time required to acquire a strip is proportional to its length. In the course of a single orbit, the satellite may be able to photograph several strips of the same polygon. Because of its agility, it is also able to acquire a strip using two opposite azimuths (direct and indirect) according to the satellite rotation sense. Hence, two shots (or images) per strip are possibles. The starting date of the acquisition of each shot must be in accordance with its visibility time window. Moreover, some requests are mono while others are stereo. A mono request consists of a single shot of each strip in the polygon. A stereo request consists of two shots of each strip at different angles but in the same direction. A strip from a stereo request is considered to have been acquired only if its twin strip has also been acquired. Finally, for each pair of shots, the satellite requires a minimum transition time to maneuver the camera from the end of the first strip to the start of the second one. Readers interested in a full description of the the AEOS management problem can refer to [START_REF] Lemaître | Selecting and scheduling observations of agile satellites[END_REF].

The input of an AEOS management problem is a set of candidate strips, from the current set of requests, that could be acquired. The problem to be dealt with is twofold: to select a set of strip acquisitions that maximize the total gain, and to order them in time. Formally, the problem can be described as follows [START_REF] Benoist | Upper bounds of the maximal revenue of an Earth observation satellite. 4OR: Q[END_REF]:

Data

A problem with n strips involves 2n possible acquisitions since for each strip i two shooting directions are possibles. These shots are numbered 2i -1 (an odd number for a shot acquired in the direct azimuth) and 2i (an even number for a shot acquired in the indirect azimuth). For each strip i ∈ [1, n] let:

-tw(i) be the index of its stereo twin strip, 0 if i is mono.

d(i) be its shooting duration.

-su(i) be its corresponding surface.

For each shot (image) j ∈ [1, 2n] let:

-es(j ) and ls(j ) be its earliest and latest start dates respectively.

-ee(j ) and le(j ) be its earliest and latest end dates respectively.

For each shot pair (i, j ), i = j ∈ [1, 2n], t (i → j) denotes the minimum transition time between the end of i to the beginning of j . We assume that t (i → j) ≥ es(j )le(i) (otherwise it is obviously underestimated). Four variables are associated to each shot i ∈ [1, 2n]:

x i ∈ {0, 1} equals 1 if and only if shot i is selected.

y 0→i ∈ {0, 1} equals 1 if and only if shot i is the first of the selection.

y i→2n+1 ∈ {0, 1} equals 1 if and only if shot i is the last of the selection.

t i is the shooting start date of i. The value of this variable is irrelevant when x i = 0.

The t i values allow to order and to schedule the shots in time.

Let m be the number of polygons. The kth polygon is characterized by:

s(k) its total area surface.

g k its gain when fully acquired.

p(k) ⊂ [1, 2n] the set of shots that it contains. We recall that each polygon is divided into a set of strips. Moreover, two shots are possibles per strip according to the sense of its acquisition.

Two continuous variables are associated to each polygon k ∈ [1, m]:

-S k ∈ [0, 1] is the percentage of the surface covered by the selected strips.

-G k ∈ [0, 1] is the corresponding percentage of the polygon gain.

Finally, one binary variable is defined for each pair of acquisitions i = j ∈ [1 , 2n]:

y i→j ∈ {0, 1} equals 1 if and only if the shot j is immediately acquired after the shot i.

Constraints

The equations constraining these variables are listed below. The acquisition of the same strip in both directions is forbidden by [START_REF] Benoist | Upper bounds of the maximal revenue of an Earth observation satellite. 4OR: Q[END_REF]. Equation (2) states the stereo constraints: simultaneous selection with identical direction. The time window for the starting time of a shot is imposed by [START_REF] Bensana | Earth observation satellite management[END_REF]. Shooting dates of consecutive images must respect minimum transition times (4). These last two equations correspond to the time constraints.

∀j ∈ [1, n], x 2j -1 + x 2j ≤ 1, (1)
∀j ∈ [1, n], if tw(j ) = 0 then (x 2j -1 = x 2tw(j )-1 and x 2j = x 2tw(j ) ), (2) ∀i ∈ [1, 2n], if x i = 1 then t i ∈ [es(i), ls(i)],
(3)

∀i = j ∈ [1, 2n], t j -t i ≥ (d(i) + t (i → j)) • y i→j + (es(j ) -ls(j )) • (1 -y i→j ). ( 4
)
We denote by C4 the set of shot pairs (i, j ) that satisfy the condition (4). Furthermore, there is at most one first shot and one last shot [START_REF] Desrochers | A new optimization algorithm for the vehicle routing problem with time window[END_REF] and each selected acquisition has exactly one predecessor and one successor [START_REF] Desrochers | A generalized permanent labelling algorithm or the shortest path problem with time windows[END_REF].

i∈ [1, 2n] y 0→i ≤ 1 and i∈ [1, 2n]

y i→2n+1 ≤ 1, ( 5
) ∀i ∈ [1, 2n], j ∈[0, 2n+1] j =i y j →i = x i = j ∈[0, 2n+1] j =i y i→j . ( 6
)
In the rest of this paper, we assume that the constraints ( 5) and ( 6) are always satisfied.

Objective function

The criterion to maximize is a global gain G defined by the sum of the gains associated to the complete or partial acquisition of each polygon k and formulated by:

G = m k=1 g k × G k such as: -∀k ∈ [1, m], S k = 1 s(k) i∈p(k) su(i) • x i . -G k = f (S k ). -f : [0, 1] → [0, 1]
is a non-linear function, piecewise linear and defined by the points {(0, 0), (0.4, 0.1), (0.7, 0.4), (1, 1)}.

In order to tackle quickly the problem of selecting and scheduling photographs for an AEOS, the local search methods seem highly appropriate and we chose a Tabu Search (TS) metaheuristic [START_REF] Glover | Tabu Search[END_REF]. Our TS algorithm is inspired by a tabu resolution methodology, presented in [START_REF] Vasquez | Neighborhood design by consistency checking[END_REF], working on a consistent neighborhood. It is combined with a systematic resolution by the means of partial enumerations. Furthermore, a secondary optimization problem is introduced and solved by a second TS algorithm. Before describing the different phases of our resolution, let us in the next section give some works concerning the satellite management problems and nigher ones.

Related work

Compared to other optimization problems, the Earth Observing Satellite management problem has received a limited attention. For the AEOS problem and in the context of the ROADEF'2003 Challenge, various methods were proposed. In [START_REF] Roadef | Challenge: Booklet of Abstracts[END_REF],

J.F. Cordeau and G. Laporte have proposed a tabu search algorithm which borrows from the Unified Tabu Search Algorithm [START_REF] Cordeau | A unified tabu search heuristic for vehicle routing problems with time windows[END_REF] developed for the Vehicle Routing Problem with Time Windows (VRPTW). An important feature of their algorithm is the possibility of exploring infeasible solutions during the search by allowing the violation of the time window constraints. Thus, the value of a solution is defined by f (s) = G(s)αw(s), where w(s) is the total time window constraints. The parameter α is initially set at 1 and self-adjusts during the course of the search to allow a mixture of feasible and infeasible solutions. The moves switch between the insertion and the removal of mono and stereo shots with respect to all the constraints except the time window one which is relaxed. Moreover, the algorithm uses two diversification mechanisms. The first one is a continuous diversification scheme which introduces penalties on poor solutions. These penalties drive the search process toward the less explored regions of the search space whenever a local optimum is reached. The second diversification mechanism perturbs the solution under certain circumstances. If the best known solution has not improved after a certain number of iterations then the search stops and restarts from the best reached solution. However, this best solution is perturbed by removing a portion of randomly selected shots. E.J. Kuipers [START_REF] Roadef | Challenge: Booklet of Abstracts[END_REF] proposed a local search algorithm based on two stages. In the first one, the most promising solutions are constructed then further optimized in the second stage. These two parts use Simulated Annealing (SA) algorithms. The neighborhood is constructed in two steps. In the first one, 1, 2, 3 or 4 requests (or parts of requests) are removed from the current solution, and in the second step 1, 2, 3 or 4 requests (or parts of requests) are added to the solution resulting from the first one. The number of the added or removed requests (1, 2, 3 or 4) in both steps is randomly chosen. Moreover, a library is constructed to file the best ways of ordering a set of 5 strips in terms of transition durations. This library is updated at each new insertion and used by the two SA algorithms. Other additional schemes are added to attempt the speeding up of the optimization process of the first stage (for instance, a limitation on the number of the strips treated according to their gain). However, the second stage considers all the strips during the neighborhood construction.

In addition, a number of variants of the AEOS problem have been studied in the literature. The paper [START_REF] Hall | Maximizing the value of a space mission[END_REF] presents the space mission problem which consists of selecting and scheduling a set of jobs on a single machine among a set of candidates jobs. Each candidate job has a fixed duration, a given time window and a weight. The aim is to select a feasible sequence of jobs that maximizes the sum of weights. The space mission problem is NP-hard and it is very close to the AEOS management problem with the following simplifications: null transition times, no unique strip acquisition and stereoscopic constraints, and a linear objective function. Several interesting greedy algorithms and an optimal algorithm for solving the space mission problem are proposed. The optimal algorithm is based on a Dynamic Programming scheme. Upper bound formulations are presented, based on a preemptive relaxation (a job can be fragmented) and a lagrangian relaxation. The proposed algorithms are tested on 30 randomly generated instances with up to 200 candidate jobs.

The selection and scheduling problem for the SPOT5 satellite concerns a non-agile satellite with only one moving axis (rolling). A consequence of this lack of manoeuvrability is that the starting time of each candidate image is fixed. This feature would result in a very simple (polynomial) problem if there were only one imaging instrument on the board of the satellite, but there are 3 instruments. Nevertheless, it is possible to pre-compute binary and ternary constraints which model the compatibilities between candidate images. Each candidate image is weighted and the problem is to find a feasible subset of the candidate images maximizing the sum of weights. This optimization problem is NP-hard and can be formulated in the general Valued Constraint Satisfaction Problem model [START_REF] Schiex | Valued constrained satisfaction problems: hard and easy problems[END_REF]. The paper [START_REF] Bensana | Earth observation satellite management[END_REF] fully describes the problem and proposes some instances benchmark. Some results with dedicated exact and approximate methods are given in [START_REF] Bensana | Exact and approximate methods for the daily management of an Earth observation satellite[END_REF][START_REF] Bensana | Earth observation satellite management[END_REF] and the column generation technique has been used to compute upper bounds on the benchmark instances [START_REF] Gabrel | Improved linear programming bounds via column generation for daily scheduling of Earth observation satellite[END_REF]. Very good results on these instances were obtained by M. Vasquez and J.K. Hao using a dedicated Tabu Search algorithm [START_REF] Vasquez | A logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an Earth observation satellite[END_REF]. These authors have also obtained very good upper bounds by means of an original partition method assessing the quality of their previous results [START_REF] Vasquez | Upper bounds for the SPOT5 daily photograph scheduling problem[END_REF]. Note that for some instances the optima values are still unknown.

The work presented in [START_REF] Gabrel | A new model and derived algorithms for the satellite shot planning problem using graph theory concepts[END_REF] concerns a selection and scheduling problem of a semiagile satellite. The differences with respect to the AEOS problem are as follows: (a) the criterion to be maximized is the number of selected images (images are not weighted), (b) the satellite is slightly mobile in two axes (pitch and roll), but remains fixed during an image acquisition; so, there is only one possible azimuth for an acquisition, (c) the satellite's kinematics do not allow for a given strip to be acquired twice during the same track, and (d) there are no stereoscopic requests, hence no corresponding stereo constraints.

We now describe some related problems. In the first one which is named the Maximum Shot Sequencing Problem (MSP), the aim is to select and to schedule a set of images over several consecutive tracks (a given image can be acquired from two or more tracks), so several possible disjoint time windows are given for each image. In the second problem, named the Maximum Shot Orbit Sequencing Problem (MSOP), only one track is processed, so a single time window is associated to each candidate image. MSOP and MSP are also NP-hards and several algorithms are proposed and based on graph theoretic concepts. In a first approach, the time is discretized. The constraints (given by the satellite kinematics) are such that MSOP amounts to a longest path problem. With time discretization, MSP amounts to find a maximal independent set in an incompatibility graph, and can be solved by an approximate algorithm based on a near-optimal partition into cliques. Due to the nature of the objective, an interesting upper bound is available. Exact and approximate algorithms are also presented for the continuous time model to solve both MSP and MSOP. The exact algorithm is a branch-and-bound algorithm with graph-based heuristics and bounds. The approximate algorithm is a kind of greedy algorithm also based upon graph properties. Experiments are conducted on a set of randomly generated instances, allowing the proposed algorithms to be assessed against upper bounds and the impact of the discretization to be measured.

The paper [START_REF] Harrison | Task scheduling for satellite based imagery[END_REF] describes a scheduling problem concerning a satellite equipped with a radar instrument which is very agile on the pitch axis but slow on the roll axis. Only one azimuth is available for acquiring images. This problem is equivalent to the space mission problem [START_REF] Hall | Maximizing the value of a space mission[END_REF] with transition times. The authors describe a partial enumeration algorithm for this problem and give preliminary results for randomly generated instances.

The work reported in [START_REF] Wolf | Three scheduling algorithms applied to the Earth observing systems domain[END_REF] describes the so-called Window-Constrained Packing problem (WCP). It differs from the problems presented above in the fact that the evaluation function is a priority-weighted sum of observation durations under suitability functions. In other words, observations have non-fixed durations (ranging between a maximum and a minimum) and preference is given to higher priority observations (with longer durations) and to the observations which are well-placed inside their time window. There are no transition times between observations. This problem is similar to the space mission problem [START_REF] Hall | Maximizing the value of a space mission[END_REF], with a particular gain function, depending on the starting times of the observations. The authors present some approximate algorithms for solving the WCP problem. A first one is a fast but not very accurate greedy algorithm. A second one is similar to the first, but it includes some lookahead. It is a little better but has expensive computation times. These algorithms have been tested on randomly generated instances. Actually, the WCP problem is a simplified short-term version of the real scheduling problem. The paper investigates the associated mid-term and long-term scheduling problems and their connections, as well as different objective functions.

A Tabu Search algorithm for AEOS problem

In this section, we first review the the principles of the Tabu Search then we will describe point by point all the components of our tabu resolution.

Review of TS

A Tabu Search (TS) is a meta-heuristic designed to tackle hard combinatorial optimization problems. By contrast with random approaches, TS is based on the belief that an intelligent search should include more systematic forms of guidance based on adaptive memory and learning. TS can be described as a form of neighborhood search with a set of critical and complementary components. For a given optimization instance (S, f ) characterized by a search space S and an objective function f , a neighborhood N is introduced. It associates to each configuration s in S, a nonempty subset N (s) of S. A typical TS algorithm begins with an initial configuration s 0 ∈ S, then repeatedly visits a series of the best local configurations following the neighborhood function. At each iteration, one of the best neighbors s ∈ S is selected to become the current configuration, even if s does not improve the current configuration in terms of the cost function.

To avoid the problem of cycles occurring and to allow the search to go beyond local optima, a tabu list is introduced. This adds a short term memory component to the method. A tabu list maintains a selective history H (short term memory), composed of previously encountered configurations or, more generally, pertinent attributes of such configurations. A simple TS strategy consists in preventing configurations of H from being considered on the next k iterations, called the tabu tenure. This can vary according to different attributes, and it is generally problem dependent. At each iteration, TS looks for the best neighbor from this dynamically modified neighborhood N (H, s), instead of N (s) itself. Such a strategy prevents the search from being trapped in short term cycling and makes the process more rigorous. When attributes of configurations, instead of configurations themselves, are recorded in a tabu list, some unvisited, but nonetheless interesting configurations may be prevented from being considered. Aspiration criteria may be used to overcome this problem. A widely used aspiration criterion consists in removing a tabu status from a move when it leads to a configuration better than the best one obtained so far. Two other important ingredients of TS are intensification and diversification. On the one hand, the intensification consists in focusing the search to exploit regions of the search space, or characteristics of solutions, that the search history suggests that they are promising. On the other hand, the diversification undertakes to explore regions that differ in significant respects from regions previously visited.

Therefore, a TS is described by specifying its main elements: the configuration representation, the cost function to evaluate the configurations, the neighborhood function, the tabu list management, the aspiration criteria, and finally the intensification and diversification phases.

Search space definition

Definition 1 The unconstrained search space S consists of all the vectors of the pairs (x i , t i ), i = 1, . . . , 2n:

S = {((x 1 , t 1 ), (x 2 , t 2 ), . . . , (x 2n , t 2n ))/ ∀i ∈ [1, 2n] : x i ∈ {0, 1} and t i ∈ R}.
In this formulation, i is a shot number among the 2 × n possible ones issued from the n strips (2 shots per strip). t i is the (unconstrained) beginning time acquisition of the shot i. The size of S is highly huge and increases as the value of n and the size of the t i intervals increase. Each element s ∈ S is a configuration that does not satisfy necessary the problem constraints. However, a solution must satisfy the constraints defined by (1) to (4).

Definition 2

The totally constrained search space X is a subset of vectors in S that satisfy all the imperative constraints (1) to (4): X = {s ∈ S/ all the elements of s satisfy the constraints (1) to (4)}.

Each vector s ∈ X is a consistent configuration (all the constraints are satisfied), which is evaluated by its corresponding gain

G(s) = m k=1 g k × f ( 1 s(k) i∈p(k) su(i) • x i ) (see Sect. 2)
. We denote by |s| the number of the shots that are selected in s (|s| = i=1,...,2n x i ). This constrained search space is used by our TS algorithm. However, it is equally possible for an algorithm to work with an intermediate search space where some constraints are relaxed. For this propose, we define a partially constrained search space C.

Definition 3

The partially constrained search space C is a subset of vectors of S satisfying only the imperative constraints (3) and ( 4): C = {s ∈ S/ all the elements of s satisfy the constraints (3) and ( 4)}. This search space, where the stereo and uniqueness acquisition constraints are relaxed, will be used in order to compute upper bounds for the simplified problem.

Definition 4

The saturated and the totally constrained search space M is a subset of X (M ⊆ X) such that: M = {s ∈ X\ for any i ∈ [1, 2n] such as x i = 0 in s, setting x i = 1 violates systematically some of the constraints (1) to (4)}.

In other words, each vector s ∈ M is a consistent and a saturated configuration where no more images can be added without violating some imperative constraints. The principle here is that TS algorithm will explore the totally constrained search space X and try to stay on the border of this saturated (promising) area. This saturation is one of the features of the optimal solution.

Consistent and saturated neighborhood

Now, we introduce the neighborhood function N over the totally constrained search space X. This function N : X → (2 X -∅) is defined as follows:

Let s = ((x 1 , t 1 ), (x 2 , t 2 ), . . . , (x 2n , t 2n )) be a consistent configuration, s = ((x 1 , t 1 ), (x 2 , t 2 ), . . . , (x 2n , t 2n )) is a neighbor of s, i.e. s ∈ N (s), if and only if the following conditions are checked:

1. ∃!i ∈ [1, 2n] \ x i = 0 and x i = 1. Moreover, if tw(i) = 0 then x tw(i) = 0 and
x tw(i) = 1 (we try to insert exactly one shot in s, and its twin if it exists). 2. For any shot i that satisfies the condition 1 and a shot j ∈ [1, 2n] such as i and j are issued from the same strip, we have x j = x j = 0. Moreover, if tw(i) = 0 then x k = x k = 0 such as the shots tw(i) and k are also issued from the same twin strip. This condition forbids the acquisition of a strip (and its twin if it exists) in two directions and deals with the first constraint of the AEOS problem. 3. For any shot i that satisfies the condition 1, we have

t i ∈ [es(i), ls(i)]. Moreover, if tw(i) = 0 then t tw(i) ∈ [es(tw(i)), ls(tw(i))
]. This condition deals with the time window visibility constraint. 4. For each shot i that satisfies the condition 1, ∀k ∈ [1, 2n] such that (i, k) ∈ C4

and

x k = 1 we have x k = 0 and if tw(k) = 0 then x tw(k) = 0. Moreover, if tw(i) = 0 then ∀l ∈ [1, 2n
] such that(tw(i), l) ∈ C4 and x l = 1 then x l = 0. In addition, if tw(l) = 0 then x tw(l) = 0. 5. For any shot i that satisfies the condition 1, -3 ≤ |s | -|s| ≤ 1. Also, if tw(i) = 0 then -6 ≤ |s | -|s| ≤ 2. 6. For any shot i that satisfies the condition 1 and such that its insertion in s requires at most the removal of two shots j , k ∈ [1, 2n] with their twin shots if they exist (-3 ≤ |s | -|s| ≤ -1, x j = x k = 1, x j = x k = 0 and j = tw(k)) then even y j →k = 1 or y k→j = 1 in s (k and j are acquired one behind the other in s).

Thus, the neighborhood of s is obtained by adding a free shot i (not yet scheduled, x i = 0) by flipping x i from 0 to 1 (condition 1), then removing some shots k (by flipping x k from 1 to 0) to repair the violated constraints (condition 4). In fact, inserting a new shot may require to drop a certain number of the already fixed ones to maintain the consistency of constraints (1) to (4) described in Sect. 2.2. However, the condition 5 enforces a maximum of 2 shot removals if all the dropped shots are mono and 4 if they are stereo (in order to maintain the consistency of the stereo constraint, if a stereo shot is removed then its twin is removed too).

According to the conditions mentioned above, the best case is the insertion of a stereo shot and its twin without any removal (|s | -|s| = 2). Oppositely to this case, the worst one corresponds to two insertions (stereo shot plus it twin: +2), such as each of these two insertions needs the removal of 2 stereo shots plus their twins: -4 (|s | -|s| = +2 -4 -4 = -6). Moreover, this choice heuristic is also restricted to the removal of successive shots as described in the condition 6.

Hence, each configuration reached from s and according to the condition 1 to 6 is also consistent and may be saturated (it is impossible to insert a new shot without any removal). Consequently, the elaborated neighborhood N (s) is consistent and can be saturated.

Partial enumerations for the neighborhood evaluation

We evaluate N (s) according to the gain criterion. For this purpose, consider a configuration s = ((x 1 , t 1 ), (x 2 , t 2 ), . . . , (x 2n , t 2n )) where |s| images are selected and an image j such that x j = 0 (i.e. j is not yet selected). The shot j can be inserted in s through |s| + 1 positions: before the first shot, after the last shot, or between two successive shots on the schedule s. Hence, the insertion of the shot j in each of the |s|+1 positions is tested by allowing successive image removals (as explained above). If a position is tested positively then a neighborhood configuration s is reached by inserting j at this position is s (and dropping some others images, if necessary). We evaluate s by computing its corresponding gain value G(s ) (see Sect. 2.3). Among all the feasible insertions of j , the one that maximizes the gain value is selected. Consequently, at each step of the TS algorithm, we solve the decision problem of finding the best insertion position for each free shot in s according to the gain function. These insertion tests correspond to partial enumerations under s.

Incremental evaluation of the neighborhood

TS algorithm uses an aggressive search strategy to exploit its neighborhood, i.e. at each iteration, it examines the value of G(s ) for each candidate neighbor s ∈ N (s) and chooses the one with the highest gain. Those operations are very time consuming. For example, let us consider a problem without stereo strips and the possibility to remove 0, 1 or 2 shots to perform a move. Table 1 gives the computing costs of the insertion of a free shot (among the 2 × (n -|s|) free ones).

Such insertion requires the test of 2|s| 2 -|s| + 2 positions, and the total cost of an iteration is 2 × (n -|s|) × (2|s| 2 -|s| + 2), which is also the complexity (at the worst case) of the decision problem of a shot insertion. In order to overcome this complexity, incremental computing techniques are used [START_REF] Fleurent | Genetic and hybrid algorithms for graph coloring[END_REF]. The main idea is to use a specific data structure containing for each possible move the corresponding gain and the resulting configuration if the insertion is really performed. Each time a move is carried out, the elements of this data structure which are affected by the move are updated accordingly.

The neighborhood is evaluated in accordance to Algorithm 1. The used notations are as follows:

-L cand is the list of the candidate moves among the neighbors of the current configuration. -best_gain is the best gain associated to the configuration obtained by the insertion of a free shot in the current configuration s and contained in L cand . -Generate-sub-schedules(s) is the function which generates sub-schedules from s by removing 0, 1 or 2 successive images (and their twins if necessary). -The set of the sub-schedules produced by the function Generate-sub-schedules(s) is denoted by D s . The first element of D s is s (no removal). We denote by |D s | the number of sub-schedules in D s and by s l the lth sub-schedule in D s . p m denotes the position numbered by m and situated between two shots which are scheduled respectively at the orders m and m + 1 according to their shooting start date. In particular, p 0 is the position before the first acquired shot and p |s l | is the position after the last acquired shot in s l .

Example 1 Consider s l = {(x 1 = 1, t 1 = 60), (x 2 = 0, t 2 = ∞), (x 3 = 0, t 3 = ∞), (x 4 = 0, t 4 = ∞), (x 5 = 1, t 5 = 40), (x 6 = 0, t 6 = ∞), (x 7 = 1, t 7 = 50), (x 8 = 0, t 8 = ∞)}. If we order the selected shots 1, 5 and 7 (x 1 = x 5 = x 7 ) in s l according to their shooting start date then we obtain shot 5 < shot 7 < shot 1 (t 5 < t 7 < t 1 ). Hence, we can express the different positions p m as follows:

p 0 -shot 5 -p 1 -shot 7 -p 2 -shot 1 -p 3 .
p 0 is the position before the shot 5.

p 1 is the position between the shots 5 and 7.

p 2 is the position between the shots 7 and 1.

p 3 is the position after the shot 1.

g * is the gain associated to the best schedule already reached s * from the beginning of the resolution, g * = G(s * ). -Insert(s l , i, p m ) is a function which returns True if the insertion of the shot i at position p m in a sub-schedule s l is feasible regarding to the problem constraints, False otherwise. -Gain(s l , i, p m ) is the associated gain to the configuration resulted from the insertion of the shot i in s l at the position p m .

In Algorithm 1, we start by generating the set D s of the sub-schedules obtained by removing some shots. Then we try to insert each free shot i in those sub-schedules. If an insertion is successful then we calculate its corresponding gain. Afterward, this insertion becomes candidate, the list of the best candidates is saved in L cand and their associated gain value is best_gain. If a candidate move improves the current best gain then L cand will contain only this move. The list L cand will be used in the move heuristic as it will be explained in the next sections.

Tabu list management and move heuristic

We define a move by the insertion of a free shot i (flipping x i from 0 to 1) followed by the removal of the conflicting shots that do not satisfy the problem constraints (for each conflicting shot j , we flip x j from 1 to 0). Now, we explain both the management of the tabu list and the heuristic used to select one of the move candidates.

Tabu list management

The role of a tabu list is to prevent short-term cycling. In this order, when a shot i is selected and scheduled (a move is carried out), this shot is classified tabu (forbidden for any change) for a certain time called the tabu tenure. In our TS algorithm, this tenure is dynamically formulated by: tabu(i) = iter + α × freq(i), where:

-iter is the number of the current iteration of the tabu algorithm.

-freq(i) counts the number of times that the shot i has been selected by the tabu algorithm (note that a shot can be inserted at a given iteration and be dropped some iterations later, then reselected after and so on).

α is a variable parameter used to weight tabu(i) according to freq(i).

Moreover, a sequence of shots is tabu if all its shots are tabu, and not tabu if it contains at least one non-tabu shot. Likewise, we state that a sub-schedule obtained from a current schedule by removing a tabu sequence is also tabu, otherwise it is not tabu. Additionally, the direct azimuth corresponds to the natural move direction of the satellite and changing azimuth between two shootings is very costly in the terms of transition time. Consequently, the acquisitions in the direct azimuth are preferred over the indirect ones. This preference is expressed by setting α = 2 × β for the shots acquired in a direct azimuth and α = β for the indirect ones (the value of β is fixed empirically). Hence, if i is odd then

tabu(i) = iter + 2 × β × freq(i) else tabu(i) = iter + β × freq(i).
Recall that in Sect. 2.1 we use odd and even numbers to differentiate the shots regarding to their acquisition directions.

Move heuristic

Once the neighborhood is evaluated, the selected shot (move) is the one that maximizes the gain value and does not remove a sequence of tabu shots. However, if a move strictly improves the best gain then the aspiration criterion is employed to cancel the tabu status of a sub-schedule. Therefore in Algorithm 1, the condition labeled [START_REF] Benoist | Upper bounds of the maximal revenue of an Earth observation satellite. 4OR: Q[END_REF] corresponds to either the best gain g * is strictly improved (aspiration criterion) or the sub-schedule s l is not tabu. To summarize, we start by constructing L cand , we select randomly one candidate move (s l , i, p m ) from L cand , then we insert the shot i in s l at the position p m to obtain the neighbor configuration s that replaces the current one, which completes the move.

As described above, if some moves lead to the same gain value then one of them is randomly chosen. However, this selection criterion is not the most effective one. For this reason and to tone down the random effect, we introduce a second objective function which is the minimization of the sum of the transition durations in a configuration s. We denote this sum by T dT (s).

A secondary optimization problem: minimization of T dT

Some moves may lead to the same gain value. In this case and to make a better choice than a random one, a second objective function is defined by the minimization of the sum of transition durations that separate the acquisition of the shots. This minimization is done according to the constraints (1) to (4) of the original AEOS problem:

Min T DT (s) = 2n i=1 2n j =1 j =i x i • x j • y i→j • d(i → j)
subject to:

(1) For any strip j ∈ [1, n], x 2j -1 + x 2j ≤ 1.

(2) For any stereo strip j ∈ [1, n] and tw(j ) = 0, we have (x 2j -1 = x 2tw(j )-1 and

x 2j = x 2tw(j ) ).

(3) For any shot

i ∈ [1, 2n], if x i = 1 then t i ∈ [es(i), ls(i)]. (4) ∀i = j ∈ [1, 2n] (i and j are shots), t j -t i ≥ (d(i) + t (i → j)) • y i→j + (es(j ) - ls(j )) • (1 -y i→j ).

The enhanced aspiration criteria

Before solving this second optimization problem, we improve the aspiration criterion as follows. The tabu status of a sub-schedule is canceled if one of the two conditions below is verified:

1. if a move leads to a configuration s better than the best configuration s * found so far, i.e. G(s ) > G(s * ) = g * , 2. if a move leads to a configuration s with the same gain value of s * but with a lower T dT value than T dT (s * ), i.e. G(s ) = G(s * ) and T dT (s ) < T dT (s * ).

In order to tackle the T dT minimization problem, we design a second tabu algorithm based on the inversion of the acquisition direction of the strips and the exchange of the order of the shots in the considered configuration. This resolution is the subject of Sect. 5.

Intensification and diversification phases

The tabu mechanism may lead to a state where no move is admissible (all moves are tabu). This occurs when each possible move has been tried a large number of times without improving the best configuration already reached s * . In this case, we launch an intensification phase. This one is based on a heuristic using a long-term information [START_REF] Glover | Tabu Search[END_REF]. To this end, when the gain cannot be improved (all the shots are tabu and the aspiration criterion is not satisfied) the intensification phase attempts to overcome this situation by exploiting the best schedule s * as follows:

First step: The minimization of the sum of the transition durations of s * is tackled by a dedicated TS algorithm (see Sect. 5). The minimization of T dT (s * ) is called the smoothing step. If it succeeds (i.e. the T dT (s * ) value is decreased) then the tabu status of all the shots are set to 0, and the tabu exploration is restarted from the smoothed s * . This step is very important. In fact, we have observed that during the experimental process if this first step has been achieved successfully then we may insert a free shot without any removal and consequently improve the best gain g * .

Second step: When the smoothing step fails, we decrease the β value by dividing it by 2, β ← β/2. Hence, the tabu durations are reduced (recall that β is a variable parameter of the tabu tenure of a shot, see Sect. 4.4). Accordingly, if β >1 then the tabu status of all the shots are set to 0 and the tabu exploration is restarted from the best solution s * .

As described above, the intensification phase alternates between two exclusive steps. In fact, the execution of the fist step (respectively, the second step) inhibits the execution of the second one (respectively, the first one). Its aim is to focus the exploration around the elements of the best solution by either reordering its selected strips and inverting their acquisition directions (T dT (s * ) minimization) or by decreasing the tabu tenure of the shots. However, if the intensification phase does not improve the best gain then a diversification process is applied.

The role of diversification is to escape from the attractive zones of the search space corresponding to the local minima. For this reason, when both the tabu exploration and the intensification phase fail, we generate a new starting point (first schedule) different from the last one used at the beginning of the tabu exploration, we set the tabu status of all the shots to 0 and the β parameter to a new value fixed empirically, then we restart the tabu search from this new point.

A greedy algorithm for the AEOS problem

To produce quickly a first feasible solution for the AEOS problem, we design and use a greedy algorithm. This one is based on a simple operation of inserting a shot that does not require the removal of the already selected shots. Also, each shot i ∈ [1, 2n] is weighted according to the number of times that it was selected by the greedy algorithm. We denote by wg(i) this weight which is initialized to 0.

When it is launched, the greedy algorithm starts by sorting the 2n shots in the increasing order of their weights wg. This treatment is accomplished by the function SortShots() in Algorithm 2 and the result is stored in the list Q (Q j is the number of the shot that is ordered at the position j in Q according to its wg(Q j ) value). The first element of Q is the least selected shot by greedy() and the last one is the most selected one. Hence, acquiring the shots according to their weights aims to favor the acquisition of the less selected shots by the greedy algorithm.

In Algorithm 2, y is a configuration where any shot is selected (∀i ∈ [1, 2n], x i = 0). In the loop "for", we try to acquire each shot Q j by satisfying all the problem constraints. Moreover and oppositely to the move heuristic that we have defined before, we forbid removing the shots that are already fixed in y. In fact, if the condition at the line [START_REF] Benoist | Upper bounds of the maximal revenue of an Earth observation satellite. 4OR: Q[END_REF] is not checked then we simply skip the current shot and handle the following one in Q.

Algorithm 2: greedy() begin let be y a configuration where ∀i ∈ [1, 2n] we have x i = 0; % Q is the list of the 2 × n shots sorted in the increasing order of the wg values Q ← SortShots(); % Q j is the j th element of Q for j = 1 to 2n do [START_REF] Benoist | Upper bounds of the maximal revenue of an Earth observation satellite. 4OR: Q[END_REF] if setting x Q j = 1 in y satisfies the constraints (1) to (4) then

x Q j ← 1; wg(Q j ) ← wg(Q j ) + 1 return y end;
Regarding to the weights wg and to their corresponding sorted shots list Q, two executions of Algorithm greedy() will return two different configurations in terms of the selected strips. This feature allows us to deal with the diversification step that needs different starting points (see last paragraph of Sect. 4.6).

Global tabu resolution

The TS algorithm follows a general scheme consisting of three iterative phases: exploration, intensification and diversification. All these resolution steps are given in Algorithm 3. It starts by initializing the different structures that it uses, such as the wg, freq and tabu values. The greedy algorithm returns a first feasible solution s 0 constructed by successive image insertions without any removal. |s 0 | + is the number of the selected shots in s 0 and which are acquired in the direct azimuth. The instruction labeled [START_REF] Bensana | Exact and approximate methods for the daily management of an Earth observation satellite[END_REF] tunes the value of the parameter α according to the shooting direction of an image and as explained in Sect. 4.4: we recall that an odd (even) number indicates a shot that is acquirable on the direct (indirect) azimuth. The Tabu-T dT (s * ) function (label [START_REF] Bensana | Earth observation satellite management[END_REF]) corresponds to the tabu algorithm dedicated to the minimization of T dT (s * ) value. Finally, the stop criterion is a limited execution time.

The diversification phase is launched when the intensification step fails. Hence, we execute a new iteration of the most external loop repeat . . . until by generating a new starting point s 0 by the means of the greedy algorithm and executing the tabu search, . . . The different phases (exploration, intensification and diversification) use the same tabu search engine. Each one is triggered and stopped automatically by the tabu list management, i.e. whenever no more move is admissible.

Tabu algorithm for minimizing T dT

As we have seen previously, the T dT minimization is used in the intensification process. We recall that for a given configuration s, we have T dT (s)

= 2n i=1 2n j =1, j =i x i • x j • y i→j • d(i → j).
The aim is to obtain a shortest schedule in terms of the sum of the transition durations between the strip shootings. Indeed, the reduction of this sum can generate visibility time windows sufficiently broad and usable by the satellite to acquire new shots and without removing those that are already selected. the minimization of T dT is based on two operations: the exchange of the order of the shots and the inversion of the acquisition direction of the strips. The order exchange is inspired by the 2-opt operation [START_REF] Lin | Computer solutions of the traveling salesman problem[END_REF] which is widely used in solving the Traveling Salesman Problem (TSP).

As in the last section, we detail the various elements of the TS algorithm dedicated to solve the T dT minimization problem.

Neighborhood evaluation

As for the first TS algorithm, the explored search space is totally constrained. Hence, each visited configuration is consistent and may be saturated. Accordingly, we define the neighborhood function N t over X as follows:

Algorithm 3: Tabu-AEOS() begin for i = 1 to 2n do wg(i) ← 0; % initialization of the wg weights repeat % initialization of the tabu and the frequency values of each shot for i = 1 to 2n do Let s = ((x 1 , t 1 ), (x 2 , t 2 ), . . . , (x 2n , t 2n )) be a current configuration, s = ((x 1 , t 1 ), (x 2 , t 2 ), . . . , (x 2n , t 2n )) is a neighbor of s, i.e. s ∈ N t (s), if and only if the following conditions are verified:

x i ← 0; freq(i) ← 0; tabu(i) ← 0; [1] s ← s 0 ←
1. ∃!i ∈ [1, 2n]/ x i = 0 and x i = 1. Moreover, if tw(i) = 0 then x tw(i) = 0 and

x tw(i) = 1. 2. For any shot i that satisfies the condition 1 and a shot j ∈ [1, 2n] such as i and j are issued from the same strip, we have x j = 1 and x j = 0. Moreover, if tw(i) = 0 then x k = 1 and x k = 0 such that tw(i) and k are also issued from the same strip.

The strip, that corresponds to the shots i and j , is acquired according to the direction of j in s (x j = 1 in s). Setting x j to 0 and x i to 1 in s means that we change the shooting direction of this strip. 3. The constraints (3) and ( 4) are satisfied in both s and s . 4. |s | = |s|. In other words, the same number of strips is selected in s and s .

In both the configurations s and s , the same strips are acquired (no strip is removed from s) as stated by the condition4. However, there is only one strip in s (condition 1) plus, if necessary, its twin for which the acquisition direction is inverted (condition 2). Moreover, to deal with time constraints (3) and ( 4), the order of the corresponding strip can be exchanged in the configuration s (in other words, its starting time changes).

A neighbor configuration s of s is evaluated according to the sum of the transition durations between the shots that it contains. Hence, for each s ∈ N t (s), the value of T dT (s ) is calculated and the best neighbors are selected through Algorithm 4 which is given below. We use the following notations: s -i is the configuration issued from s by removing the shot i (and eventually its twin) which is already selected (x i = 1 in s and x i = 0 in s -i ). |s -i | is the number of the selected shots in s -i . -remove(s, i) is the function which removes the shot i from s. The resulted configuration is s -i . j is the index of the shot issued from the same strip as i but taken in the opposite direction. -T dT * is the best T dT value obtained for the whole second TS algorithm.

-L t
-T dT (s -i , j, p m ) is the T dT value of the schedule obtained by inserting the shot j in the position p m in s -i .

At each iteration of the N t (s) evaluation, each selected shot i in s is removed (the resulting schedule is s -i ). Then, we try to insert the shot j in each position p m in s -i without any shot removal and by satisfying all the constraints (1) to ( 4). If an insertion is possible then we calculate the T dT value of the new configuration obtained by adding the shot j to s -i . The best candidate moves with the lowest T dT value (best_T dT ) are stored in L t cand which will be used in the phase of the move selection.

Tabu list management and move heuristic

For the T dT minimization, the tabu tenure is defined for the pairs (shot, position). Indeed, each time a shot j is inserted at position p m then the tabu tenure of (j, p m ) is dynamically updated by the formula: tabu(j, p m ) = iter + λ × freq (j, p m ), where:

-iter is the current iteration of the second tabu process.

-freq (j, p m ) is the number of the times that the shot j was inserted at at the position p m in s. λ is a variable parameter which is fixed empirically.

After the evaluation of the neighborhood N t , a shot j (which corresponds to the changing of the acquisition direction of an already scheduled shot i) is inserted at the position p m if the resulting configuration has the minimum T dT value and the pair (j, p m ) is not tabu. However, an aspiration criterion is employed to cancel the tabu status when T dT (s * ) (the best value already reached) is decreased. Hence, among all the candidate moves, one is randomly selected from L t cand , the insertion of j in s -i is performed and the constraints are propagated.

The general tabu algorithm for the T dT minimization

Combining all the points described above leads us to Algorithm 5 for the T dT minimization. This algorithm terminates when no more candidate moves are available (i.e. L t cand = ∅) and it returns the best configuration found s * and its corresponding T dT value, T dT * . The value of λ parameter is equal to the number of the acquired shots in s. The propagate_move function achieves the move and propagates all the constraints of the problem, namely, setting x j = 1 and x i = 0 (i and j are issued from the same strip) to deal with the first problem constraint, updating the visibility time windows and updating the starting acquisition date. Note that we have not introduce in this resolution a diversification and an intensification phases with the aim to have short execution times of the Tabu-T dT (s) algorithm.

Designing an exact algorithm to solve the AEOS management problem remains a difficult task even if a column generation approach was proposed but the obtained results were not so promising [START_REF] Roadef | Challenge: Booklet of Abstracts[END_REF]. In Sect. 7 we will compare the performances of our resolution to the best known ones. Moreover, we try to approximate the bounding of the optima values by calculating upper bounds on a simplified problem as described in the next section.

Upper bounds for the AEOS problem

To calculate upper bounds in a polynomial time, some simplifications on the original AEOS problem are mandatory. As described in Sect. 2, the AEOS management problem is a Shortest Path Problem with Time Windows (SPPTW) (see for example [START_REF] Desrochers | A generalized permanent labelling algorithm or the shortest path problem with time windows[END_REF]) with several additional properties increasing its hardness:

-Two scanning directions are possibles for each strip acquisition and mutually exclusive. -The stereo constraints: some pairs of strips describe two acquisitions of the same geographical area under different angles. Selecting one without the other is forbidden and scanning directions must be identical. -Requests are grouped into polygons whose gain is a convex piecewise linear function of the surface covered by the selected strips. -Over the 10 runs, the best gain value, the time needed to reach this gain and the number of the selected strips in the corresponding solution (columns 2, 3 and 4 of Table 3). -Over the 10 runs, the worst gain (column 5), and the average gain and time (columns 6 and 7). -The best known gains (column 8) issued from the published results during the ROADEF' 2003 challenge, in a booklet of abstracts [START_REF] Roadef | Challenge: Booklet of Abstracts[END_REF] and also available on the WEB site of the challenge 3 , but using different test parameters: Sun-Blade-1000 750 MHz/512 MB workstation and 300 seconds running time.

Result discussion

For the ten first instances (from 2 9 36 to [START_REF] Cordeau | A unified tabu search heuristic for vehicle routing problems with time windows[END_REF] Several comments can be made about these results. First, our TS algorithm is efficient and robust. In fact, 15 best gains are reached and 4 are improved, even if the best known gains were obtained on different experimentation conditions and the optimal gains are unknown. About the robustness of the algorithm, the gap value between the best gain found and the average gain, calculated using the formula 100 × ( Best Average -1), is equal to 0% for 12 instances (the best known value is always reached), and less then 1.60% for the rest of the benchmark, which is a poor value. Secondly, these instances seems highly constrained since only a small number of candidate strips are selected in the best solutions.

In Table 4, the gaps with the upper bounds are calculated by the formula 100 × (1 -Best UB ), where the column Best corresponds to the best gain values obtained by our TS algorithm and the column UB to the gains obtained by the dynamic programming algorithm on the simplified problem as explained in Sect. 6. For the instances 2 9 36, 2 9 66, 2 9 170 and 3 8 155, our TS algorithm reaches the optimality. For the other instances the gaps are between 17.08% and 28.60%. Even if these gaps are not so tight, the results obtained on the simplified problem (by the relaxation of some constraints and the linearization of the objective function) at least prove the optimality of four instances.

In this paper, we have proposed a tabu search algorithm to solve the problem of selecting and scheduling photographs of an Agile Earth Observing Satellite (AEOS). This problem is formulated as a constrained optimization problem. The involved constraints are both unary and binary and the evaluation function, to be maximized, is convex which increases the hardness of the problem. The TS algorithm explores a search space based on consistent and possibly saturated configurations. Consistency is ensured by an effective constraint propagation for each new move carried out during the search process. The resulting neighborhood is quickly evaluated by the use of incremental techniques. Moreover, the TS algorithm is bridged with systematic search by means of partial enumerations in order to solve a large number of decisional problems. In addition and to improve the efficiency of the resolution, we introduced a secondary problem which is the minimization of the sum of the transition durations in a schedule. A second tabu search algorithm was developed to tackle it where the neighborhood construction is based on exchanging the order of the acquired strips in the treated configuration and inverting their acquisition directions.

Furthermore and as an exact algorithm is hard to design for the AEOS management problem, we calculated upper bounds for a simplified problem by relaxing the uniqueness and stereo acquisition constraints, and the linearization of the objective function. Then, a dynamic programming algorithm was launched on this less constrained problem.

Our resolution was applied on benchmarks provided by the French space agencies for the ROADEF'2003 challenge. The results obtained showed the efficiency of the TS algorithm. Indeed, all the best known results were reached (except for one instance) and optimality was proved for 4 instances. Note that those instances seem highly constrained because of the low number of the selected strips in the obtained solutions.

Concerning future work, the stereoscopic constraint needs to be handled in a more efficient way. This constraint, which consumes a large amount of computing time when it is handled, increases the difficulty of the problem, and unfortunately the proportion of the stereo shots in the solutions is generally very small. In addition, we will enhance the efficiency of the second optimization problem (the minimization of the sum of transition durations in a schedule) by using more powerful techniques taken from the Traveling Salesman Problem (TSP) and the Vehicle Routing Problem with Time Windows (VRPTW). Finally, the optimal values of the AEOS managing problem remain unknown. To overcome this weakness, we will study a way to improve the tightness of the upper bounds. A first possibility is to use the techniques based on the Lagrangian relaxation.

Table 1

 1 Generate-sub-schedules(s); % D s = {s, s 1 , s 2 , . . .} ; for all i, such that x i = 0 do for l = 1 to |D

	Computing complexity for one image insertion	# removals	# sub_schedules	# insertion tests
		0	1	|s| + 1
		1	|s|	| s| 2
		2	|s| -1	(|s| -1) 2
	Algorithm 1: Evaluate-N (s)
	begin
	L cand ← ∅;
	best_gain ← -∞;
	D s ←

s | do for m = 0 to |s l | do if Insert(s l , i, p m ) = True then [1] if (Gain(s l , i, p m ) > g * ) or (s l is not tabu) then if Gain(s l , i, p m ) > best_gain then L cand ← ∅; best_gain ← Gain(s l , i, p m ) ; L cand ← {(s l , i, p m )} ; else if Gain(s l , i, p m ) = best_gain then L cand ← L cand ∪ {(s l , i, p m )} ;

return (L cand , best_gain) end;

  cand is the list of the candidate moves.-best_T dT is the best T dT value obtained at the end of the evaluation of N t (s)

	Algorithm 4: Evaluate-N t (s)
	begin
	L t cand ← ∅; best_T dT ← +∞ ; for i ∈ [1, 2n], such that x i = 1 in s do
	s -i ← remove(s, i);
	for m = 0 to |s -i | do
	if Insert(s -i , j, p m ) = True then
	if (T dT (s -i , j, p m ) < T dT * ) or ((j, p m ) is not tabu) then
	if T dT (s -i , j, p m ) < best_T dT then
	L t cand ← ∅; best_T dT ← T dT (s -i , j, p m ) ; L t cand ← {(s -i , j, p m )} ;
	else
	if T dT (s -i , j, p m ) = best_T dT then
	L t cand ← L t cand ∪ {(s -i , j, p m )} ;
	return (L t cand , best_T dT );
	end;

Table 3

 3 The results obtained after 1800 seconds running time

	Instance	Best			Worst	Average		Best known
		Gain	N s	Time	Gain	Gain	Time	Gain
	2 9 36	10,423,440	2	<1	10,423,440	10,423,440	<1	10,423,440
	2 9 66	115,710,959	7	<1	115,710,959	115,710,959	<1	115,710,959
	2 13 111	563,597,071 54	90	563,597,071	563,597,071	90	563,597,071
	2 15 170	719,417,220 40	221	719,417,220	719,417,220	561	719,417,220
	2 26 96	1,005,301,900 35	1725	985,763,300	989,671,020	443	1,005,301,900
	2 27 22	966,643,460 30	57	966,643,460	966,643,460	57	967,910,750
	2 9 170	191,358,231 17	<1	191,358,231	191,358,231	<1	191,358,231
	3 25 22	425,983,220 28	95	425,983,220	425,983,220	95	425,983,220
	3 8 155	121,680,360 12	<1	121,680,360	121,680,360	<1	121,680,360
	4 17 186	185,406,200 37	<1	185,406,200	185,406,200	<1	185,406,200
	2 21 140 1,030,060,860 32	191	1,027,543,540 1,029,288,814	467	1,029,892,360
	2 21 155 1,150,632,847 35	1074	1,129,245,020 1,132,568,329	762	1,150,632,847
	2 21 170	914,978,310 40	573	906,992,592	912,183,616 1151	891,060,370
	2 21 22	1,160,594,340 32	115	1,160,366,840 1,160,571,590	831	1,160,366,840
	2 21 37	954,965,580 37	190	954,605,760	954,821,652	602	954,965,580
	2 21 7	842,378,700 33	115	842,378,700	842,378,700	116	842,378,700
	2 21 81	986,679,410 30	897	98,424,5930	985,894,172	778	986,679,410
	2 21 96	113,4461,030 38	843	1,125,880,120 1,130,197,543	932	1,133,044,250
	3 21 155	460,196,570 36	3	460,196,570	460,196,570	3	4,6019,6570
	3 21 81	37,3553,350 28	16	373,553,350	373,553,350	16	373,553,350

  [START_REF] Roadef | Challenge: Booklet of Abstracts[END_REF] 186, which we call A instances), all the best known gains are reached except for instance 2 27 22. These values are obtained after a maximum of 221 sec, except for instance 2 26 96, which required 1725 sec. For the ten instances 2 21 140 to 3 21 81 (B instances), all the best values are reached after less than 200 sec computing time except for the instances 2 21 155 and 2 21 81, which require 1074 and 897 sec respectively. Furthermore, the gains which are

Table 4

 4 Upper bound values

	Instance	Best	UB	Gap %
	2 9 36	10,423,440	10,423,440	0.00
	2 9 66	115,710,959	115,710,959	0.00
	2 13 111	563,597,071	750,675,448	24.92
	2 15 170	719,417,220	1,007,583,810	28.60
	2 26 96	1,005,301,900	1,262,199,140	20.35
	2 27 22	966,643,460	1,225,871,727	21.15
	2 9 170	191,358,231	191,358,231	0.00
	3 25 22	425,983,220	595,723,590	28.49
	3 8 155	121,680,360	121,680,360	0.00
	4 17 186	185,406,200	233,270,070	20.52
	2 21 140	1,030,060,860	1,268,577,920	18.80
	2 21 155	1,150,632,847	1,445,129,777	20.38
	2 21 170	914,978,310	1,177,206,242	22.27
	2 21 22	1,160,594,340	1,478,755,136	21.51
	2 21 37	954,965,580	1,281,931,945	25.51
	2 21 7	842,378,700	1,060,675,390	20.58
	2 21 81	986,679,410	1,315,194,307	24.97
	2 21 96	1,133,044,250	1,366,459,404	17.08
	3 21 155	460,196,570	604,049,451	23.81
	3 21 81	373,553,350	492,952,136	24.22
	obtained for the instances 2 21 140, 2 21 170, 2 21 22 and 2 21 96 are improved after
	a maximum of 843 sec.

Available from the WEB site of the challenge: www.prism.uvsq.fr/~vdc/ROADEF/CHALLENGES/2003

Consider the simplified AEOS management problem where the uniqueness and stereoscopic acquisition constraints are relaxed (the redundant strip acquisition and violation of the stereo constraint are allowed) and the evaluation function for polygons is linearized (f (x) = x). Accordingly, each instance of the AEOS management problem can be represented as a directed graph, in which each vertex i is represented by the pair (pe i , te i ), where pe i is the geometric point of the end of a strip and te i is the end time of a strip acquisition. The directed edges represent the possible transition between vertices (the visibility time windows and the transition constraints are satisfied). A gain Ge i is associated with each vertex i corresponding to the accumulated gain on the path reaching i from a starting vertex. To keep the graph finite, the time te i must take values only from a discrete set, such as the natural numbers.

An optimal solution of the simplified AEOS management problem is just the longest path in this graph. Finding such a path deals with SPPTW which is solvable in a polynomial time. Hence, an adaptation of a dedicated algorithm to SPPTW can be successfully applied. For this reason, we elaborate a Dynamic Programming (DP) algorithm (as done in [START_REF] Kohl | An optimization algorithm for the vehicle routing problem with time windows based on Lagrangean relaxation[END_REF] also inspired by [START_REF] Desrochers | A generalized permanent labelling algorithm or the shortest path problem with time windows[END_REF]) to deal with the simplified problem.

The constructed graph is circuit-free. However, a vertex might still be visited more than once, i.e. a strip may be acquired more than once on a path (redundancy). In [START_REF] Houck | The travelling salesman problem as a constrained shortest path problem: theory and computational experience[END_REF], a method for eliminating 2 cycles (i.e. double acquisition of a single strip) is suggested but cannot easily be generalized to cycles of higher orders. The implemented DP algorithm incorporates a 2-cycle elimination but it is forced to accept cycles of higher order. Now, we outline the main elements of the DP algorithm: the local optimal value of the quality criterion Ge * i at a vertex (pe i , te i ) can be expressed as:

where gs i is the gain of the strip from which the vertex (pe i , te i ) is issued. Satisfying constraints (3) and ( 4) means the existence of an edge from vertex (pe j , te j ) to (pe i , te i ) in the constructed graph. Accordingly, we define a dominance rule, for an efficient evaluation of each edge in the DP algorithm as follows: given two vertices i and j represented by (pe i , te i ) and (pe j , te j ) and characterized by the accumulated gains Ge i and Ge j respectively then:

(i dominates j ) if and only if (pe i = pe j and te i ≤ te j and Ge i ≥ Ge j ).

Several strategies to decrease the computation time of the algorithm have been proposed. In [START_REF] Desrochers | A new optimization algorithm for the vehicle routing problem with time window[END_REF], the authors suggested a method to decrease the width of the time win-dow and also proposed using a pulling algorithm instead of the more straightforward reaching algorithm usually used in DP-algorithms for shortest path problems.

After presenting both algorithms dedicated to the resolution of the AEOS management problem and the calculation of the upper bounds, we give and discuss the results obtained on the provided benchmarks.

Computational results

The AEOS management problem was the subject of the 3rd international challenge organized by the French Society of Operations Research and Decision Analysis (ROADEF'2003), and proposed by the CNES 1 and ONERA 2 French space agencies.

Test instances and experimental settings

The provided instances are artificially generated, with the number of requests (m value) ranging from 2 to 375, and the number of strips (n value) varying from 2 to 534 with a maximum of 113 stereo strips (n stereo value). Table 2 gives the properties of each of the 20 used instances. 3 The TS and DP algorithms are implemented in C/C++ language and compiled using Visual C++. The experiments were carried on a PIV 1.9 Ghz PC with 512 MB of RAM. The execution time, corresponding to the stop criterion of Algorithm 3, is fixed to 1800 seconds in order to evaluate the behavior of the algorithm over a relatively long computation time. Table 3 gives the obtained results. The TS algorithm was run 10 times per instance with different random seeds and the following information are collected:


Michel Vasquez

Coloration des graphes de reines

Jusqu'en 2003, le nombre chromatique des graphes de reines (χ n ) n'était pas connu pour des tailles de l'échiquier strictement supérieures à 9 et multiples de 2 ou de 3. Dans ce compte-rendu nous présentons une étude qui nous conduit dans un premier temps à trouver des colorations à n couleurs pour n = 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 28 et 32. Nous montrons ensuite qu'il existe une infinité de valeurs de n divisibles par 2 ou 3 pour lesquelles χ n = n.

On the Queen graphs coloring problem. Until 2003 no chromatic numbers (χ n ) for the queen graphs were available for n>9 except where n is not a multiple of 2 or 3. In this research announcement we present an exact algorithm which provides coloring solutions for n = 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 28 and 32 such as χ n = n. Then we prove that there exists an infinite number of values for n such that n = 2p or n = 3p,and χ n = n.

Introduction

Pour une dimension n donnée, le graphe de reines (queen_n 2 ) est constitué des n 2 sommets correspondant aux cases de l'échiquier. Deux cases appartenant à une même ligne (colonne ou diagonale) constituent une arête : c'est la règle de déplacement de la reine au jeu d'échec. Le problème que nous considérons dans cette étude est le suivant : peut-on colorer le graphe queen_n 2 avec seulement n couleurs différentes ? Si c'est le cas, alors le nombre chromatique χ n du graphe est n. En effet, les n cases d'une même colonne, d'une même ligne ou des deux diagonales principales de l'échiquier sont reliées entre-elles par le mouvement possible d'une reine : ces sommets définissent des cliques de taille n du graphe. Nous pouvons donc conclure que χ n = n dès lors que nous disposons d'une coloration à n couleurs. Alors que la littérature sur la coloration de graphes est abondante, les résultats sur les graphes de reines sont peu nombreux. Nous rappelons ici les plus récents. Pour ce qui est des méthodes exactes, Mehrotra et Trick [START_REF] Mehrotra | A column generation approach for graph coloring[END_REF] utilisent une génération de colonnes efficace sur des graphes de moins de 500 sommets mais qui ne dépasse pas 81 sommets (n = 9) pour les graphes de reines. Caramia et Dell'Olmo [START_REF] Caramia | Iterative coloring extension of a maximum clique[END_REF] proposent une recherche arborescente qui Adresse e-mail : Michel.Vasquez@ema.fr (M. Vasquez).

Abstract

repose sur l'extension de la coloration d'une clique maximale : les problèmes queen_n 2 sont résolus jusqu'à n = 9. Pour ce qui est des heuristiques, Hamiez [START_REF] Hamiez | Coloration de graphes et planification de rencontres sportives: heuristiques, algorithmes et analyses[END_REF] a développé une méthode de combinaison de colorations qui traite des problèmes jusqu'à n = 16 et produit des valeurs qui majorent le nombre chromatique. Mais les méthodes incomplètes, voir également [START_REF] Chiarandini | An application of iterated local search to graph coloring problem[END_REF], ne parviennent pas à colorer queen_n 2 avec n couleurs et ne peuvent prouver le caractère optimal de leur résultat.

Recherche exhaustive

Dans cette section, notre objectif est de prouver que χ n = n pour un certain nombre de valeurs de n divisibles par 2 ou 3. À défaut d'une méthode de construction nous proposons un algorithme d'énumération qui exploite les caractéristiques particulières des graphes de reines. Il est conçu à partir d'une reformulation du problème et se caractérise par un filtrage dynamique très efficace. Une coloration à n couleurs, si elle existe, définit n ensembles de sommets sans arête commune. Ce sont des stables du graphe. Les n lignes (ou colonnes) de l'échiquier constituent des cliques de taille n. Ces cliques sont disjointes et constituent une partition du graphe. Aucun stable ne peut donc contenir plus de n sommets. Colorer n 2 sommets avec n couleurs revient à trouver n stables disjoints avec exactement n sommets chacun. Considérons maintenant les sommets d'une des cliques de taille n. À chacune des n cases correspondant à ces sommets nous associons le sous-ensemble des stables dont l'un des sommets correspond à cette case. Les n sous-ensembles de stables ainsi définis constituent une partition de l'ensemble des stables maximaux du graphe. Chacune des classes de cette partition C i , i ∈ [1, n] est une variable du problème, à laquelle on peut associer une case de l'échiquier. Les stables d'une même classe S ∈ C i sont les valeurs que peut prendre cette variable. Nous voulons donc affecter n valeurs (S 1 , . . . , S n ) sous la contrainte {S i ∩ S j = ∅, 1 i < j n} qui formalise l'interdiction de placer deux reines sur une même case. La résolution de ce problème de satisfaction de contraintes s'effectue par une recherche arborescente. La variable de branchement correspond à la case non colorée de couverture minimale. Si ce minimum est nul un retour au noeud supérieur de l'arbre de recherche est effectué. La profondeur de cette recherche ne dépasse pas n. Après chaque affectation les stables qui couvrent une case colorée sont supprimés. Cette reduction de l'espace de recherche est renforcée par un filtrage qui s'appuie sur les cliques du sous-graphe des sommets non colorés. En effet, au noeud i de l'arbre de recherche, il reste ni stables à sélectionner pour construire une solution. Si, pour cette configuration partielle, il existe -dans le sous-graphe des cases libres -une clique à n + 1i sommets, alors il n'est plus possible de la compléter et nous pouvons retourner au niveau précédent de l'arborescence. Cette règle s'applique dès la racine de l'arbre de recherche en supprimant les stables qui n'ont pas de sommet sur les diagonales principales. Au noeud suivant on prend en compte les 4 diagonales à n -1 sommets. À chaque niveau de profondeur, 4 contraintes viennent s'ajouter.

Le Tableau 1 indique le nombre de stables à la racine et le nombre de noeuds produits au niveau 3 de l'arbre de recherche, ainsi que le temps de calcul de ces combinaisons de trois stables. Les colonnes 2, 3 et 4 indiquent ces valeurs lorsque seule la contrainte de non-recouvrement est propagée. Les colonnes 5, 6 et 7 montrent que combinatoire et temps cpu sont divisés par 2 si l'on tient compte de la contrainte sur les sommets non colorés dans les diagonales. La phase expérimentale est menée sur un XEON cadencé à 3 GHz. Jusqu'à n = 11 la réponse est instantanée. Il n'y a pas de solution pour n = 10, mais il est facile de construire une coloration de queen_10 2 à partir de celle de queen_11 2 pour lequel χ 11 = 11. Donc χ 10 = 11. Pour queen_12 2 , la recherche exhaustive a duré moins de 2 heures et a produit 454 solutions. Nous avons donc la complétude pour n = 10 et n = 12. Une semaine de calculs a été nécessaire pour obtenir une solution pour queen_14 2 . Cela suffit à prouver que χ 14 = 14. Pour n 14 les stables sont générés une fois pour toute, mais la complexité spatiale de cet algorithme nous interdit de traiter des instances de taille supérieure.

Recherche incomplète

La version de l'algorithme d'énumération dont il est question dans cette section est plus économe en mémoire centrale : les stables sont générés au fur et à mesure de la recherche arborescente. Les temps de réponse de cette option sont moins bons que ceux de la version précédente d'autant plus que l'on ne bénéficie plus de l'heuristique de branchement sur la variable dont le domaine de valeurs est minimal. Toutefois, la Fig. 1 -où chaque nombre représente une couleur -fait apparaître des symétries entre les stables qui constituent une solution. À partir de ce constat, et selon la valeur de n nous allons émettre des hypothèses sur la répartition des couleurs d'une solution afin d'énumérer plusieurs stables à la fois. Pour n = 2p nous affectons simultanément un stable et son symétrique par rapport à l'axe vertical : les variables correspondent aux n 2 paires de cases opposées de la première ligne. Les n couleurs de la première ligne sont fixées une fois pour toutes. Grâce à cette hypothèse nous prouvons que χ n = n jusqu'à n = 26. Pour n = 2p + 1, et n multiple de 3, nous utilisons la symétrie centrale : les variables correspondent aux n-1 2 paires de cases opposées sur la diagonale principale : les stables qui couvrent la case centrale sont exclus de la combinatoire grâce à la contrainte sur les cliques constituées par les sommets non colorés. Dans ce cas, l'algorithme ne parcourt plus que n-1 2 niveaux dans l'arbre de recherche et prouve que χ 15 = 15. Pour n = 4p, la conjonction des symétries horizontale et verticale nous permet de colorer quatre cases en même temps. Nous obtenons ainsi des colorations à n couleurs pour n = 16, 20, 24, 28 et 32. Il en va de même, pour n = 4p + 1, avec les compositions de la rotation de π 2 nous réduisons la profondeur de l'arbre de recherche à n-1 4 (la remarque sur la coloration implicite de la case centrale quand n = 2p + 1 s'applique également ici) et parvenons à prouver que χ 21 = 21. Ces résultats sont obtenus en moins d'une semaine de calcul, excepté n = 22 qui a été distribué sur 20 CPU et n = 26 qui a coûté 1 400 000 secondes. Notons enfin qu'une coloration de queen_14 2 est trouvée après 5673 noeuds en 5 secondes avec le filtrage sur les cliques de sommets non colorés alors que, sans ce filtrage, l'algorithme visite 45 299 345 noeuds en 19 469 secondes avant de produire une solution.

Extension de colorations

Nous montrons maintenant que si χ n = n et si p est premier avec 2 et 3 alors χ np = np. La formule de coloration que nous proposons généralise des résultats connus sur le placement des n reines [START_REF] Abramson | Construction through decomposition: a divide-and-conquer algorithm for the N -queens problem[END_REF]. Notons (i, j ) la case qui se situe en ligne i et colonne j . Soit c(i, j ) une coloration du graphe queen_n 2 en n couleurs. Soit p un entier premier avec 2 et 3 et r(i, j ) ≡ p 2i + j , où ≡ p est l'égalité dans l'anneau Z/pZ. Alors la formule : R(i, j ) = r(i, j ) + p c(i/p, j/p), où k/p représente le quotient de k dans la division entière par p, est une coloration du graphe queen_(np) 2 en np couleurs. En effet : d'une part 0 r(i, j ) p -1 et 0 c(i/p, j/p) n -1 ⇒ 0 R(i, j ) p -1 + p(n -1) = np -1 : nous utilisons donc np couleurs. D'autre part, puisque r(i, j) < p, R(i, j) = R(i , j ) ⇔ r(i, j ) = r(i , j ) et c(i/p, j/p) = c(i /p, j /p). Nous en déduisons les quatre équivalences suivantes : (i) R(i, j ) = R(i, j ) ⇔ j ≡ p j et j/p = j /p (c(i, j ) est une coloration et nous sommes sur une même ligne) ⇔ j = j ; (ii) R(i, j ) = R(i , j) ⇔ i ≡ p i (p est premier avec 2) et i/p = i /p (c(i, j ) est une coloration et nous sommes sur une même colonne) ⇔ i = i ;

(iii) R(i, j ) = R(i , j ) et ji = ji ⇔ i ≡ p i et j ≡ p j (p est premier avec 3) et i/p = i /p et j/p = j /p (c(i, j ) est une coloration et nous sommes sur une même diagonale) ⇔ i = i et j = j ; (iv) R(i, j ) = R(i , j ) et j + i = j + i ⇔ i ≡ p i et j ≡ p j et i/p = i /p et j/p = j /p (c(i, j ) est une coloration et nous sommes sur une même diagonale) ⇔ i = i et j = j .

Nous avons unicité des couleurs sur une même ligne, colonne ou diagonale : R(i, j ) est donc une coloration de queen_np 2 en np couleurs. Ainsi χ np = np et nous pouvons prendre pour n n'importe quelle des douze valeurs indiquées en Sections 2 et 3.

Conclusions

Cette étude sur la coloration des graphes de reines établit que χ 10 = 11 et que χ n = n pour n = 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 28 et 32 (Une partie de ces résultats figure dans l'encyclopédie des suites d'entiers de Sloane [3].) Les contributions originales en sont :

(i) de transformer la recherche du nombre chromatique des graphes de reines en un problème de décision où il s'agit de recouvrir l'échiquier avec n stables de n sommets chacun ; (ii) d'exploiter les cliques du sous-graphe des cases de l'échiquier non colorées à tous les noeuds de l'arborescence pour réduire l'espace de recherche ; (iii) d'effectuer une exploration incomplète de l'espace des solutions pour lesquelles la répartition des couleurs sur l'échiquier vérifie certaines propriétés géométriques.

Enfin, nous proposons un algorithme polynomial qui permet, à partir de l'un de ces douze nouveaux résultats, de montrer qu'il existe une infinité d'entiers n multiples de 2 ou 3 tels que χ n = n. Ce problème reste cependant difficile et nous ne connaissons pas, par exemple, le nombre chromatique du graphe correspondant à l'échiquier de dimension n = 27.

Références

Fig. 1 .

 1 Fig. 1. Certificat pour χ 12 = 12.