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

◆ HEUR_DESC

#define HEUR_DESC "primal heuristic template"

Definition at line 42 of file heur_cycgreedy.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'h'

Definition at line 43 of file heur_cycgreedy.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 536870911

Definition at line 44 of file heur_cycgreedy.c.

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 45 of file heur_cycgreedy.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 46 of file heur_cycgreedy.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 47 of file heur_cycgreedy.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE

Definition at line 48 of file heur_cycgreedy.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 49 of file heur_cycgreedy.c.

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 60 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 84 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 122 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 164 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 197 of file heur_cycgreedy.c.

References FALSE, getObjective(), getTempObj(), scip::max(), 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 374 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 388 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 409 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 422 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 441 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 607 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()