55#define HEUR_NAME "distributiondiving"
56#define HEUR_DESC "Diving heuristic that chooses fixings w.r.t. changes in the solution density"
57#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
58#define HEUR_PRIORITY -1003300
61#define HEUR_MAXDEPTH -1
62#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
63#define HEUR_USESSUBSCIP FALSE
64#define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED
65#define EVENTHDLR_NAME "eventhdlr_distributiondiving"
66#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY
67#define DIVESET_ISPUBLIC FALSE
73#define DEFAULT_MINRELDEPTH 0.0
74#define DEFAULT_MAXRELDEPTH 1.0
75#define DEFAULT_MAXLPITERQUOT 0.05
76#define DEFAULT_MAXLPITEROFS 1000
77#define DEFAULT_MAXDIVEUBQUOT 0.8
79#define DEFAULT_MAXDIVEAVGQUOT 0.0
81#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1
82#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0
83#define DEFAULT_BACKTRACK TRUE
84#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15
85#define DEFAULT_LPSOLVEFREQ 0
86#define DEFAULT_ONLYLPBRANCHCANDS TRUE
89#define SCOREPARAM_VALUES "lhwvd"
91#define SCOREPARAM_VALUESLEN 5
92#define DEFAULT_SCOREPARAM 'r'
93#define DEFAULT_RANDSEED 117
102 SCIP_Real* rowvariances;
103 SCIP_Real* currentubs;
104 SCIP_Real* currentlbs;
105 int* rowinfinitiesdown;
107 int* rowinfinitiesup;
119struct SCIP_EventhdlrData
140 if( maxindex < heurdata->memsize )
178 for( v = 0; v <
nvars; ++v )
231 assert(0 <= varindex && varindex < heurdata->varpossmemsize);
237 heurdata->currentlbs[varindex] = lblocal;
238 heurdata->currentubs[varindex] = ublocal;
257 int* rowinfinitiesdown,
282 *rowinfinitiesdown = 0;
283 *rowinfinitiesup = 0;
286 for(
c = 0;
c < nrowvals; ++
c )
292 SCIP_Real squarecoeff;
293 SCIP_Real varvariance;
329 ++(*rowinfinitiesdown);
331 ++(*rowinfinitiesup);
340 ++(*rowinfinitiesdown);
342 ++(*rowinfinitiesup);
348 *mu += colval * varmean;
351 squarecoeff =
SQR(colval);
352 *sigma2 += squarecoeff * varvariance;
369 SCIP_Real* downscore,
378 SCIP_Real squaredbounddiff;
381 SCIP_Real squaredbounddiffup;
382 SCIP_Real squaredbounddiffdown;
383 SCIP_Real currentmean;
390 SCIP_Bool onlyactiverows;
407 assert(varub - varlb > 0.5);
412 squaredbounddiff = 0.0;
428 squaredbounddiffup = 0.0;
433 squaredbounddiffdown = 0.0;
441 onlyactiverows =
FALSE;
444 for(
i = 0;
i < ncolrows; ++
i )
447 SCIP_Real changedrowmean;
449 SCIP_Real rowvariance;
450 SCIP_Real changedrowvariance;
451 SCIP_Real currentrowprob;
452 SCIP_Real newrowprobup;
453 SCIP_Real newrowprobdown;
454 SCIP_Real squaredcoeff;
456 int rowinfinitiesdown;
482 rowmean =
heurdata->rowmeans[rowpos];
483 rowvariance =
heurdata->rowvariances[rowpos];
484 rowinfinitiesdown =
heurdata->rowinfinitiesdown[rowpos];
485 rowinfinitiesup =
heurdata->rowinfinitiesup[rowpos];
489 rowinfinitiesdown, rowinfinitiesup);
492 squaredcoeff =
SQR(rowval);
499 int rowinftiesdownafterbranch;
500 int rowinftiesupafterbranch;
503 changedrowmean = rowmean + rowval * (meanup - currentmean);
504 changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffup - squaredbounddiff);
505 changedrowvariance =
MAX(0.0, changedrowvariance);
507 rowinftiesdownafterbranch = rowinfinitiesdown;
508 rowinftiesupafterbranch = rowinfinitiesup;
512 rowinftiesupafterbranch--;
514 rowinftiesdownafterbranch--;
516 assert(rowinftiesupafterbranch >= 0);
517 assert(rowinftiesdownafterbranch >= 0);
519 rowinftiesupafterbranch);
522 newrowprobup = currentrowprob;
527 int rowinftiesdownafterbranch;
528 int rowinftiesupafterbranch;
530 changedrowmean = rowmean + rowval * (meandown - currentmean);
531 changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffdown - squaredbounddiff);
532 changedrowvariance =
MAX(0.0, changedrowvariance);
534 rowinftiesdownafterbranch = rowinfinitiesdown;
535 rowinftiesupafterbranch = rowinfinitiesup;
539 rowinftiesupafterbranch -= 1;
541 rowinftiesdownafterbranch -= 1;
543 assert(rowinftiesdownafterbranch >= 0);
544 assert(rowinftiesupafterbranch >= 0);
546 rowinftiesupafterbranch);
549 newrowprobdown = currentrowprob;
554 SCIPdebugMsg(
scip,
" Variable %s changes probability of row %s from %g to %g (branch up) or %g;\n",
556 SCIPdebugMsg(
scip,
" --> new variable score: %g (for branching up), %g (for branching down)\n",
557 *upscore, *downscore);
581 for( v =
heurdata->varpossmemsize - 1; v >= 0; --v )
629 assert(-1 <= varindex && varindex < heurdata->varpossmemsize);
634 varpos =
heurdata->varposs[varindex];
635 assert(varpos < heurdata->nupdatedvars);
656 heurdata->varposs[varindex] = varpos;
676 varpos =
heurdata->nupdatedvars - 1;
680 assert(0 <= varindex && varindex < heurdata->varpossmemsize);
702 SCIP_Real oldvariance;
703 SCIP_Real newvariance;
725 oldlb =
heurdata->currentlbs[varindex];
726 oldub =
heurdata->currentubs[varindex];
750 for(
r = 0;
r < ncolrows; ++
r )
764 SCIP_Real coeffsquared;
768 coeffsquared =
SQR(coeff);
771 heurdata->rowmeans[rowpos] += coeff * (newmean - oldmean);
772 heurdata->rowvariances[rowpos] += coeffsquared * (newvariance - oldvariance);
780 ++
heurdata->rowinfinitiesup[rowpos];
782 --
heurdata->rowinfinitiesup[rowpos];
785 ++
heurdata->rowinfinitiesdown[rowpos];
787 --
heurdata->rowinfinitiesdown[rowpos];
789 else if( coeff < 0.0 )
792 ++
heurdata->rowinfinitiesdown[rowpos];
794 --
heurdata->rowinfinitiesdown[rowpos];
797 ++
heurdata->rowinfinitiesup[rowpos];
799 --
heurdata->rowinfinitiesup[rowpos];
935 if( varindex == - 1 )
947 assert(0 <= varindex && varindex < heurdata->varpossmemsize);
964 *
roundup = (upscore > downscore);
965 *score =
MAX(upscore, downscore);
1029 heurdata = eventhdlrdata->heurdata;
1042#define divesetAvailableDistributiondiving NULL
1067 eventhdlrdata =
NULL;
1069 eventhdlrdata->heurdata =
heurdata;
1073 "event handler for dynamic acitivity distribution updating",
1074 eventExecDistribution, eventhdlrdata) );
1100 "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",
probability based branching rule based on an article by J. Pryor and J.W. Chinneck
SCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
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_RETCODE SCIPincludeHeurDistributiondiving(SCIP *scip)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
int SCIPcolGetNNonz(SCIP_COL *col)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
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_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr,)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
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,)
SCIP_Longint SCIPheurGetNCalls(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)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
int SCIPgetNLPRows(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIPinProbing(SCIP *scip)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
const char * SCIProwGetName(SCIP_ROW *row)
int SCIProwGetIndex(SCIP_ROW *row)
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
static SCIP_DIVESET * diveset
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE))
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
#define divesetAvailableDistributiondiving
#define DEFAULT_SCOREPARAM
#define DEFAULT_LPRESOLVEDOMCHGQUOT
SCIPheurSetData(heur, NULL)
#define EVENT_DISTRIBUTION
#define SCOREPARAM_VALUES
#define DEFAULT_MAXLPITERQUOT
static SCIP_RETCODE calcBranchScore(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real lpsolval, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
static void rowCalculateGauss(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_ROW *row, SCIP_Real *mu, SCIP_Real *sigma2, int *rowinfinitiesdown, int *rowinfinitiesup)
#define SCOREPARAM_VALUESLEN
static void heurdataUpdateCurrentBounds(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_LPSOLVEFREQ
static SCIP_RETCODE varProcessBoundChanges(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
static SCIP_VAR * heurdataPopBoundChangeVar(SCIP_HEURDATA *heurdata)
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
SCIPfreeSol(scip, &heurdata->sol))
static SCIP_RETCODE heurdataEnsureArraySize(SCIP *scip, SCIP_HEURDATA *heurdata, int maxindex)
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
static SCIP_RETCODE heurdataFreeArrays(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DIVESET_DIVETYPES
static void heurdataAddBoundChangeVar(SCIP_HEURDATA *heurdata, SCIP_VAR *var)
#define DEFAULT_MINRELDEPTH
SCIPcreateSol(scip, &heurdata->sol, heur))
Diving heuristic that chooses fixings w.r.t. changes in the solution density after Pryor and Chinneck...
assert(minobj< SCIPgetCutoffbound(scip))
methods commonly used by primal heuristics
memory allocation routines
public methods for managing events
public methods for primal heuristics
public methods for LP management
public methods for message output
public methods for problem variables
public methods for event handler plugins and event handlers
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
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
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_DECL_EVENTFREE(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
enum SCIP_Vartype SCIP_VARTYPE