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-2019 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file nodesel_breadthfirst.h
17  * @ingroup NODESELECTORS
18  * @brief node selector for breadth-first search
19  * @author Stefan Heinz
20  * @author Gregor Hendel
21  *
22  * This node selector performs breadth-first search, i.e., it completely evaluates an entire level of the search tree before
23  * proceeding to the next level. At one level, nodes are processed in the order they were created by the branching rule.
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
29 #include "scip/pub_message.h"
30 #include "scip/pub_nodesel.h"
31 #include "scip/pub_tree.h"
32 #include "scip/scip_message.h"
33 #include "scip/scip_nodesel.h"
34 #include "scip/scip_tree.h"
35 #include <string.h>
36 
37 #define NODESEL_NAME "breadthfirst"
38 #define NODESEL_DESC "breadth first search"
39 #define NODESEL_STDPRIORITY -10000
40 #define NODESEL_MEMSAVEPRIORITY -1000000
41 
42 /*
43  * Callback methods
44  */
45 
46 /** copy method for node selector plugins (called when SCIP copies plugins) */
47 static
48 SCIP_DECL_NODESELCOPY(nodeselCopyBreadthfirst)
49 { /*lint --e{715}*/
50  assert(scip != NULL);
51  assert(nodesel != NULL);
52  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
53 
54  /* call inclusion method of node selector */
56 
57  return SCIP_OKAY;
58 }
59 
60 /** node selection method of node selector */
61 static
62 SCIP_DECL_NODESELSELECT(nodeselSelectBreadthfirst)
63 { /*lint --e{715}*/
64  assert(nodesel != NULL);
65  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
66  assert(scip != NULL);
67  assert(selnode != NULL);
68 
69  /* siblings come before leaves at the same level. Sometimes it can occur that no leaves are left except for children */
70  *selnode = SCIPgetBestSibling(scip);
71  if( *selnode == NULL )
72  {
73  *selnode = SCIPgetBestLeaf(scip);
74  if( *selnode == NULL )
75  *selnode=SCIPgetBestChild(scip);
76  }
77  if( *selnode != NULL )
78  {
79  SCIPdebugMsg(scip, "Selecting next node number %" SCIP_LONGINT_FORMAT " at depth %d\n", SCIPnodeGetNumber(*selnode), SCIPnodeGetDepth(*selnode));
80  }
81 
82  return SCIP_OKAY;
83 }
84 
85 
86 /** node comparison method of breadth first search: nodes with lower depth are preferred; in case of a tie, the node
87  * which was created earlier (and therefore has a smaller node number) is preferred */
88 static
89 SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
90 { /*lint --e{715}*/
91  int depth1;
92  int depth2;
93 
94  assert(nodesel != NULL);
95  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
96  assert(scip != NULL);
97 
98  depth1 = SCIPnodeGetDepth(node1);
99  depth2 = SCIPnodeGetDepth(node2);
100 
101  /* if depths differ, prefer node with smaller depth */
102  if( depth1 < depth2 )
103  return -1;
104  else if( depth1 > depth2 )
105  return +1;
106  else
107  {
108  /* depths are equal; prefer node with smaller number */
109  SCIP_Longint number1;
110  SCIP_Longint number2;
111 
112  number1 = SCIPnodeGetNumber(node1);
113  number2 = SCIPnodeGetNumber(node2);
114  assert(number1 != number2);
115 
116  if( number1 < number2 )
117  return -1;
118  else
119  return +1;
120  }
121 }
122 
123 /*
124  * breadth first specific interface methods
125  */
126 
127 /** creates the node selector for breadth first search and includes it in SCIP */
129  SCIP* scip /**< SCIP data structure */
130  )
131 {
132  SCIP_NODESEL* nodesel;
133 
134  /* include node selector */
136  nodeselSelectBreadthfirst, nodeselCompBreadthfirst, NULL) );
137 
138  assert(nodesel != NULL);
139 
140  /* set non-fundamental callback functions via setter functions */
141  SCIP_CALL ( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyBreadthfirst) );
142 
143  return SCIP_OKAY;
144 }
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:309
#define NULL
Definition: def.h:253
public methods for branch and bound tree
public methods for node selector plugins
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:341
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:128
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7347
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7357
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:325
#define SCIPdebugMsg
Definition: scip_message.h:69
public methods for the branch-and-bound tree
#define NODESEL_STDPRIORITY
#define SCIP_CALL(x)
Definition: def.h:365
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:93
#define SCIP_LONGINT_FORMAT
Definition: def.h:156
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1038
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:149
static SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
#define NODESEL_DESC
node selector for breadth-first search