Abstract base class for heuristic implementations. More...

#include <HeuristicBase.h>

Inheritance diagram for PBQP::HeuristicBase< HImpl >:

Public Member Functions
	HeuristicBase (HeuristicSolverImpl< HImpl > &solver)
	Construct an instance with a reference to the given solver. More...

HeuristicSolverImpl< HImpl > &	getSolver ()
	Get the solver which is using this heuristic instance. More...

Graph &	getGraph ()
	Get the graph representing the problem to be solved. More...

bool	solverRunSimplify () const
	Tell the solver to simplify the graph before the reduction phase. More...

bool	shouldOptimallyReduce (Graph::NodeId nId)
	Decide whether a node should be optimally or heuristically reduced. More...

void	addToOptimalReduceList (Graph::NodeId nId)
	Add the given node to the list of nodes to be optimally reduced. More...

void	setup ()
	Initialise the heuristic. More...

bool	optimalReduce ()
	Optimally reduce one of the nodes in the optimal reduce list. More...

void	reduce ()
	Perform the PBQP reduction process. More...

void	addToHeuristicList (Graph::NodeId nId)
	Add a node to the heuristic reduce list. More...

bool	heuristicReduce ()
	Heuristically reduce one of the nodes in the heuristic reduce list. More...

void	preUpdateEdgeCosts (Graph::EdgeId eId)
	Prepare a change in the costs on the given edge. More...

void	postUpdateEdgeCostts (Graph::EdgeId eId)
	Handle the change in the costs on the given edge. More...

void	handleAddEdge (Graph::EdgeId eId)
	Handle the addition of a new edge into the PBQP graph. More...

void	handleRemoveEdge (Graph::EdgeId eId, Graph::NodeId nId)
	Handle disconnection of an edge from a node. More...

void	cleanup ()
	Clean up any structures used by HeuristicBase. More...

Detailed Description

template<typename HImpl>
class PBQP::HeuristicBase< HImpl >

Abstract base class for heuristic implementations.

This class provides a handy base for heuristic implementations with common solver behaviour implemented for a number of methods.

To implement your own heuristic using this class as a base you'll have to implement, as a minimum, the following methods:

void addToHeuristicList(Graph::NodeItr) : Add a node to the heuristic reduction list.
void heuristicReduce() : Perform a single heuristic reduction.
void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent) change to the cost matrix on the given edge (by R2).
void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new costs on the given edge.
void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new edge into the PBQP graph (by R2).
void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the disconnection of the given edge from the given node.
A constructor for your derived class : to pass back a reference to the solver which is using this heuristic.

These methods are implemented in this class for documentation purposes, but will assert if called.

Note that this class uses the curiously recursive template idiom to forward calls to the derived class. These methods need not be made virtual, and indeed probably shouldn't for performance reasons.

You'll also need to provide NodeData and EdgeData structs in your class. These can be used to attach data relevant to your heuristic to each node/edge in the PBQP graph.

Definition at line 52 of file HeuristicBase.h.

Constructor & Destructor Documentation

template<typename HImpl>

PBQP::HeuristicBase< HImpl >::HeuristicBase ( HeuristicSolverImpl< HImpl > & solver )

inline

Construct an instance with a reference to the given solver.

Parameters

solver The solver which is using this heuristic instance.

Definition at line 74 of file HeuristicBase.h.

Member Function Documentation

template<typename HImpl>

void PBQP::HeuristicBase< HImpl >::addToHeuristicList ( Graph::NodeId nId )

inline

Add a node to the heuristic reduce list.

Parameters

nId	Node id to add to the heuristic reduce list.

Definition at line 188 of file HeuristicBase.h.

template<typename HImpl>

void PBQP::HeuristicBase< HImpl >::addToOptimalReduceList ( Graph::NodeId nId )

inline

Add the given node to the list of nodes to be optimally reduced.

Parameters

nId	Node id to be added.

You probably don't want to over-ride this, except perhaps to record statistics before calling this implementation. HeuristicBase relies on its behaviour.

Definition at line 121 of file HeuristicBase.h.

Referenced by PBQP::HeuristicBase< Briggs >::setup().

template<typename HImpl>

void PBQP::HeuristicBase< HImpl >::cleanup ( )

inline

Clean up any structures used by HeuristicBase.

At present this just performs a sanity check: that the optimal reduce list is empty now that reduction has completed.

If your derived class has more complex structures which need tearing down you should over-ride this method but include a call back to this implementation.

Definition at line 238 of file HeuristicBase.h.

template<typename HImpl>

Graph& PBQP::HeuristicBase< HImpl >::getGraph ( )

inline

Get the graph representing the problem to be solved.

Returns: The graph representing the problem to be solved.

Definition at line 86 of file HeuristicBase.h.

template<typename HImpl>

HeuristicSolverImpl<HImpl>& PBQP::HeuristicBase< HImpl >::getSolver ( )

inline

Get the solver which is using this heuristic instance.

Returns: The solver which is using this heuristic instance.

You can use this method to get access to the solver in your derived heuristic implementation.

Definition at line 82 of file HeuristicBase.h.

Referenced by PBQP::HeuristicBase< Briggs >::reduce().

template<typename HImpl>

void PBQP::HeuristicBase< HImpl >::handleAddEdge ( Graph::EdgeId eId )

inline

Handle the addition of a new edge into the PBQP graph.

Parameters

eId	Edge id for the added edge.

Definition at line 215 of file HeuristicBase.h.

template<typename HImpl>

void PBQP::HeuristicBase< HImpl >::handleRemoveEdge	(	Graph::EdgeId	eId,
		Graph::NodeId	nId
	)

inline

Handle disconnection of an edge from a node.

Parameters

eId	Edge id for edge being disconnected.
nId	Node id for the node being disconnected from.

Edges are frequently removed due to the removal of a node. This method allows for the effect to be computed only for the remaining node in the graph.

Definition at line 226 of file HeuristicBase.h.

template<typename HImpl>

bool PBQP::HeuristicBase< HImpl >::heuristicReduce ( )

inline

Heuristically reduce one of the nodes in the heuristic reduce list.

Returns: True if a reduction takes place, false if the heuristic reduce list is empty.

Definition at line 196 of file HeuristicBase.h.

Referenced by PBQP::HeuristicBase< Briggs >::reduce().

template<typename HImpl>

bool PBQP::HeuristicBase< HImpl >::optimalReduce ( )

inline

Optimally reduce one of the nodes in the optimal reduce list.

Returns: True if a reduction takes place, false if the optimal reduce list is empty.

Selects a node from the optimal reduce list and removes it, applying R0, R1 or R2 as appropriate based on the selected node's degree.

Definition at line 149 of file HeuristicBase.h.

Referenced by PBQP::HeuristicBase< Briggs >::reduce().

template<typename HImpl>

void PBQP::HeuristicBase< HImpl >::postUpdateEdgeCostts ( Graph::EdgeId eId )

inline

Handle the change in the costs on the given edge.

Parameters

eId Edge id.

Definition at line 209 of file HeuristicBase.h.

template<typename HImpl>

void PBQP::HeuristicBase< HImpl >::preUpdateEdgeCosts ( Graph::EdgeId eId )

inline

Prepare a change in the costs on the given edge.

Parameters

eId Edge id.

Definition at line 203 of file HeuristicBase.h.

template<typename HImpl>

void PBQP::HeuristicBase< HImpl >::reduce ( )

inline

Perform the PBQP reduction process.

Reduces the problem to the empty graph by repeated application of the reduction rules R0, R1, R2 and RN. R0, R1 or R2 are always applied if possible before RN is used.

Definition at line 172 of file HeuristicBase.h.

template<typename HImpl>

void PBQP::HeuristicBase< HImpl >::setup ( )

inline

Initialise the heuristic.

HeuristicBase iterates over all nodes in the problem and adds them to the appropriate list using addToOptimalReduceList or addToHeuristicReduceList based on the result of shouldOptimallyReduce.

This behaviour should be fine for most situations.

Definition at line 132 of file HeuristicBase.h.

template<typename HImpl>

bool PBQP::HeuristicBase< HImpl >::shouldOptimallyReduce ( Graph::NodeId nId )

inline

Decide whether a node should be optimally or heuristically reduced.

Returns: Whether or not the given node should be listed for optimal reduction (via R0, R1 or R2).

HeuristicBase returns true for any node with degree less than 3. This is sane and sensible for many situations, but not all. You can over-ride this method in your derived class if you want a different selection criteria. Note however that your criteria for selecting optimal nodes should be at least as strong as this. I.e. Nodes of degree 3 or higher should not be selected under any circumstances.

Definition at line 108 of file HeuristicBase.h.

template<typename HImpl>

bool PBQP::HeuristicBase< HImpl >::solverRunSimplify ( ) const

inline

Tell the solver to simplify the graph before the reduction phase.

Returns: Whether or not the solver should run a simplification phase prior to the main setup and reduction.

HeuristicBase returns true from this method as it's a sensible default, however you can over-ride it in your derived class if you want different behaviour.

Definition at line 95 of file HeuristicBase.h.

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

HeuristicBase.h

Public Member Functions

Detailed Description

template<typename HImpl> class PBQP::HeuristicBase< HImpl >

Constructor & Destructor Documentation

Member Function Documentation

template<typename HImpl>
class PBQP::HeuristicBase< HImpl >