heur_rec.c
Go to the documentation of this file.
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
56 #define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
60 #define DEFAULT_MAXNSOLS 15 /**< default maximum number of (good) solutions be regarded in the subproblem */
64 #define DEFAULT_NWAITINGSOLS 4 /**< max number of new solutions to be available before executing the heuristic again */
335 solstp_markPcancestors(scip, solgraph->pcancestors, solgraph->orgtail, solgraph->orghead, solgraph->orgknots, solnodes, pcancestoredges, NULL, NULL, NULL ));
462 SCIP_CALL( SCIPStpHeurTMRun(scip, pcmode_fromheurdata, solgraph, NULL, prize, soledges, heurdata->ntmruns,
521 SCIPdebugMessage("solval_red=%f solval_bias=%f\n", solval_red, solstp_getObj(solgraph, soledges, 0.0));
1217 SCIP_CALL( solgraphSelectSolsDiff(scip, pool, graph, heurdata, vars, incumbentedges, incumbentindex, solselection, success) );
1219 SCIP_CALL( solgraphSelectSols(scip, pool, heurdata, incumbentindex, solselection, randomize) );
1311 if( graph->stp_type == STP_RSMT || graph->stp_type == STP_OARSMT || graph->stp_type == STP_GSTP )
1352 SCIPdebugMessage("REC: sol graph with nodes: %d, edges: %d, terminals: %d \n", nsolnodes, 2 * nsoledges, newgraph->terms);
1493 initializeIncumbent(scip, pool, graph, vars, nsols, *newsolindex, &incumentobj, incumbentedges);
1567 SCIP_CALL( retransformReducedProbSolution(scip, graph, solgraph, edgeancestor, soledges, newsoledges, stnodes) );
1631 SCIP_CALL( poolAddSol(scip, pool, heur, incumentobj, incumbentedges, nedges, newsolindex, solfound) );
1638 SCIPdebugMessage("incumbentobj=%f newsolobj=%f \n", solstp_getObjBounded(graph, incumbentedges, 0.0, nedges), solstp_getObjBounded(graph, newsoledges, 0.0, nedges));
1648 /** heuristic to exclude vertices or edges from a given solution (and inserting other edges) to improve objective */
1688 /*** 1. step: for solution S and original graph (V,E) initialize new graph (V[S], (V[S] X V[S]) \cup E) ***/
1803 newgraph, NULL, NULL, newresult, MIN(50, nsolterms), newgraph->source, newgraph->cost, newgraph->cost, NULL, NULL, success) );
1839 SCIP_CALL( solstp_markPcancestors(scip, newgraph->pcancestors, newgraph->orgtail, newgraph->orghead, nsolnodes, solnodes, NULL, NULL, NULL, NULL ) );
1857 SCIPdebugMessage("success %f < %f \n", solstp_getObjBounded(graph, newresult, 0.0, nedges), solstp_getObjBounded(graph, result, 0.0, nedges));
1861 SCIPdebugMessage("no improvements %f >= %f \n", solstp_getObjBounded(graph, newresult, 0.0, nedges), solstp_getObjBounded(graph, result, 0.0, nedges));
1883 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1945 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
1975 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2072 if( nallsols <= heurdata->nlastsols + i && heurdata->bestsolindex == SCIPsolGetIndex(SCIPgetBestSol(scip)) )
2127 newsolindex = SCIPsolGetIndex(sols[SCIPrandomGetInt(heurdata->randnumgen, 0, nreadysols - 1)]);
2132 SCIP_CALL( SCIPStpHeurRecRun(scip, NULL, heur, heurdata, graph, vars, &newsolindex, runs, nreadysols, restrictheur, &solfound) );
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
Definition: misc_stp.h:88
static void solgraphAdaptForPcMw(const GRAPH *graph, STP_Bool *solnode, int *nsolnodes, STP_Bool *soledge, int *nsoledges)
Definition: heur_rec.c:1010
Definition: type_result.h:33
Definition: type_result.h:47
Definition: graphdefs.h:184
SCIP_RETCODE SCIPStpHeurTMBuildTreeDc(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: heur_tm.c:3226
Definition: struct_scip.h:59
static int edgecostmultiplier(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real avg)
Definition: heur_rec.c:131
Constraint handler for Steiner problems.
SCIP_RETCODE reduce_solGetEdgesol(SCIP *, GRAPH *, REDSOL *, SCIP_Real *, int *)
Definition: reduce_sol.c:1197
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
static SCIP_RETCODE retransformReducedProbSolution(SCIP *scip, const GRAPH *graph, const GRAPH *solgraph, const int *edgeancestor, const int *soledges, int *newsoledges, STP_Bool *stnodes)
Definition: heur_rec.c:217
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: struct_var.h:198
SCIP_RETCODE solstp_markPcancestors(SCIP *scip, IDX **pcancestors, const int *tails, const int *heads, int orgnnodes, STP_Bool *solnodemark, STP_Bool *soledgemark, int *solnodequeue, int *nsolnodes, int *nsoledges)
Definition: solstp.c:2200
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
dual-ascent and reduction based primal heuristic for Steiner problems
static SCIP_RETCODE computeReducedProbSolutionBiased(SCIP *scip, SCIP_HEURDATA *heurdata, const GRAPH *graph, GRAPH *solgraph, const int *edgeweight, const int *edgeancestor, SCIP_VAR **vars, SCIP_Bool usestppool, int *soledges, SCIP_Bool *success)
Definition: heur_rec.c:355
Problem data for stp problem.
includes various files containing graph methods used for Steiner tree problems
Definition: struct_misc.h:259
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
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10003
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIP_RETCODE graph_pack(SCIP *, GRAPH *, GRAPH **, REDSOL *, SCIP_Bool)
Definition: graph_base.c:1324
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
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
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:2948
Definition: struct_sol.h:64
SCIP_RETCODE graph_pc_initSubgraph(SCIP *, GRAPH *)
Definition: graph_pcbase.c:763
static void initializeIncumbent(SCIP *scip, const STPSOLPOOL *pool, const GRAPH *graph, SCIP_VAR **vars, int nsols, int newsolindex, double *incumentobj, int *incumbentedges)
Definition: heur_rec.c:554
Definition: heur_tm.h:48
int graph_pc_getRoot2PtermEdge(const GRAPH *, int)
Definition: graph_pcbase.c:2499
static SCIP_RETCODE buildsolgraph(SCIP *scip, const STPSOLPOOL *pool, SCIP_HEURDATA *heurdata, const GRAPH *graph, GRAPH **solgraph, const int *incumbentedges, int *incumbentindex, int **edgeancestor, int **edgeweight, SCIP_Bool *success, SCIP_Bool randomize, SCIP_Bool addedges)
Definition: heur_rec.c:1170
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
SCIP_RETCODE reduce_exec(SCIP *, GRAPH *, REDSOL *, int, int, SCIP_Bool)
Definition: reduce_base.c:2192
Definition: type_result.h:35
SCIP_RETCODE solpool_addSol(SCIP *scip, const SCIP_Real obj, const int *soledges, STPSOLPOOL *pool, SCIP_Bool *success)
Definition: solpool.c:183
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
static SCIP_Bool poolSolIsUnreduced(const GRAPH *graph, const int solindex, const STPSOLPOOL *pool)
Definition: heur_rec.c:612
void graph_edge_addSubgraph(SCIP *, const GRAPH *, const int *, int, GRAPH *)
Definition: graph_edge.c:341
SCIP_Bool SCIPprobdataProbIsAdversarial(SCIP *scip)
Definition: probdata_stp.c:3324
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
SCIP_RETCODE SCIPStpHeurRecExclude(SCIP *scip, const GRAPH *graph, const int *result, int *newresult, int *dnodemap, STP_Bool *stvertex, SCIP_Bool *success)
Definition: heur_rec.c:1649
static void setHeurdataNUsedSols(SCIP_HEURDATA *heurdata, int nsols, SCIP_Bool restrictheur)
Definition: heur_rec.c:193
Definition: struct_heur.h:88
Improvement heuristic for Steiner problems.
reduction-based primal heuristic for Steiner problems
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
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
SCIP_RETCODE graph_pc_finalizeSubgraph(SCIP *, GRAPH *)
Definition: graph_pcbase.c:795
static SCIP_RETCODE poolAddSol(SCIP *scip, STPSOLPOOL *pool, SCIP_HEUR *heur, const SCIP_Real incumentobj, const int *incumbentedges, int nedges, int *newsolindex, SCIP_Bool *soladded)
Definition: heur_rec.c:640
static void solgraphAddEdges(SCIP_HEURDATA *heurdata, const GRAPH *graph, const STP_Bool *solnode, STP_Bool *soledge, int *nsoledges)
Definition: heur_rec.c:1127
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10044
SCIP_VAR ** SCIPprobdataGetEdgeVars(SCIP *scip)
Definition: probdata_stp.c:3277
Constraint handler for linear constraints in their most general form, .
static void solgraphAdaptForDCSTP(const GRAPH *graph, const STP_Bool *solnode, STP_Bool *soledge, int *nsoledges)
Definition: heur_rec.c:1096
SCIP_RETCODE SCIPStpHeurRecRun(SCIP *scip, STPSOLPOOL *pool, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, const GRAPH *graph, SCIP_VAR **vars, int *newsolindex, int runs, int nsols, SCIP_Bool restrictheur, SCIP_Bool *solfound)
Definition: heur_rec.c:1455
static void marksolverts(const GRAPH *g, IDX *curr, const int *unodemap, STP_Bool *RESTRICT stvertex)
Definition: heur_rec.c:173
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1344
Definition: solpool.h:38
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
Primal recombination heuristic for Steiner problems.
Definition: solpool.h:46
static SCIP_RETCODE solgraphSelectSols(SCIP *scip, const STPSOLPOOL *pool, SCIP_HEURDATA *heurdata, int *incumbentindex, int *selection, SCIP_Bool randomize)
Definition: heur_rec.c:880
shortest paths based primal heuristics for Steiner problems
static SCIP_RETCODE computeReducedProbSolution(SCIP *scip, SCIP_HEURDATA *heurdata, const GRAPH *graph, GRAPH *solgraph, REDSOL *redsol, const int *edgeweight, const int *edgeancestor, SCIP_VAR **vars, SCIP_Bool usestppool, int *soledges, SCIP_Bool *success)
Definition: heur_rec.c:489
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_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
Definition: objbenders.h:33
SCIP_RETCODE solstp_prune(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:1366
static SCIP_RETCODE solgraphSelectSolsDiff(SCIP *scip, const STPSOLPOOL *pool, const GRAPH *graph, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, const int *incumbentedges, int *incumbentindex, int *selection, SCIP_Bool *success)
Definition: heur_rec.c:711
includes various reduction methods for Steiner tree problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
default SCIP plugins
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
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
IDX * graph_edge_getAncestors(const GRAPH *, int)
Definition: graph_history.c:1202