The static stochastic knapsack problem with normally distributed item sizes

Date

2012-09-01

Author

Merzifonluoglu, Yasemin
Geunes, Joseph
Romeijn, H. Edwin

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

267
views

0
downloads

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.

Subject Keywords

Software, General Mathematics

URI

https://hdl.handle.net/11511/66947

Journal

MATHEMATICAL PROGRAMMING

DOI

https://doi.org/10.1007/s10107-011-0443-5

Collections

Natural Sciences and Mathematics, Article

Suggestions

OpenMETU
Core

THE CLASS OF (2,2)-GROUPS WITH HOMOCYCLIC REGULATOR QUOTIENT OF EXPONENT p(3) HAS BOUNDED REPRESENTATION TYPE Arnold, David M.; Mader, Adolf; Mutzbauer, Otto; Solak, Ebru (Cambridge University Press (CUP), 2015-08-01) The class of almost completely decomposable groups with a critical typeset of type (2,2) and a homocyclic regulator quotient of exponent p(3) is shown to be of bounded representation type. There are only 16 isomorphism at p types of indecomposables, all of rank 8 or lower.
An exhaustive computer search for finding new curves with many points among fibre products of two Kummer covers over F-5 and F-7 Özbudak, Ferruh; Yayla, Oguz (The Scientific and Technological Research Council of Turkey, 2013-01-01) In this paper we make an exhaustive computer search for finding new curves with many points among fibre products of 2 Kummer covers of the projective line over F-5 and F-7. At the end of the search, we have 12 records and 6 new entries for the current Table of Curves with Many Points. In particular, we observe that the fibre product
Improved p-ary codes and sequence families from Galois rings of characteristic p(2) LİNG, SAN; Özbudak, Ferruh (Society for Industrial & Applied Mathematics (SIAM), 2006-01-01) This paper explores the applications of a recent bound on some Weil-type exponential sums over Galois rings in the construction of codes and sequences. A family of codes over F-p, mostly nonlinear, of length p(m+1) and size p(2) (.) p(m(D-[D/p2])), where 1 <= D <= p(m/2), is obtained. The bound on this type of exponential sums provides a lower bound for the minimum distance of these codes. Several families of pairwise cyclically distinct p-ary sequences of period p(p(m - 1)) of low correlation are also cons...
ON THE k-TH ORDER LFSR SEQUENCE WITH PUBLIC KEY CRYPTOSYSTEMS KIRLAR, Barış Bülent; Cil, Melek (Walter de Gruyter GmbH, 2017-06-01) In this paper, we propose a novel encryption scheme based on the concepts of the commutative law of the k-th order linear recurrences over the finite field F-q for k > 2. The proposed encryption scheme is an ephemeral-static, which is useful in situations like email where the recipient may not be online. The security of the proposed encryption scheme depends on the difficulty of solving some Linear Feedback Shift Register (LFSR) problems. It has also the property of semantic security. For k = 2, we propose ...
On quasi-compactness of operator nets on Banach spaces Emelyanov, Eduard (Institute of Mathematics, Polish Academy of Sciences, 2011-01-01) The paper introduces a notion of quasi-compact operator net on a Banach space. It is proved that quasi-compactness of a uniform Lotz-Rabiger net (T(lambda))(lambda) is equivalent to quasi-compactness of some operator T(lambda). We prove that strong convergence of a quasi-compact uniform Lotz-Rabiger net implies uniform convergence to a finite-rank projection. Precompactness of operator nets is also investigated.

Citation Formats

Y. Merzifonluoglu, J. Geunes, and H. E. Romeijn, “The static stochastic knapsack problem with normally distributed item sizes,” MATHEMATICAL PROGRAMMING, pp. 459–489, 2012, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/66947.