29 #define HEUR_NAME "objpscostdiving" 30 #define HEUR_DESC "LP diving heuristic that changes variable's objective values instead of bounds, using pseudo costs as guide" 31 #define HEUR_DISPCHAR 'o' 32 #define HEUR_PRIORITY -1004000 34 #define HEUR_FREQOFS 4 35 #define HEUR_MAXDEPTH -1 36 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 37 #define HEUR_USESSUBSCIP FALSE 44 #define DEFAULT_MINRELDEPTH 0.0 45 #define DEFAULT_MAXRELDEPTH 1.0 46 #define DEFAULT_MAXLPITERQUOT 0.01 47 #define DEFAULT_MAXLPITEROFS 1000 48 #define DEFAULT_MAXSOLS -1 50 #define DEFAULT_DEPTHFAC 0.5 51 #define DEFAULT_DEPTHFACNOSOL 2.0 52 #define DEFAULT_RANDSEED 139 54 #define MINLPITER 10000 94 assert(heurdata !=
NULL);
95 assert(pscostquot !=
NULL);
96 assert(roundup !=
NULL);
99 frac =
MAX(frac, 0.1);
100 frac =
MIN(frac, 0.9);
105 assert(pscostdown >= 0.0 && pscostup >= 0.0);
114 else if( rounddir == +1 )
126 else if(
SCIPisLT(scip, pscostdown, pscostup)
134 *pscostquot =
sqrt(frac) * (1.0+pscostdown) / (1.0+pscostup);
136 *pscostquot =
sqrt(1.0-frac) * (1.0+pscostup) / (1.0+pscostdown);
140 (*pscostquot) *= 1000.0;
152 assert(scip !=
NULL);
153 assert(heur !=
NULL);
168 assert(heur !=
NULL);
170 assert(scip !=
NULL);
174 assert(heurdata !=
NULL);
188 assert(heur !=
NULL);
193 assert(heurdata !=
NULL);
202 heurdata->nlpiterations = 0;
203 heurdata->nsuccess = 0;
215 assert(heur !=
NULL);
220 assert(heurdata !=
NULL);
272 assert(heur !=
NULL);
274 assert(scip !=
NULL);
275 assert(result !=
NULL);
304 assert(heurdata !=
NULL);
313 maxdepth =
MAX(maxdepth, 30);
314 if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
321 maxnlpiterations = (
SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
322 maxnlpiterations += heurdata->maxlpiterofs;
325 if( heurdata->nlpiterations >= maxnlpiterations )
329 maxnlpiterations =
MAX(maxnlpiterations, heurdata->nlpiterations +
MINLPITER);
341 maxdivedepth = (int)(heurdata->depthfacnosol * nvars);
343 maxdivedepth = (int)(heurdata->depthfac * nvars);
344 maxdivedepth =
MIN(maxdivedepth, 10*maxdepth);
356 SCIPdebugMsg(scip,
"(node %" SCIP_LONGINT_FORMAT
") executing objpscostdiving heuristic: depth=%d, %d fractionals, dualbound=%g, maxnlpiterations=%" SCIP_LONGINT_FORMAT
", maxdivedepth=%d\n",
367 startnlpcands = nlpcands;
370 || nlpcands <= startnlpcands - divedepth/2
371 || (divedepth < maxdivedepth && nlpcands <= startnlpcands - divedepth/10
372 && heurdata->nlpiterations < maxnlpiterations)) && !
SCIPisStopped(scip) )
385 bestpscostquot = -1.0;
386 bestcandmayrounddown =
TRUE;
387 bestcandmayroundup =
TRUE;
388 bestcandroundup =
FALSE;
389 for( c = 0; c < nlpcands; ++c )
394 primsol = lpcandssol[c];
395 frac = lpcandsfrac[c];
396 if( mayrounddown || mayroundup )
399 if( bestcandmayrounddown || bestcandmayroundup )
407 if( mayrounddown && mayroundup )
408 calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup);
409 else if( mayrounddown )
410 calcPscostQuot(scip, heurdata, var, primsol, frac, +1, &pscostquot, &roundup);
412 calcPscostQuot(scip, heurdata, var, primsol, frac, -1, &pscostquot, &roundup);
416 assert(0 <= varidx && varidx < nvars);
417 if( roundings[varidx] != 0 )
418 pscostquot *= 1000.0;
421 if( pscostquot > bestpscostquot )
424 bestpscostquot = pscostquot;
425 bestcandmayrounddown = mayrounddown;
426 bestcandmayroundup = mayroundup;
427 bestcandroundup = roundup;
434 calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup);
438 assert(0 <= varidx && varidx < nvars);
439 if( roundings[varidx] != 0 )
440 pscostquot *= 1000.0;
443 if( bestcandmayrounddown || bestcandmayroundup || pscostquot > bestpscostquot )
446 bestpscostquot = pscostquot;
447 bestcandmayrounddown =
FALSE;
448 bestcandmayroundup =
FALSE;
449 bestcandroundup = roundup;
453 assert(bestcand != -1);
456 if( bestcandmayrounddown || bestcandmayroundup )
466 SCIPdebugMsg(scip,
"objpscostdiving found roundable primal solution: obj=%g\n",
475 SCIPdebugMsg(scip,
" -> solution was feasible and good enough\n");
481 var = lpcands[bestcand];
485 assert(0 <= varidx && varidx < nvars);
486 if( roundings[varidx] == +1 )
490 SCIPdebugMsg(scip,
" dive %d/%d: var <%s>, round=%u/%u, sol=%g, was already soft rounded upwards -> bounds=[%g,%g]\n",
491 divedepth, maxdivedepth,
SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
494 else if( roundings[varidx] == -1 )
498 SCIPdebugMsg(scip,
" dive %d/%d: var <%s>, round=%u/%u, sol=%g, was already soft rounded downwards -> bounds=[%g,%g]\n",
499 divedepth, maxdivedepth,
SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
504 assert(roundings[varidx] == 0);
507 objscale = divedepth * 1000.0;
509 if( bestcandroundup )
513 newobj = objscale * oldobj;
515 newobj = -objscale * oldobj;
516 newobj =
MIN(newobj, -objscale);
519 roundings[varidx] = +1;
525 newobj = objscale * oldobj;
527 newobj = -objscale * oldobj;
528 newobj =
MAX(newobj, objscale);
531 roundings[varidx] = -1;
534 SCIPdebugMsg(scip,
" dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT
"/%" SCIP_LONGINT_FORMAT
": var <%s>, round=%u/%u, sol=%g, bounds=[%g,%g], obj=%g, newobj=%g\n",
535 divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations,
556 SCIPwarningMessage(scip,
"Error while solving LP in Objpscostdiving heuristic; LP solve terminated with code <%d>\n", retcode);
557 SCIPwarningMessage(scip,
"This does not affect the remaining solution procedure --> continue\n");
572 SCIPdebugMsg(scip,
" -> lpsolstat=%d, nfrac=%d\n", lpsolstat, nlpcands);
590 SCIPdebugMsg(scip,
" -> solution was feasible and good enough\n");
599 heurdata->nsuccess++;
604 SCIPdebugMsg(scip,
"objpscostdiving heuristic finished\n");
630 assert(heur !=
NULL);
640 "heuristics/objpscostdiving/minreldepth",
641 "minimal relative depth to start diving",
644 "heuristics/objpscostdiving/maxreldepth",
645 "maximal relative depth to start diving",
648 "heuristics/objpscostdiving/maxlpiterquot",
649 "maximal fraction of diving LP iterations compared to total iteration number",
652 "heuristics/objpscostdiving/maxlpiterofs",
653 "additional number of allowed LP iterations",
656 "heuristics/objpscostdiving/maxsols",
657 "total number of feasible solutions found up to which heuristic is called (-1: no limit)",
660 "heuristics/objpscostdiving/depthfac",
661 "maximal diving depth: number of binary/integer variables times depthfac",
664 "heuristics/objpscostdiving/depthfacnosol",
665 "maximal diving depth factor if no feasible solution was found yet",
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
int SCIPgetNIntVars(SCIP *scip)
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
#define DEFAULT_MINRELDEPTH
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
#define DEFAULT_MAXLPITEROFS
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_MAXLPITERQUOT
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
int SCIPgetMaxDepth(SCIP *scip)
#define DEFAULT_MAXRELDEPTH
static SCIP_DECL_HEURINIT(heurInitObjpscostdiving)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
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)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
enum SCIP_LPSolStat SCIP_LPSOLSTAT
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
static SCIP_DECL_HEURFREE(heurFreeObjpscostdiving)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
SCIP_Real SCIPgetVarUbDive(SCIP *scip, SCIP_VAR *var)
const char * SCIPheurGetName(SCIP_HEUR *heur)
static SCIP_DECL_HEUREXEC(heurExecObjpscostdiving)
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIPInterval sqrt(const SCIPInterval &x)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_RETCODE SCIPincludeHeurObjpscostdiving(SCIP *scip)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
#define DEFAULT_DEPTHFACNOSOL
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
static void calcPscostQuot(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real primsol, SCIP_Real frac, int rounddir, SCIP_Real *pscostquot, SCIP_Bool *roundup)
static SCIP_DECL_HEURCOPY(heurCopyObjpscostdiving)
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
int SCIPgetNBinVars(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_Bool SCIPisStopped(SCIP *scip)
static SCIP_DECL_HEUREXIT(heurExitObjpscostdiving)
SCIP_Real SCIPgetVarLbDive(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPstartDive(SCIP *scip)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPendDive(SCIP *scip)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
LP diving heuristic that changes variable's objective value instead of bounds, using pseudo cost valu...
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetVarObjDive(SCIP *scip, SCIP_VAR *var)
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_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)