<p>I'm not sure if you would consider the algorithms I'll discuss here  &quot;Simplex-like&quot; (but see the comment about column generation at the end).</p>
<p>If you have a weak separation oracle for a packing/covering linear  program, you can find a <span class="math-container">$(1+\epsilon)$</span>-approximate solution to it by applying a primal-dual <a href="https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388#14388">Lagrangian-relaxation / multiplicative-weights-update algorithm</a> to the linear-programming dual.  A typical algorithm will iterate <span class="math-container">$O(n\log(n)/\epsilon^2)$</span> times, where <span class="math-container">$n$</span> is the number of variables.  Each iteration requires one call to the separation oracle.</p>
<p>For example, suppose you want to solve the fractional Element Packing problem:</p>
<blockquote>
<p><strong>input:</strong> <em>a collection of sets from a universe of <span class="math-container">$n$</span> elements, and a budget <span class="math-container">$k$</span></em><br />
<strong>output:</strong> <em>an element packing -- an assignment of non-negative weights to the elements -- of total weight <span class="math-container">$k$</span>, such that the weight assigned to each set is at most 1</em></p>
</blockquote>
<p>The linear-programming dual is the fractional Set Cover problem:</p>
<blockquote>
<p><strong>input:</strong> <em>a collection of sets from a universe of <span class="math-container">$n$</span> elements</em><br />
<strong>output:</strong> <em>a fractional set cover of size at most <span class="math-container">$k$</span></em></p>
</blockquote>
<p>A standard Lagrangian-relaxation for fractional Set Cover computes a <span class="math-container">$(1+O(\epsilon))$</span>-approximate primal-dual pair by iterating <span class="math-container">$O(n\log(n)/\epsilon^2)$</span> times. Essentially, the algorithm &quot;accesses&quot; the input only by requiring a black-box solution to the the following relaxed subproblem in each iteration:</p>
<blockquote>
<p><strong>input:</strong> <em>an assignment of non-negative weights to the elements, with total weight <span class="math-container">$k$</span></em><br />
<strong>output:</strong> <em>either (i) a set that contains elements of total weight at least <span class="math-container">$1-\epsilon$</span>, or (ii) a proof that every set has total weight at most <span class="math-container">$1$</span></em></p>
</blockquote>
<p>Equivalently, in terms of the original Element Packing problem:</p>
<blockquote>
<p><strong>input:</strong> <em>a tentative element packing of total weight <span class="math-container">$k$</span></em><br />
<strong>output:</strong> <em>either (i) a nearly violated constraint (a set that contains elements of total weight at least <span class="math-container">$1-\epsilon$</span>), or (ii) a proof that the element packing is feasible</em></p>
</blockquote>
<p>Note that this is what a weak separation oracle for the Element Packing problem computes.  So the algorithm can use the separation oracle to compute the approximate solution, as desired.</p>
<p>Recall that <span class="math-container">$n$</span> is the number of elements, so the algorithm works in polynomial time even in the scenario where there the set constraints are implicitly defined and there are an arbitrary (say exponential) number of them, as long as you have a poly-time oracle for the relaxed subproblem in each iteration.</p>
<p>The &quot;naive&quot; implementations can often be sped up by clever implementation.  See for example the nearly linear-time algorithms for various implicitly defined packing/covering LPs by e.g. <a href="https://scholar.google.com/scholar?hl=en&amp;as_sdt=0%2C22&amp;q=author%3Achekuri+author%3Aquanrud+linear&amp;btnG=" rel="noreferrer">Chekuri and Quanrud</a>.</p>
<p>Generally, the underlying duality can be best understood as <a href="https://scholar.google.com/scholar?hl=en&amp;as_sdt=0%2C22&amp;q=%22surrogate+constraint+duality%22&amp;btnG=" rel="noreferrer">surrogate constraint duality</a>, that is, each subproblem is obtained from the original problem by relaxing it, specifically by replacing a collection of constraints by a single weighted combination of those constraints.</p>
<p>One historical precursor to modern Lagrangian-relaxation / multiplicative-weights-update algorithms is the Simplex algorithm, augmented with <a href="https://en.wikipedia.org/wiki/Column_generation" rel="noreferrer">column generation</a> for the case when there are many more variables than constraints.  (Briefly: instead of having explicit columns for all variables, maintain columns only for variables that have positive value.  With each pivot, find the column to introduce into the basis by using the oracle.)</p>

CC BY-SA 4.0
2022-01-26T03:09:19.433Z
Huh. I wonder if a smoothed analysis of Simplex with column generation is possible!
Neal Young
CC BY-SA 4.0
2022-03-25T12:15:15.543Z
Thanks a lot for the detailed answer here and in the link. I see that both answers focus on  packing and covering problems. Is there a generalization for an arbitrary linear program given by a separation oracle?
Erel Segal-Halevi
CC BY-SA 4.0
2022-03-26T02:47:57.063Z
Well I guess the closest I know would be Simplex with column generation (on the dual) but I'm not an expert on general (non-packing/covering) methods.  There are various generalization of packing/covering algorithms (e.g. mixed packing covering, non-linear but appropriately convex problems, solutions for general LPs that meet the constraints only in some approximate sense), but not really to full LPs as far as I know.
Neal Young
CC BY-SA 4.0
2022-01-25T14:41:12.527Z
2022-01-25T22:19:12.663Z
2022-01-25T22:19:12.663Z
Neal Young
<p>Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the <a href="https://arxiv.org/abs/cs/0111050" rel="nofollow noreferrer">smoothed analysis framework of Spielman and Teng</a> provides a convincing explanation why this is so.</p>
<p>But the ellipsoid method has a different advantage: it can solve problems with a huge number of constraints, without listing all the constraints, by using a <a href="https://en.wikipedia.org/wiki/Separation_oracle" rel="nofollow noreferrer">separation oracle</a>. The run-time is polynomial, but with a high degree and not very efficient in practice.</p>
<p>My question: is there an algorithm, similar to the Simplex method, that can be used to solve linear programs specified by a separation oracle, and which has a smoothed polynomial run-time?</p>

CC BY-SA 4.0
2022-01-25T14:53:34.620Z
somewhat related: https://scicomp.stackexchange.com/questions/21538/implementation-of-lp-with-separation-oracle
Neal Young
<linear-programming><oracles><simplex><smoothed-analysis>
Is there a simplex-like algorithm that can be used with a separation oracle?
Erel Segal-Halevi
# Is there a simplex-like algorithm that can be used with a separation oracle?

(Asked by: username_0 on 2022-01-19)

Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the [smoothed analysis framework of Spielman and Teng](https://arxiv.org/abs/cs/0111050) provides a convincing explanation why this is so.

But the ellipsoid method has a different advantage: it can solve problems with a huge number of constraints, without listing all the constraints, by using a [separation oracle](https://en.wikipedia.org/wiki/Separation_oracle). The run-time is polynomial, but with a high degree and not very efficient in practice.

My question: is there an algorithm, similar to the Simplex method, that can be used to solve linear programs specified by a separation oracle, and which has a smoothed polynomial run-time?

**Tags:** linear-programming, oracles, simplex, smoothed-analysis
> **Comments:**
> **username_1**: somewhat related: https://scicomp.stackexchange.com/questions/21538/implementation-of-lp-with-separation-oracle  

---

## 1 answers

### Answer by username_1 on 2022-01-25. Score: 8 | Accepted answer

I'm not sure if you would consider the algorithms I'll discuss here "Simplex-like" (but see the comment about column generation at the end).

If you have a weak separation oracle for a packing/covering linear program, you can find a $(1+\epsilon)$-approximate solution to it by applying a primal-dual [Lagrangian-relaxation / multiplicative-weights-update algorithm](https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388#14388) to the linear-programming dual. A typical algorithm will iterate $O(n\log(n)/\epsilon^2)$ times, where $n$ is the number of variables. Each iteration requires one call to the separation oracle.

For example, suppose you want to solve the fractional Element Packing problem:

> **input:** *a collection of sets from a universe of $n$ elements, and a budget $k$*  
> **output:** *an element packing -- an assignment of non-negative weights to the elements -- of total weight $k$, such that the weight assigned to each set is at most 1*

The linear-programming dual is the fractional Set Cover problem:

> **input:** *a collection of sets from a universe of $n$ elements*  
> **output:** *a fractional set cover of size at most $k$*

A standard Lagrangian-relaxation for fractional Set Cover computes a $(1+O(\epsilon))$-approximate primal-dual pair by iterating $O(n\log(n)/\epsilon^2)$ times. Essentially, the algorithm "accesses" the input only by requiring a black-box solution to the the following relaxed subproblem in each iteration:

> **input:** *an assignment of non-negative weights to the elements, with total weight $k$*  
> **output:** *either (i) a set that contains elements of total weight at least $1-\epsilon$, or (ii) a proof that every set has total weight at most $1$*

Equivalently, in terms of the original Element Packing problem:

> **input:** *a tentative element packing of total weight $k$*  
> **output:** *either (i) a nearly violated constraint (a set that contains elements of total weight at least $1-\epsilon$), or (ii) a proof that the element packing is feasible*

Note that this is what a weak separation oracle for the Element Packing problem computes. So the algorithm can use the separation oracle to compute the approximate solution, as desired.

Recall that $n$ is the number of elements, so the algorithm works in polynomial time even in the scenario where there the set constraints are implicitly defined and there are an arbitrary (say exponential) number of them, as long as you have a poly-time oracle for the relaxed subproblem in each iteration.

The "naive" implementations can often be sped up by clever implementation. See for example the nearly linear-time algorithms for various implicitly defined packing/covering LPs by e.g. [Chekuri and Quanrud](https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=author%3Achekuri+author%3Aquanrud+linear&btnG=).

Generally, the underlying duality can be best understood as [surrogate constraint duality](https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=%22surrogate+constraint+duality%22&btnG=), that is, each subproblem is obtained from the original problem by relaxing it, specifically by replacing a collection of constraints by a single weighted combination of those constraints.

One historical precursor to modern Lagrangian-relaxation / multiplicative-weights-update algorithms is the Simplex algorithm, augmented with [column generation](https://en.wikipedia.org/wiki/Column_generation) for the case when there are many more variables than constraints. (Briefly: instead of having explicit columns for all variables, maintain columns only for variables that have positive value. With each pivot, find the column to introduce into the basis by using the oracle.)

> **Comments:**
> **username_1**: Huh. I wonder if a smoothed analysis of Simplex with column generation is possible!  
> **username_0**: Thanks a lot for the detailed answer here and in the link. I see that both answers focus on  packing and covering problems. Is there a generalization for an arbitrary linear program given by a separation oracle?  
> **username_1**: Well I guess the closest I know would be Simplex with column generation (on the dual) but I'm not an expert on general (non-packing/covering) methods.  There are various generalization of packing/covering algorithms (e.g. mixed packing covering, non-linear but appropriately convex problems, solutions for general LPs that meet the constraints only in some approximate sense), but not really to full LPs as far as I know.  

---

