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 For handling possibly negative unknows, we add a number @math{G} to each
1417 of the unknowns that ensures that
1420 \eqalign{ f' &= G + f\cr
1434 @noindent are all non-negative. That is, @math{G} should be such that
1437 G \geq \max(0,-i,-j,-f).
1442 @math{G >= max(0,-i,-j,-f)}.
1446 is again a big parameter.
1447 Possibly negative parameters can be handled in a similar way,
1448 by adding an additional parameter @math{P} to each of the parameters,
1449 i.e., by considering @math{n' = n + P}. For each value of @math{n},
1450 there is a pair of non-negative values of @math{n'} and @math{P},
1451 so any solution that is valid for all non-negative values
1452 of @math{n'} and @math{P} satisfying the constraints, is also
1453 valid for all values of @math{n} satisfying the constraints.
1454 The same additional parameter @math{P} can be used to handle
1455 all possibly negative parameters, but @math{P} needs to be distinct
1456 from @math{G} and @math{P} need not be a big parameter.
1457 After replacement of @math{i,j,n} and @math{f} by the new variables
1458 @math{G,P,i',j',n'} and @math{f'}, we obtain the set
1461 \eqalign{ \{\, (f',i',j') \mid
1462 & f' -i' + 2j' - 2 G \geq 0 \, \wedge \cr
1463 & 4 (n'-P) -20 \leq i' + j' - 2 G \leq 0 \, \wedge \cr
1464 & -2 (n'-P) - 10 \leq i' - j' \leq 2 (n'-P) + 10 \,\},}
1470 @math{@{(f',i',j') | f' -i' + 2j' - 2 G >= 0,
1471 4 (n'-P) -20 >= i' + j' - 2 G >= 0,
1472 -2 (n'-P) - 10 >= i' - j' >= 2 (n'-P) + 10@}}
1476 which corresponds to the following input:
1479 ( ( Solving MIN(i-2.j) under the following constraints:
1480 Unknowns may be negative.
1481 Order: f' i' j' constant G P n'
1484 ( #[ 1 -1 2 0 -2 0 0 ]
1485 #[ 0 1 1 20 -2 -4 4 ]
1486 #[ 0 -1 -1 0 2 0 0 ]
1487 #[ 0 1 -1 10 0 -2 2 ]
1488 #[ 0 -1 1 10 0 -2 2 ]
1498 ( ( Solving MIN(i-2.j) under the following constraints:
1499 Unknowns may be negative.
1500 Order: f' i' j' constant G P n' -1
1503 (list #[ 1 3 -3 -15]
1512 which should be read as:
1515 \eqalign{(f',i',j') =\; & {\tt if}\; (-P+n'+5 \geq 0) \cr
1516 & {\tt then} \; (G+3P-3n'-15, G+P-n'-5,G-P+n'+5) \cr
1517 & {\tt else} \; \bot}
1523 @math{(f',i',j') = @strong{if} (-P+n'+5 >= 0)
1524 @strong{then} (G+3P-3n'-15, G+P-n'-5,G-P+n'+5)
1525 @strong{else} bottom}
1529 That is, in the original coordinate system:
1532 (f,i,j) = {\tt if}\; (n \geq -5) \; {\tt then} \; (-3n-15, -n-5, n+5)
1533 \; {\tt else} \; \bot
1539 @math{(f,i,j) = @strong{if} (n >= -5)
1540 @strong{then} (-3n-15, -n-5, n+5)
1541 @strong{else} bottom}
1545 @noindent I.e., the minimum value for function @math{f} is @math{-3n-15},
1546 and this value is reached at point @math{(-n-5, n+5)}.
1547 This minimum exists only if
1554 otherwise, the feasible set is empty.
1556 @node Mixed Programming
1557 @subsection Mixed Programming
1558 A mixed program is a program in which some variables are constrained
1559 to be integers while others may take rational values. Suppose for
1560 instance that we have to solve:
1563 \eqalign{S = & \min a x + b y,\cr
1564 & A x + B y + c \geq 0,}
1570 @math{S = min a x + b y,
1571 A x + B y + c >= 0},
1575 where @math{y} is the vector of the integer variables. First, solve
1578 \eqalign{T = & \min a x,\cr
1579 & A x + B y + c \geq 0,}
1586 A x + B y + c >= 0},
1590 in rational, with @math{y} as parameters. The result is a quast.
1591 To each leaf @math{i} is associated a linear function @math{f_i(y)}
1592 and a set of inequalities
1594 @math{C_i y + d_i \geq 0}.
1597 @math{C_i y + d_i >= 0}.
1599 @math{T} is equal to
1600 @math{f_i} when @math{y} is such that the corresponding inequalities
1601 are satisfied. For each @math{i}, solve the problem:
1604 \eqalign{S_i = & \min f_i(y) + b y,\cr
1605 & C_i y + d_i \geq 0,}
1611 @math{S_i = min f_i(y) + b y,
1616 in integers. The final result is the minimum of all @math{S_i}.
1617 Obviously, the method can accommodate parameters in the
1618 constraints. The @math{S_i} will be functions of these
1619 parameters, and the minimum must be computed symbolically.
1622 @c %/*************************************************************************
1623 @c % * PIP Library *
1624 @c % *************************************************************************/
1626 @chapter Using the PIP Library
1627 The PIP Library (PipLib for short) was implemented to allow the user to call
1628 PIP directly from his programs, without file accesses or system calls. The
1629 user only needs to link his programs with C libraries. The
1630 PipLib mainly provides one function which takes as input the problem description
1631 and some options, and returns a @code{Quast}
1632 (@pxref{Reading the Output File}) corresponding to the solution. Some
1633 other functions are provided for convenience reasons ; they
1634 are described in a further section (@pxref{PipLib Functions}).
1635 Most of them require
1636 some specific structures to represent the problem or
1637 the solution; these structures are described in the next section
1638 (@pxref{PipLib Data Structures}).
1642 * PipLib Data Structures::
1643 * PipLib Functions::
1644 * Example of Library Utilization::
1648 @node PipLib Data Structures
1649 @section PipLib Data Structures Description
1650 In this section, we describe the data structures used by the PIP
1651 library to represent and to process a parametric integer programming problem.
1664 @subsection PipMatrix
1665 @noindent The @code{PipMatrix} structure is a copy of the PolyLib
1666 @code{Matrix} data structure (@pxref{Wil93}, and @code{polylib/types.h}).
1667 This structure is devoted to represent a set of constraints. It is
1668 defined as the following:
1673 @{ unsigned NbRows ; /* Number of rows. */
1674 unsigned NbColumns ; /* Number of columns. */
1675 Entier ** p ; /* Array of pointers to the matrix rows. */
1676 Entier * p_Init ; /* Matrix rows contiguously in memory. */
1677 int p_Init_size ; /* For internal use. */
1679 typedef struct pipmatrix PipMatrix;
1683 @noindent The whole matrix is stored in memory row after row at the
1684 @code{p_Init} address. @code{p} is an array of pointers where
1685 @code{p[i]} points to the first element of the @math{i^{th}} row.
1686 @code{NbRows} and @code{NbColumns} are respectively the number of
1687 rows and columns of the matrix.
1688 Each row corresponds to a constraint. The first element of each row is an
1689 equality/inequality tag. The
1690 constraint is an equality @math{p(x) = 0} if the first element is 0, but it is
1698 if the first element is 1.
1699 The next elements are the unknown coefficients, followed by the parameter
1700 coefficients, then the scalar coefficient.
1701 @strong{Please notice that the ordering of unknown and scalar coefficients
1702 is different from the input file of the PIP software} (this is due
1703 to historical reasons).
1704 For instance, in the problem we used as example
1705 (@pxref{Example (part 1)}) the domain is defined by
1706 the following three constraints:
1710 \hbox{$ \cases{ -i + m &$= 0$\cr
1712 j + i - k &$\geq 0$}$}
1726 @noindent would be represented by the following rows:
1730 # eq/in i j k m n cst
1737 @noindent To be able to provide different precision version (PIP/PipLib
1738 supports 32 bits, 64 bits and arbitrary precision through the GMP library),
1739 the @code{Entier} type depends on the configuration options (it may be
1740 @code{long int} for 32 bits version, @code{long long int} for 64 bits version,
1741 and @code{mpz_t} for multiple precision version).
1742 The @code{p_Init_size} field is needed to free
1743 the memory allocated by @code{mpz_init} in the multiple precision release.
1744 Set this field to 0 if you are @emph{not} using multiple precision.
1745 Set this field to the size of the @code{p_Init} array if you
1746 initialized it yourself and if you are using the multiple precision version.
1748 The context is defined by one constraint:
1757 @math{-k + m + n >= 0}
1761 @noindent the row corresponding to this constraint would be:
1770 @noindent @code{p_Init_size} is needed by the to free the memory
1771 allocated by @code{mpz_init} in the multiple precision release.
1775 @subsection PipVector
1780 @{ int nb_elements ; /* Number of elements in the vector */
1781 Entier * the_vector ; /* Vector of numerators */
1782 Entier * the_deno ; /* Vector of denominators */
1784 typedef struct pipvector PipVector ;
1788 @noindent The @code{PipVector} structure represents a @code{Vector}
1789 as described in the ouput grammar (@pxref{Reading the Output File}).
1790 @code{nb_elements} is the number of vector elements, @code{the_vector} is
1791 an array which contains the numerators of these elements and @code{the_deno}
1792 is an array which contains their denominators: the @math{i^{th}} element is
1793 @code{the_vector[i]/the_deno[i]}.
1797 @subsection PipNewparm
1802 @{ int rank ; /* Index of the newparm */
1803 PipVector * vector ; /* Vector of parameter coefficients */
1804 Entier deno ; /* Denominator for the whole vector */
1805 struct pipnewparm * next ; /* Pointer to next newparm */
1807 typedef struct pipnewparm PipNewparm ;
1811 @noindent The @code{PipNewparm} structure represents a @code{NULL}
1812 terminated linked list of @code{Newparm} as described in the ouput grammar
1813 (@pxref{Reading the Output File}).
1814 For each @code{Newparm}, the rank is @code{rank},
1815 the vector of coefficients is pointed by @code{vector}, and the denominator
1816 is @code{deno}. @code{next} is a pointer to the next @code{PipNewparm}
1826 @{ PipVector * vector ; /* Pointer to a vector */
1827 struct piplist * next ; /* Pointer to next vector */
1829 typedef struct piplist PipList ;
1833 @noindent The @code{PipList} structure represents a @code{NULL} terminated
1834 linked list of @code{Vector} as described in the ouput grammar
1835 (@pxref{Reading the Output File}).
1836 @code{vector} is a pointer to the vector of the current node and
1837 @code{next} is a pointer to the next @code{PipList} structure.
1841 @subsection PipQuast
1846 @{ PipNewparm * newparm ; /* List of newparms */
1847 PipList * list ; /* The solution (if no condition) */
1848 PipVector * condition ; /* The condition */
1849 struct pipquast * next_then ; /* Quast if condition is true */
1850 struct pipquast * next_else ; /* Quast if condition is false */
1851 struct pipquast * father ; /* Pointer to father quast */
1853 typedef struct pipquast PipQuast ;
1857 @noindent The @code{PipQuast} represents a @code{Quast} as described in the
1858 ouput grammar (@pxref{Reading the Output File}). Each @code{Quast}
1859 has a tree structure and begins with a list of @code{Newparm}
1860 (field @code{newparm}). If the pointer @code{condition} is not @code{NULL}, the
1861 list of @code{Newparm} is followed by a conditional structure : if the condition
1862 pointed by @code{condition} is true, then the solution continues in the
1863 @code{Quast} pointed by @code{next_then}, in the @code{Quast} pointed by
1864 @code{next_else} otherwise. If the pointer @code{condition} is @code{NULL}, the
1865 list of @code{Newparm} is followed by a list of vectors (field @code{list}).
1866 For @code{Quast} manipulation convenience, a pointer to the father in the tree
1867 is provided (field @code{father}), obviously the father of the root is
1872 @subsection PipOptions
1877 @{ int Nq ; /* 1 for integral solution, else 0 */
1878 int Verbose ; /* Verbosity level (from -1 to 3) */
1879 int Simplify ; /* 1 to simplify solution, else 0 */
1880 int Deepest_cut ; /* 1 to use Deepest Cut algo, else 0 */
1881 int Maximize; /* 0 for lexico minimum, 1 for maximum */
1882 int Urs_parms; /* 0 for non-negative parms, else -1 */
1883 int Urs_unknowns; /* 0 for non-negative unknowns, else -1 */
1885 typedef struct pipoptions PipOptions ;
1889 @noindent The @code{PipOptions} structure contains all the possible options
1890 ruling the PIP behaviour. Every @code{PipOptions} structure should be created
1891 and filled with the default values by the @code{pip_options_init}
1892 function (@pxref{pip_options_init}) to ensure forward compatibility.
1893 Only after this, the user should modify
1894 the structure entries according to his wishes:
1897 @item @code{Nq}: a boolean set to 1 if an integer solution is needed, 0
1899 @item @code{Verbose}: a graduate value for debug informations:
1901 @item -1: absolute silence,
1902 @item 0: relative silence,
1903 @item 1: information on cuts when an integer solution is required,
1904 @item 2: information on pivots and determinants,
1905 @item 3: information on arrays.
1907 Each option include the preceding one.
1908 If @code{Verbose} is not @math{-1}, most of the processing will be
1909 printed in a file. The file name is generated at random
1910 (by @code{mkstemp}) or set with environment variable DEBUG.
1911 @item @code{Simplify}: a boolean set to 1 if some trivial quast simplifications
1912 are needed (recursive elimination of degenerated patterns like
1913 @code{if #[...] () ()}), 0 otherwise,
1914 @item @code{Deepest_cut}: a boolean set to 1 if PIP has to use the deepest cut
1915 algorithm, 0 otherwise,
1916 @item @code{Maximize}: a boolean set to 0 if the lexicographic
1917 minimum is requested, or to 1 for the lexicographic maximum. When trying
1918 to find the lexicographic maximum, the method used is the one
1919 presented in a previous section
1920 (@pxref{Computing Lexicographic Maxima}):
1921 if no bigparm was set, a new (big) parameter is automatically created
1922 by adding a new column (at the last position) to the
1923 constraint system. This optional extra parameter is removed again from
1924 the output. Unbounded solutions have their @code{the_deno} set to zero.
1925 Note that setting this option allows for negative solutions.
1926 This may change in a future release.
1927 @item @code{Urs_parms}: controls signs of parameters:
1929 @item -1: all parameters have unrestricted sign,
1930 @item 0: all parameters are non-negative.
1932 @item @code{Urs_unknowns}: controls signs of unknowns:
1934 @item -1: all unknowns have unrestricted sign,
1935 @item 0: all unknowns are non-negative.
1940 @node PipLib Functions
1941 @section PipLib Functions
1945 * pip_options_init::
1947 * pip_matrix_alloc::
1949 * Printing Functions::
1950 * Memory Deallocation Functions::
1954 @subsection pip_solve
1958 PipQuast * pip_solve
1959 ( PipMatrix * domain, /* Domain where to find a solution */
1960 PipMatrix * context, /* Constraints on parameters */
1961 int Bg, /* Bigparm index (-1 if no bigparm) */
1962 PipOptions * options /* Options */
1967 @noindent The @code{pip_solve} function solves a linear problem provided as
1968 input. The first three parameters describe the problem that the user wants
1969 to solve. The last parameter describe the options that the user has to set.
1970 These parameters are:
1972 @item @code{domain}: a pointer to the equations and inequalities system which
1973 describe the unknown domain in the PolyLib constraints matrix shape,
1974 @item @code{context}: a pointer to the equations and inequalities system
1975 satisfied by the parameter context in the PolyLib constraints matrix
1976 shape (it can be @code{NULL} if there is no context). @strong{Caution:
1977 if there are parameters but no constraints on them, don't set
1978 @code{context} to @code{NULL} but to a matrix with the right column
1979 number (i.e., number of parameters + 2) and 0 rows because the PipLib
1980 uses this information to know the parameter number.}
1981 @item @code{Bg}: the column rank of the bignum (first column rank is 0), or a
1982 negative value if there is no big parameter in the problem to be solved,
1983 if unsure, just set to -1,
1984 @item @code{options}: a pointer to a data structure containing the options
1985 ruling the behaviour of PIP.
1987 This function returns a pointer to a @code{PipQuast} structure containing the
1988 solution, it will be @code{NULL} if the context is @code{void}.
1991 @node pip_options_init
1992 @subsection pip_options_init
1996 PipOptions * pip_options_init(void) ;
2000 @noindent The @code{pip_options_init} function allocates the memory space
2001 for a @code{PipOptions} structure and fills it with the default values:
2003 @item @code{Nq} @math{= 1}: an integer value is required,
2004 @item @code{Verbose} @math{= 0}: no debug informations,
2005 @item @code{Simplify} @math{= 0}: do not try to simplify solutions,
2006 @item @code{Deepest_cut} @math{= 0}: do not use deepest cut algorithm,
2007 @item @code{Maximize} @math{= 0}: compute the lexicographic minimum,
2008 @item @code{Urs_parms} @math{= 0}: all parameters are non-negative,
2009 @item @code{Urs_unknowns} @math{= 0}: all unknowns are non-negative.
2011 We strongly recommend to use this function to create and initialize any
2012 @code{PipOptions} structure. In this way, if some new options appear in
2013 the future, there will be no compatibility issues.
2017 @subsection pip_close
2021 void pip_close(void) ;
2025 @noindent The @code{pip_close} function
2026 frees the memory space that have been allocated
2027 for few global variables PipLib needs. This function has to be called when
2028 PipLib is no more useful in order to prevent slight memory leaks.
2031 @node pip_matrix_alloc
2032 @subsection pip_matrix_alloc
2036 PipMatrix * pip_matrix_alloc
2043 @noindent The @code{pip_matrix_alloc} function allocates the memory space
2044 for a @code{PipMatrix} structure with @code{nb_rows} rows and @code{nb_columns}
2045 columns. It fills the @code{Nb_Rows}, @code{Nb_Columns} and @code{p} fields
2046 and initializes the matrix entries to 0, then it returns a pointer to this
2050 @node pip_matrix_read
2051 @subsection pip_matrix_read
2055 PipMatrix * pip_matrix_read(FILE *) ;
2059 @noindent The @code{pip_matrix_read} function reads a matrix from a file. It
2060 takes as input a pointer to the file it has to read (possibly @code{stdin}), and
2061 returns a pointer to a @code{PipMatrix} structure. The input has the following
2064 @item some optional comment lines which begin with @code{#},
2065 @item the row numbers and column numbers, possibly followed by comments,
2067 @item the matrix rows, each row must be on a single line and is possibly
2068 followed by comments.
2070 For instance, in the example problem (@pxref{Example (part 1)}) the domain
2071 may be defined as follows
2075 # This is the domain
2076 3 7 # 3 lines and 7 columns
2077 1 0 -1 0 1 0 0 # -i + m >= 0
2078 1 -1 0 0 0 1 0 # -j + n >= 0
2079 1 1 1 -1 0 0 0 # j + i - k >= 0
2084 @node Printing Functions
2085 @subsection Printing Functions
2089 void pip_matrix_print(FILE *, PipMatrix *) ;
2090 void pip_vector_print(FILE *, PipVector *) ;
2091 void pip_newparm_print(FILE *, PipNewparm *, int indent) ;
2092 void pip_list_print(FILE *, PipList *, int indent) ;
2093 void pip_quast_print(FILE *, PipQuast *, int indent) ;
2094 void pip_options_print(FILE *, PipOptions *) ;
2098 @noindent There is a printing function for each structure of the PipLib.
2099 They all take as input
2100 a pointer to a file (possibly @code{stdout}) and a pointer to a structure.
2101 Some of them takes as input an
2102 indent step. They print the structure contents to the file without indent if
2103 @code{indent} @math{< 0}, with an indentation step of @code{indent} otherwise.
2106 @node Memory Deallocation Functions
2107 @subsection Memory Deallocation Functions
2111 void pip_matrix_free(PipMatrix *) ;
2112 void pip_vector_free(PipVector *) ;
2113 void pip_newparm_free(PipNewparm *) ;
2114 void pip_list_free(PipList *) ;
2115 void pip_quast_free(PipQuast *) ;
2116 void pip_options_free(PipOptions *) ;
2120 @noindent There is a memory deallocation function for each structure of
2121 the PipLib. They free the allocated memory for the structure.
2124 @node Example of Library Utilization
2125 @section Example of Library Utilization
2126 Here is a simple example showing how one can use the PipLib, assuming that
2127 a basic installation has been done. The following C program reads a domain and
2128 its context on the standard input then prints
2129 the solution on the standard output.
2130 Options are preselected : there is no bignum, we are looking for an integral
2131 solution without simplification and we don't want debug informations.
2132 This example is provided in the @code{example} directory of the
2133 PIP/PipLib distribution.
2139 # include <piplib/piplib64.h>
2142 @{ PipMatrix * domain, * context ;
2143 PipQuast * solution ;
2144 PipOptions * options ;
2146 options = pip_options_init() ;
2147 domain = pip_matrix_read(stdin) ;
2148 context = pip_matrix_read(stdin) ;
2150 solution = pip_solve(domain,context,-1,options) ;
2152 pip_options_free(options) ;
2153 pip_matrix_free(domain) ;
2154 pip_matrix_free(context) ;
2156 pip_quast_print(stdout,solution,0) ;
2163 @noindent The compilation command could be:
2165 gcc example.c -lpiplib64 -o example
2168 @noindent Supposing that the user wants to solve the example problem
2169 (@pxref{Example (part 1)}), he will type:
2181 @noindent And the program will answer:
2195 @c % ****************************** INSTALLING ********************************
2197 @chapter Installing PIP
2202 * Basic Installation::
2203 * Optional Features::
2209 First of all, it would be very kind to refer the following paper in any
2210 publication that result from the use of the PIP software or its library,
2211 @pxref{Fea88} (a bibtex entry is provided behind the title page of this
2212 manual, along with copyright notice, and in the PIP/PipLib home
2213 @code{http://www.PipLib.org}.
2215 This library is free software; you can redistribute it and/or modify it
2216 under the terms of the GNU Lesser General Public License as published by
2217 the Free Software Foundation; either version 2.1 of the License, or (at
2218 your option) any later version.
2219 This program is distributed in the hope that it will be useful,
2220 but WITHOUT ANY WARRANTY; without even the implied warranty of
2221 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2222 GNU General Public License for more details.
2223 @code{http://www.gnu.org/copyleft/gpl.html}
2227 @section Adjusting the Precision
2228 Pip is an all integer version of the dual simplex algorithm. As such,
2229 it has to handle integers whose size may grow exponentially as the
2230 computation proceeds. Integer overflow may occur and have to be checked.
2231 Since the hardware integer overflow exception is usually masked by
2232 the operating system or the compiler, overflow is detected by checking
2233 that a division somewhere in the algorithm, which can be proved to be
2234 exact by mathematical arguments, is indeed exact. If not, an error is
2235 reported and the computation stops.
2237 The size of the numbers to be handled depends strongly on the size of the
2238 constraint matrix and on the size of its coefficients.
2242 * Multiple Precision PIP::
2247 @subsection Bounded PIP
2248 The precision of the integer representation in the Pip code can be
2249 adjusted at compile time by giving options to the @code{configure}
2251 By giving @code{configure} the option @code{--enable-llint-version} you ask
2252 for long long int version only (64 bits). It results in a 64 bits Pip
2253 called @code{pip64}.
2254 By giving @code{configure} the option @code{--enable-int-version} you
2255 ask for int version only. It results in a 32 bits called
2256 @code{pip32} and a faster running time.
2259 @node Multiple Precision PIP
2260 @subsection Multiple Precision PIP
2261 Multiple Precision Pip is built on top of the GMP library
2262 (this library is freely available at @code{http://www.swox.com/gmp}).
2263 Each integer in the program is represented as a list of 32 bits numbers.
2264 All computations are done exactly, and the size of the numbers increases
2265 as needed to preserve exactness. It follows that no overflow is possible.
2266 However, when the size of numbers increases, computations get slower and
2267 slower, and memory overflow may occur in extreme cases. In well behaved
2268 problems, 32 bits are enough for the initial data, the size of intermediate
2269 results first increases up to a maximum, then decreases, and 32 bits
2270 are again enough for the results. Hence, it has been possible to keep
2271 the input format and output format of Multiple Precision Pip completely
2272 compatible with the formats of the bounded precision versions.
2274 To install Multiple Precision Pip, first install GMP according to the
2275 directions found at the above URL. Usually, the library is installed
2276 in @code{/usr/local/lib}, and the header files are in @code{/usr/local/include}.
2277 If this is not the case, you must adjust the Pip makefile by giving
2278 to the @code{configure} shell script the option @code{--with-gmp=PATH}, where
2279 @code{PATH} is the GMP library installation path. If GMP headers and
2280 libraries are not in the same installation path, you can be more precise
2281 by using @code{--with-gmp-include=PATH} and @code{--with-gmp-library=PATH}
2282 for GMP headers and libraries respectively.
2285 By giving @code{configure} the option @code{--enable-mp-version} you ask
2286 for a GMP version only. It results in a multiple precision Pip
2287 called @code{pipMP}.
2289 @node Basic Installation
2290 @section PIP Basic Installation
2292 Once downloaded and unpacked
2293 (e.g. using the @samp{tar -zxvf piplib-@value{VERSION}.tar.gz} command),
2294 you can compile PIP by typing the following commands on the PIP's root
2298 @item @code{./configure}
2300 @item And as root: @code{make install}
2303 Depending on the location of the GMP (and whether or not you want
2304 to use it), you may need to set the
2305 option @code{--with-gmp} of the configure script
2306 (e.g. @samp{./configure --with-gmp=/usr/local} with a default GMP
2309 The program binaries and object files can be removed from the
2310 source code directory by typing @code{make clean}. To also remove the
2311 files that the @code{configure} script created (so you can compile the
2312 package for a different kind of computer) type @code{make distclean}.
2314 Both the PIP software and PipLib library have been successfully compiled
2315 on the following systems:
2317 @item PC's under Linux, with the @code{gcc} compiler,
2318 @item PC's under Windows (Cygwin), with the @code{gcc} compiler,
2319 @item Mac's under MacOS X, with the @code{gcc} compiler,
2320 @item Sparc and UltraSparc Stations, with the @code{gcc} compiler.
2323 @node Optional Features
2324 @section Optional Features
2325 The @code{configure} shell script attempts to guess correct values for
2326 various system-dependent variables and user options used during compilation.
2327 It uses those values to create the @code{Makefile}. Various user options
2328 are provided by the PIP's configure script. They are summarized in the
2329 following list and may be printed by typing @code{./configure --help} in the
2330 PIP top-level directory.
2333 @item By default, the installation directory is @code{/usr/local}:
2334 @code{make install} will install the package's files in
2335 @code{/usr/local/bin}, @code{/usr/local/lib} and @code{/usr/local/include}.
2336 The user can specify an installation prefix other than @code{/usr/local} by
2337 giving @code{configure} the option @code{--prefix=PATH}.
2339 @item By default, both PIP software and PipLib library are compiled and installed.
2340 By giving @code{configure} the option @code{--without-pip} the user
2341 disable the compilation and installation of the PIP software.
2342 @c By giving @code{configure} the option
2343 @c @code{--without-lib} the user disable the compilation and installation of the
2346 @item By default, PIP is built in both 32 and 64 bits versions, and in
2347 multiple precision version if GMP is found by @code{configure}.
2348 To build only one version, the user may give to @code{configure} the options
2349 @code{--enable-int-version} or @code{--enable-llint-version} or
2350 @code{--enable-mp-version} to build only 32, 64 or multiple precision
2351 version respectively.
2353 @item By default, @code{configure} will look for the GMP library
2354 (necessary to build the multiple precision version) in standard
2355 locations. If necessary, the user can specify the GMP path by giving
2356 @code{configure} the option @code{--with-gmp=PATH}.
2359 @node Uninstallation
2360 @section Uninstallation
2361 The user can easily remove the PIP software and PipLib library from his system
2362 by typing (as root if necessary) from the PIP/PipLib top-level directory
2363 @code{make uninstall}.
2365 @c % **************************** DOCUMENTATION ******************************
2367 @chapter Documentation
2368 The Texinfo sources of the present document is provided in the @code{doc}
2369 directory. You can build it in either DVI format (by typing
2370 @code{texi2dvi piplib.texi}) or PDF format
2371 (by typing @code{texi2pdf piplib.texi}) or HTML format
2372 (by typing @code{makeinfo --html piplib.texi}, using @code{--no-split}
2373 option to generate a single HTML file) or info format
2374 (by typing @code{makeinfo piplib.texi}).
2376 @c % ****************************** REFERENCES ********************************
2382 @anchor{CPLEX}[CPLEX] @emph{http://www.ilog.com/products/cplex/}
2385 @anchor{Dant51}[Dant51] G.B. Dantzig. Maximization of a linear function of
2386 variables subject to linear inequalities. In Koopmans, T.C. (ed.),
2387 Activity analysis of production and allocation,
2388 John Wiley & Sons, New York, 339-347, 1951.
2391 @anchor{Fea88}[Fea88] Paul Feautrier. Parametric Integer Programming.
2392 Rairo Recherche Op@'erationnelle, 22(3):243--268, 1988.
2395 @anchor{Feau89}[Fea89] Paul Feautrier.
2396 Semantical analysis and mathematical programming; application to
2397 parallelization and vectorization.
2398 In M. Cosnard, Y. Robert, P. Quinton, and M. Raynal, editors,
2399 Workshop on Parallel and Distributed Algorithms, pages 309--320.
2400 Bonas, North Holland, 1989.
2403 @anchor{Fea92}[Fea92] P. Feautrier Some efficient solutions to the affine
2404 scheduling problem, part II: multidimensional time.
2405 International Journal of Parallel Programming, 21(6):389--420, December 1992.
2408 @anchor{Gom58}[Gom58] R. Gomory. Outline of an algorithm for integer
2409 solutions to linar programs. Bulletin of the American Mathematical
2410 Society 64:275-278, 1958.
2413 @anchor{Lem54}[Lem54] Lemke. The dual method for solving the linear
2414 programming problem. Naval Research Logistic Quarterly 22:978-981, 1954.
2417 @anchor{lp_solve}[lp_solve] @emph{http://groups.yahoo.com/group/lp_solve/}
2420 @anchor{Wil93}[Wil93] Doran K. Wilde.
2421 A library for doing polyhedral operations.
2422 Technical Report 785, IRISA, Rennes, France, 1993.
2429 @c % /*************************************************************************
2430 @c % * PART VI: END OF THE DOCUMENT *
2431 @c % *************************************************************************/
2432 @c @unnumbered Index