<p>I'm interested in an computational geometry problem that's sensibly expressed as an infinite dimensional 0-1 integer program.  I'm not worried about finding an actual minimum for the objective function, any solution with isn't stupidly big will do.  It thus seems natural to apply an approximation algorithm that starts by running simplex or similar restricted to $[0,1]$. </p>

<p>I'd expect the solutions usually require only a few hundred dimensions, <em>but</em> any naive restriction of the problem space yields millions of dimensions.  As I understand it, good implementations of a linear program solver should be polynomial time in both the dimension and constraints on average cases, but nevertheless this problem chokes GLPK.  Should GLPK really choke on a million dimensions?</p>

<p>I've therefore started looking for less naive restrictions of the problem space, which lead me to LP-type problems. In particular, there is a claim that Clarkson's algorithm applied to linear programs are equivalent to running the simplex algorithm on the dual problem.  In what sense is this true? </p>

<p>I find this claim highly dubious with respect to complexity for several reasons.  First, Clarkson's algorithm does not exploit any $[0,1]$ solutions with fast average case solutions, but merely randomly chooses pivots.  Second, Clarkson's algorithm has running time worse than exponential in the dimension $O(dn + d! d^k \log n)$, which doesn't rule out polynomial time for average cases, but I haven't found that fact yet.</p>

<p>As an aside, any nice examples of improving a restriction of an infinite dimensional linear program over time? </p>

CC BY-SA 3.0
2012-12-02T21:28:21.600Z
I take it your LP has infinitely many variables.  How many constraints does it have?  If you have finitely many constraints, you might consider Lagrangian-relaxation algorithms (or column generation).
Neal Young
CC BY-SA 3.0
2012-12-02T21:30:28.873Z
Clarkson's algorithm combined with the Matousek-Sharir-Welzl technique yields a *sub*-exponential time algorithm for linear program. I believe the bound is something like $\exp(\sqrt{d})$.
Suresh Venkat
CC BY-SA 3.0
2012-12-03T01:15:51.227Z
I'll look up Matousek-Sharir-Welzl then, thanks.  I'm unclear if that's any faster than traditional 0-1 methods based upon simplex or whatever though, but thanks.
Jeff Burdges
CC BY-SA 3.0
2012-12-03T02:08:44.943Z
Yes, I have only finitely many constraints.  Yes, column generation looks very relevant, but I'll need to read about it.  Is your point that the Lagrangian dual problem has only finitely many variables?  I'm unsure how one gets enough information about the Lagrangian dual problem, but maybe that's what you meant by column generation or something.  Thanks!
Jeff Burdges
CC BY-SA 3.0
2012-12-03T16:04:26.210Z
If the problem can be formulated as, say, a fractional covering LP with finitely many constraints, then you can approximately solve it with an iterative Lagrangian-relaxation algorithm as long as, in each iteration, from a given linear combination $v\cdot A$ of the constraints, you can compute a variable such that $v\cdot A^T_j \ge 1$ (given that such a variable exists).  See [this discussion](http://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers) and [Y01](http://scholar.google.com/scholar?cluster=14559865875924909612&hl=en&as_sdt=0,5).
Neal Young
<linear-programming><integer-programming><simplex>
LP-type vs. Approximation
Jeff Burdges
# LP-type vs. Approximation

(Asked by: username_0 on 2012-12-02)

I'm interested in an computational geometry problem that's sensibly expressed as an infinite dimensional 0-1 integer program. I'm not worried about finding an actual minimum for the objective function, any solution with isn't stupidly big will do. It thus seems natural to apply an approximation algorithm that starts by running simplex or similar restricted to $[0,1]$.

I'd expect the solutions usually require only a few hundred dimensions, *but* any naive restriction of the problem space yields millions of dimensions. As I understand it, good implementations of a linear program solver should be polynomial time in both the dimension and constraints on average cases, but nevertheless this problem chokes GLPK. Should GLPK really choke on a million dimensions?

I've therefore started looking for less naive restrictions of the problem space, which lead me to LP-type problems. In particular, there is a claim that Clarkson's algorithm applied to linear programs are equivalent to running the simplex algorithm on the dual problem. In what sense is this true?

I find this claim highly dubious with respect to complexity for several reasons. First, Clarkson's algorithm does not exploit any $[0,1]$ solutions with fast average case solutions, but merely randomly chooses pivots. Second, Clarkson's algorithm has running time worse than exponential in the dimension $O(dn + d! d^k \log n)$, which doesn't rule out polynomial time for average cases, but I haven't found that fact yet.

As an aside, any nice examples of improving a restriction of an infinite dimensional linear program over time?

**Tags:** linear-programming, integer-programming, simplex
> **Comments:**
> **username_1**: I take it your LP has infinitely many variables.  How many constraints does it have?  If you have finitely many constraints, you might consider Lagrangian-relaxation algorithms (or column generation).  
> **username_2**: Clarkson's algorithm combined with the Matousek-Sharir-Welzl technique yields a *sub*-exponential time algorithm for linear program. I believe the bound is something like $\exp(\sqrt{d})$.  
> **username_0**: I'll look up Matousek-Sharir-Welzl then, thanks.  I'm unclear if that's any faster than traditional 0-1 methods based upon simplex or whatever though, but thanks.  
> **username_0**: Yes, I have only finitely many constraints.  Yes, column generation looks very relevant, but I'll need to read about it.  Is your point that the Lagrangian dual problem has only finitely many variables?  I'm unsure how one gets enough information about the Lagrangian dual problem, but maybe that's what you meant by column generation or something.  Thanks!  
> **username_1**: If the problem can be formulated as, say, a fractional covering LP with finitely many constraints, then you can approximately solve it with an iterative Lagrangian-relaxation algorithm as long as, in each iteration, from a given linear combination $v\cdot A$ of the constraints, you can compute a variable such that $v\cdot A^T_j \ge 1$ (given that such a variable exists).  See [this discussion](http://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers) and [Y01](http://scholar.google.com/scholar?cluster=14559865875924909612&hl=en&as_sdt=0,5).  

---

## 0 answers

