Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

bilinear nonlinear handler

Author
Benjamin Mueller

Definition in file nlhdlr_bilinear.c.

#include <string.h>
#include "scip/nlhdlr_bilinear.h"
#include "scip/cons_nonlinear.h"
#include "scip/expr_product.h"
#include "scip/expr_var.h"

Go to the source code of this file.

Macros

#define NLHDLR_NAME   "bilinear"
 
#define NLHDLR_DESC   "bilinear handler for expressions"
 
#define NLHDLR_DETECTPRIORITY   -10
 
#define NLHDLR_ENFOPRIORITY   -10
 
#define MIN_INTERIORITY   0.01
 
#define MIN_ABSBOUNDSIZE   0.1
 
#define TABLE_NAME_BILINEAR   "nlhdlr_bilinear"
 
#define TABLE_DESC_BILINEAR   "bilinear nlhdlr statistics table"
 
#define TABLE_POSITION_BILINEAR   14800
 
#define TABLE_EARLIEST_STAGE_BILINEAR   SCIP_STAGE_INITSOLVE
 
#define nlhdlrInitBilinear   NULL
 
#define nlhdlrInitSepaBilinear   NULL
 
#define nlhdlrExitSepaBilinear   NULL
 
#define nlhdlrEnfoBilinear   NULL
 

Functions

static void getIneqViol (SCIP_VAR *x, SCIP_VAR *y, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Real *viol1, SCIP_Real *viol2)
 
static SCIP_Bool useBilinIneqs (SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, SCIP_Real refx, SCIP_Real refy)
 
static void updateBilinearRelaxation (SCIP *scip, SCIP_VAR *RESTRICT x, SCIP_VAR *RESTRICT y, SCIP_Real bilincoef, SCIP_SIDETYPE violside, SCIP_Real refx, SCIP_Real refy, SCIP_Real *RESTRICT ineqs, int nineqs, SCIP_Real mccormickval, SCIP_Real *RESTRICT bestcoefx, SCIP_Real *RESTRICT bestcoefy, SCIP_Real *RESTRICT bestconst, SCIP_Real *RESTRICT bestval, SCIP_Bool *success)
 
static SCIP_Bool isPointFeasible (SCIP *scip, SCIP_Real x, SCIP_Real y, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real lby, SCIP_Real uby, SCIP_Real *ineqs, int nineqs)
 
static void getFeasiblePointsBilinear (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_EXPR *expr, SCIP_INTERVAL exprbounds, SCIP_Real *underineqs, int nunderineqs, SCIP_Real *overineqs, int noverineqs, SCIP_Bool levelset, SCIP_Real *xs, SCIP_Real *ys, int *npoints)
 
static SCIP_INTERVAL intevalBilinear (SCIP *scip, SCIP_EXPR *expr, SCIP_Real *underineqs, int nunderineqs, SCIP_Real *overineqs, int noverineqs)
 
static void reversePropBilinear (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_EXPR *expr, SCIP_INTERVAL exprbounds, SCIP_Real *underineqs, int nunderineqs, SCIP_Real *overineqs, int noverineqs, SCIP_INTERVAL *intervalx, SCIP_INTERVAL *intervaly)
 
static void computeBilinEnvelope2 (SCIP *scip, SCIP_Real x, SCIP_Real y, SCIP_Real mi, SCIP_Real qi, SCIP_Real mj, SCIP_Real qj, SCIP_Real *RESTRICT xi, SCIP_Real *RESTRICT yi, SCIP_Real *RESTRICT xj, SCIP_Real *RESTRICT yj, SCIP_Real *RESTRICT xcoef, SCIP_Real *RESTRICT ycoef, SCIP_Real *RESTRICT constant)
 
static SCIP_DECL_TABLEOUTPUT (tableOutputBilinear)
 
static SCIP_DECL_NLHDLRCOPYHDLR (nlhdlrCopyhdlrBilinear)
 
static SCIP_DECL_NLHDLRFREEHDLRDATA (nlhdlrFreehdlrdataBilinear)
 
static SCIP_DECL_NLHDLRFREEEXPRDATA (nlhdlrFreeExprDataBilinear)
 
static SCIP_DECL_NLHDLREXIT (nlhdlrExitBilinear)
 
static SCIP_DECL_NLHDLRDETECT (nlhdlrDetectBilinear)
 
static SCIP_DECL_NLHDLREVALAUX (nlhdlrEvalauxBilinear)
 
static SCIP_DECL_NLHDLRESTIMATE (nlhdlrEstimateBilinear)
 
static SCIP_DECL_NLHDLRINTEVAL (nlhdlrIntevalBilinear)
 
static SCIP_DECL_NLHDLRREVERSEPROP (nlhdlrReversepropBilinear)
 
SCIP_RETCODE SCIPincludeNlhdlrBilinear (SCIP *scip)
 
SCIP_EXPR ** SCIPgetExprsBilinear (SCIP_NLHDLR *nlhdlr)
 
int SCIPgetNExprsBilinear (SCIP_NLHDLR *nlhdlr)
 
SCIP_RETCODE SCIPaddIneqBilinear (SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_EXPR *expr, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Bool *success)
 
void SCIPaddBilinLinearization (SCIP *scip, SCIP_Real bilincoef, SCIP_Real refpointx, SCIP_Real refpointy, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
 
void SCIPaddBilinMcCormick (SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
 
void SCIPcomputeBilinEnvelope1 (SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Real *RESTRICT lincoefx, SCIP_Real *RESTRICT lincoefy, SCIP_Real *RESTRICT linconstant, SCIP_Bool *RESTRICT success)
 
void SCIPcomputeBilinEnvelope2 (SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real xcoef1, SCIP_Real ycoef1, SCIP_Real constant1, SCIP_Real xcoef2, SCIP_Real ycoef2, SCIP_Real constant2, SCIP_Real *RESTRICT lincoefx, SCIP_Real *RESTRICT lincoefy, SCIP_Real *RESTRICT linconstant, SCIP_Bool *RESTRICT success)
 

Macro Definition Documentation

◆ NLHDLR_NAME

◆ NLHDLR_DESC

#define NLHDLR_DESC   "bilinear handler for expressions"

Definition at line 33 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ NLHDLR_DETECTPRIORITY

#define NLHDLR_DETECTPRIORITY   -10

it is important that the nlhdlr runs after the default nldhlr

Definition at line 34 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ NLHDLR_ENFOPRIORITY

#define NLHDLR_ENFOPRIORITY   -10

Definition at line 35 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ MIN_INTERIORITY

#define MIN_INTERIORITY   0.01

minimum interiority for a reference point for applying separation

Definition at line 37 of file nlhdlr_bilinear.c.

Referenced by useBilinIneqs().

◆ MIN_ABSBOUNDSIZE

#define MIN_ABSBOUNDSIZE   0.1

minimum size of variable bounds for applying separation

Definition at line 38 of file nlhdlr_bilinear.c.

Referenced by useBilinIneqs().

◆ TABLE_NAME_BILINEAR

#define TABLE_NAME_BILINEAR   "nlhdlr_bilinear"

Definition at line 41 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ TABLE_DESC_BILINEAR

#define TABLE_DESC_BILINEAR   "bilinear nlhdlr statistics table"

Definition at line 42 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ TABLE_POSITION_BILINEAR

#define TABLE_POSITION_BILINEAR   14800

the position of the statistics table

Definition at line 43 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ TABLE_EARLIEST_STAGE_BILINEAR

#define TABLE_EARLIEST_STAGE_BILINEAR   SCIP_STAGE_INITSOLVE

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

Definition at line 44 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ nlhdlrInitBilinear

#define nlhdlrInitBilinear   NULL

callback to be called in initialization

Definition at line 1102 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ nlhdlrInitSepaBilinear

#define nlhdlrInitSepaBilinear   NULL

separation initialization method of a nonlinear handler (called during CONSINITLP)

Definition at line 1243 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ nlhdlrExitSepaBilinear

#define nlhdlrExitSepaBilinear   NULL

separation deinitialization method of a nonlinear handler (called during CONSEXITSOL)

Definition at line 1246 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

◆ nlhdlrEnfoBilinear

#define nlhdlrEnfoBilinear   NULL

nonlinear handler separation callback

Definition at line 1249 of file nlhdlr_bilinear.c.

Referenced by SCIPincludeNlhdlrBilinear().

Function Documentation

◆ getIneqViol()

static void getIneqViol ( SCIP_VAR x,
SCIP_VAR y,
SCIP_Real  xcoef,
SCIP_Real  ycoef,
SCIP_Real  constant,
SCIP_Real viol1,
SCIP_Real viol2 
)
static

helper function to compute the violation of an inequality of the form xcoef * x <= ycoef * y + constant for two corner points of the domain [lbx,ubx] x [lby,uby]

Parameters
xfirst variable
ysecond variable
xcoefx-coefficient
ycoefy-coefficient
constantconstant
viol1buffer to store the violation of the first corner point
viol2buffer to store the violation of the second corner point

Definition at line 86 of file nlhdlr_bilinear.c.

References MAX, NULL, SCIP_Real, SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by SCIPaddIneqBilinear().

◆ useBilinIneqs()

static SCIP_Bool useBilinIneqs ( SCIP scip,
SCIP_VAR x,
SCIP_VAR y,
SCIP_Real  refx,
SCIP_Real  refy 
)
static

auxiliary function to decide whether to use inequalities for a strong relaxation of bilinear terms or not

Parameters
scipSCIP data structure
xx variable
yy variable
refxreference point for x
refyreference point for y

Definition at line 119 of file nlhdlr_bilinear.c.

References MAX, MIN_ABSBOUNDSIZE, MIN_INTERIORITY, NULL, SCIP_Real, SCIPepsilon(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_NLHDLRESTIMATE().

◆ updateBilinearRelaxation()

static void updateBilinearRelaxation ( SCIP scip,
SCIP_VAR *RESTRICT  x,
SCIP_VAR *RESTRICT  y,
SCIP_Real  bilincoef,
SCIP_SIDETYPE  violside,
SCIP_Real  refx,
SCIP_Real  refy,
SCIP_Real *RESTRICT  ineqs,
int  nineqs,
SCIP_Real  mccormickval,
SCIP_Real *RESTRICT  bestcoefx,
SCIP_Real *RESTRICT  bestcoefy,
SCIP_Real *RESTRICT  bestconst,
SCIP_Real *RESTRICT  bestval,
SCIP_Bool success 
)
static

helper function to update the best relaxation for a bilinear term when using valid linear inequalities

Parameters
scipSCIP data structure
xfirst variable
ysecond variable
bilincoefcoefficient of the bilinear term
violsideside of quadratic constraint that is violated
refxreference point for the x variable
refyreference point for the y variable
ineqscoefficients of each linear inequality; stored as triple (xcoef,ycoef,constant)
nineqstotal number of inequalities
mccormickvalvalue of the McCormick relaxation at the reference point
bestcoefxpointer to update the x coefficient
bestcoefypointer to update the y coefficient
bestconstpointer to update the constant
bestvalvalue of the best relaxation that have been found so far
successbuffer to store whether we found a better relaxation

Definition at line 155 of file nlhdlr_bilinear.c.

References MAX, NULL, REALABS, SCIP_Bool, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIPcomputeBilinEnvelope1(), SCIPcomputeBilinEnvelope2(), SCIPdebugMsg, SCIPisFeasGE(), SCIPisFeasLE(), SCIPisRelGT(), SCIPisRelLT(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by SCIP_DECL_NLHDLRESTIMATE().

◆ isPointFeasible()

static SCIP_Bool isPointFeasible ( SCIP scip,
SCIP_Real  x,
SCIP_Real  y,
SCIP_Real  lbx,
SCIP_Real  ubx,
SCIP_Real  lby,
SCIP_Real  uby,
SCIP_Real ineqs,
int  nineqs 
)
static

helper function to determine whether a given point satisfy given inequalities

Parameters
scipSCIP data structure
xx-coordinate
yy-coordinate
lbxlower bound of x
ubxupper bound of x
lbylower bound of y
ubyupper bound of y
ineqsinequalities of the form coefx x <= coefy y + constant
nineqstotal number of inequalities

Definition at line 273 of file nlhdlr_bilinear.c.

References FALSE, NULL, SCIP_Real, SCIPisGT(), SCIPisLT(), and TRUE.

Referenced by getFeasiblePointsBilinear(), and reversePropBilinear().

◆ getFeasiblePointsBilinear()

static void getFeasiblePointsBilinear ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_EXPR expr,
SCIP_INTERVAL  exprbounds,
SCIP_Real underineqs,
int  nunderineqs,
SCIP_Real overineqs,
int  noverineqs,
SCIP_Bool  levelset,
SCIP_Real xs,
SCIP_Real ys,
int *  npoints 
)
static

helper function for computing all vertices of the polytope described by the linear inequalities and the local extrema of the bilinear term along each inequality

Note
there are at most 22 points where the min/max can be achieved (given that there are at most 4 inequalities)
  • corners of [lbx,ubx]x[lby,uby] (4)
  • two intersection points for each inequality with the box (8)
  • global maximum / minimum on each inequality (4)
  • intersection between two inequalities (6)
Parameters
scipSCIP data structure
conshdlrconstraint handler, if levelset == TRUE, otherwise can be NULL
exprproduct expression
exprboundsbounds on product expression, only used if levelset == TRUE
underineqsinequalities for underestimation
nunderineqstotal number of inequalities for underestimation
overineqsinequalities for overestimation
noverineqstotal number of inequalities for overestimation
levelsetshould the level set be considered?
xsarray to store x-coordinates of computed points
ysarray to store y-coordinates of computed points
npointsbuffer to store the total number of computed points

Definition at line 320 of file nlhdlr_bilinear.c.

References SCIP_Interval::inf, isPointFeasible(), NULL, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPdebugMsg, SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPgetExprBoundsNonlinear(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalSet(), SCIPintervalSetBounds(), SCIPintervalSolveUnivariateQuadExpression(), SCIPisRelEQ(), SCIPisRelGE(), SCIPisRelLE(), SCIPisZero(), and SCIP_Interval::sup.

Referenced by intevalBilinear(), and reversePropBilinear().

◆ intevalBilinear()

static SCIP_INTERVAL intevalBilinear ( SCIP scip,
SCIP_EXPR expr,
SCIP_Real underineqs,
int  nunderineqs,
SCIP_Real overineqs,
int  noverineqs 
)
static

computes interval for a bilinear term when using at least one inequality

Parameters
scipSCIP data structure
exprproduct expression
underineqsinequalities for underestimation
nunderineqstotal number of inequalities for underestimation
overineqsinequalities for overestimation
noverineqstotal number of inequalities for overestimation

Definition at line 603 of file nlhdlr_bilinear.c.

References FALSE, getFeasiblePointsBilinear(), MAX, NULL, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPdebugMsg, SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPintervalIsEmpty(), SCIPintervalMulScalar(), SCIPintervalSetBounds(), SCIPintervalSetEmpty(), and SCIPintervalSetEntire().

Referenced by SCIP_DECL_NLHDLRINTEVAL().

◆ reversePropBilinear()

static void reversePropBilinear ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_EXPR expr,
SCIP_INTERVAL  exprbounds,
SCIP_Real underineqs,
int  nunderineqs,
SCIP_Real overineqs,
int  noverineqs,
SCIP_INTERVAL intervalx,
SCIP_INTERVAL intervaly 
)
static

uses inequalities for bilinear terms to get stronger bounds during reverse propagation

Parameters
scipSCIP data structure
conshdlrconstraint handler
exprproduct expression
exprboundsbounds on product expression
underineqsinequalities for underestimation
nunderineqstotal number of inequalities for underestimation
overineqsinequalities for overestimation
noverineqstotal number of inequalities for overestimation
intervalxbuffer to store the new interval for x
intervalybuffer to store the new interval for y

Definition at line 677 of file nlhdlr_bilinear.c.

References FALSE, getFeasiblePointsBilinear(), SCIP_Interval::inf, isPointFeasible(), MAX, NULL, SCIP_Bool, SCIP_Real, SCIPdebugMsg, SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPfeastol(), SCIPgetCoefExprProduct(), SCIPintervalSet(), SCIPintervalSetEmpty(), SCIPisRelGE(), SCIPisRelLE(), SCIP_Interval::sup, and TRUE.

Referenced by SCIP_DECL_NLHDLRREVERSEPROP().

◆ computeBilinEnvelope2()

static void computeBilinEnvelope2 ( SCIP scip,
SCIP_Real  x,
SCIP_Real  y,
SCIP_Real  mi,
SCIP_Real  qi,
SCIP_Real  mj,
SCIP_Real  qj,
SCIP_Real *RESTRICT  xi,
SCIP_Real *RESTRICT  yi,
SCIP_Real *RESTRICT  xj,
SCIP_Real *RESTRICT  yj,
SCIP_Real *RESTRICT  xcoef,
SCIP_Real *RESTRICT  ycoef,
SCIP_Real *RESTRICT  constant 
)
static

helper function to compute the convex envelope of a bilinear term when two linear inequalities are given; we use the same notation and formulas as in Locatelli 2016

Parameters
scipSCIP data structure
xreference point for x
yreference point for y
micoefficient of x in the first linear inequality
qiconstant in the first linear inequality
mjcoefficient of x in the second linear inequality
qjconstant in the second linear inequality
xibuffer to store x coordinate of the first point
yibuffer to store y coordinate of the first point
xjbuffer to store x coordinate of the second point
yjbuffer to store y coordinate of the second point
xcoefbuffer to store the x coefficient of the envelope
ycoefbuffer to store the y coefficient of the envelope
constantbuffer to store the constant of the envelope

Definition at line 770 of file nlhdlr_bilinear.c.

References EPSEQ, NULL, QUAD, QUAD_TO_DBL, REALABS, SCIP_Real, SCIPisEQ(), SCIPquadprecDivQD, SCIPquadprecDivQQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecSqrtQ, SCIPquadprecSquareQ, SCIPquadprecSumDD, SCIPquadprecSumQD, and SCIPquadprecSumQQ.

Referenced by SCIPcomputeBilinEnvelope2().

◆ SCIP_DECL_TABLEOUTPUT()

◆ SCIP_DECL_NLHDLRCOPYHDLR()

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrBilinear  )
static

nonlinear handler copy callback

Definition at line 1028 of file nlhdlr_bilinear.c.

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

◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

static SCIP_DECL_NLHDLRFREEHDLRDATA ( nlhdlrFreehdlrdataBilinear  )
static

callback to free data of handler

Definition at line 1041 of file nlhdlr_bilinear.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPhashmapFree(), and SCIPhashmapGetNElements().

◆ SCIP_DECL_NLHDLRFREEEXPRDATA()

static SCIP_DECL_NLHDLRFREEEXPRDATA ( nlhdlrFreeExprDataBilinear  )
static

◆ SCIP_DECL_NLHDLREXIT()

static SCIP_DECL_NLHDLREXIT ( nlhdlrExitBilinear  )
static

callback to be called in deinitialization

Definition at line 1106 of file nlhdlr_bilinear.c.

References NULL, SCIP_OKAY, and SCIPnlhdlrGetData().

◆ SCIP_DECL_NLHDLRDETECT()

◆ SCIP_DECL_NLHDLREVALAUX()

static SCIP_DECL_NLHDLREVALAUX ( nlhdlrEvalauxBilinear  )
static

auxiliary evaluation callback of nonlinear handler

Definition at line 1222 of file nlhdlr_bilinear.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), and SCIPisExprProduct().

◆ SCIP_DECL_NLHDLRESTIMATE()

◆ SCIP_DECL_NLHDLRINTEVAL()

static SCIP_DECL_NLHDLRINTEVAL ( nlhdlrIntevalBilinear  )
static

nonlinear handler interval evaluation callback

Definition at line 1383 of file nlhdlr_bilinear.c.

References SCIP_Interval::inf, intevalBilinear(), NULL, SCIP_OKAY, SCIPintervalIntersect(), SCIPisGT(), SCIPisLT(), SCIPnlhdlrGetData(), and SCIP_Interval::sup.

◆ SCIP_DECL_NLHDLRREVERSEPROP()

static SCIP_DECL_NLHDLRREVERSEPROP ( nlhdlrReversepropBilinear  )
static