Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

event handler for maintaining the unmodified branch-and-bound tree

Author: Jasper van Doornmalen

It is possible that SCIP detects that variable bounds can be restricted globally further than formerly known. In that case, it is decided to update the global bounds of these variables, and modify the history of the branching decisions this way. This breaks methods that depend on the assumption that historic choices in the branch-and-bound tree remain unmodified througout the search, e.g., dynamic symmetry handling constraints.

This event handler registers decisions made by the branch-and-bound tree directly at the moment of branching, and does not modify those at later stages of the solve.

Definition in file event_shadowtree.c.

#include "blockmemshell/memory.h"
#include "scip/debug.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_var.h"
#include "scip/struct_var.h"
#include "scip/type_var.h"
#include "scip/scip.h"
#include "scip/scip_branch.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_sol.h"
#include "scip/scip_var.h"
#include "scip/struct_scip.h"
#include "scip/struct_mem.h"
#include "scip/struct_tree.h"
#include "scip/symmetry.h"
#include <ctype.h>
#include <string.h>
#include "scip/event_shadowtree.h"

Go to the source code of this file.

Macros
#define	EVENTHDLR_NAME "event_shadowtree"

#define	EVENTHDLR_DESC "event handler for maintaining the unmodified branch-and-bound tree"

#define	NODEMAP_MAX_INITIAL_SIZE 10000

#define	NODEMAP_MAX_INITIAL_SIZE_2LOG 14

Functions
static	SCIP_DECL_HASHGETKEY (hashGetKeyShadowNode)

static	SCIP_DECL_HASHKEYEQ (hashKeyEqShadowNode)

static	SCIP_DECL_HASHKEYVAL (hashKeyValShadowNode)

SCIP_Real	SCIPgetShadowTreeEventHandlerExecutionTime (SCIP scip, SCIP_EVENTHDLR eventhdlr)

SCIP_SHADOWNODE *	SCIPshadowTreeGetShadowNodeFromNodeNumber (SCIP_SHADOWTREE *shadowtree, SCIP_Longint nodeid)

SCIP_SHADOWNODE *	SCIPshadowTreeGetShadowNode (SCIP_SHADOWTREE shadowtree, SCIP_NODE node)

static	SCIP_DECL_EVENTEXEC (eventExecNodeBranched)

static	SCIP_DECL_EVENTEXEC (eventExecNodeDeleted)

static	SCIP_DECL_EVENTEXEC (eventExec)

static SCIP_RETCODE	freeShadowTree (SCIP scip, SCIP_SHADOWTREE shadowtree)

static	SCIP_DECL_EVENTFREE (eventFreeShadowTree)

static	SCIP_DECL_EVENTINITSOL (eventInitsolShadowTree)

static	SCIP_DECL_EVENTEXITSOL (eventExitsolShadowTree)

SCIP_SHADOWTREE *	SCIPgetShadowTree (SCIP_EVENTHDLR *eventhdlr)

SCIP_RETCODE	SCIPactivateShadowTree (SCIP scip, SCIP_EVENTHDLR eventhdlr)

SCIP_RETCODE	SCIPincludeEventHdlrShadowTree (SCIP scip, SCIP_EVENTHDLR *eventhdlrptr)

Macro Definition Documentation

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "event_shadowtree"

Definition at line 73 of file event_shadowtree.c.

Referenced by SCIP_DECL_EVENTEXEC(), SCIPactivateShadowTree(), SCIPgetShadowTree(), and SCIPincludeEventHdlrShadowTree().

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC "event handler for maintaining the unmodified branch-and-bound tree"

Definition at line 74 of file event_shadowtree.c.

Referenced by SCIPincludeEventHdlrShadowTree().

◆ NODEMAP_MAX_INITIAL_SIZE

#define NODEMAP_MAX_INITIAL_SIZE 10000

Definition at line 75 of file event_shadowtree.c.

Referenced by SCIP_DECL_EVENTINITSOL().

◆ NODEMAP_MAX_INITIAL_SIZE_2LOG

#define NODEMAP_MAX_INITIAL_SIZE_2LOG 14

Definition at line 76 of file event_shadowtree.c.

Referenced by SCIP_DECL_EVENTINITSOL().

Function Documentation

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( hashGetKeyShadowNode )

static

hash key for SCIP_SHADOWNODE

Definition at line 102 of file event_shadowtree.c.

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashKeyEqShadowNode )

static

returns TRUE iff the indices of both node numbers are equal

Definition at line 109 of file event_shadowtree.c.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashKeyValShadowNode )

static

returns the hash value of the key

Definition at line 116 of file event_shadowtree.c.

◆ SCIPgetShadowTreeEventHandlerExecutionTime()

SCIP_Real SCIPgetShadowTreeEventHandlerExecutionTime	(	SCIP *	scip,
		SCIP_EVENTHDLR *	eventhdlr
	)

get the time spent in the shadow tree eventhdlr

Parameters

scip	SCIP data structure
eventhdlr	event handler

Definition at line 123 of file event_shadowtree.c.

References NULL, SCIPeventhdlrGetData(), and SCIPgetClockTime().

Referenced by SCIP_DECL_TABLEOUTPUT().

◆ SCIPshadowTreeGetShadowNodeFromNodeNumber()

SCIP_SHADOWNODE* SCIPshadowTreeGetShadowNodeFromNodeNumber	(	SCIP_SHADOWTREE *	shadowtree,
		SCIP_Longint	nodeid
	)

given a node number, returns the node in the shadow tree, or NULL if it doesn't exist

Parameters

shadowtree	pointer to the shadow tree
nodeid	index of the node, equivalent to the standard branch and bound tree

Definition at line 141 of file event_shadowtree.c.

References SCIP_ShadowNode::nodeid, SCIP_ShadowTree::nodemap, NULL, and SCIPhashtableRetrieve().

Referenced by SCIPshadowTreeGetShadowNode().

◆ SCIPshadowTreeGetShadowNode()

SCIP_SHADOWNODE* SCIPshadowTreeGetShadowNode	(	SCIP_SHADOWTREE *	shadowtree,
		SCIP_NODE *	node
	)

given a node, returns the node in the shadowtree, or NULL if it doesn't exist

Parameters

shadowtree	pointer to the shadow tree
node	node from the actual branch-and-bound tree

Definition at line 158 of file event_shadowtree.c.

References NULL, SCIPnodeGetNumber(), and SCIPshadowTreeGetShadowNodeFromNodeNumber().

Referenced by identifyOrbitalSymmetriesBroken(), SCIP_DECL_EVENTEXEC(), shadowtreeFillNodeDepthBranchIndices(), and shadowtreeUndoNodeDepthBranchIndices().

◆ SCIP_DECL_EVENTEXEC() [1/3]

static SCIP_DECL_EVENTEXEC ( eventExecNodeBranched )

static

event handler for branching event

Definition at line 175 of file event_shadowtree.c.

References SCIP_ShadowBoundUpdate::boundchgtype, SCIP_ShadowNode::branchingdecisions, SCIP_ShadowNode::children, SCIP_ShadowNode::nbranchingdecisions, SCIP_ShadowNode::nchildren, SCIP_ShadowBoundUpdate::newbound, SCIP_ShadowNode::nodeid, SCIP_ShadowTree::nodemap, SCIP_ShadowNode::npropagations, NULL, SCIP_ShadowNode::parent, SCIP_ShadowNode::propagations, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_CALL, SCIP_EVENTTYPE_NODEBRANCHED, SCIP_NODETYPE_FOCUSNODE, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPboundchgGetBoundchgtype(), SCIPboundchgGetBoundtype(), SCIPboundchgGetNewbound(), SCIPboundchgGetVar(), SCIPcalcMemGrowSize(), SCIPdomchgGetBoundchg(), SCIPdomchgGetNBoundchgs(), SCIPeventGetNode(), SCIPeventGetType(), SCIPeventhdlrGetData(), SCIPfreeBufferArray, SCIPgetChildren(), SCIPgetFocusNode(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPinProbing(), SCIPnodeGetDomchg(), SCIPnodeGetNumber(), SCIPnodeGetType(), SCIPreallocBufferArray, SCIPshadowTreeGetShadowNode(), and SCIP_ShadowBoundUpdate::var.

◆ SCIP_DECL_EVENTEXEC() [2/3]

static SCIP_DECL_EVENTEXEC ( eventExecNodeDeleted )

static

event handler for node deletion event

Definition at line 339 of file event_shadowtree.c.

References SCIP_ShadowNode::children, SCIP_ShadowNode::nchildren, SCIP_ShadowNode::nodeid, SCIP_ShadowTree::nodemap, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODEDELETE, SCIP_NODETYPE_PROBINGNODE, SCIP_OKAY, SCIPeventGetNode(), SCIPeventGetType(), SCIPeventhdlrGetData(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPhashtableRemove(), SCIPnodeGetNumber(), SCIPnodeGetType(), and SCIPshadowTreeGetShadowNode().

◆ SCIP_DECL_EVENTEXEC() [3/3]

static SCIP_DECL_EVENTEXEC ( eventExec )

static

execution method for all events handled by this eventhandler

Definition at line 422 of file event_shadowtree.c.

References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_ERROR, SCIP_EVENTTYPE_NODEBRANCHED, SCIP_EVENTTYPE_NODEDELETE, SCIP_OKAY, SCIPerrorMessage, SCIPeventGetType(), SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), SCIPstartClock(), and SCIPstopClock().

◆ freeShadowTree()

static SCIP_RETCODE freeShadowTree	(	SCIP *	scip,
		SCIP_SHADOWTREE *	shadowtree
	)

static

frees shadow tree data structure

Parameters

scip	SCIP data structure
shadowtree	pointer to shadow tree

Definition at line 456 of file event_shadowtree.c.

References SCIP_ShadowNode::branchingdecisions, SCIP_ShadowNode::children, SCIP_ShadowNode::nbranchingdecisions, SCIP_ShadowNode::nchildren, SCIP_ShadowTree::nodemap, SCIP_ShadowNode::npropagations, NULL, SCIP_ShadowNode::propagations, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPhashtableFree(), SCIPhashtableGetEntry(), and SCIPhashtableGetNEntries().

Referenced by SCIP_DECL_EVENTEXITSOL(), and SCIP_DECL_EVENTFREE().

◆ SCIP_DECL_EVENTFREE()

static SCIP_DECL_EVENTFREE ( eventFreeShadowTree )

static

destructor of event handler to free shadow tree data (called when SCIP is exiting)

Definition at line 502 of file event_shadowtree.c.

References freeShadowTree(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPeventhdlrGetData(), SCIPfreeBlockMemory, SCIPfreeClock(), and SCIPgetStage().

◆ SCIP_DECL_EVENTINITSOL()

static SCIP_DECL_EVENTINITSOL ( eventInitsolShadowTree )

static

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

Definition at line 531 of file event_shadowtree.c.

References SCIP_ShadowNode::branchingdecisions, SCIP_ShadowNode::children, MIN, SCIP_ShadowNode::nbranchingdecisions, SCIP_ShadowNode::nchildren, SCIP_ShadowNode::nodeid, SCIP_ShadowTree::nodemap, NODEMAP_MAX_INITIAL_SIZE, NODEMAP_MAX_INITIAL_SIZE_2LOG, SCIP_ShadowNode::npropagations, NULL, SCIP_ShadowNode::parent, SCIP_ShadowNode::propagations, SCIP_CALL, SCIP_EVENTTYPE_NODEBRANCHED, SCIP_EVENTTYPE_NODEDELETE, SCIP_OKAY, SCIPallocBlockMemory, SCIPcatchEvent(), SCIPeventhdlrGetData(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPhashtableCreate(), SCIPhashtableInsert(), and SCIPisTransformed().

◆ SCIP_DECL_EVENTEXITSOL()

static SCIP_DECL_EVENTEXITSOL ( eventExitsolShadowTree )

static

solving process deinitialization method of event handler (called before branch and bound process data is freed)

Definition at line 591 of file event_shadowtree.c.

References freeShadowTree(), NULL, SCIP_CALL, SCIP_EVENTTYPE_NODEBRANCHED, SCIP_EVENTTYPE_NODEDELETE, SCIP_OKAY, SCIPdropEvent(), SCIPeventhdlrGetData(), SCIPfreeBlockMemory, and SCIPisTransformed().

◆ SCIPgetShadowTree()

SCIP_SHADOWTREE* SCIPgetShadowTree ( SCIP_EVENTHDLR * eventhdlr )

gets the shadow tree

Parameters

eventhdlr event handler

Definition at line 624 of file event_shadowtree.c.

References EVENTHDLR_NAME, NULL, SCIPeventhdlrGetData(), and SCIPeventhdlrGetName().

Referenced by identifyOrbitalSymmetriesBroken(), and SCIPlexicographicReductionPropagate().

◆ SCIPactivateShadowTree()

SCIP_RETCODE SCIPactivateShadowTree	(	SCIP *	scip,
		SCIP_EVENTHDLR *	eventhdlr
	)

activates shadow tree eventhandler if it is not already activated (which keeps a copy of the tree)

Parameters

scip	SCIP data structure
eventhdlr	event handler

Definition at line 639 of file event_shadowtree.c.

References EVENTHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcheckStage(), SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), and TRUE.

Referenced by identifyOrbitalSymmetriesBroken(), and lexdataCreate().

◆ SCIPincludeEventHdlrShadowTree()

SCIP_RETCODE SCIPincludeEventHdlrShadowTree	(	SCIP *	scip,
		SCIP_EVENTHDLR **	eventhdlrptr
	)

creates event handler for event

Parameters

scip	SCIP data structure
eventhdlrptr	pointer to store the event handler

Definition at line 663 of file event_shadowtree.c.

References EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPcreateClock(), SCIPincludeEventhdlrBasic(), SCIPsetEventhdlrExitsol(), SCIPsetEventhdlrFree(), and SCIPsetEventhdlrInitsol().

Referenced by SCIPincludePropSymmetry().