Michel Vasquez

Vasquez

A "Logic-Constrained" Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite

Keywords: tabu search, heuristics, satellite photograph scheduling, multidimensiona! knapsack, constraîned combinatorial optimization

The daily photograph scheduling problem of earth observation satellites such as Spot 5 consists of scheduling a subset of mono or stereo photographs from a given set of candidates to different cameras. The scheduling must maximize a profit function while satisfyîng a large number of constraints. In this paper, we first present a formulation of the problem as a generalized version of the well-known knapsack mode!, which includes large numbers of bînary and ternary "logical" constraints. We then develop a tabu search algorithm which integrates some important features includîng an efficient neîghborhood, a dynamic tabu tenure mechanism, techniques for constraint handling, intensification and diversification. Extensive experiments on a set of large and realistic benchmark instances show the effectiveness of this approach.

Introduction

The daily photograph scheduling problem (DPSP) is one of the key applications for an earih observation salellite such as Spot 5. The main purpose of the DPSP is to schedule a subset of photographs from a set of candidate photographs which will be effectively taken by the satellite. The resulting subset of photographs must satisfy a large number of imperative constraints of different types and at the same time maximize a given profit function.

The profit function reflects several criteria such as client importance, demand urgency, meteorological forecasts and so on. The constraints include both physical constraints such as the recording capacity on board of the satellite and logic constraints such as non over lapping trials and meeting the minimal transition time between two successive trials on the same camera.

This problem is also important and interesting from a complexity point of view. Indeed, it can be modeled as a generalized Knapsack problem, which is known to be NP-bard. So far, several methods have been proposed to tackle this problem. These methods include exact algorithms based on Branch and Bound techniques l 17], integer linear programming with CPLEX and constraint programming with the !LOG solver [ 12[ as well as heuristics based on greedy fonctions, simulated annealing and tabu search [2_ ].

The goal of this paper is two fold. First, we introduce a new formulation of the DPSP using the well-known 0/1 knapsack model. Second, we develop an original and effective tabu search (TS) algorithm based on this formulation. This TS algorithm includes a set of important features including an efficient neighborhood, an incremental technique for move evaluation, a mechanisrn for dynamic tabu tenure, constraint handling techniques, and mechanisms for intensification and diversification.

This algorithm is extensively evaluated on a set of large and realistic instances provided by the French National Space Agency CNES (Centre National d'Etudes Spatiales). Exper irnental results show the effectiveness of this algorithm both in terms of solution quality and speed of execution. Indeed, the algorithm easily obtains the previously best known results for these instances. More importantly, it produces much better solutions for the most difficult instances with very reasonable computing times.

The paper is organized as follows, in the next section, the DPSP is described and modeled. Section 3 presents the details of the TS algorithm. Numerical results and comparisons are presented in Section 4. Implications are discussed in Section 5 and Section 6 concludes the paper.

Photograph daily scheduling problem (DPSP)

Problem dejinition

The photograph daily scheduling problem can be informally described as follows [START_REF] Bensana | Benchmark problems: earth observation satellite management[END_REF].

Prohlem Components

• A set P = {pi, p2, ... , p 11 } of candidate photographs, mono or stereo, which can be scheduled to be taken on the "next day" under appropriate conditions of the satellite trajectory and oblique viewing capability.

• A "profit" associated with each photograph Pi, which is the result of the aggregation of several criteria such as client importance, demand urgency, meteorological forecasts and so on, • A "size" associated with each photograph Pi , which represents the amount of memory required to record P i when it is taken. • A set of possibilities associated with each photograph Pi in P corresponding to the different ways to take Pi : 1) for a mono Pi, there are three possibilities because a mono photograph can be taken by any of the three cameras (front, middle and rear) on the satellite and 2) for a stereo Pi, there is one single possibility because a stereo photograph requires simultaneously the front and the rear camera. • A set of imperative bard constraints, which must be satisfied:

1. any two trials must not overlap and the minimal transition time between two succes sive photographs on the same camera must be met;

2. limitations on the instantaneous data flow through the satellite telemetry resulting from simultaneous photographs on di f ferent cameras; 3. capacity constraint: the recording capacity on board must not be exceeded.

Problem Objective

The DPSP is to find a subset P' of P which satisfies all the imperative constraints and maximizes the sum of the profits of the photographs in P'. Thus, the goal is to maximize the total value of the items (photographs) packed in the "knapsack," subject to the constraint that the total size of all the packed items does not exceed the knapsack capacity ( constraint 3) and subject to other "logical constraints" ( constraints 1 and 2 above ). The DPSP is therefore a constrained combinatorial optimization problern.

In practice, the number of photographs in P may be quite large (up to 1057 for the largest instance we tested), implying a huge search space. Moreover, the presence of a large number of hard constraints (up to tens of thousands) makes the problem difficult to solve.

Problem formulation

Representing a schedule.

Let P be the set of candidate photographs and n = 1 P 1-With each mono photograph Pi in P, we associate three pairs of elements (p;, camera_l), (pi, camera_2), (Pi, camera_3). Similarly, with each stereo photograph Pi in P, we associate one pair (Pt, camera_13). Letting n 1 and n2 be respectively the number of mono and stereo photographs in P(n = ni + n2), there are in total m = 3 * n 1 + n2 possible pairs of elements for the given set P of candidates. Now, associating a binary ( decision) variable xi with each such pair, a photograph schedule corresponds to a binary vector:

where x 1 = l if the corresponding pair (photo, camera) is present in the schedule, and x; = 0 otherwise.

For example, if P = {p 1 , p 2 , p 3 ) where p 1 and p 2 are mono photographs and p 3 is a stereo photograph, then x = (1, 0, 0, 0, 0, 0, l) represents a schedule in which p 1 is taken by camera 1, p 2 is rejected and p 3 is taken by cameras 1 and 3. (Remember that a stereo photograph requires the front and the rear cameras simultaneously.)

Evaluation of a schedule.

Define the profit of a pair (p, camera) (or its 0-1 variable) to be the pro f it of the photograph p. The total profit of al! the pairs of the given set P is then represented by a vector: g = ( g,, gz, • • •, gm ) where gi = g ; (i # j) if g i and g .i cmTespond to two different pairs of elements involving the same photograph p, i.e. (p, camera_x) and (p, camera_y).

Then the total profit value of a schedule x = (x 1 , x2, ... , Xm) is the surn of the profits of the photographs in s, i.e.

• Binary constraints

The constraints involving the non overlapping of two trials and the minimal transition time between two successive trials of a camera, and also some constraints involving limitations on instantaneous data flow are conveniently expressed by simple relations over two pairs (photo, camera). Such a binary constraint corresponds to forbidding the simultaneous presence of a pair (p;, ki) and another pair (P . i, k . i) in a schedule. If Xi and x,1 are the corresponding decision variables of such two pairs, then a binary constraint is defined as follows:

Let C2 denote the set of ail such pairs (x;, x j) which should verify the above binary con straint.

• Ternary constraints

Sorne constraints involving limitations on instantaneous data flow cannot be expressed in the form ofbinary constraints as above. These rernaining constraints may however be expressed by relations over three pairs (photo, camera). Such a ternary constraint corresponds to forbidding the simultaneous presence ofthree pairs (p;, k;), (p j , k j ), and (p 1 , k 1 ). Letting xi, x j and x 1 be the decision variables corresponding to these pairs, then such a ternary constraint is written: x1+xj+x1::;2 Let C3_1 denote the set of all such triplets (x,, Xj, x 1 ) which should verify this ternary constraint.

Finally, we need to be sure that a schedule contains no more than one pair from { (p, ki ), (p, kj), (p, k 1 )) for any (mono) photograph p. Letting x 1 , Xj and x 1 be the decision vari ables corresponding to these pairs, then this (ternary) constraint is expressed as:

Clearly there are exactly ni ternary constraints ofthis type. Let C3_2 denote the set of ail such triplets (xi, Xj, x1) which verify this second type of ternary constraints. Use C3 to denote the union of C3_] and C3_2, i.e. C3 = C3_] U C3_2.

Final mode/.

Now the DPSP can be formally stated as the following generalized 0/1 Knapsack problem: Max.f(x) = L g, • x, 1::':::. i -:Sm where X = (x,' X2, ... , Xm) E (0, 1 l m and g = ( g,, g2, ... , g,n ) E z +m subject to 1) Î:J< i < m Ci• Xi ::'S Max_capacity with Max_capacity E z + and C =-(Ci , C2, ... , Cm) E z + m 2) V(Xt,Xj) E C2,x 1 +xj :" 1 3) V(xt,Xj,Xk) E C3_1,x, +xi +x, :" 2 4) V(x,, Xj, x,) E C3-2, x, + Xj + x, :" 1 This formulation is a special instance of the multidimensional knapsack problem (MKP) [START_REF] Martello | A heuristic solution procedure for the multiconstraint zero-one knapsack problem[END_REF]. However, let us point out a notable difference. While the constraints in a MKP are ail "knapsack constraints" like Eq. (1 ), the formulation above has a single "knapsack constraint" and three types of "logic constraints" like Eqs. [START_REF] Bensana | Exact and approximate meth ods for the daily management of an earth observation satellîte[END_REF][START_REF] Chu | A genetic algorithm for the multidimensional knapsack prob\em[END_REF][START_REF] Dammeyer | Dynamic tabu list management using reverse elimination method[END_REF]. Moreover, while the number of constraints in a MKP is rarely large (for instance, well-known benchmark prob lems have at most 30 constraints), the number of logic constraints may be very high (up to 36000 for some solved instances). Therefore, special techniques are needed for handling these constraints in an effective way.

A TS algorithm for DPSP

Revie>v ofTS

This section gives a brief review of Tabu Search, emphasizing the most important features which have been implemented in our TS algorithm. For a comprehensive presentation of TS, the reader is invited to consul! the recent book by Glover and Laguna [START_REF] Glover | Tabu Search[END_REF].

Tabu Search is a meta-heuristic designed for tackling hard combinatorial optirnization problems. Contrary to randomizing approaches such as SA where randornness is extensiveJy used, TS is based on the belief that intelligent searching should embrace more systematic forrns of guidance which are based on adaptive mernory and learning.

TS can be described as a forrn of neighborhood search with a set of critical and comple mentary components. For a given instance of an optimization problem (S, f) characterized by a search space S and an objective fonction f, a neighborhood N is first introduced to associate, for each sin S, a non-ernpty subset N(s) of S. A typical TS algorithrn begins then with an initial configuration s in S and then proceeds repeatedly to visit a series of locaJly best configurations fol!owing the neighborhood function. At each iteration, one of the best neighbors s' E N(s) is sought to replace the current configuration even ifs' does not improve the current configuration in terms of the cost fonction. To avoid the problem of possible cyc!ing and to allow the search to go beyond local optima, TS introduces the notion of tabu list, which is a foundation for the sh01i term memory component of the method.

A tabu list rnaintains a selective history H, composed of previously encountered solutions or, more generally, pertinent attributes of such solutions. A simple TS strategy based on this short term rnemory H consists in preventing solutions of H from being reconsidered for the next k iterations, called the tabu tenure. The tabu tenure can vary for different attributes, and in general is problem dependent. At each iteration, TS searches for a best neighbor frorn this dynamically modified neighborhood N(H, s), instead of N(s) itself. Such a strategy prevents the search from being trapped in sh01i terrn cycling and imparts rigor to the search.

By means of the tabu restriction mediated by this memory, some non-visited, yet inter esting solutions may be prevented from being considered. Accordingly, aspiration criteria are introduced to overcome this problem. A simple and widely used aspiration criterion consists of removing a tabu classification from a rnove when the move leads to a solution better !han the best obtained so far.

1\vo other important ingredients of TS are intensification and diversification [START_REF] Glover | Tabu Search[END_REF]. Inten sification consists in focusing the search to exploit regions of the space, or characteristics of solutions, that the search history suggests are promising. For example, it may be applied to seek improved solutions by incorporating "good attributes" of previously encountered solutions. On the other band, diversification undertakes to explore regions that differ in significant respects from regions previously visited.

Components of the TS algorithm

Unconstrained and constrained search space

Definition 1. The unconstrained search .'J pace S is composed of all binary vectors of m elernents:

S = { (x,, X2, ... , x,,,) E {O, I ) "' )
The size of S may become huge for high values of m. For some instances we solved, the value of m can be as large as 2355, implying a search space of 2 2355 . However, a solution must verify lhe constraints defined by Eqs. ( 1)-( 4) and thus belongs to a constrained space. This leads to the following definition.

Dejinition 2. The totally constrained search ,space X is composed of all binary vectors of m elements, satisfying the "knapsack constraint" and the "logic constraints," i.e. X = {s E S I s satis fies ail the constraints defined by Eqs. ( 1)-( 4)} 1 ln general, an algorithm may work with either Sor X. It is equally possible for an a}gorithm to work with an interrnediary space where some constraints are relaxed. lt is this last approach which is adopted in this work. For this purpose, we define a partially constrained search space C where the knapsack constraint (Eq. ( 1)) is relaxed.

De finition 3.

The partially constrained search space C is cornposed of all binary vectors of m elements, satisfying the "logic constraints," i.e. C = { s E S I s verifies the Jogic constraints defined by Eqs. ( 2)-( 4)} Note that not all the configurations in C are equally interesting. For example, s = ( 0, 0, ... , 0) is trivially in C but far from any global optimum. The following definition identifies a subset of C which is particularly interesting from the point of view of the profit fonction.

De. finition 4. The saturated partially constrained search space M is a subset of C such that:

M = {s E C I V(xi = 0) E s,
setting Xi = I violates some binary or ternary constraints defined by Eqs. ( 2) and (3 ) } Thus a configuration s E C is saturated when no more pair (photo, camera) can be added without violating some logic constraints.

The saturated set M is similar to the notions of "critical events" 18] and "promising zones" [START_REF] Hanafi | An efficient tabu search approach for the Q-.1 multidimensiona! knapsack problem[END_REF] developed for the MKP. The p rinciple here is that the TS algorithm will search for its solutions in the partial ly constrained search space C and try to sta y at the frontier of this saturated ( p romising ) area.

Neighborhood and move.

We introduce now the neighborhoodfunction Nover the partiaily constrained search s p ace C. More p recisely, this tll.nction N:

C -+ ( 2 c -0 ) is defined as follows. Lets = ( x i , x2, ... , x 111 ) E C and s' = ( x ; , x�, ... , x;), then s' is a neighbor of s, i.e.
s' E N ( s ), if and onl y if the following conditions are verified:

1) 3 ! ; such thatx; = Oanctx ; = 1 ( 1 S i S m )
2 ) for the above i, V(x;, Xj ) E C2, x ; = 0 ( 1 S j S m )

3 ) forthe abovei,V(x;,Xj,Xk ) EC3_1,x ; +x ; S 1 (1 :,j,k:,m) Thus, a neighbor of s can be obtained by adding a pair (photo, camera) (flipping a variable X; from O to 1) in the current schedule and then dropping some pairs (photo, camera) (flipping some x j from 1 to 0) to repair binary and ternary constraint violations. Consequently, a move mv to obtain a neighbor s' from a configurations = (xi, x2, x3, ... , Xm ) is characterized by a series of flipping operations:

xi from O to 1
XJ from 1 to 0

x, from 1 toO where x; ... xk are variables linked to Xi by a binary or ternary constraint. We use mv(i) =

(xi : 0 ----fr-1, Xj ... xk : 1 ---:>-0) to denote such a move.
The repair of a violation of a binary constraint ( x ; , x j) E C2 is a simple operation:

it sufficies to set xf, to O in s' (xj = l in s). Repairing a ternary constraint violation (x;, XJ, Xk) E C3 is.more complex since there are different ways to proceed. For example, one may set either xj or x{ to Oin s 1 randomly or according to some criteria, one may set both xj and xf to O and so on. More details on this topic are discussed later (Section 5.3).

It should be clear that f rom a configurations = ( x i , x2, ... , Xm), the number of possi ble moves equals the number of variables in s having value O. Letting Z = {x 1 Es I s = (x 1 , x 2 , ••• , x m ) and x, = 0), then N (s) has exactly IZI neighboring configurations.

Note that similar neighborhoods based on adding-dropping have been used in many heuristic algorithms for MKP [3-6, 8, 11, 13]. However, one difference remains that con cerns the repair operation after adding an element; constraint repairing here is much simpler since it concerns only binary and ternary logic constraints.

Incremental evaluation of the neighborhood.

TS uses an aggressive search strategy to exploit its neighborhood, i.e. at each iteration, the TS algorithm examines the value f(s') for each candidate neighbor s' E N (s) and chooses one that has the best value. In order to do this in an efficient way, we use an incremental evaluation technique. The main idea is to keep in a special data structure O the move value for each possible move (neighbor) of the cun-ent configuration. Thus ifs' = s + mv(i), then o(i) is equal to the difference f(s') -f(s). Each time a move is carried out, the elements of this data structure affected by the move are updated accordingly.

Since the number of possible moves for each configuration is defined by I Z 1 (1 Z I S m ), the data structure O can be implemented with a vector of m elements: 8(i) gives the move value f(s) -f( s') if the con-esponding move mv(i) is carried out. The vector can be initialized at the beginning of the search and updated after a move in time O(IC2_i 1 + IC3_i 1) where C2_i and C3_i are subsets of the sets of binary and ternary logic constraints (see Section 2.2) involving the element x;. Searching for a best move within 8 requires time O (m ).

Tabu list management.

The role of a tabu list is to prevent the search from short-terrn cycling (x;: 1-+ 0 ➔ 1 ➔ 0 • • •). Remember that a move mv(i) = (x;: 0 ➔ l, x.i ... Xq: I ➔ 0) consists in fl ipping x, from O to 1 and flipping then x .i, ... , x q from 1 to O (to repair constraint violations). Each tirne such a move is carried out, the moves mv(j) = (xj 0 ➔ 1, , , ,) , , , mv(q) = (x q : 0 ➔ 1, , , ,) are classified tabu during some iterations (tabu tenure), forbidding to reset any of Xj,,,,, Xq from 0 to L The number of iterations k(t) during which a move mv(t) (t = j , , , q) is classified tabu is dynamically defined as follows:

k(t) = C(t) + a x FREQ(t)
where C (t) is the number ofbinary and ternary constraints involving the elementx,, FREQ(t) the number of times x r is flipped frorn l to O from the beginning of the search, and a = (L 1 <i<m C(i))/ m reflecting the hardness of an instance in terms of logic constraints.

Therefore� the tabu tenure of a move depends on two factors: the number of constraints containing the variable of the move and the flipping frequency of the variable.

The idea for the first part of the fonction C(t) is the following, A variable involved in a large number of constraints bas naturally more risk to be flipped during a move than a variable having few constraints on it. It is thus logic to give a longer tabu tenure for a move whose variable has many constraints on it. Therefore, each time x 1 is flipped from l to 0, x 1 cannot be reset to 1 until at least C(t) iterations have been realized. Similarly, a move concerning a variable involved in a low number of constraints is given shorter tabu tenure.

The second part of the function is dynamic and proportional to the flipping frequency of the variable x 1 (from 1 to 0). The basic idea is to penalize a move which repeats too often. The coefficient ais instance-dependent and defines a penalty factor for each move. For the instances we solved, the values of a vary from 10 to 30.

At this stage, let us notice that FREQ(t) is the essential part in the above tabu tenure function. Other frequency-based tabu tenures are also possible. For instance, the following ones have been experimented.

k2(t) = FREQ(t) k3(t) = a x FREQ(t) (ais a constant) k4(t) = C(t) + FREQ(t)
In practice, we observe that all these formulae lead to comparable results in term of quality of the solutions found. However, according to the formula used, the resolution time may be quite different. lndeed, for a same solution quality, the search using formula k(t) requires in general much shorter tirne.

It should now be clear that using the frequency of a move to tune the tabu tenure of the move may be considered as a general princîple and thus applicable to other problems.

Finally, in orderto implernent the tabu list, a vector T of m elements is used. As suggested in [START_REF] Glover | Tabu Search[END_REF], each element T(i) (1 :S; :Sm) records k(i) + iter, instead of k(i) where iter is the current number of iterations. In this way, it is very easy to know if a mv(i) is tabu or not at iteration ): if T(i) > j, mv(i) is a forbidden move; otherwise, mv(i) is a possible move,

Aspiration criteria.

The tabu status of a rnove mv(i) is canceled if one of the two conditions (two-level aspiration criteria) below is verified.

1) if the move mv(i) leads to a configurations strictly better than the best configuration s* found so far, i.e. /(s) > f(s*) even ifs requires more memory, 2) if the move mv(i) leads to a configurations of the sarne quality buts occupies Jess memory, i.e. f(s) = f( s* ) and L i ::::i:sm ci• Xi < L i ::::i:sm c; • xt.

3.3.6.

Heuristics for carrying out a move. Lets be the current confi guration at a given iteration. Let M be the set of candidate moves from s, i.e. the moves which are not forbidden by the tabu list and the moves which verifies the aspiration criteria. Now, ail the best moves (i.e. those having the highest 8(i) values) are identified and then one of them is chosen at random. Once such a move is determined, a best neighbor s' of s is obtained (s' = s + mv(i)). Before moving to the next iteration, corresponding data structures such as T (tabu list) and 8 (table of move values) are updated accordingly.

7. Intensification and diversification.

The tabu mechanism may lead to a state where no move is admissible. This occurs when each possible move has been tried a large number of times without improving the best confi guration found. When this happens, an intensifi cation phase will be started.

The intensification used by the algorithm is based on a heuristic using long-term infor mation: if an element is present in a large number of good confi gurations, then it is highly possible that this elernent is part of an optimal configuration. Heuristics of this kind are presented in [START_REF] Glover | Tabu Search[END_REF] and used by many TS algorithms.

To implement this heuristic, the algorithm uses a vector ker* of m elements ker* = (k,, k2, ...• k,,,) to collect high frequency elements. This vector is updated dynamically. f ollowing one of the two ways below.

• Each time the algorithrn finds a configurations= (x1, x2, ... , x 111 ) giving the same profit as the best one found, i.e. f (s) = .f"', ker' is updated as follows:

ker' = (x 1 • k 1 • x 2 • k 2 • ... , Xm • k111).
• Each time the algorithm finds a configurations= (x1, x2, ... , x 11i ) having a better profit than the best one found, i.e. f (s) > f*, ker* is reset to s, i.e. ker* = s.

From the vector ker*, we construct the search space / (for intensification) of indices of ker' in the following way. Let To _l be the set of indices of ker' that are equal to l and To_O those equal to O. Then the set / _ç To_O contains such indices of elements that the flipping of these elements does not affect the elements of To_ 1 even after repairing the logic constraints. The set l corresponds thus to regions of the search space where the elements of ker* are fixed. During an intensification phase, the algorithm mns on the set / and from the initial configuration sü = ker*. In this way, the intensification forces the search to exploit exclusively the areas around the kerne1 ker*. However, it is possible that ker" corresponds to a set of configurations trapped in a local optimum. lt is for this reason that the algorithm builds dynarnically another set D (for diversification) which collects the indices of elernents having a fl ipping frequency lower than the average. Thus the set D corresponds to less visited regions of the search space. During a diversification phase, the algorithm runs exclusively on the set D and from the initial confi guration sO = O. In this way, the diversification drives the search to explore areas that are either new or have not been visited very often.

Relaxation of the capacity constraint.

During the search, the capacity (knapsack) constraint may be violated by the current configurations= (x1, x2, ... , x m ), i.e., the total size of s may exceed the maximal allowed capacity CL i : : J:s m c 1 • X i > Max_capacity). To satisfy the capacity constraint, the following mechanism is devised. Each time the current configuration is improved, the capacity constraint is checked. If the constraint is violated, the configuration is irnmediately repaired by suppressing the elements Xi which have the worst ratio gi /ci until the capacity constraint is satisfied, i.e. L l:é.i:'Sm c; • Xi � Max_capacity.

Note that since we have only one knapsack constraint, the relaxation handling is much simpler compared with the techniques used for the MKP 18, 10, 11, 15]. lndeed, for the MKP, one must decide how many and which knapsack constraints are to be relaxed. Non trivial special techniques are also needed to deal with the relaxed constraints.

General algorithm.

The TS algorithm follows a general schema composed of three iterative phases: exploration, intensifi cation and diversification. The skeleton of the TS algorithm is given below. search over all the elements of the partially constrained space C (Section 3.2) whenever a non tabu move exists compute the set I and the set D (Section 3. The general stop condition is defined by a maximum number of iterations allowed. The algorithm returns the best solutions* found during the search. An alternative condition can be used to stop the algorithm when a given value of the profit fonction is reached.

The different phases (exploration, intensification and diversifi cation) use the same tabu search engine ( with different search spaces C, / and D). Each phase is triggered and stopped automatically by the tabu list management (Section 3.3.4), i.e. whenever no more moves are admissible. This is particularly the case for intensification and diversification. This app roach is quite different from previous work on MKP where the rhythm of intensification and diversification phases are controlled by some supplementary parameters [8, 10, l l]. Finally, it should be noted that the tabu list management is claimed to be dynamic, however, in a different meaning than that described e.g. in [START_REF] Dammeyer | Dynamic tabu list management using reverse elimination method[END_REF].

Experimentation and results

Test data

Experiments are carried out on a set of 20 realistic instances 2 provided by the French National Space Agency CNES and described in details in [l]. We sketch here only some main characteristics of these instances.

These instances belong to two different sets: without capacity constraint (l3 instances) and with capacity constraint (7 instances). For the instances of the first set, the optima are known thanks to two exact algorithrns: a CPLEX commercial software using an ILP formulation and a non-standard Branch and Bo und algorithm using a Valued Constraint Satisfaction Problem (VCSP) formulation [START_REF] Verfaillie | Russian doll search for solving constraint optimization prob� lems[END_REF].

For the instances of the second set, existing exact algorithms are unable to solve optimally these instances except the smallest one, due to the existence of the capacity constraint and the large size. For these instances, only sub-optimal solutions are known, which have been obtained by another tabu search algorithm [START_REF] Bensana | Exact and approximate meth ods for the daily management of an earth observation satellîte[END_REF].

Experimental settings

Our TS algorithm is programmed in C, and compiled using VisualC++ on a PC running Windows NT (32 MB RAM, 200 MHz). To obtain our computational results, the TS algo rithm is run 100 times on each instance with different random seeds. Two stop conditions are used, when a given profit value is reached or when a gîven maximum number of itera tions are realized. The tabu tenure is managed dynamically and automatically according to the formula given in Section 3.3.4.

Results on instances without capacity constraint

Sin ce the optima are known for this set of instances, the algorithm is stopped when a solution of an optimal profit value is f ound. We wish to know whether our algorithm is able to find the optimal solutions for the instances in this set. Table 1 shows the results of the TS algorithm on these instances.

For each instance, the following information is given. The first 4 columns give the name of the instance, the number of candidate photographs n in P, the number of 0/ 1 variables m and the known optimum. Columns 5-6 give the best (maximal) profi t found by the TS algorithm, the minimal number of iterations needed to find a solution of such a profi t. Columns 7-8 indicate the number of iterations and the running time needed to fi nd a solution averaged over l 00 runs. Columns 9-10 indicate the maximal and minimal numbers of selected photographs among 100 solutions. Columns 11-12 show how similar these solutions are when they are compared in pairs: the maximum and the minimum of the (100 * 99)/2 bit-wise comparisons are given.

The last column indicates the number of distinct solutions among the hundred solutions found.

Thus the fifth line means that the instance called 28 has 230 mono and stereo candidates corresponding to 346 binary variables and an optimal schedule has a profit of 56053. The TS algorithm finds a solution of profi t 56053 (optimal value) after 88 iterations (in average 1296 iterations and one second over 100 runs). Any schedule among 100 solutions found contains al least 46 and at most 47 photographs. When the 100 schedules are compared in pairs, at least 7 and at most 46 pairs (photo, camera) are shared by two schedules. Finally, among (100 * 99)/2 possible pairs of schedules, 95% of them are different. Now let us make several comments about these results. First, the TS algorithm is very effi cient and robust for these instances. lndeed, for each instance and for each of 100 runs, the al gorithm is able to fi nd an optimal solution. (It is for this reason that only the average iterations and cornputing times over 100 runs, but not the average profit are given in the table.)

Secondly, the TS algorithm is fast. Indeed, both the number of iterations and computing lime needed to find an optimal solution are quite low (fewer than 140000 iterations for 29 seconds for the larges! instance). On average, the algorithm performs 3715 to 8372 iterations per second.

Thirdly, these instances seem highly constrained since only a small number of candidate photographs are selected in an optimal solution (column 9-10). We observe also that except for three instances, all the optimal solutions found (100 for each instance) are different, though they share always a subset of pairs (photo, camera). This implies that these instances probably have rnany optimal solutions, therefore are easy to solve.

Results for instances with capacity constraint

Contrary to the instances without capacity constraint, no optimal solutions are known for this set of instances except for the smallest one. Only sub-optimal ones are available, the best of them being produced by another TS algorithm developed by the CNES (we discuss this algorithm later in Section 5.1).

To solve an instance, our TS algorithm is allowed to run 9 million iterations. This corresponds to about one hour of computing time for the largest instance ( del a y considered reasonable by the CNES and used by the TS algorithm of the CNES). Once again, the TS algorithm is run 100 times on each instance with different random seeds. Table 2 gives the results of the TS algorithrn together with the best known results (sub-optirna) for these instances.

For each instance, the following information is indicated. The first 3 columns have the same meaning as for Table 1. Columns 4-5 show the profi t and computing time (in seconds) 3 of the best known solutions. Columns 6-7 give, for the best solution found by our TS algorithm after l 00 runs, the profi t value and the number of iterations needed to find such a solution. Columns 8-10 show the avern.ged profit, number of iterations and computing tirne over 100 runs. The last column gives the profit of the worst solution found by the TS algorithm over 100 runs.

From the data in Table 2, we may make the following remarks. First, these instances are much harder than those of the first set, essentially due to the large number of variables and "logic constraints" (up to 2355 0/1 variable or 1057 integer variables, and more than 30 000 constraints). Secondly, ail the solutions (even the worst ones) produced by our TS algorithrn improve on the best known results, both in terms of solution quality and speed of execution. The quality irnprovernent is important, reaching a gain of more than 2000 units of the profit fonction in most cases. Moreover, the computing time needed to obtain such a solution satisfies by far the "one hour" constraint (40 minutes for the largest instance). Thirdly, the TS algorithm seems very robust because the quality variations of the 100 solutions for each instance remain small.

In order to see how difficult it is to reach a previously published best solution, another experiment is carried out. We re-ran 100 times the algorithm on each instance and stopped a run when the best known profi t value is reached. Averaged results of this experiment is reported in Table 3.

From this table, we sec that only one second upto a few minutes are needed to obtain the previously best solutions. Compared with the previous computing times (Column 4), the running times of our TS algorithm represent only a very smalt f r action (last Column).

Table 4 gives more information about the solutions found by indicating the maximal and minimal numbers of selected photographs among 100 solutions, and the similarity between these solutions.

From Table 4, we see that as for the instances without capacity constraint, these in stances are also highly constrained. Indeed, only about one third to one half of candidate photographs are selected in a solution. Once again, the solutions found for each instance always share some elements (photo, camera), but the solutions are all ditferent. This implies that these instances have probably many (sub-optimal) solutions for a given profit value. This may be considered as an indicator that these results may be further improved. As mentioned before, both exact and non exact algorithms have been developed for the DPSP. We describe here briefly two such algorithms: an exact algorithm called Pseudo Dynamic Search (PDS) [START_REF] Verfaillie | Russian doll search for solving constraint optimization prob� lems[END_REF] and another TS algorithm developed by the CNES [START_REF] Bensana | Exact and approximate meth ods for the daily management of an earth observation satellîte[END_REF]. Let us notice first both algorithrns are based on an integer formulation of the problem: each variable represents a candidate photograph and is associated to a value domaîn of {0, 1, 2, 3} or {O, l 3} according to whether it is a mono or stereo photograph. A configuration in the search space corresponds thus to a n-dimensional integer vector for a problem composed of n candidate photographs. The PDS algorithm is an hybridization of dynamic programming and Branch & Bound (B&B) techniques. This algorithm consists in performing n searches (n being the number of variables of the problem). each solving. with a depth first B&B, a sub-problem limited to a subset of the n variables. Once a sub-problem is solved, its best profit value is recorded. This value is then used later as a lower bound for another unsolved sub-problem. This algorithm bas proven the optimality for the 13 instances without capacity constraint (but failed for the instances with capacity constraint).

The TS algorithm of the CNES, denoted by TS-CNES hereafter, is qui te different from our algorithm. First, TS-CNES uses a different (integer)formulation of the problem. Secondly, it manipulates only feusible configurations, i.e. those verifying all the constraints of the problem. Thirdly, it uses a different neighborhood. Fourthly, it considers only a subset of neighboring configurations to make a move. This is probably because no incrementa1 evaluation technique is available. Fifthly, the tabu tenure for each move is randomly taken from predefined (very small) ranges: (3 .. 5) for problems of size Jess than 500 candidate photographs and (7 .. 10) for larger ones.

The TS-CNES algorithm has been compared with various forms of greedy and simulated annealing algorithms and proved to be the best non-exact algorithm. Compared with our TS algorithm, however, TS-CNES is Jess effective in terms of search power and speed of execution. Indeed, as shown in Section 4, our TS algorithm significantly improves upon the best results of the TS-CNES algorithm for both sets of instances (let us mention also that TS-CNES failed to find an optimal solution for 4 of the 13 instances without capacity constraint [START_REF] Bensana | Exact and approximate meth ods for the daily management of an earth observation satellîte[END_REF]).

Upper bounds

The computational results reported in this paper are much better than the previous best ones, in particular for the instances of the second set with capacity constraint. Now, we can ask how far these results are from optimal solutions. Currently, no definitive answer is known yet since all previously atternpts for finding optimal solutions failed. Another possible answer to this question consists in seeking strong upper bounds. In this section, we review the known studies in this area.

One obvious solution concerns the continuous linear programming. However, it is well known that this approach could lead to a significant gap between the optimal discrete and continuous values. Eric Bensana et al. have applied this approach to the problem described in this paper [START_REF] Bensana | Exact and approximate meth ods for the daily management of an earth observation satellîte[END_REF][START_REF] Verfaiilie | Personalcommunîcations[END_REF]. They have used CPLEX, an efficient implementation of the simplex algorithm, to solve the relaxed problem (integrity constraints relaxed). Eric Bensana et al. reported continuous optimal values (COV) which are largely above the discrete optimal values (DOV) for the instances of the first set (Recall that optimal values are known for these instances). In fact, the ratio (COV-DOV)/COV goes from 28% to 74%! Even if they have not reported bounds on the instances of the second set, it is reasonable to believe that LP bounds on these instances should be much worse, given the fact that the instances of the second set are much larger and much more difficult.

Very recently, another attempt has been reported, which tries to tighten the bounds with a new ILP formulation of the problem and the column generation technique [START_REF] Gabre | Improved linear programming bounds via column generation for daily scheduling of earth obser vation satellite[END_REF]. In this new formulation, the initial problem is decornposed into three independent sub-problems, one per camera. For the resolution of the problem, CPLEX 4.1 is employed, together with a column generation procedure. This approach improves the previous bounds for the instances of the first set, reducing the (COV-DOV)/COV ratio to the range of 0% to 20%. However, like for the initial ILP formulation, no bound was reported for the instances of the second set, due to the huge number of columns that have to be generated during the resolution.

Currently, studies continue on upper bounds for the instances of the second set. lt should be clear that deriving good upper bounds for these instances is quite difficult and constitutes itself a challenging research topic.

Repairing logic constraints

As indicated in Section 3.3.2, binary or ternary constraint violations are repaired when a rnove is carried out. A binary constraint violation is easy to repair since there is a single way to do this. However, the case for a ternary constraint violation is more complicated since there are different ways to achieve such a repair. Suppose that x. i = xk = l and the move sets xi to 1. The constraint Xi + x. i + xk =:: 2 is thus violated and needs to be repaired. Four cases are possible:

1) set bath XJ and xk to 0, 2) randomly set either x.i or Xk to 0, 3) set to Othe element which bas a smaller profit, 4) look ahead in an exhaustive way to determine the best choice in terms of lost profit.

We have tested and compared these possibilities on all the instances used in this study. We observe that 3) and 4) give significantly better results than the other ones. ln choosing between 3) and 4), the technique 4), which is more time consuming, gives slightly better results than 3) in a few cases. For the instances used in this study, experirnents showed that no more than 5 elements need to be reset to repair a ternary constraint violation after a rnove, implying that an exhaustive look ahead is still possible. For the cases where more elements need to be forward-checked, the technique 3) should be the best choice.

Handling the capacity constraint

The algorithm presented so far works within the partially constrained search space C (Section 3.2. 1 Definition 3). The capacity constraint is relaxed, i.e. during the search, the total capacity of the current configuration may exceed the maximal allowed capacity. An alternative is to impose the satisfaction of the capacity constraint during the search. ln this case, the algorithm works within the totally constrained search space and manipulates only feasible configurations. However, the relaxation of the capacity constraint helps to obtain better results and to accelerate the search. Intuitively, optimal or high quality sub-optimal solutions are located at the frontier of feasibility. Often these solutions are difficult to reach uniquely from the feasible side. A more effective way is to allow the search to oscillate around the feasibility frontier, increasing the chance to reach good solutions. Strategies of this kind have been successfully applied to the MKP [START_REF] Glover | Critical event tabu search for multîdîmensional knapsack problems[END_REF][START_REF] Hanafi | An efficient tabu search approach for the Q-.1 multidimensiona! knapsack problem[END_REF]. We show below that this is also the case for our application, even if the relaxation technique we used is different frorn those developed for the MKP.

To illustrate these points, experiments have been carried out to compare two versions of our algorithm with and without capacity constraint relaxation. We re-run these two versions for the same number of iterations and compare the quality of the solutions found. From these figures, we observe that the relaxation technique gives solutions of better quality for the same search effort. Moreover, the relaxation version of the algorithm needs fewer iterations to reach a solution of the same quality. Finally, the relaxation version is much more robust since it is Jess sensitive to the initial randorn seeds used.

Conclusions

In this paper, we have introduced a "logic constrained" knapsack formulation for a real world application, the photograph daily scheduling problem of the satellite Spot 5. Based on this formulation, we have developed a highly effective tabu search algorithm. This algorithrn incorporates some important features including an efficient neighborhood, a fast and incremental technique for move evaluation, a method for automatic tabu tenure management, and intensification and diversification mechanisms.

Computational results on a set of realistic benchmark instances have showed the effec tiveness of this algorithm. For the instances without capacity constraint, the algorithm finds all optimal solutions very easily, For the instances with capacity constraint, the algorithm finds with little computational effort previously best known results. More importantly, the algorithm significantly improves upon the best known results using Jess than one hour of computing time on a pentium PC.

An analysis of the solutions ( 100 for each instance) produced by the algorithm showed that only one third to half of the candidate photographs are retained in a schedule, indicating that these instances are highly constrained. We observed that the solutions found for a given instance are quite different, though they do share some elements in common. This implies that the density of solutions for a given profit is probably high. Therefore, we conjecture that if the obtained results (for the instances with capacity constraint) are not optimal, they may be further improved by more powerful search methods.

Unfortunately, for the moment nothing is known about the distance between the solutions found and optimal solutions. An exact algorithm would allow us to answer definitively this question. Given the hardness of these instances, a more realistic approach would be to develop more powerful techniques for deriving strong upper bounds. 4

  f ( x ) = L g; -x; lsism 2.2.3. Constraints • Capacity constraint Define the size of a pair (p, camera) (or its 0-1 variable) as the size of the photograph p. The total size of all the pairs of the given set P is then represented by a vector: where ci = cj (i f. j) if ci and Cj correspond to two different pairs of elements involving the same photograph p, i.e. (p, camera_x) and (p, camera_y). The capacity constraint states that the sum of the sizes of the photographs in a sched ule x = (xi, Xz, ... , X m ) cannot exceed the maximal recording capacity on board. This constraint is easily expressed as a knapsack constraint: L Ci • Xi :5: Ma:ccapacity 1:::ë_iSm

l) 2 )

 2 Set No. 1 (without capacity constraint): The first set includes l 3 instances having 67 to 364 candidate photographs, giving up to 809 binary variables and 14175 constraints. Set No. 2 (with capacity constraint): The second set includes 7 instances having 209 to 1057 candidate photographs, giving up to 2355 binary variables and 35933 constraints.

Figure 1 .

 1 Figure 1. Comparative results without (a) and wîth (b) capacity constraint relaxation.

Figure !(

  Figure !(a) and (b) show the comparative results on the instance 1504 (20 runs for each version of the algorithm, each run being given 300 000 iterations).From these figures, we observe that the relaxation technique gives solutions of better quality for the same search effort. Moreover, the relaxation version of the algorithm needs fewer iterations to reach a solution of the same quality. Finally, the relaxation version is much more robust since it is Jess sensitive to the initial randorn seeds used.

Table 1 .

 1 Results on instances without capacity constraint.

								No. of photos
	Pb.	" m	opt.	Best profit	iter	Average prefor. iter time(s) max. selected min.	Similarity max. min. solution Distinct
	54	67 [25	70	70	7[	280		45	45	45	29	63
	29	82 120	[2032	12032	35	8[		34	34	34	[8	97
	42 190 304 [08067 [08067	llO	29[		80	80	76	38	[00
	28 230 346	56053	56053	88	1296		47	46	46	7	95
	5 309 809	115	[ [5	256	26007	7	96	93	7[	15	[00
	404 100 158	49	49	36	596		33	31	31	15	[00
	408 200 328	3082	3082	684	8479		63	60	52	23	100
	412 300 544	16102	16102 831	33278	5	79	77	67	23	100
	li 364 692 503 143 259	22120 9096	22120 1540 133889 9096 84 907	29	98 70	95 69	84 55	33 25	100 100
	505 240 448	13100	13 IOO	910	25116	3	85	82	66	28	100
	507 311 573	15137	15137 1885	97489	18	92	89	73	32	100
	509 348 652	19125	[9125 2094 l04408	22	96	93	78	29

Table 2 .

 2 Results on instances with capacity constraînL

				Best known		Best		Average
	Pb.	n	m	profit		tîme(s)	profit	iter*	profit	iter	time(s)	Worst profit
	1401	488	914 174058		846	176056	4690	!76055	547882	120	176053
	1403	665 l 317 174137		1324	176137 177354 176134 816099	332	176133
	1405	855 1815 !74174		1574	176!79	5191155	176175 1418907	1314	176171
	1021 1057 2355 174238		2197	176246 8279411 176241 1707156	2422	176234
	1502 1504	209 605 1253 124238 61158' 1	'	13 1011	61158 124243	235 !96064	61158 !2424! 1092197 1067	405	61158 124239

Table 3 .

 3 Effort to reach a previously best rcsulL

		Pb.		Cost	Time(s)	Ratio best-known/TS
		1401		174058			846
		1403		174137	4		33!
		1405		174174	30		52
		1021		174238	39		55
		1502		61158			13
		1504		124238	49		21
		1506		165244	196		10
	TGhle 4. More information about solutions found.
				No. of Photos	Similarity
	Pb.	n	m	max.	min.	max.	min.	Distinct solution
	1401	488	914	148	144	127	40	100
	1403	665	1317	213	208	170	65	100
	1405 1021	855 1057	1815 2355	253 318	242 300	189 225	71 82	100 100
	1502	209	413	166	166	114	69	100
	1504	605	1253	280	274	188	102	100
	1506	940	2060	314	299	221	95	100
	5. Discussions
	5.1. Related work

Acknowledgments

We would like to thank gratefully the following people: Dr. Gérard Verfaillie from CERT Toulouse for many useful discussions on this application, Prof. Fred Glover and the referees of the paper for their very useful comments and careful corrections, Steve Hurley for his corrections on the final version of the paper. Thanks go also to the CNES for having defined and made available the tested instances.

Notes

!. Hereafter, we wi!l use the letter s instea<l of x to denote a configuration (x1. x2,. . x ,,, ). 2. These instances are available via ftp from ftp.cert.fr/pub/lemaitre/LVCSP/Pbs/SPOT5.tgz. 3. The TS algorîthm of the CNES is programmed in Fortran 77 and was run on a Sparc 20/50 workstation. 4. Since the final revision of the paper, the authors have obtaine<l tight upper boun<ls; see the paper "Upper bounds for the SPOT 5 daily photograph scheduling problem" by M. Vasquez and J.K. Hao, to appear in Journal of Combinatorial Optimization.