heur_masterdiving.c
Go to the documentation of this file.
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
54 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
58 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
60 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
62 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
63 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
64 #define DEFAULT_BACKTRACK FALSE /**< single backtracking by choosing another variable in case of infeasibility */
65 #define DEFAULT_MAXDISCREPANCY 2 /**< maximal discrepancy allowed in backtracking and limited discrepancy search */
66 #define DEFAULT_MAXDISCDEPTH 0 /**< maximal depth until which a limited discrepancy search is performed */
82 GCG_DECL_DIVINGINITSOL ((*divinginitsol)); /**< solving process initialization method of diving heuristic */
83 GCG_DECL_DIVINGEXITSOL ((*divingexitsol)); /**< solving process deinitialization method of diving heuristic */
84 GCG_DECL_DIVINGINITEXEC ((*divinginitexec)); /**< execution initialization method of diving heuristic */
85 GCG_DECL_DIVINGEXITEXEC ((*divingexitexec)); /**< execution deinitialization method of diving heuristic */
86 GCG_DECL_DIVINGSELECTVAR ((*divingselectvar)); /**< variable selection method of diving heuristic */
92 SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */
96 SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
98 SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
100 SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
101 SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
102 SCIP_Bool backtrack; /**< single backtracking by choosing another variable in case of infeasibility */
103 int maxdiscrepancy; /**< maximal discrepancy allowed in backtracking and limited discrepancy search */
115 SCIP_Longint nroundsols; /**< number of integral solutions that have been obtained by rounding */
119 SCIP_Longint notherdirections; /**< number of times a cutoff was resolved by branching in the other direction */
120 SCIP_Longint nbacktracks; /**< number of times a single backtracking at a deeper node was performed */
228 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
269 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
382 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
393 maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
487 SCIPdebugMessage("(node %"SCIP_LONGINT_FORMAT") executing %s heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
488 SCIPgetNNodes(scip), SCIPheurGetName(heur), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
490 /* dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
492 * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
513 || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations && objval < searchbound))
539 SCIP_CALL( heurdata->divingselectvar(scip, heur, tabulist, heurdata->maxdiscrepancy, &bestcand, &bestcandmayround) );
569 SCIPdebugMessage("%s found roundable primal solution: obj=%g\n", SCIPheurGetName(heur), SCIPgetSolOrigObj(scip, heurdata->sol));
586 SCIPdebugMessage("Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
587 SCIPvarGetName(bestcand), SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand), bestcandsol);
593 SCIPdebugMessage(" dive %d/%d, LP iter %"SCIP_LONGINT_FORMAT"/%"SCIP_LONGINT_FORMAT", pricerounds %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
594 divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations, totalpricerounds, heurdata->maxpricerounds,
612 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
613 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
621 retstat = SCIPsolveProbingLPWithPricing(scip, FALSE, TRUE, heurdata->maxpricerounds == -1 ? -1 : heurdata->maxpricerounds - totalpricerounds, &lperror, &cutoff);
624 retstat = SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff);
627 SCIPwarningMessage(scip, "Error while solving LP in %s heuristic; LP solve terminated with code <%d>\n", SCIPheurGetName(heur), retstat);
632 SCIP_CALL( SCIPsolveProbingLPWithPricing(scip, FALSE, TRUE, heurdata->maxpricerounds == -1 ? -1 : heurdata->maxpricerounds - totalpricerounds, &lperror, &cutoff) );
634 SCIP_CALL( SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff) );
643 heurdata->npricerounds += (SCIP_Longint) SCIPgetNPriceRounds(scip) - (SCIP_Longint) npricerounds;
651 /* If infeasibility is encountered, perform Farkas pricing in order to reach feasibility again */
653 && !farkaspricing && (heurdata->maxpricerounds == -1 || totalpricerounds < heurdata->maxpricerounds)
656 SCIPdebugMessage(" *** infeasibility detected at level %d - perform Farkas pricing\n", SCIPgetProbingDepth(scip));
665 /* perform backtracking if a cutoff or an infeasibility was detected and if Farkas pricing did not help */
669 if( heurdata->backtrack && divedepth > heurdata->maxdiscdepth && discrepancy < heurdata->maxdiscrepancy )
671 SCIPdebugMessage(" *** cutoff or infeasibility detected at level %d - backtracking one node\n", SCIPgetProbingDepth(scip));
688 SCIPdebugMessage(" *** cutoff or infeasibility detected at level %d - performing discrepancy search\n", SCIPgetProbingDepth(scip));
697 (divedepth >= heurdata->maxdiscdepth || discrepancies[divedepth] >= heurdata->maxdiscrepancy) );
749 SCIPdebugMessage(" -> lpsolstat=%d, objval=%g/%g, nfrac=%d\n", lpsolstat, objval, searchbound, nlpcands);
759 SCIPdebugMessage("%s found primal solution: obj=%g\n", SCIPheurGetName(heur), SCIPgetSolOrigObj(scip, heurdata->sol));
787 SCIPstatisticPrintf("Masterdiving statistic: %s at node %"SCIP_LONGINT_FORMAT" , %d dive nodes, max depth = %d, lptime = %6.1f sec, %"SCIP_LONGINT_FORMAT" lp iters, %d pricing rds, %d Farkas repairs, %d single backtracks, %d disc searches\n",
788 SCIPheurGetName(heur), SCIPgetNNodes(scip), ndivenodes, maxreacheddepth, SCIPgetClockTime(scip, lptime), totallpiters, totalpricerounds, nfarkas, nbacktracks, ndiscsearches);
852 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
866 SCIPstatisticPrintf("Master Diving Heuristics : Calls Sols Improving DiveSols Improving RoundSols Improving Nodes LP iters Price rds max nFarkas Single bt Discsrch BestPrimal Rounded?\n");
878 SCIPstatisticPrintf("%-17.17s : %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10d %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT,
879 SCIPheurGetName(heur), heurdata->ncalls, heurdata->nsols, heurdata->nimpsols, heurdata->ndivesols, heurdata->nimpdivesols, heurdata->nroundsols, heurdata->nimproundsols, heurdata->ndivenodes, heurdata->nlpiterations, heurdata->npricerounds, heurdata->maxpricerounds, heurdata->nfarkas, heurdata->nbacktracks, heurdata->ndiscsearches);
962 SCIPstatisticPrintf("Masterdiving statistic: %s found solution %13.6e , improving = %u , rounded = %u\n",
1021 GCG_DECL_DIVINGINITSOL ((*divinginitsol)), /**< solving process initialization method of diving heuristic */
1022 GCG_DECL_DIVINGEXITSOL ((*divingexitsol)), /**< solving process deinitialization method of diving heuristic */
1023 GCG_DECL_DIVINGINITEXEC ((*divinginitexec)), /**< execution initialization method of diving heuristic */
1024 GCG_DECL_DIVINGEXITEXEC ((*divingexitexec)), /**< execution deinitialization method of diving heuristic */
1025 GCG_DECL_DIVINGSELECTVAR ((*divingselectvar)), /**< variable selection method of diving heuristic */
1106 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
1111 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
1122 &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4202
Definition: event_mastersol.c:51
static SCIP_DECL_HEURINITSOL(heurInitsolMasterdiving)
Definition: heur_masterdiving.c:230
GCG_DECL_DIVINGINITEXEC((*divinginitexec))
GCG_DECL_DIVINGEXITEXEC((*divingexitexec))
static SCIP_DECL_EVENTEXITSOL(eventExitsolGenericbranchvaradd)
Definition: branch_generic.c:280
static SCIP_DECL_HEURINIT(heurInitMasterdiving)
Definition: heur_masterdiving.c:176
GCG_DIVINGDATA * GCGheurGetDivingDataMaster(SCIP_HEUR *heur)
Definition: heur_masterdiving.c:975
GCG variable pricer.
static SCIP_DECL_HEUREXIT(heurExitMasterdiving)
Definition: heur_masterdiving.c:205
Definition: heur_gcgcoefdiving.c:61
SCIP_RETCODE SCIPincludeEventHdlrMasterdiving(SCIP *scip)
Definition: heur_masterdiving.c:1158
GCG_DECL_DIVINGEXIT((*divingexit))
primal heuristic interface for LP diving heuristics on the master variables
GCG_DECL_DIVINGSELECTVAR((*divingselectvar))
GCG_DECL_DIVINGINIT((*divinginit))
static SCIP_DECL_EVENTEXEC(eventExecGenericbranchvaradd)
Definition: branch_generic.c:294
GCG_DECL_DIVINGFREE((*divingfree))
void GCGheurSetDivingDataMaster(SCIP_HEUR *heur, GCG_DIVINGDATA *divingdata)
Definition: heur_masterdiving.c:991
GCG relaxator.
static SCIP_DECL_HEUREXITSOL(heurExitsolMasterdiving)
Definition: heur_masterdiving.c:271
static SCIP_DECL_HEUREXEC(heurExecMasterdiving)
Definition: heur_masterdiving.c:294
GCG_DECL_DIVINGEXITSOL((*divingexitsol))
Definition: heur_gcgdins.c:74
static SCIP_DECL_HEURFREE(heurFreeMasterdiving)
Definition: heur_masterdiving.c:150
GCG_DECL_DIVINGINITSOL((*divinginitsol))
SCIP_RETCODE GCGincludeDivingHeurMaster(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, GCG_DECL_DIVINGFREE((*divingfree)), GCG_DECL_DIVINGINIT((*divinginit)), GCG_DECL_DIVINGEXIT((*divingexit)), GCG_DECL_DIVINGINITSOL((*divinginitsol)), GCG_DECL_DIVINGEXITSOL((*divingexitsol)), GCG_DECL_DIVINGINITEXEC((*divinginitexec)), GCG_DECL_DIVINGEXITEXEC((*divingexitexec)), GCG_DECL_DIVINGSELECTVAR((*divingselectvar)), GCG_DIVINGDATA *divingdata)
Definition: heur_masterdiving.c:1008