OptimizeStrategy.cpp
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
*/
#include "stdinc.h"
#include "OptimizeStrategy.h"
#include "TermGrader.h"
#include "Slice.h"
OptimizeStrategy::OptimizeStrategy(TermGrader& grader,
const SplitStrategy* splitStrategy,
bool reportAllSolutions,
BoundSetting boundSetting):
MsmStrategy(this, splitStrategy),
_grader(grader),
_maxSolutions(grader.getVarCount()),
_reportAllSolutions(reportAllSolutions),
_boundSetting(boundSetting),
_simplify_tmpDominator(grader.getVarCount()),
_simplify_tmpOldDominator(grader.getVarCount()),
_simplify_tmpOldDivisor(grader.getVarCount()),
_boundSimplify_tmpPivot(grader.getVarCount()) {
MsmStrategy::setUseIndependence(false);
}
const Ideal& OptimizeStrategy::getMaximalSolutions() {
return _maxSolutions;
}
const mpz_class& OptimizeStrategy::getMaximalValue() {
ASSERT(!_maxSolutions.isZeroIdeal());
return _maxValue;
}
void OptimizeStrategy::setUseIndependence(bool use) {
ASSERT(!use);
}
void OptimizeStrategy::beginConsuming() {
_maxSolutions.clear();
}
void OptimizeStrategy::consume(const Term& term) {
mpz_class& degree = _consume_tmpDegree;
_grader.getDegree(term, degree);
if (_maxSolutions.isZeroIdeal() || degree > _maxValueToBeat) {
if (_reportAllSolutions && degree == _maxValue)
_maxSolutions.insert(term);
else {
_maxValue = degree;
_maxValueToBeat = degree - _reportAllSolutions;
_maxSolutions.clear();
_maxSolutions.insert(term);
}
}
}
void OptimizeStrategy::doneConsuming() {
}
void OptimizeStrategy::getPivot(Term& pivot, Slice& slice) {
MsmStrategy::getPivot(pivot, slice, _grader);
}
bool OptimizeStrategy::simplify(Slice& slice) {
ASSERT(slice.getVarCount() == getVarCount());
if (slice.getIdeal().getGeneratorCount() == 0)
return false;
if (_boundSetting == DoNotUseBound || _maxSolutions.isZeroIdeal())
return MsmStrategy::simplify(slice);
Term& dominator = _simplify_tmpDominator;
Term& oldDominator = _simplify_tmpOldDominator;
Term& oldDivisor = _simplify_tmpOldDivisor;
ASSERT(dominator.getVarCount() == getVarCount());
ASSERT(oldDominator.getVarCount() == getVarCount());
if (!getDominator(slice, dominator))
return true; // Slice is now a base case.
bool changedSlice = false;
for (bool firstLoop = true; true ; firstLoop = false) {
// It is an invariant at this point that dominator is what is
// gotten by calling getDominator(slice, dominator).
// Obtain upper bound on the degree of elements of msm(I).
mpz_class& upperBound = _simplify_tmpUpperBound;
_grader.getUpperBound(slice.getMultiply(), dominator, upperBound);
// Check if improvement on the best value found so far is possible
// from this slice according to the bound. If it is not, then
// there is no point in looking further at this slice.
if (upperBound <= _maxValueToBeat) {
slice.clearIdealAndSubtract();
return true;
}
if (_boundSetting == UseBoundToEliminate) {
// This achieves the sequence 1) check bound, 2) simplify and
// then 3) check bound again if changed. As checking the bound
// takes much less time than simplifying, this is the best way
// to do it. I haven't actually benchmarked that claim, though.
bool changed = MsmStrategy::simplify(slice);
if (firstLoop && changed) {
changedSlice = true;
continue;
}
return changedSlice || changed;
}
ASSERT(_boundSetting == UseBoundToEliminateAndSimplify);
oldDivisor = slice.getMultiply();
oldDominator = dominator;
if (boundSimplify(slice, dominator, upperBound)) {
changedSlice = true;
if (!getDominator(slice, dominator))
return true; // Slice is now a base case.
if (changedInWayRelevantToBound
(oldDivisor, oldDominator, slice.getMultiply(), dominator))
continue; // Iterate using new divisor/dominator.
}
// Simplify the slice in the usual non-bound way.
if (MsmStrategy::simplify(slice)) {
changedSlice = true;
if (!getDominator(slice, dominator))
return true; // Slice is now a base case.
if (changedInWayRelevantToBound
(oldDivisor, oldDominator, slice.getMultiply(), dominator))
continue; // Iterate using new divisor/dominator.
}
// Slice is now a fixed point of the operations above.
break;
}
return changedSlice;
}
bool OptimizeStrategy::changedInWayRelevantToBound
(const Term& oldDivisor, const Term& oldDominator,
const Term& newDivisor, const Term& newDominator) const {
ASSERT(oldDivisor.getVarCount() == getVarCount());
ASSERT(newDivisor.getVarCount() == getVarCount());
ASSERT(oldDominator.getVarCount() == getVarCount());
ASSERT(newDominator.getVarCount() == getVarCount());
ASSERT(oldDivisor.divides(newDivisor));
ASSERT(newDivisor.divides(newDominator));
ASSERT(newDominator.divides(oldDominator));
for (size_t var = 0; var < getVarCount(); ++var) {
if (oldDivisor[var] == newDivisor[var] &&
oldDominator[var] == newDominator[var])
continue;
int sign = _grader.getGradeSign(var);
if (sign < 0) {
if (newDivisor[var] > oldDivisor[var])
return true; // Case 1 from the documentation.
ASSERT(newDivisor[var] == oldDivisor[var]);
ASSERT(newDominator[var] < oldDominator[var]);
if (oldDominator[var] == _grader.getMaxExponent(var))
return true; // Case 2 from the documentation.
} else if (sign > 0) {
if (newDominator[var] < oldDominator[var]) {
// Case 3 from the documentation.
return newDominator[var] < _grader.getMaxExponent(var) - 1;
} else {
ASSERT(newDominator[var] == oldDominator[var]);
ASSERT(newDivisor[var] > oldDivisor[var]);
if (newDivisor[var] == newDominator[var] &&
newDominator[var] == _grader.getMaxExponent(var))
return true; // Case 4 from the documentation.
}
}
}
return false;
}
bool OptimizeStrategy::boundSimplify
(Slice& slice,
const Term& dominator,
const mpz_class& upperBound) {
Term& pivot = _boundSimplify_tmpPivot;
if (getInnerSimplify(slice.getMultiply(), dominator, upperBound, pivot))
slice.innerSlice(pivot);
else if (getOuterSimplify(slice.getMultiply(), dominator, upperBound, pivot))
slice.outerSlice(pivot);
else
return false;
return true;
}
bool OptimizeStrategy::getInnerSimplify
(const Term& divisor,
const Term& dominator,
const mpz_class& upperBound,
Term& pivot) {
bool simplifiedAny = false;
for (size_t var = 0; var < getVarCount(); ++var) {
ASSERT(_grader.getGrade(var, 0) ==
_grader.getGrade(var, _grader.getMaxExponent(var)));
ASSERT(divisor[var] <= dominator[var]);
pivot[var] = 0;
if (divisor[var] == dominator[var])
continue;
int sign = _grader.getGradeSign(var);
if (sign > 0) {
Exponent B;
if (dominator[var] != _grader.getMaxExponent(var))
B = dominator[var];
else {
B = dominator[var] - 1;
if (divisor[var] == B)
continue;
}
_tmpC = _maxValueToBeat - upperBound;
_tmpC += _grader.getGrade(var, B);
Exponent tPrime;
bool foundNonImproving = _grader.getMaxIndexLessThan
(var, divisor[var], B - 1, tPrime, _tmpC);
if (foundNonImproving) {
simplifiedAny = true;
pivot[var] = tPrime - divisor[var] + 1;
ASSERT(pivot[var] > 0);
}
} else if (sign < 0) {
if (dominator[var] != _grader.getMaxExponent(var))
continue;
_tmpC = upperBound - _grader.getGrade(var, dominator[var]);
_tmpC += _grader.getGrade(var, divisor[var]);
if (_tmpC <= _maxValueToBeat) {
simplifiedAny = true;
pivot[var] = dominator[var] - divisor[var];
ASSERT(pivot[var] > 0);
}
}
}
ASSERT(simplifiedAny == !pivot.isIdentity());
return simplifiedAny;
}
bool OptimizeStrategy::getOuterSimplify
(const Term& divisor,
const Term& dominator,
const mpz_class& upperBound,
Term& pivot) {
for (size_t var = 0; var < getVarCount(); ++var) {
ASSERT(_grader.getGrade(var, 0) ==
_grader.getGrade(var, _grader.getMaxExponent(var)));
ASSERT(divisor[var] <= dominator[var]);
if (divisor[var] == dominator[var])
continue;
int sign = _grader.getGradeSign(var);
if (sign < 0) {
if (dominator[var] == _grader.getMaxExponent(var))
continue;
_tmpC = _maxValueToBeat - upperBound;
_tmpC += _grader.getGrade(var, divisor[var]);
Exponent tPrime;
bool foundNonImproving = _grader.getMinIndexLessThan
(var, divisor[var] + 1, dominator[var], tPrime, _tmpC);
if (foundNonImproving) {
pivot.setToIdentity();
pivot[var] = tPrime - divisor[var];
ASSERT(pivot[var] > 0);
return true;
}
} else if (sign > 0) {
if (dominator[var] != _grader.getMaxExponent(var))
continue;
_tmpC = upperBound - _grader.getGrade(var, dominator[var] - 1);
_tmpC += _grader.getGrade(var, dominator[var]);
if (_tmpC <= _maxValueToBeat) {
pivot.setToIdentity();
pivot[var] = dominator[var] - divisor[var];
ASSERT(pivot[var] > 0);
return true;
}
}
}
return false;
}
bool OptimizeStrategy::getDominator(Slice& slice, Term& dominator) {
ASSERT(dominator.getVarCount() == slice.getVarCount());
// The dominator is pi(lcm(min I)), where I is the ideal represented
// by the slice, and pi decrements each exponent by one.
const Term& multiply = slice.getMultiply();
const Term& lcm = slice.getLcm();
for (size_t var = 0; var < dominator.getVarCount(); ++var) {
if (lcm[var] == 0) {
slice.clearIdealAndSubtract();
return false;
}
dominator[var] = multiply[var] + lcm[var] - 1;
}
return true;
}
size_t OptimizeStrategy::getVarCount() const {
return _grader.getVarCount();
}
OptimizeStrategy.h
Slice.h
TermGrader.h
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Ideal::getGeneratorCount
size_t getGeneratorCount() const
Definition Ideal.h:57
MsmStrategy::getPivot
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
Definition MsmStrategy.cpp:285
MsmStrategy::MsmStrategy
MsmStrategy(TermConsumer *consumer, const SplitStrategy *splitStrategy)
Definition MsmStrategy.cpp:28
OptimizeStrategy::getOuterSimplify
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...
Definition OptimizeStrategy.cpp:278
OptimizeStrategy::_simplify_tmpOldDivisor
Term _simplify_tmpOldDivisor
Temporary variable used in simplify.
Definition OptimizeStrategy.h:399
OptimizeStrategy::_grader
const TermGrader & _grader
We use _grader to assign values to solutions.
Definition OptimizeStrategy.h:342
OptimizeStrategy::BoundSetting
BoundSetting
The values of BoundSetting indicate how to use the bound.
Definition OptimizeStrategy.h:46
OptimizeStrategy::DoNotUseBound
@ DoNotUseBound
Make no use of the bound.
Definition OptimizeStrategy.h:48
OptimizeStrategy::UseBoundToEliminateAndSimplify
@ UseBoundToEliminateAndSimplify
Eliminate non-improving slices and simplify slices by trying to generate non-improving slices that ar...
Definition OptimizeStrategy.h:57
OptimizeStrategy::UseBoundToEliminate
@ UseBoundToEliminate
Eliminate non-improving slices, achieving a branch-and-bound algorithm in place of the usual backtrac...
Definition OptimizeStrategy.h:52
OptimizeStrategy::getMaximalSolutions
const Ideal & getMaximalSolutions()
Returns one of or all of the msm's with optimal value found so far, depending on the value of reportA...
Definition OptimizeStrategy.cpp:41
OptimizeStrategy::OptimizeStrategy
OptimizeStrategy(TermGrader &grader, const SplitStrategy *splitStrategy, bool reportAllSolutions, BoundSetting boundSetting)
Construct an OptimizeStrategy.
Definition OptimizeStrategy.cpp:23
OptimizeStrategy::boundSimplify
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.
Definition OptimizeStrategy.cpp:204
OptimizeStrategy::_maxSolutions
Ideal _maxSolutions
Stores the optimal solutions found so far, according to the best value found so far.
Definition OptimizeStrategy.h:366
OptimizeStrategy::getDominator
bool getDominator(Slice &slice, Term &dominator)
Sets dominator to be a term dominating every element of the content of slice.
Definition OptimizeStrategy.cpp:329
OptimizeStrategy::getPivot
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
Definition OptimizeStrategy.cpp:77
OptimizeStrategy::_boundSimplify_tmpPivot
Term _boundSimplify_tmpPivot
Temporary variable used in simplify.
Definition OptimizeStrategy.h:410
OptimizeStrategy::getMaximalValue
const mpz_class & getMaximalValue()
The optimal value associated to all entries from getMaximalSolutions().
Definition OptimizeStrategy.cpp:45
OptimizeStrategy::_simplify_tmpUpperBound
mpz_class _simplify_tmpUpperBound
Temporary variable used in simplify.
Definition OptimizeStrategy.h:384
OptimizeStrategy::_maxValue
mpz_class _maxValue
The best value of any solution found so far.
Definition OptimizeStrategy.h:347
OptimizeStrategy::consume
virtual void consume(const Term &term)
Consume a term.
Definition OptimizeStrategy.cpp:58
OptimizeStrategy::_simplify_tmpOldDominator
Term _simplify_tmpOldDominator
Temporary variable used in simplify.
Definition OptimizeStrategy.h:394
OptimizeStrategy::_simplify_tmpDominator
Term _simplify_tmpDominator
Temporary variable used in simplify.
Definition OptimizeStrategy.h:389
OptimizeStrategy::_reportAllSolutions
bool _reportAllSolutions
Indicates whether to compute all optimal solutions, as opposed to computing just one (when there are ...
Definition OptimizeStrategy.h:371
OptimizeStrategy::changedInWayRelevantToBound
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.
Definition OptimizeStrategy.cpp:160
OptimizeStrategy::beginConsuming
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
Definition OptimizeStrategy.cpp:54
OptimizeStrategy::doneConsuming
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
Definition OptimizeStrategy.cpp:74
OptimizeStrategy::setUseIndependence
virtual void setUseIndependence(bool use)
Independence splits are not supported, so calling this method does nothing.
Definition OptimizeStrategy.cpp:50
OptimizeStrategy::getVarCount
size_t getVarCount() const
The number of varibles this object was initialized with.
Definition OptimizeStrategy.cpp:350
OptimizeStrategy::_maxValueToBeat
mpz_class _maxValueToBeat
Is equal to _maxValue minus _reportAllSolutions, except when no solution has been found so far,...
Definition OptimizeStrategy.h:361
OptimizeStrategy::simplify
virtual bool simplify(Slice &slice)
This method calls MsmStrategy::simplify to perform the usual simplification of slice,...
Definition OptimizeStrategy.cpp:81
OptimizeStrategy::_tmpC
mpz_class _tmpC
Temporary variable used in getInnerSimplify and getOuterSimplify.
Definition OptimizeStrategy.h:405
OptimizeStrategy::_boundSetting
BoundSetting _boundSetting
Indicates how to use the bound.
Definition OptimizeStrategy.h:374
OptimizeStrategy::_consume_tmpDegree
mpz_class _consume_tmpDegree
Temporary variable used in consume.
Definition OptimizeStrategy.h:379
OptimizeStrategy::getInnerSimplify
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...
Definition OptimizeStrategy.cpp:221
SliceStrategyCommon::simplify
virtual bool simplify(Slice &slice)
Simplifies slice and returns true if it changed.
Definition SliceStrategyCommon.cpp:55
SliceStrategy::setUseIndependence
virtual void setUseIndependence(bool use)=0
This method should only be called before calling run().
Slice
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition Slice.h:77
Slice::innerSlice
virtual bool innerSlice(const Term &pivot)
Sets this object to the inner slice according to pivot.
Definition Slice.cpp:110
Slice::outerSlice
virtual void outerSlice(const Term &pivot)
Sets this object to the outer slice according to pivot.
Definition Slice.cpp:132
Slice::getMultiply
Term & getMultiply()
Returns for a slice .
Definition Slice.h:113
Slice::clearIdealAndSubtract
void clearIdealAndSubtract()
Clears getIdeal() and getSubtract() and does not change getMultiply().
Definition Slice.cpp:99
Slice::getIdeal
const Ideal & getIdeal() const
Returns for a slice .
Definition Slice.h:104
Slice::getLcm
const Term & getLcm() const
Returns the least common multiple of the generators of getIdeal().
Definition Slice.cpp:52
Slice::getVarCount
size_t getVarCount() const
Returns the number of variables in the ambient ring.
Definition Slice.h:96
SplitStrategy
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition SplitStrategy.h:30
TermGrader
A TermGrader assigns a value, the degree, to each monomial.
Definition TermGrader.h:27
Term
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
Term::getVarCount
size_t getVarCount() const
Definition Term.h:85
Term::isIdentity
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
Term::divides
static bool divides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a divides b.
Definition Term.h:152
Term::setToIdentity
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
stdinc.h
This header file includes common definitions and is included as the first line of code in every imple...
Exponent
unsigned int Exponent
Definition stdinc.h:89
ASSERT
#define ASSERT(X)
Definition stdinc.h:86