Detailed Description

reduction-based primal heuristic for Steiner problems

Author: Daniel Rehfeldt

This file implements a reduction and dual-cost based heuristic for Steiner problems. See "SCIP-Jack - A solver for STP and variants with parallelization extensions" (2016) by Gamrath, Koch, Maher, Rehfeldt and Shinano

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

Definition in file heur_ascendprune.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_ascendprune.h"
#include "heur_local.h"
#include "heur_prune.h"
#include "graph.h"
#include "reduce.h"
#include "heur_tm.h"
#include "solstp.h"
#include "solpool.h"
#include "redcosts.h"
#include "cons_stp.h"
#include "probdata_stp.h"

Go to the source code of this file.

Data Structures
struct	redcost0_graph

Macros
#define	HEUR_NAME "ascendprune"

#define	HEUR_DESC "Dual-cost reduction heuristic for Steiner problems"

#define	HEUR_DISPCHAR 'A'

#define	HEUR_PRIORITY 2

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

#define	ASCENPRUNE_MINLPIMPROVE 0.2

Typedefs
typedef struct redcost0_graph	RCGRAPH

Functions
static int	redcostGetNTermsMarked (const GRAPH g, const RCGRAPH redcostgraph)

static SCIP_RETCODE	redcostGraphMark (SCIP scip, const GRAPH g, RCGRAPH *redcostgraph)

static SCIP_RETCODE	redcostGraphBuild (SCIP scip, const GRAPH g, RCGRAPH *redcostgraph)

static void	redcostGraphFree (SCIP scip, RCGRAPH redcostgraph)

static SCIP_RETCODE	redcostGraphSolRetransform (SCIP scip, const GRAPH g, const RCGRAPH redcostgraph, const int subresult, int *result)

static SCIP_RETCODE	redcostGraphComputeSteinerTree (SCIP scip, const GRAPH g, RCGRAPH redcostgraph, int result)

static SCIP_RETCODE	redcostGraphComputeSteinerTreeDirected (SCIP scip, const GRAPH g, RCGRAPH redcostgraph, int result, SCIP_Bool *solfound)

static SCIP_RETCODE	redcostGraphComputeSteinerTreeDegCons (SCIP scip, const GRAPH g, RCGRAPH redcostgraph, int result, SCIP_Bool *solfound)

static	SCIP_DECL_HEURCOPY (heurCopyAscendPrune)

static	SCIP_DECL_HEURFREE (heurFreeAscendPrune)

static	SCIP_DECL_HEURINIT (heurInitAscendPrune)

static	SCIP_DECL_HEUREXEC (heurExecAscendPrune)

SCIP_RETCODE	SCIPStpHeurAscendPruneRun (SCIP scip, SCIP_HEUR heur, const GRAPH g, const SCIP_Real redcosts, int result, int root, SCIP_Bool solfound, SCIP_Bool addsol)

SCIP_RETCODE	SCIPStpIncludeHeurAscendPrune (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "ascendprune"

Definition at line 49 of file heur_ascendprune.c.

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

◆ HEUR_DESC

#define HEUR_DESC "Dual-cost reduction heuristic for Steiner problems"

Definition at line 50 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'A'

Definition at line 51 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 2

Definition at line 52 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_FREQ

#define HEUR_FREQ -1

Definition at line 53 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 54 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 55 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_TIMING

#define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)

Definition at line 56 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 57 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ DEFAULT_MAXFREQPRUNE

#define DEFAULT_MAXFREQPRUNE FALSE

executions of the heuristic at maximum frequency?

Definition at line 59 of file heur_ascendprune.c.

Referenced by SCIPStpIncludeHeurAscendPrune().

◆ ASCENPRUNE_MINLPIMPROVE

#define ASCENPRUNE_MINLPIMPROVE 0.2

minimum percentual improvement of dual bound (wrt to gap) mandatory to execute heuristic

Definition at line 60 of file heur_ascendprune.c.

Referenced by SCIP_DECL_HEUREXEC().

Typedef Documentation

◆ RCGRAPH

typedef struct redcost0_graph RCGRAPH

subgraph data

Function Documentation

◆ redcostGetNTermsMarked()

static int redcostGetNTermsMarked	(	const GRAPH *	g,
		const RCGRAPH *	redcostgraph
	)

static

gets number of terms that are marked

Parameters

g	the graph
redcostgraph	reduced cost graph data

Definition at line 189 of file heur_ascendprune.c.

References graph_get_nNodes(), Is_term, GRAPH::mark, nnodes, nterms, and GRAPH::term.

Referenced by redcostGraphMark().

◆ redcostGraphMark()

static SCIP_RETCODE redcostGraphMark	(	SCIP *	scip,
		const GRAPH *	g,
		RCGRAPH *	redcostgraph
	)

static

marks part of graph corresponding to zero cost paths from the root to all terminals

Parameters

scip	SCIP data structure
g	the graph
redcostgraph	reduced cost graph data structure

Definition at line 210 of file heur_ascendprune.c.

References a, BMSclearMemoryArray, EAT_LAST, redcost0_graph::edgelist, flipedge, graph_get_nEdges(), graph_get_nNodes(), graph_knot_isInRange(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_printInfoReduced(), graph_typeIsUndirected(), GRAPH::head, GRAPH::mark, redcost0_graph::nedges_half, nnodes, redcost0_graph::nnodes, GRAPH::oeat, GRAPH::outbeg, redcostGetNTermsMarked(), redcost0_graph::redcosts, redcost0_graph::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisZero(), GRAPH::source, GRAPH::tail, GRAPH::terms, and TRUE.

Referenced by SCIPStpHeurAscendPruneRun().

◆ redcostGraphBuild()

static SCIP_RETCODE redcostGraphBuild	(	SCIP *	scip,
		const GRAPH *	g,
		RCGRAPH *	redcostgraph
	)

static

builds graphs

Parameters

scip	SCIP data structure
g	the graph
redcostgraph	reduced cost graph data structure

Definition at line 342 of file heur_ascendprune.c.

References a, EAT_LAST, redcost0_graph::edgelist, redcost0_graph::edgeNew2OrgMap, GRAPH::edges, GRAPH::extended, FARAWAY, flipedge, graph_edge_addSubgraph(), graph_get_nNodes(), graph_init(), graph_initHistory(), graph_knot_add(), graph_knot_isInRange(), graph_pc_finalizeSubgraph(), graph_pc_initSubgraph(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_typeIsSpgLike(), graph_valid(), GRAPH::head, GRAPH::hoplimit, GRAPH::knots, GRAPH::mark, GRAPH::maxdeg, redcost0_graph::nedges_half, redcost0_graph::newgraph, nnodes, redcost0_graph::nnodes, redcost0_graph::nodeOrg2NewMap, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, redcost0_graph::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, GRAPH::source, STP_DCSTP, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, TERM2EDGE_FIXEDTERM, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurAscendPruneRun().

◆ redcostGraphFree()

static void redcostGraphFree	(	SCIP *	scip,
		RCGRAPH *	redcostgraph
	)

static

frees members

Parameters

scip	SCIP data structure
redcostgraph	reduced cost graph data structure

Definition at line 496 of file heur_ascendprune.c.

References redcost0_graph::edgelist, redcost0_graph::edgeNew2OrgMap, graph_free(), redcost0_graph::newgraph, redcost0_graph::nodeOrg2NewMap, SCIPfreeBufferArrayNull, and TRUE.

Referenced by SCIPStpHeurAscendPruneRun().

◆ redcostGraphSolRetransform()

static SCIP_RETCODE redcostGraphSolRetransform	(	SCIP *	scip,
		const GRAPH *	g,
		const RCGRAPH *	redcostgraph,
		const int *	subresult,
		int *	result
	)

static

retransforms solution on subgraph

Parameters

scip	SCIP data structure
g	the graph
redcostgraph	reduced cost graph data structure
subresult	solution for new graph, can also be NULL
result	solution for original graph; for STP like also keeps sub-solution

Definition at line 513 of file heur_ascendprune.c.

References BMSclearMemoryArray, CONNECT, redcost0_graph::edgeNew2OrgMap, graph_edge_isInRange(), graph_get_nEdges(), graph_get_nNodes(), graph_typeIsDirected(), GRAPH::head, GRAPH::knots, redcost0_graph::newgraph, nnodes, redcost0_graph::root, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, solstp_getObj(), solstp_isValid(), solstp_prune(), solstp_reroot(), GRAPH::source, STP_DCSTP, GRAPH::stp_type, GRAPH::tail, TRUE, and UNKNOWN.

Referenced by redcostGraphComputeSteinerTree(), redcostGraphComputeSteinerTreeDegCons(), and redcostGraphComputeSteinerTreeDirected().

◆ redcostGraphComputeSteinerTree()

static SCIP_RETCODE redcostGraphComputeSteinerTree	(	SCIP *	scip,
		const GRAPH *	g,
		RCGRAPH *	redcostgraph,
		int *	result
	)

static

builds Steiner tree on subgraph

Parameters

scip	SCIP data structure
g	the graph
redcostgraph	reduced cost graph data structure
result	solution array

Definition at line 595 of file heur_ascendprune.c.

References GRAPH::edges, FALSE, GRAPH::grad, graph_path_exit(), graph_path_init(), graph_valid(), Is_term, GRAPH::knots, redcost0_graph::newgraph, NULL, redcostGraphSolRetransform(), reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), solstp_getObjBounded(), solstp_isValid(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by SCIPStpHeurAscendPruneRun().

◆ redcostGraphComputeSteinerTreeDirected()

static SCIP_RETCODE redcostGraphComputeSteinerTreeDirected	(	SCIP *	scip,
		const GRAPH *	g,
		RCGRAPH *	redcostgraph,
		int *	result,
		SCIP_Bool *	solfound
	)

static

builds Steiner tree on directed subgraph

Parameters

scip	SCIP data structure
g	the graph
redcostgraph	reduced cost graph data structure
result	solution array
solfound	has a solution been found?

Definition at line 643 of file heur_ascendprune.c.

References FALSE, graph_get_nEdges(), graph_get_nNodes(), graph_getEdgeCosts(), graph_path_exit(), graph_path_init(), graph_valid(), redcost0_graph::newgraph, NULL, pcmode_fromheurdata, redcostGraphSolRetransform(), reduce_unconnectedForDirected(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), solstp_getObj(), solstp_isValid(), GRAPH::source, STP_DHCSTP, STP_NWPTSPG, GRAPH::stp_type, and TRUE.

Referenced by SCIPStpHeurAscendPruneRun().

◆ redcostGraphComputeSteinerTreeDegCons()

static SCIP_RETCODE redcostGraphComputeSteinerTreeDegCons	(	SCIP *	scip,
		const GRAPH *	g,
		RCGRAPH *	redcostgraph,
		int *	result,
		SCIP_Bool *	solfound
	)

static

builds Steiner tree for DCSTP

Parameters

scip	SCIP data structure
g	the graph
redcostgraph	reduced cost graph data structure
result	solution array
solfound	has a solution been found?

Definition at line 719 of file heur_ascendprune.c.

References FALSE, graph_get_nEdges(), graph_getEdgeCosts(), graph_path_exit(), graph_path_init(), graph_valid(), redcost0_graph::newgraph, NULL, pcmode_fromheurdata, redcostGraphSolRetransform(), reduce_unconnected(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPStpHeurTMRun(), solstp_getObj(), solstp_isValid(), GRAPH::source, STP_DCSTP, GRAPH::stp_type, and TRUE.

Referenced by SCIPStpHeurAscendPruneRun().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyAscendPrune )

static

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

Definition at line 786 of file heur_ascendprune.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeAscendPrune )

static

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

Definition at line 800 of file heur_ascendprune.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitAscendPrune )

static

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

Definition at line 822 of file heur_ascendprune.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecAscendPrune )

static

execution method of primal heuristic

Definition at line 844 of file heur_ascendprune.c.

References ASCENPRUNE_MINLPIMPROVE, GRAPH::edges, FALSE, HEUR_NAME, NULL, redcosts_forLPareAvailable(), redcosts_forLPget(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetDualbound(), SCIPgetProbData(), SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPheurGetName(), SCIPisLT(), SCIPprobdataGetGraph(), SCIPprobdataGetVars(), SCIPsolGetIndex(), SCIPStpHeurAscendPruneRun(), GRAPH::source, and TRUE.

◆ SCIPStpHeurAscendPruneRun()

SCIP_RETCODE SCIPStpHeurAscendPruneRun	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		const GRAPH *	g,
		const SCIP_Real *	redcosts,
		int *	result,
		int	root,
		SCIP_Bool *	solfound,
		SCIP_Bool	addsol
	)

ascent and prune

Parameters

scip	SCIP data structure
heur	heuristic data structure or NULL
g	the graph
redcosts	the reduced costs
result	int edges array to store solution
root	the root (used for dual ascent)
solfound	has a solution been found? And added, if requested?
addsol	should the solution be added to SCIP by this method?

Definition at line 940 of file heur_ascendprune.c.

References GRAPH::extended, graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_printInfo(), graph_typeIsUndirected(), graph_valid(), Is_term, redcost0_graph::nedges_half, redcost0_graph::newgraph, NULL, redcostGraphBuild(), redcostGraphComputeSteinerTree(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), redcostGraphFree(), redcostGraphMark(), redcost0_graph::root, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, solpool_addSolToScip(), solstp_getObj(), solstp_getTrivialSol(), solstp_isValid(), GRAPH::source, STP_DCSTP, STP_RMWCSP, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsDirected(), computeSteinerTreeRedCostsPcMw(), daExec(), dualascent_execPcMw(), reduce_daSlackPrune(), SCIP_DECL_HEUREXEC(), termcompComputeSubgraphSol(), and updateSolution().

◆ SCIPStpIncludeHeurAscendPrune()

SCIP_RETCODE SCIPStpIncludeHeurAscendPrune ( SCIP * scip )

creates the prune primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1015 of file heur_ascendprune.c.

References DEFAULT_MAXFREQPRUNE, 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(), SCIPsetHeurFree(), and SCIPsetHeurInit().

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

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXFREQPRUNE

◆ ASCENPRUNE_MINLPIMPROVE

Typedef Documentation

◆ RCGRAPH

Function Documentation

◆ redcostGetNTermsMarked()

◆ redcostGraphMark()

◆ redcostGraphBuild()

◆ redcostGraphFree()

◆ redcostGraphSolRetransform()

◆ redcostGraphComputeSteinerTree()

◆ redcostGraphComputeSteinerTreeDirected()

◆ redcostGraphComputeSteinerTreeDegCons()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurAscendPruneRun()

◆ SCIPStpIncludeHeurAscendPrune()