Detailed Description

lurking-bounds reduction based primal heuristic for Steiner problems

Author: Daniel Rehfeldt

This file implements a reduction based heuristic for Steiner problems that makes use of lurking bounds.

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

#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_linear.h"
#include "heur_lurkprune.h"
#include "heur_ascendprune.h"
#include "dualascent.h"
#include "heur_local.h"
#include "heur_prune.h"
#include "graph.h"
#include "reduce.h"
#include "heur_tm.h"
#include "solstp.h"
#include "cons_stp.h"
#include "probdata_stp.h"
#include "prop_stp.h"

Go to the source code of this file.

Data Structures
struct	lurking_prune

Macros
#define	SCIP_DEBUG

#define	HEUR_NAME "lurkprune"

#define	HEUR_DESC "Reduction based heuristic for Steiner problems"

#define	HEUR_DISPCHAR 'L'

#define	HEUR_PRIORITY 1

#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_LURKPRUNE_MAXFREQ FALSE

#define	LURKPRUNE_NTMRUNS 30

#define	LURKPRUNE_MINREDELIMS 10

#define	LURKPRUNE_MAXREDROUNDS 10

#define	LURKPRUNE_MINLURKEDGE_RATIO 0.05

#define	LURKPRUNE_MINSTALLPROPORTION 0.25

#define	LURKPRUNE_MAXSTALLPROPORTION 0.5

#define	LURK_MAXTOTNEDGES 5000

Typedefs
typedef struct lurking_prune	LURKPRUNE

Functions
static SCIP_RETCODE	prunegraphInit (SCIP scip, const GRAPH g, GRAPH **prunegraph)

static SCIP_RETCODE	lurkpruneInit (SCIP scip, const GRAPH g, const SCIP_Real lurkingbounds, int soledge, LURKPRUNE lurkprune, GRAPH *prunegraph)

static void	lurkpruneFinalize (SCIP scip, const GRAPH g, GRAPH prunegraph, int soledge, LURKPRUNE lurkprune, SCIP_Bool solimproved)

static SCIP_RETCODE	reduceExact (SCIP scip, LURKPRUNE lurkprune, GRAPH *prunegraph)

static SCIP_RETCODE	reduceLurk (SCIP scip, LURKPRUNE lurkprune, GRAPH prunegraph, SCIP_Bool success)

static void	reduceFixedVars (SCIP scip, SCIP_VAR vars, const int soledge, GRAPH *prunegraph)

static SCIP_RETCODE	updateSolution (SCIP scip, GRAPH g, LURKPRUNE lurkprune, GRAPH prunegraph)

static	SCIP_DECL_HEURCOPY (heurCopyLurkPrune)

static	SCIP_DECL_HEURFREE (heurFreeLurkPrune)

static	SCIP_DECL_HEURINIT (heurInitLurkPrune)

static	SCIP_DECL_HEURINITSOL (heurInitsolLurkPrune)

static	SCIP_DECL_HEUREXITSOL (heurExitsolLurkPrune)

static	SCIP_DECL_HEUREXEC (heurExecLurkPrune)

SCIP_RETCODE	SCIPStpHeurLurkPruneRun (SCIP scip, SCIP_VAR vars, const SCIP_Real lurkingbounds, GRAPH g, SCIP_Bool initialreduce, SCIP_Bool ascendprune, int soledge, SCIP_Bool *solimproved)

SCIP_RETCODE	SCIPStpIncludeHeurLurkPrune (SCIP *scip)

Macro Definition Documentation

◆ SCIP_DEBUG

#define SCIP_DEBUG

Definition at line 27 of file heur_lurkprune.c.

Referenced by SCIPexprintGrad().

◆ HEUR_NAME

#define HEUR_NAME "lurkprune"

Definition at line 47 of file heur_lurkprune.c.

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

◆ HEUR_DESC

#define HEUR_DESC "Reduction based heuristic for Steiner problems"

Definition at line 48 of file heur_lurkprune.c.

Referenced by SCIPStpIncludeHeurLurkPrune().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'L'

Definition at line 49 of file heur_lurkprune.c.

Referenced by SCIPStpIncludeHeurLurkPrune().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 1

Definition at line 50 of file heur_lurkprune.c.

Referenced by SCIPStpIncludeHeurLurkPrune().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 51 of file heur_lurkprune.c.

Referenced by SCIPStpIncludeHeurLurkPrune().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 52 of file heur_lurkprune.c.

Referenced by SCIPStpIncludeHeurLurkPrune().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 53 of file heur_lurkprune.c.

Referenced by SCIPStpIncludeHeurLurkPrune().

◆ HEUR_TIMING

#define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)

Definition at line 54 of file heur_lurkprune.c.

Referenced by SCIPStpIncludeHeurLurkPrune().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 55 of file heur_lurkprune.c.

Referenced by SCIPStpIncludeHeurLurkPrune().

◆ DEFAULT_LURKPRUNE_MAXFREQ

#define DEFAULT_LURKPRUNE_MAXFREQ FALSE

executions of the heuristic at maximum frequency?

Definition at line 57 of file heur_lurkprune.c.

Referenced by SCIPStpIncludeHeurLurkPrune().

◆ LURKPRUNE_NTMRUNS

#define LURKPRUNE_NTMRUNS 30

TM heur runs

Definition at line 58 of file heur_lurkprune.c.

Referenced by updateSolution().

◆ LURKPRUNE_MINREDELIMS

#define LURKPRUNE_MINREDELIMS 10

minimum number of eliminations for reduction package when called by lurk-and-prune heuristic

Definition at line 59 of file heur_lurkprune.c.

Referenced by reduceExact().

◆ LURKPRUNE_MAXREDROUNDS

#define LURKPRUNE_MAXREDROUNDS 10

maximum number of reduction rounds in lurk-prune heuristic

Definition at line 60 of file heur_lurkprune.c.

Referenced by SCIPStpHeurLurkPruneRun().

◆ LURKPRUNE_MINLURKEDGE_RATIO

#define LURKPRUNE_MINLURKEDGE_RATIO 0.05

Definition at line 61 of file heur_lurkprune.c.

Referenced by lurkpruneInit().

◆ LURKPRUNE_MINSTALLPROPORTION

#define LURKPRUNE_MINSTALLPROPORTION 0.25

minimum proportion of arcs to be fixed before restarting lurk-prune heuristic

Definition at line 62 of file heur_lurkprune.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ LURKPRUNE_MAXSTALLPROPORTION

#define LURKPRUNE_MAXSTALLPROPORTION 0.5

maximum proportion of arcs to be fixed before restarting lurk-prune heuristic

Definition at line 63 of file heur_lurkprune.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ LURK_MAXTOTNEDGES

#define LURK_MAXTOTNEDGES 5000

Definition at line 64 of file heur_lurkprune.c.

Referenced by SCIP_DECL_HEUREXEC().

Typedef Documentation

◆ LURKPRUNE

typedef struct lurking_prune LURKPRUNE

data

Function Documentation

◆ prunegraphInit()

static SCIP_RETCODE prunegraphInit	(	SCIP *	scip,
		const GRAPH *	g,
		GRAPH **	prunegraph
	)

static

initializes prune graph

Parameters

scip	SCIP data structure
g	graph
prunegraph	graph

Definition at line 103 of file heur_lurkprune.c.

References graph_copy(), graph_initHistory(), graph_mark(), graph_path_init(), graph_pc_isPcMw(), SCIP_CALL, and SCIP_OKAY.

Referenced by lurkpruneInit().

◆ lurkpruneInit()

static SCIP_RETCODE lurkpruneInit	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	lurkingbounds,
		int *	soledge,
		LURKPRUNE *	lurkprune,
		GRAPH **	prunegraph
	)

static

initializes

Parameters

scip	SCIP data structure
g	graph
lurkingbounds	lurking edge bounds
soledge	array to 1. provide and 2. return primal solution
lurkprune	lurking-prune data
prunegraph	graph

Definition at line 122 of file heur_lurkprune.c.

References BMScopyMemoryArray, CONNECT, EQ, FARAWAY, GE, lurking_prune::globalobj, lurking_prune::globalsoledge, graph_get_nEdges(), graph_get_nNodes(), graph_get_nVET(), graph_printInfoReduced(), GRAPH::head, lurking_prune::lurkingbounds_half, LURKPRUNE_MINLURKEDGE_RATIO, lurking_prune::minlurkelims, nnodes, NULL, lurking_prune::obj_old, lurking_prune::offsetnew, prunegraphInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, lurking_prune::soledge, lurking_prune::solnode, solstp_getObj(), solstp_getObjBounded(), GRAPH::tail, lurking_prune::ubbest, and UNKNOWN.

Referenced by SCIPStpHeurLurkPruneRun().

◆ lurkpruneFinalize()

static void lurkpruneFinalize	(	SCIP *	scip,
		const GRAPH *	g,
		GRAPH *	prunegraph,
		int *	soledge,
		LURKPRUNE *	lurkprune,
		SCIP_Bool *	solimproved
	)

static

finalizes

Parameters

scip	SCIP data structure
g	graph
prunegraph	graph
soledge	array to 1. provide and 2. return primal solution
lurkprune	lurking-prune data
solimproved	could a better solution be found?

Definition at line 192 of file heur_lurkprune.c.

References BMScopyMemoryArray, lurking_prune::globalsoledge, graph_free(), graph_get_nEdges(), graph_path_exit(), LT, lurking_prune::lurkingbounds_half, lurking_prune::obj_old, SCIP_Real, SCIPdebugMessage, SCIPfreeBufferArray, lurking_prune::solnode, solstp_getObj(), and TRUE.

Referenced by SCIPStpHeurLurkPruneRun().

◆ reduceExact()

static SCIP_RETCODE reduceExact	(	SCIP *	scip,
		LURKPRUNE *	lurkprune,
		GRAPH *	prunegraph
	)

static

does exact reductions

Parameters

scip	SCIP data structure
lurkprune	lurking-prune data
prunegraph	graph data structure

Definition at line 220 of file heur_lurkprune.c.

References reduction_parameters::dualascent, FALSE, graph_get_nEdges(), graph_get_nNodes(), graph_pc_isMw(), graph_pc_isPc(), LURKPRUNE_MINREDELIMS, nnodes, NULL, lurking_prune::offsetnew, reduction_base::redparameters, reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), reduce_solFree(), reduce_solGetOffset(), reduce_solInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by SCIPStpHeurLurkPruneRun().

◆ reduceLurk()

static SCIP_RETCODE reduceLurk	(	SCIP *	scip,
		LURKPRUNE *	lurkprune,
		GRAPH *	prunegraph,
		SCIP_Bool *	success
	)

static

does heuristic reductions

Parameters

scip	SCIP data structure
lurkprune	lurking-prune data
prunegraph	graph data structure
success	could enough edges be removed?

Definition at line 300 of file heur_lurkprune.c.

References GRAPH::ancestors, bound, CONNECT, FALSE, flipedge, graph_edge_del(), graph_edge_isDeleted(), graph_edge_isInRange(), graph_get_nEdges(), graph_pc_edgeIsExtended(), graph_pc_isPcMw(), graph_printInfoReduced(), graph_valid(), lurking_prune::lurkingbounds_half, lurking_prune::minlurkelims, NULL, reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPsortDownRealInt(), lurking_prune::soledge, solstp_isValid(), and TRUE.

Referenced by SCIPStpHeurLurkPruneRun().

◆ reduceFixedVars()

static void reduceFixedVars	(	SCIP *	scip,
		SCIP_VAR **	vars,
		const int *	soledge,
		GRAPH *	prunegraph
	)

static

delete fixed edges

Parameters

scip	SCIP data structure
vars	problem variables or NULL
soledge	primal solution
prunegraph	graph data structure

Definition at line 403 of file heur_lurkprune.c.

References CONNECT, graph_edge_del(), graph_get_nEdges(), graph_pc_edgeIsExtended(), graph_pc_isPcMw(), SCIP_Bool, SCIPdebugMessage, SCIPvarGetUbLocal(), and TRUE.

Referenced by SCIPStpHeurLurkPruneRun().

◆ updateSolution()

static SCIP_RETCODE updateSolution	(	SCIP *	scip,
		GRAPH *	g,
		LURKPRUNE *	lurkprune,
		GRAPH *	prunegraph
	)

static

updates

Parameters

scip	SCIP data structure
g	graph data structure
lurkprune	lurking-prune data
prunegraph	graph data structure

Definition at line 434 of file heur_lurkprune.c.

References reduce_cost_parameters::addcuts, GRAPH::cost, dualascent_exec(), GRAPH::edges, FALSE, lurking_prune::globalobj, lurking_prune::globalsoledge, graph_pc_isRootedPcMw(), graph_typeIsSpgLike(), GRAPH::knots, LT, LURKPRUNE_NTMRUNS, NULL, lurking_prune::offsetnew, pcmode_fromheurdata, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), lurking_prune::soledge, lurking_prune::solnode, solstp_getObj(), solstp_isValid(), GRAPH::source, TRUE, and lurking_prune::ubbest.

Referenced by SCIPStpHeurLurkPruneRun().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyLurkPrune )

static

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

Definition at line 507 of file heur_lurkprune.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeLurkPrune )

static

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

Definition at line 521 of file heur_lurkprune.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitLurkPrune )

static

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

Definition at line 543 of file heur_lurkprune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolLurkPrune )

static

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

Definition at line 553 of file heur_lurkprune.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolLurkPrune )

static

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

Definition at line 574 of file heur_lurkprune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecLurkPrune )

static

execution method of primal heuristic

Definition at line 584 of file heur_lurkprune.c.

References CONNECT, GRAPH::cost, GRAPH::edges, EQ, FALSE, graph_pc_isPcMw(), graph_typeIsSpgLike(), HEUR_NAME, LURK_MAXTOTNEDGES, LURKPRUNE_MAXSTALLPROPORTION, LURKPRUNE_MINSTALLPROPORTION, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetProbData(), SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPheurGetName(), SCIPisGT(), SCIPisLT(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph(), SCIPprobdataGetNVars(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPStpHeurLurkPruneRun(), SCIPStpNfixedEdges(), solstp_isValid(), and UNKNOWN.

◆ SCIPStpHeurLurkPruneRun()

SCIP_RETCODE SCIPStpHeurLurkPruneRun	(	SCIP *	scip,
		SCIP_VAR **	vars,
		const SCIP_Real *	lurkingbounds,
		GRAPH *	g,
		SCIP_Bool	initialreduce,
		SCIP_Bool	ascendprune,
		int *	soledge,
		SCIP_Bool *	solimproved
	)

execute lurk-and-prune heuristic on given graph

Parameters

scip	SCIP data structure
vars	problem variables or NULL
lurkingbounds	lurking edge bounds
g	graph data structure
initialreduce	try to reduce graph initially?
ascendprune	use ascend-prune?
soledge	array to 1. provide and 2. return primal solution
solimproved	could a better solution be found?

Definition at line 731 of file heur_lurkprune.c.

References GRAPH::extended, FALSE, graph_pc_isPcMw(), LURKPRUNE_MAXREDROUNDS, lurkpruneFinalize(), lurkpruneInit(), NULL, reduceExact(), reduceFixedVars(), reduceLurk(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, solstp_isValid(), GRAPH::terms, and updateSolution().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIPStpIncludeHeurLurkPrune()

SCIP_RETCODE SCIPStpIncludeHeurLurkPrune ( SCIP * scip )

creates the lurkprune primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 792 of file heur_lurkprune.c.

References DEFAULT_LURKPRUNE_MAXFREQ, 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(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), and SCIPsetHeurInitsol().

Referenced by runShell(), SCIP_DECL_HEURCOPY(), and subscipSetupCallbacks().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ SCIP_DEBUG

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_LURKPRUNE_MAXFREQ

◆ LURKPRUNE_NTMRUNS

◆ LURKPRUNE_MINREDELIMS

◆ LURKPRUNE_MAXREDROUNDS

◆ LURKPRUNE_MINLURKEDGE_RATIO

◆ LURKPRUNE_MINSTALLPROPORTION

◆ LURKPRUNE_MAXSTALLPROPORTION

◆ LURK_MAXTOTNEDGES

Typedef Documentation

◆ LURKPRUNE

Function Documentation

◆ prunegraphInit()

◆ lurkpruneInit()

◆ lurkpruneFinalize()

◆ reduceExact()

◆ reduceLurk()

◆ reduceFixedVars()

◆ updateSolution()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurLurkPruneRun()

◆ SCIPStpIncludeHeurLurkPrune()