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 compr_weakcompr.c 26 * @ingroup OTHER_CFILES 27 * @brief weakcompr tree compression 28 * @author Jakob Witzig 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/compr_weakcompr.h" 35 #include "scip/pub_compr.h" 36 #include "scip/pub_message.h" 37 #include "scip/pub_misc_sort.h" 38 #include "scip/pub_reopt.h" 39 #include "scip/pub_tree.h" 40 #include "scip/scip_compr.h" 41 #include "scip/scip_general.h" 42 #include "scip/scip_mem.h" 43 #include "scip/scip_message.h" 44 #include "scip/scip_numerics.h" 45 #include "scip/scip_param.h" 46 #include "scip/scip_prob.h" 47 #include "scip/scip_reopt.h" 48 #include "scip/scip_tree.h" 49 #include <string.h> 50 51 #define COMPR_NAME "weakcompr" 52 #define COMPR_DESC "reduce the search frontier to k+1 or max{2, |C|+1} nodes." 53 #define COMPR_PRIORITY 1000 54 #define COMPR_MINNNODES 50 55 56 #define DEFAULT_MEM_REPR 2 /* since we cannot convert the added constraints into node currently, we choose 2 as default value */ 57 /* 58 * Data structures 59 */ 60 61 /** tree compression data */ 62 struct SCIP_ComprData 63 { 64 /* representative data */ 65 SCIP_REOPTNODE** representatives; /**< list of representatives */ 66 int nrepresentatives; /**< number of representatives */ 67 int representativessize;/**< size of array representatives */ 68 SCIP_Bool initialized; /**< was compressor data initialized? */ 69 70 /* parameter */ 71 SCIP_Bool convertconss; /**< convert added logic-or constraints of size k into k nodes */ 72 }; 73 74 75 /* 76 * Local methods 77 */ 78 79 /** sort the ids of child nodes by their dual bound of the last iteration */ 80 static 81 SCIP_RETCODE sortIDs( 82 SCIP* scip, /**< SCIP data structure */ 83 unsigned int* childids, /**< array of child ids */ 84 int nchildids /**< first position */ 85 ) 86 { 87 SCIP_Real* lowerbounds; 88 int i; 89 90 SCIP_CALL( SCIPallocBufferArray(scip, &lowerbounds, nchildids) ); 91 92 for( i = 0; i < nchildids; i++ ) 93 { 94 lowerbounds[i] = SCIPreoptnodeGetLowerbound(SCIPgetReoptnode(scip, childids[i])); 95 } 96 97 /* sort the ids in decreasing order */ 98 SCIPsortDownRealInt(lowerbounds, (signed int*)childids, nchildids); 99 100 /* free buffer memory */ 101 SCIPfreeBufferArray(scip, &lowerbounds); 102 103 return SCIP_OKAY; 104 } 105 106 /** check of enough memory is allocated and reallocate of necessary. */ 107 static 108 SCIP_RETCODE checkMemSize( 109 SCIP* scip, /**< SCIP data structure */ 110 SCIP_COMPRDATA* comprdata, /**< compression data */ 111 int nrepresentatives /**< number of representatives */ 112 ) 113 { 114 assert(scip != NULL); 115 assert(comprdata != NULL); 116 117 if( comprdata->representativessize < nrepresentatives ) 118 { 119 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &comprdata->representatives, comprdata->representativessize, nrepresentatives) ); 120 comprdata->representativessize = nrepresentatives; 121 } 122 123 return SCIP_OKAY; 124 } 125 126 /** try to find a good representation 127 * 128 * @todo implement: 129 * 1) using k nodes without added constraint; 130 * 2) resolve the added nods via some kind of interdiction branching 131 */ 132 static 133 SCIP_RETCODE constructCompression( 134 SCIP* scip, /**< SCIP data structure */ 135 SCIP_COMPR* compr, /**< compression method */ 136 SCIP_COMPRDATA* comprdata, /**< compression data */ 137 SCIP_RESULT* result /**< result pointer */ 138 ) 139 { 140 SCIP_NODE* currentnode; 141 SCIP_VAR**** conss_var; 142 SCIP_VAR*** vars; 143 SCIP_Real*** conss_val; 144 SCIP_Real** vals; 145 SCIP_BOUNDTYPE** boundtypes; 146 SCIP_BOUNDTYPE*** conss_boundtypes; 147 int** conss_nvars; 148 unsigned int* leaveids; 149 int* nconss; 150 int* nvars; 151 int mem_vars; 152 int nids; 153 int nleaveids; 154 int pos_repr_fix; 155 int size; 156 int k; 157 int r; 158 159 assert(scip != NULL); 160 assert(comprdata != NULL); 161 162 *result = SCIP_DIDNOTRUN; 163 164 size = 1; 165 currentnode = SCIPgetStage(scip) <= SCIP_STAGE_PRESOLVED ? NULL : SCIPgetCurrentNode(scip); 166 167 if( SCIPgetStage(scip) <= SCIP_STAGE_PRESOLVED ) 168 nleaveids = SCIPgetNReoptLeaves(scip, currentnode); 169 else 170 { 171 assert(currentnode != NULL); 172 nleaveids = SCIPgetNReoptLeaves(scip, currentnode); 173 } 174 175 SCIPdebugMsg(scip, ">> start <%s> at node %" SCIP_LONGINT_FORMAT " (nleaves: %d, depth: %d)\n", COMPR_NAME, 176 SCIPgetStage(scip) >= SCIP_STAGE_PRESOLVED ? 0 : SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), 177 nleaveids, SCIPgetStage(scip) <= SCIP_STAGE_PRESOLVED ? 0 : SCIPnodeGetDepth(currentnode)); 178 179 if( SCIPcomprGetMinNodes(compr) > nleaveids ) 180 { 181 SCIPdebugMsg(scip, "-> skip compression (min. leaves = %d)\n", SCIPcomprGetMinNodes(compr)); 182 return SCIP_OKAY; 183 } 184 185 if( nleaveids == 0 ) 186 { 187 SCIPdebugMsg(scip, "-> skip compression (k = %d, nleaves = %d)\n", 1, nleaveids); 188 return SCIP_OKAY; 189 } 190 191 SCIPdebugMsg(scip, "-> try compression with %d node(s)\n", 1); 192 193 *result = SCIP_DIDNOTFIND; 194 195 /* collect the nodes to compress */ 196 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &leaveids, nleaveids) ); 197 198 SCIP_CALL( SCIPgetReoptLeaveIDs(scip, currentnode, leaveids, nleaveids, &nids) ); 199 assert(nids == nleaveids); 200 201 /* sort the ids */ 202 SCIP_CALL( sortIDs(scip, leaveids, nleaveids) ); 203 204 /* allocate memory to store the old tree */ 205 206 mem_vars = 2*SCIPgetNVars(scip); 207 208 /* we use normal instead of buffer memory because we may need to reallocate the 2-dimensional arrays */ 209 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars, size) ); 210 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vals, size) ); 211 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &boundtypes, size) ); 212 213 /* allocate buffer memory */ 214 SCIP_CALL( SCIPallocBufferArray(scip, &conss_var, size) ); 215 SCIP_CALL( SCIPallocBufferArray(scip, &conss_val, size) ); 216 SCIP_CALL( SCIPallocBufferArray(scip, &conss_boundtypes, size) ); 217 SCIP_CALL( SCIPallocBufferArray(scip, &conss_nvars, size) ); 218 SCIP_CALL( SCIPallocBufferArray(scip, &nvars, size) ); 219 SCIP_CALL( SCIPallocBufferArray(scip, &nconss, size) ); 220 221 /* get data of nodes */ 222 for( k = size-1; k < 1; k++ ) 223 { 224 SCIP_REOPTNODE* reoptnode; 225 int mem_conss; 226 int nvars2; 227 int nafterdualvars; 228 SCIPdebug(int c); 229 230 /* we use normal instead of buffer memory because we may need to reallocate the 2-dimensional arrays */ 231 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars[k], mem_vars) ); 232 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vals[k], mem_vars) ); 233 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &boundtypes[k], mem_vars) ); 234 235 /* get the branching path */ 236 reoptnode = SCIPgetReoptnode(scip, leaveids[k]); 237 assert(reoptnode != NULL); 238 239 SCIPgetReoptnodePath(scip, reoptnode, vars[k], vals[k], boundtypes[k], mem_vars, &nvars2, &nafterdualvars); 240 assert(mem_vars >= nvars2 + nafterdualvars); 241 242 nvars[k] = nvars2 + nafterdualvars; 243 244 /* get the constraints */ 245 mem_conss = SCIPreoptnodeGetNConss(reoptnode); 246 247 SCIP_CALL( SCIPallocBufferArray(scip, &conss_var[k], mem_conss) ); /*lint !e866*/ 248 SCIP_CALL( SCIPallocBufferArray(scip, &conss_val[k], mem_conss) ); /*lint !e866*/ 249 SCIP_CALL( SCIPallocBufferArray(scip, &conss_boundtypes[k], mem_conss) ); /*lint !e866*/ 250 SCIP_CALL( SCIPallocBufferArray(scip, &conss_nvars[k], mem_conss) ); /*lint !e866*/ 251 252 SCIPreoptnodeGetConss(reoptnode, conss_var[k], conss_val[k], conss_boundtypes[k], mem_conss, &nconss[k], 253 conss_nvars[k]); 254 assert(mem_conss == nconss[k]); 255 256 #ifdef SCIP_DEBUG 257 for( c = 0; c < mem_conss; c++ ) 258 assert(conss_nvars[k][c] <= SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)); 259 #endif 260 261 #ifndef NDEBUG 262 reoptnode = SCIPgetReoptnode(scip, leaveids[k]); 263 assert(reoptnode != NULL); 264 265 SCIPdebugMsg(scip, "-> use node at id %u, %d vars, %d conss, lowerbound = %.g\n", leaveids[k], nvars[k], 266 SCIPreoptnodeGetNConss(reoptnode), SCIPreoptnodeGetLowerbound(reoptnode)); 267 #endif 268 } 269 270 /* perform the compression */ 271 assert(comprdata->nrepresentatives == 0); 272 273 pos_repr_fix = 1; 274 275 /* calculate the number of representatives */ 276 comprdata->nrepresentatives = (nvars[0] > 0 ? 2 : 1); 277 comprdata->nrepresentatives += nconss[0]; 278 279 /* check memory size */ 280 SCIP_CALL( checkMemSize(scip, comprdata, comprdata->nrepresentatives) ); 281 assert(comprdata->nrepresentatives <= comprdata->representativessize); 282 283 /* initialize the representatives */ 284 SCIP_CALL( SCIPinitRepresentation(scip, comprdata->representatives, comprdata->nrepresentatives) ); 285 286 /* create 2 candidates for the fixed variables */ 287 if( nvars[0] >= 1 ) 288 { 289 SCIP_Bool linear; 290 int v; 291 292 assert(pos_repr_fix < comprdata->nrepresentatives); 293 294 linear = TRUE; /* todo: we have to adapt the compression to handle integer variables */ 295 296 /* create a representative at position 1 with fixed branching path */ 297 assert(SCIPreoptnodeGetNVars(comprdata->representatives[pos_repr_fix]) == 0); 298 for( r = pos_repr_fix; r < comprdata->nrepresentatives; r++ ) 299 { 300 /* copy the branching path to all representatives */ 301 assert(comprdata->representatives[r] != NULL); 302 303 for( v = 0; v < nvars[0]; v++ ) 304 { 305 SCIP_CALL( SCIPaddReoptnodeBndchg(scip, comprdata->representatives[r], vars[0][v], 306 vals[0][v], SCIPisFeasEQ(scip, vals[0][v], 1.0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) ); 307 } 308 } 309 310 /* create a representative at position 0 with an added constraint corresponding 311 * to the branching path of the node 312 */ 313 assert(comprdata->representatives[pos_repr_fix-1] != NULL); 314 SCIP_CALL( SCIPaddReoptnodeCons(scip, comprdata->representatives[pos_repr_fix-1], vars[0], vals[0], boundtypes[k], 315 1.0, SCIPinfinity(scip), nvars[0], REOPT_CONSTYPE_DUALREDS, linear) ); 316 } 317 318 assert(0 <= pos_repr_fix && pos_repr_fix < comprdata->nrepresentatives); 319 320 /* create nconss[0] nodes for the added constraints */ 321 for( k = 0; k < nconss[0]; k++ ) 322 { 323 SCIP_Bool linear; 324 int v; 325 326 assert(pos_repr_fix < comprdata->nrepresentatives); 327 328 linear = TRUE; /* todo: we have to adapt the compression to handle integer variables */ 329 330 /* create a node with fixed bounds corresponding to constraint at position k */ 331 332 /* fix the branching path */ 333 for( v = 0; v < conss_nvars[0][k]; v++ ) 334 { 335 SCIP_CALL( SCIPaddReoptnodeBndchg(scip, comprdata->representatives[pos_repr_fix], conss_var[0][k][v], 336 conss_val[0][k][v], SCIPisFeasEQ(scip, conss_val[0][k][v], 1.0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) ); 337 } 338 339 /* add this constraint to all further representatives */ 340 for( r = pos_repr_fix + 1; r < comprdata->nrepresentatives; r++ ) 341 { 342 SCIP_CALL( SCIPaddReoptnodeCons(scip, comprdata->representatives[r], conss_var[0][k], conss_val[0][k], 343 conss_boundtypes[0][k], 1.0, SCIPinfinity(scip), conss_nvars[0][k], REOPT_CONSTYPE_DUALREDS, linear) ); 344 } 345 346 pos_repr_fix++; 347 } 348 349 /* @todo use more than one node */ 350 351 *result = SCIP_SUCCESS; 352 353 SCIPdebugMsg(scip, "-> found representation of size %d.\n", comprdata->nrepresentatives); 354 355 /* free memory */ 356 for( k = size-1; k >= 0; k-- ) 357 { 358 SCIPfreeBufferArray(scip, &conss_nvars[k]); 359 SCIPfreeBufferArray(scip, &conss_val[k]); 360 SCIPfreeBufferArray(scip, &conss_var[k]); 361 SCIPfreeBlockMemoryArray(scip, &boundtypes[k], mem_vars); 362 SCIPfreeBlockMemoryArray(scip, &vals[k], mem_vars); 363 SCIPfreeBlockMemoryArray(scip, &vars[k], mem_vars); 364 } 365 366 SCIPfreeBufferArray(scip, &nconss); 367 SCIPfreeBufferArray(scip, &nvars); 368 SCIPfreeBufferArray(scip, &conss_nvars); 369 SCIPfreeBufferArray(scip, &conss_val); 370 SCIPfreeBufferArray(scip, &conss_var); 371 SCIPfreeBlockMemoryArray(scip, &boundtypes, size); 372 SCIPfreeBlockMemoryArray(scip, &vals, size); 373 SCIPfreeBlockMemoryArray(scip, &vars, size); 374 375 SCIPfreeBlockMemoryArray(scip, &leaveids, nleaveids); 376 377 return SCIP_OKAY; 378 } 379 380 /** apply the stored representation to the reopttree */ 381 static 382 SCIP_RETCODE applyCompression( 383 SCIP* scip, /**< SCIP data structure */ 384 SCIP_COMPR* compr, /**< compression method */ 385 SCIP_COMPRDATA* comprdata, /**< compression data */ 386 SCIP_RESULT* result /**< result pointer */ 387 ) 388 { 389 SCIP_Bool success; 390 int r; 391 392 assert(scip != NULL); 393 assert(compr != NULL); 394 assert(comprdata != NULL); 395 396 *result = SCIP_DIDNOTRUN; 397 398 if( comprdata->nrepresentatives == 0 ) 399 return SCIP_OKAY; 400 401 /* set references to the root node */ 402 for( r = 0; r < comprdata->nrepresentatives; r++ ) 403 SCIPreoptnodeSetParentID(comprdata->representatives[r], 0); 404 405 success = FALSE; 406 SCIP_CALL( SCIPsetReoptCompression(scip, comprdata->representatives, comprdata->nrepresentatives, &success) ); 407 408 if( success ) 409 *result = SCIP_SUCCESS; 410 411 return SCIP_OKAY; 412 } 413 414 /* 415 * Callback methods of tree compression 416 */ 417 418 /** copy method for tree compression plugins (called when SCIP copies plugins) */ 419 static 420 SCIP_DECL_COMPRCOPY(comprCopyWeakcompr) 421 { /*lint --e{715}*/ 422 assert(scip != NULL); 423 assert(compr != NULL); 424 assert(strcmp(SCIPcomprGetName(compr), COMPR_NAME) == 0); 425 426 /* call inclusion method of primal heuristic */ 427 SCIP_CALL( SCIPincludeComprWeakcompr(scip) ); 428 429 return SCIP_OKAY; 430 } 431 432 /** destructor of tree compression to free user data (called when SCIP is exiting) */ 433 static 434 SCIP_DECL_COMPRFREE(comprFreeWeakcompr) 435 { 436 SCIP_COMPRDATA* comprdata; 437 438 assert(scip != NULL); 439 assert(compr != NULL); 440 441 comprdata = SCIPcomprGetData(compr); 442 assert(comprdata != NULL); 443 444 SCIPfreeBlockMemory(scip, &comprdata); 445 SCIPcomprSetData(compr, NULL); 446 447 return SCIP_OKAY; 448 } 449 450 /** deinitialization method of tree compression (called before transformed problem is freed) */ 451 static 452 SCIP_DECL_COMPREXIT(comprExitWeakcompr) 453 { 454 SCIP_COMPRDATA* comprdata; 455 456 assert(scip != NULL); 457 assert(compr != NULL); 458 459 comprdata = SCIPcomprGetData(compr); 460 assert(comprdata != NULL); 461 462 if( comprdata->initialized ) 463 { 464 int r; 465 466 for( r = 0; r < comprdata->nrepresentatives; r++ ) 467 { 468 SCIP_CALL( SCIPdeleteReoptnode(scip, &comprdata->representatives[r]) ); 469 } 470 471 if( comprdata->representativessize > 0 ) 472 { 473 SCIPfreeBlockMemoryArray(scip, &comprdata->representatives, comprdata->representativessize); 474 } 475 476 comprdata->representatives = NULL; 477 comprdata->representativessize = 0; 478 comprdata->nrepresentatives = 0; 479 comprdata->initialized = FALSE; 480 } 481 482 return SCIP_OKAY; 483 } 484 485 /** execution method of tree compression */ 486 static 487 SCIP_DECL_COMPREXEC(comprExecWeakcompr) 488 { 489 SCIP_COMPRDATA* comprdata; 490 491 assert(SCIPcomprIsInitialized(compr)); 492 493 comprdata = SCIPcomprGetData(compr); 494 assert(comprdata != NULL); 495 496 if( !comprdata->initialized ) 497 { 498 SCIPdebugMsg(scip, ">> initializing <%s>\n", COMPR_NAME); 499 500 comprdata->representativessize = DEFAULT_MEM_REPR; 501 comprdata->nrepresentatives = 0; 502 SCIP_CALL( SCIPallocClearMemoryArray(scip, &comprdata->representatives, comprdata->representativessize) ); 503 comprdata->initialized = TRUE; 504 } 505 506 /* try to find a representation */ 507 SCIP_CALL( constructCompression(scip, compr, comprdata, result) ); 508 509 assert(*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND || *result == SCIP_SUCCESS); 510 511 /* apply the representation, if some was found */ 512 if( *result == SCIP_SUCCESS ) 513 { 514 SCIP_CALL( applyCompression(scip, compr, comprdata, result) ); 515 assert(*result == SCIP_DIDNOTRUN || *result == SCIP_SUCCESS); 516 517 SCIPdebugMsg(scip, "->%s apply compression.\n", *result == SCIP_DIDNOTRUN ? " did not" : ""); 518 } 519 520 return SCIP_OKAY; 521 } 522 523 524 /* 525 * tree compression specific interface methods 526 */ 527 528 /** creates the weakcompr tree compression and includes it in SCIP */ 529 SCIP_RETCODE SCIPincludeComprWeakcompr( 530 SCIP* scip /**< SCIP data structure */ 531 ) 532 { 533 SCIP_COMPRDATA* comprdata; 534 SCIP_COMPR* compr; 535 536 /* create weakcompr tree compression data */ 537 SCIP_CALL( SCIPallocBlockMemory(scip, &comprdata) ); 538 assert(comprdata != NULL); 539 comprdata->initialized = FALSE; 540 541 /* include tree compression */ 542 SCIP_CALL( SCIPincludeComprBasic(scip, &compr,COMPR_NAME, COMPR_DESC, COMPR_PRIORITY, COMPR_MINNNODES, 543 comprExecWeakcompr, comprdata) ); 544 545 assert(compr != NULL); 546 547 /* set non fundamental callbacks via setter functions */ 548 SCIP_CALL( SCIPsetComprCopy(scip, compr, comprCopyWeakcompr) ); 549 SCIP_CALL( SCIPsetComprExit(scip, compr, comprExitWeakcompr) ); 550 SCIP_CALL( SCIPsetComprFree(scip, compr, comprFreeWeakcompr) ); 551 552 /* add weakcompr tree compression parameters */ 553 SCIP_CALL( SCIPaddBoolParam(scip, "compression/" COMPR_NAME "/convertconss", "convert constraints into nodes", &comprdata->convertconss, FALSE, FALSE, NULL, NULL) ); 554 555 return SCIP_OKAY; 556 } 557