heur_dks.c File Reference

Detailed Description

dks primal heuristic

Author

Adrian Göß

Dieter Weninger

Primal heuristic based on ideas published in the paper "Exploiting user-supplied Decompositions inside Heuristics" by Katrin Halbig, Adrian Göß and Dieter Weninger.

Definition in file heur_dks.c.

#include "scip/pub_lp.h"
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/debug.h"
#include "scip/heuristics.h"
#include "scip/pub_cons.h"
#include "scip/pub_event.h"
#include "scip/pub_fileio.h"
#include "scip/pub_tree.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_select.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scipdefplugins.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_dcmp.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_table.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/sol.h"
#include "scip/heur_dks.h"

Go to the source code of this file.

Data Structures
struct	Bucket
struct	Bucketlist

Macros
#define	HEUR_NAME   "dks"
#define	HEUR_DESC   "decomposition kernel search"
#define	HEUR_DISPCHAR   'D'
#define	HEUR_PRIORITY   -1102500
#define	HEUR_FREQ   -1
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   0
#define	HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE
#define	HEUR_USESSUBSCIP   TRUE
#define	DEFAULT_MAXBUCKS   20
#define	DEFAULT_KERNELSIZEFACTOR   2.0
#define	DEFAULT_ADDUSECONSS   TRUE
#define	DEFAULT_LINKBUCKSIZE   TRUE
#define	DEFAULT_TRANSLBKERNEL   TRUE
#define	DEFAULT_LESSLOCKSKERNEL   FALSE
#define	DEFAULT_USETRANSPROB   TRUE
#define	DEFAULT_BUCKMAXGAP   0.01
#define	DEFAULT_MAXLINKSCORE   1.0
#define	DEFAULT_MAXBUCKFRAC   0.10
#define	DEFAULT_MAXNODES   5000LL
#define	DEFAULT_USETWOLEVEL   TRUE
#define	DEFAULT_USEDECOMP   TRUE
#define	DEFAULT_USEBESTSOL   TRUE
#define	DEFAULT_REDCOSTSORT   TRUE
#define	DEFAULT_PRIMALONLY   FALSE
#define	DEFAULT_REDCOSTLOGSORT   TRUE
#define	DEFAULT_OBJCUTOFF   TRUE
#define	DEFAULT_RUNBINPROBSONLY   FALSE

Typedefs
typedef struct Bucketlist	BUCKETLIST
typedef struct Bucket	BUCKET

Functions
static SCIP_RETCODE	getLinkingScoreAndBlocklabels (int *blocklabels, int *varlabels, int *conslabels, SCIP_Real *linkscore, int *nblocklabels, int nblocks, int nvars, int nconss)
static SCIP_RETCODE	countKernelVariables (SCIP *scip, SCIP_VAR **vars, SCIP_SOL *bestcurrsol, SCIP_HASHMAP *lbvarmap, SCIP_Bool twolevel, SCIP_Bool usebestsol, SCIP_Bool usetransprob, SCIP_Bool usetranslb, int *bw_ncontkernelvars, int *bw_ncontnonkernelvars, int *bw_nkernelvars, int *bw_nnonkernelvars, int *bw_nintkernelvars, int *bw_nintnonkernelvars, int *ncontkernelvars, int *ncontnonkernelvars, int *nkernelvars, int *nnonkernelvars, int *nintkernelvars, int *nintnonkernelvars, int *block2index, int *varlabels, int blklbl_offset, int nvars)
static SCIP_RETCODE	fillKernels (SCIP *scip, SCIP_VAR **vars, SCIP_VAR **binintvars, SCIP_VAR ***bw_contkernelvars, SCIP_VAR ***bw_contnonkernelvars, SCIP_VAR ***bw_kernelvars, SCIP_VAR ***bw_nonkernelvars, SCIP_VAR ***bw_intkernelvars, SCIP_VAR ***bw_intnonkernelvars, SCIP_SOL *bestcurrsol, SCIP_HASHMAP *lbvarmap, SCIP_Bool twolevel, SCIP_Bool usebestsol, SCIP_Bool usetransprob, SCIP_Bool usetranslb, int *bw_contkernelcount, int *bw_contnonkernelcount, int *bw_kernelcount, int *bw_nonkernelcount, int *bw_intkernelcount, int *bw_intnonkernelcount, int *bw_ncontkernelvars, int *bw_ncontnonkernelvars, int *bw_nkernelvars, int *bw_nnonkernelvars, int *bw_nintkernelvars, int *bw_nintnonkernelvars, int *block2index, int *varlabels, int blklbl_offset, int nvars)
static SCIP_RETCODE	reducedCostSort (SCIP *scip, SCIP_VAR ***bw_contnonkernelvars, SCIP_VAR ***bw_nonkernelvars, SCIP_VAR ***bw_intnonkernelvars, SCIP_Real ***bw_cont_redcost, SCIP_Real ***bw_redcost, SCIP_Real ***bw_int_redcost, int *bw_ncontnonkernelvars, int *bw_nnonkernelvars, int *bw_nintnonkernelvars, SCIP_Bool twolevel, int nblocks)
static SCIP_RETCODE	freeRedcostArrays (SCIP *scip, SCIP_Real ***bw_cont_redcost, SCIP_Real ***bw_redcost, SCIP_Real ***bw_int_redcost, int nblocks)
static SCIP_Bool	isInCurrentLogBucket (SCIP *scip, SCIP_Real base, SCIP_Real redcost, SCIP_Real redcostmin, int currentindex, int nbuckets)
static SCIP_RETCODE	fillBuckets (SCIP *scip, BUCKETLIST **bucketlist, SCIP_VAR ***bw_contnonkernelvars, SCIP_VAR ***bw_nonkernelvars, SCIP_VAR ***bw_intnonkernelvars, int *bw_ncontnonkernelvars, int *bw_nnonkernelvars, int *bw_nintnonkernelvars, SCIP_Real **bw_cont_redcost, SCIP_Real **bw_redcost, SCIP_Real **bw_int_redcost, SCIP_Bool twolevel, SCIP_Bool redcostlogsort, int nbuckets, int nblocks)
static SCIP_RETCODE	freeBucketArrays (SCIP *scip, BUCKET *bucket, SCIP_Bool twolevel)
static SCIP_RETCODE	initBucket (BUCKETLIST *bucketlist)
static SCIP_RETCODE	freeBucket (SCIP *scip, BUCKET *bucket)
static SCIP_RETCODE	initBucketlist (SCIP *scip, BUCKETLIST **bucketlist, int nbuckets)
static SCIP_RETCODE	freeBucketlist (BUCKETLIST **bucketlist, int nbuckets)
static SCIP_RETCODE	bucketCreateSubscip (BUCKET *bucket, SCIP_Bool usetransprob, SCIP_Bool *success)
static SCIP_RETCODE	createBucketlistAndBuckets (SCIP *scip, SCIP_Bool usetransprob, int nbuckets, BUCKETLIST **bucketlist, SCIP_Bool *success)
static SCIP_RETCODE	searchKernelAndBucket (BUCKET *bucket, SCIP_VAR **contkernelvars, int ncontkernelvars, SCIP_VAR **kernelvars, int nkernelvars, SCIP_VAR **intkernelvars, int nintkernelvars, SCIP_VAR *var, SCIP_Bool *found)
static SCIP_RETCODE	adjustKernelVars (SCIP *scip, BUCKET *bucket, SCIP_VAR ***contkernelvars, int *ncontkernelvars, int maxcontkernelsize, SCIP_VAR ***kernelvars, int *nkernelvars, int maxkernelsize, SCIP_VAR ***intkernelvars, int *nintkernelvars, int maxintkernelsize, SCIP_Bool twolevel)
static SCIP_RETCODE	addUseConstraint (BUCKET *bucket)
static	SCIP_DECL_HEURCOPY (heurCopyDKS)
static	SCIP_DECL_HEURFREE (heurFreeDKS)
static	SCIP_DECL_HEUREXEC (heurExecDKS)
SCIP_RETCODE	SCIPincludeHeurDKS (SCIP *scip)

Macro Definition Documentation

HEUR_NAME

#define HEUR_NAME   "dks"

Definition at line 79 of file heur_dks.c.

HEUR_DESC

#define HEUR_DESC   "decomposition kernel search"

Definition at line 80 of file heur_dks.c.

HEUR_DISPCHAR

#define HEUR_DISPCHAR   'D'

Definition at line 81 of file heur_dks.c.

HEUR_PRIORITY

#define HEUR_PRIORITY   -1102500

Definition at line 82 of file heur_dks.c.

HEUR_FREQ

#define HEUR_FREQ   -1

Definition at line 83 of file heur_dks.c.

HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 84 of file heur_dks.c.

HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   0

Definition at line 85 of file heur_dks.c.

HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE

Definition at line 86 of file heur_dks.c.

HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 87 of file heur_dks.c.

DEFAULT_MAXBUCKS

#define DEFAULT_MAXBUCKS   20

default value for the number of buckets to investigate

Definition at line 89 of file heur_dks.c.

DEFAULT_KERNELSIZEFACTOR

#define DEFAULT_KERNELSIZEFACTOR   2.0

default value for the maximal growing of the kernel size

Definition at line 90 of file heur_dks.c.

DEFAULT_ADDUSECONSS

#define DEFAULT_ADDUSECONSS   TRUE

default value to add a use constraint

Definition at line 91 of file heur_dks.c.

DEFAULT_LINKBUCKSIZE

#define DEFAULT_LINKBUCKSIZE   TRUE

default value to respect kernel linking vars for the bucket size

Definition at line 92 of file heur_dks.c.

DEFAULT_TRANSLBKERNEL

#define DEFAULT_TRANSLBKERNEL   TRUE

default value to respect the diff of var lb in trans and orig prob

Definition at line 93 of file heur_dks.c.

DEFAULT_LESSLOCKSKERNEL

#define DEFAULT_LESSLOCKSKERNEL   FALSE

default value to respect <= 1 up- & downlock in kernel construction

Definition at line 94 of file heur_dks.c.

DEFAULT_USETRANSPROB

#define DEFAULT_USETRANSPROB   TRUE

default value to use the original or transformed problem

Definition at line 95 of file heur_dks.c.

DEFAULT_BUCKMAXGAP

#define DEFAULT_BUCKMAXGAP   0.01

default value for the maximal mip gap of a bucket

Definition at line 96 of file heur_dks.c.

DEFAULT_MAXLINKSCORE

#define DEFAULT_MAXLINKSCORE   1.0

default value for the maximal linking score of an instance

Definition at line 97 of file heur_dks.c.

DEFAULT_MAXBUCKFRAC

#define DEFAULT_MAXBUCKFRAC   0.10

default value to respect buckets with <= this share of bin/int vars

Definition at line 98 of file heur_dks.c.

DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   5000LL

default node limit of the heuristic

Definition at line 99 of file heur_dks.c.

DEFAULT_USETWOLEVEL

#define DEFAULT_USETWOLEVEL   TRUE

default value to use a two level structure for the buckets

Definition at line 100 of file heur_dks.c.

DEFAULT_USEDECOMP

#define DEFAULT_USEDECOMP   TRUE

default value to use the decomp if given

Definition at line 101 of file heur_dks.c.

DEFAULT_USEBESTSOL

#define DEFAULT_USEBESTSOL   TRUE

default value to use the best existing solution or the lp solution

Definition at line 102 of file heur_dks.c.

DEFAULT_REDCOSTSORT

#define DEFAULT_REDCOSTSORT   TRUE

default value to sort the non kernel vars before bucket split

Definition at line 103 of file heur_dks.c.

DEFAULT_PRIMALONLY

#define DEFAULT_PRIMALONLY   FALSE

default value to kill dks after the first primal solution is found

Definition at line 104 of file heur_dks.c.

DEFAULT_REDCOSTLOGSORT

#define DEFAULT_REDCOSTLOGSORT   TRUE

default value to sort non kernel vars logarithmically by redcost

Definition at line 105 of file heur_dks.c.

DEFAULT_OBJCUTOFF

#define DEFAULT_OBJCUTOFF   TRUE

default value to add an objective cutoff

Definition at line 106 of file heur_dks.c.

DEFAULT_RUNBINPROBSONLY

#define DEFAULT_RUNBINPROBSONLY   FALSE

default value to run only for bin or bin + int only problems

Definition at line 107 of file heur_dks.c.

Typedef Documentation

BUCKETLIST

typedef struct Bucketlist BUCKETLIST

data related to one bucket list, details see below

Definition at line 114 of file heur_dks.c.

BUCKET

typedef struct Bucket BUCKET

data related to one bucket

Function Documentation

getLinkingScoreAndBlocklabels()

static SCIP_RETCODE getLinkingScoreAndBlocklabels ( int *  blocklabels, int *  varlabels, int *  conslabels, SCIP_Real *  linkscore, int *  nblocklabels, int  nblocks, int  nvars, int  nconss  )

static

calculate the linking score of a given decomposition

Parameters

blocklabels	int array to store the different block labels
varlabels	array of variable labels
conslabels	array of constraint labels
linkscore	linking score to return
nblocklabels	number of block labels to return
nblocks	number of blocks
nvars	number of variables
nconss	number of constraints

Definition at line 174 of file heur_dks.c.

References b, FALSE, NULL, SCIP_Bool, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIP_Real, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

countKernelVariables()

static SCIP_RETCODE countKernelVariables ( SCIP *  scip, SCIP_VAR **  vars, SCIP_SOL *  bestcurrsol, SCIP_HASHMAP *  lbvarmap, SCIP_Bool  twolevel, SCIP_Bool  usebestsol, SCIP_Bool  usetransprob, SCIP_Bool  usetranslb, int *  bw_ncontkernelvars, int *  bw_ncontnonkernelvars, int *  bw_nkernelvars, int *  bw_nnonkernelvars, int *  bw_nintkernelvars, int *  bw_nintnonkernelvars, int *  ncontkernelvars, int *  ncontnonkernelvars, int *  nkernelvars, int *  nnonkernelvars, int *  nintkernelvars, int *  nintnonkernelvars, int *  block2index, int *  varlabels, int  blklbl_offset, int  nvars  )

static

count of potential kernel variables for one level or two level structure

Parameters

scip	main SCIP data structure
vars	array of variables
bestcurrsol	best current solution
lbvarmap	original lower bound of transformed variables
twolevel	usage of one or two level structure
usebestsol	usage of best or lp solution
usetransprob	usage of transformed or original problem
usetranslb	usage of transformed lb in comparison to original lb
bw_ncontkernelvars	blockwise number of continuous kernel variables
bw_ncontnonkernelvars	blockwise number of continuous non-kernel variables
bw_nkernelvars	blockwise number of (binary) kernel variables
bw_nnonkernelvars	blockwise number of (binary) non-kernel variables
bw_nintkernelvars	blockwise number of integer kernel variables
bw_nintnonkernelvars	blockwise number of integer non-kernel variables
ncontkernelvars	number of continuous kernel variables
ncontnonkernelvars	number of continuous non-kernel variables
nkernelvars	number of (binary) kernel variables
nnonkernelvars	number of (binary) non-kernel variables
nintkernelvars	number of integer kernel variables
nintnonkernelvars	number of integer non-kernel variables
block2index	mapping of block labels to block index
varlabels	array of variable labels
blklbl_offset	optional offset for the blocklabels, if it exists a block 0
nvars	number of variables

Definition at line 240 of file heur_dks.c.

References MAX, NULL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIPgetSolVal(), SCIPhashmapGetImageReal(), SCIPisEQ(), SCIPisGT(), SCIPvarGetLbLocal(), SCIPvarGetLbOriginal(), SCIPvarGetLPSol(), and SCIPvarGetType().

Referenced by SCIP_DECL_HEUREXEC().

fillKernels()

static SCIP_RETCODE fillKernels ( SCIP *  scip, SCIP_VAR **  vars, SCIP_VAR **  binintvars, SCIP_VAR ***  bw_contkernelvars, SCIP_VAR ***  bw_contnonkernelvars, SCIP_VAR ***  bw_kernelvars, SCIP_VAR ***  bw_nonkernelvars, SCIP_VAR ***  bw_intkernelvars, SCIP_VAR ***  bw_intnonkernelvars, SCIP_SOL *  bestcurrsol, SCIP_HASHMAP *  lbvarmap, SCIP_Bool  twolevel, SCIP_Bool  usebestsol, SCIP_Bool  usetransprob, SCIP_Bool  usetranslb, int *  bw_contkernelcount, int *  bw_contnonkernelcount, int *  bw_kernelcount, int *  bw_nonkernelcount, int *  bw_intkernelcount, int *  bw_intnonkernelcount, int *  bw_ncontkernelvars, int *  bw_ncontnonkernelvars, int *  bw_nkernelvars, int *  bw_nnonkernelvars, int *  bw_nintkernelvars, int *  bw_nintnonkernelvars, int *  block2index, int *  varlabels, int  blklbl_offset, int  nvars  )

static

fill the blockwise kernels with the respective variables

Parameters

scip	main SCIP data structure
vars	array of variables
binintvars	array of binary and integer variables
bw_contkernelvars	blockwise array of continuous kernel variables
bw_contnonkernelvars	blockwise array of continuous non-kernel variables
bw_kernelvars	blockwise array of (binary) kernel variables
bw_nonkernelvars	blockwise array of (binary) non-kernel variables
bw_intkernelvars	blockwise array of integer kernel variables
bw_intnonkernelvars	blockwise array of integer non-kernel variables
bestcurrsol	best current solution
lbvarmap	original lower bound of transformed variables
twolevel	usage of one or two level structure
usebestsol	usage of best or lp solution
usetransprob	usage of transformed or original problem
usetranslb	usage of transformed lb in comparison to original lb
bw_contkernelcount	blockwise counter of continuous kernel variables
bw_contnonkernelcount	blockwise counter of continuous non-kernel variables
bw_kernelcount	blockwise counter of (binary) kernel variables
bw_nonkernelcount	blockwise counter of (binary) non-kernel variables
bw_intkernelcount	blockwise counter of integer kernel variables
bw_intnonkernelcount	blockwise counter of integer non-kernel variables
bw_ncontkernelvars	blockwise number of continuous kernel variables
bw_ncontnonkernelvars	blockwise number of continuous non-kernel variables
bw_nkernelvars	blockwise number of (binary) kernel variables
bw_nnonkernelvars	blockwise number of (binary) non-kernel variables
bw_nintkernelvars	blockwise number of integer kernel variables
bw_nintnonkernelvars	blockwise number of integer non-kernel variables
block2index	mapping of block labels to block index
varlabels	array of variable labels
blklbl_offset	optional offset for the blocklabels, if it exists a block 0
nvars	number of variables

Definition at line 369 of file heur_dks.c.

References MAX, NULL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIPgetSolVal(), SCIPhashmapGetImageReal(), SCIPisEQ(), SCIPisGT(), SCIPvarGetLbLocal(), SCIPvarGetLbOriginal(), SCIPvarGetLPSol(), and SCIPvarGetType().

Referenced by SCIP_DECL_HEUREXEC().

reducedCostSort()

static SCIP_RETCODE reducedCostSort ( SCIP *  scip, SCIP_VAR ***  bw_contnonkernelvars, SCIP_VAR ***  bw_nonkernelvars, SCIP_VAR ***  bw_intnonkernelvars, SCIP_Real ***  bw_cont_redcost, SCIP_Real ***  bw_redcost, SCIP_Real ***  bw_int_redcost, int *  bw_ncontnonkernelvars, int *  bw_nnonkernelvars, int *  bw_nintnonkernelvars, SCIP_Bool  twolevel, int  nblocks  )

static

calculation of reduced costs and non-decreasing sorting

Parameters

scip	main SCIP data structure
bw_contnonkernelvars	array pointer of continuous, non-kernel variables
bw_nonkernelvars	array pointer of (binary,) non-kernel variables
bw_intnonkernelvars	array pointer of integer, non-kernel variables
bw_cont_redcost	array pointer with reduced costs for continuous variables
bw_redcost	array pointer with reduced costs for (binary) variables
bw_int_redcost	array pointer with reduced costs for integer variables
bw_ncontnonkernelvars	blockwise number of continuous, non-kernel variables
bw_nnonkernelvars	blockwise number of (binary,) non-kernel variables
bw_nintnonkernelvars	blockwise number of integer, non-kernel variables
twolevel	usage of one or two level structure
nblocks	number of blocks

Definition at line 544 of file heur_dks.c.

References b, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIPallocBufferArray, SCIPgetVarRedcost(), and SCIPsortRealPtr().

Referenced by SCIP_DECL_HEUREXEC().

freeRedcostArrays()

static SCIP_RETCODE freeRedcostArrays ( SCIP *  scip, SCIP_Real ***  bw_cont_redcost, SCIP_Real ***  bw_redcost, SCIP_Real ***  bw_int_redcost, int  nblocks  )

static

free memory of reduced cost arrays

Parameters

scip	main SCIP data structure
bw_cont_redcost	array pointer with reduced costs for continuous variables
bw_redcost	array pointer with reduced costs for (binary) variables
bw_int_redcost	array pointer with reduced costs for integer variables
nblocks	number of blocks

Definition at line 613 of file heur_dks.c.

References b, NULL, SCIP_OKAY, and SCIPfreeBufferArray.

Referenced by SCIP_DECL_HEUREXEC().

isInCurrentLogBucket()

static SCIP_Bool isInCurrentLogBucket ( SCIP *  scip, SCIP_Real  base, SCIP_Real  redcost, SCIP_Real  redcostmin, int  currentindex, int  nbuckets  )

static

determines affiliation to a redcost (logsorted) bucket, avoiding inf to inf comparison

Parameters

scip	SCIP data structure
base	the nbuckets-th-root of the shifted max red costs in current bucket
redcost	the reduced cost of the current variable
redcostmin	the minimal reduced cost of the current block for shifting
currentindex	current iteration index
nbuckets	number of buckets

Definition at line 662 of file heur_dks.c.

References SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisInfinity(), and SCIPisLE().

Referenced by fillBuckets().

fillBuckets()

static SCIP_RETCODE fillBuckets ( SCIP *  scip, BUCKETLIST **  bucketlist, SCIP_VAR ***  bw_contnonkernelvars, SCIP_VAR ***  bw_nonkernelvars, SCIP_VAR ***  bw_intnonkernelvars, int *  bw_ncontnonkernelvars, int *  bw_nnonkernelvars, int *  bw_nintnonkernelvars, SCIP_Real **  bw_cont_redcost, SCIP_Real **  bw_redcost, SCIP_Real **  bw_int_redcost, SCIP_Bool  twolevel, SCIP_Bool  redcostlogsort, int  nbuckets, int  nblocks  )

static

fill bucket with its variables

Parameters

scip	main SCIP data structure
bucketlist	array pointer of buckets to fill
bw_contnonkernelvars	array of continuous, non-kernel variables
bw_nonkernelvars	array of (binary,) non-kernel variables
bw_intnonkernelvars	array of integer, non-kernel variables
bw_ncontnonkernelvars	blockwise number of continuous, non-kernel variables
bw_nnonkernelvars	blockwise number of (binary,) non-kernel variables
bw_nintnonkernelvars	blockwise number of integer, non-kernel variables
bw_cont_redcost	blockwise reduced costs of continuous, non-kernel variables
bw_redcost	blockwise reduced costs of (binary,) non-kernel variables
bw_int_redcost	blockwise reduced costs of integer, non-kernel variables
twolevel	usage of one or two level structure
redcostlogsort	filling the buckets by logarithmically reduced cost sort
nbuckets	number of buckets
nblocks	number of blocks

Definition at line 699 of file heur_dks.c.

References b, Bucket::bucketvars, Bucket::contbucketvars, Bucket::intbucketvars, isInCurrentLogBucket(), Bucket::nbucketvars, Bucket::ncontbucketvars, Bucket::nintbucketvars, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPceil(), SCIPfreeBufferArray, and SCIPisInfinity().

Referenced by SCIP_DECL_HEUREXEC().

freeBucketArrays()

static SCIP_RETCODE freeBucketArrays ( SCIP *  scip, BUCKET *  bucket, SCIP_Bool  twolevel  )

static

release memory of bucket arrays

Parameters

scip	main SCIP data structure
bucket	bucket to free the arrays from
twolevel	usage of one or two level structure

Definition at line 944 of file heur_dks.c.

References Bucket::bucketvars, Bucket::contbucketvars, Bucket::intbucketvars, NULL, SCIP_OKAY, and SCIPfreeBufferArray.

Referenced by SCIP_DECL_HEUREXEC().

initBucket()

static SCIP_RETCODE initBucket ( BUCKETLIST *  bucketlist )

static

initialize a bucket

Parameters

bucketlist

bucketlist structure where the bucket belongs to

Definition at line 962 of file heur_dks.c.

References Bucket::bucketlist, Bucketlist::buckets, Bucket::bucketvars, Bucket::contbucketvars, FALSE, Bucket::intbucketvars, Bucketlist::nbuckets, Bucket::nbucketvars, Bucket::ncontbucketvars, Bucket::nintbucketvars, NULL, Bucket::number, Bucketlist::scip, Bucket::scip2sub, SCIP_OKAY, Bucket::sub2scip, Bucket::subscip, and Bucket::twolevel.

Referenced by createBucketlistAndBuckets().

freeBucket()

static SCIP_RETCODE freeBucket ( SCIP *  scip, BUCKET *  bucket  )

static

free bucket structure

Parameters

scip	SCIP data structure
bucket	bucket structure to free

Definition at line 993 of file heur_dks.c.

References NULL, Bucket::scip2sub, SCIP_CALL, SCIP_OKAY, SCIPfree(), SCIPfreeBufferArrayNull, Bucket::sub2scip, and Bucket::subscip.

Referenced by SCIP_DECL_HEUREXEC().

initBucketlist()

static SCIP_RETCODE initBucketlist ( SCIP *  scip, BUCKETLIST **  bucketlist, int  nbuckets  )

static

initialize the bucketlist

Parameters

scip	SCIP data structure
bucketlist	pointer to bucketlist
nbuckets	number of buckets

Definition at line 1015 of file heur_dks.c.

References NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPgetProbName(), and SCIPsnprintf().

Referenced by createBucketlistAndBuckets().

freeBucketlist()

static SCIP_RETCODE freeBucketlist ( BUCKETLIST **  bucketlist, int  nbuckets  )

static

free bucketlist structure

Parameters

bucketlist	pointer to bucketlist to free
nbuckets	number of buckets to free

Definition at line 1043 of file heur_dks.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_HEUREXEC().

bucketCreateSubscip()

static SCIP_RETCODE bucketCreateSubscip ( BUCKET *  bucket, SCIP_Bool  usetransprob, SCIP_Bool *  success  )

static

creates the subscip for each bucket

Parameters

bucket	the bucket to create the subscip for
usetransprob	indicating whether the transformed or the original problem is used
success	pointer to store if the creation process was successfull

Definition at line 1067 of file heur_dks.c.

References Bucket::bucketlist, FALSE, HEUR_NAME, NULL, Bucket::number, Bucketlist::scip, Bucket::scip2sub, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPaddCons(), SCIPallocClearBufferArray, SCIPblkmem(), SCIPconsGetHdlr(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPcopyLimits(), SCIPcopyParamSettings(), SCIPcopyPlugins(), SCIPcopyProb(), SCIPcopyVars(), SCIPcreate(), SCIPdebugMsg, SCIPgetConsCopy(), SCIPgetConss(), SCIPgetNConss(), SCIPgetProbName(), SCIPgetVars(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapEntryGetImage(), SCIPhashmapEntryGetOrigin(), SCIPhashmapFree(), SCIPhashmapGetEntry(), SCIPhashmapGetNEntries(), SCIPisFeasEQ(), SCIPisParamFixed(), SCIPreleaseCons(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetSubscipsOff(), SCIPsnprintf(), SCIPunfixParam(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIPverbMessage(), SCIPwarningMessage(), Bucket::sub2scip, Bucket::subscip, and TRUE.

Referenced by createBucketlistAndBuckets().

createBucketlistAndBuckets()

static SCIP_RETCODE createBucketlistAndBuckets ( SCIP *  scip, SCIP_Bool  usetransprob, int  nbuckets, BUCKETLIST **  bucketlist, SCIP_Bool *  success  )

static

create bucketlist and initialize buckets

Parameters

scip	SCIP data structure
usetransprob	indication whether to use the transformed problem (or the original)
nbuckets	number of buckets (without kernel only)
bucketlist	pointer to store bucketlist structure
success	pointer to store if the creation process was successfull

Definition at line 1262 of file heur_dks.c.

References b, bucketCreateSubscip(), initBucket(), initBucketlist(), NULL, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

searchKernelAndBucket()

static SCIP_RETCODE searchKernelAndBucket ( BUCKET *  bucket, SCIP_VAR **  contkernelvars, int  ncontkernelvars, SCIP_VAR **  kernelvars, int  nkernelvars, SCIP_VAR **  intkernelvars, int  nintkernelvars, SCIP_VAR *  var, SCIP_Bool *  found  )

static

search variable in kernel and bucket

Parameters

bucket	bucket to be solved next
contkernelvars	continuous variables in the latest kernel
ncontkernelvars	amount of continuous variables in the latest kernel
kernelvars	variables in the kernel
nkernelvars	amount of variables in the kernel
intkernelvars	variables in the integer kernel, if 2-level buckets are present
nintkernelvars	amount of variables in the integer kernel
var	variable to search for in the kernel/buckets
found	is the variable present in the current bucket or the kernel?

Definition at line 1301 of file heur_dks.c.

References Bucket::bucketvars, Bucket::contbucketvars, FALSE, Bucket::intbucketvars, Bucket::nbucketvars, Bucket::ncontbucketvars, Bucket::nintbucketvars, NULL, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPvarGetType(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

adjustKernelVars()

static SCIP_RETCODE adjustKernelVars ( SCIP *  scip, BUCKET *  bucket, SCIP_VAR ***  contkernelvars, int *  ncontkernelvars, int  maxcontkernelsize, SCIP_VAR ***  kernelvars, int *  nkernelvars, int  maxkernelsize, SCIP_VAR ***  intkernelvars, int *  nintkernelvars, int  maxintkernelsize, SCIP_Bool  twolevel  )

static

adjust the kernel variables

Parameters

scip	current scip
bucket	bucket that was solved last
contkernelvars	cont. kernelvars to adjust
ncontkernelvars	amount of cont. kernelvars
maxcontkernelsize	maximal size of the continuous kernel
kernelvars	kernelvars to adjust
nkernelvars	amount of kernelvars
maxkernelsize	maximal size of the kernel
intkernelvars	integer kernelvars to adjust
nintkernelvars	amount of integer kernelvars
maxintkernelsize	maximal size of the integer kernel
twolevel	is a twolevel structure necessary

Definition at line 1385 of file heur_dks.c.

References Bucket::bucketvars, Bucket::contbucketvars, Bucket::intbucketvars, Bucket::nbucketvars, Bucket::ncontbucketvars, Bucket::nintbucketvars, NULL, Bucket::scip2sub, SCIP_OKAY, SCIP_Real, SCIPgetBestSol(), SCIPgetNVars(), SCIPgetSolVal(), SCIPisEQ(), SCIPisGT(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarIsActive(), and Bucket::subscip.

Referenced by SCIP_DECL_HEUREXEC().

addUseConstraint()

static SCIP_RETCODE addUseConstraint ( BUCKET *  bucket )

static

add usuage constraint

Parameters

bucket

current bucket to look at

Definition at line 1637 of file heur_dks.c.

References Bucket::bucketvars, Bucket::intbucketvars, Bucket::nbucketvars, Bucket::nintbucketvars, NULL, Bucket::number, Bucket::scip2sub, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsBasicLinear(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisInfinity(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarIsActive(), and Bucket::subscip.

Referenced by SCIP_DECL_HEUREXEC().

SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyDKS  )

static

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

Definition at line 1735 of file heur_dks.c.

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

SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeDKS  )

static

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

Definition at line 1750 of file heur_dks.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().

SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecDKS  )

static

execution method of primal heuristic

Definition at line 1768 of file heur_dks.c.

References addUseConstraint(), adjustKernelVars(), b, Bucketlist::buckets, Bucket::bucketvars, countKernelVariables(), createBucketlistAndBuckets(), FALSE, fillBuckets(), fillKernels(), freeBucket(), freeBucketArrays(), freeBucketlist(), freeRedcostArrays(), getLinkingScoreAndBlocklabels(), MIN, Bucketlist::nbuckets, Bucket::nbucketvars, Bucket::nintbucketvars, nnodes, NULL, Bucket::number, reducedCostSort(), Bucket::scip2sub, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPallocClearBlockMemoryArray, SCIPallocClearBufferArray, SCIPblkmem(), SCIPceil(), SCIPconshdlrGetNConss(), SCIPdebug, SCIPdebugMsg, SCIPdecompGetConsLabels(), SCIPdecompGetNBlocks(), SCIPdecompGetVarsLabels(), SCIPduplicateBufferArray, SCIPfindConshdlr(), SCIPfixVar(), SCIPfloor(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetConss(), SCIPgetCutoffbound(), SCIPgetDecomps(), SCIPgetLPSolstat(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNConss(), SCIPgetNNodes(), SCIPgetNOrigConss(), SCIPgetNSols(), SCIPgetOrigConss(), SCIPgetOrigVars(), SCIPgetOrigVarsData(), SCIPgetRealParam(), SCIPgetSolOrigObj(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPgetTotalTime(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapSetImageReal(), SCIPheurGetData(), SCIPinfinity(), SCIPisGT(), SCIPisInfinity(), SCIPprintSol(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetRealParam(), SCIPsnprintf(), SCIPsolve(), SCIPsortInt(), SCIPtranslateSubSol(), SCIPtrySolFree(), SCIPvarGetLbLocal(), SCIPvarGetLbOriginal(), SCIPvarGetOrigvarSum(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPwriteOrigProblem(), SCIPwriteTransProblem(), searchKernelAndBucket(), Bucket::subscip, and TRUE.