42 #include "scip/scip.h"
43 #include "scip/misc.h"
44 #include "scip/scipdefplugins.h"
47 #define HEUR_NAME "xpcrossover"
48 #define HEUR_DESC "Extreme Point Crossover"
49 #define HEUR_DISPCHAR 'X'
50 #define HEUR_PRIORITY -1100500
52 #define HEUR_FREQOFS 0
53 #define HEUR_MAXDEPTH -1
54 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
55 #define HEUR_USESSUBSCIP TRUE
57 #define DEFAULT_MAXNODES 1000LL
58 #define DEFAULT_MINIMPROVE 0.01
59 #define DEFAULT_MINNODES 200LL
60 #define DEFAULT_MINFIXINGRATE 0.4
61 #define DEFAULT_NODESOFS 200LL
62 #define DEFAULT_NODESQUOT 0.1
63 #define DEFAULT_NUSEDPTS 4
64 #define DEFAULT_RANDOMIZATION FALSE
65 #define DEFAULT_COPYCUTS TRUE
68 #define DEFAULT_RANDSEED 7
70 #define HASHSIZE_POINTS 11113
102 #ifdef SCIP_STATISTIC
103 SCIP_Longint nfixfails;
104 SCIP_Real avgfixrate;
105 SCIP_Real avgzerorate;
106 SCIP_Longint totalsols;
109 SCIP_Real subsciptime;
110 SCIP_Real bestprimalbd;
153 assert(indices1 != NULL);
154 assert(indices2 != NULL);
160 for( i = 0; i < size; i++ )
162 if( indices1[i] != indices2[i] )
186 unsigned int hashkey;
190 for( i = 0; i < size; i++ )
191 hashkey *= indices[i] + 2;
192 for( i = 0; i < size; i++ )
193 hashkey += indices[i] + 1;
206 SCIP_HEURDATA* heurdata
210 SCIP_CALL( SCIPallocBlockMemory(scip, elem) );
211 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*elem)->indices,size) );
212 BMScopyMemoryArray((*elem)->indices, indices, size);
215 SCIPsortInt((*elem)->indices, size);
216 (*elem)->size = size;
218 (*elem)->prev = heurdata->lasttuple;
221 heurdata->lasttuple = *elem;
230 SCIP_HEURDATA* heurdata,
238 SCIP_VAR** mastervars;
239 SCIP_Real* mastervals;
249 SCIP_Real* blockvalue;
260 assert(scip != NULL);
261 assert(heurdata != NULL);
262 assert(selection != NULL);
263 assert(success != NULL);
267 assert(masterprob != NULL);
273 SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
274 assert(mastervars != NULL);
275 assert(nmastervars >= 0);
278 SCIP_CALL( SCIPallocBufferArray(scip, &mastervals, nmastervars) );
279 SCIP_CALL( SCIPgetSolVals(masterprob, NULL, nmastervars, mastervars, mastervals) );
282 nusedpts = heurdata->nusedpts;
285 SCIP_CALL( SCIPallocBufferArray(scip, &selvalue, nblocks * nusedpts) );
286 SCIP_CALL( SCIPallocBufferArray(scip, &blocknrs, nblocks) );
287 SCIP_CALL( SCIPallocBufferArray(scip, &blockvalue, nblocks) );
288 SCIP_CALL( SCIPallocBufferArray(scip, &identblock, nblocks) );
291 for( i = 0; i < nblocks; i++ )
304 for( i = 0; i < nmastervars; i++ )
308 mastervar = mastervars[i];
313 value = SCIPgetSolVal(masterprob, NULL, mastervar);
316 assert(!SCIPisInfinity(scip, value));
319 if( SCIPisFeasZero(scip, value) )
337 while( SCIPisFeasGE(scip, mastervals[i], 1.0) )
340 j = identblock[block] * nusedpts;
341 assert(selection[j] == -1);
346 mastervals[i] = mastervals[i] - 1.0;
350 for( j = identblock[block] + 1; j < nblocks; ++j )
353 identblock[block] = j;
358 assert(blocknrs[block] >= nidentblocks || j < nblocks);
364 for( i = 0; i < nmastervars; i++ )
368 mastervar = mastervars[i];
373 value = SCIPgetSolVal(masterprob, NULL, mastervar);
376 assert(!SCIPisInfinity(scip, value));
379 if( SCIPisFeasZero(scip, value) )
396 assert(SCIPisFeasGE(scip, mastervals[i], 0.0) && SCIPisFeasLT(scip, mastervals[i], 1.0));
398 while( SCIPisFeasPositive(scip, mastervals[i]) )
400 value = MIN(mastervals[i], 1.0 - blockvalue[block]);
403 for( j = identblock[block] * nusedpts; j < (identblock[block] + 1) * nusedpts; ++j )
408 if( selection[j] == -1 || SCIPisGT(scip, value, selvalue[j]) )
410 for( k = (identblock[block] + 1) * nusedpts - 1; k > j; --k )
412 selection[k] = selection[k-1];
413 selvalue[k] = selvalue[k-1];
421 mastervals[i] = mastervals[i] - value;
422 if( SCIPisFeasZero(scip, mastervals[i]) )
424 blockvalue[block] += value;
427 if( SCIPisFeasGE(scip, blockvalue[block], 1.0) )
429 blockvalue[block] = 0.0;
433 for( j = identblock[block] + 1; j < nblocks; ++j )
436 identblock[block] = j;
441 assert(blocknrs[block] >= nidentblocks || j < nblocks);
448 SCIP_CALL(
createPtTuple(scip, &elem, selection, nusedpts * nblocks, heurdata) );
451 if( !SCIPhashtableExists(heurdata->hashtable, elem) )
453 SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
458 SCIPfreeBufferArray(scip, &identblock);
459 SCIPfreeBufferArray(scip, &blockvalue);
460 SCIPfreeBufferArray(scip, &blocknrs);
461 SCIPfreeBufferArray(scip, &selvalue);
462 SCIPfreeBufferArray(scip, &mastervals);
472 SCIP_HEURDATA* heurdata,
480 SCIP_VAR** mastervars;
497 assert(scip != NULL);
498 assert(heurdata != NULL);
499 assert(selection != NULL);
500 assert(success != NULL);
504 assert(masterprob != NULL);
510 SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
511 assert(mastervars != NULL);
512 assert(nmastervars >= 0);
515 nusedpts = heurdata->nusedpts;
518 SCIP_CALL( SCIPallocBufferArray(scip, &npts, nblocks) );
523 for( i = 0; i < nblocks; ++i )
525 for( i = 0; i < nmastervars; ++i )
531 mastervar = mastervars[i];
532 solval = SCIPgetSolVal(masterprob, NULL, mastervar);
535 if( block >= 0 && !SCIPisFeasZero(scip, solval) )
538 for( i = 0; i < nblocks; ++i )
545 SCIPdebugMessage(
" -> not enough extreme points available for randomization.\n");
548 SCIPfreeBufferArray(scip, &npts);
559 for( i = 0; i < nblocks; ++i )
563 SCIP_CALL( SCIPallocBufferArray(scip, &blockpts, npts[i]) );
564 SCIP_CALL( SCIPallocBufferArray(scip, &ptvals, npts[i]) );
568 assert(blockrep >= 0 && blockrep <= i);
572 for( j = 0; j < nmastervars; ++j )
578 mastervar = mastervars[j];
579 solval = SCIPgetSolVal(masterprob, NULL, mastervar);
582 if( block == blockrep && !SCIPisFeasZero(scip, solval) )
584 assert(k < npts[blockrep]);
589 assert(k == npts[blockrep]);
592 SCIPsortRealInt(ptvals, blockpts, npts[blockrep]);
593 lastpt = npts[blockrep];
596 for( k = 0; k < nusedpts; ++k )
601 idx = SCIPrandomGetInt(heurdata->randnumgen, nusedpts-k-1, lastpt-1);
602 selidx = i * nusedpts + k;
603 selection[selidx] = blockpts[idx];
607 SCIPfreeBufferArray(scip, &ptvals);
608 SCIPfreeBufferArray(scip, &blockpts);
612 SCIP_CALL(
createPtTuple(scip, &elem, selection, nusedpts * nblocks, heurdata) );
615 if( !SCIPhashtableExists(heurdata->hashtable, elem) )
617 SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
622 while( !*success && iters < 10 );
625 SCIPfreeBufferArray(scip, &npts);
634 SCIP_RETCODE printExtremePoints(
643 SCIP_VAR** mastervars;
655 assert(scip != NULL);
659 assert(masterprob != NULL);
664 SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
665 assert(mastervars != NULL);
666 assert(nmastervars >= 0);
669 SCIPdebugPrintf(
"------------------------------------------------------------\n");
670 SCIPdebugPrintf(
"Current relaxation solution:\n");
672 SCIPdebugPrintf(
"------------------------------------------------------------\n");
675 for( i = 0; i < nblocks; ++i )
677 SCIPdebugPrintf(
"Block %i\n", i+1);
678 SCIPdebugPrintf(
"------------------------------------------------------------\n");
680 for( j = 0; j < nusedpts; ++j )
682 selidx = i * nusedpts + j;
683 if( selection[selidx] != -1 )
685 mastervar = mastervars[selection[selidx]];
692 SCIPdebugPrintf(
"Extreme point %i, mastervar %s, masterval=%g, index=%d:\n",
693 j+1, SCIPvarGetName(mastervar),
694 SCIPgetSolVal(masterprob, NULL, mastervar), SCIPvarGetProbindex(mastervar));
695 for( k = 0; k < norigvars; ++k )
697 SCIPdebugPrintf(
"%-32s % 20.15g \t(obj:%.15g)\n",
698 SCIPvarGetName(origvars[k]), origvals[k], SCIPvarGetObj(origvars[k]));
700 SCIPdebugPrintf(
"------------------------------------------------------------\n");
715 SCIP_HEURDATA* heurdata,
716 SCIP_Longint nstallnodes,
718 SCIP_Real memorylimit
726 char probname[SCIP_MAXSTRLEN];
727 SCIP_HASHMAP* varmapfw;
730 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
731 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
736 SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
739 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN,
"%s_extremeptsub", SCIPgetProbName(scip));
742 SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
745 SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, NULL, NULL, 0, TRUE) );
749 SCIP_CALL( SCIPcopyConss(scip, subscip, varmapfw, NULL, TRUE, FALSE, &valid) );
750 if( heurdata->copycuts )
753 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
755 SCIPdebugMessage(
"Copying the SCIP constraints was %s complete.\n", valid ?
"" :
"not ");
758 for( i = 0; i < nvars; i++ )
759 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
762 SCIPhashmapFree(&varmapfw);
766 SCIP_CALL( SCIPsetBoolParam(subscip,
"misc/catchctrlc", FALSE) );
770 SCIP_CALL( SCIPsetIntParam(subscip,
"display/verblevel", 5) );
771 SCIP_CALL( SCIPsetIntParam(subscip,
"display/freq", 100000000) );
774 SCIP_CALL( SCIPsetIntParam(subscip,
"display/verblevel", 0) );
778 SCIP_CALL( SCIPsetLongintParam(subscip,
"limits/nodes", nstallnodes) );
779 SCIP_CALL( SCIPsetLongintParam(subscip,
"limits/stallnodes", MAX(10, nstallnodes/10)) );
780 SCIP_CALL( SCIPsetRealParam(subscip,
"limits/time", timelimit) );
781 SCIP_CALL( SCIPsetRealParam(subscip,
"limits/memory", memorylimit) );
784 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
787 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
790 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
793 if( SCIPfindNodesel(subscip,
"estimate") != NULL && !SCIPisParamFixed(subscip,
"nodeselection/estimate/stdpriority") )
795 SCIP_CALL( SCIPsetIntParam(subscip,
"nodeselection/estimate/stdpriority", INT_MAX/4) );
799 if( SCIPfindBranchrule(subscip,
"inference") != NULL && !SCIPisParamFixed(subscip,
"branching/inference/priority") )
801 SCIP_CALL( SCIPsetIntParam(subscip,
"branching/inference/priority", INT_MAX/4) );
805 if( !SCIPisParamFixed(subscip,
"conflict/enable") )
807 SCIP_CALL( SCIPsetBoolParam(subscip,
"conflict/enable", FALSE) );
811 if( SCIPgetNSols(scip) > 0 )
814 SCIP_Real upperbound;
816 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
818 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
819 if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
821 cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
825 if( SCIPgetUpperbound ( scip ) >= 0 )
826 cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip );
828 cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip );
830 cutoff = MIN(upperbound, cutoff );
831 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
844 SCIP_HEURDATA* heurdata,
845 SCIP_Real* intfixingrate,
846 SCIP_Real* zerofixingrate,
851 SCIP_VAR** mastervars;
862 SCIP_Bool* zeroblocks;
874 assert(scip != NULL);
875 assert(subscip != NULL);
876 assert(subvars != NULL);
877 assert(selection != NULL);
878 assert(heurdata != NULL);
879 assert(intfixingrate != NULL);
880 assert(zerofixingrate != NULL);
881 assert(success != NULL);
885 assert(masterprob != NULL);
886 SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, NULL, NULL, NULL, NULL, NULL) );
887 assert(mastervars != NULL);
890 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
893 nusedpts = heurdata->nusedpts;
894 assert(nusedpts >= 2);
902 SCIP_CALL( SCIPallocBufferArray(scip, &fixvals, nbinvars + nintvars) );
903 SCIP_CALL( SCIPallocBufferArray(scip, &fixable, nbinvars + nintvars) );
904 SCIP_CALL( SCIPallocBufferArray(scip, &ptcounter, nbinvars + nintvars) );
905 SCIP_CALL( SCIPallocBufferArray(scip, &zeroblocks, nblocks) );
922 for( i = 0; i < nbinvars + nintvars; ++i )
929 for( i = 0; i < nblocks; ++i )
942 selidx = i * nusedpts;
943 assert(selection[selidx] != -1);
949 selidx = i * nusedpts + 1;
950 if( selection[selidx] == -1 )
951 zeroblocks[i] = TRUE;
953 zeroblocks[i] = FALSE;
956 for( j = 0; j < nusedpts; ++j )
958 selidx = i * nusedpts + j;
959 if( selection[selidx] != -1 )
962 mastervar = mastervars[selection[selidx]];
970 for( k = 0; k < norigvars; ++k )
973 SCIP_Bool firstblock;
975 if( SCIPvarGetType(origvars[k]) > SCIP_VARTYPE_INTEGER )
978 if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(origvars[k]), SCIPvarGetUbGlobal(origvars[k]) ) )
988 SCIP_VAR* pricingvar;
990 SCIP_VAR** linkingpricingvars;
994 pricingvar = linkingpricingvars[blockrep];
995 assert(pricingvar != NULL);
1002 for( l = 0; l < blockrep; ++l )
1003 if( linkingpricingvars[l] != NULL )
1005 firstblock = (l == blockrep);
1008 origvar = origvars[k];
1012 SCIP_VAR* pricingvar;
1013 SCIP_VAR** pricingorigvars;
1014 int npricingorigvars;
1017 assert(pricingvar != NULL);
1030 for( l = 0; l < npricingorigvars; ++l )
1033 origvar = pricingorigvars[l];
1036 assert(origvar != NULL);
1040 idx = SCIPvarGetProbindex(origvar);
1041 assert(idx < nbinvars + nintvars);
1044 if( j == 0 && firstblock )
1045 fixvals[idx] = origvals[k];
1048 if( fixable[idx] && !SCIPisEQ(scip, fixvals[idx], origvals[k]) )
1049 fixable[idx] = FALSE;
1051 if( !SCIPisZero(scip, origvals[k]) )
1054 zeroblocks[i] = FALSE;
1062 for( i = 0; i < nbinvars + nintvars; ++i )
1078 fixvals[i] = SCIPgetRelaxSolVal(scip, var);
1079 if( SCIPisFeasIntegral(scip, fixvals[i]) )
1084 fixvals[i] = SCIPfloor(scip, fixvals[i] + 0.5);
1097 assert(block >= 0 || block == -2);
1099 assert(ptcounter[i] <= nusedpts * nlinkblocks);
1105 if( ptcounter[i] > 0 && ptcounter[i] < nusedpts * nlinkblocks )
1110 if( ptcounter[i] == 0 )
1113 assert(SCIPisZero(scip, fixvals[i]));
1119 lb = SCIPvarGetLbGlobal(var);
1120 ub = SCIPvarGetUbGlobal(var);
1123 if( fixable[i] && (lb > fixvals[i] || fixvals[i] > ub) )
1132 if( fixable[i] && (block < 0 || !zeroblocks[block]) )
1134 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], fixvals[i]) );
1135 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], fixvals[i]) );
1139 if( SCIPisZero(scip, fixvals[i]) )
1144 *intfixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
1145 *zerofixingrate = (SCIP_Real)zerocounter / MAX((SCIP_Real)fixingcounter, 1.0);
1148 while( *intfixingrate < heurdata->minfixingrate )
1150 SCIPdebugMessage(
" fixing rate only %5.2f --> trying to fix a zero block\n", *intfixingrate);
1153 for( i = 0; i < nblocks; ++i )
1157 for( j = 0; j < nbinvars + nintvars; ++j )
1160 assert(SCIPisZero(scip, fixvals[j]));
1161 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[j], 0.0) );
1162 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[j], 0.0) );
1167 zeroblocks[i] = FALSE;
1171 *intfixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
1172 *zerofixingrate = (SCIP_Real)zerocounter / MAX((SCIP_Real)fixingcounter, 1.0);
1179 if( *intfixingrate < heurdata->minfixingrate )
1181 SCIPstatisticPrintf(
"xpcrossover statistic: fixed only %5.2f ( %5.2f zero) integer variables --> abort \n", *intfixingrate, *zerofixingrate);
1183 if( fixingcounter == nbinvars + nintvars )
1185 SCIPstatisticPrintf(
"xpcrossover statistic: fixed all ( %5.2f zero) integer variables --> abort \n", *zerofixingrate);
1191 SCIPfreeBufferArray(scip, &zeroblocks);
1192 SCIPfreeBufferArray(scip, &fixvals);
1193 SCIPfreeBufferArray(scip, &fixable);
1194 SCIPfreeBufferArray(scip, &ptcounter);
1211 #ifdef SCIP_STATISTIC
1212 SCIP_HEURDATA* heurdata;
1217 SCIP_Real* subsolvals;
1219 assert(scip != NULL);
1220 assert(subscip != NULL);
1221 assert(subvars != NULL);
1222 assert(subsol != NULL);
1224 #ifdef SCIP_STATISTIC
1226 heurdata = SCIPheurGetData(heur);
1227 assert( heurdata != NULL );
1231 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1232 assert(nvars <= SCIPgetNOrigVars(subscip));
1234 SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
1237 SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
1240 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1241 SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
1244 #ifdef SCIP_STATISTIC
1247 SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
1249 #ifdef SCIP_STATISTIC
1250 if( SCIPgetSolTransObj(scip, newsol) < heurdata->bestprimalbd )
1251 heurdata->bestprimalbd = SCIPgetSolTransObj(scip, newsol);
1253 SCIPstatisticPrintf(
"xpcrossover statistic: Solution %13.6e found at node %"SCIP_LONGINT_FORMAT
"\n",
1254 SCIPgetSolOrigObj(scip, newsol), SCIPsolGetNodenum(subsol));
1257 SCIP_CALL( SCIPfreeSol(scip, &newsol) );
1259 SCIPfreeBufferArray(scip, &subsolvals);
1268 SCIP_HEURDATA* heurdata
1272 heurdata->nfailures++;
1273 heurdata->nextnodenumber = (heurdata->nfailures <= 25
1274 ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures)
1275 : SCIP_LONGINT_MAX);
1287 SCIP_HEURDATA* heurdata;
1289 assert(heur != NULL);
1290 assert(scip != NULL);
1293 heurdata = SCIPheurGetData(heur);
1294 assert(heurdata != NULL);
1297 SCIPfreeMemory(scip, &heurdata);
1298 SCIPheurSetData(heur, NULL);
1307 SCIP_HEURDATA* heurdata;
1309 assert(heur != NULL);
1310 assert(scip != NULL);
1313 heurdata = SCIPheurGetData(heur);
1314 assert(heurdata != NULL);
1317 heurdata->usednodes = 0;
1318 heurdata->lasttuple = NULL;
1319 heurdata->nfailures = 0;
1320 heurdata->nextnodenumber = 0;
1323 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
1327 SCIP_CALL( SCIPhashtableCreate(&heurdata->hashtable, SCIPblkmem(scip),
HASHSIZE_POINTS,
1328 hashGetKeyPts, hashKeyEqPts, hashKeyValPts, NULL) );
1329 assert(heurdata->hashtable != NULL );
1338 SCIP_HEURDATA* heurdata;
1341 assert(heur != NULL);
1342 assert(scip != NULL);
1345 heurdata = SCIPheurGetData(heur);
1346 assert(heurdata != NULL);
1347 pointtuple = heurdata->lasttuple;
1350 while( pointtuple != NULL )
1353 tmp = pointtuple->
prev;
1354 SCIPfreeBlockMemoryArray(scip, &pointtuple->
indices, pointtuple->
size);
1355 SCIPfreeBlockMemory(scip, &pointtuple);
1360 assert(heurdata->hashtable != NULL );
1361 SCIPhashtableFree(&heurdata->hashtable);
1364 SCIPfreeRandom(scip, &heurdata->randnumgen);
1370 #ifdef SCIP_STATISTIC
1375 SCIP_HEURDATA* heurdata;
1377 assert(heur != NULL);
1378 assert(scip != NULL);
1381 heurdata = SCIPheurGetData(heur);
1382 assert(heurdata != NULL);
1385 heurdata->avgfixrate = 0.0;
1386 heurdata->avgzerorate = 0.0;
1387 heurdata->totalsols = 0;
1388 heurdata->subsciptime = 0.0;
1389 heurdata->bestprimalbd = SCIPinfinity(scip);
1399 SCIP_HEURDATA* heurdata;
1400 SCIP_Longint ncalls;
1402 assert(heur != NULL);
1403 assert(scip != NULL);
1406 heurdata = SCIPheurGetData(heur);
1407 assert(heurdata != NULL);
1409 ncalls = SCIPheurGetNCalls(heur);
1410 heurdata->avgfixrate /= MAX((SCIP_Real)ncalls, 1.0);
1411 heurdata->avgzerorate /= MAX((SCIP_Real)ncalls, 1.0);
1414 SCIPstatisticPrintf(
"LNS Statistics -- %s:\n", SCIPheurGetName(heur));
1415 SCIPstatisticPrintf(
"Calls : %13"SCIP_LONGINT_FORMAT
"\n", ncalls);
1416 SCIPstatisticPrintf(
"Failed Fixings : %13"SCIP_LONGINT_FORMAT
"\n", heurdata->nfixfails);
1417 SCIPstatisticPrintf(
"Sols : %13"SCIP_LONGINT_FORMAT
"\n", SCIPheurGetNSolsFound(heur));
1418 SCIPstatisticPrintf(
"Improving Sols : %13"SCIP_LONGINT_FORMAT
"\n", SCIPheurGetNBestSolsFound(heur));
1419 SCIPstatisticPrintf(
"Total Sols : %13"SCIP_LONGINT_FORMAT
"\n", heurdata->totalsols);
1420 SCIPstatisticPrintf(
"subSCIP time : %13.2f\n", heurdata->subsciptime);
1421 SCIPstatisticPrintf(
"subSCIP nodes : %13"SCIP_LONGINT_FORMAT
"\n", heurdata->usednodes);
1422 SCIPstatisticPrintf(
"Avg. fixing rate : %13.2f\n", 100.0 * heurdata->avgfixrate);
1423 SCIPstatisticPrintf(
"Avg. zero rate : %13.2f\n", 100.0 * heurdata->avgzerorate);
1424 SCIPstatisticPrintf(
"Best primal bd. :");
1425 if( SCIPisInfinity(scip, heurdata->bestprimalbd) )
1426 SCIPstatisticPrintf(
" infinity\n");
1428 SCIPstatisticPrintf(
" %13.6e\n", heurdata->bestprimalbd);
1429 SCIPstatisticPrintf(
"\n");
1442 SCIP_HEURDATA* heurdata;
1447 SCIP_Real memorylimit;
1448 SCIP_Real timelimit;
1449 SCIP_Longint nstallnodes;
1450 SCIP_Real allfixingrate;
1451 SCIP_Real intfixingrate;
1452 SCIP_Real zerofixingrate;
1458 SCIP_RETCODE retcode;
1462 assert(heur != NULL);
1463 assert(strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0);
1464 assert(scip != NULL);
1465 assert(result != NULL);
1469 assert(masterprob != NULL);
1474 heurdata = SCIPheurGetData(heur);
1475 assert(heurdata != NULL);
1477 *result = SCIP_DELAYED;
1482 if( !SCIPisRelaxSolValid(scip) )
1484 SCIPdebugMessage(
"skipping Extreme Point Crossover: invalid relaxation solution\n");
1489 if( SCIPgetStage(masterprob) > SCIP_STAGE_SOLVING || SCIPgetLPSolstat(masterprob) != SCIP_LPSOLSTAT_OPTIMAL )
1491 SCIPdebugMessage(
"skipping Extreme Point Crossover: master LP not solved to optimality.\n");
1495 assert(SCIPhasCurrentNodeLP(masterprob));
1498 if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
1501 *result = SCIP_DIDNOTRUN;
1504 if( SCIPgetNExternBranchCands(scip) == 0 )
1510 SCIP_CALL( SCIPgetRealParam(scip,
"limits/time", &timelimit) );
1511 if( !SCIPisInfinity(scip, timelimit) )
1512 timelimit -= SCIPgetSolvingTime(scip);
1513 SCIP_CALL( SCIPgetRealParam(scip,
"limits/memory", &memorylimit) );
1516 if( !SCIPisInfinity(scip, memorylimit) )
1518 memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1519 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1523 if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
1527 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
1530 nstallnodes = (SCIP_Longint)
1531 (nstallnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
1534 nstallnodes -= 100 * SCIPheurGetNCalls(heur);
1535 nstallnodes += heurdata->nodesofs;
1538 nstallnodes -= heurdata->usednodes;
1539 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
1542 if( nstallnodes < heurdata->minnodes )
1544 SCIPdebugMessage(
"skipping Extreme Point Crossover: nstallnodes=%"SCIP_LONGINT_FORMAT
", minnodes=%"SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->minnodes);
1548 if( SCIPisStopped(scip) )
1551 SCIPdebugMessage(
"Executing Extreme Point Crossover heuristic ...\n");
1554 SCIP_CALL( SCIPallocBufferArray(scip, &selection, nblocks * heurdata->nusedpts) );
1555 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, SCIPgetNVars(scip)) );
1558 for( i = 0; i < nblocks * heurdata->nusedpts; ++i )
1563 if( heurdata->randomization )
1565 SCIPdebugMessage(
"selecting extreme points randomly...\n");
1568 if( !heurdata->randomization || !success )
1570 SCIPdebugMessage(
"selecting extreme points...\n");
1577 SCIPdebugMessage(
"no proper selection could be created - aborting heuristic.\n");
1582 SCIPfreeBufferArray(scip, &selection);
1583 SCIPfreeBufferArray(scip, &subvars);
1589 SCIP_CALL( printExtremePoints(scip, heurdata->nusedpts, selection) );
1593 SCIP_CALL( SCIPcreate(&subscip) );
1594 SCIP_CALL(
setupSubproblem(scip, subscip, subvars, heurdata, nstallnodes, timelimit, memorylimit) );
1595 SCIPdebugMessage(
"XP Crossover subproblem: %d vars, %d conss\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip));
1597 SCIPstatisticPrintf(
"xpcrossover statistic: called at node %"SCIP_LONGINT_FORMAT
"\n", SCIPgetNNodes(scip));
1600 SCIP_CALL(
fixVariables(scip, subscip, subvars, selection, heurdata, &intfixingrate, &zerofixingrate, &success) );
1602 #ifdef SCIP_STATISTIC
1604 heurdata->avgfixrate += intfixingrate;
1605 heurdata->avgzerorate += zerofixingrate;
1615 #ifdef SCIP_STATISTIC
1616 ++heurdata->nfixfails;
1621 *result = SCIP_DIDNOTFIND;
1624 retcode = SCIPpresolve(subscip);
1629 if( retcode != SCIP_OKAY )
1632 SCIP_CALL( retcode );
1634 SCIPwarningMessage(scip,
"Error while presolving subproblem in XP Crossover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1638 SCIPdebugMessage(
"XP Crossover presolved subproblem: %d vars, %d conss, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
1640 allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip);
1643 allfixingrate = MAX(allfixingrate, 0.0);
1648 if( allfixingrate >= heurdata->minfixingrate / 2.0 )
1654 SCIPdebugMessage(
"subSCIP: Solving... (node limit = %lld, time limit = %.2g)\n", nstallnodes, timelimit);
1660 retcode = SCIPsolve(subscip);
1661 if( retcode != SCIP_OKAY )
1663 SCIPwarningMessage(scip,
"Error while solving subproblem in XP Crossover heuristic; sub-SCIP terminated with code <%d>\n",
1667 SCIP_CALL( SCIPsolve(subscip) );
1670 #ifdef SCIP_STATISTIC
1671 heurdata->usednodes += SCIPgetNNodes(subscip);
1672 heurdata->subsciptime += SCIPgetTotalTime(subscip);
1678 nsubsols = SCIPgetNSols(subscip);
1679 subsols = SCIPgetSols(subscip);
1681 #ifdef SCIP_STATISTIC
1682 heurdata->totalsols += nsubsols;
1683 for( i = 0; i < nsubsols; ++i )
1685 for( i = 0; i < nsubsols && !success; ++i )
1688 SCIP_CALL(
createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
1690 *result = SCIP_FOUNDSOL;
1693 SCIPstatisticPrintf(
"xpcrossover statistic: fixed %6.3f integer variables ( %6.3f zero), %6.3f all variables, needed %6.1f sec (SCIP time: %6.1f sec), %"SCIP_LONGINT_FORMAT
" nodes, found %d solutions, solution %10.4f found at node %"SCIP_LONGINT_FORMAT
"\n",
1694 intfixingrate, zerofixingrate, allfixingrate, SCIPgetSolvingTime(subscip), SCIPgetSolvingTime(scip), SCIPgetNNodes(subscip), nsubsols,
1695 success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip), nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
1701 SCIPdebugMessage(
" -> no subMIP solution found - subSCIP status is %d\n", SCIPgetStatus(subscip));
1706 SCIPstatisticPrintf(
"xpcrossover statistic: fixed only %6.3f integer variables ( %6.3f zero), %6.3f all variables --> abort \n", intfixingrate, zerofixingrate, allfixingrate);
1711 SCIP_CALL( SCIPfree(&subscip) );
1712 SCIPfreeBufferArray(scip, &selection);
1713 SCIPfreeBufferArray(scip, &subvars);
1729 SCIP_HEURDATA* heurdata;
1733 SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
1736 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1740 assert(heur != NULL);
1743 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeXpcrossover) );
1744 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitXpcrossover) );
1745 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitXpcrossover) );
1746 #ifdef SCIP_STATISTIC
1747 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolXpcrossover) );
1748 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolXpcrossover) );
1753 SCIP_CALL( SCIPaddLongintParam(scip,
"heuristics/"HEUR_NAME"/nodesofs",
1754 "number of nodes added to the contingent of the total nodes",
1755 &heurdata->nodesofs, FALSE,
DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1757 SCIP_CALL( SCIPaddLongintParam(scip,
"heuristics/"HEUR_NAME"/maxnodes",
1758 "maximum number of nodes to regard in the subproblem",
1759 &heurdata->maxnodes, TRUE,
DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1761 SCIP_CALL( SCIPaddLongintParam(scip,
"heuristics/"HEUR_NAME"/minnodes",
1762 "minimum number of nodes required to start the subproblem",
1763 &heurdata->minnodes, TRUE,
DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1765 SCIP_CALL( SCIPaddIntParam(scip,
"heuristics/"HEUR_NAME"/nusedpts",
1766 "number of extreme pts per block that will be taken into account",
1769 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/nodesquot",
1770 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1773 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/minfixingrate",
1774 "minimum percentage of integer variables that have to be fixed",
1777 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/minimprove",
1778 "factor by which crossover should at least improve the incumbent",
1781 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/randomization",
1782 "should the choice which sols to take be randomized?",
1785 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/copycuts",
1786 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",