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" |
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) |
#define HEUR_NAME "crossover" |
Definition at line 62 of file heur_crossover.c.
#define HEUR_DESC "LNS heuristic that fixes all variables that are identic in a couple of solutions" |
Definition at line 63 of file heur_crossover.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 64 of file heur_crossover.c.
#define HEUR_PRIORITY -1104000 |
Definition at line 65 of file heur_crossover.c.
#define HEUR_FREQ 30 |
Definition at line 66 of file heur_crossover.c.
#define HEUR_FREQOFS 0 |
Definition at line 67 of file heur_crossover.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 68 of file heur_crossover.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 69 of file heur_crossover.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 70 of file heur_crossover.c.
#define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
Definition at line 72 of file heur_crossover.c.
#define DEFAULT_MINIMPROVE 0.01 /* factor by which Crossover should at least improve the incumbent */ |
Definition at line 73 of file heur_crossover.c.
#define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
Definition at line 74 of file heur_crossover.c.
#define DEFAULT_MINFIXINGRATE 0.666 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 75 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover(), SCIPincludeHeurDins(), SCIPincludeHeurGins(), SCIPincludeHeurLocks(), SCIPincludeHeurLpface(), SCIPincludeHeurMutation(), SCIPincludeHeurRepair(), and SCIPincludeHeurRins().
#define DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */ |
Definition at line 76 of file heur_crossover.c.
#define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 77 of file heur_crossover.c.
#define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ |
Definition at line 78 of file heur_crossover.c.
#define DEFAULT_NUSEDSOLS 3 /* number of solutions that will be taken into account */ |
Definition at line 79 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
#define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change heuristic should wait */ |
Definition at line 80 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover(), SCIPincludeHeurDins(), SCIPincludeHeurGins(), SCIPincludeHeurLocalbranching(), SCIPincludeHeurMutation(), SCIPincludeHeurRins(), SCIPincludeHeurTrustregion(), and SCIPincludeSepaRapidlearning().
#define DEFAULT_RANDOMIZATION TRUE /* should the choice which sols to take be randomized? */ |
Definition at line 81 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
#define DEFAULT_DONTWAITATROOT FALSE /* should the nwaitingnodes parameter be ignored at the root node? */ |
Definition at line 82 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
#define DEFAULT_USELPROWS |
Definition at line 83 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover(), SCIPincludeHeurDins(), SCIPincludeHeurGins(), SCIPincludeHeurLocalbranching(), SCIPincludeHeurLpface(), SCIPincludeHeurMutation(), SCIPincludeHeurProximity(), SCIPincludeHeurRins(), and SCIPincludeHeurTrustregion().
#define DEFAULT_COPYCUTS |
Definition at line 84 of file heur_crossover.c.
#define DEFAULT_PERMUTE FALSE /* should the subproblem be permuted to increase diversification? */ |
Definition at line 85 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover().
#define HASHSIZE_SOLS 500 /* size of hash table for solution tuples in crossover heuristic */ |
Definition at line 86 of file heur_crossover.c.
Referenced by SCIP_DECL_HEURINIT().
#define DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */ |
Definition at line 87 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover(), SCIPincludeHeurDins(), SCIPincludeHeurGins(), SCIPincludeHeurLocalbranching(), SCIPincludeHeurMutation(), and SCIPincludeHeurTrustregion().
#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
Definition at line 88 of file heur_crossover.c.
Referenced by SCIPincludeHeurCrossover(), SCIPincludeHeurDins(), SCIPincludeHeurMutation(), SCIPincludeHeurProximity(), SCIPincludeHeurRins(), and SCIPincludeHeurZeroobj().
#define DEFAULT_RANDSEED 7 /* initial random seed */ |
Definition at line 89 of file heur_crossover.c.
#define EVENTHDLR_NAME "Crossover" |
Definition at line 92 of file heur_crossover.c.
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 93 of file heur_crossover.c.
typedef struct SolTuple SOLTUPLE |
Definition at line 99 of file heur_crossover.c.
|
static |
gets the hash key of a solution tuple
Definition at line 151 of file heur_crossover.c.
|
static |
|
static |
returns hashkey of a solution tuple
Definition at line 190 of file heur_crossover.c.
|
static |
calculates a hash key for a given tuple of solution indices
indices | indices of solutions |
size | number of solutions |
Definition at line 198 of file heur_crossover.c.
References i.
Referenced by createSolTuple().
|
static |
insertion sort for a small int array
a | array to be sorted |
size | size of array |
Definition at line 218 of file heur_crossover.c.
Referenced by createSolTuple().
|
static |
creates a new tuple of solutions
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 244 of file heur_crossover.c.
References BMScopyMemoryArray, calculateHashKey(), heurdata, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and sortArray().
Referenced by determineVariableFixings(), selectSolsRandomized(), and setupAndSolveSubscipCrossover().
|
static |
checks whether the new solution was found at the same node by the same heuristic as an already selected one
sols | feasible SCIP solutions |
selection | pool of solutions crossover uses |
selectionsize | size of solution pool |
newsol | candidate solution |
Definition at line 271 of file heur_crossover.c.
References FALSE, i, SCIP_Bool, SCIPsolGetHeur(), SCIPsolGetNodenum(), selection, and TRUE.
Referenced by selectSolsRandomized().
|
static |
randomly selects the solutions crossover will use from the pool of all solutions found so far
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 292 of file heur_crossover.c.
References assert(), createSolTuple(), FALSE, heurdata, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetNSols(), SCIPgetSols(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPrandomGetInt(), selection, solHasNewSource(), and TRUE.
Referenced by determineVariableFixings().
|
static |
determines the fixings for the CROSSOVER subproblem and checks whether enough fixings were found
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 359 of file heur_crossover.c.
References assert(), FALSE, heurdata, i, MAX, nbinvars, nintvars, NULL, nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetSols(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), selection, TRUE, and vars.
Referenced by determineVariableFixings().
|
static |
creates a subproblem for subscip by fixing a number of variables
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 437 of file heur_crossover.c.
References assert(), createSolTuple(), FALSE, fixVariables(), heurdata, i, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPgetNSols(), SCIPgetSols(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPsolGetHeur(), SCIPsolGetNodenum(), selection, selectSolsRandomized(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
updates heurdata after a run of crossover
scip | original SCIP data structure |
heurdata | primal heuristic data |
Definition at line 519 of file heur_crossover.c.
References heurdata, SCIP_LONGINT_MAX, and SCIPgetNNodes().
Referenced by SCIP_DECL_HEUREXEC(), and setupAndSolveSubscipCrossover().
|
static |
Definition at line 538 of file heur_crossover.c.
References assert(), EVENTHDLR_NAME, heurdata, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 567 of file heur_crossover.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurCrossover().
|
static |
setup and solve the subproblem and catch the return code
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 581 of file heur_crossover.c.
References assert(), createSolTuple(), cutoff, EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, heurdata, i, MIN, NULL, nvars, result, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyLargeNeighborhoodSearch(), SCIPcopyLimits(), SCIPdebug, SCIPdebugMsg, SCIPdropEvent(), SCIPerrorMessage, SCIPfindBranchrule(), 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(), selection, TRUE, updateFailureStatistic(), and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 809 of file heur_crossover.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 829 of file heur_crossover.c.
References assert(), DEFAULT_RANDSEED, HASHSIZE_SOLS, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPcreateRandom(), SCIPhashtableCreate(), SCIPheurGetData(), and TRUE.
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 862 of file heur_crossover.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeRandom(), SCIPhashtableFree(), and SCIPheurGetData().
|
static |
execution method of primal heuristic
Definition at line 897 of file heur_crossover.c.
References assert(), determineVariableFixings(), FALSE, heurdata, MIN, nbinvars, nintvars, NULL, nvars, result, 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(), selection, setupAndSolveSubscipCrossover(), updateFailureStatistic(), and vars.