Detailed Description

Dual-ascent dual heuristic for Steiner problems.

Author: Daniel Rehfeldt

This file includes dual-ascent for classic Steiner tree and some variants.

Definition in file dualascent.c.

#include <assert.h>
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "dualascent.h"
#include "probdata_stp.h"
#include "graph.h"
#include "heur_ascendprune.h"
#include "scip/scip.h"
#include "scip/misc.h"

Go to the source code of this file.

Data Structures
struct	dual_ascent_paths

Macros
#define	DEFAULT_DAMAXDEVIATION 0.25

#define	DA_MAXDEVIATION_LOWER 0.01

#define	DA_MAXDEVIATION_UPPER 0.9

#define	DA_EPS (5e-7)

#define	DAPATHS_HITLIMIT_PCMW 20

#define	DAPATHS_HITLIMIT 5

#define	DFS

Typedefs
typedef struct dual_ascent_paths	DAPATHS

Enumerations
enum	DACONS_Type { dacons_linear = 0, dacons_logicor = 1, dacons_setppc = 2 }

Functions
Local methods
static SCIP_RETCODE	daconsCreateEmpty (SCIP scip, enum DACONS_Type constype, SCIP_Bool consUseInital, SCIP_CONS *cons)

static SCIP_RETCODE	daconsGetParams (SCIP scip, enum DACONS_Type constype, SCIP_Bool *consUseInital)

static SCIP_RETCODE	dapathsSortStarts (SCIP scip, const GRAPH graph, const int result, DAPATHS dapaths)

static void	dapathsSetRunParams (const GRAPH graph, DAPATHS dapaths)

static SCIP_RETCODE	dapathsInit (SCIP scip, const GRAPH graph, DAPATHS *dapaths)

static void	dapathsInitRedCosts (const GRAPH graph, SCIP_Real RESTRICT redcost, SCIP_Real *objval)

static void	dapathsUpdate (const GRAPH g, const DAPATHS dapaths, SCIP_Real RESTRICT redcost, SCIP_Real objval)

static void	dapathsRunShortestPaths (const GRAPH graph, DAPATHS dapaths, SCIP_Real RESTRICT redcost, SCIP_Real objval)

static void	dapathsFreeMembers (SCIP scip, DAPATHS dapaths)

static SCIP_Bool	daNodeIsActive (const int *active, int realtail, int dfsbase)

static void	daInitRescaps (const GRAPH g, const int edgemap, int ncsredges, SCIP_Real RESTRICT rescap, SCIP_Real dualobj)

static SCIP_RETCODE	daUpdateRescaps (SCIP scip, const GRAPH g, const int edgemap, int ncsredges, SCIP_Real rescap)

static SCIP_RETCODE	daInit (SCIP scip, const GRAPH g, int root, SCIP_Bool is_pseudoroot, int gmark, int RESTRICT active, SCIP_PQUEUE pqueue, GNODE gnodearr, int *augmentingcomponent)

static SCIP_RETCODE	daExec (SCIP scip, const GRAPH g, const int result, const DAPARAMS daparams, SCIP_Bool updateRescaps, SCIP_Real RESTRICT rescap, SCIP_Real objval)

Interface methods
SCIP_RETCODE	dualascent_exec (SCIP scip, const GRAPH g, const int result, const DAPARAMS daparams, SCIP_Real RESTRICT redcost, SCIP_Real objval)

SCIP_RETCODE	dualascent_update (SCIP scip, const GRAPH g, const int result, const DAPARAMS daparams, SCIP_Real RESTRICT redcost, SCIP_Real objval)

SCIP_RETCODE	dualascent_execDegCons (SCIP scip, const GRAPH g, const int result, const DAPARAMS daparams, SCIP_Real RESTRICT redcost, SCIP_Real objval)

SCIP_RETCODE	dualascent_execPcMw (SCIP scip, GRAPH g, SCIP_Real redcost, SCIP_Real objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, int nruns)

SCIP_RETCODE	dualascent_pathsPcMw (SCIP scip, const GRAPH transgraph, SCIP_Real RESTRICT redcost, SCIP_Real objval, const int *result)

SCIP_RETCODE	dualascent_paths (SCIP scip, GRAPH graph, SCIP_Real RESTRICT redcost, SCIP_Real objval, const int *result)

SCIP_Bool	dualascent_allTermsReachable (SCIP scip, const GRAPH g, int root, const SCIP_Real *redcost)

Macro Definition Documentation

◆ DEFAULT_DAMAXDEVIATION

#define DEFAULT_DAMAXDEVIATION 0.25

max deviation for dual ascent

Definition at line 39 of file dualascent.c.

Referenced by daExec(), and dualascent_execPcMw().

◆ DA_MAXDEVIATION_LOWER

#define DA_MAXDEVIATION_LOWER 0.01

lower bound for max deviation for dual ascent

Definition at line 40 of file dualascent.c.

Referenced by daExec().

◆ DA_MAXDEVIATION_UPPER

#define DA_MAXDEVIATION_UPPER 0.9

upper bound for max deviation for dual ascent

Definition at line 41 of file dualascent.c.

Referenced by daExec().

◆ DA_EPS

#define DA_EPS (5e-7)

Definition at line 42 of file dualascent.c.

Referenced by daExec().

◆ DAPATHS_HITLIMIT_PCMW

#define DAPATHS_HITLIMIT_PCMW 20

Definition at line 43 of file dualascent.c.

Referenced by dapathsUpdate().

◆ DAPATHS_HITLIMIT

#define DAPATHS_HITLIMIT 5

Definition at line 44 of file dualascent.c.

Referenced by dapathsUpdate().

◆ DFS

#define DFS

Definition at line 47 of file dualascent.c.

Typedef Documentation

◆ DAPATHS

typedef struct dual_ascent_paths DAPATHS

internal data for path based dual-ascent

Enumeration Type Documentation

◆ DACONS_Type

enum DACONS_Type

Enumerator
dacons_linear
dacons_logicor
dacons_setppc

Definition at line 57 of file dualascent.c.

Function Documentation

◆ daconsCreateEmpty()

static SCIP_RETCODE daconsCreateEmpty	(	SCIP *	scip,
		enum DACONS_Type	constype,
		SCIP_Bool	consUseInital,
		SCIP_CONS **	cons
	)

static

creates empty constraint

Parameters

scip	SCIP data structure
constype	constraint type to be used
consUseInital	use dual-ascent cuts as initial constraints?
cons	to be initialized

Definition at line 81 of file dualascent.c.

References dacons_linear, dacons_logicor, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateConsLinear(), SCIPcreateConsLogicor(), SCIPcreateConsSetcover(), SCIPinfinity(), and TRUE.

Referenced by daExec(), and dualascent_execPcMw().

◆ daconsGetParams()

static SCIP_RETCODE daconsGetParams	(	SCIP *	scip,
		enum DACONS_Type *	constype,
		SCIP_Bool *	consUseInital
	)

static

gets parameter

Parameters

scip	SCIP data structure
constype	pointer: constraint type to be used (OUT)
consUseInital	pointer: use dual-ascent cuts as initial constraints? (OUT)

Definition at line 112 of file dualascent.c.

References dacons_linear, dacons_logicor, dacons_setppc, SCIP_CALL, SCIP_OKAY, SCIPgetBoolParam(), and SCIPgetIntParam().

Referenced by daExec(), and dualascent_execPcMw().

◆ dapathsSortStarts()

static SCIP_RETCODE dapathsSortStarts	(	SCIP *	scip,
		const GRAPH *	graph,
		const int *	result,
		DAPATHS *	dapaths
	)

static

sorts according to distance in solution

Parameters

scip	SCIP data structure
graph	graph
result	solution array
dapaths	to be initialized

Definition at line 143 of file dualascent.c.

References a, BMSclearMemoryArray, CONNECT, GRAPH::cost, EAT_LAST, EQ, FARAWAY, graph_get_nNodes(), graph_knot_printInfo(), GRAPH::head, Is_term, nnodes, dual_ascent_paths::nstartnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownRealInt(), GRAPH::source, dual_ascent_paths::startnodes, GRAPH::term, and TRUE.

Referenced by dualascent_paths().

◆ dapathsSetRunParams()

static void dapathsSetRunParams	(	const GRAPH *	graph,
		DAPATHS *	dapaths
	)

static

sets shortest path parameters: start node and abort nodes

Parameters

graph	graph
dapaths	to be initialized

Definition at line 262 of file dualascent.c.

References BMSclearMemoryArray, dual_ascent_paths::centernode, GRAPH::cost, EAT_LAST, FARAWAY, GRAPH::grad, graph_get_nNodes(), GT, GRAPH::ieat, GRAPH::inpbeg, Is_term, dual_ascent_paths::isUnrootedPcMw, dual_ascent_paths::maxdist, nnodes, dual_ascent_paths::nodes_abort, dual_ascent_paths::nstartnodes, GRAPH::outbeg, SCIP_Bool, GRAPH::source, dual_ascent_paths::startnodes, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by dapathsInit().

◆ dapathsInit()

static SCIP_RETCODE dapathsInit	(	SCIP *	scip,
		const GRAPH *	graph,
		DAPATHS *	dapaths
	)

static

initializes

Parameters

scip	SCIP data structure
graph	graph
dapaths	to be initialized

Definition at line 318 of file dualascent.c.

References BMSclearMemoryArray, dapathsSetRunParams(), dual_ascent_paths::dijklimited, graph_dijkLimited_init(), graph_get_nNodes(), nnodes, dual_ascent_paths::nodes_abort, dual_ascent_paths::nodes_hits, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and dual_ascent_paths::startnodes.

Referenced by dualascent_paths(), and dualascent_pathsPcMw().

◆ dapathsInitRedCosts()

static void dapathsInitRedCosts	(	const GRAPH *	graph,
		SCIP_Real *RESTRICT	redcost,
		SCIP_Real *	objval
	)

static

initializes reduced costs

Parameters

graph	graph; possibly transformed SAP graph
redcost	array to store reduced costs
objval	pointer to store (dual) objective value

Definition at line 341 of file dualascent.c.

References BMScopyMemoryArray, GRAPH::cost, and graph_get_nEdges().

Referenced by dapathsRunShortestPaths().

◆ dapathsUpdate()

static void dapathsUpdate	(	const GRAPH *	g,
		const DAPATHS *	dapaths,
		SCIP_Real *RESTRICT	redcost,
		SCIP_Real *	objval
	)

static

updates reduced costs and hit count

Parameters

g	graph
dapaths	DA paths data
redcost	array to store reduced costs
objval	pointer to store (dual) objective value

Definition at line 356 of file dualascent.c.

References DAPATHS_HITLIMIT, DAPATHS_HITLIMIT_PCMW, dual_ascent_paths::dijklimited, EPSILON, GE, graph_knot_isInRange(), GRAPH::head, dual_ascent_paths::isUnrootedPcMw, LE_FEAS_EPS, LT, MAX, dual_ascent_paths::maxdist, dijkstra_data::node_distance, dual_ascent_paths::nodes_abort, dual_ascent_paths::nodes_hits, dijkstra_data::nvisits, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, TRUE, and dijkstra_data::visitlist.

Referenced by dapathsRunShortestPaths().

◆ dapathsRunShortestPaths()

static void dapathsRunShortestPaths	(	const GRAPH *	graph,
		DAPATHS *	dapaths,
		SCIP_Real *RESTRICT	redcost,
		SCIP_Real *	objval
	)

static

runs

Parameters

graph	graph; possibly transformed SAP graph
dapaths	to be initialized
redcost	array to store reduced costs
objval	objective

Definition at line 417 of file dualascent.c.

References BMSclearMemoryArray, dual_ascent_paths::centernode, dapathsInitRedCosts(), dapathsUpdate(), dual_ascent_paths::dijklimited, graph_dijkLimited_reset(), graph_knot_isInRange(), graph_pathInLimitedExec(), Is_term, dual_ascent_paths::isUnrootedPcMw, GRAPH::knots, dual_ascent_paths::maxdist, dual_ascent_paths::nodes_abort, dual_ascent_paths::nstartnodes, SCIP_Bool, GRAPH::source, dual_ascent_paths::startnodes, GRAPH::term, and TRUE.

Referenced by dualascent_paths(), and dualascent_pathsPcMw().

◆ dapathsFreeMembers()

static void dapathsFreeMembers	(	SCIP *	scip,
		DAPATHS *	dapaths
	)

static

frees

Parameters

scip	SCIP data structure
dapaths	to be initialized

Definition at line 458 of file dualascent.c.

References dual_ascent_paths::dijklimited, graph_dijkLimited_free(), dual_ascent_paths::nodes_abort, dual_ascent_paths::nodes_hits, SCIPfreeBufferArray, and dual_ascent_paths::startnodes.

Referenced by dualascent_paths(), and dualascent_pathsPcMw().

◆ daNodeIsActive()

static SCIP_Bool daNodeIsActive	(	const int *	active,
		int	realtail,
		int	dfsbase
	)

inlinestatic

returns whether node realtail is active or leads to active node other than dfsbase

Parameters

active	active nodes array
realtail	vertex to start from
dfsbase	DFS source vertex

Definition at line 472 of file dualascent.c.

Referenced by daExec().

◆ daInitRescaps()

static void daInitRescaps	(	const GRAPH *	g,
		const int *	edgemap,
		int	ncsredges,
		SCIP_Real *RESTRICT	rescap,
		SCIP_Real *	dualobj
	)

static

initializes

Parameters

g	graph data structure
edgemap	CSR ancestor edge array
ncsredges	number of CSR edges
rescap	residual capacity
dualobj	dual objective

Definition at line 491 of file dualascent.c.

References GRAPH::cost.

Referenced by daExec().

◆ daUpdateRescaps()

static SCIP_RETCODE daUpdateRescaps	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	edgemap,
		int	ncsredges,
		SCIP_Real *	rescap
	)

static

updates

Parameters

scip	SCIP
g	graph data structure
edgemap	CSR ancestor edge array
ncsredges	number of CSR edges
rescap	residual capacity

Definition at line 508 of file dualascent.c.

References BMScopyMemoryArray, graph_edge_isInRange(), graph_get_nEdges(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by daExec().

◆ daInit()

static SCIP_RETCODE daInit	(	SCIP *	scip,
		const GRAPH *	g,
		int	root,
		SCIP_Bool	is_pseudoroot,
		int *	gmark,
		int *RESTRICT	active,
		SCIP_PQUEUE *	pqueue,
		GNODE *	gnodearr,
		int *	augmentingcomponent
	)

static

initializes

Parameters

scip	SCIP
g	graph data structure
root	the root
is_pseudoroot	is the root a pseudo root?
gmark	array for marking nodes
active	active vertices mark
pqueue	priority queue
gnodearr	array containing terminal nodes
augmentingcomponent	augmenting component

Definition at line 538 of file dualascent.c.

References a, GRAPH::cost, Graph_Node::dist, EAT_LAST, FALSE, GRAPH::grad, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, Graph_Node::number, SCIP_CALL, SCIP_OKAY, SCIPisZero(), SCIPpqueueInsert(), GRAPH::tail, and GRAPH::term.

Referenced by daExec().

◆ daExec()

static SCIP_RETCODE daExec	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	result,
		const DAPARAMS *	daparams,
		SCIP_Bool	updateRescaps,
		SCIP_Real *RESTRICT	rescap,
		SCIP_Real *	objval
	)

static

dual ascent heuristic

Parameters

scip	SCIP data structure
g	graph data structure
result	solution array or NULL
daparams	parameter
updateRescaps	update?
rescap	residual capacities aka reduced costs
objval	pointer to store objective value

Definition at line 623 of file dualascent.c.

References a, active, reduce_cost_parameters::addcuts, reduce_cost_parameters::ascendandprune, CONNECT, GRAPH::cost, DA_EPS, DA_MAXDEVIATION_LOWER, DA_MAXDEVIATION_UPPER, dacons_linear, dacons_logicor, daconsCreateEmpty(), daconsGetParams(), daInit(), daInitRescaps(), reduce_cost_parameters::damaxdeviation, daNodeIsActive(), daUpdateRescaps(), DEFAULT_DAMAXDEVIATION, Graph_Node::dist, dualascent_allTermsReachable(), GRAPH::edges, EQ, FALSE, FARAWAY, GNODECmpByDist(), GRAPH::grad, graph_getCsr(), graph_typeIsDirected(), reduce_cost_parameters::is_pseudoroot, Is_term, GRAPH::knots, LT, nnodes, nterms, NULL, Graph_Node::number, reduce_cost_parameters::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIPaddCoefLinear(), SCIPaddCoefLogicor(), SCIPaddCoefSetppc(), SCIPaddCons(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMessage, SCIPfindConshdlr(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, SCIPgetStage(), SCIPinfinity(), SCIPisGE(), SCIPisLT(), SCIPisStopped(), SCIPisZero(), SCIPpqueueCreate(), SCIPpqueueFirst(), SCIPpqueueFree(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPpqueueRemove(), SCIPprobdataGetVars(), SCIPreleaseCons(), SCIPreleaseRow(), SCIPStpHeurAscendPruneRun(), GRAPH::source, STP_DCSTP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by dualascent_exec(), dualascent_execDegCons(), and dualascent_update().

◆ dualascent_exec()

SCIP_RETCODE dualascent_exec	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	result,
		const DAPARAMS *	daparams,
		SCIP_Real *RESTRICT	redcost,
		SCIP_Real *	objval
	)

dual ascent heuristic

Parameters

scip	SCIP data structure
g	graph data structure
result	solution array or NULL
daparams	parameter
redcost	array to store reduced costs or NULL
objval	pointer to store objective value

Definition at line 1191 of file dualascent.c.

References daExec(), GRAPH::edges, FALSE, GRAPH::knots, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by computeDualSolution(), computeDualSolutionGuided(), computePertubedSol(), createInitialCuts(), reduce_daPcMw(), reduce_daSlackPrune(), runDualAscent(), termcompComputeSubgraphSol(), termcompReduceWithParams(), and updateSolution().

◆ dualascent_update()

SCIP_RETCODE dualascent_update	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	result,
		const DAPARAMS *	daparams,
		SCIP_Real *RESTRICT	redcost,
		SCIP_Real *	objval
	)

updates reduced costs with dual ascent heuristic

Parameters

scip	SCIP data structure
g	graph data structure
result	solution array or NULL
daparams	parameter
redcost	array to store reduced costs
objval	pointer to store objective value

Definition at line 1225 of file dualascent.c.

References daExec(), dualascent_allTermsReachable(), GE, GRAPH::knots, reduce_cost_parameters::root, SCIP_CALL, SCIP_OKAY, and TRUE.

◆ dualascent_execDegCons()

SCIP_RETCODE dualascent_execDegCons	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	result,
		const DAPARAMS *	daparams,
		SCIP_Real *RESTRICT	redcost,
		SCIP_Real *	objval
	)

dual ascent heuristic for degree constrained problem

Parameters

scip	SCIP data structure
g	graph data structure
result	solution array or NULL
daparams	parameter
redcost	array to store reduced costs or NULL
objval	pointer to store objective value

Definition at line 1256 of file dualascent.c.

References reduce_cost_parameters::addcuts, BMScopyMemoryArray, GRAPH::cost, daExec(), EAT_LAST, FALSE, FARAWAY, graph_get_nEdges(), graph_get_nNodes(), graph_knot_isInRange(), Is_term, GRAPH::maxdeg, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_cost_parameters::root, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, STP_DCSTP, GRAPH::stp_type, and GRAPH::term.

Referenced by computeDualSolution(), computeDualSolutionGuided(), and createInitialCuts().

◆ dualascent_execPcMw()

SCIP_RETCODE dualascent_execPcMw	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	redcost,
		SCIP_Real *	objval,
		SCIP_Bool	addcuts,
		SCIP_Bool	ascendandprune,
		int	nruns
	)

dual ascent heuristic for PCSPG and MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
redcost	array to store reduced costs or NULL
objval	pointer to store objective value
addcuts	should dual-ascent add Steiner cuts?
ascendandprune	perform ascend-and-prune and add solution?
nruns	number of dual ascent runs

Definition at line 1319 of file dualascent.c.

References a, active, GRAPH::cost, dacons_linear, dacons_logicor, daconsCreateEmpty(), daconsGetParams(), DEFAULT_DAMAXDEVIATION, Graph_Node::dist, dualascent_allTermsReachable(), EAT_LAST, GRAPH::edges, FALSE, FARAWAY, GNODECmpByDist(), GRAPH::grad, graph_free(), graph_transPcGetSap(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, Graph_Node::number, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIPaddCoefLinear(), SCIPaddCoefLogicor(), SCIPaddCoefSetppc(), SCIPaddCons(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBuffer, SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMessage, SCIPfindConshdlr(), SCIPflushRowExtensions(), SCIPfreeBuffer, SCIPfreeBufferArray, SCIPgetStage(), SCIPinfinity(), SCIPisEQ(), SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPisStopped(), SCIPisZero(), SCIPpqueueCreate(), SCIPpqueueFree(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPpqueueRemove(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), SCIPreleaseCons(), SCIPreleaseRow(), SCIPStpHeurAscendPruneRun(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by createInitialCuts(), and runDualAscent().

◆ dualascent_pathsPcMw()

SCIP_RETCODE dualascent_pathsPcMw	(	SCIP *	scip,
		const GRAPH *	transgraph,
		SCIP_Real *RESTRICT	redcost,
		SCIP_Real *	objval,
		const int *	result
	)

path based dual ascent heuristic

Parameters

scip	SCIP data structure
transgraph	transformed SAP graph
redcost	array to store reduced costs
objval	pointer to store (dual) objective value
result	solution array or NULL

Definition at line 1780 of file dualascent.c.

References dapathsFreeMembers(), dapathsInit(), dapathsRunShortestPaths(), NULL, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by reduce_daPcMw(), and testDaPathsPcMw3EdgesWorks().

◆ dualascent_paths()

SCIP_RETCODE dualascent_paths	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Real *RESTRICT	redcost,
		SCIP_Real *	objval,
		const int *	result
	)

path based dual ascent heuristic

Parameters

scip	SCIP data structure
graph	graph
redcost	array to store reduced costs
objval	pointer to store (dual) objective value
result	solution array or NULL

Definition at line 1803 of file dualascent.c.

References dapathsFreeMembers(), dapathsInit(), dapathsRunShortestPaths(), dapathsSortStarts(), FALSE, graph_pc_2transcheck(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_dapaths().

◆ dualascent_allTermsReachable()

SCIP_Bool dualascent_allTermsReachable	(	SCIP *	scip,
		const GRAPH *	g,
		int	root,
		const SCIP_Real *	redcost
	)

can all terminal be reached via reduced costs from given root?

Parameters

scip	SCIP
g	graph
root	root for reduced costs
redcost	reduced costs

Definition at line 1835 of file dualascent.c.

References a, BMSclearMemoryArray, EAT_LAST, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL_ABORT, SCIPallocMemoryArray, SCIPfreeMemoryArray, SCIPisZero(), GRAPH::term, GRAPH::terms, and TRUE.

Referenced by daExec(), dualascent_execPcMw(), dualascent_update(), reduce_daPcMw(), and reduce_daSlackPrune().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ DEFAULT_DAMAXDEVIATION

◆ DA_MAXDEVIATION_LOWER

◆ DA_MAXDEVIATION_UPPER

◆ DA_EPS

◆ DAPATHS_HITLIMIT_PCMW

◆ DAPATHS_HITLIMIT

◆ DFS

Typedef Documentation

◆ DAPATHS

Enumeration Type Documentation

◆ DACONS_Type

Function Documentation

◆ daconsCreateEmpty()

◆ daconsGetParams()

◆ dapathsSortStarts()

◆ dapathsSetRunParams()

◆ dapathsInit()

◆ dapathsInitRedCosts()

◆ dapathsUpdate()

◆ dapathsRunShortestPaths()

◆ dapathsFreeMembers()

◆ daNodeIsActive()

◆ daInitRescaps()

◆ daUpdateRescaps()

◆ daInit()

◆ daExec()

◆ dualascent_exec()

◆ dualascent_update()

◆ dualascent_execDegCons()

◆ dualascent_execPcMw()

◆ dualascent_pathsPcMw()

◆ dualascent_paths()

◆ dualascent_allTermsReachable()