|
 
|
[BS04b] Using a Mixed Integer Programming Tool for Solving the 0-1 Quadratic Knapsack Problem
Revue Internationale avec comité de lecture : Journal INFORMS, vol. 16(2), pp. 188-197, 2004Mots clés: programming; integer; nonlinear; 0–1 quadratic knapsack; linearization; branch and bound; experiments
Résumé:
Abstract. We consider in this paper the 0-1 Quadratic Knapsack Problem (QKP). Our purpose is to show that using a linear reformulation of this problem and a standard mixed integer programming tool, it is possible to efficiently solve (QKP) in terms of computation time and of size of problems, in comparison with the existing methods. Considering a problem involving n variables, the linearization technique we propose has the advantage of adding only (n-1) real variables and 2(n-1) constraints. This method allows to exactly solve (QKP) instances up to 140 variables.
Commentaires:
(présenté à ROADEF 2000, Nantes, 26-28 janvier 2000)
Equipe:
oc
BibTeX
| @article { | |||
| BS04b, | |||
| title | = | "{Using a Mixed Integer Programming Tool for Solving the 0-1 Quadratic Knapsack Problem}", | |
| author | = | "A. Billionnet and E. Soutil", | |
| journal | = | "INFORMS", | |
| year | = | 2004, | |
| volume | = | 16, | |
| number | = | 2, | |
| pages | = | "188-197", | |
| note | = | "{(présenté à ROADEF 2000, Nantes, 26-28 janvier 2000)}", | |
| } | |||
