1 | USAGE: solve_IP [options] toric_file problem_file |
---|
2 | |
---|
3 | |
---|
4 | |
---|
5 | DESCRIPTION: |
---|
6 | |
---|
7 | solve_IP is a program for solving integer programming problems with |
---|
8 | the Buchberger algorithm: |
---|
9 | |
---|
10 | Let A an integral (mxn)-matrix, b a vector with m integral |
---|
11 | coefficients and c a vector with n nonnegative real coefficients. The |
---|
12 | solution of the IP-problem |
---|
13 | |
---|
14 | minimize{ cx | Ax=b, all components of x are nonnegative integers } |
---|
15 | |
---|
16 | proceeds in two steps: |
---|
17 | |
---|
18 | 1. We compute the toric ideal of A and its Groebner basis with respect |
---|
19 | to a term ordering refining the cost function c. |
---|
20 | |
---|
21 | 2. We reduce the right hand vector b or an initial solution of the |
---|
22 | problem modulo this ideal. |
---|
23 | |
---|
24 | For these purposes, we can use seven different algorithms: |
---|
25 | The algorithm of Conti/Traverso (ct) can compute an optimal solution |
---|
26 | of the IP-problem directly from the right hand vector b. The same is |
---|
27 | true for its "positive" variant (pct) which can only be applied if A |
---|
28 | and b have nonnegative entries, but should be faster in that case. |
---|
29 | All other algorithms need initial solutions of the IP-problem. Except |
---|
30 | from the elimination version of the Conti-Traverso algorithm (ect), |
---|
31 | they should be more efficient than the algorithm mentionned before. |
---|
32 | These are the algorithms of Pottier (pt), Bigatti/La Scala/Robbiano |
---|
33 | (blr), Hosten/Sturmfels (hs) and Di Biase/Urbanke (du). The last two |
---|
34 | seem to be the fastest in the actual implementation. |
---|
35 | |
---|
36 | |
---|
37 | |
---|
38 | FILE FORMAT: |
---|
39 | |
---|
40 | The first input file may be a MATRIX or a GROEBNER file; these two |
---|
41 | types are called "toric files". The second input file has to be a |
---|
42 | PROBLEM file. |
---|
43 | |
---|
44 | If the PROBLEM file contains a positive number of problems ,i.e. right |
---|
45 | hand vectors or initial solutions, solve_IP appends its solutions to a |
---|
46 | SOLUTION file named like the first input file with extensions replaced |
---|
47 | by |
---|
48 | |
---|
49 | .sol.<alg> |
---|
50 | |
---|
51 | where sol stands for solution and <alg> is the abbreviation of the |
---|
52 | used algorithm as above. When called with a MATRIX file, solve_IP |
---|
53 | produces a GROEBNER file named like the MATRIX file with extensions |
---|
54 | replaced by |
---|
55 | |
---|
56 | .GB.<alg> |
---|
57 | |
---|
58 | where GB stands for GROEBNER. |
---|
59 | |
---|
60 | A 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 | |
---|
81 | The last two lines are only needed when solve_IP is called with the |
---|
82 | algorithms of Hosten/Sturmfels or Bigatti/La Scala/Robbiano, i.e. the |
---|
83 | options |
---|
84 | |
---|
85 | -alg hs |
---|
86 | or |
---|
87 | -alg blr |
---|
88 | |
---|
89 | The other algorithms ignore these lines. |
---|
90 | |
---|
91 | Example: |
---|
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 | |
---|
113 | A 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 | |
---|
146 | The Groebner basis consists always of binomials of the form x^a - x^b |
---|
147 | where x^a and x^b are relatively prime. Such a binomial can be |
---|
148 | represented by the vector a-b. The basis elements in the GROEBNER file |
---|
149 | are given by the coefficients of this vector representation. |
---|
150 | The settings for BuchbergerŽs algorithm and the compiler flags are |
---|
151 | produced when the GROEBNER file is generated by a call of solve_IP |
---|
152 | with the verbose output option |
---|
153 | |
---|
154 | -v, --verbose |
---|
155 | |
---|
156 | Example (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 | |
---|
179 | A 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 | |
---|
194 | A 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 | |
---|
217 | OPTIONS: |
---|
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] [2] criteria to use in BuchbergerŽs algorithm |
---|
239 | for discarding unneccessary S-pairs |
---|
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 | |
---|
260 | When called with a GROEBNER file, these options do not affect |
---|
261 | computation and are ignored by solve_IP. |
---|