Michel Vasquez

Jin-Kao Hao

Communiqué Par

Gérard Plateau

UNE APPROCHE HYBRIDE POUR LE SAC À DOS MULTIDIMENSIONNEL EN VARIABLES 0-1

Keywords: Sac-à-dos multidimensionnel, programmation linéaire, recherche tabou

Une approche hybride pour le sac à dos

multidimensionnel en variables 0-1

Introduction

Le sac à dos multidimensionnel en variables bivalentes (MKP01) permet de modéliser une grande variété de problèmes où il s'agit de maximiser un profit tout en ne disposant que de ressources limitées. Son expression formelle est la suivante :

MKP01 maximiser c.x s.c. A.x ≤ b et x ∈ {0, 1} n
Reçu en mars 2000. 1 LGI2P, Parc Scientifique Georges Besse, 30035 Nimes Cedex 1, France ; e-mail : vasquez@site-eerie.ema.fr 2 LERIA, Université d'Angers, 2 bd Lavoisier, 49045 Angers Cedex 1, France ; e-mail : Jin-Kao.Hao@univ-angers.fr avec c ∈ N * n , A ∈ N m×n et b ∈ N m . Les coordonnées binaires x j du vecteur x sont des variables de décision : x j = 1 si l'objet j est retenu dans le sac, 0 sinon. c j est le profit (ou gain) associé à l'objet j. Les éléments (a ij ) de la matrice A représentent, pour chaque type de ressource i, la consommation de l'objet j. Enfin les b i sont les quantités disponibles de chacune des m ressources. L'objectif est de trouver un sous ensemble d'objets qui maximise le profit tout en respectant les contraintes de limitation de ressources.

Le fait qu'on le rencontre dans des domaines d'application aussi différents que l'économie [START_REF] Lorie | Three problems in capital rationing[END_REF], l'industrie [START_REF] Dantzig | Discrete-variable extremum problems[END_REF][START_REF] Gilmore | The theory and computation of knapsack functions[END_REF][START_REF] Toyoda | A simplified algorithm for obtaining approximate solutions to zero-one programming problem[END_REF], les transports, le chargement de cargaison [START_REF] Bellman | Applied Dynamic Programming[END_REF][START_REF] Shih | A branch & bound method for the multiconstraint zero-one knapsack problem[END_REF] et l'informatique répartie [START_REF] Gavish | Allocation of data bases and processors in a distributed computting system[END_REF], etc. lui confère un grand intérêt pratique. Ce problème d'optimisation combinatoire sous contraintes est cependant NP-difficile [START_REF] Garey | Computers & Intractability A Guide to the Theory of NP-Completeness[END_REF]. Sa résolution revêt donc, aussi, un caractère théorique toujours d'actualité.

Ainsi de nombreux travaux ont été effectués sur le sujet [START_REF] Aboudi | Tabu Search for General Zero-One Integer Programs using the Pivot and Complement Heuristic[END_REF][START_REF] Balas | Pivot and Complement a Heuristic for 0-1 Programming[END_REF][START_REF] Boucher | Étude des méthodes de bruitage appliquées au problème du sac à dos à plusieurs contraintes en variables 0-1[END_REF][START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF][START_REF] Dammeyer | Dynamic tabu list management using the reverse elimination method[END_REF][START_REF] Drexl | A simulated annealing approach to the multiconstraint zero-one knapsack problem[END_REF][START_REF] Fréville | Heuristic and reduction methods for multiple constraints 0-1 linear programming problems[END_REF][START_REF] Gavish | Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality[END_REF][START_REF] Glover | Critical event tabu search for multidimensional knapsack problems[END_REF][START_REF] Hanafi | An efficient tabu search approach for the 0-1 multidimensional knapsack problem[END_REF][START_REF] Lee | An approximate algorithm for multidimensional zero-one knapsack problems a parametric approach[END_REF][START_REF] Shih | A branch & bound method for the multiconstraint zero-one knapsack problem[END_REF][START_REF] Toyoda | A simplified algorithm for obtaining approximate solutions to zero-one programming problem[END_REF] et beaucoup d'heuristiques sont encore explorées pour proposer des solutions, sinon exactes, du moins approchées à ce problème. En effet les méthodes exactes sont limitées à de petites instances ou à des instances ayant des caractéristiques bien spécifiques : matrice A creuse et quasi unimodulaire, redondance de contraintes etc. Aujourd'hui, la résolution des instances les plus difficiles de MKP01 se réalise donc essentiellement avec des approches heuristiques. L'aptitude de ces dernières à fournir des solutions de bonne qualité les rend indispensables dans le domaine pratique. Elles s'avèrent aussi très utiles pour le développement d'algorithmes exacts fondés sur des méthodes d'évaluation et séparation.

Nous proposons, dans ce papier, une approche hybride qui combine la programmation linéaire et la recherche locale tabou. L'idée fondamentale de notre approche consiste à explorer l'espace de recherche, d'une manière contrôlée, autour d'optima continus de problèmes relaxés. Ainsi nous nous distinguons des approches fondées sur le critère de choix classique du ratio profit/ressource. Pour mettre en oeuvre cette approche, nous proposons d'abord une méthode permettant de déterminer le nombre d'objets à l'optimum de MKP01. Nous développons ensuite un algorithme de recherche locale intégrant un voisinage original et une implémentation efficace de la technique d'élimination inverse pour la gestion de la liste tabou.

Nous validons cette approche sur des benchmarks classiques ainsi que des benchmarks récents réputés difficiles [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF][START_REF] Glover | Critical event tabu search for multidimensional knapsack problems[END_REF]. Nous montrons que cette approche permet non seulement de retrouver les meilleurs résultats connus pour l'ensemble des jeux expérimentés, mais aussi d'améliorer de manière significative les meilleurs résultats pour un grand nombre de jeux les plus difficiles [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF][START_REF] Hanafi | An efficient tabu search approach for the 0-1 multidimensional knapsack problem[END_REF].

Notre exposé s'organise comme suit. Après un état de l'art sur les principales stratégies de résolution (Sect. 2), nous donnons le principe général de notre approche hybride (Sect. 3). Nous développons ensuite la phase de la programmation linéaire (Sect. 4), ainsi que la phase de la recherche locale tabou (Sect. 5). Ces développements sont alimentés par la présentation des résultats expérimentaux (Sect. 6), ainsi qu'une analyse sur les performances de notre algorithme (Sect. 7). Nous terminons par une discussion sur de nombreuses perspectives.

Stratégies de résolution

Afin de situer notre approche dans le contexte général des méthodes de résolution, nous présentons ici, quelques uns des axes de recherche explorés.

Méthodes exactes

Il existe un algorithme pseudo polynômial pour résoudre le MKP01 par la programmation dynamique [START_REF] Bellman | Applied Dynamic Programming[END_REF][START_REF] Gondran | Graphes & algorithmes[END_REF]. Sa complexité O(n m i=1 (b i + 1)) le rend très vite impraticable en fonction de m et des b i .

Les algorithmes d'évaluation et séparation se distinguent essentiellement par le calcul de borne qu'ils mettent en oeuvre pour élaguer l'arbre de recherche. Un premier algorithme de branch & bound [START_REF] Shih | A branch & bound method for the multiconstraint zero-one knapsack problem[END_REF] propose de prendre, comme borne supérieure pour l'évaluation, la valeur min{z 1 (k), ..., z m (k)} où z i (k) est l'optimum du sac à dos ne contenant que la i ème contrainte au noeud k de l'arborescence. La variable de branchement étant alors celle qui correspond à l'élément fractionnaire de ce problème de sac à dos unidimensionnel. L'avantage de cette méthode est qu'elle ne traite que des sacs à dos simples que l'on sait bien résoudre [START_REF] Martello | Knapsack Problems: Algorithms and Computer Implementations[END_REF]. En revanche la borne utilisée est assez imprécise. Dans l'exemple suivant :

exemple 1(n = 4, m = 2)    c = 4 5 4 4 A = 1 3 3 2 3 3 2 1 b = 3 3
z 1 = 8 pour x 1 = (1, 0, 0, 1) et z 2 = 8 pour x 2 = (0, 0, 1, 1), alors que la solution optimale qui tient compte des deux contraintes, est x = (0, 1, 0, 0) et vaut z = 5. Non seulement z est relativement loin de min{z 1 , z 2 }, mais l'information sur les composantes de x est complètement fausse.

L'estimation, plus élaborée, de la valeur potentielle d'un branchement à partir de multiples relaxations (lagrangienne, composite...) et du calcul des multiplicateurs duaux [START_REF] Gavish | Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality[END_REF] donne de meilleurs résultats que le précédent algorithme avec toutefois un accroissement sensible de la complexité de calcul. D'une manière générale les algorithmes d'énumération implicite se heurtent à une combinatoire en O(2 n ). Pour élargir leur domaine d'application à des instances de taille plus grande on peut d'une part chercher de bons minorants par des heuristiques de construction efficaces, et d'autre part réduire la taille du problème par fixation de variables [START_REF] Gondran | Graphes & algorithmes[END_REF], élimination de contraintes [START_REF] Fréville | Heuristic and reduction methods for multiple constraints 0-1 linear programming problems[END_REF] ou encadrement du nombre de variables à l'optimum [START_REF] Fréville | Sac à dos multidimensionnel en variable 0-1 : encadrement de la somme des variables à l'optimum[END_REF]. Ces dernières méthodes font appels aux aspects les plus théoriques de la programmation linéaire.

Méthodes approchées

Plusieurs algorithmes approchés combinent la programmation linéaire avec une heuristique dont l'objectif est de rendre entières des variables continues. En effet, pour utiliser la programmation linéaire il faut supprimer le caractère binaire des variables x j . La relaxation des contraintes d'intégrité est une technique omniprésente dans les méthodes de résolution de MKP01. Elle conduit à la résolution du problème associé à MKP01 suivant :

MKP maximiser c.x s.c. A.x ≤ b et x ∈ [0-1] n .
Les composantes du vecteur x sont, dans le cas de MKP, comprises dans l'intervalle continu [0-1]. MKP se résout efficacement3 par la méthode du simplexe [START_REF] Press | Numerical Recipes in C[END_REF].

La résolution de MKP fournit une borne supérieure z qui, associée aux coûts réduits des variables hors base, permet d'introduire une technique de fixation de variables [START_REF] Gondran | Graphes & algorithmes[END_REF]. Une des techniques consiste à faire entrer les variables d'écart en base [START_REF] Balas | Pivot and Complement a Heuristic for 0-1 Programming[END_REF]. Ce principe a été repris et intégré à des approches heuristiques [START_REF] Aboudi | Tabu Search for General Zero-One Integer Programs using the Pivot and Complement Heuristic[END_REF][START_REF] Lee | An approximate algorithm for multidimensional zero-one knapsack problems a parametric approach[END_REF]. Enfin, Lo /kketangen et Glover ont réalisé plusieurs implantation d'algorithmes tabou exploitant le tableau du simplexe [START_REF] Lo /Kketangen | Solving zéro-one mixed integer programming problems using tabu search[END_REF][START_REF] Lo /Kketangen | Candidate list and exploration strategies for solving 0/1 mip problems using a pivot neighborhood, dans Metaheuristics[END_REF].

Par ailleurs on retrouve les valeurs des variables duales à l'optimum de MKP comme multiplicateur u du vecteur colonne a j des consommations de l'objet j, dans les critères de type ratio c j /(u.a j ), pour le choix d'une variable x j . Ce ratio prof it/ressource intervient, sous différentes variantes, dans la majorité des heuristiques fondées sur des mécanismes de transformation locale de la solution courante [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF][START_REF] Dammeyer | Dynamic tabu list management using the reverse elimination method[END_REF][START_REF] Glover | Critical event tabu search for multidimensional knapsack problems[END_REF][START_REF] Hanafi | An efficient tabu search approach for the 0-1 multidimensional knapsack problem[END_REF].

Parmi ces dernières nous soulignons les algorithmes génétique (AG) de Chu et Beasley [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF] et tabou de Hanafi et Fréville [START_REF] Hanafi | An efficient tabu search approach for the 0-1 multidimensional knapsack problem[END_REF] qui obtiennent les résultats parmi les meilleurs sur des instances difficiles de MKP01. Ces deux algorithmes se distinguent par la métaheuristique mise en oeuvre pour contrôler l'exploration de l'espace de recherche (AG/tabou) ainsi que par une petite variante dans le mécanisme de transformation des configurations x visitées par le processus d'optimisation. Cette opération correspond à l'algorithme bien connu Drop-Add suivant : Algorithme 1 : Drop-Add Enlever: [START_REF] Aboudi | Tabu Search for General Zero-One Integer Programs using the Pivot and Complement Heuristic[END_REF] i

* = arg max n j=1 a ij .x j /b i , i ∈ [1, m] [2] j * = arg min {c j /a i * j | x j = 1, j ∈ [1, n]} x j * ← 0 Ajouter: Faire k * = arg max c k | x k = 0 et ∀i a ik + n j=1 (a ij .x j ) ≤ b i , k ∈ [1, n] x k * 1 tant que k * existe
Les lignes 1 et 2 se retrouvent dans l'algorithme [START_REF] Hanafi | An efficient tabu search approach for the 0-1 multidimensional knapsack problem[END_REF] (ainsi que dans [START_REF] Dammeyer | Dynamic tabu list management using the reverse elimination method[END_REF]...). La ligne 1 identifie la contrainte la plus saturée. C'est une façon de s'affranchir du calcul du vecteur multiplicateur u tout en conservant le critère du ratio profit/ressource. Dans [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF] cette technique est remplacée par Un algorithme glouton guidé par l'heuristique du ratio prof it/ressource (ou simplement celle du meilleur prof it) pour ajouter des objets dans le sac construira la solution x = (1, 1, 0, 0, 0) qui vaut z = 24 alors que la solution binaire optimale est ẋ = (0, 0, 1, 1, 1) pour ż = 25.

j * = arg min {c j /(u.a j ) | x j = 1, j ∈ [1, n]}
Cet exemple n'est pas une démonstration, mais il illustre l'hypothèse suivante. Le rôle de la transformation locale est mineur devant celui de la stratégie globale d'exploration de l'espace de recherche. Cette vision globale est naturelle pour un algorithme génétique ; elle correspond à la population de vecteurs x impliqués par les opérateurs de croisement, de sélection et de mutation, qui caractérisent cette métaheuristique (une centaine d'individus sont gérés simultanément dans [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF]). Elle n'est pas systématique pour un algorithme tabou. Elle correspond, dans ce cas, à une alternance de phases d'intensification et de diversification de la recherche. Dans [START_REF] Hanafi | An efficient tabu search approach for the 0-1 multidimensional knapsack problem[END_REF] cette alternance de phases est renforcée par une stratégie d'oscillations entre la zone de faisabilité (A.

x ≤ b) et la zone d'infaisabilité (∃i ∈ [1, m] | a i .x > b i ).
Pour finir ce survol des métaheuristiques appliquées à MKP01, nous citerons le recuit simulé [START_REF] Drexl | A simulated annealing approach to the multiconstraint zero-one knapsack problem[END_REF], ainsi qu'une étude des méthodes de bruitage [START_REF] Boucher | Étude des méthodes de bruitage appliquées au problème du sac à dos à plusieurs contraintes en variables 0-1[END_REF] fondées sur les travaux de Charon et Hudry [START_REF] Charon | The noising method: A new method for combinatorial optimization[END_REF]. Les références [START_REF] Boucher | Étude des méthodes de bruitage appliquées au problème du sac à dos à plusieurs contraintes en variables 0-1[END_REF][START_REF] Drexl | A simulated annealing approach to the multiconstraint zero-one knapsack problem[END_REF] ne présentent cependant que des résultats sur des instances de petites tailles. Enfin, Fréville et Plateau ont proposé une heuristique, qui combine des calculs de coefficients duaux avec des fixations de variables, une élimination de contraintes et une procédure d'énumération, pour résoudre efficacement des instances à 2 contraintes [START_REF] Fréville | The 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool[END_REF].

Principe général de notre algorithme

Tenant compte des remarques faites sur l'exemple 2 de la section 2.2, notre étude sur la résolution approchée de MKP01 par la recherche locale (RL) s'est plus particulièrement focalisée sur les deux points suivants :

1. remise en cause de l'heuristique de mouvement (ou critère de choix d'un voisin de la configuration courante) ; 2. recherche d'un moyen d'enrichir le simple processus de RL par une stratégie globale. Nous avons trouvé un principe commun pour répondre à ces deux points d'investigation.

L'idée maîtresse de notre approche est de chercher autour de l'optimum x de MKP. Notre hypothèse est que les points binaires proches de x sont de bonne qualité. Le vecteur x contient l'information globale qui guidera notre processus de RL tout en contrôlant le mécanisme de visite du voisinage N (x) d'une configuration courante x. Pour ce faire nous limitons la RL aux seuls points x ∈ S tels que : distance(x , x) ≤ δ max 4 . La distance géométrique intervient dans le mécanisme de mouvement. Le vecteur ou point x peut être considéré comme une information à caractère stratégique pour la recherche locale.

Sur l'exemple 2 (Sect. 2.2) le simplexe donne z = 30.3 et x = (1, 1, 7 10 , 0, 0) alors que, rappelons-le, ż = 25 pour ẋ = (0, 0, 1, 1, 1). De ce point de vue notre heuristique n'est donc pas plus convaincante que celle du ratio prof it/ressource. Enfin si l'on peut considérer x comme un élément de connaissance à apporter au processus de RL, son unicité en réduit passablement le caractère global.

Faisons pourtant la remarque suivante : toute(s) solution(s) de MKP01 vérifie(nt) l'égalité : n j=1 x j = k ∈ N. Si nous ajoutons cette égalité comme contrainte au problème MKP nous obtenons une série de problèmes du type :

MKP[k]    maximiser c.x s.c. A.x ≤ b et x ∈ [0-1] n , σ(x) = k ∈ N où σ(x)
est la somme des composantes du vecteur x. Nous disposons donc de plusieurs points x[k] pour explorer l'espace de recherche S. Cette approche, directement inspirée par les travaux de Fréville et Plateau [START_REF] Fréville | Sac à dos multidimensionnel en variable 0-1 : encadrement de la somme des variables à l'optimum[END_REF], n'est pas isolée. En effet, de manière très contemporaine, l'ajout de la contrainte d'égalité a été mis en oeuvre pour réduire l'espace de recherche dans le cas du sac à dos multidimensionnel multiobjectif [START_REF] Gandibleux | The multiobjective tabu search method customized on the 0/1 multiobjective knapsack problem: The two objectives case[END_REF]. Illustrons cette heuristique sur ce même exemple de la section 2.2.

MKP[1] → z[1] = 12 et x[1] = (1, 0, 0, 0, 0) MKP[2] → z[2] = 24 et x[2] = (1, 1, 0, 0, 0) MKP[3] → z[3] = 25 et x[3] = (0, 0, 1, 1, 1).
Son comportement semble plus prometteur et nous pouvons énoncer l'idée générale de notre algorithme hybride : dans chaque hyperplan σ(x) = k lancer un processus de RL autour du point x[k] . Nous allons donc alterner, dans le processus d'optimisation, une phase de programmation linéaire P L avec une phase de recherche locale tabou RL tabou . Chaque séquence P L/RL tabou pourra être distribuée sur plusieurs machines.

La mise en oeuvre de ce principe se décompose en trois étapes :

-détermination des valeurs de k intéressantes ; -utilisation du simplexe pour calculer les x[k] correspondants ; -exécution de la recherche locale tabou autour de ces points.

La section suivante décrit la phase simplexe, ou programmation linéaire P L, qui traite les deux premières étapes que nous venons de citer.

Phase simplexe

Le processus RL tabou effectue un échantillonnage discret autour de l'optimum de MKP [k]. Notre hypothèse est qu'en tant que tel il ne fera pas mieux que la valeur z[k] de la solution continue de ce programme. La première étape de notre approche consiste donc à trouver les valeurs de k qui fournissent des bornes supérieures z[k] à un minorant z donné.

Fréville et Plateau [START_REF] Fréville | Sac à dos multidimensionnel en variable 0-1 : encadrement de la somme des variables à l'optimum[END_REF] proposent un algorithme pour l'encadrement du nombre de variables à l'optimum de MKP01 qui fait appel à plusieurs outils de la programmation linéaire. Nous avons développé un algorithme plus simple dont le principe est d'utiliser RL tabou pour obtenir un minorant z, puis résoudre par le simplexe les deux problèmes suivants MKPσmin

[z] et MKPσmax[z] : MKPσmin[z]    minimiser σ(x) s.c. A.x ≤ b et x ∈ [0-1] n , c.x ≥ (z + 1)
Soit σmin[z] la valeur optimale de ce problème. Si nous prenons moins d'objets que k min = σ min la contrainte c.x ≥ (z + 1) ne sera plus vérifiée.

MKPσmax[z]    maximiser σ(x) s.c. A.x ≤ b et x ∈ [0-1] n , c.x ≥ (z + 1)
soit σmax[z] la valeur optimale de ce problème. Si nous prenons plus d'objets que k max = σ max l'une au moins des contraintes A.x ≤ b ne sera plus vérifiée. En conséquence, les seules valeurs de k intéressantes pour notre processus de recherche locale sont celles comprises entre k min et k max . Nous calculons donc, par l'algorithme du simplexe, les (k maxk min + 1) MKP[k] qui nous fournissent les points cherchés pour la phase RL tabou .

La figure 1 résume le déroulement de cette phase simplexe ou P L sur l'instance cb30.250.10 due à Chu et Beasley [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF]. Le programme RL tabou a besoin d'un point pour amorcer la recherche, cela explique la ligne 1 de cet exemple.

Phase recherche locale

Définitions

Avant de détailler notre algorithme tabou nous résumons, dans ce paragraphe, les éléments de terminologie que le lecteur retrouvera par la suite :

-la configuration x : c'est le vecteur binaire (x 1 , • • • , x n ) ; -S
(1, 1, • • • , 1, r 1 , • • • , r q , 0, • • • , 0)
1 > r 1 ≥ r 2 ≥ • • • ≥ r q > 0.
Le mécanisme de RL peut choisir, dans le pire des cas, les objets qui correspondent à ces composantes plutôt que ceux qui correspondent aux composantes à 1. La figure 2 illustre cette configuration limite. u est le nombre de composantes à 1 dans x[k] , u + q est donc le nombre de composantes non nulles de x

[k] 5 . De plus σ(x [k] ) = k ⇒ q j=1 r j = k -u ⇒ δ [k] = 2 × (u + q -k) ∈ 2 × N. x limite → 0 . 0 1 1 1 2 . . . . . 1 k 0 . 0 x[k] → 1 . 1 1 1 r 1 r 2 . . . r q 0 . 0 δ [k] = u + q -k + q j=1 (1 -r j ) Figure 2. Heuristique de calcul de δ [k] = δ(x limite , x[k] ).
Dans le cas limite où u = k nous obtenons δ [k] = 0 ce qui est tout à fait logique puisque dans ce cas x[k] est entièrement binaire. Pratiquement, et selon les instances, nous prendrons :

δ max ≈ δ [k] .
Chaque processus RL tabou lancé autour de x[k] a donc son propre espace de recherche X k :

X k = {x ∈ {0, 1} n | σ(x) = k ∧ δ(x, x[k] ) ≤ δ max }•
Notons ici que les X k sont disjoints. Cela réduit à 0 les risques de redondance d'exploration des processus RL tabou qui peuvent donc s'exécuter indépendamment.

Voisinage

L'ensemble N (x) des voisins d'une configuration x est donc défini par la formule suivante :

N (x) = {x ∈ X k |δ(x, x ) = 2} • À cause de la contrainte σ(x) = k (implicite dans X k ), N (x)
n'est qu'un sousensemble des points à distance 2 de x. Sa cardinalité est :

|N (x)| = (n -k) × k.
Le mouvement induit par ce voisinage correspond au retrait d'un objet et l'ajout d'un autre, c'est un cas particulier de 2 change (cf. définitions Sect. 5.1). Nous noterons indifféremment mvt(x, x ) et mvt(i, j) avec

x i = 1 -x i et x j = 1 -x j .
Cette formulation du voisinage va être modifiée à la fin de la section suivante pour tenir compte d'éléments liés à la gestion de la liste tabou.

Gestion dynamique de la liste tabou

La méthode d'élimination inverse (MEI), proposée par Glover [START_REF] Glover | Tabu search[END_REF], permet de définir le statut tabou d'un mouvement de manière exacte. Cela signifie qu'elle est équivalente à l'enregistrement complet des configurations visitées. Elle est qualifiée de liste stricte [START_REF] Battiti | The reactive tabu search[END_REF]. Son principe consiste à mémoriser dans une liste (running list) les attributs des mouvements effectués. Pour savoir si un nouveau mouvement est tabou il faut parcourir la running list à l'envers. Ce faisant on construit une autre liste, la séquence d'annulation résiduelle ou SAR dans laquelle soit on recopie les attributs de la running list (y compris ceux du nouveau mouvement), s'ils n'y sont pas déjà, soit on les en enlève. Cette étape est appelée trace des attributs du mouvement. Si au cours de cette étape on rencontre la condition SAR = ∅ alors le nouveau mouvement nous ramène à un point déjà visité. Il faut donc le rendre tabou. La complexité de la MEI est donc O(iter 2 ). Dammeyer et Voß [START_REF] Dammeyer | Dynamic tabu list management using the reverse elimination method[END_REF] ont réalisé une première mise en oeuvre de la MEI sur le MKP01, dans laquelle la MEI analyse un nombre variable d'échanges causés par l'algorithme Drop-Add. Ce voisinage nécessite la gestion de traces à nombre variable d'attributs. Cela accroît la complexité de la procédure. Dans le cas de notre voisinage à k constant nous parcourons une seule fois la running list et chaque fois que |SAR| = 2 nous rendons tabou le mouvement qui implique les attributs SAR 0 et SAR 1 . L'algorithme suivant est associé à la proposition logique : mvt(i, j) tabou ⇔ tabou[i][j] = iter. Nous ne l'introduisons que pour sensibiliser le lecteur à un aspect connexe beaucoup plus gênant : un processus de recherche locale contrôlé par une liste tabou stricte construit un chemin qui peut devenir une barrière entre N (x) et une zone de X k de points potentiellement intéressants. Il faut donc autoriser, de temps en temps, le cyclage par un mécanisme d'aspiration [START_REF] Glover | Tabu search[END_REF][START_REF] Hanafi | Extension de la Méthode d' Élimination Inverse pour une gestion dynamique de la liste tabou[END_REF].

Nous contournons cet écueil par une remise à zéro de la running list. Toutefois, pour que ce mécanisme n'entraîne pas un cyclage systématique, nous imposons que les configurations x visitées après cette remise à zéro soient d'une valeur c.x = z > z min où z min représente la valeur de la meilleure configuration réalisable rencontrée jusque là. Évidemment pour que cela soit possible sans tomber dans le cadre d'une simple descente les configurations non réalisables

(∃i ∈ [1, m] | a i .x > b i ) sont admises.
Nous introduisons donc une mesure du niveau d'infaisabilité :

υ b (x) = i |aix>bi (a i .x -b i ),
que nous chercherons à minimiser au cours de la RL. A chaque fois que υ b (x) vaut 0 nous effaçons la running list et nous mettons à jour z min .

Voici, pour finir, la version définitive du voisinage :

N (x) = {x ∈ X k |(δ(x, x ) = 2) ∧ (c.x > z min ) ∧ (mvt(x, x ) non tabou)} • 5.5.
y = x ∈ N (x) | ∀ x ∈ N (x) (υ b (x ) < υ b (x )) ∨ (υ b (x ) = υ b (x ) ∧ z(x ) ≥ z(x )) .
En cas d'égalité de la fonction d'évaluation le choix est aléatoire.

Configuration initiale

Pour amorcer le processus RL tabou il faut construire un x init qui appartienne à X k . Nous allons montrer qu'il suffit, pour cela, de choisir les k objets correspondant aux plus fortes composantes de x[k] , solution optimale de MKP[k] produit par simplexe.

Reprenons le schéma de la section 5.2 et construisons une suite de points (x i )6 qui part de x limite tout en décalant, à chaque étape, les k composantes à 1 vers la gauche :

x[k] → 1 . 1 1 1 r 1 r 2 . . . r q 0 x 0 = x limite → 0 . 0 1 1 1 2 . . . . . 1 k 0 x 1 → 0 . 1 1 1 2 . . . . . 1 k 0 0 ... → . . . . . . . . . . . . x init = x u+q-k → 1 1 1 2 . . . . . 1 k 0 . 0 0 Figure 4. Construction de x init .
Comme on peut le voir sur la figure 4 la distance de x 1 à x[k] est égale à celle de x 0 plus (r q -1) soit à δ [k] + (r q -1). Par définition r q est strictement inférieur à 1 donc x 1 s'est rapproché de x[k] . On a la relation de récurrence :

δ i = δ(x i , x[k] ) = δ i-1 + (r q-i+1 -1) = δ i-1 + i avec ∀i i < 0.
La suite des distances (δ i ) correspondant à la suite (x i ) est strictement décroissante depuis la valeur δ [k] ce qui garantit : δ u+q-k < δ [k] . Nous pouvons prendre comme configuration initiale x init le point x u+q-k qui appartient bien à X k .

Algorithme RL tabou

L'algorithme RL tabou (Algorithme 3) n'optimise pas directement MKP [k]. Il résout7 une suite de problèmes de décision du type :

Existe-t-il x ∈ {0, 1} n tel que    c.x ≥ z min et A.x ≤ b et σ(x) = k
où (z min ) est une suite positive strictement croissante. Il explore les zones de l'espace de recherche X k pour lesquelles z > z min . Son objectif premier n'est pas de maximiser un critère du type prof it/ressource mais de minimiser υ b . Nous notons |R.L.| la taille de la running list qui correspond au nombre maximum d'itérations sans production d'une configuration x réalisable (A.x ≤ b). Passé cette limite le processus s'interrompt. S'il ne trouve pas de configuration respectant les contraintes de sac, cet algorithme retourne le vecteur nul. Enfin pour des raisons de clarté le facteur aléatoire a été omis. Sa mise en oeuvre consiste simplement à parcourir les composantes du vecteur x dans un ordre aléatoire.

Une analyse de la complexité de RL tabou sera faite en section 7 à la suite de la présentation des résultats.

(i, j) si δ(x, x[k] ) ≤ δmax ∧ z(x) > zmin alors si (υ b (x) < υmin) ∨ (υ b (x) = υmin ∧ z(x) > z ) alors (i , j ) = (i, j) z = z(x); υmin = υ b (x ) (xi, xj ) = (1, 0)
si z = 0 alors (x i , x j ) = (0, 1) %On effectue le mouvement mvt(i , j ) si υmin = 0 alors frl = 0 efface la running list zmin = z(x)

x * = x sinon iter = iter + 1 running list = running list ⊕ i ⊕ j ; frl = frl + 2 MAJ Tabou jusqu'à (z = 0) ∨ (frl ≥ |R.L.|)

Résultats

Nous avons expérimenté notre approche sur 3 séries de jeux tests. Pour toutes ces instances RL tabou a été exécuté, de façon distribuée, avec les 10 germes (0..9) de la fonction standard srand(). L'algorithme est codé en C et tourne sur des configurations (machine/système) aussi diverses que : (PII350/Win.NT), (PII450/Win.NT), (PIII500/Win.NT), (Ultra Sparc 5/Unix) et (Ultra Sparc 30/Unix). Les temps d'exécution en secondes, qui figurent dans les colonnes t.t., sec. * et sec., sont donc donnés seulement à titre indicatif.

Jeux classiques

Nous commençons par les 56 instances classiques que l'on retrouve notamment dans [1, 2, 5, 7, 8, 10-12, 20, 24, 31, 32]. Ces jeux ne sont plus considérés comme difficiles aujourd'hui [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF][START_REF] Hanafi | An efficient tabu search approach for the 0-1 multidimensional knapsack problem[END_REF] Nous ne faisons pas figurer le nombre total d'itérations effectuées par RL tabou puisqu'il peut se déduire par la simple formule :

iter * + 1 2 × |R.L.| .
Nous remarquons qu'en général δ * , qui est pour ces jeux la distance de la solution optimale à x[k] , est assez faible. Cela explique la rapidité de notre algorithme à résoudre ces instances. On constate par ailleurs que sur 10 instances (iter * = 0), l'heuristique du plus proche point suffit à construire la solution optimale et qu'il suffit d'un mouvement pour 31 autres instances. Pour ces 41 instances il n'est pas utile de mettre en oeuvre la métaheuristique tabou pour trouver l'optimum.

Nous rappelons que t.t. est le temps total, pour 10 relances de 1000 itérations (une par germe aléatoire), pour chaque hyperplan : ainsi t.t. est-il plus grand pour weish26 que pour weish23. weish26 contient 10 variables de plus et exige l'exploration d' un hyperplan supplémentaire. iter * est le nombre d'itérations, dans l'hyperplan σ(x) = k * , pour atteindre la meilleure configuration : sa valeur n'est pas obligatoirement corrélée à celle de t.t.

Jeux Glover et Kochenberger

Cette deuxième série de tests est constituée des 7 dernières instances proposées par Glover et Kochenberger [START_REF] Glover | Critical event tabu search for multidimensional knapsack problems[END_REF]. Le tableau 3 résume les valeurs clés de la phase Le tableau 4 correspond à la phase recherche locale. Pour cette série de problèmes, ainsi que la suivante, la taille de la running list est fixée à 100 000. La colonne T HF indique les résultats obtenus par l'algorithme tabou de Hanafi et Fréville [START_REF] Hanafi | An efficient tabu search approach for the 0-1 multidimensional knapsack problem[END_REF] que l'on peut comparer avec la valeur z * , signalée en caractères gras, de la meilleure configuration x * , à k * objets, trouvée par RL tabou . La colonne T HF contient les récentes valeurs obtenues par Hanafi avec son algorithme tabou. Les colonnes sec. * et sec. indiquent respectivement le temps d'obtention de x * et le temps total d'exécution d'une phase RL tabou . Nous améliorons strictement la majorité des résultats sur ces instances.

P L. z = max(z [k] )
Par rapport aux jeux précédents (Sect. 6.1), le nombre d'itérations et, par voie de conséquence le temps CPU, nécessaires à l'obtention de ces solutions ont augmentés. En effet :

-les nombres n et m, plus grands pour ces instances, interviennent dans la complexité de la fonction d'évaluation du voisinage ; -

δ [k * ] a augmenté et C δ [k * ] n
8 donne une idée de la combinatoire à traiter.

Notre processus doit parcourir un espace de recherche X k plus vaste. À échantillonnage équivalent de X k , il faut plus d'itérations. Comme nous l'avons évoqué au début de la section sur les jeux classiques nous avons, avec les valeurs δ [k] , une mesure expérimentale de la difficulté d'une instance de MKP01.

Jeux Chu et Beasley

270 instances de MKP01 de tailles allant de 100 à 500 variables et de 5 à 30 contraintes sont proposées, très récemment, par Chu et Beasley [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF] et constituent une partie de la OR-Library 9 . Tableau 5. 24 instances cbm.n.r. Nous présentons, dans un premier temps, un tableau synthétique sur 24 instances couvrant toutes les caractéristiques offertes par leurs auteurs (n × m × α 10 ) exceptées n = 500 et m = 30 qui font l'objet d'un autre tableau. Le format générique du libellé de ces instances est le suivant : cbm.n.r avec 0 ≤ r ≤ 29. La colonne n × m n'est donc plus utile. De même, la valeur α peut se déduire à partir du rang r de l'instance : 0 ≤ r ≤ 9 ⇒ α = 0.25, 10 ≤ r ≤ 19 ⇒ α = 0.50 et 20 ≤ r ≤ 29 ⇒ α = 0.75. De façon similaire à la section précédente, la colonne AG CB représente les meilleures valeurs obtenues par l'algorithme génétique de Chu et Beasley [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF]. Les valeurs optimales, lorsqu'elles sont connues, figurent en italique. RL tabou produit bien une solution optimale dans ce cas. Nous améliorons la majorité des résultats pour lesquels cet optimum n'est pas connu (valeurs indiquées en caractères gras).

Nous améliorons également de manière significative les meilleurs résultats obtenus par Chu et Beasley [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF] sur les 30 instances les plus importantes de la OR-Library (cf. Tab. 6). Sur cette série d'instances, la valeur z est sensiblement plus fine que la borne z. Tableau 6. 30 instances cb30.500. La taille de la running list étant fixée à 100 000, nous savons que l'algorithme a effectué 50 000 itérations après iter * . Nous donnons, dans la section suivante, une analyse de la complexité temporelle de cette fin de processus d'optimisation.

Nous terminons cette étude comparative par la synthèse des résultats sur l'ensemble des jeux à 500 variables de la OR-Library. Nous ajoutons les résultats obtenus par Osorio et al. [START_REF] Osorio | Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions[END_REF] lors de récents travaux dont l'objectif était d'améliorer les performances de l'outil de programmation linéaire en nombres entiers CPLEX (V6.5.2) ; travaux qui portent sur un algorithme de fixation de variables avec adjonction de coupes (résultats en colonne Fix+Cuts). Nous retranscrivons également, en colonne CPLEX, les valeurs trouvées par ce logiciel sans les modifications effectuées par les auteurs du rapport [START_REF] Osorio | Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions[END_REF]. Remarquons toutefois que des valeurs δ max trop faibles risquent d'interdire des zones intéressantes de X k (cf. valeurs de δ * 1 et δ * 2 Tab. 9). Ce paramètre de réglage augmente bien sûr la complexité globale de notre approche. Nous nous sommes limités à δ max = coef × δ avec coef ∈ {0.75, 1, 1.5, 2} et même exceptionnellement 3 pour certains jeux de la section 6.1 pour lesquels δ [k * ] était trop petit (voir Tabs. 1 et 2).

sec. ≈ (A × iter × (n -k) × k × m) + B × iter × (iter -

Conclusion

Nous avons mis en oeuvre une approche hybride très performante qui combine la programmation linéaire et la recherche locale tabou. Son principe général est d'utiliser la méthode du simplexe pour obtenir des points continus autour desquels lancer un algorithme tabou. Nous avons introduit une caractéristique intéressante (δ [k] ) pour les problèmes MKP01 et proposé une alternative au critère de choix prof it/ressource pour le mécanisme de transformation locale d'une configuration x. Nous avons aussi développé une version relativement efficace de la méthode d'élimination inverse dont l'exploitation peut renforcer d'autres algorithmes tabou.

L'idée d'échantillonner {0, 1} n autour d'optima de [0-1] n s'est avérée très bénéfique et performante. En effet, notre algorithme hybride améliore de manière significative les derniers résultats connus sur des instances difficiles [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF][START_REF] Hanafi | An efficient tabu search approach for the 0-1 multidimensional knapsack problem[END_REF].

Ce travail peut apporter une contribution dans le cadre des méthodes exactes et cela à deux titres :

-réduction de l'espace de recherche par encadrement du nombre de variables à l'optimum : la colonne [k] des tableaux 3, 5 et 6 donnent les valeurs potentiellement intéressantes pour l'optimum ; -fixation de variables à partir d'un minorant z de bonne qualité, sa configuration x et les coûts réduits des variables hors base [START_REF] Balas | Pivot and Complement a Heuristic for 0-1 Programming[END_REF][START_REF] Gondran | Graphes & algorithmes[END_REF] : si l'on applique ce principe sur l'instance GK024 à 500 variables, due à Glover et Kochenberger [START_REF] Glover | Critical event tabu search for multidimensional knapsack problems[END_REF], P L/RL tabou nous fournit x, tel que c.x = 9070 (Sect. 4). On peut alors fixer 38 variables à 0.

Plusieurs voies d'amélioration sont encore à explorer :

-une étude plus précise sur la distance δ max qui limite l'espace de recherche autour des points continus x[k] augmentera l'efficacité de RL tabou ; -la mise en oeuvre d'un mécanisme de relance permettra éventuellement de trouver des solutions de meilleure qualité ; -la prise en compte, dans une version distribuée, d'une population d'optima locaux, pour intégrer de nouvelles contraintes aux programmes relaxés MKP[k] puis, par le simplexe, générer de nouveaux points continus pour relancer la RL.

L'idée la plus intéressante semble bien être de transformer le schéma à sens unique P L/RL tabou , qui correspond à une simple alternance entre le simplexe et tabou par une relation réactive P L ↔ RL tabou plus riche qui construirait, de manière dynamique, un problème relaxé dont la solution continue serait plus attractive pour la recherche locale.

Voici donc de nouvelles perspectives pour la résolution approchée du sac à dos multidimensionnel en variables bivalentes, qui nous l'espérons, apporteront des résultats encore meilleurs dans un proche avenir.

  où u correspond aux coûts marginaux des m ressources de MKP. Considérons cependant l'instance de MKP01 suivante : exemple 2 (n = 5, m = 1) c = 12 12 9 8 8 A = 11 12 10 10 10 b = 30.

1 .Figure 1 .

 11 Figure 1. Phase P L pour cb30.250.10.

  les composantes triées par ordre décroissant du vecteur x[k] . Les r j sont les composantes fractionnaires de x[k] et l'on a :

Algorithme 2 :Figure 3 .

 23 Figure 3. Blocage avec 1 change dans {0, 1}4 . En 7 itérations, avec un voisinage à 1 change, le chemin parcouru aboutit à une impasse alors que S n'a pas été complètement visité. Ce phénomène de blocage est d'une très faible probabilité dans {0, 1} n avec n ≥ 100. Nous ne l'introduisons que pour sensibiliser le lecteur à un aspect connexe beaucoup plus gênant : un processus de recherche locale contrôlé par une liste tabou stricte construit un chemin qui peut devenir une barrière entre N (x) et une zone de X k de points potentiellement intéressants. Il faut donc autoriser, de temps en temps, le cyclage par un mécanisme d'aspiration[START_REF] Glover | Tabu search[END_REF][START_REF] Hanafi | Extension de la Méthode d' Élimination Inverse pour une gestion dynamique de la liste tabou[END_REF].

  Fonction d'évaluation et heuristique de mouvement Nous précisons, dans cette section, comment à partir d'un point x, nous choisissons parmi les points x ∈ N (x) le point y qui fera l'objet du mouvement mvt(x, y). La fonction d'évaluation d'une configuration x a deux composantes : υ b (x) et z(x) = c.x. La première composante est prioritaire sur la seconde. L'heuristique du choix d'un voisin de x est donc :

Algorithme 3 :

 3 RL tabou iter = 0 frl = 0 tabou[n][n] (-1) x ← xinit %Configuration initiale (figure 4) si υ b (x) = 0 alors zmin = z(x); x * x sinon zmin = 0; x * ← (0) répéter z = 0; υmin = ∞ pour i | xi = 1 faire pour j | xj = 0 faire si tabou[i][j] = iter alors (xi, xj ) = (0, 1) %On évalue le mouvement mvt

  représente l'espace de recherche. Il peut être égal à {0, 1} n si l'on considère toutes les configurations possibles x ∈ S réalisables ou non ; -le voisinage de x : N (x) est le sous-ensemble des éléments de S accessibles depuis l'élément x en une seule itération ; -l'attribut est la valeur affectée à une composante. Dans le cas binaire on peut identifier sans ambiguïté un attribut à l'indice j de la composante qui change de valeur ; -enfin le mouvement correspond au passage de la RL du point x à un de ces voisins x : mvt(x, x ) | x ∈ N (x). En reprenant ce qui vient d'être dit sur les attributs on peut aussi écrire mvt(i 1 , i 2 , ..., i k ) où les indices i j sont ceux des composantes de x qui sont complémentées dans x . Un tel mouvement est un k change.5.2. Réduction de l'espace de rechercheNous allons dans cette section spécifier un sous ensemble X ⊂ S dans lequel naviguera notre processus de recherche locale. Cette réduction de S reprend les idées que l'on vient d'énoncer : 1. limitation de S à une sphère d'un rayon fixé autour du point x[k] solution optimale de MKP[k] ; 2. conservation du nombre d'objets retenus dans les configurations x, produites par RL

tabou autour du point x[k] , à la valeur constante k (intersection de S avec l'hyperplan {σ(x) = k}). Pour le point 1 nous utilisons la distance δ définie, pour x et x binaires ou continus, par la formule δ(x, x ) = n j=1 |x jx j |. L'heuristique pour estimer la distance maximale δ max autorisée depuis le point x[k] , est la suivante : soit

  Les valeurs de la phase P L n'ont pas d'intérêt en tant que bornes puisque l'optimum est connu. Nous indiquons tout de même l'intervalle [k] des hyperplans σ(x) = k explorés par RL tabou . Pour cette série et la suivante (à des fins de comparaison) nous donnons la distance δ * de la meilleure solution x * à x[k * ] , ainsi que la valeur δ [k * ] (Sect. 5.2) à partir de laquelle on estime le rayon de recherche autour du point x[k * ] . La colonne iter * correspond au nombre de mouvements pour atteindre x * . La colonne t.t. représente la somme des temps sur tous les processus dans chaque hyperplan σ(x) = k. Tableau 2. Instances classiques (suite et fin).

	Nous avons, pour ces jeux, fixé la taille de la running list à 2000 (|R.L.| = 2000).
	Les résultats sont présentés dans les tableaux 1 et 2.
	Pb. z weish01 30 × 5 12..14 n × m [k] 4554 12 0.72 2.00	0		2
	weish02 30 × 5 13..15 Tableau 1. Instances classiques. 4536 14 3.28 2.00 weish03 30 × 5 12..14 4115 12 1.41 2.00	3 1		2 2
	Pb. weish04 30 × 5 11..12 n × m [k] weish05 30 × 5 11..12	z * k * 4561 12 2.00 2.00 δ * δ [k * ] iter * t.t. 1 1 4514 12 2.00 2.00 1 1
	fp1 weish06 40 × 5 20..21 27 × 4 14..23	3090 17 4.14 6.00 5557 20 3.20 2.00	79 8	1	0
	fp2 weish07 40 × 5 19..20 34 × 4 14..28	3186 23 7.48 6.00 5567 20 2.70 2.00	1	7	2	1
	fp3 weish08 40 × 5 21..22 19 × 2 2..6	28642 5605 21 2.55 2.00 3 2.73 2.00	1	1	2	0
	fp4 weish09 40 × 5 15..16 29 × 2 11..20	95168 14 2.18 2.00 5246 16 0.19 2.00	0	1	1	1
	fp5 weish10 50 × 5 19..23 20 × 10 9..11	2139 10 3.55 8.00 6339 21 2.69 2.00	1	1	5	0
	fp6 weish11 50 × 5 18..20 40 × 30 7..12	776 5643 19 0.82 4.00 9 5.16 8.00	27 0	4	1
	fp7 weish12 50 × 5 20..22 37 × 30 15..20	1035 17 3.55 8.00 6339 21 2.48 2.00	1	1	3	1
	peter1 6 × 10 weish13 50 × 5 19..22 3..4	3800 6159 21 2.30 2.00 3 1.16 4.00	1	0	4	0
	peter2 10 × 10 weish14 60 × 5 23..26 3..7	87061 6954 26 0.63 4.00 5 4.25 2.00	0	2	5	0
	peter3 15 × 10 8..11 weish15 60 × 5 26..27	4015 7486 26 2.00 4.00 9 1.38 2.00	1	1	3	0
	peter4 20 × 10 9..11 weish16 60 × 5 25..28	6120 7289 26 2.44 2.00 9 0.07 2.00	1	0	4	0
	peter5 28 × 10 15..18 weish17 60 × 5 38..41	12400 18 2.00 2.00 8633 41 2.00 2.00	1	1	4	1
	peter6 39 × 5 24..33 weish18 70 × 5 39..41	10618 27 4.14 6.00 9580 40 2.26 2.00	331 1	4	9
	peter7 50 × 5 26..40 weish19 70 × 5 26..29	16537 35 7.34 8.00 7698 27 2.00 2.00	852 31 1 7
	hp1 weish20 70 × 5 35..37 28 × 4 15..24	3418 18 4.14 6.00 9450 35 0.31 2.00	79 0	4	3
	hp2 weish21 70 × 5 32..35 35 × 4 14..28	3186 23 7.34 8.00 9074 32 2.00 2.00	1	7	6	9
	weing1 28 × 2 12..15 weish22 80 × 5 32..35	141278 14 2.00 2.00 8947 33 4.00 2.00	12	1	7	1
	weing2 28 × 2 10..12 weish23 80 × 5 30..33	130883 11 2.00 4.00 8344 32 4.00 2.00	1 461 12	1
	weing3 28 × 2 weish24 80 × 5 45..47 10220 45 0.06 2.00 5..9 95677 6 2.73 2.00	0	1	8	2
	weing4 28 × 2 10.17 weish25 80 × 5 40..42	119337 15 4.78 2.00 9939 40 2.00 2.00	127 1	7	4
	weing5 28 × 2 weish26 90 × 5 35..39 6..9	98796 9584 36 2.00 2.00 9 0.09 2.00	0 1 14	0
	weing6 28 × 2 10..12 weish27 90 × 5 37..39	130623 11 4.00 2.00 9819 38 1.43 2.00	19 1	7	0
	weing7 105 × 2 86..90 1095445 87 2.62 4.00 weish28 90 × 5 36..38 9492 37 1.34 4.00	1	1	9	8
	weing8 105 × 2 27..36 weish29 90 × 5 36..38	624319 30 2.18 2.00 9410 36 0.02 2.00	0	1 24 6
	sento1 60 × 30 18..23 weish30 90 × 5 50..51 11191 51 2.00 2.00 7772 20 5.16 8.00	27 16 1 2
	sento2 60 × 30 31..36	8722 33 3.55 8.00		1 10
	. Cependant :
	-d'une part ils constituent une référence à laquelle une méthode approchée ne
	peut se soustraire sans arguments a priori ;
	-d'autre part ils permettront une analyse comparative des valeurs δ [k] qui
	fournira, justement, un début d'argumentation pour caractériser a priori la
	difficulté des problèmes.

P L/RL tabou trouve la solution optimale (connue) dans tous les cas (z

* = ż). * k * δ * δ [k * ] iter * t.t.

  est la meilleure valeur parmi les optima des programmes MKP[k] . La dernière colonne (sec.) indique les durées cumulées, en secondes, pour la résolution de MKP ainsi que des MKP[k] . Phase RL tabou sur gk18 ↔ gk24.

	Tableau 3. Phase P L sur gk18 ↔ gk24.
	gk	n × m		[k]	z	z	sec.
	18 100 × 25	58..64	4545.66 4545.79	4
	19 100 × 25	49..55	3886.45 3886.80	4
	20 100 × 25	61..74	5198.54 5198.64	5
	21 100 × 25	40..46	3219.73 3219.92	5
	22 100 × 25	31..37	2544.02 2544.03	4
	23 200 × 15 119..126 9245.53 9245.67 12
	24 500 × 25 116..125 9080.44 9080.45 220
	Tableau 4. gk THF T HF	z *	δ *	δ [k sec.
	18 4524 4526 4528 13.55 24.00 61	3683	10	395
	19 3866 3867 3869 15.29 20.00 51	3144	9	382
	20 5177 5179 5180 15.95 22.00 70	2080	5	366
	21 3195 3197 3200 10.78 22.00 42	1465	4	366
	22 2521 2523 2523 14.24 28.00 34	512	2	383
	23 9231 9233 9235 19.69 16.00 123 16976 131	723
	24 9062 9064 9070 15.21 22.00 119 9210	268 2027

* ] k * iter * sec. *

  Tableau 7. Moyennes des meilleurs résultats par groupe de 10 instances cbm.500.Fix+Cuts et CPLEX sont interrompus après 3 heures de calcul (sur un PIII500) ou lorsque l'arbre de recherche dépasse les 250 Mo d'occupation mémoire. Nous constatons que, plus le nombre de contraintes est élevé, plus la moyenne des écarts à l'optimum continu est grande (dernière colonne), plus notre approche se distingue des autres algorithmes en conservant une avance qualitative significative. Voisinage et running list L'estimation du temps CPU pris par RL tabou en fonction du nombre total d'itérations n'est pas facile. En effet la running list est remise à zéro à chaque fois que l'on rencontre une configuration réalisable (Sect. 5.4). Étant donné que toute phase RL tabou finit par un nombre constant (|R.L.|/2) de mouvements on peut proposer, pour cette étape, la formule suivante :

	m	α	AGCB Fix+Cuts CPLEX P L/RL (z -z * )/z
	5 1/4 120616	120610	120619 120623	0.0008
		1/2 219503	219504	219506 219507	0.0004
		3/4 302355 302361	302358	302360	0.0002
	10 1/4 118566	118584	118597 118600	0.0020
		1/2 217275	217297	217290 217298	0.0009
		3/4 302556	302562	302573 302575	0.0007
	30 1/4 115470	115520	115497 115547	0.0055
		1/2 216187	216180	216151 216211	0.0024
		3/4 302353	302373	302366 302404	0.0015
			7. Analyse de la complexité
	7.1.

  1) 2où : A représente le coût moyen, en secondes par itération, du calcul de la fonction d'évaluation du voisinage, B celui de la mise à jour de la liste tabou. Dans cette formule, le coefficient A est assez imprécis : en effet nous nous limitons à un rayon δ max autour d'un point x[k] . Nous n'avons donc pas systématiquement la mesure de z(x), mais surtout celle de υ b (x) qui coûte m, à effectuer. Faute de pouvoir évaluer correctement A et B nous avons regroupé dans le tableau 8 Tableau 8. Temps de calcul en secondes. 'exécution sur des instances à α = 0.50 pour toutes les combinaisons n × m et pour 4 tailles de la running list. La machine utilisée est un PIII500. Nous avons modifié l'algorithme RL tabou en supprimant la remise à zéro de la running list pour avoir un nombre d'itérations directement lié à la taille de cette dernière. Le facteur quadratique dû à la gestion de la liste tabou est assez faible. Le temps maximum est de moins de 20 minutes pour |R.L.| = 100 000. C'est la valeur à rajouter aux temps indiqués dans les colonnes sec. * des tableaux 5 et 6.Dans le cas d'une parallélisation des processus tabou avec une machine par germe de srand(), ce temps n'est pas prohibitif. Nous pouvons même accroître la taille de la running list pour tenter d'améliorer encore les résultats (Tab. 9) : nous Tableau 9. Augmentation de la running list. est relativement importante. Le processus tabou a exploré plus loin. Le temps total t.t. (en secondes ) devient important mais cette évolution nous encourage à travailler sur la complexité de la procédure RL tabou .7.2. Le paramètre δ maxEnfin le paramètre δ max est un facteur crucial de l'efficacité de notre algorithme. Le tableau 10 illustre bien l'influence de δ max à la fois sur la stabilité de RL tabou vis-à-vis de la discrimination aléatoire des meilleurs candidats dans N (x) et sur le temps total d'exécution de RL tabou . La colonne g contient la valeur du germe de la fonction srand(). Nous soulignons en caractère gras les temps minimums et maximums d'exécution complète de la phase tabou pour chacune des valeurs de δ max .Tableau 10. Influence de δ max sur RL tabou : gk24, k * = 119, δ [119] = 22.

	|R.L.| n=100 m=5 25000 21 50000 70 100000 253 200000 1046 1076 1100 1371 1427 1608 2566 2771 2975 100 10 100 30 250 5 250 10 250 30 500 5 500 10 500 30 22 25 56 59 82 199 222 244 73 78 142 148 193 425 479 526 262 273 410 424 512 1001 1106 1193 les temps d|R.L.| = 100 000 |R.L.| = 300 000 cb δ * 1 z * 1 z * 2 δ * 2 iter * t.t. δ(x * 1 , x * 2 ) 5.500.10 5.8 218426 218428 9.26 173312 6441 14.0 30.500.0 15.93 115950 115991 18.61 264408 9760 24.0 constatons un gain par rapport aux valeurs des tableaux 5 et 6. Nous remarquons aussi que les distances δ * 2 aux optima x[267] et x[130] ont augmenté. En terme de combinatoire la distance δ(x * 1 , x * 2 ) entre la nouvelle solution x * 2 et la précédente x * δmax = 0.75 × δ [119] = 16.5 δmax = 0.6 × δ[119] = 13.2 iter * sec. * sec. δ * z * iter * sec. * sec. δ * z * 0 67354 2200 4014 10.87 9070 25172 626 2120 10.87 9070 1 26735 763 2581 16.17 9067 68809 1924 3409 10.87 9070 2 46175 1373 3171 13.81 9067 30508 779 2297 10.87 9070 3 15882 438 2282 14.75 9067 289 8 1445 10.87 9070 4 87218 2983 4810 10.87 9070 1754 39 1470 10.87 9070 5 4879 142 1949 16.04 9066 54029 1338 2809 10.87 9070 6 79848 2509 4237 14.90 9068 71834 1838 3290 10.87 9070 7 9210 268 2027 15.21 9070 6758 150 1616 10.87 9070 8 41101 1205 2901 14.69 9067 44282 1212 2633 10.87 9070 1 g 9 17572 507 2234 10.87 9070 25378 624 2082 10.87 9070

C'est ici l'aspect pratique qui nous intéresse, il est vrai qu'en théorie le comportement du simplexe peut être exponentiel.

Nous préciserons en section

5.2 les notions distance et δmax.

Pour ne pas surcharger le texte nous avons utilisé la notation en exposant : x i représente un vecteur complet à ne pas confondre à la i ème composante x i du vecteur x.

L'objet ici est de trouver une solution mais pas de prouver qu'il n'en existe pas.

Nous rappelons que δ [k * ] est un entier pair (Sect. 5.2).

Remerciements. Nous tenons à remercier Saïd Hanafi pour nous avoir procuré les jeux de la série GK18 ↔ GK24 (Sect. 6.2) sur lesquels il a travaillé ainsi que pour ses amples commentaires sur la MEI.


Michel Vasquez

Upper Bounds for the SPOT 5 Daily Photograph Scheduling Problem

Keywords: bounds, partition, constraint relaxation, tabu search, branch & bound

This paper introduces tight upper bounds for the daily photograph scheduling problem of earth observation satellites. These bounds, which were unavailable until now, allow us to assess the quality of the heuristic solutions obtained previously. These bounds are obtained with a partition-based approach following the "divide and pas conquer" principle. Dynamic programming and tabu search are conjointly used in this approach. We present also simplex-based linear programming relaxation and a relaxed knapsack approach for the problem.

Introduction

The daily photograph scheduling problem (DPSP) is one of the key applications for an earth observation satellite 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 overlapping trials and meeting the minimal transition time between two successive trials on the same camera. This constrained maximization problem is also important and interesting from a complexity point of view. Indeed, it can be formulated as a generalized knapsack problem, which is known to be NP-hard.

So far, several methods have been proposed to tackle this problem. In [START_REF] Verfaillie | Russian doll search for solving constraint optimization problems[END_REF], the authors introduced an exact algorithm called Pseudo Dynamic Search, which embodies a Branch & Bound technique within an iterative optimization process. This approach has been used to solve 20 benchmark instances presented in [START_REF] Bensana | Earth observation satellite management[END_REF]. For the 13 simple single-orbit instances, the approach managed to solve all of them to optimality. On the contrary, this method was unable to solve 6 of 7 multi-orbit instances within reasonable time. Indeed, the multi-orbit case is much more difficult than the single-orbit case due to the much larger size of the instances and the presence of a knapsack constraint.

Several heuristic approaches have also been developed for the DPSP. These heuristics include, among others, greedy procedures, algorithms based on simulated annealing and tabu search [START_REF] Bensana | Exact and inexact methods for the daily management of an earth observation satellite[END_REF][START_REF] Vasquez | A logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[END_REF]. In particular, 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], the authors presented an advanced tabu algorithm which finds the optimal solution for the single orbit instances and improves on the previously best known results for the multi-orbit instances. Notice that these heuristic solutions gives lower bounds for this maximization problem. Upper bounds are needed to assess the quality of heuristic solutions.

In [START_REF] Bensana | Exact and inexact methods for the daily management of an earth observation satellite[END_REF], the authors mentioned linear programming (LP) relaxation for this problem, but they did not report computational results. In [START_REF] Gabrel | Improved linear programming bounds via column generation procedure for the daily scheduling of earth observation satellite[END_REF], the author experimented this approach using CPLEX 4.1 and reported continuous optimal values (COV) for the single-orbit instances. However, these upper bounds are largely above the discrete optimal values (DOV): the ratio (COV-DOV)/COV goes from 28% to 74%! No result was reported for the much larger multi-orbit instances. The author also tried a new integer linear programming formulation of the problem based on decomposition and column generation techniques [START_REF] Gabrel | Improved linear programming bounds via column generation procedure for the daily scheduling of earth observation satellite[END_REF]. Using CPLEX 4.1, together with a column generation procedure, this approach produced better upper bounds for the single-orbit instances, reducing the above (COV-DOV)/COV ratio to the range of 0 to 20%. Once again however, no result was obtained for the multi-orbit instances, due to the huge number of columns that have to be managed during the resolution. Until now, there is no upper bound available for the multi-orbit instances of the daily photograph scheduling problem.

The study presented in this paper tries to fill this important gap. To achieve this goal, we experiment first with the most evident approach based on linear programming relaxation. We continue our investigation with dynamic programming applied to the problem where logic constraints are relaxed. As we see later, these approaches are unable to find tight upper bounds. We devise finaly a partition-based approach which gives much better bounds.

The paper is organized as follows. The DPSP problem and its "logic constrained" knapsack formulation are introduced in Section 2. The benchmark instances of the DPSP together with their best known results are presented in Section 3. In Sections 4 and 5 are presented LP relaxation approach and logic constraint relaxation approach. The partition-based approach is presented in Section 6. Upper bounds obtained with this approach are shown in Section 7. Conclusions are given in the last section.

SPOT photograph daily scheduling problem (DPSP)

We give now a brief review of the problem as well as a "logic-constrained" knapsack formulation presented 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].

Problem definition

We are given the following problem components.

• A set P = {p 1 , p 2 , . . . , p n } 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 p i , 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 p i , which represents the amount of memory required to record p i when it is taken. • A set of possibilities associated with each photograph p i in P corresponding to the different ways to take p i : (1) for a mono p i , 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 p i , there is one single possibility because a stereo photograph requires simultaneously the front and the rear camera. • A set of imperative constraints:

1. Binary constraint: for some couples (photo, camera), it is forbidden to schedule simultaneously p 1 on the camera x and p 2 on y. This constraint is the first type of logical constraint. 2. Ternary constraint: for some couples (photo, camera), it is forbidden to schedule simultaneously p 1 on the camera x, p 2 on y and p 3 on z. This constraint is the second type of logical constraint. 3. Capacity (or knapsack) constraint: the sum of the sizes of the scheduled photos cannot exceed the recording capacity on board.

The DPSP is then to find a subset P of P which maximizes the sum of the profits of the photographs in P and satisfies all the logical and knapsack constraints. In practice, both the number of photographs in P and the number of logical constraints may be quite large (more than one thousand for P and tens of thousands for logical constraints).

A "logic-constrained" knapsack formulation

A first integer formulation consists in considering a photo as an integer variable and representing the three cameras by 1, 2 and 3. Thus, a variable for a mono photo has a value domain of {0, 1, 2, 3} where the value 0 means the photo is not scheduled. Similarly, a variable for a stereo photo has a value domain of {0, 13} where the value 13 represents the simultaneous use of the cameras 1 and 3. Constraints and objective function may be deduced accordingly. More details about this formulation is given in [START_REF] Bensana | Exact and inexact methods for the daily management of an earth observation satellite[END_REF].

Another formulation is based on binary variables, each representing a couple (photo camera): x i = ( p, c) takes the value 1 if the photo p is taken by the camera c, 0 otherwise. A schedule corresponds to the non-zero components of a binary vector. This formulation requires the introduction of a supplementary constraint, called consistency constraint, stating that a photo will not be scheduled more than once.

We give now the formal definition of this formulation [START_REF] Vasquez | A logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[END_REF]. Let us define the following notations:

• m 1 : the cardinality of the set P of candidate photos; • D( p): the value domain of the photo p, D(p) = {1, 2, 3} if p is a mono photo, D( p) = {13} otherwise;

• n = p=m 1 p=1 |D( p)|: the number of binary variables of the problem; • m 1 vectors A 1 , . . . , A m 1 ∈ {0, 1} n : the non-zero components of each A p correspond to all the possible couples ( p, c) for the photo p with c being a camera;

• m 2 vectors A m 1 +1 , . . . , A m 1 +m 2 ∈ {0, 1} n : for each A i , m 1 + 1 ≤ i ≤ m 1 + m 2 , its 2 non- zero components correspond to the 2 couples ( p 1 , c 1 ), ( p 2 , c 2 ) involved in the (i -m 1 ) th binary constraint; • m 3 vectors A m 1 +m 2 +1 , . . . , A m 1 +m 2 +m 3 ∈ {0, 1} n : for each A i , m 1 + m 2 + 1 ≤ i ≤ m 1 + m 2 + m 3 , its 2 non-zero components correspond to the couples ( p 1 , c 1 ), ( p 2 , c 2 ), ( p 3 , c 3 ) involved in the (i -(m 1 + m 2 ))th ternary constraint; • m = m 1 + m 2 + m 3 + 1:

the total number of constraints;

• A m ∈ N n : the memory size of each couple ( p, c), i.e. the memory required to record p;

• A ∈ N m×n : the matrix composed of m vectors A 1 , ..., A m ; • b ∈ N m : -∀i ∈ [1, m 1 + m 2 ] b i = 1: consistency constraint and binary logical constraints; -∀i ∈ [m 1 + m 2 + 1, m 1 + m 2 + m 3 ] b i = 2:
ternary constraints; b m : recording capacity or knapsack constraint.

• c ∈ N n : the vector of profits associated to each couple (photo camera).

A 1 , . . . , A m-1 represent logical constraints. A m represents the knapsack constraint. The parameters n and m characterize the dimension of a given instance of the problem in this formulation: n is the number of binary variables and m the total number of constraints to be satisfied.

Using these notations, the initial daily photograph scheduling problem can be formulated as follows:

DPSP01 maximize z = c • x subject to A • x ≤ b and x ∈ {0, 1} n
We have thus a logic-constrained 0-1 knapsack problem, which is a special case of the general multidimensionnel knapsack problem (MKP01). Let us notice that in practice, the number of constraints in this formulation may be very important, up to several tens of thousands compared with only several tens constraints for well-known MKP01 benchmark instances.

Benchmark instances and their lower bounds

In [START_REF] Bensana | Earth observation satellite management[END_REF], the authors presented a set of 20 benchmark instances for the DPSP. 1 These instances belong to two series of different complexities. The first one has 13 instances corresponding to the simpler single-orbit case where the recording capacity (knapsack) constraint is absent. The second series includes 7 instances corresponding to the multi-orbit case where the recording capacity (knapsack) constraint is present. All the single-orbit instances have been solved to optimality. No optimal solution is known yet for 6 of the 7 multi-orbit instances.

Single-orbit instances

Table 1 summarizes the main characteristics of the 13 instances of the simple-orbit series. The first column gives the label of each instance, the second column the number of candidate photos in set P, the third column the number of binary variables. The next three columns indicate the number of binary and ternary constraints. The column z * indicates the optimal (maximal) values (given in italic numbers) for the objective function. These values have been obtained thanks to an exact algorithm called Pseudo Dynamic Search [START_REF] Verfaillie | Russian doll search for solving constraint optimization problems[END_REF]. The last column 1 • x * indicates the range for the number of taken photos in solutions found by the tabu search algorithms of [START_REF] Vasquez | A logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[END_REF].

Multi-orbit instances

Table 2 shows the main characteristics of the 7 instances of the multi-orbit case. The first six columns have the same meanings as in Table 1. The column b m defines the maximal recording capacity for the knapsack constraint. The column z * indicates either the optimal value of the objectif fonction (given in italic numbers) or the lower bound for each instance.

Notice that in addition to the presence of knapsack constraint, these instances are much larger than those of the single-orbit case.

Except the smallest instance 1502, neither optimal solution nor upper bound is known yet for these instances. The best known results have been obtained by the tabu search algorithm of [START_REF] Vasquez | A logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[END_REF], giving lower bounds for these instances.

Linear programming relaxation

One basic and general approach for generating upper bounds is Linear Programming (LP) relaxation. In LP relaxation we relax the integrality constraint of the initial problem and solve the relaxed problem using a standard method like simplex. Given the fact that there is no known result of LP relaxation for the muilti-orbit case of the general DPSP01. We decided to study first this basic approach.

Let us define the relaxed problem (denoted by DPSP in contrast to DPSP01) as follows:

DPSP maximize z = c • x subject to A • x ≤ b and x ∈ [0, 1] n
We solved exactly this relaxed DPSP using the simplex method. Given the huge size of some multi-orbit instances, we had to implement a compact version of the simplex method using the code proposed in [START_REF] Press | Numerical Recipes in C[END_REF]. Our implementation allowed us to deal with the most important instances which require up to 600 MB RAM.

We applied this approach to the instances of the single-orbit and multi-orbit cases. Upper bounds are reported in Tables 3 and4.

Upper bounds for single-orbit instances

From Table 3, we remark that the upper bounds z are very far from the optimal values z * of Table 1. The last column of Table 3 quantifies the gap between optimal continuous and binary values of the objectif function by the relative deviation (zz * )/z. The gap is in general more than 40% and goes beyong 50% for two instances. The gap may also be observed by comparing the columns 1 • x of Table 3 and1

• x * of Table 1.

Upper bounds for multi-orbit instances

From Table 4, we observe that the upper bounds for the multi-orbit instances are in general of better quality than for the single-orbit ones. Given the fact that the values z * of Table 2 are lower bounds obtained by tabu search, the stability of the relative deviation (zz * )/z constitutes a good indicator concerning the quality of the solutions of tabu search. Notice, however, the absolute values of z and 1 • x remain far away from those of z * and 1 • x * . It is generally believed that LP relaxation is not very powerful for generating good upper bounds. The above results are consistent with this fact.

Relaxing logic constraints

Given that the DPSP01 is defined by a knapsack constraint and a large number of logical constraints, we experimented a second approach based on the relaxation of these logical constraints. In this relaxed problem, the integrality constraint over the variables x i is maintained. Such a relaxation leads to the following binary knapsack problem (KP01): For this relaxed problem KP01, there are several exact algorithms for solving instances of medium size (n ≤ 200) [START_REF] Fayard | An algorithm for the solution of the 0-1 knapsack problem[END_REF][START_REF] Nauss | An efficient algorithm for 0-1 knapsack problem[END_REF]. When the values of the profit vector c are loosely correlated to the coefficients of the knapsack constraint A m , there is an algorithm for solving instances of very large size (n ≤ 100,000) [START_REF] Martello | Knapsack Problems: Algorithms and Computer Implementations[END_REF].

KP01 maximize z = c • x subject to A m • x ≤ b m and x ∈ {0, 1} n
There exists also a pseudo polynomial algorithm for solving KP01 using dynamic programming [START_REF] Bellman | Applied Dynamic Programming[END_REF]Gondran and Minoux, 1985;[START_REF] Smith | Dynamic Programming: A Practical Introduction[END_REF]. This algorithm has a space and time complexity O(n × (b m + 1)). In our case, b m = 200 for all the multi-orbit instances, this algorithm is quite interesting for the problem. We have implemented this algorithm and the results for the multi-orbit instances are given in Table 5.

From Table 5, one observes that bounds z are worse that those of z obtained with LP relaxation. This is not really surprising given the large number of relaxed logical constraints. However, compared with LP relaxation, the running time of this approach is much faster: on a PIII500 MHZ, less than 2 seconds are necessary for the dynamic programming algorithm, 10 minutes to three days for the simplex algorithm.

In summary, neither LP relaxation nor relaxing logical constraints is able to produce good upper bounds for the benchmark instances. In the next section, we present a specialized approach which will give us upper bounds of high quality.

A partition based approach

Rationale

The partition-based approach follows the well-known "divide and conquer" principle. The rationale of this approach is the following.

We have exhaustive search algorithms which are able to solve exactly small problems, but have difficulties to tackle larger ones. We divide thus a large DPSP problem into several smaller sub-problems and solve these smaller problems exactly. Using such a strategy, we relax naturally the constraints which link some sub-problems. The sum of the optimal values of all the sub-problems must be greater or equal to the optimum of the initial problem, leading to an upper bound. This argument may be formally stated as follows.

• Let X be the set of all the couples ( p, c) (variables) of a DPSP01 instance; • Let z be the optimal value of DPSP01;

• Let {X l } 1≤l≤k a partition of X composed of k classes;

• Define now k sub-problems DPSP01(X l ) for 1 ≤ l ≤ k, each DPSP01(X l ) being defined by the set of variables X l and the constraints containing only these variables; • Let {z l } 1≤l≤k the set of optimal values of the above k sub-problems DPSP01(X l ).

Here constraints connecting two or more sub-problems are ignored, thus the set of subproblems DPSP01(X l ), 1 ≤ l ≤ k constitutes a relaxation of the initial problem DPSP01. Thus, we have the following relation:

ẑ = k l=1 zl ≥ z
That is, the value ẑ gives an upper bound of the initial DPSP01(X ) instance.

Our partition-based approach may be summarized as follows.

1. Generate a partition {X l } 1≤l≤k of the variable set X of the given DPSP01 instance.

2. Solve exactly each of k sub-problems DPSP01(X l ) (1 ≤ l ≤ k) to get the set of optimal values {z l } 1≤l≤k .

Sum up the values of the set {z

l } 1≤l≤k .
In what follows, we describe first the exact algorithm for solving the sub-problems and then the heuristics for partitioning an initial problem.

An iterative enumerative algorithm

To solve exactly each DPSP01(X l ), we developed an iterative backtracking algorithm. This algorithm is inspired of the Russian Doll Search [START_REF] Bensana | Exact and inexact methods for the daily management of an earth observation satellite[END_REF][START_REF] Verfaillie | Russian doll search for solving constraint optimization problems[END_REF], which is itself a nested Branch & Bound algorithm. For each set of variables X l 1 ≤ l ≤ k, the algorithm solves successively X l nested sub-problems including only 1 variable, then 2 variables...then |X l | variables (see Algorithm 1). The exact value obtained at a step is used at the next step in order to prune the search tree.

This algorithm uses a static order of the variables in

X l = {x 1 • • • x |X l | }. Each entry i of the table zmax records the optimal value of the sub-problem DPSP01({x i+1 • • • x |X l | }). Algorithm 1: SOLVE(X l ) begin i ← |X l | zmax[i] ← 0 i ← i -1 while i ≥ 0 do zmax[i] ← ENUMERATE(X l , i) i ← i -1 zl ← zmax[0] end Algorithm 2: ENUMERATE(X l , i) begin j, z, z * ← i, 0, -1 go forward if j = |X l | then [1] if z > z * then z * ← z backtrack else j ← j + 1 x j ← 1 z ← z + l j if there is constraint violation then backtrack go forward backtrack if x j = 0 then j ← j -1 if j = i then return z * backtrack else x j ← 0 z ← z -l j [2] if z + zmax[ j] ≤ z * then

backtrack go forward end

The most important element of this nested search procedure is ENUMERATE(X l , i) (see Algorithm 2). This algorithm realises a deep-first search, backtracks only on the last |X l |-i elements of the set X l . Line ( 2), together with the update of line (1) allows a better pruning of the search tree than a standard depth first Branch & Bound search.

Not surprisingly, this algorithm has an exponential time complexity in the worse case with respect to the number of the variables of the problem. However, the algorithm is able to solve problems of reasonable size. Next section describes a way allowing us to partition a large problem into such solvable (sub-)problems.

Heuristics for partitioning

An equal size partition.

In order to partition a given DPSP01, one must answer two questions. First, what is the appropriate number k of the sub-problems? Second, for a fixed k, how should the initial problem be partitioned. Intuitively, both points would have important influence on the quality of the bounds. These issues are further studied in the next section. In fact, we will see that an optimal solution for these two points may be as hard as solving the initial problem. For the moment, we limit ourselves to a trivial partition in order to get a primary idea about the merit of this partition-based approach for upper bounds.

For a fixed number k, the n variables of the problem are divided into k classes of equal size n/k following their order in n: the first n/k variables of n go to the class X 1 , the next n/k variables to the class X 2 and so on. Table 6 shows the results for the instance 1401 (n = 914) using this partition strategy with k fixed at 10 different values from 20 to 11. The column #RC indicates the number of relaxed constraints (for a total of 15294 constraints): a relaxed constraint is one whose variables belong to more than one variable class (except the knapsack constraint which is not relaxed). Comparing Tables 6 and4, we observe that these upper bounds are better than those of LP relaxation. However, these bounds are still far from the best known lower bound which is 176056 (see Table 2). To improve these bounds, we may decrease the number of partitions k. Unfortunately, this increases rapidly the running time of the approach. We observe also that the bounds don't improve regularly when the number of partitions decreases: the bound with 19 partitions is better than those with 18 and 17.

In fact, for a given instance, there exist some partitions better than others. In particular, the number of relaxed constraints should be used as a criterion for determining the partitions. This idea is studied in detail in the next section leading to a heuristic method for a more efficient partitioning.

A criterion for optimized partitioning.

In this section, we introduce an optimization criterion for a better partitioning. The basic idea is the following. For a fixed number k of classes, a good partition should minimize the "number" of inter-class constraints. Such a partition will generate classes with a maximum of intra-class constraints, helpful for the exact algorithm.

Recall that there are different constraints in the DPSP01. The optimization criterion considers consistency, binary and ternary constraints and introduces a hierarchy for these constraints with a decreasing importance in that order. 5 Let {X l } 1≤l≤k be a partition of X . We represent this hierarchy by using the ω function:

ω(x i , x j ) =      8 if ∃k ∈ [1, m 1 ] such that A ki .A k j = 1 4 if ∃k ∈ [m 1 + 1, m 1 + m 2 ] such that A ki .A k j = 1 1 si ∃k ∈ [m 1 + m 2 + 1, m -1] such that A ki .A k j = 1
The values 8, 4 and 1 represent the relative importance that we give to each constraint and are empirically determined. We define also the following binary function κ: κ(x i , x j ) = 0 if variables x i and x j belong to a same class 1 otherwise

Then we look for a partition {X l } * of X which minimizes the function:

f ({X l }) = i< j κ(i, j).ω(i, j)
Figure 1 shows a small example with a partition of three classes. The points represent couples (photo, camera). The edges represent logical inter-class contraints. All the possible cases are given in this figure :   • one consistency constraint between couples (1,1) and (1,2); • one inter-class binary constraint between couples (3,1) and (4,2); • the two possible cases for inter-class ternary constraints: (2,1), (8,2) and (9,3) on the one hand, (5,1), (6,2) and (7,3) on the other hand. Now, consider the graph whose nodes represent the classes of a partition and whose (weighted) edges represent constraints of the given DPSP01 instance. Then the task is to find a partition such that cut edges (those having their two end points in different classes) have a minimal total sum of their weights. This problem is thus a generalized version of the well-known NP-hard graph partitioning problem (Garey and Johnson, 1979, p. 209).

Partitioning with tabu search.

Given the intrinsic difficulty of the above partitioning problem, we turn to a heuristic approach for generating good but not necessarily optimal partitions. For this purpose, we developed a tabu search algorithm, which improves iteratively an initial trivial partition. Notice that tabu search has been applied to the the conventional graph partitioning problem, see for instance [START_REF] Friden | Stabulus: A technique for finding stable sets in large graphs with tabu search[END_REF][START_REF] Rolland | Tabu search for graph partitioning[END_REF]. Our tabu search algorithm shares some common features with these previous implementation. Some specific techniques are introduced to cope with the particular nature of our problem.

Given a DPSP01 instance and a fixed number k, the tabu search algorithm tries to find a partition {X l } 1≤l≤k of the initial variable set X while minimizing the previously defined f fonction (Section 6.3.2). In the tabu search algorithm, a configuration represents a partition composed of a fixed number k classes. We describe now the neighborhood relations and tabu tenure of this Tabu algorithm.

Two neighborhood relations are used by the algorithm in an alternative way. The first neighborhood is symmetric and the size of each class of a partition is kept constant. 6 A neighboring partition is obtained by simply exchanging two nodes between two classes. More precisely, at each iteration of the algorithm, we first select a node s such that it has the maximal number of edges going out from its class X s . We then exchange s with a node t of another class X t (X s = X t ).

The second neighborhood is not symmetric. The size of each class of a partition may vary during the search. With this neighborhood, one chooses a variable s in a class X s such that |X s | ≥ s min and moves s into another class X t such that |X t | < s max . s min and s max are two symmetric values around n/k:

s max - n k = n k -s min
This principle, inspired of the work presented in [START_REF] Rolland | Tabu search for graph partitioning[END_REF] has, among others, the advantage of encouraging the grouping of the binary variables of a same photo in a same class.

The complexity of searching the first neighborhood is linear with respect to the instance size, because the first element of a move is chosen independently of the second element. For the second neighborhood, a trivial implementation will lead to a complexity of O(n × k). This complexity may be reduced using special data structures such as buckets [START_REF] Battiti | Greedy, prohibition, and reactive heuristics for graph partitioning[END_REF] when the number of the classes k is greater than two.

The tabu search algorithm uses mainly the first neighborhood during its search, i.e. during its search intensification phases and changes to the second neighborhood during its search diversification phases.

Each time a move is carried out, the reversing move is classified tabu for a number of iterations (tabu tenure). The tabu tenure of a move is determined dynamically using the following formula:

date(t, X s ) + freq(t) ≥ iter
where iter is the current iteration number, freq(t) the number of times node t has been exchanged with another node, date(t, X s ) the time stamps (an iteration number) when t was moved into X s . In addition to the number of classes k for a partition, the tabu search algorithm requires some other parameters, in particular, s min and s max .

In order to get a rough idea about the merit of this approach, we take again the instance 1401 used for the trivial partition (see Section 6.3.1). As before, we use 10 different partition sizes going from 20 classes to 11 classes. Using the approach described in this section, we obtain the results showed in Table 7.

We observe that these upper bounds ẑ are much better than previous ones and the number of relaxed constraints #RC is much smaller. The running time to obtain these results is less than one minute on a PIII500 PC. Next section shows more detailed results for all the benchmark instances using this approach.

Upper bounds for the DPSP01 benchmark instances

New upper bounds for the single-orbit instances

For the single-orbit instances, we may compare directly our results with the optimal values z * reported in [START_REF] Verfaillie | Russian doll search for solving constraint optimization problems[END_REF]. Comparisons are also given with previous known upper bounds obtained with column generation techniques [START_REF] Gabrel | Improved linear programming bounds via column generation procedure for the daily scheduling of earth observation satellite[END_REF]. This allows one to further appreciate the advantage of the partition-based approach. Results are given in Table 8 ("-" means no result is available).

From the table, we see that the upper bound of 9 out of 13 instances coincides with the optimal value and for the 4 remaining instances, two bounds are very close to the optimal value. We remark that the best partition found has only two or three classes. Finally, we observe the partition-based bounds are much better than the previous known ones.

Tight upper bounds for the multi-orbit instances

We present now the most important results of this paper, i.e. the upper bounds for the multi-orbit instances, which remained unknown so far. Results are given in Table 9.

The first column z * shows the lower bounds obtained with the tabu search algorithm described 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]. Columns c 1 , c 2 , c 3 , A m . x have the following meaning and together they give indications about the degree of unfeasibility of the solutions.

• c 1 = the number of relaxed consistency constraints;

• c 2 = the number of relaxed binary constraints; • c 3 = the number of relaxed ternary constraints;

• A m • x = memory consummation which should be ≤200 according to the knapsack constraint.

The last column (ẑz * )/ẑ contains the most important information. We observe that the upper bounds ẑ are close or very close to the lower bounds z * for these instances. This observation has two immediate important implications. First, we may conclude that the heuristic solutions presented 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] are of high quality. For three instances (1021,1504,1506), the heuristic solution is already very close to the optimal value, if it is not optimal. Second, we may conclude that these upper bounds are very tight, especially for the last four instances in the table. On the contrary, further improvements may be expected concerning the first three instances for both upper and lower bounds.

In general, few logical constraints are violated (relaxed). On the contrary, we observe an important memory excess with respect to the capacity constraint (≤200). This is not surprising given that the knapsack constraint is not taken into account by the partition algorithm.

Finally, the total resolution time (partitioning with a tabu search plus exact resolution of each sub-problem) varies from several hours to several days on a PIII 500 MHZ.

Conclusion

The main result of this study is the achievement of a set of tight upper bounds for a set of benchmark instances of the daily photograph scheduling problem of earth observation satellites such as Spot 5. Contrasting these upper bounds with the lower bounds of [START_REF] Vasquez | A logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[END_REF] allows us not only to assess the quality of the previous heuristic solutions but also to assess the quality of the upper bounds on the other hand. These upper bounds may be also helpful for devising more efficient exact algorithms. Such an algorithm may hopefully solve optimally all the benchmark instances.

The upper bounds are obtained with an original partition-based approach. This approach is based on the well-known "divide and conquer" principle. The initial problem is divided into sub-problems which are solved exactly by an iterative enumeration algorithm. A tabu search algorithm is used to determine optimized partitions.

Two more conventional approaches were also experimented. The first one is based on LP relaxation with simplex. The second relaxes the logical constraints and solves a knapsack problem with dynamic programming. Both approaches led only to weak upper bounds.

Finally, this work shows the interest of combining a heuristic search and an exact search for large and difficult combinatorial optimization.

Figure 1 .

 1 Figure 1. Example of a partition: k = 3, #RC = 4 et f = 17.

Table 1 .

 1 Benchmark instances for the simple-orbit case.

	Pb.	Photos	n	m 1	m 2	m 3	z *	1 • x *
	54	67	125	67	389	23	70	45
	29	82	120	82	610	0	12032	34
	42	190	304	190	1762	64	108067	80
	28	230	346	230	6302	590	56053	46-47
	5	309	809	309	13982	367	115	93-96
	404	100	158	100	919	18	49	31-33
	408	200	328	200	2560	389	3082	60-63
	412	300	544	300	6585	389	16102	77-79
	11 2	364	692	364	9456	4719	22120	95-98
	503	143	259	143	705	86	9096	69-70
	505	240	448	240	2666	526	13100	82-85
	507	311	573	311	5545	2293	15137	89-92
	509	348	652	348	7968	3927	19125	93-96

Table 2 .

 2 Benchmark instances for the multi-orbit case.

	Pb.	Photos	n	m 1	m 2	m 3	b m	z *	1 • x *
	1401	488	914	488	11893	2913	200	176056	146
	1403	665	1317	665	14997	3874	200	176140	216
	1405	855	1815	855	24366	4700	200	176179	249
	1021 3	1057	2355	1057	30058	5875	200	176245	309
	1502	209	413	209	296	29	200	61158	166
	1504	605	1253	605	5106	882	200	124243	276
	1506	940	2060	940	19033	4775	200	168247

Table 3 .

 3 Upper bounds with LP relaxation: Single-orbit instances.

	Pb.	n	m	Pivots	z	1 • x	(z -z * )/z (%)
		125	479	136	83.00	55.00	15.66
		120	692	140	13057.00	54.50	7.85
		304	2016	460	190567.50	125.00	43.29
		346	7122	599	221090.50	147.50	74.65
		809	14658	1625	315.00	281.25	63.49
		158	1037	181	96.00	64.50	48.96
		328	3149	436	5188.00	133.00	40.59
		544	7274	801	31323.50	212.50	48.59
		692	14539	1108	40416.00	266.00	45.27
		259	934	292	12637.50	101.75	28.02
		448	3432	564	22236.00	173.50	41.09
		573	8149	833	27361.50	222.50	44.68
		652	12243	1005	36394.00	252.00	47.45

Table 4 .

 4 Upper bounds with LP relaxation: Multi-orbit instances.

	Pb.	n	m	Pivots	z	1 • x	A m . x	(z -z * )/z (%)
	1401	914	15295	3261	300000.00	151.00	200.00	41.31
	1403		19537	3828	300149.00	283.75	200.00	41.32
	1405		29922	4342	300207.00	344.25	200.00	41.31
	1021		36991	5122	300385.00	507.75	200.00	41.33
	1502	413	535	313	64160.50	169.75	147.50	4.68
	1504		6594	1368	191279.00	352.25	200.00	35.05
	1506		24749	3682	276863.00	492.25	200.00	39.23

Table 5 .

 5 Maxima of KP01.

	Pb.	z	Pb.	z
	1401	332000	1502	89196
	1403	332182	1504	245276
	1405	332255	1506	294440
	1021	332462

Table 6 .

 6 Trivial partitions for the instance 1401.

	k	#RC	ẑ	k	#RC	ẑ
	20	8635	263069	15	7728	247070
	19	8459	252070	14	7242	240064
	18	8321	258066	13	6973	245062
	17	8039	254067	12	6648	242064
	16	7865	247067	11	6513	243063

Table 7 .

 7 Advanced partitions with tabu search for the instance 1401.

	k	#RC	ẑ	k	#RC	ẑ
	20	3094	187062	15	2585	184062
	19	3532	186064	14	3789	188062
	18	3382	187063	13	3217	186062
	17	3210	187062	12	2560	184062
	16	3297	186063	11	1940	185062

Table 8 .

 8 Comparison of upper bounds for the simple-orbit instances.

		Column-generation-based upper bounds		Partition-based upper bounds
	Pb.	ẑ	(ẑ -z * )/ẑ (%)	k	ẑ	(ẑ -z * )/ẑ (%)
	54	71.44	2.02	2	70	0
	29	-	-	3	12032	0
	42	108067	0.00	3	108067	0
	28	70053.00	19.98	2	58053	3.45
	5	119.00	3.36	3	116	0.86
	404	53.66	8.68	3	49	0
	408	3091.75	0.32	3	3083	0.03
	412	71.44	2.02	2	16102	0
	11	-	-	2	22120	0
	503	9595.00	5.20	2	9096	0
	505	14107.75	7.14	3	13103	0.02
	507	17639.22	14.19	2	15137	0
	509	-	-	2	19125	0

Table 9 .

 9 Tight upper bounds for the multi-orbit instances.

	Pb.	z *	k	ẑ	c 1	c 2	c 3	A m • x	(ẑ -z * )/ẑ (%)
	1401	176056	8	180062	13	25	1	221	2.22
	1403	176140	7	180160	6	15	0	249	2.23
	1405	176179	6	179226	2	11	3	283	1.70
	1021	176246	10	177304	5	21	5	291	0.60
	1502	61158	2	61158	0	0	0	148	0
	1504	124243	3	124258	0	3	0	237	0.01
	1506	168247	6	168294	2	13	0	283	0.03

Acknowledgments

The authors highly appreciate the valuable and detailed comments of the anonymous reviewers, which helped to improve the presentation of the paper.

Notes