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.

Afin d’améliorer la qualité de prédiction des techniques de classification automatique et de fouilles de données, plusieurs modèles ont été proposés dans la littérature en vue d’extraire des connaissances à partir des données. Toutefois, avec l’expansion des systèmes d’information et des technologies associées, ces techniques d’apprentissage s’avèrent de moins en moins adaptées aux nouvelles tailles et dimensions des données. On s’intéresse dans cette étude aux problèmes de grande dimensionnalité et à l’amélioration du processus d’apprentissage des méthodes de classification à travers les techniques de filtrage et de sélection d’attributs. Le problème « d’identification d’attributs pertinents » (Feature Selection Problem), tel qu’il est défini dans la littérature, relève d’une nature combinatoire. Dans le cadre de cette thèse, on s’est intéressé au développement de nouvelles techniques d’optimisation approchées et spécifiques au problème traité ainsi qu’à l’amélioration d’algorithmes existants. La conception, l’implémentation et l’étude empirique ont montré l’efficacité et la pertinence des métaheuristiques proposées. / Although the expansion of storage technologies, networking systems, and information system methodologies, the capabilities of conventional data processing techniques remain limited. The need to knowledge extraction, compact representation and data analysis are highly motivated by data expansion. Nevertheless, learning from data might be a complex task, particularly when it includes noisy, redundant and information-less attributes. Feature Selection (FS) tries to select the most relevant attributes from raw data, and hence guides the construction of final classification models or decision support systems. Selected features should be representative of the underlying data and provide effective usefulness to the targeted learning paradigm (i.e. classification). In this thesis, we investigate different optimization paradigms as well as its adaptation to the requirements of the feature selection challenges, namely the problem combinatorial nature. Both theoritical and empirical aspects were studied, and confirm the effectiveness of the adopted methodology as well as the proposed metaheuristic based approaches.

Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou verticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas. / A rectangular representation of a plane graph G is a representation of G, where each vertex is drawn as a rectangle, such as two rectangles have to share some boundary if and only if exist an edge in G between the corresponding vertices. Also, the representation of G must form a rectangle and does not contain any holes, in other words, every point inside the formed rectangle must correspond to some vertex of G. A rectangular drawing of a plane graph H is a drawing of H, where all edges are drawn either in vertical or in horizontal. Also, every internal face is a rectangle and the edges which are incident in the external face define a rectangle. In this dissertation, we present the main studies in the literature for problems associated with the rectangular representation. We also present results for problems associated with rectangular drawing. Finally, we present the algorithm we developed to determine the coordinates of the vertices of a rectangular drawing when the orientation of the edges have been determined.

Étant donné un graphe G = (V U T, E), tel que V U T représente l'ensemble des sommets où T est un ensemble de terminaux, et une fonction poids w associée aux sommets non terminaux, le problème du séparateur de poids minimum consiste à partitionner V U T en k + 1 sous-ensembles {S, V1,..., Vk} tel qu'il n'y a aucune arête entre deux sous-ensembles différents Vi et Vj, chaque Vi contient exactement un terminal et le poids de S est minimum. Dans cette thèse, nous étudions le problème d'un point de vue polyèdral. Nous donnons deux formulations en nombres entiers pour le problème, et pour une de ces formulations, nous étudions le polyèdre associé. Nous présentons plusieurs inégalités valides, et décrivons des conditions de facette. En utilisant ces résultats, nous développons un algorithme de coupes et branchement pour le problème. Nous étudions également le polytope des séparateurs dans les graphes décomposables par sommets d'articulation. Si G est un graphe qui se décompose en G1 et G2, alors nous montrons que le polytope des séparateurs dans G peut être décrit à partir de deux systèmes linéaires liés à G1 et G2. Ceci donne lieu à une technique permettant de caractériser le polytope des séparateurs dans les graphes qui sont récursivement décomposables. Ensuite, nous étudions des formulations étendues pour le problème et proposons des algorithmes de génération de colonnes et branchement ainsi que des algorithmes de génération de colonnes, de coupes et branchement. Pour chaque formulation, nous présentons un algorithme de génération de colonnes, une procedure pour le calcul de la borne duale ainsi qu'une règle de branchement. De plus, nous présentons quatre variantes du problème du séparateur. Nous montrons que celles-ci sont NP-difficiles, et pour chacune d'elles nous donnons une formulation en nombres entiers et présentons certaines classes d'inégalités valides. / Given a graph G = (V U T, E) with V U T the set of vertices, where T is a set of terminals, and a weight function w, associated with the nonterminal nodes, the multi-terminal vertex separator problem consists in partitioning V U T into k + 1 subsets {S, V1,..., Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one terminal and the weight of S is minimum. In this thesis, we consider the problem from a polyhedral point of view. We give two integer programming formulations for the problem, for one of them, we investigate the related polyhedron. We describe some valid inequalities and characterize when these inequalities define facets. Using these results, we develop a Branch-and-Cut algorithm for the problem. We also study the multi-terminal vertex separator polytope in the graphs decomposable by one node cutsets. If G is a graph that decomposes into G1 and G2, we show that the multi-terminal vertex separator polytope in G can be described from two linear systems related to G1 and G2. This gives rise to a technique for characterizing the multi-terminal vertex separator polytope in the graphs that are recursively decomposable. Moreover, we propose three extended formulations for the problem and derive Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present a column generation scheme, the way to compute the dual bound, and the branching scheme. Finally, we discuss four variants of the multi-terminal vertex separator problem. We show that all these variants are NP-hard and for each one we give an integer programming formulation and present some class of valid inequalities.

Les problèmes d’optimisation multi-objectifs mènent souvent à considérer des ensembles de points non-dominés très grands à mesure que la taille et le nombre d’objectifs du problème augmentent. Générer l’ensemble de ces points demande des temps de calculs prohibitifs. De plus, la plupart des solutions correspondantes ne sont pas pertinentes pour un décideur. Une autre approche consiste à utiliser des informations de préférence, ce qui produit un nombre très limité de solutions avec des temps de calcul réduits. Cela nécessite la plupart du temps une élicitation précise de paramètres. Cette étape est souvent difficile pour un décideur et peut amener à délaisser certaines solutions intéressantes. Une approche intermédiaire consiste à raisonner avec des relations de préférences construites à partir d’informations partielles. Nous présentons dans cette thèse plusieurs modèles de relations partielles de préférences. En particulier, nous nous sommes intéressés à la génération de l’ensemble des points non-dominés selon ces relations. Les expérimentations démontrent la pertinence de notre approche en termes de temps de calcul et qualité des points générés. / Multi-objective optimization problems often lead to large nondominated sets, as the size of the problem or the number of objectives increases. Generating the whole nondominated set requires significant computation time, while most of the corresponding solutions are irrelevant to the decision maker. Another approach consists in obtaining preference information, which reduces the computation time and produces one or a very limited number of solutions. This requires the elicitation of precise preference parameters most of the time, which is often difficult and partly arbitrary, and might discard solutions of interest. An intermediate approach consists in using partial preference models.In this thesis, we present several partial preference models. We especially focused on the generation of the nondominated set according to these preference relations. This approach shows competitive performances both on computation time and quality of the generated preferred sets.

The aim of the work is analysis and implementation of a tool, which will support a job scheduling for workers on the annual voluntary service which lasts for a week. The scheduling is done semiautomatically based on various criteria. Users of the tool are able to track a current state of the algorithm execution and influence it. The analysis of the chosen scheduling algorithms and their comparison on real data is also a part of the work. The tool can also be used as a register of worker, job, area and car properties. The emphasis is on the simplicity and intuitivity of the tool controlling and the data input.

The rapid developments in the field of DNA computing reflects two substantial questions: 1. Which models for DNA based computation are really universal? 2. Which model fulfills the requirements to a universal lab-practicable programmable DNA computer that is based on one of these models? This paper introduces the functional model DNA-HASKELL focussing its lab-practicability. This aim could be reached by specifying the DNA based operations in accordiance to an analysis of molecular biological processes. The specification is determined by an abstraction level that includes nucleotides and strand end labels like 5'-phosphate. Our model is able to describe DNA algorithms for any NP-complete problem - here exemplified by the knapsacik problem - as well as it is able to simulate some established mathematical models for computation. We point out the splicing operation as an example. The computational completeness of DNA-HASKELL can be supposed. This paper is based on discussions about the potenzial and limits of DNA computing, in particular the practicability of a universal DNA computer.

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. / The tomographic imaging problem deals with reconstructing an objectfrom a data called a projections and collected by illuminating the objectfrom many different directions. A projection means the information derivedfrom the transmitted energies, when an object is illuminated from a particularangle. The solution to the problem of how to reconstruct an object fromits projections dates to 1917 by Radon. The tomographic reconstructingis applicable in many interesting contexts such as nondestructive testing,image processing, electron microscopy, data security, industrial tomographyand material sciences.Discete tomography (DT) deals with the reconstruction of discret objectfrom limited number of projections. The projections are the sums along fewangles of the object to be reconstruct. One of the main problems in DTis the reconstruction of binary matrices from two projections. In general,the reconstruction of binary matrices from a small number of projections isundetermined and the number of solutions can be very large. Moreover, theprojections data and the prior knowledge about the object to reconstructare not sufficient to determine a unique solution. So DT is usually reducedto an optimization problem to select the best solution in a certain sense.In this thesis, we deal with the tomographic reconstruction of binaryand colored images. In particular, research objectives are to derive thecombinatorial optimization techniques in discrete tomography problems.

La SNCF utilise plusieurs engins spécialisés pour ausculter les fissures internes du rail. La fréquence d’auscultation de chaque rail est fonction du tonnage cumulé qui passe dessus. La programmation des engins d’auscultations ultrasonores est aujourd’hui décentralisée. Dans le cadre d’une étude de réorganisation, la SNCF souhaite étudier la faisabilité de l’optimisation de certaines tournées d’inspection. Dans le cadre de cette thèse de doctorat, l’optimisation de la programmation des engins d’auscultation à ultrasons est étudiée.Une modélisation mathématique sous forme de problème de tournées sur arcs généralisant plusieurs problèmes académiques est proposées. Une méthode de résolution exacte, appliquant la décomposition de Benders, est détaillée. À partir de cette approche, une heuristique de génération de colonnes et de contraintes est présentée et analysée numériquement sur des données réelles de 2009. Enfin, un logiciel industriel développé autour de cette approche est présenté / SNCF is using specialised rolling stock units to inspect internal defects in rails. Rail’s inspection frequency is defined by the cumulative weight of the trains which are going through. In2009, the scheduling of these train units is decentralised. SNCF is studying the centralisation of this process. In this Ph.D. thesis, a new problem, the Railroad Track Inspection SchedulingProblem is studied.A mathematical formulation, based on the generalization of classical arc routing models,is proposed. An exact solving approach, based on Benders’ decomposition scheme, is detailed.From this approach, a column and cut generation heuristic is developed, implemented, andtested on real datasets for 2009. The industrial software developed around this heuristic is presented.

Cette thèse considère le problème de sélection et d’ordonnancement des prises de vue d’un satellite agile d’observation de la Terre. La mission d’un satellite d’observation est d’obtenir des photographies de la surface de la Terre afin de satisfaire des requêtes d’utilisateurs. Les demandes, émanant de différents utilisateurs, doivent faire l’objet d’un traitement avant transmission d’un ordre vers le satellite, correspondant à une séquence d’acquisitions sélectionnées. Cette séquence doit optimiser deux objectifs sous contraintes d’exploitation. Le premier objectif est de maximiser le profit global des acquisitions sélectionnées. Le second est d’assurer l’équité du partage des ressources en minimisant la différence maximale de profit entre les utilisateurs. Deux métaheuristiques, composées d’un algorithme génétique à clé aléatoire biaisées (biased random key genetic algorithm - BRKGA) et d’une recherche locale multi-objectif basée sur des indicateurs (indicator based multi-objective local search - IBMOLS), sont proposées pour résoudre le problème. Pour BRKGA, trois méthodes de sélection, empruntées à NSGA-II, SMS-EMOA, et IBEA, sont proposées pour choisir un ensemble de chromosomes préférés comme ensemble élite. Trois stratégies de décodage, parmi lesquelles deux sont des décodages uniques et la dernière un décodage hybride, sont appliquées pour décoder les chromosomes afin d’obtenir des solutions. Pour IBMOLS, plusieurs méthodes pour générer la population initiale sont testées et une structure de voisinage est également proposée. Des expériences sont menées sur des cas réalistes, issus d’instances modifiées du challenge ROADEF 2003. On obtient ainsi les fronts de Pareto approximés de BRKGA et IBMOLS dont on calcule les hypervolumes. Les résultats de ces deux algorithmes sont comparés / This thesis considers the selection and scheduling problem of observations for agile Earth observing satellites. The mission of Earth observing satellites is to obtain photographs of the Earth surface to satisfy user requirements. Requests from several users have to be managed before transmitting an order, which is a sequence of selected acquisitions, to the satellite. The obtained sequence must optimize two objectives under operation constraints. The first objective is to maximize the total profit of the selected acquisitions. The second one is to ensure the fairness of resource sharing by minimizing the maximum profit difference between users. Two metaheuristic algorithms, consisting of a biased random key genetic algorithm (BRKGA) and an indicator-based multi-objective local search (IBMOLS), are proposed to solve the problem. For BRKGA, three selection methods, borrowed from NSGA-II, SMS-EMOA, and IBEA, are proposed to select a set of preferred chromosomes to be the elite set. Three decoding strategies, which are two single decoding and a hybrid decoding, are applied to decode chromosomes to become solutions. For IBMOLS, several methods for generating the initial population are tested and the neighborhood structure according to the problem is also proposed. Experiments are conducted on realistic instances based on ROADEF 2003 challenge instances. Hypervolumes of the approximate Pareto fronts are computed and the results from the two algorithms are compared