Relaxation Lagrangienne: Le Probleme Du Knapsack 0–1^†

† Cette recherche a été financée partielllement par le Conselho Nacional de Desenvolvimento Cientifico e Tecnológico (Brésil), contrat CNPq 200.795–81.

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.

Résumé

Etant donné le probème du knapsack 0–1, nous étudions sa relaxation Lagrangienne classique et développons quelques propriétés caractéristiques du problème en question. Nous présentons les trois phases principales des algorithmes pour les problèmes de grande taille: (1) résolution du programme linéaire associé au problème du knapsack 0–1, (2) réduction de la taille de ce problème, et (3) résolution du problème réduit par une méthode d’énumération implicite. Une variante plus difficile de ce problème, quand les coefficients de la contrainte et de la fonction économique sont égaux pour chaque variable est exposée également. Cette étude est évaluée dans la conclusion.

Notes

† Cette recherche a été financée partielllement par le Conselho Nacional de Desenvolvimento Cientifico e Tecnológico (Brésil), contrat CNPq 200.795–81.

Additional information

Notes on contributors

Nelson Maculan

NELSON MACULAN is currently a Professor in the Coordenagao dos Programas de Pos-graduagao de Engenharia and Associate Professor in the Instituto de Matematica at Federal University of Rio de Janiero, Brazil; since January 1982 he has been Visiting Professor in the Departement d'informatique et de recherche operationnelle de l'Universite de Montreal. In January 1983 he became Vice-President of IFORS (International Federation of Operational Research Societies). Professor Maculan obtained a B sc in Mining Engineering (1965), a DEA in Statistics (1967), and a PHD in Production Engineering (1975). He has written numerous papers and two books, Programafdo Linear (1980) and Programagao Linear Inteira (1978).