Dissertations / Theses: 'Optimisation combinatoire et linéaire'

1

Ben, Messaoud Saïd. "Caractérisation, modélisation et algorithmes pour des problèmes de découpe guillotine." Troyes, 2004. http://www.theses.fr/2004TROY0006.

Full text

Abstract:

Le travail de recherche réalisé dans cette thèse concerne le domaine de placement et de découpe à deux dimensions avec prise en compte de la contrainte guillotine. Jusqu'à présent, dans la littérature, aucune définition mathématique de la contrainte guillotine n'a été donnée. L'objet de cette thèse est de caractériser et modéliser formellement la contrainte guillotine et proposer des algorithmes pour résoudre différents problèmes de découpe à deux dimensions. Nous proposons une condition nécessaire et suffisante pour caractériser une configuration guillotine. Ce résultat constitue la base d'un algorithme polynomial permettant de vérifier si une configuration données est guillotine. Cette caractérisation est ensuite exploitée pour mettre au point un modèle linéaire pour le problème de découpe guillotine sur bande. Par la suite, nous étudions le problème de découpe sur bande. Ce problème consiste à placer un ensemble de pièces rectangulairs sur une bande de largeur fixe et de hauteur supposée infinie tout en respectant la contrainte guillotine avec pour objectif la minimisation de la hauteur utilisée. Deux heuristiques constructives sont proposées et ont été testées sur un grand nombre d'instances. L'originalité réside dans la façon de remplir les couches et de déterminer leurs hauteurs. Dans la dernière partie, nous traitons un problème de découpe sur un ensemble de plaques de largeur identique. Une des heuristiques proposées précédement a été généralisée pour résoudre ce problème. L'approche a été testée sur un grand nombre d'instances
This thesis focuses on a two-dimensional cutting stock problem where guillotine constraint is required. Despite the fact that guillotine constraint was introduced at the very beginning of the cutting stock and bin packing research, no mathematical definition has been given. Then the purpose of the thesis is to characterize and model the guillotine constraint and to propose efficient algorithms to solve variants of the two-dimensional cutting stock. We first give a necessary and sufficient condition for a cutting pattern to be guillotine. And consequently we propose a polynomial algorithm to check this condition for any given pattern. Then we give a linear program that describes explicitly the guillotine constraint by means of the previous condition. Thereafter, we are interested in strip packing problem which consists of packing rectangular items of predetermined sizes into a strip of fixed width and infinite height. The aim is to find cutting pattern that minimizes the total height used and where guillotine constraint is required. Two constructive heuristics are proposed and tested on a great number of instances. The originality lies in the way of filling the shelves and of determining their heights. In the last part, we deal with a variant of the two-dimensional cutting stock, in which, we have an infinite number of rectangular sheets of raw material having identical width. The aim is to cut off a given set of items while minimizing the waste. One of the heuristics proposed previously was generalized and tested on a great number of instances

APA, Harvard, Vancouver, ISO, and other styles

2

Hamiez, Jean-Philippe. "Coloration de graphes et planification de rencontres sportives : heuristiques, algorithmes et analyses." Angers, 2002. http://www.theses.fr/2002ANGE0053.

Full text

Abstract:

Les métaheuristiques sont une source d'inspiration inépuisable pour la résolution efficace de problèmes combinatoires. Nos travaux sur la coloration de graphes et un problème de planification le confirment. Nous avons ainsi développé les premières adaptations de la recherche dispersée pour la coloration et de la recherche tabou pour le problème de planification. Nos résultats rejoignent les meilleurs publiés. Nous avons aussi analysé des solutions du problème de coloration. Nos analyses ont révélé que certains ensembles de sommets sont représentatifs des solutions. Cette information nous a permis, non seulement de caractériser la diversité des solutions, mais aussi d'améliorer un algorithme tabou. Concernant la planification, différentes propriétés de la configuration initiale utilisée par notre algorithme tabou ont été exploitées pour développer, dans un premier temps, une approche de réparation exhaustive. Nos résultats dépassent largement ceux des meilleures approches connues malgré une complexité exponentielle. Pour tenter de diminuer cette complexité, nous avons, là encore, observé les solutions, et les choix effectués pour y parvenir. Cela a été profitable puisque nous avons conçu le premier algorithme à complexité linéaire pour résoudre le problème.

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

Przybylski, Anthony. "Méthode en deux phases pour la résolution exacte de problèmes d'optimisation combinatoire comportant plusieurs objectifs : nouveaux développements et application au problème d'affectation linéaire." Nantes, 2006. http://www.theses.fr/2006NANT2123.

Full text

Abstract:

Dans ce travail, nous nous intéressons à la résolution exacte de problèmes d'optimisation combinatoire multi-objectif par la méthode en deux phases. Pour cela, nous utilisons le problème d'affectation comme support de nos investigations. La méthode en deux phases est un cadre de résolution général qui a été popularisé par Ulungu en 1993 avec comme idée centrale d'exploiter la structure spécifique des problèmes d'optimisation combinatoire pour leur résolution dans un contexte multi-objectif. Elle a depuis été appliquée sur un grand nombre de problèmes, en se limitant toutefois au contexte bi-objectif. Nous apportons des affinements à cette méthode et à son application au problème d'affectation bi-objectif. En particulier, nous proposons des bornes supérieures améliorées et l'utilisation d'un algorithme de ranking comme principale routine pour la seconde phase de la méthode. Nous proposons ensuite une généralisation de cette méthode au contexte multi-objectif, qui est réalisée en deux temps. Pour la première phase, une analyse de la décomposition de l'ensemble des poids en correspondance avec les points supportés extrêmes, nous permet de mettre en évidence une notion d'adjacence géométrique entre ces points, et une condition d'exhaustivité sur leur énumération. La seconde phase consiste en la définition et l'exploration de régions dans lesquelles des énumérations sont nécessaires afin d'achever la résolution du problème. Notre solution repose essentiellement sur une description appropriée de ces régions qui en permet une exploration par analogie avec le cas bi-objectif, et permet donc la réutilisation de stratégies d'exploration existantes pour ce contexte. Les résultats expérimentaux sur le problème d'affectation tri-objectif attestent de l'efficacité de la méthode
The purpose of this work is the exact solution of multi-objective combinatorial optimisation problems with the two phase method. For this, we use assignment problem as a support for our investigations. The two phase method is a general solving scheme that has been popularized by Ulungu in 1993. The main idea of this method is to exploit the specific structure of combinatorial optimisation problems in a multi-objective context. It has been applied to a number of problems, with a limitation on the bi-objective case. We present improvements in this method and in its application to the bi-objective assignment problem. In particular, we propose improved upper bounds and the use of a ranking algorithm as main routine in the second phase of the method. We propose next a generalisation of this method to the multi-objective case, done in two steps. For the first phase, we analyse the weight set decomposition in correspondance with the nondominated extreme points. This allows us to highlight a geometric notion of adjacency between these points and an optimality condition on their enumeration. The second phase consists in the definition and the exploration of the area inside of which enumerations are required to finalize the resolution to the problem. Our solution is based primarily on an appropriate description of this area, that allows to explore it by analogy with the bi-objective case. It is therefore possible to reuse a strategy developped for this case. Experimental results on three-objective assignment problem show the efficiency of the method

APA, Harvard, Vancouver, ISO, and other styles

5

Gioan, Emeric. "Correspondance naturelle entre bases et réorientations des matroïdes orientés." Bordeaux 1, 2002. http://www.theses.fr/2002BOR12641.

Full text

Abstract:

Dans un matroi͏̈de orienté ordonné, on définit et on étudie, de façons intrinsèque et constructive, une correspondance naturelle entre les bases et les réorientations, préservant les activités énumérées par le polynôme de Tutte. Elle a de fortes propriétés de dualité, et géométriques, et peut-être construite inductivement via les mineurs relatifs au plus grand élément, ou via une décomposition en mineurs d'activités (1,0). Dans un graphe on obtient des bijections actives entre arbres couvrants et classes d'orientations, ou orientations acycliques avec unique puits fixé, ou avec unique puits et unique source adjacents fixés. Géométriquement, on obtient en général des extensions de la programmation linéaire combinatoire, selon l'ordre total des éléments : chaque réorientation est décomposée en régions bornées de mineurs du matroi͏̈de orienté et de son dual, et pour celles-ci on optimise une suite de faces emboîtées pour une suite de fonctions objectives.

APA, Harvard, Vancouver, ISO, and other styles

6

Lalande, Jean-François. "Conception de réseaux de télécommunications : optimisation et expérimentations." Phd thesis, Université de Nice Sophia-Antipolis, 2004. http://tel.archives-ouvertes.fr/tel-00008012.

Full text

Abstract:

Dans cette thèse, nous nous intéressons aux problèmes d'optimisation dans les réseaux de télécommunication. Un premier objectif consiste à identifier les problèmes spécifiques aux réseaux optiques et satellitaires, et à présenter des contributions pour l'optimisation des ressources de ces réseaux. Le second objectif est de présenter une contribution logicielle pour la conception et l'optimisation de réseaux.

La première partie débute par la présentation des réseaux optiques WDM. Nous abordons ensuite les modèles pour les réseaux optiques et satellitaires et proposons des méthodes algorithmiques nouvelles pour optimiser l'allocation des ressources de ces réseaux. Nous traitons ainsi le problème du routage, du groupage et de la protection des réseaux WDM successivement dans trois chapitres puis nous nous intéressons à un algorithme dédié à l'allocation de fréquences dans les réseaux satellitaires. Enfin, pour chaque problème, nous présentons des résultats expérimentaux sur des instances de réseaux réels.

La deuxième partie de cette thèse présente les développements logiciels qui ont été entrepris. Le premier chapitre présente le logiciel Porto dédié à la résolution de problèmes de routage, groupage et protection dans des réseaux optiques utilisant trois niveaux de brassage. Dans un second chapitre nous présentons le logiciel Mascopt, une bibliothèque d'optimisation pour le domaine des graphes et des réseaux qui a servi notamment à réaliser les expérimentations présentées dans la première partie.

APA, Harvard, Vancouver, ISO, and other styles

7

Roupin, Frédéric. "Algorithmes Combinatoires et Relaxations par Programmation Linéaire et Semidéfinie. Application à la Résolution de Problèmes Quadratiques et d'Optimisation dans les Graphes." Habilitation à diriger des recherches, Université Paris-Nord - Paris XIII, 2006. http://tel.archives-ouvertes.fr/tel-00596215.

Full text

Abstract:

Cette synthèse de travaux de recherche concerne l'algorithmique dans les graphes et l'utilisation de la pro- grammation linéaire et semidéfinie positive (SDP) dans le cadre de la résolution exacte ou approchée de plusieurs problèmes fondamentaux de l'Optimisation Combinatoire. L'approche semidéfinie, qui conduit à des relaxations convexes mais non-linéaires, a permis d'obtenir de remarquables résultats théoriques en approximation et devient à présent utilisable en pratique (tout comme la programmation linéaire qui en est un cas particulier). Nos travaux comportent une forte composante algorithmique et des études de complexité de plusieurs problèmes d'optimisation dans les graphes. Nous considérons tout d'abord le problème de la recherche d'un sous-graphe dense de taille fixée pour lequel nous présentons un algorithme polynomial avec ga- ranties de performances fondé sur la programmation linéaire et quadratique. Puis, nous étudions les problèmes de multiflots entiers et de multicoupes pour lesquels nous avons identifié de nombreux cas po- lynomiaux dans des graphes particuliers importants en pratique : arborescences, grilles, anneaux. D'une part, les solutions fractionnaires fournies par certaines relaxations linéaires de ces problèmes sont le point de départ d'algorithmes de résolution efficaces. D'autre part, les propriétés des programmes linéaires uti- lisés nous permettent également d'élaborer des algorithmes purement combinatoires et de démontrer leur validité (matrices totalement unimodulaires, théorème des écarts complémentaires). Nous proposons également des approches systématiques pour élaborer des relaxations semidéfinies pour les programmes quadratiques, modèles de très nombreux problèmes combinatoires et continus. Plus précisément, nous étudions les liens entre relaxations semidéfinies et des relaxations lagrangiennes partielles de programmes quadratiques contenant des contraintes linéaires. En particulier, les fonctions quadratiques constantes sur une variété affine sont entièrement caractérisées. Ceci permet de facilement comparer les différentes familles de contraintes redondantes proposées dans la littérature dans l'approche semidéfinie dans le cadre unifié de l'approche lagrangienne. Puis, nous présentons un algorithme pour élaborer des relaxations semidéfinies à partir de relaxations linéaires existantes. L'objectif est de pro- fiter des résultats théoriques et expérimentaux obtenus dans l'approche linéaire. Nous avons développé un logiciel (SDP_S) grâce à ces résultats. Il permet de formuler automatiquement et facilement des relaxations semidéfinies pour tout problème pouvant être formulé comme un programme quadratique en variables bivalentes. Notre méthode peut se généraliser à certains programmes à variables mixtes. Enfin, nous appliquons les méthodes décrites précédemment à une série de problèmes combinatoires classiques. Nos expérimentations montrent que l'approche semidéfinie est à présent pertinente dans la pra- tique sous certaines conditions. Premièrement, nous présentons des méthodes de séparation/évaluation efficaces fondées sur la SDP pour la résolution exacte des problèmes max 2sat et Vertex-Cover. Deuxièmement, nous proposons plusieurs bornes par SDP de grande qualité pour des problèmes particu- lièrement difficiles à résoudre par les approches linéaires : k-cluster, CMAP (un problème de placement de tâches avec contraintes de ressources), et le problème de l'affectation quadratique (QAP). Pour ce dernier nous présentons également un algorithme de coupes performant fondé sur la programmation semidéfinie. Afin d'obtenir des algorithmes efficaces en pratique, nous mettons en oeuvre non seulement nos méthodes d'élaboration de relaxations SDP, mais également des techniques algorithmiques issues de l'approximation polynomiale, ainsi que des outils spécifiques de résolution numérique des programmes semidéfinis.

APA, Harvard, Vancouver, ISO, and other styles

8

Mancel, Catherine. "Modélisation et résolution de problèmes d'optimisation combinatoire issus d'applications spatiales." Toulouse, INSA, 2004. http://www.theses.fr/2004ISAT0011.

Full text

Abstract:

Nos travaux portent sur la modélisation et la résolution de problèmes d'optimisation combinatoire émergeant dans le cadre de la planification de missions spatiales. Ces problèmes de grande taille présentent des caractéristiques communes en termes de types de données, de contraintes et de critères à optimiser. Nous nous focalisons sur l'apport de la programmation linéaire pour ces problèmes, associée à des méthodes de simplification de l'espace de recherche, par décomposition ou grâce à des techniques de propagation de contraintes. Nous avons plus particulièrement étudié deux problèmes. Le premier concerne la planification de communications sonde/satellite et d'expériences dans un projet d'exploration martienne. Une décomposition de ce problème permet de le formuler comme deux problèmes indépendants : un problème de planification des communications que nous modélisons par un programme linéaire en nombres entiers et que nous résolvons de façon exacte par un algorithme classique, et un problème d'aide à la décision pour la planification des expériences, pour lequel nous établissons des courbes d'évaluation de la charge des ressources, déduites de l'application de techniques de propagation de contraintes basées sur un raisonnement énergétique. Le second problème étudié est celui de la planifiacation de prises de vue d'un satellite d'observation de la Terre. Nous proposons un modèle linéaire en variables mixtes et nous développons une approche de résolution par génération de colonnes, qui est une adaptation de la programmation linéaire au traitement de problèmes de grande taille, faisant appel à certaines techniques de décomposition des modèles
In this work we are concerned with combinatorial optimization problems stemming from space missions planning. These huge problems have some common features concerning the type of data, constraints and criteria to be optimized. We focus on linear programming for modeling and solving these problems, associated to methods for search space simplification, using decomposition or some constraint propagation techniques. We more particularly address two problems. The first one concerns a mission which aims at a scientific investigation of Mars. It consists in planning both communication slots between martian probes and a satellite, and experiments on probes. We use linear integer programming to model and solve to optimality the sub-problem of communication slots planning, and we develop an decision-aid oriented method using constraint propagation for experiments planning. The second problem occurs in the context of the french program of Earth observing with satellites. It consists in selecting and scheduling images taken by one satellite in order to maximize a quality criterion. We give a linear model and we propose a column generation approach, based on the Dantzig-Wolfe decomposition of the model, to calculate upper bounds for this problem and in order to solve it

APA, Harvard, Vancouver, ISO, and other styles

9

Segura, Jean-Mathieu. "Localisation et affectation : application aux réseaux de contenus." Paris 6, 2011. http://www.theses.fr/2011PA066054.

Full text

Abstract:

Sur le réseau Internet, les usagers demandent un accès de plus en plus rapide à des contenus de plus en plus volumineux. Notamment, le service de Vidéo à la Demande (VoD) voit la taille des données échangées augmenter fortement avec l'arrivée de la haute définition et des vidéos en 3D. Les réseaux physiques des fournisseurs d’accès à Internet doivent ainsi sans cesse s'adapter à l'augmentation des demandes de téléchargements. La solution qui a pendant longtemps consisté à augmenter les débits en posant de nouveaux câbles connaît aujourd'hui ses limites. Une nouvelle approche efficace consiste à déployer des réseaux de distribution de contenus (CDN) qui peuvent être décrits comme un ensemble d'équipements, appelés caches, où les données sont dupliquées et stockées au plus proche des utilisateurs. Lors de la conception d'un CDN, plusieurs questions se posent quant au nombre, à la dimension et la localisation des caches, de manière à servir au mieux l'usager. En nous plaçant du point de vue d'un fournisseur d'accès à Internet, nous montrons que la conception d'un service de VoD s'inscrit dans la problématique de localisation et d'affectation de ressources en recherche opérationnelle. En particulier, nous nous intéressons à deux problèmes mêlant localisation et affectation: le problème du 2-p-Médian et le problème de Location-Dispatching. Nous montrons que, dans le cas où le réseau considéré est un arbre, le premier problème est polynomial. Nous formulons le second problème comme un programme linéaire en nombre entiers et nous proposons une étude polyédrale du polytope associé, ainsi que de nouvelles inégalités valides. A partir de cette étude, nous déduisons un algorithme de coupes et branchements pour résoudre le problème. Nous proposons également de nouvelles formulations entières de problèmes de localisation et d'affectation et nous comparons expérimentalement leurs efficacités. En conclusion nous tentons de répondre aux questions posées par la conception de CDN à partir des différentes approches étudiées dans ce document.

APA, Harvard, Vancouver, ISO, and other styles

10

Haouari, Mohamed. "Les problèmes de tournées avec fenêtres de temps, modélisation et algorithmes de résolution exacte et heuristique." Châtenay-Malabry, Ecole centrale de Paris, 1991. http://www.theses.fr/1991ECAP0183.

Full text

Abstract:

Cette thèse présente une nouvelle heuristique en deux phases pour le PTVFT. Des tests empiriques montrent que cdette heuristique est très efficace. De même, plusieurs variantes du PTVFT sont résolues d'une manière exacte grâce à l'approche de génération de colonnes. La taille et la complexité des problèmes résolus dépasse nettement celle des algorithmes déjà publié dans la littérature scientifique.

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

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

13

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

14

Dodin, Pierre. "Contrôle de l'information par optimisation sur les graphes géodétiques et contrôle de l'allocation dans le cadre des systèmes de capteurs délocalisés." Paris 6, 2003. http://www.theses.fr/2003PA066096.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Lesca, Julien. "Exploitation de fonctions d'agrégation dépendant du rang pour la décision multi-objectifs : procédures d'optimisation et mécanismes incitatifs." Paris 6, 2013. http://www.theses.fr/2013PA066127.

Full text

Abstract:

La recherche de solutions équilibrées dans des problèmes multi-objectifs est un des enjeux majeurs de problématiques comme la décision multi-critères, multi-agents ou la décision dans l'incertain. La structure des problèmes sur lesquels portent cette recherche peut être combinatoire ou continue, et rendre impossible la comparaison paire à paire des différentes solutions pour évaluer la meilleure d'entre elles. Les travaux de cette thèse tente d'apporter une réponse algorithmique à cette question, en proposant des approches par programmation mathématique et par programmation dynamique pour la recherche de solutions optimales dans des problèmes multi-objectifs combinatoires et continus. Des modèles de décision sous la forme de fonctions d'agrégation dépendant du rang sont considérés dans cette thèse pour comparer les solutions entre elles. Nous étudions en particulier la résolution de programmes linéaires et mixtes, où la fonction objectif est définie comme une intégrale de Choquet sur un ensemble d'objectifs. Nous traitons ensuite de la recherche de solutions robustes dans des problèmes de décision dans l'incertain où la vraisemblance des évènements est définie sous la forme de polyèdre de probabilités possibles (modèle multi-prior). Nous consacrons aussi un chapitre à la recherche de chemins Choquet-optimaux, et nous proposons des règles de dominance pour des algorithmes de programmation dynamique, qui vont permettre d'accélérer la résolution en supprimant de la recherche des sous-chemins qui ne peuvent pas mener à des solutions optimales. Enfin, nous aborderons le thème des mécanismes incitatifs pour des procédures de décision multi-agents, lorsque des modèles de décision complexes comme l'intégrale de Choquet sont utilisés
The search for well-balanced solutions in multiobjective problems is a major issue in decision-making under uncertainty, multicriteria or multiagent decision-making. The problem's structure where this search takes place can be combinatorial or continuous and in both cases, the enumeration of solutions is impossible. This thesis work intends to give an algorithmic answer to this question by providing mathematical programming and dynamic programming approaches to find optimal solutions when the aggregating function is the Choquet integral, one of the most expressive aggregator. This thesis provides also a mechanism design analysis of multiagent problems where the aggregating function is non-affine as it is the case for the Choquet integral

APA, Harvard, Vancouver, ISO, and other styles

16

Sirdey, Renaud. "Modèles et algorithmes pour la reconfiguration de systèmes répartis utilisés en téléphonie cellulaire." Phd thesis, Université de Technologie de Compiègne, 2007. http://tel.archives-ouvertes.fr/tel-00189425.

Full text

Abstract:

Ce travail de thèse de doctorat traite de l'étude d'un problème d'ordonnancement NP-difficile au sens fort à contraintes de ressource : le problème de la programmation des déplacements de processus. Ce problème, issu de l'industrie des télécommunications, est lié à l'opérabilité de certains systèmes temps réel répartis à haute disponibilité tels le BSCe3, un autocommutateur pour la téléphonie cellulaire commercialisé par Nortel.
En quelques mots, ce problème consiste, étant donnée une répartition arbitraire admissible de processus sur les processeurs d'un système réparti, à trouver une séquence d'opérations (migrations de processus sans effet sur le service ou arrêts temporaires) de moindre impact par le biais de laquelle une autre répartition arbitraire, et fixée à l'avance, peut être obtenue. La principale contrainte réside dans le fait que la capacité des processeurs du système ne doit pas être dépassée durant la reconfiguration.
Nous avons abordé ce problème d'ordonnancement sous différents angles. Tout d'abord, nous avons établi son caractère NP-difficile au sens fort et exhibé quelques cas particuliers polynomiaux. Puis, sur le plan de la résolution exacte dans le cas général, nous avons conçu deux algorithmes de recherche arborescente : le premier trouve ses fondements dans l'étude de la structure combinatoire du problème, le second dans des considérations polyédrales. De nombreux résultats expérimentaux illustrent la pertinence pratique de ces deux algorithmes. Enfin, en raison des contraintes imposées par le caractère temps réel de notre application industrielle, nous avons mis au point un algorithme efficace de résolution approchée basé sur la métaheuristique du recuit simulé et, en capitalisant sur nos travaux en résolution exacte, empiriquement vérifié sa capacité pratique à produire des solutions acceptables, en un sens bien défini.

APA, Harvard, Vancouver, ISO, and other styles

17

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

18

Roux, Antoine. "Etude d’un code correcteur linéaire pour le canal à effacements de paquets et optimisation par comptage de forêts et calcul modulaire." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS337.

Full text

Abstract:

La transmission fiable de données sur un canal de transmission est un problème récurrent en Informatique. En effet, quel que soit le canal de transmission employé, on observe obligatoirement de la détérioration de l’information transmise, voire sa perte pure et simple. Afin de palier à ce problème, plusieurs solutions ont été apportées, notamment via l’emploi de codes correcteurs. Dans cette thèse, nous étudions un code correcteur développé en 2014 et 2015 pour l’entreprise Thales durant ma deuxième année de Master en apprentissage. Il s’agit d’un code actuellement utilisé par Thales pour fiabiliser une transmission UDP passant par un dispositif réseau, l’Elips-SD. L’Elips-SD est une diode réseau qu’on place sur une fibre optique et qui garantit physiquement que la transmission est unidirectionnelle. Le cas d’utilisation principal de cette diode est de permettre le suivi de la production d’un site sensible, ou encore de superviser son fonctionnement, tout en garantissant à ce site une protection face aux intrusions extérieures. A l’opposé, un autre cas d’utilisation est la transmission de données depuis un ou plusieurs sites non-sécurisés vers un site sécurisé, dont on souhaite s’assurer qu’aucune information ne pourra par la suite fuiter. Le code correcteur que nous étudions est un code correcteur linéaire pour le canal à effacements de paquets, qui a reçu la certification OTAN de la Direction Générale des Armées. Nous l’avons babtisé "Fauxtraut", anagramme de "Fast algorithm using Xor to repair altered unidirectionnal transmissions". Afin d’étudier ce code correcteur, de présenter son fonctionnement et ses performances, et les différentes modifications apportées durant cette thèse, nous établissons tout d’abord un état de l’art des codes correcteurs, en nous concentrant principalement sur les codes linéaires non-MDS, tels que les codes LDPC. Puis nous présentons le fonctionnement de Fauxtraut, et analysons son comportement (complexité, consommation mémoire, performances) par la théorie et par des simulations. Enfin, nous présenterons différentes versions de ce code correcteur développées durant cette thèse, qui aboutissent à d’autres cas d’utilisation, tels que la transmission d’information sur un canal unidirectionnel à erreurs ou sur un canal bidirectionnel, à l’image de ce que permet de faire le protocole H-ARQ. Dans cette partie, nous étudierons notamment le comportement de notre code correcteur via la théorie des graphes : calculer la probabilité de décoder convenablement ou non revient à connaître la probabilité d’apparition de cycles dans le sous-graphe de graphes particuliers, les graphes de Rook et les graphes bipartis complets. Le problème s’énonce simplement et s’avère compliqué, et nous espérons qu’il saura intéresser des chercheurs du domaine. Nous présentons une méthode permettant de calculer exactement cette probabilité pour de petits graphes (qui aboutit à un certain nombre de formules closes), et une fonction tendant asymptotiquement vers cette probabilité pour de plus grands graphes. Nous étudierons aussi la manière de paramétrer automatiquement notre code correcteur par le calcul modulaire et la combinatoire, utilisant la fonction de Landau, qui retourne un ensemble de nombres entiers dont la somme est fixée et le plus commun multiple est maximal. Dans une dernière partie, nous présentons un travail effectué durant cette thèse ayant conduit à une publication dans la revue Theoretical Computer Science. Il concerne un problème non-polynomial de la théorie des graphes : le couplage maximal dans les graphes temporels. Cet article propose notamment deux algorithmes de complexité polynomiale : un algorithme de 2-approximation et un algorithme de kernelisation pour ce problème. L’algorithme de 2- approximation peut notamment être utilisé de manière incrémentale : arêtes du flot de liens nous parviennent les unes après les autres, et on construit la 2-approximation au fur et à mesure de leur arrivée
Reliably transmitting information over a transmission channel is a recurrent problem in Informatic Sciences. Whatever may be the channel used to transmit information, we automatically observe erasure of this information, or pure loss. Different solutions can be used to solve this problem, using forward error correction codes is one of them. In this thesis, we study a corrector code developped in 2014 and 2015 for Thales society during my second year of master of apprenticeship. It is currently used to ensure the reliability of a transmission based on the UDP protocole, and passing by a network diode, Elips-SD. Elip-SD is an optical diode that can be plugged on an optical fiber to physically ensure that the transmission is unidirectional. The main usecase of such a diode is to enable supervising a critical site, while ensuring that no information can be transmitted to this site. At the opposite, another usecase is the transmission from one or multiple unsecured emitters to one secured receiver who wants to ensure that no information can be robbed. The corrector code that we present is a linear corrector code for the binary erasure channel using packets, that obtained the NATO certification from the DGA ("Direction Générale de Armées" in French). We named it Fauxtraut, for "Fast algorithm using Xor to repair altered unidirectional transmissions". In order to study this code, presenting how it works, its performance and the modifications we added during this thesis, we first establish a state of the art of forward error correction, focusing on non-MDS linear codes such as LDPC codes. Then we present Fauxtraut behavior, and analyse it theorically and with simulations. Finally, we present different versions of this code that were developped during this thesis, leading to other usecases such as transmitting reliable information that can be altered instead of being erased, or on a bidirectionnal channel, such as the H-ARQ protocole, and different results on the number of cycles in particular graphs. In the last part, we present results that we obtained during this thesis and that finally lead to an article in the Technical Computer Science. It concerns a non-polynomial problema of Graphs theorie : maximum matching in temporal graphs. In this article, we propose two algorithms with polynomial complexity : a 2-approximation algorithm and a kernelisation algorithm forthis problema

APA, Harvard, Vancouver, ISO, and other styles

19

Nguyen, Quang Thuan. "Approches locales et globales basées sur la programmation DC et DCA pour des problèmes combinatoires en variables mixtes 0-1 : applications à la planification opérationnelle." Electronic Thesis or Diss., Metz, 2010. http://www.theses.fr/2010METZ037S.

Full text

Abstract:

Cette thèse développe les deux approches locales et globales basées sur la programmation DC et DCA pour l'optimisation combinatoire en variables mixtes 0-1 et leurs applications à la résolution de nombreux problèmes en planification opérationnelle. Plus particulièrement, cette thèse adresse à: l'amélioration de l'algorithme d'approximation extérieure basée sur DCA (appelé DCACUT) introduit par Nguyen V.V. et Le Thi pour la programmation linéaire en variables mixtes 0-1, les combinaisons des algorithmes globaux et DCA et l'étude numérique comparative de ces approches pour la programmation linéaire en variables mixtes 0-1, l'utilisation de DCA à la résolution de la programmation DC en variables mixtes 0-1 en utilisant la pénalité exacte, la mise en œuvre des algorithmes développés à la résolution des problèmes de grande taille en planification opérationnelle comme les problèmes dans le réseau de télécommunication sans fils, les problèmes d’ordonnancement ainsi que le problème d'affectation de tâches des véhicules aériens non pilotés ou bien le problème des tournées de véhicules dans une chaîne d'approvisionnement
This thesis develops two local and global approaches based on DC programming and DCA for mixed 0-1 combinatorial optimization and their applications to many problems in operational planning. More particularly, this thesis consists of: the improvement of the outer approximation algorithm based on DCA (called DCACUT) introduced by Nguyen V.V and Le Thi for mixed 0-1 linear programming, the combinations of global algorithms and DCA and the comparative numerical study of these approaches for mixed 0-1 linear programming, the use of DCA for solving mixed 0-1 programming via an exact penalty technique, the implementation of the algorithms developed for solving large scale problems in operational planning: two problems in wireless telecommunication network, two scheduling problems, an UAV task assignment problem and an inventory routing problem in supply chains

APA, Harvard, Vancouver, ISO, and other styles

20

Meunier, Frédéric. "Pleins étiquetages et configurations équilibrées : aspects topologiques de l'Optimisation Combinatoire." Phd thesis, Université Joseph Fourier (Grenoble), 2006. http://tel.archives-ouvertes.fr/tel-00136938.

Full text

Abstract:

Cette thèse traite principalement des contreparties combinatoires et constructives de certains théorèmes d'optimisation combinatoire qui font appel à des outils de topologie algébrique. Des généralisations des lemmes de Sperner et des formules combinatoires de Ky Fan sont proposées, ainsi que des applications à la coloration des graphes de Kneser et au célèbre problème du partage équitable du collier. Un problème d'ordonnancement lié à ce dernier problème est également abordé. Enfin, le dernier chapitre contient des résultats nouveaux pour les sigma-jeux (jeux de lampes) sur la grille.

APA, Harvard, Vancouver, ISO, and other styles

21

Rivano, Hervé. "Algorithmique et télécommunications : Coloration et multiflot approchés et applications aux réseaux d'infrastructure." Phd thesis, Université de Nice Sophia-Antipolis, 2003. http://tel.archives-ouvertes.fr/tel-00169842.

Full text

Abstract:

Cette thèse s'intéresse aux problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux d'infrastructure de télécommunication. L'optimisation de ces réseaux est essentielle aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées.

Nous donnons une nouvelle modélisation des réseaux optiques WDM multifibres. En considérant un routage agrégé au niveau des câbles, nous optons pour une nouvelle lecture des contraintes d'affectation de longueurs d'onde fondée sur des conflits de groupe.

Nous étudions aussi le problème de coloration de chemins, issu de l'affectation de longueurs d'onde dans les réseaux optiques monofibres. Nous développons, pour la relaxation linéaire de ce problème, un algorithme polynomial efficace dans les arbres de degré borné, puis, par extension, dans les graphes de largeur arborescente bornée. Nous majorons le coût d'une telle coloration dans les arbres binaires et donnons une (1+5/(3e)+o(1))-approximation aléatoire pour la coloration entière dans les arbres de degré borné, ce qui améliore le meilleur algorithme connu pour ce cas.

Nous présentons enfin des avancées algorithmiques pour les problèmes de multiflot entier et fractionnaire. Nous donnons un algorithme d'arrondi aléatoire incrémental pour l'approximation du multiflot entier. Motivés par le besoin d'un calcul rapide de multiflot fractionnaire pour l'algorithme précédent, nous nous intéressons aux approximations combinatoires de ce problème. En employant des techniques de calcul dynamique des plus courts chemins, nous améliorons l'un des meilleurs algorithme de la littérature.
Webstats4U - Free web site statistics

APA, Harvard, Vancouver, ISO, and other styles

22

Gaoua, Yacine. "Modèles mathématiques et techniques d’optimisation non linéaire et combinatoire pour la gestion d’énergie d’un système multi-source : vers une implantation temps-réel pour différentes structures électriques de véhicules hybrides." Thesis, Toulouse, INPT, 2014. http://www.theses.fr/2014INPT0124/document.

Full text

Abstract:

La gestion de la distribution de l’énergie électrique dans un système multi-source (véhicule hybride électrique) est primordiale. Elle permet d’augmenter les performances du système en minimisant la consommation de combustible utilisée par la source principale, tout en respectant la demande et les différentes contraintes de fonctionnement de la chaîne énergétique et de sécurité du système. Dans cette thèse, dans le cas où le profil de mission est connu, une approche combinatoire est proposée en modélisant le problème de gestion d’énergie sous la forme d’un problème d’optimisation avec satisfaction des contraintes. Celui-ci est résolu par une méthode exacte issue de la recherche opérationnelle, conduisant à des solutions optimales en des temps de calcul fortement réduits en comparaison avec ceux obtenus par l’application de la programmation dynamique ou la commande optimale. Pour éprouver la sensibilité aux perturbations, une étude de robustesse est menée sur la base de l’analyse de la solution de pire-cas d’un scénario sur des profils de mission d’un véhicule. Les cas pratiques d’utilisation imposent de ne connaître la demande du moteur électrique qu’à l’instant présent, selon le mode de conduite du chauffeur. Afin de gérer l’énergie du véhicule en temps réel, un algorithme en ligne, basé sur une approche de type floue, est développé. Pour mesurer la qualité de la solution floue obtenue, une étude de performance est réalisée (recherche de l’optimum global), en ayant recours à une optimisation hors-ligne sur des profils de mission de référence, basée sur une modélisation non linéaire du problème de gestion d’énergie. Les résultats obtenus ont permis de valider la qualité de la solution floue résultante
Managing the distribution of electrical energy in a multi-source system (hybrid electric vehicle) is paramount. It increases the system performance by minimizing the fuel used by the primary source, while respecting demand, the differents operating constraints of the energy chain and system security. In this thesis, where the mission profile is known, a combinatorial approach is proposed by modeling the problem of energy management as an optimization problem with constraint satisfaction. The problem is solved using an exact method from operations research, leading to optimal solutions with reduced computation time in comparison with those obtained by applying dynamic programming or optimal control strategies. To test the perturbation sensitivity, robustness study is conducted, based on the analysis of the worst-case solution of the worst scenario, which can be achieved on the vehicle mission profile. In practical cases, the vehicle demand is unknown, and we have only the information about the instantaneous demand, which depends on driving style of the driver. In order to manage on line the energy of the vehicle, an on-line algorithm, based on a fuzzy approach is developed. To measure the quality of the fuzzy solution obtained, a performance study is carried out (finding the optimum solution), using an off-line optimization under reference mission profiles, based on non-linear modeling of the power management problem. The results were used to validate the quality of the resulting fuzzy solution

APA, Harvard, Vancouver, ISO, and other styles

23

Lardeux, Benoît. "Conception de réseaux de télécommunications multicouche et évolutif." Compiègne, 2005. http://www.theses.fr/2005COMP1576.

Full text

Abstract:

Dans ce document sont abordés des problèmes complexes d'optimisation dans les télécommunications. La problématique étudiée concerne le dimensionnement de réseaux en fonction des demandes de trafic. L'écoulement de ces demandes dans le réseau étant modélisé par un multiflot, il s'agit de déterminer des valeurs de capacités modulaires nécessaires à installer sur les liens pour un coût global minimal. Les coûts des combinaisons de modules de capacité pouvant être installées sont modélisés par des fonctions croissantes en escalier quelconques. Deux problèmes de dimensionnement de réseaux étendus, intéressants dans le contexte actuel d'évolution des télécommunications, ont été étudiés: le problème multicouche pour lequel nous cherchons à optimiser le dimensionnement de plusieurs couches de réseau encapsulées les unes dans les autres et le problème multipériode qui consiste à déterminer l'évolution de l'architecture et du dimensionnement en fonction de l'évolution du trafic au cours d'une période de temps donnée
Ln this thesis we focus on two complex optimization problems in telecommunication networks, the multi-Iayered and the multi'-period network design problems. The main issue studied here concerns the network design problem given a matrix of traffic demands. Traffic demands are carried simultaneously in the network, and we intend to compute the best available capacity values to install on the links at a minimal global cost. The costs of the capacity commodities combinations available on the links are modeled by general step increasing cost functions. Two extensive network design problems interesting under the CUITent context of expansion in telecommunications are thoroughly studied: the multi-Iayered and the multi-period network design problems. For the first problem, we propose a method for the design of a network built on several encapsulated layers. Ln the second part of this thesis, we tackle the problem of the topologyand dimensionning evolution given the traffic growing throughout a given horizon time

APA, Harvard, Vancouver, ISO, and other styles

24

Chauvin, Alan. "Contribution à l'optimisation globale pour le dimensionnement et la gestion d'énergie de véhicules hybrides électriques basée sur une approche combinatoire." Thesis, Lyon, INSA, 2015. http://www.theses.fr/2015ISAL0101/document.

Full text

Abstract:

L'hybridation des sources de puissance dans le domaine des applications embarquées s'est imposée comme une solution adéquate pour répondre aux législations environnementales et atteindre une meilleure efficacité énergétique. Toutefois, le choix dans le dimensionnement des composants et la stratégie de commande doivent répondre à un cahier des charges, souvent complexe et hétérogène, tout en limitant les coûts du système. La résolution de ce problème d'optimisation incluant de nombreuses variables peut s'avérer complexe à cause des non-linéarités présentes dans le problème formulé. Il faut donc disposer d'outils de résolution efficaces et capables de fournir une solution fiable. Dans cette thèse, nous proposons une méthode d'optimisation globale pour le dimensionnement et la commande optimale de véhicules hybrides basée sur l'optimisation combinatoire, et en particulier sur la programmation linéaire en nombres entiers (PLNE). A partir d'un problème d'optimisation non linéaire, le problème initial est reformulé en une multitude de sous-problèmes linéaires en nombres entiers sur lesquels un algorithme de Branch & Bound parallèle est exécuté. Afin de résoudre des problèmes de grande taille, un second algorithme basé sur le Branch & Cut est développé. Cette méthode est déployée pour l'étude d'un système d'alimentation hybride d'une mini-excavatrice électrique. Le problème d'optimisation, dans lequel des contraintes énergétiques et des contraintes de vieillissement sont implantées, est évalué suivant différents paramètres du cahier des charges. Enfin, cette approche est également appliquée pour l'optimisation de trajectoires d'un système multi-actionneur synchronisés
Hybridization of power sources for embedded applications becomes an interesting solution to respect environmental legislation and achieve a higher energy efficiency. However, the choice for components sizing and the energy management strategy need to meet specifications while reducing costs. To solve this optimization problems including several types of variables can be complex because of non linearities included in the formulated problem. Therefore the use of effective solving tools, able to provide a reliable solution, is required. In this thesis, a global optimization method is proposed for the design and the optimal control of hybrid vehicles based on combinatorial optimization, particularly on integer linear programming. From a non-linear optimization problem, the initial problem is reformulated into a multitude of integer linear sub-problems for which a parallel Branch & Bound algorithm is executed. In order to solve large-scale problems, a second algorithm based on the Branch & Cut is developed. This method is used for the study of a hybrid power supply system of a mini-excavator electric. The optimization problem, where energy constraints and aging constraints are implemented, is evaluated according to several parameters and specifications. Finally, this approach is also applied for the optimization of trajectories for a synchronized multi-actuators system

APA, Harvard, Vancouver, ISO, and other styles

25

Louat, Christophe. "Etude et mise en œuvre de stratégies de coupes efficaces pour des problèmes entiers mixtes 0-1." Versailles-St Quentin en Yvelines, 2009. http://www.theses.fr/2009VERS0060.

Full text

Abstract:

Pour cette étude, plusieurs solveurs ont été utilisés afin de comparer leurs comportement quand des mêmes coupes sont ajoutées. Deux solveurs commerciaux (Cplex et Xpress) et un solveur libre (Glpk) ont été utilisés pour faire des tests avec un Branch-and-Bound Séquentiel. Un solveur libre (Bob++) a été utilisé pour réaliser des tests avec un Branch-and-Bound parallèle. Afin de faciliter l’utilisation des différents solveurs en ne faisant qu’un seul code a été créé. Nous présentons tout d’abord les différentes méthodes de coupes qui ont été intégrées à la librairie Glop pour réaliser des expérimentations. Nous montrons ensuite les différentes stratégies implémentées les unes étant des stratégies fixes, les autres des stratégies qui s’adaptent au déroulement de la résolution du problème. Nous présentons et analysons les résultats des exécutions réalisées avec un Branch-and-Bound séquentiel et enfin ceux des exécutions réalisé avec un Branch-and-Bound parallèle
The use of cutting planes is since severals years one of the most used methods to improve the search of an optimal solution reducing the search space in a Branch-and-Bound. The work presented here aims at studying several cutting plane methods and at proposing some strategies to integrate them in a resolution method based on Branch-and-Bound algorithm to solve mixed integer 0-1 problems. We present extensive computational experiments in ordrer to try to find efficient cutting plane generation strategies with generic mixted integer 0-1 problems and with different solvers. For this study, some solvers were used to compare their when the same cutting planes are added. Two commercial solver (Cplex and Xpress) and one free solveur (Glpk) are used to test the different strategies in a sequential Branch-and-Bound. One free solver is used to test these strategies in a parallel Branch-and-Bound. To provide an easy way to use these different solvers, a free library (Glop) that allows the user to use some solver with a same code has been created. We first present the different cutting plane methods that were integrated in the library Glop to produce computational experimentents. We then turn our interest on the different strategies we implement, the one being fixed strategies, the other being strategies that adapt to the problem resolution. We present and analyse the results of computational experiments with sequential Branch-and-Bound and in the last part, those obtained with parallel Branch-and-Bound

APA, Harvard, Vancouver, ISO, and other styles

26

Mertz, Théophile. "Optimisation simultanée de la configuration et du dimensionnement des réseaux de chaleur urbains." Thesis, Pau, 2016. http://www.theses.fr/2016PAUU3019/document.

Full text

Abstract:

L’objectif de ces travaux est de développer une méthode d’aide à la conception des réseaux de chaleur urbains (RCU). Cette méthode utilise un modèle de type MINLP (Mixed Integer Non Linear Programming) pour l’optimisation simultanée de la configuration et du dimensionnement d’un RCU. Aux variables continues pour l’aide au dimensionnement (température, vitesse, diamètre, aire des échangeurs), s’ajoutent des variables binaires aidant à définir la configuration du réseau (maillage et choix des technologies). La fonction objectif à minimiser est le coût total (capex et opex), qui est soumise à un ensemble de contraintes non linéaires (p. ex. pertes thermiques et de charge, bilans). La méthode développée dans ce manuscrit offre la possibilité de connecter en cascade des consommateurs n’ayant pas les mêmes besoins en température, et de réaliser des réseaux bouclés (une canalisation par tranchée). Elle permet aussi de choisir : les consommateurs à connecter au RCU, le ou les sites de production ainsi que le type de technologie utilisée. Enfin la bonne prise en compte de la physique permet de choisir le meilleur compromis entre pertes thermiques et pertes de charge, sur une large gamme de température. Cette formulation permet donc d’optimiser des réseaux de 4éme génération et de démontrer la rentabilité de l’intégration d’EnR&R sur le long terme (30 ans). Un premier travail est réalisé afin de proposer une méthodologie de résolution en plusieurs étapes permettant l’obtention de l’optimum global. Différents cas d’études académiques sont utilisés pour présenter les intérêts multiples de cette formulation. Enfin la comparaison avec un réseau existant a permis de démontrer la cohérence des résultats du modèle et a servi de base pour l’optimisation d’un cas d’étude de grande dimension. Plusieurs études de sensibilité post-optimale sont réalisées afin de démontrer l’intérêt de cet outil pour l’aide à la conception initiale ou l’extension de RCU existants
The aim of this thesis is to develop a method that provides design assistance for District Heating Network (DHN). This tool allows simultaneously the optimization of the configuration and its sizing, thanks to an MINLP formulation (Mixed Integer Non-Linear Programming). Binary variables help to choose the optimal configuration (network layout and technologies of production), whereas continuous variables help DHN sizing (temperature, diameter, velocity, heat exchanger area, thermal generating capacity …). The objective function to minimize is the total cost (capex and opex), subjected to numerous nonlinear constraints (e.g. thermal losses, pressure drop, energy balance).This method enables to design temperature cascade between consumers, when consumer temperature requirements are different, and also looped network (only one pipe in one trench). It helps also the decision to connect (or not) consumers to the main network and also the location(s) and type(s) of the heating plant. Moreover, the arbitrage between heat losses and pressure drops is taken into account thanks to physical considerations (non-linear equations). Eventually, it is possible to design 4th generation DHN and prove their financial profitability over the long terms (30 years). First a multi-step resolution strategy is proposed to ensure finding global optimum of the complex MINLP problem. Then academic study cases are analyzed to underline the numerous assets of the formulation. Finally, the optimal design compared to an existing DHN ensures the consistency of the method and allows to build a study case at a wider scale, which can be solved thanks to the comprehensive strategy developed. The design assistance method is available for initial design as well as for extension of existing DHN

APA, Harvard, Vancouver, ISO, and other styles

27

Ouzia, Hacène. "Hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1 : théorie et applications." Paris 6, 2008. http://www.theses.fr/2008PA066349.

Full text

Abstract:

Dans cette thèse, nous abordons les liens entre diverses hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1. Parmi celles-ci, citons la hiérarchie de Sherali-Adams (S&A) et la hiérarchie Lift-and-Project (L&P). Tout d’abord, nous montrons que la hiérarchie L&P est semi-algébrique. Puis, nous introduisons une nouvelle hiérarchie de relaxations semi-algébriques, dite SRL*, intermédiaire entre les hiérarchies S&A et L&P. Nous examinons les liens entre les hiérarchies L&P et SRL*. Nous aborderons comment renforcer la description linéaire d’une relaxation L&P pour qu’elle coïncide avec celle d’une relaxation SRL*. Nous montrons aussi que toute relaxation S&A s’obtient en renforçant une relaxation SRL* par des contraintes dites « conditions de symétries ». Nous étayons notre analyse par des résultats de calculs préliminaires comparant le renforcement des relaxations L&P, S&A et SRL* de rang 2. Ensuite, nous caractérisons les programmes linéaires mixtes 0-1 pour lesquels les hiérarchies S&A et SRL* coïncident. Comme application, nous prouverons que les hiérarchies SRL* et S&A coïncident pour l'optimisation d'une fonction pseudo booléenne sur un polyèdre quelconque. Pour illustrer cette propriété nous présentons des résultats de calculs préliminaires sur des instances MINCUT avec contraintes de cardinalité. Enfin, nous présentons des expériences de calcul concernant les renforcements procurés par des relaxations L&P de rang 2 et 3 sur des instances Max-2SAT et Max-3SAT. Nous explorons également, la possibilité d’utiliser des relaxations L&P partielles.

APA, Harvard, Vancouver, ISO, and other styles

28

Bourdache, Nadjet. "Élicitation incrémentale des préférences pour l’optimisation multi-objectifs : modèles non-linéaires, domaines combinatoires et approches tolérantes aux erreurs." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS255.

Full text

Abstract:

Les travaux effectués durant cette thèse s'inscrivent dans le cadre de la théorie de la décision algorithmique, domaine au carrefour de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle. Cette thèse vise à concevoir des méthodes d'optimisation interactive fondées sur l'élicitation incrémentale des préférences pour la prise de décision multicritère, multi-agents ou dans le risque. Nous nous intéressons plus précisément à l'élicitation incrémentale des paramètres de fonctions d'agrégation qui consiste à alterner questions préférentielles permettant de réduire l'incertitude concernant la valeur des paramètres modélisant les préférences particulières du décideur, et exploration de l'espace des solutions, jusqu'à pouvoir déterminer une recommandation de bonne qualité. L'intérêt d'alterner phases de questions et phases d'exploration est double: d'une part, les informations préférentielles récoltées durant une phase d'élicitation permettent de mieux focaliser la phase d'exploration suivante sur les solutions les plus intéressantes pour le décideur; d'autre part, l'exploration de l'espace des solutions permet de guider le choix des questions de manière à ce qu'elles soient les plus informatives possible. Nous introduisons dans cette thèse des méthodes d'élicitation dans différents contextes. Dans un premier temps, nous nous intéressons à des fonctions d'agrégation non-linéaires pour modéliser les préférences du décideur sur un ensemble combinatoire d'alternatives. Nous nous intéressons ensuite à la conception de méthodes d'élicitation prenant en compte la possibilité de la présence d'incohérences dans les réponses du décideur, d'abord sur domaine explicite, puis sur domaine combinatoire. Les algorithmes introduits sont génériques et peuvent s'appliquer à différents problèmes de choix multi-objectifs
This thesis work falls within the area of algorithmic decision theory, a research domain at the crossroad of decision theory, operations research and artificial intelligence. The aim is to produce interactive optimization methods based on incremental preference elicitation in decision problems involving several criteria, opinions of agents or scenarios. Preferences are represented by general decision models whose parameters must be adapted to each decision problem and each decision maker. Our methods interleave the elicitation of parameters and the exploration of the solution space in order to determine the optimal choice for the decision maker. The idea behind this is to use information provided by the elicitation to guide the exploration of the solution space and vice versa. In this thesis, we introduce new incremental elicitation methods for decision making in different contexts : first for decision making in combinatorial domains when the decision models are non-linear, and then in a setting where one takes into account the possibility of inconsistencies in the answers of te decision maker. All the algorithms that we introduce are general and can be applied to a wide range of multiobjective decision problems

APA, Harvard, Vancouver, ISO, and other styles

29

Nguyen, Quang Thuan. "Approches locales et globales basées sur la programmation DC et DCA pour des problèmes combinatoires en variables mixtes 0-1 : applications à la planification opérationnelle." Thesis, Metz, 2010. http://www.theses.fr/2010METZ037S/document.

Full text

Abstract:

Cette thèse développe les deux approches locales et globales basées sur la programmation DC et DCA pour l'optimisation combinatoire en variables mixtes 0-1 et leurs applications à la résolution de nombreux problèmes en planification opérationnelle. Plus particulièrement, cette thèse adresse à: l'amélioration de l'algorithme d'approximation extérieure basée sur DCA (appelé DCACUT) introduit par Nguyen V.V. et Le Thi pour la programmation linéaire en variables mixtes 0-1, les combinaisons des algorithmes globaux et DCA et l'étude numérique comparative de ces approches pour la programmation linéaire en variables mixtes 0-1, l'utilisation de DCA à la résolution de la programmation DC en variables mixtes 0-1 en utilisant la pénalité exacte, la mise en œuvre des algorithmes développés à la résolution des problèmes de grande taille en planification opérationnelle comme les problèmes dans le réseau de télécommunication sans fils, les problèmes d’ordonnancement ainsi que le problème d'affectation de tâches des véhicules aériens non pilotés ou bien le problème des tournées de véhicules dans une chaîne d'approvisionnement
This thesis develops two local and global approaches based on DC programming and DCA for mixed 0-1 combinatorial optimization and their applications to many problems in operational planning. More particularly, this thesis consists of: the improvement of the outer approximation algorithm based on DCA (called DCACUT) introduced by Nguyen V.V and Le Thi for mixed 0-1 linear programming, the combinations of global algorithms and DCA and the comparative numerical study of these approaches for mixed 0-1 linear programming, the use of DCA for solving mixed 0-1 programming via an exact penalty technique, the implementation of the algorithms developed for solving large scale problems in operational planning: two problems in wireless telecommunication network, two scheduling problems, an UAV task assignment problem and an inventory routing problem in supply chains

APA, Harvard, Vancouver, ISO, and other styles

30

Salazar-Neumann, Martha. "Advances in robust combinatorial optimization and linear programming." Doctoral thesis, Universite Libre de Bruxelles, 2010. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210192.

Full text

Abstract:

La construction de modèles qui protègent contre les incertitudes dans les données, telles que la variabilité de l'information et l'imprécision est une des principales préoccupations en optimisation sous incertitude. L'incertitude peut affecter différentes domaines, comme le transport, les télécommunications, la finance, etc. ainsi que les différentes parts d'un problème d'optimisation, comme les coefficients de la fonction objectif et /ou les contraintes. De plus, l'ensemble des données incertaines peut être modélisé de différentes façons, comme sous ensembles compactes et convexes de l´espace réel de dimension n, polytopes, produits Cartésiens des intervalles, ellipsoïdes, etc.

Une des approches possibles pour résoudre des tels problèmes est de considérer les versions minimax regret, pour lesquelles résoudre un problème sous incertitude revient à trouver une solution qui s'écarte le moins possible de la valeur solution optimale dans tout les cas.

Dans le cas des incertitudes définies par intervalles, les versions minimax regret de nombreux problèmes combinatoires polynomiaux sont NP-difficiles, d'ou l'importance d'essayer de réduire l'espace des solutions. Dans ce contexte, savoir quand un élément du problème, représenté par une variable, fait toujours ou jamais partie d'une solution optimal pour toute réalisation des données (variables 1-persistentes et 0-persistentes respectivement), constitue une manière de réduire la taille du problème. Un des principaux objectifs de cette thèse est d'étudier ces questions pour quelques problèmes d'optimisation combinatoire sous incertitude.

Nous étudions les versions minimax regret du problème du choix de p éléments parmi m, de l'arbre couvrant minimum et des deux problèmes de plus court chemin. Pour de tels problèmes, dans le cas des incertitudes définis par intervalles, nous étudions le problème de trouver les variables 1- et 0-persistentes. Nous présentons une procédure de pre-traitement du problème, lequel réduit grandement la taille des formulations des versions de minimax regret.

Nous nous intéressons aussi à la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont incertains et l'ensemble des données incertaines est polyédral. Dans le cas où l'ensemble des incertitudes est défini par des intervalles, le problème de trouver le regret maximum est NP-difficile. Nous présentons des cas spéciaux ou les problèmes de maximum regret et de minimax regret sont polynomiaux. Dans le cas où l´ensemble des incertitudes est défini par un polytope, nous présentons un algorithme pour trouver une solution exacte au problème de minimax regret et nous discutons les résultats numériques obtenus dans un grand nombre d´instances générées aléatoirement.

Nous étudions les relations entre le problème de 1-centre continu et la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont évalués à l´aide des intervalles. En particulier, nous décrivons la géométrie de ce dernier problème, nous généralisons quelques résultats en théorie de localisation et nous donnons des conditions sous lesquelles certaines variables peuvet être éliminées du problème. Finalement, nous testons ces conditions dans un nombre d´instances générées aléatoirement et nous donnons les conclusions.
Doctorat en sciences, Orientation recherche opérationnelle
info:eu-repo/semantics/nonPublished

APA, Harvard, Vancouver, ISO, and other styles

31

Tlig, Ghassen. "Programmation mathématique en tomographie discrète." Phd thesis, Conservatoire national des arts et metiers - CNAM, 2013. http://tel.archives-ouvertes.fr/tel-00957445.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

32

Delmée, Quentin. "Résolution exacte de problèmes de localisation de services bi-objectifs en variables mixtes." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4055/document.

Full text

Abstract:

Dans ce travail, nous nous intéressons à la résolution exacte de problèmes de localisation de service en variables mixtes. Les problèmes de programmation linéaire bi-objectif en variables mixtes ont été très étudiés dans les dernières années, mais uniquement dans un contexte générique. De même, les problèmes de localisation de services bi-objectif n’ont été étudiés que dans un cas purement discret. Nous considérons dans un premier temps le problème de localisation de services bi-objectif sans capacité. Afin de le résoudre, nous adaptons la méthode de pavage par boîtes proposée pour le cas discret. Les boîtes rectangulaires deviennent triangulaires dans le cas mixte. De plus, leur exploration est grandement facilitée, ce qui déplace la difficulté du problème dans l’énumération et le filtrage de ces boîtes. Différentes stratégies d’énumération sont proposées. Le problème de localisation de services bi-objectif avec capacité est ensuite considéré. Tout d’abord, une adaptation de la méthode de pavage par boîtes triangulaires est réalisée pour le cas avec capacité. Cependant, la nature du problème rend cette méthode beaucoup plus limitée. Nous considérons ensuite une méthode en deux phases dont la principale routine d’exploration repose sur une adaptation d’un algorithme de branch and bound initialement proposé par Beasley, dans le contexte bi-objectif. Les résultats expérimentaux sur des instances aux caractéristiques variées attestent de la pertinence des méthodes que nous proposons
The purpose of this work is the exact solution of biobjective mixed-integer facility location problems. Biobjective mixed integer linear programming problem have been largely studied in recent years but only in the generic context. The same way, the study of biobjective facility location problems has been restricted to the discrete case. We consider first the bi-objective uncapacitated facility location problem. To solve it, we adapt the box paving method proposed for the discrete case. Rectangular boxes become triangular. Moreover, their exploration becomes considerably easier. The difficulty of the problem is therefore translated to the enumeration and the filtering of these boxes. Different enumeration strategies are proposed. Next, we consider the bi-objective capacitated facility location problem. We first propose an adaptation of the triangular box paving method to the capacitated case. However, the structure of the problem highly limits the method. Thus, we consider a two phase method. The main exploration routine is based on the adaptation of a branch and bound algorithm proposed by Beasley that we adapt to the bi-objective context. Experimental results on various instances show the efficiency of the proposed methods

APA, Harvard, Vancouver, ISO, and other styles

33

Koubàa, Mohamed. "Routage, protection et ingénierie de trafic dans les réseaux WDM tout-optiques." Phd thesis, Télécom ParisTech, 2005. http://pastel.archives-ouvertes.fr/pastel-00001947.

Full text

Abstract:

Cette thèse porte essentiellement sur les problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux de transport WDM tout-optiques. L'optimisation de ces réseaux est nécessaire aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées. La thèse est organisée en trois parties. La première partie traite du problème de routage et affectation de longueur d'onde. Nous proposons de résoudre le problème considérant des demandes de trafic permanentes. Des méthodes à la fois exactes basées sur la programmation linéaire et approchées ont été développées. Nous étendons ensuite le modèle de trafic pour considérer simultanément des demandes de trafic pré-planifiées et des demandes de trafic aléatoires. Différent algorithmes de routage ont été développés. Les différents algorithmes ont été comparés en terme de taux de rejet global. La deuxième partie concerne le problème de routage et affectation de longueurs d'onde avec protection. Les ressources dédiées à la protection sont rarement sollicitées, nous cherchons à en minimiser le nombre grâce au multiplexage des circuits optiques de protection. Des méthodes exactes et approchées sont encore une fois proposées considérant les demandes de trafic citées ci-dessus. La dernière partie présente un algorithme de reroutage de canaux optiques afin d'améliorer le taux de rejet dans les réseaux tout-optiques sans convertisseurs en longueurs d'onde. Plusieurs variantes de l'algorithme ont été proposées. Les résultats obtenus montrent un gain intéressant en terme de taux de rejet.

APA, Harvard, Vancouver, ISO, and other styles

34

Thuillier, Kerian. "Méthodes de satisfiabilité hybrides pour l'inférence de régulations booléennes contrôlant des réseaux métaboliques." Electronic Thesis or Diss., Université de Rennes (2023-....), 2024. http://www.theses.fr/2024URENS032.

Full text

Abstract:

Les systèmes biologiques sont des systèmes multi-échelles complexes composés de nombreux mécanismes biologiques interconnectés. Parmi ces échelles, il y a le métabolisme, qui transforme les nutriments en énergie et en biomasse, et le système de régulation, qui agit comme un contrôleur de l’activité métabolique. Modéliser le couplage du métabolisme et de la régulation est difficile et nécessite d'intégrer les formalismes algébriques différentiels modélisant le métabolisme avec les formalismes discrets modélisant la régulation. Bien qu'il existe des formalismes de simulation de la dynamique hybride de ce couplage, il n'existe aucune méthode pour synthétiser les contrôleurs régulant l'activité métabolique, i.e. les règles de régulation. Cette thèse présente trois formulations du problème de synthèse comme des problèmes d'optimisation combinatoire sous contraintes, logiques et hybrides (logiques et linéaires), quantifiées. Chaque formulation fait l'objet d'une approche de résolution dédiée. La première repose sur des méthodes de satisfiabilité, tandis que les deux autres utilisent des méthodes de résolution hybrides couplant des contraintes logiques et linéaires. En particulier, la thèse présente une méthode générique pour résoudre les problèmes d'optimisation combinatoire sous contraintes linéaires quantifiées. Ces travaux ont conduit au développement de deux logiciels, MERRIN et MerrinASP, qui étendent le paradigme de programmation par ensembles réponses (ASP) avec des contraintes linéaires quantifiées. Cette thèse met également à disposition des jeux de données synthétiques simulant différents types de données omiques, ainsi que le protocole utilisé pour les générer
Biological systems are complex multi-scale systems composed of many interconnected biological mechanisms. These scales include the metabolism, which transforms nutrients into energy and biomass, and the regulatory system, which acts as a controller of metabolic activity. Modeling the coupling of metabolism and regulation is difficult and requires integrating the differential-algebraic formalisms of metabolism with the discrete formalisms of regulation. Although formalisms for simulating the hybrid dynamics of this coupling exist, no method allows for the synthesis of the controllers that regulate metabolic activity, that is, the regulatory rules. This thesis presents three formulations of the synthesis problem as combinatorial optimization problems under logical and hybrid (logical and linear) quantified constraints. A dedicated solving method is given for each formulation. The first formulation is solved using satisfiability methods, while the other two rely on hybrid solving methods that integrate logical constraints and linear arithmetic. In particular, the thesis presents a generic framework for solving combinatorial optimization problems under quantified linear constraints. These formalizations have led to the development of two tools, MERRIN and MerrinASP, which extend Answer Set Programming (ASP) with quantified linear constraints. This thesis also provides synthetic datasets that simulate different types of omics data, as well as the protocol used to generate them

APA, Harvard, Vancouver, ISO, and other styles

35

Garnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.

Full text

Abstract:

En algorithmique et en complexité, la plus grande part de la recherche se base sur l’hypothèse que P ≠ NP (Polynomial time et Non deterministic Polynomial time), c'est-à-dire qu'il existe des problèmes dont la solution peut être vérifiée mais non construite en temps polynomial. Si cette hypothèse est admise, de nombreux problèmes naturels ne sont pas dans P (c'est-à-dire, n'admettent pas d'algorithme efficace), ce qui a conduit au développement de nombreuses branches de l'algorithmique. L'une d'elles est la complexité paramétrée. Elle propose des algorithmes exacts, dont l'analyse est faite en fonction de la taille de l'instance et d'un paramètre. Ce paramètre permet une granularité plus fine dans l'analyse de la complexité.Un algorithme sera alors considéré comme efficace s'il est à paramètre fixé, c'est-à-dire, lorsque sa complexité est exponentielle en fonction du paramètre et polynomiale en fonction de la taille de l'instance. Ces algorithmes résolvent les problèmes de la classe FPT (Fixed Parameter Tractable).L'extraction de noyaux est une technique qui permet, entre autre, d’élaborer des algorithmes à paramètre fixé. Elle peut être vue comme un pré-calcul de l'instance, avec une garantie sur la compression des données. Plus formellement, une extraction de noyau est une réduction polynomiale depuis un problème vers lui même, avec la contrainte supplémentaire que la taille du noyau (l'instance réduite) est bornée en fonction du paramètre. Pour obtenir l’algorithme à paramètre fixé, il suffit de résoudre le problème dans le noyau, par exemple par une recherche exhaustive (de complexité exponentielle, en fonction du paramètre). L’existence d'un noyau implique donc l'existence d'un algorithme à paramètre fixé, la réciproque est également vraie. Cependant, l’existence d'un algorithme à paramètre fixé efficace ne garantit pas un petit noyau, c'est a dire un noyau dont la taille est linéaire ou polynomiale. Sous certaines hypothèses, il existe des problèmes n’admettant pas de noyau (c'est-à-dire hors de FPT) et il existe des problèmes de FPT n’admettant pas de noyaux polynomiaux.Un résultat majeur dans le domaine des noyaux est la construction d'un noyau linéaire pour le problème Domination dans les graphes planaires, par Alber, Fellows et Niedermeier.Tout d'abord, la méthode de décomposition en régions proposée par Alber, Fellows et Niedermeier, a permis de construire de nombreux noyaux pour des variantes de Domination dans les graphes planaires. Cependant cette méthode comportait un certain nombre d’imprécisions, ce qui rendait les preuves invalides. Dans la première partie de notre thèse, nous présentons cette méthode sous une forme plus rigoureuse et nous l’illustrons par deux problèmes : Domination Rouge Bleue et Domination Totale.Ensuite, la méthode a été généralisée, d'une part, sur des classes de graphes plus larges (de genre borné, sans-mineur, sans-mineur-topologique), d'autre part, pour une plus grande variété de problèmes. Ces méta-résultats prouvent l’existence de noyaux linéaires ou polynomiaux pour tout problème vérifiant certaines conditions génériques, sur une classe de graphes peu denses. Cependant, pour atteindre une telle généralité, il a fallu sacrifier la constructivité des preuves : les preuves ne fournissent pas d'algorithme d'extraction constructif et la borne sur le noyau n'est pas explicite. Dans la seconde partie de notre thèse nous effectuons un premier pas vers des méta-résultats constructifs ; nous proposons un cadre général pour construire des noyaux linéaires en nous inspirant des principes de la programmation dynamique et d'un méta-résultat de Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh et Thilikos
In the fields of Algorithmic and Complexity, a large area of research is based on the assumption that P ≠ NP(Polynomial time and Non deterministic Polynomial time), which means that there are problems for which a solution can be verified but not constructed in polynomial time. Many natural problems are not in P, which means, that they have no efficient algorithm. In order to tackle such problems, many different branches of Algorithmic have been developed. One of them is called Parametric Complexity. It consists in developing exact algorithms whose complexity is measured as a function of the size of the instance and of a parameter. Such a parameter allows a more precise analysis of the complexity. In this context, an algorithm will be considered to be efficient if it is fixed parameter tractable (fpt), that is, if it has a complexity which is exponential in the parameter and polynomial in the size of the instance. Problems that can be solved by such an algorithm form the FPT class.Kernelisation is a technical that produces fpt algorithms, among others. It can be viewed as a preprocessing of the instance, with a guarantee on the compression of the data. More formally, a kernelisation is a polynomial reduction from a problem to itself, with the additional constraint that the size of the kernel, the reduced instance, is bounded by a function of the parameter. In order to obtain an fpt algorithm, it is sufficient to solve the problem in the reduced instance, by brute-force for example (which has exponential complexity, in the parameter). Hence, the existence of a kernelisiation implies the existence of an fpt algorithm. It holds that the converse is true also. Nevertheless, the existence of an efficient fpt algorithm does not imply a small kernel, meaning a kernel with a linear or polynomial size. Under certain hypotheses, it can be proved that some problems can not have a kernel (that is, are not in FPT) and that some problems in FPT do not have a polynomial kernel.One of the main results in the field of Kernelisation is the construction of a linear kernel for the Dominating Set problem on planar graphs, by Alber, Fellows and Niedermeier.To begin with, the region decomposition method proposed by Alber, Fellows and Niedermeier has been reused many times to develop kernels for variants of Dominating Set on planar graphs. Nevertheless, this method had quite a few inaccuracies, which has invalidated the proofs. In the first part of our thesis, we present a more thorough version of this method and we illustrate it with two examples: Red Blue Dominating Set and Total Dominating Set.Next, the method has been generalised to larger classes of graphs (bounded genus, minor-free, topological-minor-free), and to larger families of problems. These meta-results prove the existence of a linear or polynomial kernel for all problems verifying some generic conditions, on a class of sparse graphs. As a price of generality, the proofs do not provide constructive algorithms and the bound on the size of the kernel is not explicit. In the second part of our thesis, we make a first step to constructive meta-results. We propose a framework to build linear kernels based on principles of dynamic programming and a meta-result of Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh and Thilikos

APA, Harvard, Vancouver, ISO, and other styles

36

Khaled, Oumaima. "Une méthodologie générique de réparation multicritère pour l'optimisation sous incertitude : Application aux problèmes de planification et d'affectation." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLC047.

Full text

Abstract:

Plusieurs problématiques de gestion d’opérations peuvent être formalisées avec un problème d’optimisation discret. Ces modèles d’optimisation sont traditionnellement développés sous l’hypothèse que les données d’entrée sont déterministes, non impactées par des changements inattendus ou des incertitudes. Au cours des dernières années, le besoin en modèles performants, incluant des outils efficaces et permettant de réagir de manière optimale aux imprévus (perturbations), n’a cessé de croitre. En phase d’exécution d’un système, plusieurs événements imprévus (incertitudes) peuvent le perturber et le faire dévier de son parcours original voire rendre son exécution impossible. Il est vrai que ces incertitudes peuvent être considérées de manière proactive par le biais d’une optimisation stochastique ou des modèles d'optimisation robustes. Mais même avec des solutions robustes, des événements inattendus peuvent encore se produire nécessitant de revoir le plan robuste en cours d’exécution. Dans cette thèse, l’objectif est de prendre en compte ces incertitudes de manière réactive dans les modèles. Ainsi, une nouvelle méthodologie générique est proposée pour les problèmes d'optimisation de réparation / récupération. En considérant les solutions réparées / récupérées fournies par cette méthodologie appliquée à un plan initial en cours de mise en oeuvre, un décideur peut vouloir minimiser les coûts d'exploitation, mais aussi limiter les changements par rapport au plan initial. Le problème de réparation / récupération est formulé comme un problème d'optimisation multiobjectif, qui minimise des fonctions spécifiques relatives à divers critères de réparation (pilotés par les choix du décideur)
A wide variety of operations management problems can be formulated and solved as discrete optimization problems. Traditionally, these models have been mostly developed and used under the assumption that the input data are known in advance, not subject to unexpected changes, nor impacted by uncertainty. In recent years, the need for improved models providing efficient tools for quickly and optimally reacting to the occurrence of unexpected events (disruptions) has become a more and more important issue. In the execution phase, various unanticipated events will disrupt the system and make the plan deviate from its intended course and even make it infeasible.Uncertainty can be taken into account in a proactive way with stochastic optimization or robust optimization models. However, even with robust solutions, unexpected events can still occur requiring to reconsider the robust plan under execution. In this thesis, we are interested to cope with uncertainty in a reactive way. We propose a new generic methodology for repair/recovery optimization problems. When considering repair/recovery solutions for the initial plan under implementation, the decision-maker may want to minimize operating costs, but also limit the changes with respect to the initial plan. We formulate the repair/recovery problem as a multiobjective optimization problem minimizing specified functions for various repair criteria

APA, Harvard, Vancouver, ISO, and other styles

37

Boria, Nicolas. "Optimisation combinatoire et environnements dynamiques." Paris 9, 2011. http://basepub.dauphine.fr/xmlui/handle/123456789/7232.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Chung, Yerim. "Optimisation combinatoire inverse et applications." Paris 1, 2010. http://www.theses.fr/2010PA010009.

Full text

Abstract:

L'optimisation combinatoire inverse a suscité beaucoup d'attention de la communauté de la recherche opérationnelle pendant les deux dernières décennies. Étant donnée une instance d'un problème d'optimisation combinatoire définie par un système de paramètres (coûts, profits, etc. ) et une solution réalisable, le problème inverse associé consiste à modifier au minimum les paramètres afin de rendre la solution fixée optimale dans l'instance modifiée. Dans le cadre de l'optimisation combinatoire, de nombreux problèmes inverses ont été étudiés, mais relativement peu d'études ont été menées sur des versions inverses de problèmes NP-difficiles. Dans cette thèse, nous considérons des problèmes combinatoires inverses généralisés. Nous commençons par imposer certaines contraintes aux paramètres à modifier. En particulier, des contraintes booléennes nous permettent de définir des versions inverses de problèmes non pondérés. Ainsi, des contraintes discrètes engendrent des problèmes combinatoires inverses eux-même combinatoires. Nous introduisons alors deux variantes de problèmes combinatoires inverses généralisés, à savoir "les problèmes inverses contre un algorithme spécifié" et "les problèmes inverses en valeur". Pour la première, un algorithme étant spécifié pour le problème d'origine, on cherche, pour une instance et une solution réalisable fixées, à modifier le moins possible l'instance pour que cette solution puisse être choisie par l'algorithme. Un problème inverse en valeur quant à lui est défini en spécifiant une valeur à atteindre au lieu d'une solution cible. L'objectif est de modifier le moins possible l'instance considerée de sorte que la valeur optimale de l'instance modifiée soit égale à la valeur fixée. Nous étudions différentes versions inverses de problèmes NP-difficiles. Les problèmes abordés sont le stable maximum d'un graphe (ensemble maximum de sommets 2 à 2 non adjacents), le voyageur de commerce minimum et la coloration minimum des sommets d'un graphe. Notre principal objectif est d'étudier la complexité et l'approximabilité de ces problèmes.

APA, Harvard, Vancouver, ISO, and other styles

39

Damay, Jean. "Techniques de résolution basées sur la Programmation Linéaire pour l'Ordonnancement de Projet." Clermont-Ferrand 2, 2005. http://195.221.120.247/simclient/consultation/binaries/stream.asp?INSTANCE=UCFRSIM&eidmpa=DOCUMENTS_THESES_90.

Full text

Abstract:

Nous considérons le problème d'ordonnancement de projet RCPSP. Il consiste à planifier l'exécution d'un ensemble d'activités, soumises à des contraintes de précédence et de ressources, et nous minimisons ici la durée du projet. Nous présentons une reformulation originale de ce problème, basée sur une relaxation linéaire, ou chaque variable est associée à un ensemble d'activités pouvant être exécutées simultanément. Cette relaxation est résolue par l'algorithme du Simplexe avec Génération de Colonnes, auquel nous adjoignons un test incrémental de réalisabilité de la solution en base. Un résultat théorique de connexité est également fourni. Nous proposons en outre des techniques de diversification dans l'espace de recherche. Ces méthodes traitent avec qualité le cas particulier préemptif. Une métode par Séparation/ Evaluation, basée sur cette même relaxation linéaire, est développée pour ce cas, fournissant toutes les solutions optimales des instances de référence à 30 activités

APA, Harvard, Vancouver, ISO, and other styles

40

Haddad, Marcel Adonis. "Nouveaux modèles robustes et probabilistes pour la localisation d'abris dans un contexte de feux de forêt." Electronic Thesis or Diss., Université Paris sciences et lettres, 2020. http://www.theses.fr/2020UPSLD021.

Full text

Abstract:

A cause du réchauffement climatique, le nombre et l’intensité des feux de forêts augmentent autour du globe. Dansce contexte, la construction de refuges contre le feu est une solution de plus en plus envisagée. Le problème consisteessentiellement à localiser p refuges de sorte à minimiser la distance maximale qui sépare un usager du plus procherefuge accessible en cas de feux. Le territoire considéré est divisé en zones et est modélisé comme un graphe auxarêtes pondérées. Un départ de feux sur une seule zone (c’est-à-dire sur un sommet). La principale conséquence d’unfeu est que les chemins d’évacuation sont modifiés de deux manières. Premièrement, un chemin d’évacuation ne peutpas traverser le sommet en feu. Deuxièmement, le fait qu’une personne proche de l’incendie puisse avoir un choix limitéde direction d’évacuation, ou être sous stress, est modélisé à l’aide d’une stratégie d’évacuation nouvellement définie.Cette stratégie d’évacuation induit des distances d’évacuation particulières qui rendent notre modèle spécifique. Selon letype de données considéré et l’objectif recherché, nous proposons deux problèmes avec ce modèle: le Robust p-CenterUnder Pressure et le Probabilistic p-Center Under Pressure. Nous prouvons que ces deux problèmes sont NP-difficilessur des classes de graphes pertinentes pour notre contexte. Nous proposons également des résultats d’approximationet d’inapproximation. Finalement, nous développons des algorithmes polynomiaux sur des classes de graphes simples,et nous développons des algorithmes mathématiques basés sur la programmation linéaire
The location of shelters in different areas threatened by wildfires is one of the possible ways to reduce fatalities in acontext of an increasing number of catastrophic and severe forest fires. The problem is basically to locate p sheltersminimizing the maximum distance people will have to cover to reach the closest accessible shelter in case of fire. Thelandscape is divided in zones and is modeled as an edge-weighted graph with vertices corresponding to zones andedges corresponding to direct connections between two adjacent zones. Each scenario corresponds to a fire outbreak ona single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuationpath cannot pass through the vertex on fire. Second, the fact that someone close to the fire may have limited choice, ormay not take rational decisions, when selecting a direction to escape is modeled using a new kind of evacuation strategy.This evacuation strategy, called Under Pressure, induces particular evacuation distances which render our model specific.We propose two problems with this model: the Robust p-Center Under Pressure problem and the Probabilistic p-CenterUnder Pressure problem. First we prove hardness results for both problems on relevant classes of graphs for our context.In addition, we propose polynomial exact algorithms on simple classes of graphs and we develop mathematical algorithmsbased on integer linear programming

APA, Harvard, Vancouver, ISO, and other styles

41

Ould, Mohamed Lemine Mohamed. "Connaissance inter-entreprises et optimisation combinatoire." Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090015/document.

Full text

Abstract:

La connaissance inter-entreprises permet à chaque société de se renseigner sur ses clients, ses fournisseurs et de développer son activité tout en limitant le risque lié à la solvabilité ou retard de paiement de ses partenaires. Avec les tensions de trésorerie, la nécessité de la croissance et l'augmentation de la concurrence, ce domaine devient plus que jamais stratégique aussi bien pour les PME que pour les grands groupes. La quantité de données traitée dans ce domaine, les exigences de qualité et de fraîcheur, la nécessité de croiser ces données pour déduire des nouvelles informations et indicateurs, posent plusieurs problèmes pour lesquels l'optimisation en général et l'optimisation combinatoire en particulier peuvent apporter des solutions efficaces. Dans cette thèse, nous utilisons l'optimisation combinatoire, l'algorithmique du texte et la théorie des graphes pour résoudre efficacement des problèmes issus du domaine de la connaissance inter-entreprises et posés par Altares D&B. Dans un premier temps, nous nous intéressons à la qualité de la base de données des dirigeants. Ce problème combine la détection et suppression des doublons dans une base de données et la détection d'erreurs dans une chaîne de caractères. Nous proposons une méthode de résolution basée sur la normalisation des données et l'algorithmique de texte et de comparaison syntaxique entre deux chaînes de caractères. Les résultats expérimentaux montrent non seulement que cette méthode est pertinente dans la détection et la suppression des doublons mais aussi qu'elle est efficace de point du vue temps de traitement. Nous nous focalisons par la suite sur les données des liens capitalistiques et nous considérons le problème de calcul des liens indirects et l'identification des têtes des groupes. Nous présentons une méthode de résolution basée sur la théorie des graphes. Nous testons cette méthode sur plusieurs instances réelles. Nous prouvons l'efficacité de cette méthode par son temps de traitement et par l'espace de calcul qu'elle utilise. Enfin, nous remarquons que le temps de calcul de celui-ci augmente de façon logarithmique en fonction de la taille d'instance. Enfin, nous considérons le problème de l'identification des réseaux d'influence. Nous formalisons ce problème en termes de graphes et nous le ramenons à un problème de partitionnement de graphe qui est NP-difficile dans ce cas général. Nous proposons alors une formulation en programme linéaire en nombre entier pour ce problème. Nous étudions le polyèdre associé et décrivons plusieurs classes de contraintes valides. Nous donnons des conditions nécessaires pour que ces contraintes définissent des facettes et discutons des algorithmes de séparations de ces contraintes. En utilisant les résultats polyédraux obtenus, nous développons un algorithme de coupes et branchements. Enfin, nous donnons quelques résultats expérimentaux qui montrent l'efficacité de notre algorithme de coupes et branchements
The inter-companies knowledge allows to every partner to learn about its customers, its suppliers and to develop its activity. Also this permits to limit the risk related to the creditworthiness, or the late payment of its partners. With the cash flow pressures, the need for growth and increased competition, this area becomes more strategic than ever, for both small (PME) and large groups. The amount of data processed in this domain, the requirements of quality and freshness, the need to cross these data to obtain new information and indicators, yield several optimization problems for which the recent techniques and computational tools can bring effective solutions. In this thesis, we use combinatorial optimization, text algorithms as well as graph theory to solve efficiently problems arising in the field of inter-companies knowledge. In particular, such problems was encountered in Altares D&B. First, we focus on the quality of the managers database. This problem combines the detection and removal of duplicates in a database, as well as the error detection in a string. We propose a method for solving this problem, based on data normalization, text algorithms and syntactic comparison between two strings. Our experimental results show that this method is relevant for the detection and removal of duplicates, and it is also very efficient in terms of processing time. In a second part of the thesis, we address a problem related to the data of ownership links. We compute the indirect links, and identify the group heads. We propose a method for solving this problem using graph theory and combinatorial optimization. We then perform a set of experiments on several real-world instances. The computational results show the effectiveness of our method in terms of CPU-time and resource allocation. In fact, the CPU time for computation increases logarithmically with the size of the instances. Finally, we consider the problem of identifying influence networks. We give a description of this problem in terms of graphs, and show that it can reduce to a graph partitioning problem. The latter is NP-hard. We then propose an integer linear programming formulation to model the problem. We investigate the associated polyhedron and describe several classes of valid inequalities. We give some necessaryand sufficient conditions for these inequalities to define facets of the considered polyhedron, and we discuss the related separation problems. Based on the obtained polyhedral results, we devise a Branch-and-Cut algorithm to solve the problem. Some numerical results are presented to show the efficiency of our algorithm

APA, Harvard, Vancouver, ISO, and other styles

42

Laburthe, François. "Contraintes et algorithmes en optimisation combinatoire." Paris 7, 1998. http://www.theses.fr/1998PA077236.

Full text

Abstract:

Ce travail evalue la programmation par contraintes (ppc) pour la resolution de problemes d'optimisation combinatoire. Sur un ensemble de grands problemes (d'allocation de ressources, d'ordonnancement, d'optimisation de parcours et d'emplois du temps), on etudie et on propose de renforcer la resolution en ppc par des regles de coupes redondantes, des algorithmes de propagation issus de la recherche operationnelle et des arbres de recherche dedies. On compare ensuite l'efficacite d'une resolution par contraintes avec des algorithmes traditionnels de recherche operationnelle, ce qui permet d'etablir une cartographie de la resolution des problemes combinatoires consideres, mettant en relation les problemes (leur type et leur taille) avec les methodes de resolution appropriees (programmation par contraintes et algorithmes de recherche operationnelle). Cette cartographie montre l'interet de developper, pour les problemes complexes de grandes taille, des algorithmes hybrides, utilisant la programmation par contraintes en cooperation avec d'autres grandes methodes de resolution, comme l'optimisation locale par exemple. Pour permettre la programmation de tels algorithmes complexes, on propose un langage de haut niveau, salsa, permettant de specifier le controle d'algorithmes de recherche complexes. On illustre son utilisation pour la resolution de problemes divers d'optimisation par des algorithmes hybrides et on presente une semantique operationnelle a partir de laquelle a ete realise l'implementation prototype.

APA, Harvard, Vancouver, ISO, and other styles

43

LE, GALL ARMELLE. "Incrementalite et adaptativite en optimisation combinatoire." Paris 11, 1997. http://www.theses.fr/1997PA112356.

Full text

Abstract:

Dans cette these, nous nous interessons a accroitre l'efficacite de methodes permettant de resoudre un probleme d'optimisation combinatoire pour une serie d'instances. Nous developpons des versions adaptatives aux methodes conventionnelles, i. E. Qui utilisent des informations provenant d'une precedente resolution. Dans le cas particulier ou la nouvelle instance ne se distingue de la precedente que par le nombre de variables, on parle de methodes incrementales. Une etude menee sur differents problemes polynomiaux a confirme l'interet des algorithmes incrementaux. L'utilisation de fonctions d'evaluation incrementales dans les methodes de separation-evaluation permet un gain important car les evaluations sont realisees a maintes reprises et pour des instances tres voisines. Nous proposons trois methodes qui different sur la position de l'instance de reference dans l'arbre de recherche. Elles sont validees sur le probleme np-difficile du placement de taches sur un systeme distribue. Nous avons mis en evidence les capacites adaptatives des reseaux de neurones : nous avons defini comment perturber un reseau pour que celui-ci quitte un etat stable et converge vers un nouvel etat representatif d'une solution a une nouvelle instance, voisine de la precedente. Cette methode presente un interet pratique evident car elle est independante du probleme et de la transformation appliquee a l'instance. Les differentes versions du modele de hopfield presentent un manque de selectivite qui se traduit experimentalement par des neurones qui conservent des activations loin a la fois de 0 et de 1. Comme le mecanisme d'activation competitive est particulierement apte a realiser cette separation, nous avons generalise les regles permettant son instauration pour definir une nouvelle extension du modele de hopfield. L'etude sur l'adaptativite est menee avec ce modele dont la validite a ete confirmee sur le probleme du recouvrement d'ensembles.

APA, Harvard, Vancouver, ISO, and other styles

44

Koubi, Vassilada. "Reseaux de neurones et optimisation combinatoire." Paris 5, 1994. http://www.theses.fr/1994PA05S014.

Full text

Abstract:

Les problemes d'optimisation combinatoire ont des donnees assez structurees qui conviennent au traitement d'une architecture neuronale. Ces problemes qui appartiennent en general a la classe np-complet, necessitent une grande puissance de calcul. L'objectif de ce travail est d'appliquer le modele de reseau de neurones aleatoires aux problemes d'optimisation combinatoire. L'application du reseau neuronal aleatoire de gelenbe, a un probleme d'optimisation combinatoire, est caracterisee par l'evolution des entrees externes, qui correspondent au gradient de la fonction objective, en contradiction avec les autres methodes neuronales ou les entrees sont en general constantes. Deux alternatives de resolution sont proposees : l'approche gradient, application de l'algorithme du gradient sur la fonction et l'approche dynamique, introduction du gradient de la fonction aux equations dynamiques qui sont liees au probleme considere. Nous avons resolu un probleme classique d'optimisation combinatoire, le probleme du voyageur de commerce, et un probleme de satisfaction des contraintes, le probleme de reines non attaquantes. De plus nous avons propose la solution pour d'autres problemes. Le reseau neuronal aleatoire applique au probleme du voyageur de commerce a ete evalue et compare avec les autres methodes connexionnistes. Les resultats obtenus sont assez satisfaisants, de qualite similaire (ou meme meilleure) a ceux obtenus par d'autres methodes. Le probleme de reines a ete resolu par deux modelisations. La premiere consiste a resoudre directement ce probleme, alors que dans la seconde on considere le probleme des reines comme un probleme du stable maximal. Quelque soit la methode retenue, toutes les solutions possibles, ou presque, pour ce probleme ont ete obtenues.

APA, Harvard, Vancouver, ISO, and other styles

45

HOUDAYER, JEROME. "Verres de spins et optimisation combinatoire." Paris 11, 1999. http://www.theses.fr/1999PA112205.

Full text

Abstract:

Les systemes desordonnes et frustres sont un des sujets actifs de la physique statistique actuelle dont l'etude analytique est particulierement difficile. L'approximation de champ moyen est une approche fructueuse, mais sa pertinence pour les systemes en dimension finie est encore debattue. Dans cette these, j'etudie la validite de cette approximation et la nature du paysage d'energie pour deux systemes differents : le couplage minimal et les verres de spins. Les techniques utilisees sont essentiellement numeriques, mais contrairement a ce qu'on voit habituellement il ne s'agit pas ici de simulations de type monte carlo. La methode que j'ai retenue permet d'etudier un systeme a temperature nulle et consiste a calculer l'etat fondamental et les excitations de faible energie par des methodes d'optimisation combinatoire. L'optimisation combinatoire est la branche de l'informatique qui s'interesse aux problemes d'optimisation d'une fonction sur un ensemble fini de configurations. Trouver le fondamental d'un systeme desordonne et frustre est un probleme de ce type ce qui cree des liens interessants entre les deux domaines. Les apports de cette these peuvent etre decomposes en trois parties : premierement une etude approfondie du couplage minimal (un probleme de dimerisation), dont la conclusion principale est l'existence de deux echelles, l'echelle macroscopique bien decrite par le champ moyen et l'echelle microscopique decrite par une theorie de type gouttelettes. Deuxiemement, une etude des verres de spins en dimension finie qui semble indiquer l'absence de la ligne de transition at en champ magnetique predite par le champ moyen. Et finalement le developpement d'un nouveau type d'algorithme d'optimisation combinatoire base sur l'idee de renormalisation qui s'avere etre a la fois general et tres puissant.

APA, Harvard, Vancouver, ISO, and other styles

46

Waserhole, Ariel. "Optimisation des systèmes de véhicules en libre service par la tarification." Thesis, Grenoble, 2013. http://www.theses.fr/2013GRENM049/document.

Full text

Abstract:

Nous étudions les systèmes de véhicules en libre service en aller-simple : avec emprunt et restitution dans des lieux éventuellement différents. La publicité promeut l'image de flexibilité et d'accessibilité (tarifaire) de tels systèmes, mais en réalité il arrive qu'il n'y ait pas de véhicule disponible au départ, voire pire, pas de place à l'arrivée. Il est envisageable (et pratiqué pour Vélib' à Paris) de relocaliser les véhicules pour éviter que certaines stations soient vides ou pleines à cause des marées ou de la gravitation. Notre parti-pris est cependant de ne pas considérer de ``relocalisation physique'' (à base de tournées de camions) en raison du coût, du trafic et de la pollution occasionnées (surtout pour des systèmes de voitures, comme Autolib' à Paris). La question à laquelle nous désirons répondre dans cette thèse est la suivante : Une gestion via des tarifs incitatifs permet-elle d'améliorer significativement les performances des systèmes de véhicules en libre service ?
One way Vehicle Sharing Systems (VSS), in which users pick-up and return a vehicle in different places is a new type of transportation system that presents many advantages. However, even if advertising promotes an image of flexibility and price accessibility, in reality customers might not find a vehicle at the original station (which may be considered as an infinite price), or worse, a parking spot at destination. Since the first Bike Sharing Systems (BSS), problems of vehicles and parking spots availability have appeared crucial. We define the system performance as the number of trips sold (to be maximized). BSS performance is currently improved by vehicle relocation with trucks. Our scope is to focus on self regulating systems through pricing incentives, avoiding physical station balancing. The question we are investigating in this thesis is the following: Can a management of the incentives increases significantly the performance of the vehicle sharing systems?

APA, Harvard, Vancouver, ISO, and other styles

47

Tusera, Alexandre. "De l'affectation linéaire appliquée au problème de routage dans une grille multidimensionnelle." Versailles-St Quentin en Yvelines, 1995. http://www.theses.fr/1995VERS0004.

Full text

Abstract:

Nous nous proposons, dans cette thèse, d'aborder le problème de routage dans une grille par une approche différente des méthodes classiques à la recuit simulé. Nous établissons le rapport entre le problème énoncé et l'affectation linéaire en d dimensions (dD-LAP), problème NP-difficile bien connu de la recherche opérationnelle. Nous étendons l'étude polyédrale du problème 3D-LAP au cas multidimensionnel en montrant l'accroissement de la complexité avec le nombre de dimensions. Parmi les différentes méthodes de résolution de ce problème, nous investiguons en détail les méthodes de sous-gradient, les plus adaptées compte tenu de la taille des problèmes envisagés ; notamment, nous introduisons deux heuristiques nouvelles pour le 3D-LAP: l'approximation locale et l'approximation globale. Toutes les deux sont basées sur la relaxation lagrangienne avec sous-gradient et sur la prise en compte de la structure polyédrale du 3D-LAP pour orienter la direction de recherche le long de la trajectoire du sous-gradient. Le polyèdre du problème est approximé localement/globalement par un nombre restreint de facettes. Donc il s'agit d'une approche encore inconnue dans la littérature, à notre connaissance: comment choisir un ensemble de facettes de cardinalité restreinte contenant des facettes "efficaces" parmi un nombre très grand (typiquement en nombre exponentiel pour un problème NP-difficile

APA, Harvard, Vancouver, ISO, and other styles

48

Darlay, Julien. "Analyse combinatoire de données : structures et optimisation." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00683651.

Full text

Abstract:

Cette thèse porte sur des problèmes d'exploration de données avec le point de vue de la recherche opérationnelle. L'exploration de données consiste en l'apprentissage de nouvelles connaissances à partir d'observations contenues dans une base de données. La nature des problèmes rencontrés dans ce domaine est proche de celle des problèmes de la recherche opérationnelle: grandes instances, objectifs complexes et difficulté algorithmique. L'exploration de données peut aussi se modéliser comme un problème d'optimisation avec un objectif partiellement connu. Cette thèse se divise en deux parties. La première est une introduction à l'exploration de données. Elle présente l'Analyse Combinatoire de Données (ACD), une méthode d'exploration de données issue de l'optimisation discrète. Cette méthode est appliquée à des données médicales originales et une extension aux problèmes d'analyse de temps de survie est proposée. L'analyse de temps de survie consiste à modéliser le temps avant un événement (typiquement un décès ou une rechute). Les heuristiques proposées utilisent des techniques classiques de recherche opérationnelle telles que la programmation linéaire en nombres entiers, la décomposition de problème, des algorithmes gloutons. La seconde partie est plus théorique et s'intéresse à deux problèmes combinatoires rencontrés dans le domaine de l'exploration de données. Le premier est un problème de partitionnement de graphes en sous-graphes denses pour l'apprentissage non supervisé. Nous montrons la complexité algorithmique de ce problème et nous proposons un algorithme polynomial basé sur la programmation dynamique lorsque le graphe est un arbre. Cet algorithme repose sur des résultats de la théorie des couplages. Le second problème est une généralisation des problèmes de couverture par les tests pour la sélection d'attributs. Les lignes d'une matrice sont coloriées en deux couleurs. L'objectif est de trouver un sous-ensemble minimum de colonnes tel que toute paire de lignes avec des couleurs différentes restent distinctes lorsque la matrice est restreinte au sous-ensemble de colonnes. Nous montrons des résultats de complexité ainsi que des bornes serrées sur la taille des solutions optimales pour différentes structures de matrices.

APA, Harvard, Vancouver, ISO, and other styles

49

Poirion, Pierre-Louis. "Programmation linéaire mixte robuste; Application au dimensionnement d'un système hybride de production d'électricité." Thesis, Paris, CNAM, 2013. http://www.theses.fr/2015CNAM0948/document.

Full text

Abstract:

Dans cette thèse, nous nous intéressons à l’optimisation robuste. Plus précisément,nous nous intéresserons aux problèmes linéaires mixtes bi-niveaux, c’est à dire aux problèmes dans lesquels le processus de décision est divisé en deux parties : dans un premier temps, les valeurs optimales des variables dites "de décisions" seront calculées ; puis, une fois que l’incertitude sur les données est levée, nous calculerons les valeurs des variables dites "de recours". Dans cette thèse, nousnous limiterons au cas où les variables de deuxième étape, dites "de recours", sontcontinues.Dans la première partie de cette thèse, nous nous concentrerons sur l’étudethéorique de tels problèmes. Nous commencerons par résoudre un problème linéairesimplifié dans lequel l’incertitude porte seulement sur le membre droit descontraintes, et est modélisée par un polytope bien particulier. Nous supposerons enoutre que le problème vérifie une propriété dite "de recours complet", qui assureque, quelles que soient les valeurs prises par les variables de dcisions, si ces dernières sont admissibles, alors le problème admet toujours une solution réalisable, et ce, quelles que soient les valeurs prises par les paramètres incertains. Nous verrons alors une méthode permettant, à partir d’un programme robuste quelconque, de se ramener à un programme robuste équivalent dont le problème déterministe associévérifie la propriété de recours complet. Avant de traiter le cas général, nous nouslimiterons d’abord au cas o les variables de décisions sont entières. Nous testeronsalors notre approche sur un problème de production. Ensuite, après avoir remarquéque l’approche développée dans les chapitres précédents ne se généralisait pasnaturellement aux polytopes qui n’ont pas des points extrmes 0-1, nous montreronscomment, en utilisant des propriétés de convexité du problème, résoudre le problème robuste dans le cas général. Nous en déduirons alors des résultats de complexité sur le problème de deuxième étape, et sur le problème robuste. Dans la suite de cette partie nous tenterons d’utiliser au mieux les informations probabilistes que l’on a sur les données aléatoires pour estimer la pertinence de notre ensemble d’incertitude.Dans la deuxième partie de cette thèse, nous étudierons un problème de conceptionde parc hybride de production d’électricité. Plus précisément, nous chercheronsà optimiser un parc de production électrique constitué d’éoliennes, de panneauxsolaires, de batteries et d’un générateur à diesel, destiné à répondre à unedemande locale d’énergie électrique. Il s’agit de déterminer le nombre d’éoliennes,de panneaux solaires et de batteries à installer afin de répondre à la demande pourun cot minimum. Cependant, les données du problème sont très aléatoires. En effet,l’énergie produite par une éolienne dépend de la force et de la direction du vent ; celle produite par un panneau solaire, de l’ensoleillement et la demande en électricité peut tre liée à la température ou à d’autres paramètres extérieurs. Pour résoudre ce problème, nous commencerons par modéliser le problème déterministeen un programme linéaire mixte. Puis nous appliquerons directement l’approche de la première partie pour résoudre le problème robuste associé. Nous montrerons ensuite que le problème de deuxième étape associé, peut se résoudre en temps polynomial en utilisant un algorithme de programmation dynamique. Enfin, nous donnerons quelques généralisations et améliorations pour notre problème
Robust optimization is a recent approach to study problems with uncertain datathat does not rely on a prerequisite precise probability model but on mild assumptionson the uncertainties involved in the problem.We studied a linear two-stage robustproblem with mixed-integer first-stage variables and continuous second stagevariables. We considered column wise uncertainty and focused on the case whenthe problem doesn’t satisfy a "full recourse property" which cannot be always satisfied for real problems. We also studied the complexity of the robust problemwhich is NP-hard and proved that it is actually polynomial solvable when a parameterof the problem is fixed.We then applied this approach to study a stand-alonehybrid system composed of wind turbines, solar photovoltaic panels and batteries.The aim was to determine the optimal number of photovoltaic panels, wind turbinesand batteries in order to serve a given demand while minimizing the total cost of investment and use. We also studied some properties of the second stage problem, in particular that the second stage problem can be solvable in polynomial time using dynamic programming

APA, Harvard, Vancouver, ISO, and other styles

50

Poirion, Pierre-Louis. "Programmation linéaire mixte robuste; Application au dimensionnement d'un système hybride de production d'électricité." Electronic Thesis or Diss., Paris, CNAM, 2013. http://www.theses.fr/2013CNAM0948.

Full text

Abstract:

Dans cette thèse, nous nous intéressons à l’optimisation robuste. Plus précisément,nous nous intéresserons aux problèmes linéaires mixtes bi-niveaux, c’est à dire aux problèmes dans lesquels le processus de décision est divisé en deux parties : dans un premier temps, les valeurs optimales des variables dites "de décisions" seront calculées ; puis, une fois que l’incertitude sur les données est levée, nous calculerons les valeurs des variables dites "de recours". Dans cette thèse, nousnous limiterons au cas où les variables de deuxième étape, dites "de recours", sontcontinues.Dans la première partie de cette thèse, nous nous concentrerons sur l’étudethéorique de tels problèmes. Nous commencerons par résoudre un problème linéairesimplifié dans lequel l’incertitude porte seulement sur le membre droit descontraintes, et est modélisée par un polytope bien particulier. Nous supposerons enoutre que le problème vérifie une propriété dite "de recours complet", qui assureque, quelles que soient les valeurs prises par les variables de dcisions, si ces dernières sont admissibles, alors le problème admet toujours une solution réalisable, et ce, quelles que soient les valeurs prises par les paramètres incertains. Nous verrons alors une méthode permettant, à partir d’un programme robuste quelconque, de se ramener à un programme robuste équivalent dont le problème déterministe associévérifie la propriété de recours complet. Avant de traiter le cas général, nous nouslimiterons d’abord au cas o les variables de décisions sont entières. Nous testeronsalors notre approche sur un problème de production. Ensuite, après avoir remarquéque l’approche développée dans les chapitres précédents ne se généralisait pasnaturellement aux polytopes qui n’ont pas des points extrmes 0-1, nous montreronscomment, en utilisant des propriétés de convexité du problème, résoudre le problème robuste dans le cas général. Nous en déduirons alors des résultats de complexité sur le problème de deuxième étape, et sur le problème robuste. Dans la suite de cette partie nous tenterons d’utiliser au mieux les informations probabilistes que l’on a sur les données aléatoires pour estimer la pertinence de notre ensemble d’incertitude.Dans la deuxième partie de cette thèse, nous étudierons un problème de conceptionde parc hybride de production d’électricité. Plus précisément, nous chercheronsà optimiser un parc de production électrique constitué d’éoliennes, de panneauxsolaires, de batteries et d’un générateur à diesel, destiné à répondre à unedemande locale d’énergie électrique. Il s’agit de déterminer le nombre d’éoliennes,de panneaux solaires et de batteries à installer afin de répondre à la demande pourun cot minimum. Cependant, les données du problème sont très aléatoires. En effet,l’énergie produite par une éolienne dépend de la force et de la direction du vent ; celle produite par un panneau solaire, de l’ensoleillement et la demande en électricité peut tre liée à la température ou à d’autres paramètres extérieurs. Pour résoudre ce problème, nous commencerons par modéliser le problème déterministeen un programme linéaire mixte. Puis nous appliquerons directement l’approche de la première partie pour résoudre le problème robuste associé. Nous montrerons ensuite que le problème de deuxième étape associé, peut se résoudre en temps polynomial en utilisant un algorithme de programmation dynamique. Enfin, nous donnerons quelques généralisations et améliorations pour notre problème
Robust optimization is a recent approach to study problems with uncertain datathat does not rely on a prerequisite precise probability model but on mild assumptionson the uncertainties involved in the problem.We studied a linear two-stage robustproblem with mixed-integer first-stage variables and continuous second stagevariables. We considered column wise uncertainty and focused on the case whenthe problem doesn’t satisfy a "full recourse property" which cannot be always satisfied for real problems. We also studied the complexity of the robust problemwhich is NP-hard and proved that it is actually polynomial solvable when a parameterof the problem is fixed.We then applied this approach to study a stand-alonehybrid system composed of wind turbines, solar photovoltaic panels and batteries.The aim was to determine the optimal number of photovoltaic panels, wind turbinesand batteries in order to serve a given demand while minimizing the total cost of investment and use. We also studied some properties of the second stage problem, in particular that the second stage problem can be solvable in polynomial time using dynamic programming

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Optimisation combinatoire et linéaire'

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