source: git/IntegerProgramming/solve_IP.hlp

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.