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_estimate.c
26   	 * @ingroup DEFPLUGINS_NODESEL
27   	 * @brief  node selector for best estimate 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_estimate.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 <string.h>
45   	
46   	#define NODESEL_NAME             "estimate"
47   	#define NODESEL_DESC             "best estimate search"
48   	#define NODESEL_STDPRIORITY      200000
49   	#define NODESEL_MEMSAVEPRIORITY     100
50   	
51   	
52   	/*
53   	 * Default parameter settings
54   	 */
55   	
56   	#define DEFAULT_MINPLUNGEDEPTH       -1 /**< minimal plunging depth, before new best node may be selected (-1 for dynamic setting) */
57   	#define DEFAULT_MAXPLUNGEDEPTH       -1 /**< maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting) */
58   	#define DEFAULT_MAXPLUNGEQUOT      0.25 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
59   	                                         *   where plunging is performed */
60   	#define DEFAULT_BESTNODEFREQ         10 /**< frequency at which the best node instead of the best estimate is selected (0: never) */
61   	#define DEFAULT_BREADTHFIRSTDEPTH    -1 /**< depth until breadth-first search is applied (-1: never) */
62   	#define DEFAULT_PLUNGEOFFSET          0 /**< number of nodes before doing plunging the first time */
63   	
64   	
65   	/** node selector data for best estimate search node selection */
66   	struct SCIP_NodeselData
67   	{
68   	   SCIP_Real             maxplungequot;      /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
69   	                                              *   where plunging is performed */
70   	   int                   minplungedepth;     /**< minimal plunging depth, before new best node may be selected
71   	                                              *   (-1 for dynamic setting) */
72   	   int                   maxplungedepth;     /**< maximal plunging depth, before new best node is forced to be selected
73   	                                              *   (-1 for dynamic setting) */
74   	   int                   bestnodefreq;       /**< frequency at which the best node instead of the best estimate is selected
75   	                                              *   (0: never) */
76   	   int                   breadthfirstdepth;  /**< depth until breadth-fisrt search is applied */
77   	   int                   plungeoffset;       /**< number of nodes before doing plunging the first time */
78   	};
79   	
80   	
81   	/*
82   	 * Callback methods
83   	 */
84   	
85   	/** copy method for node selector plugins (called when SCIP copies plugins) */
86   	static
87   	SCIP_DECL_NODESELCOPY(nodeselCopyEstimate)
88   	{  /*lint --e{715}*/
89   	   assert(scip != NULL);
90   	   assert(nodesel != NULL);
91   	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
92   	
93   	   /* call inclusion method of node selector */
94   	   SCIP_CALL( SCIPincludeNodeselEstimate(scip) );
95   	
96   	   return SCIP_OKAY;
97   	}
98   	
99   	/** destructor of node selector to free user data (called when SCIP is exiting) */
100  	static
101  	SCIP_DECL_NODESELFREE(nodeselFreeEstimate)
102  	{  /*lint --e{715}*/
103  	   SCIP_NODESELDATA* nodeseldata;
104  	
105  	   assert(nodesel != NULL);
106  	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
107  	   assert(scip != NULL);
108  	
109  	   /* free user data of node selector */
110  	   nodeseldata = SCIPnodeselGetData(nodesel);
111  	   assert(nodeseldata != NULL);
112  	   SCIPfreeBlockMemory(scip, &nodeseldata);
113  	   SCIPnodeselSetData(nodesel, nodeseldata);
114  	
115  	   return SCIP_OKAY;
116  	}
117  	
118  	
119  	/** node selection method of node selector */
120  	static
121  	SCIP_DECL_NODESELSELECT(nodeselSelectEstimate)
122  	{  /*lint --e{715}*/
123  	   SCIP_NODESELDATA* nodeseldata;
124  	   int minplungedepth;
125  	   int maxplungedepth;
126  	   int plungedepth;
127  	   int bestnodefreq;
128  	   SCIP_Real maxplungequot;
129  	
130  	   assert(nodesel != NULL);
131  	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
132  	   assert(scip != NULL);
133  	   assert(selnode != NULL);
134  	
135  	   *selnode = NULL;
136  	
137  	   /* get node selector user data */
138  	   nodeseldata = SCIPnodeselGetData(nodesel);
139  	   assert(nodeseldata != NULL);
140  	
141  	   /* check if the breadth-first search should be applied */
142  	   if( SCIPgetDepth(scip) <= nodeseldata->breadthfirstdepth )
143  	   {
144  	      SCIP_NODE* node;
145  	
146  	      SCIPdebugMsg(scip, "perform breadth-first search at depth <%d>\n", SCIPgetDepth(scip));
147  	
148  	      node = SCIPgetPrioSibling(scip);
149  	      if( node != NULL )
150  	      {
151  	         *selnode = node;
152  	         SCIPdebugMsg(scip, "  -> selected prio sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
153  	         return SCIP_OKAY;
154  	      }
155  	
156  	      node = SCIPgetPrioChild(scip);
157  	      if( node != NULL )
158  	      {
159  	         *selnode = node;
160  	         SCIPdebugMsg(scip, "  -> selected prio child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
161  	         return SCIP_OKAY;
162  	      }
163  	   }
164  	
165  	   bestnodefreq = (nodeseldata->bestnodefreq == 0 ? INT_MAX : nodeseldata->bestnodefreq);
166  	
167  	   /* check if we don't want to do plunging yet */
168  	   if( SCIPgetNNodes(scip) < nodeseldata->plungeoffset )
169  	   {
170  	      /* we don't want to plunge yet: select best node from the tree */
171  	      SCIPdebugMsg(scip, "nnodes=%" SCIP_LONGINT_FORMAT " < %d=plungeoffset -> don't start plunging\n", SCIPgetNNodes(scip),
172  	         nodeseldata->plungeoffset);
173  	
174  	      if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
175  	         *selnode = SCIPgetBestboundNode(scip);
176  	      else
177  	         *selnode = SCIPgetBestNode(scip);
178  	      SCIPdebugMsg(scip, "  -> best node   : lower=%g\n",
179  	         *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
180  	      return SCIP_OKAY;
181  	   }
182  	
183  	   /* calculate minimal and maximal plunging depth */
184  	   minplungedepth = nodeseldata->minplungedepth;
185  	   maxplungedepth = nodeseldata->maxplungedepth;
186  	   maxplungequot = nodeseldata->maxplungequot;
187  	   if( minplungedepth == -1 )
188  	   {
189  	      minplungedepth = SCIPgetMaxDepth(scip)/10;
190  	      if( SCIPgetNStrongbranchLPIterations(scip) > 2*SCIPgetNNodeLPIterations(scip) )
191  	        minplungedepth += 10;
192  	      if( maxplungedepth >= 0 )
193  	         minplungedepth = MIN(minplungedepth, maxplungedepth);
194  	   }
195  	   if( maxplungedepth == -1 )
196  	      maxplungedepth = SCIPgetMaxDepth(scip)/2;
197  	   maxplungedepth = MAX(maxplungedepth, minplungedepth);
198  	
199  	   /* check, if we exceeded the maximal plunging depth */
200  	   plungedepth = SCIPgetPlungeDepth(scip);
201  	   if( plungedepth > maxplungedepth )
202  	   {
203  	      /* we don't want to plunge again: select best node from the tree */
204  	      SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d -> abort plunging\n", minplungedepth, maxplungedepth, plungedepth);
205  	      if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
206  	         *selnode = SCIPgetBestboundNode(scip);
207  	      else
208  	         *selnode = SCIPgetBestNode(scip);
209  	      SCIPdebugMsg(scip, "  -> best node   : lower=%g\n",
210  	         *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
211  	   }
212  	   else
213  	   {
214  	      SCIP_NODE* node;
215  	      SCIP_Real lowerbound;
216  	      SCIP_Real cutoffbound;
217  	      SCIP_Real maxbound;
218  	
219  	      /* get global lower and cutoff bound */
220  	      lowerbound = SCIPgetLowerbound(scip);
221  	      cutoffbound = SCIPgetCutoffbound(scip);
222  	
223  	      /* if we didn't find a solution yet, the cutoff bound is usually very bad:
224  	       * use only 20% of the gap as cutoff bound
225  	       */
226  	      if( SCIPgetNSolsFound(scip) == 0 )
227  	         cutoffbound = lowerbound + 0.2 * (cutoffbound - lowerbound);
228  	
229  	      /* check, if plunging is forced at the current depth */
230  	      if( plungedepth < minplungedepth )
231  	         maxbound = SCIPinfinity(scip);
232  	      else
233  	      {
234  	         /* calculate maximal plunging bound */
235  	         maxbound = lowerbound + maxplungequot * (cutoffbound - lowerbound);
236  	      }
237  	
238  	      SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d, bounds: [%g,%g], maxbound: %g\n",
239  	         minplungedepth, maxplungedepth, plungedepth, lowerbound, cutoffbound, maxbound);
240  	
241  	      /* we want to plunge again: prefer children over siblings, and siblings over leaves,
242  	       * but only select a child or sibling, if its estimate is small enough;
243  	       * prefer using nodes with higher node selection priority assigned by the branching rule
244  	       */
245  	      node = SCIPgetPrioChild(scip);
246  	      if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
247  	      {
248  	         *selnode = node;
249  	         SCIPdebugMsg(scip, "  -> selected prio child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
250  	      }
251  	      else
252  	      {
253  	         node = SCIPgetBestChild(scip);
254  	         if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
255  	         {
256  	            *selnode = node;
257  	            SCIPdebugMsg(scip, "  -> selected best child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
258  	         }
259  	         else
260  	         {
261  	            node = SCIPgetPrioSibling(scip);
262  	            if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
263  	            {
264  	               *selnode = node;
265  	               SCIPdebugMsg(scip, "  -> selected prio sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
266  	            }
267  	            else
268  	            {
269  	               node = SCIPgetBestSibling(scip);
270  	               if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
271  	               {
272  	                  *selnode = node;
273  	                  SCIPdebugMsg(scip, "  -> selected best sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
274  	               }
275  	               else
276  	               {
277  	                  if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
278  	                     *selnode = SCIPgetBestboundNode(scip);
279  	                  else
280  	                     *selnode = SCIPgetBestNode(scip);
281  	                  SCIPdebugMsg(scip, "  -> selected best leaf: estimate=%g\n",
282  	                     *selnode != NULL ? SCIPnodeGetEstimate(*selnode) : SCIPinfinity(scip));
283  	               }
284  	            }
285  	         }
286  	      }
287  	   }
288  	
289  	   return SCIP_OKAY;
290  	}
291  	
292  	
293  	/** node comparison method of node selector */
294  	static
295  	SCIP_DECL_NODESELCOMP(nodeselCompEstimate)
296  	{  /*lint --e{715}*/
297  	   SCIP_Real estimate1;
298  	   SCIP_Real estimate2;
299  	
300  	   assert(nodesel != NULL);
301  	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
302  	   assert(scip != NULL);
303  	
304  	   estimate1 = SCIPnodeGetEstimate(node1);
305  	   estimate2 = SCIPnodeGetEstimate(node2);
306  	   if( (SCIPisInfinity(scip,  estimate1) && SCIPisInfinity(scip,  estimate2)) ||
307  	       (SCIPisInfinity(scip, -estimate1) && SCIPisInfinity(scip, -estimate2)) ||
308  	       SCIPisEQ(scip, estimate1, estimate2) )
309  	   {
310  	      SCIP_Real lowerbound1;
311  	      SCIP_Real lowerbound2;
312  	
313  	      lowerbound1 = SCIPnodeGetLowerbound(node1);
314  	      lowerbound2 = SCIPnodeGetLowerbound(node2);
315  	      if( SCIPisLT(scip, lowerbound1, lowerbound2) )
316  	         return -1;
317  	      else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
318  	         return +1;
319  	      else
320  	      {
321  	         SCIP_NODETYPE nodetype1;
322  	         SCIP_NODETYPE nodetype2;
323  	
324  	         nodetype1 = SCIPnodeGetType(node1);
325  	         nodetype2 = SCIPnodeGetType(node2);
326  	         if( nodetype1 == SCIP_NODETYPE_CHILD && nodetype2 != SCIP_NODETYPE_CHILD )
327  	            return -1;
328  	         else if( nodetype1 != SCIP_NODETYPE_CHILD && nodetype2 == SCIP_NODETYPE_CHILD )
329  	            return +1;
330  	         else if( nodetype1 == SCIP_NODETYPE_SIBLING && nodetype2 != SCIP_NODETYPE_SIBLING )
331  	            return -1;
332  	         else if( nodetype1 != SCIP_NODETYPE_SIBLING && nodetype2 == SCIP_NODETYPE_SIBLING )
333  	            return +1;
334  	         else
335  	         {
336  	            int depth1;
337  	            int depth2;
338  	
339  	            depth1 = SCIPnodeGetDepth(node1);
340  	            depth2 = SCIPnodeGetDepth(node2);
341  	            if( depth1 < depth2 )
342  	               return -1;
343  	            else if( depth1 > depth2 )
344  	               return +1;
345  	            else
346  	               return 0;
347  	         }
348  	      }
349  	   }
350  	
351  	   if( SCIPisLT(scip, estimate1, estimate2) )
352  	      return -1;
353  	
354  	   assert(SCIPisGT(scip, estimate1, estimate2));
355  	   return +1;
356  	}
357  	
358  	
359  	/*
360  	 * estimate specific interface methods
361  	 */
362  	
363  	/** creates the node selector for best estimate search and includes it in SCIP */
364  	SCIP_RETCODE SCIPincludeNodeselEstimate(
365  	   SCIP*                 scip                /**< SCIP data structure */
366  	   )
367  	{
368  	   SCIP_NODESELDATA* nodeseldata;
369  	   SCIP_NODESEL* nodesel;
370  	
371  	   /* allocate and initialize node selector data; this has to be freed in the destructor */
372  	   SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );
373  	
374  	   /* include node selector */
375  	   SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY,
376  	          nodeselSelectEstimate, nodeselCompEstimate, nodeseldata) );
377  	
378  	   assert(nodesel != NULL);
379  	
380  	   SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyEstimate) );
381  	   SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeEstimate) );
382  	
383  	   /* add node selector parameters */
384  	   SCIP_CALL( SCIPaddIntParam(scip,
385  	         "nodeselection/estimate/minplungedepth",
386  	         "minimal plunging depth, before new best node may be selected (-1 for dynamic setting)",
387  	         &nodeseldata->minplungedepth, TRUE, DEFAULT_MINPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
388  	   SCIP_CALL( SCIPaddIntParam(scip,
389  	         "nodeselection/estimate/maxplungedepth",
390  	         "maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting)",
391  	         &nodeseldata->maxplungedepth, TRUE, DEFAULT_MAXPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
392  	   SCIP_CALL( SCIPaddRealParam(scip,
393  	         "nodeselection/estimate/maxplungequot",
394  	         "maximal quotient (estimate - lowerbound)/(cutoffbound - lowerbound) where plunging is performed",
395  	         &nodeseldata->maxplungequot, TRUE, DEFAULT_MAXPLUNGEQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
396  	   SCIP_CALL( SCIPaddIntParam(scip,
397  	         "nodeselection/estimate/bestnodefreq",
398  	         "frequency at which the best node instead of the best estimate is selected (0: never)",
399  	         &nodeseldata->bestnodefreq, FALSE, DEFAULT_BESTNODEFREQ, 0, INT_MAX, NULL, NULL) );
400  	   SCIP_CALL( SCIPaddIntParam(scip,
401  	         "nodeselection/estimate/breadthfirstdepth",
402  	         "depth until breadth-first search is applied",
403  	         &nodeseldata->breadthfirstdepth, FALSE, DEFAULT_BREADTHFIRSTDEPTH, -1, INT_MAX, NULL, NULL) );
404  	   SCIP_CALL( SCIPaddIntParam(scip,
405  	         "nodeselection/estimate/plungeoffset",
406  	         "number of nodes before doing plunging the first time",
407  	         &nodeseldata->plungeoffset, FALSE, DEFAULT_PLUNGEOFFSET, 0, INT_MAX, NULL, NULL) );
408  	
409  	   return SCIP_OKAY;
410  	}
411  	
412