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.
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.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXITSOL(), SCIP_DECL_HEURFREE(), and SCIPincludeHeurCycGreedy().
◆ HEUR_DESC
#define HEUR_DESC "primal heuristic template" |
Definition at line 42 of file heur_cycgreedy.c.
Referenced by SCIPincludeHeurCycGreedy().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR 'h' |
Definition at line 43 of file heur_cycgreedy.c.
Referenced by SCIPincludeHeurCycGreedy().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY 536870911 |
Definition at line 44 of file heur_cycgreedy.c.
Referenced by SCIPincludeHeurCycGreedy().
◆ HEUR_FREQ
#define HEUR_FREQ 1 |
Definition at line 45 of file heur_cycgreedy.c.
Referenced by SCIPincludeHeurCycGreedy().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 46 of file heur_cycgreedy.c.
Referenced by SCIPincludeHeurCycGreedy().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 47 of file heur_cycgreedy.c.
Referenced by SCIPincludeHeurCycGreedy().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE |
Definition at line 48 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 49 of file heur_cycgreedy.c.
Referenced by SCIPincludeHeurCycGreedy().
Function Documentation
◆ getObjective()
|
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 |
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 |
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 |
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 |
- 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_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 |
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 |
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 |
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 |
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 |
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().