Frobby  0.9.0
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 
58 void OptimizeStrategy::consume(const Term& term) {
59  mpz_class& degree = _consume_tmpDegree;
60 
61  _grader.getDegree(term, degree);
62  if (_maxSolutions.isZeroIdeal() || degree > _maxValueToBeat) {
63  if (_reportAllSolutions && degree == _maxValue)
64  _maxSolutions.insert(term);
65  else {
66  _maxValue = degree;
69  _maxSolutions.insert(term);
70  }
71  }
72 }
73 
75 }
76 
77 void OptimizeStrategy::getPivot(Term& pivot, Slice& slice) {
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 
208  Term& pivot = _boundSimplify_tmpPivot;
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 
329 bool 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 }
Term _simplify_tmpOldDominator
Temporary variable used in simplify.
void clearIdealAndSubtract()
Clears getIdeal() and getSubtract() and does not change getMultiply().
Definition: Slice.cpp:99
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
Eliminate non-improving slices, achieving a branch-and-bound algorithm in place of the usual backtrac...
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:308
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.
const Ideal & getMaximalSolutions()
Returns one of or all of the msm&#39;s with optimal value found so far, depending on the value of reportA...
size_t getVarCount() const
Definition: Term.h:85
size_t getVarCount() const
Returns the number of variables in the ambient ring.
Definition: Slice.h:96
virtual void setUseIndependence(bool use)
This method should only be called before calling run().
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition: SplitStrategy.h:30
Term _boundSimplify_tmpPivot
Temporary variable used in simplify.
mpz_class _consume_tmpDegree
Temporary variable used in consume.
const Term & getLcm() const
Returns the least common multiple of the generators of getIdeal().
Definition: Slice.cpp:52
virtual void outerSlice(const Term &pivot)
Sets this object to the outer slice according to pivot.
Definition: Slice.cpp:132
virtual bool innerSlice(const Term &pivot)
Sets this object to the inner slice according to pivot.
Definition: Slice.cpp:110
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition: Slice.h:77
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
Exponent getMaxExponent(size_t var) const
Definition: TermGrader.cpp:282
size_t getVarCount() const
Definition: TermGrader.cpp:287
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.
#define ASSERT(X)
Definition: stdinc.h:85
mpz_class getDegree(const Term &term) const
Returns the degree of term.
Definition: TermGrader.cpp:47
const mpz_class & getMaximalValue()
The optimal value associated to all entries from getMaximalSolutions().
virtual void consume(const Term &term)
Consume a term.
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
bool isZeroIdeal() const
Definition: Ideal.cpp:86
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...
A TermGrader assigns a value, the degree, to each monomial.
Definition: TermGrader.h:27
virtual bool simplify(Slice &slice)
This method calls MsmStrategy::simplify to perform the usual simplification of slice, which then occurs if and only if the usual simplification has been turned on.
Ideal _maxSolutions
Stores the optimal solutions found so far, according to the best value found so far.
OptimizeStrategy(TermGrader &grader, const SplitStrategy *splitStrategy, bool reportAllSolutions, BoundSetting boundSetting)
Construct an OptimizeStrategy.
Term & getMultiply()
Returns for a slice .
Definition: Slice.h:113
mpz_class _simplify_tmpUpperBound
Temporary variable used in simplify.
const TermGrader & _grader
We use _grader to assign values to solutions.
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
size_t getGeneratorCount() const
Definition: Ideal.h:57
Make no use of the bound.
mpz_class _maxValueToBeat
Is equal to _maxValue minus _reportAllSolutions, except when no solution has been found so far...
static bool divides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a divides b.
Definition: Term.h:144
BoundSetting _boundSetting
Indicates how to use the bound.
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_tmpDominator
Temporary variable used in simplify.
mpz_class _maxValue
The best value of any solution found so far.
const Ideal & getIdeal() const
Returns for a slice .
Definition: Slice.h:104
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
Eliminate non-improving slices and simplify slices by trying to generate non-improving slices that ar...
mpz_class _tmpC
Temporary variable used in getInnerSimplify and getOuterSimplify.
BoundSetting
The values of BoundSetting indicate how to use the bound.
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
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:296
bool _reportAllSolutions
Indicates whether to compute all optimal solutions, as opposed to computing just one (when there are ...
void clear()
Definition: Ideal.cpp:641
virtual bool simplify(Slice &slice)
Simplifies slice and returns true if it changed.
size_t getVarCount() const
The number of varibles this object was initialized with.
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
void insert(const Exponent *term)
Definition: Ideal.cpp:455
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
bool getDominator(Slice &slice, Term &dominator)
Sets dominator to be a term dominating every element of the content of slice.
Term _simplify_tmpOldDivisor
Temporary variable used in simplify.
unsigned int Exponent
Definition: stdinc.h:88
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
const mpz_class & getGrade(size_t var, Exponent exponent) const
Definition: TermGrader.cpp:275
virtual void setUseIndependence(bool use)
Independence splits are not supported, so calling this method does nothing.