OptimizeStrategy Class Reference

OptimizeStrategy optimizes a function on the maximal standard monomials of a monomial ideal using branch-and-bound. More...

`#include <OptimizeStrategy.h>`

Inheritance diagram for OptimizeStrategy:

## Public Types

enum | BoundSetting { DoNotUseBound , UseBoundToEliminate , UseBoundToEliminateAndSimplify }
| The values of BoundSetting indicate how to use the bound. More...

## Public Member Functions

| OptimizeStrategy (TermGrader &grader, const SplitStrategy *splitStrategy, bool reportAllSolutions, BoundSetting boundSetting)
| Construct an OptimizeStrategy.
const Ideal & | 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 & | getMaximalValue ()
| The optimal value associated to all entries from getMaximalSolutions().
virtual void | setUseIndependence (bool use)
| Independence splits are not supported, so calling this method does nothing.
virtual void | getPivot (Term &pivot, Slice &slice)
| Used by pivotSplit to obtain a pivot.
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.
virtual void | beginConsuming ()
| Tell the consumer to begin consuming an ideal.
virtual void | consume (const Term &term)
| Consume a term.
virtual void | doneConsuming ()
| Must be called once after each time beginConsuming has been called.
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)
| Run the Slice algorithm.
virtual bool | processSlice (TaskEngine &tasks, unique_ptr< Slice > slice)
| Process the parameter slice.
Public Member Functions inherited from SliceStrategyCommon
| SliceStrategyCommon (const SplitStrategy *splitStrategy)
virtual | ~SliceStrategyCommon ()
virtual void | freeSlice (unique_ptr< Slice > slice)
| It is allowed to delete returned slices directly, but it is better to use freeSlice.
virtual void | setUseSimplification (bool use)
| This method should only be called before calling run().
Public Member Functions inherited from SliceStrategy
virtual | ~SliceStrategy ()
Public Member Functions inherited from TermConsumer
virtual | ~TermConsumer ()
virtual void | consumeRing (const VarNames &names)
| Tell the consumer which ring is being used.
virtual void | beginConsumingList ()
| Tell the consumer that the ideals that are consumed until the next call to doneConsumingList are to be considered as one list of ideals, rather than as a number of separate ideals.
virtual void | doneConsumingList ()
| Must be called once after each time beginConsumingList has been called.
void | consume (const Ideal &ideal)
| This is a non-virtual utility method that calls the other methods to achieve its effect of calling beginConsuming, then consuming all generators, and then calling doneConsuming.

## Private Member Functions

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.
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.
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 slice.
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 slice.
bool | getDominator (Slice &slice, Term &dominator)
| Sets dominator to be a term dominating every element of the content of slice.
size_t | getVarCount () const
| The number of varibles this object was initialized with.
| FRIEND_TEST (OptimizeStrategy, ChangedInWayRelevantToBound)
| FRIEND_TEST (OptimizeStrategy, SimplifyPositiveGrading)
| FRIEND_TEST (OptimizeStrategy, SimplifyNegativeGrading)

## Private Attributes

const TermGrader & | _grader
| We use _grader to assign values to solutions.
mpz_class | _maxValue
| The best value of any solution found so far.
mpz_class | _maxValueToBeat
| Is equal to _maxValue minus _reportAllSolutions, except when no solution has been found so far, in which case the value is undefined.
Ideal | _maxSolutions
| Stores the optimal solutions found so far, according to the best value found so far.
bool | _reportAllSolutions
| Indicates whether to compute all optimal solutions, as opposed to computing just one (when there are any).
BoundSetting | _boundSetting
| Indicates how to use the bound.
mpz_class | _consume_tmpDegree
| Temporary variable used in consume.
mpz_class | _simplify_tmpUpperBound
| Temporary variable used in simplify.
Term | _simplify_tmpDominator
| Temporary variable used in simplify.
Term | _simplify_tmpOldDominator
| Temporary variable used in simplify.
Term | _simplify_tmpOldDivisor
| Temporary variable used in simplify.
mpz_class | _tmpC
| Temporary variable used in getInnerSimplify and getOuterSimplify.
Term | _boundSimplify_tmpPivot
| Temporary variable used in simplify.

## 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 ()
| Returns a slice from the cache that freeSlice adds to, or allocate a new one using allocateSlice.
virtual void | pivotSplit (unique_ptr< Slice > slice)
| Takes over ownership of slice.
bool | getUseIndependence () const
| Returns true if independence splits should be performed when possible.
bool | getUseSimplification () const
| Returns true if slices should be simplified.
Protected Attributes inherited from SliceStrategyCommon
const SplitStrategy * | _split
TaskEngine | _tasks
| This keeps track of pending tasks to process.

## Detailed Description

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.

Definition at line 43 of file OptimizeStrategy.h.

## Member Enumeration Documentation

## BoundSetting

enum OptimizeStrategy::BoundSetting

The values of BoundSetting indicate how to use the bound.

Enumerator
DoNotUseBound | Make no use of the bound.
UseBoundToEliminate | Eliminate non-improving slices, achieving a branch-and-bound algorithm in place of the usual backtracking.
UseBoundToEliminateAndSimplify | Eliminate non-improving slices and simplify slices by trying to generate non-improving slices that are then eliminated, allowing to move to the other slice.

Definition at line 46 of file OptimizeStrategy.h.

## Constructor & Destructor Documentation

## OptimizeStrategy()

OptimizeStrategy::OptimizeStrategy | ( | TermGrader & | grader,
|  | const SplitStrategy * | splitStrategy,
|  | bool | reportAllSolutions,
|  | BoundSetting | boundSetting )

Construct an OptimizeStrategy.

Parameters

  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.

Definition at line 23 of file OptimizeStrategy.cpp.

## Member Function Documentation

## beginConsuming()

void OptimizeStrategy::beginConsuming | ( |  | ) |

virtual

Tell the consumer to begin consuming an ideal.

It is required to call this method before calling consume().

Implements TermConsumer.

Definition at line 54 of file OptimizeStrategy.cpp.

## boundSimplify()

bool OptimizeStrategy::boundSimplify | ( | Slice & | slice,
|  | const Term & | dominator,
|  | const mpz_class & | upperBound )

private

This method simplifies a slice based on generating non-improving outer and inner slices.

The idea is conceptually simple, but it has been quite a challenge to get the code to be correct, efficient and as good as possible in terms of simplifying as much as possible. This is why there are so many tests related to this, and why the comments for this and related methods are so detailed.

To each slice we associate a divisor and a dominator , which respectively divide and dominate each msm in the content of the slice. I.e. . We summarize this as a pair . Let be the associated upper bound, i.e. the largest possible value that the grader associates to a monomial such that . Thus is an uppper bound on the value of any msm in the content of the slice to which is associated.

To be more exact, for a slice , is the divisor, while is the dominator. Also, let be the value of and let be the highest value according to the grader of an msm found so far.

This allows us to discard slices that are non-improving, in that they do not improve on the best value found so far. Note that whether "improve" means "strictly improve" or "weakly improve" depends on whether we are reporting all optimal msm's or just one. In the following discussion we will assume that we are looking for just one msm, so that a slice is non-improving if it does not strictly improve.

This method is called when the slice itself cannot be seen to be non-improving from the divisor and dominator. However, if we consider pivot splits on pivots that are pure powers, i.e. of the form , then we can compute a divisor and dominator for both the inner and outer slice just from the divisor and dominator of the current slice. Note that the divisor and dominator assigned in this way are not necessarily as tight as the ones we would get if we actually computed the inner and outer slice.

It may be that we can see that the inner or outer slice from above is non-improving. If the inner slice is non-improving, then we can discard it and replace the current slice with the outer slice, and vice versa if the outer slice is non-improving. This is bound-driven simplification of a slice, and it is efficient since we can perform these calculations looking only at the two monomials divisor and dominator.

Consider a pivot split on . Then the outer slice has , where is equal to except that . The inner slice will have , where is equal to except that . Note that the sensible 's to consider are those for which . We need to work in terms of rather than just since we work with a TermGrader that has no reasonable way of making sense of just t.

If possible, this method moves to an inner or outer slice of the parameter slice based on this reasoning.

See getInnerSimplify and getOuterSimplify for more details. Which one of those two is relevant for a given slice and variable depends on the sign of that variable in the grading, and on whether the ideal contains a pure power that maps to the same value as zero does. We call the latter phenomenon a "fake power".

Parameters

  slice | The slice to work on.
  dominator | The dominator of slice (passed as a parameter to avoid recomputation).
  upperBound | The upper bound associated to slice (to avoid recomputation).

Returns
  Returns true if and only if slice changed.

Definition at line 203 of file OptimizeStrategy.cpp.

## changedInWayRelevantToBound()

bool OptimizeStrategy::changedInWayRelevantToBound | ( | const Term & | oldDivisor,
|  | const Term & | oldDominator,
|  | const Term & | newDivisor,
|  | const Term & | newDominator ) const

private

Returns true if iterating bound-based simplification might do something.

There are four cases where it makes sense to iterate the bound-based simplification after the slice has changed.

- Case 1: The sign is negative, and the divisor has increased. This is relevant whether or not we are using a fake power, since if so there still is an effect on the bound for a split that gets rid of the pure power.
- Case 2: The sign is negative, and we were using a fake power to get the value of zero, but now it is gone.
- Case 3: The sign is positive, and the dominator has decreased, and it did not just remove a fake power exponent.
- Case 4: The sign is positive, and the dominator has a fake power exponent, and the divisor has increased so that we are forced to use it.

Definition at line 159 of file OptimizeStrategy.cpp.

## consume()

void OptimizeStrategy::consume | ( | const Term & | term | ) |

virtual

Consume a term.

Implements TermConsumer.

Definition at line 58 of file OptimizeStrategy.cpp.

## doneConsuming()

void OptimizeStrategy::doneConsuming | ( |  | ) |

virtual

Must be called once after each time beginConsuming has been called.

Implements TermConsumer.

Definition at line 74 of file OptimizeStrategy.cpp.

## FRIEND_TEST() [1/3]

OptimizeStrategy::FRIEND_TEST | ( | OptimizeStrategy | ,
|  | ChangedInWayRelevantToBound | )

private

## FRIEND_TEST() [2/3]

OptimizeStrategy::FRIEND_TEST | ( | OptimizeStrategy | ,
|  | SimplifyNegativeGrading | )

private

## FRIEND_TEST() [3/3]

OptimizeStrategy::FRIEND_TEST | ( | OptimizeStrategy | ,
|  | SimplifyPositiveGrading | )

private

## getDominator()

bool OptimizeStrategy::getDominator | ( | Slice & | slice,
|  | Term & | dominator )

private

Sets dominator to be a term dominating every element of the content of slice.

Returns false (and clears slice) only if slice is a trivial base case slice, but may return true even if it is a base case slice.

Definition at line 329 of file OptimizeStrategy.cpp.

## getInnerSimplify()

bool OptimizeStrategy::getInnerSimplify | ( | const Term & | divisor,
|  | const Term & | dominator,
|  | const mpz_class & | upperBound,
|  | Term & | pivot )

private

Find an outer slice that is non-improving, allowing us to replace the current slice with the inner slice.

We only need to know a divisor and dominator of the current slice to perform this analysis. If then there is nothing to be done for the 'th entry, so assume that .

There are two ways to obtain a non-improving outer slice. The first is if the grading sign is positive, and . Let if is not a fake exponent, and let if is a fake exponent. Then we have that

whereby is equivalent to

Letting , we are thus looking for a with such that . To make the inner slice as much simpler as possible, we would like to find the largest such t, if any. TermGrader has a method that does this.

The other way of getting a non-improving outer slice is with a negative grading sign and a fake power. The fake power allows to set the value at the i'th entry down to the value of zero, which is better than any other exponent when the sign is negative.

A non-trivial outer slice will not have the fake power, and thus possibly decrease the upper bound of the outer slice relative to the current slice, which may make it non-improving. This is most likely to happen for the largest possible , and we want to be large anyway in order to make the inner slice as simple as possible, so it only makes sense to check this for . As the sign is negative, we get that

where we are noting that . The question is then whether .

Parameters

  divisor | The divisor associated to the slice.
  dominator | The dominator associated to the slice.
  upperBound | The upper bound associated to the slice (passed as a parameter to avoid recomputation).
  pivot | Is set to a pivot that generates a non-improving outer slice if one is found.

Returns
  Returns true if and only if a non-improving outer slice was found.

Definition at line 220 of file OptimizeStrategy.cpp.

## getMaximalSolutions()

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.

Definition at line 41 of file OptimizeStrategy.cpp.

## getMaximalValue()

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.

Definition at line 45 of file OptimizeStrategy.cpp.

## getOuterSimplify()

bool OptimizeStrategy::getOuterSimplify | ( | const Term & | divisor,
|  | const Term & | dominator,
|  | const mpz_class & | upperBound,
|  | Term & | pivot )

private

Find an inner slice that is non-improving, allowing us to replace the current slice with the outer slice.

We only need to know a divisor and dominator of the current slice to perform this analysis. If then there is nothing to be done for the 'th entry, so assume that .

There are two ways to obtain a non-improving inner slice. The first is if the grading sign is negative, there is no fake power of , and . Since the sign is negative and there is no fake power, we have that

, whereby is equivalent to

Letting , we are thus looking for a with such that . To make the outer slice as much simpler as possible, we would like to find the smallest such t, if any. TermGrader has a method that does this.

Note that the assumption above that there is no fake power of does not rule out any useful simplification, as in that case the inner slice will never be non-improving, since it would also have the fake power (in our analysis of just looking at and ), so that the upper bound of the inner slice would be equal to the upper bound of the current slice.

The other way of getting a non-improving inner slice is with a positive grading sign and a fake power. If is as large as possible, i.e. , then the outer slice is forced to use the fake power, which decreases the 'th entry down to the value for zero, which is the worst possible when the sign is positive, and this might make the inner slice non-improving.

As the sign is positive, and is a fake exponent, we get that

and it is then a question of whether .

Parameters

  divisor | The divisor associated to the slice.
  dominator | The dominator associated to the slice.
  upperBound | The upper bound associated to the slice (passed as a parameter to avoid recomputation).
  pivot | Is set to a pivot that generates a non-improving inner slice if one is found.

Returns
  Returns true if and only if a non-improving inner slice was found.

Definition at line 277 of file OptimizeStrategy.cpp.

## getPivot()

void OptimizeStrategy::getPivot | ( | Term & | pivot,
|  | Slice & | slice )

virtual

Used by pivotSplit to obtain a pivot.

Reimplemented from MsmStrategy.

Definition at line 77 of file OptimizeStrategy.cpp.

## getVarCount()

size_t OptimizeStrategy::getVarCount | ( |  | ) | const

private

The number of varibles this object was initialized with.

Definition at line 350 of file OptimizeStrategy.cpp.

## setUseIndependence()

void OptimizeStrategy::setUseIndependence | ( | bool | use | ) |

virtual

Independence splits are not supported, so calling this method does nothing.

Will assert in debug mode if use is true.

Reimplemented from SliceStrategyCommon.

Definition at line 50 of file OptimizeStrategy.cpp.

## simplify()

bool OptimizeStrategy::simplify | ( | Slice & | slice | ) |

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.

Definition at line 81 of file OptimizeStrategy.cpp.

## Member Data Documentation

## _boundSetting

BoundSetting OptimizeStrategy::_boundSetting

private

Indicates how to use the bound.

Definition at line 374 of file OptimizeStrategy.h.

## _boundSimplify_tmpPivot

Term OptimizeStrategy::_boundSimplify_tmpPivot

private

Temporary variable used in simplify.

Is a member variable in order to avoid the cost of initializing a Term every time.

Definition at line 410 of file OptimizeStrategy.h.

## _consume_tmpDegree

mpz_class OptimizeStrategy::_consume_tmpDegree

private

Temporary variable used in consume.

Is a member variable in order to avoid the cost of initializing an mpz_class every time.

Definition at line 379 of file OptimizeStrategy.h.

## _grader

const TermGrader& OptimizeStrategy::_grader

private

We use _grader to assign values to solutions.

Definition at line 342 of file OptimizeStrategy.h.

## _maxSolutions

Ideal OptimizeStrategy::_maxSolutions

private

Stores the optimal solutions found so far, according to the best value found so far.

Definition at line 366 of file OptimizeStrategy.h.

## _maxValue

mpz_class OptimizeStrategy::_maxValue

private

The best value of any solution found so far.

The value is undefined if no solution has been found so far.

Definition at line 347 of file OptimizeStrategy.h.

## _maxValueToBeat

mpz_class OptimizeStrategy::_maxValueToBeat

private

Is equal to _maxValue minus _reportAllSolutions, except when no solution has been found so far, in which case the value is undefined.

We use _maxValueToBeat in place of _maxValue as a way to handle both values of _reportAllSolutions without having a lot of code of the type

if (_reportAllSolutions ? a < _maxValue : a <= _maxValue) ...

The point is that we can replace this by

if (a <= _maxValueToBeat) ...

Definition at line 361 of file OptimizeStrategy.h.

## _reportAllSolutions

bool OptimizeStrategy::_reportAllSolutions

private

Indicates whether to compute all optimal solutions, as opposed to computing just one (when there are any).

Definition at line 371 of file OptimizeStrategy.h.

## _simplify_tmpDominator

Term OptimizeStrategy::_simplify_tmpDominator

private

Temporary variable used in simplify.

Is a member variable in order to avoid the cost of initializing a Term every time.

Definition at line 389 of file OptimizeStrategy.h.

## _simplify_tmpOldDivisor

Term OptimizeStrategy::_simplify_tmpOldDivisor

private

Temporary variable used in simplify.

Is a member variable in order to avoid the cost of initializing a Term every time.

Definition at line 399 of file OptimizeStrategy.h.

## _simplify_tmpOldDominator

Term OptimizeStrategy::_simplify_tmpOldDominator

private

Temporary variable used in simplify.

Is a member variable in order to avoid the cost of initializing a Term every time.

Definition at line 394 of file OptimizeStrategy.h.

## _simplify_tmpUpperBound

mpz_class OptimizeStrategy::_simplify_tmpUpperBound

private

Temporary variable used in simplify.

Is a member variable in order to avoid the cost of initializing an mpz_class every time.

Definition at line 384 of file OptimizeStrategy.h.

## _tmpC

mpz_class OptimizeStrategy::_tmpC

private

Temporary variable used in getInnerSimplify and getOuterSimplify.

Is a member variable in order to avoid the cost of initializing an mpz_class every time.

Definition at line 405 of file OptimizeStrategy.h.

The documentation for this class was generated from the following files:

- src/OptimizeStrategy.h
- src/OptimizeStrategy.cpp