expr.c
Go to the documentation of this file.
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
64 #ifdef SCIP_DISABLED_CODE /* this macro is currently not used, which offends lint, so disable it */
112 /* calculate the size with this loop, such that the resulting numbers are always the same (-> block memory) */
147 /** checks if a given new lower bound is tighter (w.r.t. given bound strengthening epsilon) than the old one (copied from scip/set.c) */
167 /** checks if a given new upper bound is tighter (w.r.t. given bound strengthening epsilon) than the old one (copied from scip/set.c) */
252 /** gives curvature for base^exponent for given bounds and curvature of base-function and constant exponent */
281 /* if basebounds contains 0.0, consider negative and positive interval separately, if possible */
287 /* something like x^(-2) may look convex on each side of zero, but is not convex on the whole interval due to the singularity at 0.0 */
294 return (SCIP_EXPRCURV) (SCIPexprcurvPower(leftbounds, basecurv, exponent) & SCIPexprcurvPower(rightbounds, basecurv, exponent));
298 /* (base^exponent)'' = exponent * ( (exponent-1) base^(exponent-2) (base')^2 + base^(exponent-1) base'' )
303 * - for base > 0.0 and 0.0 < exponent < 1.0, we can't say (first sommand negative, second summand positive)
309 * - for base > 0.0 and exponent > 1.0, we can't say (first summand positive, second summand negative)
358 * See Maranas and Floudas, Finding All Solutions of Nonlinearly Constrained Systems of Equations, JOGO 7, 1995
450 * - all except one exponent j* are negative and exp_j* >= 1 - sum_{j!=j*}exp_j, but the latter is equivalent to sum_j exp_j >= 1
515 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*quadraticdata)->lincoefs, lincoefs, nchildren) );
520 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*quadraticdata)->quadelems, quadelems, nquadelems) );
617 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &monomialdata->childidxs, monomialdata->factorssize, newsize) );
618 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &monomialdata->exponents, monomialdata->factorssize, newsize) );
634 SCIP_Bool copymonomials /**< whether to copy monomials, or copy only given pointers, in which case polynomialdata assumes ownership of monomial structure */
661 monomials[i]->coef, monomials[i]->nfactors, monomials[i]->childidxs, monomials[i]->exponents) ); /*lint !e613*/
666 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, monomials, nmonomials) );
692 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, (*polynomialdata)->monomialssize) );
697 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &(*polynomialdata)->monomials[i], sourcepolynomialdata->monomials[i]->coef,
698 sourcepolynomialdata->monomials[i]->nfactors, sourcepolynomialdata->monomials[i]->childidxs, sourcepolynomialdata->monomials[i]->exponents) );
732 BMSfreeBlockMemoryArray(blkmem, &(*polynomialdata)->monomials, (*polynomialdata)->monomialssize);
750 ensureBlockMemoryArraySize(blkmem, &polynomialdata->monomials, &polynomialdata->monomialssize, minsize);
775 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials + nmonomials) );
783 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials + i],
784 monomials[i]->coef, monomials[i]->nfactors, monomials[i]->childidxs, monomials[i]->exponents) ); /*lint !e613*/
789 BMScopyMemoryArray(&polynomialdata->monomials[polynomialdata->nmonomials], monomials, nmonomials); /*lint !e866*/
823 SCIPsortPtr((void**)polynomialdata->monomials, monomialdataCompare, polynomialdata->nmonomials);
849 /* merge monomials by adding their coefficients, eliminate monomials with no factors or zero coefficient*/
886 if( monomialdataCompare((void*)polynomialdata->monomials[i], (void*)polynomialdata->monomials[i+offset+1]) != 0 )
947 SCIPexprChgMonomialCoef(polynomialdata->monomials[i], polynomialdata->monomials[i]->coef * factor);
977 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i], factor, childmap) );
983 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials+1) );
984 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials], polynomialdata->constant, 0, NULL, NULL) );
985 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[polynomialdata->nmonomials], factor, childmap) );
1023 SCIP_CALL( polynomialdataMultiplyByMonomial(blkmem, polynomialdata, factordata->monomials[0], childmap) );
1030 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials+1) );
1031 SCIP_CALL( SCIPexprCreateMonomial(blkmem, &polynomialdata->monomials[polynomialdata->nmonomials], polynomialdata->constant, 0, NULL, NULL) );
1037 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, polynomialdata->nmonomials * (factordata->nmonomials + (factordata->constant == 0.0 ? 0 : 1))) );
1045 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 */
1046 SCIP_CALL( polynomialdataAddMonomials(blkmem, polynomialdata, orignmonomials, polynomialdata->monomials, TRUE) );
1052 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i1], factordata->monomials[i2], childmap) );
1067 SCIPexprChgMonomialCoef(polynomialdata->monomials[i1], polynomialdata->monomials[i1]->coef * factordata->constant);
1075 SCIP_CALL( SCIPexprMultiplyMonomialByMonomial(blkmem, polynomialdata->monomials[i1], factordata->monomials[i2], childmap) );
1195 int maxexpansionexponent,/**< maximal exponent for which polynomials (with > 1 summands) are expanded */
1222 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && factorpolynomial->constant < 0.0 ) /*lint !e835*/
1224 /* if polynomial is a negative constant and our exponent is not integer, then cannot do expansion */
1225 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n", factorpolynomial->constant, monomial->exponents[factorpos]);
1258 /* if coefficient of monomial is negative and our exponent is not integer, then do not do expansion
1259 * @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
1266 /* @todo if there is an even number of factors in factormonomial that are negative, then they always multiply to something positive
1269 * MINLPLib instances tls2,4,6 are examples where we are loosing here (do not recognize convexity)
1276 SCIP_CALL( monomialdataEnsureFactorsSize(blkmem, monomial, monomial->nfactors + factormonomial->nfactors) );
1281 /* can do this because monomial->exponents[factorpos] is assumed to be integer or factormonomial has positive coefficient and only one factor
1282 * thus, if factormonomial->exponents[i] is fractional, then we can assume that it's argument is positive
1303 /* if exponent is negative or fractional and the polynomial is not just a monomial, then we cannot do expansion */
1304 if( !EPSISINT(monomial->exponents[factorpos], 0.0) || monomial->exponents[factorpos] < 0.0 ) /*lint !e835*/
1318 * that is, assume monomial is f1^a1 f2^a2 ... and we want to expand f1 = (g11^beta11 g12^beta12... + g21^beta21 g22^beta22 ... + ...)
1319 * then we do this only if all ai and all beta are > 0.0 and a1 max(beta11+beta12+..., beta21+beta22+..., ...) + a2 + ... < maxexpansionexponent
1322 if( maxexpansionexponent < INT_MAX && (monomial->nfactors > 1 || monomial->exponents[factorpos] != 1.0) )
1349 SCIPdebugMessage("skip expansion because %d'th factor in %d'th monomial of factorpolynomial is negative\n", i, j);
1358 SCIPdebugMessage("skip expansion because degree of %d'th monomial would yield degree %g > max = %d in expansion\n",
1371 SCIP_CALL( polynomialdataPower(blkmem, factorpolynomialcopy, (int)EPSFLOOR(monomial->exponents[factorpos], 0.0)) ); /*lint !e835*/
1388 polynomialdata->monomials[monomialpos] = polynomialdata->monomials[polynomialdata->nmonomials-1];
1393 SCIP_CALL( polynomialdataAddMonomials(blkmem, polynomialdata, factorpolynomialcopy->nmonomials, factorpolynomialcopy->monomials, FALSE) );
1407 /** a default implementation of expression interval evaluation that always gives a correct result */
1416 /** a default implementation of expression curvature check that always gives a correct result */
1651 #if defined(__GNUC__) && __GNUC__ * 100 + __GNUC_MINOR__ * 10 >= 490 && !defined(__INTEL_COMPILER)
1694 * if both nominator and denominator are not constant, then quotient may not be convex nor concave
1839 #if defined(__GNUC__) && __GNUC__ * 100 + __GNUC_MINOR__ * 10 >= 490 && !defined(__INTEL_COMPILER)
2125 /* erf and erfi do not seem to exist on every system, and we cannot really handle them anyway, so they are currently disabled */
2432 * if only one factor is not constant, then product is curvature of this factor, multiplied by sign of product of remaining factors
2530 /* for a linear expression, we need to copy the array that holds the coefficients and constant term */
2532 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &targetdata, (SCIP_Real*)opdatasource.data, nchildren + 1) ); /*lint !e866*/
2585 *result += quadelems->coef * argvals[quadelems->idx1] * argvals[quadelems->idx2]; /*lint !e613*/
2657 SCIPdebugMessage("%g x^2 + %g y^2 + %g x y + %g x + %g y = [%g,%g] for x = [%g,%g], y = [%g,%g]\n",
2659 result->inf, result->sup, argvals[0].inf, argvals[0].sup, argvals[1].inf, argvals[1].sup); /*lint !e613*/
2671 /* for each argument, we collect it's linear index from lincoefs, it's square coefficients and all factors from bilinear terms
2680 /* there are no quadratic terms with argidx in its first argument, that should be easy to handle */
2701 SCIPintervalMulScalar(infinity, &tmp, argvals[quadelems[i].idx2], quadelems[i].coef); /*lint !e613*/
2763 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef * argbounds[quadelems[i].idx1].inf, argcurv[quadelems[i].idx2]));
2768 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef * argbounds[quadelems[i].idx2].inf, argcurv[quadelems[i].idx1]));
2773 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(quadelems[i].coef, SCIPexprcurvPower(argbounds[quadelems[i].idx1], argcurv[quadelems[i].idx1], 2.0)));
2798 sourcedata->constant, nchildren, sourcedata->lincoefs, sourcedata->nquadelems, sourcedata->quadelems) );
3045 /* we assume that some simplifier was running, so that monomials do not have constants in their factors and such that all factors are different
3049 *result = SCIPexprcurvAdd(*result, SCIPexprcurvMultiply(monomial->coef, SCIPexprcurvMonomial(monomial->nfactors, monomial->exponents, monomial->childidxs, argcurv, argbounds)));
3112 SCIP_CALL( exprdata->inteval(infinity, exprdata->userdata, nargs, argvals, result, NULL, NULL) );
3116 /* if user does not provide interval evaluation, then return a result that is always correct */
3137 /* if user does not provide curvature check, then return unknown (which is handled like indefinite) */
3163 SCIP_CALL( exprdatasource->copydata(blkmem, nchildren, exprdatasource->userdata, &exprdatatarget->userdata) );
3208 SCIP_DECL_EXPRCOPYDATA ((*copydata)); /**< expression data copy function, or NULL to only opdata union */
3209 SCIP_DECL_EXPRFREEDATA ((*freedata)); /**< expression data free function, or NULL if nothing to free */
3214 /** table containing for each operand the name, the number of children, and some evaluation functions */
3245 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY,
3246 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY,
3247 EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY, EXPROPEMPTY,
3251 { "linear", -2, exprevalLinear, exprevalIntLinear, exprcurvLinear, exprCopyDataLinear, exprFreeDataLinear },
3252 { "quadratic", -2, exprevalQuadratic, exprevalIntQuadratic, exprcurvQuadratic, exprCopyDataQuadratic, exprFreeDataQuadratic },
3253 { "polynomial", -2, exprevalPolynomial, exprevalIntPolynomial, exprcurvPolynomial, exprCopyDataPolynomial, exprFreeDataPolynomial },
3254 { "user", -2, exprevalUser, exprevalIntUser, exprcurvUser, exprCopyDataUser, exprFreeDataUser }
3316 /** tries to convert a given (operator,operatordata) pair into a polynomial operator with corresponding data
3653 SCIP_CALL( polynomialdataCreate(blkmem, &polynomialdata, 0, NULL, lineardata[nchildren], FALSE) );
3695 SCIP_CALL( polynomialdataCreate(blkmem, &polynomialdata, 0, NULL, quaddata->constant, FALSE) );
3697 SCIP_CALL( polynomialdataEnsureMonomialsSize(blkmem, polynomialdata, (quaddata->lincoefs != NULL ? nchildren : 0) + quaddata->nquadelems) );
3833 /* polynomial simplification and monomial merging should ensure that monomial i corresponds to child i and that there are not unused children */
3837 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == 1.0 && polynomialdata->monomials[1]->coef == 1.0 )
3854 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == 1.0 && polynomialdata->monomials[1]->coef == -1.0 )
3871 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 2 && polynomialdata->monomials[0]->coef == -1.0 && polynomialdata->monomials[1]->coef == 1.0 )
3921 * that monomials are ordered according to the child index, and that constant monomials have been removed
3943 if( maxdegree == 2 && (polynomialdata->nmonomials > 1 || polynomialdata->constant != 0.0 || polynomialdata->monomials[0]->coef != 1.0) )
3945 /* 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 */
3950 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &quaddata->quadelems, polynomialdata->nmonomials - nlinmonomials) );
3966 assert(polynomialdata->monomials[i]->nfactors == 1 || polynomialdata->monomials[i]->nfactors == 2);
3973 quaddata->lincoefs[polynomialdata->monomials[i]->childidxs[0]] += polynomialdata->monomials[i]->coef;
3992 quaddata->quadelems[quadelemidx].idx1 = MIN(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]);
3993 quaddata->quadelems[quadelemidx].idx2 = MAX(polynomialdata->monomials[i]->childidxs[0], polynomialdata->monomials[i]->childidxs[1]);
4008 if( polynomialdata->constant == 0.0 && polynomialdata->nmonomials == 1 && polynomialdata->monomials[0]->coef == 1.0 )
4100 if( monomial->nfactors == 2 && monomial->exponents[0] == 1.0 && monomial->exponents[1] == -1.0 )
4114 if( monomial->nfactors == 2 && monomial->exponents[0] == -1.0 && monomial->exponents[1] == 1.0 )
4139 /** adds copies of expressions to the array of children of a sum, product, linear, quadratic, or polynomial expression
4141 * For a sum or product expression, this corresponds to add additional summands and factors, resp.
4143 * For a quadratic or polynomial expression, only the children array may be enlarged, the expression itself remains the same.
4151 SCIP_Bool comparechildren, /**< whether to compare expressions with already existing children (no effect for sum and product) */
4153 int* childmap /**< array where to store mapping of indices from exprs to children array in expr, or NULL if not of interest */
4160 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);
4171 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) );
4174 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren + i], exprs[i]) ); /*lint !e613*/
4192 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nexprs) );
4200 if( expr->children[j] != NULL && SCIPexprAreEqual(expr->children[j], exprs[i], eps) ) /*lint !e613*/
4209 SCIP_CALL( SCIPexprCopyDeep(blkmem, &expr->children[expr->nchildren], exprs[i]) ); /*lint !e613*/
4228 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, orignchildren + nexprs, expr->nchildren) );
4236 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, orignchildren + 1, expr->nchildren + 1) );
4248 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data->lincoefs, orignchildren, expr->nchildren) );
4249 BMSclearMemoryArray(&data->lincoefs[orignchildren], expr->nchildren - orignchildren); /*lint !e866*/
4395 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, lastnonnull+1) );
4457 * exprsimplifyConvertToPolynomials should have been called before to eliminate simple polynomial operands.
4465 int maxexpansionexponent/**< maximal exponent for which we still expand non-monomial polynomials */
4474 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr->children[i], eps, maxexpansionexponent) );
4504 if( (expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) ||
4510 /* since child0 has no children and it's polynomial was flattened, it should have no monomials */
4511 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0);
4535 if( ((expr->children[0]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[0]) == 0) || expr->children[0]->op == SCIP_EXPR_CONST) &&
4536 ((expr->children[1]->op == SCIP_EXPR_POLYNOMIAL && SCIPexprGetNChildren(expr->children[1]) == 0) || expr->children[1]->op == SCIP_EXPR_CONST) )
4541 /* since children have no children and it's polynomial was flattened, it should have no monomials */
4542 assert(expr->children[0]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[0]) == 0);
4543 assert(expr->children[1]->op != SCIP_EXPR_POLYNOMIAL || SCIPexprGetNMonomials(expr->children[1]) == 0);
4596 * 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
4624 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
4639 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && SCIPexprGetOpReal(expr->children[i]) < 0.0 ) /*lint !e835*/
4642 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n",
4697 SCIP_CALL( exprsimplifyAddChildren(blkmem, expr, expr->children[i]->nchildren, expr->children[i]->children, TRUE, eps, childmap) );
4707 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
4722 SCIP_CALL( polynomialdataExpandMonomialFactor(blkmem, messagehdlr, polynomialdata, j, factorpos,
4723 (SCIP_EXPRDATA_POLYNOMIAL*)expr->children[i]->data.data, childmap, maxexpansionexponent, &success) );
4734 /* expansion may remove monomials[j], move a monomial from the end to position j, or add new monomials to the end of polynomialdata
4795 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part */
4859 if( childusage[childidx] == 1 && varsusage[SCIPexprGetOpIndex(expr->children[childidx])] == 1 )
4861 /* if the child expression is not used in another monomial (which would due to merging be not linear)
4908 SCIP_CALL( exprUnconvertPolynomial(blkmem, &expr->op, &expr->data, expr->nchildren, (void**)expr->children) );
4921 * Creates a new variable index if variable not seen before, updates varnames and vartable structures.
4931 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */
4933 const char* varnameendptr /**< if a <varname> should be parsed, set this to NULL. Then, str points to the '<'
4961 SCIPerrorMessage("Variable name %.*s is too long for buffer in exprparseReadVariable.\n", namelength, str);
4984 SCIPerrorMessage("Buffer in exprparseReadVariable is too short for varaible name %.*s.\n", namelength, str);
5020 /** if str[0] points to an opening parenthesis, this function sets endptr to point to the matching closing bracket in str
5050 SCIPerrorMessage("unable to find closing parenthesis in unbalanced expression %.*s\n", length, str);
5087 SCIPerrorMessage("unable to find separating comma in unbalanced expression %.*s\n", length, str);
5106 SCIP_HASHTABLE* vartable, /**< hash table for variable names and corresponding expression index */
5133 SCIPdebugMessage("exprParse (%i): parsing %.*s\n", recursiondepth, (int) (lastchar-str + 1), str);
5146 while( subexpptr != lastchar && !(nopenbrackets == 0 && (subexpptr[0] == '+' || subexpptr[0] == '-') && subexpptr != str) )
5157 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str, (int) ((subexpptr - 1) - str + 1), subexpptr - 1, nvars,
5162 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, subexpptr , (int) (lastchar - (subexpptr ) + 1), lastchar, nvars,
5166 * we always use add, because we leave the operator between the found expressions in the second argument
5167 * this way, we do not have to worry about ''minus brackets'' in the case of more then two summands:
5199 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, subexpptr, subexplength, subexpendptr, nvars, varnames,
5228 SCIP_CALL( exprParse(blkmem, messagehdlr, expr, str, (int)(lastchar - str) + 1, lastchar, nvars, varnames,
5246 SCIP_CALL( exprparseReadVariable(blkmem, &str, expr, nvars, varnames, varnameslength, vartable, 1.0, NULL) );
5253 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5273 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5326 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5334 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, comma, endptr - comma, endptr - 1, nvars, varnames,
5355 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5362 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) )
5390 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg1, str + 1, comma - str - 1, comma - 1, nvars, varnames,
5397 if( !isdigit((unsigned char)comma[0]) && !((comma[0] == '-' || comma[0] == '+') && isdigit((unsigned char)comma[1])) )
5421 /* check for a variable, that was not recognized earlier because somebody omitted the '<' and '>' we need for
5427 /* allow only variable names containing characters, digits, hash marks, and underscores here */
5431 SCIP_CALL( exprparseReadVariable(blkmem, &varnamestartptr, expr, nvars, varnames, varnameslength,
5453 SCIPerrorMessage("error finding first expression in \"%.*s\" took us outside of given subexpression length\n", length, strstart);
5481 if( isdigit((unsigned char)str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit((unsigned char)str[1])) )
5511 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str + 1, endptr - str - 1, endptr -1, nvars, varnames,
5559 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames,
5617 /* if there is a part of the string left to be parsed, we assume that this as a multiplication */
5627 SCIPdebugMessage("No operator found, assuming a multiplication before %.*s\n", (int) (lastchar - str + 1), str);
5630 SCIP_CALL( exprParse(blkmem, messagehdlr, &arg2, str, (int) (lastchar - str + 1), lastchar, nvars, varnames,
5797 /* the coefficients are stored in the first nchildren elements of the array stored as expression data */
6128 SCIPerrorMessage("cannot create complex expression linear, quadratic, polynomial, or user with SCIPexprCreate\n");
6158 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*targetexpr)->children, sourceexpr->nchildren) );
6168 assert((*targetexpr)->children == NULL); /* otherwise, sourceexpr->children was not NULL, which is wrong */
6176 SCIP_CALL( exprOpTable[sourceexpr->op].copydata(blkmem, sourceexpr->nchildren, sourceexpr->data, &(*targetexpr)->data) );
6241 /** creates an expression from the addition of two given expression, with coefficients, and a constant
6243 * The given expressions may be modified or freed, otherwise it will be used a child expression.
6344 if( SCIPexprGetOperator(term1) == SCIP_EXPR_LINEAR && SCIPexprGetOperator(term2) == SCIP_EXPR_LINEAR )
6350 SCIP_CALL( SCIPexprAddToLinear(blkmem, term1, SCIPexprGetNChildren(term2), SCIPexprGetLinearCoefs(term2), SCIPexprGetChildren(term2), SCIPexprGetLinearConstant(term2) + constant) );
6401 * The given expressions may be modified or freed, otherwise it will be used a child expression.
6501 /** creates a SCIP_EXPR_LINEAR expression that is (affine) linear in its children: constant + sum_i coef_i child_i */
6526 /* we store the coefficients and the constant in a single array and make this our operand data */
6569 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->nchildren + nchildren) );
6573 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, expr->nchildren + 1, expr->nchildren + nchildren + 1) );
6583 /** creates a SCIP_EXPR_QUADRATIC expression: constant + sum_i coef_i child_i + sum_i coef_i child1_i child2_i */
6610 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) );
6631 /** creates a SCIP_EXPR_POLYNOMIAL expression from an array of monomials: constant + sum_i monomial_i */
6658 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) );
6683 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, nmonomials, monomials, copymonomials) );
6729 SCIP_CALL( polynomialdataMultiplyByMonomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, factor, childmap) );
6737 * Children of factor need to be children of expr already, w.r.t. an optional mapping of child indices.
6775 SCIP_CALL( polynomialdataMultiplyByPolynomial(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, (SCIP_EXPRDATA_POLYNOMIAL*)factor->data.data, childmap) );
6796 SCIP_CALL( polynomialdataPower(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, exponent) );
6801 /** merges monomials in a polynomial expression that differ only in coefficient into a single monomial
6816 polynomialdataMergeMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)expr->data.data, eps, mergefactors);
6881 BMScopyMemoryArray(&monomial->childidxs[monomial->nfactors], childidxs, nfactors); /*lint !e866*/
6882 BMScopyMemoryArray(&monomial->exponents[monomial->nfactors], exponents, nfactors); /*lint !e866*/
6908 SCIP_CALL( SCIPexprAddMonomialFactors(blkmem, monomial, factor->nfactors, factor->childidxs, factor->exponents) );
6986 while( i+offset+1 < monomial->nfactors && monomial->childidxs[i] == monomial->childidxs[i+offset+1] )
7058 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->childidxs, childidxs, nfactors) );
7071 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*monomial)->exponents, exponents, nfactors) );
7133 * Note that if the factors have not been merged, the position of some factor corresponding to a given child is given.
7159 SCIP_EXPRINTCAPABILITY evalcapability, /**< capability of evaluation functions (partially redundant, currently) */
7161 SCIP_DECL_USEREXPRINTEVAL ((*inteval)), /**< interval evaluation function, or NULL if not implemented */
7163 SCIP_DECL_USEREXPRPROP ((*prop)), /**< interval propagation function, or NULL if not implemented */
7164 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */
7165 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */
7166 SCIP_DECL_USEREXPRFREEDATA ((*freedata)), /**< expression data free function, or NULL if nothing to free */
7167 SCIP_DECL_USEREXPRPRINT ((*print)) /**< expression print function, or NULL for default string "user" */
7177 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */
7178 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */
7338 else if( expr->data.dbl > 0.0 && (int)expr->data.dbl == expr->data.dbl ) /* natural exponent gives polynomial again */ /*lint !e777*/
7467 /* if no linear or no quadratic coefficient with current child on first position, then nothing to do */
7479 while( quadidx < quadraticdata->nquadelems && quadraticdata->quadelems[quadidx].idx1 == childidx )
7490 SCIP_CALL( SCIPexprGetMaxDegree(expr->children[quadraticdata->quadelems[quadidx].idx2], &child2) );
7530 /* if the exponent of the factor is not a natural number and the child is not constant (degree 0),
7532 if( child1 != 0 && (monomialdata->exponents[j] < 0.0 || (int)monomialdata->exponents[j] != monomialdata->exponents[j]) )
7611 return SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps) && SCIPexprAreEqual(expr1->children[1], expr2->children[1], eps);
7629 return EPSEQ(expr1->data.dbl, expr2->data.dbl, eps) && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps);
7632 return expr1->data.intval == expr2->data.intval && SCIPexprAreEqual(expr1->children[0], expr2->children[0], eps);
7793 * If linear variables are split off, expression interpreter data, if stored in the tree, is freed.
7800 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
7802 int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */
7803 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */
7821 SCIP_CALL( exprsimplifyFlattenPolynomials(blkmem, messagehdlr, expr, eps, maxexpansionexponent) );
7830 SCIP_CALL( exprsimplifySeparateLinearFromPolynomial(blkmem, expr, eps, nvars, nlinvars, linidxs, lincoefs) );
7850 SCIP_Real* varvals, /**< values for variables, can be NULL if the expression operand is not a variable */
7851 SCIP_Real* param, /**< values for parameters, can be NULL if the expression operand is not a parameter */
7860 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, argvals, varvals, param, val) );
7869 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7895 SCIP_CALL( exprOpTable[expr->op].eval(expr->data, expr->nchildren, buf, varvals, param, val) );
7910 SCIP_INTERVAL* argvals, /**< interval values for children, can be NULL if the expression has no children */
7911 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */
7912 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7921 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, argvals, varvals, param, val) );
7930 SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */
7931 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
7952 SCIP_CALL( SCIPexprEvalInt(expr->children[i], infinity, varvals, param, &buf[i]) ); /*lint !e644*/
7957 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, buf, varvals, param, val) );
7986 SCIP_CALL( exprdata->eval(exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) );
7998 SCIP_INTERVAL* hessian /**< buffer to store values of full Hessian, or NULL if not requested */
8018 SCIP_CALL( exprdata->inteval(infinity, exprdata->userdata, expr->nchildren, argvals, val, gradient, hessian) );
8031 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
8046 SCIP_CALL( SCIPexprCheckCurvature(expr->children[i], infinity, varbounds, param, &childcurv[i], &childbounds[i]) ); /*lint !e644*/
8055 SCIP_CALL( exprOpTable[expr->op].curv(infinity, expr->data, expr->nchildren, childbounds, childcurv, curv) );
8056 SCIP_CALL( exprOpTable[expr->op].inteval(infinity, expr->data, expr->nchildren, childbounds, varbounds, param, bounds) );
8066 SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
8093 retcode = doCheckCurvature(expr, infinity, varbounds, childbounds, param, curv, childcurv, bounds);
8106 /** under-/overestimates a user expression w.r.t. to given values and bounds for children expressions */
8113 SCIP_Real* coeffs, /**< buffer to store the linear coefficients for each child expression that gives a valid under-/overestimator */
8114 SCIP_Real* constant, /**< buffer to store the constant value of the linear under-/overestimator */
8129 SCIP_CALL( exprdata->estimate(infinity, exprdata->userdata, expr->nchildren, argvals, argbounds, overestimate, coeffs, constant, success ) );
8238 /* @Note: 'expr->data.intval' is either between 0 and number of variables-1, if it uses the varnames array, or
8440 SCIPexprPrint(expr->children[quadraticdata->quadelems[i].idx1], messagehdlr, file, varnames, paramnames, paramvals);
8448 SCIPexprPrint(expr->children[quadraticdata->quadelems[i].idx2], messagehdlr, file, varnames, paramnames, paramvals);
8482 SCIPexprPrint(expr->children[monomialdata->childidxs[j]], messagehdlr, file, varnames, paramnames, paramvals);
8562 * for each variable, we store its name, prefixed with the assigned index in the first sizeof(int) bytes
8564 SCIP_CALL( SCIPhashtableCreate(&vartable, blkmem, 10, exprparseVarTableGetKey, SCIPhashKeyEqString,
8567 retcode = exprParse(blkmem, messagehdlr, expr, str, (int) (lastchar - str + 1), lastchar, nvars, &varnames,
8693 /** indicates whether there are parameterized constants (SCIP_EXPR_PARAM) in expression tree */
8777 SCIP_Real* params /**< values for parameters, or NULL (if NULL but nparams > 0, then params is initialized with zeros) */
8834 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*targettree)->vars, sourcetree->vars, sourcetree->nvars) );
8842 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*targettree)->params, sourcetree->params, sourcetree->nparams) );
8924 * If linear variables are split off, expression interpreter data, if stored in the tree, is freed.
8930 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
8931 int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */
8932 int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */
8957 /* we should be careful about declaring numbers close to zero as zero, so take eps^2 as tolerance */
8958 SCIP_CALL( SCIPexprSimplify(tree->blkmem, messagehdlr, tree->root, eps*eps, maxexpansionexponent, tree->nvars, nlinvars, linidxs, lincoefs) );
8965 assert(testval_before != testval_before || testval_before == testval_after || EPSZ(SCIPrelDiff(testval_before, testval_after), eps)); /*lint !e777*/
8978 * 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.
9009 /** tries to determine the curvature type of an expression tree w.r.t. given variable domains */
9032 SCIP_CALL( SCIPexprCheckCurvature(tree->root, infinity, varbounds, tree->params, curv, &exprbounds) );
9087 * 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
9089 #define QUADELEMS_ISBETTER(a, b) ( ((a).idx1 < (b).idx1) || ((a).idx1 == (b).idx1 && (a).idx2 < (b).idx2) )
9099 /** quicksort an array of quadratic elements; pivot is the medial element (taken from scip/sorttpl.c) */
9148 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
9149 assert(!QUADELEMS_ISBETTER(elems[mid], pivotkey)); /* the pivot element did not change its position */
9232 * If (idx1,idx2) is found in quadelems, then returns TRUE and stores position of quadratic element in *pos.
9233 * 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.
9241 int* pos /**< buffer to store position of found quadratic element or position where it would be inserted, or NULL */
9266 if( idx1 < quadelems[middle].idx1 || (idx1 == quadelems[middle].idx1 && idx2 < quadelems[middle].idx2) ) /*lint !e613*/
9268 else if( quadelems[middle].idx1 < idx1 || (quadelems[middle].idx1 == idx1 && quadelems[middle].idx2 < idx2) ) /*lint !e613*/
9333 /* now i should point to the position after the last valid element, i.e., it is the remaining number of elements */
9366 node->parentssorted = (node->nparents <= 1) || (node->parentssorted && (exprgraphnodecomp((void*)node->parents[node->nparents-2], (void*)parent) <= 0));
9401 SCIP_EXPRGRAPHNODE** node, /**< expression graph node where to remove a parent, *node will be set to NULL */
9421 (void) SCIPsortedvecFindPtr((void**)(*node)->parents, exprgraphnodecomp, (void*)parent, (*node)->nparents, &pos);
9468 return SCIPsortedvecFindPtr((void**)node->parents, exprgraphnodecomp, (void*)parent, node->nparents, &pos);
9471 /** adds expression graph nodes to the array of children of a sum, product, linear, quadratic, or polynomial expression
9473 * For a sum or product expression, this corresponds to add additional summands and factors, resp.
9475 * For a quadratic or polynomial expression, only the children array may be enlarged, the expression itself remains the same.
9486 int* childmap /**< array where to store mapping of indices from exprs to children array in node, or NULL if not of interest */
9498 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);
9505 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, node->nchildren, node->nchildren + nexprs) );
9546 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, orignchildren + nexprs, node->nchildren) );
9554 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data, orignchildren + 1, node->nchildren + 1) );
9566 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &data->lincoefs, orignchildren, node->nchildren) );
9567 BMSclearMemoryArray(&data->lincoefs[orignchildren], node->nchildren - orignchildren); /*lint !e866*/
9600 SCIPdebugMessage("replace child %p in node %p by %p\n", (void*)*oldchild, (void*)node, (void*)newchild);
9638 assert(((SCIP_EXPRGRAPHNODE*)elem1)->data.dbl == ((SCIP_EXPRGRAPHNODE*)elem1)->data.dbl); /* assert that const value is not nan */ /*lint !e777*/
9639 assert(((SCIP_EXPRGRAPHNODE*)elem2)->data.dbl == ((SCIP_EXPRGRAPHNODE*)elem2)->data.dbl); /* assert that const value is not nan */ /*lint !e777*/
9711 while( exprgraph->constnodes[*pos] != node && *pos > 0 && exprgraph->constnodes[*pos-1]->data.dbl == node->data.dbl ) /*lint !e777*/
9714 while( exprgraph->constnodes[*pos] != node && *pos < exprgraph->nconsts-1 && exprgraph->constnodes[*pos+1]->data.dbl == node->data.dbl ) /*lint !e777*/
9752 /* set initial curvature to linear for variables, parameters, and constants and unknown otherwise */
9799 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9802 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9807 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9810 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9815 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9818 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9823 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9826 SCIPmessageFPrintInfo(messagehdlr, file, "c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9831 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9837 SCIPmessageFPrintInfo(messagehdlr, file, "c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9852 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9871 SCIPmessageFPrintInfo(messagehdlr, file, "(c0[%10g,%10g]", node->children[0]->bounds.inf, node->children[0]->bounds.sup);
9873 SCIPmessageFPrintInfo(messagehdlr, file, ",c1[%10g,%10g]", node->children[1]->bounds.inf, node->children[1]->bounds.sup);
9884 SCIPmessageFPrintInfo(messagehdlr, file, "c%d[%10g,%10g]", i, node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9896 SCIPmessageFPrintInfo(messagehdlr, file, "c%d[%10g,%10g]", i, node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9921 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9944 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[i]->bounds.inf, node->children[i]->bounds.sup);
9957 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[quadraticdata->quadelems[i].idx1]->bounds.inf, node->children[quadraticdata->quadelems[i].idx1]->bounds.sup);
9964 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[quadraticdata->quadelems[i].idx2]->bounds.inf, node->children[quadraticdata->quadelems[i].idx2]->bounds.sup);
9999 SCIPmessageFPrintInfo(messagehdlr, file, "[%10g,%10g]", node->children[monomialdata->childidxs[j]]->bounds.inf, node->children[monomialdata->childidxs[j]]->bounds.sup);
10038 SCIPmessageFPrintInfo(messagehdlr, file, "n%d_%d [fillcolor=\"%g,%g,%g\", label=\"", node->depth, node->pos, color, color, color);
10059 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);
10094 SCIP_CALL( exprOpTable[node->op].eval(node->data, node->nchildren, buf, varvals, NULL, &node->value) );
10132 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a bound recalculation in parent nodes */
10133 SCIP_Bool parenttightenisinvalid /**< whether to consider bounds that have been tightened by parents as invalid */
10142 assert(node->depth >= 1); /* node should be in graph and not be at depth 0 (i.e., no variable, constant, or parameter) */
10175 SCIP_CALL( exprOpTable[node->op].inteval(infinity, node->data, node->nchildren, childbounds, NULL, NULL, &newbounds) );
10183 /* NOTE: if you change code below, please make analog changes also in SCIPexprgraphUpdateNodeBoundsCurvature */
10185 /* if bounds of a children were relaxed or our bounds were tightened by a (now possibly invalid) reverse propagation from a parent
10186 * and now our bounds are relaxed, then we have to propagate this upwards to ensure valid bounds
10188 * if bounds were tightened (considerably), then tell this to those parents which think that they have valid bounds
10190 * finally, if there was only a little tightening, then keep this updated bounds, but don't notify parents
10193 ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED) || ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) && parenttightenisinvalid)) )
10213 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);
10227 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */
10228 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
10240 assert(!SCIPintervalIsEmpty(infinity, node->bounds)); /* should not call backward prop. for a node that yield a cutoff already */
10241 assert(!node->enabled || !(node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED)); /* there should be no unprocessed relaxations of children bounds, if node is enabled */
10243 /* if we have no recent bound tightening from a parent, then no use in reverse-propagating our bounds */
10252 if( (node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE) == SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE )
10258 /* 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);
10279 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10285 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10296 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10302 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10313 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10319 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10330 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10336 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10355 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10366 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10375 SCIPintervalPowerScalarInverse(infinity, &childbounds, node->children[0]->bounds, node->data.dbl, node->bounds);
10382 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10403 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10412 SCIPintervalPowerScalarInverse(infinity, &childbounds, node->children[0]->bounds, (SCIP_Real)node->data.intval, node->bounds);
10419 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10436 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10447 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10486 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10499 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10514 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10521 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10537 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10542 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
10608 /* if there are too many unbounded bounds, then could only compute infinite bounds for children, so give up */
10620 * node->bounds.sup - (minlinactivity - c_i.inf), if c_i.inf > -infinity and minlinactivityinf == 0
10634 childbounds.sup = SCIPintervalNegateReal(minlinactivity - node->bounds.sup - node->children[i]->bounds.inf);
10639 * node->bounds.inf - (maxlinactivity - c_i.sup), if c_i.sup < infinity and maxlinactivityinf == 0
10655 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
10686 /* if there is 0.0 in the product, then later division will hardly give useful bounds, so giveup for this i */
10693 SCIPintervalDiv(infinity, &childbounds, node->bounds, childbounds); /* f / prod_{j:j!=i} c_j */
10694 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
10795 /* SCIPdebugMessage("activity = [%10g,%10g] ninf = [%d,%d]; bounds = [%10g,%10g]\n", minlinactivity, maxlinactivity, minlinactivityinf, maxlinactivityinf, node->bounds.inf, node->bounds.sup); */
10797 /* if there are too many unbounded bounds, then could only compute infinite bounds for children, so give up */
10820 ac.sup = SCIPintervalNegateReal(SCIPintervalNegateReal(coefs[i]) * node->children[i]->bounds.sup);
10834 * (node->bounds.sup - minlinactivity)/coefs[i] + c_i.inf, if c_i.inf > -infinity and minlinactivityinf == 0
10835 * (node->bounds.sup - minlinactivity)/coefs[i], if c_i.inf == -infinity and minlinactivityinf == 1
10847 childbounds.sup = SCIPintervalNegateReal((minlinactivity - ac.inf - node->bounds.sup)/coefs[i]);
10852 * (node->bounds.inf - maxlinactivity)/coefs[i] + c_i.sup, if c_i.sup < infinity and maxlinactivityinf == 0
10853 * (node->bounds.inf - maxlinactivity)/coefs[i], if c_i.sup == infinity and maxlinactivityinf == 1
10874 * (node->bounds.sup - minlinactivity)/coefs[i] + c_i.sup, if c_i.sup < infinity and minlinactivityinf == 0
10875 * (node->bounds.sup - minlinactivity)/coefs[i], if c_i.sup == infinity and minlinactivityinf == 1
10886 childbounds.inf = (minlinactivity - ac.inf - node->bounds.sup)/SCIPintervalNegateReal(coefs[i]);
10891 * (node->bounds.inf - maxlinactivity)/coefs[i] + c_i.inf, if c_i.inf > -infinity and maxlinactivityinf == 0
10892 * (node->bounds.inf - maxlinactivity)/coefs[i], if c_i.inf == -infinity and maxlinactivityinf == 1
10900 childbounds.sup = SCIPintervalNegateReal((node->bounds.inf - maxlinactivity)/SCIPintervalNegateReal(coefs[i]));
10904 childbounds.sup = SCIPintervalNegateReal((node->bounds.inf - maxlinactivity + ac.sup)/SCIPintervalNegateReal(coefs[i]));
10909 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
10938 /* too expensive, runtime here is O(nchildren * nquadelems) = O(nquadelems^2) since nchildren <= 2*nquadelems usually */
10972 if( (childbounds.inf > node->children[0]->bounds.inf + 1e-9 || childbounds.sup + 1e-9 < node->children[0]->bounds.sup) )
10974 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",
10977 node->children[1]->bounds.inf, node->children[1]->bounds.sup, childbounds.inf, childbounds.sup, (int)SCIPintervalIsEmpty(infinity, childbounds)
10984 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
10995 if( (childbounds.inf > node->children[1]->bounds.inf + 1e-9 || childbounds.sup + 1e-9 < node->children[1]->bounds.sup) )
10997 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",
11000 node->children[1]->bounds.inf, node->children[1]->bounds.sup, childbounds.inf, childbounds.sup, (int)SCIPintervalIsEmpty(infinity, childbounds)
11007 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[1], childbounds, minstrength, infinity, cutoff);
11040 SCIPintervalMulScalar(infinity, &tmp, node->children[quadelems[k].idx2]->bounds, quadelems[k].coef);
11045 SCIPintervalMulScalar(infinity, &tmp, node->children[quadelems[k].idx1]->bounds, quadelems[k].coef);
11056 SCIPintervalMul(infinity, &tmp, node->children[quadelems[k].idx1]->bounds, node->children[quadelems[k].idx2]->bounds);
11064 SCIPintervalSolveUnivariateQuadExpression(infinity, &childbounds, a, b, c, node->children[i]->bounds);
11068 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
11160 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - 2.0*n);
11170 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - n);
11189 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - 2.0*n);
11199 SCIPintervalPowerScalar(infinity, &tmp, node->children[i]->bounds, monomial->exponents[k] - n);
11215 SCIPintervalPowerScalar(infinity, &tmp, node->children[monomial->childidxs[k]]->bounds, monomial->exponents[k]);
11251 SCIPdebugMessage("solve [%10g,%10g]c%d^%g + [%10g,%10g]c%d^%g = [%10g,%10g] for c%d^%g in [%10g,%10g]",
11252 a.inf, a.sup, i, 2*n, b.inf, b.sup, i, n, c.inf, c.sup, i, n, childpowbounds.inf, childpowbounds.sup);
11271 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[i], childbounds, minstrength, infinity, cutoff);
11273 /* SCIPdebugMessage("-> node %p (%d,%d): [%10g,%10g] = ", (void*)node, node->depth, node->pos, node->bounds.inf, node->bounds.sup);
11297 SCIP_CALL_ABORT( exprdata->prop(infinity, exprdata->userdata, 1, &childbounds, node->bounds, cutoff) );
11300 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[0], childbounds, minstrength, infinity, cutoff);
11305 SCIP_ALLOC_ABORT( BMSallocBlockMemoryArray(exprgraph->blkmem, &childrenbounds, node->nchildren) );
11309 SCIP_CALL_ABORT( exprdata->prop(infinity, exprdata->userdata, node->nchildren, childrenbounds, node->bounds, cutoff) );
11313 SCIPexprgraphTightenNodeBounds(exprgraph, node->children[c], childrenbounds[c], minstrength, infinity, cutoff);
11442 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &node->children, node->nchildren, lastnonnull+1) );
11454 /** aims at simplifying a node in an expression graph, assuming all children have been simplified
11464 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
11487 SCIPdebugMessage("attempt simplification of node %p (%d,%d)\n", (void*)node, node->depth, node->pos);
11499 SCIPdebugMessage("turn node %p (%d,%d) into constant %g\n", (void*)node, node->depth, node->pos, node->value);
11558 * 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
11566 * if child was simplified in this round, it may have already been converted, and then nothing happens
11588 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
11601 if( !EPSISINT(monomial->exponents[factorpos], 0.0) && node->children[i]->data.dbl < 0.0 ) /*lint !e835*/
11604 SCIPmessagePrintWarning(messagehdlr, "got negative constant %g to the power of a noninteger exponent %g\n", node->children[i]->data.dbl, monomial->exponents[factorpos]);
11645 * if child was simplified in this round, it may have already been converted, and then nothing happens
11648 SCIP_CALL( exprConvertToPolynomial(blkmem, &node->children[i]->op, &node->children[i]->data, node->children[i]->nchildren) );
11664 SCIP_CALL( exprgraphNodeAddChildren(blkmem, node, node->children[i]->nchildren, node->children[i]->children, childmap) );
11674 /* if monomial is not sorted, then polynomial should not be sorted either, or have only one monomial */
11677 /* make sure factors are merged, should only be potentially necessary if not sorted, see also #1848 */
11695 SCIP_CALL( polynomialdataExpandMonomialFactor(blkmem, messagehdlr, polynomialdata, j, factorpos,
11696 (SCIP_EXPRDATA_POLYNOMIAL*)node->children[i]->data.data, childmap, maxexpansionexponent, &success) );
11706 /* expansion may remove monomials[j], move a monomial from the end to position j, or add new monomials to the end of polynomialdata
11771 * but if we found duplicates in the children array, then it should be reduced, and we want to count this as a change too
11813 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[i], &childexprs[i], nexprvars, varidx) ); /*lint !e613*/
11834 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, SCIP_EXPR_VARIDX, varidx[node->data.intval]) );
11849 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], node->data.dbl) ); /*lint !e613*/
11857 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], node->data.intval) ); /*lint !e613*/
11870 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, expr, node->op, childexprs[0], childexprs[1]) ); /*lint !e613*/
11903 SCIP_CALL( SCIPexprCreateLinear(exprgraph->blkmem, expr, node->nchildren, childexprs, (SCIP_Real*)node->data.data, ((SCIP_Real*)node->data.data)[node->nchildren]) );
11942 SCIP_CALL( exprdata->copydata(exprgraph->blkmem, node->nchildren, exprdata->userdata, &userdata) );
11948 userdata, exprdata->evalcapability, exprdata->eval, exprdata->inteval, exprdata->curv, exprdata->prop, exprdata->estimate, exprdata->copydata, exprdata->freedata, exprdata->print) );
11968 * @note The function does not clear the array first, but only increases already existing counts.
11973 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */
11991 /** checks whether a node can be put into a component when checking block separability of an expression
11993 * If a variable used by node is already in another component, components are merged and component number is updated.
12017 exprgraphNodeCheckSeparabilityComponent(node->children[i], compnr, nchildcomps, childcomps, nvars, varcomps);
12038 /* variable is already in another component, so have to merge component compnr into that component
12070 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->nodessize, &exprgraph->nnodes, &exprgraph->nodes, &exprgraph->depth, mindepth);
12074 BMSclearMemoryArray(&exprgraph->nodessize[olddepth], exprgraph->depth - olddepth); /*lint !e866*/
12075 BMSclearMemoryArray(&exprgraph->nnodes[olddepth], exprgraph->depth - olddepth); /*lint !e866*/
12081 /** remove a variable from the variables arrays, assuming that its node will be removed or converted next */
12115 SCIP_CALL( exprgraph->exprgraphvarchgidx(exprgraph, exprgraph->userdata, exprgraph->vars[exprgraph->nvars-1], exprgraph->varnodes[exprgraph->nvars-1], exprgraph->nvars-1, varidx) );
12122 SCIP_CALL( SCIPhashmapSetImage(exprgraph->varidxs, exprgraph->vars[varidx], (void*)(size_t)(varidx)) );
12155 SCIPdebugMessage("move node %p (%d,%d) to depth %d\n", (void*)node, node->depth, node->pos, newdepth);
12182 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[newdepth], &exprgraph->nodessize[newdepth], exprgraph->nnodes[newdepth]+1); /*lint !e866*/
12188 /* 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) */
12195 exprgraph->nodes[olddepth][oldpos] = exprgraph->nodes[olddepth][exprgraph->nnodes[olddepth]-1];
12198 /* 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) */
12211 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
12214 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], node) < 0);
12218 /* adding a variable by moving it from a higher depth seems awkward, how did the variable get there in the first place? */
12223 /* nodes at depth 0 always have curvature linear, even before any curvature check was running */
12230 /** given a list of children, tries to find a common parent that represents a given operator with the same given data */
12238 SCIP_EXPR** exprchildren, /**< children of expression to consider when modifying (reordering) operator data, or NULL */
12239 SCIP_EXPRGRAPHNODE** parent /**< buffer to store parent node if any is found, or NULL if none found */
12270 (op != SCIP_EXPR_REALPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/
12271 (op != SCIP_EXPR_SIGNPOWER || opdata.dbl == children[0]->parents[p]->data.dbl) && /*lint !e777*/
12272 (op != SCIP_EXPR_LINEAR || ((SCIP_Real*)opdata.data)[nchildren] == ((SCIP_Real*)children[0]->parents[p]->data.data)[nchildren]) && /*lint !e777*/
12273 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->nquadelems == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->nquadelems) &&
12274 (op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)opdata.data)->constant == ((SCIP_EXPRDATA_QUADRATIC*)children[0]->parents[p]->data.data)->constant) && /*lint !e777*/
12275 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->nmonomials == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->nmonomials) &&
12276 (op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)opdata.data)->constant == ((SCIP_EXPRDATA_POLYNOMIAL*)children[0]->parents[p]->data.data)->constant) /*lint !e777*/
12282 /* for all remaining children, remove parent candidates, that are not in their list of parents */
12288 /* if parentcands[p] is a parent of childnodes[i], then move last parent candidate to position p,
12301 SCIPdebugMessage("check %d parent candidates for expr with operator %d and %d children\n", nparentcands, op, nchildren);
12309 /* at this point, all parents in parentcands have the nodes in children as children and are of the same operator type
12310 * check if there is also one which corresponds to same expression and store that one in *parent
12338 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12339 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12351 * However, if there are duplicates in children, then it can happen that not every child of parentcands[p] is also one of the children.
12352 * So only if children equals parentcands[p]->children in some permutation, the expressions are the same.
12354 if( (parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1]) ||
12363 /* as in the case for two nodes, we need to check whether parentcands[p]->children and children are equal up to permutation */
12390 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12391 assert(parentcands[p]->nchildren == 2); /* that was the second criterium for adding a node to parentcands */
12392 /* order of operands matters, so check if childnodes have same order as children of parent candidate (and are the same nodes too) */
12393 if( parentcands[p]->children[0] == children[0] && parentcands[p]->children[1] == children[1] )
12407 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */
12408 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */
12409 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */
12410 assert(parentcands[0]->data.intval == opdata.intval); /* that was another criterium for adding a node to parentcands */
12421 assert(parentcands[0]->op == op); /* that was the first criterium for adding a node to parentcands */
12422 assert(parentcands[0]->nchildren == 1); /* that was the second criterium for adding a node to parentcands */
12423 assert(parentcands[0]->children[0] == children[0]); /* that's what exprgraphNodeIsParent should have ensured */
12424 assert(parentcands[0]->data.dbl == opdata.dbl); /* that was another criterium for adding a node to parentcands */ /*lint !e777*/
12439 /* sort childnodes, take care that children in expression are sorted the same way if given (so we don't mess up assignment of coefficients) */
12441 SCIPsortPtrPtrReal((void**)children, (void**)exprchildren, exprcoef, exprgraphnodecomp, nchildren);
12446 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12447 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12450 assert(exprcoef[nchildren] == candcoef[nchildren]); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12486 /* sort children in expr and parentcands and update indices in quadelems accordingly, then sort quadelems again and compare */
12496 SCIPsortPtrPtrRealInt((void**)children, (void**)exprchildren, exprlincoef, invperm, exprgraphnodecomp, nchildren);
12501 SCIPsortPtrPtrInt((void**)children, (void**)exprchildren, invperm, exprgraphnodecomp, nchildren);
12527 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12528 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12532 assert(canddata->nquadelems == exprdata->nquadelems); /* that was a criterium for adding a node to parentcands */
12533 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12540 SCIPsortPtrRealInt((void**)parentcands[p]->children, candlincoef, invperm, exprgraphnodecomp, parentcands[p]->nchildren);
12564 /* check if children and linear coefficients in parent candidate and expression are the same */
12569 if( (exprlincoef == NULL ? 0.0 : exprlincoef[i]) != (candlincoef == NULL ? 0.0 : candlincoef[i]) ) /*lint !e777*/
12597 /* @todo in one GlobalLib instance, two polynoms differ only in the sign of all coefficients, it would be nice to recognize this somehow */
12607 /* sort children in expr and parentcands and update child indices in polynomialdata, then sort monomials again and compare */
12616 SCIPsortPtrPtrInt((void**)children, (void**)exprchildren, invperm, exprgraphnodecomp, nchildren);
12630 assert(parentcands[p]->op == op); /* that was the first criterium for adding a node to parentcands */
12631 assert(parentcands[p]->nchildren == nchildren); /* that was the second criterium for adding a node to parentcands */
12634 assert(canddata->nmonomials == exprdata->nmonomials); /* that was a criterium for adding a node to parentcands */
12635 assert(canddata->constant == exprdata->constant); /* that was a criterium for adding a node to parentcands */ /*lint !e777*/
12705 SCIP_EXPRGRAPHNODE** exprnode, /**< buffer to store expression graph node corresponding to root of this expression */
12706 SCIP_Bool* exprnodeisnew /**< buffer to indicate whether the node in *exprnode has been newly created for this expression (otherwise, expression was already in graph) */
12754 /* find node corresponding to constant corresponding to parameter and add if not existing yet */
12778 SCIP_CALL( exprgraphAddExpr(exprgraph, expr->children[i], vars, params, &childnodes[i], &childisnew) ); /*lint !e644*/
12783 /* if all children were known already, check if there is also already a node for the expression that we aim to add */
12786 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, expr->nchildren, childnodes, expr->op, expr->data, expr->children, exprnode) );
12794 /* SCIPdebugMessage("reused node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos);
12809 SCIP_CALL( exprOpTable[expr->op].copydata(exprgraph->blkmem, expr->nchildren, expr->data, &opdata) );
12822 /* SCIPdebugMessage("created new node %p (%d,%d) for expr ", (void*)*exprnode, (*exprnode)->depth, (*exprnode)->pos);
12834 SCIP_Bool* clearreverseprop, /**< flag to set if we had reset bound tightenings from reverse propagation */
12835 SCIP_Bool* boundchanged /**< buffer to store whether a variables bound has changes, compared to those stored in nodes */
12860 /* hmm, may happen due to numerics, let's be conservative and relax bounds to something that seems reasonable */
12875 SCIPdebugMessage("registered relaxed bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
12879 /* if a childs bounds are relaxed, then a previous reverse propagation may be invalid, so we have to clear its remainings */
12889 SCIPdebugMessage("registered tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
12896 SCIPdebugMessage("registered slightly tightened bound [%g,%g] of var %d for propagation\n", node->bounds.inf, node->bounds.sup, i);
13141 /** gives linear coefficients belonging to a SCIP_EXPR_QUADRATIC expression, or NULL if all coefficients are 0.0 */
13236 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */
13237 assert(node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID); /* we assume node bounds to be valid */
13257 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&childcurv, monomial->nfactors), TERMINATE );
13282 *curv = SCIPexprcurvMonomial(monomial->nfactors, monomial->exponents, NULL, childcurv, childbounds);
13448 /* we store the coefficients and the constant in a single array and make this our operand data */
13477 SCIP_CALL( quadraticdataCreate(blkmem, &data, constant, nchildren, lincoefs, nquadelems, quadelems) );
13502 SCIP_CALL( polynomialdataCreate(blkmem, &data, nmonomials, monomials, constant, copymonomials) );
13524 SCIP_CALL( polynomialdataAddMonomials(blkmem, (SCIP_EXPRDATA_POLYNOMIAL*)node->data.data, nmonomials, monomials, copymonomials) );
13539 SCIP_DECL_USEREXPRESTIMATE ((*estimate)), /**< estimation function, or NULL if convex, concave, or not implemented */
13540 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)), /**< expression data copy function, or NULL if nothing to copy */
13541 SCIP_DECL_USEREXPRFREEDATA ((*freedata)), /**< expression data free function, or NULL if nothing to free */
13542 SCIP_DECL_USEREXPRPRINT ((*print)) /**< expression print function, or NULL for default string "user" */
13551 assert((evalcapability & SCIP_EXPRINTCAPABILITY_FUNCVALUE) != 0); /* the function evaluation is not optional */
13552 assert(((evalcapability & SCIP_EXPRINTCAPABILITY_INTFUNCVALUE) == 0) || inteval != NULL); /* if capability says it can do interval evaluation, then the corresponding callback needs to be provided */
13576 /** given a node of an expression graph, splitup a linear part which variables are not used somewhere else in the same expression
13580 * If it is not linear, the node may change, i.e., the remaining nonlinear part may be stored in a new node.
13612 SCIPdebugMessage("split off linear part for %s node %p (%d,%d)\n", SCIPexpropGetName((*node)->op), (void*)*node, (*node)->depth, (*node)->pos);
13641 if( (*node)->data.dbl == 1.0 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13654 if( (*node)->data.intval == 1 && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13667 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13678 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13689 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 )
13701 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 )
13711 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13722 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13733 else if( (*node)->children[0]->op == SCIP_EXPR_VARIDX && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 2 )
13745 else if( ((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX) && linvarssize >= 1 )
13755 if( (*node)->children[0]->op == SCIP_EXPR_CONST && (*node)->children[1]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13763 else if( (*node)->children[1]->op == SCIP_EXPR_CONST && (*node)->children[0]->op == SCIP_EXPR_VARIDX && linvarssize >= 1 )
13830 assert(exprgraph->nvars > 0); /* in a simplified expr graph with no variables, there can only be const nodes, but these were handled above */
13847 SCIP_CALL( exprOpTable[orignode->op].copydata(exprgraph->blkmem, orignode->nchildren, orignode->data, &data) );
13853 SCIP_CALL( SCIPexprgraphAddNode(exprgraph, *node, -1, orignode->nchildren, orignode->children) );
13868 /* we had looked at this above already and only continued if exactly one node is still a child and linvarssize is >= 1 */
13869 assert((*node)->children[0]->op == SCIP_EXPR_VARIDX || (*node)->children[1]->op == SCIP_EXPR_VARIDX);
13870 assert((*node)->children[0]->op != SCIP_EXPR_VARIDX || (*node)->children[1]->op != SCIP_EXPR_VARIDX);
13873 varchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[0] : (*node)->children[1];
13874 otherchild = (*node)->children[0]->op == SCIP_EXPR_VARIDX ? (*node)->children[1] : (*node)->children[0];
13902 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, 2, 1) ); /*lint !e506*/
13994 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14105 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14106 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &coefs, (*node)->nchildren+1, nchildren+1) );
14237 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &(*node)->children, (*node)->nchildren, nchildren) );
14238 SCIP_ALLOC( BMSreallocBlockMemoryArray(exprgraph->blkmem, &quaddata->lincoefs, (*node)->nchildren, nchildren) );
14271 /* get nonlinear child usage: how often each child is used in the polynomial in a nonlinear monomial */
14316 /* we are at a linear monomial in a variable that is not used somewhere else in nonlinear form */
14319 linvars[*nlinvars] = exprgraph->vars[(*node)->children[childidx]->data.intval]; /*lint !e613*/
14379 /* if node was not duplicated and not removed but changed, then invalidate value, bounds, and simplified status */
14413 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, (*srcnode)->parents[0], srcnode, targetnode) );
14452 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);
14457 SCIPdebugMessage("remove node %p (%d, %d) with op %s from expression graph\n", (void*)*node, (*node)->depth, (*node)->pos, SCIPexpropGetName((*node)->op));
14499 exprgraph->nodes[(*node)->depth][(*node)->pos] = exprgraph->nodes[(*node)->depth][exprgraph->nnodes[(*node)->depth]-1];
14520 /* @todo should be a private method and node creation should already capture a node instead of waiting that it's added to the graph */
14573 /** disables a node and recursively all children which have no enabled parents in an expression graph */
14589 /* workaround: don't disable nodes if there could be more users than the one who is disabling the node
14590 * otherwise, if there are several nonlinear constraints using the same expression graph node as root node,
14605 SCIPdebugMessage("disabled node %p (%d,%d), nuses = %d\n", (void*)node, node->depth, node->pos, node->nuses);
14698 * Sets bound status to SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT if tightening is strong enough and not cutoff.
14704 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) */
14706 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
14721 SCIPdebugMessage("ignore bound tightening for node %p (%d,%d)\n", (void*)node, node->depth, node->pos);
14755 SCIPdebugPrintf(" -> [%10g, %10g] status %d\n", node->bounds.inf, node->bounds.sup, node->boundstatus);
14765 SCIP_Real minstrength, /**< minimal required relative bound strengthening to trigger a bound recalculation in parent nodes */
14766 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
14779 assert(node->enabled); /* node should be enabled, otherwise we may not have uptodate bounds and curvatures in children */
14824 SCIP_CALL_TERMINATE( retcode, exprOpTable[node->op].inteval(infinity, node->data, node->nchildren, childbounds, NULL, NULL, &newbounds), TERMINATE );
14826 /* if bounds of a children were relaxed or our bounds were tightened by a (now possibly invalid) reverse propagation from a parent
14827 * and now our bounds are relaxed, then we have to propagate this upwards to ensure valid bounds
14829 * if bounds were tightened (considerably), then tell this to those parents which think that they have valid bounds
14831 * finally, if there was only a little tightening, then keep this updated bounds, but don't notify parents
14834 ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_CHILDRELAXED) || ((node->boundstatus & SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) && clearreverseprop)) )
14854 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);
14865 SCIPdebugMessage("node %p(%d,%d) has empty domain in SCIPexprgraphUpdateNodeBoundsCurvature\n", (void*)node, node->depth, node->pos);
14869 SCIP_CALL_TERMINATE( retcode, exprOpTable[node->op].curv(infinity, node->data, node->nchildren, childbounds, childcurv, &node->curv), TERMINATE );
14871 /* SCIPdebugMessage("curvature %s for %s = ", SCIPexprcurvGetName(node->curv), SCIPexpropGetName(node->op));
15088 int varssizeinit, /**< minimal initial size for variables array, or -1 to choose automatically */
15089 int depthinit, /**< minimal initial depth of expression graph, or -1 to choose automatically */
15090 SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)), /**< callback method to invoke when a variable has been added to the expression graph, or NULL if not needed */
15091 SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)), /**< callback method to invoke when a variable will be removed from the expression graph, or NULL if not needed */
15092 SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)), /**< callback method to invoke when a variable changes its index in the expression graph, or NULL if not needed */
15108 ensureBlockMemoryArraySize3((*exprgraph)->blkmem, &(*exprgraph)->varnodes, &(*exprgraph)->vars, &(*exprgraph)->varbounds, &(*exprgraph)->varssize, varssizeinit);
15109 SCIP_CALL( SCIPhashmapCreate(&(*exprgraph)->varidxs, (*exprgraph)->blkmem, (*exprgraph)->varssize) );
15143 BMSfreeBlockMemoryArrayNull(blkmem, &(*exprgraph)->nodes[d], (*exprgraph)->nodessize[d]); /*lint !e866*/
15176 int mindepth, /**< minimal depth in expression graph where to add node, e.g., 0 or smaller to choose automatically */
15207 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[depth], &exprgraph->nodessize[depth], exprgraph->nnodes[depth]+1); /*lint !e866*/
15226 SCIP_ALLOC( BMSduplicateBlockMemoryArray(exprgraph->blkmem, &node->children, children, nchildren) );
15238 /* set bounds to entire, set status to "should recompute", and note that we have to update something */
15244 /* if not a variable, set value of node according to values of children (if all have valid values) */
15261 SCIP_EXPRGRAPHNODE** varnodes /**< array to store nodes corresponding to variables, or NULL if not of interest */
15272 /* 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 */
15275 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + nvars);
15276 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->nodes[0], &exprgraph->nodessize[0], exprgraph->nnodes[0] + nvars);
15304 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1);
15308 SCIP_CALL( SCIPhashmapInsert(exprgraph->varidxs, vars[i], (void*)(size_t)exprgraph->nvars) ); /*lint !e613*/
15314 SCIPdebugMessage("added node %p (%d, %d) for new variable %d\n", (void*)node, node->depth, node->pos, node->data.intval);
15319 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[i], node) ); /*lint !e613*/
15333 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store pointer to expression graph node corresponding to constant */
15361 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
15364 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], *constnode) < 0);
15366 SCIPdebugMessage("added node %p (%d, %d) for new constant %g\n", (void*)constnode, (*constnode)->depth, (*constnode)->pos, (*constnode)->data.dbl);
15382 SCIP_EXPRGRAPHNODE** rootnode, /**< buffer to store expression graph node corresponding to root of expression tree */
15383 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) */
15401 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[0]->root, exprtrees[0]->vars, exprtrees[0]->params, rootnode, rootnodeisnew) );
15419 SCIP_CALL( exprgraphAddExpr(exprgraph, exprtrees[i]->root, exprtrees[i]->vars, exprtrees[i]->params, &rootnodes[i], &rootnodeisnew_) ); /*lint !e644*/
15450 /* all exprtrees were in the graph already, check if we also already have a node for the sum of rootnodes */
15451 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, op, data, NULL, rootnode) );
15482 /* all exprtrees were in the graph already, check if we also already have a node for the linear combination of rootnodes */
15483 SCIP_CALL( exprgraphFindParentByOperator(exprgraph, nexprtrees, rootnodes, SCIP_EXPR_LINEAR, data, NULL, rootnode) );
15508 rootnodeisnew ? "new" : "old", (void*)*rootnode, (*rootnode)->depth, (*rootnode)->pos, nexprtrees);
15564 SCIPdebugMessage("try to replace varnode %p (%d uses, %d parents) by %p\n", (void*)varnode, varnode->nuses, varnode->nparents, (void*)node);
15584 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varnode->children, 1) ); /*lint !e506*/
15591 varnode->boundstatus = (node->boundstatus == SCIP_EXPRBOUNDSTATUS_VALID) ? SCIP_EXPRBOUNDSTATUS_VALID : SCIP_EXPRBOUNDSTATUS_CHILDRELAXED;
15610 ensureBlockMemoryArraySize(exprgraph->blkmem, &exprgraph->constnodes, &exprgraph->constssize, exprgraph->nconsts + 1);
15613 exprgraph->constssorted = exprgraph->nconsts <= 1 || (exprgraph->constssorted && exprgraphConstNodeComp(exprgraph->constnodes[exprgraph->nconsts-2], varnode) < 0);
15625 ensureBlockMemoryArraySize3(exprgraph->blkmem, &exprgraph->vars, &exprgraph->varnodes, &exprgraph->varbounds, &exprgraph->varssize, exprgraph->nvars + 1);
15629 SCIP_CALL( SCIPhashmapInsert(exprgraph->varidxs, vars[0], (void*)(size_t)exprgraph->nvars) ); /*lint !e613*/
15635 SCIP_CALL( exprgraph->exprgraphvaradded(exprgraph, exprgraph->userdata, vars[0], varnode) ); /*lint !e613*/
15692 SCIP_EXPRGRAPHNODE** varnode /**< buffer to store node corresponding to variable, if found, or NULL if not found */
15721 SCIP_EXPRGRAPHNODE** constnode /**< buffer to store node corresponding to constant, if found, or NULL if not found */
15782 SCIPmessageFPrintInfo(messagehdlr, file, "node [fontcolor=white, style=filled, rankdir=LR]\n");
15839 SCIP_Bool clearreverseprop, /**< whether to reset bound tightenings from reverse propagation */
15840 SCIP_Bool* domainerror /**< buffer to store whether a node with empty bounds has been found, propagation is interrupted in this case */
15856 /* if variable bounds have not changed and we do not have to clear a previous backward propagation, we can just return */
15859 SCIPdebugMessage("no bounds changed and clearreverseprop is FALSE -> skip propagation of variable bounds\n");
15872 SCIPdebugMessage("bounds of node %p(%d,%d) empty, stop bounds propagation\n", (void*)node, node->depth, node->pos);
15888 * NOTE: it is assumed that SCIPexprgraphPropagateVarBounds was called before if variable bounds were relaxed.
15893 SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */
15894 SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
15918 /** updates curvature information in expression graph nodes w.r.t. currently stored variable bounds
15925 SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
15953 SCIPerrorMessage("SCIPexprgraphCheckCurvature gets domain error while propagating variables bounds, ignoring...\n");
15963 * 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)).
15969 int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
15971 SCIP_Bool* domainerror /**< buffer to indicate whether a domain error has been encountered, i.e., some expressions turned into NaN */
16012 /* 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 */
16042 * for each node, convert to polynomials and merge in child nodes that are not in use otherwise, if possible
16061 /* we should be careful about declaring numbers close to zero as zero, so take eps^2 as tolerance */
16062 SCIP_CALL( exprgraphNodeSimplify(exprgraph, node, messagehdlr, eps*eps, maxexpansionexponent, &havechangenode) );
16093 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be simplified */
16113 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */
16123 /* node moved to depth 0, so exprgraph->nodes[i] points to the next node that need to be simplified */
16152 SCIP_CALL( exprUnconvertPolynomial(exprgraph->blkmem, &node->op, &node->data, node->nchildren, (void**)node->children) );
16162 SCIP_CALL( exprgraphNodeReplaceChild(exprgraph, node->parents[j], &node, node->children[0]) );
16167 /* if node was freed, exprgraph->nodes[i] points to the next node that need to be unconverted */
16199 /* nodes that are in use should not have been removed by simplifier, check if they still have the same value in our testpoint */
16210 assert(!SCIPisFinite(testval_before) || EPSZ(SCIPrelDiff(testval_before, testval_after), eps)); /*lint !e777*/
16228 SCIP_EXPRGRAPHNODE* rootnode, /**< expression graph node that should represent root of expression tree */
16243 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
16275 /** creates a sum of expression trees with pairwise disjoint variables from a given node in an expression graph
16282 int exprtreessize, /**< length of exprtrees and exprtreecoefs arrays, need to be at least one */
16313 /* easy cases: if we have space for only one tree or there is only one child or only one variable in the graph,
16320 (node->op != SCIP_EXPR_QUADRATIC || ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1) &&
16321 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1)) )
16340 exprgraphNodeCheckSeparabilityComponent(node->children[i], &compnr, i-1, childcomp, exprgraph->nvars, varcomp); /*lint !e644*/
16363 /* reassign all children in component childcomp[data->quadelems[i].idx2] to component childcomp[data->quadelems[i].idx1] */
16382 if( childcomp[data->monomials[i]->childidxs[j]] != childcomp[data->monomials[i]->childidxs[0]] )
16384 /* reassign all children in component childcomp[data->monomials[i]->childidxs[j]] to component childcomp[data->monomials[i]->childidxs[0]] */
16389 assert(childcomp[data->monomials[i]->childidxs[j]] == childcomp[data->monomials[i]->childidxs[0]]);
16420 /* it turned out that expression is not block separable, so fallback to SCIPexprgraphGetTree */
16432 /* if we have not enough space for all expressions, merge components with number > exprtreessize into component exprtreessize */
16443 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &varidx, exprgraph->nvars) ); /* mapping of expression graph variable indices to expression tree variable indices */
16444 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmap, node->nchildren) ); /* mapping of child indices from node to expressions belonging to a single component */
16445 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childmapinv, node->nchildren) ); /* mapping of child indices from expressions belonging to a single component to node */
16463 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[j], &exprs[nexprs], &nexprvars, varidx) ); /*lint !e644*/
16477 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16488 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16489 /* if component i consists of first child, then it has coefficient 1.0, otherwise it has coefficient -1 */
16501 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16509 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16527 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], exprs[0], nexprvars, 0, NULL) );
16536 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_CONST, nodecoefs[node->nchildren]/nodecoefs[childmapinv[0]]) );
16538 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16545 if( nexprs == 2 && nodecoefs[childmapinv[0]] == nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/
16551 else if( nexprs == 2 && nodecoefs[childmapinv[0]] == -nodecoefs[childmapinv[1]] && (i > 0 || nodecoefs[node->nchildren] == 0.0) ) /*lint !e777*/
16554 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &sumexpr, SCIP_EXPR_MINUS, exprs[0], exprs[1]) );
16572 /* if all coefficients are equal and no constant, create SUM expression, otherwise LINEAR expression */
16580 SCIP_CALL( SCIPexprCreateLinear(exprgraph->blkmem, &sumexpr, nexprs, exprs, coefs, i == 0 ? nodecoefs[node->nchildren] : 0.0) );
16587 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], sumexpr, nexprvars, 0, NULL) );
16622 quadelems[nquadelems].idx1 = MIN(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]); /*lint !e644*/
16623 quadelems[nquadelems].idx2 = MAX(childmap[nodedata->quadelems[j].idx1], childmap[nodedata->quadelems[j].idx2]);
16629 SCIP_CALL( SCIPexprCreateQuadratic(exprgraph->blkmem, &quadexpr, nexprs, exprs, i == 0 ? nodedata->constant : 0.0, lincoefs, nquadelems, quadelems) );
16630 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], quadexpr, nexprvars, 0, NULL) );
16664 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomials[nmonomials], nodedata->monomials[j]->coef, nodedata->monomials[j]->nfactors,
16674 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &polyexpr, nexprs, exprs, nmonomials, monomials, i == 0 ? constant : 0.0, FALSE) );
16675 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[i], polyexpr, nexprvars, 0, NULL) );
16712 /** returns how often expression graph variables are used in a subtree of the expression graph */
16716 int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */
16728 /** gives the number of summands which the expression of an expression graph node consists of */
16764 /** creates a sum of expression trees, possibly sharing variables, from a given node in an expression graph */
16768 int exprtreessize, /**< length of exprtrees and exptreecoefs arrays, should be at least SCIPexprgraphGetSumTreesNSummands() */
16792 (node->op != SCIP_EXPR_QUADRATIC || (((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->lincoefs == NULL && ((SCIP_EXPRDATA_QUADRATIC*)node->data.data)->nquadelems <= 1)) &&
16793 (node->op != SCIP_EXPR_POLYNOMIAL || ((SCIP_EXPRDATA_POLYNOMIAL*)node->data.data)->nmonomials <= 1) )
16867 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodecoefs[node->nchildren] / exprtreecoefs[0]) );
16905 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
16916 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx1], &expr, &nexprvars, varidx) );
16927 /* create expression from the subgraph at quadelems[i].idx2, may add more variables into varidx */
16928 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[quadelems[i].idx2], &expr2, &nexprvars, varidx) );
16934 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) );
16939 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) );
16960 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &constexpr_, SCIP_EXPR_CONST, nodedata->constant / exprtreecoefs[0]) );
16989 /* buffer where to store mapping of expression graph variable indices to expression tree variable indices */
17002 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) );
17013 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_INTPOWER, expr, (int)monomials[i]->exponents[0]) );
17017 SCIP_CALL( SCIPexprCreate(exprgraph->blkmem, &expr, SCIP_EXPR_REALPOWER, expr, monomials[i]->exponents[0]) );
17020 else if( monomials[i]->nfactors == 2 && monomials[i]->exponents[0] == 1.0 && monomials[i]->exponents[1] == 1.0 )
17025 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[0]], &expr, &nexprvars, varidx) );
17026 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[1]], &expr2, &nexprvars, varidx) );
17040 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &childidxs, monomials[i]->nfactors) );
17043 SCIP_CALL( exprgraphNodeCreateExpr(exprgraph, node->children[monomials[i]->childidxs[f]], &exprs[f], &nexprvars, varidx) ); /*lint !e644*/
17048 * add also constant here, but need to divide by monomial coefficient, since we set the exprtreecoefs to monomial coef
17050 SCIP_CALL( SCIPexprCreateMonomial(exprgraph->blkmem, &monomial, 1.0, monomials[i]->nfactors, childidxs, monomials[i]->exponents) );
17051 SCIP_CALL( SCIPexprCreatePolynomial(exprgraph->blkmem, &expr, monomials[i]->nfactors, exprs, 1, &monomial, constant / monomials[i]->coef, FALSE) );
17059 SCIP_CALL( SCIPexprtreeCreate(exprgraph->blkmem, &exprtrees[*nexprtrees], expr, nexprvars, 0, NULL) );
17064 SCIP_ALLOC( BMSallocBlockMemoryArray(exprgraph->blkmem, &exprtrees[*nexprtrees]->vars, nexprvars) );
17079 /* add constant to first summand, if still nonzero; need to divide by coefficient of the this exprtree */
17085 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:2074
#define SCIP_EXPRBOUNDSTATUS_CHILDRELAXED
Definition: type_expr.h:213
void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_Real SCIPexprgraphGetNodeVal(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13331
SCIP_RETCODE SCIPexprgraphPropagateVarBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Bool clearreverseprop, SCIP_Bool *domainerror)
Definition: expr.c:15836
void SCIPexprtreeGetVarsUsage(SCIP_EXPRTREE *tree, int *varsusage)
Definition: expr.c:8907
void SCIPquadelemSort(SCIP_QUADELEM *quadelems, int nquadelems)
Definition: expr.c:9211
SCIP_RETCODE SCIPexprgraphReplaceVarByLinearSum(SCIP_EXPRGRAPH *exprgraph, void *var, int ncoefs, SCIP_Real *coefs, void **vars, SCIP_Real constant)
Definition: expr.c:15517
void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:712
void SCIPintervalMax(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:2487
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:449
Definition: type_expr.h:57
static void exprgraphSortConstNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:9651
void SCIPexprgraphSetVarNodeValue(SCIP_EXPRGRAPHNODE *varnode, SCIP_Real value)
Definition: expr.c:14973
static SCIP_RETCODE exprgraphNodeAddParent(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE *parent)
Definition: expr.c:9344
SCIP_RETCODE SCIPexprSubstituteVars(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR **substexprs)
Definition: expr.c:8145
static SCIP_RETCODE exprsimplifyConvertToPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4265
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
Definition: intervalarith.c:384
SCIP_RETCODE SCIPexprgraphAddNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int mindepth, int nchildren, SCIP_EXPRGRAPHNODE **children)
Definition: expr.c:15173
void SCIPintervalSign(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2701
static SCIP_RETCODE eval(SCIP_EXPR *expr, const vector< Type > &x, SCIP_Real *param, Type &val)
Definition: exprinterpret_cppad.cpp:1766
static SCIP_RETCODE exprsimplifyRemoveDuplicatePolynomialChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real eps)
Definition: expr.c:4289
SCIP_RETCODE SCIPexprgraphGetSumTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs)
Definition: expr.c:16765
SCIP_RETCODE SCIPexprtreeEvalInt(SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_INTERVAL *val)
Definition: expr.c:8739
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:15257
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:8756
int * SCIPexprGetMonomialChildIndices(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5920
SCIP_RETCODE SCIPexprgraphUpdateNodeBoundsCurvature(SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool clearreverseprop)
Definition: expr.c:14762
static SCIP_RETCODE polynomialdataMultiplyByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap)
Definition: expr.c:955
Definition: type_expr.h:72
static SCIP_RETCODE exprUnconvertPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPROP *op, SCIP_EXPROPDATA *data, int nchildren, void **children)
Definition: expr.c:3761
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2265
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:8026
static SCIP_RETCODE exprgraphNodeAddChildren(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, int nexprs, SCIP_EXPRGRAPHNODE **exprs, int *childmap)
Definition: expr.c:9481
int SCIPexprgraphGetNodeNChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12967
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:11789
void SCIPexprPrint(SCIP_EXPR *expr, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames, const char **paramnames, SCIP_Real *paramvals)
Definition: expr.c:8225
static SCIP_RETCODE exprgraphEnsureDepth(SCIP_EXPRGRAPH *exprgraph, int mindepth)
Definition: expr.c:12056
void SCIPsortPtrPtrRealInt(void **ptrarray1, void **ptrarray2, SCIP_Real *realarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
static void polynomialdataSortMonomials(SCIP_EXPRDATA_POLYNOMIAL *polynomialdata)
Definition: expr.c:800
static SCIP_RETCODE exprgraphNodeSimplify(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, SCIP_Bool *havechange)
Definition: expr.c:11459
void SCIPsortPtrPtrReal(void **ptrarray1, void **ptrarray2, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
static SCIP_RETCODE polynomialdataMultiplyByPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_EXPRDATA_POLYNOMIAL *factordata, int *childmap)
Definition: expr.c:999
static SCIP_RETCODE exprparseFindSeparatingComma(const char *str, const char **endptr, int length)
Definition: expr.c:5064
static SCIP_RETCODE exprgraphNodeRemovePolynomialNullChildren(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:11390
void SCIPexprChgPolynomialConstant(SCIP_EXPR *expr, SCIP_Real constant)
Definition: expr.c:6689
SCIP_RETCODE SCIPexprgraphAddConst(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode)
Definition: expr.c:15330
Definition: type_expr.h:74
SCIP_RETCODE SCIPexprtreeGetMaxDegree(SCIP_EXPRTREE *tree, int *maxdegree)
Definition: expr.c:8710
SCIP_Real * SCIPexprtreeGetParamVals(SCIP_EXPRTREE *tree)
Definition: expr.c:8632
void SCIPexprgraphSetVarNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_INTERVAL varbounds)
Definition: expr.c:15017
SCIP_RETCODE SCIPexprCreateMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL **monomial, SCIP_Real coef, int nfactors, int *childidxs, SCIP_Real *exponents)
Definition: expr.c:7035
void SCIPexprgraphCaptureNode(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12945
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:13460
SCIP_Real SCIPexprGetRealPowerExponent(SCIP_EXPR *expr)
Definition: expr.c:5756
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:7795
SCIP_RETCODE SCIPexprPolynomialPower(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int exponent)
Definition: expr.c:6785
void SCIPexprChgMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real newcoef)
Definition: expr.c:6851
SCIP_Real SCIPexprGetPolynomialConstant(SCIP_EXPR *expr)
Definition: expr.c:5888
void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode)
Definition: intervalarith.c:191
void SCIPexprgraphPropagateNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool *cutoff)
Definition: expr.c:15890
void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:843
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT
Definition: type_expr.h:214
SCIP_Bool SCIPexprAreEqual(SCIP_EXPR *expr1, SCIP_EXPR *expr2, SCIP_Real eps)
Definition: expr.c:7580
void SCIPexprMonomialPower(SCIP_EXPRDATA_MONOMIAL *monomial, int exponent)
Definition: expr.c:6926
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetVarNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14963
Definition: type_expr.h:62
Definition: type_expr.h:73
static void exprgraphNodeCheckSeparabilityComponent(SCIP_EXPRGRAPHNODE *node, int *compnr, int nchildcomps, int *childcomps, int nvars, int *varcomps)
Definition: expr.c:11996
static SCIP_RETCODE exprgraphNodeRemovePolynomialDuplicateChildren(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:11332
SCIP_Real SCIPexprgraphGetNodeSignPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13096
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:3292
void SCIPsortPtrPtrInt(void **ptrarray1, void **ptrarray2, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
Definition: struct_misc.h:248
SCIP_RETCODE SCIPexprtreeCopy(BMS_BLKMEM *blkmem, SCIP_EXPRTREE **targettree, SCIP_EXPRTREE *sourcetree)
Definition: expr.c:8812
int SCIPexprgraphGetNodeNParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12987
void SCIPexprGetVarsUsage(SCIP_EXPR *expr, int *varsusage)
Definition: expr.c:7557
void SCIPintervalMin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:2471
SCIP_INTERVAL SCIPexprgraphGetNodeBounds(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13321
SCIP_RETCODE SCIPexprgraphEval(SCIP_EXPRGRAPH *exprgraph, SCIP_Real *varvals)
Definition: expr.c:15815
void SCIPexprReindexVars(SCIP_EXPR *expr, int *newindices)
Definition: expr.c:8183
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
Definition: intervalarith.c:359
void SCIPintervalPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1745
int * SCIPexprgraphGetNNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14923
SCIP_RETCODE SCIPexprEvalInt(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val)
Definition: expr.c:7927
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10087
Definition: type_expr.h:100
void SCIPexprSortMonomialFactors(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:7116
static void polynomialdataApplyChildmap(SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int *childmap)
Definition: expr.c:1158
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:15377
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_RETCODE SCIPexprMultiplyMonomialByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap)
Definition: expr.c:6891
SCIP_RETCODE SCIPexprtreeCreate(BMS_BLKMEM *blkmem, SCIP_EXPRTREE **tree, SCIP_EXPR *root, int nvars, int nparams, SCIP_Real *params)
Definition: expr.c:8771
SCIP_Bool SCIPquadelemSortedFind(SCIP_QUADELEM *quadelems, int idx1, int idx2, int nquadelems, int *pos)
Definition: expr.c:9236
void SCIPexprtreeSetParamVal(SCIP_EXPRTREE *tree, int paramidx, SCIP_Real paramval)
Definition: expr.c:8642
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:1008
int SCIPexprgraphGetNodePolynomialNMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13190
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:10022
static void exprgraphUpdateVarNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_Bool *clearreverseprop, SCIP_Bool *boundchanged)
Definition: expr.c:12832
SCIP_RETCODE SCIPexprgraphMoveNodeParents(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **srcnode, SCIP_EXPRGRAPHNODE *targetnode)
Definition: expr.c:14396
SCIP_EXPRCURV SCIPexprcurvMonomial(int nfactors, SCIP_Real *exponents, int *factoridxs, SCIP_EXPRCURV *factorcurv, SCIP_INTERVAL *factorbounds)
Definition: expr.c:361
SCIP_EXPRDATA_MONOMIAL ** SCIPexprGetMonomials(SCIP_EXPR *expr)
Definition: expr.c:5864
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:2014
public methods for expressions, expression trees, expression graphs, and related stuff ...
SCIP_EXPRCURV SCIPexprcurvMultiply(SCIP_Real factor, SCIP_EXPRCURV curvature)
Definition: expr.c:240
int SCIPexprGetMonomialNFactors(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5910
void SCIPintervalSin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2531
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3025
#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:9010
SCIP_EXPROP SCIPexprgraphGetNodeOperator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13027
static SCIP_RETCODE exprgraphCreateNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_EXPROP op, SCIP_EXPROPDATA opdata)
Definition: expr.c:9722
SCIP_EXPRDATA_MONOMIAL ** SCIPexprgraphGetNodePolynomialMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13178
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:15085
Definition: type_expr.h:47
Definition: type_expr.h:49
int SCIPexprgraphGetNodeOperatorIndex(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13037
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:4924
Definition: struct_misc.h:121
Definition: type_expr.h:53
SCIP_Real SCIPexprgraphGetNodeLinearConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13118
#define ensureBlockMemoryArraySize3(blkmem, array1, array2, array3, cursize, minsize)
Definition: expr.c:87
#define BMSduplicateBlockMemoryArray(mem, ptr, source, num)
Definition: memory.h:443
SCIP_Real SCIPexprgraphGetNodePolynomialConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13202
SCIP_RETCODE SCIPexprAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:6667
SCIP_Bool SCIPexprgraphHasNodeNonlinearAncestor(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14647
SCIP_EXPRCURV SCIPexprgraphGetNodeCurvature(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13341
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:6584
Definition: type_expr.h:51
SCIP_Bool SCIPexprgraphFindConstNode(SCIP_EXPRGRAPH *exprgraph, SCIP_Real constant, SCIP_EXPRGRAPHNODE **constnode)
Definition: expr.c:15718
SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand)
Definition: intervalarith.c:408
SCIP_RETCODE SCIPexprEval(SCIP_EXPR *expr, SCIP_Real *varvals, SCIP_Real *param, SCIP_Real *val)
Definition: expr.c:7866
void SCIPexprgraphSetVarsBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_INTERVAL *varbounds)
Definition: expr.c:14985
static SCIP_Bool isUbBetter(SCIP_Real minstrength, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: expr.c:169
Definition: type_retcode.h:36
SCIP_RETCODE SCIPexprgraphCheckCurvature(SCIP_EXPRGRAPH *exprgraph, SCIP_Real infinity, SCIP_Bool clearreverseprop)
Definition: expr.c:15922
SCIP_RETCODE SCIPexprGetMaxDegree(SCIP_EXPR *expr, int *maxdegree)
Definition: expr.c:7232
static void polynomialdataMultiplyByConstant(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_Real factor)
Definition: expr.c:925
interval arithmetics for provable bounds
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
Definition: intervalarith.c:373
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:13530
void SCIPsortPtrRealInt(void **ptrarray, SCIP_Real *realarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_Real * SCIPexprGetQuadLinearCoefs(SCIP_EXPR *expr)
Definition: expr.c:5840
SCIP_EXPRGRAPHNODE *** SCIPexprgraphGetNodes(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:14933
int SCIPexprgraphGetSumTreesNSummands(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:16729
static SCIP_RETCODE exprsimplifyRemovePolynomialNullChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4343
void SCIPintervalLog(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2403
SCIP_RETCODE SCIPexprCopyDeep(BMS_BLKMEM *blkmem, SCIP_EXPR **targetexpr, SCIP_EXPR *sourceexpr)
Definition: expr.c:6141
Definition: type_expr.h:52
SCIP_Bool SCIPexprgraphHasNodeUserEstimator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13309
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
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:5096
static SCIP_RETCODE quadraticdataCreate(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_QUADRATIC **quadraticdata, SCIP_Real constant, int nchildren, SCIP_Real *lincoefs, int nquadelems, SCIP_QUADELEM *quadelems)
Definition: expr.c:490
SCIP_EXPRCURV SCIPexprcurvPower(SCIP_INTERVAL basebounds, SCIP_EXPRCURV basecurv, SCIP_Real exponent)
Definition: expr.c:253
void print(const Container &container, const std::string &prefix="", const std::string &suffix="", std::ostream &os=std::cout, bool negate=false, int prec=6)
Definition: global_functions.h:95
static SCIP_RETCODE exprgraphNodeReplaceChild(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE **oldchild, SCIP_EXPRGRAPHNODE *newchild)
Definition: expr.c:9582
void SCIPmessagePrintWarning(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:417
internal miscellaneous methods
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem)
Definition: misc.c:9356
static SCIP_Bool exprgraphNodeIsParent(SCIP_EXPRGRAPHNODE *node, SCIP_EXPRGRAPHNODE *parent)
Definition: expr.c:9450
static void polynomialdataFree(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata)
Definition: expr.c:712
void SCIPexprMergeMonomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real eps, SCIP_Bool mergefactors)
Definition: expr.c:6805
SCIP_Bool SCIPexprAreMonomialsEqual(SCIP_EXPRDATA_MONOMIAL *monomial1, SCIP_EXPRDATA_MONOMIAL *monomial2, SCIP_Real eps)
Definition: expr.c:6820
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:13434
SCIP_RETCODE SCIPexprgraphGetSeparableTrees(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int exprtreessize, int *nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *exprtreecoefs)
Definition: expr.c:16279
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_Bool SCIPexprgraphIsNodeEnabled(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12957
SCIP_INTERVAL * SCIPexprgraphGetVarsBounds(SCIP_EXPRGRAPH *exprgraph)
Definition: expr.c:15077
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:6632
SCIP_RETCODE SCIPexprCheckCurvature(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *varbounds, SCIP_Real *param, SCIP_EXPRCURV *curv, SCIP_INTERVAL *bounds)
Definition: expr.c:8062
SCIP_RETCODE SCIPexprEvalUser(SCIP_EXPR *expr, SCIP_Real *argvals, SCIP_Real *val, SCIP_Real *gradient, SCIP_Real *hessian)
Definition: expr.c:7969
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:584
SCIP_RETCODE SCIPexprEvalShallow(SCIP_EXPR *expr, SCIP_Real *argvals, SCIP_Real *varvals, SCIP_Real *param, SCIP_Real *val)
Definition: expr.c:7847
void SCIPexprMultiplyPolynomialByConstant(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real factor)
Definition: expr.c:6702
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
Definition: intervalarith.c:347
void SCIPexprgraphTightenNodeBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_INTERVAL nodebounds, SCIP_Real minstrength, SCIP_Real infinity, SCIP_Bool *cutoff)
Definition: expr.c:14700
static SCIP_RETCODE exprsimplifyUnconvertPolynomials(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4890
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:8107
static SCIP_RETCODE exprgraphNodeUpdateBounds(SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool parenttightenisinvalid)
Definition: expr.c:10129
void SCIPexprFreeMonomial(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL **monomial)
Definition: expr.c:7092
SCIP_RETCODE SCIPexprMulConstant(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPR *term, SCIP_Real factor)
Definition: expr.c:6404
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:7153
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
SCIP_Bool SCIPexprgraphHasNodeSibling(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14612
SCIP_RETCODE SCIPexprgraphGetNodePolynomialMonomialCurvature(SCIP_EXPRGRAPHNODE *node, int monomialidx, SCIP_Real infinity, SCIP_EXPRCURV *curv)
Definition: expr.c:13217
Definition: type_retcode.h:34
SCIP_Real SCIPexprgraphGetNodeOperatorReal(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13048
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:6246
SCIP_Real SCIPexprgraphGetNodeQuadraticConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13130
SCIP_RETCODE SCIPexprMultiplyPolynomialByPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR *factor, int *childmap)
Definition: expr.c:6739
void SCIPexprMergeMonomialFactors(SCIP_EXPRDATA_MONOMIAL *monomial, SCIP_Real eps)
Definition: expr.c:6956
void SCIPintervalCos(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2617
SCIP_EXPRINTCAPABILITY SCIPexprGetUserEvalCapability(SCIP_EXPR *expr)
Definition: expr.c:5962
public data structures and miscellaneous methods
static void polynomialdataMergeMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, SCIP_Real eps, SCIP_Bool mergefactors)
Definition: expr.c:833
Definition: type_expr.h:85
SCIP_Real SCIPexprGetSignPowerExponent(SCIP_EXPR *expr)
Definition: expr.c:5778
static SCIP_RETCODE exprgraphNodeEval(SCIP_EXPRGRAPHNODE *node, SCIP_Real *varvals)
Definition: expr.c:10064
SCIP_Bool SCIPexprgraphAreAllNodeChildrenVars(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14631
void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
Definition: intervalarith.c:3146
Definition: type_expr.h:39
static SCIP_RETCODE monomialdataEnsureFactorsSize(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomialdata, int minsize)
Definition: expr.c:603
void SCIPexprgraphSetVarNodeLb(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_Real lb)
Definition: expr.c:15037
static SCIP_RETCODE exprsimplifyFlattenPolynomials(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPR *expr, SCIP_Real eps, int maxexpansionexponent)
Definition: expr.c:4460
static SCIP_RETCODE exprgraphNodeRemoveParent(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node, SCIP_EXPRGRAPHNODE *parent)
Definition: expr.c:9399
SCIP_EXPRINTDATA * SCIPexprtreeGetInterpreterData(SCIP_EXPRTREE *tree)
Definition: expr.c:8657
SCIP_RETCODE SCIPexprtreeFreeInterpreterData(SCIP_EXPRTREE *tree)
Definition: expr.c:8680
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:3468
void SCIPquadelemSqueeze(SCIP_QUADELEM *quadelems, int nquadelems, int *nquadelemsnew)
Definition: expr.c:9288
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10118
void SCIPintervalSquareRoot(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:1361
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:3209
void SCIPexprgraphGetSubtreeVarsUsage(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int *varsusage)
Definition: expr.c:16713
void SCIPexprgraphSetVarNodeUb(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *varnode, SCIP_Real ub)
Definition: expr.c:15057
static SCIP_Bool exprgraphFindConstNodePos(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int *pos)
Definition: expr.c:9667
void SCIPintervalSquare(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:1289
SCIP_RETCODE SCIPexprgraphNodeSplitOffLinear(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node, int linvarssize, int *nlinvars, void **linvars, SCIP_Real *lincoefs, SCIP_Real *constant)
Definition: expr.c:13584
SCIP_RETCODE SCIPexprCreate(BMS_BLKMEM *blkmem, SCIP_EXPR **expr, SCIP_EXPROP op,...)
Definition: expr.c:5973
void SCIPintervalScalprodScalars(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
Definition: intervalarith.c:1261
Definition: struct_expr.h:116
SCIP_Bool SCIPexprFindMonomialFactor(SCIP_EXPRDATA_MONOMIAL *monomial, int childidx, int *pos)
Definition: expr.c:7136
Definition: type_expr.h:58
void SCIPexprgraphFreeNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node)
Definition: expr.c:14522
void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:557
static void exprgraphNodePropagateBounds(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, SCIP_Real infinity, SCIP_Real minstrength, SCIP_Bool *cutoff)
Definition: expr.c:10223
#define SCIP_EXPRBOUNDSTATUS_CHILDTIGHTENED
Definition: type_expr.h:212
void SCIPexprgraphDisableNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14574
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:8981
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2326
Definition: struct_expr.h:89
void SCIPintervalAbs(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2503
SCIP_Real SCIPexprGetMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5900
static SCIP_RETCODE polynomialdataCopy(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata, SCIP_EXPRDATA_POLYNOMIAL *sourcepolynomialdata)
Definition: expr.c:675
static SCIP_RETCODE polynomialdataExpandMonomialFactor(BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int monomialpos, int factorpos, SCIP_EXPRDATA_POLYNOMIAL *factorpolynomial, int *childmap, int maxexpansionexponent, SCIP_Bool *success)
Definition: expr.c:1187
void * SCIPexprgraphGetNodeVar(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13059
Definition: type_expr.h:63
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9394
SCIP_Real * SCIPexprgraphGetNodeQuadraticLinearCoefs(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13142
static SCIP_RETCODE exprConvertToPolynomial(BMS_BLKMEM *blkmem, SCIP_EXPROP *op, SCIP_EXPROPDATA *data, int nchildren)
Definition: expr.c:3323
SCIP_RETCODE SCIPexprEvalIntUser(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *argvals, SCIP_INTERVAL *val, SCIP_INTERVAL *gradient, SCIP_INTERVAL *hessian)
Definition: expr.c:7992
int SCIPexprgraphGetNodeIntPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13085
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12997
static void exprgraphNodeSortParents(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:9373
static SCIP_RETCODE exprgraphAddExpr(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPR *expr, void **vars, SCIP_Real *params, SCIP_EXPRGRAPHNODE **exprnode, SCIP_Bool *exprnodeisnew)
Definition: expr.c:12700
static SCIP_RETCODE polynomialdataAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:758
static void quadraticdataSort(SCIP_EXPRDATA_QUADRATIC *quadraticdata)
Definition: expr.c:528
Definition: struct_misc.h:74
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3041
SCIP_Bool SCIPexprgraphFindVarNode(SCIP_EXPRGRAPH *exprgraph, void *var, SCIP_EXPRGRAPHNODE **varnode)
Definition: expr.c:15689
Definition: type_expr.h:79
void SCIPexprReindexParams(SCIP_EXPR *expr, int *newindices)
Definition: expr.c:8204
SCIP_Real * SCIPexprgraphGetNodeLinearCoefs(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13107
#define SCIP_EXPRINTCAPABILITY_FUNCVALUE
Definition: type_exprinterpret.h:36
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
Definition: intervalarith.c:396
int SCIPexprgraphGetNodePosition(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13017
static SCIP_Bool isLbBetter(SCIP_Real minstrength, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: expr.c:149
SCIP_RETCODE SCIPexprgraphNodePolynomialAddMonomials(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE *node, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Bool copymonomials)
Definition: expr.c:13511
void SCIPexprFreeShallow(BMS_BLKMEM *blkmem, SCIP_EXPR **expr)
Definition: expr.c:6221
Definition: type_expr.h:86
SCIP_QUADELEM * SCIPexprGetQuadElements(SCIP_EXPR *expr)
Definition: expr.c:5815
SCIP_RETCODE SCIPexprgraphCreateNodePolynomial(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Real constant, SCIP_Bool copymonomials)
Definition: expr.c:13486
void SCIPintervalExp(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
Definition: intervalarith.c:2319
public methods for message output
SCIP_USEREXPRDATA * SCIPexprgraphGetNodeUserData(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13297
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:4789
SCIP_RETCODE SCIPexprgraphCreateNode(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, SCIP_EXPROP op,...)
Definition: expr.c:13351
SCIP_RETCODE SCIPexprEvalIntShallow(SCIP_EXPR *expr, SCIP_Real infinity, SCIP_INTERVAL *argvals, SCIP_INTERVAL *varvals, SCIP_Real *param, SCIP_INTERVAL *val)
Definition: expr.c:7907
SCIP_RETCODE SCIPexprgraphReleaseNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE **node)
Definition: expr.c:14428
#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE
Definition: type_expr.h:216
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:608
SCIP_RETCODE SCIPhashmapSetImage(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2971
SCIP_RETCODE SCIPexprtreeSimplify(SCIP_EXPRTREE *tree, SCIP_MESSAGEHDLR *messagehdlr, SCIP_Real eps, int maxexpansionexponent, int *nlinvars, int *linidxs, SCIP_Real *lincoefs)
Definition: expr.c:8926
SCIP_RETCODE SCIPexprgraphGetTree(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *rootnode, SCIP_EXPRTREE **exprtree)
Definition: expr.c:16226
Definition: type_expr.h:71
Definition: type_expr.h:54
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:463
static SCIP_RETCODE polynomialdataCreate(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL **polynomialdata, int nmonomials, SCIP_EXPRDATA_MONOMIAL **monomials, SCIP_Real constant, SCIP_Bool copymonomials)
Definition: expr.c:628
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:982
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:9340
Definition: struct_expr.h:77
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12977
void SCIPsortPtrReal(void **ptrarray, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPexprAddMonomialFactors(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_MONOMIAL *monomial, int nfactors, int *childidxs, SCIP_Real *exponents)
Definition: expr.c:6862
SCIP_Real * SCIPexprGetMonomialExponents(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5930
void SCIPexprgraphPrintNode(SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: expr.c:14684
SCIP_RETCODE SCIPexprtreeSubstituteVars(SCIP_EXPRTREE *tree, SCIP_EXPR **substexprs)
Definition: expr.c:9045
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:8538
static SCIP_RETCODE exprgraphNodeEvalWithChildren(SCIP_EXPRGRAPHNODE *node, SCIP_Real *varvals)
Definition: expr.c:10108
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:15965
static SCIP_RETCODE exprsimplifyRemovePolynomialUnusedChildren(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:4409
void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:664
static SCIP_RETCODE exprgraphMoveNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int newdepth)
Definition: expr.c:12136
static SCIP_RETCODE exprparseFindClosingParenthesis(const char *str, const char **endptr, int length)
Definition: expr.c:5025
SCIP_RETCODE SCIPexprAddToLinear(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int nchildren, SCIP_Real *coefs, SCIP_EXPR **children, SCIP_Real constant)
Definition: expr.c:6539
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:4146
SCIP_RETCODE SCIPexprMultiplyPolynomialByMonomial(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPRDATA_MONOMIAL *factor, int *childmap)
Definition: expr.c:6716
SCIP_Real SCIPexprgraphGetNodeRealPowerExponent(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13074
Definition: struct_expr.h:55
SCIP_RETCODE SCIPexprintFreeData(SCIP_EXPRINTDATA **interpreterdata)
Definition: exprinterpret_cppad.cpp:2256
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2874
int SCIPexprgraphGetNodeQuadraticNQuadElements(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13166
Definition: type_retcode.h:43
static SCIP_RETCODE polynomialdataPower(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int exponent)
Definition: expr.c:1088
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:6502
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:584
SCIP_Real SCIPexprGetLinearConstant(SCIP_EXPR *expr)
Definition: expr.c:5802
void SCIPexprtreeSetInterpreterData(SCIP_EXPRTREE *tree, SCIP_EXPRINTDATA *interpreterdata)
Definition: expr.c:8667
SCIP_EXPRCURV SCIPexprcurvAdd(SCIP_EXPRCURV curv1, SCIP_EXPRCURV curv2)
Definition: expr.c:205
static void quadelemsQuickSort(SCIP_QUADELEM *elems, int start, int end)
Definition: expr.c:9101
static SCIP_RETCODE polynomialdataEnsureMonomialsSize(BMS_BLKMEM *blkmem, SCIP_EXPRDATA_POLYNOMIAL *polynomialdata, int minsize)
Definition: expr.c:741
SCIP_RETCODE SCIPexprtreeSetParams(SCIP_EXPRTREE *tree, int nparams, SCIP_Real *paramvals)
Definition: expr.c:8876
SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void)
Definition: intervalarith.c:199
static void exprgraphPrintNodeExpression(SCIP_EXPRGRAPHNODE *node, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames, SCIP_Bool printchildrenbounds)
Definition: expr.c:9766
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:12232
static void exprgraphNodeGetVarsUsage(SCIP_EXPRGRAPHNODE *node, int *varsusage)
Definition: expr.c:11971
SCIP_RETCODE SCIPexprgraphPrintDot(SCIP_EXPRGRAPH *exprgraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char **varnames)
Definition: expr.c:15766
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:439
void SCIPintervalSetRoundingModeDownwards(void)
Definition: intervalarith.c:270
void SCIPintervalPowerScalarInverse(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL basedomain, SCIP_Real exponent, SCIP_INTERVAL image)
Definition: intervalarith.c:1993
int SCIPexprgraphGetNodeDepth(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13007
#define ensureBlockMemoryArraySize(blkmem, array1, cursize, minsize)
Definition: expr.c:52
SCIP_RETCODE SCIPexprtreeEval(SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Real *val)
Definition: expr.c:8723
SCIP_EXPRINTCAPABILITY evalcapability
Definition: struct_expr.h:104
void SCIPexprgraphSetVarBounds(SCIP_EXPRGRAPH *exprgraph, void *var, SCIP_INTERVAL varbounds)
Definition: expr.c:14997
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
static SCIP_RETCODE exprgraphRemoveVar(SCIP_EXPRGRAPH *exprgraph, int varidx)
Definition: expr.c:12083
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:2825
void SCIPexprgraphEnableNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:14547
SCIP_QUADELEM * SCIPexprgraphGetNodeQuadraticQuadElements(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13154