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 pricestore.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for storing priced variables 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/clock.h" 34 #include "scip/lp.h" 35 #include "scip/pricestore.h" 36 #include "scip/pub_lp.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_var.h" 39 #include "scip/set.h" 40 #include "scip/struct_lp.h" 41 #include "scip/struct_pricestore.h" 42 #include "scip/struct_prob.h" 43 #include "scip/struct_set.h" 44 #include "scip/struct_var.h" 45 #include "scip/tree.h" 46 #include "scip/var.h" 47 48 49 50 /* 51 * dynamic memory arrays 52 */ 53 54 /** resizes vars and score arrays to be able to store at least num entries */ 55 static 56 SCIP_RETCODE pricestoreEnsureVarsMem( 57 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 58 SCIP_SET* set, /**< global SCIP settings */ 59 int num /**< minimal number of slots in array */ 60 ) 61 { 62 assert(pricestore != NULL); 63 assert(set != NULL); 64 65 if( num > pricestore->varssize ) 66 { 67 int newsize; 68 69 newsize = SCIPsetCalcMemGrowSize(set, num); 70 SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->vars, newsize) ); 71 SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->scores, newsize) ); 72 pricestore->varssize = newsize; 73 } 74 assert(num <= pricestore->varssize); 75 76 return SCIP_OKAY; 77 } 78 79 /** resizes bdviolvars arrays to be able to store at least num entries */ 80 static 81 SCIP_RETCODE pricestoreEnsureBdviolvarsMem( 82 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 83 SCIP_SET* set, /**< global SCIP settings */ 84 int num /**< minimal number of slots in array */ 85 ) 86 { 87 assert(pricestore != NULL); 88 assert(set != NULL); 89 90 if( num > pricestore->bdviolvarssize ) 91 { 92 int newsize; 93 94 newsize = SCIPsetCalcMemGrowSize(set, num); 95 SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->bdviolvars, newsize) ); 96 SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->bdviolvarslb, newsize) ); 97 SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->bdviolvarsub, newsize) ); 98 pricestore->bdviolvarssize = newsize; 99 } 100 assert(num <= pricestore->bdviolvarssize); 101 102 return SCIP_OKAY; 103 } 104 105 106 /** creates pricing storage */ 107 SCIP_RETCODE SCIPpricestoreCreate( 108 SCIP_PRICESTORE** pricestore /**< pointer to store pricing storage */ 109 ) 110 { 111 assert(pricestore != NULL); 112 113 SCIP_ALLOC( BMSallocMemory(pricestore) ); 114 115 SCIP_CALL( SCIPclockCreate(&(*pricestore)->probpricingtime, SCIP_CLOCKTYPE_DEFAULT) ); 116 (*pricestore)->vars = NULL; 117 (*pricestore)->scores = NULL; 118 (*pricestore)->bdviolvars = NULL; 119 (*pricestore)->bdviolvarslb = NULL; 120 (*pricestore)->bdviolvarsub = NULL; 121 (*pricestore)->varssize = 0; 122 (*pricestore)->nvars = 0; 123 (*pricestore)->bdviolvarssize = 0; 124 (*pricestore)->nbdviolvars = 0; 125 (*pricestore)->naddedbdviolvars = 0; 126 (*pricestore)->nprobpricings = 0; 127 (*pricestore)->nprobvarsfound = 0; 128 (*pricestore)->nvarsfound = 0; 129 (*pricestore)->nvarsapplied = 0; 130 (*pricestore)->initiallp = FALSE; 131 132 return SCIP_OKAY; 133 } 134 135 /** frees pricing storage */ 136 SCIP_RETCODE SCIPpricestoreFree( 137 SCIP_PRICESTORE** pricestore /**< pointer to store pricing storage */ 138 ) 139 { 140 assert(pricestore != NULL); 141 assert(*pricestore != NULL); 142 assert((*pricestore)->nvars == 0); 143 assert((*pricestore)->nbdviolvars == 0); 144 145 SCIPclockFree(&(*pricestore)->probpricingtime); 146 BMSfreeMemoryArrayNull(&(*pricestore)->vars); 147 BMSfreeMemoryArrayNull(&(*pricestore)->scores); 148 BMSfreeMemoryArrayNull(&(*pricestore)->bdviolvars); 149 BMSfreeMemoryArrayNull(&(*pricestore)->bdviolvarslb); 150 BMSfreeMemoryArrayNull(&(*pricestore)->bdviolvarsub); 151 BMSfreeMemory(pricestore); 152 153 return SCIP_OKAY; 154 } 155 156 /** informs pricing storage, that the setup of the initial LP starts now */ 157 void SCIPpricestoreStartInitialLP( 158 SCIP_PRICESTORE* pricestore /**< pricing storage */ 159 ) 160 { 161 assert(pricestore != NULL); 162 assert(!pricestore->initiallp); 163 assert(pricestore->nvars == 0); 164 165 pricestore->initiallp = TRUE; 166 } 167 168 /** informs pricing storage, that the setup of the initial LP is now finished */ 169 void SCIPpricestoreEndInitialLP( 170 SCIP_PRICESTORE* pricestore /**< pricing storage */ 171 ) 172 { 173 assert(pricestore != NULL); 174 assert(pricestore->initiallp); 175 assert(pricestore->nvars == 0); 176 177 pricestore->initiallp = FALSE; 178 } 179 180 /** adds variable to pricing storage and capture it */ 181 SCIP_RETCODE SCIPpricestoreAddVar( 182 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 183 BMS_BLKMEM* blkmem, /**< block memory */ 184 SCIP_SET* set, /**< global SCIP settings */ 185 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 186 SCIP_LP* lp, /**< LP data */ 187 SCIP_VAR* var, /**< priced variable */ 188 SCIP_Real score, /**< pricing score of variable (the larger, the better the variable) */ 189 SCIP_Bool root /**< are we at the root node? */ 190 ) 191 { 192 int maxpricevars; 193 int v; 194 195 assert(pricestore != NULL); 196 assert(set != NULL); 197 assert(var != NULL); 198 199 #ifndef NDEBUG 200 /* check if we add this variables to the same scip, where we created it */ 201 if( var->scip != set->scip ) 202 { 203 SCIPerrorMessage("try to add a variable of another scip instance\n"); 204 return SCIP_INVALIDDATA; 205 } 206 #endif 207 208 SCIPsetDebugMsg(set, "adding variable <%s> (lb=%g, ub=%g) to pricing storage (initiallp=%u)\n", 209 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), pricestore->initiallp); 210 211 if( pricestore->initiallp ) 212 maxpricevars = INT_MAX; 213 else 214 { 215 pricestore->nvarsfound++; 216 maxpricevars = SCIPsetGetPriceMaxvars(set, root); 217 } 218 assert(maxpricevars >= 1); 219 assert(pricestore->nvars <= maxpricevars); 220 221 /* check, if variable belongs to the best "maxpricevars" pricing variables */ 222 if( pricestore->nvars < maxpricevars || score > pricestore->scores[maxpricevars-1] ) 223 { 224 /* capture variable */ 225 SCIPvarCapture(var); 226 227 /* if the array consists of "maxpricevars" variables, release the worst variables */ 228 if( pricestore->nvars == maxpricevars ) 229 { 230 SCIP_CALL( SCIPvarRelease(&pricestore->vars[pricestore->nvars-1], blkmem, set, eventqueue, lp) ); 231 pricestore->nvars--; 232 } 233 assert(pricestore->nvars < maxpricevars); 234 235 /* get enough memory to store additional variable */ 236 SCIP_CALL( pricestoreEnsureVarsMem(pricestore, set, pricestore->nvars+1) ); 237 assert(pricestore->nvars <= pricestore->varssize); 238 239 /* insert the variable at the correct position in sorted arrays */ 240 for( v = pricestore->nvars; v > 0 && score > pricestore->scores[v-1]; --v ) 241 { 242 pricestore->vars[v] = pricestore->vars[v-1]; 243 pricestore->scores[v] = pricestore->scores[v-1]; 244 } 245 pricestore->vars[v] = var; 246 pricestore->scores[v] = score; 247 pricestore->nvars++; 248 } 249 250 return SCIP_OKAY; 251 } 252 253 /** adds variable where zero violates the bounds to pricing storage, capture it */ 254 SCIP_RETCODE SCIPpricestoreAddBdviolvar( 255 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 256 BMS_BLKMEM* blkmem, /**< block memory */ 257 SCIP_SET* set, /**< global SCIP settings */ 258 SCIP_STAT* stat, /**< problem statistics */ 259 SCIP_LP* lp, /**< LP data */ 260 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 261 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 262 SCIP_VAR* var /**< variable, where zero violates the bounds */ 263 ) 264 { 265 assert(pricestore != NULL); 266 assert(set != NULL); 267 assert(var != NULL); 268 assert(SCIPsetIsPositive(set, SCIPvarGetLbLocal(var)) || SCIPsetIsNegative(set, SCIPvarGetUbLocal(var))); 269 assert(pricestore->naddedbdviolvars <= pricestore->nbdviolvars); 270 271 SCIPsetDebugMsg(set, "zero violates bounds of <%s> (lb=%g, ub=%g)\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 272 273 if( !pricestore->initiallp ) 274 pricestore->nvarsfound++; 275 276 /* get enough memory to store additional variable */ 277 SCIP_CALL( pricestoreEnsureBdviolvarsMem(pricestore, set, pricestore->nbdviolvars+1) ); 278 assert(pricestore->nbdviolvars <= pricestore->bdviolvarssize); 279 280 /* capture variable */ 281 SCIPvarCapture(var); 282 283 /* insert variable in bdviolvars arrays */ 284 pricestore->bdviolvars[pricestore->nbdviolvars] = var; 285 pricestore->bdviolvarslb[pricestore->nbdviolvars] = SCIPvarGetLbLocal(var); 286 pricestore->bdviolvarsub[pricestore->nbdviolvars] = SCIPvarGetUbLocal(var); 287 pricestore->nbdviolvars++; 288 289 /* Temporarily set bounds, such that zero is feasible, because we don't want to destroy 290 * dual feasibility (by adding columns) and primal feasibility (by introducing violated bounds) 291 * at the same time. 292 * The correct bounds must be reset with a call to SCIPpricestoreResetBounds(). 293 * The inference information is unimportant for this temporary bound change. 294 */ 295 if( SCIPsetIsPositive(set, SCIPvarGetLbLocal(var)) ) 296 { 297 SCIP_CALL( SCIPvarChgLbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, 0.0) ); 298 } 299 else 300 { 301 SCIP_CALL( SCIPvarChgUbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, 0.0) ); 302 } 303 304 return SCIP_OKAY; 305 } 306 307 /** adds given problem variable to pricing storage, if zero is not best bound w.r.t. objective function */ 308 static 309 SCIP_RETCODE addBoundViolated( 310 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 311 BMS_BLKMEM* blkmem, /**< block memory buffers */ 312 SCIP_SET* set, /**< global SCIP settings */ 313 SCIP_STAT* stat, /**< dynamic problem statistics */ 314 SCIP_TREE* tree, /**< branch and bound tree */ 315 SCIP_LP* lp, /**< LP data */ 316 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 317 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 318 SCIP_VAR* var, /**< problem variable */ 319 SCIP_Bool* added /**< pointer to store whether variable was added to pricing storage */ 320 ) 321 { 322 assert(tree != NULL); 323 assert(added != NULL); 324 325 *added = FALSE; 326 327 /* add variable, if zero is not feasible within the bounds */ 328 if( SCIPsetIsPositive(set, SCIPvarGetLbLocal(var)) || SCIPsetIsNegative(set, SCIPvarGetUbLocal(var)) ) 329 { 330 SCIPsetDebugMsg(set, " -> zero violates bounds of <%s> [%g,%g]\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 331 SCIP_CALL( SCIPpricestoreAddBdviolvar(pricestore, blkmem, set, stat, lp, branchcand, eventqueue, var) ); 332 *added = TRUE; 333 } 334 else 335 { 336 SCIP_Real bestbound; 337 338 /* add variable, if zero is not best bound w.r.t. objective function */ 339 bestbound = SCIPvarGetBestBoundLocal(var); 340 if( !SCIPsetIsZero(set, bestbound) ) 341 { 342 SCIPsetDebugMsg(set, " -> best bound of <%s> [%g,%g] is not zero but %g\n", 343 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestbound); 344 SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, 345 -SCIPvarGetObj(var) * bestbound, (SCIPtreeGetCurrentDepth(tree) == 0)) ); 346 *added = TRUE; 347 } 348 } 349 350 return SCIP_OKAY; 351 } 352 353 /** adds problem variables with negative reduced costs to pricing storage */ 354 SCIP_RETCODE SCIPpricestoreAddProbVars( 355 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 356 BMS_BLKMEM* blkmem, /**< block memory buffers */ 357 SCIP_SET* set, /**< global SCIP settings */ 358 SCIP_STAT* stat, /**< dynamic problem statistics */ 359 SCIP_PROB* prob, /**< transformed problem after presolve */ 360 SCIP_TREE* tree, /**< branch and bound tree */ 361 SCIP_LP* lp, /**< LP data */ 362 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 363 SCIP_EVENTQUEUE* eventqueue /**< event queue */ 364 ) 365 { 366 SCIP_VAR* var; 367 SCIP_COL* col; 368 SCIP_Bool root; 369 SCIP_Bool added; 370 int v; 371 int abortpricevars; 372 int maxpricevars; 373 int nfoundvars; 374 375 assert(pricestore != NULL); 376 assert(set != NULL); 377 assert(stat != NULL); 378 assert(prob != NULL); 379 assert(lp != NULL); 380 assert(lp->solved); 381 assert(tree != NULL); 382 assert(SCIPtreeHasCurrentNodeLP(tree)); 383 assert(prob->nvars >= SCIPlpGetNCols(lp)); 384 385 /* if all problem variables of status COLUMN are already in the LP, nothing has to be done */ 386 if( prob->ncolvars == SCIPlpGetNCols(lp) ) 387 return SCIP_OKAY; 388 389 root = (SCIPtreeGetCurrentDepth(tree) == 0); 390 maxpricevars = SCIPsetGetPriceMaxvars(set, root); 391 assert(maxpricevars >= 1); 392 abortpricevars = (int)(set->price_abortfac * maxpricevars); 393 assert(abortpricevars >= maxpricevars); 394 395 /**@todo test pricing: is abortpricevars a good idea? -> like strong branching, lookahead, ... */ 396 397 pricestore->nprobpricings++; 398 399 /* start timing */ 400 SCIPclockStart(pricestore->probpricingtime, set); 401 402 /* price already existing problem variables */ 403 nfoundvars = 0; 404 for( v = 0; v < prob->nvars && nfoundvars < abortpricevars; ++v ) 405 { 406 var = prob->vars[v]; 407 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ) 408 { 409 col = SCIPvarGetCol(var); 410 assert(col != NULL); 411 assert(col->var == var); 412 assert(col->len >= 0); 413 assert(col->lppos >= -1); 414 assert(col->lpipos >= -1); 415 assert(SCIPcolIsInLP(col) == (col->lpipos >= 0)); 416 417 if( !SCIPcolIsInLP(col) ) 418 { 419 SCIPsetDebugMsg(set, "price column variable <%s> in bounds [%g,%g]\n", 420 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 421 422 /* add variable to pricing storage, if zero is not best bound w.r.t. objective function */ 423 SCIP_CALL( addBoundViolated(pricestore, blkmem, set, stat, tree, lp, branchcand, eventqueue, var, &added) ); 424 425 if( added ) 426 { 427 pricestore->nprobvarsfound++; 428 nfoundvars++; 429 } 430 else if( SCIPcolGetNNonz(col) > 0 ) 431 { 432 SCIP_Real feasibility; 433 434 /* a column not in LP that doesn't have zero in its bounds was added by bound checking above */ 435 assert(!SCIPsetIsPositive(set, SCIPvarGetLbLocal(col->var))); 436 assert(!SCIPsetIsNegative(set, SCIPvarGetUbLocal(col->var))); 437 438 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE ) 439 { 440 /* The LP was proven infeasible, so we have an infeasibility proof by the dual Farkas multipliers y. 441 * The valid inequality y^T A x >= y^T b is violated by all x, especially by the (for this 442 * inequality most feasible solution) x' defined by 443 * x'_i = ub_i, if y^T A_i > 0 444 * x'_i = lb_i, if y^T A_i <= 0. 445 * Pricing in this case means to add variables i with positive Farkas value, i.e. y^T A_i x'_i > 0 446 */ 447 feasibility = -SCIPcolGetFarkasValue(col, stat, lp); 448 SCIPsetDebugMsg(set, " <%s> Farkas feasibility: %e\n", SCIPvarGetName(col->var), feasibility); 449 } 450 else 451 { 452 /* The dual LP is feasible, and we have a feasible dual solution. Pricing in this case means to 453 * add variables with negative feasibility, that is 454 * - positive reduced costs for variables with negative lower bound 455 * - negative reduced costs for variables with positive upper bound 456 */ 457 feasibility = SCIPcolGetFeasibility(col, set, stat, lp); 458 SCIPsetDebugMsg(set, " <%s> reduced cost feasibility: %e\n", SCIPvarGetName(col->var), feasibility); 459 } 460 461 /* add variable if feasibility is negative, i.e., the reduced costs are negative */ 462 if( !SCIPsetIsPositive(set, feasibility) ) 463 { 464 SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, -feasibility / (col->len+1), root) ); 465 pricestore->nprobvarsfound++; 466 nfoundvars++; 467 } 468 } 469 } 470 } 471 } 472 473 /* stop timing */ 474 SCIPclockStop(pricestore->probpricingtime, set); 475 476 return SCIP_OKAY; 477 } 478 479 /** adds priced variables to the LP */ 480 SCIP_RETCODE SCIPpricestoreApplyVars( 481 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 482 BMS_BLKMEM* blkmem, /**< block memory buffers */ 483 SCIP_SET* set, /**< global SCIP settings */ 484 SCIP_STAT* stat, /**< dynamic problem statistics */ 485 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 486 SCIP_PROB* prob, /**< transformed problem after presolve */ 487 SCIP_TREE* tree, /**< branch and bound tree */ 488 SCIP_LP* lp /**< LP data */ 489 ) 490 { 491 SCIP_VAR* var; 492 SCIP_COL* col; 493 int v; 494 495 assert(pricestore != NULL); 496 assert(pricestore->naddedbdviolvars <= pricestore->nbdviolvars); 497 assert(set != NULL); 498 assert(prob != NULL); 499 assert(lp != NULL); 500 assert(tree != NULL); 501 assert(SCIPtreeIsFocusNodeLPConstructed(tree)); 502 503 SCIPsetDebugMsg(set, "adding %d variables (%d bound violated and %d priced vars) to %d LP columns\n", 504 SCIPpricestoreGetNVars(pricestore), pricestore->nbdviolvars - pricestore->naddedbdviolvars, 505 pricestore->nvars, SCIPlpGetNCols(lp)); 506 507 /* add the variables with violated bounds to LP */ 508 for( v = pricestore->naddedbdviolvars; v < pricestore->nbdviolvars; ++v ) 509 { 510 var = pricestore->bdviolvars[v]; 511 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN); 512 assert(SCIPvarGetProbindex(var) >= 0); 513 assert(var->nuses >= 2); /* at least used in pricing storage and in problem */ 514 515 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE ) 516 { 517 /* transform loose variable into column variable */ 518 SCIP_CALL( SCIPvarColumn(var, blkmem, set, stat, prob, lp) ); 519 } 520 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN); 521 522 col = SCIPvarGetCol(var); 523 assert(col != NULL); 524 assert(col->lppos == -1); 525 SCIPsetDebugMsg(set, "adding bound violated variable <%s> (lb=%g, ub=%g)\n", SCIPvarGetName(var), 526 pricestore->bdviolvarslb[v], pricestore->bdviolvarsub[v]); 527 SCIP_CALL( SCIPlpAddCol(lp, set, col, SCIPtreeGetCurrentDepth(tree)) ); 528 529 if( !pricestore->initiallp ) 530 pricestore->nvarsapplied++; 531 } 532 pricestore->naddedbdviolvars = pricestore->nbdviolvars; 533 534 /* add the selected pricing variables to LP */ 535 for( v = 0; v < pricestore->nvars; ++v ) 536 { 537 var = pricestore->vars[v]; 538 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN); 539 assert(SCIPvarGetProbindex(var) >= 0); 540 assert(var->nuses >= 2); /* at least used in pricing storage and in problem */ 541 542 /* transform variable into column variable, if needed */ 543 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE ) 544 { 545 SCIP_CALL( SCIPvarColumn(var, blkmem, set, stat, prob, lp) ); 546 } 547 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN); 548 549 col = SCIPvarGetCol(var); 550 assert(col != NULL); 551 assert(col->lppos == -1); 552 SCIPsetDebugMsg(set, "adding priced variable <%s> (score=%g)\n", SCIPvarGetName(var), pricestore->scores[v]); 553 SCIP_CALL( SCIPlpAddCol(lp, set, col, SCIPtreeGetCurrentDepth(tree)) ); 554 555 /* release the variable */ 556 SCIP_CALL( SCIPvarRelease(&pricestore->vars[v], blkmem, set, eventqueue, lp) ); 557 558 if( !pricestore->initiallp ) 559 pricestore->nvarsapplied++; 560 } 561 562 /* clear the pricing storage */ 563 pricestore->nvars = 0; 564 565 return SCIP_OKAY; 566 } 567 568 /** reset variables' bounds violated by zero to its original value */ 569 SCIP_RETCODE SCIPpricestoreResetBounds( 570 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 571 BMS_BLKMEM* blkmem, /**< block memory */ 572 SCIP_SET* set, /**< global SCIP settings */ 573 SCIP_STAT* stat, /**< problem statistics */ 574 SCIP_LP* lp, /**< LP data */ 575 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 576 SCIP_EVENTQUEUE* eventqueue /**< event queue */ 577 ) 578 { 579 SCIP_VAR* var; 580 int v; 581 582 assert(pricestore != NULL); 583 assert(set != NULL); 584 assert(lp != NULL); 585 assert(pricestore->nvars == 0); 586 assert(pricestore->naddedbdviolvars == pricestore->nbdviolvars); 587 588 /* reset variables' bounds, release them, and clear the boundviolation storage; 589 * the inference information is unimportant in these removals of temporary bound changes 590 */ 591 for( v = 0; v < pricestore->nbdviolvars; ++v ) 592 { 593 var = pricestore->bdviolvars[v]; 594 assert(var != NULL); 595 596 SCIPsetDebugMsg(set, "resetting bounds of <%s> from [%g,%g] to [%g,%g]\n", var->name, 597 SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), pricestore->bdviolvarslb[v], pricestore->bdviolvarsub[v]); 598 SCIP_CALL( SCIPvarChgLbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, pricestore->bdviolvarslb[v]) ); 599 SCIP_CALL( SCIPvarChgUbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, pricestore->bdviolvarsub[v]) ); 600 SCIP_CALL( SCIPvarRelease(&pricestore->bdviolvars[v], blkmem, set, eventqueue, lp) ); 601 } 602 pricestore->naddedbdviolvars = 0; 603 pricestore->nbdviolvars = 0; 604 605 return SCIP_OKAY; 606 } 607 608 /** gets number of variables in pricing storage */ 609 int SCIPpricestoreGetNVars( 610 SCIP_PRICESTORE* pricestore /**< pricing storage */ 611 ) 612 { 613 assert(pricestore != NULL); 614 assert(pricestore->nbdviolvars >= pricestore->naddedbdviolvars); 615 616 return pricestore->nvars + pricestore->nbdviolvars - pricestore->naddedbdviolvars; 617 } 618 619 /** gets number of variables in pricing storage whose bounds must be reset */ 620 int SCIPpricestoreGetNBoundResets( 621 SCIP_PRICESTORE* pricestore /**< pricing storage */ 622 ) 623 { 624 assert(pricestore != NULL); 625 assert(pricestore->nbdviolvars >= pricestore->naddedbdviolvars); 626 627 return pricestore->nbdviolvars - pricestore->naddedbdviolvars; 628 } 629 630 /** gets time needed to price existing problem variables */ 631 SCIP_Real SCIPpricestoreGetProbPricingTime( 632 SCIP_PRICESTORE* pricestore /**< pricing storage */ 633 ) 634 { 635 assert(pricestore != NULL); 636 637 return SCIPclockGetTime(pricestore->probpricingtime); 638 } 639 640 /** gets total number of calls to problem variable pricing */ 641 int SCIPpricestoreGetNProbPricings( 642 SCIP_PRICESTORE* pricestore /**< pricing storage */ 643 ) 644 { 645 assert(pricestore != NULL); 646 647 return pricestore->nprobpricings; 648 } 649 650 /** gets total number of times, a problem variable was priced in */ 651 int SCIPpricestoreGetNProbvarsFound( 652 SCIP_PRICESTORE* pricestore /**< pricing storage */ 653 ) 654 { 655 assert(pricestore != NULL); 656 657 return pricestore->nprobvarsfound; 658 } 659 660 /** get total number of variables found so far in pricing */ 661 int SCIPpricestoreGetNVarsFound( 662 SCIP_PRICESTORE* pricestore /**< pricing storage */ 663 ) 664 { 665 assert(pricestore != NULL); 666 667 return pricestore->nvarsfound; 668 } 669 670 /** get total number of variables priced into the LP so far */ 671 int SCIPpricestoreGetNVarsApplied( 672 SCIP_PRICESTORE* pricestore /**< pricing storage */ 673 ) 674 { 675 assert(pricestore != NULL); 676 677 return pricestore->nvarsapplied; 678 } 679 680