### Abstract

This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item's value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. 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 containing no more than two fractionally selected items, and develop a customized branch-and-bound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions.

Original language | English |
---|---|

Pages (from-to) | 459-489 |

Journal | Mathematical Programming |

Volume | 134 |

Issue number | 2 |

DOIs | |

Publication status | Published - Sep 2012 |

Externally published | Yes |

### Keywords

- OPTIMIZATION
- NEWSVENDOR
- ALGORITHM
- PORTFOLIO
- SELECTION

### Cite this

*Mathematical Programming*,

*134*(2), 459-489. https://doi.org/10.1007/s10107-011-0443-5

}

*Mathematical Programming*, vol. 134, no. 2, pp. 459-489. https://doi.org/10.1007/s10107-011-0443-5

**The static stochastic knapsack problem with normally distributed item sizes.** / Merzifonluoglu, Yasemin; Geunes, Joseph; Romeijn, H. Edwin.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - The static stochastic knapsack problem with normally distributed item sizes

AU - Merzifonluoglu, Yasemin

AU - Geunes, Joseph

AU - Romeijn, H. Edwin

PY - 2012/9

Y1 - 2012/9

N2 - This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item's value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. 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 containing no more than two fractionally selected items, and develop a customized branch-and-bound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions.

AB - This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item's value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. 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 containing no more than two fractionally selected items, and develop a customized branch-and-bound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions.

KW - OPTIMIZATION

KW - NEWSVENDOR

KW - ALGORITHM

KW - PORTFOLIO

KW - SELECTION

U2 - 10.1007/s10107-011-0443-5

DO - 10.1007/s10107-011-0443-5

M3 - Article

VL - 134

SP - 459

EP - 489

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -