perspective nonlinear handler
Definition in file nlhdlr_perspective.c.
#include <string.h>
#include "scip/nlhdlr_perspective.h"
#include "scip/cons_nonlinear.h"
#include "scip/scip_sol.h"
#include "scip/pub_misc_rowprep.h"
#include "scip/nlhdlr.h"
Go to the source code of this file.
Data Structures | |
struct | SCVarData |
Macros | |
#define | NLHDLR_NAME "perspective" |
#define | NLHDLR_DESC "perspective handler for expressions" |
#define | NLHDLR_DETECTPRIORITY -20 |
#define | NLHDLR_ENFOPRIORITY 125 |
#define | DEFAULT_MAXPROPROUNDS 1 |
#define | DEFAULT_MINDOMREDUCTION 0.1 |
#define | DEFAULT_MINVIOLPROBING 1e-05 |
#define | DEFAULT_PROBINGONLYINSEPA TRUE |
#define | DEFAULT_PROBINGFREQ 1 |
#define | DEFAULT_CONVEXONLY FALSE |
#define | DEFAULT_TIGHTENBOUNDS TRUE |
#define | DEFAULT_ADJREFPOINT TRUE |
#define NLHDLR_NAME "perspective" |
Definition at line 40 of file nlhdlr_perspective.c.
#define NLHDLR_DESC "perspective handler for expressions" |
Definition at line 41 of file nlhdlr_perspective.c.
#define NLHDLR_DETECTPRIORITY -20 |
detect last so that to make use of what other handlers detected
Definition at line 42 of file nlhdlr_perspective.c.
#define NLHDLR_ENFOPRIORITY 125 |
enforce first because perspective cuts are always stronger
Definition at line 43 of file nlhdlr_perspective.c.
#define DEFAULT_MAXPROPROUNDS 1 |
maximal number of propagation rounds in probing
Definition at line 45 of file nlhdlr_perspective.c.
#define DEFAULT_MINDOMREDUCTION 0.1 |
minimal relative reduction in a variable's domain for applying probing
Definition at line 46 of file nlhdlr_perspective.c.
Referenced by SCIPincludeNlhdlrPerspective().
#define DEFAULT_MINVIOLPROBING 1e-05 |
minimal violation w.r.t. auxiliary variables for applying probing
Definition at line 47 of file nlhdlr_perspective.c.
Referenced by SCIPincludeNlhdlrPerspective().
#define DEFAULT_PROBINGONLYINSEPA TRUE |
whether to do probing only in separation loop
Definition at line 48 of file nlhdlr_perspective.c.
Referenced by SCIPincludeNlhdlrPerspective().
#define DEFAULT_PROBINGFREQ 1 |
probing frequency (-1 - no probing, 0 - root node only)
Definition at line 49 of file nlhdlr_perspective.c.
Referenced by SCIPincludeNlhdlrPerspective().
#define DEFAULT_CONVEXONLY FALSE |
whether perspective cuts are added only for convex expressions
Definition at line 50 of file nlhdlr_perspective.c.
Referenced by SCIPincludeNlhdlrPerspective().
#define DEFAULT_TIGHTENBOUNDS TRUE |
whether variable semicontinuity is used to tighten variable bounds
Definition at line 51 of file nlhdlr_perspective.c.
Referenced by SCIPincludeNlhdlrPerspective().
#define DEFAULT_ADJREFPOINT TRUE |
whether to adjust the reference point if indicator is not 1
Definition at line 52 of file nlhdlr_perspective.c.
Referenced by SCIPincludeNlhdlrPerspective().
|
static |
frees nlhdlrexprdata structure
scip | SCIP data structure |
nlhdlrexprdata | nlhdlr expression data |
Definition at line 120 of file nlhdlr_perspective.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().
Referenced by SCIP_DECL_NLHDLRFREEEXPRDATA().
|
static |
scip | SCIP data structure |
nlexprdata | nlhdlr expression data |
pos | position of the indicator |
Definition at line 149 of file nlhdlr_perspective.c.
References assert(), i, SCIP_CALL, SCIP_OKAY, and SCIPreleaseVar().
Referenced by computeOffValues().
|
static |
adds an auxiliary variable to the vars array in nlhdlrexprdata
scip | SCIP data structure |
nlhdlrexprdata | nlhdlr expression data |
auxvarmap | hashmap linking auxvars to positions in nlhdlrexprdata->vars |
auxvar | variable to be added |
Definition at line 172 of file nlhdlr_perspective.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPcaptureVar(), SCIPhashmapGetImageInt(), SCIPhashmapSetImageInt(), and SCIPreallocBlockMemoryArray.
Referenced by computeOffValues().
|
static |
adds an indicator to the data of a semicontinuous variable
scip | SCIP data structure |
scvdata | semicontinuous variable data |
indicator | indicator to be added |
val0 | value of the variable when indicator == 0 |
lb1 | lower bound of the variable when indicator == 1 |
ub1 | upper bound of the variable when indicator == 1 |
Definition at line 213 of file nlhdlr_perspective.c.
References assert(), SCVarData::bndssize, SCVarData::bvars, FALSE, i, SCVarData::lbs1, SCVarData::nbnds, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, SCIPsortedvecFindPtr(), SCVarData::ubs1, and SCVarData::vals0.
Referenced by computeOffValues(), and varIsSemicontinuous().
|
static |
find scvardata of var and position of indicator in it
If indicator is not there, returns NULL.
scvars | hashmap linking variables to scvardata |
var | variable |
indicator | indicator variable |
pos | pointer to store the position of indicator |
Definition at line 282 of file nlhdlr_perspective.c.
References assert(), SCVarData::bvars, SCVarData::nbnds, NULL, SCIP_Bool, SCIPhashmapGetImage(), SCIPsortedvecFindPtr(), and var.
Referenced by analyseVarOnoffBounds(), computeOffValues(), SCIP_DECL_NLHDLRENFO(), and tightenOnBounds().
|
static |
checks if a variable is semicontinuous and, if needed, updates the scvars hashmap
A variable \(x\) is semicontinuous if its bounds depend on at least one binary variable called the indicator, and indicator = 0 ⇒ \(x = x^0\) for some real constant \(x^0\).
scip | SCIP data structure |
var | the variable to check |
scvars | semicontinuous variable information |
result | buffer to store whether var is semicontinuous |
Definition at line 316 of file nlhdlr_perspective.c.
References addSCVarIndicator(), assert(), SCVarData::bvars, c, FALSE, MAX, MIN, SCVarData::nbnds, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocClearBlockMemory, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPisEQ(), SCIPsortedvecFindPtr(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), TRUE, SCVarData::vals0, and var.
Referenced by exprIsSemicontinuous().
|
static |
scip | SCIP data structure |
nlhdlrdata | nonlinear handler data |
nlhdlrexprdata | nlhdlr expression data |
expr | expression |
res | buffer to store whether the expression is semicontinuous |
Definition at line 479 of file nlhdlr_perspective.c.
References assert(), SCVarData::bvars, c, FALSE, SCVarData::nbnds, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_OKAY, SCIPallocClearBufferArray, SCIPcaptureVar(), SCIPcomputeArraysIntersectionPtr(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArrayNull, SCIPfreeExpriter(), SCIPgetVarExprVar(), SCIPhashmapGetImage(), SCIPisExprSum(), SCIPisExprVar(), SCIPreallocBlockMemoryArray, SCIPsortedvecFindPtr(), SCIPvarGetName(), SCIPvarIsRelaxationOnly(), TRUE, var, and varIsSemicontinuous().
Referenced by SCIP_DECL_NLHDLRDETECT().
|
static |
computes the 'off' value of the expression and the 'off' values of semicontinuous auxiliary variables for each indicator variable
scip | SCIP data structure |
nlhdlrdata | nonlinear handler data |
nlhdlrexprdata | nlhdlr expression data |
expr | expression |
Definition at line 661 of file nlhdlr_perspective.c.
References addAuxVar(), addSCVarIndicator(), assert(), SCVarData::bndssize, SCVarData::bvars, FALSE, getSCVarDataInd(), i, SCVarData::lbs1, NULL, removeIndicator(), SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocClearBlockMemory, SCIPblkmem(), SCIPcreateExpriter(), SCIPcreateSol(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPevalExpr(), SCIPexprGetEvalValue(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPfreeSol(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprVarExprs(), SCIPgetVarExprVar(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPisExprSum(), SCIPisExprVar(), SCIPreleaseExpr(), SCIPsetSolVals(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), sol, TRUE, SCVarData::ubs1, SCVarData::vals0, and var.
Referenced by SCIP_DECL_NLHDLRINITSEPA().
|
static |
go into probing and set some variable bounds
scip | SCIP data structure |
nlhdlrdata | nonlinear handler data |
nlhdlrexprdata | nlhdlr expression data |
indicator | indicator variable |
probingvars | array of vars whose bounds we will change in probing |
probingdoms | array of intervals to which bounds of probingvars will be changed in probing |
nprobingvars | number of probing vars |
sol | solution to be separated |
solcopy | buffer for a copy of sol before going into probing; if *solcopy == sol, then copy is created |
cutoff_probing | pointer to store whether indicator == 1 is infeasible |
Definition at line 839 of file nlhdlr_perspective.c.
References NULL, propagate, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPcreateSol(), SCIPgetDepth(), SCIPgetSolVal(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPisGT(), SCIPisLT(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPsetSolVal(), SCIPstartProbing(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and sol.
Referenced by SCIP_DECL_NLHDLRENFO().
|
static |
analyse on/off bounds on a variable
analyses for
probinglb and probingub are only set if doprobing is TRUE. They are either set to bounds that should be used in probing or to SCIP_INVALID if bounds on var shouldn't be changed in probing.
scip | SCIP data structure |
nlhdlrdata | nonlinear handler data |
var | variable |
indicator | indicator variable |
indvalue | indicator value for which the bounds are applied |
infeas | pointer to store whether infeasibility has been detected |
probinglb | pointer to store the lower bound to be applied in probing |
probingub | pointer to store the upper bound to be applied in probing |
doprobing | whether we currently consider to go into probing |
reduceddom | pointer to store whether any variables were fixed |
Definition at line 922 of file nlhdlr_perspective.c.
References assert(), FALSE, getSCVarDataInd(), SCVarData::lbs1, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPfixVar(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisGT(), SCIPisLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCVarData::ubs1, SCVarData::vals0, and var.
Referenced by analyseOnoffBounds().
|
static |
looks for bound tightenings to be applied either in the current node or in probing
Loops through both possible values of indicator and calls analyseVarOnoffBounds(). Might update the *doprobing flag by setting it to FALSE if:
If *doprobing==TRUE, stores bounds suggested by analyseVarOnoffBounds() in order to apply them in probing together with the fixing indicator=1.
scip | SCIP data structure |
nlhdlrdata | nonlinear handler data |
nlhdlrexprdata | nlhdlr expression data |
indicator | indicator variable |
probingvars | array to store variables whose bounds will be changed in probing |
probingdoms | array to store bounds to be applied in probing |
nprobingvars | pointer to store number of vars whose bounds will be changed in probing |
doprobing | pointer to the flag telling whether we want to do probing |
result | pointer to store the result |
Definition at line 1080 of file nlhdlr_perspective.c.
References analyseVarOnoffBounds(), assert(), b, FALSE, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPreallocBufferArray, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by SCIP_DECL_NLHDLRENFO().
|
static |
saves local bounds on all expression variables, including auxiliary variables, obtained from propagating indicator == 1 to the corresponding SCVARDATA (should only be used in the root node)
nlhdlrexprdata | nlhdlr expression data |
scvars | hashmap with semicontinuous variables |
indicator | indicator variable |
Definition at line 1176 of file nlhdlr_perspective.c.
References getSCVarDataInd(), SCVarData::lbs1, MAX, MIN, NULL, SCIP_OKAY, SCIP_Real, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCVarData::ubs1, and var.
Referenced by SCIP_DECL_NLHDLRENFO().
|
static |
nonlinear handler copy callback
Definition at line 1212 of file nlhdlr_perspective.c.
References assert(), NLHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeNlhdlrPerspective(), and SCIPnlhdlrGetName().
|
static |
callback to free data of handler
Definition at line 1226 of file nlhdlr_perspective.c.
References SCIP_OKAY, and SCIPfreeBlockMemory.
|
static |
callback to free expression specific data
Definition at line 1236 of file nlhdlr_perspective.c.
References freeNlhdlrExprData(), SCIP_CALL, SCIP_OKAY, and SCIPfreeBlockMemory.
|
static |
callback to be called in deinitialization
Definition at line 1246 of file nlhdlr_perspective.c.
References assert(), SCVarData::bndssize, SCVarData::bvars, c, SCVarData::lbs1, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPhashmapEntryGetImage(), SCIPhashmapFree(), SCIPhashmapGetEntry(), SCIPhashmapGetNEntries(), SCIPnlhdlrGetData(), SCVarData::ubs1, and SCVarData::vals0.
|
static |
callback to detect structure in expression tree
We are looking for expressions g(x), where x is a vector of semicontinuous variables that all share at least one indicator variable.
Definition at line 1284 of file nlhdlr_perspective.c.
References assert(), exprIsSemicontinuous(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocClearBlockMemory, SCIPblkmem(), SCIPcaptureVar(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBufferArray, SCIPgetExprEnfoDataNonlinear(), SCIPgetExprNAuxvarUsesNonlinear(), SCIPgetExprNEnfosNonlinear(), SCIPgetExprNVars(), SCIPgetExprVarExprs(), SCIPgetNBinVars(), SCIPgetNVars(), SCIPgetVarExprVar(), SCIPhashmapCreate(), SCIPinfoMessage(), SCIPisExprSum(), SCIPnlhdlrGetData(), SCIPnlhdlrGetName(), SCIPnlhdlrHasEstimate(), SCIPprintExpr(), SCIPreleaseExpr(), SCIPsortPtr(), and TRUE.
|
static |
auxiliary evaluation callback of nonlinear handler
Definition at line 1419 of file nlhdlr_perspective.c.
References assert(), NULL, REALABS, SCIP_CALL, SCIP_INVALID, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIP_Real, SCIPgetExprAuxVarNonlinear(), SCIPgetExprEnfoDataNonlinear(), SCIPgetExprNEnfosNonlinear(), SCIPgetSolVal(), SCIPnlhdlrHasEstimate(), SCIPsetExprEnfoAuxValueNonlinear(), and sol.
|
static |
separation initialization method of a nonlinear handler
Definition at line 1465 of file nlhdlr_perspective.c.
References computeOffValues(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPnlhdlrGetData(), and SCIPreallocBlockMemoryArray.
|
static |
nonlinear handler enforcement callback
"Perspectivies" cuts produced by other nonlinear handlers.
Suppose that we want to separate \(x\) from the set \(\{ x : g(x) \leq 0\}\). If \(g(x) = g^0\) if indicator \(z = 0\), and a cut is given by \(\sum_i a_ix_i + c \leq \text{aux}\), where \(x_i = x_i^0\) if \(z = 0\) for all \(i\), then the "perspectivied" cut is
\[\sum_i a_ix_i + c + (1 - z)\,(g^0 - c - \sum_i a_ix_i^0) \leq \text{aux}.\]
This ensures that at \(z = 1\), the new cut is equivalent to the given cut, and at \(z = 0\) it reduces to \(g^0 \leq \text{aux}\).
Definition at line 1499 of file nlhdlr_perspective.c.
References analyseOnoffBounds(), assert(), cutoff, FALSE, getSCVarDataInd(), i, MAX, NULL, propagate, r, REALABS, result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_INVALIDRESULT, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIP_VARSTATUS_FIXED, SCIPaddRowprepTerm(), SCIPallocBufferArray, SCIPclearPtrarray(), SCIPcreateBoolarray(), SCIPcreatePtrarray(), SCIPcreateSol(), SCIPdebugMsg, SCIPendProbing(), SCIPerrorMessage, SCIPfeastol(), SCIPfixVar(), SCIPfreeBoolarray(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreePtrarray(), SCIPfreeRowprep(), SCIPfreeSol(), SCIPgetBoolarrayVal(), SCIPgetDepth(), SCIPgetExprAbsAuxViolationNonlinear(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprEnfoDataNonlinear(), SCIPgetExprNEnfosNonlinear(), SCIPgetPtrarrayMaxIdx(), SCIPgetPtrarrayMinIdx(), SCIPgetPtrarrayVal(), SCIPgetSolVal(), SCIPgetSubscipDepth(), SCIPinfoMessage(), SCIPinProbing(), SCIPisFeasEQ(), SCIPnlhdlrGetData(), SCIPnlhdlrGetName(), SCIPnlhdlrHasEstimate(), SCIPprintExpr(), SCIPprintRowprep(), SCIPprocessRowprepNonlinear(), SCIProwprepAddConstant(), SCIProwprepGetCoefs(), SCIProwprepGetName(), SCIProwprepGetNVars(), SCIProwprepGetSide(), SCIProwprepGetVars(), SCIPsetBoolarrayVal(), SCIPsetPtrarrayVal(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), sol, startProbing(), tightenOnBounds(), TRUE, and SCVarData::vals0.