41#define HEUR_NAME "cyckerlin"
42#define HEUR_DESC "switch heuristic that tries to improve solution by trading states betweeen clusters"
43#define HEUR_DISPCHAR '@'
44#define HEUR_PRIORITY 500
47#define HEUR_MAXDEPTH -1
48#define MAXPERMUTATIONS 5
49#define DEFAULT_RANDSEED 177
50#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
51#define HEUR_USESSUBSCIP FALSE
120 assert(nbins > 0 && ncluster > 0 && nbins > ncluster);
124 for(
i = 0;
i < nbins; ++
i )
126 for(
c = 0;
c < ncluster; ++
c )
130 if( binvars[
i][
c] !=
NULL)
166 for( cluster = 0; cluster < ncluster; ++cluster )
168 for( bin = 0; bin < nbins; ++bin )
170 if( cluster != newcluster )
172 qmatrix[newcluster][cluster] += sign * solclustering[bin][cluster] * cmatrix[newbin][bin];
173 qmatrix[cluster][newcluster] += sign * solclustering[bin][cluster] * cmatrix[bin][newbin];
179 qmatrix[newcluster][newcluster] += sign * (cmatrix[newbin][bin] + cmatrix[bin][newbin])
180 * solclustering[bin][cluster];
186 solclustering[newbin][newcluster] = (sign + 1.0) / 2.0;
204 for( k = 0; k < ncluster; ++k )
206 for( l = 0; l < ncluster; ++l )
209 for(
i = 0;
i < nbins; ++
i )
211 for( j = 0; j < nbins; ++j )
217 qmatrix[k][l] += cmatrix[
i][j] * clustering[
i][k] * clustering[j][l];
237 for(
c = 0;
c < ncluster; ++
c )
239 c2 = (
c + 1 ) % ncluster;
240 objective += ( qmatrix[
c][c2] - qmatrix[c2][
c]);
241 objective += scale * qmatrix[
c][
c];
260 int* switchedcluster,
291 for( bin = 0; bin < nbins; ++bin )
293 if( binprocessed[bin] || nbinsincluster[clusterofbin[bin]] == 1 )
295 k = clusterofbin[bin];
300 for( l = 0; l < ncluster; ++l )
302 if( binfixed[bin][k] || binfixed[bin][l] )
309 indkmin = ncluster - 1;
314 indlmin = ncluster - 1;
323 for(
i = 0;
i < nbins; ++
i )
326 irrevchg -= clustering[
i][indkmin] * (cmatrix[
i][bin] - cmatrix[bin][
i]);
327 irrevchg -= clustering[
i][(k+1) % ncluster] * (cmatrix[bin][
i] - cmatrix[
i][bin]);
329 clustering[bin][k] = 0;
330 clustering[bin][l] = 1;
332 irrevchg += clustering[
i][indlmin] * (cmatrix[
i][bin] - cmatrix[bin][
i]);
333 irrevchg += clustering[
i][(l+1) % ncluster] * (cmatrix[bin][
i] - cmatrix[
i][bin]);
335 clustering[bin][k] = 1;
336 clustering[bin][l] = 0;
341 cohchg -= clustering[
i][k] * (cmatrix[bin][
i]+ cmatrix[
i][bin]);
342 cohchg += clustering[
i][l] * (cmatrix[bin][
i]+ cmatrix[
i][bin]);
346 if( oldobjective + irrevchg + scale * cohchg > maxboundlocal )
348 maxboundlocal = oldobjective + irrevchg + scale * cohchg;
358 assert(maxbin >= 0 && maxcluster >= 0);
359 assert(maxbin < nbins && maxcluster < ncluster);\
362 setBinToCluster(clustering, cmatrix, qmatrix, maxbin, clusterofbin[maxbin],
FALSE, nbins, ncluster);
365 nbinsincluster[clusterofbin[maxbin]]--;
366 nbinsincluster[maxcluster]++;
368 clusterofbin[maxbin] = maxcluster;
369 binprocessed[maxbin] =
TRUE;
371 switchedbin[iteration] = maxbin;
372 switchedcluster[iteration] = maxcluster;
375 if( switchbound[iteration] > *maxbound )
377 *maxbound = switchbound[iteration];
378 *bestlength = iteration;
413 int* switchedcluster;
428 for(
i = 0;
i < nbins; ++
i )
435 for(
c = 0;
c < ncluster; ++
c )
437 nbinsincluster[
c] = 0;
440 for(
i = 0;
i < nbins; ++
i )
442 for(
c = 0;
c < ncluster; ++
c )
444 solclustering[
i][
c] = startclustering[
i][
c];
458 while( heurpossible )
461 for(
c = 0;
c < ncluster; ++
c )
463 nbinsincluster[
c] = 0;
466 for(
i = 0;
i < nbins; ++
i )
468 for(
c = 0;
c < ncluster; ++
c )
470 clustering[
i][
c] = solclustering[
i][
c];
490 for(
i = 0;
i < nrswitches; ++
i )
492 if( !
switchNext(
scip, cmatrix, qmatrix, clustering, binfixed, binprocessed, clusterofbin,
493 nbinsincluster, switchedbin, switchedcluster, switchbound, &maxbound, &bestlength,
i) )
501 for(
i = 0;
i <= bestlength; ++
i )
503 for(
c = 0;
c < ncluster; ++
c )
505 solclustering[switchedbin[
i]][
c] = 0;
508 solclustering[switchedbin[
i]][switchedcluster[
i]] = 1;
509 clusterofbin[switchedbin[
i]] = switchedcluster[
i];
518 if( max > objective )
536 heurpossible =
FALSE;
541 for(
i = 0;
i < nbins; ++
i )
581 for( t = 0; t < ncluster; ++t )
583 binsincluster[t] = 0;
585 for(
i = 0;
i < nbins; ++
i )
595 for(
i = 0;
i < nbins; ++
i )
605 for( t = 0; t < ncluster; ++t )
609 while(pushed < binsincluster[t] / 2)
613 if( rndcluster == nbins -1 )
618 startclustering[rndcluster][t] = 0;
619 startclustering[rndcluster][
phi(t,ncluster)] = 1;
669 for(
c = 0;
c < ncluster; ++
c )
673 for(
i = 0;
i < nbins; ++
i )
696 for(
i = 0;
i < nbins; ++
i )
702 for(
c = 0;
c < ncluster; ++
c )
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_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
#define SCIPallocMemoryArray(scip, ptr, num)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_SOL * SCIPgetBestSol(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 SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPfreeRandom(scip, &heurdata->randnumgen)
static SCIP_Real getObjective(SCIP *scip, SCIP_Real **qmatrix, SCIP_Real scale, int ncluster)
static void setBinToCluster(SCIP_Real **solclustering, SCIP_Real **cmatrix, SCIP_Real **qmatrix, int newbin, int newcluster, SCIP_Bool setone, int nbins, int ncluster)
static void computeIrrevMat(SCIP_Real **clustering, SCIP_Real **qmatrix, SCIP_Real **cmatrix, int nbins, int ncluster)
static SCIP_RETCODE createSwitchSolution(SCIP *scip, SCIP_HEUR *heur, SCIP_Real **cmatrix, SCIP_Real **qmatrix, SCIP_Bool **binfixed, SCIP_Real **startclustering, SCIP_RESULT *result, int nbins, int ncluster)
SCIP_RETCODE SCIPincludeHeurCycKerlin(SCIP *scip)
static SCIP_RETCODE runCyckerlin(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_RESULT *result)
static SCIP_RETCODE getSolutionValues(SCIP *scip, SCIP_SOL *bestsol, SCIP_Real **solclustering, SCIP_Bool **binfixed, int *clusterofbin, int *nbinsincluster)
static SCIP_RETCODE permuteStartSolution(SCIP *scip, SCIP_Real **startclustering, SCIP_RANDNUMGEN *rnd, int nbins, int ncluster)
static SCIP_Bool switchNext(SCIP *scip, SCIP_Real **cmatrix, SCIP_Real **qmatrix, SCIP_Real **clustering, SCIP_Bool **binfixed, SCIP_Bool *binprocessed, int *clusterofbin, int *nbinsincluster, int *switchedbin, int *switchedcluster, SCIP_Real *switchbound, SCIP_Real *maxbound, int *bestlength, int iteration)
SCIP_RETCODE addCandSolCyckerlin(SCIP *scip, SCIP_SOL *sol)
Improvement heuristic that trades bin-variables between clusters.
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
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_Bool isPartition(SCIP *scip, SCIP_Real **solclustering, int nbins, int ncluster)
problem data for cycle clustering problem
public data structures and miscellaneous methods
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
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXITSOL(x)
#define SCIP_DECL_HEUREXEC(x)
struct SCIP_RandNumGen SCIP_RANDNUMGEN
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE