KUET Institutional Repository

Heuristic Approaches for Maximin Distance and Packing Problems

Show simple item record

dc.contributor.advisor Locatelli, Prof. Marco
dc.contributor.author Jamali, Abdur Rakib Muhammad Jalal Uddin
dc.date.accessioned 2018-08-11T08:49:11Z
dc.date.available 2018-08-11T08:49:11Z
dc.date.copyright 2009
dc.date.issued 2009-02-18
dc.identifier.other ID 0000000
dc.identifier.uri http://hdl.handle.net/20.500.12228/321
dc.description This thesis is submitted to the Dipartimento di Informatica (Computer Science), Università Degli Studi di Torino, Italy in partial fulfillment of the requirements for the degree of Doctor of Philosophy, February 18, 2009. en_US
dc.description Cataloged from PDF Version of Thesis.
dc.description Includes bibliographical references (pages 150-168).
dc.description.abstract In this thesis we mainly deal with two problems - experimental design and packing problems. In the field of experimental design problems we consider maximin Latin Hypercube Designs (LHDs). In the field of packing problems we consider those of packing n equal or unequal circles in a circular container with minimum radius. Both problems can be formulated as optimization ones. The former is a combinatorial problem, while the latter is a continuous one. We propose heuristic approaches to tackle these problems. These are Iterated Local Search (ILS) heuristics for maximin LHDs, and Basin Hopping (BH) heuristics for packing problems. Actually, ILS and BH approaches have strong similarities and could be described within an unified framework. However, following the literature, where ILS approaches are mainly applied to combinatorial problems, while BH approaches are mainly applied to continuous problems, we will keep them apart. In order to deal with maximin LHDs, we propose two ILS variants, corresponding to two distinct optimality criteria which are employed to drive the search among LHDs. Extensive experiments are performed for the investigation of the strengths and weaknesses of the algorithms. A remarkable finding is that the most efficient method, though time consuming, performs a non monotonic search, driven by an appropriate objective function, within the space of LHDs. The proposed approaches are extensively compared with the existing ones in the literature, and many improved results with respect to best known ones, are obtained. In particular, the proposed methods seem to outperform the existing ones when the dimension of the design points increases. Finally, we also discuss about the time complexity of the algorithms; by mixing theoretical results with experimental ones, we derive an empirical formula for each ILS variant, returning the expected run time as a function of the number of design points and of their dimension. To deal with the problem of packing equal circles in a circular container with minimum radius, we propose a variant of BH, namely Monotonic BH (MBH) and its population based counterpart, Population BH (PBH). Extensive computational experiments are performed both to analyze the problem at hand, and to choose in an appropriate way the parameter values for the proposed methods. Different improvements with respect to the best results reported in the literature are detected. The problem of packing unequal circles in a circular container with minimum radius is also attacked with the MBH and PBH approaches, but some components of these approaches are adapted in order to fully exploit the peculiarities of the problem with unequal circles (in particular, its combinatorial nature due to the different radii of the circles). Again extensive computational experiments are performed and improvements with respect to the existing literature are detected. en_US
dc.description.statementofresponsibility Abdur Rakib Muhammad Jalal Uddin Jamali
dc.format.extent 178 pages
dc.language.iso en_US en_US
dc.publisher Università degli Studi di Torino, Torino, Italy en_US
dc.rights Khulna University of Engineering & Technology (KUET) thesis/dissertation/internship reports are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission.
dc.subject Latin Hypercube Designs (LHDs) en_US
dc.subject Experimental Design en_US
dc.subject Packing Problem en_US
dc.subject Heuristic Approach en_US
dc.title Heuristic Approaches for Maximin Distance and Packing Problems en_US
dc.type Thesis en_US
dc.description.degree Doctor of Philosophy
dc.contributor.department Dipartimento di Informatica (Computer Science)


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search KUET IR


Advanced Search

Browse

My Account

Statistics