45 #define HEUR_NAME "undercover" 46 #define HEUR_DESC "solves a sub-CIP determined by a set covering approach" 47 #define HEUR_DISPCHAR 'U' 48 #define HEUR_PRIORITY -1110000 50 #define HEUR_FREQOFS 0 51 #define HEUR_MAXDEPTH -1 52 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 53 #define HEUR_USESSUBSCIP TRUE 56 #define DEFAULT_FIXINGALTS "li" 58 #define DEFAULT_MAXNODES (SCIP_Longint)500 59 #define DEFAULT_MINNODES (SCIP_Longint)500 60 #define DEFAULT_NODESOFS (SCIP_Longint)500 62 #define DEFAULT_CONFLICTWEIGHT 1000.0 63 #define DEFAULT_CUTOFFWEIGHT 1.0 64 #define DEFAULT_INFERENCEWEIGHT 1.0 65 #define DEFAULT_MAXCOVERSIZEVARS 1.0 66 #define DEFAULT_MAXCOVERSIZECONSS SCIP_REAL_MAX 67 #define DEFAULT_MINCOVEREDREL 0.15 68 #define DEFAULT_MINCOVEREDABS 5 69 #define DEFAULT_MINIMPROVE 0.0 70 #define DEFAULT_NODESQUOT 0.1 71 #define DEFAULT_RECOVERDIV 0.9 73 #define DEFAULT_MAXBACKTRACKS 6 74 #define DEFAULT_MAXRECOVERS 0 75 #define DEFAULT_MAXREORDERS 1 77 #define DEFAULT_COVERINGOBJ 'u' 78 #define DEFAULT_FIXINGORDER 'v' 80 #define DEFAULT_BEFORECUTS TRUE 81 #define DEFAULT_FIXINTFIRST FALSE 82 #define DEFAULT_LOCKSROUNDING TRUE 83 #define DEFAULT_ONLYCONVEXIFY FALSE 84 #define DEFAULT_POSTNLP TRUE 85 #define DEFAULT_COVERBD FALSE 86 #define DEFAULT_REUSECOVER FALSE 87 #define DEFAULT_COPYCUTS TRUE 90 #define DEFAULT_RANDSEED 43 93 #define COVERINGOBJS "cdlmtu" 94 #define FIXINGORDERS "CcVv" 96 #define MAXPOSTNLPFAILS 1 97 #define MINTIMELEFT 1.0 98 #define SUBMIPSETUPCOSTS 200 228 if( !consmarker[idx] )
231 consmarker[idx] =
TRUE;
260 struct HessianData* hessiandata,
278 assert(scip != NULL);
279 assert(nlrow != NULL);
280 assert(exprint == NULL || hessiandata != NULL);
281 assert(coveringscip != NULL);
283 assert(coveringvars != NULL);
284 assert(termcounter != NULL);
285 assert(conscounter != NULL);
286 assert(consmarker != NULL);
287 assert(success != NULL);
294 if( exprtree != NULL )
305 if( exprtreevars != NULL && nexprtreevars > 0 )
317 assert(hessiandata != NULL);
318 assert(hessiandata->nvars == 0 || hessiandata->varvals != NULL);
319 assert(hessiandata->nvars == 0 || hessiandata->sparsity != NULL);
325 if( hessiandata->nvars < nexprtreevars )
329 hessiandata->nvars = nexprtreevars;
333 if( hessiandata->evalsol == NULL )
343 for( idx1 = nexprtreevars-1; idx1 >= 0; idx1-- )
354 if( hessiandata->sparsity[idx1*nexprtreevars + idx1]
362 incCounters(termcounter, conscounter, consmarker, probidx1);
371 for( idx2 = nexprtreevars-1; idx2 > idx1; idx2-- )
377 if( !hessiandata->sparsity[idx1*nexprtreevars + idx2] && !hessiandata->sparsity[idx2*nexprtreevars + idx1] )
381 if( hessiandata->sparsity[idx2*nexprtreevars + idx2] && !
termIsConstant(scip, exprtreevars[idx2], 1.0, globalbounds) )
399 coveringconsvars[0] = coveringvars[probidx1];
400 coveringconsvars[1] = coveringvars[probidx2];
404 if( coveringcons == NULL )
406 SCIPdebugMsg(scip,
"failed to create set covering constraint <%s>\n", name);
417 incCounters(termcounter, conscounter, consmarker, probidx1);
418 incCounters(termcounter, conscounter, consmarker, probidx2);
425 for( i = nexprtreevars-1; i >= 0; i-- )
427 assert(exprtreevars[i] != NULL);
433 SCIPdebugMsg(scip,
"strange: inactive variable <%s> detected in nonlinear row <%s>\n",
448 incCounters(termcounter, conscounter, consmarker, probidx1);
471 assert(bilinvar1 != NULL);
472 assert(bilinvar2 != NULL);
477 if( probidx1 == -1 || probidx2 == -1 )
484 if( bilinvar1 == bilinvar2 )
500 incCounters(termcounter, conscounter, consmarker, probidx1);
517 coveringconsvars[0] = coveringvars[probidx1];
518 coveringconsvars[1] = coveringvars[probidx2];
522 if( coveringcons == NULL )
524 SCIPdebugMsg(scip,
"failed to create set covering constraint <%s>\n", name);
533 incCounters(termcounter, conscounter, consmarker, probidx1);
534 incCounters(termcounter, conscounter, consmarker, probidx2);
565 struct HessianData hessiandata;
573 assert(scip != NULL);
574 assert(coveringscip != NULL);
575 assert(coveringvars != NULL);
576 assert(success != NULL);
596 assert(exprint != NULL);
599 hessiandata.evalsol = NULL;
600 hessiandata.varvals = NULL;
601 hessiandata.sparsity = NULL;
602 hessiandata.nvars = 0;
607 for( i = 0; i < nvars; i++ )
629 TRUE,
FALSE, NULL, NULL, NULL, NULL, NULL) );
630 assert(coveringvars[i] != NULL);
651 if( conshdlr != NULL )
653 mapsize =
MAX(mapsize, nnlprows);
658 assert(nlrowmap != NULL);
664 if( conshdlr != NULL )
683 assert(andcons != NULL);
685 assert(andvars != NULL);
698 assert(andvars[v] != NULL);
702 if(
varIsFixed(scip, andvars[v], 0.0, globalbounds) )
716 if( probindex == -1 )
722 assert(repvar != NULL);
747 assert(probindex >= 0);
755 coveringconsvars[ntofix] = coveringvars[probindex];
756 coveringconsvals[ntofix] = 1.0;
763 assert(andres != NULL);
776 if( probindex == -1 )
782 assert(repvar != NULL);
815 assert(probindex >= 0);
831 coveringconsvars[ntofix] = coveringvars[probindex];
832 coveringconsvals[ntofix] = (
SCIP_Real)(ntofix - 1);
841 if( coveringcons == NULL )
843 SCIPdebugMsg(scip,
"failed to create linear constraint <%s>\n", name);
854 for( v = ntofix-1; v >= 0; v-- )
869 if( conshdlr != NULL && coverbd )
887 assert(bdcons != NULL);
889 assert(bdvars != NULL);
901 for( v = nbdvars-1; v >= 0; v-- )
905 assert(bdvars[v] != NULL);
917 if( probindex == -1 )
923 assert(repvar != NULL);
948 assert(probindex >= 0);
956 coveringconsvars[ntofix] = coveringvars[probindex];
957 coveringconsvals[ntofix] = 1.0;
964 assert(ntofix <= nbdvars);
972 if( coveringcons == NULL )
974 SCIPdebugMsg(scip,
"failed to create linear constraint <%s>\n", name);
985 for( v = ntofix-1; v >= 0; v-- )
1000 if( conshdlr != NULL )
1012 assert(indcons != NULL);
1014 assert(binvar != NULL);
1026 if( probindex == -1 )
1034 assert(repvar != NULL);
1053 assert(probindex >= 0);
1056 coveringvar = coveringvars[probindex];
1063 incCounters(termcounter, conscounter, consmarker, probindex);
1069 if( conshdlr != NULL )
1080 assert(quadcons != NULL);
1084 assert(nlrow != NULL);
1085 if( nlrowmap != NULL )
1100 termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
1102 if( *success ==
FALSE )
1111 if( conshdlr != NULL && !onlyconvexify )
1129 assert(soccons != NULL);
1131 assert(socrhsvar != NULL);
1133 assert(soclhsvars != NULL);
1137 assert(nlrow != NULL);
1138 if( nlrowmap != NULL )
1153 if( probindex == -1 )
1170 assert(soclhsvars[v] != NULL);
1174 if( probindex == -1 )
1196 if( coveringcons == NULL )
1198 SCIPdebugMsg(scip,
"failed to create set packing constraint <%s>\n", name);
1208 for( v = ntofix-1; v >= 0; v-- )
1218 if( nlrowmap != NULL )
1229 for( i = nnlrows-1; i >= 0; i-- )
1231 assert(nlrows[i] != NULL);
1240 termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
1242 if( *success ==
FALSE )
1248 switch( coveringobj )
1251 for( i = nvars-1; i >= 0; i-- )
1257 for( i = nvars-1; i >= 0; i-- )
1264 for( i = nvars-1; i >= 0; i-- )
1272 for( i = nvars-1; i >= 0; i-- )
1280 for( i = nvars-1; i >= 0; i-- )
1286 for( i = nvars-1; i >= 0; i-- )
1292 SCIPerrorMessage(
"invalid choice <%c> for covering objective\n", coveringobj);
1301 if( nlrowmap != NULL )
1307 if( hessiandata.nvars > 0 )
1309 assert(hessiandata.evalsol != NULL);
1310 assert(hessiandata.varvals != NULL);
1311 assert(hessiandata.sparsity != NULL);
1320 assert(hessiandata.evalsol == NULL);
1321 assert(hessiandata.varvals == NULL);
1322 assert(hessiandata.sparsity == NULL);
1332 for( i = 0; i < nvars; ++i)
1333 nnonzs += termcounter[i];
1336 for( i = 0; i < nvars; ++i)
1337 if( conscounter[i] > 0 )
1360 int diversification,
1372 assert(scip != NULL);
1373 assert(vars != NULL);
1375 assert(cover != NULL);
1376 assert(coversize >= 1);
1377 assert(coversize <= nvars);
1378 assert(diversification >= 1);
1379 assert(success != NULL);
1380 assert(infeas != NULL);
1396 if( diversification == 1 )
1399 for( i = coversize-1; i >= 0; i-- )
1409 if( nconsvars == 0 )
1430 for( i = coversize-1; i >= 0; i-- )
1434 consvars[nconsvars] = vars[cover[i]];
1435 consvals[nconsvars] = 1.0;
1439 rhs = (
SCIP_Real) (nconsvars-diversification);
1450 nconsvars, consvars, consvals, -
SCIPinfinity(scip), rhs,
1464 if( !(*infeas) && cons != NULL )
1495 assert(scip != NULL);
1497 assert(bdvars != NULL);
1498 assert(bdtypes != NULL);
1499 assert(bdbounds != NULL);
1500 assert(success != NULL);
1512 for( i = bdlen-1; i >= 0 && isbinary; i-- )
1524 for( i = bdlen-1; i >= 0; i-- )
1531 consvars[i] = bdvars[i];
1595 assert(coveringscip != NULL);
1596 assert(coveringvars != NULL);
1597 assert(cover != NULL);
1598 assert(coversize != NULL);
1599 assert(timelimit > 0.0);
1600 assert(memorylimit > 0.0);
1601 assert(success != NULL);
1621 SCIPdebugMsg(coveringscip,
"timelimit = %g, memlimit = %g\n", timelimit, memorylimit);
1651 SCIPwarningMessage(coveringscip,
"Error while solving covering problem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1665 for( i = 0; i < ncoveringvars; i++ )
1667 if( solvals[i] > 0.5 )
1669 cover[*coversize] = i;
1677 SCIPdebugMsg(coveringscip,
"found a feasible cover: %d/%d variables fixed, normalized penalty=%g\n\n",
1711 assert(scip != NULL);
1712 assert(heurdata != NULL);
1714 assert(vars != NULL);
1715 assert(coversize >= 1);
1716 assert(cover != NULL);
1717 assert(lastfailed >= 0);
1722 if( lastfailed == 0 )
1729 sortdown = (heurdata->fixingorder ==
'c' || heurdata->fixingorder ==
'v' );
1733 for( i = coversize-1; i >= 0; i-- )
1738 assert(cover[i] >= 0);
1739 assert(cover[i] < nvars);
1740 var = vars[cover[i]];
1742 if( heurdata->fixingorder ==
'C' || heurdata->fixingorder ==
'c' )
1749 else if( heurdata->fixingorder ==
'V' || heurdata->fixingorder ==
'v' )
1750 scores[i] = cover[i];
1754 assert(scores[i] >= 0.0);
1758 bestscore =
MAX(bestscore, scores[i]);
1760 bestscore = MIN(bestscore, scores[i]);
1765 if( heurdata->fixintfirst )
1767 for( i = coversize-1; i >= 0; i-- )
1772 scores[i] += bestscore+1.0;
1774 scores[i] = bestscore - 1.0/(scores[i]+1.0);
1780 if( lastfailed < coversize )
1783 scores[lastfailed] += bestscore+2.0;
1785 scores[lastfailed] = bestscore - 2.0/(scores[lastfailed]+1.0);
1786 i = cover[lastfailed];
1795 assert(lastfailed >= coversize || cover[0] == i);
1821 assert(scip != NULL);
1822 assert(heurdata != NULL);
1823 assert(var != NULL);
1824 assert(val != NULL);
1825 assert(success != NULL);
1841 if( heurdata->nlpsolved )
1843 assert(!heurdata->nlpfailed);
1850 else if( !heurdata->nlpfailed )
1860 for( i = bdlen-1; i >= 0; i-- )
1866 relaxvar = bdvars[i];
1869 if( i > 0 && bdvars[i-1] == relaxvar )
1871 assert(bdtypes[i] != bdtypes[i-1]);
1908 SCIPdebugMsg(scip,
"solving NLP relaxation to obtain fixing values %s (stat=%d)\n", *success ?
"successful" :
"failed", stat);
1913 heurdata->nnlpfails = 0;
1914 heurdata->nlpsolved =
TRUE;
1922 heurdata->nnlpfails++;
1923 heurdata->nlpfailed =
TRUE;
1924 heurdata->nlpsolved =
FALSE;
1926 SCIPdebugMsg(scip,
"solving NLP relaxation failed (%d time%s%s)\n",
1927 heurdata->nnlpfails, heurdata->nnlpfails > 1 ?
"s" :
"", heurdata->nnlpfails >=
MAXNLPFAILS ?
", will not be called again" :
"");
1974 alternatives[0] = 1.0 - fixval;
1979 alternatives[0] = 0.0;
1980 alternatives[1] = 1.0;
2006 alternatives[*nalternatives] = lb;
2013 alternatives[*nalternatives] = ub;
2020 alternatives[*nalternatives] = (lb+fixval)/2.0;
2027 alternatives[*nalternatives] = (ub+fixval)/2.0;
2031 assert(*nalternatives <= 4);
2055 else if( locksrounding )
2096 assert(scip != NULL);
2097 assert(subscip != NULL);
2098 assert(subvars != NULL);
2099 assert(subsol != NULL);
2100 assert(newsol != NULL);
2101 assert(*newsol != NULL);
2153 assert(scip != NULL);
2154 assert(heur != NULL);
2155 assert(cover != NULL);
2156 assert(fixedvals != NULL);
2157 assert(coversize >= 1);
2158 assert(timelimit > 0.0);
2159 assert(memorylimit > 0.0);
2160 assert(nodelimit >= 1);
2161 assert(nstallnodes >= 1);
2162 assert(validsolved != NULL);
2163 assert(sol != NULL);
2164 assert(*sol == NULL);
2165 assert(nusednodes != NULL);
2167 *validsolved =
FALSE;
2172 assert(heurdata != NULL);
2178 nfixedvars = coversize;
2181 for( i = coversize-1; i >= 0; i-- )
2183 assert(cover[i] >= 0);
2184 assert(cover[i] < nvars);
2186 fixedvars[i] = vars[cover[i]];
2198 heurdata->globalbounds,
FALSE,
TRUE, validsolved) );
2200 if( heurdata->copycuts )
2206 SCIPdebugMsg(scip,
"problem copied, copy %svalid\n", *validsolved ?
"" :
"in");
2209 for( i = nvars-1; i >= 0; i-- )
2212 assert(subvars[i] != NULL);
2234 SCIPwarningMessage(scip,
"unfixing parameter heuristics/" HEUR_NAME "/freq in subscip of undercover heuristic to avoid recursive calls\n");
2239 SCIPdebugMsg(scip,
"timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT
", nstallnodes = %" SCIP_LONGINT_FORMAT
"\n", timelimit, memorylimit, nodelimit, nstallnodes);
2241 SCIPdebugMsg(scip,
"timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT
", nstallnodes = %" SCIP_LONGINT_FORMAT
"\n", timelimit, memorylimit, nodelimit, nstallnodes);
2274 cutoff = (upperbound >= 0 ? 1.0 - heurdata->minimprove : 1.0 + heurdata->minimprove) * upperbound;
2276 cutoff = (1.0 - heurdata->minimprove) * upperbound + heurdata->minimprove *
SCIPgetLowerbound(scip);
2278 cutoff = MIN(upperbound, cutoff);
2281 SCIPdebugMsg(scip,
"adding objective cutoff=%g (minimprove=%g)\n", cutoff, heurdata->minimprove);
2296 SCIPwarningMessage(scip,
"Error while solving subproblem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
2327 assert(subsols != NULL);
2330 for( i = 0; i < nsubsols && !success; i++ )
2342 SCIPdebugMsg(scip,
"heuristic found %d solutions in subproblem; solution %d feasible in original problem\n", nsubsols, i);
2352 *validsolved = *validsolved && i == 1;
2388 assert(scip != NULL);
2389 assert(var != NULL);
2392 assert(infeas != NULL);
2393 assert(bdlen != NULL);
2394 assert(*bdlen >= 0);
2396 assert(bdvars != NULL);
2397 assert(bdtypes != NULL);
2398 assert(bdbounds != NULL);
2421 SCIPdebugMsg(scip,
"tentatively decreasing upper bound of variable <%s> to %g for probing\n",
2425 bdvars[*bdlen] = var;
2428 oldbounds[*bdlen] = oldub;
2433 SCIPdebugMsg(scip,
" --> propagation reduced %" SCIP_LONGINT_FORMAT
" further domains\n", ndomredsfound);
2443 oldbounds[*bdlen] = oldlb;
2448 val = MIN(val, oldub);
2449 val =
MAX(val, oldlb);
2466 SCIPdebugMsg(scip,
"tentatively increasing lower bound of variable <%s> to %g for probing\n",
2470 bdvars[*bdlen] = var;
2477 SCIPdebugMsg(scip,
" --> propagation reduced %" SCIP_LONGINT_FORMAT
" further domains\n", ndomredsfound);
2525 for( i = 0; i < coversize && !(*infeas); i++ )
2557 for( nbacktracks = 0; nbacktracks <= heurdata->maxbacktracks+nfailedvals && *infeas; nbacktracks++ )
2567 if( nbacktracks < heurdata->nfixingalts )
2575 if( (heurdata->fixingalts[nbacktracks] !=
'l' || lpsolved)
2576 && (heurdata->fixingalts[nbacktracks] !=
'n' || !heurdata->nlpfailed)
2577 && (heurdata->fixingalts[nbacktracks] !=
'i' ||
SCIPgetBestSol(scip) != NULL) )
2579 SCIP_CALL(
getFixingValue(scip, heurdata, vars[idx], &val, heurdata->fixingalts[nbacktracks], &success, *bdlen, bdvars, bdtypes, oldbounds) );
2584 SCIPdebugMsg(scip,
"retrieving fixing value '%c' for variable <%s> failed, trying next in the list\n",
2592 if( boundalts == NULL )
2597 assert(nboundalts >= 0);
2598 assert(nboundalts <= 4);
2602 else if( boundalts != NULL && nbacktracks < heurdata->nfixingalts+nboundalts )
2604 assert(nbacktracks-heurdata->nfixingalts >= 0);
2605 val = boundalts[nbacktracks-heurdata->nfixingalts];
2620 val = MIN(val, oldub);
2621 val =
MAX(val, oldlb);
2627 for( j = nusedvals-1; j >= 0 && !usedbefore; j-- )
2637 assert(nusedvals < heurdata->maxbacktracks);
2638 usedvals[nusedvals] = val;
2647 SCIPdebugMsg(scip,
" --> cutoff detected - backtracking\n");
2653 if( boundalts != NULL)
2660 SCIPdebugMsg(scip,
"no feasible fixing value found for variable <%s> in fixing order\n",
2668 fixingvals[i] = val;
2677 assert(*infeas || i == coversize);
2678 assert(!(*infeas) || i < coversize);
2725 assert(scip != NULL);
2726 assert(heur != NULL);
2727 assert(result != NULL);
2745 assert(heurdata != NULL);
2748 heurdata->nlpsolved =
FALSE;
2760 for( i = 0; i < heurdata->nnlconshdlrs; ++i )
2762 assert(nnlconss >= 0);
2766 if( nnlconss < (
SCIP_Real)
SCIPgetNConss(scip) * heurdata->mincoveredrel || nnlconss < heurdata->mincoveredabs )
2768 SCIPdebugMsg(scip,
"too few nonlinear constraints present, not running\n");
2777 maxcoversize = nvars*heurdata->maxcoversizevars;
2782 maxcoversize = MIN(maxcoversize, maxcoversizeconss);
2791 heurdata->coverbd, heurdata->coveringobj, &success) );
2795 SCIPdebugMsg(scip,
"creating covering problem failed, terminating\n");
2800 SCIPdebugMsg(scip,
"covering problem created successfully\n");
2805 for( i = nvars-1; i >= 0; i-- )
2837 heurdata->nfixingalts = (int) strlen(heurdata->fixingalts);
2838 assert(heurdata->nfixingalts >= 1);
2841 while( (ncovers <= heurdata->maxrecovers || reusecover) && !success )
2854 conflictcreated =
FALSE;
2863 if( ncovers == 0 && success )
2867 assert(coversize >= 0);
2868 assert(coversize <= nvars);
2877 SCIPdebugMsg(scip,
"no feasible cover found in covering problem %d, terminating\n", ncovers);
2882 if( coversize == 0 || coversize > maxcoversize )
2884 SCIPdebugMsg(scip,
"terminating due to coversize=%d\n", coversize);
2891 SCIPdebugMsg(scip,
"terminating due to coversize=%d\n", coversize);
2901 lastfailed = reusecover ?
MAX(1, coversize-1) : coversize;
2904 while( ndives <= heurdata->maxreorders && !success )
2911 reordered = reordered || ndives == 0;
2912 SCIPdebugMsg(scip,
"%sordering variables in cover %s\n", ndives == 0 ?
"" :
"re", reordered ?
"" :
"failed");
2919 SCIP_CALL(
fixAndPropagate(scip, heurdata, cover, coversize, fixingvals, &bdlen, bdvars, bdtypes, bdbounds, oldbounds,
2920 &nfixedints, &nfixedconts, &lastfailed, &infeas) );
2926 SCIPdebugMsg(scip,
"%d dive%s of fix-and-propagate for cover %d took %.1f seconds\n", ndives, ndives > 1 ?
"s" :
"", ncovers,
SCIPgetClockTime(scip, clock));
2938 SCIPdebugMsg(scip,
"no feasible fixing values found for cover %d\n", ncovers);
2946 SCIPdebugMsg(scip,
"heuristic successfully fixed %d variables (%d integral, %d continuous) during probing\n",
2947 nfixedints+nfixedconts, nfixedints, nfixedconts);
2951 validsolved =
FALSE;
2956 timelimit, memorylimit, heurdata->maxnodes, nstallnodes, &validsolved, &sol, &nsubnodes) );
2959 heurdata->nusednodes += nsubnodes;
2973 useconf = bdlen > 0 && (bdlen <= minmaxvars || bdlen < maxvarsfac*nvars);
2979 conflictcreated = success;
2982 SCIPdebugMsg(scip,
"subproblem solved (%s), forbidding assignment in original problem %s, %sconflict length=%d\n",
2983 sol == NULL ?
"infeasible" :
"optimal",
2984 success ?
"successful" :
"failed", useconf ?
"" :
"skipped due to ", bdlen);
2988 success = (sol != NULL);
3000 if( nfixedconts == 0 && validsolved )
3002 SCIPdebugMsg(scip,
"subproblem solved to optimality while all covering variables are integral, hence skipping NLP local search\n");
3006 SCIPdebugMsg(scip,
"time limit hit, skipping NLP local search\n");
3008 else if( heurdata->nlpheur == NULL )
3010 SCIPdebugMsg(scip,
"NLP heuristic not found, skipping NLP local search\n");
3020 heurdata->npostnlpfails = 0;
3022 heurdata->npostnlpfails++;
3032 if( !success && ncovers <= heurdata->maxrecovers )
3035 int diversification;
3039 diversification =
MAX(diversification, 1);
3042 SCIP_CALL(
forbidCover(coveringscip, nvars, coveringvars, coversize, cover, diversification, &success, &infeas) );
3046 SCIPdebugMsg(scip,
"recovering problem infeasible (diversification=%d), terminating\n", diversification);
3051 SCIPdebugMsg(scip,
"failed to forbid current cover in the covering problem, terminating\n");
3056 SCIPdebugMsg(scip,
"added constraint to the covering problem in order to forbid current cover\n");
3062 if( heurdata->reusecover && !reusecover && conflictcreated )
3071 SCIPdebugMsg(scip,
"heuristic terminating unsuccessfully\n");
3078 if( heurdata->nlpsolved )
3094 for( i = nvars-1; i >= 0; i-- )
3116 assert(scip != NULL);
3117 assert(heur != NULL);
3132 assert(scip != NULL);
3133 assert(heur != NULL);
3137 assert(heurdata != NULL);
3152 assert(heur != NULL);
3153 assert(scip != NULL);
3157 assert(heurdata != NULL);
3172 assert(heur != NULL);
3173 assert(scip != NULL);
3177 assert(heurdata != NULL);
3192 assert(heur != NULL);
3193 assert(scip != NULL);
3197 assert(heurdata != NULL);
3200 heurdata->nusednodes = 0;
3201 heurdata->npostnlpfails = 0;
3202 heurdata->nnlpfails = 0;
3213 if( heurdata->nlconshdlrs[h] != NULL )
3217 if( heurdata->nlconshdlrs[h] != NULL )
3220 if( heurdata->coverbd )
3223 if( heurdata->nlconshdlrs[h] != NULL )
3228 if( heurdata->nlconshdlrs[h] != NULL )
3232 if( heurdata->nlconshdlrs[h] != NULL )
3236 if( heurdata->nlconshdlrs[h] != NULL )
3240 if( heurdata->nlconshdlrs[h] != NULL )
3243 heurdata->nnlconshdlrs = h;
3244 assert( heurdata->nnlconshdlrs <= 7 );
3264 assert(heur != NULL);
3269 assert(heurdata != NULL);
3292 assert(heur != NULL);
3293 assert(scip != NULL);
3294 assert(result != NULL);
3299 if( nodeinfeasible )
3304 assert(heurdata != NULL);
3311 if( strcmp(heurdata->fixingalts,
"n") == 0 &&
SCIPgetNNlpis(scip) == 0 )
3313 SCIPdebugMsg(scip,
"skipping undercover heuristic: want to use NLP fixing values exclusively, but no NLP solver available\n");
3323 nstallnodes += heurdata->nodesofs;
3326 nstallnodes -= heurdata->nusednodes;
3327 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
3328 nstallnodes =
MAX(nstallnodes, 1);
3331 if( nstallnodes < heurdata->minnodes )
3333 SCIPdebugMsg(scip,
"skipping undercover heuristic: nstallnodes=%" SCIP_LONGINT_FORMAT
", minnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->minnodes);
3343 SCIPdebugMsg(scip,
"skipping undercover heuristic: time left=%g\n", timelimit);
3357 SCIPdebugMsg(scip,
"skipping undercover heuristic: too little memory\n");
3363 for( h = heurdata->nnlconshdlrs-1; h >= 0 && !run; h-- )
3381 for( i = nnlrows-1; i >= 0 && !run; i-- )
3383 assert(nlrows[i] != NULL);
3391 SCIPdebugMsg(scip,
"skipping undercover heuristic: no nonlinear constraints found\n");
3429 heurdata->globalbounds =
FALSE;
3436 assert(heur != NULL);
3447 heurdata->fixingalts = NULL;
3449 "prioritized sequence of fixing values used ('l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution)",
3454 "maximum number of nodes to regard in the subproblem",
3458 "minimum number of nodes required to start the subproblem",
3462 "number of nodes added to the contingent of the total nodes",
3467 "weight for conflict score in fixing order",
3471 "weight for cutoff score in fixing order",
3475 "weight for inference score in fixing order",
3479 "maximum coversize (as fraction of total number of variables)",
3483 "maximum coversize maximum coversize (as ratio to the percentage of non-affected constraints)",
3487 "minimum percentage of nonlinear constraints in the original problem",
3491 "factor by which the heuristic should at least improve the incumbent",
3495 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
3499 "fraction of covering variables in the last cover which need to change their value when recovering",
3504 "minimum number of nonlinear constraints in the original problem",
3508 "maximum number of backtracks in fix-and-propagate",
3512 "maximum number of recoverings",
3516 "maximum number of reorderings of the fixing order",
3521 "objective function of the covering problem (influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks, 'm'in of up/down locks, 'u'nit penalties)",
3525 "order in which variables should be fixed (increasing 'C'onflict score, decreasing 'c'onflict score, increasing 'V'ariable index, decreasing 'v'ariable index",
3530 "should the heuristic be called at root node before cut separation?",
3534 "should integer variables in the cover be fixed first?",
3538 "shall LP values for integer vars be rounded according to locks?",
3542 "should we only fix variables in order to obtain a convex problem?",
3546 "should the NLP heuristic be called to polish a feasible solution?",
3550 "should bounddisjunction constraints be covered (or just copied)?",
3554 "should all active cuts from cutpool be copied to constraints in subproblem?",
3558 "shall the cover be reused if a conflict was added after an infeasible subproblem?",
3590 assert(scip != NULL);
3591 assert(coveringscip != NULL);
3612 assert(*coversize >= 0);
3613 assert(*coversize <= nvars);
3616 for( i = *coversize-1; i >= 0; i-- )
3618 assert(coverinds[i] >= 0);
3619 assert(coverinds[i] < nvars);
3620 cover[i] = vars[coverinds[i]];
3626 SCIPdebugMsg(scip,
"failure: covering problem could not be created\n");
3630 for( i = nvars-1; i >= 0; i-- )
3661 assert(scip != NULL);
3662 assert(coversize != NULL);
3663 assert(success != NULL);
3671 timelimit, memorylimit, objlimit,
3672 globalbounds, onlyconvexify, coverbd, coveringobj, success);
enum SCIP_Result SCIP_RESULT
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
enum SCIP_BoundType SCIP_BOUNDTYPE
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define SCIP_HEURTIMING_DURINGLPLOOP
static SCIP_RETCODE processNlRow(SCIP *scip, SCIP_NLROW *nlrow, SCIP_EXPRINT *exprint, struct HessianData *hessiandata, SCIP *coveringscip, int nvars, SCIP_VAR **coveringvars, int *termcounter, int *conscounter, SCIP_Bool *consmarker, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool *success)
int SCIPgetNNLPNlRows(SCIP *scip)
SCIP_VAR ** SCIPgetLhsVarsSOC(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
SCIP_RETCODE SCIPlinkCurrentSol(SCIP *scip, SCIP_SOL *sol)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_FIXINGORDER
static SCIP_Bool termIsConvex(SCIP *scip, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool sign)
methods to interpret (evaluate) an expression tree "fast"
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
static SCIP_RETCODE getFixingValue(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real *val, char fixalt, SCIP_Bool *success, int bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *oldbounds)
static SCIP_RETCODE computeFixingOrder(SCIP *scip, SCIP_HEURDATA *heurdata, int nvars, SCIP_VAR **vars, int coversize, int *cover, int lastfailed, SCIP_Bool *success)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
int SCIPgetProbingDepth(SCIP *scip)
#define DEFAULT_MAXRECOVERS
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
#define DEFAULT_MAXREORDERS
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
#define DEFAULT_MINCOVEREDABS
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
#define DEFAULT_RECOVERDIV
int SCIPgetNOrigVars(SCIP *scip)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateConsSetcover(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
static SCIP_RETCODE solveCoveringProblem(SCIP *coveringscip, int ncoveringvars, SCIP_VAR **coveringvars, int *coversize, int *cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool *success)
static SCIP_RETCODE roundFixingValue(SCIP *scip, SCIP_Real *val, SCIP_VAR *var, SCIP_Bool locksrounding)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
#define DEFAULT_MAXCOVERSIZECONSS
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Undercover primal heuristic for MINLPs.
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
#define DEFAULT_MINIMPROVE
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)
static SCIP_DECL_HEUREXITSOL(heurExitsolUndercover)
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPexprintCompile(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
int SCIPnlrowGetNQuadVars(SCIP_NLROW *nlrow)
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
int SCIPvarGetProbindex(SCIP_VAR *var)
#define DEFAULT_INFERENCEWEIGHT
#define DEFAULT_MINCOVEREDREL
struct SCIP_HeurData SCIP_HEURDATA
#define SCIPfreeBlockMemory(scip, ptr)
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_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
#define DEFAULT_FIXINTFIRST
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
SCIP_RETCODE SCIPsetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int ival)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_BEFORECUTS
#define SCIPfreeBufferArray(scip, ptr)
static SCIP_DECL_HEUREXIT(heurExitUndercover)
SCIP_RETCODE SCIPcreate(SCIP **scip)
static SCIP_DECL_HEURCOPY(heurCopyUndercover)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define DEFAULT_CONFLICTWEIGHT
#define SCIPallocBlockMemory(scip, ptr)
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
static SCIP_RETCODE createConflict(SCIP *scip, int bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool *success)
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_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_VAR ** SCIPexprtreeGetVars(SCIP_EXPRTREE *tree)
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
const char * SCIPgetProbName(SCIP *scip)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
#define DEFAULT_ONLYCONVEXIFY
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPnlrowGetQuadVars(SCIP_NLROW *nlrow)
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsolveDiveNLP(SCIP *scip)
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPgetNlRowSOC(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_RETCODE SCIPexprintCreate(BMS_BLKMEM *blkmem, SCIP_EXPRINT **exprint)
SCIP_RETCODE SCIPaddConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_NODE *validnode)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
static SCIP_DECL_HEUREXEC(heurExecUndercover)
#define SCIPfreeBufferArrayNull(scip, ptr)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_RETCODE SCIPchgVarBoundsDiveNLP(SCIP *scip, SCIP_VAR *var, SCIP_Real lb, SCIP_Real ub)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIPInterval sign(const SCIPInterval &x)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
const char * SCIPvarGetName(SCIP_VAR *var)
#define DEFAULT_NODESQUOT
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
int SCIPgetNNlpis(SCIP *scip)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
int SCIPexprtreeGetNVars(SCIP_EXPRTREE *tree)
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
SCIP_QUADELEM * SCIPnlrowGetQuadElems(SCIP_NLROW *nlrow)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
#define SCIPstatisticPrintf
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
SCIP_EXPRINTCAPABILITY SCIPexprintGetCapability(void)
SCIP_RETCODE SCIPcomputeCoverUndercover(SCIP *scip, int *coversize, SCIP_VAR **cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
#define DEFAULT_CUTOFFWEIGHT
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
static SCIP_Bool varIsFixed(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_Bool global)
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SCIPallocBufferArray(scip, ptr, num)
public data structures and miscellaneous methods
SCIP_RETCODE SCIPincludeHeurUndercover(SCIP *scip)
#define SCIP_EXPRINTCAPABILITY_HESSIAN
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
static SCIP_RETCODE computeCoverUndercover(SCIP *scip, SCIP *coveringscip, int *coversize, SCIP_VAR **cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
int SCIPgetNLhsVarsSOC(SCIP *scip, SCIP_CONS *cons)
static void incCounters(int *termcounter, int *conscounter, SCIP_Bool *consmarker, int idx)
#define DEFAULT_LOCKSROUNDING
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_VAR * SCIPgetRhsVarSOC(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
static void calculateAlternatives(SCIP *scip, SCIP_VAR *var, SCIP_Real fixval, int *nalternatives, SCIP_Real *alternatives)
int SCIPgetDepth(SCIP *scip)
static SCIP_RETCODE updateTimelimit(SCIP *scip, SCIP_CLOCK *clck, SCIP_Real *timelimit)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
#define DEFAULT_COVERINGOBJ
int SCIPgetNSols(SCIP *scip)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
static SCIP_RETCODE performFixing(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_Bool *infeas, int *bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Real *oldbounds)
SCIP_RETCODE SCIPapplyHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_Longint itercontingent, SCIP_Real timelimit, SCIP_Real minimprove, SCIP_Longint *iterused, SCIP_SOL *resultsol)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_VAR * SCIPgetBinaryVarIndicator(SCIP_CONS *cons)
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
#define SCIP_MAXTREEDEPTH
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
int SCIPgetNVars(SCIP *scip)
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
#define DEFAULT_MAXBACKTRACKS
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
#define DEFAULT_FIXINGALTS
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPendDiveNLP(SCIP *scip)
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)
int SCIPgetNConss(SCIP *scip)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
static SCIP_RETCODE fixAndPropagate(SCIP *scip, SCIP_HEURDATA *heurdata, int *cover, int coversize, SCIP_Real *fixingvals, int *bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Real *oldbounds, int *nfixedints, int *nfixedconts, int *lastfailed, SCIP_Bool *infeas)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_Real SCIPgetRhsCoefSOC(SCIP *scip, SCIP_CONS *cons)
static SCIP_Bool termIsConstant(SCIP *scip, SCIP_VAR *var, SCIP_Real coeff, SCIP_Bool global)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
SCIP_RETCODE SCIPexprintHessianSparsityDense(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Bool *sparsity)
static SCIP_RETCODE copySol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *subsol, SCIP_SOL **newsol)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateConsBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPstartDiveNLP(SCIP *scip)
const char * SCIPnlrowGetName(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEURINIT(heurInitUndercover)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_RETCODE SCIPexprintFree(SCIP_EXPRINT **exprint)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
#define BMSclearMemoryArray(ptr, num)
static SCIP_RETCODE forbidCover(SCIP *scip, int nvars, SCIP_VAR **vars, int coversize, int *cover, int diversification, SCIP_Bool *success, SCIP_Bool *infeas)
#define DEFAULT_REUSECOVER
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
static SCIP_RETCODE solveSubproblem(SCIP *scip, SCIP_HEUR *heur, int coversize, int *cover, SCIP_Real *fixedvals, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint nodelimit, SCIP_Longint nstallnodes, SCIP_Bool *validsolved, SCIP_SOL **sol, SCIP_Longint *nusednodes)
SCIP_Real SCIPnlrowGetLhs(SCIP_NLROW *nlrow)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
static SCIP_RETCODE SCIPapplyUndercover(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint nstallnodes)
static SCIP_DECL_HEURINITSOL(heurInitsolUndercover)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
#define DEFAULT_MAXCOVERSIZEVARS
SCIP_Real * SCIPgetLhsCoefsSOC(SCIP *scip, SCIP_CONS *cons)
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 SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
static SCIP_RETCODE createCoveringProblem(SCIP *scip, SCIP *coveringscip, SCIP_VAR **coveringvars, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
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_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
#define SCIPreallocBufferArray(scip, ptr, num)
static SCIP_DECL_HEURFREE(heurFreeUndercover)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)