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-2016 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 email to 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 
28 #include <assert.h>
29 #include <string.h>
30 
32 
33 
34 #define NODESEL_NAME "breadthfirst"
35 #define NODESEL_DESC "breadth first search"
36 #define NODESEL_STDPRIORITY -10000
37 #define NODESEL_MEMSAVEPRIORITY -1000000
38 
39 /*
40  * Callback methods
41  */
42 
43 /** copy method for node selector plugins (called when SCIP copies plugins) */
44 static
45 SCIP_DECL_NODESELCOPY(nodeselCopyBreadthfirst)
46 { /*lint --e{715}*/
47  assert(scip != NULL);
48  assert(nodesel != NULL);
49  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
50 
51  /* call inclusion method of node selector */
53 
54  return SCIP_OKAY;
55 }
56 
57 /** node selection method of node selector */
58 static
59 SCIP_DECL_NODESELSELECT(nodeselSelectBreadthfirst)
60 { /*lint --e{715}*/
61  assert(nodesel != NULL);
62  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
63  assert(scip != NULL);
64  assert(selnode != NULL);
65 
66  /* siblings come before leaves at the same level. Sometimes it can occur that no leaves are left except for children */
67  *selnode = SCIPgetBestSibling(scip);
68  if( *selnode == NULL )
69  {
70  *selnode = SCIPgetBestLeaf(scip);
71  if( *selnode == NULL )
72  *selnode=SCIPgetBestChild(scip);
73  }
74  if( *selnode != NULL )
75  {
76  SCIPdebugMessage("Selecting next node number %" SCIP_LONGINT_FORMAT " at depth %d\n", SCIPnodeGetNumber(*selnode), SCIPnodeGetDepth(*selnode));
77  }
78 
79  return SCIP_OKAY;
80 }
81 
82 
83 /** node comparison method of breadth first search: nodes with lower depth are preferred; in case of a tie, the node
84  * which was created earlier (and therefore has a smaller node number) is preferred */
85 static
86 SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
87 { /*lint --e{715}*/
88  int depth1;
89  int depth2;
90 
91  assert(nodesel != NULL);
92  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
93  assert(scip != NULL);
94 
95  depth1 = SCIPnodeGetDepth(node1);
96  depth2 = SCIPnodeGetDepth(node2);
97 
98  /* if depths differ, prefer node with smaller depth */
99  if( depth1 < depth2 )
100  return -1;
101  else if( depth1 > depth2 )
102  return +1;
103  else
104  {
105  /* depths are equal; prefer node with smaller number */
106  SCIP_Longint number1;
107  SCIP_Longint number2;
108 
109  number1 = SCIPnodeGetNumber(node1);
110  number2 = SCIPnodeGetNumber(node2);
111  assert(number1 != number2);
112 
113  if( number1 < number2 )
114  return -1;
115  else
116  return +1;
117  }
118 }
119 
120 /*
121  * breadth first specific interface methods
122  */
123 
124 /** creates the node selector for breadth first search and includes it in SCIP */
126  SCIP* scip /**< SCIP data structure */
127  )
128 {
129  SCIP_NODESELDATA* nodeseldata;
130  SCIP_NODESEL* nodesel;
131 
132  /* create breadthfirst node selector data */
133  nodeseldata = NULL;
134 
135  /* include node selector */
137  nodeselSelectBreadthfirst, nodeselCompBreadthfirst, nodeseldata) );
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.c:37002
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip.c:8028
#define NULL
Definition: lpi_spx.cpp:130
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7026
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_CALL(x)
Definition: def.h:266
#define SCIPdebugMessage
Definition: pub_message.h:77
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.c:7992
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7016
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip.c:37034
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:38
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip.c:37018
#define NODESEL_STDPRIORITY
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:992
#define NODESEL_MEMSAVEPRIORITY
#define NODESEL_NAME
static SCIP_DECL_NODESELSELECT(nodeselSelectBreadthfirst)
static SCIP_DECL_NODESELCOPY(nodeselCopyBreadthfirst)
#define SCIP_Longint
Definition: def.h:112
static SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
#define NODESEL_DESC
SCIP_RETCODE SCIPincludeNodeselBreadthfirst(SCIP *scip)
node selector for breadth-first search