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_restartdfs.c 26 * @ingroup DEFPLUGINS_NODESEL 27 * @brief node selector for depth first search with periodical selection of the best node 28 * @author Tobias Achterberg 29 * @author Stefan Heinz 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "scip/nodesel_restartdfs.h" 35 #include "scip/pub_message.h" 36 #include "scip/pub_nodesel.h" 37 #include "scip/pub_tree.h" 38 #include "scip/scip_mem.h" 39 #include "scip/scip_nodesel.h" 40 #include "scip/scip_param.h" 41 #include "scip/scip_solvingstats.h" 42 #include "scip/scip_tree.h" 43 #include <string.h> 44 45 #define NODESEL_NAME "restartdfs" 46 #define NODESEL_DESC "depth first search with periodical selection of the best node" 47 #define NODESEL_STDPRIORITY 10000 48 #define NODESEL_MEMSAVEPRIORITY 50000 49 50 51 /* 52 * Default parameter settings 53 */ 54 55 #define SELECTBESTFREQ 100 /**< frequency for selecting the best node instead of the deepest one */ 56 #define COUNTONLYLEAVES TRUE /**< only count leaf nodes or all nodes */ 57 58 59 /** node selector data for best first search node selection */ 60 struct SCIP_NodeselData 61 { 62 SCIP_Longint lastrestart; /**< node number where the last best node was selected */ 63 SCIP_Longint nprocessedleaves; /**< number of processed leafs since the last restart */ 64 int selectbestfreq; /**< frequency for selecting the best node instead of the deepest one */ 65 SCIP_Bool countonlyleaves; /**< only count leaf nodes or all nodes */ 66 }; 67 68 69 /* 70 * Callback methods 71 */ 72 73 /** copy method for node selector plugins (called when SCIP copies plugins) */ 74 static 75 SCIP_DECL_NODESELCOPY(nodeselCopyRestartdfs) 76 { /*lint --e{715}*/ 77 assert(scip != NULL); 78 assert(nodesel != NULL); 79 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0); 80 81 /* call inclusion method of node selector */ 82 SCIP_CALL( SCIPincludeNodeselRestartdfs(scip) ); 83 84 return SCIP_OKAY; 85 } 86 87 /** destructor of node selector to free user data (called when SCIP is exiting) */ 88 static 89 SCIP_DECL_NODESELFREE(nodeselFreeRestartdfs) 90 { /*lint --e{715}*/ 91 SCIP_NODESELDATA* nodeseldata; 92 93 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0); 94 95 /* free user data of node selector */ 96 nodeseldata = SCIPnodeselGetData(nodesel); 97 assert(nodeseldata != NULL); 98 SCIPfreeBlockMemory(scip, &nodeseldata); 99 SCIPnodeselSetData(nodesel, nodeseldata); 100 101 return SCIP_OKAY; 102 } 103 104 105 /** solving process initialization method of node selector (called when branch and bound process is about to begin) */ 106 static 107 SCIP_DECL_NODESELINITSOL(nodeselInitsolRestartdfs) 108 { 109 SCIP_NODESELDATA* nodeseldata; 110 111 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0); 112 113 nodeseldata = SCIPnodeselGetData(nodesel); 114 assert(nodeseldata != NULL); 115 116 /* reset counters */ 117 nodeseldata->lastrestart = 0; 118 nodeseldata->nprocessedleaves = 0; 119 120 return SCIP_OKAY; 121 } 122 123 124 /** node selection method of node selector */ 125 static 126 SCIP_DECL_NODESELSELECT(nodeselSelectRestartdfs) 127 { /*lint --e{715}*/ 128 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0); 129 assert(selnode != NULL); 130 131 /* decide if we want to select the node with lowest bound or the deepest node; finish the current dive in any case */ 132 *selnode = SCIPgetPrioChild(scip); 133 if( *selnode == NULL ) 134 { 135 SCIP_NODESELDATA* nodeseldata; 136 SCIP_Longint nnodes; 137 138 /* get node selector user data */ 139 nodeseldata = SCIPnodeselGetData(nodesel); 140 assert(nodeseldata != NULL); 141 142 /* increase the number of processed leafs since we are in a leaf */ 143 nodeseldata->nprocessedleaves++; 144 145 nnodes = SCIPgetNNodes(scip); 146 147 /* check if in case of "only leaves" the number processed leaves exceeds the frequency or in the other case the 148 * number of processed node does it 149 */ 150 if( (nodeseldata->countonlyleaves && nodeseldata->nprocessedleaves >= nodeseldata->selectbestfreq) 151 || (!nodeseldata->countonlyleaves && nnodes - nodeseldata->lastrestart >= nodeseldata->selectbestfreq ) ) 152 { 153 nodeseldata->lastrestart = nnodes; 154 nodeseldata->nprocessedleaves = 0; 155 *selnode = SCIPgetBestboundNode(scip); 156 } 157 else 158 { 159 *selnode = SCIPgetPrioSibling(scip); 160 if( *selnode == NULL ) 161 *selnode = SCIPgetBestLeaf(scip); 162 } 163 } 164 165 return SCIP_OKAY; 166 } 167 168 169 /** node comparison method of node selector */ 170 static 171 SCIP_DECL_NODESELCOMP(nodeselCompRestartdfs) 172 { /*lint --e{715}*/ 173 return (int)(SCIPnodeGetNumber(node2) - SCIPnodeGetNumber(node1)); 174 } 175 176 177 /* 178 * restartdfs specific interface methods 179 */ 180 181 /** creates the node selector for restarting depth first search and includes it in SCIP */ 182 SCIP_RETCODE SCIPincludeNodeselRestartdfs( 183 SCIP* scip /**< SCIP data structure */ 184 ) 185 { 186 SCIP_NODESELDATA* nodeseldata; 187 SCIP_NODESEL* nodesel; 188 189 /* allocate and initialize node selector data; this has to be freed in the destructor */ 190 SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) ); 191 nodeseldata->lastrestart = 0; 192 nodeseldata->nprocessedleaves = 0; 193 nodeseldata->selectbestfreq = SELECTBESTFREQ; 194 nodeseldata->countonlyleaves = COUNTONLYLEAVES; 195 196 /* include node selector */ 197 SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY, 198 nodeselSelectRestartdfs, nodeselCompRestartdfs, nodeseldata) ); 199 200 assert(nodesel != NULL); 201 202 SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyRestartdfs) ); 203 SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeRestartdfs) ); 204 SCIP_CALL( SCIPsetNodeselInitsol(scip, nodesel, nodeselInitsolRestartdfs) ); 205 206 /* add node selector parameters */ 207 SCIP_CALL( SCIPaddIntParam(scip, 208 "nodeselection/restartdfs/selectbestfreq", 209 "frequency for selecting the best node instead of the deepest one", 210 &nodeseldata->selectbestfreq, FALSE, SELECTBESTFREQ, 0, INT_MAX, NULL, NULL) ); 211 212 /* add node selector parameters */ 213 SCIP_CALL( SCIPaddBoolParam(scip, 214 "nodeselection/restartdfs/countonlyleaves", 215 "count only leaf nodes (otherwise all nodes)?", 216 &nodeseldata->countonlyleaves, FALSE, COUNTONLYLEAVES, NULL, NULL) ); 217 218 return SCIP_OKAY; 219 } 220 221