Solving the three dimensional quadratic assignment problem on a computational grid

Mezmaz, Mohand; Mehdi, Malika; Bouvry, Pascal; Talbi, El-Ghazali; Tuyttens, Daniel

doi:10.1007/s10586-013-0313-4

Reference : Solving the three dimensional quadratic assignment problem on a computational grid


	Document type :	Scientific journals : Article
	Discipline(s) :	Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/10993/30197

Title :	Solving the three dimensional quadratic assignment problem on a computational grid
Language :	English
Author, co-author :	Mezmaz, Mohand [University of Mons]
	Mehdi, Malika [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
	Bouvry, Pascal [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
	Talbi, El-Ghazali [LIFL]
	Tuyttens, Daniel [University of Mons]
Publication date :	2014
Journal title :	Cluster Computing
Publisher :	Springer Science & Business Media B.V.
Volume :	17
Issue/season :	2
Pages :	205-217
Peer reviewed :	Yes (verified by ORBi^lu)
Audience :	International
ISSN :	1386-7857
Keywords :	[en] distributed computing ; branch and bound ; 3D QAP
Abstract :	[en] The exact resolution of large instances of combinatorial optimization problems, such as three dimensional quadratic assignment problem (Q3AP), is a real challenge for grid computing. Indeed, it is necessary to reconsider the resolution algorithms and take into account the characteristics of such environments, especially large scale and dynamic availability of resources, and their multi-domain administration. In this paper, we revisit the design and implementation of the branch and bound algorithm for solving large combinatorial optimization problems such as Q3AP on the computational grids. Such gridification is based on new ways to effi- ciently deal with some crucial issues, mainly dynamic adaptive load balancing and fault tolerance. Our new approach allowed the exact resolution on a nation-wide grid of a dif- ficult Q3AP instance. To solve this instance, an average of 1,123 computing cores were used for less than 12 days with a peak of around 3,427 computing cores.
Research centres :	University of Luxembourg: High Performance Computing - ULHPC
Permalink :	http://hdl.handle.net/10993/30197
DOI :	10.1007/s10586-013-0313-4

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Limited access	cluster.pdf		Publisher postprint	1.09 MB	Request a copy

All documents in ORBi^lu are protected by a user license.

University of Luxembourg Library | Feedback | Legal notices