Detailed Description
improvement heuristic that exchanges binary variables between clusters. Similar to the famous kernighan/lin heuristic for graph partitioning
Definition in file heur_cyckerlin.c.
#include "heur_cyckerlin.h"
#include <assert.h>
#include <string.h>
#include "probdata_cyc.h"
#include "scip/pub_misc.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "cyckerlin" |
#define | HEUR_DESC "switch heuristic that tries to improve solution by trading states betweeen clusters" |
#define | HEUR_DISPCHAR '@' |
#define | HEUR_PRIORITY 500 |
#define | HEUR_FREQ 10 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | MAXPERMUTATIONS 5 |
#define | DEFAULT_RANDSEED 177 |
#define | HEUR_TIMING SCIP_HEURTIMING_BEFORENODE |
#define | HEUR_USESSUBSCIP FALSE |
Functions | |
SCIP_RETCODE | addCandSolCyckerlin (SCIP *scip, SCIP_SOL *sol) |
static SCIP_RETCODE | getSolutionValues (SCIP *scip, SCIP_SOL *bestsol, SCIP_Real **solclustering, SCIP_Bool **binfixed, int *clusterofbin, int *nbinsincluster) |
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_Real | getObjective (SCIP *scip, SCIP_Real **qmatrix, SCIP_Real scale, 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) |
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) |
static SCIP_RETCODE | permuteStartSolution (SCIP *scip, SCIP_Real **startclustering, SCIP_RANDNUMGEN *rnd, int nbins, int ncluster) |
static SCIP_RETCODE | runCyckerlin (SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_RESULT *result) |
static | SCIP_DECL_HEURCOPY (heurCopyCyckerlin) |
static | SCIP_DECL_HEURFREE (heurFreeCyckerlin) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolCyckerlin) |
static | SCIP_DECL_HEURINIT (heurInitCyckerlin) |
static | SCIP_DECL_HEUREXEC (heurExecCyckerlin) |
SCIP_RETCODE | SCIPincludeHeurCycKerlin (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "cyckerlin" |
Definition at line 41 of file heur_cyckerlin.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXITSOL(), SCIP_DECL_HEURFREE(), and SCIPincludeHeurCycKerlin().
◆ HEUR_DESC
#define HEUR_DESC "switch heuristic that tries to improve solution by trading states betweeen clusters" |
Definition at line 42 of file heur_cyckerlin.c.
Referenced by SCIPincludeHeurCycKerlin().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR '@' |
Definition at line 43 of file heur_cyckerlin.c.
Referenced by SCIPincludeHeurCycKerlin().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY 500 |
Definition at line 44 of file heur_cyckerlin.c.
Referenced by SCIPincludeHeurCycKerlin().
◆ HEUR_FREQ
#define HEUR_FREQ 10 |
Definition at line 45 of file heur_cyckerlin.c.
Referenced by SCIPincludeHeurCycKerlin().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 46 of file heur_cyckerlin.c.
Referenced by SCIPincludeHeurCycKerlin().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 47 of file heur_cyckerlin.c.
Referenced by SCIPincludeHeurCycKerlin().
◆ MAXPERMUTATIONS
#define MAXPERMUTATIONS 5 |
Definition at line 48 of file heur_cyckerlin.c.
Referenced by runCyckerlin().
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 177 |
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE |
Definition at line 50 of file heur_cyckerlin.c.
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXITSOL(), and SCIPincludeHeurCycKerlin().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 51 of file heur_cyckerlin.c.
Referenced by SCIPincludeHeurCycKerlin().
Function Documentation
◆ addCandSolCyckerlin()
SCIP_RETCODE addCandSolCyckerlin | ( | SCIP * | scip, |
SCIP_SOL * | sol | ||
) |
external method that adds a solution to the list of candidate-solutions that should be improved
- Parameters
-
scip SCIP data structure sol the given solution
Definition at line 65 of file heur_cyckerlin.c.
References NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPfindHeur(), SCIPheurGetData(), and SCIPreallocMemoryArray.
Referenced by SCIP_DECL_EVENTEXEC().
◆ getSolutionValues()
|
static |
get the bin-var assignment from scip and save it as a matrix
- Parameters
-
scip SCIP data structure bestsol the solution solclustering matrix to save the bin-vars binfixed matrix to save if a bin is fixed in scip clusterofbin array containing the cluster of each bin nbinsincluster number of bins in each cluster
Definition at line 99 of file heur_cyckerlin.c.
References FALSE, NULL, SCIP_OKAY, SCIPcycGetBinvars(), SCIPcycGetNBins(), SCIPcycGetNCluster(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by runCyckerlin().
◆ setBinToCluster()
|
static |
Set a bin to a new cluster, update the qmatrix.
- Parameters
-
solclustering the matrix with the clustering of the bins cmatrix the transition matrix qmatrix the matrix containing the transition probabilities between clusters newbin the bin to be changed newcluster the cluster where the bin is changed setone TRUE if the assignment is switched from 0 to 1, FALSE if 1 to 0 nbins the number of bins ncluster the number of clusters
Definition at line 151 of file heur_cyckerlin.c.
References SCIP_Real.
Referenced by switchNext().
◆ computeIrrevMat()
|
static |
initialize the q-matrix from a given (possibly incomplete) clusterassignment
- Parameters
-
clustering the matrix containing the clusterassignment qmatrix the returned matrix the transition probability between clusters cmatrix the transition-matrix containg the probability-data nbins the number of bins ncluster the number of possible clusters
Definition at line 191 of file heur_cyckerlin.c.
Referenced by createSwitchSolution().
◆ getObjective()
|
static |
calculate the current objective value for a q-matrix
- Parameters
-
scip SCIP data structure qmatrix the irreversibility matrix scale the scaling parameter in the objective function ncluster the number of cluster
Definition at line 226 of file heur_cyckerlin.c.
References SCIP_Real.
Referenced by createSwitchSolution(), and switchNext().
◆ switchNext()
|
static |
exchange another bin to a different cluster. No bin may be changed twice
- Parameters
-
scip SCIP data structure cmatrix the transition matrix qmatrix the irreversibility matrix clustering the clusterassignement binfixed array containing information about fixedbins binprocessed has the bin already been switched? clusterofbin contains the cluster each bin is in at the moment nbinsincluster number of bins in each cluster switchedbin the bins swithced in each iteration switchedcluster the cluster to witch the bin was assigned in each iteration switchbound the objective achieved in each iteration maxbound the best objective value so far bestlength the amount of switches with the best objective value so far iteration which iteration are we in
Definition at line 250 of file heur_cyckerlin.c.
References FALSE, getObjective(), isPartition(), SCIP_Real, SCIPcycGetNBins(), SCIPcycGetNCluster(), SCIPcycGetScale(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisZero(), setBinToCluster(), and TRUE.
Referenced by createSwitchSolution().
◆ createSwitchSolution()
|
static |
Create a solution in scip from the clustering
- Parameters
-
scip SCIP data structure heur heuristic pointer cmatrix the transition matrix qmatrix the projected transition matrix using the clustering binfixed matrix that tells which bin-variables cannot be changed startclustering the start-assignment result result pointer nbins the number of states ncluster the number of clusters
Definition at line 386 of file heur_cyckerlin.c.
References assignVars(), computeIrrevMat(), FALSE, getObjective(), isPartition(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateSol(), SCIPcycGetScale(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetSolOrigObj(), SCIPisFeasEQ(), SCIPtrySolFree(), switchNext(), and TRUE.
Referenced by runCyckerlin().
◆ permuteStartSolution()
|
static |
method that randomly creates a different solution from a given solution. From each cluster, half the states are randomly selected and added to the next cluster.
- Parameters
-
scip SCIP data structure startclustering the solution to be permuted rnd a random number generator nbins the number of states ncluster the number of clusters
Definition at line 562 of file heur_cyckerlin.c.
References phi(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPisPositive(), SCIPisZero(), and SCIPrandomGetInt().
Referenced by runCyckerlin().
◆ runCyckerlin()
|
static |
executes the exchange heuristic for a given solution
- Parameters
-
scip SCIP data structure heur heuristic pointer sol given solution result result pointer
Definition at line 634 of file heur_cyckerlin.c.
References createSwitchSolution(), DEFAULT_RANDSEED, getSolutionValues(), isPartition(), MAXPERMUTATIONS, permuteStartSolution(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateRandom(), SCIPcycGetCmatrix(), SCIPcycGetNBins(), SCIPcycGetNCluster(), SCIPfreeBufferArray, SCIPfreeRandom(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 724 of file heur_cyckerlin.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurCycKerlin().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 739 of file heur_cyckerlin.c.
References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeMemoryArray, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
◆ SCIP_DECL_HEUREXITSOL()
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 763 of file heur_cyckerlin.c.
References HEUR_NAME, HEUR_TIMING, NULL, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetTimingmask().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 786 of file heur_cyckerlin.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and SCIPheurGetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 809 of file heur_cyckerlin.c.
References HEUR_TIMING, NULL, runCyckerlin(), SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPgetNNodes(), SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPheurSetTimingmask(), and SCIPisZero().
◆ SCIPincludeHeurCycKerlin()
SCIP_RETCODE SCIPincludeHeurCycKerlin | ( | SCIP * | scip | ) |
creates the oneopt primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 848 of file heur_cyckerlin.c.
References HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), and SCIPsetHeurInit().
Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeCycPlugins().