Date : 1989
Editeur / Publisher : Le Chesnay, France : Institut National de Recherche en Informatique et en Automatique , 1989
Type : Livre / Book
Langue / Language : français / French
Classification Dewey : 004
Collection : Rapports de recherche / INRIA / Le Chesnay : INRIA , 1980-2011
Résumé / Abstract : Abstract: "The characteristics of parallel machines (vectorization, multiprocessing) are exploited in order to solve the 0-1 multiknapsack problem: in a first phase, a lost of tests are performed in parallel in order to reduce the size of the problem (fixation of variables, elimination of constraints); in a second phase, a parallel Branch and Bound algorithm allows to get an optimal solution. Our parallel algorithm has been implemented on the asynchronous multiprocessor machine CRAY 2. Computational results are reported and compared with those obtained in a sequential approach