heur_nlpdiving.c
Go to the documentation of this file.
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
81 #define DEFAULT_MAXNLPITERREL 10 /**< additional allowed number of NLP iterations relative to successfully found solutions */
82 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
84 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
86 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
87 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
88 #define DEFAULT_MINSUCCQUOT 0.1 /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
89 #define DEFAULT_MAXFEASNLPS 10 /**< maximal number of NLPs with feasible solution to solve during one dive */
90 #define DEFAULT_FIXQUOT 0.2 /**< percentage of fractional variables that should be fixed before the next NLP solve */
91 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
93 #define DEFAULT_PREFERLPFRACS FALSE /**< prefer variables that are also fractional in LP solution? */
95 #define DEFAULT_SOLVESUBMIP FALSE /**< should a sub-MIP be solved if all cover variables are fixed? */
96 #define DEFAULT_NLPSTART 's' /**< which point should be used as starting point for the NLP solver? */
97 #define DEFAULT_VARSELRULE 'd' /**< which variable selection should be used? ('f'ractionality, 'c'oefficient,
107 {
112 int maxnlpiterrel; /**< additional allowed number of NLP iterations relative to successfully found solutions */
113 SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
115 SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
117 SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
118 SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
120 SCIP_Real minsuccquot; /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
121 SCIP_Real fixquot; /**< percentage of fractional variables that should be fixed before the next NLP solve */
151 /** gets fractional variables of last NLP solution along with solution values and fractionalities
153 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
165 SCIP_Real** nlpcandssol, /**< pointer to store the array of NLP fractional variables solution values, or NULL */
166 SCIP_Real** nlpcandsfrac, /**< pointer to store the array of NLP fractional variables fractionalities, or NULL */
182 /* values may be outside the domain in exact arithmetic, but inside the domain within relative tolerance, and still
183 * slightly fractional, because SCIPisFeasIntegral() uses absolute tolerance; project value onto domain to avoid this
190 if( (*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c]) || (*nlpcandssol)[c] > SCIPvarGetUbLocal((*nlpcands)[c]) )
232 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
246 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
289 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
290 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
295 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
300 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
325 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
342 if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
371 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
406 * - round variable with a small ratio between the increase in the objective and the locking numbers
408 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
422 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
458 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
459 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
470 nlocks = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) + SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
502 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
516 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
560 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
561 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
566 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
571 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
596 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
653 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
671 if( bestcandmayrounddown || bestcandmayroundup || nviolrows + frac < bestnviolrows + bestcandfrac )
689 /** calculates the pseudocost score for a given variable w.r.t. a given solution value and a given rounding direction */
722 * to avoid performance variability caused by numerics we use random numbers to decide whether we want to roundup or
730 || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) - 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
733 || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) + 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
735 else if( SCIPisLT(scip, frac, 0.3) || (SCIPisEQ(scip, frac, 0.3) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
737 else if( SCIPisGT(scip, frac, 0.7) || (SCIPisEQ(scip, frac, 0.7) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
762 * - of these variables, round variable with largest rel. difference of pseudo cost values in corresponding
767 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
781 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
824 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
829 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
833 * - if variable may be rounded in both directions, round corresponding to the pseudo cost values
834 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
883 * - of these variables, round a variable to its value in direction of incumbent solution, and choose the
886 * - round variable in direction that destroys LP feasibility (other direction is checked by SCIProundSol())
889 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
904 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
950 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
951 if( SCIPisLT(scip, solval, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, solval, SCIPvarGetUbLocal(var)) )
964 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
968 * - if variable may be rounded in both directions, round corresponding to its value in incumbent solution
969 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
987 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1004 if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
1025 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1059 * - choose a variable for which the sum of the distances from the relaxations' solutions to a common
1075 SCIP_Real* bestboundval, /**< pointer to store the bound, the best candidate should be rounded to */
1076 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
1077 SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
1118 assert(SCIPisLE(scip, SCIPvarGetLbLocal(var), lpsol) && SCIPisLE(scip, lpsol, SCIPvarGetUbLocal(var)));
1120 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
1121 if( SCIPisLT(scip, nlpsol, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpsol, SCIPvarGetUbLocal(var)) )
1126 /* if this candidate is trivially roundable, and we already know a candidate that is not, continue */
1140 /* if both values are in the same interval, find out which integer is (in sum) the closer one, this will be the
1178 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1214 /** creates a new solution for the original problem by copying the solution of the subproblem */
1246 subsolvals[i] = MIN(MAX(0.0, SCIPvarGetLbLocal(vars[i])), SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
1289 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", NULL, NULL, 0, FALSE, FALSE, FALSE,
1295 assert(SCIPhashmapGetImage(varmap, covervars[c]) != NULL); /* cover variable cannot be relaxation-only, thus must have been copied */
1297 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c])),
1331 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
1337 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
1342 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
1385 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
1463 otherbound = (eventtype & SCIP_EVENTTYPE_LBCHANGED) ? SCIPvarGetUbLocal(var) : SCIPvarGetLbLocal(var);
1491 /* SCIPdebugMsg(scip, "changed bound of cover variable <%s> from %f to %f (nfixedcovervars: %d).\n", SCIPvarGetName(var),
1570 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1592 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",
1593 SCIPgetProbName(scip), SCIPheurGetNSolsFound(heur), SCIPheurGetNCalls(heur), SCIPheurGetTime(heur),
1594 heurdata->nnlpiterations, heurdata->nnlpsolves, heurdata->nnlpiterations/MAX(1.0,(SCIP_Real)heurdata->nnlpsolves),
1595 (100*heurdata->nsuccess) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailcutoff) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfaildepth) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailnlperror) / (int)SCIPheurGetNCalls(heur)
1604 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
1708 /* only call heuristic, if the current node will not be cutoff, e.g., due to a (integer and NLP-)feasible LP solution */
1717 if( (SCIPheurGetNSolsFound(heur) + 1.0) / (SCIP_Real)(SCIPheurGetNCalls(heur) + 1.0) < heurdata->minsuccquot )
1728 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
1741 maxnnlpiterations += (int)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxnlpiterrel);
1749 maxnnlpiterations = (int)MAX((SCIP_Real) maxnnlpiterations, (SCIP_Real) heurdata->nnlpiterations + 1.2*avgnnlpiterations);
1773 SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, maxnnlpiterations - heurdata->nnlpiterations) );
1826 SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
1843 * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
1844 * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
1869 /* for guided diving: get best solution that should guide the search; if this solution lives in the original variable space,
1938 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1950 SCIP_CALL( SCIPcomputeCoverUndercover(scip, &ncovervars, covervars, timelimit, memorylimit, SCIPinfinity(scip), FALSE, FALSE, FALSE, 'u', &covercomputed) );
1955 /* a cover can be empty, if the cover computation reveals that all nonlinear constraints are linear w.r.t. current variable fixations */
1973 SCIP_CALL( SCIPcatchVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr,
1994 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing nlpdiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
1995 SCIPgetNNodes(scip), SCIPgetDepth(scip), nnlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
2013 /* dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
2015 * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
2028 while( !nlperror && !cutoff && (nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_UNKNOWN) && nnlpcands > 0
2031 || (nfeasnlps < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound))
2037 /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
2057 SCIP_CALL( chooseCoefVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2066 SCIP_CALL( chooseVeclenVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2075 SCIP_CALL( choosePscostVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2084 SCIP_CALL( chooseGuidedVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, bestsol, varincover, covercomputed,
2093 /* double diving only works if we have both relaxations at hand, otherwise we fall back to fractional diving */
2102 SCIP_CALL( SCIPgetSolVals(scip, heurdata->sol, npseudocands, pseudocands, pseudocandsnlpsol) );
2103 SCIP_CALL( chooseDoubleVar(scip, heurdata, pseudocands, pseudocandsnlpsol, pseudocandslpsol, npseudocands,
2113 SCIP_CALL( chooseFracVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2128 * this should only happen if they are slightly outside bounds (i.e., still within feastol, relative tolerance),
2129 * but far enough out to be considered as fractional (within feastol, but using absolute tolerance)
2141 SCIPdebugMsg(scip, "nlpdiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2159 /* if all variables have been found to be essentially integral (even though there is some numerical doubt, see comment above), then stop */
2172 /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2177 SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2178 SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2182 if( SCIPisFeasLT(scip, backtrackvarval, SCIPvarGetLbLocal(backtrackvar)) || SCIPisFeasGT(scip, backtrackvarval, SCIPvarGetUbLocal(backtrackvar)) )
2184 SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2185 SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2193 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2195 SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2201 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2203 SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2220 /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2225 SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2230 if( SCIPisFeasLT(scip, bestboundval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestboundval, SCIPvarGetUbLocal(var)) )
2232 SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2242 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2249 /* 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 */
2250 if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2261 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2268 /* 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 */
2269 if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2296 SCIPdebugMsg(scip, " *** cutoff detected in propagation at level %d\n", SCIPgetProbingDepth(scip));
2330 assert(SCIPvarGetType(covervars[c]) >= SCIP_VARTYPE_IMPLINT || SCIPisFeasIntegral(scip, nlpsolval));
2334 * @todo do we need a new probing node for each fixing? if one of these fixings leads to a cutoff
2350 /* if covervar was implicit integer and fractional, then nlpsolval may be below lower bound now, so adjust to new bound */
2388 /* get LP solution status, objective value, and fractional variables, that should be integral */
2390 assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
2391 (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))));
2422 SCIPdebugMsg(scip, " *** cutoff detected in LP solving at level %d, lpsolstat = %d\n", SCIPgetProbingDepth(scip), lpsolstat);
2443 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
2462 SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, MAX(maxnnlpiterations - heurdata->nnlpiterations, MINNLPITER)) );
2489 "Error while solving NLP in nlpdiving heuristic; NLP solve terminated with code <%d>\n", termstat);
2501 /* get NLP solution status, objective value, and fractional variables, that should be integral */
2507 SCIPdebugMsg(scip, " *** cutoff detected in NLP solving at level %d, nlpsolstat: %d\n", SCIPgetProbingDepth(scip), nlpsolstat);
2515 /* forget previous backtrack variable, we will never go back to a depth before the current one */
2537 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking one step\n", SCIPgetProbingDepth(scip));
2540 /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2548 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking to depth %d\n", SCIPgetProbingDepth(scip), backtrackdepth);
2551 /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2560 /* in case, we are feasible after backtracking, fix less variables at once in continuing diving
2576 SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
2578 SCIPdebugMsg(scip, " -> nlpsolstat=%d, objval=%g/%g, nfrac nlp=%d lp=%d\n", nlpsolstat, objval, searchbound, nnlpcands, nlpbranchcands);
2583 if( nlperror || (nlpsolstat > SCIP_NLPSOLSTAT_LOCINFEASIBLE && nlpsolstat != SCIP_NLPSOLSTAT_UNKNOWN) )
2585 SCIPdebugMsgPrint(scip, "NLP bad status - nlperror: %ud nlpsolstat: %d \n", nlperror, nlpsolstat);
2595 || (divedepth < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound) ) )
2597 SCIPdebugMsgPrint(scip, "TOO DEEP - divedepth: %4d cands halfed: %d ltmaxdepth: %d ltmaxiter: %d bound: %d\n", divedepth,
2598 (nnlpcands > startnnlpcands - divedepth/2), (divedepth >= maxdivedepth), (heurdata->nnlpiterations >= maxnnlpiterations),
2608 SCIPdebugMsgPrint(scip, "UNKNOWN, very mysterical reason\n"); /* see also special case var == NULL (bestcand == -1) after choose*Var above */
2617 SCIPdebugMsg(scip, "nlpdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2621 * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
2622 * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
2650 assert(heurdata->nfixedcovervars >= 0); /* variables might have been globally fixed in propagation */
2659 SCIP_CALL( SCIPdropVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, -1) );
2733 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2746 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
2773 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
2777 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
2786 &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2825 "which point should be used as starting point for the NLP solver? ('n'one, last 'f'easible, from dive's'tart)",
2829 "which variable selection should be used? ('f'ractionality, 'c'oefficient, 'p'seudocost, 'g'uided, 'd'ouble, 'v'eclen)",
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HASHMAP *varmap, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1220
Definition: type_result.h:33
Definition: type_result.h:47
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2447
NLP diving heuristic that chooses fixings w.r.t. the fractionalities.
Definition: type_result.h:34
Definition: type_nlpi.h:64
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
public methods for SCIP parameter handling
Definition: type_nlpi.h:51
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
Definition: struct_scip.h:59
public methods for node selector plugins
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1136
SCIP_EXPORT int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3250
public methods for memory management
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:416
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
internal methods for NLPI solver interfaces
SCIP_RETCODE SCIPgetNLPStatistics(SCIP *scip, SCIP_NLPSTATISTICS *statistics)
Definition: scip_nlp.c:666
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:3628
public solving methods
public methods for timing
Definition: struct_var.h:198
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:240
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3131
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:897
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
Undercover primal heuristic for MINLPs.
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
Definition: type_var.h:53
Definition: struct_misc.h:259
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3200
public methods for problem variables
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:48
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:893
Definition: type_nlpi.h:81
Definition: type_lp.h:37
public methods for SCIP variables
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
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:3125
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:390
Definition: type_nlpi.h:78
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:874
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3192
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1575
SCIP_RETCODE SCIPgetNLPFracVars(SCIP *scip, SCIP_VAR ***fracvars, SCIP_Real **fracvarssol, SCIP_Real **fracvarsfrac, int *nfracvars, int *npriofracvars)
Definition: scip_nlp.c:739
Definition: type_nlpi.h:67
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
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:1069
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1420
public methods for querying solving statistics
Definition: struct_sol.h:64
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:724
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:108
public methods for the branch-and-bound tree
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3362
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:610
Definition: struct_misc.h:128
static SCIP_RETCODE getNLPFracVars(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR ***nlpcands, SCIP_Real **nlpcandssol, SCIP_Real **nlpcandsfrac, int *nnlpcands)
Definition: heur_nlpdiving.c:165
void SCIPnlpStatisticsFree(BMS_BLKMEM *blkmem, SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:803
Definition: type_nlpi.h:63
Definition: type_result.h:35
Definition: type_nlpi.h:52
Definition: struct_nlpi.h:78
Definition: type_paramset.h:54
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
public methods for event handler plugins and event handlers
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
SCIP_RETCODE SCIPincludeHeurNlpdiving(SCIP *scip)
Definition: heur_nlpdiving.c:2726
SCIP_RETCODE SCIPgetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int *ival)
Definition: scip_nlp.c:770
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
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:775
Definition: type_retcode.h:33
public methods for problem copies
public methods for primal CIP solutions
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:225
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:942
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:671
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
Definition: struct_heur.h:88
Definition: type_lp.h:34
public methods for primal heuristic plugins and divesets
SCIP_RETCODE SCIPsetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int ival)
Definition: scip_nlp.c:798
static SCIP_RETCODE solveSubMIP(SCIP *scip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1406
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
Definition: type_nlpi.h:54
public data structures and miscellaneous methods
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:9945
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1255
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
Definition: type_var.h:55
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
int SCIPnlpStatisticsGetNIterations(SCIP_NLPSTATISTICS *statistics)
Definition: nlpi.c:818
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
Definition: type_message.h:43
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1121
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:2908
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3228
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:95
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:130
public methods for the LP relaxation, rows and columns
SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
Definition: heur_subnlp.c:2468
SCIP_EXPORT int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3193
public methods for nonlinear relaxations
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:555
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1390
public methods for branching rule plugins and branching
public methods for managing events
general public methods
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
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:510
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:695
public methods for solutions
public methods for random numbers
public methods for the probing mode
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:786
SCIP_RETCODE SCIPsetNLPRealPar(SCIP *scip, SCIP_NLPPARAM type, SCIP_Real dval)
Definition: scip_nlp.c:854
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1860
NLP local search primal heuristic using sub-SCIPs.
Definition: type_var.h:84
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:74
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:292
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip_var.c:8747
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:336
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1568
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
Definition: type_retcode.h:45
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:439
Definition: type_lp.h:35
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_RETCODE SCIPnlpStatisticsCreate(BMS_BLKMEM *blkmem, SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:786
Definition: type_lp.h:33
public methods for primal heuristics
Definition: type_paramset.h:53
Definition: type_retcode.h:43
Definition: objbenders.h:33
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:3231
public methods for global and local (sub)problems
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip_var.c:8713
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:158
static SCIP_RETCODE doSolveSubMIP(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1269
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:968
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_nlp.c:564
static SCIP_DECL_HEURINITSOL(heurInitsolNlpdiving)
Definition: heur_nlpdiving.c:1610
Definition: struct_event.h:195
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
memory allocation routines