Thanks for the responses everyone. On Thursday 07 June 2007 00:37, [EMAIL PROTECTED] 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
