[back] [prev] [next] [index] [root]

<p>&nbsp;<p>
<hr noshade size="5">
<h2><a name="SimplexInit"></a>
SimplexInit
</h2>

Initializes the enumeration of all integral points contained in a
bounded simplex.

<p><p>

<h3>
Syntax:
</h3>
<pre>s := SimplexInit(A, b [ , delta ]);</pre>

<p>

<table>
<tr>
<td>Simplex</td>
<td><pre>  s  </pre></td>
<td></td>
</tr>
<tr>
<td>real matrix</td>
<td><pre>  A  </pre></td>
<td>A \in R^{m \times n}</td>
</tr>
<tr>
<td>real matrix</td>
<td><pre>  b  </pre></td>
<td>b \in R^{m}</td>
</tr>
<tr>
<td>real</td>
<td><pre>  delta  </pre></td>
<td>should be 1+\epsilon</td>
</tr>
</table>

<p>


See also:&nbsp;&nbsp;<a href="kashref.html#SimplexNext">SimplexNext</a>, <a href="kashref.html#SimplexElt">SimplexElt</a>, <a href="kashref.html#SimplexReInit">SimplexReInit</a>

<p>

<h3>
Description:
</h3>
Initializes the enumeration of all integral points contained in an
bounded simplex. This function performs Fourier-Motzkin elimination
to produce a triangular system. Be careful: The size of the
system may be exponential in the number of initial constraints.

A simplex <tt> s</tt> if defined as <tt> s</tt> := { x\in R^n |  <tt> A</tt>x &lt;=  <tt> b</tt> }
where  &lt;=  means  &lt;=  componentwise. If <tt> delta</tt> is given,
it is used as a correction for round-off errors. You may
get points outside of <tt> s</tt>.

<p><p>

<p>
<hr>
<p>
<h3>
Example:
</h3>
Find all x,y in {\Bbb Z}^2|{ &gt;=  0} subject to x+y  &lt;=  3: 
<pre>

kash> A := Mat(R, [[1,1],[-1, 0],[0,-1]]);
[ 1  1]
[-1  0]
[ 0 -1]
kash> b := MatTrans(Mat(R, [[3, 0, 0]]));
[3]
[0]
[0]
kash> s := SimplexInit(A, b);;
kash> while SimplexNext(s) do Print(SimplexElt(s), "\n"); od;
> [ 0, 0 ]
[ 1, 0 ]
[ 2, 0 ]
[ 3, 0 ]
[ 0, 1 ]
[ 1, 1 ]
[ 2, 1 ]
[ 0, 2 ]
[ 1, 2 ]
[ 0, 3 ]

</pre>

<p>


<hr>

<p>
<a href="../kashref.html"><- back</a>[back] [prev] [next] [index] [root]