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

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.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ DEFAULT_ADDUSECONSS

#define DEFAULT_ADDUSECONSS TRUE

default value to add a use constraint

Definition at line 91 of file heur_dks.c.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ DEFAULT_USETRANSPROB

#define DEFAULT_USETRANSPROB TRUE

default value to use the original or transformed problem

Definition at line 95 of file heur_dks.c.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ DEFAULT_USEDECOMP

#define DEFAULT_USEDECOMP TRUE

default value to use the decomp if given

Definition at line 101 of file heur_dks.c.

Referenced by SCIPincludeHeurDKS(), and SCIPincludeHeurGins().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

◆ DEFAULT_OBJCUTOFF

#define DEFAULT_OBJCUTOFF TRUE

default value to add an objective cutoff

Definition at line 106 of file heur_dks.c.

Referenced by SCIPincludeHeurDKS().

◆ 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.

Referenced by SCIPincludeHeurDKS().

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()

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 assert(), b, FALSE, NULL, nvars, SCIP_Bool, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIP_Real, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ countKernelVariables()

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 assert(), i, MAX, NULL, nvars, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIPgetSolVal(), SCIPhashmapGetImageReal(), SCIPisEQ(), SCIPisGT(), SCIPvarGetLbLocal(), SCIPvarGetLbOriginal(), SCIPvarGetLPSol(), SCIPvarGetType(), and vars.

Referenced by SCIP_DECL_HEUREXEC().

◆ fillKernels()

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 assert(), i, MAX, NULL, nvars, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIPgetSolVal(), SCIPhashmapGetImageReal(), SCIPisEQ(), SCIPisGT(), SCIPvarGetLbLocal(), SCIPvarGetLbOriginal(), SCIPvarGetLPSol(), SCIPvarGetType(), and vars.

Referenced by SCIP_DECL_HEUREXEC().

◆ reducedCostSort()

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, i, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPgetVarRedcost(), and SCIPsortRealPtr().

Referenced by SCIP_DECL_HEUREXEC().

◆ freeRedcostArrays()

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, SCIP_Real, and SCIPfreeBufferArray.

Referenced by SCIP_DECL_HEUREXEC().

◆ isInCurrentLogBucket()

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 assert(), SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisInfinity(), and SCIPisLE().

Referenced by fillBuckets().

◆ fillBuckets()

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 assert(), b, Bucket::bucketvars, Bucket::contbucketvars, Bucket::intbucketvars, isInCurrentLogBucket(), Bucket::nbucketvars, Bucket::ncontbucketvars, Bucket::nintbucketvars, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPceil(), SCIPfreeBufferArray, and SCIPisInfinity().

Referenced by SCIP_DECL_HEUREXEC().

◆ freeBucketArrays()

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_Bool, SCIP_OKAY, and SCIPfreeBufferArray.

Referenced by SCIP_DECL_HEUREXEC().

◆ initBucket()

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 assert(), 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()

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 assert(), NULL, Bucket::scip2sub, SCIP_CALL, SCIP_OKAY, SCIPfree(), SCIPfreeBufferArrayNull, Bucket::sub2scip, and Bucket::subscip.

Referenced by SCIP_DECL_HEUREXEC().

◆ initBucketlist()

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 assert(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPgetProbName(), and SCIPsnprintf().

Referenced by createBucketlistAndBuckets().

◆ freeBucketlist()

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 assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_HEUREXEC().

◆ bucketCreateSubscip()

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 assert(), Bucket::bucketlist, FALSE, HEUR_NAME, i, NULL, Bucket::number, nvars, Bucketlist::scip, Bucket::scip2sub, SCIP_Bool, 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, TRUE, var, and vars.

Referenced by createBucketlistAndBuckets().

◆ createBucketlistAndBuckets()

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 assert(), b, bucketCreateSubscip(), initBucket(), initBucketlist(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ searchKernelAndBucket()

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_Bool, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPvarGetType(), TRUE, and var.

Referenced by SCIP_DECL_HEUREXEC().

◆ adjustKernelVars()

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 assert(), Bucket::bucketvars, Bucket::contbucketvars, Bucket::intbucketvars, Bucket::nbucketvars, Bucket::ncontbucketvars, Bucket::nintbucketvars, NULL, Bucket::scip2sub, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPgetBestSol(), SCIPgetNVars(), SCIPgetSolVal(), SCIPisEQ(), SCIPisGT(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarIsActive(), Bucket::subscip, and var.

Referenced by SCIP_DECL_HEUREXEC().

◆ addUseConstraint()

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(), Bucket::subscip, and var.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

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 assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurDKS().

◆ SCIP_DECL_HEURFREE()

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 assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEUREXEC()

SCIP_DECL_HEUREXEC ( heurExecDKS )

static

execution method of primal heuristic

Definition at line 1768 of file heur_dks.c.

References addUseConstraint(), adjustKernelVars(), assert(), b, Bucketlist::buckets, Bucket::bucketvars, countKernelVariables(), createBucketlistAndBuckets(), cutoff, FALSE, fillBuckets(), fillKernels(), freeBucket(), freeBucketArrays(), freeBucketlist(), freeRedcostArrays(), getLinkingScoreAndBlocklabels(), heurdata, i, MIN, Bucketlist::nbuckets, Bucket::nbucketvars, Bucket::nintbucketvars, nnodes, NULL, Bucket::number, nvars, reducedCostSort(), result, 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(), sol, Bucket::subscip, TRUE, var, and vars.

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXBUCKS

◆ DEFAULT_KERNELSIZEFACTOR

◆ DEFAULT_ADDUSECONSS

◆ DEFAULT_LINKBUCKSIZE

◆ DEFAULT_TRANSLBKERNEL

◆ DEFAULT_LESSLOCKSKERNEL

◆ DEFAULT_USETRANSPROB

◆ DEFAULT_BUCKMAXGAP

◆ DEFAULT_MAXLINKSCORE

◆ DEFAULT_MAXBUCKFRAC

◆ DEFAULT_MAXNODES

◆ DEFAULT_USETWOLEVEL

◆ DEFAULT_USEDECOMP

◆ DEFAULT_USEBESTSOL

◆ DEFAULT_REDCOSTSORT

◆ DEFAULT_PRIMALONLY

◆ DEFAULT_REDCOSTLOGSORT

◆ DEFAULT_OBJCUTOFF

◆ DEFAULT_RUNBINPROBSONLY

Typedef Documentation

◆ BUCKETLIST

◆ BUCKET

Function Documentation

◆ getLinkingScoreAndBlocklabels()

◆ countKernelVariables()

◆ fillKernels()

◆ reducedCostSort()

◆ freeRedcostArrays()

◆ isInCurrentLogBucket()

◆ fillBuckets()

◆ freeBucketArrays()

◆ initBucket()

◆ freeBucket()

◆ initBucketlist()

◆ freeBucketlist()

◆ bucketCreateSubscip()

◆ createBucketlistAndBuckets()

◆ searchKernelAndBucket()

◆ adjustKernelVars()

◆ addUseConstraint()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEUREXEC()