67#define HEUR_NAME "indicatordiving"
68#define HEUR_DESC "LP diving heuristic that fixes indicator variables controlling semicontinuous variables"
69#define HEUR_DISPCHAR 'I'
70#define HEUR_PRIORITY -150000
73#define HEUR_MAXDEPTH -1
74#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
75#define HEUR_USESSUBSCIP FALSE
76#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY
77#define DIVESET_ISPUBLIC FALSE
84#define DEFAULT_MINRELDEPTH 0.0
85#define DEFAULT_MAXRELDEPTH 1.0
86#define DEFAULT_MAXLPITERQUOT 0.05
87#define DEFAULT_MAXLPITEROFS 1000
88#define DEFAULT_MAXDIVEUBQUOT 0.8
90#define DEFAULT_MAXDIVEAVGQUOT 0.0
92#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1
93#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0
94#define DEFAULT_BACKTRACK TRUE
95#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15
96#define DEFAULT_LPSOLVEFREQ 30
97#define DEFAULT_ONLYLPBRANCHCANDS FALSE
99#define DEFAULT_RANDSEED 11
104#define DEFAULT_ROUNDINGFRAC 0.5
105#define DEFAULT_ROUNDINGMODE 0
106#define DEFAULT_SEMICONTSCOREMODE 0
107#define DEFAULT_USEVARBOUNDS TRUE
108#define DEFAULT_RUNWITHOUTSCINDS FALSE
145 SCIP_Real roundingfrac;
147 int semicontscoremode;
148 SCIP_Bool usevarbounds;
149 SCIP_Bool runwithoutscinds;
150 SCIP_Bool gotoindconss;
151 SCIP_Bool containsviolindconss;
193 if( hashmap !=
NULL )
224 SCIP_Bool* isindicator,
225 SCIP_Bool* containsviolindconss,
239 *isindicator =
FALSE;
254 *containsviolindconss =
FALSE;
256 for(
c = 0;
c < nconss;
c++ )
260 if( *containsviolindconss )
273 SCIP_Bool* isvarbound
341 for(
i = scvdata->
nbnds;
i > pos; --
i )
350 scvdata->
bvars[pos] = indicator;
351 scvdata->
vals0[pos] = val0;
352 scvdata->
lbs1[pos] = lb1;
353 scvdata->
ubs1[pos] = ub1;
386 SCIP_Real* vlbconstants;
387 SCIP_Real* vubconstants;
399 if( scvdata !=
NULL )
425 for(
c = 0;
c < nvlbs; ++
c )
432 lb0 =
MAX(vlbconstants[
c], glb);
433 lb1 =
MAX(vlbconstants[
c] + vlbcoefs[
c], glb);
436 if( vubvars !=
NULL )
444 ub0 =
MIN(vubconstants[pos], gub);
445 ub1 =
MIN(vubconstants[pos] + vubcoefs[pos], gub);
457 if( scvdata ==
NULL )
467 for(
c = 0;
c < nvubs; ++
c )
481 ub0 =
MIN(vubconstants[
c], gub);
482 ub1 =
MIN(vubconstants[
c] + vubcoefs[
c], gub);
487 if( scvdata ==
NULL )
496 if( scvdata !=
NULL )
500 for(
c = 0;
c < scvdata->
nbnds; ++
c )
518 SCIP_Bool* hasunfixedscindconss
527 *hasunfixedscindconss =
FALSE;
533 for(
i = 0;
i < nconss;
i++ )
559 for( v = 0; v < nconsvars ; v++ )
564 semicontinuousvar = consvars[v];
570 *hasunfixedscindconss =
TRUE;
574 if( *hasunfixedscindconss )
598 SCIP_Bool usevarbounds,
614 for(
i = 0;
i < nconss;
i++ )
628 for(
i = 0;
i < nconss;
i++ )
639#define MIN_RAND 1e-06
640#define MAX_RAND 1e-05
681 *score = -1.0 / *score;
778 SCIP_Bool hasunfixedscindconss;
837 SCIP_Real lpsolsemicontinuous;
843 SCIP_Bool isindicatorvar;
845 SCIP_Bool issemicont;
846 SCIP_Bool fixconstant;
852 semicontinuousvar =
NULL;
854 lpsolsemicontinuous = 0.0;
896 if(
heurdata->containsviolindconss &&
906 if(
heurdata->usevarbounds && !isindicatorvar )
916 if( !isindicatorvar && (!isvbdvar ||
heurdata->containsviolindconss || !
heurdata->usevarbounds) )
921 if( !
heurdata->containsviolindconss && !isvbdvar )
924 *score = (*score / (100 + fabs(*score))) * 100 - 200;
948 lincons = varboundcons;
959 if( nconsvars != 2 || !issemicont )
962 *score = (*score / (100 + fabs(*score))) * 100 - 200;
972 for( v = 0; v < nconsvars ; v++ )
974 if( consvars[v] == nonoptionvar )
977 semicontinuousvar = consvars[v];
990 for(
b = 0;
b < scdata->
nbnds;
b++ )
1012 *score = (*score / (100 + fabs(*score))) * 100 - 200;
1024 fixconstant =
FALSE;
1035 SCIP_Real shiftedlpsolsemicontinuous = lpsolsemicontinuous;
1036 SCIP_Real shiftedlbs1 = scdata->
lbs1[idxbvars];
1043 shiftedlpsolsemicontinuous -= scdata->
vals0[idxbvars];
1044 shiftedlbs1 -= scdata->
vals0[idxbvars];
1047 *score = 100 * (shiftedlbs1 - shiftedlpsolsemicontinuous) / shiftedlbs1;
1053 fixconstant = (*score > (1 -
heurdata->roundingfrac) * 100);
1056 fixconstant = (*score <= (1 -
heurdata->roundingfrac) * 100);
1062 switch(
heurdata->semicontscoremode )
1067 if( shiftedlpsolsemicontinuous < shiftedlbs1 * heurdata->roundingfrac )
1068 *score = 100 * (shiftedlpsolsemicontinuous / (
heurdata->roundingfrac * shiftedlbs1));
1070 *score = 100 * (-shiftedlpsolsemicontinuous / ((1 -
heurdata->roundingfrac) * shiftedlbs1) + (1 / (1 -
heurdata->roundingfrac)) );
1073 *score = 100 - *score;
1085 *
roundup = isindicatorvar ? fixconstant : !fixconstant;
1160 "in violation case all fractional below this value are fixed to constant",
1164 "decides which roundingmode is selected (0: conservative, 1: aggressive)",
1168 "which values of semi-continuous variables should get a high score? (0: low, 1: middle, 2: high)",
1172 "should varbound constraints be considered?",
1176 "should heur run if there are no indicator constraints modeling semicont. vars?",
constraint handler for indicator constraints
Constraint handler for variable bound constraints .
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetBinaryVarIndicator(SCIP_CONS *cons)
SCIP_VAR * SCIPgetSlackVarIndicator(SCIP_CONS *cons)
SCIP_CONS * SCIPgetLinearConsIndicator(SCIP_CONS *cons)
SCIP_Bool SCIPisViolatedIndicator(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
int SCIPgetNVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPincludeHeurIndicatordiving(SCIP *scip)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
SCIP_RETCODE SCIPcreateDiveset(SCIP *scip, SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, unsigned int initialseed, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_Bool ispublic, SCIP_Bool specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)),)
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBlockMemory(scip, ptr)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetProbingDepth(SCIP *scip)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
int SCIPvarGetNVlbs(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
int SCIPvarGetNVubs(SCIP_VAR *var)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
SCIPfreeSol(scip, &heurdata->sol))
static SCIP_DIVESET * diveset
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE))
#define DEFAULT_ONLYLPBRANCHCANDS
static SCIP_RETCODE releaseSCHashmap(SCIP *scip, SCIP_HASHMAP *hashmap)
#define DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define DEFAULT_ROUNDINGMODE
static void checkAndGetIndicator(SCIP *scip, SCIP_VAR *cand, SCIP_HASHMAP *map, SCIP_CONS **cons, SCIP_Bool *isindicator, SCIP_Bool *containsviolindconss, SCIP_Bool newnode, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr)
static SCIP_RETCODE createMaps(SCIP *scip, SCIP_CONSHDLR *indicatorconshdlr, SCIP_CONSHDLR *varboundconshdlr, SCIP_Bool usevarbounds, SCIP_HASHMAP **indicatormap, SCIP_HASHMAP **varboundmap)
#define DEFAULT_USEVARBOUNDS
enum IndicatorDivingRoundingMode INDICATORDIVINGROUNDINGMODE
#define DEFAULT_MAXLPITERQUOT
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_LPSOLVEFREQ
static SCIP_RETCODE hasUnfixedSCIndicator(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HASHMAP *scvars, SCIP_Bool *hasunfixedscindconss)
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEUBQUOTNOSOL
static void getScoreOfFarkasDiving(SCIP *scip, SCIP_DIVESET *diveset, SCIP_VAR *cand, SCIP_Real candsfrac, SCIP_Bool *roundup, SCIP_Real *score)
#define DEFAULT_SEMICONTSCOREMODE
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_ROUNDINGFRAC
#define DEFAULT_MAXLPITEROFS
static SCIP_RETCODE varIsSemicontinuous(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *scvars, SCIP_Real constant, SCIP_Bool *result)
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
static void checkAndGetVarbound(SCIP *scip, SCIP_VAR *cand, SCIP_HASHMAP *map, SCIP_CONS **cons, SCIP_Bool *isvarbound)
static SCIP_RETCODE addSCVarIndicator(SCIP *scip, SCVARDATA *scvdata, SCIP_VAR *indicator, SCIP_Real val0, SCIP_Real lb1, SCIP_Real ub1)
#define DIVESET_DIVETYPES
static SCIP_Bool isViolatedAndNotFixed(SCIP *scip, SCIP_SOL *sol, SCIP_CONS *cons)
#define DEFAULT_RUNWITHOUTSCINDS
#define DEFAULT_MINRELDEPTH
IndicatorDivingRoundingMode
LP diving heuristic that fixes indicator variables controlling semicontinuous variables.
assert(minobj< SCIPgetCutoffbound(scip))
methods commonly used by primal heuristics
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPgetConsVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int varssize, SCIP_Bool *success)
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing constraints
public methods for primal heuristics
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for the branch-and-bound tree
#define SCIP_DECL_DIVESETAVAILABLE(x)
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_DIVESETGETSCORE(x)
#define SCIP_DECL_HEUREXEC(x)
@ SCIP_DIVECONTEXT_SINGLE
enum SCIP_Retcode SCIP_RETCODE