Scippy

SCIP

Solving Constraint Integer Programs

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