bilinear nonlinear handler
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 |
#define NLHDLR_NAME "bilinear" |
Definition at line 41 of file nlhdlr_bilinear.c.
Referenced by SCIP_DECL_NLHDLRCOPYHDLR(), SCIP_DECL_NLHDLRCOPYHDLR(), SCIP_DECL_NLHDLRCOPYHDLR(), SCIP_DECL_NLHDLRCOPYHDLR(), SCIP_DECL_NLHDLRCOPYHDLR(), SCIP_DECL_NLHDLRCOPYHDLR(), SCIP_DECL_NLHDLRCOPYHDLR(), SCIP_DECL_TABLEOUTPUT(), SCIP_DECL_TABLEOUTPUT(), SCIPaddIneqBilinear(), SCIPgetExprsBilinear(), SCIPgetNExprsBilinear(), SCIPincludeNlhdlrBilinear(), SCIPincludeNlhdlrDefault(), SCIPincludeNlhdlrPerspective(), SCIPincludeNlhdlrQuadratic(), SCIPincludeNlhdlrQuotient(), SCIPincludeNlhdlrSignomial(), and SCIPincludeNlhdlrSoc().
#define NLHDLR_DESC "bilinear handler for expressions" |
Definition at line 42 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear(), SCIPincludeNlhdlrDefault(), SCIPincludeNlhdlrPerspective(), SCIPincludeNlhdlrQuadratic(), SCIPincludeNlhdlrQuotient(), SCIPincludeNlhdlrSignomial(), and SCIPincludeNlhdlrSoc().
#define NLHDLR_DETECTPRIORITY -10 |
it is important that the nlhdlr runs after the default nldhlr
Definition at line 43 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear(), SCIPincludeNlhdlrDefault(), SCIPincludeNlhdlrPerspective(), SCIPincludeNlhdlrQuadratic(), SCIPincludeNlhdlrQuotient(), SCIPincludeNlhdlrSignomial(), and SCIPincludeNlhdlrSoc().
#define NLHDLR_ENFOPRIORITY -10 |
Definition at line 44 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear(), SCIPincludeNlhdlrDefault(), SCIPincludeNlhdlrPerspective(), SCIPincludeNlhdlrQuadratic(), SCIPincludeNlhdlrQuotient(), SCIPincludeNlhdlrSignomial(), and SCIPincludeNlhdlrSoc().
#define MIN_INTERIORITY 0.01 |
minimum interiority for a reference point for applying separation
Definition at line 46 of file nlhdlr_bilinear.c.
Referenced by useBilinIneqs().
#define MIN_ABSBOUNDSIZE 0.1 |
minimum size of variable bounds for applying separation
Definition at line 47 of file nlhdlr_bilinear.c.
Referenced by useBilinIneqs().
#define TABLE_NAME_BILINEAR "nlhdlr_bilinear" |
Definition at line 50 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear().
#define TABLE_DESC_BILINEAR "bilinear nlhdlr statistics table" |
Definition at line 51 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear().
#define TABLE_POSITION_BILINEAR 14800 |
the position of the statistics table
Definition at line 52 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear().
#define TABLE_EARLIEST_STAGE_BILINEAR SCIP_STAGE_INITSOLVE |
output of the statistics table is only printed from this stage onwards
Definition at line 53 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear().
#define nlhdlrInitBilinear NULL |
callback to be called in initialization
Definition at line 1111 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear().
#define nlhdlrInitSepaBilinear NULL |
separation initialization method of a nonlinear handler (called during CONSINITLP)
Definition at line 1252 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear().
#define nlhdlrExitSepaBilinear NULL |
separation deinitialization method of a nonlinear handler (called during CONSEXITSOL)
Definition at line 1255 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear().
#define nlhdlrEnfoBilinear NULL |
nonlinear handler separation callback
Definition at line 1258 of file nlhdlr_bilinear.c.
Referenced by SCIPincludeNlhdlrBilinear().
|
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]
x | first variable |
y | second variable |
xcoef | x-coefficient |
ycoef | y-coefficient |
constant | constant |
viol1 | buffer to store the violation of the first corner point |
viol2 | buffer to store the violation of the second corner point |
Definition at line 95 of file nlhdlr_bilinear.c.
References assert(), MAX, NULL, SCIP_Real, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SQR, x, and y.
Referenced by SCIPaddIneqBilinear().
|
static |
auxiliary function to decide whether to use inequalities for a strong relaxation of bilinear terms or not
scip | SCIP data structure |
x | x variable |
y | y variable |
refx | reference point for x |
refy | reference point for y |
Definition at line 128 of file nlhdlr_bilinear.c.
References assert(), MAX, MIN, MIN_ABSBOUNDSIZE, MIN_INTERIORITY, NULL, SCIP_Bool, SCIP_Real, SCIPepsilon(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), x, and y.
Referenced by SCIP_DECL_NLHDLRESTIMATE().
|
static |
helper function to update the best relaxation for a bilinear term when using valid linear inequalities
scip | SCIP data structure |
x | first variable |
y | second variable |
bilincoef | coefficient of the bilinear term |
violside | side of quadratic constraint that is violated |
refx | reference point for the x variable |
refy | reference point for the y variable |
ineqs | coefficients of each linear inequality; stored as triple (xcoef,ycoef,constant) |
nineqs | total number of inequalities |
mccormickval | value of the McCormick relaxation at the reference point |
bestcoefx | pointer to update the x coefficient |
bestcoefy | pointer to update the y coefficient |
bestconst | pointer to update the constant |
bestval | value of the best relaxation that have been found so far |
success | buffer to store whether we found a better relaxation |
Definition at line 164 of file nlhdlr_bilinear.c.
References assert(), i, MAX, NULL, REALABS, RESTRICT, SCIP_Bool, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIPcomputeBilinEnvelope1(), SCIPcomputeBilinEnvelope2(), SCIPdebugMsg, SCIPisFeasGE(), SCIPisFeasLE(), SCIPisRelGT(), SCIPisRelLT(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, x, and y.
Referenced by SCIP_DECL_NLHDLRESTIMATE().
|
static |
helper function to determine whether a given point satisfy given inequalities
scip | SCIP data structure |
x | x-coordinate |
y | y-coordinate |
lbx | lower bound of x |
ubx | upper bound of x |
lby | lower bound of y |
uby | upper bound of y |
ineqs | inequalities of the form coefx x <= coefy y + constant |
nineqs | total number of inequalities |
Definition at line 282 of file nlhdlr_bilinear.c.
References assert(), FALSE, i, NULL, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLT(), TRUE, x, and y.
Referenced by getFeasiblePointsBilinear(), and reversePropBilinear().
|
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
scip | SCIP data structure |
conshdlr | constraint handler, if levelset == TRUE, otherwise can be NULL |
expr | product expression |
exprbounds | bounds on product expression, only used if levelset == TRUE |
underineqs | inequalities for underestimation |
nunderineqs | total number of inequalities for underestimation |
overineqs | inequalities for overestimation |
noverineqs | total number of inequalities for overestimation |
levelset | should the level set be considered? |
xs | array to store x-coordinates of computed points |
ys | array to store y-coordinates of computed points |
npoints | buffer to store the total number of computed points |
Definition at line 329 of file nlhdlr_bilinear.c.
References assert(), i, SCIP_Interval::inf, isPointFeasible(), NULL, result, SCIP_Bool, 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().
|
static |
computes interval for a bilinear term when using at least one inequality
scip | SCIP data structure |
expr | product expression |
underineqs | inequalities for underestimation |
nunderineqs | total number of inequalities for underestimation |
overineqs | inequalities for overestimation |
noverineqs | total number of inequalities for overestimation |
Definition at line 612 of file nlhdlr_bilinear.c.
References assert(), FALSE, getFeasiblePointsBilinear(), i, MAX, MIN, NULL, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPdebugMsg, SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPintervalIsEmpty(), SCIPintervalMulScalar(), SCIPintervalSetBounds(), SCIPintervalSetEmpty(), and SCIPintervalSetEntire().
Referenced by SCIP_DECL_NLHDLRINTEVAL().
|
static |
uses inequalities for bilinear terms to get stronger bounds during reverse propagation
scip | SCIP data structure |
conshdlr | constraint handler |
expr | product expression |
exprbounds | bounds on product expression |
underineqs | inequalities for underestimation |
nunderineqs | total number of inequalities for underestimation |
overineqs | inequalities for overestimation |
noverineqs | total number of inequalities for overestimation |
intervalx | buffer to store the new interval for x |
intervaly | buffer to store the new interval for y |
Definition at line 686 of file nlhdlr_bilinear.c.
References assert(), FALSE, getFeasiblePointsBilinear(), i, SCIP_Interval::inf, isPointFeasible(), MAX, MIN, 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().
|
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
scip | SCIP data structure |
x | reference point for x |
y | reference point for y |
mi | coefficient of x in the first linear inequality |
qi | constant in the first linear inequality |
mj | coefficient of x in the second linear inequality |
qj | constant in the second linear inequality |
xi | buffer to store x coordinate of the first point |
yi | buffer to store y coordinate of the first point |
xj | buffer to store x coordinate of the second point |
yj | buffer to store y coordinate of the second point |
xcoef | buffer to store the x coefficient of the envelope |
ycoef | buffer to store the y coefficient of the envelope |
constant | buffer to store the constant of the envelope |
Definition at line 779 of file nlhdlr_bilinear.c.
References assert(), computeBilinEnvelope2(), EPSEQ, NULL, QUAD, QUAD_TO_DBL, REALABS, RESTRICT, SCIP_Real, SCIPisEQ(), SCIPquadprecDivQD, SCIPquadprecDivQQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecSqrtQ, SCIPquadprecSquareQ, SCIPquadprecSumDD, SCIPquadprecSumQD, SCIPquadprecSumQQ, x, and y.
Referenced by computeBilinEnvelope2(), and SCIPcomputeBilinEnvelope2().
|
static |
output method of statistics table to output file stream 'file'
Definition at line 953 of file nlhdlr_bilinear.c.
References assert(), c, FALSE, NLHDLR_NAME, NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_OKAY, SCIPblkmem(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateExpriter(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPfindConshdlr(), SCIPfindNlhdlrNonlinear(), SCIPfreeExpriter(), SCIPgetExprNonlinear(), SCIPgetNlhdlrExprDataNonlinear(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPhashmapSetImageInt(), SCIPinfoMessage(), and SCIPnlhdlrGetData().
|
static |
nonlinear handler copy callback
Definition at line 1037 of file nlhdlr_bilinear.c.
References assert(), NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrBilinear(), and SCIPnlhdlrGetName().
|
static |
callback to free data of handler
Definition at line 1050 of file nlhdlr_bilinear.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPhashmapFree(), and SCIPhashmapGetNElements().
|
static |
callback to free expression specific data
Definition at line 1069 of file nlhdlr_bilinear.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryNull, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapRemove(), SCIPhashmapSetImageInt(), SCIPnlhdlrGetData(), and SCIPreleaseExpr().
|
static |
callback to be called in deinitialization
Definition at line 1115 of file nlhdlr_bilinear.c.
References assert(), NULL, SCIP_OKAY, and SCIPnlhdlrGetData().
|
static |
callback to detect structure in expression tree
Definition at line 1125 of file nlhdlr_bilinear.c.
References assert(), c, FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIP_STAGE_INITSOLVE, SCIPallocClearBlockMemory, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPcaptureExpr(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetExprNAuxvarUsesNonlinear(), SCIPgetNVars(), SCIPgetStage(), SCIPgetVarExprVar(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapInsertInt(), SCIPinfoMessage(), SCIPisExprProduct(), SCIPisExprVar(), SCIPnlhdlrGetData(), SCIPprintExpr(), SCIPreallocBlockMemoryArray, SCIPregisterExprUsageNonlinear(), SCIPvarIsBinary(), TRUE, and valid.
|
static |
auxiliary evaluation callback of nonlinear handler
Definition at line 1231 of file nlhdlr_bilinear.c.
References assert(), NULL, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), SCIPisExprProduct(), and sol.
|
static |
nonlinear handler under/overestimation callback
Definition at line 1262 of file nlhdlr_bilinear.c.
References assert(), FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPaddBilinMcCormick(), SCIPaddRowprepTerm(), SCIPcreateRowprep(), SCIPensureRowprepSize(), SCIPexprGetChildren(), SCIPgetCoefExprProduct(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetExprAuxVarNonlinear(), SCIPgetSolVal(), SCIPisFeasLE(), SCIPisGE(), SCIPisLE(), SCIPnlhdlrGetData(), SCIPnodeGetNumber(), SCIProwprepAddConstant(), SCIPsetPtrarrayVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), sol, TRUE, updateBilinearRelaxation(), useBilinIneqs(), x, and y.
|
static |
nonlinear handler interval evaluation callback
Definition at line 1392 of file nlhdlr_bilinear.c.
References assert(), SCIP_Interval::inf, intevalBilinear(), NULL, SCIP_OKAY, SCIPintervalIntersect(), SCIPisGT(), SCIPisLT(), SCIPnlhdlrGetData(), and SCIP_Interval::sup.
|
static |
nonlinear handler callback for reverse propagation
Definition at line 1415 of file nlhdlr_bilinear.c.
References assert(), SCIP_Interval::inf, NULL, reversePropBilinear(), SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetExprBoundsNonlinear(), SCIPintervalSetEntire(), SCIPnlhdlrGetData(), SCIPtightenExprIntervalNonlinear(), and SCIP_Interval::sup.