1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 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 38 #include "scip/nodesel_breadthfirst.h" 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 */ 65 SCIP_CALL( SCIPincludeNodeselBreadthfirst(scip) ); 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 */ 138 SCIP_RETCODE SCIPincludeNodeselBreadthfirst( 139 SCIP* scip /**< SCIP data structure */ 140 ) 141 { 142 SCIP_NODESEL* nodesel; 143 144 /* include node selector */ 145 SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY, 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 } 155