1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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   	
34   	#include "scip/nodesel_restartdfs.h"
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 */
82   	   SCIP_CALL( SCIPincludeNodeselRestartdfs(scip) );
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;
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  	
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 */
182  	SCIP_RETCODE SCIPincludeNodeselRestartdfs(
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 */
197  	   SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY,
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 */
207  	   SCIP_CALL( SCIPaddIntParam(scip,
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 */
213  	   SCIP_CALL( SCIPaddBoolParam(scip,
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  	
221