The double exponential runtime is tight for 2-stage stochastic ILPs
Open Access
- 28 May 2022
- journal article
- research article
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 1145-1172
Abstract
We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form $$\min \{c^T x \mid {\mathcal {A}} x = b, \ell \le x \le u, x \in {\mathbb {Z}}^{r + ns} \}$$ where the constraint matrix $${\mathcal {A}} \in {\mathbb {Z}}^{nt \times r +ns}$$ consists of n matrices $$A_i \in {\mathbb {Z}}^{t \times r}$$ on the vertical line and n matrices $$B_i \in {\mathbb {Z}}^{t \times s}$$ on the diagonal line aside. We show a stronger hardness result for a number theoretic problem called Quadratic Congruences where the objective is to compute a number $$z \le \gamma $$ satisfying $$z^2 \equiv \alpha \bmod \beta $$ for given $$\alpha , \beta , \gamma \in {\mathbb {Z}}$$ . This problem was proven to be NP-hard already in 1978 by Manders and Adleman. However, this hardness only applies for instances where the prime factorization of $$\beta $$ admits large multiplicities of each prime number. We circumvent this necessity proving that the problem remains NP-hard, even if each prime number only occurs constantly often. Using this new hardness result for the $$\textsc {Quadratic Congruences}$$ problem, we prove a lower bound of $$2^{2^{\delta (s+t)}} |I|^{O(1)}$$ for some $$\delta > 0$$ for the running time of any algorithm solving 2-stage stochastic ILPs assuming the Exponential Time Hypothesis (ETH). Here, |I| is the encoding length of the instance. This result even holds if r, $$||b||_{\infty }$$ , $$||c||_{\infty }, ||\ell ||_{\infty }$$ and the largest absolute value $$\varDelta $$ in the constraint matrix $${\mathcal {A}}$$ are constant. This shows that the state-of-the-art algorithms are nearly tight. Further, it proves the suspicion that these ILPs are indeed harder to solve than the closely related $$n$$ -fold ILPs where the constraint matrix is the transpose of $${\mathcal {A}}$$ .
Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (JA 612/20-1)
This publication has 24 references indexed in Scilit:
- The Chinese Remainder Theorem and Simultaneous Congruences2008
- -fold integer programmingDiscrete Optimization, 2008
- Exact solutions to a class of stochastic generalized assignment problemsEuropean Journal of Operational Research, 2006
- All Linear and Integer Programs Are Slim 3‐Way Transportation ProgramsSIAM Journal on Optimization, 2006
- Decomposition of test sets in stochastic integer programmingMathematical Programming, 2003
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- Two‐stage stochastic integer programming: a surveyStatistica Neerlandica, 1996
- NP-Complete decision problems for binary quadraticsJournal of Computer and System Sciences, 1978
- Contributions to the theory of the riemann zeta-function and the theory of the distribution of primesActa Mathematica, 1916