Detailed Description
type definitions related to nonlinear handlers of nonlinear constraints
This file defines the interface for nonlinear handlers.
Definition in file type_nlhdlr.h.
Go to the source code of this file.
Macros | |
#define | SCIP_NLHDLR_METHOD_NONE 0x0u |
#define | SCIP_NLHDLR_METHOD_SEPABELOW 0x1u |
#define | SCIP_NLHDLR_METHOD_SEPAABOVE 0x2u |
#define | SCIP_NLHDLR_METHOD_SEPABOTH (SCIP_NLHDLR_METHOD_SEPABELOW | SCIP_NLHDLR_METHOD_SEPAABOVE) |
#define | SCIP_NLHDLR_METHOD_ACTIVITY 0x4u |
#define | SCIP_NLHDLR_METHOD_ALL (SCIP_NLHDLR_METHOD_SEPABOTH | SCIP_NLHDLR_METHOD_ACTIVITY) |
#define | SCIP_DECL_NLHDLRCOPYHDLR(x) |
#define | SCIP_DECL_NLHDLRFREEHDLRDATA(x) |
#define | SCIP_DECL_NLHDLRFREEEXPRDATA(x) |
#define | SCIP_DECL_NLHDLRINIT(x) |
#define | SCIP_DECL_NLHDLREXIT(x) |
#define | SCIP_DECL_NLHDLRDETECT(x) |
#define | SCIP_DECL_NLHDLREVALAUX(x) |
#define | SCIP_DECL_NLHDLRINTEVAL(x) |
#define | SCIP_DECL_NLHDLRREVERSEPROP(x) |
#define | SCIP_DECL_NLHDLRINITSEPA(x) |
#define | SCIP_DECL_NLHDLREXITSEPA(x) |
#define | SCIP_DECL_NLHDLRENFO(x) |
#define | SCIP_DECL_NLHDLRESTIMATE(x) |
Typedefs | |
typedef unsigned int | SCIP_NLHDLR_METHOD |
typedef struct SCIP_Nlhdlr | SCIP_NLHDLR |
typedef struct SCIP_NlhdlrData | SCIP_NLHDLRDATA |
typedef struct SCIP_NlhdlrExprData | SCIP_NLHDLREXPRDATA |
Macro Definition Documentation
◆ SCIP_NLHDLR_METHOD_NONE
#define SCIP_NLHDLR_METHOD_NONE 0x0u |
no enforcement
Definition at line 41 of file type_nlhdlr.h.
Referenced by detectNlhdlr(), and SCIP_DECL_NLHDLRDETECT().
◆ SCIP_NLHDLR_METHOD_SEPABELOW
#define SCIP_NLHDLR_METHOD_SEPABELOW 0x1u |
separation for expr <= auxvar, thus might estimate expr from below
Definition at line 42 of file type_nlhdlr.h.
Referenced by addTightEstimatorCuts(), createNlhdlrExprData(), detectNlhdlr(), enforceExpr(), SCIP_DECL_EXPR_OWNERPRINT(), SCIP_DECL_NLHDLRDETECT(), and SCIP_DECL_NLHDLRENFO().
◆ SCIP_NLHDLR_METHOD_SEPAABOVE
#define SCIP_NLHDLR_METHOD_SEPAABOVE 0x2u |
separation for expr >= auxvar, thus might estimate expr from above
Definition at line 43 of file type_nlhdlr.h.
Referenced by addTightEstimatorCuts(), createNlhdlrExprData(), detectNlhdlr(), enforceExpr(), SCIP_DECL_EXPR_OWNERPRINT(), SCIP_DECL_NLHDLRDETECT(), and SCIP_DECL_NLHDLRENFO().
◆ SCIP_NLHDLR_METHOD_SEPABOTH
#define SCIP_NLHDLR_METHOD_SEPABOTH (SCIP_NLHDLR_METHOD_SEPABELOW | SCIP_NLHDLR_METHOD_SEPAABOVE) |
separation for expr == auxvar
Definition at line 44 of file type_nlhdlr.h.
Referenced by analyzeViolation(), detectNlhdlr(), enforceExpr(), initSepa(), SCIP_DECL_NLHDLRDETECT(), and SCIP_DECL_NLHDLREVALAUX().
◆ SCIP_NLHDLR_METHOD_ACTIVITY
#define SCIP_NLHDLR_METHOD_ACTIVITY 0x4u |
activity computation (interval evaluation) and propagation (reverse propagation)
Definition at line 45 of file type_nlhdlr.h.
Referenced by detectNlhdlr(), forwardPropExpr(), propExprDomains(), reversePropQueue(), SCIP_DECL_EXPR_OWNERPRINT(), and SCIP_DECL_NLHDLRDETECT().
◆ SCIP_NLHDLR_METHOD_ALL
#define SCIP_NLHDLR_METHOD_ALL (SCIP_NLHDLR_METHOD_SEPABOTH | SCIP_NLHDLR_METHOD_ACTIVITY) |
all enforcement methods
Definition at line 46 of file type_nlhdlr.h.
Referenced by detectNlhdlr(), and SCIP_DECL_NLHDLRDETECT().
◆ SCIP_DECL_NLHDLRCOPYHDLR
#define SCIP_DECL_NLHDLRCOPYHDLR | ( | x | ) |
nonlinear handler copy callback
The method includes the nonlinear handler into a nonlinear constraint handler.
This method is usually called when doing a copy of a nonlinear constraint handler.
- Parameters
-
[in] targetscip target SCIP main data structure [in] targetconshdlr target nonlinear constraint handler [out] sourceconshdlr nonlinear constraint handler in source SCIP [out] sourcenlhdlr nonlinear handler in source SCIP
Definition at line 61 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLRFREEHDLRDATA
#define SCIP_DECL_NLHDLRFREEHDLRDATA | ( | x | ) |
callback to free data of handler
- Parameters
-
[in] scip SCIP data structure [in] nlhdlr nonlinear handler [in] nlhdlrdata nonlinear handler data to be freed
Definition at line 73 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLRFREEEXPRDATA
#define SCIP_DECL_NLHDLRFREEEXPRDATA | ( | x | ) |
callback to free expression specific data
- Parameters
-
[in] scip SCIP data structure [in] nlhdlr nonlinear handler [in] expr expression [in] nlhdlrexprdata nonlinear handler expression data to be freed
Definition at line 85 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLRINIT
#define SCIP_DECL_NLHDLRINIT | ( | x | ) |
callback to be called in initialization (called after problem was transformed)
- Parameters
-
[in] scip SCIP data structure [in] nlhdlr nonlinear handler
Definition at line 96 of file type_nlhdlr.h.
Referenced by SCIP_DECL_NLHDLRFREEEXPRDATA().
◆ SCIP_DECL_NLHDLREXIT
#define SCIP_DECL_NLHDLREXIT | ( | x | ) |
callback to be called in deinitialization (called before transformed problem is freed)
- Parameters
-
[in] scip SCIP data structure [in] nlhdlr nonlinear handler
Definition at line 105 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLRDETECT
#define SCIP_DECL_NLHDLRDETECT | ( | x | ) |
callback to detect structure in expression
The nonlinear handler shall analyze the current expression and decide whether it wants to contribute in enforcing the relation between this expression (expr
) and its descendants (e.g., children) via linear under- or overestimation, cut generation, and/or activity computation and propagation. For linear under- or overestimation and cut generation, an auxiliary variable (auxvar
) can be assumed to be associated with expr
and auxiliary variables may be requested in descendant expressions.
We distinguish the following enforcement methods:
- SCIP_NLHDLR_METHOD_SEPABELOW : linear underestimation of
expr
or cut generation for the relationexpr
≤auxvar
(denoted as "below") - SCIP_NLHDLR_METHOD_SEPAABOVE : linear overestimation of
expr
or cut generation for the relationexpr
≥auxvar
(denoted as "above") - SCIP_NLHDLR_METHOD_ACTIVITY : domain propagation (i.e., constant under/overestimation) for the relation
expr
=auxvar
.
On input, parameter enforcing
indicates for any of these methods, whether
- it is not necessary to have such a method, e.g., because no
auxvar
will exist forexpr
, or no one uses or sets activities of this expression, or because analysis of the expression has shown that a relation likeexpr
≥auxvar
is not necessary to be satisfied, - or there already exists a nonlinear handler that will provide this method in an "enforcement" sense, that is, it believes that no one else could provide this method in a stronger sense. (This is mainly used by nlhdlr_default to check whether it should still reach out to the exprhdlr or whether it would be dominated by some nonlinear handler.)
The DETECT callback shall augment the enforcing
bitmask by setting the enforcement methods it wants to provide in an "enforcement" sense.
Additionally, the participating
bitmask shall be set if the nonlinear handler wants to be called on this expression at all. Here, it shall set all methods that it wants to provide, which are those set in enforcing
, but additionally those where it wants to participate but leave enforcement to another nonlinear handler. This can be useful for nonlinear handlers that do not implement a complete enforcement, e.g., a handler that only contributes cutting planes in some situations only.
A nonlinear handler will be called only for those callbacks that it mentioned in participating
, which is
- ENFO and/or ESTIMATE will be called with
overestimate==FALSE
if SCIP_NLHDLR_METHOD_SEPABELOW has been set - ENFO and/or ESTIMATE will be called with
overestimate==TRUE
if SCIP_NLHDLR_METHOD_SEPAABOVE has been set - INTEVAL and/or REVERSEPROP will be called if SCIP_NLHDLR_METHOD_ACTIVITY has been set
If SCIP_NLHDLR_METHOD_SEPABELOW or SCIP_NLHDLR_METHOD_SEPAABOVE has been set, then at least one of the callbacks ENFO and ESTIMATE needs to be implemented. Also EVALAUX will be called in this case. If SCIP_NLHDLR_METHOD_ACTIVITY has been set, then at least one of INTEVAL and REVERSEPROP needs to be implemented. If the nonlinear handler chooses not to participate, then it must not set nlhdlrexprdata
and can leave participating
at its initial value (SCIP_NLHDLR_METHOD_NONE).
Additionally, a nonlinear handler that decides to participate in any of the enforcement methods must call SCIPregisterExprUsageNonlinear() for every subexpression that it will use and indicate whether
- it will use an auxiliary variable in ENFO or ESTIMATE,
- it will use activity for some subexpressions when computing estimators or cuts, and
- it will use activity for some subexpressions when in INTEVAL or REVERSEPROP.
- Note
- Auxiliary variables do not exist in subexpressions during DETECT and are not created by a call to SCIPregisterExprUsageNonlinear(). They will be available when the INITSEPA callback is called.
- Parameters
-
[in] scip SCIP data structure [in] conshdlr nonlinear constraint handler [in] nlhdlr nonlinear handler [in] expr expression to analyze [in] cons the constraint that expression defines, or NULL when the expr does not define any constraint, that is, when it is not the root of an expression of a constraint [in,out] enforcing enforcement methods that are provided by some nonlinear handler (to be updated by detect callback) [out] participating enforcement methods that this nonlinear handler should be called for (to be set by detect callback), initialized to SCIP_NLHDLR_METHOD_NONE [out] nlhdlrexprdata nlhdlr's expr data to be stored in expr, can only be set to non-NULL if success is set to TRUE
Definition at line 168 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLREVALAUX
#define SCIP_DECL_NLHDLREVALAUX | ( | x | ) |
auxiliary evaluation callback of nonlinear handler
Evaluates the expression w.r.t. the auxiliary variables that were introduced by the nonlinear handler (if any). The method is used to determine the violation of the relation that the nonlinear handler attempts to enforce. During enforcement, this violation value is used to decide whether estimation/separation callbacks should be called.
It can be assumed that the expression itself has been evaluated in the given sol.
- Parameters
-
[in] scip SCIP data structure [in] nlhdlr nonlinear handler [in] expr expression to evaluate [in] nlhdlrexprdata expression specific data of the nonlinear handler [out] auxvalue buffer to store value of expression w.r.t. auxiliary variables [in] sol point to evaluate
Definition at line 193 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLRINTEVAL
#define SCIP_DECL_NLHDLRINTEVAL | ( | x | ) |
nonlinear handler interval evaluation (activity computation) callback
The method computes an interval that contains the image (range) of the expression.
- Parameters
-
[in] scip SCIP main data structure [in] nlhdlr nonlinear handler [in] expr expression [in] nlhdlrexprdata expression specific data of the nonlinear handler [in,out] interval buffer where to store interval (on input: current interval for expr, on output: computed interval for expr) [in] intevalvar callback to be called when interval evaluating a variable [in] intevalvardata data to be passed to intevalvar callback
Definition at line 213 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLRREVERSEPROP
#define SCIP_DECL_NLHDLRREVERSEPROP | ( | x | ) |
nonlinear handler callback for reverse propagation
The method propagates the given bounds over the arguments of an expression. The arguments of an expression are other expressions and the tighter intervals should be passed to the corresponding argument (expression) via SCIPtightenExprIntervalNonlinear().
- Parameters
-
[in] scip SCIP main data structure [in] conshdlr nonlinear constraint handler [in] nlhdlr nonlinear handler [in] expr expression [in] nlhdlrexprdata expression specific data of the nonlinear handler [in] bounds the bounds on the expression that should be propagated [out] infeasible buffer to store whether an expression's bounds were propagated to an empty interval [out] nreductions buffer to store the number of interval reductions of all children
Definition at line 237 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLRINITSEPA
#define SCIP_DECL_NLHDLRINITSEPA | ( | x | ) |
separation initialization method of a nonlinear handler (called during CONSINITLP)
The method shall initialize the separation data of the nonlinear handler, if any, and add initial cuts to the LP relaxation.
- Parameters
-
[in] scip SCIP main data structure [in] conshdlr nonlinear constraint handler [in] cons nonlinear constraint [in] nlhdlr nonlinear handler [in] nlhdlrexprdata exprdata of nonlinear handler [in] expr expression [in] overestimate whether the expression needs to be overestimated [in] underestimate whether the expression needs to be underestimated [out] infeasible buffer to store whether infeasibility was detected while building the LP
Definition at line 261 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLREXITSEPA
#define SCIP_DECL_NLHDLREXITSEPA | ( | x | ) |
separation deinitialization method of a nonlinear handler (called during CONSEXITSOL)
The method shall deinitialize the separation data of the nonlinear handler, if any.
- Parameters
-
[in] scip SCIP main data structure [in] nlhdlr nonlinear handler [in] nlhdlrexprdata exprdata of nonlinear handler [in] expr expression
Definition at line 281 of file type_nlhdlr.h.
Referenced by SCIP_DECL_NLHDLRINITSEPA().
◆ SCIP_DECL_NLHDLRENFO
#define SCIP_DECL_NLHDLRENFO | ( | x | ) |
nonlinear handler separation and enforcement callback
The method tries to separate the given solution from the set defined by either
expr - auxvar <= 0 (if !overestimate)
or
expr - auxvar >= 0 (if overestimate),
where auxvar = SCIPgetExprAuxVarNonlinear(expr)
.
It can do so by
- separation, i.e., finding an affine hyperplane (a cut) that separates the given point,
- bound tightening, i.e., changing bounds on a variable so that the given point is outside the updated domain,
- adding branching scores to potentially split the current problem into 2 subproblems
If parameter inenforcement
is FALSE, then only the first option (separation) is allowed.
If the nonlinear handler always separates by computing a linear under- or overestimator of expr, then it could be advantageous to implement the ESTIMATE callback instead.
Note, that the nonlinear handler may also choose to separate for a relaxation of the mentioned sets, e.g., expr
≤ upperbound(auxvar
) or expr
≥ lowerbound(auxvar
). This is especially useful in situations where expr
is the root expression of a constraint and it is sufficient to satisfy lhs
≤ expr
≤ rhs
. cons_nonlinear ensures that lhs
≤ lowerbound(auxvar
) and upperbound(auxvar
) ≤ rhs
.
cons_nonlinear may call this callback first with allowweakcuts
= FALSE and repeat later with allowweakcuts
= TRUE, if it didn't succeed to enforce a solution without using weak cuts. If in enforcement and the nonlinear handler cannot enforce by separation or bound tightening, it should register branching scores for those expressions where branching may help to compute tighter cuts in children.
The nonlinear handler must set result
to SCIP_SEPARATED if it added a cut, to SCIP_REDUCEDDOM if it added a bound change, and to SCIP_BRANCHED if it added branching scores. Otherwise, it may set result to SCIP_DIDNOTRUN or SCIP_DIDNOTFIND.
Parameter cons
gives the constraint that is currently enforced. Note that expr
does not need to be the root of this constraint, i.e., SCIPgetExprNonlinear(cons)==expr
may not hold. If an expression appears in several constraints, it is not well defined which constraint is given in cons
. The main purpose of cons
is to provide a constraint source for LP rows that are added in this callback.
- Parameters
-
[in] scip SCIP main data structure [in] conshdlr nonlinear constraint handler [in] cons nonlinear constraint that is currently enforced [in] nlhdlr nonlinear handler [in] expr expression [in] nlhdlrexprdata expression specific data of the nonlinear handler [in] sol solution to be separated (NULL for the LP solution) [in] auxvalue current value of expression w.r.t. auxiliary variables as obtained from EVALAUX [in] overestimate whether the expression needs to be over- or underestimated [in] allowweakcuts whether we should only look for "strong" cuts, or anything that separates is fine [in] separated whether another nonlinear handler already added a cut for this expression [in] inenforcement whether we are in enforcement, or only in separation [out] result pointer to store the result
Definition at line 344 of file type_nlhdlr.h.
◆ SCIP_DECL_NLHDLRESTIMATE
#define SCIP_DECL_NLHDLRESTIMATE | ( | x | ) |
nonlinear handler under/overestimation callback
The method tries to compute linear under- or overestimators of expr
that are as tight as possible at a given point. If the value of the estimator in the solution is smaller (larger) than targetvalue
when underestimating (overestimating), then no estimator needs to be computed. Note, that targetvalue
can be infinite if any estimator will be accepted. If successful, it shall store the estimators in the given rowpreps
data structure and set the rowprep->local
flag accordingly (SCIProwprepSetLocal()). The sidetype of a rowprep must be set to SCIP_SIDETYPE_LEFT if overestimating and SCIP_SIDETYPE_RIGHT if underestimating.
If the callback is required to indicate for which expression a reduction in the local bounds (usually by branching) would improve the estimator, it shall do so via calls to SCIPaddExprsViolScoreNonlinear().
- Parameters
-
[in] scip SCIP main data structure [in] conshdlr constraint handler [in] nlhdlr nonlinear handler [in] expr expression [in] nlhdlrexprdata expression data of nonlinear handler [in] sol solution at which to estimate (NULL for the LP solution) [in] auxvalue current value of expression w.r.t. auxiliary variables as obtained from EVALAUX [in] overestimate whether the expression needs to be over- or underestimated [in] targetvalue a value the estimator shall exceed, can be +/-infinity [in] addbranchscores indicates whether to register branching scores [out] rowpreps an array where to store the estimators [out] success buffer to indicate whether an estimator could be computed [out] addedbranchscores buffer to store whether the branching score callback was successful
Definition at line 387 of file type_nlhdlr.h.
Typedef Documentation
◆ SCIP_NLHDLR_METHOD
typedef unsigned int SCIP_NLHDLR_METHOD |
nlhdlr methods bitflags
Definition at line 48 of file type_nlhdlr.h.
◆ SCIP_NLHDLR
typedef struct SCIP_Nlhdlr SCIP_NLHDLR |
nonlinear handler
Definition at line 402 of file type_nlhdlr.h.
◆ SCIP_NLHDLRDATA
typedef struct SCIP_NlhdlrData SCIP_NLHDLRDATA |
nonlinear handler data
Definition at line 403 of file type_nlhdlr.h.
◆ SCIP_NLHDLREXPRDATA
typedef struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA |
nonlinear handler data for a specific expression
Definition at line 404 of file type_nlhdlr.h.