Finding points contained within a convex hull.
Hello. I've got a system of linear inequalities representing half-spaces. The half-spaces may or may not form a convex hull. I need to find the integral coordinates that are contained within the convex hull, if there is one. For example, given 0 <= x <= 4 0 <= y <= 3 0 <= 2x - y 0 <= 1.2y - x I want the following (x,y) coordinates [(0,0),(1,1),(1,2),(2,2),(2,3),(3,3)] Anybody have any suggestions, or libraries, for solving this in many dimensions and equations? Thanks Daniel
On Wed, Jun 06, 2007 at 12:23:03PM +1200, Daniel McAllansmith wrote:
Hello.
I've got a system of linear inequalities representing half-spaces. The half-spaces may or may not form a convex hull.
I need to find the integral coordinates that are contained within the convex hull, if there is one.
For example, given 0 <= x <= 4 0 <= y <= 3 0 <= 2x - y 0 <= 1.2y - x
I want the following (x,y) coordinates [(0,0),(1,1),(1,2),(2,2),(2,3),(3,3)]
Anybody have any suggestions, or libraries, for solving this in many dimensions and equations?
If I am not mistaken, this problem is called integer programming and it is NP-complete
Do you simply want the set of coordinates, or do you want to do
something smart with the them (i.e. optimize a function value etc)?
In the first case, with a good starting point and a function that
enumerates all coordinates (by going in a spiral, perhaps), I think
this can be done in O(nm), where n = number of coordinates in the hull
and m = number of conditions to be tested for each point. But that all
depends on the number of coordinates iterated but not in the hull
being constant, i.e. the number of coordinates iterated but filtered
out of the set - I have a hunch that that you'll have to factor in the
number of dimensions somehow - it could well be O(n^dm) or something.
Oh, and you'll need a terminating condition for the coordinate
enumerator - and prove that it is correct.
The latter case is NP-complete ;-) Which might mean that what I said
above is totally wrong and is also an NP-complete problem.
Oh, and BTW, isn't any intersection of half-spaces always a convex
hull? In which case is it not?
// Simon
On 6/6/07, Ilya Tsindlekht
On Wed, Jun 06, 2007 at 12:23:03PM +1200, Daniel McAllansmith wrote:
Hello.
I've got a system of linear inequalities representing half-spaces. The half-spaces may or may not form a convex hull.
I need to find the integral coordinates that are contained within the convex hull, if there is one.
For example, given 0 <= x <= 4 0 <= y <= 3 0 <= 2x - y 0 <= 1.2y - x
I want the following (x,y) coordinates [(0,0),(1,1),(1,2),(2,2),(2,3),(3,3)]
Anybody have any suggestions, or libraries, for solving this in many dimensions and equations?
If I am not mistaken, this problem is called integer programming and it is NP-complete _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Simon Brenner wrote:
Do you simply want the set of coordinates, or do you want to do something smart with the them (i.e. optimize a function value etc)?
In the first case, with a good starting point and a function that enumerates all coordinates (by going in a spiral, perhaps), I think this can be done in O(nm), where n = number of coordinates in the hull and m = number of conditions to be tested for each point. But that all depends on the number of coordinates iterated but not in the hull being constant, i.e. the number of coordinates iterated but filtered out of the set - I have a hunch that that you'll have to factor in the number of dimensions somehow - it could well be O(n^dm) or something. Oh, and you'll need a terminating condition for the coordinate enumerator - and prove that it is correct.
The latter case is NP-complete ;-) Which might mean that what I said above is totally wrong and is also an NP-complete problem.
Oh, and BTW, isn't any intersection of half-spaces always a convex hull? In which case is it not?
If one transforms to get all the extreme vertexes, then you can easily bound each coordinate by the min and max values of that coordinate in the set of vertexes. These bounds on each coordinate give you a large "rectangular" box that contains your polyhedra. Brute force testing all the integer coordinates in the box scales as the volume of the box (some length^d) times the cost of computing the conditions, O(d*m). Cheers, Chris
Thanks for the responses everyone. On Thursday 07 June 2007 00:37, haskell@list.mightyreason.com wrote:
Simon Brenner wrote:
Do you simply want the set of coordinates, or do you want to do something smart with the them (i.e. optimize a function value etc)?
Ultimately optimise several functions over the feasible coordinates, however the functions to optimise are complicated, definitely non-linear, and the linear constraints are already a simplification of non-linear constraints. I was hoping to get a superset of coordinates, filter with the real constraints then optimise each of the target functions.
Oh, and BTW, isn't any intersection of half-spaces always a convex hull? In which case is it not?
Inconsistent constraints, e.g. x>5, y>5, x+y<10
If one transforms to get all the extreme vertexes, then you can easily bound each coordinate by the min and max values of that coordinate in the set of vertexes. These bounds on each coordinate give you a large "rectangular" box that contains your polyhedra.
Since Ilya pointed out that integer linear programming is NP-complete I've been thinking of determining the bounding-box and doing a branch-and-bound search. My idea was to solve the linear constraints twice for each dimension, to maximise and minimise the variable in that dimension. From there I can divide and conquer, hopefully discarding/fixing whole dimensions and reducing the proportion of invalid coordinates. If need be I could even randomly sample the remaining coordinates to keep things tractable. I guess that's not much different from what I was orginally planning - superset, filter, optimise... the superset is just bigger now. How would you go about finding extreme vertices? Would it be quicker than solving the constraints for each max/min? Thanks Daniel
On Jun 6, 2007, at 11:38 PM, Daniel McAllansmith wrote: [Trying to find the domain of a bounded integer linear program]
How would you go about finding extreme vertices? Would it be quicker than solving the constraints for each max/min?
If you're just looking to find bounding coordinates in each dimension, you should be able to do this using linear programming. This will yield non-integer coordinate bounds which you can narrow as appropriate. -Jan-Willem Maessen
Simon Brenner wrote:
Do you simply want the set of coordinates, or do you want to do something smart with the them (i.e. optimize a function value etc)?
In the first case, with a good starting point and a function that enumerates all coordinates (by going in a spiral, perhaps), I think this can be done in O(nm), where n = number of coordinates in the hull and m = number of conditions to be tested for each point. But that all depends on the number of coordinates iterated but not in the hull being constant, i.e. the number of coordinates iterated but filtered out of the set - I have a hunch that that you'll have to factor in the number of dimensions somehow - it could well be O(n^dm) or something. Oh, and you'll need a terminating condition for the coordinate enumerator - and prove that it is correct.
The latter case is NP-complete ;-) Which might mean that what I said above is totally wrong and is also an NP-complete problem.
The number of coordinates in the hull is exponential in the number of bits you use to represent those integers. So, the algorithm and NP-completeness don't contradict each other. The situation is similar to the knapsack problem. Regards, apfelmus
Daniel McAllansmith wrote:
Hello.
I've got a system of linear inequalities representing half-spaces. The half-spaces may or may not form a convex hull.
They could only fail to define a convex volume if they are inconsistent and define an empty set. Though they might define a convex volume of lesser dimension than the space.
I need to find the integral coordinates that are contained within the convex hull, if there is one.
For example, given 0 <= x <= 4 0 <= y <= 3 0 <= 2x - y 0 <= 1.2y - x
I want the following (x,y) coordinates [(0,0),(1,1),(1,2),(2,2),(2,3),(3,3)]
Anybody have any suggestions, or libraries, for solving this in many dimensions and equations?
Thanks Daniel
This FAQ looks useful: http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/polyfaq.html You want to find something like the Volume, so Quoting from: http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node26.html
Is there any efficient algorithm to compute the volume of a convex polytope in $ R^d$?
It is known that computing the volume of a $ V$-polytope (or H-polytope) is #P-hard, see [DF88] and [Kha93]. There are theoretically efficient randomized algorithms to approximate the volume of a convex body [LS93] but no implementation seems to be available.
There is a comparative study [BEF00] of various volume computation algorithms for convex polytopes. It indicates that there is no single algorithm that works well for many different types of polytopes. For ``near'' simple polytopes, triangulation-based algorithms are more efficient. For ``near'' simplicial polytopes, sign-decomposition-based algorithms are better. See the paper for the justification of these claims.
I have never touched a problem like this, but it seems that enumerating the point could be attacked by recursive brute force: * Find an extreme vertex and any other point in the polyhedra (e.g. a different extreme vertex). If the polyhedra is empty this will fail. If the polyhedra is a single point this will find one vertex but no other point, so just check this vertex to see if it has all integer coordinates. * Pick a dimension for which the vertex and other point have different coordinates. Call this dimension's coordinate x. The vertex has value vx and the other point ix. Neither vx nor ix are required to be integers. * Now you make several recursive problems that have different integer values of coordinate x. These subproblems are in two series: ** Increasing series x = a, a+1, a+2, a+3, ... where a = ceil of vx. ** Decreasing series x = b, b-1, b-2, b-3, ... where b = floor of vx. ** Obviously a==b is a special case. ** If you are very clever you can always find a dimensions for which it is obvious that one of the two series is always outside the polygon and need not be checked. But this will also be noticed by the brute force algorithm once that series is run for the first x not equal to vx (which will be either the first or second element of that series depending on whether vx is an integer). * For the two series plug 'x' back into your original set of equations. ** If any equation is False then stop this series of subproblems ** If an equation is True then you can remove it ** If all equations are True, then you have found a integer point in the volume and you can return it and continue with the series of subproblems. ** Otherwise, take the remaining equation compute the vertices of the convex hull (If the new polyhedra is empty then stop this series of subproblems) and iterate this enumeration procedure. ** Note: A subproblem may find no integer points in its convex hull, but that does not stop the algorithm from checking the next value of x in the series. The above looks like a polynomial time complexity algorithm to me. Cheers, Chris
It's been a while, but I believe that you can solve integer programming problems of this type using Groebner bases. (Google for "integer programming with Groebner bases"). I have some Groebner basis code in Haskell at http://www.polyomino.f2s.com/david/haskell/commalg.html
participants (7)
-
apfelmus -
Daniel McAllansmith -
DavidA -
haskell＠list.mightyreason.com -
Ilya Tsindlekht -
Jan-Willem Maessen -
Simon Brenner