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   branch_nodereopt.c
26   	 * @ingroup DEFPLUGINS_BRANCH
27   	 * @brief  branching rule to reconstruct the search tree
28   	 * @author Jakob Witzig
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	#include <assert.h>
33   	#include <string.h>
34   	
35   	#include "scip/branch_nodereopt.h"
36   	#include "scip/branch_relpscost.h"
37   	#include "scip/scip.h"
38   	#include "scip/tree.h"
39   	#include "scip/pub_reopt.h"
40   	
41   	#define BRANCHRULE_NAME            "nodereopt"
42   	#define BRANCHRULE_DESC            "branching rule for node reoptimization"
43   	#define BRANCHRULE_PRIORITY        -9000000
44   	#define BRANCHRULE_MAXDEPTH            -1
45   	#define BRANCHRULE_MAXBOUNDDIST         1.0
46   	
47   	/*
48   	 * Data structures
49   	 */
50   	
51   	
52   	/** execute the branching of nodes with additional constraints */
53   	static
54   	SCIP_RETCODE Exec(
55   	   SCIP*                 scip,               /**< SCIP data structure */
56   	   SCIP_RESULT*          result              /**< pointer to store the result */
57   	   )
58   	{
59   	   SCIP_REOPTNODE* reoptnode;
60   	   SCIP_NODE* curnode;
61   	   SCIP_REOPTTYPE reopttype;
62   	   SCIP_Bool localrestart;
63   	   unsigned int* childids;
64   	   unsigned int curid;
65   	   int naddedconss;
66   	   int nchilds;
67   	   int childnodessize;
68   	   int ncreatednodes;
69   	   int c;
70   	
71   	   assert(scip != NULL );
72   	   assert(SCIPisReoptEnabled(scip));
73   	
74   	   curnode = SCIPgetCurrentNode(scip);
75   	   assert(curnode != NULL);
76   	
77   	   curid = SCIPnodeGetReoptID(curnode);
78   	   assert(curid >= 1 || SCIPgetRootNode(scip) == curnode);
79   	
80   	   /* calculate local similarity and delete the induced subtree if the similarity is to low */
81   	   localrestart = FALSE;
82   	   SCIP_CALL( SCIPcheckReoptRestart(scip, curnode, &localrestart) );
83   	
84   	   ncreatednodes = 0;
85   	
86   	   if( localrestart )
87   	   {
88   	      *result = SCIP_DIDNOTRUN;
89   	      goto TERMINATE;
90   	   }
91   	
92   	   SCIPdebugMsg(scip, "current node is %lld, ID %u:\n", SCIPnodeGetNumber(curnode), curid);
93   	
94   	   /* get the corresponding node of the reoptimization tree */
95   	   reoptnode = SCIPgetReoptnode(scip, curid);
96   	   assert(reoptnode != NULL);
97   	   reopttype = (SCIP_REOPTTYPE)SCIPreoptnodeGetType(reoptnode);
98   	
99   	   /* The current node is equal to the root and dual reductions were performed. Since the root has a special role
100  	    * within the reoptimiziation we have to split the root node into several nodes and move all stored child nodes to
101  	    * the one representing the root node including all dual reductions as before.
102  	    *
103  	    * @note If the type is infsubtree, there cannot exist a child node and the method SCIPapplyReopt adds a global valid
104  	    * constraint only.
105  	    */
106  	   if( curid == 0 )
107  	   {
108  	      if( reopttype == SCIP_REOPTTYPE_STRBRANCHED || reopttype == SCIP_REOPTTYPE_INFSUBTREE )
109  	      {
110  	         int ncreatedchilds;
111  	
112  	         /* apply the reoptimization at the root node */
113  	         SCIP_CALL( SCIPsplitReoptRoot(scip, &ncreatedchilds, &naddedconss) );
114  	
115  	         if( reopttype == SCIP_REOPTTYPE_INFSUBTREE )
116  	         {
117  	            assert(ncreatedchilds == 0);
118  	            assert(naddedconss == 1);
119  	
120  	            /* there is nothing to do */
121  	            *result = SCIP_DIDNOTRUN;
122  	
123  	            goto TERMINATE;
124  	         }
125  	
126  	         assert(reopttype == SCIP_REOPTTYPE_STRBRANCHED);
127  	         assert(ncreatedchilds >= 2);
128  	
129  	         ncreatednodes += ncreatedchilds;
130  	
131  	         /* We decrease the counter by one because after splitting the root node and moving all children to the node
132  	          * representing the original root with all fixings (caused by dual reductions), we continue reactivating the
133  	          * original children nodes of the root. Thus, the node containing all the fixings can be replaced by the children
134  	          * nodes
135  	          */
136  	         --ncreatednodes;
137  	      }
138  	
139  	      goto REVIVE;
140  	   }
141  	
142  	   /* if we reach this part of the code the current has to be different to the root node */
143  	   assert(curid >= 1);
144  	
145  	  REVIVE:
146  	
147  	   /* get the IDs of all child nodes */
148  	   childnodessize = SCIPreoptnodeGetNChildren(reoptnode);
149  	   SCIP_CALL( SCIPallocBufferArray(scip, &childids, childnodessize) );
150  	   SCIP_CALL( SCIPgetReoptChildIDs(scip, curnode, childids, childnodessize, &nchilds) );
151  	
152  	   if( childnodessize < nchilds )
153  	   {
154  	      childnodessize = SCIPreoptnodeGetNChildren(reoptnode);
155  	      SCIP_CALL( SCIPreallocBufferArray(scip, &childids, childnodessize) );
156  	      SCIP_CALL( SCIPgetReoptChildIDs(scip, curnode, childids, childnodessize, &nchilds) );
157  	   }
158  	   assert(nchilds <= childnodessize);
159  	
160  	   naddedconss = 0;
161  	
162  	   for(c = 0; c < nchilds; c++)
163  	   {
164  	      SCIP_NODE** childnodes;
165  	      SCIP_Bool success;
166  	      unsigned int childid;
167  	      int ncreatedchilds;
168  	
169  	      childid = childids[c];
170  	      assert(childid >= 1);
171  	
172  	      SCIPdebugMsg(scip, "process child at ID %u\n", childid);
173  	
174  	      reoptnode = SCIPgetReoptnode(scip, childid);
175  	      assert(reoptnode != NULL);
176  	
177  	      reopttype = (SCIP_REOPTTYPE)SCIPreoptnodeGetType(reoptnode);
178  	      ncreatedchilds = 0;
179  	
180  	      /* check whether node need to be split */
181  	      if( reopttype == SCIP_REOPTTYPE_STRBRANCHED || reopttype == SCIP_REOPTTYPE_INFSUBTREE )
182  	      {
183  	         /* by default we assume the node get split into two node (because using a constraint to split the node is
184  	          * the default case */
185  	         childnodessize = 2;
186  	      }
187  	      else
188  	      {
189  	         /* we only need to reconstruct the node */
190  	         childnodessize = 1;
191  	      }
192  	
193  	      /* allocate buffer */
194  	      SCIP_CALL( SCIPallocBufferArray(scip, &childnodes, childnodessize) );
195  	
196  	      /* apply the reoptimization */
197  	      SCIP_CALL( SCIPapplyReopt(scip, reoptnode, childid, SCIPnodeGetEstimate(curnode), childnodes, &ncreatedchilds,
198  	            &naddedconss, childnodessize, &success) );
199  	
200  	      if( !success )
201  	      {
202  	         assert(ncreatedchilds > childnodessize);
203  	
204  	         /* reallocate buffer memory */
205  	         childnodessize = ncreatedchilds+1;
206  	         SCIP_CALL( SCIPreallocBufferArray(scip, &childnodes, childnodessize) );
207  	
208  	         /* apply the reoptimization */
209  	         SCIP_CALL( SCIPapplyReopt(scip, reoptnode, childid, SCIPnodeGetEstimate(curnode), childnodes, &ncreatedchilds,
210  	               &naddedconss, childnodessize, &success) );
211  	      }
212  	
213  	      assert(success);
214  	
215  	      /* free buffer memory */
216  	      SCIPfreeBufferArray(scip, &childnodes);
217  	
218  	      ncreatednodes += ncreatedchilds;
219  	   }
220  	
221  	   if( ncreatednodes == 0 )
222  	      *result = SCIP_DIDNOTRUN;
223  	   else
224  	      *result = SCIP_BRANCHED;
225  	
226  	   /* free the buffer memory */
227  	   SCIPfreeBufferArray(scip, &childids);
228  	
229  	  TERMINATE:
230  	
231  	   SCIPdebugMsg(scip, "**** finish reoptimizing %d child nodes of node %lld ****\n", ncreatednodes, SCIPnodeGetNumber(curnode));
232  	
233  	   return SCIP_OKAY;
234  	}
235  	
236  	/*
237  	 * Callback methods of branching rule
238  	 */
239  	
240  	/** copy method for branchrule plugins (called when SCIP copies plugins) */
241  	static
242  	SCIP_DECL_BRANCHCOPY(branchCopyNodereopt)
243  	{  /*lint --e{715}*/
244  	   assert(scip != NULL);
245  	   assert(branchrule != NULL);
246  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
247  	
248  	   /* call inclusion method of branchrule */
249  	   SCIP_CALL( SCIPincludeBranchruleNodereopt(scip) );
250  	
251  	   return SCIP_OKAY;
252  	}
253  	
254  	/** branching execution method for fractional LP solutions */
255  	static
256  	SCIP_DECL_BRANCHEXECLP(branchExeclpNodereopt)
257  	{/*lint --e{715}*/
258  	   assert(branchrule != NULL );
259  	   assert(*result != SCIP_BRANCHED);
260  	
261  	   *result = SCIP_DIDNOTRUN;
262  	
263  	   if( SCIPisReoptEnabled(scip) && SCIPreoptimizeNode(scip, SCIPgetCurrentNode(scip)) )
264  	   {
265  	      SCIP_VAR** branchcands;
266  	      SCIP_Real* branchcandssol;
267  	      SCIP_Real* branchcandsfrac;
268  	      SCIP_Real objsimrootlp;
269  	      SCIP_Bool sbinit;
270  	      int nbranchcands;
271  	
272  	      assert(SCIPgetNReoptRuns(scip) > 1);
273  	
274  	      SCIP_CALL( SCIPgetBoolParam(scip, "reoptimization/strongbranchinginit", &sbinit) );
275  	      SCIP_CALL( SCIPgetRealParam(scip, "reoptimization/objsimrootLP", &objsimrootlp) );
276  	
277  	      if( sbinit && SCIPgetCurrentNode(scip) == SCIPgetRootNode(scip)
278  	       && SCIPgetReoptSimilarity(scip, SCIPgetNReoptRuns(scip)-1, SCIPgetNReoptRuns(scip)) <= objsimrootlp ) /* check objsimrootlp */
279  	      {
280  	         /* get branching candidates */
281  	         SCIP_CALL( SCIPgetLPBranchCands(scip, &branchcands, &branchcandssol, &branchcandsfrac, NULL, &nbranchcands, NULL) );
282  	
283  	         /* run strong branching initialization */
284  	         if( nbranchcands > 0 )
285  	         {
286  	            SCIP_CALL( SCIPexecRelpscostBranching(scip, branchcands, branchcandssol, branchcandsfrac, nbranchcands, FALSE, result) );
287  	            assert(*result == SCIP_DIDNOTRUN || *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM || *result == SCIP_CONSADDED);
288  	         }
289  	      }
290  	
291  	      if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
292  	      {
293  	         assert((SCIPnodeGetReoptID(SCIPgetCurrentNode(scip)) == 0 && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 )
294  	              || 1 <= SCIPnodeGetReoptID(SCIPgetCurrentNode(scip)));
295  	
296  	         SCIP_CALL( Exec(scip, result) );
297  	      }
298  	   }
299  	
300  	   return SCIP_OKAY;
301  	}
302  	
303  	/** branching execution method for external candidates */
304  	static SCIP_DECL_BRANCHEXECEXT(branchExecextNodereopt)
305  	{/*lint --e{715}*/
306  	   assert(branchrule != NULL );
307  	   assert(*result != SCIP_BRANCHED);
308  	
309  	   *result = SCIP_DIDNOTRUN;
310  	
311  	   if( SCIPisReoptEnabled(scip) && SCIPreoptimizeNode(scip, SCIPgetCurrentNode(scip)) )
312  	   {
313  	      assert((SCIPnodeGetReoptID(SCIPgetCurrentNode(scip)) == 0 && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 )
314  	           || 1 <= SCIPnodeGetReoptID(SCIPgetCurrentNode(scip)));
315  	
316  	      SCIP_CALL( Exec(scip, result) );
317  	   }
318  	
319  	   return SCIP_OKAY;
320  	}
321  	
322  	/** branching execution method for not completely fixed pseudo solutions */
323  	static SCIP_DECL_BRANCHEXECPS(branchExecpsNodereopt)
324  	{/*lint --e{715}*/
325  	   assert(branchrule != NULL );
326  	   assert(*result != SCIP_BRANCHED);
327  	
328  	   *result = SCIP_DIDNOTRUN;
329  	
330  	   if( SCIPisReoptEnabled(scip) && SCIPreoptimizeNode(scip, SCIPgetCurrentNode(scip)) )
331  	   {
332  	      assert((SCIPnodeGetReoptID(SCIPgetCurrentNode(scip)) == 0 && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 )
333  	           || 1 <= SCIPnodeGetReoptID(SCIPgetCurrentNode(scip)));
334  	
335  	      SCIP_CALL( Exec(scip, result) );
336  	   }
337  	
338  	   return SCIP_OKAY;
339  	}
340  	
341  	/*
342  	 * branching rule specific interface methods
343  	 */
344  	
345  	/** creates the nodereopt branching rule and includes it in SCIP */
346  	SCIP_RETCODE SCIPincludeBranchruleNodereopt(
347  	   SCIP*                 scip                /**< SCIP data structure */
348  	   )
349  	{
350  	   SCIP_BRANCHRULE* branchrule;
351  	
352  	   assert(scip != NULL );
353  	
354  	   /* include nodereopt branching rule */
355  	   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC,
356  	         BRANCHRULE_PRIORITY, BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, NULL));
357  	
358  	   assert(branchrule != NULL );
359  	
360  	   /* set non fundamental callbacks via setter functions */
361  	   SCIP_CALL(SCIPsetBranchruleCopy(scip, branchrule, branchCopyNodereopt));
362  	   SCIP_CALL(SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpNodereopt));
363  	   SCIP_CALL(SCIPsetBranchruleExecExt(scip, branchrule, branchExecextNodereopt));
364  	   SCIP_CALL(SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsNodereopt));
365  	
366  	   return SCIP_OKAY;
367  	}
368