Detailed Description
Primal recombination heuristic for Steiner problems.
This file implements a recombination heuristic for Steiner problems, see "SCIP-Jack - A solver for STP and variants with parallelization extensions" by Gamrath, Koch, Maher, Rehfeldt and Shinano
Definition in file heur_rec.h.
Go to the source code of this file.
Data Structures | |
struct | stp_solution |
struct | stp_solution_pool |
Typedefs | |
typedef struct stp_solution | STPSOL |
typedef struct stp_solution_pool | STPSOLPOOL |
Functions | |
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) |
STPSOL * | SCIPStpHeurRecSolfromIdx (STPSOLPOOL *pool, const int soindex) |
SCIP_RETCODE | SCIPStpHeurRecInitPool (SCIP *scip, STPSOLPOOL **pool, const int nedges, const int maxsize) |
SCIP_RETCODE | SCIPStpHeurRecAddToPool (SCIP *scip, const SCIP_Real obj, const int *soledges, STPSOLPOOL *pool, SCIP_Bool *success) |
void | SCIPStpHeurRecFreePool (SCIP *scip, STPSOLPOOL **pool) |
SCIP_RETCODE | SCIPStpIncludeHeurRec (SCIP *scip) |
SCIP_RETCODE | SCIPStpHeurRecExclude (SCIP *scip, const GRAPH *graph, const int *result, int *newresult, int *dnodemap, STP_Bool *stvertex, SCIP_Bool *success) |
Typedef Documentation
◆ STPSOL
typedef struct stp_solution STPSOL |
element of Steiner tree solution pool
◆ STPSOLPOOL
typedef struct stp_solution_pool STPSOLPOOL |
edge based solution pool for Steiner tree problems (in presolving)
Function Documentation
◆ SCIPStpHeurRecRun()
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 | ||
) |
run REC heuristic
runs STP recombination heuristic
- Parameters
-
scip SCIP data structure pool STP solution pool or NULL heur heuristic or NULL heurdata heuristic data or NULL graph graph data vars variables or NULL newsolindex index of new solution runs number of runs nsols number of solutions in pool (SCIP or STP) restrictheur use restricted version of heur? solfound new solution found?
Definition at line 1026 of file heur_rec.c.
References GRAPH::ancestors, BLOCKED, BMScopyMemoryArray, buildsolgraph(), CONNECT, GRAPH::cost, CYCLES_PER_RUN, EAT_LAST, edgecostmultiplier(), GRAPH::edges, GRAPH::extended, FALSE, GRAPH::fixedges, flipedge, graph_free(), graph_pack(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_term2edgeConsistent(), graph_sol_getObj(), graph_sol_markPcancestors(), graph_sol_valid(), graph_valid(), GRAPH::head, GRAPH::ieat, Int_List_Node::index, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, stp_solution_pool::maxindex, stp_solution_pool::nedges, nnodes, NULL, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgtail, Int_List_Node::parent, GRAPH::pcancestors, GRAPH::prize, REC_MAX_FAILS, reduce(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeMemoryArray, SCIPgetNSols(), SCIPgetSols(), SCIPgetSolVal(), SCIPheurGetData(), SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPisStopped(), SCIPprobdataAddNewSol(), SCIPrandomGetInt(), SCIPsolGetIndex(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurTMBuildTreeDc(), SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), SCIPvarGetUbGlobal(), stp_solution_pool::sols, GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_NWSPG, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, TRUE, and UNKNOWN.
Referenced by computeDaSolPcMw(), reduce_da(), and SCIP_DECL_HEUREXEC().
◆ SCIPStpHeurRecSolfromIdx()
STPSOL* SCIPStpHeurRecSolfromIdx | ( | STPSOLPOOL * | pool, |
const int | soindex | ||
) |
get solution from index
- Parameters
-
pool the pool soindex the index
Definition at line 870 of file heur_rec.c.
References stp_solution::index, NULL, stp_solution_pool::size, and stp_solution_pool::sols.
Referenced by computeDaSolPcMw(), and reduce_da().
◆ SCIPStpHeurRecInitPool()
SCIP_RETCODE SCIPStpHeurRecInitPool | ( | SCIP * | scip, |
STPSOLPOOL ** | pool, | ||
const int | nedges, | ||
const int | maxsize | ||
) |
initializes STPSOL pool
- Parameters
-
scip SCIP data structure pool the pool nedges number of edges of solutions to be stored in the pool maxsize capacity of pool
Definition at line 894 of file heur_rec.c.
References stp_solution_pool::maxindex, stp_solution_pool::maxsize, stp_solution_pool::nedges, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocMemoryArray, stp_solution_pool::size, and stp_solution_pool::sols.
Referenced by reduce_da(), and reduce_daPcMw().
◆ SCIPStpHeurRecAddToPool()
SCIP_RETCODE SCIPStpHeurRecAddToPool | ( | SCIP * | scip, |
const SCIP_Real | obj, | ||
const int * | soledges, | ||
STPSOLPOOL * | pool, | ||
SCIP_Bool * | success | ||
) |
tries to add STPSOL to pool
- Parameters
-
scip SCIP data structure obj objective of solution to be added soledges edge array of solution to be added pool the pool success has solution been added?
Definition at line 953 of file heur_rec.c.
References BMScopyMemoryArray, FALSE, stp_solution::index, isInPool(), stp_solution_pool::maxindex, stp_solution_pool::maxsize, stp_solution_pool::nedges, NULL, stp_solution::obj, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocMemoryArray, SCIPdebugMessage, SCIPisGT(), stp_solution_pool::size, stp_solution::soledges, stp_solution_pool::sols, and TRUE.
Referenced by computeDaSolPcMw(), reduce_da(), reduce_daPcMw(), and SCIPStpHeurRecRun().
◆ SCIPStpHeurRecFreePool()
void SCIPStpHeurRecFreePool | ( | SCIP * | scip, |
STPSOLPOOL ** | pool | ||
) |
frees STPSOL pool
- Parameters
-
scip SCIP data structure pool the pool
Definition at line 925 of file heur_rec.c.
References stp_solution_pool::maxsize, NULL, SCIPfreeBlockMemory, SCIPfreeMemoryArray, stp_solution_pool::size, stp_solution::soledges, and stp_solution_pool::sols.
Referenced by markPcMwRoots(), reduce_da(), and reduce_daPcMw().
◆ SCIPStpIncludeHeurRec()
SCIP_RETCODE SCIPStpIncludeHeurRec | ( | SCIP * | scip | ) |
creates the rec primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 2104 of file heur_rec.c.
References DEFAULT_MAXFREQREC, DEFAULT_MAXNSOLS, DEFAULT_NTMRUNS, DEFAULT_NUSEDSOLS, DEFAULT_NWAITINGSOLS, DEFAULT_RANDSEED, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPcreateRandom(), SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExit(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), SCIPsetHeurInitsol(), and TRUE.
Referenced by runShell(), and SCIP_DECL_HEURCOPY().
◆ SCIPStpHeurRecExclude()
SCIP_RETCODE SCIPStpHeurRecExclude | ( | SCIP * | scip, |
const GRAPH * | graph, | ||
const int * | result, | ||
int * | newresult, | ||
int * | dnodemap, | ||
STP_Bool * | stvertex, | ||
SCIP_Bool * | success | ||
) |
heuristic to exclude vertices or edges from a given solution (and inserting other edges) to improve objective
- Parameters
-
scip SCIP data structure graph graph structure result edge solution array (UNKNOWN/CONNECT) newresult new edge solution array (UNKNOWN/CONNECT) dnodemap node array for internal use stvertex node array for internally marking solution vertices success solution improved?
Definition at line 1595 of file heur_rec.c.
References GRAPH::ancestors, BMSclearMemoryArray, CONNECT, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, GRAPH::fixedges, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_path_exit(), graph_path_init(), graph_pc_init(), graph_pc_updateTerm2edge(), graph_sol_getObj(), graph_sol_markPcancestors(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, marksolverts(), MIN, nnodes, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, GRAPH::prize, reduce(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBufferArray, SCIPheurGetData(), SCIPisLT(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.
Referenced by computeDaSolPcMw().