41#define HEUR_NAME "cycgreedy"
42#define HEUR_DESC "primal heuristic template"
43#define HEUR_DISPCHAR 'h'
44#define HEUR_PRIORITY 536870911
47#define HEUR_MAXDEPTH -1
48#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
49#define HEUR_USESSUBSCIP FALSE
54 int lasteffectrootdepth;
67 SCIP_Real objective = 0.0;
71 for(
c = 0;
c < ncluster; ++
c )
73 c2 = (
c + 1 ) % ncluster;
74 objective += qmatrix[
c][c2] - qmatrix[c2][
c];
75 objective += scale * qmatrix[
c][
c];
85 SCIP_Real** clusterassignment,
97 for( k = 0; k < ncluster; ++k )
99 for( l = 0; l < ncluster; ++l )
103 for(
i = 0;
i < nbins; ++
i )
105 for( j = 0; j < nbins; ++j )
108 if( clusterassignment[
i][k] < 1 || clusterassignment[j][l] < 1 )
111 qmatrix[k][l] += cmatrix[
i][j];
123 SCIP_Real** clusterassignment,
135 for( cluster = 0; cluster < ncluster; ++cluster )
137 for( bin = 0; bin < nbins; ++bin )
141 if( clusterassignment[bin][cluster] == 1 )
144 if( cluster != newcluster )
146 qmatrix[newcluster][cluster] += temp * cmatrix[newbin][bin];
147 qmatrix[cluster][newcluster] += temp * cmatrix[bin][newbin];
152 qmatrix[newcluster][newcluster] += cmatrix[newbin][bin];
154 qmatrix[newcluster][newcluster] += (cmatrix[newbin][bin] + cmatrix[bin][newbin]) * temp;
168 SCIP_Real** clusterassignment,
182 for(
i = 0;
i < nbins; ++
i )
184 temp = (clusterassignment[
i][
phiinv(newcluster, ncluster)] < 1 ? 0 : 1);
185 obj += (cmatrix[
i][newbin] - cmatrix[newbin][
i]) * temp;
186 temp = (clusterassignment[
i][
phi(newcluster, ncluster)] < 1 ? 0 : 1);
187 obj -= (cmatrix[
i][newbin] - cmatrix[newbin][
i]) * temp;
188 temp = (clusterassignment[
i][newcluster] < 1 ? 0 : 1);
189 obj += (cmatrix[
i][newbin] + cmatrix[newbin][
i]) * temp;
200 SCIP_Real** clusterassignment,
203 SCIP_Bool* isassigned,
211 SCIP_Real* binobjective;
212 SCIP_Bool** clusterispossible;
228 for(
i = 0;
i < nbins; ++
i )
234 for(
c = 0;
c < ncluster; ++
c )
238 if( binsincluster[
c] == 0 )
240 for(
i = 0;
i < nbins; ++
i )
247 binobjective[
i] =
getTempObj(
scip, qmatrix, cmatrix, clusterassignment,
i,
c, nbins, ncluster);
249 if( binobjective[
i] > tempobj )
252 tempobj = binobjective[
i];
261 for( c1 = 0; c1 < ncluster; ++c1 )
263 clusterassignment[save][c1] = 0;
266 clusterassignment[save][
c] = 1;
271 isassigned[save] =
TRUE;
272 *amountassigned += 1;
275 updateIrrevMat(clusterassignment, qmatrix, cmatrix, save,
c, nbins, ncluster);
280 for(
i = 0;
i < nbins; ++
i )
286 for(
i = 0;
i < nbins; ++
i )
292 for( c1 = 0; c1 < ncluster; ++c1 )
295 if( 0 != clusterassignment[
i][c1] )
296 clusterispossible[
i][c1] =
TRUE;
298 clusterispossible[
i][c1] =
FALSE;
302 for( c2 = 0; c2 < ncluster; ++c2 )
304 if( !clusterispossible[
i][c2] || clusterassignment[
i][c2] == 0 )
308 save = (int) clusterassignment[
i][c2];
309 clusterassignment[
i][c2] = 1;
312 tempobj =
getTempObj(
scip, qmatrix, cmatrix, clusterassignment,
i, c2, nbins, ncluster);
317 binobjective[
i] = tempobj;
321 clusterassignment[
i][c2] = save;
325 if( localheur &&
SCIPisGT(
scip, binobjective[
i], *objective) )
330 for(
i = 0;
i < nbins; ++
i )
334 max = binobjective[
i];
339 assert(!isassigned[ind] && ind > -1 && ind < nbins);
342 for( c1 = 0; c1 < ncluster; ++c1 )
344 clusterassignment[ind][c1] = 0;
347 clusterassignment[ind][bestcluster[ind]] = 1;
348 binsincluster[bestcluster[ind]]++;
349 *amountassigned += 1;
350 isassigned[ind] =
TRUE;
353 updateIrrevMat(clusterassignment, qmatrix, cmatrix, ind, bestcluster[ind], nbins, ncluster);
357 for(
i = 0;
i < nbins; ++
i )
446 SCIP_Real** clustering;
448 SCIP_Bool* isassigned;
451 SCIP_Bool possible =
TRUE;
452 SCIP_Bool feasible =
FALSE;
477 assert(nbins > 0 && ncluster > 0);
485 for (
i = 0;
i < nbins; ++
i )
494 for( j = 0; j < ncluster; ++j )
497 clustering[
i][j] = -1;
504 for(
i = 0;
i < nbins; ++
i )
506 for( j = 0; j < ncluster; ++j )
508 if(
NULL == binvars[
i][j] )
522 isassigned[
i] =
TRUE;
525 for(
c = 0;
c < ncluster; ++
c )
527 if( clustering[
i][
c] == -1 )
528 clustering[
i][
c] = 0;
536 for(
i = 0;
i < nbins; ++
i )
541 for( j = 0; j < ncluster; ++j )
543 if( 0 == clustering[
i][j] )
545 if( 1 == clustering[
i][j] )
549 if( ncluster == amountzeros || sum > 1 )
553 if( amountassigned < nbins && possible )
560 while( amountassigned < nbins )
563 isassigned, nbins, ncluster, &amountassigned, binsincluster, &
obj ) );
586 for (
i = 0;
i < nbins; ++
i )
632 "localheur",
"If set to true, heuristic assigns bins as soon as any improvement is found",
Constraint handler for AND constraints, .
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 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,)
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, 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)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocMemory(scip, ptr)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeMemory(scip, ptr)
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 SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetEffectiveRootDepth(SCIP *scip)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIPcreateSol(scip, &heurdata->sol, heur))
static SCIP_Real getObjective(SCIP *scip, SCIP_Real **qmatrix, SCIP_Real scale, int ncluster)
SCIP_RETCODE SCIPincludeHeurCycGreedy(SCIP *scip)
static void computeIrrevMat(SCIP_Real **clusterassignment, SCIP_Real **qmatrix, SCIP_Real **cmatrix, int nbins, int ncluster)
static void updateIrrevMat(SCIP_Real **clusterassignment, SCIP_Real **qmatrix, SCIP_Real **cmatrix, int newbin, int newcluster, int nbins, int ncluster)
static SCIP_RETCODE assignNextBin(SCIP *scip, SCIP_Bool localheur, SCIP_Real **clusterassignment, SCIP_Real **cmatrix, SCIP_Real **qmatrix, SCIP_Bool *isassigned, int nbins, int ncluster, int *amountassigned, int *binsincluster, SCIP_Real *objective)
static SCIP_Real getTempObj(SCIP *scip, SCIP_Real **qmatrix, SCIP_Real **cmatrix, SCIP_Real **clusterassignment, int newbin, int newcluster, int nbins, int ncluster)
Greedy primal heuristic. States are assigned to clusters iteratively. At each iteration all possible ...
assert(minobj< SCIPgetCutoffbound(scip))
internal miscellaneous methods
SCIP_RETCODE assignVars(SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
int SCIPcycGetNBins(SCIP *scip)
int phiinv(int k, int ncluster)
SCIP_Real SCIPcycGetScale(SCIP *scip)
int SCIPcycGetNCluster(SCIP *scip)
SCIP_VAR *** SCIPcycGetBinvars(SCIP *scip)
SCIP_Real ** SCIPcycGetCmatrix(SCIP *scip)
SCIP_Bool isPartition(SCIP *scip, SCIP_Real **solclustering, int nbins, int ncluster)
problem data for cycle clustering problem
static SCIP_Real phi(SCIP *scip, SCIP_Real val, SCIP_Real lb, SCIP_Real ub)
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXITSOL(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_Retcode SCIP_RETCODE