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) |
#define HEUR_NAME "cyckerlin" |
Definition at line 41 of file heur_cyckerlin.c.
#define HEUR_DESC "switch heuristic that tries to improve solution by trading states betweeen clusters" |
Definition at line 42 of file heur_cyckerlin.c.
#define HEUR_DISPCHAR '@' |
Definition at line 43 of file heur_cyckerlin.c.
#define HEUR_PRIORITY 500 |
Definition at line 44 of file heur_cyckerlin.c.
#define HEUR_FREQ 10 |
Definition at line 45 of file heur_cyckerlin.c.
#define HEUR_FREQOFS 0 |
Definition at line 46 of file heur_cyckerlin.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 47 of file heur_cyckerlin.c.
#define MAXPERMUTATIONS 5 |
Definition at line 48 of file heur_cyckerlin.c.
Referenced by runCyckerlin().
#define DEFAULT_RANDSEED 177 |
random seed
Definition at line 49 of file heur_cyckerlin.c.
#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE |
Definition at line 50 of file heur_cyckerlin.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 51 of file heur_cyckerlin.c.
SCIP_RETCODE addCandSolCyckerlin | ( | SCIP * | scip, |
SCIP_SOL * | sol ) |
external method that adds a solution to the list of candidate-solutions that should be improved
scip | SCIP data structure |
sol | the given solution |
Definition at line 65 of file heur_cyckerlin.c.
References assert(), heurdata, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPfindHeur(), SCIPheurGetData(), SCIPreallocMemoryArray, and sol.
Referenced by SCIP_DECL_EVENTEXEC().
|
static |
get the bin-var assignment from scip and save it as a matrix
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 assert(), c, FALSE, i, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPcycGetBinvars(), SCIPcycGetNBins(), SCIPcycGetNCluster(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by runCyckerlin().
|
static |
Set a bin to a new cluster, update the qmatrix.
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_Bool, and SCIP_Real.
Referenced by switchNext().
|
static |
initialize the q-matrix from a given (possibly incomplete) clusterassignment
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().
calculate the current objective value for a q-matrix
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.
Referenced by createSwitchSolution(), and switchNext().
|
static |
exchange another bin to a different cluster. No bin may be changed twice
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 assert(), FALSE, getObjective(), i, isPartition(), SCIP_Bool, SCIP_Real, SCIPcycGetNBins(), SCIPcycGetNCluster(), SCIPcycGetScale(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisZero(), setBinToCluster(), and TRUE.
Referenced by createSwitchSolution().
|
static |
Create a solution in scip from the clustering
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 assert(), assignVars(), c, computeIrrevMat(), FALSE, getObjective(), i, isPartition(), result, 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().
|
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.
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 c, i, phi(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPisPositive(), SCIPisZero(), and SCIPrandomGetInt().
Referenced by runCyckerlin().
|
static |
executes the exchange heuristic for a given solution
scip | SCIP data structure |
heur | heuristic pointer |
sol | given solution |
result | result pointer |
Definition at line 634 of file heur_cyckerlin.c.
References assert(), c, createSwitchSolution(), DEFAULT_RANDSEED, getSolutionValues(), i, isPartition(), MAXPERMUTATIONS, permuteStartSolution(), result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateRandom(), SCIPcycGetCmatrix(), SCIPcycGetNBins(), SCIPcycGetNCluster(), SCIPfreeBufferArray, SCIPfreeRandom(), sol, and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 724 of file heur_cyckerlin.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurCycKerlin().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 739 of file heur_cyckerlin.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeMemoryArray, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
|
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 assert(), HEUR_NAME, HEUR_TIMING, heurdata, NULL, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetTimingmask().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 786 of file heur_cyckerlin.c.
References assert(), heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and SCIPheurGetData().
|
static |
execution method of primal heuristic
Definition at line 809 of file heur_cyckerlin.c.
References assert(), HEUR_TIMING, heurdata, i, NULL, result, runCyckerlin(), SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPgetNNodes(), SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPheurSetTimingmask(), and SCIPisZero().
SCIP_RETCODE SCIPincludeHeurCycKerlin | ( | SCIP * | scip | ) |
creates the oneopt primal heuristic and includes it in SCIP
scip | SCIP data structure |
Definition at line 848 of file heur_cyckerlin.c.
References assert(), HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), and SCIPsetHeurInit().
Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeCycPlugins().