doc: update License section to switch to LGPL 2.1+

[piplib.git] / doc / piplib.texi

\input texinfo
@c %
@c %  /**-----------------------------------------------------------------**
@c %   **                            PIP/PipLib                           **
@c %   **-----------------------------------------------------------------**
@c %   **                            piplib.texi                          **
@c %   **-----------------------------------------------------------------**
@c %   **                 First version: December 2nd 1989                **
@c %   **-----------------------------------------------------------------**/
@c %
@c % release 1.0: December   2nd 1989 (Paul Feautrier and Nadia Tawbi, TeX)
@c % release 2.0: ?
@c % release 3.0: September  9th 1996 (+ Jean-Francois Collard)
@c % release 4.0: September 22th 2001 (+ Cedric Bastoul, LaTeX, 1.0, 1.01, 1.02)
@c % release 4.1: November  25th 2002 (for PipLib 1.1)
@c % release 4.2: January   16th 2003 (for PipLib 1.2, 1.2.1)
@c % release 4.3: March     17th 2003 (for PipLib 1.3, 1.3.1, 1.3.2)
@c % release 4.4: October   18th 2003 (for PipLib 1.3.3)
@c % release 4.5: November   8th 2005 (for PipLib 1.3.4, 1.3.5)
@c % release 4.6: February  21th 2006 (for PipLib 1.3.6)
@c % release 5.0: July       9th 2007 (Texinfo, for PipLib 1.4.0)

@c %
@c %/**************************************************************************
@c % *                     PIP : Parametric Integer Programming               *
@c % **************************************************************************/

@c @documentlanguage en
@c @documentencoding ISO-8859-15

@c % /*************************************************************************
@c %  *                              PART I: HEADER                           *
@c %  *************************************************************************/
@c %**start of header
@setfilename piplib.info
@settitle PIP/PipLib - Parametric Integer Programming

@set EDITION 5.0
@include gitversion.texi
@set UPDATED July 9th 2007
@setchapternewpage odd

@c %**end of header

@c % /*************************************************************************
@c %  *                 PART II: SUMMARY DESCRIPTION AND COPYRIGHT            *
@c %  *************************************************************************/

@copying
This manual is for PIP and PipLib version @value{VERSION}, a software
which solves Parametric Integer Programming problems. That is, PIP finds the
lexicographic minimum of the set of integer points which lie inside a
convex polyhedron, when that polyhedron depends linearly on one or
more integral parameters.

It would be quite kind to refer the following paper in any publication that
results from the use of the PIP software or its library:

@example
@@Article@{Fea88,
@ @ author =@ @ @ @ @{P. Feautrier@},
@ @ title =@ @ @ @ @ @{Parametric Integer Programming@},
@ @ journal = @ @ @{RAIRO Recherche Op\'erationnelle@},
@ @ year =@ @ @ @ @ @ 1988,
@ @ volume =@ @ @ @ 22,
@ @ number =@ @ @ @ 3,
@ @ pages =@ @ @ @ @ @{243--268@}
@}
@end example

Copyright @copyright{} 1988-2007 Paul Feautrier.

@c quotation
Permission is granted to copy, distribute and/or modify this document under
the terms of the GNU Free Documentation License, Version 1.2 
published by the Free Software Foundation. To receive a copy of the
GNU Free Documentation License, write to the Free Software Foundation, Inc.,
59 Temple Place, Suite 330, Boston, MA  02111-1307 USA.
@c end quotation
@end copying

@c % /*************************************************************************
@c %  *                 PART III: TITLEPAGE, CONTENTS, COPYRIGHT              *
@c %  *************************************************************************/
@titlepage
@title PIP/PipLib
@subtitle A Solver for Parametric Integer Programming Problems
@subtitle Edition @value{EDITION}, for PIP/PipLib @value{VERSION}
@subtitle @value{UPDATED}
@author Paul Feautrier, Jean-Fran@,{c}ois Collard, C@'edric Bastoul
     
@c The following two commands start the copyright page.
@page

@vskip 0pt plus 1filll
@insertcopying
@end titlepage
     
@c Output the table of contents at the beginning.
@contents

@c % /*************************************************************************
@c %  *                     PART IV: TOP NODE AND MASTER MENU                 *
@c %  *************************************************************************/
@ifnottex
@node Top
@top PIP/PipLib
     
@insertcopying
@end ifnottex

@menu
* Introduction::
* PIP Software::
* PIP Library::
* Installing::
* Documentation::
* References::
@end menu
 


@c % /*************************************************************************
@c %  *                       PART V: BODY OF THE DOCUMENT                    *
@c %  *************************************************************************/

@c %  ****************************** INTRODUCTION ******************************
@node Introduction
@chapter Introduction
PIP is a software that finds the lexicographic minimum (or maximum) in the
set of integer points belonging to a convex polyhedron. The very big
difference with well known integer programming tools like @emph{lp_solve}
(@pxref{lp_solve}) or @emph{CPLEX} (@pxref{CPLEX})
is the polyhedron may depend linearly on one or more integral
parameters. If the user asks for a non integral solution, PIP can
give the exact solution as an integral quotient. The heart of PIP
is the parameterized Gomory's Cuts algorithm followed by the parameterized
Dual Simplex method (@pxref{Fea88}). The PIP Library (PipLib for short) was
implemented to allow the user to call PIP directly from his programs,
without file accesses or system calls. The user only needs to link his
programs with C libraries.

PIP stands for @emph{Parametric Integer Programming}. PIP/PipLib is known
to be quite stable (the project began and is active since 1988) and fast.
It is used in many projects, mostly but not exclusively in automatic
optimizing/parallelizing compilation (e.g. to compute data dependences).
PIP is a kind of @emph{kernel} which does a simple, well defined work, but does
it well. There is no plan to extend it too much. However you are very welcome
and encouraged to post reports on bugs, wishes, critics, comments, suggestions
or successful experiences in the forum of @code{http://www.PipLib.org}
(preferably) or to send them to @w{paul.feautrier@@ens-lyon.fr} or
@w{cedric.bastoul@@inria.fr} directly.

@menu
* Basics::
* Compilation::
* Formulation::
@end menu

@node Basics
@section A First Basic Example
To better understand what can PIP achieve, let us consider the
following 2-dimensional polyhedron where @math{i} and @math{j} are the unknown
(the two dimensions of the space) and @math{m} and @math{n} are the
parameters (the symbolic constants).

@image{images/pipmin,15cm}

@noindent It is defined by the following set of constraints:
@tex
$$
\left\{\eqalign{2i + 3j - 8 &\geq 0\cr
                 4i - j - 4 &\geq 0\cr
                     -i + n &\geq 0\cr
                          j &\geq 0\cr
                     -j + m &\geq 0}\right.
$$
@end tex
@ifnottex
@example
@group
2i + 3j - 8 >= 0
4i - j - 4 >= 0
-i + n >= 0
j >= 0
-j + m >= 0
@end group
@end example
@end ifnottex

Classic tools to find the lexicographic minimum are challenged because
of the parameters. On the contrary PIP can, without any informations on parameters,
give all the solutions corresponding to all the possible cases according
to the parameter values:

@example
@group
if (7*n >= 10) @{
  if (7*m >= 12) @{
    solution is (i = 2, j = 2)
  @}
  if (2*n+3*m >= 8) @{
    solution is (i = -m-(m div 2)+4, j = m)
  @}
@}
@end group
@end example

@noindent Also, it is possible to fully or partially define the parameter values. Then
PIP will give only the solutions for the possible cases.
For instance with the context:

@tex
$$
\hbox{$ \cases{ m \geq n\cr
                n \geq 5}$}
$$
@end tex

@ifnottex
@example
@group
m >= n
n >= 5
@end group
@end example
@end ifnottex

@noindent There is only one possible solution:

@example
@group
solution is (i = 2, j = 2)
@end group
@end example

@noindent Let the power of Parametric Integer Programming be with you.

@node Compilation
@section PIP for Optimizing Compilation

The semantic analysis of programs accessing arrays often boils down
to finding integer solutions to parametric linear programming problems. This is
due to two main phenomena:
@itemize @bullet
@item  Array subscripts are very often linear functions of surrounding loop
       counters ;
@item  The program's execution order enforces an order on possible solutions.
@end itemize

Let us consider the following example:
@example
@group
for (i = 0 ; i<= m ; i++)
  for (j = 0 ; j<= n ; j++)
    a[2*i+j] = i+j;
@end group
@end example

After completion of execution, for which values of @math{k} is
@code{A[}@math{k}@code{]} defined, and which instances of the assignment wrote
into this array element ? We can easily check that answering this question
is equivalent to finding the solutions of the following system, where @math{i},
@math{j} and @math{k} are the unknowns:

@tex
$$
\hbox{$ \cases{ 0 \leq  i \leq m\cr
                0 \leq  j \leq n\cr
                2i + j  = k}$}
$$
@end tex

@ifnottex
@example
@group
0 <= i <= m
0 <= j <= n
2i + j = k
@end group
@end example
@end ifnottex

Moreover, if we want to know which instance gave its @strong{final} value
to @code{A[}@math{k}@code{]}, that is if we are looking for the @strong{last}
instance writing into @code{A[}@math{k}@code{]}, then we have to look for the
maximal value of vector @math{(i,j)} according to lexicographic order. We
thus consider the following polyhedron
@tex
${\cal F}(k, m, n)$:
@end tex
@ifnottex
@math{@strong{F}(k, m, n)}:
@end ifnottex

@tex
$${\cal F}(k, m, n) = \{<i, j>| 0 \leq i \leq m, 0 \leq j \leq n, 2i+j = k\}$$
@end tex

@ifnottex
@example
@group
@math{@strong{F}(k, m, n) = @{<i,j> | 0<=i<=m, 0<=j<=n, 2i+j=k@}}
@end group
@end example
@end ifnottex

What is the lexicographical maximum of the integer-valued vectors included in
@tex
${\cal F}(k, m, n)$~?
@end tex
@ifnottex
@math{@strong{F}(k, m, n)} ?
@end ifnottex
The aim of PIP is to solve such problems. The reader is referred to
@pxref{Fea88} for a mathematical description of the method.

@node Formulation
@section General Formulation

Let
@tex
${\cal F}$
@end tex
@ifnottex
@math{@strong{F}}
@end ifnottex
be a polyhedron:

@tex
$${\cal F}(\vec{z}) = \{\vec{x} | \vec{x} \geq \vec{0},
                      A \vec{x} + B \vec{z} + \vec{c} \geq \vec{0}\}$$
@end tex

@ifnottex
@example
@group
@math{@strong{F}(@strong{z}) = @{@strong{x} | @strong{x}>=@strong{0}, A@strong{x}+B@strong{y}+@strong{c}>=@strong{0}@}}
@end group
@end example
@end ifnottex

In this formula,
@tex
$\vec{x}$
@end tex
@ifnottex
@math{@strong{x}}
@end ifnottex
is a vector with @math{n} entries: the vector of all unknowns.
@tex
$\vec{z}$, $\vec{z}\geq \vec{0}$,
@end tex
@ifnottex
@math{@strong{z}, @strong{z}>=@strong{0}},
@end ifnottex
is the vector built from parameters and has @math{m} entries. Polyhedron
@tex
${\cal F}(\vec{z})$
@end tex
@ifnottex
@math{@strong{F}(@strong{z})},
@end ifnottex
is a subset of
@tex
${\bf R}^{n}$
@end tex
@ifnottex
@math{R^n}
@end ifnottex
and is defined by @math{n + l} inequalities: @math{n} inequalities expressing
@tex
$\vec{x} \geq \vec{0}$
@end tex
@ifnottex
@math{@strong{x}>=@strong{0}}
@end ifnottex
and the @math{l} inequalities corresponding to rows of matrix
@math{A} of size @math{l * n}, matrix @math{B} of size @math{l * p},
and constant vector
@tex
$\vec{c}$
@end tex
@ifnottex
@math{@strong{c}}
@end ifnottex
of size @math{l}.

Size parameters can themselves be constrained by a set of affine inequalities
@tex
$M \vec{z} + \vec{h} \geq \vec{0}$,
@end tex
@ifnottex
@math{M@strong{z}+@strong{h}>=@strong{0}},
@end ifnottex
which is called the @emph{context} of the problem. @math{M} is an @math{m * p}
matrix and
@tex
$\vec{h}$
@end tex
@ifnottex
@math{@strong{h}}
@end ifnottex
a vector of dimension @math{m}.
All data of a PIP problem:
@tex
($A, B, M, \vec{c}, \vec{h}$)
@end tex
@ifnottex
(@math{A, B, M, @strong{c}, @strong{h}})
@end ifnottex
are assumed to be integer-valued. 


@c %  *********************** Using the PIP Software **************************
@node PIP Software
@chapter Using the PIP Software
@menu
* A First Example::
* Writing the Input File::
* Reading the Output File::
* Calling PIP::
* Power::
@end menu

@c %/*************************************************************************
@c % *                              A FIRST EXAMPLE                          *
@c % *************************************************************************/
@node A First Example
@section A First Example
PIP takes as input a file that must be written accordingly to a grammar
described in depth in a further section (@pxref{Writing the Input File}). 
Moreover it supports some options to tune the internal algorithm or the
software verbosity. They are discussed in a dedicated section
(@pxref{Calling PIP}). However, a basic use of PIP is not very complex
and we present in this section how to compute the lexicographic minimum of
a basic example discussed earlier.

The problem is to find the lexicographic minimum of a parametric
2-dimensional polyhedron where @math{i} and @math{j} are the unknown
(the two dimensions of the space) and @math{m} and @math{n} are the
parameters (the symbolic constants),
defined by the following set of constraints:
@tex
$$
\left\{\eqalign{2i + 3j - 8 &\geq 0\cr
                 4i - j - 4 &\geq 0\cr
                     -i + n &\geq 0\cr
                          j &\geq 0\cr
                     -j + m &\geq 0}\right.
$$
@end tex
@ifnottex
@example
@group
2i + 3j - 8 >= 0
4i - j - 4 >= 0
-i + n >= 0
j >= 0
-j + m >= 0
@end group
@end example
@end ifnottex
@noindent We also consider a partial knowledge of the parameter values,
called the @emph{context,}
expressed thanks to the following affine constraint:
@tex
$$ n -3 \geq 0 $$
@end tex
@ifnottex
@example
@math{n>=3}
@end example
@end ifnottex

An input file that corresponds to this problem may be the following.
Note that we do not describe here precisely
the structure and the components of this file (@pxref{Writing the Input File}
for such information, if you feel it necessary):

@example
( ( Four parts in the file:
    - comments (here !),
    - Information line: here "2 2 5 0 -1 1" meaning 2 unknown,
      2 parameters, 5 inequalities for domain, 1 ineq. for context,
      no big parameter (-1) and integer solution requested (1).
    - List of domain inequalities: #[ 2  3 -8  0  0] meaning
      (2)*i + (3)*j + (-8)*1 + (0)*m + (0)*n >= 0.
    - List of context inequalities: #[ 0  1 -3] meaning
      (0)*m + (1)*n + (-3)*1 >= 0.
  )
  2 2 5 1 -1 1
  ( #[ 2  3 -8  0  0]
    #[ 4 -1 -4  0  0]
    #[-1  0  0  0  1]
    #[ 0  1  0  0  0]
    #[ 0 -1  0  1  0]
  )
  ( #[ 0  1 -3]
  )
)
@end example

This file may be called @samp{basic.pip}
(this example is provided in the PIP distribution as
@code{test/basic.pip}) and we can ask PIP to process it
and to print out the answer by a simple calling to PIP with this file as input:
@samp{pip basic.pip}. PIP will print the answer on the standard output:

@example
( ( Comments are exactly the same as in input file (but not there
    for explanation purpose !). There are three major points:
    - The solution may depend on parameter values, thus it may include
      "if" constructions as "if #[condition] (then part) (else part)".
      "if #[  7  0 -12]" means "if ((7)*m + (0)*n + (-12)*1 >= 0)".
    - Final solution is either void ("()") or a list. For instance,
      "list #[  0  0  2] #[  0  0  2]" means the solution is
      i = (0)*m + (0)*n + (2)*1 and j = (0)*m + (0)*n + (2)*1.
    - New parameters representing the integer division of a parametric
      expression by a constant may be locally necessary. For instance,
      "(newparm @strong{2} (div #[  1  0  0] 2))" means that a new parameter
      with value ((1)*m + (0)*n + (0)*1)div(2) will be present at
      index @strong{2} in the next expressions (index starts to 0).
  )
  ( if #[  7  0 -12]
    (list #[  0  0  2]
          #[  0  0  2]
    )
    ( if #[  3  2 -8]
      (newparm 2 (div #[  1  0  0] 2))
      (list #[ -1  0 -1  4]
            #[  1  0  0  0]
      )
      ()
    )
  )
)
@end example

This answer in not intended to be read by humans but by computers. However
it is not that difficult to translate it in a more readable way:

@example
if (7*m >= 12) @{
  solution is (i = 2, j = 2)
@}
else @{
  if (3*m+2*n >= 8) @{
    solution is (i = -m-(m div 2)+4, j = m)
  @}
  else @{
    no solution
  @}
@}
@end example

@c %/*************************************************************************
@c % *                                Input file                             *
@c % *************************************************************************/
@node Writing the Input File
@section Writing the Input File
The input text file contains a problem description, i.e. the domain,
the context and few additional informations. The input text file respects
the following context-free grammar (terminals are preceeded by "_"):

@example
File         ::= Problem
Problem      ::= ( Comments Infos Domain Context )
Comments     ::= ( _String )
Infos        ::= Nn Np Nl Nm Bg Nq
Domain       ::= ( Vector_list )
Context      ::= ( Vector_list )
Vector       ::= #[ Integer_list ]
Vector_list  ::= Vector Vector_list | @emph{void}
Integer_list ::= _Integer Integer_list | @emph{void}
Nn           ::= _Integer
Np           ::= _Integer
Nl           ::= _Integer
Nm           ::= _Integer
Bg           ::= _Integer
Nq           ::= 0 | 1
@end example


@itemize @bullet
@item @samp{Comments} are arbitrary strings. These comments are written
      verbatim to the output file, and are useful to keep track of
      problems and solutions.
@item @samp{Nn} is the number of unknowns in the program (which was denoted
      by @math{n} in the first section).
@item @samp{Np} is the number of (symbolic) parameters (@math{p})
@item @samp{Nl} is the number of inequalities defining the domain of the
      unknowns (@math{l}). 
@item @samp{Nm} is the number of inequalities satisfied by the
      parameters (@math{m}).
@item @samp{Bg} is the index of a @emph{Big} parameter whose value is assumed 
      to be infinitely large. That is, if the big parameter appears with a
      positive coefficient in a form
@tex
$\phi$,
@end tex
@ifnottex
@math{phi}
@end ifnottex
      then we can immediately deduce that
@tex
$\phi > 0$.
@end tex
@ifnottex
@math{phi > 0}.
@end ifnottex
      If @samp{Bg} is set to a nonpositive
      value, then there is no big parameter in the problem to be solved.
      Index begins at 0. Thus, since @samp{Bg} is the column rank of the
      corresponding parameter in the @samp{Domain}, the first valid value
      for @samp{Bg} is @math{n+1} (after the coefficient of the constant).
@item @samp{Nq} is an integer but should be interpreted as a boolean value
      as in C, that is, it denotes @emph{true} if its value is nonzero.
      If @samp{Nq} is true, then an integer-valued solution is requested.
      Otherwise, PIP finds the lexicographic minimum rational solution
      to the problem.
@item @samp{Domain} stores the set of inequalities defining the domain 
      of unknowns. Each @samp{Vector} represents one inequality. The entries
      in @samp{Vector} are, in this @strong{compulsory} order:
      @itemize @bullet
      @item the coefficients of the unknowns (i.e., a row of matrix @math{A}),
      @item the (additive) constant, (i.e., an entry of vector
@tex
$\vec{c}$),
@end tex
@ifnottex
@math{@strong{c}}),
@end ifnottex
      @item the coefficients of the parameters (i.e., a row of matrix @math{B})
      @end itemize
      This notation heavily depends on the positions given
      to unknowns and parameters: it is the responsibility of the user to
      enforce a coherent ordering of coefficients and to set a coefficient
      to zero when the corresponding unknown/parameter does not appear.

      There are @math{l} such @samp{Vector}s in @samp{Domain}, and each
      @samp{Vector} exactly has @math{n+1+p} entries.
@item In a similar way, @samp{Context} is a list of @samp{Vector}s.
      Each @samp{Vector} represents a row of the matrix @math{M} followed by
      the corresponding entry in vector
@tex
$\vec{h}$.
@end tex
@ifnottex
@math{@strong{h}}.
@end ifnottex
      @samp{Context} thus includes @math{m} @samp{Vector}s of @math{p + 1}
      entries.
@end itemize

Note that several @samp{Problem}s can be given to PIP in the same
file. The problems may be separated by any text that does not
contain a parenthesis. By using Unix FIFOs as input and output files,
it is easy to convert the present implementation of PIP into a
linear programming server.

@menu
* Example (part 1)::
@end menu

@node Example (part 1)
@subsection Example (part 1)
@anchor{section::example}

We consider the loop nest below (@pxref{Fea88}):
@example
@group
for (i = 0 ; i <= m ; i++)
  for (j = 0 ; j <= n ; j++)
    for (k = 0 ; k <= i+j ; k++)
      ...
@end group
@end example
We wish to rewrite this nest in the order @math{k, j, i}. The
bounds on @math{k} can easily be guessed
@tex
($0\leq k \leq m+n$), 
@end tex
@ifnottex
(0 <= @math{k} <= @math{m+n}).
@end ifnottex
so let's look for the lower bound on @math{j} in the rewritten nest.
This lower bound on @math{j} can be found by solving the following problem:

@tex
$$ {\cal D}(k,m,n) = \{\,<\!j,i\!>\, |\, i \leq m, j \leq n, k \leq i + j\}.$$
@end tex
@ifnottex
@math{@strong{D}(k,m,n) = @{<j,i>|i<=m,j<=n,k<=i+j@}}.
@end ifnottex

This problem is to be solved in the context
@tex
$k \leq m+n$.  
@end tex
@ifnottex
@math{k} <= @math{m+n}.
@end ifnottex
The input file may thus look like this:
@example
@group
( ( Lower bound on j after loop inversion.
    Unknowns: j i, parameters: k m n.
  )
  2 3 3 1 -1 1
  ( #[ 0 -1  0  0  1  0]
    #[-1  0  0  0  0  1]
    #[ 1  1  0 -1  0  0]
  )
  ( #[-1  1  1  0]
  )
)
@end group
@end example

The first sequence of integers should be read as: this problem has 2
unknowns (@math{i} and @math{j}) and 3 parameters
(@math{k}, @math{m} and @math{n}). The domain is
defined by 3 inequalities, the context by 1 inequality. There is no
(-1) big parameter and it is true (1) that we are looking for an
integer solution.

@c %/*************************************************************************
@c % *                             Output File                               *
@c % *************************************************************************/
@node Reading the Output File
@section Reading the Output File

The output file can be described by the following grammar
(terminals are preceeded by "_"):
@example
File             ::= Result
Result           ::= ( Comments Solution )
Comments         ::= ( _String )
Solution         ::= ( Quast_group ) | @emph{void}
Quast_group      ::= Newparm_list Quast
Quast            ::= Form | (if Vector Quast_group Quast_group)
Form             ::= (list Vector_list) | ()
Newparm_list     ::= Newparm Newparm_list | @emph{void}
Vector_list      ::= Vector Vector_list | @emph{void}
Coefficient_list ::= Coefficient Coefficient_list | @emph{void}
Newparm          ::= (newparm _Integer (div Vector _Integer))
Vector           ::= #[ Coefficient_list ]
Coefficient      ::= _Integer | _Integer / _Integer
@end example
The @samp{Comments} are copied from the input file. The @samp{Solution}
is said to be @emph{void} when the initial context is void. Otherwise,
it is given as a quast (quasi-affine selection tree) written in a
Lisp-like way. The quast may possibly be preceded by the definition
of one or several new parameters (see below).

The vector coefficients may be either integers or rationals written as
a division
@samp{numerator/denominator}. The latter case occurs if @samp{Nq} had been
set to 0 in the input file.

In the solution, a @samp{Vector} represents an affine form; each entry
is the coefficient of the corresponding parameter (the parameter of
the same rank). The last entry is the additive constant.

The definition of a new parameter begins with the key-word
@samp{newparm}, then an index (rank) number, a vector of coefficients, and a
denominator. The new parameter is equal to the integer division of the
vector by the denominator. The new parameter can only appear in the
@samp{Quast} following its definition. Introducing a new parameter adds
one entry in the list of parameters, so the length of vectors in the
solution is not constant. However, this length is always equal to 1 plus
the number of original parameters plus the number of new parameters
currently defined.

The solution is a multi-level conditional expression (a
tree of nested conditionals.) A predicate expression @math{p} should be
understood as the boolean expression
@tex
$p\geq 0$.
@end tex
@ifnottex
@math{p} >= @math{0}.
@end ifnottex
Leaves of the conditional tree are either @samp{()}, meaning that
the input problem has no solution, or a @samp{Form}. A @samp{Form}
is a list of vectors, each vector giving the value of the corresponding
unknown.

@menu
* Example (part 2)::
@end menu

@node Example (part 2)
@subsection Example (part 2)
The output of PIP is not intended for human consumption.
No attempt has been made to implement a pretty-printer. In the interest
of readability, some of the result files in this paper have been beautified
by hand. The reader should not be surprised if he gets results with
different layouts when running the examples.

Here is the exact output solution file for the previous example
(@pxref{Example (part 1)}):
@example
@group
( ( Lower bound on j after loop inversion.
    Unknowns: j i, parameters: k m n.
   1  )(if #[ -1 1 0 0]
(list #[ 0 0 0 0]
#[ 1 0 0 0]
)
(list #[ 1 -1 0 0]
#[ 0 1 0 0]
)
)
)
@end group
@end example
To express this solution, no new parameter had to be introduced. The
form associated to the first conditional is
@math{(-1)*k + (1)*m + (0)*n + (0)*1 = m-k}
so the test should be read as
@tex
$m - k \geq 0$.
@end tex
@ifnottex
@math{m-k} >= @math{0}.
@end ifnottex
If this inequality holds, then the solution is @math{<0,k>}.
Otherwise, the solution is @math{<k-m,m>}.

To sum things up, the lexicographical minimum of
@tex
${\cal D}$
@end tex
@ifnottex
@math{@strong{D}}
@end ifnottex
is:

@code{if m-k >= 0 then <0, k> else <k-m, m>}.

Hence the lower bound on the first coordinate:

@code{if m-k >= 0 then 0 else k-m}.



@c %/*************************************************************************
@c % *                             Calling PIP                               *
@c % *************************************************************************/
@node Calling PIP
@section Calling PIP

PIP is called by the following command:
@example
       pip [-s|-v...] [-d] [-z] [input [output]]
@end example
The default behavior of PIP is to read the input informations from the
standard input and to print the solution (or some error messages if
anything went wrong) on the standard output. Options and messages are
discussed in next sections.

@menu
* Options::
* Messages::
@end menu

@node Options
@subsection Options
PIP's behavior and the output shape is under the user control thanks
to few options which are detailed in this section.
@code{input} is the input file. If none is given, input is standard input.
For instance, we can call PIP to process the
input file @code{test.pip} with default options by typing:
@code{pip test.pip} or @code{more test.pip | pip}.
If no @code{output} file is given, then the results are printed to the
standard output.

@menu
* Verbosity::
* Simplification::
* Deepest Cut::
@end menu

@node Verbosity
@subsubsection Verbosity
PIP prints some information on the screen after having solved a
problem. The @code{-s} (silent mode) switches this feature off. On the
contrary, the verbose @code{-v} option tells PIP to copy, in a file,
all the input data and all the intermediary results. The name of this
file is given either by the variable @code{DEBUG} in the environment or
is built by @code{mkstemp}. The number of consecutive @code{-v}'s
(from 0 to 3) controls the degree of verbosity of Pip.
A word of caution: debug files may become very large very fast.

@node Simplification
@subsubsection Simplification
If the @code{-z} option is given, then the solution is somewhat simplified.
The solution of a parametric problem may be in the form of a quast all
of whose leaves are nil. This means in fact that the original polyhedron
is empty whatever the values of the parameters. An example, due to Dirk
Fimmel, is the following:

@example
@group
( ((i j 1)(m n))
  2 2 7 0 -1 1
  ( #[2 6 -9 0 0]
    #[5 -3 0 0 0]
    #[2 -10 15 0 0]
    #[-2 6 -3 0 0]
    #[-2 -6 17 0 0]
    #[0 1 0 -1 0]
    #[1 0 0 0 -1]
  )
  ()
)
@end group
@end example

@noindent Without the @code{-z} option, the solution is:

@example
( ((i j 1)(m n) -1 )
  ( if #[ -4 0 5]
    ( if #[ 0 -4 3] 
      ()
      ( if #[ 0 -2 9]
        ( if #[ 0 -2 3]
          (newparm 2 (div #[ 0 2 3] 6))
          (newparm 3 (div #[ 0 2 10 7] 12))
          (newparm 4 (div #[ 0 4 0 2 1] 6))
          ()
          ( if #[ 0 -2 7]
            (newparm 2 (div #[ 0 4 3] 6))
            ( if #[ 0 -8 6 11]
              ()
              ()
            )
            ()
          )
        )
        ()
      )
    )
    ( if #[ -1 0 3]
      ( if #[ -1 0 2]
        ( if #[ 10 -2 -15]
          ()
          ()
        )
        ()
      )
      ()
    )
  )
)
@end example

@noindent Inspection reveals that all leaves are @code{()}. With the
@code{-z} option, the solution is much simpler:

@example
@group
( ((i j 1)(m n) -1 )
  ()
)
@end group
@end example

@node Deepest Cut
@subsubsection Deepest Cut
When Pip is asked for an integral solution, it constructs new constraints
(the so-called @emph{cuts}) which eliminate fractional solutions and keep
all integer solutions. The selection of cuts is somewhat arbitrary. When
the @code{-d} option is given, Pip uses this degree of freedom to select
the @emph{deepest cut} according to an algorithm by Gondran. Intractable
problems may become tractable when using this option, and conversely.
Use with caution.

@node Messages
@subsection Messages

PIP may print various messages to give, e.g., some information on the
complexity of the problem or to help the user to solve some errors. 

@menu
* General::
* Input::
* Solution::
* Implementation::
@end menu

@node General
@subsubsection General Messages

@itemize @bullet
@item @samp{Version X.x}. Currently, @code{D.1}.
@item @samp{cross : <n>, alloc : <m>} This message is output after solving
      each problem. The value of @code{<n>} gives an idea of the complexity of
      the problem.
@end itemize

@node Input
@subsubsection Errors Related to the Input

@itemize @bullet
@item @samp{Syntax error}: unbalanced parentheses in the input.
@item @samp{Too much variables}.
@item @samp{Too much parameters}: check the input and/or change the value of
      constants @code{MAXCOL} and @code{MAXPARM} in file @code{type.h}, then
      rebuild PIP.
@item @samp{Your computer doesn't have enough memory}: self explanatory.
@end itemize

@node Solution
@subsubsection Errors Related to the Solution

@itemize @bullet
@item @samp{Integer Overflow}: A number has been generated that is too large
      to be accommodated in a 32 bit integer. Check the input and/or switch
      to Zbigniew Chamski's infinite precision PIP.
@item @samp{The solution is too complex}: the solution quast has grown beyond
      the memory allocated to it. Check the input and/or change the value of
      constant @code{SOL\_SIZE} in file @code{type.h}, then rebuild PIP.
@item @samp{Memory overflow}: self explanatory.
@item @samp{<file> unaccessible}: one of the input, output or debug file
      cannot be opened.
@end itemize

@node Implementation
@subsubsection Implementation Errors

All such error messages begin by the word @samp{Syserr}. These messages
indicate a bug in the implementation. You should report such events
by sending a copy of the input file by e-mail to the author,
@code{Paul.Feautrier@@ens-lyon.fr} who will endeavor to solve the problem
as soon as possible.

@c %/*************************************************************************
@c % *                          The power of PIP                             *
@c % *************************************************************************/
@node Power
@section The Power of PIP 

In the following sections, we explain how PIP can be used to solve 
extended classes of problems:
@itemize @bullet
@item Problems where equalities occur.
@item Problems where a lexicographic @emph{maximum} has to be found. 
@item Cases when linear cost functions are to be optimized.
@item Problems where unknowns and/or parameters may be negative.
@end itemize

@menu
* Handling Equalities::
* The Bigparm Trick::
* Computing Lexicographic Maxima::
* Optimizing Linear Cost Functions::
* Negative Unknowns and Parameters::
* Mixed Programming::
@end menu

@node Handling Equalities
@subsection Handling Equalities
When the input problem contains @math{r} affine equalities
@math{f_i = 0},
@tex
@math{1 \leq i\leq r},
@end tex
@ifnottex
@math{1 <= i <= r},
@end ifnottex
one may just write @math{r} inequalities 
@tex
@math{f_i \geq 0}
@end tex
@ifnottex
@math{f_i >= 0}
@end ifnottex
and @math{r} inequalities
@tex
@math{f_i \leq 0},
@end tex
@ifnottex
@math{f_i <= 0},
@end ifnottex
thus satisfying PIP's input syntax.
However, one may notice that only @math{r+1} inequalities
are needed:
@tex
@math{f_i \geq 0}, @math{1\leq i\leq r},
@end tex
@ifnottex
@math{f_i >= 0}, @math{1 <= i <= r},
@end ifnottex
and the following inequality:
@tex
@math{\sum_{i=1}^{r} f_i \leq 0}.
@end tex
@ifnottex
@math{sum_(i=1,r) f_i <= 0}.
@end ifnottex


@node The Bigparm Trick
@subsection The Bigparm Trick
In some cases, it is useful to suppose that one parameter in a PIP problem
grows @emph{very large}. Some examples will be given in the following sections.
Let @math{B} be the name of this parameter. Suppose that in the solution, one
of the predicates is:

@tex
@math{a B + b \geq 0,}
@end tex
@ifnottex
@math{a B + b >= 0,}
@end ifnottex

@noindent where @math{b} may depend on all other parameters. For @math{B}
large enough, if @math{a > 0}
then the predicate is true, and if @math{a < 0} then the predicate is false.
One can find the limit shape of the solution by removing such tests and 
replacing them by their true of false branch, as appropriate. This can be done
a posteriori on the results of PIP, or PIP can do it @emph{on the fly}
while solving the problem. This last method is more efficient, since it
tends to simplify the solution.

PIP is notified of the presence of a big parameter by setting the @samp{Bg}
argument to a positive value. This value is the rank of the big parameter
in the problem domain. Hence, the lowest admissible value for @samp{Bg}
is @samp{Nn + 1}.

The reader should convince himself that in the presence of two big
parameters, no such simplifications are possible unless one has some
information on the relative size of the parameters. Such situations
should be handled by giving PIP ordinary parameters, and doing the
simplification on the solution in the light of extra knowledge.

@node Computing Lexicographic Maxima
@subsection Computing Lexicographic Maxima
To get the maximum of an unknown @math{x},  minimize @math{B - x}, where
B is a new @emph{big} parameter. Adding a parameter just adds one column
in the problem domain. The fact that this column corresponds to a big
parameter is specified by setting the 5-th switch to a positive value,
this value being the position of the column of B in the problem
domain (column index starts to 0).

These cases can be handled systematically in the following way. Suppose that
we are asked for the integer maximum of the polyhedron:
@tex
$$
\left\{\eqalign{x  &\geq 0\cr
                y  &\geq 0\cr
                3y &\leq x + 12\cr
                y  &\geq 2x - 3\cr}\right.
$$
@end tex
@ifnottex
@example
@group
 x >= 0,
 y >= 0,
3y <= x + 12,
 y >= 2x - 3.
@end group
@end example
@end ifnottex
Let us introduce the new unknowns:
@tex
$$ x'= B - x, \;\; y' = B - y ,$$
@end tex
@ifnottex
@math{x'= B - x}, @math{y' = B - y},
@end ifnottex
where @math{B} is the big parameter. The system translates to:
@tex
$$
\left\{\eqalign{           -x' + B &\geq 0\cr
                           -y' + B &\geq 0\cr
                -x' + 3y' + 12 -2B &\geq 0\cr
                  2x' - y' + 3 - B &\geq 0\cr}\right.
$$
@end tex
@ifnottex
@example
@group
           -x' + B >= 0,
           -y' + B >= 0,
-x' + 3y' + 12 -2B >= 0,
  2x' - y' + 3 - B >= 0.
@end group
@end example
@end ifnottex
Finding the maximum of @math{(x,y)^T} is equivalent to finding the minimum of
@math{(x', y')^T}, provided @math{B} is large enough. The solution of the
above problem is:
@example
( (a maximization problem 1)
  ( if #[ -1 6]
    ( if #[ -1 3]
      (list #[ 0 0]
            #[ 0 0]
      )
      ( if #[ -5 27]
        (newparm 1 (div #[ 1 1] 2))
        (list #[ 1 -1 -1]
              #[ 0  0  0]
        )
        (list #[ 1 -4]
              #[ 1 -5]
        )
      )
    )
    (list #[ 1 -4]
          #[ 1 -5]
    )
  )
)
@end example

Suppose we tell PIP that @math{B} is a large parameter. The input file is now:
@example
@group
( (a maximization problem)
  2 1 4 0 3 1
  ( #[-1  0  0  1]
    #[ 0 -1  0  1]
    #[-1  3 12 -2]
    #[ 2 -1  3 -1]
  )
  ()
)
@end group
@end example
@noindent and the solution is much simpler:
@example
@group
( (a maximization problem 1)
  (list #[ 1 -4]
        #[ 1 -5]
  )
)
@end group
@end example
The reader may care to check that this result is equivalent to the
previous one as soon as @math{B > 5}. The position of the minimum is:
@math{x' = B - 4}, @math{y' = B - 5}, from which we deduce:
@math{x = 4, y = 5}. As
expected, @math{B} has disappeared from the solution. If this does not happen,
we observe first that @math{B} must have a positive coefficient in the result
(if not, one of the inequalities
@tex
@math{x, y \geq 0}
@end tex
@ifnottex
@math{x, y >= 0}
@end ifnottex
would be violated for
@math{B} large enough). This means that the original polyhedron is not bounded,
since, whatever @math{B}, it contains a point whose coordinates are
@math{O(B)}, and hence has no maximum.

@node Optimizing Linear Cost Functions
@subsection Optimizing Linear Cost Functions
The problem here is to compute the minimum of a linear function
@tex
@math{\vec{c}\vec{x}}
@end tex
@ifnottex
@math{@strong{c}@strong{x}}
@end ifnottex
in a polyhedron @math{@strong{P}},
where
@tex
@math{\vec{c}}
@end tex
@ifnottex
@math{@strong{c}}
@end ifnottex
is a vector with integer coefficients. Let us introduce
a new unknown @math{y}. Solve the linear programming problem obtained by
adding the constraint
@tex
@math{y \geq \vec{c}\vec{x}}
@end tex
@ifnottex
@math{y >= @strong{c}@strong{x}}
@end ifnottex
to the defining constraints of @math{@strong{P}}.
@math{y} should be the first unknown in the lexicographic ordering. Let
@tex
@math{(y_s, \vec{x}_s)}
@end tex
@ifnottex
@math{(y_s, @strong{x}_s)}
@end ifnottex
be the solution. Suppose that the minimum of
@tex
@math{\vec{c}\vec{x}}
@end tex
@ifnottex
@math{@strong{c}@strong{x}}
@end ifnottex
in @math{@strong{P}} is obtained at
@tex
@math{\vec{x}_m}
@end tex
@ifnottex
@math{@strong{x}_m}
@end ifnottex
and set
@tex
@math{y_m = \vec{c}\vec{x}_m}.
@end tex
@ifnottex
@math{y_m = @strong{c}@strong{x}_m}.
@end ifnottex
Since
@tex
@math{\vec{x}_s}
@end tex
@ifnottex
@math{@strong{x}_s}
@end ifnottex
is in @math{@strong{P}}, and
@tex
@math{y_s \geq \vec{c}\vec{x}_s},
@end tex
@ifnottex
@math{y_s >= @strong{c}@strong{x}_s},
@end ifnottex
it is clear that
@tex
@math{y_s \geq y_m}.
@end tex
@ifnottex
@math{y_s >= y_m}.
@end ifnottex
Conversely,
@tex
@math{(y_m, \vec{x}_m)}
@end tex
@ifnottex
@math{(y_m, @strong{x}_m)}
@end ifnottex
satisfies the constraints of the problem of which
@tex
@math{(y_s, \vec{x}_s)}
@end tex
@ifnottex
@math{(y_s, @strong{x}_s)}
@end ifnottex
is the lexicographic minimum. Hence
@tex
@math{(y_s, \vec{x}_s) \ll (y_m, \vec{x}_m)},
@end tex
@ifnottex
@math{(y_s, @strong{x}_s) << (y_m, @strong{x}_m)},
@end ifnottex
and, since @math{y} is the first unknown,
@tex
@math{y_s \leq y_m}.
@end tex
@ifnottex
@math{y_s <= y_m}
@end ifnottex
Hence, @math{y_m = y_s}.
There is no guarantee, however, that
@tex
@math{\vec{x}_s = \vec{x}_m}
@end tex
@ifnottex
@math{@strong{x}_s = @strong{x}_m}
@end ifnottex
(but if they differ, solutions are equally good since
@tex
@math{y_s = \vec{c}\vec{x}_s}
@end tex
@ifnottex
@math{y_s = @strong{c}@strong{x}_s}
@end ifnottex
and
@tex
@math{y_m = y_s = \vec{c}\vec{x}_s = \vec{c}\vec{x}_m}).
@end tex
@ifnottex
@math{y_m = y_s = @strong{c}@strong{x}_s = @strong{c}@strong{x}_m}).
@end ifnottex

@node Negative Unknowns and Parameters
@subsection Negative Unknowns and Parameters
Suppose we want to find the minimum of @math{f(i,j) = i-2j} over the square
domain defined by
@tex
@math{@{(i,j) | -4 n -20 \leq i + j \leq 0, -2 n - 10 \leq i - j \leq 2 n + 10@}}
@end tex
@ifnottex
@math{@{(i,j) | -4 n -20 <= i + j <= 0, -2 n - 10 <= i - j <= 2 n + 10@}}
@end ifnottex

(this example was proposed and solved by Pierre Boulet):

@image{images/negatifs,8cm}
As above, we introduce a new unknown @math{f} and the inequality
@tex
@math{f-i+2j \geq 0}.
@end tex
@ifnottex
@math{f-i+2j >= 0}.
@end ifnottex
Since we want to optimize @math{f}, @math{f}
will appear as the first unknown.

To allow @math{n} (or any other parameter) to become negative, 
we apply the standard trick of replacing @math{n} by @math{n = n' - n''},
where @math{n'} and @math{n''} are two new parameters, both non-negative.
For handling possibly negative unknows, we add a number @math{G} to each
of the unknowns that ensures that
@tex
$$
\eqalign{ f' &= G + f\cr
          i' &= G + i\cr
          j' &= G + j}
$$
@end tex
@ifnottex
@example
@group
       f' = G + f
       i' = G + i
       j' = G + j
@end group
@end example
@end ifnottex
@noindent are all non-negative. That is, @math{G} should be such that
@tex
$$
G \geq \max(0,-i,-j,-f).
$$
@end tex
@ifnottex
@example
@math{G >= max(0,-i,-j,-f)}.
@end example
@end ifnottex
Hence, @math{G}
is again a big parameter. 
After replacement of @math{i,j,n} and @math{f} by the new variables
@math{i',j',n',n''} and @math{f'}, we obtain the set
@tex
$$
\eqalign{ \{\, (f',i',j') \mid
    & f' -i' + 2j' - 2 G \geq 0 \, \wedge \cr
    & 4 (n'-n'') -20 \leq i' + j' - 2 G \leq 0 \, \wedge \cr
    & -2 (n'-n'') - 10 \leq i' - j' \leq 2 (n'-n'') + 10 \,\},}
$$
@end tex
@ifnottex
@example
@group
@math{@{(f',i',j') | f' -i' + 2j' - 2 G >= 0,
              4 (n'-n'') -20 >= i' + j' - 2 G >= 0,
              -2 (n'-n'') - 10 >= i' - j' >= 2 (n'-n'') + 10@}}
@end group
@end example
@end ifnottex
which corresponds to the following input:
@example
@group
( ( Solving MIN(i-2.j) under the following constraints:
    Unknowns may be negative.
    Order: f' i' j' constant G n'' n'
  )
  3 3 5 0 4 1
  ( #[ 1 -1  2  0 -2  0  0 ]
    #[ 0  1  1 20 -2 -4  4 ]
    #[ 0 -1 -1  0  2  0  0 ]
    #[ 0  1 -1 10  0 -2  2 ]
    #[ 0 -1  1 10  0 -2  2 ]
  )
  ()
)
@end group
@end example

The result is:
@example
@group
( ( Solving MIN(i-2.j) under the following constraints:
    Unknowns may be negative.
    Order: f' i' j' constant G n'' n' -1
  )
  ( if #[ 0 -1 1 5]
    (list #[ 1  3 -3 -15]
          #[ 1  1 -1  -5]
          #[ 1 -1  1   5]
    )
    ()
  )
)
@end group
@end example
which should be read as:
@tex
$$
\eqalign{(f',i',j') =\; & {\tt if}\;  (-n''+n'+5 \geq 0) \cr
                      & {\tt then} \; (G+3n''-3n'-15, G+n''-n'-5,G-n''+n'+5) \cr
                      & {\tt else} \; \bot}
$$
@end tex
@ifnottex
@example
@group
@math{(f',i',j') = @strong{if} (-n''+n'+5 >= 0)
             @strong{then} (G+3n''-3n'-15, G+n''-n'-5,G-n''+n'+5)
             @strong{else} bottom}
@end group
@end example
@end ifnottex
That is, in the original coordinate system:
@tex
$$
(f,i,j) = {\tt if}\;  (n \geq -5) \; {\tt then} \; (-3n-15, -n-5, n+5)
 \; {\tt else} \; \bot
$$
@end tex
@ifnottex
@example
@group
@math{(f,i,j) = @strong{if} (n >= -5)
          @strong{then} (-3n-15, -n-5, n+5)
          @strong{else} bottom}
@end group
@end example
@end ifnottex
@noindent I.e., the minimum value for function @math{f} is @math{-3n-15},
and this value is reached at point @math{(-n-5, n+5)}.
This minimum exists only if
@tex
@math{n \geq -5};
@end tex
@ifnottex
@math{n >= -5};
@end ifnottex
otherwise, the feasible set is empty.

@node Mixed Programming
@subsection Mixed Programming
A mixed program is a program in which some variables are constrained
to be integers while others may take rational values. Suppose for
instance that we have to solve:
@tex
$$
\eqalign{S = & \min a x + b y,\cr
             & A x + B y + c \geq 0,}
$$
@end tex
@ifnottex
@example
@group
@math{S = min a x + b y,
    A x + B y + c >= 0},
@end group
@end example
@end ifnottex
where @math{y} is the vector of the integer variables. First, solve
@tex
$$
\eqalign{T = & \min a x,\cr
             & A x + B y + c \geq 0,}
$$
@end tex
@ifnottex
@example
@group
@math{T = min a x,
    A x + B y + c >= 0},
@end group
@end example
@end ifnottex
in rational, with @math{y} as parameters. The result is a quast.
To each leaf @math{i} is associated a linear function @math{f_i(y)}
and a set of inequalities
@tex
@math{C_i y + d_i \geq 0}. 
@end tex
@ifnottex
@math{C_i y + d_i >= 0}. 
@end ifnottex
@math{T} is equal to
@math{f_i} when @math{y} is such that the corresponding inequalities
are satisfied. For each @math{i}, solve the problem:
@tex
$$
\eqalign{S_i = & \min f_i(y) + b y,\cr
               & C_i y + d_i \geq 0,}
$$
@end tex
@ifnottex
@example
@group
@math{S_i = min f_i(y) + b y,
      C_i y + d_i >= 0},
@end group
@end example
@end ifnottex
in integers. The final result is the minimum of all @math{S_i}.
Obviously, the method can accommodate parameters in the
constraints. The @math{S_i} will be functions of these
parameters, and the minimum must be computed symbolically.


@c %/*************************************************************************
@c % *                             PIP Library                               *
@c % *************************************************************************/
@node PIP Library
@chapter Using the PIP Library
The PIP Library (PipLib for short) was implemented to allow the user to call
PIP directly from his programs, without file accesses or system calls. The
user only needs to link his programs with C libraries. The
PipLib mainly provides one function which takes as input the problem description
and some options, and returns a @code{Quast}
(@pxref{Reading the Output File}) corresponding to the solution. Some
other functions are provided for convenience reasons ; they
are described in a further section (@pxref{PipLib Functions}).
Most of them require
some specific structures to represent the problem or
the solution; these structures are described in the next section
(@pxref{PipLib Data Structures}).


@menu
* PipLib Data Structures::
* PipLib Functions::
* Example of Library Utilization::
@end menu


@node PipLib Data Structures
@section PipLib Data Structures Description
In this section, we describe the data structures used by the PIP
library to represent and to process a parametric integer programming problem.


@menu
* PipMatrix::
* PipVector::
* PipNewparm::
* PipList::
* PipQuast::
* PipOptions::
@end menu

@node PipMatrix
@subsection PipMatrix
@noindent The @code{PipMatrix} structure is a copy of the PolyLib
@code{Matrix} data structure (@pxref{Wil93}, and @code{polylib/types.h}).
This structure is devoted to represent a set of constraints. It is 
defined as the following:

@example
@group
struct pipmatrix
@{ unsigned NbRows ;    /* Number of rows. */
  unsigned NbColumns ; /* Number of columns. */
  Entier ** p ;        /* Array of pointers to the matrix rows. */
  Entier * p_Init ;    /* Matrix rows contiguously in memory. */
  int p_Init_size ;    /* For internal use. */
@}
typedef struct pipmatrix PipMatrix;
@end group
@end example

@noindent The whole matrix is stored in memory row after row at the
@code{p_Init} address. @code{p} is an array of pointers where
@code{p[i]} points to the first element of the @math{i^{th}} row.
@code{NbRows} and @code{NbColumns} are respectively the number of
rows and columns of the matrix. 
Each row corresponds to a constraint. The first element of each row is an
equality/inequality tag. The
constraint is an equality @math{p(x) = 0} if the first element is 0, but it is
an inequality
@tex
@math{p(x) \geq 0}
@end tex
@ifnottex
@math{p(x) >= 0}
@end ifnottex
if the first element is 1.
The next elements are the unknown coefficients, followed by the parameter
coefficients, then the scalar coefficient.
@strong{Please notice that the ordering of unknown and scalar coefficients
is different from the input file of the PIP software} (this is due
to historical reasons).
For instance, in the problem we used as example
(@pxref{Example (part 1)}) the domain is defined by
the following three constraints:

@tex
$$
\hbox{$ \cases{ -i + m       &$= 0$\cr
                -j + n       &$\geq 0$\cr
                 j + i - k   &$\geq 0$}$}
$$
@end tex

@ifnottex
@example
@group
    -i + m  = 0
    -j + n >= 0
 i + j - k >= 0
@end group
@end example
@end ifnottex

@noindent would be represented by the following rows:

@example
@group
# eq/in  i   j   k   m   n   cst
    0    0  -1   0   1   0    0 
    1   -1   0   0   0   1    0 
    1    1   1  -1   0   0    0 
@end group
@end example

@noindent To be able to provide different precision version (PIP/PipLib
supports 32 bits, 64 bits and arbitrary precision through the GMP library),
the @code{Entier} type depends on the configuration options (it may be
@code{long int} for 32 bits version, @code{long long int} for 64 bits version,
and @code{mpz_t} for multiple precision version).
The @code{p_Init_size} field is needed to free
the memory allocated by @code{mpz_init} in the multiple precision release.
Set this field to 0 if you are @emph{not} using multiple precision.
Set this field to the size of the @code{p_Init} array if you
initialized it yourself and if you are using the multiple precision version.

The context is defined by one constraint:

@tex
$$
-k + m + n \geq 0
$$
@end tex
@ifnottex
@example
@math{-k + m + n >= 0}
@end example
@end ifnottex

@noindent the row corresponding to this constraint would be:

@example
@group
# eq/in  k   m   n   cst
    1   -1   1   1    0 
@end group
@end example

@noindent @code{p_Init_size} is needed by the to free the memory
allocated by @code{mpz_init} in the multiple precision release.


@node PipVector
@subsection PipVector

@example
@group
struct pipvector
@{ int nb_elements ;          /* Number of elements in the vector */
  Entier * the_vector ;      /* Vector of numerators */
  Entier * the_deno ;        /* Vector of denominators */
@} ;
typedef struct pipvector PipVector ;
@end group
@end example

@noindent The @code{PipVector} structure represents a @code{Vector}
as described in the ouput grammar (@pxref{Reading the Output File}).
@code{nb_elements} is the number of vector elements, @code{the_vector} is
an array which contains the numerators of these elements and @code{the_deno}
is an array which contains their denominators: the @math{i^{th}} element is
@code{the_vector[i]/the_deno[i]}.


@node PipNewparm
@subsection PipNewparm

@example
@group
struct pipnewparm
@{ int rank ;                 /* Index of the newparm */
  PipVector * vector ;       /* Vector of parameter coefficients */
  Entier deno ;              /* Denominator for the whole vector */
  struct pipnewparm * next ; /* Pointer to next newparm */
@} ;
typedef struct pipnewparm PipNewparm ;
@end group
@end example

@noindent The @code{PipNewparm} structure represents a @code{NULL}
terminated linked list of @code{Newparm} as described in the ouput grammar
(@pxref{Reading the Output File}).
For each @code{Newparm}, the rank is @code{rank},
the vector of coefficients is pointed by @code{vector}, and the denominator
is @code{deno}. @code{next} is a pointer to the next @code{PipNewparm}
structure.


@node PipList
@subsection PipList

@example
@group
struct piplist
@{ PipVector * vector ;          /* Pointer to a vector */
  struct piplist * next ;       /* Pointer to next vector */
@} ;
typedef struct piplist PipList ;
@end group
@end example

@noindent The @code{PipList} structure represents a @code{NULL} terminated
linked list of @code{Vector} as described in the ouput grammar
(@pxref{Reading the Output File}). 
@code{vector} is a pointer to the vector of the current node and
@code{next} is a pointer to the next @code{PipList} structure.


@node PipQuast
@subsection PipQuast

@example
@group
struct pipquast
@{ PipNewparm * newparm ;        /* List of newparms */
  PipList * list ;              /* The solution (if no condition) */
  PipVector * condition ;       /* The condition */
  struct pipquast * next_then ; /* Quast if condition is true */
  struct pipquast * next_else ; /* Quast if condition is false */
  struct pipquast * father ;    /* Pointer to father quast */
@} ;      
typedef struct pipquast PipQuast ;
@end group
@end example

@noindent The @code{PipQuast} represents a @code{Quast} as described in the
ouput grammar (@pxref{Reading the Output File}). Each @code{Quast}
has a tree structure and begins with a list of @code{Newparm}
(field @code{newparm}). If the pointer @code{condition} is not @code{NULL}, the
list of @code{Newparm} is followed by a conditional structure : if the condition
pointed by @code{condition} is true, then the solution continues in the
@code{Quast} pointed by @code{next_then}, in the @code{Quast} pointed by
@code{next_else} otherwise. If the pointer @code{condition} is @code{NULL}, the
list of @code{Newparm} is followed by a list of vectors (field @code{list}).
For @code{Quast} manipulation convenience, a pointer to the father in the tree
is provided (field @code{father}), obviously the father of the root is
@code{NULL}. 


@node PipOptions
@subsection PipOptions

@example
@group
struct pipoptions
@{ int Nq ;                  /* 1 for integral solution, else 0 */
  int Verbose ;             /* Verbosity level (from -1 to 3) */
  int Simplify ;            /* 1 to simplify solution, else 0 */
  int Deepest_cut ;         /* 1 to use Deepest Cut algo, else 0 */
  int Maximize;             /* 0 for lexico minimum, 1 for maximum */
  int Urs_parms;            /* 0 for non-negative parms, else -1 */
  int Urs_unknowns;         /* 0 for non-negative unknowns, else -1 */
@} ;      
typedef struct pipoptions PipOptions ;
@end group
@end example

@noindent The @code{PipOptions} structure contains all the possible options
ruling the PIP behaviour. Every @code{PipOptions} structure should be created
and filled with the default values by the @code{pip_options_init}
function (@pxref{pip_options_init}) to ensure forward compatibility.
Only after this, the user should modify
the structure entries according to his wishes:

@enumerate
@item @code{Nq}: a boolean set to 1 if an integer solution is needed, 0
      otherwise,
@item @code{Verbose}: a graduate value for debug informations:
      @itemize @bullet
      @item -1: absolute silence,
      @item 0: relative silence,
      @item 1: information on cuts when an integer solution is required,
      @item 2: information on pivots and determinants,
      @item 3: information on arrays.
      @end itemize
      Each option include the preceding one.
      If @code{Verbose} is not @math{-1}, most of the processing will be
      printed in a file. The file name is generated at random
      (by @code{mkstemp}) or set with environment variable DEBUG.
@item @code{Simplify}: a boolean set to 1 if some trivial quast simplifications
      are needed (recursive elimination of degenerated patterns like
      @code{if #[...] () ()}), 0 otherwise,
@item @code{Deepest_cut}: a boolean set to 1 if PIP has to use the deepest cut
      algorithm, 0 otherwise,
@item @code{Maximize}: a boolean set to 0 if the lexicographic
      minimum is requested, or to 1 for the lexicographic maximum. When trying
      to find the lexicographic maximum, the method used is the one
      presented in a previous section 
      (@pxref{Computing Lexicographic Maxima}):
      if no bigparm was set, a new (big) parameter is automatically created
      by adding a new column (at the last position) to the
      constraint system.  This optional extra parameter is removed again from
      the output.  Unbounded solutions have their @code{the_deno} set to zero.
      Note that setting this option allows for negative solutions.
      This may change in a future release.
@item @code{Urs_parms}: controls signs of parameters:
        @itemize @bullet
        @item -1: all parameters have unrestricted sign,
        @item 0: all parameters are non-negative.
        @end itemize
@item @code{Urs_unknowns}: controls signs of unknowns:
        @itemize @bullet
        @item -1: all unknowns have unrestricted sign,
        @item 0: all unknowns are non-negative.
        @end itemize
@end enumerate


@node PipLib Functions
@section PipLib Functions

@menu
* pip_solve::
* pip_options_init::
* pip_close::
* pip_matrix_alloc::
* pip_matrix_read::
* Printing Functions::
* Memory Deallocation Functions::
@end menu

@node pip_solve
@subsection pip_solve

@example
@group
PipQuast * pip_solve
( PipMatrix * domain,      /* Domain where to find a solution */
  PipMatrix * context,     /* Constraints on parameters */
  int Bg,                  /* Bigparm index (-1 if no bigparm) */
  PipOptions * options     /* Options */
) ;
@end group
@end example

@noindent The @code{pip_solve} function solves a linear problem provided as
input. The first three parameters describe the problem that the user wants
to solve. The last parameter describe the options that the user has to set.
These parameters are:
@enumerate
@item @code{domain}: a pointer to the equations and inequalities system which
      describe the unknown domain in the PolyLib constraints matrix shape,
@item @code{context}: a pointer to the equations and inequalities system
      satisfied by the parameter context in the PolyLib constraints matrix
      shape (it can be @code{NULL} if there is no context). @strong{Caution:
      if there are parameters but no constraints on them, don't set
      @code{context} to @code{NULL} but to a matrix with the right column
      number (i.e., number of parameters + 2) and 0 rows because the PipLib
      uses this information to know the parameter number.}
@item @code{Bg}: the column rank of the bignum (first column rank is 0), or a
      negative value if there is no big parameter in the problem to be solved,
      if unsure, just set to -1, 
@item @code{options}: a pointer to a data structure containing the options
      ruling the behaviour of PIP.
@end enumerate
This function returns a pointer to a @code{PipQuast} structure containing the
solution, it will be @code{NULL} if the context is @code{void}.


@node pip_options_init
@subsection pip_options_init

@example
@group
PipOptions * pip_options_init(void) ;
@end group
@end example

@noindent The @code{pip_options_init} function allocates the memory space
for a @code{PipOptions} structure and fills it with the default values:
@itemize
@item @code{Nq} @math{= 1}: an integer value is required,
@item @code{Verbose} @math{= 0}: no debug informations,
@item @code{Simplify} @math{= 0}: do not try to simplify solutions,
@item @code{Deepest_cut} @math{= 0}: do not use deepest cut algorithm,
@item @code{Maximize} @math{= 0}: compute the lexicographic minimum,
@item @code{Urs_parms} @math{= 0}: all parameters are non-negative,
@item @code{Urs_unknowns} @math{= 0}: all unknowns are non-negative.
@end itemize
We strongly recommend to use this function to create and initialize any
@code{PipOptions} structure. In this way, if some new options appear in
the future, there will be no compatibility issues.


@node pip_close
@subsection pip_close

@example
@group
void pip_close(void) ;
@end group
@end example

@noindent The @code{pip_close} function
frees the memory space that have been allocated
for few global variables PipLib needs. This function has to be called when
PipLib is no more useful in order to prevent slight memory leaks.


@node pip_matrix_alloc
@subsection pip_matrix_alloc

@example
@group
PipMatrix * pip_matrix_alloc
( unsigned nb_rows,
  unsigned nb_columns
) ;
@end group
@end example

@noindent The @code{pip_matrix_alloc} function allocates the memory space
for a @code{PipMatrix} structure with @code{nb_rows} rows and @code{nb_columns}
columns. It fills the @code{Nb_Rows}, @code{Nb_Columns} and @code{p} fields
and initializes the matrix entries to 0, then it returns a pointer to this
structure.


@node pip_matrix_read
@subsection pip_matrix_read

@example
@group
PipMatrix * pip_matrix_read(FILE *) ;
@end group
@end example

@noindent The @code{pip_matrix_read} function reads a matrix from a file. It
takes as input a pointer to the file it has to read (possibly @code{stdin}), and
returns a pointer to a @code{PipMatrix} structure. The input has the following
syntax:
@itemize
@item some optional comment lines which begin with @code{#},
@item the row numbers and column numbers, possibly followed by comments,
      on a single line,
@item the matrix rows, each row must be on a single line and is possibly
      followed by comments.
@end itemize
For instance, in the example problem (@pxref{Example (part 1)}) the domain
may be defined as follows

@example
@group
# This is the domain
3 7                 # 3 lines and 7 columns
1  0 -1  0  1  0  0 # -i + m >= 0
1 -1  0  0  0  1  0 # -j + n >= 0
1  1  1 -1  0  0  0 # j + i - k >= 0
@end group
@end example


@node Printing Functions
@subsection Printing Functions

@example
@group
void pip_matrix_print(FILE *, PipMatrix *) ;
void pip_vector_print(FILE *, PipVector *) ;
void pip_newparm_print(FILE *, PipNewparm *, int indent) ;
void pip_list_print(FILE *, PipList *, int indent) ;
void pip_quast_print(FILE *, PipQuast *, int indent) ;
void pip_options_print(FILE *, PipOptions *) ;
@end group
@end example

@noindent There is a printing function for each structure of the PipLib.
They all take as input
a pointer to a file (possibly @code{stdout}) and a pointer to a structure.
Some of them takes as input an
indent step. They print the structure contents to the file without indent if
@code{indent} @math{< 0}, with an indentation step of @code{indent} otherwise.


@node Memory Deallocation Functions
@subsection Memory Deallocation Functions

@example
@group
void pip_matrix_free(PipMatrix *) ;
void pip_vector_free(PipVector *) ;
void pip_newparm_free(PipNewparm *) ;
void pip_list_free(PipList *) ;
void pip_quast_free(PipQuast *) ;
void pip_options_free(PipOptions *) ;
@end group
@end example

@noindent There is a memory deallocation function for each structure of
the PipLib. They free the allocated memory for the structure.


@node Example of Library Utilization
@section Example of Library Utilization
Here is a simple example showing how one can use the PipLib, assuming that
a basic installation has been done. The following C program reads a domain and
its context on the standard input then prints
the solution on the standard output.
Options are preselected : there is no bignum, we are looking for an integral
solution without simplification and we don't want debug informations.
This example is provided in the @code{example} directory of the
PIP/PipLib distribution.

@example
@group
/* example.c */
# include <stdio.h>
# include <piplib/piplib64.h>

int main()
@{ PipMatrix * domain, * context  ;
  PipQuast * solution ;
  PipOptions * options ;
 
  options = pip_options_init() ;
  domain  = pip_matrix_read(stdin) ;
  context = pip_matrix_read(stdin) ;

  solution = pip_solve(domain,context,-1,options) ;

  pip_options_free(options) ;
  pip_matrix_free(domain) ;
  pip_matrix_free(context) ;

  pip_quast_print(stdout,solution,0) ;
  pip_close() ;
  return 0 ;
@}
@end group
@end example

@noindent The compilation command could be:
@example
gcc example.c -lpiplib64 -o example
@end example

@noindent Supposing that the user wants to solve the example problem
(@pxref{Example (part 1)}), he will type:

@example
3 7
1  0 -1  0  1  0  0 
1 -1  0  0  0  1  0 
1  1  1 -1  0  0  0 

1 5
1 -1  1  1  0 
@end example

@noindent And the program will answer:

@example
( if #[ -1  1  0  0]
  (list #[  0  0  0  0]
        #[  1  0  0  0]
  )
  (list #[  1 -1  0  0]
        #[  0  1  0  0]
  )
)
@end example


@c %  ****************************** INSTALLING ********************************
@node Installing
@chapter Installing PIP

@menu
* License::
* Adjusting::
* Basic Installation::
* Optional Features::
* Uninstallation::
@end menu

@node License
@section License
First of all, it would be very kind to refer the following paper in any
publication that result from the use of the PIP software or its library,
@pxref{Fea88} (a bibtex entry is provided behind the title page of this
manual, along with copyright notice, and in the PIP/PipLib home
@code{http://www.PipLib.org}.

This library is free software; you can redistribute it and/or modify it
under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or (at
your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
@code{http://www.gnu.org/copyleft/gpl.html}


@node Adjusting
@section Adjusting the Precision
Pip is an all integer  version of the dual simplex algorithm. As such,
it has to handle integers whose size may grow exponentially as the
computation proceeds. Integer overflow may occur and have to be checked.
Since the hardware integer overflow exception is usually masked by
the operating system or the compiler, overflow is detected by checking
that a division somewhere in the algorithm, which can be proved to be
exact by mathematical arguments, is indeed exact. If not, an error is
reported and the computation stops.

The size of the numbers to be handled depends strongly on the size of the
constraint matrix and on the size of its coefficients.

@menu
* Bounded PIP::
* Multiple Precision PIP::
@end menu


@node Bounded PIP
@subsection Bounded PIP
The precision of the integer representation in the Pip code can be
adjusted at compile time by giving options to the @code{configure}
shell script.
By giving @code{configure} the option @code{--enable-llint-version} you ask
for long long int version only (64 bits). It results in a 64 bits Pip
called @code{pip64}.
By giving @code{configure} the option @code{--enable-int-version} you
ask for int version only. It results in a 32 bits called
@code{pip32} and a faster running time.


@node Multiple Precision PIP
@subsection Multiple Precision PIP
Multiple Precision Pip is built on top of the GMP library
(this library is freely available at @code{http://www.swox.com/gmp}). 
Each integer in the program is represented as a list of 32 bits numbers.
All computations are done exactly, and the size of the numbers increases
as needed to preserve exactness. It follows that no overflow is possible.
However, when the size of numbers increases, computations get slower and
slower, and memory overflow may occur in extreme cases. In well behaved
problems, 32 bits are enough for the initial data, the size of intermediate
results first increases up to a maximum, then decreases, and 32 bits
are again enough for the results. Hence, it has been possible to keep
the input format and output format of Multiple Precision Pip completely
compatible with the formats of the bounded precision versions.

To install Multiple Precision Pip, first install GMP according to the
directions found at the above URL. Usually, the library is installed
in @code{/usr/local/lib}, and the header files are in @code{/usr/local/include}.
If this is not the case, you must adjust the Pip makefile by giving
to the @code{configure} shell script the option @code{--with-gmp=PATH}, where
@code{PATH} is the GMP library installation path. If GMP headers and
libraries are not in the same installation path, you can be more precise
by using @code{--with-gmp-include=PATH} and @code{--with-gmp-library=PATH}
for GMP headers and libraries respectively.


By giving @code{configure} the option @code{--enable-mp-version} you ask
for a GMP version only. It results in a multiple precision Pip
called @code{pipMP}.

@node Basic Installation
@section PIP Basic Installation

Once downloaded and unpacked
(e.g. using the @samp{tar -zxvf piplib-@value{VERSION}.tar.gz} command),
you can compile PIP by typing the following commands on the PIP's root
directory:

@itemize @bullet
@item @code{./configure}
@item @code{make}
@item And as root: @code{make install}
@end itemize

Depending on the location of the GMP (and whether or not you want
to use it), you may need to set the
option @code{--with-gmp} of the configure script
(e.g. @samp{./configure --with-gmp=/usr/local} with a default GMP
installation).

The program binaries and object files can be removed from the
source code directory by typing @code{make clean}. To also remove the
files that the @code{configure} script created (so you can compile the
package for a different kind of computer) type @code{make distclean}.

Both the PIP software and PipLib library have been successfully compiled
on the following systems:
@itemize @bullet
@item PC's under Linux, with the @code{gcc} compiler,
@item PC's under Windows (Cygwin), with the @code{gcc} compiler,
@item Mac's under MacOS X, with the @code{gcc} compiler,
@item Sparc and UltraSparc Stations, with the @code{gcc} compiler.
@end itemize

@node Optional Features 
@section Optional Features  
The @code{configure} shell script attempts to guess correct values for
various system-dependent variables and user options used during compilation.
It uses those values to create the @code{Makefile}. Various user options
are provided by the PIP's configure script. They are summarized in the
following list and may be printed by typing @code{./configure --help} in the
PIP top-level directory.

@itemize @bullet
@item By default, the installation directory is @code{/usr/local}:
@code{make install} will install the package's files in
@code{/usr/local/bin}, @code{/usr/local/lib} and @code{/usr/local/include}.
The user can specify an installation prefix other than @code{/usr/local} by
giving @code{configure} the option @code{--prefix=PATH}.

@item By default, both PIP software and PipLib library are compiled and installed.
By giving  @code{configure} the option @code{--without-pip} the user
disable the compilation and installation of the PIP software.
@c By giving @code{configure} the option
@c @code{--without-lib} the user disable the compilation and installation of the
@c PipLib library.

@item By default, PIP is built in both 32 and 64 bits versions, and in
multiple precision version if GMP is found by @code{configure}.
To build only one version, the user may give to @code{configure} the options
@code{--enable-int-version} or @code{--enable-llint-version} or
@code{--enable-mp-version} to build only 32, 64 or multiple precision
version respectively.

@item By default, @code{configure} will look for the GMP library
(necessary to build the multiple precision version) in standard
locations. If necessary, the user can specify the GMP path by giving
@code{configure} the option @code{--with-gmp=PATH}.
@end itemize

@node Uninstallation 
@section Uninstallation  
The user can easily remove the PIP software and PipLib library from his system
by typing (as root if necessary) from the PIP/PipLib top-level directory
@code{make uninstall}.

@c %  **************************** DOCUMENTATION ******************************
@node Documentation
@chapter Documentation
The Texinfo sources of the present document is provided in the @code{doc}
directory. You can build it in either DVI format (by typing
@code{texi2dvi piplib.texi}) or PDF format
(by typing @code{texi2pdf piplib.texi}) or HTML format
(by typing @code{makeinfo --html piplib.texi}, using @code{--no-split}
option to generate a single HTML file) or info format
(by typing @code{makeinfo piplib.texi}).

@c %  ****************************** REFERENCES ********************************
@node References
@chapter References

@itemize
@item
@anchor{CPLEX}[CPLEX] @emph{http://www.ilog.com/products/cplex/}

@item
@anchor{Dant51}[Dant51] G.B. Dantzig. Maximization of a linear function of
variables subject to linear inequalities. In Koopmans, T.C. (ed.),
Activity analysis of production and allocation,
John Wiley & Sons, New York, 339-347, 1951.

@item
@anchor{Fea88}[Fea88] Paul Feautrier. Parametric Integer Programming.
Rairo Recherche Op@'erationnelle, 22(3):243--268, 1988.

@item
@anchor{Feau89}[Fea89] Paul Feautrier.
Semantical analysis and mathematical programming; application to
parallelization and vectorization.
In M. Cosnard, Y. Robert, P. Quinton, and M. Raynal, editors,
Workshop on Parallel and Distributed Algorithms, pages 309--320.
Bonas, North Holland, 1989.

@item
@anchor{Fea92}[Fea92] P. Feautrier Some efficient solutions to the affine
scheduling problem, part II: multidimensional time.
International Journal of Parallel Programming, 21(6):389--420, December 1992.

@item
@anchor{Gom58}[Gom58] R. Gomory. Outline of an algorithm for integer
solutions to linar programs. Bulletin of the American Mathematical
Society 64:275-278, 1958.

@item
@anchor{Lem54}[Lem54] Lemke. The dual method for solving the linear
programming problem. Naval Research Logistic Quarterly 22:978-981, 1954.

@item
@anchor{lp_solve}[lp_solve] @emph{http://groups.yahoo.com/group/lp_solve/}

@item
@anchor{Wil93}[Wil93] Doran K. Wilde.
A library for doing polyhedral operations.
Technical Report 785, IRISA, Rennes, France, 1993.

@end itemize




@c % /*************************************************************************
@c %  *                       PART VI: END OF THE DOCUMENT                    *
@c %  *************************************************************************/
@c @unnumbered Index
     
@c @printindex cp
     
@bye