<p>During the solution of some computational problem, we have arrived at a linear program of the following form:</p>
<p><span class="math-container">\begin{align*}
\text{maximize} ~~  c x
\\
\text{subject to} ~~  A x \leq b,     x \geq 0
\end{align*}</span></p>
<p>where the number of variables in <span class="math-container">$x$</span> is exponential in the problem size, but the number of constraints is polynomial.</p>
<p>The most common technique we know for solving such problems is through its dual:</p>
<p><span class="math-container">\begin{align*}
\text{minimize} ~~ b y
\\
\text{subject to} ~~ A^T y \geq c, y\geq 0
\end{align*}</span></p>
<p>The dual has an exponential number of constraints, but it is often possible to design a <a href="https://en.wikipedia.org/wiki/Separation_oracle" rel="nofollow noreferrer">separation oracle</a> - a function that decides, given a vector <span class="math-container">$y$</span>, whether it satisfies all constraints, and if not - returns a violated constraint. The ellipsoid method can solve the dual using a polynomial number of calls to this oracle; then, the duality theorem can be used to find a solution to the primal LP. Sometimes, there exists an approximate separation oracle - given a vector <span class="math-container">$y$</span>, it either finds a violated constraint or asserts that all constraints are satisfied approximately; then, using the ellipsoid method and the duality theorem, we can find an approximate solution to the primal LP.</p>
<p>In our case, we could not find a suitable exact or approximate separation oracle; we suspect that desigining such an oracle may be NP-hard. So our questions are:</p>
<ol>
<li><p>Are there techniques for approximately solving the original LP directly in polynomial time, without going through the dual? <sub>Note that, if the original LP has <span class="math-container">$m$</span> constraints, it has an optimal solution in which at most <span class="math-container">$m$</span> variables are nonzero; as <span class="math-container">$m$</span> is polynomial in the problem size, the solution can be output in polynomial time.</sub></p>
</li>
<li><p>Are there techniques for proving that solving the original LP, exactly or approximately, is NP-hard?</p>
</li>
</ol>
<p>We will be happy to receive references to papers that use such techniques.</p>

CC BY-SA 4.0
2023-09-06T13:37:41.433Z
For your first question: maybe dimensionality reduction techniques (which are often linear) could be applied to reduce the number of variables, up to some approximation?
One has to be careful to make sure that there are reduced solutions that are sufficiently close to optimal solutions of the LP.
GBathie
CC BY-SA 4.0
2023-09-06T14:53:26.913Z
@GBathie you mean the techniques used in machine learning? I have used some such techniques in the past, but I never saw such a technique with a theoretical guarantee for the approximation ratio - they are usually checked by simulations. Do you know of a dimensionality reduction technique that has a theoretical approximation guarantee?
Erel Segal-Halevi
CC BY-SA 4.0
2023-09-06T17:24:55.490Z
Shameless plug: we had a similar phenomenon when constructing LP whose variables were an exponential size family of subgraph of a data graph $G$. We observed that when $G$ is of treewidth k, then we could rewrite the LP into an LP having the same value but having "only" 2^k*poly(|G|) variables. We tried to abstract it away into a framework where the variables are the answer to a database query. This ended up in this paper: https://arxiv.org/abs/2210.16694. The framework may be hard to follow in the end, but maybe you have similar structure. We can discuss it offline if needed.
holf
CC BY-SA 4.0
2023-09-06T19:20:01.697Z
If I take the interpretation that your matrix is implicitly specified, so the input itself is poly(n) length for a parameter n while the derived matrix is poly(n) by exp(n), then the number of variables is exp(n), so what counts as a "solution" to you? (If a solver must return a feasible setting to all the variables, it must take at least exp(n) time.) Maybe you're allowed to return a small circuit whose truth table is the assignment?
If instead the matrix *is* the input, then the input length is already exp(n), and so the LP can obviously be solved in "polynomial time in the input"...
Ryan Williams
CC BY-SA 4.0
2023-09-06T19:32:13.207Z
@RyanWilliams Since there are poly(n) constraints, there exists an optimal solution in which only poly(n) variables are nonzero, so it can be output in poly(n) time.
Erel Segal-Halevi
CC BY-SA 4.0
2023-09-08T06:53:53.960Z
@holf I will be happy to discuss offline. How can I contact you? (my email is erelsgl@gmail.com)
Erel Segal-Halevi
CC BY-SA 4.0
2023-09-12T13:24:03.887Z
If the LP is a (possibly mixed) packing/covering LP, Lagrangian-relaxation (MWU) algorithms can be used instead of Ellipsoid.  See e.g. https://cstheory.stackexchange.com/questions/51003/is-there-a-simplex-like-algorithm-that-can-be-used-with-a-separation-oracle/51032 and https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388 .
Neal Young
<reference-request><approximation-algorithms><linear-programming>
Techniques for solving huge linear programs
Erel Segal-Halevi
# Techniques for solving huge linear programs

(Asked by: username_0 on 2023-09-06)

During the solution of some computational problem, we have arrived at a linear program of the following form:

\begin{align\*}
\text{maximize} ~~ c x
\\
\text{subject to} ~~ A x \leq b, x \geq 0
\end{align\*}

where the number of variables in $x$ is exponential in the problem size, but the number of constraints is polynomial.

The most common technique we know for solving such problems is through its dual:

\begin{align\*}
\text{minimize} ~~ b y
\\
\text{subject to} ~~ A^T y \geq c, y\geq 0
\end{align\*}

The dual has an exponential number of constraints, but it is often possible to design a [separation oracle](https://en.wikipedia.org/wiki/Separation_oracle) - a function that decides, given a vector $y$, whether it satisfies all constraints, and if not - returns a violated constraint. The ellipsoid method can solve the dual using a polynomial number of calls to this oracle; then, the duality theorem can be used to find a solution to the primal LP. Sometimes, there exists an approximate separation oracle - given a vector $y$, it either finds a violated constraint or asserts that all constraints are satisfied approximately; then, using the ellipsoid method and the duality theorem, we can find an approximate solution to the primal LP.

In our case, we could not find a suitable exact or approximate separation oracle; we suspect that desigining such an oracle may be NP-hard. So our questions are:

1. Are there techniques for approximately solving the original LP directly in polynomial time, without going through the dual? Note that, if the original LP has $m$ constraints, it has an optimal solution in which at most $m$ variables are nonzero; as $m$ is polynomial in the problem size, the solution can be output in polynomial time.
2. Are there techniques for proving that solving the original LP, exactly or approximately, is NP-hard?

We will be happy to receive references to papers that use such techniques.

**Tags:** reference-request, approximation-algorithms, linear-programming
> **Comments:**
> **username_1**: For your first question: maybe dimensionality reduction techniques (which are often linear) could be applied to reduce the number of variables, up to some approximation? One has to be careful to make sure that there are reduced solutions that are sufficiently close to optimal solutions of the LP.  
> **username_0**: @GBathie you mean the techniques used in machine learning? I have used some such techniques in the past, but I never saw such a technique with a theoretical guarantee for the approximation ratio - they are usually checked by simulations. Do you know of a dimensionality reduction technique that has a theoretical approximation guarantee?  
> **username_2**: Shameless plug: we had a similar phenomenon when constructing LP whose variables were an exponential size family of subgraph of a data graph $G$. We observed that when $G$ is of treewidth k, then we could rewrite the LP into an LP having the same value but having "only" 2^k*poly(|G|) variables. We tried to abstract it away into a framework where the variables are the answer to a database query. This ended up in this paper: https://arxiv.org/abs/2210.16694. The framework may be hard to follow in the end, but maybe you have similar structure. We can discuss it offline if needed.  
> **username_3**: If I take the interpretation that your matrix is implicitly specified, so the input itself is poly(n) length for a parameter n while the derived matrix is poly(n) by exp(n), then the number of variables is exp(n), so what counts as a "solution" to you? (If a solver must return a feasible setting to all the variables, it must take at least exp(n) time.) Maybe you're allowed to return a small circuit whose truth table is the assignment? If instead the matrix *is* the input, then the input length is already exp(n), and so the LP can obviously be solved in "polynomial time in the input"...  
> **username_0**: @RyanWilliams Since there are poly(n) constraints, there exists an optimal solution in which only poly(n) variables are nonzero, so it can be output in poly(n) time.  
> **username_0**: @holf I will be happy to discuss offline. How can I contact you? (my email is erelsgl@gmail.com)  
> **username_4**: If the LP is a (possibly mixed) packing/covering LP, Lagrangian-relaxation (MWU) algorithms can be used instead of Ellipsoid.  See e.g. https://cstheory.stackexchange.com/questions/51003/is-there-a-simplex-like-algorithm-that-can-be-used-with-a-separation-oracle/51032 and https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388 .  

---

## 0 answers

