I have two vectors which specify the bounds $x_{min}$ and $x_{max}$ of the sample space. Also, it has to satisfy the linear constraint $Ax \leq b$.

How to generate an evenly spaced set of points, with some control over grid spacing, which satisfy these constraints and this includes both the boundaries and the interior? In other words, how do I generate a 'mesh' for a feasibility region? The feasibility problem in this case

\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & 1 \\ & \text{subject to} & & Ax \leq b \\ &&& x_{min} \leq x \leq x_{max} \end{aligned} \end{equation*}

  • 1
    $\begingroup$ Do you mean vertex enumeration? Can you specify which set of points you want? $\endgroup$ – Kirill Feb 21 '17 at 1:20
  • $\begingroup$ The entire feasible region, which includes the interior and the boundaries. $\endgroup$ – gpavanb Feb 21 '17 at 2:00
  • 5
    $\begingroup$ If you want all of the points (interior and boundary), then you can only define the region implicitly, which you have done in your problem statement. Taking your $x$'s as real numbers, the feasible region has (in general) an uncountable number of elements, so you can't store it directly. In order to mesh your feasible region, you might try an n-dimensional delaunay of the polyhedron vertices (see @Kirill's comment above), then use a mesh-refinement technique to generate a sane distribution of interior points. This will be expensive, but might work if you really need all this information. $\endgroup$ – Tyler Olsen Feb 21 '17 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.