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