heur_prune.c
Go to the documentation of this file.
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
53 #define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
58 #define PRUNE_TMRUNS_FAST 70 /**< number of runs in TM heuristic when called by prune heuristic */
59 #define PRUNE_MINREDELIMS 2 /**< maximum number of eliminations for reduction package when called by prune heuristic */
177 SCIP_CALL( SCIPStpHeurTMRun(scip, pcmode_fromheurdata, prunegraph, nodearrint, NULL, soledge, nruns,
301 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
324 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
370 if( graph->stp_type != STP_SPG && graph->stp_type != STP_RSMT && graph->stp_type != STP_OARSMT &&
385 if( SCIPsolGetHeur(bestsol) == heur || heurdata->bestsolindex == SCIPsolGetIndex(SCIPgetBestSol(scip)) )
441 SCIPdebugMessage("prune, best: old %f, new %f \n \n", SCIPgetSolOrigObj(scip, bestsol) - SCIPprobdataGetOffset(scip), pobj);
506 const SCIP_Bool pcmw = (probtype == STP_MWCSP || probtype == STP_RMWCSP || probtype == STP_RPCSPG || probtype == STP_PCSPG);
529 SCIP_CALL( SCIPStpHeurTMBuildTreePcMw(scip, prunegraph, FALSE, path, prunegraph->cost, &objold, solnode) );
750 vbase, nodearrint, edgearrint, nodearrint2, nodearrchar, FALSE, FALSE, FALSE, reductbound, FALSE, TRUE, TRUE) );
759 RPARAMS parameters = { .dualascent = FALSE, .boundreduce = FALSE, .nodereplacing = TRUE, .reductbound_min = PRUNE_MINREDELIMS,
788 SCIP_CALL( computeNewSols(scip, g, prunegraph, nodearrint, solnode, soledge, globalsoledge, &globalobj, FALSE, FALSE, success) );
793 SCIPdebugMessage("initially reduced graph: |V| = %d, |E| = %d, |T| = %d \n", annodes, anedges, anterms);
816 setMinMaxElims(scip, &minnelims, &lminnelims, annodes, anedges, anterms, i + 1, PRUNE_MAXREDROUNDS);
871 vbase, nodearrint, edgearrint, nodearrint2, nodearrchar, FALSE, FALSE, FALSE, reductbound, FALSE, TRUE, TRUE) );
880 RPARAMS parameters = { .dualascent = FALSE, .boundreduce = FALSE, .nodereplacing = TRUE, .reductbound_min = PRUNE_MINREDELIMS,
921 SCIPdebugMessage("obj of best prune sol: %f \n", solstp_getObjBounded(g, globalsoledge, 0.0, nedges));
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
static void setNodeSolArray(const GRAPH *g, SCIP_Real *RESTRICT uborg, int *RESTRICT solnode, const int *soledge)
Definition: heur_prune.c:86
SCIP_RETCODE SCIPStpHeurPruneRun(SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, const SCIP_Bool withinitialsol, const SCIP_Bool reducegraph)
Definition: heur_prune.c:599
Definition: type_result.h:33
Definition: type_result.h:47
Definition: graphdefs.h:184
Definition: struct_scip.h:59
SCIP_RETCODE SCIPStpHeurPruneUpdateSols(SCIP *scip, GRAPH *g, GRAPH *prunegraph, int *solnode, int *soledge, int *globalsoledge, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool *success)
Definition: heur_prune.c:489
Constraint handler for Steiner problems.
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
static SCIP_RETCODE computeNewSols(SCIP *scip, GRAPH *g, GRAPH *prunegraph, int *nodearrint, int *solnode, int *soledge, int *globalsoledge, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool beFast, SCIP_Bool *success)
Definition: heur_prune.c:131
SCIP_RETCODE reduce_redLoopPc(SCIP *, REDSOL *, GRAPH *, PATH *, PATH *, SCIP_Real *, int *, int *, int *, int *, int *, int *, STP_Bool *, SCIP_Bool, SCIP_Bool, SCIP_Bool, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1896
SCIP_RETCODE solstp_getOrg(SCIP *scip, const GRAPH *transgraph, const GRAPH *orggraph, const int *transsoledge, int *orgsoledge)
Definition: solstp.c:2148
Definition: struct_var.h:198
includes methods for Steiner tree problem solutions
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, enum PCMW_TmMode pcmw_tmmode, GRAPH *graph, int *starts, const SCIP_Real *prize, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Bool *success)
Definition: heur_tm.c:3418
SCIP_RETCODE reduce_boundPruneHeur(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, const int *, const int *, int *, int)
Definition: reduce_bnd.c:1237
Problem data for stp problem.
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE reduce_redLoopMw(SCIP *, REDSOL *, GRAPH *, PATH *, SCIP_Real *, int *, int *, int *, STP_Bool *, STP_Bool, STP_Bool, STP_Bool, int, SCIP_Bool, SCIP_Bool)
Definition: reduce_base.c:1771
void reduce_solGetNodesol(const GRAPH *, REDSOL *, int *)
Definition: reduce_sol.c:1176
Definition: graphdefs.h:284
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
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
Definition: reducedefs.h:100
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:2948
Definition: struct_sol.h:64
Definition: heur_tm.h:48
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:2879
Definition: reduce_sol.c:70
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: probdata_stp.c:3693
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
Definition: type_retcode.h:33
Definition: reducedefs.h:75
static void setMinMaxElims(SCIP *scip, int *minnelims, int *lminnelims, int annodes, int anedges, int anterms, int nround, int maxrounds)
Definition: heur_prune.c:206
Definition: struct_heur.h:88
Improvement heuristic for Steiner problems.
reduction-based primal heuristic for Steiner problems
void SCIPStpHeurTMBuildTree(SCIP *scip, GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:2932
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
public data structures and miscellaneous methods
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_RETCODE reduce_unconnectedRpcRmw(SCIP *, GRAPH *, SCIP_Real *)
Definition: reduce_pcsimple.c:1524
SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw(SCIP *scip, const GRAPH *g, SCIP_Bool useRootSym, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:3012
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_RETCODE reduce_solAddNodesol(const GRAPH *, const int *, REDSOL *)
Definition: reduce_sol.c:1150
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
Definition: probdata_stp.c:3190
shortest paths based primal heuristics for Steiner problems
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_RETCODE reduce_redLoopStp(SCIP *, GRAPH *, REDBASE *)
Definition: reduce_base.c:2074
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
Definition: objbenders.h:33
includes various reduction methods for Steiner tree problems
default SCIP plugins
SCIP callable library.
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