29 #define HEUR_NAME "distributiondiving" 30 #define HEUR_DESC "Diving heuristic that chooses fixings w.r.t. changes in the solution density" 31 #define HEUR_DISPCHAR 'e' 32 #define HEUR_PRIORITY -1003300 34 #define HEUR_FREQOFS 3 35 #define HEUR_MAXDEPTH -1 36 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 37 #define HEUR_USESSUBSCIP FALSE 38 #define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED 39 #define EVENTHDLR_NAME "eventhdlr_distributiondiving" 40 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY 42 #define SQUARED(x) ((x) * (x)) 47 #define DEFAULT_MINRELDEPTH 0.0 48 #define DEFAULT_MAXRELDEPTH 1.0 49 #define DEFAULT_MAXLPITERQUOT 0.05 50 #define DEFAULT_MAXLPITEROFS 1000 51 #define DEFAULT_MAXDIVEUBQUOT 0.8 53 #define DEFAULT_MAXDIVEAVGQUOT 0.0 55 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 56 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 57 #define DEFAULT_BACKTRACK TRUE 58 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 59 #define DEFAULT_LPSOLVEFREQ 0 60 #define DEFAULT_ONLYLPBRANCHCANDS TRUE 63 #define SCOREPARAM_VALUES "lhwvd" 65 #define SCOREPARAM_VALUESLEN 5 66 #define DEFAULT_SCOREPARAM 'r' 67 #define DEFAULT_RANDSEED 117 79 int* rowinfinitiesdown;
93 struct SCIP_EventhdlrData
114 if( maxindex < heurdata->memsize )
118 newsize = (int)
SCIPfeasCeil(scip, (maxindex + 1) * 1.1);
119 assert(newsize > heurdata->memsize);
120 assert(heurdata->memsize >= 0);
123 if( heurdata->memsize == 0 )
148 heurdata->varpossmemsize = nvars;
149 heurdata->nupdatedvars = 0;
152 for( v = 0; v < nvars; ++v )
159 assert(heurdata->varfilterposs[v] >= 0);
161 heurdata->varposs[v] = -1;
162 heurdata->updatedvars[v] = NULL;
177 for( r = heurdata->memsize; r < newsize; ++r )
181 heurdata->rowinfinitiesdown[r] = 0;
182 heurdata->rowinfinitiesup[r] = 0;
186 heurdata->memsize = newsize;
206 assert(0 <= varindex && varindex < heurdata->varpossmemsize);
212 heurdata->currentlbs[varindex] = lblocal;
213 heurdata->currentubs[varindex] = ublocal;
232 int* rowinfinitiesdown,
241 assert(scip != NULL);
244 assert(sigma2 != NULL);
245 assert(rowinfinitiesup != NULL);
246 assert(rowinfinitiesdown != NULL);
252 assert(nrowvals == 0 || rowcols != NULL);
253 assert(nrowvals == 0 || rowvals != NULL);
257 *rowinfinitiesdown = 0;
258 *rowinfinitiesup = 0;
261 for( c = 0; c < nrowvals; ++c )
272 assert(rowcols[c] != NULL);
274 assert(colvar != NULL);
305 ++(*rowinfinitiesdown);
307 ++(*rowinfinitiesup);
316 ++(*rowinfinitiesdown);
318 ++(*rowinfinitiesup);
324 *mu += colval * varmean;
328 *sigma2 += squarecoeff * varvariance;
368 assert(scip != NULL);
370 assert(upscore != NULL);
371 assert(downscore != NULL);
376 assert(varcol != NULL);
383 assert(varub - varlb > 0.5);
388 squaredbounddiff = 0.0;
404 squaredbounddiffup = 0.0;
409 squaredbounddiffdown = 0.0;
417 onlyactiverows =
FALSE;
420 for( i = 0; i < ncolrows; ++i )
432 int rowinfinitiesdown;
453 rowCalculateGauss(scip, heurdata, row, &heurdata->rowmeans[rowpos], &heurdata->rowvariances[rowpos],
454 &heurdata->rowinfinitiesdown[rowpos], &heurdata->rowinfinitiesup[rowpos]);
458 rowmean = heurdata->rowmeans[rowpos];
459 rowvariance = heurdata->rowvariances[rowpos];
460 rowinfinitiesdown = heurdata->rowinfinitiesdown[rowpos];
461 rowinfinitiesup = heurdata->rowinfinitiesup[rowpos];
465 rowinfinitiesdown, rowinfinitiesup);
468 squaredcoeff =
SQUARED(rowval);
475 int rowinftiesdownafterbranch;
476 int rowinftiesupafterbranch;
479 changedrowmean = rowmean + rowval * (meanup - currentmean);
480 changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffup - squaredbounddiff);
481 changedrowvariance =
MAX(0.0, changedrowvariance);
483 rowinftiesdownafterbranch = rowinfinitiesdown;
484 rowinftiesupafterbranch = rowinfinitiesup;
488 rowinftiesupafterbranch--;
490 rowinftiesdownafterbranch--;
492 assert(rowinftiesupafterbranch >= 0);
493 assert(rowinftiesdownafterbranch >= 0);
494 newrowprobup =
SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
495 rowinftiesupafterbranch);
498 newrowprobup = currentrowprob;
503 int rowinftiesdownafterbranch;
504 int rowinftiesupafterbranch;
506 changedrowmean = rowmean + rowval * (meandown - currentmean);
507 changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffdown - squaredbounddiff);
508 changedrowvariance =
MAX(0.0, changedrowvariance);
510 rowinftiesdownafterbranch = rowinfinitiesdown;
511 rowinftiesupafterbranch = rowinfinitiesup;
515 rowinftiesupafterbranch -= 1;
517 rowinftiesdownafterbranch -= 1;
519 assert(rowinftiesdownafterbranch >= 0);
520 assert(rowinftiesupafterbranch >= 0);
521 newrowprobdown =
SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
522 rowinftiesupafterbranch);
525 newrowprobdown = currentrowprob;
530 SCIPdebugMsg(scip,
" Variable %s changes probability of row %s from %g to %g (branch up) or %g;\n",
532 SCIPdebugMsg(scip,
" --> new variable score: %g (for branching up), %g (for branching down)\n",
533 *upscore, *downscore);
546 assert(heurdata->memsize == 0 || heurdata->rowmeans != NULL);
547 assert(heurdata->memsize >= 0);
549 if( heurdata->varpossmemsize > 0 )
557 for( v = heurdata->varpossmemsize - 1; v >= 0; --v )
574 if( heurdata->memsize > 0 )
581 heurdata->memsize = 0;
584 heurdata->varpossmemsize = 0;
585 heurdata->nupdatedvars = 0;
606 assert(-1 <= varindex && varindex < heurdata->varpossmemsize);
611 varpos = heurdata->varposs[varindex];
612 assert(varpos < heurdata->nupdatedvars);
617 assert(heurdata->updatedvars[varpos] == var);
631 assert(heurdata->varpossmemsize > heurdata->nupdatedvars);
632 varpos = heurdata->nupdatedvars;
633 heurdata->updatedvars[varpos] = var;
634 heurdata->varposs[varindex] = varpos;
635 ++heurdata->nupdatedvars;
649 assert(heurdata->nupdatedvars >= 0);
652 if( heurdata->nupdatedvars == 0 )
655 varpos = heurdata->nupdatedvars - 1;
656 var = heurdata->updatedvars[varpos];
659 assert(0 <= varindex && varindex < heurdata->varpossmemsize);
660 assert(varpos == heurdata->varposs[varindex]);
662 heurdata->varposs[varindex] = -1;
663 heurdata->nupdatedvars--;
697 assert(varcol != NULL);
704 oldlb = heurdata->currentlbs[varindex];
705 oldub = heurdata->currentubs[varindex];
729 for( r = 0; r < ncolrows; ++r )
733 assert(colrows[r] != NULL);
745 &&
SCIPisFeasGE(scip, heurdata->rowvariances[rowpos], 0.0));
751 heurdata->rowmeans[rowpos] += coeff * (newmean - oldmean);
752 heurdata->rowvariances[rowpos] += coeffsquared * (newvariance - oldvariance);
753 heurdata->rowvariances[rowpos] =
MAX(0.0, heurdata->rowvariances[rowpos]);
760 ++heurdata->rowinfinitiesup[rowpos];
762 --heurdata->rowinfinitiesup[rowpos];
765 ++heurdata->rowinfinitiesdown[rowpos];
767 --heurdata->rowinfinitiesdown[rowpos];
769 else if( coeff < 0.0 )
772 ++heurdata->rowinfinitiesdown[rowpos];
774 --heurdata->rowinfinitiesdown[rowpos];
777 ++heurdata->rowinfinitiesup[rowpos];
779 --heurdata->rowinfinitiesup[rowpos];
781 assert(heurdata->rowinfinitiesdown[rowpos] >= 0);
782 assert(heurdata->rowinfinitiesup[rowpos] >= 0);
799 assert(eventhdlrdata != NULL);
815 assert(scip != NULL);
816 assert(heur != NULL);
831 assert(heur != NULL);
833 assert(scip != NULL);
837 assert(heurdata != NULL);
851 assert(heur != NULL);
856 assert(heurdata != NULL);
871 assert(heur != NULL);
876 assert(heurdata != NULL);
894 assert(heurdata != NULL);
897 while( heurdata->nupdatedvars > 0 )
903 assert(nextvar != NULL);
907 assert(cand != NULL);
915 if( varindex == - 1 )
928 assert(0 <= varindex && varindex < heurdata->varpossmemsize);
948 *roundup = (upscore > downscore);
949 *score =
MAX(upscore, downscore);
963 assert(heur != NULL);
965 assert(scip != NULL);
966 assert(result != NULL);
973 assert(heurdata != NULL);
983 if( heurdata->scoreparam ==
'r' )
986 heurdata->score = heurdata->scoreparam;
992 assert(diveset != NULL);
1009 assert(eventhdlr != NULL);
1011 assert(eventhdlrdata != NULL);
1013 heurdata = eventhdlrdata->heurdata;
1039 heurdata->memsize = 0;
1040 heurdata->rowmeans = NULL;
1041 heurdata->rowvariances = NULL;
1042 heurdata->rowinfinitiesdown = NULL;
1043 heurdata->rowinfinitiesup = NULL;
1044 heurdata->varfilterposs = NULL;
1045 heurdata->currentlbs = NULL;
1046 heurdata->currentubs = NULL;
1049 eventhdlrdata = NULL;
1051 eventhdlrdata->heurdata = heurdata;
1053 heurdata->eventhdlr = NULL;
1055 "event handler for dynamic acitivity distribution updating",
1056 eventExecDistribution, eventhdlrdata) );
1057 assert( heurdata->eventhdlr != NULL);
1065 assert(heur != NULL);
1079 divesetGetScoreDistributiondiving) );
1082 "the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p., 'v'otes lowest c.p., votes highest c.p.('w'), 'r'evolving",
int SCIPgetNIntVars(SCIP *scip)
#define DIVESET_DIVETYPES
void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
probability based branching rule based on an article by J. Pryor and J.W. Chinneck ...
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_STAGE SCIPgetStage(SCIP *scip)
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreDistributiondiving)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
#define SCOREPARAM_VALUESLEN
static SCIP_RETCODE heurdataEnsureArraySize(SCIP *scip, SCIP_HEURDATA *heurdata, int maxindex)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
#define SCOREPARAM_VALUES
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
enum SCIP_Retcode SCIP_RETCODE
int SCIPvarGetProbindex(SCIP_VAR *var)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIPfreeBlockMemory(scip, ptr)
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)
static SCIP_RETCODE calcBranchScore(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real lpsolval, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
#define EVENT_DISTRIBUTION
#define SCIPfreeBufferArray(scip, ptr)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
static SCIP_DECL_EVENTFREE(eventFreeDistributiondiving)
SCIP_RETCODE SCIPincludeHeurDistributiondiving(SCIP *scip)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
#define DEFAULT_MINRELDEPTH
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define DEFAULT_SCOREPARAM
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
#define DEFAULT_LPSOLVEFREQ
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
static SCIP_DECL_HEURCOPY(heurCopyDistributiondiving)
static SCIP_DECL_EVENTEXEC(eventExecDistribution)
const char * SCIPvarGetName(SCIP_VAR *var)
static void rowCalculateGauss(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_ROW *row, SCIP_Real *mu, SCIP_Real *sigma2, int *rowinfinitiesdown, int *rowinfinitiesup)
#define DEFAULT_MAXLPITEROFS
int SCIPgetNLPRows(SCIP *scip)
#define DEFAULT_MAXLPITERQUOT
static SCIP_DECL_HEUREXIT(heurExitDistributiondiving)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
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 specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)))
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
static SCIP_DECL_HEUREXEC(heurExecDistributiondiving)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static void heurdataUpdateCurrentBounds(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
static SCIP_RETCODE heurdataFreeArrays(SCIP *scip, SCIP_HEURDATA *heurdata)
int SCIPgetNBinVars(SCIP *scip)
SCIP_Bool SCIPinProbing(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Diving heuristic that chooses fixings w.r.t. changes in the solution density after Pryor and Chinneck...
int SCIPcolGetNNonz(SCIP_COL *col)
#define DEFAULT_BACKTRACK
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
static void heurdataAddBoundChangeVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
#define DEFAULT_ONLYLPBRANCHCANDS
SCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
static SCIP_DECL_HEURFREE(heurFreeDistributiondiving)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
static SCIP_VAR * heurdataPopBoundChangeVar(SCIP *scip, SCIP_HEURDATA *heurdata)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIProwGetIndex(SCIP_ROW *row)
enum SCIP_Vartype SCIP_VARTYPE
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define DEFAULT_MAXDIVEUBQUOT
static SCIP_DECL_HEURINIT(heurInitDistributiondiving)
static SCIP_RETCODE varProcessBoundChanges(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
#define DEFAULT_MAXRELDEPTH
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
#define SCIPreallocBufferArray(scip, ptr, num)
#define DEFAULT_MAXDIVEAVGQUOT