Detailed Description

Primal recombination heuristic for Steiner problems.

Author: 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 "grph.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 1025 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 869 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 893 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 952 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 924 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 2103 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 1594 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().

SCIP

Detailed Description

Data Structures

Typedefs

Functions

Typedef Documentation

◆ STPSOL

◆ STPSOLPOOL

Function Documentation

◆ SCIPStpHeurRecRun()

◆ SCIPStpHeurRecSolfromIdx()

◆ SCIPStpHeurRecInitPool()

◆ SCIPStpHeurRecAddToPool()

◆ SCIPStpHeurRecFreePool()

◆ SCIPStpIncludeHeurRec()

◆ SCIPStpHeurRecExclude()