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