heur_rec.c
Go to the documentation of this file.
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
54 #define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
58 #define DEFAULT_MAXNSOLS 15 /**< default maximum number of (good) solutions be regarded in the subproblem */
62 #define DEFAULT_NWAITINGSOLS 4 /**< max number of new solutions to be available before executing the heuristic again */
513 SCIP_CALL( selectdiffsols(scip, pool, graph, heurdata, vars, incumbentedges, incumbentindex, solselection, success) );
694 if( graph->stp_type == STP_RSMT || graph->stp_type == STP_OARSMT || graph->stp_type == STP_GSTP )
729 SCIPdebugMessage("REC: sol graph with nodes: %d, edges: %d, terminals: %d \n", nsolnodes, 2 * nsoledges, newgraph->terms);
769 graph_pc_updateTerm2edge(newgraph, graph, dnodemap[orgtail], dnodemap[orghead], orgtail, orghead);
772 graph_edge_add(scip, newgraph, dnodemap[orgtail], dnodemap[orghead], graph->cost[i], graph->cost[i + 1]);
1048 const SCIP_Bool pcmw = (probtype == STP_PCSPG || probtype == STP_MWCSP || probtype == STP_RPCSPG || probtype == STP_RMWCSP );
1193 SCIPdebugMessage("REC: graph not completely reduced, nodes: %d, edges: %d, terminals: %d \n", solgraph->knots, nsoledges, solgraph->terms);
1251 if( probtype == STP_DHCSTP && SCIPisLT(scip, cost[e], BLOCKED) && SCIPisGT(scip, cost[e], maxcost) )
1310 SCIP_CALL( SCIPStpHeurTMRun(scip, tmheurdata, solgraph, NULL, &best_start, soledges, heurdata->ntmruns,
1452 SCIP_CALL( graph_sol_markPcancestors(scip, solgraph->pcancestors, solgraph->orgtail, solgraph->orghead, solgraph->orgknots,
1593 /** heuristic to exclude vertices or edges from a given solution (and inserting other edges) to improve objective */
1635 /*** 1. step: for solution S and original graph (V,E) initialize new graph (V[S], (V[S] X V[S]) \cup E) ***/
1754 SCIP_CALL( SCIPStpHeurTMRun(scip, tmheurdata, newgraph, NULL, &best_start, newresult, MIN(50, nsolterms), newgraph->source, newgraph->cost,
1791 SCIP_CALL( graph_sol_markPcancestors(scip, newgraph->pcancestors, newgraph->orgtail, newgraph->orghead, nsolnodes, solnodes, NULL, NULL, NULL, NULL ) );
1810 SCIPdebugMessage("success %f < %f \n", graph_sol_getObj(graph->cost, newresult, 0.0, nedges), graph_sol_getObj(graph->cost, result, 0.0, nedges));
1814 SCIPdebugMessage("no improvements %f >= %f \n", graph_sol_getObj(graph->cost, newresult, 0.0, nedges), graph_sol_getObj(graph->cost, result, 0.0, nedges));
1836 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1898 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
1925 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
1980 pcmw = (probtype == STP_PCSPG || probtype == STP_MWCSP || probtype == STP_RPCSPG || probtype == STP_RMWCSP);
2015 if( nallsols <= heurdata->nlastsols + i && heurdata->bestsolindex == SCIPsolGetIndex(SCIPgetBestSol(scip)) )
2074 SCIP_CALL( SCIPStpHeurRecRun(scip, NULL, heur, heurdata, graph, vars, &newsolindex, runs, nreadysols, restrictheur, &solfound) );
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
Definition: misc_stp.h:73
Definition: type_result.h:33
Definition: type_result.h:47
SCIP_RETCODE SCIPStpHeurTMBuildTreeDc(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: heur_tm.c:732
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: struct_scip.h:59
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
static SCIP_Bool isInPool(const int *soledges, const STPSOLPOOL *pool)
Definition: heur_rec.c:834
static int edgecostmultiplier(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real avg)
Definition: heur_rec.c:128
Constraint handler for Steiner problems.
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
Definition: struct_var.h:198
dual-ascent and reduction based primal heuristic for Steiner problems
Problem data for stp problem.
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, SCIP_HEURDATA *heurdata, GRAPH *graph, int *starts, int *bestnewstart, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Real maxcost, SCIP_Bool *success, SCIP_Bool pcmwfull)
Definition: heur_tm.c:1649
Definition: struct_misc.h:259
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 SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
void graph_pc_updateTerm2edge(GRAPH *, const GRAPH *, int, int, int, int)
Definition: grphbase.c:928
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:2357
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
SCIP_Bool graph_pc_term2edgeConsistent(const GRAPH *)
Definition: grphbase.c:853
Definition: struct_sol.h:64
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
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
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:465
static void marksolverts(GRAPH *g, IDX *curr, int *unodemap, STP_Bool *stvertex)
Definition: heur_rec.c:815
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_SOL *sol, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: probdata_stp.c:3153
SCIP_Bool graph_sol_valid(SCIP *, const GRAPH *, const int *)
Definition: grphbase.c:3070
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
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:1594
Definition: struct_heur.h:88
Improvement heuristic for Steiner problems.
reduction-based primal heuristic for Steiner problems
public data structures and miscellaneous methods
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:9959
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
static SCIP_RETCODE selectsols(SCIP *scip, const STPSOLPOOL *pool, SCIP_HEURDATA *heurdata, int *incumbentindex, int *selection, SCIP_Bool randomize)
Definition: heur_rec.c:336
SCIP_VAR ** SCIPprobdataGetEdgeVars(SCIP *scip)
Definition: probdata_stp.c:2623
SCIP_RETCODE SCIPStpHeurRecInitPool(SCIP *scip, STPSOLPOOL **pool, const int nedges, const int maxsize)
Definition: heur_rec.c:893
SCIP_RETCODE graph_sol_markPcancestors(SCIP *, IDX **, const int *, const int *, int, STP_Bool *, STP_Bool *, int *, int *, int *)
Definition: grphbase.c:3292
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10000
SCIP_Real graph_sol_getObj(const SCIP_Real *, const int *, SCIP_Real, int)
Definition: grphbase.c:3200
Constraint handler for linear constraints in their most general form, .
static SCIP_RETCODE selectdiffsols(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:170
includes various files containing graph methods used for Steiner tree problems
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:1025
Definition: heur_rec.h:38
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
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
STPSOL * SCIPStpHeurRecSolfromIdx(STPSOLPOOL *pool, const int soindex)
Definition: heur_rec.c:869
Primal recombination heuristic for Steiner problems.
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
Definition: heur_rec.h:46
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_RETCODE SCIPStpHeurTMPrunePc(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
Definition: heur_tm.c:167
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, int *best_result)
Definition: heur_local.c:208
shortest paths based primal heuristics for Steiner problems
SCIP_RETCODE SCIPStpHeurRecAddToPool(SCIP *scip, const SCIP_Real obj, const int *soledges, STPSOLPOOL *pool, SCIP_Bool *success)
Definition: heur_rec.c:952
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
SCIP_RETCODE reduce(SCIP *, GRAPH **, SCIP_Real *, int, int, SCIP_Bool)
Definition: reduce.c:1675
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
void SCIPStpHeurRecFreePool(SCIP *scip, STPSOLPOOL **pool)
Definition: heur_rec.c:924
Definition: objbenders.h:33
SCIP_RETCODE SCIPStpHeurTMPrune(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int layer, int *result, STP_Bool *connected)
Definition: heur_tm.c:555
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
default SCIP plugins
SCIP callable library.