# README version 1.5
# 2011/10/21, 10:52:00
# - Francois IRIGOIN
C3/LINEAR LIBRARY FOR LINEAR INTEGER PROGRAMMING
------------------------------------------------
contributors: [linear@cri.ensmp.fr]
Corinne Ancourt, Neil Butler, Béatrice Creusillet, Fabien Coelho,
Malik Imadache, Francois Irigoin, Duong Nguyen, Nga Nguyen, Yi-qing Yang.
This library uses sparse data structures to store the vectors,
constraints and constraint systems, and dense data structures for
matrices.
The C data type for the coefficients is Value. It can be set to 32 or
64 bit integers, but is incompatible with big nums. Arithmetic
overflows are trapped.
The library is also interfaced with the Janus library.
BUILDING THE LIBRARIES
----------------------
The libraries are available on Internet at URL:
LINEAR_SVN=http://svn.cri.ensmp.fr/svn/linear
- for building these libraries, use gmake (GNU Make)
- environment variables of interest for building the linear libraries
directories:
LINEAR_ROOT= your-installation-directory/prod/linear
LINEAR_PRODDIR=$(LINEAR_ROOT)
LINEAR_INCDIR=$(LINEAR_PRODDIR)/include
LINEAR_SHRDIR=${LINEAR_PRODDIR}/Share (old in /Include)
LINEAR_LIBDIR=$(LINEAR_PRODDIR)/lib
LINEAR_SRCDIR=$(LINEAR_PRODDIR)/src
the order in which libraires should be built:
LINEAR_ORDERED_LIBS="arithmetique vecteur contrainte sc matrice matrix ray_dte sommet sg polynome polyedre plint sparse_sc union"
architecture:
Linear/C3 Library_ARCH=.
compilers and options:
see ${LINEAR_INCDIR}/makefile_macros.${Linear/C3 Library_ARCH}
you can define your own file.
- then gmake LIBS=${LINEAR_ORDERED_LIBS} recompile
USING THE LIBRARY
-----------------
include the needed headers stored in $LINEAR_INCLUDEDIR
links to the libraries stored in $LINEAR_LIBDIR/$Linear/C3 Library_ARCH
For use examples, see the Tests directory.
DATA TYPES HIERARCHY
--------------------
arithmetique:
vecteur[arithmetique]: vectors
contrainte[vecteur]: constraints
sc[contrainte,vecteur]: systems (equalities and inequalities)
matrice: rational dense matrices
ray_dte:
sommet[ray_dte,vecteur]: for constraints, systems and functions (?)
plint[sommet,matrice,sc]: integer linear programming
sparse_sc[matrice,sc]: sparse systems
sg[sommet,ray_dte]: generating systems
polyedre[sg,sc]: polyhedrons
union[sc]: polyhedron list, Presburger equivalent (see Arnauld
Leservot's PhD)
polynome[sc]: polynomial library
The interesting functions are located in the "sc" library when only
constraints are used. If the dual representation is used (sg
library), functions are to be found in the "polyedre" library.
Each source sub-directory, e.g. arithmetique, contains information
about its data structures in sub-directory/sub-directory.h,
e.g. arithmetique/arithmetique.h or sc/sc.h, and about the
sub-directory functions. This is information is usually given in
French. Source code also contains comments for each function.
TEXTUAL INTERFACE
-----------------
A textual format has been defined to input and output sparse
constraint systemsm (sc). Here is one example:
VAR i, j, k
{
i==1,
j <= 2i,
j + k == 3
}
Note that each dimension is named and declared. Here, a 3-D system
is declared with dimensions i, j and k. Note that multiplications
are implicit and the constraint formatting is free. Constraints can
be spread on multiple lines. An several constraints can be declared
in one line.
# end of README
#