Scippy

SCIP

Solving Constraint Integer Programs

heur_cycgreedy.c File Reference

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"

◆ 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
scipSCIP data structure
qmatrixthe irreversibility matrix
scalethe scaling parameter in the objective function
nclusterthe 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
clusterassignmentthe matrix containing the (incomplete) clusterassignment
qmatrixthe returned matrix with the irreversibility between two clusters
cmatrixthe transition-matrix containg the probability-data
nbinsthe number of bins
nclusterthe 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
clusterassignmentthe matrix containing the (incomplete) clusterassignment
qmatrixthe returned matrix with the irreversibility between two clusters
cmatrixthe transition-matrix containg the probability-data
newbinthe bin to be added to the assignment
newclusterthe bluster in which the bin was changed
nbinsthe number of bins
nclusterthe 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
scipSCIP data structure
qmatrixthe irreversibility matrix
cmatrixthe transition matrix
clusterassignmentthe clusterassignment
newbinthe bin that would be added to cluster
newclusterthe cluster the bin would be added to
nbinsthe number of bins
nclusterthe 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
scipSCIP data structure
localheurshould the heuristic only compute local optimal assignment
clusterassignmentthe matrix with the Clusterassignment
cmatrixthe transition matrix
qmatrixthe irreversibility matrix
isassignedTRUE, if the bin i was already assigned to a cluster
nbinsthe number of bins
nclusterthe number of cluster
amountassignedthe total amount of bins already assigned
binsinclusterthe number of bins currently in a cluster
objectivethe 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()

◆ SCIPincludeHeurCycGreedy()

SCIP_RETCODE SCIPincludeHeurCycGreedy ( SCIP scip)