PIP/PipLib - A parametric integer linear programming solver

What's new:

This page is no more maintained, PipLib is now on http://www.PipLib.org.
New PipLib's home, available since November 9th 2005.
PIP/PipLib 1.3.3 (From 1.2.x to 1.3.x Caution: changes !), available since April 14th, 2004.

[Home] [Getting PIP/PipLib] [Documentation and Information] [PIP Links] [References]

PIP/PipLib is the well known Paul Feautrier's parametric integer linear programming solver [2,3]. PIP is a software which finds the lexicographic minimum of the set of integer points lying inside a convex polyhedron. This polyhedron can depend linearly on one or more integral parameters. If the user asks for a non integral solution, PIP can give the exact solution as an integral quotient. The heart of PIP is the parametrized Gomory's cuts algorithm [2,4] followed by the parameterized dual simplex method [1,2,5]. 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.

Polyhedron to study	Context

	No context. PIP will give all the solutions corresponding to all the possible cases according to the parameter values: if (7n >= 10) { if (7m >= 12) { (i = 2, j = 2) } if (2n+3m >= 8) { (i = -m-(m div 2)+4, j = m) } } With context. It is possible to fully or partially define the parameter values. Then PIP will give only the solutions for the possible cases. For instance with the context: m >= n n >= 5 there is only one possible solution: (i = 2, j = 2)

Getting PIP/PipLib

Latest sources

PIP/PipLib 1.3.3 (211kb) (updated: April 14th, 2004).

This version includes PIP/PipLib 32, 64 bits and MP (multiple precision). It is still for evaluation and there is no guarantee that the upward compatibility will be respected (although we do think so). A lot of reports are needed to freeze the library API. So you are very welcome and encouraged to send me reports of bugs, wishes, critics, comments, suggestions or successful experiences.

Changes

1.3.2 -> 1.3.3 : Option for computing the lexicographic maximum.
1.3.1 -> 1.3.2 : Full compatibility between PipMatrix and PolyLib's Matrix structures (fixes MP version).
1.3 -> 1.3.1 : Problem when linking PipLibMP under C++ solved, crash when callin PIP without parameter fixed, better automatic testing.
1.2.1 -> 1.3 : new -d option for using the deepest cut algorithm. Changes in the pip_solve calling in PipLib in order to garantee upward compatibility from this version, see the manual for this function. Verbose option is now graduated.
1.2 -> 1.2.1 : fixes in the MP version (mainly leak fixes, but also fixes in the handling of equalities). Many thanks to Eddy De Greef.
1.1 -> 1.2 : Integer/MP codes fusion, minor bug fixes, static library now working, linking from C++ facilities added.
1.0.2 -> 1.1 : Multiple precision version integration.
1.0.1 -> 1.0.2 : No more segfault with -s option.
1.0 -> 1.0.1 : Tests can be checked automatically.

Extensions

MuPad-PipLib Interface by François Thomasset (available since May 5th, 2003).

You are invited to check the Paul Feautrier homepage for further news about PIP.

Documentation and Information

Latest documentation:

PIP/PipLib's Guide (290kb), (postscript, PDF, HTML) (updated: October 18, 2003).

The user's guide presents some useful background and some kind of problems where a parametric integer programming solver can help. It shows in detail how to write the input file for the PIP software and how to set its options. It presents the PIP library, its data structures and its various functions. It explains how to compile, install and uninstall it. A copy of this document is provided in the doc/ subdirectory in the standard distribution.

The PolyLib mailing-list:

Announcements on PIP/PipLib are sent to the PolyLib mailing-list. To join the list, send an email to sympa@u-strasbg.fr containing the following message: SUB PolyLib firstname lastname organization. You will then be asked to confirm your subscription by replying to the returned message. A forum group of the Polylib community was also set up. You may subscribe to the group in order to be able to have full contact with the Polylib world.

PIP Links

PIP has a long history started with Paul Feautrier in 1988. It is used anywhere the polyhedral model is useful and in particular in automatic parallelization domain:

LooPo
PIPS
Bouclettes
PAF

SPPoC was the first tool providing PIP as a library and an easy access to polyhedral computation.

References

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

[2] P. Feautrier. Parametric integer programming. RAIRO Recherche Opérationnelle, 22(3):243-268, 1988. [bibtex]

[3] P. Feautrier, J.F. Collard, C. Bastoul. Solving systems of affine (in)equalities. Technical Report, PRiSM, Versailles University, 2002. [postscript] [bibtex]

[4] R. Gomory. Outline of an algorithm for integer solutions to linar programs. Bulletin of the American Mathematical Society 64:275-278, 1958.

[5] Lemke. The dual method for solving the linear programming problem. Naval Research Logistic Quarterly 22:978-981, 1954.

last update feruary, 6th 2003.
Cédric Bastoul, cedric.bastoul@prism.uvsq.fr