Scippy

SCIP

Solving Constraint Integer Programs

nodesel_breadthfirst.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file nodesel_breadthfirst.h
17  * @ingroup DEFPLUGINS_NODESEL
18  * @ingroup NODESELECTORS
19  * @brief node selector for breadth-first search
20  * @author Stefan Heinz
21  * @author Gregor Hendel
22  *
23  * This node selector performs breadth-first search, i.e., it completely evaluates an entire level of the search tree before
24  * proceeding to the next level. At one level, nodes are processed in the order they were created by the branching rule.
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 
30 #include "scip/pub_message.h"
31 #include "scip/pub_nodesel.h"
32 #include "scip/pub_tree.h"
33 #include "scip/scip_message.h"
34 #include "scip/scip_nodesel.h"
35 #include "scip/scip_tree.h"
36 #include <string.h>
37 
38 #define NODESEL_NAME "breadthfirst"
39 #define NODESEL_DESC "breadth first search"
40 #define NODESEL_STDPRIORITY -10000
41 #define NODESEL_MEMSAVEPRIORITY -1000000
42 
43 /*
44  * Callback methods
45  */
46 
47 /** copy method for node selector plugins (called when SCIP copies plugins) */
48 static
49 SCIP_DECL_NODESELCOPY(nodeselCopyBreadthfirst)
50 { /*lint --e{715}*/
51  assert(scip != NULL);
52  assert(nodesel != NULL);
53  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
54 
55  /* call inclusion method of node selector */
57 
58  return SCIP_OKAY;
59 }
60 
61 /** node selection method of node selector */
62 static
63 SCIP_DECL_NODESELSELECT(nodeselSelectBreadthfirst)
64 { /*lint --e{715}*/
65  assert(nodesel != NULL);
66  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
67  assert(scip != NULL);
68  assert(selnode != NULL);
69 
70  /* siblings come before leaves at the same level. Sometimes it can occur that no leaves are left except for children */
71  *selnode = SCIPgetBestSibling(scip);
72  if( *selnode == NULL )
73  {
74  *selnode = SCIPgetBestLeaf(scip);
75  if( *selnode == NULL )
76  *selnode=SCIPgetBestChild(scip);
77  }
78  if( *selnode != NULL )
79  {
80  SCIPdebugMsg(scip, "Selecting next node number %" SCIP_LONGINT_FORMAT " at depth %d\n", SCIPnodeGetNumber(*selnode), SCIPnodeGetDepth(*selnode));
81  }
82 
83  return SCIP_OKAY;
84 }
85 
86 
87 /** node comparison method of breadth first search: nodes with lower depth are preferred; in case of a tie, the node
88  * which was created earlier (and therefore has a smaller node number) is preferred */
89 static
90 SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
91 { /*lint --e{715}*/
92  int depth1;
93  int depth2;
94 
95  assert(nodesel != NULL);
96  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
97  assert(scip != NULL);
98 
99  depth1 = SCIPnodeGetDepth(node1);
100  depth2 = SCIPnodeGetDepth(node2);
101 
102  /* if depths differ, prefer node with smaller depth */
103  if( depth1 < depth2 )
104  return -1;
105  else if( depth1 > depth2 )
106  return +1;
107  else
108  {
109  /* depths are equal; prefer node with smaller number */
110  SCIP_Longint number1;
111  SCIP_Longint number2;
112 
113  number1 = SCIPnodeGetNumber(node1);
114  number2 = SCIPnodeGetNumber(node2);
115  assert(number1 != number2);
116 
117  if( number1 < number2 )
118  return -1;
119  else
120  return +1;
121  }
122 }
123 
124 /*
125  * breadth first specific interface methods
126  */
127 
128 /** creates the node selector for breadth first search and includes it in SCIP */
130  SCIP* scip /**< SCIP data structure */
131  )
132 {
133  SCIP_NODESEL* nodesel;
134 
135  /* include node selector */
137  nodeselSelectBreadthfirst, nodeselCompBreadthfirst, NULL) );
138 
139  assert(nodesel != NULL);
140 
141  /* set non-fundamental callback functions via setter functions */
142  SCIP_CALL ( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyBreadthfirst) );
143 
144  return SCIP_OKAY;
145 }
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:310
public methods for branch and bound tree
public methods for node selector plugins
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:342
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:129
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7438
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7448
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:326
#define SCIPdebugMsg
Definition: scip_message.h:69
public methods for the branch-and-bound tree
#define NULL
Definition: lpi_spx1.cpp:155
#define NODESEL_STDPRIORITY
#define SCIP_CALL(x)
Definition: def.h:370
public methods for node selectors
#define NODESEL_MEMSAVEPRIORITY
#define NODESEL_NAME
static SCIP_DECL_NODESELSELECT(nodeselSelectBreadthfirst)
SCIP_RETCODE SCIPincludeNodeselBasic(SCIP *scip, SCIP_NODESEL **nodesel, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
Definition: scip_nodesel.c:94
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1043
SCIP_RETCODE SCIPincludeNodeselBreadthfirst(SCIP *scip)
public methods for message output
static SCIP_DECL_NODESELCOPY(nodeselCopyBreadthfirst)
public methods for message handling
#define SCIP_Longint
Definition: def.h:148
static SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
#define NODESEL_DESC
node selector for breadth-first search