[Haskell-cafe] Finding points contained within a convex hull.
Daniel McAllansmith
dm.maillists at gmail.com
Wed Jun 6 23:38:04 EDT 2007
Thanks for the responses everyone.
On Thursday 07 June 2007 00:37, haskell at 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
More information about the Haskell-Cafe
mailing list