The 0–1 bidimensional knapsack problem: Toward an efficient high-level primitive tool

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.