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_bfs.c
26   	 * @ingroup DEFPLUGINS_NODESEL
27   	 * @brief  node selector for best first search
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/nodesel_bfs.h"
34   	#include "scip/pub_message.h"
35   	#include "scip/pub_nodesel.h"
36   	#include "scip/pub_tree.h"
37   	#include "scip/scip_mem.h"
38   	#include "scip/scip_message.h"
39   	#include "scip/scip_nodesel.h"
40   	#include "scip/scip_numerics.h"
41   	#include "scip/scip_param.h"
42   	#include "scip/scip_solvingstats.h"
43   	#include "scip/scip_tree.h"
44   	#include "scip/type_misc.h"
45   	#include <string.h>
46   	
47   	#define NODESEL_NAME             "bfs"
48   	#define NODESEL_DESC             "best first search"
49   	#define NODESEL_STDPRIORITY      100000
50   	#define NODESEL_MEMSAVEPRIORITY       0
51   	
52   	
53   	/*
54   	 * Default parameter settings
55   	 */
56   	
57   	#define MINPLUNGEDEPTH               -1 /**< minimal plunging depth, before new best node may be selected (-1 for dynamic setting) */
58   	#define MAXPLUNGEDEPTH               -1 /**< maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting) */
59   	#define MAXPLUNGEQUOT              0.25 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
60   	                                              *   where plunging is performed */
61   	
62   	
63   	/** node selector data for best first search node selection */
64   	struct SCIP_NodeselData
65   	{
66   	   SCIP_Real             maxplungequot;      /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
67   	                                              *   where plunging is performed */
68   	   int                   minplungedepth;     /**< minimal plunging depth, before new best node may be selected
69   	                                              *   (-1 for dynamic setting) */
70   	   int                   maxplungedepth;     /**< maximal plunging depth, before new best node is forced to be selected
71   	                                              *   (-1 for dynamic setting) */
72   	};
73   	
74   	
75   	/*
76   	 * Callback methods
77   	 */
78   	
79   	/** copy method for node selector plugins (called when SCIP copies plugins) */
80   	static
81   	SCIP_DECL_NODESELCOPY(nodeselCopyBfs)
82   	{  /*lint --e{715}*/
83   	   assert(scip != NULL);
84   	   assert(nodesel != NULL);
85   	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
86   	
87   	   /* call inclusion method of node selector */
88   	   SCIP_CALL( SCIPincludeNodeselBfs(scip) );
89   	
90   	   return SCIP_OKAY;
91   	}
92   	
93   	/** destructor of node selector to free user data (called when SCIP is exiting) */
94   	/**! [SnippetNodeselFreeBfs] */
95   	static
96   	SCIP_DECL_NODESELFREE(nodeselFreeBfs)
97   	{  /*lint --e{715}*/
98   	   SCIP_NODESELDATA* nodeseldata;
99   	
100  	   assert(nodesel != NULL);
101  	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
102  	   assert(scip != NULL);
103  	
104  	   /* free user data of node selector */
105  	   nodeseldata = SCIPnodeselGetData(nodesel);
106  	   assert(nodeseldata != NULL);
107  	   SCIPfreeBlockMemory(scip, &nodeseldata);
108  	   SCIPnodeselSetData(nodesel, nodeseldata);
109  	
110  	   return SCIP_OKAY;
111  	}
112  	/**! [SnippetNodeselFreeBfs] */
113  	
114  	
115  	/** node selection method of node selector */
116  	static
117  	SCIP_DECL_NODESELSELECT(nodeselSelectBfs)
118  	{  /*lint --e{715}*/
119  	   SCIP_NODESELDATA* nodeseldata;
120  	   int minplungedepth;
121  	   int maxplungedepth;
122  	   int plungedepth;
123  	   SCIP_Real maxplungequot;
124  	
125  	   assert(nodesel != NULL);
126  	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
127  	   assert(scip != NULL);
128  	   assert(selnode != NULL);
129  	
130  	   *selnode = NULL;
131  	
132  	   /* get node selector user data */
133  	   nodeseldata = SCIPnodeselGetData(nodesel);
134  	   assert(nodeseldata != NULL);
135  	
136  	   /* calculate minimal and maximal plunging depth */
137  	   minplungedepth = nodeseldata->minplungedepth;
138  	   maxplungedepth = nodeseldata->maxplungedepth;
139  	   maxplungequot = nodeseldata->maxplungequot;
140  	   if( minplungedepth == -1 )
141  	   {
142  	      minplungedepth = SCIPgetMaxDepth(scip)/10;
143  	      if( SCIPgetNStrongbranchLPIterations(scip) > 2*SCIPgetNNodeLPIterations(scip) )
144  	        minplungedepth += 10;
145  	      if( maxplungedepth >= 0 )
146  	         minplungedepth = MIN(minplungedepth, maxplungedepth);
147  	   }
148  	   if( maxplungedepth == -1 )
149  	      maxplungedepth = SCIPgetMaxDepth(scip)/2;
150  	   maxplungedepth = MAX(maxplungedepth, minplungedepth);
151  	
152  	   /* check, if we exceeded the maximal plunging depth */
153  	   plungedepth = SCIPgetPlungeDepth(scip);
154  	   if( plungedepth >= maxplungedepth )
155  	   {
156  	      /* we don't want to plunge again: select best node from the tree */
157  	      SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d -> abort plunging\n", minplungedepth, maxplungedepth, plungedepth);
158  	      *selnode = SCIPgetBestNode(scip);
159  	      SCIPdebugMsg(scip, "  -> best node   : lower=%g\n",
160  	         *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
161  	   }
162  	   else
163  	   {
164  	      SCIP_NODE* node;
165  	      SCIP_Real maxbound;
166  	
167  	      /* check, if plunging is forced at the current depth */
168  	      if( plungedepth < minplungedepth )
169  	      {
170  	         maxbound = SCIPinfinity(scip);
171  	         SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d => maxbound: infinity\n",
172  	            minplungedepth, maxplungedepth, plungedepth);
173  	      }
174  	      else
175  	      {
176  	         SCIP_Real lowerbound;
177  	         SCIP_Real cutoffbound;
178  	         /* get global lower and cutoff bound */
179  	         lowerbound = SCIPgetLowerbound(scip);
180  	         cutoffbound = SCIPgetCutoffbound(scip);
181  	
182  	         /* if we didn't find a solution yet, the cutoff bound is usually very bad:
183  	          * use only 20% of the gap as cutoff bound
184  	          */
185  	         if( SCIPgetNSolsFound(scip) == 0 )
186  	            cutoffbound = lowerbound + 0.2 * (cutoffbound - lowerbound);
187  	         /* calculate maximal plunging bound */
188  	         maxbound = lowerbound + maxplungequot * (cutoffbound - lowerbound);
189  	
190  	         SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d, bounds: [%g,%g], maxbound: %g\n",
191  	            minplungedepth, maxplungedepth, plungedepth, lowerbound, cutoffbound, maxbound);         
192  	      }
193  	
194  	      /* we want to plunge again: prefer children over siblings, and siblings over leaves,
195  	       * but only select a child or sibling, if its dual bound is small enough;
196  	       * prefer using nodes with higher node selection priority assigned by the branching rule
197  	       */
198  	      node = SCIPgetPrioChild(scip);
199  	      if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
200  	      {
201  	         *selnode = node;
202  	         SCIPdebugMsg(scip, "  -> selected prio child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
203  	      }
204  	      else
205  	      {
206  	         node = SCIPgetBestChild(scip);
207  	         if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
208  	         {
209  	            *selnode = node;
210  	            SCIPdebugMsg(scip, "  -> selected best child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
211  	         }
212  	         else
213  	         {
214  	            node = SCIPgetPrioSibling(scip);
215  	            if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
216  	            {
217  	               *selnode = node;
218  	               SCIPdebugMsg(scip, "  -> selected prio sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
219  	            }
220  	            else
221  	            {
222  	               node = SCIPgetBestSibling(scip);
223  	               if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
224  	               {
225  	                  *selnode = node;
226  	                  SCIPdebugMsg(scip, "  -> selected best sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
227  	               }
228  	               else
229  	               {
230  	                  *selnode = SCIPgetBestNode(scip);
231  	                  SCIPdebugMsg(scip, "  -> selected best leaf: lower=%g\n",
232  	                     *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
233  	               }
234  	            }
235  	         }
236  	      }
237  	   }
238  	
239  	   return SCIP_OKAY;
240  	}
241  	
242  	
243  	/** node comparison method of node selector */
244  	static
245  	SCIP_DECL_NODESELCOMP(nodeselCompBfs)
246  	{  /*lint --e{715}*/
247  	   SCIP_Real lowerbound1;
248  	   SCIP_Real lowerbound2;
249  	
250  	   assert(nodesel != NULL);
251  	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
252  	   assert(scip != NULL);
253  	
254  	   lowerbound1 = SCIPnodeGetLowerbound(node1);
255  	   lowerbound2 = SCIPnodeGetLowerbound(node2);
256  	   if( SCIPisLT(scip, lowerbound1, lowerbound2) )
257  	      return -1;
258  	   else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
259  	      return +1;
260  	   else
261  	   {
262  	      SCIP_Real estimate1;
263  	      SCIP_Real estimate2;
264  	
265  	      estimate1 = SCIPnodeGetEstimate(node1);
266  	      estimate2 = SCIPnodeGetEstimate(node2);
267  	      if( (SCIPisInfinity(scip,  estimate1) && SCIPisInfinity(scip,  estimate2)) ||
268  	          (SCIPisInfinity(scip, -estimate1) && SCIPisInfinity(scip, -estimate2)) ||
269  	          SCIPisEQ(scip, estimate1, estimate2) )
270  	      {
271  	         SCIP_NODETYPE nodetype1;
272  	         SCIP_NODETYPE nodetype2;
273  	
274  	         nodetype1 = SCIPnodeGetType(node1);
275  	         nodetype2 = SCIPnodeGetType(node2);
276  	         if( nodetype1 == SCIP_NODETYPE_CHILD && nodetype2 != SCIP_NODETYPE_CHILD )
277  	            return -1;
278  	         else if( nodetype1 != SCIP_NODETYPE_CHILD && nodetype2 == SCIP_NODETYPE_CHILD )
279  	            return +1;
280  	         else if( nodetype1 == SCIP_NODETYPE_SIBLING && nodetype2 != SCIP_NODETYPE_SIBLING )
281  	            return -1;
282  	         else if( nodetype1 != SCIP_NODETYPE_SIBLING && nodetype2 == SCIP_NODETYPE_SIBLING )
283  	            return +1;
284  	         else
285  	         {
286  	            int depth1;
287  	            int depth2;
288  	
289  	            depth1 = SCIPnodeGetDepth(node1);
290  	            depth2 = SCIPnodeGetDepth(node2);
291  	            if( depth1 < depth2 )
292  	               return -1;
293  	            else if( depth1 > depth2 )
294  	               return +1;
295  	            else
296  	               return 0;
297  	         }
298  	      }
299  	
300  	      if( SCIPisLT(scip, estimate1, estimate2) )
301  	         return -1;
302  	
303  	      assert(SCIPisGT(scip, estimate1, estimate2));
304  	      return +1;
305  	   }
306  	}
307  	
308  	
309  	/*
310  	 * bfs specific interface methods
311  	 */
312  	
313  	/** creates the node selector for best first search and includes it in SCIP */
314  	SCIP_RETCODE SCIPincludeNodeselBfs(
315  	   SCIP*                 scip                /**< SCIP data structure */
316  	   )
317  	{
318  	   SCIP_NODESELDATA* nodeseldata;
319  	   SCIP_NODESEL* nodesel;
320  	
321  	   /* allocate and initialize node selector data; this has to be freed in the destructor */
322  	   SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );
323  	
324  	   /* include node selector */
325  	   SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY,
326  	          nodeselSelectBfs, nodeselCompBfs, nodeseldata) );
327  	
328  	   assert(nodesel != NULL);
329  	
330  	   SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyBfs) );
331  	   SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeBfs) );
332  	
333  	   /* add node selector parameters */
334  	   SCIP_CALL( SCIPaddIntParam(scip,
335  	         "nodeselection/bfs/minplungedepth",
336  	         "minimal plunging depth, before new best node may be selected (-1 for dynamic setting)",
337  	         &nodeseldata->minplungedepth, TRUE, MINPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
338  	   SCIP_CALL( SCIPaddIntParam(scip,
339  	         "nodeselection/bfs/maxplungedepth",
340  	         "maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting)",
341  	         &nodeseldata->maxplungedepth, TRUE, MAXPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
342  	   SCIP_CALL( SCIPaddRealParam(scip,
343  	         "nodeselection/bfs/maxplungequot",
344  	         "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where plunging is performed",
345  	         &nodeseldata->maxplungequot, TRUE, MAXPLUNGEQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
346  	
347  	   return SCIP_OKAY;
348  	}
349  	
350