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" (2017) by Gamrath, Koch, Maher, Rehfeldt and Shinano

A list of all interface methods can be found in heur_rec.h

Definition in file heur_rec.c.

#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_linear.h"
#include "heur_rec.h"
#include "heur_prune.h"
#include "heur_slackprune.h"
#include "heur_local.h"
#include "graph.h"
#include "reduce.h"
#include "heur_tm.h"
#include "cons_stp.h"
#include "scip/pub_misc.h"
#include "probdata_stp.h"
#include "solstp.h"
#include "math.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME "rec"

#define	HEUR_DESC "recombination heuristic for Steiner problems"

#define	HEUR_DISPCHAR 'R'

#define	HEUR_PRIORITY 100

#define	HEUR_FREQ 1

#define	HEUR_FREQOFS 0

#define	HEUR_MAXDEPTH -1

#define	HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP \| SCIP_HEURTIMING_AFTERLPLOOP \| SCIP_HEURTIMING_AFTERNODE)

#define	HEUR_USESSUBSCIP FALSE

#define	DEFAULT_MAXFREQREC FALSE

#define	DEFAULT_MAXNSOLS 15

#define	DEFAULT_NUSEDSOLS 4

#define	DEFAULT_RANDSEED 1984

#define	DEFAULT_NTMRUNS 100

#define	DEFAULT_NWAITINGSOLS 4

#define	BOUND_MAXNTERMINALS 1000

#define	BOUND_MAXNEDGES 20000

#define	RUNS_RESTRICTED 3

#define	RUNS_NORMAL 10

#define	CYCLES_PER_RUN 3

#define	REC_MAX_FAILS 4

#define	REC_MIN_NSOLS 4

#define	REC_ADDEDGE_FACTOR 1.0

#define	COST_MAX_POLY_x0 500

#define	COST_MIN_POLY_x0 100

Functions
static	SCIP_DECL_PARAMCHGD (paramChgdRandomseed)

static int	edgecostmultiplier (SCIP scip, SCIP_HEURDATA heurdata, SCIP_Real avg)

static void	marksolverts (const GRAPH g, IDX curr, const int unodemap, STP_Bool RESTRICT stvertex)

static void	setHeurdataNUsedSols (SCIP_HEURDATA *heurdata, int nsols, SCIP_Bool restrictheur)

static SCIP_RETCODE	retransformReducedProbSolution (SCIP scip, const GRAPH graph, const GRAPH solgraph, const int edgeancestor, const int soledges, int newsoledges, STP_Bool *stnodes)

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)

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)

static void	initializeIncumbent (SCIP scip, const STPSOLPOOL pool, const GRAPH graph, SCIP_VAR vars, int nsols, int newsolindex, double incumentobj, int *incumbentedges)

static SCIP_Bool	poolSolIsUnreduced (const GRAPH graph, const int solindex, const STPSOLPOOL pool)

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)

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)

static SCIP_RETCODE	solgraphSelectSols (SCIP scip, const STPSOLPOOL pool, SCIP_HEURDATA heurdata, int incumbentindex, int *selection, SCIP_Bool randomize)

static void	solgraphAdaptForPcMw (const GRAPH graph, STP_Bool solnode, int nsolnodes, STP_Bool soledge, int *nsoledges)

static void	solgraphAdaptForDCSTP (const GRAPH graph, const STP_Bool solnode, STP_Bool soledge, int nsoledges)

static void	solgraphAddEdges (SCIP_HEURDATA heurdata, const GRAPH graph, const STP_Bool solnode, STP_Bool soledge, int *nsoledges)

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)

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	SCIPStpHeurRecExclude (SCIP scip, const GRAPH graph, const int result, int newresult, int dnodemap, STP_Bool stvertex, SCIP_Bool *success)

static	SCIP_DECL_HEUREXIT (heurExitRec)

static	SCIP_DECL_HEURCOPY (heurCopyRec)

static	SCIP_DECL_HEURFREE (heurFreeRec)

static	SCIP_DECL_HEURINIT (heurInitRec)

static	SCIP_DECL_HEURINITSOL (heurInitsolRec)

static	SCIP_DECL_HEUREXITSOL (heurExitsolRec)

static	SCIP_DECL_HEUREXEC (heurExecRec)

SCIP_RETCODE	SCIPStpIncludeHeurRec (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "rec"

Definition at line 49 of file heur_rec.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), and SCIPStpIncludeHeurRec().

◆ HEUR_DESC

#define HEUR_DESC "recombination heuristic for Steiner problems"

Definition at line 50 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'R'

Definition at line 51 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 100

Definition at line 52 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 53 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 54 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 55 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_TIMING

#define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)

Definition at line 56 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 57 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ DEFAULT_MAXFREQREC

#define DEFAULT_MAXFREQREC FALSE

executions of the rec heuristic at maximum frequency?

Definition at line 59 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ DEFAULT_MAXNSOLS

#define DEFAULT_MAXNSOLS 15

default maximum number of (good) solutions be regarded in the subproblem

Definition at line 60 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ DEFAULT_NUSEDSOLS

#define DEFAULT_NUSEDSOLS 4

number of solutions that will be taken into account

Definition at line 61 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINITSOL(), and SCIPStpIncludeHeurRec().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 1984

random seed

Definition at line 62 of file heur_rec.c.

Referenced by SCIP_DECL_HEURINITSOL(), and SCIPStpIncludeHeurRec().

◆ DEFAULT_NTMRUNS

#define DEFAULT_NTMRUNS 100

number of runs in TM heuristic

Definition at line 63 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ DEFAULT_NWAITINGSOLS

#define DEFAULT_NWAITINGSOLS 4

max number of new solutions to be available before executing the heuristic again

Definition at line 64 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ BOUND_MAXNTERMINALS

#define BOUND_MAXNTERMINALS 1000

Definition at line 66 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ BOUND_MAXNEDGES

#define BOUND_MAXNEDGES 20000

Definition at line 67 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ RUNS_RESTRICTED

#define RUNS_RESTRICTED 3

Definition at line 68 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ RUNS_NORMAL

#define RUNS_NORMAL 10

Definition at line 69 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ CYCLES_PER_RUN

#define CYCLES_PER_RUN 3

Definition at line 70 of file heur_rec.c.

Referenced by SCIPStpHeurRecRun().

◆ REC_MAX_FAILS

#define REC_MAX_FAILS 4

Definition at line 71 of file heur_rec.c.

Referenced by SCIPStpHeurRecRun().

◆ REC_MIN_NSOLS

#define REC_MIN_NSOLS 4

Definition at line 72 of file heur_rec.c.

Referenced by solgraphSelectSols(), and solgraphSelectSolsDiff().

◆ REC_ADDEDGE_FACTOR

#define REC_ADDEDGE_FACTOR 1.0

Definition at line 73 of file heur_rec.c.

Referenced by solgraphAddEdges().

◆ COST_MAX_POLY_x0

#define COST_MAX_POLY_x0 500

Definition at line 75 of file heur_rec.c.

Referenced by edgecostmultiplier().

◆ COST_MIN_POLY_x0

#define COST_MIN_POLY_x0 100

Definition at line 76 of file heur_rec.c.

Referenced by edgecostmultiplier().

Function Documentation

◆ SCIP_DECL_PARAMCHGD()

static SCIP_DECL_PARAMCHGD ( paramChgdRandomseed )

static

information method for a parameter change of random seed

Definition at line 113 of file heur_rec.c.

References NULL, SCIP_OKAY, SCIPparamGetData(), and SCIPparamGetInt().

◆ edgecostmultiplier()

static int edgecostmultiplier	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		SCIP_Real	avg
	)

static

edge cost multiplier

Parameters

scip	SCIP data structure
heurdata	heuristic data structure
avg	number of solutions containing this edge

Definition at line 131 of file heur_rec.c.

References COST_MAX_POLY_x0, COST_MIN_POLY_x0, MAX, SCIP_Real, SCIPisGE(), SCIPisLE(), and SCIPrandomGetInt().

Referenced by computeReducedProbSolutionBiased().

◆ marksolverts()

static void marksolverts	(	const GRAPH *	g,
		IDX *	curr,
		const int *	unodemap,
		STP_Bool *RESTRICT	stvertex
	)

inlinestatic

Definition at line 173 of file heur_rec.c.

References Int_List_Node::index, NULL, GRAPH::orghead, GRAPH::orgtail, Int_List_Node::parent, and TRUE.

Referenced by SCIPStpHeurRecExclude().

◆ setHeurdataNUsedSols()

static void setHeurdataNUsedSols	(	SCIP_HEURDATA *	heurdata,
		int	nsols,
		SCIP_Bool	restrictheur
	)

static

Parameters

heurdata	heuristic data structure
nsols	number of solutions
restrictheur	restrict heuristic?

Definition at line 193 of file heur_rec.c.

References SCIPrandomGetInt().

Referenced by SCIPStpHeurRecRun().

◆ retransformReducedProbSolution()

static SCIP_RETCODE retransformReducedProbSolution	(	SCIP *	scip,
		const GRAPH *	graph,
		const GRAPH *	solgraph,
		const int *	edgeancestor,
		const int *	soledges,
		int *	newsoledges,
		STP_Bool *	stnodes
	)

static

compute (heuristic) solution on reduced (and merged) problem

Parameters

scip	SCIP data structure
graph	graph data
solgraph	graph data
edgeancestor	ancestor to edge
soledges	old solution edges
newsoledges	new solution edges
stnodes	new solution nodes

Definition at line 217 of file heur_rec.c.

References CONNECT, GRAPH::edges, FALSE, graph_edge_getAncestors(), graph_getFixedges(), graph_pc_isPcMw(), GRAPH::head, Int_List_Node::index, GRAPH::knots, nnodes, NULL, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgtail, Int_List_Node::parent, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, solstp_markPcancestors(), STP_DCSTP, GRAPH::stp_type, GRAPH::tail, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurRecRun().

◆ computeReducedProbSolutionBiased()

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
	)

static

compute (heuristic) solution on reduced (and merged) problem

Parameters

scip	SCIP data structure
heurdata	heuristic data
graph	graph data
solgraph	graph data
edgeweight	for each edge: number of solution that contain this edge
edgeancestor	ancestor to edge edge
vars	variables or NULL
usestppool	using STP pool?
soledges	solution edges
success	success?

Definition at line 355 of file heur_rec.c.

References BLOCKED, BMScopyMemoryArray, GRAPH::cost, edgecostmultiplier(), GRAPH::edges, GRAPH::extended, FALSE, flipedge, graph_edge_getAncestors(), graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_isPcMw(), GRAPH::head, Int_List_Node::index, Is_pseudoTerm, Is_term, GRAPH::knots, MAX, NULL, Int_List_Node::parent, pcmode_fromheurdata, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisStopped(), SCIPStpHeurLocalRun(), SCIPStpHeurTMRun(), SCIPvarGetUbGlobal(), solstp_isValid(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_NWPTSPG, STP_NWSPG, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by computeReducedProbSolution().

◆ computeReducedProbSolution()

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
	)

static

compute (heuristic) solution on reduced (and merged) problem

Parameters

scip	SCIP data structure
heurdata	heuristic data
graph	graph data
solgraph	graph data
redsol	reduction solution
edgeweight	for each edge: number of solution that contain this edge
edgeancestor	ancestor to edge edge
vars	variables or NULL
usestppool	using STP pool?
soledges	solution edges
success	success?

Definition at line 489 of file heur_rec.c.

References BMScopyMemoryArray, computeReducedProbSolutionBiased(), GRAPH::edges, EQ, FARAWAY, graph_path_exit(), graph_path_init(), graph_pc_isPcMw(), graph_typeIsSpgLike(), graph_valid(), GRAPH::knots, LT, NULL, reduce_solGetEdgesol(), reduce_solUsesNodesol(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, solstp_getObj(), solstp_isValid(), STP_RMWCSP, GRAPH::stp_type, and GRAPH::terms.

Referenced by SCIPStpHeurRecRun().

◆ initializeIncumbent()

static void initializeIncumbent	(	SCIP *	scip,
		const STPSOLPOOL *	pool,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		int	nsols,
		int	newsolindex,
		double *	incumentobj,
		int *	incumbentedges
	)

static

initialize solution vector and objective of incumbent

Parameters

scip	SCIP data structure
pool	solution pool or NULL
graph	graph data structure
vars	problem variables
nsols	number of solutions in pool (SCIP or STP)
newsolindex	index of new solution
incumentobj	pointer to incumbent value
incumbentedges	edges of solution to be used as recombination root

Definition at line 554 of file heur_rec.c.

References BMScopyMemoryArray, CONNECT, GRAPH::edges, stp_solution_pool::nedges, NULL, SCIPgetSols(), SCIPgetSolVal(), SCIPisEQ(), SCIPsolGetIndex(), stp_solution_pool::sols, solstp_getObjBounded(), and UNKNOWN.

Referenced by SCIPStpHeurRecRun().

◆ poolSolIsUnreduced()

static SCIP_Bool poolSolIsUnreduced	(	const GRAPH *	graph,
		const int	solindex,
		const STPSOLPOOL *	pool
	)

static

any edge of given solution deleted?

Parameters

graph	graph structure
solindex	the index
pool	the pool

Definition at line 612 of file heur_rec.c.

References CONNECT, EAT_FREE, GRAPH::edges, FALSE, GRAPH::oeat, stp_solution::soledges, stp_solution_pool::sols, and TRUE.

Referenced by buildsolgraph().

◆ poolAddSol()

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
	)

static

store solution in (SCIP or STP) pool

Parameters

scip	SCIP data structure
pool	STP solution pool or NULL
heur	heuristic or NULL
incumentobj	objective of solution to be added
incumbentedges	edge array of solution to be added
nedges	nedges
newsolindex	index of new solution
soladded	solution added?

Definition at line 640 of file heur_rec.c.

References CONNECT, stp_solution_pool::maxindex, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetNSols(), SCIPgetSols(), SCIPprobdataAddNewSol(), SCIPsolGetIndex(), and solpool_addSol().

Referenced by SCIPStpHeurRecRun().

◆ solgraphSelectSolsDiff()

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
	)

static

select solutions to be merged

Parameters

scip	SCIP data structure
pool	solution pool or NULL
graph	graph data structure
heurdata	SCIP data structure
vars	problem variables
incumbentedges	edges of solution to be used as recombination root
incumbentindex	index of ancestor of incumbent solution
selection	selected solutions
success	could at least two solutions be selected?

Definition at line 711 of file heur_rec.c.

References CONNECT, GRAPH::edges, FALSE, graph_pc_isPcMw(), GRAPH::head, Is_term, NULL, REC_MIN_NSOLS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetNSols(), SCIPgetSols(), SCIPgetSolVal(), SCIPisEQ(), SCIPrandomPermuteIntArray(), SCIPsolGetIndex(), stp_solution_pool::size, stp_solution::soledges, stp_solution_pool::sols, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by buildsolgraph().

◆ solgraphSelectSols()

static SCIP_RETCODE solgraphSelectSols	(	SCIP *	scip,
		const STPSOLPOOL *	pool,
		SCIP_HEURDATA *	heurdata,
		int *	incumbentindex,
		int *	selection,
		SCIP_Bool	randomize
	)

static

select solutions to be merged

Parameters

scip	SCIP data structure
pool	solution pool or NULL
heurdata	SCIP data structure
incumbentindex	index of ancestor of incumbent solution
selection	selected solutions
randomize	select solutions randomly?

Definition at line 880 of file heur_rec.c.

References FALSE, NULL, REC_MIN_NSOLS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetNSols(), SCIPgetSols(), SCIPrandomGetInt(), SCIPrandomPermuteIntArray(), SCIPsolGetIndex(), stp_solution_pool::size, stp_solution_pool::sols, and TRUE.

Referenced by buildsolgraph().

◆ solgraphAdaptForPcMw()

static void solgraphAdaptForPcMw	(	const GRAPH *	graph,
		STP_Bool *	solnode,
		int *	nsolnodes,
		STP_Bool *	soledge,
		int *	nsoledges
	)

static

adapt merged solution graph for PC/MW

Parameters

graph	graph structure
solnode	solution nodes array
nsolnodes	number of nodes pointer
soledge	solution edges array
nsoledges	number of edges pointer

Definition at line 1010 of file heur_rec.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_pc_getRoot2PtermEdge(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, Is_pseudoTerm, GRAPH::knots, nnodes, GRAPH::source, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by buildsolgraph().

◆ solgraphAdaptForDCSTP()

static void solgraphAdaptForDCSTP	(	const GRAPH *	graph,
		const STP_Bool *	solnode,
		STP_Bool *	soledge,
		int *	nsoledges
	)

static

adapt merged solution graph for DCSTP

Parameters

graph	graph structure
solnode	solution nodes array
soledge	solution edges array
nsoledges	number of edges pointer

Definition at line 1096 of file heur_rec.c.

References EAT_LAST, GRAPH::head, Is_term, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::term, and TRUE.

Referenced by buildsolgraph().

◆ solgraphAddEdges()

static void solgraphAddEdges	(	SCIP_HEURDATA *	heurdata,
		const GRAPH *	graph,
		const STP_Bool *	solnode,
		STP_Bool *	soledge,
		int *	nsoledges
	)

static

add additional edges to solution graph

Parameters

heurdata	SCIP data structure
graph	graph structure
solnode	solution nodes array
soledge	solution edges array
nsoledges	number of edges pointer

Definition at line 1127 of file heur_rec.c.

References EAT_FREE, GRAPH::edges, GRAPH::head, GRAPH::oeat, REC_ADDEDGE_FACTOR, SCIPdebugMessage, SCIPrandomGetInt(), GRAPH::tail, and TRUE.

Referenced by buildsolgraph().

◆ buildsolgraph()

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
	)

static

merge selected solutions to a new graph

Parameters

scip	SCIP data structure
pool	solution pool or NULL
heurdata	SCIP data structure
graph	graph structure
solgraph	pointer to store new graph
incumbentedges	edges of solution to be used as recombination root
incumbentindex	index of ancestor of incumbent solution
edgeancestor	ancestor to edge edge
edgeweight	for each edge: number of solution that contain this edge
success	new graph constructed?
randomize	select solution randomly?
addedges	add additional edges between solution vertices?

Definition at line 1170 of file heur_rec.c.

References CONNECT, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, graph_edge_addSubgraph(), graph_free(), graph_init(), graph_knot_add(), graph_pc_finalizeSubgraph(), graph_pc_initSubgraph(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_nFixedTerms(), graph_valid(), GRAPH::head, GRAPH::hoplimit, GRAPH::knots, GRAPH::maxdeg, nnodes, GRAPH::norgmodelknots, NULL, GRAPH::oeat, poolSolIsUnreduced(), GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetSols(), SCIPgetSolVal(), SCIPisEQ(), SCIPprobdataGetEdgeVars(), stp_solution::soledges, solgraphAdaptForDCSTP(), solgraphAdaptForPcMw(), solgraphAddEdges(), solgraphSelectSols(), solgraphSelectSolsDiff(), stp_solution_pool::sols, GRAPH::source, STP_DCSTP, STP_GSTP, STP_OARSMT, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurRecRun().

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

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 heuristic?
solfound	new 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().

◆ 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 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().

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitRec )

static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 1885 of file heur_rec.c.

References NULL, SCIP_OKAY, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyRec )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 1899 of file heur_rec.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPStpIncludeHeurRec().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeRec )

static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 1913 of file heur_rec.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPfreeRandom(), SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitRec )

static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 1936 of file heur_rec.c.

References NULL, and SCIP_OKAY.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolRec )

static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 1947 of file heur_rec.c.

References DEFAULT_NUSEDSOLS, DEFAULT_RANDSEED, NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolRec )

static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 1977 of file heur_rec.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecRec )

static

execution method of primal heuristic

Definition at line 1985 of file heur_rec.c.

References BOUND_MAXNEDGES, BOUND_MAXNTERMINALS, DEFAULT_NUSEDSOLS, GRAPH::edges, FARAWAY, graph_pc_isPc(), graph_pc_isPcMw(), HEUR_NAME, NULL, RUNS_NORMAL, RUNS_RESTRICTED, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetNSolsFound(), SCIPgetProbData(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPheurGetData(), SCIPheurGetName(), SCIPisLT(), SCIPprobdataGetGraph(), SCIPprobdataGetVars(), SCIPprobdataProbIsAdversarial(), SCIPrandomGetInt(), SCIPsolGetIndex(), SCIPStpHeurRecRun(), STP_BRMWCSP, STP_DCSTP, STP_DHCSTP, GRAPH::stp_type, and GRAPH::terms.

◆ SCIPStpIncludeHeurRec()

SCIP_RETCODE SCIPStpIncludeHeurRec ( SCIP * scip )

creates the rec primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2161 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(), SCIP_DECL_HEURCOPY(), and subscipSetupCallbacks().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXFREQREC

◆ DEFAULT_MAXNSOLS

◆ DEFAULT_NUSEDSOLS

◆ DEFAULT_RANDSEED

◆ DEFAULT_NTMRUNS

◆ DEFAULT_NWAITINGSOLS

◆ BOUND_MAXNTERMINALS

◆ BOUND_MAXNEDGES

◆ RUNS_RESTRICTED

◆ RUNS_NORMAL

◆ CYCLES_PER_RUN

◆ REC_MAX_FAILS

◆ REC_MIN_NSOLS

◆ REC_ADDEDGE_FACTOR

◆ COST_MAX_POLY_x0

◆ COST_MIN_POLY_x0

Function Documentation

◆ SCIP_DECL_PARAMCHGD()

◆ edgecostmultiplier()

◆ marksolverts()

◆ setHeurdataNUsedSols()

◆ retransformReducedProbSolution()

◆ computeReducedProbSolutionBiased()

◆ computeReducedProbSolution()

◆ initializeIncumbent()

◆ poolSolIsUnreduced()

◆ poolAddSol()

◆ solgraphSelectSolsDiff()

◆ solgraphSelectSols()

◆ solgraphAdaptForPcMw()

◆ solgraphAdaptForDCSTP()

◆ solgraphAddEdges()

◆ buildsolgraph()

◆ SCIPStpHeurRecRun()

◆ SCIPStpHeurRecExclude()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpIncludeHeurRec()