Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making

In a bottleneck combinatorial problem, the objective is to minimize the highest cost of elements of a subset selected from the combinatorial solution space. This paper studies data-driven distributionally robust bottleneck combinatorial problems (DRBCP) with stochastic costs, where the probability distribution of the cost vector is contained in a ball of distributions centered at the empirical distribution specified by the Wasserstein distance. We study two distinct versions of DRBCP from different applications: (i) Motivated by the multi-hop wireless network application, we first study the uncertainty quantification of DRBCP (denoted by DRBCP-U), where decision-makers would like to have an accurate estimation of the worst-case value of DRBCP. The difficulty of DRBCP-U is to handle its max–min–max form. Fortunately, similar to the strong duality of linear programming, the alternative forms of the bottleneck combinatorial problems using clutters and blocking systems allow us to derive equivalent deterministic reformulations, which can be computed via mixed-integer programs. In addition, by drawing the connection between DRBCP-U and its sampling average approximation counterpart under empirical distribution, we show that the Wasserstein radius can be chosen in the order of negative square root of sample size, improving the existing known results; and (ii) Next, motivated by the ride-sharing application, decision-makers choose the best service-and-passenger matching that minimizes the unfairness. That is, we study the decision-making DRBCP, denoted by DRBCP-D. For DRBCP-D, we show that its optimal solution is also optimal to its sampling average approximation counterpart, and the Wasserstein radius can be chosen in a similar order as DRBCP-U. When the sample size is small, we propose to use the optimal value of DRBCP-D to construct an indifferent solution space and propose an alternative decision-robust model, which finds the best indifferent solution to minimize the empirical variance. We further show that the decision robust model can be recast as a mixed-integer conic program. Finally, we extend the proposed models and solution approaches to the distributionally robust \(\varGamma \)—sum bottleneck combinatorial problem (\(\hbox {DR}\varGamma \hbox {BCP}\)), where decision-makers are interested in minimizing the worst-case sum of \(\varGamma \) highest costs of elements.

The authors would like to thank Editor-in-Chief Dr. Sven Leyffer and two anonymous reviewers for their valuable comments on improving this paper.

Authors and Affiliations

1. Virginia Tech, Blacksburg, VA, USA

   Weijun Xie & Jie Zhang

2. Georgia Institute of Technology, Atlanta, GA, USA

   Shabbir Ahmed

Corresponding author

Correspondence to Weijun Xie.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A. DRBCP-U (2a) under \(q-\hbox {Wasserstein}\) ambiguity set: equivalent reformulation, MIP representation, and confidence bounds

For the completeness of this paper, in this appendix, we provide parallel results for DRBCP-U (2a) under \(q-\hbox {Wasserstein}\) ambiguity set (3) with \(q\in [1,\infty )\).

1.1 A.1 Equivalent reformulation

We first derive a deterministic representation of DRBCP-U (2a) under \(q-\hbox {Wasserstein}\) ambiguity set.

Theorem 10

Suppose \(\Vert \cdot \Vert =\Vert \cdot \Vert _r\) with \(r\ge 1\), then DRBCP-U (2a) \(q-\hbox {Wasserstein}\) ambiguity set is equivalent to

where F is defined in Theorem 1 and set \(I^k(t,y)=\{j\in y: t-{\overline{c}}_j^k\ge 0\}\).

Proof

According to Theorem 1 and theorem 1 in [17], we have

By swapping the two maximization operators and linearizing the inner minimization operator, we further have

To simplify the inner maximization, we let \(\beta _j^k=c_j^k-t^k\) for all \(j\in y\) and define set \(I^k(t,y)=\{j\in y: t-{\overline{c}}_j^k\ge 0\}\), then we have

where the second equality is due to the optimality condition that if \(j\in y\setminus I^k(t^k,y) \), we must have \(\beta _j^k=-t^k+{{\bar{c}}}_j^k>0\); otherwise, \(\beta _j^k=0\). \(\square \)

1.2 A.2 Mixed integer programming representation

Note that in Theorem 10, the outer minimization problem is a univariate convex program and thus can be solved efficiently via the bisection method. We then observe that for any given \(\lambda \), the inner maximizations in DRBCP-U (29) can be decomposed into N separate MIPs.

Proposition 7

Suppose that the blocker F admits a binary programming representation \({\widehat{F}}\subseteq \{0,1\}^n\). Then \(v_U=\min _{\lambda \ge 0}\{\lambda \theta ^q+1/N\sum _{k\in [N]}v_U^k(\lambda )\}\) and \(v_U^k(\lambda )\) is equivalent to

where \(M_{j}^k= {\widehat{M}}^k-{\bar{c}}_{j}^k\) and \( {\widehat{M}}^k=\max _{\tau \in [n]}{\bar{c}}_\tau ^k+(\lambda q)^{-1/(q-1)}\).

Proof

According to the proof of Theorem 10, \(v_U=\min _{\lambda \in [0,1]}\{\lambda \theta ^q+1/N\sum _{k\in [N]}v_U^k(\lambda )\}\), where

Above, we can augment the vector \(\varvec{\beta }^k\) by defining free variable \(\beta _j^k\) for each \(j\in [n]\setminus y\) and rewrite \(v_U^k(\lambda )\) as

since at optimality, we must have \(\beta _{j}^k=-t^k+{{\bar{c}}}_j^k\) for each \(j\in [n]\setminus y\).

As the blocker F admits a binary programming representation \({\widehat{F}}\), the value \(v_U^k(\lambda )\) is further equal to

To prove that (32) and (31) are equivalent, we only need to show that \(\beta _{j}^k\ge -M_j^k\) for each \(j\in [n]\). Since at optimality, \(\beta _{j}^k\) is equal to 0 or \(-t^k+{{\bar{c}}}_j^k\). Thus, it is sufficient to find an upper bound of \(t^k\). In (29), suppose the optimal \(t^k\ge \max _{\tau \in [n]}{\bar{c}}_\tau ^k\), and then \(I^k(t,y)=y\). The first order optimality condition of inner maximization of (29) yields

where the first inequality is due to \(t^k-{{\bar{c}}}_j^k\ge t^k-\max _{\tau \in [n]}{\bar{c}}_\tau ^k\) and \(|y|\ge 1\). Thus, we can define \({\widehat{M}}^k\) as

\(\square \)

We remark that: (i) to obtain \(v_U\), one needs to first fix \(\lambda \) and then solve N separate MIPs (31), and then optimize \(\lambda \), which requires more computational time compared to that of DRBCP-U (2a) under \(\infty -\) Wasserstein ambiguity set; and (ii) as long as r is a rational number, using the conic quadratic representation results in [4], then the MIP (31) can be formulated as a mixed integer second order conic program (MISOCP).

1.3 A.3 Confidence bounds

In this subsection, we plan to compare \(v_U\) with its sampling average approximation counterpart, which further motivates us a choice of Wasserstein radius \(\theta \). Recall that \(v_U^{SAA}\) and \(v_U^{T}\) are defined in (14a) and (14b), respectively. Our goal is to determine a proper \(\theta \) such that \(v_U\ge v_U^{T}\) with a high probability. To begin with, we would like to show the relationship between \(v_U\) and \(v_U^{SAA}\).

Proposition 8

Let \(v_U^{SAA}\) be defined in (14a). Then

Proof

1. (i)

   To prove \(v^U-v^{SAA}\le \theta \), using the fact that \(t^k \ge \min _{j\in y}{\bar{c}}_j^k\), then we can upper bound \(v^U\) as

   $$\begin{aligned} v_U&\le \min _{\lambda \ge 0}\left\{ \lambda \theta ^q+\frac{1}{N}\sum _{k\in [N]}\max _{y\in F}\max _{t^k\ge \min _{j\in y}{\bar{c}}_j^k}\left\{ t^k-\lambda \left( t^k-\min _{j\in y}{\bar{c}}_j^k\right) ^{q}\right\} \right\} . \end{aligned}$$

   (33)

   To optimize the inner maximization, there are two cases:

   1. Case 1.

      If \(q=1\), then the inequality (33) is equivalent to

      $$\begin{aligned} v_U&\le \min _{\lambda \ge 0}\left\{ \lambda \theta +\frac{1}{N}\sum _{k\in [N]}\max _{y\in F} \min _{j\in y}{\bar{c}}_j^k: \lambda \ge 1\right\} =v^{SAA}+\theta . \end{aligned}$$
   2. Case 2.

      If \(q>1\), then the inequality (33) is equivalent to

      $$\begin{aligned} v_U&\le \min _{\lambda \ge 0}\left\{ \lambda \theta ^q+\frac{q-1}{q^{\frac{q}{q-1}}}\lambda ^{-\frac{1}{q-1}}+\frac{1}{N}\sum _{k\in [N]}\max _{y\in F} \min _{j\in y}{\bar{c}}_j^k\right\} \\&=v^{SAA}+\theta . \end{aligned}$$
   3. Case 3.

      To prove \(v^U-v^{SAA}\ge \frac{\theta }{{\max }_{y\in F}|y|^{\frac{1}{r}}}\), using the fact that \(t^k \ge \min _{j\in y}{\bar{c}}_j^k\) again, then we can bound \(v^U\) from the below as

      $$\begin{aligned} v_U&\ge \min _{\lambda \ge 0}\left\{ \lambda \theta ^q+\frac{1}{N}\sum _{k\in [N]}\max _{y\in F}\max _{t^k\ge \min _{j\in y}{\bar{c}}_j^k}\left\{ t^k-\lambda |y|^{\frac{q}{r}}\left( t^k-\min _{j\in y}{\bar{c}}_j^k\right) ^{q}\right\} \right\} . \end{aligned}$$

      (34)

   To optimize the inner maximization, there are two cases:

   1. Case 1.

      If \(q=1\), then the inequality (34) is equivalent to

      $$\begin{aligned} v_U&\ge \min _{\lambda \ge 0}\left\{ \lambda \theta +\frac{1}{N}\sum _{k\in [N]}\max _{y\in F} \min _{j\in y}{\bar{c}}_j^k: \lambda \ge \frac{1}{\min _{h\in F}|h|^{\frac{q}{r}}}\right\} =v^{SAA}+\frac{\theta }{\min _{y\in F}|y|^{\frac{q}{r}}}\\&\ge v^{SAA}+\frac{\theta }{\max _{y\in F}|y|^{\frac{q}{r}}}. \end{aligned}$$
   2. Case 2.

      If \(q>1\), using the fact that \(|y|^{\frac{q}{r}}\le \max _{h\in F}|h|^{\frac{q}{r}}\) for all \(y\in F\), then the right-hand side of inequality (34) is further lower bounded by

      $$\begin{aligned} v_U&\ge \min _{\lambda \ge 0}\left\{ \lambda \theta ^q+\frac{q-1}{q^{\frac{q}{q-1}}}\left( \frac{1}{\lambda \max _{h\in F}|h|^{\frac{q}{r}}}\right) ^{\frac{1}{q-1}}+\frac{1}{N}\sum _{k\in [N]}\max _{y\in F} \min _{j\in y}{\bar{c}}_j^k\right\} \\&=v^{SAA}+\frac{\theta }{\max _{y\in F}|y|^{\frac{1}{r}}}. \end{aligned}$$

      \(\square \)

Now we are ready to show the following main result on the relationship between the value of DRBCP-U \(v_U\) and true value \(v_U^T\).

Theorem 11

Suppose that there exists a positive \(\sigma \) such that \({{\mathbb {E}}}_{{\mathbb {P}}^T}[\exp ((Z(\tilde{\varvec{c}})-v_U^T)^2/\sigma ^2)]\le e\). Given \(\epsilon \in (0,1)\), then

1. (i)

   let \(\theta =N^{-\frac{1}{2}}\sigma \sqrt{-3\log (\epsilon )}{\max }_{y\in F}|y|^{\frac{1}{r}}=O(N^{-\frac{1}{2}})\). Then we have

   $$\begin{aligned} {\mathbb {P}}^T\left\{ v_U\ge v_U^T\right\} \ge 1-\epsilon ; \end{aligned}$$
2. (ii)

   let \(\theta =N^{-\frac{1}{2}}\sigma \sqrt{-3\log (\epsilon )}=O(N^{-\frac{1}{2}})\). Then we have

   $$\begin{aligned} {\mathbb {P}}^T\left\{ v_U\le v_U^T+2\theta \right\} \ge 1-\epsilon . \end{aligned}$$

Proof

The proof is almost identical to Theorem 3 and is thus omitted. \(\square \)

1.4 A.4 Numerical illustration of DRBCP-U (2a) under \(2-\)Wasserstein ambiguity set

See Table 3.

1.5 A.5 Numerical illustration of DRBCP-D (2b) under \(\phi \)-divergence

Alternatively, we can consider DRBCP-D (2b) under a \(\phi \)-divergence ambiguity set \({{\mathcal {P}}}\). In particular, we construct the ambiguity set based on the total-variational distance with radius \(d\in [0,2]\). According to [25], given \(d\in [0,2]\), the distributionally robust fair matching problem in Example 6 under total variation based ambiguity set admits the following form

The numerical results using the same datasets as those in Sect. 5.2 are displayed in Fig. 2 and Table 4.

Numerical illustration of fair matching problem under total variation-based ambiguity set (35): using real-world dataset in Sect. 5.2

Full size image

Reprints and permissions