Detailed Description

Extreme Point Crossover.

Author: Christian Puchert

#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.

Data Structures
struct	SCIP_HeurData

struct	PointTuple

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

#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

◆ HEUR_NAME

#define HEUR_NAME "xpcrossover"

Definition at line 47 of file heur_xpcrossover.c.

◆ HEUR_DESC

#define HEUR_DESC "Extreme Point Crossover"

Definition at line 48 of file heur_xpcrossover.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'X'

Definition at line 49 of file heur_xpcrossover.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -1100500

Definition at line 50 of file heur_xpcrossover.c.

◆ HEUR_FREQ

#define HEUR_FREQ 0

Definition at line 51 of file heur_xpcrossover.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 52 of file heur_xpcrossover.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 53 of file heur_xpcrossover.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE

Definition at line 54 of file heur_xpcrossover.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP TRUE

Definition at line 55 of file heur_xpcrossover.c.

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES 1000LL

maximum number of nodes to regard in the subproblem

Definition at line 57 of file heur_xpcrossover.c.

◆ DEFAULT_MINIMPROVE

#define DEFAULT_MINIMPROVE 0.01

factor by which crossover should at least improve the incumbent

Definition at line 58 of file heur_xpcrossover.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES 200LL

minimum number of nodes to regard in the subproblem

Definition at line 59 of file heur_xpcrossover.c.

◆ DEFAULT_MINFIXINGRATE

#define DEFAULT_MINFIXINGRATE 0.4

minimum percentage of integer variables that have to be fixed

Definition at line 60 of file heur_xpcrossover.c.

◆ DEFAULT_NODESOFS

#define DEFAULT_NODESOFS 200LL

number of nodes added to the contingent of the total nodes

Definition at line 61 of file heur_xpcrossover.c.

◆ DEFAULT_NODESQUOT

#define DEFAULT_NODESQUOT 0.1

subproblem nodes in relation to nodes of the original problem

Definition at line 62 of file heur_xpcrossover.c.

◆ DEFAULT_NUSEDPTS

#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.

◆ DEFAULT_RANDOMIZATION

#define DEFAULT_RANDOMIZATION FALSE

should the choice which sols to take be randomized?

Definition at line 64 of file heur_xpcrossover.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 65 of file heur_xpcrossover.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 7

initial random seed

Definition at line 68 of file heur_xpcrossover.c.

◆ HASHSIZE_POINTS

#define HASHSIZE_POINTS 11113

size of hash table for extreme point tuples

Definition at line 70 of file heur_xpcrossover.c.

Typedef Documentation

◆ POINTTUPLE

typedef struct PointTuple POINTTUPLE

Definition at line 78 of file heur_xpcrossover.c.

Function Documentation

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( hashGetKeyPts )

static

gets the hash key of an extreme point tuple

Definition at line 133 of file heur_xpcrossover.c.

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashKeyEqPts )

static

returns TRUE iff both extreme point tuples are identical

Definition at line 141 of file heur_xpcrossover.c.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashKeyValPts )

static

returns hashkey of an extreme point tuple

Definition at line 172 of file heur_xpcrossover.c.

◆ calculateHashKey()

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

static

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

Parameters

indices	indices of master variables
size	number of master variables

Definition at line 180 of file heur_xpcrossover.c.

Referenced by createPtTuple().

◆ createPtTuple()

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

scip	original SCIP data structure
elem	tuple of master variables which should be created
indices	indices of master variables
size	number of master variables
heurdata	primal heuristic data

Definition at line 201 of file heur_xpcrossover.c.

References calculateHashKey().

Referenced by selectExtremePoints(), and selectExtremePointsRandomized().

◆ selectExtremePoints()

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

Parameters

scip	original SCIP data structure
heurdata	primal heuristic data
selection	indices of selected extreme points
success	pointer to store whether the process was successful

Definition at line 228 of file heur_xpcrossover.c.

References createPtTuple(), 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,
		SCIP_Bool *	success
	)

static

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

Parameters

scip	original SCIP data structure
heurdata	primal heuristic data
selection	indices of selected extreme points
success	pointer to store whether the process was successful

Definition at line 470 of file heur_xpcrossover.c.

References createPtTuple(), GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), GCGisPricingprobRelevant(), 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

scip	original SCIP data structure
subscip	SCIP data structure for the subproblem
subvars	the variables of the subproblem
heurdata	primal heuristic data
nstallnodes	node limit for subproblem
timelimit	time limit for subproblem
memorylimit	memory limit for subproblem

Definition at line 711 of file heur_xpcrossover.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ fixVariables()

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

Parameters

scip	original SCIP data structure
subscip	SCIP data structure for the subproblem
subvars	the variables of the subproblem
selection	selected extreme points the heuristic will use
heurdata	primal heuristic data
intfixingrate	percentage of integers that get actually fixed
zerofixingrate	percentage of variables fixed to zero
success	pointer to store whether the problem was created successfully

Definition at line 839 of file heur_xpcrossover.c.

References GCGgetBlockRepresentative(), GCGgetMasterprob(), GCGgetNPricingprobs(), GCGlinkingVarGetNBlocks(), GCGlinkingVarGetPricingVars(), GCGmasterVarGetNOrigvars(), GCGmasterVarGetOrigvals(), GCGmasterVarGetOrigvars(), GCGoriginalVarGetPricingVar(), GCGoriginalVarIsLinking(), GCGpricingVarGetNOrigvars(), GCGpricingVarGetOrigvars(), GCGvarGetBlock(), GCGvarIsOriginal(), and GCGvarIsPricing().

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

scip	original SCIP data structure
subscip	SCIP structure of the subproblem
subvars	the variables of the subproblem
heur	primal heuristic structure
subsol	solution of the subproblem
success	used to store whether new solution was found or not

Definition at line 1202 of file heur_xpcrossover.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ updateFailureStatistic()

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

static

updates heurdata after a run of crossover

Parameters

scip	original SCIP data structure
heurdata	primal heuristic data

Definition at line 1266 of file heur_xpcrossover.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeXpcrossover )

static

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

Definition at line 1285 of file heur_xpcrossover.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitXpcrossover )

static

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

Definition at line 1305 of file heur_xpcrossover.c.

References DEFAULT_RANDSEED, and HASHSIZE_POINTS.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitXpcrossover )

static

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

Definition at line 1336 of file heur_xpcrossover.c.

References PointTuple::indices, PointTuple::prev, and PointTuple::size.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecXpcrossover )

static

execution method of primal heuristic

Definition at line 1438 of file heur_xpcrossover.c.

References createNewSol(), fixVariables(), GCGgetMasterprob(), GCGgetNPricingprobs(), HEUR_NAME, selectExtremePoints(), selectExtremePointsRandomized(), setupSubproblem(), and updateFailureStatistic().

◆ SCIPincludeHeurXpcrossover()

SCIP_RETCODE SCIPincludeHeurXpcrossover ( SCIP * scip )

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

Parameters

scip	SCIP data structure

Definition at line 1725 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().

GCG

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXNODES

◆ DEFAULT_MINIMPROVE

◆ DEFAULT_MINNODES

◆ DEFAULT_MINFIXINGRATE

◆ DEFAULT_NODESOFS

◆ DEFAULT_NODESQUOT

◆ DEFAULT_NUSEDPTS

◆ DEFAULT_RANDOMIZATION

◆ DEFAULT_COPYCUTS

◆ DEFAULT_RANDSEED

◆ HASHSIZE_POINTS

Typedef Documentation

◆ POINTTUPLE

Function Documentation

◆ SCIP_DECL_HASHGETKEY()

◆ SCIP_DECL_HASHKEYEQ()

◆ SCIP_DECL_HASHKEYVAL()

◆ calculateHashKey()

◆ createPtTuple()

◆ selectExtremePoints()

◆ selectExtremePointsRandomized()

◆ setupSubproblem()

◆ fixVariables()

◆ createNewSol()

◆ updateFailureStatistic()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPincludeHeurXpcrossover()