29 #define HEUR_NAME "intdiving" 30 #define HEUR_DESC "LP diving heuristic that fixes binary variables with large LP value to one" 31 #define HEUR_DISPCHAR 'n' 32 #define HEUR_PRIORITY -1003500 34 #define HEUR_FREQOFS 9 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.05 47 #define DEFAULT_MAXLPITEROFS 1000 48 #define DEFAULT_MAXDIVEUBQUOT 0.8 50 #define DEFAULT_MAXDIVEAVGQUOT 0.0 52 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 53 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 54 #define DEFAULT_BACKTRACK TRUE 56 #define MINLPITER 10000 108 assert(heur !=
NULL);
114 assert(heurdata !=
NULL);
128 assert(heur !=
NULL);
133 assert(heurdata !=
NULL);
139 heurdata->nlpiterations = 0;
140 heurdata->nsuccess = 0;
152 assert(heur !=
NULL);
157 assert(heurdata !=
NULL);
195 assert(heur !=
NULL);
198 assert(result !=
NULL);
227 assert(heurdata !=
NULL);
232 maxdepth =
MAX(maxdepth, 100);
233 if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
240 maxnlpiterations = (
SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
241 maxnlpiterations += heurdata->maxlpiterofs;
244 if( heurdata->nlpiterations >= maxnlpiterations )
248 maxnlpiterations =
MAX(maxnlpiterations, heurdata->nlpiterations +
MINLPITER);
260 if( heurdata->maxdiveubquotnosol > 0.0 )
265 if( heurdata->maxdiveavgquotnosol > 0.0 )
273 if( heurdata->maxdiveubquot > 0.0 )
278 if( heurdata->maxdiveavgquot > 0.0 )
284 searchbound =
MIN(searchubbound, searchavgbound);
290 maxdivedepth =
MIN(maxdivedepth, maxdepth);
301 SCIPdebugMsg(
scip,
"(node %" SCIP_LONGINT_FORMAT
") executing intdiving heuristic: depth=%d, %d non-fixed, dualbound=%g, searchbound=%g\n",
310 for( c = 0; c < nfixcands; ++c )
319 assert(c >= nbinfixcands);
329 for( i = c; i > nbinfixcands; --i )
331 fixcands[i] = fixcands[i-1];
332 fixcandscores[i] = fixcandscores[i-1];
336 right = nbinfixcands;
349 for( i = right; i > left && score > fixcandscores[i-1]; --i )
351 fixcands[i] = fixcands[i-1];
352 fixcandscores[i] = fixcandscores[i-1];
355 fixcandscores[i] = score;
356 SCIPdebugMsg(
scip,
" <%s>: ncliques=%d/%d, nimpls=%d/%d, inferencescore=%g, colveclen=%d -> score=%g\n",
376 || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations && objval < searchbound))
395 nnewlpiterations = 0;
406 for( c = nextcand; c < nbinfixcands; ++c )
424 if( solval > bestsolval )
448 for( c =
MAX(nextcand, nbinfixcands); c < nfixcands; ++c )
472 if( frac < bestfrac )
486 assert(-1 <= bestcand && bestcand < nfixcands);
492 var = fixcands[bestcand];
507 SCIPdebugMsg(
scip,
"Selected variable <%s> already fixed to [%g,%g], diving aborted \n",
514 SCIPdebugMsg(
scip,
"selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
521 SCIPdebugMsg(
scip,
" dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT
"/%" SCIP_LONGINT_FORMAT
", %d unfixed: var <%s>, sol=%g, oldbounds=[%g,%g], fixed to %g\n",
533 if( nnewdomreds > 0 || !
SCIPisEQ(
scip, bestsolval, bestfixval) )
545 SCIPwarningMessage(
scip,
"Error while solving LP in Intdiving heuristic; LP solve terminated with code <%d>\n",retstat);
557 heurdata->nlpiterations += nnewlpiterations;
567 if( cutoff && !backtracked && heurdata->backtrack )
586 while( backtracked );
595 if( nnewlpiterations > 0 || !
SCIPisEQ(
scip, bestsolval, bestfixval) )
620 nextcand = bestcand+1;
622 SCIPdebugMsg(
scip,
" -> lpsolstat=%d, objval=%g/%g\n", lpsolstat, objval, searchbound);
632 heurdata->nsuccess++;
660 assert(heur !=
NULL);
670 "heuristics/intdiving/minreldepth",
671 "minimal relative depth to start diving",
674 "heuristics/intdiving/maxreldepth",
675 "maximal relative depth to start diving",
678 "heuristics/intdiving/maxlpiterquot",
679 "maximal fraction of diving LP iterations compared to node LP iterations",
682 "heuristics/intdiving/maxlpiterofs",
683 "additional number of allowed LP iterations",
686 "heuristics/intdiving/maxdiveubquot",
687 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
690 "heuristics/intdiving/maxdiveavgquot",
691 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
694 "heuristics/intdiving/maxdiveubquotnosol",
695 "maximal UBQUOT when no solution was found yet (0.0: no limit)",
698 "heuristics/intdiving/maxdiveavgquotnosol",
699 "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
702 "heuristics/intdiving/backtrack",
703 "use one level of backtracking if infeasibility is encountered?",
int SCIPgetNIntVars(SCIP *scip)
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetProbingDepth(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasFracIntegral(SCIP *scip, SCIP_Real val)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPgetNPseudoBranchCands(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
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)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
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)
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)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
static SCIP_DECL_HEURINIT(heurInitIntdiving)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
LP diving heuristic that fixes variables with integral LP value.
const char * SCIPheurGetName(SCIP_HEUR *heur)
static SCIP_DECL_HEUREXEC(heurExecIntdiving)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPincludeHeurIntdiving(SCIP *scip)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
static SCIP_DECL_HEUREXIT(heurExitIntdiving)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
static SCIP_DECL_HEURCOPY(heurCopyIntdiving)
#define DEFAULT_MAXLPITEROFS
#define DEFAULT_MINRELDEPTH
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
int SCIPgetDepth(SCIP *scip)
#define DEFAULT_MAXDIVEAVGQUOT
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
static SCIP_DECL_HEURFREE(heurFreeIntdiving)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
void SCIPenableVarHistory(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
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)
#define SCIP_MAXTREEDEPTH
int SCIPgetNBinVars(SCIP *scip)
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
int SCIPcolGetNNonz(SCIP_COL *col)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
#define DEFAULT_MAXLPITERQUOT
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
#define DEFAULT_MAXRELDEPTH
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPgetVarAvgInferenceScore(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_Real SCIPfloor(SCIP *scip, SCIP_Real val)
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)
#define DEFAULT_MAXDIVEUBQUOTNOSOL
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
#define DEFAULT_MAXDIVEUBQUOT