Frobby 0.9.5
OptimizeStrategy.h
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#ifndef OPTIMIZE_STRATEGY_GUARD
18#define OPTIMIZE_STRATEGY_GUARD
19
20#include "MsmStrategy.h"
21#include "Term.h"
22#include "TermConsumer.h"
23#include "tests.h"
24
25class Slice;
26class TermGrader;
27
44public:
59
75
81
87
91 virtual void setUseIndependence(bool use);
92
93 virtual void getPivot(Term& pivot, Slice& slice);
94
104 virtual bool simplify(Slice& slice);
105
106 virtual void beginConsuming();
107 virtual void consume(const Term& term);
108 virtual void doneConsuming();
109
110 private:
131 (const Term& oldDivisor, const Term& oldDominator,
132 const Term& newDivisor, const Term& newDominator) const;
133
210 bool boundSimplify
211 (Slice& slice,
212 const Term& dominator,
213 const mpz_class& upperBound);
214
266 (const Term& divisor,
267 const Term& dominator,
268 const mpz_class& upperBound,
269 Term& pivot);
270
325 (const Term& divisor,
326 const Term& dominator,
327 const mpz_class& upperBound,
328 Term& pivot);
329
337
339 size_t getVarCount() const;
340
343
348
362
367
372
375
380
385
390
395
400
406
411
412
416};
417
418#endif
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
OptimizeStrategy optimizes a function on the maximal standard monomials of a monomial ideal using bra...
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.
FRIEND_TEST(OptimizeStrategy, SimplifyPositiveGrading)
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...
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.
FRIEND_TEST(OptimizeStrategy, ChangedInWayRelevantToBound)
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.
FRIEND_TEST(OptimizeStrategy, SimplifyNegativeGrading)
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...
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition Slice.h:77
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
This class is used to transfer terms one at a time from one part of the program to another,...
A TermGrader assigns a value, the degree, to each monomial.
Definition TermGrader.h:27
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49