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