expr.c
Go to the documentation of this file.
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
64 #ifdef SCIP_DISABLED_CODE /* this macro is currently not used, which offends lint, so disable it */
112 /* calculate the size with this loop, such that the resulting numbers are always the same (-> block memory) */
147 /** 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) */
167 /** 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) */
252 /** gives curvature for base^exponent for given bounds and curvature of base-function and constant exponent */
281 /* if basebounds contains 0.0, consider negative and positive interval separately, if possible */
287 /* 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 */
294 return (SCIP_EXPRCURV) (SCIPexprcurvPower(leftbounds, basecurv, exponent) & SCIPexprcurvPower(rightbounds, basecurv, exponent));
298 /* (base^exponent)'' = exponent * ( (exponent-1) base^(exponent-2) (base')^2 + base^(exponent-1) base'' )
303 * - for base > 0.0 and 0.0 < exponent < 1.0, we can't say (first sommand negative, second summand positive)
309 * - for base > 0.0 and exponent > 1.0, we can't say (first summand positive, second summand negative)
358 * See Maranas and Floudas, Finding All Solutions of Nonlinearly Constrained Systems of Equations, JOGO 7, 1995
450 * - 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
515 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*quadraticdata)->lincoefs, lincoefs, nchildren) );
520 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*quadraticdata)->quadelems, quadelems, nquadelems) );
617 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &monomialdata->childidxs, monomialdata->factorssize, newsize) );
618 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &monomialdata->exponents, monomialdata->factorssize, newsize) );
634 SCIP_Bool copymonomials /**< whether to copy monomials, or copy only given pointers, in which case polynomialdata assumes ownership of monomial structure */
661 monomials[i]->coef, monomials[i]->nfactors, monomials[i]->childidxs, monomials[i]->exponents) ); /*lint !e613*/
666 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, monomials, nmonomials) );
692 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, (*polynomialdata)->monomialssize) );
697 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &(*polynomialdata)->monomials[i], sourcepolynomialdata->monomials[i]->coef,
698 sourcepolynomialdata->monomials[i]->nfactors, sourcepolynomialdata->monomials[i]->childidxs, sourcepolynomialdata->monomials[i]->exponents) );
732 BMSfreeBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, (*polynomialdata)->monomialssize);
750 ensureBlockMemoryArraySize(blkmem, &polynomialdata->monomials, &polynomialdata->monomialssize, minsize);
775 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials + nmonomials) );
783 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials + i],
784 monomials[i]->coef, monomials[i]->nfactors, monomials[i]->childidxs, monomials[i]->exponents) ); /*lint !e613*/
789 BMScopyMemoryArray(&polynomialdata->monomials[polynomialdata->nmonomials], monomials, nmonomials); /*lint !e866*/
823 SCIPsortPtr((void**)polynomialdata->monomials, monomialdataCompare, polynomialdata->nmonomials);
849 /* merge monomials by adding their coefficients, eliminate monomials with no factors or zero coefficient*/
886 if( monomialdataCompare((void*)polynomialdata->monomials[i], (void*)polynomialdata->monomials[i+offset+1]) != 0 )
947 SCIPexprChgMonomialCoef(polynomialdata->monomials[i], polynomialdata->monomials[i]->coef * factor);
977 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i], factor, childmap) );
983 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials+1) );
984 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials], polynomialdata->constant, 0, NULL, NULL) );
985 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[polynomialdata->nmonomials], factor, childmap) );
1024 SCIP_CALL( polynomialdataMultiplyByMonomial(blkmem, polynomialdata, factordata->monomials[0], childmap) );
1031 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials+1) );
1032 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials], polynomialdata->constant, 0, NULL, NULL) );
1038 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials * (factordata->nmonomials + (factordata->constant == 0.0 ? 0 : 1))) );
1046 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 */
1047 SCIP_CALL( polynomialdataAddMonomials(blkmem, polynomialdata, orignmonomials, polynomialdata->monomials, TRUE) );
1053 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i1], factordata->monomials[i2], childmap) );
1068 SCIPexprChgMonomialCoef(polynomialdata->monomials[i1], polynomialdata->monomials[i1]->coef * factordata->constant);
1076 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i1], factordata->monomials[i2], childmap) );
1196 int maxexpansionexponent,/**< maximal exponent for which polynomials (with > 1 summands) are expanded */
1223 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && factorpolynomial->constant < 0.0 ) /*lint !e835*/
1225 /* if polynomial is a negative constant and our exponent is not integer, then cannot do expansion */
1226 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n", factorpolynomial->constant, monomial->exponents[factorpos]);
1259 /* if coefficient of monomial is negative and our exponent is not integer, then do not do expansion
1260 * @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
1267 /* @todo if there is an even number of factors in factormonomial that are negative, then they always multiply to something positive
1270 * MINLPLib instances tls2,4,6 are examples where we are loosing here (do not recognize convexity)
1277 SCIP_CALL( monomialdataEnsureFactorsSize(blkmem, monomial, monomial->nfactors + factormonomial->nfactors) );
1282 /* can do this because monomial->exponents[factorpos] is assumed to be integer or factormonomial has positive coefficient and only one factor
1283 * thus, if factormonomial->exponents[i] is fractional, then we can assume that it's argument is positive
1304 /* if exponent is negative or fractional and the polynomial is not just a monomial, then we cannot do expansion */
1305 if( !EPSISINT(monomial->exponents[factorpos], 0.0) || monomial->exponents[factorpos] < 0.0 ) /*lint !e835*/
1319 * that is, assume monomial is f1^a1 f2^a2 ... and we want to expand f1 = (g11^beta11 g12^beta12... + g21^beta21 g22^beta22 ... + ...)
1320 * then we do this only if all ai and all beta are > 0.0 and a1 max(beta11+beta12+..., beta21+beta22+..., ...) + a2 + ... < maxexpansionexponent
1323 if( maxexpansionexponent < INT_MAX && (monomial->nfactors > 1 || monomial->exponents[factorpos] != 1.0) )
1350 SCIPdebugMessage("skip expansion because %d'th factor in %d'th monomial of factorpolynomial is negative\n", i, j);
1359 SCIPdebugMessage("skip expansion because degree of %d'th monomial would yield degree %g > max = %d in expansion\n",
1372 SCIP_CALL( polynomialdataPower(blkmem, factorpolynomialcopy, (int)EPSFLOOR(monomial->exponents[factorpos], 0.0)) ); /*lint !e835*/
1389 polynomialdata->monomials[monomialpos] = polynomialdata->monomials[polynomialdata->nmonomials-1];
1394 SCIP_CALL( polynomialdataAddMonomials(blkmem, polynomialdata, factorpolynomialcopy->nmonomials, factorpolynomialcopy->monomials, FALSE) );
1408 /** a default implementation of expression interval evaluation that always gives a correct result */
1417 /** a default implementation of expression curvature check that always gives a correct result */
1652 #if defined(__GNUC__) && __GNUC__ * 100 + __GNUC_MINOR__ * 10 >= 490 && !defined(__INTEL_COMPILER)
1695 * if both nominator and denominator are not constant, then quotient may not be convex nor concave
1840 #if defined(__GNUC__) && __GNUC__ * 100 + __GNUC_MINOR__ * 10 >= 490 && !defined(__INTEL_COMPILER)
2126 /* erf and erfi do not seem to exist on every system, and we cannot really handle them anyway, so they are currently disabled */
2433 * if only one factor is not constant, then product is curvature of this factor, multiplied by sign of product of remaining factors
2531 /* for a linear expression, we need to copy the array that holds the coefficients and constant term */
2533 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &targetdata, (SCIP_Real*)opdatasource.data, nchildren + 1) ); /*lint !e866*/
2586 *result += quadelems->coef * argvals[quadelems->idx1] * argvals[quadelems->idx2]; /*lint !e613*/
2658 SCIPdebugMessage("%g x^2 + %g y^2 + %g x y + %g x + %g y = [%g,%g] for x = [%g,%g], y = [%g,%g]\n",
2660 result->inf, result->sup, argvals[0].inf, argvals[0].sup, argvals[1].inf, argvals[1].sup); /*lint !e613*/
2672 /* for each argument, we collect it's linear index from lincoefs, it's square coefficients and all factors from bilinear terms
2681 /* there are no quadratic terms with argidx in its first argument, that should be easy to handle */
2702 SCIPintervalMulScalar(infinity, &tmp, argvals[quadelems[i].idx2], quadelems[i].coef); /*lint !e613*/
2764 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef * argbounds[quadelems[i].idx1].inf, argcurv[quadelems[i].idx2]));
2769 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef * argbounds[quadelems[i].idx2].inf, argcurv[quadelems[i].idx1]));
2774 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef, SCIPexprcurvPower(argbounds[quadelems[i].idx1], argcurv[quadelems[i].idx1], 2.0)));
2799 sourcedata->constant, nchildren, sourcedata->lincoefs, sourcedata->nquadelems, sourcedata->quadelems) );
3046 /* we assume that some simplifier was running, so that monomials do not have constants in their factors and such that all factors are different
3050 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(monomial->coef, SCIPexprcurvMonomial(monomial->nfactors, monomial->exponents, monomial->childidxs, argcurv, argbounds)));
3113 SCIP_CALL( exprdata->inteval(infinity, exprdata->userdata, nargs, argvals, result, NULL, NULL) );
3117 /* if user does not provide interval evaluation, then return a result that is always correct */
3138 /* if user does not provide curvature check, then return unknown (which is handled like indefinite) */
3164 SCIP_CALL( exprdatasource->copydata(blkmem, nchildren, exprdatasource->userdata, &exprdatatarget->userdata) );
3209 SCIP_DECL_EXPRCOPYDATA ((*copydata)); /**< expression data copy function, or NULL to only opdata union */
3210 SCIP_DECL_EXPRFREEDATA ((*freedata)); /**< expression data free function, or NULL if nothing to free */
3215 /** table containing for each operand the name, the number of children, and some evaluation functions */
3246 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY,
3247 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY,
3248 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY,
3252 { "linear", -2, exprevalLinear, exprevalIntLinear, exprcurvLinear, exprCopyDataLinear, exprFreeDataLinear },
3253 { "quadratic", -2, exprevalQuadratic, exprevalIntQuadratic, exprcurvQuadratic, exprCopyDataQuadratic, exprFreeDataQuadratic },
3254 { "polynomial", -2, exprevalPolynomial, exprevalIntPolynomial, exprcurvPolynomial, exprCopyDataPolynomial, exprFreeDataPolynomial },
3255 { "user", -2, exprevalUser, exprevalIntUser, exprcurvUser, exprCopyDataUser, exprFreeDataUser }
3317 /** tries to convert a given (operator,operatordata) pair into a polynomial operator with corresponding data
3654 SCIP_CALL( polynomialdataCreate(blkmem, &polynomialdata, 0, NULL, lineardata[nchildren], FALSE) );
3696 SCIP_CALL( polynomialdataCreate(blkmem, &polynomialdata, 0, NULL, quaddata->constant, FALSE) );
3698 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, (quaddata->lincoefs != NULL ? nchildren : 0) + quaddata->nquadelems) );
3834 /* polynomial simplification and monomial merging should ensure that monomial i corresponds to child i and that there are not unused children */
3838 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == 1.0 && polynomialdata->monomials[1]->coef == 1.0 )
3855 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == 1.0 && polynomialdata->monomials[1]->coef == -1.0 )
3872 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == -1.0 && polynomialdata->monomials[1]->coef == 1.0 )
3922 * that monomials are ordered according to the child index, and that constant monomials have been removed
3944 if( maxdegree == 2 && (polynomialdata->nmonomials > 1 || polynomialdata->constant != 0.0 || polynomialdata->monomials[0]->coef != 1.0) )
3946 /* 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 */
3951 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &quaddata->quadelems, polynomialdata->nmonomials - nlinmonomials) );
3967 assert(polynomialdata->monomials[i]->nfactors == 1 || polynomialdata->monomials[i]->nfactors == 2);
3974 quaddata->lincoefs[polynomialdata->monomials[i]->childidxs[0]] += polynomialdata->monomials[i]->coef;
3993 quaddata->quadelems[quadelemidx].idx1 = MIN(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]);
3994 quaddata->quadelems[quadelemidx].idx2 = MAX(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]);
4009 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 1 && polynomialdata->monomials[0]->coef == 1.0 )
4101 if( monomial->nfactors == 2 && monomial->exponents[0] == 1.0 && monomial->exponents[1] == -1.0 )
4115 if( monomial->nfactors == 2 && monomial->exponents[0] == -1.0 && monomial->exponents[1] == 1.0 )
4140 /** adds copies of expressions to the array of children of a sum, product, linear, quadratic, or polynomial expression
4142 * For a sum or product expression, this corresponds to add additional summands and factors, resp.
4144 * For a quadratic or polynomial expression, only the children array may be enlarged, the expression itself remains the same.
4152 SCIP_Bool comparechildren, /**< whether to compare expressions with already existing children (no effect for sum and product) */
4154 int* childmap /**< array where to store mapping of indices from exprs to children array in expr, or NULL if not of interest */
4161 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);
4172 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) );
4175 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren + i], exprs[i]) ); /*lint !e613*/
4193 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) );
4201 if( expr->children[j] != NULL && SCIPexprAreEqual(expr->children[j], exprs[i], eps) ) /*lint !e613*/
4210 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren], exprs[i]) ); /*lint !e613*/
4229 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, orignchildren + nexprs, expr->nchildren) );
4237 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, orignchildren + 1, expr->nchildren + 1) );
4249 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data->lincoefs, orignchildren, expr->nchildren) );
4250 BMSclearMemoryArray(&data->lincoefs[orignchildren], expr->nchildren - orignchildren); /*lint !e866*/
4396 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, lastnonnull+1) );
4458 * exprsimplifyConvertToPolynomials should have been called before to eliminate simple polynomial operands.
4466 int maxexpansionexponent/**< maximal exponent for which we still expand non-monomial polynomials */
4475 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr->children[i], eps, maxexpansionexponent) );
4505 if( (expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) ||
4511 /* since child0 has no children and it's polynomial was flattened, it should have no monomials */
4512 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0);
4536 if( ((expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) || expr->children[0]->op == SCIP_EXPR_CONST) &&
4537 ((expr->children[1]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[1]) == 0) || expr->children[1]->op == SCIP_EXPR_CONST) )
4542 /* since children have no children and it's polynomial was flattened, it should have no monomials */
4543 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0);
4544 assert(expr->children[1]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[1]) == 0);
4597 * 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
4625 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
4640 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && SCIPexprGetOpReal(expr->children[i]) < 0.0 ) /*lint !e835*/
4643 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n",
4698 SCIP_CALL( exprsimplifyAddChildren(blkmem, expr, expr->children[i]->nchildren, expr->children[i]->children, TRUE, eps, childmap) );
4708 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
4723 SCIP_CALL( polynomialdataExpandMonomialFactor(blkmem, messagehdlr, polynomialdata, j, factorpos,
4724 (SCIP_EXPRDATA_POLYNOMIAL*)expr->children[i]->data.data, childmap, maxexpansionexponent, &success) );
4735 /* expansion may remove monomials[j], move a monomial from the end to position j, or add new monomials to the end of polynomialdata
4796 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part */
4860 if( childusage[childidx] == 1 && varsusage[SCIPexprGetOpIndex(expr->children[childidx])] == 1 )
4862 /* if the child expression is not used in another monomial (which would due to merging be not linear)
4909 SCIP_CALL( exprUnconvertPolynomial(blkmem, &expr->op, &expr->data, expr->nchildren, (void**)expr->children) );
4922 * Creates a new variable index if variable not seen before, updates varnames and vartable structures.
4932 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */
4934 const char* varnameendptr /**< if a <varname> should be parsed, set this to NULL. Then, str points to the '<'
4962 SCIPerrorMessage("Variable name %.*s is too long for buffer in exprparseReadVariable.\n", namelength, str);
4985 SCIPerrorMessage("Buffer in exprparseReadVariable is too short for varaible name %.*s.\n", namelength, str);
5021 /** if str[0] points to an opening parenthesis, this function sets endptr to point to the matching closing bracket in str
5051 SCIPerrorMessage("unable to find closing parenthesis in unbalanced expression %.*s\n", length, str);
5088 SCIPerrorMessage("unable to find separating comma in unbalanced expression %.*s\n", length, str);
5107 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */
5134 SCIPdebugMessage("exprParse (%i): parsing %.*s\n", recursiondepth, (int) (lastchar-str + 1), str);
5147 while( subexpptr != lastchar && !(nopenbrackets == 0 && (subexpptr[0] == '+' || subexpptr[0] == '-') && subexpptr != str) )
5158 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str, (int) ((subexpptr - 1) - str + 1), subexpptr - 1, nvars,
5163 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, subexpptr , (int) (lastchar - (subexpptr ) + 1), lastchar, nvars,
5167 * we always use add, because we leave the operator between the found expressions in the second argument
5168 * this way, we do not have to worry about ''minus brackets'' in the case of more then two summands:
5200 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, subexpptr, subexplength, subexpendptr, nvars, varnames,
5229 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, str, (int)(lastchar - str) + 1, lastchar, nvars, varnames,
5247 SCIP_CALL( exprparseReadVariable(blkmem, &str, expr, nvars, varnames, varnameslength, vartable, 1.0, NULL) );
5254 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5274 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5327 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5335 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, comma, endptr - comma, endptr - 1, nvars, varnames,
5356 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5363 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) )
5391 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5398 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) )
5422 /* check for a variable, that was not recognized earlier because somebody omitted the '<' and '>' we need for
5428 /* allow only variable names containing characters, digits, hash marks, and underscores here */
5432 SCIP_CALL( exprparseReadVariable(blkmem, &varnamestartptr, expr, nvars, varnames, varnameslength,
5454 SCIPerrorMessage("error finding first expression in \"%.*s\" took us outside of given subexpression length\n", length, strstart);
5482 if( isdigit((unsigned char)str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit((unsigned char)str[1])) )
5512 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5560 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames,
5618 /* if there is a part of the string left to be parsed, we assume that this as a multiplication */
5628 SCIPdebugMessage("No operator found, assuming a multiplication before %.*s\n", (int) (lastchar - str + 1), str);
5631 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames,
5798 /* the coefficients are stored in the first nchildren elements of the array stored as expression data */
6129 SCIPerrorMessage("cannot create complex expression linear, quadratic, polynomial, or user with SCIPexprCreate\n");
6159 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*targetexpr)->children, sourceexpr->nchildren) );
6169 assert((*targetexpr)->children == NULL); /* otherwise, sourceexpr->children was not NULL, which is wrong */
6177 SCIP_CALL( exprOpTable[sourceexpr->op].copydata(blkmem, sourceexpr->nchildren, sourceexpr->data, &(*targetexpr)->data) );
6242 /** creates an expression from the addition of two given expression, with coefficients, and a constant
6244 * The given expressions may be modified or freed, otherwise it will be used a child expression.
6345 if( SCIPexprGetOperator(term1) == SCIP_EXPR_LINEAR && SCIPexprGetOperator(term2) == SCIP_EXPR_LINEAR )
6351 SCIP_CALL( SCIPexprAddToLinear(blkmem, term1, SCIPexprGetNChildren(term2), SCIPexprGetLinearCoefs(term2), SCIPexprGetChildren(term2), SCIPexprGetLinearConstant(term2) + constant) );
6402 * The given expressions may be modified or freed, otherwise it will be used a child expression.
6502 /** creates a SCIP_EXPR_LINEAR expression that is (affine) linear in its children: constant + sum_i coef_i child_i */
6527 /* we store the coefficients and the constant in a single array and make this our operand data */
6570 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nchildren) );
6574 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, expr->nchildren + 1, expr->nchildren + nchildren + 1) );
6584 /** creates a SCIP_EXPR_QUADRATIC expression: constant + sum_i coef_i child_i + sum_i coef_i child1_i child2_i */
6611 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) );
6632 /** creates a SCIP_EXPR_POLYNOMIAL expression from an array of monomials: constant + sum_i monomial_i */
6659 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) );
6684 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, nmonomials, monomials, copymonomials) );
6730 SCIP_CALL( polynomialdataMultiplyByMonomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, factor, childmap) );
6738 * Children of factor need to be children of expr already, w.r.t. an optional mapping of child indices.
6776 SCIP_CALL( polynomialdataMultiplyByPolynomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, (SCIP_EXPRDATA_POLYNOMIAL*)factor->data.data, childmap) );
6797 SCIP_CALL( polynomialdataPower(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, exponent) );
6802 /** merges monomials in a polynomial expression that differ only in coefficient into a single monomial
6817 polynomialdataMergeMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, eps, mergefactors);
6882 BMScopyMemoryArray(&monomial->childidxs[monomial->nfactors], childidxs, nfactors); /*lint !e866*/
6883 BMScopyMemoryArray(&monomial->exponents[monomial->nfactors], exponents, nfactors); /*lint !e866*/
6909 SCIP_CALL( SCIPexprAddMonomialFactors(blkmem, monomial, factor->nfactors, factor->childidxs, factor->exponents) );
6987 while( i+offset+1 < monomial->nfactors && monomial->childidxs[i] == monomial->childidxs[i+offset+1] )
7059 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->childidxs, childidxs, nfactors) );
7072 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->exponents, exponents, nfactors) );
7134 * Note that if the factors have not been merged, the position of some factor corresponding to a given child is given.
7160 SCIP_EXPRINTCAPABILITY evalcapability, /**< capability of evaluation functions (partially redundant, currently) */
7162 SCIP_DECL_USEREXPRINTEVAL ((*inteval)), /**< interval evaluation function, or NULL if not implemented */
7164 SCIP_DECL_USEREXPRPROP ((*prop)), /**< interval propagation function, or NULL if not implemented */
7165 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */
7166 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */
7167 SCIP_DECL_USEREXPRFREEDATA ((*freedata)), /**< expression data free function, or NULL if nothing to free */
7168 SCIP_DECL_USEREXPRPRINT ((*print)) /**< expression print function, or NULL for default string "user" */
7178 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */
7179 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */
7339 else if( expr->data.dbl > 0.0 && (int)expr->data.dbl == expr->data.dbl ) /* natural exponent gives polynomial again */ /*lint !e777*/
7468 /* if no linear or no quadratic coefficient with current child on first position, then nothing to do */
7480 while( quadidx < quadraticdata->nquadelems && quadraticdata->quadelems[quadidx].idx1 == childidx )
7491 SCIP_CALL( SCIPexprGetMaxDegree(expr->children[quadraticdata->quadelems[quadidx].idx2], &child2) );
7531 /* if the exponent of the factor is not a natural number and the child is not constant (degree 0),
7533 if( child1 != 0 && (monomialdata->exponents[j] < 0.0 || (int)monomialdata->exponents[j] != monomialdata->exponents[j]) )
7612 return SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps) && SCIPexprAreEqual(expr1->children[1], expr2->children[1], eps);
7630 return EPSEQ(expr1->data.dbl, expr2->data.dbl, eps) && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps);
7633 return expr1->data.intval == expr2->data.intval && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps);
7794 * If linear variables are split off, expression interpreter data, if stored in the tree, is freed.
7801 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
7803 int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */
7804 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */
7822 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr, eps, maxexpansionexponent) );
7831 SCIP_CALL( exprsimplifySeparateLinearFromPolynomial(blkmem, expr, eps, nvars, nlinvars, linidxs, lincoefs) );
7851 SCIP_Real* varvals, /**< values for variables, can be NULL if the expression operand is not a variable */
7852 SCIP_Real* param, /**< values for parameters, can be NULL if the expression operand is not a parameter */
7861 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, argvals, varvals, param, val) );
7870 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7896 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, buf, varvals, param, val) );
7911 SCIP_INTERVAL* argvals, /**< interval values for children, can be NULL if the expression has no children */
7912 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */
7913 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7922 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, argvals, varvals, param, val) );
7931 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */
7932 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7953 SCIP_CALL( SCIPexprEvalInt(expr->children[i], infinity, varvals, param, &buf[i]) ); /*lint !e644*/
7958 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, buf, varvals, param, val) );
7987 SCIP_CALL( exprdata->eval(exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) );
7999 SCIP_INTERVAL* hessian /**< buffer to store values of full Hessian, or NULL if not requested */
8019 SCIP_CALL( exprdata->inteval(infinity, exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) );
8032 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
8047 SCIP_CALL( SCIPexprCheckCurvature(expr->children[i], infinity, varbounds, param, &childcurv[i], &childbounds[i]) ); /*lint !e644*/
8056 SCIP_CALL( exprOpTable[expr->op].curv(infinity, expr->data, expr->nchildren, childbounds, childcurv, curv) );
8057 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, childbounds, varbounds, param, bounds) );
8067 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
8094 retcode = doCheckCurvature(expr, infinity, varbounds, childbounds, param, curv, childcurv, bounds);
8107 /** under-/overestimates a user expression w.r.t. to given values and bounds for children expressions */
8114 SCIP_Real* coeffs, /**< buffer to store the linear coefficients for each child expression that gives a valid under-/overestimator */
8115 SCIP_Real* constant, /**< buffer to store the constant value of the linear under-/overestimator */
8130 SCIP_CALL( exprdata->estimate(infinity, exprdata->userdata, expr->nchildren, argvals, argbounds, overestimate, coeffs, constant, success ) );
8239 /* @Note: 'expr->data.intval' is either between 0 and number of variables-1, if it uses the varnames array, or
8441 SCIPexprPrint(expr->children[quadraticdata->quadelems[i].idx1], messagehdlr, file, varnames, paramnames, paramvals);
8449 SCIPexprPrint(expr->children[quadraticdata->quadelems[i].idx2], messagehdlr, file, varnames, paramnames, paramvals);
8483 SCIPexprPrint(expr->children[monomialdata->childidxs[j]], messagehdlr, file, varnames, paramnames, paramvals);
8563 * for each variable, we store its name, prefixed with the assigned index in the first sizeof(int) bytes
8565 SCIP_CALL( SCIPhashtableCreate(&vartable, blkmem, 10, exprparseVarTableGetKey, SCIPhashKeyEqString,
8568 retcode = exprParse(blkmem, messagehdlr, expr, str, (int) (lastchar - str + 1), lastchar, nvars, &varnames,
8694 /** indicates whether there are parameterized constants (SCIP_EXPR_PARAM) in expression tree */
8778 SCIP_Real* params /**< values for parameters, or NULL (if NULL but nparams > 0, then params is initialized with zeros) */
8835 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*targettree)->vars, sourcetree->vars, sourcetree->nvars) );
8843 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*targettree)->params, sourcetree->params, sourcetree->nparams) );
8925 * If linear variables are split off, expression interpreter data, if stored in the tree, is freed.
8931 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
8932 int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */
8933 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */
8958 /* we should be careful about declaring numbers close to zero as zero, so take eps^2 as tolerance */
8959 SCIP_CALL( SCIPexprSimplify(tree->blkmem, messagehdlr, tree->root, eps*eps, maxexpansionexponent, tree->nvars, nlinvars, linidxs, lincoefs) );
8966 assert(testval_before != testval_before || testval_before == testval_after || EPSZ(SCIPrelDiff(testval_before, testval_after), eps)); /*lint !e777*/
8979 * 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.
9010 /** tries to determine the curvature type of an expression tree w.r.t. given variable domains */
9033 SCIP_CALL( SCIPexprCheckCurvature(tree->root, infinity, varbounds, tree->params, curv, &exprbounds) );
9088 * 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
9090 #define QUADELEMS_ISBETTER(a, b) ( ((a).idx1 < (b).idx1) || ((a).idx1 == (b).idx1 && (a).idx2 < (b).idx2) )
9100 /** quicksort an array of quadratic elements; pivot is the medial element (taken from scip/sorttpl.c) */
9149 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
9150 assert(!QUADELEMS_ISBETTER(elems[mid], pivotkey)); /* the pivot element did not change its position */
9233 * If (idx1,idx2) is found in quadelems, then returns TRUE and stores position of quadratic element in *pos.
9234 * 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.
9242 int* pos /**< buffer to store position of found quadratic element or position where it would be inserted, or NULL */
9267 if( idx1 < quadelems[middle].idx1 || (idx1 == quadelems[middle].idx1 && idx2 < quadelems[middle].idx2) ) /*lint !e613*/
9269 else if( quadelems[middle].idx1 < idx1 || (quadelems[middle].idx1 == idx1 && quadelems[middle].idx2 < idx2) ) /*lint !e613*/
9334 /* now i should point to the position after the last valid element, i.e., it is the remaining number of elements */
9367 node->parentssorted = (node->nparents <= 1) || (node->parentssorted && (exprgraphnodecomp((void*)node->parents[node->nparents-2], (void*)parent) <= 0));
9402 SCIP_EXPRGRAPHNODE** node, /**< expression graph node where to remove a parent, *node will be set to NULL */
9422 (void) SCIPsortedvecFindPtr((void**)(*node)->parents, exprgraphnodecomp, (void*)parent, (*node)->nparents, &pos);
9469 return SCIPsortedvecFindPtr((void**)node->parents, exprgraphnodecomp, (void*)parent, node->nparents, &pos);
9472 /** adds expression graph nodes to the array of children of a sum, product, linear, quadratic, or polynomial expression
9474 * For a sum or product expression, this corresponds to add additional summands and factors, resp.
9476 * For a quadratic or polynomial expression, only the children array may be enlarged, the expression itself remains the same.
9487 int* childmap /**< array where to store mapping of indices from exprs to children array in node, or NULL if not of interest */
9499 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);
9506 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, node->nchildren, node->nchildren + nexprs) );
9547 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, orignchildren + nexprs, node->nchildren) );
9555 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, orignchildren + 1, node->nchildren + 1) );
9567 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data->lincoefs, orignchildren, node->nchildren) );
9568 BMSclearMemoryArray(&data->lincoefs[orignchildren], node->nchildren - orignchildren); /*lint !e866*/
9601 SCIPdebugMessage("replace child %p in node %p by %p\n", (void*)*oldchild, (void*)node, (void*)newchild);
9639 assert(((SCIP_EXPRGRAPHNODE*)elem1)->data.dbl == ((SCIP_EXPRGRAPHNODE*)elem1)->data.dbl); /* assert that const value is not nan */ /*lint !e777*/
9640 assert(((SCIP_EXPRGRAPHNODE*)elem2)->data.dbl == ((SCIP_EXPRGRAPHNODE*)elem2)->data.dbl); /* assert that const value is not nan */ /*lint !e777*/
9712 while( exprgraph->constnodes[*pos] != node && *pos > 0 && exprgraph->constnodes[*pos-1]->data.dbl == node->data.dbl ) /*lint !e777*/
9715 while( exprgraph->constnodes[*pos] != node && *pos < exprgraph->nconsts-1 && exprgraph->constnodes[*pos+1]->data.dbl == node->data.dbl ) /*lint !e777*/
9753 /* set initial curvature to linear for variables, parameters, and constants and unknown otherwise */
9800 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9803 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9808 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9811 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9816 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9819 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9824 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9827 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9832 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9838 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9853 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9872 SCIPmessageFPrintInfo(messagehdlr, file, "(c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9874 SCIPmessageFPrintInfo(messagehdlr, file, ",c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9885 SCIPmessageFPrintInfo(messagehdlr, file, "c%d[%10g,%10g]", i, node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9897 SCIPmessageFPrintInfo(messagehdlr, file, "c%d[%10g,%10g]", i, node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9922 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9945 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9958 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[quadraticdata->quadelems[i].idx1]->bounds.inf, node->children[quadraticdata->quadelems[i].idx1]->bounds.sup);
9965 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[quadraticdata->quadelems[i].idx2]->bounds.inf, node->children[quadraticdata->quadelems[i].idx2]->bounds.sup);
10000 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[monomialdata->childidxs[j]]->bounds.inf, node->children[monomialdata->childidxs[j]]->bounds.sup);
10039 SCIPmessageFPrintInfo(messagehdlr, file, "n%d_%d [fillcolor=\"%g,%g,%g\", label=\"", node->depth, node->pos, color, color, color);
10060 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);
10095 SCIP_CALL( exprOpTable[node->op].eval(node->data, node->nchildren, buf, varvals, NULL, &node->value) );
10133 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a bound recalculation in parent nodes */
10134 SCIP_Bool parenttightenisinvalid /**< whether to consider bounds that have been tightened by parents as invalid */
10143 assert(node->depth >= 1); /* node should be in graph and not be at depth 0 (i.e., no variable, constant, or parameter) */
10176 SCIP_CALL( exprOpTable[node->op].inteval(infinity, node->data, node->nchildren, childbounds, NULL, NULL, &newbounds) );
10184 /* NOTE: if you change code below, please make analog changes also in SCIPexprgraphUpdateNodeBoundsCurvature */
10186 /* if bounds of a children were relaxed or our bounds were tightened by a (now possibly invalid) reverse propagation from a parent
10187 * and now our bounds are relaxed, then we have to propagate this upwards to ensure valid bounds
10189 * if bounds were tightened (considerably), then tell this to those parents which think that they have valid bounds
10191 * finally, if there was only a little tightening, then keep this updated bounds, but don't notify parents
10194 ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED) || ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) && parenttightenisinvalid)) )
10214 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);
10228 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */
10229 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
10241 assert(!SCIPintervalIsEmpty(infinity, node->bounds)); /* should not call backward prop. for a node that yield a cutoff already */
10242 assert(!node->enabled || !(node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED)); /* there should be no unprocessed relaxations of children bounds, if node is enabled */
10244 /* if we have no recent bound tightening from a parent, then no use in reverse-propagating our bounds */
10253 if( (node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE) == SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE )
10259 /* 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);
10280 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10286 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10297 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10303 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10314 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10320 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10331 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10337 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10356 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10367 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10376 SCIPintervalPowerScalarInverse(infinity, &childbounds, node->children[0]->bounds, node->data.dbl, node->bounds);
10383 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10404 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10413 SCIPintervalPowerScalarInverse(infinity, &childbounds, node->children[0]->bounds, (SCIP_Real)node->data.intval, node->bounds);
10420 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10437 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10448 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10487 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10500 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10515 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10522 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10538 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10543 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10609 /* if there are too many unbounded bounds, then could only compute infinite bounds for children, so give up */
10621 * node->bounds.sup - (minlinactivity - c_i.inf), if c_i.inf > -infinity and minlinactivityinf == 0
10635 childbounds.sup = SCIPintervalNegateReal(minlinactivity - node->bounds.sup - node->children[i]->bounds.inf);
10640 * node->bounds.inf - (maxlinactivity - c_i.sup), if c_i.sup < infinity and maxlinactivityinf == 0
10656 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
10687 /* if there is 0.0 in the product, then later division will hardly give useful bounds, so giveup for this i */
10694 SCIPintervalDiv(infinity, &childbounds, node->bounds, childbounds); /* f / prod_{j:j!=i} c_j */
10695 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
10796 /* SCIPdebugMessage("activity = [%10g,%10g] ninf = [%d,%d]; bounds = [%10g,%10g]\n", minlinactivity, maxlinactivity, minlinactivityinf, maxlinactivityinf, node->bounds.inf, node->bounds.sup); */
10798 /* if there are too many unbounded bounds, then could only compute infinite bounds for children, so give up */
10821 ac.sup = SCIPintervalNegateReal(SCIPintervalNegateReal(coefs[i]) * node->children[i]->bounds.sup);
10835 * (node->bounds.sup - minlinactivity)/coefs[i] + c_i.inf, if c_i.inf > -infinity and minlinactivityinf == 0
10836 * (node->bounds.sup - minlinactivity)/coefs[i], if c_i.inf == -infinity and minlinactivityinf == 1
10848 childbounds.sup = SCIPintervalNegateReal((minlinactivity - ac.inf - node->bounds.sup)/coefs[i]);
10853 * (node->bounds.inf - maxlinactivity)/coefs[i] + c_i.sup, if c_i.sup < infinity and maxlinactivityinf == 0
10854 * (node->bounds.inf - maxlinactivity)/coefs[i], if c_i.sup == infinity and maxlinactivityinf == 1
10875 * (node->bounds.sup - minlinactivity)/coefs[i] + c_i.sup, if c_i.sup < infinity and minlinactivityinf == 0
10876 * (node->bounds.sup - minlinactivity)/coefs[i], if c_i.sup == infinity and minlinactivityinf == 1
10887 childbounds.inf = (minlinactivity - ac.inf - node->bounds.sup)/SCIPintervalNegateReal(coefs[i]);
10892 * (node->bounds.inf - maxlinactivity)/coefs[i] + c_i.inf, if c_i.inf > -infinity and maxlinactivityinf == 0
10893 * (node->bounds.inf - maxlinactivity)/coefs[i], if c_i.inf == -infinity and maxlinactivityinf == 1
10901 childbounds.sup = SCIPintervalNegateReal((node->bounds.inf - maxlinactivity)/SCIPintervalNegateReal(coefs[i]));
10905 childbounds.sup = SCIPintervalNegateReal((node->bounds.inf - maxlinactivity + ac.sup)/SCIPintervalNegateReal(coefs[i]));
10910 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
10939 /* too expensive, runtime here is O(nchildren * nquadelems) = O(nquadelems^2) since nchildren <= 2*nquadelems usually */
10973 if( (childbounds.inf > node->children[0]->bounds.inf + 1e-9 || childbounds.sup + 1e-9 < node->children[0]->bounds.sup) )
10975 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",
10978 node->children[1]->bounds.inf, node->children[1]->bounds.sup, childbounds.inf, childbounds.sup, (int)SCIPintervalIsEmpty(infinity, childbounds)
10985 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10996 if( (childbounds.inf > node->children[1]->bounds.inf + 1e-9 || childbounds.sup + 1e-9 < node->children[1]->bounds.sup) )
10998 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",
11001 node->children[1]->bounds.inf, node->children[1]->bounds.sup, childbounds.inf, childbounds.sup, (int)SCIPintervalIsEmpty(infinity, childbounds)
11008 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
11041 SCIPintervalMulScalar(infinity, &tmp, node->children[quadelems[k].idx2]->bounds, quadelems[k].coef);
11046 SCIPintervalMulScalar(infinity, &tmp, node->children[quadelems[k].idx1]->bounds, quadelems[k].coef);
11057 SCIPintervalMul(infinity, &tmp, node->children[quadelems[k].idx1]->bounds, node->children[quadelems[k].idx2]->bounds);
11065 SCIPintervalSolveUnivariateQuadExpression(infinity, &childbounds, a, b, c, node->children[i]->bounds);
11069 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
11161 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - 2.0*n);
11171 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - n);
11190 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - 2.0*n);
11200 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - n);
11216 SCIPintervalPowerScalar(infinity, &tmp, node->children[monomial->childidxs[k]]->bounds, monomial->exponents[k]);
11252 SCIPdebugMessage("solve [%10g,%10g]c%d^%g + [%10g,%10g]c%d^%g = [%10g,%10g] for c%d^%g in [%10g,%10g]",
11253 a.inf, a.sup, i, 2*n, b.inf, b.sup, i, n, c.inf, c.sup, i, n, childpowbounds.inf, childpowbounds.sup);
11272 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
11274 /* SCIPdebugMessage("-> node %p (%d,%d): [%10g,%10g] = ", (void*)node, node->depth, node->pos, node->bounds.inf, node->bounds.sup);
11298 SCIP_CALL_ABORT( exprdata->prop(infinity, exprdata->userdata, 1, &childbounds, node->bounds, cutoff) );
11301 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
11306 SCIP_ALLOC_ABORT( BMSallocBlockMemoryArray(exprgraph->blkmem, &childrenbounds, node->nchildren) );
11310 SCIP_CALL_ABORT( exprdata->prop(infinity, exprdata->userdata, node->nchildren, childrenbounds, node->bounds, cutoff) );
11314 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[c], childrenbounds[c], minstrength, infinity, cutoff);
11443 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, node->nchildren, lastnonnull+1) );
11455 /** aims at simplifying a node in an expression graph, assuming all children have been simplified
11465 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
11488 SCIPdebugMessage("attempt simplification of node %p (%d,%d)\n", (void*)node, node->depth, node->pos);
11500 SCIPdebugMessage("turn node %p (%d,%d) into constant %g\n", (void*)node, node->depth, node->pos, node->value);
11559 * 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
11567 * if child was simplified in this round, it may have already been converted, and then nothing happens
11589 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
11602 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && node->children[i]->data.dbl < 0.0 ) /*lint !e835*/
11605 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n", node->children[i]->data.dbl, monomial->exponents[factorpos]);
11646 * if child was simplified in this round, it may have already been converted, and then nothing happens
11649 SCIP_CALL( exprConvertToPolynomial(blkmem, &node->children[i]->op, &node->children[i]->data, node->children[i]->nchildren) );
11665 SCIP_CALL( exprgraphNodeAddChildren(blkmem, node, node->children[i]->nchildren, node->children[i]->children, childmap) );
11675 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
11678 /* make sure factors are merged, should only be potentially necessary if not sorted, see also #1848 */
11696 SCIP_CALL( polynomialdataExpandMonomialFactor(blkmem, messagehdlr, polynomialdata, j, factorpos,
11697 (SCIP_EXPRDATA_POLYNOMIAL*)node->children[i]->data.data, childmap, maxexpansionexponent, &success) );
11707 /* expansion may remove monomials[j], move a monomial from the end to position j, or add new monomials to the end of polynomialdata
11772 * but if we found duplicates in the children array, then it should be reduced, and we want to count this as a change too
11814 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[i], &childexprs[i], nexprvars, varidx) ); /*lint !e613*/
11835 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, SCIP_EXPR_VARIDX, varidx[node->data.intval]) );
11851 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], node->data.dbl) ); /*lint !e613*/
11860 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], node->data.intval) ); /*lint !e613*/
11874 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], childexprs[1]) ); /*lint !e613*/
11908 SCIP_CALL( SCIPexprCreateLinear(exprgraph->blkmem, expr, node->nchildren, childexprs, (SCIP_Real*)node->data.data, ((SCIP_Real*)node->data.data)[node->nchildren]) );
11947 SCIP_CALL( exprdata->copydata(exprgraph->blkmem, node->nchildren, exprdata->userdata, &userdata) );
11954 userdata, exprdata->evalcapability, exprdata->eval, exprdata->inteval, exprdata->curv, exprdata->prop, exprdata->estimate, exprdata->copydata, exprdata->freedata, exprdata->print) );
11974 * @note The function does not clear the array first, but only increases already existing counts.
11979 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */
11997 /** checks whether a node can be put into a component when checking block separability of an expression
11999 * If a variable used by node is already in another component, components are merged and component number is updated.
12023 exprgraphNodeCheckSeparabilityComponent(node->children[i], compnr, nchildcomps, childcomps, nvars, varcomps);
12044 /* variable is already in another component, so have to merge component compnr into that component
12077 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->nodessize, &exprgraph->nnodes, &exprgraph->nodes, &exprgraph->depth, mindepth);
12081 BMSclearMemoryArray(&exprgraph->nodessize[olddepth], exprgraph->depth - olddepth); /*lint !e866*/
12082 BMSclearMemoryArray(&exprgraph->nnodes[olddepth], exprgraph->depth - olddepth); /*lint !e866*/
12088 /** remove a variable from the variables arrays, assuming that its node will be removed or converted next */
12122 SCIP_CALL( exprgraph->exprgraphvarchgidx(exprgraph, exprgraph->userdata, exprgraph->vars[exprgraph->nvars-1], exprgraph->varnodes[exprgraph->nvars-1], exprgraph->nvars-1, varidx) );
12162 SCIPdebugMessage("move node %p (%d,%d) to depth %d\n", (void*)node, node->depth, node->pos, newdepth);
12189 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[newdepth], &exprgraph->nodessize[newdepth], exprgraph->nnodes[newdepth]+1); /*lint !e866*/
12195 /* by moving the node to a new depth, the parents array in all its childrens may not be sorted anymore (parents order depends on depth) */
12202 exprgraph->nodes[olddepth][oldpos] = exprgraph->nodes[olddepth][exprgraph->nnodes[olddepth]-1];
12205 /* by moving the node to a new position, the parents array in all its children may not be sorted anymore (parents order depends on depth) */
12218 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
12221 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], node) < 0);
12225 /* adding a variable by moving it from a higher depth seems awkward, how did the variable get there in the first place? */
12230 /* nodes at depth 0 always have curvature linear, even before any curvature check was running */
12237 /** given a list of children, tries to find a common parent that represents a given operator with the same given data */
12245 SCIP_EXPR** exprchildren, /**< children of expression to consider when modifying (reordering) operator data, or NULL */
12246 SCIP_EXPRGRAPHNODE** parent /**< buffer to store parent node if any is found, or NULL if none found */
12277 (op != SCIP_EXPR_REALPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/
12278 (op != SCIP_EXPR_SIGNPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/
12279 (op != SCIP_EXPR_LINEAR || ((SCIP_Real*)opdata.data)[nchildren] == ((SCIP_Real*)children[0]->parents[p]->data.data)[nchildren]) && /*lint !e777*/
12280 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->nquadelems == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->nquadelems) &&
12281 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->constant == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->constant) && /*lint !e777*/
12282 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->nmonomials == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->nmonomials) &&
12283 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->constant == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->constant) /*lint !e777*/
12289 /* for all remaining children, remove parent candidates, that are not in their list of parents */
12295 /* if parentcands[p] is a parent of childnodes[i], then move last parent candidate to position p,
12308 SCIPdebugMessage("check %d parent candidates for expr with operator %d and %d children\n", nparentcands, op, nchildren);
12316 /* at this point, all parents in parentcands have the nodes in children as children and are of the same operator type
12317 * check if there is also one which corresponds to same expression and store that one in *parent
12345 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12346 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12358 * However, if there are duplicates in children, then it can happen that not every child of parentcands[p] is also one of the children.
12359 * So only if children equals parentcands[p]->children in some permutation, the expressions are the same.
12361 if( (parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1]) ||
12370 /* as in the case for two nodes, we need to check whether parentcands[p]->children and children are equal up to permutation */
12397 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12398 assert(parentcands[p]->nchildren == 2); /* that was the second criterium for adding a node to parentcands */
12399 /* order of operands matters, so check if childnodes have same order as children of parent candidate (and are the same nodes too) */
12400 if( parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1] )
12414 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */
12415 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */
12416 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */
12417 assert(parentcands[0]->data.intval == opdata.intval); /* that was another criterium for adding a node to parentcands */
12428 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */
12429 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */
12430 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */
12431 assert(parentcands[0]->data.dbl == opdata.dbl); /* that was another criterium for adding a node to parentcands */ /*lint !e777*/
12446 /* sort childnodes, take care that children in expression are sorted the same way if given (so we don't mess up assignment of coefficients) */
12448 SCIPsortPtrPtrReal((void**)children, (void**)exprchildren, exprcoef, exprgraphnodecomp, nchildren);
12453 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12454 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12457 assert(exprcoef[nchildren] == candcoef[nchildren]); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12493 /* sort children in expr and parentcands and update indices in quadelems accordingly, then sort quadelems again and compare */
12503 SCIPsortPtrPtrRealInt((void**)children, (void**)exprchildren, exprlincoef, invperm, exprgraphnodecomp, nchildren);
12508 SCIPsortPtrPtrInt((void**)children, (void**)exprchildren, invperm, exprgraphnodecomp, nchildren);
12534 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12535 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12539 assert(canddata->nquadelems == exprdata->nquadelems); /* that was a criterium for adding a node to parentcands */
12540 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12547 SCIPsortPtrRealInt((void**)parentcands[p]->children, candlincoef, invperm, exprgraphnodecomp, parentcands[p]->nchildren);
12571 /* check if children and linear coefficients in parent candidate and expression are the same */
12576 if( (exprlincoef == NULL ? 0.0 : exprlincoef[i]) != (candlincoef == NULL ? 0.0 : candlincoef[i]) ) /*lint !e777*/
12604 /* @todo in one GlobalLib instance, two polynoms differ only in the sign of all coefficients, it would be nice to recognize this somehow */
12614 /* sort children in expr and parentcands and update child indices in polynomialdata, then sort monomials again and compare */
12623 SCIPsortPtrPtrInt((void**)children, (void**)exprchildren, invperm, exprgraphnodecomp, nchildren);
12637 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12638 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12641 assert(canddata->nmonomials == exprdata->nmonomials); /* that was a criterium for adding a node to parentcands */
12642 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12712 SCIP_EXPRGRAPHNODE** exprnode, /**< buffer to store expression graph node corresponding to root of this expression */
12713 SCIP_Bool* exprnodeisnew /**< buffer to indicate whether the node in *exprnode has been newly created for this expression (otherwise, expression was already in graph) */
12761 /* find node corresponding to constant corresponding to parameter and add if not existing yet */
12785 SCIP_CALL( exprgraphAddExpr(exprgraph, expr->children[i], vars, params, &childnodes[i], &childisnew) ); /*lint !e644*/
12790 /* if all children were known already, check if there is also already a node for the expression that we aim to add */
12793 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, expr->nchildren, childnodes, expr->op, expr->data, expr->children, exprnode) );
12801 /* SCIPdebugMessage("reused node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos);
12816 SCIP_CALL( exprOpTable[expr->op].copydata(exprgraph->blkmem, expr->nchildren, expr->data, &opdata) );
12829 /* SCIPdebugMessage("created new node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos);
12841 SCIP_Bool* clearreverseprop, /**< flag to set if we had reset bound tightenings from reverse propagation */
12842 SCIP_Bool* boundchanged /**< buffer to store whether a variables bound has changes, compared to those stored in nodes */
12867 /* hmm, may happen due to numerics, let's be conservative and relax bounds to something that seems reasonable */
12882 SCIPdebugMessage("registered relaxed bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
12886 /* if a childs bounds are relaxed, then a previous reverse propagation may be invalid, so we have to clear its remainings */
12896 SCIPdebugMessage("registered tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
12903 SCIPdebugMessage("registered slightly tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
13148 /** gives linear coefficients belonging to a SCIP_EXPR_QUADRATIC expression, or NULL if all coefficients are 0.0 */
13243 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */
13244 assert(node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID); /* we assume node bounds to be valid */
13264 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&childcurv, monomial->nfactors), TERMINATE );
13289 *curv = SCIPexprcurvMonomial(monomial->nfactors, monomial->exponents, NULL, childcurv, childbounds);
13455 /* we store the coefficients and the constant in a single array and make this our operand data */
13484 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) );
13509 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) );
13531 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)node->data.data, nmonomials, monomials, copymonomials) );
13546 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */
13547 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */
13548 SCIP_DECL_USEREXPRFREEDATA ((*freedata)), /**< expression data free function, or NULL if nothing to free */
13549 SCIP_DECL_USEREXPRPRINT ((*print)) /**< expression print function, or NULL for default string "user" */
13558 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */
13559 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */
13583 /** given a node of an expression graph, splitup a linear part which variables are not used somewhere else in the same expression
13587 * If it is not linear, the node may change, i.e., the remaining nonlinear part may be stored in a new node.
13619 SCIPdebugMessage("split off linear part for %s node %p (%d,%d)\n", SCIPexpropGetName((*node)->op), (void*)*node, (*node)->depth, (*node)->pos);
13648 if( (*node)->data.dbl == 1.0 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13661 if( (*node)->data.intval == 1 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13674 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13685 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13696 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 )
13708 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 )
13718 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13729 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13740 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 )
13752 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 )
13762 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13770 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13837 assert(exprgraph->nvars > 0); /* in a simplified expr graph with no variables, there can only be const nodes, but these were handled above */
13854 SCIP_CALL( exprOpTable[orignode->op].copydata(exprgraph->blkmem, orignode->nchildren, orignode->data, &data) );
13860 SCIP_CALL( SCIPexprgraphAddNode(exprgraph, *node, -1, orignode->nchildren, orignode->children) );
13875 /* we had looked at this above already and only continued if exactly one node is still a child and linvarssize is >= 1 */
13876 assert((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX);
13877 assert((*node)->children[0]->op != SCIP_EXPR_VARIDX || (*node)->children[1]->op != SCIP_EXPR_VARIDX);
13880 varchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[0] : (*node)->children[1];
13881 otherchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[1] : (*node)->children[0];
13909 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, 2, 1) ); /*lint !e506*/
14001 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14112 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14113 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &coefs, (*node)->nchildren+1, nchildren+1) );
14244 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14245 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &quaddata->lincoefs, (*node)->nchildren, nchildren) );
14278 /* get nonlinear child usage: how often each child is used in the polynomial in a nonlinear monomial */
14323 /* we are at a linear monomial in a variable that is not used somewhere else in nonlinear form */
14326 linvars[*nlinvars] = exprgraph->vars[(*node)->children[childidx]->data.intval]; /*lint !e613*/
14386 /* if node was not duplicated and not removed but changed, then invalidate value, bounds, and simplified status */
14420 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, (*srcnode)->parents[0], srcnode, targetnode) );
14459 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);
14464 SCIPdebugMessage("remove node %p (%d, %d) with op %s from expression graph\n", (void*)*node, (*node)->depth, (*node)->pos, SCIPexpropGetName((*node)->op));
14506 exprgraph->nodes[(*node)->depth][(*node)->pos] = exprgraph->nodes[(*node)->depth][exprgraph->nnodes[(*node)->depth]-1];
14527 /* @todo should be a private method and node creation should already capture a node instead of waiting that it's added to the graph */
14580 /** disables a node and recursively all children which have no enabled parents in an expression graph */
14596 /* workaround: don't disable nodes if there could be more users than the one who is disabling the node
14597 * otherwise, if there are several nonlinear constraints using the same expression graph node as root node,
14612 SCIPdebugMessage("disabled node %p (%d,%d), nuses = %d\n", (void*)node, node->depth, node->pos, node->nuses);
14705 * Sets bound status to SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT if tightening is strong enough and not cutoff.
14711 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) */
14713 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
14728 SCIPdebugMessage("ignore bound tightening for node %p (%d,%d)\n", (void*)node, node->depth, node->pos);
14762 SCIPdebugPrintf(" -> [%10g, %10g] status %d\n", node->bounds.inf, node->bounds.sup, node->boundstatus);
14772 SCIP_Real minstrength, /**< minimal required relative bound strengthening to trigger a bound recalculation in parent nodes */
14773 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
14786 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */
14831 SCIP_CALL_TERMINATE( retcode, exprOpTable[node->op].inteval(infinity, node->data, node->nchildren, childbounds, NULL, NULL, &newbounds), TERMINATE );
14833 /* if bounds of a children were relaxed or our bounds were tightened by a (now possibly invalid) reverse propagation from a parent
14834 * and now our bounds are relaxed, then we have to propagate this upwards to ensure valid bounds
14836 * if bounds were tightened (considerably), then tell this to those parents which think that they have valid bounds
14838 * finally, if there was only a little tightening, then keep this updated bounds, but don't notify parents
14841 ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED) || ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) && clearreverseprop)) )
14861 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);
14872 SCIPdebugMessage("node %p(%d,%d) has empty domain in SCIPexprgraphUpdateNodeBoundsCurvature\n", (void*)node, node->depth, node->pos);
14876 SCIP_CALL_TERMINATE( retcode, exprOpTable[node->op].curv(infinity, node->data, node->nchildren, childbounds, childcurv, &node->curv), TERMINATE );
14878 /* SCIPdebugMessage("curvature %s for %s = ", SCIPexprcurvGetName(node->curv), SCIPexpropGetName(node->op));
15095 int varssizeinit, /**< minimal initial size for variables array, or -1 to choose automatically */
15096 int depthinit, /**< minimal initial depth of expression graph, or -1 to choose automatically */
15097 SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)), /**< callback method to invoke when a variable has been added to the expression graph, or NULL if not needed */
15098 SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)), /**< callback method to invoke when a variable will be removed from the expression graph, or NULL if not needed */
15099 SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)), /**< callback method to invoke when a variable changes its index in the expression graph, or NULL if not needed */
15115 ensureBlockMemoryArraySize3((*exprgraph)->blkmem, &(*exprgraph)->varnodes, &(*exprgraph)->vars, &(*exprgraph)->varbounds, &(*exprgraph)->varssize, varssizeinit);
15116 SCIP_CALL( SCIPhashmapCreate(&(*exprgraph)->varidxs, (*exprgraph)->blkmem, (*exprgraph)->varssize) );
15150 BMSfreeBlockMemoryArrayNull(blkmem, &(*exprgraph)->nodes[d], (*exprgraph)->nodessize[d]); /*lint !e866*/
15183 int mindepth, /**< minimal depth in expression graph where to add node, e.g., 0 or smaller to choose automatically */
15214 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[depth], &exprgraph->nodessize[depth], exprgraph->nnodes[depth]+1); /*lint !e866*/
15233 SCIP_ALLOC( BMSduplicateBlockMemoryArray(exprgraph->blkmem, &node->children, children, nchildren) );
15245 /* set bounds to entire, set status to "should recompute", and note that we have to update something */
15251 /* if not a variable, set value of node according to values of children (if all have valid values) */
15268 SCIP_EXPRGRAPHNODE** varnodes /**< array to store nodes corresponding to variables, or NULL if not of interest */
15279 /* 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 */
15282 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + nvars);
15283 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[0], &exprgraph->nodessize[0], exprgraph->nnodes[0] + nvars);
15311 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1);
15315 SCIP_CALL( SCIPhashmapInsertInt(exprgraph->varidxs, vars[i], exprgraph->nvars) ); /*lint !e613*/
15321 SCIPdebugMessage("added node %p (%d, %d) for new variable %d\n", (void*)node, node->depth, node->pos, node->data.intval);
15326 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[i], node) ); /*lint !e613*/
15340 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store pointer to expression graph node corresponding to constant */
15368 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
15371 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], *constnode) < 0);
15373 SCIPdebugMessage("added node %p (%d, %d) for new constant %g\n", (void*)constnode, (*constnode)->depth, (*constnode)->pos, (*constnode)->data.dbl);
15389 SCIP_EXPRGRAPHNODE** rootnode, /**< buffer to store expression graph node corresponding to root of expression tree */
15390 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) */
15409 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[0]->root, exprtrees[0]->vars, exprtrees[0]->params, rootnode, rootnodeisnew) );
15427 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[i]->root, exprtrees[i]->vars, exprtrees[i]->params, &rootnodes[i], &rootnodeisnew_) ); /*lint !e644*/
15458 /* all exprtrees were in the graph already, check if we also already have a node for the sum of rootnodes */
15459 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, op, data, NULL, rootnode) );
15490 /* all exprtrees were in the graph already, check if we also already have a node for the linear combination of rootnodes */
15491 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, SCIP_EXPR_LINEAR, data, NULL, rootnode) );
15516 rootnodeisnew ? "new" : "old", (void*)*rootnode, (*rootnode)->depth, (*rootnode)->pos, nexprtrees);
15572 SCIPdebugMessage("try to replace varnode %p (%d uses, %d parents) by %p\n", (void*)varnode, varnode->nuses, varnode->nparents, (void*)node);
15592 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varnode->children, 1) ); /*lint !e506*/
15599 varnode->boundstatus = (node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID) ? SCIP_EXPRBOUNDSTATUS_VALID : SCIP_EXPRBOUNDSTATUS_CHILDRELAXED;
15618 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
15621 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], varnode) < 0);
15633 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1);
15637 SCIP_CALL( SCIPhashmapInsertInt(exprgraph->varidxs, vars[0], exprgraph->nvars) ); /*lint !e613*/
15643 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[0], varnode) ); /*lint !e613*/
15700 SCIP_EXPRGRAPHNODE** varnode /**< buffer to store node corresponding to variable, if found, or NULL if not found */
15729 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store node corresponding to constant, if found, or NULL if not found */
15790 SCIPmessageFPrintInfo(messagehdlr, file, "node [fontcolor=white, style=filled, rankdir=LR]\n");
15847 SCIP_Bool clearreverseprop, /**< whether to reset bound tightenings from reverse propagation */
15848 SCIP_Bool* domainerror /**< buffer to store whether a node with empty bounds has been found, propagation is interrupted in this case */
15864 /* if variable bounds have not changed and we do not have to clear a previous backward propagation, we can just return */
15867 SCIPdebugMessage("no bounds changed and clearreverseprop is FALSE -> skip propagation of variable bounds\n");
15880 SCIPdebugMessage("bounds of node %p(%d,%d) empty, stop bounds propagation\n", (void*)node, node->depth, node->pos);
15896 * NOTE: it is assumed that SCIPexprgraphPropagateVarBounds was called before if variable bounds were relaxed.
15901 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */
15902 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
15926 /** updates curvature information in expression graph nodes w.r.t. currently stored variable bounds
15933 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
15961 SCIPerrorMessage("SCIPexprgraphCheckCurvature gets domain error while propagating variables bounds, ignoring...\n");
15971 * 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)).
15977 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
15979 SCIP_Bool* domainerror /**< buffer to indicate whether a domain error has been encountered, i.e., some expressions turned into NaN */
16020 /* 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 */
16050 * for each node, convert to polynomials and merge in child nodes that are not in use otherwise, if possible
16069 /* we should be careful about declaring numbers close to zero as zero, so take eps^2 as tolerance */
16070 SCIP_CALL( exprgraphNodeSimplify(exprgraph, node, messagehdlr, eps*eps, maxexpansionexponent, &havechangenode) );
16101 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be simplified */
16121 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */
16131 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */
16160 SCIP_CALL( exprUnconvertPolynomial(exprgraph->blkmem, &node->op, &node->data, node->nchildren, (void**)node->children) );
16170 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, node->parents[j], &node, node->children[0]) );
16175 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be unconverted */
16207 /* nodes that are in use should not have been removed by simplifier, check if they still have the same value in our testpoint */
16219 assert(!SCIPisFinite(testval_before) || EPSZ(SCIPrelDiff(testval_before, testval_after), eps)); /*lint !e777*/
16237 SCIP_EXPRGRAPHNODE* rootnode, /**< expression graph node that should represent root of expression tree */
16252 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
16284 /** creates a sum of expression trees with pairwise disjoint variables from a given node in an expression graph
16291 int exprtreessize, /**< length of exprtrees and exprtreecoefs arrays, need to be at least one */
16322 /* easy cases: if we have space for only one tree or there is only one child or only one variable in the graph,
16329 (node->op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1) &&
16330 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1)) )
16349 exprgraphNodeCheckSeparabilityComponent(node->children[i], &compnr, i-1, childcomp, exprgraph->nvars, varcomp); /*lint !e644*/
16372 /* reassign all children in component childcomp[data->quadelems[i].idx2] to component childcomp[data->quadelems[i].idx1] */
16391 if( childcomp[data->monomials[i]->childidxs[j]] != childcomp[data->monomials[i]->childidxs[0]] )
16393 /* reassign all children in component childcomp[data->monomials[i]->childidxs[j]] to component childcomp[data->monomials[i]->childidxs[0]] */
16398 assert(childcomp[data->monomials[i]->childidxs[j]] == childcomp[data->monomials[i]->childidxs[0]]);
16429 /* it turned out that expression is not block separable, so fallback to SCIPexprgraphGetTree */
16441 /* if we have not enough space for all expressions, merge components with number > exprtreessize into component exprtreessize */
16452 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varidx, exprgraph->nvars) ); /* mapping of expression graph variable indices to expression tree variable indices */
16453 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmap, node->nchildren) ); /* mapping of child indices from node to expressions belonging to a single component */
16454 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmapinv, node->nchildren) ); /* mapping of child indices from expressions belonging to a single component to node */
16472 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[j], &exprs[nexprs], &nexprvars, varidx) ); /*lint !e644*/
16486 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16497 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16498 /* if component i consists of first child, then it has coefficient 1.0, otherwise it has coefficient -1 */
16510 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16518 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16536 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16545 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_CONST, nodecoefs[node->nchildren]/nodecoefs[childmapinv[0]]) );
16547 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16554 if( nexprs == 2 && nodecoefs[childmapinv[0]] == nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/
16560 else if( nexprs == 2 && nodecoefs[childmapinv[0]] == -nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/
16563 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_MINUS, exprs[0], exprs[1]) );
16581 /* if all coefficients are equal and no constant, create SUM expression, otherwise LINEAR expression */
16589 SCIP_CALL( SCIPexprCreateLinear(exprgraph->blkmem, &sumexpr, nexprs, exprs, coefs, i == 0 ? nodecoefs[node->nchildren] : 0.0) );
16596 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16631 quadelems[nquadelems].idx1 = MIN(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]); /*lint !e644*/
16632 quadelems[nquadelems].idx2 = MAX(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]);
16638 SCIP_CALL( SCIPexprCreateQuadratic(exprgraph->blkmem, &quadexpr, nexprs, exprs, i == 0 ? nodedata->constant : 0.0, lincoefs, nquadelems, quadelems) );
16639 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], quadexpr, nexprvars, 0, NULL) );
16673 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomials[nmonomials], nodedata->monomials[j]->coef, nodedata->monomials[j]->nfactors,
16683 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &polyexpr, nexprs, exprs, nmonomials, monomials, i == 0 ? constant : 0.0, FALSE) );
16684 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], polyexpr, nexprvars, 0, NULL) );
16721 /** returns how often expression graph variables are used in a subtree of the expression graph */
16725 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */
16737 /** gives the number of summands which the expression of an expression graph node consists of */
16773 /** creates a sum of expression trees, possibly sharing variables, from a given node in an expression graph */
16777 int exprtreessize, /**< length of exprtrees and exptreecoefs arrays, should be at least SCIPexprgraphGetSumTreesNSummands() */
16801 (node->op != SCIP_EXPR_QUADRATIC || (((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->lincoefs == NULL && ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1)) &&
16802 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1) )
16876 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodecoefs[node->nchildren] / exprtreecoefs[0]) );
16914 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
16925 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx1], &expr, &nexprvars, varidx) );
16936 /* create expression from the subgraph at quadelems[i].idx2, may add more variables into varidx */
16937 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx2], &expr2, &nexprvars, varidx) );
16943 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) );
16948 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) );
16969 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodedata->constant / exprtreecoefs[0]) );
16998 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
17011 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) );
17022 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_INTPOWER, expr, (int)monomials[i]->exponents[0]) );
17026 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_REALPOWER, expr, monomials[i]->exponents[0]) );
17029 else if( monomials[i]->nfactors == 2 && monomials[i]->exponents[0] == 1.0 && monomials[i]->exponents[1] == 1.0 )
17034 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) );
17035 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[1]], &expr2, &nexprvars, varidx) );
17049 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childidxs, monomials[i]->nfactors) );
17052 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[f]], &exprs[f], &nexprvars, varidx) ); /*lint !e644*/
17057 * add also constant here, but need to divide by monomial coefficient, since we set the exprtreecoefs to monomial coef
17059 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomial, 1.0, monomials[i]->nfactors, childidxs, monomials[i]->exponents) );
17060 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &expr, monomials[i]->nfactors, exprs, 1, &monomial, constant / monomials[i]->coef, FALSE) );
17068 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) );
17073 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) );
17088 /* add constant to first summand, if still nonzero; need to divide by coefficient of the this exprtree */
17094 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:2095
#define SCIP_EXPRBOUNDSTATUS_CHILDRELAXED
Definition: type_expr.h:213
SCIP_Real SCIPexprgraphGetNodeVal(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13338
SCIP_RETCODE SCIPexprgraphPropagateVarBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Bool clearreverseprop, SCIP_Bool *domainerror)
Definition: expr.c:15844
void SCIPexprtreeGetVarsUsage(SCIP_EXPRTREE *tree, int *varsusage)
Definition: expr.c:8908
void SCIPquadelemSort(SCIP_QUADELEM *quadelems, int nquadelems)
Definition: expr.c:9212
SCIP_RETCODE SCIPexprgraphReplaceVarByLinearSum(SCIP_EXPRGRAPH *exprgraph, void *var, int ncoefs, SCIP_Real *coefs, void **vars, SCIP_Real constant)
Definition: expr.c:15525
void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:733
void SCIPintervalMax(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:2508
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:457
Definition: type_expr.h:57
static void exprgraphSortConstNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:9652
void SCIPexprgraphSetVarNodeValue(SCIP_EXPRGRAPHNODE *varnode, SCIP_Real value)
Definition: expr.c:14980
static SCIP_RETCODE exprgraphNodeAddParent(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE *parent)
Definition: expr.c:9345
SCIP_RETCODE SCIPexprSubstituteVars(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR **substexprs)
Definition: expr.c:8146
static SCIP_RETCODE exprsimplifyConvertToPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4266
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
Definition: intervalarith.c:405
SCIP_RETCODE SCIPexprgraphAddNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int mindepth, int nchildren, SCIP_EXPRGRAPHNODE **children)
Definition: expr.c:15180
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2364
void SCIPintervalSign(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2722
static SCIP_RETCODE eval(SCIP_EXPR *expr, const vector< Type > &x, SCIP_Real *param, Type &val)
Definition: exprinterpret_cppad.cpp:1766
static SCIP_RETCODE exprsimplifyRemoveDuplicatePolynomialChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real eps)
Definition: expr.c:4290
SCIP_RETCODE SCIPexprgraphGetSumTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs)
Definition: expr.c:16774
SCIP_RETCODE SCIPexprtreeEvalInt(SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_INTERVAL *val)
Definition: expr.c:8740
Definition: intervalarith.h:37
Definition: type_expr.h:59
SCIP_RETCODE SCIPexprgraphAddVars(SCIP_EXPRGRAPH *exprgraph, int nvars, void **vars, SCIP_EXPRGRAPHNODE **varnodes)
Definition: expr.c:15264
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:8757
int * SCIPexprGetMonomialChildIndices(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5921
SCIP_RETCODE SCIPexprgraphUpdateNodeBoundsCurvature(SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool clearreverseprop)
Definition: expr.c:14769
static SCIP_RETCODE polynomialdataMultiplyByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap)
Definition: expr.c:955
Definition: type_expr.h:72
static SCIP_RETCODE exprUnconvertPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPROP *op, SCIP_EXPROPDATA *data, int nchildren, void **children)
Definition: expr.c:3762
static SCIP_RETCODE doCheckCurvature(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varbounds, SCIP_INTERVAL *childbounds, SCIP_Real *param, SCIP_EXPRCURV *curv, SCIP_EXPRCURV *childcurv, SCIP_INTERVAL *bounds)
Definition: expr.c:8027
static SCIP_RETCODE exprgraphNodeAddChildren(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, int nexprs, SCIP_EXPRGRAPHNODE **exprs, int *childmap)
Definition: expr.c:9482
int SCIPexprgraphGetNodeNChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12974
Definition: type_expr.h:65
static SCIP_RETCODE exprgraphNodeCreateExpr(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_EXPR **expr, int *nexprvars, int *varidx)
Definition: expr.c:11790
SCIP_EXPORT SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
void SCIPexprPrint(SCIP_EXPR *expr, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames, const char **paramnames, SCIP_Real *paramvals)
Definition: expr.c:8226
static SCIP_RETCODE exprgraphEnsureDepth(SCIP_EXPRGRAPH *exprgraph, int mindepth)
Definition: expr.c:12063
static void polynomialdataSortMonomials(SCIP_EXPRDATA_POLYNOMIAL *polynomialdata)
Definition: expr.c:800
static SCIP_RETCODE exprgraphNodeSimplify(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, SCIP_Bool *havechange)
Definition: expr.c:11460
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2425
static SCIP_RETCODE polynomialdataMultiplyByPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_EXPRDATA_POLYNOMIAL *factordata, int *childmap)
Definition: expr.c:999
static SCIP_RETCODE exprparseFindSeparatingComma(const char *str, const char **endptr, int length)
Definition: expr.c:5065
static SCIP_RETCODE exprgraphNodeRemovePolynomialNullChildren(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:11391
void SCIPexprChgPolynomialConstant(SCIP_EXPR *expr, SCIP_Real constant)
Definition: expr.c:6690
SCIP_RETCODE SCIPexprgraphAddConst(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode)
Definition: expr.c:15337
Definition: type_expr.h:74
SCIP_RETCODE SCIPexprtreeGetMaxDegree(SCIP_EXPRTREE *tree, int *maxdegree)
Definition: expr.c:8711
SCIP_Real * SCIPexprtreeGetParamVals(SCIP_EXPRTREE *tree)
Definition: expr.c:8633
void SCIPexprgraphSetVarNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_INTERVAL varbounds)
Definition: expr.c:15024
SCIP_RETCODE SCIPexprCreateMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL **monomial, SCIP_Real coef, int nfactors, int *childidxs, SCIP_Real *exponents)
Definition: expr.c:7036
void SCIPexprgraphCaptureNode(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12952
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:13467
SCIP_Real SCIPexprGetRealPowerExponent(SCIP_EXPR *expr)
Definition: expr.c:5757
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3009
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:7796
SCIP_RETCODE SCIPexprPolynomialPower(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int exponent)
Definition: expr.c:6786
void SCIPexprChgMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real newcoef)
Definition: expr.c:6852
SCIP_Real SCIPexprGetPolynomialConstant(SCIP_EXPR *expr)
Definition: expr.c:5889
void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode)
Definition: intervalarith.c:211
void SCIPexprgraphPropagateNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool *cutoff)
Definition: expr.c:15898
void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:864
#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT
Definition: type_expr.h:214
SCIP_Bool SCIPexprAreEqual(SCIP_EXPR *expr1, SCIP_EXPR *expr2, SCIP_Real eps)
Definition: expr.c:7581
void SCIPexprMonomialPower(SCIP_EXPRDATA_MONOMIAL *monomial, int exponent)
Definition: expr.c:6927
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetVarNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14970
Definition: type_expr.h:62
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9640
Definition: type_expr.h:73
static void exprgraphNodeCheckSeparabilityComponent(SCIP_EXPRGRAPHNODE *node, int *compnr, int nchildcomps, int *childcomps, int nvars, int *varcomps)
Definition: expr.c:12002
static SCIP_RETCODE exprgraphNodeRemovePolynomialDuplicateChildren(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:11333
SCIP_Real SCIPexprgraphGetNodeSignPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13103
Definition: struct_message.h:36
static SCIP_RETCODE exprCreate(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPROP op, int nchildren, SCIP_EXPR **children, SCIP_EXPROPDATA opdata)
Definition: expr.c:3293
Definition: struct_misc.h:255
SCIP_RETCODE SCIPexprtreeCopy(BMS_BLKMEM *blkmem, SCIP_EXPRTREE **targettree, SCIP_EXPRTREE *sourcetree)
Definition: expr.c:8813
int SCIPexprgraphGetNodeNParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12994
void SCIPexprGetVarsUsage(SCIP_EXPR *expr, int *varsusage)
Definition: expr.c:7558
void SCIPintervalMin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:2492
SCIP_INTERVAL SCIPexprgraphGetNodeBounds(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13328
SCIP_RETCODE SCIPexprgraphEval(SCIP_EXPRGRAPH *exprgraph, SCIP_Real *varvals)
Definition: expr.c:15823
void SCIPexprReindexVars(SCIP_EXPR *expr, int *newindices)
Definition: expr.c:8184
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
Definition: intervalarith.c:380
void SCIPintervalPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1766
int * SCIPexprgraphGetNNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14930
SCIP_RETCODE SCIPexprEvalInt(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val)
Definition: expr.c:7928
Definition: type_expr.h:100
SCIP_EXPORT void SCIPsortPtrReal(void **ptrarray, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPexprSortMonomialFactors(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:7117
static void polynomialdataApplyChildmap(SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int *childmap)
Definition: expr.c:1159
Definition: type_expr.h:40
Definition: type_expr.h:87
SCIP_RETCODE SCIPexprgraphAddExprtreeSum(SCIP_EXPRGRAPH *exprgraph, int nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *coefs, SCIP_EXPRGRAPHNODE **rootnode, SCIP_Bool *rootnodeisnew)
Definition: expr.c:15384
SCIP_RETCODE SCIPexprMultiplyMonomialByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap)
Definition: expr.c:6892
SCIP_RETCODE SCIPexprtreeCreate(BMS_BLKMEM *blkmem, SCIP_EXPRTREE **tree, SCIP_EXPR *root, int nvars, int nparams, SCIP_Real *params)
Definition: expr.c:8772
SCIP_Bool SCIPquadelemSortedFind(SCIP_QUADELEM *quadelems, int idx1, int idx2, int nquadelems, int *pos)
Definition: expr.c:9237
void SCIPexprtreeSetParamVal(SCIP_EXPRTREE *tree, int paramidx, SCIP_Real paramval)
Definition: expr.c:8643
Definition: type_expr.h:55
Definition: type_expr.h:46
void SCIPintervalDiv(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:1029
int SCIPexprgraphGetNodePolynomialNMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13197
Definition: type_expr.h:88
static void exprgraphPrintNodeDot(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames)
Definition: expr.c:10023
static void exprgraphUpdateVarNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Bool *clearreverseprop, SCIP_Bool *boundchanged)
Definition: expr.c:12839
SCIP_RETCODE SCIPexprgraphMoveNodeParents(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **srcnode, SCIP_EXPRGRAPHNODE *targetnode)
Definition: expr.c:14403
SCIP_EXPRCURV SCIPexprcurvMonomial(int nfactors, SCIP_Real *exponents, int *factoridxs, SCIP_EXPRCURV *factorcurv, SCIP_INTERVAL *factorbounds)
Definition: expr.c:361
SCIP_EXPRDATA_MONOMIAL ** SCIPexprGetMonomials(SCIP_EXPR *expr)
Definition: expr.c:5865
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:2113
SCIP_EXPORT void SCIPsortPtrPtrRealInt(void **ptrarray1, void **ptrarray2, SCIP_Real *realarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
public methods for expressions, expression trees, expression graphs, and related stuff ...
SCIP_EXPRCURV SCIPexprcurvMultiply(SCIP_Real factor, SCIP_EXPRCURV curvature)
Definition: expr.c:240
int SCIPexprGetMonomialNFactors(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5911
void SCIPintervalSin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2552
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3098
#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:9011
SCIP_EXPROP SCIPexprgraphGetNodeOperator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13034
static SCIP_RETCODE exprgraphCreateNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_EXPROP op, SCIP_EXPROPDATA opdata)
Definition: expr.c:9723
SCIP_EXPRDATA_MONOMIAL ** SCIPexprgraphGetNodePolynomialMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13185
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:15092
Definition: type_expr.h:47
Definition: type_expr.h:49
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3240
int SCIPexprgraphGetNodeOperatorIndex(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13044
Definition: type_expr.h:76
static SCIP_RETCODE exprparseReadVariable(BMS_BLKMEM *blkmem, const char **str, SCIP_EXPR **expr, int *nvars, int **varnames, int *varnameslength, SCIP_HASHTABLE *vartable, SCIP_Real coefficient, const char *varnameendptr)
Definition: expr.c:4925
Definition: struct_misc.h:127
Definition: type_expr.h:53
SCIP_Real SCIPexprgraphGetNodeLinearConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13125
#define ensureBlockMemoryArraySize3(blkmem, array1, array2, array3, cursize, minsize)
Definition: expr.c:87
#define BMSduplicateBlockMemoryArray(mem, ptr, source, num)
Definition: memory.h:451
SCIP_Real SCIPexprgraphGetNodePolynomialConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13209
SCIP_RETCODE SCIPexprAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:6668
SCIP_Bool SCIPexprgraphHasNodeNonlinearAncestor(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14654
SCIP_EXPRCURV SCIPexprgraphGetNodeCurvature(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13348
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:6585
Definition: type_expr.h:51
SCIP_Bool SCIPexprgraphFindConstNode(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode)
Definition: expr.c:15726
SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand)
Definition: intervalarith.c:429
SCIP_RETCODE SCIPexprEval(SCIP_EXPR *expr, SCIP_Real *varvals, SCIP_Real *param, SCIP_Real *val)
Definition: expr.c:7867
void SCIPexprgraphSetVarsBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_INTERVAL *varbounds)
Definition: expr.c:14992
static SCIP_Bool isUbBetter(SCIP_Real minstrength, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: expr.c:169
Definition: type_retcode.h:36
SCIP_RETCODE SCIPexprgraphCheckCurvature(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Bool clearreverseprop)
Definition: expr.c:15930
SCIP_RETCODE SCIPexprGetMaxDegree(SCIP_EXPR *expr, int *maxdegree)
Definition: expr.c:7233
static void polynomialdataMultiplyByConstant(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_Real factor)
Definition: expr.c:925
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10364
interval arithmetics for provable bounds
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
Definition: intervalarith.c:394
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)), SCIP_DECL_USEREXPRPRINT((*print)))
Definition: expr.c:13537
SCIP_Real * SCIPexprGetQuadLinearCoefs(SCIP_EXPR *expr)
Definition: expr.c:5841
SCIP_EXPRGRAPHNODE *** SCIPexprgraphGetNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14940
int SCIPexprgraphGetSumTreesNSummands(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:16738
static SCIP_RETCODE exprsimplifyRemovePolynomialNullChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4344
void SCIPintervalLog(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2424
SCIP_RETCODE SCIPexprCopyDeep(BMS_BLKMEM *blkmem, SCIP_EXPR **targetexpr, SCIP_EXPR *sourceexpr)
Definition: expr.c:6142
Definition: type_expr.h:52
SCIP_Bool SCIPexprgraphHasNodeUserEstimator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13316
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, int *varnameslength, SCIP_HASHTABLE *vartable, int recursiondepth)
Definition: expr.c:5097
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:490
SCIP_EXPRCURV SCIPexprcurvPower(SCIP_INTERVAL basebounds, SCIP_EXPRCURV basecurv, SCIP_Real exponent)
Definition: expr.c:253
void print(const Container &container, const std::string &prefix="", const std::string &suffix="", std::ostream &os=std::cout, bool negate=false, int prec=6)
Definition: global_functions.h:95
static SCIP_RETCODE exprgraphNodeReplaceChild(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE **oldchild, SCIP_EXPRGRAPHNODE *newchild)
Definition: expr.c:9583
void SCIPmessagePrintWarning(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:417
SCIP_EXPORT SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
internal miscellaneous methods
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem)
Definition: misc.c:9602
static SCIP_Bool exprgraphNodeIsParent(SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE *parent)
Definition: expr.c:9451
static void polynomialdataFree(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata)
Definition: expr.c:712
void SCIPexprMergeMonomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real eps, SCIP_Bool mergefactors)
Definition: expr.c:6806
SCIP_Bool SCIPexprAreMonomialsEqual(SCIP_EXPRDATA_MONOMIAL *monomial1, SCIP_EXPRDATA_MONOMIAL *monomial2, SCIP_Real eps)
Definition: expr.c:6821
SCIP_EXPORT void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
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:13441
SCIP_RETCODE SCIPexprgraphGetSeparableTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs)
Definition: expr.c:16288
SCIP_Bool SCIPexprgraphIsNodeEnabled(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12964
SCIP_INTERVAL * SCIPexprgraphGetVarsBounds(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:15084
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:6633
SCIP_RETCODE SCIPexprCheckCurvature(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varbounds, SCIP_Real *param, SCIP_EXPRCURV *curv, SCIP_INTERVAL *bounds)
Definition: expr.c:8063
SCIP_RETCODE SCIPexprEvalUser(SCIP_EXPR *expr, SCIP_Real *argvals, SCIP_Real *val, SCIP_Real *gradient, SCIP_Real *hessian)
Definition: expr.c:7970
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:584
SCIP_RETCODE SCIPexprEvalShallow(SCIP_EXPR *expr, SCIP_Real *argvals, SCIP_Real *varvals, SCIP_Real *param, SCIP_Real *val)
Definition: expr.c:7848
void SCIPexprMultiplyPolynomialByConstant(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real factor)
Definition: expr.c:6703
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
Definition: intervalarith.c:368
void SCIPexprgraphTightenNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_INTERVAL nodebounds, SCIP_Real minstrength, SCIP_Real infinity, SCIP_Bool *cutoff)
Definition: expr.c:14707
static SCIP_RETCODE exprsimplifyUnconvertPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4891
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:8108
static SCIP_RETCODE exprgraphNodeUpdateBounds(SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool parenttightenisinvalid)
Definition: expr.c:10130
void SCIPexprFreeMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL **monomial)
Definition: expr.c:7093
SCIP_EXPORT void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPexprMulConstant(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPR *term, SCIP_Real factor)
Definition: expr.c:6405
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)), SCIP_DECL_USEREXPRPRINT((*print)))
Definition: expr.c:7154
SCIP_Bool SCIPexprgraphHasNodeSibling(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14619
SCIP_RETCODE SCIPexprgraphGetNodePolynomialMonomialCurvature(SCIP_EXPRGRAPHNODE *node, int monomialidx, SCIP_Real infinity, SCIP_EXPRCURV *curv)
Definition: expr.c:13224
Definition: type_retcode.h:34
SCIP_Real SCIPexprgraphGetNodeOperatorReal(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13055
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:6247
SCIP_Real SCIPexprgraphGetNodeQuadraticConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13137
SCIP_RETCODE SCIPexprMultiplyPolynomialByPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR *factor, int *childmap)
Definition: expr.c:6740
void SCIPexprMergeMonomialFactors(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real eps)
Definition: expr.c:6957
void SCIPintervalCos(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2638
SCIP_EXPRINTCAPABILITY SCIPexprGetUserEvalCapability(SCIP_EXPR *expr)
Definition: expr.c:5963
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:833
SCIP_EXPORT void SCIPsortPtrRealInt(void **ptrarray, SCIP_Real *realarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
Definition: type_expr.h:85
SCIP_Real SCIPexprGetSignPowerExponent(SCIP_EXPR *expr)
Definition: expr.c:5779
static SCIP_RETCODE exprgraphNodeEval(SCIP_EXPRGRAPHNODE *node, SCIP_Real *varvals)
Definition: expr.c:10065
SCIP_Bool SCIPexprgraphAreAllNodeChildrenVars(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14638
void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
Definition: intervalarith.c:3168
Definition: type_expr.h:39
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2891
static SCIP_RETCODE monomialdataEnsureFactorsSize(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomialdata, int minsize)
Definition: expr.c:603
void SCIPexprgraphSetVarNodeLb(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_Real lb)
Definition: expr.c:15044
SCIP_EXPORT SCIP_RETCODE SCIPexprintFreeData(SCIP_EXPRINTDATA **interpreterdata)
Definition: exprinterpret_cppad.cpp:2256
static SCIP_RETCODE exprsimplifyFlattenPolynomials(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPR *expr, SCIP_Real eps, int maxexpansionexponent)
Definition: expr.c:4461
static SCIP_RETCODE exprgraphNodeRemoveParent(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node, SCIP_EXPRGRAPHNODE *parent)
Definition: expr.c:9400
SCIP_EXPRINTDATA * SCIPexprtreeGetInterpreterData(SCIP_EXPRTREE *tree)
Definition: expr.c:8658
SCIP_RETCODE SCIPexprtreeFreeInterpreterData(SCIP_EXPRTREE *tree)
Definition: expr.c:8681
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:3490
void SCIPquadelemSqueeze(SCIP_QUADELEM *quadelems, int nquadelems, int *nquadelemsnew)
Definition: expr.c:9289
void SCIPintervalSquareRoot(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:1382
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:3231
SCIP_EXPORT void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
void SCIPexprgraphGetSubtreeVarsUsage(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int *varsusage)
Definition: expr.c:16722
void SCIPexprgraphSetVarNodeUb(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_Real ub)
Definition: expr.c:15064
static SCIP_Bool exprgraphFindConstNodePos(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int *pos)
Definition: expr.c:9668
void SCIPintervalSquare(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:1310
SCIP_RETCODE SCIPexprgraphNodeSplitOffLinear(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node, int linvarssize, int *nlinvars, void **linvars, SCIP_Real *lincoefs, SCIP_Real *constant)
Definition: expr.c:13591
SCIP_RETCODE SCIPexprCreate(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPROP op,...)
Definition: expr.c:5974
void SCIPintervalScalprodScalars(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
Definition: intervalarith.c:1282
Definition: struct_expr.h:116
SCIP_Bool SCIPexprFindMonomialFactor(SCIP_EXPRDATA_MONOMIAL *monomial, int childidx, int *pos)
Definition: expr.c:7137
Definition: type_expr.h:58
void SCIPexprgraphFreeNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node)
Definition: expr.c:14529
void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:578
static void exprgraphNodePropagateBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool *cutoff)
Definition: expr.c:10224
#define SCIP_EXPRBOUNDSTATUS_CHILDTIGHTENED
Definition: type_expr.h:212
void SCIPexprgraphDisableNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14581
Definition: type_expr.h:64
Definition: struct_expr.h:101
SCIP_RETCODE SCIPexprtreeAddExpr(SCIP_EXPRTREE *tree, SCIP_EXPR *expr, SCIP_Bool copyexpr)
Definition: expr.c:8982
Definition: struct_expr.h:89
void SCIPintervalAbs(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2524
SCIP_Real SCIPexprGetMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5901
static SCIP_RETCODE polynomialdataCopy(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata, SCIP_EXPRDATA_POLYNOMIAL *sourcepolynomialdata)
Definition: expr.c:675
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:1188
void * SCIPexprgraphGetNodeVar(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13066
Definition: type_expr.h:63
SCIP_Real * SCIPexprgraphGetNodeQuadraticLinearCoefs(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13149
static SCIP_RETCODE exprConvertToPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPROP *op, SCIP_EXPROPDATA *data, int nchildren)
Definition: expr.c:3324
SCIP_RETCODE SCIPexprEvalIntUser(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *argvals, SCIP_INTERVAL *val, SCIP_INTERVAL *gradient, SCIP_INTERVAL *hessian)
Definition: expr.c:7993
int SCIPexprgraphGetNodeIntPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13092
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13004
static void exprgraphNodeSortParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:9374
static SCIP_RETCODE exprgraphAddExpr(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPR *expr, void **vars, SCIP_Real *params, SCIP_EXPRGRAPHNODE **exprnode, SCIP_Bool *exprnodeisnew)
Definition: expr.c:12707
static SCIP_RETCODE polynomialdataAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:758
static void quadraticdataSort(SCIP_EXPRDATA_QUADRATIC *quadraticdata)
Definition: expr.c:528
Definition: struct_misc.h:79
SCIP_Bool SCIPexprgraphFindVarNode(SCIP_EXPRGRAPH *exprgraph, void *var, SCIP_EXPRGRAPHNODE **varnode)
Definition: expr.c:15697
Definition: type_expr.h:79
void SCIPexprReindexParams(SCIP_EXPR *expr, int *newindices)
Definition: expr.c:8205
SCIP_Real * SCIPexprgraphGetNodeLinearCoefs(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13114
#define SCIP_EXPRINTCAPABILITY_FUNCVALUE
Definition: type_exprinterpret.h:36
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
Definition: intervalarith.c:417
int SCIPexprgraphGetNodePosition(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13024
static SCIP_Bool isLbBetter(SCIP_Real minstrength, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: expr.c:149
SCIP_RETCODE SCIPexprgraphNodePolynomialAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:13518
void SCIPexprFreeShallow(BMS_BLKMEM *blkmem, SCIP_EXPR **expr)
Definition: expr.c:6222
Definition: type_expr.h:86
SCIP_QUADELEM * SCIPexprGetQuadElements(SCIP_EXPR *expr)
Definition: expr.c:5816
SCIP_RETCODE SCIPexprgraphCreateNodePolynomial(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Real constant, SCIP_Bool copymonomials)
Definition: expr.c:13493
void SCIPintervalExp(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2340
public methods for message output
SCIP_USEREXPRDATA * SCIPexprgraphGetNodeUserData(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13304
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:4790
SCIP_RETCODE SCIPexprgraphCreateNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_EXPROP op,...)
Definition: expr.c:13358
SCIP_RETCODE SCIPexprEvalIntShallow(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *argvals, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val)
Definition: expr.c:7908
SCIP_RETCODE SCIPexprgraphReleaseNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node)
Definition: expr.c:14435
#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE
Definition: type_expr.h:216
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:608
SCIP_RETCODE SCIPexprtreeSimplify(SCIP_EXPRTREE *tree, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, int *nlinvars, int *linidxs, SCIP_Real *lincoefs)
Definition: expr.c:8927
SCIP_RETCODE SCIPexprgraphGetTree(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *rootnode, SCIP_EXPRTREE **exprtree)
Definition: expr.c:16235
Definition: type_expr.h:71
Definition: type_expr.h:54
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:484
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:628
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1003
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:9586
Definition: struct_expr.h:77
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12984
SCIP_RETCODE SCIPexprAddMonomialFactors(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, int nfactors, int *childidxs, SCIP_Real *exponents)
Definition: expr.c:6863
SCIP_Real * SCIPexprGetMonomialExponents(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5931
void SCIPexprgraphPrintNode(SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: expr.c:14691
SCIP_RETCODE SCIPexprtreeSubstituteVars(SCIP_EXPRTREE *tree, SCIP_EXPR **substexprs)
Definition: expr.c:9046
Definition: type_expr.h:75
Definition: type_expr.h:56
SCIP_RETCODE SCIPexprParse(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPR **expr, const char *str, const char *lastchar, int *nvars, int *varnames, int varnameslength)
Definition: expr.c:8539
static SCIP_RETCODE exprgraphNodeEvalWithChildren(SCIP_EXPRGRAPHNODE *node, SCIP_Real *varvals)
Definition: expr.c:10109
Definition: struct_expr.h:155
SCIP_RETCODE SCIPexprgraphSimplify(SCIP_EXPRGRAPH *exprgraph, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, SCIP_Bool *havechange, SCIP_Bool *domainerror)
Definition: expr.c:15973
static SCIP_RETCODE exprsimplifyRemovePolynomialUnusedChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4410
void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:685
static SCIP_RETCODE exprgraphMoveNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int newdepth)
Definition: expr.c:12143
static SCIP_RETCODE exprparseFindClosingParenthesis(const char *str, const char **endptr, int length)
Definition: expr.c:5026
SCIP_RETCODE SCIPexprAddToLinear(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nchildren, SCIP_Real *coefs, SCIP_EXPR **children, SCIP_Real constant)
Definition: expr.c:6540
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:4147
SCIP_EXPORT void SCIPsortPtrPtrReal(void **ptrarray1, void **ptrarray2, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPexprMultiplyPolynomialByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap)
Definition: expr.c:6717
SCIP_Real SCIPexprgraphGetNodeRealPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13081
Definition: struct_expr.h:55
int SCIPexprgraphGetNodeQuadraticNQuadElements(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13173
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10333
Definition: type_retcode.h:43
static SCIP_RETCODE polynomialdataPower(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int exponent)
Definition: expr.c:1089
Definition: type_expr.h:50
#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT
Definition: type_expr.h:215
SCIP_RETCODE SCIPexprCreateLinear(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real *coefs, SCIP_Real constant)
Definition: expr.c:6503
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:605
SCIP_Real SCIPexprGetLinearConstant(SCIP_EXPR *expr)
Definition: expr.c:5803
void SCIPexprtreeSetInterpreterData(SCIP_EXPRTREE *tree, SCIP_EXPRINTDATA *interpreterdata)
Definition: expr.c:8668
SCIP_EXPRCURV SCIPexprcurvAdd(SCIP_EXPRCURV curv1, SCIP_EXPRCURV curv2)
Definition: expr.c:205
static void quadelemsQuickSort(SCIP_QUADELEM *elems, int start, int end)
Definition: expr.c:9102
static SCIP_RETCODE polynomialdataEnsureMonomialsSize(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int minsize)
Definition: expr.c:741
SCIP_RETCODE SCIPexprtreeSetParams(SCIP_EXPRTREE *tree, int nparams, SCIP_Real *paramvals)
Definition: expr.c:8877
SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void)
Definition: intervalarith.c:219
static void exprgraphPrintNodeExpression(SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames, SCIP_Bool printchildrenbounds)
Definition: expr.c:9767
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:12239
static void exprgraphNodeGetVarsUsage(SCIP_EXPRGRAPHNODE *node, int *varsusage)
Definition: expr.c:11977
SCIP_RETCODE SCIPexprgraphPrintDot(SCIP_EXPRGRAPH *exprgraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames)
Definition: expr.c:15774
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3256
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:447
void SCIPintervalSetRoundingModeDownwards(void)
Definition: intervalarith.c:291
void SCIPintervalPowerScalarInverse(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL basedomain, SCIP_Real exponent, SCIP_INTERVAL image)
Definition: intervalarith.c:2014
int SCIPexprgraphGetNodeDepth(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13014
#define ensureBlockMemoryArraySize(blkmem, array1, cursize, minsize)
Definition: expr.c:52
SCIP_RETCODE SCIPexprtreeEval(SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Real *val)
Definition: expr.c:8724
SCIP_EXPRINTCAPABILITY evalcapability
Definition: struct_expr.h:104
void SCIPexprgraphSetVarBounds(SCIP_EXPRGRAPH *exprgraph, void *var, SCIP_INTERVAL varbounds)
Definition: expr.c:15004
static SCIP_RETCODE exprgraphRemoveVar(SCIP_EXPRGRAPH *exprgraph, int varidx)
Definition: expr.c:12090
SCIP_EXPORT void SCIPsortPtrPtrInt(void **ptrarray1, void **ptrarray2, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
Definition: type_expr.h:48
Definition: type_expr.h:41
void SCIPintervalQuad(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL xrng)
Definition: intervalarith.c:2846
void SCIPexprgraphEnableNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14554
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3174
SCIP_QUADELEM * SCIPexprgraphGetNodeQuadraticQuadElements(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13161