12
$\begingroup$

(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) 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): 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. used as part of an approximation algorithm for the minimum linear arrangement 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 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?

$\endgroup$

migrated from cs.stackexchange.com Oct 15 '15 at 16:53

This question came from our site for students, researchers and practitioners of computer science.

  • 1
    $\begingroup$ The paper Polynomial Interior Point Cutting Plane Methods by John E. Mitchel (Optimization Methods and Software 18(5), 507-534, 2003) looks relevant: tandfonline.com/doi/abs/10.1080/10556780310001607956 $\endgroup$ – Thomas Kalinowski Oct 15 '15 at 21:26
  • 1
    $\begingroup$ 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), link.springer.com/article/10.1007/BF00939559 $\endgroup$ – Thomas Kalinowski Oct 15 '15 at 22:02
  • $\begingroup$ See also Bornstein and Vempala's paper Flow Metrics for a similar LP with polynomially many variables and constraints. $\endgroup$ – Neal Young May 20 '17 at 21:50
  • $\begingroup$ 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. $\endgroup$ – Neal Young May 20 '17 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.