76#define HEUR_NAME "clique"
77#define HEUR_DESC "LNS heuristic using a clique partition to restrict the search neighborhood"
78#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
79#define HEUR_PRIORITY 5000
82#define HEUR_MAXDEPTH -1
83#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
84#define HEUR_USESSUBSCIP TRUE
86#define DEFAULT_MAXNODES 5000LL
87#define DEFAULT_MININTFIXINGRATE 0.65
88#define DEFAULT_MINMIPFIXINGRATE 0.65
90#define DEFAULT_MINIMPROVE 0.01
92#define DEFAULT_MINNODES 500LL
93#define DEFAULT_NODESOFS 500LL
94#define DEFAULT_NODESQUOT 0.1
95#define DEFAULT_MAXPROPROUNDS 2
96#define DEFAULT_MAXBACKTRACKS 10
97#define DEFAULT_COPYCUTS TRUE
99#define DEFAULT_USELOCKFIXINGS FALSE
137 int* cliquesizes = (
int*)dataptr;
139 return cliquesizes[ind2] - cliquesizes[ind1];
156 for( v = 0; v < ncliquevars; ++v )
192 int probingdepthofonefix;
219 for(
c = ncliques - 1;
c >= 0; --
c )
224 SCIPsort(permutation, compCliquesSize, (
void*)cliquesizes, ncliques);
227 for(
c = ncliques - 1;
c >= 1; --
c )
229 assert(cliquesizes[permutation[
c]] <= cliquesizes[permutation[
c-1]]);
234 probingdepthofonefix = 0;
240 for(
c = 0;
c < ncliques; ++
c )
247 bestclique = firstclique;
249 if( bestclique >= ncliques )
253 assert(!propagated[permutation[bestclique]]);
255 for(
i = firstclique + 1;
i < ncliques; ++
i)
257 if( cliquesizes[permutation[
i]] < bestcliquesize )
260 if( propagated[permutation[
i]] )
265 if( cliquesize > bestcliquesize )
268 bestcliquesize = cliquesize;
270 else if( cliquesize == 0 )
272 propagated[permutation[
i]] =
TRUE;
275 clique = cliques[permutation[bestclique]];
276 propagated[permutation[bestclique]] =
TRUE;
278 while( firstclique < ncliques && propagated[permutation[firstclique]] )
285 for( v = 0; v < ncliquevars; ++v )
312 if( cliquevals[bestpos] )
350 if( cliquevals[bestpos] )
363 for( ; v < ncliquevars; ++v )
383 else if( bestpos >= 0 )
385 assert(bestpos <= ncliquevars);
388 onefixvars[(*nonefixvars)] = cliquevars[bestpos];
391 if( cliquevals[bestpos] )
394 onefixvals[(*nonefixvars)] = 1;
399 onefixvals[(*nonefixvars)] = 0;
423 if( *nonefixvars > 0 )
425 if( probingdepthofonefix > 0 )
428 probingdepthofonefix = 0;
435 if(
SCIPvarGetLbLocal(onefixvars[*nonefixvars - 1]) < 1.5 - onefixvals[*nonefixvars - 1]
436 &&
SCIPvarGetUbLocal(onefixvars[*nonefixvars - 1]) > 0.5 - onefixvals[*nonefixvars - 1] )
454 SCIPdebugMsg(
scip,
"probing was infeasible after %d backtracks\n", nbacktracks);
456 if( enabledconflicts )
465 for(
i = 0;
i < *nonefixvars; ++
i )
483 else if( nbacktracks >
heurdata->maxbacktracks )
497 assert((*nonefixvars > 0) || probingdepthofonefix == 0 );
626 nstallnodes =
MIN(nstallnodes,
heurdata->maxnodes);
629 if( nstallnodes < heurdata->minnodes )
672#ifdef COLLECTSTATISTICS
690 SCIPdebugMsg(
scip,
"npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands,
heurdata->minintfixingrate);
692 if( npscands > oldnpscands * (1.0 -
heurdata->minintfixingrate) )
694 if(
heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 -
heurdata->minintfixingrate) )
708 SCIPdebugMsg(
scip,
"after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n",
709 npscands, oldnpscands, allrowsfulfilled,
heurdata->minintfixingrate);
711 if( !allrowsfulfilled && npscands > oldnpscands * (1 -
heurdata->minintfixingrate) )
744 if( nunfixedcols > 0.5 * ncols )
747 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
748 100.0 * (nunfixedcols / (
SCIP_Real)ncols), nunfixedcols, ncols);
765 SCIPwarningMessage(
scip,
"Error while solving LP in clique heuristic; LP solve terminated with code <%d>\n",
799 SCIPdebugMsg(
scip,
"clique heuristic found roundable primal solution: obj=%g\n",
838 for(
i = 0;
i < nonefixvars; ++
i )
886 SCIP_CALL(
SCIPcopyConsCompression(
scip, subscip, varmap,
NULL,
"_clique",
NULL,
NULL, 0,
FALSE,
FALSE,
FALSE,
960 cutoffbound =
MIN(upperbound, cutoffbound);
1004 for(
i = 0;
i < nonefixvars; ++
i )
1085 "minimum percentage of integer variables that have to be fixable",
1089 "minimum percentage of fixed variables in the sub-MIP",
1093 "maximum number of nodes to regard in the subproblem",
1097 "number of nodes added to the contingent of the total nodes",
1101 "minimum number of nodes required to start the subproblem",
1105 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1109 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1113 "maximum number of propagation rounds during probing (-1 infinity)",
1117 "should all active cuts from cutpool be copied to constraints in subproblem?",
1121 "should more variables be fixed based on variable locks if the fixing rate was not reached?",
1125 "maximum number of backtracks during the fixing process",
#define DEFAULT_MAXPROPROUNDS
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
#define SCIP_MAXTREEDEPTH
#define SCIP_CALL_ABORT(x)
#define SCIP_LONGINT_FORMAT
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 SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
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 threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
int SCIPgetNConss(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
SCIP_RETCODE SCIPaddConflict(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
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_Bool SCIPisParamFixed(SCIP *scip, const char *name)
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 SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
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 SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
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 SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPincludeHeurClique(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
int SCIPgetNPseudoBranchCands(SCIP *scip)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
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_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Bool SCIPallColsInLP(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
int SCIPgetNUnfixedLPCols(SCIP *scip)
int SCIPgetNLPCols(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetProbingDepth(SCIP *scip)
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
int SCIPgetNSols(SCIP *scip)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
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_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPgetNCliques(SCIP *scip)
void SCIPenableVarHistory(SCIP *scip)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
#define DEFAULT_NODESQUOT
#define DEFAULT_MININTFIXINGRATE
#define DEFAULT_MINIMPROVE
#define DEFAULT_MINMIPFIXINGRATE
#define DEFAULT_MAXBACKTRACKS
static SCIP_RETCODE applyCliqueFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool enabledconflicts, SCIP_VAR **onefixvars, SCIP_Shortbool *onefixvals, int *nonefixvars, SCIP_Bool *cutoff)
static int getCliqueUnfixedVars(SCIP_CLIQUE *clique)
#define DEFAULT_USELOCKFIXINGS
LNS heuristic using a clique partition to restrict the search neighborhood.
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for primal heuristics
public methods for implications, variable bounds, and cliques
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
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
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
@ SCIP_CONFTYPE_PROPAGATION
struct SCIP_Cons SCIP_CONS
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
struct SCIP_Clique SCIP_CLIQUE
enum SCIP_LPSolStat SCIP_LPSOLSTAT
@ SCIP_LPSOLSTAT_INFEASIBLE
@ SCIP_LPSOLSTAT_OBJLIMIT
struct SCIP_HashMap SCIP_HASHMAP
#define SCIP_DECL_SORTINDCOMP(x)
enum SCIP_Retcode SCIP_RETCODE