Rozprawy doktorskie: „Combinatorial optimisation problems”

1

Namazi, Majid. "Learning in Combinatorial Constraint Optimisation". Thesis, Griffith University, 2022. http://hdl.handle.net/10072/419082.

Pełny tekst źródła

Streszczenie:

Many real-world problems can be modelled as constraint optimisation problems (COPs). Each COP includes a set of variables with domains of values, constraints on the assignments to the variables, and an objective function, which should be minimised or maximised. In this thesis, we consider only combinatorial COPs, where domains of the variables are discrete. A component is a subproblem of a COP with specific variables, assignable values or constraints. Most practical COPs, including waste collection, mail delivery, supply chain management, and travelling thief problem (TTP), have more than one component. Existing methods for solving COPs, especially multi-component COPs, repeatedly solve the same problem or subproblem but do not take advantage of learning during the search. This research aimed to apply memorising and online or adaptive machine learning models. The memory buffers and the ML models are built, deployed, and updated during the search to improve search efficacy and efficiency in solving COPs, especially multi-component ones. In this research, we have developed a history memorising method to enhance diversity and effectiveness in solving COPs. Also, we have developed three online machine learning-based methods, one coordination learning for improving efficacy and two surrogate models for enhancing the efficiency of TTP solving. Our proposed solver, CoCo, is currently the state-of-the-art solver for solving TTP. History memorising is an online low-level learning method to keep previously visited solutions or their objective values to avoid or escape from local optima during the search. The Late Acceptance Hill Climbing (LAHC) is a history memorising metaheuristic with promising performance on some COP domains. It aims to overcome the main downside of the traditional Hill Climbing (HC) search, which is often quickly trapped in a local optimum due to strictly accepting only non-worsening moves within each iteration. In contrast, LAHC also accepts worsening moves by keeping the objective values of the previously visited solutions in a limited-size circular memory. It compares the fitness values of candidate solutions against the least recent element in the circular memory to decide on accepting or rejecting them. However, we have realised that whenever all values in memory become the same, LAHC behaves like HC and gets stuck in local optima. We propose an improved form of LAHC called Diversified Late Acceptance Search (DLAS) for solving COPs in general, which usually uses much smaller memory, converges much faster than LAHC and escapes local optima much better than LAHC. The proposed DLAS approach outperforms LAHC on benchmark sets of Travelling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP) instances. TTP is an academic proxy for the waste collection and mail delivery real-world optimisation problems composed of TSP and Knapsack Problem (KP). In TTP, a thief makes a cyclic tour through a set of cities while collecting profitable items scattered over the cities into a rented capacitated knapsack. As the weight of the knapsack increases, the thief’s speed decreases; hence the renting cost increases. Solving TTP aims to maximise profit while minimising the renting cost simultaneously, which means maximising the difference between profit and renting cost. Existing TTP solvers typically employ interleaving and solve one component at a time while keeping the solution of the other component unchanged. This form of interleaving essentially means poor coordination in solving TTP. In this thesis, we first show that a simple local search based coordination approach does not work in TTP. Then, to adequately address interdependence between TSP and KP components, we propose a human-designed coordination heuristic that adjusts collection plans during the exploration of cyclic tours. We further propose another human-designed coordination heuristic that explicitly exploits the cyclic tours in selecting items during collection plan exploration. Lastly, we propose an online machine learning-based coordination heuristic that captures the characteristics of the two human-designed coordination heuristics while solving any TTP instance. Our proposed coordination-based approaches help our TTP solver, cooperative coordination (CoCo), significantly outperform existing state-of-the-art TTP solvers on a set of benchmark TTP instances. Our proposed CoCo solver modifies a TTP instance’s underlying TSP and KP solutions in an iterative interleaved fashion. The TSP solution as a cyclic tour is typically changed in a deterministic way using the steepest-ascent Hill-Climbing (HC) search similar to other cooperative solvers. In contrast, changes to the KP solution typically involve a random HC search, effectively resulting in a quasi-meandering exploration of the TTP solution space. Once CoCo reaches a plateau, it restarts the iterative search of the TTP solution space by using a new initial cyclic tour. We have noticed that the final objective value remains almost the same if the same or similar initial cyclic tour is tried several times by CoCo or the other cooperative TTP solvers. Considering this semideterministic nature of the state-of-the-art cooperative TTP solvers, we propose two adaptive and online surrogate models to filter out non-promising initial cyclic tours to improve search efficiency. These surrogate models are automatically built, updated and deployed while solving any TTP instance. The first model is a Support Vector Regression (SVR)-based black-box model, and the second is a K Nearest Neighbour (KNN)-based white-box simulation model. Both models help to filter out non-promising initial cyclic tours while losing a small number of the cyclic tours leading to the best overall solutions. However, the KNN-based white-box simulation model is more accurate and efficient.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Info & Comm Tech
Science, Environment, Engineering and Technology
Full Text

Style APA, Harvard, Vancouver, ISO itp.

2

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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

Voudouris, Christos. "Guided local search for combinatorial optimisation problems". Thesis, University of Essex, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.361019.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

4

Lee, 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

5

Du, Plessis Andre. "On two combinatorial optimisation problems involving lotteries". Thesis, Stellenbosch : University of Stellenbosch, 2010. http://hdl.handle.net/10019.1/4137.

Pełny tekst źródła

Streszczenie:

Thesis (MComm (Logistics))--University of Stellenbosch, 2010.
ENGLISH 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.

Style APA, Harvard, Vancouver, ISO itp.

6

Moser, Irene. "Applying external optimisation to dynamic optimisation problems". Swinburne Research Bank, 2008. http://hdl.handle.net/1959.3/22526.

Pełny tekst źródła

Streszczenie:

Thesis (Ph.D) - Swinburne University of Technology, Faculty of Information & Communication Technologies, 2008.
[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.

Style APA, Harvard, Vancouver, ISO itp.

7

Chu, Paul C. H. "A genetic algorithm approach for combinatorial optimisation problems". Thesis, Imperial College London, 1997. http://hdl.handle.net/10044/1/11491.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

8

Barake, 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

9

White, Bradley Michael. "Experimental Development of Automated Search Techniques for Discrete Combinatorial Optimisation". Thesis, Griffith University, 2009. http://hdl.handle.net/10072/365420.

Pełny tekst źródła

Streszczenie:

A suite of techniques for finding the optimal solutions for a set of discrete combinatorial problems was developed. An experimental approach was used, with a suitable test-bed found in a class of word-puzzles. The crux of such research is that seeking optimal solutions to discrete combinatorial problems requires the use of deterministic algorithms. Attention was focused on the development of new techniques capable of exhausting the search space more efficiently. Although research was restricted to tractable problems, exhaustion of the search space was recognised to be practically infeasible for all but small problem instances. Thus the size and complexity of the problems examined was necessarily restricted. On these grounds the selection of an appropriate test-bed was fundamental to the research. Complex word problems were used because they encompass a wide range of discrete combinatorial problems, but have only a small literature. The specific puzzle examples employed as test-beds had all been used in public competitions with solutions submitted by thousands of humans, with the winning solutions and scores published. This allowed a simple and independent initial benchmark of success. The techniques developed could be judged to be at least partially successful in that they were able to at least equal and in some cases beat the highest recorded scores. The general problem of benchmarking is discussed. It was observed that small changes to the test bed puzzles or to the techniques would often impact dramatically on the results. In an attempt to isolate the reasons for this, a focused view of the search algorithms was adopted. Complex holistic algorithms were broken into smaller sub-algorithmic categories, such as: node selection, domain maintenance, forward tracking, backtracking, branch-and-bound, primary slot selection, variable ordering, value ordering, and constraint ordering. Within each of these categories a range of variations is presented. Techniques for removing inconsistencies prior to search were also experimented with. These consistency pre-processors were found to have a minimal and at times detrimental effect on search times when a good selection of search techniques was used. However, they were found to offer considerable benefits in instances where a poor selection of search techniques was chosen. As such these consistency pre-processors may be viewed as useful in terms of a risk management strategy for solving these problems. Whilst not the primary focus of this research experimentation with stochastic techniques within a deterministic framework was performed. The purpose of which was to gauge the impact of generating good solutions prior to an exhaustive search. A technique developed was observed to frequently improve the time taken to form an optimal solution, and improve the total time taken to exhaust the search space. While the major effort in the research was necessarily spent in developing and testing these algorithms and their implementations, specific attention was paid to the methodological problems inherent in experimental approaches to program development.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Griffith Business School
Griffith Business School
Full Text

Style APA, Harvard, Vancouver, ISO itp.

10

Buljubasic, Mirsad. "Efficient local search for several combinatorial optimization problems". Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS010/document.

Pełny tekst źródła

Streszczenie:

Cette thèse porte sur la conception et l'implémentation d'algorithmes approchés pour l'optimisation en variables discrètes. Plus particulièrement, dans cette étude nous nous intéressons à la résolution de trois problèmes combinatoires difficiles : le « Bin-Packing », la « Réaffectation de machines » et la « Gestion des rames sur les sites ferroviaires ». Le premier est un problème d'optimisation classique et bien connu, tandis que les deux autres, issus du monde industriel, ont été proposés respectivement par Google et par la SNCF. Pour chaque problème, nous proposons une approche heuristique basée sur la recherche locale et nous comparons nos résultats avec les meilleurs résultats connus dans la littérature. En outre, en guise d'introduction aux méthodes de recherche locale mise en œuvre dans cette thèse, deux métaheuristiques, GRASP et Recherche Tabou, sont présentées à travers leur application au problème de la couverture minimale
This 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

Style APA, Harvard, Vancouver, ISO itp.

11

Congram, Richard K. "Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimisation". Thesis, University of Southampton, 2000. https://eprints.soton.ac.uk/50630/.

Pełny tekst źródła

Streszczenie:

In this thesis, we study neighbourhoods of exponential size that can be searched in polynomial time. Such neighbourhoods are used in local search algorithms for classes of combinatorial optimisation problems. We introduce a method, called dynasearch, of constructing new neighbourhoods, and of viewing some previously derived exponentially sized neighbourhoods which are searchable in polynomial time. We produce new neighbourhoods by combining simple well-known neighbourhood moves (such as swap, insert, and k-opt) so that the moves can be performed together as a single move. In dynasearch neighbourhoods, the moves are combined in such a way that the effect of the combined move on the objective function is equal to the sum of the effects of the individual moves from the underlying neighbourhood. Dynasearch neighbourhoods can be formed using dynamic programing from underlying moves: • nested within each other; • disjoint from each other; • and in the case of the TSP overlapping one another. Our dynasearch neighbourhoods made from underlying disjoint moves are successfully implemented within well-known local search methods to form competitive algorithms for the travelling salesman problem and state-of-the-art algorithms for the total weighted tardiness problem and linear ordering problem. By viewing moves from some known travelling salesman problem neighbourhoods as a combination of underlying moves, each reversing a section of the tour, greater insight into the structure of the neighbourhoods may be obtained. This insight has both enabled us to calculate the size of a number of neighbourhoods and demonstrate how some neighbourhoods are contained within others.

Style APA, Harvard, Vancouver, ISO itp.

12

Chiarandini, 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.

Pełny tekst źródła

Streszczenie:

Graph colouring is a combinatorial optimisation problem consisting in colouring the vertices of a graph such that no vertices connected by an edge receive the same colour. The minimal number of colours for which such a colouring exists is an intrinsic property of the graph and is called chromatic number. Many real life situations, such as the frequency assignment in mobile networks or the scheduling of courses at a university, can be modelled in this way. Colouring planar graphs, such as maps can be easy, and four colours suffice, but real life systems are much more complex. When modelled by graph colouring, they entail general graphs of large size and include more sophisticated constraints than those representable by simple unweighted edges. Stochastic Local Search (SLS) methods are approximate techniques for efficiently solving these complex combinatorial optimisation problems. They typically consist of construction algorithms, iterative improvement algorithms, and meta-components, better known as metaheuristics. The first two are strongly problem dependent and require the exploitation of problem-specific knowledge, while the last are more general concepts to guide the first two components. The instantiation of SLS algorithms arises from the combination of concrete algorithmic components. This task is complex due to the many possible combinations and the need of determining a certain number of parameters. Empirical tests become then necessary to take the correct decisions. The starting point of this work is the definition of the statistical methods that are appropriate for the analysis of SLS algorithms. We argue that the assumptions for the application of parametric tests are often violated and opt for two alternative methods: permutation and rank-based tests. Our work contributes to the development of permutation tests and to their introduction in the analysis of SLS algorithms. In addition, we transfer a graphical representation of results through simultaneous confidence intervals from the parametric to the non-parametric cases. This representation has the advantage of conveying in one single graph both descriptive and inferential statistics. The developed statistical methods serve for the analysis of SLS algorithms on the graph colouring problem and one of its many possible generalisations, the set T-colouring problem. Several SLS algorithms have been proposed in the literature for the graph colouring problem but no ``unbiased'' comparison has been attempted. A similar situation holds for the set T-colouring problem. In both cases, we design new algorithms, re-implement the most prominent methods, and finally compare them in a rigorous experimental analysis. As the final step, we study SLS algorithms for solving a university course timetabling problem. The design of algorithm components stems from the knowledge gained on the graph colouring problems but the assemblage and configuration of these components is carried out with a systematic methodology. The focus in this context was on the selection of one single algorithm to submit to an algorithm competition. The methodology is presented as an engineering process characterised by the interaction of SLS components design and empirical tests. We deem that this methodological approach is appropriate for the application of SLS methods to complex real life problems. The main results are the following: on the graph colouring problem, the simple Tabu Search with one-exchange neighbourhood remains a very competitive approach and the use of a very large scale neighbourhood is not profitable; on the set T-colouring problem, the best overall algorithm is an Adaptive Iterated Greedy also based on Tabu Search with one-exchange neighbourhood which, under certain circumstances, can be further improved by a restricted exact reassignment of colours; the use of an engineering methodology based on sequential testing is particularly suitable for the application of SLS methods, as it led us to devise the algorithm whose solutions for course timetabling ranked the best out of 24 feasible submissions at the International Timetabling Competition held in 2003.

Style APA, Harvard, Vancouver, ISO itp.

13

Paris, Gabrielle. "Resolution of some optimisation problems on graphs and combinatorial games". Thesis, Lyon, 2018. http://www.theses.fr/2018LYSE1180/document.

Pełny tekst źródła

Streszczenie:

J'ai étudié trois problèmes d'optimisation dans les graphes et les jeux combinatoires.Tout d'abord, les codes identifiants dans les graphes où les sommets font faces à des failles: les codes cherchent à repérer les failles pour les réparer. On s'est intéressé aux codes identifiants dans les graphes circulants en utilisant des plongements de ces graphes dans des grilles infinies.Ensuite, j'ai étudié le jeu de marquage de sommets et le jeu de coloration d'arêtes: ici deux joueurs se font face, le premier cherche à construire une coloration correcte (ou un marquage correct) et le deuxième cherche à l'en empêcher. Pour le jeu de marquage on s'est intéressé aux changements de stratégie gagnante lorsqu'on modifie le graphe. Pour le jeu de coloration d'arêtes on a donné une stratégie gagnante pour le premier joueur pourvu que le graphe considéré admette une certaine décomposition sur les arêtes. On améliore notamment des résultats sur les graphes planaires.Enfin j'ai étudié les jeux à tas purement de casse: deux joueurs à tour de rôle prennent un tas et le cassent en un certain nombre de tas non vides. On s'intéresse aux stratégies gagnantes lorsque les joueurs jouent sur un unique tas contenant n jetons. Ces jeux de pure casse semblent, à l'oeil nu, être réguliers. On a montré que c'est effectivement le cas pour certains et on a donné un test qui permet de déterminer la régularité cas par cas. Un seul cas ne semble pas correspondre à cette régularité: son comportement reste un mystère.En conclusion, je me suis intéressé à trois problèmes bilatéraux qui utilisent différentes méthodes et qui remplissent des propos différents dans le domaine de la combinatoire
I 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

Style APA, Harvard, Vancouver, ISO itp.

14

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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

15

Tayarani-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/.

Pełny tekst źródła

Streszczenie:

Anatomy of the fitness landscape for a group of well known combinatorial optimisation problems is studied in this research and the similarities and the differences between their landscapes are pointed out. In this research we target the analysis of the fitness landscape for MAX-SAT, Graph-Colouring, Travelling Salesman and Quadratic Assignment problems. Belonging to the class of NP-Hard problems, all these problems become exponentially harder as the problem size grows. We study a group of properties of the fitness landscape for these problems and show what properties are shared by different problems and what properties are different. The properties we investigate here include the time it takes for a local search algorithm to find a local optimum, the number of local and global optima, distance between local and global optima, expected cost of found optima, probability of reaching a global optimum and the cost of the best configuration in the search space. The relationship between these properties and the system size and other parameters of the problems are studied, and it is shown how these properties are shared or differ in different problems. We also study the long-range correlation within the search space, including the expected cost in the Hamming sphere around the local and global optima, the basin of attraction of the local and global optima and the probability of finding a local optimum as a function of its cost. We believe these information provide good insight for algorithm designers.

Style APA, Harvard, Vancouver, ISO itp.

16

Munera, Ramirez Danny. "Solving Hard Combinatorial Optimization Problems using Cooperative Parallel Metaheuristics". Thesis, Paris 1, 2016. http://www.theses.fr/2016PA01E074.

Pełny tekst źródła

Streszczenie:

Les Problèmes d’Optimisation Combinatoire (COP) sont largement utilisés pour modéliser et résoudre un grand nombre de problèmes industriels. La résolution de ces problèmes pose un véritable défi en raison de leur inhérente difficulté, la plupart étant NP-difficiles. En effet, les COP sont difficiles à résoudre par des méthodes exactes car la taille de l’espace de recherche à explorer croît de manière exponentielle par rapport à la taille du problème. Les méta-heuristiques sont souvent les méthodes les plus efficaces pour résoudre les problèmes les plus difficiles. Malheureusement, bien des problèmes réels restent hors de portée des meilleures méta-heuristiques. Le parallélisme permet d’améliorer les performances des méta-heuristiques. L’idée de base est d’avoir plusieurs instances d’une méta-heuristique explorant de manière simultanée l’espace de recherche pour accélérer la recherche de solution. Les meilleures techniques font communiquer ces instances pour augmenter la probabilité de trouver une solution. Cependant, la conception d’une méthode parallèle coopérative n’est pas une tâche aisée, et beaucoup de choix cruciaux concernant la communication doivent être résolus. Malheureusement, nous savons qu’il n’existe pas d’unique configuration permettant de résoudre efficacement tous les problèmes. Ceci explique que l’on trouve aujourd’hui des systèmes coopératifs efficaces mais conçus pour un problème spécifique ou bien des systèmes plus génériques mais dont les performances sont en général limitées. Dans cette thèse nous proposons un cadre général pour les méta-heuristiques parallèles coopératives (CPMH). Ce cadre prévoit plusieurs paramètres permettant de contrôler la coopération. CPMH organise les instances de méta-heuristiques en équipes ; chaque équipe vise à intensifier la recherche dans une région particulière de l’espace de recherche. Cela se fait grâce à des communications intra-équipes. Des communications inter-équipes permettent quant a` elles d’assurer la diversification de la recherche. CPMH offre à l’utilisateur la possibilité d’ajuster le compromis entre intensification et diversification. De plus, ce cadre supporte différentes méta-heuristiques et permet aussi l’hybridation de méta-heuristiques. Nous proposons également X10CPMH, une implémentation de CPMH, écrite en langage parallèle X10. Pour valider notre approche, nous abordons deux COP du monde industriel : des variantes difficiles du Problème de Stable Matching (SMP) et le Problème d’Affectation Quadratique (QAP). Nous proposons plusieurs méta-heuristiques originales en version séquentielle et parallèle, y compris un nouvelle méthode basée sur l’optimisation extrémale ainsi qu’un nouvel algorithme hybride en parallèle coopératif pour QAP. Ces algorithmes sont implémentés grâce à X10CPMH. L’évaluation expérimentale montre que les versions avec parallélisme coopératif offrent un très bon passage à l’échelle tout en fournissant des solutions de haute qualité. Sur les variantes difficiles de SMP, notre méthode coopérative offre des facteurs d’accélération super-linéaires. En ce qui concerne QAP, notre méthode hybride en parallèle coopératif fonctionne très bien sur les cas les plus difficiles et permet d’améliorer les meilleures solutions connues de plusieurs instances
Combinatorial 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 diﬃcult 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-oﬀ 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

Style APA, Harvard, Vancouver, ISO itp.

17

Randall, Marcus Christian, i 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.

Pełny tekst źródła

Streszczenie:

There are many real world assignment, scheduling and planning tasks which can be classified as combinatorial optimisation problems (COPs). These are usually formulated as a mathematical problem of minimising or maximising some cost function subject to a number of constraints. Usually, such problems are NP hard, and thus, whilst it is possible to find exact solutions to specific problems, in general only approximate solutions can be found. There are many algorithms that have been proposed for finding approximate solutions to COPs, ranging from special purpose heuristics to general search meta-heuristics such as simulated annealing and tabu search. General meta-heuristic algorithms like simulated annealing have been applied to a wide range of problems. In most cases, the designer must choose an appropriate data structure and a set of local operators that define a search neighbourhood. The variability in representation techniques, and suitable neighbourhood transition operators, has meant that it is usually necessary to develop new code for each problem. Toolkits like the one developed by Ingber's Adaptive Simulated Annealing (Ingber 1993, 1996) have been applied to assist rapid prototyping of simulated annealing codes, however, these still require the development of new programs for each type of problem. There have been very few attempts to develop a general meta-heuristic solver, with the notable exception being Connolly's General Purpose Simulated Annealing (Connolly 1992). In this research, a general meta-heuristic based system is presented that is suitable for a wide range of COPs. The main goal of this work is to build an environment in which it is possible to specify a range of COPs using an algebraic formulation, and to produce a tailored solver automatically. This removes the need for the development of specific software, allowing very rapid prototyping. Similar techniques have been available for linear programming based solvers for some years in the form of the GAMS (General Algebraic Modelling System) (Brooke, Kendrick, Meeraus and Raman 1997) and AMPL (Fourer, Gay and Kernighan 1993) interfaces. The new system is based on a novel linked list data structure rather than the more conventional vector notation due to the natural mapping between COPS and lists. In addition, the modelling system is found to be very suitable for processing by meta-heuristic search algorithms as it allows the direct application of common local search operators. A general solver is built that is based on the linked list modelling system. This system is capable of using meta-heuristic search engines such as greedy search, tabu search and simulated annealing. A number of implementation issues such as generating initial solutions, choosing and invoking appropriate local search transition operators and producing suitable incremental cost expressions, are considered. As such, the system can been seen as a good test-bench for model prototypers and those who wish to test various meta-heuristic implementations in a standard way. However, it is not meant as a replacement or substitute for efficient special purpose search algorithms. The solver shows good performance on a wide range of problems, frequently reaching the optimal and best-known solutions. Where this is not the case, solutions within a few percent deviation are produced. Performance is dependent on the chosen transition operators and the frequency with which each is applied. To a lesser extent, the performance of this implementation is influenced by runtime parameters of the meta-heuristic search engine.

Style APA, Harvard, Vancouver, ISO itp.

18

Randall, Marcus. "A General Modelling System and Meta-Heuristic Based Solver for Combinatorial Optimisation Problems". Thesis, Griffith University, 1999. http://hdl.handle.net/10072/367399.

Pełny tekst źródła

Streszczenie:

There are many real world assignment, scheduling and planning tasks which can be classified as combinatorial optimisation problems (COPs). These are usually formulated as a mathematical problem of minimising or maximising some cost function subject to a number of constraints. Usually, such problems are NP hard, and thus, whilst it is possible to find exact solutions to specific problems, in general only approximate solutions can be found. There are many algorithms that have been proposed for finding approximate solutions to COPs, ranging from special purpose heuristics to general search meta-heuristics such as simulated annealing and tabu search. General meta-heuristic algorithms like simulated annealing have been applied to a wide range of problems. In most cases, the designer must choose an appropriate data structure and a set of local operators that define a search neighbourhood. The variability in representation techniques, and suitable neighbourhood transition operators, has meant that it is usually necessary to develop new code for each problem. Toolkits like the one developed by Ingber's Adaptive Simulated Annealing (Ingber 1993, 1996) have been applied to assist rapid prototyping of simulated annealing codes, however, these still require the development of new programs for each type of problem. There have been very few attempts to develop a general meta-heuristic solver, with the notable exception being Connolly's General Purpose Simulated Annealing (Connolly 1992). In this research, a general meta-heuristic based system is presented that is suitable for a wide range of COPs. The main goal of this work is to build an environment in which it is possible to specify a range of COPs using an algebraic formulation, and to produce a tailored solver automatically. This removes the need for the development of specific software, allowing very rapid prototyping. Similar techniques have been available for linear programming based solvers for some years in the form of the GAMS (General Algebraic Modelling System) (Brooke, Kendrick, Meeraus and Raman 1997) and AMPL (Fourer, Gay and Kernighan 1993) interfaces. The new system is based on a novel linked list data structure rather than the more conventional vector notation due to the natural mapping between COPS and lists. In addition, the modelling system is found to be very suitable for processing by meta-heuristic search algorithms as it allows the direct application of common local search operators. A general solver is built that is based on the linked list modelling system. This system is capable of using meta-heuristic search engines such as greedy search, tabu search and simulated annealing. A number of implementation issues such as generating initial solutions, choosing and invoking appropriate local search transition operators and producing suitable incremental cost expressions, are considered. As such, the system can been seen as a good test-bench for model prototypers and those who wish to test various meta-heuristic implementations in a standard way. However, it is not meant as a replacement or substitute for efficient special purpose search algorithms. The solver shows good performance on a wide range of problems, frequently reaching the optimal and best-known solutions. Where this is not the case, solutions within a few percent deviation are produced. Performance is dependent on the chosen transition operators and the frequency with which each is applied. To a lesser extent, the performance of this implementation is influenced by runtime parameters of the meta-heuristic search engine.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Environmental and Applied Science
Science, Environment, Engineering and Technology
Full Text

Style APA, Harvard, Vancouver, ISO itp.

19

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.

Pełny tekst źródła

Streszczenie:

The initial question addressed in this thesis is how to take into account the multi-objective aspect of decision problems in inverse optimization. The most straightforward extension consists of finding a minimal adjustment of the objective functions coefficients such that a given feasible solution becomes efficient. However, there is not only a single question raised by inverse multi-objective optimization, because there is usually not a single efficient solution. The way we define inverse multi-objective

optimization 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

Style APA, Harvard, Vancouver, ISO itp.

20

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.

Pełny tekst źródła

Streszczenie:

Thesis (MScEng)--Stellenbosch University, 2012.
ENGLISH 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.

Style APA, Harvard, Vancouver, ISO itp.

21

Montero, Elisabeth. "Calibration strategies for bio-inspired population-based algorithms that solve combinatorial optimization problems". Nice, 2011. http://www.theses.fr/2011NICE4040.

Pełny tekst źródła

Streszczenie:

La sélection de valeurs adéquates pour les paramètres des algorithmes bio-inspirés est un processus crucial pour obtenir de bonnes performances. C’est un processus complexe étant donné que les valeurs des paramètres dépendent en général du problème que l’on cherche à résoudre. Il est de plus très coûteux en temps, et les paramètres ne sont pas complètement indépendants entre eux. La première contribution de cette thèse consiste en une étude comparative des caractéristiques et performances des différentes méthodes connues dans la littérature pour ajuster les paramètres, en analysant leurs avantages et leurs inconvénients. Le plus grand désavantage de ces méthodes est qu’elles sont très coûteuses en temps. Cependant, elles permettent d’obtenir de bonnes estimations pour les paramètres, en concentrant la recherche dans des régions statistiquement prometteuses. Nous présentons de plus une analyse du potentiel de ces techniques en tant qu’aide dans le processus de conception d’algorithmes évolutifs. Même si ces techniques aident à prendre des décisions quant à la conception de l’algorithme, elles ne sont pas capables d’éliminer de l’algorithme les éléments qui ne contribuent pas à son bon fonctionnement. La contribution principale de la thèse se situe sur la capacité de déterminer les valeurs des paramètres à la volée. Nous proposons deux nouvelles méthodes pour améliorer les performances des algorithmes évolutifs : Ac et Sac. Ac réalise un contrôle de la population dans lequel un opérateur reçoit une récompense en fonction de l’amélioration de performance issue de son application. Sac est quant à lui orienté à un contrôle individuel dans lequel le taux d’un opérateur qui correspond à un individu dépend de l’efficacité qu’a eue cet opérateur dans l’amélioration des générations précédentes. Ces deux méthodes peuvent être incorporées sans introduire un coût significatif, et sans changement important dans la conception d’origine de l’algorithme. Les décisions prises durant la recherche se basent ainsi sur les informations disponibles sur le comportement passé, à partir d’un processus permettant à l’algorithme d’effectuer des changements de valeurs de paramètres qu’il juge nécessaires. L’application de ces techniques a permis à l’algorithme d’éliminer des composants non nécessaires à sa recherche, grâce à une utilisation minimale de ceux-ci. Nous proposons également la stratégie (C,n)-strategy connue pour réaliser un contrôle dans l’algorithme immunitaire CLONAG, permettant de réduire en bonne partie le nombre de paramètres sur lesquels repose son exécution, ainsi que d’améliorer son comportement grâce à la modification à la volée du nombre de cellules sélectionnées pour le clonage, ainsi que le nombre de clones produits. Les techniques appliquées à l’algorithme évolutif, comme celle appliquée à l’algorithme immunitaire cherchent un équilibre entre l’exploration et l’exploitation de l’espace de recherche en utilisant les paramètres sélectionnés pour réaliser le contrôle. A partir du travail réalisé dans cette thèse, nous pouvons conclure que les techniques d’ajustement des paramètres permettent effectivement de trouver un ensemble de valeurs des paramètres qui offre une bonne performance de l’algorithme de recherche. Ces techniques demandent une analyse antérieure de la définition de l’espace de recherche pour les valeurs des paramètres, et requièrent de plus un temps d‘exécution considérable. Néanmoins, à partir des informations données par ces techniques d’ajustement, il est possible de prendre des décisions concernant la conception de l’algorithme que l’on veut ajuster. En ce qui concerne les techniques de contrôle de paramètres, nous pouvons conclure qu’elles permettent d’améliorer l’efficacité de l’algorithme et de réduire l’effort d’ajustement des paramètres car elles réduisent le nombre de paramètres à ajuster, qu’elles sont capables d’ajuster automatiquement les paramètres de l’algorithme sans modifier la conception d’origine de l’algorithme, et enfin, qu’elles ajoutent une quantité minime de paramètres additionnels à l’algorithme. Le développement de techniques capables de travailler avec n’importe quel type de paramètres demandant une définition de l’information d’entrée et qui soient capables de stopper à temps la recherche afin de ne pas perdre de ressources, reste un terme de recherche ouvert. Nous avons montré dans cette thèse qu’il est possible de réaliser un contrôle à la volée des paramètres des algorithmes basés sur des populations. Une perspective de recherche intéressante consiste à arriver à automatiser l’identification du rôle des composants de l’algorithme afin de pouvoir concevoir automatiquement les stratégies de contrôle
Selection 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

Style APA, Harvard, Vancouver, ISO itp.

22

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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

23

He, 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/.

Pełny tekst źródła

Streszczenie:

This thesis focuses on the construction of effective and efficient hybrid methods based on the integrations of Constraint Programming (CP), Integer Programming (IP) and local search (LS) to tackle two combinatorial optimisation problems from different application areas: the nurse rostering problems and the portfolio selection problems. The principle of designing hybrid methods in this thesis can be described as: for the combinatorial problems to be solved, the properties of the problems are investigated firstly and the problems are decomposed accordingly in certain ways; then the suitable solution techniques are integrated to solve the problem based on the properties of substructures/subproblems by taking the advantage of each technique. For the over-constrained nurse rostering problems with a large set of complex constraints, the problems are first decomposed by constraint. That is, only certain selected set of constraints is considered to generate feasible solutions at the first stage. Then the rest of constraints are tackled by a second stage local search method. Therefore, the hybrid methods based on this constraint decomposition can be represented by a two-stage framework “feasible solution + improvement”. Two integration methods are proposed and investigated under this framework. In the first integration method, namely a hybrid CP with Variable Neighourhood Search (VNS) approach, the generation of feasible initial solutions relies on the CP while the improvement of initial solutions is gained by a simple VNS in the second stage. In the second integration method, namely a constraint-directed local search, the local search is enhanced by using the information of constraints. The experimental results demonstrate the effectiveness of these hybrid approaches. Based on another decomposition method, Dantzig-Wolfe decomposition, in the third integration method, a CP based column generation, integrates the feasibility reasoning of CP with the relaxation and optimality reasoning of Linear Programming. The experimental results demonstrate the effectiveness of the methods as well as the knowledge of the quality of the solution. For the portfolio selection problems, two integration methods, which integrate Branch-and-Bound algorithm with heuristic search, are proposed and investigated. In layered Branch-and-Bound algorithm, the problem is decomposed into the subsets of variables which are considered at certain layers in the search tree according to their different features. Node selection heuristics, and branching rules, etc. are tailored to the individual layers, which speed up the search to the optimal solution in a given time limit. In local search branching Branch-and-Bound algorithm, the idea of local search is applied as the branching rule of Branch-and-Bound. The local search branching is applied to generate a sequence of subproblems. The procedure for solving these subproblems is accelerated by means of the solution information reusing. This close integration between local search and Branch-and-Bound improves the efficiency of the Branch-and-Bound algorithm according to the experimental results. The hybrid approaches benefit from each component which is selected according to the properties of the decomposed problems. The effectiveness and efficiency of all the hybrid approaches to the two application problems developed in this thesis are demonstrated. The idea of designing appropriate components in hybrid approach concerning properties of subproblems is a promising methodology with extensive potential applications in other real-world combinatorial optimisation problems.

Style APA, Harvard, Vancouver, ISO itp.

24

Canzar, 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.

Pełny tekst źródła

Streszczenie:

This thesis is devoted to two $\mathcal{NP}$-complete combinatorial optimization problems arising in computational biology, the well-studied \emph{multiple sequence alignment} problem and the new formulated \emph{interval constraint coloring} problem. It shows that advanced mathematical programming techniques are capable of solving large scale real-world instances from biology to optimality. Furthermore, it reveals alternative methods that provide approximate solutions. In the first part of the thesis, we present a \emph{Lagrangian relaxation} approach for the multiple sequence alignment (MSA) problem. The multiple alignment is one common mathematical abstraction of the comparison of multiple biological sequences, like DNA, RNA, or protein sequences. If the weight of a multiple alignment is measured by the sum of the projected pairwise weights of all pairs of sequences in the alignment, then finding a multiple alignment of maximum weight is $\mathcal{NP}$-complete if the number of sequences is not fixed. The majority of the available tools for aligning multiple sequences implement heuristic algorithms; no current exact method is able to solve moderately large instances or instances involving sequences exhibiting a lower degree of similarity. We present a branch-and-bound (B\&B) algorithm for the MSA problem.\ignore{the multiple sequence alignment problem.} We approximate the optimal integer solution in the nodes of the B\&B tree by a Lagrangian relaxation of an ILP formulation for MSA relative to an exponential large class of inequalities, that ensure that all pairwise alignments can be incorporated to a multiple alignment. By lifting these constraints prior to dualization the Lagrangian subproblem becomes an \emph{extended pairwise alignment} (EPA) problem: Compute the longest path in an acyclic graph, that is penalized a charge for entering ``obstacles''. We describe an efficient algorithm that solves the EPA problem repetitively to determine near-optimal \emph{Lagrangian multipliers} via subgradient optimization. The reformulation of the dualized constraints with respect to additionally introduced variables improves the convergence rate dramatically. We account for the exponential number of dualized constraints by starting with an empty \emph{constraint pool} in the first iteration to which we add cuts in each iteration, that are most violated by the convex combination of a small number of preceding Lagrangian solutions (including the current solution). In this \emph{relax-and-cut} scheme, only inequalities from the constraint pool are dualized. The interval constraint coloring problem appears in the interpretation of experimental data in biochemistry. Monitoring hydrogen-deuterium exchange rates via mass spectroscopy is a method used to obtain information about protein tertiary structure. The output of these experiments provides aggregate data about the exchange rate of residues in overlapping fragments of the protein backbone. These fragments must be re-assembled in order to obtain a global picture of the protein structure. The interval constraint coloring problem is the mathematical abstraction of this re-assembly process. The objective of the interval constraint coloring problem is to assign a color (exchange rate) to a set of integers (protein residues) such that a set of constraints is satisfied. Each constraint is made up of a closed interval (protein fragment) and requirements on the number of elements in the interval that belong to each color class (exchange rates observed in the experiments). We introduce a polyhedral description of the interval constraint coloring problem, which serves as a basis to attack the problem by integer linear programming (ILP) methods and tools, which perform well in practice. Since the goal is to provide biochemists with all possible candidate solutions, we combine related solutions to equivalence classes in an improved ILP formulation in order to reduce the running time of our enumeration algorithm. Moreover, we establish the polynomial-time solvability of the two-color case by the integrality of the linear programming relaxation polytope $\mathcal{P}$, and also present a combinatorial polynomial-time algorithm for this case. We apply this algorithm as a subroutine to approximate solutions to instances with arbitrary but fixed number of colors and achieve an order of magnitude improvement in running time over the (exact) ILP approach. We show that the problem is $\mathcal{NP}$-complete for arbitrary number of colors, and we provide algorithms that, given an instance with $\mathcal{P}\neq\emptyset$, find a coloring that satisfies all the coloring requirements within $\pm 1$ of the prescribed value. In light of our $\mathcal{NP}$-completeness result, this is essentially the best one can hope for. Our approach is based on polyhedral theory and randomized rounding techniques. In practice, data emanating from the experiments are noisy, which normally causes the instance to be infeasible, and, in some cases, even forces $\mathcal{P}$ to be empty. To deal with this problem, the objective of the ILP is to minimize the total sum of absolute deviations from the coloring requirements over all intervals. The combinatorial approach for the two-color case optimizes the same objective function. Furthermore, we use this combinatorial method to compute, in a Lagrangian way, a bound on the minimum total error, which is exploited in a branch-and-bound manner to determine all optimal colorings. Alternatively, we study a variant of the problem in which we want to maximize the number of requirements that are satisfied. We prove that this variant is $\mathcal{APX}$-hard even in the two-color case and thus does not admit a polynomial time approximation scheme (PTAS) unless $\mathcal{P}=\mathcal{NP}$. Therefore, we slightly (by a factor of $(1+\epsilon)$) relax the condition on when a requirement is satisfied and propose a \emph{quasi-polynomial time approximation scheme} (QPTAS) which finds a coloring that ``satisfies'' the requirements of as many intervals as possible.

Style APA, Harvard, Vancouver, ISO itp.

25

Violin, 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.

Pełny tekst źródła

Streszczenie:

There are many real cases where a company needs to determine the price of its products so as to maximise its revenue or profit.

To 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

Style APA, Harvard, Vancouver, ISO itp.

26

Sghir, Inès. "A Multi-Agent based Optimization Method for Combinatorial Optimization Problems". Thesis, Angers, 2016. http://www.theses.fr/2016ANGE0009/document.

Pełny tekst źródła

Streszczenie:

Nous élaborons une approche multi-agents pour la résolution des problèmes d’optimisation combinatoire nommée MAOM-COP. Elle combine des métaheuristiques, les systèmes multi-agents et l’apprentissage par renforcement. Les heuristiques manquent d’une vue d’ensemble sur l’évolution de la recherche. Notre objectif consiste à utiliser les systèmes multi-agents pour créer des méthodes de recherche coopératives. Ces méthodes explorent plusieurs métaheuristiques. MAOM-COP est composée de plusieurs agents qui sont l’agent décideur, les agents intensificateurs et les agents diversificateurs (agents croisement et agent perturbation). A l’aide de l’apprentissage, l’agent décideur décide dynamiquement quel agent à activer entre les agents intensificateurs et les agents croisement. Si les agents intensificateurs sont activés, ils appliquent des algorithmes de recherche locale. Durant leurs recherches, ils peuvent s’échanger des informations, comme ils peuvent déclencher l’agent perturbation. Si les agents croisement sont activés, ils exécutent des opérateurs de recombinaison. Nous avons appliqué MAOM-COP sur les problèmes suivants : l’affectation quadratique, la coloration des graphes, la détermination des gagnants et le sac à dos multidimensionnel. MAOM-COP possède des performances compétitives par rapport aux algorithmes de l’état de l’art
We 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

Style APA, Harvard, Vancouver, ISO itp.

27

Almeida, Coco Amadeu. "Robust covering problems : formulations, algorithms and an application". Thesis, Troyes, 2017. http://www.theses.fr/2017TROY0026/document.

Pełny tekst źródła

Streszczenie:

Deux problèmes robustes d'optimisation NP-difficiles sont étudiés dans cette thèse: le problème min-max regret de couverture pondérée (min-max regret WSCP) et le problème min-max regret de couverture et localisation maximale (min-max regret MCLP). Les données incertaines dans ces problèmes sont modélisées par des intervalles et seules les valeurs minimales et maximales pour chaque intervalle sont connues. Le min-max regret WSCP a été investigué notamment dans le cadre théorique, alors que le min-max regret MCLP a des applications en logistique des catastrophes étudiées dans cette thèse. Deux autres critères d'optimisation robuste ont été dérivés pour le MCLP: le max-max MCLP et le min-max MCLP. En matière de méthodes, formulations mathématiques, algorithmes exacts et heuristiques ont été développés et appliqués aux deux problèmes. Des expérimentations computationnelles ont montré que les algorithmes exacts ont permis de résoudre efficacement 14 des 75 instances générées par le min-max regret WSCP et toutes les instances réalistes pour le min-max regret MCLP. Pour les cas simulés qui n'ont pas été résolus de manière optimale dans les deux problèmes, les heuristiques développées dans cette thèse ont trouvé des solutions aussi bien ou mieux que le meilleur algorithme exact dans presque tous les cas. En ce qui concerne l'application en logistique des catastrophes, les modèles robustes ont trouvé des solutions similaires pour les scénarios réalistes des tremblements de terre qui a eu lieu à Katmandu au Népal en 2015. Cela indique que nous avons une solution robuste
Two 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

Style APA, Harvard, Vancouver, ISO itp.

28

Maziere, Florian. "Modèles de parallélisme pour les métaheuristiques multi-objectifs". Thesis, Reims, 2019. http://www.theses.fr/2019REIMS002/document.

Pełny tekst źródła

Streszczenie:

L’objectif de ce projet de trois ans est de proposer des avancées conceptuelles et technologiques dans la résolution de problèmes d’ordonnancement du personnel. L’atteinte de cet objectif passe par la proposition de nouveaux algorithmes basés sur les métaheuristiques et leur implémentation sur les architectures de calcul haute performance. Ce projet s’inscrit en complémentarité du projet HORUS qui bénéficie d’une subvention ANR et qui réunit les expertises scientifiques de deux laboratoires universitaires spécialisés en optimisation et en calcul parallèle : l’équipe SysCom du laboratoire CReSTIC de l’URCA et l’équipe CaRO du laboratoire PRiSM de l’UVSQ. Les avancées technologiques proposées s’appuient également sur les moyens de calcul haute performance offerts par le Centre de Calcul Régional Champagne-Ardenne
.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

Style APA, Harvard, Vancouver, ISO itp.

29

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.

Pełny tekst źródła

Streszczenie:

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyaux
The 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

Style APA, Harvard, Vancouver, ISO itp.

30

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.

Pełny tekst źródła

Streszczenie:

Combinatorial optimisation problems (COPs) have been at the origin of the design of many optimal and heuristic solution frameworks such as branch-and-bound algorithms, branch-and-cut algorithms, classical local search methods, metaheuristics, and hyperheuristics. This thesis proposes a refined generic and parametrised infeasible local search (GPILS) algorithm for solving COPs and customises it to solve the traveling salesman problem (TSP), for illustration purposes. In addition, a rule-based heuristic is proposed to initialise infeasible local search, referred to as the parameterised infeasible heuristic (PIH), which allows the analyst to have some control over the features of the infeasible solution he/she might want to start the infeasible search with. A recursive infeasible neighbourhood search (RINS) as well as a generic patching procedure to search the infeasible space are also proposed. These procedures are designed in a generic manner, so they can be adapted to any choice of parameters of the GPILS, where the set of parameters, in fact for simplicity, refers to set of parameters, components, criteria and rules. Furthermore, a hyperheuristic framework is proposed for optimizing the parameters of GPILS referred to as HH-GPILS. Experiments have been run for both sequential (i.e. simulated annealing, variable neighbourhood search, and tabu search) and parallel hyperheuristics (i.e., genetic algorithms / GAs) to empirically assess the performance of the proposed HH-GPILS in solving TSP using instances from the TSPLIB. Empirical results suggest that HH-GPILS delivers an outstanding performance. Finally, an offline learning mechanism is proposed as a seeding technique to improve the performance and speed of the proposed parallel HH-GPILS. The proposed offline learning mechanism makes use of a knowledge-base to keep track of the best performing chromosomes and their scores. Empirical results suggest that this learning mechanism is a promising technique to initialise the GA's population.

Style APA, Harvard, Vancouver, ISO itp.

31

Salazar-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.

Pełny tekst źródła

Streszczenie:

La construction de modèles qui protègent contre les incertitudes dans les données, telles que la variabilité de l'information et l'imprécision est une des principales préoccupations en optimisation sous incertitude. L'incertitude peut affecter différentes domaines, comme le transport, les télécommunications, la finance, etc. ainsi que les différentes parts d'un problème d'optimisation, comme les coefficients de la fonction objectif et /ou les contraintes. De plus, l'ensemble des données incertaines peut être modélisé de différentes façons, comme sous ensembles compactes et convexes de l´espace réel de dimension n, polytopes, produits Cartésiens des intervalles, ellipsoïdes, etc.

Une 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

Style APA, Harvard, Vancouver, ISO itp.

32

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.

Pełny tekst źródła

Streszczenie:

Stochastic combinatorial optimization problems are combinatorial optimization problems where part of the problem data are probabilistic. The focus of this thesis is on stochastic routing problems, a class of stochastic combinatorial optimization problems that arise in distribution management. Stochastic routing problems involve finding the best solution to distribute goods across a logistic network. In the problems we tackle, we consider a setting in which the cost of a solution is described by a random variable; the goal is to find the solution that minimizes the expected cost. Solving such stochastic routing problems is a challenging task because of two main factors. First, the number of possible solutions grows exponentially with the instance size. Second, computing the expected cost of a solution is computationally very expensive.

To 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

Style APA, Harvard, Vancouver, ISO itp.

33

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.

Pełny tekst źródła

Streszczenie:

De nombreux problèmes d'optimisation combinatoire considèrent plusieurs objectifs, souvent conflictuels. Cette thèse s'intéresse à l'utilisation de méthodes de recherche locale, de structures de données et de recherche Monte-Carlo pour la recherche de l'ensemble des solutions efficaces de tels problèmes, représentant l'ensemble des meilleurs compromis pouvant être réalisés en considération de tous les objectifs.Nous proposons une nouvelle méthode d'approximation appelée 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combinant les concepts de recherche locale Pareto (PLS) et de décomposition. La PLS est une descente de recherche locale adaptée au multi-objectif, et la décomposition consiste en la subdivision du problème multi-objectif en plusieurs problèmes mono-objectif. Deux méthodes d'optimisation mono-objectif sont considérées: la recherche locale itérée et la recherche Monte-Carlo imbriquée. Deux modules principaux sont intégrés à 2PIPLS/D. Le premier généralise et améliore une méthode existante et génère un ensemble initial de solutions. Le second réduit efficacement l'espace de recherche et permet d'accélérer la PLS sans négliger la qualité de l'approximation générée. Nous introduisons aussi deux nouvelles structures de données gérant dynamiquement un ensemble de solutions incomparables, la première est spécialisée pour le cas bi-objectif et la seconde pour le cas général.2PIPLS/D est appliquée au Problème du Voyageur de Commerce bi-objectif et tri-objectif et surpasse ses concurrents sur les instances testées. Ensuite, 2PIPLS/D est appliquée à un nouveau problème avec cinq objectifs en lien avec la récente réforme territoriale d'agrandissement des régions françaises
Many 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

Style APA, Harvard, Vancouver, ISO itp.

34

Pruvost, Geoffrey. "Contributions à l’optimisation multi-objectif à base de décomposition". Thesis, Université de Lille (2018-2021), 2021. http://www.theses.fr/2021LILUB026.

Pełny tekst źródła

Streszczenie:

Dans cette thèse, nous nous intéressons à l'optimisation combinatoire multi-objectif, et en particulier aux algorithmes évolutionnaires à base de décomposition. Ce type d'approches consiste à décomposer le problème multi-objectif original en plusieurs sous-problèmes mono-objectif, qui sont alors résolus de façon coopérative. Dans ce cadre, nous considérons la conception et l'analyse de nouveaux composants algorithmiques contribuant à la mise en place des fondations d'un framework d'optimisation à base de décomposition pour les problèmes combinatoires multi-objectif dits "boîte-noire", pour lesquels la forme analytique des fonctions objectif n'est pas connue de l'algorithme de résolution. Tout d'abord, nous étudions les éléments clés pour une meilleure répartition des efforts de calculs tout au long du processus d'optimisation. Pour cela, nous étudions l'impact conjoint de la taille de la population et du nombre de solutions générées par itération, tout en proposant différentes stratégies de sélection du ou des sous-problèmes à optimiser à chaque étape. Nous étudions ensuite différents mécanismes permettant de s'échapper des optima locaux. Ceux-ci s'inspirent de techniques issues de l'optimisation mono-objectif, et permettent d'améliorer considérablement le profil de convergence des approches considérées. Nous nous plaçons pour finir dans un contexte d'optimisation coûteuse, où l'évaluation de chaque solution s'avère particulièrement gourmande en temps de calcul, ce qui limite considérablement le budget alloué à l'optimisation. Pour cela, nous étudions de nouveaux composants s'appuyant sur des méta-modèles combinatoires, et nous considérons leur intégration au sein d'approches évolutionnaires multi-objectif basée sur la décomposition
In 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

Style APA, Harvard, Vancouver, ISO itp.

35

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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

36

Alaya, 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.

Pełny tekst źródła

Streszczenie:

Dans cette thèse, nous nous intéressons à l'étude des capacités de la méta heuristique d'optimisation par colonie de fourmis (Ant Colony Optimization - ACO) pour résoudre des problèmes d'optimisation combinatoire multi-objectif. Dans ce cadre, nous avons proposé une taxonomie des algorithmes ACO proposés dans la littérature pour résoudre des problèmes de ce type. Nous avons mené, par la suite, une étude expérimentale de différentes stratégies phéromonales pour le cas du problème du sac à dos multidimensionnel mono-objectif. Enfin,nous avons proposé un algorithme ACO générique pour résoudre des problèmes d'optimisation multi-objectif. Cet algorithme est paramétré par le nombre de colonies de fourmis et le nombre de structures de phéromone considérées. Il permet de tester et de comparer, dans un même cadre,plusieurs approches. Nous avons proposé six variantes de cet algorithme dont trois présentent de nouvelles approches et trois autres reprennent des approches existantes. Nous avons appliqué et comparé ces variantes au problème du sac à dos multidimensionnel multi-objectif

Style APA, Harvard, Vancouver, ISO itp.

37

Minot, Maël. "Investigating decomposition methods for the maximum common subgraph and sum colouring problems". Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEI120/document.

Pełny tekst źródła

Streszczenie:

Notre objectif est d’évaluer et de rendre opérationnelle la décomposition de problèmes d’optimisation sous contraintes. Nous nous sommes intéressés à deux problèmes en particulier : le problème de la recherche d’un plus grand sous-graphe commun (MCIS), et le problème de somme coloration minimale (MSCP). Il s’agit de problèmes NP-difficiles pour lesquels les approches de résolution complètes passent difficilement à l’échelle, et nous proposons de les améliorer à cet égard en décomposant ces problèmes en sous-problèmes indépendants. Les décompositions que nous proposons s’appuient sur la structure du problème initial pour créer des sous-problèmes de tailles équilibrées. Pour le MCIS, nous introduisons une décomposition basée sur la structure du graphe de compatibilité, et nous montrons que cette décomposition permet d’obtenir des sous-problèmes plus équilibrés que la méthode EPS classiquement utilisée pour paralléliser la résolution de problèmes en programmation par contraintes. Pour le MSCP, nous introduisons une nouvelle décomposition arborescente de hauteur bornée, et nous montrons comment tirer partie de la complémentarité de la programmation par contraintes et de la programmation linéaire en nombres entiers pour obtenir et résoudre les sous-problèmes indépendants qui en découlent. Nous proposons également une approche portfolio qui utilise des techniques d’apprentissage automatique pour choisir dynamiquement l’approche la plus performante en fonction du problème à résoudre
The 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

Style APA, Harvard, Vancouver, ISO itp.

38

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.

Pełny tekst źródła

Streszczenie:

La thèse porte sur l’étude de problèmes réels de transport et de distribution par voie routière. Il s’agit plus précisément de deux problèmes distincts d’optimisation des tournées de véhicules ; la distribution de produits pétroliers et le transfert des conteneurs. La résolution du premier problème, identifié comme le problème de tournées de véhicules avec compartiments multiples et fenêtres de temps ou MCVRP-TW (Multi-Compartment Vehicle Routing Problem with Time Windows), est basée sur une méthode de recherche tabou. Une adaptation de la méthode de résolution a été appliquée à deux autres problématiques annexes, la première intègre des contraintes supplémentaires liées à l’opération de chargement des produits pétroliers dans les compartiments, et la seconde inclut le concept d’ajustement des quantités demandées. Par ailleurs, dans l’optique d’une transition énergétique, nous nous sommes intéressés au problème de transfert des conteneurs par camions électriques dans la zone industrialo-portuaire du Havre. L’optimisation se situe à deux niveaux, un niveau stratégique pour le dimensionnement de l’infrastructure électrique et un niveau opérationnel pour la construction des tournées de véhicules. Seul le niveau stratégique a été abordé dans le cadre d’un projet de recherche grâce à un couplage de l’optimisation et la simulation
The 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

Style APA, Harvard, Vancouver, ISO itp.

39

Siala, Mohamed. "Search, propagation, and learning in sequencing and scheduling problems". Thesis, Toulouse, INSA, 2015. http://www.theses.fr/2015ISAT0008/document.

Pełny tekst źródła

Streszczenie:

Les problèmes de séquencement et d'ordonnancement forment une famille de problèmes combinatoires qui implique la programmation dans le temps d'un ensemble d'opérations soumises à des contraintes de capacités et de ressources. Nous contribuons dans cette thèse à la résolution de ces problèmes dans un contexte de satisfaction de contraintes et d'optimisation combinatoire. Nos propositions concernent trois aspects différents: comment choisir le prochain nœud à explorer (recherche)? comment réduire efficacement l'espace de recherche (propagation)? et que peut-on apprendre des échecs rencontrés lors de la recherche (apprentissage)? Nos contributions commencent par une étude approfondie des heuristiques de branchement pour le problème de séquencement de chaîne d'assemblage de voitures. Cette évaluation montre d'abord les paramètres clés de ce qui constitue une bonne heuristique pour ce problème. De plus, elle montre que la stratégie de branchement est aussi importante que la méthode de propagation. Deuxièmement, nous étudions les mécanismes de propagation pour une classe de contraintes de séquencement à travers la conception de plusieurs algorithmes de filtrage. En particulier, nous proposons un algorithme de filtrage complet pour un type de contrainte de séquence avec une complexité temporelle optimale dans le pire cas. Troisièmement, nous investiguons l'impact de l'apprentissage de clauses pour résoudre le problème de séquencement de véhicules à travers une nouvelle stratégie d'explication réduite pour le nouveau filtrage. L'évaluation expérimentale montre l'importance de l'apprentissage de clauses pour ce problème. Ensuite, nous proposons une alternative pour la génération retardée de variables booléennes pour encoder les domaines. Finalement, nous revisitons les algorithmes d'analyse de conflits pour résoudre les problèmes d'ordonnancement disjonctifs. En particulier, nous introduisons une nouvelle procédure d'analyse de conflits dédiée pour cette famille de problèmes. La nouvelle méthode diffère des algorithmes traditionnels par l'apprentissage de clauses portant uniquement sur les variables booléennes de disjonctions. Enfin, nous présentons les résultats d'une large étude expérimentale qui démontre l'impact de ces nouveaux mécanismes d'apprentissage. En particulier, la nouvelle méthode d'analyse de conflits a permis de découvrir de nouvelle bornes inférieures pour des instances largement étudiées de la littérature
Sequencing 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

Style APA, Harvard, Vancouver, ISO itp.

40

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.

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

41

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.

Pełny tekst źródła

Streszczenie:

L'optimisation multi-objectif concerne la résolution de problèmes pour lesquels plusieurs objectifs (ou critères) contradictoires sont pris en compte. Contrairement aux problèmes d'optimisation ayant un seul objectif, un problème multi-objectif ne possède pas une valeur optimale unique mais plutôt un ensemble de points appelés "ensemble non dominé". Les bornes inférieures et supérieures d'un problème multi-objectif peuvent être également décrites par des ensembles. Dans la pratique, les variables utilisées en optimisation multiobjectif représentent souvent des objets non fractionnables et on parle alors de problèmes multi-objectif en nombres entiers. Afin d'obtenir de meilleures bornes qui peuvent être utilisées dans la conception de méthodes exactes, certains problèmes sont formulés avec un nombre exponentiel de variables de décision et ces problèmes sont résolus par la méthode de génération de colonnes. Les travaux de cette thèse visent à contribuer à l'étude de l'utilisation de la génération de colonnes en programmation linéaires en nombres entiers multi-objectif. Pour cela nous étudions un problème de tournées de véhicules bi-objectif qui peut être considéré comme une généralisation de plusieurs autres problèmes de tournées de véhicules. Nous proposons des formulations mathématiques pour ce problème et des techniques pour accélérer le calcul des bornes inférieures par génération de colonnes. Les sous-problèmes qui doivent être résolus pour le calcul des bornes inférieures ont une structure similaire. Nous exploitons cette caractéristique pour traiter simultanément certains sous-problèmes plutôt qu'indépendamment.

Style APA, Harvard, Vancouver, ISO itp.

42

Kaddani, Sami. "Partial preference models in discrete multi-objective optimization". Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED012/document.

Pełny tekst źródła

Streszczenie:

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

Style APA, Harvard, Vancouver, ISO itp.

43

Pereira, Vargas Liguori Pedro. "Polyhedral approaches for some network design problems". Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED074.

Pełny tekst źródła

Streszczenie:

Cette thèse étudie les aspects polyhédraux de certains problèmes de conception de réseau, en se concentrant principalement sur les aspects liés à la connectivité dessous-structures nécessaires pour créer des applications réseau fiables. Le cœur de nombreuses applications différentes de conception de réseau réside dans le fait qu’il est nécessaire de fournir un sous-réseau connexe (pouvant être compris comme un ensemble de sommets ou d’arêtes induisant un sous-graphe connecté) pouvant présenter d’autres propriétés souhaitables, comme atteindre un certain niveau de capacité de survie ou de robustesse, des contraintes de capacité ou d’autres types de contraintes budgétaires, en fonction du contexte. La plupart des études menées et des algorithmes développés tentent de tirer parti de ces aspects particuliers qui différencient une application de l’autre, sans se préoccuper des aspects qui réunissent ces questions. Par conséquent, ce travail tente de développer une approche unifiée capable d’explorer les aspects les plus pertinents des problèmes de conception de réseau, en espérant que cela conduirait à une compréhension réfléchie de problèmes plus spécifiques, en apportant une contribution précieuse à la recherche
This 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

Style APA, Harvard, Vancouver, ISO itp.

44

Sun, Wen. "Heuristic Algorithms for Graph Coloring Problems". Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0027/document.

Pełny tekst źródła

Streszczenie:

Cette thèse concerne quatre problèmes de coloration de graphes NPdifficiles, à savoir le problème de coloration (GCP), le problème de coloration équitable (ECP), le problème de coloration des sommets pondérés et le problème de sous-graphe critique (k-VCS). Ces problèmes sont largement étudiés dans la littérature, non seulement pour leur difficulté théorique, mais aussi pour leurs applications réelles dans de nombreux domaines. Étant donné qu'ils appartiennent à la classe de problèmes NP-difficiles, il est difficile de les résoudre dans le cas général de manière exacte. Pour cette raison, cette thèse est consacrée au développement d'approches heuristiques pour aborder ces problèmes complexes. Plus précisément, nous développons un algorithme mémétique de réduction (RMA) pour la coloration des graphes, un algorithme de recherche réalisable et irréalisable (FISA) pour la coloration équitable et un réalisable et irréalisable (AFISA) pour le problème de coloration des sommets pondérés et un algorithme de suppression basé sur le retour en arrière (IBR) pour le problème k-VCS. Tous les algorithmes ont été expérimentalement évalués et comparés aux méthodes de l'état de l'art
This 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

Style APA, Harvard, Vancouver, ISO itp.

45

Lokhov, Andrey Y. "Dynamic cavity method and problems on graphs". Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112331/document.

Pełny tekst źródła

Streszczenie:

Un grand nombre des problèmes d'optimisation, ainsi que des problèmes inverses, combinatoires ou hors équilibre qui apparaissent en physique statistique des systèmes complexes, peuvent être représentés comme un ensemble des variables en interaction sur un certain réseau. Bien que la recette universelle pour traiter ces problèmes n'existe pas, la compréhension qualitative et quantitative des problèmes complexes sur des graphes a fait des grands progrès au cours de ces dernières années. Un rôle particulier a été joué par des concepts empruntés de la physique des verres de spin et la théorie des champs, qui ont eu beaucoup de succès en ce qui concerne la description des propriétés statistiques des systèmes complexes et le développement d'algorithmes efficaces pour des problèmes concrets.En première partie de cette thèse, nous étudions des problèmes de diffusion sur des réseaux, avec la dynamique hors équilibre. En utilisant la méthode de cavité sur des trajectoires dans le temps, nous montrons comment dériver des équations dynamiques dites "message-passing'' pour une large classe de modèles avec une dynamique unidirectionnelle -- la propriété clef qui permet de résoudre le problème. Ces équations sont asymptotiquement exactes pour des graphes localement en arbre et en général représentent une bonne approximation pour des réseaux réels. Nous illustrons cette approche avec une application des équations dynamiques pour résoudre le problème inverse d'inférence de la source d'épidémie dans le modèle "susceptible-infected-recovered''.Dans la seconde partie du manuscrit, nous considérons un problème d'optimisation d'appariement planaire optimal sur une ligne. En exploitant des techniques de la théorie de champs et des arguments combinatoires, nous caractérisons une transition de phase topologique qui se produit dans un modèle désordonné simple, le modèle de Bernoulli. Visant une application à la physique des structures secondaires de l'ARN, nous discutons la relation entre la transition d'appariement parfait-imparfait et la transition de basse température connue entre les états fondu et vitreux de biopolymère; nous proposons également des modèles généralisés qui suggèrent une correspondance exacte entre la matrice des contacts et la séquence des nucléotides, permettant ainsi de donner un sens à la notion des alphabets effectifs non-entiers
A 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

Style APA, Harvard, Vancouver, ISO itp.

46

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.

Pełny tekst źródła

Streszczenie:

Nous nous intéressons dans cette thèse aux possibilités d'hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l'objectif de résoudre des problèmes NPdifficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l'ordre des valeurs sur lesquelles brancher. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général est de tenir compte par une technique d'apprentissage de l'impact qu'ont eu les décisions de branchement dans les parties déjà explorées de l'arbre. Nous évaluons l'efficacité de la méthode proposée sur deux problèmes classiques : un problème d'optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, qui détermine par un algorithme de programmation dynamique la sous-séquence optimale d'un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d'être visités. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l'efficacité de l'opérateur que nous proposons en appliquant cette recherche à voisinage large sur deux problèmes, respectivement le Problème de l'Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d'Optimisation par Colonies de Fourmis. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu'il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l'aide de tests expérimentaux

Style APA, Harvard, Vancouver, ISO itp.

47

Mehdi, 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.

Pełny tekst źródła

Streszczenie:

La résolution efficace de problèmes d'optimisation a permutation de grande taille nécessite le développement de méthodes hybrides complexes combinant différentes classes d'algorithmes d'optimisation. L'hybridation des metaheuristiques avec les méthodes exactes arborescentes, tel que l'algorithme du branch-and-bound (B&B), engendre une nouvelle classe d'algorithmes plus efficace que ces deux classes de méthodes utilisées séparément. Le défi principal dans le développement de telles méthodes consiste a trouver des liens ou connections entre les stratégies de recherches divergentes utilisées dans les deux classes de méthodes. Les Algorithmes Genetiques (AGs) sont des metaheuristiques, a base de population, tr'es populaires bas'es sur des op'erateurs stochastiques inspirés de la théorie de l'évolution. Contrairement aux AGs et aux m'etaheuristiques généralement, les algorithmes de B&B sont basées sur l'énumération implicite de l'espace de recherche représente par le moyen d'un arbre, dit arbre de recherche. Notre approche d'hybridation consiste a définir un codage commun des solutions et de l'espace de recherche ainsi que des opérateurs de recherche ad'equats afin de permettre un couplage efficace de bas niveau entre les deux classes de méthodes AGs et B&B. La représentation de l'espace de recherche par le moyen d'arbres est traditionnellement utilis'ee dans les algorithmes de B&B. Dans cette thèse, cette représentation a été adaptée aux metaheuristiques. L'encodage des permutations au moyen de nombres naturels faisant référence a l'ordre d'énumération lexicographique des permutations dans l'arbre du B&B, est proposé comme une nouvelle manière de représenter l'espace de recherche des problèmes 'a permutations dans les metaheuristiques. Cette méthode de codage est basée sur les propriétés mathématiques des permutations, 'a savoir les codes de Lehmer et les tables d'inversions ainsi que les système d'énumération factoriels. Des fonctions de transformation permettant le passage entre les deux représentations (permutations et nombres) ainsi que des opérateurs de recherche adaptes au codage, sont définis pour les problèmes 'a permutations généralisés. Cette représentation, désormais commune aux metaheuristiques et aux algorithmes de B&B, nous a permis de concevoir des stratégies d'hybridation et de collaboration efficaces entre les AGs et le B&B. En effet, deux approches d'hybridation entre les AGs et les algorithmes de B&B (HGABB et COBBIGA) bas'es sur cette représentation commune ont été proposées dans cette thèse. Pour validation, une implémentation a été réalisée pour le problème d'affectation quadratique 'a trois dimension (Q3AP). Afin de résoudre de larges instances de ce problème, nous avons aussi propose une parallélisation pour les deux algorithme hybrides, basée sur des techniques de décomposition d'espace (décomposition par intervalle) utilisées auparavant pour la parallélisation des algorithmes de B&B. Du point de vue implémentation, afin de faciliter de futurs conceptions et implémentations de méthodes hybrides combinant metaheuristiques et méthodes exacte arborescentes, nous avons développe une plateforme d'hybridation intégrée au logiciel pour metaheuristiques, ParadisEO. La nouvelle plateforme a été utilisée pour réaliser des expérimentations intensives sur la grille de calcul Grid'5000.

Style APA, Harvard, Vancouver, ISO itp.

48

Sheppard, Nicholas Paul. "Self-Reduction for Combinatorial Optimisation". University of Sydney. Computer Science, 2001. http://hdl.handle.net/2123/797.

Pełny tekst źródła

Streszczenie:

This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.

Style APA, Harvard, Vancouver, ISO itp.

49

Belhoul, 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.

Pełny tekst źródła

Streszczenie:

Notre objectif dans cette thèse est de proposer des algorithmes efficaces pour résoudre des problèmes d’optimisation combinatoire difficiles. Dans un premier temps, nous établissons le principe de l’énumération ordonnée qui consiste à générer dans un ordre adéquat les solutions d’un problème relâché associé au problème principal jusqu’à l’obtention de la preuve d’optimalité d’une solution. Nous construisons une procédure générique dans le cadre général des problème d’optimisation combinatoire. Dans un second temps nous abordons les applications de notre algorithme sur des problèmes qui admettent le problème d’affectation comme relaxation. Le premier cas particulier que nous étudions est la recherche d’une solution de bon compromis pour le problème d’affectation multiobjectif. La seconde application se rapporte au problème du voyageur de commerce asymétrique qui présente la difficulté de comporter des contraintes qui interdisent les sous-tournées, en plus des contraintes du problème d’affectation
Our 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

Style APA, Harvard, Vancouver, ISO itp.

50

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.

Pełny tekst źródła

Streszczenie:

Le travail que nous développons dans le cadre de cette thèse s'articule autour des problèmes de recherche de structure de recouvrement de graphes sous contrainte sur le degré des sommets. Comme l'arbre de recouvrement couvre les sommets d'un graphe connexe avec un minimum de liens, il est généralement proposé comme solution à ce type de problèmes. Cependant, pour certaines applications telles que le routage dans les réseaux optiques, les solutions ne sont pas nécessairement des sous-graphes. Nous supposons dans cette thèse que la contrainte sur le degré est due à une capacité limitée instantanée des sommets et que la seule exigence sur le recouvrement est sa connexité. Dans ce cas, la solution peut être différente d'un arbre. Nous reformulons ces problèmes de recouvrement en nous appuyant sur une extension du concept d'arbre appelée hiérarchie de recouvrement. Notre objectif principal est de démontrer son intérêt vis-à-vis de l'arbre en termes de faisabilité et de coût du recouvrement. Nous considérons deux types de contraintes sur le degré : des bornes sur le degré des sommets ou une borne sur le nombre de sommets de branchement et cherchons dans les deux cas un recouvrement de coût minimum. Nous illustrons aussi l'applicabilité des hiérarchies en étudiant un problème prenant davantage en compte la réalité du routage optique. Pour ces différents problèmes NP-difficiles, nous montrons, tant sur le coût des solutions optimales que sur la garantie de performance des solutions approchées, l'intérêt des hiérarchies de recouvrement. Ce constat se voit conforté par des expérimentations sur des graphes aléatoires
The 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

Style APA, Harvard, Vancouver, ISO itp.

Rozprawy doktorskie na temat „Combinatorial optimisation problems”

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych