source: git/IntegerProgramming/globals.h @ 76f3a18

spielwiese
Last change on this file since 76f3a18 was 76f3a18, checked in by Oleksandr Motsak <motsak@…>, 12 years ago
added building binary programs from IntegerProgramming: toric_ideal, solve_IP, change_cost, gen_test and LLL ADD: IntegerProgramming is a SUBPACKAGE of the main package CHG: removing obsolette stuff (gccversion.sh) CHG: use gmp.h instead of si_gmp.h! TODO: install help files properly (only distributed for now)
  • Property mode set to 100644
File size: 8.1 KB
Line 
1// globals.h
2
3// In this file
4// - some facilities as the g++ input/output routines are included,
5// - the general data type can be chosen (the people of Singular do not like
6//   templates),
7// - some makros are defined for an easier handling of the program,
8// - some flags and constants can be set to observe the behaviour of the
9//   algorithms when using different strategies.
10
11#ifndef GLOBALS_H
12#define GLOBALS_H
13// Include facilities needed by several files:
14
15// the following is not good! TODO: move to all including sources...
16#include "config.h"
17
18#include <stdio.h>
19#ifndef HAVE_IOSTREAM_H
20#include <iostream>
21#include <fstream>
22#include <iomanip>
23#include <limits>
24#else
25#include <iostream.h>
26#include <fstream.h>
27#include <iomanip.h>
28#include <limits.h>
29#endif
30#include <stddef.h>
31#include <stdlib.h>
32#include <math.h>
33#include <string.h>
34
35using namespace std;
36
37// Include a BigInt class from a foreign library:
38// This is needed by the LLL algorithm. If no such class is included,
39// it computes with long ints; this results in overflows and unexpected
40// behaviour even when computing with relatively small instances.
41
42#define GMP
43
44#ifdef GMP
45
46#include "BigInt.h"
47
48#else   // GMP
49
50typedef long BigInt;
51
52#endif // GMP
53
54// Define the general data type:
55// short seems to be sufficient for most practicable instances.
56
57typedef short Integer;
58// The general data type to deal with can be short, long or int...
59
60//#define _SHORT_
61// For an overflow control for thE result of the LLL algorithm, we have to
62// know the data type used.
63
64
65
66// Define a BOOLEAN data type etc. for an easy-to-read code:
67
68typedef char BOOLEAN;
69#define TRUE  1
70#define FALSE 0
71
72#define MAXIMUM(a,b) (a>b? a:b)
73
74#define INHOMOGENEOUS 0
75#define HOMOGENEOUS   1
76// For a more comfortable call of the term_ordering constructors.
77
78
79
80
81// Enumerate the algorithms:
82// The ideal constructor (builds an ideal from the input matrix) depends on
83// the algorithm. The constants are defined to make constructor calls easier
84// (you do not need to remember a number).
85
86#define CONTI_TRAVERSO           1
87#define POSITIVE_CONTI_TRAVERSO  2
88#define POTTIER                  3
89#define HOSTEN_STURMFELS         4
90#define DIBIASE_URBANKE          5
91#define BIGATTI_LASCALA_ROBBIANO 6
92
93
94
95
96// Enumerate the criteria to discard unnecessary S-pairs:
97// The constants are defined to allow an easier call of BuchbergerŽs algorithm
98// with different criteria. This algorithm takes as an argument a short int
99// which represents the combination of criteria to be used (with a default
100// combination if no argument is given).
101// The method to compute the argument for a certain combination is simple:
102// Simply add the constants that belong to criteria you want to use. As the
103// constants are chosen to be different powers of 2, each short int (in the
104// range of 0 to 31) gives a unique combination (cf. the read-write-execute
105// rights for files in UNIX systems).
106// EXAMPLE:
107// If you want to call BuchbergerŽs algorithm with the criterion "relatively
108// prime leading terms" and the second criterion for the ideal I, write:
109//
110//      I.reduced_Groebner_basis_1(REL_PRIMENESS + SECOND_CRITERION);
111// or
112//      I.reduced_Groebner_basis_1(17);
113//
114// The argument 0 means that no criteria are used, the argument 31 leads to
115// the use of all criteria.
116
117#define REL_PRIMENESS      1
118#define M_CRITERION        2
119#define F_CRITERION        4
120#define B_CRITERION        8
121#define SECOND_CRITERION  16
122
123// The names of tehse criteria are chosen according to the criteria
124// described in Gebauer/Moeller (except from the last).
125// The first one (relatively prime leading terms) is a local criterion
126// and the most effective.
127// The last four criteria are global ones involving searches over the
128// generator lists. But although the lcm-computations performed by these
129// checks are not much cheaper than a reduction, most of the criteria seem to
130// accelerate the computations.
131// REL_PRIMENESS should always be used.
132// The Gebauer/Moeller-criteria (M,F,B) seem to improve computation time in
133// the general case; Buchberger's second criterion seems to improve it in
134// more special cases (for example the transportation problem). They should
135// be switched on and off according to these results, but never be enabled
136// together; the overhead of too many criteria leads to a rather bad
137// performance in all cases.
138// The relatively primeness criterion is tested first because it
139// is very easy to check. The order of the Gebauer/Moeller-criteria does not
140// really affect computation. The relative order of the Gebauer/Moeller
141// criteria and the second criterion (if they are enabled together) has almost
142// the same effect as switching off the last criterion in this order.
143// There is no possibility to change the order in which the criteria are
144// tested without changing the program!
145
146
147
148
149// Enumerate the term orderings that can be used to refine the weight:
150// W_REV_LEX will give a term ordering in the classical sense if and only if
151// all weights are positive. It has been implemented because several
152// algorithms need a reverse lexicographical refinement. (Of course, these
153// algorithms control if they have a positive grading.)
154// A warning will be output when using W_REV_LEX in an insecure case.
155
156#define W_LEX          4
157#define W_REV_LEX      5
158#define W_DEG_LEX      6
159#define W_DEG_REV_LEX  7
160
161
162
163// Enumerate the term ordering used for the block of elimination variables:
164
165#define LEX          1
166#define DEG_LEX      2
167#define DEG_REV_LEX  3
168
169//////////////////////////////////////////////////////////////////////////////
170///////////////     TEST PARAMETER SECTION    ////////////////////////////////
171//////////////////////////////////////////////////////////////////////////////
172
173// Set flags concerning the basic operations and the course of Buchberger's
174// algorithm:
175
176#define SUPPORT_DRIVEN_METHODS
177// possibilities:
178// SUPPORT_DRIVEN_METHODS
179// NO_SUPPORT_DRIVEN_METHODS
180
181// This flag allows to switch of and on the use of the support vectors in
182// the binomial class; these are used to speed up tests for reducibility of
183// binomials, relative primeness etc.
184
185#define SUPPORT_DRIVEN_METHODS_EXTENDED
186// possibilities:
187// SUPPORT_DRIVEN_METHODS_EXTENDED
188// NO_SUPPORT_DRIVEN_METHODS_EXTENDED
189
190// This flag allows to switch of and on the extended use of the support
191// information. This includes the splitting of the ideal generators into
192// several lists according to their head support. This discards many
193// unnecessary tests for divisibility etc.
194// SUPPORT_DRIVEN_METHODS_EXTENDED should only be enabled when
195// SUPPORT_DRIVEN_METHODS is set, too! The combination
196// NO_SUPPORT_DRIVEN_METHODS and  SUPPORT_DRIVEN_METHODS_EXTENDED is quite
197// senseless and will only work if your compiler automatically initializes
198// integers to zero.
199
200const unsigned short List_Support_Variables=8;
201
202// This is the number of variables considered to create and maintain the
203// generator lists of an ideal if SUPPORT_DRIVEN_METHODS_EXTENDED is
204// enabled. As there are 2^List_Support_Variables lists, this number
205// should not be too big (to avoid the overhead of many empty lists).
206// The best number may depend on the problem size and structure...
207
208#define SUPPORT_VARIABLES_LAST
209// possibilities:
210// SUPPORT_VARIABLES_LAST
211// SUPPORT_VARIABLES_FIRST
212
213// This flag determines whether the first or the last variables are considered
214// by the support methods. So this setting will only affect the computation if
215// such methods are enabled.
216// The reason for the introduction of this flag is the following:
217// The Conti-Traverso algorithm for solving an integer program works in two
218// phases: Given an artificial solution in auxiliary variables, these
219// variables are first eliminated to get a feasible solution. The elimination
220// variables are for technical reasons always the last. In a second phase,
221// this solution is reduced to a minimal solution with respect to a given
222// term ordering.
223// If SUPPORT_VARIABLES_LAST is set, the first phase will probably take
224// less time as if SUPPORT_VARIABLES_FIRST is set. If one is only interested
225// in finding a feasible solution (not necessary  minimal),
226// SUPPORT_VARIABLES_LAST might be the better choice.
227
228#endif  // GLOBALS_H
229
Note: See TracBrowser for help on using the repository browser.