heur_indicatordiving.c
Go to the documentation of this file.
31 * A diving heuristic iteratively rounds some fractional variables or variables determined by constraint handlers,
35 * If the semicontinuous variable is unbounded, the indicator constraint is not part of the LP and,
38 * For these indicator variables the score depends on the LP value and the bounds of the corresponding semicontinuous variable.
39 * If parameter usevarbounds=TRUE, also varbound constraints modeling semicontinuous variables are considered.
43/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
68#define HEUR_DESC "LP diving heuristic that fixes indicator variables controlling semicontinuous variables"
76#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */
77#define DIVESET_ISPUBLIC FALSE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
86#define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
88#define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
90#define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
92#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
93#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
94#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
95#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
97#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
114};
127 SCIP_Real* lbs1; /**< global lower bounds of the variable when the corresponding bvars[i] = 1 */
128 SCIP_Real* ubs1; /**< global upper bounds of the variable when the corresponding bvars[i] = 1 */
145 SCIP_Real roundingfrac; /**< in violation case all fractional below this value are fixed to constant */
146 int roundingmode; /**< decides which roundingmode is selected (0: conservative (default), 1: aggressive) */
147 int semicontscoremode; /**< which values of semi-continuous variables should get a high score? (0: low (default), 1: middle, 2: high) */
149 SCIP_Bool runwithoutscinds; /**< should heur run if there are no indicator constraints modeling semicont. vars? */
150 SCIP_Bool gotoindconss; /**< can we skip the candidate var until indicator conss handler determines the candidate var? */
151 SCIP_Bool containsviolindconss;/**< contains current solution violated indicator constraints? (only unbounded) */
160/** checks if constraint is violated but not fixed, i.e., it will be a diving candidate variable */
179 return (SCIPisFeasIntegral(scip, solval) && SCIPvarGetLbLocal(binvar) < SCIPvarGetUbLocal(binvar) - 0.5);
215/** checks if variable is indicator variable and stores corresponding indicator constraint; additionally, if we are at a
224 SCIP_Bool* isindicator, /**< pointer to store whether candidate variable is indicator variable */
225 SCIP_Bool* containsviolindconss,/**< pointer to store whether there are violated and not fixed (unbounded) indicator constraints */
245 /* since we are at a new probing node, check if there are violated and not fixed indicator constraints */
258 *containsviolindconss = *containsviolindconss || isViolatedAndNotFixed(scip, sol, indicatorconss[c]);
266/** checks if variable is binary variable of varbound constraint and stores corresponding varbound constraint */
321 found = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, &pos);
361 * A variable x is semicontinuous if its bounds depend on at least one binary variable called the indicator,
454 /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */
484 /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */
499 SCIPdebugMsg(scip, "var <%s> has global bounds [%f, %f] and the following on/off bounds:\n", SCIPvarGetName(var), glb, gub);
502 SCIPdebugMsg(scip, " c = %d, bvar <%s>: val0 = %f\n", c, SCIPvarGetName(scvdata->bvars[c]), scvdata->vals0[c]);
518 SCIP_Bool* hasunfixedscindconss /**< pointer to store if there are unfixed indicator variables modeling semicont. vars */
561 if( consvars[v] == SCIPgetSlackVarIndicator(indicatorconss[i]) ) /* note that we have exact two variables */
649 SCIP_Bool* roundup, /**< pointer to store whether the preferred rounding direction is upwards */
778 SCIP_Bool hasunfixedscindconss; /* are there unfixed indicator variables modeling a semicont. variable? */
792 SCIP_CALL( hasUnfixedSCIndicator(scip, heurdata->indicatorconshdlr, heurdata->scvars, &hasunfixedscindconss) );
797 if( !hasunfixedscindconss && (!heurdata->runwithoutscinds || !heurdata->usevarbounds || SCIPconshdlrGetNConss(heurdata->varboundconshdlr) == 0) )
803 SCIP_CALL( createMaps(scip, heurdata->indicatorconshdlr, heurdata->varboundconshdlr, heurdata->usevarbounds, &heurdata->indicatormap, &heurdata->varboundmap) );
811 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
835 SCIP_VAR* nonoptionvar; /* second variable in linear cons which is not the option variable (indicator: slackvar, varbound: binary var) */
845 SCIP_Bool issemicont; /* indicates whether variable has (maybe) required semicont. properties */
867 /* check if we are at a new probing node; since diving heuristics backtrack at most one probing node, we are at a new
878 /* skip if current candidate can not be determined by the indicator constraint handler and violated indicator
880 if( !(SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5)
892 &heurdata->containsviolindconss, heurdata->newnode, heurdata->sol, heurdata->indicatorconshdlr);
894 /* skip candidate in next calls since we have violated indicator constraints but current candidate is not determined
897 !((SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5) && isindicatorvar) )
913 * - or if candidate variable is not an indicator variable but there will be indicator variables as candidates
914 * - or if candidate variable is not an indicator variable and varbound constraints are not considered.
916 if( !isindicatorvar && (!isvbdvar || heurdata->containsviolindconss || !heurdata->usevarbounds) )
929 SCIPdebugMsg(scip, "cand: %s, candsol: %.2f, candobjcoeff: %f\n", SCIPvarGetName(cand), candsol, SCIPvarGetObj(cand));
938 issemicont = SCIPisInfinity(scip, -SCIPconsGetLhs(scip, lincons, &success)); /* TODO: allow also indicators for lower bounds */
979 SCIPdebugMsg(scip, "%s lp sol %f %f\n", SCIPvarGetName( semicontinuousvar ), lpsolsemicontinuous,
992 if( (scdata->bvars[b] == cand || (SCIPvarIsNegated(cand) && scdata->bvars[0] == SCIPvarGetNegationVar(cand)))
997 if( SCIPisGE(scip, lpsolsemicontinuous, scdata->vals0[b]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[b]) )
1021 if( SCIPisGE(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[idxbvars]))
1038 assert(SCIPisGT(scip, lpsolsemicontinuous, scdata->vals0[idxbvars]) && SCIPisLT(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]));
1070 *score = 100 * (-shiftedlpsolsemicontinuous / ((1 - heurdata->roundingfrac) * shiftedlbs1) + (1 / (1 - heurdata->roundingfrac)) );
1100 * If varbound constraints should be considered, skip only if there are also no varbound constraints.
1153 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
1154 SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT,
1155 DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT,
1156 DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS,
1157 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreIndicatordiving, divesetAvailableIndicatordiving) );
1168 "which values of semi-continuous variables should get a high score? (0: low, 1: middle, 2: high)",
constraint handler for indicator constraints
Constraint handler for variable bound constraints .
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5547
SCIP_VAR * SCIPgetBinaryVarIndicator(SCIP_CONS *cons)
Definition: cons_indicator.c:8906
SCIP_VAR * SCIPgetSlackVarIndicator(SCIP_CONS *cons)
Definition: cons_indicator.c:9025
SCIP_CONS * SCIPgetLinearConsIndicator(SCIP_CONS *cons)
Definition: cons_indicator.c:8802
SCIP_Bool SCIPisViolatedIndicator(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
Definition: cons_indicator.c:9076
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3570
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3549
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
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)
Definition: scip_param.c:83
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)
Definition: scip_param.c:139
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)
Definition: scip_param.c:57
SCIP_RETCODE SCIPincludeHeurIndicatordiving(SCIP *scip)
Definition: heur_indicatordiving.c:1128
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4670
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2622
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2578
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_DECL_DIVESETAVAILABLE((*divesetavailable)))
Definition: scip_heur.c:318
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition: heur.c:720
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
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)
Definition: scip_heur.c:117
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:220
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
static SCIP_RETCODE releaseSCHashmap(SCIP *scip, SCIP_HASHMAP *hashmap)
Definition: heur_indicatordiving.c:184
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreIndicatordiving)
Definition: heur_indicatordiving.c:826
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)
Definition: heur_indicatordiving.c:219
static SCIP_RETCODE createMaps(SCIP *scip, SCIP_CONSHDLR *indicatorconshdlr, SCIP_CONSHDLR *varboundconshdlr, SCIP_Bool usevarbounds, SCIP_HASHMAP **indicatormap, SCIP_HASHMAP **varboundmap)
Definition: heur_indicatordiving.c:594
enum IndicatorDivingRoundingMode INDICATORDIVINGROUNDINGMODE
Definition: heur_indicatordiving.c:115
static SCIP_DECL_DIVESETAVAILABLE(divesetAvailableIndicatordiving)
Definition: heur_indicatordiving.c:1097
static SCIP_RETCODE hasUnfixedSCIndicator(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HASHMAP *scvars, SCIP_Bool *hasunfixedscindconss)
Definition: heur_indicatordiving.c:514
static void getScoreOfFarkasDiving(SCIP *scip, SCIP_DIVESET *diveset, SCIP_VAR *cand, SCIP_Real candsfrac, SCIP_Bool *roundup, SCIP_Real *score)
Definition: heur_indicatordiving.c:644
static SCIP_DECL_HEUREXIT(heurExitIndicatordiving)
Definition: heur_indicatordiving.c:752
static SCIP_DECL_HEURINIT(heurInitIndicatordiving)
Definition: heur_indicatordiving.c:727
static SCIP_RETCODE varIsSemicontinuous(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *scvars, SCIP_Real constant, SCIP_Bool *result)
Definition: heur_indicatordiving.c:365
static void checkAndGetVarbound(SCIP *scip, SCIP_VAR *cand, SCIP_HASHMAP *map, SCIP_CONS **cons, SCIP_Bool *isvarbound)
Definition: heur_indicatordiving.c:268
static SCIP_DECL_HEURFREE(heurFreeIndicatordiving)
Definition: heur_indicatordiving.c:706
static SCIP_RETCODE addSCVarIndicator(SCIP *scip, SCVARDATA *scvdata, SCIP_VAR *indicator, SCIP_Real val0, SCIP_Real lb1, SCIP_Real ub1)
Definition: heur_indicatordiving.c:295
static SCIP_Bool isViolatedAndNotFixed(SCIP *scip, SCIP_SOL *sol, SCIP_CONS *cons)
Definition: heur_indicatordiving.c:162
static SCIP_DECL_HEURCOPY(heurCopyIndicatordiving)
Definition: heur_indicatordiving.c:691
static SCIP_DECL_HEUREXEC(heurExecIndicatordiving)
Definition: heur_indicatordiving.c:774
LP diving heuristic that fixes indicator variables controlling semicontinuous variables.
methods commonly used by primal heuristics
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:112
SCIP_RETCODE SCIPgetConsVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int varssize, SCIP_Bool *success)
Definition: misc_linear.c:179
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:48
Definition: objbenders.h:44
public methods for managing constraints
public methods for primal heuristics
public methods for message output
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
Definition: struct_cons.h:47
Definition: struct_cons.h:127
Definition: struct_heur.h:68
Definition: struct_misc.h:131
Definition: struct_misc.h:138
Definition: struct_heur.h:98
Definition: struct_misc.h:269
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: heur_indicatordiving.c:125
Definition: struct_scip.h:70