Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

perspective nonlinear handler

Author
Ksenia Bestuzheva

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
 

Typedefs

typedef struct SCVarData SCVARDATA
 

Functions

static SCIP_RETCODE freeNlhdlrExprData (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
 
static SCIP_RETCODE removeIndicator (SCIP *scip, SCIP_NLHDLREXPRDATA *nlexprdata, int pos)
 
static SCIP_RETCODE addAuxVar (SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_HASHMAP *auxvarmap, SCIP_VAR *auxvar)
 
static SCIP_RETCODE addSCVarIndicator (SCIP *scip, SCVARDATA *scvdata, SCIP_VAR *indicator, SCIP_Real val0, SCIP_Real lb1, SCIP_Real ub1)
 
static SCVARDATAgetSCVarDataInd (SCIP_HASHMAP *scvars, SCIP_VAR *var, SCIP_VAR *indicator, int *pos)
 
static SCIP_RETCODE varIsSemicontinuous (SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *scvars, SCIP_Bool *result)
 
static SCIP_RETCODE exprIsSemicontinuous (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_EXPR *expr, SCIP_Bool *res)
 
static SCIP_RETCODE computeOffValues (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_EXPR *expr)
 
static SCIP_RETCODE startProbing (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *indicator, SCIP_VAR **probingvars, SCIP_INTERVAL *probingdoms, int nprobingvars, SCIP_SOL *sol, SCIP_SOL **solcopy, SCIP_Bool *cutoff_probing)
 
static SCIP_RETCODE analyseVarOnoffBounds (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_VAR *var, SCIP_VAR *indicator, SCIP_Bool indvalue, SCIP_Bool *infeas, SCIP_Real *probinglb, SCIP_Real *probingub, SCIP_Bool doprobing, SCIP_Bool *reduceddom)
 
static SCIP_RETCODE analyseOnoffBounds (SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *indicator, SCIP_VAR ***probingvars, SCIP_INTERVAL **probingdoms, int *nprobingvars, SCIP_Bool *doprobing, SCIP_RESULT *result)
 
static SCIP_RETCODE tightenOnBounds (SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_HASHMAP *scvars, SCIP_VAR *indicator)
 
static SCIP_DECL_NLHDLRCOPYHDLR (nlhdlrCopyhdlrPerspective)
 
static SCIP_DECL_NLHDLRFREEHDLRDATA (nlhdlrFreehdlrdataPerspective)
 
static SCIP_DECL_NLHDLRFREEEXPRDATA (nlhdlrFreeExprDataPerspective)
 
static SCIP_DECL_NLHDLREXIT (nlhdlrExitPerspective)
 
static SCIP_DECL_NLHDLRDETECT (nlhdlrDetectPerspective)
 
static SCIP_DECL_NLHDLREVALAUX (nlhdlrEvalauxPerspective)
 
static SCIP_DECL_NLHDLRINITSEPA (nlhdlrInitSepaPerspective)
 
static SCIP_DECL_NLHDLRENFO (nlhdlrEnfoPerspective)
 
SCIP_RETCODE SCIPincludeNlhdlrPerspective (SCIP *scip)
 

Macro Definition Documentation

◆ NLHDLR_NAME

#define NLHDLR_NAME   "perspective"

Definition at line 40 of file nlhdlr_perspective.c.

◆ NLHDLR_DESC

#define NLHDLR_DESC   "perspective handler for expressions"

Definition at line 41 of file nlhdlr_perspective.c.

◆ NLHDLR_DETECTPRIORITY

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

◆ NLHDLR_ENFOPRIORITY

#define NLHDLR_ENFOPRIORITY   125

enforce first because perspective cuts are always stronger

Definition at line 43 of file nlhdlr_perspective.c.

◆ DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS   1

maximal number of propagation rounds in probing

Definition at line 45 of file nlhdlr_perspective.c.

◆ DEFAULT_MINDOMREDUCTION

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

◆ DEFAULT_MINVIOLPROBING

#define DEFAULT_MINVIOLPROBING   1e-05

minimal violation w.r.t. auxiliary variables for applying probing

Definition at line 47 of file nlhdlr_perspective.c.

◆ DEFAULT_PROBINGONLYINSEPA

#define DEFAULT_PROBINGONLYINSEPA   TRUE

whether to do probing only in separation loop

Definition at line 48 of file nlhdlr_perspective.c.

◆ DEFAULT_PROBINGFREQ

#define DEFAULT_PROBINGFREQ   1

probing frequency (-1 - no probing, 0 - root node only)

Definition at line 49 of file nlhdlr_perspective.c.

◆ DEFAULT_CONVEXONLY

#define DEFAULT_CONVEXONLY   FALSE

whether perspective cuts are added only for convex expressions

Definition at line 50 of file nlhdlr_perspective.c.

◆ DEFAULT_TIGHTENBOUNDS

#define DEFAULT_TIGHTENBOUNDS   TRUE

whether variable semicontinuity is used to tighten variable bounds

Definition at line 51 of file nlhdlr_perspective.c.

◆ DEFAULT_ADJREFPOINT

#define DEFAULT_ADJREFPOINT   TRUE

whether to adjust the reference point if indicator is not 1

Definition at line 52 of file nlhdlr_perspective.c.

Typedef Documentation

◆ SCVARDATA

typedef struct SCVarData SCVARDATA

Definition at line 74 of file nlhdlr_perspective.c.

Function Documentation

◆ freeNlhdlrExprData()

static SCIP_RETCODE freeNlhdlrExprData ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata 
)
static

frees nlhdlrexprdata structure

Parameters
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data

Definition at line 120 of file nlhdlr_perspective.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().

Referenced by SCIP_DECL_NLHDLRFREEEXPRDATA().

◆ removeIndicator()

static SCIP_RETCODE removeIndicator ( SCIP scip,
SCIP_NLHDLREXPRDATA nlexprdata,
int  pos 
)
static
Parameters
scipSCIP data structure
nlexprdatanlhdlr expression data
posposition of the indicator

Definition at line 149 of file nlhdlr_perspective.c.

References SCIP_CALL, SCIP_OKAY, and SCIPreleaseVar().

Referenced by computeOffValues().

◆ addAuxVar()

static SCIP_RETCODE addAuxVar ( SCIP scip,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_HASHMAP auxvarmap,
SCIP_VAR auxvar 
)
static

adds an auxiliary variable to the vars array in nlhdlrexprdata

Parameters
scipSCIP data structure
nlhdlrexprdatanlhdlr expression data
auxvarmaphashmap linking auxvars to positions in nlhdlrexprdata->vars
auxvarvariable to be added

Definition at line 172 of file nlhdlr_perspective.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPcaptureVar(), SCIPhashmapGetImageInt(), SCIPhashmapSetImageInt(), and SCIPreallocBlockMemoryArray.

Referenced by computeOffValues().

◆ addSCVarIndicator()

static SCIP_RETCODE addSCVarIndicator ( SCIP scip,
SCVARDATA scvdata,
SCIP_VAR indicator,
SCIP_Real  val0,
SCIP_Real  lb1,
SCIP_Real  ub1 
)
static

adds an indicator to the data of a semicontinuous variable

Parameters
scipSCIP data structure
scvdatasemicontinuous variable data
indicatorindicator to be added
val0value of the variable when indicator == 0
lb1lower bound of the variable when indicator == 1
ub1upper bound of the variable when indicator == 1

Definition at line 213 of file nlhdlr_perspective.c.

References SCVarData::bndssize, SCVarData::bvars, FALSE, SCVarData::lbs1, SCVarData::nbnds, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, SCIPsortedvecFindPtr(), SCVarData::ubs1, and SCVarData::vals0.

Referenced by computeOffValues(), and varIsSemicontinuous().

◆ getSCVarDataInd()

static SCVARDATA * getSCVarDataInd ( SCIP_HASHMAP scvars,
SCIP_VAR var,
SCIP_VAR indicator,
int *  pos 
)
static

find scvardata of var and position of indicator in it

If indicator is not there, returns NULL.

Parameters
scvarshashmap linking variables to scvardata
varvariable
indicatorindicator variable
pospointer to store the position of indicator

Definition at line 282 of file nlhdlr_perspective.c.

References SCVarData::bvars, SCVarData::nbnds, NULL, SCIP_Bool, SCIPhashmapGetImage(), and SCIPsortedvecFindPtr().

Referenced by analyseVarOnoffBounds(), computeOffValues(), SCIP_DECL_NLHDLRENFO(), and tightenOnBounds().

◆ varIsSemicontinuous()

static SCIP_RETCODE varIsSemicontinuous ( SCIP scip,
SCIP_VAR var,
SCIP_HASHMAP scvars,
SCIP_Bool result 
)
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\).

Parameters
scipSCIP data structure
varthe variable to check
scvarssemicontinuous variable information
resultbuffer to store whether var is semicontinuous

Definition at line 316 of file nlhdlr_perspective.c.

References addSCVarIndicator(), SCVarData::bvars, FALSE, MAX, MIN, SCVarData::nbnds, NULL, 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, and SCVarData::vals0.

Referenced by exprIsSemicontinuous().

◆ exprIsSemicontinuous()

◆ computeOffValues()

◆ startProbing()

static SCIP_RETCODE startProbing ( SCIP scip,
SCIP_NLHDLRDATA nlhdlrdata,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_VAR indicator,
SCIP_VAR **  probingvars,
SCIP_INTERVAL probingdoms,
int  nprobingvars,
SCIP_SOL sol,
SCIP_SOL **  solcopy,
SCIP_Bool cutoff_probing 
)
static

go into probing and set some variable bounds

Parameters
scipSCIP data structure
nlhdlrdatanonlinear handler data
nlhdlrexprdatanlhdlr expression data
indicatorindicator variable
probingvarsarray of vars whose bounds we will change in probing
probingdomsarray of intervals to which bounds of probingvars will be changed in probing
nprobingvarsnumber of probing vars
solsolution to be separated
solcopybuffer for a copy of sol before going into probing; if *solcopy == sol, then copy is created
cutoff_probingpointer to store whether indicator == 1 is infeasible

Definition at line 839 of file nlhdlr_perspective.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPcreateSol(), SCIPgetDepth(), SCIPgetSolVal(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPisGT(), SCIPisLT(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPsetSolVal(), SCIPstartProbing(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_NLHDLRENFO().

◆ analyseVarOnoffBounds()

static SCIP_RETCODE analyseVarOnoffBounds ( SCIP scip,
SCIP_NLHDLRDATA nlhdlrdata,
SCIP_VAR var,
SCIP_VAR indicator,
SCIP_Bool  indvalue,
SCIP_Bool infeas,
SCIP_Real probinglb,
SCIP_Real probingub,
SCIP_Bool  doprobing,
SCIP_Bool reduceddom 
)
static

analyse on/off bounds on a variable

analyses for

  1. tightening bounds in probing for indicator = 1,
  2. fixing indicator / detecting cutoff if one or both states are infeasible,
  3. tightening local bounds if indicator is fixed.

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.

Parameters
scipSCIP data structure
nlhdlrdatanonlinear handler data
varvariable
indicatorindicator variable
indvalueindicator value for which the bounds are applied
infeaspointer to store whether infeasibility has been detected
probinglbpointer to store the lower bound to be applied in probing
probingubpointer to store the upper bound to be applied in probing
doprobingwhether we currently consider to go into probing
reduceddompointer to store whether any variables were fixed

Definition at line 922 of file nlhdlr_perspective.c.

References 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, and SCVarData::vals0.

Referenced by analyseOnoffBounds().

◆ analyseOnoffBounds()

static SCIP_RETCODE analyseOnoffBounds ( SCIP scip,
SCIP_NLHDLRDATA nlhdlrdata,
SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_VAR indicator,
SCIP_VAR ***  probingvars,
SCIP_INTERVAL **  probingdoms,
int *  nprobingvars,
SCIP_Bool doprobing,
SCIP_RESULT result 
)
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.

Parameters
scipSCIP data structure
nlhdlrdatanonlinear handler data
nlhdlrexprdatanlhdlr expression data
indicatorindicator variable
probingvarsarray to store variables whose bounds will be changed in probing
probingdomsarray to store bounds to be applied in probing
nprobingvarspointer to store number of vars whose bounds will be changed in probing
doprobingpointer to the flag telling whether we want to do probing
resultpointer to store the result

Definition at line 1080 of file nlhdlr_perspective.c.

References analyseVarOnoffBounds(), b, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPreallocBufferArray, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by SCIP_DECL_NLHDLRENFO().

◆ tightenOnBounds()

static SCIP_RETCODE tightenOnBounds ( SCIP_NLHDLREXPRDATA nlhdlrexprdata,
SCIP_HASHMAP scvars,
SCIP_VAR indicator 
)
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)

Parameters
nlhdlrexprdatanlhdlr expression data
scvarshashmap with semicontinuous variables
indicatorindicator variable

Definition at line 1176 of file nlhdlr_perspective.c.

References getSCVarDataInd(), SCVarData::lbs1, MAX, MIN, NULL, SCIP_OKAY, SCIP_Real, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and SCVarData::ubs1.

Referenced by SCIP_DECL_NLHDLRENFO().

◆ SCIP_DECL_NLHDLRCOPYHDLR()

static SCIP_DECL_NLHDLRCOPYHDLR ( nlhdlrCopyhdlrPerspective  )
static

nonlinear handler copy callback

Definition at line 1212 of file nlhdlr_perspective.c.

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

◆ SCIP_DECL_NLHDLRFREEHDLRDATA()

static SCIP_DECL_NLHDLRFREEHDLRDATA ( nlhdlrFreehdlrdataPerspective  )
static

callback to free data of handler

Definition at line 1226 of file nlhdlr_perspective.c.

References SCIP_OKAY, and SCIPfreeBlockMemory.

◆ SCIP_DECL_NLHDLRFREEEXPRDATA()

static SCIP_DECL_NLHDLRFREEEXPRDATA ( nlhdlrFreeExprDataPerspective  )
static

callback to free expression specific data

Definition at line 1236 of file nlhdlr_perspective.c.

References freeNlhdlrExprData(), SCIP_CALL, SCIP_OKAY, and SCIPfreeBlockMemory.

◆ SCIP_DECL_NLHDLREXIT()

static SCIP_DECL_NLHDLREXIT ( nlhdlrExitPerspective  )
static

◆ SCIP_DECL_NLHDLRDETECT()

◆ SCIP_DECL_NLHDLREVALAUX()

static SCIP_DECL_NLHDLREVALAUX ( nlhdlrEvalauxPerspective  )
static

◆ SCIP_DECL_NLHDLRINITSEPA()

static SCIP_DECL_NLHDLRINITSEPA ( nlhdlrInitSepaPerspective  )
static

separation initialization method of a nonlinear handler

Definition at line 1474 of file nlhdlr_perspective.c.

References computeOffValues(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPnlhdlrGetData(), and SCIPreallocBlockMemoryArray.

◆ SCIP_DECL_NLHDLRENFO()

static SCIP_DECL_NLHDLRENFO ( nlhdlrEnfoPerspective  )
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 1521 of file nlhdlr_perspective.c.

References analyseOnoffBounds(), FALSE, getSCVarDataInd(), MAX, NULL, r, REALABS, 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(), startProbing(), tightenOnBounds(), TRUE, and SCVarData::vals0.