expr.c
Go to the documentation of this file.
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 63 #ifdef SCIP_DISABLED_CODE /* this macro is currently not used, which offends lint, so disable it */ 111 /* calculate the size with this loop, such that the resulting numbers are always the same (-> block memory) */ 130 /** checks if a given new lower bound is tighter (w.r.t. given bound strengthening epsilon) than the old one (copied from scip/set.c) */ 150 /** checks if a given new upper bound is tighter (w.r.t. given bound strengthening epsilon) than the old one (copied from scip/set.c) */ 235 /** gives curvature for base^exponent for given bounds and curvature of base-function and constant exponent */ 264 /* if basebounds contains 0.0, consider negative and positive interval separately, if possible */ 270 /* something like x^(-2) may look convex on each side of zero, but is not convex on the whole interval due to the singularity at 0.0 */ 277 return (SCIP_EXPRCURV) (SCIPexprcurvPower(leftbounds, basecurv, exponent) & SCIPexprcurvPower(rightbounds, basecurv, exponent)); 281 /* (base^exponent)'' = exponent * ( (exponent-1) base^(exponent-2) (base')^2 + base^(exponent-1) base'' ) 286 * - for base > 0.0 and 0.0 < exponent < 1.0, we can't say (first sommand negative, second summand positive) 292 * - for base > 0.0 and exponent > 1.0, we can't say (first summand positive, second summand negative) 341 * See Maranas and Floudas, Finding All Solutions of Nonlinearly Constrained Systems of Equations, JOGO 7, 1995 433 * - 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 498 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*quadraticdata)->lincoefs, lincoefs, nchildren) ); 503 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*quadraticdata)->quadelems, quadelems, nquadelems) ); 600 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &monomialdata->childidxs, monomialdata->factorssize, newsize) ); 601 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &monomialdata->exponents, monomialdata->factorssize, newsize) ); 617 SCIP_Bool copymonomials /**< whether to copy monomials, or copy only given pointers, in which case polynomialdata assumes ownership of monomial structure */ 644 monomials[i]->coef, monomials[i]->nfactors, monomials[i]->childidxs, monomials[i]->exponents) ); /*lint !e613*/ 649 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, monomials, nmonomials) ); 675 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, (*polynomialdata)->monomialssize) ); 680 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &(*polynomialdata)->monomials[i], sourcepolynomialdata->monomials[i]->coef, 681 sourcepolynomialdata->monomials[i]->nfactors, sourcepolynomialdata->monomials[i]->childidxs, sourcepolynomialdata->monomials[i]->exponents) ); 715 BMSfreeBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, (*polynomialdata)->monomialssize); 733 ensureBlockMemoryArraySize(blkmem, &polynomialdata->monomials, &polynomialdata->monomialssize, minsize); 758 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials + nmonomials) ); 766 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials + i], 767 monomials[i]->coef, monomials[i]->nfactors, monomials[i]->childidxs, monomials[i]->exponents) ); /*lint !e613*/ 772 BMScopyMemoryArray(&polynomialdata->monomials[polynomialdata->nmonomials], monomials, nmonomials); /*lint !e866*/ 806 SCIPsortPtr((void**)polynomialdata->monomials, monomialdataCompare, polynomialdata->nmonomials); 832 /* merge monomials by adding their coefficients, eliminate monomials with no factors or zero coefficient*/ 869 if( monomialdataCompare((void*)polynomialdata->monomials[i], (void*)polynomialdata->monomials[i+offset+1]) != 0 ) 930 SCIPexprChgMonomialCoef(polynomialdata->monomials[i], polynomialdata->monomials[i]->coef * factor); 960 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i], factor, childmap) ); 966 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials+1) ); 967 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials], polynomialdata->constant, 0, NULL, NULL) ); 968 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[polynomialdata->nmonomials], factor, childmap) ); 1006 SCIP_CALL( polynomialdataMultiplyByMonomial(blkmem, polynomialdata, factordata->monomials[0], childmap) ); 1013 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials+1) ); 1014 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials], polynomialdata->constant, 0, NULL, NULL) ); 1020 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials * (factordata->nmonomials + (factordata->constant == 0.0 ? 0 : 1))) ); 1028 assert(polynomialdata->nmonomials + orignmonomials <= polynomialdata->monomialssize); /* reallocating in polynomialdataAddMonomials would make the polynomialdata->monomials invalid, so assert that above the monomials array was made large enough */ 1029 SCIP_CALL( polynomialdataAddMonomials(blkmem, polynomialdata, orignmonomials, polynomialdata->monomials, TRUE) ); 1035 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i1], factordata->monomials[i2], childmap) ); 1050 SCIPexprChgMonomialCoef(polynomialdata->monomials[i1], polynomialdata->monomials[i1]->coef * factordata->constant); 1058 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i1], factordata->monomials[i2], childmap) ); 1178 int maxexpansionexponent,/**< maximal exponent for which polynomials (with > 1 summands) are expanded */ 1205 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && factorpolynomial->constant < 0.0 ) /*lint !e835*/ 1207 /* if polynomial is a negative constant and our exponent is not integer, then cannot do expansion */ 1208 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n", factorpolynomial->constant, monomial->exponents[factorpos]); 1241 /* if coefficient of monomial is negative and our exponent is not integer, then do not do expansion 1242 * @todo the only case where this could make sense is if the factors can be negative, i.e., when we have negative arguments with an odd exponent: (-x^a)^b = (-x)^(ab) for a odd 1249 /* @todo if there is an even number of factors in factormonomial that are negative, then they always multiply to something positive 1252 * MINLPLib instances tls2,4,6 are examples where we are loosing here (do not recognize convexity) 1259 SCIP_CALL( monomialdataEnsureFactorsSize(blkmem, monomial, monomial->nfactors + factormonomial->nfactors) ); 1264 /* can do this because monomial->exponents[factorpos] is assumed to be integer or factormonomial has positive coefficient and only one factor 1265 * thus, if factormonomial->exponents[i] is fractional, then we can assume that it's argument is positive 1286 /* if exponent is negative or fractional and the polynomial is not just a monomial, then we cannot do expansion */ 1287 if( !EPSISINT(monomial->exponents[factorpos], 0.0) || monomial->exponents[factorpos] < 0.0 ) /*lint !e835*/ 1301 * that is, assume monomial is f1^a1 f2^a2 ... and we want to expand f1 = (g11^beta11 g12^beta12... + g21^beta21 g22^beta22 ... + ...) 1302 * then we do this only if all ai and all beta are > 0.0 and a1 max(beta11+beta12+..., beta21+beta22+..., ...) + a2 + ... < maxexpansionexponent 1305 if( maxexpansionexponent < INT_MAX && (monomial->nfactors > 1 || monomial->exponents[factorpos] != 1.0) ) 1332 SCIPdebugMessage("skip expansion because %d'th factor in %d'th monomial of factorpolynomial is negative\n", i, j); 1341 SCIPdebugMessage("skip expansion because degree of %d'th monomial would yield degree %g > max = %d in expansion\n", 1354 SCIP_CALL( polynomialdataPower(blkmem, factorpolynomialcopy, (int)EPSFLOOR(monomial->exponents[factorpos], 0.0)) ); /*lint !e835*/ 1371 polynomialdata->monomials[monomialpos] = polynomialdata->monomials[polynomialdata->nmonomials-1]; 1376 SCIP_CALL( polynomialdataAddMonomials(blkmem, polynomialdata, factorpolynomialcopy->nmonomials, factorpolynomialcopy->monomials, FALSE) ); 1390 /** a default implementation of expression interval evaluation that always gives a correct result */ 1399 /** a default implementation of expression curvature check that always gives a correct result */ 1674 * if both nominator and denominator are not constant, then quotient may not be convex nor concave 2104 /* erf and erfi do not seem to exist on every system, and we cannot really handle them anyway, so they are currently disabled */ 2411 * if only one factor is not constant, then product is curvature of this factor, multiplied by sign of product of remaining factors 2509 /* for a linear expression, we need to copy the array that holds the coefficients and constant term */ 2511 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &targetdata, (SCIP_Real*)opdatasource.data, nchildren + 1) ); /*lint !e866*/ 2564 *result += quadelems->coef * argvals[quadelems->idx1] * argvals[quadelems->idx2]; /*lint !e613*/ 2636 SCIPdebugMessage("%g x^2 + %g y^2 + %g x y + %g x + %g y = [%g,%g] for x = [%g,%g], y = [%g,%g]\n", 2638 result->inf, result->sup, argvals[0].inf, argvals[0].sup, argvals[1].inf, argvals[1].sup); /*lint !e613*/ 2650 /* for each argument, we collect it's linear index from lincoefs, it's square coefficients and all factors from bilinear terms 2659 /* there are no quadratic terms with argidx in its first argument, that should be easy to handle */ 2680 SCIPintervalMulScalar(infinity, &tmp, argvals[quadelems[i].idx2], quadelems[i].coef); /*lint !e613*/ 2742 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef * argbounds[quadelems[i].idx1].inf, argcurv[quadelems[i].idx2])); 2747 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef * argbounds[quadelems[i].idx2].inf, argcurv[quadelems[i].idx1])); 2752 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef, SCIPexprcurvPower(argbounds[quadelems[i].idx1], argcurv[quadelems[i].idx1], 2.0))); 2777 sourcedata->constant, nchildren, sourcedata->lincoefs, sourcedata->nquadelems, sourcedata->quadelems) ); 3019 /* we assume that some simplifier was running, so that monomials do not have constants in their factors and such that all factors are different 3023 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(monomial->coef, SCIPexprcurvMonomial(monomial->nfactors, monomial->exponents, monomial->childidxs, argcurv, argbounds))); 3086 SCIP_CALL( exprdata->inteval(infinity, exprdata->userdata, nargs, argvals, result, NULL, NULL) ); 3090 /* if user does not provide interval evaluation, then return a result that is always correct */ 3111 /* if user does not provide curvature check, then return unknown (which is handled like indefinite) */ 3137 SCIP_CALL( exprdatasource->copydata(blkmem, nchildren, exprdatasource->userdata, &exprdatatarget->userdata) ); 3182 SCIP_DECL_EXPRCOPYDATA ((*copydata)); /**< expression data copy function, or NULL to only opdata union */ 3183 SCIP_DECL_EXPRFREEDATA ((*freedata)); /**< expression data free function, or NULL if nothing to free */ 3188 /** table containing for each operand the name, the number of children, and some evaluation functions */ 3219 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, 3220 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, 3221 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, 3225 { "linear", -2, exprevalLinear, exprevalIntLinear, exprcurvLinear, exprCopyDataLinear, exprFreeDataLinear }, 3226 { "quadratic", -2, exprevalQuadratic, exprevalIntQuadratic, exprcurvQuadratic, exprCopyDataQuadratic, exprFreeDataQuadratic }, 3227 { "polynomial", -2, exprevalPolynomial, exprevalIntPolynomial, exprcurvPolynomial, exprCopyDataPolynomial, exprFreeDataPolynomial }, 3228 { "user", -2, exprevalUser, exprevalIntUser, exprcurvUser, exprCopyDataUser, exprFreeDataUser } 3290 /** tries to convert a given (operator,operatordata) pair into a polynomial operator with corresponding data 3627 SCIP_CALL( polynomialdataCreate(blkmem, &polynomialdata, 0, NULL, lineardata[nchildren], FALSE) ); 3669 SCIP_CALL( polynomialdataCreate(blkmem, &polynomialdata, 0, NULL, quaddata->constant, FALSE) ); 3671 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, (quaddata->lincoefs != NULL ? nchildren : 0) + quaddata->nquadelems) ); 3807 /* polynomial simplification and monomial merging should ensure that monomial i corresponds to child i and that there are not unused children */ 3811 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == 1.0 && polynomialdata->monomials[1]->coef == 1.0 ) 3828 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == 1.0 && polynomialdata->monomials[1]->coef == -1.0 ) 3845 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == -1.0 && polynomialdata->monomials[1]->coef == 1.0 ) 3895 * that monomials are ordered according to the child index, and that constant monomials have been removed 3917 if( maxdegree == 2 && (polynomialdata->nmonomials > 1 || polynomialdata->constant != 0.0 || polynomialdata->monomials[0]->coef != 1.0) ) 3919 /* polynomial is quadratic expression with more than one summand or with a constant or a square or bilinear term with coefficient != 1.0, so turn into SCIP_EXPR_QUADRATIC */ 3924 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &quaddata->quadelems, polynomialdata->nmonomials - nlinmonomials) ); 3940 assert(polynomialdata->monomials[i]->nfactors == 1 || polynomialdata->monomials[i]->nfactors == 2); 3947 quaddata->lincoefs[polynomialdata->monomials[i]->childidxs[0]] += polynomialdata->monomials[i]->coef; 3966 quaddata->quadelems[quadelemidx].idx1 = MIN(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]); 3967 quaddata->quadelems[quadelemidx].idx2 = MAX(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]); 3982 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 1 && polynomialdata->monomials[0]->coef == 1.0 ) 4072 if( monomial->nfactors == 2 && monomial->exponents[0] == 1.0 && monomial->exponents[1] == -1.0 ) 4084 if( monomial->nfactors == 2 && monomial->exponents[0] == -1.0 && monomial->exponents[1] == 1.0 ) 4106 /** adds copies of expressions to the array of children of a sum, product, linear, quadratic, or polynomial expression 4108 * For a sum or product expression, this corresponds to add additional summands and factors, resp. 4110 * For a quadratic or polynomial expression, only the children array may be enlarged, the expression itself remains the same. 4118 SCIP_Bool comparechildren, /**< whether to compare expressions with already existing children (no effect for sum and product) */ 4120 int* childmap /**< array where to store mapping of indices from exprs to children array in expr, or NULL if not of interest */ 4127 assert(expr->op == SCIP_EXPR_SUM || expr->op == SCIP_EXPR_PRODUCT || expr->op == SCIP_EXPR_LINEAR || expr->op == SCIP_EXPR_QUADRATIC || expr->op == SCIP_EXPR_POLYNOMIAL); 4138 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) ); 4141 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren + i], exprs[i]) ); /*lint !e613*/ 4159 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) ); 4167 if( expr->children[j] != NULL && SCIPexprAreEqual(expr->children[j], exprs[i], eps) ) /*lint !e613*/ 4176 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren], exprs[i]) ); /*lint !e613*/ 4195 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, orignchildren + nexprs, expr->nchildren) ); 4203 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, orignchildren + 1, expr->nchildren + 1) ); 4215 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data->lincoefs, orignchildren, expr->nchildren) ); 4216 BMSclearMemoryArray(&data->lincoefs[orignchildren], expr->nchildren - orignchildren); /*lint !e866*/ 4362 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, lastnonnull+1) ); 4424 * exprsimplifyConvertToPolynomials should have been called before to eliminate simple polynomial operands. 4432 int maxexpansionexponent/**< maximal exponent for which we still expand non-monomial polynomials */ 4441 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr->children[i], eps, maxexpansionexponent) ); 4471 if( (expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) || 4477 /* since child0 has no children and it's polynomial was flattened, it should have no monomials */ 4478 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0); 4502 if( ((expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) || expr->children[0]->op == SCIP_EXPR_CONST) && 4503 ((expr->children[1]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[1]) == 0) || expr->children[1]->op == SCIP_EXPR_CONST) ) 4508 /* since children have no children and it's polynomial was flattened, it should have no monomials */ 4509 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0); 4510 assert(expr->children[1]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[1]) == 0); 4563 * thereby allowing some expansions of polynomials that may not be possible otherwise, e.g., turning c0*c1 with c0=quadratic and c1=constant into a single monomial 4591 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */ 4606 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && SCIPexprGetOpReal(expr->children[i]) < 0.0 ) /*lint !e835*/ 4609 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n", 4664 SCIP_CALL( exprsimplifyAddChildren(blkmem, expr, expr->children[i]->nchildren, expr->children[i]->children, TRUE, eps, childmap) ); 4674 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */ 4689 SCIP_CALL( polynomialdataExpandMonomialFactor(blkmem, messagehdlr, polynomialdata, j, factorpos, 4690 (SCIP_EXPRDATA_POLYNOMIAL*)expr->children[i]->data.data, childmap, maxexpansionexponent, &success) ); 4701 /* expansion may remove monomials[j], move a monomial from the end to position j, or add new monomials to the end of polynomialdata 4762 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part */ 4826 if( childusage[childidx] == 1 && varsusage[SCIPexprGetOpIndex(expr->children[childidx])] == 1 ) 4828 /* if the child expression is not used in another monomial (which would due to merging be not linear) 4875 SCIP_CALL( exprUnconvertPolynomial(blkmem, &expr->op, &expr->data, expr->nchildren, (void**)expr->children) ); 4888 * Creates a new variable index if variable not seen before, updates varnames and vartable structures. 4897 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */ 4899 const char* varnameendptr /**< if a <varname> should be parsed, set this to NULL. Then, str points to the '<' 4927 SCIPerrorMessage("Variable name %.*s is too long for buffer in exprparseReadVariable.\n", namelength, str); 4979 /** if str[0] points to an opening parenthesis, this function sets endptr to point to the matching closing bracket in str 5009 SCIPerrorMessage("unable to find closing parenthesis in unbalanced expression %.*s\n", length, str); 5046 SCIPerrorMessage("unable to find separating comma in unbalanced expression %.*s\n", length, str); 5064 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */ 5091 SCIPdebugMessage("exprParse (%i): parsing %.*s\n", recursiondepth, (int) (lastchar-str + 1), str); 5104 while( subexpptr != lastchar && !(nopenbrackets == 0 && (subexpptr[0] == '+' || subexpptr[0] == '-') && subexpptr != str) ) 5115 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str, (int) ((subexpptr - 1) - str + 1), subexpptr - 1, nvars, varnames, vartable, recursiondepth + 1) ); 5119 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, subexpptr , (int) (lastchar - (subexpptr ) + 1), lastchar, nvars, varnames, vartable, recursiondepth + 1) ); 5122 * we always use add, because we leave the operator between the found expressions in the second argument 5123 * this way, we do not have to worry about ''minus brackets'' in the case of more then two summands: 5155 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, subexpptr, subexplength, subexpendptr, nvars, varnames, vartable, recursiondepth + 1) ); 5158 else if( isdigit((unsigned char)str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit((unsigned char)str[1])) ) 5172 if( str[0] != '*' && str[0] != '/' && str[0] != '+' && str[0] != '-' && str[0] != '/' && str[0] != '^' ) 5176 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, str, (int)(lastchar - str) + 1, lastchar, nvars, varnames, vartable, recursiondepth + 1) ); 5200 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames, vartable, recursiondepth + 1) ); 5219 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames, vartable, recursiondepth + 1) ); 5266 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames, vartable, recursiondepth + 1) ); 5272 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) ) 5300 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames, vartable, recursiondepth + 1) ); 5306 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) ) 5330 /* check for a variable, that was not recognized earlier because somebody omitted the '<' and '>' we need for 5336 /* allow only variable names containing characters, digits, hash marks, and underscores here */ 5340 SCIP_CALL( exprparseReadVariable(blkmem, &varnamestartptr, expr, nvars, varnames, vartable, 1.0, str) ); 5361 SCIPerrorMessage("error finding first expression in \"%.*s\" took us outside of given subexpression length\n", length, strstart); 5391 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str + 1, endptr - str - 1, endptr -1, nvars, varnames, vartable, recursiondepth + 1) ); 5398 else if( isdigit((unsigned char)str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit((unsigned char)str[1])) ) 5421 SCIP_CALL( SCIPexprCreate(blkmem, expr, SCIP_EXPR_INTPOWER, arg1, (int)SCIPexprGetOpReal(arg2)) ); 5444 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames, vartable, recursiondepth + 1) ); 5500 /* if there is a part of the string left to be parsed, we assume that this as a multiplication */ 5510 SCIPdebugMessage("No operator found, assuming a multiplication before %.*s\n", (int) (lastchar - str + 1), str); 5513 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames, vartable, recursiondepth + 1) ); 5677 /* the coefficients are stored in the first nchildren elements of the array stored as expression data */ 6006 SCIPerrorMessage("cannot create complex expression linear, quadratic, polynomial, or user with SCIPexprCreate\n"); 6036 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*targetexpr)->children, sourceexpr->nchildren) ); 6046 assert((*targetexpr)->children == NULL); /* otherwise, sourceexpr->children was not NULL, which is wrong */ 6054 SCIP_CALL( exprOpTable[sourceexpr->op].copydata(blkmem, sourceexpr->nchildren, sourceexpr->data, &(*targetexpr)->data) ); 6119 /** creates an expression from the addition of two given expression, with coefficients, and a constant 6121 * The given expressions may be modified or freed, otherwise it will be used a child expression. 6222 if( SCIPexprGetOperator(term1) == SCIP_EXPR_LINEAR && SCIPexprGetOperator(term2) == SCIP_EXPR_LINEAR ) 6228 SCIP_CALL( SCIPexprAddToLinear(blkmem, term1, SCIPexprGetNChildren(term2), SCIPexprGetLinearCoefs(term2), SCIPexprGetChildren(term2), SCIPexprGetLinearConstant(term2) + constant) ); 6279 * The given expressions may be modified or freed, otherwise it will be used a child expression. 6379 /** creates a SCIP_EXPR_LINEAR expression that is (affine) linear in its children: constant + sum_i coef_i child_i */ 6404 /* we store the coefficients and the constant in a single array and make this our operand data */ 6447 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nchildren) ); 6451 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, expr->nchildren + 1, expr->nchildren + nchildren + 1) ); 6461 /** creates a SCIP_EXPR_QUADRATIC expression: constant + sum_i coef_i child_i + sum_i coef_i child1_i child2_i */ 6488 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) ); 6509 /** creates a SCIP_EXPR_POLYNOMIAL expression from an array of monomials: constant + sum_i monomial_i */ 6536 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) ); 6561 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, nmonomials, monomials, copymonomials) ); 6607 SCIP_CALL( polynomialdataMultiplyByMonomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, factor, childmap) ); 6615 * Children of factor need to be children of expr already, w.r.t. an optional mapping of child indices. 6653 SCIP_CALL( polynomialdataMultiplyByPolynomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, (SCIP_EXPRDATA_POLYNOMIAL*)factor->data.data, childmap) ); 6674 SCIP_CALL( polynomialdataPower(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, exponent) ); 6679 /** merges monomials in a polynomial expression that differ only in coefficient into a single monomial 6694 polynomialdataMergeMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, eps, mergefactors); 6759 BMScopyMemoryArray(&monomial->childidxs[monomial->nfactors], childidxs, nfactors); /*lint !e866*/ 6760 BMScopyMemoryArray(&monomial->exponents[monomial->nfactors], exponents, nfactors); /*lint !e866*/ 6786 SCIP_CALL( SCIPexprAddMonomialFactors(blkmem, monomial, factor->nfactors, factor->childidxs, factor->exponents) ); 6864 while( i+offset+1 < monomial->nfactors && monomial->childidxs[i] == monomial->childidxs[i+offset+1] ) 6936 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->childidxs, childidxs, nfactors) ); 6949 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->exponents, exponents, nfactors) ); 7011 * Note that if the factors have not been merged, the position of some factor corresponding to a given child is given. 7037 SCIP_EXPRINTCAPABILITY evalcapability, /**< capability of evaluation functions (partially redundant, currently) */ 7039 SCIP_DECL_USEREXPRINTEVAL ((*inteval)), /**< interval evaluation function, or NULL if not implemented */ 7041 SCIP_DECL_USEREXPRPROP ((*prop)), /**< interval propagation function, or NULL if not implemented */ 7042 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */ 7043 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */ 7044 SCIP_DECL_USEREXPRFREEDATA ((*freedata)) /**< expression data free function, or NULL if nothing to free */ 7055 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */ 7056 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */ 7214 else if( expr->data.dbl > 0.0 && (int)expr->data.dbl == expr->data.dbl ) /* natural exponent gives polynomial again */ /*lint !e777*/ 7343 /* if no linear or no quadratic coefficient with current child on first position, then nothing to do */ 7355 while( quadidx < quadraticdata->nquadelems && quadraticdata->quadelems[quadidx].idx1 == childidx ) 7366 SCIP_CALL( SCIPexprGetMaxDegree(expr->children[quadraticdata->quadelems[quadidx].idx2], &child2) ); 7406 /* if the exponent of the factor is not a natural number and the child is not constant (degree 0), 7408 if( child1 != 0 && (monomialdata->exponents[j] < 0.0 || (int)monomialdata->exponents[j] != monomialdata->exponents[j]) ) 7487 return SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps) && SCIPexprAreEqual(expr1->children[1], expr2->children[1], eps); 7505 return EPSEQ(expr1->data.dbl, expr2->data.dbl, eps) && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps); 7508 return expr1->data.intval == expr2->data.intval && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps); 7663 * If linear variables are split off, expression interpreter data, if stored in the tree, is freed. 7670 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */ 7672 int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */ 7673 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */ 7691 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr, eps, maxexpansionexponent) ); 7700 SCIP_CALL( exprsimplifySeparateLinearFromPolynomial(blkmem, expr, eps, nvars, nlinvars, linidxs, lincoefs) ); 7720 SCIP_Real* varvals, /**< values for variables, can be NULL if the expression operand is not a variable */ 7721 SCIP_Real* param, /**< values for parameters, can be NULL if the expression operand is not a parameter */ 7730 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, argvals, varvals, param, val) ); 7739 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */ 7765 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, buf, varvals, param, val) ); 7780 SCIP_INTERVAL* argvals, /**< interval values for children, can be NULL if the expression has no children */ 7781 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */ 7782 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */ 7791 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, argvals, varvals, param, val) ); 7800 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */ 7801 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */ 7822 SCIP_CALL( SCIPexprEvalInt(expr->children[i], infinity, varvals, param, &buf[i]) ); /*lint !e644*/ 7827 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, buf, varvals, param, val) ); 7856 SCIP_CALL( exprdata->eval(exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) ); 7868 SCIP_INTERVAL* hessian /**< buffer to store values of full Hessian, or NULL if not requested */ 7888 SCIP_CALL( exprdata->inteval(infinity, exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) ); 7899 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */ 7930 SCIP_CALL( SCIPexprCheckCurvature(expr->children[i], infinity, varbounds, param, &childcurv[i], &childbounds[i]) ); /*lint !e644*/ 7939 SCIP_CALL( exprOpTable[expr->op].curv(infinity, expr->data, expr->nchildren, childbounds, childcurv, curv) ); 7940 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, childbounds, varbounds, param, bounds) ); 7952 /** under-/overestimates a user expression w.r.t. to given values and bounds for children expressions */ 7959 SCIP_Real* coeffs, /**< buffer to store the linear coefficients for each child expression that gives a valid under-/overestimator */ 7960 SCIP_Real* constant, /**< buffer to store the constant value of the linear under-/overestimator */ 7975 SCIP_CALL( exprdata->estimate(infinity, exprdata->userdata, expr->nchildren, argvals, argbounds, overestimate, coeffs, constant, success ) ); 8084 /* @Note: 'expr->data.intval' is either between 0 and number of variables-1, if it uses the varnames array, or 8285 SCIPexprPrint(expr->children[quadraticdata->quadelems[i].idx1], messagehdlr, file, varnames, paramnames, paramvals); 8293 SCIPexprPrint(expr->children[quadraticdata->quadelems[i].idx2], messagehdlr, file, varnames, paramnames, paramvals); 8327 SCIPexprPrint(expr->children[monomialdata->childidxs[j]], messagehdlr, file, varnames, paramnames, paramvals); 8404 * for each variable, we store its name, prefixed with the assigned index in the first sizeof(int) bytes 8406 SCIP_CALL( SCIPhashtableCreate(&vartable, blkmem, 10, exprparseVarTableGetKey, SCIPhashKeyEqString, SCIPhashKeyValString, NULL) ); 8408 retcode = exprParse(blkmem, messagehdlr, expr, str, (int) (lastchar - str + 1), lastchar, nvars, &varnames, vartable, 0); 8533 /** indicates whether there are parameterized constants (SCIP_EXPR_PARAM) in expression tree */ 8617 SCIP_Real* params /**< values for parameters, or NULL (if NULL but nparams > 0, then params is initialized with zeros) */ 8674 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*targettree)->vars, sourcetree->vars, sourcetree->nvars) ); 8682 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*targettree)->params, sourcetree->params, sourcetree->nparams) ); 8764 * If linear variables are split off, expression interpreter data, if stored in the tree, is freed. 8770 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */ 8771 int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */ 8772 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */ 8794 /* we should be careful about declaring numbers close to zero as zero, so take eps^2 as tolerance */ 8795 SCIP_CALL( SCIPexprSimplify(tree->blkmem, messagehdlr, tree->root, eps*eps, maxexpansionexponent, tree->nvars, nlinvars, linidxs, lincoefs) ); 8802 assert(testval_before != testval_before || testval_before == testval_after || EPSZ(SCIPrelDiff(testval_before, testval_after), eps)); /*lint !e777*/ 8815 * The root is replaced with an SCIP_EXPR_PLUS expression which has the previous root and the given expression (or a copy of it) as children. 8839 /** tries to determine the curvature type of an expression tree w.r.t. given variable domains */ 8853 SCIP_CALL( SCIPexprCheckCurvature(tree->root, infinity, varbounds, tree->params, curv, &exprbounds) ); 8906 * a is better than b if index1 of a is smaller than index1 of b or index1 of both is equal but index2 of a is smaller than index2 of b 8908 #define QUADELEMS_ISBETTER(a, b) ( ((a).idx1 < (b).idx1) || ((a).idx1 == (b).idx1 && (a).idx2 < (b).idx2) ) 8918 /** quicksort an array of quadratic elements; pivot is the medial element (taken from scip/sorttpl.c) */ 8967 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */ 8968 assert(!QUADELEMS_ISBETTER(elems[mid], pivotkey)); /* the pivot element did not change its position */ 9051 * If (idx1,idx2) is found in quadelems, then returns TRUE and stores position of quadratic element in *pos. 9052 * If (idx1,idx2) is not found in quadelems, then returns FALSE and stores position where a quadratic element with these indices would be inserted in *pos. 9060 int* pos /**< buffer to store position of found quadratic element or position where it would be inserted, or NULL */ 9085 if( idx1 < quadelems[middle].idx1 || (idx1 == quadelems[middle].idx1 && idx2 < quadelems[middle].idx2) ) /*lint !e613*/ 9087 else if( quadelems[middle].idx1 < idx1 || (quadelems[middle].idx1 == idx1 && quadelems[middle].idx2 < idx2) ) /*lint !e613*/ 9152 /* now i should point to the position after the last valid element, i.e., it is the remaining number of elements */ 9185 node->parentssorted = (node->nparents <= 1) || (node->parentssorted && (node->parents[node->nparents-2] <= parent)); 9220 SCIP_EXPRGRAPHNODE** node, /**< expression graph node where to remove a parent, *node will be set to NULL */ 9240 (void) SCIPsortedvecFindPtr((void**)(*node)->parents, ptrcomp, (void*)parent, (*node)->nparents, &pos); 9287 return SCIPsortedvecFindPtr((void**)node->parents, ptrcomp, (void*)parent, node->nparents, &pos); 9290 /** adds expression graph nodes to the array of children of a sum, product, linear, quadratic, or polynomial expression 9292 * For a sum or product expression, this corresponds to add additional summands and factors, resp. 9294 * For a quadratic or polynomial expression, only the children array may be enlarged, the expression itself remains the same. 9305 int* childmap /**< array where to store mapping of indices from exprs to children array in node, or NULL if not of interest */ 9317 assert(node->op == SCIP_EXPR_SUM || node->op == SCIP_EXPR_PRODUCT || node->op == SCIP_EXPR_LINEAR || node->op == SCIP_EXPR_QUADRATIC || node->op == SCIP_EXPR_POLYNOMIAL); 9324 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, node->nchildren, node->nchildren + nexprs) ); 9365 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, orignchildren + nexprs, node->nchildren) ); 9373 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, orignchildren + 1, node->nchildren + 1) ); 9385 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data->lincoefs, orignchildren, node->nchildren) ); 9386 BMSclearMemoryArray(&data->lincoefs[orignchildren], node->nchildren - orignchildren); /*lint !e866*/ 9419 SCIPdebugMessage("replace child %p in node %p by %p\n", (void*)*oldchild, (void*)node, (void*)newchild); 9457 assert(((SCIP_EXPRGRAPHNODE*)elem1)->data.dbl == ((SCIP_EXPRGRAPHNODE*)elem1)->data.dbl); /* assert that const value is not nan */ /*lint !e777*/ 9458 assert(((SCIP_EXPRGRAPHNODE*)elem2)->data.dbl == ((SCIP_EXPRGRAPHNODE*)elem2)->data.dbl); /* assert that const value is not nan */ /*lint !e777*/ 9530 while( exprgraph->constnodes[*pos] != node && *pos > 0 && exprgraph->constnodes[*pos-1]->data.dbl == node->data.dbl ) /*lint !e777*/ 9533 while( exprgraph->constnodes[*pos] != node && *pos < exprgraph->nconsts-1 && exprgraph->constnodes[*pos+1]->data.dbl == node->data.dbl ) /*lint !e777*/ 9571 /* set initial curvature to linear for variables, parameters, and constants and unknown otherwise */ 9618 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup); 9621 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup); 9626 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup); 9629 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup); 9634 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup); 9637 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup); 9642 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup); 9645 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup); 9650 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup); 9656 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup); 9671 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup); 9690 SCIPmessageFPrintInfo(messagehdlr, file, "(c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup); 9692 SCIPmessageFPrintInfo(messagehdlr, file, ",c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup); 9703 SCIPmessageFPrintInfo(messagehdlr, file, "c%d[%10g,%10g]", i, node->children[i]->bounds.inf, node->children[i]->bounds.sup); 9715 SCIPmessageFPrintInfo(messagehdlr, file, "c%d[%10g,%10g]", i, node->children[i]->bounds.inf, node->children[i]->bounds.sup); 9740 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[i]->bounds.inf, node->children[i]->bounds.sup); 9763 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[i]->bounds.inf, node->children[i]->bounds.sup); 9776 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[quadraticdata->quadelems[i].idx1]->bounds.inf, node->children[quadraticdata->quadelems[i].idx1]->bounds.sup); 9783 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[quadraticdata->quadelems[i].idx2]->bounds.inf, node->children[quadraticdata->quadelems[i].idx2]->bounds.sup); 9818 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[monomialdata->childidxs[j]]->bounds.inf, node->children[monomialdata->childidxs[j]]->bounds.sup); 9857 SCIPmessageFPrintInfo(messagehdlr, file, "n%d_%d [fillcolor=\"%g,%g,%g\", label=\"", node->depth, node->pos, color, color, color); 9878 SCIPmessageFPrintInfo(messagehdlr, file, "n%d_%d -> n%d_%d [label=\"c%d\"]\n", node->depth, node->pos, node->children[i]->depth, node->children[i]->pos, i); 9913 SCIP_CALL( exprOpTable[node->op].eval(node->data, node->nchildren, buf, varvals, NULL, &node->value) ); 9951 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a bound recalculation in parent nodes */ 9952 SCIP_Bool parenttightenisinvalid /**< whether to consider bounds that have been tightened by parents as invalid */ 9961 assert(node->depth >= 1); /* node should be in graph and not be at depth 0 (i.e., no variable, constant, or parameter) */ 9993 SCIP_CALL( exprOpTable[node->op].inteval(infinity, node->data, node->nchildren, childbounds, NULL, NULL, &newbounds) ); 10001 /* NOTE: if you change code below, please make analog changes also in SCIPexprgraphUpdateNodeBoundsCurvature */ 10003 /* if bounds of a children were relaxed or our bounds were tightened by a (now possibly invalid) reverse propagation from a parent 10004 * and now our bounds are relaxed, then we have to propagate this upwards to ensure valid bounds 10006 * if bounds were tightened (considerably), then tell this to those parents which think that they have valid bounds 10008 * finally, if there was only a little tightening, then keep this updated bounds, but don't notify parents 10011 ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED) || ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) && parenttightenisinvalid)) ) 10031 SCIPdebugMessage("updated bounds of node %p (%d,%d) op %s to [%g,%g]\n", (void*)node, node->depth, node->pos, SCIPexpropGetName(node->op), node->bounds.inf, node->bounds.sup); 10045 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */ 10046 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */ 10058 assert(!SCIPintervalIsEmpty(infinity, node->bounds)); /* should not call backward prop. for a node that yield a cutoff already */ 10059 assert(!node->enabled || !(node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED)); /* there should be no unprocessed relaxations of children bounds, if node is enabled */ 10061 /* if we have no recent bound tightening from a parent, then no use in reverse-propagating our bounds */ 10070 if( (node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE) == SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE ) 10076 /* SCIPdebugMessage("propagating node %p (%d,%d) op %s: [%10g,%10g] = ", (void*)node, node->depth, node->pos, SCIPexpropGetName(node->op), node->bounds.inf, node->bounds.sup); 10097 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10103 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff); 10114 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10120 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff); 10131 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10137 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff); 10148 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10154 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff); 10173 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10184 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10193 SCIPintervalPowerScalarInverse(infinity, &childbounds, node->children[0]->bounds, node->data.dbl, node->bounds); 10200 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10221 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10230 SCIPintervalPowerScalarInverse(infinity, &childbounds, node->children[0]->bounds, (SCIP_Real)node->data.intval, node->bounds); 10237 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10254 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10265 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10289 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10302 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10317 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10324 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff); 10340 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10345 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff); 10411 /* if there are too many unbounded bounds, then could only compute infinite bounds for children, so give up */ 10423 * node->bounds.sup - (minlinactivity - c_i.inf), if c_i.inf > -infinity and minlinactivityinf == 0 10437 childbounds.sup = SCIPintervalNegateReal(minlinactivity - node->bounds.sup - node->children[i]->bounds.inf); 10442 * node->bounds.inf - (maxlinactivity - c_i.sup), if c_i.sup < infinity and maxlinactivityinf == 0 10458 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff); 10489 /* if there is 0.0 in the product, then later division will hardly give useful bounds, so giveup for this i */ 10496 SCIPintervalDiv(infinity, &childbounds, node->bounds, childbounds); /* f / prod_{j:j!=i} c_j */ 10497 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff); 10598 /* SCIPdebugMessage("activity = [%10g,%10g] ninf = [%d,%d]; bounds = [%10g,%10g]\n", minlinactivity, maxlinactivity, minlinactivityinf, maxlinactivityinf, node->bounds.inf, node->bounds.sup); */ 10600 /* if there are too many unbounded bounds, then could only compute infinite bounds for children, so give up */ 10623 ac.sup = SCIPintervalNegateReal(SCIPintervalNegateReal(coefs[i]) * node->children[i]->bounds.sup); 10637 * (node->bounds.sup - minlinactivity)/coefs[i] + c_i.inf, if c_i.inf > -infinity and minlinactivityinf == 0 10638 * (node->bounds.sup - minlinactivity)/coefs[i], if c_i.inf == -infinity and minlinactivityinf == 1 10650 childbounds.sup = SCIPintervalNegateReal((minlinactivity - ac.inf - node->bounds.sup)/coefs[i]); 10655 * (node->bounds.inf - maxlinactivity)/coefs[i] + c_i.sup, if c_i.sup < infinity and maxlinactivityinf == 0 10656 * (node->bounds.inf - maxlinactivity)/coefs[i], if c_i.sup == infinity and maxlinactivityinf == 1 10677 * (node->bounds.sup - minlinactivity)/coefs[i] + c_i.sup, if c_i.sup < infinity and minlinactivityinf == 0 10678 * (node->bounds.sup - minlinactivity)/coefs[i], if c_i.sup == infinity and minlinactivityinf == 1 10689 childbounds.inf = (minlinactivity - ac.inf - node->bounds.sup)/SCIPintervalNegateReal(coefs[i]); 10694 * (node->bounds.inf - maxlinactivity)/coefs[i] + c_i.inf, if c_i.inf > -infinity and maxlinactivityinf == 0 10695 * (node->bounds.inf - maxlinactivity)/coefs[i], if c_i.inf == -infinity and maxlinactivityinf == 1 10703 childbounds.sup = SCIPintervalNegateReal((node->bounds.inf - maxlinactivity)/SCIPintervalNegateReal(coefs[i])); 10707 childbounds.sup = SCIPintervalNegateReal((node->bounds.inf - maxlinactivity + ac.sup)/SCIPintervalNegateReal(coefs[i])); 10712 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff); 10741 /* too expensive, runtime here is O(nchildren * nquadelems) = O(nquadelems^2) since nchildren <= 2*nquadelems usually */ 10775 if( (childbounds.inf > node->children[0]->bounds.inf + 1e-9 || childbounds.sup + 1e-9 < node->children[0]->bounds.sup) ) 10777 SCIPdebugMessage("%g x^2 + %g y^2 + %g xy + %g x + %g y in [%g,%g], x = [%g,%g], y = [%g,%g] -> x in [%g,%g], cutoff = %d\n", 10780 node->children[1]->bounds.inf, node->children[1]->bounds.sup, childbounds.inf, childbounds.sup, (int)SCIPintervalIsEmpty(infinity, childbounds) 10787 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 10798 if( (childbounds.inf > node->children[1]->bounds.inf + 1e-9 || childbounds.sup + 1e-9 < node->children[1]->bounds.sup) ) 10800 SCIPdebugMessage("%g x^2 + %g y^2 + %g xy + %g x + %g y in [%g,%g], x = [%g,%g], y = [%g,%g] -> y in [%g,%g], cutoff = %d\n", 10803 node->children[1]->bounds.inf, node->children[1]->bounds.sup, childbounds.inf, childbounds.sup, (int)SCIPintervalIsEmpty(infinity, childbounds) 10810 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff); 10843 SCIPintervalMulScalar(infinity, &tmp, node->children[quadelems[k].idx2]->bounds, quadelems[k].coef); 10848 SCIPintervalMulScalar(infinity, &tmp, node->children[quadelems[k].idx1]->bounds, quadelems[k].coef); 10859 SCIPintervalMul(infinity, &tmp, node->children[quadelems[k].idx1]->bounds, node->children[quadelems[k].idx2]->bounds); 10871 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff); 10962 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - 2.0*n); 10972 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - n); 10991 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - 2.0*n); 11001 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - n); 11017 SCIPintervalPowerScalar(infinity, &tmp, node->children[monomial->childidxs[k]]->bounds, monomial->exponents[k]); 11053 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff); 11055 /* SCIPdebugMessage("-> node %p (%d,%d): [%10g,%10g] = ", (void*)node, node->depth, node->pos, node->bounds.inf, node->bounds.sup); 11079 SCIP_CALL_ABORT( exprdata->prop(infinity, exprdata->userdata, 1, &childbounds, node->bounds, cutoff) ); 11082 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff); 11087 SCIP_ALLOC_ABORT( BMSallocBlockMemoryArray(exprgraph->blkmem, &childrenbounds, node->nchildren) ); 11091 SCIP_CALL_ABORT( exprdata->prop(infinity, exprdata->userdata, node->nchildren, childrenbounds, node->bounds, cutoff) ); 11095 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[c], childrenbounds[c], minstrength, infinity, cutoff); 11224 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, node->nchildren, lastnonnull+1) ); 11236 /** aims at simplifying a node in an expression graph, assuming all children have been simplified 11246 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */ 11269 SCIPdebugMessage("attempt simplification of node %p (%d,%d)\n", (void*)node, node->depth, node->pos); 11281 SCIPdebugMessage("turn node %p (%d,%d) into constant %g\n", (void*)node, node->depth, node->pos, node->value); 11340 * thereby allowing some expansions of polynomials that may not be possible otherwise, e.g., turning c0*c1 with c0=quadratic and c1=constant into a single monomial 11348 * if child was simplified in this round, it may have already been converted, and then nothing happens 11370 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */ 11383 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && node->children[i]->data.dbl < 0.0 ) /*lint !e835*/ 11386 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n", node->children[i]->data.dbl, monomial->exponents[factorpos]); 11427 * if child was simplified in this round, it may have already been converted, and then nothing happens 11430 SCIP_CALL( exprConvertToPolynomial(blkmem, &node->children[i]->op, &node->children[i]->data, node->children[i]->nchildren) ); 11446 SCIP_CALL( exprgraphNodeAddChildren(blkmem, node, node->children[i]->nchildren, node->children[i]->children, childmap) ); 11456 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */ 11473 SCIP_CALL( polynomialdataExpandMonomialFactor(blkmem, messagehdlr, polynomialdata, j, factorpos, 11474 (SCIP_EXPRDATA_POLYNOMIAL*)node->children[i]->data.data, childmap, maxexpansionexponent, &success) ); 11484 /* expansion may remove monomials[j], move a monomial from the end to position j, or add new monomials to the end of polynomialdata 11549 * but if we found duplicates in the children array, then it should be reduced, and we want to count this as a change too 11591 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[i], &childexprs[i], nexprvars, varidx) ); /*lint !e613*/ 11612 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, SCIP_EXPR_VARIDX, varidx[node->data.intval]) ); 11626 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], node->data.dbl) ); /*lint !e613*/ 11633 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], node->data.intval) ); /*lint !e613*/ 11645 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], childexprs[1]) ); /*lint !e613*/ 11677 SCIP_CALL( SCIPexprCreateLinear(exprgraph->blkmem, expr, node->nchildren, childexprs, (SCIP_Real*)node->data.data, ((SCIP_Real*)node->data.data)[node->nchildren]) ); 11716 SCIP_CALL( exprdata->copydata(exprgraph->blkmem, node->nchildren, exprdata->userdata, &userdata) ); 11722 userdata, exprdata->evalcapability, exprdata->eval, exprdata->inteval, exprdata->curv, exprdata->prop, exprdata->estimate, exprdata->copydata, exprdata->freedata) ); 11742 * @note The function does not clear the array first, but only increases already existing counts. 11747 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */ 11765 /** checks whether a node can be put into a component when checking block separability of an expression 11767 * If a variable used by node is already in another component, components are merged and component number is updated. 11791 exprgraphNodeCheckSeparabilityComponent(node->children[i], compnr, nchildcomps, childcomps, nvars, varcomps); 11812 /* variable is already in another component, so have to merge component compnr into that component 11844 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->nodessize, &exprgraph->nnodes, &exprgraph->nodes, &exprgraph->depth, mindepth); 11848 BMSclearMemoryArray(&exprgraph->nodessize[olddepth], exprgraph->depth - olddepth); /*lint !e866*/ 11849 BMSclearMemoryArray(&exprgraph->nnodes[olddepth], exprgraph->depth - olddepth); /*lint !e866*/ 11855 /** remove a variable from the variables arrays, assuming that its node will be removed or converted next */ 11889 SCIP_CALL( exprgraph->exprgraphvarchgidx(exprgraph, exprgraph->userdata, exprgraph->vars[exprgraph->nvars-1], exprgraph->varnodes[exprgraph->nvars-1], exprgraph->nvars-1, varidx) ); 11896 SCIP_CALL( SCIPhashmapSetImage(exprgraph->varidxs, exprgraph->vars[varidx], (void*)(size_t)(varidx)) ); 11929 SCIPdebugMessage("move node %p (%d,%d) to depth %d\n", (void*)node, node->depth, node->pos, newdepth); 11956 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[newdepth], &exprgraph->nodessize[newdepth], exprgraph->nnodes[newdepth]+1); /*lint !e866*/ 11965 exprgraph->nodes[olddepth][oldpos] = exprgraph->nodes[olddepth][exprgraph->nnodes[olddepth]-1]; 11977 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1); 11980 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], node) < 0); 11984 /* adding a variable by moving it from a higher depth seems awkward, how did the variable get there in the first place? */ 11989 /* nodes at depth 0 always have curvature linear, even before any curvature check was running */ 11996 /** given a list of children, tries to find a common parent that represents a given operator with the same given data */ 12004 SCIP_EXPR** exprchildren, /**< children of expression to consider when modifying (reordering) operator data, or NULL */ 12005 SCIP_EXPRGRAPHNODE** parent /**< buffer to store parent node if any is found, or NULL if none found */ 12036 (op != SCIP_EXPR_REALPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/ 12037 (op != SCIP_EXPR_SIGNPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/ 12038 (op != SCIP_EXPR_LINEAR || ((SCIP_Real*)opdata.data)[nchildren] == ((SCIP_Real*)children[0]->parents[p]->data.data)[nchildren]) && /*lint !e777*/ 12039 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->nquadelems == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->nquadelems) && 12040 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->constant == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->constant) && /*lint !e777*/ 12041 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->nmonomials == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->nmonomials) && 12042 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->constant == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->constant) /*lint !e777*/ 12048 /* for all remaining children, remove parent candidates, that are not in their list of parents */ 12054 /* if parentcands[p] is a parent of childnodes[i], then move last parent candidate to position p, 12067 SCIPdebugMessage("check %d parent candidates for expr with operator %d and %d children\n", nparentcands, op, nchildren); 12075 /* at this point, all parents in parentcands have the nodes in children as children and are of the same operator type 12076 * check if there is also one which corresponds to same expression and store that one in *parent 12104 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */ 12105 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */ 12117 * However, if there are duplicates in children, then it can happen that not every child of parentcands[p] is also one of the children. 12118 * So only if children equals parentcands[p]->children in some permutation, the expressions are the same. 12120 if( (parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1]) || 12129 /* as in the case for two nodes, we need to check whether parentcands[p]->children and children are equal up to permutation */ 12156 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */ 12157 assert(parentcands[p]->nchildren == 2); /* that was the second criterium for adding a node to parentcands */ 12158 /* order of operands matters, so check if childnodes have same order as children of parent candidate (and are the same nodes too) */ 12159 if( parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1] ) 12173 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */ 12174 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */ 12175 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */ 12176 assert(parentcands[0]->data.intval == opdata.intval); /* that was another criterium for adding a node to parentcands */ 12187 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */ 12188 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */ 12189 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */ 12190 assert(parentcands[0]->data.dbl == opdata.dbl); /* that was another criterium for adding a node to parentcands */ /*lint !e777*/ 12205 /* sort childnodes, take care that children in expression are sorted the same way if given (so we don't mess up assignment of coefficients) */ 12212 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */ 12213 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */ 12216 assert(exprcoef[nchildren] == candcoef[nchildren]); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/ 12252 /* sort children in expr and parentcands and update indices in quadelems accordingly, then sort quadelems again and compare */ 12262 SCIPsortPtrPtrRealInt((void**)children, (void**)exprchildren, exprlincoef, invperm, ptrcomp, nchildren); 12293 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */ 12294 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */ 12298 assert(canddata->nquadelems == exprdata->nquadelems); /* that was a criterium for adding a node to parentcands */ 12299 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/ 12306 SCIPsortPtrRealInt((void**)parentcands[p]->children, candlincoef, invperm, ptrcomp, parentcands[p]->nchildren); 12330 /* check if children and linear coefficients in parent candidate and expression are the same */ 12335 if( (exprlincoef == NULL ? 0.0 : exprlincoef[i]) != (candlincoef == NULL ? 0.0 : candlincoef[i]) ) /*lint !e777*/ 12363 /* @todo in one GlobalLib instance, two polynoms differ only in the sign of all coefficients, it would be nice to recognize this somehow */ 12373 /* sort children in expr and parentcands and update child indices in polynomialdata, then sort monomials again and compare */ 12396 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */ 12397 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */ 12400 assert(canddata->nmonomials == exprdata->nmonomials); /* that was a criterium for adding a node to parentcands */ 12401 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/ 12471 SCIP_EXPRGRAPHNODE** exprnode, /**< buffer to store expression graph node corresponding to root of this expression */ 12472 SCIP_Bool* exprnodeisnew /**< buffer to indicate whether the node in *exprnode has been newly created for this expression (otherwise, expression was already in graph) */ 12520 /* find node corresponding to constant corresponding to parameter and add if not existing yet */ 12544 SCIP_CALL( exprgraphAddExpr(exprgraph, expr->children[i], vars, params, &childnodes[i], &childisnew) ); /*lint !e644*/ 12549 /* if all children were known already, check if there is also already a node for the expression that we aim to add */ 12552 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, expr->nchildren, childnodes, expr->op, expr->data, expr->children, exprnode) ); 12560 /* SCIPdebugMessage("reused node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos); 12575 SCIP_CALL( exprOpTable[expr->op].copydata(exprgraph->blkmem, expr->nchildren, expr->data, &opdata) ); 12588 /* SCIPdebugMessage("created new node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos); 12600 SCIP_Bool* clearreverseprop, /**< flag to set if we had reset bound tightenings from reverse propagation */ 12601 SCIP_Bool* boundchanged /**< buffer to store whether a variables bound has changes, compared to those stored in nodes */ 12626 /* hmm, may happen due to numerics, let's be conservative and relax bounds to something that seems reasonable */ 12641 SCIPdebugMessage("registered relaxed bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i); 12645 /* if a childs bounds are relaxed, then a previous reverse propagation may be invalid, so we have to clear its remainings */ 12655 SCIPdebugMessage("registered tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i); 12662 SCIPdebugMessage("registered slightly tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i); 12907 /** gives linear coefficients belonging to a SCIP_EXPR_QUADRATIC expression, or NULL if all coefficients are 0.0 */ 13001 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */ 13002 assert(node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID); /* we assume node bounds to be valid */ 13047 *curv = SCIPexprcurvMonomial(monomial->nfactors, monomial->exponents, NULL, childcurv, childbounds); 13212 /* we store the coefficients and the constant in a single array and make this our operand data */ 13241 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) ); 13266 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) ); 13288 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)node->data.data, nmonomials, monomials, copymonomials) ); 13303 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */ 13304 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */ 13305 SCIP_DECL_USEREXPRFREEDATA ((*freedata)) /**< expression data free function, or NULL if nothing to free */ 13314 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */ 13315 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */ 13338 /** given a node of an expression graph, splitup a linear part which variables are not used somewhere else in the same expression 13342 * If it is not linear, the node may change, i.e., the remaining nonlinear part may be stored in a new node. 13374 SCIPdebugMessage("split off linear part for %s node %p (%d,%d)\n", SCIPexpropGetName((*node)->op), (void*)*node, (*node)->depth, (*node)->pos); 13403 if( (*node)->data.dbl == 1.0 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 ) 13416 if( (*node)->data.intval == 1 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 ) 13429 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 ) 13440 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 ) 13451 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 ) 13463 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 ) 13473 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 ) 13484 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 ) 13495 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 ) 13507 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 ) 13517 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 ) 13525 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 ) 13592 assert(exprgraph->nvars > 0); /* in a simplified expr graph with no variables, there can only be const nodes, but these were handled above */ 13609 SCIP_CALL( exprOpTable[orignode->op].copydata(exprgraph->blkmem, orignode->nchildren, orignode->data, &data) ); 13615 SCIP_CALL( SCIPexprgraphAddNode(exprgraph, *node, -1, orignode->nchildren, orignode->children) ); 13630 /* we had looked at this above already and only continued if exactly one node is still a child and linvarssize is >= 1 */ 13631 assert((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX); 13632 assert((*node)->children[0]->op != SCIP_EXPR_VARIDX || (*node)->children[1]->op != SCIP_EXPR_VARIDX); 13635 varchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[0] : (*node)->children[1]; 13636 otherchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[1] : (*node)->children[0]; 13664 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, 2, 1) ); /*lint !e506*/ 13756 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) ); 13867 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) ); 13868 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &coefs, (*node)->nchildren+1, nchildren+1) ); 13999 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) ); 14000 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &quaddata->lincoefs, (*node)->nchildren, nchildren) ); 14033 /* get nonlinear child usage: how often each child is used in the polynomial in a nonlinear monomial */ 14078 /* we are at a linear monomial in a variable that is not used somewhere else in nonlinear form */ 14081 linvars[*nlinvars] = exprgraph->vars[(*node)->children[childidx]->data.intval]; /*lint !e613*/ 14141 /* if node was not duplicated and not removed but changed, then invalidate value, bounds, and simplified status */ 14175 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, (*srcnode)->parents[0], srcnode, targetnode) ); 14214 SCIPdebugMessage("skip removing node %p (%d, %d) with %d parents and %d uses from expression graph\n", (void*)*node, (*node)->depth, (*node)->pos, (*node)->nparents, (*node)->nuses); 14219 SCIPdebugMessage("remove node %p (%d, %d) with op %s from expression graph\n", (void*)*node, (*node)->depth, (*node)->pos, SCIPexpropGetName((*node)->op)); 14261 exprgraph->nodes[(*node)->depth][(*node)->pos] = exprgraph->nodes[(*node)->depth][exprgraph->nnodes[(*node)->depth]-1]; 14278 /* @todo should be a private method and node creation should already capture a node instead of waiting that it's added to the graph */ 14331 /** disables a node and recursively all children which have no enabled parents in an expression graph */ 14356 SCIPdebugMessage("disabled node %p (%d,%d), nuses = %d\n", (void*)node, node->depth, node->pos, node->nuses); 14449 * Sets bound status to SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT if tightening is strong enough and not cutoff. 14455 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes (set to negative value if propagation should always be triggered) */ 14457 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */ 14472 SCIPdebugMessage("ignore bound tightening for node %p (%d,%d)\n", (void*)node, node->depth, node->pos); 14506 SCIPdebugPrintf(" -> [%10g, %10g] status %d\n", node->bounds.inf, node->bounds.sup, node->boundstatus); 14516 SCIP_Real minstrength, /**< minimal required relative bound strengthening to trigger a bound recalculation in parent nodes */ 14517 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */ 14529 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */ 14574 SCIP_CALL( exprOpTable[node->op].inteval(infinity, node->data, node->nchildren, childbounds, NULL, NULL, &newbounds) ); 14576 /* if bounds of a children were relaxed or our bounds were tightened by a (now possibly invalid) reverse propagation from a parent 14577 * and now our bounds are relaxed, then we have to propagate this upwards to ensure valid bounds 14579 * if bounds were tightened (considerably), then tell this to those parents which think that they have valid bounds 14581 * finally, if there was only a little tightening, then keep this updated bounds, but don't notify parents 14584 ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED) || ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) && clearreverseprop)) ) 14604 SCIPdebugMessage("updated bounds of node %p (%d,%d) op %s to [%g,%g]\n", (void*)node, node->depth, node->pos, SCIPexpropGetName(node->op), node->bounds.inf, node->bounds.sup); 14615 SCIPdebugMessage("node %p(%d,%d) has empty domain in SCIPexprgraphUpdateNodeBoundsCurvature\n", (void*)node, node->depth, node->pos); 14619 SCIP_CALL( exprOpTable[node->op].curv(infinity, node->data, node->nchildren, childbounds, childcurv, &node->curv) ); 14621 /* SCIPdebugMessage("curvature %s for %s = ", SCIPexprcurvGetName(node->curv), SCIPexpropGetName(node->op)); 14838 int varssizeinit, /**< minimal initial size for variables array, or -1 to choose automatically */ 14839 int depthinit, /**< minimal initial depth of expression graph, or -1 to choose automatically */ 14840 SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)), /**< callback method to invoke when a variable has been added to the expression graph, or NULL if not needed */ 14841 SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)), /**< callback method to invoke when a variable will be removed from the expression graph, or NULL if not needed */ 14842 SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)), /**< callback method to invoke when a variable changes its index in the expression graph, or NULL if not needed */ 14858 ensureBlockMemoryArraySize3((*exprgraph)->blkmem, &(*exprgraph)->varnodes, &(*exprgraph)->vars, &(*exprgraph)->varbounds, &(*exprgraph)->varssize, varssizeinit); 14859 SCIP_CALL( SCIPhashmapCreate(&(*exprgraph)->varidxs, (*exprgraph)->blkmem, SCIPcalcHashtableSize(5 * (*exprgraph)->varssize)) ); 14893 BMSfreeBlockMemoryArrayNull(blkmem, &(*exprgraph)->nodes[d], (*exprgraph)->nodessize[d]); /*lint !e866*/ 14926 int mindepth, /**< minimal depth in expression graph where to add node, e.g., 0 or smaller to choose automatically */ 14957 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[depth], &exprgraph->nodessize[depth], exprgraph->nnodes[depth]+1); /*lint !e866*/ 14976 SCIP_ALLOC( BMSduplicateBlockMemoryArray(exprgraph->blkmem, &node->children, children, nchildren) ); 14988 /* set bounds to entire, set status to "should recompute", and note that we have to update something */ 14994 /* if not a variable, set value of node according to values of children (if all have valid values) */ 15011 SCIP_EXPRGRAPHNODE** varnodes /**< array to store nodes corresponding to variables, or NULL if not of interest */ 15022 /* if there are no variables yet, then it's quite likely that we will create new nodes for all vars, so can easily estimate how much space we will need in variables array and nodes at depth 0 arrays */ 15025 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + nvars); 15026 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[0], &exprgraph->nodessize[0], exprgraph->nnodes[0] + nvars); 15054 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1); 15058 SCIP_CALL( SCIPhashmapInsert(exprgraph->varidxs, vars[i], (void*)(size_t)exprgraph->nvars) ); /*lint !e613*/ 15064 SCIPdebugMessage("added node %p (%d, %d) for new variable %d\n", (void*)node, node->depth, node->pos, node->data.intval); 15069 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[i], node) ); /*lint !e613*/ 15083 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store pointer to expression graph node corresponding to constant */ 15111 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1); 15114 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], *constnode) < 0); 15116 SCIPdebugMessage("added node %p (%d, %d) for new constant %g\n", (void*)constnode, (*constnode)->depth, (*constnode)->pos, (*constnode)->data.dbl); 15132 SCIP_EXPRGRAPHNODE** rootnode, /**< buffer to store expression graph node corresponding to root of expression tree */ 15133 SCIP_Bool* rootnodeisnew /**< buffer to indicate whether the node in *rootnode has been newly created for this expression tree (otherwise, expression tree was already in graph) */ 15151 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[0]->root, exprtrees[0]->vars, exprtrees[0]->params, rootnode, rootnodeisnew) ); 15169 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[i]->root, exprtrees[i]->vars, exprtrees[i]->params, &rootnodes[i], &rootnodeisnew_) ); /*lint !e644*/ 15200 /* all exprtrees were in the graph already, check if we also already have a node for the sum of rootnodes */ 15201 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, op, data, NULL, rootnode) ); 15232 /* all exprtrees were in the graph already, check if we also already have a node for the linear combination of rootnodes */ 15233 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, SCIP_EXPR_LINEAR, data, NULL, rootnode) ); 15258 rootnodeisnew ? "new" : "old", (void*)*rootnode, (*rootnode)->depth, (*rootnode)->pos, nexprtrees); 15314 SCIPdebugMessage("try to replace varnode %p (%d uses, %d parents) by %p\n", (void*)varnode, varnode->nuses, varnode->nparents, (void*)node); 15334 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varnode->children, 1) ); /*lint !e506*/ 15341 varnode->boundstatus = (node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID) ? SCIP_EXPRBOUNDSTATUS_VALID : SCIP_EXPRBOUNDSTATUS_CHILDRELAXED; 15360 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1); 15363 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], varnode) < 0); 15375 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1); 15379 SCIP_CALL( SCIPhashmapInsert(exprgraph->varidxs, vars[0], (void*)(size_t)exprgraph->nvars) ); /*lint !e613*/ 15385 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[0], varnode) ); /*lint !e613*/ 15442 SCIP_EXPRGRAPHNODE** varnode /**< buffer to store node corresponding to variable, if found, or NULL if not found */ 15471 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store node corresponding to constant, if found, or NULL if not found */ 15532 SCIPmessageFPrintInfo(messagehdlr, file, "node [fontcolor=white, style=filled, rankdir=LR]\n"); 15589 SCIP_Bool clearreverseprop, /**< whether to reset bound tightenings from reverse propagation */ 15590 SCIP_Bool* domainerror /**< buffer to store whether a node with empty bounds has been found, propagation is interrupted in this case */ 15606 /* if variable bounds have not changed and we do not have to clear a previous backward propagation, we can just return */ 15609 SCIPdebugMessage("no bounds changed and clearreverseprop is FALSE -> skip propagation of variable bounds\n"); 15622 SCIPdebugMessage("bounds of node %p(%d,%d) empty, stop bounds propagation\n", (void*)node, node->depth, node->pos); 15638 * NOTE: it is assumed that SCIPexprgraphPropagateVarBounds was called before if variable bounds were relaxed. 15643 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */ 15644 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */ 15668 /** updates curvature information in expression graph nodes w.r.t. currently stored variable bounds 15675 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */ 15703 SCIPerrorMessage("SCIPexprgraphCheckCurvature gets domain error while propagating variables bounds, ignoring...\n"); 15713 * A domain error can occur when variables were fixed to values for which a parent expression is not defined (e.g., 0^(-1) or log(-1)). 15719 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */ 15721 SCIP_Bool* domainerror /**< buffer to indicate whether a domain error has been encountered, i.e., some expressions turned into NaN */ 15762 /* nodes that are in use should not be removed by simplifier, so for those we store their value and check if it remains the same after simplifier was run */ 15790 * for each node, convert to polynomials and merge in child nodes that are not in use otherwise, if possible 15809 /* we should be careful about declaring numbers close to zero as zero, so take eps^2 as tolerance */ 15810 SCIP_CALL( exprgraphNodeSimplify(exprgraph, node, messagehdlr, eps*eps, maxexpansionexponent, &havechangenode) ); 15841 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be simplified */ 15861 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */ 15871 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */ 15900 SCIP_CALL( exprUnconvertPolynomial(exprgraph->blkmem, &node->op, &node->data, node->nchildren, (void**)node->children) ); 15910 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, node->parents[j], &node, node->children[0]) ); 15915 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be unconverted */ 15947 /* nodes that are in use should not have been removed by simplifier, check if they still have the same value in our testpoint */ 15958 assert(!SCIPisFinite(testval_before) || EPSZ(SCIPrelDiff(testval_before, testval_after), eps)); /*lint !e777*/ 15976 SCIP_EXPRGRAPHNODE* rootnode, /**< expression graph node that should represent root of expression tree */ 15991 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */ 16023 /** creates a sum of expression trees with pairwise disjoint variables from a given node in an expression graph 16030 int exprtreessize, /**< length of exprtrees and exprtreecoefs arrays, need to be at least one */ 16061 /* easy cases: if we have space for only one tree or there is only one child or only one variable in the graph, 16068 (node->op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1) && 16069 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1)) ) 16088 exprgraphNodeCheckSeparabilityComponent(node->children[i], &compnr, i-1, childcomp, exprgraph->nvars, varcomp); /*lint !e644*/ 16111 /* reassign all children in component childcomp[data->quadelems[i].idx2] to component childcomp[data->quadelems[i].idx1] */ 16130 if( childcomp[data->monomials[i]->childidxs[j]] != childcomp[data->monomials[i]->childidxs[0]] ) 16132 /* reassign all children in component childcomp[data->monomials[i]->childidxs[j]] to component childcomp[data->monomials[i]->childidxs[0]] */ 16137 assert(childcomp[data->monomials[i]->childidxs[j]] == childcomp[data->monomials[i]->childidxs[0]]); 16168 /* it turned out that expression is not block separable, so fallback to SCIPexprgraphGetTree */ 16180 /* if we have not enough space for all expressions, merge components with number > exprtreessize into component exprtreessize */ 16191 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varidx, exprgraph->nvars) ); /* mapping of expression graph variable indices to expression tree variable indices */ 16192 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmap, node->nchildren) ); /* mapping of child indices from node to expressions belonging to a single component */ 16193 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmapinv, node->nchildren) ); /* mapping of child indices from expressions belonging to a single component to node */ 16211 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[j], &exprs[nexprs], &nexprvars, varidx) ); /*lint !e644*/ 16225 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) ); 16236 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) ); 16237 /* if component i consists of first child, then it has coefficient 1.0, otherwise it has coefficient -1 */ 16249 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) ); 16257 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) ); 16275 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) ); 16284 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_CONST, nodecoefs[node->nchildren]/nodecoefs[childmapinv[0]]) ); 16286 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) ); 16293 if( nexprs == 2 && nodecoefs[childmapinv[0]] == nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/ 16299 else if( nexprs == 2 && nodecoefs[childmapinv[0]] == -nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/ 16302 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_MINUS, exprs[0], exprs[1]) ); 16320 /* if all coefficients are equal and no constant, create SUM expression, otherwise LINEAR expression */ 16328 SCIP_CALL( SCIPexprCreateLinear(exprgraph->blkmem, &sumexpr, nexprs, exprs, coefs, i == 0 ? nodecoefs[node->nchildren] : 0.0) ); 16335 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) ); 16370 quadelems[nquadelems].idx1 = MIN(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]); /*lint !e644*/ 16371 quadelems[nquadelems].idx2 = MAX(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]); 16377 SCIP_CALL( SCIPexprCreateQuadratic(exprgraph->blkmem, &quadexpr, nexprs, exprs, i == 0 ? nodedata->constant : 0.0, lincoefs, nquadelems, quadelems) ); 16378 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], quadexpr, nexprvars, 0, NULL) ); 16412 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomials[nmonomials], nodedata->monomials[j]->coef, nodedata->monomials[j]->nfactors, 16422 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &polyexpr, nexprs, exprs, nmonomials, monomials, i == 0 ? constant : 0.0, FALSE) ); 16423 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], polyexpr, nexprvars, 0, NULL) ); 16460 /** returns how often expression graph variables are used in a subtree of the expression graph */ 16464 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */ 16476 /** gives the number of summands which the expression of an expression graph node consists of */ 16512 /** creates a sum of expression trees, possibly sharing variables, from a given node in an expression graph */ 16516 int exprtreessize, /**< length of exprtrees and exptreecoefs arrays, should be at least SCIPexprgraphGetSumTreesNSummands() */ 16540 (node->op != SCIP_EXPR_QUADRATIC || (((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->lincoefs == NULL && ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1)) && 16541 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1) ) 16615 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodecoefs[node->nchildren] / exprtreecoefs[0]) ); 16653 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */ 16664 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx1], &expr, &nexprvars, varidx) ); 16675 /* create expression from the subgraph at quadelems[i].idx2, may add more variables into varidx */ 16676 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx2], &expr2, &nexprvars, varidx) ); 16682 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) ); 16687 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) ); 16708 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodedata->constant / exprtreecoefs[0]) ); 16737 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */ 16750 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) ); 16761 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_INTPOWER, expr, (int)monomials[i]->exponents[0]) ); 16765 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_REALPOWER, expr, monomials[i]->exponents[0]) ); 16768 else if( monomials[i]->nfactors == 2 && monomials[i]->exponents[0] == 1.0 && monomials[i]->exponents[1] == 1.0 ) 16773 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) ); 16774 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[1]], &expr2, &nexprvars, varidx) ); 16788 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childidxs, monomials[i]->nfactors) ); 16791 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[f]], &exprs[f], &nexprvars, varidx) ); /*lint !e644*/ 16796 * add also constant here, but need to divide by monomial coefficient, since we set the exprtreecoefs to monomial coef 16798 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomial, 1.0, monomials[i]->nfactors, childidxs, monomials[i]->exponents) ); 16799 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &expr, monomials[i]->nfactors, exprs, 1, &monomial, constant / monomials[i]->coef, FALSE) ); 16807 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) ); 16812 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) ); 16827 /* add constant to first summand, if still nonzero; need to divide by coefficient of the this exprtree */ 16833 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, constant / exprtreecoefs[0]) ); void SCIPintervalSignPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2) Definition: intervalarith.c:2194 static SCIP_RETCODE exprparseReadVariable(BMS_BLKMEM *blkmem, const char **str, SCIP_EXPR **expr, int *nvars, int **varnames, SCIP_HASHTABLE *vartable, SCIP_Real coefficient, const char *varnameendptr) Definition: expr.c:4891 #define SCIP_EXPRBOUNDSTATUS_CHILDRELAXED Definition: type_expr.h:211 void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_Real SCIPexprgraphGetNodeVal(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:13095 SCIP_RETCODE SCIPexprgraphPropagateVarBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Bool clearreverseprop, SCIP_Bool *domainerror) Definition: expr.c:15586 void SCIPexprtreeGetVarsUsage(SCIP_EXPRTREE *tree, int *varsusage) Definition: expr.c:8747 void SCIPquadelemSort(SCIP_QUADELEM *quadelems, int nquadelems) Definition: expr.c:9030 SCIP_RETCODE SCIPexprgraphReplaceVarByLinearSum(SCIP_EXPRGRAPH *exprgraph, void *var, int ncoefs, SCIP_Real *coefs, void **vars, SCIP_Real constant) Definition: expr.c:15267 void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2) Definition: intervalarith.c:832 void SCIPintervalMax(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:2609 #define BMSfreeBlockMemoryArrayNull(mem, ptr, num) Definition: memory.h:422 Definition: type_expr.h:55 static void exprgraphSortConstNodes(SCIP_EXPRGRAPH *exprgraph) Definition: expr.c:9470 void SCIPexprgraphSetVarNodeValue(SCIP_EXPRGRAPHNODE *varnode, SCIP_Real value) Definition: expr.c:14723 static SCIP_RETCODE exprgraphNodeAddParent(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE *parent) Definition: expr.c:9163 SCIP_RETCODE SCIPexprSubstituteVars(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR **substexprs) Definition: expr.c:7991 static SCIP_RETCODE exprsimplifyConvertToPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr) Definition: expr.c:4232 SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand) Definition: intervalarith.c:504 SCIP_RETCODE SCIPexprgraphAddNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int mindepth, int nchildren, SCIP_EXPRGRAPHNODE **children) Definition: expr.c:14923 void SCIPintervalSign(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand) Definition: intervalarith.c:2651 static SCIP_RETCODE eval(SCIP_EXPR *expr, const vector< Type > &x, SCIP_Real *param, Type &val) Definition: exprinterpret_cppad.cpp:1788 static SCIP_RETCODE exprsimplifyRemoveDuplicatePolynomialChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real eps) Definition: expr.c:4256 SCIP_RETCODE SCIPexprgraphGetSumTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs) Definition: expr.c:16513 SCIP_RETCODE SCIPexprtreeEvalInt(SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_INTERVAL *val) Definition: expr.c:8579 Definition: intervalarith.h:36 Definition: type_expr.h:57 SCIP_RETCODE SCIPexprgraphAddVars(SCIP_EXPRGRAPH *exprgraph, int nvars, void **vars, SCIP_EXPRGRAPHNODE **varnodes) Definition: expr.c:15007 methods to interpret (evaluate) an expression tree "fast" void SCIPexprtreePrint(SCIP_EXPRTREE *tree, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames, const char **paramnames) Definition: expr.c:8596 int * SCIPexprGetMonomialChildIndices(SCIP_EXPRDATA_MONOMIAL *monomial) Definition: expr.c:5800 SCIP_RETCODE SCIPexprgraphUpdateNodeBoundsCurvature(SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool clearreverseprop) Definition: expr.c:14513 static SCIP_RETCODE polynomialdataMultiplyByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap) Definition: expr.c:938 Definition: type_expr.h:70 static SCIP_RETCODE exprUnconvertPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPROP *op, SCIP_EXPROPDATA *data, int nchildren, void **children) Definition: expr.c:3735 SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element) Definition: misc.c:1567 static SCIP_RETCODE exprgraphNodeAddChildren(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, int nexprs, SCIP_EXPRGRAPHNODE **exprs, int *childmap) Definition: expr.c:9300 int SCIPexprgraphGetNodeNChildren(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12733 Definition: type_expr.h:63 static SCIP_RETCODE exprgraphNodeCreateExpr(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_EXPR **expr, int *nexprvars, int *varidx) Definition: expr.c:11567 void SCIPexprPrint(SCIP_EXPR *expr, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames, const char **paramnames, SCIP_Real *paramvals) Definition: expr.c:8071 static SCIP_RETCODE exprgraphEnsureDepth(SCIP_EXPRGRAPH *exprgraph, int mindepth) Definition: expr.c:11830 void SCIPsortPtrPtrRealInt(void **ptrarray1, void **ptrarray2, SCIP_Real *realarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) static void polynomialdataSortMonomials(SCIP_EXPRDATA_POLYNOMIAL *polynomialdata) Definition: expr.c:783 static SCIP_RETCODE exprgraphNodeSimplify(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, SCIP_Bool *havechange) Definition: expr.c:11241 void SCIPsortPtrPtrReal(void **ptrarray1, void **ptrarray2, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) static SCIP_RETCODE polynomialdataMultiplyByPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_EXPRDATA_POLYNOMIAL *factordata, int *childmap) Definition: expr.c:982 static SCIP_RETCODE exprparseFindSeparatingComma(const char *str, const char **endptr, int length) Definition: expr.c:5023 static SCIP_RETCODE exprgraphNodeRemovePolynomialNullChildren(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node) Definition: expr.c:11172 SCIP_RETCODE SCIPexprgraphCreateNodeUser(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_USEREXPRDATA *data, SCIP_EXPRINTCAPABILITY evalcapability, SCIP_DECL_USEREXPREVAL((*eval)), SCIP_DECL_USEREXPRINTEVAL((*inteval)), SCIP_DECL_USEREXPRCURV((*curv)), SCIP_DECL_USEREXPRPROP((*prop)), SCIP_DECL_USEREXPRESTIMATE((*estimate)), SCIP_DECL_USEREXPRCOPYDATA((*copydata)), SCIP_DECL_USEREXPRFREEDATA((*freedata))) Definition: expr.c:13294 void SCIPexprChgPolynomialConstant(SCIP_EXPR *expr, SCIP_Real constant) Definition: expr.c:6567 SCIP_RETCODE SCIPexprgraphAddConst(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode) Definition: expr.c:15080 Definition: type_expr.h:72 SCIP_RETCODE SCIPexprtreeGetMaxDegree(SCIP_EXPRTREE *tree, int *maxdegree) Definition: expr.c:8550 SCIP_Real * SCIPexprtreeGetParamVals(SCIP_EXPRTREE *tree) Definition: expr.c:8472 void SCIPexprgraphSetVarNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_INTERVAL varbounds) Definition: expr.c:14767 SCIP_RETCODE SCIPexprCreateMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL **monomial, SCIP_Real coef, int nfactors, int *childidxs, SCIP_Real *exponents) Definition: expr.c:6913 void SCIPexprgraphCaptureNode(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12711 Definition: struct_expr.h:67 SCIP_RETCODE SCIPexprgraphCreateNodeQuadratic(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, int nchildren, SCIP_Real *lincoefs, int nquadelems, SCIP_QUADELEM *quadelems, SCIP_Real constant) Definition: expr.c:13224 SCIP_Real SCIPexprGetRealPowerExponent(SCIP_EXPR *expr) Definition: expr.c:5636 SCIP_RETCODE SCIPexprintFreeData(SCIP_EXPRINTDATA **interpreterdata) Definition: exprinterpret_cppad.cpp:2278 data definitions for expressions and expression trees SCIP_RETCODE SCIPexprSimplify(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPR *expr, SCIP_Real eps, int maxexpansionexponent, int nvars, int *nlinvars, int *linidxs, SCIP_Real *lincoefs) Definition: expr.c:7665 SCIP_RETCODE SCIPexprPolynomialPower(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int exponent) Definition: expr.c:6663 void SCIPexprChgMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real newcoef) Definition: expr.c:6729 SCIP_Real SCIPexprGetPolynomialConstant(SCIP_EXPR *expr) Definition: expr.c:5768 void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode) Definition: intervalarith.c:188 void SCIPexprgraphPropagateNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool *cutoff) Definition: expr.c:15640 void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:963 SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize) Definition: misc.c:2057 #define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT Definition: type_expr.h:212 SCIP_Bool SCIPexprAreEqual(SCIP_EXPR *expr1, SCIP_EXPR *expr2, SCIP_Real eps) Definition: expr.c:7456 void SCIPexprMonomialPower(SCIP_EXPRDATA_MONOMIAL *monomial, int exponent) Definition: expr.c:6804 SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetVarNodes(SCIP_EXPRGRAPH *exprgraph) Definition: expr.c:14713 Definition: type_expr.h:60 Definition: type_expr.h:71 static void exprgraphNodeCheckSeparabilityComponent(SCIP_EXPRGRAPHNODE *node, int *compnr, int nchildcomps, int *childcomps, int nvars, int *varcomps) Definition: expr.c:11770 static SCIP_RETCODE exprgraphNodeRemovePolynomialDuplicateChildren(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node) Definition: expr.c:11114 SCIP_Real SCIPexprgraphGetNodeSignPowerExponent(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12862 Definition: struct_message.h:35 static SCIP_RETCODE exprCreate(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPROP op, int nchildren, SCIP_EXPR **children, SCIP_EXPROPDATA opdata) Definition: expr.c:3266 static SCIP_RETCODE exprParse(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPR **expr, const char *str, int length, const char *lastchar, int *nvars, int **varnames, SCIP_HASHTABLE *vartable, int recursiondepth) Definition: expr.c:5055 void SCIPsortPtrPtrInt(void **ptrarray1, void **ptrarray2, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_RETCODE SCIPexprtreeCopy(BMS_BLKMEM *blkmem, SCIP_EXPRTREE **targettree, SCIP_EXPRTREE *sourcetree) Definition: expr.c:8652 int SCIPexprgraphGetNodeNParents(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12753 void SCIPexprGetVarsUsage(SCIP_EXPR *expr, int *varsusage) Definition: expr.c:7433 void SCIPintervalMin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:2593 SCIP_INTERVAL SCIPexprgraphGetNodeBounds(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:13085 SCIP_RETCODE SCIPexprgraphEval(SCIP_EXPRGRAPH *exprgraph, SCIP_Real *varvals) Definition: expr.c:15565 void SCIPexprReindexVars(SCIP_EXPR *expr, int *newindices) Definition: expr.c:8029 void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup) Definition: intervalarith.c:479 void SCIPintervalPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2) Definition: intervalarith.c:1865 int * SCIPexprgraphGetNNodes(SCIP_EXPRGRAPH *exprgraph) Definition: expr.c:14673 SCIP_RETCODE SCIPexprEvalInt(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val) Definition: expr.c:7797 SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr) Definition: misc.c:8214 Definition: type_expr.h:98 void SCIPexprSortMonomialFactors(SCIP_EXPRDATA_MONOMIAL *monomial) Definition: expr.c:6994 static void polynomialdataApplyChildmap(SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int *childmap) Definition: expr.c:1141 Definition: type_expr.h:38 Definition: type_expr.h:85 SCIP_RETCODE SCIPexprgraphAddExprtreeSum(SCIP_EXPRGRAPH *exprgraph, int nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *coefs, SCIP_EXPRGRAPHNODE **rootnode, SCIP_Bool *rootnodeisnew) Definition: expr.c:15127 void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2116 SCIP_RETCODE SCIPexprMultiplyMonomialByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap) Definition: expr.c:6769 SCIP_RETCODE SCIPexprCreateUser(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_USEREXPRDATA *data, SCIP_EXPRINTCAPABILITY evalcapability, SCIP_DECL_USEREXPREVAL((*eval)), SCIP_DECL_USEREXPRINTEVAL((*inteval)), SCIP_DECL_USEREXPRCURV((*curv)), SCIP_DECL_USEREXPRPROP((*prop)), SCIP_DECL_USEREXPRESTIMATE((*estimate)), SCIP_DECL_USEREXPRCOPYDATA((*copydata)), SCIP_DECL_USEREXPRFREEDATA((*freedata))) Definition: expr.c:7031 SCIP_RETCODE SCIPexprtreeCreate(BMS_BLKMEM *blkmem, SCIP_EXPRTREE **tree, SCIP_EXPR *root, int nvars, int nparams, SCIP_Real *params) Definition: expr.c:8611 SCIP_Bool SCIPquadelemSortedFind(SCIP_QUADELEM *quadelems, int idx1, int idx2, int nquadelems, int *pos) Definition: expr.c:9055 void SCIPexprtreeSetParamVal(SCIP_EXPRTREE *tree, int paramidx, SCIP_Real paramval) Definition: expr.c:8482 Definition: type_expr.h:53 Definition: type_expr.h:44 void SCIPintervalDiv(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:1128 int SCIPexprgraphGetNodePolynomialNMonomials(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12956 Definition: type_expr.h:86 static void exprgraphPrintNodeDot(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames) Definition: expr.c:9841 static void exprgraphUpdateVarNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Bool *clearreverseprop, SCIP_Bool *boundchanged) Definition: expr.c:12598 void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs) Definition: intervalarith.c:2957 SCIP_RETCODE SCIPexprgraphMoveNodeParents(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **srcnode, SCIP_EXPRGRAPHNODE *targetnode) Definition: expr.c:14158 SCIP_EXPRCURV SCIPexprcurvMonomial(int nfactors, SCIP_Real *exponents, int *factoridxs, SCIP_EXPRCURV *factorcurv, SCIP_INTERVAL *factorbounds) Definition: expr.c:344 SCIP_EXPRDATA_MONOMIAL ** SCIPexprGetMonomials(SCIP_EXPR *expr) Definition: expr.c:5744 SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr) Definition: misc.c:1480 public methods for expressions, expression trees, expression graphs, and related stuff ... SCIP_EXPRCURV SCIPexprcurvMultiply(SCIP_Real factor, SCIP_EXPRCURV curvature) Definition: expr.c:223 int SCIPexprGetMonomialNFactors(SCIP_EXPRDATA_MONOMIAL *monomial) Definition: expr.c:5790 SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2159 #define SCIP_EXPRINTCAPABILITY_INTFUNCVALUE Definition: type_exprinterpret.h:37 SCIP_RETCODE SCIPexprtreeCheckCurvature(SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varbounds, SCIP_EXPRCURV *curv, SCIP_INTERVAL *bounds) Definition: expr.c:8840 SCIP_EXPROP SCIPexprgraphGetNodeOperator(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12793 static SCIP_RETCODE exprgraphCreateNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_EXPROP op, SCIP_EXPROPDATA opdata) Definition: expr.c:9541 SCIP_EXPRDATA_MONOMIAL ** SCIPexprgraphGetNodePolynomialMonomials(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12944 SCIP_RETCODE SCIPexprgraphCreate(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPH **exprgraph, int varssizeinit, int depthinit, SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)), SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)), SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)), void *userdata) Definition: expr.c:14835 Definition: type_expr.h:45 Definition: type_expr.h:47 int SCIPexprgraphGetNodeOperatorIndex(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12803 Definition: type_expr.h:74 Definition: struct_misc.h:101 Definition: type_expr.h:51 SCIP_Real SCIPexprgraphGetNodeLinearConstant(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12884 #define ensureBlockMemoryArraySize3(blkmem, array1, array2, array3, cursize, minsize) Definition: expr.c:86 #define BMSduplicateBlockMemoryArray(mem, ptr, source, num) Definition: memory.h:416 SCIP_Real SCIPexprgraphGetNodePolynomialConstant(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12968 SCIP_RETCODE SCIPexprAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials) Definition: expr.c:6545 SCIP_Bool SCIPexprgraphHasNodeNonlinearAncestor(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:14398 SCIP_EXPRCURV SCIPexprgraphGetNodeCurvature(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:13105 SCIP_RETCODE SCIPexprCreateQuadratic(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real constant, SCIP_Real *lincoefs, int nquadelems, SCIP_QUADELEM *quadelems) Definition: expr.c:6462 Definition: type_expr.h:49 SCIP_Bool SCIPexprgraphFindConstNode(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode) Definition: expr.c:15468 SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand) Definition: intervalarith.c:528 SCIP_RETCODE SCIPexprEval(SCIP_EXPR *expr, SCIP_Real *varvals, SCIP_Real *param, SCIP_Real *val) Definition: expr.c:7736 void SCIPexprgraphSetVarsBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_INTERVAL *varbounds) Definition: expr.c:14735 static SCIP_Bool isUbBetter(SCIP_Real minstrength, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub) Definition: expr.c:152 Definition: type_retcode.h:36 SCIP_RETCODE SCIPexprgraphCheckCurvature(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Bool clearreverseprop) Definition: expr.c:15672 SCIP_RETCODE SCIPexprGetMaxDegree(SCIP_EXPR *expr, int *maxdegree) Definition: expr.c:7108 static void polynomialdataMultiplyByConstant(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_Real factor) Definition: expr.c:908 interval arithmetics for provable bounds void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant) Definition: intervalarith.c:493 void SCIPsortPtrRealInt(void **ptrarray, SCIP_Real *realarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_Real * SCIPexprGetQuadLinearCoefs(SCIP_EXPR *expr) Definition: expr.c:5720 SCIP_EXPRGRAPHNODE *** SCIPexprgraphGetNodes(SCIP_EXPRGRAPH *exprgraph) Definition: expr.c:14683 int SCIPexprgraphGetSumTreesNSummands(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:16477 static SCIP_RETCODE exprsimplifyRemovePolynomialNullChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr) Definition: expr.c:4310 void SCIPintervalLog(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand) Definition: intervalarith.c:2519 SCIP_RETCODE SCIPexprCopyDeep(BMS_BLKMEM *blkmem, SCIP_EXPR **targetexpr, SCIP_EXPR *sourceexpr) Definition: expr.c:6019 Definition: type_expr.h:50 SCIP_Bool SCIPexprgraphHasNodeUserEstimator(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:13073 SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos) static SCIP_RETCODE quadraticdataCreate(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_QUADRATIC **quadraticdata, SCIP_Real constant, int nchildren, SCIP_Real *lincoefs, int nquadelems, SCIP_QUADELEM *quadelems) Definition: expr.c:473 SCIP_EXPRCURV SCIPexprcurvPower(SCIP_INTERVAL basebounds, SCIP_EXPRCURV basecurv, SCIP_Real exponent) Definition: expr.c:236 static SCIP_RETCODE exprgraphNodeReplaceChild(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE **oldchild, SCIP_EXPRGRAPHNODE *newchild) Definition: expr.c:9401 void SCIPmessagePrintWarning(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...) Definition: message.c:411 static SCIP_Bool exprgraphNodeIsParent(SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE *parent) Definition: expr.c:9269 static void polynomialdataFree(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata) Definition: expr.c:695 void SCIPexprMergeMonomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real eps, SCIP_Bool mergefactors) Definition: expr.c:6683 SCIP_Bool SCIPexprAreMonomialsEqual(SCIP_EXPRDATA_MONOMIAL *monomial1, SCIP_EXPRDATA_MONOMIAL *monomial2, SCIP_Real eps) Definition: expr.c:6698 Definition: type_retcode.h:33 SCIP_RETCODE SCIPexprgraphCreateNodeLinear(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, int ncoefs, SCIP_Real *coefs, SCIP_Real constant) Definition: expr.c:13198 SCIP_RETCODE SCIPexprgraphGetSeparableTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs) Definition: expr.c:16027 void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_Bool SCIPexprgraphIsNodeEnabled(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12723 SCIP_INTERVAL * SCIPexprgraphGetVarsBounds(SCIP_EXPRGRAPH *exprgraph) Definition: expr.c:14827 SCIP_RETCODE SCIPexprParse(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPR **expr, const char *str, const char *lastchar, int *nvars, int *varnames) Definition: expr.c:8381 SCIP_RETCODE SCIPexprCreatePolynomial(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Real constant, SCIP_Bool copymonomials) Definition: expr.c:6510 SCIP_RETCODE SCIPexprCheckCurvature(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varbounds, SCIP_Real *param, SCIP_EXPRCURV *curv, SCIP_INTERVAL *bounds) Definition: expr.c:7895 SCIP_RETCODE SCIPexprEvalUser(SCIP_EXPR *expr, SCIP_Real *argvals, SCIP_Real *val, SCIP_Real *gradient, SCIP_Real *hessian) Definition: expr.c:7839 void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...) Definition: message.c:578 SCIP_RETCODE SCIPexprEvalShallow(SCIP_EXPR *expr, SCIP_Real *argvals, SCIP_Real *varvals, SCIP_Real *param, SCIP_Real *val) Definition: expr.c:7717 void SCIPexprMultiplyPolynomialByConstant(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real factor) Definition: expr.c:6580 void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value) Definition: intervalarith.c:467 void SCIPexprgraphTightenNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_INTERVAL nodebounds, SCIP_Real minstrength, SCIP_Real infinity, SCIP_Bool *cutoff) Definition: expr.c:14451 static SCIP_RETCODE exprsimplifyUnconvertPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr) Definition: expr.c:4857 SCIP_RETCODE SCIPexprEstimateUser(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_Real *argvals, SCIP_INTERVAL *argbounds, SCIP_Bool overestimate, SCIP_Real *coeffs, SCIP_Real *constant, SCIP_Bool *success) Definition: expr.c:7953 static SCIP_RETCODE exprgraphNodeUpdateBounds(SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool parenttightenisinvalid) Definition: expr.c:9948 void SCIPexprFreeMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL **monomial) Definition: expr.c:6970 SCIP_RETCODE SCIPexprMulConstant(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPR *term, SCIP_Real factor) Definition: expr.c:6282 SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos) SCIP_Bool SCIPexprgraphHasNodeSibling(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:14363 SCIP_RETCODE SCIPexprgraphGetNodePolynomialMonomialCurvature(SCIP_EXPRGRAPHNODE *node, int monomialidx, SCIP_Real infinity, SCIP_EXPRCURV *curv) Definition: expr.c:12983 Definition: type_retcode.h:34 SCIP_Real SCIPexprgraphGetNodeOperatorReal(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12814 Definition: struct_expr.h:46 SCIP_RETCODE SCIPexprAdd(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_Real coef1, SCIP_EXPR *term1, SCIP_Real coef2, SCIP_EXPR *term2, SCIP_Real constant) Definition: expr.c:6124 SCIP_Real SCIPexprgraphGetNodeQuadraticConstant(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12896 SCIP_RETCODE SCIPexprMultiplyPolynomialByPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR *factor, int *childmap) Definition: expr.c:6617 void SCIPexprMergeMonomialFactors(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real eps) Definition: expr.c:6834 SCIP_EXPRINTCAPABILITY SCIPexprGetUserEvalCapability(SCIP_EXPR *expr) Definition: expr.c:5842 public data structures and miscellaneous methods static void polynomialdataMergeMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_Real eps, SCIP_Bool mergefactors) Definition: expr.c:816 Definition: type_expr.h:83 SCIP_Real SCIPexprGetSignPowerExponent(SCIP_EXPR *expr) Definition: expr.c:5658 static SCIP_RETCODE exprgraphNodeEval(SCIP_EXPRGRAPHNODE *node, SCIP_Real *varvals) Definition: expr.c:9883 SCIP_Bool SCIPexprgraphAreAllNodeChildrenVars(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:14382 Definition: type_expr.h:37 static SCIP_RETCODE monomialdataEnsureFactorsSize(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomialdata, int minsize) Definition: expr.c:586 void SCIPexprgraphSetVarNodeLb(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_Real lb) Definition: expr.c:14787 static SCIP_RETCODE exprsimplifyFlattenPolynomials(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPR *expr, SCIP_Real eps, int maxexpansionexponent) Definition: expr.c:4427 static SCIP_RETCODE exprgraphNodeRemoveParent(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node, SCIP_EXPRGRAPHNODE *parent) Definition: expr.c:9218 SCIP_EXPRINTDATA * SCIPexprtreeGetInterpreterData(SCIP_EXPRTREE *tree) Definition: expr.c:8497 SCIP_RETCODE SCIPexprtreeFreeInterpreterData(SCIP_EXPRTREE *tree) Definition: expr.c:8520 void SCIPintervalSolveBivariateQuadExpressionAllScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real ax, SCIP_Real ay, SCIP_Real axy, SCIP_Real bx, SCIP_Real by, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds, SCIP_INTERVAL ybnds) Definition: intervalarith.c:3278 void SCIPquadelemSqueeze(SCIP_QUADELEM *quadelems, int nquadelems, int *nquadelemsnew) Definition: expr.c:9107 SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr) Definition: misc.c:8245 void SCIPintervalSquareRoot(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand) Definition: intervalarith.c:1481 void SCIPintervalQuadBivar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real ax, SCIP_Real ay, SCIP_Real axy, SCIP_Real bx, SCIP_Real by, SCIP_INTERVAL xbnds, SCIP_INTERVAL ybnds) Definition: intervalarith.c:3019 void SCIPexprgraphGetSubtreeVarsUsage(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int *varsusage) Definition: expr.c:16461 void SCIPexprgraphSetVarNodeUb(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_Real ub) Definition: expr.c:14807 static SCIP_Bool exprgraphFindConstNodePos(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int *pos) Definition: expr.c:9486 void SCIPintervalSquare(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand) Definition: intervalarith.c:1409 SCIP_RETCODE SCIPexprgraphNodeSplitOffLinear(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node, int linvarssize, int *nlinvars, void **linvars, SCIP_Real *lincoefs, SCIP_Real *constant) Definition: expr.c:13346 SCIP_RETCODE SCIPexprCreate(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPROP op,...) Definition: expr.c:5853 void SCIPintervalScalprodScalars(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2) Definition: intervalarith.c:1381 Definition: struct_expr.h:115 SCIP_Bool SCIPexprFindMonomialFactor(SCIP_EXPRDATA_MONOMIAL *monomial, int childidx, int *pos) Definition: expr.c:7014 Definition: type_expr.h:56 void SCIPexprgraphFreeNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node) Definition: expr.c:14280 void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:677 static void exprgraphNodePropagateBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool *cutoff) Definition: expr.c:10041 #define SCIP_EXPRBOUNDSTATUS_CHILDTIGHTENED Definition: type_expr.h:210 void SCIPexprgraphDisableNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node) Definition: expr.c:14332 Definition: type_expr.h:62 Definition: struct_expr.h:101 SCIP_RETCODE SCIPexprtreeAddExpr(SCIP_EXPRTREE *tree, SCIP_EXPR *expr, SCIP_Bool copyexpr) Definition: expr.c:8817 void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key) Definition: misc.c:1627 Definition: struct_expr.h:89 void SCIPintervalAbs(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand) Definition: intervalarith.c:2625 SCIP_Real SCIPexprGetMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial) Definition: expr.c:5780 static SCIP_RETCODE polynomialdataCopy(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata, SCIP_EXPRDATA_POLYNOMIAL *sourcepolynomialdata) Definition: expr.c:658 static SCIP_RETCODE polynomialdataExpandMonomialFactor(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int monomialpos, int factorpos, SCIP_EXPRDATA_POLYNOMIAL *factorpolynomial, int *childmap, int maxexpansionexponent, SCIP_Bool *success) Definition: expr.c:1170 void * SCIPexprgraphGetNodeVar(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12825 Definition: type_expr.h:61 SCIP_Real * SCIPexprgraphGetNodeQuadraticLinearCoefs(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12908 static SCIP_RETCODE exprConvertToPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPROP *op, SCIP_EXPROPDATA *data, int nchildren) Definition: expr.c:3297 SCIP_Real SCIPgetRandomReal(SCIP_Real minrandval, SCIP_Real maxrandval, unsigned int *seedp) Definition: misc.c:7719 SCIP_RETCODE SCIPexprEvalIntUser(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *argvals, SCIP_INTERVAL *val, SCIP_INTERVAL *gradient, SCIP_INTERVAL *hessian) Definition: expr.c:7862 int SCIPexprgraphGetNodeIntPowerExponent(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12851 SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeParents(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12763 static void exprgraphNodeSortParents(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:9192 static SCIP_RETCODE exprgraphAddExpr(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPR *expr, void **vars, SCIP_Real *params, SCIP_EXPRGRAPHNODE **exprnode, SCIP_Bool *exprnodeisnew) Definition: expr.c:12466 static SCIP_RETCODE polynomialdataAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials) Definition: expr.c:741 static void quadraticdataSort(SCIP_EXPRDATA_QUADRATIC *quadraticdata) Definition: expr.c:511 Definition: struct_misc.h:80 SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2177 SCIP_Bool SCIPexprgraphFindVarNode(SCIP_EXPRGRAPH *exprgraph, void *var, SCIP_EXPRGRAPHNODE **varnode) Definition: expr.c:15439 Definition: type_expr.h:77 void SCIPexprReindexParams(SCIP_EXPR *expr, int *newindices) Definition: expr.c:8050 SCIP_Real * SCIPexprgraphGetNodeLinearCoefs(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12873 #define SCIP_EXPRINTCAPABILITY_FUNCVALUE Definition: type_exprinterpret.h:36 void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant) Definition: intervalarith.c:516 int SCIPexprgraphGetNodePosition(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12783 static SCIP_Bool isLbBetter(SCIP_Real minstrength, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub) Definition: expr.c:132 SCIP_RETCODE SCIPexprgraphNodePolynomialAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials) Definition: expr.c:13275 void SCIPexprFreeShallow(BMS_BLKMEM *blkmem, SCIP_EXPR **expr) Definition: expr.c:6099 Definition: type_expr.h:84 SCIP_QUADELEM * SCIPexprGetQuadElements(SCIP_EXPR *expr) Definition: expr.c:5695 SCIP_RETCODE SCIPexprgraphCreateNodePolynomial(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Real constant, SCIP_Bool copymonomials) Definition: expr.c:13250 void SCIPintervalExp(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand) Definition: intervalarith.c:2439 public methods for message output SCIP_USEREXPRDATA * SCIPexprgraphGetNodeUserData(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:13061 static SCIP_RETCODE exprsimplifySeparateLinearFromPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real eps, int nvars, int *nlinvars, int *linidxs, SCIP_Real *lincoefs) Definition: expr.c:4756 SCIP_RETCODE SCIPexprgraphCreateNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_EXPROP op,...) Definition: expr.c:13115 SCIP_RETCODE SCIPexprEvalIntShallow(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *argvals, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val) Definition: expr.c:7777 SCIP_RETCODE SCIPexprgraphReleaseNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node) Definition: expr.c:14190 #define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE Definition: type_expr.h:214 void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...) Definition: message.c:602 SCIP_RETCODE SCIPhashmapSetImage(SCIP_HASHMAP *hashmap, void *origin, void *image) Definition: misc.c:2137 SCIP_RETCODE SCIPexprtreeSimplify(SCIP_EXPRTREE *tree, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, int *nlinvars, int *linidxs, SCIP_Real *lincoefs) Definition: expr.c:8766 SCIP_RETCODE SCIPexprgraphGetTree(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *rootnode, SCIP_EXPRTREE **exprtree) Definition: expr.c:15974 Definition: type_expr.h:69 Definition: type_expr.h:52 void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:583 static SCIP_RETCODE polynomialdataCreate(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Real constant, SCIP_Bool copymonomials) Definition: expr.c:611 void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2) Definition: intervalarith.c:1102 Definition: struct_expr.h:77 SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeChildren(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12743 void SCIPsortPtrReal(void **ptrarray, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_RETCODE SCIPexprAddMonomialFactors(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, int nfactors, int *childidxs, SCIP_Real *exponents) Definition: expr.c:6740 SCIP_Real * SCIPexprGetMonomialExponents(SCIP_EXPRDATA_MONOMIAL *monomial) Definition: expr.c:5810 void SCIPexprgraphPrintNode(SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file) Definition: expr.c:14435 SCIP_RETCODE SCIPexprtreeSubstituteVars(SCIP_EXPRTREE *tree, SCIP_EXPR **substexprs) Definition: expr.c:8866 Definition: type_expr.h:73 Definition: type_expr.h:54 static SCIP_RETCODE exprgraphNodeEvalWithChildren(SCIP_EXPRGRAPHNODE *node, SCIP_Real *varvals) Definition: expr.c:9927 Definition: struct_expr.h:154 SCIP_RETCODE SCIPexprgraphSimplify(SCIP_EXPRGRAPH *exprgraph, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, SCIP_Bool *havechange, SCIP_Bool *domainerror) Definition: expr.c:15715 static SCIP_RETCODE exprsimplifyRemovePolynomialUnusedChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr) Definition: expr.c:4376 void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2) Definition: intervalarith.c:784 static SCIP_RETCODE exprgraphMoveNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int newdepth) Definition: expr.c:11910 static SCIP_RETCODE exprparseFindClosingParenthesis(const char *str, const char **endptr, int length) Definition: expr.c:4984 SCIP_RETCODE SCIPexprAddToLinear(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nchildren, SCIP_Real *coefs, SCIP_EXPR **children, SCIP_Real constant) Definition: expr.c:6417 static SCIP_RETCODE exprsimplifyAddChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nexprs, SCIP_EXPR **exprs, SCIP_Bool comparechildren, SCIP_Real eps, int *childmap) Definition: expr.c:4113 SCIP_RETCODE SCIPexprMultiplyPolynomialByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap) Definition: expr.c:6594 SCIP_Real SCIPexprgraphGetNodeRealPowerExponent(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12840 Definition: struct_expr.h:55 SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image) Definition: misc.c:2094 int SCIPexprgraphGetNodeQuadraticNQuadElements(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12932 Definition: type_retcode.h:43 static SCIP_RETCODE polynomialdataPower(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int exponent) Definition: expr.c:1071 Definition: type_expr.h:48 #define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT Definition: type_expr.h:213 SCIP_RETCODE SCIPexprCreateLinear(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real *coefs, SCIP_Real constant) Definition: expr.c:6380 void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2) Definition: intervalarith.c:704 SCIP_Real SCIPexprGetLinearConstant(SCIP_EXPR *expr) Definition: expr.c:5682 void SCIPexprtreeSetInterpreterData(SCIP_EXPRTREE *tree, SCIP_EXPRINTDATA *interpreterdata) Definition: expr.c:8507 SCIP_EXPRCURV SCIPexprcurvAdd(SCIP_EXPRCURV curv1, SCIP_EXPRCURV curv2) Definition: expr.c:188 static void quadelemsQuickSort(SCIP_QUADELEM *elems, int start, int end) Definition: expr.c:8920 static SCIP_RETCODE polynomialdataEnsureMonomialsSize(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int minsize) Definition: expr.c:724 SCIP_RETCODE SCIPexprtreeSetParams(SCIP_EXPRTREE *tree, int nparams, SCIP_Real *paramvals) Definition: expr.c:8716 SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void) Definition: intervalarith.c:196 static void exprgraphPrintNodeExpression(SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames, SCIP_Bool printchildrenbounds) Definition: expr.c:9585 static SCIP_RETCODE exprgraphFindParentByOperator(SCIP_EXPRGRAPH *exprgraph, int nchildren, SCIP_EXPRGRAPHNODE **children, SCIP_EXPROP op, SCIP_EXPROPDATA opdata, SCIP_EXPR **exprchildren, SCIP_EXPRGRAPHNODE **parent) Definition: expr.c:11998 static void exprgraphNodeGetVarsUsage(SCIP_EXPRGRAPHNODE *node, int *varsusage) Definition: expr.c:11745 SCIP_RETCODE SCIPexprgraphPrintDot(SCIP_EXPRGRAPH *exprgraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames) Definition: expr.c:15516 #define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum) Definition: memory.h:412 void SCIPintervalSetRoundingModeDownwards(void) Definition: intervalarith.c:390 void SCIPintervalPowerScalarInverse(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL basedomain, SCIP_Real exponent, SCIP_INTERVAL image) Definition: intervalarith.c:2113 int SCIPexprgraphGetNodeDepth(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12773 SCIP_RETCODE SCIPexprtreeEval(SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Real *val) Definition: expr.c:8563 SCIP_EXPRINTCAPABILITY evalcapability Definition: struct_expr.h:104 void SCIPexprgraphSetVarBounds(SCIP_EXPRGRAPH *exprgraph, void *var, SCIP_INTERVAL varbounds) Definition: expr.c:14747 #define ensureBlockMemoryArraySize(blkmem, array1, cursize, minsize) Definition: expr.c:51 void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len) static SCIP_RETCODE exprgraphRemoveVar(SCIP_EXPRGRAPH *exprgraph, int varidx) Definition: expr.c:11857 Definition: type_expr.h:46 Definition: type_expr.h:39 void SCIPintervalQuad(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL xrng) Definition: intervalarith.c:2775 void SCIPexprgraphEnableNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node) Definition: expr.c:14305 SCIP_QUADELEM * SCIPexprgraphGetNodeQuadraticQuadElements(SCIP_EXPRGRAPHNODE *node) Definition: expr.c:12920 |