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 exprcurv.c 26 * @ingroup OTHER_CFILES 27 * @brief functions to work with curvature (convex, concave, etc) 28 * @author Stefan Vigerske 29 * 30 * Declarations are in pub_expr.h 31 */ 32 33 #include "scip/pub_expr.h" 34 35 /** curvature names as strings */ 36 static 37 const char* curvnames[4] = 38 { 39 "unknown", 40 "convex", 41 "concave", 42 "linear" 43 }; 44 45 #ifdef NDEBUG 46 #undef SCIPexprcurvAdd 47 #undef SCIPexprcurvNegate 48 #undef SCIPexprcurvMultiply 49 #endif 50 51 /** gives curvature for a sum of two functions with given curvature */ 52 SCIP_EXPRCURV SCIPexprcurvAdd( 53 SCIP_EXPRCURV curv1, /**< curvature of first summand */ 54 SCIP_EXPRCURV curv2 /**< curvature of second summand */ 55 ) 56 { 57 return (SCIP_EXPRCURV) (curv1 & curv2); 58 } 59 60 /** gives the curvature for the negation of a function with given curvature */ 61 SCIP_EXPRCURV SCIPexprcurvNegate( 62 SCIP_EXPRCURV curvature /**< curvature of function */ 63 ) 64 { 65 switch( curvature ) 66 { 67 case SCIP_EXPRCURV_CONCAVE: 68 return SCIP_EXPRCURV_CONVEX; 69 70 case SCIP_EXPRCURV_CONVEX: 71 return SCIP_EXPRCURV_CONCAVE; 72 73 case SCIP_EXPRCURV_LINEAR: 74 case SCIP_EXPRCURV_UNKNOWN: 75 /* can return curvature, do this below */ 76 break; 77 78 default: 79 SCIPerrorMessage("unknown curvature status.\n"); 80 SCIPABORT(); 81 } 82 83 return curvature; 84 } 85 86 /** gives curvature for a functions with given curvature multiplied by a constant factor */ 87 SCIP_EXPRCURV SCIPexprcurvMultiply( 88 SCIP_Real factor, /**< constant factor */ 89 SCIP_EXPRCURV curvature /**< curvature of other factor */ 90 ) 91 { 92 if( factor == 0.0 ) 93 return SCIP_EXPRCURV_LINEAR; 94 if( factor > 0.0 ) 95 return curvature; 96 return SCIPexprcurvNegate(curvature); 97 } 98 99 /** gives curvature for base^exponent for given bounds and curvature of base-function and constant exponent */ 100 SCIP_EXPRCURV SCIPexprcurvPower( 101 SCIP_INTERVAL basebounds, /**< bounds on base function */ 102 SCIP_EXPRCURV basecurv, /**< curvature of base function */ 103 SCIP_Real exponent /**< exponent */ 104 ) 105 { 106 SCIP_Bool expisint; 107 108 assert(basebounds.inf <= basebounds.sup); 109 110 if( exponent == 0.0 ) 111 return SCIP_EXPRCURV_LINEAR; 112 113 if( exponent == 1.0 ) 114 return basecurv; 115 116 expisint = EPSISINT(exponent, 0.0); /*lint !e835*/ 117 118 /* if exponent is fractional, then power is not defined for a negative base 119 * thus, consider only positive part of basebounds 120 */ 121 if( !expisint && basebounds.inf < 0.0 ) 122 { 123 basebounds.inf = 0.0; 124 if( basebounds.sup < 0.0 ) 125 return SCIP_EXPRCURV_LINEAR; 126 } 127 128 /* if basebounds contains 0.0, consider negative and positive interval separately, if possible */ 129 if( basebounds.inf < 0.0 && basebounds.sup > 0.0 ) 130 { 131 SCIP_INTERVAL leftbounds; 132 SCIP_INTERVAL rightbounds; 133 134 /* something like x^(-2) may look convex on each side of zero, but is not convex on the whole interval 135 * due to the singularity at 0.0 */ 136 if( exponent < 0.0 ) 137 return SCIP_EXPRCURV_UNKNOWN; 138 139 SCIPintervalSetBounds(&leftbounds, basebounds.inf, 0.0); 140 SCIPintervalSetBounds(&rightbounds, 0.0, basebounds.sup); 141 142 return (SCIP_EXPRCURV) (SCIPexprcurvPower(leftbounds, basecurv, exponent) & SCIPexprcurvPower(rightbounds, basecurv, exponent)); 143 } 144 assert(basebounds.inf >= 0.0 || basebounds.sup <= 0.0); 145 146 /* (base^exponent)'' = exponent * ( (exponent-1) base^(exponent-2) (base')^2 + base^(exponent-1) base'' ) 147 * 148 * if base'' is positive, i.e., base is convex, then 149 * - for base > 0.0 and exponent > 1.0, the second deriv. is positive -> convex 150 * - for base < 0.0 and exponent > 1.0, we can't say (first and second summand opposite signs) 151 * - for base > 0.0 and 0.0 < exponent < 1.0, we can't say (first sommand negative, second summand positive) 152 * - for base > 0.0 and exponent < 0.0, we can't say (first and second summand opposite signs) 153 * - for base < 0.0 and exponent < 0.0 and even, the second deriv. is positive -> convex 154 * - for base < 0.0 and exponent < 0.0 and odd, the second deriv. is negative -> concave 155 * 156 * if base'' is negative, i.e., base is concave, then 157 * - for base > 0.0 and exponent > 1.0, we can't say (first summand positive, second summand negative) 158 * - for base < 0.0 and exponent > 1.0 and even, the second deriv. is positive -> convex 159 * - for base < 0.0 and exponent > 1.0 and odd, the second deriv. is negative -> concave 160 * - for base > 0.0 and 0.0 < exponent < 1.0, the second deriv. is negative -> concave 161 * - for base > 0.0 and exponent < 0.0, the second deriv. is positive -> convex 162 * - for base < 0.0 and exponent < 0.0, we can't say (first and second summand opposite signs) 163 * 164 * if base'' is zero, i.e., base is linear, then 165 * (base^exponent)'' = exponent * (exponent-1) base^(exponent-2) (base')^2 166 * - just multiply signs 167 */ 168 169 if( basecurv == SCIP_EXPRCURV_LINEAR ) 170 { 171 SCIP_Real sign; 172 173 /* base^(exponent-2) is negative, if base < 0.0 and exponent is odd */ 174 sign = exponent * (exponent - 1.0); 175 assert(basebounds.inf >= 0.0 || expisint); 176 if( basebounds.inf < 0.0 && ((int)exponent)%2 != 0 ) 177 sign *= -1.0; 178 assert(sign != 0.0); 179 180 return sign > 0.0 ? SCIP_EXPRCURV_CONVEX : SCIP_EXPRCURV_CONCAVE; 181 } 182 183 if( basecurv == SCIP_EXPRCURV_CONVEX ) 184 { 185 if( basebounds.sup <= 0.0 && exponent < 0.0 && expisint ) 186 return ((int)exponent)%2 == 0 ? SCIP_EXPRCURV_CONVEX : SCIP_EXPRCURV_CONCAVE; 187 if( basebounds.inf >= 0.0 && exponent > 1.0 ) 188 return SCIP_EXPRCURV_CONVEX ; 189 return SCIP_EXPRCURV_UNKNOWN; 190 } 191 192 if( basecurv == SCIP_EXPRCURV_CONCAVE ) 193 { 194 if( basebounds.sup <= 0.0 && exponent > 1.0 && expisint ) 195 return ((int)exponent)%2 == 0 ? SCIP_EXPRCURV_CONVEX : SCIP_EXPRCURV_CONCAVE; 196 if( basebounds.inf >= 0.0 && exponent < 1.0 ) 197 return exponent < 0.0 ? SCIP_EXPRCURV_CONVEX : SCIP_EXPRCURV_CONCAVE; 198 return SCIP_EXPRCURV_UNKNOWN; 199 } 200 201 return SCIP_EXPRCURV_UNKNOWN; 202 } 203 204 /** gives required curvature for base so that base^exponent has given curvature under given bounds on base and constant exponent 205 * 206 * returns curvature unknown if expected curvature cannot be obtained 207 */ 208 SCIP_EXPRCURV SCIPexprcurvPowerInv( 209 SCIP_INTERVAL basebounds, /**< bounds on base function */ 210 SCIP_Real exponent, /**< exponent, must not be 0 */ 211 SCIP_EXPRCURV powercurv /**< expected curvature for power */ 212 ) 213 { 214 SCIP_Bool expisint; 215 216 assert(basebounds.inf <= basebounds.sup); 217 assert(exponent != 0.0); 218 assert(powercurv != SCIP_EXPRCURV_UNKNOWN); 219 220 if( exponent == 1.0 ) 221 return powercurv; 222 223 /* power is usually never linear, now that exponent != 1 */ 224 if( powercurv == SCIP_EXPRCURV_LINEAR ) 225 return SCIP_EXPRCURV_UNKNOWN; 226 227 expisint = EPSISINT(exponent, 0.0); /*lint !e835*/ 228 229 /* if exponent is fractional, then power is only defined for a non-negative base 230 * boundtightening should have ensured this before calling this function, 231 * but sometimes this does not work and so we correct this here for us 232 */ 233 if( !expisint && basebounds.inf < 0.0 ) 234 { 235 basebounds.inf = 0.0; 236 if( basebounds.sup < 0.0 ) 237 return SCIP_EXPRCURV_UNKNOWN; 238 } 239 240 /* if basebounds contains 0.0, consider negative and positive interval separately, if possible */ 241 if( basebounds.inf < 0.0 && basebounds.sup > 0.0 ) 242 { 243 SCIP_INTERVAL leftbounds; 244 SCIP_INTERVAL rightbounds; 245 SCIP_EXPRCURV leftcurv; 246 SCIP_EXPRCURV rightcurv; 247 248 /* something like x^(-2) may look convex on each side of zero, but is not convex on the whole 249 * interval due to the singularity at 0.0 */ 250 if( exponent < 0.0 ) 251 return SCIP_EXPRCURV_UNKNOWN; 252 253 SCIPintervalSetBounds(&leftbounds, basebounds.inf, 0.0); 254 SCIPintervalSetBounds(&rightbounds, 0.0, basebounds.sup); 255 256 leftcurv = SCIPexprcurvPowerInv(leftbounds, exponent, powercurv); 257 rightcurv = SCIPexprcurvPowerInv(rightbounds, exponent, powercurv); 258 259 /* now need to intersect */ 260 if( leftcurv == SCIP_EXPRCURV_LINEAR ) 261 return rightcurv; 262 if( rightcurv == SCIP_EXPRCURV_LINEAR ) 263 return leftcurv; 264 if( leftcurv == SCIP_EXPRCURV_UNKNOWN || rightcurv == SCIP_EXPRCURV_UNKNOWN ) 265 return SCIP_EXPRCURV_UNKNOWN; 266 assert(leftcurv == SCIP_EXPRCURV_CONVEX || leftcurv == SCIP_EXPRCURV_CONCAVE); 267 assert(rightcurv == SCIP_EXPRCURV_CONVEX || rightcurv == SCIP_EXPRCURV_CONCAVE); 268 return SCIP_EXPRCURV_LINEAR; 269 } 270 assert(basebounds.inf >= 0.0 || basebounds.sup <= 0.0); 271 272 /* inverting the logic from SCIPexprcurvPower here */ 273 if( powercurv == SCIP_EXPRCURV_CONVEX ) 274 { 275 SCIP_Real sign; 276 277 if( basebounds.sup <= 0.0 && exponent < 0.0 && expisint && ((int)exponent)%2 == 0 ) 278 return SCIP_EXPRCURV_CONVEX; 279 if( basebounds.inf >= 0.0 && exponent > 1.0 ) 280 return SCIP_EXPRCURV_CONVEX; 281 if( basebounds.sup <= 0.0 && exponent > 1.0 && expisint && ((int)exponent)%2 == 0 ) 282 return SCIP_EXPRCURV_CONCAVE; 283 if( basebounds.inf >= 0.0 && exponent < 0.0 ) 284 return SCIP_EXPRCURV_CONCAVE; 285 286 /* base^(exponent-2) is negative, if base < 0.0 and exponent is odd */ 287 sign = exponent * (exponent - 1.0); 288 assert(basebounds.inf >= 0.0 || expisint); 289 if( basebounds.inf < 0.0 && ((int)exponent)%2 != 0 ) 290 sign *= -1.0; 291 assert(sign != 0.0); 292 293 if( sign > 0.0 ) 294 return SCIP_EXPRCURV_LINEAR; 295 } 296 else 297 { 298 SCIP_Real sign; 299 300 assert(powercurv == SCIP_EXPRCURV_CONCAVE); /* linear handled at top, unknown should not be the case */ 301 302 if( basebounds.sup <= 0.0 && exponent < 0.0 && expisint && ((int)exponent)%2 != 0 ) 303 return SCIP_EXPRCURV_CONVEX; 304 if( basebounds.sup <= 0.0 && exponent > 1.0 && expisint && ((int)exponent)%2 != 0 ) 305 return SCIP_EXPRCURV_CONCAVE; 306 if( basebounds.inf >= 0.0 && exponent < 1.0 && exponent >= 0.0 ) 307 return SCIP_EXPRCURV_CONCAVE; 308 309 /* base^(exponent-2) is negative, if base < 0.0 and exponent is odd */ 310 sign = exponent * (exponent - 1.0); 311 assert(basebounds.inf >= 0.0 || expisint); 312 if( basebounds.inf < 0.0 && ((int)exponent)%2 != 0 ) 313 sign *= -1.0; 314 assert(sign != 0.0); 315 316 if( sign < 0.0 ) 317 return SCIP_EXPRCURV_LINEAR; 318 } 319 320 return SCIP_EXPRCURV_UNKNOWN; 321 } 322 323 /** gives curvature for a monomial with given curvatures and bounds for each factor 324 * 325 * See Maranas and Floudas, Finding All Solutions of Nonlinearly Constrained Systems of Equations, JOGO 7, 1995 326 * for the categorization in the case that all factors are linear. 327 * 328 * Exponents can also be negative or rational. 329 */ 330 SCIP_EXPRCURV SCIPexprcurvMonomial( 331 int nfactors, /**< number of factors in monomial */ 332 SCIP_Real* exponents, /**< exponents in monomial, or NULL if all 1.0 */ 333 int* factoridxs, /**< indices of factors (but not exponents), or NULL if identity mapping */ 334 SCIP_EXPRCURV* factorcurv, /**< curvature of each factor */ 335 SCIP_INTERVAL* factorbounds /**< bounds of each factor */ 336 ) 337 { 338 SCIP_Real mult; 339 SCIP_Real e; 340 SCIP_INTERVAL bounds; 341 SCIP_EXPRCURV curv; 342 SCIP_EXPRCURV fcurv; 343 int nnegative; 344 int npositive; 345 SCIP_Real sum; 346 SCIP_Bool expcurvpos; 347 SCIP_Bool expcurvneg; 348 int j; 349 int f; 350 351 assert(nfactors >= 0); 352 assert(factorcurv != NULL || nfactors == 0); 353 assert(factorbounds != NULL || nfactors == 0); 354 355 if( nfactors == 0 ) 356 return SCIP_EXPRCURV_LINEAR; 357 358 if( nfactors == 1 ) 359 { 360 f = factoridxs != NULL ? factoridxs[0] : 0; 361 e = exponents != NULL ? exponents[0] : 1.0; 362 /* SCIPdebugMessage("monomial [%g,%g]^%g is %s\n", 363 factorbounds[f].inf, factorbounds[f].sup, e, 364 SCIPexprcurvGetName(SCIPexprcurvPower(factorbounds[f], factorcurv[f], e))); */ 365 return SCIPexprcurvPower(factorbounds[f], factorcurv[f], e); /*lint !e613*/ 366 } 367 368 mult = 1.0; 369 370 nnegative = 0; /* number of negative exponents */ 371 npositive = 0; /* number of positive exponents */ 372 sum = 0.0; /* sum of exponents */ 373 expcurvpos = TRUE; /* whether exp_j * f_j''(x) >= 0 for all factors (assuming f_j >= 0) */ 374 expcurvneg = TRUE; /* whether exp_j * f_j''(x) <= 0 for all factors (assuming f_j >= 0) */ 375 376 for( j = 0; j < nfactors; ++j ) 377 { 378 f = factoridxs != NULL ? factoridxs[j] : j; 379 if( factorcurv[f] == SCIP_EXPRCURV_UNKNOWN ) /*lint !e613*/ 380 return SCIP_EXPRCURV_UNKNOWN; 381 382 e = exponents != NULL ? exponents[j] : 1.0; 383 bounds = factorbounds[f]; /*lint !e613*/ 384 385 /* if argument is negative, then exponent should be integer; correct bounds if that doesn't hold */ 386 if( !EPSISINT(e, 0.0) && bounds.inf < 0.0 ) /*lint !e835*/ 387 { 388 bounds.inf = 0.0; 389 if( bounds.sup < 0.0 ) 390 return SCIP_EXPRCURV_UNKNOWN; 391 } 392 393 if( bounds.inf < 0.0 && bounds.sup > 0.0 ) 394 return SCIP_EXPRCURV_UNKNOWN; 395 396 if( e < 0.0 ) 397 ++nnegative; 398 else 399 ++npositive; 400 sum += e; 401 402 if( bounds.inf < 0.0 ) 403 { 404 /* flip j'th argument: (f_j)^(exp_j) = (-1)^(exp_j) (-f_j)^(exp_j) */ 405 406 /* -f_j has negated curvature of f_j */ 407 fcurv = SCIPexprcurvNegate(factorcurv[f]); /*lint !e613*/ 408 409 /* negate monomial, if exponent is odd, i.e., (-1)^(exp_j) = -1 */ 410 if( (int)e % 2 != 0 ) 411 mult *= -1.0; 412 } 413 else 414 { 415 fcurv = factorcurv[f]; /*lint !e613*/ 416 } 417 418 /* check if exp_j * fcurv is convex (>= 0) and/or concave */ 419 fcurv = SCIPexprcurvMultiply(e, fcurv); 420 if( !(fcurv & SCIP_EXPRCURV_CONVEX) ) 421 expcurvpos = FALSE; 422 if( !(fcurv & SCIP_EXPRCURV_CONCAVE) ) 423 expcurvneg = FALSE; 424 } 425 426 /* if all factors are linear, then a product f_j^exp_j with f_j >= 0 is convex if 427 * - all exponents are negative, or 428 * - all except one exponent j* are negative and exp_j* >= 1 - sum_{j!=j*}exp_j, but the latter is equivalent to sum_j exp_j >= 1 429 * further, the product is concave if 430 * - all exponents are positive and the sum of exponents is <= 1.0 431 * 432 * if factors are nonlinear, then we require additionally, that for convexity 433 * - each factor is convex if exp_j >= 0, or concave if exp_j <= 0, i.e., exp_j*f_j'' >= 0 434 * and for concavity, we require that 435 * - all factors are concave, i.e., exp_j*f_j'' <= 0 436 */ 437 438 if( nnegative == nfactors && expcurvpos ) 439 curv = SCIP_EXPRCURV_CONVEX; 440 else if( nnegative == nfactors-1 && EPSGE(sum, 1.0, 1e-9) && expcurvpos ) 441 curv = SCIP_EXPRCURV_CONVEX; 442 else if( npositive == nfactors && EPSLE(sum, 1.0, 1e-9) && expcurvneg ) 443 curv = SCIP_EXPRCURV_CONCAVE; 444 else 445 curv = SCIP_EXPRCURV_UNKNOWN; 446 curv = SCIPexprcurvMultiply(mult, curv); 447 448 return curv; 449 } 450 451 /** for a monomial with given bounds for each factor, gives condition on the curvature of each factor, 452 * so that monomial has a requested curvature, if possible 453 * 454 * @return whether `monomialcurv` can be achieved 455 */ 456 SCIP_Bool SCIPexprcurvMonomialInv( 457 SCIP_EXPRCURV monomialcurv, /**< desired curvature */ 458 int nfactors, /**< number of factors in monomial */ 459 SCIP_Real* exponents, /**< exponents in monomial, or NULL if all 1.0 */ 460 SCIP_INTERVAL* factorbounds, /**< bounds of each factor */ 461 SCIP_EXPRCURV* factorcurv /**< buffer to store required curvature of each factor */ 462 ) 463 { 464 int nnegative; 465 int npositive; 466 SCIP_INTERVAL bounds; 467 SCIP_Real e; 468 SCIP_Real sum; 469 int j; 470 471 assert(monomialcurv != SCIP_EXPRCURV_UNKNOWN); 472 assert(nfactors >= 1); 473 assert(factorbounds != NULL); 474 assert(factorcurv != NULL); 475 476 if( nfactors == 1 ) 477 { 478 factorcurv[0] = SCIPexprcurvPowerInv(factorbounds[0], exponents != NULL ? exponents[0] : 1.0, monomialcurv); 479 return factorcurv[0] != SCIP_EXPRCURV_UNKNOWN; 480 } 481 482 /* any decent monomial with at least 2 factors is not linear */ 483 if( monomialcurv == SCIP_EXPRCURV_LINEAR ) 484 return FALSE; 485 486 /* count positive and negative exponents, sum of exponents; flip negative factors */ 487 nnegative = 0; /* number of negative exponents */ 488 npositive = 0; /* number of positive exponents */ 489 sum = 0.0; /* sum of exponents */ 490 for( j = 0; j < nfactors; ++j ) 491 { 492 e = exponents != NULL ? exponents[j] : 1.0; 493 assert(e != 0.0); /* should have been simplified away */ 494 495 bounds = factorbounds[j]; 496 497 /* if argument is negative, then exponent should be integer 498 * if that didn't happen, consider argument as if non-negative 499 */ 500 if( !EPSISINT(e, 0.0) && bounds.inf < 0.0 ) /*lint !e835*/ 501 { 502 bounds.inf = 0.0; 503 if( bounds.sup < 0.0 ) 504 return FALSE; 505 } 506 507 /* mixed signs are bad */ 508 if( bounds.inf < 0.0 && bounds.sup > 0.0 ) 509 return FALSE; 510 511 if( e < 0.0 ) 512 ++nnegative; 513 else 514 ++npositive; 515 sum += e; 516 517 if( bounds.inf < 0.0 ) 518 { 519 /* flip j'th argument: (f_j)^(exp_j) = (-1)^(exp_j) (-f_j)^(exp_j) 520 * thus, negate monomial, if exponent is odd, i.e., (-1)^(exp_j) = -1 521 */ 522 if( (int)e % 2 != 0 ) 523 monomialcurv = SCIPexprcurvNegate(monomialcurv); 524 } 525 } 526 527 /* if all factors are linear, then a product f_j^exp_j with f_j >= 0 is convex if 528 * - all exponents are negative, or 529 * - all except one exponent j* are negative and exp_j* >= 1 - sum_{j!=j*}exp_j, but the latter is equivalent to sum_j exp_j >= 1 530 * further, the product is concave if 531 * - all exponents are positive and the sum of exponents is <= 1.0 532 * 533 * if factors are nonlinear, then we require additionally, that for convexity 534 * - each factor is convex if exp_j >= 0, or concave if exp_j <= 0, i.e., exp_j*f_j'' >= 0 535 * and for concavity, we require that 536 * - all factors are concave, i.e., exp_j*f_j'' <= 0 537 */ 538 539 if( monomialcurv == SCIP_EXPRCURV_CONVEX ) 540 { 541 if( nnegative < nfactors-1 ) /* at least two positive exponents */ 542 return FALSE; 543 if( nnegative < nfactors && !EPSGE(sum, 1.0, 1e-9) ) /* one negative exponent, but sum is not >= 1 */ 544 return FALSE; 545 546 /* monomial will be convex, if each factor is convex if exp_j >= 0, or concave if exp_j <= 0, i.e., exp_j*f_j'' >= 0 */ 547 for( j = 0; j < nfactors; ++j ) 548 { 549 e = exponents != NULL ? exponents[j] : 1.0; 550 551 /* if factor is negative, then factorcurv[j] need to be flipped, which we can also get by flipping e */ 552 if( factorbounds[j].inf < 0.0 && EPSISINT(e, 0.0) ) /*lint !e835*/ 553 e = -e; 554 if( e >= 0.0 ) 555 factorcurv[j] = SCIP_EXPRCURV_CONVEX; 556 else 557 factorcurv[j] = SCIP_EXPRCURV_CONCAVE; 558 } 559 } 560 else 561 { 562 assert(monomialcurv == SCIP_EXPRCURV_CONCAVE); 563 if( npositive < nfactors ) /* at least one negative exponent */ 564 return FALSE; 565 if( !EPSLE(sum, 1.0, 1e-9) ) /* sum is not <= 1 */ 566 return FALSE; 567 568 /* monomial will be concave, if each factor is concave */ 569 for( j = 0; j < nfactors; ++j ) 570 { 571 e = exponents != NULL ? exponents[j] : 1.0; 572 573 /* if factor is negative, then factorcurv[j] need to be flipped, i.e. convex */ 574 if( factorbounds[j].inf < 0.0 && EPSISINT(e, 0.0) ) /*lint !e835*/ 575 factorcurv[j] = SCIP_EXPRCURV_CONVEX; 576 else 577 factorcurv[j] = SCIP_EXPRCURV_CONCAVE; 578 } 579 } 580 581 return TRUE; 582 } 583 584 /** gives name as string for a curvature */ 585 const char* SCIPexprcurvGetName( 586 SCIP_EXPRCURV curv /**< curvature */ 587 ) 588 { 589 assert(0 <= curv && curv <= SCIP_EXPRCURV_LINEAR); /*lint !e685 !e2650 !e587 !e831 !e641 !e568*/ 590 591 return curvnames[curv]; 592 } 593