as a PDF
Contents
1. Context i Vector Vector Integer Nn Integer Np Integer N1 Integer Nm Integer Bg Integer Nq 0 1 This syntax was chosen so as to ease the generation of problems by a Lisp pro gram In particular each Problem is a balanced list as far as both parentheses and brackets are concerned Comments are arbitrary lists These comments are written verbatim to the output file and are useful to keep track of problems and solutions Note that several Problems can be given to PIP in the same file The problems may be separated by any text that does not contain a parenthesis By using Unix FIFO s as input and output files it is easy to convert the present implementation of PIP into a linear programming server Nn is the number of unknowns in the program which was denoted by n in the first section Np is the number of symbolic parameters p N1 is the number of inequalities defining the domain of the unknowns J Nm is the number of inequalities satisfied by the parameters m Bg is the index of a Big parameter whose value is assumed to be infinitely large That is if the big parameter appears with a positive coefficient in a form then we can immediately deduce that gt 0 If Bg is set to a nonpositive value then there is no big parameter in the problem to be solved Be aware that Bg is the column rank of the corresponding parameter in the Tableau and that the first va2. e C code files in the source directory 4 INSTALLING PIP 24 e a lot of data files dat and of result files 11 in the test directory you should then run at least some of the dat files and compare the results to the corresponding 11 file e asimple example showing how to use the PipLib in the example directory e a postscript version of the present document pip ps in the doc directory e files needed for compilation and installation in the PIP root directory 4 4 1 basic installation The configure shell script attempts to guess correct values for various system dependent variables used during compilation It uses those values to create a Makefile The file configure in is used to create configure by a program called autoconf You only need configure in if you want to change it or regen erate configure using a newer version of autoconf The simplest way to compile this package is e cd to the directory containing the package s source code and type configure to configure the package for your system while running configure prints some messages telling which features it is checking for e type make to compile the package and install the program and the library e you can remove the program binaries and object files from the source code directory by typing make clean To also remove the files that configure created so you can compile the package for a different kind of computer type make distclean PIP and the PipLi
3. n so let s look for the lower bound on j in the rewritten nest This lower bound on j can be found by solving the following problem Do k lt j i gt ji lt mj lt n k lt it jf This problem is to be solved in the context k lt m n The input file may thus look like this Lower bound on j after loop inversion unknowns j i parameters k m n 23 3 14 1 1 0 100 1 0 1 00001 1 10 10 0 1 1 1 0 The first sequence of integers should be read as This problem has 2 unknowns i and j and 3 parameters k m and n The domain is defined by 3 inequalities the context by 1 inequality There is no 1 big parameter and it is true 1 that we are looking for an integer solution 2 USING THE PIP SOFTWARE 5 2 2 Calling PIP PIP is called by the following command pip sl v dl z input output PIP prints some information on the screen after having solved a problem The s silent mode switches this feature off On the contrary the verbose v option tells PIP to copy in a file all the input data and all the intermediary results The name of this file is given either by the variable DEBUG in the environment or is built by mkstemp The number of consecutive vee s controls the degree of verbosity of Pip A word of caution debug files may become very large very fast When Pip is asked for an integral solution it constructs new constraints the so called cuts which eliminate fractional solutions
4. 0 Inspection reveals that all leaves are With the z option the solution is much simpler G j 1 n 1 O 2 4 The Power of PIP In the following sections we explain how PIP can be used to solve extended classes of problems e Problems where equalities occur e Problems where a lexicographical maximum has to be found e Cases when linear cost functions are to be optimized e Problems where unknowns and or parameters may be negative 2 4 1 Handling Equalities When the input problem contains r affine equalities f 0 1 lt i lt r one may just write r inequalities f gt 0 and r inequalties f lt 0 thus satisfying PIP s input syntax However one may notice that only r 1 inequalities are needed f 0 1 lt i lt r and the following inequality SAS i l 2 4 2 The bigparm trick In some cases it is useful to suppose that one parameter in a PIP problem grows very large Some examples will be given in the following sections Let B be the name of this parameter Suppose that in the solution one of the predicates is aB b gt 0 where b may depend on all other parameters For B large enough if a gt 0 then the predicate is true and if a lt 0 then the predicate is false One can find the limit shape of the solution by removing such tests and replacing them by their true of false branch as appropriate This can be done a posteriori on the results of PIP or PIP can do it on the fly while sol
5. and keep all integer solutions The selection of cuts is somewhat arbitrary When the d option is given Pip uses this degree of freedom to select the deepest cut according to an algorithm by Gondran Untractable problems may become tractable when using this option and conversely Use with caution If the z option is given then the solution is somewhat simplified see below input and output are the names of the input data and output results files respectively If no output input file is given then the results are printed to the standard output input 2 2 1 Messages e Version X x Currently D 1 e cross lt n gt alloc lt m gt This message is output after solving each problem The value of lt n gt gives an idea of the complexity of the problem Errors related to the input e Syntax error unbalanced parentheses in the input e Your computer doesn t have enough memory self explanatory Errors related to the solution e Integer Overflow A number has been generated that is too large to be accommodated in a 32 bit integer Check the input and or switch to Zbigniew Chamski s infinite precision PIP e The solution is too complex the solution quast has grown beyond the memory allocated to it Check the input and or change the value of con stant SOL_SIZE in file type h then rebuild PIP 2 USING THE PIP SOFTWARE 6 e Memory overflow self explanatory e lt file gt unaccessible one of the input o
6. file it has to read possibly stdin and returns a pointer to a PipMatrix structure The input has the following syntax e some optional comment lines which begin with e the row numbers and column numbers possibly followed by comments on a single line 3 USING THE PIP LIBRARY 20 e the matrix rows each row must be on a single line and is possibly followed by comments For instance in the problem of section 2 1 1 the domain is defined as follows This is the domain 7 3 lines and 7 columns 0 1 0 1 0 O i m gt 0 1 0 00 1 O0 j n gt 0 1 1 1 0 0 O j i k gt 0 3 2 6 Printing Functions void pip_matrix_print FILE PipMatrix void pip_vector_print FILE PipVector void pip_newparm_print FILE PipNewparm int indent void pip_list_print FILE PipList int indent void pip_quast_print FILE PipQuast int indent void pip_options_print FILE PipOptions There is a printing function for each structure of the PipLib They all take as input a pointer to a file possibly stdout and a pointer to a structure Some of them takes as input an indent step They print the structure contents to the file without indent if indent lt 0 with an indentation step of indent otherwise 3 2 7 Memory Deallocation Functions void pip_matrix_free PipMatrix void pip_vector_free PipVector void pip_newparm_free PipNewparm void pip_list_free PipList void pip_quast_free PipQuast voi
7. Solving Systems of Affine In Equalities PIP s User s Guide Paul Feautrier Additions by Jean Francois Collard and C dric Bastoul Fourth Version rev 1 5 November 8 2005 Abstract This document is the User s Manual of PIP a software which solves Parametric Integer Programming problems That is PIP finds the lexi cographic minimum of the set of integer points which lie inside a convex polyhedron when that polyhedron depends linearly on one or more integral parameters 1 Introduction The semantic analysis of programs accessing arrays often boils down to finding integer solutions to parametric linear programming problems This is due to two main phenomena e Array subscripts are very often linear functions of surrounding loop coun ters e The program s execution order enforces an order on possible solutions Let us consider the following example for i 0 to m do for j 0 to n do I a 2 itj i j After completion of execution for which values of k is A k defined and which instances of the assignment wrote into this array element We can easily check that answering this question is equivalent to finding the solutions of the following system where i j and k are the unknowns 0 lt i lt m 1 0 lt j lt n 2 2i j k 3 2 USING THE PIP SOFTWARE 2 Moreover if we want to know which instance gave its final value to A k that is if we are looking for the last instance writing into A k then we
8. b have been successfully compiled on the following systems e PC s under Linux with the gcc compiler e PC s under Windows Cygwin with the gcc compiler but because of some Cygwin limitations only 32 bits version will work and user may experience some problems when linking with PipLib e SparcStations with the gcc compiler 4 4 2 optionnal features e By default make will install the package s files in usr local bin usr local lib etc You can specify an installation prefix other than usr local by giving configure the option prefix PATH REFERENCES 25 e By default both PIP and the PipLib are compiled and installed By giv ing configure the option without pip you disable the compilation and installation of PIP By giving configure the option without lib you disable the compilation and installation of the PipLib e By default both int 32 bits and long long int 64 bits versions are built Multiple precision is built too if the GMP library is found By giving configure the option enable int you ask for int version only By giving configure the option enable llint you ask for long long int version only By giving configure the option enable gmp you ask for GMP version only e By default PIP looks for the GMP library in the standard path usr or usr local If the multiple precision Pip construction is needed and if the GMP library was installed elsewhere you must must give to the configure shell scri
9. d pip_options_free PipOptions There is a memory deallocation function for each structure of the PipLib They free the allocated memory for the structure 3 3 Example Here is a simple example showing how one can use the PipLib assuming that a basic installation was done The following C program reads a domain and its context on the standard input then prints the solution on the standard output Options are preselected there is no bignum we are looking for an integral solution without simplification and we don t want debug informations 3 USING THE PIP LIBRARY 21 example c include lt stdio h gt include lt piplib piplib64 h gt int main PipMatrix domain context PipQuast solution PipOptions options domain pip_matrix_read stdin context pip_matrix_read stdin options pip_options_init solution pip_solve domain context 1 options pip_options_free options pip_matrix_free domain pip_matrix_free context pip_quast_print stdout solution 0 pip_close The compilation command could be gcc example c lpiplib64 o example Supposing that the user wants to solve the problem of section 2 1 1 he will type Pree RF WwW 7 O 1 O 1 0 0 1 0 00 1 0 1 1 1 0 0 0 5 1 1 1 0 And the program will print if 1 10 0 list 0 0 0 0 100 0 list 1 1 0 0 4 INSTALLING PIP 22 01 0 0 4 Installi
10. d warranty of MERCHANTABIL ITY or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details http www gnu org copyleft gpl html 4 3 Adjusting the Precision Pip is an all integer version of the dual simplex algorithm As such it has to handle integers whose size may grow exponentially as the computation proceeds Integer overflow may occur and have to be checked Since the hardware integer overflow exception is usually masked by the operating system or the compiler overflow is detected by checking that a division somewhere in the algorithm which can be proved to be exact by mathematical arguments is indeed exact If not an error is reported and the computation stops 4 INSTALLING PIP 23 The size of the numbers to be handled depends strongly on the size of the constraint matrix and on the size of its coefficients 4 3 1 Bounded Pip The precision of the integer representation in the Pip code can be adjusted at com pile time by giving options to the configure shell script By giving configure the option enable 1llint you ask for long long int version only 64 bits It re sults in a 64 bits Pip called pip64 By giving configure the option enable int you ask for int version only It results in a 32 bits called pip32 and a faster run ning time 4 3 2 Multiple Precision Pip Multiple Precision Pip is built on top of the GMP library this library is freely available at http www swox com gmp Each in
11. e NULL if the context is void 3 2 2 pip_options_init function PipOptions pip_options_init void The pip_options_init function allocates the memory space for a PipOptions structure and fills it with the default values 3 USING THE PIP LIBRARY 19 e Nq 1 an integer value is required e Verbose 0 no debug informations e Simplify 0 do not try to simplify solutions e Deepest_cut 0 do not use deepest cut algorithm e Max 0 compute the lexicographic minimum We strongly recommand to use this function to create and initialize any PipOptions structure In this way if some new options appear in the future there will be no compatibility problems 3 2 3 pip_close function void pip_close void The pip_close frees the memory space that have been allocated for few global variables PipLib needs This function has to be called when PipLib is no more useful in order to prevent slight memory leaks 3 2 4 pip_matrix_alloc function PipMatrix pip_matrix_alloc unsigned nb_rows unsigned nb_columns Ks The pip matrix_alloc function allocates the memory space for a PipMatrix structure with nb_rows rows and nb columns columns It fills the Nb_Rows Nb_Columns and p fields and initializes the matrix entries to 0 then it returns a pointer to this structure 3 2 5 pip_matrix_read function PipMatrix pip_matrix_read FILE The pip_matrix_read function read a matrix from a file It takes as input a pointer to the
12. e Quast pointed by next_else otherwise If the pointer condition is NULL the list of Newparm is followed by a list of vectors field list For Quast manipulation convenience a pointer to the father in the tree is provided field father obviously the father of the root is NULL 3 1 6 PipOptions structure struct pipoptions int Nq int Verbose int Simplify int Deepest_cut int Max 4 typedef struct pipoptions PipOptions The PipOptions structure contains all the possible options ruling the PIP be haviour and having to be set by the user 1 Nq a boolean set to 1 if an integer solution is needed 0 otherwise 2 Verbose a graduate value for debug informations e 1 absolute silence e 0 relative silence e 1 information on cuts when an integer solution is required e 2 information on pivots and determinants 3 information on arrays Each option include the preceding one If Verbose is not 1 most of the processing will be printed in a file The file name is generated at random by mkstemp or set with environment variable DEBUG 3 Simplify a boolean set to 1 if some trivial quast simplifications are needed recursive elimination of degenerated patterns like if O 0 0 otherwise 4 Deepest_cut a boolean set to 1 if PIP has to use the deepest cut algorithm 0 otherwise 3 USING THE PIP LIBRARY 18 5 Max a boolean set to 0 if the lexicographic minimum is asked or to 1 for the lexicograp
13. e maximum of x y is equivalent to finding the minimum of x y T provided B is large enough The solution of the above problem is a maximization problem 1 if 1 6 Gi 1 3 list 0 0 0 0 if 5 27 2 USING THE PIP SOFTWARE 11 newparm 1 div 1 1 2 list 1 1 1 0 0 0 list 1 4 1 5 list 1 4 1 5 Suppose we tell PIP that B is a large parameter The input file is now a maximization problem 214031 1 0 0 1 0 1 0 1 1 3 12 2 2 1 3 1 O and the solution is much simpler a maximization problem 1 list 1 4 1 5 The reader may care to check that this result is equivalent to the previous one as soon as B gt 5 The position of the minimum is 2 B 4 y B 5 from which we deduce x 4 y 5 As expected B has disappeared from the solution If this does not happen we observe first that B must have a positive coefficient in the result if not one of the inequalities x y gt 0 would be violated for B large enough This means that the original polyhedron is not bounded since whatever B it contains a point whose coordinates are O B and hence has no maximum 2 4 4 Optimizing Linear Cost Functions The problem here is to compute the minimum of a linear function cx in a poly hedron P where c is a vector with integer coefficients Let us introduce a new unknown y Solve the linear programmi
14. have to look for the maximal value of vector i j according to lexicographic order We thus consider the following polyhedron F k m n Flk m n lt i j gt 0 lt i lt mO0 lt j lt n 2i j k 4 What is the lexicographical maximum of the integer valued vectors included in F k m n The aim of PIP is to solve such problems The reader is refered to 1 for a mathematical description of the method 1 1 General formulation Let F be a polyhedron F Z 7 Z gt 0 AZ BZ Z gt 0 5 In this formula 7 is a vector with n entries the vector of all unknowns 7 7 gt 0 is the vector built from parameters and has p entries Polyhedron F Z is a subset of R and is defined by n l inequalities n inequalities expressing T gt 0 and the inequalities correponding to rows of matrix A of size l x n matrix B of size x p and constant vector C of size l Size parameters can themselves be constrained by a set of affine inequalities M7 h gt 0 which is called the context of the problem M is an m x p matrix and h a vector of dimension m All data of a PIP problem A B M h are assumed to be integer valued 2 Using the PIP Software 2 1 Writing the Input File The input text file follows the following context free grammar Grammar 1 File Problem Problem Comments Nn Np N1 Nm Bg Nq Tableau Context Comments List List Atom List 2 USING THE PIP SOFTWARE 3 Tableau Vector
15. hic maximum When trying to find the lexicographic maximum the used method is the one presented in section 2 4 3 if no bigparm was set a new big parameter is automatically created by adding a new ending column to the constraint system don t forget this when processing the output Every PipOptions structure should be created and filled with the default values by the pip_options_init function see section 3 2 2 3 2 PipLib functions description 3 2 1 pip_solve function PipQuast pip_solve PipMatrix domain PipMatrix context int Bg PipOptions options D3 The pip_solve function solves a linear problem provided as input The first three parameters describe the problem that the user wants to solve The last parameter describe the options that the user has to set These parameters are 1 domain a pointer to the equations and inequations system which describes the unknown domain in the PolyLib constraints matrix shape 2 context a pointer to the equations and inequations system satisfied by the parameters context in the PolyLib constraints matrix shape it can be NULL if there is no context 3 Bg the column rank of the bignum first column rank is 0 or a negative value if there is no big parameter in the problem to be solved 4 options a pointer to a data structure containing the options ruling the behaviour of PIP This function returns a pointer to a PipQuast structure containing the solution it will b
16. ies Ciy d gt 0 T is equal to fi when y is such that the corresponding inequalities are satisfied For each 7 solve the problem S min fi y by Cy di gt 0 in integers The final result is the minimum of all S Obviously the method can accomodate parameters in the constraints The S will be functions of these parameters and the minimum must be computed symbolically 3 Using the PIP Library The PIP Library PipLib for short was implemented to allow the user to call PIP directly from his programs without file accesses or system calls The user only needs to link his programs with C libraries The PipLib mainly provides one function which takes as input the problem description and some options and returns a Quast see grammar 2 in section 2 3 corresponding to the solution Some other functions are provided for convenience reasons they are described in section 3 2 Most of them require some specific structures to represent the problem or the solution these structures are described in section 3 1 3 1 PipLib data structures description 3 1 1 PipMatrix structure struct pipmatrix unsigned NbRows NbColumns 3 USING THE PIP LIBRARY 15 Entier p Entier p_Init int p_Init_size typedef struct pipmatrix PipMatrix The PipMatrix structure is devoted to represent a constraints matrix in the PolyLib shape 3 The whole matrix is arranged row after row at the p Init adress p is an array of pointers in
17. ing MIN i 2 j under the following constraints 1This example was proposed and solved by Pierre Boulet 2 USING THE PIP SOFTWARE 13 Unknowns may be negative Order f i j constant G P n 335041 101120 2 4 4 1 120 200 0 1 10200 0 1 1 10 0 2 2 0 1 1 10 0 2 2 C The result is Solving MIN i 2 j under the following constraints Unknowns may be negative Order f i j constant G P n 1 if 0 1 1 5 list 1 3 3 15 1 1 1 5 1 1 1 5 O which should be read as Fij if P n 5 gt 0 then G 3P 3n 15 G P n 5 G P 4 n 5 else L That is in the original coordinate system f i j if n gt 5 then 3n 15 n 5 n 5 else L I e the minimum value for function f is 3n 15 and this value is reached at point n 5 n 5 This minimum exists only if n gt 5 otherwise the feasible set is empty 3 USING THE PIP LIBRARY 14 2 4 6 Mixed Programming A mixed program is a program in which some variables are constrained to be integers while others may take rational values Suppose for instance that we have to solve S minaz by Ax By c gt 0 where y is the vector of the integer variables First solve T minaz Ax By c gt 0 in rational with y as parameters The result is a quast To each leaf i is associated a linear function f y and a set of inequalit
18. lid value for it is Nn 1 Nq is an integer but should be interpreted as a boolean value a la C that is it denotes true if its value is nonzero If Nq is true then an integer valued solution is looked for Otherwise PIP finds the lexicographic minimum rational solution to the problem Tableau stores the set of inequalities defining the domain of unknowns Each Vector represents one inequality The entries in Vector are in this order 2 USING THE PIP SOFTWARE 4 the coefficients of the unknowns L e a row of matrix A the additive constant I e an entry of vector the coefficients of the parameters I e a row of matrix B This notation heavily depends on the positions given to unknowns and pa rameters it is the responsability of the user to enforce a coherent ordering of coefficients and to set a coefficient to zero when the corresponding un known parameter does not appear There are l such Vectors in Tableau and each vector exactly has n 1 p entries e In a similar way Context is a list of Vectors Each Vector represents a row of Matrix M followed by the corresponding entry in vector h Context thus includes m Vectors of p 1 entries 2 1 1 Example This example is taken from 2 We consider the loop nest below for i 0 to m do for j 0 to n do II for k 0 to i j do and we wish to rewrite this nest in the order k j i The bounds on k can easily be guessed 0 lt k lt m
19. ng PIP 4 1 Implementation Notes The main problem with any integer programming software is that since one must distinguish between integer and rationals all computations are to be done exactly Rationals must be represented as quotients with an integer numerator and an integer denominator In the preceding version there was only one denominator for the whole tableau The consequence was that simplifications where most unlikely and that the integers in the tableau were growing until overflows occured In the present version there is one denominator per row of the tableau Reduc tion to lower terms occurs frequently and the growth of numbers in the problem tableau is limited As a consequence much larger problems can be solved This has had the unfortunate consequence that several bugs which were beyond the domain of the old version have now surfaced These bugs have been corrected As far as the author can tell these bugs mainly gave correct results which were not in simplest form the quast had extraneous leaves In some cases the result was wrong but the error was self evident for instance there were denominators in integer results 4 2 License This program is free software you can redistribute it and or modify it under the terms of the GNU General Public License version 2 as published by the Free Software Foundation This program is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY without even the implie
20. ng problem obtained by adding the con straint y gt cx to the defining constraints of P y should be the first unknown in the lexicographic ordering Let Ys x be the solution Suppose that the minimum of cx in P is obtained at m and set Ym CLm Since x is in P and Ys gt cag it is clear that ys gt Ym Conversely Ym m satisfies the constraints of the problem of which ys 2m is the lexicographic minimum Hence ys s K Ym m and since y is the first unknown Ys lt Ym Hence Ym ys There is no guarantee however that s m 2 USING THE PIP SOFTWARE 12 2 4 5 Negative Unknowns and Parameters Suppose we want to find the minimum of f 7 j i 2j over the square domain represented in Figure 11 n 5 n 5 n 5 Figure 1 Problem domain As above we introduce a new unknown f and the inequality f i 27 gt 0 Since we want to optimize f f will appear as the first unknown The trick for solving the problem in Z is to introduce the following parameters e G gt mazx 0 i j f e P maz 0 n This choice insure that the new variables and parameters fi G f Sea jo Gtj n P n are all positive This property stays true if G grows Hence G is again a big parameter However P must be considered as an ordinary parameter After replacement of i 7 n f by the new variables 2 j n f we get a system which corresponds to the following input 4 Solv
21. nt of the corresponding parameter the parameter of the same rank The last entry is the additive constant The definition of a new parameter begins with the key word newparm then a rank number a vector of coefficients and a denominator The new parame ter is equal to the integer division of the vector by the denominator The new parameter can only appear in the Quast following its definition Introducing a new parameter adds one entry in the list of parameters so the length of vectors in the solution is not constant However this length is always equal to 1 plus the number of original parameters plus the number of new parameters currently defined The solution is a multi level conditional expression a tree of nested condition als A predicate expression p should be understood as the boolean expression p gt 0 Leaves of the conditional tree are either nil meaning that the input problem has no solution or a Form A Form is a list of vectors each vector giving the value of the corresponding unknown 2 3 1 Example The output of PIP is not intended for human consumption No attempt has been made to implement a pretty printer In the interest of readability some of the result files in this paper have been beautified by hand The reader should not be surprised if he gets results with different layouts when running the examples Here is the output solution file for the example above 2 1 1 Lower bound on j after loop inversion
22. or i the_deno i 3 1 3 PipNewparm structure struct pipnewparm int rank PipVector vector Entier deno struct pipnewparm next F3 typedef struct pipnewparm PipNewparm The PipNewparm structure represents a NULL terminated linked list of Newparm as described in grammar 2 in section 2 3 For each Newparm the rank is rank the vector of coefficients is pointed by vector and the denominator is deno next is a pointer to the next PipNewparm structure 3 1 4 PipList structure struct piplist PipVector vector struct piplist next Ps typedef struct piplist PipList The PipList structure represents a NULL terminated linked list of Vector as described in grammar 2 in section 2 3 vector is a pointer to the vector of the current node and next is a pointer to the next PipList structure 3 1 5 PipQuast structure struct pipquast PipNewparm newparm PipList list PipVector condition struct pipquast next_then struct pipquast next_else struct pipquast father F3 typedef struct pipquast PipQuast 3 USING THE PIP LIBRARY 17 The PipQuast represents a Quast as described in grammar 2 in section 2 3 Each Quast has a tree structure and begins with a list of Newparm field newparm If the pointer condition is not NULL the list of Newparm is followed by a conditional structure if the condition pointed by condition is true then the solution continues in the Quast pointed by next_then in th
23. pt the option with gmp PATH where PATH is the GMP library installation path Another possibility is to give the GMP include and or library path separately by using with gmp include PATH and with gmp library PATH 4 4 3 uninstallation You can easily remove PIP and the PipLib from your system by typing make uninstall Report all bugs problems inaccuracies in the documentation to Paul Feautrier ens lyon fr Cedric Bastoul prism uvsq fr Praise is also appreciated Let the power of parametric integer programming be with you References 1 Paul Feautrier Parametric integer programming RAIRO Recherche Op rationnelle 22 243 268 September 1988 2 Paul Feautrier Semantical analysis and mathematical programming ap plication to parallelization and vectorization In M Cosnard Y Robert P Quinton and M Raynal editors Workshop on Parallel and Distributed Algorithms Bonas pages 309 320 North Holland 1989 3 Doran K Wilde A library for doing polyhedral operations Technical Report 785 IRISA Rennes France 1993
24. teger in the program is repre sented as a list of 32 bits numbers All computations are done exactly and the size of the numbers increases as needed to preserve exactness It follows that no overflow is possible However when the size of numbers increases computations get slower and slower and memory overflow may occur in extreme cases In well behaved problems 32 bits are enough for the initial data the size of intermediate results first increases up to a maximum then decreses and 32 bits are again enough for the results Hence it has been possible to keep the input format and output format of Multiple Precision Pip completely compatible with the formats of the bounded precision versions To install Multiple Precision Pip first install Gmp according to the directions found at the above URL Usually the library is installed in usr local 1lib and the header files are in usr local include If this is not the case you must adjust the Pip makefile by giving to the configure shell script the option with gmp PATH where PATH is the GMP library installation path By giving configure the option enable gmp you ask for a GMP version only It results in a multiple precision Pip called pipMP 4 4 Building the Executable and the Library To build PIP first copy the above tarfile to any convenient directory Expand the tarfile using zcat pip tar Z tar xvf You should obtain the following files e header files in the include directory
25. unknowns j i parameters k mn 1 if 1 1 0 0 list 0 0 0 0 1 0 0 0 list 1 1 0 0 0 1 0 0 To express this solution no new parameter had to be introduced The form associated to the first conditional is 1xk 1xm 0xn 0xl m k so the test should be read as k m gt 0 If this inequality holds then the solution is lt 0 k gt Otherwise the solution is lt m k m gt To sum things up the lexicographical minimum of D is 2 USING THE PIP SOFTWARE 8 if m k gt 0 then lt 0 k gt else lt k m m gt Hence the lower bound on the first coordinate if m k gt 0 then O else k m 2 3 2 Simplifying the solution The solution of a parametric problem may be in the form of a quast all of whose leaves are nil This means in fact that the original polyhedron is empty whatever the values of the parameters An example due to Dirk Fimmel is the following G j 1 m n 2270 11 2 6 9 0 0 5 3 0 0 0 2 10 15 0 0 2 6 3 0 0 2 6 17 0 0 0 10 1 0 1 0 0 0 1 O Without the z option the solution is OCCE j 1 m n 1 if 4 0 5 if 0 4 3 O if 0 2 9 if 0 2 3 newparm 2 div 0 2 3 6 newparm 3 div 0 2 10 7 12 newparm 4 div 0 4 0 2 1 6 O Gif 0 2 7 newparm 2 div 0 4 3 6 if 0 8 6 11 O 0 O O Gif 1 0 3 if 1 0 2 Gf 10 2 15 00 2 USING THE PIP SOFTWARE 9 QO
26. utput or debug file cannot be opened Dimension errors e Too much variables e Too much parameters Check the input and or change the value of con stants MAXCOL and MAXPARM in file type h then rebuild PIP Implementation errors All such error messages begin by the word Syserr These messages indicate a bug in the implementation You should report such events by sending a copy of the input file by e mail to the author Paul Feautrier prism uvsq fr who will endeavor to solve the problem as soon as possible 2 3 Output Data The output file can be described by the following grammar Grammar 2 File Result Result Comments Solution Solution Quast_group void Quast_group Quast Newparm Quast Quast Form if Vector Quast_group Quast_group Form list Vector nil Newparm newparm Integer div Vector Integer Vector Coefficient Coefficient Integer Integer Integer The Comments are copied from the input file The Solution is said to be void when the initial context is void Otherwise it is given as a quast written a la Lisp The quast may possibly be preceded by the definition of one or several new parameters The vector coefficients may be either integers or rationals written as num denonm The latter case occurs if Nq had been set to 0 in the input file 2 USING THE PIP SOFTWARE 7 In the solution a Vector represents an affine form each entry is the coefficie
27. ving the problem This last method is more efficient since it tends to simplify the solution 2 USING THE PIP SOFTWARE 10 PIP is notified of the presence of a big parameter by setting the Bg argument to a positive value This value is the rank of the big parameter in the problem tableau Hence the lowest admissible value for Bg is Nn 1 The reader should convince himself that in the presence of two big parame ters no such simplifications are possible unless one has some information on the relative size of the parameters Such situations should be handled by giving PIP ordinary parameters and doing the simplification on the solution in the light of extra knowledge 2 4 3 Computing Lexicographical Maxima To get the maximum of an unknown 2 minimize B x where B is a new big parameter Adding a parameter just adds one column in the problem tableau The fact that this column corresponds to a Big parameter is specified by setting the 5 th switch to a positive value this value being the position of the column of B in the problem tableau These cases can be handled systematically in the following way Suppose that we are asked for the integer maximum of the polyhedron x gt 0 gt 0 6 3y lt x 12 y gt 2r 3 Let us introduce the new unknowns c B r y B y where B is the big parameter System 6 translates to 7 B gt 0 y B gt 0 x 3y 12 2B gt 0 2x y 3 B gt 0 Finding th
28. which p i points to the beginning of the it row NbRows and NbColumns are respectively the number of rows and columns of the matrix We use this structure to carry polyhedrons Each row corresponds to a constraint which the polyhedron must satisfy The constraint is an equality if the first element is 0 an inequality p x gt 0 if the first element is 1 The next elements are the unknown coefficients followed by the parameter coefficients The last element is the constant factor For instance in the problem of section 2 1 1 the domain is defined by 3 constraints i m gt 0 j n gt 0 j i k gt 0 the rows corresponding to these constraints would be eq in i j k m n cst 1 O 1 O 1 0 0 1 1 0 0 0 1 0 1 1 1 1 o o0 0 The context is defined by one constraint k m n gt 0 the row corresponding to this constraint would be eq in k m n cst 1 1 1 1 0 p Init_size is needed by the polylib to free the memory allocated by mpz_init in the multiple precision release 3 1 2 PipVector structure struct pipvector int nb_elements Entier the_vector Entier the_deno ae typedef struct pipvector PipVector 3 USING THE PIP LIBRARY 16 The PipVector structure represents a Vector as described in grammar 2 in sec tion 2 3 nb_elements is the number of vector elements the_vector is an array which contains the numerators of these elements and the_deno is an array which contains their denominators the it element is the_vect
Download Pdf Manuals
Related Search