Go to the documentation of this file.
25 bool reportAllSolutions,
29 _maxSolutions(grader.getVarCount()),
30 _reportAllSolutions(reportAllSolutions),
31 _boundSetting(boundSetting),
33 _simplify_tmpDominator(grader.getVarCount()),
34 _simplify_tmpOldDominator(grader.getVarCount()),
35 _simplify_tmpOldDivisor(grader.getVarCount()),
36 _boundSimplify_tmpPivot(grader.getVarCount()) {
99 bool changedSlice =
false;
100 for (
bool firstLoop =
true; true ; firstLoop =
false) {
122 if (firstLoop && changed) {
126 return changedSlice || changed;
131 oldDominator = dominator;
138 (oldDivisor, oldDominator, slice.
getMultiply(), dominator))
148 (oldDivisor, oldDominator, slice.
getMultiply(), dominator))
161 const Term& newDivisor,
const Term& newDominator)
const {
171 for (
size_t var = 0; var < getVarCount(); ++var) {
172 if (oldDivisor[var] == newDivisor[var] &&
173 oldDominator[var] == newDominator[var])
176 int sign = _grader.getGradeSign(var);
178 if (newDivisor[var] > oldDivisor[var])
181 ASSERT(newDivisor[var] == oldDivisor[var]);
182 ASSERT(newDominator[var] < oldDominator[var]);
186 }
else if (sign > 0) {
187 if (newDominator[var] < oldDominator[var]) {
191 ASSERT(newDominator[var] == oldDominator[var]);
192 ASSERT(newDivisor[var] > oldDivisor[var]);
193 if (newDivisor[var] == newDominator[var] &&
205 const Term& dominator,
206 const mpz_class& upperBound) {
208 Term& pivot = _boundSimplify_tmpPivot;
210 if (getInnerSimplify(slice.
getMultiply(), dominator, upperBound, pivot))
212 else if (getOuterSimplify(slice.
getMultiply(), dominator, upperBound, pivot))
222 const Term& dominator,
223 const mpz_class& upperBound,
226 bool simplifiedAny =
false;
227 for (
size_t var = 0; var < getVarCount(); ++var) {
228 ASSERT(_grader.getGrade(var, 0) ==
229 _grader.getGrade(var, _grader.getMaxExponent(var)));
230 ASSERT(divisor[var] <= dominator[var]);
233 if (divisor[var] == dominator[var])
236 int sign = _grader.getGradeSign(var);
242 B = dominator[var] - 1;
243 if (divisor[var] == B)
247 _tmpC = _maxValueToBeat - upperBound;
248 _tmpC += _grader.getGrade(var, B);
251 bool foundNonImproving = _grader.getMaxIndexLessThan
252 (var, divisor[var], B - 1, tPrime, _tmpC);
254 if (foundNonImproving) {
255 simplifiedAny =
true;
256 pivot[var] = tPrime - divisor[var] + 1;
259 }
else if (sign < 0) {
262 _tmpC = upperBound - _grader.getGrade(var, dominator[var]);
263 _tmpC += _grader.getGrade(var, divisor[var]);
265 if (_tmpC <= _maxValueToBeat) {
266 simplifiedAny =
true;
267 pivot[var] = dominator[var] - divisor[var];
274 return simplifiedAny;
279 const Term& dominator,
280 const mpz_class& upperBound,
283 for (
size_t var = 0; var < getVarCount(); ++var) {
284 ASSERT(_grader.getGrade(var, 0) ==
285 _grader.getGrade(var, _grader.getMaxExponent(var)));
286 ASSERT(divisor[var] <= dominator[var]);
287 if (divisor[var] == dominator[var])
290 int sign = _grader.getGradeSign(var);
295 _tmpC = _maxValueToBeat - upperBound;
296 _tmpC += _grader.getGrade(var, divisor[var]);
299 bool foundNonImproving = _grader.getMinIndexLessThan
300 (var, divisor[var] + 1, dominator[var], tPrime, _tmpC);
302 if (foundNonImproving) {
304 pivot[var] = tPrime - divisor[var];
309 }
else if (sign > 0) {
313 _tmpC = upperBound - _grader.getGrade(var, dominator[var] - 1);
314 _tmpC += _grader.getGrade(var, dominator[var]);
316 if (_tmpC <= _maxValueToBeat) {
318 pivot[var] = dominator[var] - divisor[var];
338 for (
size_t var = 0; var < dominator.
getVarCount(); ++var) {
344 dominator[var] = multiply[var] +
lcm[var] - 1;
const TermGrader & _grader
We use _grader to assign values to solutions.
static bool isIdentity(const Exponent *a, size_t varCount)
Returns whether a is 1, i.e. whether all entries of a are 0.
void clearIdealAndSubtract()
Clears getIdeal() and getSubtract() and does not change getMultiply().
virtual void setUseIndependence(bool use)
This method should only be called before calling run().
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...
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
virtual void outerSlice(const Term &pivot)
Sets this object to the outer slice according to pivot.
mpz_class _maxValue
The best value of any solution found so far.
mpz_class _maxValueToBeat
Is equal to _maxValue minus _reportAllSolutions, except when no solution has been found so far,...
virtual bool innerSlice(const Term &pivot)
Sets this object to the inner slice according to pivot.
Term _simplify_tmpDominator
Temporary variable used in simplify.
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...
size_t getVarCount() const
Returns the number of variables in the ambient ring.
size_t getVarCount() const
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
const Term & getLcm() const
Returns the least common multiple of the generators of getIdeal().
BoundSetting
The values of BoundSetting indicate how to use the bound.
bool _reportAllSolutions
Indicates whether to compute all optimal solutions, as opposed to computing just one (when there are ...
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.
size_t getGeneratorCount() const
bool getDominator(Slice &slice, Term &dominator)
Sets dominator to be a term dominating every element of the content of slice.
Term _simplify_tmpOldDominator
Temporary variable used in simplify.
This class represents a slice, which is the central data structure of the Slice Algorithm.
Term _simplify_tmpOldDivisor
Temporary variable used in simplify.
@ DoNotUseBound
Make no use of the bound.
Term & getMultiply()
Returns for a slice .
Term represents a product of variables which does not include a coefficient.
const Ideal & getIdeal() const
Returns for a slice .
virtual void setUseIndependence(bool use)
Independence splits are not supported, so calling this method does nothing.
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 getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
const Ideal & getMaximalSolutions()
Returns one of or all of the msm's with optimal value found so far, depending on the value of reportA...
@ UseBoundToEliminateAndSimplify
Eliminate non-improving slices and simplify slices by trying to generate non-improving slices that ar...
mpz_class _consume_tmpDegree
Temporary variable used in consume.
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
static bool divides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a divides b.
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
virtual void consume(const Term &term)
Consume a term.
@ UseBoundToEliminate
Eliminate non-improving slices, achieving a branch-and-bound algorithm in place of the usual backtrac...
Represents a monomial ideal with int exponents.
size_t getVarCount() const
mpz_class getDegree(const Term &term) const
Returns the degree of term.
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
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.
const mpz_class & getMaximalValue()
The optimal value associated to all entries from getMaximalSolutions().
static void setToIdentity(Exponent *res, size_t varCount)
Set res equal to , i.e. set each entry of res equal to 0.
void insert(const Exponent *term)
Ideal _maxSolutions
Stores the optimal solutions found so far, according to the best value found so far.
A TermGrader assigns a value, the degree, to each monomial.
size_t getMaxExponent() const
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 bool simplify(Slice &slice)
This method calls MsmStrategy::simplify to perform the usual simplification of slice,...
OptimizeStrategy(TermGrader &grader, const SplitStrategy *splitStrategy, bool reportAllSolutions, BoundSetting boundSetting)
Construct an OptimizeStrategy.
mpz_class _simplify_tmpUpperBound
Temporary variable used in simplify.