USAGE: solve_IP [options] toric_file problem_file
            
             
           
DESCRIPTION:
             
solve_IP is a program for solving integer programming problems with
the Buchberger algorithm:
             
Let A an integral (mxn)-matrix, b a vector with m integral
coefficients and c a vector with n nonnegative real coefficients. The
solution of the IP-problem 
          
    minimize{ cx | Ax=b, all components of x are nonnegative integers }
              
proceeds in two steps:
           
1. We compute the toric ideal of A and its Groebner basis with respect
   to a term ordering refining the cost function c. 
            
2. We reduce the right hand vector b or an initial solution of the
   problem modulo this ideal.
              
For these purposes, we can use seven different algorithms:
The algorithm of Conti/Traverso (ct) can compute an optimal solution
of the IP-problem directly from the right hand vector b. The same is
true for its "positive" variant (pct) which can only be applied if A
and b have nonnegative entries, but should be faster in that case. 
All other algorithms need initial solutions of the IP-problem. Except
from the elimination version of the Conti-Traverso algorithm (ect),
they should be more efficient than the algorithm mentionned before.
These are the algorithms of Pottier (pt), Bigatti/La Scala/Robbiano
(blr), Hosten/Sturmfels (hs) and Di Biase/Urbanke (du). The last two
seem to be the fastest in the actual implementation.
                
            
                
FILE FORMAT:
               
The first input file may be a MATRIX or a GROEBNER file; these two
types are called "toric files". The second input file has to be a
PROBLEM file. 
               
If the PROBLEM file contains a positive number of problems ,i.e. right
hand vectors or initial solutions, solve_IP appends its solutions to a
SOLUTION file named like the first input file with extensions replaced
by 
          
	.sol.<alg>
              
where sol stands for solution and <alg> is the abbreviation of the
used algorithm as above. When called with a MATRIX file, solve_IP
produces a GROEBNER file named like the MATRIX file with extensions
replaced by 	 
              
	.GB.<alg> 
             
where GB stands for GROEBNER.
               
A MATRIX file should look as follows:
           
            
  MATRIX              
            
  columns:
  <number of columns>
              
  cost vector:
  <coefficients of the cost vector>
          
  rows:
  <number of rows>
            
  matrix:
  <matrix coefficients>
          
  positive row space vector:              
  <coefficients of row space vector>                                 
         
        
The last two lines are only needed when solve_IP is called with the
algorithms of Hosten/Sturmfels or Bigatti/La Scala/Robbiano, i.e. the
options  
         
	-alg hs
or
	-alg blr
          
The other algorithms ignore these lines.  
       
Example:
       
       
  MATRIX
        
  columns:
  3
            
  cost vector:
  1 1 1
      
  rows:
  2
          
  matrix:
  1 2 3
  4 5 6
          
  positive row space vector:
  1 2 3
          
          
A GROEBNER file looks as follows:
         
         
  GROEBNER 
            
  computed with algorithm:
  <algorithm name abbreviation>       (* abbreviations as above *)
  from file(s):                       (* the following four lines are 
  <name of respective MATRIX file>       optional *)
  computation time:                     
  <computation time in seconds>          
             
  term ordering:
  elimination block
  <number of elimination variables>
  <LEX / DEG_LEX                      (* only if number of elimination
  / DEG_REV_LEX>                         variables >0 *)
  weighted block
  <number of weighted variables>
  <W_LEX / W_REV_LEX                  (* number of weighted variables    
  / W_DEG_LEX / W_DEG_REV_LEX>           should always be >0 *)
  <weight_vector>
             
  size:
  <number of elements>
          
  Groebner basis:
  <basis elements>                   
            
  <settings for the Buchberger 
   algorithm and compiler settings>  (* optional *)		
            
                  
The Groebner basis consists always of binomials of the form x^a - x^b
where x^a and x^b are relatively prime. Such a binomial can be
represented by the vector a-b. The basis elements in the GROEBNER file 
are given by the coefficients of this vector representation.
The settings for Buchberger´s algorithm and the compiler flags are
produced when the GROEBNER file is generated by a call of solve_IP
with the verbose output option
          
	-v, --verbose  
             
Example (not belonging to the example above):
         
         
  GROEBNER
         
  computed with algorithm:
  du
        
  term ordering:	
  elimination block:
  0
  weighted block:
  3
  W_LEX
  1 2 3
           
  size:
  1
              
  Groebner basis:
  2 3 -2			    (*  x^2 * y^3 - z^2  *) 
           
               
A PROBLEM file should look as follows:
          
             
  PROBLEM
             
  vector size:
  <vector dimension>
            
  number of instances:
  <number of vectors>
             
  right-hand or initial solution vectors:      
  <vector coefficients>                    
         
            
A SOLUTION file looks as follows:
          
  SOLUTION                                   
               
  computed with algorithm:               
  <algorithm name abbreviation>          
  from file:                                  (* the GROEBNER file *)    
  <file name>                                  
             
  <right hand/initial solution> vector:       
  <vector as in the problem file>
  solvable:                                   (* only if right-hand
  <YES/NO>                                       vector is given *) 
  optimal solution:                           (* only in the case of 
  <optimal solution vector>		         existence *) 
  computation time:                           (* only for reduction *) 
  <reduction time in seconds>                 
            
  ...                                         (* further vectors,
                                                 same format *) 
         
        
             
OPTIONS: 
          
 -alg       <alg>,      
--algorithm <alg>         algorithm to use for solving the given IP 
                          instances; <alg> may be 
             ct           for Conti/Traverso,
             pct          for the positive Conti/Traverso,
             ect          for Conti/Traverso with elimination,
             pt           for Pottier,
             hs           for Hosten/Sturmfels,
             du           for Di Biase/Urbanke,
             blr          for Bigatti-LaScal-Robbiano.
               
 -p         <number>      percentage of new generators to cause an
                          autoreduction during Buchberger´s algorithm; 
                          <number> may be an arbitrary float, a
                          negative value allows no intermediate
                          autoreductions
			  default is 
                          -p 12.0  
                
 -S [RP] [M] [B] [M] [2]  criteria to use in Buchberger´s algorithm
                          for discarding unneccessary S-pairs
             RP           relatively prime leading terms
             M            Gebauer-Moeller criterion M
             F            Gebauer-Moeller criterion F
             B            Gebauer-Moeller criterion B
             2            Buchberger´s second criterion
			  default is 
                          -S RP M B 		
             
 -v,          
--verbose                 verbose output mode; writes the settings for 
                          Buchberger´s algorithm and the compiler
                          flags into the output GROEBNER file 
             
-V <number>, 
--version <number>        version of Buchberger´s algorithm to use;
                          <number> may be 1, 1a, 2 or 3
			  default is
                          -V 1	
                  
                   
When called with a GROEBNER file, these options do not affect
computation and are ignored by solve_IP.