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_dfs.c 26 * @ingroup DEFPLUGINS_NODESEL 27 * @brief node selector for depth first search 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/nodesel_dfs.h" 34 #include "scip/pub_message.h" 35 #include "scip/pub_nodesel.h" 36 #include "scip/pub_tree.h" 37 #include "scip/scip_message.h" 38 #include "scip/scip_nodesel.h" 39 #include "scip/scip_tree.h" 40 #include <string.h> 41 42 #define NODESEL_NAME "dfs" 43 #define NODESEL_DESC "depth first search" 44 #define NODESEL_STDPRIORITY 0 45 #define NODESEL_MEMSAVEPRIORITY 100000 46 47 48 /* 49 * Callback methods 50 */ 51 52 /** copy method for node selector plugins (called when SCIP copies plugins) */ 53 static 54 SCIP_DECL_NODESELCOPY(nodeselCopyDfs) 55 { /*lint --e{715}*/ 56 assert(scip != NULL); 57 assert(nodesel != NULL); 58 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0); 59 60 /* call inclusion method of node selector */ 61 SCIP_CALL( SCIPincludeNodeselDfs(scip) ); 62 63 return SCIP_OKAY; 64 } 65 66 67 /** node selection method of node selector */ 68 static 69 SCIP_DECL_NODESELSELECT(nodeselSelectDfs) 70 { /*lint --e{715}*/ 71 assert(nodesel != NULL); 72 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0); 73 assert(scip != NULL); 74 assert(selnode != NULL); 75 76 *selnode = SCIPgetPrioChild(scip); 77 if( *selnode == NULL ) 78 { 79 *selnode = SCIPgetPrioSibling(scip); 80 if( *selnode == NULL ) 81 { 82 SCIPdebugMsg(scip, "select best leaf\n"); 83 *selnode = SCIPgetBestLeaf(scip); 84 } 85 86 SCIPdebugMsg(scip, "select best sibling leaf\n"); 87 } 88 89 return SCIP_OKAY; 90 } 91 92 93 /** node comparison method of node selector */ 94 static 95 SCIP_DECL_NODESELCOMP(nodeselCompDfs) 96 { /*lint --e{715}*/ 97 int depth1; 98 int depth2; 99 100 assert(nodesel != NULL); 101 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0); 102 assert(scip != NULL); 103 104 depth1 = SCIPnodeGetDepth(node1); 105 depth2 = SCIPnodeGetDepth(node2); 106 if( depth1 > depth2 ) 107 return -1; 108 else if( depth1 < depth2 ) 109 return +1; 110 else 111 { 112 SCIP_Real lowerbound1; 113 SCIP_Real lowerbound2; 114 115 lowerbound1 = SCIPnodeGetLowerbound(node1); 116 lowerbound2 = SCIPnodeGetLowerbound(node2); 117 if( lowerbound1 < lowerbound2 ) 118 return -1; 119 else if( lowerbound1 > lowerbound2 ) 120 return +1; 121 else 122 return 0; 123 } 124 } 125 126 127 /* 128 * dfs specific interface methods 129 */ 130 131 /** creates the node selector for depth first search and includes it in SCIP */ 132 SCIP_RETCODE SCIPincludeNodeselDfs( 133 SCIP* scip /**< SCIP data structure */ 134 ) 135 { 136 SCIP_NODESEL* nodesel; 137 138 /* include node selector */ 139 SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY, 140 nodeselSelectDfs, nodeselCompDfs, NULL) ); 141 142 assert(nodesel != NULL); 143 144 SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyDfs) ); 145 146 return SCIP_OKAY; 147 } 148