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) |
#define HEUR_NAME "cycgreedy" |
Definition at line 41 of file heur_cycgreedy.c.
#define HEUR_DESC "primal heuristic template" |
Definition at line 42 of file heur_cycgreedy.c.
#define HEUR_DISPCHAR 'h' |
Definition at line 43 of file heur_cycgreedy.c.
#define HEUR_PRIORITY 536870911 |
Definition at line 44 of file heur_cycgreedy.c.
#define HEUR_FREQ 1 |
Definition at line 45 of file heur_cycgreedy.c.
#define HEUR_FREQOFS 0 |
Definition at line 46 of file heur_cycgreedy.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 47 of file heur_cycgreedy.c.
#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE |
Definition at line 48 of file heur_cycgreedy.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 49 of file heur_cycgreedy.c.
|
static |
calculate the current objective value for a q-matrix
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.
Referenced by assignNextBin(), getTempObj(), and SCIP_DECL_HEUREXEC().
|
static |
initialize the q-matrix from a given (possibly incomplete) clusterassignment
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().
|
static |
update the irreversibility matrix, after the clusterassignment[newcluster][newbin] was either set from 0 to 1 or from 1 to 0
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.
References SCIP_Real.
Referenced by assignNextBin().
|
static |
get the temporary objective value bound after newbin would be added to newcluster but dont not change anything with the clustering
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(), i, obj, phi(), phiinv(), SCIP_Real, and SCIPcycGetScale().
Referenced by assignNextBin().
|
static |
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 assert(), c, FALSE, getObjective(), getTempObj(), i, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocClearBufferArray, SCIPcycGetScale(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisGT(), SCIPisLT(), TRUE, and updateIrrevMat().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 374 of file heur_cycgreedy.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurCycGreedy().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 388 of file heur_cycgreedy.c.
References assert(), HEUR_NAME, heurdata, NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
|
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 assert(), HEUR_NAME, HEUR_TIMING, NULL, SCIP_OKAY, SCIPheurGetName(), and SCIPheurSetTimingmask().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 422 of file heur_cycgreedy.c.
References assert(), heurdata, NULL, SCIP_OKAY, and SCIPheurGetData().
|
static |
execution method of primal heuristic
Definition at line 441 of file heur_cycgreedy.c.
References assert(), assignNextBin(), assignVars(), c, computeIrrevMat(), FALSE, getObjective(), heurdata, i, isPartition(), NULL, obj, result, 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(), sol, and TRUE.
SCIP_RETCODE SCIPincludeHeurCycGreedy | ( | SCIP * | scip | ) |
creates the CycGreedy - primal heuristic and includes it in SCIP
scip | SCIP data structure |
Definition at line 607 of file heur_cycgreedy.c.
References assert(), FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), and TRUE.
Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeCycPlugins().