Detailed Description

LP diving heuristic that chooses fixings w.r.t. the pseudo cost values.

Author: Tobias Achterberg; Christian Puchert

Definition in file heur_gcgpscostdiving.c.

#include <assert.h>
#include <string.h>
#include "heur_gcgpscostdiving.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 "gcgpscostdiving"

#define	HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the pseudo cost values"

#define	HEUR_DISPCHAR 'p'

#define	HEUR_PRIORITY -1002000

#define	HEUR_FREQ 10

#define	HEUR_FREQOFS 2

#define	HEUR_MAXDEPTH -1

#define	DEFAULT_USEMASTERPSCOSTS FALSE

Functions
static SCIP_RETCODE	getRootRelaxSol (SCIP scip, SCIP_SOL *rootsol)

static SCIP_RETCODE	calcMasterPscosts (SCIP scip, SCIP_Real *masterpscosts)

static SCIP_Bool	areVarsInSameBlock (SCIP_VAR origvar, SCIP_VAR mastervar)

static SCIP_RETCODE	calcPscostDownMaster (SCIP scip, SCIP_VAR var, SCIP_Real masterpscosts, SCIP_Real pscostdown)

static SCIP_RETCODE	calcPscostUpMaster (SCIP scip, SCIP_VAR var, SCIP_Real masterpscosts, SCIP_Real pscostup)

static SCIP_RETCODE	calcPscostQuot (SCIP scip, GCG_DIVINGDATA divingdata, SCIP_VAR var, SCIP_Real primsol, SCIP_Real rootsolval, SCIP_Real frac, int rounddir, SCIP_Real pscostquot, SCIP_Bool *roundup)

static	GCG_DECL_DIVINGFREE (heurFreeGcgpscostdiving)

static	GCG_DECL_DIVINGINIT (heurInitGcgpscostdiving)

static	GCG_DECL_DIVINGEXIT (heurExitGcgpscostdiving)

static	GCG_DECL_DIVINGINITEXEC (heurInitexecGcgpscostdiving)

static	GCG_DECL_DIVINGEXITEXEC (heurExitexecGcgpscostdiving)

static	GCG_DECL_DIVINGSELECTVAR (heurSelectVarGcgpscostdiving)

SCIP_RETCODE	GCGincludeHeurGcgpscostdiving (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "gcgpscostdiving"

Definition at line 44 of file heur_gcgpscostdiving.c.

◆ HEUR_DESC

#define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the pseudo cost values"

Definition at line 45 of file heur_gcgpscostdiving.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'p'

Definition at line 46 of file heur_gcgpscostdiving.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -1002000

Definition at line 47 of file heur_gcgpscostdiving.c.

◆ HEUR_FREQ

#define HEUR_FREQ 10

Definition at line 48 of file heur_gcgpscostdiving.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 2

Definition at line 49 of file heur_gcgpscostdiving.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 50 of file heur_gcgpscostdiving.c.

◆ DEFAULT_USEMASTERPSCOSTS

#define DEFAULT_USEMASTERPSCOSTS FALSE

shall pseudocosts be calculated w.r.t. the master problem?

Definition at line 57 of file heur_gcgpscostdiving.c.

Function Documentation

◆ getRootRelaxSol()

static SCIP_RETCODE getRootRelaxSol	(	SCIP *	scip,
		SCIP_SOL **	rootsol
	)

static

get relaxation solution of root node (in original variables)

Parameters

scip	SCIP data structure
rootsol	pointer to store root relaxation solution

Definition at line 76 of file heur_gcgpscostdiving.c.

References GCGgetMasterprob(), and GCGtransformMastersolToOrigsol().

Referenced by GCG_DECL_DIVINGINITEXEC().

◆ calcMasterPscosts()

static SCIP_RETCODE calcMasterPscosts	(	SCIP *	scip,
		SCIP_Real **	masterpscosts
	)

static

calculate pseudocosts for the master variables

Parameters

scip	SCIP data structure
masterpscosts	pointer to store the array of master pseudocosts

Definition at line 114 of file heur_gcgpscostdiving.c.

References GCGgetMasterprob(), GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), and GCGmasterVarGetOrigvars().

Referenced by GCG_DECL_DIVINGINITEXEC().

◆ 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 167 of file heur_gcgpscostdiving.c.

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

Referenced by calcPscostDownMaster(), and calcPscostUpMaster().

◆ calcPscostDownMaster()

static SCIP_RETCODE calcPscostDownMaster	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Real *	masterpscosts,
		SCIP_Real *	pscostdown
	)

static

calculates the down-pseudocost for a given original variable w.r.t. the master variables in which it is contained

Parameters

scip	SCIP data structure
var	problem variable
masterpscosts	master variable pseudocosts
pscostdown	pointer to store the pseudocost value

Definition at line 222 of file heur_gcgpscostdiving.c.

References areVarsInSameBlock(), GCGgetMasterprob(), GCGoriginalVarGetMastervals(), GCGoriginalVarGetMastervars(), and GCGoriginalVarGetNMastervars().

Referenced by calcPscostQuot().

◆ calcPscostUpMaster()

static SCIP_RETCODE calcPscostUpMaster	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Real *	masterpscosts,
		SCIP_Real *	pscostup
	)

static

calculates the up-pseudocost for a given original variable w.r.t. the master variables in which it is contained

Parameters

scip	SCIP data structure
var	problem variable
masterpscosts	master variable pseudocosts
pscostup	pointer to store the pseudocost value

Definition at line 296 of file heur_gcgpscostdiving.c.

References areVarsInSameBlock(), GCGgetMasterprob(), GCGoriginalVarGetMastervals(), GCGoriginalVarGetMastervars(), and GCGoriginalVarGetNMastervars().

Referenced by calcPscostQuot().

◆ calcPscostQuot()

static SCIP_RETCODE calcPscostQuot	(	SCIP *	scip,
		GCG_DIVINGDATA *	divingdata,
		SCIP_VAR *	var,
		SCIP_Real	primsol,
		SCIP_Real	rootsolval,
		SCIP_Real	frac,
		int	rounddir,
		SCIP_Real *	pscostquot,
		SCIP_Bool *	roundup
	)

static

calculates the pseudocost score for a given variable w.r.t. a given solution value and a given rounding direction

Parameters

scip	SCIP data structure
divingdata	diving data
var	problem variable
primsol	primal solution of variable
rootsolval	root relaxation solution of variable
frac	fractionality of variable
rounddir	-1: round down, +1: round up, 0: select due to pseudo cost values
pscostquot	pointer to store pseudo cost quotient
roundup	pointer to store whether the variable should be rounded up

Definition at line 370 of file heur_gcgpscostdiving.c.

References calcPscostDownMaster(), calcPscostUpMaster(), GCG_DivingData::masterpscosts, and GCG_DivingData::usemasterpscosts.

Referenced by GCG_DECL_DIVINGSELECTVAR().

◆ GCG_DECL_DIVINGFREE()

static GCG_DECL_DIVINGFREE ( heurFreeGcgpscostdiving )

static

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

Definition at line 445 of file heur_gcgpscostdiving.c.

References GCGheurGetDivingDataOrig(), and GCGheurSetDivingDataOrig().

◆ GCG_DECL_DIVINGINIT()

static GCG_DECL_DIVINGINIT ( heurInitGcgpscostdiving )

static

initialization method of diving heuristic (called after problem was transformed)

Definition at line 464 of file heur_gcgpscostdiving.c.

References GCG_DivingData::firstrun, GCGheurGetDivingDataOrig(), GCG_DivingData::masterpscosts, and GCG_DivingData::rootsol.

◆ GCG_DECL_DIVINGEXIT()

static GCG_DECL_DIVINGEXIT ( heurExitGcgpscostdiving )

static

deinitialization method of diving heuristic (called before transformed problem is freed)

Definition at line 485 of file heur_gcgpscostdiving.c.

References GCG_DivingData::firstrun, GCGheurGetDivingDataOrig(), and GCG_DivingData::rootsol.

◆ GCG_DECL_DIVINGINITEXEC()

static GCG_DECL_DIVINGINITEXEC ( heurInitexecGcgpscostdiving )

static

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

Definition at line 507 of file heur_gcgpscostdiving.c.

References calcMasterPscosts(), GCG_DivingData::firstrun, GCGheurGetDivingDataOrig(), getRootRelaxSol(), GCG_DivingData::masterpscosts, and GCG_DivingData::rootsol.

◆ GCG_DECL_DIVINGEXITEXEC()

static GCG_DECL_DIVINGEXITEXEC ( heurExitexecGcgpscostdiving )

static

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

Definition at line 534 of file heur_gcgpscostdiving.c.

References GCGheurGetDivingDataOrig(), and GCG_DivingData::masterpscosts.

◆ GCG_DECL_DIVINGSELECTVAR()

static GCG_DECL_DIVINGSELECTVAR ( heurSelectVarGcgpscostdiving )

static

variable selection method of diving heuristic; finds best candidate variable w.r.t. pseudo costs:

prefer variables that may not be rounded without destroying LP feasibility:
- of these variables, round variable with largest rel. difference of pseudo cost values in corresponding direction
if all remaining fractional variables may be rounded without destroying LP feasibility:
- round variable in the objective value direction
binary variables are preferred

Definition at line 561 of file heur_gcgpscostdiving.c.

References calcPscostQuot(), GCGheurGetDivingDataOrig(), and GCG_DivingData::rootsol.

◆ GCGincludeHeurGcgpscostdiving()

SCIP_RETCODE GCGincludeHeurGcgpscostdiving ( SCIP * scip )

creates the gcgpscostdiving heuristic and includes it in GCG

Parameters

scip	SCIP data structure

Definition at line 686 of file heur_gcgpscostdiving.c.

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

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_USEMASTERPSCOSTS

Function Documentation

◆ getRootRelaxSol()

◆ calcMasterPscosts()

◆ areVarsInSameBlock()

◆ calcPscostDownMaster()

◆ calcPscostUpMaster()

◆ calcPscostQuot()

◆ GCG_DECL_DIVINGFREE()

◆ GCG_DECL_DIVINGINIT()

◆ GCG_DECL_DIVINGEXIT()

◆ GCG_DECL_DIVINGINITEXEC()

◆ GCG_DECL_DIVINGEXITEXEC()

◆ GCG_DECL_DIVINGSELECTVAR()

◆ GCGincludeHeurGcgpscostdiving()