Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_gcgzirounding.c File Reference

Detailed Description

zirounding primal heuristic

Author
Gregor Hendel
Christian Puchert

Definition in file heur_gcgzirounding.c.

#include <string.h>
#include "heur_gcgzirounding.h"
#include "gcg.h"
#include "relax_gcg.h"

Go to the source code of this file.

Data Structures

struct  SCIP_HeurData
 

Macros

#define HEUR_NAME   "gcgzirounding"
 
#define HEUR_DESC   "rounding heuristic on original variables as suggested by C. Wallace taking row slacks and bounds into account"
 
#define HEUR_DISPCHAR   'z'
 
#define HEUR_PRIORITY   -500
 
#define HEUR_FREQ   -1 /* / @todo heuristic deactivated due to false solutions */
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE
 
#define HEUR_USESSUBSCIP   FALSE
 
#define DEFAULT_MAXROUNDINGLOOPS   2
 
#define DEFAULT_STOPZIROUND   TRUE
 
#define DEFAULT_STOPPERCENTAGE   0.02
 
#define DEFAULT_MINSTOPNCALLS   1000
 
#define MINSHIFT   1e-4
 

Typedefs

typedef enum Direction DIRECTION
 

Enumerations

enum  Direction {
  DIRECTION_UP = 1,
  DIRECTION_DOWN = -1
}
 

Functions

static SCIP_Real getZiValue (SCIP *scip, SCIP_Real val)
 
static void calculateBounds (SCIP *scip, SCIP_VAR *var, SCIP_Real currentvalue, SCIP_Real *upperbound, SCIP_Real *lowerbound, SCIP_Real *upslacks, SCIP_Real *downslacks, int nslacks, SCIP_Bool *numericalerror)
 
static SCIP_RETCODE updateSlacks (SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real shiftvalue, SCIP_Real *upslacks, SCIP_Real *downslacks, SCIP_Real *activities, SCIP_VAR **slackvars, SCIP_Real *slackcoeffs, int nslacks)
 
static void rowFindSlackVar (SCIP *scip, SCIP_ROW *row, SCIP_VAR **varpointer, SCIP_Real *coeffpointer)
 
static SCIP_DECL_HEURFREE (heurFreeGcgzirounding)
 
static SCIP_DECL_HEURINIT (heurInitGcgzirounding)
 
static SCIP_DECL_HEUREXIT (heurExitGcgzirounding)
 
static SCIP_DECL_HEURINITSOL (heurInitsolGcgzirounding)
 
static SCIP_DECL_HEUREXEC (heurExecGcgzirounding)
 
SCIP_RETCODE SCIPincludeHeurGcgzirounding (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "gcgzirounding"

Definition at line 42 of file heur_gcgzirounding.c.

◆ HEUR_DESC

#define HEUR_DESC   "rounding heuristic on original variables as suggested by C. Wallace taking row slacks and bounds into account"

Definition at line 43 of file heur_gcgzirounding.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'z'

Definition at line 44 of file heur_gcgzirounding.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -500

Definition at line 45 of file heur_gcgzirounding.c.

◆ HEUR_FREQ

#define HEUR_FREQ   -1 /* / @todo heuristic deactivated due to false solutions */

Definition at line 47 of file heur_gcgzirounding.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 48 of file heur_gcgzirounding.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 49 of file heur_gcgzirounding.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 50 of file heur_gcgzirounding.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

Definition at line 51 of file heur_gcgzirounding.c.

◆ DEFAULT_MAXROUNDINGLOOPS

#define DEFAULT_MAXROUNDINGLOOPS   2

delimits the number of main loops, can be set to -1 for no limit

Definition at line 53 of file heur_gcgzirounding.c.

◆ DEFAULT_STOPZIROUND

#define DEFAULT_STOPZIROUND   TRUE

deactivation check is enabled by default

Definition at line 54 of file heur_gcgzirounding.c.

◆ DEFAULT_STOPPERCENTAGE

#define DEFAULT_STOPPERCENTAGE   0.02

the tolerance percentage after which zirounding will not be executed anymore

Definition at line 55 of file heur_gcgzirounding.c.

◆ DEFAULT_MINSTOPNCALLS

#define DEFAULT_MINSTOPNCALLS   1000

number of heuristic calls before deactivation check

Definition at line 56 of file heur_gcgzirounding.c.

◆ MINSHIFT

#define MINSHIFT   1e-4

minimum shift value for every single step

Definition at line 58 of file heur_gcgzirounding.c.

Typedef Documentation

◆ DIRECTION

typedef enum Direction DIRECTION

Definition at line 80 of file heur_gcgzirounding.c.

Enumeration Type Documentation

◆ Direction

enum Direction
Enumerator
DIRECTION_UP 
DIRECTION_DOWN 

Definition at line 75 of file heur_gcgzirounding.c.

Function Documentation

◆ getZiValue()

static SCIP_Real getZiValue ( SCIP *  scip,
SCIP_Real  val 
)
static

returns the fractionality of a value x, which is calculated as zivalue(x) = min(x-floor(x), ceil(x)-x)

Parameters
scippointer to current SCIP data structure
valthe value for which the fractionality should be computed

Definition at line 88 of file heur_gcgzirounding.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ calculateBounds()

static void calculateBounds ( SCIP *  scip,
SCIP_VAR *  var,
SCIP_Real  currentvalue,
SCIP_Real *  upperbound,
SCIP_Real *  lowerbound,
SCIP_Real *  upslacks,
SCIP_Real *  downslacks,
int  nslacks,
SCIP_Bool *  numericalerror 
)
static

determines shifting bounds for variable

Parameters
scippointer to current SCIP data structure
varthe variable for which lb and ub have to be calculated
currentvaluethe current value of var in the working solution
upperboundpointer to store the calculated upper bound on the variable shift
lowerboundpointer to store the calculated lower bound on the variable shift
upslacksarray that contains the slacks between row activities and the right hand sides of the rows
downslacksarray that contains lhs slacks
nslackscurrent number of slacks
numericalerrorflag to determine whether a numerical error occurred

Definition at line 106 of file heur_gcgzirounding.c.

References MINSHIFT.

Referenced by SCIP_DECL_HEUREXEC().

◆ updateSlacks()

static SCIP_RETCODE updateSlacks ( SCIP *  scip,
SCIP_SOL *  sol,
SCIP_VAR *  var,
SCIP_Real  shiftvalue,
SCIP_Real *  upslacks,
SCIP_Real *  downslacks,
SCIP_Real *  activities,
SCIP_VAR **  slackvars,
SCIP_Real *  slackcoeffs,
int  nslacks 
)
static

when a variable is shifted, the activities and slacks of all rows it appears in have to be updated

Parameters
scippointer to current SCIP data structure
solworking solution
varpointer to variable to be modified
shiftvaluethe value by which the variable is shifted
upslacksupslacks of all rows the variable appears in
downslacksdownslacks of all rows the variable appears in
activitiesactivities of the LP rows
slackvarsthe slack variables for equality rows
slackcoeffsthe slack variable coefficients
nslackssize of the arrays

Definition at line 230 of file heur_gcgzirounding.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ rowFindSlackVar()

static void rowFindSlackVar ( SCIP *  scip,
SCIP_ROW *  row,
SCIP_VAR **  varpointer,
SCIP_Real *  coeffpointer 
)
static

finds a continuous slack variable for an equation row, NULL if none exists

Parameters
scippointer to current SCIP data structure
rowthe row for which a slack variable is searched
varpointerpointer to store the slack variable
coeffpointerpointer to store the coefficient of the slack variable

Definition at line 315 of file heur_gcgzirounding.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeGcgzirounding  )
static

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

Definition at line 374 of file heur_gcgzirounding.c.

References HEUR_NAME.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitGcgzirounding  )
static

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

Definition at line 392 of file heur_gcgzirounding.c.

References HEUR_NAME.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitGcgzirounding  )
static

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

Definition at line 409 of file heur_gcgzirounding.c.

References HEUR_NAME.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolGcgzirounding  )
static

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

Definition at line 426 of file heur_gcgzirounding.c.

References HEUR_NAME.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecGcgzirounding  )
static

execution method of primal heuristic

Definition at line 442 of file heur_gcgzirounding.c.

References calculateBounds(), DIRECTION_DOWN, DIRECTION_UP, GCGgetMasterprob(), getZiValue(), HEUR_NAME, MINSHIFT, rowFindSlackVar(), and updateSlacks().

◆ SCIPincludeHeurGcgzirounding()

SCIP_RETCODE SCIPincludeHeurGcgzirounding ( SCIP *  scip)

creates the GCG zirounding primal heuristic and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 878 of file heur_gcgzirounding.c.

References DEFAULT_MAXROUNDINGLOOPS, DEFAULT_MINSTOPNCALLS, DEFAULT_STOPPERCENTAGE, DEFAULT_STOPZIROUND, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, and HEUR_USESSUBSCIP.

Referenced by SCIPincludeGcgPlugins().