Submitted by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:31:58Z No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:35:15Z (GMT) No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-17T17:35:15Z (GMT). No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2011-02-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work considers three relevant NP-hard problems. The firstone is the one-dimensional cutting stock problem in which the non-used material in the cutting patterns may be used in the future. For this problem we analyze the existing mathematical models, propose new models, design a heuristic and two metaheuristic approaches, being their performances improved by using parallel programming, and solve instances, practical and randomly generated, from the literature. The computational experiments were quite good for all tested instances. The second problem we consider is the stable roommates problem (a variant of the stable matching problem). For this we give two mathematical programming models, sequential and parallel implementations of a Tabu Search, and a Branch-andBound. Also, we report computational experiments to instances of the problem. The last problem we consider is the compartmentalized knapsack problem (a generalization of the knapsack problem) for which we analyze a quadratic integer model and give a linear integer model. We design a greedy heuristic and a GRASP algorithm, that uses path-relinking, and solve randomly generated instances. All parallel implementations use Graphics Processing Units (GPUs). / Este trabalho considera três problemas, NP-difíceis, relevantes de estudo em otimização combinatória. O primeiro deles é o problema de corte uni-dimensional de objetos, onde o material não usado pelos padrões de corte pode ser usado no futuro. Para este problema analisamos os modelos matemáticos existentes, propomos novos modelos, projetamos uma heurística construtiva e duas metaheurísticas, sendo seus desempenhos melhorados com programação paralela, e resolvemos instâncias, práticas e aleatórias, encontradas na literatura; sendo os experimentos computacionais muito bons para todas as intânciastestadas.Osegundoproblemaqueconsideramoséoproblemadoscompanheiros estáveis (stable roommates problem), uma variante do problema de emparelhamento estável (stable matching problem). Para este propomos dois modelos matemáticos, uma implementação sequencial e uma paralela de uma Tabu Search, e um Branch-andBound. Também reportamos experimentos computacionais para instâncias do problema. O último problema considerado é o da mochila compartimentada (uma generalização do problema clássico da mochila), para o qual analisamos uma modelagem quadrática inteira e propomos um modelo linear inteiro; também projetamos uma heurística gulosa, um algoritmo GRASP, que usa path-relinking, e resolvemos intâncias geradas aleatóriamente. Todas as implementações em paralelo usam unidades de processamento gráfico (Graphics Processing Units, GPUs).

La localisation des personnes et des objets à l’intérieur des bâtiments basée sur les réseaux WLAN connaît un intérêt croissant depuis quelques années ; ce système peut être un parfait complément pour fournir des informations de localisation statique ou dynamique dans des environnements où les techniques de positionnement telles que GPS ne sont pas efficaces. Le manuscrit de thèse propose une nouvelle approche pour définir un système WLAN de positionnement indoor (WLAN-IPS) comme un problème d'optimisation combinatoire afin de garantir à la fois une qualité de communication et une minimisation de l'erreur de positionnement via le réseau. Cette approche est caractérisée par plusieurs questions difficiles que nous abordons en trois étapes.Dans un premier temps, nous avons conçu un réseau WLAN-IPS et mis en œuvre une plateforme de test. Nous avons examiné la performance du système sous diverses contraintes expérimentales et nous nous sommes penchés sur l'analyse des relations entre l'erreur de positionnement et les facteurs environnementaux externes. Ces relations ont permis de proposer des indicateurs pour évaluer l'erreur de positionnement. Ensuite nous avons proposé un modèle physique qui définit tous les paramètres majeurs rencontrés en WLAN-IPS à partir de la littérature. L'objectif initial des infrastructures WLAN étant de fournir un accès radio de qualité au réseau, nous avons introduit un objectif supplémentaire qui est de minimiser l'erreur de localisation dans le contexte IPS. Deux indicateurs principaux ont été définis afin d'évaluer la qualité de service (QoS) et l'erreur de localisation pour LBS (Location-Based Services). Enfin après avoir défini la formulation mathématique du problème d'optimisation et les indicateurs clés de performance, nous avons proposé un algorithme mono-objectif et un algorithme multicritère basés sur Tabu Search et Variable Neighborhood Search pour fournir des bonnes solutions en temps raisonnable. Les simulations montrent que ces deux algorithmes sont très efficaces pour le problème d'optimisation que nous avons posé. / Indoor Positioning Systems (IPS) using the existing WLAN have won growing interest in the last years, it can be a perfect supplement to provide location information of users in indoor environments where other positioning techniques such as GPS, are not much effective. The thesis manuscript proposes a new approach to define a WLAN-based indoor positioning system (WLAN-IPS) as a combinatorial optimization problem to guarantee the requested communication quality while optimizing the positioning error. This approach is characterised by several difficult issues we tackled in three steps.At first, we designed a WLAN-IPS and implemented it as a test framework. Using this framework, we looked at the system performance under various experimental constraints. Through these experiments, we went as far as possible in analysing the relationships between the positioning error and the external environmental factors. These relationships were considered as evaluation indicators of the positioning error. Secondly, we proposed a model that defines all major parameters met in the WLAN-IPS from the literature. As the original purpose of the WLAN infrastructures is to provide radio communication access, we introduced an additional purpose which is to minimize the location error within IPS context. Two main indicators were defined in order to evaluate the network Quality of Service (QoS) and the positioning error for Location-Based Service (LBS). Thirdly, after defining the mathematical formulation of the optimisation problem and the key performance indicators, we proposed a mono-objective algorithm and a multi-objective algorithm which are based on Tabu Search metaheuristic to provide good solutions within a reasonable amount of time. The simulations demonstrate that these two algorithms are highly efficient for the indoor positioning optimization problem.

Le travail présenté dans ce mémoire étudie et propose des modèles de calcul parallèles de type cellulaire pour traiter différents problèmes d’optimisation NP-durs définis dans l’espace euclidien, et leur implantation sur des processeurs graphiques multi-fonction (Graphics Processing Unit; GPU). Le but est de pouvoir traiter des problèmes de grande taille tout en permettant des facteurs d’accélération substantiels à l’aide du parallélisme massif. Les champs d’application visés concernent les systèmes embarqués pour la stéréovision de même que les problèmes de transports définis dans le plan, tels que les problèmes de tournées de véhicules. La principale caractéristique du modèle cellulaire est qu’il est fondé sur une décomposition du plan en un nombre approprié de cellules, chacune comportant une part constante de la donnée, et chacune correspondant à une unité de calcul (processus). Ainsi, le nombre de processus parallèles et la taille mémoire nécessaire sont en relation linéaire avec la taille du problème d’optimisation, ce qui permet de traiter des instances de très grandes tailles.L’efficacité des modèles cellulaires proposés a été testée sur plateforme parallèle GPU sur quatre applications. La première application est un problème d’appariement d’images stéréo. Elle concerne la stéréovision couleur. L’entrée du problème est une paire d’images stéréo, et la sortie une carte de disparités représentant les profondeurs dans la scène 3D. Le but est de comparer des méthodes d’appariement local selon l’approche winner-takes-all et appliquées à des paires d’images CFA (color filter array). La deuxième application concerne la recherche d’améliorations de l’implantation GPU permettant de réaliser un calcul quasi temps-réel de l’appariement. Les troisième et quatrième applications ont trait à l’implantation cellulaire GPU des réseaux neuronaux de type carte auto-organisatrice dans le plan. La troisième application concerne la génération de maillages structurés appliquée aux cartes de disparité afin de produire des représentations compressées des surfaces 3D. Enfin, la quatrième application concerne le traitement d’instances de grandes tailles du problème du voyageur de commerce euclidien comportant jusqu’à 33708 villes.Pour chacune des applications, les implantations GPU permettent une accélération substantielle du calcul par rapport aux versions CPU, pour des tailles croissantes des problèmes et pour une qualité de résultat obtenue similaire ou supérieure. Le facteur d’accélération GPU par rapport à la version CPU est d’environ 20 fois plus vite pour la version GPU sur le traitement des images CFA, cependant que le temps de traitement GPU est d’environ de 0,2s pour une paire d’images de petites tailles de la base Middlebury. L’algorithme amélioré quasi temps-réel nécessite environ 0,017s pour traiter une paire d’images de petites tailles, ce qui correspond aux temps d’exécution parmi les plus rapides de la base Middlebury pour une qualité de résultat modérée. La génération de maillages structurés est évaluée sur la base Middlebury afin de déterminer les facteurs d’accélération et qualité de résultats obtenus. Le facteur d’accélération obtenu pour l’implantation parallèle des cartes auto-organisatrices appliquée au problème du voyageur de commerce et pour l’instance avec 33708 villes est de 30 pour la version parallèle. / The work presented in this PhD studies and proposes cellular computation parallel models able to address different types of NP-hard optimization problems defined in the Euclidean space, and their implementation on the Graphics Processing Unit (GPU) platform. The goal is to allow both dealing with large size problems and provide substantial acceleration factors by massive parallelism. The field of applications concerns vehicle embedded systems for stereovision as well as transportation problems in the plane, as vehicle routing problems. The main characteristic of the cellular model is that it decomposes the plane into an appropriate number of cellular units, each responsible of a constant part of the input data, and such that each cell corresponds to a single processing unit. Hence, the number of processing units and required memory are with linear increasing relationship to the optimization problem size, which makes the model able to deal with very large size problems.The effectiveness of the proposed cellular models has been tested on the GPU parallel platform on four applications. The first application is a stereo-matching problem. It concerns color stereovision. The problem input is a stereo image pair, and the output a disparity map that represents depths in the 3D scene. The goal is to implement and compare GPU/CPU winner-takes-all local dense stereo-matching methods dealing with CFA (color filter array) image pairs. The second application focuses on the possible GPU improvements able to reach near real-time stereo-matching computation. The third and fourth applications deal with a cellular GPU implementation of the self-organizing map neural network in the plane. The third application concerns structured mesh generation according to the disparity map to allow 3D surface compressed representation. Then, the fourth application is to address large size Euclidean traveling salesman problems (TSP) with up to 33708 cities.In all applications, GPU implementations allow substantial acceleration factors over CPU versions, as the problem size increases and for similar or higher quality results. The GPU speedup factor over CPU was of 20 times faster for the CFA image pairs, but GPU computation time is about 0.2s for a small image pair from Middlebury database. The near real-time stereovision algorithm takes about 0.017s for a small image pair, which is one of the fastest records in the Middlebury benchmark with moderate quality. The structured mesh generation is evaluated on Middlebury data set to gauge the GPU acceleration factor and quality obtained. The acceleration factor for the GPU parallel self-organizing map over the CPU version, on the largest TSP problem with 33708 cities, is of 30 times faster.

Cette thèse porte sur la planification du personnel en accordant une attention particulière à l'aspect humain et aux facteurs ergonomiques dans le domaine de la production. Un certain nombre de modèles mathématiques sont présentés pour formuler les problèmes d'ordonnancement et de planification du personnel étudié. Concernant les modèles de planification, la productivité du système de fabrication et le bien-être des travailleurs sont ciblés. De cette manière, une méthode d'affectation des travailleurs est présentée pour réduire le temps de production et une méthode d'ordonnancement pour la rotation des tâches est présentée afin d’équilibrer la charge de travail des opérateurs. À cet effet, une analyse ergonomique est effectuée sur les postes de travail du système de production étudié. Cette analyse aboutit à l'évaluation des postes du travail suivant la convention dite des feux de circulation, c'est-à-dire que les postes sont classés dans les niveaux de charge faible, moyen et élevé qui sont représentés respectivement par les couleurs verte, jaune et rouge. Une approche mathématique est développée pour convertir ces résultats en valeurs numériques, car les paramètres quantitatifs sont plus applicables pour l'optimisation de la planification. Une programmation multi-objectifs est proposée pour optimiser les deux objectifs mentionnés du problème d'ordonnancement de tournée du personnel étudié. Les méthodes d'agrégation linéaire et de ε-contrainte sont appliquées pour résoudre ce modèle d'optimisation. En outre, cette thèse présente une nouvelle variante du problème d'affectation appelé problème d'affectation généralisée par séquence qui est défini pour la planification du personnel dans un système combiné constitué des postes de travail en série et en parallèle. Il est prouvé que ce problème d'optimisation combinatoire est NP-difficile et les méthodes exactes ne sont pas capables de résoudre les instances de grande taille. Ainsi, trois méthodes approchées composées de deux approches matheuristiques et une heuristique hybride sont développées pour résoudre ce problème. Les méthodes matheuristiques sont basées sur la décomposition de la formulation pour simplifier le modèle principal en deux ou plusieurs modèles plus petits. La troisième méthode est une heuristique gloutonne combinée à une recherche locale. En outre, dans la dernière étape de cette thèse, la planification des ressources humaines pour un système de soins à domicile est formulée mathématiquement. Selon la structure du système, une intégration des problèmes d'affectation et de tournées de véhicules est présentée. Enfin, une approche matheuristique en trois étapes est proposée pour résoudre ce problème d'optimisation combinatoire. / This thesis concerns the human resource planning by paying a special attention to the human aspect and ergonomic factors in the manufacturing domain. A number of mathematical models are presented to formulate the studied workforce scheduling and planning problems. In the planning models, the productivity of the manufacturing system and the well-being of the workers are targeted. In this way, a worker assignment approach is presented to reduce the production time and a job rotation scheduling approach is presented to balance the workloads on the operators. For this purpose, an ergonomic analysis is carried out on the jobs of the studied production system. This analysis results in the traffic light evaluation for the jobs, i.e., the jobs are categorized into the low, medium and high workload levels which are presented respectively by the green, yellow and red colors. A mathematical approach is developed to convert these outputs to the numerical values, because the quantitative parameters are more applicable for the optimization of the planning. A multi-objective programming is proposed to optimize two mentioned objectives of the studied workforce scheduling problem. Both linear aggregation and epsilon-constraint methods are applied to solve this optimization model. Furthermore, this thesis presents a novel variant of the assignment problem called sequencing generalized assignment problem which is defined for workforce scheduling in a combined system consisting of the jobs in series and in parallel. It is proved that this combinatorial optimization problem is NP-hard and the exact methods are not able to solve the large-scale instances. Hence, three approximate methods consisting of two matheuristic and a hybrid heuristic approaches are developed to solve it. The matheuristic methods are based on the decomposition of the formulation to break down and simplify the main model into two or more smaller models. The third method is a greedy heuristic combined with a local search. The efficiency of the three mentioned methods is evaluated by various instances of different sizes. Moreover, in the last step of this thesis, the human resource planning for a home healthcare system is formulated mathematically. According to the structure of the system, an integration of the worker assignment and vehicle routing problems is presented. Finally, a three-steps matheuristic approach is proposed to solve this combinatorial optimization problem.

Dans la présente thèse de doctorat je présente des résultats concernant des modèles désordonnés et frustrés venant de la physique statistique et de l'optimisation combinatoire. Comme application de la théorie des verres de spins, j'étudie le modèle de Blume, Emery et Griffiths désordonné et frustré. Ce modèle est traité dans l'approximation de champ moyen dans le cadre de la méthode des répliques A l'aide de l'Ansatz symétrique dans les répliques je présente une solution numérique complète puis je discute des effets de brisure de cette symétrie La stabilité de la solution symétrique a été Rudik et les régions instables identifiées Le diagramme de phase exhibe des transitions de premier et de second ordre. Le point tricritique persiste dans le modèle frustré, Ce qui est en accord avec des travaux antérieurs une version du modèle BEG avec un potentiel chimique désordonné a également été étudiée. les calculs confirment que le point tricritique apparaît à plus basse température quand il y a du désordre. Ensuite je considère le problème de la bipartition d'un graphe. Ce problème correspond du point de vue de la physique statistique h un verre de spins soumis h une contrainte d'aimantation totale nulle. je considère les propriétés statistiques des solutions de faible énergie engendrées par des algorithmes heuristiques. de tels algorithme sont en général conçus pour résoudre des problèmes d'optimisation combinatoire qui sont NP- difficiles. Plusieurs heuristiques ont 60 implémentées pour le problème de la bipartition de graphe. des lois d'échelle ont été obtenues : en particulier la moyenne et la variance du coût obéissent A une loi linéaire en N. Par conséquent le coût obtenu par des heuristiques est une quantité auto-moyennante. je suggère que cette propriété est générale valable aussi pour les solutions aléatoires pour les solutions quasi-optimales et pour les solutions optimales. En outre je propose une procédure pour comparer des algorithmes heuristiques. Cette procédure tient compte de la qualité de la solution aussi bien que du temps de calcul utilisé. Dans la troisième partie de ma thèse j'ai étudié en détail les propriétés h température nulle des verres de spins sur des graphes aléatoires lacunaires avec une coordination fixe. les verres de spins sur de tels graphes peuvent être considérés comme une approximation aux vrais verres de spins qui est plus réaliste que le modèle de Sherrington et Kirkpatrick. J'ai conçu un nouvel algorithme pour trouver les états fondamentaux. Aussi je teste numériquement une conjecture de Banavar, Sherrington et Sourlas qui donne la densité d'énergie du fondamental dans la limite de grande taille en fonction de la coordination. La distribution du paramètre d'ordre se révèle être non triviale et les données présentent une forte indication de la présence d'ultramétricité pour toutes les valeur de la coordination. Ces résultats confirment que les propriétés particulières des verres de spin, déduites an niveau de l'approximation de champ moyen dans le cadre du modèle de Sherrington et Kirkpatrick, sont aussi présentes pour des modèles plus réalistes comme les verres de spins sur des graphes aléatoires lacunaires avec une coordination fixe.

The inapproximability for NP-hard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation. Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems. In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following: For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon. The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull. For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level SA+ relaxations. We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology. Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicate-P constraint satisfaction problems over q-ary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution. We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the level-d SDP relaxation.

The inapproximability for NP-hard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation. Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems. In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following: For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon. The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull. For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level SA+ relaxations. We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology. Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicate-P constraint satisfaction problems over q-ary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution. We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the level-d SDP relaxation.

Afin d'enrichir les données de corpus bilingues parallèles, il peut être judicieux de travailler avec des corpus dits comparables. En effet dans ce type de corpus, même si les documents dans la langue cible ne sont pas l'exacte traduction de ceux dans la langue source, on peut y retrouver des mots ou des phrases en relation de traduction. L'encyclopédie libre Wikipédia constitue un corpus comparable multilingue de plusieurs millions de documents. Notre travail consiste à trouver une méthode générale et endogène permettant d'extraire un maximum de phrases parallèles. Nous travaillons avec le couple de langues français-anglais mais notre méthode, qui n'utilise aucune ressource bilingue extérieure, peut s'appliquer à tout autre couple de langues. Elle se décompose en deux étapes. La première consiste à détecter les paires d’articles qui ont le plus de chance de contenir des traductions. Nous utilisons pour cela un réseau de neurones entraîné sur un petit ensemble de données constitué d'articles alignés au niveau des phrases. La deuxième étape effectue la sélection des paires de phrases grâce à un autre réseau de neurones dont les sorties sont alors réinterprétées par un algorithme d'optimisation combinatoire et une heuristique d'extension. L'ajout des quelques 560~000 paires de phrases extraites de Wikipédia au corpus d'entraînement d'un système de traduction automatique statistique de référence permet d'améliorer la qualité des traductions produites. Nous mettons les données alignées et le corpus extrait à la disposition de la communauté scientifique. / Working with comparable corpora can be useful to enhance bilingual parallel corpora. In fact, in such corpora, even if the documents in the target language are not the exact translation of those in the source language, one can still find translated words or sentences. The free encyclopedia Wikipedia is a multilingual comparable corpus of several millions of documents. Our task is to find a general endogenous method for extracting a maximum of parallel sentences from this source. We are working with the English-French language pair but our method -- which uses no external bilingual resources -- can be applied to any other language pair. It can best be described in two steps. The first one consists of detecting article pairs that are most likely to contain translations. This is achieved through a neural network trained on a small data set composed of sentence aligned articles. The second step is to perform the selection of sentence pairs through another neural network whose outputs are then re-interpreted by a combinatorial optimization algorithm and an extension heuristic. The addition of the 560~000 pairs of sentences extracted from Wikipedia to the training set of a baseline statistical machine translation system improves the quality of the resulting translations. We make both the aligned data and the extracted corpus available to the scientific community.

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers d'un réseau de transport. Pour se rendre à leurs destinations, les usagers font un choix de route et utilisent des arcs sur lesquels nous imposons des tarifs. Chaque route est caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème a surtout été abordé sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale se voient attribuer une mesure positive de flot. Le modèle déterministe se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques. Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques de l'affectation logit et démontrons la validité de règles de simplification de la topologie du réseau qui permettent de réduire la dimension du problème sans en modifier la solution. Nous établissons ensuite l'unimodalité du problème pour une vaste gamme de topologies et nous généralisons certains de nos résultats au problème de la tarification d'une ligne de produits. Dans le deuxième article, nous abordons le problème d'un point de vue numérique pour le cas avec plusieurs paires origine-destination. Nous développons des algorithmes qui exploitent l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modèles combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte où la sensibilité au prix d'un usager est aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons que l'utilisation d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons plus particulièrement la contribution au revenu des différents groupes d'usagers. / The network pricing problem consists in finding tolls to set on a subset of a network's arcs, so to maximize a revenue expression. A fixed demand of commuters, going from their origins to their destinations, is assumed. Each commuter chooses a path of minimal "disutility", a measure of discomfort associated with the use of a path and which takes into account fixed costs and tolls. A deterministic modelling of commuter behaviour is mostly found in the literature, according to which positive flow is only assigned to \og shortest\fg\: paths. Even though the determinist pricing model is amenable to global optimization by the use of enumeration techniques, it has often been criticized for its lack of realism. In this thesis, we consider a probabilistic extension of this model involving a logit dicrete choice model. This more realistic model is non-linear and non-concave, but still possesses strong combinatorial features. Our analysis spans three separate articles. In the first we tackle the problem from a theoretical perspective for the case of a single origin-destination pair and develop a first order analysis that exploits the logit assignment analytical properties. We show the validity of simplification rules to the network topology which yield a reduction in the problem dimensionality. This enables us to establish the problem's unimodality for a wide class of topologies. We also establish a parallel with the product-line pricing problem, for which we generalize some of our results. In our second article, we address the problem from a numerical point of view for the case where multiple origin-destination pairs are present. We work out algorithms that exploit both local information and the pricing problem specific combinatorial features. We provide theoretical results which put in perspective the deterministic and probabilistic models, as well as numerical evidence according to which a very simple combinatorial approximation can lead to the best solutions. Also, our experiments clearly indicate that under any reasonable setting, the logit pricing problem is much smoother, and admits less optima then its deterministic counterpart. The third article is concerned with an extension to an heterogeneous demand resulting from a mixed-logit discrete choice model. Commuter price sensitivity is assumed random and the corresponding revenue expression admits no closed form expression. We devise nonlinear and combinatorial approximation schemes for its evaluation and optimization, which allow us to obtain quasi-optimal solutions. Numerical experiments here indicate that the most realistic model yields the best solution, independently of how well the model can actually be solved. We finally illustrate how the output of the model can be used for economic purposes by evaluating the contributions to the revenue of various commuter groups.

Le problème de tournées de véhicules (VRP) implique de planifier les itinéraires d'une flotte de véhicules afin de desservir un ensemble de clients à moindre coût. Ce problème d'optimisation combinatoire NP-difficile apparait dans de nombreux domaines d'application, notamment en logistique, télécommunications, robotique ou gestion de crise dans des contextes militaires et humanitaires. Ces applications amènent différents contraintes, objectifs et décisions supplémentaires ; des "attributs" qui viennent compléter les formulations classiques du problème. Les nombreux VRP Multi-Attributs (MAVRP) qui s'ensuivent sont le support d'une littérature considérable, mais qui manque de méthodes généralistes capables de traiter efficacement un éventail significatif de variantes. Par ailleurs, la résolution de problèmes "riches", combinant de nombreux attributs, pose d'importantes difficultés méthodologiques. Cette thèse contribue à relever ces défis par le biais d'analyses structurelles des problèmes, de développements de stratégies métaheuristiques, et de méthodes unifiées. Nous présentons tout d'abord une étude transversale des concepts à succès de 64 méta-heuristiques pour 15 MAVRP afin d'en cerner les "stratégies gagnantes". Puis, nous analysons les problèmes et algorithmes d'ajustement d'horaires en présence d'une séquence de tâches fixée, appelés problèmes de "timing". Ces méthodes, développées indépendamment dans différents domaines de recherche liés au transport, ordonnancement, allocation de ressource et même régression isotonique, sont unifiés dans une revue multidisciplinaire. Un algorithme génétique hybride efficace est ensuite proposé, combinant l'exploration large des méthodes évolutionnaires, les capacités d'amélioration agressive des métaheuristiques à voisinage, et une évaluation bi-critère des solutions considérant coût et contribution à la diversité de la population. Les meilleures solutions connues de la littérature sont retrouvées ou améliorées pour le VRP classique ainsi que des variantes avec multiples dépôts et périodes. La méthode est étendue aux VRP avec contraintes de fenêtres de temps, durée de route, et horaires de conducteurs. Ces applications mettent en jeu de nouvelles méthodes d'évaluation efficaces de contraintes temporelles relaxées, des phases de décomposition, et des recherches arborescentes pour l'insertion des pauses des conducteurs. Un algorithme de gestion implicite du placement des dépôts au cours de recherches locales, par programmation dynamique, est aussi proposé. Des études expérimentales approfondies démontrent la contribution notable des nouvelles stratégies au sein de plusieurs cadres méta-heuristiques. Afin de traiter la variété des attributs, un cadre de résolution heuristique modulaire est présenté ainsi qu'un algorithme génétique hybride unifié (UHGS). Les attributs sont gérés par des composants élémentaires adaptatifs. Des expérimentations sur 26 variantes du VRP et 39 groupes d'instances démontrent la performance remarquable de UHGS qui, avec une unique implémentation et paramétrage, égalise ou surpasse les nombreux algorithmes dédiés, issus de plus de 180 articles, révélant ainsi que la généralité ne s'obtient pas forcément aux dépends de l'efficacité pour cette classe de problèmes. Enfin, pour traiter les problèmes riches, UHGS est étendu au sein d'un cadre de résolution parallèle coopératif à base de décomposition, d'intégration de solutions partielles, et de recherche guidée. L'ensemble de ces travaux permet de jeter un nouveau regard sur les MAVRP et les problèmes de timing, leur résolution par des méthodes méta-heuristiques, ainsi que les méthodes généralistes pour l'optimisation combinatoire. / The Vehicle Routing Problem (VRP) involves designing least cost delivery routes to service a geographically-dispersed set of customers while taking into account vehicle-capacity constraints. This NP-hard combinatorial optimization problem is linked with multiple applications in logistics, telecommunications, robotics, crisis management in military and humanitarian frameworks, among others. Practical routing applications are usually quite distinct from the academic cases, encompassing additional sets of specific constraints, objectives and decisions which breed further new problem variants. The resulting "Multi-Attribute" Vehicle Routing Problems (MAVRP) are the support of a vast literature which, however, lacks unified methods capable of addressing multiple MAVRP. In addition, some "rich" VRPs, i.e. those that involve several attributes, may be difficult to address because of the wide array of combined and possibly antagonistic decisions they require. This thesis contributes to address these challenges by means of problem structure analysis, new metaheuristics and unified method developments. The "winning strategies" of 64 state-of-the-art algorithms for 15 different MAVRP are scrutinized in a unifying review. Another analysis is targeted on "timing" problems and algorithms for adjusting the execution dates of a given sequence of tasks. Such methods, independently studied in different research domains related to routing, scheduling, resource allocation, and even isotonic regression are here surveyed in a multidisciplinary review. A Hybrid Genetic Search with Advanced Diversity Control (HGSADC) is then introduced, which combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and a bi-criteria evaluation of solutions based on cost and diversity measures. Results of remarkable quality are achieved on classic benchmark instances of the capacitated VRP, the multi-depot VRP, and the periodic VRP. Further extensions of the method to VRP variants with constraints on time windows, limited route duration, and truck drivers' statutory pauses are also proposed. New route and neighborhood evaluation procedures are introduced to manage penalized infeasible solutions w.r.t. to time-window and duration constraints. Tree-search procedures are used for drivers' rest scheduling, as well as advanced search limitation strategies, memories and decomposition phases. A dynamic programming-based neighborhood search is introduced to optimally select the depot, vehicle type, and first customer visited in the route during local searches. The notable contribution of these new methodological elements is assessed within two different metaheuristic frameworks. To further advance general-purpose MAVRP methods, we introduce a new component-based heuristic resolution framework and a Unified Hybrid Genetic Search (UHGS), which relies on modular self-adaptive components for addressing problem specifics. Computational experiments demonstrate the groundbreaking performance of UHGS. With a single implementation, unique parameter setting and termination criterion, this algorithm matches or outperforms all current problem-tailored methods from more than 180 articles, on 26 vehicle routing variants and 39 benchmark sets. To address rich problems, UHGS was included in a new parallel cooperative solution framework called "Integrative Cooperative Search (ICS)", based on problem decompositions, partial solutions integration, and global search guidance. This compendium of results provides a novel view on a wide range of MAVRP and timing problems, on efficient heuristic searches, and on general-purpose solution methods for combinatorial optimization problems. / Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes