Scippy

SCIP

Solving Constraint Integer Programs

nodesel.h
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-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 */
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 */
65  SCIP_NODEPQ** nodepq /**< pointer to a node priority queue */
66  );
67 
68 /** frees node priority queue and all nodes in the queue */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
128  const SCIP_NODEPQ* nodepq /**< node priority queue */
129  );
130 
131 /** returns the nodes array of the queue */
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 */
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 */
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 */
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 */
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 */
181  SCIP_NODESEL* nodesel, /**< node selector */
182  SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
183  );
184 
185 /** creates a node selector */
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 */
208  SCIP_NODESEL** nodesel, /**< pointer to node selector data structure */
209  SCIP_SET* set /**< global SCIP settings */
210  );
211 
212 /** initializes node selector */
214  SCIP_NODESEL* nodesel, /**< node selector */
215  SCIP_SET* set /**< global SCIP settings */
216  );
217 
218 /** deinitializes node selector */
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 */
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 */
232  SCIP_NODESEL* nodesel, /**< node selector */
233  SCIP_SET* set /**< global SCIP settings */
234  );
235 
236 /** select next node to be processed */
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 */
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 */
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 */
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 */
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 */
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 */
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
void SCIPnodeselSetInit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINIT((*nodeselinit)))
Definition: nodesel.c:1165
SCIP_RETCODE SCIPnodepqClear(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: nodesel.c:165
#define SCIP_DECL_NODESELCOMP(x)
Definition: type_nodesel.h:140
void SCIPnodeselEnableOrDisableClocks(SCIP_NODESEL *nodesel, SCIP_Bool enable)
Definition: nodesel.c:1219
int SCIPnodepqCompare(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel.c:264
int SCIPnodepqLen(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:571
#define SCIP_DECL_NODESELINITSOL(x)
Definition: type_nodesel.h:97
SCIP_Real SCIPnodepqGetLowerboundSum(SCIP_NODEPQ *nodepq)
Definition: nodesel.c:629
SCIP_NODESEL * SCIPnodepqGetNodesel(SCIP_NODEPQ *nodepq)
Definition: nodesel.c:206
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for global SCIP settings
SCIP_RETCODE SCIPnodeselExitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:988
SCIP_NODE * SCIPnodepqGetLowerboundNode(SCIP_NODEPQ *nodepq, SCIP_SET *set)
Definition: nodesel.c:605
type definitions for return codes for SCIP methods
type definitions for collecting reoptimization information
#define SCIP_DECL_NODESELEXITSOL(x)
Definition: type_nodesel.h:108
type definitions for problem statistics
SCIP_RETCODE SCIPnodeselCopyInclude(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:749
#define SCIP_DECL_NODESELINIT(x)
Definition: type_nodesel.h:78
SCIP_RETCODE SCIPnodeselExit(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:934
type definitions for LP management
SCIP_RETCODE SCIPnodeselSelect(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE **selnode)
Definition: nodesel.c:1012
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:52
SCIP_RETCODE SCIPnodeselFree(SCIP_NODESEL **nodesel, SCIP_SET *set)
Definition: nodesel.c:869
SCIP_RETCODE SCIPnodepqInsert(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
Definition: nodesel.c:280
SCIP_RETCODE SCIPnodepqBound(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_Real cutoffbound)
Definition: nodesel.c:639
SCIP_RETCODE SCIPnodepqFree(SCIP_NODEPQ **nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: nodesel.c:141
SCIP_RETCODE SCIPnodeselInitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:964
SCIP_RETCODE SCIPnodeselInit(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:898
SCIP_RETCODE SCIPnodepqSetNodesel(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition: nodesel.c:216
#define SCIP_DECL_NODESELFREE(x)
Definition: type_nodesel.h:70
SCIP_RETCODE SCIPnodepqRemove(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
Definition: nodesel.c:524
type definitions for managing events
public methods for node selectors
void SCIPnodeselSetExit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXIT((*nodeselexit)))
Definition: nodesel.c:1176
#define SCIP_Bool
Definition: def.h:93
#define SCIP_DECL_NODESELEXIT(x)
Definition: type_nodesel.h:86
int SCIPnodeselCompare(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel.c:1035
type definitions for branch and bound tree
void SCIPnodeselSetInitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
Definition: nodesel.c:1187
void SCIPnodeselSetMemsavePriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
Definition: nodesel.c:1106
void SCIPnodeselSetExitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
Definition: nodesel.c:1198
SCIP_RETCODE SCIPnodeselCreate(SCIP_NODESEL **nodesel, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELCOPY((*nodeselcopy)), SCIP_DECL_NODESELFREE((*nodeselfree)), SCIP_DECL_NODESELINIT((*nodeselinit)), SCIP_DECL_NODESELEXIT((*nodeselexit)), SCIP_DECL_NODESELINITSOL((*nodeselinitsol)), SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)), SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:835
SCIP_RETCODE SCIPnodepqCreate(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition: nodesel.c:105
#define SCIP_Real
Definition: def.h:186
void SCIPnodeselSetFree(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: nodesel.c:1154
#define SCIP_DECL_NODESELCOPY(x)
Definition: type_nodesel.h:61
SCIP_NODE * SCIPnodepqFirst(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:545
SCIP_Real SCIPnodepqGetLowerbound(SCIP_NODEPQ *nodepq, SCIP_SET *set)
Definition: nodesel.c:582
SCIP_NODE ** SCIPnodepqNodes(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:561
void SCIPnodeselSetCopy(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: nodesel.c:1143
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:439
void SCIPnodeselSetStdPriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
Definition: nodesel.c:1082
#define SCIP_DECL_NODESELSELECT(x)
Definition: type_nodesel.h:123
void SCIPnodepqDestroy(SCIP_NODEPQ **nodepq)
Definition: nodesel.c:127
memory allocation routines