|
Frobby 0.10.0
|
#include <OptimizeStrategy.h>


Public Types | |
| enum | BoundSetting { DoNotUseBound , UseBoundToEliminate , UseBoundToEliminateAndSimplify } |
Public Member Functions | |
| 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 () |
| Public Member Functions inherited from MsmStrategy | |
| MsmStrategy (TermConsumer *consumer, const SplitStrategy *splitStrategy) | |
| MsmStrategy (TermConsumer *consumer, const SplitStrategy *splitStrategy, const Ideal &initialSubtract) | |
| virtual void | run (const Ideal &ideal) |
| virtual bool | processSlice (TaskEngine &tasks, unique_ptr< Slice > slice) |
| Public Member Functions inherited from SliceStrategyCommon | |
| SliceStrategyCommon (const SplitStrategy *splitStrategy) | |
| virtual void | freeSlice (unique_ptr< Slice > slice) |
| virtual void | setUseSimplification (bool use) |
| Public Member Functions inherited from TermConsumer | |
| virtual void | consumeRing (const VarNames &names) |
| virtual void | beginConsumingList () |
| virtual void | doneConsumingList () |
| void | consume (const Ideal &ideal) |
Additional Inherited Members | |
| Protected Member Functions inherited from MsmStrategy | |
| virtual void | getPivot (Term &pivot, Slice &slice, const TermGrader &grader) |
| Protected Member Functions inherited from SliceStrategyCommon | |
| unique_ptr< Slice > | newSlice () |
| virtual void | pivotSplit (unique_ptr< Slice > slice) |
| bool | getUseIndependence () const |
| bool | getUseSimplification () const |
| Protected Attributes inherited from SliceStrategyCommon | |
| const SplitStrategy * | _split |
| TaskEngine | _tasks |
OptimizeStrategy optimizes a function on the maximal standard monomials of a monomial ideal using branch-and-bound.
Branch-and-bound is an algorithmic technique. In this case, it amounts to having a bound, which is a function that assigns a value to each slice. This value is an non-strict upper bound on the value of each maximal standard monomial in the content of that slice. If the value of the bound is worse than the best value of an msm found so far, then we do not have to consider that slice further. Such a slice is called non-improving.
Whenever a slice is non-improving, we avoid some computation by ignoring it. We exploit this further, by purposefully seeking to generate slices that are non-improving.
The values of BoundSetting indicate how to use the bound.
| OptimizeStrategy::OptimizeStrategy | ( | TermGrader & | grader, |
| const SplitStrategy * | splitStrategy, | ||
| bool | reportAllSolutions, | ||
| BoundSetting | boundSetting ) |
Construct an OptimizeStrategy.
| grader | This object assigns values to monomials. |
| splitStrategy | The split selection strategy to use. |
| reportAllSolutions | Compute all msm's of optimal value if true. Otherwise compute a single msm of optimal value. |
| boundSetting | Indicates how much to use the bound. |
|
virtual |
Tell the consumer to begin consuming an ideal. It is required to call this method before calling consume().
Implements TermConsumer.
|
virtual |
Consume a term.
Implements TermConsumer.
|
virtual |
Must be called once after each time beginConsuming has been called.
Implements TermConsumer.
| const Ideal & OptimizeStrategy::getMaximalSolutions | ( | ) |
Returns one of or all of the msm's with optimal value found so far, depending on the value of reportAllSolutions passed to the constructor.
| const mpz_class & OptimizeStrategy::getMaximalValue | ( | ) |
The optimal value associated to all entries from getMaximalSolutions(). This method can only be called if getMaximalSolutions() is not the zero ideal.
Used by pivotSplit to obtain a pivot.
Reimplemented from MsmStrategy.
|
virtual |
Independence splits are not supported, so calling this method does nothing. Will assert in debug mode if use is true.
Reimplemented from SliceStrategyCommon.
|
virtual |
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.
Independent of whether usual simplification has been turned on, this method also eliminates non-improving slices, and uses bound-driven simplification, depending on the value of BoundSetting passed to the constructor.
Reimplemented from SliceStrategyCommon.