# source:git/IntegerProgramming/solve_IP.hlp@6ba162

spielwiese
Last change on this file since 6ba162 was 6ba162, checked in by Hans Schönemann <hannes@…>, 23 years ago
This commit was generated by cvs2svn to compensate for changes in r4282, which included commits to RCS files with non-trunk default branches. git-svn-id: file:///usr/local/Singular/svn/trunk@4283 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to `100644`
File size: 8.1 KB
Line
1USAGE: solve_IP [options] toric_file problem_file
2
3
4
5DESCRIPTION:
6
7solve_IP is a program for solving integer programming problems with
8the Buchberger algorithm:
9
10Let A an integral (mxn)-matrix, b a vector with m integral
11coefficients and c a vector with n nonnegative real coefficients. The
12solution of the IP-problem
13
14    minimize{ cx | Ax=b, all components of x are nonnegative integers }
15
16proceeds in two steps:
17
181. We compute the toric ideal of A and its Groebner basis with respect
19   to a term ordering refining the cost function c.
20
212. We reduce the right hand vector b or an initial solution of the
22   problem modulo this ideal.
23
24For these purposes, we can use seven different algorithms:
25The algorithm of Conti/Traverso (ct) can compute an optimal solution
26of the IP-problem directly from the right hand vector b. The same is
27true for its "positive" variant (pct) which can only be applied if A
28and b have nonnegative entries, but should be faster in that case.
29All other algorithms need initial solutions of the IP-problem. Except
30from the elimination version of the Conti-Traverso algorithm (ect),
31they should be more efficient than the algorithm mentionned before.
32These are the algorithms of Pottier (pt), Bigatti/La Scala/Robbiano
33(blr), Hosten/Sturmfels (hs) and Di Biase/Urbanke (du). The last two
34seem to be the fastest in the actual implementation.
35
36
37
38FILE FORMAT:
39
40The first input file may be a MATRIX or a GROEBNER file; these two
41types are called "toric files". The second input file has to be a
42PROBLEM file.
43
44If the PROBLEM file contains a positive number of problems ,i.e. right
45hand vectors or initial solutions, solve_IP appends its solutions to a
46SOLUTION file named like the first input file with extensions replaced
47by
48
49        .sol.<alg>
50
51where sol stands for solution and <alg> is the abbreviation of the
52used algorithm as above. When called with a MATRIX file, solve_IP
53produces a GROEBNER file named like the MATRIX file with extensions
54replaced by
55
56        .GB.<alg>
57
58where GB stands for GROEBNER.
59
60A MATRIX file should look as follows:
61
62
63  MATRIX
64
65  columns:
66  <number of columns>
67
68  cost vector:
69  <coefficients of the cost vector>
70
71  rows:
72  <number of rows>
73
74  matrix:
75  <matrix coefficients>
76
77  positive row space vector:
78  <coefficients of row space vector>
79
80
81The last two lines are only needed when solve_IP is called with the
82algorithms of Hosten/Sturmfels or Bigatti/La Scala/Robbiano, i.e. the
83options
84
85        -alg hs
86or
87        -alg blr
88
89The other algorithms ignore these lines.
90
91Example:
92
93
94  MATRIX
95
96  columns:
97  3
98
99  cost vector:
100  1 1 1
101
102  rows:
103  2
104
105  matrix:
106  1 2 3
107  4 5 6
108
109  positive row space vector:
110  1 2 3
111
112
113A GROEBNER file looks as follows:
114
115
116  GROEBNER
117
118  computed with algorithm:
119  <algorithm name abbreviation>       (* abbreviations as above *)
120  from file(s):                       (* the following four lines are
121  <name of respective MATRIX file>       optional *)
122  computation time:
123  <computation time in seconds>
124
125  term ordering:
126  elimination block
127  <number of elimination variables>
128  <LEX / DEG_LEX                      (* only if number of elimination
129  / DEG_REV_LEX>                         variables >0 *)
130  weighted block
131  <number of weighted variables>
132  <W_LEX / W_REV_LEX                  (* number of weighted variables
133  / W_DEG_LEX / W_DEG_REV_LEX>           should always be >0 *)
134  <weight_vector>
135
136  size:
137  <number of elements>
138
139  Groebner basis:
140  <basis elements>
141
142  <settings for the Buchberger
143   algorithm and compiler settings>  (* optional *)
144
145
146The Groebner basis consists always of binomials of the form x^a - x^b
147where x^a and x^b are relatively prime. Such a binomial can be
148represented by the vector a-b. The basis elements in the GROEBNER file
149are given by the coefficients of this vector representation.
150The settings for BuchbergerŽs algorithm and the compiler flags are
151produced when the GROEBNER file is generated by a call of solve_IP
152with the verbose output option
153
154        -v, --verbose
155
156Example (not belonging to the example above):
157
158
159  GROEBNER
160
161  computed with algorithm:
162  du
163
164  term ordering:
165  elimination block:
166  0
167  weighted block:
168  3
169  W_LEX
170  1 2 3
171
172  size:
173  1
174
175  Groebner basis:
176  2 3 -2                            (*  x^2 * y^3 - z^2  *)
177
178
179A PROBLEM file should look as follows:
180
181
182  PROBLEM
183
184  vector size:
185  <vector dimension>
186
187  number of instances:
188  <number of vectors>
189
190  right-hand or initial solution vectors:
191  <vector coefficients>
192
193
194A SOLUTION file looks as follows:
195
196  SOLUTION
197
198  computed with algorithm:
199  <algorithm name abbreviation>
200  from file:                                  (* the GROEBNER file *)
201  <file name>
202
203  <right hand/initial solution> vector:
204  <vector as in the problem file>
205  solvable:                                   (* only if right-hand
206  <YES/NO>                                       vector is given *)
207  optimal solution:                           (* only in the case of
208  <optimal solution vector>                      existence *)
209  computation time:                           (* only for reduction *)
210  <reduction time in seconds>
211
212  ...                                         (* further vectors,
213                                                 same format *)
214
215
216
217OPTIONS:
218
219 -alg       <alg>,
220--algorithm <alg>         algorithm to use for solving the given IP
221                          instances; <alg> may be
222             ct           for Conti/Traverso,
223             pct          for the positive Conti/Traverso,
224             ect          for Conti/Traverso with elimination,
225             pt           for Pottier,
226             hs           for Hosten/Sturmfels,
227             du           for Di Biase/Urbanke,
228             blr          for Bigatti-LaScal-Robbiano.
229
230 -p         <number>      percentage of new generators to cause an
231                          autoreduction during BuchbergerŽs algorithm;
232                          <number> may be an arbitrary float, a
233                          negative value allows no intermediate
234                          autoreductions
235                          default is
236                          -p 12.0
237
238 -S [RP] [M] [B] [M]   criteria to use in BuchbergerŽs algorithm
240             RP           relatively prime leading terms
241             M            Gebauer-Moeller criterion M
242             F            Gebauer-Moeller criterion F
243             B            Gebauer-Moeller criterion B
244             2            BuchbergerŽs second criterion
245                          default is
246                          -S RP M B
247
248 -v,
249--verbose                 verbose output mode; writes the settings for
250                          BuchbergerŽs algorithm and the compiler
251                          flags into the output GROEBNER file
252
253-V <number>,
254--version <number>        version of BuchbergerŽs algorithm to use;
255                          <number> may be 1, 1a, 2 or 3
256                          default is
257                          -V 1
258
259
260When called with a GROEBNER file, these options do not affect
261computation and are ignored by solve_IP.
Note: See TracBrowser for help on using the repository browser.