[6ba162] | 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 |
---|