heur_crossover.c
Go to the documentation of this file.
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
63 #define HEUR_DESC "LNS heuristic that fixes all variables that are identic in a couple of solutions"
73 #define DEFAULT_MINIMPROVE 0.01 /* factor by which Crossover should at least improve the incumbent */
75 #define DEFAULT_MINFIXINGRATE 0.666 /* minimum percentage of integer variables that have to be fixed */
77 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
78 #define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */
80 #define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change heuristic should wait */
82 #define DEFAULT_DONTWAITATROOT FALSE /* should the nwaitingnodes parameter be ignored at the root node? */
85 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
88 #define DEFAULT_PERMUTE FALSE /* should the subproblem be permuted to increase diversification? */
90 #define DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */
91 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
118 SCIP_Longint nwaitingnodes; /**< number of nodes without incumbent change heuristic should wait */
120 SCIP_Longint nextnodenumber; /**< number of nodes at which crossover should be called the next time */
123 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
124 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
126 SCIP_Bool dontwaitatroot; /**< should the nwaitingnodes parameter be ignored at the root node? */
272 /** checks whether the new solution was found at the same node by the same heuristic as an already selected one */
293 /** randomly selects the solutions crossover will use from the pool of all solutions found so far */
360 /** determines the fixings for the CROSSOVER subproblem and checks whether enough fixings were found */
364 SCIP_VAR** fixedvars, /**< array to store source SCIP variables whose copies should be fixed in the sub-SCIP */
417 fixable = fixable && SCIPvarGetLbGlobal(vars[i]) <= solval && solval <= SCIPvarGetUbGlobal(vars[i]);
442 SCIP_VAR** fixedvars, /**< array to store source SCIP variables whose copies should be fixed in the sub-SCIP */
464 /* use nusedsols best solutions if randomization is deactivated or there are only nusedsols solutions at hand
466 if( !heurdata->randomization || nsols == nusedsols || heurdata->prevlastsol != sols[nusedsols-1] )
481 /* check, whether all solutions have been found by the same heuristic at the same node; in this case we do not run
497 /* if solution tuple has already been tried, randomization is allowed and enough solutions are at hand, try
498 * to randomize another tuple. E.g., this can happen if the last crossover solution was among the best ones */
515 SCIP_CALL( fixVariables(scip, fixedvars, fixedvals, nfixedvars, fixedvarssize, selection, heurdata, success) );
527 /* increase number of failures, calculate next node at which crossover should be called and update actual solutions */
590 SCIP_VAR** fixedvars, /**< array to store the variables that should be fixed in the subproblem */
591 SCIP_Real* fixedvals, /**< array to store the fixing values to fix variables in the subproblem */
618 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "crossover", fixedvars, fixedvals, nfixedvars,
623 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCrossover, NULL) );
669 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
675 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
681 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
686 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
709 cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
724 SCIP_CALL( SCIPpermuteProb(subscip, SCIPinitializeRandomSeed(scip, (unsigned) SCIPheurGetNCalls(heur)), TRUE, TRUE, TRUE, TRUE, TRUE) );
729 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
739 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
743 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
760 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */
787 /* if solution was among the best ones, crossover should not be called until another good solution was found */
795 /* if solution is not better than incumbent or could not be added to problem => run is counted as a failure */
943 /* in nonrandomized mode: only recall heuristic, if at least one new good solution was found in the meantime */
952 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, SCIPgetBestSol(scip)) < heurdata->nwaitingnodes
963 (nstallnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
1002 SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, nbinvars + nintvars, selection, heurdata, &success) );
1007 /* if creation of sub-SCIP was aborted (e.g. due to number of fixings), free sub-SCIP and abort */
1010 /* this run will be counted as a failure since no new solution tuple could be generated or the neighborhood of the
1118 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:79
Definition: type_result.h:42
Definition: type_result.h:56
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:958
Definition: type_result.h:43
public methods for SCIP parameter handling
Definition: struct_scip.h:68
public methods for node selector plugins
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2496
public methods for memory management
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1596
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
public solving methods
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
Definition: struct_var.h:207
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1874
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3023
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3287
methods commonly used by primal heuristics
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:609
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:932
static unsigned int calculateHashKey(int *indices, int size)
Definition: heur_crossover.c:201
Definition: struct_misc.h:268
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
public methods for problem variables
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:117
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1448
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10012
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3210
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1371
public methods for SCIP variables
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip_solvingstats.c:4136
public methods for numerical tolerances
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2245
public methods for querying solving statistics
Definition: struct_sol.h:73
public methods for the branch-and-bound tree
Definition: struct_misc.h:137
LNS heuristic that tries to combine several feasible solutions.
Definition: type_result.h:44
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
Definition: type_paramset.h:63
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip_copy.c:1265
Definition: type_retcode.h:42
public methods for problem copies
public methods for primal CIP solutions
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)
Definition: heur_crossover.c:584
Definition: struct_heur.h:97
static SCIP_RETCODE createSolTuple(SCIP *scip, SOLTUPLE **elem, int *indices, int size, SCIP_HEURDATA *heurdata)
Definition: heur_crossover.c:247
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:56
public data structures and miscellaneous methods
static SCIP_RETCODE selectSolsRandomized(SCIP *scip, int *selection, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_crossover.c:295
SCIP_RETCODE SCIPpermuteProb(SCIP *scip, unsigned int randseed, SCIP_Bool permuteconss, SCIP_Bool permutebinvars, SCIP_Bool permuteintvars, SCIP_Bool permuteimplvars, SCIP_Bool permutecontvars)
Definition: scip_prob.c:789
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:286
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1430
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:320
SCIP_RETCODE SCIPincludeHeurCrossover(SCIP *scip)
Definition: heur_crossover.c:1044
static SCIP_RETCODE fixVariables(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, int fixedvarssize, int *selection, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_crossover.c:362
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:661
public methods for branching rule plugins and branching
Definition: struct_misc.h:89
public methods for managing events
general public methods
public methods for solutions
public methods for random numbers
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:234
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition: heuristics.c:925
public methods for message handling
static SCIP_Bool solHasNewSource(SCIP_SOL **sols, int *selection, int selectionsize, int newsol)
Definition: heur_crossover.c:274
Definition: type_retcode.h:54
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3244
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2608
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
public methods for primal heuristics
unsigned int SCIPinitializeRandomSeed(SCIP *scip, unsigned int initialseedvalue)
Definition: scip_randnumgen.c:111
Definition: type_paramset.h:62
Definition: objbenders.h:43
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_crossover.c:522
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:883
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
Definition: struct_event.h:204
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, int fixedvarssize, int *selection, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_crossover.c:440
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1657
memory allocation routines