Detailed Description

uct node selector which balances exploration and exploitation by considering node visits

Author: Gregor Hendel

the UCT node selection rule selects the next leaf according to a mixed score of the node's actual lower bound and the number of times it has been visited so far compared to its parent node.

The idea of UCT node selection for MIP appeared in: Ashish Sabharwal and Horst Samulowitz Guiding Combinatorial Optimization with UCT (2011)

The authors adapted a game-tree exploration scheme called UCB to MIP trees. Starting from the root node as current node, the algorithm selects the current node's child \(N_i\) which maximizes the UCT score

\( \mbox{score}(N_i) := -\mbox{estimate}_{N_i} + \mbox{weight} \cdot \frac{\mbox{visits}(\mbox{parent}(N_i))}{\mbox{visits}(N_i)} \)

where \(\mbox{estimate}\) is the node's lower bound normalized by the root lower bound, and \(\mbox{visits}\) denotes the number of times a leaf in the subtree rooted at this node has been explored so far.

The selected node in the sense of the SCIP node selection is the leaf reached by the above criterion.

The authors suggest that this node selection rule is particularly useful at the beginning of the solving process, but to switch to a different node selection after a number of nodes has been explored to reduce computational overhead. Our implementation uses only information available from the original SCIP tree which does not support the forward path mechanism needed for the most efficient node selection. Instead, the algorithm selects the next leaf by looping over all leaves and comparing the best leaf found so far with the next one. Two leaves l_1, l_2 are compared by following their paths back upwards until their deepest common ancestor \(a\) is reached, together with the two children of \(a\) representing the two paths to l_1, l_2. The leaf represented by the child of \(a\) with higher UCT score is a candidate for the next selected leaf.

The node selector features several parameters:

the nodelimit delimits the number of explored nodes before UCT selection is turned off the weight parameter changes the relevance of the visits quotient in the UCT score (see above score formula) useestimate determines whether the node's estimate or lower bound is taken as estimate

Note: It should be avoided to switch to uct node selection after the branch and bound process has begun because the central UCT score information how often a path was taken is not collected if UCT is inactive. A safe use of UCT is to switch it on before SCIP starts optimization.

Definition in file nodesel_uct.c.

#include "blockmemshell/memory.h"
#include "scip/nodesel_uct.h"
#include "scip/pub_message.h"
#include "scip/pub_nodesel.h"
#include "scip/pub_tree.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	NODESEL_NAME "uct"

#define	NODESEL_DESC "node selector which balances exploration and exploitation "

#define	NODESEL_STDPRIORITY 10

#define	NODESEL_MEMSAVEPRIORITY 0

#define	DEFAULT_WEIGHT 0.1

#define	DEFAULT_NODELIMIT 31

#define	DEFAULT_USEESTIMATE FALSE

#define	INITIALSIZE 1024

#define	MAXNODELIMIT 1000000

Functions
static int	nodeGetVisits (SCIP_NODESELDATA nodeseldata, SCIP_NODE node)

static void	updateVisits (SCIP_NODESELDATA nodeseldata, SCIP_NODE node)

static SCIP_RETCODE	turnoffNodeSelector (SCIP scip, SCIP_NODESEL nodesel)

static SCIP_Real	nodeGetUctScore (SCIP scip, SCIP_NODE node, SCIP_NODESELDATA *nodeseldata)

static int	compareNodes (SCIP scip, SCIP_NODESELDATA nodeseldata, SCIP_NODE node1, SCIP_NODE node2)

static void	selectBestNode (SCIP scip, SCIP_NODE selnode, SCIP_NODESELDATA nodeseldata, SCIP_NODE **nodes, int nnodes)

static SCIP_RETCODE	ensureMemorySize (SCIP scip, SCIP_NODESELDATA nodeseldata)

static	SCIP_DECL_NODESELCOPY (nodeselCopyUct)

static	SCIP_DECL_NODESELINITSOL (nodeselInitsolUct)

static	SCIP_DECL_NODESELEXITSOL (nodeselExitsolUct)

static	SCIP_DECL_NODESELFREE (nodeselFreeUct)

static	SCIP_DECL_NODESELSELECT (nodeselSelectUct)

static	SCIP_DECL_NODESELCOMP (nodeselCompUct)

SCIP_RETCODE	SCIPincludeNodeselUct (SCIP *scip)

Macro Definition Documentation

◆ NODESEL_NAME

#define NODESEL_NAME "uct"

Definition at line 84 of file nodesel_uct.c.

◆ NODESEL_DESC

#define NODESEL_DESC "node selector which balances exploration and exploitation "

Definition at line 85 of file nodesel_uct.c.

◆ NODESEL_STDPRIORITY

#define NODESEL_STDPRIORITY 10

Definition at line 86 of file nodesel_uct.c.

◆ NODESEL_MEMSAVEPRIORITY

#define NODESEL_MEMSAVEPRIORITY 0

Definition at line 87 of file nodesel_uct.c.

◆ DEFAULT_WEIGHT

#define DEFAULT_WEIGHT 0.1

default values for user parameters weight of node visits in UCT score

Definition at line 90 of file nodesel_uct.c.

◆ DEFAULT_NODELIMIT

#define DEFAULT_NODELIMIT 31

limit of node selections after which UCT node selection is turned off

Definition at line 91 of file nodesel_uct.c.

◆ DEFAULT_USEESTIMATE

#define DEFAULT_USEESTIMATE FALSE

should the estimate (TRUE) or the lower bound of a node be used for UCT score?

Definition at line 92 of file nodesel_uct.c.

◆ INITIALSIZE

#define INITIALSIZE 1024

initial size of node visits array (increased dynamically if required)

Definition at line 93 of file nodesel_uct.c.

◆ MAXNODELIMIT

#define MAXNODELIMIT 1000000

the maximum value for user parameter nodelimit

Definition at line 94 of file nodesel_uct.c.

Function Documentation

◆ nodeGetVisits()

static int nodeGetVisits	(	SCIP_NODESELDATA *	nodeseldata,
		SCIP_NODE *	node
	)

static

get the number times node has been visited so far

Parameters

nodeseldata	node selector data
node	the node in question

Definition at line 117 of file nodesel_uct.c.

References NULL, and SCIPnodeGetNumber().

Referenced by nodeGetUctScore().

◆ updateVisits()

static void updateVisits	(	SCIP_NODESELDATA *	nodeseldata,
		SCIP_NODE *	node
	)

static

increases the visits counter along the path from node to the root node

Parameters

nodeseldata	node selector data
node	leaf node of path along which the visits are backpropagated

Definition at line 139 of file nodesel_uct.c.

References NULL, SCIPnodeGetDepth(), SCIPnodeGetNumber(), and SCIPnodeGetParent().

Referenced by SCIP_DECL_NODESELSELECT().

◆ turnoffNodeSelector()

static SCIP_RETCODE turnoffNodeSelector	(	SCIP *	scip,
		SCIP_NODESEL *	nodesel
	)

static

switches to a different node selection rule by assigning the lowest priority of all node selectors to uct

Parameters

scip	SCIP data structure
nodesel	the node selector to be turned off

Definition at line 169 of file nodesel_uct.c.

References MAX, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_NORMAL, SCIPgetNNodesels(), SCIPgetNodesels(), SCIPnodeselGetStdPriority(), SCIPsetNodeselStdPriority(), and SCIPverbMessage().

Referenced by SCIP_DECL_NODESELSELECT().

◆ nodeGetUctScore()

static SCIP_Real nodeGetUctScore	(	SCIP *	scip,
		SCIP_NODE *	node,
		SCIP_NODESELDATA *	nodeseldata
	)

static

returns UCT score of node; the UCT score is a mixture of the node's lower bound or estimate and the number of times it has been visited so far in relation with the number of times its parent has been visited so far

Parameters

scip	SCIP data structure
node	the node for which UCT score is requested
nodeseldata	node selector data

Definition at line 202 of file nodesel_uct.c.

References MAX, MIN, nodeGetVisits(), NULL, REALABS, SCIP_Real, SCIPgetLowerboundRoot(), SCIPisEQ(), SCIPisGE(), SCIPisInfinity(), SCIPnodeGetEstimate(), SCIPnodeGetLowerbound(), and SCIPnodeGetParent().

Referenced by compareNodes().

◆ compareNodes()

static int compareNodes	(	SCIP *	scip,
		SCIP_NODESELDATA *	nodeseldata,
		SCIP_NODE *	node1,
		SCIP_NODE *	node2
	)

static

compares two leaf nodes by comparing the UCT scores of the two children of their deepest common ancestor

Parameters

scip	SCIP data structure
nodeseldata	node selector data
node1	first node for comparison
node2	second node for comparisons

Definition at line 254 of file nodesel_uct.c.

References nodeGetUctScore(), NULL, SCIP_Real, SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPnodeGetDepth(), and SCIPnodeGetParent().

Referenced by selectBestNode().

◆ selectBestNode()

static void selectBestNode	(	SCIP *	scip,
		SCIP_NODE **	selnode,
		SCIP_NODESELDATA *	nodeseldata,
		SCIP_NODE **	nodes,
		int	nnodes
	)

static

selects the best node among nodes with respect to UCT score

Parameters

scip	SCIP data structure
selnode	pointer to store the selected node, needs not be empty
nodeseldata	node selector data
nodes	array of nodes to select from
nnodes	size of the nodes array

Definition at line 307 of file nodesel_uct.c.

References compareNodes(), nnodes, and NULL.

Referenced by SCIP_DECL_NODESELSELECT().

◆ ensureMemorySize()

static SCIP_RETCODE ensureMemorySize	(	SCIP *	scip,
		SCIP_NODESELDATA *	nodeseldata
	)

static

keeps visits array large enough to save visits for all nodes in the branch and bound tree

Parameters

scip	SCIP data structure
nodeseldata	node selector data

Definition at line 336 of file nodesel_uct.c.

References BMSclearMemoryArray, INITIALSIZE, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocClearMemoryArray, SCIPdebugMsg, SCIPgetNNodes(), and SCIPreallocMemoryArray.

Referenced by SCIP_DECL_NODESELSELECT().

◆ SCIP_DECL_NODESELCOPY()

static SCIP_DECL_NODESELCOPY ( nodeselCopyUct )

static

copy method for node selector plugins (called when SCIP copies plugins)

Definition at line 376 of file nodesel_uct.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPincludeNodeselUct().

◆ SCIP_DECL_NODESELINITSOL()

static SCIP_DECL_NODESELINITSOL ( nodeselInitsolUct )

static

solving process initialization method of node selector (called when branch and bound process is about to begin)

Definition at line 386 of file nodesel_uct.c.

References NULL, SCIP_OKAY, SCIPnodeselGetData(), and SCIPnodeselGetStdPriority().

◆ SCIP_DECL_NODESELEXITSOL()

static SCIP_DECL_NODESELEXITSOL ( nodeselExitsolUct )

static

solving process deinitialization method of node selector (called when branch and bound process data gets freed)

Definition at line 404 of file nodesel_uct.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArray, SCIPnodeselGetData(), and SCIPsetNodeselStdPriority().

◆ SCIP_DECL_NODESELFREE()

static SCIP_DECL_NODESELFREE ( nodeselFreeUct )

static

destructor of node selector to free user data (called when SCIP is exiting)

Definition at line 430 of file nodesel_uct.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeMemoryArray, SCIPnodeselGetData(), and SCIPnodeselSetData().

◆ SCIP_DECL_NODESELSELECT()

static SCIP_DECL_NODESELSELECT ( nodeselSelectUct )

static

node selection method of node selector

Definition at line 451 of file nodesel_uct.c.

References ensureMemorySize(), NODESEL_NAME, NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMsg, SCIPerrorMessage, SCIPgetNNodes(), SCIPgetNNodesLeft(), SCIPgetOpenNodesData(), SCIPnodeGetNumber(), SCIPnodeselGetData(), SCIPnodeselGetName(), selectBestNode(), turnoffNodeSelector(), and updateVisits().

◆ SCIP_DECL_NODESELCOMP()

static SCIP_DECL_NODESELCOMP ( nodeselCompUct )

static

node comparison method of UCT node selector

Definition at line 518 of file nodesel_uct.c.

References SCIP_Real, SCIPisGT(), SCIPisLT(), and SCIPnodeGetLowerbound().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ NODESEL_NAME

◆ NODESEL_DESC

◆ NODESEL_STDPRIORITY

◆ NODESEL_MEMSAVEPRIORITY

◆ DEFAULT_WEIGHT

◆ DEFAULT_NODELIMIT

◆ DEFAULT_USEESTIMATE

◆ INITIALSIZE

◆ MAXNODELIMIT

Function Documentation

◆ nodeGetVisits()

◆ updateVisits()

◆ turnoffNodeSelector()

◆ nodeGetUctScore()

◆ compareNodes()

◆ selectBestNode()

◆ ensureMemorySize()

◆ SCIP_DECL_NODESELCOPY()

◆ SCIP_DECL_NODESELINITSOL()

◆ SCIP_DECL_NODESELEXITSOL()

◆ SCIP_DECL_NODESELFREE()

◆ SCIP_DECL_NODESELSELECT()

◆ SCIP_DECL_NODESELCOMP()