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_default.c 26 * @ingroup DEFPLUGINS_NLHDLR 27 * @brief default nonlinear handler that calls expression handler methods 28 * @author Stefan Vigerske 29 */ 30 31 #include <string.h> 32 33 #include "scip/nlhdlr_default.h" 34 #include "scip/pub_nlhdlr.h" 35 #include "scip/cons_nonlinear.h" 36 37 /* fundamental nonlinear handler properties */ 38 #define NLHDLR_NAME "default" 39 #define NLHDLR_DESC "default handler for expressions" 40 #define NLHDLR_DETECTPRIORITY 0 41 #define NLHDLR_ENFOPRIORITY 0 42 43 /** translate from one value of infinity to another 44 * 45 * if val is ≥ infty1, then give infty2, else give val 46 */ 47 #define infty2infty(infty1, infty2, val) ((val) >= (infty1) ? (infty2) : (val)) 48 49 #define UNDERESTIMATEUSESACTIVITY 0x1u /**< whether underestimation uses activity */ 50 #define OVERESTIMATEUSESACTIVITY 0x2u /**< whether overestimation uses activity */ 51 52 /*lint -e666*/ 53 /*lint -e850*/ 54 55 /** evaluates an expression w.r.t. the values in the auxiliary variables */ 56 static 57 SCIP_RETCODE evalExprInAux( 58 SCIP* scip, /**< SCIP data structure */ 59 SCIP_EXPR* expr, /**< expression to be evaluated */ 60 SCIP_Real* val, /**< buffer to store value of expression */ 61 SCIP_SOL* sol /**< solution to be evaluated */ 62 ) 63 { 64 SCIP_Real* childvals; 65 SCIP_VAR* childvar; 66 int c; 67 68 assert(scip != NULL); 69 assert(expr != NULL); 70 assert(val != NULL); 71 assert(SCIPexprGetNChildren(expr) > 0); 72 73 SCIP_CALL( SCIPallocBufferArray(scip, &childvals, SCIPexprGetNChildren(expr)) ); 74 75 for( c = 0; c < SCIPexprGetNChildren(expr); ++c ) 76 { 77 childvar = SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[c]); 78 /* there should be an auxiliary variable, because we created them in detect for every child if we said that we will separate; 79 * at the moment, EVALAUX should only be called for nlhdlrs that said they will separate 80 * if that changes, then we should handle this here, e.g., via *val = SCIPexprGetEvalValue(expr); break; 81 */ 82 assert(childvar != NULL); 83 84 childvals[c] = SCIPgetSolVal(scip, sol, childvar); 85 } 86 87 SCIP_CALL( SCIPcallExprEval(scip, expr, childvals, val) ); 88 89 SCIPfreeBufferArray(scip, &childvals); 90 91 return SCIP_OKAY; 92 } 93 94 /** check whether expression should be handled by the default nlhdlr 95 * 96 * if no nlhdlr so far provides enforcement or boundtightening for expr, then the default nlhdlr takes over 97 */ 98 static 99 SCIP_DECL_NLHDLRDETECT(nlhdlrDetectDefault) 100 { /*lint --e{715}*/ 101 SCIP_EXPRHDLR* exprhdlr; 102 SCIP_Bool estimatebelowusesactivity = FALSE; 103 SCIP_Bool estimateaboveusesactivity = FALSE; 104 int c; 105 106 assert(scip != NULL); 107 assert(nlhdlr != NULL); 108 assert(expr != NULL); 109 assert(enforcing != NULL); 110 assert(participating != NULL); 111 assert(nlhdlrexprdata != NULL); 112 113 exprhdlr = SCIPexprGetHdlr(expr); 114 assert(exprhdlr != NULL); 115 116 if( (*enforcing & SCIP_NLHDLR_METHOD_ACTIVITY) == 0 ) 117 { 118 /* expr handlers having reverseprop but no inteval is something that we don't support at the moment for simplicity */ 119 assert(!SCIPexprhdlrHasReverseProp(exprhdlr) || SCIPexprhdlrHasIntEval(exprhdlr)); 120 121 /* participate in inteval and/or reverseprop if that is not yet provided in enforcing and we have inteval */ 122 if( SCIPexprhdlrHasIntEval(exprhdlr) ) 123 *participating = SCIP_NLHDLR_METHOD_ACTIVITY; 124 } 125 126 /* participate in sepa if exprhdlr for expr has an estimate callback and sepa below or above is still missing */ 127 if( ((*enforcing & SCIP_NLHDLR_METHOD_SEPABOTH) != SCIP_NLHDLR_METHOD_SEPABOTH) && SCIPexprhdlrHasEstimate(exprhdlr) ) 128 { 129 /* communicate back that the nlhdlr will provide the separation on the currently missing sides */ 130 if( (*enforcing & SCIP_NLHDLR_METHOD_SEPABELOW) == 0 ) 131 *participating |= SCIP_NLHDLR_METHOD_SEPABELOW; 132 133 if( (*enforcing & SCIP_NLHDLR_METHOD_SEPAABOVE) == 0 ) 134 *participating |= SCIP_NLHDLR_METHOD_SEPAABOVE; 135 } 136 137 if( !*participating ) 138 return SCIP_OKAY; 139 140 /* since this is the default handler, we enforce where we participate */ 141 *enforcing |= *participating; 142 143 /* increment activity usage counter and create auxiliary variables if necessary 144 * if separating, first guess whether we will use activities in estimate (distinguish under- and overestimation) 145 * we assume that the exprhdlr will use activity on all children iff we are estimating on a nonconvex side 146 * TODO it would be better to request this information directly from the exprhdlr than inferring it from curvature, 147 * but with the currently available exprhdlr that wouldn't make a difference 148 */ 149 if( *participating & SCIP_NLHDLR_METHOD_SEPABOTH ) 150 { 151 SCIP_EXPRCURV* childcurv; 152 153 /* allocate memory to store the required curvature of the children (though we don't use it) */ 154 SCIP_CALL( SCIPallocBufferArray(scip, &childcurv, SCIPexprGetNChildren(expr)) ); 155 156 if( *participating & SCIP_NLHDLR_METHOD_SEPABELOW ) 157 { 158 /* check whether the expression is convex */ 159 SCIP_Bool isconvex; 160 SCIP_CALL( SCIPcallExprCurvature(scip, expr, SCIP_EXPRCURV_CONVEX, &isconvex, childcurv) ); 161 estimatebelowusesactivity = !isconvex; 162 } 163 164 if( *participating & SCIP_NLHDLR_METHOD_SEPAABOVE ) 165 { 166 /* check whether the expression is concave */ 167 SCIP_Bool isconcave; 168 SCIP_CALL( SCIPcallExprCurvature(scip, expr, SCIP_EXPRCURV_CONCAVE, &isconcave, childcurv) ); 169 estimateaboveusesactivity = !isconcave; 170 } 171 172 /* free memory */ 173 SCIPfreeBufferArray(scip, &childcurv); 174 } 175 176 /* indicate enforcement methods required in children: 177 * - if separating, make sure that (auxiliary) variable will exist 178 * - if activity computation, then register activity usage 179 * - if estimating on a non-convex side, then indicate activity usage for separation for that side 180 */ 181 for( c = 0; c < SCIPexprGetNChildren(expr); ++c ) 182 { 183 /* todo skip auxvarusage for value-expressions? would then need update in evalExprInAux, too */ 184 SCIP_CALL( SCIPregisterExprUsageNonlinear(scip, SCIPexprGetChildren(expr)[c], 185 *participating & SCIP_NLHDLR_METHOD_SEPABOTH, 186 *participating & SCIP_NLHDLR_METHOD_ACTIVITY, estimatebelowusesactivity, estimateaboveusesactivity) ); 187 } 188 189 /* remember estimatebelowusesactivity and estimateaboveusesactivity in nlhdlrexprdata */ 190 *nlhdlrexprdata = (SCIP_NLHDLREXPRDATA*)(size_t)((estimatebelowusesactivity ? UNDERESTIMATEUSESACTIVITY : 0x0u) 191 | (estimateaboveusesactivity ? OVERESTIMATEUSESACTIVITY : 0x0u)); 192 193 return SCIP_OKAY; 194 } 195 196 /** evaluate expression w.r.t. values of auxiliary variables in children */ 197 static 198 SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalAuxDefault) 199 { /*lint --e{715}*/ 200 assert(expr != NULL); 201 assert(auxvalue != NULL); 202 203 SCIP_CALL( evalExprInAux(scip, expr, auxvalue, sol) ); 204 205 return SCIP_OKAY; 206 } 207 208 /** initialize LP relaxation by initial estimators */ 209 static 210 SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaDefault) 211 { /*lint --e{715}*/ 212 SCIP_INTERVAL* childrenbounds; 213 SCIP_Real* coefs[SCIP_EXPR_MAXINITESTIMATES]; 214 SCIP_Real constant[SCIP_EXPR_MAXINITESTIMATES]; 215 SCIP_VAR* auxvar; 216 SCIP_ROWPREP* rowprep; 217 int nreturned; 218 int i, j; 219 220 assert(scip != NULL); 221 assert(expr != NULL); 222 assert(infeasible != NULL); 223 224 *infeasible = FALSE; 225 226 if( !SCIPexprhdlrHasInitEstimates(SCIPexprGetHdlr(expr)) ) 227 return SCIP_OKAY; 228 229 SCIPdebug( SCIPinfoMessage(scip, NULL, "initsepa exprhdlr %s for expr ", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))) ); 230 SCIPdebug( SCIPprintExpr(scip, expr, NULL) ); 231 SCIPdebug( SCIPinfoMessage(scip, NULL, "\n") ); 232 233 /* use global bounds of auxvar as global valid bounds for children 234 * if at root node (thus local=global) and estimate actually uses bounds, then intersect with (local) activity of expression 235 */ 236 SCIP_CALL( SCIPallocBufferArray(scip, &childrenbounds, SCIPexprGetNChildren(expr)) ); 237 for( i = 0; i < SCIPexprGetNChildren(expr); ++i ) 238 { 239 auxvar = SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[i]); 240 assert(auxvar != NULL); 241 242 SCIPintervalSetBounds(&childrenbounds[i], 243 -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -SCIPvarGetLbGlobal(auxvar)), 244 infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, SCIPvarGetUbGlobal(auxvar))); 245 246 if( SCIPgetDepth(scip) == 0 && 247 ((underestimate && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY)) || 248 (overestimate && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY ))) ) 249 { 250 SCIP_CALL( SCIPevalExprActivity(scip, SCIPexprGetChildren(expr)[i]) ); 251 SCIPintervalIntersect(&childrenbounds[i], childrenbounds[i], SCIPexprGetActivity(SCIPexprGetChildren(expr)[i])); 252 } 253 254 if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childrenbounds[i]) ) 255 { 256 SCIPdebugMsg(scip, "activity for expression %d (unexpectedly) empty in initsepa\n", i); 257 *infeasible = TRUE; 258 SCIPfreeBufferArray(scip, &childrenbounds); 259 return SCIP_OKAY; 260 } 261 } 262 263 /* allocate each coefficients array */ 264 for( i = 0; i < SCIP_EXPR_MAXINITESTIMATES; ++i ) 265 { 266 SCIP_CALL( SCIPallocBufferArray(scip, &coefs[i], SCIPexprGetNChildren(expr)) ); 267 } 268 269 /* create rowprep */ 270 SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, SCIP_SIDETYPE_RIGHT, FALSE) ); 271 SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, SCIPexprGetNChildren(expr)+1) ); 272 273 /* call the separation initialization callback of the expression handler and turn estimates into SCIP rows */ 274 for( i = 0; i < 2 && !*infeasible; ++i ) 275 { 276 nreturned = 0; 277 if( i == 0 && underestimate ) 278 { 279 SCIP_CALL( SCIPcallExprInitestimates(scip, expr, childrenbounds, FALSE, coefs, constant, &nreturned) ); 280 assert(SCIProwprepGetSidetype(rowprep) == SCIP_SIDETYPE_RIGHT); 281 } 282 if( i == 1 && overestimate ) 283 { 284 SCIP_CALL( SCIPcallExprInitestimates(scip, expr, childrenbounds, TRUE, coefs, constant, &nreturned) ); 285 SCIProwprepSetSidetype(rowprep, SCIP_SIDETYPE_LEFT); 286 } 287 288 for( j = 0; j < nreturned && !*infeasible; ++j ) 289 { 290 SCIP_Bool success; 291 int v; 292 293 SCIProwprepReset(rowprep); 294 295 for( v = 0; v < SCIPexprGetNChildren(expr); ++v ) 296 { 297 SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[v]), coefs[j][v]) ); 298 } 299 SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(expr), -1.0) ); 300 SCIProwprepAddConstant(rowprep, constant[j]); /*lint !e644*/ 301 302 /* special treatment for sums to get equality rows */ 303 if( j == 0 && SCIPisExprSum(scip, expr) ) 304 { 305 SCIP_Real scalefactor; 306 SCIP_ROW* row; 307 308 /* improve numerics by scaling only (does not relax inequality) */ 309 scalefactor = SCIPscaleupRowprep(scip, rowprep, 1.0, &success); 310 if( success && scalefactor == 1.0 && underestimate && overestimate ) 311 { 312 /* if the rowprep didn't have to be changed, then turn it into a row, change this to an equality, and add it to the LP */ 313 /* TODO do this also if not actually needing both under- and overestimator (should still be valid, but also stronger?) */ 314 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "initestimate_sum%d", j); 315 316 SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) ); 317 318 /* since we did not relax the estimator, we can turn the row into an equality */ 319 if( SCIPisInfinity(scip, SCIProwGetRhs(row)) ) 320 { 321 SCIP_CALL( SCIPchgRowRhs(scip, row, SCIProwGetLhs(row)) ); 322 } 323 else 324 { 325 SCIP_CALL( SCIPchgRowLhs(scip, row, SCIProwGetRhs(row)) ); 326 } 327 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 328 329 SCIPdebug( SCIPinfoMessage(scip, NULL, " added %scut ", *infeasible ? "infeasible " : "") ); 330 SCIPdebug( SCIPprintRow(scip, row, NULL) ); 331 332 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 333 334 i = 2; /* to break outside loop on i, too */ 335 break; 336 } 337 } 338 339 /* straighten out numerics */ 340 SCIP_CALL( SCIPcleanupRowprep2(scip, rowprep, NULL, SCIPgetHugeValue(scip), &success) ); 341 342 /* if cleanup removed all but one variable, then the cut is essentially a bound; we can skip this and rely on boundtightening */ 343 if( success && SCIProwprepGetNVars(rowprep) > 1 ) 344 { 345 /* add the cut */ 346 SCIP_ROW* row; 347 348 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "init%sestimate%d_%s", 349 i == 0 ? "under" : "over", j, SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))); 350 351 SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) ); 352 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 353 354 SCIPdebug( SCIPinfoMessage(scip, NULL, " added %scut ", *infeasible ? "infeasible " : "") ); 355 SCIPdebug( SCIPprintRow(scip, row, NULL) ); 356 357 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 358 } 359 } 360 } 361 362 SCIPfreeRowprep(scip, &rowprep); 363 364 for( i = SCIP_EXPR_MAXINITESTIMATES-1; i >= 0; --i ) 365 { 366 SCIPfreeBufferArray(scip, &coefs[i]); 367 } 368 369 SCIPfreeBufferArray(scip, &childrenbounds); 370 371 return SCIP_OKAY; 372 } 373 374 /** compute linear estimator */ 375 static 376 SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateDefault) 377 { /*lint --e{715}*/ 378 SCIP_Real constant; 379 SCIP_Bool local; 380 SCIP_Bool* branchcand = NULL; 381 int nchildren; 382 int c; 383 SCIP_INTERVAL* localbounds; 384 SCIP_INTERVAL* globalbounds; 385 SCIP_Real* refpoint; 386 SCIP_ROWPREP* rowprep; 387 SCIP_VAR* auxvar; 388 389 assert(scip != NULL); 390 assert(expr != NULL); 391 assert(rowpreps != NULL); 392 assert(success != NULL); 393 394 *addedbranchscores = FALSE; 395 396 nchildren = SCIPexprGetNChildren(expr); 397 398 SCIP_CALL( SCIPallocBufferArray(scip, &localbounds, nchildren) ); 399 SCIP_CALL( SCIPallocBufferArray(scip, &globalbounds, nchildren) ); 400 SCIP_CALL( SCIPallocBufferArray(scip, &refpoint, nchildren) ); 401 /* we need to pass a branchcand array to exprhdlr's estimate also if not asked to add branching scores */ 402 SCIP_CALL( SCIPallocBufferArray(scip, &branchcand, nchildren) ); 403 404 SCIPdebug( SCIPinfoMessage(scip, NULL, "estimate exprhdlr %s for expr ", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))) ); 405 SCIPdebug( SCIPprintExpr(scip, expr, NULL) ); 406 SCIPdebug( SCIPinfoMessage(scip, NULL, "\n") ); 407 408 for( c = 0; c < nchildren; ++c ) 409 { 410 auxvar = SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[c]); 411 assert(auxvar != NULL); 412 413 SCIPintervalSetBounds(&localbounds[c], 414 -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -SCIPvarGetLbLocal(auxvar)), 415 infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, SCIPvarGetUbLocal(auxvar))); 416 417 if( ((size_t)nlhdlrexprdata & (overestimate ? OVERESTIMATEUSESACTIVITY : UNDERESTIMATEUSESACTIVITY)) ) 418 { 419 /* if expr estimate uses bounds, then intersect the auxvar bounds with the current activity, in case the latter is a bit tighter */ 420 SCIP_CALL( SCIPevalExprActivity(scip, SCIPexprGetChildren(expr)[c]) ); 421 SCIPintervalIntersectEps(&localbounds[c], SCIPepsilon(scip), localbounds[c], SCIPexprGetActivity(SCIPexprGetChildren(expr)[c])); 422 423 if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, localbounds[c]) ) 424 { 425 *success = FALSE; 426 goto TERMINATE; 427 } 428 } 429 else 430 { 431 /* if we think that expr estimate wouldn't use bounds, then just set something valid */ 432 } 433 434 SCIPintervalSetBounds(&globalbounds[c], 435 -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -SCIPvarGetLbGlobal(auxvar)), 436 infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, SCIPvarGetUbGlobal(auxvar))); 437 438 refpoint[c] = SCIPgetSolVal(scip, sol, auxvar); 439 440 branchcand[c] = TRUE; 441 } 442 443 SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, TRUE) ); 444 445 /* make sure enough space is available in rowprep arrays */ 446 SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nchildren) ); 447 448 /* call the estimation callback of the expression handler */ 449 SCIP_CALL( SCIPcallExprEstimate(scip, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue, 450 SCIProwprepGetCoefs(rowprep), &constant, &local, success, branchcand) ); 451 452 if( *success ) 453 { 454 int i; 455 456 SCIProwprepSetLocal(rowprep, local); 457 458 /* add variables to rowprep (coefs were already added by SCIPexprhdlrEstimateExpr) */ 459 for( i = 0; i < nchildren; ++i ) 460 { 461 SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[i]), 462 SCIProwprepGetCoefs(rowprep)[i]) ); 463 } 464 465 SCIProwprepAddConstant(rowprep, constant); 466 467 SCIPdebug( SCIPinfoMessage(scip, NULL, " found rowprep ") ); 468 SCIPdebug( SCIPprintRowprepSol(scip, rowprep, sol, NULL) ); 469 470 SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, 0, rowprep) ); 471 472 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_%s%p_%s%" SCIP_LONGINT_FORMAT, 473 overestimate ? "over" : "under", 474 SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), 475 (void*)expr, 476 sol != NULL ? "sol" : "lp", 477 sol != NULL ? (SCIP_Longint) SCIPsolGetIndex(sol) : SCIPgetNLPs(scip)); 478 } 479 else 480 { 481 SCIPfreeRowprep(scip, &rowprep); 482 } 483 484 if( addbranchscores ) 485 { 486 SCIP_Real violation; 487 488 #ifndef BRSCORE_ABSVIOL 489 SCIP_CALL( SCIPgetExprRelAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) ); 490 #else 491 SCIP_CALL( SCIPgetExprAbsAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) ); 492 #endif 493 assert(violation > 0.0); /* there should be a violation if we were called to enforce */ 494 495 if( nchildren == 1 ) 496 { 497 if( branchcand[0] ) 498 { 499 SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, SCIPexprGetChildren(expr), 1, violation, sol, addedbranchscores) ); 500 } 501 } 502 else 503 { 504 SCIP_EXPR** exprs; 505 int nexprs = 0; 506 507 /* get list of those children that have the branchcand-flag set */ 508 SCIP_CALL( SCIPallocBufferArray(scip, &exprs, nchildren) ); 509 510 for( c = 0; c < nchildren; ++c ) 511 if( branchcand[c] ) 512 exprs[nexprs++] = SCIPexprGetChildren(expr)[c]; 513 514 SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, exprs, nexprs, violation, sol, addedbranchscores) ); 515 516 SCIPfreeBufferArray(scip, &exprs); 517 } 518 519 if( *addedbranchscores ) 520 { 521 /* count this branchscore as belonging to the exprhdlr, too 522 * thus, it will be counted for the default nlhdlr, but also for this exprhdlr 523 */ 524 SCIPexprhdlrIncrementNBranchings(SCIPexprGetHdlr(expr)); 525 } 526 } 527 528 TERMINATE: 529 SCIPfreeBufferArray(scip, &branchcand); 530 SCIPfreeBufferArray(scip, &refpoint); 531 SCIPfreeBufferArray(scip, &globalbounds); 532 SCIPfreeBufferArray(scip, &localbounds); 533 534 return SCIP_OKAY; 535 } 536 537 /** solution linearization callback */ 538 static 539 SCIP_DECL_NLHDLRSOLLINEARIZE(nlhdlrSollinearizeDefault) 540 { /*lint --e{715}*/ 541 SCIP_Real constant; 542 SCIP_Bool local; 543 SCIP_Bool* branchcand = NULL; 544 int nchildren; 545 int c; 546 int rnd; 547 SCIP_INTERVAL* bounds; 548 SCIP_Real* refpoint; 549 SCIP_VAR* auxvar; 550 551 assert(scip != NULL); 552 assert(expr != NULL); 553 554 SCIPdebug( SCIPinfoMessage(scip, NULL, "sollinearize exprhdlr %s for expr ", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))) ); 555 SCIPdebug( SCIPprintExpr(scip, expr, NULL) ); 556 SCIPdebug( SCIPinfoMessage(scip, NULL, "\n") ); 557 558 nchildren = SCIPexprGetNChildren(expr); 559 560 if( !overestimate && !underestimate ) 561 return SCIP_OKAY; 562 563 /* skip on sum, as the estimator doesn't depend on the reference point (expr is linear in auxvars) */ 564 if( SCIPisExprSum(scip, expr) ) 565 return SCIP_OKAY; 566 567 /* if expr estimate would use bounds, then the function is very likely not convex (w.r.t. global bounds), so skip */ 568 if( (overestimate && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY)) && 569 (underestimate && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY)) ) 570 return SCIP_OKAY; 571 572 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nchildren) ); 573 SCIP_CALL( SCIPallocBufferArray(scip, &refpoint, nchildren) ); 574 /* we need to pass a branchcand array to exprhdlr's estimate also if not asked to add branching scores */ 575 SCIP_CALL( SCIPallocBufferArray(scip, &branchcand, nchildren) ); 576 577 for( c = 0; c < nchildren; ++c ) 578 { 579 auxvar = SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[c]); 580 assert(auxvar != NULL); 581 582 SCIPintervalSetBounds(&bounds[c], 583 -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -SCIPvarGetLbGlobal(auxvar)), 584 infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, SCIPvarGetUbGlobal(auxvar))); 585 586 refpoint[c] = SCIPgetSolVal(scip, sol, auxvar); 587 } 588 589 for( rnd = (overestimate ? 0 : 1); rnd < (underestimate ? 2 : 1); ++rnd ) /* rnd == 0: overestimate, rnd == 1: underestimate */ 590 { 591 SCIP_ROWPREP* rowprep; 592 SCIP_Bool success = FALSE; 593 594 if( rnd == 0 && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY) ) 595 continue; 596 if( rnd == 1 && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY) ) 597 continue; 598 599 SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, rnd == 0 ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, FALSE) ); 600 601 /* make sure enough space is available in rowprep arrays */ 602 SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nchildren + 1) ); 603 604 for( c = 0; c < nchildren; ++c ) 605 branchcand[c] = TRUE; 606 607 /* call the estimation callback of the expression handler 608 * since we pass the global bounds as local bounds, too, we can ignore whether resulting estimator is marked as local 609 */ 610 SCIP_CALL( SCIPcallExprEstimate(scip, expr, bounds, bounds, refpoint, rnd == 0, 611 rnd == 0 ? SCIPinfinity(scip) : -SCIPinfinity(scip), 612 SCIProwprepGetCoefs(rowprep), &constant, &local, &success, branchcand) ); 613 614 if( success ) 615 { 616 int i; 617 618 /* add variables to rowprep (coefs were already added by SCIPexprhdlrEstimateExpr) */ 619 for( i = 0; i < nchildren; ++i ) 620 { 621 SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[i]), 622 SCIProwprepGetCoefs(rowprep)[i]) ); 623 } 624 625 SCIProwprepAddConstant(rowprep, constant); 626 627 SCIPdebug( SCIPinfoMessage(scip, NULL, " found rowprep ") ); 628 SCIPdebug( SCIPprintRowprepSol(scip, rowprep, sol, NULL) ); 629 630 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_%s%p_sol%dnotify", 631 rnd == 0 ? "over" : "under", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), (void*)expr, SCIPsolGetIndex(sol)); 632 633 /* complete estimator to cut and clean it up */ 634 SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(expr), -1.0) ); 635 SCIP_CALL( SCIPcleanupRowprep2(scip, rowprep, sol, SCIPgetHugeValue(scip), &success) ); 636 } 637 638 /* if cleanup succeeded and rowprep is still global, add to cutpool */ 639 if( success && !SCIProwprepIsLocal(rowprep) ) 640 { 641 SCIP_ROW* row; 642 643 SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) ); 644 SCIP_CALL( SCIPaddPoolCut(scip, row) ); 645 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 646 } 647 648 SCIPfreeRowprep(scip, &rowprep); 649 } 650 651 SCIPfreeBufferArray(scip, &branchcand); 652 SCIPfreeBufferArray(scip, &refpoint); 653 SCIPfreeBufferArray(scip, &bounds); 654 655 return SCIP_OKAY; 656 } 657 658 /** interval-evaluate expression w.r.t. activity of children */ 659 static 660 SCIP_DECL_NLHDLRINTEVAL(nlhdlrIntevalDefault) 661 { /*lint --e{715}*/ 662 assert(scip != NULL); 663 assert(expr != NULL); 664 665 /* call the interval evaluation callback of the expression handler */ 666 SCIP_CALL( SCIPcallExprInteval(scip, expr, interval, intevalvar, intevalvardata) ); 667 668 return SCIP_OKAY; 669 } 670 671 /** tighten bounds on children from bounds on expression and bounds on children */ 672 static 673 SCIP_DECL_NLHDLRREVERSEPROP(nlhdlrReversepropDefault) 674 { /*lint --e{715}*/ 675 SCIP_INTERVAL* childrenbounds; 676 int c; 677 678 assert(scip != NULL); 679 assert(expr != NULL); 680 assert(infeasible != NULL); 681 assert(nreductions != NULL); 682 683 *nreductions = 0; 684 685 SCIP_CALL( SCIPallocBufferArray(scip, &childrenbounds, SCIPexprGetNChildren(expr)) ); 686 for( c = 0; c < SCIPexprGetNChildren(expr); ++c ) 687 childrenbounds[c] = SCIPgetExprBoundsNonlinear(scip, SCIPexprGetChildren(expr)[c]); 688 689 /* call the reverse propagation callback of the expression handler */ 690 SCIP_CALL( SCIPcallExprReverseprop(scip, expr, bounds, childrenbounds, infeasible) ); 691 692 if( !*infeasible ) 693 { 694 for( c = 0; c < SCIPexprGetNChildren(expr); ++c ) 695 { 696 SCIP_CALL( SCIPtightenExprIntervalNonlinear(scip, SCIPexprGetChildren(expr)[c], childrenbounds[c], 697 infeasible, nreductions) ); 698 } 699 SCIPexprhdlrIncrementNDomainReductions(SCIPexprGetHdlr(expr), *nreductions); 700 } 701 702 SCIPfreeBufferArray(scip, &childrenbounds); 703 704 return SCIP_OKAY; 705 } 706 707 /** nonlinear handler copy callback */ 708 static 709 SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrDefault) 710 { /*lint --e{715}*/ 711 assert(targetscip != NULL); 712 assert(sourcenlhdlr != NULL); 713 assert(strcmp(SCIPnlhdlrGetName(sourcenlhdlr), NLHDLR_NAME) == 0); 714 715 SCIP_CALL( SCIPincludeNlhdlrDefault(targetscip) ); 716 717 return SCIP_OKAY; 718 } 719 720 /** callback to free expression specific data */ 721 static 722 SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataDefault) 723 { /*lint --e{715}*/ 724 assert(nlhdlrexprdata != NULL); 725 726 *nlhdlrexprdata = NULL; 727 728 return SCIP_OKAY; 729 } 730 731 /** includes default nonlinear handler in nonlinear constraint handler */ 732 SCIP_RETCODE SCIPincludeNlhdlrDefault( 733 SCIP* scip /**< SCIP data structure */ 734 ) 735 { 736 SCIP_NLHDLR* nlhdlr; 737 738 assert(scip != NULL); 739 740 SCIP_CALL( SCIPincludeNlhdlrNonlinear(scip, &nlhdlr, NLHDLR_NAME, NLHDLR_DESC, NLHDLR_DETECTPRIORITY, 741 NLHDLR_ENFOPRIORITY, nlhdlrDetectDefault, nlhdlrEvalAuxDefault, NULL) ); 742 assert(nlhdlr != NULL); 743 744 SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrDefault); 745 SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrFreeExprDataDefault); 746 SCIPnlhdlrSetSepa(nlhdlr, nlhdlrInitSepaDefault, NULL, nlhdlrEstimateDefault, NULL); 747 SCIPnlhdlrSetSollinearize(nlhdlr, nlhdlrSollinearizeDefault); 748 SCIPnlhdlrSetProp(nlhdlr, nlhdlrIntevalDefault, nlhdlrReversepropDefault); 749 750 return SCIP_OKAY; 751 } 752