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++ )
612 assert(coveringvars[i] !=
NULL);
633 if( conshdlr !=
NULL )
635 mapsize =
MAX(mapsize, nnlprows);
640 assert(nlrowmap !=
NULL);
646 if( conshdlr !=
NULL )
665 assert(andcons !=
NULL);
667 assert(andvars !=
NULL);
680 assert(andvars[v] !=
NULL);
684 if(
varIsFixed(scip, andvars[v], 0.0, globalbounds) )
698 if( probindex == -1 )
704 assert(repvar !=
NULL);
729 assert(probindex >= 0);
737 coveringconsvars[ntofix] = coveringvars[probindex];
738 coveringconsvals[ntofix] = 1.0;
745 assert(andres !=
NULL);
758 if( probindex == -1 )
764 assert(repvar !=
NULL);
797 assert(probindex >= 0);
813 coveringconsvars[ntofix] = coveringvars[probindex];
814 coveringconsvals[ntofix] = (
SCIP_Real)(ntofix - 1);
823 if( coveringcons ==
NULL )
825 SCIPdebugMsg(scip,
"failed to create linear constraint <%s>\n", name);
836 for( v = ntofix-1; v >= 0; v-- )
851 if( conshdlr !=
NULL && coverbd )
869 assert(bdcons !=
NULL);
871 assert(bdvars !=
NULL);
883 for( v = nbdvars-1; v >= 0; v-- )
887 assert(bdvars[v] !=
NULL);
899 if( probindex == -1 )
905 assert(repvar !=
NULL);
930 assert(probindex >= 0);
938 coveringconsvars[ntofix] = coveringvars[probindex];
939 coveringconsvals[ntofix] = 1.0;
946 assert(ntofix <= nbdvars);
954 if( coveringcons ==
NULL )
956 SCIPdebugMsg(scip,
"failed to create linear constraint <%s>\n", name);
967 for( v = ntofix-1; v >= 0; v-- )
982 if( conshdlr !=
NULL )
994 assert(indcons !=
NULL);
996 assert(binvar !=
NULL);
1008 if( probindex == -1 )
1016 assert(repvar !=
NULL);
1035 assert(probindex >= 0);
1038 coveringvar = coveringvars[probindex];
1045 incCounters(termcounter, conscounter, consmarker, probindex);
1051 if( conshdlr !=
NULL )
1062 assert(quadcons !=
NULL);
1066 assert(nlrow !=
NULL);
1067 if( nlrowmap !=
NULL )
1082 termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
1084 if( *success ==
FALSE )
1093 if( conshdlr !=
NULL && !onlyconvexify )
1111 assert(soccons !=
NULL);
1113 assert(socrhsvar !=
NULL);
1115 assert(soclhsvars !=
NULL);
1119 assert(nlrow !=
NULL);
1120 if( nlrowmap !=
NULL )
1135 if( probindex == -1 )
1152 assert(soclhsvars[v] !=
NULL);
1156 if( probindex == -1 )
1178 if( coveringcons ==
NULL )
1180 SCIPdebugMsg(scip,
"failed to create set packing constraint <%s>\n", name);
1190 for( v = ntofix-1; v >= 0; v-- )
1200 if( nlrowmap !=
NULL )
1211 for( i = nnlrows-1; i >= 0; i-- )
1213 assert(nlrows[i] !=
NULL);
1222 termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
1224 if( *success ==
FALSE )
1230 switch( coveringobj )
1233 for( i = nvars-1; i >= 0; i-- )
1239 for( i = nvars-1; i >= 0; i-- )
1246 for( i = nvars-1; i >= 0; i-- )
1254 for( i = nvars-1; i >= 0; i-- )
1262 for( i = nvars-1; i >= 0; i-- )
1268 for( i = nvars-1; i >= 0; i-- )
1274 SCIPerrorMessage(
"invalid choice <%c> for covering objective\n", coveringobj);
1283 if( nlrowmap !=
NULL )
1289 if( hessiandata.nvars > 0 )
1291 assert(hessiandata.evalsol !=
NULL);
1292 assert(hessiandata.varvals !=
NULL);
1293 assert(hessiandata.sparsity !=
NULL);
1302 assert(hessiandata.evalsol ==
NULL);
1303 assert(hessiandata.varvals ==
NULL);
1304 assert(hessiandata.sparsity ==
NULL);
1314 for( i = 0; i < nvars; ++i)
1315 nnonzs += termcounter[i];
1318 for( i = 0; i < nvars; ++i)
1319 if( conscounter[i] > 0 )
1342 int diversification,
1354 assert(scip !=
NULL);
1355 assert(vars !=
NULL);
1357 assert(cover !=
NULL);
1358 assert(coversize >= 1);
1359 assert(coversize <= nvars);
1360 assert(diversification >= 1);
1361 assert(success !=
NULL);
1362 assert(infeas !=
NULL);
1378 if( diversification == 1 )
1381 for( i = coversize-1; i >= 0; i-- )
1391 if( nconsvars == 0 )
1412 for( i = coversize-1; i >= 0; i-- )
1416 consvars[nconsvars] = vars[cover[i]];
1417 consvals[nconsvars] = 1.0;
1421 rhs = (
SCIP_Real) (nconsvars-diversification);
1432 nconsvars, consvars, consvals, -
SCIPinfinity(scip), rhs,
1446 if( !(*infeas) && cons !=
NULL )
1477 assert(scip !=
NULL);
1479 assert(bdvars !=
NULL);
1480 assert(bdtypes !=
NULL);
1481 assert(bdbounds !=
NULL);
1482 assert(success !=
NULL);
1494 for( i = bdlen-1; i >= 0 && isbinary; i-- )
1506 for( i = bdlen-1; i >= 0; i-- )
1513 consvars[i] = bdvars[i];
1577 assert(coveringscip !=
NULL);
1578 assert(coveringvars !=
NULL);
1579 assert(cover !=
NULL);
1580 assert(coversize !=
NULL);
1581 assert(timelimit > 0.0);
1582 assert(memorylimit > 0.0);
1583 assert(success !=
NULL);
1603 SCIPdebugMsg(coveringscip,
"timelimit = %g, memlimit = %g\n", timelimit, memorylimit);
1633 SCIPwarningMessage(coveringscip,
"Error while solving covering problem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1647 for( i = 0; i < ncoveringvars; i++ )
1649 if( solvals[i] > 0.5 )
1651 cover[*coversize] = i;
1659 SCIPdebugMsg(coveringscip,
"found a feasible cover: %d/%d variables fixed, normalized penalty=%g\n\n",
1693 assert(scip !=
NULL);
1694 assert(heurdata !=
NULL);
1696 assert(vars !=
NULL);
1697 assert(coversize >= 1);
1698 assert(cover !=
NULL);
1699 assert(lastfailed >= 0);
1704 if( lastfailed == 0 )
1711 sortdown = (heurdata->fixingorder ==
'c' || heurdata->fixingorder ==
'v' );
1715 for( i = coversize-1; i >= 0; i-- )
1720 assert(cover[i] >= 0);
1721 assert(cover[i] < nvars);
1722 var = vars[cover[i]];
1724 if( heurdata->fixingorder ==
'C' || heurdata->fixingorder ==
'c' )
1731 else if( heurdata->fixingorder ==
'V' || heurdata->fixingorder ==
'v' )
1732 scores[i] = cover[i];
1736 assert(scores[i] >= 0.0);
1740 bestscore =
MAX(bestscore, scores[i]);
1742 bestscore =
MIN(bestscore, scores[i]);
1747 if( heurdata->fixintfirst )
1749 for( i = coversize-1; i >= 0; i-- )
1754 scores[i] += bestscore+1.0;
1756 scores[i] = bestscore - 1.0/(scores[i]+1.0);
1762 if( lastfailed < coversize )
1765 scores[lastfailed] += bestscore+2.0;
1767 scores[lastfailed] = bestscore - 2.0/(scores[lastfailed]+1.0);
1768 i = cover[lastfailed];
1777 assert(lastfailed >= coversize || cover[0] == i);
1803 assert(scip !=
NULL);
1804 assert(heurdata !=
NULL);
1805 assert(var !=
NULL);
1806 assert(val !=
NULL);
1807 assert(success !=
NULL);
1823 if( heurdata->nlpsolved )
1825 assert(!heurdata->nlpfailed);
1832 else if( !heurdata->nlpfailed )
1842 for( i = bdlen-1; i >= 0; i-- )
1848 relaxvar = bdvars[i];
1851 if( i > 0 && bdvars[i-1] == relaxvar )
1853 assert(bdtypes[i] != bdtypes[i-1]);
1890 SCIPdebugMsg(scip,
"solving NLP relaxation to obtain fixing values %s (stat=%d)\n", *success ?
"successful" :
"failed", stat);
1895 heurdata->nnlpfails = 0;
1896 heurdata->nlpsolved =
TRUE;
1904 heurdata->nnlpfails++;
1905 heurdata->nlpfailed =
TRUE;
1906 heurdata->nlpsolved =
FALSE;
1908 SCIPdebugMsg(scip,
"solving NLP relaxation failed (%d time%s%s)\n",
1909 heurdata->nnlpfails, heurdata->nnlpfails > 1 ?
"s" :
"", heurdata->nnlpfails >=
MAXNLPFAILS ?
", will not be called again" :
"");
1950 alternatives[0] = 1.0 - fixval;
1955 alternatives[0] = 0.0;
1956 alternatives[1] = 1.0;
1982 alternatives[*nalternatives] = lb;
1989 alternatives[*nalternatives] = ub;
1996 alternatives[*nalternatives] = (lb+fixval)/2.0;
2003 alternatives[*nalternatives] = (ub+fixval)/2.0;
2007 assert(*nalternatives <= 4);
2031 else if( locksrounding )
2072 assert(scip !=
NULL);
2073 assert(subscip !=
NULL);
2074 assert(subvars !=
NULL);
2075 assert(subsol !=
NULL);
2076 assert(newsol !=
NULL);
2077 assert(*newsol !=
NULL);
2129 assert(scip !=
NULL);
2130 assert(heur !=
NULL);
2131 assert(cover !=
NULL);
2132 assert(fixedvals !=
NULL);
2133 assert(coversize >= 1);
2134 assert(timelimit > 0.0);
2135 assert(memorylimit > 0.0);
2136 assert(nodelimit >= 1);
2137 assert(nstallnodes >= 1);
2138 assert(validsolved !=
NULL);
2139 assert(sol !=
NULL);
2140 assert(*sol ==
NULL);
2141 assert(nusednodes !=
NULL);
2143 *validsolved =
FALSE;
2148 assert(heurdata !=
NULL);
2154 nfixedvars = coversize;
2157 for( i = coversize-1; i >= 0; i-- )
2159 assert(cover[i] >= 0);
2160 assert(cover[i] < nvars);
2162 fixedvars[i] = vars[cover[i]];
2174 heurdata->globalbounds,
FALSE,
TRUE, validsolved) );
2176 if( heurdata->copycuts )
2182 SCIPdebugMsg(scip,
"problem copied, copy %svalid\n", *validsolved ?
"" :
"in");
2185 for( i = nvars-1; i >= 0; i-- )
2188 assert(subvars[i] !=
NULL);
2210 SCIPwarningMessage(scip,
"unfixing parameter heuristics/" HEUR_NAME "/freq in subscip of undercover heuristic to avoid recursive calls\n");
2215 SCIPdebugMsg(scip,
"timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT
", nstallnodes = %" SCIP_LONGINT_FORMAT
"\n", timelimit, memorylimit, nodelimit, nstallnodes);
2217 SCIPdebugMsg(scip,
"timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT
", nstallnodes = %" SCIP_LONGINT_FORMAT
"\n", timelimit, memorylimit, nodelimit, nstallnodes);
2250 cutoff = (upperbound >= 0 ? 1.0 - heurdata->minimprove : 1.0 + heurdata->minimprove) * upperbound;
2252 cutoff = (1.0 - heurdata->minimprove) * upperbound + heurdata->minimprove *
SCIPgetLowerbound(scip);
2254 cutoff =
MIN(upperbound, cutoff);
2257 SCIPdebugMsg(scip,
"adding objective cutoff=%g (minimprove=%g)\n", cutoff, heurdata->minimprove);
2272 SCIPwarningMessage(scip,
"Error while solving subproblem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
2303 assert(subsols !=
NULL);
2306 for( i = 0; i < nsubsols && !success; i++ )
2318 SCIPdebugMsg(scip,
"heuristic found %d solutions in subproblem; solution %d feasible in original problem\n", nsubsols, i);
2328 *validsolved = *validsolved && i == 1;
2364 assert(scip !=
NULL);
2365 assert(var !=
NULL);
2368 assert(infeas !=
NULL);
2369 assert(bdlen !=
NULL);
2370 assert(*bdlen >= 0);
2372 assert(bdvars !=
NULL);
2373 assert(bdtypes !=
NULL);
2374 assert(bdbounds !=
NULL);
2397 SCIPdebugMsg(scip,
"tentatively decreasing upper bound of variable <%s> to %g for probing\n",
2401 bdvars[*bdlen] = var;
2404 oldbounds[*bdlen] = oldub;
2409 SCIPdebugMsg(scip,
" --> propagation reduced %" SCIP_LONGINT_FORMAT
" further domains\n", ndomredsfound);
2419 oldbounds[*bdlen] = oldlb;
2424 val =
MIN(val, oldub);
2425 val =
MAX(val, oldlb);
2442 SCIPdebugMsg(scip,
"tentatively increasing lower bound of variable <%s> to %g for probing\n",
2446 bdvars[*bdlen] = var;
2453 SCIPdebugMsg(scip,
" --> propagation reduced %" SCIP_LONGINT_FORMAT
" further domains\n", ndomredsfound);
2501 for( i = 0; i < coversize && !(*infeas); i++ )
2533 for( nbacktracks = 0; nbacktracks <= heurdata->maxbacktracks+nfailedvals && *infeas; nbacktracks++ )
2543 if( nbacktracks < heurdata->nfixingalts )
2551 if( (heurdata->fixingalts[nbacktracks] !=
'l' || lpsolved)
2552 && (heurdata->fixingalts[nbacktracks] !=
'n' || !heurdata->nlpfailed)
2555 SCIP_CALL(
getFixingValue(scip, heurdata, vars[idx], &val, heurdata->fixingalts[nbacktracks], &success, *bdlen, bdvars, bdtypes, oldbounds) );
2560 SCIPdebugMsg(scip,
"retrieving fixing value '%c' for variable <%s> failed, trying next in the list\n",
2568 if( boundalts ==
NULL )
2573 assert(nboundalts >= 0);
2574 assert(nboundalts <= 4);
2578 else if( boundalts !=
NULL && nbacktracks < heurdata->nfixingalts+nboundalts )
2580 assert(nbacktracks-heurdata->nfixingalts >= 0);
2581 val = boundalts[nbacktracks-heurdata->nfixingalts];
2596 val =
MIN(val, oldub);
2597 val =
MAX(val, oldlb);
2603 for( j = nusedvals-1; j >= 0 && !usedbefore; j-- )
2613 assert(nusedvals < heurdata->maxbacktracks);
2614 usedvals[nusedvals] = val;
2623 SCIPdebugMsg(scip,
" --> cutoff detected - backtracking\n");
2629 if( boundalts !=
NULL)
2636 SCIPdebugMsg(scip,
"no feasible fixing value found for variable <%s> in fixing order\n",
2644 fixingvals[i] = val;
2653 assert(*infeas || i == coversize);
2654 assert(!(*infeas) || i < coversize);
2701 assert(scip !=
NULL);
2702 assert(heur !=
NULL);
2703 assert(result !=
NULL);
2721 assert(heurdata !=
NULL);
2724 heurdata->nlpsolved =
FALSE;
2736 for( i = 0; i < heurdata->nnlconshdlrs; ++i )
2738 assert(nnlconss >= 0);
2742 if( nnlconss < (
SCIP_Real)
SCIPgetNConss(scip) * heurdata->mincoveredrel || nnlconss < heurdata->mincoveredabs )
2744 SCIPdebugMsg(scip,
"too few nonlinear constraints present, not running\n");
2753 maxcoversize = nvars*heurdata->maxcoversizevars;
2758 maxcoversize =
MIN(maxcoversize, maxcoversizeconss);
2767 heurdata->coverbd, heurdata->coveringobj, &success) );
2771 SCIPdebugMsg(scip,
"creating covering problem failed, terminating\n");
2776 SCIPdebugMsg(scip,
"covering problem created successfully\n");
2781 for( i = nvars-1; i >= 0; i-- )
2813 heurdata->nfixingalts = (int) strlen(heurdata->fixingalts);
2814 assert(heurdata->nfixingalts >= 1);
2817 while( (ncovers <= heurdata->maxrecovers || reusecover) && !success )
2830 conflictcreated =
FALSE;
2839 if( ncovers == 0 && success )
2843 assert(coversize >= 0);
2844 assert(coversize <= nvars);
2853 SCIPdebugMsg(scip,
"no feasible cover found in covering problem %d, terminating\n", ncovers);
2858 if( coversize == 0 || coversize > maxcoversize )
2860 SCIPdebugMsg(scip,
"terminating due to coversize=%d\n", coversize);
2867 SCIPdebugMsg(scip,
"terminating due to coversize=%d\n", coversize);
2877 lastfailed = reusecover ?
MAX(1, coversize-1) : coversize;
2880 while( ndives <= heurdata->maxreorders && !success )
2887 reordered = reordered || ndives == 0;
2888 SCIPdebugMsg(scip,
"%sordering variables in cover %s\n", ndives == 0 ?
"" :
"re", reordered ?
"" :
"failed");
2895 SCIP_CALL(
fixAndPropagate(scip, heurdata, cover, coversize, fixingvals, &bdlen, bdvars, bdtypes, bdbounds, oldbounds,
2896 &nfixedints, &nfixedconts, &lastfailed, &infeas) );
2902 SCIPdebugMsg(scip,
"%d dive%s of fix-and-propagate for cover %d took %.1f seconds\n", ndives, ndives > 1 ?
"s" :
"", ncovers,
SCIPgetClockTime(scip, clock));
2914 SCIPdebugMsg(scip,
"no feasible fixing values found for cover %d\n", ncovers);
2922 SCIPdebugMsg(scip,
"heuristic successfully fixed %d variables (%d integral, %d continuous) during probing\n",
2923 nfixedints+nfixedconts, nfixedints, nfixedconts);
2927 validsolved =
FALSE;
2932 timelimit, memorylimit, heurdata->maxnodes, nstallnodes, &validsolved, &sol, &nsubnodes) );
2935 heurdata->nusednodes += nsubnodes;
2949 useconf = bdlen > 0 && (bdlen <= minmaxvars || bdlen < maxvarsfac*nvars);
2955 conflictcreated = success;
2958 SCIPdebugMsg(scip,
"subproblem solved (%s), forbidding assignment in original problem %s, %sconflict length=%d\n",
2959 sol ==
NULL ?
"infeasible" :
"optimal",
2960 success ?
"successful" :
"failed", useconf ?
"" :
"skipped due to ", bdlen);
2964 success = (sol !=
NULL);
2976 if( nfixedconts == 0 && validsolved )
2978 SCIPdebugMsg(scip,
"subproblem solved to optimality while all covering variables are integral, hence skipping NLP local search\n");
2982 SCIPdebugMsg(scip,
"time limit hit, skipping NLP local search\n");
2984 else if( heurdata->nlpheur ==
NULL )
2986 SCIPdebugMsg(scip,
"NLP heuristic not found, skipping NLP local search\n");
2996 heurdata->npostnlpfails = 0;
2998 heurdata->npostnlpfails++;
3008 if( !success && ncovers <= heurdata->maxrecovers )
3011 int diversification;
3015 diversification =
MAX(diversification, 1);
3018 SCIP_CALL(
forbidCover(coveringscip, nvars, coveringvars, coversize, cover, diversification, &success, &infeas) );
3022 SCIPdebugMsg(scip,
"recovering problem infeasible (diversification=%d), terminating\n", diversification);
3027 SCIPdebugMsg(scip,
"failed to forbid current cover in the covering problem, terminating\n");
3032 SCIPdebugMsg(scip,
"added constraint to the covering problem in order to forbid current cover\n");
3038 if( heurdata->reusecover && !reusecover && conflictcreated )
3047 SCIPdebugMsg(scip,
"heuristic terminating unsuccessfully\n");
3054 if( heurdata->nlpsolved )
3070 for( i = nvars-1; i >= 0; i-- )
3093 assert(heur !=
NULL);
3108 assert(scip !=
NULL);
3109 assert(heur !=
NULL);
3113 assert(heurdata !=
NULL);
3128 assert(heur !=
NULL);
3129 assert(scip !=
NULL);
3133 assert(heurdata !=
NULL);
3148 assert(heur !=
NULL);
3149 assert(scip !=
NULL);
3153 assert(heurdata !=
NULL);
3168 assert(heur !=
NULL);
3169 assert(scip !=
NULL);
3173 assert(heurdata !=
NULL);
3176 heurdata->nusednodes = 0;
3177 heurdata->npostnlpfails = 0;
3178 heurdata->nnlpfails = 0;
3189 if( heurdata->nlconshdlrs[h] !=
NULL )
3193 if( heurdata->nlconshdlrs[h] !=
NULL )
3196 if( heurdata->coverbd )
3199 if( heurdata->nlconshdlrs[h] !=
NULL )
3204 if( heurdata->nlconshdlrs[h] !=
NULL )
3208 if( heurdata->nlconshdlrs[h] !=
NULL )
3212 if( heurdata->nlconshdlrs[h] !=
NULL )
3216 if( heurdata->nlconshdlrs[h] !=
NULL )
3219 heurdata->nnlconshdlrs = h;
3220 assert( heurdata->nnlconshdlrs <= 7 );
3240 assert(heur !=
NULL);
3245 assert(heurdata !=
NULL);
3268 assert(heur !=
NULL);
3269 assert(scip !=
NULL);
3270 assert(result !=
NULL);
3275 if( nodeinfeasible )
3280 assert(heurdata !=
NULL);
3287 if( strcmp(heurdata->fixingalts,
"n") == 0 &&
SCIPgetNNlpis(scip) == 0 )
3289 SCIPdebugMsg(scip,
"skipping undercover heuristic: want to use NLP fixing values exclusively, but no NLP solver available\n");
3299 nstallnodes += heurdata->nodesofs;
3302 nstallnodes -= heurdata->nusednodes;
3303 nstallnodes =
MIN(nstallnodes, heurdata->maxnodes);
3304 nstallnodes =
MAX(nstallnodes, 1);
3307 if( nstallnodes < heurdata->minnodes )
3309 SCIPdebugMsg(scip,
"skipping undercover heuristic: nstallnodes=%" SCIP_LONGINT_FORMAT
", minnodes=%" SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->minnodes);
3319 SCIPdebugMsg(scip,
"skipping undercover heuristic: time left=%g\n", timelimit);
3333 SCIPdebugMsg(scip,
"skipping undercover heuristic: too little memory\n");
3339 for( h = heurdata->nnlconshdlrs-1; h >= 0 && !run; h-- )
3357 for( i = nnlrows-1; i >= 0 && !run; i-- )
3359 assert(nlrows[i] !=
NULL);
3367 SCIPdebugMsg(scip,
"skipping undercover heuristic: no nonlinear constraints found\n");
3405 heurdata->globalbounds =
FALSE;
3412 assert(heur !=
NULL);
3423 heurdata->fixingalts =
NULL;
3425 "prioritized sequence of fixing values used ('l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution)",
3430 "maximum number of nodes to regard in the subproblem",
3434 "minimum number of nodes required to start the subproblem",
3438 "number of nodes added to the contingent of the total nodes",
3443 "weight for conflict score in fixing order",
3447 "weight for cutoff score in fixing order",
3451 "weight for inference score in fixing order",
3455 "maximum coversize (as fraction of total number of variables)",
3459 "maximum coversize maximum coversize (as ratio to the percentage of non-affected constraints)",
3463 "minimum percentage of nonlinear constraints in the original problem",
3467 "factor by which the heuristic should at least improve the incumbent",
3471 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
3475 "fraction of covering variables in the last cover which need to change their value when recovering",
3480 "minimum number of nonlinear constraints in the original problem",
3484 "maximum number of backtracks in fix-and-propagate",
3488 "maximum number of recoverings",
3492 "maximum number of reorderings of the fixing order",
3497 "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)",
3501 "order in which variables should be fixed (increasing 'C'onflict score, decreasing 'c'onflict score, increasing 'V'ariable index, decreasing 'v'ariable index",
3506 "should the heuristic be called at root node before cut separation?",
3510 "should integer variables in the cover be fixed first?",
3514 "shall LP values for integer vars be rounded according to locks?",
3518 "should we only fix variables in order to obtain a convex problem?",
3522 "should the NLP heuristic be called to polish a feasible solution?",
3526 "should bounddisjunction constraints be covered (or just copied)?",
3530 "should all active cuts from cutpool be copied to constraints in subproblem?",
3534 "shall the cover be reused if a conflict was added after an infeasible subproblem?",
3566 assert(scip !=
NULL);
3567 assert(coversize !=
NULL);
3568 assert(success !=
NULL);
3592 assert(*coversize >= 0);
3593 assert(*coversize <= nvars);
3596 for( i = *coversize-1; i >= 0; i-- )
3598 assert(coverinds[i] >= 0);
3599 assert(coverinds[i] < nvars);
3600 cover[i] = vars[coverinds[i]];
3606 SCIPdebugMsg(scip,
"failure: covering problem could not be created\n");
3610 for( i = nvars-1; i >= 0; i-- )
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)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
enum SCIP_BoundType SCIP_BOUNDTYPE
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define SCIP_HEURTIMING_DURINGLPLOOP
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
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 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)
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
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)
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)
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
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)