Wednesday, 15:45 - 16:10 h, Room: H 3004


Paolo Detti
The bounded sequential multiple knapsack problem


The Bounded Multiple Knapsack Problem (BMKP) is a generalization of the 0-1 multiple knapsack problem, where a bounded amount of each item type is available. In this work, a special case of BMKP is considered in which the sizes of the items are divisible. This problem is known in the literature as Bounded Sequential Multiple Knapsack Problem (BSMKP). Several authors have addressed the Bounded Sequential Knapsack Problem (BSKP). Pochet and Weismantel provided a description of the bounded sequential single-knapsack polytope. Polynomial time algorithms for BSKP and BSMKP are also proposed in the literature. This work basically extends the study of Pochet and Weismantel to BSMKP. Specifically, problem transformations are proposed for BSMKP that allow a characterization of the optimal solutions and the description of the BSMKP polytope.
Keywords: bounded sequential multiknapsack, optimal solutions, polytope description.


Talk 2 of the contributed session Wed.3.H 3004
"Knapsack and bin packing" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra In Canada influence on blood clots.