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-2018 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 email to scip@zib.de. */
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_retcode.h"
31 #include "scip/type_set.h"
32 #include "scip/type_stat.h"
33 #include "scip/type_lp.h"
34 #include "scip/type_tree.h"
35 #include "scip/type_reopt.h"
36 #include "scip/pub_nodesel.h"
37 
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41 
42 /*
43  * node priority queue methods
44  */
45 
46 /** creates node priority queue */
47 extern
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 */
55 extern
57  SCIP_NODEPQ** nodepq /**< pointer to a node priority queue */
58  );
59 
60 /** frees node priority queue and all nodes in the queue */
61 extern
63  SCIP_NODEPQ** nodepq, /**< pointer to a node priority queue */
64  BMS_BLKMEM* blkmem, /**< block memory buffers */
65  SCIP_SET* set, /**< global SCIP settings */
66  SCIP_STAT* stat, /**< problem statistics */
67  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
68  SCIP_TREE* tree, /**< branch and bound tree */
69  SCIP_LP* lp /**< current LP data */
70  );
71 
72 /** deletes all nodes in the node priority queue */
73 extern
75  SCIP_NODEPQ* nodepq, /**< node priority queue */
76  BMS_BLKMEM* blkmem, /**< block memory buffers */
77  SCIP_SET* set, /**< global SCIP settings */
78  SCIP_STAT* stat, /**< problem statistics */
79  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
80  SCIP_TREE* tree, /**< branch and bound tree */
81  SCIP_LP* lp /**< current LP data */
82  );
83 
84 /** returns the node selector associated with the given node priority queue */
85 extern
87  SCIP_NODEPQ* nodepq /**< node priority queue */
88  );
89 
90 /** sets the node selector used for sorting the nodes in the queue, and resorts the queue if necessary */
91 extern
93  SCIP_NODEPQ** nodepq, /**< pointer to a node priority queue */
94  SCIP_SET* set, /**< global SCIP settings */
95  SCIP_NODESEL* nodesel /**< node selector to use for sorting the nodes in the queue */
96  );
97 
98 /** compares two nodes; returns -1/0/+1 if node1 better/equal/worse than node2 */
99 extern
101  SCIP_NODEPQ* nodepq, /**< node priority queue */
102  SCIP_SET* set, /**< global SCIP settings */
103  SCIP_NODE* node1, /**< first node to compare */
104  SCIP_NODE* node2 /**< second node to compare */
105  );
106 
107 /** inserts node into node priority queue */
108 extern
110  SCIP_NODEPQ* nodepq, /**< node priority queue */
111  SCIP_SET* set, /**< global SCIP settings */
112  SCIP_NODE* node /**< node to be inserted */
113  );
114 
115 /** removes node from the node priority queue */
116 extern
118  SCIP_NODEPQ* nodepq, /**< node priority queue */
119  SCIP_SET* set, /**< global SCIP settings */
120  SCIP_NODE* node /**< node to remove */
121  );
122 
123 /** returns the best node of the queue without removing it */
124 extern
126  const SCIP_NODEPQ* nodepq /**< node priority queue */
127  );
128 
129 /** returns the nodes array of the queue */
130 extern
132  const SCIP_NODEPQ* nodepq /**< node priority queue */
133  );
134 
135 /** returns the number of nodes stored in the node priority queue */
136 extern
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 extern
144  SCIP_NODEPQ* nodepq, /**< node priority queue */
145  SCIP_SET* set /**< global SCIP settings */
146  );
147 
148 /** gets the node with minimal lower bound of all nodes in the queue */
149 extern
151  SCIP_NODEPQ* nodepq, /**< node priority queue */
152  SCIP_SET* set /**< global SCIP settings */
153  );
154 
155 /** gets the sum of lower bounds of all nodes in the queue */
156 extern
158  SCIP_NODEPQ* nodepq /**< node priority queue */
159  );
160 
161 /** free all nodes from the queue that are cut off by the given upper bound */
162 extern
164  SCIP_NODEPQ* nodepq, /**< node priority queue */
165  BMS_BLKMEM* blkmem, /**< block memory buffer */
166  SCIP_SET* set, /**< global SCIP settings */
167  SCIP_STAT* stat, /**< dynamic problem statistics */
168  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
169  SCIP_TREE* tree, /**< branch and bound tree */
170  SCIP_REOPT* reopt, /**< reoptimization data structure */
171  SCIP_LP* lp, /**< current LP data */
172  SCIP_Real cutoffbound /**< cutoff bound: all nodes with lowerbound >= cutoffbound are cut off */
173  );
174 
175 
176 
177 
178 /*
179  * node selector methods
180  */
181 
182 /** copies the given node selector to a new scip */
183 extern
185  SCIP_NODESEL* nodesel, /**< node selector */
186  SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
187  );
188 
189 /** creates a node selector */
190 extern
192  SCIP_NODESEL** nodesel, /**< pointer to store node selector */
193  SCIP_SET* set, /**< global SCIP settings */
194  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
195  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
196  const char* name, /**< name of node selector */
197  const char* desc, /**< description of node selector */
198  int stdpriority, /**< priority of the node selector in standard mode */
199  int memsavepriority, /**< priority of the node selector in memory saving mode */
200  SCIP_DECL_NODESELCOPY ((*nodeselcopy)), /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */
201  SCIP_DECL_NODESELFREE ((*nodeselfree)), /**< destructor of node selector */
202  SCIP_DECL_NODESELINIT ((*nodeselinit)), /**< initialize node selector */
203  SCIP_DECL_NODESELEXIT ((*nodeselexit)), /**< deinitialize node selector */
204  SCIP_DECL_NODESELINITSOL((*nodeselinitsol)),/**< solving process initialization method of node selector */
205  SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)),/**< solving process deinitialization method of node selector */
206  SCIP_DECL_NODESELSELECT((*nodeselselect)),/**< node selection method */
207  SCIP_DECL_NODESELCOMP ((*nodeselcomp)), /**< node comparison method */
208  SCIP_NODESELDATA* nodeseldata /**< node selector data */
209  );
210 
211 /** frees memory of node selector */
212 extern
214  SCIP_NODESEL** nodesel, /**< pointer to node selector data structure */
215  SCIP_SET* set /**< global SCIP settings */
216  );
217 
218 /** initializes node selector */
219 extern
221  SCIP_NODESEL* nodesel, /**< node selector */
222  SCIP_SET* set /**< global SCIP settings */
223  );
224 
225 /** deinitializes node selector */
226 extern
228  SCIP_NODESEL* nodesel, /**< node selector */
229  SCIP_SET* set /**< global SCIP settings */
230  );
231 
232 /** informs node selector that the branch and bound process is being started */
233 extern
235  SCIP_NODESEL* nodesel, /**< node selector */
236  SCIP_SET* set /**< global SCIP settings */
237  );
238 
239 /** informs node selector that the branch and bound process data is being freed */
240 extern
242  SCIP_NODESEL* nodesel, /**< node selector */
243  SCIP_SET* set /**< global SCIP settings */
244  );
245 
246 /** select next node to be processed */
247 extern
249  SCIP_NODESEL* nodesel, /**< node selector */
250  SCIP_SET* set, /**< global SCIP settings */
251  SCIP_NODE** selnode /**< pointer to store node to be processed next */
252  );
253 
254 /** compares two nodes; returns -1/0/+1 if node1 better/equal/worse than node2 */
255 extern
257  SCIP_NODESEL* nodesel, /**< node selector */
258  SCIP_SET* set, /**< global SCIP settings */
259  SCIP_NODE* node1, /**< first node to compare */
260  SCIP_NODE* node2 /**< second node to compare */
261  );
262 
263 /** sets priority of node selector in standard mode */
264 extern
266  SCIP_NODESEL* nodesel, /**< node selector */
267  SCIP_SET* set, /**< global SCIP settings */
268  int priority /**< new priority of the node selector */
269  );
270 
271 /** sets priority of node selector in memory saving mode */
272 extern
274  SCIP_NODESEL* nodesel, /**< node selector */
275  SCIP_SET* set, /**< global SCIP settings */
276  int priority /**< new priority of the node selector */
277  );
278 
279 /** sets copy method of node selector */
280 extern
281 void SCIPnodeselSetCopy(
282  SCIP_NODESEL* nodesel, /**< node selector */
283  SCIP_DECL_NODESELCOPY ((*nodeselcopy)) /**< copy method of node selector or NULL if you don't want to copy your plugin into sub-SCIPs */
284  );
285 
286 /** sets destructor method of node selector */
287 extern
288 void SCIPnodeselSetFree(
289  SCIP_NODESEL* nodesel, /**< node selector */
290  SCIP_DECL_NODESELFREE ((*nodeselfree)) /**< destructor of node selector */
291  );
292 
293 /** sets initialization method of node selector */
294 extern
295 void SCIPnodeselSetInit(
296  SCIP_NODESEL* nodesel, /**< node selector */
297  SCIP_DECL_NODESELINIT ((*nodeselinit)) /**< initialize node selector */
298  );
299 
300 /** sets deinitialization method of node selector */
301 extern
302 void SCIPnodeselSetExit(
303  SCIP_NODESEL* nodesel, /**< node selector */
304  SCIP_DECL_NODESELEXIT ((*nodeselexit)) /**< deinitialize node selector */
305  );
306 
307 /** sets solving process initialization method of node selector */
308 extern
310  SCIP_NODESEL* nodesel, /**< node selector */
311  SCIP_DECL_NODESELINITSOL ((*nodeselinitsol))/**< solving process initialization method of node selector */
312  );
313 
314 /** sets solving process deinitialization method of node selector */
315 extern
317  SCIP_NODESEL* nodesel, /**< node selector */
318  SCIP_DECL_NODESELEXITSOL ((*nodeselexitsol))/**< solving process deinitialization method of node selector */
319  );
320 
321 /** enables or disables all clocks of \p nodesel, depending on the value of the flag */
322 extern
324  SCIP_NODESEL* nodesel, /**< the node selector for which all clocks should be enabled or disabled */
325  SCIP_Bool enable /**< should the clocks of the node selector be enabled? */
326  );
327 
328 #ifdef __cplusplus
329 }
330 #endif
331 
332 #endif
void SCIPnodeselSetInit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINIT((*nodeselinit)))
Definition: nodesel.c:1114
#define SCIP_DECL_NODESELCOMP(x)
Definition: type_nodesel.h:126
void SCIPnodeselEnableOrDisableClocks(SCIP_NODESEL *nodesel, SCIP_Bool enable)
Definition: nodesel.c:1168
int SCIPnodepqCompare(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel.c:251
int SCIPnodepqLen(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:558
#define SCIP_DECL_NODESELINITSOL(x)
Definition: type_nodesel.h:83
SCIP_Real SCIPnodepqGetLowerboundSum(SCIP_NODEPQ *nodepq)
Definition: nodesel.c:616
SCIP_NODESEL * SCIPnodepqGetNodesel(SCIP_NODEPQ *nodepq)
Definition: nodesel.c:193
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPnodepqBound(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_Real cutoffbound)
Definition: nodesel.c:626
type definitions for global SCIP settings
SCIP_RETCODE SCIPnodeselExitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:936
SCIP_NODE * SCIPnodepqGetLowerboundNode(SCIP_NODEPQ *nodepq, SCIP_SET *set)
Definition: nodesel.c:592
type definitions for return codes for SCIP methods
type definitions for collecting reoptimization information
#define SCIP_DECL_NODESELEXITSOL(x)
Definition: type_nodesel.h:94
type definitions for problem statistics
SCIP_RETCODE SCIPnodeselCopyInclude(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:735
#define SCIP_DECL_NODESELINIT(x)
Definition: type_nodesel.h:64
SCIP_RETCODE SCIPnodeselExit(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:882
type definitions for LP management
SCIP_RETCODE SCIPnodeselSelect(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE **selnode)
Definition: nodesel.c:960
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:38
SCIP_RETCODE SCIPnodeselFree(SCIP_NODESEL **nodesel, SCIP_SET *set)
Definition: nodesel.c:818
SCIP_RETCODE SCIPnodepqInsert(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
Definition: nodesel.c:267
SCIP_RETCODE SCIPnodeselInitsol(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:912
SCIP_RETCODE SCIPnodeselInit(SCIP_NODESEL *nodesel, SCIP_SET *set)
Definition: nodesel.c:846
SCIP_RETCODE SCIPnodepqSetNodesel(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition: nodesel.c:203
#define SCIP_DECL_NODESELFREE(x)
Definition: type_nodesel.h:56
SCIP_RETCODE SCIPnodepqRemove(SCIP_NODEPQ *nodepq, SCIP_SET *set, SCIP_NODE *node)
Definition: nodesel.c:511
public methods for node selectors
void SCIPnodeselSetExit(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXIT((*nodeselexit)))
Definition: nodesel.c:1125
SCIP_RETCODE SCIPnodepqFree(SCIP_NODEPQ **nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: nodesel.c:130
#define SCIP_Bool
Definition: def.h:61
#define SCIP_DECL_NODESELEXIT(x)
Definition: type_nodesel.h:72
int SCIPnodeselCompare(SCIP_NODESEL *nodesel, SCIP_SET *set, SCIP_NODE *node1, SCIP_NODE *node2)
Definition: nodesel.c:984
type definitions for branch and bound tree
void SCIPnodeselSetInitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELINITSOL((*nodeselinitsol)))
Definition: nodesel.c:1136
SCIP_RETCODE SCIPnodepqClear(SCIP_NODEPQ *nodepq, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_TREE *tree, SCIP_LP *lp)
Definition: nodesel.c:153
void SCIPnodeselSetMemsavePriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
Definition: nodesel.c:1055
void SCIPnodeselSetExitsol(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELEXITSOL((*nodeselexitsol)))
Definition: nodesel.c:1147
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:753
SCIP_RETCODE SCIPnodepqCreate(SCIP_NODEPQ **nodepq, SCIP_SET *set, SCIP_NODESEL *nodesel)
Definition: nodesel.c:95
#define SCIP_Real
Definition: def.h:149
void SCIPnodeselSetFree(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: nodesel.c:1103
#define SCIP_DECL_NODESELCOPY(x)
Definition: type_nodesel.h:47
SCIP_NODE * SCIPnodepqFirst(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:532
SCIP_Real SCIPnodepqGetLowerbound(SCIP_NODEPQ *nodepq, SCIP_SET *set)
Definition: nodesel.c:569
SCIP_NODE ** SCIPnodepqNodes(const SCIP_NODEPQ *nodepq)
Definition: nodesel.c:548
void SCIPnodeselSetCopy(SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: nodesel.c:1092
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:419
void SCIPnodeselSetStdPriority(SCIP_NODESEL *nodesel, SCIP_SET *set, int priority)
Definition: nodesel.c:1031
#define SCIP_DECL_NODESELSELECT(x)
Definition: type_nodesel.h:109
void SCIPnodepqDestroy(SCIP_NODEPQ **nodepq)
Definition: nodesel.c:116
memory allocation routines