What is the quickest way to find a point inside a linear feasible space? (Defined by the intersection of several hyperplanes and halfspaces). I want to be able to choose an initial point in the original convex space, discover a certain neighborhood around it (not convex but can be written as the union of some convex spaces defined by by the intersection of several halfspaces) using a procedure that depends on the point I have, and then I need to choose another point in the original space but not in the neighborhood already explored. I need to keep doing that until the space is exhausted (It should be exhausted eventually). Basically, I have a convex space $S$, I need loop until $S=\phi$ while doing the following: Choose $x\in S$, Find $N$ around $x$, and then $S \leftarrow S - N$ Any help is appreciated.
|
|
||||
|
|
|
Finding a single feasible point is traditionally done by phase 1 of the simplex algorithm. http://en.wikipedia.org/wiki/Simplex_algorithm#Finding_an_initial_canonical_tableau This means that you can do it by calling any routine for linear programming, just by putting the objective function to zero. Covering the feasible domain by balls of fixed radius $r$ whose midpoints are feasible is much harder, though, as exccluding a ball constitutes a nonconvex domain. There are algorithms for enumerating all vertices of a bounded polyhedron given by equations and inequalities (their number typically grows exponentially with the dimension, though). After having all vertices, the feasible set consists just of their convex combinations, so this can be used to samle inside. But unless the polyhedron is a simplex, different convex combinations may give the same point, so one would need to add a reject facility when generating a minimal covering. |
|||||||
|
|
There is a software called PORTA that can enumerate all the points that are feasible in a set of linear inequalities and equalities. http://www.iwr.uni-heidelberg.de/groups/comopt/software/PORTA/ enjoy it! |
|||
|
