# SCIP

Solving Constraint Integer Programs

## Detailed Description

nonlinear handler to handle quadratic expressions

Some definitions:

• a BILINEXPRTERM is a product of two expressions
• a QUADEXPRTERM stores an expression expr that is known to appear in a nonlinear, quadratic term, that is expr^2 or expr*other_expr. It stores its sqrcoef (that can be 0), its linear coef and all the bilinear expression terms in which expr appears.

#include <string.h>
#include "scip/cons_nonlinear.h"
#include "scip/pub_nlhdlr.h"
#include "scip/nlhdlr_quadratic.h"
#include "scip/expr_pow.h"
#include "scip/expr_sum.h"
#include "scip/expr_var.h"
#include "scip/expr_product.h"
#include "scip/pub_misc_rowprep.h"

Go to the source code of this file.

struct  Rays

## Macros

#define INTERLOG(x)

#define NLHDLR_DESC   "handler for quadratic expressions"

#define NLHDLR_DETECTPRIORITY   1

#define NLHDLR_ENFOPRIORITY   100

#define INTERCUTS_MINVIOL   1e-4

#define DEFAULT_USEINTERCUTS   FALSE

#define DEFAULT_USESTRENGTH   FALSE

#define DEFAULT_USEBOUNDS   FALSE

#define BINSEARCH_MAXITERS   120

#define DEFAULT_NCUTSROOT   20

#define DEFAULT_NCUTS   2

## Typedefs

typedef struct Rays RAYS

## Functions

static SCIP_RETCODE addColToCut (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real cutcoef, SCIP_COL *col)

static SCIP_RETCODE addRowToCut (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real cutcoef, SCIP_ROW *row, SCIP_Bool *success)

static SCIP_RETCODE constructBasicVars2TableauRowMap (SCIP *scip, int *map)

static int countBasicVars (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, SCIP_Bool *nozerostat)

static SCIP_RETCODE storeDenseTableauRow (SCIP *scip, SCIP_COL *col, int *basicvarpos2tableaurow, int nbasiccol, int raylength, SCIP_Real *binvrow, SCIP_Real *binvarow, SCIP_Real *tableaurows)

static SCIP_RETCODE storeDenseTableauRowsByColumns (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, int raylength, SCIP_VAR *auxvar, SCIP_Real *tableaurows, int *rayentry2conspos)

static SCIP_RETCODE createRays (SCIP *scip, RAYS **rays)

static SCIP_RETCODE createBoundRays (SCIP *scip, RAYS **rays, int size)

static void freeRays (SCIP *scip, RAYS **rays)

static SCIP_RETCODE insertRayEntry (SCIP *scip, RAYS *rays, SCIP_Real coef, int coefidx, int coefpos)

static void constructLPPos2ConsPosMap (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, int *map)

static SCIP_RETCODE insertRayEntries (SCIP *scip, RAYS *rays, SCIP_Real *densetableaucols, int *rayentry2conspos, int raylength, int nray, int conspos, SCIP_Real factor, int *nnonz, SCIP_Bool *success)

static SCIP_RETCODE createAndStoreSparseRays (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, RAYS **raysptr, SCIP_Bool *success)

static SCIP_RETCODE intercutsComputeCommonQuantities (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, SCIP_Real sidefactor, SCIP_SOL *sol, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real *wzlp, SCIP_Real *kappa)

static SCIP_Real computeEigenvecDotRay (SCIP_Real *eigenvec, int nquadvars, SCIP_Real *raycoefs, int *rayidx, int raynnonz)

static SCIP_Real computeWRayLinear (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real sidefactor, SCIP_Real *raycoefs, int *rayidx, int raynnonz)

static SCIP_RETCODE computeRestrictionToRay (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *raycoefs, int *rayidx, int raynnonz, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real *coefs1234a, SCIP_Real *coefs4b, SCIP_Real *coefscondition, SCIP_Bool *success)

static SCIP_Real evalPhiAtRay (SCIP_Real t, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e)

static SCIP_Real isCase4a (SCIP_Real tsol, SCIP_Real *coefs4a, SCIP_Real *coefscondition)

static void doBinarySearch (SCIP *scip, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e, SCIP_Real *sol)

static SCIP_Real computeRoot (SCIP *scip, SCIP_Real *coefs)

static SCIP_Real computeIntersectionPoint (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_Bool iscase4, SCIP_Real *coefs1234a, SCIP_Real *coefs4b, SCIP_Real *coefscondition)

static SCIP_Bool areCoefsNumericsGood (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_Real *coefs1234a, SCIP_Real *coefs4b, SCIP_Bool iscase4)

static SCIP_RETCODE computeIntercut (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_ROWPREP *rowprep, SCIP_Real *interpoints, SCIP_SOL *sol, SCIP_Bool *success)

static void combineRays (SCIP_Real *raycoefs1, int *rayidx1, int raynnonz1, SCIP_Real *raycoefs2, int *rayidx2, int raynnonz2, SCIP_Real *newraycoefs, int *newrayidx, int *newraynnonz, SCIP_Real coef1, SCIP_Real coef2)

static SCIP_Bool raysAreDependent (SCIP *scip, SCIP_Real *raycoefs1, int *rayidx1, int raynnonz1, SCIP_Real *raycoefs2, int *rayidx2, int raynnonz2, SCIP_Real *coef)

static SCIP_RETCODE rayInRecessionCone (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, int j, int i, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real alpha, SCIP_Bool *inreccone, SCIP_Bool *success)

static SCIP_RETCODE findRho (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, int idx, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real *interpoints, SCIP_Real *rho, SCIP_Bool *success)

static SCIP_RETCODE computeStrengthenedIntercut (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, RAYS *rays, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *strengthsuccess)

static SCIP_RETCODE setVarToNearestBound (SCIP *scip, SCIP_SOL *sol, SCIP_SOL *vertex, SCIP_VAR *var, SCIP_Real *factor, SCIP_Bool *success)

static SCIP_RETCODE findVertexAndGetRays (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_SOL *vertex, SCIP_VAR *auxvar, RAYS **raysptr, SCIP_Bool *success)

static SCIP_Bool isQuadConsViolated (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *auxvar, SCIP_SOL *sol, SCIP_Real sidefactor)

static SCIP_RETCODE generateIntercut (SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool overestimate, SCIP_Bool *success)

static SCIP_Bool isPropagable (SCIP_EXPR *qexpr)

static SCIP_Bool isPropagableTerm (SCIP_EXPR *qexpr, int idx)

static SCIP_RETCODE propagateBoundsQuadExpr (SCIP *scip, SCIP_EXPR *expr, SCIP_Real sqrcoef, SCIP_INTERVAL b, SCIP_INTERVAL rhs, SCIP_Bool *infeasible, int *nreductions)

static SCIP_RETCODE propagateBoundsLinExpr (SCIP *scip, SCIP_EXPR *expr, SCIP_Real b, SCIP_INTERVAL rhs, SCIP_Bool *infeasible, int *nreductions)

static SCIP_Real computeMaxBoundaryForBilinearProp (SCIP_Real a, SCIP_Real c, SCIP_Real x1, SCIP_Real x2)

static SCIP_Real computeMaxForBilinearProp (SCIP_Real a, SCIP_Real c, SCIP_INTERVAL dom)

static void computeRangeForBilinearProp (SCIP_INTERVAL exprdom, SCIP_Real coef, SCIP_INTERVAL rhs, SCIP_INTERVAL *range)

static SCIP_RETCODE reversePropagateLinearExpr (SCIP *scip, SCIP_EXPR **linexprs, int nlinexprs, SCIP_Real *lincoefs, SCIP_Real constant, SCIP_INTERVAL rhs, SCIP_Bool *infeasible, int *nreductions)

## ◆ INTERLOG

 #define INTERLOG ( x )

Definition at line 42 of file nlhdlr_quadratic.c.

## ◆ NLHDLR_DESC

 #define NLHDLR_DESC   "handler for quadratic expressions"

Definition at line 58 of file nlhdlr_quadratic.c.

## ◆ NLHDLR_DETECTPRIORITY

 #define NLHDLR_DETECTPRIORITY   1

Definition at line 59 of file nlhdlr_quadratic.c.

## ◆ NLHDLR_ENFOPRIORITY

 #define NLHDLR_ENFOPRIORITY   100

Definition at line 60 of file nlhdlr_quadratic.c.

Definition at line 63 of file nlhdlr_quadratic.c.

Definition at line 64 of file nlhdlr_quadratic.c.

the position of the statistics table

Definition at line 65 of file nlhdlr_quadratic.c.

output of the statistics table is only printed from this stage onwards

Definition at line 66 of file nlhdlr_quadratic.c.

## ◆ INTERCUTS_MINVIOL

 #define INTERCUTS_MINVIOL   1e-4

Definition at line 69 of file nlhdlr_quadratic.c.

## ◆ DEFAULT_USEINTERCUTS

 #define DEFAULT_USEINTERCUTS   FALSE

Definition at line 70 of file nlhdlr_quadratic.c.

## ◆ DEFAULT_USESTRENGTH

 #define DEFAULT_USESTRENGTH   FALSE

Definition at line 71 of file nlhdlr_quadratic.c.

## ◆ DEFAULT_USEBOUNDS

 #define DEFAULT_USEBOUNDS   FALSE

Definition at line 72 of file nlhdlr_quadratic.c.

## ◆ BINSEARCH_MAXITERS

 #define BINSEARCH_MAXITERS   120

Definition at line 73 of file nlhdlr_quadratic.c.

Referenced by doBinarySearch(), and findRho().

## ◆ DEFAULT_NCUTSROOT

 #define DEFAULT_NCUTSROOT   20

Definition at line 74 of file nlhdlr_quadratic.c.

## ◆ DEFAULT_NCUTS

 #define DEFAULT_NCUTS   2

Definition at line 75 of file nlhdlr_quadratic.c.

## ◆ RAYS

 typedef struct Rays RAYS

Definition at line 156 of file nlhdlr_quadratic.c.

## ◆ SCIP_DECL_TABLEOUTPUT()

static

output method of statistics table to output file stream 'file'

Definition at line 165 of file nlhdlr_quadratic.c.

 static SCIP_RETCODE addColToCut ( SCIP * scip, SCIP_ROWPREP * rowprep, SCIP_SOL * sol, SCIP_Real cutcoef, SCIP_COL * col )
static

adds cutcoef * (col - col*) to rowprep

Parameters
 scip SCIP data structure rowprep rowprep to store intersection cut sol solution to separate cutcoef cut coefficient col column to add to rowprep

Definition at line 205 of file nlhdlr_quadratic.c.

Referenced by computeIntercut(), and computeStrengthenedIntercut().

 static SCIP_RETCODE addRowToCut ( SCIP * scip, SCIP_ROWPREP * rowprep, SCIP_Real cutcoef, SCIP_ROW * row, SCIP_Bool * success )
static

adds cutcoef * (slack - slack*) to rowprep

row is lhs ≤ <coefs, vars> + constant ≤ rhs, thus slack is defined by slack + <coefs.vars> + constant = side

If row (slack) is at upper, it means that <coefs,vars*> + constant = rhs, and so slack* = side - rhs –> slack - slack* = rhs - <coefs, vars> - constant.

If row (slack) is at lower, then <coefs,vars*> + constant = lhs, and so slack* = side - lhs –> slack - slack* = lhs - <coefs, vars> - constant.

Parameters
 scip SCIP data structure rowprep rowprep to store intersection cut cutcoef cut coefficient row row, whose slack we are ading to rowprep success if the row is nonbasic enough

Definition at line 240 of file nlhdlr_quadratic.c.

Referenced by computeIntercut(), and computeStrengthenedIntercut().

## ◆ constructBasicVars2TableauRowMap()

 static SCIP_RETCODE constructBasicVars2TableauRowMap ( SCIP * scip, int * map )
static

constructs map between lp position of a basic variable and its row in the tableau

Parameters
 scip SCIP data structure map buffer to store the map

Definition at line 301 of file nlhdlr_quadratic.c.

Referenced by storeDenseTableauRowsByColumns().

## ◆ countBasicVars()

 static int countBasicVars ( SCIP_NLHDLREXPRDATA * nlhdlrexprdata, SCIP_VAR * auxvar, SCIP_Bool * nozerostat )
static

counts the number of basic variables in the quadratic expr

Parameters
 nlhdlrexprdata nlhdlr expression data auxvar aux var of expr or NULL if not needed (e.g. separating real cons) nozerostat whether there is no variable with basis status zero

Definition at line 327 of file nlhdlr_quadratic.c.

Referenced by createAndStoreSparseRays().

## ◆ storeDenseTableauRow()

 static SCIP_RETCODE storeDenseTableauRow ( SCIP * scip, SCIP_COL * col, int * basicvarpos2tableaurow, int nbasiccol, int raylength, SCIP_Real * binvrow, SCIP_Real * binvarow, SCIP_Real * tableaurows )
static

stores the row of the tableau where col is basic

In general, we will have

basicvar1 = tableaurow var1
basicvar2 = tableaurow var2
...
basicvarn = tableaurow varn


However, we want to store the the tableau row by columns. Thus, we need to know which of the basic vars col is.

Note we only store the entries of the nonbasic variables

Parameters
 scip SCIP data structure col basic columns to store its tableau row basicvarpos2tableaurow map between basic var and its tableau row nbasiccol which basic var this is raylength the length of a ray (the total number of basic vars) binvrow buffer to store row of Binv binvarow buffer to store row of Binv A tableaurows pointer to store the tableau rows

Definition at line 406 of file nlhdlr_quadratic.c.

Referenced by storeDenseTableauRowsByColumns().

## ◆ storeDenseTableauRowsByColumns()

 static SCIP_RETCODE storeDenseTableauRowsByColumns ( SCIP * scip, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, int raylength, SCIP_VAR * auxvar, SCIP_Real * tableaurows, int * rayentry2conspos )
static

stores the rows of the tableau corresponding to the basic variables in the quadratic expression

Also return a map storing to which var the entry of a ray corresponds, i.e., if the tableau is

basicvar_1 = ray1_1 nonbasicvar_1 + ...
basicvar_2 = ray1_2 nonbasicvar_1 + ...
...
basicvar_n = ray1_n nonbasicvar_1 + ...


The map maps k to the position of basicvar_k in the variables of the constraint assuming the variables are sorted as [quadratic vars, linear vars, auxvar].

Parameters
 scip SCIP data structure nlhdlrexprdata nlhdlr expression data raylength length of a ray of the tableau auxvar aux var of expr or NULL if not needed (e.g. separating real cons) tableaurows buffer to store the tableau rows rayentry2conspos buffer to store the map

Definition at line 473 of file nlhdlr_quadratic.c.

Referenced by createAndStoreSparseRays().

## ◆ createRays()

 static SCIP_RETCODE createRays ( SCIP * scip, RAYS ** rays )
static

initializes rays data structure

Parameters
 scip SCIP data structure rays rays data structure

Definition at line 573 of file nlhdlr_quadratic.c.

Referenced by createAndStoreSparseRays().

## ◆ createBoundRays()

 static SCIP_RETCODE createBoundRays ( SCIP * scip, RAYS ** rays, int size )
static

initializes rays data structure for bound rays

Parameters
 scip SCIP data structure rays rays data structure size number of rays to allocate

Definition at line 596 of file nlhdlr_quadratic.c.

References BMSclearMemory, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.

Referenced by findVertexAndGetRays().

## ◆ freeRays()

 static void freeRays ( SCIP * scip, RAYS ** rays )
static

frees rays data structure

Parameters
 scip SCIP data structure rays rays data structure

Definition at line 620 of file nlhdlr_quadratic.c.

References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.

Referenced by createAndStoreSparseRays(), and generateIntercut().

## ◆ insertRayEntry()

 static SCIP_RETCODE insertRayEntry ( SCIP * scip, RAYS * rays, SCIP_Real coef, int coefidx, int coefpos )
static

inserts entry to rays data structure; checks and resizes if more space is needed

Parameters
 scip SCIP data structure rays rays data structure coef coefficient to insert coefidx index of coefficient (conspos of var it corresponds to) coefpos where to insert coefficient

Definition at line 638 of file nlhdlr_quadratic.c.

Referenced by insertRayEntries().

## ◆ constructLPPos2ConsPosMap()

 static void constructLPPos2ConsPosMap ( SCIP_NLHDLREXPRDATA * nlhdlrexprdata, SCIP_VAR * auxvar, int * map )
static

constructs map between the lppos of a variables and its position in the constraint assuming the constraint variables are sorted as [quad vars, lin vars, aux var (if it exists)]

If a variable doesn't appear in the constraint, then its position is -1.

Parameters
 nlhdlrexprdata nlhdlr expression data auxvar aux var of the expr map buffer to store the mapping

Definition at line 670 of file nlhdlr_quadratic.c.

Referenced by createAndStoreSparseRays().

## ◆ insertRayEntries()

 static SCIP_RETCODE insertRayEntries ( SCIP * scip, RAYS * rays, SCIP_Real * densetableaucols, int * rayentry2conspos, int raylength, int nray, int conspos, SCIP_Real factor, int * nnonz, SCIP_Bool * success )
static

inserts entries of factor * nray-th column of densetableaucols into rays data structure

Parameters
 scip SCIP data structure rays rays data structure densetableaucols column of the tableau in dense format rayentry2conspos map between rayentry and conspos of associated var raylength length of a tableau column nray which tableau column to insert conspos conspos of ray's nonbasic var in the cons; -1 if not in the cons factor factor to multiply each tableau col nnonz position to start adding the ray in rays and buffer to store nnonz success we can't separate if there is a nonzero ray with basis status ZERO

Definition at line 713 of file nlhdlr_quadratic.c.

Referenced by createAndStoreSparseRays().

## ◆ createAndStoreSparseRays()

 static SCIP_RETCODE createAndStoreSparseRays ( SCIP * scip, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, SCIP_VAR * auxvar, RAYS ** raysptr, SCIP_Bool * success )
static

stores rays in sparse form

The first rays correspond to the nonbasic variables and the last rays to the nonbasic slack variables.

More details: The LP tableau is of the form

basicvar_1 = ray1_1 nonbasicvar_1 + ... + raym_1 nonbasicvar_m
basicvar_2 = ray1_2 nonbasicvar_1 + ... + raym_2 nonbasicvar_m
...
basicvar_n = ray1_n nonbasicvar_1 + ... + raym_n nonbasicvar_m
nonbasicvar_1 = 1.0 nonbasicvar_1 + ... +    0.0 nonbasicvar_m
...
nonbasicvar_m = 0.0 nonbasicvar_1 + ... +    1.0 nonbasicvar_m


so rayk = (rayk_1, ... rayk_n, e_k) We store the entries of the rays associated to the variables present in the quadratic expr. We do not store zero rays.

Also, we store the rays as if every nonbasic variable was at lower (so that all rays moves to infinity) Since the tableau is:

basicvar + Binv L (nonbasic_lower - lb) + Binv U (nonbasic_upper - ub) = basicvar_sol


then:

basicvar = basicvar_sol - Binv L (nonbasic_lower - lb) + Binv U (ub - nonbasic_upper)


and so the entries of the rays associated with the basic variables are: rays_basicvars = [-BinvL, BinvU].

So we flip the sign of the rays associated to nonbasic vars at lower. In constrast, the nonbasic part of the ray has a 1.0 for nonbasic at lower and a -1.0 for nonbasic at upper, i.e. nonbasic_lower = lb + 1.0(nonbasic_lower - lb) and nonbasic_upper = ub - 1.0(ub - nonbasic_upper)

Parameters
 scip SCIP data structure nlhdlrexprdata nlhdlr expression data auxvar aux var of expr or NULL if not needed (e.g. separating real cons) raysptr buffer to store rays datastructure success we can't separate if there is a var with basis status ZERO

Definition at line 837 of file nlhdlr_quadratic.c.

Referenced by generateIntercut().

## ◆ intercutsComputeCommonQuantities()

 static SCIP_RETCODE intercutsComputeCommonQuantities ( SCIP * scip, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, SCIP_VAR * auxvar, SCIP_Real sidefactor, SCIP_SOL * sol, SCIP_Real * vb, SCIP_Real * vzlp, SCIP_Real * wcoefs, SCIP_Real * wzlp, SCIP_Real * kappa )
static

compute quantities for intersection cuts

Assume the quadratic is stored as

$q(z) = z_q^T Q z_q + b_q^T z_q + b_l z_l + c - z_a$

where:

• $$z_q$$ are the quadratic vars
• $$z_l$$ are the linear vars
• $$z_a$$ is the aux var if it exists

We can rewrite it as

$\Vert x(z)\Vert^2 - \Vert y\Vert^2 + w(z) + \kappa \leq 0.$

To do this transformation and later to compute the actual cut we need to compute and store some quantities. Let

• $$I_0$$, $$I_+$$, and $$I_-$$ be the index set of zero, positive, and negative eigenvalues, respectively
• $$v_i$$ be the i-th eigenvector of $$Q$$
• $$zlp$$ be the lp value of the variables $$z$$

The quantities we need are:

• $$vb_i = v_i^T b$$ for $$i \in I_+ \cup I_-$$
• $$vzlp_i = v_i^T zlp_q$$ for $$i \in I_+ \cup I_-$$
• $$\kappa = c - 1/4 \sum_{i \in I_+ \cup I_-} (v_i^T b_q)^2 / eigval_i$$
• $$w(z) = (\sum_{i \in I_0} v_i^T b_q v_i^T) z_q + b_l^T z_l - z_a$$
• $$w(zlp)$$
Returns
$$\kappa$$ and the vector $$\sum_{i \in I_0} v_i^T b_q v_i^T$$
Note
if the constraint is q(z) ≤ rhs, then the constant when writing the constraint as quad ≤ 0 is c - rhs.
if the quadratic constraint we are separating is q(z) ≥ lhs, then we multiply by -1. In practice, what changes is
• the sign of the eigenvalues
• the sign of $$b_q$$ and $$b_l$$
• the sign of the coefficient of the auxvar (if it exists)
• the constant of the quadratic written as quad ≤ 0 is lhs - c
The eigenvectors do not change sign!
Parameters
 scip SCIP data structure nlhdlrexprdata nlhdlr expression data auxvar aux var of expr or NULL if not needed (e.g. separating real cons) sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise sol solution to separate vb buffer to store $$v_i^T b$$ for $$i \in I_+ \cup I_-$$ vzlp buffer to store $$v_i^T zlp_q$$ for $$i \in I_+ \cup I_-$$ wcoefs buffer to store the coefs of quad vars of w wzlp pointer to store the value of w at zlp kappa pointer to store the value of kappa

Definition at line 1036 of file nlhdlr_quadratic.c.

Referenced by generateIntercut().

## ◆ computeEigenvecDotRay()

 static SCIP_Real computeEigenvecDotRay ( SCIP_Real * eigenvec, int nquadvars, SCIP_Real * raycoefs, int * rayidx, int raynnonz )
static

computes eigenvec^T ray

Parameters
 eigenvec eigenvector nquadvars number of quadratic vars (length of eigenvec) raycoefs coefficients of ray rayidx index of consvar the ray coef is associated to raynnonz length of raycoefs and rayidx

Definition at line 1151 of file nlhdlr_quadratic.c.

References SCIP_Real.

Referenced by computeRestrictionToRay().

## ◆ computeWRayLinear()

 static SCIP_Real computeWRayLinear ( SCIP_NLHDLREXPRDATA * nlhdlrexprdata, SCIP_Real sidefactor, SCIP_Real * raycoefs, int * rayidx, int raynnonz )
static

computes linear part of evaluation of w(ray): $$b_l^T ray_l - ray_a$$

Note
we can know whether the auxiliary variable appears by the entries of the ray
Parameters
 nlhdlrexprdata nlhdlr expression data sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise raycoefs coefficients of ray rayidx ray coef[i] affects var at pos rayidx[i] in consvar raynnonz length of raycoefs and rayidx

Definition at line 1180 of file nlhdlr_quadratic.c.

Referenced by computeRestrictionToRay().

## ◆ computeRestrictionToRay()

 static SCIP_RETCODE computeRestrictionToRay ( SCIP * scip, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real * raycoefs, int * rayidx, int raynnonz, SCIP_Real * vb, SCIP_Real * vzlp, SCIP_Real * wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real * coefs1234a, SCIP_Real * coefs4b, SCIP_Real * coefscondition, SCIP_Bool * success )
static

calculate coefficients of restriction of the function to given ray.

The restriction of the function representing the maximal S-free set to zlp + t * ray has the form SQRT(A t^2 + B t + C) - (D t + E) for cases 1, 2, and 3. For case 4 it is a piecewise defined function and each piece is of the aforementioned form.

This function computes the coefficients A, B, C, D, E for the given ray. In case 4, it computes the coefficients for both pieces, in addition to coefficients needed to evaluate the condition in the piecewise definition of the function.

The parameter iscase4 tells the function if it is case 4 or not.

Parameters
 scip SCIP data structure nlhdlrexprdata nlhdlr expression data sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 raycoefs coefficients of ray rayidx index of consvar the ray coef is associated to raynnonz length of raycoefs and rayidx vb array containing $$v_i^T b$$ for $$i \in I_+ \cup I_-$$ vzlp array containing $$v_i^T zlp_q$$ for $$i \in I_+ \cup I_-$$ wcoefs coefficients of w for the qud vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa coefs1234a buffer to store A, B, C, D, and E of cases 1, 2, 3, or 4a coefs4b buffer to store A, B, C, D, and E of case 4b (or NULL if not needed) coefscondition buffer to store data to evaluate condition to decide case 4a or 4b success did we successfully compute the coefficients?

Definition at line 1246 of file nlhdlr_quadratic.c.

Referenced by computeIntercut(), and rayInRecessionCone().

## ◆ evalPhiAtRay()

 static SCIP_Real evalPhiAtRay ( SCIP_Real t, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e )
static

returns phi(zlp + t * ray) = SQRT(A t^2 + B t + C) - (D t + E)

Parameters
 t argument of phi restricted to ray a value of A b value of B c value of C d value of D e value of E

Definition at line 1478 of file nlhdlr_quadratic.c.

Referenced by computeIntersectionPoint(), computeRoot(), and doBinarySearch().

## ◆ isCase4a()

 static SCIP_Real isCase4a ( SCIP_Real tsol, SCIP_Real * coefs4a, SCIP_Real * coefscondition )
static

checks whether case 4a applies

The condition for being in case 4a is

$-\lambda_{r+1} \Vert \hat y(zlp + tsol\, ray)\Vert + \hat y_{s+1}(zlp + tsol\, ray) \leq 0$

This reduces to

$-num(\hat x_{r+1}(zlp)) \sqrt{A t^2 + B t + C} / E + w(ray) \cdot t + num(\hat y_{s+1}(zlp)) \leq 0$

where num is the numerator.

Parameters
 tsol t in the above formula coefs4a coefficients A, B, C, D, and E of case 4a coefscondition extra coefficients needed for the evaluation of the condition: $$num(\hat x_{r+1}(zlp)) / E$$; $$w(ray)$$; $$num(\hat y_{s+1}(zlp))$$

Definition at line 1542 of file nlhdlr_quadratic.c.

Referenced by computeIntersectionPoint().

## ◆ doBinarySearch()

 static void doBinarySearch ( SCIP * scip, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e, SCIP_Real * sol )
static

helper function of computeRoot: we want phi to be ≤ 0

Parameters
 scip SCIP data structure a value of A b value of B c value of C d value of D e value of E sol buffer to store solution; also gives initial point

Definition at line 1555 of file nlhdlr_quadratic.c.

References BINSEARCH_MAXITERS, evalPhiAtRay(), SCIP_Real, SCIPisFeasEQ(), and SCIPisFeasZero().

Referenced by computeRoot().

## ◆ computeRoot()

 static SCIP_Real computeRoot ( SCIP * scip, SCIP_Real * coefs )
static

finds smallest positive root phi by finding the smallest positive root of (A - D^2) t^2 + (B - 2 D*E) t + (C - E^2) = 0

However, we are conservative and want a solution such that phi is negative, but close to 0. Thus, we correct the result with a binary search.

Parameters
 scip SCIP data structure coefs value of A

Definition at line 1600 of file nlhdlr_quadratic.c.

Referenced by computeIntersectionPoint().

## ◆ computeIntersectionPoint()

 static SCIP_Real computeIntersectionPoint ( SCIP * scip, SCIP_NLHDLRDATA * nlhdlrdata, SCIP_Bool iscase4, SCIP_Real * coefs1234a, SCIP_Real * coefs4b, SCIP_Real * coefscondition )
static

The maximal S-free set is $$\gamma(z) \leq 0$$; we find the intersection point of the ray ray starting from zlp with the boundary of the S-free set. That is, we find $$t \geq 0$$ such that $$\gamma(zlp + t \cdot \text{ray}) = 0$$.

In cases 1,2, and 3, gamma is of the form

$\gamma(zlp + t \cdot \text{ray}) = \sqrt{A t^2 + B t + C} - (D t + E)$

In the case 4 gamma is of the form

$\gamma(zlp + t \cdot \text{ray}) = \begin{cases} \sqrt{A t^2 + B t + C} - (D t + E), & \text{if some condition holds}, \\ \sqrt{A' t^2 + B' t + C'} - (D' t + E'), & \text{otherwise.} \end{cases}$

It can be shown (given the special properties of $$\gamma$$) that the smallest positive root of each function of the form $$\sqrt{a t^2 + b t + c} - (d t + e)$$ is the same as the smallest positive root of the quadratic equation:

\begin{align} & \sqrt{a t^2 + b t + c} - (d t + e)) (\sqrt{a t^2 + b t + c} + (d t + e)) = 0 \\ \Leftrightarrow & (a - d^2) t^2 + (b - 2 d\,e) t + (c - e^2) = 0 \end{align}

So, in cases 1, 2, and 3, this function just returns the solution of the above equation. In case 4, it first solves the equation assuming we are in the first piece. If there is no solution, then the second piece can't have a solution (first piece ≥ second piece for all t) Then we check if the solution satisfies the condition. If it doesn't then we solve the equation for the second piece. If it has a solution, then it has to be the solution.

Parameters
 scip SCIP data structure nlhdlrdata nlhdlr data iscase4 whether we are in case 4 or not coefs1234a values of A, B, C, D, and E of cases 1, 2, 3, or 4a coefs4b values of A, B, C, D, and E of case 4b coefscondition values needed to evaluate condition of case 4

Definition at line 1700 of file nlhdlr_quadratic.c.

References computeRoot(), evalPhiAtRay(), isCase4a(), MAX, NULL, SCIP_Real, SCIPinfoMessage(), and SCIPisInfinity().

Referenced by computeIntercut(), and rayInRecessionCone().

## ◆ areCoefsNumericsGood()

 static SCIP_Bool areCoefsNumericsGood ( SCIP * scip, SCIP_NLHDLRDATA * nlhdlrdata, SCIP_Real * coefs1234a, SCIP_Real * coefs4b, SCIP_Bool iscase4 )
static

checks if numerics of the coefficients are not too bad

Parameters
 scip SCIP data structure nlhdlrdata nlhdlr data coefs1234a coefficients for case 1-3 and 4a coefs4b coefficients for case 4b iscase4 whether we are in case 4

Definition at line 1767 of file nlhdlr_quadratic.c.

References FALSE, INTERLOG, REALABS, SCIP_Real, SCIPinfinity(), SCIPisHugeValue(), and TRUE.

Referenced by computeIntercut().

## ◆ computeIntercut()

 static SCIP_RETCODE computeIntercut ( SCIP * scip, SCIP_NLHDLRDATA * nlhdlrdata, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, RAYS * rays, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real * vb, SCIP_Real * vzlp, SCIP_Real * wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_ROWPREP * rowprep, SCIP_Real * interpoints, SCIP_SOL * sol, SCIP_Bool * success )
static

computes intersection cut cuts off sol (because solution sol violates the quadratic constraint cons) and stores it in rowprep. Here, we don't use any strengthening.

Parameters
 scip SCIP data structure nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data rays rays sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 vb array containing $$v_i^T b$$ for $$i \in I_+ \cup I_-$$ vzlp array containing $$v_i^T zlp_q$$ for $$i \in I_+ \cup I_-$$ wcoefs coefficients of w for the qud vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa rowprep rowprep for the generated cut interpoints array to store intersection points for all rays or NULL if nothing needs to be stored sol solution we want to separate success if a cut candidate could be computed

Definition at line 1843 of file nlhdlr_quadratic.c.

Referenced by computeStrengthenedIntercut(), and generateIntercut().

## ◆ combineRays()

 static void combineRays ( SCIP_Real * raycoefs1, int * rayidx1, int raynnonz1, SCIP_Real * raycoefs2, int * rayidx2, int raynnonz2, SCIP_Real * newraycoefs, int * newrayidx, int * newraynnonz, SCIP_Real coef1, SCIP_Real coef2 )
static

combine ray 1 and 2 to obtain new ray coef1 * ray1 - coef2 * ray2 in sparse format

Parameters
 raycoefs1 coefficients of ray 1 rayidx1 index of consvar of the ray 1 coef is associated to raynnonz1 length of raycoefs1 and rayidx1 raycoefs2 coefficients of ray 2 rayidx2 index of consvar of the ray 2 coef is associated to raynnonz2 length of raycoefs2 and rayidx2 newraycoefs coefficients of combined ray newrayidx index of consvar of the combined ray coef is associated to newraynnonz pointer to length of newraycoefs and newrayidx coef1 coef of ray 1 coef2 coef of ray 2

Definition at line 1947 of file nlhdlr_quadratic.c.

Referenced by rayInRecessionCone().

## ◆ raysAreDependent()

 static SCIP_Bool raysAreDependent ( SCIP * scip, SCIP_Real * raycoefs1, int * rayidx1, int raynnonz1, SCIP_Real * raycoefs2, int * rayidx2, int raynnonz2, SCIP_Real * coef )
static

checks if two rays are linearly dependent

Parameters
 scip SCIP data structure raycoefs1 coefficients of ray 1 rayidx1 index of consvar of the ray 1 coef is associated to raynnonz1 length of raycoefs1 and rayidx1 raycoefs2 coefficients of ray 2 rayidx2 index of consvar of the ray 2 coef is associated to raynnonz2 length of raycoefs2 and rayidx2 coef pointer to store coef (s.t. r1 = coef * r2) in case rays are dependent

Definition at line 2004 of file nlhdlr_quadratic.c.

References FALSE, SCIPisEQ(), SCIPisZero(), and TRUE.

Referenced by findRho().

## ◆ rayInRecessionCone()

 static SCIP_RETCODE rayInRecessionCone ( SCIP * scip, SCIP_NLHDLRDATA * nlhdlrdata, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, RAYS * rays, int j, int i, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real * vb, SCIP_Real * vzlp, SCIP_Real * wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real alpha, SCIP_Bool * inreccone, SCIP_Bool * success )
static

checks if the ray alpha * ray_i + (1 - alpha) * ray_j is in the recession cone of the S-free set. To do so, we check if phi restricted to the ray has a positive root.

Parameters
 scip SCIP data structure nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data rays rays j index of current ray in recession cone i index of current ray not in recession cone sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 vb array containing $$v_i^T b$$ for $$i \in I_+ \cup I_-$$ vzlp array containing $$v_i^T zlp_q$$ for $$i \in I_+ \cup I_-$$ wcoefs coefficients of w for the quad vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa alpha coef for combining the two rays inreccone pointer to store whether the ray is in the recession cone or not success Did numerical troubles occur?

Definition at line 2053 of file nlhdlr_quadratic.c.

Referenced by findRho().

## ◆ findRho()

 static SCIP_RETCODE findRho ( SCIP * scip, SCIP_NLHDLRDATA * nlhdlrdata, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, RAYS * rays, int idx, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real * vb, SCIP_Real * vzlp, SCIP_Real * wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_Real * interpoints, SCIP_Real * rho, SCIP_Bool * success )
static

finds the smallest negative steplength for the current ray r_idx such that the combination of r_idx with all rays not in the recession cone is in the recession cone

Parameters
 scip SCIP data structure nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data rays rays idx index of current ray we want to find rho for sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 vb array containing $$v_i^T b$$ for $$i \in I_+ \cup I_-$$ vzlp array containing $$v_i^T zlp_q$$ for $$i \in I_+ \cup I_-$$ wcoefs coefficients of w for the quad vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa interpoints array to store intersection points for all rays or NULL if nothing needs to be stored rho pointer to store the optimal rho success could we successfully find the right rho?

Definition at line 2122 of file nlhdlr_quadratic.c.

Referenced by computeStrengthenedIntercut().

## ◆ computeStrengthenedIntercut()

 static SCIP_RETCODE computeStrengthenedIntercut ( SCIP * scip, SCIP_NLHDLRDATA * nlhdlrdata, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, RAYS * rays, SCIP_Real sidefactor, SCIP_Bool iscase4, SCIP_Real * vb, SCIP_Real * vzlp, SCIP_Real * wcoefs, SCIP_Real wzlp, SCIP_Real kappa, SCIP_ROWPREP * rowprep, SCIP_SOL * sol, SCIP_Bool * success, SCIP_Bool * strengthsuccess )
static

computes intersection cut using negative edge extension to strengthen rays that do not intersect (i.e., rays in the recession cone)

Parameters
 scip SCIP data structure nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data rays rays sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise iscase4 whether we are in case 4 vb array containing $$v_i^T b$$ for $$i \in I_+ \cup I_-$$ vzlp array containing $$v_i^T zlp_q$$ for $$i \in I_+ \cup I_-$$ wcoefs coefficients of w for the qud vars or NULL if w is 0 wzlp value of w at zlp kappa value of kappa rowprep rowprep for the generated cut sol solution to separate success if a cut candidate could be computed strengthsuccess if strengthening was successfully applied

Definition at line 2241 of file nlhdlr_quadratic.c.

Referenced by generateIntercut().

## ◆ setVarToNearestBound()

 static SCIP_RETCODE setVarToNearestBound ( SCIP * scip, SCIP_SOL * sol, SCIP_SOL * vertex, SCIP_VAR * var, SCIP_Real * factor, SCIP_Bool * success )
static

sets variable in solution "vertex" to its nearest bound

Parameters
 scip SCIP data structure sol solution to separate vertex new solution to separate var var we want to find nearest bound to factor is vertex for current var at lower or upper? success TRUE if no variable is bounded

Definition at line 2357 of file nlhdlr_quadratic.c.

Referenced by findVertexAndGetRays().

## ◆ findVertexAndGetRays()

 static SCIP_RETCODE findVertexAndGetRays ( SCIP * scip, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, SCIP_SOL * sol, SCIP_SOL * vertex, SCIP_VAR * auxvar, RAYS ** raysptr, SCIP_Bool * success )
static

This function finds vertex (w.r.t. bounds of variables appearing in the quadratic) that is closest to the current solution we want to separate.

Furthermore, we store the rays corresponding to the unit vectors, i.e.,

• if $$x_i$$ is at its lower bound in vertex –> $$r_i = e_i$$
• if $$x_i$$ is at its upper bound in vertex –> $$r_i = -e_i$$
Parameters
 scip SCIP data structure nlhdlrexprdata nlhdlr expression data sol solution to separate vertex new 'vertex' (w.r.t. bounds) solution to separate auxvar aux var of expr or NULL if not needed (e.g. separating real cons) raysptr pointer to new bound rays success TRUE if no variable is unbounded

Definition at line 2402 of file nlhdlr_quadratic.c.

Referenced by generateIntercut().

 static SCIP_Bool isQuadConsViolated ( SCIP * scip, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, SCIP_VAR * auxvar, SCIP_SOL * sol, SCIP_Real sidefactor )
static

checks if the quadratic constraint is violated by sol

Parameters
 scip SCIP data structure nlhdlrexprdata nlhdlr expression data auxvar aux var of expr or NULL if not needed (e.g. separating real cons) sol solution to check feasibility for sidefactor 1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise

Definition at line 2485 of file nlhdlr_quadratic.c.

Referenced by generateIntercut().

## ◆ generateIntercut()

 static SCIP_RETCODE generateIntercut ( SCIP * scip, SCIP_EXPR * expr, SCIP_NLHDLRDATA * nlhdlrdata, SCIP_NLHDLREXPRDATA * nlhdlrexprdata, SCIP_CONS * cons, SCIP_SOL * sol, SCIP_ROWPREP * rowprep, SCIP_Bool overestimate, SCIP_Bool * success )
static

generates intersection cut that cuts off sol (which violates the quadratic constraint cons)

Parameters
 scip SCIP data structure expr expr nlhdlrdata nlhdlr data nlhdlrexprdata nlhdlr expression data cons violated constraint that contains expr sol solution to separate rowprep rowprep for the generated cut overestimate TRUE if viol cons is q(z) ≥ lhs; FALSE if q(z) ≤ rhs success whether separation was successfull or not

Definition at line 2569 of file nlhdlr_quadratic.c.

Referenced by SCIP_DECL_NLHDLRENFO().

## ◆ isPropagable()

 static SCIP_Bool isPropagable ( SCIP_EXPR * qexpr )
static

returns whether a quadratic form is "propagable"

It is propagable, if a variable (aka child expr) appears at least twice, which is the case if at least two of the following hold:

• it appears as a linear term (coef*expr)
• it appears as a square term (coef*expr^2)
• it appears in a bilinear term
• it appears in another bilinear term
Parameters

Definition at line 2735 of file nlhdlr_quadratic.c.

Referenced by SCIP_DECL_NLHDLRDETECT().

## ◆ isPropagableTerm()

 static SCIP_Bool isPropagableTerm ( SCIP_EXPR * qexpr, int idx )
static

returns whether a quadratic term is "propagable"

A term is propagable, if its variable (aka child expr) appears at least twice, which is the case if at least two of the following hold:

• it appears as a linear term (coef*expr)
• it appears as a square term (coef*expr^2)
• it appears in a bilinear term
• it appears in another bilinear term
Parameters

Definition at line 2768 of file nlhdlr_quadratic.c.

Referenced by SCIP_DECL_NLHDLRDETECT(), SCIP_DECL_NLHDLRINTEVAL(), and SCIP_DECL_NLHDLRREVERSEPROP().

 static SCIP_RETCODE propagateBoundsQuadExpr ( SCIP * scip, SCIP_EXPR * expr, SCIP_Real sqrcoef, SCIP_INTERVAL b, SCIP_INTERVAL rhs, SCIP_Bool * infeasible, int * nreductions )
static

solves a quadratic equation $$a\, \text{expr}^2 + b\, \text{expr} \in \text{rhs}$$ (with $$b$$ an interval) and reduces bounds on expr or deduces infeasibility if possible

Parameters
 scip SCIP data structure expr expression for which to solve sqrcoef square coefficient b interval acting as linear coefficient rhs interval acting as rhs infeasible buffer to store if propagation produced infeasibility nreductions buffer to store the number of interval reductions

Definition at line 2786 of file nlhdlr_quadratic.c.

Referenced by SCIP_DECL_NLHDLRREVERSEPROP().

## ◆ propagateBoundsLinExpr()

 static SCIP_RETCODE propagateBoundsLinExpr ( SCIP * scip, SCIP_EXPR * expr, SCIP_Real b, SCIP_INTERVAL rhs, SCIP_Bool * infeasible, int * nreductions )
static

solves a linear equation $$b\, \text{expr} \in \text{rhs}$$ (with $$b$$ a scalar) and reduces bounds on expr or deduces infeasibility if possible

Parameters
 scip SCIP data structure expr expression for which to solve b linear coefficient rhs interval acting as rhs infeasible buffer to store if propagation produced infeasibility nreductions buffer to store the number of interval reductions

Definition at line 2837 of file nlhdlr_quadratic.c.

Referenced by SCIP_DECL_NLHDLRREVERSEPROP().

## ◆ computeMaxBoundaryForBilinearProp()

 static SCIP_Real computeMaxBoundaryForBilinearProp ( SCIP_Real a, SCIP_Real c, SCIP_Real x1, SCIP_Real x2 )
static

returns max of a/x - c*x for x in {x1, x2} with x1, x2 > 0

Parameters
 a coefficient a c coefficient c x1 coefficient x1 > 0 x2 coefficient x2 > 0

Definition at line 2873 of file nlhdlr_quadratic.c.

Referenced by computeMaxForBilinearProp().

## ◆ computeMaxForBilinearProp()

 static SCIP_Real computeMaxForBilinearProp ( SCIP_Real a, SCIP_Real c, SCIP_INTERVAL dom )
static

returns max of a/x - c*x for x in dom; it assumes that dom is contained in (0, +inf)

Parameters
 a coefficient a c coefficient c dom domain of x

Definition at line 2901 of file nlhdlr_quadratic.c.

Referenced by computeRangeForBilinearProp().

## ◆ computeRangeForBilinearProp()

 static void computeRangeForBilinearProp ( SCIP_INTERVAL exprdom, SCIP_Real coef, SCIP_INTERVAL rhs, SCIP_INTERVAL * range )
static

computes the range of rhs/x - coef * x for x in exprdom; this is used for the propagation of bilinear terms

If 0 is in the exprdom, we set range to $$\mathbb{R}$$ (even though this is not quite correct, it is correct for the intended use of the function). TODO: maybe check before calling it whether 0 is in the domain and then just avoid calling it

If rhs is [A,B] and x > 0, then we want the min of A/x - coef*x and max of B/x - coef*x for x in [exprdom]. If rhs is [A,B] and x < 0, then we want the min of B/x - coef*x and max of A/x - coef*x for x in [exprdom]. However, this is the same as min of -B/x + coef*x and max of -A/x + coef*x for x in -[exprdom]. Thus, we can always reduce to x > 0 by multiplying [exprdom], rhs, and coef by -1.

Parameters
 exprdom expression for which to solve coef expression for which to solve rhs rhs used for computation range storage for the resulting range

Definition at line 2968 of file nlhdlr_quadratic.c.

Referenced by SCIP_DECL_NLHDLRREVERSEPROP().

## ◆ reversePropagateLinearExpr()

 static SCIP_RETCODE reversePropagateLinearExpr ( SCIP * scip, SCIP_EXPR ** linexprs, int nlinexprs, SCIP_Real * lincoefs, SCIP_Real constant, SCIP_INTERVAL rhs, SCIP_Bool * infeasible, int * nreductions )
static

reverse propagates coef_i expr_i + constant in rhs

Parameters
 scip SCIP data structure linexprs linear expressions nlinexprs number of linear expressions lincoefs coefficients of linear expressions constant constant rhs rhs infeasible buffer to store whether an exps' bounds were propagated to an empty interval nreductions buffer to store the number of interval reductions of all exprs

Definition at line 3003 of file nlhdlr_quadratic.c.

Referenced by SCIP_DECL_NLHDLRREVERSEPROP().

## ◆ SCIP_DECL_NLHDLRFREEEXPRDATA()

static

callback to free expression specific data

Definition at line 3053 of file nlhdlr_quadratic.c.

## ◆ SCIP_DECL_NLHDLRDETECT()

static

callback to detect structure in expression tree

• it is a product expression of two expressions, or
• it is power expression of an expression with exponent 2.0.

We define a propagable quadratic expression as a quadratic expression whose termwise propagation does not yield the best propagation. In other words, is a quadratic expression that suffers from the dependency problem.

Specifically, a propagable quadratic expression is a sum expression such that there is at least one expr that appears at least twice (because of simplification, this means it appears in a quadratic terms and somewhere else). For example: $$x^2 + y^2$$ is not a propagable quadratic expression; $$x^2 + x$$ is a propagable quadratic expression; $$x^2 + x y$$ is also a propagable quadratic expression

Furthermore, we distinguish between propagable and non-propagable terms. A term is propagable if any of the expressions involved in it appear somewhere else. For example, $$xy + z^2 + z$$ is a propagable quadratic, the term $$xy$$ is non-propagable, and $$z^2$$ is propagable. For propagation, non-propagable terms are handled as if they were linear terms, that is, we do not use the activity of $$x$$ and $$y$$ to compute the activity of $$xy$$ but rather we use directly the activity of $$xy$$. Similarly, we do not backward propagate to $$x$$ and $$y$$ (the product expr handler will do this), but we backward propagate to $$x*y$$. More technically, we register $$xy$$ for its activity usage, rather than $$x$$ and $$y$$.

For propagation, we store the quadratic in our data structure in the following way: We count how often a variable appears. Then, a bilinear product expr_i * expr_j is stored as expr_i * expr_j if # expr_i appears > # expr_j appears. When # expr_i appears = # expr_j appears, it then it will be stored as expr_i * expr_j if and only if expr_i < expr_j, where '<' is the expression order (see Ordering Rules in scip_expr.h). Heuristically, this should be useful for propagation. The intuition is that by factoring out the variable that appears most often we should be able to take care of the dependency problem better.

Simple convex quadratics like $$x^2 + y^2$$ are ignored since the default nlhdlr will take care of them.

Note
The expression needs to be simplified (in particular, it is assumed to be sorted).
Common subexpressions are also assumed to have been identified, the hashing will fail otherwise!

Sorted implies that:

• expr < expr^2: bases are the same, but exponent 1 < 2
• expr < expr * other_expr: u*v < w holds if and only if v < w (OR8), but here w = u < v, since expr comes before other_expr in the product
• expr < other_expr * expr: u*v < w holds if and only if v < w (OR8), but here v = w

Thus, if we see somebody twice, it is a propagable quadratic.

It also implies that

• expr^2 < expr * other_expr
• other_expr * expr < expr^2

It also implies that x^-2 < x^-1, but since, so far, we do not interpret x^-2 as (x^-1)^2, it is not a problem.

Definition at line 3118 of file nlhdlr_quadratic.c.

## ◆ SCIP_DECL_NLHDLREVALAUX()

static

nonlinear handler auxiliary evaluation callback

Definition at line 3391 of file nlhdlr_quadratic.c.

static

## ◆ SCIP_DECL_NLHDLRINTEVAL()

static

nonlinear handler forward propagation callback

This method should solve the problem

   max/min quad expression over box constraints


However, this problem is difficult so we are satisfied with a proxy. Interval arithmetic suffices when no variable appears twice, however this is seldom the case, so we try to take care of the dependency problem to some extent: Let $$P_l = \{i : \text{expr}_l \text{expr}_i \,\text{is a bilinear expr}\}$$.

1. partition the quadratic expression as sum of quadratic functions $$\sum_l q_l$$ where $$q_l = a_l \text{expr}_l^2 + c_l \text{expr}_l + \sum_{i \in P_l} b_{il} \text{expr}_i \text{expr}_l$$
2. build interval quadratic functions, i.e., $$a x^2 + b x$$ where $$b$$ is an interval, i.e., $$a_l \text{expr}_l^2 + [\sum_{i \in P_l} b_{il} \text{expr}_i + c_l] \text{expr}_l$$
3. compute $$\min/\max \{ a x^2 + b x : x \in [x] \}$$ for each interval quadratic, i.e., $$\min/\max a_l \text{expr}_l^2 + \text{expr}_l [\sum_{i \in P_l} b_{il} \text{expr}_i + c_l] : \text{expr}_l \in [\text{expr}_l]$$

Notes:

1. The $$l$$-th quadratic expr (expressions that appear quadratically) is associated with $$q_l$$.
2. nlhdlrdata->quadactivities[l] is the activity of $$q_l$$ as computed in the description above.
3. The $$q_l$$ of a quadratic term might be empty, in which case nlhdlrdata->quadactivities[l] is [0,0].
For example, consider $$x^2 + xy$$. There are two quadratic expressions, $$x$$ and $$y$$. The $$q$$ associated to $$x$$ is $$x^2 + xy$$, while the $$q$$ associated to $$y$$ is empty. Thus, nlhdlrdata->quadactivities[1] is [0,0] in this case. The logic is to avoid considering the term $$xy$$ twice.
Note
The order matters! If $$\text{expr}_i\, \text{expr}_l$$ is a term in the quadratic, then $$i$$ is not in $$P_l$$

Definition at line 3703 of file nlhdlr_quadratic.c.

## ◆ SCIP_DECL_NLHDLRREVERSEPROP()

static

nonlinear handler reverse propagation callback

Note
the implemented technique is a proxy for solving the problem min/max{ x_i : quad expr in [quad expr] } and as such can be improved.

Definition at line 3965 of file nlhdlr_quadratic.c.

## ◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

static

callback to free data of handler

Definition at line 4279 of file nlhdlr_quadratic.c.

References NULL, SCIP_OKAY, and SCIPfreeBlockMemory.