Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_xprins.c File Reference

Detailed Description

Extreme Point RINS.

Author
Christian Puchert

Definition in file heur_xprins.c.

#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "heur_xprins.h"
#include "gcg.h"
#include "scip/scip.h"
#include "scip/misc.h"
#include "scip/scipdefplugins.h"

Go to the source code of this file.

Data Structures

struct  SCIP_HeurData
 

Macros

#define HEUR_NAME   "xprins"
 
#define HEUR_DESC   "Extreme Point RINS"
 
#define HEUR_DISPCHAR   'Y'
 
#define HEUR_PRIORITY   -1100600
 
#define HEUR_FREQ   0
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE
 
#define HEUR_USESSUBSCIP   TRUE
 
#define DEFAULT_EQUALITYRATE   0.5
 
#define DEFAULT_MAXNODES   1000LL
 
#define DEFAULT_MINIMPROVE   0.01
 
#define DEFAULT_MINNODES   200LL
 
#define DEFAULT_MINFIXINGRATE   0.4
 
#define DEFAULT_NODESOFS   200LL
 
#define DEFAULT_NODESQUOT   0.1
 
#define DEFAULT_NUSEDPTS   -1
 
#define DEFAULT_RANDOMIZATION   FALSE
 
#define DEFAULT_COPYCUTS   TRUE
 
#define DEFAULT_RANDSEED   7
 

Functions

static SCIP_RETCODE selectExtremePoints (SCIP *scip, SCIP_HEURDATA *heurdata, int *selection, int *nactualpts, SCIP_Bool *success)
 
static SCIP_RETCODE selectExtremePointsRandomized (SCIP *scip, SCIP_HEURDATA *heurdata, int *selection, int *nactualpts, SCIP_Bool *success)
 
static SCIP_RETCODE countExtremePoints (SCIP *scip, int *selection, int nusedpts, int *nactualpts)
 
static SCIP_RETCODE setupSubproblem (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata, SCIP_Longint nstallnodes, SCIP_Real timelimit, SCIP_Real memorylimit)
 
static void compareOneExtremePoint (SCIP *scip, SCIP_VAR *mastervar, int solblock, int *neqpts, SCIP_Bool *zeroblocks)
 
static SCIP_RETCODE compareExtremePointsToRelaxSol (SCIP *scip, int *selection, int nusedpts, int *neqpts, SCIP_Bool *zeroblocks)
 
static SCIP_RETCODE fixVariables (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, int *selection, int *nactualpts, SCIP_HEURDATA *heurdata, SCIP_Real *intfixingrate, SCIP_Real *zerofixingrate, SCIP_Bool *success)
 
static SCIP_RETCODE createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
 
static void updateFailureStatistic (SCIP *scip, SCIP_HEURDATA *heurdata)
 
static SCIP_DECL_HEURFREE (heurFreeXprins)
 
static SCIP_DECL_HEURINIT (heurInitXprins)
 
static SCIP_DECL_HEUREXIT (heurExitXprins)
 
static SCIP_DECL_HEUREXEC (heurExecXprins)
 
SCIP_RETCODE SCIPincludeHeurXprins (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "xprins"

Definition at line 47 of file heur_xprins.c.

◆ HEUR_DESC

#define HEUR_DESC   "Extreme Point RINS"

Definition at line 48 of file heur_xprins.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'Y'

Definition at line 49 of file heur_xprins.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1100600

Definition at line 50 of file heur_xprins.c.

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 51 of file heur_xprins.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 52 of file heur_xprins.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 53 of file heur_xprins.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 54 of file heur_xprins.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   TRUE

Definition at line 55 of file heur_xprins.c.

◆ DEFAULT_EQUALITYRATE

#define DEFAULT_EQUALITYRATE   0.5

minimum percentage of coincidence of relaxation and extreme pts

Definition at line 57 of file heur_xprins.c.

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   1000LL

maximum number of nodes to regard in the subproblem

Definition at line 58 of file heur_xprins.c.

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE   0.01

factor by which xprins should at least improve the incumbent

Definition at line 59 of file heur_xprins.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   200LL

minimum number of nodes to regard in the subproblem

Definition at line 60 of file heur_xprins.c.

◆ DEFAULT_MINFIXINGRATE

#define DEFAULT_MINFIXINGRATE   0.4

minimum percentage of integer variables that have to be fixed

Definition at line 61 of file heur_xprins.c.

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS   200LL

number of nodes added to the contingent of the total nodes

Definition at line 62 of file heur_xprins.c.

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT   0.1

subproblem nodes in relation to nodes of the original problem

Definition at line 63 of file heur_xprins.c.

◆ DEFAULT_NUSEDPTS

#define DEFAULT_NUSEDPTS   -1

number of extreme pts per block that will be taken into account (-1: all; 0: all which contribute to current relaxation solution)

Definition at line 64 of file heur_xprins.c.

◆ DEFAULT_RANDOMIZATION

#define DEFAULT_RANDOMIZATION   FALSE

should the choice which sols to take be randomized?

Definition at line 67 of file heur_xprins.c.

◆ DEFAULT_COPYCUTS

#define DEFAULT_COPYCUTS   TRUE

if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool of the original scip be copied to constraints of the subscip

Definition at line 68 of file heur_xprins.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   7

initial random seed

Definition at line 71 of file heur_xprins.c.

Function Documentation

◆ selectExtremePoints()

static SCIP_RETCODE selectExtremePoints ( SCIP *  scip,
SCIP_HEURDATA *  heurdata,
int *  selection,
int *  nactualpts,
SCIP_Bool *  success 
)
static

for each block, select extreme points (represented by mastervars) to be compared to the relaxation solution

Parameters
sciporiginal SCIP data structure
heurdataprimal heuristic data
selectionindices of selected extreme points
nactualptsnumber of points per block that have actually been selected
successpointer to store whether the process was successful

Definition at line 123 of file heur_xprins.c.

References GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNIdenticalBlocks(), GCGgetNPricingprobs(), GCGmasterVarIsRay(), GCGvarGetBlock(), and GCGvarIsMaster().

Referenced by SCIP_DECL_HEUREXEC().

◆ selectExtremePointsRandomized()

static SCIP_RETCODE selectExtremePointsRandomized ( SCIP *  scip,
SCIP_HEURDATA *  heurdata,
int *  selection,
int *  nactualpts,
SCIP_Bool *  success 
)
static

select extreme points (represented by mastervars) randomly

Parameters
sciporiginal SCIP data structure
heurdataprimal heuristic data
selectionindices of selected extreme points
nactualptsnumber of points per block that have actually been selected
successpointer to store whether the process was successful

Definition at line 362 of file heur_xprins.c.

References GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), GCGisPricingprobRelevant(), and GCGvarGetBlock().

Referenced by SCIP_DECL_HEUREXEC().

◆ countExtremePoints()

static SCIP_RETCODE countExtremePoints ( SCIP *  scip,
int *  selection,
int  nusedpts,
int *  nactualpts 
)
static
Parameters
sciporiginal SCIP data structure
selectionselected extreme points the heuristic will use, or NULL
nusedptsnumber of extreme points per block to be considered, or 0, or -1
nactualptsnumber of points per block that have actually been selected

Definition at line 515 of file heur_xprins.c.

References GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), and GCGvarGetBlock().

Referenced by SCIP_DECL_HEUREXEC().

◆ setupSubproblem()

static SCIP_RETCODE setupSubproblem ( SCIP *  scip,
SCIP *  subscip,
SCIP_VAR **  subvars,
SCIP_HEURDATA *  heurdata,
SCIP_Longint  nstallnodes,
SCIP_Real  timelimit,
SCIP_Real  memorylimit 
)
static

initialize the subSCIP instance: copy SCIP to subSCIP, set the parameters

Parameters
sciporiginal SCIP data structure
subscipSCIP data structure for the subproblem
subvarsthe variables of the subproblem
heurdataprimal heuristic data
nstallnodesnode limit for subproblem
timelimittime limit for subproblem
memorylimitmemory limit for subproblem

Definition at line 572 of file heur_xprins.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ compareOneExtremePoint()

static void compareOneExtremePoint ( SCIP *  scip,
SCIP_VAR *  mastervar,
int  solblock,
int *  neqpts,
SCIP_Bool *  zeroblocks 
)
static

compare an extreme point (represented by a master variable) to the relaxation solution

Parameters
sciporiginal SCIP data structure
mastervarmaster variable representing the extreme point
solblockblock in which the relaxation solution should be compared, or -1 if all blocks of the extreme point should be considered
neqptsfor each original variable, count how many extreme points share its relaxation solution value
zeroblocksfor each block, the information whether it would be fixed entirely to zero

Definition at line 703 of file heur_xprins.c.

References GCGgetNPricingprobs(), GCGisLinkingVarInBlock(), GCGlinkingVarGetPricingVars(), GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), GCGmasterVarGetOrigvars(), GCGoriginalVarGetPricingVar(), GCGoriginalVarIsLinking(), GCGpricingVarGetNOrigvars(), GCGpricingVarGetOrigvars(), GCGvarGetBlock(), GCGvarIsMaster(), and GCGvarIsPricing().

Referenced by compareExtremePointsToRelaxSol().

◆ compareExtremePointsToRelaxSol()

static SCIP_RETCODE compareExtremePointsToRelaxSol ( SCIP *  scip,
int *  selection,
int  nusedpts,
int *  neqpts,
SCIP_Bool *  zeroblocks 
)
static

compare all selected extreme points to the relaxation solution

Parameters
sciporiginal SCIP data structure
selectionselected extreme points the heuristic will use, or NULL
nusedptsnumber of extreme points per block to be considered, or 0, or -1
neqptsfor each original variable, count how many extreme points share its relaxation solution value
zeroblocksfor each block, the information whether it would be fixed entirely to zero

Definition at line 817 of file heur_xprins.c.

References compareOneExtremePoint(), GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), and GCGvarGetBlock().

Referenced by fixVariables().

◆ fixVariables()

static SCIP_RETCODE fixVariables ( SCIP *  scip,
SCIP *  subscip,
SCIP_VAR **  subvars,
int *  selection,
int *  nactualpts,
SCIP_HEURDATA *  heurdata,
SCIP_Real *  intfixingrate,
SCIP_Real *  zerofixingrate,
SCIP_Bool *  success 
)
static

fix variables; for each variable, we evaluate the percentage of extreme points in which it has the same value as in the relaxation solution and fix it if the percentage exceeds a certain value

Parameters
sciporiginal SCIP data structure
subscipSCIP data structure for the subproblem
subvarsthe variables of the subproblem
selectionselected extreme points the heuristic will use, or NULL
nactualptsnumber of points per block that have actually been selected
heurdataprimal heuristic data
intfixingratepercentage of integers that get actually fixed
zerofixingratepercentage of variables fixed to zero
successpointer to store whether the problem was created successfully

Definition at line 896 of file heur_xprins.c.

References compareExtremePointsToRelaxSol(), GCGgetNPricingprobs(), GCGlinkingVarGetPricingVars(), GCGoriginalVarIsLinking(), GCGvarGetBlock(), and GCGvarIsOriginal().

Referenced by SCIP_DECL_HEUREXEC().

◆ createNewSol()

static SCIP_RETCODE createNewSol ( SCIP *  scip,
SCIP *  subscip,
SCIP_VAR **  subvars,
SCIP_HEUR *  heur,
SCIP_SOL *  subsol,
SCIP_Bool *  success 
)
static

creates a new solution for the original problem by copying the solution of the subproblem

Parameters
sciporiginal SCIP data structure
subscipSCIP structure of the subproblem
subvarsthe variables of the subproblem
heurprimal heuristic structure
subsolsolution of the subproblem
successused to store whether new solution was found or not

Definition at line 1136 of file heur_xprins.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ updateFailureStatistic()

static void updateFailureStatistic ( SCIP *  scip,
SCIP_HEURDATA *  heurdata 
)
static

updates heurdata after a run of crossover

Parameters
sciporiginal SCIP data structure
heurdataprimal heuristic data

Definition at line 1203 of file heur_xprins.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeXprins  )
static

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

Definition at line 1223 of file heur_xprins.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitXprins  )
static

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

Definition at line 1243 of file heur_xprins.c.

References DEFAULT_RANDSEED.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitXprins  )
static

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

Definition at line 1268 of file heur_xprins.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecXprins  )
static

◆ SCIPincludeHeurXprins()

SCIP_RETCODE SCIPincludeHeurXprins ( SCIP *  scip)