source: git/IntegerProgramming/globals.h @ f8084c

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