Detailed Description
crossover primal heuristic
Definition in file heur_crossover.c.
#include "blockmemshell/memory.h"
#include "scip/heur_crossover.h"
#include "scip/heuristics.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "crossover" |
#define | HEUR_DESC "LNS heuristic that fixes all variables that are identic in a couple of solutions" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
#define | HEUR_PRIORITY -1104000 |
#define | HEUR_FREQ 30 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINIMPROVE 0.01 /* factor by which Crossover should at least improve the incumbent */ |
#define | DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINFIXINGRATE 0.666 /* minimum percentage of integer variables that have to be fixed */ |
#define | DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */ |
#define | DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ |
#define | DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ |
#define | DEFAULT_NUSEDSOLS 3 /* number of solutions that will be taken into account */ |
#define | DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change heuristic should wait */ |
#define | DEFAULT_RANDOMIZATION TRUE /* should the choice which sols to take be randomized? */ |
#define | DEFAULT_DONTWAITATROOT FALSE /* should the nwaitingnodes parameter be ignored at the root node? */ |
#define | DEFAULT_USELPROWS |
#define | DEFAULT_COPYCUTS |
#define | DEFAULT_PERMUTE FALSE /* should the subproblem be permuted to increase diversification? */ |
#define | HASHSIZE_SOLS 500 /* size of hash table for solution tuples in crossover heuristic */ |
#define | DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */ |
#define | DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
#define | DEFAULT_RANDSEED 7 /* initial random seed */ |
#define | EVENTHDLR_NAME "Crossover" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Typedefs | |
typedef struct SolTuple | SOLTUPLE |
Functions | |
static | SCIP_DECL_HASHGETKEY (hashGetKeySols) |
static | SCIP_DECL_HASHKEYEQ (hashKeyEqSols) |
static | SCIP_DECL_HASHKEYVAL (hashKeyValSols) |
static unsigned int | calculateHashKey (int *indices, int size) |
static void | sortArray (int *a, int size) |
static SCIP_RETCODE | createSolTuple (SCIP *scip, SOLTUPLE **elem, int *indices, int size, SCIP_HEURDATA *heurdata) |
static SCIP_Bool | solHasNewSource (SCIP_SOL **sols, int *selection, int selectionsize, int newsol) |
static SCIP_RETCODE | selectSolsRandomized (SCIP *scip, int *selection, SCIP_HEURDATA *heurdata, SCIP_Bool *success) |
static SCIP_RETCODE | fixVariables (SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, int fixedvarssize, int *selection, SCIP_HEURDATA *heurdata, SCIP_Bool *success) |
static SCIP_RETCODE | determineVariableFixings (SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, int fixedvarssize, int *selection, SCIP_HEURDATA *heurdata, SCIP_Bool *success) |
static void | updateFailureStatistic (SCIP *scip, SCIP_HEURDATA *heurdata) |
static | SCIP_DECL_EVENTEXEC (eventExecCrossover) |
static | SCIP_DECL_HEURCOPY (heurCopyCrossover) |
static SCIP_RETCODE | setupAndSolveSubscipCrossover (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, SCIP_Longint nstallnodes, SCIP_RESULT *result, int *selection, int nvars, int nfixedvars, int nusedsols) |
static | SCIP_DECL_HEURFREE (heurFreeCrossover) |
static | SCIP_DECL_HEURINIT (heurInitCrossover) |
static | SCIP_DECL_HEUREXIT (heurExitCrossover) |
static | SCIP_DECL_HEUREXEC (heurExecCrossover) |
SCIP_RETCODE | SCIPincludeHeurCrossover (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "crossover" |
Definition at line 53 of file heur_crossover.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIPincludeHeurCrossover(), and setupAndSolveSubscipCrossover().
◆ HEUR_DESC
#define HEUR_DESC "LNS heuristic that fixes all variables that are identic in a couple of solutions" |
Definition at line 54 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 55 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1104000 |
Definition at line 56 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ HEUR_FREQ
#define HEUR_FREQ 30 |
Definition at line 57 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 58 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 59 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 60 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 61 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
Definition at line 63 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE 0.01 /* factor by which Crossover should at least improve the incumbent */ |
Definition at line 64 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
Definition at line 65 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_MINFIXINGRATE
#define DEFAULT_MINFIXINGRATE 0.666 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 66 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */ |
Definition at line 67 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 68 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_LPLIMFAC
#define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ |
Definition at line 69 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_NUSEDSOLS
#define DEFAULT_NUSEDSOLS 3 /* number of solutions that will be taken into account */ |
Definition at line 70 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_NWAITINGNODES
#define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change heuristic should wait */ |
Definition at line 71 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_RANDOMIZATION
#define DEFAULT_RANDOMIZATION TRUE /* should the choice which sols to take be randomized? */ |
Definition at line 72 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_DONTWAITATROOT
#define DEFAULT_DONTWAITATROOT FALSE /* should the nwaitingnodes parameter be ignored at the root node? */ |
Definition at line 73 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_USELPROWS
#define DEFAULT_USELPROWS |
Definition at line 74 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_COPYCUTS
#define DEFAULT_COPYCUTS |
Definition at line 76 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_PERMUTE
#define DEFAULT_PERMUTE FALSE /* should the subproblem be permuted to increase diversification? */ |
Definition at line 79 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ HASHSIZE_SOLS
#define HASHSIZE_SOLS 500 /* size of hash table for solution tuples in crossover heuristic */ |
Definition at line 80 of file heur_crossover.c.
Referenced by SCIP_DECL_HEURINIT().
◆ DEFAULT_BESTSOLLIMIT
#define DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */ |
Definition at line 81 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_USEUCT
#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
Definition at line 82 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 7 /* initial random seed */ |
Definition at line 83 of file heur_crossover.c.
Referenced by SCIP_DECL_HEURINIT().
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "Crossover" |
Definition at line 86 of file heur_crossover.c.
Referenced by SCIP_DECL_EVENTEXEC(), and setupAndSolveSubscipCrossover().
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 87 of file heur_crossover.c.
Referenced by setupAndSolveSubscipCrossover().
Typedef Documentation
◆ SOLTUPLE
typedef struct SolTuple SOLTUPLE |
Definition at line 93 of file heur_crossover.c.
Function Documentation
◆ SCIP_DECL_HASHGETKEY()
|
static |
gets the hash key of a solution tuple
Definition at line 145 of file heur_crossover.c.
◆ SCIP_DECL_HASHKEYEQ()
|
static |
returns TRUE iff both solution tuples are identical
Definition at line 153 of file heur_crossover.c.
◆ SCIP_DECL_HASHKEYVAL()
|
static |
returns hashkey of a solution tuple
Definition at line 184 of file heur_crossover.c.
◆ calculateHashKey()
|
static |
calculates a hash key for a given tuple of solution indices
- Parameters
-
indices indices of solutions size number of solutions
Definition at line 192 of file heur_crossover.c.
Referenced by createSolTuple().
◆ sortArray()
|
static |
insertion sort for a small int array
- Parameters
-
a array to be sorted size size of array
Definition at line 212 of file heur_crossover.c.
Referenced by createSolTuple().
◆ createSolTuple()
|
static |
creates a new tuple of solutions
- Parameters
-
scip original SCIP data structure elem tuple of solutions which should be created indices indices of solutions size number of solutions heurdata primal heuristic data
Definition at line 238 of file heur_crossover.c.
References BMScopyMemoryArray, calculateHashKey(), SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and sortArray().
Referenced by determineVariableFixings(), selectSolsRandomized(), and setupAndSolveSubscipCrossover().
◆ solHasNewSource()
|
static |
checks whether the new solution was found at the same node by the same heuristic as an already selected one
- Parameters
-
sols feasible SCIP solutions selection pool of solutions crossover uses selectionsize size of solution pool newsol candidate solution
Definition at line 265 of file heur_crossover.c.
References FALSE, SCIPsolGetHeur(), SCIPsolGetNodenum(), and TRUE.
Referenced by selectSolsRandomized().
◆ selectSolsRandomized()
|
static |
randomly selects the solutions crossover will use from the pool of all solutions found so far
- Parameters
-
scip original SCIP data structure selection pool of solutions crossover uses heurdata primal heuristic data success pointer to store whether the process was successful
Definition at line 286 of file heur_crossover.c.
References createSolTuple(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetNSols(), SCIPgetSols(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPrandomGetInt(), solHasNewSource(), and TRUE.
Referenced by determineVariableFixings().
◆ fixVariables()
|
static |
determines the fixings for the CROSSOVER subproblem and checks whether enough fixings were found
- Parameters
-
scip original SCIP data structure fixedvars array to store source SCIP variables whose copies should be fixed in the sub-SCIP fixedvals array to store solution values for variable fixing nfixedvars pointer to store the number of fixed variables fixedvarssize size of the arrays to store fixing variables selection pool of solutions crossover will use heurdata primal heuristic data success pointer to store whether the problem was created successfully
Definition at line 353 of file heur_crossover.c.
References FALSE, MAX, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetSols(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by determineVariableFixings().
◆ determineVariableFixings()
|
static |
creates a subproblem for subscip by fixing a number of variables
- Parameters
-
scip original SCIP data structure fixedvars array to store source SCIP variables whose copies should be fixed in the sub-SCIP fixedvals array to store solution values for variable fixing nfixedvars pointer to store the number of fixed variables fixedvarssize size of the arrays to store fixing variables selection pool of solutions crossover will use heurdata primal heuristic data success pointer to store whether the problem was created successfully
Definition at line 431 of file heur_crossover.c.
References createSolTuple(), FALSE, fixVariables(), SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPgetNSols(), SCIPgetSols(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPsolGetHeur(), SCIPsolGetNodenum(), selectSolsRandomized(), and TRUE.
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 513 of file heur_crossover.c.
References SCIP_LONGINT_MAX, and SCIPgetNNodes().
Referenced by SCIP_DECL_HEUREXEC(), and setupAndSolveSubscipCrossover().
◆ SCIP_DECL_EVENTEXEC()
|
static |
Definition at line 532 of file heur_crossover.c.
References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 561 of file heur_crossover.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurCrossover().
◆ setupAndSolveSubscipCrossover()
|
static |
setup and solve the subproblem and catch the return code
- Parameters
-
scip SCIP data structure subscip sub-SCIP data structure heur mutation heuristic heurdata heuristics data vars SCIP variables fixedvars array to store the variables that should be fixed in the subproblem fixedvals array to store the fixing values to fix variables in the subproblem nstallnodes node limit for the subproblem result pointer to store the result selection pool of solutions crossover uses nvars number of original problem's variables nfixedvars the number of variables that should be fixed nusedsols number of solutions which will be chosen
Definition at line 575 of file heur_crossover.c.
References createSolTuple(), EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyLargeNeighborhoodSearch(), SCIPcopyLimits(), SCIPdebug, SCIPdebugMsg, SCIPdropEvent(), SCIPerrorMessage, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetLowerbound(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSols(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashtableInsert(), SCIPheurGetNCalls(), SCIPincludeEventhdlrBasic(), SCIPinitializeRandomSeed(), SCIPisInfinity(), SCIPisParamFixed(), SCIPmergeVariableStatistics(), SCIPpermuteProb(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolGetIndex(), SCIPsolve(), SCIPsumepsilon(), SCIPtransformProb(), SCIPtranslateSubSols(), SCIPwriteOrigProblem(), TRUE, and updateFailureStatistic().
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 814 of file heur_crossover.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 834 of file heur_crossover.c.
References DEFAULT_RANDSEED, HASHSIZE_SOLS, NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPcreateRandom(), SCIPhashtableCreate(), SCIPheurGetData(), and TRUE.
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 867 of file heur_crossover.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeRandom(), SCIPhashtableFree(), and SCIPheurGetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 902 of file heur_crossover.c.
References determineVariableFixings(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcheckCopyLimits(), SCIPcreate(), SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetDepth(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSolNodenum(), SCIPgetSols(), SCIPgetVarsData(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPisStopped(), setupAndSolveSubscipCrossover(), and updateFailureStatistic().