| 1 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 2 |
% |
| 3 |
% 4ti2 User Guide, Advanced guide |
| 4 |
% |
| 5 |
% $Id$ |
| 6 |
% |
| 7 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 8 |
|
| 9 |
\chapter{Advanced guide} |
| 10 |
|
| 11 |
In this part, we deal with several more advanced problem |
| 12 |
specifications in \FourTiTwo{}. |
| 13 |
|
| 14 |
First we introduce \emph{affine systems} and their encodings. In |
| 15 |
fact, affine systems are the basic objects used in \FourTiTwo{}, |
| 16 |
since every linear system is transformed into an affine system. |
| 17 |
However, in the integer situation, it is not always possible to |
| 18 |
transform an affine system back into a linear system without adding |
| 19 |
variables or modulo constraints. |
| 20 |
|
| 21 |
%% Next, we demonstrate how one can exploit bounds on integer variables |
| 22 |
%% to truncate the solution set. |
| 23 |
|
| 24 |
%% Again, we use a few sample problems to demonstrate how to use |
| 25 |
%% \FourTiTwo{}. After working through this part, you should know about |
| 26 |
%% how to run the following functions on affine systems: |
| 27 |
%% \begin{itemize} |
| 28 |
%% \item \File{qsolve}, \File{rays}, \File{circuits} |
| 29 |
%% \item \File{zsolve}, \File{hilbert}, \File{graver} |
| 30 |
%% \item \File{markov}, \File{groebner}, \File{normalform}, \File{minimize} |
| 31 |
%% \end{itemize} |
| 32 |
|
| 33 |
|
| 34 |
\section{Affine systems and their encodings} |
| 35 |
|
| 36 |
%% In \FourTiTwo, the definition of an \emph{affine system} is slightly |
| 37 |
%% different for the continuous and for the integer situation. In fact, |
| 38 |
%% the definition for the integer case is simply the integer analogue |
| 39 |
%% to the definition for the continuous case. |
| 40 |
|
| 41 |
%% \subsection{Continuous affine systems} |
| 42 |
|
| 43 |
%% Let $a+\Lattice_{\R}$ be a linear affine space given by the vector |
| 44 |
%% $a$ and by generators for the linear space $\Lattice_{\R}$. We wish |
| 45 |
%% to find a finite sign-compatible description for the set of all |
| 46 |
%% vectors $x\in a+\Lattice_{\R}$. |
| 47 |
|
| 48 |
%% \subsection{Integer affine systems} |
| 49 |
|
| 50 |
Let $a+\Lattice_{\Z}$ be an ``integer linear affine space'' given by |
| 51 |
the vector $a\in\Z^n$ and by generators for the lattice |
| 52 |
$\Lattice_{\Z}\subseteq\Z^n$. We wish to find a finite |
| 53 |
sign-compatible description for the set of all (integer) vectors |
| 54 |
$x\in a+\Lattice_{\Z}$. |
| 55 |
|
| 56 |
%% \subsection{Specifying an affine system in \FourTiTwo{}} |
| 57 |
|
| 58 |
% Currently, only homogeneous affine systems can be solved in |
| 59 |
% \FourTiTwo{} over $\R$ and over $\Z$ using the functions |
| 60 |
% \File{qsolve} and \File{zsolve}, respectively. In order to call |
| 61 |
% these functions, |
| 62 |
%% One needs to specify an affine system to |
| 63 |
%% \FourTiTwo. |
| 64 |
|
| 65 |
As an example, let consider the linear space $\Lattice_{\R}$ and the |
| 66 |
lattice $\Lattice_{\Z}$ both spanned by the two vectors $(1,-2,1,0)$ |
| 67 |
and $(2,-3,-0,1)$. Moreover, consider the sign-constraints |
| 68 |
$(1,2,2,0)$. Thus, we are looking for a finite explicit |
| 69 |
sign-compatible description for all $x$ that can be written as |
| 70 |
\[ |
| 71 |
x=\left( |
| 72 |
\begin{array}{rr} |
| 73 |
1 & 2\\ |
| 74 |
-2 & -3\\ |
| 75 |
1 & 0\\ |
| 76 |
0 & 1\\ |
| 77 |
\end{array} |
| 78 |
\right)\lambda, |
| 79 |
\] |
| 80 |
with $\lambda\in\R^2$ and $\lambda\in\Z^2$, respectively. |
| 81 |
|
| 82 |
In order to solve this affine system using %% \File{qsolve} or |
| 83 |
\File{zsolve}, we create the following input files to encode the |
| 84 |
affine system: |
| 85 |
\begin{center} |
| 86 |
\begin{tabular}{|l|l|} |
| 87 |
\hline |
| 88 |
\text{ affine.lat } & \text{ affine.sign }\\ |
| 89 |
\hline |
| 90 |
$\begin{array}{rrrrrr}& 2 & 4 & & &\\& 1 & -1 & 1 & 0 &\\& 2 & -3 & 0 & 1 &\\ \end{array}$ & |
| 91 |
$\begin{array}{rrrrrr}& 1 & 4 & & &\\& 1 & 2 & 2 & 0 &\\ \\ \\\end{array}$\\ |
| 92 |
\hline |
| 93 |
\end{tabular} |
| 94 |
\end{center} |
| 95 |
and then call |
| 96 |
%% \begin{center} |
| 97 |
%% {\tt ./qsolve affine} |
| 98 |
%% \end{center} |
| 99 |
%% %%%%%%%%%%%%%%%%% This doesn't work in 4ti2 1.6.2 |
| 100 |
%% and |
| 101 |
\begin{center} |
| 102 |
{\tt ./zsolve affine} |
| 103 |
\end{center} |
| 104 |
%% In the continuous case, this creates the files \File{affine.qhom} |
| 105 |
%% and \File{affine.qfree}, and in the integer case |
| 106 |
This creates the |
| 107 |
files \File{affine.zhom} and \File{affine.zinhom}. %% and \File{affine.zfree}. |
| 108 |
|
| 109 |
%% In contrast to calling %% \File{qsolve} and |
| 110 |
%% \File{zsolve} on a linear |
| 111 |
%% system, these calls create only two files, since at the moment only |
| 112 |
%% homogeneous affine systems (with $a=0$) are supported by |
| 113 |
%% \FourTiTwo{}. |
| 114 |
|
| 115 |
|
| 116 |
|
| 117 |
%%% Local Variables: |
| 118 |
%%% mode: latex |
| 119 |
%%% TeX-master: "4ti2_manual" |
| 120 |
%%% End: |