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