Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Télédetection en milieu périurbain. Détection et localisation du changement de l'occupation du sol par intégration des donnés-satellite SPOT HRV dans un système d'information géographique

Thèse pour obtenir le grade de DOCTEUR DE L' UNIVERSITÉ PARIS XII, Discipline: Urbanisme Aménagement

« Resolution Search » et problèmes d’optimisation discrète

Thèse réalisée en cotutelle avec l'Université d'Avignon.

Localisation et fonction de CHK2 en mitose

Les centrosomes dont le rôle principal est d’organiser le cytosquelette de microtubules et le fuseau mitotique servent aussi de sites d’interaction pour plusieurs protéines régulatrices du cycle cellulaire et de la réponse aux dommages à l’ADN. Une de ces protéines est la kinase CHK2 et plusieurs publications montrent une sous-population de CHK2 localisée aux centrosomes dans les cellules en interphase et en mitose. Toutefois, la localisation de CHK2 aux centrosomes demeure controversée, car des doutes subsistent en ce qui concerne la spécificité des anticorps utilisés en immunocytochimie. En utilisant des lignées cellulaires du cancer du côlon, les cellules HCT116 sauvages et HCT116 CHK2-/- ainsi que différentes lignées d’ostéosarcome humain dans lesquelles l’expression de CHK2 a été inhibée par ARN interférence, nous montrons que les anticorps anti-CHK2 qui donnent un signal centrosomal sont non spécifiques et reconnaissent un antigène inconnu sur les centrosomes. Cependant, par des expériences d’immunofluorescence réalisées avec des cellules U2OS qui expriment les protéines de fusion GFP-CHK2 ou FLAG-CHK2, nous révélons une localisation centrosomale de CHK2 dans les cellules en mitose, mais pas en interphase. Ce résultat a été confirmé par vidéomicroscopie dans les cellules vivantes exprimant GFP-CHK2. Pour déterminer le ou les rôles potentiels de CHK2 en mitose nous avons réalisé des expériences pour explorer le rôle de CHK2 dans la progression de la mitose, la nucléation des microtubules aux centrosomes et la progression de la mitose en présence de problèmes d’attachement des chromosomes où de lésions génotoxiques. Nos données suggèrent que CHK2 n’est pas impliquée dans la régulation de la mitose dans les cellules U2OS.

Localisation of aryl sulfotransferase expression in human tissues using hybridisation histochemistry and immunohistochemistry

To date, the laboratory has cloned seven unique human sulfotransferases; five aryl sulfotransferases (HAST1, HAST2, HAST3, HAST4 and HAST4v), an estrogen sulfotransferase and a dehydroepiandrosterone sulfotransferase. The cellular distribution of human aryl sulfotransferases in human hepatic and extrahepatic tissues has been determined using the techniques of hybridization histochemistry and immunohistochemistry. Human aryl sulfotransferase expression was detected in liver, epithelial cells of the gastrointestinal mucosal layer, epithelial cells lining bronchioles and in mammary duct epithelial cells. (C) 1998 Elsevier Science Ireland Ltd. All rights reserved.

Localisation of gelatinase activity in epidermal hoof lamellae by in situ zymography

In situ gelatin zymography is a technique, which utilises a gelatin-based emulsion overlay to detect and, more importantly, localise the gelatinase activity in underlying tissue. Gelatinase A [matrix metalloproteinase-2 (MMP-2)] and gelatinase B [matrix metalloproteinase-9 (MMP-9)] are present in equine hoof homogenates and supernatants from cultured hoof explants by SDS-PAGE gelatin zymography, and it has been assumed that the enzymes are derived solely from matrix and epithelia and not from other sources such as leucocytes. Using in situ zymography, gelatinases are shown to be localised within the equine epidermal hoof lamellae and, more specifically, are apparently produced by epidermal basal and/or parabasal cells. The pattern of expression correlates with that expected based on the progression of pathological changes observed during the onset of laminitis, thus providing further evidence that laminitis pathology probably arises as a result of inadequate local MMP regulation.

Problèmes posés par la population sporo-pollinique d'un niveau à plantes de la série de Buarcos (Portugal)

L'analyse pollinique des sédiments argileux, riches en macrorestes de végétaux, du "Belasien» (Crétacé inférieur) de Buarcos a permis reconnaître la présence d'une riche microflore. On a, nottament, reconnu la présence de: Concavisporites punctatus, Auritulinosporites complexis, Chomotriletes sp., Trilobosporites cf. bernissartensis, Apiculatisporites vulgaris, Cicatricosisporites sp. 1, Cicatricosisporites sp. 2. Cicatricosisporites sp. 3, Cicatricosisporites sp. 4, Cicatricosisporites sp. 5, Cicatricosisporites sp. 6. Costatoperforosporites fistulosus, Ceratosporites sp. l, C. cf. equalis, Ischyosporites teixeirae n. sp., Liburnisporites sp. AequitriraditeS cf. spinulosus, Cedripites lusitanicus, Clavatipollenites cf. hughesi. Après discution de la stratigraphie des diffèrentes espèces on sugère une âge barremo-aptien pour cette association malgré la présence de l'ensemble Apiculalisporites vulgaris-Classopollls major plutôt d'âge Aptien.

Design of the ISePorto robocup Middle-Size League Robotic Soccer Team: Control, Localisation and Coordination

Proceedings of the 10th Mediterranean Conference on Control and Automation - MED2002 Lisbon, Portugal, July 9-12, 2002

Control and Localisation for the ISePorto Robotic Soccer Team

International Conference on Advanced Robotics, Coimbra, Portugal, Julho 2003