List of all members | Public Member Functions | Protected Member Functions | Private Member Functions
ipo::OracleBase Class Referenceabstract

Detailed Description

Base class for an optimization oracle for a polyhedron $ P $ and all its faces. The oracle is either exact or it is associated to another optimization oracle, called the next oracle and called heuristic. The next oracle in turn need not be exact. All oracles reachable by going to the next one are called associated. The isExact() method indicates whether the oracle is exact or not and the thisHeuristic() method indicates the number of associated oracles (being zero if exact). The goal of this concept is to allow the implementation of quick heuristcs or approximation algorithms that forward a query to the next oracle if its own answer is not satisfactory.

An instance has a reference to a Space that manages the ambient space of $ P $, and that must agree for all associated oracles. An actual implementation of an oracle (or heuristic) must inherit from this class and implement the maximize() and setFace() methods. If there is no direct way to implement the optimization over arbitrary faces, consider inheriting from FaceOracleBase instead.

A call to any of the maximize() methods to optimize objective $ c \in \mathbb{Q}^n $ over the current face $ F $ (setFace()) with improveValue $ \gamma $ and requested maxHeuristic and minHeuristic must obey the following rules, where we denote by $ S \subseteq F $ and $ R \subseteq \text{recc}(P) $ the sets of returned points and rays, respectively. The returned OracleResult is denoted by result.

#include <ipo/oracles.h>

+ Inheritance diagram for ipo::OracleBase:

Public Member Functions

const std::string & name () const
 Returns the name of the oracle. More...
 
const Spacespace () const
 Returns the ambient space. More...
 
std::size_t heuristicLevel () const
 Returns the heuristic level of this oracle. More...
 
virtual void setFace (const LinearConstraint &newFace)
 Restricts the oracle to the face defined by newFace. More...
 
void maximize (OracleResult &result, const soplex::VectorRational &objective, const ObjectiveBound &objectiveBound=ObjectiveBound(), std::size_t minHeuristic=0, std::size_t maxHeuristic=std::numeric_limits< std::size_t >::max())
 Runs the oracle to maximize the dense rational objective. More...
 
void maximize (OracleResult &result, const Vector &objective, const ObjectiveBound &objectiveBound=ObjectiveBound(), std::size_t minHeuristic=0, std::size_t maxHeuristic=std::numeric_limits< std::size_t >::max())
 Runs the oracle to maximize the sparse rational objective. More...
 

Protected Member Functions

 OracleBase (const std::string &name, const std::shared_ptr< OracleBase > &nextOracle=NULL)
 Constructs an oracle with given name, optionally associated to nextOracle. More...
 
void initializeSpace (const Space &space)
 Initializes datastructures that require the oracle's ambient space. More...
 
virtual std::size_t maximizeController (OracleResult &result, const soplex::VectorRational &objective, const ObjectiveBound &objectiveBound, std::size_t maxHeuristic, std::size_t minHeuristic, bool &sort, bool &checkDups)
 Wrapper method that calls the oracle's implementation. More...
 
virtual std::size_t maximizeImplementation (OracleResult &result, const soplex::VectorRational &objective, const ObjectiveBound &objectiveBound, std::size_t minHeuristic, std::size_t maxHeuristic, bool &sort, bool &checkDups)=0
 Oracle's implementation to maximize the dense rational objective. More...
 
virtual const LinearConstraintcurrentFace ()
 Returns the current face. More...
 

Private Member Functions

 OracleBase ()
 Default constructor is disabled. More...
 

Constructor & Destructor Documentation

ipo::OracleBase::OracleBase ( const std::string &  name,
const std::shared_ptr< OracleBase > &  nextOracle = NULL 
)
protected

Constructs an oracle with given name that is optionally associated to nextOracle. If not associated, then the space will be the emptySpace() initially.

ipo::OracleBase::OracleBase ( )
private

Default constructor is disabled.

Member Function Documentation

const std::string& ipo::OracleBase::name ( ) const
inline

Returns the name of the oracle.

const Space& ipo::OracleBase::space ( ) const
inline

Returns a reference to the ambient space.

std::size_t ipo::OracleBase::heuristicLevel ( ) const
inline

Returns the heuristic level of this oracle which is equal to the number of heuristics it is associated to. This number is equal to zero if the oracle is not associated to another oracle. Otherwise, it is equal to the value of thisHeuristic() for the associated oracle plus 1.

virtual void ipo::OracleBase::setFace ( const LinearConstraint newFace)
virtual

Restricts the optimization oracle to the face $ F $ of $ P $ defined by newFace. For newFace equal to NULL we define $ F := P $.

This implementation stores newFace such that currentFace() works properly and calls setFace() for the next oracle.

Reimplemented in ipo::FaceOracleBase, ipo::MIPOracleBase, ipo::ProjectionOracle, and ipo::SCIPOracle.

void ipo::OracleBase::maximize ( OracleResult result,
const soplex::VectorRational &  objective,
const ObjectiveBound &  objectiveBound = ObjectiveBound(),
std::size_t  minHeuristic = 0,
std::size_t  maxHeuristic = std::numeric_limits< std::size_t >::max() 
)

Runs the optimization oracle to maximize the given dense rational objective over the current face $ F $ (see setFace()) and returns result. If maxHeuristic is less than thisHeuristic() or if the objective value requested by objectiveBound is not exceeded, then the call must be forwarded to the next oracle.

This implementation initializes the result data structure, calls the maximizeController() method (with a dense objective vector), and finally postprocesses the result object.

Parameters
resultAfter the call, contains the oracle's answer.
objectiveObjective vector $ c \in \mathbb{Q}^n $ to be maximized.
objectiveBoundObjective value $ \gamma $ that should be exceeded.
minHeuristicRequested minimum heuristic level.
maxHeuristicRequested maximum heuristic level.

For requirements on the behavior, see Detailed Description of OracleBase.

void ipo::OracleBase::maximize ( OracleResult result,
const Vector objective,
const ObjectiveBound &  objectiveBound = ObjectiveBound(),
std::size_t  minHeuristic = 0,
std::size_t  maxHeuristic = std::numeric_limits< std::size_t >::max() 
)

Runs the optimization oracle to maximize the given sparse rational objective over the current face $ F $ (see setFace()) and returns result. If maxHeuristic is less than thisHeuristic() or if the objective value requested by objectiveBound is not exceeded, then the call must be forwarded to the next oracle.

This implementation initializes the result data structure, calls the maximizeController() method (with a dense objective vector), and finally postprocesses the result object.

Parameters
resultAfter the call, contains the oracle's answer.
objectiveObjective vector $ c \in \mathbb{Q}^n $ to be maximized.
objectiveBoundObjective value $ \gamma $ that should be exceeded.
minHeuristicRequested minimum heuristic level.
maxHeuristicRequested maximum heuristic level.

For requirements on the behavior, see Detailed Description of OracleBase.

void ipo::OracleBase::initializeSpace ( const Space space)
protected

Initializes datastructures that require the oracle's ambient space. Should be called before the constructor ends.

virtual std::size_t ipo::OracleBase::maximizeController ( OracleResult result,
const soplex::VectorRational &  objective,
const ObjectiveBound &  objectiveBound,
std::size_t  maxHeuristic,
std::size_t  minHeuristic,
bool &  sort,
bool &  checkDups 
)
protectedvirtual

This method is called by maximize(), forwards the call to the next oracle if requested, calls the maximizeImplementation() method, and finally forwards the call to the next oracle if necessary.

Parameters
resultAfter the call, contains the oracle's answer.
objectiveObjective vector $ c \in \mathbb{Q}^n $ to be maximized.
objectiveBoundObjective value $ \gamma $ that should be exceeded.
sortSet this variable to true if points must be sorted.
checkDupsSet this variable to true if points or rays must be checked for duplicates.

For requirements on the behavior, see Detailed Description of OracleBase.

Reimplemented in ipo::FaceOracleBase.

virtual std::size_t ipo::OracleBase::maximizeImplementation ( OracleResult result,
const soplex::VectorRational &  objective,
const ObjectiveBound &  objectiveBound,
std::size_t  minHeuristic,
std::size_t  maxHeuristic,
bool &  sort,
bool &  checkDups 
)
protectedpure virtual

This method is called by maximizeController() and contains the implementation of the oracle.

Parameters
resultAfter the call, contains the oracle's answer.
objectiveObjective vector $ c \in \mathbb{Q}^n $ to be maximized.
objectiveBoundObjective value $ \gamma $ that should be exceeded.
sortSet this variable to true if points must be sorted.
checkDupsSet this variable to true if points or rays must be checked for duplicates.

For requirements on the behavior, see Detailed Description of OracleBase.

Implemented in ipo::MIPOracleBase, ipo::ProjectionOracle, and ipo::ExternalOracle.

virtual const LinearConstraint& ipo::OracleBase::currentFace ( )
protectedvirtual

Returns the current face.

See also
setFace()

Reimplemented in ipo::FaceOracleBase.