46 #define HEUR_NAME "clique" 47 #define HEUR_DESC "LNS heuristic using a clique partition to restrict the search neighborhood" 48 #define HEUR_DISPCHAR 'Q' 49 #define HEUR_PRIORITY 5000 51 #define HEUR_FREQOFS 0 52 #define HEUR_MAXDEPTH -1 53 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 54 #define HEUR_USESSUBSCIP TRUE 56 #define DEFAULT_MAXNODES 5000LL 57 #define DEFAULT_MININTFIXINGRATE 0.65 58 #define DEFAULT_MINMIPFIXINGRATE 0.65 60 #define DEFAULT_MINIMPROVE 0.01 63 #define DEFAULT_MINNODES 500LL 64 #define DEFAULT_NODESOFS 500LL 65 #define DEFAULT_NODESQUOT 0.1 66 #define DEFAULT_MAXPROPROUNDS 2 67 #define DEFAULT_MAXBACKTRACKS 10 68 #define DEFAULT_COPYCUTS TRUE 71 #define DEFAULT_USELOCKFIXINGS FALSE 110 int* cliquesizes = (
int*)dataptr;
112 return cliquesizes[ind2] - cliquesizes[ind1];
129 for( v = 0; v < ncliquevars; ++v )
164 int probingdepthofonefix;
177 assert(scip != NULL);
178 assert(heurdata != NULL);
179 assert(onefixvars != NULL);
180 assert(nonefixvars != NULL);
181 assert(cutoff != NULL);
191 for( c = ncliques - 1; c >= 0; --c )
196 SCIPsort(permutation, compCliquesSize, (
void*)cliquesizes, ncliques);
199 for( c = ncliques - 1; c >= 1; --c )
201 assert(cliquesizes[permutation[c]] <= cliquesizes[permutation[c-1]]);
206 probingdepthofonefix = 0;
212 for( c = 0; c < ncliques; ++c )
219 bestclique = firstclique;
221 if( bestclique >= ncliques )
225 assert(!propagated[permutation[bestclique]]);
227 for( i = firstclique + 1; i < ncliques; ++i)
229 if( cliquesizes[permutation[i]] < bestcliquesize )
232 if( propagated[permutation[i]] )
237 if( cliquesize > bestcliquesize )
240 bestcliquesize = cliquesize;
242 else if( cliquesize == 0 )
244 propagated[permutation[i]] =
TRUE;
247 clique = cliques[permutation[bestclique]];
248 propagated[permutation[bestclique]] =
TRUE;
250 while( firstclique < ncliques && propagated[permutation[firstclique]] )
257 for( v = 0; v < ncliquevars; ++v )
284 if( cliquevals[bestpos] )
302 assert(bestpos >= 0);
322 if( cliquevals[bestpos] )
335 for( ; v < ncliquevars; ++v )
355 else if( bestpos >= 0 )
357 assert(bestpos <= ncliquevars);
360 onefixvars[(*nonefixvars)] = cliquevars[bestpos];
363 if( cliquevals[bestpos] )
366 onefixvals[(*nonefixvars)] = 1;
371 onefixvals[(*nonefixvars)] = 0;
383 SCIPdebugMessage(
"propagate fixings of clique %d: cutoff=%u\n", c, *cutoff);
395 if( *nonefixvars > 0 )
397 if( probingdepthofonefix > 0 )
401 probingdepthofonefix = 0;
408 if(
SCIPvarGetLbLocal(onefixvars[*nonefixvars - 1]) < 1.5 - onefixvals[*nonefixvars - 1]
409 &&
SCIPvarGetUbLocal(onefixvars[*nonefixvars - 1]) > 0.5 - onefixvals[*nonefixvars - 1] )
418 SCIPdebugMessage(
"backtrack %d was %sfeasible\n", nbacktracks, (*cutoff ?
"in" :
""));
422 assert(*cutoff ==
TRUE);
435 for( i = 0; i < *nonefixvars; ++i )
444 SCIPdebugMsg(scip,
"probing was infeasible after %d backtracks\n", nbacktracks);
455 else if( nbacktracks > heurdata->maxbacktracks )
457 SCIPdebugMsg(scip,
"interrupt probing after %d backtracks\n", nbacktracks);
469 assert((*nonefixvars > 0) || probingdepthofonefix == 0 );
476 SCIPdebugMsg(scip,
"applied %d of %d cliques in probing\n", c, ncliques);
477 SCIPdebugMsg(scip,
"probing was %sfeasible\n", (*cutoff) ?
"in" :
"");
497 assert(scip != NULL);
498 assert(subscip != NULL);
499 assert(subvars != NULL);
500 assert(subsol != NULL);
501 assert(success != NULL);
534 assert(
scip != NULL);
535 assert(heur != NULL);
550 assert(heur != NULL);
552 assert(
scip != NULL);
556 assert(heurdata != NULL);
571 assert(heur != NULL);
573 assert(
scip != NULL);
577 assert(heurdata != NULL);
579 heurdata->usednodes = 0;
612 assert(heur != NULL);
614 assert(
scip != NULL);
615 assert(result != NULL);
621 assert(heurdata != NULL);
640 nstallnodes += heurdata->nodesofs;
643 nstallnodes -= heurdata->usednodes;
644 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
647 if( nstallnodes < heurdata->minnodes )
649 SCIPdebugMsg(
scip,
"skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT
", minnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->minnodes);
687 #ifdef COLLECTSTATISTICS 708 SCIPdebugMsg(
scip,
"npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands, heurdata->minintfixingrate);
710 if( npscands > oldnpscands * (1.0 - heurdata->minintfixingrate) )
712 if( heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 - heurdata->minintfixingrate) )
726 SCIPdebugMsg(
scip,
"after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n",
727 npscands, oldnpscands, allrowsfulfilled, heurdata->minintfixingrate);
729 if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minintfixingrate) )
764 SCIPwarningMessage(
scip,
"Error while solving LP in clique heuristic; LP solve terminated with code <%d>\n",
796 SCIPdebugMsg(
scip,
"clique heuristic found roundable primal solution: obj=%g\n",
831 for( i = 0; i < nonefixvars; ++i )
880 SCIP_CALL(
SCIPcopyConsCompression(
scip, subscip, varmap, NULL,
"_clique", NULL, NULL, 0,
FALSE,
FALSE,
TRUE, &valid) );
882 if( heurdata->copycuts )
888 for( i = 0; i < nvars; i++ )
948 minimprove = heurdata->minimprove;
964 cutoffbound = MIN(upperbound, cutoffbound);
988 SCIPdebugMsg(
scip,
"solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT
", maxnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->maxnodes);
1001 for( i = 0; i < nsubsols && !success; ++i )
1015 for( i = 0; i < nonefixvars; ++i )
1092 assert(heur != NULL);
1102 "minimum percentage of integer variables that have to be fixable",
1106 "minimum percentage of fixed variables in the sub-MIP",
1110 "maximum number of nodes to regard in the subproblem",
1114 "number of nodes added to the contingent of the total nodes",
1118 "minimum number of nodes required to start the subproblem",
1122 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1126 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1130 "maximum number of propagation rounds during probing (-1 infinity)",
1134 "should all active cuts from cutpool be copied to constraints in subproblem?",
1138 "should more variables be fixed based on variable locks if the fixing rate was not reached?",
1142 "maximum number of backtracks during the fixing process",
#define DEFAULT_MINMIPFIXINGRATE
#define DEFAULT_MININTFIXINGRATE
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
LNS heuristic using a clique partition to restrict the search neighborhood.
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
int SCIPgetProbingDepth(SCIP *scip)
#define SCIPallocClearBufferArray(scip, ptr, num)
public methods for implications, variable bounds, and cliques
static int getCliqueUnfixedVars(SCIP_CLIQUE *clique)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
static SCIP_DECL_HEURFREE(heurFreeClique)
static SCIP_DECL_HEUREXEC(heurExecClique)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPgetNPseudoBranchCands(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
#define DEFAULT_NODESQUOT
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
#define DEFAULT_MAXPROPROUNDS
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 DEFAULT_MAXBACKTRACKS
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
#define SCIPfreeBufferArray(scip, ptr)
enum SCIP_LPSolStat SCIP_LPSOLSTAT
SCIP_RETCODE SCIPcreate(SCIP **scip)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPdebugPrintCons(x, y, z)
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_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *newsol, SCIP_SOL *subsol, SCIP_Bool *success)
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeurClique(SCIP *scip)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
#define SCIPfreeBufferArrayNull(scip, ptr)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
const char * SCIPvarGetName(SCIP_VAR *var)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
#define DEFAULT_USELOCKFIXINGS
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
#define DEFAULT_MINIMPROVE
static SCIP_RETCODE applyCliqueFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **onefixvars, SCIP_Shortbool *onefixvals, int *nonefixvars, SCIP_Bool *cutoff)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
#define SCIPallocBufferArray(scip, ptr, num)
public data structures and miscellaneous methods
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
int SCIPgetDepth(SCIP *scip)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
void SCIPenableVarHistory(SCIP *scip)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
int SCIPgetNSols(SCIP *scip)
static SCIP_DECL_SORTINDCOMP(compCliquesSize)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
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)
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
#define SCIP_MAXTREEDEPTH
int SCIPgetNBinVars(SCIP *scip)
SCIP_Bool SCIPinProbing(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
int SCIPgetNConss(SCIP *scip)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
int SCIPgetNCliques(SCIP *scip)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_Bool SCIPallColsInLP(SCIP *scip)
static SCIP_DECL_HEURINIT(heurInitClique)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
#define SCIP_CALL_ABORT(x)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
static SCIP_DECL_HEURCOPY(heurCopyClique)
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_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
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)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)