43 #define HEUR_NAME "clique" 44 #define HEUR_DESC "LNS heuristic using a clique partition to restrict the search neighborhood" 45 #define HEUR_DISPCHAR 'Q' 46 #define HEUR_PRIORITY -1000500 48 #define HEUR_FREQOFS 0 49 #define HEUR_MAXDEPTH -1 50 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 51 #define HEUR_USESSUBSCIP TRUE 53 #define DEFAULT_MAXNODES 5000LL 54 #define DEFAULT_MINFIXINGRATE 0.25 55 #define DEFAULT_MINIMPROVE 0.01 58 #define DEFAULT_MINNODES 500LL 59 #define DEFAULT_NODESOFS 500LL 60 #define DEFAULT_NODESQUOT 0.1 61 #define DEFAULT_MAXPROPROUNDS 2 62 #define DEFAULT_RANDSEED 61 65 #define DEFAULT_MULTIPLIER 1.1 66 #define DEFAULT_COPYCUTS TRUE 106 assert(elem1 !=
NULL);
128 int* cliquepartition,
140 assert(scip !=
NULL);
141 assert(binvars !=
NULL);
142 assert(cliquepartition !=
NULL);
151 for( v = nbinvars - 1; v >= 0; --v )
153 assert(0 <= cliquepartition[v] && cliquepartition[v] < ncliques);
154 ++(cliquecount[cliquepartition[v]]);
165 for( c = 0; c < ncliques; ++c )
174 varpointers[c] = (
SCIP_VAR**) (vars + nextpos);
175 assert(cliquecount[c] > 0);
176 nextpos += cliquecount[c];
179 assert(nextpos == nbinvars);
182 for( v = 0; v < nbinvars; ++v )
184 *(varpointers[cliquepartition[v]]) = binvars[v];
185 ++(varpointers[cliquepartition[v]]);
188 for( v = 0; v < nbinvars; ++v )
189 assert(vars[v] !=
NULL);
196 nextpos = cliquecount[0];
199 for( v = 0; v < nbinvars; ++v )
203 nextpos += cliquecount[c];
207 cliquepartition[v] = cliquenumber;
209 assert(cliquepartition[v - 1] == ncliques - 1);
212 for( v = 1; v < nbinvars; ++v )
231 int* cliquepartition,
236 int* probingdepthofonefix,
254 assert(scip !=
NULL);
255 assert(heurdata !=
NULL);
256 assert(binvars !=
NULL);
257 assert(onefixvars !=
NULL);
258 assert(nonefixvars !=
NULL);
260 assert(probingdepthofonefix !=
NULL);
261 assert(cutoff !=
NULL);
262 assert(result !=
NULL);
265 *probingdepthofonefix = 0;
273 for( c = 0; c < ncliques; ++c )
280 while( v < nbinvars && cliquepartition[v] == c )
292 if( v == nbinvars && allfixed )
299 assert(bestpos < nbinvars);
300 assert(c == cliquepartition[bestpos]);
312 onefixvars[(*nonefixvars)] = binvars[v];
323 while( v < nbinvars && cliquepartition[v] == c )
362 SCIPdebugMsg(scip,
" -> solution was feasible and good enough\n");
373 if( nbinvars - v == ncliques - c )
377 assert((*probingdepthofonefix > 0 && *nonefixvars > 0) || (*probingdepthofonefix == 0 && *nonefixvars == 0));
378 assert(*cutoff || (nbinvars - v == ncliques - c) || (v == nbinvars && (c == ncliques || c == ncliques - 1)));
380 SCIPdebugMsg(scip,
"fixed %d of %d variables in probing\n", v, nbinvars);
381 SCIPdebugMsg(scip,
"applied %d of %d cliques in probing\n", c, ncliques);
382 SCIPdebugMsg(scip,
"probing was %sfeasible\n", (*cutoff) ?
"in" :
"");
384 SCIPdebugMsg(scip,
"clique heuristic rounded %d solutions and tried %d of them\n", nsolsround, nsolstried);
404 assert(scip !=
NULL);
405 assert(subscip !=
NULL);
406 assert(subvars !=
NULL);
407 assert(subsol !=
NULL);
408 assert(success !=
NULL);
442 assert(heur !=
NULL);
457 assert(heur !=
NULL);
463 assert(heurdata !=
NULL);
478 assert(heur !=
NULL);
484 assert(heurdata !=
NULL);
490 heurdata->usednodes = 0;
502 assert(heur !=
NULL);
508 assert(heurdata !=
NULL);
526 int* cliquepartition;
538 int probingdepthofonefix;
554 assert(heur !=
NULL);
557 assert(result !=
NULL);
563 assert(heurdata !=
NULL);
574 heurdata->nnodefornextrun = INT_MAX;
581 heurdata->nnodefornextrun = INT_MAX;
591 nstallnodes += heurdata->nodesofs;
594 nstallnodes -= heurdata->usednodes;
595 nstallnodes =
MIN(nstallnodes, heurdata->maxnodes);
598 if( nstallnodes < heurdata->minnodes )
600 SCIPdebugMsg(
scip,
"skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT
", minnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->minnodes);
617 SCIPsortPtr((
void**)binvars, varObjSort, nbinvars);
639 if( ncliques == nbinvars )
641 heurdata->nnodefornextrun = INT_MAX;
648 for( i = nbinvars - 1; i >= 0; --i )
650 if( cliquepartition[i] != ncliques - nbinvars + i )
652 assert(cliquepartition[i] > ncliques - nbinvars + i);
657 if( i + 2 < heurdata->minfixingrate * nbinvars )
694 SCIP_CALL(
applyCliqueFixings(
scip, heurdata, binvars, nbinvars, cliquepartition, ncliques, onefixvars, &nonefixvars, sol, &probingdepthofonefix, &cutoff, result) );
699 backtrackcutoff =
FALSE;
703 if( cutoff && nonefixvars > 0)
705 assert(probingdepthofonefix > 0);
717 SCIPdebugMsg(
scip,
"backtrack was %sfeasible\n", (backtrackcutoff ?
"in" :
""));
723 SCIPdebugMsg(
scip,
"npscands=%d, oldnpscands=%d, heurdata->minfixingrate=%g\n", npscands, oldnpscands, heurdata->minfixingrate);
725 if( npscands > oldnpscands * (1 - heurdata->minfixingrate) )
736 allfixsolfound =
FALSE;
738 if( !backtrackcutoff && solvelp )
753 SCIPwarningMessage(
scip,
"Error while solving LP in clique heuristic; LP solve terminated with code <%d>\n",
781 SCIPdebugMsg(
scip,
"clique heuristic found roundable primal solution: obj=%g\n",
793 allfixsolfound =
TRUE;
813 shortconflict = cutoff && (nonefixvars > 0);
838 if( !allfixsolfound && !lperror )
863 SCIP_CALL(
SCIPcopyConsCompression(
scip, subscip, varmap,
NULL,
"_clique",
NULL,
NULL, 0,
FALSE,
FALSE,
TRUE, &valid) );
865 if( heurdata->copycuts )
871 for( i = 0; i < nvars; i++ )
931 minimprove = heurdata->minimprove;
947 cutoffbound =
MIN(upperbound, cutoffbound);
971 SCIPdebugMsg(
scip,
"solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT
", maxnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->maxnodes);
984 for( i = 0; i < nsubsols && !success; ++i )
995 shortconflict = backtracked;
1033 if( onefixvars !=
NULL )
1054 heurdata->nnodefornextrun =
MIN(tmpnnodes, INT_MAX);
1055 SCIPdebugMsg(
scip,
"Next run will be at node %" SCIP_LONGINT_FORMAT
".\n", heurdata->nnodefornextrun);
1080 assert(heur !=
NULL);
1091 "value to increase nodenumber to determine the next run",
1095 "initial random seed value to permutate variables",
1099 "minimum percentage of integer variables that have to be fixable",
1103 "maximum number of nodes to regard in the subproblem",
1107 "number of nodes added to the contingent of the total nodes",
1111 "minimum number of nodes required to start the subproblem",
1115 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1119 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1123 "maximum number of propagation rounds during probing (-1 infinity)",
1127 "should all active cuts from cutpool be copied to constraints in subproblem?",
enum SCIP_Result SCIP_RESULT
#define DEFAULT_MULTIPLIER
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
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_RETCODE SCIPlinkCurrentSol(SCIP *scip, SCIP_SOL *sol)
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)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
static SCIP_DECL_HEURFREE(heurFreeClique)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
static SCIP_DECL_HEUREXEC(heurExecClique)
SCIP_RETCODE SCIPgetNegatedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **negvars)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPgetNPseudoBranchCands(SCIP *scip)
static SCIP_DECL_HEUREXIT(heurExitClique)
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)
int SCIPsnprintf(char *t, int len, const char *s,...)
void SCIPrandomPermuteArray(SCIP_RANDNUMGEN *randnumgen, void **array, int begin, int end)
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 SCIPduplicateBufferArray(scip, ptr, source, num)
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)
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
static SCIP_RETCODE stableSortBinvars(SCIP *scip, SCIP_VAR **binvars, int nbinvars, int *cliquepartition, int ncliques)
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)))
#define DEFAULT_MINFIXINGRATE
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...
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)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
#define DEFAULT_MINIMPROVE
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_RETCODE SCIPcalcCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
int SCIPgetNSols(SCIP *scip)
#define BMScopyMemoryArray(ptr, source, num)
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)
#define SCIP_MAXTREEDEPTH
SCIP_Bool SCIPinProbing(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
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)))
static SCIP_RETCODE applyCliqueFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **binvars, int nbinvars, int *cliquepartition, int ncliques, SCIP_VAR **onefixvars, int *nonefixvars, SCIP_SOL *sol, int *probingdepthofonefix, SCIP_Bool *cutoff, SCIP_RESULT *result)
static SCIP_DECL_SORTPTRCOMP(varObjSort)
SCIP_Bool SCIPisStopped(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)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
#define BMSclearMemoryArray(ptr, num)
#define SCIP_CALL_ABORT(x)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
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 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)