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 expr_var.c 26 * @ingroup DEFPLUGINS_EXPR 27 * @brief variable expression handler 28 * @author Stefan Vigerske 29 * @author Benjamin Mueller 30 * @author Felipe Serrano 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #include <string.h> 36 #include "scip/expr_var.h" 37 #include "scip/expr_sum.h" 38 39 #ifdef NDEBUG 40 #undef SCIPgetVarExprVar 41 #endif 42 43 #define EXPRHDLR_NAME "var" 44 #define EXPRHDLR_DESC "SCIP variable expression" 45 #define EXPRHDLR_PRECEDENCE 0 46 #define EXPRHDLR_HASHKEY SCIPcalcFibHash(22153.0) 47 48 /** translate from one value of infinity to another 49 * 50 * if val is >= infty1, then give infty2, else give val 51 */ 52 #define infty2infty(infty1, infty2, val) ((val) >= (infty1) ? (infty2) : (val)) 53 54 55 /** simplifies a variable expression 56 * 57 * We replace the variable when fixed by its value. 58 * If a variable is fixed, (multi)aggregated or more generally, inactive, we replace it with its active counterpart 59 * 60 * Implementation note: 61 * - we follow the general approach of the simplify, where we replace the var expression for its 62 * simplified expression only in the current parent. So if we see that there is any performance issue in the simplify 63 * we might have to revisit this decision. 64 * - we build the sum expression by appending variable expressions one at a time. This may be 65 * speed-up if we allocate memory for all the variable expressions and build the sum directly. 66 */ 67 static 68 SCIP_DECL_EXPRSIMPLIFY(simplifyVar) 69 { /*lint --e{715}*/ 70 SCIP_VAR* var; 71 SCIP_VAR** vars; 72 SCIP_Real* coefs; 73 SCIP_Real constant; 74 int nvars; 75 int varssize; 76 int i; 77 SCIP_EXPR* sumexpr; 78 79 assert(expr != NULL); 80 assert(simplifiedexpr != NULL); 81 82 var = SCIPgetVarExprVar(expr); 83 assert(var != NULL); 84 85 /* if var is active then there is nothing to simplify */ 86 if( SCIPvarIsActive(var) ) 87 { 88 *simplifiedexpr = expr; 89 /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */ 90 SCIPcaptureExpr(*simplifiedexpr); 91 return SCIP_OKAY; 92 } 93 94 /* var is not active; obtain active representation var = constant + sum coefs_i vars_i */ 95 varssize = 5; 96 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) ); 97 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, varssize) ); 98 99 vars[0] = var; 100 coefs[0] = 1.0; 101 constant = 0.0; 102 nvars = 1; 103 if( !SCIPvarIsOriginal(var) ) 104 { 105 int requsize; 106 107 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, coefs, &nvars, varssize, &constant, &requsize, TRUE) ); 108 109 if( requsize > varssize ) 110 { 111 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requsize) ); 112 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, requsize) ); 113 varssize = requsize; 114 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, coefs, &nvars, varssize, &constant, &requsize, TRUE) ); 115 assert(requsize <= nvars); 116 } 117 } 118 119 /* create expression for constant + sum coefs_i vars_i */ 120 SCIP_CALL( SCIPcreateExprSum(scip, &sumexpr, 0, NULL, NULL, constant, ownercreate, ownercreatedata) ); 121 122 for( i = 0; i < nvars; ++i ) 123 { 124 SCIP_EXPR* child; 125 126 SCIP_CALL( SCIPcreateExprVar(scip, &child, vars[i], ownercreate, ownercreatedata) ); 127 SCIP_CALL( SCIPappendExprSumExpr(scip, sumexpr, child, coefs[i]) ); 128 SCIP_CALL( SCIPreleaseExpr(scip, &child) ); 129 } 130 131 /* simplify since it might not really be a sum */ 132 SCIP_CALL( SCIPcallExprSimplify(scip, sumexpr, simplifiedexpr, ownercreate, ownercreatedata) ); 133 134 #ifdef SCIP_DEBUG 135 SCIPinfoMessage(scip, NULL, "expr_var simplify: <%s> := ", SCIPvarGetName(var)); 136 SCIPprintExpr(scip, *simplifiedexpr, NULL); 137 SCIPinfoMessage(scip, NULL, "\n"); 138 #endif 139 140 /* we cannot handle fixings to infinity at the moment (TODO we should) */ 141 assert(!SCIPisInfinity(scip, REALABS(constant))); 142 143 /* release no longer used sumexpr */ 144 SCIP_CALL( SCIPreleaseExpr(scip, &sumexpr) ); 145 146 /* free memory */ 147 SCIPfreeBufferArray(scip, &coefs); 148 SCIPfreeBufferArray(scip, &vars); 149 150 return SCIP_OKAY; 151 } 152 153 /** the order of two variable is given by their indices 154 * 155 * @note this is affected by permutations in the problem 156 */ 157 static 158 SCIP_DECL_EXPRCOMPARE(compareVar) 159 { /*lint --e{715}*/ 160 int index1; 161 int index2; 162 163 index1 = SCIPvarGetIndex(SCIPgetVarExprVar(expr1)); 164 index2 = SCIPvarGetIndex(SCIPgetVarExprVar(expr2)); 165 166 return index1 < index2 ? -1 : index1 == index2 ? 0 : 1; 167 } 168 169 /** expression handler copy callback */ 170 static 171 SCIP_DECL_EXPRCOPYHDLR(copyhdlrVar) 172 { /*lint --e{715}*/ 173 SCIP_CALL( SCIPincludeExprhdlrVar(scip) ); 174 175 return SCIP_OKAY; 176 } 177 178 /** expression data copy callback */ 179 static 180 SCIP_DECL_EXPRCOPYDATA(copydataVar) 181 { /*lint --e{715}*/ 182 SCIP_VAR* var; 183 184 assert(targetexprdata != NULL); 185 assert(sourceexpr != NULL); 186 187 /* copying into a different SCIP should be handled on the SCIPexprCopy() level (via mapexpr) */ 188 assert(targetscip == sourcescip); 189 190 var = SCIPgetVarExprVar(sourceexpr); 191 assert(var != NULL); 192 193 *targetexprdata = (SCIP_EXPRDATA*)var; 194 195 SCIP_CALL( SCIPcaptureVar(targetscip, var) ); 196 197 return SCIP_OKAY; 198 } 199 200 /** expression data free callback */ 201 static 202 SCIP_DECL_EXPRFREEDATA(freedataVar) 203 { /*lint --e{715}*/ 204 SCIP_EXPRDATA* exprdata; 205 206 assert(expr != NULL); 207 208 exprdata = SCIPexprGetData(expr); 209 assert(exprdata != NULL); 210 211 SCIP_CALL( SCIPreleaseVar(scip, (SCIP_VAR**)&exprdata) ); 212 213 SCIPexprSetData(expr, NULL); 214 215 return SCIP_OKAY; 216 } 217 218 /** expression print callback */ 219 static 220 SCIP_DECL_EXPRPRINT(printVar) 221 { /*lint --e{715}*/ 222 assert(expr != NULL); 223 assert(SCIPgetVarExprVar(expr) != NULL); 224 225 if( stage == SCIP_EXPRITER_ENTEREXPR ) 226 { 227 SCIPinfoMessage(scip, file, "<%s>", SCIPvarGetName(SCIPgetVarExprVar(expr))); 228 } 229 230 return SCIP_OKAY; 231 } 232 233 /** expression point evaluation callback */ 234 static 235 SCIP_DECL_EXPREVAL(evalVar) 236 { /*lint --e{715}*/ 237 assert(expr != NULL); 238 assert(SCIPgetVarExprVar(expr) != NULL); 239 240 *val = SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr)); 241 242 return SCIP_OKAY; 243 } 244 245 /** expression backward derivative evaluation callback */ 246 static 247 SCIP_DECL_EXPRBWDIFF(bwdiffVar) 248 { /*lint --e{715}*/ 249 /* this should never happen because variable expressions do not have children */ 250 return SCIP_INVALIDCALL; 251 } 252 253 /** expression forward derivative evaluation callback */ 254 static 255 SCIP_DECL_EXPRFWDIFF(fwdiffVar) 256 { /*lint --e{715}*/ 257 assert(expr != NULL); 258 assert(SCIPgetVarExprVar(expr) != NULL); 259 260 *dot = SCIPgetSolVal(scip, direction, SCIPgetVarExprVar(expr)); 261 262 return SCIP_OKAY; 263 } 264 265 /** expression derivative evaluation callback */ 266 static 267 SCIP_DECL_EXPRBWFWDIFF(bwfwdiffVar) 268 { /*lint --e{715}*/ 269 /* this should never happen because variable expressions do not have children */ 270 return SCIP_INVALIDCALL; 271 } 272 273 /** expression interval evaluation callback */ 274 static 275 SCIP_DECL_EXPRINTEVAL(intevalVar) 276 { /*lint --e{715}*/ 277 SCIP_VAR* var; 278 279 assert(expr != NULL); 280 281 var = SCIPgetVarExprVar(expr); 282 assert(var != NULL); 283 284 if( intevalvar != NULL ) 285 *interval = intevalvar(scip, var, intevalvardata); 286 else 287 { 288 SCIP_Real lb; 289 SCIP_Real ub; 290 291 lb = SCIPvarGetLbLocal(var); 292 ub = SCIPvarGetUbLocal(var); 293 294 SCIPintervalSetBounds(interval, /*lint !e666*/ 295 -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -lb), /*lint !e666*/ 296 infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, ub)); /*lint !e666*/ 297 } 298 299 return SCIP_OKAY; 300 } 301 302 /** variable hash callback */ 303 static 304 SCIP_DECL_EXPRHASH(hashVar) 305 { /*lint --e{715}*/ 306 SCIP_VAR* var; 307 308 assert(scip != NULL); 309 assert(expr != NULL); 310 assert(SCIPexprGetNChildren(expr) == 0); 311 assert(hashkey != NULL); 312 313 var = SCIPgetVarExprVar(expr); 314 assert(var != NULL); 315 316 *hashkey = EXPRHDLR_HASHKEY; 317 *hashkey ^= SCIPcalcFibHash((SCIP_Real)SCIPvarGetIndex(var)); 318 319 return SCIP_OKAY; 320 } 321 322 /** expression curvature detection callback */ 323 static 324 SCIP_DECL_EXPRCURVATURE(curvatureVar) 325 { /*lint --e{715}*/ 326 assert(scip != NULL); 327 assert(expr != NULL); 328 assert(success != NULL); 329 assert(SCIPexprGetNChildren(expr) == 0); 330 331 /* x -> x is linear, convex, and concave */ 332 *success = TRUE; 333 334 return SCIP_OKAY; 335 } 336 337 /** expression monotonicity detection callback */ 338 static 339 SCIP_DECL_EXPRMONOTONICITY(monotonicityVar) 340 { /*lint --e{715}*/ 341 assert(scip != NULL); 342 assert(expr != NULL); 343 assert(result != NULL); 344 assert(SCIPexprGetNChildren(expr) == 0); 345 346 *result = SCIP_MONOTONE_INC; 347 348 return SCIP_OKAY; 349 } 350 351 /** expression integrality detection callback */ 352 static 353 SCIP_DECL_EXPRINTEGRALITY(integralityVar) 354 { /*lint --e{715}*/ 355 assert(scip != NULL); 356 assert(expr != NULL); 357 assert(isintegral != NULL); 358 359 *isintegral = SCIPvarIsIntegral(SCIPgetVarExprVar(expr)); 360 361 return SCIP_OKAY; 362 } 363 364 /** creates the handler for variable expression and includes it into SCIP */ 365 SCIP_RETCODE SCIPincludeExprhdlrVar( 366 SCIP* scip /**< SCIP data structure */ 367 ) 368 { 369 SCIP_EXPRHDLR* exprhdlr; 370 371 SCIP_CALL( SCIPincludeExprhdlr(scip, &exprhdlr, EXPRHDLR_NAME, EXPRHDLR_DESC, EXPRHDLR_PRECEDENCE, evalVar, NULL) ); 372 assert(exprhdlr != NULL); 373 374 SCIPexprhdlrSetCopyFreeHdlr(exprhdlr, copyhdlrVar, NULL); 375 SCIPexprhdlrSetCopyFreeData(exprhdlr, copydataVar, freedataVar); 376 SCIPexprhdlrSetSimplify(exprhdlr, simplifyVar); 377 SCIPexprhdlrSetCompare(exprhdlr, compareVar); 378 SCIPexprhdlrSetPrint(exprhdlr, printVar); 379 SCIPexprhdlrSetIntEval(exprhdlr, intevalVar); 380 SCIPexprhdlrSetHash(exprhdlr, hashVar); 381 SCIPexprhdlrSetDiff(exprhdlr, bwdiffVar, fwdiffVar, bwfwdiffVar); 382 SCIPexprhdlrSetCurvature(exprhdlr, curvatureVar); 383 SCIPexprhdlrSetMonotonicity(exprhdlr, monotonicityVar); 384 SCIPexprhdlrSetIntegrality(exprhdlr, integralityVar); 385 386 return SCIP_OKAY; 387 } 388 389 /** creates a variable expression */ 390 SCIP_RETCODE SCIPcreateExprVar( 391 SCIP* scip, /**< SCIP data structure */ 392 SCIP_EXPR** expr, /**< pointer where to store expression */ 393 SCIP_VAR* var, /**< variable to be stored */ 394 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 395 void* ownercreatedata /**< data to pass to ownercreate */ 396 ) 397 { 398 SCIP_EXPRDATA* exprdata; 399 400 assert(expr != NULL); 401 assert(var != NULL); 402 403 /* capture the variable so that it doesn't disappear while the expr still points to it */ 404 SCIP_CALL( SCIPcaptureVar(scip, var) ); 405 406 exprdata = (SCIP_EXPRDATA*)var; 407 408 SCIP_CALL( SCIPcreateExpr(scip, expr, SCIPgetExprhdlrVar(scip), exprdata, 0, NULL, ownercreate, ownercreatedata) ); 409 410 return SCIP_OKAY; 411 } 412 413 /* from pub_expr.h */ 414 415 /** gets the variable of a variable expression */ 416 SCIP_VAR* SCIPgetVarExprVar( 417 SCIP_EXPR* expr /**< variable expression */ 418 ) 419 { 420 assert(expr != NULL); 421 assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0); 422 assert(SCIPexprGetData(expr) != NULL); 423 424 return (SCIP_VAR*)SCIPexprGetData(expr); 425 } 426