heur_gcgfracdiving.c File Reference

Detailed Description

LP diving heuristic that chooses fixings w.r.t. the fractionalities.

Author

Tobias Achterberg

Christian Puchert

Definition in file heur_gcgfracdiving.c.

#include <assert.h>
#include <string.h>
#include "heur_gcgfracdiving.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   "gcgfracdiving"
#define	HEUR_DESC   "LP diving heuristic that chooses fixings w.r.t. the fractionalities"
#define	HEUR_DISPCHAR   'f'
#define	HEUR_PRIORITY   -1003000
#define	HEUR_FREQ   10
#define	HEUR_FREQOFS   3
#define	HEUR_MAXDEPTH   -1
#define	DEFAULT_USEMASTERFRACS   FALSE

Functions
static SCIP_Bool	areVarsInSameBlock (SCIP_VAR *origvar, SCIP_VAR *mastervar)
static SCIP_RETCODE	getMasterDownFrac (SCIP *scip, SCIP_VAR *var, SCIP_Real *frac)
static SCIP_RETCODE	getMasterUpFrac (SCIP *scip, SCIP_VAR *var, SCIP_Real *frac)
static	GCG_DECL_DIVINGFREE (heurFreeGcgfracdiving)
static	GCG_DECL_DIVINGSELECTVAR (heurSelectVarGcgfracdiving)
SCIP_RETCODE	GCGincludeHeurGcgfracdiving (SCIP *scip)

Macro Definition Documentation

HEUR_NAME

#define HEUR_NAME   "gcgfracdiving"

Definition at line 44 of file heur_gcgfracdiving.c.

HEUR_DESC

#define HEUR_DESC   "LP diving heuristic that chooses fixings w.r.t. the fractionalities"

Definition at line 45 of file heur_gcgfracdiving.c.

HEUR_DISPCHAR

#define HEUR_DISPCHAR   'f'

Definition at line 46 of file heur_gcgfracdiving.c.

HEUR_PRIORITY

#define HEUR_PRIORITY   -1003000

Definition at line 47 of file heur_gcgfracdiving.c.

HEUR_FREQ

#define HEUR_FREQ   10

Definition at line 48 of file heur_gcgfracdiving.c.

HEUR_FREQOFS

#define HEUR_FREQOFS   3

Definition at line 49 of file heur_gcgfracdiving.c.

HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 50 of file heur_gcgfracdiving.c.

DEFAULT_USEMASTERFRACS

#define DEFAULT_USEMASTERFRACS   FALSE

calculate the fractionalities w.r.t. the master LP?

Definition at line 57 of file heur_gcgfracdiving.c.

Function Documentation

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 73 of file heur_gcgfracdiving.c.

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

Referenced by getMasterDownFrac(), and getMasterUpFrac().

getMasterDownFrac()

static SCIP_RETCODE getMasterDownFrac ( SCIP *  scip, SCIP_VAR *  var, SCIP_Real *  frac  )

static

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

Parameters

scip	SCIP data structure
var	original variable to get fractionality for
frac	pointer to store fractionality

Definition at line 131 of file heur_gcgfracdiving.c.

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

Referenced by GCG_DECL_DIVINGSELECTVAR().

getMasterUpFrac()

static SCIP_RETCODE getMasterUpFrac ( SCIP *  scip, SCIP_VAR *  var, SCIP_Real *  frac  )

static

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

Parameters

scip	SCIP data structure
var	original variable to get fractionality for
frac	pointer to store fractionality

Definition at line 201 of file heur_gcgfracdiving.c.

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

Referenced by GCG_DECL_DIVINGSELECTVAR().

GCG_DECL_DIVINGFREE()

static GCG_DECL_DIVINGFREE ( heurFreeGcgfracdiving  )

static

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

Definition at line 273 of file heur_gcgfracdiving.c.

References GCGheurGetDivingDataOrig(), and GCGheurSetDivingDataOrig().

GCG_DECL_DIVINGSELECTVAR()

static GCG_DECL_DIVINGSELECTVAR ( heurSelectVarGcgfracdiving  )

static

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

• prefer variables that may not be rounded without destroying LP feasibility:
  • of these variables, round least fractional variable in corresponding direction
• if all remaining fractional variables may be rounded without destroying LP feasibility:
  • round variable with least increasing objective value
• binary variables are preferred

Definition at line 299 of file heur_gcgfracdiving.c.

References GCGheurGetDivingDataOrig(), getMasterDownFrac(), getMasterUpFrac(), and GCG_DivingData::usemasterfracs.

GCGincludeHeurGcgfracdiving()

SCIP_RETCODE GCGincludeHeurGcgfracdiving

(

SCIP *

scip

)

creates the gcgfracdiving heuristic and includes it in GCG

Parameters

scip	SCIP data structure

Definition at line 475 of file heur_gcgfracdiving.c.

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

Referenced by SCIPincludeGcgPlugins().