<p>(The specific problem I have is stated as precisely as I could in the very last paragraph which starts with a boldface "Question:", up until then the question provides context for it.)</p>

<p>Say we have an undirected vertex-weighted graph $G=(V,E,w)$ on $n$ vertices and want to find an optimal fractional vertex cover. You could use the following linear program (see <a href="http://theory.stanford.edu/~trevisan/cs261/lecture07.pdf">these lecture notes</a>) to do this:</p>

<p>\begin{align}
\text{minimize} &amp;\sum_{v \in V} w(v)\cdot x_v \\
x_v &amp;\leq 1 \qquad \forall v \in V \\
x_v &amp;\geq 0 \qquad \forall v \in V \\
x_u + x_v &amp;\geq 1 \qquad \forall \{u,v\} \in E
\end{align}</p>

<p>That gives you a polynomial time algorithm since there are polynomially many constraints, and there are polynomial time algorithms for linear programming.</p>

<p>However: what if there are superpolynomially many constraints? I have come across claims that you can still solve linear programs of that kind if you only have polynomially many explicit constraints (i.e. a constraint matrix of polynomial size) and for the remaining constraints, you get an implicit specification called a "separation oracle" (see e.g. <a href="http://www.cc.gatech.edu/~vempala/acg/www/18.433/L18.pdf">these notes</a>): such an oracle is a p-time algorithm that can check whether a constraint was violated and if so, produce a violated constraint. This works for the ellipsoid algorithm since the violated constraint defines a separating hyperplane (if I understood that correctly). An example for such a linear program is the one <a href="http://dx.doi.org/10.1109/SFCS.1995.492463">Even et al.</a> used as part of an approximation algorithm for the <a href="https://www.nada.kth.se/~viggo/wwwcompendium/node55.html">minimum linear arrangement</a> problem, where given an edge-weighted, connected, undirected graph $G=(V,E,w)$, we want to find a bijection $\pi: V \to [|V|]$ that minimizes $\sum_{\{u,v\}=e \in E} w(e)\cdot |\pi(u) - \pi(v)|$. The LP is this:</p>

<p>\begin{align}
\text{minimize} &amp;\sum_{e \in E} w(e)\cdot l(e) \\
&amp;\forall U \subseteq V:\, \forall v\in U: \sum_{u \in U} \text{dist}_l(u,v)\geq \frac{1}{4}(|U|^2-1) \\
&amp;\forall e\in E:\,l(e) \geq 0
\end{align}</p>

<p>Here, $\text{dist}_l(u,v)$ is the shortest-path distance between $u$ and $v$ according to $l$. The second line specifies exponentially many constraints, however a separation oracle exists: first, run all-pairs-shortest-paths with respect to $l$, then for each vertex, sort the distances to all other vertices in ascending order. A constraint belonging to the second line is violated iff for some vertex $v$, the first $1\leq k \leq n-1$ distances sum to less than $\frac{(k+1)^2-1}{4}$, and in this case a witness for the violation consists of the endpoints of those shortest paths.</p>

<p>I've also seen claims that instead of the ellipsoid algorithm, one can use interior point methods. From what I've read, "interior point" doesn't refer to a single algorithm (or set of close variants of one algorithm) that solves the linear programming problem, but a number of different algorithms for different classes of problems. The <a href="http://dx.doi.org/10.1007/BF01594937">paper where Ye's algorithm</a> was introduced has extensive references on the development of interior point methods. I was also unable to find references that outline how to use interior point methods to solve implicitly specified linear programs that would have superpolynomial size if specified explicitly.</p>

<p><strong>Question:</strong> Which interior point methods can be used to solve implicitly defined linear programs (which would have superpolynomial size if defined explicitly) in polynomial time, and how does the implicit definition have to be specified?</p>

CC BY-SA 3.0
2015-10-15T21:26:11.927Z
The paper Polynomial Interior Point Cutting Plane Methods by John E. Mitchel (Optimization Methods and Software 18(5),  507-534, 2003) looks relevant: http://www.tandfonline.com/doi/abs/10.1080/10556780310001607956
Thomas Kalinowski
CC BY-SA 3.0
2015-10-15T22:02:41.053Z
Here is another paper doing something very similar to what you describe: Cutting planes and column generation techniques with the projective algorithm by J. L. Goffin and J. P. Vial (Journal of Optimization Theory and Applications 65(3), 409-429, 1990), http://link.springer.com/article/10.1007/BF00939559
Thomas Kalinowski
CC BY-SA 3.0
2017-05-20T21:50:35.063Z
See also Bornstein and Vempala's paper [Flow Metrics](https://doi.org/10.1016/j.tcs.2003.05.003) for a similar LP with polynomially many variables and constraints.
Neal Young
CC BY-SA 3.0
2017-05-20T22:19:27.533Z
Or you could use a Lagrangian-relaxation algorithm.  The dual of your LP is a packing LP: for each $U\subseteq V$ and sequence $\pi$ w/a path $\pi_{uw}$ for each $\{u,w\}\subseteq U$, add var.$~x_\pi \ge 0$.  Let $A_{e\pi}$ be number of paths in $\pi$ edge $e$ occurs in.  Dual is 
$$\max\big\{ \sum_\pi x_\pi (|U(\pi)|^2-1)/4 : (\forall e\in E)~ \sum_{\pi} A_{e\pi} x_\pi \le w(e).\big\}$$
Lagrangian-relaxation needs only an oracle that, given edge wts.$~\ell(e)>0$,
finds $\pi$ minimizing $$\frac{\sum_{e} A_{e\pi}\ell(e) /w(e)}{\sum_{e}\ell(e)(|U(\pi)|^2-1)/4}$$That should be your sep oracle.
Neal Young
<linear-programming>
Linear programming with superpolynomially many constraints?
G. Bach
# Linear programming with superpolynomially many constraints?

(Asked by: username_0 on 2015-10-14)

(The specific problem I have is stated as precisely as I could in the very last paragraph which starts with a boldface "Question:", up until then the question provides context for it.)

Say we have an undirected vertex-weighted graph $G=(V,E,w)$ on $n$ vertices and want to find an optimal fractional vertex cover. You could use the following linear program (see [these lecture notes](http://theory.stanford.edu/~trevisan/cs261/lecture07.pdf)) to do this:

\begin{align}
\text{minimize} &\sum\_{v \in V} w(v)\cdot x\_v \\
x\_v &\leq 1 \qquad \forall v \in V \\
x\_v &\geq 0 \qquad \forall v \in V \\
x\_u + x\_v &\geq 1 \qquad \forall \{u,v\} \in E
\end{align}

That gives you a polynomial time algorithm since there are polynomially many constraints, and there are polynomial time algorithms for linear programming.

However: what if there are superpolynomially many constraints? I have come across claims that you can still solve linear programs of that kind if you only have polynomially many explicit constraints (i.e. a constraint matrix of polynomial size) and for the remaining constraints, you get an implicit specification called a "separation oracle" (see e.g. [these notes](http://www.cc.gatech.edu/~vempala/acg/www/18.433/L18.pdf)): such an oracle is a p-time algorithm that can check whether a constraint was violated and if so, produce a violated constraint. This works for the ellipsoid algorithm since the violated constraint defines a separating hyperplane (if I understood that correctly). An example for such a linear program is the one [Even et al.](http://dx.doi.org/10.1109/SFCS.1995.492463) used as part of an approximation algorithm for the [minimum linear arrangement](https://www.nada.kth.se/~viggo/wwwcompendium/node55.html) problem, where given an edge-weighted, connected, undirected graph $G=(V,E,w)$, we want to find a bijection $\pi: V \to [|V|]$ that minimizes $\sum\_{\{u,v\}=e \in E} w(e)\cdot |\pi(u) - \pi(v)|$. The LP is this:

\begin{align}
\text{minimize} &\sum\_{e \in E} w(e)\cdot l(e) \\
&\forall U \subseteq V:\, \forall v\in U: \sum\_{u \in U} \text{dist}\_l(u,v)\geq \frac{1}{4}(|U|^2-1) \\
&\forall e\in E:\,l(e) \geq 0
\end{align}

Here, $\text{dist}\_l(u,v)$ is the shortest-path distance between $u$ and $v$ according to $l$. The second line specifies exponentially many constraints, however a separation oracle exists: first, run all-pairs-shortest-paths with respect to $l$, then for each vertex, sort the distances to all other vertices in ascending order. A constraint belonging to the second line is violated iff for some vertex $v$, the first $1\leq k \leq n-1$ distances sum to less than $\frac{(k+1)^2-1}{4}$, and in this case a witness for the violation consists of the endpoints of those shortest paths.

I've also seen claims that instead of the ellipsoid algorithm, one can use interior point methods. From what I've read, "interior point" doesn't refer to a single algorithm (or set of close variants of one algorithm) that solves the linear programming problem, but a number of different algorithms for different classes of problems. The [paper where Ye's algorithm](http://dx.doi.org/10.1007/BF01594937) was introduced has extensive references on the development of interior point methods. I was also unable to find references that outline how to use interior point methods to solve implicitly specified linear programs that would have superpolynomial size if specified explicitly.

**Question:** Which interior point methods can be used to solve implicitly defined linear programs (which would have superpolynomial size if defined explicitly) in polynomial time, and how does the implicit definition have to be specified?

**Tags:** linear-programming
> **Comments:**
> **username_1**: The paper Polynomial Interior Point Cutting Plane Methods by John E. Mitchel (Optimization Methods and Software 18(5),  507-534, 2003) looks relevant: http://www.tandfonline.com/doi/abs/10.1080/10556780310001607956  
> **username_1**: Here is another paper doing something very similar to what you describe: Cutting planes and column generation techniques with the projective algorithm by J. L. Goffin and J. P. Vial (Journal of Optimization Theory and Applications 65(3), 409-429, 1990), http://link.springer.com/article/10.1007/BF00939559  
> **username_2**: See also Bornstein and Vempala's paper [Flow Metrics](https://doi.org/10.1016/j.tcs.2003.05.003) for a similar LP with polynomially many variables and constraints.  
> **username_2**: Or you could use a Lagrangian-relaxation algorithm.  The dual of your LP is a packing LP: for each $U\subseteq V$ and sequence $\pi$ w/a path $\pi_{uw}$ for each $\{u,w\}\subseteq U$, add var.$~x_\pi \ge 0$.  Let $A_{e\pi}$ be number of paths in $\pi$ edge $e$ occurs in.  Dual is  $$\max\big\{ \sum_\pi x_\pi (|U(\pi)|^2-1)/4 : (\forall e\in E)~ \sum_{\pi} A_{e\pi} x_\pi \le w(e).\big\}$$ Lagrangian-relaxation needs only an oracle that, given edge wts.$~\ell(e)>0$, finds $\pi$ minimizing $$\frac{\sum_{e} A_{e\pi}\ell(e) /w(e)}{\sum_{e}\ell(e)(|U(\pi)|^2-1)/4}$$That should be your sep oracle.  

---

## 0 answers

