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 - 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.

  • $\begingroup$ 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. $\endgroup$
    – GBathie
    Sep 6, 2023 at 13:37
  • $\begingroup$ @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? $\endgroup$ Sep 6, 2023 at 14:53
  • $\begingroup$ 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: 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. $\endgroup$
    – holf
    Sep 6, 2023 at 17:24
  • 4
    $\begingroup$ 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"... $\endgroup$ Sep 6, 2023 at 19:20
  • 1
    $\begingroup$ If the LP is a (possibly mixed) packing/covering LP, Lagrangian-relaxation (MWU) algorithms can be used instead of Ellipsoid. See e.g. cstheory.stackexchange.com/questions/51003/… and cstheory.stackexchange.com/questions/4697/… . $\endgroup$
    – Neal Young
    Sep 12, 2023 at 13:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.