Frobby  0.9.0
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 
25 class Slice;
26 class TermGrader;
27 
43 class OptimizeStrategy : public MsmStrategy, public TermConsumer {
44 public:
46  enum BoundSetting {
49 
53 
58  };
59 
72  const SplitStrategy* splitStrategy,
73  bool reportAllSolutions,
74  BoundSetting boundSetting);
75 
80  const Ideal& getMaximalSolutions();
81 
86  const mpz_class& getMaximalValue();
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 
265  bool getInnerSimplify
266  (const Term& divisor,
267  const Term& dominator,
268  const mpz_class& upperBound,
269  Term& pivot);
270 
324  bool getOuterSimplify
325  (const Term& divisor,
326  const Term& dominator,
327  const mpz_class& upperBound,
328  Term& pivot);
329 
336  bool getDominator(Slice& slice, Term& dominator);
337 
339  size_t getVarCount() const;
340 
343 
347  mpz_class _maxValue;
348 
361  mpz_class _maxValueToBeat;
362 
367 
372 
375 
380 
385 
390 
395 
400 
405  mpz_class _tmpC;
406 
411 
412 
413  FRIEND_TEST(OptimizeStrategy, ChangedInWayRelevantToBound);
414  FRIEND_TEST(OptimizeStrategy, SimplifyPositiveGrading);
415  FRIEND_TEST(OptimizeStrategy, SimplifyNegativeGrading);
416 };
417 
418 #endif
Term _simplify_tmpOldDominator
Temporary variable used in simplify.
Eliminate non-improving slices, achieving a branch-and-bound algorithm in place of the usual backtrac...
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's with optimal value found so far, depending on the value of reportA...
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.
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.
OptimizeStrategy optimizes a function on the maximal standard monomials of a monomial ideal using bra...
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().
virtual void consume(const Term &term)
Consume a term.
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
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
This class is used to transfer terms one at a time from one part of the program to another...
Definition: TermConsumer.h:36
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.
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.
Make no use of the bound.
mpz_class _maxValueToBeat
Is equal to _maxValue minus _reportAllSolutions, except when no solution has been found so far...
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.
FRIEND_TEST(OptimizeStrategy, ChangedInWayRelevantToBound)
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.
bool _reportAllSolutions
Indicates whether to compute all optimal solutions, as opposed to computing just one (when there are ...
size_t getVarCount() const
The number of varibles this object was initialized with.
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.
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
virtual void setUseIndependence(bool use)
Independence splits are not supported, so calling this method does nothing.