Detailed Description

Greedy primal heuristic. States are assigned to clusters iteratively. At each iteration all possible assignments are computed and the one with the best change in objective value is selected.

Author: Leon Eifler

Definition in file heur_cycgreedy.c.

#include "heur_cycgreedy.h"
#include <assert.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include "scip/misc.h"
#include "probdata_cyc.h"
#include "scip/cons_and.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME "cycgreedy"

#define	HEUR_DESC "primal heuristic template"

#define	HEUR_DISPCHAR 'h'

#define	HEUR_PRIORITY 536870911

#define	HEUR_FREQ 1

#define	HEUR_FREQOFS 0

#define	HEUR_MAXDEPTH -1

#define	HEUR_TIMING SCIP_HEURTIMING_BEFORENODE

#define	HEUR_USESSUBSCIP FALSE

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

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

static void	updateIrrevMat (SCIP_Real clusterassignment, SCIP_Real qmatrix, SCIP_Real **cmatrix, int newbin, int newcluster, int nbins, int ncluster)

static SCIP_Real	getTempObj (SCIP scip, SCIP_Real qmatrix, SCIP_Real cmatrix, SCIP_Real *clusterassignment, int newbin, int newcluster, int nbins, int ncluster)

static SCIP_RETCODE	assignNextBin (SCIP scip, SCIP_Bool localheur, SCIP_Real clusterassignment, SCIP_Real cmatrix, SCIP_Real qmatrix, SCIP_Bool isassigned, int nbins, int ncluster, int amountassigned, int binsincluster, SCIP_Real *objective)

static	SCIP_DECL_HEURCOPY (heurCopyCycGreedy)

static	SCIP_DECL_HEURFREE (heurFreeCycGreedy)

static	SCIP_DECL_HEUREXITSOL (heurExitsolCycGreedy)

static	SCIP_DECL_HEURINIT (heurInitCycGreedy)

static	SCIP_DECL_HEUREXEC (heurExecCycGreedy)

SCIP_RETCODE	SCIPincludeHeurCycGreedy (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "cycgreedy"

Definition at line 32 of file heur_cycgreedy.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXITSOL(), SCIP_DECL_HEURFREE(), and SCIPincludeHeurCycGreedy().

◆ HEUR_DESC

#define HEUR_DESC "primal heuristic template"

Definition at line 33 of file heur_cycgreedy.c.

Referenced by SCIPincludeHeurCycGreedy().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'h'

Definition at line 34 of file heur_cycgreedy.c.

Referenced by SCIPincludeHeurCycGreedy().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 536870911

Definition at line 35 of file heur_cycgreedy.c.

Referenced by SCIPincludeHeurCycGreedy().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 36 of file heur_cycgreedy.c.

Referenced by SCIPincludeHeurCycGreedy().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 37 of file heur_cycgreedy.c.

Referenced by SCIPincludeHeurCycGreedy().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 38 of file heur_cycgreedy.c.

Referenced by SCIPincludeHeurCycGreedy().

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE

Definition at line 39 of file heur_cycgreedy.c.

Referenced by SCIP_DECL_HEUREXITSOL(), and SCIPincludeHeurCycGreedy().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 40 of file heur_cycgreedy.c.

Referenced by SCIPincludeHeurCycGreedy().

Function Documentation

◆ 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 51 of file heur_cycgreedy.c.

References SCIP_Real.

Referenced by assignNextBin(), getTempObj(), and SCIP_DECL_HEUREXEC().

◆ computeIrrevMat()

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

static

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

Parameters

clusterassignment	the matrix containing the (incomplete) clusterassignment
qmatrix	the returned matrix with the irreversibility between two clusters
cmatrix	the transition-matrix containg the probability-data
nbins	the number of bins
ncluster	the number of possible clusters

Definition at line 75 of file heur_cycgreedy.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ updateIrrevMat()

static void updateIrrevMat	(	SCIP_Real **	clusterassignment,
		SCIP_Real **	qmatrix,
		SCIP_Real **	cmatrix,
		int	newbin,
		int	newcluster,
		int	nbins,
		int	ncluster
	)

static

update the irreversibility matrix, after the clusterassignment[newcluster][newbin] was either set from 0 to 1 or from 1 to 0

Parameters

clusterassignment	the matrix containing the (incomplete) clusterassignment
qmatrix	the returned matrix with the irreversibility between two clusters
cmatrix	the transition-matrix containg the probability-data
newbin	the bin to be added to the assignment
newcluster	the bluster in which the bin was changed
nbins	the number of bins
ncluster	the number of clusters

Definition at line 113 of file heur_cycgreedy.c.

Referenced by assignNextBin().

◆ getTempObj()

static SCIP_Real getTempObj	(	SCIP *	scip,
		SCIP_Real **	qmatrix,
		SCIP_Real **	cmatrix,
		SCIP_Real **	clusterassignment,
		int	newbin,
		int	newcluster,
		int	nbins,
		int	ncluster
	)

static

get the temporary objective value bound after newbin would be added to newcluster but dont not change anything with the clustering

Parameters

scip	SCIP data structure
qmatrix	the irreversibility matrix
cmatrix	the transition matrix
clusterassignment	the clusterassignment
newbin	the bin that would be added to cluster
newcluster	the cluster the bin would be added to
nbins	the number of bins
ncluster	the number of cluster

Definition at line 155 of file heur_cycgreedy.c.

References getObjective(), phi(), phiinv(), SCIP_Real, and SCIPcycGetScale().

Referenced by assignNextBin().

◆ assignNextBin()

static SCIP_RETCODE assignNextBin	(	SCIP *	scip,
		SCIP_Bool	localheur,
		SCIP_Real **	clusterassignment,
		SCIP_Real **	cmatrix,
		SCIP_Real **	qmatrix,
		SCIP_Bool *	isassigned,
		int	nbins,
		int	ncluster,
		int *	amountassigned,
		int *	binsincluster,
		SCIP_Real *	objective
	)

static

Parameters

scip	SCIP data structure
localheur	should the heuristic only compute local optimal assignment
clusterassignment	the matrix with the Clusterassignment
cmatrix	the transition matrix
qmatrix	the irreversibility matrix
isassigned	TRUE, if the bin i was already assigned to a cluster
nbins	the number of bins
ncluster	the number of cluster
amountassigned	the total amount of bins already assigned
binsincluster	the number of bins currently in a cluster
objective	the objective

Definition at line 188 of file heur_cycgreedy.c.

References FALSE, getObjective(), getTempObj(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocClearBufferArray, SCIPcycGetScale(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisGT(), SCIPisLT(), TRUE, and updateIrrevMat().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyCycGreedy )

static

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

Definition at line 365 of file heur_cycgreedy.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeCycGreedy )

static

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

Definition at line 379 of file heur_cycgreedy.c.

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

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolCycGreedy )

static

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

Definition at line 400 of file heur_cycgreedy.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitCycGreedy )

static

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

Definition at line 413 of file heur_cycgreedy.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecCycGreedy )

static

execution method of primal heuristic

Definition at line 432 of file heur_cycgreedy.c.

References assignNextBin(), assignVars(), computeIrrevMat(), FALSE, getObjective(), isPartition(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocClearBufferArray, SCIPcreateSol(), SCIPcycGetBinvars(), SCIPcycGetCmatrix(), SCIPcycGetNBins(), SCIPcycGetNCluster(), SCIPcycGetScale(), SCIPfreeBufferArray, SCIPgetEffectiveRootDepth(), SCIPheurGetData(), SCIPisEQ(), SCIPtrySolFree(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

◆ SCIPincludeHeurCycGreedy()

SCIP_RETCODE SCIPincludeHeurCycGreedy ( SCIP * scip )

creates the CycGreedy - primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 598 of file heur_cycgreedy.c.

References FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), and TRUE.

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

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

Function Documentation

◆ getObjective()

◆ computeIrrevMat()

◆ updateIrrevMat()

◆ getTempObj()

◆ assignNextBin()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPincludeHeurCycGreedy()