Interface between MuPAD and Piplib:
Parametric Integer Programming

François Thomasset
INRIA - Rocquencourt - France
April 2003

PIP/PipLib is a parametric integer linear programming solver written by Paul Feautrier. PIP finds the lexicographic minimum of the set of integer points lying inside a convex polyhedron. This polyhedron may depend linearly on some integral parameters.
If the user does not require an integral solution, PIP can give the exact solution as an integral quotient. The heart of PIP is the parametrized algorithm of Gomory's cuts, followed by the parameterized dual simplex method. The PIP Library (PipLib for short) was implemented by Cédric Bastoul 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.

For more details and references on Pip, see the web page of Cédric Bastoul:
	  http://www.prism.uvsq.fr/~cedb/bastools/piplib.html

The present interface allows the user to type a system within MuPad, give it to Pip, and retrieve the solution in MuPad.
A polyhedron is defined as a list of linear inequalities satisfied by the coordinates of points in the polyhedron, possibly dependent on a set of parameters. These parameters may themselves be submitted to a system of constraints: the "context".
Example (from the RAIRO paper): 

>> PIP_minimize ([i <= m, j <= n,
                  2 i + j + k <= 2 m + n,
                  2 m + n <= 2 i + j + k
                 ],              // the system of inequalities defining the polyhedron
                 [i,j],          // the unknowns: variables iterating on the polyhedron
		 [k<=m+n],       // the context: inequalities relating the parameters
                 [k,m,n],        // parameters
		 -1,             // bigparm -- see the pip manual
                 TRUE,           // want an integer solution
                 1,1,            // simplify_, deepest_cut_: see the pip manual
                 0);             // verbose_: set it to 1 for debugging
Caveat: use the non strict operators "<=" and ">="; at the moment, I don't recognize the strict operators "<" and ">". It could make sense to accept strict operators when looking for integer solutions in a future version (then "a>b" would be replaced by "a>=b+1": this is correct when a and b are known to be integers; in the current version the user has to do this replacement himself in the input).
The equality operator "=" is not accepted either (use two inequalities instead). This restriction may also be alleviated some day.
PIP_minimize transforms this problem to appropriate tables and calls the dynamic module (interface_pip.mdm), which calls the actual Pip.

We retrieve in MuPad the following "quast" as a solution: 

[{}, _if_(0 <= 2 m - k + n,
          [{}, _if_(0 <= k - 2 m,
                    [{}, {i = 0, j = 2 m - k + n}],
                    [{p1 = k div 2}, _if_(0 <= n - k + 2 p1,
                                          [{}, {i = m - p1, j = n - k + 2 p1}],
                                          {} )
                    ] )
          ],
          {} )
]
As you can see, this quast structure is organized as a tree; at each level, we have 2 components: The leafs are sets of equalities expressing the solution as functions of the parameters. An empty set "{}" in a leaf means that this branch has no solution.

You may either handle this result in MuPAD, or call the pretty printing function pprint_quast to get a human-readable result: 

 if (0 <= 2*m - k + n)
   then
     if (0 <= k - 2*m)
       then
         {j = 2*m - k + n, i = 0}
       else
         p1 = k div 2
         if (0 <= n - k + 2*p1)
           then
             {j = n - k + 2*p1, i = m - p1}
           else
             {}
   else
     {}
Note: to compare with the RAIRO paper, don't forget the change of variable from (i,j) to (m-i,n-j)!

On option you may get the parameters substituted in the quast expressions when printing: giving TRUE as the the second argument to pprint_quast yields the following output, which a human reader may find more readable: 

 if (0 <= 2*m - k + n)
   then
     if (0 <= k - 2*m)
       then
         {j = 2*m - k + n, i = 0}
       else
         if (0 <= n - k + 2*(k div 2))
           then
             {j = n - k + 2*(k div 2), i = m - (k div 2)}
           else
             {}
   else
     {}

Finally the 3rd argument to pprint_quast allows the user to respect a MuPAD-like syntax in pretty-printing the output: assignments to new parameters terminated by semi-colons, if-then-else's terminated by 'end_if'.

Installation guide for this interface

  1. Install MuPad in some directory MuPadDIR (see the web site www.mupad.de). Make sure that MuPadDIR/share/bin is in your search path. Then saying: mupad in your shell starts a mupad session.
    Please use a version at least as recent as 2.0.0 of MuPad.
    Don't forget to register yourself as a MuPad user at www.sciface.com/register.shtml.

  2. Install the gmp and piplib libraries:
  3. Furthermore, the binary files of the libraries (libpiplibMP.a and libgmp.a) are expected to be installed in the directory $COMMON/lib; this is achieved by typing 'make install' in the directory of the library, provided the proper option has been given to configure when configure-ing gmp and piplib for your environment --try 'configure --help' for each of these libraries. So in directory $COMMON/lib, we expect to see (among others) files libpiplibMP.a and libgmp.a; in case 'make install' did not install these files for you, you may fix it via file copy or symbolic links, e.g. 
    	cd $COMMON/gmp
	ln -s libgmp.a ../lib/libgmp.a
    In your environment, setup your library path to the place where libraries are installed: 
            setenv LD_LIBRARY_PATH $COMMON/lib/
  4. Make sure that mupad and mmg are in your execution path. (mmg is the dynamic module generator of MuPAD; it will be used to compile the interface).
    Go to the directory where this distribution is installed; if a file interface_pip.mdm exists, remove it ('make clean'); then type 'make'.
    A new file interface_pip.mdm should be generated.

    Note that 'make world' will build everything for you: the libraries gmp and piplib, then it 'makes' the interface_pip.mdm. Provided of course that COMMON is correctly defined in your environment, and that the directories $COMMON/gmp and $COMMON/piplib contain the sources of these libraries.
    So that 'make world' is is equivalent to the sequence: 
            ./install_libs.sh
	make
  5. Start mupad.
    A number of examples are available in the files under the subdirectory Test of this distribution.
    Note that these example files assume that the directory where the present interface has been installed is available in a MuPAD variable with name pip_interface_dir. You may for instance initialize this variable in your initialization file $HOME/.mupad/userinit.mu; alternatively you may edit the examples files.
    So for instance, typing under a shell: 
    $ mupad Test/pip_rairoi.mupad
    should produce the above output for the rairo paper (provided the pip_interface_dir has been properly initialized).
    You may change the last parameter of PIP_minimize (want_integer_sol) to FALSE to see the rational solution.
Email: Francois.Thomasset@inria.fr