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