source: git/IntegerProgramming/term_ordering.h @ 96ce32

spielwiese
Last change on this file since 96ce32 was 1a3778, checked in by Frédéric Chapoton <chapoton@…>, 18 months ago
fix some typos in IntegerProgramming
  • Property mode set to 100644
File size: 9.3 KB
Line 
1// term_ordering.h
2
3
4// Our IP-algorithms need two kinds of term orderings: a weighted term ordering
5// and a block ordering that eliminates some auxiliary variables. Both
6// are constructed from the input or for the specific requirements of the
7// algorithms. To allow an easy and flexible handling, the term ordering is
8// realized as a class.
9
10// Weight vectors for term orderings have to be nonnegative in most contexts.
11// But input vectors with negative components are not refused by the
12// constructors. This has the following two reasons:
13// - There is a more general notion of term ordering who does not claim
14//   the monomial 1 to be a (unique) minimal monomial. This allows negative
15//   weights.
16// - This class is written for the final purpose of integer programming.
17//   The linear objective function induces the term ordering and might also
18//   have negative components. Although the program actually cannot treat
19//   this case, there are ways to tackle it. In view of a possible later
20//   expansion of the program, the nonnegativity check is delegated to a
21//   separate function instead of doing it in the constructors.
22
23// For the same reasons as mentioned in the binomial class, frequently
24// used operations on Integer vectors do not perform range checks. Nor do
25// they check if an error has occurred (i.e. control the "error flag", see
26// below).
27// These are concretely the functions weight(...), compare_to_zero(...) and
28// compare(...).
29// All other routines perform argument checks (range, file format...).
30// This is only really important when reading from a file (as most other range
31// checks are already made by the routines calling these functions). But as
32// all these operations are executed only a few times in the course of our
33// algorithms, the checks do not slow down computation.
34
35#ifndef TERM_ORDERING_H
36#define TERM_ORDERING_H
37
38#include "globals.h"
39
40class binomial;
41
42class term_ordering
43{
44protected:
45
46  float *weight_vector;
47
48  short weighted_block_size;
49  // the number of weighted variables
50  // Also the "error flag", i.e. values <0 indicate an error:
51  // -1 indicates a "semantic" error (arguments out of range, for example a
52  //    negative number of variables);
53  // -2 indicates an error occurred when reading from a file.
54
55  short weighted_ordering;
56  // the term ordering refining the weight on the weighted variables
57  // possibilities: see in globals.h
58
59  short elimination_block_size;
60  // the number of elimination variables
61
62  short elimination_ordering;
63  // the term ordering on the elimination variables
64
65  BOOLEAN homogeneous;
66  // This flag is set to TRUE if the term ordering is thought of as a
67  // homogeneous one (i.e. the weighted part), else to FALSE. The standard
68  // setting is FALSE.
69  // The routine compare_to_zero is faster if the term ordering is homogeneous.
70  // It would be safer and more natural to take this flag as a member of
71  // the ideal class; this would, however, require many supplementary
72  // functions (homogeneous versions of existing functions) in the ideal and
73  // even in the binomial class.
74
75public:
76// constructors and destructor
77
78  term_ordering(const BOOLEAN& homogeneous=FALSE);
79  // Sets weighted_block_size and elimination_block_size to zero.
80  // With this default constructor, the term ordering can be taken as a member
81  // of another class (the ideal class in our case).
82
83  term_ordering(const short& number_of_weighted_variables,
84                const float* weights,
85                const short& _weighted_ordering,
86                const BOOLEAN& _homogeneous=FALSE);
87  // Initializes weight vector with weights,
88  // weighted_block_size with number_of_weighted_variables,
89  // the refining ordering as given in the argument
90  // and elimination_block_size with 0.
91
92  term_ordering(const short& number_of_weighted_variables,
93                const float* weights,
94                const short& _weighted_ordering,
95                const short& number_of_elimination_variables,
96                const short& _elimination_ordering,
97                const BOOLEAN& _homogeneous=FALSE);
98  // Initializes weight vector with weights,
99  // weighted_block_size with number_of_weighted_variables,
100  // the orderings as given in the arguments
101  // and elimination_block_size with _number_of_elimination_variables.
102
103  term_ordering(ifstream& input, const short& _weighted_ordering,
104                const BOOLEAN& _homogeneous=FALSE);
105  // Reads a weight vector from the input stream and converts it into a
106  // weighted term ordering (with the refining ordering given by the second
107  // argument).
108  // The input stream must have the following format:
109  //
110  //    size n of the weight vector (=weighted_block_size)
111  //    components 0..n-1 of the weight vector
112  //
113
114  term_ordering(const short& n, ifstream& input,
115                const short& _weighted_ordering,
116                const BOOLEAN& _homogeneous=FALSE);
117  // Reads a weight vector of size n from the input stream and converts it
118  // into a weighted term ordering (with the refining ordering given by the
119  // second argument).
120  // The input stream has the following format:
121  //
122  //    components 0..n-1 of the weight vector
123  //
124
125  term_ordering(const term_ordering&);
126  // copy-constructor
127
128
129  ~term_ordering();
130  // destructor
131
132// object properties
133
134  short number_of_weighted_variables() const;
135  // Returns weighted_block_size.
136
137  short weight_refinement() const;
138  // Returns weighted_ordering.
139
140  short number_of_elimination_variables() const;
141  // Returns elimination_block_size.
142
143  short elimination_refinement() const;
144  // Returns elimination_ordering.
145
146  BOOLEAN is_homogeneous() const;
147  // Returns homogeneous.
148
149  short error_status() const;
150  // Returns weighted_block_size if weighted_block_size<0, else 0
151  // (this is the "error flag").
152
153  BOOLEAN is_nonnegative() const;
154  // Returns TRUE iff all components of the weight vector are >=0.
155  // If this is not the case, Buchberger's algorithm will perhaps not
156  // terminate using the actual ordering, i.e. the ordering is no
157  // well ordering.
158
159  BOOLEAN is_positive() const;
160  // Returns TRUE ifs all components of the weight vector are >0.
161  // If this is not the case, this may lead to problems even if all weights
162  // are nonnegative: Zero weights do not give a well ordering in combination
163  // with a reverse lexicographical refinement.
164
165// frequently used comparison functions
166
167  double weight(const Integer* v) const;
168  // Returns the weight of an Integer vector v with respect to weight_vector,
169  // i.e. the scalar product of the two vectors.
170  // UNCHECKED PRECONDITION: v has weighted_block_size components.
171  // The return type is double to avoid overflows.
172
173  short compare_to_zero(const Integer* v) const;
174  // This function is used to determine a binomials's head with respect to the
175  // actual term ordering. The comparison of its two monomials is done
176  // according to the binomial data structure:
177  // Instead of comparing explicitly two monomials, the Integer vector
178  // corresponding to their difference is compared to the zero vector.
179  // The function returns
180  //          1, if v>0,
181  //             -1, if v<0,
182  //              0, if v=0
183  // UNCHECKED PRECONDITION:
184  // v has weighted_block_size + elimination_block_size components
185
186  short compare(const binomial& bin1, const binomial& bin2) const;
187  // Compares the given binomials by first comparing the heads, then in the
188  // case of equality the tails.
189  // UNCHECKED PRECONDITION: The exponent vectors of the binomials have
190  // already the correct sign, i.e. the positive part of a vector is really
191  // its head and not its tail.
192  // The function returns
193  //        -1 if bin1<bin2
194  //         0 if bin1=bin2
195  //         1 if bin1>bin2
196
197// operators and routines needed by the algorithms to manipulate the term
198// ordering
199
200  term_ordering& operator=(const term_ordering&);
201  // assignment operator with memory control
202
203  float operator[](const short& i) const;
204  // Returns weight_vector[i] (FLT_MAX if i is out of range).
205
206  term_ordering& convert_to_weighted_ordering();
207  // Sets elimination_block_size to 0.
208
209  term_ordering& convert_to_elimination_ordering
210  (const short& number_of_elimination_variables,
211   const short& _elimination_ordering);
212  // Sets elimination_block_size to number_of_elimination_variables
213  // and the ordering on the elimination variables as given in the argument.
214
215  term_ordering& append_weighted_variable(const float& weight);
216  // Appends the given weight to the weight vector (with memory control).
217
218  term_ordering& delete_last_weighted_variable();
219  // Deletes the last weighted variable (with memory control).
220
221  term_ordering& swap_weights(const short& i, const short& j);
222  // This function is used if two weighted variables must change their
223  // position (order) with respect to the refining ordering.
224
225// output
226
227  void print_weight_vector() const;
228  void print() const;
229  // Writes the term ordering to the standard output medium
230  // (only the weight vector or with supplementary information).
231
232  void print_weight_vector(FILE*) const;
233  void print(FILE*) const;
234  // Writes the term ordering to the referenced file
235  // which has to be opened for writing before.
236
237  void print_weight_vector(ofstream&) const;
238  void print(ofstream&) const;
239  // Writes the term ordering to the given ofstream.
240
241  void format_print_weight_vector(ofstream&) const;
242  // Writes the term ordering to the given ofstream in the format required
243  // by the IP-algorithms.
244
245};
246#endif  // TERM_ORDERING_H
Note: See TracBrowser for help on using the repository browser.