Solving Constraint Integer Programs

heur_rec.h File Reference

Detailed Description

Primal recombination heuristic for Steiner problems.

Daniel Rehfeldt

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.

#include "scip/scip.h"
#include "graph.h"
#include "solpool.h"

Go to the source code of this file.


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)
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)

Function Documentation

◆ SCIPStpHeurRecRun()

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

scipSCIP data structure
poolSTP solution pool or NULL
heurheuristic or NULL
heurdataheuristic data or NULL
graphgraph data
varsvariables or NULL
newsolindexindex of new solution
runsnumber of runs
nsolsnumber of solutions in pool (SCIP or STP)
restrictheuruse restricted version of heuristic?
solfoundnew solution found?

Definition at line 1455 of file heur_rec.c.

References BMScopyMemoryArray, buildsolgraph(), computeReducedProbSolution(), CYCLES_PER_RUN, GRAPH::edges, FALSE, FARAWAY, graph_free(), graph_pack(), graph_typeIsUndirected(), graph_valid(), initializeIncumbent(), GRAPH::knots, nnodes, NULL, poolAddSol(), REC_MAX_FAILS, reduce_exec(), reduce_solFree(), reduce_solInit(), retransformReducedProbSolution(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeMemoryArray, SCIPheurGetData(), SCIPisLT(), SCIPisStopped(), SCIPrandomGetInt(), SCIPStpHeurTMBuildTreeDc(), setHeurdataNUsedSols(), solstp_getObjBounded(), solstp_isValid(), solstp_prune(), STP_DCSTP, STP_DHCSTP, STP_REDUCTION_ADVANCED, STP_RMWCSP, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsPcMw(), and SCIP_DECL_HEUREXEC().

◆ SCIPStpIncludeHeurRec()

◆ 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

scipSCIP data structure
graphgraph structure
resultedge solution array (UNKNOWN/CONNECT)
newresultnew edge solution array (UNKNOWN/CONNECT)
dnodemapnode array for internal use
stvertexnode array for internally marking solution vertices
successsolution improved?

Definition at line 1649 of file heur_rec.c.

References BMSclearMemoryArray, CONNECT, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, graph_edge_addSubgraph(), graph_edge_getAncestors(), graph_free(), graph_getFixedges(), graph_init(), graph_knot_add(), graph_path_exit(), graph_path_init(), graph_pc_finalizeSubgraph(), graph_pc_initSubgraph(), graph_pc_isPcMw(), graph_valid(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, marksolverts(), nnodes, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, pcmode_fromheurdata, GRAPH::prize, reduce_exec(), reduce_solFree(), reduce_solInit(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisLT(), SCIPisZero(), SCIPStpHeurTMRun(), solstp_getObjBounded(), solstp_isValid(), solstp_markPcancestors(), solstp_prune(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by computeSteinerTreeRedCostsPcMw().