SCIP
Solving Constraint Integer Programs
How to add expression handlers
Expression handlers define basic expression types and provide additional functionality to work with expressions, e.g., differentiation, simplification, estimation, hashing, copying, printing, parsing. A complete list of all expression handlers contained in this release can be found here. In addition to expression handlers, higher level nonlinear structures are handled by nonlinear handlers, see How to add nonlinear handlers.
Here is what you have to do to implement an own expression handler:
- Copy the template files
src/scip/expr_xyz.candsrc/scip/expr_xyz.hinto filesexpr_myfunc.candexpr_myfunc.h, respectively.
Make sure to adjust your Makefile such that these files are compiled and linked to your project. - Use
SCIPincludeExprhdlrMyfunc()in order to include the expression handler into your SCIP instance, e.g., in the main file of your project. - Open the new files with a text editor and replace all occurrences of "xyz" by "myfunc".
- Adjust the properties of the expression handler (see Properties of an Expression Handler).
- Define the expression handler data and expression data (see Expression Handler Data and Expression Data). This is optional.
- Implement the interface methods (see Interface Methods).
- Implement the fundamental callback methods (see Fundamental Callback Methods of an Expression Handler).
- Implement the additional callback methods (see Additional Callback Methods of an Expression Handler), where necessary.
Additional documentation for the callback methods of an expression handler, in particular for the input parameters, can be found in the file type_expr.h.
For a complete implementation of an expression handler, take the one for exponential expressions (src/scip/expr_exp.c) as an example.
Properties of an Expression Handler
At the top of the new file expr_myfunc.c, you can find the expression handler properties. These are given as compiler defines. The properties you have to set have the following meaning:
- EXPRHDLR_NAME: the name of the expression handler.
- This name is used in the interactive shell to address the expression handler. Additionally, if you or a parsing routine is searching for an expression handler with SCIPfindExprhdlr(), this name is looked up. Names have to be unique: no two expression handlers may have the same name.
- EXPRHDLR_DESC: the description of the expression handler.
- This string is printed as a description of the expression handler in the interactive shell.
- EXPRHDLR_PRECEDENCE: the precedence of the expression handler.
- Precedence of the expression operation relative to other expressions when printing the expression.
Expression Handler Data and Expression Data
Below the header "Data structures" you can find structs called struct SCIP_ExprhdlrData and struct SCIP_ExprData. In this first data structure, you can store the data of your expression handler. For example, you should store the adjustable parameters of the expression handler in this data structure. In the second data structure, you can store data that is unique to an expression. For example, the pow expression handler stores the exponent in this data structure.
Defining expression handler data and expression data is optional. You can leave these structs empty.
Interface Methods
SCIPincludeExprhdlrMyfunc()
At the bottom of expr_myfunc.c, you can find the interface method SCIPincludeExprhdlrMyfunc(), which also appears in expr_myfunc.h. SCIPincludeExprhdlrMyfunc() is called by the user, if (s)he wants to include the expression handler, i.e., if (s)he wants to use the expression handler in his/her application.
This method is responsible for notifying SCIP of the presence of the expression handler. For this, you must call SCIPincludeExprhdlr() from SCIPincludeExprhdlrMyfunc(). The function only expects the properties and fundamental callbacks of the expression handler as arguments. Additional callbacks must be added via setter functions as, e.g., SCIPexprhdlrSetCopyFreeHdlr().
If you are using expression handler data, you have to allocate the memory for the data at this point. You can do this by calling:
SCIP_CALL( SCIPallocBlockMemory(scip, &exprhdlrdata) );
You also have to initialize the fields in struct SCIP_ExprhdlrData afterwards. For freeing the expression handler data, see EXPRFREEHDLR.
You may also add user parameters for your expression handler, see How to add additional user parameters for how to add user parameters.
For the logarithm expression handler, the include method is as follows:
SCIP_CALL( SCIPallocClearBlockMemory(scip, &exprhdlrdata) );
SCIP_CALL( SCIPincludeExprhdlr(scip, &exprhdlr, EXPRHDLR_NAME, EXPRHDLR_DESC, EXPRHDLR_PRECEDENCE, evalLog,
exprhdlrdata) );
assert(exprhdlr != NULL);
SCIPexprhdlrSetCopyFreeHdlr(exprhdlr, copyhdlrLog, freehdlrLog);
SCIPexprhdlrSetCopyFreeData(exprhdlr, copydataLog, freedataLog);
SCIPexprhdlrSetSimplify(exprhdlr, simplifyLog);
SCIPexprhdlrSetParse(exprhdlr, parseLog);
SCIPexprhdlrSetIntEval(exprhdlr, intevalLog);
SCIPexprhdlrSetEstimate(exprhdlr, initestimatesLog, estimateLog);
SCIPexprhdlrSetReverseProp(exprhdlr, reversepropLog);
SCIPexprhdlrSetHash(exprhdlr, hashLog);
SCIPexprhdlrSetCurvature(exprhdlr, curvatureLog);
SCIPexprhdlrSetMonotonicity(exprhdlr, monotonicityLog);
"minimal distance from zero to enforce for child in bound tightening",
SCIPcreateExprMyfunc()
Another interface method that can be found in expr_myfunc.c is SCIPcreateExprMyfunc(). This method is called by the user, if (s)he wants to create an expression that is handled by this expression handler. Typically, the creation function takes the operands of the expression (the children) as arguments. SCIPcreateExprMyfunc() may further be extended to take parameters of an expression into account. For example, SCIPcreateExprPow() receives the exponent as argument.
In the implementation of SCIPcreateExprMyfunc(), the expression data shall be allocated and initialized, if the expression has data (like the exponent of pow expressions). Then the expression shall be created by a call to SCIPcreateExpr(). This function takes the expression handler, expression data, children, and ownercreate callback as arguments. For freeing the expression data, see EXPRFREEDATA.
The ownercreate and ownercreatedata that are passed to SCIPcreateExprMyfunc() need to be passed on to SCIP. The owner of the expression that is created uses these arguments to store additional data in an expression. For most usecases, these arguments will be set to NULL. However, if the EXPRPARSE callback is implemented, then SCIPcreateExprMyfunc() may need to be called with a non-NULL value for ownercreate and ownercreatedata. This will be the case if, for example, the constraint handler for nonlinear constraint parses an expression. The constraint handler will then own the expression and needs to store some data in the expression.
For the product expression handler, the expression create function is as follows:
SCIP_CALL( SCIPallocBlockMemory(scip, &exprdata) );
exprdata->coefficient = coefficient;
SCIP_CALL( SCIPcreateExpr(scip, expr, SCIPgetExprhdlrProduct(scip), exprdata, nchildren, children, ownercreate, ownercreatedata) );
Fundamental Callback Methods of an Expression Handler
The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain an operational algorithm. They are passed to SCIP when the expression handler is created and included in SCIP via SCIPincludeExprhdlr(), see Interface Methods.
Expression handlers have one fundamental callback, EXPREVAL, that needs to be implemented. However, expression handlers with stateful expressions (expressions that have data) need to implement also the EXPRCOPYDATA, EXPRFREEDATA, and EXPRCOMPARE callbacks.
Additional documentation for the callback methods, in particular relating to their input parameters, can be found in type_expr.h.
EXPREVAL
The expression evaluation callback defines the mathematical operation that the expression handler represents. Its purpose is to evaluate an expression by taking the values of its children (operands) into account.
The children of the expression can be retrieved via SCIPexprGetChildren() and SCIPexprGetNChildren(). The value (a SCIP_Real) for each child can be retrieved via function SCIPexprGetEvalValue(). The value of the expression should be stored in the argument val that is passed to the callback. For example, the evaluation in the expression handler for sum is doing the following:
*val = exprdata->constant;
for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
{
*val += exprdata->coefficients[c] * SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[c]);
}
When an expression cannot be evaluated w.r.t. the values of its children, such a domain error must be signaled to SCIP by setting *val to SCIP_INVALID. SCIP then aborts evaluation. It is thus not necessary to check in the evaluation callback whether any child has value SCIP_INVALID. For example, the evaluation in the expression handler for logarithm expressions is doing the following:
{
SCIPdebugMsg(scip, "invalid evaluation of logarithmic expression\n");
*val = SCIP_INVALID;
}
else
{
*val = log(SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[0]));
}
The solution (sol) that is passed to EXPREVAL can usually be ignored. It is used by the expression handler for variables to retrieve the value of a variable expression.
Additional Callback Methods of an Expression Handler
The additional callback methods do not need to be implemented in every case. However, some of them have to be implemented for most applications; they can be used, for example, to initialize and free private data. Additional callbacks can be passed via specific setter functions after a call of SCIPincludeExprhdlr(), see also SCIPincludeExprhdlrMyfunc().
EXPRCOPYHDLR
This method should include the expression handler into a given SCIP instance. It is usually called when a copy of SCIP is generated.
By not implementing this callback, the expression handler will not be available in copied SCIP instances. If a nonlinear constraint uses expressions of this type, it will not be possible to copy them. This may deteriorate the performance of primal heuristics using sub-SCIPs.
EXPRFREEHDLR
If you are using expression handler data (see Expression Handler Data and Expression Data and SCIPincludeExprhdlrMyfunc()), you have to implement this method in order to free the expression handler data.
EXPRCOPYDATA
This method is called when creating copies of an expression within the same or between different SCIP instances. It is given the source expression, whose data shall be copied, and expects that the data for the target expression is returned. This data will then be used to create a new expression.
If expressions that are handled by this expression handler have no data, then this callback can be omitted.
EXPRFREEDATA
This method is called when freeing an expression that has data. It is given an expression and shall free its expression data. It shall then call SCIPexprSetData(expr, NULL).
This callback must be implemented for expressions that have data.
EXPRPRINT
This callback is called when an expression is printed. It is called while DFS-iterating over the expression at different stages, that is, when the expression is visited the first time, before each child of the expression is visited, after each child of the expression has been visited, and when the iterator leaves the expression for its parent. At the various stages, the expression may print a string. The given precedence of the parent expression can be used to decide whether parenthesis need to be printed.
For example, the pow expression prints (f(x))^p where f(x) is a print of the child of the pow expression and p is the exponent:
switch( stage )
{
case SCIP_EXPRITER_ENTEREXPR :
{
/* print function with opening parenthesis */
SCIPinfoMessage(scip, file, "(");
break;
}
case SCIP_EXPRITER_VISITINGCHILD :
{
assert(currentchild == 0);
break;
}
case SCIP_EXPRITER_LEAVEEXPR :
{
SCIP_Real exponent = SCIPgetExponentExprPow(expr);
/* print closing parenthesis */
if( exponent >= 0.0 )
SCIPinfoMessage(scip, file, ")^%g", exponent);
else
SCIPinfoMessage(scip, file, ")^(%g)", exponent);
break;
}
case SCIP_EXPRITER_VISITEDCHILD :
default:
break;
}
The pow expression handler does not yet take expression precedence into account to decide whether the parenthesis around f(x) can be omitted. For the sum expression handler, this has been implemented:
switch( stage )
{
case SCIP_EXPRITER_ENTEREXPR :
{
/* print opening parenthesis, if necessary */
if( EXPRHDLR_PRECEDENCE <= parentprecedence )
{
SCIPinfoMessage(scip, file, "(");
}
/* print constant, if nonzero */
if( exprdata->constant != 0.0 )
{
SCIPinfoMessage(scip, file, "%g", exprdata->constant);
}
break;
}
case SCIP_EXPRITER_VISITINGCHILD :
{
SCIP_Real coef;
coef = exprdata->coefficients[currentchild];
/* print coefficient, if necessary */
if( coef == 1.0 )
{
/* if coefficient is 1.0, then print only "+" if not the first term */
if( exprdata->constant != 0.0 || currentchild > 0 )
{
SCIPinfoMessage(scip, file, "+");
}
}
else if( coef == -1.0 )
{
/* if coefficient is -1.0, then print only "-" */
SCIPinfoMessage(scip, file, "-");
}
else
{
/* force "+" sign on positive coefficient if not the first term */
SCIPinfoMessage(scip, file, (exprdata->constant != 0.0 || currentchild > 0) ? "%+g*" : "%g*", coef);
}
break;
}
case SCIP_EXPRITER_LEAVEEXPR :
{
/* print closing parenthesis, if necessary */
if( EXPRHDLR_PRECEDENCE <= parentprecedence )
{
SCIPinfoMessage(scip, file, ")");
}
break;
}
case SCIP_EXPRITER_VISITEDCHILD :
default: ;
}
If this callback is not implemented, the expression is printed as <hdlrname>(<child1>, <child2>, ...).
EXPRPARSE
This callback is called when an expression is parsed from a string and an operator with the name of the expression handler is found. The given string points to the beginning of the arguments of the expression, that is, the beginning of "..." in the string myfunc(...). The callback shall interpret "..." and create an expression, probably via SCIPcreateExprMyfunc(), and return this created expression and the position of the last character in "..." to SCIP. When creating an expression, the given ownercreate and ownercreatedata shall be passed on.
The string "..." likely contains one or several other expressions that will be the children of the myfunc expression. SCIPparseExpr() shall be used to parse these expressions.
For an expression that takes only one argument and has no parameters, the parsing routine is straightforward. For example:
/* parse child expression from remaining string */
assert(childexpr != NULL);
/* create exponential expression */
SCIP_CALL( SCIPcreateExprExp(scip, expr, childexpr, ownercreate, ownercreatedata) );
assert(*expr != NULL);
/* release child expression since it has been captured by the exponential expression */
SCIP_CALL( SCIPreleaseExpr(scip, &childexpr) );
*success = TRUE;
For an expression that has additional data, the parsing routine is slightly more complex. For the signpower expression, this parses signpower(<child>,<exponent>):
/* parse child expression string */
assert(childexpr != NULL);
string = *endstring;
while( *string == ' ' )
++string;
if( *string != ',' )
{
SCIPerrorMessage("Expected comma after first argument of signpower().\n");
return SCIP_READERROR;
}
++string;
{
SCIPerrorMessage("Expected numeric exponent for second argument of signpower().\n");
return SCIP_READERROR;
}
if( exponent <= 1.0 || SCIPisInfinity(scip, exponent) )
{
SCIPerrorMessage("Expected finite exponent >= 1.0 for signpower().\n");
return SCIP_READERROR;
}
/* create signpower expression */
SCIP_CALL( SCIPcreateExprSignpower(scip, expr, childexpr, exponent, ownercreate, ownercreatedata) );
assert(*expr != NULL);
/* release child expression since it has been captured by the signpower expression */
SCIP_CALL( SCIPreleaseExpr(scip, &childexpr) );
*success = TRUE;
If this callback is not implemented, the expression cannot be parsed. For instance, .cip files with nonlinear constraints that use this expression cannot be read.
EXPRCURVATURE
This callback is called when an expression is checked for convexity or concavity. It is important to note that the callback is given a desired curvature (convex, concave, or both (=linear)) and the callback is required to return whether the given expression has the desired curvature. In addition, it can state conditions on the curvature of the children under which the desired curvature can be achieved and it can take bounds on the children into account. SCIPevalExprActivity() and SCIPexprGetActivity() shall be used to evaluate and get bounds on a child expression.
The implementation in the absolute-value expression handler serves as an example:
/* expression is |child|, get domain of child */
SCIP_CALL( SCIPevalExprActivity(scip, child) );
childbounds = SCIPexprGetActivity(child);
childinf = SCIPintervalGetInf(childbounds);
childsup = SCIPintervalGetSup(childbounds);
*success = TRUE;
if( childinf >= 0.0 ) /* |f(x)| = f(x) */
childcurv[0] = exprcurvature;
else if( childsup <= 0.0 ) /* |f(x)| = -f(x) */
childcurv[0] = SCIPexprcurvNegate(exprcurvature);
else if( exprcurvature == SCIP_EXPRCURV_CONVEX ) /* |f(x)|, f mixed sign, is convex if f is linear */
childcurv[0] = SCIP_EXPRCURV_LINEAR;
else /* |f(x)|, f mixed sign, is never concave nor linear */
*success = FALSE;
If this callback is not implemented, the expression is assumed to be indefinite.
EXPRMONOTONICITY
This callback is called when an expression is checked for its monotonicity with respect to a given child. It is given the index of the child and shall return whether the expression is monotonically increasing or decreasing with respect to this child, that is, when assuming that all other children are fixed. Bounds on the children can be taken into account. These can be evaluated and obtained via SCIPevalExprActivity() and SCIPexprGetActivity().
The implementation in the absolute value expression handler serves as an example:
SCIP_CALL( SCIPevalExprActivity(scip, child) );
childbounds = SCIPexprGetActivity(child);
if( childbounds.sup <= 0.0 )
*result = SCIP_MONOTONE_DEC;
else if( childbounds.inf >= 0.0 )
*result = SCIP_MONOTONE_INC;
else
*result = SCIP_MONOTONE_UNKNOWN;
If this callback is not implemented, the expression is assumed to be not monotone in any child.
EXPRINTEGRALITY
This callback is called when an expression is checked for integrality, that is, whether the expression evaluates always to an integral value in a feasible solution. An implementation usually uses SCIPexprIsIntegral() to check whether children evaluate to an integral value.
For example, a sum expression is returned to be integral if all coefficients and all children are integral:
*isintegral = EPSISINT(exprdata->constant, 0.0); /*lint !e835*/
for( i = 0; i < SCIPexprGetNChildren(expr) && *isintegral; ++i )
{
SCIP_EXPR* child = SCIPexprGetChildren(expr)[i];
assert(child != NULL);
}
If this callback is not implemented, the expression is assumed to be not integral.
EXPRHASH
This callback is called when a hash value is computed for an expression. The hash is used to quickly identify expressions that may be equal (or better: to identify expressions that cannot be pairwise equal).
The hash shall be unique to the expression as likely as positive. To achieve this, the hashing algorithm shall use the expression type, expression data, and hash of children as input. It must also be deterministic in this input.
For example, for the sum expression, the coefficients and the hashes of all children are taken into account:
*hashkey = EXPRHDLR_HASHKEY;
*hashkey ^= SCIPcalcFibHash(exprdata->constant);
for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
*hashkey ^= SCIPcalcFibHash(exprdata->coefficients[c]) ^ childrenhashes[c];
EXPRHDLR_HASHKEY is a constant that is unique to the sum expression handler.
If this callback is not implemented, a hash is computed from the expression handler name and the hashes of all children.
EXPRCOMPARE
This callback is called when two expressions (expr1 and expr2) that are handled by the expression handlers need to be compared. The method shall impose an order on expressions and thus must return
- -1 if expr1 < expr2, or
- 0 if expr1 = expr2, or
- 1 if expr1 > expr2.
The callback may use SCIPcompareExpr() to compare children of expr1 and expr2.
For example, for pow expressions, the order is given by the order of the children. If the children are equal, then the order of the exponents is used:
compareresult = SCIPcompareExpr(scip, SCIPexprGetChildren(expr1)[0], SCIPexprGetChildren(expr2)[0]);
if( compareresult != 0 )
return compareresult;
expo1 = SCIPgetExponentExprPow(expr1);
expo2 = SCIPgetExponentExprPow(expr2);
return expo1 == expo2 ? 0 : expo1 < expo2 ? -1 : 1;
If this callback is not implemented, a comparison is done based on the children of expr1 and expr2 only. If the expression is stateful, it must implement this callback.
EXPRBWDIFF
This callback is called when the gradient or Hessian of a function that is represented by an expression is computed.
The method shall compute the partial derivative of the expression w.r.t. a child with specified childidx. That is, it should return
\[ \frac{\partial \text{expr}}{\partial \text{child}_{\text{childidx}}} \]
See also Differentiation methods in scip_expr.h for more details on automatic differentiation of expressions.
For the product expression, backward differentiation is implemented as follows:
{
*val = SCIPexprGetEvalValue(expr) / SCIPexprGetEvalValue(child);
}
else
{
int i;
*val = SCIPexprGetData(expr)->coefficient;
for( i = 0; i < SCIPexprGetNChildren(expr) && (*val != 0.0); ++i )
{
if( i == childidx )
continue;
*val *= SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[i]);
}
}
If this callback is not implemented, gradients and Hessian of functions that involve this expression cannot be computed. This can be hurtful for performance because linear relaxation routines that rely on gradient evaluation (e.g., nlhdlr_convex) cannot be used.
EXPRFWDIFF
This callback is called when the Hessian of a function that is represented by an expression is computed. It may also be used to compute first derivatives.
The method shall evaluate the directional derivative of the expression when interpreted as an operator \( f(c_1, \ldots, c_n) \), where \( c_1, \ldots, c_n \) are the children. The directional derivative is
\[ \sum_{i = 1}^n \frac{\partial f}{\partial c_i} D_u c_i, \]
where \( u \) is the direction (given to the callback) and \( D_u c_i \) is the directional derivative of the i-th child, which can be accessed via SCIPexprGetDot(). The point at which to compute the derivative is given by SCIPexprGetEvalValue().
See also Differentiation methods in scip_expr.h for more details on automatic differentiation of expressions.
For a product, \(f(x) = c\prod_i x_i\), the directional derivative is \(c\sum_j \prod_{i\neq j} x_i x^{\text{dot}}_j\):
*dot = 0.0;
for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
{
SCIP_EXPR* child;
child = SCIPexprGetChildren(expr)[c];
assert(SCIPexprGetEvalValue(child) != SCIP_INVALID);
assert(SCIPexprGetDot(child) != SCIP_INVALID);
if( SCIPexprGetDot(child) == 0.0 )
continue;
if( SCIPexprGetEvalValue(child) != 0.0 )
else
{
SCIP_Real partial;
int i;
partial = SCIPexprGetData(expr)->coefficient;
for( i = 0; i < SCIPexprGetNChildren(expr) && (partial != 0.0); ++i )
{
if( i == c )
continue;
partial *= SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[i]);
}
*dot += partial * SCIPexprGetDot(child);
}
}
If this callback is not implemented, routines (in particular primal heuristics) that rely on solving NLPs cannot be used, as they currently rely on using forward differentiation for gradient computations.
EXPRBWFWDIFF
This callback is called when the Hessian of a function that is represented by an expression is computed.
The method computes the total derivative, w.r.t. its children, of the partial derivative of expr w.r.t. childidx. Equivalently, it computes the partial derivative w.r.t. childidx of the total derivative.
The expression should be interpreted as an operator \( f(c_1, \ldots, c_n) \), where \( c_1, \ldots, c_n \) are the children, and the method should return
\[ \sum_{i = 1}^n \frac{\partial^2 f}{\partial c_i} \partial c_{\text{childidx}} D_u c_i, \]
where \( u \) is the direction (given to the callback) and \( D_u c_i \) is the directional derivative of the i-th child, which can be accessed via SCIPexprGetDot().
Thus, if \( n = 1 \) (i.e., the expression represents a univariate operator), the method should return
\[ f^{\prime \prime}(\text{SCIPexprGetEvalValue}(c)) D_u c. \]
See also Differentiation methods in scip_expr.h for more details on automatic differentiation of expressions.
For a product, \(f(x) = c\prod_i x_i\), the directional derivative is \(c\partial_k \sum_j \prod_{i \neq j} x_i x^{\text{dot}}_j = c\sum_{j \neq k} \prod_{i \neq j, k} x_i x^{\text{dot}}_j\):
*bardot = 0.0;
for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
{
SCIP_EXPR* child;
if( c == childidx )
continue;
child = SCIPexprGetChildren(expr)[c];
assert(SCIPexprGetEvalValue(child) != SCIP_INVALID);
assert(SCIPexprGetDot(child) != SCIP_INVALID);
if( SCIPexprGetDot(child) == 0.0 )
continue;
*bardot += SCIPexprGetEvalValue(expr) / (SCIPexprGetEvalValue(child) * SCIPexprGetEvalValue(partialchild)) * SCIPexprGetDot(child);
else
{
SCIP_Real partial;
int i;
partial = SCIPexprGetData(expr)->coefficient;
for( i = 0; i < SCIPexprGetNChildren(expr) && (partial != 0.0); ++i )
{
if( i == c || i == childidx )
continue;
partial *= SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[i]);
}
*bardot += partial * SCIPexprGetDot(child);
}
}
If this callback is not implemented, there is currently no particular performance impact. In a future version, not implementing this callback would mean that Hessians are not available for NLP solvers, in which case they may have to work with approximations.
EXPRINTEVAL
This callback is called when bounds on an expression need to be computed. It shall compute an (as tight as possible) overestimate on the range that the expression values take w.r.t. bounds (given as SCIP_INTERVAL) for the children. The latter can be accessed via SCIPexprGetActivity().
Often, interval evaluation is implemented analogous to evaluation with numbers. For example, for products:
SCIPintervalSet(interval, exprdata->coefficient);
SCIPdebugMsg(scip, "inteval %p with %d children: %.20g", (void*)expr, SCIPexprGetNChildren(expr), exprdata->coefficient);
for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
{
SCIP_INTERVAL childinterval;
childinterval = SCIPexprGetActivity(SCIPexprGetChildren(expr)[c]);
{
SCIPintervalSetEmpty(interval);
break;
}
/* multiply childinterval with the so far computed interval */
SCIPintervalMul(SCIP_INTERVAL_INFINITY, interval, *interval, childinterval);
}
SCIPdebugMsgPrint(scip, " = [%.20g,%.20g]\n", interval->inf, interval->sup);
If this callback is not implemented, the performance of domain propagation for nonlinear constraints and other routines that rely on bounds of expressions will be impacted severely.
EXPRESTIMATE
While EXPRINTEVAL computes constant under- and overestimators, this callback is called when linear under- or overestimators need to be computed. The estimator shall be as tight as possible at a given point and must be valid w.r.t. given (local) bounds. If the value of the estimator in the reference point is smaller (larger) than a given targetvalue when underestimating (overestimating), then no estimator needs to be computed. Note, that targetvalue can be infinite if any estimator will be accepted.
The callback shall also indicate whether the estimator is also valid w.r.t. given global bounds and for which child a reduction in the local bounds (usually by branching) would improve the estimator.
For the absolute-value expression, the under- and overestimators are computed as follows:
if( !overestimate )
{
*constant = 0.0;
if( refpoint[0] <= 0.0 )
*coefs = -1.0;
else
*coefs = 1.0;
*islocal = FALSE;
*branchcand = FALSE;
}
else
{
/* overestimator */
SCIP_Real lb;
SCIP_Real ub;
lb = localbounds[0].inf;
ub = localbounds[0].sup;
if( !SCIPisPositive(scip, ub) )
{
/* |x| = -x */
*coefs = -1.0;
*constant = 0.0;
*islocal = SCIPisPositive(scip, globalbounds[0].sup);
*branchcand = FALSE;
}
{
/* |x| = x */
*coefs = 1.0;
*constant = 0.0;
*islocal = SCIPisNegative(scip, globalbounds[0].inf);
*branchcand = FALSE;
}
{
/* |x| with x having mixed sign and ub+lb does not cancel out -> secant */
SCIP_Real alpha;
assert(lb < 0.0);
assert(ub > 0.0);
/* let alpha = (|ub|-|lb|) / (ub-lb) = (ub+lb)/(ub-lb)
* then the resulting secant is -lb + alpha * (x - lb) = -lb - alpha*lb + alpha*x
*/
alpha = (ub + lb) / (ub - lb);
*coefs = alpha;
*constant = -lb - alpha * lb;
*islocal = TRUE;
}
else if( lb == -ub ) /*lint !e777*/
{
/* alpha = 0 */
*coefs = 0.0;
*constant = -lb;
*islocal = TRUE;
}
else
{
*success = FALSE;
return SCIP_OKAY;
}
}
If this callback is not implemented, updating the linear relaxation for nonlinear constraints that use this expression will not be possible, which has a severe impact on performance.
EXPRINITESTIMATES
This callback is similar to EXPRESTIMATE, but is not given a reference point. It can also return several (up to SCIP_EXPR_MAXINITESTIMATES many) estimators. A usecase for this callback is the construction of an initial linear relaxation of nonlinear constraints.
For the absolute-value expression, the following initial under- and overestimators are computed:
if( !overestimate )
{
/* compute left tangent -x <= z */
coefs[*nreturned][0] = -1.0;
constant[*nreturned] = 0.0;
(*nreturned)++;
/* compute right tangent x <= z */
coefs[*nreturned][0] = 1.0;
constant[*nreturned] = 0.0;
(*nreturned)++;
}
/* compute secant */
if( overestimate )
{
SCIP_Real lb;
SCIP_Real ub;
lb = bounds.inf;
ub = bounds.sup;
/* it does not make sense to add a cut if child variable is unbounded or fixed */
{
if( !SCIPisPositive(scip, ub) )
{
/* z = -x, so add z <= -x here (-x <= z is the underestimator that is added above) */
coefs[*nreturned][0] = -1.0;
constant[*nreturned] = 0.0;
(*nreturned)++;
}
{
/* z = x, so add z <= x here (x <= z is the underestimator that is added above) */
coefs[*nreturned][0] = 1.0;
constant[*nreturned] = 0.0;
(*nreturned)++;
}
else
{
/* z = abs(x), x still has mixed sign */
SCIP_Real alpha;
/* let alpha = (|ub|-|lb|) / (ub-lb) then the resulting secant looks like
*
* z - |ub| <= alpha * (x - ub) <=> z <= alpha * x + |ub| - alpha * ub
*/
coefs[*nreturned][0] = alpha;
constant[*nreturned] = REALABS(ub) - alpha * ub;
(*nreturned)++;
}
}
}
If this callback is not implemented, the initial linear relaxation for nonlinear constraints may be less tight. This can have a minor effect on performance, as long as EXPRESTIMATE has been implemented and the linear relaxation is still bounded (e.g., when all nonlinear variables have finite bounds).
EXPRSIMPLIFY
This callback shall try to simplify an expression by applying algebraic transformations. It shall return the simplified (and equivalent) expression. It can assume that children have been simplified. If no simplification is possible, then it can return the original expression, but needs to capture it. When creating a new expression, it shall pass on the given ownerdata creation callback and its data.
A simplification that should be implemented by every expression handler at the moment is constant-folding, i.e., returning a value-expression if every child is a value expression. For an example, the simplification for the exponentiation expression is implemented as
/* check for value expression */
if( SCIPisExprValue(scip, child) )
{
SCIP_CALL( SCIPcreateExprValue(scip, simplifiedexpr, exp(SCIPgetValueExprValue(child)), ownercreate, ownercreatedata) );
}
else
{
*simplifiedexpr = expr;
/* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
SCIPcaptureExpr(*simplifiedexpr);
}
See also SCIPsimplifyExpr() for more information on implemented simplification rules.
If this callback is not implemented, reducing the problem size when variables are fixed may not be possible, which can have an impact on performance. (Also bugs may show up as this situation is untested.)
EXPRREVERSEPROP
This callback is called when given bounds on an expression shall be propagated over the children of an expression. Already existing bounds on the children (see EXPRINTEVAL) shall be used. That is, the method shall compute an interval overestimate on
\[ \{ x_i : f(c_1,\ldots,c_{i-1},x_i,c_{i+1},\ldots,c_n) \in \text{bounds} \} \]
for each child \(i\), given bounds on f and initial intervals \(c_i, i=1,\ldots,n,\), for the children.
For univariate expressions, the implementation can be rather straightforward, e.g., for absolute value:
/* abs(x) in I -> x \in (-I \cup I) \cap bounds(x) */
right = bounds; /* I */
SCIPintervalSetBounds(&left, -right.sup, -right.inf); /* -I */
childbounds = childrenbounds[0];
/* childbounds can be empty here already, but that should work fine here */
SCIPintervalIntersect(&left, left, childbounds); /* -I \cap bounds(x), could become empty */
SCIPintervalIntersect(&right, right, childbounds); /* I \cap bounds(x), could become empty */
/* compute smallest interval containing (-I \cap bounds(x)) \cup (I \cap bounds(x)) = (-I \cup I) \cap bounds(x)
* this works also if left or right is empty
*/
SCIPintervalUnify(&childrenbounds[0], left, right);
For multivariate expressions, it can be more complicated, e.g., for products:
SCIPintervalSet(&zero, 0.0);
/* f = const * prod_k c_k => c_i solves c_i * (const * prod_{j:j!=i} c_j) = f */
for( i = 0; i < SCIPexprGetNChildren(expr) && !(*infeasible); ++i )
{
SCIPintervalSet(&otherfactor, exprdata->coefficient);
/* compute prod_{j:j!=i} c_j */
for( j = 0; j < SCIPexprGetNChildren(expr); ++j )
{
if( i == j )
continue;
/* TODO we should compute these only one time instead of repeating this for almost every i */
childbounds = childrenbounds[j];
{
*infeasible = TRUE;
return SCIP_OKAY;
}
SCIPintervalMul(SCIP_INTERVAL_INFINITY, &otherfactor, otherfactor, childbounds);
}
childbounds = childrenbounds[i];
{
*infeasible = TRUE;
return SCIP_OKAY;
}
/* solve x*otherfactor = f for x in c_i */
SCIPintervalSolveUnivariateQuadExpression(SCIP_INTERVAL_INFINITY, &childbounds, zero, otherfactor, bounds, childbounds);
SCIPdebugMsg(scip, "child %d: solved [%g,%g]*x = [%g,%g] with x in [%g,%g] -> x = [%g,%g]\n", i, otherfactor.inf, otherfactor.sup,
bounds.inf, bounds.sup,
childrenbounds[i].inf, childrenbounds[i].sup,
childbounds.inf, childbounds.sup);
/* store computed bounds of the expression */
SCIPintervalIntersect(&childrenbounds[i], childrenbounds[i], childbounds);
{
*infeasible = TRUE;
return SCIP_OKAY;
}
}
If this callback is not implemented, the performance of domain propagation for nonlinear constraints will be impacted severely.