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