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 "grph.h"
#include "heur_tm.h"
#include "cons_stp.h"
#include "scip/pub_misc.h"
#include "probdata_stp.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 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)

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

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 void	marksolverts (GRAPH g, IDX curr, int unodemap, STP_Bool stvertex)

static SCIP_Bool	isInPool (const int soledges, const STPSOLPOOL pool)

STPSOL *	SCIPStpHeurRecSolfromIdx (STPSOLPOOL *pool, const int soindex)

SCIP_RETCODE	SCIPStpHeurRecInitPool (SCIP scip, STPSOLPOOL *pool, const int nedges, const int maxsize)

void	SCIPStpHeurRecFreePool (SCIP scip, STPSOLPOOL *pool)

SCIP_RETCODE	SCIPStpHeurRecAddToPool (SCIP scip, const SCIP_Real obj, const int soledges, STPSOLPOOL pool, SCIP_Bool success)

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 47 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 48 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'R'

Definition at line 49 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 100

Definition at line 50 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 51 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 52 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 53 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 54 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 55 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 57 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 58 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 59 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 60 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 61 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 62 of file heur_rec.c.

Referenced by SCIPStpIncludeHeurRec().

◆ BOUND_MAXNTERMINALS

#define BOUND_MAXNTERMINALS 1000

Definition at line 64 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ BOUND_MAXNEDGES

#define BOUND_MAXNEDGES 20000

Definition at line 65 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ RUNS_RESTRICTED

#define RUNS_RESTRICTED 3

Definition at line 66 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ RUNS_NORMAL

#define RUNS_NORMAL 10

Definition at line 67 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ CYCLES_PER_RUN

#define CYCLES_PER_RUN 3

Definition at line 68 of file heur_rec.c.

Referenced by SCIPStpHeurRecRun().

◆ REC_MAX_FAILS

#define REC_MAX_FAILS 4

Definition at line 69 of file heur_rec.c.

Referenced by SCIPStpHeurRecRun().

◆ REC_MIN_NSOLS

#define REC_MIN_NSOLS 4

Definition at line 70 of file heur_rec.c.

Referenced by selectdiffsols(), and selectsols().

◆ REC_ADDEDGE_FACTOR

#define REC_ADDEDGE_FACTOR 1.0

Definition at line 71 of file heur_rec.c.

Referenced by buildsolgraph().

◆ COST_MAX_POLY_x0

#define COST_MAX_POLY_x0 500

Definition at line 73 of file heur_rec.c.

Referenced by edgecostmultiplier().

◆ COST_MIN_POLY_x0

#define COST_MIN_POLY_x0 100

Definition at line 74 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 110 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	SCIP data structure
avg	number of solutions containing this edge

Definition at line 128 of file heur_rec.c.

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

Referenced by SCIPStpHeurRecRun().

◆ selectdiffsols()

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
	)

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 170 of file heur_rec.c.

References CONNECT, GRAPH::edges, FALSE, GRAPH::head, Is_term, MIN, 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, sqrt(), GRAPH::tail, GRAPH::term, and TRUE.

Referenced by buildsolgraph().

◆ selectsols()

static SCIP_RETCODE selectsols	(	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 336 of file heur_rec.c.

References FALSE, MIN, 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, sqrt(), 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 465 of file heur_rec.c.

References CONNECT, GRAPH::cost, EAT_FREE, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, flipedge, graph_edge_add(), graph_init(), graph_knot_add(), graph_pc_init(), graph_pc_updateTerm2edge(), graph_valid(), GRAPH::head, GRAPH::hoplimit, Is_gterm, Is_pterm, Is_term, GRAPH::knots, GRAPH::maxdeg, nnodes, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, REC_ADDEDGE_FACTOR, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetSols(), SCIPgetSolVal(), SCIPisEQ(), SCIPprobdataGetEdgeVars(), selectdiffsols(), selectsols(), stp_solution::soledges, stp_solution_pool::sols, GRAPH::source, STP_DCSTP, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurRecRun().

◆ marksolverts()

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

static

Definition at line 815 of file heur_rec.c.

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

Referenced by SCIPStpHeurRecExclude().

◆ isInPool()

static SCIP_Bool isInPool	(	const int *	soledges,
		const STPSOLPOOL *	pool
	)

static

Parameters

soledges	edge array of solution to be checked
pool	the pool

Definition at line 834 of file heur_rec.c.

References FALSE, stp_solution_pool::nedges, NULL, SCIPdebugMessage, stp_solution_pool::size, stp_solution::soledges, stp_solution_pool::sols, and TRUE.

Referenced by SCIPStpHeurRecAddToPool().

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

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

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

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

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

static SCIP_DECL_HEUREXIT ( heurExitRec )

static

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

Definition at line 1838 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 1852 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 1866 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 1889 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 1900 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 1927 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 1935 of file heur_rec.c.

References BOUND_MAXNEDGES, BOUND_MAXNTERMINALS, DEFAULT_NUSEDSOLS, GRAPH::edges, FARAWAY, HEUR_NAME, MIN, NULL, RUNS_NORMAL, RUNS_RESTRICTED, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetNSolsFound(), SCIPgetProbData(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPheurGetData(), SCIPheurGetName(), SCIPisLT(), SCIPprobdataGetGraph(), SCIPprobdataGetVars(), SCIPrandomGetInt(), SCIPsolGetIndex(), SCIPStpHeurRecRun(), STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, 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 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().

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

◆ selectdiffsols()

◆ selectsols()

◆ buildsolgraph()

◆ marksolverts()

◆ isInPool()

◆ SCIPStpHeurRecSolfromIdx()

◆ SCIPStpHeurRecInitPool()

◆ SCIPStpHeurRecFreePool()

◆ SCIPStpHeurRecAddToPool()

◆ SCIPStpHeurRecRun()

◆ SCIPStpHeurRecExclude()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpIncludeHeurRec()