heur_cyckerlin.c
Go to the documentation of this file.
22 /*---+---- 1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 #define HEUR_DESC "switch heuristic that tries to improve solution by trading states betweeen clusters"
55 /** external method that adds a solution to the list of candidate-solutions that should be improved */
77 SCIP_CALL( SCIPreallocMemoryArray(scip, &(heurdata->candidates), (SCIP_Longint) heurdata->candlength * 2) );
123 if( (SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(binvars[i][c]), SCIPvarGetLbGlobal(binvars[i][c]))) )
353 setBinToCluster(clustering, cmatrix, qmatrix, maxbin, clusterofbin[maxbin], FALSE, nbins, ncluster);
480 /* main part of the heuristic. States are switched until every state has been exchanged exactly once */
491 /* select the clustering with the best objective and reconstruct it from the start clustering */
550 /** method that randomly creates a different solution from a given solution. From each cluster, half the states are
671 SCIP_CALL( getSolutionValues(scip, sol, startclustering, binfixed, clusterofbin, nbinsincluster) );
675 SCIP_CALL( createSwitchSolution(scip, heur, cmatrix, qmatrix, binfixed, startclustering, result, nbins, ncluster) );
682 SCIP_CALL( createSwitchSolution(scip, heur, cmatrix, qmatrix, binfixed, startclustering, result, nbins, ncluster) );
752 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
static SCIP_Real getObjective(SCIP *scip, SCIP_Real **qmatrix, SCIP_Real scale, int ncluster)
Definition: heur_cyckerlin.c:217
Definition: type_result.h:33
Definition: type_result.h:47
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
Definition: struct_scip.h:59
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
static SCIP_DECL_HEUREXITSOL(heurExitsolCyckerlin)
Definition: heur_cyckerlin.c:754
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)
Definition: heur_cyckerlin.c:377
static SCIP_RETCODE runCyckerlin(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: heur_cyckerlin.c:625
static SCIP_RETCODE getSolutionValues(SCIP *scip, SCIP_SOL *bestsol, SCIP_Real **solclustering, SCIP_Bool **binfixed, int *clusterofbin, int *nbinsincluster)
Definition: heur_cyckerlin.c:90
SCIP_RETCODE assignVars(SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
Definition: probdata_cyc.c:79
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
Definition: struct_var.h:198
static SCIP_RETCODE permuteStartSolution(SCIP *scip, SCIP_Real **startclustering, SCIP_RANDNUMGEN *rnd, int nbins, int ncluster)
Definition: heur_cyckerlin.c:553
Definition: struct_misc.h:259
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
Definition: struct_sol.h:64
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)
Definition: scip_heur.c:108
Definition: type_result.h:35
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
static SCIP_Real phi(SCIP *scip, SCIP_Real val, SCIP_Real lb, SCIP_Real ub)
Definition: sepa_eccuts.c:747
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1469
Definition: type_retcode.h:33
Definition: struct_heur.h:88
static void setBinToCluster(SCIP_Real **solclustering, SCIP_Real **cmatrix, SCIP_Real **qmatrix, int newbin, int newcluster, SCIP_Bool setone, int nbins, int ncluster)
Definition: heur_cyckerlin.c:142
public data structures and miscellaneous methods
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:9945
SCIP_RETCODE SCIPincludeHeurCycKerlin(SCIP *scip)
Definition: heur_cyckerlin.c:839
static void computeIrrevMat(SCIP_Real **clustering, SCIP_Real **qmatrix, SCIP_Real **cmatrix, int nbins, int ncluster)
Definition: heur_cyckerlin.c:182
problem data for cycle clustering problem
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_RETCODE addCandSolCyckerlin(SCIP *scip, SCIP_SOL *sol)
Definition: heur_cyckerlin.c:56
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
Improvement heuristic that trades bin-variables between clusters.
SCIP_Bool isPartition(SCIP *scip, SCIP_Real **solclustering, int nbins, int ncluster)
Definition: probdata_cyc.c:48
Definition: objbenders.h:33
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)
Definition: scip_sol.c:3231
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)
Definition: heur_cyckerlin.c:241