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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file nodesel_breadthfirst.h
26  * @ingroup DEFPLUGINS_NODESEL
27  * @ingroup NODESELECTORS
28  * @brief node selector for breadth-first search
29  * @author Stefan Heinz
30  * @author Gregor Hendel
31  *
32  * This node selector performs breadth-first search, i.e., it completely evaluates an entire level of the search tree before
33  * proceeding to the next level. At one level, nodes are processed in the order they were created by the branching rule.
34  */
35 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
39 #include "scip/pub_message.h"
40 #include "scip/pub_nodesel.h"
41 #include "scip/pub_tree.h"
42 #include "scip/scip_message.h"
43 #include "scip/scip_nodesel.h"
44 #include "scip/scip_tree.h"
45 #include <string.h>
46 
47 #define NODESEL_NAME "breadthfirst"
48 #define NODESEL_DESC "breadth first search"
49 #define NODESEL_STDPRIORITY -10000
50 #define NODESEL_MEMSAVEPRIORITY -1000000
51 
52 /*
53  * Callback methods
54  */
55 
56 /** copy method for node selector plugins (called when SCIP copies plugins) */
57 static
58 SCIP_DECL_NODESELCOPY(nodeselCopyBreadthfirst)
59 { /*lint --e{715}*/
60  assert(scip != NULL);
61  assert(nodesel != NULL);
62  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
63 
64  /* call inclusion method of node selector */
66 
67  return SCIP_OKAY;
68 }
69 
70 /** node selection method of node selector */
71 static
72 SCIP_DECL_NODESELSELECT(nodeselSelectBreadthfirst)
73 { /*lint --e{715}*/
74  assert(nodesel != NULL);
75  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
76  assert(scip != NULL);
77  assert(selnode != NULL);
78 
79  /* siblings come before leaves at the same level. Sometimes it can occur that no leaves are left except for children */
80  *selnode = SCIPgetBestSibling(scip);
81  if( *selnode == NULL )
82  {
83  *selnode = SCIPgetBestLeaf(scip);
84  if( *selnode == NULL )
85  *selnode=SCIPgetBestChild(scip);
86  }
87  if( *selnode != NULL )
88  {
89  SCIPdebugMsg(scip, "Selecting next node number %" SCIP_LONGINT_FORMAT " at depth %d\n", SCIPnodeGetNumber(*selnode), SCIPnodeGetDepth(*selnode));
90  }
91 
92  return SCIP_OKAY;
93 }
94 
95 
96 /** node comparison method of breadth first search: nodes with lower depth are preferred; in case of a tie, the node
97  * which was created earlier (and therefore has a smaller node number) is preferred */
98 static
99 SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
100 { /*lint --e{715}*/
101  int depth1;
102  int depth2;
103 
104  assert(nodesel != NULL);
105  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
106  assert(scip != NULL);
107 
108  depth1 = SCIPnodeGetDepth(node1);
109  depth2 = SCIPnodeGetDepth(node2);
110 
111  /* if depths differ, prefer node with smaller depth */
112  if( depth1 < depth2 )
113  return -1;
114  else if( depth1 > depth2 )
115  return +1;
116  else
117  {
118  /* depths are equal; prefer node with smaller number */
119  SCIP_Longint number1;
120  SCIP_Longint number2;
121 
122  number1 = SCIPnodeGetNumber(node1);
123  number2 = SCIPnodeGetNumber(node2);
124  assert(number1 != number2);
125 
126  if( number1 < number2 )
127  return -1;
128  else
129  return +1;
130  }
131 }
132 
133 /*
134  * breadth first specific interface methods
135  */
136 
137 /** creates the node selector for breadth first search and includes it in SCIP */
139  SCIP* scip /**< SCIP data structure */
140  )
141 {
142  SCIP_NODESEL* nodesel;
143 
144  /* include node selector */
146  nodeselSelectBreadthfirst, nodeselCompBreadthfirst, NULL) );
147 
148  assert(nodesel != NULL);
149 
150  /* set non-fundamental callback functions via setter functions */
151  SCIP_CALL ( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyBreadthfirst) );
152 
153  return SCIP_OKAY;
154 }
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:138
#define NULL
Definition: def.h:267
public methods for branch and bound tree
public methods for node selector plugins
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:103
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:336
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7454
#define SCIPdebugMsg
Definition: scip_message.h:78
public methods for the branch-and-bound tree
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7444
#define NODESEL_STDPRIORITY
#define SCIP_CALL(x)
Definition: def.h:380
public methods for node selectors
#define NODESEL_MEMSAVEPRIORITY
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1052
#define NODESEL_NAME
static SCIP_DECL_NODESELSELECT(nodeselSelectBreadthfirst)
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
public methods for message output
static SCIP_DECL_NODESELCOPY(nodeselCopyBreadthfirst)
public methods for message handling
#define SCIP_Longint
Definition: def.h:158
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:320
static SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
#define NODESEL_DESC
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:352
SCIP_RETCODE SCIPincludeNodeselBreadthfirst(SCIP *scip)
node selector for breadth-first search