The static stochastic knapsack problem with normally distributed item sizes

Yasemin Merzifonluoglu, Joseph Geunes*, H. Edwin Romeijn

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

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 languageEnglish
Pages (from-to)459-489
JournalMathematical Programming
Volume134
Issue number2
DOIs
Publication statusPublished - Sep 2012
Externally publishedYes

Keywords

  • OPTIMIZATION
  • NEWSVENDOR
  • ALGORITHM
  • PORTFOLIO
  • SELECTION

Cite this

Merzifonluoglu, Yasemin ; Geunes, Joseph ; Romeijn, H. Edwin. / The static stochastic knapsack problem with normally distributed item sizes. In: Mathematical Programming. 2012 ; Vol. 134, No. 2. pp. 459-489.
@article{f4edc7d5fa5444399192b327b4b70396,
title = "The static stochastic knapsack problem with normally distributed item sizes",
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.",
keywords = "OPTIMIZATION, NEWSVENDOR, ALGORITHM, PORTFOLIO, SELECTION",
author = "Yasemin Merzifonluoglu and Joseph Geunes and Romeijn, {H. Edwin}",
year = "2012",
month = "9",
doi = "10.1007/s10107-011-0443-5",
language = "English",
volume = "134",
pages = "459--489",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "2",

}

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

In: Mathematical Programming, Vol. 134, No. 2, 09.2012, p. 459-489.

Research output: Contribution to journalArticleScientificpeer-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 -