6
$\begingroup$

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

$\endgroup$
1

1 Answer 1

7
$\begingroup$

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

Generally, the underlying duality can be best understood as surrogate constraint duality, 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 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.)

$\endgroup$
3
  • 1
    $\begingroup$ Huh. I wonder if a smoothed analysis of Simplex with column generation is possible! $\endgroup$
    – Neal Young
    Jan 26 at 3:09
  • $\begingroup$ 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? $\endgroup$ Mar 25 at 12:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Mar 26 at 2:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.