1 | // IP_algorithms.h |
---|
2 | |
---|
3 | #ifndef IP_ALGORITHMS_H |
---|
4 | #define IP_ALGORITHMS_H |
---|
5 | |
---|
6 | #include "ideal.h" |
---|
7 | |
---|
8 | typedef char* INPUT_FILE; |
---|
9 | typedef char* OUTPUT_FILE; |
---|
10 | |
---|
11 | // This file contains the declaration of all implemented IP-algorithms. |
---|
12 | // They only solve problems for nonnegative weight vectors. |
---|
13 | |
---|
14 | // Let A an integral (mxn)-matrix, b a vector with m integral |
---|
15 | // coefficients and c a vector with n nonnegative real coefficients. |
---|
16 | // The solution of the IP-problem |
---|
17 | // |
---|
18 | // minimize cx |
---|
19 | // under the conditions |
---|
20 | // Ax=b and all components of x are nonnegative integers |
---|
21 | // |
---|
22 | // proceeds in two steps: |
---|
23 | |
---|
24 | // First, we have to compute the toric ideal of A and its Groebner basis |
---|
25 | // with respect to a term ordering refining the cost function c. This can |
---|
26 | // be done by the following procedures. They check the format of their input |
---|
27 | // file (which should be a MATRIX file as described below) and return 1 if |
---|
28 | // they were successfull, 0 else. |
---|
29 | // They take as arguments: |
---|
30 | // - their input file |
---|
31 | // - the arguments for BuchbergerŽs algorithm (see the comments in ideal.h) |
---|
32 | // - the output mode (verbose or not, default: not verbose; verbose mode |
---|
33 | // prints compiler settings and options for BuchbergerŽs algorithm) |
---|
34 | // The last four arguments have default values and do not have to be |
---|
35 | // specified. |
---|
36 | |
---|
37 | // In the case of a successful computation, they write the computed Groebner |
---|
38 | // basis into a GROEBNER file which is named as the input file with extension |
---|
39 | // replaced by |
---|
40 | // .GB.<alg> |
---|
41 | // where <alg> is an abbreviation for the used algorithm: |
---|
42 | // ct for Conti_Traverso(...) |
---|
43 | // pct for Positive_Conti_Traverso(...) |
---|
44 | // ect for Elim_Conti_Traverso(...) |
---|
45 | // pt for Pottier(...) |
---|
46 | // hs for Hosten_Sturmfels(...) |
---|
47 | // du for DiBiase_Urbanke(...) |
---|
48 | // blr for Bigatti_LaScala_Robbiano(...) |
---|
49 | |
---|
50 | extern int Conti_Traverso(INPUT_FILE MATRIX, |
---|
51 | const short& version=1, |
---|
52 | const short& S_pair_criteria=11, |
---|
53 | const float& interred_percentage=12.0, |
---|
54 | const BOOLEAN& verbose=FALSE); |
---|
55 | // The complete algorithm of Conti and Traverso which computes the toric |
---|
56 | // ideal of an extended matrix and which can be used for solving |
---|
57 | // integer programs without initial solution. |
---|
58 | |
---|
59 | extern int Positive_Conti_Traverso(INPUT_FILE MATRIX, |
---|
60 | const short& version=1, |
---|
61 | const short& S_pair_criteria=11, |
---|
62 | const float& interred_percentage=12.0, |
---|
63 | const BOOLEAN& verbose=FALSE); |
---|
64 | // The variant of the above algorithm for matrices and right hand vector |
---|
65 | // with only nonnegative entries using one elimination variable less. |
---|
66 | |
---|
67 | extern int Elim_Conti_Traverso(INPUT_FILE MATRIX, |
---|
68 | const short& version=1, |
---|
69 | const short& S_pair_criteria=11, |
---|
70 | const float& interred_percentage=12.0, |
---|
71 | const BOOLEAN& verbose=FALSE); |
---|
72 | // A version of the Conti-Traverso-algorithm which really computes the toric |
---|
73 | // ideal of A. Used for test purposes (correctness and performance of the |
---|
74 | // other algorithms). Nonnegativity is ignored. |
---|
75 | |
---|
76 | extern int Pottier(INPUT_FILE MATRIX, |
---|
77 | const short& version=1, |
---|
78 | const short& S_pair_criteria=11, |
---|
79 | const float& interred_percentage=12.0, |
---|
80 | const BOOLEAN& verbose=FALSE); |
---|
81 | // The algorithm proposed by Pottier using one elimination variable and |
---|
82 | // a lattice basis of the matrix kernel to compute the toric ideal A. |
---|
83 | |
---|
84 | extern int Hosten_Sturmfels(INPUT_FILE MATRIX, |
---|
85 | const short& version=1, |
---|
86 | const short& S_pair_criteria=11, |
---|
87 | const float& interred_percentage=12.0, |
---|
88 | const BOOLEAN& verbose=FALSE); |
---|
89 | // The algorithm proposed by Hosten and Sturmfels which computes the toric |
---|
90 | // ideal of A from its kernel lattice basis without supplementary |
---|
91 | // variables, but with various Groebner basis calculations. |
---|
92 | |
---|
93 | extern int DiBiase_Urbanke(INPUT_FILE MATRIX, |
---|
94 | const short& version=1, |
---|
95 | const short& S_pair_criteria=11, |
---|
96 | const float& interred_percentage=12.0, |
---|
97 | const BOOLEAN& verbose=FALSE); |
---|
98 | // The algorithm proposed by DiBiase and Urbanke which computes the toric |
---|
99 | // ideal of A from its kernel lattice basis using "variable flips". |
---|
100 | |
---|
101 | extern int Bigatti_LaScala_Robbiano(INPUT_FILE MATRIX, |
---|
102 | const short& version=1, |
---|
103 | const short& S_pair_criteria=11, |
---|
104 | const float& interred_percentage=12.0, |
---|
105 | const BOOLEAN& verbose=FALSE); |
---|
106 | // A modified version of the algorithm called EATI using "pseudo-elimination". |
---|
107 | // This algorithm is quite similar to Pottier's algorithm, but deals with |
---|
108 | // homogenous binomials. |
---|
109 | |
---|
110 | // The second step of the IP-solution is to reduce one or more given |
---|
111 | // initial solutions (which also define right-hand vectors b) with respect |
---|
112 | // to the computed Groebner basis. In the case that the Groebner basis |
---|
113 | // was computed via the algorithm of Conti and Traverso, it is sufficient |
---|
114 | // to give the right-hand vectors. In all other cases we need explicit |
---|
115 | // initial solutions. The routine |
---|
116 | |
---|
117 | extern int solve(INPUT_FILE PROBLEM, INPUT_FILE GROEBNER); |
---|
118 | |
---|
119 | // solves the IP-problems given by the vectors in PROBLEM with respect |
---|
120 | // to GROEBNER which should contain a Groebner basis as computed above. The |
---|
121 | // output is appended to a (eventually newly created) file named as GROEBNER |
---|
122 | // with extensions replaced by: |
---|
123 | // .sol.<alg> |
---|
124 | // where <alg> is an abbreviation of the algorithm used to compute GROEBNER. |
---|
125 | |
---|
126 | // We also provide functionality to recompute toric ideals with respect to |
---|
127 | // another cost function: |
---|
128 | |
---|
129 | extern int change_cost(INPUT_FILE GROEBNER, INPUT_FILE NEW_COST, |
---|
130 | const short& version=1, |
---|
131 | const short& S_pair_criteria=11, |
---|
132 | const float& interred_percentage=12.0, |
---|
133 | const BOOLEAN& verbose=FALSE); |
---|
134 | |
---|
135 | // recomputes the Groebner basis in GROEBNER with respect to the cost given |
---|
136 | // in NEW_COST and writes the result into the file named as NEW_COST with |
---|
137 | // extension replaced by |
---|
138 | // .GB.<alg> |
---|
139 | // where <alg> is an abbreviation of the algorithm used to compute GROEBNER. |
---|
140 | |
---|
141 | ////////////////////////////////////////////////////////////////////////////// |
---|
142 | //////////// FORMAT OF INPUT AND OUTPUT FILES /////////////////////// |
---|
143 | ////////////////////////////////////////////////////////////////////////////// |
---|
144 | |
---|
145 | // The files appearing under the name MATRIX in the above declarations should |
---|
146 | // look as follows to be accepted by the algorithms: |
---|
147 | |
---|
148 | // MATRIX (* specifie format *) |
---|
149 | // |
---|
150 | // columns: |
---|
151 | // <number of columns> |
---|
152 | // |
---|
153 | // cost vector: |
---|
154 | // <coefficients of the cost vector> |
---|
155 | // |
---|
156 | // rows: |
---|
157 | // <number of rows> |
---|
158 | // |
---|
159 | // matrix: |
---|
160 | // <matrix coefficients> |
---|
161 | // |
---|
162 | // positive row space vector: (* optional, see below *) |
---|
163 | // <coefficients of row space vector> |
---|
164 | |
---|
165 | // For example: |
---|
166 | |
---|
167 | // MATRIX |
---|
168 | // |
---|
169 | // columns: |
---|
170 | // 3 |
---|
171 | // |
---|
172 | // cost vector: |
---|
173 | // 1 1 1 |
---|
174 | // |
---|
175 | // rows: |
---|
176 | // 2 |
---|
177 | // |
---|
178 | // matrix: |
---|
179 | // 1 2 3 |
---|
180 | // 4 5 6 |
---|
181 | // |
---|
182 | // positive row space vector: |
---|
183 | // 1 2 3 |
---|
184 | |
---|
185 | // The positive row space vector is only needed by the algorithms of |
---|
186 | // Hosten/Sturmfels and Bigatti/LaScala/Robbiano. It is ignored by the other |
---|
187 | // algorithms, as well as further lines in the input file. This allows us to |
---|
188 | // use the same input format for all algorithms. The comments (as the word |
---|
189 | // "rows:") are only written into the file to make it easy to read. |
---|
190 | |
---|
191 | |
---|
192 | // The file named NEW_COST in the change_cost procedure should have the |
---|
193 | // following format: |
---|
194 | |
---|
195 | // NEW_COST |
---|
196 | // |
---|
197 | // variables: (* only weighted variables *) |
---|
198 | // <number of weighted variables> |
---|
199 | // |
---|
200 | // cost vector: |
---|
201 | // <coefficients o the weight vector> |
---|
202 | |
---|
203 | // For convenience, the MATRIX format is also accepted by the change_cost |
---|
204 | // procedure. The lines following the cost vector are then ignored. |
---|
205 | |
---|
206 | // The files appearing under the name GROEBNER in the above declarations |
---|
207 | // are created in the following form by the algorithms for computing toric |
---|
208 | // ideals. This form is accepted by the solve(...) and the |
---|
209 | // change_cost(...) procedures: |
---|
210 | |
---|
211 | // GROEBNER (* specifie format *) |
---|
212 | // |
---|
213 | // computed with algorithm: |
---|
214 | // <algorithm name abbreviation> (* abbreviations as above *) |
---|
215 | // from file(s): (* the following four lines are |
---|
216 | // <name of respective MATRIX file> optional *) |
---|
217 | // computation time: |
---|
218 | // <computation time in seconds> |
---|
219 | // |
---|
220 | // term ordering: |
---|
221 | // elimination block |
---|
222 | // <number of elimination variables> |
---|
223 | // <LEX / DEG_LEX (* only if number of elimination |
---|
224 | // / DEG_REV_LEX> variables >0 *) |
---|
225 | // weighted block |
---|
226 | // <number of weighted variables> |
---|
227 | // <W_LEX / W_REV_LEX (* number of weighted variables |
---|
228 | // / W_DEG_LEX / W_DEG_REV_LEX> should always >0 *) |
---|
229 | // <weight_vector> |
---|
230 | // |
---|
231 | // size: |
---|
232 | // <number of elements> |
---|
233 | // |
---|
234 | // Groebner basis: |
---|
235 | // <basis elements> (* one basis element in each row, |
---|
236 | // given by the coefficients of |
---|
237 | // its vector representation *) |
---|
238 | // settings for the (* all following lines are |
---|
239 | // Buchberger algorithm: optional, verbose mode *) |
---|
240 | // version: (* as explained in ideal.h, |
---|
241 | // <version number> between 0 and 3 *) |
---|
242 | // S-pair criteria: |
---|
243 | // <{relatively prime leading terms, (* a subset of these criteria *) |
---|
244 | // criterion M, criterion F, |
---|
245 | // criterion B, second criterion}> |
---|
246 | // interreduction percentage: |
---|
247 | // <interreduction percentage> |
---|
248 | // |
---|
249 | // compiler settings: (* see the procedure |
---|
250 | // ... print_flags(...) in |
---|
251 | // ... IP_algorithms.cc *) |
---|
252 | |
---|
253 | // If the GROEBNER file is created by change_cost(...), the algorithm name |
---|
254 | // and MATRIX file are chosen as those of the original GROEBNER file; the |
---|
255 | // new_cost file is specified as a second MATRIX file. |
---|
256 | |
---|
257 | |
---|
258 | // The files appearing under the name PROBLEM in the above declarations should |
---|
259 | // look as follows to be accepted by the procedure solve(...): |
---|
260 | |
---|
261 | // PROBLEM (* specifie format *) |
---|
262 | // |
---|
263 | // vector size: |
---|
264 | // <vector dimension> |
---|
265 | // |
---|
266 | // number of instances: |
---|
267 | // <number of vectors> |
---|
268 | // |
---|
269 | // right hand or initial solution vectors: |
---|
270 | // <vector coefficients> (* one vector per row *) |
---|
271 | |
---|
272 | |
---|
273 | // solve(...) verifies if the vector size given in the PROBLEM file and |
---|
274 | // the number of variables given in the GROEBNER file match the respective |
---|
275 | // algorithm. In the matching case, it creates a SOLUTION file of the |
---|
276 | // following format (not used as an input file for any procedure): |
---|
277 | |
---|
278 | // SOLUTION (* specifie format *) |
---|
279 | // |
---|
280 | // computed with algorithm: (* from the respective |
---|
281 | // <algorithm name abbreviation> GROEBNER file *) |
---|
282 | // from file: (* the GROEBNER file *) |
---|
283 | // <file name> |
---|
284 | // |
---|
285 | // <right hand/initial solution> vector: |
---|
286 | // <vector as in the problem file> |
---|
287 | // solvable: (* only if right-hand |
---|
288 | // <YES/NO> vector is given *) |
---|
289 | // optimal solution: (* only in the case of |
---|
290 | // <optimal solution vector> existence *) |
---|
291 | // computation time: (* only reduction time *) |
---|
292 | // <reduction time in seconds> |
---|
293 | // |
---|
294 | // ... (* further vectors *) |
---|
295 | |
---|
296 | #endif |
---|