Detailed Description

Includes dual-ascent for classic Steiner tree and some variants.

Author: Daniel Rehfeldt

Definition in file dualascent.h.

#include "scip/scip.h"
#include "graph.h"

Data Structures
struct	reduce_cost_parameters

Typedefs
typedef struct reduce_cost_parameters	DAPARAMS

Functions
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_execDegCons (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_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)

Typedef Documentation

◆ DAPARAMS

typedef struct reduce_cost_parameters DAPARAMS

reduced cost parameters

Function Documentation

◆ 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_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 for reduced costs

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_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_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 the PCSPG and the MWCSP

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