38#define HEUR_NAME "redsize"
39#define HEUR_DESC "primal heuristic that solves the problem with a sparser matrix as a submip"
40#define HEUR_DISPCHAR 'u'
41#define HEUR_PRIORITY 536870911
44#define HEUR_MAXDEPTH -1
45#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
46#define HEUR_USESSUBSCIP TRUE
48#define DEFAULT_REDUCTIONRATE 0.75
52 SCIP_Real reductionrate;
70 SCIP_Real** solclustering;
86 for(
i = 0;
i < nbins; ++
i )
90 for( t = 0; t < ncluster; ++t )
103 for(
i = 0;
i < nbins; ++
i )
118 SCIP_Real percentile,
137 for(
i = 0;
i < size; ++
i )
139 for( j = 0; j <
i; ++j )
144 nonzeros[nnonzeros] =
MAX(scale * (matrix[
i][j]+matrix[j][
i]), matrix[
i][j] - matrix[j][
i]);
145 idxnonzeros[nnonzeros] =
i * size + j;
150 if( currentsize < nnonzeros + 2 )
164 for(
i = 0;
i < nnonzeros * percentile; ++
i )
166 j = idxnonzeros[
i] % size;
167 k = idxnonzeros[
i] / size;
185 SCIP_Real reductionrate,
186 SCIP_Longint maxnodes
190 SCIP_Real** cmatrix_orig;
191 SCIP_Real** cmatrix_red;
208 assert(0.0 <= reductionrate && reductionrate <= 1.0);
215 assert(nbins > 0 && ncluster > 0 && nbins >= ncluster);
236 for(
i = 0;
i < nbins; ++
i )
239 for( j = 0; j < nbins; ++j )
241 cmatrix_red[
i][j] = cmatrix_orig[
i][j];
301 for(
i = 0;
i < nsubsols; ++
i )
307 for(
i = 0;
i < nbins; ++
i )
404 "percentile of transition probabilities that gets deleted in the submip",
SCIP_RETCODE SCIPincludeCycPlugins(SCIP *scip)
SCIP plugins for cycle clustering.
#define SCIP_CALL_ABORT(x)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
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 SCIPsetCharParam(SCIP *scip, const char *name, char value)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
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_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
int SCIPgetNSols(SCIP *scip)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_RETCODE SCIPtrySolFree(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 SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_RETCODE SCIPreduceMatrixSize(SCIP *scip, SCIP_Real **matrix, SCIP_Real percentile, SCIP_Real scale, int size)
SCIP_RETCODE SCIPincludeHeurRedsize(SCIP *scip)
static SCIP_RETCODE SCIPapplyRedSize(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real reductionrate, SCIP_Longint maxnodes)
#define DEFAULT_REDUCTIONRATE
static SCIP_RETCODE SCIPcycAddIncompleteSol(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_RESULT *result)
primal heuristic that solves the problem with a sparser matrix as a submip
SCIP_RETCODE assignVars(SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
int SCIPcycGetNBins(SCIP *scip)
SCIP_Real SCIPcycGetScale(SCIP *scip)
int SCIPcycGetNCluster(SCIP *scip)
SCIP_VAR *** SCIPcycGetBinvars(SCIP *scip)
SCIP_Real ** SCIPcycGetCmatrix(SCIP *scip)
SCIP_RETCODE SCIPcreateProbCyc(SCIP *scip, const char *name, int nbins, int ncluster, SCIP_Real **cmatrix)
problem data for cycle clustering problem
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE