[QST07a] A branch-and-bound algorithm to solve large scale integer quadratic multidimensional knapsack problem

Conférence Internationale avec comité de lecture : SOFSEM'07, Harrachov, RÃ©publique TchÃ¨que, January 2007, Vol. 4362, pp.456-464, Series LNCS 4362,

Auteurs: D. Quadri , E. Soutil , P. Tolla

motcle:

Résumé: The separable quadratic multi-knapsack problem (QMKP) consists in maximizing a concave separable quadratic integer (non pure binary) function subject to m linear capacity constrainsts. In this paper we develop a branch-and-bound algorithm to solve (QMKP) to optimality. This method is based on the computation of a tight upper bound for (QMKP) wich is derived from a linearization and a surrogate relaxation. Our branch-and-bound also incorporates pre-processing procedures. The computational performance of our branch-andÃ¨bound is copared to that of three exact methods: a branch-and-bound algorithm developed by Djerdjour et al. (1988), a 0-1 linearization ethod originally applied to the separable quadratic knapsack problem with a single constraint that we extend to the case of m constraints, a standard branch-and-bound algorithm (Cplex 9.0 quadratic optimization). Our branch-and-bound clearly outperforms other methods for large instances (up to 2000 variables and constraints).

Equipe: oc

Collaboration: LIA

BibTeX

@inproceedings {
	QST07a,
	title	=	"{A branch-and-bound algorithm to solve large scale integer quadratic multidimensional knapsack problem}",
	author	=	" D. Quadri and E. Soutil and P. Tolla ",
	booktitle	=	"{SOFSEM'07, Harrachov, RÃ©publique TchÃ¨que}",
	year	=	2007,
	month	=	"January",
	series	=	"LNCS 4362",
	volume	=	4362,
	pages	=	"456-464",
}