SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2024 Zuse Institute Berlin (ZIB) */
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"
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 */
60struct 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) */
74static
76{ /*lint --e{715}*/
77 assert(scip != NULL);
78 assert(nodesel != NULL);
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) */
88static
90{ /*lint --e{715}*/
91 SCIP_NODESELDATA* nodeseldata;
92
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) */
106static
108{
109 SCIP_NODESELDATA* nodeseldata;
110
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 */
125static
127{ /*lint --e{715}*/
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 */
133 if( *selnode == NULL )
134 {
135 SCIP_NODESELDATA* nodeseldata;
136 SCIP_Longint nnodes;
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
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;
156 }
157 else
158 {
160 if( *selnode == NULL )
162 }
163 }
164
165 return SCIP_OKAY;
166}
167
168
169/** node comparison method of node selector */
170static
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 */
199
200 assert(nodesel != NULL);
201
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
#define NULL
Definition def.h:267
#define FALSE
Definition def.h:94
#define SCIP_CALL(x)
Definition def.h:374
#define nnodes
Definition gastrans.c:74
SCIP_RETCODE SCIPincludeNodeselRestartdfs(SCIP *scip)
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
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
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition tree.c:7444
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)
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition nodesel.c:1130
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel,)
SCIP_RETCODE SCIPsetNodeselInitsol(SCIP *scip, SCIP_NODESEL *nodesel,)
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition nodesel.c:1120
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel,)
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition nodesel.c:1052
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition scip_tree.c:304
SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition scip_tree.c:384
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition scip_tree.c:288
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition scip_tree.c:352
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
#define SELECTBESTFREQ
#define NODESEL_NAME
#define NODESEL_MEMSAVEPRIORITY
#define NODESEL_STDPRIORITY
#define COUNTONLYLEAVES
#define NODESEL_DESC
node selector for depth first search with periodical selection of the best node
public methods for message output
public methods for node selectors
public methods for branch and bound tree
public methods for memory management
public methods for node selector plugins
public methods for SCIP parameter handling
public methods for querying solving statistics
public methods for the branch-and-bound tree
#define SCIP_DECL_NODESELCOMP(x)
#define SCIP_DECL_NODESELINITSOL(x)
#define SCIP_DECL_NODESELCOPY(x)
#define SCIP_DECL_NODESELSELECT(x)
#define SCIP_DECL_NODESELFREE(x)
struct SCIP_NodeselData SCIP_NODESELDATA
enum SCIP_Retcode SCIP_RETCODE