Frobby 0.9.5
OptimizeStrategy.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see http://www.gnu.org/licenses/.
16*/
17#include "stdinc.h"
18#include "OptimizeStrategy.h"
19
20#include "TermGrader.h"
21#include "Slice.h"
22
24 const SplitStrategy* splitStrategy,
25 bool reportAllSolutions,
26 BoundSetting boundSetting):
27 MsmStrategy(this, splitStrategy),
28 _grader(grader),
29 _maxSolutions(grader.getVarCount()),
30 _reportAllSolutions(reportAllSolutions),
31 _boundSetting(boundSetting),
32
33 _simplify_tmpDominator(grader.getVarCount()),
34 _simplify_tmpOldDominator(grader.getVarCount()),
35 _simplify_tmpOldDivisor(grader.getVarCount()),
36 _boundSimplify_tmpPivot(grader.getVarCount()) {
37
39}
40
42 return _maxSolutions;
43}
44
47 return _maxValue;
48}
49
51 ASSERT(!use);
52}
53
56}
57
59 mpz_class& degree = _consume_tmpDegree;
60
61 _grader.getDegree(term, degree);
62 if (_maxSolutions.isZeroIdeal() || degree > _maxValueToBeat) {
63 if (_reportAllSolutions && degree == _maxValue)
65 else {
66 _maxValue = degree;
70 }
71 }
72}
73
75}
76
78 MsmStrategy::getPivot(pivot, slice, _grader);
79}
80
82 ASSERT(slice.getVarCount() == getVarCount());
83 if (slice.getIdeal().getGeneratorCount() == 0)
84 return false;
85
87 return MsmStrategy::simplify(slice);
88
89 Term& dominator = _simplify_tmpDominator;
90 Term& oldDominator = _simplify_tmpOldDominator;
91 Term& oldDivisor = _simplify_tmpOldDivisor;
92
93 ASSERT(dominator.getVarCount() == getVarCount());
94 ASSERT(oldDominator.getVarCount() == getVarCount());
95
96 if (!getDominator(slice, dominator))
97 return true; // Slice is now a base case.
98
99 bool changedSlice = false;
100 for (bool firstLoop = true; true ; firstLoop = false) {
101 // It is an invariant at this point that dominator is what is
102 // gotten by calling getDominator(slice, dominator).
103
104 // Obtain upper bound on the degree of elements of msm(I).
105 mpz_class& upperBound = _simplify_tmpUpperBound;
106 _grader.getUpperBound(slice.getMultiply(), dominator, upperBound);
107
108 // Check if improvement on the best value found so far is possible
109 // from this slice according to the bound. If it is not, then
110 // there is no point in looking further at this slice.
111 if (upperBound <= _maxValueToBeat) {
112 slice.clearIdealAndSubtract();
113 return true;
114 }
115
117 // This achieves the sequence 1) check bound, 2) simplify and
118 // then 3) check bound again if changed. As checking the bound
119 // takes much less time than simplifying, this is the best way
120 // to do it. I haven't actually benchmarked that claim, though.
121 bool changed = MsmStrategy::simplify(slice);
122 if (firstLoop && changed) {
123 changedSlice = true;
124 continue;
125 }
126 return changedSlice || changed;
127 }
129
130 oldDivisor = slice.getMultiply();
131 oldDominator = dominator;
132
133 if (boundSimplify(slice, dominator, upperBound)) {
134 changedSlice = true;
135 if (!getDominator(slice, dominator))
136 return true; // Slice is now a base case.
138 (oldDivisor, oldDominator, slice.getMultiply(), dominator))
139 continue; // Iterate using new divisor/dominator.
140 }
141
142 // Simplify the slice in the usual non-bound way.
143 if (MsmStrategy::simplify(slice)) {
144 changedSlice = true;
145 if (!getDominator(slice, dominator))
146 return true; // Slice is now a base case.
148 (oldDivisor, oldDominator, slice.getMultiply(), dominator))
149 continue; // Iterate using new divisor/dominator.
150 }
151
152 // Slice is now a fixed point of the operations above.
153 break;
154 }
155
156 return changedSlice;
157}
158
160(const Term& oldDivisor, const Term& oldDominator,
161 const Term& newDivisor, const Term& newDominator) const {
162 ASSERT(oldDivisor.getVarCount() == getVarCount());
163 ASSERT(newDivisor.getVarCount() == getVarCount());
164 ASSERT(oldDominator.getVarCount() == getVarCount());
165 ASSERT(newDominator.getVarCount() == getVarCount());
166
167 ASSERT(oldDivisor.divides(newDivisor));
168 ASSERT(newDivisor.divides(newDominator));
169 ASSERT(newDominator.divides(oldDominator));
170
171 for (size_t var = 0; var < getVarCount(); ++var) {
172 if (oldDivisor[var] == newDivisor[var] &&
173 oldDominator[var] == newDominator[var])
174 continue;
175
176 int sign = _grader.getGradeSign(var);
177 if (sign < 0) {
178 if (newDivisor[var] > oldDivisor[var])
179 return true; // Case 1 from the documentation.
180
181 ASSERT(newDivisor[var] == oldDivisor[var]);
182 ASSERT(newDominator[var] < oldDominator[var]);
183 if (oldDominator[var] == _grader.getMaxExponent(var))
184
185 return true; // Case 2 from the documentation.
186 } else if (sign > 0) {
187 if (newDominator[var] < oldDominator[var]) {
188 // Case 3 from the documentation.
189 return newDominator[var] < _grader.getMaxExponent(var) - 1;
190 } else {
191 ASSERT(newDominator[var] == oldDominator[var]);
192 ASSERT(newDivisor[var] > oldDivisor[var]);
193 if (newDivisor[var] == newDominator[var] &&
194 newDominator[var] == _grader.getMaxExponent(var))
195 return true; // Case 4 from the documentation.
196 }
197 }
198 }
199
200 return false;
201}
202
204(Slice& slice,
205 const Term& dominator,
206 const mpz_class& upperBound) {
207
209
210 if (getInnerSimplify(slice.getMultiply(), dominator, upperBound, pivot))
211 slice.innerSlice(pivot);
212 else if (getOuterSimplify(slice.getMultiply(), dominator, upperBound, pivot))
213 slice.outerSlice(pivot);
214 else
215 return false;
216
217 return true;
218}
219
221(const Term& divisor,
222 const Term& dominator,
223 const mpz_class& upperBound,
224 Term& pivot) {
225
226 bool simplifiedAny = false;
227 for (size_t var = 0; var < getVarCount(); ++var) {
228 ASSERT(_grader.getGrade(var, 0) ==
230 ASSERT(divisor[var] <= dominator[var]);
231 pivot[var] = 0;
232
233 if (divisor[var] == dominator[var])
234 continue;
235
236 int sign = _grader.getGradeSign(var);
237 if (sign > 0) {
238 Exponent B;
239 if (dominator[var] != _grader.getMaxExponent(var))
240 B = dominator[var];
241 else {
242 B = dominator[var] - 1;
243 if (divisor[var] == B)
244 continue;
245 }
246
247 _tmpC = _maxValueToBeat - upperBound;
248 _tmpC += _grader.getGrade(var, B);
249
250 Exponent tPrime;
251 bool foundNonImproving = _grader.getMaxIndexLessThan
252 (var, divisor[var], B - 1, tPrime, _tmpC);
253
254 if (foundNonImproving) {
255 simplifiedAny = true;
256 pivot[var] = tPrime - divisor[var] + 1;
257 ASSERT(pivot[var] > 0);
258 }
259 } else if (sign < 0) {
260 if (dominator[var] != _grader.getMaxExponent(var))
261 continue;
262 _tmpC = upperBound - _grader.getGrade(var, dominator[var]);
263 _tmpC += _grader.getGrade(var, divisor[var]);
264
265 if (_tmpC <= _maxValueToBeat) {
266 simplifiedAny = true;
267 pivot[var] = dominator[var] - divisor[var];
268 ASSERT(pivot[var] > 0);
269 }
270 }
271 }
272
273 ASSERT(simplifiedAny == !pivot.isIdentity());
274 return simplifiedAny;
275}
276
278(const Term& divisor,
279 const Term& dominator,
280 const mpz_class& upperBound,
281 Term& pivot) {
282
283 for (size_t var = 0; var < getVarCount(); ++var) {
284 ASSERT(_grader.getGrade(var, 0) ==
286 ASSERT(divisor[var] <= dominator[var]);
287 if (divisor[var] == dominator[var])
288 continue;
289
290 int sign = _grader.getGradeSign(var);
291 if (sign < 0) {
292 if (dominator[var] == _grader.getMaxExponent(var))
293 continue;
294
295 _tmpC = _maxValueToBeat - upperBound;
296 _tmpC += _grader.getGrade(var, divisor[var]);
297
298 Exponent tPrime;
299 bool foundNonImproving = _grader.getMinIndexLessThan
300 (var, divisor[var] + 1, dominator[var], tPrime, _tmpC);
301
302 if (foundNonImproving) {
303 pivot.setToIdentity();
304 pivot[var] = tPrime - divisor[var];
305 ASSERT(pivot[var] > 0);
306
307 return true;
308 }
309 } else if (sign > 0) {
310 if (dominator[var] != _grader.getMaxExponent(var))
311 continue;
312
313 _tmpC = upperBound - _grader.getGrade(var, dominator[var] - 1);
314 _tmpC += _grader.getGrade(var, dominator[var]);
315
316 if (_tmpC <= _maxValueToBeat) {
317 pivot.setToIdentity();
318 pivot[var] = dominator[var] - divisor[var];
319 ASSERT(pivot[var] > 0);
320
321 return true;
322 }
323 }
324 }
325
326 return false;
327}
328
329bool OptimizeStrategy::getDominator(Slice& slice, Term& dominator) {
330 ASSERT(dominator.getVarCount() == slice.getVarCount());
331
332 // The dominator is pi(lcm(min I)), where I is the ideal represented
333 // by the slice, and pi decrements each exponent by one.
334
335 const Term& multiply = slice.getMultiply();
336 const Term& lcm = slice.getLcm();
337
338 for (size_t var = 0; var < dominator.getVarCount(); ++var) {
339 if (lcm[var] == 0) {
340 slice.clearIdealAndSubtract();
341 return false;
342 }
343
344 dominator[var] = multiply[var] + lcm[var] - 1;
345 }
346
347 return true;
348}
349
351 return _grader.getVarCount();
352}
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
bool isZeroIdeal() const
Definition: Ideal.cpp:86
size_t getGeneratorCount() const
Definition: Ideal.h:57
void clear()
Definition: Ideal.cpp:641
void insert(const Exponent *term)
Definition: Ideal.cpp:455
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
bool getOuterSimplify(const Term &divisor, const Term &dominator, const mpz_class &upperBound, Term &pivot)
Find an inner slice that is non-improving, allowing us to replace the current slice with the outer sl...
Term _simplify_tmpOldDivisor
Temporary variable used in simplify.
const TermGrader & _grader
We use _grader to assign values to solutions.
BoundSetting
The values of BoundSetting indicate how to use the bound.
@ DoNotUseBound
Make no use of the bound.
@ UseBoundToEliminateAndSimplify
Eliminate non-improving slices and simplify slices by trying to generate non-improving slices that ar...
@ UseBoundToEliminate
Eliminate non-improving slices, achieving a branch-and-bound algorithm in place of the usual backtrac...
const Ideal & getMaximalSolutions()
Returns one of or all of the msm's with optimal value found so far, depending on the value of reportA...
OptimizeStrategy(TermGrader &grader, const SplitStrategy *splitStrategy, bool reportAllSolutions, BoundSetting boundSetting)
Construct an OptimizeStrategy.
bool boundSimplify(Slice &slice, const Term &dominator, const mpz_class &upperBound)
This method simplifies a slice based on generating non-improving outer and inner slices.
Ideal _maxSolutions
Stores the optimal solutions found so far, according to the best value found so far.
bool getDominator(Slice &slice, Term &dominator)
Sets dominator to be a term dominating every element of the content of slice.
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
Term _boundSimplify_tmpPivot
Temporary variable used in simplify.
const mpz_class & getMaximalValue()
The optimal value associated to all entries from getMaximalSolutions().
mpz_class _simplify_tmpUpperBound
Temporary variable used in simplify.
mpz_class _maxValue
The best value of any solution found so far.
virtual void consume(const Term &term)
Consume a term.
Term _simplify_tmpOldDominator
Temporary variable used in simplify.
Term _simplify_tmpDominator
Temporary variable used in simplify.
bool _reportAllSolutions
Indicates whether to compute all optimal solutions, as opposed to computing just one (when there are ...
bool changedInWayRelevantToBound(const Term &oldDivisor, const Term &oldDominator, const Term &newDivisor, const Term &newDominator) const
Returns true if iterating bound-based simplification might do something.
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
virtual void setUseIndependence(bool use)
Independence splits are not supported, so calling this method does nothing.
size_t getVarCount() const
The number of varibles this object was initialized with.
mpz_class _maxValueToBeat
Is equal to _maxValue minus _reportAllSolutions, except when no solution has been found so far,...
virtual bool simplify(Slice &slice)
This method calls MsmStrategy::simplify to perform the usual simplification of slice,...
mpz_class _tmpC
Temporary variable used in getInnerSimplify and getOuterSimplify.
BoundSetting _boundSetting
Indicates how to use the bound.
mpz_class _consume_tmpDegree
Temporary variable used in consume.
bool getInnerSimplify(const Term &divisor, const Term &dominator, const mpz_class &upperBound, Term &pivot)
Find an outer slice that is non-improving, allowing us to replace the current slice with the inner sl...
virtual void setUseIndependence(bool use)
This method should only be called before calling run().
virtual bool simplify(Slice &slice)
Simplifies slice and returns true if it changed.
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition: Slice.h:77
virtual bool innerSlice(const Term &pivot)
Sets this object to the inner slice according to pivot.
Definition: Slice.cpp:110
virtual void outerSlice(const Term &pivot)
Sets this object to the outer slice according to pivot.
Definition: Slice.cpp:132
Term & getMultiply()
Returns for a slice .
Definition: Slice.h:113
void clearIdealAndSubtract()
Clears getIdeal() and getSubtract() and does not change getMultiply().
Definition: Slice.cpp:99
const Ideal & getIdeal() const
Returns for a slice .
Definition: Slice.h:104
const Term & getLcm() const
Returns the least common multiple of the generators of getIdeal().
Definition: Slice.cpp:52
size_t getVarCount() const
Returns the number of variables in the ambient ring.
Definition: Slice.h:96
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition: SplitStrategy.h:30
A TermGrader assigns a value, the degree, to each monomial.
Definition: TermGrader.h:27
mpz_class getDegree(const Term &term) const
Returns the degree of term.
Definition: TermGrader.cpp:47
size_t getVarCount() const
Definition: TermGrader.cpp:287
Exponent getMaxExponent(size_t var) const
Definition: TermGrader.cpp:282
bool getMaxIndexLessThan(size_t var, Exponent from, Exponent to, Exponent &index, const mpz_class &maxDegree) const
Finds maximal index in [from, to] to such that degree(t) <= maxDegree.
Definition: TermGrader.cpp:153
void getUpperBound(const Term &divisor, const Term &dominator, mpz_class &bound) const
Assigns to bound the degree of the largest term v such that divisor divides v and v divides dominator...
Definition: TermGrader.cpp:69
bool getMinIndexLessThan(size_t var, Exponent from, Exponent to, Exponent &index, const mpz_class &maxDegree) const
Finds minimal index in [from, to] to such that degree(t) <= maxDegree.
Definition: TermGrader.cpp:126
int getGradeSign(size_t var) const
Returns 1 if the grade strictly increases with the exponent of var, returns -1 if it strictly decreas...
Definition: TermGrader.cpp:302
const mpz_class & getGrade(size_t var, Exponent exponent) const
Definition: TermGrader.cpp:275
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
size_t getVarCount() const
Definition: Term.h:85
static bool isIdentity(const Exponent *a, size_t varCount)
Returns whether a is 1, i.e. whether all entries of a are 0.
Definition: Term.h:316
static bool divides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a divides b.
Definition: Term.h:152
static void setToIdentity(Exponent *res, size_t varCount)
Set res equal to , i.e. set each entry of res equal to 0.
Definition: Term.h:304
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
unsigned int Exponent
Definition: stdinc.h:89
#define ASSERT(X)
Definition: stdinc.h:86