Consider the problem of maximizing the revenue generated by tolls set on a subset <p>of arcs of a transportation network, where origin-destination flows (commodities) are assigned to shortest paths with respect to the sum of tolls and initial costs. <p>This thesis is concerned with a particular case of the above problem, in which all toll arcs are connected and constitute a path, as occurs on highways. Further, as toll levels are usually computed using the highway entry and exit points, a complete toll subgraph is considered, where each toll arc corresponds to a toll subpath. Two <p>variants of the problem are studied, with or without specific constraints linking together the tolls on the arcs. <p>The problem is modelled as a linear mixed integer program, and proved to be NP-hard. Next, several classes of valid inequalities are proposed, which strengthen important constraints of the initial model. Their efficiency is first shown theoretically, as these are facet defining for the restricted one and two commodity problems. <p>Also, we prove that some of the valid inequalities proposed, together with several <p>constraints of the linear program, provide a complete description of the convex hull <p>of feasible solutions for a single commodity problem. Numerical tests have also been conducted, and highlight the real efficiency of the valid inequalities for the multi-commodity case. Finally, we point out the links between the problem studied in the thesis and a more classical design and pricing problem in economics. /<p><p><p>Considérons le problème qui consiste à maximiser les profits issus de la tarification d’un sous-ensemble d’arcs d’un réseau de transport, où les flots origine-destination (produits) sont affectés aux plus courts chemins par rapport aux tarifs et aux coûts initiaux. Cette thèse porte sur une structure de réseau particulière du problème ci-dessus, dans laquelle tous les arcs tarifables sont connectés et forment un chemin, <p>comme c’est le cas sur une autoroute. Étant donné que les tarifs sont habituellement déterminés selon les points d’entrée et de sortie sur l’autoroute, nous considérons un sous-graphe tarifable complet, où chaque arc correspond en réalité à un sous-chemin. Deux variantes de ce problème sont étudiées, avec ou sans contraintes <p>spécifiques reliant les niveaux de tarifs sur les arcs. <p>Ce problème peut être modélisé comme un programme linéaire mixte entier. Nous prouvons qu’il est <p>NP-difficile. Plusieurs familles d’inégalités valides sont ensuite proposées, celles-ci renforçant certaines contraintes du modèle initial. Leur efficacité est d’abord démontrée de manière théorique, puisqu’il s’agit de facettes <p>des problèmes restreints à un ou deux produits. Certaines des inégalités valides proposées, ainsi que plusieurs contraintes du modèle initial, permettent aussi de donner une description complète de l’enveloppe convexe des solutions réalisables d’un problème restreint à un seul produit. Des tests numériques ont également <p>été menés, et mettent en évidence l’efficacité réelle des inégalités valides pour le problème général à plusieurs produits. Enfin, nous soulignons les liens entre le problème de tarification de réseau étudié dans cette thèse et un problème plus classique de tarification de produits en gestion. <p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Dans le cadre de cette thèse, nous nous sommes intéressés à la mise en œuvre d'algorithmes auto-adaptatifs d'Intelligence Collective pour la résolution de problèmes d'optimisation modélisés dans un langage de Programmation par contraintes (PPC). Nous avons porté une attention particulière à la famille d'algorithmes de type " Ant Colony Optimization " (ACO). Nous avons développé trois contributions, à savoir : (1) Intégration des algorithmes de type ACO dans un langage de programmation par contraintes pour la résolution de problèmes de satisfaction de contraintes; (2) Proposition d'un algorithme hybride et générique où ACO est couplé à une approche complète pour résoudre des problèmes d'optimisation combinatoires (3) Proposition d'une stratégie capable d'adapter dynamiquement les paramètres de ACO.

.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte. / We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.

L'objectif de la thèse est de créer et développer de nouvelles méthodes de résolution efficaces des problèmes combinatoires en configuration des lignes de fabrication. Deux problèmes ont été particulièrement étudiés: le problème d'équilibrage et de choix d'équipement pour des lignes dédiées et le problème de minimisation des coûts de changements de séries pour des lignes multi-produits. Une solution du premier problème consiste en une affectation admissible des ressources à un nombre de stations à déterminer de sorte que le coût total soit minimal. Afin de résoudre ce problème, nous l'avons réduit au problème de partition d'ensemble et l'avons résolu par des heuristiques gloutonnes et une méthode exacte de génération de contraintes. Les expérimentations sur différentes instances ont montré que la nouvelle approche de résolution surclasse les approches antérieures de la littérature en termes de qualité de solution et de temps de calcul. Pour le second problème deux critères sont considérés lexicographiquement : la minimisation du nombre de stations et la minimisation du coût de changement de séries. Nous avons examiné successivement les cas d'exécution parallèle et séquentielle des opérations. Des solutions approchées ont été trouvées par des heuristiques gloutonnes. Ensuite, nous avons proposé deux modèles de programmation linéaire en nombres entiers (PLNE) afin de trouver le nombre de stations minimal et ensuite d'obtenir le coût de changement de séries minimal. Les résultats des expérimentations sur ces nouveaux problèmes se sont avérés prometteurs à la fois en termes de qualité de solution et de temps de calcul. / The objective of this thesis is to create and develop new effective solution methods for production line configuration problems. Two problems were studied: the equipment selection and balancing problem for dedicated lines and the setup cost minimization problem for multi-product lines. A solution for the first problem consists in a feasible assignment of the resources to an unknown number of stations so that the total cost is minimized. In order to solve this problem, we reduced it to the set partitioning problem and solved it by greedy heuristics and an exact method of constraint generation. The computer experiments on different problem instances showed that the new solution approach outperforms the previous methods from the literature both in terms of solution quality and computational time. For the second problem two criteria were considered lexicographically: the minimization of the number of stations and the minimization of the total setup cost. We examined successively the cases with parallel and sequential execution of operations. Approximate solutions were found by greedy heuristics. Then, we proposed two integer programming models in order to obtain the minimal number of stations and then the minimal setup cost. The experimental results for this new problem proved to be promising both in terms of solution quality and computational time.

Cette thèse concerne l'étude de l'algorithmique et de la complexité des communications dans les réseaux radio. En particulier, nous nous sommes intéressés au problème de rassembler les informations des sommets d'un réseau radio en un noeud central.<br />Ce problème est motivé par une question de France Telecom (Orange Labs) "comment amener Internet dans les villages".<br />Les sommets représentent les maisons des villages qui communiquent entre elles par radio, le but étant d'atteindre une passerelle centrale connectée à Internet par une liaison satellite. Le même problème se rencontre dans les réseaux de senseurs où il s'agit de collecter les informations des senseurs dans une station de base.<br />Une particularité des réseaux radio est que la distance de transmission est limité et que les transmissions interfèrent entre elles (phénomènes d'interférences). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s'ils sont à distance au plus dT et qu'un noeud interfère avec un autre si leur distance est au plus dI. Les distances sont considérées dans un graphe représentant le réseau. Une étape de communication consistera donc en un ensemble de transmissions compatibles (n'interférant pas).<br />Notre objectif est de trouver le nombre minimum d'étapes nécessaires pour réaliser un tel rassemblement et de concevoir des algorithmes réalisant ce minimum. Pour des topologies particulières comme le chemin et la grille, nous avons établi des résultats optimaux ou quasi optimaux.<br />Nous avons aussi considéré le cas systolique (ou continu) où on veut maximiser le debit offert à chaque noeud.

Un réseau de télécommunication optique est configuré de manière à répondre à<br />une demande donnée, avec un certain objectif. Avec le temps, la demande<br />d'exploitation du réseau change. C'est dans ce contexte que se pose le<br />problème de la reconfiguration: être capable de changer la configuration du<br />réseau de manière à l'adapter à des nouvelles demandes. Pour ce faire il faut<br />généralement interrompre totalement ou partiellement le trafic. Étant données<br />les quantités de données y circulant, il n'est guère envisageable d'arrêter le<br />réseau. De nombreux paramètres sont à prendre en compte afin de déterminer ce<br />que sera une bonne solution, et plusieurs métriques peuvent être utilisées<br />pour mesurer la qualité d'une solution.<br /><br />Dans une première partie, nous nous intéressons au problème de la<br />reconfiguration comme problème d'optimisation mono-objectif. Nous proposons un<br />modèle mathématique permettant de représenter le problème. Cependant, le<br />résoudre exactement peut être très coûteux en temps de calcul. Nous proposons<br />également une heuristique gloutonne et une heuristique basée sur le recuit<br />simulé. Les solutions obtenues présentent différentes caractéristiques selon<br />la métrique optimisée. L'algorithme glouton est rapide et trouve des solutions<br />décentes. L'algorithme du recuit simulé obtient des solutions qui sont<br />comparables aux solutions optimales.<br /><br />Dans une seconde partie, nous nous intéressons à l'aspect multiobjectif du<br />problème. Il consiste à considérer simultanément les différentes métriques et<br />rechercher un ensemble de solutions représentant différents compromis<br />intéressants. Puis nous proposons un algorithme basé sur notre modélisation<br />mathématique. Nous adaptons également un algorithme évolutif. Donner une<br />certaine flexibilité par rapport à une métrique permet généralement<br />d'améliorer de manière significative les solutions obtenues par rapport aux<br />autres métriques.

Le bon déroulement d'un processus de gestion des connaissances passe par l'utilisation de méthodes efficaces de visualisation qui permettent une compréhension aisée des différents modèles de connaissances utilisés. Les retours d'expériences avec le système de gestion des connaissances Atanor, qui est orienté vers le déploiement des connaissances dans un contexte opérationnel portant sur des systèmes complexes, ont montré que le modèle d'arbres actuellement utilisé pour la visualisation des modèles de connaissances n'est pas intuitif. Des redondances de sommets trop nombreuses peuvent entraîner des difficultés de lecture et cacher des caractéristiques importantes. Pour résoudre ces problèmes nous proposons le modèle Graph'Atanor qui est basé sur des graphes en niveaux.<br>Le passage au modèle de graphes pose le problème de sa représentation visuelle. Les tracés doivent rester lisibles et compréhensibles par les utilisateurs. Ceci se traduit notamment par le respect de critères esthétiques qui permettent de modéliser un problème d'optimisation combinatoire consistant à trouver un ordre optimal des sommets dans chaque niveau. Pour résoudre ce problème, nous avons développé un algorithme génétique qui possède deux particularités : deux opérateurs de croisements spécifiques et une hybridation par une recherche locale. Les expérimentations montrent que pour des graphes de taille standard, l'algorithme génétique donne de meilleurs résultats que les autres méthodes que nous connaissons. La comparaison des modèles de représentation des connaissances sur un exemple industriel montre qu'en plus de faciliter la lecture, Graph'Atanor permet de facilement suivre la trace des utilisateurs et de mettre en avant les sommets critiques.

Le problème de la recherche d'un élément dans un ensemble donne est un des problèmes fondamentaux en informatique non numérique, lie, par exemple, aux bases de données, a la compilation, a l'optimisation combinatoire, etc... Dans cette thèse nous abordons le problème de la recherche dans des ensembles ordonnes et quelques problèmes qui lui sont lies. Une matrice est dite triée si elle possédé une relation d'ordre total sur chaque ligne et chaque colonne. Un cas particulier est l'ensemble des matrices définies par x+y, la somme cartésienne de deux vecteurs tries. Après un tour d'horizon des problèmes de la sélection, de la recherche et du tri sur des ensembles de la forme x=y, nous démontrons des bornes inférieures et introduisons des bornes supérieures pour les problèmes de la recherche et de la sélection. Nous proposons, en outre, plusieurs algorithmes parallèles pour la recherche dans x+y. Ensuite nous montrons comment appliquer ces résultats a la resolution en parallèle du problème de décision du sac-a-dos, ou, étant donnes plusieurs objets et un sac de capacité définie a remplir, on veut décider s'il existe une combinaison des objets qui remplit exactement le sac. Des algorithmes avec une accélération optimale sont introduits pour divers modèles de machines parallèles a mémoire partagée et distribuée. Pour ce problème les approches existantes se ramènent soit a la recherche dans x+y, soit a la traversée d'un espace combinatoire a l'aide de la technique du Branch & Bound. Cette dernière technique est aussi discutée dans ce travail, ou nous présentons un algorithme de Branch & Bound en vue de la resolution de problèmes d'optimisation combinatoire sur la connexion machine. Enfin, toujours dans le domaine de l'optimisation combinatoire, nous étudions le comportement de l'algorithme de recuit simule. Nous prouvons que, malgré la confiance qu'il inspire et sa grande utilisation pour des application

Cette thèse, fruit d'un contrat de recherche avec Générale des Eaux,<br />porte sur le problème de tournées de service multi-périodes avec fenêtres de temps et flotte limitée. Nous proposons plusieurs méthodes de résolution approchées, ainsi qu'une méthode optimale. La méthode optimale est basée sur la génération de colonnes. Une des méthodes approchées est un algorithme mémétique basé sur une heuristique également développée dans cette thèse. Enfin, la méthode optimale est dérivée en méthode approchée par l'utilisation d'une heuristique pour la résolution du sous-problème.<br />Les algorithmes proposés permettent d'apporter des solutions efficaces à des problèmes comportant jusqu'à 300 clients, dans des temps variant de quelques secondes à quelques dizaines de minutes. Dans un second temps, nous appliquons ces méthodes à des scénarios issus de problématiques réelles, dans une logique d'aide à la décision.