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.h 26 * @ingroup INTERNALAPI 27 * @brief internal methods for node selectors and node priority queues 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_NODESEL_H__ 34 #define __SCIP_NODESEL_H__ 35 36 37 #include "scip/def.h" 38 #include "blockmemshell/memory.h" 39 #include "scip/type_event.h" 40 #include "scip/type_retcode.h" 41 #include "scip/type_set.h" 42 #include "scip/type_stat.h" 43 #include "scip/type_lp.h" 44 #include "scip/type_tree.h" 45 #include "scip/type_reopt.h" 46 #include "scip/pub_nodesel.h" 47 48 #ifdef __cplusplus 49 extern "C" { 50 #endif 51 52 /* 53 * node priority queue methods 54 */ 55 56 /** creates node priority queue */ 57 SCIP_RETCODE SCIPnodepqCreate( 58 SCIP_NODEPQ** nodepq, /**< pointer to a node priority queue */ 59 SCIP_SET* set, /**< global SCIP settings */ 60 SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */ 61 ); 62 63 /** frees node priority queue, but not the data nodes themselves */ 64 void SCIPnodepqDestroy( 65 SCIP_NODEPQ** nodepq /**< pointer to a node priority queue */ 66 ); 67 68 /** frees node priority queue and all nodes in the queue */ 69 SCIP_RETCODE SCIPnodepqFree( 70 SCIP_NODEPQ** nodepq, /**< pointer to a node priority queue */ 71 BMS_BLKMEM* blkmem, /**< block memory buffers */ 72 SCIP_SET* set, /**< global SCIP settings */ 73 SCIP_STAT* stat, /**< problem statistics */ 74 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 75 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 76 SCIP_TREE* tree, /**< branch and bound tree */ 77 SCIP_LP* lp /**< current LP data */ 78 ); 79 80 /** deletes all nodes in the node priority queue */ 81 SCIP_RETCODE SCIPnodepqClear( 82 SCIP_NODEPQ* nodepq, /**< node priority queue */ 83 BMS_BLKMEM* blkmem, /**< block memory buffers */ 84 SCIP_SET* set, /**< global SCIP settings */ 85 SCIP_STAT* stat, /**< problem statistics */ 86 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 87 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 88 SCIP_TREE* tree, /**< branch and bound tree */ 89 SCIP_LP* lp /**< current LP data */ 90 ); 91 92 /** returns the node selector associated with the given node priority queue */ 93 SCIP_NODESEL* SCIPnodepqGetNodesel( 94 SCIP_NODEPQ* nodepq /**< node priority queue */ 95 ); 96 97 /** sets the node selector used for sorting the nodes in the queue, and resorts the queue if necessary */ 98 SCIP_RETCODE SCIPnodepqSetNodesel( 99 SCIP_NODEPQ** nodepq, /**< pointer to a node priority queue */ 100 SCIP_SET* set, /**< global SCIP settings */ 101 SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */ 102 ); 103 104 /** compares two nodes; returns -1/0/+1 if node1 better/equal/worse than node2 */ 105 int SCIPnodepqCompare( 106 SCIP_NODEPQ* nodepq, /**< node priority queue */ 107 SCIP_SET* set, /**< global SCIP settings */ 108 SCIP_NODE* node1, /**< first node to compare */ 109 SCIP_NODE* node2 /**< second node to compare */ 110 ); 111 112 /** inserts node into node priority queue */ 113 SCIP_RETCODE SCIPnodepqInsert( 114 SCIP_NODEPQ* nodepq, /**< node priority queue */ 115 SCIP_SET* set, /**< global SCIP settings */ 116 SCIP_NODE* node /**< node to be inserted */ 117 ); 118 119 /** removes node from the node priority queue */ 120 SCIP_RETCODE SCIPnodepqRemove( 121 SCIP_NODEPQ* nodepq, /**< node priority queue */ 122 SCIP_SET* set, /**< global SCIP settings */ 123 SCIP_NODE* node /**< node to remove */ 124 ); 125 126 /** returns the best node of the queue without removing it */ 127 SCIP_NODE* SCIPnodepqFirst( 128 const SCIP_NODEPQ* nodepq /**< node priority queue */ 129 ); 130 131 /** returns the nodes array of the queue */ 132 SCIP_NODE** SCIPnodepqNodes( 133 const SCIP_NODEPQ* nodepq /**< node priority queue */ 134 ); 135 136 /** returns the number of nodes stored in the node priority queue */ 137 int SCIPnodepqLen( 138 const SCIP_NODEPQ* nodepq /**< node priority queue */ 139 ); 140 141 /** gets the minimal lower bound of all nodes in the queue */ 142 SCIP_Real SCIPnodepqGetLowerbound( 143 SCIP_NODEPQ* nodepq, /**< node priority queue */ 144 SCIP_SET* set /**< global SCIP settings */ 145 ); 146 147 /** gets the node with minimal lower bound of all nodes in the queue */ 148 SCIP_NODE* SCIPnodepqGetLowerboundNode( 149 SCIP_NODEPQ* nodepq, /**< node priority queue */ 150 SCIP_SET* set /**< global SCIP settings */ 151 ); 152 153 /** gets the sum of lower bounds of all nodes in the queue */ 154 SCIP_Real SCIPnodepqGetLowerboundSum( 155 SCIP_NODEPQ* nodepq /**< node priority queue */ 156 ); 157 158 /** free all nodes from the queue that are cut off by the given upper bound */ 159 SCIP_RETCODE SCIPnodepqBound( 160 SCIP_NODEPQ* nodepq, /**< node priority queue */ 161 BMS_BLKMEM* blkmem, /**< block memory buffer */ 162 SCIP_SET* set, /**< global SCIP settings */ 163 SCIP_STAT* stat, /**< dynamic problem statistics */ 164 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 165 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 166 SCIP_TREE* tree, /**< branch and bound tree */ 167 SCIP_REOPT* reopt, /**< reoptimization data structure */ 168 SCIP_LP* lp, /**< current LP data */ 169 SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */ 170 ); 171 172 173 174 175 /* 176 * node selector methods 177 */ 178 179 /** copies the given node selector to a new scip */ 180 SCIP_RETCODE SCIPnodeselCopyInclude( 181 SCIP_NODESEL* nodesel, /**< node selector */ 182 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */ 183 ); 184 185 /** creates a node selector */ 186 SCIP_RETCODE SCIPnodeselCreate( 187 SCIP_NODESEL** nodesel, /**< pointer to store node selector */ 188 SCIP_SET* set, /**< global SCIP settings */ 189 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 190 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 191 const char* name, /**< name of node selector */ 192 const char* desc, /**< description of node selector */ 193 int stdpriority, /**< priority of the node selector in standard mode */ 194 int memsavepriority, /**< priority of the node selector in memory saving mode */ 195 SCIP_DECL_NODESELCOPY ((*nodeselcopy)), /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */ 196 SCIP_DECL_NODESELFREE ((*nodeselfree)), /**< destructor of node selector */ 197 SCIP_DECL_NODESELINIT ((*nodeselinit)), /**< initialize node selector */ 198 SCIP_DECL_NODESELEXIT ((*nodeselexit)), /**< deinitialize node selector */ 199 SCIP_DECL_NODESELINITSOL((*nodeselinitsol)),/**< solving process initialization method of node selector */ 200 SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)),/**< solving process deinitialization method of node selector */ 201 SCIP_DECL_NODESELSELECT((*nodeselselect)),/**< node selection method */ 202 SCIP_DECL_NODESELCOMP ((*nodeselcomp)), /**< node comparison method */ 203 SCIP_NODESELDATA* nodeseldata /**< node selector data */ 204 ); 205 206 /** frees memory of node selector */ 207 SCIP_RETCODE SCIPnodeselFree( 208 SCIP_NODESEL** nodesel, /**< pointer to node selector data structure */ 209 SCIP_SET* set /**< global SCIP settings */ 210 ); 211 212 /** initializes node selector */ 213 SCIP_RETCODE SCIPnodeselInit( 214 SCIP_NODESEL* nodesel, /**< node selector */ 215 SCIP_SET* set /**< global SCIP settings */ 216 ); 217 218 /** deinitializes node selector */ 219 SCIP_RETCODE SCIPnodeselExit( 220 SCIP_NODESEL* nodesel, /**< node selector */ 221 SCIP_SET* set /**< global SCIP settings */ 222 ); 223 224 /** informs node selector that the branch and bound process is being started */ 225 SCIP_RETCODE SCIPnodeselInitsol( 226 SCIP_NODESEL* nodesel, /**< node selector */ 227 SCIP_SET* set /**< global SCIP settings */ 228 ); 229 230 /** informs node selector that the branch and bound process data is being freed */ 231 SCIP_RETCODE SCIPnodeselExitsol( 232 SCIP_NODESEL* nodesel, /**< node selector */ 233 SCIP_SET* set /**< global SCIP settings */ 234 ); 235 236 /** select next node to be processed */ 237 SCIP_RETCODE SCIPnodeselSelect( 238 SCIP_NODESEL* nodesel, /**< node selector */ 239 SCIP_SET* set, /**< global SCIP settings */ 240 SCIP_NODE** selnode /**< pointer to store node to be processed next */ 241 ); 242 243 /** compares two nodes; returns -1/0/+1 if node1 better/equal/worse than node2 */ 244 int SCIPnodeselCompare( 245 SCIP_NODESEL* nodesel, /**< node selector */ 246 SCIP_SET* set, /**< global SCIP settings */ 247 SCIP_NODE* node1, /**< first node to compare */ 248 SCIP_NODE* node2 /**< second node to compare */ 249 ); 250 251 /** sets priority of node selector in standard mode */ 252 void SCIPnodeselSetStdPriority( 253 SCIP_NODESEL* nodesel, /**< node selector */ 254 SCIP_SET* set, /**< global SCIP settings */ 255 int priority /**< new priority of the node selector */ 256 ); 257 258 /** sets priority of node selector in memory saving mode */ 259 void SCIPnodeselSetMemsavePriority( 260 SCIP_NODESEL* nodesel, /**< node selector */ 261 SCIP_SET* set, /**< global SCIP settings */ 262 int priority /**< new priority of the node selector */ 263 ); 264 265 /** sets copy method of node selector */ 266 void SCIPnodeselSetCopy( 267 SCIP_NODESEL* nodesel, /**< node selector */ 268 SCIP_DECL_NODESELCOPY ((*nodeselcopy)) /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */ 269 ); 270 271 /** sets destructor method of node selector */ 272 void SCIPnodeselSetFree( 273 SCIP_NODESEL* nodesel, /**< node selector */ 274 SCIP_DECL_NODESELFREE ((*nodeselfree)) /**< destructor of node selector */ 275 ); 276 277 /** sets initialization method of node selector */ 278 void SCIPnodeselSetInit( 279 SCIP_NODESEL* nodesel, /**< node selector */ 280 SCIP_DECL_NODESELINIT ((*nodeselinit)) /**< initialize node selector */ 281 ); 282 283 /** sets deinitialization method of node selector */ 284 void SCIPnodeselSetExit( 285 SCIP_NODESEL* nodesel, /**< node selector */ 286 SCIP_DECL_NODESELEXIT ((*nodeselexit)) /**< deinitialize node selector */ 287 ); 288 289 /** sets solving process initialization method of node selector */ 290 void SCIPnodeselSetInitsol( 291 SCIP_NODESEL* nodesel, /**< node selector */ 292 SCIP_DECL_NODESELINITSOL ((*nodeselinitsol))/**< solving process initialization method of node selector */ 293 ); 294 295 /** sets solving process deinitialization method of node selector */ 296 void SCIPnodeselSetExitsol( 297 SCIP_NODESEL* nodesel, /**< node selector */ 298 SCIP_DECL_NODESELEXITSOL ((*nodeselexitsol))/**< solving process deinitialization method of node selector */ 299 ); 300 301 /** enables or disables all clocks of \p nodesel, depending on the value of the flag */ 302 void SCIPnodeselEnableOrDisableClocks( 303 SCIP_NODESEL* nodesel, /**< the node selector for which all clocks should be enabled or disabled */ 304 SCIP_Bool enable /**< should the clocks of the node selector be enabled? */ 305 ); 306 307 #ifdef __cplusplus 308 } 309 #endif 310 311 #endif 312