Routing optimization with time windows under uncertainty

We study an a priori Traveling Salesman Problem with Time Windows (tsptw) in which the travel times along the arcs are uncertain and the goal is to determine within a budget constraint, a route for the service vehicle in order to arrive at the customers’ locations within their stipulated time windows as well as possible. In particular, service at customer’s location cannot commence before the beginning of the time window and any arrival after the end of the time window is considered late and constitutes to poor customer service. In articulating the service level of the tsptw under uncertainty, we propose a new decision criterion, called the essential riskiness index, which has the computationally attractive feature of convexity that enables us to formulate and solve the problem more effectively. As a decision criterion for articulating service levels, it takes into account both the probability of lateness and its magnitude, and can be applied in contexts where either the distributional information of the uncertain travel times is fully or partially known. We propose a new formulation for the tsptw, where we explicitly express the service starting time at each customer’s location as a convex piecewise affine function of the travel times, which would enable us to obtain the tractable formulation of the corresponding distributionally robust problem. We also show how to optimize the essential riskiness index via Benders decomposition and present cases where we can obtain closed-form solutions to the subproblems. We also illustrate in our numerical studies that this approach scales well with the number of samples used for the sample average approximation. The approach can be extended to a more general setting including Vehicle Routing Problem with Time Windows with uncertain travel times and customers’ demands.

The authors would like to thank the anonymous reviewers and associate editor for their extremely helpful suggestions and very thorough review of the paper. The first author is financially supported by the Chinese Scholarship Council, the National Research Foundation Singapore (NRF-RSS2016-004), and the National Natural Science Foundation of China (71725001). The third author is financially supported by Singapore Ministry of Education Social Science Research Thematic Grant (MOE2016-SSRTG-059). The last author is funded by the National Natural Science Foundation of China (71420107028, 91747105).

Disclaimer Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of the Singapore Ministry of Education or the Singapore Government.

Authors and Affiliations

1. School of Business Administration, Southwestern University of Finance and Economics, Chengdu, 611130, People’s Republic of China

   Yu Zhang

2. Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore, 119245, Republic of Singapore

   Yu Zhang

3. Department of Electrical, Electronic, and Information Engineering “Guglielmo Marconi” (DEI), University of Bologna, 47521, Cesena, Italy

   Roberto Baldacci

4. Department of Analytics and Operations, National University of Singapore, Singapore, 119245, Republic of Singapore

   Melvyn Sim

5. College of Management Science and Engineering, Dongbei University of Finance and Economics, Dalian, 116000, People’s Republic of China

   Jiafu Tang

Corresponding author

Correspondence to Roberto Baldacci.

Proofs of analytical results

1.1 Proof of Proposition 2

It has been established that the variable \(\varvec{s}^l\), \(l \in \mathcal {N}\), represents the partial route from node 1 to node l along the route determined by \(\varvec{x}\), say \(\{(1, i_2), (i_2, i_3)\), \(\ldots , (i_{\check{\kappa }-1}, \underbrace{i_{\check{\kappa }}}_{=l})\), \(\ldots , (i_{n - 1},\underbrace{ i_n}_{ = n})\}\) so that

(see, for instance, [24]). We have from Eq. (1) that the service commencement time at the node l can be determined recursively as follows,

Hence, we have

where \(k=i_{\hat{\kappa }}\) represents a node along the partial route from node 1 to node l.

Next we show that the service commencement time at node l can also determined by Eq. (2). For notational convenience, we define

for all \(k \in \underline{\mathcal {N}}\cup \{1\}\) and consider three cases as follows:

1. i)

   When \(k = 1\), we have \(\underline{\tau }_1 = 0\) and \(\varvec{s}^1 = \varvec{0}\) and hence, we have

   $$\begin{aligned} t^1_l = \displaystyle \sum _{a \in \delta ^-(1)} s^{l}_a \underline{\tau }_1 + \varvec{z}'(\varvec{s}^{l} - \varvec{s}^{1}) = \displaystyle \underline{\tau }_1 + \sum _{a \in \{ (1, i_2), (i_2, i_3), \ldots , (i_{\check{\kappa }- 1}, l) \}} z_a. \end{aligned}$$

   Moreover, \(t^1_l \ge 0\) because \(\varvec{z} \ge \varvec{0}\).

2. ii)

   When \(k \in \{i_2, i_3, \ldots , i_{\check{\kappa }- 1}, l\} \cap \underline{\mathcal {N}}\), we have \(\sum _{a \in \delta ^-(k)} s^{l}_a = 1\) and

   $$\begin{aligned} t^k_l = \displaystyle \sum _{a \in \delta ^-(k)} s^{l}_a \underline{\tau }_k + \varvec{z}'(\varvec{s}^{l} - \varvec{s}^{k}) = \underline{\tau }_k + \sum _{a \in \{ (k, i_{\hat{\kappa }+ 1}), (i_{\hat{\kappa }+ 1}, i_{\hat{\kappa }+ 2}), \ldots , (i_{\check{\kappa }- 1}, l) \}} z_a. \end{aligned}$$
3. iii)

   When \(k \in \{i_{\check{\kappa }+ 1}, i_{\check{\kappa }+ 2}, \ldots , n\} \cap \underline{\mathcal {N}}\), we have \(\sum _{a \in \delta ^-(k)} s^{l}_a = 0\) and \((\varvec{s}^{l} - \varvec{s}^{k}) \le \varvec{0}\). Since \(\varvec{z} \ge \varvec{0}\), we have

   $$\begin{aligned} t^k_l = \sum _{a \in \delta ^-(k)} s^{l}_a \underline{\tau }_k + \varvec{z}'(\varvec{s}^{l} - \varvec{s}^{k}) \le 0 \le t^1_l. \end{aligned}$$

   Hence, \(\max \{ t^1_l,t^k_l \} = t^1_l\) for all \(k \in \{i_{\check{\kappa }+ 1}, i_{\check{\kappa }+ 2}, \ldots , n\} \cap \underline{\mathcal {N}}\).

Observe that we can express Eq. (2) as

We note that for all \(k \in \{i_2, i_3, \ldots , i_{\hat{\kappa }- 1}, l\} \backslash \underline{\mathcal {N}}\) we have \(\underline{\tau }_k = 0\) and since \(\varvec{z} \ge \varvec{0}\), we also have

Hence, \(\max \{ t^1_l,t^k_l \} = t^1_l\) for all \(k \in \{i_2, i_3, \ldots , i_{\check{\kappa }- 1}, l\} \backslash \underline{\mathcal {N}}\). Therefore, taking these conditions into account, we have shown the equivalence of Eqs. (34), (35) and (2).

1.2 Proof of Proposition 3

1. i)

   Satisficing: If \(\mathbb {P}\left( \tilde{\xi } \le 0 \right) =1\), then \(\displaystyle \mathbb {E}_{\mathbb {P}}\left( \max \{\tilde{\xi }, -\alpha \}\right) \le 0\) for all \(\alpha \ge 0\) and \(\rho _E(\tilde{\xi }) = 0\). Conversely, if \(\rho _E(\tilde{\xi }) = 0\), we have \(\displaystyle \mathbb {E}_{\mathbb {P}}\left( \max \{\tilde{\xi }, 0\}\right) \le 0\), which implies \(\mathbb {P}\left( \tilde{\xi } \le 0 \right) =1\).

2. ii)

   Infeasibility: For any \(\alpha \in [0, \infty )\), if \(\displaystyle \mathbb {E}_{\mathbb {P}} \left( \tilde{\xi } \right) > 0\), then \(\displaystyle \mathbb {E}_{\mathbb {P}}\left( \max \{\tilde{\xi }, -\alpha \} \right) > 0\). However, the definition requires

   $$\begin{aligned} \displaystyle \mathbb {E}_{\mathbb {P}}\left( \max \{\tilde{\xi }, -\alpha \} \right) \le 0. \end{aligned}$$

   We conclude that \(\rho _E(\tilde{\xi }) = \min \emptyset = \infty \).

3. iii)

   Convexity: We denote \(\alpha _1^* = \rho _{E}\left( \tilde{\xi }_1\right) \) and \(\alpha _2^* = \rho _{E}\left( \tilde{\xi }_2\right) \). Hence, \(\mathbb {E}_\mathbb {P}\left( \max \{\tilde{\xi }_1, -\alpha _1^*\}\right) \le 0\) and \(\mathbb {E}_\mathbb {P}\left( \max \{\tilde{\xi }_2, -\alpha _2^*\}\right) \le 0\). Since the function \(\mathbb {E}_\mathbb {P}\left( \max \{\tilde{\xi }, -\alpha \}\right) \) is jointly convex in \(\tilde{\xi }\) and \(\alpha \), we have for \(\lambda \in [0,1]\),

   $$\begin{aligned} \begin{array}{rl} &{} \mathbb {E}_\mathbb {P}\left( \max \{\lambda \tilde{\xi }_1+(1-\lambda )\tilde{\xi }_2, -\left( \lambda \alpha _1^* + (1 - \lambda )\alpha _2^*\right) \}\right) \\ &{}\quad \le \lambda \mathbb {E}_\mathbb {P}\left( \max \{\tilde{\xi }_1, -\alpha _1^*\}\right) + (1 - \lambda ) \mathbb {E}_\mathbb {P}\left( \max \{\tilde{\xi }_2, -\alpha _2^*\}\right) \\ &{}\quad \le 0. \end{array} \end{aligned}$$

   Hence, \(\alpha _\lambda = \lambda \alpha _1^* + (1 - \lambda )\alpha _2^*\) satisfies \(\mathbb {E}_\mathbb {P}\left( \max \{\lambda \tilde{\xi }_1+(1-\lambda )\tilde{\xi }_2, -\alpha _\lambda \}\right) \le 0\) and \(\rho _{E}\left( \lambda \tilde{\xi }_1+(1-\lambda )\tilde{\xi }_2\right) \le \alpha _\lambda = \lambda \rho _{E}\left( \tilde{\xi }_1\right) +(1-\lambda )\rho _{E}\left( \tilde{\xi }_2\right) \).

4. iv)

   Delay bounds: The bound is true for \(\rho _E\left( \tilde{\xi }\right) = \infty \) and \(\rho _E\left( \tilde{\xi }\right) = 0\), since the latter would imply \(\mathbb {P}\left( \tilde{\xi } > 0 \right) =0\). For \(\rho _E\left( \tilde{\xi }\right) \in (0,\infty )\), we let \(\alpha ^* = \rho _E\left( \tilde{\xi }\right) \) and hence we have

   $$\begin{aligned} \begin{array}{rcl} \mathbb {P}\left( \tilde{\xi }>\alpha ^* \theta \right) &{}=&{} \displaystyle \mathbb {P}\left( \tilde{\xi } + \alpha ^*> \alpha ^*\theta + \alpha ^* \right) \\ &{}\le &{} \displaystyle \mathbb {P}\left( \left( \tilde{\xi } + \alpha ^* \right) ^+ > \alpha ^* (1 + \theta ) \right) \\ &{}\le &{} \displaystyle \frac{\mathbb {E}\left( (\tilde{\xi } + \alpha ^*)^+\right) }{ \alpha ^* (1 + \theta ) } \\ &{}\le &{} \displaystyle \frac{\alpha ^*}{\alpha ^* (1 + \theta )} \\ &{} = &{} \displaystyle \frac{1}{1+\theta }. \end{array} \end{aligned}$$

   The second inequality holds because of Markov inequality; the third inequality is due to \(\mathbb {E}_{\mathbb {P}}\left( \max \{ \tilde{\xi } + \alpha ^*, 0 \} \right) \le \alpha ^*\), implied by the definition.

1.3 Proof of Theorem 1

We denote \(\tilde{{\varvec{u}}} = \tilde{{\varvec{z}}} - \varvec{\mu }\) and rewrite the ambiguity set as

For each \(l \in \overline{\mathcal {N}}\), we determine the worse-case expectation

by formulating the following optimization problem:

Its dual problem is given as

for which strong duality holds and their objectives coincide (see, for instance, [23]). We express the first constraint in Problem (36) equivalently as

or further as

Similarly, we express the second constraint in Problem (36) equivalently as

Hence, the first constraint of Problem (10) is satisfied if and only if there exists \(v_{l0} \in \mathbb {R}\), \(\varvec{v}_l \in \mathbb {R}^{|\mathcal {A}|}\) and \(\varvec{V}_l \in \mathbb {R}^{|\mathcal {A}| \times |\mathcal {A}|}\) for \(l \in \overline{\mathcal {N}}\) that are feasible in the following system of conic constraints,

Substituting them in Problem (10), we obtain Problem (11).

1.4 Proof of Theorem 2

It suffices to show that for a given \(s_0 \in \mathbb {R}, \varvec{s} \in \mathbb {R}^{|\mathcal {A}|}, \varvec{s} \ne \varvec{0}, \alpha \ge 0\), the following constraints are feasible

for some \(v_0 \in \mathbb {R}, \varvec{v} \in \mathbb {R}^{|\mathcal {A}|}, \varvec{V} \in \mathbb {S}_+^{|\mathcal {A}| }\) if and only if

For the “if” direction, suppose the constraint (38) is feasible, since \(\varvec{s}'\varvec{\varSigma }'\varvec{s}>0\), we would have \(\alpha >0\) and \(\alpha - s_0> 0\). Let

Observe that for all \(\varvec{u} \in \mathbb {R}^{|\mathcal {A}|}\),

and

Moreover,

Hence, the constraints in (37) are also feasible.

Conversely, suppose the constraints in (37) are feasible for some \(v_0 \in \mathbb {R}, \varvec{v} \in \mathbb {R}^{|\mathcal {A}|}, \varvec{V} \in \mathbb {S}_+^{|\mathcal {A}| }\). Let

Note that since \(\varvec{s}\varvec{\varSigma }\varvec{s}>0\), we have \(r_0 \in (0,1)\). Observe that

since for all \(\varvec{w} \in \mathbb {R}^{|\mathcal {A}|}\),

and

Therefore,

or equivalently

Hence,

which implies the feasibility of the constraint (38).

1.5 Proof of Proposition 4

Denote the optimal solutions of Problem (14) with \(\varvec{s}\) being \(\varvec{\check{s}}\) and \(\varvec{\hat{s}}\) by \(\check{\alpha }_l\) and \(\hat{\alpha }_l\), respectively, so that \(F_l(\varvec{\check{s}}) = \check{\alpha }_l\) and \(F_l(\varvec{\hat{s}}) = \hat{\alpha }_l\). To prove the convexity of \(F_l(\varvec{s})\) by definition, we shall prove \(F_l(\lambda \varvec{\check{s}} + (1-\lambda ) \varvec{\hat{s}}) \le \lambda F_l(\varvec{\check{s}}) + (1-\lambda ) F_l(\varvec{\hat{s}})\) for any \(\lambda \in [0,1]\).

Observe that the left-hand side function of the first constraint in Problem (14), \(g(\varvec{s},\alpha _l) {=} \sup _{\mathbb {P}\in \mathbb {F}}\mathbb {E}_{\mathbb {P}} \left( \max \left\{ \max _{k \in \underline{\mathcal {N}}\cup \{1\}} \left\{ \sum _{a \in \delta ^-(k)} s^{l}_a \underline{\tau }_k + \tilde{{\varvec{z}}}^\prime (\varvec{s}^{l} {-} \varvec{s}^{k}) \right\} - \overline{\tau }_l, - \alpha _l \right\} \right) \), is convex piecewise affine in \((\varvec{s},\alpha _l)\). We then have, for any \(\lambda \in [0,1]\),

Also note that \(\lambda \check{\alpha } + (1-\lambda ) \hat{\alpha } \ge 0\). Hence, \(\lambda \check{\alpha } + (1-\lambda ) \hat{\alpha }\) is a feasible solution to Problem (14) with \(\varvec{s}\) being \(\lambda \varvec{\check{s}} + (1-\lambda ) \varvec{\hat{s}}\). As a result,

This completes the proof.

1.6 Proof of Theorem 3

We specify the dual problem of Problem (17) as follows,

which we claim is equivalent to the following problem,

We next prove the claim. For an optimal solution \((\psi , \varvec{r}, \varvec{q})\) to Problem (39), we infer from the first and the fifth constraints that \(\psi \ge \sum _{k \in \underline{\mathcal {N}}\cup \{1\}} r^{\omega }_k\), \(\forall \omega \in \varOmega \), and therefore, \(q^{i} = \psi - \sum _{k \in \underline{\mathcal {N}}\cup \{1\}} r^{i}_k \ge \sum _{k \in \underline{\mathcal {N}}\cup \{1\}} r^{\omega }_k - \sum _{k \in \underline{\mathcal {N}}\cup \{1\}} r^{i}_k\), \(\forall i, \omega \in \varOmega \). This inequality and the second constraint in Problem (39) imply that \(|\varOmega | \sum _{k \in \underline{\mathcal {N}}\cup \{1\}} r_k^{\omega } - \sum _{k \in \underline{\mathcal {N}}\cup \{1\}} \sum _{i \in \varOmega } r_k^{i} \le 1, \forall \omega \in \varOmega \). Hence, the solution \(p^\omega := \sum _{k \in \underline{\mathcal {N}}\cup \{1\}} r_k^{\omega }\), \(\forall \omega \in \varOmega \), is clearly feasible in Problem (40). Since, by definition \(\xi _l^\omega (\varvec{s}) = \max _{k \in \underline{\mathcal {N}}\cup \{1\}} \xi _{lk}^{\omega }(\varvec{s})\), it follows that \(\check{F}_l(\varvec{s}) \ge \hat{F}_l(\varvec{s})\). Conversely, for an optimal solution \(\varvec{p}\) to Problem (40), we construct a solution to Problem (39) as follows. Let \(r_{\kappa ^*(\omega )}^\omega := p^{\omega }\) for all \(\omega \in \varOmega \) where \(\kappa ^*(\omega ) \in {{\mathrm{arg\,max}}}_{k \in \underline{\mathcal {N}}\cup \{1\}} \xi _{lk}^{\omega }(\varvec{s})\), \(r_k^\omega := 0\) for all \(\omega \in \varOmega \) and \(k \in \underline{\mathcal {N}}\cup \{1\}\backslash \{\kappa ^*(\omega )\}\), \(\psi := \max _{\omega \in \varOmega } p^{\omega }\), and \(q^\omega := \max _{i \in \varOmega } p^{i} - p^{\omega }\) for all \(\omega \in \varOmega \). We can verify that the solution is feasible and the objective value is equal to \(\check{F}_l(\varvec{s})\). In particular, Constraint \(\sum _{\omega \in \varOmega }q^\omega \le 1\) is feasible since \(|\varOmega | p^{\omega } - \sum _{i \in \varOmega } p^{i} \le 1\) for all \(\omega \in {{\mathrm{arg\,max}}}_{i \in \varOmega } p^i\). Hence, \(\hat{F}_l(\varvec{s}) \ge \check{F}_l(\varvec{s})\). We then conclude that \(\hat{F}_l(\varvec{s}) = \check{F}_l(\varvec{s})\) and the two problems are equivalent. Observe that \(\varvec{0}\) is a feasible solution to Problem (40); the problem then can be bounded optimal or unbounded. Since strong duality holds for linear programming problems, we also have \(\hat{F}_l(\varvec{s}) = F_l(\varvec{s})\).

We next solve Problem (40). The problem is unbounded if and only if there exists a recession direction \(\varvec{p} \not = \varvec{0}\), \(|\varOmega | p^{\omega } - \sum _{i \in \varOmega } p^{i} \le 0\) and \(p^{\omega } \ge 0\) for \(\omega \in \varOmega \), such that \(\sum _{\omega \in \varOmega }\xi _l^{\omega }(\varvec{s}) p^{\omega } > 0\). The recession direction should satisfy \(p^1 = p^2 = \cdots = p^{|\varOmega |} > 0\), or otherwise the constraint \(|\varOmega | p^{\omega } - \sum _{i \in \varOmega } p^{i} \le 0\) would be violated for all \(\omega \in {{\mathrm{arg\,max}}}_{i \in \varOmega } p^i\). Hence, the condition \(\sum _{\omega \in \varOmega }\xi _l^{\omega }(\varvec{s}) p^{\omega } > 0\) is equivalent to \(\sum _{\omega \in \varOmega } \xi _l^{\omega } (\varvec{s})> 0\), and in which case, the problem is unbounded and \(F_l(\varvec{s})=\infty \).

If the problem is bounded and optimal, there exists an optimal extreme point solution, which is determined by selecting \(|\varOmega |\) binding constraints in Problem (40). Observe that for a given \(\omega \in \varOmega \) the constraints \(p^\omega \ge 0\) and \(|\varOmega | p^{\omega } - \sum _{i \in \varOmega } p^{i} \le 1\) cannot be simultaneously binding because it would imply that \(- \sum _{i \in \varOmega \backslash \{\omega \}} p^{i} = 1\), which contradicts with the nonnegativity of \(\varvec{p}\). Hence, partition \(\varOmega \) into two subsets \(\varOmega _1\) and \(\varOmega _2\), such that \(|\varOmega | p^{\omega } - \sum _{i \in \varOmega } p^{i} = 1\), \(\forall \omega \in \varOmega _1\) and \(p^{\omega } = 0\), \(\forall \omega \in \varOmega _2\). When \(\varOmega _1 = \emptyset \), we have \(\varvec{p} = \varvec{0}\) being an extreme point with objective value of zero. We also note that \(|\varOmega _1| = |\varOmega |\) is inadmissible because we would have \(\sum _{\omega \in \varOmega } (|\varOmega | p^{\omega } - \sum _{i \in \varOmega } p^{i}) = \sum _{\omega \in \varOmega } 1\), which is a contradiction unless \( |\varOmega |=0\). When \(1 \le |\varOmega _1| \le |\varOmega | - 1\), we solve for the system of linear equations, \(|\varOmega | p^{\omega } - \sum _{i \in \varOmega } p^{i} = 1\), \(\forall \omega \in \varOmega _1\), or equivalently, \((|\varOmega | \varvec{I} - \varvec{e} \varvec{e}')\varvec{p} = \varvec{e}\), where \(\varvec{I}\) is the unit diagonal matrix in \(\mathbb {R}^{|\varOmega _1| \times |\varOmega _1|}\), \(\varvec{p} = (p^{\omega })'_{\omega \in \varOmega _1}\), and \(\varvec{e}\) is the vector of ones in \(\mathbb {R}^{|\varOmega _1|}\). Observe that \( \varvec{p} = \frac{1}{|\varOmega | - |\varOmega _1|} \varvec{e} \) is a feasible solution. Moreover, it is the unique solution because \((|\varOmega | \varvec{I} - \varvec{e} \varvec{e}')\) is invertible and we can verify that \((|\varOmega | \varvec{I} - \varvec{e} \varvec{e}') (\frac{1}{|\varOmega |} \varvec{I} + \frac{1}{|\varOmega | (|\varOmega | - |\varOmega _1|)} \varvec{e} \varvec{e}') = \varvec{I}\). Hence, \(p^{\omega } = \frac{1}{|\varOmega | - |\varOmega _1|}\), \(\forall \omega \in \varOmega _1\) and \(p^\omega = 0\), \(\forall \omega \in \varOmega _2\) is an extreme point solution. Observe that at optimality, \(\varOmega _1\) would correspond to the set \(\{\nu (1), \nu (2), \ldots , \nu (|\varOmega _1|) \}\) and the objective value would be \( \sum _{\omega =1}^{|\varOmega _1|} \frac{\xi _l^{\nu (\omega )}(\varvec{s})}{|\varOmega | - |\varOmega _1|}. \) Finally, we conclude that

and the result follows.

1.7 Proof of Theorem 4

Let \(\beta \), \( \begin{bmatrix} \gamma _0,&\varvec{\gamma }' \\ \varvec{\gamma },&\varvec{\varGamma } \end{bmatrix}, \) and \( \begin{bmatrix} r_{k0},&\varvec{r}_k' \\ \varvec{r}_k,&\varvec{R}_k \end{bmatrix}, \)\(k \in \underline{\mathcal {N}}\cup \{1\}\), be the dual variables corresponding to the first three constraints in Problem (19), respectively, where \(\varvec{\gamma } \in \mathbb {R}^{|\mathcal {A}|}\), \(\varvec{\varGamma } \in \mathbb {R}^{|\mathcal {A}| \times |\mathcal {A}|}\), \(\varvec{r}_k \in \mathbb {R}^{|\mathcal {A}|}\), \(\varvec{R}_k \in \mathbb {R}^{|\mathcal {A}| \times |\mathcal {A}|}\). Based on the theory of conic duality (see, for instance, [8]), we obtain its dual problem (20). Moreover, their objectives coincide because the Slater’s condition holds, i.e., there exists a strictly relative interior point for Problem (20), defined as \(\beta = 1\), \(\gamma _0 = r_{k0} = \frac{1}{|\underline{\mathcal {N}}| + 2}\), \(\varvec{\gamma } = \varvec{r}_k = \varvec{0}\), and \(\varvec{\varGamma } = \varvec{R}_k = \frac{\varvec{\varSigma }}{|\underline{\mathcal {N}}| + 2}\), \(k \in \underline{\mathcal {N}}\cup \{1\}\), such that

where \(\mathbb {S}_{++}^{|\mathcal {A}| + 1}\) represents the set of symmetric positive definite matrices in \(\mathbb {R}^{(|\mathcal {A}|+1) \times (|\mathcal {A}|+1)}\). The last two constraints hold because

1.8 Proof of Theorem 5

Given a restricted master problem’s solution \({\varvec{s}}^*\), we denote the objective values of Problem (21) and (22) by \(\hat{F}(\varvec{s}^*)\) and \(\check{F}(\varvec{s}^*)\), respectively. When \({\varvec{s}^l}^*=\varvec{0}\), we observe that \(\hat{F}(\varvec{s}^*) = \check{F}(\varvec{s}^*) = 0\). Otherwise, if \(\overline{\tau }_l - \varvec{\mu }'{\varvec{s}^l}^* >0\), it is easy to see that

Based on the first-order condition, the optimal solution of Problem (22) is

and correspondingly,

If \(\overline{\tau }_l - \varvec{\mu }'{\varvec{s}^l}^* \le 0\), since \(\varvec{\varSigma }\) is positive definite, we observe that Problem (21) is infeasible and \(\hat{F}(\varvec{s}^*) = \infty \). Observe also that

is an recession direction to Problem (22) such that \(\check{F}(\varvec{s}^*) = \infty = \hat{F}(\varvec{s}^*)\). Hence, the result follows.

Reprints and permissions