Detailed Description

propagator for Steiner tree problems, using the LP reduced costs

Author: Daniel Rehfeldt

This propagator makes use of the reduced cost of an optimally solved LP relaxation to propagate the variables

Definition in file prop_stp.c.

#include <assert.h>
#include <string.h>
#include "prop_stp.h"
#include "grph.h"
#include "branch_stp.h"
#include "scip/tree.h"

Go to the source code of this file.

Macros
Propagator properties
#define	PROP_NAME "stp"

#define	PROP_DESC "stp propagator"

#define	PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP \| SCIP_PROPTIMING_AFTERLPLOOP

#define	PROP_PRIORITY 1000000

#define	PROP_FREQ 1

#define	PROP_DELAY FALSE

#define	PROP_STP_EDGE_KILLED -1

#define	PROP_STP_EDGE_UNSET 0

#define	PROP_STP_EDGE_SET 1

#define	PROP_STP_EDGE_FIXED 2

Default parameter values
#define	DEFAULT_MAXNWAITINGROUNDS 2

#define	REDUCTION_WAIT_RATIO 0.02

Functions
Local methods
static SCIP_RETCODE	globalfixing (SCIP scip, SCIP_VAR vars, int nfixededges, const SCIP_Real fixingbounds, const GRAPH graph, SCIP_Real cutoffbound, int nedges)

static SCIP_Bool	redcostAvailable (SCIP *scip)

static void	setRedcosts (SCIP scip, SCIP_VAR vars, int nedges, SCIP_Real cost)

static void	setVnoiDistances (SCIP scip, const SCIP_Real cost, const GRAPH graph, PATH vnoi, SCIP_Real costrev, SCIP_Real pathdist, int pathedge, int vbase)

static void	updateFixingBounds (SCIP_Real fixingbounds, const GRAPH graph, const SCIP_Real cost, const SCIP_Real pathdist, const PATH *vnoi, SCIP_Real lpobjal)

static SCIP_RETCODE	dualcostVarfixing (SCIP scip, SCIP_Real lpobjval, SCIP_VAR vars, SCIP_PROPDATA propdata, int nfixed, const GRAPH graph)

static SCIP_RETCODE	reduceRedcostExtended (SCIP scip, SCIP_Real lpobjval, SCIP_VAR vars, GRAPH propgraph)

static SCIP_RETCODE	redbasedVarfixing (SCIP scip, SCIP_Real lpobjval, SCIP_VAR vars, SCIP_PROPDATA propdata, int nfixed, SCIP_Bool probisinfeas, const GRAPH *g)

Callback methods of propagator
static	SCIP_DECL_PROPCOPY (propCopyStp)

static	SCIP_DECL_PROPFREE (propFreeStp)

static	SCIP_DECL_PROPEXEC (propExecStp)

static	SCIP_DECL_PROPINITSOL (propInitsolStp)

static	SCIP_DECL_PROPEXITSOL (propExitsolStp)

Interface methods
SCIP_RETCODE	fixedgevar (SCIP scip, SCIP_VAR edgevar, int *nfixed)

int	SCIPStpNfixedEdges (SCIP *scip)

void	SCIPStpPropGetGraph (SCIP scip, GRAPH graph, SCIP_Longint graphnodenumber)

SCIP_RETCODE	SCIPincludePropStp (SCIP *scip)

Macro Definition Documentation

◆ PROP_NAME

#define PROP_NAME "stp"

Definition at line 39 of file prop_stp.c.

Referenced by SCIP_DECL_PROPCOPY(), and SCIPincludePropStp().

◆ PROP_DESC

#define PROP_DESC "stp propagator"

Definition at line 40 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 41 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_PRIORITY

#define PROP_PRIORITY 1000000

propagator priority

Definition at line 42 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_FREQ

#define PROP_FREQ 1

propagator frequency

Definition at line 43 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_DELAY

#define PROP_DELAY FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 44 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_STP_EDGE_KILLED

#define PROP_STP_EDGE_KILLED -1

Definition at line 46 of file prop_stp.c.

Referenced by redbasedVarfixing().

◆ PROP_STP_EDGE_UNSET

#define PROP_STP_EDGE_UNSET 0

Definition at line 47 of file prop_stp.c.

Referenced by redbasedVarfixing().

◆ PROP_STP_EDGE_SET

#define PROP_STP_EDGE_SET 1

Definition at line 48 of file prop_stp.c.

Referenced by redbasedVarfixing().

◆ PROP_STP_EDGE_FIXED

#define PROP_STP_EDGE_FIXED 2

Definition at line 49 of file prop_stp.c.

Referenced by redbasedVarfixing().

◆ DEFAULT_MAXNWAITINGROUNDS

#define DEFAULT_MAXNWAITINGROUNDS 2

maximum number of rounds to wait until propagating again

Definition at line 58 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ REDUCTION_WAIT_RATIO

#define REDUCTION_WAIT_RATIO 0.02

ratio of edges to be newly fixed before performing reductions for additional fixing

Definition at line 59 of file prop_stp.c.

Referenced by SCIP_DECL_PROPEXEC().

Function Documentation

◆ globalfixing()

static SCIP_RETCODE globalfixing	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int *	nfixededges,
		const SCIP_Real *	fixingbounds,
		const GRAPH *	graph,
		SCIP_Real	cutoffbound,
		int	nedges
	)

static

try to make global fixings

Parameters

scip	SCIP structure
vars	variables
nfixededges	points to number of fixed edges
fixingbounds	fixing bounds
graph	graph structure
cutoffbound	cutoff bound
nedges	number of edges

Definition at line 121 of file prop_stp.c.

References SCIP_OKAY, SCIPchgVarUbGlobal(), SCIPisEQ(), SCIPisLT(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by dualcostVarfixing().

◆ redcostAvailable()

static SCIP_Bool redcostAvailable ( SCIP * scip )

static

Parameters

scip	SCIP structure

Definition at line 151 of file prop_stp.c.

References FALSE, SCIP_LPSOLSTAT_OPTIMAL, SCIPgetCutoffbound(), SCIPgetLPSolstat(), SCIPhasCurrentNodeLP(), SCIPisInfinity(), SCIPisLPRelax(), SCIPisLPSolBasic(), and TRUE.

Referenced by SCIP_DECL_PROPEXEC().

◆ setRedcosts()

static void setRedcosts	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int	nedges,
		SCIP_Real *	cost
	)

static

initialize reduced costs

Parameters

scip	SCIP structure
vars	variables
nedges	nedges
cost	reduced costs

Definition at line 180 of file prop_stp.c.

References FARAWAY, NULL, SCIPgetSolVal(), SCIPgetVarRedcost(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and SCIPvarIsBinary().

Referenced by dualcostVarfixing(), and reduceRedcostExtended().

◆ setVnoiDistances()

static void setVnoiDistances	(	SCIP *	scip,
		const SCIP_Real *	cost,
		const GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	pathedge,
		int *	vbase
	)

static

initialize (Voronoi) distances

Parameters

scip	SCIP structure
cost	reduced costs
graph	graph data structure
vnoi	Voronoi paths
costrev	reversed reduced costs
pathdist	path distance
pathedge	path edge
vbase	Voronoi base

Definition at line 227 of file prop_stp.c.

References EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_path_execX(), graph_voronoiTerms(), GRAPH::knots, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, and GRAPH::source.

Referenced by dualcostVarfixing(), and reduceRedcostExtended().

◆ updateFixingBounds()

static void updateFixingBounds	(	SCIP_Real *	fixingbounds,
		const GRAPH *	graph,
		const SCIP_Real *	cost,
		const SCIP_Real *	pathdist,
		const PATH *	vnoi,
		SCIP_Real	lpobjal
	)

static

updates fixing bounds for reduced cost fixings

Parameters

fixingbounds	fixing bounds
graph	graph data structure
cost	reduced costs
pathdist	shortest path distances
vnoi	Voronoi paths
lpobjal	LP objective

Definition at line 260 of file prop_stp.c.

References shortest_path::dist, EAT_LAST, GRAPH::head, Is_term, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, and GRAPH::term.

Referenced by dualcostVarfixing().

◆ dualcostVarfixing()

static SCIP_RETCODE dualcostVarfixing	(	SCIP *	scip,
		SCIP_Real	lpobjval,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata,
		int *	nfixed,
		const GRAPH *	graph
	)

static

dual cost based fixing of variables

Parameters

scip	SCIP data structure
lpobjval	LP value
vars	variables
propdata	propagator data
nfixed	pointer to number of fixed edges
graph	graph data structure

Definition at line 287 of file prop_stp.c.

References shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, fixedgevar(), flipedge, globalfixing(), GRAPH::head, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetDepth(), SCIPisGE(), SCIPisGT(), setRedcosts(), setVnoiDistances(), GRAPH::term, and updateFixingBounds().

Referenced by SCIP_DECL_PROPEXEC().

◆ reduceRedcostExtended()

static SCIP_RETCODE reduceRedcostExtended	(	SCIP *	scip,
		SCIP_Real	lpobjval,
		SCIP_VAR **	vars,
		GRAPH *	propgraph
	)

static

extended reduced cost reduction

Parameters

scip	SCIP data structure
lpobjval	LP value
vars	variables
propgraph	graph data structure

Definition at line 367 of file prop_stp.c.

References GRAPH::edges, GRAPH::knots, nnodes, NULL, reduce_extendedEdge(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCutoffbound(), setRedcosts(), setVnoiDistances(), and GRAPH::source.

Referenced by redbasedVarfixing().

◆ redbasedVarfixing()

static SCIP_RETCODE redbasedVarfixing	(	SCIP *	scip,
		SCIP_Real	lpobjval,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata,
		int *	nfixed,
		SCIP_Bool *	probisinfeas,
		const GRAPH *	g
	)

static

This methods tries to fix edges by performing reductions on the current graph. To this end, the already 0-fixed edges are (temporarily) removed from the underlying graph to strengthen the reduction methods.

Parameters

scip	SCIP data structure
lpobjval	LP value
vars	variables
propdata	propagator data
nfixed	pointer to number of fixed edges
probisinfeas	is problem infeasible?
g	graph data structure

Definition at line 424 of file prop_stp.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, GRAPH::edges, FALSE, FARAWAY, GRAPH::fixedges, fixedgevar(), flipedge, graph_copy_data(), graph_edge_del(), graph_free_history(), graph_free_historyDeep(), graph_init_history(), graph_knot_chg(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, GRAPH::ieat, Int_List_Node::index, level0(), NULL, Int_List_Node::parent, PROP_STP_EDGE_FIXED, PROP_STP_EDGE_KILLED, PROP_STP_EDGE_SET, PROP_STP_EDGE_UNSET, reduce_contractZeroEdges(), reduceRedcostExtended(), reduceStp(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPnodeGetNumber(), SCIPStpBranchruleApplyVertexChgs(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, and TRUE.

Referenced by SCIP_DECL_PROPEXEC().

◆ SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyStp )

static

copy method for propagator plugins (called when SCIP copies plugins)

Definition at line 614 of file prop_stp.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropStp(), and SCIPpropGetName().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeStp )

static

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

Definition at line 629 of file prop_stp.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPpropGetData(), and SCIPpropSetData().

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecStp )

static

reduced cost propagation method for an LP solution

Definition at line 647 of file prop_stp.c.

References BLOCKED, GRAPH::cost, dualcostVarfixing(), GRAPH::edges, FALSE, graph_copy(), graph_init_history(), NULL, redbasedVarfixing(), redcostAvailable(), REDUCTION_WAIT_RATIO, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPdebugMessage, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetNPseudoBranchCands(), SCIPgetProbData(), SCIPgetStage(), SCIPisGT(), SCIPnodeGetNumber(), SCIPprobdataGetGraph(), SCIPprobdataGetVars(), SCIPpropGetData(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), STP_DCSTP, STP_PCSPG, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, and TRUE.

◆ SCIP_DECL_PROPINITSOL()

static SCIP_DECL_PROPINITSOL ( propInitsolStp )

static

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

Definition at line 801 of file prop_stp.c.

References NULL, SCIP_OKAY, and SCIPpropGetData().

◆ SCIP_DECL_PROPEXITSOL()

static SCIP_DECL_PROPEXITSOL ( propExitsolStp )

static

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

Definition at line 823 of file prop_stp.c.

References graph_free(), NULL, SCIP_OKAY, SCIPfreeMemoryArrayNull, SCIPpropGetData(), and TRUE.

◆ fixedgevar()

SCIP_RETCODE fixedgevar	(	SCIP *	scip,
		SCIP_VAR *	edgevar,
		int *	nfixed
	)

fix a variable (corresponding to an edge) to zero

Parameters

scip	SCIP data structure
edgevar	the variable to be fixed
nfixed	counter that is incriminated if variable could be fixed

Definition at line 848 of file prop_stp.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPchgVarUb(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by dualcostVarfixing(), redbasedVarfixing(), and reduce_boundHopRc().

◆ SCIPStpNfixedEdges()

int SCIPStpNfixedEdges ( SCIP * scip )

return total number of arcs fixed by 'fixedgevar' method of this propagator

Parameters

scip	SCIP data structure

Definition at line 865 of file prop_stp.c.

References NULL, SCIPfindProp(), and SCIPpropGetData().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIPStpPropGetGraph()

void SCIPStpPropGetGraph	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Longint *	graphnodenumber
	)

gets propagator graph

Parameters

scip	SCIP data structure
graph	graph data
graphnodenumber	point to b&b node for which graph is valid

Definition at line 883 of file prop_stp.c.

References NULL, SCIPfindProp(), and SCIPpropGetData().

◆ SCIPincludePropStp()

SCIP_RETCODE SCIPincludePropStp ( SCIP * scip )

creates the stp propagator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 904 of file prop_stp.c.

References DEFAULT_MAXNWAITINGROUNDS, FALSE, NULL, PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRIORITY, PROP_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPincludePropBasic(), SCIPsetPropCopy(), SCIPsetPropExitsol(), SCIPsetPropFree(), and SCIPsetPropInitsol().

Referenced by runShell(), and SCIP_DECL_PROPCOPY().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_TIMING

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ PROP_STP_EDGE_KILLED

◆ PROP_STP_EDGE_UNSET

◆ PROP_STP_EDGE_SET

◆ PROP_STP_EDGE_FIXED

◆ DEFAULT_MAXNWAITINGROUNDS

◆ REDUCTION_WAIT_RATIO

Function Documentation

◆ globalfixing()

◆ redcostAvailable()

◆ setRedcosts()

◆ setVnoiDistances()

◆ updateFixingBounds()

◆ dualcostVarfixing()

◆ reduceRedcostExtended()

◆ redbasedVarfixing()

◆ SCIP_DECL_PROPCOPY()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPINITSOL()

◆ SCIP_DECL_PROPEXITSOL()

◆ fixedgevar()

◆ SCIPStpNfixedEdges()

◆ SCIPStpPropGetGraph()

◆ SCIPincludePropStp()