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