heur_xpcrossover.c File Reference

Detailed Description

Extreme Point Crossover.

Author
Christian Puchert

Definition in file heur_xpcrossover.c.

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

Go to the source code of this file.

Macros

#define HEUR_NAME   "xpcrossover"
 
#define HEUR_DESC   "Extreme Point Crossover"
 
#define HEUR_DISPCHAR   'X'
 
#define HEUR_PRIORITY   -1100500
 
#define HEUR_FREQ   0
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE
 
#define HEUR_USESSUBSCIP   TRUE
 
#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   4
 
#define DEFAULT_RANDOMIZATION   FALSE
 
#define DEFAULT_COPYCUTS   TRUE
 
#define DEFAULT_RANDSEED   7 /* initial random seed */
 
#define HASHSIZE_POINTS   11113
 

Typedefs

typedef struct PointTuple POINTTUPLE
 

Functions

static SCIP_DECL_HASHGETKEY (hashGetKeyPts)
 
static SCIP_DECL_HASHKEYEQ (hashKeyEqPts)
 
static SCIP_DECL_HASHKEYVAL (hashKeyValPts)
 
static unsigned int calculateHashKey (int *indices, int size)
 
static SCIP_RETCODE createPtTuple (SCIP *scip, POINTTUPLE **elem, int *indices, int size, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE selectExtremePoints (SCIP *scip, SCIP_HEURDATA *heurdata, int *selection, SCIP_Bool *success)
 
static SCIP_RETCODE selectExtremePointsRandomized (SCIP *scip, SCIP_HEURDATA *heurdata, int *selection, SCIP_Bool *success)
 
static SCIP_RETCODE setupSubproblem (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata, SCIP_Longint nstallnodes, SCIP_Real timelimit, SCIP_Real memorylimit)
 
static SCIP_RETCODE fixVariables (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, int *selection, 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 (heurFreeXpcrossover)
 
static SCIP_DECL_HEURINIT (heurInitXpcrossover)
 
static SCIP_DECL_HEUREXIT (heurExitXpcrossover)
 
static SCIP_DECL_HEUREXEC (heurExecXpcrossover)
 
SCIP_RETCODE SCIPincludeHeurXpcrossover (SCIP *scip)
 

Macro Definition Documentation

#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 65 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define DEFAULT_MAXNODES   1000LL

maximum number of nodes to regard in the subproblem

Definition at line 57 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define DEFAULT_MINFIXINGRATE   0.4

minimum percentage of integer variables that have to be fixed

Definition at line 60 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define DEFAULT_MINIMPROVE   0.01

factor by which crossover should at least improve the incumbent

Definition at line 58 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define DEFAULT_MINNODES   200LL

minimum number of nodes to regard in the subproblem

Definition at line 59 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define DEFAULT_NODESOFS   200LL

number of nodes added to the contingent of the total nodes

Definition at line 61 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define DEFAULT_NODESQUOT   0.1

subproblem nodes in relation to nodes of the original problem

Definition at line 62 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define DEFAULT_NUSEDPTS   4

number of extreme pts per block that will be taken into account

Definition at line 63 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define DEFAULT_RANDOMIZATION   FALSE

should the choice which sols to take be randomized?

Definition at line 64 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define DEFAULT_RANDSEED   7 /* initial random seed */

Definition at line 70 of file heur_xpcrossover.c.

#define HASHSIZE_POINTS   11113

size of hash table for extreme point tuples

Definition at line 72 of file heur_xpcrossover.c.

#define HEUR_DESC   "Extreme Point Crossover"

Definition at line 48 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define HEUR_DISPCHAR   'X'

Definition at line 49 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define HEUR_FREQ   0

Definition at line 51 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define HEUR_FREQOFS   0

Definition at line 52 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define HEUR_MAXDEPTH   -1

Definition at line 53 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define HEUR_NAME   "xpcrossover"

Definition at line 47 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define HEUR_PRIORITY   -1100500

Definition at line 50 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 54 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

#define HEUR_USESSUBSCIP   TRUE

Definition at line 55 of file heur_xpcrossover.c.

Referenced by SCIPincludeHeurXpcrossover().

Typedef Documentation

typedef struct PointTuple POINTTUPLE

Definition at line 80 of file heur_xpcrossover.c.

Function Documentation

static unsigned int calculateHashKey ( int *  indices,
int  size 
)
static

calculates a hash key for a given tuple of master variable indices

Parameters
indicesindices of master variables
sizenumber of master variables

Definition at line 182 of file heur_xpcrossover.c.

References createPtTuple().

Referenced by createPtTuple().

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 1204 of file heur_xpcrossover.c.

References updateFailureStatistic(), and SCIP_HeurData::vars.

Referenced by fixVariables().

static SCIP_RETCODE createPtTuple ( SCIP *  scip,
POINTTUPLE **  elem,
int *  indices,
int  size,
SCIP_HEURDATA *  heurdata 
)
static

creates a new tuple of extreme points (= mastervars)

Parameters
sciporiginal SCIP data structure
elemtuple of master variables which should be created
indicesindices of master variables
sizenumber of master variables
heurdataprimal heuristic data

Definition at line 203 of file heur_xpcrossover.c.

References calculateHashKey(), and selectExtremePoints().

Referenced by calculateHashKey(), selectExtremePoints(), and selectExtremePointsRandomized().

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

fix those variables which are identical in each extreme point of their blocks

Todo:
can there be aggregated linking variables?
Parameters
sciporiginal SCIP data structure
subscipSCIP data structure for the subproblem
subvarsthe variables of the subproblem
selectionselected extreme points the heuristic will use
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 841 of file heur_xpcrossover.c.

References createNewSol(), GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), GCGlinkingVarGetNBlocks(), GCGlinkingVarGetPricingVars(), GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), GCGmasterVarGetOrigvars(), GCGoriginalVarGetPricingVar(), GCGoriginalVarIsLinking(), GCGpricingVarGetNOrigvars(), GCGpricingVarGetOrigvars(), GCGvarGetBlock(), GCGvarIsOriginal(), GCGvarIsPricing(), SCIP_HeurData::minfixingrate, SCIP_HeurData::nusedpts, and SCIP_HeurData::vars.

Referenced by setupSubproblem().

static SCIP_DECL_HASHGETKEY ( hashGetKeyPts  )
static

gets the hash key of an extreme point tuple

Definition at line 135 of file heur_xpcrossover.c.

static SCIP_DECL_HASHKEYEQ ( hashKeyEqPts  )
static

returns TRUE iff both extreme point tuples are identical

Definition at line 143 of file heur_xpcrossover.c.

static SCIP_DECL_HASHKEYVAL ( hashKeyValPts  )
static

returns hashkey of an extreme point tuple

Definition at line 174 of file heur_xpcrossover.c.

static SCIP_DECL_HEUREXEC ( heurExecXpcrossover  )
static

execution method of primal heuristic

Definition at line 1440 of file heur_xpcrossover.c.

static SCIP_DECL_HEUREXIT ( heurExitXpcrossover  )
static

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

Definition at line 1338 of file heur_xpcrossover.c.

static SCIP_DECL_HEURFREE ( heurFreeXpcrossover  )
static

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

Definition at line 1287 of file heur_xpcrossover.c.

Referenced by updateFailureStatistic().

static SCIP_DECL_HEURINIT ( heurInitXpcrossover  )
static

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

Definition at line 1307 of file heur_xpcrossover.c.

SCIP_RETCODE SCIPincludeHeurXpcrossover ( SCIP *  scip)

creates the Extreme Point Crossover primal heuristic and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 1727 of file heur_xpcrossover.c.

References DEFAULT_COPYCUTS, DEFAULT_MAXNODES, DEFAULT_MINFIXINGRATE, DEFAULT_MINIMPROVE, DEFAULT_MINNODES, DEFAULT_NODESOFS, DEFAULT_NODESQUOT, DEFAULT_NUSEDPTS, DEFAULT_RANDOMIZATION, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, and HEUR_USESSUBSCIP.

Referenced by SCIPincludeGcgPlugins().

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

for each block, select extreme points (represented by mastervars) to be crossed

Todo:
handle infinite master solution values
Todo:
handle infinite master solution values
Parameters
sciporiginal SCIP data structure
heurdataprimal heuristic data
selectionindices of selected extreme points
successpointer to store whether the process was successful

Definition at line 230 of file heur_xpcrossover.c.

References createPtTuple(), GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNIdenticalBlocks(), GCGgetNPricingprobs(), GCGmasterVarIsRay(), GCGvarGetBlock(), GCGvarIsMaster(), SCIP_HeurData::nusedpts, and selectExtremePointsRandomized().

Referenced by createPtTuple().

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

select extreme points (represented by mastervars) to be crossed randomly

Parameters
sciporiginal SCIP data structure
heurdataprimal heuristic data
selectionindices of selected extreme points
successpointer to store whether the process was successful

Definition at line 472 of file heur_xpcrossover.c.

References createPtTuple(), GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), GCGisPricingprobRelevant(), GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), GCGmasterVarGetOrigvars(), GCGrelaxGetCurrentOrigSol(), GCGvarGetBlock(), GCGvarIsMaster(), SCIP_HeurData::nusedpts, and setupSubproblem().

Referenced by selectExtremePoints().

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 713 of file heur_xpcrossover.c.

References fixVariables(), and SCIP_HeurData::vars.

Referenced by selectExtremePointsRandomized().

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 1268 of file heur_xpcrossover.c.

References SCIP_DECL_HEURFREE().

Referenced by createNewSol().