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 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 CPLEX callable routines library (version 4.0, 6.0, 7.0 or 
8.0). The program compiles with gcc-2.95.3 (or earlier version).

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

- Specify the location of gcc-2.95.3 (or earlier version), if it is not 
  the default on your system (use "gcc -v" to see the version of gcc you are
  using).

- Specify the location of the standard mathematical library (variable LIB).

- Specify the location of the CPLEX callable library libcplex.a 
  (variable LIB_CPLEX).

- For CPLEX7.0 and CPLEX8.0, specify the location of the header file
  cplex.h (variable CPLEX7H or CPLEX8H). (It is assumed that this file is
  in the directory $(LIB_CPLEX) for CPLEX4.0 and CPLEX6.0).

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