Item Type: 
Ph.D. Thesis 
Title: 
Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems 
Language: 
English 
Abstract: 
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 metacomponents, better known as metaheuristics. The first two are strongly problem dependent and require the exploitation of problemspecific 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 rankbased 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 nonparametric 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 Tcolouring 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 Tcolouring problem. In both cases, we design new algorithms, reimplement 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 oneexchange neighbourhood remains a very competitive approach and the use of a very large scale neighbourhood is not profitable; on the set Tcolouring problem, the best overall algorithm is an Adaptive Iterated Greedy also based on Tabu Search with oneexchange 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. 
Alternative Abstract: 
Alternative Abstract  Language 

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 metacomponents, better known as metaheuristics. The first two are strongly problem dependent and require the exploitation of problemspecific 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 rankbased 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 nonparametric 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 Tcolouring 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 Tcolouring problem. In both cases, we design new algorithms, reimplement 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 oneexchange neighbourhood remains a very competitive approach and the use of a very large scale neighbourhood is not profitable; on the set Tcolouring problem, the best overall algorithm is an Adaptive Iterated Greedy also based on Tabu Search with oneexchange 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.  English 

Place of Publication: 
Darmstadt 
Uncontrolled Keywords: 
Sequentieller Test 
Alternative keywords: 
Alternative keywords  Language 

Sequentieller Test  German  Generalized Graph Coloring, Set TColoring, Automated Timetabling, Frequency Assignment, Combinatorial Optimization  English 

Classification DDC: 
000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik 
Divisions: 
Fachbereich Informatik 
Date Deposited: 
17 Oct 2008 09:22 
Last Modified: 
07 Dec 2012 11:51 
Official URL: 
http://elib.tudarmstadt.de/diss/000595 
URN: 
urn:nbn:de:tudatuprints5950 
Referees: 
Bibel, Prof. Dr. Wolfgang and Stützle, PD Dr. hab Thomas 
Advisors: 
Stützle, PD Dr. hab Thomas 
Refereed: 
8 July 2005 
URI: 
http://tuprints.ulb.tudarmstadt.de/id/eprint/595 
Export: 
