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);
3975 quaddata->lincoefs[polynomialdata->monomials[i]->childidxs[0]] += polynomialdata->monomials[i]->coef;
3994 quaddata->quadelems[quadelemidx].idx1 = MIN(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]);
3995 quaddata->quadelems[quadelemidx].idx2 = MAX(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]);
4010 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 1 && polynomialdata->monomials[0]->coef == 1.0 )
4102 if( monomial->nfactors == 2 && monomial->exponents[0] == 1.0 && monomial->exponents[1] == -1.0 )
4116 if( monomial->nfactors == 2 && monomial->exponents[0] == -1.0 && monomial->exponents[1] == 1.0 )
4141 /** adds copies of expressions to the array of children of a sum, product, linear, quadratic, or polynomial expression
4143 * For a sum or product expression, this corresponds to add additional summands and factors, resp.
4145 * For a quadratic or polynomial expression, only the children array may be enlarged, the expression itself remains the same.
4153 SCIP_Bool comparechildren, /**< whether to compare expressions with already existing children (no effect for sum and product) */
4155 int* childmap /**< array where to store mapping of indices from exprs to children array in expr, or NULL if not of interest */
4162 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);
4173 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) );
4176 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren + i], exprs[i]) ); /*lint !e613*/
4194 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) );
4202 if( expr->children[j] != NULL && SCIPexprAreEqual(expr->children[j], exprs[i], eps) ) /*lint !e613*/
4211 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren], exprs[i]) ); /*lint !e613*/
4230 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, orignchildren + nexprs, expr->nchildren) );
4238 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, orignchildren + 1, expr->nchildren + 1) );
4250 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data->lincoefs, orignchildren, expr->nchildren) );
4251 BMSclearMemoryArray(&data->lincoefs[orignchildren], expr->nchildren - orignchildren); /*lint !e866*/
4397 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, lastnonnull+1) );
4459 * exprsimplifyConvertToPolynomials should have been called before to eliminate simple polynomial operands.
4467 int maxexpansionexponent/**< maximal exponent for which we still expand non-monomial polynomials */
4476 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr->children[i], eps, maxexpansionexponent) );
4506 if( (expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) ||
4512 /* since child0 has no children and it's polynomial was flattened, it should have no monomials */
4513 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0);
4537 if( ((expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) || expr->children[0]->op == SCIP_EXPR_CONST) &&
4538 ((expr->children[1]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[1]) == 0) || expr->children[1]->op == SCIP_EXPR_CONST) )
4543 /* since children have no children and it's polynomial was flattened, it should have no monomials */
4544 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0);
4545 assert(expr->children[1]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[1]) == 0);
4598 * 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
4626 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
4641 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && SCIPexprGetOpReal(expr->children[i]) < 0.0 ) /*lint !e835*/
4644 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n",
4699 SCIP_CALL( exprsimplifyAddChildren(blkmem, expr, expr->children[i]->nchildren, expr->children[i]->children, TRUE, eps, childmap) );
4709 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
4724 SCIP_CALL( polynomialdataExpandMonomialFactor(blkmem, messagehdlr, polynomialdata, j, factorpos,
4725 (SCIP_EXPRDATA_POLYNOMIAL*)expr->children[i]->data.data, childmap, maxexpansionexponent, &success) );
4736 /* expansion may remove monomials[j], move a monomial from the end to position j, or add new monomials to the end of polynomialdata
4797 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part */
4861 if( childusage[childidx] == 1 && varsusage[SCIPexprGetOpIndex(expr->children[childidx])] == 1 )
4863 /* if the child expression is not used in another monomial (which would due to merging be not linear)
4910 SCIP_CALL( exprUnconvertPolynomial(blkmem, &expr->op, &expr->data, expr->nchildren, (void**)expr->children) );
4923 * Creates a new variable index if variable not seen before, updates varnames and vartable structures.
4933 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */
4935 const char* varnameendptr /**< if a <varname> should be parsed, set this to NULL. Then, str points to the '<'
4963 SCIPerrorMessage("Variable name %.*s is too long for buffer in exprparseReadVariable.\n", namelength, str);
4986 SCIPerrorMessage("Buffer in exprparseReadVariable is too short for varaible name %.*s.\n", namelength, str);
5022 /** if str[0] points to an opening parenthesis, this function sets endptr to point to the matching closing bracket in str
5052 SCIPerrorMessage("unable to find closing parenthesis in unbalanced expression %.*s\n", length, str);
5089 SCIPerrorMessage("unable to find separating comma in unbalanced expression %.*s\n", length, str);
5108 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */
5135 SCIPdebugMessage("exprParse (%i): parsing %.*s\n", recursiondepth, (int) (lastchar-str + 1), str);
5148 while( subexpptr != lastchar && !(nopenbrackets == 0 && (subexpptr[0] == '+' || subexpptr[0] == '-') && subexpptr != str) )
5159 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str, (int) ((subexpptr - 1) - str + 1), subexpptr - 1, nvars,
5164 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, subexpptr , (int) (lastchar - (subexpptr ) + 1), lastchar, nvars,
5168 * we always use add, because we leave the operator between the found expressions in the second argument
5169 * this way, we do not have to worry about ''minus brackets'' in the case of more then two summands:
5201 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, subexpptr, subexplength, subexpendptr, nvars, varnames,
5230 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, str, (int)(lastchar - str) + 1, lastchar, nvars, varnames,
5248 SCIP_CALL( exprparseReadVariable(blkmem, &str, expr, nvars, varnames, varnameslength, vartable, 1.0, NULL) );
5255 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5275 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5328 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5336 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, comma, endptr - comma, endptr - 1, nvars, varnames,
5357 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5364 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) )
5392 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5399 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) )
5423 /* check for a variable, that was not recognized earlier because somebody omitted the '<' and '>' we need for
5429 /* allow only variable names containing characters, digits, hash marks, and underscores here */
5433 SCIP_CALL( exprparseReadVariable(blkmem, &varnamestartptr, expr, nvars, varnames, varnameslength,
5455 SCIPerrorMessage("error finding first expression in \"%.*s\" took us outside of given subexpression length\n", length, strstart);
5483 if( isdigit((unsigned char)str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit((unsigned char)str[1])) )
5513 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5561 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames,
5619 /* if there is a part of the string left to be parsed, we assume that this as a multiplication */
5629 SCIPdebugMessage("No operator found, assuming a multiplication before %.*s\n", (int) (lastchar - str + 1), str);
5632 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames,
5799 /* the coefficients are stored in the first nchildren elements of the array stored as expression data */
6130 SCIPerrorMessage("cannot create complex expression linear, quadratic, polynomial, or user with SCIPexprCreate\n");
6160 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*targetexpr)->children, sourceexpr->nchildren) );
6170 assert((*targetexpr)->children == NULL); /* otherwise, sourceexpr->children was not NULL, which is wrong */
6178 SCIP_CALL( exprOpTable[sourceexpr->op].copydata(blkmem, sourceexpr->nchildren, sourceexpr->data, &(*targetexpr)->data) );
6243 /** creates an expression from the addition of two given expression, with coefficients, and a constant
6245 * The given expressions may be modified or freed, otherwise it will be used a child expression.
6346 if( SCIPexprGetOperator(term1) == SCIP_EXPR_LINEAR && SCIPexprGetOperator(term2) == SCIP_EXPR_LINEAR )
6352 SCIP_CALL( SCIPexprAddToLinear(blkmem, term1, SCIPexprGetNChildren(term2), SCIPexprGetLinearCoefs(term2), SCIPexprGetChildren(term2), SCIPexprGetLinearConstant(term2) + constant) );
6403 * The given expressions may be modified or freed, otherwise it will be used a child expression.
6503 /** creates a SCIP_EXPR_LINEAR expression that is (affine) linear in its children: constant + sum_i coef_i child_i */
6528 /* we store the coefficients and the constant in a single array and make this our operand data */
6571 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nchildren) );
6575 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, expr->nchildren + 1, expr->nchildren + nchildren + 1) );
6585 /** creates a SCIP_EXPR_QUADRATIC expression: constant + sum_i coef_i child_i + sum_i coef_i child1_i child2_i */
6612 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) );
6633 /** creates a SCIP_EXPR_POLYNOMIAL expression from an array of monomials: constant + sum_i monomial_i */
6660 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) );
6685 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, nmonomials, monomials, copymonomials) );
6731 SCIP_CALL( polynomialdataMultiplyByMonomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, factor, childmap) );
6739 * Children of factor need to be children of expr already, w.r.t. an optional mapping of child indices.
6777 SCIP_CALL( polynomialdataMultiplyByPolynomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, (SCIP_EXPRDATA_POLYNOMIAL*)factor->data.data, childmap) );
6798 SCIP_CALL( polynomialdataPower(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, exponent) );
6803 /** merges monomials in a polynomial expression that differ only in coefficient into a single monomial
6818 polynomialdataMergeMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, eps, mergefactors);
6883 BMScopyMemoryArray(&monomial->childidxs[monomial->nfactors], childidxs, nfactors); /*lint !e866*/
6884 BMScopyMemoryArray(&monomial->exponents[monomial->nfactors], exponents, nfactors); /*lint !e866*/
6910 SCIP_CALL( SCIPexprAddMonomialFactors(blkmem, monomial, factor->nfactors, factor->childidxs, factor->exponents) );
6988 while( i+offset+1 < monomial->nfactors && monomial->childidxs[i] == monomial->childidxs[i+offset+1] )
7060 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->childidxs, childidxs, nfactors) );
7073 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->exponents, exponents, nfactors) );
7135 * Note that if the factors have not been merged, the position of some factor corresponding to a given child is given.
7161 SCIP_EXPRINTCAPABILITY evalcapability, /**< capability of evaluation functions (partially redundant, currently) */
7163 SCIP_DECL_USEREXPRINTEVAL ((*inteval)), /**< interval evaluation function, or NULL if not implemented */
7165 SCIP_DECL_USEREXPRPROP ((*prop)), /**< interval propagation function, or NULL if not implemented */
7166 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */
7167 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */
7168 SCIP_DECL_USEREXPRFREEDATA ((*freedata)), /**< expression data free function, or NULL if nothing to free */
7169 SCIP_DECL_USEREXPRPRINT ((*print)) /**< expression print function, or NULL for default string "user" */
7179 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */
7180 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */
7340 else if( expr->data.dbl > 0.0 && (int)expr->data.dbl == expr->data.dbl ) /* natural exponent gives polynomial again */ /*lint !e777*/
7469 /* if no linear or no quadratic coefficient with current child on first position, then nothing to do */
7481 while( quadidx < quadraticdata->nquadelems && quadraticdata->quadelems[quadidx].idx1 == childidx )
7492 SCIP_CALL( SCIPexprGetMaxDegree(expr->children[quadraticdata->quadelems[quadidx].idx2], &child2) );
7532 /* if the exponent of the factor is not a natural number and the child is not constant (degree 0),
7534 if( child1 != 0 && (monomialdata->exponents[j] < 0.0 || (int)monomialdata->exponents[j] != monomialdata->exponents[j]) )
7613 return SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps) && SCIPexprAreEqual(expr1->children[1], expr2->children[1], eps);
7631 return EPSEQ(expr1->data.dbl, expr2->data.dbl, eps) && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps);
7634 return expr1->data.intval == expr2->data.intval && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps);
7795 * If linear variables are split off, expression interpreter data, if stored in the tree, is freed.
7802 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
7804 int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */
7805 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */
7823 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr, eps, maxexpansionexponent) );
7832 SCIP_CALL( exprsimplifySeparateLinearFromPolynomial(blkmem, expr, eps, nvars, nlinvars, linidxs, lincoefs) );
7852 SCIP_Real* varvals, /**< values for variables, can be NULL if the expression operand is not a variable */
7853 SCIP_Real* param, /**< values for parameters, can be NULL if the expression operand is not a parameter */
7862 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, argvals, varvals, param, val) );
7871 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7897 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, buf, varvals, param, val) );
7912 SCIP_INTERVAL* argvals, /**< interval values for children, can be NULL if the expression has no children */
7913 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */
7914 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7923 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, argvals, varvals, param, val) );
7932 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */
7933 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7954 SCIP_CALL( SCIPexprEvalInt(expr->children[i], infinity, varvals, param, &buf[i]) ); /*lint !e644*/
7959 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, buf, varvals, param, val) );
7988 SCIP_CALL( exprdata->eval(exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) );
8000 SCIP_INTERVAL* hessian /**< buffer to store values of full Hessian, or NULL if not requested */
8020 SCIP_CALL( exprdata->inteval(infinity, exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) );
8033 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
8048 SCIP_CALL( SCIPexprCheckCurvature(expr->children[i], infinity, varbounds, param, &childcurv[i], &childbounds[i]) ); /*lint !e644*/
8057 SCIP_CALL( exprOpTable[expr->op].curv(infinity, expr->data, expr->nchildren, childbounds, childcurv, curv) );
8058 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, childbounds, varbounds, param, bounds) );
8068 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
8095 retcode = doCheckCurvature(expr, infinity, varbounds, childbounds, param, curv, childcurv, bounds);
8108 /** under-/overestimates a user expression w.r.t. to given values and bounds for children expressions */
8115 SCIP_Real* coeffs, /**< buffer to store the linear coefficients for each child expression that gives a valid under-/overestimator */
8116 SCIP_Real* constant, /**< buffer to store the constant value of the linear under-/overestimator */
8131 SCIP_CALL( exprdata->estimate(infinity, exprdata->userdata, expr->nchildren, argvals, argbounds, overestimate, coeffs, constant, success ) );
8240 /* @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) );
11971 userdata, exprdata->evalcapability, exprdata->eval, exprdata->inteval, exprdata->curv, exprdata->prop, exprdata->estimate, exprdata->copydata, exprdata->freedata, exprdata->print) );
11991 * @note The function does not clear the array first, but only increases already existing counts.
11996 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */
12014 /** checks whether a node can be put into a component when checking block separability of an expression
12016 * If a variable used by node is already in another component, components are merged and component number is updated.
12040 exprgraphNodeCheckSeparabilityComponent(node->children[i], compnr, nchildcomps, childcomps, nvars, varcomps);
12061 /* variable is already in another component, so have to merge component compnr into that component
12094 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->nodessize, &exprgraph->nnodes, &exprgraph->nodes, &exprgraph->depth, mindepth);
12098 BMSclearMemoryArray(&exprgraph->nodessize[olddepth], exprgraph->depth - olddepth); /*lint !e866*/
12099 BMSclearMemoryArray(&exprgraph->nnodes[olddepth], exprgraph->depth - olddepth); /*lint !e866*/
12105 /** remove a variable from the variables arrays, assuming that its node will be removed or converted next */
12139 SCIP_CALL( exprgraph->exprgraphvarchgidx(exprgraph, exprgraph->userdata, exprgraph->vars[exprgraph->nvars-1], exprgraph->varnodes[exprgraph->nvars-1], exprgraph->nvars-1, varidx) );
12179 SCIPdebugMessage("move node %p (%d,%d) to depth %d\n", (void*)node, node->depth, node->pos, newdepth);
12206 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[newdepth], &exprgraph->nodessize[newdepth], exprgraph->nnodes[newdepth]+1); /*lint !e866*/
12212 /* 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) */
12219 exprgraph->nodes[olddepth][oldpos] = exprgraph->nodes[olddepth][exprgraph->nnodes[olddepth]-1];
12222 /* 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) */
12235 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
12238 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], node) < 0);
12242 /* adding a variable by moving it from a higher depth seems awkward, how did the variable get there in the first place? */
12247 /* nodes at depth 0 always have curvature linear, even before any curvature check was running */
12254 /** given a list of children, tries to find a common parent that represents a given operator with the same given data */
12262 SCIP_EXPR** exprchildren, /**< children of expression to consider when modifying (reordering) operator data, or NULL */
12263 SCIP_EXPRGRAPHNODE** parent /**< buffer to store parent node if any is found, or NULL if none found */
12294 (op != SCIP_EXPR_REALPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/
12295 (op != SCIP_EXPR_SIGNPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/
12296 (op != SCIP_EXPR_LINEAR || ((SCIP_Real*)opdata.data)[nchildren] == ((SCIP_Real*)children[0]->parents[p]->data.data)[nchildren]) && /*lint !e777*/
12297 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->nquadelems == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->nquadelems) &&
12298 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->constant == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->constant) && /*lint !e777*/
12299 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->nmonomials == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->nmonomials) &&
12300 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->constant == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->constant) /*lint !e777*/
12306 /* for all remaining children, remove parent candidates, that are not in their list of parents */
12312 /* if parentcands[p] is a parent of childnodes[i], then move last parent candidate to position p,
12325 SCIPdebugMessage("check %d parent candidates for expr with operator %d and %d children\n", nparentcands, op, nchildren);
12333 /* at this point, all parents in parentcands have the nodes in children as children and are of the same operator type
12334 * check if there is also one which corresponds to same expression and store that one in *parent
12362 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12363 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12375 * However, if there are duplicates in children, then it can happen that not every child of parentcands[p] is also one of the children.
12376 * So only if children equals parentcands[p]->children in some permutation, the expressions are the same.
12378 if( (parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1]) ||
12387 /* as in the case for two nodes, we need to check whether parentcands[p]->children and children are equal up to permutation */
12414 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12415 assert(parentcands[p]->nchildren == 2); /* that was the second criterium for adding a node to parentcands */
12416 /* order of operands matters, so check if childnodes have same order as children of parent candidate (and are the same nodes too) */
12417 if( parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1] )
12431 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */
12432 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */
12433 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */
12434 assert(parentcands[0]->data.intval == opdata.intval); /* that was another criterium for adding a node to parentcands */
12445 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */
12446 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */
12447 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */
12448 assert(parentcands[0]->data.dbl == opdata.dbl); /* that was another criterium for adding a node to parentcands */ /*lint !e777*/
12463 /* sort childnodes, take care that children in expression are sorted the same way if given (so we don't mess up assignment of coefficients) */
12465 SCIPsortPtrPtrReal((void**)children, (void**)exprchildren, exprcoef, exprgraphnodecomp, nchildren);
12470 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12471 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12474 assert(exprcoef[nchildren] == candcoef[nchildren]); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12510 /* sort children in expr and parentcands and update indices in quadelems accordingly, then sort quadelems again and compare */
12520 SCIPsortPtrPtrRealInt((void**)children, (void**)exprchildren, exprlincoef, invperm, exprgraphnodecomp, nchildren);
12525 SCIPsortPtrPtrInt((void**)children, (void**)exprchildren, invperm, exprgraphnodecomp, nchildren);
12551 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12552 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12556 assert(canddata->nquadelems == exprdata->nquadelems); /* that was a criterium for adding a node to parentcands */
12557 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12564 SCIPsortPtrRealInt((void**)parentcands[p]->children, candlincoef, invperm, exprgraphnodecomp, parentcands[p]->nchildren);
12588 /* check if children and linear coefficients in parent candidate and expression are the same */
12593 if( (exprlincoef == NULL ? 0.0 : exprlincoef[i]) != (candlincoef == NULL ? 0.0 : candlincoef[i]) ) /*lint !e777*/
12621 /* @todo in one GlobalLib instance, two polynoms differ only in the sign of all coefficients, it would be nice to recognize this somehow */
12631 /* sort children in expr and parentcands and update child indices in polynomialdata, then sort monomials again and compare */
12640 SCIPsortPtrPtrInt((void**)children, (void**)exprchildren, invperm, exprgraphnodecomp, nchildren);
12654 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12655 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12658 assert(canddata->nmonomials == exprdata->nmonomials); /* that was a criterium for adding a node to parentcands */
12659 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12729 SCIP_EXPRGRAPHNODE** exprnode, /**< buffer to store expression graph node corresponding to root of this expression */
12730 SCIP_Bool* exprnodeisnew /**< buffer to indicate whether the node in *exprnode has been newly created for this expression (otherwise, expression was already in graph) */
12778 /* find node corresponding to constant corresponding to parameter and add if not existing yet */
12802 SCIP_CALL( exprgraphAddExpr(exprgraph, expr->children[i], vars, params, &childnodes[i], &childisnew) ); /*lint !e644*/
12807 /* if all children were known already, check if there is also already a node for the expression that we aim to add */
12810 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, expr->nchildren, childnodes, expr->op, expr->data, expr->children, exprnode) );
12818 /* SCIPdebugMessage("reused node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos);
12833 SCIP_CALL( exprOpTable[expr->op].copydata(exprgraph->blkmem, expr->nchildren, expr->data, &opdata) );
12846 /* SCIPdebugMessage("created new node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos);
12858 SCIP_Bool* clearreverseprop, /**< flag to set if we had reset bound tightenings from reverse propagation */
12859 SCIP_Bool* boundchanged /**< buffer to store whether a variables bound has changes, compared to those stored in nodes */
12884 /* hmm, may happen due to numerics, let's be conservative and relax bounds to something that seems reasonable */
12899 SCIPdebugMessage("registered relaxed bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
12903 /* if a childs bounds are relaxed, then a previous reverse propagation may be invalid, so we have to clear its remainings */
12913 SCIPdebugMessage("registered tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
12920 SCIPdebugMessage("registered slightly tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
13165 /** gives linear coefficients belonging to a SCIP_EXPR_QUADRATIC expression, or NULL if all coefficients are 0.0 */
13260 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */
13261 assert(node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID); /* we assume node bounds to be valid */
13281 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&childcurv, monomial->nfactors), TERMINATE );
13306 *curv = SCIPexprcurvMonomial(monomial->nfactors, monomial->exponents, NULL, childcurv, childbounds);
13472 /* we store the coefficients and the constant in a single array and make this our operand data */
13501 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) );
13526 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) );
13548 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)node->data.data, nmonomials, monomials, copymonomials) );
13563 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */
13564 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */
13565 SCIP_DECL_USEREXPRFREEDATA ((*freedata)), /**< expression data free function, or NULL if nothing to free */
13566 SCIP_DECL_USEREXPRPRINT ((*print)) /**< expression print function, or NULL for default string "user" */
13575 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */
13576 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */
13600 /** given a node of an expression graph, splitup a linear part which variables are not used somewhere else in the same expression
13604 * If it is not linear, the node may change, i.e., the remaining nonlinear part may be stored in a new node.
13636 SCIPdebugMessage("split off linear part for %s node %p (%d,%d)\n", SCIPexpropGetName((*node)->op), (void*)*node, (*node)->depth, (*node)->pos);
13665 if( (*node)->data.dbl == 1.0 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13678 if( (*node)->data.intval == 1 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13691 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13702 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13713 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 )
13725 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 )
13735 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13746 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13757 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 )
13769 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 )
13779 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13787 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13854 assert(exprgraph->nvars > 0); /* in a simplified expr graph with no variables, there can only be const nodes, but these were handled above */
13871 SCIP_CALL( exprOpTable[orignode->op].copydata(exprgraph->blkmem, orignode->nchildren, orignode->data, &data) );
13877 SCIP_CALL( SCIPexprgraphAddNode(exprgraph, *node, -1, orignode->nchildren, orignode->children) );
13892 /* we had looked at this above already and only continued if exactly one node is still a child and linvarssize is >= 1 */
13893 assert((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX);
13894 assert((*node)->children[0]->op != SCIP_EXPR_VARIDX || (*node)->children[1]->op != SCIP_EXPR_VARIDX);
13897 varchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[0] : (*node)->children[1];
13898 otherchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[1] : (*node)->children[0];
13926 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, 2, 1) ); /*lint !e506*/
14018 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14129 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14130 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &coefs, (*node)->nchildren+1, nchildren+1) );
14261 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14262 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &quaddata->lincoefs, (*node)->nchildren, nchildren) );
14295 /* get nonlinear child usage: how often each child is used in the polynomial in a nonlinear monomial */
14340 /* we are at a linear monomial in a variable that is not used somewhere else in nonlinear form */
14343 linvars[*nlinvars] = exprgraph->vars[(*node)->children[childidx]->data.intval]; /*lint !e613*/
14403 /* if node was not duplicated and not removed but changed, then invalidate value, bounds, and simplified status */
14437 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, (*srcnode)->parents[0], srcnode, targetnode) );
14476 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);
14481 SCIPdebugMessage("remove node %p (%d, %d) with op %s from expression graph\n", (void*)*node, (*node)->depth, (*node)->pos, SCIPexpropGetName((*node)->op));
14523 exprgraph->nodes[(*node)->depth][(*node)->pos] = exprgraph->nodes[(*node)->depth][exprgraph->nnodes[(*node)->depth]-1];
14544 /* @todo should be a private method and node creation should already capture a node instead of waiting that it's added to the graph */
14597 /** disables a node and recursively all children which have no enabled parents in an expression graph */
14613 /* workaround: don't disable nodes if there could be more users than the one who is disabling the node
14614 * otherwise, if there are several nonlinear constraints using the same expression graph node as root node,
14629 SCIPdebugMessage("disabled node %p (%d,%d), nuses = %d\n", (void*)node, node->depth, node->pos, node->nuses);
14722 * Sets bound status to SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT if tightening is strong enough and not cutoff.
14728 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) */
14730 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
14745 SCIPdebugMessage("ignore bound tightening for node %p (%d,%d)\n", (void*)node, node->depth, node->pos);
14779 SCIPdebugPrintf(" -> [%10g, %10g] status %d\n", node->bounds.inf, node->bounds.sup, node->boundstatus);
14789 SCIP_Real minstrength, /**< minimal required relative bound strengthening to trigger a bound recalculation in parent nodes */
14790 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
14803 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */
14848 SCIP_CALL_TERMINATE( retcode, exprOpTable[node->op].inteval(infinity, node->data, node->nchildren, childbounds, NULL, NULL, &newbounds), TERMINATE );
14850 /* if bounds of a children were relaxed or our bounds were tightened by a (now possibly invalid) reverse propagation from a parent
14851 * and now our bounds are relaxed, then we have to propagate this upwards to ensure valid bounds
14853 * if bounds were tightened (considerably), then tell this to those parents which think that they have valid bounds
14855 * finally, if there was only a little tightening, then keep this updated bounds, but don't notify parents
14858 ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED) || ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) && clearreverseprop)) )
14878 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);
14889 SCIPdebugMessage("node %p(%d,%d) has empty domain in SCIPexprgraphUpdateNodeBoundsCurvature\n", (void*)node, node->depth, node->pos);
14893 SCIP_CALL_TERMINATE( retcode, exprOpTable[node->op].curv(infinity, node->data, node->nchildren, childbounds, childcurv, &node->curv), TERMINATE );
14895 /* SCIPdebugMessage("curvature %s for %s = ", SCIPexprcurvGetName(node->curv), SCIPexpropGetName(node->op));
15112 int varssizeinit, /**< minimal initial size for variables array, or -1 to choose automatically */
15113 int depthinit, /**< minimal initial depth of expression graph, or -1 to choose automatically */
15114 SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)), /**< callback method to invoke when a variable has been added to the expression graph, or NULL if not needed */
15115 SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)), /**< callback method to invoke when a variable will be removed from the expression graph, or NULL if not needed */
15116 SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)), /**< callback method to invoke when a variable changes its index in the expression graph, or NULL if not needed */
15132 ensureBlockMemoryArraySize3((*exprgraph)->blkmem, &(*exprgraph)->varnodes, &(*exprgraph)->vars, &(*exprgraph)->varbounds, &(*exprgraph)->varssize, varssizeinit);
15133 SCIP_CALL( SCIPhashmapCreate(&(*exprgraph)->varidxs, (*exprgraph)->blkmem, (*exprgraph)->varssize) );
15167 BMSfreeBlockMemoryArrayNull(blkmem, &(*exprgraph)->nodes[d], (*exprgraph)->nodessize[d]); /*lint !e866*/
15200 int mindepth, /**< minimal depth in expression graph where to add node, e.g., 0 or smaller to choose automatically */
15231 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[depth], &exprgraph->nodessize[depth], exprgraph->nnodes[depth]+1); /*lint !e866*/
15250 SCIP_ALLOC( BMSduplicateBlockMemoryArray(exprgraph->blkmem, &node->children, children, nchildren) );
15262 /* set bounds to entire, set status to "should recompute", and note that we have to update something */
15268 /* if not a variable, set value of node according to values of children (if all have valid values) */
15285 SCIP_EXPRGRAPHNODE** varnodes /**< array to store nodes corresponding to variables, or NULL if not of interest */
15296 /* 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 */
15299 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + nvars);
15300 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[0], &exprgraph->nodessize[0], exprgraph->nnodes[0] + nvars);
15328 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1);
15332 SCIP_CALL( SCIPhashmapInsertInt(exprgraph->varidxs, vars[i], exprgraph->nvars) ); /*lint !e613*/
15338 SCIPdebugMessage("added node %p (%d, %d) for new variable %d\n", (void*)node, node->depth, node->pos, node->data.intval);
15343 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[i], node) ); /*lint !e613*/
15357 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store pointer to expression graph node corresponding to constant */
15385 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
15388 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], *constnode) < 0);
15390 SCIPdebugMessage("added node %p (%d, %d) for new constant %g\n", (void*)constnode, (*constnode)->depth, (*constnode)->pos, (*constnode)->data.dbl);
15406 SCIP_EXPRGRAPHNODE** rootnode, /**< buffer to store expression graph node corresponding to root of expression tree */
15407 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) */
15426 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[0]->root, exprtrees[0]->vars, exprtrees[0]->params, rootnode, rootnodeisnew) );
15444 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[i]->root, exprtrees[i]->vars, exprtrees[i]->params, &rootnodes[i], &rootnodeisnew_) ); /*lint !e644*/
15475 /* all exprtrees were in the graph already, check if we also already have a node for the sum of rootnodes */
15476 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, op, data, NULL, rootnode) );
15507 /* all exprtrees were in the graph already, check if we also already have a node for the linear combination of rootnodes */
15508 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, SCIP_EXPR_LINEAR, data, NULL, rootnode) );
15533 rootnodeisnew ? "new" : "old", (void*)*rootnode, (*rootnode)->depth, (*rootnode)->pos, nexprtrees);
15589 SCIPdebugMessage("try to replace varnode %p (%d uses, %d parents) by %p\n", (void*)varnode, varnode->nuses, varnode->nparents, (void*)node);
15609 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varnode->children, 1) ); /*lint !e506*/
15616 varnode->boundstatus = (node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID) ? SCIP_EXPRBOUNDSTATUS_VALID : SCIP_EXPRBOUNDSTATUS_CHILDRELAXED;
15635 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
15638 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], varnode) < 0);
15650 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1);
15654 SCIP_CALL( SCIPhashmapInsertInt(exprgraph->varidxs, vars[0], exprgraph->nvars) ); /*lint !e613*/
15660 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[0], varnode) ); /*lint !e613*/
15717 SCIP_EXPRGRAPHNODE** varnode /**< buffer to store node corresponding to variable, if found, or NULL if not found */
15746 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store node corresponding to constant, if found, or NULL if not found */
15807 SCIPmessageFPrintInfo(messagehdlr, file, "node [fontcolor=white, style=filled, rankdir=LR]\n");
15864 SCIP_Bool clearreverseprop, /**< whether to reset bound tightenings from reverse propagation */
15865 SCIP_Bool* domainerror /**< buffer to store whether a node with empty bounds has been found, propagation is interrupted in this case */
15881 /* if variable bounds have not changed and we do not have to clear a previous backward propagation, we can just return */
15884 SCIPdebugMessage("no bounds changed and clearreverseprop is FALSE -> skip propagation of variable bounds\n");
15897 SCIPdebugMessage("bounds of node %p(%d,%d) empty, stop bounds propagation\n", (void*)node, node->depth, node->pos);
15913 * NOTE: it is assumed that SCIPexprgraphPropagateVarBounds was called before if variable bounds were relaxed.
15918 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */
15919 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
15943 /** updates curvature information in expression graph nodes w.r.t. currently stored variable bounds
15950 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
15978 SCIPerrorMessage("SCIPexprgraphCheckCurvature gets domain error while propagating variables bounds, ignoring...\n");
15988 * 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)).
15994 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
15996 SCIP_Bool* domainerror /**< buffer to indicate whether a domain error has been encountered, i.e., some expressions turned into NaN */
16030 exprgraph->varbounds[i].inf < -100.0 ? MIN(-100.0, exprgraph->varbounds[i].sup) : exprgraph->varbounds[i].inf,
16031 exprgraph->varbounds[i].sup > 100.0 ? MAX( 100.0, exprgraph->varbounds[i].inf) : exprgraph->varbounds[i].sup); /*lint !e644*/
16039 /* 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 */
16069 * for each node, convert to polynomials and merge in child nodes that are not in use otherwise, if possible
16088 /* we should be careful about declaring numbers close to zero as zero, so take eps^2 as tolerance */
16089 SCIP_CALL( exprgraphNodeSimplify(exprgraph, node, messagehdlr, eps*eps, maxexpansionexponent, &havechangenode) );
16120 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be simplified */
16140 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */
16150 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */
16179 SCIP_CALL( exprUnconvertPolynomial(exprgraph->blkmem, &node->op, &node->data, node->nchildren, (void**)node->children) );
16189 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, node->parents[j], &node, node->children[0]) );
16194 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be unconverted */
16226 /* nodes that are in use should not have been removed by simplifier, check if they still have the same value in our testpoint */
16238 assert(!SCIPisFinite(testval_before) || EPSZ(SCIPrelDiff(testval_before, testval_after), 10*eps)); /*lint !e777*/
16256 SCIP_EXPRGRAPHNODE* rootnode, /**< expression graph node that should represent root of expression tree */
16271 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
16303 /** creates a sum of expression trees with pairwise disjoint variables from a given node in an expression graph
16310 int exprtreessize, /**< length of exprtrees and exprtreecoefs arrays, need to be at least one */
16341 /* easy cases: if we have space for only one tree or there is only one child or only one variable in the graph,
16348 (node->op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1) &&
16349 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1)) )
16368 exprgraphNodeCheckSeparabilityComponent(node->children[i], &compnr, i-1, childcomp, exprgraph->nvars, varcomp); /*lint !e644*/
16391 /* reassign all children in component childcomp[data->quadelems[i].idx2] to component childcomp[data->quadelems[i].idx1] */
16410 if( childcomp[data->monomials[i]->childidxs[j]] != childcomp[data->monomials[i]->childidxs[0]] )
16412 /* reassign all children in component childcomp[data->monomials[i]->childidxs[j]] to component childcomp[data->monomials[i]->childidxs[0]] */
16417 assert(childcomp[data->monomials[i]->childidxs[j]] == childcomp[data->monomials[i]->childidxs[0]]);
16448 /* it turned out that expression is not block separable, so fallback to SCIPexprgraphGetTree */
16460 /* if we have not enough space for all expressions, merge components with number > exprtreessize into component exprtreessize */
16471 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varidx, exprgraph->nvars) ); /* mapping of expression graph variable indices to expression tree variable indices */
16472 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmap, node->nchildren) ); /* mapping of child indices from node to expressions belonging to a single component */
16473 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmapinv, node->nchildren) ); /* mapping of child indices from expressions belonging to a single component to node */
16491 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[j], &exprs[nexprs], &nexprvars, varidx) ); /*lint !e644*/
16505 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16516 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16517 /* if component i consists of first child, then it has coefficient 1.0, otherwise it has coefficient -1 */
16529 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16537 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16555 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16564 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_CONST, nodecoefs[node->nchildren]/nodecoefs[childmapinv[0]]) );
16566 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16573 if( nexprs == 2 && nodecoefs[childmapinv[0]] == nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/
16579 else if( nexprs == 2 && nodecoefs[childmapinv[0]] == -nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/
16582 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_MINUS, exprs[0], exprs[1]) );
16600 /* if all coefficients are equal and no constant, create SUM expression, otherwise LINEAR expression */
16608 SCIP_CALL( SCIPexprCreateLinear(exprgraph->blkmem, &sumexpr, nexprs, exprs, coefs, i == 0 ? nodecoefs[node->nchildren] : 0.0) );
16615 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16650 quadelems[nquadelems].idx1 = MIN(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]); /*lint !e644*/
16651 quadelems[nquadelems].idx2 = MAX(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]);
16657 SCIP_CALL( SCIPexprCreateQuadratic(exprgraph->blkmem, &quadexpr, nexprs, exprs, i == 0 ? nodedata->constant : 0.0, lincoefs, nquadelems, quadelems) );
16658 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], quadexpr, nexprvars, 0, NULL) );
16692 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomials[nmonomials], nodedata->monomials[j]->coef, nodedata->monomials[j]->nfactors,
16702 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &polyexpr, nexprs, exprs, nmonomials, monomials, i == 0 ? constant : 0.0, FALSE) );
16703 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], polyexpr, nexprvars, 0, NULL) );
16740 /** returns how often expression graph variables are used in a subtree of the expression graph */
16744 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */
16756 /** gives the number of summands which the expression of an expression graph node consists of */
16792 /** creates a sum of expression trees, possibly sharing variables, from a given node in an expression graph */
16796 int exprtreessize, /**< length of exprtrees and exptreecoefs arrays, should be at least SCIPexprgraphGetSumTreesNSummands() */
16820 (node->op != SCIP_EXPR_QUADRATIC || (((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->lincoefs == NULL && ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1)) &&
16821 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1) )
16895 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodecoefs[node->nchildren] / exprtreecoefs[0]) );
16933 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
16944 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx1], &expr, &nexprvars, varidx) );
16955 /* create expression from the subgraph at quadelems[i].idx2, may add more variables into varidx */
16956 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx2], &expr2, &nexprvars, varidx) );
16962 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) );
16967 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) );
16988 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodedata->constant / exprtreecoefs[0]) );
17017 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
17030 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) );
17041 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_INTPOWER, expr, (int)monomials[i]->exponents[0]) );
17045 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_REALPOWER, expr, monomials[i]->exponents[0]) );
17048 else if( monomials[i]->nfactors == 2 && monomials[i]->exponents[0] == 1.0 && monomials[i]->exponents[1] == 1.0 )
17053 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) );
17054 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[1]], &expr2, &nexprvars, varidx) );
17068 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childidxs, monomials[i]->nfactors) );
17071 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[f]], &exprs[f], &nexprvars, varidx) ); /*lint !e644*/
17076 * add also constant here, but need to divide by monomial coefficient, since we set the exprtreecoefs to monomial coef
17078 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomial, 1.0, monomials[i]->nfactors, childidxs, monomials[i]->exponents) );
17079 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &expr, monomials[i]->nfactors, exprs, 1, &monomial, constant / monomials[i]->coef, FALSE) );
17087 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) );
17092 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) );
17107 /* add constant to first summand, if still nonzero; need to divide by coefficient of the this exprtree */
17113 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:2154
#define SCIP_EXPRBOUNDSTATUS_CHILDRELAXED
Definition: type_expr.h:213
SCIP_Real SCIPexprgraphGetNodeVal(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13355
SCIP_RETCODE SCIPexprgraphPropagateVarBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Bool clearreverseprop, SCIP_Bool *domainerror)
Definition: expr.c:15861
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:15542
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:2567
#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:14997
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:8147
static SCIP_RETCODE exprsimplifyConvertToPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4267
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:15197
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2486
void SCIPintervalSign(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2777
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:4291
SCIP_RETCODE SCIPexprgraphGetSumTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs)
Definition: expr.c:16793
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:15281
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:5922
SCIP_RETCODE SCIPexprgraphUpdateNodeBoundsCurvature(SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool clearreverseprop)
Definition: expr.c:14786
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:8028
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:12991
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:8227
static SCIP_RETCODE exprgraphEnsureDepth(SCIP_EXPRGRAPH *exprgraph, int mindepth)
Definition: expr.c:12080
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:2547
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:5066
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:6691
SCIP_RETCODE SCIPexprgraphAddConst(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode)
Definition: expr.c:15354
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:15041
SCIP_RETCODE SCIPexprCreateMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL **monomial, SCIP_Real coef, int nfactors, int *childidxs, SCIP_Real *exponents)
Definition: expr.c:7037
void SCIPexprgraphCaptureNode(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12969
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:13484
SCIP_Real SCIPexprGetRealPowerExponent(SCIP_EXPR *expr)
Definition: expr.c:5758
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3131
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:7797
SCIP_RETCODE SCIPexprPolynomialPower(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int exponent)
Definition: expr.c:6787
void SCIPexprChgMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real newcoef)
Definition: expr.c:6853
SCIP_Real SCIPexprGetPolynomialConstant(SCIP_EXPR *expr)
Definition: expr.c:5890
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:15915
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:7582
void SCIPexprMonomialPower(SCIP_EXPRDATA_MONOMIAL *monomial, int exponent)
Definition: expr.c:6928
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetVarNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14987
Definition: type_expr.h:62
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9967
Definition: type_expr.h:73
static void exprgraphNodeCheckSeparabilityComponent(SCIP_EXPRGRAPHNODE *node, int *compnr, int nchildcomps, int *childcomps, int nvars, int *varcomps)
Definition: expr.c:12019
static SCIP_RETCODE exprgraphNodeRemovePolynomialDuplicateChildren(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:11350
SCIP_Real SCIPexprgraphGetNodeSignPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13120
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:13011
void SCIPexprGetVarsUsage(SCIP_EXPR *expr, int *varsusage)
Definition: expr.c:7559
void SCIPintervalMin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:2551
SCIP_INTERVAL SCIPexprgraphGetNodeBounds(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13345
SCIP_RETCODE SCIPexprgraphEval(SCIP_EXPRGRAPH *exprgraph, SCIP_Real *varvals)
Definition: expr.c:15840
void SCIPexprReindexVars(SCIP_EXPR *expr, int *newindices)
Definition: expr.c:8185
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:1825
int * SCIPexprgraphGetNNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14947
SCIP_RETCODE SCIPexprEvalInt(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val)
Definition: expr.c:7929
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:7118
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:15401
SCIP_RETCODE SCIPexprMultiplyMonomialByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap)
Definition: expr.c:6893
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:1076
int SCIPexprgraphGetNodePolynomialNMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13214
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:12856
SCIP_RETCODE SCIPexprgraphMoveNodeParents(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **srcnode, SCIP_EXPRGRAPHNODE *targetnode)
Definition: expr.c:14420
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:5866
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:2235
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:5912
void SCIPintervalSin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2611
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3220
#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:13051
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:13202
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:15109
Definition: type_expr.h:47
Definition: type_expr.h:49
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3362
int SCIPexprgraphGetNodeOperatorIndex(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13061
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:4926
Definition: struct_misc.h:128
Definition: type_expr.h:53
SCIP_Real SCIPexprgraphGetNodeLinearConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13142
#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:13226
SCIP_RETCODE SCIPexprAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:6669
SCIP_Bool SCIPexprgraphHasNodeNonlinearAncestor(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14671
SCIP_EXPRCURV SCIPexprgraphGetNodeCurvature(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13365
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:6586
Definition: type_expr.h:51
SCIP_Bool SCIPexprgraphFindConstNode(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode)
Definition: expr.c:15743
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:7868
void SCIPexprgraphSetVarsBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_INTERVAL *varbounds)
Definition: expr.c:15009
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:15947
SCIP_RETCODE SCIPexprGetMaxDegree(SCIP_EXPR *expr, int *maxdegree)
Definition: expr.c:7234
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:10691
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:13554
SCIP_Real * SCIPexprGetQuadLinearCoefs(SCIP_EXPR *expr)
Definition: expr.c:5842
SCIP_EXPRGRAPHNODE *** SCIPexprgraphGetNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14957
int SCIPexprgraphGetSumTreesNSummands(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:16757
static SCIP_RETCODE exprsimplifyRemovePolynomialNullChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4345
void SCIPintervalLog(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2483
SCIP_RETCODE SCIPexprCopyDeep(BMS_BLKMEM *blkmem, SCIP_EXPR **targetexpr, SCIP_EXPR *sourceexpr)
Definition: expr.c:6143
Definition: type_expr.h:52
SCIP_Bool SCIPexprgraphHasNodeUserEstimator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13333
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:5098
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:9929
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:6807
SCIP_Bool SCIPexprAreMonomialsEqual(SCIP_EXPRDATA_MONOMIAL *monomial1, SCIP_EXPRDATA_MONOMIAL *monomial2, SCIP_Real eps)
Definition: expr.c:6822
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:13458
SCIP_RETCODE SCIPexprgraphGetSeparableTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs)
Definition: expr.c:16307
SCIP_Bool SCIPexprgraphIsNodeEnabled(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12981
SCIP_INTERVAL * SCIPexprgraphGetVarsBounds(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:15101
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:6634
SCIP_RETCODE SCIPexprCheckCurvature(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varbounds, SCIP_Real *param, SCIP_EXPRCURV *curv, SCIP_INTERVAL *bounds)
Definition: expr.c:8064
SCIP_RETCODE SCIPexprEvalUser(SCIP_EXPR *expr, SCIP_Real *argvals, SCIP_Real *val, SCIP_Real *gradient, SCIP_Real *hessian)
Definition: expr.c:7971
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:7849
void SCIPexprMultiplyPolynomialByConstant(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real factor)
Definition: expr.c:6704
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:14724
static SCIP_RETCODE exprsimplifyUnconvertPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4892
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:8109
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:7094
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:6406
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:7155
SCIP_Bool SCIPexprgraphHasNodeSibling(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14636
SCIP_RETCODE SCIPexprgraphGetNodePolynomialMonomialCurvature(SCIP_EXPRGRAPHNODE *node, int monomialidx, SCIP_Real infinity, SCIP_EXPRCURV *curv)
Definition: expr.c:13241
Definition: type_retcode.h:34
SCIP_Real SCIPexprgraphGetNodeOperatorReal(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13072
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:6248
SCIP_Real SCIPexprgraphGetNodeQuadraticConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13154
SCIP_RETCODE SCIPexprMultiplyPolynomialByPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR *factor, int *childmap)
Definition: expr.c:6741
void SCIPexprMergeMonomialFactors(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real eps)
Definition: expr.c:6958
void SCIPintervalCos(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2695
SCIP_EXPRINTCAPABILITY SCIPexprGetUserEvalCapability(SCIP_EXPR *expr)
Definition: expr.c:5964
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:5780
static SCIP_RETCODE exprgraphNodeEval(SCIP_EXPRGRAPHNODE *node, SCIP_Real *varvals)
Definition: expr.c:10082
SCIP_Bool SCIPexprgraphAreAllNodeChildrenVars(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14655
void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
Definition: intervalarith.c:3223
Definition: type_expr.h:39
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
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:15061
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:4462
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:3545
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:1429
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:3286
SCIP_EXPORT void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
void SCIPexprgraphGetSubtreeVarsUsage(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int *varsusage)
Definition: expr.c:16741
void SCIPexprgraphSetVarNodeUb(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_Real ub)
Definition: expr.c:15081
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:1357
SCIP_RETCODE SCIPexprgraphNodeSplitOffLinear(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node, int linvarssize, int *nlinvars, void **linvars, SCIP_Real *lincoefs, SCIP_Real *constant)
Definition: expr.c:13608
SCIP_RETCODE SCIPexprCreate(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPROP op,...)
Definition: expr.c:5975
void SCIPintervalScalprodScalars(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
Definition: intervalarith.c:1329
Definition: struct_expr.h:116
SCIP_Bool SCIPexprFindMonomialFactor(SCIP_EXPRDATA_MONOMIAL *monomial, int childidx, int *pos)
Definition: expr.c:7138
Definition: type_expr.h:58
void SCIPexprgraphFreeNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node)
Definition: expr.c:14546
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:14598
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:2583
SCIP_Real SCIPexprGetMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5902
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:13083
Definition: type_expr.h:63
SCIP_Real * SCIPexprgraphGetNodeQuadraticLinearCoefs(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13166
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:7994
int SCIPexprgraphGetNodeIntPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13109
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13021
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:12724
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:15714
Definition: type_expr.h:79
void SCIPexprReindexParams(SCIP_EXPR *expr, int *newindices)
Definition: expr.c:8206
SCIP_Real * SCIPexprgraphGetNodeLinearCoefs(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13131
#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:13041
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:13535
void SCIPexprFreeShallow(BMS_BLKMEM *blkmem, SCIP_EXPR **expr)
Definition: expr.c:6223
Definition: type_expr.h:86
SCIP_QUADELEM * SCIPexprGetQuadElements(SCIP_EXPR *expr)
Definition: expr.c:5817
SCIP_RETCODE SCIPexprgraphCreateNodePolynomial(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Real constant, SCIP_Bool copymonomials)
Definition: expr.c:13510
void SCIPintervalExp(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2399
public methods for message output
SCIP_USEREXPRDATA * SCIPexprgraphGetNodeUserData(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13321
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:4791
SCIP_RETCODE SCIPexprgraphCreateNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_EXPROP op,...)
Definition: expr.c:13375
SCIP_RETCODE SCIPexprEvalIntShallow(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *argvals, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val)
Definition: expr.c:7909
SCIP_RETCODE SCIPexprgraphReleaseNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node)
Definition: expr.c:14452
#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:16254
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:9913
Definition: struct_expr.h:77
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13001
SCIP_RETCODE SCIPexprAddMonomialFactors(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, int nfactors, int *childidxs, SCIP_Real *exponents)
Definition: expr.c:6864
SCIP_Real * SCIPexprGetMonomialExponents(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5932
void SCIPexprgraphPrintNode(SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: expr.c:14708
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:15990
static SCIP_RETCODE exprsimplifyRemovePolynomialUnusedChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4411
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:12160
static SCIP_RETCODE exprparseFindClosingParenthesis(const char *str, const char **endptr, int length)
Definition: expr.c:5027
SCIP_RETCODE SCIPexprAddToLinear(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nchildren, SCIP_Real *coefs, SCIP_EXPR **children, SCIP_Real constant)
Definition: expr.c:6541
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:4148
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:6718
SCIP_Real SCIPexprgraphGetNodeRealPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13098
Definition: struct_expr.h:55
int SCIPexprgraphGetNodeQuadraticNQuadElements(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13190
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10660
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:6504
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:5804
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:12256
static void exprgraphNodeGetVarsUsage(SCIP_EXPRGRAPHNODE *node, int *varsusage)
Definition: expr.c:11994
SCIP_RETCODE SCIPexprgraphPrintDot(SCIP_EXPRGRAPH *exprgraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames)
Definition: expr.c:15791
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3378
#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:2073
int SCIPexprgraphGetNodeDepth(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13031
#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:15021
static SCIP_RETCODE exprgraphRemoveVar(SCIP_EXPRGRAPH *exprgraph, int varidx)
Definition: expr.c:12107
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:2901
void SCIPexprgraphEnableNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14571
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3296
SCIP_QUADELEM * SCIPexprgraphGetNodeQuadraticQuadElements(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13178