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