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" [...]


  Payday Loans Wisconsin. 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 No RX influence on blood clots.