The 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool |
| |
Authors: | Arnaud Fréville Gérard Plateau |
| |
Affiliation: | (1) Laboratoire d'Informatique et de Mathématiques Appliquées de Valenciennes, URA CNRS no 1507, Institut des Sciences et Techniques, Université de Valenciennes, BP311, 59304 Valenciennes cedex, France;(2) Laboratoire d'Informatique de Paris-Nord, URA CNRS no 1507, Institut des Sciences et Techniques, Université de Valenciennes, BP311, 59304 Valenciennes cedex, France;(3) Laboratoire d'Informatique de Paris-Nord, URA CNRS no 1507, Institut Galilée, Université Paris-Nord, Avenue J.B. Clément, 93430 Villetaneuse, France |
| |
Abstract: | Efficient codes exist for exactly solving the 0-1 knapsack problem, which is a common primitive structure in relaxation and decomposition techniques for the solution of general models. We suggest moving to a higher primitive level by using the bidimensional knapsack, which can be used to enhance linear programming or Lagrangean type classical relaxations.With the ultimate aim of providing an exact and efficient solution to the bidimensional knapsack problem, we describe here a heuristic approach based on surrogate duality. In particular, we consider the usefulness of a specific preprocessing phase before a possible enumerative phase.Extensive numerical experiments, based on test problems from the literature as well as randomly generated instances, show that our code compares favorably with the GP procedure developed by Gavish and Pirkul for the multidimensional case. |
| |
Keywords: | 0-1 bidimensional knapsack heuristics implicit enumeration size reduction surrogate dual |
本文献已被 SpringerLink 等数据库收录! |
|