heur_nlpdiving.c
Go to the documentation of this file.
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
90 #define DEFAULT_MAXNLPITERREL 10 /**< additional allowed number of NLP iterations relative to successfully found solutions */
91 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
93 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
95 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
96 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
97 #define DEFAULT_MINSUCCQUOT 0.1 /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
98 #define DEFAULT_MAXFEASNLPS 10 /**< maximal number of NLPs with feasible solution to solve during one dive */
99 #define DEFAULT_FIXQUOT 0.2 /**< percentage of fractional variables that should be fixed before the next NLP solve */
100 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
102 #define DEFAULT_PREFERLPFRACS FALSE /**< prefer variables that are also fractional in LP solution? */
104 #define DEFAULT_SOLVESUBMIP FALSE /**< should a sub-MIP be solved if all cover variables are fixed? */
105 #define DEFAULT_NLPSTART 's' /**< which point should be used as starting point for the NLP solver? */
106 #define DEFAULT_VARSELRULE 'd' /**< which variable selection should be used? ('f'ractionality, 'c'oefficient,
116 {
121 int maxnlpiterrel; /**< additional allowed number of NLP iterations relative to successfully found solutions */
122 SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
124 SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
126 SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
127 SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
129 SCIP_Real minsuccquot; /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
130 SCIP_Real fixquot; /**< percentage of fractional variables that should be fixed before the next NLP solve */
160 /** gets fractional variables of last NLP solution along with solution values and fractionalities
162 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
174 SCIP_Real** nlpcandssol, /**< pointer to store the array of NLP fractional variables solution values, or NULL */
175 SCIP_Real** nlpcandsfrac, /**< pointer to store the array of NLP fractional variables fractionalities, or NULL */
191 /* values may be outside the domain in exact arithmetic, but inside the domain within relative tolerance, and still
192 * slightly fractional, because SCIPisFeasIntegral() uses absolute tolerance; project value onto domain to avoid this
199 if( (*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c]) || (*nlpcandssol)[c] > SCIPvarGetUbLocal((*nlpcands)[c]) )
241 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
255 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
298 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
299 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
304 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
309 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
334 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
351 if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
380 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
415 * - round variable with a small ratio between the increase in the objective and the locking numbers
417 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
431 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
467 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
468 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
479 nlocks = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) + SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
511 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
525 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
569 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
570 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
575 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
580 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
605 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
662 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
680 if( bestcandmayrounddown || bestcandmayroundup || nviolrows + frac < bestnviolrows + bestcandfrac )
698 /** calculates the pseudocost score for a given variable w.r.t. a given solution value and a given rounding direction */
731 * to avoid performance variability caused by numerics we use random numbers to decide whether we want to roundup or
739 || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) - 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
742 || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) + 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
744 else if( SCIPisLT(scip, frac, 0.3) || (SCIPisEQ(scip, frac, 0.3) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
746 else if( SCIPisGT(scip, frac, 0.7) || (SCIPisEQ(scip, frac, 0.7) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
771 * - of these variables, round variable with largest rel. difference of pseudo cost values in corresponding
776 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
790 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
833 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
838 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
842 * - if variable may be rounded in both directions, round corresponding to the pseudo cost values
843 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
892 * - of these variables, round a variable to its value in direction of incumbent solution, and choose the
895 * - round variable in direction that destroys LP feasibility (other direction is checked by SCIProundSol())
898 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
913 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
959 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
960 if( SCIPisLT(scip, solval, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, solval, SCIPvarGetUbLocal(var)) )
973 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
977 * - if variable may be rounded in both directions, round corresponding to its value in incumbent solution
978 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
996 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1013 if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
1034 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1068 * - choose a variable for which the sum of the distances from the relaxations' solutions to a common
1084 SCIP_Real* bestboundval, /**< pointer to store the bound, the best candidate should be rounded to */
1085 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
1086 SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
1127 assert(SCIPisLE(scip, SCIPvarGetLbLocal(var), lpsol) && SCIPisLE(scip, lpsol, SCIPvarGetUbLocal(var)));
1129 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
1130 if( SCIPisLT(scip, nlpsol, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpsol, SCIPvarGetUbLocal(var)) )
1135 /* if this candidate is trivially roundable, and we already know a candidate that is not, continue */
1149 /* if both values are in the same interval, find out which integer is (in sum) the closer one, this will be the
1187 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1223 /** creates a new solution for the original problem by copying the solution of the subproblem */
1255 subsolvals[i] = MIN(MAX(0.0, SCIPvarGetLbLocal(vars[i])), SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
1298 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", NULL, NULL, 0, FALSE, FALSE, FALSE,
1304 assert(SCIPhashmapGetImage(varmap, covervars[c]) != NULL); /* cover variable cannot be relaxation-only, thus must have been copied */
1306 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c])),
1340 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
1346 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
1351 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
1394 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
1472 otherbound = (eventtype & SCIP_EVENTTYPE_LBCHANGED) ? SCIPvarGetUbLocal(var) : SCIPvarGetLbLocal(var);
1500 /* SCIPdebugMsg(scip, "changed bound of cover variable <%s> from %f to %f (nfixedcovervars: %d).\n", SCIPvarGetName(var),
1579 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1601 SCIPstatisticMessage("%-30s %5" SCIP_LONGINT_FORMAT " sols in %5" SCIP_LONGINT_FORMAT " runs, %6.1fs, %7d NLP iters in %5d NLP solves, %5.1f avg., %3d%% success %3d%% cutoff %3d%% depth %3d%% nlperror\n",
1602 SCIPgetProbName(scip), SCIPheurGetNSolsFound(heur), SCIPheurGetNCalls(heur), SCIPheurGetTime(heur),
1603 heurdata->nnlpiterations, heurdata->nnlpsolves, heurdata->nnlpiterations/MAX(1.0,(SCIP_Real)heurdata->nnlpsolves),
1604 (100*heurdata->nsuccess) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailcutoff) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfaildepth) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailnlperror) / (int)SCIPheurGetNCalls(heur)
1691 /* only call heuristic, if the current node will not be cutoff, e.g., due to a (integer and NLP-)feasible LP solution */
1700 if( (SCIPheurGetNSolsFound(heur) + 1.0) / (SCIP_Real)(SCIPheurGetNCalls(heur) + 1.0) < heurdata->minsuccquot )
1711 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
1724 maxnnlpiterations += (int)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxnlpiterrel);
1732 maxnnlpiterations = (int)MAX((SCIP_Real) maxnnlpiterations, (SCIP_Real) heurdata->nnlpiterations + 1.2*avgnnlpiterations);
1753 .fastfail = heurdata->nlpfastfail ? SCIP_NLPPARAM_FASTFAIL_AGGRESSIVE : SCIP_NLPPARAM_FASTFAIL_CONSERVATIVE) ); /*lint !e666*/
1785 SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
1802 * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
1803 * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
1824 /* for guided diving: get best solution that should guide the search; if this solution lives in the original variable space,
1893 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1905 SCIP_CALL( SCIPcomputeCoverUndercover(scip, &ncovervars, covervars, timelimit, memorylimit, SCIPinfinity(scip), FALSE, FALSE, FALSE, 'u', &covercomputed) );
1910 /* a cover can be empty, if the cover computation reveals that all nonlinear constraints are linear w.r.t. current variable fixations */
1928 SCIP_CALL( SCIPcatchVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr,
1949 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing nlpdiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
1950 SCIPgetNNodes(scip), SCIPgetDepth(scip), nnlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
1968 /* dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
1970 * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
1983 while( !nlperror && !cutoff && (nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_UNKNOWN) && nnlpcands > 0
1986 || (nfeasnlps < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound))
1992 /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
2012 SCIP_CALL( chooseCoefVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2021 SCIP_CALL( chooseVeclenVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2030 SCIP_CALL( choosePscostVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2039 SCIP_CALL( chooseGuidedVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, bestsol, varincover, covercomputed,
2048 /* double diving only works if we have both relaxations at hand, otherwise we fall back to fractional diving */
2057 SCIP_CALL( SCIPgetSolVals(scip, heurdata->sol, npseudocands, pseudocands, pseudocandsnlpsol) );
2058 SCIP_CALL( chooseDoubleVar(scip, heurdata, pseudocands, pseudocandsnlpsol, pseudocandslpsol, npseudocands,
2068 SCIP_CALL( chooseFracVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2083 * this should only happen if they are slightly outside bounds (i.e., still within feastol, relative tolerance),
2084 * but far enough out to be considered as fractional (within feastol, but using absolute tolerance)
2096 SCIPdebugMsg(scip, "nlpdiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2114 /* if all variables have been found to be essentially integral (even though there is some numerical doubt, see comment above), then stop */
2127 /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2132 SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2133 SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2137 if( SCIPisFeasLT(scip, backtrackvarval, SCIPvarGetLbLocal(backtrackvar)) || SCIPisFeasGT(scip, backtrackvarval, SCIPvarGetUbLocal(backtrackvar)) )
2139 SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2140 SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2148 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2150 SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2156 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2158 SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2175 /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2180 SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2185 if( SCIPisFeasLT(scip, bestboundval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestboundval, SCIPvarGetUbLocal(var)) )
2187 SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2197 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2204 /* remember variable for backtracking, if we have none yet (e.g., we are just after NLP solve) or we are half way to the next NLP solve */
2205 if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2216 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2223 /* remember variable for backtracking, if we have none yet (e.g., we are just after NLP solve) or we are half way to the next NLP solve */
2224 if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2251 SCIPdebugMsg(scip, " *** cutoff detected in propagation at level %d\n", SCIPgetProbingDepth(scip));
2285 assert(SCIPvarGetType(covervars[c]) >= SCIP_VARTYPE_IMPLINT || SCIPisFeasIntegral(scip, nlpsolval));
2289 * @todo do we need a new probing node for each fixing? if one of these fixings leads to a cutoff
2305 /* if covervar was implicit integer and fractional, then nlpsolval may be below lower bound now, so adjust to new bound */
2343 /* get LP solution status, objective value, and fractional variables, that should be integral */
2345 assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
2346 (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))));
2377 SCIPdebugMsg(scip, " *** cutoff detected in LP solving at level %d, lpsolstat = %d\n", SCIPgetProbingDepth(scip), lpsolstat);
2398 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
2437 "Error while solving NLP in nlpdiving heuristic; NLP solve terminated with code <%d>\n", termstat);
2447 /* get NLP solution status, objective value, and fractional variables, that should be integral */
2453 SCIPdebugMsg(scip, " *** cutoff detected in NLP solving at level %d, nlpsolstat: %d\n", SCIPgetProbingDepth(scip), nlpsolstat);
2461 /* forget previous backtrack variable, we will never go back to a depth before the current one */
2483 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking one step\n", SCIPgetProbingDepth(scip));
2486 /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2494 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking to depth %d\n", SCIPgetProbingDepth(scip), backtrackdepth);
2497 /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2506 /* in case, we are feasible after backtracking, fix less variables at once in continuing diving
2522 SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
2524 SCIPdebugMsg(scip, " -> nlpsolstat=%d, objval=%g/%g, nfrac nlp=%d lp=%d\n", nlpsolstat, objval, searchbound, nnlpcands, nlpbranchcands);
2529 if( nlperror || (nlpsolstat > SCIP_NLPSOLSTAT_LOCINFEASIBLE && nlpsolstat != SCIP_NLPSOLSTAT_UNKNOWN) )
2531 SCIPdebugMsgPrint(scip, "NLP bad status - nlperror: %ud nlpsolstat: %d \n", nlperror, nlpsolstat);
2541 || (divedepth < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound) ) )
2543 SCIPdebugMsgPrint(scip, "TOO DEEP - divedepth: %4d cands halfed: %d ltmaxdepth: %d ltmaxiter: %d bound: %d\n", divedepth,
2544 (nnlpcands > startnnlpcands - divedepth/2), (divedepth >= maxdivedepth), (heurdata->nnlpiterations >= maxnnlpiterations),
2554 SCIPdebugMsgPrint(scip, "UNKNOWN, very mysterical reason\n"); /* see also special case var == NULL (bestcand == -1) after choose*Var above */
2563 SCIPdebugMsg(scip, "nlpdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2567 * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
2568 * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
2596 assert(heurdata->nfixedcovervars >= 0); /* variables might have been globally fixed in propagation */
2605 SCIP_CALL( SCIPdropVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, -1) );
2675 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2687 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
2714 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
2718 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
2727 &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2766 "which point should be used as starting point for the NLP solver? ('n'one, last 'f'easible, from dive's'tart)",
2770 "which variable selection should be used? ('f'ractionality, 'c'oefficient, 'p'seudocost, 'g'uided, 'd'ouble, 'v'eclen)",
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:79
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HASHMAP *varmap, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1229
Definition: type_result.h:42
Definition: type_result.h:56
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:958
Definition: type_nlpi.h:60
NLP diving heuristic that chooses fixings w.r.t. the fractionalities.
Definition: type_result.h:43
Definition: type_nlpi.h:163
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3299
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:225
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
Definition: struct_scip.h:68
public methods for node selector plugins
public methods for memory management
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1143
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3357
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip_var.c:8814
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1596
static SCIP_RETCODE chooseVeclenVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:425
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
public solving methods
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
public methods for timing
Definition: struct_var.h:207
static SCIP_RETCODE chooseFracVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:249
static SCIP_RETCODE chooseGuidedVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_SOL *bestsol, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:906
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1874
Undercover primal heuristic for MINLPs.
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3024
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3287
Definition: type_var.h:62
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:932
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3142
Definition: struct_misc.h:268
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
public methods for problem variables
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:117
Definition: type_nlpi.h:181
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10019
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3211
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1371
Definition: type_lp.h:46
public methods for SCIP variables
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
Definition: type_nlpi.h:166
public methods for numerical tolerances
static SCIP_RETCODE chooseDoubleVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **pseudocands, SCIP_Real *pseudocandsnlpsol, SCIP_Real *pseudocandslpsol, int npseudocands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Real *bestboundval, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:1078
public methods for querying solving statistics
Definition: struct_sol.h:73
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3373
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip_var.c:8780
public methods for the branch-and-bound tree
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1128
public methods for NLPI solver interfaces
Definition: struct_misc.h:137
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:618
static SCIP_RETCODE getNLPFracVars(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR ***nlpcands, SCIP_Real **nlpcandssol, SCIP_Real **nlpcandsfrac, int *nnlpcands)
Definition: heur_nlpdiving.c:174
Definition: type_nlpi.h:162
Definition: type_result.h:44
Definition: type_nlpi.h:197
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
Definition: type_paramset.h:63
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
Definition: type_nlpi.h:178
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1398
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_nlp.c:468
static SCIP_RETCODE choosePscostVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:784
Definition: type_retcode.h:42
public methods for problem copies
public methods for primal CIP solutions
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:819
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)
Definition: heur_undercover.c:3319
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
Definition: struct_heur.h:97
Definition: type_lp.h:43
public methods for primal heuristic plugins and divesets
static SCIP_RETCODE solveSubMIP(SCIP *scip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1415
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:56
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 threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2960
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1221
public data structures and miscellaneous methods
SCIP_RETCODE SCIPgetNLPStatistics(SCIP *scip, SCIP_NLPSTATISTICS *statistics)
Definition: scip_nlp.c:588
Definition: type_var.h:64
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2455
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1430
Definition: type_message.h:52
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3241
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
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)
Definition: scip_sol.c:3135
public methods for the LP relaxation, rows and columns
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:661
public methods for nonlinear relaxation
public methods for branching rule plugins and branching
SCIP_RETCODE SCIPincludeHeurNlpdiving(SCIP *scip)
Definition: heur_nlpdiving.c:2668
public methods for managing events
general public methods
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:398
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
static SCIP_RETCODE chooseCoefVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:519
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)
Definition: scip_param.c:167
static void calcPscostQuot(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real primsol, SCIP_Real frac, int rounddir, SCIP_Real *pscostquot, SCIP_Bool *roundup, SCIP_Bool prefvar)
Definition: heur_nlpdiving.c:704
public methods for solutions
public methods for random numbers
public methods for the probing mode
public methods for message output
NLP local search primal heuristic using sub-SCIPs.
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1576
Definition: type_var.h:93
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:234
SCIP_RETCODE SCIPgetNLPFracVars(SCIP *scip, SCIP_VAR ***fracvars, SCIP_Real **fracvarssol, SCIP_Real **fracvarsfrac, int *nfracvars, int *npriofracvars)
Definition: scip_nlp.c:663
public methods for message handling
Definition: type_retcode.h:54
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3244
Definition: type_lp.h:44
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1263
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
Definition: type_lp.h:42
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
public methods for primal heuristics
Definition: type_paramset.h:62
Definition: type_retcode.h:52
Definition: objbenders.h:43
public methods for global and local (sub)problems
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
static SCIP_RETCODE doSolveSubMIP(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1278
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:883
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
Definition: struct_event.h:204
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:328
memory allocation routines