Relaxation Lagrangienne: Le Probleme Du Knapsack 0–1†

Publisher Website
Google Scholar
Abstract
We study the Lagrangian relaxation for the knapsack 0–1 problem and we present some of its characteristics. The three main steps of the algorithms to solve large scale knapsack 0–1 problems are: (1) solution of the associated linear program, (2) reduction of the number of variabies, and (3) choice of an implicit enumeration scheme. A particular 0–1 knapsack problem called “the value-independent knapsack problem” is also presented. We conclude by a qualification of the results exposed in this paper.