
A Branch-and-Bound Algorithm to Solve Large Scale Integer Quadratic Multi-Knapsack Problems
Tolla, Pierre; Soutif, Eric; Quadri, Dominique (2007), A Branch-and-Bound Algorithm to Solve Large Scale Integer Quadratic Multi-Knapsack Problems, in Plasil, Frantisek; Sack, Harald; Meinel, Christoph; Van Der Hoek, Wiebe; Italiano, Giuseppe; Van Leeuwen, Jan, SOFSEM 2007: Theory and Practice of Computer Science, Springer : Berlin, p. 456-464. http://dx.doi.org/10.1007/978-3-540-69507-3_39
View/ Open
Type
Communication / ConférenceDate
2007Conference title
SOFSEM 2007: 33rd Conference on Current Trends in Theory and Practice of Computer ScienceConference date
2007-01Conference city
HarrachovConference country
République tchèqueBook title
SOFSEM 2007: Theory and Practice of Computer ScienceBook author
Plasil, Frantisek; Sack, Harald; Meinel, Christoph; Van Der Hoek, Wiebe; Italiano, Giuseppe; Van Leeuwen, JanPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
4362Published in
Berlin
ISBN
978-3-540-69506-6
Pages
456-464
Publication identifier
Metadata
Show full item recordAbstract (EN)
The separable quadratic multi-knapsack problem (QMKP) consists in maximizing a concave separable quadratic integer (non pure binary) function subject to m linear capacity constraints. 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) which 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 compared to that of three exact methods: a branch-and-bound algorithm developed by Djerdjour et al. (1988), a 0-1 linearization method 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 (Cplex9.0 quadratic optimization). Our branch-and-bound clearly outperforms other methods for large instances (up to 2000 variables and constraints).Subjects / Keywords
Surrogate relaxation; Linearization; Separable quadratic function; Integer programming; Branch-and-boundRelated items
Showing items related by title and author.
-
Quadri, Dominique; Soutif, Eric; Tolla, Pierre (2009) Article accepté pour publication ou publié
-
Quadri, Dominique; Soutif, Eric; Tolla, Pierre (2007) Article accepté pour publication ou publié
-
Soutif, Eric; Quadri, Dominique (2007) Article accepté pour publication ou publié
-
Quadri, Dominique; Soutif, Eric; Tolla, Pierre (2007) Document de travail / Working paper
-
Quadri, Dominique; Soutif, Eric; Tolla, Pierre (2007) Chapitre d'ouvrage