Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_greedycolsel.c File Reference

Detailed Description

greedy column selection primal heuristic

Author
Christian Puchert

Definition in file heur_greedycolsel.c.

#include <assert.h>
#include "heur_greedycolsel.h"
#include "gcg.h"
#include "pricer_gcg.h"

Go to the source code of this file.

Data Structures

struct  SCIP_HeurData
 

Macros

#define HEUR_NAME   "greedycolsel"
 
#define HEUR_DESC   "greedy column selection heuristic"
 
#define HEUR_DISPCHAR   'e'
 
#define HEUR_PRIORITY   0
 
#define HEUR_FREQ   1
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_DURINGPRICINGLOOP
 
#define HEUR_USESSUBSCIP   FALSE
 
#define DEFAULT_MINCOLUMNS   200
 
#define DEFAULT_USEOBJ   FALSE
 
#define heurCopyGreedycolsel   NULL
 
#define heurInitsolGreedycolsel   NULL
 
#define heurExitsolGreedycolsel   NULL
 

Functions

static int getViolationChange (SCIP *scip, SCIP_Real *activities, SCIP_VAR *mastervar)
 
static SCIP_RETCODE getBestMastervar (SCIP *scip, SCIP_SOL *mastersol, SCIP_Real *activities, int *blocknr, SCIP_Bool *ignored, SCIP_Bool useobj, int *index, int *violchange)
 
static SCIP_RETCODE updateActivities (SCIP *scip, SCIP_Real *activities, SCIP_VAR *mastervar)
 
static SCIP_RETCODE searchZeroMastervar (SCIP *scip, int block, SCIP_VAR **zeromastervar)
 
static SCIP_RETCODE getZeroMastervar (SCIP *scip, SCIP_HEURDATA *heurdata, int block, SCIP_VAR **zeromastervar)
 
static SCIP_DECL_HEURFREE (heurFreeGreedycolsel)
 
static SCIP_DECL_HEURINIT (heurInitGreedycolsel)
 
static SCIP_DECL_HEUREXIT (heurExitGreedycolsel)
 
static SCIP_DECL_HEUREXEC (heurExecGreedycolsel)
 
SCIP_RETCODE SCIPincludeHeurGreedycolsel (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "greedycolsel"

Definition at line 42 of file heur_greedycolsel.c.

◆ HEUR_DESC

#define HEUR_DESC   "greedy column selection heuristic"

Definition at line 43 of file heur_greedycolsel.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'e'

Definition at line 44 of file heur_greedycolsel.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   0

Definition at line 45 of file heur_greedycolsel.c.

◆ HEUR_FREQ

#define HEUR_FREQ   1

Definition at line 46 of file heur_greedycolsel.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 47 of file heur_greedycolsel.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 48 of file heur_greedycolsel.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_DURINGPRICINGLOOP

Definition at line 50 of file heur_greedycolsel.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

Definition at line 51 of file heur_greedycolsel.c.

◆ DEFAULT_MINCOLUMNS

#define DEFAULT_MINCOLUMNS   200

minimum number of columns to regard in the master problem

Definition at line 53 of file heur_greedycolsel.c.

◆ DEFAULT_USEOBJ

#define DEFAULT_USEOBJ   FALSE

use objective coefficients as tie breakers

Definition at line 54 of file heur_greedycolsel.c.

◆ heurCopyGreedycolsel

#define heurCopyGreedycolsel   NULL

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 341 of file heur_greedycolsel.c.

◆ heurInitsolGreedycolsel

#define heurInitsolGreedycolsel   NULL

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 425 of file heur_greedycolsel.c.

◆ heurExitsolGreedycolsel

#define heurExitsolGreedycolsel   NULL

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 429 of file heur_greedycolsel.c.

Function Documentation

◆ getViolationChange()

static int getViolationChange ( SCIP *  scip,
SCIP_Real *  activities,
SCIP_VAR *  mastervar 
)
static

how would the number of violated rows change if mastervar were increased?

Definition at line 86 of file heur_greedycolsel.c.

Referenced by getBestMastervar().

◆ getBestMastervar()

static SCIP_RETCODE getBestMastervar ( SCIP *  scip,
SCIP_SOL *  mastersol,
SCIP_Real *  activities,
int *  blocknr,
SCIP_Bool *  ignored,
SCIP_Bool  useobj,
int *  index,
int *  violchange 
)
static

get the index of the "best" master variable w.r.t. pseudo costs

Definition at line 143 of file heur_greedycolsel.c.

References GCGgetNIdenticalBlocks(), GCGmasterGetOrigprob(), GCGmasterVarIsRay(), GCGvarGetBlock(), GCGvarIsMaster(), and getViolationChange().

Referenced by SCIP_DECL_HEUREXEC().

◆ updateActivities()

static SCIP_RETCODE updateActivities ( SCIP *  scip,
SCIP_Real *  activities,
SCIP_VAR *  mastervar 
)
static

update activities

Definition at line 217 of file heur_greedycolsel.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ searchZeroMastervar()

static SCIP_RETCODE searchZeroMastervar ( SCIP *  scip,
int  block,
SCIP_VAR **  zeromastervar 
)
static

for a given block, search if there is a master variable corresponding to the zero solution;

Definition at line 269 of file heur_greedycolsel.c.

References GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), and GCGvarGetBlock().

Referenced by getZeroMastervar().

◆ getZeroMastervar()

static SCIP_RETCODE getZeroMastervar ( SCIP *  scip,
SCIP_HEURDATA *  heurdata,
int  block,
SCIP_VAR **  zeromastervar 
)
static

for a given block, return the master variable corresponding to the zero solution, or NULL is there is no such variable available

Definition at line 315 of file heur_greedycolsel.c.

References searchZeroMastervar().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeGreedycolsel  )
static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 345 of file heur_greedycolsel.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitGreedycolsel  )
static

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

Definition at line 366 of file heur_greedycolsel.c.

References GCGgetNPricingprobs(), and GCGmasterGetOrigprob().

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitGreedycolsel  )
static

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

Definition at line 406 of file heur_greedycolsel.c.

◆ SCIP_DECL_HEUREXEC()

◆ SCIPincludeHeurGreedycolsel()

SCIP_RETCODE SCIPincludeHeurGreedycolsel ( SCIP *  scip)

creates the greedy column selection primal heuristic and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 801 of file heur_greedycolsel.c.

References DEFAULT_MINCOLUMNS, DEFAULT_USEOBJ, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, heurCopyGreedycolsel, heurExitsolGreedycolsel, and heurInitsolGreedycolsel.

Referenced by GCGincludeMasterPlugins().