Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

nonlinear handler to handle quadratic expressions

Author
Felipe Serrano
Antonia Chmiela

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.

Definition in file nlhdlr_quadratic.c.

Go to the source code of this file.

Data Structures

struct  Rays
 

Macros

#define INTERLOG(x)
 
#define NLHDLR_NAME   "quadratic"
 
#define NLHDLR_DESC   "handler for quadratic expressions"
 
#define NLHDLR_DETECTPRIORITY   1
 
#define NLHDLR_ENFOPRIORITY   100
 
#define TABLE_NAME_QUADRATIC   "nlhdlr_quadratic"
 
#define TABLE_DESC_QUADRATIC   "quadratic nlhdlr statistics table"
 
#define TABLE_POSITION_QUADRATIC   14700
 
#define TABLE_EARLIEST_STAGE_QUADRATIC   SCIP_STAGE_TRANSFORMED
 
#define INTERCUTS_MINVIOL   1e-4
 
#define DEFAULT_USEINTERCUTS   FALSE
 
#define DEFAULT_USESTRENGTH   FALSE
 
#define DEFAULT_USEMONOIDAL   TRUE
 
#define DEFAULT_USEMINREP   TRUE
 
#define DEFAULT_USEBOUNDS   FALSE
 
#define BINSEARCH_MAXITERS   120
 
#define DEFAULT_NCUTSROOT   20
 
#define DEFAULT_NCUTS   2
 

Typedefs

typedef struct Rays RAYS
 

Functions

static SCIP_DECL_TABLEOUTPUT (tableOutputQuadratic)
 
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 void computeVApexAndVRay (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real *apex, SCIP_Real *raycoefs, int *rayidx, int raynnonz, SCIP_Real *vapex, SCIP_Real *vray)
 
static SCIP_RETCODE computeRestrictionToLine (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real sidefactor, SCIP_Real *raycoefs, int *rayidx, int raynnonz, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real kappa, SCIP_Real *apex, SCIP_Real *coefs2, SCIP_Bool *success)
 
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 computeMonoidalQuadCoefs (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *vapex, SCIP_Real *vray, SCIP_Real kappa, SCIP_Real sidefactor, SCIP_Real *a, SCIP_Real *b, SCIP_Real *c)
 
static SCIP_Bool isRayInStrip (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *vapex, SCIP_Real *vray, SCIP_Real kappa, SCIP_Real sidefactor, SCIP_Real cutcoef)
 
static SCIP_Real findMonoidalQuadRoot (SCIP *scip, SCIP_Real a, SCIP_Real b, SCIP_Real c)
 
static void computeApex (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real kappa, SCIP_Real sidefactor, SCIP_Real *apex, SCIP_Bool *success)
 
static SCIP_RETCODE computeMonoidalStrengthCoef (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, int lppos, SCIP_Real *raycoefs, int *rayidx, int raynnonz, SCIP_Real *vb, SCIP_Real *vzlp, SCIP_Real *wcoefs, SCIP_Real kappa, SCIP_Real *apex, SCIP_Real sidefactor, SCIP_Real *cutcoef, SCIP_Bool *success)
 
static void sparsifyIntercut (SCIP *scip, SCIP_ROWPREP *rowprep)
 
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)
 
static SCIP_DECL_NLHDLRFREEEXPRDATA (nlhdlrFreeexprdataQuadratic)
 
static SCIP_DECL_NLHDLRDETECT (nlhdlrDetectQuadratic)
 
static SCIP_DECL_NLHDLREVALAUX (nlhdlrEvalauxQuadratic)
 
static SCIP_DECL_NLHDLRENFO (nlhdlrEnfoQuadratic)
 
static SCIP_DECL_NLHDLRINTEVAL (nlhdlrIntevalQuadratic)
 
static SCIP_DECL_NLHDLRREVERSEPROP (nlhdlrReversepropQuadratic)
 
static SCIP_DECL_NLHDLRFREEHDLRDATA (nlhdlrFreehdlrdataQuadratic)
 
static SCIP_DECL_NLHDLRCOPYHDLR (nlhdlrCopyhdlrQuadratic)
 
SCIP_RETCODE SCIPincludeNlhdlrQuadratic (SCIP *scip)
 

Macro Definition Documentation

◆ INTERLOG

◆ NLHDLR_NAME

#define NLHDLR_NAME   "quadratic"

◆ NLHDLR_DESC

#define NLHDLR_DESC   "handler for quadratic expressions"

Definition at line 66 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ NLHDLR_DETECTPRIORITY

#define NLHDLR_DETECTPRIORITY   1

Definition at line 67 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ NLHDLR_ENFOPRIORITY

#define NLHDLR_ENFOPRIORITY   100

Definition at line 68 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ TABLE_NAME_QUADRATIC

#define TABLE_NAME_QUADRATIC   "nlhdlr_quadratic"

Definition at line 71 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ TABLE_DESC_QUADRATIC

#define TABLE_DESC_QUADRATIC   "quadratic nlhdlr statistics table"

Definition at line 72 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ TABLE_POSITION_QUADRATIC

#define TABLE_POSITION_QUADRATIC   14700

the position of the statistics table

Definition at line 73 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ TABLE_EARLIEST_STAGE_QUADRATIC

#define TABLE_EARLIEST_STAGE_QUADRATIC   SCIP_STAGE_TRANSFORMED

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

Definition at line 74 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ INTERCUTS_MINVIOL

#define INTERCUTS_MINVIOL   1e-4

Definition at line 77 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ DEFAULT_USEINTERCUTS

#define DEFAULT_USEINTERCUTS   FALSE

Definition at line 78 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ DEFAULT_USESTRENGTH

#define DEFAULT_USESTRENGTH   FALSE

Definition at line 79 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ DEFAULT_USEMONOIDAL

#define DEFAULT_USEMONOIDAL   TRUE

Definition at line 80 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ DEFAULT_USEMINREP

#define DEFAULT_USEMINREP   TRUE

Definition at line 81 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ DEFAULT_USEBOUNDS

#define DEFAULT_USEBOUNDS   FALSE

Definition at line 82 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ BINSEARCH_MAXITERS

#define BINSEARCH_MAXITERS   120

Definition at line 83 of file nlhdlr_quadratic.c.

Referenced by doBinarySearch(), findMonoidalQuadRoot(), and findRho().

◆ DEFAULT_NCUTSROOT

#define DEFAULT_NCUTSROOT   20

Definition at line 84 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

◆ DEFAULT_NCUTS

#define DEFAULT_NCUTS   2

Definition at line 85 of file nlhdlr_quadratic.c.

Referenced by SCIPincludeNlhdlrQuadratic().

Typedef Documentation

◆ RAYS

typedef struct Rays RAYS

Definition at line 175 of file nlhdlr_quadratic.c.

Function Documentation

◆ SCIP_DECL_TABLEOUTPUT()

static SCIP_DECL_TABLEOUTPUT ( tableOutputQuadratic  )
static

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

Definition at line 184 of file nlhdlr_quadratic.c.

References NLHDLR_NAME, NULL, SCIP_OKAY, SCIPfindConshdlr(), SCIPfindNlhdlrNonlinear(), SCIPinfoMessage(), and SCIPnlhdlrGetData().

◆ addColToCut()

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
scipSCIP data structure
rowpreprowprep to store intersection cut
solsolution to separate
cutcoefcut coefficient
colcolumn to add to rowprep

Definition at line 227 of file nlhdlr_quadratic.c.

References NULL, SCIP_BASESTAT_LOWER, SCIP_CALL, SCIP_OKAY, SCIPaddRowprepTerm(), SCIPcolGetBasisStatus(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPgetSolVal(), SCIPinfoMessage(), SCIProwprepAddConstant(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by computeIntercut(), and computeStrengthenedIntercut().

◆ addRowToCut()

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
scipSCIP data structure
rowpreprowprep to store intersection cut
cutcoefcut coefficient
rowrow, whose slack we are ading to rowprep
successif the row is nonbasic enough

Definition at line 262 of file nlhdlr_quadratic.c.

References FALSE, NULL, SCIP_BASESTAT_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPcolGetVar(), SCIPgetRowActivity(), SCIPinfoMessage(), SCIPisFeasEQ(), SCIPisInfinity(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), and SCIProwprepAddConstant().

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
scipSCIP data structure
mapbuffer to store the map

Definition at line 323 of file nlhdlr_quadratic.c.

References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetLPBasisInd(), and SCIPgetNLPRows().

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
nlhdlrexprdatanlhdlr expression data
auxvaraux var of expr or NULL if not needed (e.g. separating real cons)
nozerostatwhether there is no variable with basis status zero

Definition at line 349 of file nlhdlr_quadratic.c.

References FALSE, NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_ZERO, SCIPcolGetBasisStatus(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPvarGetCol(), and TRUE.

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
scipSCIP data structure
colbasic columns to store its tableau row
basicvarpos2tableaurowmap between basic var and its tableau row
nbasiccolwhich basic var this is
raylengththe length of a ray (the total number of basic vars)
binvrowbuffer to store row of Binv
binvarowbuffer to store row of Binv A
tableaurowspointer to store the tableau rows

Definition at line 428 of file nlhdlr_quadratic.c.

References NULL, SCIP_BASESTAT_BASIC, SCIP_CALL, SCIP_OKAY, SCIPcolGetBasisStatus(), SCIPcolGetLPPos(), SCIPgetLPBInvARow(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), and SCIProwGetBasisStatus().

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
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
raylengthlength of a ray of the tableau
auxvaraux var of expr or NULL if not needed (e.g. separating real cons)
tableaurowsbuffer to store the tableau rows
rayentry2consposbuffer to store the map

Definition at line 495 of file nlhdlr_quadratic.c.

References constructBasicVars2TableauRowMap(), NULL, SCIP_BASESTAT_BASIC, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeBufferArray, SCIPgetExprAuxVarNonlinear(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPinfoMessage(), SCIPvarGetCol(), and storeDenseTableauRow().

Referenced by createAndStoreSparseRays().

◆ createRays()

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

initializes rays data structure

Parameters
scipSCIP data structure
raysrays data structure

Definition at line 595 of file nlhdlr_quadratic.c.

References BMSclearMemory, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPgetNLPCols(), and SCIPgetNLPRows().

Referenced by createAndStoreSparseRays().

◆ createBoundRays()

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

initializes rays data structure for bound rays

Parameters
scipSCIP data structure
raysrays data structure
sizenumber of rays to allocate

Definition at line 618 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
scipSCIP data structure
raysrays data structure

Definition at line 642 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
scipSCIP data structure
raysrays data structure
coefcoefficient to insert
coefidxindex of coefficient (conspos of var it corresponds to)
coefposwhere to insert coefficient

Definition at line 660 of file nlhdlr_quadratic.c.

References Rays::rays, Rays::raysidx, Rays::rayssize, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBufferArray.

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
nlhdlrexprdatanlhdlr expression data
auxvaraux var of the expr
mapbuffer to store the mapping

Definition at line 692 of file nlhdlr_quadratic.c.

References NULL, SCIPcolGetLPPos(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), and SCIPvarGetCol().

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
scipSCIP data structure
raysrays data structure
densetableaucolscolumn of the tableau in dense format
rayentry2consposmap between rayentry and conspos of associated var
raylengthlength of a tableau column
nraywhich tableau column to insert
consposconspos of ray's nonbasic var in the cons; -1 if not in the cons
factorfactor to multiply each tableau col
nnonzposition to start adding the ray in rays and buffer to store nnonz
successwe can't separate if there is a nonzero ray with basis status ZERO

Definition at line 735 of file nlhdlr_quadratic.c.

References FALSE, insertRayEntry(), Rays::nrays, NULL, Rays::rays, Rays::raysbegin, Rays::raysidx, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfoMessage(), SCIPisZero(), and TRUE.

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
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
auxvaraux var of expr or NULL if not needed (e.g. separating real cons)
raysptrbuffer to store rays datastructure
successwe can't separate if there is a var with basis status ZERO

Definition at line 859 of file nlhdlr_quadratic.c.

References constructLPPos2ConsPosMap(), countBasicVars(), createRays(), freeRays(), insertRayEntries(), Rays::lpposray, Rays::nrays, NULL, Rays::rays, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPinfoMessage(), SCIProwGetBasisStatus(), SCIProwGetLPPos(), SCIPvarGetName(), storeDenseTableauRowsByColumns(), and TRUE.

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
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
auxvaraux var of expr or NULL if not needed (e.g. separating real cons)
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
solsolution to separate
vbbuffer to store \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlpbuffer to store \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
wcoefsbuffer to store the coefs of quad vars of w
wzlppointer to store the value of w at zlp
kappapointer to store the value of kappa

Definition at line 1058 of file nlhdlr_quadratic.c.

References BMSclearMemoryArray, NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPisZero(), and SQR.

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
eigenveceigenvector
nquadvarsnumber of quadratic vars (length of eigenvec)
raycoefscoefficients of ray
rayidxindex of consvar the ray coef is associated to
raynnonzlength of raycoefs and rayidx

Definition at line 1177 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
nlhdlrexprdatanlhdlr expression data
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
raycoefscoefficients of ray
rayidxray coef[i] affects var at pos rayidx[i] in consvar
raynnonzlength of raycoefs and rayidx

Definition at line 1206 of file nlhdlr_quadratic.c.

References NULL, SCIP_Real, and SCIPexprGetQuadraticData().

Referenced by computeRestrictionToRay().

◆ computeVApexAndVRay()

static void computeVApexAndVRay ( SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_Real apex,
SCIP_Real raycoefs,
int *  rayidx,
int  raynnonz,
SCIP_Real vapex,
SCIP_Real vray 
)
static

computes the dot product of v_i and the current ray as well as of v_i and the apex where v_i is the i-th eigenvalue

Parameters
nlhdlrexprdatanlhdlr expression data
apexarray containing the apex of the S-free set in the original space
raycoefscoefficients of ray
rayidxindex of consvar the ray coef is associated to
raynnonzlength of raycoefs and rayidx
vapexarray to store \(v_i^T apex\)
vrayarray to store \(v_i^T ray\)

Definition at line 1263 of file nlhdlr_quadratic.c.

References NULL, SCIP_Real, and SCIPexprGetQuadraticData().

Referenced by computeMonoidalStrengthCoef(), and computeRestrictionToLine().

◆ computeRestrictionToLine()

static SCIP_RETCODE computeRestrictionToLine ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_Real  sidefactor,
SCIP_Real raycoefs,
int *  rayidx,
int  raynnonz,
SCIP_Real vb,
SCIP_Real vzlp,
SCIP_Real  kappa,
SCIP_Real apex,
SCIP_Real coefs2,
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
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
raycoefscoefficients of ray
rayidxindex of consvar the ray coef is associated to
raynnonzlength of raycoefs and rayidx
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
kappavalue of kappa
apexapex of C
coefs2buffer to store A, B, C, D, and E of case 2
successdid we successfully compute the coefficients?

Definition at line 1331 of file nlhdlr_quadratic.c.

References a, b, BMSclearMemoryArray, computeVApexAndVRay(), FALSE, INTERLOG, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPexprGetQuadraticData(), SCIPfreeBufferArray, SCIPinfoMessage(), SCIPisZero(), SQR, and TRUE.

Referenced by computeIntercut().

◆ 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
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
iscase4whether we are in case 4
raycoefscoefficients of ray
rayidxindex of consvar the ray coef is associated to
raynnonzlength of raycoefs and rayidx
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
wcoefscoefficients of w for the qud vars or NULL if w is 0
wzlpvalue of w at zlp
kappavalue of kappa
coefs1234abuffer to store A, B, C, D, and E of cases 1, 2, 3, or 4a
coefs4bbuffer to store A, B, C, D, and E of case 4b (or NULL if not needed)
coefsconditionbuffer to store data to evaluate condition to decide case 4a or 4b
successdid we successfully compute the coefficients?

Definition at line 1464 of file nlhdlr_quadratic.c.

References a, b, BMSclearMemoryArray, computeEigenvecDotRay(), computeWRayLinear(), FALSE, INTERLOG, MAX, MIN, NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetQuadraticData(), SCIPinfoMessage(), SCIPisZero(), SQR, and TRUE.

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
targument of phi restricted to ray
avalue of A
bvalue of B
cvalue of C
dvalue of D
evalue of E

Definition at line 1701 of file nlhdlr_quadratic.c.

References QUAD, QUAD_ASSIGN, QUAD_SCALE, QUAD_TO_DBL, SCIP_Real, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecSqrtQ, SCIPquadprecSquareD, SCIPquadprecSumQD, and SCIPquadprecSumQQ.

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
tsolt in the above formula
coefs4acoefficients A, B, C, D, and E of case 4a
coefsconditionextra 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 1765 of file nlhdlr_quadratic.c.

References SQR.

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
scipSCIP data structure
avalue of A
bvalue of B
cvalue of C
dvalue of D
evalue of E
solbuffer to store solution; also gives initial point

Definition at line 1778 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
scipSCIP data structure
coefsvalue of A

Definition at line 1823 of file nlhdlr_quadratic.c.

References a, b, doBinarySearch(), evalPhiAtRay(), SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalIsEmpty(), SCIPintervalSetBounds(), and SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar().

Referenced by computeIntercut(), and 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
scipSCIP data structure
nlhdlrdatanlhdlr data
iscase4whether we are in case 4 or not
coefs1234avalues of A, B, C, D, and E of cases 1, 2, 3, or 4a
coefs4bvalues of A, B, C, D, and E of case 4b
coefsconditionvalues needed to evaluate condition of case 4

Definition at line 1923 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
scipSCIP data structure
nlhdlrdatanlhdlr data
coefs1234acoefficients for case 1-3 and 4a
coefs4bcoefficients for case 4b
iscase4whether we are in case 4

Definition at line 1990 of file nlhdlr_quadratic.c.

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

Referenced by computeIntercut().

◆ computeMonoidalQuadCoefs()

static SCIP_RETCODE computeMonoidalQuadCoefs ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_Real vb,
SCIP_Real vzlp,
SCIP_Real vapex,
SCIP_Real vray,
SCIP_Real  kappa,
SCIP_Real  sidefactor,
SCIP_Real a,
SCIP_Real b,
SCIP_Real c 
)
static

computes the coefficients a, b, c defining the quadratic function defining set S restricted to the line theta * apex.

The solution to the monoidal strengthening problem is then given by the smallest root of the function a * theta^2 + b * theta + c

Parameters
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
vapexarray containing \(v_i^T apex\)
vrayarray containing \(v_i^T ray\)
kappavalue of kappa
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
apointer to store quadratic coefficient
bpointer to store linear coefficient
cpointer to store constant

Definition at line 2071 of file nlhdlr_quadratic.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetQuadraticData(), SCIPisZero(), and SQR.

Referenced by computeMonoidalStrengthCoef().

◆ isRayInStrip()

static SCIP_Bool isRayInStrip ( SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_Real vb,
SCIP_Real vzlp,
SCIP_Real vapex,
SCIP_Real vray,
SCIP_Real  kappa,
SCIP_Real  sidefactor,
SCIP_Real  cutcoef 
)
static

check if ray was in strip by checking if the point in the monoid corresponding to the cutcoef we just found is "on the wrong side" of the hyperplane -(a - lambda^Ta lambda)^T x

Parameters
nlhdlrexprdatanlhdlr expression data
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
vapexarray containing \(v_i^T apex\)
vrayarray containing \(v_i^T ray\)
kappavalue of kappa
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
cutcoefoptimal solution of the monoidal quadratic

Definition at line 2121 of file nlhdlr_quadratic.c.

References NULL, SCIP_Real, SCIPexprGetQuadraticData(), and SQR.

Referenced by computeMonoidalStrengthCoef().

◆ findMonoidalQuadRoot()

static SCIP_Real findMonoidalQuadRoot ( SCIP scip,
SCIP_Real  a,
SCIP_Real  b,
SCIP_Real  c 
)
static

computes the smallest root of the quadratic function a*x^2 + b*x + c with a > 0 and b^2 - 4ac >= 0. We use binary search between -inf and minimum at -b/2a.

Parameters
scipSCIP data structure
aquadratic coefficient
blinear coefficient
cconstant

Definition at line 2172 of file nlhdlr_quadratic.c.

References a, ABS, b, BINSEARCH_MAXITERS, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalIsEmpty(), SCIPintervalSetBounds(), SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(), SCIPisInfinity(), SCIPisZero(), and SQR.

Referenced by computeMonoidalStrengthCoef().

◆ computeApex()

static void computeApex ( SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_Real vb,
SCIP_Real vzlp,
SCIP_Real  kappa,
SCIP_Real  sidefactor,
SCIP_Real apex,
SCIP_Bool success 
)
static

computes the apex of the S-free set (if it exists)

Parameters
nlhdlrexprdatanlhdlr expression data
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
kappavalue of kappa
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
apexarray to store apex
successTRUE if computation of apex was successful

Definition at line 2261 of file nlhdlr_quadratic.c.

References FALSE, NULL, SCIP_Real, SCIPexprGetQuadraticData(), SQR, and TRUE.

Referenced by computeIntercut().

◆ computeMonoidalStrengthCoef()

static SCIP_RETCODE computeMonoidalStrengthCoef ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
int  lppos,
SCIP_Real raycoefs,
int *  rayidx,
int  raynnonz,
SCIP_Real vb,
SCIP_Real vzlp,
SCIP_Real wcoefs,
SCIP_Real  kappa,
SCIP_Real apex,
SCIP_Real  sidefactor,
SCIP_Real cutcoef,
SCIP_Bool success 
)
static

for a given ray, computes the cut coefficient using monoidal strengthening (if possible)

Parameters
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
lpposlp pos of current ray
raycoefscoefficients of ray
rayidxindex of consvar the ray coef is associated to
raynnonzlength of raycoefs and rayidx
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
wcoefscoefficients of w for the qud vars or NULL if w is 0
kappavalue of kappa
apexarray containing the apex of the S-free set in the original space
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
cutcoefpointer to store cut coef
successTRUE if monoidal strengthening could be applied

Definition at line 2327 of file nlhdlr_quadratic.c.

References a, b, computeMonoidalQuadCoefs(), computeVApexAndVRay(), FALSE, findMonoidalQuadRoot(), isRayInStrip(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPcolGetVar(), SCIPexprGetQuadraticData(), SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPRows(), SCIProwIsIntegral(), SCIPvarGetType(), SQR, and TRUE.

Referenced by computeIntercut().

◆ sparsifyIntercut()

static void sparsifyIntercut ( SCIP scip,
SCIP_ROWPREP rowprep 
)
static

sparsify intersection cut by replacing non-basic variables with their bounds if their coefficient allows it

Parameters
scipSCIP data structure
rowpreprowprep for the generated cut

Definition at line 2402 of file nlhdlr_quadratic.c.

References NULL, SCIP_Real, SCIPgetSolVal(), SCIPisZero(), SCIProwprepAddSide(), SCIProwprepGetCoefs(), SCIProwprepGetNVars(), SCIProwprepGetVars(), SCIProwprepSetCoef(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_NLHDLRENFO().

◆ 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
scipSCIP data structure
nlhdlrdatanlhdlr data
nlhdlrexprdatanlhdlr expression data
raysrays
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
iscase4whether we are in case 4
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
wcoefscoefficients of w for the qud vars or NULL if w is 0
wzlpvalue of w at zlp
kappavalue of kappa
rowpreprowprep for the generated cut
interpointsarray to store intersection points for all rays or NULL if nothing needs to be stored
solsolution we want to separate
successif a cut candidate could be computed

Definition at line 2455 of file nlhdlr_quadratic.c.

References addColToCut(), addRowToCut(), areCoefsNumericsGood(), computeApex(), computeIntersectionPoint(), computeMonoidalStrengthCoef(), computeRestrictionToLine(), computeRestrictionToRay(), computeRoot(), FALSE, INTERLOG, Rays::lpposray, Rays::nrays, NULL, Rays::rays, Rays::raysbegin, Rays::raysidx, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPexprGetQuadraticData(), SCIPfreeBufferArrayNull, SCIPgetLPCols(), SCIPgetLPRows(), SCIPinfinity(), SCIPinfoMessage(), SCIPisInfinity(), SCIProwGetBasisStatus(), and TRUE.

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
raycoefs1coefficients of ray 1
rayidx1index of consvar of the ray 1 coef is associated to
raynnonz1length of raycoefs1 and rayidx1
raycoefs2coefficients of ray 2
rayidx2index of consvar of the ray 2 coef is associated to
raynnonz2length of raycoefs2 and rayidx2
newraycoefscoefficients of combined ray
newrayidxindex of consvar of the combined ray coef is associated to
newraynnonzpointer to length of newraycoefs and newrayidx
coef1coef of ray 1
coef2coef of ray 2

Definition at line 2682 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
scipSCIP data structure
raycoefs1coefficients of ray 1
rayidx1index of consvar of the ray 1 coef is associated to
raynnonz1length of raycoefs1 and rayidx1
raycoefs2coefficients of ray 2
rayidx2index of consvar of the ray 2 coef is associated to
raynnonz2length of raycoefs2 and rayidx2
coefpointer to store coef (s.t. r1 = coef * r2) in case rays are dependent

Definition at line 2739 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
scipSCIP data structure
nlhdlrdatanlhdlr data
nlhdlrexprdatanlhdlr expression data
raysrays
jindex of current ray in recession cone
iindex of current ray not in recession cone
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
iscase4whether we are in case 4
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
wcoefscoefficients of w for the quad vars or NULL if w is 0
wzlpvalue of w at zlp
kappavalue of kappa
alphacoef for combining the two rays
inrecconepointer to store whether the ray is in the recession cone or not
successDid numerical troubles occur?

Definition at line 2788 of file nlhdlr_quadratic.c.

References combineRays(), computeIntersectionPoint(), computeRestrictionToRay(), FALSE, Rays::rays, Rays::raysbegin, Rays::raysidx, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), and TRUE.

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
scipSCIP data structure
nlhdlrdatanlhdlr data
nlhdlrexprdatanlhdlr expression data
raysrays
idxindex of current ray we want to find rho for
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
iscase4whether we are in case 4
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
wcoefscoefficients of w for the quad vars or NULL if w is 0
wzlpvalue of w at zlp
kappavalue of kappa
interpointsarray to store intersection points for all rays or NULL if nothing needs to be stored
rhopointer to store the optimal rho
successcould we successfully find the right rho?

Definition at line 2857 of file nlhdlr_quadratic.c.

References BINSEARCH_MAXITERS, FALSE, Rays::nrays, rayInRecessionCone(), Rays::rays, raysAreDependent(), Rays::raysbegin, Rays::raysidx, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), and SCIPisZero().

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
scipSCIP data structure
nlhdlrdatanlhdlr data
nlhdlrexprdatanlhdlr expression data
raysrays
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
iscase4whether we are in case 4
vbarray containing \(v_i^T b\) for \(i \in I_+ \cup I_-\)
vzlparray containing \(v_i^T zlp_q\) for \(i \in I_+ \cup I_-\)
wcoefscoefficients of w for the qud vars or NULL if w is 0
wzlpvalue of w at zlp
kappavalue of kappa
rowpreprowprep for the generated cut
solsolution to separate
successif a cut candidate could be computed
strengthsuccessif strengthening was successfully applied

Definition at line 2976 of file nlhdlr_quadratic.c.

References addColToCut(), addRowToCut(), computeIntercut(), FALSE, findRho(), INTERLOG, Rays::lpposray, Rays::nrays, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPRows(), SCIPisInfinity(), SCIPisZero(), SCIProwGetBasisStatus(), and TRUE.

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
scipSCIP data structure
solsolution to separate
vertexnew solution to separate
varvar we want to find nearest bound to
factoris vertex for current var at lower or upper?
successTRUE if no variable is bounded

Definition at line 3092 of file nlhdlr_quadratic.c.

References bound, FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisInfinity(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

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
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
solsolution to separate
vertexnew 'vertex' (w.r.t. bounds) solution to separate
auxvaraux var of expr or NULL if not needed (e.g. separating real cons)
raysptrpointer to new bound rays
successTRUE if no variable is unbounded

Definition at line 3137 of file nlhdlr_quadratic.c.

References createBoundRays(), Rays::lpposray, Rays::nrays, NULL, Rays::rays, Rays::raysbegin, Rays::raysidx, Rays::rayssize, SCIP_CALL, SCIP_OKAY, SCIPcolGetLPPos(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPvarGetCol(), setVarToNearestBound(), and TRUE.

Referenced by generateIntercut().

◆ isQuadConsViolated()

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
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
auxvaraux var of expr or NULL if not needed (e.g. separating real cons)
solsolution to check feasibility for
sidefactor1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise

Definition at line 3220 of file nlhdlr_quadratic.c.

References FALSE, NULL, SCIP_Real, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPgetSolVal(), SQR, and TRUE.

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
scipSCIP data structure
exprexpr
nlhdlrdatanlhdlr data
nlhdlrexprdatanlhdlr expression data
consviolated constraint that contains expr
solsolution to separate
rowpreprowprep for the generated cut
overestimateTRUE if viol cons is q(z) ≥ lhs; FALSE if q(z) ≤ rhs
successwhether separation was successfull or not

Definition at line 3304 of file nlhdlr_quadratic.c.

References computeIntercut(), computeStrengthenedIntercut(), createAndStoreSparseRays(), FALSE, findVertexAndGetRays(), freeRays(), intercutsComputeCommonQuantities(), INTERLOG, isQuadConsViolated(), NULL, Rays::rays, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIPallocBufferArray, SCIPcreateSol(), SCIPexprGetQuadraticData(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPgetExprAuxVarNonlinear(), SCIPinfoMessage(), SCIPprintExpr(), SCIProwprepAddSide(), SCIProwprepGetSide(), SCIProwprepSetSidetype(), and TRUE.

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
qexprquadratic representation data

Definition at line 3471 of file nlhdlr_quadratic.c.

References FALSE, NULL, SCIP_Real, SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), and TRUE.

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
qexprquadratic representation data
idxindex of quadratic term to consider

Definition at line 3504 of file nlhdlr_quadratic.c.

References NULL, SCIP_Real, and SCIPexprGetQuadraticQuadTerm().

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

◆ propagateBoundsQuadExpr()

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
scipSCIP data structure
exprexpression for which to solve
sqrcoefsquare coefficient
binterval acting as linear coefficient
rhsinterval acting as rhs
infeasiblebuffer to store if propagation produced infeasibility
nreductionsbuffer to store the number of interval reductions

Definition at line 3522 of file nlhdlr_quadratic.c.

References a, SCIP_Interval::inf, NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPgetExprBoundsNonlinear(), SCIPinfoMessage(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalSet(), SCIPintervalSolveUnivariateQuadExpression(), SCIPprintExpr(), SCIPtightenExprIntervalNonlinear(), SCIP_Interval::sup, and TRUE.

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
scipSCIP data structure
exprexpression for which to solve
blinear coefficient
rhsinterval acting as rhs
infeasiblebuffer to store if propagation produced infeasibility
nreductionsbuffer to store the number of interval reductions

Definition at line 3573 of file nlhdlr_quadratic.c.

References SCIP_Interval::inf, NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPinfoMessage(), SCIPintervalDivScalar(), SCIPprintExpr(), SCIPtightenExprIntervalNonlinear(), and SCIP_Interval::sup.

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
acoefficient a
ccoefficient c
x1coefficient x1 > 0
x2coefficient x2 > 0

Definition at line 3609 of file nlhdlr_quadratic.c.

References MAX, SCIP_Real, SCIPintervalGetRoundingMode(), SCIPintervalNegateReal(), SCIPintervalSetRoundingMode(), and SCIPintervalSetRoundingModeUpwards().

Referenced by computeMaxForBilinearProp().

◆ computeMaxForBilinearProp()

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

◆ 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
exprdomexpression for which to solve
coefexpression for which to solve
rhsrhs used for computation
rangestorage for the resulting range

Definition at line 3704 of file nlhdlr_quadratic.c.

References computeMaxForBilinearProp(), SCIP_Interval::inf, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPintervalMulScalar(), SCIPintervalSetBounds(), SCIPintervalSetEntire(), and SCIP_Interval::sup.

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
scipSCIP data structure
linexprslinear expressions
nlinexprsnumber of linear expressions
lincoefscoefficients of linear expressions
constantconstant
rhsrhs
infeasiblebuffer to store whether an exps' bounds were propagated to an empty interval
nreductionsbuffer to store the number of interval reductions of all exprs

Definition at line 3739 of file nlhdlr_quadratic.c.

References SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPallocBufferArray, SCIPexprGetActivity(), SCIPfreeBufferArray, SCIPintervalPropagateWeightedSum(), and SCIPtightenExprIntervalNonlinear().

Referenced by SCIP_DECL_NLHDLRREVERSEPROP().

◆ SCIP_DECL_NLHDLRFREEEXPRDATA()

static SCIP_DECL_NLHDLRFREEEXPRDATA ( nlhdlrFreeexprdataQuadratic  )
static

callback to free expression specific data

Definition at line 3789 of file nlhdlr_quadratic.c.

References NULL, SCIP_OKAY, SCIPexprGetQuadraticData(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

◆ SCIP_DECL_NLHDLRDETECT()

static SCIP_DECL_NLHDLRDETECT ( nlhdlrDetectQuadratic  )
static

callback to detect structure in expression tree

A term is quadratic if

  • 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 3854 of file nlhdlr_quadratic.c.

References FALSE, isPropagable(), isPropagableTerm(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_UNKNOWN, SCIP_INTERVAL_INFINITY, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_NLHDLR_METHOD_ALL, SCIP_NLHDLR_METHOD_NONE, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIP_STAGE_PRESOLVING, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemory, SCIPcheckExprQuadratic(), SCIPcomputeExprQuadraticCurvature(), SCIPdebugMsg, SCIPexprAreQuadraticExprsVariables(), SCIPexprGetActivity(), SCIPexprGetNChildren(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPexprSetCurvature(), SCIPgetStage(), SCIPgetSubscipDepth(), SCIPinfoMessage(), SCIPintervalIsEntire(), SCIPisExprSum(), SCIPnlhdlrGetData(), SCIPprintExpr(), SCIPprintExprQuadratic(), SCIPregisterExprUsageNonlinear(), and TRUE.

◆ SCIP_DECL_NLHDLREVALAUX()

static SCIP_DECL_NLHDLREVALAUX ( nlhdlrEvalauxQuadratic  )
static

◆ SCIP_DECL_NLHDLRENFO()

◆ SCIP_DECL_NLHDLRINTEVAL()

static SCIP_DECL_NLHDLRINTEVAL ( nlhdlrIntevalQuadratic  )
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 4444 of file nlhdlr_quadratic.c.

References b, SCIP_Interval::inf, isPropagableTerm(), NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPexprGetActivity(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfindConshdlr(), SCIPgetCurBoundsTagNonlinear(), SCIPinfoMessage(), SCIPintervalAdd(), SCIPintervalGetInf(), SCIPintervalGetRoundingMode(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalMulScalar(), SCIPintervalQuadUpperBound(), SCIPintervalSet(), SCIPintervalSetBounds(), SCIPintervalSetEmpty(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSetRoundingModeUpwards(), SCIPprintExpr(), and SCIP_Interval::sup.

◆ SCIP_DECL_NLHDLRREVERSEPROP()

◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

static SCIP_DECL_NLHDLRFREEHDLRDATA ( nlhdlrFreehdlrdataQuadratic  )
static

callback to free data of handler

Definition at line 5020 of file nlhdlr_quadratic.c.

References NULL, SCIP_OKAY, and SCIPfreeBlockMemory.

◆ SCIP_DECL_NLHDLRCOPYHDLR()

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrQuadratic  )
static

nonlinear handler copy callback

Definition at line 5031 of file nlhdlr_quadratic.c.

References NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrQuadratic(), and SCIPnlhdlrGetName().