A note on the complexity of two-stage stochastic linear optimization with small second stage
Christoph Buchheim · 2026
Read A note on the complexity of two-stage stochastic linear optimization with small second stage by Christoph Buchheim (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25028.txt.
Introduction
Christoph Buchheim shows two-stage stochastic linear optimization stays strongly #P-hard regardless. It is already intractable for independent uniform interval variables with fixed recourse. Surprisingly, hardness survives for a one-dimensional uniform random vector. The proof goes via #P-hardness of computing the area of a two-dimensional polytope from a compact extended formulation. In standard form, fixing the second-stage constraint count keeps strong #P-hardness, while fixing variables leaves only weak hardness. Fixing both the random dimension and the constraint count makes it tractable.
Catalog record
| CREATOR | Christoph Buchheim |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31596 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25028
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note on the complexity of two-stage stochastic linear optimization with small second stage Christoph Buchheim 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. Keywords: 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 \begin{array}[]{rl}\min&c^{\top}x+\mathbb{E}_{\xi}[Q(x,\xi)]\\[3.22916pt] \text{s.t.}&Ax\leq b\;,\end{array} (SSLP) where the second-stage objective value Q(x,\xi) depends on the first-stage decision x and on a random variable \xi , namely, \displaystyle Q(x,\xi)\;=\;\min\quad \displaystyle q_{\xi}^{\top}y s.t. \displaystyle T_{\xi}x+Wy=h_{\xi},\quad y\geq 0\;. 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\leq 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 [ 2 ] . If the random variable \xi has finite support, it is easy to see that ( SSLP ) 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 ( SSLP ) 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. [ 9 ] that ( SSLP ) is #P-hard in this setting, even if only the objective vector q_{\xi} is random. Since the objective in ( SSLP ) is convex in x , the difficulty of solving ( SSLP ) 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 [ 9 ] 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 ( SSLP ) with fixed dimension d . Unfortunately, Problem ( SSLP ) 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 ( SSLP ) 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 ( SSLP ) 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 [ 1 ] . 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 \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{1}{2}(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\geq 2 . Consider the polyhedron \displaystyle P^{\emptyset}_{n}~:=~ \displaystyle\big\{ \displaystyle(y,z)\in\mathbb{R}^{n+1}\times\mathbb{R}^{n+1}\mid \displaystyle\;\left.\begin{array}[]{l}\;y_{i+1}=\cos(\tfrac{\pi}{2^{i-1}})y_{i}+\sin(\tfrac{\pi}{2^{i-1}})z_{i}\\[4.30554pt] \;z_{i+1}\geq-\sin(\tfrac{\pi}{2^{i-1}})y_{i}+\cos(\tfrac{\pi}{2^{i-1}})z_{i}\\[4.30554pt] \;z_{i+1}\geq+\sin(\tfrac{\pi}{2^{i-1}})y_{i}-\cos(\tfrac{\pi}{2^{i-1}})z_{i}\end{array}~\right\}~\forall i=1,\dots,n \displaystyle\quad\;y_{n+1}\leq 1,~\cos(\tfrac{\pi}{2^{n-1}})y_{n+1}+\sin(\tfrac{\pi}{2^{n-1}})z_{n+1}\leq 1\big\}\;. 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 [ 1 ] 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^{\prime}}