Dissertations / Theses on the topic 'Combinatorial optimisation problems'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Combinatorial optimisation problems.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Namazi, Majid. "Learning in Combinatorial Constraint Optimisation." Thesis, Griffith University, 2022. http://hdl.handle.net/10072/419082.
Full textThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Info & Comm Tech
Science, Environment, Engineering and Technology
Full Text
Zverovitch, Alexei E. "Construction heuristics for hard combinatorial optimisation problems." Thesis, Royal Holloway, University of London, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.405253.
Full textVoudouris, Christos. "Guided local search for combinatorial optimisation problems." Thesis, University of Essex, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.361019.
Full textLee, Lai Soon. "Multicrossover genetic algorithms for combinatorial optimisation problems." Thesis, University of Southampton, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.431202.
Full textDu, Plessis Andre. "On two combinatorial optimisation problems involving lotteries." Thesis, Stellenbosch : University of Stellenbosch, 2010. http://hdl.handle.net/10019.1/4137.
Full textENGLISH ABSTRACT: Suppose a lottery draw consists of forming a winning ticket by randomly choosing t m distinct numbers from a universal set Um = f1; : : : ;mg. Each lottery participant forms a set of tickets prior to the draw, each ticket consisting of n m distinct numbers from Um, and is awarded a prize if k minfn; tg or more numbers in at least one of his/her tickets matches those of the winning ticket. A lottery of this form is denoted by the quadruple hm; n; t; ki, and the prize is known as a k-prize. The participant's set of tickets is also known as a playing set. The participant may wish to form a playing set in such a way that the probability of winning a k-prize is at least 0 < 1. Naturally, the participant will want to minimise the cost of forming such a playing set, which means that the cardinality of the playing set should be as small as possible. This combinatorial minimisation problem is known as the incomplete lottery problem and was introduced by Gr undlingh [16], who also formulated a related problem called the resource utilisation problem. In this problem one attempts to select a playing set of pre-speci ed cardinality ` in such a way that the probability of winning a k-prize is maximised. Gr undlingh [16] studied the incomplete lottery problem and the resource utilisation problem in the special case where n = t. In this thesis both problems are considered in the general case where n 6= t. Exact and approximate solution methods are presented and compared to each other in terms of solution quality achieved, execution time and practical feasibility. The rst solution method involves a mathematical programming formulation of both problems. Using this solution method, both problems are solved for small lottery instances. An exhaustive enumeration solution method, which uses the concept of overlapping playing set structures [5, 16], is reviewed and used to solve both combinatorial optimisation problems for the same small lottery instances. The concept of an overlapping playing set structure is further explored and incorporated in an attempt to solve both combinatorial optimisation problems approximately by means of various metaheuristic solution approaches, including a simulated annealing algorithm, a tabu search and a genetic algorithm. The focus of the thesis nally shifts to a di erent problem involving lotteries. An investigation is conducted into the probability, P(N; ), of participants sharing a k-prize if a total of N tickets are purchased by participants of the lottery hm; n; t; ki. Special attention is a orded in this problem to the jackpot prize of the South African national lottery, Lotto, represented by the quadruple h49; 6; 6; 6i and how the value of P(N; ) is a ected by the way that participants select their playing sets.
AFRIKAANSE OPSOMMING: Gestel 'n lotery-trekking bestaan uit die ewekansige seleksie van 'n wenkaartjie bestaande uit t m verskillende getalle uit 'n universele versameling Um = f1; : : : ;mg. Elke lotery-deelnemer vorm 'n versameling kaartjies voor die trekking, wat elk uit n m verskillende getalle in Um bestaan, en wen 'n prys indien k minfn; tg of meer getalle in minstens een van sy/haar kaartjies ooreenstem met di e in die wenkaartjie. 'n Lotery van hierdie vorm word deur die viertal hm; n; t; ki aangedui, en die prys staan as 'n k-prys bekend. 'n Deelnemer se kaartjies staan ook as a spelversameling bekend. 'n Lotery-deelnemer mag poog om sy spelversameling s o te selekteer dat die waarskynlikheid om 'n k-prys te wen, minstens 0 < 1 is. Die deelnemer sal natuurlik die koste wat met so 'n spelversameling gepaard gaan, wil minimeer, wat beteken dat die kardinaliteit van sy spelversameling so klein as moontlik moet wees. Hierdie kombinatoriese minimeringsprobleem staan as die onvolledige lottery-probleem bekend en is vir die eerste keer deur Gr undlingh [16] bestudeer, wat ook die verwante hulpbronbenuttingsprobleem geformuleer het. In laasgenoemde probleem word daar gesoek na 'n spelversameling van vooraf-gespesi seerde kardinaliteit wat die waarskynlikheid om 'n k-prys te wen, maksimeer. Gr undlingh [16] het die onvolledige lottery-probleem en die hulpbronbenuttingsprobleem in die spesiale geval oorweeg waar n = t. In hierdie tesis word beide probleme in die algemeen oorweeg waar n 6= t. Eksakte en heuristiese oplossingstegnieke word vir beide probleme daargestel en met mekaar in terme van oplossingskwaliteit, oplossingstyd en praktiese haalbaarheid vergelyk. Die eerste oplossingstegniek behels 'n wiskundige programmeringsformulering van beide probleme. Die probleme word deur middel van hierdie benadering vir klein loterye opgelos. 'n Uitputtende enumerasietegniek, wat gebruik maak van die konsep van spelversameling oorvleuelingstrukture [5, 16], word daarna in o enskou geneem en beide kombinatoriese optimeringsprobleme word vir dieselfde klein loterye met behulp van hierdie tegniek opgelos. Die konsep van 'n spelversameling oorvleuelingstruktuur word verder ondersoek en in 'n benaderde oplossingstegniek vir beide kombinatoriese optimeringsprobleme ge nkorporeer deur gebruik te maak van verskeie metaheuristiese oplossingsbenaderings, insluitende 'n gesimuleerde afkoelingsalgoritme, 'n tabu-soektog en 'n genetiese algoritme. Die fokus in die tesis verskuif laastens na 'n ander probleem oor loterye. 'n Ondersoek word geloots na die waarskynlikheid, P(N; ), dat lottery-deelnemers 'n k-prys sal deel indien 'n totaal van N kaartjies in die lotery hm; n; t; ki gekoop word. Spesiale aandag word aan hierdie probleem geskenk in die geval van die boerpot-prys in die Suid-Afrikaanse nasionale lotery, Lotto, wat deur die viertal h49; 6; 6; 6i voorgestel word, en hoe die waarde van P(N; ) be nvloed word deur die manier waarop deelnmers hul spelversamelings selekteer.
Moser, Irene. "Applying external optimisation to dynamic optimisation problems." Swinburne Research Bank, 2008. http://hdl.handle.net/1959.3/22526.
Full text[A thesis submitted in total fulfillment of the requirements of for the degree of Doctor of Philosophy, Faculty of Information and Communication Technologies, Swinburne University of Technology, 2008]. Typescript. Includes bibliographical references p. 193-201.
Chu, Paul C. H. "A genetic algorithm approach for combinatorial optimisation problems." Thesis, Imperial College London, 1997. http://hdl.handle.net/10044/1/11491.
Full textBarake, M. A. "PROBE : a meta-heuristic for combinatorial optimisation problems." Thesis, University of East Anglia, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.368139.
Full textWhite, Bradley Michael. "Experimental Development of Automated Search Techniques for Discrete Combinatorial Optimisation." Thesis, Griffith University, 2009. http://hdl.handle.net/10072/365420.
Full textThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Griffith Business School
Griffith Business School
Full Text
Buljubasic, Mirsad. "Efficient local search for several combinatorial optimization problems." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS010/document.
Full textThis Ph.D. thesis concerns algorithms for Combinatorial Optimization Problems. In Combinatorial Optimization Problems the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. Specifically, in this research we consider three different problems in the field of Combinatorial Optimization including One-dimensional Bin Packing (and two similar problems), Machine Reassignment Problem and Rolling Stock Problem. The first one is a classical and well known optimization problem, while the other two are real world and very large scale problems arising in industry and have been recently proposed by Google and French Railways (SNCF) respectively. For each problem we propose a local search based heuristic algorithm and we compare our results with the best known results in the literature. Additionally, as an introduction to local search methods, two metaheuristic approaches, GRASP and Tabu Search are explained through a computational study on Set Covering Problem
Congram, Richard K. "Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimisation." Thesis, University of Southampton, 2000. https://eprints.soton.ac.uk/50630/.
Full textChiarandini, Marco. "Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems." Phd thesis, [S.l. : s.n.], 2005. https://tuprints.ulb.tu-darmstadt.de/595/1/ChiarandiniPhD.pdf.
Full textParis, Gabrielle. "Resolution of some optimisation problems on graphs and combinatorial games." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSE1180/document.
Full textI studied three optimization problems on graphs and combinatorial games.First, identifying codes were studied : vertices couteract faults. Identifying codes help locate the fault to repare it. We focused on circulant graphs by embedding them on infinite grids.Then, the marking and the coloring games were studied : two player games were one player wants to build something (a proper coloration or a proper marking) and the other wants to prevent the first player from doing so. For the marking game we studied the evolution of the strategy when modifying the graph. For the coloring game we defined a new edge-wise decomposition of graphs and we defined a new strategy on this decomposition that improves known results on planar graphs.In the end, I studied pure breaking games : two players take turns to break a heap of tokens in a given number of non-empty heaps. We focused on winning strategies for the game starting with a unique heap on n tokens. These games seem, on first sight, to be all regular : we showed this is the case for some of them and we gave a test to study one game at a time. Only one of these games does not seem to be regular, its behavior remains a mystery.To sum up, I studied three bilateral problems that use different methods and have different purposes in combinatorics
Joyce, Robert. "Dynamic optimisation of NP-hard combinatorial problems of engineering data sets." Thesis, Coventry University, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.261170.
Full textTayarani-Najar, M. H. "Analysis of the fitness landscape for the class of combinatorial optimisation problems." Thesis, University of Southampton, 2013. https://eprints.soton.ac.uk/355534/.
Full textMunera, Ramirez Danny. "Solving Hard Combinatorial Optimization Problems using Cooperative Parallel Metaheuristics." Thesis, Paris 1, 2016. http://www.theses.fr/2016PA01E074.
Full textCombinatorial Optimization Problems (COP) are widely used to model and solve real-life problems in many different application domains. These problems represent a real challenge for the research community due to their inherent difficulty, as many of them are NP-hard. COPs are difficult to solve with exact methods due to the exponential growth of the problem’s search space with respect to the size of the problem. Metaheuristics are often the most efficient methods to make the hardest problems tractable. However, some hard and large real-life problems are still out of the scope of even the best metaheuristic algorithms. Parallelism is a straightforward way to improve metaheuristics performance. The basic idea is to perform concurrent explorations of the search space in order to speed up the search process. Currently, the most advanced techniques implement some communication mechanism to exchange information between metaheuristic instances in order to try and increase the probability to find a solution. However, designing an efficient cooperative parallel method is a very complex task, and many issues about communication must be solved. Furthermore, it is known that no unique cooperative configuration may efficiently tackle all problems. This is why there are currently efficient cooperative solutions dedicated to some specific problems or more general cooperative methods but with limited performances in practice. In this thesis we propose a general framework for Cooperative Parallel Metaheuristics (CPMH). This framework includes several parameters to control the cooperation. CPMH organizes the explorers into teams; each team aims at intensifying the search in a particular region of the search space and uses intra-team communication. In addition, inter-team communication is used to ensure search diversification. CPMH allows the user to tune the trade-off between intensification and diversification. However, our framework supports different metaheuristics and metaheuristics hybridization. We also provide X10CPMH, an implementation of our CPMH framework developed in the X10 parallel language. To assess the soundness of our approach we tackle two hard real-life COP: hard variants of the Stable Matching Problem (SMP) and the Quadratic Assignment Problem (QAP). For all problems we propose new sequential and parallel metaheuristics, including a new Extremal Optimization-based method and a new hybrid cooperative parallel algorithm for QAP. All algorithms are implemented thanks to X10CPMH. A complete experimental evaluation shows that the cooperative parallel versions of our methods scale very well, providing high-quality solutions within a limited timeout. On hard and large variants of SMP, our cooperative parallel method reaches super-linear speedups. Regarding QAP, the cooperative parallel hybrid algorithm performs very well on the hardest instances, and improves the best known solutions of several instances
Randall, Marcus Christian, and n/a. "A General Modelling System and Meta-Heuristic Based Solver for Combinatorial Optimisation Problems." Griffith University. School of Environmental and Applied Science, 1999. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20051116.120133.
Full textRandall, Marcus. "A General Modelling System and Meta-Heuristic Based Solver for Combinatorial Optimisation Problems." Thesis, Griffith University, 1999. http://hdl.handle.net/10072/367399.
Full textThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Environmental and Applied Science
Science, Environment, Engineering and Technology
Full Text
Roland, Julien. "Inverse multi-objective combinatorial optimization." Doctoral thesis, Universite Libre de Bruxelles, 2013. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209383.
Full textoptimization takes into account this important aspect. This gives rise to many questions which are identified by a precise notation that highlights a large collection of inverse problems that could be investigated. In this thesis, a selection of inverse problems are presented and solved. This selection is motivated by their possible applications and the interesting theoretical questions they can rise in practice.
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished
Hauman, Charlotte. "The application of the cross-entropy method for multi-objective optimisation to combinatorial problems." Thesis, Stellenbosch : Stellenbosch University, 2012. http://hdl.handle.net/10019.1/71636.
Full textENGLISH ABSTRACT: Society is continually in search of ways to optimise various objectives. When faced with multiple and con icting objectives, humans are in need of solution techniques to enable optimisation. This research is based on a recent venture in the eld of multi-objective optimisation, the use of the cross-entropy method to solve multi-objective problems. The document provides a brief overview of the two elds, multi-objective optimisation and the cross-entropy method, touching on literature, basic concepts and applications or techniques. The application of the method to two problems is then investigated. The rst application is to the multi-objective vehicle routing problem with soft time windows, a widely studied problem with many real-world applications. The problem is modelled mathematically with a transition probability matrix that is updated according to cross-entropy principles before converging to an approximation solution set. The highly constrained problem is successfully modelled and the optimisation algorithm is applied to a set of benchmark problems. It was found that the cross-entropy method for multi-objective optimisation is a valid technique in providing feasible and non-dominated solutions. The second application is to a real world case study in blood management done at the Western Province Blood Transfusion Service. The conceptual model is derived from interviews with relevant stakeholders before discrete event simulation is used to model the system. The cross-entropy method is used to optimise the inventory policy of the system by simultaneously maximising the combined service level of the system and minimising the total distance travelled. By integrating the optimisation and simulation model, the study shows that the inventory policy of the service can improve signi cantly, and the use of the cross-entropy algorithm adequately progresses to a front of solutions. The research proves the remarkable width and simplicity of possible applications of the cross-entropy algorithm for multi-objective optimisation, whilst contributing to literature on the vehicle routing problem and blood management. Results on benchmark problems for the vehicle routing problem with soft time windows are provided and an improved inventory policy is suggested to the Western Province Blood Transfusion Service.
AFRIKAANSE OPSOMMING: Die mensdom is voortdurend op soek na maniere om verskeie doelwitte te optimeer. Wanneer die mens konfrontreer word met meervoudige en botsende doelwitte, is oplossingsmetodes nodig om optimering te bewerkstellig. Hierdie navorsing is baseer op 'n nuwe wending in die veld van multi-doelwit optimering, naamlik die gebruik van die kruisentropie metode om multi-doelwit probleme op te los. Die dokument verskaf 'n bre e oorsig oor die twee velde { multi-doelwit optimering en die kruis-entropie-metode { deur kortliks te kyk na die beskikbare literatuur, basiese beginsels, toepassingsareas en metodes. Die toepassing van die metode op twee onafhanklike probleme word dan ondersoek. Die eerste toepassing is di e van die multi-doelwit voertuigroeteringsprobleem met plooibare tydvensters. Die probleem word eers wiskundig modelleer met 'n oorgangswaarskynlikheidsmatriks. Die matriks word dan deur kruis-entropie beginsels opdateer voor dit konvergeer na 'n benaderingsfront van oplossings. Die oplossingsruimte is onderwerp aan heelwat beperkings, maar die probleem is suksesvol modelleer en die optimeringsalgoritme is gevolglik toegepas op 'n stel verwysingsprobleme. Die navorsing het gevind dat die kruis-entropie metode vir multi-doelwit optimering 'n geldige metode is om 'n uitvoerbare front van oplossings te beraam. Die tweede toepassing is op 'n gevallestudie van die bestuur van bloed binne die konteks van die Westelike Provinsie Bloedoortappingsdiens. Na aanleiding van onderhoude met die relevante belanghebbers is 'n konsepmodel geskep voor 'n simulasiemodel van die stelsel gebou is. Die kruis-entropie metode is gebruik om die voorraadbeleid van die stelsel te optimeer deur 'n gesamentlike diensvlak van die stelsel te maksimeer en terselfdetyd die totale reis-afstand te minimeer. Deur die optimerings- en simulasiemodel te integreer, wys die studie dat die voorraadbeleid van die diens aansienlik kan verbeter, en dat die kruis-entropie algoritme in staat is om na 'n front van oplossings te beweeg. Die navorsing bewys die merkwaardige wydte en eenvoud van moontlike toepassings van die kruis-entropie algoritme vir multidoelwit optimering, terwyl dit 'n bydrae lewer tot die afsonderlike velde van voertuigroetering en die bestuur van bloed. Uitslae vir die verwysingsprobleme van die voertuigroeteringsprobleem met plooibare tydvensters word verskaf en 'n verbeterde voorraadbeleid word aan die Westelike Provinsie Bloedoortappingsdiens voorgestel.
Montero, Elisabeth. "Calibration strategies for bio-inspired population-based algorithms that solve combinatorial optimization problems." Nice, 2011. http://www.theses.fr/2011NICE4040.
Full textSelection of proper values for parameters of bio-inspired algorithms is crucial to get good performance. To find these values is a complex process because parameter values depend on the problem that is being solved. Moreover, it is a high time consuming task and parameters are interrelated values. The first contribution of this thesis is the comparative study of features and performance of some automated parameter tuning methods. Advantages and disadvantages of these methods were identified. The main disadvantage of tuning methods is that they are high consuming time process. These methods search for parameters values focusing on statistically promising areas of the parameters search space. We also present an analysis of the potential of using these techniques to support the design process of evolutionary algorithms. In most cases, tuning methods are not able to discard elements that do not contribute to their operation. The main contribution of this thesis is related to the ability of varying parameter values during the execution of the algorithm. These kinds of approaches are known as parameter control methods. Two methods are proposed in this thesis for improving the performance of evolutionary algorithms by controlling its operators rates : Ac and Sac. Ac works in a population level rewarding operators that perfom good transformations during the iteration and punishing the others. Sac works in an individual level rewarding or punishing operators according to the performance of their applications in each individual. These both control methods can be incorporated to the evolutionary algorithm without introducing a meaningful cost in terms of time and without changing the original structure of the evolutionary algorithm. Variations of parameter values are based on current and past information about the operators performance. The incorporation of these techniques allows the algorithm to decide when and how much use each operator during the search process. Moreover, we propose the (C,n)-strategy for the CLONALG artificial immune system. In this case we control the amount of selected cells and clones produced in each iteration. The application of our control method allows us to reduce the amount of parameters to tune for the algorithm. Our control technique is able to manage the relationship between intensification and diversification stages of the search by varying the values of these parameters. From this work, we can conclude that parameter tuning techniques are able to find parameter values that show a good performance on the tuned algorithm. Most of these techniques require a previous analysis of the parameter search spaces and, in general, they require a considerable amount time. However, they can be able to make decisions about the design of the evolutionary algorithm. About the incorporation of parameter control strategies, we can conclude that it is possible to improve the efficiency of the algorithm, reducing the tuning effort by decreasing the number of parameters of tune. It is possible to vary parameter values during the search without changing the original design of the algorithm. Finally, the proposed techniques add a minimum amount of easily tunable new parameters. The development of tuning techniques able to work with any kind of parameters and capable to determine proper stopping criteria in order to do not waste resources is still an open research area. In this thesis we have shown that it is possible to perform on-line parameter variation in population-based algorithms. One interesting point of research is the automatic identification of the role of different components of the algorithm in order to automatize the design process of parameter control strategies
Baia, Amandio Pereira. "Branch and bound algorithms in combinatorial optimisation and their application in planning and distribution problems." Thesis, Coventry University, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.335421.
Full textHe, Fang. "Effective integrations of constraint programming, integer programming and local search for two combinatorial optimisation problems." Thesis, University of Nottingham, 2012. http://eprints.nottingham.ac.uk/14208/.
Full textCanzar, Stefan. "Lagrangian Relaxation - Solving NP-hard Problems in Computational Biology via Combinatorial Optimization." Phd thesis, Université Henri Poincaré - Nancy I, 2008. http://tel.archives-ouvertes.fr/tel-00388521.
Full textViolin, Alessia. "Mathematical programming approaches to pricing problems." Doctoral thesis, Universite Libre de Bruxelles, 2014. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209173.
Full textTo do so, the company must consider customers' reactions to these prices, as they may refuse to buy a given product or service if its price is too high. This is commonly known in literature as a pricing problem.
This class of problems, which is typically bilevel, was first studied in the 1990s and is NP-hard, although polynomial algorithms do exist for some particular cases. Many questions are still open on this subject.
The aim of this thesis is to investigate mathematical properties of pricing problems, in order to find structural properties, formulations and solution methods that are as efficient as possible. In particular, we focus our attention on pricing problems over a network. In this framework, an authority owns a subset of arcs and imposes tolls on them, in an attempt to maximise his/her revenue, while users travel on the network, seeking for their minimum cost path.
First, we provide a detailed review of the state of the art on bilevel pricing problems.
Then, we consider a particular case where the authority is using an unit toll scheme on his/her subset of arcs, imposing either the same toll on all of them, or a toll proportional to a given parameter particular to each arc (for instance a per kilometre toll). We show that if tolls are all equal then the complexity of the problem is polynomial, whereas in case of proportional tolls it is pseudo-polynomial.
We then address a robust approach taking into account uncertainty on parameters. We solve some polynomial cases of the pricing problem where uncertainty is considered using an interval representation.
Finally, we focus on another particular case where toll arcs are connected such that they constitute a path, as occurs on highways. We develop a Dantzig-Wolfe reformulation and present a Branch-and-Cut-and-Price algorithm to solve it. Several improvements are proposed, both for the column generation algorithm used to solve the linear relaxation and for the branching part used to find integer solutions. Numerical results are also presented to highlight the efficiency of the proposed strategies. This problem is proved to be APX-hard and a theoretical comparison between our model and another one from the literature is carried out.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
Sghir, Inès. "A Multi-Agent based Optimization Method for Combinatorial Optimization Problems." Thesis, Angers, 2016. http://www.theses.fr/2016ANGE0009/document.
Full textWe elaborate a multi-agent based optimization method for combinatorial optimization problems named MAOM-COP. It combines metaheuristics, multiagent systems and reinforcement learning. Although the existing heuristics contain several techniques to escape local optimum, they do not have an entire vision of the evolution of optimization search. Our main objective consists in using the multi-agent system to create intelligent cooperative methods of search. These methods explore several existing metaheuristics. MAOMCOP is composed of the following agents: the decisionmaker agent, the intensification agents and the diversification agents which are composed of the perturbation agent and the crossover agents. Based on learning techniques, the decision-maker agent decides dynamically which agent to activate between intensification agents and crossover agents. If the intensifications agents are activated, they apply local search algorithms. During their searches, they can exchange information, as they can trigger the perturbation agent. If the crossover agents are activated, they perform recombination operations. We applied MAOMCOP to the following problems: quadratic assignment, graph coloring, winner determination and multidimensional knapsack. MAOM-COP shows competitive performances compared with the approaches of the literature
Almeida, Coco Amadeu. "Robust covering problems : formulations, algorithms and an application." Thesis, Troyes, 2017. http://www.theses.fr/2017TROY0026/document.
Full textTwo robust optimization NP-Hard problems are studied in this thesis: the min-max regret Weighted Set Covering Problem (min-max regret WSCP) and the min-max regret Maximal Coverage Location Problem (min-max regret MCLP). The min-max regret WSCP and min-max regret MCLP are, respectively, the robust optimization counterparts of the Set Covering Problem and of the Maximal Coverage Location Problem. The uncertain data in these problems is modeled by intervals and only the minimum and maximum values for each interval are known. However, while the min-max regret WSCP is mainly studied theoretically, the min-max regret MCLP has an application in disaster logistics which is also investigated in this thesis. Two other robust optimization criteria were derived for the MCLP: the max-max MCLP and the min-max MCLP. In terms of methods, mathematical formulations, exact algorithms and heuristics were developed and applied to both problems. Computational experiments showed that the exact algorithms efficiently solved 14 out of 75 instances generated to the min-max regret WSCP and all realistic instances created to the min-max regret MCLP. For the simulated instances that was not solved to optimally in both problems, the heuristics developed in this thesis found solutions, as good as, or better than the exact algorithms in almost all instances. Concerning the application in disaster logistics, the robust models found similar solutions for realistic scenarios of the earthquakes that hit Kathmandu, Nepal in 2015. This indicates that we have got a robust solution, according to all optimization models
Maziere, Florian. "Modèles de parallélisme pour les métaheuristiques multi-objectifs." Thesis, Reims, 2019. http://www.theses.fr/2019REIMS002/document.
Full text.Many academic and industrial optimization problems are multi-objective and have been of particular interest to researchers in recent years. These problems usually do not have a single optimal solution but a set of best trade-off solutions which form the so-called Pareto front in the objective space. In order to approximate the Pareto front, multi-objective evolutionary algorithms (MOEAs) have been largely investigated in the fields of continuous and combinatorial optimization. Contrary to some classical algorithms, MOEAs have the ability to provide a number of solutions in one single run and are less sensitive to the shape of the Pareto front.As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, MOEAs could greatly benefit from today's high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today.This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii)Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models
Watrigant, Rémi. "Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20100/document.
Full textThe theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms
Hamid, Mona. "New local search in the space of infeasible solutions framework for the routing of vehicles." Thesis, University of Edinburgh, 2018. http://hdl.handle.net/1842/33177.
Full textSalazar-Neumann, Martha. "Advances in robust combinatorial optimization and linear programming." Doctoral thesis, Universite Libre de Bruxelles, 2010. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210192.
Full textUne des approches possibles pour résoudre des tels problèmes est de considérer les versions minimax regret, pour lesquelles résoudre un problème sous incertitude revient à trouver une solution qui s'écarte le moins possible de la valeur solution optimale dans tout les cas.
Dans le cas des incertitudes définies par intervalles, les versions minimax regret de nombreux problèmes combinatoires polynomiaux sont NP-difficiles, d'ou l'importance d'essayer de réduire l'espace des solutions. Dans ce contexte, savoir quand un élément du problème, représenté par une variable, fait toujours ou jamais partie d'une solution optimal pour toute réalisation des données (variables 1-persistentes et 0-persistentes respectivement), constitue une manière de réduire la taille du problème. Un des principaux objectifs de cette thèse est d'étudier ces questions pour quelques problèmes d'optimisation combinatoire sous incertitude.
Nous étudions les versions minimax regret du problème du choix de p éléments parmi m, de l'arbre couvrant minimum et des deux problèmes de plus court chemin. Pour de tels problèmes, dans le cas des incertitudes définis par intervalles, nous étudions le problème de trouver les variables 1- et 0-persistentes. Nous présentons une procédure de pre-traitement du problème, lequel réduit grandement la taille des formulations des versions de minimax regret.
Nous nous intéressons aussi à la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont incertains et l'ensemble des données incertaines est polyédral. Dans le cas où l'ensemble des incertitudes est défini par des intervalles, le problème de trouver le regret maximum est NP-difficile. Nous présentons des cas spéciaux ou les problèmes de maximum regret et de minimax regret sont polynomiaux. Dans le cas où l´ensemble des incertitudes est défini par un polytope, nous présentons un algorithme pour trouver une solution exacte au problème de minimax regret et nous discutons les résultats numériques obtenus dans un grand nombre d´instances générées aléatoirement.
Nous étudions les relations entre le problème de 1-centre continu et la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont évalués à l´aide des intervalles. En particulier, nous décrivons la géométrie de ce dernier problème, nous généralisons quelques résultats en théorie de localisation et nous donnons des conditions sous lesquelles certaines variables peuvet être éliminées du problème. Finalement, nous testons ces conditions dans un nombre d´instances générées aléatoirement et nous donnons les conclusions.
Doctorat en sciences, Orientation recherche opérationnelle
info:eu-repo/semantics/nonPublished
Balaprakash, Prasanna. "Estimation-based metaheuristics for stochastic combinatorial optimization: case studies in sochastic routing problems." Doctoral thesis, Universite Libre de Bruxelles, 2010. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210179.
Full textTo tackle stochastic routing problems, stochastic local search algorithms such as iterative improvement algorithms and metaheuristics are quite promising because they offer effective strategies to tackle the combinatorial nature of these problems. However, a crucial factor that determines the success of these algorithms in stochastic settings is the trade-off between the computation time needed to search for high quality solutions in a large search space and the computation time spent in computing the expected cost of solutions obtained during the search.
To compute the expected cost of solutions in stochastic routing problems, two classes of approaches have been proposed in the literature: analytical computation and empirical estimation. The former exactly computes the expected cost using closed-form expressions; the latter estimates the expected cost through Monte Carlo simulation.
Many previously proposed metaheuristics for stochastic routing problems use the analytical computation approach. However, in a large number of practical stochastic routing problems, due to the presence of complex constraints, the use of the analytical computation approach is difficult, time consuming or even impossible. Even for the prototypical stochastic routing problems that we consider in this thesis, the adoption of the analytical computation approach is computationally expensive. Notwithstanding the fact that the empirical estimation approach can address the issues posed by the analytical computation approach, its adoption in metaheuristics to tackle stochastic routing problems has never been thoroughly investigated.
In this thesis, we study two classical stochastic routing problems: the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demands and customers (VRPSDC). The goal of the thesis is to design, implement, and analyze effective metaheuristics that use the empirical estimation approach to tackle these two problems. The main results of this thesis are:
1) The empirical estimation approach is a viable alternative to the widely-adopted analytical computation approach for the PTSP and the VRPSDC;
2) A principled adoption of the empirical estimation approach in metaheuristics results in high performing algorithms for tackling the PTSP and the VRPSDC. The estimation-based metaheuristics developed in this thesis for these two problems define the new state-of-the-art.
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished
Cornu, Marek. "Local Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED043/document.
Full textMany Combinatorial Optimization problems consider several, often conflicting, objectives. This thesis deals with Local Search, data structures and Monte Carlo Search methods for finding the set of efficient solutions of such problems, which is the set of all best possible trade-offs given all the objectives.We propose a new approximation method called 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combining the notions of Pareto Local Search (PLS) and Decomposition. PLS is a local search descent adapted to Multi-Objective spaces, and Decomposition consists in the subdivision of the Multi-Objective problem into a number of Single-Objective problems. Two Single-Objective methods are considered: Iterated Local Search and Nested Monte Carlo Search. Two main components are embedded within the 2PIPLS/D framework. The first one generalizes and improves an existing method generating an initial set of solutions. The second one reduces efficiently the search space and accelerates PLS without notable impact on the quality of the generated approximation. We also introduce two new data structures for dynamically managing a set of incomparable solutions. The first one is specialized for the bi-objective case, while the second one is general.2PIPLS/D is applied to the bi-objective and tri-objective Traveling Salesman Problem and outperforms its competitors on tested instances. Then, 2PIPLS/D is instantiated on a new five-objective problem related to the recent territorial reform of French regions which resulted in the reassignment of departments to new larger regions
Pruvost, Geoffrey. "Contributions à l’optimisation multi-objectif à base de décomposition." Thesis, Université de Lille (2018-2021), 2021. http://www.theses.fr/2021LILUB026.
Full textIn this thesis, we are interested in multi-objective combinatorial optimization, and in particular in evolutionary algorithms based on decomposition. This type of approaches consists in decomposing the original multi-objective problem into multiple single-objective sub-problems that are then solved cooperatively. In this context, we consider the design and the analysis of new algorithmic components contributing to the establishment of the foundations of an optimization framework based on decomposition for multi-objective combinatorial problems known as "black box", i.e., for which the analytical form of the objective functions is not available to the solving algorithm. First of all, we investigate the key components for a better distribution of the computational efforts during the optimization process. To this end, we study the joint impact of the population size and of the number of solutions generated at each iteration, while proposing different strategies for selecting one ore multiple sub-problem(s) to be optimized at each stage. We then study different mechanisms allowing to escape from local optima. They are inspired by techniques from single-objective optimization, and we show they can significantly improve the convergence profile of the considered approaches. Finally, we consider the context of expensive optimization, where the evaluation of each solution is particularly intensive in terms of computational resources. This hence drastically restrict the budget allocated to the optimization process. As such, we investigate new components based on combinatorial meta-models, and we consider their integration within decomposition-based multi-objective evolutionary approaches
Heilporn, Géraldine. "Network pricing problems : complexity, polyhedral study and solution approaches." Thèse, Universite Libre de Bruxelles, 2008. http://hdl.handle.net/1866/6451.
Full textAlaya, Inès. "Optimisation multi-objectif par colonies de fourmis : cas des problèmes de sac à dos." Phd thesis, Université Claude Bernard - Lyon I, 2009. http://tel.archives-ouvertes.fr/tel-00603780.
Full textMinot, Maël. "Investigating decomposition methods for the maximum common subgraph and sum colouring problems." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEI120/document.
Full textThe objective of this thesis is, from a general standpoint, to design and evaluate decomposition methods for solving constrained optimisation problems. Two optimisation problems in particular are considered: the maximum common induced subgraph problem, in which the largest common part between two graphs is to be found, and the sum colouring problem, where a graph must be coloured in a way that minimises a sum of weights induced by the employed colours. The maximum common subgraph (MCIS) problem is notably difficult, with a strong applicability in domains such as biology, chemistry and image processing, where the need to measure the similarity between structured objects represented by graphs may arise. The outstanding difficulty of this problem makes it strongly advisable to employ a decomposition method, possibly coupled with a parallelisation of the solution process. However, existing decomposition methods are not well suited to solve the MCIS problem: some lead to a poor balance between subproblems, while others, like tree decomposition, are downright inapplicable. To enable the structural decomposition of such problems, Chmeiss et al. proposed an approach, TR-decomposition, acting at a low level: the microstructure of the problem. This approach had yet to be applied to the MCIS problem. We evaluate it in this context, aiming at reducing the size of the search space while also enabling parallelisation. The second problem that caught our interest is the sum colouring problem. It is an NP-hard variant of the widely known classical graph colouring problem. As in most colouring problems, it basically consists in assigning colours to the vertices of a given graph while making sure no neighbour vertices use the same colour. In the sum colouring problem, however, each colour is associated with a weight. The objective is to minimise the sum of the weights of the colours used by every vertex. This leads to generally harder instances than the classical colouring problem, which simply requires to use as few colours as possible. Only a few exact methods have been proposed for this problem. Among them stand notably a constraint programming (CP) model, a branch and bound approach, as well as an integer linear programming (ILP) model. We led an in-depth investigation of CP's capabilities to solve the sum colouring problem, while also looking into ways to make it more efficient. Additionally, we evaluated a combination of integer linear programming and constraint programming, with the intention of conciliating the strong points of these highly complementary approaches. We took inspiration from the classical backtracking bounded by tree decomposition (BTD) approach. We employ a tree decomposition with a strictly bounded height. We then derive profit from the complementarity of our approaches by developing a portfolio approach, able to choose one of the considered approaches automatically by relying on a number of features extracted from each instance
Benantar, Abdelaziz. "Optimisation pour des problèmes industriels de tournées de véhicules : vers une transition énergétique." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMLH12.
Full textThe thesis focuses on the study of real road transportation and distribution pro-blems. The question concerns in particular the optimization of two different vehicle routing problems arising in the distribution of petroleum products and the transfer of containers. The first problem, modelled as an application of the multi-compartment vehicle routing problem with time windows (MCVRPTW), is solved by using a tabu search method. The same method is then applied to two other variants. One introduces additional constraints related to loading operations for petroleum products on the compartments, while the other one includes the ad-justment concept in quantities applied for. Moreover, in the context of an energy transition, we addressed the container transfer problem using a fleet of electric trucks in the industrial port zone of Le Havre. The optimization involves two levels : the strategic level for dimensioning electrical infrastructures and the operational level for constructing the vehicle routes. Only the strategic level is tackled with a research project thanks to a coupling of optimization and simulation
Siala, Mohamed. "Search, propagation, and learning in sequencing and scheduling problems." Thesis, Toulouse, INSA, 2015. http://www.theses.fr/2015ISAT0008/document.
Full textSequencing and scheduling involve the organization in time of operations subject to capacity and resource constraints. We propose in this dissertation several improvements to the constraint satisfaction and combinatorial optimization methods for solving these problems. These contributions concern three different aspects: how to choose the next node to explore (search)? how much, and how efficiently, one can reduce the search space (propagation)? and what can be learnt from previous failures (learning)? Our contributions start with an empirical study of search heuristics for the well known car-sequencing problem. This evaluation characterizes the key aspects of a good heuristic and shows that the search strategy is as important as the propagation aspect in this problem. Second, we carefully investigate the propagation aspect in a class of sequencing problems. In particular, we propose an algorithm for filtering a type of sequence constraints which worst case time complexity is lower than the best known upper bound, and indeed optimal. Third, we investigate the impact of clause learning for solving the car-sequencing problem. In particular, we propose reduced explanations for the new filtering. The experimental evaluation shows compelling evidence supporting the importance of clause learning for solving efficiently this problem. Next, we revisit the general approach of lazy generation for the Boolean variables encoding the domains. Our proposition avoids a classical redundancy issue without computational overhead. Finally, we investigate conflict analysis algorithms for solving disjunctive scheduling problems. In particular, we introduce a novel learning procedure tailored to this family of problems. The new conflict analysis differs from conventional methods by learning clauses whose size are not function of the scheduling horizon. Our comprehensive experimental study with traditional academic benchmarks demonstrates the impact of the novel learning scheme that we propose. In particular, we find new lower bounds for a well known scheduling benchmark
Zhang, Naiyu. "Cellular GPU Models to Euclidean Optimization Problems : Applications from Stereo Matching to Structured Adaptive Meshing and Traveling Salesman Problem." Thesis, Belfort-Montbéliard, 2013. http://www.theses.fr/2013BELF0215/document.
Full textThe 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
Sarpong, Boadu Mensah. "Column generation for bi-objective integer linear programs : application to bi-objective vehicle routing problems." Phd thesis, INSA de Toulouse, 2013. http://tel.archives-ouvertes.fr/tel-00919861.
Full textKaddani, Sami. "Partial preference models in discrete multi-objective optimization." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED012/document.
Full textMulti-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
Pereira, Vargas Liguori Pedro. "Polyhedral approaches for some network design problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED074.
Full textThis theses study the polyhedral aspects of some network design problems, focusing most on the aspects related to connectivity of the substructures necessary to build reliable network applications. At theheart of many different network design applications lies the fact that one must provide a connected subnetwork (which can be viewed as a collection of vertices or edges inducing a connected subgraph) exhibiting other desirable properties, like achieving some level of survivability or robustness, capacity constraints,or other types of budgetary constraints, depending on the context.A majority of the studies conductedand of the algorithms developed tryto take advantage of those particular aspects that differentiate one application from another, and not much attention has been given to the aspectsthat bring together these questions. Most of the studies conducted and the algorithms developed try to take advantage of those particular aspects that differentiate one application from another, and not much attention has been given to the aspects that bring together these questions. Hence, this work tries to develop an unified approach capable of exploring the most pertinent aspects of network design problems hoping that this can lead to thoughtful insights to more specific problems, being a valuable contribution to the research community and it
Sun, Wen. "Heuristic Algorithms for Graph Coloring Problems." Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0027/document.
Full textThis thesis concerns four NP-hard graph coloring problems, namely, graph coloring (GCP), equitable coloring (ECP), weighted vertex coloring (WVCP) and k-vertex-critical subgraphs (k-VCS). These problems are extensively studied in the literature not only for their theoretical intractability, but also for their real-world applications in many domains. Given that they belong to the class of NP-hard problems, it is computationally difficult to solve them exactly in the general case. For this reason, this thesis is devoted to developing effective heuristic approaches to tackle these challenging problems. We develop a reduction memetic algorithm (RMA) for the graph coloring problem, a feasible and infeasible search algorithm (FISA) for the equitable coloring problem, an adaptive feasible and infeasible search algorithm (AFISA) for the weighted vertex coloring problem and an iterated backtrack-based removal (IBR) algorithm for the k-VCS problem. All these algorithms were experimentally evaluated and compared with state-of-the-art methods
Lokhov, Andrey Y. "Dynamic cavity method and problems on graphs." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112331/document.
Full textA large number of optimization, inverse, combinatorial and out-of-equilibrium problems, arising in the statistical physics of complex systems, allow for a convenient representation in terms of disordered interacting variables defined on a certain network. Although a universal recipe for dealing with these problems does not exist, the recent years have seen a serious progress in understanding and quantifying an important number of hard problems on graphs. A particular role has been played by the concepts borrowed from the physics of spin glasses and field theory, that appeared to be extremely successful in the description of the statistical properties of complex systems and in the development of efficient algorithms for concrete problems.In the first part of the thesis, we study the out-of-equilibrium spreading problems on networks. Using dynamic cavity method on time trajectories, we show how to derive dynamic message-passing equations for a large class of models with unidirectional dynamics -- the key property that makes the problem solvable. These equations are asymptotically exact for locally tree-like graphs and generally provide a good approximation for real-world networks. We illustrate the approach by applying the dynamic message-passing equations for susceptible-infected-recovered model to the inverse problem of inference of epidemic origin. In the second part of the manuscript, we address the optimization problem of finding optimal planar matching configurations on a line. Making use of field-theory techniques and combinatorial arguments, we characterize a topological phase transition that occurs in the simple Bernoulli model of disordered matching. As an application to the physics of the RNA secondary structures, we discuss the relation of the perfect-imperfect matching transition to the known molten-glass transition at low temperatures, and suggest generalized models that incorporate a one-to-one correspondence between the contact matrix and the nucleotide sequence, thus giving sense to the notion of effective non-integer alphabets
Bontoux, Boris. "Techniques hybrides de recherche exacte et approchée : application à des problèmes de transport." Phd thesis, Université d'Avignon, 2008. http://tel.archives-ouvertes.fr/tel-00459367.
Full textMehdi, Malika. "PARALLEL HYBRID OPTIMIZATION METHODS FOR PERMUTATION BASED PROBLEMS." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2011. http://tel.archives-ouvertes.fr/tel-00841962.
Full textSheppard, Nicholas Paul. "Self-Reduction for Combinatorial Optimisation." University of Sydney. Computer Science, 2001. http://hdl.handle.net/2123/797.
Full textBelhoul, Lyes. "Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée." Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090060/document.
Full textOur aim in this thesis is to propose efficient algorithms for solving difficult combinatorial optimization problems. Our algorithms are based on a generic method of ordered enumeration. Initially, we describe the principle of ordered enumeration which consists in generating in a specific order solutions of a relaxed problem associated to the difficult main problem, until meeting a proof of the optimality of a feasible solution. We construct a generic procedure in the general context of combinatorial optimization problems. In a second step we discuss applications of our algorithm on some difficult problems which admit the assignment problem as relaxation. The first special case we study is the search for a compromise solution to the multiobjective assignment problem. The second application is the asymmetric travelling salesman problem, which contains sub-tour constraints in addition to the constraints of the assignment problem
Merabet, Massinissa. "Solutions optimales des problèmes de recouvrement sous contraintes sur le degré des nœuds." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20138/document.
Full textThe work conducted in this thesis is focused on the minimum spanning problems in graphs under constraints on the vertex degrees. As the spanning tree covers the vertices of a connected graph with a minimum number of links, it is generally proposed as a solution for this kind of problems. However, for some applications such as the routing in optical networks, the solution is not necessarily a sub-graph. In this thesis, we assume that the degree constraints are due to a limited instantaneous capacity of the vertices and that the only pertinent requirement on the spanning structure is its connectivity. In that case, the solution may be different from a tree. We propose the reformulation of this kind of spanning problems. To find the optimal coverage of the vertices, an extension of the tree concept called hierarchy is proposed. Our main purpose is to show its interest regarding the tree in term of feasibility and costs of the coverage. Thus, we take into account two types of degree constraints: either an upper bound on the degree of vertices and an upper bound on the number of branching vertices. We search a minimum cost spanning hierarchy in both cases. Besides, we also illustrate the applicability of hierarchies by studying a problem that takes more into account the reality of the optical routing. For all those NP-hard problems, we show the interest of the spanning hierarchy for both costs of optimal solutions and performance guarantee of approximate solutions. These results are confirmed by several experimentations on random graphs