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

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

Go to the source code of this file.

Macros
#define	HEUR_NAME "rec"

#define	HEUR_DESC "LNS heuristic fixing all variables corresponding to edges used in at least one of several selected solutions"

#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 TRUE

#define	DEFAULT_MAXFREQREC FALSE

#define	DEFAULT_MAXNSOLS 50

#define	DEFAULT_NUSEDSOLS 4

#define	DEFAULT_RANDSEED 0

#define	DEFAULT_NTMRUNS 75

#define	DEFAULT_NWAITINGSOLS 4

Functions
static	SCIP_DECL_PARAMCHGD (paramChgdRandomseed)

static SCIP_Real	costMultiplier (SCIP scip, SCIP_HEURDATA heurdata, SCIP_Real avg)

static SCIP_RETCODE	selectdiffsols (SCIP scip, GRAPH graph, SCIP_HEURDATA heurdata, SCIP_VAR vars, SCIP_SOL newsol, int selection, SCIP_Bool *success)

static SCIP_RETCODE	selectsols (SCIP scip, SCIP_HEURDATA heurdata, SCIP_SOL *newsol, int selection, SCIP_Bool randomize)

static SCIP_RETCODE	buildsolgraph (SCIP scip, SCIP_HEURDATA heurdata, SCIP_SOL *newsol, GRAPH graph, GRAPH solgraph, int edgeancestor, int *edgeweight, SCIP_Bool success, SCIP_Bool randomize)

static	SCIP_DECL_HEURCOPY (heurCopyRec)

static	SCIP_DECL_HEURFREE (heurFreeRec)

static	SCIP_DECL_HEURINIT (heurInitRec)

static	SCIP_DECL_HEUREXEC (heurExecRec)

SCIP_RETCODE	SCIPincludeHeurRec (SCIP *scip)

Macro Definition Documentation

#define DEFAULT_MAXFREQREC FALSE

executions of the rec heuristic at maximum frequency?

Definition at line 54 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define DEFAULT_MAXNSOLS 50

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

Definition at line 55 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define DEFAULT_NTMRUNS 75

number of runs in TM heuristic

Definition at line 58 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define DEFAULT_NUSEDSOLS 4

number of solutions that will be taken into account

Definition at line 56 of file heur_rec.c.

Referenced by SCIP_DECL_HEUREXEC(), and SCIPincludeHeurRec().

#define DEFAULT_NWAITINGSOLS 4

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

Definition at line 59 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define DEFAULT_RANDSEED 0

random seed

Definition at line 57 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define HEUR_DESC "LNS heuristic fixing all variables corresponding to edges used in at least one of several selected solutions"

Definition at line 45 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define HEUR_DISPCHAR 'R'

Definition at line 46 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define HEUR_FREQ 1

Definition at line 48 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define HEUR_FREQOFS 0

Definition at line 49 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define HEUR_MAXDEPTH -1

Definition at line 50 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define HEUR_NAME "rec"

Definition at line 44 of file heur_rec.c.

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

#define HEUR_PRIORITY 100

Definition at line 47 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)

Definition at line 51 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

#define HEUR_USESSUBSCIP TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 52 of file heur_rec.c.

Referenced by SCIPincludeHeurRec().

Function Documentation

static SCIP_RETCODE buildsolgraph	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		SCIP_SOL **	newsol,
		GRAPH *	graph,
		GRAPH **	solgraph,
		int **	edgeancestor,
		int **	edgeweight,
		SCIP_Bool *	success,
		SCIP_Bool	randomize
	)

static

merge selected solutions to a new graph

Parameters

scip	SCIP data structure
heurdata	SCIP data structure
newsol	new solution
graph	graph structure
solgraph	pointer to store new graph
edgeancestor	ancestor to edge edge
edgeweight	fore each edge: number of solution that contain this edge
success	new graph constructed?
randomize	select solution randomly?

Definition at line 451 of file heur_rec.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, graph_edge_add(), graph_init(), graph_knot_add(), GSTP, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, Is_gterm, Is_pterm, Is_term, GRAPH::knots, GRAPH::maxdeg, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPprobdataGetEdgeVars(), selectdiffsols(), selectsols(), GRAPH::source, STP_DEG_CONS, STP_GRID, STP_MAX_NODE_WEIGHT, STP_OBSTACLES_GRID, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, STP_UNDIRECTED, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_Real costMultiplier	(	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 112 of file heur_rec.c.

References SCIP_HeurData::nusedsols.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEURCOPY ( heurCopyRec )

static

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

Definition at line 702 of file heur_rec.c.

References HEUR_NAME, and SCIPincludeHeurRec().

static SCIP_DECL_HEUREXEC ( heurExecRec )

static

execution method of primal heuristic

Definition at line 767 of file heur_rec.c.

References GRAPH::ancestors, BLOCKED, buildsolgraph(), CONNECT, GRAPH::cost, costMultiplier(), DEFAULT_NUSEDSOLS, GRAPH::edges, FALSE, GRAPH::fixedges, flipedge, graph_free(), graph_pack(), graph_path_exit(), graph_path_init(), graph_sol_valid(), graph_valid(), GRAPH::head, HEUR_NAME, SCIP_HeurData::hopfactor, Int_List_Node::index, GRAPH::knots, SCIP_HeurData::lastsolindex, SCIP_HeurData::nlastsols, Int_List_Node::parent, reduce(), SCIPheurComputeSteinerTree(), SCIPheurImproveSteinerTree(), SCIPheurPruneDegConsSteinerTree(), SCIPheurPrunePCSteinerTree(), SCIPheurPruneSteinerTree(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), GRAPH::source, STP_DEG_CONS, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, STP_UNDIRECTED, GRAPH::tail, GRAPH::terms, TRUE, and UNKNOWN.

static SCIP_DECL_HEURFREE ( heurFreeRec )

static

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

Definition at line 716 of file heur_rec.c.

static SCIP_DECL_HEURINIT ( heurInitRec )

static

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

Definition at line 736 of file heur_rec.c.

static SCIP_DECL_PARAMCHGD ( paramChgdRandomseed )

static

information method for a parameter change of random seed

Definition at line 95 of file heur_rec.c.

SCIP_RETCODE SCIPincludeHeurRec ( SCIP * scip )

creates the rec primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1236 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, and HEUR_USESSUBSCIP.

Referenced by runShell(), and SCIP_DECL_HEURCOPY().

static SCIP_RETCODE selectdiffsols	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_HEURDATA *	heurdata,
		SCIP_VAR **	vars,
		SCIP_SOL **	newsol,
		int *	selection,
		SCIP_Bool *	success
	)

static

select solutions to be merged

Parameters

scip	SCIP data structure
graph	graph data structure
heurdata	SCIP data structure
vars	problem variables
newsol	new solution
selection	selected solutions
success	could at least two solutions be selected?

Definition at line 170 of file heur_rec.c.

References GRAPH::edges, FALSE, GRAPH::head, Is_term, SCIP_HeurData::maxnsols, SCIP_HeurData::nselectedsols, SCIP_HeurData::nusedsols, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by buildsolgraph().

static SCIP_RETCODE selectsols	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		SCIP_SOL **	newsol,
		int *	selection,
		SCIP_Bool	randomize
	)

static

select solutions to be merged

Parameters

scip	SCIP data structure
heurdata	SCIP data structure
newsol	new solution
selection	selected solutions
randomize	select solutions randomly?

Definition at line 329 of file heur_rec.c.

References FALSE, SCIP_HeurData::maxnsols, SCIP_HeurData::nselectedsols, SCIP_HeurData::nusedsols, and TRUE.

Referenced by buildsolgraph().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation