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_SHADOWNODESCIPshadowTreeGetShadowNodeFromNodeNumber (SCIP_SHADOWTREE *shadowtree, SCIP_Longint nodeid)
 
SCIP_SHADOWNODESCIPshadowTreeGetShadowNode (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_SHADOWTREESCIPgetShadowTree (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.

◆ EVENTHDLR_DESC

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

Definition at line 74 of file event_shadowtree.c.

◆ NODEMAP_MAX_INITIAL_SIZE

#define NODEMAP_MAX_INITIAL_SIZE   10000

Definition at line 75 of file event_shadowtree.c.

◆ NODEMAP_MAX_INITIAL_SIZE_2LOG

#define NODEMAP_MAX_INITIAL_SIZE_2LOG   14

Definition at line 76 of file event_shadowtree.c.

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
scipSCIP data structure
eventhdlrevent 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
shadowtreepointer to the shadow tree
nodeidindex 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
shadowtreepointer to the shadow tree
nodenode from the actual branch-and-bound tree

Definition at line 158 of file event_shadowtree.c.

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

Referenced by applyOrbitalBranchingPropagations(), applyOrbitalReductionPropagations(), SCIP_DECL_EVENTEXEC(), shadowtreeFillNodeDepthBranchIndices(), and shadowtreeUndoNodeDepthBranchIndices().

◆ SCIP_DECL_EVENTEXEC() [1/3]

◆ SCIP_DECL_EVENTEXEC() [2/3]

◆ SCIP_DECL_EVENTEXEC() [3/3]

static SCIP_DECL_EVENTEXEC ( eventExec  )
static

◆ freeShadowTree()

◆ 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()

◆ 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
eventhdlrevent handler

Definition at line 624 of file event_shadowtree.c.

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

Referenced by SCIPlexicographicReductionPropagate(), and SCIPorbitalReductionPropagate().

◆ 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
scipSCIP data structure
eventhdlrevent 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 addComponent(), and lexdataCreate().

◆ SCIPincludeEventHdlrShadowTree()

SCIP_RETCODE SCIPincludeEventHdlrShadowTree ( SCIP scip,
SCIP_EVENTHDLR **  eventhdlrptr 
)

creates event handler for event

Parameters
scipSCIP data structure
eventhdlrptrpointer 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().