\documentclass{ctwart}

\bibliographystyle{plain}% 

\usepackage{amssymb,amsmath,color}
\usepackage{dsfont}   
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\E}{\mathbb E}
\newcommand{\I}{\mathbb I}
\newcommand{\1}{\mathbb H}
\newcommand{\Y}{\mathbb Y}
\begin{document}

\setcounter{page}{111}

\begin{frontmatter}

\title{On a Stochastic Knapsack Problem}

\author{Stefanie Kosuch \and Marc Letournel  \and Abdel Lisser}
  
\address{Laboratoire de recherche en Informatique, Universit\'e Paris Sud\\ 91405 Orsay Cedex, France}

\begin{keyword}
stochastic knapsack \sep expectation constraint \sep stochastic gradient method \sep Arrow-Hurwicz
\end{keyword}

\end{frontmatter}

\section{Introduction}
%
The deterministic knapsack problem is a well known and well studied
NP-hard combinatorial optimization problem. It consists in filling a
knapsack with items out of a given set such that the weight capacity
of the knapsack is respected and the total reward maximized. For a
review of references on the stochastic knapsack problem, stochastic
gradient algorithms and branch-and-bound methods see \cite{ApC}. In
the deterministic problem, all parameters (item weights, rewards,
knapsack capacity) are known (\textit{deterministic}). In the
stochastic counterpart, some (or all) of these parameters are
assumed to be random, i.e. not known at the moment the decision has
to be made.\\
In this paper, we study the stochastic knapsack problem with
expectation constraint. The item weights are assumed to be independently normally distributed.
We solve the relaxed version of this problem
using a stochastic gradient algorithm in order to provide upper
bounds for a branch-and-bound framework. Two approaches to estimate
the needed gradients are applied, one based on Integration by Parts
and one using Finite Differences. Finite Differences is a robust and
simple approach with efficient results despite the fact that
the estimated gradients are biased, meanwhile Integration by Parts is
based upon a more theoretical analysis and permits to enlarge the
field of applications.
%
\section{Mathematical formulations}\label{sec:form}
 %
We consider a stochastic knapsack problem of the following form:
Given a set of $n$ items. Each item has a weight that is not known
in advance and the decision of which items to choose has to be made
without the exact knowledge of their weights. Therefore, we handle
the weights as random variables and assume that weight $\chi_i$ of
item $i$ is independently normally distributed with mean $\mu_i>0$
and standard deviation $\sigma_i$. Furthermore, each item has a fix
reward per weight unit $r_i>0$. We denote by $\chi$, $\mu$, $\sigma$
and $r$ the corresponding $n$-dimensional vectors. The aim is to
maximize the expected total gain $\E[\sum_{i=1}^n r_i \chi_i x_i]$.
In addition, we assume that the knapsack problem has a fixed weight
capacity $c>0$.
In this paper, we solve the following expectation constrained
knapsack problem:\\
\\
 %
\textbf{Expectation Constrained Knapsack Problem ($ECKP$)}
\begin{eqnarray}\label{ECKP}
&&{\max_{x\in \{0,1\}^n} \E \left[\sum_{i=1}^n r_i \chi_i x_i\right]}\\
\textnormal{s.t. } &&\E\left[\1_{\R^+}(c-g(x,\chi))\right]\geq p \label{cons:ECKP}
\end{eqnarray}
%
where $\E\left[\cdot \right]$ denotes the expectation, $g(x,\chi) =
\sum_{i=1}^n \chi_i x_i$ is the total weight of the chosen items,
$\1_{\R^+}$ denotes the indicator function of the positive real
interval - the Heaviside function, and $p\in (0.5,1]$ is the
prescribed probability.
%
We refer to the function inside the expectation of the constraint function as
$\theta$, i.e. $\theta(x,\chi) = \1_{\R^+}(c-g(x,\chi))$.
% 
\section{Problem solving method}\label{sec:methods}
 %
Due to its combinatorial nature, $ECKP$ can be solved using a
branch-and-bound framework as presented in \cite{ApC}. To obtain
upper bounds, the authors propose to solve the corresponding
continuous optimization problem using a stochastic gradient
type algorithm. A stochastic gradient algorithm is an algorithm that combines both Monte-Carlo techniques and the deterministic gradient method. More precisely, instead of computing the gradient of the objective funtion (that is a function in expectation) to determine the direction of descent, one uses the gradient of the function insight the expectation. By drawing independent samples of the random variables at each iteration, one approximates the expectation.\\ 
Applying a gradient method to solve the relaxed $ECKP$ is promising as its
objective function is concave and, in addition, constraint
(\ref{cons:ECKP}) defines a convex feasible set due to the
assumption that the weights are independently normally distributed.\\
%
The particular stochastic gradient algorithm used in this work is the Stochastic Arrow-Hurwicz
algorithm (hereafter called $SAH$-algorithm) that uses Lagrangian
multipliers to deal with the expectation constraint (for further
details see \cite{Culioli}).\\
%
However, to use such an algorithm for $ECKP$, one has to
estimate the gradient of the indicator function $\1_{\R^+}(\cdot)$.
In this paper, we apply two different approaches: the first one is a
non-biased estimator based on Integration by Parts (called hereafter
\textit{IP-method}) proposed in \cite{Thesis} to solve
continuous stochastic optimization problems. The second approach is
a Finite Differences estimator (\textit{FD-method}) presented in
\cite{Andrieu}. Unlike the IP-method method, the FD-method provides
a biased estimator of the gradient.\\
In subsection \ref{sec:FD} we present the two methods. Subsection \ref{sec:convanalysis} gives a first insight in the convergence analysis we conducted.
%
\subsubsection{Gradient computation methods}\label{sec:FD}
%
 In the FD-method, the $h$-th component of the gradient of
 $\theta$ is approximated by the corresponding difference quotient
%
\[\frac{\theta(x+\delta \nu^h,\chi) -  \theta(x-\delta \nu^h,\chi)}{2\delta}\]
%
where $\delta > 0$ and $\nu^h \in \{0,1\}^n$ such that $\nu^h_h=1$ and $\nu^h_i=0$ for $i\not=h$.\\
%
The basic idea of the IP-method consists in using Integration by
Parts to reformulate $\E[\theta(x,\chi)]$ which gives rise to a
function in expectation $\E[\widetilde{\theta}(x,\chi)]$ s.t.
$\E[\widetilde{\theta}(x,\chi)] = \E[\theta(x,\chi)]$.
$\widetilde{ \theta}$ is differentiable and the idea is to use the
gradient of $\widetilde{\theta}$ in the $SAH$-algorithm.
% 
Andrieu et al. presented how to compute such a
$\widetilde{\theta}(x,\chi)$ using Integration by Parts (see Theorem
5.5 in \cite{Thesis}). We state and proof their theorem for the case of $ECKP$ with
normally distributed weights.
%
\subsubsection{Convergence analysis}\label{sec:convanalysis}
When using the IP-method, main adaptations have been made to correctly check all hypotheses of convergence. Instead of replacing $\{0,1\}^n$ by $[0,1]^n$ when relaxing $ECKP$, the theoretical analysis compels us to consider a complementary set of a neighborhood of $0_{[0,1]^n}$. However, assuming that an empty knapsack is not an optimal solution, it is convenient to consider that the optimal solution vector of the continuous problem contains at least one component $x_{\kappa}$ with $x_{\kappa}\geq 1/n$. We are thus allowed to replace $[0,1]^n$ by $\{x\in [0,1]^n \,|\, ||x||_{\infty} \geq 1/n\}=X_{cont}$. Accordingly, we obtain the following admissible set of the relaxed $ECKP$:
%
\[X^{ad}_{cont} = \{x\in X_{cont}: \E\left[\1_{\R^+}(c-g(x,\chi))\right] \geq p\}\]
%
Checking that all steps of the algorithm stay in this subset is a central point of our work.
%
\section{Numerical results for the relaxed and combinatorial ECKP}\label{sec:NumRes}
%
We tested our algorithms on an instance from the literature as
well as on a great number of randomly generated instances.\\
Numerical tests of the $SAH$-algorithm involving the abovementioned adaptations have shown that the algorithm converges on all tested instances. We also compared our approach with a method that has previously been used to solve the relaxed $ECKP$. The idea of this method is to reformulate the problem as a deterministic equivalent second order cone problem ($SOCP$) and to solve it using an interior point algorithm. It turned out that in terms of running time, our $SAH$-algorithm outperforms the $SOCP$ approach for small and medium size instances (up to $1000$ items). Concerning the resolution of the combinatorial problem using a branch-and-bound framework, we are able to solve problems with up to $250$ items in an average computing time of $1h$. In comparison, when using the $SOCP$ procedure one can only solve problems up to $75$ items in comparable time.
%
\bibliography{31_Kosuch_StochKnap}
\end{document}
   
