expr.c
Go to the documentation of this file.
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
65 #ifdef SCIP_DISABLED_CODE /* this macro is currently not used, which offends lint, so disable it */
113 /* calculate the size with this loop, such that the resulting numbers are always the same (-> block memory) */
148 /** 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) */
168 /** 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) */
253 /** gives curvature for base^exponent for given bounds and curvature of base-function and constant exponent */
282 /* if basebounds contains 0.0, consider negative and positive interval separately, if possible */
288 /* 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 */
295 return (SCIP_EXPRCURV) (SCIPexprcurvPower(leftbounds, basecurv, exponent) & SCIPexprcurvPower(rightbounds, basecurv, exponent));
299 /* (base^exponent)'' = exponent * ( (exponent-1) base^(exponent-2) (base')^2 + base^(exponent-1) base'' )
304 * - for base > 0.0 and 0.0 < exponent < 1.0, we can't say (first sommand negative, second summand positive)
310 * - for base > 0.0 and exponent > 1.0, we can't say (first summand positive, second summand negative)
359 * See Maranas and Floudas, Finding All Solutions of Nonlinearly Constrained Systems of Equations, JOGO 7, 1995
451 * - 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
516 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*quadraticdata)->lincoefs, lincoefs, nchildren) );
521 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*quadraticdata)->quadelems, quadelems, nquadelems) );
618 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &monomialdata->childidxs, monomialdata->factorssize, newsize) );
619 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &monomialdata->exponents, monomialdata->factorssize, newsize) );
635 SCIP_Bool copymonomials /**< whether to copy monomials, or copy only given pointers, in which case polynomialdata assumes ownership of monomial structure */
662 monomials[i]->coef, monomials[i]->nfactors, monomials[i]->childidxs, monomials[i]->exponents) ); /*lint !e613*/
667 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, monomials, nmonomials) );
693 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, (*polynomialdata)->monomialssize) );
698 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &(*polynomialdata)->monomials[i], sourcepolynomialdata->monomials[i]->coef,
699 sourcepolynomialdata->monomials[i]->nfactors, sourcepolynomialdata->monomials[i]->childidxs, sourcepolynomialdata->monomials[i]->exponents) );
733 BMSfreeBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, (*polynomialdata)->monomialssize);
751 ensureBlockMemoryArraySize(blkmem, &polynomialdata->monomials, &polynomialdata->monomialssize, minsize);
776 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials + nmonomials) );
784 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials + i],
785 monomials[i]->coef, monomials[i]->nfactors, monomials[i]->childidxs, monomials[i]->exponents) ); /*lint !e613*/
790 BMScopyMemoryArray(&polynomialdata->monomials[polynomialdata->nmonomials], monomials, nmonomials); /*lint !e866*/
824 SCIPsortPtr((void**)polynomialdata->monomials, monomialdataCompare, polynomialdata->nmonomials);
850 /* merge monomials by adding their coefficients, eliminate monomials with no factors or zero coefficient*/
887 if( monomialdataCompare((void*)polynomialdata->monomials[i], (void*)polynomialdata->monomials[i+offset+1]) != 0 )
948 SCIPexprChgMonomialCoef(polynomialdata->monomials[i], polynomialdata->monomials[i]->coef * factor);
978 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i], factor, childmap) );
984 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials+1) );
985 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials], polynomialdata->constant, 0, NULL, NULL) );
986 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[polynomialdata->nmonomials], factor, childmap) );
1025 SCIP_CALL( polynomialdataMultiplyByMonomial(blkmem, polynomialdata, factordata->monomials[0], childmap) );
1032 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials+1) );
1033 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials], polynomialdata->constant, 0, NULL, NULL) );
1039 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials * (factordata->nmonomials + (factordata->constant == 0.0 ? 0 : 1))) );
1047 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 */
1048 SCIP_CALL( polynomialdataAddMonomials(blkmem, polynomialdata, orignmonomials, polynomialdata->monomials, TRUE) );
1054 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i1], factordata->monomials[i2], childmap) );
1069 SCIPexprChgMonomialCoef(polynomialdata->monomials[i1], polynomialdata->monomials[i1]->coef * factordata->constant);
1077 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i1], factordata->monomials[i2], childmap) );
1197 int maxexpansionexponent,/**< maximal exponent for which polynomials (with > 1 summands) are expanded */
1224 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && factorpolynomial->constant < 0.0 ) /*lint !e835*/
1226 /* if polynomial is a negative constant and our exponent is not integer, then cannot do expansion */
1227 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n", factorpolynomial->constant, monomial->exponents[factorpos]);
1260 /* if coefficient of monomial is negative and our exponent is not integer, then do not do expansion
1261 * @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
1268 /* @todo if there is an even number of factors in factormonomial that are negative, then they always multiply to something positive
1271 * MINLPLib instances tls2,4,6 are examples where we are loosing here (do not recognize convexity)
1278 SCIP_CALL( monomialdataEnsureFactorsSize(blkmem, monomial, monomial->nfactors + factormonomial->nfactors) );
1283 /* can do this because monomial->exponents[factorpos] is assumed to be integer or factormonomial has positive coefficient and only one factor
1284 * thus, if factormonomial->exponents[i] is fractional, then we can assume that it's argument is positive
1305 /* if exponent is negative or fractional and the polynomial is not just a monomial, then we cannot do expansion */
1306 if( !EPSISINT(monomial->exponents[factorpos], 0.0) || monomial->exponents[factorpos] < 0.0 ) /*lint !e835*/
1320 * that is, assume monomial is f1^a1 f2^a2 ... and we want to expand f1 = (g11^beta11 g12^beta12... + g21^beta21 g22^beta22 ... + ...)
1321 * then we do this only if all ai and all beta are > 0.0 and a1 max(beta11+beta12+..., beta21+beta22+..., ...) + a2 + ... < maxexpansionexponent
1324 if( maxexpansionexponent < INT_MAX && (monomial->nfactors > 1 || monomial->exponents[factorpos] != 1.0) )
1351 SCIPdebugMessage("skip expansion because %d'th factor in %d'th monomial of factorpolynomial is negative\n", i, j);
1360 SCIPdebugMessage("skip expansion because degree of %d'th monomial would yield degree %g > max = %d in expansion\n",
1373 SCIP_CALL( polynomialdataPower(blkmem, factorpolynomialcopy, (int)EPSFLOOR(monomial->exponents[factorpos], 0.0)) ); /*lint !e835*/
1390 polynomialdata->monomials[monomialpos] = polynomialdata->monomials[polynomialdata->nmonomials-1];
1395 SCIP_CALL( polynomialdataAddMonomials(blkmem, polynomialdata, factorpolynomialcopy->nmonomials, factorpolynomialcopy->monomials, FALSE) );
1409 /** a default implementation of expression interval evaluation that always gives a correct result */
1418 /** a default implementation of expression curvature check that always gives a correct result */
1653 #if defined(__GNUC__) && __GNUC__ * 100 + __GNUC_MINOR__ * 10 >= 490 && !defined(__INTEL_COMPILER)
1696 * if both nominator and denominator are not constant, then quotient may not be convex nor concave
1841 #if defined(__GNUC__) && __GNUC__ * 100 + __GNUC_MINOR__ * 10 >= 490 && !defined(__INTEL_COMPILER)
2127 /* erf and erfi do not seem to exist on every system, and we cannot really handle them anyway, so they are currently disabled */
2434 * if only one factor is not constant, then product is curvature of this factor, multiplied by sign of product of remaining factors
2532 /* for a linear expression, we need to copy the array that holds the coefficients and constant term */
2534 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &targetdata, (SCIP_Real*)opdatasource.data, nchildren + 1) ); /*lint !e866*/
2587 *result += quadelems->coef * argvals[quadelems->idx1] * argvals[quadelems->idx2]; /*lint !e613*/
2659 SCIPdebugMessage("%g x^2 + %g y^2 + %g x y + %g x + %g y = [%g,%g] for x = [%g,%g], y = [%g,%g]\n",
2661 result->inf, result->sup, argvals[0].inf, argvals[0].sup, argvals[1].inf, argvals[1].sup); /*lint !e613*/
2673 /* for each argument, we collect it's linear index from lincoefs, it's square coefficients and all factors from bilinear terms
2682 /* there are no quadratic terms with argidx in its first argument, that should be easy to handle */
2703 SCIPintervalMulScalar(infinity, &tmp, argvals[quadelems[i].idx2], quadelems[i].coef); /*lint !e613*/
2765 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef * argbounds[quadelems[i].idx1].inf, argcurv[quadelems[i].idx2]));
2770 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef * argbounds[quadelems[i].idx2].inf, argcurv[quadelems[i].idx1]));
2775 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef, SCIPexprcurvPower(argbounds[quadelems[i].idx1], argcurv[quadelems[i].idx1], 2.0)));
2800 sourcedata->constant, nchildren, sourcedata->lincoefs, sourcedata->nquadelems, sourcedata->quadelems) );
3047 /* we assume that some simplifier was running, so that monomials do not have constants in their factors and such that all factors are different
3051 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(monomial->coef, SCIPexprcurvMonomial(monomial->nfactors, monomial->exponents, monomial->childidxs, argcurv, argbounds)));
3114 SCIP_CALL( exprdata->inteval(infinity, exprdata->userdata, nargs, argvals, result, NULL, NULL) );
3118 /* if user does not provide interval evaluation, then return a result that is always correct */
3139 /* if user does not provide curvature check, then return unknown (which is handled like indefinite) */
3165 SCIP_CALL( exprdatasource->copydata(blkmem, nchildren, exprdatasource->userdata, &exprdatatarget->userdata) );
3210 SCIP_DECL_EXPRCOPYDATA ((*copydata)); /**< expression data copy function, or NULL to only opdata union */
3211 SCIP_DECL_EXPRFREEDATA ((*freedata)); /**< expression data free function, or NULL if nothing to free */
3216 /** table containing for each operand the name, the number of children, and some evaluation functions */
3247 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY,
3248 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY,
3249 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY,
3253 { "linear", -2, exprevalLinear, exprevalIntLinear, exprcurvLinear, exprCopyDataLinear, exprFreeDataLinear },
3254 { "quadratic", -2, exprevalQuadratic, exprevalIntQuadratic, exprcurvQuadratic, exprCopyDataQuadratic, exprFreeDataQuadratic },
3255 { "polynomial", -2, exprevalPolynomial, exprevalIntPolynomial, exprcurvPolynomial, exprCopyDataPolynomial, exprFreeDataPolynomial },
3256 { "user", -2, exprevalUser, exprevalIntUser, exprcurvUser, exprCopyDataUser, exprFreeDataUser }
3318 /** tries to convert a given (operator,operatordata) pair into a polynomial operator with corresponding data
3655 SCIP_CALL( polynomialdataCreate(blkmem, &polynomialdata, 0, NULL, lineardata[nchildren], FALSE) );
3697 SCIP_CALL( polynomialdataCreate(blkmem, &polynomialdata, 0, NULL, quaddata->constant, FALSE) );
3699 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, (quaddata->lincoefs != NULL ? nchildren : 0) + quaddata->nquadelems) );
3835 /* polynomial simplification and monomial merging should ensure that monomial i corresponds to child i and that there are not unused children */
3839 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == 1.0 && polynomialdata->monomials[1]->coef == 1.0 )
3856 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == 1.0 && polynomialdata->monomials[1]->coef == -1.0 )
3873 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == -1.0 && polynomialdata->monomials[1]->coef == 1.0 )
3923 * that monomials are ordered according to the child index, and that constant monomials have been removed
3945 if( maxdegree == 2 && (polynomialdata->nmonomials > 1 || polynomialdata->constant != 0.0 || polynomialdata->monomials[0]->coef != 1.0) )
3947 /* 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 */
3952 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &quaddata->quadelems, polynomialdata->nmonomials - nlinmonomials) );
3968 assert(polynomialdata->monomials[i]->nfactors == 1 || polynomialdata->monomials[i]->nfactors == 2);
3976 quaddata->lincoefs[polynomialdata->monomials[i]->childidxs[0]] += polynomialdata->monomials[i]->coef;
3995 quaddata->quadelems[quadelemidx].idx1 = MIN(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]);
3996 quaddata->quadelems[quadelemidx].idx2 = MAX(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]);
4011 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 1 && polynomialdata->monomials[0]->coef == 1.0 )
4103 if( monomial->nfactors == 2 && monomial->exponents[0] == 1.0 && monomial->exponents[1] == -1.0 )
4117 if( monomial->nfactors == 2 && monomial->exponents[0] == -1.0 && monomial->exponents[1] == 1.0 )
4142 /** adds copies of expressions to the array of children of a sum, product, linear, quadratic, or polynomial expression
4144 * For a sum or product expression, this corresponds to add additional summands and factors, resp.
4146 * For a quadratic or polynomial expression, only the children array may be enlarged, the expression itself remains the same.
4154 SCIP_Bool comparechildren, /**< whether to compare expressions with already existing children (no effect for sum and product) */
4156 int* childmap /**< array where to store mapping of indices from exprs to children array in expr, or NULL if not of interest */
4163 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);
4174 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) );
4177 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren + i], exprs[i]) ); /*lint !e613*/
4195 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) );
4203 if( expr->children[j] != NULL && SCIPexprAreEqual(expr->children[j], exprs[i], eps) ) /*lint !e613*/
4212 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren], exprs[i]) ); /*lint !e613*/
4231 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, orignchildren + nexprs, expr->nchildren) );
4239 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, orignchildren + 1, expr->nchildren + 1) );
4251 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data->lincoefs, orignchildren, expr->nchildren) );
4252 BMSclearMemoryArray(&data->lincoefs[orignchildren], expr->nchildren - orignchildren); /*lint !e866*/
4398 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, lastnonnull+1) );
4460 * exprsimplifyConvertToPolynomials should have been called before to eliminate simple polynomial operands.
4468 int maxexpansionexponent/**< maximal exponent for which we still expand non-monomial polynomials */
4477 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr->children[i], eps, maxexpansionexponent) );
4507 if( (expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) ||
4513 /* since child0 has no children and it's polynomial was flattened, it should have no monomials */
4514 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0);
4538 if( ((expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) || expr->children[0]->op == SCIP_EXPR_CONST) &&
4539 ((expr->children[1]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[1]) == 0) || expr->children[1]->op == SCIP_EXPR_CONST) )
4544 /* since children have no children and it's polynomial was flattened, it should have no monomials */
4545 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0);
4546 assert(expr->children[1]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[1]) == 0);
4599 * 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
4627 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
4642 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && SCIPexprGetOpReal(expr->children[i]) < 0.0 ) /*lint !e835*/
4645 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n",
4700 SCIP_CALL( exprsimplifyAddChildren(blkmem, expr, expr->children[i]->nchildren, expr->children[i]->children, TRUE, eps, childmap) );
4710 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
4725 SCIP_CALL( polynomialdataExpandMonomialFactor(blkmem, messagehdlr, polynomialdata, j, factorpos,
4726 (SCIP_EXPRDATA_POLYNOMIAL*)expr->children[i]->data.data, childmap, maxexpansionexponent, &success) );
4737 /* expansion may remove monomials[j], move a monomial from the end to position j, or add new monomials to the end of polynomialdata
4798 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part */
4862 if( childusage[childidx] == 1 && varsusage[SCIPexprGetOpIndex(expr->children[childidx])] == 1 )
4864 /* if the child expression is not used in another monomial (which would due to merging be not linear)
4911 SCIP_CALL( exprUnconvertPolynomial(blkmem, &expr->op, &expr->data, expr->nchildren, (void**)expr->children) );
4924 * Creates a new variable index if variable not seen before, updates varnames and vartable structures.
4934 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */
4936 const char* varnameendptr /**< if a <varname> should be parsed, set this to NULL. Then, str points to the '<'
4964 SCIPerrorMessage("Variable name %.*s is too long for buffer in exprparseReadVariable.\n", namelength, *str);
4987 SCIPerrorMessage("Buffer in exprparseReadVariable is too short for varaible name %.*s.\n", namelength, *str);
5023 /** if str[0] points to an opening parenthesis, this function sets endptr to point to the matching closing bracket in str
5053 SCIPerrorMessage("unable to find closing parenthesis in unbalanced expression %.*s\n", length, str);
5090 SCIPerrorMessage("unable to find separating comma in unbalanced expression %.*s\n", length, str);
5109 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */
5136 SCIPdebugMessage("exprParse (%i): parsing %.*s\n", recursiondepth, (int) (lastchar-str + 1), str);
5148 * a '+' or '-' that follows an 'e' or 'E' indicates that we are in the middle of a number, so it doesn't separate terms
5150 while( subexpptr != lastchar && !(nopenbrackets == 0 && (subexpptr[0] == '+' || subexpptr[0] == '-') && subexpptr != str && subexpptr[-1] != 'e' && subexpptr[-1] != 'E') )
5161 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str, (int) ((subexpptr - 1) - str + 1), subexpptr - 1, nvars,
5166 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, subexpptr , (int) (lastchar - (subexpptr ) + 1), lastchar, nvars,
5170 * we always use add, because we leave the operator between the found expressions in the second argument
5171 * this way, we do not have to worry about ''minus brackets'' in the case of more then two summands:
5203 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, subexpptr, subexplength, subexpendptr, nvars, varnames,
5232 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, str, (int)(lastchar - str) + 1, lastchar, nvars, varnames,
5250 SCIP_CALL( exprparseReadVariable(blkmem, &str, expr, nvars, varnames, varnameslength, vartable, 1.0, NULL) );
5257 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5277 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5330 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5338 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, comma, endptr - comma, endptr - 1, nvars, varnames,
5359 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5366 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) )
5394 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5401 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) )
5425 /* check for a variable, that was not recognized earlier because somebody omitted the '<' and '>' we need for
5431 /* allow only variable names containing characters, digits, hash marks, and underscores here */
5435 SCIP_CALL( exprparseReadVariable(blkmem, &varnamestartptr, expr, nvars, varnames, varnameslength,
5457 SCIPerrorMessage("error finding first expression in \"%.*s\" took us outside of given subexpression length\n", length, strstart);
5485 if( isdigit((unsigned char)str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit((unsigned char)str[1])) )
5515 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5563 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames,
5621 /* if there is a part of the string left to be parsed, we assume that this as a multiplication */
5631 SCIPdebugMessage("No operator found, assuming a multiplication before %.*s\n", (int) (lastchar - str + 1), str);
5634 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames,
5801 /* the coefficients are stored in the first nchildren elements of the array stored as expression data */
6132 SCIPerrorMessage("cannot create complex expression linear, quadratic, polynomial, or user with SCIPexprCreate\n");
6162 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*targetexpr)->children, sourceexpr->nchildren) );
6172 assert((*targetexpr)->children == NULL); /* otherwise, sourceexpr->children was not NULL, which is wrong */
6180 SCIP_CALL( exprOpTable[sourceexpr->op].copydata(blkmem, sourceexpr->nchildren, sourceexpr->data, &(*targetexpr)->data) );
6245 /** creates an expression from the addition of two given expression, with coefficients, and a constant
6247 * The given expressions may be modified or freed, otherwise it will be used a child expression.
6348 if( SCIPexprGetOperator(term1) == SCIP_EXPR_LINEAR && SCIPexprGetOperator(term2) == SCIP_EXPR_LINEAR )
6354 SCIP_CALL( SCIPexprAddToLinear(blkmem, term1, SCIPexprGetNChildren(term2), SCIPexprGetLinearCoefs(term2), SCIPexprGetChildren(term2), SCIPexprGetLinearConstant(term2) + constant) );
6405 * The given expressions may be modified or freed, otherwise it will be used a child expression.
6505 /** creates a SCIP_EXPR_LINEAR expression that is (affine) linear in its children: constant + sum_i coef_i child_i */
6530 /* we store the coefficients and the constant in a single array and make this our operand data */
6573 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nchildren) );
6577 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, expr->nchildren + 1, expr->nchildren + nchildren + 1) );
6587 /** creates a SCIP_EXPR_QUADRATIC expression: constant + sum_i coef_i child_i + sum_i coef_i child1_i child2_i */
6614 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) );
6635 /** creates a SCIP_EXPR_POLYNOMIAL expression from an array of monomials: constant + sum_i monomial_i */
6662 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) );
6687 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, nmonomials, monomials, copymonomials) );
6733 SCIP_CALL( polynomialdataMultiplyByMonomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, factor, childmap) );
6741 * Children of factor need to be children of expr already, w.r.t. an optional mapping of child indices.
6779 SCIP_CALL( polynomialdataMultiplyByPolynomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, (SCIP_EXPRDATA_POLYNOMIAL*)factor->data.data, childmap) );
6800 SCIP_CALL( polynomialdataPower(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, exponent) );
6805 /** merges monomials in a polynomial expression that differ only in coefficient into a single monomial
6820 polynomialdataMergeMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, eps, mergefactors);
6885 BMScopyMemoryArray(&monomial->childidxs[monomial->nfactors], childidxs, nfactors); /*lint !e866*/
6886 BMScopyMemoryArray(&monomial->exponents[monomial->nfactors], exponents, nfactors); /*lint !e866*/
6912 SCIP_CALL( SCIPexprAddMonomialFactors(blkmem, monomial, factor->nfactors, factor->childidxs, factor->exponents) );
6990 while( i+offset+1 < monomial->nfactors && monomial->childidxs[i] == monomial->childidxs[i+offset+1] )
7062 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->childidxs, childidxs, nfactors) );
7075 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->exponents, exponents, nfactors) );
7137 * Note that if the factors have not been merged, the position of some factor corresponding to a given child is given.
7163 SCIP_EXPRINTCAPABILITY evalcapability, /**< capability of evaluation functions (partially redundant, currently) */
7165 SCIP_DECL_USEREXPRINTEVAL ((*inteval)), /**< interval evaluation function, or NULL if not implemented */
7167 SCIP_DECL_USEREXPRPROP ((*prop)), /**< interval propagation function, or NULL if not implemented */
7168 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */
7169 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */
7170 SCIP_DECL_USEREXPRFREEDATA ((*freedata)), /**< expression data free function, or NULL if nothing to free */
7171 SCIP_DECL_USEREXPRPRINT ((*print)) /**< expression print function, or NULL for default string "user" */
7181 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */
7182 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */
7342 else if( expr->data.dbl > 0.0 && (int)expr->data.dbl == expr->data.dbl ) /* natural exponent gives polynomial again */ /*lint !e777*/
7471 /* if no linear or no quadratic coefficient with current child on first position, then nothing to do */
7483 while( quadidx < quadraticdata->nquadelems && quadraticdata->quadelems[quadidx].idx1 == childidx )
7494 SCIP_CALL( SCIPexprGetMaxDegree(expr->children[quadraticdata->quadelems[quadidx].idx2], &child2) );
7534 /* if the exponent of the factor is not a natural number and the child is not constant (degree 0),
7536 if( child1 != 0 && (monomialdata->exponents[j] < 0.0 || (int)monomialdata->exponents[j] != monomialdata->exponents[j]) )
7615 return SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps) && SCIPexprAreEqual(expr1->children[1], expr2->children[1], eps);
7633 return EPSEQ(expr1->data.dbl, expr2->data.dbl, eps) && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps);
7636 return expr1->data.intval == expr2->data.intval && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps);
7797 * If linear variables are split off, expression interpreter data, if stored in the tree, is freed.
7804 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
7806 int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */
7807 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */
7825 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr, eps, maxexpansionexponent) );
7834 SCIP_CALL( exprsimplifySeparateLinearFromPolynomial(blkmem, expr, eps, nvars, nlinvars, linidxs, lincoefs) );
7854 SCIP_Real* varvals, /**< values for variables, can be NULL if the expression operand is not a variable */
7855 SCIP_Real* param, /**< values for parameters, can be NULL if the expression operand is not a parameter */
7864 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, argvals, varvals, param, val) );
7873 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7899 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, buf, varvals, param, val) );
7914 SCIP_INTERVAL* argvals, /**< interval values for children, can be NULL if the expression has no children */
7915 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */
7916 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7925 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, argvals, varvals, param, val) );
7934 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */
7935 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7956 SCIP_CALL( SCIPexprEvalInt(expr->children[i], infinity, varvals, param, &buf[i]) ); /*lint !e644*/
7961 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, buf, varvals, param, val) );
7990 SCIP_CALL( exprdata->eval(exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) );
8002 SCIP_INTERVAL* hessian /**< buffer to store values of full Hessian, or NULL if not requested */
8022 SCIP_CALL( exprdata->inteval(infinity, exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) );
8035 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
8050 SCIP_CALL( SCIPexprCheckCurvature(expr->children[i], infinity, varbounds, param, &childcurv[i], &childbounds[i]) ); /*lint !e644*/
8059 SCIP_CALL( exprOpTable[expr->op].curv(infinity, expr->data, expr->nchildren, childbounds, childcurv, curv) );
8060 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, childbounds, varbounds, param, bounds) );
8070 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
8097 retcode = doCheckCurvature(expr, infinity, varbounds, childbounds, param, curv, childcurv, bounds);
8110 /** under-/overestimates a user expression w.r.t. to given values and bounds for children expressions */
8117 SCIP_Real* coeffs, /**< buffer to store the linear coefficients for each child expression that gives a valid under-/overestimator */
8118 SCIP_Real* constant, /**< buffer to store the constant value of the linear under-/overestimator */
8133 SCIP_CALL( exprdata->estimate(infinity, exprdata->userdata, expr->nchildren, argvals, argbounds, overestimate, coeffs, constant, success ) );
8242 /* @Note: 'expr->data.intval' is either between 0 and number of variables-1, if it uses the varnames array, or
8442 SCIPexprPrint(expr->children[quadraticdata->quadelems[i].idx1], messagehdlr, file, varnames, paramnames, paramvals);
8450 SCIPexprPrint(expr->children[quadraticdata->quadelems[i].idx2], messagehdlr, file, varnames, paramnames, paramvals);
8484 SCIPexprPrint(expr->children[monomialdata->childidxs[j]], messagehdlr, file, varnames, paramnames, paramvals);
8564 * for each variable, we store its name, prefixed with the assigned index in the first sizeof(int) bytes
8566 SCIP_CALL( SCIPhashtableCreate(&vartable, blkmem, 10, exprparseVarTableGetKey, SCIPhashKeyEqString,
8569 retcode = exprParse(blkmem, messagehdlr, expr, str, (int) (lastchar - str + 1), lastchar, nvars, &varnames,
8695 /** indicates whether there are parameterized constants (SCIP_EXPR_PARAM) in expression tree */
8779 SCIP_Real* params /**< values for parameters, or NULL (if NULL but nparams > 0, then params is initialized with zeros) */
8836 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*targettree)->vars, sourcetree->vars, sourcetree->nvars) );
8844 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*targettree)->params, sourcetree->params, sourcetree->nparams) );
8926 * If linear variables are split off, expression interpreter data, if stored in the tree, is freed.
8932 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
8933 int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */
8934 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */
8959 /* we should be careful about declaring numbers close to zero as zero, so take eps^2 as tolerance */
8960 SCIP_CALL( SCIPexprSimplify(tree->blkmem, messagehdlr, tree->root, eps*eps, maxexpansionexponent, tree->nvars, nlinvars, linidxs, lincoefs) );
8967 assert(testval_before != testval_before || testval_before == testval_after || EPSZ(SCIPrelDiff(testval_before, testval_after), eps)); /*lint !e777*/
8980 * 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.
9011 /** tries to determine the curvature type of an expression tree w.r.t. given variable domains */
9034 SCIP_CALL( SCIPexprCheckCurvature(tree->root, infinity, varbounds, tree->params, curv, &exprbounds) );
9089 * 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
9091 #define QUADELEMS_ISBETTER(a, b) ( ((a).idx1 < (b).idx1) || ((a).idx1 == (b).idx1 && (a).idx2 < (b).idx2) )
9101 /** quicksort an array of quadratic elements; pivot is the medial element (taken from scip/sorttpl.c) */
9150 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
9151 assert(!QUADELEMS_ISBETTER(elems[mid], pivotkey)); /* the pivot element did not change its position */
9234 * If (idx1,idx2) is found in quadelems, then returns TRUE and stores position of quadratic element in *pos.
9235 * 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.
9243 int* pos /**< buffer to store position of found quadratic element or position where it would be inserted, or NULL */
9268 if( idx1 < quadelems[middle].idx1 || (idx1 == quadelems[middle].idx1 && idx2 < quadelems[middle].idx2) ) /*lint !e613*/
9270 else if( quadelems[middle].idx1 < idx1 || (quadelems[middle].idx1 == idx1 && quadelems[middle].idx2 < idx2) ) /*lint !e613*/
9335 /* now i should point to the position after the last valid element, i.e., it is the remaining number of elements */
9368 node->parentssorted = (node->nparents <= 1) || (node->parentssorted && (exprgraphnodecomp((void*)node->parents[node->nparents-2], (void*)parent) <= 0));
9403 SCIP_EXPRGRAPHNODE** node, /**< expression graph node where to remove a parent, *node will be set to NULL */
9424 (void) SCIPsortedvecFindPtr((void**)(*node)->parents, exprgraphnodecomp, (void*)parent, (*node)->nparents, &pos);
9439 * this is faster than moving the last parent to position pos if there are many repeated calls to this function as the parents array remains sorted
9479 return SCIPsortedvecFindPtr((void**)node->parents, exprgraphnodecomp, (void*)parent, node->nparents, &pos);
9482 /** adds expression graph nodes to the array of children of a sum, product, linear, quadratic, or polynomial expression
9484 * For a sum or product expression, this corresponds to add additional summands and factors, resp.
9486 * For a quadratic or polynomial expression, only the children array may be enlarged, the expression itself remains the same.
9497 int* childmap /**< array where to store mapping of indices from exprs to children array in node, or NULL if not of interest */
9509 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);
9516 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, node->nchildren, node->nchildren + nexprs) );
9557 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, orignchildren + nexprs, node->nchildren) );
9565 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, orignchildren + 1, node->nchildren + 1) );
9577 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data->lincoefs, orignchildren, node->nchildren) );
9578 BMSclearMemoryArray(&data->lincoefs[orignchildren], node->nchildren - orignchildren); /*lint !e866*/
9611 SCIPdebugMessage("replace child %p in node %p by %p\n", (void*)*oldchild, (void*)node, (void*)newchild);
9613 /* let's see if child is just next to the place where we looked in a previous call to this function */
9614 if( exprgraph->lastreplacechildpos >= 0 && exprgraph->lastreplacechildpos+1 < node->nchildren && node->children[exprgraph->lastreplacechildpos+1] == *oldchild )
9656 assert(((SCIP_EXPRGRAPHNODE*)elem1)->data.dbl == ((SCIP_EXPRGRAPHNODE*)elem1)->data.dbl); /* assert that const value is not nan */ /*lint !e777*/
9657 assert(((SCIP_EXPRGRAPHNODE*)elem2)->data.dbl == ((SCIP_EXPRGRAPHNODE*)elem2)->data.dbl); /* assert that const value is not nan */ /*lint !e777*/
9729 while( exprgraph->constnodes[*pos] != node && *pos > 0 && exprgraph->constnodes[*pos-1]->data.dbl == node->data.dbl ) /*lint !e777*/
9732 while( exprgraph->constnodes[*pos] != node && *pos < exprgraph->nconsts-1 && exprgraph->constnodes[*pos+1]->data.dbl == node->data.dbl ) /*lint !e777*/
9770 /* set initial curvature to linear for variables, parameters, and constants and unknown otherwise */
9817 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9820 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9825 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9828 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9833 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9836 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9841 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9844 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9849 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9855 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9870 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9889 SCIPmessageFPrintInfo(messagehdlr, file, "(c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9891 SCIPmessageFPrintInfo(messagehdlr, file, ",c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9902 SCIPmessageFPrintInfo(messagehdlr, file, "c%d[%10g,%10g]", i, node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9914 SCIPmessageFPrintInfo(messagehdlr, file, "c%d[%10g,%10g]", i, node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9939 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9962 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9975 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[quadraticdata->quadelems[i].idx1]->bounds.inf, node->children[quadraticdata->quadelems[i].idx1]->bounds.sup);
9982 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[quadraticdata->quadelems[i].idx2]->bounds.inf, node->children[quadraticdata->quadelems[i].idx2]->bounds.sup);
10017 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[monomialdata->childidxs[j]]->bounds.inf, node->children[monomialdata->childidxs[j]]->bounds.sup);
10056 SCIPmessageFPrintInfo(messagehdlr, file, "n%d_%d [fillcolor=\"%g,%g,%g\", label=\"", node->depth, node->pos, color, color, color);
10077 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);
10112 SCIP_CALL( exprOpTable[node->op].eval(node->data, node->nchildren, buf, varvals, NULL, &node->value) );
10150 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a bound recalculation in parent nodes */
10151 SCIP_Bool parenttightenisinvalid /**< whether to consider bounds that have been tightened by parents as invalid */
10160 assert(node->depth >= 1); /* node should be in graph and not be at depth 0 (i.e., no variable, constant, or parameter) */
10193 SCIP_CALL( exprOpTable[node->op].inteval(infinity, node->data, node->nchildren, childbounds, NULL, NULL, &newbounds) );
10201 /* NOTE: if you change code below, please make analog changes also in SCIPexprgraphUpdateNodeBoundsCurvature */
10203 /* if bounds of a children were relaxed or our bounds were tightened by a (now possibly invalid) reverse propagation from a parent
10204 * and now our bounds are relaxed, then we have to propagate this upwards to ensure valid bounds
10206 * if bounds were tightened (considerably), then tell this to those parents which think that they have valid bounds
10208 * finally, if there was only a little tightening, then keep this updated bounds, but don't notify parents
10211 ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED) || ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) && parenttightenisinvalid)) )
10231 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);
10245 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */
10246 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
10258 assert(!SCIPintervalIsEmpty(infinity, node->bounds)); /* should not call backward prop. for a node that yield a cutoff already */
10259 assert(!node->enabled || !(node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED)); /* there should be no unprocessed relaxations of children bounds, if node is enabled */
10261 /* if we have no recent bound tightening from a parent, then no use in reverse-propagating our bounds */
10270 if( (node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE) == SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE )
10276 /* 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);
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);
10348 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10354 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10373 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10384 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10393 SCIPintervalPowerScalarInverse(infinity, &childbounds, node->children[0]->bounds, node->data.dbl, node->bounds);
10400 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10421 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10430 SCIPintervalPowerScalarInverse(infinity, &childbounds, node->children[0]->bounds, (SCIP_Real)node->data.intval, node->bounds);
10437 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10454 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10465 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10504 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10517 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10532 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10539 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10555 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10560 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10626 /* if there are too many unbounded bounds, then could only compute infinite bounds for children, so give up */
10638 * node->bounds.sup - (minlinactivity - c_i.inf), if c_i.inf > -infinity and minlinactivityinf == 0
10652 childbounds.sup = SCIPintervalNegateReal(minlinactivity - node->bounds.sup - node->children[i]->bounds.inf);
10657 * node->bounds.inf - (maxlinactivity - c_i.sup), if c_i.sup < infinity and maxlinactivityinf == 0
10673 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
10704 /* if there is 0.0 in the product, then later division will hardly give useful bounds, so giveup for this i */
10711 SCIPintervalDiv(infinity, &childbounds, node->bounds, childbounds); /* f / prod_{j:j!=i} c_j */
10712 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
10813 /* SCIPdebugMessage("activity = [%10g,%10g] ninf = [%d,%d]; bounds = [%10g,%10g]\n", minlinactivity, maxlinactivity, minlinactivityinf, maxlinactivityinf, node->bounds.inf, node->bounds.sup); */
10815 /* if there are too many unbounded bounds, then could only compute infinite bounds for children, so give up */
10838 ac.sup = SCIPintervalNegateReal(SCIPintervalNegateReal(coefs[i]) * node->children[i]->bounds.sup);
10852 * (node->bounds.sup - minlinactivity)/coefs[i] + c_i.inf, if c_i.inf > -infinity and minlinactivityinf == 0
10853 * (node->bounds.sup - minlinactivity)/coefs[i], if c_i.inf == -infinity and minlinactivityinf == 1
10865 childbounds.sup = SCIPintervalNegateReal((minlinactivity - ac.inf - node->bounds.sup)/coefs[i]);
10870 * (node->bounds.inf - maxlinactivity)/coefs[i] + c_i.sup, if c_i.sup < infinity and maxlinactivityinf == 0
10871 * (node->bounds.inf - maxlinactivity)/coefs[i], if c_i.sup == infinity and maxlinactivityinf == 1
10892 * (node->bounds.sup - minlinactivity)/coefs[i] + c_i.sup, if c_i.sup < infinity and minlinactivityinf == 0
10893 * (node->bounds.sup - minlinactivity)/coefs[i], if c_i.sup == infinity and minlinactivityinf == 1
10904 childbounds.inf = (minlinactivity - ac.inf - node->bounds.sup)/SCIPintervalNegateReal(coefs[i]);
10909 * (node->bounds.inf - maxlinactivity)/coefs[i] + c_i.inf, if c_i.inf > -infinity and maxlinactivityinf == 0
10910 * (node->bounds.inf - maxlinactivity)/coefs[i], if c_i.inf == -infinity and maxlinactivityinf == 1
10918 childbounds.sup = SCIPintervalNegateReal((node->bounds.inf - maxlinactivity)/SCIPintervalNegateReal(coefs[i]));
10922 childbounds.sup = SCIPintervalNegateReal((node->bounds.inf - maxlinactivity + ac.sup)/SCIPintervalNegateReal(coefs[i]));
10927 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
10956 /* too expensive, runtime here is O(nchildren * nquadelems) = O(nquadelems^2) since nchildren <= 2*nquadelems usually */
10990 if( (childbounds.inf > node->children[0]->bounds.inf + 1e-9 || childbounds.sup + 1e-9 < node->children[0]->bounds.sup) )
10992 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",
10995 node->children[1]->bounds.inf, node->children[1]->bounds.sup, childbounds.inf, childbounds.sup, (int)SCIPintervalIsEmpty(infinity, childbounds)
11002 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
11013 if( (childbounds.inf > node->children[1]->bounds.inf + 1e-9 || childbounds.sup + 1e-9 < node->children[1]->bounds.sup) )
11015 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",
11018 node->children[1]->bounds.inf, node->children[1]->bounds.sup, childbounds.inf, childbounds.sup, (int)SCIPintervalIsEmpty(infinity, childbounds)
11025 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
11058 SCIPintervalMulScalar(infinity, &tmp, node->children[quadelems[k].idx2]->bounds, quadelems[k].coef);
11063 SCIPintervalMulScalar(infinity, &tmp, node->children[quadelems[k].idx1]->bounds, quadelems[k].coef);
11074 SCIPintervalMul(infinity, &tmp, node->children[quadelems[k].idx1]->bounds, node->children[quadelems[k].idx2]->bounds);
11082 SCIPintervalSolveUnivariateQuadExpression(infinity, &childbounds, a, b, c, node->children[i]->bounds);
11086 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
11178 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - 2.0*n);
11188 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - n);
11207 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - 2.0*n);
11217 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - n);
11233 SCIPintervalPowerScalar(infinity, &tmp, node->children[monomial->childidxs[k]]->bounds, monomial->exponents[k]);
11269 SCIPdebugMessage("solve [%10g,%10g]c%d^%g + [%10g,%10g]c%d^%g = [%10g,%10g] for c%d^%g in [%10g,%10g]",
11270 a.inf, a.sup, i, 2*n, b.inf, b.sup, i, n, c.inf, c.sup, i, n, childpowbounds.inf, childpowbounds.sup);
11281 SCIPdebugPrintf(" with c%d = [%10g, %10g] -> c%d = [%10g, %10g]\n", i, node->children[i]->bounds.inf, node->children[i]->bounds.sup, i, childbounds.inf, childbounds.sup);
11289 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
11291 /* SCIPdebugMessage("-> node %p (%d,%d): [%10g,%10g] = ", (void*)node, node->depth, node->pos, node->bounds.inf, node->bounds.sup);
11315 SCIP_CALL_ABORT( exprdata->prop(infinity, exprdata->userdata, 1, &childbounds, node->bounds, cutoff) );
11318 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
11323 SCIP_ALLOC_ABORT( BMSallocBlockMemoryArray(exprgraph->blkmem, &childrenbounds, node->nchildren) );
11327 SCIP_CALL_ABORT( exprdata->prop(infinity, exprdata->userdata, node->nchildren, childrenbounds, node->bounds, cutoff) );
11331 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[c], childrenbounds[c], minstrength, infinity, cutoff);
11460 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, node->nchildren, lastnonnull+1) );
11472 /** aims at simplifying a node in an expression graph, assuming all children have been simplified
11482 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
11505 SCIPdebugMessage("attempt simplification of node %p (%d,%d)\n", (void*)node, node->depth, node->pos);
11517 SCIPdebugMessage("turn node %p (%d,%d) into constant %g\n", (void*)node, node->depth, node->pos, node->value);
11576 * 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
11584 * if child was simplified in this round, it may have already been converted, and then nothing happens
11606 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
11619 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && node->children[i]->data.dbl < 0.0 ) /*lint !e835*/
11622 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n", node->children[i]->data.dbl, monomial->exponents[factorpos]);
11663 * if child was simplified in this round, it may have already been converted, and then nothing happens
11666 SCIP_CALL( exprConvertToPolynomial(blkmem, &node->children[i]->op, &node->children[i]->data, node->children[i]->nchildren) );
11682 SCIP_CALL( exprgraphNodeAddChildren(blkmem, node, node->children[i]->nchildren, node->children[i]->children, childmap) );
11692 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
11695 /* make sure factors are merged, should only be potentially necessary if not sorted, see also #1848 */
11713 SCIP_CALL( polynomialdataExpandMonomialFactor(blkmem, messagehdlr, polynomialdata, j, factorpos,
11714 (SCIP_EXPRDATA_POLYNOMIAL*)node->children[i]->data.data, childmap, maxexpansionexponent, &success) );
11724 /* expansion may remove monomials[j], move a monomial from the end to position j, or add new monomials to the end of polynomialdata
11789 * but if we found duplicates in the children array, then it should be reduced, and we want to count this as a change too
11831 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[i], &childexprs[i], nexprvars, varidx) ); /*lint !e613*/
11852 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, SCIP_EXPR_VARIDX, varidx[node->data.intval]) );
11868 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], node->data.dbl) ); /*lint !e613*/
11877 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], node->data.intval) ); /*lint !e613*/
11891 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], childexprs[1]) ); /*lint !e613*/
11925 SCIP_CALL( SCIPexprCreateLinear(exprgraph->blkmem, expr, node->nchildren, childexprs, (SCIP_Real*)node->data.data, ((SCIP_Real*)node->data.data)[node->nchildren]) );
11964 SCIP_CALL( exprdata->copydata(exprgraph->blkmem, node->nchildren, exprdata->userdata, &userdata) );
11972 userdata, exprdata->evalcapability, exprdata->eval, exprdata->inteval, exprdata->curv, exprdata->prop, exprdata->estimate, exprdata->copydata, exprdata->freedata, exprdata->print) );
11992 * @note The function does not clear the array first, but only increases already existing counts.
11997 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */
12015 /** checks whether a node can be put into a component when checking block separability of an expression
12017 * If a variable used by node is already in another component, components are merged and component number is updated.
12041 exprgraphNodeCheckSeparabilityComponent(node->children[i], compnr, nchildcomps, childcomps, nvars, varcomps);
12062 /* variable is already in another component, so have to merge component compnr into that component
12095 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->nodessize, &exprgraph->nnodes, &exprgraph->nodes, &exprgraph->depth, mindepth);
12099 BMSclearMemoryArray(&exprgraph->nodessize[olddepth], exprgraph->depth - olddepth); /*lint !e866*/
12100 BMSclearMemoryArray(&exprgraph->nnodes[olddepth], exprgraph->depth - olddepth); /*lint !e866*/
12106 /** remove a variable from the variables arrays, assuming that its node will be removed or converted next */
12140 SCIP_CALL( exprgraph->exprgraphvarchgidx(exprgraph, exprgraph->userdata, exprgraph->vars[exprgraph->nvars-1], exprgraph->varnodes[exprgraph->nvars-1], exprgraph->nvars-1, varidx) );
12180 SCIPdebugMessage("move node %p (%d,%d) to depth %d\n", (void*)node, node->depth, node->pos, newdepth);
12207 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[newdepth], &exprgraph->nodessize[newdepth], exprgraph->nnodes[newdepth]+1); /*lint !e866*/
12213 /* 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) */
12220 exprgraph->nodes[olddepth][oldpos] = exprgraph->nodes[olddepth][exprgraph->nnodes[olddepth]-1];
12223 /* 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) */
12236 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
12239 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], node) < 0);
12243 /* adding a variable by moving it from a higher depth seems awkward, how did the variable get there in the first place? */
12248 /* nodes at depth 0 always have curvature linear, even before any curvature check was running */
12255 /** given a list of children, tries to find a common parent that represents a given operator with the same given data */
12263 SCIP_EXPR** exprchildren, /**< children of expression to consider when modifying (reordering) operator data, or NULL */
12264 SCIP_EXPRGRAPHNODE** parent /**< buffer to store parent node if any is found, or NULL if none found */
12295 (op != SCIP_EXPR_REALPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/
12296 (op != SCIP_EXPR_SIGNPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/
12297 (op != SCIP_EXPR_LINEAR || ((SCIP_Real*)opdata.data)[nchildren] == ((SCIP_Real*)children[0]->parents[p]->data.data)[nchildren]) && /*lint !e777*/
12298 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->nquadelems == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->nquadelems) &&
12299 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->constant == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->constant) && /*lint !e777*/
12300 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->nmonomials == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->nmonomials) &&
12301 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->constant == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->constant) /*lint !e777*/
12307 /* for all remaining children, remove parent candidates, that are not in their list of parents */
12313 /* if parentcands[p] is a parent of childnodes[i], then move last parent candidate to position p,
12326 SCIPdebugMessage("check %d parent candidates for expr with operator %d and %d children\n", nparentcands, op, nchildren);
12334 /* at this point, all parents in parentcands have the nodes in children as children and are of the same operator type
12335 * check if there is also one which corresponds to same expression and store that one in *parent
12363 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12364 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12376 * However, if there are duplicates in children, then it can happen that not every child of parentcands[p] is also one of the children.
12377 * So only if children equals parentcands[p]->children in some permutation, the expressions are the same.
12379 if( (parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1]) ||
12388 /* as in the case for two nodes, we need to check whether parentcands[p]->children and children are equal up to permutation */
12415 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12416 assert(parentcands[p]->nchildren == 2); /* that was the second criterium for adding a node to parentcands */
12417 /* order of operands matters, so check if childnodes have same order as children of parent candidate (and are the same nodes too) */
12418 if( parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1] )
12432 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */
12433 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */
12434 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */
12435 assert(parentcands[0]->data.intval == opdata.intval); /* that was another criterium for adding a node to parentcands */
12446 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */
12447 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */
12448 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */
12449 assert(parentcands[0]->data.dbl == opdata.dbl); /* that was another criterium for adding a node to parentcands */ /*lint !e777*/
12464 /* sort childnodes, take care that children in expression are sorted the same way if given (so we don't mess up assignment of coefficients) */
12466 SCIPsortPtrPtrReal((void**)children, (void**)exprchildren, exprcoef, exprgraphnodecomp, nchildren);
12471 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12472 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12475 assert(exprcoef[nchildren] == candcoef[nchildren]); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12511 /* sort children in expr and parentcands and update indices in quadelems accordingly, then sort quadelems again and compare */
12521 SCIPsortPtrPtrRealInt((void**)children, (void**)exprchildren, exprlincoef, invperm, exprgraphnodecomp, nchildren);
12526 SCIPsortPtrPtrInt((void**)children, (void**)exprchildren, invperm, exprgraphnodecomp, nchildren);
12552 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12553 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12557 assert(canddata->nquadelems == exprdata->nquadelems); /* that was a criterium for adding a node to parentcands */
12558 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12565 SCIPsortPtrRealInt((void**)parentcands[p]->children, candlincoef, invperm, exprgraphnodecomp, parentcands[p]->nchildren);
12589 /* check if children and linear coefficients in parent candidate and expression are the same */
12594 if( (exprlincoef == NULL ? 0.0 : exprlincoef[i]) != (candlincoef == NULL ? 0.0 : candlincoef[i]) ) /*lint !e777*/
12622 /* @todo in one GlobalLib instance, two polynoms differ only in the sign of all coefficients, it would be nice to recognize this somehow */
12632 /* sort children in expr and parentcands and update child indices in polynomialdata, then sort monomials again and compare */
12641 SCIPsortPtrPtrInt((void**)children, (void**)exprchildren, invperm, exprgraphnodecomp, nchildren);
12655 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12656 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12659 assert(canddata->nmonomials == exprdata->nmonomials); /* that was a criterium for adding a node to parentcands */
12660 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12730 SCIP_EXPRGRAPHNODE** exprnode, /**< buffer to store expression graph node corresponding to root of this expression */
12731 SCIP_Bool* exprnodeisnew /**< buffer to indicate whether the node in *exprnode has been newly created for this expression (otherwise, expression was already in graph) */
12779 /* find node corresponding to constant corresponding to parameter and add if not existing yet */
12803 SCIP_CALL( exprgraphAddExpr(exprgraph, expr->children[i], vars, params, &childnodes[i], &childisnew) ); /*lint !e644*/
12808 /* if all children were known already, check if there is also already a node for the expression that we aim to add */
12811 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, expr->nchildren, childnodes, expr->op, expr->data, expr->children, exprnode) );
12819 /* SCIPdebugMessage("reused node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos);
12834 SCIP_CALL( exprOpTable[expr->op].copydata(exprgraph->blkmem, expr->nchildren, expr->data, &opdata) );
12847 /* SCIPdebugMessage("created new node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos);
12859 SCIP_Bool* clearreverseprop, /**< flag to set if we had reset bound tightenings from reverse propagation */
12860 SCIP_Bool* boundchanged /**< buffer to store whether a variables bound has changes, compared to those stored in nodes */
12885 /* hmm, may happen due to numerics, let's be conservative and relax bounds to something that seems reasonable */
12900 SCIPdebugMessage("registered relaxed bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
12904 /* if a childs bounds are relaxed, then a previous reverse propagation may be invalid, so we have to clear its remainings */
12914 SCIPdebugMessage("registered tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
12921 SCIPdebugMessage("registered slightly tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
13166 /** gives linear coefficients belonging to a SCIP_EXPR_QUADRATIC expression, or NULL if all coefficients are 0.0 */
13261 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */
13262 assert(node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID); /* we assume node bounds to be valid */
13282 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&childcurv, monomial->nfactors), TERMINATE );
13307 *curv = SCIPexprcurvMonomial(monomial->nfactors, monomial->exponents, NULL, childcurv, childbounds);
13473 /* we store the coefficients and the constant in a single array and make this our operand data */
13502 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) );
13527 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) );
13549 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)node->data.data, nmonomials, monomials, copymonomials) );
13564 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */
13565 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */
13566 SCIP_DECL_USEREXPRFREEDATA ((*freedata)), /**< expression data free function, or NULL if nothing to free */
13567 SCIP_DECL_USEREXPRPRINT ((*print)) /**< expression print function, or NULL for default string "user" */
13576 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */
13577 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */
13601 /** given a node of an expression graph, splitup a linear part which variables are not used somewhere else in the same expression
13605 * If it is not linear, the node may change, i.e., the remaining nonlinear part may be stored in a new node.
13637 SCIPdebugMessage("split off linear part for %s node %p (%d,%d)\n", SCIPexpropGetName((*node)->op), (void*)*node, (*node)->depth, (*node)->pos);
13666 if( (*node)->data.dbl == 1.0 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13679 if( (*node)->data.intval == 1 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13692 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13703 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13714 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 )
13726 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 )
13736 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13747 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13758 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 )
13770 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 )
13780 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13788 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13855 assert(exprgraph->nvars > 0); /* in a simplified expr graph with no variables, there can only be const nodes, but these were handled above */
13872 SCIP_CALL( exprOpTable[orignode->op].copydata(exprgraph->blkmem, orignode->nchildren, orignode->data, &data) );
13878 SCIP_CALL( SCIPexprgraphAddNode(exprgraph, *node, -1, orignode->nchildren, orignode->children) );
13893 /* we had looked at this above already and only continued if exactly one node is still a child and linvarssize is >= 1 */
13894 assert((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX);
13895 assert((*node)->children[0]->op != SCIP_EXPR_VARIDX || (*node)->children[1]->op != SCIP_EXPR_VARIDX);
13898 varchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[0] : (*node)->children[1];
13899 otherchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[1] : (*node)->children[0];
13927 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, 2, 1) ); /*lint !e506*/
14019 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14130 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14131 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &coefs, (*node)->nchildren+1, nchildren+1) );
14262 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14263 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &quaddata->lincoefs, (*node)->nchildren, nchildren) );
14296 /* get nonlinear child usage: how often each child is used in the polynomial in a nonlinear monomial */
14341 /* we are at a linear monomial in a variable that is not used somewhere else in nonlinear form */
14344 linvars[*nlinvars] = exprgraph->vars[(*node)->children[childidx]->data.intval]; /*lint !e613*/
14404 /* if node was not duplicated and not removed but changed, then invalidate value, bounds, and simplified status */
14438 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, (*srcnode)->parents[0], srcnode, targetnode) );
14477 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);
14482 SCIPdebugMessage("remove node %p (%d, %d) with op %s from expression graph\n", (void*)*node, (*node)->depth, (*node)->pos, SCIPexpropGetName((*node)->op));
14524 exprgraph->nodes[(*node)->depth][(*node)->pos] = exprgraph->nodes[(*node)->depth][exprgraph->nnodes[(*node)->depth]-1];
14545 /* @todo should be a private method and node creation should already capture a node instead of waiting that it's added to the graph */
14598 /** disables a node and recursively all children which have no enabled parents in an expression graph */
14614 /* workaround: don't disable nodes if there could be more users than the one who is disabling the node
14615 * otherwise, if there are several nonlinear constraints using the same expression graph node as root node,
14630 SCIPdebugMessage("disabled node %p (%d,%d), nuses = %d\n", (void*)node, node->depth, node->pos, node->nuses);
14723 * Sets bound status to SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT if tightening is strong enough and not cutoff.
14729 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) */
14731 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
14746 SCIPdebugMessage("ignore bound tightening for node %p (%d,%d)\n", (void*)node, node->depth, node->pos);
14780 SCIPdebugPrintf(" -> [%10g, %10g] status %d\n", node->bounds.inf, node->bounds.sup, node->boundstatus);
14790 SCIP_Real minstrength, /**< minimal required relative bound strengthening to trigger a bound recalculation in parent nodes */
14791 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
14804 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */
14849 SCIP_CALL_TERMINATE( retcode, exprOpTable[node->op].inteval(infinity, node->data, node->nchildren, childbounds, NULL, NULL, &newbounds), TERMINATE );
14851 /* if bounds of a children were relaxed or our bounds were tightened by a (now possibly invalid) reverse propagation from a parent
14852 * and now our bounds are relaxed, then we have to propagate this upwards to ensure valid bounds
14854 * if bounds were tightened (considerably), then tell this to those parents which think that they have valid bounds
14856 * finally, if there was only a little tightening, then keep this updated bounds, but don't notify parents
14859 ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED) || ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) && clearreverseprop)) )
14879 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);
14890 SCIPdebugMessage("node %p(%d,%d) has empty domain in SCIPexprgraphUpdateNodeBoundsCurvature\n", (void*)node, node->depth, node->pos);
14894 SCIP_CALL_TERMINATE( retcode, exprOpTable[node->op].curv(infinity, node->data, node->nchildren, childbounds, childcurv, &node->curv), TERMINATE );
14896 /* SCIPdebugMessage("curvature %s for %s = ", SCIPexprcurvGetName(node->curv), SCIPexpropGetName(node->op));
15113 int varssizeinit, /**< minimal initial size for variables array, or -1 to choose automatically */
15114 int depthinit, /**< minimal initial depth of expression graph, or -1 to choose automatically */
15115 SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)), /**< callback method to invoke when a variable has been added to the expression graph, or NULL if not needed */
15116 SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)), /**< callback method to invoke when a variable will be removed from the expression graph, or NULL if not needed */
15117 SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)), /**< callback method to invoke when a variable changes its index in the expression graph, or NULL if not needed */
15133 ensureBlockMemoryArraySize3((*exprgraph)->blkmem, &(*exprgraph)->varnodes, &(*exprgraph)->vars, &(*exprgraph)->varbounds, &(*exprgraph)->varssize, varssizeinit);
15134 SCIP_CALL( SCIPhashmapCreate(&(*exprgraph)->varidxs, (*exprgraph)->blkmem, (*exprgraph)->varssize) );
15168 BMSfreeBlockMemoryArrayNull(blkmem, &(*exprgraph)->nodes[d], (*exprgraph)->nodessize[d]); /*lint !e866*/
15201 int mindepth, /**< minimal depth in expression graph where to add node, e.g., 0 or smaller to choose automatically */
15232 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[depth], &exprgraph->nodessize[depth], exprgraph->nnodes[depth]+1); /*lint !e866*/
15251 SCIP_ALLOC( BMSduplicateBlockMemoryArray(exprgraph->blkmem, &node->children, children, nchildren) );
15263 /* set bounds to entire, set status to "should recompute", and note that we have to update something */
15269 /* if not a variable, set value of node according to values of children (if all have valid values) */
15286 SCIP_EXPRGRAPHNODE** varnodes /**< array to store nodes corresponding to variables, or NULL if not of interest */
15297 /* 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 */
15300 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + nvars);
15301 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[0], &exprgraph->nodessize[0], exprgraph->nnodes[0] + nvars);
15329 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1);
15333 SCIP_CALL( SCIPhashmapInsertInt(exprgraph->varidxs, vars[i], exprgraph->nvars) ); /*lint !e613*/
15339 SCIPdebugMessage("added node %p (%d, %d) for new variable %d\n", (void*)node, node->depth, node->pos, node->data.intval);
15344 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[i], node) ); /*lint !e613*/
15358 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store pointer to expression graph node corresponding to constant */
15386 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
15389 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], *constnode) < 0);
15391 SCIPdebugMessage("added node %p (%d, %d) for new constant %g\n", (void*)constnode, (*constnode)->depth, (*constnode)->pos, (*constnode)->data.dbl);
15407 SCIP_EXPRGRAPHNODE** rootnode, /**< buffer to store expression graph node corresponding to root of expression tree */
15408 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) */
15427 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[0]->root, exprtrees[0]->vars, exprtrees[0]->params, rootnode, rootnodeisnew) );
15445 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[i]->root, exprtrees[i]->vars, exprtrees[i]->params, &rootnodes[i], &rootnodeisnew_) ); /*lint !e644*/
15476 /* all exprtrees were in the graph already, check if we also already have a node for the sum of rootnodes */
15477 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, op, data, NULL, rootnode) );
15508 /* all exprtrees were in the graph already, check if we also already have a node for the linear combination of rootnodes */
15509 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, SCIP_EXPR_LINEAR, data, NULL, rootnode) );
15534 rootnodeisnew ? "new" : "old", (void*)*rootnode, (*rootnode)->depth, (*rootnode)->pos, nexprtrees);
15590 SCIPdebugMessage("try to replace varnode %p (%d uses, %d parents) by %p\n", (void*)varnode, varnode->nuses, varnode->nparents, (void*)node);
15610 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varnode->children, 1) ); /*lint !e506*/
15617 varnode->boundstatus = (node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID) ? SCIP_EXPRBOUNDSTATUS_VALID : SCIP_EXPRBOUNDSTATUS_CHILDRELAXED;
15636 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
15639 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], varnode) < 0);
15651 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1);
15655 SCIP_CALL( SCIPhashmapInsertInt(exprgraph->varidxs, vars[0], exprgraph->nvars) ); /*lint !e613*/
15661 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[0], varnode) ); /*lint !e613*/
15718 SCIP_EXPRGRAPHNODE** varnode /**< buffer to store node corresponding to variable, if found, or NULL if not found */
15747 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store node corresponding to constant, if found, or NULL if not found */
15808 SCIPmessageFPrintInfo(messagehdlr, file, "node [fontcolor=white, style=filled, rankdir=LR]\n");
15865 SCIP_Bool clearreverseprop, /**< whether to reset bound tightenings from reverse propagation */
15866 SCIP_Bool* domainerror /**< buffer to store whether a node with empty bounds has been found, propagation is interrupted in this case */
15882 /* if variable bounds have not changed and we do not have to clear a previous backward propagation, we can just return */
15885 SCIPdebugMessage("no bounds changed and clearreverseprop is FALSE -> skip propagation of variable bounds\n");
15898 SCIPdebugMessage("bounds of node %p(%d,%d) empty, stop bounds propagation\n", (void*)node, node->depth, node->pos);
15914 * NOTE: it is assumed that SCIPexprgraphPropagateVarBounds was called before if variable bounds were relaxed.
15919 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */
15920 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
15944 /** updates curvature information in expression graph nodes w.r.t. currently stored variable bounds
15951 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
15979 SCIPerrorMessage("SCIPexprgraphCheckCurvature gets domain error while propagating variables bounds, ignoring...\n");
15989 * 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)).
15995 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
15997 SCIP_Bool* domainerror /**< buffer to indicate whether a domain error has been encountered, i.e., some expressions turned into NaN */
16031 exprgraph->varbounds[i].inf < -100.0 ? MIN(-100.0, exprgraph->varbounds[i].sup) : exprgraph->varbounds[i].inf,
16032 exprgraph->varbounds[i].sup > 100.0 ? MAX( 100.0, exprgraph->varbounds[i].inf) : exprgraph->varbounds[i].sup); /*lint !e644*/
16040 /* 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 */
16070 * for each node, convert to polynomials and merge in child nodes that are not in use otherwise, if possible
16089 /* we should be careful about declaring numbers close to zero as zero, so take eps^2 as tolerance */
16090 SCIP_CALL( exprgraphNodeSimplify(exprgraph, node, messagehdlr, eps*eps, maxexpansionexponent, &havechangenode) );
16121 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be simplified */
16141 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */
16151 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */
16180 SCIP_CALL( exprUnconvertPolynomial(exprgraph->blkmem, &node->op, &node->data, node->nchildren, (void**)node->children) );
16190 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, node->parents[j], &node, node->children[0]) );
16195 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be unconverted */
16227 /* nodes that are in use should not have been removed by simplifier, check if they still have the same value in our testpoint */
16239 assert(!SCIPisFinite(testval_before) || EPSZ(SCIPrelDiff(testval_before, testval_after), 10*eps)); /*lint !e777*/
16257 SCIP_EXPRGRAPHNODE* rootnode, /**< expression graph node that should represent root of expression tree */
16272 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
16304 /** creates a sum of expression trees with pairwise disjoint variables from a given node in an expression graph
16311 int exprtreessize, /**< length of exprtrees and exprtreecoefs arrays, need to be at least one */
16342 /* easy cases: if we have space for only one tree or there is only one child or only one variable in the graph,
16349 (node->op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1) &&
16350 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1)) )
16369 exprgraphNodeCheckSeparabilityComponent(node->children[i], &compnr, i-1, childcomp, exprgraph->nvars, varcomp); /*lint !e644*/
16392 /* reassign all children in component childcomp[data->quadelems[i].idx2] to component childcomp[data->quadelems[i].idx1] */
16411 if( childcomp[data->monomials[i]->childidxs[j]] != childcomp[data->monomials[i]->childidxs[0]] )
16413 /* reassign all children in component childcomp[data->monomials[i]->childidxs[j]] to component childcomp[data->monomials[i]->childidxs[0]] */
16418 assert(childcomp[data->monomials[i]->childidxs[j]] == childcomp[data->monomials[i]->childidxs[0]]);
16449 /* it turned out that expression is not block separable, so fallback to SCIPexprgraphGetTree */
16461 /* if we have not enough space for all expressions, merge components with number > exprtreessize into component exprtreessize */
16472 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varidx, exprgraph->nvars) ); /* mapping of expression graph variable indices to expression tree variable indices */
16473 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmap, node->nchildren) ); /* mapping of child indices from node to expressions belonging to a single component */
16474 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmapinv, node->nchildren) ); /* mapping of child indices from expressions belonging to a single component to node */
16492 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[j], &exprs[nexprs], &nexprvars, varidx) ); /*lint !e644*/
16506 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16517 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16518 /* if component i consists of first child, then it has coefficient 1.0, otherwise it has coefficient -1 */
16530 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16538 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16556 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16565 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_CONST, nodecoefs[node->nchildren]/nodecoefs[childmapinv[0]]) );
16567 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16574 if( nexprs == 2 && nodecoefs[childmapinv[0]] == nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/
16580 else if( nexprs == 2 && nodecoefs[childmapinv[0]] == -nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/
16583 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_MINUS, exprs[0], exprs[1]) );
16601 /* if all coefficients are equal and no constant, create SUM expression, otherwise LINEAR expression */
16609 SCIP_CALL( SCIPexprCreateLinear(exprgraph->blkmem, &sumexpr, nexprs, exprs, coefs, i == 0 ? nodecoefs[node->nchildren] : 0.0) );
16616 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16651 quadelems[nquadelems].idx1 = MIN(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]); /*lint !e644*/
16652 quadelems[nquadelems].idx2 = MAX(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]);
16658 SCIP_CALL( SCIPexprCreateQuadratic(exprgraph->blkmem, &quadexpr, nexprs, exprs, i == 0 ? nodedata->constant : 0.0, lincoefs, nquadelems, quadelems) );
16659 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], quadexpr, nexprvars, 0, NULL) );
16693 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomials[nmonomials], nodedata->monomials[j]->coef, nodedata->monomials[j]->nfactors,
16703 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &polyexpr, nexprs, exprs, nmonomials, monomials, i == 0 ? constant : 0.0, FALSE) );
16704 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], polyexpr, nexprvars, 0, NULL) );
16741 /** returns how often expression graph variables are used in a subtree of the expression graph */
16745 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */
16757 /** gives the number of summands which the expression of an expression graph node consists of */
16793 /** creates a sum of expression trees, possibly sharing variables, from a given node in an expression graph */
16797 int exprtreessize, /**< length of exprtrees and exptreecoefs arrays, should be at least SCIPexprgraphGetSumTreesNSummands() */
16821 (node->op != SCIP_EXPR_QUADRATIC || (((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->lincoefs == NULL && ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1)) &&
16822 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1) )
16896 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodecoefs[node->nchildren] / exprtreecoefs[0]) );
16934 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
16945 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx1], &expr, &nexprvars, varidx) );
16956 /* create expression from the subgraph at quadelems[i].idx2, may add more variables into varidx */
16957 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx2], &expr2, &nexprvars, varidx) );
16963 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) );
16968 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) );
16989 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodedata->constant / exprtreecoefs[0]) );
17018 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
17031 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) );
17042 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_INTPOWER, expr, (int)monomials[i]->exponents[0]) );
17046 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_REALPOWER, expr, monomials[i]->exponents[0]) );
17049 else if( monomials[i]->nfactors == 2 && monomials[i]->exponents[0] == 1.0 && monomials[i]->exponents[1] == 1.0 )
17054 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) );
17055 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[1]], &expr2, &nexprvars, varidx) );
17069 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childidxs, monomials[i]->nfactors) );
17072 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[f]], &exprs[f], &nexprvars, varidx) ); /*lint !e644*/
17077 * add also constant here, but need to divide by monomial coefficient, since we set the exprtreecoefs to monomial coef
17079 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomial, 1.0, monomials[i]->nfactors, childidxs, monomials[i]->exponents) );
17080 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &expr, monomials[i]->nfactors, exprs, 1, &monomial, constant / monomials[i]->coef, FALSE) );
17088 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) );
17093 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) );
17108 /* add constant to first summand, if still nonzero; need to divide by coefficient of the this exprtree */
17114 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:2167
#define SCIP_EXPRBOUNDSTATUS_CHILDRELAXED
Definition: type_expr.h:213
SCIP_Real SCIPexprgraphGetNodeVal(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13356
SCIP_RETCODE SCIPexprgraphPropagateVarBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Bool clearreverseprop, SCIP_Bool *domainerror)
Definition: expr.c:15862
void SCIPexprtreeGetVarsUsage(SCIP_EXPRTREE *tree, int *varsusage)
Definition: expr.c:8909
void SCIPquadelemSort(SCIP_QUADELEM *quadelems, int nquadelems)
Definition: expr.c:9213
SCIP_RETCODE SCIPexprgraphReplaceVarByLinearSum(SCIP_EXPRGRAPH *exprgraph, void *var, int ncoefs, SCIP_Real *coefs, void **vars, SCIP_Real constant)
Definition: expr.c:15543
void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:780
void SCIPintervalMax(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:2580
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:459
Definition: type_expr.h:57
static void exprgraphSortConstNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:9669
void SCIPexprgraphSetVarNodeValue(SCIP_EXPRGRAPHNODE *varnode, SCIP_Real value)
Definition: expr.c:14998
static SCIP_RETCODE exprgraphNodeAddParent(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE *parent)
Definition: expr.c:9346
SCIP_RETCODE SCIPexprSubstituteVars(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR **substexprs)
Definition: expr.c:8149
static SCIP_RETCODE exprsimplifyConvertToPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4268
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
Definition: intervalarith.c:452
SCIP_RETCODE SCIPexprgraphAddNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int mindepth, int nchildren, SCIP_EXPRGRAPHNODE **children)
Definition: expr.c:15198
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2487
void SCIPintervalSign(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2790
static SCIP_RETCODE eval(SCIP_EXPR *expr, const vector< Type > &x, SCIP_Real *param, Type &val)
Definition: exprinterpret_cppad.cpp:1769
static SCIP_RETCODE exprsimplifyRemoveDuplicatePolynomialChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real eps)
Definition: expr.c:4292
SCIP_RETCODE SCIPexprgraphGetSumTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs)
Definition: expr.c:16794
SCIP_RETCODE SCIPexprtreeEvalInt(SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_INTERVAL *val)
Definition: expr.c:8741
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:15282
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:8758
int * SCIPexprGetMonomialChildIndices(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5924
SCIP_RETCODE SCIPexprgraphUpdateNodeBoundsCurvature(SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool clearreverseprop)
Definition: expr.c:14787
static SCIP_RETCODE polynomialdataMultiplyByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap)
Definition: expr.c:956
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:3763
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:8030
static SCIP_RETCODE exprgraphNodeAddChildren(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, int nexprs, SCIP_EXPRGRAPHNODE **exprs, int *childmap)
Definition: expr.c:9492
int SCIPexprgraphGetNodeNChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12992
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:11807
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:8229
static SCIP_RETCODE exprgraphEnsureDepth(SCIP_EXPRGRAPH *exprgraph, int mindepth)
Definition: expr.c:12081
static void polynomialdataSortMonomials(SCIP_EXPRDATA_POLYNOMIAL *polynomialdata)
Definition: expr.c:801
static SCIP_RETCODE exprgraphNodeSimplify(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, SCIP_Bool *havechange)
Definition: expr.c:11477
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2548
static SCIP_RETCODE polynomialdataMultiplyByPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_EXPRDATA_POLYNOMIAL *factordata, int *childmap)
Definition: expr.c:1000
static SCIP_RETCODE exprparseFindSeparatingComma(const char *str, const char **endptr, int length)
Definition: expr.c:5067
static SCIP_RETCODE exprgraphNodeRemovePolynomialNullChildren(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:11408
void SCIPexprChgPolynomialConstant(SCIP_EXPR *expr, SCIP_Real constant)
Definition: expr.c:6693
SCIP_RETCODE SCIPexprgraphAddConst(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode)
Definition: expr.c:15355
Definition: type_expr.h:74
SCIP_RETCODE SCIPexprtreeGetMaxDegree(SCIP_EXPRTREE *tree, int *maxdegree)
Definition: expr.c:8712
SCIP_Real * SCIPexprtreeGetParamVals(SCIP_EXPRTREE *tree)
Definition: expr.c:8634
void SCIPexprgraphSetVarNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_INTERVAL varbounds)
Definition: expr.c:15042
SCIP_RETCODE SCIPexprCreateMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL **monomial, SCIP_Real coef, int nfactors, int *childidxs, SCIP_Real *exponents)
Definition: expr.c:7039
void SCIPexprgraphCaptureNode(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12970
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:13485
SCIP_Real SCIPexprGetRealPowerExponent(SCIP_EXPR *expr)
Definition: expr.c:5760
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
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:7799
SCIP_RETCODE SCIPexprPolynomialPower(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int exponent)
Definition: expr.c:6789
void SCIPexprChgMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real newcoef)
Definition: expr.c:6855
SCIP_Real SCIPexprGetPolynomialConstant(SCIP_EXPR *expr)
Definition: expr.c:5892
void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode)
Definition: intervalarith.c:262
void SCIPexprgraphPropagateNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool *cutoff)
Definition: expr.c:15916
void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:911
#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT
Definition: type_expr.h:214
SCIP_Bool SCIPexprAreEqual(SCIP_EXPR *expr1, SCIP_EXPR *expr2, SCIP_Real eps)
Definition: expr.c:7584
void SCIPexprMonomialPower(SCIP_EXPRDATA_MONOMIAL *monomial, int exponent)
Definition: expr.c:6930
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetVarNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14988
Definition: type_expr.h:62
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9981
Definition: type_expr.h:73
static void exprgraphNodeCheckSeparabilityComponent(SCIP_EXPRGRAPHNODE *node, int *compnr, int nchildcomps, int *childcomps, int nvars, int *varcomps)
Definition: expr.c:12020
static SCIP_RETCODE exprgraphNodeRemovePolynomialDuplicateChildren(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:11350
SCIP_Real SCIPexprgraphGetNodeSignPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13121
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:3294
Definition: struct_misc.h:259
SCIP_RETCODE SCIPexprtreeCopy(BMS_BLKMEM *blkmem, SCIP_EXPRTREE **targettree, SCIP_EXPRTREE *sourcetree)
Definition: expr.c:8814
int SCIPexprgraphGetNodeNParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13012
void SCIPexprGetVarsUsage(SCIP_EXPR *expr, int *varsusage)
Definition: expr.c:7561
void SCIPintervalMin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:2564
SCIP_INTERVAL SCIPexprgraphGetNodeBounds(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13346
SCIP_RETCODE SCIPexprgraphEval(SCIP_EXPRGRAPH *exprgraph, SCIP_Real *varvals)
Definition: expr.c:15841
void SCIPexprReindexVars(SCIP_EXPR *expr, int *newindices)
Definition: expr.c:8187
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
Definition: intervalarith.c:427
void SCIPintervalPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1838
int * SCIPexprgraphGetNNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14948
SCIP_RETCODE SCIPexprEvalInt(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val)
Definition: expr.c:7931
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:7120
static void polynomialdataApplyChildmap(SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int *childmap)
Definition: expr.c:1160
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:15402
SCIP_RETCODE SCIPexprMultiplyMonomialByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap)
Definition: expr.c:6895
SCIP_RETCODE SCIPexprtreeCreate(BMS_BLKMEM *blkmem, SCIP_EXPRTREE **tree, SCIP_EXPR *root, int nvars, int nparams, SCIP_Real *params)
Definition: expr.c:8773
SCIP_Bool SCIPquadelemSortedFind(SCIP_QUADELEM *quadelems, int idx1, int idx2, int nquadelems, int *pos)
Definition: expr.c:9238
void SCIPexprtreeSetParamVal(SCIP_EXPRTREE *tree, int paramidx, SCIP_Real paramval)
Definition: expr.c:8644
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:1089
int SCIPexprgraphGetNodePolynomialNMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13215
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:10040
static void exprgraphUpdateVarNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Bool *clearreverseprop, SCIP_Bool *boundchanged)
Definition: expr.c:12857
SCIP_RETCODE SCIPexprgraphMoveNodeParents(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **srcnode, SCIP_EXPRGRAPHNODE *targetnode)
Definition: expr.c:14421
SCIP_EXPRCURV SCIPexprcurvMonomial(int nfactors, SCIP_Real *exponents, int *factoridxs, SCIP_EXPRCURV *factorcurv, SCIP_INTERVAL *factorbounds)
Definition: expr.c:362
SCIP_EXPRDATA_MONOMIAL ** SCIPexprGetMonomials(SCIP_EXPR *expr)
Definition: expr.c:5868
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:2236
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:241
int SCIPexprGetMonomialNFactors(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5914
void SCIPintervalSin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2624
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
#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:9012
SCIP_EXPROP SCIPexprgraphGetNodeOperator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13052
static SCIP_RETCODE exprgraphCreateNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_EXPROP op, SCIP_EXPROPDATA opdata)
Definition: expr.c:9740
SCIP_EXPRDATA_MONOMIAL ** SCIPexprgraphGetNodePolynomialMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13203
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:15110
Definition: type_expr.h:47
Definition: type_expr.h:49
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
int SCIPexprgraphGetNodeOperatorIndex(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13062
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:4927
Definition: struct_misc.h:128
Definition: type_expr.h:53
SCIP_Real SCIPexprgraphGetNodeLinearConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13143
#define ensureBlockMemoryArraySize3(blkmem, array1, array2, array3, cursize, minsize)
Definition: expr.c:88
#define BMSduplicateBlockMemoryArray(mem, ptr, source, num)
Definition: memory.h:453
SCIP_Real SCIPexprgraphGetNodePolynomialConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13227
SCIP_RETCODE SCIPexprAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:6671
SCIP_Bool SCIPexprgraphHasNodeNonlinearAncestor(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14672
SCIP_EXPRCURV SCIPexprgraphGetNodeCurvature(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13366
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:6588
Definition: type_expr.h:51
SCIP_Bool SCIPexprgraphFindConstNode(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode)
Definition: expr.c:15744
SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand)
Definition: intervalarith.c:476
SCIP_RETCODE SCIPexprEval(SCIP_EXPR *expr, SCIP_Real *varvals, SCIP_Real *param, SCIP_Real *val)
Definition: expr.c:7870
void SCIPexprgraphSetVarsBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_INTERVAL *varbounds)
Definition: expr.c:15010
static SCIP_Bool isUbBetter(SCIP_Real minstrength, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: expr.c:170
Definition: type_retcode.h:36
SCIP_RETCODE SCIPexprgraphCheckCurvature(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Bool clearreverseprop)
Definition: expr.c:15948
SCIP_RETCODE SCIPexprGetMaxDegree(SCIP_EXPR *expr, int *maxdegree)
Definition: expr.c:7236
static void polynomialdataMultiplyByConstant(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_Real factor)
Definition: expr.c:926
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10705
interval arithmetics for provable bounds
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
Definition: intervalarith.c:441
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:13555
SCIP_Real * SCIPexprGetQuadLinearCoefs(SCIP_EXPR *expr)
Definition: expr.c:5844
SCIP_EXPRGRAPHNODE *** SCIPexprgraphGetNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14958
int SCIPexprgraphGetSumTreesNSummands(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:16758
static SCIP_RETCODE exprsimplifyRemovePolynomialNullChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4346
void SCIPintervalLog(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2496
SCIP_RETCODE SCIPexprCopyDeep(BMS_BLKMEM *blkmem, SCIP_EXPR **targetexpr, SCIP_EXPR *sourceexpr)
Definition: expr.c:6145
Definition: type_expr.h:52
SCIP_Bool SCIPexprgraphHasNodeUserEstimator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13334
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:5099
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:491
SCIP_EXPRCURV SCIPexprcurvPower(SCIP_INTERVAL basebounds, SCIP_EXPRCURV basecurv, SCIP_Real exponent)
Definition: expr.c:254
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:9593
void SCIPmessagePrintWarning(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:418
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:9943
static SCIP_Bool exprgraphNodeIsParent(SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE *parent)
Definition: expr.c:9461
static void polynomialdataFree(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata)
Definition: expr.c:713
void SCIPexprMergeMonomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real eps, SCIP_Bool mergefactors)
Definition: expr.c:6809
SCIP_Bool SCIPexprAreMonomialsEqual(SCIP_EXPRDATA_MONOMIAL *monomial1, SCIP_EXPRDATA_MONOMIAL *monomial2, SCIP_Real eps)
Definition: expr.c:6824
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:13459
SCIP_RETCODE SCIPexprgraphGetSeparableTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs)
Definition: expr.c:16308
SCIP_Bool SCIPexprgraphIsNodeEnabled(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12982
SCIP_INTERVAL * SCIPexprgraphGetVarsBounds(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:15102
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:6636
SCIP_RETCODE SCIPexprCheckCurvature(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varbounds, SCIP_Real *param, SCIP_EXPRCURV *curv, SCIP_INTERVAL *bounds)
Definition: expr.c:8066
SCIP_RETCODE SCIPexprEvalUser(SCIP_EXPR *expr, SCIP_Real *argvals, SCIP_Real *val, SCIP_Real *gradient, SCIP_Real *hessian)
Definition: expr.c:7973
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:585
SCIP_RETCODE SCIPexprEvalShallow(SCIP_EXPR *expr, SCIP_Real *argvals, SCIP_Real *varvals, SCIP_Real *param, SCIP_Real *val)
Definition: expr.c:7851
void SCIPexprMultiplyPolynomialByConstant(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real factor)
Definition: expr.c:6706
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
Definition: intervalarith.c:415
void SCIPexprgraphTightenNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_INTERVAL nodebounds, SCIP_Real minstrength, SCIP_Real infinity, SCIP_Bool *cutoff)
Definition: expr.c:14725
static SCIP_RETCODE exprsimplifyUnconvertPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4893
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:8111
static SCIP_RETCODE exprgraphNodeUpdateBounds(SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool parenttightenisinvalid)
Definition: expr.c:10147
void SCIPexprFreeMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL **monomial)
Definition: expr.c:7096
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:6408
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:7157
SCIP_Bool SCIPexprgraphHasNodeSibling(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14637
SCIP_RETCODE SCIPexprgraphGetNodePolynomialMonomialCurvature(SCIP_EXPRGRAPHNODE *node, int monomialidx, SCIP_Real infinity, SCIP_EXPRCURV *curv)
Definition: expr.c:13242
Definition: type_retcode.h:34
SCIP_Real SCIPexprgraphGetNodeOperatorReal(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13073
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:6250
SCIP_Real SCIPexprgraphGetNodeQuadraticConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13155
SCIP_RETCODE SCIPexprMultiplyPolynomialByPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR *factor, int *childmap)
Definition: expr.c:6743
void SCIPexprMergeMonomialFactors(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real eps)
Definition: expr.c:6960
void SCIPintervalCos(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2708
SCIP_EXPRINTCAPABILITY SCIPexprGetUserEvalCapability(SCIP_EXPR *expr)
Definition: expr.c:5966
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:834
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:5782
static SCIP_RETCODE exprgraphNodeEval(SCIP_EXPRGRAPHNODE *node, SCIP_Real *varvals)
Definition: expr.c:10082
SCIP_Bool SCIPexprgraphAreAllNodeChildrenVars(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14656
void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
Definition: intervalarith.c:3236
Definition: type_expr.h:39
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
static SCIP_RETCODE monomialdataEnsureFactorsSize(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomialdata, int minsize)
Definition: expr.c:604
void SCIPexprgraphSetVarNodeLb(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_Real lb)
Definition: expr.c:15062
SCIP_EXPORT SCIP_RETCODE SCIPexprintFreeData(SCIP_EXPRINTDATA **interpreterdata)
Definition: exprinterpret_cppad.cpp:2259
static SCIP_RETCODE exprsimplifyFlattenPolynomials(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPR *expr, SCIP_Real eps, int maxexpansionexponent)
Definition: expr.c:4463
static SCIP_RETCODE exprgraphNodeRemoveParent(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node, SCIP_EXPRGRAPHNODE *parent)
Definition: expr.c:9401
SCIP_EXPRINTDATA * SCIPexprtreeGetInterpreterData(SCIP_EXPRTREE *tree)
Definition: expr.c:8659
SCIP_RETCODE SCIPexprtreeFreeInterpreterData(SCIP_EXPRTREE *tree)
Definition: expr.c:8682
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:3558
void SCIPquadelemSqueeze(SCIP_QUADELEM *quadelems, int nquadelems, int *nquadelemsnew)
Definition: expr.c:9290
void SCIPintervalSquareRoot(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:1442
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:3299
SCIP_EXPORT void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
void SCIPexprgraphGetSubtreeVarsUsage(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int *varsusage)
Definition: expr.c:16742
void SCIPexprgraphSetVarNodeUb(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_Real ub)
Definition: expr.c:15082
static SCIP_Bool exprgraphFindConstNodePos(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int *pos)
Definition: expr.c:9685
void SCIPintervalSquare(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:1370
SCIP_RETCODE SCIPexprgraphNodeSplitOffLinear(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node, int linvarssize, int *nlinvars, void **linvars, SCIP_Real *lincoefs, SCIP_Real *constant)
Definition: expr.c:13609
SCIP_RETCODE SCIPexprCreate(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPROP op,...)
Definition: expr.c:5977
void SCIPintervalScalprodScalars(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
Definition: intervalarith.c:1342
Definition: struct_expr.h:116
SCIP_Bool SCIPexprFindMonomialFactor(SCIP_EXPRDATA_MONOMIAL *monomial, int childidx, int *pos)
Definition: expr.c:7140
Definition: type_expr.h:58
void SCIPexprgraphFreeNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node)
Definition: expr.c:14547
void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:625
static void exprgraphNodePropagateBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool *cutoff)
Definition: expr.c:10241
#define SCIP_EXPRBOUNDSTATUS_CHILDTIGHTENED
Definition: type_expr.h:212
void SCIPexprgraphDisableNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14599
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:8983
Definition: struct_expr.h:89
void SCIPintervalAbs(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2596
SCIP_Real SCIPexprGetMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5904
static SCIP_RETCODE polynomialdataCopy(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata, SCIP_EXPRDATA_POLYNOMIAL *sourcepolynomialdata)
Definition: expr.c:676
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:1189
void * SCIPexprgraphGetNodeVar(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13084
Definition: type_expr.h:63
SCIP_Real * SCIPexprgraphGetNodeQuadraticLinearCoefs(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13167
static SCIP_RETCODE exprConvertToPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPROP *op, SCIP_EXPROPDATA *data, int nchildren)
Definition: expr.c:3325
SCIP_RETCODE SCIPexprEvalIntUser(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *argvals, SCIP_INTERVAL *val, SCIP_INTERVAL *gradient, SCIP_INTERVAL *hessian)
Definition: expr.c:7996
int SCIPexprgraphGetNodeIntPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13110
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13022
static void exprgraphNodeSortParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:9375
static SCIP_RETCODE exprgraphAddExpr(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPR *expr, void **vars, SCIP_Real *params, SCIP_EXPRGRAPHNODE **exprnode, SCIP_Bool *exprnodeisnew)
Definition: expr.c:12725
static SCIP_RETCODE polynomialdataAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:759
static void quadraticdataSort(SCIP_EXPRDATA_QUADRATIC *quadraticdata)
Definition: expr.c:529
Definition: struct_misc.h:80
SCIP_Bool SCIPexprgraphFindVarNode(SCIP_EXPRGRAPH *exprgraph, void *var, SCIP_EXPRGRAPHNODE **varnode)
Definition: expr.c:15715
Definition: type_expr.h:79
void SCIPexprReindexParams(SCIP_EXPR *expr, int *newindices)
Definition: expr.c:8208
SCIP_Real * SCIPexprgraphGetNodeLinearCoefs(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13132
#define SCIP_EXPRINTCAPABILITY_FUNCVALUE
Definition: type_exprinterpret.h:36
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
Definition: intervalarith.c:464
int SCIPexprgraphGetNodePosition(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13042
static SCIP_Bool isLbBetter(SCIP_Real minstrength, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: expr.c:150
SCIP_RETCODE SCIPexprgraphNodePolynomialAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:13536
void SCIPexprFreeShallow(BMS_BLKMEM *blkmem, SCIP_EXPR **expr)
Definition: expr.c:6225
Definition: type_expr.h:86
SCIP_QUADELEM * SCIPexprGetQuadElements(SCIP_EXPR *expr)
Definition: expr.c:5819
SCIP_RETCODE SCIPexprgraphCreateNodePolynomial(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Real constant, SCIP_Bool copymonomials)
Definition: expr.c:13511
void SCIPintervalExp(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2412
public methods for message output
SCIP_USEREXPRDATA * SCIPexprgraphGetNodeUserData(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13322
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:4792
SCIP_RETCODE SCIPexprgraphCreateNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_EXPROP op,...)
Definition: expr.c:13376
SCIP_RETCODE SCIPexprEvalIntShallow(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *argvals, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val)
Definition: expr.c:7911
SCIP_RETCODE SCIPexprgraphReleaseNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node)
Definition: expr.c:14453
#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE
Definition: type_expr.h:216
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:609
SCIP_RETCODE SCIPexprtreeSimplify(SCIP_EXPRTREE *tree, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, int *nlinvars, int *linidxs, SCIP_Real *lincoefs)
Definition: expr.c:8928
SCIP_RETCODE SCIPexprgraphGetTree(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *rootnode, SCIP_EXPRTREE **exprtree)
Definition: expr.c:16255
Definition: type_expr.h:71
Definition: type_expr.h:54
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:531
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:629
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1050
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:9927
Definition: struct_expr.h:77
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13002
SCIP_RETCODE SCIPexprAddMonomialFactors(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, int nfactors, int *childidxs, SCIP_Real *exponents)
Definition: expr.c:6866
SCIP_Real * SCIPexprGetMonomialExponents(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5934
void SCIPexprgraphPrintNode(SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: expr.c:14709
SCIP_RETCODE SCIPexprtreeSubstituteVars(SCIP_EXPRTREE *tree, SCIP_EXPR **substexprs)
Definition: expr.c:9047
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:8540
static SCIP_RETCODE exprgraphNodeEvalWithChildren(SCIP_EXPRGRAPHNODE *node, SCIP_Real *varvals)
Definition: expr.c:10126
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:15991
static SCIP_RETCODE exprsimplifyRemovePolynomialUnusedChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4412
void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:732
static SCIP_RETCODE exprgraphMoveNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int newdepth)
Definition: expr.c:12161
static SCIP_RETCODE exprparseFindClosingParenthesis(const char *str, const char **endptr, int length)
Definition: expr.c:5028
SCIP_RETCODE SCIPexprAddToLinear(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nchildren, SCIP_Real *coefs, SCIP_EXPR **children, SCIP_Real constant)
Definition: expr.c:6543
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:4149
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:6720
SCIP_Real SCIPexprgraphGetNodeRealPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13099
Definition: struct_expr.h:55
int SCIPexprgraphGetNodeQuadraticNQuadElements(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13191
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10674
Definition: type_retcode.h:43
static SCIP_RETCODE polynomialdataPower(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int exponent)
Definition: expr.c:1090
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:6506
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:652
SCIP_Real SCIPexprGetLinearConstant(SCIP_EXPR *expr)
Definition: expr.c:5806
void SCIPexprtreeSetInterpreterData(SCIP_EXPRTREE *tree, SCIP_EXPRINTDATA *interpreterdata)
Definition: expr.c:8669
SCIP_EXPRCURV SCIPexprcurvAdd(SCIP_EXPRCURV curv1, SCIP_EXPRCURV curv2)
Definition: expr.c:206
static void quadelemsQuickSort(SCIP_QUADELEM *elems, int start, int end)
Definition: expr.c:9103
static SCIP_RETCODE polynomialdataEnsureMonomialsSize(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int minsize)
Definition: expr.c:742
SCIP_RETCODE SCIPexprtreeSetParams(SCIP_EXPRTREE *tree, int nparams, SCIP_Real *paramvals)
Definition: expr.c:8878
SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void)
Definition: intervalarith.c:270
static void exprgraphPrintNodeExpression(SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames, SCIP_Bool printchildrenbounds)
Definition: expr.c:9784
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:12257
static void exprgraphNodeGetVarsUsage(SCIP_EXPRGRAPHNODE *node, int *varsusage)
Definition: expr.c:11995
SCIP_RETCODE SCIPexprgraphPrintDot(SCIP_EXPRGRAPH *exprgraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames)
Definition: expr.c:15792
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3379
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:449
void SCIPintervalSetRoundingModeDownwards(void)
Definition: intervalarith.c:338
void SCIPintervalPowerScalarInverse(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL basedomain, SCIP_Real exponent, SCIP_INTERVAL image)
Definition: intervalarith.c:2086
int SCIPexprgraphGetNodeDepth(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13032
#define ensureBlockMemoryArraySize(blkmem, array1, cursize, minsize)
Definition: expr.c:53
SCIP_RETCODE SCIPexprtreeEval(SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Real *val)
Definition: expr.c:8725
SCIP_EXPRINTCAPABILITY evalcapability
Definition: struct_expr.h:104
void SCIPexprgraphSetVarBounds(SCIP_EXPRGRAPH *exprgraph, void *var, SCIP_INTERVAL varbounds)
Definition: expr.c:15022
static SCIP_RETCODE exprgraphRemoveVar(SCIP_EXPRGRAPH *exprgraph, int varidx)
Definition: expr.c:12108
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:2914
void SCIPexprgraphEnableNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14572
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3297
SCIP_QUADELEM * SCIPexprgraphGetNodeQuadraticQuadElements(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13179