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.

◆ 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

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

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

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

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 SCIP_Real getObjective	(	SCIP *	scip,
		SCIP_Real **	qmatrix,
		SCIP_Real	scale,
		int	ncluster
	)

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

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

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

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 SCIP_RETCODE runCyckerlin	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

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 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 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 739 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 763 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 786 of file heur_cyckerlin.c.

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

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecCyckerlin )

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

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ MAXPERMUTATIONS

◆ DEFAULT_RANDSEED

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

Function Documentation

◆ addCandSolCyckerlin()

◆ getSolutionValues()

◆ setBinToCluster()

◆ computeIrrevMat()

◆ getObjective()

◆ switchNext()

◆ createSwitchSolution()

◆ permuteStartSolution()

◆ runCyckerlin()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPincludeHeurCycKerlin()