Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_gcgguideddiving.c File Reference

Detailed Description

LP diving heuristic that chooses fixings in direction of incumbent solutions.

Author
Tobias Achterberg
Christian Puchert

Definition in file heur_gcgguideddiving.c.

#include <assert.h>
#include <string.h>
#include "heur_gcgguideddiving.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   "gcgguideddiving"
 
#define HEUR_DESC   "LP diving heuristic that chooses fixings in direction of incumbent solutions"
 
#define HEUR_DISPCHAR   'g'
 
#define HEUR_PRIORITY   -1007000
 
#define HEUR_FREQ   10
 
#define HEUR_FREQOFS   7
 
#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 (heurFreeGcgguideddiving)
 
static GCG_DECL_DIVINGINITEXEC (heurInitexecGcgguideddiving)
 
static GCG_DECL_DIVINGEXITEXEC (heurExitexecGcgguideddiving)
 
static GCG_DECL_DIVINGSELECTVAR (heurSelectVarGcgguideddiving)
 
SCIP_RETCODE GCGincludeHeurGcgguideddiving (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "gcgguideddiving"

Definition at line 44 of file heur_gcgguideddiving.c.

◆ HEUR_DESC

#define HEUR_DESC   "LP diving heuristic that chooses fixings in direction of incumbent solutions"

Definition at line 45 of file heur_gcgguideddiving.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'g'

Definition at line 46 of file heur_gcgguideddiving.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1007000

Definition at line 47 of file heur_gcgguideddiving.c.

◆ HEUR_FREQ

#define HEUR_FREQ   10

Definition at line 48 of file heur_gcgguideddiving.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   7

Definition at line 49 of file heur_gcgguideddiving.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 50 of file heur_gcgguideddiving.c.

◆ DEFAULT_USEMASTERFRACS

#define DEFAULT_USEMASTERFRACS   FALSE

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

Definition at line 57 of file heur_gcgguideddiving.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
origvaroriginal variable
mastervarmaster variable

Definition at line 74 of file heur_gcgguideddiving.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
scipSCIP data structure
varoriginal variable to get fractionality for
fracpointer to store fractionality

Definition at line 132 of file heur_gcgguideddiving.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
scipSCIP data structure
varoriginal variable to get fractionality for
fracpointer to store fractionality

Definition at line 202 of file heur_gcgguideddiving.c.

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

Referenced by GCG_DECL_DIVINGSELECTVAR().

◆ GCG_DECL_DIVINGFREE()

static GCG_DECL_DIVINGFREE ( heurFreeGcgguideddiving  )
static

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

Definition at line 275 of file heur_gcgguideddiving.c.

References GCGheurGetDivingDataOrig(), and GCGheurSetDivingDataOrig().

◆ GCG_DECL_DIVINGINITEXEC()

static GCG_DECL_DIVINGINITEXEC ( heurInitexecGcgguideddiving  )
static

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

Definition at line 294 of file heur_gcgguideddiving.c.

References GCG_DivingData::bestsol, and GCGheurGetDivingDataOrig().

◆ GCG_DECL_DIVINGEXITEXEC()

static GCG_DECL_DIVINGEXITEXEC ( heurExitexecGcgguideddiving  )
static

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

Definition at line 313 of file heur_gcgguideddiving.c.

References GCG_DivingData::bestsol, and GCGheurGetDivingDataOrig().

◆ GCG_DECL_DIVINGSELECTVAR()

static GCG_DECL_DIVINGSELECTVAR ( heurSelectVarGcgguideddiving  )
static

variable selection method of diving heuristic; finds best candidate variable w.r.t. the incumbent solution:

  • prefer variables that may not be rounded without destroying LP feasibility:
    • of these variables, round a variable to its value in direction of incumbent solution, and choose the variable that is closest to its rounded value
  • if all remaining fractional variables may be rounded without destroying LP feasibility:
    • round variable in direction that destroys LP feasibility (other direction is checked by SCIProundSol())
    • round variable with least increasing objective value
  • binary variables are prefered
  • variables in a minimal cover or variables that are also fractional in an optimal LP solution might also be prefered if a corresponding parameter is set

Definition at line 343 of file heur_gcgguideddiving.c.

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

◆ GCGincludeHeurGcgguideddiving()

SCIP_RETCODE GCGincludeHeurGcgguideddiving ( SCIP *  scip)

creates the gcgguideddiving heuristic and includes it in GCG

Parameters
scipSCIP data structure

Definition at line 515 of file heur_gcgguideddiving.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().