Frobby 0.10.0
Loading...
Searching...
No Matches
OptimizeStrategy Class Reference

#include <OptimizeStrategy.h>

Inheritance diagram for OptimizeStrategy:
Collaboration diagram for OptimizeStrategy:

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

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.

Member Enumeration Documentation

◆ 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.

Constructor & Destructor Documentation

◆ OptimizeStrategy()

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

Construct an OptimizeStrategy.

Parameters
graderThis object assigns values to monomials.
splitStrategyThe split selection strategy to use.
reportAllSolutionsCompute all msm's of optimal value if true. Otherwise compute a single msm of optimal value.
boundSettingIndicates how much to use the bound.

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.

◆ consume()

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

Consume a term.

Implements TermConsumer.

◆ doneConsuming()

void OptimizeStrategy::doneConsuming ( )
virtual

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

Implements TermConsumer.

◆ 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.

◆ 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.

◆ getPivot()

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

Used by pivotSplit to obtain a pivot.

Reimplemented from MsmStrategy.

◆ 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.

◆ 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.


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