Dissertations / Theses: 'Programmation linéaire aux nombres entiers'

1

Guepet, Julien. "Optimisation de la gestion des avions dans un aéroport : affectation aux points de stationnement, routage au sol et ordonnancement à la piste." Thesis, Université Grenoble Alpes (ComUE), 2015. http://www.theses.fr/2015GREAM030/document.

Full text

Abstract:

Le cadre de cette thèse est l'optimisation des opérations aéroportuaires. Nous nous intéressons à trois problèmes de gestion des avions dans un aéroport : l'affectation aux points de stationnement, le routage au sol entre les pistes et les points de stationnement, et l'ordonnancement des décollages et des atterrissages.Ce travail a été réalisée en collaboration étroite avec la société Amadeus. Nos approches ont été testées et validées avec des données réelles provenant d'aéroports européens.Nous proposons une formulation en Programme Linéaire en Nombres Entiers (PLNE) du problème d'affectation aux points de stationnement. Nous montrons que trouver une affectation réalisable est un problème NP-Complet et nous proposons diverses améliorations visant à réduire le temps de résolution de notre modèle. Nous obtenons ainsi des solutions de meilleure qualité que celles de la littérature, tout en conservant un temps de calcul raisonnable.Le problème de routage au sol est modélisé en adaptant un PLNE de la littérature. Nous montrons que les indicateurs de l'industrie sont en contradiction avec l'objectif de réduction du temps de roulage, et donc des émissions de pollutions. Nous proposons de nouveaux indicateurs basés sur l'heure de décollage, et non sur l'heure de départ du point de stationnement.Enfin, nous nous intéressons à l'intégration de l'ordonnancement à la piste avec le routage au sol. Nous montrons qu'une meilleure intégration permet de réduire le temps de roulage et d'améliorer la gestion de la piste. Nous proposons une heuristique séquentielle basée sur une modélisation en PLNE innovante du problème d'ordonnancement à la piste. Nous montrons que cette heuristique fournit des solutions de bonne qualité en temps raisonnable, contrairement à l'approche exacte de la littérature
In this thesis, we address the optimization of aircraft ground operations at airports, focusing on three main optimization problems: the stand allocation, the ground routing between stands and runways, and the sequencing of take-offs and landings.These works result from a close collaboration with Amadeus. Our approaches have been tested and validated with real data from European airports.The stand allocation problem is formulated as a Mixed Integer Program (MIP). We show that finding an allocation plan respecting operational requirements is NP-Complete and we strengthen our model in several directions. We obtain better solutions than the literature withing reasonable computation times for an industrial application.The ground routing problem is modeled by a MIP formulation adapted from the literature. We show that the main indicators of the industry are in contradiction with the objective of reducing taxi times and therefore air pollution. We propose new indicators based on take-off times instead of push back times.Lastly, we focus on the integration of the runway sequencing with the ground routing. We highlight that a better integration allows to reduce taxi times while improving the management of the runway. We propose a sequential heuristic based on an innovative MIP formulation of the runway sequencing problem. This heuristic is shown to provide high quality solutions in reasonable computation times, unlike the exact approach from the literature

APA, Harvard, Vancouver, ISO, and other styles

2

Loiseau, Irène. "Sur la génération de colonnes en nombres entiers." Paris 13, 2005. http://www.theses.fr/2005PA132018.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

3

Létocart, Lucas. "Problèmes de multicoupe et de multiflot en nombres entiers." Paris, CNAM, 2002. http://www.theses.fr/2002CNAM0430.

Full text

Abstract:

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 anneaux
The 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

APA, Harvard, Vancouver, ISO, and other styles

4

Danna, Emilie. "Intégration des techniques de recherche locale à la programmation linéaire en nombres entiers." Avignon, 2004. http://www.theses.fr/2004AVIG0132.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

5

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.

Full text

Abstract:

À 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).

APA, Harvard, Vancouver, ISO, and other styles

6

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

7

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/.

Full text

Abstract:

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
The 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

APA, Harvard, Vancouver, ISO, and other styles

8

Peschiera, Franco. "Exact and heuristic methods to optimize maintenances and flight schedules of military aircraft." Thesis, Toulouse, ISAE, 2020. http://www.theses.fr/2020ESAE0034.

Full text

Abstract:

Cette thèse étudie le problème de planification de vol et de la maintenancedes avions militaires. D’abord, nous étudions la complexité de ce problème d’optimisation.Puis, nous proposons un modèle de programmation linéaire en nombres entiers (PLNE) pourle résoudre. Nous construisons un générateur d’instances et une heuristique pour générer dessolutions initiales. Ensuite, nous appliquons l’Apprentissage Automatique pour améliorer laperformance des modèles PLNE en utilisant des coupes valides générées à partir des conditionsinitiales et des coupes apprises à partir de la prédiction des caractéristiques de solutionsoptimales. Ces coupes sont appliquées à un nouveau modèle PLNE. Le résultat est une réductiondu temps de résolution avec peu de pertes d’optimalité et de faisabilité par rapport auxméthodes matheuristiques alternatives. Finalement, nous présentons une nouvelle matheuristiquepour résoudre efficacement des grandes instances. La méthode utilise une descente àvoisinage variable qui combine la programmation dynamique (DP) et l’horizon glissant. LaDP exploite une représentation en graphe de l’espace des solutions de chaque avion. Le résultatest des solutions rapides et presque optimales, et un passage à l’échelle efficace pourdes instances de très grande taille
This thesis studies the long term Military Flight and Maintenance Planningproblem. First, we evaluate the complexity of this optimisation problem. Then we propose aMixed Integer Programming (MIP) model to solve it. We develop an instance generator anda heuristic to generate initial solutions. Furthermore, we apply Machine Learning to improvethe performance of the MIP model by using valid cuts generated on the basis of initialconditions and learned cuts based on the prediction of characteristics of optimal solutions.These cuts are applied to a new MIP model. This results in reductions in the solutiontime with little losses in optimality and feasibility in comparison to alternative matheuristicmethods. Finally, we present a new matheuristic to efficiently solve large instances. Themethod employs a Variable Neighborhood Descent that combines Dynamic Programming(DP) and Rolling Horizon neighborhoods. The DP is applied to a graph representation of thesolution space for a single aircraft. This results in fast good quality solutions and an efficientscaling for very large instances

APA, Harvard, Vancouver, ISO, and other styles

9

Dujardin, Yann. "Régulation adaptative multi-objectif et multi-mode aux carrefours à feux." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00904781.

Full text

Abstract:

Afin de répondre à la problématique de la régulation multi-objectif et multi-mode des carrefours à feux, nous proposons trois modèles de programmation linéaire mixte en nombres entiers constituant les moteurs d'un système de régulation pleinement adaptatif, ainsi que deux procédures interactives d'optimisation multi-objectif permettant d'adapter itérativement une "politique de régulation" à la situation de trafic. Les critères pris en compte, tous à minimiser, sont le temps d'attente et le nombre d'arrêts des véhicules particuliers, et un critère dédié aux transports en commun permettant de fixer un temps d'attente souhaité pour chaque bus. Des expérimentations ont montré qu'un des trois modèles, dit hybride, se démarque positivement des deux autres. Ce modèle a alors été mis en œuvre avec une des deux procédures interactives, permettant de contrôler un trafic simulé sur une période d'une heure dans différents scénarios types, et comparé à un système de régulation semi-adaptatif.

APA, Harvard, Vancouver, ISO, and other styles

10

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

11

Wu, Lei. "Contribution à la programmation linéaire en nombres entiers : problèmes de placement-chargement et knapsack." Amiens, 2011. http://www.theses.fr/2011AMIE0112.

Full text

Abstract:

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 taille
This 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

APA, Harvard, Vancouver, ISO, and other styles

12

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

13

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.

Full text

Abstract:

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ées
Multiobjective 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

APA, Harvard, Vancouver, ISO, and other styles

14

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

15

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.

Full text

Abstract:

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
We 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

APA, Harvard, Vancouver, ISO, and other styles

16

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

17

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.

Full text

Abstract:

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ème
This 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

APA, Harvard, Vancouver, ISO, and other styles

18

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.

Full text

Abstract:

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--1
This 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

APA, Harvard, Vancouver, ISO, and other styles

19

Feng, Jianguang. "Modélisation et optimisation des Hoist Scheduling Problems." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLC043/document.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

20

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.

Full text

Abstract:

"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. "

APA, Harvard, Vancouver, ISO, and other styles

21

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Lucas, Rémi. "Planification adaptative des ressources ferroviaires." Electronic Thesis or Diss., Institut polytechnique de Paris, 2020. https://theses.hal.science/tel-03009036.

Full text

Abstract:

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 planifier
Railway 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

APA, Harvard, Vancouver, ISO, and other styles

23

Morin, Pierre-Antoine. "Planification et ordonnancement de projets sous contraintes de ressources complexes." Thesis, Toulouse 3, 2018. http://www.theses.fr/2018TOU30291/document.

Full text

Abstract:

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ème
The 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

APA, Harvard, Vancouver, ISO, and other styles

24

Klopfenstein, Olivier. "Optimisation robuste des réseaux de télécommunication." Compiègne, 2008. http://www.theses.fr/2008COMP1740.

Full text

Abstract:

Cette thèse est consacrée à la prise en compte de données incertaines dans les problèmes d'optimisation. On se concentre sur la programmation mathématique sous contraintes probabilistes, dont le but est de trouver la meilleure solution qui sera réalisable avec une probabilité minimale garantie. Par ailleurs, on s'intéresse à la prise en compte de variables de décisions entières, qui sont souvent requises en pratique. Pour résoudre de tels problèmes combinatoires sous contraintes probabilistes, on s'appuie d'abord sur l'optimisation robuste. Les liens théoriques entre ces deux familles de méthodes sont mis en évidence. A partir de modèles robustes appropriés, des algorithmes de résolution heuristique sont définis. On s'intéresse ensuite à la résolution optimale de problèmes combinatoires sous contraintes probabilistes. Des tests numériques illustrent les méthodes présentées et montrent leur efficacité pratique. Enfin, deux applications au domaine des télécommunications sont développées. Elles concernent toutes deux la localisation de fonctions dans un réseau
This thesis deals with taking uncertain data into account in optimization problems. Our focus is on mathematical programs with chance constraints. In this approach, the goal is to find the best solution, given a unfeasibility probability tolerance. Furthermore, we concentrate on integer variables, since they are often required for practical applications. To solve such chance-constrained combinatorial problems, we first rely on robust optimization. The theoretical links between these two families of approaches are studied. Based on appropriate robust models, solution algorithms to chance-constrained combinatorial problems are designed. Then, the optimal solution of such problems is also investigated. Specific theoretical results and algorithms are given to reach optimality. Finally, two specific telecommuniation applications are developed. Both of them deal with location in a network

APA, Harvard, Vancouver, ISO, and other styles

25

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.

Full text

Abstract:

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)

APA, Harvard, Vancouver, ISO, and other styles

26

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

27

Labbé, Vincent. "Modélisation et apprentissage des préférences appliqués à la recommandation dans les systèmes d'impression." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2009. http://tel.archives-ouvertes.fr/tel-00814267.

Full text

Abstract:

Cette thèse porte sur la modélisation et l'apprentissage automatique des préférences, dans le contexte industriel de l'impression en grand format. En particulier, nous nous intéressons à l'automatisation de la configuration d'impression. De par la palette des comportements possibles, cette fonctionnalité n'est triviale, ni à concevoir, ni à utiliser. Nous proposons une nouvelle approche pour en améliorer les deux aspect complémentaires : évolutivité et utilisabilité. Notre réalisation principale est un système de recommandation adaptatif, basé sur trois contributions originales : une modélisation de la configuration d'impression grand format à partir d'un modèle de préférence, sous la forme de problèmes d'optimisation sous contraintes, un modèle des préférences de l'imprimeur, sous la forme de fonctions d'utilité additive linéaires par morceaux, basée sur une famille d'attributs adaptée, un algorithme d'apprentissage automatique d'ordonnancements à partir de données comparatives. Basé sur l'algorithme rankSVM (noyau linéaire), notre méthode d'apprentissage permet d'adapter la complexité de l'espace de description des données, tout en conservant la linéarité

APA, Harvard, Vancouver, ISO, and other styles

28

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

29

Belmokhtar, Sana. "Lignes d'usinage avec équipements standard : modélisation, configuration et optimisation." Phd thesis, Ecole Nationale Supérieure des Mines de Saint-Etienne, 2006. http://tel.archives-ouvertes.fr/tel-00156570.

Full text

Abstract:

Cette thèse s'inscrit dans le cadre du développement d'outils d'aide à la décision pour la configuration des lignes d'usinage modulaires à partir d'équipements standard. Le problème de configuration se pose en termes de sélection d'un sous-ensemble d'unités d'usinage et de leur affectation aux postes de travail définissant ainsi la structure de la ligne. Le problème revient à trouver la meilleure solution en termes de coût de mise en oeuvre en prenant en compte différents types de contraintes : productivité minimum à assurer, précédence, incompatibilité et capacité de stations et ligne. Le cœur de la thèse est dédié à l'étude des lignes avec un mode d'activation parallèle des unités d'usinage dans les stations. Dans ce cas, le début d'un cycle est marqué par l'enclenchement simultané de toutes les unités d'usinage de la ligne. Pour ce problème, nous avons proposé un modèle générique pour une approche par programmation par contraintes et deux modèles linéaires en nombres entiers.

APA, Harvard, Vancouver, ISO, and other styles

30

Briand, Cyril. "Analyse d'intervalles pour l'ordonnancement d'activités." Habilitation à diriger des recherches, Université Paul Sabatier - Toulouse III, 2009. http://tel.archives-ouvertes.fr/tel-00558925.

Full text

Abstract:

Ce travail s'attache à décrire l'intérêt de l'analyse d'intervalles en ordonnancement. L'analyse d'intervalles considère les relations d'ordres existantes (algèbre de Allen) entres certains intervalles caractéristiques des tâches à ordonnancer. On montre comment, pour certains problèmes particuliers, elle permet de définir des conditions de dominance ou des conditions suffisantes d'optimalité, caractérisant des ensembles remarquables de solutions. Dans le cas de certains problèmes à une machine réputés difficiles, nous montrons comment de telles conditions peuvent être utiles pour déduire des nouvelles formulations de programmation linéaire en nombres entiers très efficaces. De plus, les conditions étant relativement indépendantes des valeurs numériques du problème, on montre aussi leur intérêt pour la caractérisation d'ensembles flexibles et robustes de solutions. D'autres travaux seront également évoqués dans lesquels la notion d'intervalle est centrale.

APA, Harvard, Vancouver, ISO, and other styles

31

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.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

32

Doan, Nhat Linh. "Routage équitable et dimensionnement dans les grands réseaux." Compiègne, 2005. http://www.theses.fr/2005COMP1560.

Full text

Abstract:

Dans cette thèse, nous adressons deux problématiques de nature différente: le problème de routage dans les réseaux de télécommunications et celui des avions dans l'espace aérien. TI s'agit de problèmes fortement inspirés d'applications réelles et qui sont à la fois complexes et de grande taille. Le premier problème concerne le routage max-min équitable des flots élastiques. Le deuxième problème consiste à associer une route et un niveau de vol à chaque avion dans l'espace aérien afin de réduire le nombre des conflits en-route et les délais "enroute" qu'ils induisent. Ces problèmes sont résolus grâce aux modèles de flots basés sur la programmation linéaire avec des techniques avancées telles que la décomposition de Benders et la génération de colonnes
Ln this thesis, we've addressed two routing problems, one in telecommunications networks and the second in air traffic networks. They are usually by complex and large scale optimization problems. The first one concerns the max-min fair routing of elastic flows while the second one is concerned with the route and level flight assignment in air traffie networks. Both problems are solved using flow based network models as weIl as linear programming with advanced techniques such as Bender's decomposition and column generation

APA, Harvard, Vancouver, ISO, and other styles

33

Farah, Ihsen. "Optimisation des flux de trafic aérien." Le Havre, 2013. http://www.theses.fr/2013LEHA0003.

Full text

Abstract:

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ées
In 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

APA, Harvard, Vancouver, ISO, and other styles

34

Bitar, Abdoul. "Ordonnancement sur machines parallèles appliqué à la fabrication de semi-conducteurs : ateliers de photolithographie." Thesis, Saint-Etienne, EMSE, 2015. http://www.theses.fr/2015EMSE0808/document.

Full text

Abstract:

Le secteur des semi-conducteurs a connu un développement considérable ces dernières décennies, du fait des nouvelles applications de la microélectronique dans l'industrie. Le processus de fabrication est réputé pour sa complexité. L'un des ateliers les plus critiques de la production, l'atelier de photolithographie, est régi par un ensemble conséquent de contraintes de production. La multiplicité des ressources utilisées, le nombre important de produits traités, en font une zone importante à optimiser. Les objectifs de la thèse ont été de modéliser cet atelier sous la forme d'un problème d'ordonnancement sur machines parallèles et d'optimiser plusieurs critères jugés pertinents pour évaluer la qualité des solutions. Des résultats en termes de complexité, et d'algorithmes de résolution, ont permis une application industrielle, dans la mesure où un logiciel d'optimisation destiné à l'ordonnancement des lots en photolithographie a été développé
Semiconductor manufacturing has grown considerably in recent decades, due to new industrial applications of microelectronic devices. The related manufacturing process is known to be complex. A bottleneck process step, the photolithography workshop, gathers various types of constraints, related to the number of auxiliary resources and the tools characteristics. The aims of the thesis were to model this workstation as a parallel machine scheduling problem and to optimize various criteria, determined by industrial needs. Some complexity results are provided and optimization algorithms led to an industrial application, i.e. a software providing optimized schedules in a specific fab

APA, Harvard, Vancouver, ISO, and other styles

35

Angilella, Vincent. "Design optimal des réseaux Fiber To The Home." Thesis, Evry, Institut national des télécommunications, 2018. http://www.theses.fr/2018TELE0004/document.

Full text

Abstract:

Pour les opérateurs, les réseaux FTTH représentent à la fois la solution de référence pour répondre à la demande croissante de trafic fixe, et un investissement considérable dû à leur mise en place. Le but de ces travaux est d'assurer le déploiement de réseaux de qualité à moindre coût. Nous commençons à présenter les différents aspects de la planification de ces réseaux qui en font un problème complexe. La littérature concernée est abordée afin d'exhiber les nouveaux défis que nous relevons. Puis nous élaborons des stratégies permettant de trouver la meilleure solution dans différents contextes. Plusieurs politiques de maintenance ou d'utilisation du génie civil sont ainsi explorées. Les problèmes rencontrés sont analysés à la lumière de divers outils d'optimisation (programmation entière, inégalités valides, programmation dynamique, approximations, complexités, inapproximabilité...) que nous utilisons et développons selon nos besoins. Les solutions proposées ont été testées et validées sur des instances réelles, et ont pour but d'être utilisées par Orange
For operators, FTTH networks are the most widespread solution to the increasing traffic demand. Their layout requires a huge investment. The aim of this work is to ensure a cost effective deployment of quality networks. We start by presenting aspects of this network design problem which make it a complex problem. The related literature is reviewed to highlight the novel issues that we solve. Then, we elaborate strategies to find the best solution in different contexts. Several policies regarding maintenance or civil engineering use will be investigated. The problems encountered are tackled using several combinatorial optimization tools (integer programming, valid inequalities, dynamic programming, approximations, complexity theory, inapproximability…) which will be developed according to our needs. The proposed solutions were tested and validated on real-life instances, and are meant to be implemented in a network planning tool from Orange

APA, Harvard, Vancouver, ISO, and other styles

36

Sahraoui, Youcef. "Short-term hydropower production scheduling : feasibility and modeling." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLX025/document.

Full text

Abstract:

Dans le secteur électrique et chez EDF, l'optimisation mathématique est utilisée pour modéliser et résoudre des problèmes de gestion de la production d'électricité.Citons quelques applications : la modélisation des problèmes d'équilibre des marchés, la gestion des risques d'épuisement des barrages, la programmation des arrêts de tranches nucléaires.Plus particulièrement l'hydroélectricté est une énergie renouvelable, peu chère, flexible mais limitée.Exploiter l'hydraulique constitue donc un enjeu important.Nous nous intéressons à des problèmes d'optimisation de Programmation Non Linéaire en Nombres Entiers (PNLNE) dont les variables de décision sont continues ou discrètes et dont les fonctions exprimant l'objectif et les contraintes sont linéaires ou non.Les non-linéarités et la combinatoire induite par les variables entières rendent les PNLNE difficiles à résoudre.En effet les méthodes existantes n'arrivent pas toujours à résoudre les grands PNLNE à l'optimalité avec des temps de calcul limités.En amont des performances de résolution, la faisabilité est une question préliminaire à aborder puisqu'il faut s'assurer que les PNLNE à résoudre admettent des solutions.Lorsqu'il y a des infaisabilités dans des modèles complexes, il est très utile mais très difficile de les analyser.Par ailleurs la résolution de PNLNE est plus difficile si l'on requiert une certification de la précision exacte des résultats.En effet les méthodes résolutions sont en général mises en oeuvre en arithmétique flottante, ce qui peut donner lieu à une précision approchée.Nous abordons deux problèmes d'optimisation liés à la planification de la production hydraulique, Hydro Unit-Commitment (HUC) en Anglais.Etant données des ressources d'eau finies dans les barrages l'objet du HUC est de prescrire des programmes de production les plus rentables qui soient compatibles avec les spécifications techniques des usines hydrauliques.Le volume, le débit et la puissance sont représentés par des variables continues tandis que l'activation des turbines est communément formulée avec des variables binaires.Les non-linéarités proviennent en général des fonctions qui expriment la puissance générée en fonction du volume et du débit.Nous distinguons deux problèmes : un PLNE avec des caractéristiques linéaires et discrètes et un PNL avec des caractéristiques non linéaires et continues.Dans le 2ème chapitre, nous traitons de la faisabilité d'un HUC réel en PLNE.Comparé à un HUC standard le modèle inclut deux spécifications supplémentaires : des points de fonctionnements discrets sur la courbe puissance-débit ainsi que des niveaux cibles pour le volume des réservoirs.Les complications liées aux données réelles et au calcul numérique, associées aux spécifications du modèle rendent notre problème difficile à résoudre et souvent infaisable.Nous procédons par étape pour identifier et traiter les sources d'infaisabilité, à savoir les erreurs numériques et les infaisabilités de modélisation, pour rendre le problème faisable.Des résultats numériques étayent l'efficacité de notre méthode sur un ensemble de test de 66 instances réelles qui contient de nombreuses infaisabilités.Le 3ème chapitre porte sur l'adaptation de l'algorithme Multiplicative Weights Update (MWU) à la PNLNE.Cette adaptation est fondée sur une reformulation paramétrée spécifique dénommée pointwise.Nous définissons des propriétés souhaitables pour obtenir de bonnes reformulations pointwise et nous fournissons des règles pour adapter l'algorithme étape par étape.Nous démontrons que notre matheuristique du MWU conserve une garantie d'approximation relative contrairement à la plupart des heuristiques.Le MWU est comparée à la méthode Multi-Start pour résoudre un HUC en PNL et les résultats numériques penchent en faveur du MWU
In the electricity industry, and more specifically at the French utility company EDF, mathematical optimization is used to model and solve problems related to electricity production management.To name a few applications: planning for capacity investments, managing depletion risks of hydro-reservoirs, scheduling outages and refueling for nuclear plants.More specifically, hydroelectricity is a renewable, cheap, flexible but limited source of energy.Harnessing hydroelectricity is thus critical for electricity production management.We are interested in Mixed-Integer Non-Linear Programming (MINLP) optimization problems.They are optimization problems whose decision variables can be continuous or discrete and the functions to express the objective and constraints can be linear or non-linear.The non-linearities and the combinatorial aspect induced by the integer variables make these problems particularly difficult to solve.Indeed existing methods cannot always solve large MINLP problems to the optimum within limited computational timeframes.Prior to solution performance, feasibility is preliminary challenge to tackle since we want to ensure the MINLP problems to solve admit feasible solutions.When infeasibilities occur in complex models, it is useful but not trivial to analyze their causes.Also, certifying the exactness of the results compounds the difficulty of solving MINLP problems as solution methods are generally implemented in floating-point arithmetic, which may lead to approximate precision.In this thesis, we work on two optimization problems - a Mixed-Integer Linear Program (MILP) and a Non-Linear Program (NLP) - related to Short-Term Hydropower production Scheduling (STHS).Given finite resources of water in reservoirs, the purpose of STHS is to prescribe production schedules with largest payoffs that are compatible with technical specifications of the hydroelectric plants.While water volumes, water flows, and electric powers can be represented with continuous variables, commitment statuses of turbine units usually have to be formulated with binary variables.Non-linearities commonly originate from the Input/Output functions that model generated power according to water volume and water flow.We decide to focus on two distinguished problems: a MILP with linear discrete features and a NLP with non-linear continuous features.In the second chapter, we deal with feasibility issues of a real-world MILP STHS.Compared with a standard STHS problem, the model features two additional specifications:discrete operational points of the power-flow curve and mid-horizon and final strict targets for reservoir levels.Issues affecting real-world data and numerical computing, together with specific model features, make our problem harder to solve and often infeasible.Given real-world instances, we reformulate the model to make the problem feasible.We follow a step-by-step approach to exhibit and cope with one source of infeasility at a time, namely numerical errors and model infeasibilities.Computational results show the effectiveness of the approach on an original test set of 66 real-world instances that demonstrated a high occurrence of infeasibilities.The third chapter is about the transposition of the Multiplicative Weights Update algorithm to the (nonconvex) nonlinear and mixed integer nonlinear programming setting, based on a particular parametrized reformulation of the problem - denoted pointwise.We define desirable properties for deriving pointwise reformulation and provide generic guidelines to transpose the algorithm step-by-step.Unlike most metaheuristics, we show that our MWU metaheuristic still retains a relative approximation guarantee in the NLP and MINLP settings.We benchmark it computationally to solve a hard NLP STHS.We find it compares favorably to the well-known Multi-Start method, which, on the other hand, offers no approximation guarantee

APA, Harvard, Vancouver, ISO, and other styles

37

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

38

Serrano, montero Christian. "Planification et ordonnancement des activités dans un centre de crossdock international." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEM029.

Full text

Abstract:

Afin d’accélérer les flux de produits, de réduire les niveaux de stocks et de faire des économies de transport, les entreprises de presque toutes les industries ont mis en place des centres de crossdock. Ces centres sont un point intermédiaire de consolidation dans une chaîne logistique. Les constructeurs automobiles Renault et Nissan s’appuient sur un réseau international de plateformes crossdock pour lier des fournisseurs de pièces de première monte avec des usines de production lointaines, généralement en outre-mer. Dans un cadre d’un partenariat académique-industriel entre le laboratoire LIMOS et Renault, cette thèse est focalisée sur la planification et l’ordonnancement des activités dans ces centres de crossdock. Des études de terrain menées chez Renault et Nissan nous ont permis d’identifier les caractéristiques, les contraintes et les inducteurs de coûts des plateformes de crossdock, ainsi que de cibler notre revue de la littérature. Sur ces bases, nous proposons une approche d’optimisation séquentielle, comprenant deux modèles en programmation linéaire en nombres entiers, implémentés dans CPLEX et testés sur des données industrielles de deux plateformes Renault. Les résultats des expérimentations obtenus sur le premier modèle (planification) ont montré une nette amélioration en termes de coûts, par rapport à la méthode Renault. Fort de ce constat, une implémentation industrielle a été faite, avec des résultats aussi probants. Le deuxième modèle (ordonnancement) s’avère pertinent pour des instances de moyenne taille. L’approche proposée permet de répondre à la configuration actuelle des AILN Renault et nous considérons qu’elle est adaptable à d’autres industries
In order to accelerate product flow, reduce inventory levels and make economies in transportation, companies in almost all industries have set up cross-dock centres. These centres are an intermediate point of consolidation in a supply chain. Car manufacturers Renault and Nissan rely on an international network of crossdock platforms to link suppliers of OEM parts with overseas production plants. In a framework of an academic-industrial partnership between the LIMOS laboratory and Renault, this thesis focuses on the activity planning and scheduling at these crossdock centres.Field studies conducted at Renault and Nissan allowed us to identify the characteristics, constraints and cost drivers of crossdock platforms, as well as to target our review of the literature. Based on this, we propose a sequential optimization approach, comprising two integer linear programming models, implemented in CPLEX and tested on industrial data of two Renault platforms. Numerical experiments’ results obtained on the first model (planning) showed a significant improvement in cost, compared to the Renault method. In light of this results, an industrial implementation was made, with such convincing results. The second model (scheduling) proved to be relevant for medium-sized instances. The proposed approach fits to the current configuration of AILN Renault and we consider that it is adaptable to other industries

APA, Harvard, Vancouver, ISO, and other styles

39

TOUATI, Sid-Ahmed-Ali. "Méthodes d'optimisations de programmes bas niveau." Habilitation à diriger des recherches, Université de Versailles-Saint Quentin en Yvelines, 2010. http://tel.archives-ouvertes.fr/tel-00665897.

Full text

Abstract:

Ce manuscrit synthétise plus d'une décade de notre recherche académique sur le sujet d'optimisation de codes bas niveau, dont le but est une intégration dans un compilateur optimisant ou dans un outil d'optimisation semi-automatique. Dans les programmes bas niveau, les caractéristiques du processeur sont connues et peuvent être utilisées pour générer des codes plus en harmonie avec le matériel. Nous commençons notre document par une vue générale sur le problème d'ordonnancement des phases de compilation. Actuellement, des centaines d'étapes de compilation et d'optimisation de codes existent; un problème fondamental et ouvert reste de savoir comment les combiner et les ordonner efficacement. Pour pallier rapidement cette difficulté, une stratégie du moindre effort consiste à appliquer une compilation itérative en exécutant successivement le programme avant de décider de la technique d'optimisation de code à employer et avec quels paramètres. Nous prouvons que l'approche de compilation itérative ne simpli fie pas fondamentalement le problème, et l'utilisation de modèles statiques de performances reste un choix raisonnable. Un problème classique de con it entre deux étapes de compilation est celui qui lie l'allocation de registres et l'ordonnancement d'instructions. Nous montrons comment gérer efficacement cet antagonisme en séparant les contraintes de registres des contraintes d'ordonnancement d'instructions. Cela est possible grâce à la notion de saturation en registres (RS), qui est le besoin maximal en registres pour tous les ordonnancements possibles d'un graphe. Nous apportons une contribution formelle et une heuristique efficace, qui permettent la détection de contraintes de registres toujours véri fiées; ils peuvent par conséquent être négligées. Nous introduisons la plate-forme SIRA, qui permet de garantir l'absence de code de vidage avant l'ordonnancement d'instructions. SIRA est un modèle basé sur la théorie des graphes permettant de borner le besoin maximal en registres pour tout pipeline logiciel, sans altérer, si possible, le parallélisme d'instructions. SIRA modélise les contraintes cycliques des registres dans différentes architectures possibles : avec plusieurs types de registres, avec tampons ou les d'attente, et avec des bancs de registres rotatifs. Nous apportons une heuristique efficace qui montre des résultats satisfaisants, que ce soit comme outil indépendant, ou comme passe intégrée dans un vrai compilateur. Dans le contexte des processeurs exhibant des retards d'accès aux registres (VLIW, EPIC, DSP), nous attirons l'attention sur le problème qui peut survenir lorsque les contraintes de registres sont traitées avant l'ordonnancement d'instructions. Ce problème est la création de circuits négatifs ou nuls dans le graphe de dépendances de données. Nous montrons comment éliminer ces circuits indésirables dans le contexte de SIRA. SIRA définit une relation formelle entre le nombre de registres alloués, le parallélisme d'instructions et le facteur de déroulage d'une boucle. Nous nous basons sur cette relation pour écrire un algorithme optimal qui minimise le facteur de déroulage tout en sauvegardant le parallélisme d'instructions et en garantissant l'absence de code de vidage. D'après nos connaissances, ceci est le premier résultat qui démontre que le compactage de la taille de code n'est pas un objectif antagoniste à l'optimisation des performances de code. L'interaction entre la hiérarchie mémoire et le parallélisme d'instructions est un point central si l'on souhaite réduire le coût des latences d'opérations de chargement. Premièrement, notre étude pratique avec des micro-benchmarks montre que les processeurs superscalaires ayant une exécution dans le désordre ont un bug de performances dans leur mécanisme de désambiguation mémoire. Nous montrons ensuite qu'une vectorisation des opérations mémoire résoud ce problème pour des codes réguliers. Deuxièmement, nous étudions l'optimisation de préchargement de données pour des codes VLIW embarqués irréguliers. Finalement, avec l'arrivée des processeurs multicoeurs, nous observons que les temps d'exécution des programmes deviennent très variables. A fin d'améliorer la reproductibilité des résultats expérimentaux, nous avons conçu le Speedup-Test, un protocole statistique rigoureux. Nous nous basons sur des tests statistiques connus (tests de Shapiro-Wilk, F de Fisher, de Student, de Kolmogorov-Smirnov, de Wilcoxon- Mann-Whitney) a n d'évaluer si une accélération observée du temps d'exécution médian ou moyen est signi cative.

APA, Harvard, Vancouver, ISO, and other styles

40

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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

41

Ait, ferhat Dehia. "Conception de solutions exactes pour la fabrication de "vias" en utilisant la technologie DSA." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAM094.

Full text

Abstract:

Maitriser les coûts de fabrication des circuits intégrés tout en augmentant leur densité est d'une importance primordiale pour maintenir une certaine rentabilité dans l’industrie du semi-conducteur. Parmi les différents composants d’un circuit, nous nous intéressons aux connections verticales et métalliques, connues sous le nom de « vias ». Durant la fabrication, un processus de lithographie complexe est utilisé pour former une disposition de vias est formée sur une plaque de silicium, à l’aide d’un un masque optique. Pour des raisons de fabrication, une distance minimum entre les vias doit être respectée. Lorsque cette distance n’est pas respectée, nous parlons de « conflit ». Afin de supprimer ces conflits, l’industrie utilise une technique qui permet de décomposer une disposition de vias cible en plusieurs sous-ensembles, où les contraintes de distance minimum sont respectées : la formation des sous-ensembles individuels se fait en séquence sur la plaque de silicium en utilisant un masque optique par sous-ensemble. Cette technique est appelée Multiple Patterning (MP). Il y a de nombreuses façons de décomposer une disposition de vias et le but est d’assigner les vias à un nombre minimum de masques, car les masques sont coûteux. Minimiser le nombre de masques est équivalent à minimiser le nombre de couleurs dans un graphe disque unitaire. Ce problème est NP-difficile, mais un certain nombre de « bonnes » heuristiques existent. Une technique récente et prometteuse basée sur l’auto-assemblage et direction des molécules, aussi connue sous le nom Directed Self Assembly (DSA), permet de grouper les vias en conflits à condition de respecter certaines contraintes. L’objectif est de trouver la meilleure façon de grouper les vias afin de minimiser le nombre de masques tout en respectant les contraintes liées à DSA. Ce problème est un problème de coloration de graphes où les sommets de chaque couleurs définissent un ensemble de chemins « indépendants » de longueurs au plus k que nous appelons aussi le problème de coloration par k-chemins. Durant la modélisation, nous avons distingué deux problèmes de coloration par k-chemins pertinents: le problème général et le problème induit. Les deux problèmes sont connus pour être NP-difficile, ce qui explique l’utilisation d’heuristiques dans l’industrie pour trouver une décomposition valide en sous-ensembles. Dans cette étude, nous nous intéressons à des méthodes exactes afin de concevoir des solutions optimales et d’évaluer la qualité de l’heuristique développée en industrie (chez Mentor Graphics). Nous présentons différentes méthodes: une approche par programmation linéaire en nombre entier (ILP) où nous étudions plusieurs formulations, une approche par programmation dynamique pour résoudre le cas induit quand k=1 ou k=2 et lorsque les graphes ont une petite longueur arborescente ; enfin, nous étudions le cas particulier des graphes lignes. Les résultats des différentes études numériques montrent que les formulations ILP « naïves » sont les meilleures. Elles listent tous les chemins possibles de longueur au plus k. Les tests sur des données industrielles ayant au plus 2000 sommets (plus grande composante connexe parmi celles qui constituent une instance) ont montré que les deux problèmes, général et induit, sont résolus en moins de 6 secondes, pour k=1 et k=2. La programmation dynamique, appliquée au problème induit de coloration par k-chemins quand k=1 et k=2, montre des résultats équivalents à ceux de la formulation ILP naïve. Cependant, nous nous attendons à de meilleurs résultats par programmation dynamique quand la valeur de k augmente. Enfin, nous montrons qu’un cas particuliers des graphes lignes peut être résolu en temps polynomial en exploitant les propriétés de l’algorithme d'Edmonds et des couplages dans les graphes bipartis
Controlling the manufacturing costs of integrated circuits while increasing their density is of a paramount importance to maintain a certain degree of profitability in the semi-conductor industry. Among various components of a circuit, we are interested in vertical metallic connections known as “vias”. During manufacturing, a complex lithography process is used to form an arrangement of vias on a silicon wafer support, using an optical mask. For manufacturing reasons, a minimum distance between the vias must be respected. Whenever this is not the case, we are talking about a “conflict”. In order to eliminate these conflicts, the industry uses a technique that decomposes an arrangement of vias in several subsets, where minimum distance constraints are respected: the formation of the individual subsets is done, in sequence, on a silicon wafer using one optical mask per subset. This technique is called Multiple Patterning (MP). There are several ways to decompose an arrangement of vias, the goal being to assign the vias to a minimum number of masks, since the masks are expensive. Minimizing the number of masks is equivalent to minimizing the number of colors in a unit disk graph. This is a NP-hard problem however, a number of “good” heuristics exist. A recent and promising technique is based on the direction and self-assembly of the molecules called Directed Self Assembly (DSA), allows to group vias in conflict according to certain conditions. The main challenge is to find the best way of grouping vias to minimize the number of masks while respecting the constraints related to DSA. This problem is a graph coloring problem where the vertices within each color define a set of independent paths of length at most k also called a k-path coloring problem. During the graph modeling, we distinguished two k-path coloring problems: a general problem and an induced problem. Both problems are known to be NP-hard, which explains the use of heuristics in the industry to find a valid decomposition into subsets. In this study, we are interested in exact methods to design optimal solutions and evaluate the quality of heuristics developed in the industry (at Mentor Graphics). We present different methods: an integer linear programming (ILP) approach where we study several formulations, a dynamic programming approach to solve the induced case when k=1 or k=2 and when the graphs have small tree-width; finally, we study a particular case of line graphs. The results of the various numerical studies show that the naïve ILP formulations are the best, they list all possible paths of length at most k. Tests on a snippet of industrial instances of at most 2000 vertices (a largest connected component among those constituting an instance) have shown that the two problems, general and induced, are solved in less than 6 seconds, for k=1 and k=2. Dynamic programming, applied to the induced k-path coloring when k=1 and k=2, shows results equivalent to those of the naïve ILP formulation, but we expect better results by dynamic programming when the value of k increases. Finally, we show that the particular case of line graphs can be solved in polynomial time by exploiting the properties of Edmonds’ algorithm and bipartite matching

APA, Harvard, Vancouver, ISO, and other styles

42

Trilling, Lorraine. "Aide à la décision pour le dimensionnement et le pilotage de ressources humaines mutualisées en milieu hospitalier." Phd thesis, INSA de Lyon, 2006. http://tel.archives-ouvertes.fr/tel-00173007.

Full text

Abstract:

Le regroupement des blocs opératoires au sein d'un Plateau Médico-Technique (PMT) présente des enjeux dans la phase de conception (dimensionnement des ressources et choix d'organisation) et dans la phase de pilotage (planification de l'activité et affectation des ressources humaines et matérielles) face auxquels les décideurs hospitaliers manquent d'outils. En réponse à ces besoins, cette thèse propose une démarche globale d'aide à la décision pour la conception du PMT et le pilotage des ressources humaines mutualisées de ce secteur. Cette démarche aborde trois principaux problèmes. Dans un premier temps, nous nous intéressons à la modélisation des processus de PMT existants, dont le but est de faire émerger un diagnostic et d'engager une démarche d'amélioration de la performance. Ces modèles sont réutilisés dans un second temps pour la modélisation des processus cibles qui nous permettent d'obtenir, par simulation de l'activité, les courbes de charge exprimant les besoins en personnel. Nous abordons la question du dimensionnement du personnel regroupé du PMT par la construction des vacations couvrant cette charge prévisionnelle, à l'aide de la Programmation Linéaire en Nombres Entiers (PLNE) couplée à la simulation de flux. Dans un troisième temps, nous étudions deux problèmes de planication d'horaires de travail : celui des infirmiers anesthésistes et celui des médecins anesthésistes, pour lesquels nous développons plusieurs approches de résolution basées sur la Programmation Linéaire Mixte (PLM) et sur la Programmation Par Contraintes (PPC), expérimentées et validées dans le cadre d'applications réelles.

APA, Harvard, Vancouver, ISO, and other styles

43

Hadj-Hamou, Khaled. "Contribution a la conception de produits a forte diversité et de leur chaine logistique : une approche par contraintes." Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2002. http://tel.archives-ouvertes.fr/tel-00271348.

Full text

Abstract:

Les travaux présentés dans cette thèse portent sur la conception simultanée du produit et de sa chaîne logistique, dans le cas où la demande présente une diversité élevée. Situés entre conception de produit et dimensionnement de chaîne logistique, ces travaux se placent fondamentalement dans le domaine de l'Ingénierie Intégrée ou du Concurrent Engineering. Avec la diversité croissante des produits, cette démarche est rendue nécessaire pour pouvoir concevoir le plus rapidement possible une famille de produits et leur chaîne logistique dans le but de minimiser le coût total de fonctionnement de la chaîne logistique. La première partie de la thèse porte sur l'aide à la conception de produits. Elle présente une démarche multi-phases de préconception et de personnalisation des produits à forte diversité et des outils d'assistance à cette démarche de conception exploitant des modèles génériques à base de connaissances de type propagation et satisfaction des contraintes (modèles CSP). Le résultat de cette démarche est un ensemble de solutions de conception. La seconde partie de la thèse porte sur la conception de réseaux logistiques. Elle présente une approche permettant de sélectionner les solutions produits et de dimensionner la chaîne logistique en s'appuyant sur un modèle de recherche opérationnelle de type programmation linéaire mixte en nombres entiers et dont l'objectif est de minimiser le coût de fonctionnement global de la chaîne logistique. L'application industrielle visée, concernant la conception de systèmes de câblage pour l'industrie automobile est présentée, permettant d'illustrer la démarche proposée.

APA, Harvard, Vancouver, ISO, and other styles

44

Ait, Ouahmed Mohammed Amine. "Optimisation dans l'auto-partage à un seul sens avec voitures électriques et relocalisations." Thesis, Avignon, 2018. http://www.theses.fr/2018AVIG0228/document.

Full text

Abstract:

Cette thèse a pour objectif de modéliser et résoudre des problèmes d’optimisation d’un système d’auto-partage avec des voitures électriques dit « à un seul sens », où les utilisateurs peuvent prendre une voiture dans une station et la laisser ensuite dans une autre. Ce fonctionnement conduit généralement à une situation de déséquilibre dans la répartition des voitures avec certaines stations pleines et d’autres vides. Une des solutions utilisées par les opérateurs d’autopartage pour pallier ce problème est le recours à des agents pour déplacer les voitures selon le besoin. Identifier et répondre à ce besoin est un problème d’optimisation non trivial, notamment à cause de l’usage de véhicules électriques, ce qui engendre des contraintes de rechargement de batteries et d’autonomie. Le problème d’optimisation est décomposé en deux sous-problèmes : le premier est le problème d’affectation des voitures aux clients, ainsi que leurs routages, que nous nommons ROCSP pour Recharging One way Car Sharing Problem ; le second problème est celui du planning des agents et leurs routages que nous nommons ESRP pour Employee Scheduling Routing Problem. 1. Résolution du ROCSP : deux modélisations en Programmation Linéaire en Nombres Entiers (PLNE) sont proposées, la première basée sur les flots et la deuxième sur les chemins, ce qui fait que les deux modèles intègrent de manière différente les contraintes de recharge électrique. Comme la résolution exacte à travers les modèles PLNE s’avère très gourmande en temps de calcul et non adaptée aux instances d’auto-partage de taille réelle, nous proposons des heuristiques qui permettent dans un temps raisonnable d’optimiser la redistribution des voitures et la gestion du service. Ces heuristiques permettent de calculer le nombre de voitures et les différentes opérations de relocalisation (redistribution des voitures) à réaliser sur une journée donnée. 2. Résolution du ESRP : un modèle PLNE est proposé pour la résolution exacte du ESRP, et, en complément, des heuristiques sont proposées pour une résolution approchée et relativement rapide. L’objectif est la détermination du nombre minimal d’agents nécessaire pour effectuer les opérations de relocalisation qui découlent du premier problème, le ROCSP. Dans une partie prospective, et une fois les ROCSP et ESRP résolus dans leur version statique, nous nous focaliserons sur une autre variante du problème avec réservation dynamique. Nous proposons également d’explorer un nouveau concept - l’auto-copartage - qui se veut une hybridation entre autopartage et covoiturage. Les algorithmes proposés ont été validés sur le réseau Auto Bleue de la ville de Nice essentiellement, qui gère une flotte de véhicules électriques, en s’appuyant sur des modèles de génération de flux pour estimer la demande, mais aussi d’autres instances que nous avons générées pour simuler d’autres villes, au sein d’un Système d’Information Géographique
This thesis aims at modelling and solving optimization problems related to the management of one-way-electric-car-sharing systems, where users can take a car from a station, use it, and then return it to another station. This generally leads to an imbalanced distribution of cars, with some full stations and other empty ones. A solution to this problem, implemented by car-sharing operators, is to employ staff agents to move cars as needed. However, identifying this need is a non-trivial optimization problem, especially since the system may be more constrained when the vehicles used are electric, which generates battery recharging and autonomy constraints. The global optimization problem addressed is then divided into two sub-problems. The first one is assigning the cars to customers, as well as their routing; it is denoted by ROCSP (Recharging OneWay Car Sharing Problem). The second problem involves agents planning and routing; it is denoted by ESRP (Employee Scheduling Routing Problem). 1. For the ROCSP, we propose two Mixed-integer linear programming (MILP) modelizations of the problem: One based on flows and the other based on paths. This means that the two models include the battery-recharging constraints in two different ways. As the exact resolution through the MILP models is quite expensive in terms of computational time and is not adapted for the resolution of real-size car-sharing instances, we introduce heuristics that enable the optimization of cars-redistribution and service management of the service within a reasonable amount of time. These heuristics allows the calculation of the number of cars and the various redistribution operations to be performed on a given day. 2. For the ESRP, this second problem is also addressed with MILP models for the exact resolution, and some heuristics are suggested for an approximate resolution. This process has reasonable calculation time and aims at finding the minimum number of agents to perform the necessary relocation operations that stem from the first problem, namely, the ROCSP. Once the ROCSP and ESRP solved in their static versions, we then focus on the ROCSP by exploring another variant of the problem : ROCSP with dynamic reservation. We also suggest to explore a new concept : Auto-CoPartage, which is a hybridization of car-sharing and carpooling. The stated algorithms are validated on the Auto Bleue electrical vehicles fleet in the network of the city of Nice, essentially by relying on flow generation models to estimate the demand, but also using other instances that we have generated for other cities. All the data are handled using a Geographical Information System

APA, Harvard, Vancouver, ISO, and other styles

45

Le, roux Agnès. "Ordonnancement de rendez-vous en tête à tête." Thesis, Nantes, Ecole des Mines, 2014. http://www.theses.fr/2014EMNA0182/document.

Full text

Abstract:

Les problèmes d’ordonnancement de rendez-vous en tête-à-tête sont des problèmes dans lesquels des personnes souhaitent se rencontrer par deux lors de courts rendez-vous qui se déroulent lors d’une session unique. Dans cette thèse, nous référençons plusieurs applications de ce type de problèmes et proposons des notations qui généralisent les notations standards de problèmes d’ordonnancement α|β|γ. Nous nous intéressons en particulier à un cas dans lequel deux populations distinctes se rencontrent, des participants peuvent arriver en retard et des rencontres sont interdites. L’objectif est de minimiser le nombre maximal d’attentes des participants. Nous étudions dans un premier temps la complexité de ces problèmes : nous démontrons que plusieurs cas sans rencontre interdite sont polynomiaux et que le cas général est NP-complet au sens fort. Nous proposons ensuite des bornes inférieures. Puis nous développons plusieurs méthodes de résolution. Des modèles de programmation linéaire en nombres entiers et un modèle de programmation par contraintes sont tout d’abord proposés. Des règles de dominance permettant de limiter les symétries sont intégrées à ces modèles dans le but de limiter l’espace des solutions. Enfin, nous proposons une recherche à divergence limitée (limited discrepancy search) qui est une méthode approchée basée sur l’exploration d’un arbre de recherche tronqué. Dans cette méthode, nous exploitons le plus possible les propriétés de symétrie du problème pour faciliter la convergence vers une bonne solution. Toutes ces méthodes sont testées et comparées sur un ensemble de 300 instances générées aléatoirement d’après des paramètres réalistes
One-to-one meeting scheduling problems are problems where a population of actors want to meet each other during short time slots that take place in a single session. In this thesis, we reference several applications of this type of problems found in the literature and introduce a notation extending the well-known scheduling notation α|β|γ. We are particularly interested in a case in which two distinct populations meet, participants may arrive late and some meetings are forbidden. The objective is to minimize the maximum number of participants waiting slots. First, we study the complexity of these problems: we show that several cases with no forbidden meeting are polynomial and that the general case is NP-complete in the strong sense. We then propose lower bounds. After that, we develop several resolution methods. Integer linear programming models and a constraint programming model are developed. To limit the solution space, we add dominance rules based on symmetries to these methods. Finally, we present a limited discrepancy search (i.e. an approximate method based on the exploration of a truncated tree search). In this method, we use as much as possible the symmetry properties of the problem to facilitate the convergence to a good solution. All these methods are tested and compared on a set of 300 randomly generated instances from realistic parameters

APA, Harvard, Vancouver, ISO, and other styles

46

Essafi, Mohamed. "Conception et optimisation d'allocation de ressources dans les lignes d'usinage reconfigurables." Phd thesis, Ecole Nationale Supérieure des Mines de Saint-Etienne, 2010. http://tel.archives-ouvertes.fr/tel-00669980.

Full text

Abstract:

Les travaux de cette thèse concernent la conception et l'optimisation de lignes de transfert reconfigurables. L'objectif principal est de concevoir une ligne d'usinage à moindre coût tout en respectant les contraintes techniques, technologiques et économiques du problème. Le problème d'optimisation correspondant est un problème d'équilibrage de lignes d'usinage sujet à des contraintes spécifiques. Il consiste à affecter les opérations aux stations de travail en minimisant les coûts d'installation. En plus des contraintes habituelles de ce type de problème, à savoir, les contraintes de précédence, d'inclusion et d'exclusion, nous avons dû considérer des contraintes d'accessibilité. De plus, la spécificité principale des lignes reconfigurables par rapport aux lignes de transfert dédiées, vient de la réalisation en série des opérations. Celle-ci rend souvent nécessaire la mise en place de stations équipées de plusieurs centres d'usinage travaillant en parallèle pour obtenir les volumes de production souhaités. Enfin, l'utilisation d'une tête d'usinage mono-broche induit la prise en compte de temps inter-opératoire de déplacements et de changement d'outils qui dépendent de la séquence d'opérations. Dans un premier temps, nous avons proposé une modélisation mathématique du problème à l'aide d'un programme linéaire en nombres mixtes. Nous avons aussi développé des méthodes de calcul de bornes inférieures ainsi qu'une procédure de prétraitement. Cependant, les contraintes additionnelles rendent la résolution du problème d'équilibrage plus difficile que dans le cas des lignes dédiées, et l'approche proposée ne permet généralement pas de résoudre des instances de taille industrielle. Pour répondre à ce besoin, nous avons donc développé plusieurs méthodes de résolution approchées du problème en nous inspirant de métaheuristiques efficaces sur des problèmes d'optimisation combinatoire.

APA, Harvard, Vancouver, ISO, and other styles

47

Hannachi, Marwa. "Placement des tâches matérielles de tailles variables sur des architectures reconfigurables dynamiquement et partiellement." Thesis, Université de Lorraine, 2017. http://www.theses.fr/2017LORR0297/document.

Full text

Abstract:

Les systèmes adaptatifs basés sur les architectures FPGA (Field-Programmable Gate Arrays) peuvent bénéficier grandement de la grande flexibilité offerte par la reconfiguration partielle dynamique (DPR). Grâce au DPR, les tâches matérielles composant un système adaptatif peuvent être allouées et re-allouées à la demande ou en fonction de l'environnement dynamique. Les flots de conceptions disponibles et les outils commerciaux ont évolué pour répondre aux exigences des architectures reconfigurables qui sont toutefois limitées dans leurs fonctionnalités. Ces outils ne permettent pas un placement et une relocation efficaces de tâches matérielles de tailles variables. L'objectif principal de ces travaux de thèse consiste à proposer des nouvelles méthodologies et de nouvelles approches pour faciliter au concepteur la phase de conception d'un système adaptatif reconfigurable opérationnelle, valide, optimisé et adapté aux changements dynamiques de l'environnement. La première contribution de cette thèse porte sur la problématique de la relocation des tâches matérielles de tailles différentes. Une méthodologie de conception est proposée pour répondre à un problème majeur des mécanismes de relogement : le stockage d'une unique bitstream de configuration pour réduire les besoins de la mémoire et pour accroître la réutilisable des modules matériels générés. Une technique de partitionnement de la région reconfigurable est appliquée dans la méthodologie de relogement proposée pour augmenter l'efficacité d'utilisation des ressources matérielles dans le cas des tâches reconfigurables de tailles variables. Cette méthodologie prend en compte aussi la communication entre différentes régions reconfigurables et la région statique. Pour valider la méthode, plusieurs études de cas sont implémentées. Cette validation montre une utilisation efficace des ressources matérielles ainsi une réduction importante du temps de reconfiguration. La deuxième partie de cette thèse présente et détaille une formulation mathématique afin d'automatiser le floorplanning des zones reconfigurables dans les FPGAs. Les algorithmes de recherche présentés dans cette thèse sont basés sur la technique d'optimisation PLMNE (programmation linéaire mixte en nombres entiers). Ces algorithmes permettent de définir automatiquement l'emplacement, la taille et la forme de la zone reconfigurable dynamique. Nous nous intéressons principalement dans cette recherche à la satisfaction des contraintes de placement des zones reconfigurables et celles liées à la relocation. De plus, nous considérons l’optimisation des ressources matérielles dans le FPGA en tenant compte des tâches de tailles variables. Finalement, une évaluation de l'approche proposée est présentée
Adaptive systems based on Field-Programmable Gate Arrays (FPGA) architectures can benefit greatly from the high degree of flexibility offered by dynamic partial reconfiguration (DPR). Thanks to DPR, hardware tasks composing an adaptive system can be allocated and relocated on demand or depending on the dynamically changing environment. Existing design flows and commercial tools have evolved to meet the requirements of reconfigurables architectures, but that are limited in functionality. These tools do not allow an efficient placement and relocation of variable-sized hardware tasks. The main objective of this thesis is to propose a new methodology and a new approaches to facilitate to the designers the design phase of an adaptive and reconfigurable system and to make it operational, valid, optimized and adapted to dynamic changes in the environment. The first contribution of this thesis deals with the issues of relocation of variable-sized hardware tasks. A design methodology is proposed to address a major problem of relocation mechanisms: storing a single configuration bitstream to reduce memory requirements and increasing the reusability of generating hardware modules. A reconfigurable region partitioning technique is applied in this proposed relocation methodology to increase the efficiency of use of hardware resources in the case of reconfigurable tasks of variable sizes. This methodology also takes into account communication between different reconfigurable regions and the static region. To validate the design method, several cases studies are implemented. This validation shows an efficient use of hardware resources and a significant reduction in reconfiguration time. The second part of this thesis presents and details a mathematical formulations in order to automate the floorplanning of the reconfigurable regions in the FPGAs. The algorithms presented in this thesis are based on the optimization technique MILP (mixed integer linear programming). These algorithms allow to define automatically the location, the size and the shape of the dynamic reconfigurable region. We are mainly interested in this research to satisfy the constraints of placement of the reconfigurable zones and those related to the relocation. In addition, we consider the optimization of the hardware resources in the FPGA taking into account the tasks of variable sizes. Finally, an evaluation of the proposed approach is presented

APA, Harvard, Vancouver, ISO, and other styles

48

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.

Full text

Abstract:

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 5
This 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

APA, Harvard, Vancouver, ISO, and other styles

49

Mkadem, Mohamed Amine. "Flow-shop with time delays, linear modeling and exact solution approaches." Thesis, Compiègne, 2017. http://www.theses.fr/2017COMP2390/document.

Full text

Abstract:

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 efficaces
In 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

APA, Harvard, Vancouver, ISO, and other styles

50

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.

Full text

Abstract:

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 partie
The 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

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Programmation linéaire aux nombres entiers'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles