Efficient Algorithms with Performance Guarantees for the Stochastic Multiple-Choice Knapsack Problem

1 Introduction

The class of knapsack problems is a fundamental set of NPhard combinatorial optimisation problems that are widely used in many areas, ranging from finance and management science, to computer science and artificial intelligence. The standard (or 0-1) knapsack problem consists of a knapsack with capacity C, and a set of items, each of which has certain value and weight. The goal of the decision maker (i.e., the optimiser) is to find a set of items with maximum total value such that the sum of the items' weight does not exceed the capacity C of the knapsack. Other popular variants of the knapsack require different constraints, such as: (i) choosing multiple copies of a single item is allowed (bounded/unbounded knapsack); (ii) choosing one from each subset of items (multiple-choice knapsack); or (iii) putting items into multiple knapsacks (multi-knapsack) (for further details of the knapsack problems, see, e.g., [Kellerer et al., 2004]).

∗Corresponding author. University of Southampton, UK. Email: l.tran-thanh@soton.ac.uk.

†University of Science and Technology of China. Email: yingce.xia@gmail.com.

‡Microsoft Research. Email: taoqin@microsoft.com.

§University of Southampton, UK. Email: nrj@ecs.soton.ac.uk.

In the classical (or offline) setting of the knapsack problems, the items are typically available for the decision maker from the beginning of the process, with deterministic and known values and weights. However, a number of researchers are recently focussing on the stochastic version [Lueker, 1995; Babaioff et al., 2007; Tran-Thanh et al., 2012], where a set of new items arrive to the system at each time step in an online manner, and the value and weight of these items are typically randomly drawn from a distribution. The decision maker then chooses (a subset of) items to place into the knapsack without exceeding its capacity, while disposing of the others (which cannot be reused in the future). This stochastic setting has many applications, especially in the field of artificial intelligence and its related areas, such as stochastic planning, sequential decision theory, and online machine learning [Cohn and Mit, 1998; Lu et al., 1999; Benoist et al., 2001; Tran-Thanh et al., 2012], as problems within these areas typically consist of real-time processes, where the decisions have to be made sequentially at each time step. Despite the important role of the stochastic knapsacks in many research areas, and the fact that their offline counterpart have been thoroughly investigated for many years, only a small number of efficient algorithms, that require low computational costs and enjoy good theoretical performance guarantees, have been proposed within this area. In more detail, while researchers have devised approximation algorithms, that are both theoretically and practically efficient, for the stochastic 0-1 [Lueker, 1995; Kakade et al., 2007] and bounded/unbounded knapsacks [Ding et al., 2013; Tran-Thanh et al., 2014], similar efficient algorithms for other stochastic knapsacks have not yet been proposed.

Against this background, this paper aims to fill the gap by introducing new efficient algorithms for the stochastic multiple-choice knapsack problem (S-MCKP), an important variant of the stochastic knapsack, which occurs in many sequential decision making problems. In particular, in SMCKP, a set of K items, whose value and weight are randomly drawn from stationary value-weight distributions, arrive to the system at each time step, and a decision maker has to choose at most one item to put into the knapsack, in order to maximise the total expected value of the chosen items, before the true value and weight of each item are revealed to her. This problem is motivated by many real-world applications. For example, consider the search and rescue domain in robotics, where an autonomous rescue robot has to decide at each round (i.e., time step) where to go. To reach different locations, the robot has to consume a certain amount of energy (i.e., weight) from its limited battery (i.e., capacity), and receives a certain utility (i.e., value) when it executes the task. Since it can have access to the observations of the other first responders and searchers, it can also evaluate the cost and utility of other actions it did not choose (i.e., all the valueweight pairs are revealed) at the end of each round. The goal of the robot is then to maximise its total utility over a finite time horizon, with respect to its limited battery.

While the S-MCKP has been studied as a special case of a more generic model [Badanidiyuru et al., 2013], or with simplified settings [Zhou and Naroditskiy, 2008], state-of-theart algorithms are still computationally expensive and do not have good performance guarantees, and thus, cannot be used in real-world applications (see Section 2 for more details). In addition, other existing stochastic knapsack algorithms, that are designed for different settings, are not suitable for efficiently handling the multiple-choice constraint, and thus, they will not provide good performance in S-MCKP either. To this end, our main goal is to develop fast algorithms that can provide good theoretical performance guarantees for the SMCKP. In particular, we consider two settings that together cover all the possible scenarios, namely: (i) when the valueweight distribution functions are known; and (ii) when this distribution functions are not known a priori. Given these two settings, we first introduce OPT-S-MCKP, an algorithm which is provably optimal (i.e., provides the best expected performance) for the case of known value-weight distributions. We also show that its performance loss (i.e., the difference between an algorithm's performance to that of the best possible) in the case of having unknown value-weight distributions is at most ˜O(√T) where T is the finite time horizon, and the logarithmic terms are hidden in the ˜O notation. Note that the sub-linear (e.g, squared root) performance loss implies that the average performance loss per time step is converging to 0 as T tends to infinity. Thus, the behaviour of the algorithm with a sub-linear performance loss converges to that of an optimal algorithm. However, as S-MCKP is NP-hard, this optimal algorithm cannot be computationally efficient. To overcome this issue, we additionally propose two novel approximation algorithms, FR-S-MCKP; and G-SMCKP, respectively. These algorithms represent two dominant classes of approximation techniques within the knapsack literature. In particular, the former follows a fractional relaxation approximation approach, and enjoys a poly(K) computational cost per time step (K is the number of items per time step), while the latter applies a greedy approximation method, and achieves linear computational complexity. In addition, we also prove that FR-S-MCKP provably achieves performance loss of at most ˜O(√T) for both cases of known and unknown value-weight distributions. In contrast, while similar performance guarantees do not exist for G-S-MCKP, we demonstrate through extensive numerical evaluation that it can achieve similar performance, compared to that of the other two methods, with significantly lower computational cost. In summary, we extend the state of the art as follows:

• We provide the first comprehensive theoretical analysis for a stochastic knapsack problem, S-MCKP, that is widely used in many real-world applications. In particular, we propose OPT-S-MCKP, the first method that is optimal when the value-weight distributions are known, and can achieve performance loss guarantee of ˜O(√T) when the distributions are not given a priori.
• We also propose two novel approximation algorithms, R-S-MCKP, and G-S-MCKP, that can achieve efficient performance with low computational costs, and we show that FR-S-MCKP can provably achieve ˜O(√T) performance loss guarantee for both cases of known and unknown distributions.

In the remainder of the paper, we first provide a review of the related work (Section 2). We then describe S-MCKP (Section 3) and the algorithms in more detail (Sections 4 and 5). We also provide the theoretical analysis (Theorems 1, 2, and 3) and numerical evaluation of the algorithms (Section 6).

2 RelatedWork

[Lueker, 1995] was the first to investigate knapsack problems in the stochastic setting. In particular, he proposed a greedy approach to approximate the stochastic 0-1 knapsack problem, and he proved that the algorithm can guarantee a performance loss of at most O(lnT). His results were later extended by [Kakade et al., 2007], who described an approximation technique with ˜O(√T) performance loss guarantee for the online 0-1 knapsack problem with adversarial values and weights (i.e., here the sequence of values and weights is not randomly drawn from a distribution, but is set a priori by an adversary). These approaches, however, are specifically designed for the 0-1 knapsack, and thus, cannot be applied to our settings, as they heavily rely on the fact that the decision space at each time step is binary.

More similar to our paper are the works on bounded and unbounded stochastic knapsacks (which are in fact special cases of the multiple-choice version, with the time horizon set to be infinite). More specifically, [Tran-Thanh et al., 2010; 2012; Ding et al., 2013] investigated the unbounded setting, and proposed algorithms that can achieve O(lnT) performance loss, compared to that of the best possible. On the other hand, existing algorithms for bounded (i.e. there is a limit on the number of copies we can choose from each single item) knapsack are less efficient. In particular, [Tran-Thanh et al., 2014] proposed an algorithm with O(T 2/3 ) performance loss guarantee, while the algorithm developed by [Ho and Wortman-Vaughan, 2012] can achieve a performance approximation with a comparative ratio (i.e., the performance loss is linear). Nevertheless, the abovementioned algorithms, both for unbounded and bounded knapsacks, cannot be applied to our settings as they are designed for special cases of our model, that does take the finite time horizon T into account. Thus, they may put into a knapsack a sequence of items that contains significantly larger items than T , which is the maximal number of items we can put into the knapsack (as at most one item can be chosen per time step). More recently, [Badanidiyuru et al., 2013] investigated the stochastic multi-dimensional knapsack, that can be regarded as a generalisation of many knapsack problems, and proposed two approximation algorithms with guaranteed performance losses. However, these algorithms are designed for very generic settings, and thus, are computationally very involved, with inefficient performance guarantees, compared to our results. In particular, their results guarantee a ˜O(√OPT) upper bound on the loss, where OPT is the performance of the optimal solution, which is typically significantly larger than ˜O(√T). Apart from this, S-MCKP was also studied by [Zhou and Naroditskiy, 2008] with a modified setting, where all the valueweight pairs are revealed before each decision. However, their algorithm does not have any performance guarantees.

It is worth mentioning that a special case of our setting, where all the weights are set to be equal and deterministic, is a well studied topic in the online machine learning literature, known as the problem of learning with expert advices [Cesa-Bianchi et al., 1997; Cesa-Bianchi and Lugosi, 2006]. Within this area, state-of-the-art algorithms typically enjoy a constant performance loss, compared to that of the best fixed solution on hindsight. However, as these algorithms do not take the weights into account, they are not suitable to tackle S-MCKP, where the role of the weights are essential. More recently, [Amin et al., 2015] introduced weights (as advice costs) into this domain of learning with expert advice. However, their model only considers fixed and deterministic weights, with a per time step capacity, which is refilled after each time step. Given these differences in the model, their proposed method does not fit into our setting, and thus, will not be suitable for providing efficient performance.

3 The S-MCKPModel

In this section we describe the stochastic multiple-choice knapsack problem (S-MCKP) in more detail. The S-MCKP model consists of a knapsack with capacity C. At each time step t ∈ {1, . . . , T}, we have to choose one from a set of K items Kt = {(vt(k), wt(k))|1 ≤ k ≤ K} where vt(k) and wt(k) are the value and the weight of the kth item fromKt, respectively. Let Vt = {vt(k)}Kk=1 andWt = {wt(k)}Kk=1 denote the vectors of values and weights of the items at time step t, respectively. In our setting, we assume that these value and weight vectors are drawn from stationary value-weight distributions. Moreover, let DV and DW denote the marginal distribution of value vector Vt and weight vector Wt, respectively. For now, we assume that DW is discrete, that is, wt(k) are discrete values 1 . We also assume that there exist V,W > 0 such that for each 1 ≤ k ≤ K and 1 ≤ t ≤ T, vt(k) ≤ V and wt(k) ≤ W with probability 1. Now, let pk(w) denote the probability that wk(t) = w. In addition, let µk = E[vt(k)] denote the expected value we can get if we choose the kth item of Kt. Since Kt is drawn from a stationary joint value-weight distribution, E[vt(k)] remains the same for all t and thus, we can leave the time index out from µk. Let µ = {µk}Kk=1 be the vector of these expected values.

1 This assumption can be easily relaxed to real-value weights. In fact, the main purpose of having this assumption is that it is easier to

In our model, the concrete value and weight of each item in Kt is only revealed after we have chosen an item from Kt (these values are also revealed if we decide not to choose any items). Our goal is to choose at most one item from each Kt and put it into the knapsack such that the total weight cannot exceed the capacity C and the expected total value of the chosen items is maximised. More formally, let xt ∈ {0, 1}K denote a binary vector that represents our item choice at time step t. That is, ∑Kk=1 xt(k) ≤ 1. Our objective is to find a sequence of xt for t = 1, 2, . . . , T such that we achieve the optimal solution for the following constrained problem:

In what follows, we will discuss two cases, that covers all the possible scenarios of the problem, in more detail, namely: (i) we know in advance the joint value-weight distribution of the items (Section 4); and (ii) we do not have prior knowledge about this joint value-weight distribution (Section 5).

4 S-MCKP with Known Distributions

In this section, we assume that we have accurate prior knowledge about the joint value-weight distribution, and thus, both DV and DW are known in advance. To tackle this version of S-MCKP, we first propose an optimal solution (Section 4.1), which is computationally involved. To overcome the computational issues, we propose two near-optimal heuristics, each of which is taken from a popular class of approximation algorithms within the knapsack literature, that are computationally efficient (Sections 4.2 and 4.3).

4.1 An Optimal Solution

We first provide an optimal solution of the S-MCKP model. To do so, we introduce the following terms. Let G∗ (c, t) denote the maximal expected total value that we can achieve from time step t, with remaining budget c. Note that what we want to calculate is G∗ (C, 1). In addition, let G∗ (c, t, k) denote the maximal expected total value we can achieve if we choose the kth item from Kt, with remaining budget c. To formalise the fact that we can decide not to choose any of the items at time step t, we introduce a new item indexed by k = 0 such that it always returns value and weight 0. This implies that µ0 = w0 = 0. Now we turn to the description of the Bellman equations. Note that when t ≥ T + 1 (i.e., we exceed the time horizon), for any c > 0, we have:

describe the main idea of OPT-S-MCKP on discrete weights, while FR-S-MCKP and G-S-MCKP can work with real-value weights without modification. To adopt OPT-S-MCKP to the case of realvalue weights, we only have to replace the Bellman equations described in Section 4.1 with their differential equation counterparts.

where 0 ≤ k ≤ K. In fact, this indicates that when we reach the time horizon, no additional item (and thus, value) can be added to the knapsack. Furthermore, for any c ≤ 0, 1 ≤ t ≤ T , and 0 ≤ k ≤ K, we have:

That is, we cannot achieve any improvements if we exceed the capacity. We now have the following recursion. For each 1 ≤ t ≤ T , and 0 ≤ k ≤ K, we have

This implies that G∗ (c, t) = max0≤k≤K G∗ (c, t, k). We can also identify the item which we have to choose fromKt (including the fake item k = 0) in the optimal solution. In particular, let k∗ (c, t) denote this optimal item at time step t with the remaining capacity is c. We have:

Note that k∗ (c, T + 1) = 0 for any c. It is known that the solution of this set of Bellman equations (or dynamic programming) provides the optimal solution of S-MCKP [Kellerer et al., 2004]. Indeed, with this recursion, we can identify k∗ (C, 1), which is the first item of the optimal solution. Given this, the optimal algorithm, OPT-S-MCKP, is as follows:

Initialisation: We set t = 1 and ct = C, respectively.

Solving the equations: We solve the Bellman equations described in Eqs (2) - (5) for each t and ct, from which we obtain k∗ (ct, t), the optimal item to be chosen at each time step t and residual capacity ct.

Iterative steps:

1. We put k∗ (ct, t) into the knapsack and observe its value and weight. Let wk∗ (ct,t) denote the latter.
2. We set ct+1 = ct -wk∗ (ct,t) and t = t + 1. We repeat Step 1 with the new time and capacity values.

This algorithm, however, is computationally involved, as we have to solve a set of O(KTC) Bellman equations. This will lead to heavy computational cost in case of large T and C, which is typical in many real-world applications(see our experiments for more details). Given this, we next discuss two computationally more efficient approximation algorithms (i.e., with polynomial computation cost) for the S-MCKP.

4.2 Fractional Relaxation-based Approximation

We start with the description of FR-S-MCKP, a fractional relaxation-based approximation method for S-MCKP. In particular, the approach relies on the following idea. One way to overcome the computational complexity of OPT-S-MCKP is to relax the original problem described in Eq (1). In particular, let νk = E[wk] denote the expected weight of item k. Let vector ν = {νk}Kk=1 denote by the set of these expected weights. Similarly to the case of OPT-S-MCKP, we also add a dummy item with index k = 0, fixed value 0, and fixed weight 0, respectively. We consider the following fractional relaxation of the S-MCKP:

That is, we allow xt(k) to be fractional (and not binary as in the original S-MCKP). In addition, we also relax the capacity constraint so that instead of restricting the total sum of weights has to be smaller than C for almost surely (as it is the case in the original problem), we only require the average total weight to be smaller than the capacity of the knapsack. This relaxation enjoys the advantage of having a polynomial (in the number of items) computational cost to calculate its optimal solution [Bagchi et al., 1996]. Suppose that {x∗t }Tt=1 = {{x∗t (k)}Kk=0}Tt=1 denote the optimal solution of the abovementioned relaxed problem. Since by modifying the contribution of the dummy item to this solution does not violate the capacity constraint at all, we can increase x∗t (0) until we exceed 1. That is, we set the new x∗t (0) := 1- ∑Kk=1 x∗t (k). By doing so, we can always guarantee that the sum of the elements within the optimal solution {x∗t }Tt=1 is always T (this will play an important role in the proofs). Thus, FR-S-MCKP can be described as follows: Initialisation: We set t = 1 and ct = C, respectively. Iterative steps:

1. We solve the relaxed knapsack problem described in Eq (6) with residual capacity ct and remaining time T -t+1 (i.e., we replace C and T with ct and T -t+1, respectively). Let {x∗τ }T+1-t τ=1 denote the optimal solution, where x∗τ = {x∗τ (k)}Kk=0 .
2. We then randomly choose item k with probability qt(k) = ∑τ x∗τ (k) ∑τ ∑k x∗τ (k) . Let k∗ (ct, t) denote the chosen item with weight wk∗ (ct,t). If t ≥ T (we exceed the time limit) or wk∗ (ct,t) > ct (we exceed the capacity limit) then STOP. Otherwise put item into knapsack.
3. We set ct+1 = ct -wk∗ (ct,t) and t = t + 1. We repeat Step 1 with the new time and capacity values.

The intuition behind this algorithm is that by choosing an item with probability qt(k), we can guarantee that the expected value of the chosen item is actually 1 T of the optimal solution of the relaxed knapsack. Thus, by summing up over T time steps, the performance of FR-S-MCKP converges to the relaxed optimal solution, which is an upper bound of the optimum of the original S-MCKP. In fact, regarding the performance of FR-S-MCKP, we state the following:

Theorem 1 Let K∗ = argmaxk µk νk . Recall that W denotes the upper bound for all the possible weights. The performance loss of FR-S-MCKP, defined of the difference between its expected performance and that of OPT-S-MCKP, is at most

That is, we can guarantee that the expected performance of FR-S-MCKP is at most ˜O(√T) less than that of the optimal solution, where all the logarithmic terms are hidden in the notation ˜O. In terms of computational cost, at each time step t, FR-S-MCKP solves the relaxed knapsack problem defined in Eq (6) with poly(K) cost (where the degree of the polynom is strictly larger than 1), it is clearly faster than OPT-S-MCKP.

Due to space limitations, we omit the proof. However, the main steps of the proof can be sketched as follows. We decompose the total performance loss of FR-S-MCKP into stepwise losses. We then provide an upper bound for each stepwise loss with a function f, which is linear to the difference between the current remaining capacity ct of FR-S-MCKP and the average capacity of the optimal solution at the current time step t. We then provide a martingale in which the differences between the consecutive elements are upper bounds of the abovementioned capacity differences. By applying the Azuma-Hoeffding inequality on this martingale, we provide an upper bound on how large these differences can be. Finally, by summing up these bounds over T, we obtain the desired performance loss bound.

4.3 Greedy Approximation

We now turn to the discussion of G-S-MCKP, a greedy heuristic for S-MCKP. In this heuristic, at each time step t, we greedily choose the item that, if we are only allowed to solely choose that item in the remaining time steps, will provide the highest total value w.r.t. the remaining capacity. In particular, the itemwe choose at time step t is the one that satisfies:

That is, at each time step t, we consider all the indices that on average can still fit into the remaining capacity ct if we have to consecutively choose that single index in the remaining part of the process. We then choose the index that provides highest total expected value in the remaining time steps. Hence, the algorithm can be described as follows:

Initialisation: We set t = 1 and ct = C, respectively. Iterative steps:

1. We calculate k∗ (ct, t) according to Eq (7) and choose this item. If t ≥ T (we exceed the time limit) or wk∗ (ct,t) > ct (we exceed the capacity limit) then STOP. Otherwise put item k∗ (ct, t) into the knapsack and GOTO Step 2.
2. We set ct+1 = ct -wk∗ (ct,t) and t = t + 1. We repeat Step 1 with the new time and capacity values.

The intuition behind this heuristic is, that in many cases, by solely choosing a fixed item, we can still achieve a good approximation solution for the knapsack problem (see [Kellerer et al., 2004] for more details). Following this idea, this algorithm chooses the best fixed-item strategy that can maximise the total value in the remaining time steps, in order to achieve better approximation. This algorithm is computationally very efficient, as evaluating Eq (7) only requires O(K) complexity at each time step. Thus, it is significantly more efficient in terms of computational costs, compared to OPT-S-MCKP

and FR-S-MCKP, respectively. On the other hand, unlike FRS-MCKP, we do not have theoretical guarantees on the performance of G-S-MCKP. However, as we will demonstrate later, that G-S-MCKP can provide good performance in practice.

5 S-MCKP with Unknown Distributions

In this section, we investigate the case when the value-weight distributions are unknown. That is, we do not have the full information about the distribution function of the value-weight pairs of the items. Instead, we can only observe a realisation of these pairs at each time step. In this setting, achieving the optimum is impossible, as it requires the full knowledge of the distribution functions. Given this, the main goal is shifted to the minimisation of the performance loss. As such, we aim to develop algorithms with sub-linear losses. To achieve this goal, we provide a solution that combines the previously proposed algorithms with distribution estimation in order to efficiently fit this case of S-MCKP. In particular, we describe how to maintain an approximate of the unknown value-weight distributions at each time step and how to apply OPT-S-MCKP, FR-S-MCKP, and G-S-MCKP to this sequence of approximated distributions. We then provide rigorous theoretical performance guarantees for these solutions.

5.1 Approximated S-MCKP

We start with the approximation of the value-weight distribution. As we can observe the K value-weight pairs of each item k at every time step, we can use the empirical distribution of the value-weight distribution, generated by the observed data, to approximate the parameters that are needed for us. In particular, we are interested in the mean of the value and the marginal distribution of the weight of each item, as all the proposed algorithms, (i.e., OPT-S-MCKP, FR-S-MCKP, and G-S-MCKP) use them in order to calculate the next item to choose. Given this, let ˆµk,t denote the average of the values observed for item k at time step t (not including the value that is revealed at time step t). In addition, let ˆ pk,t(w) denote the empirical probability. Having these approximations, the algorithms proposed in Section 4 can be applied to the setting of unknown value-weight distribution as follows:

Initialisation: We set t = 1 and ct = C. Let ALG denote either OPT-S-MCKP, FR-S-MCKP, and G-S-MCKP, respectively. We randomly choose one item to put in to the knapsack. If we exceed either the time or capacity constraint then STOP, otherwise we update t = t + 1 and ct = C - w where w is the weight of the randomly chosen item. We also update ˆµk,t and ˆ pk,t(w) for each k and w, and GOTO next phase 2 .

Iterative steps:

1. We run ALG with the current set of {ˆµk,t}Kk=1 and {ˆ pk,t(w)}k,w.
2. If ALG stops (due to exceeding a constraint) then STOP, otherwise t = t + 1 and ct = ct - w where w is the weight of the currently chosen item, update {ˆµk,t}Kk=1 and {ˆ pk,t(w)}k,w, and GOTO Step 1.

2 Note that FR-S-MCKP also needs to maintain ˆ νk,t, the average weight of each item k. However, this can be easily calculated from ˆ pk,t(w) by taking the weighted average of the weights.

5.2 Performance Analysis of the Algorithms

We now turn to the performance analysis of the algorithms within the setting of unknown value-weight distributions. Let K∗ = argmaxk µk νk , and recall that V and W are the upper bounds of all the values and weights, respectively. We state the following theorems:

Theorem 2 The performance loss of OPT-S-MCKP without the prior knowledge of the value-weight distribution, compared to that of a best possible algorithm, is at most

Theorem 3 The performance loss of FR-S-MCKP without the prior knowledge of the value-weight distribution is at most

Again, we omit the proofs due to space limitations. However, they can be sketched as follows. By using the AzumaHoeffding and Dvoretzky-Kiefer-Wolfowitz inequalities, we can provide upper bounds on the estimation error of ˆµk,t and ˆ pk,t(w), respectively. Using similar techniques from the proof of Theorem 1 with some other technical algebrae, we get an upper bound on the step-wise losses. By summing these bounds, we obtain the desired results.

As we can see, both OPT-S-MCKP and FR-S-MCKP can achieve ˜O(√T) performance loss (again, the logarithmic terms are hidden in the notation ˜O), which is sub-linear. This guarantees the desired efficiency of the algorithms. On the other hand, similarly to the case of having full knowledge of the value-weight distributions, we do not have any performance guarantees for G-S-MCKP when it is applied to the setting of unknown value-weight distributions. However, as we will demonstrate in the next section, this algorithm can still performwell in practice, compared to its counterparts.

6 Numerical Evaluations

Given the theoretical analysis of the algorithms, we now turn to the empirical evaluation of the proposed algorithms. The main reason behind having this is that we want to investigate whether G-S-MCKP, which does not have theoretical performance guarantees, can provide good performance, compared to that of the other two methods. To do so, we conduct a set of numerical simulations. In these simulations, the values of each item are sampled from the set {10, 15, 20, · · · , 55} and the weights of each item are from {5, 10, 15, · · · , 50}. We set the number of items per time step to be 50, and we generate the value-weight distributions as follows. We take the following block of 10 value-weight distributions: Pk{vt(k) = 5(k + 1)} = p, Pk{wt(k) = 5k} = p, Pk{vt(k) = 5(i + 1)} = 1-p 9 , Pk{wt(k) = 5i} = 1-p 9 ∀i ∈ {1, 2, · · · , 10}\{k}, where k = 1, 2, . . . 10. By varying the value of p over the set {0.6, 0.5, 0.4, 0.3, 0.25}, we get 50 pairs of value-weight distributions. The capacity of the knapsack is 10000, and we run each experiment 100 times 3 .

Figure 1 depicts the results of the algorithms. In particular, Figures 1a and 1b show the performance of the algorithms in the cases of known and a priori unknown value-weight distributions, while Figure 1c shows the running time of the algorithms, respectively. As we can see, OPT-S-MCKP performs the best, while FR-S-MCKP and G-S-MCKP achieve very close performance to that of OPT-S-MCKP in both cases. In particular, we can observe that FR-S-MCKP is slightly better than G-S-MCKP. This is due to the fact that the fractional relaxation technique typically provides better approximation, compared to the fixed item greedy approach [Kellerer et al., 2004]. As FR-S-MCKP converges to the former and G-SMCKP converges to the latter, FR-S-MCKP indeed has better performance. We can also observe that the performance of the algorithms in the unknown distributions case is slightly worse than in its known distributions counterpart. This is due to the estimation errors of the distributions. However, as these errors typically converge to 0 in a fast manner, the performance loss we obtain by moving from known distributions to the unknown case is also small. In terms of running time (see Figure 1c), G-S-MCKP achieves the most efficient computational running time that is faster than that of the others by up to an order of magnitude of 2.5 (compared to the running time of FR-S-MCKP) and 4 (compared to OPT-S-MCKP), respectively. In addition, FR-S-MCKP is faster than OPT-S-MCKP by up to a magnitude of 2. Thus, this results demonstrate that both FR-S-MCKP and G-S-MCKP can achieve near optimal performance with significantly less computational cost, com-

3 We have also run additional experiments with different parameter settings. However, due to page limitations, we ignore the details of those results, as they show similar results on a broad view.

7 Conclusions

In this paper we provide a comprehensive analysis of SMCKP, the stochastic multiple-choice knapsack problem. In particular, we proposed OPT-S-MCKP, an optimal algorithm for the case when the value-weight distributions are known. We also proved that this algorithm can achieve ˜O(√T) performance loss when these distributions are not known a priori. We also developed two computationally efficient approximation algorithms, FR-S-MCKP and G-S-MCKP. The former can provably achieve ˜O(√T) performance loss for both known and unknown distribution scenarios. On the other hand, while G-S-MCKP does not have rigorous theoretical performance guarantees, we demonstrated that it can still achieve good performance (i.e., comparable with the other two methods) with a significantly lower computational cost. As a result, these approximation algorithms can be used in many real-world applications where both low computational cost and high performance are key requirements.

As a possible future work, we aim to provide theoretical performance guarantees for G-S-MCKP, as our conjecture is that it can also achieve ˜O(√T) performance guarantee. However, this is not trivial as our current techniques are not suitable for tackling this problem. In particular, it is essential to estimate how bad a decision of G-S-MCKP at each time step is, compared to that of the optimal algorithm.

8 Acknowledgement

We gratefully acknowledge funding from the UK Research Council for project 'ORCHID', grant EP/I011587/1.