The static stochastic knapsack problem with normally distributed item sizes

Merzifonluoglu, Yasemin
Geunes, Joseph
Romeijn, H. Edwin
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.


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...
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: