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) */
57static
58SCIP_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 */
71static
72SCIP_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 */
98static
99SCIP_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}
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludeNodeselBreadthfirst(SCIP *scip)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
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_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:138
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1052
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:336
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:320
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:352
#define NODESEL_NAME
static SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
#define NODESEL_MEMSAVEPRIORITY
static SCIP_DECL_NODESELSELECT(nodeselSelectBreadthfirst)
#define NODESEL_STDPRIORITY
#define NODESEL_DESC
static SCIP_DECL_NODESELCOPY(nodeselCopyBreadthfirst)
node selector for breadth-first search
public methods for message output
public methods for node selectors
public methods for branch and bound tree
public methods for message handling
public methods for node selector plugins
public methods for the branch-and-bound tree
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63