Thèse de doctorat : Informatique : Lille 1 : 2000. / Résumé en français et en anglais. Bibliogr. p. 177-188.

La tomographie est un ensemble de techniques visant à reconstruirel'intérieur d'un objet sans toucher l'objet lui même comme dans le casd'un scanner. Les principes théoriques de la tomographie ont été énoncéspar Radon en 1917. On peut assimiler l'objet à reconstruire à une image,matrice, etc.Le problème de reconstruction tomographique consiste à estimer l'objet àpartir d'un ensemble de projections obtenues par mesures expérimentalesautour de l'objet à reconstruire. La tomographie discrète étudie le cas où lenombre de projections est limité et l'objet est défini de façon discrète. Leschamps d'applications de la tomographie discrète sont nombreux et variés.Citons par exemple les applications de type non destructif comme l'imageriemédicale. Il existe d'autres applications de la tomographie discrète, commeles problèmes d'emplois du temps.La tomographie discrète peut être considérée comme un problème d'optimisationcombinatoire car le domaine de reconstruction est discret et le nombrede projections est fini. La programmation mathématique en nombres entiersconstitue un outil pour traiter les problèmes d'optimisation combinatoire.L'objectif de cette thèse est d'étudier et d'utiliser les techniques d'optimisationcombinatoire pour résoudre les problèmes de tomographie.

Cette thèse considère le problème de sélection et d'ordonnancement des prises de vue d'un satellite agile d'observation de la Terre. La mission d'un satellite d'observation est d'obtenir des photographies de la surface de la Terre afin de satisfaire des requêtes d'utilisateurs. Les demandes, émanant de différents utilisateurs, doivent faire l'objet d'un traitement avant transmission d'un ordre vers le satellite, correspondant à une séquence d'acquisitions sélectionnées. Cette séquence doit optimiser deux objectifs sous contraintes d'exploitation. Le premier objectif est de maximiser le profit global des acquisitions sélectionnées. Le second est d'assurer l'équité du partage des ressources en minimisant la différence maximale de profit entre les utilisateurs. Deux métaheuristiques, composées d'un algorithme génétique à clé aléatoire biaisées (biased random key genetic algorithm - BRKGA) et d'une recherche locale multi-objectif basée sur des indicateurs (indicator based multi-objective local search - IBMOLS), sont proposées pour résoudre le problème. Pour BRKGA, trois méthodes de sélection, empruntées à NSGA-II, SMS-EMOA, et IBEA, sont proposées pour choisir un ensemble de chromosomes préférés comme ensemble élite. Trois stratégies de décodage, parmi lesquelles deux sont des décodages uniques et la dernière un décodage hybride, sont appliquées pour décoder les chromosomes afin d'obtenir des solutions. Pour IBMOLS, plusieurs méthodes pour générer la population initiale sont testées et une structure de voisinage est également proposée. Des expériences sont menées sur des cas réalistes, issus d'instances modifiées du challenge ROADEF 2003. On obtient ainsi les fronts de Pareto approximés de BRKGA et IBMOLS dont on calcule les hypervolumes. Les résultats de ces deux algorithmes sont comparés.

Cette thèse est consacrée à l'étude de plusieurs problèmes d'optimisation combinatoire qui se présentent dans le domaine du calcul parallèle embarqué. En particulier, la gestion optimale de la mémoire et des problèmes d'ordonnancement pour les applications flot de données exécutées sur des processeurs massivement multicœurs sont étudiés. Deux techniques d'optimisation d'accès à la mémoire sont considérées : la réutilisation des données et le préchargement. La gestion des accès à la mémoire est déclinée en trois problèmes d'optimisation combinatoire. Dans le premier problème, une stratégie de préchargement pour les applications flot de données est étudiée, de façon à minimiser le temps d'exécution de l'application. Ce problème est modélisé comme un flow shop hybride sous contraintes de précédence, un problème \mathcal{NP}\text{-difficile} . Un algorithme de résolution heuristique avec deux bornes inférieures sont proposés afin de faire une estimation conservatrice, quoique suffisamment précise, de la distance à l'optimum des solutions obtenues. Le deuxième problème traite de l'exécution conditionnelle dépendante des données et de la gestion optimale du préchargement pour les structures de branchement. Quelques fonctions économiques, ainsi que des techniques de préchargement, sont examinées. Dans tous ces cas des algorithmes de résolution polynomiaux sont proposés. Le troisième problème consiste à ordonner un ensemble de tâches de façon à maximiser la réutilisation des données communes. Ce problème étant \mathcal{NP}\text{-difficile} , ce que nous avons établi, nous avons proposé deux algorithmes heuristiques. La distance à l'optimum des solutions est estimée en utilisant des solutions exactes. Ces dernières sont obtenues à l'aide d'une méthode branch-and-bound que nous avons proposée.

La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des graphes. Il s'agit en effet de la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle on ignore encore s'il existe un algorithme polynomial permettant de résoudre le problème du stable maximum. Or ce problème, dont on sait qu'il est difficile en général, est d'une grande importance en pratique (problèmes de planification, d'allocation de registres dans un processeur, biologie moléculaire...). Dans cette thèse, nous commençons par dresser un état de l'art complet des méthodes utilisées pour résoudre le problème dans des sous-classes de graphes sans P5, puis nous étudions et résolvons ce problème dans une sous-classe particulière, la classe des graphes sans P5 3-colorables. Nous apportons également des solutions aux problèmes de la reconnaissance et de la coloration de ces graphes, chaque fois en temps linéaire. Enfin, nous définissons, caractérisons et sommes capables de reconnaître les graphes "chain-probe", qui sont les graphes auxquels il est possible de rajouter des arêtes entre certains sommets de sorte qu'ils soient bipartis et sans P5. Les problèmes de ce type proviennent de la génétique et ont également des applications en intelligence artificielle.

L'objectif de cette thèse porte sur des recherches théoriques et algorithmiques d'optimisation locale et globale via les techniques de programmation DC & DCA, Séparation et Evaluation (SE) ainsi que les techniques de relaxation DC/SDP, pour résoudre plusieurs types de problèmes d'optimisation non convexe (notamment en Optimisation Combinatoire et Optimisation Polynomiale). La thèse comporte quatre parties :La première partie présente les outils fondamentaux et les techniques essentielles en programmation DC & l'Algorithme DC (DCA), ainsi que les techniques de relaxation SDP, et les méthodes de séparation et évaluation (SE).Dans la deuxième partie, nous nous intéressons à la résolution de problèmes de programmation quadratique et linéaire mixte en variables entières. Nous proposons de nouvelles approches locales et globales basées sur DCA, SE et SDP. L'implémentation de logiciel et des simulations numériques sont aussi étudiées.La troisième partie explore des approches de la programmation DC & DCA en les combinant aux techniques SE et SDP pour la résolution locale et globale de programmes polynomiaux. Le programme polynomial avec des fonctions polynomiales homogènes et son application à la gestion de portefeuille avec moments d'ordre supérieur en optimisation financière ont été discutés de manière approfondie dans cette partie.Enfin, nous étudions dans la dernière partie un programme d'optimisation sous contraintes de type matrices semi-définies via nos approches de la programmation DC. Nous nous consacrons à la résolution du problème de réalisabilité des contraintes BMI et QMI en contrôle optimal.L'ensemble de ces travaux a été implémenté avec MATLAB, C/C++ ... nous permettant de confirmer l'utilisation pratique et d'enrichir nos travaux de recherche.

Au fil des années, un nombre croissant de méthodes de résolution ont été proposées afin de traiter des problèmes plus grands et plus complexes. Parmi ces méthodes, les métaheuristiques sont largement utilisées dans le monde académique et industriel afin de résoudre efficacement des problèmes d'optimisation et de satisfaction de contraintes. Toutefois la conception de métaheuristiques de plus en plus performantes produit souvent des systèmes fortement complexes dont l'utilisation demande une expertise non négligeable aussi bien du problème lui-même que de la façon de paramétrer la méthode de résolution. Concevoir des algorithmes de recherche autonomes est donc une question importante. Cette thèse traite du problème de la gestion et de la sélection d'opérateurs dans le contexte de la recherche locale, au sein d'un contrôleur générique. Celui a pour but de pouvoir être réutilisé facilement pour traiter différents problèmes. Nous nous attachons donc à concevoir des méthodes simples et robustes. La sélection des opérateurs se base sur un apprentissage des performances antérieures de chaque opérateur afin de déterminer les opérateurs vraisemblablement les plus bénéfiques à chaque pas de la recherche. Pour effectuer ces choix, le contrôleur se base sur la capacité des opérateurs à améliorer la qualité des solutions ainsi que sur la faculté de produire des solutions qui diffèrent de celles déjà obtenues. Les méthodes proposées sont testées sur différents problèmes théoriques et pratiques d'optimisation combinatoire et de satisfaction de contraintes. Les résultats obtenus montrent qu'il est possible d'obtenir des résultats corrects avec des méthodes simples. Les mécanismes adaptatifs proposés se révèlent robustes sur différents problèmes.

Cette thèse considère le problème consistant à intégrer les décisions de routage et stockage lors de la conception de la chaîne logistique. Le but est de sélectionner des dépôts parmi un ensemble de candidats pour desservir un ensemble de détaillants à l’aide d’une flotte de véhicules de capacité permettant visiter plus d’un détaillant par route. On cherche à déterminer la localisation de ces dépôts et les tournées des véhicules afin de maintenir leurs niveaux optimaux de stocks. La demande chez les détaillants est connue à l’avance. Des applications dans les domaines de la logistique humanitaire et militaire sont envisageables. Pour résoudre le problème, deux matheuristiques sont proposées. Dans la première partie, une méthode coopérative qui combine des méthodes exactes pour le problème de conception de la chaîne logistique et des méthodes heuristiques de routage est présentée. Dans la deuxième partie, une méthode de décomposition utilisant une réformulation de Dantzig-Wolf sur les variables de routage est proposée. L’algorithme intègre les concepts de génération de colonnes, relaxation lagrangienne et recherche locale. Les résultats montrent la capacité des algorithmes à trouver des solutions de bonne qualité et nous estimons de façon empirique l’impact de considérer un modèle intégré au lieu d’utiliser une méthode d’optimisation séquentielle. De plus, les résultats des méthodes présentées sur des sous-problèmes sont aussi étudiés. Ces sont: le problème de localisation-routage, le problème de tournées avec gestion de stocks, et le problème de plus court chemin généralisé / The problem of designing a supply chain including simultaneously routing and inventory management decisions is studied in this thesis. The objective is to select a subset of depots to open, the inventory policies for a 2-echelon system, and the set of routes to perform distribution from the upper echelon to the next using a homogeneous fleet of vehicles over a finite planning horizon. Demand is considered to be known. Applications are found in humanitarian logistics and military logistics. To solve the problem, two matheuristic procedures are developed. On the first part a cooperative algorithm combining exact methods for the supply chain design problem and routing heuristics is presented. On the second part, a partition is proposed using a Dantzig-Wolf reformulation on the routing variables. An hybridization between column generation, Lagrangian relaxation and local search is proposed in this part, put together as a heuristic method. Furthermore, results demonstrate the capability of the algorithms to compute high quality solutions and empirically estimate the improvement in the cost function of the proposed model when compared to a sequential optimization approach. Furthermore, results of the proposed methodologies on benchmark instances for subproblems are studied as well. Those are the capacitated location-routing problem, the inventory-routing problem, and the generalized elementary shortest path problem

Les travaux de cette thèse concernent la résolution d'un problème de planification dans un réseau de distribution à deux échelons intégrant la gestion de stocks de produits périssables, le dimensionnement de lots, des alternatives d'approvisionnement. La livraison s'effectue directement entre un fournisseur et son client, sans tournée avec une flotte homogène de véhicules. Nous proposons un programme linéaire mixte, une heuristique constructive (déterministe) et une heuristique réactive randomisée. Pour certaines instances, le solveur de programme linéaire mixte ne fournit pas une bonne solution réalisable dans la limite de temps définie ou prend beaucoup de temps. Les heuristiques proposées sont rapides mais ne donnent pas de bonnes solutions pour certaines instances. Pour améliorer la qualité des solutions des heuristiques, la descente à voisinage variable (VND), la recherche locale itérative (ILS) et la recherche locale itérative à démarrages multiples (MS-ILS) sont développées.Toutes ces méthodes ont été incluses dans un APS (Advanced Planning System) et sont comparées avec CPLEX sur des instances extraites de bases de données réelles. Un générateur aléatoire d'instances est conçu pour plus de diversité pour les tests. Une relaxation lagrangienne est implémentée pour comparer les solutions des instances, pour lesquelles CPLEX ne fournit pas une bonne solution réalisable dans le temps imparti, avec les autres méthodes. Une heuristique lagrangienne, utilisant la relaxation lagrangienne et une heuristique de réparation, est également développée / This work presents a planning problem in a distribution network incorporating two levels inventory management of perishable products, lot-sizing, multi-sourcing and transport capacity with a homogeneous fleet of vehicles. A mixed integer linear programming (MILP) a greedy heuristic and a reactive randomized heuristic are developed to solve this real planning problem. There are some instances for which the solver CPLEX cannot give a good upper bound within the limited time and for other instances it takes a lot of time to solve MILP. The heuristics are alternatives to the mixed integer linear program to quickly solve some large instances taking into account original and difficult constraints. For some instances the gap between the solutions of the solver (MILP) and the heuristics becomes quite significant. The variable neighborhood descent (VND), the iterated local search (ILS) and the multi-start iterated local search (MS-ILS) are implemented. These methods are included in an APS (Advanced Planning System) and compared with a MILP solver. The instances are derived from actual data or built using a random generator of instances to have wider diversity for computational evaluation. A lagrangian relaxation is developed to compare the solutions of the instances, for which CPLEX cannot give a good upper bound within the limited time, with the other methods (greedy heuristic, VND, ILS and MS-ILS). A lagrangian heuristic is proposed; the solution of lagrangian relaxation is used to build a feasible solution with a repair heuristic

La validation des charges utiles des satellites de télécommunication nécessite des opérations coûteuses en temps et en personnel. Ce coût augmente régulièrement du fait de la complexité croissante des charges utiles. Il est donc crucial pour Astrium d'optimiser la réalisation des opérations de test. L'objectif de cette thèse CIFRE menée en collaboration entre Astrium et l'Onera est de développer une suite logicielle d'aide à la génération de plans de test. Le problème de génération de plan de test a été modélisé sous forme de graphe orienté à états. La NP-complétude de ce problème a été établie. Des modèles mathématiques ont été construits en programmation linéaire en nombres entiers et en programmation par contraintes en vue d'une résolution par des solveurs génériques. Cependant, ces solveurs génériques se sont heurtés à des problèmes d'insuffisance de mémoire liés à la très grande taille des instances à traiter. Ceci nous a conduits à développer un solveur spécialisé à base de recherche arborescente faisant appel à des mécanismes spécifiques de choix de variables et de valeurs, de propagation de contraintes, de calcul de borne, de retour-arrière, d'apprentissage et de redémarrage. Un solveur spécialisé à base de recherche locale a été développé en parallèle. Les résultats obtenus par ces différents solveurs avec différents paramétrages ont pu être comparés. / Telecommunication satellite payload validation requires operations which are expensive in terms of time and manpower. This cost is constantly increasing as the payloads become more and more complex. It is crucial for Astrium to optimise the testing phase to keep these costs under control. The objective of this CIFRE thesis, conducted in collaboration with Astrium and Onera, is to develop a software suite to help generate test plans for the payloads.The problem of generating test plans was modeled using the form of a directed graph with states. The NP-completeness of this problem was proven. Mathematical models were built using integer linear programming and constraint programming with a view to solving the problems using generic solvers. However, these generic solvers had problems due to insufficient memory on account of the large size of instances to be handled. These problems led us to develop a specialised solver using a tree search, with special mechanisms for choosing variables and values, propagating constraints, computing bounds, backjumping,learning, and restarting. A specialised solver based on local search was developed in parallel.The results obtained by these different solvers with different settings were compared.