4
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ 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). $\endgroup$
    – Neal Young
    Dec 2, 2012 at 21:28
  • 2
    $\begingroup$ 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})$. $\endgroup$
    – Suresh Venkat
    Dec 2, 2012 at 21:30
  • $\begingroup$ 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. $\endgroup$
    – Jeff Burdges
    Dec 3, 2012 at 1:15
  • $\begingroup$ 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! $\endgroup$
    – Jeff Burdges
    Dec 3, 2012 at 2:08
  • 1
    $\begingroup$ 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 and Y01. $\endgroup$
    – Neal Young
    Dec 3, 2012 at 16:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.