Detailed Description

LP diving heuristic that rounds variables with long column vectors.

Author: Tobias Achterberg; Christian Puchert

Definition in file heur_gcgveclendiving.c.

#include <assert.h>
#include <string.h>
#include "heur_gcgveclendiving.h"
#include "heur_origdiving.h"
#include "gcg.h"

Go to the source code of this file.

Data Structures
struct	GCG_DivingData

Macros
#define	HEUR_NAME "gcgveclendiving"

#define	HEUR_DESC "LP diving heuristic that rounds variables with long column vectors"

#define	HEUR_DISPCHAR 'v'

#define	HEUR_PRIORITY -1003100

#define	HEUR_FREQ 10

#define	HEUR_FREQOFS 4

#define	HEUR_MAXDEPTH -1

#define	DEFAULT_USEMASTERSCORES FALSE

Functions
static SCIP_RETCODE	calculateScoreOrig (SCIP scip, SCIP_VAR var, SCIP_Real frac, SCIP_Real score, SCIP_Bool roundup)

static SCIP_Bool	areVarsInSameBlock (SCIP_VAR origvar, SCIP_VAR mastervar)

static SCIP_RETCODE	getMasterDownScore (SCIP scip, GCG_DIVINGDATA divingdata, SCIP_VAR var, SCIP_Real score)

static SCIP_RETCODE	getMasterUpScore (SCIP scip, GCG_DIVINGDATA divingdata, SCIP_VAR var, SCIP_Real score)

static SCIP_RETCODE	calculateScoreMaster (SCIP scip, GCG_DIVINGDATA divingdata, SCIP_VAR var, SCIP_Real score, SCIP_Bool *roundup)

static	GCG_DECL_DIVINGFREE (heurFreeGcgveclendiving)

static	GCG_DECL_DIVINGINITEXEC (heurInitexecGcgveclendiving)

static	GCG_DECL_DIVINGEXITEXEC (heurExitexecGcgveclendiving)

static	GCG_DECL_DIVINGSELECTVAR (heurSelectVarGcgveclendiving)

SCIP_RETCODE	GCGincludeHeurGcgveclendiving (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "gcgveclendiving"

Definition at line 44 of file heur_gcgveclendiving.c.

◆ HEUR_DESC

#define HEUR_DESC "LP diving heuristic that rounds variables with long column vectors"

Definition at line 45 of file heur_gcgveclendiving.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'v'

Definition at line 46 of file heur_gcgveclendiving.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -1003100

Definition at line 47 of file heur_gcgveclendiving.c.

◆ HEUR_FREQ

#define HEUR_FREQ 10

Definition at line 48 of file heur_gcgveclendiving.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 4

Definition at line 49 of file heur_gcgveclendiving.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 50 of file heur_gcgveclendiving.c.

◆ DEFAULT_USEMASTERSCORES

#define DEFAULT_USEMASTERSCORES FALSE

calculate vector length scores w.r.t. the master LP?

Definition at line 57 of file heur_gcgveclendiving.c.

Function Documentation

◆ calculateScoreOrig()

static SCIP_RETCODE calculateScoreOrig	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Real	frac,
		SCIP_Real *	score,
		SCIP_Bool *	roundup
	)

static

for a variable, calculate the vector length score w.r.t. the original problem

Parameters

scip	SCIP data structure
var	variable to calculate score for
frac	the variable's fractionality in the current LP solution
score	pointer to return the score
roundup	pointer to return whether the variable is rounded up

Definition at line 74 of file heur_gcgveclendiving.c.

Referenced by GCG_DECL_DIVINGSELECTVAR().

◆ areVarsInSameBlock()

static SCIP_Bool areVarsInSameBlock	(	SCIP_VAR *	origvar,
		SCIP_VAR *	mastervar
	)

static

check whether an original variable and a master variable belong to the same block

Parameters

origvar	original variable
mastervar	master variable

Definition at line 105 of file heur_gcgveclendiving.c.

References GCGisLinkingVarInBlock(), GCGoriginalVarGetMastervars(), GCGoriginalVarGetNMastervars(), GCGoriginalVarIsLinking(), and GCGvarGetBlock().

Referenced by getMasterDownScore(), and getMasterUpScore().

◆ getMasterDownScore()

static SCIP_RETCODE getMasterDownScore	(	SCIP *	scip,
		GCG_DIVINGDATA *	divingdata,
		SCIP_VAR *	var,
		SCIP_Real *	score
	)

static

get the 'down' score of an original variable w.r.t. the master problem; this is the sum of the vector length scores of the master variables which would have to be fixed to zero if the original variable were rounded down

Parameters

scip	SCIP data structure
divingdata	diving heuristic data
var	original variable to get fractionality for
score	pointer to store fractionality

Definition at line 163 of file heur_gcgveclendiving.c.

References areVarsInSameBlock(), GCGgetMasterprob(), GCGoriginalVarGetMastervals(), GCGoriginalVarGetNMastervars(), and GCG_DivingData::masterscores.

Referenced by calculateScoreMaster().

◆ getMasterUpScore()

static SCIP_RETCODE getMasterUpScore	(	SCIP *	scip,
		GCG_DIVINGDATA *	divingdata,
		SCIP_VAR *	var,
		SCIP_Real *	score
	)

static

get the 'up' score of an original variable w.r.t. the master problem; this is the sum of the scores of the master variables which would have to be fixed to zero if the original variable were rounded up

Parameters

scip	SCIP data structure
divingdata	diving heuristic data
var	original variable to get fractionality for
score	pointer to store fractionality

Definition at line 220 of file heur_gcgveclendiving.c.

References areVarsInSameBlock(), GCGgetMasterprob(), GCGoriginalVarGetMastervals(), GCGoriginalVarGetNMastervars(), and GCG_DivingData::masterscores.

Referenced by calculateScoreMaster().

◆ calculateScoreMaster()

static SCIP_RETCODE calculateScoreMaster	(	SCIP *	scip,
		GCG_DIVINGDATA *	divingdata,
		SCIP_VAR *	var,
		SCIP_Real *	score,
		SCIP_Bool *	roundup
	)

static

for a variable, calculate the vector length score w.r.t. the master problem

Parameters

scip	SCIP data structure
divingdata	diving heuristic data
var	variable to calculate score for
score	pointer to return the score
roundup	pointer to return whether the variable is rounded up

Definition at line 274 of file heur_gcgveclendiving.c.

References getMasterDownScore(), and getMasterUpScore().

Referenced by GCG_DECL_DIVINGSELECTVAR().

◆ GCG_DECL_DIVINGFREE()

static GCG_DECL_DIVINGFREE ( heurFreeGcgveclendiving )

static

destructor of diving heuristic to free user data (called when GCG is exiting)

Definition at line 307 of file heur_gcgveclendiving.c.

References GCGheurGetDivingDataOrig(), and GCGheurSetDivingDataOrig().

◆ GCG_DECL_DIVINGINITEXEC()

static GCG_DECL_DIVINGINITEXEC ( heurInitexecGcgveclendiving )

static

execution initialization method of diving heuristic (called when execution of diving heuristic is about to begin)

Definition at line 326 of file heur_gcgveclendiving.c.

References GCGgetMasterprob(), GCGheurGetDivingDataOrig(), GCG_DivingData::masterscores, and GCG_DivingData::usemasterscores.

◆ GCG_DECL_DIVINGEXITEXEC()

static GCG_DECL_DIVINGEXITEXEC ( heurExitexecGcgveclendiving )

static

execution deinitialization method of diving heuristic (called when execution data is freed)

Definition at line 383 of file heur_gcgveclendiving.c.

References GCGheurGetDivingDataOrig(), GCG_DivingData::masterscores, and GCG_DivingData::usemasterscores.

◆ GCG_DECL_DIVINGSELECTVAR()

static GCG_DECL_DIVINGSELECTVAR ( heurSelectVarGcgveclendiving )

static

variable selection method of diving heuristic; finds best candidate variable w.r.t. vector length:

round variables in direction where objective value gets worse; for zero objective coefficient, round upwards
round variable with least objective value deficit per row the variable appears in (we want to "fix" as many rows as possible with the least damage to the objective function)

Definition at line 411 of file heur_gcgveclendiving.c.

References calculateScoreMaster(), calculateScoreOrig(), GCGheurGetDivingDataOrig(), and GCG_DivingData::usemasterscores.

◆ GCGincludeHeurGcgveclendiving()

SCIP_RETCODE GCGincludeHeurGcgveclendiving ( SCIP * scip )

creates the gcgveclendiving heuristic and includes it in GCG

Parameters

scip	SCIP data structure

Definition at line 484 of file heur_gcgveclendiving.c.

References DEFAULT_USEMASTERSCORES, GCGincludeDivingHeurOrig(), HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, and GCG_DivingData::usemasterscores.

Referenced by SCIPincludeGcgPlugins().

GCG

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ DEFAULT_USEMASTERSCORES

Function Documentation

◆ calculateScoreOrig()

◆ areVarsInSameBlock()

◆ getMasterDownScore()

◆ getMasterUpScore()

◆ calculateScoreMaster()

◆ GCG_DECL_DIVINGFREE()

◆ GCG_DECL_DIVINGINITEXEC()

◆ GCG_DECL_DIVINGEXITEXEC()

◆ GCG_DECL_DIVINGSELECTVAR()

◆ GCGincludeHeurGcgveclendiving()