Detailed Description
Extreme Point Crossover.
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.
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 |
gets the hash key of an extreme point tuple
Definition at line 133 of file heur_xpcrossover.c.
◆ SCIP_DECL_HASHKEYEQ()
|
static |
returns TRUE iff both extreme point tuples are identical
Definition at line 141 of file heur_xpcrossover.c.
◆ SCIP_DECL_HASHKEYVAL()
|
static |
returns hashkey of an extreme point tuple
Definition at line 172 of file heur_xpcrossover.c.
◆ calculateHashKey()
|
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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().