SCIP Doxygen Documentation
Loading...
Searching...
No Matches
heur_cyckerlin.c File Reference

Detailed Description

improvement heuristic that exchanges binary variables between clusters. Similar to the famous kernighan/lin heuristic for graph partitioning

Author
Leon Eifler

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.

◆ 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.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   '@'

Definition at line 43 of file heur_cyckerlin.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   500

Definition at line 44 of file heur_cyckerlin.c.

◆ HEUR_FREQ

#define HEUR_FREQ   10

Definition at line 45 of file heur_cyckerlin.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 46 of file heur_cyckerlin.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 47 of file heur_cyckerlin.c.

◆ MAXPERMUTATIONS

#define MAXPERMUTATIONS   5

Definition at line 48 of file heur_cyckerlin.c.

Referenced by runCyckerlin().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   177

random seed

Definition at line 49 of file heur_cyckerlin.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 50 of file heur_cyckerlin.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 51 of file heur_cyckerlin.c.

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
scipSCIP data structure
solthe 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().

◆ getSolutionValues()

SCIP_RETCODE getSolutionValues ( SCIP * scip,
SCIP_SOL * bestsol,
SCIP_Real ** solclustering,
SCIP_Bool ** binfixed,
int * clusterofbin,
int * nbinsincluster )
static

get the bin-var assignment from scip and save it as a matrix

Parameters
scipSCIP data structure
bestsolthe solution
solclusteringmatrix to save the bin-vars
binfixedmatrix to save if a bin is fixed in scip
clusterofbinarray containing the cluster of each bin
nbinsinclusternumber 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().

◆ setBinToCluster()

void setBinToCluster ( SCIP_Real ** solclustering,
SCIP_Real ** cmatrix,
SCIP_Real ** qmatrix,
int newbin,
int newcluster,
SCIP_Bool setone,
int nbins,
int ncluster )
static

Set a bin to a new cluster, update the qmatrix.

Parameters
solclusteringthe matrix with the clustering of the bins
cmatrixthe transition matrix
qmatrixthe matrix containing the transition probabilities between clusters
newbinthe bin to be changed
newclusterthe cluster where the bin is changed
setoneTRUE if the assignment is switched from 0 to 1, FALSE if 1 to 0
nbinsthe number of bins
nclusterthe number of clusters

Definition at line 151 of file heur_cyckerlin.c.

References SCIP_Bool, and SCIP_Real.

Referenced by switchNext().

◆ computeIrrevMat()

void computeIrrevMat ( SCIP_Real ** clustering,
SCIP_Real ** qmatrix,
SCIP_Real ** cmatrix,
int nbins,
int ncluster )
static

initialize the q-matrix from a given (possibly incomplete) clusterassignment

Parameters
clusteringthe matrix containing the clusterassignment
qmatrixthe returned matrix the transition probability between clusters
cmatrixthe transition-matrix containg the probability-data
nbinsthe number of bins
nclusterthe number of possible clusters

Definition at line 191 of file heur_cyckerlin.c.

References i, and SCIP_Real.

Referenced by createSwitchSolution().

◆ getObjective()

SCIP_Real getObjective ( SCIP * scip,
SCIP_Real ** qmatrix,
SCIP_Real scale,
int ncluster )
static

calculate the current objective value for a q-matrix

Parameters
scipSCIP data structure
qmatrixthe irreversibility matrix
scalethe scaling parameter in the objective function
nclusterthe number of cluster

Definition at line 226 of file heur_cyckerlin.c.

References c, and SCIP_Real.

Referenced by createSwitchSolution(), and switchNext().

◆ switchNext()

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

exchange another bin to a different cluster. No bin may be changed twice

Parameters
scipSCIP data structure
cmatrixthe transition matrix
qmatrixthe irreversibility matrix
clusteringthe clusterassignement
binfixedarray containing information about fixedbins
binprocessedhas the bin already been switched?
clusterofbincontains the cluster each bin is in at the moment
nbinsinclusternumber of bins in each cluster
switchedbinthe bins swithced in each iteration
switchedclusterthe cluster to witch the bin was assigned in each iteration
switchboundthe objective achieved in each iteration
maxboundthe best objective value so far
bestlengththe amount of switches with the best objective value so far
iterationwhich 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().

◆ createSwitchSolution()

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

Create a solution in scip from the clustering

Parameters
scipSCIP data structure
heurheuristic pointer
cmatrixthe transition matrix
qmatrixthe projected transition matrix using the clustering
binfixedmatrix that tells which bin-variables cannot be changed
startclusteringthe start-assignment
resultresult pointer
nbinsthe number of states
nclusterthe 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().

◆ permuteStartSolution()

SCIP_RETCODE permuteStartSolution ( SCIP * scip,
SCIP_Real ** startclustering,
SCIP_RANDNUMGEN * rnd,
int nbins,
int ncluster )
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
scipSCIP data structure
startclusteringthe solution to be permuted
rnda random number generator
nbinsthe number of states
nclusterthe 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().

◆ runCyckerlin()

SCIP_RETCODE runCyckerlin ( SCIP * scip,
SCIP_HEUR * heur,
SCIP_SOL * sol,
SCIP_RESULT * result )
static

executes the exchange heuristic for a given solution

Parameters
scipSCIP data structure
heurheuristic pointer
solgiven solution
resultresult 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().

◆ SCIP_DECL_HEURCOPY()

SCIP_DECL_HEURCOPY ( heurCopyCyckerlin )
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().

◆ SCIP_DECL_HEURFREE()

SCIP_DECL_HEURFREE ( heurFreeCyckerlin )
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().

◆ SCIP_DECL_HEUREXITSOL()

SCIP_DECL_HEUREXITSOL ( heurExitsolCyckerlin )
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().

◆ SCIP_DECL_HEURINIT()

SCIP_DECL_HEURINIT ( heurInitCyckerlin )
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().

◆ SCIP_DECL_HEUREXEC()

SCIP_DECL_HEUREXEC ( heurExecCyckerlin )
static

◆ SCIPincludeHeurCycKerlin()

SCIP_RETCODE SCIPincludeHeurCycKerlin ( SCIP * scip)