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 mentioned 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 unnecessary 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.