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