OptimizeStrategy.h
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/.
*/
#ifndef OPTIMIZE_STRATEGY_GUARD
#define OPTIMIZE_STRATEGY_GUARD
#include "MsmStrategy.h"
#include "Term.h"
#include "TermConsumer.h"
#include "tests.h"
class Slice;
class TermGrader;
class OptimizeStrategy : public MsmStrategy, public TermConsumer {
public:
enum BoundSetting {
DoNotUseBound,
UseBoundToEliminate,
UseBoundToEliminateAndSimplify
};
OptimizeStrategy(TermGrader& grader,
const SplitStrategy* splitStrategy,
bool reportAllSolutions,
BoundSetting boundSetting);
const Ideal& getMaximalSolutions();
const mpz_class& getMaximalValue();
virtual void setUseIndependence(bool use);
virtual void getPivot(Term& pivot, Slice& slice);
virtual bool simplify(Slice& slice);
virtual void beginConsuming();
virtual void consume(const Term& term);
virtual void doneConsuming();
private:
bool changedInWayRelevantToBound
(const Term& oldDivisor, const Term& oldDominator,
const Term& newDivisor, const Term& newDominator) const;
bool boundSimplify
(Slice& slice,
const Term& dominator,
const mpz_class& upperBound);
bool getInnerSimplify
(const Term& divisor,
const Term& dominator,
const mpz_class& upperBound,
Term& pivot);
bool getOuterSimplify
(const Term& divisor,
const Term& dominator,
const mpz_class& upperBound,
Term& pivot);
bool getDominator(Slice& slice, Term& dominator);
size_t getVarCount() const;
const TermGrader& _grader;
mpz_class _maxValue;
mpz_class _maxValueToBeat;
Ideal _maxSolutions;
bool _reportAllSolutions;
BoundSetting _boundSetting;
mpz_class _consume_tmpDegree;
mpz_class _simplify_tmpUpperBound;
Term _simplify_tmpDominator;
Term _simplify_tmpOldDominator;
Term _simplify_tmpOldDivisor;
mpz_class _tmpC;
Term _boundSimplify_tmpPivot;
FRIEND_TEST(OptimizeStrategy, ChangedInWayRelevantToBound);
FRIEND_TEST(OptimizeStrategy, SimplifyPositiveGrading);
FRIEND_TEST(OptimizeStrategy, SimplifyNegativeGrading);
};
#endif
MsmStrategy.h
TermConsumer.h
Term.h
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
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::FRIEND_TEST
FRIEND_TEST(OptimizeStrategy, SimplifyPositiveGrading)
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::FRIEND_TEST
FRIEND_TEST(OptimizeStrategy, ChangedInWayRelevantToBound)
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::FRIEND_TEST
FRIEND_TEST(OptimizeStrategy, SimplifyNegativeGrading)
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
Slice
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition Slice.h:77
SplitStrategy
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition SplitStrategy.h:30
TermConsumer
This class is used to transfer terms one at a time from one part of the program to another,...
Definition TermConsumer.h:36
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
tests.h