source: git/IntegerProgramming/IP_algorithms.h @ f8084c

spielwiese
Last change on this file since f8084c was 194c2e7, checked in by Hans Schönemann <hannes@…>, 14 years ago
short -> int git-svn-id: file:///usr/local/Singular/svn/trunk@12539 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 12.0 KB
Line 
1// IP_algorithms.h
2
3#ifndef IP_ALGORITHMS_H
4#define IP_ALGORITHMS_H
5
6#include "ideal.h"
7
8typedef char* INPUT_FILE;
9typedef 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
50extern int Conti_Traverso(INPUT_FILE MATRIX,
51                          const int& version=1,
52                          const int& 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
59extern int Positive_Conti_Traverso(INPUT_FILE MATRIX,
60                                   const int& version=1,
61                                   const int& 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
67extern int Elim_Conti_Traverso(INPUT_FILE MATRIX,
68                               const int& version=1,
69                               const int& 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
76extern int Pottier(INPUT_FILE MATRIX,
77                   const int& version=1,
78                   const int& 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
84extern int Hosten_Sturmfels(INPUT_FILE MATRIX,
85                            const int& version=1,
86                            const int& 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
93extern int DiBiase_Urbanke(INPUT_FILE MATRIX,
94                           const int& version=1,
95                           const int& 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
101extern int Bigatti_LaScala_Robbiano(INPUT_FILE MATRIX,
102                                    const int& version=1,
103                                    const int& 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
117extern 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
129extern int change_cost(INPUT_FILE GROEBNER, INPUT_FILE NEW_COST,
130                       const int& version=1,
131                       const int& 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
Note: See TracBrowser for help on using the repository browser.