A Branch-and-Bound Algorithm to Solve Large Scale Integer Quadratic Multi-Knapsack Problems
| Autor: | Dominique Quadri, Pierre Tolla, Eric Soutif |
|---|---|
| Rok vydání: | 2007 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783540695066 SOFSEM (1) |
| DOI: | 10.1007/978-3-540-69507-3_39 |
| Popis: | The separable quadratic multi-knapsack problem (QMKP) consists in maximizing a concave separable quadratic integer (non pure binary) function subject to mlinear 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 mconstraints, 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). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|