3 @c % /**-----------------------------------------------------------------**
5 @c % **-----------------------------------------------------------------**
7 @c % **-----------------------------------------------------------------**
8 @c % ** First version: December 2nd 1989 **
9 @c % **-----------------------------------------------------------------**/
11 @c % release 1.0: December 2nd 1989 (Paul Feautrier and Nadia Tawbi, TeX)
13 @c % release 3.0: September 9th 1996 (+ Jean-Francois Collard)
14 @c % release 4.0: September 22th 2001 (+ Cedric Bastoul, LaTeX, 1.0, 1.01, 1.02)
15 @c % release 4.1: November 25th 2002 (for PipLib 1.1)
16 @c % release 4.2: January 16th 2003 (for PipLib 1.2, 1.2.1)
17 @c % release 4.3: March 17th 2003 (for PipLib 1.3, 1.3.1, 1.3.2)
18 @c % release 4.4: October 18th 2003 (for PipLib 1.3.3)
19 @c % release 4.5: November 8th 2005 (for PipLib 1.3.4, 1.3.5)
20 @c % release 4.6: February 21th 2006 (for PipLib 1.3.6)
21 @c % release 5.0: July 9th 2007 (Texinfo, for PipLib 1.4.0)
24 @c %/**************************************************************************
25 @c % * PIP : Parametric Integer Programming *
26 @c % **************************************************************************/
28 @c @documentlanguage en
29 @c @documentencoding ISO-8859-15
31 @c % /*************************************************************************
32 @c % * PART I: HEADER *
33 @c % *************************************************************************/
35 @setfilename piplib.info
36 @settitle PIP/PipLib - Parametric Integer Programming
39 @include gitversion.texi
40 @set UPDATED July 9th 2007
41 @setchapternewpage odd
45 @c % /*************************************************************************
46 @c % * PART II: SUMMARY DESCRIPTION AND COPYRIGHT *
47 @c % *************************************************************************/
50 This manual is for PIP and PipLib version @value{VERSION}, a software
51 which solves Parametric Integer Programming problems. That is, PIP finds the
52 lexicographic minimum of the set of integer points which lie inside a
53 convex polyhedron, when that polyhedron depends linearly on one or
54 more integral parameters.
56 It would be quite kind to refer the following paper in any publication that
57 results from the use of the PIP software or its library:
61 @ @ author =@ @ @ @ @{P. Feautrier@},
62 @ @ title =@ @ @ @ @ @{Parametric Integer Programming@},
63 @ @ journal = @ @ @{RAIRO Recherche Op\'erationnelle@},
64 @ @ year =@ @ @ @ @ @ 1988,
65 @ @ volume =@ @ @ @ 22,
66 @ @ number =@ @ @ @ 3,
67 @ @ pages =@ @ @ @ @ @{243--268@}
71 Copyright @copyright{} 1988-2007 Paul Feautrier.
74 Permission is granted to copy, distribute and/or modify this document under
75 the terms of the GNU Free Documentation License, Version 1.2
76 published by the Free Software Foundation. To receive a copy of the
77 GNU Free Documentation License, write to the Free Software Foundation, Inc.,
78 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
82 @c % /*************************************************************************
83 @c % * PART III: TITLEPAGE, CONTENTS, COPYRIGHT *
84 @c % *************************************************************************/
87 @subtitle A Solver for Parametric Integer Programming Problems
88 @subtitle Edition @value{EDITION}, for PIP/PipLib @value{VERSION}
89 @subtitle @value{UPDATED}
90 @author Paul Feautrier, Jean-Fran@,{c}ois Collard, C@'edric Bastoul
92 @c The following two commands start the copyright page.
95 @vskip 0pt plus 1filll
99 @c Output the table of contents at the beginning.
102 @c % /*************************************************************************
103 @c % * PART IV: TOP NODE AND MASTER MENU *
104 @c % *************************************************************************/
123 @c % /*************************************************************************
124 @c % * PART V: BODY OF THE DOCUMENT *
125 @c % *************************************************************************/
127 @c % ****************************** INTRODUCTION ******************************
129 @chapter Introduction
130 PIP is a software that finds the lexicographic minimum (or maximum) in the
131 set of integer points belonging to a convex polyhedron. The very big
132 difference with well known integer programming tools like @emph{lp_solve}
133 (@pxref{lp_solve}) or @emph{CPLEX} (@pxref{CPLEX})
134 is the polyhedron may depend linearly on one or more integral
135 parameters. If the user asks for a non integral solution, PIP can
136 give the exact solution as an integral quotient. The heart of PIP
137 is the parameterized Gomory's Cuts algorithm followed by the parameterized
138 Dual Simplex method (@pxref{Fea88}). The PIP Library (PipLib for short) was
139 implemented to allow the user to call PIP directly from his programs,
140 without file accesses or system calls. The user only needs to link his
141 programs with C libraries.
143 PIP stands for @emph{Parametric Integer Programming}. PIP/PipLib is known
144 to be quite stable (the project began and is active since 1988) and fast.
145 It is used in many projects, mostly but not exclusively in automatic
146 optimizing/parallelizing compilation (e.g. to compute data dependences).
147 PIP is a kind of @emph{kernel} which does a simple, well defined work, but does
148 it well. There is no plan to extend it too much. However you are very welcome
149 and encouraged to post reports on bugs, wishes, critics, comments, suggestions
150 or successful experiences in the forum of @code{http://www.PipLib.org}
151 (preferably) or to send them to @w{paul.feautrier@@ens-lyon.fr} or
152 @w{cedric.bastoul@@inria.fr} directly.
161 @section A First Basic Example
162 To better understand what can PIP achieve, let us consider the
163 following 2-dimensional polyhedron where @math{i} and @math{j} are the unknown
164 (the two dimensions of the space) and @math{m} and @math{n} are the
165 parameters (the symbolic constants).
167 @image{images/pipmin,15cm}
169 @noindent It is defined by the following set of constraints:
172 \left\{\eqalign{2i + 3j - 8 &\geq 0\cr
173 4i - j - 4 &\geq 0\cr
176 -j + m &\geq 0}\right.
191 Classic tools to find the lexicographic minimum are challenged because
192 of the parameters. On the contrary PIP can, without any informations on parameters,
193 give all the solutions corresponding to all the possible cases according
194 to the parameter values:
200 solution is (i = 2, j = 2)
203 solution is (i = -m-(m div 2)+4, j = m)
209 @noindent Also, it is possible to fully or partially define the parameter values. Then
210 PIP will give only the solutions for the possible cases.
211 For instance with the context:
215 \hbox{$ \cases{ m \geq n\cr
229 @noindent There is only one possible solution:
233 solution is (i = 2, j = 2)
237 @noindent Let the power of Parametric Integer Programming be with you.
240 @section PIP for Optimizing Compilation
242 The semantic analysis of programs accessing arrays often boils down
243 to finding integer solutions to parametric linear programming problems. This is
244 due to two main phenomena:
246 @item Array subscripts are very often linear functions of surrounding loop
248 @item The program's execution order enforces an order on possible solutions.
251 Let us consider the following example:
254 for (i = 0 ; i<= m ; i++)
255 for (j = 0 ; j<= n ; j++)
260 After completion of execution, for which values of @math{k} is
261 @code{A[}@math{k}@code{]} defined, and which instances of the assignment wrote
262 into this array element ? We can easily check that answering this question
263 is equivalent to finding the solutions of the following system, where @math{i},
264 @math{j} and @math{k} are the unknowns:
268 \hbox{$ \cases{ 0 \leq i \leq m\cr
284 Moreover, if we want to know which instance gave its @strong{final} value
285 to @code{A[}@math{k}@code{]}, that is if we are looking for the @strong{last}
286 instance writing into @code{A[}@math{k}@code{]}, then we have to look for the
287 maximal value of vector @math{(i,j)} according to lexicographic order. We
288 thus consider the following polyhedron
293 @math{@strong{F}(k, m, n)}:
297 $${\cal F}(k, m, n) = \{<i, j>| 0 \leq i \leq m, 0 \leq j \leq n, 2i+j = k\}$$
303 @math{@strong{F}(k, m, n) = @{<i,j> | 0<=i<=m, 0<=j<=n, 2i+j=k@}}
308 What is the lexicographical maximum of the integer-valued vectors included in
310 ${\cal F}(k, m, n)$~?
313 @math{@strong{F}(k, m, n)} ?
315 The aim of PIP is to solve such problems. The reader is referred to
316 @pxref{Fea88} for a mathematical description of the method.
319 @section General Formulation
331 $${\cal F}(\vec{z}) = \{\vec{x} | \vec{x} \geq \vec{0},
332 A \vec{x} + B \vec{z} + \vec{c} \geq \vec{0}\}$$
338 @math{@strong{F}(@strong{z}) = @{@strong{x} | @strong{x}>=@strong{0}, A@strong{x}+B@strong{y}+@strong{c}>=@strong{0}@}}
350 is a vector with @math{n} entries: the vector of all unknowns.
352 $\vec{z}$, $\vec{z}\geq \vec{0}$,
355 @math{@strong{z}, @strong{z}>=@strong{0}},
357 is the vector built from parameters and has @math{m} entries. Polyhedron
362 @math{@strong{F}(@strong{z})},
371 and is defined by @math{n + l} inequalities: @math{n} inequalities expressing
373 $\vec{x} \geq \vec{0}$
376 @math{@strong{x}>=@strong{0}}
378 and the @math{l} inequalities corresponding to rows of matrix
379 @math{A} of size @math{l * n}, matrix @math{B} of size @math{l * p},
389 Size parameters can themselves be constrained by a set of affine inequalities
391 $M \vec{z} + \vec{h} \geq \vec{0}$,
394 @math{M@strong{z}+@strong{h}>=@strong{0}},
396 which is called the @emph{context} of the problem. @math{M} is an @math{m * p}
404 a vector of dimension @math{m}.
405 All data of a PIP problem:
407 ($A, B, M, \vec{c}, \vec{h}$)
410 (@math{A, B, M, @strong{c}, @strong{h}})
412 are assumed to be integer-valued.
415 @c % *********************** Using the PIP Software **************************
417 @chapter Using the PIP Software
420 * Writing the Input File::
421 * Reading the Output File::
426 @c %/*************************************************************************
427 @c % * A FIRST EXAMPLE *
428 @c % *************************************************************************/
429 @node A First Example
430 @section A First Example
431 PIP takes as input a file that must be written accordingly to a grammar
432 described in depth in a further section (@pxref{Writing the Input File}).
433 Moreover it supports some options to tune the internal algorithm or the
434 software verbosity. They are discussed in a dedicated section
435 (@pxref{Calling PIP}). However, a basic use of PIP is not very complex
436 and we present in this section how to compute the lexicographic minimum of
437 a basic example discussed earlier.
439 The problem is to find the lexicographic minimum of a parametric
440 2-dimensional polyhedron where @math{i} and @math{j} are the unknown
441 (the two dimensions of the space) and @math{m} and @math{n} are the
442 parameters (the symbolic constants),
443 defined by the following set of constraints:
446 \left\{\eqalign{2i + 3j - 8 &\geq 0\cr
447 4i - j - 4 &\geq 0\cr
450 -j + m &\geq 0}\right.
464 @noindent We also consider a partial knowledge of the parameter values,
465 called the @emph{context,}
466 expressed thanks to the following affine constraint:
476 An input file that corresponds to this problem may be the following.
477 Note that we do not describe here precisely
478 the structure and the components of this file (@pxref{Writing the Input File}
479 for such information, if you feel it necessary):
482 ( ( Four parts in the file:
484 - Information line: here "2 2 5 0 -1 1" meaning 2 unknown,
485 2 parameters, 5 inequalities for domain, 1 ineq. for context,
486 no big parameter (-1) and integer solution requested (1).
487 - List of domain inequalities: #[ 2 3 -8 0 0] meaning
488 (2)*i + (3)*j + (-8)*1 + (0)*m + (0)*n >= 0.
489 - List of context inequalities: #[ 0 1 -3] meaning
490 (0)*m + (1)*n + (-3)*1 >= 0.
504 This file may be called @samp{basic.pip}
505 (this example is provided in the PIP distribution as
506 @code{test/basic.pip}) and we can ask PIP to process it
507 and to print out the answer by a simple calling to PIP with this file as input:
508 @samp{pip basic.pip}. PIP will print the answer on the standard output:
511 ( ( Comments are exactly the same as in input file (but not there
512 for explanation purpose !). There are three major points:
513 - The solution may depend on parameter values, thus it may include
514 "if" constructions as "if #[condition] (then part) (else part)".
515 "if #[ 7 0 -12]" means "if ((7)*m + (0)*n + (-12)*1 >= 0)".
516 - Final solution is either void ("()") or a list. For instance,
517 "list #[ 0 0 2] #[ 0 0 2]" means the solution is
518 i = (0)*m + (0)*n + (2)*1 and j = (0)*m + (0)*n + (2)*1.
519 - New parameters representing the integer division of a parametric
520 expression by a constant may be locally necessary. For instance,
521 "(newparm @strong{2} (div #[ 1 0 0] 2))" means that a new parameter
522 with value ((1)*m + (0)*n + (0)*1)div(2) will be present at
523 index @strong{2} in the next expressions (index starts to 0).
530 (newparm 2 (div #[ 1 0 0] 2))
540 This answer in not intended to be read by humans but by computers. However
541 it is not that difficult to translate it in a more readable way:
545 solution is (i = 2, j = 2)
549 solution is (i = -m-(m div 2)+4, j = m)
557 @c %/*************************************************************************
559 @c % *************************************************************************/
560 @node Writing the Input File
561 @section Writing the Input File
562 The input text file contains a problem description, i.e. the domain,
563 the context and few additional informations. The input text file respects
564 the following context-free grammar (terminals are preceeded by "_"):
568 Problem ::= ( Comments Infos Domain Context )
569 Comments ::= ( _String )
570 Infos ::= Nn Np Nl Nm Bg Nq
571 Domain ::= ( Vector_list )
572 Context ::= ( Vector_list )
573 Vector ::= #[ Integer_list ]
574 Vector_list ::= Vector Vector_list | @emph{void}
575 Integer_list ::= _Integer Integer_list | @emph{void}
586 @item @samp{Comments} are arbitrary strings. These comments are written
587 verbatim to the output file, and are useful to keep track of
588 problems and solutions.
589 @item @samp{Nn} is the number of unknowns in the program (which was denoted
590 by @math{n} in the first section).
591 @item @samp{Np} is the number of (symbolic) parameters (@math{p})
592 @item @samp{Nl} is the number of inequalities defining the domain of the
594 @item @samp{Nm} is the number of inequalities satisfied by the
595 parameters (@math{m}).
596 @item @samp{Bg} is the index of a @emph{Big} parameter whose value is assumed
597 to be infinitely large. That is, if the big parameter appears with a
598 positive coefficient in a form
605 then we can immediately deduce that
612 If @samp{Bg} is set to a nonpositive
613 value, then there is no big parameter in the problem to be solved.
614 Index begins at 0. Thus, since @samp{Bg} is the column rank of the
615 corresponding parameter in the @samp{Domain}, the first valid value
616 for @samp{Bg} is @math{n+1} (after the coefficient of the constant).
617 @item @samp{Nq} is an integer but should be interpreted as a boolean value
618 as in C, that is, it denotes @emph{true} if its value is nonzero.
619 If @samp{Nq} is true, then an integer-valued solution is requested.
620 Otherwise, PIP finds the lexicographic minimum rational solution
622 @item @samp{Domain} stores the set of inequalities defining the domain
623 of unknowns. Each @samp{Vector} represents one inequality. The entries
624 in @samp{Vector} are, in this @strong{compulsory} order:
626 @item the coefficients of the unknowns (i.e., a row of matrix @math{A}),
627 @item the (additive) constant, (i.e., an entry of vector
634 @item the coefficients of the parameters (i.e., a row of matrix @math{B})
636 This notation heavily depends on the positions given
637 to unknowns and parameters: it is the responsibility of the user to
638 enforce a coherent ordering of coefficients and to set a coefficient
639 to zero when the corresponding unknown/parameter does not appear.
641 There are @math{l} such @samp{Vector}s in @samp{Domain}, and each
642 @samp{Vector} exactly has @math{n+1+p} entries.
643 @item In a similar way, @samp{Context} is a list of @samp{Vector}s.
644 Each @samp{Vector} represents a row of the matrix @math{M} followed by
645 the corresponding entry in vector
652 @samp{Context} thus includes @math{m} @samp{Vector}s of @math{p + 1}
656 Note that several @samp{Problem}s can be given to PIP in the same
657 file. The problems may be separated by any text that does not
658 contain a parenthesis. By using Unix FIFOs as input and output files,
659 it is easy to convert the present implementation of PIP into a
660 linear programming server.
666 @node Example (part 1)
667 @subsection Example (part 1)
668 @anchor{section::example}
670 We consider the loop nest below (@pxref{Fea88}):
673 for (i = 0 ; i <= m ; i++)
674 for (j = 0 ; j <= n ; j++)
675 for (k = 0 ; k <= i+j ; k++)
679 We wish to rewrite this nest in the order @math{k, j, i}. The
680 bounds on @math{k} can easily be guessed
682 ($0\leq k \leq m+n$),
685 (0 <= @math{k} <= @math{m+n}).
687 so let's look for the lower bound on @math{j} in the rewritten nest.
688 This lower bound on @math{j} can be found by solving the following problem:
691 $$ {\cal D}(k,m,n) = \{\,<\!j,i\!>\, |\, i \leq m, j \leq n, k \leq i + j\}.$$
694 @math{@strong{D}(k,m,n) = @{<j,i>|i<=m,j<=n,k<=i+j@}}.
697 This problem is to be solved in the context
702 @math{k} <= @math{m+n}.
704 The input file may thus look like this:
707 ( ( Lower bound on j after loop inversion.
708 Unknowns: j i, parameters: k m n.
721 The first sequence of integers should be read as: this problem has 2
722 unknowns (@math{i} and @math{j}) and 3 parameters
723 (@math{k}, @math{m} and @math{n}). The domain is
724 defined by 3 inequalities, the context by 1 inequality. There is no
725 (-1) big parameter and it is true (1) that we are looking for an
728 @c %/*************************************************************************
730 @c % *************************************************************************/
731 @node Reading the Output File
732 @section Reading the Output File
734 The output file can be described by the following grammar
735 (terminals are preceeded by "_"):
738 Result ::= ( Comments Solution )
739 Comments ::= ( _String )
740 Solution ::= ( Quast_group ) | @emph{void}
741 Quast_group ::= Newparm_list Quast
742 Quast ::= Form | (if Vector Quast_group Quast_group)
743 Form ::= (list Vector_list) | ()
744 Newparm_list ::= Newparm Newparm_list | @emph{void}
745 Vector_list ::= Vector Vector_list | @emph{void}
746 Coefficient_list ::= Coefficient Coefficient_list | @emph{void}
747 Newparm ::= (newparm _Integer (div Vector _Integer))
748 Vector ::= #[ Coefficient_list ]
749 Coefficient ::= _Integer | _Integer / _Integer
751 The @samp{Comments} are copied from the input file. The @samp{Solution}
752 is said to be @emph{void} when the initial context is void. Otherwise,
753 it is given as a quast (quasi-affine selection tree) written in a
754 Lisp-like way. The quast may possibly be preceded by the definition
755 of one or several new parameters (see below).
757 The vector coefficients may be either integers or rationals written as
759 @samp{numerator/denominator}. The latter case occurs if @samp{Nq} had been
760 set to 0 in the input file.
762 In the solution, a @samp{Vector} represents an affine form; each entry
763 is the coefficient of the corresponding parameter (the parameter of
764 the same rank). The last entry is the additive constant.
766 The definition of a new parameter begins with the key-word
767 @samp{newparm}, then an index (rank) number, a vector of coefficients, and a
768 denominator. The new parameter is equal to the integer division of the
769 vector by the denominator. The new parameter can only appear in the
770 @samp{Quast} following its definition. Introducing a new parameter adds
771 one entry in the list of parameters, so the length of vectors in the
772 solution is not constant. However, this length is always equal to 1 plus
773 the number of original parameters plus the number of new parameters
776 The solution is a multi-level conditional expression (a
777 tree of nested conditionals.) A predicate expression @math{p} should be
778 understood as the boolean expression
783 @math{p} >= @math{0}.
785 Leaves of the conditional tree are either @samp{()}, meaning that
786 the input problem has no solution, or a @samp{Form}. A @samp{Form}
787 is a list of vectors, each vector giving the value of the corresponding
794 @node Example (part 2)
795 @subsection Example (part 2)
796 The output of PIP is not intended for human consumption.
797 No attempt has been made to implement a pretty-printer. In the interest
798 of readability, some of the result files in this paper have been beautified
799 by hand. The reader should not be surprised if he gets results with
800 different layouts when running the examples.
802 Here is the exact output solution file for the previous example
803 (@pxref{Example (part 1)}):
806 ( ( Lower bound on j after loop inversion.
807 Unknowns: j i, parameters: k m n.
819 To express this solution, no new parameter had to be introduced. The
820 form associated to the first conditional is
821 @math{(-1)*k + (1)*m + (0)*n + (0)*1 = m-k}
822 so the test should be read as
827 @math{m-k} >= @math{0}.
829 If this inequality holds, then the solution is @math{<0,k>}.
830 Otherwise, the solution is @math{<k-m,m>}.
832 To sum things up, the lexicographical minimum of
841 @code{if m-k >= 0 then <0, k> else <k-m, m>}.
843 Hence the lower bound on the first coordinate:
845 @code{if m-k >= 0 then 0 else k-m}.
849 @c %/*************************************************************************
851 @c % *************************************************************************/
855 PIP is called by the following command:
857 pip [-s|-v...] [-d] [-z] [input [output]]
859 The default behavior of PIP is to read the input informations from the
860 standard input and to print the solution (or some error messages if
861 anything went wrong) on the standard output. Options and messages are
862 discussed in next sections.
871 PIP's behavior and the output shape is under the user control thanks
872 to few options which are detailed in this section.
873 @code{input} is the input file. If none is given, input is standard input.
874 For instance, we can call PIP to process the
875 input file @code{test.pip} with default options by typing:
876 @code{pip test.pip} or @code{more test.pip | pip}.
877 If no @code{output} file is given, then the results are printed to the
887 @subsubsection Verbosity
888 PIP prints some information on the screen after having solved a
889 problem. The @code{-s} (silent mode) switches this feature off. On the
890 contrary, the verbose @code{-v} option tells PIP to copy, in a file,
891 all the input data and all the intermediary results. The name of this
892 file is given either by the variable @code{DEBUG} in the environment or
893 is built by @code{mkstemp}. The number of consecutive @code{-v}'s
894 (from 0 to 3) controls the degree of verbosity of Pip.
895 A word of caution: debug files may become very large very fast.
898 @subsubsection Simplification
899 If the @code{-z} option is given, then the solution is somewhat simplified.
900 The solution of a parametric problem may be in the form of a quast all
901 of whose leaves are nil. This means in fact that the original polyhedron
902 is empty whatever the values of the parameters. An example, due to Dirk
903 Fimmel, is the following:
922 @noindent Without the @code{-z} option, the solution is:
931 (newparm 2 (div #[ 0 2 3] 6))
932 (newparm 3 (div #[ 0 2 10 7] 12))
933 (newparm 4 (div #[ 0 4 0 2 1] 6))
936 (newparm 2 (div #[ 0 4 3] 6))
961 @noindent Inspection reveals that all leaves are @code{()}. With the
962 @code{-z} option, the solution is much simpler:
973 @subsubsection Deepest Cut
974 When Pip is asked for an integral solution, it constructs new constraints
975 (the so-called @emph{cuts}) which eliminate fractional solutions and keep
976 all integer solutions. The selection of cuts is somewhat arbitrary. When
977 the @code{-d} option is given, Pip uses this degree of freedom to select
978 the @emph{deepest cut} according to an algorithm by Gondran. Intractable
979 problems may become tractable when using this option, and conversely.
985 PIP may print various messages to give, e.g., some information on the
986 complexity of the problem or to help the user to solve some errors.
996 @subsubsection General Messages
999 @item @samp{Version X.x}. Currently, @code{D.1}.
1000 @item @samp{cross : <n>, alloc : <m>} This message is output after solving
1001 each problem. The value of @code{<n>} gives an idea of the complexity of
1006 @subsubsection Errors Related to the Input
1009 @item @samp{Syntax error}: unbalanced parentheses in the input.
1010 @item @samp{Too much variables}.
1011 @item @samp{Too much parameters}: check the input and/or change the value of
1012 constants @code{MAXCOL} and @code{MAXPARM} in file @code{type.h}, then
1014 @item @samp{Your computer doesn't have enough memory}: self explanatory.
1018 @subsubsection Errors Related to the Solution
1021 @item @samp{Integer Overflow}: A number has been generated that is too large
1022 to be accommodated in a 32 bit integer. Check the input and/or switch
1023 to Zbigniew Chamski's infinite precision PIP.
1024 @item @samp{The solution is too complex}: the solution quast has grown beyond
1025 the memory allocated to it. Check the input and/or change the value of
1026 constant @code{SOL\_SIZE} in file @code{type.h}, then rebuild PIP.
1027 @item @samp{Memory overflow}: self explanatory.
1028 @item @samp{<file> unaccessible}: one of the input, output or debug file
1032 @node Implementation
1033 @subsubsection Implementation Errors
1035 All such error messages begin by the word @samp{Syserr}. These messages
1036 indicate a bug in the implementation. You should report such events
1037 by sending a copy of the input file by e-mail to the author,
1038 @code{Paul.Feautrier@@ens-lyon.fr} who will endeavor to solve the problem
1039 as soon as possible.
1041 @c %/*************************************************************************
1042 @c % * The power of PIP *
1043 @c % *************************************************************************/
1045 @section The Power of PIP
1047 In the following sections, we explain how PIP can be used to solve
1048 extended classes of problems:
1050 @item Problems where equalities occur.
1051 @item Problems where a lexicographic @emph{maximum} has to be found.
1052 @item Cases when linear cost functions are to be optimized.
1053 @item Problems where unknowns and/or parameters may be negative.
1057 * Handling Equalities::
1058 * The Bigparm Trick::
1059 * Computing Lexicographic Maxima::
1060 * Optimizing Linear Cost Functions::
1061 * Negative Unknowns and Parameters::
1062 * Mixed Programming::
1065 @node Handling Equalities
1066 @subsection Handling Equalities
1067 When the input problem contains @math{r} affine equalities
1070 @math{1 \leq i\leq r},
1075 one may just write @math{r} inequalities
1082 and @math{r} inequalities
1089 thus satisfying PIP's input syntax.
1090 However, one may notice that only @math{r+1} inequalities
1093 @math{f_i \geq 0}, @math{1\leq i\leq r},
1096 @math{f_i >= 0}, @math{1 <= i <= r},
1098 and the following inequality:
1100 @math{\sum_{i=1}^{r} f_i \leq 0}.
1103 @math{sum_(i=1,r) f_i <= 0}.
1107 @node The Bigparm Trick
1108 @subsection The Bigparm Trick
1109 In some cases, it is useful to suppose that one parameter in a PIP problem
1110 grows @emph{very large}. Some examples will be given in the following sections.
1111 Let @math{B} be the name of this parameter. Suppose that in the solution, one
1112 of the predicates is:
1115 @math{a B + b \geq 0,}
1118 @math{a B + b >= 0,}
1121 @noindent where @math{b} may depend on all other parameters. For @math{B}
1122 large enough, if @math{a > 0}
1123 then the predicate is true, and if @math{a < 0} then the predicate is false.
1124 One can find the limit shape of the solution by removing such tests and
1125 replacing them by their true of false branch, as appropriate. This can be done
1126 a posteriori on the results of PIP, or PIP can do it @emph{on the fly}
1127 while solving the problem. This last method is more efficient, since it
1128 tends to simplify the solution.
1130 PIP is notified of the presence of a big parameter by setting the @samp{Bg}
1131 argument to a positive value. This value is the rank of the big parameter
1132 in the problem domain. Hence, the lowest admissible value for @samp{Bg}
1135 The reader should convince himself that in the presence of two big
1136 parameters, no such simplifications are possible unless one has some
1137 information on the relative size of the parameters. Such situations
1138 should be handled by giving PIP ordinary parameters, and doing the
1139 simplification on the solution in the light of extra knowledge.
1141 @node Computing Lexicographic Maxima
1142 @subsection Computing Lexicographic Maxima
1143 To get the maximum of an unknown @math{x}, minimize @math{B - x}, where
1144 B is a new @emph{big} parameter. Adding a parameter just adds one column
1145 in the problem domain. The fact that this column corresponds to a big
1146 parameter is specified by setting the 5-th switch to a positive value,
1147 this value being the position of the column of B in the problem
1148 domain (column index starts to 0).
1150 These cases can be handled systematically in the following way. Suppose that
1151 we are asked for the integer maximum of the polyhedron:
1154 \left\{\eqalign{x &\geq 0\cr
1157 y &\geq 2x - 3\cr}\right.
1170 Let us introduce the new unknowns:
1172 $$ x'= B - x, \;\; y' = B - y ,$$
1175 @math{x'= B - x}, @math{y' = B - y},
1177 where @math{B} is the big parameter. The system translates to:
1180 \left\{\eqalign{ -x' + B &\geq 0\cr
1182 -x' + 3y' + 12 -2B &\geq 0\cr
1183 2x' - y' + 3 - B &\geq 0\cr}\right.
1191 -x' + 3y' + 12 -2B >= 0,
1192 2x' - y' + 3 - B >= 0.
1196 Finding the maximum of @math{(x,y)^T} is equivalent to finding the minimum of
1197 @math{(x', y')^T}, provided @math{B} is large enough. The solution of the
1200 ( (a maximization problem 1)
1207 (newparm 1 (div #[ 1 1] 2))
1223 Suppose we tell PIP that @math{B} is a large parameter. The input file is now:
1226 ( (a maximization problem)
1237 @noindent and the solution is much simpler:
1240 ( (a maximization problem 1)
1247 The reader may care to check that this result is equivalent to the
1248 previous one as soon as @math{B > 5}. The position of the minimum is:
1249 @math{x' = B - 4}, @math{y' = B - 5}, from which we deduce:
1250 @math{x = 4, y = 5}. As
1251 expected, @math{B} has disappeared from the solution. If this does not happen,
1252 we observe first that @math{B} must have a positive coefficient in the result
1253 (if not, one of the inequalities
1260 would be violated for
1261 @math{B} large enough). This means that the original polyhedron is not bounded,
1262 since, whatever @math{B}, it contains a point whose coordinates are
1263 @math{O(B)}, and hence has no maximum.
1265 @node Optimizing Linear Cost Functions
1266 @subsection Optimizing Linear Cost Functions
1267 The problem here is to compute the minimum of a linear function
1269 @math{\vec{c}\vec{x}}
1272 @math{@strong{c}@strong{x}}
1274 in a polyhedron @math{@strong{P}},
1282 is a vector with integer coefficients. Let us introduce
1283 a new unknown @math{y}. Solve the linear programming problem obtained by
1284 adding the constraint
1286 @math{y \geq \vec{c}\vec{x}}
1289 @math{y >= @strong{c}@strong{x}}
1291 to the defining constraints of @math{@strong{P}}.
1292 @math{y} should be the first unknown in the lexicographic ordering. Let
1294 @math{(y_s, \vec{x}_s)}
1297 @math{(y_s, @strong{x}_s)}
1299 be the solution. Suppose that the minimum of
1301 @math{\vec{c}\vec{x}}
1304 @math{@strong{c}@strong{x}}
1306 in @math{@strong{P}} is obtained at
1315 @math{y_m = \vec{c}\vec{x}_m}.
1318 @math{y_m = @strong{c}@strong{x}_m}.
1327 is in @math{@strong{P}}, and
1329 @math{y_s \geq \vec{c}\vec{x}_s},
1332 @math{y_s >= @strong{c}@strong{x}_s},
1336 @math{y_s \geq y_m}.
1343 @math{(y_m, \vec{x}_m)}
1346 @math{(y_m, @strong{x}_m)}
1348 satisfies the constraints of the problem of which
1350 @math{(y_s, \vec{x}_s)}
1353 @math{(y_s, @strong{x}_s)}
1355 is the lexicographic minimum. Hence
1357 @math{(y_s, \vec{x}_s) \ll (y_m, \vec{x}_m)},
1360 @math{(y_s, @strong{x}_s) << (y_m, @strong{x}_m)},
1362 and, since @math{y} is the first unknown,
1364 @math{y_s \leq y_m}.
1369 Hence, @math{y_m = y_s}.
1370 There is no guarantee, however, that
1372 @math{\vec{x}_s = \vec{x}_m}
1375 @math{@strong{x}_s = @strong{x}_m}
1377 (but if they differ, solutions are equally good since
1379 @math{y_s = \vec{c}\vec{x}_s}
1382 @math{y_s = @strong{c}@strong{x}_s}
1386 @math{y_m = y_s = \vec{c}\vec{x}_s = \vec{c}\vec{x}_m}).
1389 @math{y_m = y_s = @strong{c}@strong{x}_s = @strong{c}@strong{x}_m}).
1392 @node Negative Unknowns and Parameters
1393 @subsection Negative Unknowns and Parameters
1394 Suppose we want to find the minimum of @math{f(i,j) = i-2j} over the square
1397 @math{@{(i,j) | -4 n -20 \leq i + j \leq 0, -2 n - 10 \leq i - j \leq 2 n + 10@}}
1400 @math{@{(i,j) | -4 n -20 <= i + j <= 0, -2 n - 10 <= i - j <= 2 n + 10@}}
1403 (this example was proposed and solved by Pierre Boulet):
1405 @image{images/negatifs,8cm}
1406 As above, we introduce a new unknown @math{f} and the inequality
1408 @math{f-i+2j \geq 0}.
1413 Since we want to optimize @math{f}, @math{f}
1414 will appear as the first unknown.
1416 To allow @math{n} (or any other parameter) to become negative,
1417 we apply the standard trick of replacing @math{n} by @math{n = n' - n''},
1418 where @math{n'} and @math{n''} are two new parameters, both non-negative.
1419 For handling possibly negative unknows, we add a number @math{G} to each
1420 of the unknowns that ensures that
1423 \eqalign{ f' &= G + f\cr
1437 @noindent are all non-negative. That is, @math{G} should be such that
1440 G \geq \max(0,-i,-j,-f).
1445 @math{G >= max(0,-i,-j,-f)}.
1449 is again a big parameter.
1450 After replacement of @math{i,j,n} and @math{f} by the new variables
1451 @math{i',j',n',n''} and @math{f'}, we obtain the set
1454 \eqalign{ \{\, (f',i',j') \mid
1455 & f' -i' + 2j' - 2 G \geq 0 \, \wedge \cr
1456 & 4 (n'-n'') -20 \leq i' + j' - 2 G \leq 0 \, \wedge \cr
1457 & -2 (n'-n'') - 10 \leq i' - j' \leq 2 (n'-n'') + 10 \,\},}
1463 @math{@{(f',i',j') | f' -i' + 2j' - 2 G >= 0,
1464 4 (n'-n'') -20 >= i' + j' - 2 G >= 0,
1465 -2 (n'-n'') - 10 >= i' - j' >= 2 (n'-n'') + 10@}}
1469 which corresponds to the following input:
1472 ( ( Solving MIN(i-2.j) under the following constraints:
1473 Unknowns may be negative.
1474 Order: f' i' j' constant G n'' n'
1477 ( #[ 1 -1 2 0 -2 0 0 ]
1478 #[ 0 1 1 20 -2 -4 4 ]
1479 #[ 0 -1 -1 0 2 0 0 ]
1480 #[ 0 1 -1 10 0 -2 2 ]
1481 #[ 0 -1 1 10 0 -2 2 ]
1491 ( ( Solving MIN(i-2.j) under the following constraints:
1492 Unknowns may be negative.
1493 Order: f' i' j' constant G n'' n' -1
1496 (list #[ 1 3 -3 -15]
1505 which should be read as:
1508 \eqalign{(f',i',j') =\; & {\tt if}\; (-n''+n'+5 \geq 0) \cr
1509 & {\tt then} \; (G+3n''-3n'-15, G+n''-n'-5,G-n''+n'+5) \cr
1510 & {\tt else} \; \bot}
1516 @math{(f',i',j') = @strong{if} (-n''+n'+5 >= 0)
1517 @strong{then} (G+3n''-3n'-15, G+n''-n'-5,G-n''+n'+5)
1518 @strong{else} bottom}
1522 That is, in the original coordinate system:
1525 (f,i,j) = {\tt if}\; (n \geq -5) \; {\tt then} \; (-3n-15, -n-5, n+5)
1526 \; {\tt else} \; \bot
1532 @math{(f,i,j) = @strong{if} (n >= -5)
1533 @strong{then} (-3n-15, -n-5, n+5)
1534 @strong{else} bottom}
1538 @noindent I.e., the minimum value for function @math{f} is @math{-3n-15},
1539 and this value is reached at point @math{(-n-5, n+5)}.
1540 This minimum exists only if
1547 otherwise, the feasible set is empty.
1549 @node Mixed Programming
1550 @subsection Mixed Programming
1551 A mixed program is a program in which some variables are constrained
1552 to be integers while others may take rational values. Suppose for
1553 instance that we have to solve:
1556 \eqalign{S = & \min a x + b y,\cr
1557 & A x + B y + c \geq 0,}
1563 @math{S = min a x + b y,
1564 A x + B y + c >= 0},
1568 where @math{y} is the vector of the integer variables. First, solve
1571 \eqalign{T = & \min a x,\cr
1572 & A x + B y + c \geq 0,}
1579 A x + B y + c >= 0},
1583 in rational, with @math{y} as parameters. The result is a quast.
1584 To each leaf @math{i} is associated a linear function @math{f_i(y)}
1585 and a set of inequalities
1587 @math{C_i y + d_i \geq 0}.
1590 @math{C_i y + d_i >= 0}.
1592 @math{T} is equal to
1593 @math{f_i} when @math{y} is such that the corresponding inequalities
1594 are satisfied. For each @math{i}, solve the problem:
1597 \eqalign{S_i = & \min f_i(y) + b y,\cr
1598 & C_i y + d_i \geq 0,}
1604 @math{S_i = min f_i(y) + b y,
1609 in integers. The final result is the minimum of all @math{S_i}.
1610 Obviously, the method can accommodate parameters in the
1611 constraints. The @math{S_i} will be functions of these
1612 parameters, and the minimum must be computed symbolically.
1615 @c %/*************************************************************************
1616 @c % * PIP Library *
1617 @c % *************************************************************************/
1619 @chapter Using the PIP Library
1620 The PIP Library (PipLib for short) was implemented to allow the user to call
1621 PIP directly from his programs, without file accesses or system calls. The
1622 user only needs to link his programs with C libraries. The
1623 PipLib mainly provides one function which takes as input the problem description
1624 and some options, and returns a @code{Quast}
1625 (@pxref{Reading the Output File}) corresponding to the solution. Some
1626 other functions are provided for convenience reasons ; they
1627 are described in a further section (@pxref{PipLib Functions}).
1628 Most of them require
1629 some specific structures to represent the problem or
1630 the solution; these structures are described in the next section
1631 (@pxref{PipLib Data Structures}).
1635 * PipLib Data Structures::
1636 * PipLib Functions::
1637 * Example of Library Utilization::
1641 @node PipLib Data Structures
1642 @section PipLib Data Structures Description
1643 In this section, we describe the data structures used by the PIP
1644 library to represent and to process a parametric integer programming problem.
1657 @subsection PipMatrix
1658 @noindent The @code{PipMatrix} structure is a copy of the PolyLib
1659 @code{Matrix} data structure (@pxref{Wil93}, and @code{polylib/types.h}).
1660 This structure is devoted to represent a set of constraints. It is
1661 defined as the following:
1666 @{ unsigned NbRows ; /* Number of rows. */
1667 unsigned NbColumns ; /* Number of columns. */
1668 Entier ** p ; /* Array of pointers to the matrix rows. */
1669 Entier * p_Init ; /* Matrix rows contiguously in memory. */
1670 int p_Init_size ; /* For internal use. */
1672 typedef struct pipmatrix PipMatrix;
1676 @noindent The whole matrix is stored in memory row after row at the
1677 @code{p_Init} address. @code{p} is an array of pointers where
1678 @code{p[i]} points to the first element of the @math{i^{th}} row.
1679 @code{NbRows} and @code{NbColumns} are respectively the number of
1680 rows and columns of the matrix.
1681 Each row corresponds to a constraint. The first element of each row is an
1682 equality/inequality tag. The
1683 constraint is an equality @math{p(x) = 0} if the first element is 0, but it is
1691 if the first element is 1.
1692 The next elements are the unknown coefficients, followed by the parameter
1693 coefficients, then the scalar coefficient.
1694 @strong{Please notice that the ordering of unknown and scalar coefficients
1695 is different from the input file of the PIP software} (this is due
1696 to historical reasons).
1697 For instance, in the problem we used as example
1698 (@pxref{Example (part 1)}) the domain is defined by
1699 the following three constraints:
1703 \hbox{$ \cases{ -i + m &$= 0$\cr
1705 j + i - k &$\geq 0$}$}
1719 @noindent would be represented by the following rows:
1723 # eq/in i j k m n cst
1730 @noindent To be able to provide different precision version (PIP/PipLib
1731 supports 32 bits, 64 bits and arbitrary precision through the GMP library),
1732 the @code{Entier} type depends on the configuration options (it may be
1733 @code{long int} for 32 bits version, @code{long long int} for 64 bits version,
1734 and @code{mpz_t} for multiple precision version).
1735 The @code{p_Init_size} field is needed to free
1736 the memory allocated by @code{mpz_init} in the multiple precision release.
1737 Set this field to 0 if you are @emph{not} using multiple precision.
1738 Set this field to the size of the @code{p_Init} array if you
1739 initialized it yourself and if you are using the multiple precision version.
1741 The context is defined by one constraint:
1750 @math{-k + m + n >= 0}
1754 @noindent the row corresponding to this constraint would be:
1763 @noindent @code{p_Init_size} is needed by the to free the memory
1764 allocated by @code{mpz_init} in the multiple precision release.
1768 @subsection PipVector
1773 @{ int nb_elements ; /* Number of elements in the vector */
1774 Entier * the_vector ; /* Vector of numerators */
1775 Entier * the_deno ; /* Vector of denominators */
1777 typedef struct pipvector PipVector ;
1781 @noindent The @code{PipVector} structure represents a @code{Vector}
1782 as described in the ouput grammar (@pxref{Reading the Output File}).
1783 @code{nb_elements} is the number of vector elements, @code{the_vector} is
1784 an array which contains the numerators of these elements and @code{the_deno}
1785 is an array which contains their denominators: the @math{i^{th}} element is
1786 @code{the_vector[i]/the_deno[i]}.
1790 @subsection PipNewparm
1795 @{ int rank ; /* Index of the newparm */
1796 PipVector * vector ; /* Vector of parameter coefficients */
1797 Entier deno ; /* Denominator for the whole vector */
1798 struct pipnewparm * next ; /* Pointer to next newparm */
1800 typedef struct pipnewparm PipNewparm ;
1804 @noindent The @code{PipNewparm} structure represents a @code{NULL}
1805 terminated linked list of @code{Newparm} as described in the ouput grammar
1806 (@pxref{Reading the Output File}).
1807 For each @code{Newparm}, the rank is @code{rank},
1808 the vector of coefficients is pointed by @code{vector}, and the denominator
1809 is @code{deno}. @code{next} is a pointer to the next @code{PipNewparm}
1819 @{ PipVector * vector ; /* Pointer to a vector */
1820 struct piplist * next ; /* Pointer to next vector */
1822 typedef struct piplist PipList ;
1826 @noindent The @code{PipList} structure represents a @code{NULL} terminated
1827 linked list of @code{Vector} as described in the ouput grammar
1828 (@pxref{Reading the Output File}).
1829 @code{vector} is a pointer to the vector of the current node and
1830 @code{next} is a pointer to the next @code{PipList} structure.
1834 @subsection PipQuast
1839 @{ PipNewparm * newparm ; /* List of newparms */
1840 PipList * list ; /* The solution (if no condition) */
1841 PipVector * condition ; /* The condition */
1842 struct pipquast * next_then ; /* Quast if condition is true */
1843 struct pipquast * next_else ; /* Quast if condition is false */
1844 struct pipquast * father ; /* Pointer to father quast */
1846 typedef struct pipquast PipQuast ;
1850 @noindent The @code{PipQuast} represents a @code{Quast} as described in the
1851 ouput grammar (@pxref{Reading the Output File}). Each @code{Quast}
1852 has a tree structure and begins with a list of @code{Newparm}
1853 (field @code{newparm}). If the pointer @code{condition} is not @code{NULL}, the
1854 list of @code{Newparm} is followed by a conditional structure : if the condition
1855 pointed by @code{condition} is true, then the solution continues in the
1856 @code{Quast} pointed by @code{next_then}, in the @code{Quast} pointed by
1857 @code{next_else} otherwise. If the pointer @code{condition} is @code{NULL}, the
1858 list of @code{Newparm} is followed by a list of vectors (field @code{list}).
1859 For @code{Quast} manipulation convenience, a pointer to the father in the tree
1860 is provided (field @code{father}), obviously the father of the root is
1865 @subsection PipOptions
1870 @{ int Nq ; /* 1 for integral solution, else 0 */
1871 int Verbose ; /* Verbosity level (from -1 to 3) */
1872 int Simplify ; /* 1 to simplify solution, else 0 */
1873 int Deepest_cut ; /* 1 to use Deepest Cut algo, else 0 */
1874 int Maximize; /* 0 for lexico minimum, 1 for maximum */
1875 int Urs_parms; /* 0 for non-negative parms, else -1 */
1876 int Urs_unknowns; /* 0 for non-negative unknowns, else -1 */
1878 typedef struct pipoptions PipOptions ;
1882 @noindent The @code{PipOptions} structure contains all the possible options
1883 ruling the PIP behaviour. Every @code{PipOptions} structure should be created
1884 and filled with the default values by the @code{pip_options_init}
1885 function (@pxref{pip_options_init}) to ensure forward compatibility.
1886 Only after this, the user should modify
1887 the structure entries according to his wishes:
1890 @item @code{Nq}: a boolean set to 1 if an integer solution is needed, 0
1892 @item @code{Verbose}: a graduate value for debug informations:
1894 @item -1: absolute silence,
1895 @item 0: relative silence,
1896 @item 1: information on cuts when an integer solution is required,
1897 @item 2: information on pivots and determinants,
1898 @item 3: information on arrays.
1900 Each option include the preceding one.
1901 If @code{Verbose} is not @math{-1}, most of the processing will be
1902 printed in a file. The file name is generated at random
1903 (by @code{mkstemp}) or set with environment variable DEBUG.
1904 @item @code{Simplify}: a boolean set to 1 if some trivial quast simplifications
1905 are needed (recursive elimination of degenerated patterns like
1906 @code{if #[...] () ()}), 0 otherwise,
1907 @item @code{Deepest_cut}: a boolean set to 1 if PIP has to use the deepest cut
1908 algorithm, 0 otherwise,
1909 @item @code{Maximize}: a boolean set to 0 if the lexicographic
1910 minimum is requested, or to 1 for the lexicographic maximum. When trying
1911 to find the lexicographic maximum, the method used is the one
1912 presented in a previous section
1913 (@pxref{Computing Lexicographic Maxima}):
1914 if no bigparm was set, a new (big) parameter is automatically created
1915 by adding a new column (at the last position) to the
1916 constraint system. This optional extra parameter is removed again from
1917 the output. Unbounded solutions have their @code{the_deno} set to zero.
1918 Note that setting this option allows for negative solutions.
1919 This may change in a future release.
1920 @item @code{Urs_parms}: controls signs of parameters:
1922 @item -1: all parameters have unrestricted sign,
1923 @item 0: all parameters are non-negative.
1925 @item @code{Urs_unknowns}: controls signs of unknowns:
1927 @item -1: all unknowns have unrestricted sign,
1928 @item 0: all unknowns are non-negative.
1933 @node PipLib Functions
1934 @section PipLib Functions
1938 * pip_options_init::
1940 * pip_matrix_alloc::
1942 * Printing Functions::
1943 * Memory Deallocation Functions::
1947 @subsection pip_solve
1951 PipQuast * pip_solve
1952 ( PipMatrix * domain, /* Domain where to find a solution */
1953 PipMatrix * context, /* Constraints on parameters */
1954 int Bg, /* Bigparm index (-1 if no bigparm) */
1955 PipOptions * options /* Options */
1960 @noindent The @code{pip_solve} function solves a linear problem provided as
1961 input. The first three parameters describe the problem that the user wants
1962 to solve. The last parameter describe the options that the user has to set.
1963 These parameters are:
1965 @item @code{domain}: a pointer to the equations and inequalities system which
1966 describe the unknown domain in the PolyLib constraints matrix shape,
1967 @item @code{context}: a pointer to the equations and inequalities system
1968 satisfied by the parameter context in the PolyLib constraints matrix
1969 shape (it can be @code{NULL} if there is no context). @strong{Caution:
1970 if there are parameters but no constraints on them, don't set
1971 @code{context} to @code{NULL} but to a matrix with the right column
1972 number (i.e., number of parameters + 2) and 0 rows because the PipLib
1973 uses this information to know the parameter number.}
1974 @item @code{Bg}: the column rank of the bignum (first column rank is 0), or a
1975 negative value if there is no big parameter in the problem to be solved,
1976 if unsure, just set to -1,
1977 @item @code{options}: a pointer to a data structure containing the options
1978 ruling the behaviour of PIP.
1980 This function returns a pointer to a @code{PipQuast} structure containing the
1981 solution, it will be @code{NULL} if the context is @code{void}.
1984 @node pip_options_init
1985 @subsection pip_options_init
1989 PipOptions * pip_options_init(void) ;
1993 @noindent The @code{pip_options_init} function allocates the memory space
1994 for a @code{PipOptions} structure and fills it with the default values:
1996 @item @code{Nq} @math{= 1}: an integer value is required,
1997 @item @code{Verbose} @math{= 0}: no debug informations,
1998 @item @code{Simplify} @math{= 0}: do not try to simplify solutions,
1999 @item @code{Deepest_cut} @math{= 0}: do not use deepest cut algorithm,
2000 @item @code{Maximize} @math{= 0}: compute the lexicographic minimum,
2001 @item @code{Urs_parms} @math{= 0}: all parameters are non-negative,
2002 @item @code{Urs_unknowns} @math{= 0}: all unknowns are non-negative.
2004 We strongly recommend to use this function to create and initialize any
2005 @code{PipOptions} structure. In this way, if some new options appear in
2006 the future, there will be no compatibility issues.
2010 @subsection pip_close
2014 void pip_close(void) ;
2018 @noindent The @code{pip_close} function
2019 frees the memory space that have been allocated
2020 for few global variables PipLib needs. This function has to be called when
2021 PipLib is no more useful in order to prevent slight memory leaks.
2024 @node pip_matrix_alloc
2025 @subsection pip_matrix_alloc
2029 PipMatrix * pip_matrix_alloc
2036 @noindent The @code{pip_matrix_alloc} function allocates the memory space
2037 for a @code{PipMatrix} structure with @code{nb_rows} rows and @code{nb_columns}
2038 columns. It fills the @code{Nb_Rows}, @code{Nb_Columns} and @code{p} fields
2039 and initializes the matrix entries to 0, then it returns a pointer to this
2043 @node pip_matrix_read
2044 @subsection pip_matrix_read
2048 PipMatrix * pip_matrix_read(FILE *) ;
2052 @noindent The @code{pip_matrix_read} function reads a matrix from a file. It
2053 takes as input a pointer to the file it has to read (possibly @code{stdin}), and
2054 returns a pointer to a @code{PipMatrix} structure. The input has the following
2057 @item some optional comment lines which begin with @code{#},
2058 @item the row numbers and column numbers, possibly followed by comments,
2060 @item the matrix rows, each row must be on a single line and is possibly
2061 followed by comments.
2063 For instance, in the example problem (@pxref{Example (part 1)}) the domain
2064 may be defined as follows
2068 # This is the domain
2069 3 7 # 3 lines and 7 columns
2070 1 0 -1 0 1 0 0 # -i + m >= 0
2071 1 -1 0 0 0 1 0 # -j + n >= 0
2072 1 1 1 -1 0 0 0 # j + i - k >= 0
2077 @node Printing Functions
2078 @subsection Printing Functions
2082 void pip_matrix_print(FILE *, PipMatrix *) ;
2083 void pip_vector_print(FILE *, PipVector *) ;
2084 void pip_newparm_print(FILE *, PipNewparm *, int indent) ;
2085 void pip_list_print(FILE *, PipList *, int indent) ;
2086 void pip_quast_print(FILE *, PipQuast *, int indent) ;
2087 void pip_options_print(FILE *, PipOptions *) ;
2091 @noindent There is a printing function for each structure of the PipLib.
2092 They all take as input
2093 a pointer to a file (possibly @code{stdout}) and a pointer to a structure.
2094 Some of them takes as input an
2095 indent step. They print the structure contents to the file without indent if
2096 @code{indent} @math{< 0}, with an indentation step of @code{indent} otherwise.
2099 @node Memory Deallocation Functions
2100 @subsection Memory Deallocation Functions
2104 void pip_matrix_free(PipMatrix *) ;
2105 void pip_vector_free(PipVector *) ;
2106 void pip_newparm_free(PipNewparm *) ;
2107 void pip_list_free(PipList *) ;
2108 void pip_quast_free(PipQuast *) ;
2109 void pip_options_free(PipOptions *) ;
2113 @noindent There is a memory deallocation function for each structure of
2114 the PipLib. They free the allocated memory for the structure.
2117 @node Example of Library Utilization
2118 @section Example of Library Utilization
2119 Here is a simple example showing how one can use the PipLib, assuming that
2120 a basic installation has been done. The following C program reads a domain and
2121 its context on the standard input then prints
2122 the solution on the standard output.
2123 Options are preselected : there is no bignum, we are looking for an integral
2124 solution without simplification and we don't want debug informations.
2125 This example is provided in the @code{example} directory of the
2126 PIP/PipLib distribution.
2132 # include <piplib/piplib64.h>
2135 @{ PipMatrix * domain, * context ;
2136 PipQuast * solution ;
2137 PipOptions * options ;
2139 options = pip_options_init() ;
2140 domain = pip_matrix_read(stdin) ;
2141 context = pip_matrix_read(stdin) ;
2143 solution = pip_solve(domain,context,-1,options) ;
2145 pip_options_free(options) ;
2146 pip_matrix_free(domain) ;
2147 pip_matrix_free(context) ;
2149 pip_quast_print(stdout,solution,0) ;
2156 @noindent The compilation command could be:
2158 gcc example.c -lpiplib64 -o example
2161 @noindent Supposing that the user wants to solve the example problem
2162 (@pxref{Example (part 1)}), he will type:
2174 @noindent And the program will answer:
2188 @c % ****************************** INSTALLING ********************************
2190 @chapter Installing PIP
2195 * Basic Installation::
2196 * Optional Features::
2202 First of all, it would be very kind to refer the following paper in any
2203 publication that result from the use of the PIP software or its library,
2204 @pxref{Fea88} (a bibtex entry is provided behind the title page of this
2205 manual, along with copyright notice, and in the PIP/PipLib home
2206 @code{http://www.PipLib.org}.
2208 This library is free software; you can redistribute it and/or modify it
2209 under the terms of the GNU Lesser General Public License as published by
2210 the Free Software Foundation; either version 2.1 of the License, or (at
2211 your option) any later version.
2212 This program is distributed in the hope that it will be useful,
2213 but WITHOUT ANY WARRANTY; without even the implied warranty of
2214 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2215 GNU General Public License for more details.
2216 @code{http://www.gnu.org/copyleft/gpl.html}
2220 @section Adjusting the Precision
2221 Pip is an all integer version of the dual simplex algorithm. As such,
2222 it has to handle integers whose size may grow exponentially as the
2223 computation proceeds. Integer overflow may occur and have to be checked.
2224 Since the hardware integer overflow exception is usually masked by
2225 the operating system or the compiler, overflow is detected by checking
2226 that a division somewhere in the algorithm, which can be proved to be
2227 exact by mathematical arguments, is indeed exact. If not, an error is
2228 reported and the computation stops.
2230 The size of the numbers to be handled depends strongly on the size of the
2231 constraint matrix and on the size of its coefficients.
2235 * Multiple Precision PIP::
2240 @subsection Bounded PIP
2241 The precision of the integer representation in the Pip code can be
2242 adjusted at compile time by giving options to the @code{configure}
2244 By giving @code{configure} the option @code{--enable-llint-version} you ask
2245 for long long int version only (64 bits). It results in a 64 bits Pip
2246 called @code{pip64}.
2247 By giving @code{configure} the option @code{--enable-int-version} you
2248 ask for int version only. It results in a 32 bits called
2249 @code{pip32} and a faster running time.
2252 @node Multiple Precision PIP
2253 @subsection Multiple Precision PIP
2254 Multiple Precision Pip is built on top of the GMP library
2255 (this library is freely available at @code{http://www.swox.com/gmp}).
2256 Each integer in the program is represented as a list of 32 bits numbers.
2257 All computations are done exactly, and the size of the numbers increases
2258 as needed to preserve exactness. It follows that no overflow is possible.
2259 However, when the size of numbers increases, computations get slower and
2260 slower, and memory overflow may occur in extreme cases. In well behaved
2261 problems, 32 bits are enough for the initial data, the size of intermediate
2262 results first increases up to a maximum, then decreases, and 32 bits
2263 are again enough for the results. Hence, it has been possible to keep
2264 the input format and output format of Multiple Precision Pip completely
2265 compatible with the formats of the bounded precision versions.
2267 To install Multiple Precision Pip, first install GMP according to the
2268 directions found at the above URL. Usually, the library is installed
2269 in @code{/usr/local/lib}, and the header files are in @code{/usr/local/include}.
2270 If this is not the case, you must adjust the Pip makefile by giving
2271 to the @code{configure} shell script the option @code{--with-gmp=PATH}, where
2272 @code{PATH} is the GMP library installation path. If GMP headers and
2273 libraries are not in the same installation path, you can be more precise
2274 by using @code{--with-gmp-include=PATH} and @code{--with-gmp-library=PATH}
2275 for GMP headers and libraries respectively.
2278 By giving @code{configure} the option @code{--enable-mp-version} you ask
2279 for a GMP version only. It results in a multiple precision Pip
2280 called @code{pipMP}.
2282 @node Basic Installation
2283 @section PIP Basic Installation
2285 Once downloaded and unpacked
2286 (e.g. using the @samp{tar -zxvf piplib-@value{VERSION}.tar.gz} command),
2287 you can compile PIP by typing the following commands on the PIP's root
2291 @item @code{./configure}
2293 @item And as root: @code{make install}
2296 Depending on the location of the GMP (and whether or not you want
2297 to use it), you may need to set the
2298 option @code{--with-gmp} of the configure script
2299 (e.g. @samp{./configure --with-gmp=/usr/local} with a default GMP
2302 The program binaries and object files can be removed from the
2303 source code directory by typing @code{make clean}. To also remove the
2304 files that the @code{configure} script created (so you can compile the
2305 package for a different kind of computer) type @code{make distclean}.
2307 Both the PIP software and PipLib library have been successfully compiled
2308 on the following systems:
2310 @item PC's under Linux, with the @code{gcc} compiler,
2311 @item PC's under Windows (Cygwin), with the @code{gcc} compiler,
2312 @item Mac's under MacOS X, with the @code{gcc} compiler,
2313 @item Sparc and UltraSparc Stations, with the @code{gcc} compiler.
2316 @node Optional Features
2317 @section Optional Features
2318 The @code{configure} shell script attempts to guess correct values for
2319 various system-dependent variables and user options used during compilation.
2320 It uses those values to create the @code{Makefile}. Various user options
2321 are provided by the PIP's configure script. They are summarized in the
2322 following list and may be printed by typing @code{./configure --help} in the
2323 PIP top-level directory.
2326 @item By default, the installation directory is @code{/usr/local}:
2327 @code{make install} will install the package's files in
2328 @code{/usr/local/bin}, @code{/usr/local/lib} and @code{/usr/local/include}.
2329 The user can specify an installation prefix other than @code{/usr/local} by
2330 giving @code{configure} the option @code{--prefix=PATH}.
2332 @item By default, both PIP software and PipLib library are compiled and installed.
2333 By giving @code{configure} the option @code{--without-pip} the user
2334 disable the compilation and installation of the PIP software.
2335 @c By giving @code{configure} the option
2336 @c @code{--without-lib} the user disable the compilation and installation of the
2339 @item By default, PIP is built in both 32 and 64 bits versions, and in
2340 multiple precision version if GMP is found by @code{configure}.
2341 To build only one version, the user may give to @code{configure} the options
2342 @code{--enable-int-version} or @code{--enable-llint-version} or
2343 @code{--enable-mp-version} to build only 32, 64 or multiple precision
2344 version respectively.
2346 @item By default, @code{configure} will look for the GMP library
2347 (necessary to build the multiple precision version) in standard
2348 locations. If necessary, the user can specify the GMP path by giving
2349 @code{configure} the option @code{--with-gmp=PATH}.
2352 @node Uninstallation
2353 @section Uninstallation
2354 The user can easily remove the PIP software and PipLib library from his system
2355 by typing (as root if necessary) from the PIP/PipLib top-level directory
2356 @code{make uninstall}.
2358 @c % **************************** DOCUMENTATION ******************************
2360 @chapter Documentation
2361 The Texinfo sources of the present document is provided in the @code{doc}
2362 directory. You can build it in either DVI format (by typing
2363 @code{texi2dvi piplib.texi}) or PDF format
2364 (by typing @code{texi2pdf piplib.texi}) or HTML format
2365 (by typing @code{makeinfo --html piplib.texi}, using @code{--no-split}
2366 option to generate a single HTML file) or info format
2367 (by typing @code{makeinfo piplib.texi}).
2369 @c % ****************************** REFERENCES ********************************
2375 @anchor{CPLEX}[CPLEX] @emph{http://www.ilog.com/products/cplex/}
2378 @anchor{Dant51}[Dant51] G.B. Dantzig. Maximization of a linear function of
2379 variables subject to linear inequalities. In Koopmans, T.C. (ed.),
2380 Activity analysis of production and allocation,
2381 John Wiley & Sons, New York, 339-347, 1951.
2384 @anchor{Fea88}[Fea88] Paul Feautrier. Parametric Integer Programming.
2385 Rairo Recherche Op@'erationnelle, 22(3):243--268, 1988.
2388 @anchor{Feau89}[Fea89] Paul Feautrier.
2389 Semantical analysis and mathematical programming; application to
2390 parallelization and vectorization.
2391 In M. Cosnard, Y. Robert, P. Quinton, and M. Raynal, editors,
2392 Workshop on Parallel and Distributed Algorithms, pages 309--320.
2393 Bonas, North Holland, 1989.
2396 @anchor{Fea92}[Fea92] P. Feautrier Some efficient solutions to the affine
2397 scheduling problem, part II: multidimensional time.
2398 International Journal of Parallel Programming, 21(6):389--420, December 1992.
2401 @anchor{Gom58}[Gom58] R. Gomory. Outline of an algorithm for integer
2402 solutions to linar programs. Bulletin of the American Mathematical
2403 Society 64:275-278, 1958.
2406 @anchor{Lem54}[Lem54] Lemke. The dual method for solving the linear
2407 programming problem. Naval Research Logistic Quarterly 22:978-981, 1954.
2410 @anchor{lp_solve}[lp_solve] @emph{http://groups.yahoo.com/group/lp_solve/}
2413 @anchor{Wil93}[Wil93] Doran K. Wilde.
2414 A library for doing polyhedral operations.
2415 Technical Report 785, IRISA, Rennes, France, 1993.
2422 @c % /*************************************************************************
2423 @c % * PART VI: END OF THE DOCUMENT *
2424 @c % *************************************************************************/
2425 @c @unnumbered Index