A note on the complexity of two-stage stochastic linear optimization with small second stage
May 24, 2026
Abstract
Two-stage stochastic linear optimization is known to be #P-hard when all involved random variables are independently and uniformly distributed over intervals, even with fixed recourse. We show that this problem is actually #P-hard in the strong sense. More surprisingly, this hardness persists when the random vector is one-dimensional, i.e., uniformly distributed over a single interval. To obtain this result, we show that computing the area of a two-dimensional polytope given by a compact extended formulation is strongly #P-hard.
Furthermore, we obtain the same complexity result in case the number of second-stage constraints is fixed (for a problem in standard form), while fixing the number of second-stage variables leads to a weakly #P-hard problem. Finally, if both the dimension of the random vector and the number of second-stage constraints are fixed, the problem turns out to be tractable.
Stochastic Optimization, #P-hardness, Extended Formulations
1 Introduction↩︎
In two-stage stochastic optimization, some of the problem parameters may depend on a random vector. The decision maker has to take some of her decisions before the random variables are realized (the first stage or here-and-now decisions), while the remaining decisions can be taken afterwards (the second stage, wait-and-see, or recourse decisions). The goal is to optimize the expected objective value. The latter depends on the probability distribution of the random parameters, which we assume to be part of the input. In case of a linear optimization problem, the two-stage stochastic counterpart can be stated as \[\label{prob:sslp}\begin{array}{rl} \min \quad & c^\top x +\mathbb{E}_\xi[Q(x,\xi)]\\[0.75ex] \text{s.t.}\quad & Ax\le b\;, \end{array}\tag{1}\] where the second-stage objective value \(Q(x,\xi)\) depends on the first-stage decision \(x\) and on a random variable \(\xi\), namely, \[\begin{align} Q(x,\xi) \; = \; \min \quad & q_\xi^\top y\\ \text{s.t.}\quad & T_\xi x+W y=h_\xi,\quad y\ge 0\;. \end{align}\] Here \(c\in\mathbb{R}^{n_1}\), \(A\in\mathbb{R}^{m_1\times n_1}\), and \(b\in\mathbb{R}^{m_1}\) describe the first-stage objective and constraints, where we assume for the sake of simplicity that \(\{x\in\mathbb{R}^{n_1}\mid Ax\le b\}\) is non-empty and bounded. Moreover, \(q_\xi\in\mathbb{R}^{n_2}\), \(T_\xi\in\mathbb{R}^{m_2\times n_1}\), \(W\in\mathbb{R}^{m_2\times n_2}\), and \(h_\xi\in\mathbb{R}^{m_2}\) define the second-stage linear optimization problem over the variables \(y\in\mathbb{R}^{n_2}\). We assume here that \(q_\xi\), \(T_\xi\), and \(h_\xi\) depend on the random variable \(\xi\) in an affine-linear way. In this note, we restrict ourselves to the case of fixed recourse, meaning that \(W\) does not depend on \(\xi\), which is a common assumption in two-stage stochastic linear optimization. For more details, we refer to the textbook [1].
If the random variable \(\xi\) has finite support, it is easy to see that 1 can be reformulated as an equivalent single stage linear optimization problem. For this, we can essentially introduce a copy of the second stage for each possible realization of \(\xi\). In particular, problem 1 can be solved efficiently if the support of \(\xi\) is given explicitly as part of the input. This is not possible, however, if the distribution of \(\xi\) is continuous or if the support is finite but exponential in the input. In fact, the complexity picture changes drastically if \(\xi\) follows a continuous uniform distribution, even if all entries of \(\xi\) are independently distributed. In the remainder of this note, we assume \(\xi\sim{\cal U}[l,u]\) with \(l,u\in\mathbb{R}^d\), \(l<u\). It was shown by Hanasusanto et al.[2] that 1 is #P-hard in this setting, even if only the objective vector \(q_\xi\) is random. Since the objective in 1 is convex in \(x\), the difficulty of solving 1 essentially stems from the difficulty of computing objective values, i.e., of computing \(\mathbb{E}_\xi[Q(x,\xi)]\) for a given first-stage decision \(x\). This result even holds for \(n_1=1\), i.e., in case of a single first-stage variable.
The proof presented in [2] requires both an unbounded number of second-stage variables and an unbounded dimension of the random vector \(\xi\). It is thus a natural question to ask which complexity results persist if one or both of these parameters are fixed. Surprisingly, to the best of our knowledge, these questions have not been discussed in the literature so far – although one could argue that in practice the sample space is often low-dimensional, even if many coefficients in the second-stage problem are affected by the uncertainty. For instance, the only relevant random variables in an agricultural application may be the amount of rain and sunshine during a certain period. Moreover, using principle component analysis, the dimension of the random vector can often be reduced without losing too much in terms of solution quality. This motivated our investigation of the complexity of 1 with fixed dimension \(d\).
Unfortunately, Problem 1 turns out to be #P-hard even when restricted to \(d=1\), i.e., to a single random variable (Section 2), or to \(n_2=2\) and \(m_2=1\), i.e., to a second-stage problem with very few variables and constraints (Section 3). Both is true even in the case of fixed recourse and for \(n_1=1\). In fact, we show #P-hardness in the strong sense for \(d=1\) or \(m_2=1\). However, if both \(m_2\) and \(d\) are fixed, the problem turns tractable (Section 4).
2 Fixed dimension of the random vector↩︎
We first discuss the special case of Problem 1 where the dimension \(d\) of the random vector is fixed. Our aim is to reduce #IS, the #P-complete counting version of the independent set problem, to the restriction of 1 with \(d=1\). This will imply that the latter restriction is still #P-hard, even in the strong sense. To this end, we use a construction that is inspired by the extended formulation of a regular polygon presented by Ben-Tal and Nemirovski [3]. For the following, let \(Q_k\) denote the regular \(k\)-gon centered in the origin with vertices \[v_i:=\sec(\tfrac\pi k)(\cos((2i+1)\tfrac\pi k),\sin((2i+1)\tfrac\pi k))^\top,\quad i=0,\dots,k-1\;.\] Then \(||v_i||=\sec(\tfrac\pi k)\) for all \(i=0,\dots,k-1\) and \(\mathop{\mathrm{vol}}(Q_{k})=k\tan(\tfrac\pi k)\). The center point of the facet of \(Q_k\) connecting \(v_i\) and \(v_{i+1}\) (setting \(v_{k}:=v_0\)) is denoted by \[w_i:=\tfrac 12(v_i+v_{i+1})=(\cos((2i+2)\tfrac\pi k),\sin((2i+2)\tfrac\pi k))^\top\;,\] it has length \(||w_i||=1\) and agrees with the normal vector of the corresponding facet for all \(i=0,\dots,k-1\).
Now to start the construction, let a simple undirected graph \(G=(V,E)\) be given, where we assume \(V=\{1,\dots,n\}\) with \(n\ge 2\). Consider the polyhedron \[\begin{align} P^\emptyset_n ~ := ~ & \big\{ & (y,z)\in\mathbb{R}^{n+1}\times\mathbb{R}^{n+1}\mid\\ && \; \left.\begin{array}{l} \; y_{i+1} = \cos(\tfrac\pi{2^{i-1}})y_{i}+\sin(\tfrac\pi{2^{i-1}})z_{i}\\[1ex] \; z_{i+1} \ge -\sin(\tfrac\pi{2^{i-1}})y_{i}+\cos(\tfrac\pi{2^{i-1}})z_{i}\\[1ex] \; z_{i+1} \ge +\sin(\tfrac\pi{2^{i-1}})y_{i}-\cos(\tfrac\pi{2^{i-1}})z_{i} \end{array} ~ \right\} ~ \forall i=1,\dots,n\\ &&\quad\; y_{n+1} \le 1, ~ \cos(\tfrac\pi{2^{n-1}})y_{n+1}+\sin(\tfrac\pi{2^{n-1}})z_{n+1}\le 1\big\}\;. \end{align}\] This formulation contains the matrix \[R_i:=\begin{pmatrix} \cos(\tfrac\pi{2^{i-1}}) & \sin(\tfrac\pi{2^{i-1}})\\ -\sin(\tfrac\pi{2^{i-1}}) & \cos(\tfrac\pi{2^{i-1}})\\ \end{pmatrix}\] which describes the clockwise rotation in \(\mathbb{R}^2\) around the origin by \(\tfrac\pi{2^{i-1}}\) degrees, i.e., by one \(2^i\)-th of a full rotation. Moreover, we will denote by \(R\) the reflection in \(\mathbb{R}^2\) with respect to the first axis, which flips the sign of the second entry. The geometric idea behind the construction in [3] is captured in the following lemma.
Lemma 1. For each vertex \(v_\ell\) of \(Q_{2^n}\), there exists a unique \(b^\ell\in\{0,1\}^n\) with \[R^{b^\ell_n}R_n\cdots R^{b^\ell_1}R_1 v_\ell=v_0\;.\]
Proof. To show existence, we define \(b^\ell\) recursively for \(i=1,\dots,n\), setting \(b^\ell_i:=1\) if and only if \[R_{i}R^{b^\ell_{i-1}}R_{i-1}\cdots R^{b^\ell_1}R_1 v_\ell\] has a negative second entry. Then it follows by induction that the angle of \(R^{b^\ell_{i}}R_{i}\cdots R^{b^\ell_1}R_1 v_\ell\) lies in the range \([0,\tfrac\pi{2^{i-1}}]\). In particular, the final vector \(v=R^{b^\ell_{n}}R_{n}\cdots R^{b^\ell_1}R_1 v_\ell\) has an angle in \([0,\tfrac\pi{2^{n-1}}]\). Moreover, \(v=v_{\ell'}\) for some \(\ell'\in\{0,\dots,2^n-1\}\), since all involved rotations and reflections permute the vertices of \(Q_{2^n}\). Thus \(v=v_0\), the only vertex with angle in \([0,\tfrac\pi{2^{n-1}}]\).
To show uniqueness, let \(b\in\{0,1\}^n\setminus\{b^\ell\}\) and let \(i\) be minimal with \(b_i\neq b^\ell_i\). Then \(R^{b_i}R_{i}\cdots R^{b_1}R_1 v_\ell\) has a non-positive second entry and an angle in \([\tfrac\pi{2^{i-1}},2\pi]\). It follows by induction that \(R^{b_j}R_{j}\cdots R^{b_1}R_1 v_\ell\) has an angle in \([\tfrac\pi{2^{j-1}},2\pi]\) for all \(j\ge i\), hence \(R^{b_n}R_{n}\cdots R^{b_1}R_1 v_\ell\) cannot agree with \(v_0\), which has an angle of \(\tfrac\pi{2^n}\). ◻
By Lemma 1, the vertices \(v_\ell\) of \(Q_{2^n}\) are in one-to-one correspondence with the binary vectors \(b_\ell\in\{0,1\}^n\); see Figure 1 for an illustration. In particular, they correspond to the subsets of \(V\) via \(S_\ell:=\{i\in V\mid b^\ell_i=0\}\). Note that the connection between \(\ell\) and \(b^\ell\) is different from the standard binary expansion of \(\ell\).
Figure 1: The regular \(2^n\)-gon \(Q_{2^n}\) for \(n=2,3\) and the binary vectors \(b^\ell\) assigned to its vertices..
We also remark that \(R^{b^\ell_n}R_n\cdots R^{b^\ell_1}R_1\) maps any vector with an angle in \([\ell\tfrac \pi{2^{n-1}},(\ell+1)\tfrac \pi{2^{n-1}}]\), i.e., between the angles of \(w_{\ell-1}\) and \(w_\ell\), to a vector with angle in \([0,\tfrac \pi{2^{n-1}}]\).
The following result is shown in [3], but we give a slightly different proof here, as its core idea is essential for motivating the rest of the construction.
Proposition 1. The projection \(\bar P^\emptyset_n\) of \(P^\emptyset_n\) to \((y_1,z_1)\) agrees with \(Q_{2^n}\).
Proof. To show \(Q_{2^n}\subseteq \bar P^\emptyset_n\), it suffices to consider the vertices \(v_\ell\) of \(Q_{2^n}\). Then defining \((y_1,z_1)^\top:=v_\ell\) and \((y_{i+1},z_{i+1})^\top:=R^{b^\ell_i}R_i(y_i,z_i)^\top\), for \(i=1,\dots,n\), yields a vector \((y,z)\) that satisfies the recursive constraints in \(P^\emptyset_n\) by construction. Furthermore, we obtain \((y_{n+1},z_{n+1})^\top=v_0=(1,\tan(\tfrac\pi{2^n}))^\top\) from Lemma 1, which satisfies the remaining two constraints.
For the other inclusion, let \((y,z)\in P^\emptyset_n\). We show that \((y_1,z_1)\) then satisfies all facet-defining inequalities for \(Q_{2^n}\), i.e., \(w_\ell^\top (y_1,z_1)^\top\le 1\) for each \(\ell\). As mentioned above, \(R^{b^\ell_i}R_i\cdots R^{b^\ell_1}R_1w_\ell\) has a non-negative second entry for all \(i=1,\dots,n\). In particular, since all involved rotations and reflections are orthogonal, we obtain \[\begin{align} w_\ell^\top(y_1,z_1)^\top & = & (R^{b^\ell_1}R_1w_\ell)^\top R^{b^\ell_1}R_1(y_1,z_1)^\top\\ & \le & (R^{b^\ell_1}R_1w_\ell)^\top (y_2,z_2)^\top\\ & = & (R^{b^\ell_2}R_2R^{b^\ell_1}R_1w_\ell)^\top R^{b^\ell_2}R_2(y_2,z_2)^\top\\ & \le & (R^{b^\ell_2}R_2R^{b^\ell_1}R_1w_\ell)^\top (y_3,z_3)^\top\\ & \vdots & \\ & \le & (R^{b^\ell_n}R_n\cdots R^{b^\ell_1}R_1w_\ell)^\top (y_{n+1},z_{n+1})^\top\\ & = & w_0^\top (y_{n+1},z_{n+1})^\top\\ & = & \cos(\tfrac\pi{2^{n-1}})y_{n+1}+\sin(\tfrac\pi{2^{n-1}})z_{n+1}\le 1\;, \end{align}\] which yields the desired result. ◻
In the recursive construction of \((y,z)\) from \(v_\ell\) described above, the vector \(R_i(y_{i},z_{i})^\top\) is reflected if and only if \(b^\ell_i=1\). We will exploit this for cutting off from \(\bar P_n^\emptyset\) exactly those vertices corresponding to dependent sets in \(G\). To this end, we define a further polyhedron for each edge \(e\in E\) as follows: \[\begin{align} P^e_n:= & \big\{ & (y,z)\in\mathbb{R}^{n+1}\times\mathbb{R}^{n+1}\mid\\ && \left.\begin{array}{l} \,\,y_{i+1} = \cos(\tfrac\pi{2^{i-1}})y_{i}+\sin(\tfrac\pi{2^{i-1}})z_{i}\\[1ex] \,\,z_{i+1} = -\sin(\tfrac\pi{2^{i-1}})y_{i}+\cos(\tfrac\pi{2^{i-1}})z_{i}\text{ if~i\in e}\\[1ex] \left.\begin{array}{l} z_{i+1} \ge -\sin(\tfrac\pi{2^{i-1}})y_{i}+\cos(\tfrac\pi{2^{i-1}})z_{i}\\[1ex] z_{i+1} \ge +\sin(\tfrac\pi{2^{i-1}})y_{i}-\cos(\tfrac\pi{2^{i-1}})z_{i} \end{array} ~ \right\} \text{ if~i\not\in e} \end{array}\right\} ~ \forall i=1,\dots,n\\ &&\;\;\;\, \cos(\tfrac\pi{2^n})y_{n+1}+\sin(\tfrac\pi{2^n})z_{n+1}\le \cos(\tfrac\pi{2^n}) \big\} \end{align}\] Finally, we denote by \(\bar P^e_n\) the projection of \(P^e_n\) to \((y_1,z_1)\) and define \[\bar P_G:=\underset{e\in E\cup\{\emptyset\}}{\scalebox{1.5}{\cap}}\bar P^e_n\;.\] In summary, we have constructed an extended formulation of the two-dimensional polytope \(\bar P_G\) that can be computed in polynomial time from the graph \(G\). We will show that we can derive the number of independent sets of \(G\) from the area of \(\bar P_G\).
Lemma 2. For each \(e\in E\), the intersection \(\bar P^\emptyset_n\cap\bar P^e_n\) agrees with the closure of \[Q_{2^n}\setminus\underset{\ell:\,e\subseteq S_\ell}{\scalebox{1.5}{\cup}}\Delta_\ell\;,\] where \(\Delta_\ell\) is the triangle spanned by \(w_{\ell-1}\), \(v_\ell\), and \(w_{\ell}\).
Proof. It suffices to show the following three statements:
\(w_\ell\in\bar P^e_n\) for all \(\ell=0,\dots,2^n-1\).
If \(e\not\subseteq S_\ell\), then \(v_\ell\in \bar P^e_n\).
If \(e\subseteq S_\ell\), the maximum of \(v_\ell^\top (y_1,z_1)^\top\) over \(\bar P_n^e\) is attained at \(w_{\ell-1}\) and \(w_{\ell}\).
For (a), we again define \((y,z)\in P_n^e\) recursively. Starting with \((y_1,z_1)^\top:=w_\ell\), we set \((y_{i+1},z_{i+1})^\top:=R_i(y_i,z_i)^\top\) if \(i\in e\) or if the second entry of \(R_i(y_i,z_i)^\top\) is non-negative, and \((y_{i+1},z_{i+1})^\top:=RR_i(y_i,z_i)^\top\) otherwise. Then the resulting vector \((y,z)\) satisfies all recursive constraints and \((y_{n+1},z_{n+1})\) agrees with \(w_{\ell'}\) for some \(\ell'\in\{0,\dots,2^n-1\}\), thus it also satisfies the last constraint in \(P_n^e\).
For (b), we use the same construction as in (a), now starting with \((y_1,z_1)^\top=v_\ell\). Since \(e\not\subseteq S_\ell\), we must obtain \((y_{n+1},z_{n+1})^\top=R^{b_n}R_n\cdots R^{b_1}R_1v_\ell\) with \(b\neq b^\ell\), so that \((y_{n+1},z_{n+1})^\top=v_{\ell'}\) with \(\ell'\neq 0\). It follows again that \((y_{n+1},z_{n+1})\) satisfies the last constraint in \(P_n^e\).
Finally, to show (c), let \(e\subseteq S_\ell\). Then we obtain \(v_\ell^\top(y_1,z_1)\le v_0^\top(y_{n+1},z_{n+1})\) exactly as in the second direction of the proof of Proposition 1, except that the \(i\)-th and \(j\)-th inequalities now turn into equations for \(e=\{i,j\}\). From the last constraint, we thus derive \(v_\ell^\top(y_1,z_1)\le 1\), and this bound is attained at \(w_{\ell-1}\) and \(w_\ell\). ◻
The statement of Lemma 2 is illustrated in Figure 2.
It is now easy to derive
Theorem 2. It is strongly #P-hard to compute \(\mathop{\mathrm{vol}}(\bar P_G)\) up to an additive error of less than \[\tfrac 14\tan(\tfrac\pi{2^n})(1-\cos(\tfrac\pi{2^{n-1}}))\;.\]
Proof. The interiors of all triangles \(\Delta_\ell\) are pairwise disjoint and have the same area \(\delta:=\tfrac 12\tan(\tfrac\pi{2^n})(1-\cos(\tfrac\pi{2^{n-1}}))\). Moreover, by Lemma 2, the triangle \(\Delta_\ell\) is missing in \(\bar P_G\) if and only if there exists an edge \(e\) with \(e\subseteq S_\ell\), i.e., if and only if \(S_\ell\) is a dependent set in \(G\). We derive that \(\mathop{\mathrm{vol}}(\bar P_G)=\mathop{\mathrm{vol}}(Q_{2^{n}})-(2^n-n_{\text{IS}})\delta\), where \(n_{\text{IS}}\) is the number of independent sets in \(G\). Hence \[n_{\text{IS}}=2^n-\tfrac 1\delta(\mathop{\mathrm{vol}}(Q_{2^n})-\mathop{\mathrm{vol}}(\bar P_G))\] can be computed efficiently from \(\mathop{\mathrm{vol}}(\bar P_G)\) if the latter is known up to an additive error of less than \(\tfrac 12\delta\). However, it is strongly #P-complete to compute \(n_{\text{IS}}\), even on graphs with maximal degree three [4]. ◻
Lemma 3. For \(n\ge 2\), we have \(\delta>\tfrac 1{2^{3n-3}}\).
Proof. Since \(\tfrac\pi{2^{n-1}}\in [0,\tfrac\pi 2]\), we obtain \(\tan(\tfrac\pi{2^n})\ge\tfrac 1{2^{n-1}}\) and \(1-\cos(\tfrac\pi{2^{n-1}})> \tfrac 1{2^{2n-3}}\) and thus the desired lower bound. ◻
Theorem 3. Problem 1 is strongly #P-hard for \(d=1\) and \(n_1=1\), even if only the right hand side \(h_yi\) is random.
Proof. Since \(\bar P_G\) is convex and contains both \((-1,0)\) and \((1,0)\), we have \[\begin{align} \mathop{\mathrm{vol}}(\bar P_G) & = & \textstyle \int_{-1}^1 (\max\{z_1\mid (y_1,z_1)\in \bar P_G\}-\min\{z_1\mid (y_1,z_1)\in \bar P_G\}) \,\textrm{d}y_1\\ & = & 2\mathbb{E}_\xi[\max\{z_1\mid (\xi,z_1)\in \bar P_G\}]-2\mathbb{E}_\xi[\min\{z_1\mid (\xi,z_1)\in \bar P_G\}] \end{align}\] with \(\xi\sim{\cal U}[-1,1]\). In view of Theorem 2, it remains to show that the computation of \(\mathbb{E}_\xi[\max\{z_1\mid (\xi,z_1)\in \bar P_G\}]\) can be polynomially reduced to 1 with \(n_1=1\); the min-case is analogous. For this, similar to [2], we consider the problem of minimizing \[-cx+\mathbb{E}_\xi[\max\{z_1\mid (\xi,z_1)\in x\bar P_G\}]=x(\mathbb{E}_\xi[\max\{z_1\mid (\xi,z_1)\in \bar P_G\}]-c)\] over the single first-stage variable \(x\in [0,1]\). This is a problem of type 1 . Indeed, an extended formulation of \(x\bar P_G\) is obtained by multiplying all right-hand sides in \(P_n^\emptyset\) and in all \(P_n^e\) with \(x\), so that the former right hand side now takes the role of the matrix \(T\), which is fixed. Moreover, the former variable \(y_1\), now replaced by \(\xi\), moves to the right hand side.
If the optimum is attained at \(x=0\), we derive \(\mathbb{E}_\xi[\max\{z_1\mid (\xi,z_1)\in \bar P_G\}]\ge c\), otherwise \(\mathbb{E}_\xi[\max\{z_1\mid (\xi,z_1)\in \bar P_G\}]\le c\). Using a standard bisection approach for \(c\) in the range \([\tfrac 12,1]\), the computation of the value \(\mathbb{E}_\xi[\max\{z_1\mid (\xi,z_1)\in \bar P_G\}]\) can thus be reduced to at most \(3n-3\) calls to 1 by Lemma 3. ◻
The statement of Theorem 3 also holds if, instead of the right hand side \(h_\xi\), only the objective \(q_\xi\) is random. For this, it suffices to dualize the given extended formulation of \((\xi,z_1)\in \bar P_G\) and scale by \(x\) afterwards.
3 Fixed size of the second-stage problem↩︎
We next prove that bounding the number of variables and constraints in the second stage is not sufficient to obtain a tractable special case of 1 either. This can be shown by similar techniques as employed in [2], although in the reduction presented there, the second stage is not bounded and only weak #P-hardness is shown for the case of fixed recourse. We first fix only the number of constraints \(m_2\).
Theorem 4. Problem 1 is strongly #P-hard if \(n_1=1\) and \(m_2=1\), even if only the objective \(q_\xi\) is random.
Proof. Let \(P=\{\xi\in [0,1]^d\mid A\xi\le b\}\) be any non-empty polytope with \(A\in\mathbb{Z}^{m\times d}\) and \(b\in\mathbb{Z}^m\), for any \(m\in\mathbb{N}\). Then computing the volume of \(P\) is strongly # P-hard [5]. For \(x\in[0,1]\) and \(t\in\mathbb{R}\), we consider the following second-stage problem \[\begin{align} Q_{t}(x,\xi) \; = \; \max \quad & (A\xi-b-te)^\top y\\ \text{s.t.}\quad & y\ge 0,\quad e^\top y\le x\;, \end{align}\] where \(e=(1,\dots,1)^\top\in\mathbb{R}^m\). Transformed into standard form, we thus have \(m_2=1\) and \(n_2=m+1\). Then \[Q_{t}(x,\xi)=\max\,\{0,\max\,\{a_j \xi-b_j\mid j=1,\dots,m\}-t\}\cdot x\;,\] where \(a_j\) denotes the \(j\)th row vector of \(A\), and \[\tfrac\partial{\partial t} Q_{t}(x,\xi)=\left\{\begin{array}{cl} 0 & \text{if }A\xi< b+te \\ -x & \text{if }a_j\xi > b_j+t\text{ for some }j\in\{1,\dots,m\} \end{array}\right.\] Hence, using the Leibniz integral rule and assuming \(\xi\sim{\cal U}[0,1]^d\), \[\tfrac\partial{\partial t} \mathbb{E}_\xi[Q_{t}(x,\xi)] = \mathbb{E}_\xi[\tfrac\partial{\partial t} Q_{t}(x,\xi)] = (\mathop{\mathrm{vol}}(P_t)-1)\cdot x\;,\] where \(P_t=\{\xi\in [0,1]^d\mid A\xi\le b+te\}\). Now define \(p(t):=\mathbb{E}_\xi[Q_t(x,\xi)]\). By Lemma 5 in Appendix 6, the derivative \(p'(t)=(\mathop{\mathrm{vol}}(P_t)-1)x\) is a polynomial of degree at most \(d\) in the range \([0,1]\). Hence \(p\) is a polynomial of degree at most \(d+1\) in the same range, and the \(d+2\) coefficients of \(p\) can be obtained by evaluating \(p\) at \(d+2\) different points in \([0,1]\); the derivative \(p'\) can then be determined symbolically. Altogether, for \(x>0\), the computation of \(\mathop{\mathrm{vol}}(P)\) can be polynomially reduced to the computation of \(\mathbb{E}_\xi[Q_{t}(x,\xi)]\) for different values of \(t\in\mathbb{R}\), so that the latter task is strongly #P-hard. Arguing analogously to the last part of the proof of Theorem 3, it follows that 1 is strongly #P-hard for \(n_1=m_2=1\). ◻
If the polytope \(P\) in the proof of Theorem 4 is defined by only one linear inequality, it is still (weakly) # P-hard to compute the volume of \(P\) [5]. We thus obtain
Theorem 5. Problem 1 is #P-hard if \(n_1=1\), \(n_2=2\), and \(m_2=1\), even if only the objective \(q_\xi\) is random.
Comparing the results of Theorem 4 and Theorem 5, it remains to clarify whether fixing \(n_2\) (and thus also \(m_2\)) leads to a strongly or weakly # P-hard problem. The latter is the case.
Theorem 6. Let \(n_2\) be fixed. Then 1 can be solved up to any desired accuracy \(\varepsilon>0\) in pseudopolynomial time (and in time logarithmic in \(1/\varepsilon\)).
Proof. It is easy to verify that \(\mathbb{E}_\xi[Q(x,\xi)]\) is a convex function in \(x\), thus by Grötschel et al. [6] – and due to our assumption that the first-stage feasible region is non-empty and bounded – it suffices to show that \(\mathbb{E}_\xi[Q(x,\xi)]\) can be computed in pseudopolynomial time for any given \(x\in\mathbb{R}^n\).
Let \(B\) be the set of bases of \(W\). Since \(n_2\) is fixed and \(m_2\le n_2\), also \(|B|\le n_2^{m_2}\) is bounded. For each \({\cal B}\in B\), let \(P_{\cal B}\) denote the set of all \(\xi\in[l,u]^d\) such that \({\cal B}\) is feasible and optimal for the given \(x\), i.e., \[P_{\cal B}:=\{\xi\in [l,u]^d\mid W_{\cal B}^{-1}(h_\xi-T_\xi x)\ge 0,~(q_\xi)_{\cal N}-W_{\cal N}^\top (W_{\cal B}^{-1})^\top(q_\xi)_{\cal B}\ge 0\}\;.\] Each \(P_{\cal B}\) is a polytope defined by intersecting the box \([l,u]^d\) with \(n_2\) many halfspaces.
Next, we partition \(B\) into equivalence classes \(B^{(1)},\dots,B^{(\ell)}\) with respect to the quadratic function \((q_\xi)_{{\cal B}}^\top W_{{\cal
B}}^{-1}(h_\xi-T_\xi x)\) that describes the objective value of the basic solution corresponding to \({\cal B}\) as a function of \(\xi\). More precisely, two bases are equivalent if
this function agrees on \(\mathbb{R}^d\); we denote the latter by \(q^{(r)}\) for the class \(B^{(r)}\). Two bases \({\cal
B}_1\) and \({\cal B}_2\) belonging to different classes are simultaneously optimal on a zero set, so that \(\mathop{\mathrm{vol}}(P_{{\cal B}_1}\cap P_{{\cal B}_2})=0\). In
particular, setting \(P^{(r)}:=\cup_{{\cal B}\in B^{(r)}}P_{{\cal B}}\), we obtain \[\mathbb{E}_\xi[Q(x,\xi)] = \mathbb{E}_\xi\big[\max_{{\cal B}\in B}\;(q_\xi)_{\cal B}^\top W_{\cal
B}^{-1}(h_\xi-T_\xi x)\big] = \Big(\prod_{i=1}^d\tfrac 1{u_i-l_i}\Big)\sum_{r=1}^\ell \int_{P^{(r)}} q^{(r)}(\xi) \,\textrm{d}\xi\;.\] By the inclusion-exclusion principle, we have \[\int_{P^{(r)}} q^{(r)}(\xi) \,\textrm{d}\xi = \sum_{\emptyset\neq B'\subseteq B^{(r)}}(-1)^{|B'|+1} \int_{\cap_{{\cal B}\in B'} P_{{\cal B}}} q^{(r)}(\xi)\,\textrm{d}\xi\;.\label{eq:incl95excl}\tag{2}\]
Since \(|B^{(r)}|\le |B|\le n_2^{m_2}\), this sum ranges over at most \(2^{n_2^{m_2}}-1\) many subsets and each intersection \(\cap_{{\cal B}\in B'} P_{{\cal
B}}\) is a polytope defined by box constraints and at most \(n_2^{m_2+1}\) linear inequalities. All integrals in 2 can thus be computed in pseudopolynomial time by Lemma 7 in Appendix 6. This yields the desired result. ◻
4 Fixing both sizes↩︎
We finally discuss the case where both the dimension \(d\) of the random vector and the number \(m_2\) of second-stage constraints are fixed.
Theorem 7. Let \(d\) and \(m_2\) be fixed. Then 1 can be solved up to any desired accuracy \(\varepsilon>0\) in polynomial time (and in time logarithmic in \(1/\varepsilon\)).
Proof. The result can be shown analogously to Theorem 6. Again, it suffices to compute \(\mathbb{E}_\xi[Q(x,\xi)]\), but the number of second-stage bases \(|B|\) is now polynomial instead of fixed. In particular, the number of non-zero terms in the sum in 2 can now become exponential. However, the total number of constraints defining all polytopes \(P_{\cal B}\) with \({\cal B}\in B^{(r)}\) is \(n_2^{m_2+1}\) and hence polynomial, as \(m_2\) is fixed. Since \(d\) is fixed as well, we can compute the corresponding hyperplane arrangement and identify all cells belonging to \(P^{(r)}\) in polynomial time; see, e.g., [7]. Finally, integrating \(q^{(r)}\) over \(P^{(r)}\) reduces to integrating \(q^{(r)}\) over these cells, which can be done efficiently for fixed \(d\) using triangulation; see, e.g., [8]. ◻
5 Conclusion↩︎
The following table summarizes all results. Recall that \(m_2\le n_2\) and hence fixed \(n_2\) implies fixed \(m_2\).
| fixed parameter | \(d\) | \(m_2\) | \(n_2\) | \(d\) and \(m_2\) |
|---|---|---|---|---|
| complexity | strongly | strongly | weakly | polynomial |
| #P-hard | #P-hard | #P-hard | ||
| reference | Theorem 3 | Theorem 4 | Theorem 5 | Theorem 7 |
| Theorem 6 |
An interesting question for further research could be the fixed-parameter tractability of 1 for the positive cases, in particular for fixed \(d\) and \(m_2\). Moreover, the presented algorithms only serve to show tractability and can surely be improved significantly, which is out of the scope of this note.
6 Auxiliary results on polytope volumes↩︎
For the convenience of the reader, we recall and prove some technical results on volumes of polytopes that can be found – although somewhat implicitly – in the literature; see, e.g., [5], [9], [10]. For all results, we assume that \(A\in\mathbb{Z}^{m\times d}\) is given and define \(P(b):=\{\xi\in[0,1]^d\mid A\xi\le b\}\) for all \(b\in\mathbb{R}^m\).
Lemma 4. The volume of \(P(b)\), as a function in \(b\in\mathbb{R}^m\), is a polynomial of degree at most \(d\) on each box \([\bar b,\bar b+e]\) with \(\bar b\in\mathbb{Z}^m\).
Proof. Let \(\bar b\in\mathbb{Z}^m\) and fix any triangulation of \(P(\bar b+\tfrac 12e)\). If \(b\) ranges over \([\bar b,\bar b+e]\), the same triangulation remains valid, since \(A\) is integer; however, the vertices of \(P(b)\) are affine-linear functions in \(b\) in that range. As the volume of a \(d\)-dimensional simplex is a polynomial of degree at most \(d\) in its vertices, the result follows. ◻
Lemma 5. Let \(b,b'\in\mathbb{Z}^m\). Then the volume of \(P(b+tb')\) is a polynomial in \(t\) of degree at most \(d\) in the range \([0,t']\), where \(t':=1/{||b'||_\infty}\).
Proof. For each \(i\in\{1,\dots,m\}\), we either have \((b+tb')_i\in[b_i,b_i+1]\) for all \(t\in[0,t']\) or \((b+tb')_i\in[b_i-1,b_i]\) for all \(t\in[0,t']\). By Lemma 4, the volume of \(P(b+tb')\) is thus a polynomial of degree at most \(d\) for \(t\in[0,t']\). ◻
Lemma 6. Let \(b\in\mathbb{R}^m\). If \(m\) is fixed, then the volume of \(P(b)\) can be computed in time polynomial in \(d\) and \(||A||_\infty\).
Proof. For \(k\in\{0,1,\dots,d\}\) and \(s\in\mathbb{R}^m\), define \(P_{k}(s):=\{\xi\in[0,1]^k\mid A_k\xi\le s\}\), where \(A_k\in\mathbb{Z}^{m\times k}\) consists of the first \(k\) columns of \(A\). By Lemma 4, the volume of \(P_{k}(s)\) is a polynomial in \(s\) of degree at most \(k\) on each box \([\bar s,\bar s+e]\), \(\bar s\in\mathbb{Z}^m\). The at most \(k^m\) coefficients of these polynomials, for all \(\bar s\) in the set \[\textstyle Z_k:=\mathbb{Z}^m\cap [\lfloor b\rfloor-\sum_{\ell=k+1}^d||a_\ell||_\infty,\lfloor b\rfloor+\sum_{\ell=k+1}^d||a_\ell||_\infty]\;,\] can be computed iteratively for \(k=0,\dots,d\) using dynamic programming: First, by convention, \(\mathop{\mathrm{vol}}(P_{0,s})=1\) if \(s\ge 0\) and zero otherwise, so that all polynomials for \(k=0\) can be computed easily. For \(k\ge 1\), we use the recursive formula \[\mathop{\mathrm{vol}}(P_{k}(s))=\int_0^1\mathop{\mathrm{vol}}(P_{k-1}(s-a_kt))\,\textrm{d}t\quad\forall k\in\mathbb{N},\,s\in\mathbb{R}^m\;.\] Again by Lemma 4, the volume of \(P_{k-1}(s-a_kt)\) is a polynomial in \(t\) as long as \(s-a_kt\) remains in a box \([\bar s,\bar s+e]\). To compute the coefficients of \(\mathop{\mathrm{vol}}(P_{k}(s))\) on \(s\in[\bar s,\bar s+e]\) for some \(\bar s\in Z_k\), it suffices to symbolically integrate the polynomial \(\mathop{\mathrm{vol}}(P_{k-1}(s-a_kt))\), as a function in \(t\), for each of the corresponding ranges of \(t\), and to coefficient-wise sum up the resulting polynomials in \(s\) weighted by the lengths of these ranges. By definition of \(Z_k\), we have \(\bar s-a_kt\in[\bar{\bar s},\bar{\bar s}+e]\) for some \(\bar{\bar s}\in Z_{k-1}\), for all \(t\in[0,1]\), so that we know the coefficients of \(\mathop{\mathrm{vol}}(P_{k-1}(s-a_kt))\) from the previous iteration.
Since \(|Z_k|\le (2(d-k)||A||_\infty+1)^m\) for all \(k\), all this can be done in time polynomial in \(d\) and \(||A||_\infty\) if \(m\) is fixed. Finally, the desired volume is obtained by evaluating the polynomial describing \(\mathop{\mathrm{vol}}(P_{d}(b))\) on \([\lfloor b\rfloor,\lfloor b\rfloor+e]\) in the given \(b\in\mathbb{R}^m\). ◻
Lemma 7. Let \(b\in\mathbb{R}^m\) and let \(q\colon\mathbb{R}^d\to\mathbb{R}\) be a quadratic function. If \(m\) is fixed, then the integral \(\int_{P(b)} q(\xi)\,\textrm{d}\xi\) can be computed in time polynomial in \(d\) and \(||A||_\infty\).
Proof. Using linearity, it suffices to compute all moments \(\int_{P(b)} \xi_i\xi_j\,\textrm{d}\xi\), \(\int_{P(b)} \xi_i\,\textrm{d}\xi\), and \(\int_{P(b)} 1\,\textrm{d}\xi\) for \(i,j\in\{1,\dots,d\}\). But \(\int_{P(b)} \xi_i\xi_j\,\textrm{d}\xi=\mathop{\mathrm{vol}}(P')\) for the polytope \[P'=\{(\xi,u,v)\in [0,1]^{d+2}\mid A\xi\le b,u\le\xi_i,v\le\xi_j\}\;,\] and the integrals \(\int_{P(b)} \xi_i\,\textrm{d}\xi\) can be treated analogously. The result now follows directly from Lemma 6. ◻
References↩︎
Fakultät für Mathematik, TU Dortmund, Germany. Email: christoph.buchheim@tu-dortmund.de↩︎