GENERAL

For a linear system describing a polyhedron P of the form
  
                                b - A y - B x >= 0

and the list of the extreme rays u of the cone u A = 0, u >= 0, the program
domcheck_clp generates the inequalities

                               (u b) - (u B) x >= 0

and outputs an equivalent minimal system of inequalities (i.e. a minimal system
describing the projection of the polyhedron onto the space of the variables x).
  
If a set of inequalities

                                    s - S x >= 0

is known to be valid for this projection there is the option of specifying
this set. The program will then report if this set of inequalities is
sufficient or not to describe the projection (useful in particular for non
full dimensional polytopes).

This program may also be used simply to remove redundancy in a given linear
system of the form
                              b - B x >= 0.
                              
In that case, just put 'none' for the file containing the extreme rays.




INSTALLATION

The program uses the CLP solver from the COIN library. (see
http://www-coin-or.org).

To install the program, some modifications in the makefile are necessary:

- Specify the location of the gcc compiler g++, if it is not the default
  on your system.

- Specify the location of the standard mathematical library (variable LIB)
  and other required libraries.

- Specify the location of the include directory containing the header files 
  OsiSolverInterface.hpp, OsiClpSolverInterface.hpp, and CoinTime.hpp
  on the line starting with 'COINinc = '

- Specify the location of the library directory containing the libraries
  CoinUtils, Osi, OsiClp, and Clp (these must be installed separately).



INPUT FILE FORMAT

A system b - B x >= 0 with n inequalities and m variables is described by
a matrix of size (n x (m+1)) containing the coefficients of [b  (-B)].
More precisely, the file looks like:

     [text]
     begin
     #lines_to_read   #columns_to_read    [type_of_input]
     ...
     ...
     ...     (matrix of size (#lines_to_read x #columns_to_read))
     ...
     ...
     end
     [option]

where
     [text] is an arbitrary text not containing the keyword 'begin'.

     [type_of_input] is 'real', 'integer' or 'rational' (optional for
                     this program).

     [option] can only be 'nonnegative', which means that the inequalities
              implying the non negativity of the variables have to be added
              to the system. (this option is allowed only for the file 
              containing [s  (-S)]).


NB: 1) The file containing the extreme rays of the cone u A = 0, u >= 0 is
       supposed to be the output file of Fukuda's program cdd
       (see cdd user manual).

    2) each line of a matrix can be followed by a comment
       (skipped by the program).





OUTPUT FILE FORMAT

A matrix of the form [e  (-E)   (indic)] corresponding to the system

e - E x >= 0.

The entries of the array (indic) are either

     an integer                 or               'S' followed by an integer.

In the first case, the integer is the number of the ray generating the 
corresponding inequality. In the second case, the integer is the number of
the inequality of the system [s (-S)] corresponding to the inequality.





EXAMPLES

Several examples of input and output files may be found in the
subdirectory EX.

Input files:

   The files containing the rays have the suffix '.ext'

   The files containing the system [b  (-B)] have the suffix 'sub.ine'

   The files containing a dominating system [s  (-S)] have the suffix '.syst'

Output files:

   The output files generated when the dominating system is part of the input
   have the suffix '.res'

   The output files generated without specifying the dominating system (option
   'none') have the suffix '.resnone'
   


CONTACT AND BUG REPORT

fmargot@andrew.cmu.edu