Nonlinear handlers define the extended formulations of nonlinear constraints and provide domain propagation and separation routines on this extended formulation. In difference to expression handlers, they do not define a function, but instead identify a structure in an existing expression and provide bound tightening and separation on this structure similar to EXPRINTEVAL, EXPRREVERSEPROP, EXPRINITESTIMATES, and EXPRESTIMATE. The structure typically consists of a composition of expressions.

Nonlinear handlers are a new plugin type in SCIP and may still have some rough edges. They resemble constraint handlers in some sense, but are specific to the handling of nonlinear constraints. We suggest to read section "New Handler for Nonlinear Constraints" in the SCIP 8.0 release report (2021) to understand the role and use of nonlinear handlers before attempting to implement one.

A complete list of all nonlinear handlers contained in this release can be found here. In difference to many other plugins in SCIP, nonlinear handlers are not handled by the SCIP core but by the constraint handler for nonlinear constraints.

Here is what you have to do to implement a nonlinear handler:

Copy the template files src/scip/nlhdlr_xyz.c and src/scip/nlhdlr_xyz.h into files nlhdlr_mystruct.c and nlhdlr_mystruct.h, respectively.
Make sure to adjust your build system such that these files are compiled and linked to your project.
If you are adding a new default plugin, this means updating the src/CMakeLists.txt and Makefile files in the SCIP distribution.
Use SCIPincludeNlhdlrMystruct() in order to include the nonlinear handler into your SCIP instance, e.g., in the main file of your project.
If you are adding a new default plugin, this include function must be added to src/scipdefplugins.c.
Open the new files with a text editor and replace all occurrences of "xyz" by "mystruct".
Adjust the properties of the nonlinear handler (see Properties of a Nonlinear Handler).
Define the nonlinear handler data and nonlinear handler expression data (see Nonlinear Handler Data and Nonlinear Handler Expression Data). This is optional.
Implement the interface methods (see Interface Methods).
Implement the fundamental callback methods (see Fundamental Callback Methods of a Nonlinear Handler).
Implement the additional callback methods (see Additional Callback Methods of a Nonlinear Handler), where necessary.

Additional documentation for the callback methods of a nonlinear handler, in particular for the input parameters, can be found in the file type_nlhdlr.h.

Properties of a Nonlinear Handler

At the top of the new file nlhdlr_mystruct.c, you can find the nonlinear handler properties. These are given as compiler defines. The properties you have to set have the following meaning:

NLHDLR_NAME: the name of the nonlinear handler.: This name is used in the interactive shell to address the nonlinear handler. Additionally, if you are searching for a nonlinear handler with SCIPfindNlhdlrNonlinear(), this name is looked up. Names have to be unique: no two nonlinear handlers may have the same name.

NLHDLR_DESC: the description of the nonlinear handler.: This string is printed as a description of the nonlinear handler in the interactive shell.

NLHDLR_DETECTPRIORITY: the priority of the nonlinear handler when detecting structure.: This priority decides when the NLHDLRDETECT callback of the nonlinear handler is called, relative to other nonlinear handlers, on an expression. Typically, the priority should be strictly positive. This is because the nonlinear handler "default" (having detection priority 0) will not become active on expressions that are already handled by other nonlinear handlers.

NLHDLR_ENFOPRIORITY: the priority of the nonlinear handler when enforcing constraints in the extended formulations.: This priority decides when the callbacks that help on domain propagation and separation are called for an expression for which the nonlinear handler detected a structure. A high priority means that the nonlinear handler will be called before others. The nonlinear handler "default" has enforcement priority 0.

Nonlinear Handler Data and Nonlinear Handler Expression Data

Below the header "Data structures" you can find structs called struct SCIP_NlhdlrData and struct SCIP_NlhdlrExprData. In this first data structure, you can store the data of your nonlinear handler. For example, you should store the adjustable parameters of the nonlinear handler in this data structure. In the second data structure, you can store data that is unique to an expression for which the nonlinear handler detected a structure. For example, the nonlinear handler for quotients stores a representation of a detected quotient in this data structure.
Defining nonlinear handler data and nonlinear handler expression data is optional. You can leave these structs empty.

Interface Methods

At the bottom of nlhdlr_mystruct.c, you can find the interface method SCIPincludeNlhdlrXyz(), which also appears in nlhdlr_mystruct.h. SCIPincludeNlhdlrXyz() is called by the user, if (s)he wants to include the nonlinear handler, i.e., if (s)he wants to use the nonlinear handler in his/her application.

This method is responsible for notifying SCIP of the presence of the nonlinear handler. For this, you must call SCIPincludeNlhdlrNonlinear() from SCIPincludeNlhdlrMystruct(). The function only expects the properties and fundamental callbacks of the nonlinear handler as arguments. Additional callbacks must be added via setter functions as, e.g., SCIPnlhdlrSetCopyHdlr().

If you are using nonlinear handler data, you have to allocate the memory for the data at this point and initialize it. For freeing the nonlinear handler data, see NLHDLRFREEHDLRDATA. You may also add user parameters or statistic tables for your nonlinear handler, see How to add additional user parameters for how to add user parameters.

For the bilinear nonlinear handler, the include method is as follows:

   /* create nonlinear handler specific data */
   SCIP_CALL( SCIPallocBlockMemory(scip, &nlhdlrdata) );
   BMSclearMemory(nlhdlrdata);
 
   SCIP_CALL( SCIPincludeNlhdlrNonlinear(scip, &nlhdlr, NLHDLR_NAME, NLHDLR_DESC, NLHDLR_DETECTPRIORITY,
      NLHDLR_ENFOPRIORITY, nlhdlrDetectBilinear, nlhdlrEvalauxBilinear, nlhdlrdata) );
   assert(nlhdlr != NULL);
 
   SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrBilinear);
   SCIPnlhdlrSetFreeHdlrData(nlhdlr, nlhdlrFreehdlrdataBilinear);
   SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrFreeExprDataBilinear);
   SCIPnlhdlrSetInitExit(nlhdlr, nlhdlrInitBilinear, nlhdlrExitBilinear);
   SCIPnlhdlrSetSepa(nlhdlr, nlhdlrInitSepaBilinear, nlhdlrEnfoBilinear, nlhdlrEstimateBilinear, nlhdlrExitSepaBilinear);
   SCIPnlhdlrSetProp(nlhdlr, nlhdlrIntevalBilinear, nlhdlrReversepropBilinear);
 
   /* parameters */
   SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/useinteval",
         "whether to use the interval evaluation callback of the nlhdlr",
         &nlhdlrdata->useinteval, FALSE, TRUE, NULL, NULL) );
 
   SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/usereverseprop",
         "whether to use the reverse propagation callback of the nlhdlr",
         &nlhdlrdata->usereverseprop, FALSE, TRUE, NULL, NULL) );
 
   SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/maxseparoundsroot",
         "maximum number of separation rounds in the root node",
         &nlhdlrdata->maxseparoundsroot, FALSE, 10, 0, INT_MAX, NULL, NULL) );
 
   SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/maxseparounds",
         "maximum number of separation rounds in a local node",
         &nlhdlrdata->maxseparounds, FALSE, 1, 0, INT_MAX, NULL, NULL) );
 
   SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/maxsepadepth",
         "maximum depth to apply separation",
         &nlhdlrdata->maxsepadepth, FALSE, INT_MAX, 0, INT_MAX, NULL, NULL) );
 
   /* statistic table */
   assert(SCIPfindTable(scip, TABLE_NAME_BILINEAR) == NULL);
   SCIP_CALL( SCIPincludeTable(scip, TABLE_NAME_BILINEAR, TABLE_DESC_BILINEAR, FALSE,
         NULL, NULL, NULL, NULL, NULL, NULL, tableOutputBilinear,
         NULL, TABLE_POSITION_BILINEAR, TABLE_EARLIEST_STAGE_BILINEAR) );

Fundamental Callback Methods of a Nonlinear 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 nonlinear handler is created and included in SCIP via SCIPincludeNlhdlrNonlinear(), see Interface Methods.

Nonlinear handlers have two fundamental callbacks that need to be implemented. Additional documentation for the callback methods, in particular to their input parameters, can be found in type_nlhdlr.h.

NLHDLRDETECT

This callback is called by the handler for nonlinear constraints when extended formulations are constructed. The result of this callback determines the extended formulation.

The nonlinear handler shall analyze the given expression (expr) and decide whether it wants to contribute in enforcing the relation between bounds or an auxiliary variable (auxvar) associated with this expression 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 can be assumed to be associated with the expression and auxiliary variables may be requested for descendant expressions.

We distinguish the following enforcement methods:

SCIP_NLHDLR_METHOD_SEPABELOW : linear underestimation of expr or cut generation for the relation expr ≤ auxvar (denoted as "below")
SCIP_NLHDLR_METHOD_SEPAABOVE : linear overestimation of expr or cut generation for the relation expr ≥ auxvar (denoted as "above")
SCIP_NLHDLR_METHOD_ACTIVITY : domain propagation (i.e., constant under/overestimation) for expr.

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 for expr, or no one uses or sets activities of this expression, or because analysis of the expression has shown that a relation like expr ≥ 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 the nonlinear handler "default" to check whether it should still reach out to the expression handler 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

NLHDLRENFO and/or NLHDLRESTIMATE will be called with overestimate==FALSE if SCIP_NLHDLR_METHOD_SEPABELOW has been set
NLHDLRENFO and/or NLHDLRESTIMATE will be called with overestimate==TRUE if SCIP_NLHDLR_METHOD_SEPAABOVE has been set
NLHDLRINTEVAL and/or NLHDLRREVERSEPROP 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 NLHDLRENFO and NLHDLRESTIMATE needs to be implemented. Also NLHDLREVALAUX will be called in this case. If SCIP_NLHDLR_METHOD_ACTIVITY has been set, then at least one of NLHDLRINTEVAL and NLHDLRREVERSEPROP 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 NLHDLRENFO or NLHDLRESTIMATE,
it will use activity for some subexpressions when computing estimators or cuts, and
it will use activity for some subexpressions when in NLHDLRINTEVAL or NLHDLRREVERSEPROP.

Note that auxiliary variables do not exist in subexpressions during DETECT and are not created by a call to SCIPregisterExprUsageNonlinear(). They will be available when the NLHDLRINITSEPA callback is called.

For an example, see the implementation of the DETECT callback for the nonlinear handler for quotients (src/scip/nlhdlr_quotient.c).

NLHDLREVALAUX

This callback is called by the constraint handler for nonlinear constraints when the violation of constraints in the extended formulation (expr ≤/≥ auxvar) needs to be evaluated. During constraint enforcement, this violation value is used to decide whether estimation and separation callbacks should be called.

The method shall evaluate the expression w.r.t. the auxiliary variables that were introduced by the nonlinear handler (if any). It can be assumed that the expression itself has been evaluated in the given sol.

For an example, see the evaluation for the quotient nonlinear handler:

   /* get auxiliary variables */
   auxvarx = SCIPgetExprAuxVarNonlinear(nlhdlrexprdata->numexpr);
   auxvary = SCIPgetExprAuxVarNonlinear(nlhdlrexprdata->denomexpr);
   assert(auxvarx != NULL);
   assert(auxvary != NULL);
 
   /* get solution values of the auxiliary variables */
   solvalx = SCIPgetSolVal(scip, sol, auxvarx);
   solvaly = SCIPgetSolVal(scip, sol, auxvary);
 
   /* evaluate expression w.r.t. the values of the auxiliary variables */
   nomval = nlhdlrexprdata->numcoef *  solvalx + nlhdlrexprdata->numconst;
   denomval = nlhdlrexprdata->denomcoef *  solvaly + nlhdlrexprdata->denomconst;
 
   /* return SCIP_INVALID if the denominator evaluates to zero */
   *auxvalue = (denomval != 0.0) ? nlhdlrexprdata->constant + nomval / denomval : SCIP_INVALID;

Additional Callback Methods of a Nonlinear 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 SCIPincludeNlhdlrNonlinear(), see also Interface Methods.

NLHDLRCOPYHDLR

This callback is called when doing a copy of the constraint handler for nonlinear constraints. It shall include the nonlinear handler into the copy of the constraint handler.

NLHDLRFREEHDLRDATA

If you are using nonlinear handler data (see Nonlinear Handler Data and Nonlinear Handler Expression Data and Interface Methods), you have to implement this method in order to free the nonlinear handler data.

NLHDLRFREEEXPRDATA

If you are using nonlinear handler expression data (see Nonlinear Handler Data and Nonlinear Handler Expression Data and NLHDLRDETECT), you have to implement this method in order to free the nonlinear handler expression data. This method is called when an extended formulation is freed.

NLHDLRINIT

This callback is called when the constraint handler for nonlinear constraints is initialized, that is, after the problem was transformed. The nonlinear handler can use this callback to initialize or reset some data for the upcoming solve.

NLHDLREXIT

This callback is called when the constraint handler for nonlinear constraints is deinitialized, that is, before the transformed problem is freed. The nonlinear handler can use this callback to free some data that was used for the previous solve only.

NLHDLRINTEVAL

This callback is called when bounds on a given expression shall be computed. It is called for expressions for which the nonlinear handler registered to participate in SCIP_NLHDLR_METHOD_ACTIVITY in NLHDLRDETECT. The method is given the currently available bounds to the expression and can return possibly tighter bounds.

For a univariate quotient ((ax+b)/(cx+d)), the interval evaluation is implemented as follows:

   /* get activity of the numerator (= denominator) expression */
   bnds = SCIPexprGetActivity(nlhdlrexprdata->numexpr);
 
   /* call interval evaluation for the univariate quotient expression */
   *interval = intEvalQuotient(scip, bnds, nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst,
      nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst, nlhdlrexprdata->constant);

NLHDLRREVERSEPROP

This callback is called when bounds on a given expression shall be propagated to its successors. It is called for expressions for which the nonlinear handler registered to participate in SCIP_NLHDLR_METHOD_ACTIVITY in NLHDLRDETECT. The tighter intervals should be passed to the corresponding expression via SCIPtightenExprIntervalNonlinear().

For a univariate quotient ((ax+b)/(cx+d)), reverse propagation is implemented as follows:

   result = reversepropQuotient(bounds, nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst,
      nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst, nlhdlrexprdata->constant);
 
   SCIPdebugMsg(scip, "try to tighten bounds of %p: [%g,%g] -> [%g,%g]\n",
      (void*)nlhdlrexprdata->numexpr, SCIPgetExprBoundsNonlinear(scip, nlhdlrexprdata->numexpr).inf,
      SCIPgetExprBoundsNonlinear(scip, nlhdlrexprdata->numexpr).sup, result.inf, result.sup);
 
   /* tighten bounds of the expression */
   SCIP_CALL( SCIPtightenExprIntervalNonlinear(scip, nlhdlrexprdata->numexpr, result, infeasible, nreductions) );

NLHDLRINITSEPA

This callback is called when the constraint handler for nonlinear constraints initializes the LP relaxation (CONSINITLP). It is called for expressions for which the nonlinear handler registered to participate in SCIP_NLHDLR_METHOD_SEPABELOW or SCIP_NLHDLR_METHOD_SEPAABOVE in NLHDLRDETECT. The method shall initialize the separation data of the nonlinear handler, if any, and add initial cuts to the LP relaxation. It can assume that auxiliary variables are available for expressions for which auxiliary variables were requested via SCIPregisterExprUsageNonlinear() in NLHDLRDETECT.

NLHDLREXITSEPA

This callback is called when the solving process is finished and the branch and bound process data is freed (CONSEXITSOL). It is called for expressions for which the nonlinear handler registered to participate in SCIP_NLHDLR_METHOD_SEPABELOW or SCIP_NLHDLR_METHOD_SEPAABOVE in NLHDLRDETECT and NLHDLRINITSEPA was called. The method shall deinitialize the separation data of the nonlinear handler, if any.

NLHDLRENFO

This callback is called when the constraint handler requires that the relation between the given expression and its auxiliary variable (expr ≤ auxvar or expr ≥ auxvar) is violated by a given solution and this solution needs to be separated. It is called for expressions for which the nonlinear handler registered to participate in SCIP_NLHDLR_METHOD_SEPABELOW or SCIP_NLHDLR_METHOD_SEPAABOVE in NLHDLRDETECT.

The nonlinear handler can enforce expr ≤/≥ auxvar by

separation, i.e., finding an affine hyperplane (a cut) that separates the given point, or
bound tightening, i.e., changing bounds on a variable so that the given point is outside the updated domain, or
adding branching scores to potentially split the current problem into two 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 is usually easier to implement the NLHDLRESTIMATE 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. The constraint handler ensures that lhs ≤ lowerbound(auxvar) and upperbound(auxvar) ≤ rhs.

The constraint handler 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.

NLHDLRESTIMATE

This callback is called when the constraint handler requires that the relaxation between the given expression and its auxiliary variable (expr ≤ auxvar or expr ≥ auxvar) is violated by a given solution and this solution needs to be separated. It is called for expressions for which the nonlinear handler registered to participate in SCIP_NLHDLR_METHOD_SEPABELOW or SCIP_NLHDLR_METHOD_SEPAABOVE in NLHDLRDETECT. This method is a simpler alternative to NLHDLRENFO and is called if NLHDLRENFO is not implemented or does not succeed.

The method shall compute one or several linear under- or overestimator 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 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. 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.

The callback may also be required to indicate for which expression a reduction in the local bounds (usually by branching) would improve the estimator. This is done by a call to SCIPaddExprsViolScoreNonlinear().

For the quotient nonlinear handler, the estimators are computed as follows:

   *addedbranchscores = FALSE;
   *success = FALSE;
 
   SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, TRUE) );
 
   if( nlhdlrexprdata->numexpr == nlhdlrexprdata->denomexpr )
   {
      /* univariate case */
      SCIP_CALL( estimateUnivariateQuotient(scip, sol, nlhdlrexprdata->numexpr, nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst,
         nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst, nlhdlrexprdata->constant, overestimate, rowprep,
         &branchingusefulx, success) );
   }
   else
   {
      /* bivariate case */
      SCIP_CALL( estimateBivariateQuotient(scip, nlhdlrexprdata->numexpr, nlhdlrexprdata->denomexpr, SCIPgetExprAuxVarNonlinear(expr), sol,
         nlhdlrexprdata->numcoef, nlhdlrexprdata->numconst, nlhdlrexprdata->denomcoef, nlhdlrexprdata->denomconst,
         nlhdlrexprdata->constant, overestimate, rowprep,
         &branchingusefulx, &branchingusefuly, success) );
   }
 
   if( *success )
   {
      SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, 0, rowprep) );
   }
   else
   {
      SCIPfreeRowprep(scip, &rowprep);
   }
 
   /* add branching scores if requested */
   if( addbranchscores )
   {
      SCIP_EXPR* exprs[2];
      SCIP_Real violation;
      int nexprs = 0;
 
      if( branchingusefulx )
         exprs[nexprs++] = nlhdlrexprdata->numexpr;
      if( branchingusefuly )
         exprs[nexprs++] = nlhdlrexprdata->denomexpr;
 
      /* compute violation w.r.t. the auxiliary variable(s) */
#ifndef BRSCORE_ABSVIOL
      SCIP_CALL( SCIPgetExprRelAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
#else
      SCIP_CALL( SCIPgetExprAbsAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
#endif
      assert(violation > 0.0);  /* there should be a violation if we were called to enforce */
 
      SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, exprs, nexprs, violation, sol, addedbranchscores) );
   }

NLHDLRSOLLINEARIZE

This callback is called by the constraint handler when it has caught a solution event from SCIP and option constraints/nonlinear/linearizeheursol has been enabled. The constraint handler then calls the nonlinear handlers for all expressions they currently handle. The nonlinear handler may use this opportunity to add a cut that supports its nonlinear function in the given solution to the cutpool. For convex functions, this may help to accellerate proving optimality for a solution found by a NLP solver.