62#define HEUR_NAME "crossover"
63#define HEUR_DESC "LNS heuristic that fixes all variables that are identic in a couple of solutions"
64#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
65#define HEUR_PRIORITY -1104000
68#define HEUR_MAXDEPTH -1
69#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
70#define HEUR_USESSUBSCIP TRUE
72#define DEFAULT_MAXNODES 5000LL
73#define DEFAULT_MINIMPROVE 0.01
74#define DEFAULT_MINNODES 50LL
75#define DEFAULT_MINFIXINGRATE 0.666
76#define DEFAULT_NODESOFS 500LL
77#define DEFAULT_NODESQUOT 0.1
78#define DEFAULT_LPLIMFAC 2.0
79#define DEFAULT_NUSEDSOLS 3
80#define DEFAULT_NWAITINGNODES 200LL
81#define DEFAULT_RANDOMIZATION TRUE
82#define DEFAULT_DONTWAITATROOT FALSE
83#define DEFAULT_USELPROWS FALSE
85#define DEFAULT_COPYCUTS TRUE
88#define DEFAULT_PERMUTE FALSE
89#define HASHSIZE_SOLS 500
90#define DEFAULT_BESTSOLLIMIT -1
91#define DEFAULT_USEUCT FALSE
92#define DEFAULT_RANDSEED 7
95#define EVENTHDLR_NAME "Crossover"
96#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
111 SCIP_Longint maxnodes;
112 SCIP_Longint minnodes;
113 SCIP_Longint nodesofs;
118 SCIP_Longint nwaitingnodes;
119 unsigned int nfailures;
120 SCIP_Longint nextnodenumber;
121 SCIP_Real minfixingrate;
122 SCIP_Real minimprove;
125 SCIP_Bool randomization;
126 SCIP_Bool dontwaitatroot;
170 indices1 = ((
SOLTUPLE*)key1)->indices;
171 indices2 = ((
SOLTUPLE*)key2)->indices;
181 for(
i = 0;
i < size;
i++ )
183 if( indices1[
i] != indices2[
i] )
207 unsigned int hashkey;
211 for(
i = 0;
i < size;
i++ )
212 hashkey *= (
unsigned) indices[
i] + 1;
213 for(
i = 0;
i < size;
i++ )
214 hashkey += (
unsigned) indices[
i];
231 for(
i = 1;
i < size;
i++ )
235 while( j >= 0 &&
a[j] > tmp )
262 (*elem)->size = size;
264 (*elem)->prev =
heurdata->lasttuple;
283 for(
i = 0;
i < selectionsize;
i++ )
316 assert(nusedsols < lastsol);
322 while( !*success &&
i < 10 )
324 SCIP_Bool validtuple;
327 for( j = 0; j < nusedsols && validtuple; j++ )
336 validtuple = (k >= nusedsols-j-1);
365 SCIP_Real* fixedvals,
375 SCIP_Real fixingrate;
405 for( j = 1; j <
heurdata->nusedsols; j++ )
409 if(
REALABS(solval - varsolval) > 0.5 )
422 fixedvars[(*nfixedvars)] =
vars[
i];
423 fixedvals[(*nfixedvars)] = solval;
443 SCIP_Real* fixedvals,
462 assert(nsols >= nusedsols);
466 if( !
heurdata->randomization || nsols == nusedsols ||
heurdata->prevlastsol != sols[nusedsols-1] )
470 SCIP_Longint solnodenum;
473 for(
i = 0;
i < nusedsols;
i++ )
484 for(
i = 1;
i < nusedsols;
i++ )
499 if( !(*success) &&
heurdata->randomization && nsols > nusedsols )
591 SCIP_Real* fixedvals,
592 SCIP_Longint nstallnodes,
604 SCIP_Real upperbound;
624 if( eventhdlr ==
NULL )
732#ifdef SCIP_DISABLED_CODE
776 for(
i = 0;
i < nusedsols;
i++ )
857 hashGetKeySols, hashKeyEqSols, hashKeyValSols,
NULL) );
879 while( soltuple !=
NULL )
882 tmp = soltuple->prev;
908 SCIP_Longint nstallnodes;
910 SCIP_Real* fixedvals;
937 if( sols[nusedsols-1] !=
heurdata->prevlastsol )
940 if( sols[0] !=
heurdata->prevbestsol )
971 nstallnodes =
MIN(nstallnodes,
heurdata->maxnodes);
974 if( nstallnodes < heurdata->minnodes )
1070 "number of nodes added to the contingent of the total nodes",
1074 "maximum number of nodes to regard in the subproblem",
1078 "minimum number of nodes required to start the subproblem",
1082 "number of solutions to be taken into account",
1086 "number of nodes without incumbent change that heuristic should wait",
1090 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1094 "minimum percentage of integer variables that have to be fixed",
1098 "factor by which Crossover should at least improve the incumbent",
1102 "factor by which the limit on the number of LP depends on the node limit",
1106 "should the choice which sols to take be randomized?",
1110 "should the nwaitingnodes parameter be ignored at the root node?",
1114 "should subproblem be created out of the rows in the LP rows?",
1118 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1122 "should the subproblem be permuted to increase diversification?",
1126 "limit on number of improving incumbent solutions in sub-CIP",
1130 "should uct node selection be used at the beginning of the search?",
#define SCIP_CALL_ABORT(x)
#define SCIP_LONGINT_FORMAT
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_RETCODE SCIPpermuteProb(SCIP *scip, unsigned int randseed, SCIP_Bool permuteconss, SCIP_Bool permutebinvars, SCIP_Bool permuteintvars, SCIP_Bool permuteimplvars, SCIP_Bool permutecontvars)
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
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)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
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)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
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)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
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)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
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)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPincludeHeurCrossover(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
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)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
int SCIPgetNSols(SCIP *scip)
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
int SCIPsolGetIndex(SCIP_SOL *sol)
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
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)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
unsigned int SCIPinitializeRandomSeed(SCIP *scip, unsigned int initialseedvalue)
SCIPfreeRandom(scip, &heurdata->randnumgen)
#define DEFAULT_NODESQUOT
#define DEFAULT_NWAITINGNODES
#define DEFAULT_NUSEDSOLS
#define DEFAULT_DONTWAITATROOT
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 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)
#define DEFAULT_MINFIXINGRATE
#define DEFAULT_MINIMPROVE
#define DEFAULT_USELPROWS
static SCIP_RETCODE createSolTuple(SCIP *scip, SOLTUPLE **elem, int *indices, int size, SCIP_HEURDATA *heurdata)
static void sortArray(int *a, int size)
#define DEFAULT_RANDOMIZATION
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 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 unsigned int calculateHashKey(int *indices, int size)
#define DEFAULT_BESTSOLLIMIT
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
LNS heuristic that tries to combine several feasible solutions.
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
methods commonly used by primal heuristics
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing events
public methods for primal heuristics
public methods for message output
public data structures and miscellaneous methods
public methods for primal CIP solutions
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for event handler plugins and event handlers
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_LPSOLVED
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
#define SCIP_DECL_HASHKEYEQ(x)
#define SCIP_DECL_HASHGETKEY(x)
#define SCIP_DECL_HASHKEYVAL(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE