Siga este link para ver outros tipos de publicações sobre o tema: Problème Linéaire en Nombres Entiers.
Teses / dissertações sobre o tema "Problème Linéaire en Nombres Entiers"
Crie uma referência precisa em APA, MLA, Chicago, Harvard, e outros estilos
Veja os 50 melhores trabalhos (teses / dissertações) para estudos sobre o assunto "Problème Linéaire en Nombres Entiers".
Ao lado de cada fonte na lista de referências, há um botão "Adicionar à bibliografia". Clique e geraremos automaticamente a citação bibliográfica do trabalho escolhido no estilo de citação de que você precisa: APA, MLA, Harvard, Chicago, Vancouver, etc.
Você também pode baixar o texto completo da publicação científica em formato .pdf e ler o resumo do trabalho online se estiver presente nos metadados.
Veja as teses / dissertações das mais diversas áreas científicas e compile uma bibliografia correta.
1
Létocart, Lucas. "Problèmes de multicoupe et de multiflot en nombres entiers". Paris, CNAM, 2002. http://www.theses.fr/2002CNAM0430.
Texto completo da fonteResumo:
L'objet de cette thèse est l'étude et la résolution de problèmes d'optimisation combinatoire dans les graphes : les problèmes de multiflot maximal en nombres entiers et de multicoupe minimale, ainsi que de plusieurs problèmes connexes : les problèmes de coupe et flot multiterminaux, de flots inséparables, de multichemins et de chemins disjoints par les arêtes. Après avoir effectué une étude bibliographique, nous montrons que les problèmes de multiflot et de multicoupe sont polynomiaux dans les arbres orientés puis nous proposons un algorithme de séparation et d 'évaluation afin de résoudre le problème NP-difficile de la multicoupe minimale dans les arbres non orientés. Nous proposons enfin des algorithmes polynomiaux pour les problèmes de coupe et de flot multiterminaux et pour le problème de la multicoupe minimale dans les anneauxThe object of this work is to study and to solve combinatorial optimization problems in graphs : maximum integral multiflow and minimum multicut problems, and some subproblems, as the multiterminal cut and flow, the unspittable flow, the multipath and the edge disjoint path problems are polynomial in directed trees and we propose a polynomial algorithm to solve both problems in rooted trees. We use linear programming and semi-definite programming in a branch and bound algorithm in order to solve the NP-hard minimum multicut problem in undirected trees. We propose also polynomial algorithms for the multiterminal cut and flow problems and for the minimum multicut problem in rings
2
Wu, Lei. "Contribution à la programmation linéaire en nombres entiers : problèmes de placement-chargement et knapsack". Amiens, 2011. http://www.theses.fr/2011AMIE0112.
Texto completo da fonteResumo:
La programmation linéaire en nombres entiers (PLNE) connait une utilisation de plus en plus importante pour la modélisation et la résolution des problèmes pratiques. Par ailleurs, à cause de certains problèmes complexes et fortement combinatoires, les méthodes de résolution issues de la PLNE peuvent perdre de leur efficacité. Dans nos travaux de recherche, nous nous intéresserons à la réduction de l’exhaustivité des procédures de la PLNE afin d’échapper à l’explosion combinatoire à laquelle nous serons confrontés. En effet, nous montrons comment la PLNE peut contribuer efficacement à la résolution de deux problèmes de l’optimisation combinatoire, NP-difficiles : le problème de placement en trois dimensions (3D-SBSBPP) et une variante de la famille des problèmes de knapsack (MMKP). Le premier problème est issu du monde industriel, en particulier de la logistique où l’on se propose, par exemple, de résoudre un problème de chargement de conteneurs (colis, palettes, etc. ) dans le processus d’une chaine logistique. Le deuxième problème intervient aujourd’hui dans diverses applications pratiques de grande importance comme l’allocation des ressources dans un réseau informatique et, dans la modélisation du problème d’adaptation dynamique des ressources d’un système multimédia pour assurer la qualité de service nécessaire pour le trafic multimédia. Une première partie est consacrée à l’étude du problème 3D-SBSBPP. Dans un premier temps, nous proposons une modélisation sous forme d’un PLNE. Ensuite, afin de déterminer un encadrement efficace des bornes inférieures (minorants), nous proposons de nouvelles contraintes valides pour le programme mathématique. Dans la continuité de ce travail, nous proposons de nouvelles heuristiques, puis une méthode augmentée qui est basée sur une technique de ré-optimisation. Finalement, en s’appuyant sur certains paramètres de pénalité sur des contraintes, d’autres méthodes hybrides sont aussi proposées. La deuxième partie de nos travaux de recherche consiste en l’étude du problème MMKP. Dans un premier temps, nous proposons un modèle équivalent pour le problème MMKP. Ce modèle est construit à partir d’une solution (admissible ou non-admissible) obtenue par une relaxation Lagrangienne. Le but du modèle proposé est double: il permet de répondre à l’existence d’une solution admissible pour le MMKP et, de le résoudre à l’optimum. Nous montrons aussi que ce modèle est de complexité théorique moins importante que celle du modèle original. Dans un deuxième temps, nous proposons une autre méthode exacte combinant le modèle équivalent et une méthode par séparation et évaluation. Finalement, nous proposons l’adaptation des deux approches résultantes afin de résoudre des instances de grande tailleThis thesis deals with Integer Linear Programming (ILP) : an effective approach for modeling and solving combinatorial optimization problems. ILP is becoming more and more important for treating practical problems in recent research. Despite the fact that the problem has often a complex and highly combinatorial structure, ILP-based resolution methods may lose their effectiveness. The main goal of our framework is to reduce the completeness of ILP-based method by exploiting the problem's particular properties. In order to show how the ILP could contribute effectively to solving combinatorial optimization problems, we consider two NP-hard problems : 3D Single Bin-Size Bin Packing Problem and Multi-dimensional Multi-choice Multiple Knapsack Problem. The first problem comes from the industrial world, particularly in logistics processes where it is proposed to solve, for example, a problem of optimal allocation of boxes with a set of available containers (parcels, pallets, etc. ) in the process of a supply chain. The second problem can be encountered in real-world applications, such as service level agreement, model of allocation resources, or as a dynamic adaptation of system of resources for multimedia multi-sessions
3
Schaal, Arnaud. "Approche hybride pour la résolution de problèmes linéaires en nombres entiers : méthodes intérieures et méta-heuristiques". Paris 9, 1997. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1997PA090036.
Texto completo da fonteResumo:
Les méthodes intérieures apparaissent depuis peu comme étant utile dans le cadre de la programmation linéaire en nombres entiers. De même, les méta-heuristiques sont apparues afin de permettre la résolution de certains problèmes en nombres entiers. Le travail poursuivi dans cette thèse consiste à présenter les différentes méthodes de programmation linéaire en nombres entiers avant de proposer de les coordonner dans une nouvelle méthode hybride destinée à résoudre des problèmes linéaires en nombres entiers de grande taille et denses. La méthode hybride proposée dans cette thèse combine une méthode intérieure irréalisable, un algorithme génétique et l'exploitation de coupes économiques. La méthode intérieure trouve rapidement des solutions à composantes réelles appelées points d'ancrage. L'algorithme génétique explore le voisinage de ces points d'ancrage afin de trouver des solutions réalisables à composantes entières satisfaisantes. Les coupes permettent de trouver de nouveaux points d'ancrage recentrés situés à l'intérieur de l'espace admissible initial. Cette approche est présentée puis expérimentée sur 50 problèmes différents allant de 50 variables 50 contraintes à 1000 variables 100 contraintes.
4
Zeghal-Mansour, Farah. "Résolution de programmes linéaires en nombres entiers de grandes tailles et application à un problème d'affectation en transport aérien". Paris 6, 2002. http://www.theses.fr/2002PA066565.
Texto completo da fonte
5
Feng, Jianguang. "Modélisation et optimisation des Hoist Scheduling Problems". Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLC043/document.
Texto completo da fonteResumo:
Dans cette thèse, nous étudions des Hoist Scheduling Problems (HSP) qui se posent fréquemment dans des lignes automatiques de traitement de surface. Dans ces lignes, des ponts roulants sont utilisés pour transporter les pièces entre les bains. Ainsi, les ponts roulants jouent un rôle essentiel dans la performance de ces lignes ; et un ordonnancement optimal de leurs mouvements est un facteur déterminant pour garantir la qualité des produits et maximiser la productivité. Les lignes que nous étudions comportent un seul pont roulant mais peuvent être des lignes de base ou des lignes étendues (où des bains sont à fonctions et/ou capacités multiples). Nous examinons trois Hoist Scheduling Problems : l’optimisation robuste d’un HSP cyclique, l’ordonnancement dynamique d’une ligne étendue de type job shop et l’ordonnancement cyclique d’une telle ligne.Pour l’optimisation robuste d’un HSP cyclique, nous définissons la robustesse comme la marge dans le temps de déplacement du pont roulant. Nous formulons le problème en programmation linéaire en nombres mixtes à deux objectifs pour optimiser simultanément le temps de cycle et la robustesse. Nous démontrons que le temps de cycle minimal augmente avec la robustesse, et que par conséquent la frontière Pareto est constituée d’une infinité de solutions. Les valeurs minimales et maximales des deux objectifs sont établies. Les résultats expérimentaux à partir de benchmarks et d’instances générées aléatoirement montrent l’efficacité de l’approche proposée.Nous étudions ensuite un problème d’ordonnancement dynamique dans une ligne étendue de type job shop. Nous mettons en évidence une erreur de formulation dans une un modèle existant pour un problème similaire mais sans bains multi-fonctions. Cette erreur peut rendre l’ordonnancement obtenu sous-optimal voire irréalisable. Nous construisons un nouveau modèle qui corrige cette erreur. De plus il est plus compact et s’applique au cas avec des bains à la fois à capacités et à fonctions multiples. Les résultats expérimentaux menés sur des instances avec ou sans bains multi-fonctions montrent que le modèle proposé conduit toujours à une solution optimale et plus efficace que le modèle existant.Nous nous focalisons enfin sur l’ordonnancement cyclique d’une ligne étendue de type job shop avec des bains à fonctions et capacités multiples. Nous construisons un modèle mathématique en formulant les contraintes de capacité du pont roulant, les intervalles des durées opératoires, et les contraintes de capacité des bains. Nous établissons également des contraintes valides. Les expériences réalisées sur des instances générées aléatoirement montrent l’efficacité du modèle proposéThis thesis studies hoist scheduling problems (HSPs) arising in automated electroplating lines. In such lines, hoists are often used for material handing between tanks. These hoists play a crucial role in the performance of the lines and an optimal schedule of the hoist operations is a key factor in guaranteeing product quality and maximizing productivity. We focus on extended lines (i.e. with multi-function and/or multi-capacity tanks) with a single hoist. This research investigates three hoist scheduling problems: robust optimization for cyclic HSP, dynamic jobshop HSP in extended lines and cyclic jobshop HSP in extended lines.We first study the robust optimization for a cyclic HSP. The robustness of a cyclic hoist schedule is defined in terms of the free slacks in hoist traveling times. A bi-objective mixed-integer linear programming (MILP) model is developed to optimize the cycle time and the robustness simultaneously. It is proved that the optimal cycle time strictly increases with the robustness, thus there is an infinite number of Pareto optimal solutions. We established lower and upper bounds of these two objectives. Computational results on several benchmark instances and randomly generated instances indicate that the proposed approach can effectively solve the problem.We then examine a dynamic jobshop HSP with multifunction and multi-capacity tanks. We demonstrate that an existing model for a similar problem can lead to suboptimality. To deal with this issue, a new MILP model is developed to generate an optimal reschedule. It can handle the case where a multi-function tank is also multi-capacity. Computational results on instances with and without multifunction tanks indicate that the proposed model always yields optimal solutions, and is more compact and effective than the existing one.Finally, we investigate a cyclic jobshop HSP with multifunction and multi-capacity tanks. An MILP model is developed for the problem. The key issue is to formulate the time-window constraints and the tank capacity constraints. We adapt the formulation of time-window constraints for a simpler cyclic HSP to the jobshop case. The tank capacity constraints are handled by dealing with the relationships between hoist moves so that there is always an empty processing slot for new parts. Computational experiments on numerical examples and randomly generated instances indicate that the proposed model can effectively solve the problem
6
Nait-Abdallah, Rabie. "Modèles de dimensionnement et de planification dans un centre d'appels". Phd thesis, Ecole Centrale Paris, 2008. http://tel.archives-ouvertes.fr/tel-00275832.
Texto completo da fonteResumo:
Cette thèse aborde la gestion des ressources humaines dans un centre d'appels. Plus spécifiquement, nous nous intéressons aux problèmes de dimensionnement et de planification. L'objectif sous-jacent est d'assurer la meilleure qualité de service au client (par exemple minimiser le délai d'attente) avec un coût salarial minimum pour l'entreprise. Ces problématiques sont généralement modélisées dans la littérature par le problème de construction de vacation (shift-scheduling problem). Pour appréhender ce problème, nous introduisons le paradigme de chaîne d'activités. Ce paradigme nous permet de représenter la grande diversité des environnements et des contraintes de gestion des ressources humaines dans un centre d'appels. Nous traduisons ensuite ce paradigme en programme linéaire en nombres entiers pour résoudre les problèmes de dimensionnement et de planification. Nous proposons enfin une méthode pour intégrer au programme linéaire en nombres entiers un objectif de qualité de service non linéaire.
7
Kone, Oumar. "Nouvelles approches pour la résolution du problème d'ordonnancement de projet à moyens limités". Phd thesis, Université Paul Sabatier - Toulouse III, 2009. http://tel.archives-ouvertes.fr/tel-00446704.
Texto completo da fonteResumo:
Dans ce travail de thèse, nous avons étudié deux types de problèmes d'ordonnancement. La majeure partie concerne le problème d'ordonnancement de projet à moyens limités (RCPSP). Le problème d'ordonnancement des opérations de manutention dans un entrepôt de transbordement ("crossdocking") est également traité avec une moindre importance. Dans une première partie (la plus étendue), nous abordons le RCPSP. À partir de modélisations utilisant la programmation linéaire en nombres entiers, nous avons proposé deux nouvelles formulations de ce problème, utilisant des variables indicées par des événements. Dans l'une d'entre elles, on utilise une variable binaire pour marquer le début de l'exécution de chaque activité et une autre variable pour marquer sa fin. Dans la seconde proposition, une seule variable est utilisée. Elle identifie les événements après lesquels l'activité reste en cours ou débute son exécution. De façon générale, comparées à d'autres modèles de la littérature sur divers types d'instances, nos propositions affichent des résultats plus intéressants sur les instances contenant des activités aux durées disparates et associées à de longs horizons d'ordonnancement. En particulier, sur ces mêmes types d'instances mais hautement cumulatives (caractéristiques de base du RCPSP), elles sont également les plus performantes. Nous avons également abordé la résolution d'une extension du RCPSP consistant à prendre en compte des ressources particulières, qui peuvent être consommées en début d'exécution de chaque activité, mais aussi produites à leur fin : il s'agit du RCPSP avec consommation et production de ressources. Afin d'effectuer une comparaison expérimentale entre différents modèles, nous avons proposé une adaptation de nos formulations basées événements, des formulations à temps discret de Pritsker et de Christofides, et de la formulation à temps continu basée sur les flots (proposé par Artigues sur la base des travaux de Balas). Globalement, les résultats mon trent que nos formulations basées événements obtiennent les meilleurs résultats sur bon nombre de types d'instances. Dans la seconde partie (plus réduite), nous avons également proposé un branch-and-bound utilisant des coupes basées sur la frontière de Pareto, pour la résolution du problème d'ordonnancement des opérations de manutention au sein d'un entrepôt de transbordement ("crossdocking"). Les excellents résultats obtenus ont renforcé nos interrogations sur la complexité non-prouvée de ce problème, et ont permis d'établir par la suite que le problème est de complexité polynomiale.
8
Farah, Ihsen. "Optimisation des flux de trafic aérien". Le Havre, 2013. http://www.theses.fr/2013LEHA0003.
Texto completo da fonteResumo:
Dans cette thèse, nous traitons le problème de gestion des flux de trafic aérien. Nous présentons un nouveau programme linéaire en nombres entiers qui prend en compte toutes les phases d'un vol. Il prend en compte également le réacheminement des vols. Nous proposons également un algorithme de fourmi «Max-Min». Pour montrer l'efficacité de notre nouvelle formulation et de notre approche, des simulations numériques appliquées à des données réelles sont présentées. Nous traitons également le problème datterrissage d'avions dans le cas statique. Nous proposons une formulation quadratique et nous proposons un changement de variables pour linéariser le modèle. Le deuxième objectif de ce travail est de résoudre effectivement ce modèle. Pour cela, nous proposons une méthode exacte basée sur l'algorithme de séparation et évaluation et un algorithme de colonies de fourmis pour résoudre les instances de grandes tailles. Pour confirmer ce travail, des simulations numériques pour la métaheuristique et la méthode exacte sont présentéesIn this thesis, we adress the Air Traffic Flow Management Problem (TFMP). We present a new Integer Linear Program which takes into account all phases of flight. We purpose also a Max-Min ant system algorithm to resolve the TFMP. Numerical simulations are applied to real data to show the effectiveness of our new formulation and our approach. We adress also the static Aircraft Landing Problem (ALP). We propose a quadratic integer program and propose a change of variables to linearize the model. Second objective is to resolve effectivly this model. Therefore, an exact method based on Branch and Bound algorithm is presented. We propose also an Ant Colony System to resolve the instances with a big size. To confirm this work, simulation and computer modeling results for both of the heuristic and exact algorithm are presented
9
Ternier, Ian-Christopher. "Résolution exacte du Problème de Coloration de Graphe et ses variantes". Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED060/document.
Texto completo da fonteResumo:
Dans un graphe non orienté, le Problème de Coloration de Graphe (PCG) consiste à assigner à chaque sommet du graphe une couleur de telle sorte qu'aucune paire de sommets adjacents n'aient la même couleur et le nombre total de couleurs est minimisé. DSATUR est un algorithme exact efficace pour résoudre le PCG. Un de ses défauts est qu'une borne inférieure est calculée une seule fois au noeud racine de l'algorithme de branchement, et n'est jamais mise à jour. Notre nouvelle version de DSATUR surpasse l'état de l'art pour un ensemble d'instances aléatoires à haute densité, augmentant significativement la taille des instances résolues. Nous étudions trois formulations PLNE pour le Problème de la Somme Chromatique Minimale (PSCM). Chaque couleur est représentée par un entier naturel. Le PSCM cherche à minimiser la somme des cardinalités des sous-ensembles des sommets recevant la même couleur, pondérés par l'entier correspondant à la couleur, de telle sorte que toute paire de sommets adjacents reçoive des couleurs différentes. Nous nous concentrons sur l'étude d'une formulation étendue et proposons un algorithme de Branch-and-PriceGiven an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph such that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR is an effective exact algorithm for the VCP. We introduce new lower bounding techniques enabling the computing of a lower bound at each node of the branching scheme. Our new DSATUR outperforms the state of the art for random VCP instances with high density, significantly increasing the size of solvable instances. Similar results can be achieved for a subset of high density DIMACS instances. We study three ILP formulations for the Minimum Sum Coloring Problem (MSCP). The problem is an extension of the classical Vertex Coloring Problem in which each color is represented by a positive natural number. The MSCP asks to minimize the sum of the cardinality of subsets of vertices receiving the same color, weighted by the index of the color, while ensuring that vertices linked by an edge receive different colors. We focus on studying an extended formulation and devise a complete Branch-and-Price algorithm
10
Ouzia, Hacène. "Hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1 : théorie et applications". Paris 6, 2008. http://www.theses.fr/2008PA066349.
Texto completo da fonteResumo:
Dans cette thèse, nous abordons les liens entre diverses hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1. Parmi celles-ci, citons la hiérarchie de Sherali-Adams (S&A) et la hiérarchie Lift-and-Project (L&P). Tout d’abord, nous montrons que la hiérarchie L&P est semi-algébrique. Puis, nous introduisons une nouvelle hiérarchie de relaxations semi-algébriques, dite SRL*, intermédiaire entre les hiérarchies S&A et L&P. Nous examinons les liens entre les hiérarchies L&P et SRL*. Nous aborderons comment renforcer la description linéaire d’une relaxation L&P pour qu’elle coïncide avec celle d’une relaxation SRL*. Nous montrons aussi que toute relaxation S&A s’obtient en renforçant une relaxation SRL* par des contraintes dites « conditions de symétries ». Nous étayons notre analyse par des résultats de calculs préliminaires comparant le renforcement des relaxations L&P, S&A et SRL* de rang 2. Ensuite, nous caractérisons les programmes linéaires mixtes 0-1 pour lesquels les hiérarchies S&A et SRL* coïncident. Comme application, nous prouverons que les hiérarchies SRL* et S&A coïncident pour l'optimisation d'une fonction pseudo booléenne sur un polyèdre quelconque. Pour illustrer cette propriété nous présentons des résultats de calculs préliminaires sur des instances MINCUT avec contraintes de cardinalité. Enfin, nous présentons des expériences de calcul concernant les renforcements procurés par des relaxations L&P de rang 2 et 3 sur des instances Max-2SAT et Max-3SAT. Nous explorons également, la possibilité d’utiliser des relaxations L&P partielles.
11
Ben, Moallem Marwa. "Seafaring staff scheduling problem with workload fairness and incompatibility : modeling and resolution". Electronic Thesis or Diss., Strasbourg, 2024. http://www.theses.fr/2024STRAD034.
Texto completo da fonteResumo:
Les défis liés à la planification du personnel ont été largement étudiés dans les secteurs du transport, comme les compagnies aériennes, les chemins de fer et les bus urbains, mais leur application dans le transport maritime reste relativement limitée. Ce travail traite d'un problème de planification du personnel navigant, inspiré d'une étude de cas réelle, dans laquelle un armateur exploite plusieurs catégories de navires nécessitant des compétences spécifiques. L'objectif est d'assurer une répartition équitable de la charge de travail, de minimiser l'incompatibilité entre les travailleurs, tout en respectant les exigences telles que la qualification, les jours et les intervalles de repos requis entre les quarts. L'originalité de ce travail réside dans l'intégration de ces objectifs multiples et contraintes dans une formulation de Problème Linéaire en Nombres Entiers (PLNE), accompagnée de résultats expérimentaux qui évaluent les performances du modèle sous différents paramètres. Cette recherche démontre que le problème est NP-difficile, justifiant ainsi l'utilisation de méthodes heuristiques. La méthode heuristique, testée de manière approfondie par rapport à la méthode exacte, s'est révélée efficace pour gérer l’affectation tout en respectant les contraintes définies. Le processus de benchmarking a montré que l'heuristique fournit des solutions proches de l'optimum tout en réduisant considérablement les temps de calcul, offrant ainsi un outil pratique d'aide à la décision pour l’affectation complexe du personnelStaff scheduling challenges have been extensively studied in transportation sectors like airlines, railways, and urban buses, yet their application in sea transport remains notably underexplored. This work addresses a seafaring staff scheduling problem inspired by a real case study, where a shipowner operates multiple vessel categories requiring specific skills. The objective is to achieve a fair workload distribution, minimize worker incompatibility, and comply with legal requirements such as mandatory rest periods and shift intervals. The novelty of this work lies in the integration of these multiple objectives and constraints into a Mixed Integer Linear Programming (MILP) model, supported by experimental results that assess the model’s performance under varying parameters. This research demonstrates that the problem is NP-hard, justifying the use of heuristic methods. The heuristic approach, rigorously tested against exact methods, is shown to effectively manage scheduling while adhering to the problem's constraints. Benchmarking results reveal that the heuristic yields near-optimal solutions with significantly reduced computation times, offering a practical decision-support tool for complex maritime staff scheduling
12
Benhida, Soufia. "De l'optimisation pour l'aide à la décision : applications au problème du voyageur de commerce probabiliste et à l'approximation de données". Thesis, Normandie, 2018. http://www.theses.fr/2018NORMIR27.
Texto completo da fonteResumo:
La 1ere partie de ce travail traite l'optimisation des tournées sous forme d'un problème d'optimisation nommé Le problème de Voyageur de Commerce. Dans cette partie nous nous intéressons à faire une riche présentation du problème de Voyageur de Commerce, ses variantes, puis nous proposons une stratégie de génération de contrainte pour la résolution du TSP. Ensuite on traite sa version stochastique : le problème de Voyageur de commerce Probabiliste. Nous proposons une formulation mathématique du PTSP et nous présentons des résultats numériques obtenus par résolution exacte pour une série d'instances de petite taille. Dans la seconde partie, nous proposons une méthode d'approximation générale permettant d'approcher différents type de données, d'abord nous traitons l'approximation d'un signal de vent (cas simple, ID), ensuite l'approximation d'un champ de vecteurs avec prise en compte de la topographie qui constitue la principale contribution de cette partieThe first part of this work deals with route optimization in the form of an optimization problem named The Traveler's Business Problem. In this part we are interested to make a rich presentation of the problem of Traveler Commerce, its variants, then we propose a strategy of constraint generation for the resolution of the TSP. Then we treat its stochastic version : the probabilistic business traveler problem. We propose a mathematical formulation of the PTSP and we present numerical results obtained by exact resolution for a series of small instances. In the second part, we propose a method of general approximation to approximate different type of data, first we treat the approximation of a wind signal (simple case, 1D), then the approximation of a vector field taking into account the topography which is the main contribution of this part
13
Gicquel, Céline. "MIP models and exact methods for the Discrete Lot-sizing and Scheduling Problem with sequence-dependent changeover costs and times". Phd thesis, Ecole Centrale Paris, 2008. http://tel.archives-ouvertes.fr/tel-00375964.
Texto completo da fonteResumo:
Le dimensionnement des lots de production est une des nombreuses activités survenant dans le cadre de la planification de production. Il a pour objet de déterminer quand et combien produire de façon à réaliser le meilleur compromis possible entre la minimisation des coûts liés à la production (coûts fixes de reconfiguration de la ressource, coûts de stockage...) et la satisfaction de la demande des clients Nous nous intéressons ici un problème de planification de production par lots connu sous le nom de "Discrete Lot-sizing and Scheduling Problem" ou "DLSP". Plus précisément, nous étudions plusieurs variantes de ce problème dans lesquelles les coûts et/ou les temps de changement de produits sur la ressource sont dépendant de la séquence et nous proposons diverses extensions d'une méthode disponible dans la littérature pour la résolution exacte du problème mono-niveau, mono-ressource. Nos contributions portent à la fois sur la modélisation du problème et sur l'implémentation de méthodes efficaces de résolution. En ce qui concerne la modélisation, nous étudions l'intégration de divers aspects opérationnels dans le modèle de base afin d'en améliorer la pertinence industrielle. Ainsi nous considérons les extensions suivantes : la prise en compte d'une structure de produits "multi-attributs" qui permet de diminuer la taille du problème d'optimisation à résoudre, l'intégration de temps de changement positifs afin de mieux modéliser la perte de production causée par une reconfiguration de la ressource et la présence de plusieurs ressources parallèles dont la production doit être planifiée simultanément. En ce qui concerne la résolution du problème, nous présentons pour chacune des extensions du modèle de base une approche de résolution visant à fournir des solutions optimales exactes. En général, les résultats de nos expériences numériques montrent l'utilité pratique de ces algorithmes pour la résolution d'instances de moyenne et grande taille en des temps de calcul compatibles avec une application industrielle
14
Koné, Oumar. "Nouvelles approches pour la résolution du problème d'ordonnancement de projet à moyens limités". Toulouse 3, 2009. http://thesesups.ups-tlse.fr/681/.
Texto completo da fonteResumo:
Dans ce travail de thèse, nous avons étudié deux types de problèmes d'ordonnancement. La majeure partie concerne le problème d'ordonnancement de projet à moyens limités (RCPSP). Le problème d'ordonnancement des opérations de manutention dans un entrepôt de transbordement ("crossdocking") est également traité avec une moindre importance. Dans une première partie (la plus étendue), nous abordons le RCPSP. À partir de modélisations utilisant la programmation linéaire en nombres entiers, nous avons proposé deux nouvelles formulations de ce problème, utilisant des variables indicées par des événements. Dans l'une d'entre elles, on utilise une variable binaire pour marquer le début de l'exécution de chaque activité et une autre variable pour marquer sa fin. Dans la seconde proposition, une seule variable est utilisée. Elle identifie les événements après lesquels l'activité reste en cours ou débute son exécution. De façon générale, comparées à d'autres modèles de la littérature sur divers types d'instances, nos propositions affichent des résultats plus intéressants sur les instances contenant des activités aux durées disparates et associées à de longs horizons d'ordonnancement. En particulier, sur ces mêmes types d'instances mais hautement cumulatives (caractéristiques de base du RCPSP), elles sont également les plus performantes. Nous avons également abordé la résolution d'une extension du RCPSP consistant à prendre en compte des ressources particulières, qui peuvent être consommées en début d'exécution de chaque activité, mais aussi produites à leur fin : il s'agit du RCPSP avec consommation et production de ressources. Afin d'effectuer une comparaison expérimentale entre différents modèles, nous avons proposé une adaptation de nos formulations basées événements, des formulations à temps discret de Pritsker et de Christofides, et de la formulation à temps continu basée sur les flots (proposé par Artigues sur la base des travaux de Balas). Globalement, les résultats montrent que nos formulations basées événements obtiennent les meilleurs résultats sur bon nombre de types d'instances. .In this thesis, we studied two types of scheduling problems. The major part concerns the Resource-Constrained Project Scheduling Problem (RCPSP). The scheduling problem of handling operations in a warehouse of Crossdocking is also dealt. First, from models using mixed integer linear programming, we proposed two new formulations of this problem, using variables indexed by events. In one of them, we use a binary variable to mark the beginning of the performing of each activity and another variable to mark its end. In the second proposal, a single variable is used. It identifies events in which the activity starts or continues its performing. Overall, compared to other models in the literature on various types of instances, our proposals show more interesting results on the instances with long scheduling horizons containing activities with disparate durations. In particular, on the highly cumulative instances (basic characteristics of RCPSP) of these types of instances, they are the most efficient. We also treat the resolution of the extension of the RCPSP which consists in taking into account specific resources that can be consumed during the performing of each activity, but also produced in another quantity at the end of performing of each activity: it is the RCPSP with consumption and production of resources. To make a comparison between different experimental models, we proposed an adaptation of our event-based formulations, the discrete-time formulations of Pritsker and Christofides, and the flow-based continuous-time formulation (proposed by Artigues on basis of the work of Balas). Overall, the results show that our event-based formulations are most successful on many types of instances. Second, in one less extensive part, we proposed a branch-and-bound using some cuts based on the Pareto frontier for the resolution of the scheduling problem of handling operations in a warehouse of Crossdocking. The excellent results obtained, which had strengthened our questions about the non-proved complexity of this problem, have contributed to establish later that this problem is of polynomial complexity
15
Sarpong, Boadu Mensah. "Column generation for bi-objective integer linear programs : application to bi-objective vehicle routing problems". Phd thesis, INSA de Toulouse, 2013. http://tel.archives-ouvertes.fr/tel-00919861.
Texto completo da fonteResumo:
L'optimisation multi-objectif concerne la résolution de problèmes pour lesquels plusieurs objectifs (ou critères) contradictoires sont pris en compte. Contrairement aux problèmes d'optimisation ayant un seul objectif, un problème multi-objectif ne possède pas une valeur optimale unique mais plutôt un ensemble de points appelés "ensemble non dominé". Les bornes inférieures et supérieures d'un problème multi-objectif peuvent être également décrites par des ensembles. Dans la pratique, les variables utilisées en optimisation multiobjectif représentent souvent des objets non fractionnables et on parle alors de problèmes multi-objectif en nombres entiers. Afin d'obtenir de meilleures bornes qui peuvent être utilisées dans la conception de méthodes exactes, certains problèmes sont formulés avec un nombre exponentiel de variables de décision et ces problèmes sont résolus par la méthode de génération de colonnes. Les travaux de cette thèse visent à contribuer à l'étude de l'utilisation de la génération de colonnes en programmation linéaires en nombres entiers multi-objectif. Pour cela nous étudions un problème de tournées de véhicules bi-objectif qui peut être considéré comme une généralisation de plusieurs autres problèmes de tournées de véhicules. Nous proposons des formulations mathématiques pour ce problème et des techniques pour accélérer le calcul des bornes inférieures par génération de colonnes. Les sous-problèmes qui doivent être résolus pour le calcul des bornes inférieures ont une structure similaire. Nous exploitons cette caractéristique pour traiter simultanément certains sous-problèmes plutôt qu'indépendamment.
16
Arenas, Pimentel Luis Diego. "Contributions d'un modèle microscopique à la résolution du problème de construction d'une grille horaire et à la planification des activités de maintenance de l'infrastructure ferroviaire". Thesis, Valenciennes, 2016. http://www.theses.fr/2016VALE0034/document.
Texto completo da fonteResumo:
La plupart des systèmes ferroviaires subissent une demande croissante de capacité. Pour y faire face, il faut construire de nouvelles infrastructures ou exploiter plus efficacement celles existantes, notamment en définissant des grilles horaires optimisées. Dans la littérature, la plupart des approches de construction des grilles sont basées sur des représentations macroscopiques de l'infrastructure, ce qui peut conduireà des solutions infaisables ou inefficaces. En revanche, les approches microscopiques reposent sur une modélisation réaliste du système ferroviaire, ce qui garantit la faisabilité et l'efficacité des résultats. Néanmoins, en raison de leur complexité, l'utilisation de ces approches est généralement limitée à une seule gare. Malgré l'optimisation de la grille horaire, les travaux de maintenance peuvent avoir un fort impact sur les circulations des trains. En présence de maintenances, il peut donc être nécessaire de redéfinir la grille horaire pour assurer une exploitation efficace de la capacité. Nous présentons deux contributions principales sous forme de deux approches microscopiques : une pour la conception de grilles horaires et l'autre pour leur redéfinition en cas de maintenance. La deuxième est la première approche microscopique qui apparaît dans la littérature pour aborder ce problème tout en considérant des aspects comme les limitations temporaires de vitesse. Nous démontrons la validité de nos approches et leur applicabilité dans des scénarios réels. De plus, nous montrons que les approches microscopiques peuvent être utilisées pour traiter des zones de l'infrastructure contenant plusieurs garesMost railway systems experience a growing demand of railway capacity. To face this demand, either new infrastructure must be built or a more efficient exploitation of the existing one must be attained. Timetables play a determinant role in the efficient capacity exploitation. Most timetabling approaches in the literature are based on macroscopic representations of the infrastructure. This may lead to inefficient and in some cases, impractical solutions. Instead, microscopic approaches are based on more realistic modelling of the elements of the railway system. This guarantees the feasibility of the timetables while promoting an efficient capacity exploitation. However, due to their complexity, the scope of microscopic approaches is typically restricted to main stations. Despite the optimization of timetables, the performance of infrastructure maintenance may severely impact the trains' circulations in the network. Therefore, the timetable may have to be rearranged to ensure an efficient capacity exploitation. We present two main contributions in this thesis: first, a microscopic approach for timetable design. Second, a microscopic approach for timetable rearrangement to cope with maintenance. This is the first microscopic approach in the literature to tackle this problem while also considering specific aspects as temporary speed limitations. After a thorough experimental analysis, we demonstrate the validity of our approaches and their practical applicability in real life scenarios. In particular, we show that microscopic approaches can be used to tackle large areas of the infrastructure, including several stations
17
Mencarelli, Luca. "The Multiplicative Weights Update Algorithm for Mixed Integer NonLinear Programming : Theory, Applications, and Limitations". Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLX099/document.
Texto completo da fonteResumo:
L'objectif de cette thèse consiste à présenter un nouvel algorithme pour la programmation non linéaire en nombres entiers, inspirée par la méthode Multiplicative Weights Update et qui compte sur une nouvelle classe de reformulations, appelées les reformulations ponctuelles.La programmation non linéaire en nombres entiers est un sujet très difficile et fascinant dans le domaine de l'optimisation mathématique à la fois d'un point de vue théorique et computationnel. Il est possible de formuler de nombreux problèmes dans ce schéma général et, habituellement, ils posent de réels défis en termes d'efficacité et de précision de la solution obtenue quant aux procédures de résolution.La thèse est divisée en trois parties principales : une introduction composée par le Chapitre 1, une définition théorique du nouvel algorithme dans le Chapitre 2 et l'application de cette nouvelle méthodologie à deux problèmes concrets d'optimisation, tels que la sélection optimale du portefeuille avec le critère moyenne-variance dans le Chapitre 3 et le problème du sac à dos non linéaire dans le Chapitre 4. Conclusions et questions ouvertes sont présentées dans le Chapitre 5This thesis presents a new algorithm for Mixed Integer NonLinear Programming, inspired by the Multiplicative Weights Update framework and relying on a new class of reformulations, called the pointwise reformulations.Mixed Integer NonLinear Programming is a hard and fascinating topic in Mathematical Optimization both from a theoretical and a computational viewpoint. Many real-word problems can be cast this general scheme and, usually, are quite challenging in terms of efficiency and solution accuracy with respect to the solving procedures.The thesis is divided in three main parts: a foreword consisting in Chapter 1, a theoretical foundation of the new algorithm in Chapter 2, and the application of this new methodology to two real-world optimization problems, namely the Mean-Variance Portfolio Selection in Chapter 3, and the Multiple NonLinear Separable Knapsack Problem in Chapter 4. Conclusions and open questions are drawn in Chapter 5
18
Glize, Estele. "Méthodes exactes pour les problèmes combinatoires bi-objectif : Application sur les problèmes de tournées de véhicules". Thesis, Toulouse, INSA, 2019. http://www.theses.fr/2019ISAT0023.
Texto completo da fonteResumo:
De nombreux problèmes réels comportent plusieurs critères à considérer simultanément. À titre d’exemple, un trajet peut se caractériser par son coût, son impact écologique, son temps de parcours ou encore sa longueur. Les problèmes mathématiques résultants relèvent de l’optimisation multi-objectif. En général, il n’existe pas de solution réalisable optimisant tous les objectifs. Ainsi, les décideurs veulent analyser le compromis entre tous les objectifs pour pouvoir choisir la solution la plus adéquate. Par conséquent, résoudre un problème multi-objectif consiste à trouver un sous-ensemble de points, dits non dominés, dans l’espace des objectifs. Ces points sont associés à des solutions réalisables pour lesquelles il n’est pas possible d’améliorer un objectif sans en détériorer un autre. Peu de méthodes exactes existent dans la littérature pour traiter les problèmes combinatoires multi-objectif NP-difficiles, en particulier ceux dont la variante mono-objectif est déjà NP-difficile. Cette thèse s’inscrit dans l’étude des méthodes exactes pour de tels problèmes multi-objectif et utilise la classe des problèmes de tournées de véhicules bi-objectif comme référence. Les travaux se concentrent sur une approche basée sur la génération de colonnes et qui vise à énumérer efficacement l’ensemble des points non dominés de ces problèmes. Nous proposons notamment d’analyser diverses techniques d’exploration de l’espace des objectifs et de les améliorer grâce à des propriétés structurelles. Afin d’en démontrer la généricité, l’approche est appliquée à plusieurs variantes bi-objectif des problèmes de tournées de véhicules : le problème de tournées de véhicules avec fenêtre de temps, le problème de tournées couvrantes et le problème de course d’orientation par équipes avec fenêtre de temps. Les multiples tests numériques soulignent l’efficacité de la méthode proposéeReal-world problems involve several different criteria to take into account. For instance, a route may be associated with multiple features such as its cost, its ecological footprint, its duration, or its length. Resulting mathematical problems are addressed by multi-objective optimization. In general, there is no feasible solution able to maximize or minimize all objectives. Thus, decision makers want to examine the trade-off between the objectives in order to select the most suitable solution for them. Solving a multi-objective optimization problem consists of finding a set of points in the objective space, called non dominated points. No point in the objective space is better than a point of this set for all objectives. Few exact methods exist in literature to solve NP-hard multi- objective combinatorial problems, especially those with a NP-hard mono-objective variant. This thesis works on exact methods for such multi-objective problems, and the class of bi-objective vehicle routing problems is used as reference. The manuscript presents a column generation based-approach which aims to efficiently enumerate the set of non dominated points of the problems. We seek the best way to explore the objective space, and we propose different acceleration techniques based on structural properties. To show its generic aspect, the approach is applied to several bi-objective variants of the vehicle routing problem : the vehicle routing problem with time windows, the covering tour problem and the team-orienteering problem with time windows. Extensive computational experiments highlight the efficiency of the proposed method
19
Loiseau, Irène. "Sur la génération de colonnes en nombres entiers". Paris 13, 2005. http://www.theses.fr/2005PA132018.
Texto completo da fonteResumo:
Dans les deux premières parties de ce travail nous présentons des méthodes exactes pour la résolution des problèmes de programmation linéaire en nombres entiers avec un très grand nombre de variables. Ces méthodes sont appelées dans la littérature méthodes de "branch-and-price". Pour les cas où les contraintes de problèmes ont tous leurs coefficients égaux à 0ou 1 (colonnes à composantes 0 ou 1), nous développons des coupes géométriques pour l'élimination des colonnes préalablement générées. Ce schéma peut être appliqué à des problèmes sans structure spécifique. Nous faisons aussi unze comparaison entre les relaxations linéaires des différentes formations de problèmes de programmation linéaire en nombre entiers. Nous discutons des difficultés pour choisir les règles de séparation (ie. De branchement dans l'arbre de recherche) à l'intérieur des algorithmes de génération de colonnes. Dans le dernier chapître on fait une synthèse de quelques problèmes de dimensionnement de réseaux de télécommunications composés d'anneaux ainsi que des problèmes de graphes induits. Nous présentons un algorithme de génération de colonnes appliqué à ce type de problème et des résultats expérimentaux sur des instances de petites et moyennes tailles.
20
Mkadem, Mohamed Amine. "Flow-shop with time delays, linear modeling and exact solution approaches". Thesis, Compiègne, 2017. http://www.theses.fr/2017COMP2390/document.
Texto completo da fonteResumo:
Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l’objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à la modélisation de ce problème. Nous avons proposé plusieurs programmes linéaires en nombres entiers. En particulier, nous avons introduit une formulation linéaire basée sur une généralisation non triviale du modèle d’affectation pour le cas où les durées des opérations sur une même machine sont identiques. Dans un deuxième temps, nous avons élargi la portée de ces formulations mathématiques pour développer plusieurs bornes inférieures et un algorithme exact basé sur la méthode de coupe et branchement (Branch-and-Cut). En effet, un ensemble d’inégalités valides a été considéré afin d’améliorer la relaxation linéaire de ces programmes et d’accélérer leur convergence. Ces inégalités sont basées sur la proposition de nouvelles règles de dominance et l’identification de sous-instances faciles à résoudre. L’identification de ces sous-instances revient à déterminer les cliques maximales dans un graphe d’intervalles. En plus des inégalités valides, la méthode exacte proposée inclut la considération d’une méthode heuristique et d’une procédure visant à élaguer les nœuds. Enfin, nous avons proposé un algorithme par séparation et évaluation (Branch-and-Bound) pour lequel, nous avons introduit des règles de dominance et une méthode heuristique basée sur la recherche locale. Nos expérimentations montrent l’efficacité de nos approches qui dominent celles de la littérature. Ces expérimentations ont été conduites sur plusieurs classes d’instances qui incluent celles de la littérature, ainsi que des nouvelles classes d’instances où les algorithmes de la littérature se sont montrés peu efficacesIn this thesis, we study the two-machine flow-shop problem with time delays in order to minimize the makespan. First, we propose a set of Mixed Integer Programming (MIP) formulations for the problem. In particular, we introduce a new compact mathematical formulation for the case where operations are identical per machine. The proposed mathematical formulations are then used to develop lower bounds and a branch-and-cut method. A set of valid inequalities is proposed in order to improve the linear relaxation of the MIPs. These inequalities are based on proposing new dominance rules and computing optimal solutions of polynomial-time-solvable sub-instances. These sub-instances are extracted by computing all maximal cliques on a particular Interval graph. In addition to the valid inequalities, the branch-and-cut method includes the consideration of a heuristic method and a node pruning procedure. Finally, we propose a branch-and-bound method. For which, we introduce a local search-based heuristic and dominance rules. Experiments were conducted on a variety of classes of instances including both literature and new proposed ones. These experiments show the efficiency of our approaches that outperform the leading methods published in the research literature
21
Ayala, Perez Maria. "Programmation linéaire en nombres entiers pour l'ordonnancement cyclique sous contraintes de ressources". Phd thesis, Université Paul Sabatier - Toulouse III, 2011. http://tel.archives-ouvertes.fr/tel-00604537.
Texto completo da fonteResumo:
Un problème d'ordonnancement cyclique consiste à ordonner dans le temps l'exécution répétitive d'un ensemble d'opérations liées par des contraintes de précédence, en utilisant un nombre limité de ressources. Ces problèmes ont des applications immédiates dans les systèmes de production ou en informatique parallèle. Particulièrement, ils permettent de modéliser l'ensemble des contraintes de précédence et de ressource à prendre en compte pour l'ordonnancement d'instructions dans les processeurs de type VLIW (Very Long Instruction Word). Dans ce cas, une opération représente une instance d'une instruction dans un programme. L'ordonnancement d'instructions de boucles internes est connu sous le nom de pipeline logiciel. Le pipeline logiciel désigne une méthode efficace pour l'optimisation de boucles qui permet la réalisation en parallèle des opérations des différentes itérations de la boucle. Dans cette thèse, nous nous intéressons principalement au problème d'ordonnancement périodique qui est un cas particulier de l'ordonnancement cyclique et qui est également la base du pipeline logiciel. Le terme ordonnancement modulo désigne un ordonnancement périodique tel que l'allocation de ressources pour une opération donnée n'est pas modifiée d'une itération sur l'autre. Pour résoudre le problème, nous nous intéressons aux formulations de programmation linéaire en nombres entiers, et notamment à la résolution du problème par des techniques de séparation, évaluation, génération de colonnes, relaxation lagrangienne et des méthodes hybrides. En particulier, nous proposons des nouvelles formulations basées sur des variables binaires représentant l'exécution d'ensembles d'instructions en parallèle. Enfin, les méthodes développées ont été validées sur des jeux d'instances industrielles pour des processeurs de type VLIW. Un problème d'ordonnancement cyclique consiste à ordonner dans le temps l'exécution répétitive d'un ensemble d'opérations liées par des contraintes de précédence, en utilisant un nombre limité de ressources. Ces problèmes ont des applications immédiates dans les systèmes de production ou en informatique parallèle. Particulièrement, ils permettent de modéliser l'ensemble des contraintes de précédence et de ressource à prendre en compte pour l'ordonnancement d'instructions dans les processeurs de type VLIW (Very Long Instruction Word). Dans ce cas, une opération représente une instance d'une instruction dans un programme. L'ordonnancement d'instructions de boucles internes est connu sous le nom de pipeline logiciel. Le pipeline logiciel désigne une méthode efficace pour l'optimisation de boucles qui permet la réalisation en parallèle des opérations des différentes itérations de la boucle. Dans cette thèse, nous nous intéressons principalement au problème d'ordonnancement périodique qui est un cas particulier de l'ordonnancement cyclique et qui est également la base du pipeline logiciel. Le terme ordonnancement modulo désigne un ordonnancement périodique tel que l'allocation de ressources pour une opération donnée n'est pas modifiée d'une itération sur l'autre. Pour résoudre le problème, nous nous intéressons aux formulations de programmation linéaire en nombres entiers, et notamment à la résolution du problème par des techniques de séparation, évaluation, génération de colonnes, relaxation lagrangienne et des méthodes hybrides. En particulier, nous proposons des nouvelles formulations basées sur des variables binaires représentant l'exécution d'ensembles d'instructions en parallèle. Enfin, les méthodes développées ont été validées sur des jeux d'instances industrielles pour des processeurs de type VLIW.
22
Ayala, Perez Maria Alejandra. "Programmation linéaire en nombres entiers pour l'ordonnancement cyclique sous contraintes de ressources". Toulouse 3, 2011. http://thesesups.ups-tlse.fr/1175/.
Texto completo da fonteResumo:
Un problème d'ordonnancement cyclique consiste à ordonner dans le temps l'exécution répétitive d'un ensemble d'opérations liées par des contraintes de précédence, en utilisant un nombre limité de ressources. Ces problèmes ont des applications immédiates dans les systèmes de production ou en informatique parallèle. Particulièrement, ils permettent de modéliser l'ensemble des contraintes de précédence et de ressource à prendre en compte pour l'ordonnancement d'instructions dans les processeurs de type VLIW (Very Long Instruction Word). Dans ce cas, une opération représente une instance d'une instruction dans un programme. L'ordonnancement d'instructions de boucles internes est connu sous le nom de pipeline logiciel. Le pipeline logiciel désigne une méthode efficace pour l'optimisation de boucles qui permet la réalisation en parallèle des opérations des différentes itérations de la boucle. Dans cette thèse, nous nous intéressons principalement au problème d'ordonnancement périodique qui est un cas particulier de l'ordonnancement cyclique et qui est également la base du pipeline logiciel. Le terme ordonnancement modulo désigne un ordonnancement périodique tel que l'allocation de ressources pour une opération donnée n'est pas modifiée d'une itération sur l'autre. Pour résoudre le problème, nous nous intéressons aux formulations de programmation linéaire en nombres entiers, et notamment à la résolution du problème par des techniques de séparation, évaluation, génération de colonnes, relaxation lagrangienne et des méthodes hybrides. En particulier, nous proposons des nouvelles formulations basées sur des variables binaires représentant l'exécution d'ensembles d'instructions en parallèle. Enfin, les méthodes développées ont été validées sur des jeux d'instances industrielles pour des processeurs de type VLIWThe resource-constrained modulo scheduling problem (RCMSP) is a general periodic cyclic scheduling problem, abstracted from the problem solved by compilers when optimizing inner loops at instruction level for very long instruction word parallel processors. Since solving the instruction scheduling problem at compilation phase in less time critical than for real time scheduling, integer linear programming (ILP) is a relevant technique for the RCMSP. In this work, we are interested in the methods based on the integer linear programming for the RCMSP. At first, we present a study of the two classic integer linear formulation for the RCMSP. A theoretical evidence of the equivalence between the classic formulations is shown in terms of linear programming (LP) relaxation. Secondly, based on the ILP formulations for the RCMSP, stronger formulations for the RCMSP derived from Dantzig-Wolfe decomposition are presented. In these formulations, the number of variables can be huge, for this reason, we proposed a column generation scheme to solve their LP relaxations. We propose also the heuristics methods based on the Lagragian relaxation and decomposed software pipelining. The heuristic methods search the transformation of the classic integer linear programming for the RCMSP for the performance improvement in the time for the search of solutions. All formulations are compared experimentally on problem instances generated from real data issued from the STMicroelectronics ST200 VLIW processor family
23
Danna, Emilie. "Intégration des techniques de recherche locale à la programmation linéaire en nombres entiers". Avignon, 2004. http://www.theses.fr/2004AVIG0132.
Texto completo da fonteResumo:
Cette thèse présente plusieurs algorithmes pour l'intégration des techniques de recherche locale à la programmation linéaire en nombres entiers (PLNE). Premièrement, nous introduisons un schéma de coopération entre recherche locale et génération de colonnes qui généralise le concept d'heuristiques pour le branch-and-cut au branch-and-price et nous l'appliquons avec succès au problème de tournées de véhicules avec fenêtres de temps. Deuxièmement, nous présentons une nouvelle heuristique pour les problèmes linéaires quelconques en nombres entiers : Relaxation Induced Neighborhood Search (RINS). Cette heuristique produit des solutions entières de qualité pour des modèles qu'il était très difficile de résoudre auparavant. Elle est maintenant implantée dans le logiciel ILOG CPLEX 9. RINS exploite les trois concepts fondamentaux de la recherche locale (voisinage, intensification et diversification) en les transposant à la programmation linéaire en nombres entiers. Cette heuristique est générique : elle peut être appliquée à n'importe quel modèle de PLNE, sans aucune connaissance préalable de sa structure. RINS nous permet de formaliser la notion d'algorithme "conceptuellement hybride". Ce paradigme de développement consiste à utiliser une seule technique de résolution et à intégrer dans ce cadre les concepts d'autres techniques plutôt qu'à faire coopérer des composants logiciels. Les performances de RINS et notre analyse des difficultés des algorithmes hybrides existants laissent à penser que cette classe d'algorithmes est prometteuse. Troisièmement, nous nous intéressons plus en détail au problème d'ordonnancement d'atelier avec coûts d'avance et de retard sur lequel RINS est particulièrement efficace. Nous proposons plusieurs améliorations et extensions du modèle disjonctif pour ce problème et une heuristique (MCORE: big-M COefficient REduction) qui pourrait être généralisée à d'autres modèles de structure similaire. MCORE est également un algorithme "conceptuellement hybride"We present several algorithms for integrating local search technique into mixed integer programming (MIP). We first introduce a cooperation scheme between local search and branch-and-price that generalizes the concept of branch-and-cut heuristics to branch-and-price and we apply it successfully to the vehicle routing problem with time windows. We then present a new MIP heuristic that we call Relaxation Induced Neighborhood Search (RINS). This heuristic finds good integer solutions on models that previously were very difficult to solve. It is now implemented in ILOG CPLEX 9. RINS exploits the three fundamental concepts of local search (neighborhood, intensification, and diversification) and transposes them to mixed integer programming. This heuristic is generic : it can be applied to any MIP model, with no other input than the model itself. RINS allows us to formalize the notion of "hybrid in spirit'' algorithms. This development paradigm consists in using only one optimization technique and integrating into its framework concepts of other resolution techniques instead of having several software components cooperate. RINS performances and our analysis of difficulties encountered by existing hybrid algorithms suggest that this class of algorithms is promising. We finally concentrate on the job-shop scheduling problem with earliness and tardiness costs on which RINS is particularly effective. We propose several improvements and extensions of the disjunctive model for this problem and a heuristic (MCORE : big-M COefficient REduction) that could be generalized to other MIP models of similar structure. MCORE is also a "hybrid in spirit'' algorithm
24
Makhlouf, Yosra. "Hybrid flow shop scheduling for a surgery planning problem". Electronic Thesis or Diss., Université de Lorraine, 2023. http://www.theses.fr/2023LORR0178.
Texto completo da fonteResumo:
Dans cette thèse, nous étudions un problème d’ordonnancement de type flow shop hybride à deux étages avec une contrainte sans attente et flexibilité inter-étage pour minimiser le makespan. Le problème est inspiré du contexte hospitalier pour la planification des opérations chirurgicales. La variante du problème abordée a récemment été introduite dans la littérature et démontrée NP-diffcile au sens fort. Le problème est particulièrement dur en raison des multiples ressources impliquées et des restrictions sur les temps d'attente et sur les périodes d'inactivité des ressources. Au mieux de nos connaissances, la version générale du problème avec plusieurs machines à chaque étage, la non-attente et la flexibilité entre les étages n'a jamais été traitée jusqu'à présent. Seuls des algorithmes d'approximation pour certaines versions simplifiées du problème ont été présentés. Aucun test expérimental n'a été effectué. Cette thèse aborde la version générale de l’ordonnancement en flow shop hybride à deux étages sans attente avec flexibilité inter-étage pour la minimisation du makespan. Nous nous concentrons sur les formulations mathématiques et les méthodes de résolution exactes. Notre contribution comporte deux axes : un modèle mathématique et une méthode arborescente exacte. Nous développons également plusieurs bornes inférieures et heuristiques et effectuons des tests expérimentaux afin d'évaluer les performances des approches proposées. La première contribution est un modèle indexé par le temps de programmation linéaire en nombres entiers mixtes pour le problème. Nous ajoutons des inégalités valides pour renforcer la formulation. Des bornes inférieures sur la valeur du makespan sont également calculées et des heuristiques sont développées. Le modèle est testé sur plusieurs classes d'instances générées en fonction du contexte hospitalier. Les performances du modèle et des inégalités valides sont étudiées. La deuxième contribution est un algorithme par séparation et évaluation adapté à la structure du problème. Nous établissons une nouvelle propriété de dominance et développons plusieurs heuristiques pour calculer des solutions initiales. Un schéma de branchement est présenté en fonction des caractéristiques et des contraintes du problème. L'algorithme est testé sur le même groupe d'instances pour évaluer la performance. Une comparaison avec le modèle mathématique est également effectuéeIn this thesis, we study a two-stage hybrid flow shop scheduling problem with no-wait and inter-stage flexibility for minimizing the makespan. The problem is inspired from the hospital context for the scheduling of surgeries. The addressed problem variant was recently introduced in the literature and proved to be strongly NP-hard. The problem is particularly challenging due to the multiple resources involved and restrictions on waiting times and resource idleness. To the best of our knowledge, the general version of the problem with multiple machines at each stage, no-wait and inter-stage flexibility has never been treated so far. Only approximation algorithms for some simplified versions of the problem have been presented. No experimental testing was conducted. This thesis addresses the general version of the two-stage no-wait hybrid flow shop with inter-stage flexibility for makespan minimization. We focus on mathematical formulations and exact solution methods. Our contribution is two-fold: a mathematical model, and an exact search tree method. We also develop several lower bounds and heuristics and perform experimental testing in order to evaluate the performance of the proposed approaches. The first contribution is a time-indexed mixed integer linear programming model for the problem. We add valid inequalities to strengthen the formulation. Lower bounds on the makespan value are also computed and heuristics are developed. The model is tested on several classes of instances generated based on the hospital context. The performances of the model and valid inequalities are highlighted. The second contribution is a branch-and-bound algorithm tailored to the problem's structure. We establish a novel dominance property and develop several heuristics to compute initial solutions. A branching scheme is presented based on the problem's characteristics and constraints. The branch-and-bound is tested on the same testbed to evaluate the performance. A comparison to the mathematical model is also conducted
25
Plateau, Agnès. "Hybridation de méthodes intérieures et de métaheuristiques pour la programmation linéaire en nombres entiers". Paris 9, 2000. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=2000PA090065.
Texto completo da fonteResumo:
À l'origine destinées à la résolution de programmes linéaires continus, les méthodes intérieures ont trouvé un champ d'applications beaucoup plus large incluant aussi bien les programmes quadratiques que les problèmes d'optimisation en nombres entiers et plus récemment encore, les problèmes de programmation semi-définie. Les méthodes intérieures représentent une bonne alternative à la méthode du simplexe, particulièrement pour des problèmes de grande taille dont la matrice des contraintes possède une structure appropriée. Par conséquent, plusieurs méthodes de type branch-and-bound utilisant des techniques de points intérieurs ont été développées pour la programmation entière depuis une dizaine d'années. Cette thèse est consacrée a l'élaboration d'une méthode hybride performante pour la résolution approchée de programmes linéaires en nombres entiers, reposant sur une combinaison originale d'un algorithme de points intérieurs et d'ajout de coupes avec une métaheuristique. Elle débute par une recherche arborescente qui met en jeu une méthode intérieure et deux types de coupes (économiques et valides), engendrant un ensemble diversifié de solutions entières réalisables. Ces solutions permettent de construire la population initiale d'une métaheuristique de type recomposition de chemins (path relinking), qui est une méthode de combinaison de couples de solutions. Ce concept de combinaison permet d'élargir le champ d'exploration du domaine des solutions en travaillant sur la base non pas d'une solution unique mais d'une population de solutions. Notre méthode est validée par des expériences numériques effectuées sur des instances de programmes linéaires en variables 0-1 (sac à dos multidimensionnel, problème général d'affectation).
26
Hijazi, Hassan. "Optimisation non-linéaire mixte en nombres entiers pour la conception de réseaux en télécommunications". Thesis, Aix-Marseille 2, 2010. http://www.theses.fr/2010AIX22107/document.
Texto completo da fonteResumo:
Dans cette thèse, nous nous basons sur les outils apportés par la programmation mathématique afin de modéliser et résoudre des problèmes relevant du domaine des télécommunications. Notre premier objectif consiste à se conformer aux contraintes réelles, prenant en compte les aléas courants, afin de définir des stratégies optimales de routage et de planification dans les réseaux. Les contributions théoriques concernent l'optimisation convexe non linéaire mixte en nombres entiers. Parmi les résultats majeurs, nous établissons en particulier : *une formulation compacte des contraintes de type "on/off" qui s'écrivent f(x) ≤ 0 si z = 1,I ≤ x ≤ u si z = 0, basée sur une nouvelle caractérisation de l'enveloppe convexe de l'union d'un hyper-rectangle et d'un ensemble convexe dans l'espace des variables d'origine. * Une prise en compte de l'incertitude au niveau des fonctions additives ∑i(fi(xi) + vi) ≤ 0 où vi représente une perturbation bornée de chaque fonction univarée fi(xi). * Un algorithme spécialisé pour les problèmes d'optimisation non-linéaires mixtes en nombres entiers faisant intervenir des fonctions additives. D'un point de vue industriel, ces apports théoriques nous permettent de nous rapprocher de notre objectif consistant à définir des stratégies de gestion optimales pour des réseaux de télécommunications plus fiables. La qualité de service perçue par le client est modélisée par une fonction délai de bout en bout, différentiée selon le type de service et dépendant de la congestion au niveau de chaque lienIn our work, we rely on the powerful arsenal of mathematical programming theory to model telecommunication problems and devise efficient methods for solving them. Our goal is to comply to real life constraints when defining optimal routing strategies and designing efficient capacity planning tools. Theoretical contributions apply the field of Mixed Integer Non-Linear Optimization. Among relevant results, let us mention :Explicit formulations of convex hulls in disjunctive programming, generalizing the famous perspective formulationsTractable compact formulations of problems featuring inerval uncertainty in Robust OptimizationAn efficient Outer-Inner approximation algorithm for solving large families of separable mixed Integer Non-Linear Programs (MINLPs) and Second Order Cone Programs (SOCPs), outperforming state-of-the-art commercial solvers.In the application part, our work aims at introducing reliable telecommunication networks, offering appropriate and guaranteed Quality of Service to all its customers. Today, Wide Access Networks (WAN), Virtual Private Networks (VPN) or IP-based Backbones carry a wide range services, namely: voice, video streaming and data traffic. Each one of these contents has its own performance requirements. Unfortunately, best effort algorithms are implemented at all levels, offering no guarantee for delay sensitive applications. Is it possible to build routing strategies guaranteeing upper bounds on source-to-destination delays? Can we make these routing protocols to delay variation ? Does service differentiation affect capacity planning decisions ? Answers to these questions will be developed in this thesis
27
Darwiche, Mostafa. "When operations research meets structural pattern recognition : on the solution of error-tolerant graph matching problems". Thesis, Tours, 2018. http://www.theses.fr/2018TOUR4022/document.
Texto completo da fonteResumo:
Cette thèse se situe à l’intersection de deux domaines de recherche scientifique la Reconnaissance d’Objets Structurels (ROS) et la Recherche Opérationnelle (RO). Le premier consiste à rendre la machine plus intelligente et à reconnaître les objets, en particulier ceux basés sur les graphes. Alors que le second se focalise sur la résolution de problèmes d’optimisation combinatoire difficiles. L’idée principale de cette thèse est de combiner les connaissances de ces deux domaines. Parmi les problèmes difficiles existants en ROS, le problème de la distance d’édition entre graphes (DEG) a été sélectionné comme le cœur de ce travail. Les contributions portent sur la conception de méthodes adoptées du domaine RO pour la résolution du problème de DEG. Explicitement, des nouveaux modèles linéaires en nombre entiers et des matheuristiques ont été développé à cet effet et de très bons résultats ont été obtenus par rapport à des approches existantesThis thesis is focused on Graph Matching (GM) problems and in particular the Graph Edit Distance (GED) problems. There is a growing interest in these problems due to their numerous applications in different research domains, e.g. biology, chemistry, computer vision, etc. However, these problems are known to be complex and hard to solve, as the GED is a NP-hard problem. The main objectives sought in this thesis, are to develop methods for solving GED problems to optimality and/or heuristically. Operations Research (OR) field offers a wide range of exact and heuristic algorithms that have accomplished very good results when solving optimization problems. So, basically all the contributions presented in thesis are methods inspired from OR field. The exact methods are designed based on deep analysis and understanding of the problem, and are presented as Mixed Integer Linear Program (MILP) formulations. The proposed heuristic approaches are adapted versions of existing MILP-based heuristics (also known as matheuristics), by considering problem-dependent information to improve their performances and accuracy
28
Collet, Guillaume. "Alignements locaux pour la reconnaissance de repliements des protéines par programmation linéaire en nombres entiers". Phd thesis, Rennes 1, 2010. https://theses.hal.science/docs/00/51/27/25/PDF/manuscrit_GC.pdf.
Texto completo da fonteResumo:
"Détecter des similarités et des homologies entre protéines est une étape cruciale du processus d'annotation des génomes. Afin de détecter des homologies, les alignements de séquences sont couramment utilisés. Néanmoins, dans la "zone d'ombre", nous devons utiliser les méthodes de reconnaissance de repliements pour détecter des homologies. Dans ce domaine, le problème du "Protein Threading" (PTP) utilise des paramètres pairés pour aligner globalement une séquence de protéine avec une structure de protéine. À notre connaissance, il n'existe pas de méthode d'alignement local utilisant des paramètres pairés. À partir du PTP, nous proposons cinq modéles mathématiques de ces alignements locaux qui ont été implémentés et testés grâce au logiciel CPLEX. Nous avons ensuite développé un algorithme dédié permettant de résoudre un de ces modèles. Cet algorithme utilise des techniques connues en recherche opérationnelle : la séparation-évaluation, la descente de sous-gradient et la relaxation lagrangienne. Bien que les alignements locaux soient d'une plus grande complexité, nous montrons qu'ils sont réalisables et qu'ils améliorent la qualité des alignements. "Detecting similarities and homologies between proteins is a key step during the annotation process. To find such homologies, multiple sequence alignments are widely used. These methods provide global to local alignment features. Nevertheless, in the so called "Twilight Zone", one must relies on fold recognition methods to find homologous proteins. In this field, the Protein Threading Problem (PTP) uses pairwise parameters to globaly align a protein sequence with a protein structure. As far as we know, no local alignment method using pairwise parameters exists. Based on the PTP, we proposed 5 mathematical formulations of such local alignments. These formulations have been implemented and tested with CPLEX 10. 0 package. Then, we developed an efficient dedicated algorithm to solve local alignments. Our algorithm uses well-known techniques from Operational Research: Branch & Bound, Subgradient Descent and Lagrangian Relaxation. We show that, despite greater complexity, local alignments using pairwise parameters are feasible and improve the quality of the alignments
29
Collet, Guillaume. "Alignements locaux pour la reconnaissance de repliements des protéines par programmation linéaire en nombres entiers". Phd thesis, Université Rennes 1, 2010. http://tel.archives-ouvertes.fr/tel-00512725.
Texto completo da fonteResumo:
Détecter des similarités et des homologies entre protéines est une étape cruciale du processus d'annotation des génomes. Afin de détecter des homologies, les alignements de séquences, globaux ou locaux, sont couramment utilisés. Néanmoins, dans la "zone d'ombre", nous devons utiliser les méthodes de reconnaissance de repliements. Dans ce domaine, le problème du "Protein Threading" (PTP) utilise des paramètres pairés pour aligner globalement une séquence de protéine avec une structure de protéine. À notre connaissance, il n'existe pas de méthode d'alignement local utilisant des paramètres pairés. À partir du PTP, nous proposons cinq modélisations mathématiques de ces alignements locaux qui ont été implémentées et testées grâce au logiciel CPLEX 10.0. Nous avons ensuite développé un algorithme dédié permettant de résoudre un de ces modèles. Cet algorithme utilise des techniques connues en recherche opérationnelle : la séparation-évaluation, la descente de sous-gradient et la relaxation lagrangienne. Bien que les alignements locaux soient d'une plus grande complexité, nous montrons qu'ils sont réalisables et qu'ils améliorent la qualité des alignements.
30
Kagni, Victor. "Programmation linéaire multiobjectif en nombres entiers : théories, algorithmes et essai d'application à la gestion d'équipements hospitaliers". Dijon, 1995. http://www.theses.fr/1995DIJOE013.
Texto completo da fonteResumo:
Les méthodes de programmation linéaire multiobjectif avec des variables continues datent de 1960. C'est en 1973 que l'indivisibilité a été prise en compte dans l'optimisation multiobjective. Ce travail est donc une contribution aux problèmes et méthodes multiobjectives en nombres entiers. La première partie traite les problèmes mono-objectifs et multiobjectifs continus. On y trouve le théorème de séparation adapté en multiobjectif et le théorème d'équivalence entre l'optimum de Pareto continu et le programme multiparamétrique continu. Cette équivalence est à l'origine des méthodes multiobjectives continues selon que la détermination des pondérations des préférences du décideur est a priori, a posteriori ou progressive. Ces méthodes sont traitées dans les généralités. La deuxième partie traite la programmation multiobjectif en nombres entiers, en théories et algorithmes. Le théorème d'équivalence précédent a été adapté en nombres entiers dans cette partie. Les méthodes en nombres entiers ont été traitées dans la troisième partie, privilégiant ainsi les pondérations a priori avec le goal programming en nombres entiers et progressives avec les méthodes interactives en nombres entiers par révélation des préférences, à cause de leur souplesse. L'accent est mis sur les pondérations progressives des préférences afin de limiter les jugements de valeur sur les objectifs. Les méthodes sont ainsi exposées selon que les variables décrivent n, 0-1 et selon qu'elles sont mixtes. Selon la nature des variables, des méthodes interactives en nombres entiers avec "branchements préférentiels" ont été proposées. Elles optimisent simultanément tous les objectifs en respectant l'optimum de Pareto en nombres entiers. En ce qui concerne les variables mixtes, la technique de décomposition binaire et la médiane ont été utiliséesMultiobjective linear programming methods with continuous variables date from 1960. It's only in 1973 that the indivisibility was taken into account in multiobjective optimization. This work is a contribution to the multiobjective integer linear problems and methods. The first part is about single and multiobjective problems with continuous variables. It includes the separation theorem used as a multiobjective case, and the theorem of the equivalence between Pareto's optimum and multiparametric program. This equivalence is a source of continuous multiobjective methods when the decision maker's preference weightings are made a priori, a posteriori or when they are progressive. These methods are used in general cases. The second part deals with multiobjective integer linear programming in theories and algorithms. The preceding equivalence theorem has been adapted to integer case in this part. Integer methods are subject of the third part; a greater place is given to a priori weightings, with integer goal programming and progressive weightings with integer interactive methods by preference revelation, because of their adaptability. Progressive preference weightings are emphasized so as to limit value judgement on objectives. So, methods are presented depending on whether variables describe n, 0-1 or they are mixed. Integer interactive methods with preferential vector have been suggested. They optimize all the objectives simultanously, respecting integer Pareto's optimum. Concerning mixed variables, the methods used were binary decomposition and median analysis
31
Ouali, Abdelkader. "Méthodes hybrides parallèles pour la résolution de problèmes d'optimisation combinatoire : application au clustering sous contraintes". Thesis, Normandie, 2017. http://www.theses.fr/2017NORMC215/document.
Texto completo da fonteResumo:
Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialiséesCombinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics
32
Mehiaoui, Asma. "Techniques d'analyse et d'optimisation pour la synthèse architecturale de systèmes temps réel embarqués distribués : problèmes de placement, de partitionnement et d'ordonnancement". Thesis, Brest, 2014. http://www.theses.fr/2014BRES0011/document.
Texto completo da fonteResumo:
Dans le cadre industriel et académique, les méthodologies de développement logiciel exploitent de plus en plus le concept de “modèle” afin d’appréhender la complexité des systèmes temps réel critiques. En particulier, celles-ci définissent une étape dans laquelle un modèle fonctionnel, conçu comme un graphe de blocs fonctionnels communiquant via des échanges de signaux de données, est déployé sur un modèle de plateforme d’exécution matérielle et un modèle de plateforme d’exécution logicielle composé de tâches et de messages. Cette étape appelée étape de déploiement, permet d’établir une architecture opérationnelle du système nécessitant une validation des propriétés temporelles du système. Dans le contexte des systèmes temps réel dirigés par les évènements, la vérification des propriétés temporelles est réalisée à l’aide de l’analyse d’ordonnançabilité basée sur l’analyse des temps de réponse. Chaque choix de déploiement effectué a un impact essentiel sur la validité et la qualité du système. Néanmoins, les méthodologies existantes n’offrent pas de support permettant de guider le concepteur d’applications durant l’exploration de l’espace des architectures possibles. L’objectif de ces travaux de thèse consiste à mettre en place des techniques d’analyse et de synthèse automatiques permettant de guider le concepteur vers une architecture opérationnelle valide et optimisée par rapport aux performances du système. Notre proposition est dédiée à l’exploration de l’espace des architectures en tenant compte à la fois des quatre degrés de liberté déterminés durant la phase de déploiement, à savoir (j) le placement des éléments fonctionnels sur les éléments de calcul et de communication de la plateforme d’exécution, (ii) le partitionnement des éléments fonctionnels en tâches temps réel et des signaux de données en messages, (iii) l’affectation de priorités d’exécution aux tâches et aux messages du système et (iv) l’attribution du mécanisme de protection des données partagées pour les systèmes temps réel périodiques. Nous nous intéressons principalement à la satisfaction des contraintes temporelles et celles liées aux capacités des ressources de la plateforme cible. De plus, nous considérons l’optimisation des latences de bout-en-bout et la consommation mémoire. Les approches d’exploration architecturale présentées dans cette thèse sont basées sur la technique d’optimisation PLNE (programmation linéaire en nombres entiers) et concernent à la fois les applications activées périodiquement et celles dont l’activation est pilotée par les données. Contrairement à de nombreuses approches antérieures fournissant une solution partielle au problème de déploiement, les méthodes proposées considèrent l’ensemble du problème de déploiement. Les approches proposées dans cette thèse sont évaluées à l’aide d’applications génériques et industriellesModern development methodologies from the industry and the academia exploit more and more the ”model” concept to address the complexity of critical real-time systems. These methodologies define a key stage in which the functional model, designed as a network of function blocks communicating through exchanged data signals, is deployed onto a hardware execution platform model and implemented in a software model consisting of a set of tasks and messages. This stage so-called deployment stage allows establishment of an operational architecture of the system, thus it requires evaluation and validation of the temporal properties of the system. In the context of event-driven real-time systems, the verification of temporal properties is performed using the schedulability analysis based on the response time analysis. Each deployment choice has an essential impact on the validity and the quality of the system. However, the existing methodologies do not provide supportto guide the designer of applications in the exploration of the operational architectures space. The objective of this thesis is to develop techniques for analysis and automatic synthesis of a valid operational architecture optimized with respect to the system performances. Our proposition is dedicated to the exploration of architectures space considering at the same time the four degrees of freedom determined during the deployment phase, (i) the placement of functional elements on the computing and communication resources of the execution platform, (ii) the partitioning of function elements into real time tasks and data signals into messages, (iii) the priority assignment to system tasks and messages and (iv) the assignment of shared data protection mechanism for periodic real-time systems. We are mainly interested in meeting temporal constraints and memory capacity of the target platform. In addition, we are focusing on the optimization of end-to-end latency and memory consumption. The design space exploration approaches presented in this thesis are based on the MILP (Mixed Integer Linear programming) optimization technique and concern at the same time time-driven and data-driven applications. Unlike many earlier approaches providing a partial solution to the deployment problem, our methods consider the whole deployment problem. The proposed approaches in this thesis are evaluated using both synthetic and industrial applications
33
Thiongane, Babacar. "Réoptimisation dans le dual lagrangien du biknapsack en variables 0-1". Paris 13, 2003. http://www.theses.fr/2003PA132007.
Texto completo da fonteResumo:
Dans cette thèse nous étudions la réoptimisation dans le dual lagrangien du biknapsack en variables 0-1. La première partie de la thèse concerne la postoptimisation en variables 0-1 (analyse de sensibilitè, paramétrisation et réoptimisation). Nous faisons une synthèse sur les volets "analyse de sensibilité" et réoptimisation" pour les problèmes linéaires en 0-1, et proposons des contributions plus originales autour du problème de la paramétrisation en 0-1, et notamment sur la complexité du problème. De plus, un nouvel algorithme a été proposé pour le résoudre. Une étude de la réoptimisation dans la résolution du dual lagrangien du biknapsack 0-1 pro-prement dite est réalisée dans la seconde partie, dans laquelle nous proposons deux nouveaux algorithmes itératifs MARIE et ASIA. Les techniques de réoptimisation employées dans ces deux algorithmes concernent la phase de prétaitement de la résolution d'une instance de knapsack 0-1 à chaque itération. Les performances de ces algorithmes ont été mises en évidence à travers des expérimentations numériques. Une procédure de réoptimisation basée sur l'exploitation de l'arborescence obtenue par branch ! bound a aussi été proposée. Finalement des gains intéressants ont été obtenus par combinaison des techniques de réoptimisation utilisées (prétaitement et exploration) pour résoudre chaque instance de knapsack 0-1 au sein d'un algorithme de sous-gradient.
34
Boumghar, Sabéha. "Nouvelle approche de l'optimisation en temps réel des feux d'un carrefour complexe isolé par la programmation linéaire en nombres entiers". Paris 9, 2000. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=2000PA090034.
Texto completo da fonteResumo:
Le carrefour à feux constitue un noeud important dans le réseau de transport urbain. Il permet d'écouler ou de stocker des flux de véhicules selon la variation du trafic. Ainsi, il est considéré comme un levier important en matière de régulation du trafic urbain. Nous nous intéressons dans le cadre de cette thèse au problème d'optimisation en temps réel des feux d'un carrefour complexe isolé afin de minimiser le temps d'attente de ses usagers. La formulation de ce problème par un programme linéaire mixte en nombres entières nous a permis d'appréhender toute sa dynamique et sa complexité. Le système bonsaï que nous proposons est une stratégie adaptative qui permet d'adapter les durées des états vert et rouge des feux en fonction des débits d'arrivée et des longueurs des files d'attente aux tronçons qui leur sont associés, et déterminer l'ordonnancement optimal des états de feux. Pour la résolution de ce problème, une approche exacte fondée sur une méthode de recherche arborescente, algorithme de BRANCH and BOUND (B & B), a été adoptée. Les expérimentations sur des carrefours fictifs et le carrefour réel situé devant l'inrets ont révélé des temps de convergence très courts de l'ordre de quelques centièmes de seconde, pour des instances du problème de 400 à 640 variables binaires. Néanmoins, nous proposons deux heuristiques permettant la réduction des temps de convergence de l'algorithme B & B. Ces heuristiques peuvent être utiles dans le cas d'un carrefour de très grande taille et dans la perspective de la régulation d'un ensemble de carrefours, voire d'un réseau. Les performances en temps d'attente ont révélé des gains de 49% en moyenne de notre stratégie bonsaï par rapport au système de plan de feux fixes implémenté sur le terrain. Ces gains peuvent atteindre 60% dans le cas d'un trafic fluide.
35
Nait-Abdallah, Mohamed Rabie. "Modèles de dimensionnement et de planification dans un centre d'appels". Châtenay-Malabry, Ecole centrale de Paris, 2008. http://www.theses.fr/2008ECAP1062.
Texto completo da fonteResumo:
Cette thèse aborde la gestion des ressources humaines dans un centre d’appels. Plus spécifiquement, nous nous intéressons aux problèmes de dimensionnement et de planification. L’objectif sous-jacent est d’assurer la meilleure qualité de service au client (par exemple minimiser le délai d’attente) avec un coût salarial minimum pour l’entreprise. Ces problématiques sont généralement modélisées dans la littérature par le problème de construction de vacation (shift-scheduling problem). Pour appréhender ce problème, nous introduisons le paradigme de chaîne d’activités. Ce paradigme nous permet de représenter la grande diversité des environnements et des contraintes de gestion des ressources humaines dans un centre d’appels. Nous traduisons ensuite ce paradigme en programme linéaire en nombres entiers pour résoudre les problèmes de dimensionnement et de planification. Nous proposons enfin une méthode pour intégrer au programme linéaire en nombres entiers un objectif de qualité de service non linéaireWe address in this thesis dimensioning and planning issues in a call center. The purpose is to guarantee a high quality of service at a minimum cost for the company. In the literature, theses issues are generally modeled using the shift-scheduling problem. In this thesis we introduce what we call the activity series paradigm. This paradigm allows dealing with the great diversity of call center constraints and environments. It was used to model and solve the planning and dimensioning problems with an integer linear program. We also, develop a method to optimize a non-linear quality of service in the shift-scheduling problem
36
Abdull, Aziz Manaf. "Etude d'algorithmes de réduction de bases de réseaux et problème du sac à dos". Aix-Marseille 2, 1994. http://www.theses.fr/1994AIX22018.
Texto completo da fonteResumo:
Le premier chapitre de ce travail consiste en l'etude de base lll#(##)-reduite et d'un algorithme effectuant une telle reduction. Nous avons mesure, s. V. Designant la norme d'un plus court vecteur du reseau engendre par la famille (b#1,. . ,b#n). A) l'influence du choix de sur les nombres moyens de bases aleatoires b#-#1,. . ,b#-#n satisfaisant respectivement 1) s. V=l(b#-#1) ; 2) s. V=l(b#-#i), avec 2in ; 3) s. Vl(b#-#i), pour tout i, 1in. B) l'influence du type de tir aleatoire sur les resultats de a) ; ou (b#-#i) designe un vecteur quelconque de la base lll#(##)-reduite. A partir des resultats experimentaux nous constatons que: a) le pourcentage des bases satisfaisant 1) augmente avec. B) l'influence du choix du tir aleatoire sur les resultats de a) n'est pas notable. Nous avons egalement compare les longueurs des differents vecteurs d'une famille lll#(##)-reduite, et cela suivant que vaut 0. 75 ou 0. 99. A partir des resultats experimentaux nous constatons que: a) toute famille lll#(#0#. #9#9#)-reduite est ordonnee, i. E. L(b#-#1)<
37
Haddad, Marcel Adonis. "Nouveaux modèles robustes et probabilistes pour la localisation d'abris dans un contexte de feux de forêt". Electronic Thesis or Diss., Université Paris sciences et lettres, 2020. http://www.theses.fr/2020UPSLD021.
Texto completo da fonteResumo:
A cause du réchauffement climatique, le nombre et l’intensité des feux de forêts augmentent autour du globe. Dansce contexte, la construction de refuges contre le feu est une solution de plus en plus envisagée. Le problème consisteessentiellement à localiser p refuges de sorte à minimiser la distance maximale qui sépare un usager du plus procherefuge accessible en cas de feux. Le territoire considéré est divisé en zones et est modélisé comme un graphe auxarêtes pondérées. Un départ de feux sur une seule zone (c’est-à-dire sur un sommet). La principale conséquence d’unfeu est que les chemins d’évacuation sont modifiés de deux manières. Premièrement, un chemin d’évacuation ne peutpas traverser le sommet en feu. Deuxièmement, le fait qu’une personne proche de l’incendie puisse avoir un choix limitéde direction d’évacuation, ou être sous stress, est modélisé à l’aide d’une stratégie d’évacuation nouvellement définie.Cette stratégie d’évacuation induit des distances d’évacuation particulières qui rendent notre modèle spécifique. Selon letype de données considéré et l’objectif recherché, nous proposons deux problèmes avec ce modèle: le Robust p-CenterUnder Pressure et le Probabilistic p-Center Under Pressure. Nous prouvons que ces deux problèmes sont NP-difficilessur des classes de graphes pertinentes pour notre contexte. Nous proposons également des résultats d’approximationet d’inapproximation. Finalement, nous développons des algorithmes polynomiaux sur des classes de graphes simples,et nous développons des algorithmes mathématiques basés sur la programmation linéaireThe location of shelters in different areas threatened by wildfires is one of the possible ways to reduce fatalities in acontext of an increasing number of catastrophic and severe forest fires. The problem is basically to locate p sheltersminimizing the maximum distance people will have to cover to reach the closest accessible shelter in case of fire. Thelandscape is divided in zones and is modeled as an edge-weighted graph with vertices corresponding to zones andedges corresponding to direct connections between two adjacent zones. Each scenario corresponds to a fire outbreak ona single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuationpath cannot pass through the vertex on fire. Second, the fact that someone close to the fire may have limited choice, ormay not take rational decisions, when selecting a direction to escape is modeled using a new kind of evacuation strategy.This evacuation strategy, called Under Pressure, induces particular evacuation distances which render our model specific.We propose two problems with this model: the Robust p-Center Under Pressure problem and the Probabilistic p-CenterUnder Pressure problem. First we prove hardness results for both problems on relevant classes of graphs for our context.In addition, we propose polynomial exact algorithms on simple classes of graphs and we develop mathematical algorithmsbased on integer linear programming
38
Meister, Benoît. "Stating and manipulating periodicity in the polytope model : Applications to program analysis and optimization". Université Louis Pasteur (Strasbourg) (1971-2008), 2004. https://publication-theses.unistra.fr/public/theses_doctorat/2004/MEISTER_Benoit_2004.pdf.
Texto completo da fonteResumo:
Cette thèse est centrée sur les objets mathématiques formés de l'intersection entre un polyèdre rationnel dépendant de paramètres et un réseau régulier de points à coordonnées entières: les Z-polyèdres paramétriques. Ces objets sont utilisés en compilation où ils permettent de modéliser les nids de boucles for/do (on parle du "modèle polyédrique"), afin d'analyser leur comportement, et de les transformer pour les optimiser ou les paralléliser. Cette thèse contribue à l'amélioration de ce modèle en introduisant le concept de polyèdre périodique, qui traduit le caractère périodique des coordonnées de points entiers extrémaux du Z-polyèdre. Ce concept est d'abord utilisé pour définir le premier algorithme de calcul de la coque entière d'un Z-polyèdre paramétrique P, c'est à dire l'enveloppe convexe des points contenus dans P. Dans le même cadre, nous nous intéressons aux polynômes d'Ehrhart, qui donnent le nombre de points à coordonnées entières contenus dans P et qui possèdent un caractère périodique. Certaines observations fines sur le caractère périodique de la coque entière de P nous permettent d'étendre une conjecture prononcée par Ehrhart et qui donne des informations précises sur la périodicité des coefficients. Nous en dérivons une condition pour laquelle le polynôme d'Ehrhart d'un Z-polyèdre est non-périodique, et en déduisons deux méthodes d'approximation d'un polynôme d'Ehrhart par un polynôme non-périodique. Dans l'un des cas, nous donnons également un algorithme de calcul de ce polynôme dont la complexité est polynomiale en dimension fixée. D'autre part, l'ensemble des solutions faisables d'un problème de programmation linéaire paramétrique en nombre entiers est un Z-polyèdre S. La solution optimale est donnée par un un point extrémal de S, qui dépend périodiquement des paramètres. Notre approche est de considérer un problème général, englobant le problème du maximum lexicographique et la forme classique de la programmation linéaire en nombre entiers. Nous donnons un nouvel algorithme de calcul d'une solution optimale de ce problèmeThis thesis focuses on mathematical objects that are the intersection between a rational parametric polyhedron and a lattice of integer points: Z-polyhedra. These objects are used in compilers, where they model nested for/do loops (this model is known as the "polyhedron model"), in order to analyze their behaviour and to transform them in an optimal or parallel loop nest. The main contribution of this thesis is an enhancement of this model, by integrating the periodic character of extremal integer points of the Z-polyhedron, using "periodic polyhedra". This concept is first used to devise the first algorithm for computing the integer hull of a parametric Z-polyhedron P, i. E. , the convex hull of the integer points that belong to P. In the same frame, we study Ehrhart polynomials, which give the number of points with integer coordinates that belong to P. Ehrhart polynomials depend periodically on the parameters of P. Starting from observations about the periodicity of the integer hull of P, we extend a conjecture stated by Ehrhart which gives accurate information on the periodicity of the polynomial's coefficients. Using this, we derive a new condition for which the Ehrhart polynomial of a Z-polyhedron is non-periodic. This allows to give two methods for approximating an Ehrhart polynomial by a non-periodic polynomial. In one of the two cases, we also give a new method for computing this polynomial, whose complexity is polynomial for a fixed dimension. Besides, the set of feasible solutions of a parametric linear integer programming problem is a Z-polyhedron S. The optimal solution is given by an extremal integer point of S, which depends periodically on S's parameters. Our approach considers a problem that encompasses the integer lexicographic maximum problem and the classical integer linear programming problem. We devise a new algorithm for computing the optimal solution of such a problem
39
Partouche, Ariane. "Planification d'horaires de travail : méthodologie, modélisation et résolution à l'aide de la programmation linéaire en nombres entiers et de la programmation par contraintes". Paris 9, 1998. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1998PA090007.
Texto completo da fonteResumo:
La reconnaissance croissante des enjeux économiques et sociaux liés à une gestion efficace de la ressource travail motive de nombreuses recherches et applications sur la planification d'horaires. L'adéquation d'effectifs à une charge variable et étendue au-delà des plages de travail individuelles, ainsi que l'aménagement des jours de travail et de repos, constituent des problèmes fortement combinatoires qui requièrent l'utilisation de techniques d'optimisation. L'objet de cette thèse est de caractériser les diverses situations de planification, de synthétiser la multitude d'approches présentées dans la littérature, de modéliser et résoudre efficacement certains problèmes complexes de planification d'horaires. Nous nous intéressons en particulier au problème de construction de vacations couvrant une courbe de charge à cout minimal. Après avoir comparé différentes modélisations et approches de résolution, nous montrons expérimentalement, sur des instances de grande taille, que ce problème formulé comme un problème de couverture d'ensembles généralisé est facilement résolu par programmation linéaire en nombres entiers (plne). Nous caractérisons même certaines classes polynomiales de ce problème. Nous étudions ensuite le problème central d'élaboration de grilles de travail pour lequel les performances de la plne et de la programmation par contraintes (ppc) sont également comparées. Finalement, nous élaborons une méthodologie de décomposition d'un problème global de planification associant les techniques de plne et ppc. Cette méthodologie est implémentée et validée dans le cadre d'applications réelles.
40
Azibi, Amine Riad. "Construction de critères en aide à la décision : aspects méthodologiques, techniques et pratiques". Paris 9, 2003. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=2003PA090022.
Texto completo da fonteResumo:
Cette thèse traite de la construction de critères en aide à la décision. La construction de critères constitue une étape clé du processus d'aide à la décision. Cette étape soulève certaines difficultés techniques liées notamment à la prise en compte d'aspects qualitatifs. Nous nous intéressons dans cette thèse plus particulièrement aux critères agrégeant des conséquences qualitatives, ce qui est notamment le cas de critères fondés sur des conséquences dispersées. Après avoir souligné le parallèle entre la problématique de l'agrégation d'attributs qualitatifs et celle de l'affectation, nous proposons une méthodologie d'aide à la construction d'un système cohérent d'affectation multi-attribut. Nos travaux sont axés sur l'utilisation de règles d'affectation de type " si. . . Alors. . . " afin de respecter le caractère qualitatif des attributs. Notre approche repose sur une démarche itérative d'aide à la construction d'une base de règles. Cette démarche originale, de portée générale, vise à enrichir ou affiner progressivement la base de règles en vue d'aboutir à un modèle d'affectation cohérent. Les tests de cohérence sont fondés sur une correspondance entre la représentation logique des règles et une représentation algébrique équivalente. Cette correspondance permet d'exprimer les règles par des contraintes linéaires et de tester la cohérence du modèle d'affectation par règles en résolvant une série de programmes linéaires en variables 0--1This thesis is devoted to criteria construction in decision aiding. Construction of criteria represents a major stage in the decision support process. This stage raises technical difficulties notably related to the use of qualitative aspects. More specifically, we are interested in criteria aggregating qualitative consequences, which is the case of criteria based on dispersed consequences. After emphasizing the equivalence between the aggregation of qualitative attributes and an assignment problem, we propose an original methodology for building a coherent multi-attribute assignment system. Our work is based on “if. . . Then. . . ” assignment rules in order to respect the qualitative nature of attributes. We propose a general approach for a progressive construction of a rule-based assignment model. The process consists in testing iteratively the consistency of the rule base to transform it progressively into a consistent assignment model. Consistency tests are based on a correspondence between the logical representation of rules and an equivalent algebraic representation. This allows us to express rules by linear constraints and then to test the consistency of rule-based assignment models by solving a series of linear programs
41
Salazar, zendeja Luis. "Modèles et algorithmes pour le problème d'interdiction de l'arbre couvrant de poids minimal". Electronic Thesis or Diss., Centrale Lille Institut, 2022. http://www.theses.fr/2022CLIL0028.
Texto completo da fonteResumo:
Dans cette thèse, nous étudions le problème de l’Interdiction de l’Arbre Couvrant Minimal (IACM). Ce problème est un jeu à deux joueurs entre un opérateur de réseau et un interdicteur. Le premier détermine un Arbre Couvrant Minimal (ACM) dans un réseau. Limité par un budget, le second cherche à changer la topologie du réseau pour augmenter le poids de l’ACM. Deux types d’interdiction sont considérés : l’interdiction totale et l’interdiction partielle.Une arête totalement interdite est considérée comme absente tandis que le poids d’une arête partiellement interdite est augmentée d’une quantité prédéfinie. Le budget de l’interdicteur est modélisé par une contrainte de cardinalité,chaque arête a le même poids d’interdiction, ou une contrainte de sac `a dos, les poids d’interdiction peuvent être différents. Sept formulations mathématiques du problème IACM ont été élaborées. Elles se sont avérées efficaces pour des graphes de petite et moyenne taille. Un algorithme de type ”Branch-and-Price” et un algorithme basé sur la décomposition de Benders ont été conçus pour les graphes de plus grande taille. En outre, des inégalités valides sont proposées pour renforcer les modèles et améliorer les performances des algorithmes. Des instances de 200sommets et 19900 ar êtes ont ainsi pu être résolues optimalementIn this thesis, we study the Minimum Spanning Tree Interdiction (MSTI) problem. This problem is a two-player game between a network operator and an interdictor. The former aims to determine a Minimum Spanning Tree (MST) in a network. Constrained by a budget, the latter seeks to change the network topology to increase the weight of aMST. Two types of interdiction are considered: total and partial interdiction. A total interdicted edge is considered absent while the weight of a partial interdicted edge is augmented by a predefined amount. The interdictor’s budget ismodeled as a cardinality, each edge has the same interdiction weight, or knapsack constraint, the interdiction weightsmight be different. Seven mathematical formulations for the MSTI problem are devised. They proved to be efficient on small and medium-size graphs. A Branch-and-Price algorithm and a Benders Decomposition algorithm are designedfor larger graphs. In addition, valid inequalities are proposed to strengthen the models and improve the efficiency of the proposed methods. Instances including up to 200 nodes and 19900 edges are solved to optimality
42
Narboni, Guy Alain. "Un cas remarquable de systèmes linéaires : les systèmes monotones : résolution et application à la vérification formelle de programmes". Cachan, Ecole normale supérieure, 2001. http://www.theses.fr/2001DENS0051.
Texto completo da fonteResumo:
"Savoir décider si oui ou non un système d'inégalités linéaires admet une solution entière est un sous-problème important dans beaucoup d'études de cas. Il est bien connu que cette question, de nature diophantienne, peut être source de difficultés combinatoires. Nous exhumons, dans ce travail, une classe particulière de problèmes linéaires à variables entières dont la résolution exacte peut s'obtenir sans énumération, à partir d'une relaxation continue (soit directement, soit itérativement sur des problèmes bornés). Cette classe "polynômiale" se caractérise par une concordance remarquable entre des propriétés syntaxiques (matrices ayant au plus un coefficient strictement positif par ligne) et des propriétés géométriques (ensemble des solutions formant un demi-treillis). Nous montrons que les techniques de filtrage opérant localement par réduction d'intervalles sont complètes pour cette classe (lorsque les domaines sont bornés), du fait de l'existance d'une solution particulière qui est un extrêmum global. Les systèmes étudiés recouvrent des problèmes aussi variés que la satisfaction de clauses de Horn en logique propositionnelle ou la recherche de plus courts chemins sur un graphe. En abordant leur résolution de manière comparée, nous établissons des ponts entre les procédures classiques d'élimination de variables et d'optimisation discrète et les techniques plus récentes d'approximation par intervalles. Une application plus élaborée concerne l'analyse, en programmation logique avec contraintes, de l'accessiblité dans des machines à états discrets. Les implantations réalisées avec le solveur linéaire de Prolog II ou le solveur d'intervalles de Prolog IV nous permettent de prouver automatiquement plusieurs propriétés, sur des exemples tirés du domaine de la vérification formelle de programmes""Deciding whether or not a linear system of inequalities has integer solutions is an important sub-problem occurring in many case studies. It is well known that such a question of diophantine nature can be a formidable source of combinatorial difficulties. In this thesis, we focus on a class of integer linear problems than can be solved without enumeration (either directly or iteratively, if the problem is bounded)- their relaxation giving here an exact solution. This "polynomial" class is characterized by a remarkable confluence of syntactic and geometric properties (matrices having at most one postivie entry per now, concording with solutions sets forming a semi-lattice). We show that local consistency techniques based on interval narrowing are complete for that class (when the domains are bounded). This stems from the fact that one particular solution is a global maximum (or minimum). The systems under study encompass questions ranging from the satisfiability problem for Horn propositional clauses to the computation of shortest paths on a graph. By comparatively studying their solution algorithms, we are able to establish connections between the classical procedures of variable elimination and discrete optimization, and the more recent interval (or finite domains) approximation solving techniques. A more elaborate application, requiring the power of contraint logic programming, deals with reachability analysis on discrete state machines. Our implementations, using either the linear solver of Prolog III or the interval solver Prolog IV, enable us to prove several program properties automatically, on examples taken from the field of formal verification. "
43
Louat, Christophe. "Etude et mise en œuvre de stratégies de coupes efficaces pour des problèmes entiers mixtes 0-1". Versailles-St Quentin en Yvelines, 2009. http://www.theses.fr/2009VERS0060.
Texto completo da fonteResumo:
Pour cette étude, plusieurs solveurs ont été utilisés afin de comparer leurs comportement quand des mêmes coupes sont ajoutées. Deux solveurs commerciaux (Cplex et Xpress) et un solveur libre (Glpk) ont été utilisés pour faire des tests avec un Branch-and-Bound Séquentiel. Un solveur libre (Bob++) a été utilisé pour réaliser des tests avec un Branch-and-Bound parallèle. Afin de faciliter l’utilisation des différents solveurs en ne faisant qu’un seul code a été créé. Nous présentons tout d’abord les différentes méthodes de coupes qui ont été intégrées à la librairie Glop pour réaliser des expérimentations. Nous montrons ensuite les différentes stratégies implémentées les unes étant des stratégies fixes, les autres des stratégies qui s’adaptent au déroulement de la résolution du problème. Nous présentons et analysons les résultats des exécutions réalisées avec un Branch-and-Bound séquentiel et enfin ceux des exécutions réalisé avec un Branch-and-Bound parallèleThe use of cutting planes is since severals years one of the most used methods to improve the search of an optimal solution reducing the search space in a Branch-and-Bound. The work presented here aims at studying several cutting plane methods and at proposing some strategies to integrate them in a resolution method based on Branch-and-Bound algorithm to solve mixed integer 0-1 problems. We present extensive computational experiments in ordrer to try to find efficient cutting plane generation strategies with generic mixted integer 0-1 problems and with different solvers. For this study, some solvers were used to compare their when the same cutting planes are added. Two commercial solver (Cplex and Xpress) and one free solveur (Glpk) are used to test the different strategies in a sequential Branch-and-Bound. One free solver is used to test these strategies in a parallel Branch-and-Bound. To provide an easy way to use these different solvers, a free library (Glop) that allows the user to use some solver with a same code has been created. We first present the different cutting plane methods that were integrated in the library Glop to produce computational experimentents. We then turn our interest on the different strategies we implement, the one being fixed strategies, the other being strategies that adapt to the problem resolution. We present and analyse the results of computational experiments with sequential Branch-and-Bound and in the last part, those obtained with parallel Branch-and-Bound
44
Nguyen, Dang Phuong. "Contributions à des problèmes de partitionnement de graphe sous contraintes de ressources". Thesis, Paris 6, 2016. http://www.theses.fr/2016PA066697/document.
Texto completo da fonteResumo:
Le problème de partitionnement de graphe est un problème fondamental en optimisation combinatoire. Le problème revient à décomposer l'ensemble des nœuds d'un graphe en plusieurs sous-ensembles disjoints de nœuds (ou clusters), de sorte que la somme des poids des arêtes dont les extrémités se trouvent dans différents clusters est réduite au minimum. Dans cette thèse, nous étudions le problème de partitionnement de graphes avec des poids (non négatifs) sur les nœuds et un ensemble de contraintes supplémentaires sur les clusters (GPP-SC) précisant que la capacité totale (par exemple, le poids total des nœuds dans un cluster, la capacité totale sur les arêtes ayant au moins une extrémité dans un cluster) de chaque groupe ne doit pas dépasser une limite prédéfinie (appelée limite de capacité). Ceci diffère des variantes du problème de partitionnement de graphe le plus souvent abordées dans la littérature en ce que:_ Le nombre de clusters n'est pas imposé (et fait partie de la solution),_ Les poids des nœuds ne sont pas homogènes.Le sujet de ce travail est motivé par le problème de la répartition des tâches dans les structures multicœurs. Le but est de trouver un placement admissible de toutes les tâches sur les processeurs tout en respectant leur capacité de calcul et de minimiser le volume total de la communication inter-processeur. Ce problème peut être formulé comme un problème de partitionnement de graphe sous contraintes de type sac-à-dos (GPKC) sur des graphes peu denses, un cas particulier de GPP-SC. En outre, dans de telles applications, le cas des incertitudes sur les poids des nœuds (poids qui correspondent par exemple à la durée des tâches) doit être pris en compte.La première contribution de ce travail est de prendre en compte le caractère peu dense des graphes G = (V,E) typiques rencontrés dans nos applications. La plupart des modèles de programmation mathématique existants pour le partitionnement de graphe utilisent O(|V|^3) contraintes métriques pour modéliser les partitions de nœuds et donc supposent implicitement que G est un graphe complet. L'utilisation de ces contraintes métriques dans le cas où G n'est pas complet nécessite l'ajout de contraintes qui peuvent augmenter considérablement la taille du programme. Notre résultat montre que, pour le cas où G est un graphe peu dense, nous pouvons réduire le nombre de contraintes métriques à O(|V||E|) [1], [4]The graph partitioning problem is a fundamental problem in combinatorial optimization. The problem refers to partitioning the set of nodes of an edge weighted graph in several disjoint node subsets (or clusters), so that the sum of the weights of the edges whose end-nodes are in different clusters is minimized. In this thesis, we study the graph partitioning problem on graph with (non negative) node weights with additional set constraints on the clusters (GPP-SC) specifying that the total capacity (e.g. the total node weight, the total capacity over the edges having at least one end-node in the cluster) of each cluster should not exceed a specified limit (called capacity limit). This differs from the variants of graph partitioning problem most commonly addressed in the literature in that:-The number of clusters is not imposed (and is part of the solution),-The weights of the nodes are not homogeneous.The subject of the present work is motivated by the task allocation problem in multicore structures. The goal is to find a feasible placement of all tasks to processors while respecting their computing capacity and minimizing the total volume of interprocessor communication. This problem can be formulated as a graph partitioning problem under knapsack constraints (GPKC) on sparse graphs, a special case of GPP-SC. Moreover, in such applications, the case of uncertain node weights (weights correspond for example to task durations) has to be taken into account.The first contribution of the present work is to take into account the sparsity character of the graph G = (V,E). Most existing mathematical programming models for the graph partitioning problem use O(|V|^3) metric constraints to model the partition of nodes and thus implicitly assume that G is a complete graph. Using these metric constraints in the case where G is not complete requires adding edges and constraints which may greatly increase the size of the program. Our result shows that for the case where G is a sparse graph, we can reduce the number of metric constraints to O(|V||E|).The second contribution of present work is to compute lower bounds for large size graphs. We propose a new programming model for the graph partitioning problem that make use of only O(m) variables. The model contains cycle inequalities and all inequalities related to the paths in the graph to formulate the feasible partitions. Since there are an exponential number of constraints, solving the model needs a separation method to speed up the computation times. We propose such a separation method that use an all pair shortest path algorithm thus is polynomial time. Computational results show that our new model and method can give tight lower bounds for large size graphs of thousands of nodes
45
Nguyen, Dang Phuong. "Contributions à des problèmes de partitionnement de graphe sous contraintes de ressources". Electronic Thesis or Diss., Paris 6, 2016. http://www.theses.fr/2016PA066697.
Texto completo da fonteResumo:
Le problème de partitionnement de graphe est un problème fondamental en optimisation combinatoire. Le problème revient à décomposer l'ensemble des nœuds d'un graphe en plusieurs sous-ensembles disjoints de nœuds (ou clusters), de sorte que la somme des poids des arêtes dont les extrémités se trouvent dans différents clusters est réduite au minimum. Dans cette thèse, nous étudions le problème de partitionnement de graphes avec des poids (non négatifs) sur les nœuds et un ensemble de contraintes supplémentaires sur les clusters (GPP-SC) précisant que la capacité totale (par exemple, le poids total des nœuds dans un cluster, la capacité totale sur les arêtes ayant au moins une extrémité dans un cluster) de chaque groupe ne doit pas dépasser une limite prédéfinie (appelée limite de capacité). Ceci diffère des variantes du problème de partitionnement de graphe le plus souvent abordées dans la littérature en ce que:_ Le nombre de clusters n'est pas imposé (et fait partie de la solution),_ Les poids des nœuds ne sont pas homogènes.Le sujet de ce travail est motivé par le problème de la répartition des tâches dans les structures multicœurs. Le but est de trouver un placement admissible de toutes les tâches sur les processeurs tout en respectant leur capacité de calcul et de minimiser le volume total de la communication inter-processeur. Ce problème peut être formulé comme un problème de partitionnement de graphe sous contraintes de type sac-à-dos (GPKC) sur des graphes peu denses, un cas particulier de GPP-SC. En outre, dans de telles applications, le cas des incertitudes sur les poids des nœuds (poids qui correspondent par exemple à la durée des tâches) doit être pris en compte.La première contribution de ce travail est de prendre en compte le caractère peu dense des graphes G = (V,E) typiques rencontrés dans nos applications. La plupart des modèles de programmation mathématique existants pour le partitionnement de graphe utilisent O(|V|^3) contraintes métriques pour modéliser les partitions de nœuds et donc supposent implicitement que G est un graphe complet. L'utilisation de ces contraintes métriques dans le cas où G n'est pas complet nécessite l'ajout de contraintes qui peuvent augmenter considérablement la taille du programme. Notre résultat montre que, pour le cas où G est un graphe peu dense, nous pouvons réduire le nombre de contraintes métriques à O(|V||E|) [1], [4]The graph partitioning problem is a fundamental problem in combinatorial optimization. The problem refers to partitioning the set of nodes of an edge weighted graph in several disjoint node subsets (or clusters), so that the sum of the weights of the edges whose end-nodes are in different clusters is minimized. In this thesis, we study the graph partitioning problem on graph with (non negative) node weights with additional set constraints on the clusters (GPP-SC) specifying that the total capacity (e.g. the total node weight, the total capacity over the edges having at least one end-node in the cluster) of each cluster should not exceed a specified limit (called capacity limit). This differs from the variants of graph partitioning problem most commonly addressed in the literature in that:-The number of clusters is not imposed (and is part of the solution),-The weights of the nodes are not homogeneous.The subject of the present work is motivated by the task allocation problem in multicore structures. The goal is to find a feasible placement of all tasks to processors while respecting their computing capacity and minimizing the total volume of interprocessor communication. This problem can be formulated as a graph partitioning problem under knapsack constraints (GPKC) on sparse graphs, a special case of GPP-SC. Moreover, in such applications, the case of uncertain node weights (weights correspond for example to task durations) has to be taken into account.The first contribution of the present work is to take into account the sparsity character of the graph G = (V,E). Most existing mathematical programming models for the graph partitioning problem use O(|V|^3) metric constraints to model the partition of nodes and thus implicitly assume that G is a complete graph. Using these metric constraints in the case where G is not complete requires adding edges and constraints which may greatly increase the size of the program. Our result shows that for the case where G is a sparse graph, we can reduce the number of metric constraints to O(|V||E|).The second contribution of present work is to compute lower bounds for large size graphs. We propose a new programming model for the graph partitioning problem that make use of only O(m) variables. The model contains cycle inequalities and all inequalities related to the paths in the graph to formulate the feasible partitions. Since there are an exponential number of constraints, solving the model needs a separation method to speed up the computation times. We propose such a separation method that use an all pair shortest path algorithm thus is polynomial time. Computational results show that our new model and method can give tight lower bounds for large size graphs of thousands of nodes
46
Lucas, Rémi. "Planification adaptative des ressources ferroviaires". Electronic Thesis or Diss., Institut polytechnique de Paris, 2020. https://theses.hal.science/tel-03009036.
Texto completo da fonteResumo:
La planification ferroviaire consiste à établir en amont des circulations un plan de transport spécifiant l’emploi du temps de chaque ressource : les sillons, qui correspondent aux horaires des trains, les matériels roulants devant assurer leur circulation, ainsi que les agents à bord de ces trains. Compte tenu de la complexité du système ferroviaire, cette planification est effectuée potentiellement plusieurs années à l’avance, où un plan de transport précis est établi.Or, une fois qu’une ressource a été planifiée, il est parfois nécessaire d’adapter le plan de transport et donc de le changer. Les raisons peuvent être multiples : changement horaire pour causes de travaux, infrastructure partiellement endommagée, demande d’une rame supplémentaire pour un train, avarie sur un type de matériel roulant… Ainsi, le plan de transport est parfois adapté à plusieurs reprises entre sa conception potentiellement plusieurs années à l’avance et son exécution le jour des circulations. Dès lors, il est légitime de se demander si la conception d’un plan de transport précis avec des échelles de temps aussi importantes est raisonnable.Dans cette thèse, nous envisageons d’ajouter de la flexibilité dans le processus de planification, afin que les efforts déployés pour adapter le plan de transport lorsque cela est nécessaire soient réduits. Nous introduisons la notion de coûts d’adaptation du plan de transport, et nous proposons d’expliciter ces coûts d’adaptation pour le matériel roulant. Nous précisons notamment les coûts d’adaptation structurels, qui permettent de quantifier les similitudes entre deux planifications différentes du matériel roulant. La planification adaptative telle que nous l'envisageons consiste alors à anticiper dès la phase de conception les futures adaptations possibles du plan de transport. Plusieurs modèles de Programmation Linéaire en Nombres Entiers sont introduits et des résultats expérimentaux sont proposés sur des instances réelles issues de SNCF. L'approche de planification adaptative a pu être comparée à l'approche actuelle, et on montre que les coûts d'adaptation du plan de transport peuvent être effectivement réduits en adoptant cette nouvelle façon de planifierRailway planning consists of drawing up a transportation plan before operational time, specifying a planning for each resource: the train paths, which correspond to the schedules, the rolling stock that will be used to move the trains, and the crew on board the trains. Given the complexity of the railway system, this transportation plan is carried out potentially several years in advance, when a precise transportation plan is drawn up.However, once a resource has been planned, it is sometimes necessary to adapt the transportation plan and therefore change it. There may be many reasons for this: schedule changes due to work, partially damaged infrastructure, request for an additional train set for a train, damage to a type of rolling stock, etc. Thus, the transportation plan may sometimes be adapted several times between its design, potentially several years in advance, and its execution on the day of traffic. It is therefore legitimate to ask whether the design of a precise transport plan with such large time scales is reasonable.In this thesis, we consider the adding of flexibility to the planning process so that the effort to adapt the transportation plan when necessary is reduced. We introduce the notion of transportation plan adaptation costs, and we propose to make these adaptation costs explicit for the rolling stock resource. In particular, we specify the structural adaptation costs, which make it possible to quantify the similarities between two different rolling stock plannings. Adaptive planning consists in anticipating possible future adaptations of the transport plan as early as the design phase. Several Integer Linear Programs are introduced and experimental results are proposed on real SNCF instances. The adaptive planning approach can be compared with the current approach, and it is shown that the adaptation costs can be effectively reduced by adopting this new way of planning
47
Morin, Pierre-Antoine. "Planification et ordonnancement de projets sous contraintes de ressources complexes". Thesis, Toulouse 3, 2018. http://www.theses.fr/2018TOU30291/document.
Texto completo da fonteResumo:
La structure de projet se retrouve dans de nombreux contextes de l'industrie et des services. Il s'agit de réaliser un ensemble d'activités pouvant être connectées par des liens logiques de séquence (antériorité), en faisant appel à des ressources disponibles en quantité limitée. L'objectif est la minimisation d'un critère généralement lié à la durée ou au coût du projet. La plupart des problèmes d'ordonnancement de projet dans la littérature considèrent une unité de temps commune pour la détermination des dates d'exécution des activités et pour l'évaluation instantanée du respect des capacités des ressources qu'elles utilisent. Or, s'il est souvent nécessaire en pratique d'obtenir un calendrier détaillé des plages d'exécution des activités, l'utilisation des ressources peut être évaluée sur un horizon plus agrégé, comme par exemple les quarts de travail des employés. Dans cette thèse, un nouveau modèle intégrant ces deux échelles de temps est présenté afin de définir le problème d'ordonnancement de projet avec agrégation périodique des contraintes de ressources (PARCPSP). Ce problème est étudié du point de vue de la théorie de la complexité et des propriétés structurelles sont établies, mettant notamment en évidence des différences majeures avec le problème classique d'ordonnancement de projet sous contraintes de ressources (RCPSP). De ces propriétés sont dérivées des formulations exactes basées sur la programmation linéaire en nombres entiers, comparées en termes de qualité de la relaxation linéaire. Par ailleurs, plusieurs heuristiques, telles que des algorithmes de liste, ou une méthode approchée basée sur une résolution itérative qui exploite différentes échelles de temps, sont proposées. Les résultats expérimentaux montrent l'intérêt de ces différentes méthodes et illustrent la difficulté du problèmeThe project structure arises in many fields of industry and services. It consists in performing a set of activities that may be linked by precedence relations, and use resources whose capacity is limited. The objective is to minimize a criterion usually linked to the duration or the cost of the project. Most of project scheduling problems in the literature assume that the same time scale should be used to determine activity start and completion dates and check resource constraints at each time. However, although it is often required in practice to build a precise schedule specifying the execution range of each activity, the resource usage can be evaluated on an aggregated basis, like worker shifts. In this thesis, a new model that enables the integration of these two time scales is presented in order to define the periodically aggregated resource-constrained project scheduling problem (PARCPSP). This problem is studied within the framework of complexity theory and several structural properties are established, highlighting major differences with the standard resource-constrained project scheduling problem (RCPSP). These properties allow deriving exact formulations based on integer linear programming, whose linear relaxations are compared. Moreover, several heuristics, such as schedule generations schemes, or an approached method based on a multi time scale iterative process, are proposed. Experimental results show the interest of these different methods and point out the intractability of the problem
48
Sun, Xiao Chao. "Résolution de la programmation linéaire en nombres entiers : méthodes des coupes, méthodes de séparation et évaluation et méthodes de décomposition de programmes par matrices d'intervalles et par matrices graphiques". Clermont-Ferrand 2, 1993. http://www.theses.fr/1993CLF21451.
Texto completo da fonteResumo:
1#r#e partie (chapitres 1 a 3): cette partie exploite les proprietes par une demarche de recherche verticale allant de l'etude d'une situation theorique (approximation de hermite sur un cone simple) a l'elaboration et la mise en uvre de methodes iteratives pour la programmation lineaire en nombres entiers. La caracterisation d'une approximation entiere proche d'un sommet realisable non entier permet de definir des coupes particulieres, dites coupes de hermite, qui sont integrees iterativement dans une procedure enumerative, cette derniere etant elle-meme allegee par l'emploi d'une approche de type branch and bound. Utiliser iterativement des directions de recherche generees aleatoirement (objectifs de controle) pour rechercher des solutions entieres dans une couche du polyedre de cout constant. Cette recherche peut a son tour exploiter la forme normale de hermite et integrer les coupes correspondantes dans le polyedre defini a l'iteration suivante. 2#e partie (chapitres 4 a 7): au chapitre iv une methode est proposee pour essayer de reduire les programmes en nombres entiers au cas ou les matrices sont totalement unimodulaires quitte a rajouter un certain nombre de variables de controle (l'interet de la methode se situe quand ce nombre de variables additionnelles est faible). Ceci conduit a etudier aux chapitres suivants les matrices totalement unimodulaires associees aux hypergraphes d'intervalles et aux matrices graphiques. Les resultats obtenus pour ces deux problemes permettent de montrer la pertinence de la methode proposee (theoreme i du chapitre v et theoreme v du chapitre vii)
49
Gugenheim, Dan. "Modélisation et optimisation d’un réseau de transport de gaz". Phd thesis, Toulouse, INPT, 2011. http://oatao.univ-toulouse.fr/11760/1/gugenheim.pdf.
Texto completo da fonteResumo:
Durant ces 40 dernières années, le gaz naturel a vu son utilisation augmenter jusqu’à constituer aujourd’hui la troisième ressource énergétique mondiale. Il est alors devenu nécessaire de l’acheminer sur des distances de plus en plus longues entre les lieux d’extraction et de consommation. Ce transport peut s’effectuer à l’état liquide par des méthaniers ou à l’état gazeux par le biais des réseaux de transport de gaz naturel composés de canalisations de grandes dimensions, tant en diamètre qu’en longueur. Cette thèse porte sur la modélisation et l’optimisation de la configuration des réseaux de transport de gaz naturel et sur l’application au cas du réseau principal de transport français qui présente plusieurs particularités. En effet, il s’agit d’un réseau de grandes dimensions, fortement maillé pour lequel plusieurs sources d’approvisionnement sont possibles pour desservir divers points de consommation. Il possède en outre, des stations d’interconnexion entre les canalisations. GRTgaz en est le gestionnaire. Ce travail concerne l’étude de la faisabilité de configurer le réseau de transport pour un scénario d’approvisionnement et de consommation. Le coeur de cette thèse porte sur le développement d’un modèle de réseau de transport de gaz et sur la détermination des flux et des configurations des stations d’interconnexion dans ce réseau à l’aide d’outils d’optimisation. L’une des innovations est la description et la modélisation des stations d’interconnexion, carrefours incontournables du réseau. Deux modèles sont ainsi proposés, faisant intervenir une formulation d’une part mixte non linéaire en nombres entiers et d’autre part, non linéaire continue. Leur efficacité en fonction de différents solveurs d’optimisation est ensuite discutée. Le choix de la meilleure formulation du problème de transport de gaz naturel a été étudié sur un ensemble de réseaux fictifs, mais représentatifs du réseau français. La meilleure stratégie, basée sur l’utilisation combinée d’une ormulation non linéaire continue, du choix de la pression comme variable et d’une initialisation par un sous-problème a ensuite été appliquée sur des instances de taille réelle. Les difficultés du passage à des instances réelles ont ensuite été résolues à l’aide de deux améliorations: d’une part, la mise à l’échelle des variables a permis de mieux conditionner le problème, puis d’autre part, une suite de relaxations a été employée afin de résoudre tous les cas réels. Les solutions sont finalement validées à l’aide de solutions métiers existantes.
50
Alfonso, Lizarazo Edgar. "Optimisation de la collecte de sang : concilier la qualité de service au donneur de sang et l'efficience de l'organisation de la collecte". Phd thesis, Ecole Nationale Supérieure des Mines de Saint-Etienne, 2013. http://tel.archives-ouvertes.fr/tel-00859974.
Texto completo da fonteResumo:
Les rapports d'activité de l'Établissement Français du Sang (EFS) font état d'une demande croissante de produits sanguins labiles (PSL) tels les concentrés globules rouges (CGR), les plaquettes, et le plasma. Afin d'assurer la demande vitale en PSL, il est primordial d'optimiser la logistique liée aux activités de collecte du sang et de ses composants. Pour faire face à cette situation, l'EFS Auvergne-Loire mène une réflexion dans le but d'utiliser de manière plus efficiente les dispositifs de collecte en sites fixes et mobiles pour améliorer (i) la qualité de service rendue au donneur, et (ii) l'efficience de l'utilisation des ressources humaines. Dans ce contexte nous avons développé dans cette thèse des outils opérationnels pour (i) la modélisation des dispositifs de collecte, (ii) la régulation des flux de donneurs, et (iii) la planification de collectes mobiles.La méthode d'analyse des dispositifs de collecte est basée sur des techniques de simulation à événements discrets. Une modélisation préalable des flux de donneurs dans les systèmes de collecte en sites fixes et mobiles à l'aide de réseaux de Petri a été proposée. Pour la régulation de flux de donneurs, notamment pour la planification optimale des rendez-vous des donneurs et la planification de la capacité dans les systèmes de collecte au site fixe, deux approches ont été abordées: (a) Construction d'un algorithme basée sur techniques d'optimisation stochastique via simulation ; (b) Programmation mathématique: Modèle de programmation en nombres entiers non-linéaire (MINLP) basée sur réseaux de files d'attente et représentation et évaluation des systèmes à événements discrets à travers de programmation mathématique. Pour la planification de collectes mobiles. Deux types de modèles ont été développés : (a) Au niveau tactique : Modèles de programmation en nombres entiers linéaire (MIP) pour planifier les semaines de collectes pour chaque ensemble disponible sur un horizon de temps pour garantir l'autosuffisance à niveau régional des CGR. (b) Au niveau opérationnel : Modèle de programmation en nombres entiers linéaire (MIP) pour l'organisation du travail des équipes en charge de la collecte.