Online Primal-Dual Algorithms For Stochastic Resource Allocation Problems

The resource allocation problem (RAP) [2] is to find the best allocation of a fixed amount of resources to various activities, in order to maximize the total revenue. The online RAP has a wide range of applications such as network routing [7], computer resource allocation [19], Internet advertising [24], portfolio selection [14] and so on. This paper studies a multi-dimensional online RAP with uncertainty. There are $m$ resources and $k$ resource consumption schemes for each request. The request for the resources arrives one by one. When the $i$-th request is revealed, one or none of $k$ resource consumption schemes is chosen to satisfy this request. If $l$-th resource consumption scheme is chosen, the revenue and the consumption of the $j$-th resource are $c_{tl}$ and $a_{tjl}$ respectively. The decision is irrevocable and has to be decided immediately according to the historical information $\{(\bm{c}_{\tau},\bm{A}_{\tau})\}_{\tau=1}^{t}$, without future information. Our aim is to maximize the total revenue with limited resource capacities, given the total number $n$ of incoming requests and considering the uncertainty of $a_{tjl}$.

This paper models the uncertainty with chance constraints and conditional expectation constraints. On one hand, a number of studies such as [23, 30, 29, 11] have applied the offline chance constrained resource allocation model into engineering fields. Some of these fields are better suited for applying online models. Taking [23] as an example, Lu et al. studied a offline planning model for selecting non-profit operations in a hospital considering the uncertainty of resource consumption. It is an online problem in practice since the decision must be made immediately when a operation request is arrived. On the other hand, the online chance constrained resource allocation model can be applied to the order fulfillment task, which is an important application in the field of the supply chain. In the order fulfillment problem, each order needs to be allocated to a transportation channel which will be delivered from the origin to the destination [27]. The goal is to maximize the total revenue while ensuring the average transportation time does not suppress the given threshold. We refer this average transportation time constraint as the timeliness constraint. A long delivery time highly impairs the customer’s experience. Consequently, timeliness constraint upper bound are often adopted to guarantee the relatively low average transportation time. Due to the complicacy of the transportation process, the transportation time of each channel is attained by prediction and has uncertainty. As far as we know, this is the first work to take both chance constraints and conditional expectation constraints into the consideration for the online RAP.

The deterministic RAP can be modeled as an integer linear programming (ILP) problem. Many recent papers have studied the online ILP problems (see [25, 21, 1, 13, 10, 3, 12, 20] and references therein). Algorithms in [25, 21, 1, 13, 10, 3, 12, 20] are all dual-based which maintain dual prices in iterations and can achieve near-optimal solutions under mild conditions. When a new request arrives, the decision is made immediately based on the dual price vector. Among these studies, researchers [25, 21, 1, 13, 10] construct dual problems by using historical information and solving them to obtain the dual prices. To deal with the disadvantage that solving dual problems may be time-consuming, researchers [3, 12, 20] propose online primal-dual (OPD) algorithms that update the dual prices by utilizing the dual mirror descent or projected stochastic subgradient descent. It is worth to mention that these OPD algorithms are simple and efficient since the dual prices are updated through algebraic computation without solving optimization problems.

However, the optimization models studied in [25, 21, 1, 13, 10, 12, 18, 20, 3] are deterministic and may suffer from poor performance when the resource consumption is uncertain in practice. In the existing articles that study the uncertain online optimization, the uncertainty is modeled by the worst-case scenario value, expectation, regret, or a linear combination of the above (see [5, 4, 16, 22, 17]). These modeling methods are mainly aimed at the uncertainty in the objective function, while almost no chance constraint or conditional expectation constraint is considered in the existing studies.

Chance constrained programming [8] is a widely used stochastic programming technique to model the uncertainty in constraints. In stochastic programming [28], it is assumed that some parameters are uncertain and their distributions are known. If the uncertain parameters in an active inequality constraint are set to the medians, the probability of this constraint not holding is 50%. To avoid this issue in the online RAP, this paper adopts the chance constraints to model the uncertainty. The chance constraint is the constraint on the uncertain parameters whose holding probability is not lower than the prescribed level. The solution methods for chance constrained programming (CCP) have been studied by [8, 15, 9, 26]. If the uncertain parameters have a known multivariate Gaussian distribution, the chance constrained counterparts of linear constraints can be transformed into deterministic second-order cone (SOC) constraints.

The conditional expectation constraint [26] can be served as a supplement to chance constraints, since the chance constraint does not restrict the amount of the violation of inequality constraints directly. In some cases, the expected amount of violation can be large even if the chance constraints are satisfied. To address this concern, the conditional expectation constraint is also taken into consideration in this paper. Similar to chance constraints, the conditional expectation constraints can also be transformed into deterministic SOC constraints under the assumption of multivariate Gaussian distribution [26].

This paper studies the online stochastic RAP considering the uncertainty of resource consumption coefficients. The chance constraint and conditional expectation constraint are used to model the uncertainty and both of them can be transformed into the SOC constraints equivalently. The non-linearity and indecomposability of the SOC constraints make the online problem challenging to handle. The main contributions of this paper are as follows.

1. (1)

   To the best of our knowledge, this is the first time chance constraints and conditional expectation constraints are introduced in the online RAP. A linearization method is presented to transform the SOC constrained problem into a linear form suitable for the online solution.

2. (2)

   We theoretically analyze the performance of the vanilla OPD algorithm when it is applied to solve the linearized stochastic RAP. Under mild technical assumptions, the expected optimality gap and constraint violation are both $O(\sqrt{n})$.

3. (3)

   We propose modified versions of the OPD approach by leveraging the structure of the SOC constraints to effectively reduce the probability deviation of chance constraints and the constraint violation of conditional expectation constraints in practice.

4. (4)

   Massive numerical experiments are conducted to demonstrate the applicability and effectiveness of the proposed algorithms.

The rest of this paper is organized as follows. Section 2 formulates the stochastic programming model of RAP and its linear relaxation. Section 3 introduces the proposed heuristic corrections and modified OPD algorithms for solving stochastic RAPs. Section 4 gives the numerical experiment results. Finally in Section 5, conclusions are drawn.

Consider the multi-dimensional RAP with $n$ requests and $m$ resources. For each request, there are always $k$ resource consumption schemes that can satisfy it. When a request is revealed, the decision maker chooses one scheme or none. Without loss of generality, a deterministic multi-dimensional RAP can be modeled as follows:

where the revenue coefficient vector $\bm{c}_{t}\in\mathbb{R}^{k}$, and the resource consumption vector $\bm{a}_{tj}\in\mathbb{R}^{k}$. The decision variables are $\bm{x}=(\bm{x}_{1},\dots,\bm{x}_{n})^{\top}$. $x_{tl}=1$ means that $t$-th request is satisfied by resource consumption scheme $l$. $b_{j}$ is the capacity of resource $j$. $\bm{1}$ denotes all-one vector. In the online setting of ILP, the input data $(\bm{c}_{t},\bm{a}_{t1},\dots,\bm{a}_{tm})$ is revealed one by one and $\bm{x}_{t}$ is determined instantaneously when $(\bm{c}_{t},\bm{a}_{t1},\dots,\bm{a}_{tm})$ is revealed.

Throughout this paper, we assume that the input data of deterministic problem and stochastic programming problem is drawn i.i.d. from some distributions. Moreover, $n$ and $\bm{b}$ are assumed to be known and fixed.

In practice, the value of $\bm{a}_{tj}$ may be obtained by predicting that yields the uncertainty. Consequently, taken the uncertainty of $\bm{a}_{tj}$ into consideration, we formulate the following chance constraints:

where $\mathbb{P}$ means probability, $\eta_{j}$ is the given confidence level and $\mathcal{P}_{a}$ is the distribution of $\bm{a}_{tj}$.

The constraints (2) only restrict the probability of violating inequality and do not restrict the amount of violation directly. To address this issue, the conditional expectation constraints (3) are also considered in this paper which can limit the expected violation of these inequality constraints.

where $\mathbb{E}$ denotes expectation and $\gamma_{j}$ is the given parameter. This paper assumes that the expectation in (3) always exists.

Replacing the deterministic constraints in (1) by the chance constraints (2) and conditional expectation constraints (3), we formulate the following stochastic programming problem:

For convenience, we refer to the problem (4) as a CCP problem throughout this paper, thought (3) are not standard chance constraints.

In the online setting of the CCP problem (4), the revenue vector $\bm{c}_{t}$ and the distributions of the resource consumption vectors $\{\bm{a}_{t1},\dots,\bm{a}_{tm}\}$ are revealed one by one. For any $t$ and $j$, we assume that $\bm{a}_{tj}\sim N(\bar{\bm{a}}_{tj},\bm{K}_{tj})$ which means the true value of $\bm{a}_{tj}$ belongs to a known Gaussian distribution with mean $\bar{\bm{a}}_{tj}$ and covariance matrix $\bm{K}_{tj}$. In the following, we will reformulate (4) into a deterministic problem.

First is to reformulate the chance constraints (2). According to the properties of Gaussian distribution, we have that $\sum_{t=1}^{n}\bm{a}_{tj}^{\top}\bm{x}_{t}\sim N(\sum_{t=1}^{n}\bar{\bm{a}}_{tj}^{\top}\bm{x}_{t}$, $\sum_{t=1}^{n}\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t})$. Thus, the constraints (2) are equivalent to the following constraints [15]:

where $\Phi(\cdot)$ represents the cumulative distribution function of the standard Gaussian distribution.

Next is to reformulate the conditional expectation constraints (3). The value of the conditional expectation $\mathbb{E}[\sum_{t=1}^{n}\bm{a}_{tj}^{\top}\bm{x}_{t}-b_{j}|\sum_{t=1}^{n}\bm{a}_{tj}^{\top}\bm{x}_{t}-b_{j}>0]$ is related to the variance $\sqrt{\sum_{t=1}^{n}\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t}}$, which makes the parameter $\gamma_{j}$ difficult to quantify. As an alternative, we replace $\gamma_{j}$ with the normalized value $\tilde{\gamma}_{j}$ that equals to $\gamma_{j}/\sqrt{\sum_{t=1}^{n}\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t}}$. Specifically, the constraint (3) is rewritten as

According to [26], the constraints (6) are equivalent to

where the function $h(\cdot)$ has the form¹¹1In [26], $\sqrt{\cdot}$ in $\sqrt{2\pi}$ is left out which is a typo.

Under the assumption of Gaussian distribution, the constraints (5) and (7) have the same formulations and the only difference lies on the coefficient of $\sqrt{\sum_{t=1}^{n}\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t}}$. Consequently, when both (5) and (7) exist, we can merge them into the following constraint,

where $\psi_{j}=\max\{\Phi^{-1}(\eta_{j}),h^{-1}(\tilde{\gamma}_{j})\}$. When $\eta_{j}>50\%$ or $\tilde{\gamma}_{j}<\sqrt{\pi/2}$, $\psi_{j}>0$.

Substituting (9) into (4), the CCP problem (4) is equivalent to the following deterministic problem:

The problem (10) is an integer SOC programming (ISOCP) problem when $\psi_{j}>0,\forall j$. The offline version of (10) can be solved by commercial solvers such as Gurobi. However, in the online setting, it is difficult to solve problem (10) due to its indecomposability: $\bm{x}_{t}$ with different subscripts $t$ are coupled with each other in $\sqrt{\sum_{t=1}^{n}\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t}}$. In other words, calculating the individual constraint consumption at each time step $t$ is challenging. Moreover, we make the following assumption throughout this paper.

To begin, we provide the following proposition.

To address the non-decomposable issue raised by the non-linearity of $\sqrt{\sum_{t=1}^{n}\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t}}$, we linearize this term to decouple different $\bm{x}_{t}$. Specifically, according to Cauchy-Schwarz inequality $\sqrt{n\sum_{t=1}^{n}\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t}}\geq\sum_{t=1}^{n}$ $\sqrt{\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t}}$ and Proposition 1, the nonlinear and non-decomposable problem (10) can be approximated by

It is worth to mention that the relaxed problem (11) is an integer LP (ILP) problem which is linear and decomposable, and can be solved in the online setting by existing algorithms. The vanilla OPD algorithm for solving this relaxed problem is the basis of our algorithms for solving the CCP problem (10) and we will detail it in the following section.

Recall that (11) is an ILP problem and Li et al. [20] have proposed an effective OPD algorithm to solve the online ILP problem. For simplicity, denote $\tilde{\bm{a}}_{tj}=\bar{\bm{a}}_{tj}+{\psi_{j}}\bm{\gamma}_{tj}{/\sqrt{n}}$ and we present the OPD method as shown in Algorithm 1.

In Algorithm 1, we denote $\tilde{\bm{A}}_{t}=(\tilde{\bm{a}}_{t1}^{\top},\dots,\tilde{\bm{a}}_{tm}^{\top})^{\top}$, $\bm{b}=(b_{1},\dots,b_{m})^{\top}$ and $\bm{x}_{t}=(x_{t1},\dots,x_{tk})^{\top}$. Algorithm 1 is a dual-based algorithm which maintains a dual vector $\bm{p}_{t}$. In each round $t$, $\bm{c}_{t}$ and $\tilde{\bm{A}}_{t}$ are revealed. Then, $\bm{x}_{t}$ is determined immediately by choosing $l$ that maximizes $(\bm{c}_{t}^{\top}-\bm{p}_{t}^{\top}\tilde{\bm{A}}_{t})\bm{e}_{l}$, where $\bm{e}_{l}\in\mathbb{R}^{k}$ and $\bm{e}_{l}$ is the unit vector with $l$-th coordinate being $1$. After determining $\bm{x}_{t}$, $\bm{p}_{t}$ is updated by a projected stochastic subgradient descent method where $(\bm{d}-\tilde{\bm{A}}_{t}\bm{x}_{t})$ is the subgradient corresponding to $\bm{p}_{t}$. Li et al. [20] have shown that Algorithm 1 provides a near-optimal solution of the problem (12) that is the linear relaxation of (11), as stated in Theorem 1.

Theorem 1 states the upper bound of the expected optimality gap and the expected constraint violation, which are both $O(\sqrt{n})$. Then, we provide the lower bound of the expected optimality gap in the following theorem.

Next, we will analysis the performance of Algorithm 1 compared to the optimal solution of the ISOCP problem (10). The linear relaxation of the ISOCP problem (10) is

where the binary variables are relaxed into continuous variables on $[0,1]$. The optimal objective values of the ISOCP problem (10) and SOCP problem (16) are referred to as $\hat{R}_{n}^{ISOCP}$ and $\hat{R}_{n}^{SOCP}$, respectively. Then, we establish the optimality gap between the LP problem (12) and SOCP problem (16), and the constraint violation in the following lemma.

As shown in Lemma 1, both the optimal gap and the constraint violation between the LP problem (12) and SOCP problem (16) are $O(\sqrt{n})$. Then, putting Theorem 1, Theorem 2, and Lemma 1 together, we can obtain that the expected optimality gap and constraint violation compared to the optimal solution of the SOCP problem (16) in Theorem 3.

Moreover, inequality $\hat{R}_{n}^{ISOCP}\leq\hat{R}_{n}^{SOCP}$ holds due to the fact that the SOCP problem (16) is the linear relaxation of the ISOCP problem (10). Thus, Algorithm 1 achieves $O(\sqrt{n})$ regret and constraint violation compared to the optimal solution of the ISOCP problem (10) as stated in Theorem 4.

Although Algorithm 1 has been able to obtain a near-optimal solution of the ISOCP problem (10) according to Theorem 4, its practical performance can be further improved by narrowing the gap between the solutions generated by Algorithm 1 and the offline ISOCP (10). To be specific, this gap mainly comes from the following two points:

1. (a)

   The error between the offline ILP problem (11) and the offline ISOCP problem (10).

2. (b)

   The error between the online solution and offline solution of the ILP problem (11).

To address these issues, we propose two modified OPD algorithms (Algorithms 2 and 3) to solve the online CCP problem (10). In Algorithm 2, a heuristic correction is applied to correct the error (a). For the $j$-th constraint, we introduce scale factors

to reduce the gap between $\sqrt{\sum_{t=1}^{n}\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t}}$ and $\sum_{t=1}^{n}{\bm{\gamma}_{tj}^{\top}\bm{x}_{t}}$ $/{\sqrt{n}}$. Intuitively speaking, recalling that in section 2.4 we utilize Cauchy-Schwarz inequality to linearize the non-decomposable problem (10), equation (23) can be regarded as the empirical correction for the non-decomposable term $\sqrt{(t-1)\sum_{i=1}^{t-1}\bm{x}_{i}^{\top}\bm{K}_{ij}\bm{x}_{i}}$ with the linear term $\sum_{i=1}^{t-1}\gamma_{ij}^{\top}\bm{x}_{i}$.

Define

As shown in Algorithm 2, $\hat{\bm{A}}_{t}(\bm{\beta_{t}})$ is used in place of $\tilde{\bm{A}}_{t}$. That is, we use the expression $\sum_{t=1}^{n}\beta_{tj}\bm{\gamma}_{tj}^{\top}\bm{x}_{t}/\sqrt{n}$ to approximate $\sqrt{\sum_{t=1}^{n}\bm{x}_{t}^{\top}\bm{K}_{tj}\bm{x}_{t}}$. In round $t$, $\bm{\beta}_{t}$ is calculated according to (23) which is based on the historical decisions and will be used in the next iteration for correction. It is worth noting that $\bm{\beta}_{t}=(\beta_{t1},\dots,\beta_{tm})^{\top}$ is calculated in each round and can be computed incrementally with low computational cost.

In the numerical experiments section 4, it is illustrated that Algorithm 2 has better performance than Algorithm 1 in terms of the constraint violation. An intuitive explanation is that Algorithm 2 is more inclined to reject the orders with high uncertainty of resource consumption (i.e., $\bm{K}_{tj}$) than Algorithm 1 because $\bm{\beta}_{t}\geq\bm{1}$.

Next, we will propose another algorithm to correct the error (b). The error (b) consists of two parts, the optimality gap and constraint violation. In most cases, compared with the optimality gap, the CCP problems have a lower tolerance for the constraint violation, since the constraint violation will cause the probability

or the conditional expectations

to deviate from their set values. For instance, if the confidence level of a chance constraint is set to 90% but the actual confidence level of the online solution is 60%, this online solution is unacceptable.

For the online LP problem, Li et al. [20] have proposed a variant of the OPD algorithm that can reduce the amount of the constraint violation in practice. It is a non-stationary algorithm in which the resource consumption is considered while doing the subgradient descent. Specifically, instead of using the static average consumption $\bm{d}=\bm{b}/n$, the time-varying $\bm{d}_{t}$ calculated by the formula (28) is utilized in Line 9 of Algorithm 1.

Inspired by the above non-stationary method, we propose the following formula to dynamically adjust the right-hand-side capacity $\bm{d}$ in each round:

where

Then, we obtain Algorithm 3 by merging the correction formula (29) into Algorithm 2. The intuition behind the correction formula (29) is given as follows: if too many resources are spent in the early rounds, the remaining resources will diminish. Then Algorithm 3 will raise the dual price and be more likely to reject an order with high resource consumption as a result. On the other hand, if a large number of orders with high resource consumption are rejected at the start, resulting in an excess of remaining resources, Algorithm 3 will decrease the dual price in order to accept more orders in the future. This correction strategy makes Algorithm 3 perform better than Algorithms 1 and 2 in numerical experiments.

In the first subsection, we apply the proposed algorithms to the classic CCP problem which does not contain the conditional expectation constraints (3). Algorithm 1, Algorithm 2, Algorithm 3 and Algorithm 3 without correction (23) are compared in terms of optimality gap and probability deviation. These algorithms are implemented on two different models. Table 1 lists the distributions from which the elements in $\bm{c}_{tj}$, $\bm{\bar{a}}_{tj}$ or $\bm{K}_{tj}$ are i.i.d. sampled. $f(\chi^{2}(v))$ denotes $X=f(Y)$ and $Y\sim~{}\chi^{2}(v)$. The uniform distribution is bounded while the chi-square distribution is unbounded. In other words, the CCP problems in Experiment I satisfy Assumption 1 but the CCP problems in Experiment II do not.

In this subsection, we apply the proposed algorithms to the CCP problem with only conditional expectation constraints and compare the performance in terms of the normalized constraint violation and the constraint violation. The input data are the same as these in Section 4.1. The parameters $k$ and $m$ are also set to 5 and 4, and $\tilde{\gamma}_{j}$ in four conditional expectation constraints are set to 0.2, 0.3, 0.4 and 0.5, respectively. The scale of $\tilde{\gamma}_{j}$ matches the standard normal distribution: 0.2, 0.3, 0.4 and 0.5 correspond to 0.2, 0.3, 0.4 and 0.5 times the standard deviation, respectively.