The Static Stochastic Knapsack Problem with Normally Distributed Item Sizes
Speaker
Abstract
| You are cordially invited to attend the presentations. Details of the first presentation are given below. Remember that this is a lunch meeting. For ordering the right amount of sandwiches, coffee, tea and milk, please let us know before Wednesday, June 18th whether you will be present. We hope to welcome all of you. |
| We consider a static stochastic knapsack problem that requires assigning items with random sizes to a knapsack whose capacity is known and fixed. An item's value equals the realization of the product of a random unit revenue and the random size of the item. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is assessed for each unit of overflow, while our model allows for a salvage value for each unit of unused knapsack. We seek to maximize the expected net profit resulting from the selection of items in the knapsack. We focus on the case where item sizes are independent and normally distributed random variables, and provide an exact solution method for a continuous relaxation of the problem. We show that an optimal solution to this relaxation exists that contains no more than two fractionally selected items, and use this relaxation in a branch and bound algorithm for obtaining an optimal binary solution. In addition, we present a very efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions to the problem. |
| Contact information: |
| Wilco van den Heuvel |
