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 nlhdlr_perspective.c 26 * @ingroup DEFPLUGINS_NLHDLR 27 * @brief perspective nonlinear handler 28 * @author Ksenia Bestuzheva 29 */ 30 31 #include <string.h> 32 33 #include "scip/nlhdlr_perspective.h" 34 #include "scip/cons_nonlinear.h" 35 #include "scip/scip_sol.h" 36 #include "scip/pub_misc_rowprep.h" 37 #include "scip/nlhdlr.h" 38 39 /* fundamental nonlinear handler properties */ 40 #define NLHDLR_NAME "perspective" 41 #define NLHDLR_DESC "perspective handler for expressions" 42 #define NLHDLR_DETECTPRIORITY -20 /**< detect last so that to make use of what other handlers detected */ 43 #define NLHDLR_ENFOPRIORITY 125 /**< enforce first because perspective cuts are always stronger */ 44 45 #define DEFAULT_MAXPROPROUNDS 1 /**< maximal number of propagation rounds in probing */ 46 #define DEFAULT_MINDOMREDUCTION 0.1 /**< minimal relative reduction in a variable's domain for applying probing */ 47 #define DEFAULT_MINVIOLPROBING 1e-05 /**< minimal violation w.r.t. auxiliary variables for applying probing */ 48 #define DEFAULT_PROBINGONLYINSEPA TRUE /**< whether to do probing only in separation loop */ 49 #define DEFAULT_PROBINGFREQ 1 /**< probing frequency (-1 - no probing, 0 - root node only) */ 50 #define DEFAULT_CONVEXONLY FALSE /**< whether perspective cuts are added only for convex expressions */ 51 #define DEFAULT_TIGHTENBOUNDS TRUE /**< whether variable semicontinuity is used to tighten variable bounds */ 52 #define DEFAULT_ADJREFPOINT TRUE /**< whether to adjust the reference point if indicator is not 1 */ 53 54 /* 55 * Data structures 56 */ 57 58 /** data structure to store information of a semicontinuous variable 59 * 60 * For a variable x (not stored in the struct), this stores the data of nbnds implications 61 * bvars[i] = 0 -> x = vals[i] 62 * bvars[i] = 1 -> lbs[i] <= x <= ubs[i] 63 * where bvars[i] are binary variables. 64 */ 65 struct SCVarData 66 { 67 SCIP_Real* vals0; /**< values of the variable when the corresponding bvars[i] = 0 */ 68 SCIP_Real* lbs1; /**< global lower bounds of the variable when the corresponding bvars[i] = 1 */ 69 SCIP_Real* ubs1; /**< global upper bounds of the variable when the corresponding bvars[i] = 1 */ 70 SCIP_VAR** bvars; /**< the binary variables on which the variable domain depends */ 71 int nbnds; /**< number of suitable on/off bounds the var has */ 72 int bndssize; /**< size of the arrays */ 73 }; 74 typedef struct SCVarData SCVARDATA; 75 76 /** nonlinear handler expression data 77 * 78 * For an expression expr (not stored in the struct), this stores the data of nindicators implications 79 * indicators[i] = 0 -> expr = exprvals[0] 80 * where indicators[i] is an indicator (binary) variable, corresponding to some bvars entry in SCVarData. 81 * 82 * Also stores the variables the expression depends on. 83 */ 84 struct SCIP_NlhdlrExprData 85 { 86 SCIP_Real* exprvals0; /**< 'off' values of the expression for each indicator variable */ 87 SCIP_VAR** vars; /**< expression variables (both original and auxiliary) */ 88 int nvars; /**< total number of variables in the expression */ 89 int varssize; /**< size of the vars array */ 90 SCIP_VAR** indicators; /**< all indicator variables for the expression */ 91 int nindicators; /**< number of indicator variables */ 92 }; 93 94 /** nonlinear handler data */ 95 struct SCIP_NlhdlrData 96 { 97 SCIP_HASHMAP* scvars; /**< maps semicontinuous variables to their on/off bounds (SCVarData) */ 98 99 /* parameters */ 100 int maxproprounds; /**< maximal number of propagation rounds in probing */ 101 SCIP_Real mindomreduction; /**< minimal relative reduction in a variable's domain for applying probing */ 102 SCIP_Real minviolprobing; /**< minimal violation w.r.t. auxiliary variables for applying probing */ 103 SCIP_Bool probingonlyinsepa; /**< whether to do probing only in separation loop */ 104 int probingfreq; /**< if and when to do probing */ 105 SCIP_Bool convexonly; /**< whether perspective cuts are added only for convex expressions */ 106 SCIP_Bool tightenbounds; /**< whether variable semicontinuity is used to tighten variable bounds */ 107 SCIP_Bool adjrefpoint; /**< whether to adjust the reference point if indicator is not 1 */ 108 }; 109 110 /* 111 * Local methods 112 */ 113 114 /* 115 * Helper methods for working with nlhdlrExprData 116 */ 117 118 /** frees nlhdlrexprdata structure */ 119 static 120 SCIP_RETCODE freeNlhdlrExprData( 121 SCIP* scip, /**< SCIP data structure */ 122 SCIP_NLHDLREXPRDATA* nlhdlrexprdata /**< nlhdlr expression data */ 123 ) 124 { 125 int v; 126 127 if( nlhdlrexprdata->nindicators != 0 ) 128 { 129 assert(nlhdlrexprdata->indicators != NULL); 130 for( v = nlhdlrexprdata->nindicators - 1; v >= 0; --v ) 131 { 132 SCIP_CALL( SCIPreleaseVar(scip, &(nlhdlrexprdata->indicators[v])) ); 133 } 134 SCIPfreeBlockMemoryArray(scip, &(nlhdlrexprdata->indicators), nlhdlrexprdata->nindicators); 135 SCIPfreeBlockMemoryArrayNull(scip, &(nlhdlrexprdata->exprvals0), nlhdlrexprdata->nindicators); 136 } 137 138 for( v = nlhdlrexprdata->nvars - 1; v >= 0; --v ) 139 { 140 SCIP_CALL( SCIPreleaseVar(scip, &(nlhdlrexprdata->vars[v])) ); 141 } 142 SCIPfreeBlockMemoryArrayNull(scip, &nlhdlrexprdata->vars, nlhdlrexprdata->varssize); 143 144 return SCIP_OKAY; 145 } 146 147 /* remove an indicator from nlhdlr expression data */ 148 static 149 SCIP_RETCODE removeIndicator( 150 SCIP* scip, /**< SCIP data structure */ 151 SCIP_NLHDLREXPRDATA* nlexprdata, /**< nlhdlr expression data */ 152 int pos /**< position of the indicator */ 153 ) 154 { 155 int i; 156 157 assert(pos >= 0 && pos < nlexprdata->nindicators); 158 159 SCIP_CALL( SCIPreleaseVar(scip, &nlexprdata->indicators[pos]) ); 160 for( i = pos; i < nlexprdata->nindicators - 1; ++i ) 161 { 162 nlexprdata->indicators[i] = nlexprdata->indicators[i+1]; 163 } 164 165 --nlexprdata->nindicators; 166 167 return SCIP_OKAY; 168 } 169 170 /** adds an auxiliary variable to the vars array in nlhdlrexprdata */ 171 static 172 SCIP_RETCODE addAuxVar( 173 SCIP* scip, /**< SCIP data structure */ 174 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */ 175 SCIP_HASHMAP* auxvarmap, /**< hashmap linking auxvars to positions in nlhdlrexprdata->vars */ 176 SCIP_VAR* auxvar /**< variable to be added */ 177 ) 178 { 179 int pos; 180 int newsize; 181 182 assert(nlhdlrexprdata != NULL); 183 assert(auxvar != NULL); 184 185 pos = SCIPhashmapGetImageInt(auxvarmap, (void*) auxvar); 186 187 if( pos != INT_MAX ) 188 return SCIP_OKAY; 189 190 /* ensure size */ 191 if( nlhdlrexprdata->nvars + 1 > nlhdlrexprdata->varssize ) 192 { 193 newsize = SCIPcalcMemGrowSize(scip, nlhdlrexprdata->nvars + 1); 194 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nlhdlrexprdata->vars, nlhdlrexprdata->varssize, newsize) ); 195 nlhdlrexprdata->varssize = newsize; 196 } 197 assert(nlhdlrexprdata->nvars + 1 <= nlhdlrexprdata->varssize); 198 199 nlhdlrexprdata->vars[nlhdlrexprdata->nvars] = auxvar; 200 SCIP_CALL( SCIPcaptureVar(scip, auxvar) ); 201 SCIP_CALL( SCIPhashmapSetImageInt(auxvarmap, (void*) auxvar, nlhdlrexprdata->nvars) ); 202 ++(nlhdlrexprdata->nvars); 203 204 return SCIP_OKAY; 205 } 206 207 /* 208 * Semicontinuous variable methods 209 */ 210 211 /** adds an indicator to the data of a semicontinuous variable */ 212 static 213 SCIP_RETCODE addSCVarIndicator( 214 SCIP* scip, /**< SCIP data structure */ 215 SCVARDATA* scvdata, /**< semicontinuous variable data */ 216 SCIP_VAR* indicator, /**< indicator to be added */ 217 SCIP_Real val0, /**< value of the variable when indicator == 0 */ 218 SCIP_Real lb1, /**< lower bound of the variable when indicator == 1 */ 219 SCIP_Real ub1 /**< upper bound of the variable when indicator == 1 */ 220 ) 221 { 222 int newsize; 223 int i; 224 SCIP_Bool found; 225 int pos; 226 227 assert(scvdata != NULL); 228 assert(indicator != NULL); 229 230 /* find the position where to insert */ 231 if( scvdata->bvars == NULL ) 232 { 233 assert(scvdata->nbnds == 0 && scvdata->bndssize == 0); 234 found = FALSE; 235 pos = 0; 236 } 237 else 238 { 239 found = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, &pos); 240 } 241 242 if( found ) 243 return SCIP_OKAY; 244 245 /* ensure sizes */ 246 if( scvdata->nbnds + 1 > scvdata->bndssize ) 247 { 248 newsize = SCIPcalcMemGrowSize(scip, scvdata->nbnds + 1); 249 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->bvars, scvdata->bndssize, newsize) ); 250 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->vals0, scvdata->bndssize, newsize) ); 251 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->lbs1, scvdata->bndssize, newsize) ); 252 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->ubs1, scvdata->bndssize, newsize) ); 253 scvdata->bndssize = newsize; 254 } 255 assert(scvdata->nbnds + 1 <= scvdata->bndssize); 256 assert(scvdata->bvars != NULL); 257 258 /* move entries if needed */ 259 for( i = scvdata->nbnds; i > pos; --i ) 260 { 261 /* coverity[forward_null] */ 262 scvdata->bvars[i] = scvdata->bvars[i-1]; 263 scvdata->vals0[i] = scvdata->vals0[i-1]; 264 scvdata->lbs1[i] = scvdata->lbs1[i-1]; 265 scvdata->ubs1[i] = scvdata->ubs1[i-1]; 266 } 267 268 scvdata->bvars[pos] = indicator; 269 scvdata->vals0[pos] = val0; 270 scvdata->lbs1[pos] = lb1; 271 scvdata->ubs1[pos] = ub1; 272 ++scvdata->nbnds; 273 274 return SCIP_OKAY; 275 } 276 277 /** find scvardata of var and position of indicator in it 278 * 279 * If indicator is not there, returns NULL. 280 */ 281 static 282 SCVARDATA* getSCVarDataInd( 283 SCIP_HASHMAP* scvars, /**< hashmap linking variables to scvardata */ 284 SCIP_VAR* var, /**< variable */ 285 SCIP_VAR* indicator, /**< indicator variable */ 286 int* pos /**< pointer to store the position of indicator */ 287 ) 288 { 289 SCIP_Bool exists; 290 SCVARDATA* scvdata; 291 292 assert(var != NULL); 293 assert(scvars != NULL); 294 assert(indicator != NULL); 295 296 scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var); 297 if( scvdata != NULL ) 298 { 299 /* look for the indicator variable */ 300 exists = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, pos); 301 if( !exists ) 302 return NULL; 303 304 return scvdata; 305 } 306 307 return NULL; 308 } 309 310 /** checks if a variable is semicontinuous and, if needed, updates the scvars hashmap 311 * 312 * A variable \f$x\f$ is semicontinuous if its bounds depend on at least one binary variable called the indicator, 313 * and indicator = 0 ⇒ \f$x = x^0\f$ for some real constant \f$x^0\f$. 314 */ 315 static 316 SCIP_RETCODE varIsSemicontinuous( 317 SCIP* scip, /**< SCIP data structure */ 318 SCIP_VAR* var, /**< the variable to check */ 319 SCIP_HASHMAP* scvars, /**< semicontinuous variable information */ 320 SCIP_Bool* result /**< buffer to store whether var is semicontinuous */ 321 ) 322 { 323 SCIP_Real lb0; 324 SCIP_Real ub0; 325 SCIP_Real lb1; 326 SCIP_Real ub1; 327 SCIP_Real glb; 328 SCIP_Real gub; 329 SCIP_Bool exists; 330 int c; 331 int pos; 332 SCIP_VAR** vlbvars; 333 SCIP_VAR** vubvars; 334 SCIP_Real* vlbcoefs; 335 SCIP_Real* vubcoefs; 336 SCIP_Real* vlbconstants; 337 SCIP_Real* vubconstants; 338 int nvlbs; 339 int nvubs; 340 SCVARDATA* scvdata; 341 SCIP_VAR* bvar; 342 343 assert(scip != NULL); 344 assert(var != NULL); 345 assert(scvars != NULL); 346 assert(result != NULL); 347 348 scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var); 349 if( scvdata != NULL ) 350 { 351 *result = TRUE; 352 return SCIP_OKAY; 353 } 354 355 vlbvars = SCIPvarGetVlbVars(var); 356 vubvars = SCIPvarGetVubVars(var); 357 vlbcoefs = SCIPvarGetVlbCoefs(var); 358 vubcoefs = SCIPvarGetVubCoefs(var); 359 vlbconstants = SCIPvarGetVlbConstants(var); 360 vubconstants = SCIPvarGetVubConstants(var); 361 nvlbs = SCIPvarGetNVlbs(var); 362 nvubs = SCIPvarGetNVubs(var); 363 glb = SCIPvarGetLbGlobal(var); 364 gub = SCIPvarGetUbGlobal(var); 365 366 *result = FALSE; 367 368 /* Scan through lower bounds; for each binary vlbvar save the corresponding lb0 and lb1. 369 * Then check if there is an upper bound with this vlbvar and save ub0 and ub1. 370 * If the found bounds imply that the var value is fixed to some val0 when vlbvar = 0, 371 * save vlbvar and val0 to scvdata. 372 */ 373 for( c = 0; c < nvlbs; ++c ) 374 { 375 if( SCIPvarGetType(vlbvars[c]) != SCIP_VARTYPE_BINARY ) 376 continue; 377 378 SCIPdebugMsg(scip, "var <%s>[%f, %f] lower bound: %f <%s> %+f", SCIPvarGetName(var), glb, gub, vlbcoefs[c], SCIPvarGetName(vlbvars[c]), vlbconstants[c]); 379 380 bvar = vlbvars[c]; 381 382 lb0 = MAX(vlbconstants[c], glb); 383 lb1 = MAX(vlbconstants[c] + vlbcoefs[c], glb); 384 385 /* look for bvar in vubvars */ 386 if( vubvars != NULL ) 387 exists = SCIPsortedvecFindPtr((void**)vubvars, SCIPvarComp, bvar, nvubs, &pos); 388 else 389 exists = FALSE; 390 if( exists ) 391 { /*lint --e{644}*/ 392 SCIPdebugMsgPrint(scip, ", upper bound: %f <%s> %+f", vubcoefs[pos], SCIPvarGetName(vubvars[pos]), vubconstants[pos]); /*lint !e613*/ 393 394 /* save the upper bounds */ 395 ub0 = MIN(vubconstants[pos], gub); 396 ub1 = MIN(vubconstants[pos] + vubcoefs[pos], gub); 397 } 398 else 399 { 400 /* if there is no upper bound with vubvar = bvar, use global var bounds */ 401 ub0 = gub; 402 ub1 = gub; 403 } 404 405 /* the 'off' domain of a semicontinuous var should reduce to a single point and be different from the 'on' domain */ 406 SCIPdebugMsgPrint(scip, " -> <%s> in [%f, %f] (off), [%f, %f] (on)\n", SCIPvarGetName(var), lb0, ub0, lb1, ub1); 407 if( SCIPisEQ(scip, lb0, ub0) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) ) 408 { 409 if( scvdata == NULL ) 410 { 411 SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) ); 412 } 413 414 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) ); 415 } 416 } 417 418 /* look for vubvars that have not been processed yet */ 419 assert(vubvars != NULL || nvubs == 0); 420 for( c = 0; c < nvubs; ++c ) 421 { 422 /* coverity[forward_null] */ 423 if( SCIPvarGetType(vubvars[c]) != SCIP_VARTYPE_BINARY ) /*lint !e613*/ 424 continue; 425 426 bvar = vubvars[c]; /*lint !e613*/ 427 428 /* skip vars that are in vlbvars */ 429 if( vlbvars != NULL && SCIPsortedvecFindPtr((void**)vlbvars, SCIPvarComp, bvar, nvlbs, &pos) ) 430 continue; 431 432 SCIPdebugMsg(scip, "var <%s>[%f, %f] upper bound: %f <%s> %+f", 433 SCIPvarGetName(var), glb, gub, vubcoefs[c], SCIPvarGetName(vubvars[c]), vubconstants[c]); /*lint !e613*/ 434 435 lb0 = glb; 436 lb1 = glb; 437 ub0 = MIN(vubconstants[c], gub); 438 ub1 = MIN(vubconstants[c] + vubcoefs[c], gub); 439 440 /* the 'off' domain of a semicontinuous var should reduce to a single point and be different from the 'on' domain */ 441 SCIPdebugMsgPrint(scip, " -> <%s> in [%f, %f] (off), [%f, %f] (on)\n", SCIPvarGetName(var), lb0, ub0, lb1, ub1); 442 if( SCIPisEQ(scip, lb0, ub0) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) ) 443 { 444 if( scvdata == NULL ) 445 { 446 SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) ); 447 } 448 449 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) ); 450 } 451 } 452 453 if( scvdata != NULL ) 454 { 455 #ifdef SCIP_DEBUG 456 SCIPdebugMsg(scip, "var <%s> has global bounds [%f, %f] and the following on/off bounds:\n", SCIPvarGetName(var), glb, gub); 457 for( c = 0; c < scvdata->nbnds; ++c ) 458 { 459 SCIPdebugMsg(scip, " c = %d, bvar <%s>: val0 = %f\n", c, SCIPvarGetName(scvdata->bvars[c]), scvdata->vals0[c]); 460 } 461 #endif 462 SCIP_CALL( SCIPhashmapInsert(scvars, var, scvdata) ); 463 *result = TRUE; 464 } 465 466 return SCIP_OKAY; 467 } 468 469 /* 470 * Semicontinuous expression methods 471 */ 472 473 /* checks if an expression is semicontinuous 474 * 475 * An expression is semicontinuous if all of its nonlinear variables are semicontinuous 476 * and share at least one common indicator variable 477 */ 478 static 479 SCIP_RETCODE exprIsSemicontinuous( 480 SCIP* scip, /**< SCIP data structure */ 481 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */ 482 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */ 483 SCIP_EXPR* expr, /**< expression */ 484 SCIP_Bool* res /**< buffer to store whether the expression is semicontinuous */ 485 ) 486 { 487 int v; 488 SCIP_Bool var_is_sc; 489 SCVARDATA* scvdata; 490 SCIP_VAR* var; 491 int nindicators; 492 int nbnds0; 493 int c; 494 SCIP_VAR** indicators; 495 SCIP_Bool* nonlinear; 496 497 *res = FALSE; 498 499 /* constant expression is not semicontinuous; variable expressions are of no interest here */ 500 if( nlhdlrexprdata->nvars == 0 ) 501 return SCIP_OKAY; 502 503 indicators = NULL; 504 nindicators = 0; 505 nbnds0 = 0; 506 507 if( SCIPisExprSum(scip, expr) ) 508 { 509 SCIP_EXPRITER* it; 510 SCIP_EXPR* child; 511 SCIP_EXPR* curexpr; 512 int pos; 513 SCIP_Bool issc; 514 515 /* sums are treated separately because if there are variables that are non-semicontinuous but 516 * appear only linearly, we still want to apply perspective to expr 517 */ 518 519 SCIP_CALL( SCIPallocClearBufferArray(scip, &nonlinear, nlhdlrexprdata->nvars) ); 520 SCIP_CALL( SCIPcreateExpriter(scip, &it) ); 521 522 for( c = 0; c < SCIPexprGetNChildren(expr); ++c ) 523 { 524 child = SCIPexprGetChildren(expr)[c]; 525 526 if( SCIPisExprVar(scip, child) ) 527 { 528 var = SCIPgetVarExprVar(child); 529 530 /* save information on semicontinuity of child */ 531 SCIP_CALL( varIsSemicontinuous(scip, var, nlhdlrdata->scvars, &var_is_sc) ); 532 533 /* since child is a variable, go on regardless of the value of var_is_sc */ 534 continue; 535 } 536 537 issc = TRUE; 538 539 SCIP_CALL( SCIPexpriterInit(it, child, SCIP_EXPRITER_DFS, FALSE) ); 540 curexpr = SCIPexpriterGetCurrent(it); 541 542 /* all nonlinear terms of a sum should be semicontinuous in original variables */ 543 while( !SCIPexpriterIsEnd(it) ) 544 { 545 assert(curexpr != NULL); 546 547 if( SCIPisExprVar(scip, curexpr) ) 548 { 549 var = SCIPgetVarExprVar(curexpr); 550 551 if( !SCIPvarIsRelaxationOnly(var) ) 552 { 553 SCIP_CALL( varIsSemicontinuous(scip, var, nlhdlrdata->scvars, &var_is_sc) ); 554 555 /* mark the variable as nonlinear */ 556 (void) SCIPsortedvecFindPtr((void**) nlhdlrexprdata->vars, SCIPvarComp, (void*) var, nlhdlrexprdata->nvars, 557 &pos); 558 assert(0 <= pos && pos < nlhdlrexprdata->nvars); 559 nonlinear[pos] = TRUE; 560 561 if( !var_is_sc ) 562 { 563 /* non-semicontinuous child which is (due to a previous check) not a var -> 564 * expr is non-semicontinuous 565 */ 566 issc = FALSE; 567 break; 568 } 569 } 570 } 571 curexpr = SCIPexpriterGetNext(it); 572 } 573 574 if( !issc ) 575 { 576 SCIPfreeExpriter(&it); 577 goto TERMINATE; 578 } 579 } 580 SCIPfreeExpriter(&it); 581 } 582 else 583 { 584 /* non-sum expression */ 585 nonlinear = NULL; 586 587 /* all variables of a non-sum on/off expression should be semicontinuous */ 588 for( v = 0; v < nlhdlrexprdata->nvars; ++v ) 589 { 590 SCIP_CALL( varIsSemicontinuous(scip, nlhdlrexprdata->vars[v], nlhdlrdata->scvars, &var_is_sc) ); 591 if( !var_is_sc ) 592 return SCIP_OKAY; 593 } 594 } 595 596 /* look for common binary variables for all variables of the expression */ 597 598 SCIPdebugMsg(scip, "Array intersection for var <%s>\n", SCIPvarGetName(nlhdlrexprdata->vars[0])); 599 for( v = 0; v < nlhdlrexprdata->nvars; ++v ) 600 { 601 SCIPdebugMsg(scip, "%s; \n", SCIPvarGetName(nlhdlrexprdata->vars[v])); 602 603 if( nonlinear != NULL && !nonlinear[v] ) 604 continue; 605 606 scvdata = (SCVARDATA*)SCIPhashmapGetImage(nlhdlrdata->scvars, (void*) nlhdlrexprdata->vars[v]); 607 608 /* we should have exited earlier if there is a nonlinear non-semicontinuous variable */ 609 assert(scvdata != NULL); 610 611 if( indicators == NULL ) 612 { 613 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &indicators, scvdata->bvars, scvdata->nbnds) ); 614 nbnds0 = scvdata->nbnds; 615 nindicators = nbnds0; 616 } 617 else 618 { 619 SCIPcomputeArraysIntersectionPtr((void**)indicators, nindicators, (void**)scvdata->bvars, scvdata->nbnds, 620 SCIPvarComp, (void**)indicators, &nindicators); 621 } 622 623 /* if we have found out that the intersection is empty, expr is not semicontinuous */ 624 if( indicators != NULL && nindicators == 0 ) 625 { 626 SCIPfreeBlockMemoryArray(scip, &indicators, nbnds0); 627 goto TERMINATE; 628 } 629 } 630 631 /* this can happen if all children are linear vars and none are semicontinuous */ 632 if( indicators == NULL ) 633 { 634 goto TERMINATE; 635 } 636 assert(nindicators > 0 && nindicators <= nbnds0); 637 638 if( nindicators < nbnds0 ) 639 { 640 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &indicators, nbnds0, nindicators) ); 641 } 642 643 for( v = 0; v < nindicators; ++v ) 644 { 645 SCIP_CALL( SCIPcaptureVar(scip, indicators[v]) ); 646 } 647 nlhdlrexprdata->indicators = indicators; 648 nlhdlrexprdata->nindicators = nindicators; 649 *res = TRUE; 650 651 TERMINATE: 652 SCIPfreeBufferArrayNull(scip, &nonlinear); 653 654 return SCIP_OKAY; 655 } 656 657 /** computes the 'off' value of the expression and the 'off' values of 658 * semicontinuous auxiliary variables for each indicator variable 659 */ 660 static 661 SCIP_RETCODE computeOffValues( 662 SCIP* scip, /**< SCIP data structure */ 663 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */ 664 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */ 665 SCIP_EXPR* expr /**< expression */ 666 ) 667 { 668 SCIP_EXPRITER* it; 669 SCIP_SOL* sol; 670 int i; 671 int v; 672 int norigvars; 673 SCIP_Real* origvals0; 674 SCIP_VAR** origvars; 675 SCVARDATA* scvdata; 676 SCIP_VAR* auxvar; 677 SCIP_EXPR* curexpr; 678 SCIP_HASHMAP* auxvarmap; 679 SCIP_Bool hasnonsc; 680 int pos; 681 682 assert(expr != NULL); 683 684 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(nlhdlrexprdata->exprvals0), nlhdlrexprdata->nindicators) ); 685 SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) ); 686 SCIP_CALL( SCIPallocBufferArray(scip, &origvals0, nlhdlrexprdata->nvars) ); 687 SCIP_CALL( SCIPhashmapCreate(&auxvarmap, SCIPblkmem(scip), 10) ); 688 SCIP_CALL( SCIPcreateExpriter(scip, &it) ); 689 SCIP_CALL( SCIPduplicateBufferArray(scip, &origvars, nlhdlrexprdata->vars, nlhdlrexprdata->nvars) ); 690 norigvars = nlhdlrexprdata->nvars; 691 692 for( i = nlhdlrexprdata->nindicators - 1; i >= 0; --i ) 693 { 694 hasnonsc = FALSE; 695 696 /* set sol to the off value of all expr vars for this indicator */ 697 for( v = 0; v < norigvars; ++v ) 698 { 699 /* set vals0[v] = 0 if var is non-sc with respect to indicators[i] - then it will not 700 * contribute to exprvals0[i] since any non-sc var must be linear 701 */ 702 scvdata = getSCVarDataInd(nlhdlrdata->scvars, origvars[v], nlhdlrexprdata->indicators[i], &pos); 703 if( scvdata == NULL ) 704 { 705 origvals0[v] = 0.0; 706 hasnonsc = TRUE; 707 } 708 else 709 { 710 origvals0[v] = scvdata->vals0[pos]; 711 } 712 } 713 SCIP_CALL( SCIPsetSolVals(scip, sol, norigvars, origvars, origvals0) ); 714 SCIP_CALL( SCIPevalExpr(scip, expr, sol, 0L) ); 715 716 if( SCIPexprGetEvalValue(expr) == SCIP_INVALID ) /*lint !e777*/ 717 { 718 SCIPdebugMsg(scip, "expression evaluation failed for %p, removing indicator %s\n", 719 (void*)expr, SCIPvarGetName(nlhdlrexprdata->indicators[i])); 720 /* TODO should we fix the indicator variable to 1? */ 721 /* since the loop is backwards, this only modifies the already processed part of nlhdlrexprdata->indicators */ 722 SCIP_CALL( removeIndicator(scip, nlhdlrexprdata, i) ); 723 continue; 724 } 725 726 nlhdlrexprdata->exprvals0[i] = SCIPexprGetEvalValue(expr); 727 728 /* iterate through the expression and create scvdata for aux vars */ 729 SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) ); 730 curexpr = SCIPexpriterGetCurrent(it); 731 732 while( !SCIPexpriterIsEnd(it) ) 733 { 734 auxvar = SCIPgetExprAuxVarNonlinear(curexpr); 735 736 if( auxvar != NULL ) 737 { 738 SCIP_Bool issc = TRUE; 739 #ifndef NDEBUG 740 SCIP_EXPR** childvarexprs; 741 int nchildvarexprs; 742 SCIP_VAR* var; 743 #endif 744 745 if( hasnonsc ) 746 { 747 /* expr is a sum with non-semicontinuous linear terms. Therefore, curexpr might be 748 * non-semicontinuous. In that case the auxvar is also non-semicontinuous, so 749 * we will skip on/off bounds computation. 750 */ 751 if( SCIPisExprVar(scip, curexpr) ) 752 { 753 /* easy case: curexpr is a variable, can check semicontinuity immediately */ 754 scvdata = getSCVarDataInd(nlhdlrdata->scvars, SCIPgetVarExprVar(curexpr), 755 nlhdlrexprdata->indicators[i], &pos); 756 issc = scvdata != NULL; 757 } 758 else if( SCIPisExprSum(scip, curexpr) && curexpr == expr ) 759 { 760 /* if expr itself is a sum, this is an exception since a sum with nonlinear terms is 761 * allowed to have both semicontinuous and non-semicontinuous variables; we skip it here 762 * and then analyse it term by term 763 */ 764 issc = FALSE; 765 } 766 767 #ifndef NDEBUG 768 if( !SCIPisExprVar(scip, curexpr) && (!SCIPisExprSum(scip, curexpr) || curexpr != expr) ) 769 { 770 /* curexpr is a non-variable expression and does not fit the sum special case, 771 * so it belongs to the non-linear part of expr. 772 * Since the non-linear part of expr must be semicontinuous with respect to 773 * nlhdlrexprdata->indicators[i], curexpr must be semicontinuous 774 */ 775 776 SCIP_CALL( SCIPallocBufferArray(scip, &childvarexprs, norigvars) ); 777 SCIP_CALL( SCIPgetExprVarExprs(scip, curexpr, childvarexprs, &nchildvarexprs) ); 778 779 /* all nonlinear variables of a sum on/off term should be semicontinuous */ 780 for( v = 0; v < nchildvarexprs; ++v ) 781 { 782 var = SCIPgetVarExprVar(childvarexprs[v]); 783 scvdata = getSCVarDataInd(nlhdlrdata->scvars, var, nlhdlrexprdata->indicators[i], &pos); 784 assert(scvdata != NULL); 785 786 SCIP_CALL( SCIPreleaseExpr(scip, &childvarexprs[v]) ); 787 } 788 789 SCIPfreeBufferArray(scip, &childvarexprs); 790 } 791 #endif 792 } 793 794 if( issc ) 795 { 796 /* we know that all vars are semicontinuous with respect to exprdata->indicators; it remains to: 797 * - get or create the scvardata structure for auxvar 798 * - if had to create scvardata, add it to scvars hashmap 799 * - add the indicator and the off value (= curexpr's off value) to scvardata 800 */ 801 scvdata = (SCVARDATA*) SCIPhashmapGetImage(nlhdlrdata->scvars, (void*)auxvar); 802 if( scvdata == NULL ) 803 { 804 SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) ); 805 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->bvars, nlhdlrexprdata->nindicators) ); 806 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->vals0, nlhdlrexprdata->nindicators) ); 807 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->lbs1, nlhdlrexprdata->nindicators) ); 808 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->ubs1, nlhdlrexprdata->nindicators) ); 809 scvdata->bndssize = nlhdlrexprdata->nindicators; 810 SCIP_CALL( SCIPhashmapInsert(nlhdlrdata->scvars, auxvar, scvdata) ); 811 } 812 813 SCIP_CALL( addSCVarIndicator(scip, scvdata, nlhdlrexprdata->indicators[i], 814 SCIPexprGetEvalValue(curexpr), SCIPvarGetLbGlobal(auxvar), SCIPvarGetUbGlobal(auxvar)) ); 815 } 816 817 SCIP_CALL( addAuxVar(scip, nlhdlrexprdata, auxvarmap, auxvar) ); 818 } 819 820 curexpr = SCIPexpriterGetNext(it); 821 } 822 } 823 824 SCIPfreeExpriter(&it); 825 SCIPhashmapFree(&auxvarmap); 826 SCIPfreeBufferArray(scip, &origvars); 827 SCIPfreeBufferArray(scip, &origvals0); 828 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 829 830 return SCIP_OKAY; 831 } 832 833 /* 834 * Probing and bound tightening methods 835 */ 836 837 /** go into probing and set some variable bounds */ 838 static 839 SCIP_RETCODE startProbing( 840 SCIP* scip, /**< SCIP data structure */ 841 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */ 842 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */ 843 SCIP_VAR* indicator, /**< indicator variable */ 844 SCIP_VAR** probingvars, /**< array of vars whose bounds we will change in probing */ 845 SCIP_INTERVAL* probingdoms, /**< array of intervals to which bounds of probingvars will be changed in probing */ 846 int nprobingvars, /**< number of probing vars */ 847 SCIP_SOL* sol, /**< solution to be separated */ 848 SCIP_SOL** solcopy, /**< buffer for a copy of sol before going into probing; if *solcopy == sol, then copy is created */ 849 SCIP_Bool* cutoff_probing /**< pointer to store whether indicator == 1 is infeasible */ 850 ) 851 { 852 int v; 853 SCIP_Real newlb; 854 SCIP_Real newub; 855 SCIP_Bool propagate; 856 857 propagate = SCIPgetDepth(scip) == 0; 858 859 /* if a copy of sol has not been created yet, then create one now and copy the relevant var values from sol, 860 * because sol can change after SCIPstartProbing, e.g., when linked to the LP solution 861 */ 862 if( *solcopy == sol ) 863 { 864 SCIP_CALL( SCIPcreateSol(scip, solcopy, NULL) ); 865 for( v = 0; v < nlhdlrexprdata->nvars; ++v ) 866 { 867 SCIP_CALL( SCIPsetSolVal(scip, *solcopy, nlhdlrexprdata->vars[v], SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[v])) ); 868 } 869 for( v = 0; v < nlhdlrexprdata->nindicators; ++v ) 870 { 871 SCIP_CALL( SCIPsetSolVal(scip, *solcopy, nlhdlrexprdata->indicators[v], SCIPgetSolVal(scip, sol, nlhdlrexprdata->indicators[v])) ); 872 } 873 } 874 875 /* go into probing */ 876 SCIP_CALL( SCIPstartProbing(scip) ); 877 878 /* create a probing node */ 879 SCIP_CALL( SCIPnewProbingNode(scip) ); 880 881 /* set indicator to 1 */ 882 SCIP_CALL( SCIPchgVarLbProbing(scip, indicator, 1.0) ); 883 884 /* apply stored bounds */ 885 for( v = 0; v < nprobingvars; ++v ) 886 { 887 newlb = SCIPintervalGetInf(probingdoms[v]); 888 newub = SCIPintervalGetSup(probingdoms[v]); 889 890 if( SCIPisGT(scip, newlb, SCIPvarGetLbLocal(probingvars[v])) || (newlb >= 0.0 && SCIPvarGetLbLocal(probingvars[v]) < 0.0) ) 891 { 892 SCIP_CALL( SCIPchgVarLbProbing(scip, probingvars[v], newlb) ); 893 } 894 if( SCIPisLT(scip, newub, SCIPvarGetUbLocal(probingvars[v])) || (newub <= 0.0 && SCIPvarGetUbLocal(probingvars[v]) > 0.0) ) 895 { 896 SCIP_CALL( SCIPchgVarUbProbing(scip, probingvars[v], newub) ); 897 } 898 } 899 900 if( propagate ) 901 { 902 SCIP_Longint ndomreds; 903 904 SCIP_CALL( SCIPpropagateProbing(scip, nlhdlrdata->maxproprounds, cutoff_probing, &ndomreds) ); 905 } 906 907 return SCIP_OKAY; 908 } 909 910 /** analyse on/off bounds on a variable 911 * 912 * analyses for 913 * 1. tightening bounds in probing for indicator = 1, 914 * 2. fixing indicator / detecting cutoff if one or both states are infeasible, 915 * 3. tightening local bounds if indicator is fixed. 916 * 917 * `probinglb` and `probingub` are only set if `doprobing` is TRUE. 918 * They are either set to bounds that should be used in probing or to `SCIP_INVALID` if bounds on 919 * `var` shouldn't be changed in probing. 920 */ 921 static 922 SCIP_RETCODE analyseVarOnoffBounds( 923 SCIP* scip, /**< SCIP data structure */ 924 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */ 925 SCIP_VAR* var, /**< variable */ 926 SCIP_VAR* indicator, /**< indicator variable */ 927 SCIP_Bool indvalue, /**< indicator value for which the bounds are applied */ 928 SCIP_Bool* infeas, /**< pointer to store whether infeasibility has been detected */ 929 SCIP_Real* probinglb, /**< pointer to store the lower bound to be applied in probing */ 930 SCIP_Real* probingub, /**< pointer to store the upper bound to be applied in probing */ 931 SCIP_Bool doprobing, /**< whether we currently consider to go into probing */ 932 SCIP_Bool* reduceddom /**< pointer to store whether any variables were fixed */ 933 ) 934 { 935 SCVARDATA* scvdata; 936 int pos; 937 SCIP_Real sclb; 938 SCIP_Real scub; 939 SCIP_Real loclb; 940 SCIP_Real locub; 941 SCIP_Bool bndchgsuccess; 942 943 assert(var != NULL); 944 assert(indicator != NULL); 945 assert(infeas != NULL); 946 assert(reduceddom != NULL); 947 948 /* shouldn't be called if indicator is fixed to !indvalue */ 949 assert((indvalue && SCIPvarGetUbLocal(indicator) > 0.5) || (!indvalue && SCIPvarGetLbLocal(indicator) < 0.5)); 950 951 *infeas = FALSE; 952 *reduceddom = FALSE; 953 scvdata = getSCVarDataInd(nlhdlrdata->scvars, var, indicator, &pos); 954 if( doprobing ) 955 { 956 assert(probinglb != NULL); 957 assert(probingub != NULL); 958 959 *probinglb = SCIP_INVALID; 960 *probingub = SCIP_INVALID; 961 } 962 963 /* nothing to do for non-semicontinuous variables */ 964 if( scvdata == NULL ) 965 { 966 return SCIP_OKAY; 967 } 968 969 sclb = indvalue ? scvdata->lbs1[pos] : scvdata->vals0[pos]; 970 scub = indvalue ? scvdata->ubs1[pos] : scvdata->vals0[pos]; 971 loclb = SCIPvarGetLbLocal(var); 972 locub = SCIPvarGetUbLocal(var); 973 974 /* nothing to do for fixed variables */ 975 if( SCIPisEQ(scip, loclb, locub) ) 976 return SCIP_OKAY; 977 978 /* use a non-redundant lower bound */ 979 if( SCIPisGT(scip, sclb, SCIPvarGetLbLocal(var)) || (sclb >= 0.0 && loclb < 0.0) ) 980 { 981 /* first check for infeasibility */ 982 if( SCIPisFeasGT(scip, sclb, SCIPvarGetUbLocal(var)) ) 983 { 984 SCIP_CALL( SCIPfixVar(scip, indicator, indvalue ? 0.0 : 1.0, infeas, &bndchgsuccess) ); 985 *reduceddom += bndchgsuccess; 986 if( *infeas ) 987 { 988 return SCIP_OKAY; 989 } 990 } 991 else if( nlhdlrdata->tightenbounds && 992 (SCIPvarGetUbLocal(indicator) <= 0.5 || SCIPvarGetLbLocal(indicator) >= 0.5) ) 993 { 994 /* indicator is fixed; due to a previous check, here it can only be fixed to indvalue; 995 * therefore, sclb is valid for the current node 996 */ 997 998 if( indvalue == 0 ) 999 { 1000 assert(sclb == scub); /*lint !e777*/ 1001 SCIP_CALL( SCIPfixVar(scip, var, sclb, infeas, &bndchgsuccess) ); 1002 } 1003 else 1004 { 1005 SCIP_CALL( SCIPtightenVarLb(scip, var, sclb, FALSE, infeas, &bndchgsuccess) ); 1006 } 1007 *reduceddom += bndchgsuccess; 1008 if( *infeas ) 1009 { 1010 return SCIP_OKAY; 1011 } 1012 } 1013 } 1014 1015 /* use a non-redundant upper bound */ 1016 if( SCIPisLT(scip, scub, SCIPvarGetUbLocal(var)) || (scub <= 0.0 && locub > 0.0) ) 1017 { 1018 /* first check for infeasibility */ 1019 if( SCIPisFeasLT(scip, scub, SCIPvarGetLbLocal(var)) ) 1020 { 1021 SCIP_CALL( SCIPfixVar(scip, indicator, indvalue ? 0.0 : 1.0, infeas, &bndchgsuccess) ); 1022 *reduceddom += bndchgsuccess; 1023 if( *infeas ) 1024 { 1025 return SCIP_OKAY; 1026 } 1027 } 1028 else if( nlhdlrdata->tightenbounds && 1029 (SCIPvarGetUbLocal(indicator) <= 0.5 || SCIPvarGetLbLocal(indicator) >= 0.5) ) 1030 { 1031 /* indicator is fixed; due to a previous check, here it can only be fixed to indvalue; 1032 * therefore, scub is valid for the current node 1033 */ 1034 1035 if( indvalue == 0 ) 1036 { 1037 assert(sclb == scub); /*lint !e777*/ 1038 SCIP_CALL( SCIPfixVar(scip, var, scub, infeas, &bndchgsuccess) ); 1039 } 1040 else 1041 { 1042 SCIP_CALL( SCIPtightenVarUb(scip, var, scub, FALSE, infeas, &bndchgsuccess) ); 1043 } 1044 *reduceddom += bndchgsuccess; 1045 if( *infeas ) 1046 { 1047 return SCIP_OKAY; 1048 } 1049 } 1050 } 1051 1052 /* If a bound change has been found and indvalue == TRUE, try to use the new bounds. 1053 * This is only done for indvalue == TRUE since this is where enfo asks other nlhdlrs to estimate, 1054 * and at indicator == FALSE we already only have a single point 1055 */ 1056 if( doprobing && indvalue && (((scub - sclb) / (locub - loclb)) <= 1.0 - nlhdlrdata->mindomreduction || 1057 (sclb >= 0.0 && loclb < 0.0) || (scub <= 0.0 && locub > 0.0)) ) 1058 { 1059 *probinglb = sclb; 1060 *probingub = scub; 1061 } 1062 1063 SCIPdebugMsg(scip, "%s in [%g, %g] instead of [%g, %g] (vals0 = %g)\n", SCIPvarGetName(var), sclb, scub, 1064 SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), scvdata->vals0[pos]); 1065 1066 return SCIP_OKAY; 1067 } 1068 1069 /** looks for bound tightenings to be applied either in the current node or in probing 1070 * 1071 * Loops through both possible values of indicator and calls analyseVarOnoffBounds(). 1072 * Might update the `*doprobing` flag by setting it to `FALSE` if: 1073 * - indicator is fixed or 1074 * - analyseVarOnoffBounds() hasn't found a sufficient improvement at indicator==1. 1075 * 1076 * If `*doprobing==TRUE`, stores bounds suggested by analyseVarOnoffBounds() in order to apply them in probing together 1077 * with the fixing `indicator=1`. 1078 */ 1079 static 1080 SCIP_RETCODE analyseOnoffBounds( 1081 SCIP* scip, /**< SCIP data structure */ 1082 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */ 1083 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */ 1084 SCIP_VAR* indicator, /**< indicator variable */ 1085 SCIP_VAR*** probingvars, /**< array to store variables whose bounds will be changed in probing */ 1086 SCIP_INTERVAL** probingdoms, /**< array to store bounds to be applied in probing */ 1087 int* nprobingvars, /**< pointer to store number of vars whose bounds will be changed in probing */ 1088 SCIP_Bool* doprobing, /**< pointer to the flag telling whether we want to do probing */ 1089 SCIP_RESULT* result /**< pointer to store the result */ 1090 ) 1091 { 1092 int v; 1093 SCIP_VAR* var; 1094 SCIP_Bool infeas; 1095 int b; 1096 SCIP_Real probinglb = SCIP_INVALID; 1097 SCIP_Real probingub = SCIP_INVALID; 1098 SCIP_Bool changed; 1099 SCIP_Bool reduceddom; 1100 1101 assert(indicator != NULL); 1102 assert(nprobingvars != NULL); 1103 assert(doprobing != NULL); 1104 assert(result != NULL); 1105 1106 changed = FALSE; 1107 1108 /* no probing if indicator already fixed */ 1109 if( SCIPvarGetUbLocal(indicator) <= 0.5 || SCIPvarGetLbLocal(indicator) >= 0.5 ) 1110 { 1111 *doprobing = FALSE; 1112 } 1113 1114 /* consider each possible value of indicator */ 1115 for( b = 0; b < 2; ++b ) 1116 { 1117 for( v = 0; v < nlhdlrexprdata->nvars; ++v ) 1118 { 1119 /* nothing left to do if indicator is already fixed to !indvalue 1120 * (checked in the inner loop since analyseVarOnoff bounds might fix the indicator) 1121 */ 1122 if( (b == 1 && SCIPvarGetUbLocal(indicator) <= 0.5) || (b == 0 && SCIPvarGetLbLocal(indicator) >= 0.5) ) 1123 { 1124 *doprobing = FALSE; 1125 break; 1126 } 1127 1128 var = nlhdlrexprdata->vars[v]; 1129 1130 SCIP_CALL( analyseVarOnoffBounds(scip, nlhdlrdata, var, indicator, b == 1, &infeas, &probinglb, 1131 &probingub, *doprobing, &reduceddom) ); 1132 1133 if( infeas ) 1134 { 1135 *result = SCIP_CUTOFF; 1136 *doprobing = FALSE; 1137 return SCIP_OKAY; 1138 } 1139 else if( reduceddom ) 1140 { 1141 *result = SCIP_REDUCEDDOM; 1142 } 1143 1144 if( !(*doprobing) ) 1145 continue; 1146 1147 /* if bounds to be applied in probing have been found, store them */ 1148 if( probinglb != SCIP_INVALID ) /*lint !e777*/ 1149 { 1150 assert(probingub != SCIP_INVALID); /*lint !e777*/ 1151 1152 SCIP_CALL( SCIPreallocBufferArray(scip, probingvars, *nprobingvars + 1) ); 1153 SCIP_CALL( SCIPreallocBufferArray(scip, probingdoms, *nprobingvars + 1) ); 1154 (*probingvars)[*nprobingvars] = var; 1155 (*probingdoms)[*nprobingvars].inf = probinglb; 1156 (*probingdoms)[*nprobingvars].sup = probingub; 1157 ++*nprobingvars; 1158 1159 changed = TRUE; 1160 } 1161 } 1162 } 1163 1164 if( !changed ) 1165 { 1166 *doprobing = FALSE; 1167 } 1168 1169 return SCIP_OKAY; 1170 } 1171 1172 /** saves local bounds on all expression variables, including auxiliary variables, obtained from propagating 1173 * indicator == 1 to the corresponding SCVARDATA (should only be used in the root node) 1174 */ 1175 static 1176 SCIP_RETCODE tightenOnBounds( 1177 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */ 1178 SCIP_HASHMAP* scvars, /**< hashmap with semicontinuous variables */ 1179 SCIP_VAR* indicator /**< indicator variable */ 1180 ) 1181 { 1182 int v; 1183 SCIP_VAR* var; 1184 SCVARDATA* scvdata; 1185 int pos; 1186 SCIP_Real lb; 1187 SCIP_Real ub; 1188 1189 for( v = 0; v < nlhdlrexprdata->nvars; ++v ) 1190 { 1191 var = nlhdlrexprdata->vars[v]; 1192 lb = SCIPvarGetLbLocal(var); 1193 ub = SCIPvarGetUbLocal(var); 1194 scvdata = getSCVarDataInd(scvars, var, indicator, &pos); 1195 1196 if( scvdata != NULL ) 1197 { 1198 scvdata->lbs1[pos] = MAX(scvdata->lbs1[pos], lb); 1199 scvdata->ubs1[pos] = MIN(scvdata->ubs1[pos], ub); 1200 } 1201 } 1202 1203 return SCIP_OKAY; 1204 } 1205 1206 /* 1207 * Callback methods of nonlinear handler 1208 */ 1209 1210 /** nonlinear handler copy callback */ 1211 static 1212 SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrPerspective) 1213 { /*lint --e{715}*/ 1214 assert(targetscip != NULL); 1215 assert(sourcenlhdlr != NULL); 1216 assert(strcmp(SCIPnlhdlrGetName(sourcenlhdlr), NLHDLR_NAME) == 0); 1217 1218 SCIP_CALL( SCIPincludeNlhdlrPerspective(targetscip) ); 1219 1220 return SCIP_OKAY; 1221 } 1222 1223 1224 /** callback to free data of handler */ 1225 static 1226 SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrFreehdlrdataPerspective) 1227 { /*lint --e{715}*/ 1228 SCIPfreeBlockMemory(scip, nlhdlrdata); 1229 1230 return SCIP_OKAY; 1231 } 1232 1233 1234 /** callback to free expression specific data */ 1235 static 1236 SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataPerspective) 1237 { /*lint --e{715}*/ 1238 SCIP_CALL( freeNlhdlrExprData(scip, *nlhdlrexprdata) ); 1239 SCIPfreeBlockMemory(scip, nlhdlrexprdata); 1240 1241 return SCIP_OKAY; 1242 } 1243 1244 /** callback to be called in initialization */ 1245 #if 0 1246 static 1247 SCIP_DECL_NLHDLRINIT(nlhdlrInitPerspective) 1248 { /*lint --e{715}*/ 1249 return SCIP_OKAY; 1250 } 1251 #endif 1252 1253 /** callback to be called in deinitialization */ 1254 static 1255 SCIP_DECL_NLHDLREXIT(nlhdlrExitPerspective) 1256 { /*lint --e{715}*/ 1257 SCIP_HASHMAPENTRY* entry; 1258 SCVARDATA* data; 1259 int c; 1260 SCIP_NLHDLRDATA* nlhdlrdata; 1261 1262 nlhdlrdata = SCIPnlhdlrGetData(nlhdlr); 1263 assert(nlhdlrdata != NULL); 1264 1265 if( nlhdlrdata->scvars != NULL ) 1266 { 1267 for( c = 0; c < SCIPhashmapGetNEntries(nlhdlrdata->scvars); ++c ) 1268 { 1269 entry = SCIPhashmapGetEntry(nlhdlrdata->scvars, c); 1270 if( entry != NULL ) 1271 { 1272 data = (SCVARDATA*) SCIPhashmapEntryGetImage(entry); 1273 SCIPfreeBlockMemoryArray(scip, &data->ubs1, data->bndssize); 1274 SCIPfreeBlockMemoryArray(scip, &data->lbs1, data->bndssize); 1275 SCIPfreeBlockMemoryArray(scip, &data->vals0, data->bndssize); 1276 SCIPfreeBlockMemoryArray(scip, &data->bvars, data->bndssize); 1277 SCIPfreeBlockMemory(scip, &data); 1278 } 1279 } 1280 SCIPhashmapFree(&nlhdlrdata->scvars); 1281 assert(nlhdlrdata->scvars == NULL); 1282 } 1283 1284 return SCIP_OKAY; 1285 } 1286 1287 /** callback to detect structure in expression tree 1288 * 1289 * We are looking for expressions g(x), where x is a vector of semicontinuous variables that all share at least one 1290 * indicator variable. 1291 */ 1292 static 1293 SCIP_DECL_NLHDLRDETECT(nlhdlrDetectPerspective) 1294 { /*lint --e{715}*/ 1295 SCIP_NLHDLRDATA* nlhdlrdata; 1296 SCIP_EXPR** varexprs; 1297 SCIP_Bool success = FALSE; 1298 int i; 1299 SCIP_Bool hassepabelow = FALSE; 1300 SCIP_Bool hassepaabove = FALSE; 1301 SCIP_Bool hasnondefault = FALSE; 1302 1303 nlhdlrdata = SCIPnlhdlrGetData(nlhdlr); 1304 1305 assert(scip != NULL); 1306 assert(nlhdlr != NULL); 1307 assert(expr != NULL); 1308 assert(participating != NULL); 1309 assert(enforcing != NULL); 1310 assert(nlhdlrexprdata != NULL); 1311 assert(nlhdlrdata != NULL); 1312 1313 /* do not run if we will have no auxvar to add a cut for */ 1314 if( SCIPgetExprNAuxvarUsesNonlinear(expr) == 0 ) 1315 return SCIP_OKAY; 1316 1317 if( SCIPgetNBinVars(scip) == 0 ) 1318 { 1319 SCIPdebugMsg(scip, "problem has no binary variables, not running perspective detection\n"); 1320 return SCIP_OKAY; 1321 } 1322 1323 for( i = 0; i < SCIPgetExprNEnfosNonlinear(expr); ++i ) 1324 { 1325 SCIP_NLHDLR* nlhdlr2; 1326 SCIP_NLHDLR_METHOD nlhdlr2participates; 1327 SCIP_Bool sepabelowusesactivity; 1328 SCIP_Bool sepaaboveusesactivity; 1329 SCIPgetExprEnfoDataNonlinear(expr, i, &nlhdlr2, NULL, &nlhdlr2participates, &sepabelowusesactivity, &sepaaboveusesactivity, NULL); 1330 1331 if( (nlhdlr2participates & SCIP_NLHDLR_METHOD_SEPABOTH) == 0 ) 1332 continue; 1333 1334 if( !SCIPnlhdlrHasEstimate(nlhdlr2) ) 1335 continue; 1336 1337 if( strcmp(SCIPnlhdlrGetName(nlhdlr2), "default") != 0 ) 1338 hasnondefault = TRUE; 1339 1340 /* If we are supposed to run only on convex expressions, than check whether there is a nlhdlr 1341 * that participates in separation without using activity for it. Otherwise, check for 1342 * participation regardless of activity usage. 1343 */ 1344 if( (nlhdlr2participates & SCIP_NLHDLR_METHOD_SEPABELOW) && (!nlhdlrdata->convexonly || !sepabelowusesactivity) ) 1345 hassepabelow = TRUE; 1346 1347 if( (nlhdlr2participates & SCIP_NLHDLR_METHOD_SEPAABOVE) && (!nlhdlrdata->convexonly || !sepaaboveusesactivity) ) 1348 hassepaabove = TRUE; 1349 } 1350 1351 /* If a sum expression is handled only by default nlhdlr, then all the children will have auxiliary vars. 1352 * Since the sum will then be linear in auxiliary variables, perspective can't improve anything for it 1353 */ 1354 if( SCIPisExprSum(scip, expr) && !hasnondefault ) 1355 { 1356 SCIPdebugMsg(scip, "sum expr only has default exprhdlr, not running perspective detection\n"); 1357 return SCIP_OKAY; 1358 } 1359 1360 /* If no other nlhdlr separates, neither does perspective (if convexonly, only separation 1361 * without using activity counts) 1362 */ 1363 if( !hassepabelow && !hassepaabove ) 1364 { 1365 SCIPdebugMsg(scip, "no nlhdlr separates without using activity, not running perspective detection\n"); 1366 return SCIP_OKAY; 1367 } 1368 1369 #ifdef SCIP_DEBUG 1370 SCIPdebugMsg(scip, "Called perspective detect, expr = %p: ", (void*)expr); 1371 SCIPprintExpr(scip, expr, NULL); 1372 SCIPdebugMsgPrint(scip, "\n"); 1373 #endif 1374 1375 /* allocate memory */ 1376 SCIP_CALL( SCIPallocClearBlockMemory(scip, nlhdlrexprdata) ); 1377 if( nlhdlrdata->scvars == NULL ) 1378 { 1379 SCIP_CALL( SCIPhashmapCreate(&(nlhdlrdata->scvars), SCIPblkmem(scip), SCIPgetNVars(scip)) ); 1380 } 1381 1382 /* save varexprs to nlhdlrexprdata */ 1383 SCIP_CALL( SCIPgetExprNVars(scip, expr, &(*nlhdlrexprdata)->nvars) ); 1384 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->vars, (*nlhdlrexprdata)->nvars) ); 1385 SCIP_CALL( SCIPallocBufferArray(scip, &varexprs, (*nlhdlrexprdata)->nvars) ); 1386 (*nlhdlrexprdata)->varssize = (*nlhdlrexprdata)->nvars; 1387 SCIP_CALL( SCIPgetExprVarExprs(scip, expr, varexprs, &(*nlhdlrexprdata)->nvars) ); 1388 for( i = 0; i < (*nlhdlrexprdata)->nvars; ++i ) 1389 { 1390 (*nlhdlrexprdata)->vars[i] = SCIPgetVarExprVar(varexprs[i]); 1391 SCIP_CALL( SCIPreleaseExpr(scip, &varexprs[i]) ); 1392 SCIP_CALL( SCIPcaptureVar(scip, (*nlhdlrexprdata)->vars[i]) ); 1393 } 1394 SCIPsortPtr((void**) (*nlhdlrexprdata)->vars, SCIPvarComp, (*nlhdlrexprdata)->nvars); 1395 SCIPfreeBufferArray(scip, &varexprs); 1396 1397 /* check if expr is semicontinuous and save indicator variables */ 1398 SCIP_CALL( exprIsSemicontinuous(scip, nlhdlrdata, *nlhdlrexprdata, expr, &success) ); 1399 1400 if( success ) 1401 { 1402 assert(*nlhdlrexprdata != NULL); 1403 assert((*nlhdlrexprdata)->nindicators > 0); 1404 1405 if( hassepaabove ) 1406 *participating |= SCIP_NLHDLR_METHOD_SEPAABOVE; 1407 if( hassepabelow ) 1408 *participating |= SCIP_NLHDLR_METHOD_SEPABELOW; 1409 1410 #ifdef SCIP_DEBUG 1411 SCIPinfoMessage(scip, NULL, "detected an on/off expr: "); 1412 SCIPprintExpr(scip, expr, NULL); 1413 SCIPinfoMessage(scip, NULL, "\n"); 1414 #endif 1415 } 1416 else 1417 { 1418 assert(*nlhdlrexprdata != NULL); 1419 SCIP_CALL( nlhdlrFreeExprDataPerspective(scip, nlhdlr, expr, nlhdlrexprdata) ); 1420 } 1421 1422 return SCIP_OKAY; 1423 } 1424 1425 1426 /** auxiliary evaluation callback of nonlinear handler */ 1427 static 1428 SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalauxPerspective) 1429 { /*lint --e{715}*/ 1430 int e; 1431 SCIP_Real maxdiff; 1432 SCIP_Real auxvarvalue; 1433 SCIP_Real enfoauxval; 1434 1435 assert(scip != NULL); 1436 assert(expr != NULL); 1437 assert(auxvalue != NULL); 1438 1439 auxvarvalue = SCIPgetSolVal(scip, sol, SCIPgetExprAuxVarNonlinear(expr)); 1440 maxdiff = 0.0; 1441 *auxvalue = auxvarvalue; 1442 1443 /* use the auxvalue from one of the other nlhdlrs that estimates for this expr: take the one that is farthest 1444 * from the current value of auxvar 1445 */ 1446 for( e = 0; e < SCIPgetExprNEnfosNonlinear(expr); ++e ) 1447 { 1448 SCIP_NLHDLR* nlhdlr2; 1449 SCIP_NLHDLREXPRDATA* nlhdlr2exprdata; 1450 SCIP_NLHDLR_METHOD nlhdlr2participation; 1451 1452 SCIPgetExprEnfoDataNonlinear(expr, e, &nlhdlr2, &nlhdlr2exprdata, &nlhdlr2participation, NULL, NULL, NULL); 1453 1454 /* skip nlhdlr that do not participate or do not provide estimate */ 1455 if( (nlhdlr2participation & SCIP_NLHDLR_METHOD_SEPABOTH) == 0 || !SCIPnlhdlrHasEstimate(nlhdlr2) ) 1456 continue; 1457 1458 SCIP_CALL( SCIPnlhdlrEvalaux(scip, nlhdlr2, expr, nlhdlr2exprdata, &enfoauxval, sol) ); 1459 1460 SCIPsetExprEnfoAuxValueNonlinear(expr, e, enfoauxval); 1461 1462 if( REALABS(enfoauxval - auxvarvalue) > maxdiff && enfoauxval != SCIP_INVALID ) /*lint !e777*/ 1463 { 1464 maxdiff = REALABS(enfoauxval - auxvarvalue); 1465 *auxvalue = enfoauxval; 1466 } 1467 } 1468 1469 return SCIP_OKAY; 1470 } 1471 1472 /** separation initialization method of a nonlinear handler */ 1473 static 1474 SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaPerspective) 1475 { /*lint --e{715}*/ 1476 int sindicators; 1477 1478 sindicators = nlhdlrexprdata->nindicators; 1479 1480 /* compute 'off' values of expr and subexprs (and thus auxvars too) */ 1481 SCIP_CALL( computeOffValues(scip, SCIPnlhdlrGetData(nlhdlr), nlhdlrexprdata, expr) ); 1482 1483 /* some indicator variables might have been removed if evaluation failed, check how many remain */ 1484 if( nlhdlrexprdata->nindicators == 0 ) 1485 { 1486 SCIPfreeBlockMemoryArray(scip, &nlhdlrexprdata->indicators, sindicators); 1487 SCIPfreeBlockMemoryArray(scip, &nlhdlrexprdata->exprvals0, sindicators); 1488 } 1489 else if( nlhdlrexprdata->nindicators < sindicators ) 1490 { 1491 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nlhdlrexprdata->indicators, sindicators, nlhdlrexprdata->nindicators) ); 1492 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nlhdlrexprdata->exprvals0, sindicators, nlhdlrexprdata->nindicators) ); 1493 } 1494 1495 return SCIP_OKAY; 1496 } 1497 1498 1499 #if 0 1500 /** separation deinitialization method of a nonlinear handler (called during CONSEXITSOL) */ 1501 static 1502 SCIP_DECL_NLHDLREXITSEPA(nlhdlrExitSepaPerspective) 1503 { /*lint --e{715}*/ 1504 SCIPerrorMessage("method of perspective nonlinear handler not implemented yet\n"); 1505 SCIPABORT(); /*lint --e{527}*/ 1506 1507 return SCIP_OKAY; 1508 } 1509 #endif 1510 1511 /** nonlinear handler enforcement callback 1512 * 1513 * "Perspectivies" cuts produced by other nonlinear handlers. 1514 * 1515 * Suppose that we want to separate \f$x\f$ from the set \f$\{ x : g(x) \leq 0\}\f$. 1516 * If \f$g(x) = g^0\f$ if indicator \f$z = 0\f$, and a cut is given by \f$\sum_i a_ix_i + c \leq \text{aux}\f$, where \f$x_i = x_i^0\f$ if \f$z = 0\f$ for all \f$i\f$, 1517 * then the "perspectivied" cut is \f[\sum_i a_ix_i + c + (1 - z)\,(g^0 - c - \sum_i a_ix_i^0) \leq \text{aux}.\f] 1518 * This ensures that at \f$z = 1\f$, the new cut is equivalent to the given cut, and at \f$z = 0\f$ it reduces to \f$g^0 \leq \text{aux}\f$. 1519 */ 1520 static 1521 SCIP_DECL_NLHDLRENFO(nlhdlrEnfoPerspective) 1522 { /*lint --e{715}*/ 1523 SCIP_ROWPREP* rowprep; 1524 SCIP_VAR* auxvar; 1525 int i; 1526 int j; 1527 SCIP_NLHDLRDATA* nlhdlrdata; 1528 SCIP_Real cst0; 1529 SCIP_VAR* indicator; 1530 SCIP_PTRARRAY* rowpreps2; 1531 SCIP_PTRARRAY* rowpreps; 1532 int nrowpreps; 1533 SCIP_SOL* solcopy; 1534 SCIP_Bool doprobing; 1535 SCIP_BOOLARRAY* addedbranchscores2; 1536 SCIP_Bool stop; 1537 int nenfos; 1538 int* enfoposs; 1539 SCIP_SOL* soladj; 1540 int pos; 1541 SCVARDATA* scvdata; 1542 1543 nlhdlrdata = SCIPnlhdlrGetData(nlhdlr); 1544 1545 #ifdef SCIP_DEBUG 1546 SCIPinfoMessage(scip, NULL, "enforcement method of perspective nonlinear handler called for expr %p: ", (void*)expr); 1547 SCIP_CALL( SCIPprintExpr(scip, expr, NULL) ); 1548 SCIPinfoMessage(scip, NULL, " at\n"); 1549 for( i = 0; i < nlhdlrexprdata->nvars; ++i ) 1550 { 1551 SCIPinfoMessage(scip, NULL, "%s = %g\n", SCIPvarGetName(nlhdlrexprdata->vars[i]), 1552 SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i])); 1553 } 1554 SCIPinfoMessage(scip, NULL, "%s = %g", SCIPvarGetName(SCIPgetExprAuxVarNonlinear(expr)), 1555 SCIPgetSolVal(scip, sol, SCIPgetExprAuxVarNonlinear(expr))); 1556 #endif 1557 1558 assert(scip != NULL); 1559 assert(expr != NULL); 1560 assert(conshdlr != NULL); 1561 assert(nlhdlrexprdata != NULL); 1562 assert(nlhdlrdata != NULL); 1563 1564 if( nlhdlrexprdata->nindicators == 0 ) 1565 { 1566 /* we might have removed all indicators in initsepa */ 1567 *result = SCIP_DIDNOTRUN; 1568 return SCIP_OKAY; 1569 } 1570 1571 auxvar = SCIPgetExprAuxVarNonlinear(expr); 1572 assert(auxvar != NULL); 1573 1574 /* detect should have picked only those expressions for which at least one other nlhdlr can enforce */ 1575 assert(SCIPgetExprNEnfosNonlinear(expr) > 1); 1576 1577 SCIP_CALL( SCIPallocBufferArray(scip, &enfoposs, SCIPgetExprNEnfosNonlinear(expr) - 1) ); 1578 1579 doprobing = FALSE; 1580 nenfos = 0; 1581 soladj = NULL; 1582 1583 /* find suitable nlhdlrs and check if there is enough violation to do probing */ 1584 for( j = 0; j < SCIPgetExprNEnfosNonlinear(expr); ++j ) 1585 { 1586 SCIP_NLHDLR* nlhdlr2; 1587 SCIP_NLHDLREXPRDATA* nlhdlr2exprdata; 1588 SCIP_NLHDLR_METHOD nlhdlr2participate; 1589 SCIP_Real nlhdlr2auxvalue; 1590 SCIP_Real violation; 1591 SCIP_Bool violbelow; 1592 SCIP_Bool violabove; 1593 SCIP_Bool sepausesactivity = FALSE; 1594 1595 SCIPgetExprEnfoDataNonlinear(expr, j, &nlhdlr2, &nlhdlr2exprdata, &nlhdlr2participate, !overestimate ? &sepausesactivity : NULL, overestimate ? &sepausesactivity: NULL, &nlhdlr2auxvalue); /*lint !e826*/ 1596 1597 if( nlhdlr2 == nlhdlr ) 1598 continue; 1599 1600 /* if nlhdlr2 cannot estimate, then cannot use it */ 1601 if( !SCIPnlhdlrHasEstimate(nlhdlr2) ) 1602 continue; 1603 1604 /* if nlhdlr2 does not participate in the separation on the desired side (overestimate), then skip it */ 1605 if( (nlhdlr2participate & (overestimate ? SCIP_NLHDLR_METHOD_SEPAABOVE : SCIP_NLHDLR_METHOD_SEPABELOW)) == 0 ) 1606 continue; 1607 1608 /* if only working on convex-looking expressions, then skip nlhdlr if it uses activity for estimates */ 1609 if( nlhdlrdata->convexonly && sepausesactivity ) 1610 continue; 1611 1612 /* evalaux should have called evalaux of nlhdlr2 by now 1613 * check whether handling the violation for nlhdlr2 requires under- or overestimation and this fits to 1614 * overestimate flag 1615 */ 1616 SCIP_CALL( SCIPgetExprAbsAuxViolationNonlinear(scip, expr, nlhdlr2auxvalue, sol, &violation, &violbelow, 1617 &violabove) ); 1618 assert(violation >= 0.0); 1619 1620 if( (overestimate && !violabove) || (!overestimate && !violbelow) ) 1621 continue; 1622 1623 /* if violation is small, cuts would likely be weak - skip perspectification */ 1624 if( !allowweakcuts && violation < SCIPfeastol(scip) ) 1625 continue; 1626 1627 enfoposs[nenfos] = j; 1628 ++nenfos; 1629 1630 /* enable probing if tightening the domain could be useful for nlhdlr and violation is above threshold */ 1631 if( sepausesactivity && violation >= nlhdlrdata->minviolprobing ) 1632 doprobing = TRUE; 1633 } 1634 1635 if( nenfos == 0 ) 1636 { 1637 *result = SCIP_DIDNOTRUN; 1638 SCIPfreeBufferArray(scip, &enfoposs); 1639 return SCIP_OKAY; 1640 } 1641 1642 /* check probing frequency against depth in b&b tree */ 1643 if( nlhdlrdata->probingfreq == -1 || (nlhdlrdata->probingfreq == 0 && SCIPgetDepth(scip) != 0) || 1644 (nlhdlrdata->probingfreq > 0 && SCIPgetDepth(scip) % nlhdlrdata->probingfreq != 0) ) 1645 doprobing = FALSE; 1646 1647 /* if addbranchscores is TRUE, then we can assume to be in enforcement and not in separation */ 1648 if( nlhdlrdata->probingonlyinsepa && addbranchscores ) 1649 doprobing = FALSE; 1650 1651 /* disable probing if already being in probing or if in a subscip */ 1652 if( SCIPinProbing(scip) || SCIPgetSubscipDepth(scip) != 0 ) 1653 doprobing = FALSE; 1654 1655 nrowpreps = 0; 1656 *result = SCIP_DIDNOTFIND; 1657 solcopy = sol; 1658 stop = FALSE; 1659 1660 SCIP_CALL( SCIPcreatePtrarray(scip, &rowpreps2) ); 1661 SCIP_CALL( SCIPcreatePtrarray(scip, &rowpreps) ); 1662 SCIP_CALL( SCIPcreateBoolarray(scip, &addedbranchscores2) ); 1663 1664 /* build cuts for every indicator variable */ 1665 for( i = 0; i < nlhdlrexprdata->nindicators && !stop; ++i ) 1666 { 1667 int v; 1668 int minidx; 1669 int maxidx; 1670 int r; 1671 SCIP_VAR** probingvars; 1672 SCIP_INTERVAL* probingdoms; 1673 int nprobingvars; 1674 SCIP_Bool doprobingind; 1675 SCIP_Real indval; 1676 SCIP_Real solval; 1677 SCIP_Bool adjrefpoint; 1678 1679 indicator = nlhdlrexprdata->indicators[i]; 1680 probingvars = NULL; 1681 probingdoms = NULL; 1682 nprobingvars = 0; 1683 doprobingind = doprobing; 1684 solval = SCIPgetSolVal(scip, solcopy, indicator); 1685 adjrefpoint = nlhdlrdata->adjrefpoint && !SCIPisFeasEQ(scip, solval, 1.0); 1686 1687 SCIP_CALL( analyseOnoffBounds(scip, nlhdlrdata, nlhdlrexprdata, indicator, &probingvars, &probingdoms, 1688 &nprobingvars, &doprobingind, result) ); 1689 1690 /* don't add perspective cuts for fixed indicators since there is no use for perspectivy */ 1691 if( SCIPvarGetLbLocal(indicator) >= 0.5 ) 1692 { 1693 assert(!doprobingind); 1694 continue; 1695 } 1696 1697 if( SCIPvarGetUbLocal(indicator) <= 0.5 ) 1698 { /* this case is stronger as it implies that everything is fixed; therefore we are now happy */ 1699 assert(!doprobingind); 1700 SCIPfreeBufferArrayNull(scip, &probingvars); 1701 SCIPfreeBufferArrayNull(scip, &probingdoms); 1702 goto TERMINATE; 1703 } 1704 1705 if( doprobingind ) 1706 { 1707 SCIP_Bool propagate; 1708 SCIP_Bool cutoff_probing; 1709 SCIP_Bool cutoff; 1710 SCIP_Bool fixed; 1711 1712 #ifndef NDEBUG 1713 SCIP_Real* solvals; 1714 SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nlhdlrexprdata->nvars) ); 1715 for( v = 0; v < nlhdlrexprdata->nvars; ++v ) 1716 { 1717 solvals[v] = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[v]); 1718 } 1719 #endif 1720 1721 propagate = SCIPgetDepth(scip) == 0; 1722 1723 SCIP_CALL( startProbing(scip, nlhdlrdata, nlhdlrexprdata, indicator, probingvars, probingdoms, nprobingvars, 1724 sol, &solcopy, &cutoff_probing) ); 1725 1726 #ifndef NDEBUG 1727 for( v = 0; v < nlhdlrexprdata->nvars; ++v ) 1728 { 1729 assert(solvals[v] == SCIPgetSolVal(scip, solcopy, nlhdlrexprdata->vars[v])); /*lint !e777*/ 1730 } 1731 SCIPfreeBufferArray(scip, &solvals); 1732 #endif 1733 1734 SCIPfreeBufferArrayNull(scip, &probingvars); 1735 SCIPfreeBufferArrayNull(scip, &probingdoms); 1736 1737 if( propagate ) 1738 { /* we are in the root node and startProbing did propagation */ 1739 /* probing propagation might have detected infeasibility */ 1740 if( cutoff_probing ) 1741 { 1742 /* indicator == 1 is infeasible -> set indicator to 0 */ 1743 1744 SCIP_CALL( SCIPendProbing(scip) ); 1745 1746 SCIP_CALL( SCIPfixVar(scip, indicator, 0.0, &cutoff, &fixed) ); 1747 1748 if( cutoff ) 1749 { 1750 *result = SCIP_CUTOFF; 1751 goto TERMINATE; 1752 } 1753 1754 continue; 1755 } 1756 1757 /* probing propagation in the root node can provide better on/off bounds */ 1758 SCIP_CALL( tightenOnBounds(nlhdlrexprdata, nlhdlrdata->scvars, indicator) ); 1759 } 1760 } 1761 1762 if( adjrefpoint ) 1763 { 1764 /* make sure that when we adjust the point, we don't divide by something too close to 0.0 */ 1765 indval = MAX(solval, 0.1); 1766 1767 /* create an adjusted point x^adj = (x* - x0) / z* + x0 */ 1768 SCIP_CALL( SCIPcreateSol(scip, &soladj, NULL) ); 1769 for( v = 0; v < nlhdlrexprdata->nvars; ++v ) 1770 { 1771 if( SCIPvarGetStatus(nlhdlrexprdata->vars[v]) == SCIP_VARSTATUS_FIXED ) 1772 continue; 1773 1774 scvdata = getSCVarDataInd(nlhdlrdata->scvars, nlhdlrexprdata->vars[v], indicator, &pos); 1775 1776 /* a non-semicontinuous variable must be linear in expr; skip it */ 1777 if( scvdata == NULL ) 1778 continue; 1779 1780 SCIP_CALL( SCIPsetSolVal(scip, soladj, nlhdlrexprdata->vars[v], 1781 (SCIPgetSolVal(scip, solcopy, nlhdlrexprdata->vars[v]) - scvdata->vals0[pos]) / indval 1782 + scvdata->vals0[pos]) ); 1783 } 1784 for( v = 0; v < nlhdlrexprdata->nindicators; ++v ) 1785 { 1786 if( SCIPvarGetStatus(nlhdlrexprdata->indicators[v]) == SCIP_VARSTATUS_FIXED ) 1787 continue; 1788 1789 SCIP_CALL( SCIPsetSolVal(scip, soladj, nlhdlrexprdata->indicators[v], 1790 SCIPgetSolVal(scip, solcopy, nlhdlrexprdata->indicators[v])) ); 1791 } 1792 if( SCIPvarGetStatus(auxvar) != SCIP_VARSTATUS_FIXED ) 1793 { 1794 SCIP_CALL( SCIPsetSolVal(scip, soladj, auxvar, SCIPgetSolVal(scip, solcopy, auxvar)) ); 1795 } 1796 } 1797 1798 /* use cuts from every suitable nlhdlr */ 1799 for( j = 0; j < nenfos; ++j ) 1800 { 1801 SCIP_Bool addedbranchscores2j; 1802 SCIP_NLHDLR* nlhdlr2; 1803 SCIP_NLHDLREXPRDATA* nlhdlr2exprdata; 1804 SCIP_Real nlhdlr2auxvalue; 1805 SCIP_Bool success2; 1806 1807 SCIPgetExprEnfoDataNonlinear(expr, enfoposs[j], &nlhdlr2, &nlhdlr2exprdata, NULL, NULL, NULL, &nlhdlr2auxvalue); 1808 assert(SCIPnlhdlrHasEstimate(nlhdlr2) && nlhdlr2 != nlhdlr); 1809 1810 SCIPdebugMsg(scip, "asking nonlinear handler %s to %sestimate\n", SCIPnlhdlrGetName(nlhdlr2), overestimate ? "over" : "under"); 1811 1812 /* ask the nonlinear handler for an estimator */ 1813 if( adjrefpoint ) 1814 { 1815 SCIP_CALL( SCIPnlhdlrEvalaux(scip, nlhdlr2, expr, nlhdlr2exprdata, &nlhdlr2auxvalue, soladj) ); 1816 1817 /* coverity[copy_paste_error] */ 1818 SCIP_CALL( SCIPnlhdlrEstimate(scip, conshdlr, nlhdlr2, expr, 1819 nlhdlr2exprdata, soladj, 1820 nlhdlr2auxvalue, overestimate, SCIPgetSolVal(scip, solcopy, auxvar), 1821 FALSE, rowpreps2, &success2, &addedbranchscores2j) ); 1822 } 1823 else 1824 { 1825 SCIP_CALL( SCIPnlhdlrEstimate(scip, conshdlr, nlhdlr2, expr, 1826 nlhdlr2exprdata, solcopy, 1827 nlhdlr2auxvalue, overestimate, SCIPgetSolVal(scip, solcopy, auxvar), 1828 FALSE, rowpreps2, &success2, &addedbranchscores2j) ); 1829 } 1830 1831 minidx = SCIPgetPtrarrayMinIdx(scip, rowpreps2); 1832 maxidx = SCIPgetPtrarrayMaxIdx(scip, rowpreps2); 1833 1834 assert((success2 && minidx <= maxidx) || (!success2 && minidx > maxidx)); 1835 1836 /* perspectivy all cuts from nlhdlr2 and add them to rowpreps */ 1837 for( r = minidx; r <= maxidx; ++r ) 1838 { 1839 SCIP_Real maxcoef; 1840 SCIP_Real* rowprepcoefs; 1841 SCIP_VAR** rowprepvars; 1842 1843 rowprep = (SCIP_ROWPREP*) SCIPgetPtrarrayVal(scip, rowpreps2, r); 1844 assert(rowprep != NULL); 1845 1846 #ifdef SCIP_DEBUG 1847 SCIPinfoMessage(scip, NULL, "rowprep for expr "); 1848 SCIPprintExpr(scip, expr, NULL); 1849 SCIPinfoMessage(scip, NULL, "rowprep before perspectivy is: \n"); 1850 SCIPprintRowprep(scip, rowprep, NULL); 1851 #endif 1852 1853 /* given a rowprep: sum aixi + sum biyi + c, where xi are semicontinuous variables and yi are 1854 * non-semicontinuous variables (which appear in expr linearly, which detect must have ensured), 1855 * perspectivy the semicontinuous part by adding (1-z)(g0 - c - sum aix0i) (the constant is 1856 * treated as belonging to the semicontinuous part) 1857 */ 1858 1859 /* we want cst0 = g0 - c - sum aix0i; first add g0 - c */ 1860 cst0 = nlhdlrexprdata->exprvals0[i] + SCIProwprepGetSide(rowprep); 1861 1862 maxcoef = 0.0; 1863 rowprepcoefs = SCIProwprepGetCoefs(rowprep); 1864 rowprepvars = SCIProwprepGetVars(rowprep); 1865 1866 for( v = 0; v < SCIProwprepGetNVars(rowprep); ++v ) 1867 { 1868 if( REALABS( rowprepcoefs[v]) > maxcoef ) 1869 { 1870 maxcoef = REALABS(rowprepcoefs[v]); 1871 } 1872 1873 scvdata = getSCVarDataInd(nlhdlrdata->scvars, rowprepvars[v], indicator, &pos); 1874 1875 /* a non-semicontinuous variable must be linear in expr; skip it */ 1876 if( scvdata == NULL ) 1877 continue; 1878 1879 cst0 -= rowprepcoefs[v] * scvdata->vals0[pos]; 1880 } 1881 1882 /* only perspectivy when the absolute value of cst0 is not too small 1883 * TODO on ex1252a there was cst0=0 - ok to still use the cut? 1884 */ 1885 if( cst0 == 0.0 || maxcoef / REALABS(cst0) <= 10.0 / SCIPfeastol(scip) ) 1886 { 1887 /* update the rowprep by adding cst0 - cst0*z */ 1888 SCIProwprepAddConstant(rowprep, cst0); 1889 SCIP_CALL(SCIPaddRowprepTerm(scip, rowprep, indicator, -cst0)); 1890 } 1891 else 1892 { 1893 SCIPfreeRowprep(scip, &rowprep); 1894 continue; 1895 } 1896 1897 SCIP_CALL(SCIPaddRowprepTerm(scip, rowprep, auxvar, -1.0)); 1898 1899 SCIPdebugMsg(scip, "rowprep after perspectivy is: \n"); 1900 #ifdef SCIP_DEBUG 1901 SCIPprintRowprep(scip, rowprep, NULL); 1902 #endif 1903 1904 SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, nrowpreps, rowprep) ); 1905 SCIP_CALL( SCIPsetBoolarrayVal(scip, addedbranchscores2, nrowpreps, addedbranchscores2j) ); 1906 ++nrowpreps; 1907 } 1908 1909 SCIP_CALL( SCIPclearPtrarray(scip, rowpreps2) ); 1910 } 1911 1912 if( adjrefpoint ) 1913 { 1914 SCIP_CALL( SCIPfreeSol(scip, &soladj) ); 1915 } 1916 1917 if( doprobingind ) 1918 { 1919 SCIP_CALL( SCIPendProbing(scip) ); 1920 } 1921 1922 /* add all cuts found for indicator i */ 1923 for( r = SCIPgetPtrarrayMinIdx(scip, rowpreps); r <= SCIPgetPtrarrayMaxIdx(scip, rowpreps) && !stop; ++r ) 1924 { 1925 SCIP_RESULT resultr; 1926 1927 #ifdef SCIP_DEBUG 1928 SCIPprintRowprep(scip, rowprep, NULL); 1929 #endif 1930 rowprep = (SCIP_ROWPREP*) SCIPgetPtrarrayVal(scip, rowpreps, r); 1931 resultr = SCIP_DIDNOTFIND; 1932 1933 (void) strcat(SCIProwprepGetName(rowprep), "_persp_indicator_"); 1934 (void) strcat(SCIProwprepGetName(rowprep), SCIPvarGetName(indicator)); 1935 1936 SCIP_CALL( SCIPprocessRowprepNonlinear(scip, nlhdlr, cons, expr, rowprep, overestimate, auxvar, auxvalue, 1937 allowweakcuts, SCIPgetBoolarrayVal(scip, addedbranchscores2, r), FALSE, solcopy, &resultr) ); 1938 1939 if( resultr == SCIP_SEPARATED ) 1940 *result = SCIP_SEPARATED; 1941 else if( resultr == SCIP_CUTOFF ) 1942 { 1943 *result = SCIP_CUTOFF; 1944 stop = TRUE; 1945 } 1946 else if( resultr == SCIP_BRANCHED ) 1947 { 1948 if( *result != SCIP_SEPARATED && *result != SCIP_REDUCEDDOM ) 1949 *result = SCIP_BRANCHED; 1950 } 1951 else if( resultr != SCIP_DIDNOTFIND ) 1952 { 1953 SCIPerrorMessage("estimate called by perspective nonlinear handler returned invalid result <%d>\n", resultr); 1954 return SCIP_INVALIDRESULT; 1955 } 1956 } 1957 1958 /* free all rowpreps for indicator i */ 1959 for( r = SCIPgetPtrarrayMinIdx(scip, rowpreps); r <= SCIPgetPtrarrayMaxIdx(scip, rowpreps); ++r ) 1960 { 1961 rowprep = (SCIP_ROWPREP*) SCIPgetPtrarrayVal(scip, rowpreps, r); 1962 SCIPfreeRowprep(scip, &rowprep); 1963 } 1964 1965 SCIP_CALL( SCIPclearPtrarray(scip, rowpreps) ); 1966 } 1967 1968 TERMINATE: 1969 SCIP_CALL( SCIPfreeBoolarray(scip, &addedbranchscores2) ); 1970 SCIP_CALL( SCIPfreePtrarray(scip, &rowpreps) ); 1971 SCIP_CALL( SCIPfreePtrarray(scip, &rowpreps2) ); 1972 if( solcopy != sol ) 1973 { 1974 SCIP_CALL( SCIPfreeSol(scip, &solcopy) ); 1975 } 1976 SCIPfreeBufferArray(scip, &enfoposs); 1977 1978 return SCIP_OKAY; 1979 } 1980 1981 1982 /* 1983 * nonlinear handler specific interface methods 1984 */ 1985 1986 /** includes perspective nonlinear handler in nonlinear constraint handler */ 1987 SCIP_RETCODE SCIPincludeNlhdlrPerspective( 1988 SCIP* scip /**< SCIP data structure */ 1989 ) 1990 { 1991 SCIP_NLHDLRDATA* nlhdlrdata; 1992 SCIP_NLHDLR* nlhdlr; 1993 1994 assert(scip != NULL); 1995 1996 /* create nonlinear handler data */ 1997 SCIP_CALL( SCIPallocBlockMemory(scip, &nlhdlrdata) ); 1998 BMSclearMemory(nlhdlrdata); 1999 2000 SCIP_CALL( SCIPincludeNlhdlrNonlinear(scip, &nlhdlr, NLHDLR_NAME, NLHDLR_DESC, NLHDLR_DETECTPRIORITY, 2001 NLHDLR_ENFOPRIORITY, nlhdlrDetectPerspective, nlhdlrEvalauxPerspective, nlhdlrdata) ); 2002 assert(nlhdlr != NULL); 2003 2004 SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/maxproprounds", 2005 "maximal number of propagation rounds in probing", 2006 &nlhdlrdata->maxproprounds, FALSE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX, NULL, NULL) ); 2007 2008 SCIP_CALL( SCIPaddRealParam(scip, "nlhdlr/" NLHDLR_NAME "/mindomreduction", 2009 "minimal relative reduction in a variable's domain for applying probing", 2010 &nlhdlrdata->mindomreduction, FALSE, DEFAULT_MINDOMREDUCTION, 0.0, 1.0, NULL, NULL) ); 2011 2012 SCIP_CALL( SCIPaddRealParam(scip, "nlhdlr/" NLHDLR_NAME "/minviolprobing", 2013 "minimal violation w.r.t. auxiliary variables for applying probing", 2014 &nlhdlrdata->minviolprobing, FALSE, DEFAULT_MINVIOLPROBING, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 2015 2016 SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/probingonlyinsepa", 2017 "whether to do probing only in separation", 2018 &nlhdlrdata->probingonlyinsepa, FALSE, DEFAULT_PROBINGONLYINSEPA, NULL, NULL) ); 2019 2020 SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/probingfreq", 2021 "probing frequency (-1 - no probing, 0 - root node only)", 2022 &nlhdlrdata->probingfreq, FALSE, DEFAULT_PROBINGFREQ, -1, INT_MAX, NULL, NULL) ); 2023 2024 SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/convexonly", 2025 "whether perspective cuts are added only for convex expressions", 2026 &nlhdlrdata->convexonly, FALSE, DEFAULT_CONVEXONLY, NULL, NULL) ); 2027 2028 SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/tightenbounds", 2029 "whether variable semicontinuity is used to tighten variable bounds", 2030 &nlhdlrdata->tightenbounds, FALSE, DEFAULT_TIGHTENBOUNDS, NULL, NULL) ); 2031 2032 SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/adjrefpoint", 2033 "whether to adjust the reference point", 2034 &nlhdlrdata->adjrefpoint, FALSE, DEFAULT_ADJREFPOINT, NULL, NULL) ); 2035 2036 SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrPerspective); 2037 SCIPnlhdlrSetFreeHdlrData(nlhdlr, nlhdlrFreehdlrdataPerspective); 2038 SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrFreeExprDataPerspective); 2039 SCIPnlhdlrSetInitExit(nlhdlr, NULL, nlhdlrExitPerspective); 2040 SCIPnlhdlrSetSepa(nlhdlr, nlhdlrInitSepaPerspective, nlhdlrEnfoPerspective, NULL, NULL); 2041 2042 return SCIP_OKAY; 2043 } 2044