- / -

The classical Hospitals / Residents problem (HR) is a many-to-one bipartite matching problem involving preferences, motivated by centralised matching schemes arising in entry level labour markets, the assignment of pupils to schools and higher education admissions schemes, among its many applications. The particular requirements of these matching schemes may lead to generalisations of HR that involve additional inputs or constraints on an acceptable solution. In this thesis we study such variants of HR from an algorithmic and integer programming viewpoint. The Hospitals / Residents problem with Couples (HRC) is a variant of HR that is important in practical applications because it models the case where couples submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that an instance of HRC need not admit a stable matching. We show that deciding whether an instance of HRC admits a stable matching is NP-complete even under some very severe restrictions on the lengths and the structure of the participants’ preference lists. However, we show that under certain restrictions on the lengths of the agents’ preference lists, it is possible to find a maximum cardinality stable matching or report that none exists in polynomial time. Since an instance of HRC need not admit a stable matching, it is natural to seek the ‘most stable’ matching possible, i.e., a matching that admits the minimum number of blocking pairs. We use a gap-introducing reduction to establish an inapproximability bound for the problem of finding a matching in an instance of HRC that admits the minimum number of blocking pairs. Further, we show how this result might be generalised to prove that a number of minimisation problems based on matchings having NP-complete decision versions have the same inapproximability bound. We also show that this result holds for more general minimisation problems having NP-complete decisions versions that are not based on matching problems. Further, we present a full description of the first Integer Programming (IP) model for finding a maximum cardinality stable matching or reporting that none exists in an arbitrary instance of HRC. We present empirical results showing the average size of a maximum cardinality stable matching and the percentage of instances admitting stable matching taken over a number of randomly generated instances of HRC with varying properties. We also show how this model might be generalised to the variant of HRC in which ties are allowed in either the hospitals’ or the residents’ preference lists, the Hospitals / Residents problem with Couples and Ties (HRCT). We also describe and prove the correctness of the first IP model for finding a maximum cardinality ‘most stable’ matching in an arbitrary instance of HRC. We describe empirical results showing the average number of blocking pairs admitted by a most-stable matching as well as the average size of a maximum cardinality ‘most stable’ matching taken over a number of randomly generated instances of HRC with varying properties. Further, we examine the output when the IP model for HRCT is applied to real world instances arising from the process used to assign medical graduates to Foundation Programme places in Scotland in the years 2010-2012. The Hungarian Higher Education Allocation Scheme places a number of additional constraints on the feasibility of an allocation and this gives rise to various generalisations of HR. We show how a number of these additional requirements may be modelled using IP techniques by use of an appropriate combination of IP constraints. We present IP models for HR with Stable Score Limits and Ties, HR with Paired Applications, Ties and Stable Score limits, HR with Common Quotas, Ties and Stable Score Limits and also HR with Lower Quotas, Ties and Stable Score limits that model these generalisations of HR. The Teachers’ Allocation Problem (TAP) is a variant of HR that models the allocation of trainee teachers to supervised teaching positions in Slovakia. In TAP teachers express preference lists over pairs of subjects at individual schools. It is known that deciding whether an optimal matching exists that assigns all of the trainee teachers is NP-complete for a number of restricted cases. We describe IP models for finding a maximum cardinality matching in an arbitrary TAP instance and for finding a maximum cardinality stable matching, or reporting that none exists, in a TAP instance where schools also have preferences. We show the results when applying the first model to the real data arising from the allocation of trainee teachers to schools carried out at P.J. Safarik University in Kosice in 2013.

Many concrete problems, ranging from Portfolio selection to Water resource management, may be cast into a multiobjective programming framework. The simplistic way of superseding blindly conflictual goals by one objective function let no chance to the model but to churn out meaningless outcomes. Hence interest of discussing ways for tackling Multiobjective Programming Problems. More than this, in many real-life situations, uncertainty and imprecision are in the state of affairs. In this dissertation we discuss ways for solving Multiobjective Programming Problems with fixed and fuzzy coefficients. No preference, a priori, a posteriori, interactive and metaheuristic methods are discussed for the deterministic case. As far as the fuzzy case is concerned, two approaches based respectively on possibility measures and on Embedding Theorem for fuzzy numbers are described. A case study is also carried out for the sake of illustration. We end up with some concluding remarks along with lines for further development, in this field. / Operations Research / M. Sc. (Operations Research)

Dans cette thèse, nous étudions des approches basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithm) pour la programmation mathématique avec des contraintes d'équilibre, notée MPEC (Mathematical Programming with Equilibrum Constraints en anglais). Etant un sujet classique et difficile de la programmation mathématique et de la recherche opérationnelle, et de par ses diverses applications importantes, MPEC a attiré l'attention de nombreux chercheurs depuis plusieurs années. La thèse se compose de quatre chapitres principaux. Le chapitre 2 étudie une classe de programmes mathématiques avec des contraintes de complémentarité linéaire. En utilisant quatre fonctions de pénalité, nous reformulons le problème considéré comme des problèmes DC standard, i.e minimisation d'une fonction DC sous les contraintes convexes. Nous développons ensuite des algorithmes appropriés basés sur DCA pour résoudre les problèmes DC résultants. Deux d'entre eux sont reformulés encore sous la forme des problèmes DC généraux (i.e. minimisation d'une fonction DC sous des contraintes DC) pour que les sous-problèmes convexes dans DCA soient plus faciles à résoudre. Après la conception de DCA pour le problème considéré, nous développons ces schémas DCA pour deux cas particuliers: la programmation quadratique avec des contraintes de complémentarité linéaire, et le problème de complémentarité aux valeurs propres. Le chapitre 3 aborde une classe de programmes mathématiques avec des contraintes d'inégalité variationnelle. Nous utilisons une technique de pénalisation pour reformuler le problème considéré comme un programme DC. Une variante de DCA et sa version accélérée sont proposées pour résoudre ce programme DC. Comme application, nous résolvons le problème de détermination du prix de péages dans un réseau de transport avec des demandes fixes (" the second-best toll pricing problem with fixed demands" en anglais). Le chapitre 4 se concentre sur une classe de problèmes d'optimisation à deux niveaux avec des variables binaires dans le niveau supérieur. En utilisant une fonction de pénalité exacte, nous reformulons le problème considéré comme un programme DC standard pour lequel nous développons un algorithme efficace basé sur DCA. Nous appliquons l'algorithme proposé pour résoudre le problème d'interdiction de flot maximum dans un réseau ("maximum flow network interdiction problem" en anglais). Dans le chapitre 5, nous nous intéressons au problème de conception de réseau d'équilibre continu ("continuous equilibrium network design problem" en anglais). Il est modélisé sous forme d'un programme mathématique avec des contraintes de complémentarité, brièvement nommé MPCC (Mathematical Program with Complementarity Constraints en anglais). Nous reformulons ce problème MPCC comme un programme DC général et proposons un schéma DCA approprié pour le problème résultant / In this dissertation, we investigate approaches based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) for mathematical programs with equilibrium constraints. Being a classical and challenging topic of nonconvex optimization, and because of its many important applications, mathematical programming with equilibrium constraints has attracted the attention of many researchers since many years. The dissertation consists of four main chapters. Chapter 2 studies a class of mathematical programs with linear complementarity constraints. By using four penalty functions, we reformulate the considered problem as standard DC programs, i.e. minimizing a DC function on a convex set. The appropriate DCA schemes are developed to solve these four DC programs. Two among them are reformulated again as general DC programs (i.e. minimizing a DC function under DC constraints) in order that the convex subproblems in DCA are easier to solve. After designing DCA for the considered problem, we show how to develop these DCA schemes for solving the quadratic problem with linear complementarity constraints and the asymmetric eigenvalue complementarity problem. Chapter 3 addresses a class of mathematical programs with variational inequality constraints. We use a penalty technique to recast the considered problem as a DC program. A variant of DCA and its accelerated version are proposed to solve this DC program. As an application, we tackle the second-best toll pricing problem with fixed demands. Chapter 4 focuses on a class of bilevel optimization problems with binary upper level variables. By using an exact penalty function, we express the bilevel problem as a standard DC program for which an efficient DCA scheme is developed. We apply the proposed algorithm to solve a maximum flow network interdiction problem. In chapter 5, we are interested in the continuous equilibrium network design problem. It was formulated as a Mathematical Program with Complementarity Constraints (MPCC). We reformulate this MPCC problem as a general DC program and then propose a suitable DCA scheme for the resulting problem

Η αυτοματοποιημένη μεθοδολογία εύρεσης προγραμμάτων υπολογιστών (κώδικα) που βασίζεται στις αρχές της βιολογικής εξέλιξης, ονομάζεται Γενετικός Προγραμματισμός (ΓΠ). Με άλλα λόγια, πρόκειται για μια τεχνική Μηχανικής Μάθησης, η οποία χρησιμοποιεί ένα Εξελικτικό Αλγόριθμο για να βελτιστοποιήσει ένα πληθυσμό από προγράμματα υπολογιστή σύμφωνα με μια συνάρτηση καταλληλότητας που καθορίζεται από την ικανότητα του προγράμματος να εκτελέσει ένα δοσμένο υπολογιστικό έργο. Στην εργασία αυτή θα χρησιμοποιηθούν διάφορες τεχνικές Γενετικού Προγραμματισμού στην μοντελοποίηση Χρονοσειρών. Τα συστήματα που θα αναπτυχθούν, θα χρησιμοποιηθούν για τους παρακάτω σκοπούς: • Μοντελοποίηση του συστήματος που «παράγει» τη χρονοσειρά, • Εξαγωγή χαρακτηριστικών και κανόνων που μπορούν να οδηγήσουν στην ικανότητα πρόβλεψης χρονοσειρών. Οι χρονοσειρές που θα χρησιμοποιηθούν για να δοκιμάσουμε την λειτουργία των συστημάτων που θα υλοποιηθούν είναι οι εξής: • Χρονοσειρά δεικτών ελληνικού χρηματιστηρίου, • Χρονοσειρές ιατρικών δεδομένων όπως για παράδειγμα χρονοσειρά σήματος μαγνητοεγκεφαλογραφήματος. Οι κλασσικές τεχνικές Γενετικού Προγραμματισμού χρησιμοποιούν δενδρικές δομές για την αναπαράσταση των προγραμμάτων-ατόμων των πληθυσμών. Στο παρελθόν έχουν εκπονηθεί και υλοποιηθεί πολλές εργασίες που χρησιμοποιούν γενετικό προγραμματισμό για την μοντελοποίηση χρονοσειρών. Τα αποτελέσματα ήταν ικανοποιητικά. Το βασικό πρόβλημα που αντιμετωπίστηκε ήταν ο μεγάλος χρόνος εκτέλεσης που απαιτούν οι κλασσικές τεχνικές Γενετικού προγραμματισμού. Το θέμα λοιπόν είναι ανοιχτό σε μελέτη και υπάρχει η ανάγκη να χρησιμοποιηθούν νέες τεχνικές γενετικού προγραμματισμού για να πάρουμε και καλύτερα και πιο γρήγορα αποτελέσματα. Στην εργασία αυτή, θα χρησιμοποιηθεί η τεχνική του Γραμμικού Γενετικού Προγραμματισμού. Σε αυτήν την τεχνική, τα προγράμματα-άτομα του πληθυσμού αναπαρίστανται σαν μια ακολουθία από εντολές οι οποίες αναπαρίστανται σε δυαδική μορφή. Οι δύο αυτές τεχνικές θα συγκριθούν και θα βγουν συμπεράσματα για το ποια είναι η πιο χρήσιμη στον τομέα της μοντελοποίησης χρονοσειρών. Ακόμη, θα υλοποιηθούν αλγόριθμοι οι οποίοι εντοπίζουν και αφαιρούν τον κώδικα που δεν συμμετέχει στην παραγωγή της εξόδου των προγραμμάτων-ατόμων του πληθυσμού. Οι αλγόριθμοι αυτοί, περιμένουμε να επιταχύνουν κατά πολύ την διαδικασία της εξέλιξης του πληθυσμού, αφού στον γενετικό προγραμματισμό σχηματίζονται συχνά τέτοια μπλοκ κώδικα που δεν επηρεάζουν την έξοδο των προγραμμάτων. / -

Many concrete problems, ranging from Portfolio selection to Water resource management, may be cast into a multiobjective programming framework. The simplistic way of superseding blindly conflictual goals by one objective function let no chance to the model but to churn out meaningless outcomes. Hence interest of discussing ways for tackling Multiobjective Programming Problems. More than this, in many real-life situations, uncertainty and imprecision are in the state of affairs. In this dissertation we discuss ways for solving Multiobjective Programming Problems with fixed and fuzzy coefficients. No preference, a priori, a posteriori, interactive and metaheuristic methods are discussed for the deterministic case. As far as the fuzzy case is concerned, two approaches based respectively on possibility measures and on Embedding Theorem for fuzzy numbers are described. A case study is also carried out for the sake of illustration. We end up with some concluding remarks along with lines for further development, in this field. / Operations Research / M. Sc. (Operations Research)

MOR (Model Order Reduction) est devenu un domaine très répondu dans la recherche grâce à l'intérêt qu'il peut apporter dans la réduction des systèmes, ce qui permet d'économiser du temps, de la mémoire et le coût de CPU pour les outils de CAO. Ce domaine contient principalement deux branches: linéaires et non linéaires. MOR linéaire est un domaine mature avec des techniques numériques bien établie et bien connus dans la domaine de la recherche, par contre le domaine non linéaire reste vague, et jusqu'à présent il n'a pas montré des bons résultats dans la simulation des circuits électriques. La recherche est toujours en cours dans ce domaine, en raison de l’intérêt qu'il peut fournir aux simulateurs contemporains, surtout avec la croissance des puces électroniques en termes de taille et de complexité, et les exigences industrielles vers l'intégration des systèmes sur la même puce.Une contribution significative, pour résoudre le problème de Harmonic Balance (Equilibrage Harmonique) en utilisant la technique MOR, a été proposé en 2002 par E. Gad et M. Nakhla. La technique a montré une réduction substantielle de la dimension du système, tout en préservant, en sortie, la précision de l'analyse en régime permanent. Cette méthode de MOR utilise la technique de projection par l'intermédiaire de Krylov, et il préserve la passivité du système. Cependant, il souffre de quelques limitations importantes dans la construction de la matrice “pre-conditioner“ qui permettrait de réduire le système. La limitation principale est la nécessité d'une factorisation explicite comme une suite numérique de l'équation des dispositifs non linéaires . cette limitation rend la technique difficile à appliquer dans les conditions générales d'un simulateur. Cette thèse examinera les aspects non linéaires du modèle de réduction pour les équations de bilan harmoniques, et il étudiera les solutions pour surmonter les limitations mentionnées ci-dessus, en particulier en utilisant des approches de dérivateur numériques. / MOR recently became a well-known research field, due to the interest that it shows in reducing the system, which saves time, memory, and CPU cost for CAD tools. This field contains two branches, linear and nonlinear MOR, the linear MOR is a mature domain with well-established theory and numerical techniques. Meanwhile, nonlinear MOR domain is still stammering, and so far it didn’t show good and successful results in electrical circuit simulation. Some improvements however started to pop-up recently, and research is still going on this field because of the help that it can give to the contemporary simulators, especially with the growth of the electronic chips in terms of size and complexity due to industrial demands towards integrating systems on the same chip. A significant contribution in the MOR technique of HB solution has been proposed a decade ago by E. Gad and M. Nakhla. The technique has shown to provide a substantial system dimension reduction while preserving the precision of the output in steady state analysis. This MOR method uses the technique of projection via Krylov, and it preserves the passivity of the system. However, it suffers a number of important limitations in the construction of the pre-conditioner matrix which is ought to reduce the system. The main limitation is the necessity for explicit factorization as a power series of the equation of the nonlinear devices. This makes the technique difficult to apply in general purpose simulator conditions. This thesis will review the aspects of the nonlinear model order reduction technique for harmonic balance equations, and it will study solutions to overcome the above mentioned limitations, in particular using numerical differentiation approaches.

Cette thèse traite de l'estimation du mouvement à partir d'une séquence d'images par des méthodes d'assimilation de données. Les travaux ont porté sur la prise en compte des objets dans les processus d'estimation, afin de corréler en espace les résultats obtenus. Les deux composantes méthodologiques que sont approche variationnelle et approche séquentielle sont traitées. L'algorithme variationnel repose sur une équation d'évolution, une équation d'ébauche et une équation d'observation. L'estimation s'obtient comme le minimum d'une fonction de coût. Dans une première étape, l'objet est décrit par sa courbe frontière. Le modèle dynamique caractérise l'évolution des images et déplace les objets afin que leurs positions correspondent à celles observées dans les acquisitions image. Cette approche impacte fortement les temps de calculs, mais permet une amélioration de l'estimation du mouvement. Deuxièmement, les valeurs de la matrice de covariance des erreurs d'ébauche sont modifiées afin de corréler, à moindre coût, les pixels de l'image. L'algorithme séquentiel présenté repose sur la création d'un ensemble de vecteurs d'état ainsi que sur des approches de localisation. Pour modéliser les objets, un nouveau critère de localisation portant sur l'intensité de niveau de gris des pixels a été défini. Cependant, la localisation, si elle est appliquée directement sur la matrice de covariance d'erreur, rend la méthode inutilisable pour de grandes images. Une approche consistant à découper le domaine global en sous-domaines indépendants, avant d'estimer le mouvement, a été mise au point. La prise en compte des objets intervient lors du découpage du domaine d'analyse global. / This thesis describes approaches estimating motion from image sequences with data assimilation methods. A particular attention is given to include representations of the displayed objects in the estimation process. Variational and sequential implementations are discussed in the document.The variational methods rely on an evolution equation, a background equation and an observation equation, which characterize the studied system and the observations. The motion estimation is obtained as the minimum of a cost function. In a first approach, the structures are modeled by their boundaries. The image model describes both the evolution of the gray level function and the displacement of the structures. The resulting motion field should allow the position of the structures in the model to match their observed position. The use of structures betters the result. A second approach, less expensive regarding the computational costs, is designed, where the structures are modeled by the values of the background error covariance matrix.The sequential approach, described in the thesis, relies on the creation of an ensemble of state vectors and on the use of localization methods. In order to model the structures, a new localization criteria based on the gray level values is defined. However, the localization method, if directly applied on the background error covariance matrix, renders the approach inoperable on large images. Therefore, another localization method is designed, which consists to decompose the image domain into independent subdomains before the estimation. Here, the structures representation intervenes while decomposing the global domain.

Dans cette thèse nous développons une technique de déformation pour l'optimisation de formes. Les formes sont représentées par leur frontière, paramétrée par des courbes de Bézier par morceaux. En tant que courbes polynomiales, elles sont définies par leurs coefficients que l'on appelle plutôt points de contrôle. Bouger les points de contrôle revient à modifier la courbe et donc déplacer la frontière des formes. Dans un contexte d'optimisation de formes, ce sont alors les points de contrôle qui sont les variables du problème et l'on a transformé ce dernier en un problème d'optimisation paramétrique. Notre méthode de déformation consiste en un premier temps à paramétrer les frontières par des courbes de Bézier comme indiqué plus haut et dans un second temps à calculer une déformation des points de contrôle à partir d'une direction de descente de la fonction objectif. Notre méthode est de nature géométrique mais l'on propose un moyen de changer la topologie des formes en mesurant la distance entre les points de contrôle : on peut scinder une forme en deux ou inversement en réunir deux en une. Nous avons testé la méthode sur trois problèmes qui sont la conception d'un filtre micro-ondes, la détection d'inclusions et les trajectoires optimales. / We develop a deformation technique for shape optimization problems. The shapes are described only by their boundary, parameterized by piecewise Bézier curves. They are polynomial curves hence entirely defined by their coefficients which are called control points. By moving these control points the curves change and so is the boundary of the shape. Used in a shape optimization problem, the control points become the optimization variables meaning that the problem is a parametric optimization problem. Our method consists in first parameterizing the boundary of a shape by Bézier curves as stated above and then compute a deformation of the control points from a descent direction for the objective function. The method is almost purely geometric but we add a way to include topological changes by diving a shape into two or conversly merging two shapes into one. We tested our method on three particular shape optimization problems which are microwave filter design, inclusions detection and optimal trajectories.

Dans cette thèse, nous étudions trois catégories de problèmes : les d-extensibles, les d-bloqueurs et les d-transversaux.Les d-extensibles de stables optimaux sont des ensembles de sommets d'un graphe G tels que tout stable de cardinal d du sous-graphe induit par un d-extensible peut être étendu à un stable optimal de G à l'aide de sommets qui n'appartiennent pas au d-extensible. Nous étudions les d-extensibles de cardinal maximal de stables dans les graphes bipartis. Nous démontrons quelques propriétés structurelles puis nous déterminons une borne inférieure du cardinal maximal d'un d-extensible. Nous étudions quelques classes de graphes dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial. Nous nous intéressons ensuite aux d-extensibles de stables dans les arbres. Nous prouvons plusieurs propriétés structurelles, déterminons une autre borne inférieure du cardinal maximal d'un d-extensible et étudions quelques classes d'arbres dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial.Les d-bloqueurs de stables sont des ensembles de sommets d'un graphe G tels que, si on retire les sommets d'un d-bloqueur, le cardinal maximal d'un stable du graphe induit par les sommets restants est inférieur d'au moins d au cardinal maximal d'un stable du graphe initial. Nous nous intéressons ici aux d-bloqueurs de coût minimal de stables dans les arbres. Après avoir prouvé une caractérisation des d-bloqueurs de stables dans les arbres, nous démontrons que déterminer un d-bloqueur de coût minimal de stable est un problème polynomial dans une classe d'arbres particulière.Soit Pi un problème d'optimisation sur un ensemble d'éléments fini. Un d-transversal de Pi est un ensembles d'éléments tel que l'intersection entre le d-transversal et toute solution optimale au problème Pi est de cardinal supérieur égal à d. Nous proposons ici une approche de génération de contraintes pour déterminer des d-transversaux de cardinal maximal de problèmes modélisés par des programmes mathématiques en variables binaires. Nous étudions deux variantes de cette approche que nous testons sur des instances de graphes générés aléatoirement pour déterminer des d-transversaux de stables optimaux et des d-transversaux de couplages optimaux / In this thesis, we study three types of problems : the d-extensibles sets, the d-blockers and the d-transversals.In a graph G, a d-extensible set of maximum independent sets is a subset of vertices of G such that every stable set of cardinality d in the subgraph restricted to the d-extensible set can be extented to a maximum stable set of G using only vertices that do not belong to the d-extensible set. We study d-extensible sets of mxaimum cardinality of stable sets in bipartite graphs. We show some structural properties and we determine a lower bound of the maximum cardinality of a d-extensible set. We consider some classes of graph where finding an optimum d-extensible set can be done in polynomial time. Then, we study the d-extensibles sets of stable sets in trees. We prove some properties on the structures of the d-extensibles sets and we determine another lower bound of the maximum cardinality of a d-extensible set. Finaly, we study somme classes of tree where a d-extensible sets of maximum cardinality can be done in polynomial time.In a graph G, a d-blocker is a subset of vertices such that, if removed, a maximum stable set of the resulting subgraph is of cardinality at most the cardinality of a maximum stable set of G minus d. We study d-blocker of minimal cost of stable sets in tree.We prove a caracterisation of d-blockers in tree and we study a particular classe of trees where computing a d-blocker of minimal cost of stable sets can be done in polynomial time.Let Pi be an optimisation problem on a finite set of elements. A d-transversal of Pi is a subset of elements such that the intersection between the d-transversal and every optimal solution of Pi contains at lest d elements. We propose an approach to compute d-transversal of any optimisation problem modelised by mathematical program with binary variables. We use a contraints generation approach. We compare two variations of this approach on randomly generated graph by computing d-transversals of stables sets and d-transversals of matching