nlhdlr_quadratic.c File Reference

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.

#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.

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

#define INTERLOG

(

x

)

Definition at line 52 of file nlhdlr_quadratic.c.

Referenced by areCoefsNumericsGood(), computeIntercut(), computeRestrictionToLine(), computeRestrictionToRay(), computeStrengthenedIntercut(), generateIntercut(), and SCIP_DECL_NLHDLRENFO().

NLHDLR_NAME

#define NLHDLR_NAME   "quadratic"

Definition at line 65 of file nlhdlr_quadratic.c.

Referenced by SCIP_DECL_NLHDLRCOPYHDLR(), SCIP_DECL_TABLEOUTPUT(), and SCIPincludeNlhdlrQuadratic().

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

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 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

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 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

scip	SCIP data structure
map	buffer 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

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 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

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 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

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 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

scip	SCIP data structure
rays	rays 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

scip	SCIP data structure
rays	rays data structure
size	number 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

scip	SCIP data structure
rays	rays 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

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 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

nlhdlrexprdata	nlhdlr expression data
auxvar	aux var of the expr
map	buffer 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

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 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

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 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

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 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

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 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

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 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

nlhdlrexprdata	nlhdlr expression data
apex	array containing the apex of the S-free set in the original space
raycoefs	coefficients of ray
rayidx	index of consvar the ray coef is associated to
raynnonz	length of raycoefs and rayidx
vapex	array to store \(v_i^T apex\)
vray	array 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

scip	SCIP data structure
nlhdlrexprdata	nlhdlr expression data
sidefactor	1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
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_-\)
kappa	value of kappa
apex	apex of C
coefs2	buffer to store A, B, C, D, and E of case 2
success	did 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

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 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

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 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

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 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

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 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

scip	SCIP data structure
coefs	value 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

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 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

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

References ABS, FALSE, INTERLOG, 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

scip	SCIP data structure
nlhdlrexprdata	nlhdlr expression data
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_-\)
vapex	array containing \(v_i^T apex\)
vray	array containing \(v_i^T ray\)
kappa	value of kappa
sidefactor	1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
a	pointer to store quadratic coefficient
b	pointer to store linear coefficient
c	pointer to store constant

Definition at line 2070 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

nlhdlrexprdata	nlhdlr expression data
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_-\)
vapex	array containing \(v_i^T apex\)
vray	array containing \(v_i^T ray\)
kappa	value of kappa
sidefactor	1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
cutcoef	optimal solution of the monoidal quadratic

Definition at line 2120 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

scip	SCIP data structure
a	quadratic coefficient
b	linear coefficient
c	constant

Definition at line 2171 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

nlhdlrexprdata	nlhdlr expression data
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_-\)
kappa	value of kappa
sidefactor	1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
apex	array to store apex
success	TRUE if computation of apex was successful

Definition at line 2260 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

scip	SCIP data structure
nlhdlrexprdata	nlhdlr expression data
lppos	lp pos of current ray
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
kappa	value of kappa
apex	array containing the apex of the S-free set in the original space
sidefactor	1.0 if the violated constraint is q ≤ rhs, -1.0 otherwise
cutcoef	pointer to store cut coef
success	TRUE if monoidal strengthening could be applied

Definition at line 2326 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

scip	SCIP data structure
rowprep	rowprep for the generated cut

Definition at line 2401 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

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 2454 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

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 2681 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 2738 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 2787 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

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 2856 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

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 2975 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

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 3091 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

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 3136 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

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 3219 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

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 3303 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

qexpr

quadratic representation data

Definition at line 3470 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

qexpr	quadratic representation data
idx	index of quadratic term to consider

Definition at line 3503 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

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 3521 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

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 3572 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

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

Definition at line 3608 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

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

References computeMaxBoundaryForBilinearProp(), SCIP_Interval::inf, MAX, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPintervalDivScalar(), SCIPintervalGetRoundingMode(), SCIPintervalNegateReal(), SCIPintervalSet(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSquareRoot(), SCIPnextafter(), and SCIP_Interval::sup.

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 3703 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

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 3738 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 3788 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 3853 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

nonlinear handler auxiliary evaluation callback

Definition at line 4126 of file nlhdlr_quadratic.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetEvalValue(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetExprAuxVarNonlinear(), and SCIPgetSolVal().

SCIP_DECL_NLHDLRENFO()

static SCIP_DECL_NLHDLRENFO ( nlhdlrEnfoQuadratic  )

static

nonlinear handler enforcement callback

Definition at line 4191 of file nlhdlr_quadratic.c.

References ABS, FALSE, generateIntercut(), INTERLOG, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_SIDETYPE_LEFT, SCIPaddRow(), SCIPcleanupRowprep(), SCIPcreateRowprep(), SCIPdebugMsg, SCIPexprGetQuadraticData(), SCIPfeastol(), SCIPfreeRowprep(), SCIPgetCurrentNode(), SCIPgetCutEfficacy(), SCIPgetExprAuxVarNonlinear(), SCIPgetLhsNonlinear(), SCIPgetLPSolstat(), SCIPgetNLPs(), SCIPgetNVars(), SCIPgetRhsNonlinear(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetRowprepRowCons(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPisLPSolBasic(), SCIPmergeRowprepTerms(), SCIPnlhdlrGetData(), SCIPnodeGetDepth(), SCIPnodeGetNumber(), SCIPprintCons(), SCIPprintExpr(), SCIPprintRow(), SCIPprintTransSol(), SCIPreleaseRow(), SCIProwprepGetName(), SCIProwprepGetNVars(), SCIPsnprintf(), SCIPvarGetName(), sparsifyIntercut(), and TRUE.

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 4443 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()

static SCIP_DECL_NLHDLRREVERSEPROP ( nlhdlrReversepropQuadratic  )

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

References b, computeRangeForBilinearProp(), SCIP_Interval::inf, isPropagableTerm(), NULL, propagateBoundsLinExpr(), propagateBoundsQuadExpr(), reversePropagateLinearExpr(), SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPexprGetActivityTag(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeBufferArray, SCIPgetExprBoundsNonlinear(), SCIPintervalAdd(), SCIPintervalGetInf(), SCIPintervalGetRoundingMode(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalIsEntire(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetBounds(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSetRoundingModeUpwards(), SCIPintervalSub(), SCIPisSumRelEQ(), SCIPswapReals(), SCIP_Interval::sup, and TRUE.

SCIP_DECL_NLHDLRFREEHDLRDATA()

static SCIP_DECL_NLHDLRFREEHDLRDATA ( nlhdlrFreehdlrdataQuadratic  )

static

callback to free data of handler

Definition at line 5019 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 5030 of file nlhdlr_quadratic.c.

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