[ERS03] Comparison of Different Lower Bounds for the Constrained Module Allocation Problem

Rapport Scientifique : Date de dépot: 2003/01/01, (Tech. Rep.: CEDRIC-03-473)

Auteurs: S. Elloumi , F. Roupin , E. Soutil

motcle:

Résumé: We consider the Constrained Module Allocation Problem (CMAP), where a set of program modules must be assigned to a set of processors having a limited capacity. The optimal assignment minimizes the sum of execution costs and communication costs between modules. This problem is naturally formulated as a quadratic 0-1 problem with linear constraints. In this paper, we propose seven lower bounds for the CMAP, coming from three families of techniques: linearization, semi-definite programming and lagrangian decomposition. We explain in details how to use these techniques. We make several comparisons from a theoretical point of view. Furthermore, we carry out an extensive experimental comparison, based on many generated instances of different types. Our objective is to give an empirical qualitative measure of the advantages and drawbacks of each lower bound.

Collaboration: LIPN

Download

BibTeX

@techreport {
	ERS03,
	title	=	"{Comparison of Different Lower Bounds for the Constrained Module Allocation Problem}",
	author	=	"S. Elloumi and F. Roupin and E. Soutil",
	number	=	"{CEDRIC-03-473}",
	institution	=	"{CEDRIC laboratory, CNAM-Paris, France}",
	date	=	{01-01-2003},
}