Scippy

SCIP

Solving Constraint Integer Programs

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"

◆ HEUR_DESC

#define HEUR_DESC   "switch heuristic that tries to improve solution by trading states betweeen clusters"

Definition at line 33 of file heur_cyckerlin.c.

Referenced by SCIPincludeHeurCycKerlin().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   '@'

Definition at line 34 of file heur_cyckerlin.c.

Referenced by SCIPincludeHeurCycKerlin().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   500

Definition at line 35 of file heur_cyckerlin.c.

Referenced by SCIPincludeHeurCycKerlin().

◆ HEUR_FREQ

#define HEUR_FREQ   10

Definition at line 36 of file heur_cyckerlin.c.

Referenced by SCIPincludeHeurCycKerlin().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 37 of file heur_cyckerlin.c.

Referenced by SCIPincludeHeurCycKerlin().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 38 of file heur_cyckerlin.c.

Referenced by SCIPincludeHeurCycKerlin().

◆ MAXPERMUTATIONS

#define MAXPERMUTATIONS   5

Definition at line 39 of file heur_cyckerlin.c.

Referenced by runCyckerlin().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   177

random seed

Definition at line 40 of file heur_cyckerlin.c.

Referenced by runCyckerlin().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 42 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
scipSCIP data structure
solthe given solution

Definition at line 56 of file heur_cyckerlin.c.

References NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPfindHeur(), SCIPheurGetData(), and SCIPreallocMemoryArray.

Referenced by SCIP_DECL_EVENTEXEC().

◆ getSolutionValues()

static 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 90 of file heur_cyckerlin.c.

References FALSE, NULL, SCIP_OKAY, SCIPcycGetBinvars(), SCIPcycGetNBins(), SCIPcycGetNCluster(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by runCyckerlin().

◆ setBinToCluster()

static 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 142 of file heur_cyckerlin.c.

References SCIP_Real, and sign().

Referenced by switchNext().

◆ computeIrrevMat()

static 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 182 of file heur_cyckerlin.c.

Referenced by createSwitchSolution().

◆ getObjective()

static 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 217 of file heur_cyckerlin.c.

References SCIP_Real.

Referenced by createSwitchSolution(), and switchNext().

◆ switchNext()

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

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 241 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 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 377 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 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 553 of file heur_cyckerlin.c.

References phi(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPisPositive(), SCIPisZero(), and SCIPrandomGetInt().

Referenced by runCyckerlin().

◆ runCyckerlin()

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

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 715 of file heur_cyckerlin.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurCycKerlin().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeCyckerlin  )
static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 730 of file heur_cyckerlin.c.

References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeMemoryArray, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolCyckerlin  )
static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 754 of file heur_cyckerlin.c.

References HEUR_NAME, HEUR_TIMING, NULL, SCIP_OKAY, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetTimingmask().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitCyckerlin  )
static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 777 of file heur_cyckerlin.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecCyckerlin  )
static

◆ SCIPincludeHeurCycKerlin()

SCIP_RETCODE SCIPincludeHeurCycKerlin ( SCIP scip)