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 <stdlib.h>
#include "prop_stp.h"
#include "graph.h"
#include "reduce.h"
#include "solstp.h"
#include "redcosts.h"
#include "extreduce.h"
#include "cons_stp.h"
#include "branch_stp.h"
#include "portab.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

#define	PROP_STP_REDCOST_LEVELS 5

Default parameter values
#define	DEFAULT_MAXNWAITINGROUNDS 2

#define	REDUCTION_WAIT_RATIO_INITIAL 0.01

#define	REDUCTION_WAIT_FACTOR 2.0

Functions
Local methods
static SCIP_RETCODE	fixEdgeVar (SCIP scip, int edge, SCIP_VAR vars, SCIP_PROPDATA propdata)

static SCIP_Real	getCutoffbound (SCIP *scip, SCIP_Real lpbound)

static void	getBoundchangesPcMW (SCIP scip, SCIP_VAR vars, const GRAPH propgraph, int nodestate, SCIP_Bool conflictFound)

static SCIP_RETCODE	getBoundchanges (SCIP scip, SCIP_VAR vars, const GRAPH propgraph, int nodestate, int edgestate, SCIP_Bool *probisinfeas)

static SCIP_RETCODE	getGraphStatesDirected (SCIP scip, const GRAPH graph, int nodestate, int edgestate, SCIP_Bool *probisinfeas)

static SCIP_RETCODE	trailGraphWithStates (SCIP scip, const GRAPH graph, const int nodestate, const int edgestate, SCIP_Bool *probisinfeas)

static SCIP_RETCODE	getRedCost2ndNextDistances (SCIP scip, const SCIP_Real redcost, GRAPH g, PATH vnoi, SCIP_Real pathdist, int vbase, int *state)

static void	mark0FixedArcs (const GRAPH graph, SCIP_VAR vars, STP_Bool arcIs0Fixed)

static void	validateEdgestate (const GRAPH graph, const GRAPH propgraph, SCIP_VAR *vars, const int edgestate, SCIP_Bool *error)

static void	setEdgestate (const GRAPH graph, IDX curr, int *RESTRICT edgestate)

static void	fixEdgestate (const GRAPH graph, IDX curr, int *RESTRICT edgestate)

static SCIP_RETCODE	applyEdgestateToProb (SCIP scip, const GRAPH graph, SCIP_VAR *vars, const int edgestate, SCIP_PROPDATA *propdata)

static void	updateEdgestateFromRed (const GRAPH graph, const GRAPH propgraph, SCIP_VAR *vars, const int nodestate, int edgestate, SCIP_Bool error)

static void	updateEdgestateFromRedPcmw (SCIP scip, const GRAPH graph, const GRAPH propgraph, SCIP_VAR vars, const int nodestate, int edgestate, SCIP_Bool error)

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

static void	updateDeg2LurkingBounds (const GRAPH graph, const SCIP_Real pathdist, const PATH vnoi, SCIP_Real lpobjal, SCIP_Real deg2bounds)

static void	propgraphFixNode (SCIP scip, int node, GRAPH propgraph, SCIP_Real *offset)

static void	propgraphDeleteNode (SCIP scip, int node, GRAPH propgraph, SCIP_Real *offset)

static void	propgraphFixEdge (SCIP scip, int e, GRAPH propgraph)

static void	propgraphDeleteEdge (SCIP scip, int e, GRAPH propgraph)

static void	propgraphMarkFixedTermsPcMw (SCIP scip, const int nodestate, GRAPH propgraph, SCIP_Bool hasFixedTerms)

static void	propgraphApplyStates (SCIP scip, const int nodestate, const int edgestate, GRAPH propgraph, SCIP_Real *offset)

static SCIP_RETCODE	propgraphApplyImplicationsPcMw (SCIP scip, const GRAPH g, SCIP_VAR *vars, SCIP_PROPDATA propdata, SCIP_Bool probisinfeas, SCIP_Real offset)

static SCIP_RETCODE	propgraphPruneUnconnected (SCIP scip, GRAPH propgraph, SCIP_Bool probisinfeas, SCIP_Real offset)

static SCIP_RETCODE	propgraphApplyBoundchanges (SCIP scip, SCIP_VAR vars, const GRAPH g, int nodestate, int edgestate, SCIP_PROPDATA propdata, SCIP_Bool probisinfeas, SCIP_Real *offset)

static SCIP_RETCODE	initPropgraph (SCIP scip, const GRAPH graph, SCIP_PROPDATA *propdata)

static SCIP_Bool	useRedcostdata (const GRAPH *graph)

static void	writeRedcostdata (SCIP scip, int level, const GRAPH graph, SCIP_VAR *vars, SCIP_PROPDATA propdata)

static SCIP_RETCODE	initRedcostdata (SCIP scip, const GRAPH graph, SCIP_VAR *vars, SCIP_PROPDATA propdata)

static void	updateRedcostdata (SCIP scip, const GRAPH graph, SCIP_VAR *vars, SCIP_PROPDATA propdata)

static SCIP_RETCODE	updatePropgraph (SCIP scip, const GRAPH graph, SCIP_PROPDATA *propdata)

static SCIP_RETCODE	fixVarsDualcostLurking (SCIP scip, const GRAPH graph, SCIP_Real cutoffbound, SCIP_PROPDATA propdata, SCIP_VAR *vars)

static SCIP_RETCODE	fixVarsDualcost (SCIP scip, SCIP_VAR vars, SCIP_PROPDATA propdata, GRAPH graph, SCIP_Bool probisinfeas)

static SCIP_RETCODE	fixVarsExtendedRed (SCIP scip, const GRAPH graph, SCIP_VAR *vars, SCIP_PROPDATA propdata)

static SCIP_RETCODE	fixVarsRedbased (SCIP scip, const GRAPH graph, SCIP_VAR *vars, SCIP_PROPDATA propdata, SCIP_Bool *probisinfeas)

static SCIP_Bool	fixVarsRedbasedIsPromising (SCIP scip, const GRAPH graph, SCIP_VAR *vars, SCIP_PROPDATA propdata)

static void	blockEdgesWithGlobalFixings (SCIP scip, SCIP_VAR vars, GRAPH graph)

static SCIP_RETCODE	initPropAtFirstCall (SCIP scip, const GRAPH graph, SCIP_VAR *vars, SCIP_PROPDATA propdata)

static SCIP_RETCODE	applyLastVertexBranch (SCIP scip, const GRAPH graph, SCIP_VAR *vars, SCIP_PROPDATA propdata)

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	SCIPStpFixEdgeVarTo0 (SCIP scip, SCIP_VAR edgevar, SCIP_Bool *success)

SCIP_RETCODE	SCIPStpFixEdgeVarTo1 (SCIP scip, SCIP_VAR edgevar, SCIP_Bool *success)

int	SCIPStpNfixedEdges (SCIP *scip)

SCIP_RETCODE	SCIPStpPropCheckForInfeas (SCIP scip, SCIP_Bool probisinfeas)

SCIP_RETCODE	SCIPStpPropGetGraph (SCIP scip, GRAPH graph, SCIP_Longint graphnodenumber, SCIP_Bool probisinfeas, SCIP_Real offset)

const SCIP_Bool *	SCIPStpPropGet2BoundedArr (SCIP *scip)

SCIP_RETCODE	SCIPincludePropStp (SCIP *scip)

Macro Definition Documentation

◆ PROP_NAME

#define PROP_NAME "stp"

Definition at line 46 of file prop_stp.c.

Referenced by SCIP_DECL_PROPCOPY(), and SCIPincludePropStp().

◆ PROP_DESC

#define PROP_DESC "stp propagator"

Definition at line 47 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 48 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_PRIORITY

#define PROP_PRIORITY 1000000

propagator priority

Definition at line 49 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_FREQ

#define PROP_FREQ 1

propagator frequency

Definition at line 50 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 51 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ PROP_STP_EDGE_KILLED

#define PROP_STP_EDGE_KILLED -1

Definition at line 53 of file prop_stp.c.

Referenced by getBoundchanges(), getGraphStatesDirected(), propgraphApplyStates(), setEdgestate(), trailGraphWithStates(), and validateEdgestate().

◆ PROP_STP_EDGE_UNSET

#define PROP_STP_EDGE_UNSET 0

Definition at line 54 of file prop_stp.c.

Referenced by applyEdgestateToProb(), getBoundchanges(), getGraphStatesDirected(), setEdgestate(), updateEdgestateFromRedPcmw(), and validateEdgestate().

◆ PROP_STP_EDGE_SET

#define PROP_STP_EDGE_SET 1

Definition at line 55 of file prop_stp.c.

Referenced by setEdgestate(), and updateEdgestateFromRedPcmw().

◆ PROP_STP_EDGE_FIXED

#define PROP_STP_EDGE_FIXED 2

Definition at line 56 of file prop_stp.c.

Referenced by fixEdgestate(), getBoundchanges(), getGraphStatesDirected(), propgraphApplyStates(), and validateEdgestate().

◆ PROP_STP_REDCOST_LEVELS

#define PROP_STP_REDCOST_LEVELS 5

Definition at line 58 of file prop_stp.c.

Referenced by fixVarsRedbasedIsPromising(), initRedcostdata(), and updateRedcostdata().

◆ DEFAULT_MAXNWAITINGROUNDS

#define DEFAULT_MAXNWAITINGROUNDS 2

maximum number of rounds to wait until propagating again

Definition at line 67 of file prop_stp.c.

Referenced by SCIPincludePropStp().

◆ REDUCTION_WAIT_RATIO_INITIAL

#define REDUCTION_WAIT_RATIO_INITIAL 0.01

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

Definition at line 68 of file prop_stp.c.

Referenced by fixVarsRedbasedIsPromising(), and SCIP_DECL_PROPINITSOL().

◆ REDUCTION_WAIT_FACTOR

#define REDUCTION_WAIT_FACTOR 2.0

Definition at line 69 of file prop_stp.c.

Referenced by fixVarsRedbasedIsPromising().

Function Documentation

◆ fixEdgeVar()

static SCIP_RETCODE fixEdgeVar	(	SCIP *	scip,
		int	edge,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata
	)

static

fix a variable (corresponding to an edge) to zero

Parameters

scip	SCIP data structure
edge	the edge
vars	variables
propdata	propagator data

Definition at line 147 of file prop_stp.c.

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

Referenced by applyEdgestateToProb(), applyLastVertexBranch(), fixVarsDualcost(), fixVarsExtendedRed(), and propgraphApplyImplicationsPcMw().

◆ getCutoffbound()

static SCIP_Real getCutoffbound	(	SCIP *	scip,
		SCIP_Real	lpbound
	)

static

gets cutoff bound

Parameters

scip	SCIP data structure
lpbound	LP bound

Definition at line 172 of file prop_stp.c.

References SCIP_Real, SCIPdebugMessage, SCIPgetCutoffbound(), and SCIPprobdataGetPresolUpperBound().

Referenced by fixVarsDualcost(), fixVarsExtendedRed(), fixVarsRedbased(), and writeRedcostdata().

◆ getBoundchangesPcMW()

static void getBoundchangesPcMW	(	SCIP *	scip,
		SCIP_VAR **	vars,
		const GRAPH *	propgraph,
		int *	nodestate,
		SCIP_Bool *	conflictFound
	)

static

gets bound changes specific for PC/MW

Parameters

scip	SCIP structure
vars	variables
propgraph	graph data structure
nodestate	state
conflictFound	conflict found?

Definition at line 201 of file prop_stp.c.

References BRANCH_STP_VERTEX_KILLED, BRANCH_STP_VERTEX_TERM, GRAPH::cost, GRAPH::extended, FALSE, graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsPropPotTerm(), GRAPH::knots, nnodes, GRAPH::prize, SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), GRAPH::term2edge, and TRUE.

Referenced by getBoundchanges(), and getGraphStatesDirected().

◆ getBoundchanges()

static SCIP_RETCODE getBoundchanges	(	SCIP *	scip,
		SCIP_VAR **	vars,
		const GRAPH *	propgraph,
		int *	nodestate,
		int *	edgestate,
		SCIP_Bool *	probisinfeas
	)

static

gets bound changes

Parameters

scip	SCIP structure
vars	variables
propgraph	graph data structure
nodestate	node state (uninitialized)
edgestate	edge state (uninitialized)
probisinfeas	is problem infeasible?

Definition at line 281 of file prop_stp.c.

References BRANCH_STP_VERTEX_TERM, BRANCH_STP_VERTEX_UNSET, GRAPH::extended, FALSE, getBoundchangesPcMW(), graph_get_nEdges(), graph_get_nNodes(), graph_pc_edgeIsExtended(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, nnodes, PROP_STP_EDGE_FIXED, PROP_STP_EDGE_KILLED, PROP_STP_EDGE_UNSET, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetDepth(), SCIPStpBranchruleGetVertexChgs(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), GRAPH::tail, and TRUE.

Referenced by propgraphApplyBoundchanges().

◆ getGraphStatesDirected()

static SCIP_RETCODE getGraphStatesDirected	(	SCIP *	scip,
		const GRAPH *	graph,
		int *	nodestate,
		int *	edgestate,
		SCIP_Bool *	probisinfeas
	)

static

gets state of graph at current B&B node, including bound changes; takes direction of edges into account!

Parameters

scip	SCIP structure
graph	graph data structure
nodestate	node state (uninitialized)
edgestate	edge state (uninitialized)
probisinfeas	is problem infeasible?

Definition at line 368 of file prop_stp.c.

References BRANCH_STP_VERTEX_TERM, GRAPH::extended, FALSE, getBoundchangesPcMW(), graph_get_nEdges(), graph_pc_isPcMw(), GRAPH::head, PROP_STP_EDGE_FIXED, PROP_STP_EDGE_KILLED, PROP_STP_EDGE_UNSET, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetDepth(), SCIPprobdataGetVars(), SCIPStpBranchruleGetVertexChgs(), SCIPStpBranchruleInitNodeState(), SCIPStpBranchruleIsActive(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), GRAPH::tail, and TRUE.

Referenced by SCIPStpPropCheckForInfeas().

◆ trailGraphWithStates()

static SCIP_RETCODE trailGraphWithStates	(	SCIP *	scip,
		const GRAPH *	graph,
		const int *	nodestate,
		const int *	edgestate,
		SCIP_Bool *	probisinfeas
	)

static

trails graph and checks for infeasibility

Parameters

scip	SCIP structure
graph	graph data structure
nodestate	node state
edgestate	edge state
probisinfeas	is problem infeasible?

Definition at line 433 of file prop_stp.c.

References BRANCH_STP_VERTEX_KILLED, BRANCH_STP_VERTEX_TERM, graph_get_nNodes(), GRAPH::head, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, PROP_STP_EDGE_KILLED, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPfreeBufferArray, GRAPH::source, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPushBack, StpVecReserve, GRAPH::terms, and TRUE.

Referenced by SCIPStpPropCheckForInfeas().

◆ getRedCost2ndNextDistances()

static SCIP_RETCODE getRedCost2ndNextDistances	(	SCIP *	scip,
		const SCIP_Real *	redcost,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	pathdist,
		int *	vbase,
		int *	state
	)

static

initialize reduced cost distances

Parameters

scip	SCIP structure
redcost	reduced costs
g	graph data structure
vnoi	Voronoi paths
pathdist	path distance
vbase	Voronoi base
state	state

Definition at line 503 of file prop_stp.c.

References EAT_LAST, FARAWAY, flipedge, graph_get2nextTermPaths(), graph_get_nEdges(), graph_get_nNodes(), graph_isMarked(), graph_path_execX(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and GRAPH::source.

Referenced by fixVarsDualcost().

◆ mark0FixedArcs()

static void mark0FixedArcs	(	const GRAPH *	graph,
		SCIP_VAR **	vars,
		STP_Bool *	arcIs0Fixed
	)

inlinestatic

marks arcs fixed to 0

Parameters

graph	graph structure
vars	variables (in)
arcIs0Fixed	array (out)

Definition at line 544 of file prop_stp.c.

References graph_get_nEdges(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by fixVarsExtendedRed().

◆ validateEdgestate()

static void validateEdgestate	(	const GRAPH *	graph,
		const GRAPH *	propgraph,
		SCIP_VAR **	vars,
		const int *	edgestate,
		SCIP_Bool *	error
	)

static

some checks

Parameters

graph	graph structure
propgraph	propagator graph
vars	variables
edgestate	edge state array
error	error during update?

Definition at line 570 of file prop_stp.c.

References FALSE, flipedge, graph_edge_printInfo(), graph_get_nEdges(), graph_pc_edgeIsExtended(), graph_pc_isPcMw(), PROP_STP_EDGE_FIXED, PROP_STP_EDGE_KILLED, PROP_STP_EDGE_UNSET, SCIP_Bool, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by updateEdgestateFromRed(), and updateEdgestateFromRedPcmw().

◆ setEdgestate()

static void setEdgestate	(	const GRAPH *	graph,
		IDX *	curr,
		int *RESTRICT	edgestate
	)

inlinestatic

helper method for reduction based variable fixings

Parameters

graph	graph structure
curr	current ancestor
edgestate	edge state array

Definition at line 619 of file prop_stp.c.

References flipedge, graph_edge_printInfo(), Int_List_Node::index, NULL, Int_List_Node::parent, PROP_STP_EDGE_KILLED, PROP_STP_EDGE_SET, and PROP_STP_EDGE_UNSET.

Referenced by updateEdgestateFromRed().

◆ fixEdgestate()

static void fixEdgestate	(	const GRAPH *	graph,
		IDX *	curr,
		int *RESTRICT	edgestate
	)

inlinestatic

helper method for reduction based variable fixings

Parameters

graph	graph structure
curr	current ancestor
edgestate	edge state array

Definition at line 650 of file prop_stp.c.

References flipedge, graph_edge_printInfo(), Int_List_Node::index, NULL, Int_List_Node::parent, and PROP_STP_EDGE_FIXED.

Referenced by updateEdgestateFromRed(), and updateEdgestateFromRedPcmw().

◆ applyEdgestateToProb()

static SCIP_RETCODE applyEdgestateToProb	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		const int *	edgestate,
		SCIP_PROPDATA *	propdata
	)

static

method for reduction based variable fixings

Parameters

scip	SCIP data structure
graph	graph structure
vars	variables
edgestate	edge state array
propdata	propagator data

Definition at line 676 of file prop_stp.c.

References GRAPH::cost, GRAPH::extended, FARAWAY, fixEdgeVar(), graph_edge_printInfo(), graph_get_nEdges(), graph_pc_isPcMw(), PROP_STP_EDGE_UNSET, SCIP_Bool, SCIP_CALL, SCIP_OKAY, and SCIPisGE().

Referenced by fixVarsRedbased().

◆ updateEdgestateFromRed()

static void updateEdgestateFromRed	(	const GRAPH *	graph,
		const GRAPH *	propgraph,
		SCIP_VAR **	vars,
		const int *	nodestate,
		int *	edgestate,
		SCIP_Bool *	error
	)

static

update method for reduction based variable fixings

Parameters

graph	graph structure
propgraph	propagator graph
vars	variables
nodestate	node state array
edgestate	edge state array
error	error during update?

Definition at line 721 of file prop_stp.c.

References GRAPH::ancestors, EAT_FREE, GRAPH::extended, fixEdgestate(), flipedge, graph_get_nEdges(), graph_getFixedges(), graph_pc_isPcMw(), GRAPH::head, GRAPH::ieat, GRAPH::pcancestors, SCIP_Bool, setEdgestate(), GRAPH::source, GRAPH::tail, and validateEdgestate().

Referenced by fixVarsRedbased().

◆ updateEdgestateFromRedPcmw()

static void updateEdgestateFromRedPcmw	(	SCIP *	scip,
		const GRAPH *	graph,
		const GRAPH *	propgraph,
		SCIP_VAR **	vars,
		const int *	nodestate,
		int *	edgestate,
		SCIP_Bool *	error
	)

static

update method for reduction based variable fixings

Parameters

scip	SCIP
graph	graph structure
propgraph	propagator graph
vars	variables
nodestate	node state array
edgestate	edge state array
error	error during update?

Definition at line 763 of file prop_stp.c.

References GRAPH::ancestors, EAT_FREE, GRAPH::edges, FALSE, fixEdgestate(), flipedge, graph_get_nEdges(), graph_get_nNodes(), graph_getFixedges(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), GRAPH::head, GRAPH::ieat, Int_List_Node::index, GRAPH::knots, nnodes, NULL, Int_List_Node::parent, GRAPH::pcancestors, PROP_STP_EDGE_SET, PROP_STP_EDGE_UNSET, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_markPcancestors(), GRAPH::source, GRAPH::tail, TRUE, and validateEdgestate().

Referenced by fixVarsRedbased().

◆ updateEdgeLurkingBounds()

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

static

updates fixing bounds for reduced cost fixings

Parameters

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

Definition at line 862 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 fixVarsDualcost().

◆ updateDeg2LurkingBounds()

static void updateDeg2LurkingBounds	(	const GRAPH *	graph,
		const SCIP_Real *	pathdist,
		const PATH *	vnoi,
		SCIP_Real	lpobjal,
		SCIP_Real *	deg2bounds
	)

static

Parameters

graph	graph data structure
pathdist	shortest path distances
vnoi	Voronoi paths
lpobjal	LP objective
deg2bounds	bounds

Definition at line 890 of file prop_stp.c.

References shortest_path::dist, Is_term, GRAPH::knots, nnodes, SCIP_Real, and GRAPH::term.

Referenced by fixVarsDualcost().

◆ propgraphFixNode()

static void propgraphFixNode	(	SCIP *	scip,
		int	node,
		GRAPH *	propgraph,
		SCIP_Real *	offset
	)

inlinestatic

fixes node of propgraph (ignores dummy terminals!)

Parameters

scip	SCIP data structure
node	the node
propgraph	propagator graph
offset	pointer to the offset (in/out)

Definition at line 914 of file prop_stp.c.

References GRAPH::extended, graph_knot_chg(), graph_knot_printInfo(), graph_pc_enforceNode(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_knotToFixedTerm(), SCIPdebugMessage, and STP_TERM.

Referenced by propgraphApplyStates().

◆ propgraphDeleteNode()

static void propgraphDeleteNode	(	SCIP *	scip,
		int	node,
		GRAPH *	propgraph,
		SCIP_Real *	offset
	)

inlinestatic

deletes node of propgraph (ignores dummy terminals!)

Parameters

scip	SCIP data structure
node	the node
propgraph	propagator graph
offset	offset pointer

Definition at line 961 of file prop_stp.c.

References GRAPH::extended, graph_knot_del(), graph_knot_printInfo(), graph_pc_deleteTerm(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_knotIsPropPotTerm(), Is_anyTerm, Is_term, SCIPdebugMessage, GRAPH::term, and TRUE.

Referenced by propgraphApplyStates().

◆ propgraphFixEdge()

static void propgraphFixEdge	(	SCIP *	scip,
		int	e,
		GRAPH *	propgraph
	)

static

fixes edge of propgraph

Parameters

scip	SCIP data structure
e	the edge
propgraph	propagator graph

Definition at line 1012 of file prop_stp.c.

References GRAPH::cost, GRAPH::extended, FARAWAY, flipedge, graph_pc_isMw(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, SCIP_Bool, SCIPisEQ(), SCIPisGE(), and GRAPH::tail.

Referenced by propgraphApplyStates().

◆ propgraphDeleteEdge()

static void propgraphDeleteEdge	(	SCIP *	scip,
		int	e,
		GRAPH *	propgraph
	)

static

deletes edge of propgraph

Parameters

scip	SCIP data structure
e	the edge
propgraph	propagator graph

Definition at line 1053 of file prop_stp.c.

References GRAPH::cost, GRAPH::extended, FARAWAY, flipedge, graph_edge_del(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, Is_term, SCIP_Bool, SCIPisGE(), GRAPH::tail, GRAPH::term, and TRUE.

Referenced by propgraphApplyStates().

◆ propgraphMarkFixedTermsPcMw()

static void propgraphMarkFixedTermsPcMw	(	SCIP *	scip,
		const int *	nodestate,
		GRAPH *	propgraph,
		SCIP_Bool *	hasFixedTerms
	)

static

apply current bound changes to propgraph

Parameters

scip	SCIP data structure
nodestate	node state
propgraph	propagator graph
hasFixedTerms	have terminals been fixed?

Definition at line 1091 of file prop_stp.c.

References BLOCKED_MINOR, BRANCH_STP_VERTEX_TERM, GRAPH::extended, FALSE, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotChgPrize(), graph_pc_knotIsPropPotTerm(), nnodes, and TRUE.

Referenced by propgraphApplyBoundchanges().

◆ propgraphApplyStates()

static void propgraphApplyStates	(	SCIP *	scip,
		const int *	nodestate,
		const int *	edgestate,
		GRAPH *	propgraph,
		SCIP_Real *	offset
	)

inlinestatic

helper method for propgraphApplyBoundchanges

Parameters

scip	SCIP data structure (in)
nodestate	node state (in)
edgestate	edge state (in)
propgraph	propagator graph (in/out)
offset	pointer to the offset (in/out)

Definition at line 1121 of file prop_stp.c.

References BRANCH_STP_VERTEX_KILLED, BRANCH_STP_VERTEX_TERM, flipedge, graph_get_nEdges(), graph_get_nNodes(), nnodes, PROP_STP_EDGE_FIXED, PROP_STP_EDGE_KILLED, propgraphDeleteEdge(), propgraphDeleteNode(), propgraphFixEdge(), propgraphFixNode(), and GRAPH::tail.

Referenced by propgraphApplyBoundchanges().

◆ propgraphApplyImplicationsPcMw()

static SCIP_RETCODE propgraphApplyImplicationsPcMw	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata,
		SCIP_Bool *	probisinfeas,
		SCIP_Real *	offset
	)

static

Apply current implications resulting from bound changes to propgraph.

Parameters

scip	SCIP data structure
g	the original graph
vars	variables
propdata	propagator data
probisinfeas	is problem infeasible?
offset	pointer to the offset

Definition at line 1170 of file prop_stp.c.

References BLOCKED_MINOR, GRAPH::extended, fixEdgeVar(), GRAPH::grad, graph_get_nNodes(), graph_knot_del(), graph_pc_deleteTerm(), graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_knotIsPropPotTerm(), graph_pc_knotToFixedTerm(), graph_pc_nNonFixedTerms(), Is_anyTerm, Is_pseudoTerm, GRAPH::knots, nnodes, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisLT(), SCIPStpGetPcImplNstarts(), SCIPStpGetPcImplStarts(), SCIPStpGetPcImplVerts(), GRAPH::term, and TRUE.

Referenced by propgraphApplyBoundchanges().

◆ propgraphPruneUnconnected()

static SCIP_RETCODE propgraphPruneUnconnected	(	SCIP *	scip,
		GRAPH *	propgraph,
		SCIP_Bool *	probisinfeas,
		SCIP_Real *	offset
	)

static

Prunes unconnected vertices and edges. Also checks for resulting infeasibility

Parameters

scip	SCIP data structure
propgraph	propagator graph (in)
probisinfeas	is problem infeasible?
offset	pointer to the offset

Definition at line 1276 of file prop_stp.c.

References FALSE, graph_pc_isRootedPcMw(), reduce_unconnectedInfeas(), reduce_unconnectedRpcRmwInfeas(), SCIP_CALL, and SCIP_OKAY.

Referenced by fixVarsRedbased(), and SCIPStpPropGetGraph().

◆ propgraphApplyBoundchanges()

static SCIP_RETCODE propgraphApplyBoundchanges	(	SCIP *	scip,
		SCIP_VAR **	vars,
		const GRAPH *	g,
		int *	nodestate,
		int *	edgestate,
		SCIP_PROPDATA *	propdata,
		SCIP_Bool *	probisinfeas,
		SCIP_Real *	offset
	)

static

Apply current bound changes to propgraph. Note that the graph type of propgraph might be changed!

Parameters

scip	SCIP data structure
vars	variables
g	graph data structure
nodestate	node state (uninitialized)
edgestate	edge state (uninitialized)
propdata	propagator data
probisinfeas	is problem infeasible?
offset	pointer to the offset

Definition at line 1297 of file prop_stp.c.

References BLOCKED_MINOR, GRAPH::edges, FALSE, getBoundchanges(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_transPcmw2rooted(), GRAPH::knots, propgraphApplyImplicationsPcMw(), propgraphApplyStates(), propgraphMarkFixedTermsPcMw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, and GRAPH::stp_type.

Referenced by fixVarsRedbased(), and SCIPStpPropGetGraph().

◆ initPropgraph()

static SCIP_RETCODE initPropgraph	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_PROPDATA *	propdata
	)

inlinestatic

initializes

Parameters

scip	SCIP data structure
graph	graph structure to use for the update
propdata	propagator data

Definition at line 1361 of file prop_stp.c.

References graph_copy(), graph_copyPseudoAncestors(), graph_initHistory(), NULL, SCIP_CALL, SCIP_OKAY, SCIPgetCurrentNode(), and SCIPnodeGetNumber().

Referenced by initPropAtFirstCall(), and SCIPStpPropGetGraph().

◆ useRedcostdata()

static SCIP_Bool useRedcostdata ( const GRAPH * graph )

inlinestatic

initializes

Parameters

graph graph structure to use for the update

Definition at line 1394 of file prop_stp.c.

References graph_pc_isPc(), and graph_typeIsSpgLike().

Referenced by fixVarsRedbasedIsPromising(), and initPropAtFirstCall().

◆ writeRedcostdata()

static void writeRedcostdata	(	SCIP *	scip,
		int	level,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata
	)

static

writes reduced costs into given level

Parameters

scip	SCIP data structure
level	the level
graph	graph structure to use for the update
vars	variables
propdata	propagator data

Definition at line 1404 of file prop_stp.c.

References GE, getCutoffbound(), LE, redcosts_forLPget(), redcosts_getEdgeCosts(), redcosts_setCutoff(), redcosts_setDualBound(), redcosts_setRoot(), SCIP_Real, and GRAPH::source.

Referenced by fixVarsExtendedRed(), initRedcostdata(), and updateRedcostdata().

◆ initRedcostdata()

static SCIP_RETCODE initRedcostdata	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata
	)

inlinestatic

initializes

Parameters

scip	SCIP data structure
graph	graph structure to use for the update
vars	variables
propdata	propagator data

Definition at line 1430 of file prop_stp.c.

References reduced_costs_parameters::cutoff, graph_get_nEdges(), graph_get_nNodes(), nnodes, NULL, PROP_STP_REDCOST_LEVELS, redcosts_initFromParams(), SCIP_CALL, SCIP_OKAY, and writeRedcostdata().

Referenced by initPropAtFirstCall().

◆ updateRedcostdata()

static void updateRedcostdata	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata
	)

inlinestatic

updates

Parameters

scip	SCIP data structure
graph	graph structure to use for the update
vars	variables
propdata	propagator data

Definition at line 1460 of file prop_stp.c.

References PROP_STP_REDCOST_LEVELS, redcosts_addLevel(), redcosts_getLevel(), redcosts_getNlevels(), SCIP_Bool, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPrandomGetInt(), and writeRedcostdata().

Referenced by fixVarsRedbasedIsPromising().

◆ updatePropgraph()

static SCIP_RETCODE updatePropgraph	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_PROPDATA *	propdata
	)

inlinestatic

update the graph from propdata from given graph

Parameters

scip	SCIP data structure
graph	graph structure to use for the update
propdata	propagator data

Definition at line 1516 of file prop_stp.c.

References GRAPH::edges, graph_copyData(), graph_freeHistory(), graph_freeHistoryDeep(), graph_initHistory(), graph_pc_isRootedPcMw(), graph_pc_nFixedTerms(), GRAPH::knots, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, SCIP_CALL, SCIP_OKAY, SCIPgetCurrentNode(), and SCIPnodeGetNumber().

Referenced by fixVarsRedbased(), and SCIPStpPropGetGraph().

◆ fixVarsDualcostLurking()

static SCIP_RETCODE fixVarsDualcostLurking	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_Real	cutoffbound,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR **	vars
	)

static

try to make global fixings based on lurking bounds

Parameters

scip	SCIP structure
graph	graph structure
cutoffbound	cutoff bound
propdata	propagator data
vars	variables

Definition at line 1545 of file prop_stp.c.

References GRAPH::edges, Is_term, GRAPH::knots, nnodes, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPchgVarUbGlobal(), SCIPisEQ(), SCIPisLT(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), GRAPH::term, and TRUE.

Referenced by fixVarsDualcost().

◆ fixVarsDualcost()

static SCIP_RETCODE fixVarsDualcost	(	SCIP *	scip,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata,
		GRAPH *	graph,
		SCIP_Bool *	probisinfeas
	)

static

dual cost based fixing of variables

Parameters

scip	SCIP data structure
vars	variables
propdata	propagator data
graph	graph data structure
probisinfeas	is problem infeasible?

Definition at line 1601 of file prop_stp.c.

References BMScopyMemoryArray, BRANCH_STP_VERTEX_TERM, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, fixEdgeVar(), fixVarsDualcostLurking(), flipedge, getCutoffbound(), getRedCost2ndNextDistances(), graph_knot_chg(), graph_mark(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, redcosts_forLPareReliable(), redcosts_forLPget(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetDepth(), SCIPisGT(), SCIPisLT(), SCIPStpBranchruleGetVertexChgs(), SCIPStpBranchruleInitNodeState(), SCIPStpBranchruleIsActive(), GRAPH::source, STP_TERM, GRAPH::term, TRUE, updateDeg2LurkingBounds(), and updateEdgeLurkingBounds().

Referenced by SCIP_DECL_PROPEXEC().

◆ fixVarsExtendedRed()

static SCIP_RETCODE fixVarsExtendedRed	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata
	)

static

extended reduced cost reduction

Parameters

scip	SCIP data structure
graph	original graph data structure
vars	variables
propdata	propagator data

Definition at line 1749 of file prop_stp.c.

References GRAPH::edges, extreduce_deleteArcs(), fixEdgeVar(), getCutoffbound(), graph_mark(), graph_pc_2org(), graph_pc_2trans(), graph_pc_edgeIsExtended(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), mark0FixedArcs(), NULL, redcosts_getCutoff(), redcosts_getCutoffTop(), redcosts_getEdgeCostsTop(), redcosts_getNlevels(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), redcosts_increaseOnDeletedArcs(), redcosts_initializeDistances(), redcosts_setCutoffFromBound(), redcosts_unifyBlockedEdgeCosts(), reduce_extendedEdge(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPvarGetUbLocal(), GRAPH::source, GRAPH::stp_type, TRUE, and writeRedcostdata().

Referenced by fixVarsRedbased().

◆ fixVarsRedbased()

static SCIP_RETCODE fixVarsRedbased	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata,
		SCIP_Bool *	probisinfeas
	)

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
graph	graph data structure
vars	variables
propdata	propagator data
probisinfeas	is problem infeasible?

Definition at line 1846 of file prop_stp.c.

References applyEdgestateToProb(), extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, GRAPH::extended, extred_fast, extreduce_distDataFree(), extreduce_distDataInit(), extreduce_extPermaFree(), extreduce_extPermaInit(), extreduce_pseudoDeleteNodes(), FALSE, fixVarsExtendedRed(), getCutoffbound(), graph_free_dcsr(), graph_get_nEdges(), graph_get_nNodes(), graph_init_dcsr(), graph_path_exit(), graph_pc_isMw(), graph_pc_isPc(), graph_pc_isPcMw(), graph_typeIsSpgLike(), graph_valid(), nnodes, NULL, propgraphApplyBoundchanges(), propgraphPruneUnconnected(), extension_data_permanent::redcostdata, extension_data_permanent::redcostEqualAllow, redcosts_getCutoff(), redcosts_getNlevels(), redcosts_initializeDistances(), redcosts_setCutoffFromBound(), redcosts_unifyBlockedEdgeCosts(), reduce_mw(), reduce_pc(), reduce_solFree(), reduce_solGetOffset(), reduce_solInit(), reduce_stp(), reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, TRUE, updateEdgestateFromRed(), updateEdgestateFromRedPcmw(), and updatePropgraph().

Referenced by SCIP_DECL_PROPEXEC().

◆ fixVarsRedbasedIsPromising()

static SCIP_Bool fixVarsRedbasedIsPromising	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata
	)

static

promising?

Parameters

scip	SCIP data structure
graph	graph data structure
vars	variables
propdata	propagator data

Definition at line 2012 of file prop_stp.c.

References GRAPH::edges, FALSE, GE, graph_pc_isPcMw(), graph_typeIsSpgLike(), PROP_STP_REDCOST_LEVELS, REDUCTION_WAIT_FACTOR, REDUCTION_WAIT_RATIO_INITIAL, SCIP_Bool, SCIP_Longint, SCIP_Real, SCIPdebugMessage, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPisGT(), SCIPnodeGetNumber(), STP_BRMWCSP, GRAPH::stp_type, TRUE, updateRedcostdata(), and useRedcostdata().

Referenced by SCIP_DECL_PROPEXEC().

◆ blockEdgesWithGlobalFixings()

static void blockEdgesWithGlobalFixings	(	SCIP *	scip,
		SCIP_VAR **	vars,
		GRAPH *	graph
	)

inlinestatic

block edges of the underlying graphs by using global fixings

Parameters

scip	SCIP data structure
vars	variables
graph	graph data structure

Definition at line 2068 of file prop_stp.c.

References BLOCKED, GRAPH::cost, EQ, graph_get_nEdges(), graph_pc_isPc(), graph_typeIsSpgLike(), LT, SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), STP_DCSTP, and GRAPH::stp_type.

Referenced by SCIP_DECL_PROPEXEC().

◆ initPropAtFirstCall()

static SCIP_RETCODE initPropAtFirstCall	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata
	)

static

initializes for first call

Parameters

scip	SCIP data structure
graph	graph structure to use for the update
vars	variables
propdata	propagator data

Definition at line 2105 of file prop_stp.c.

References EAT_LAST, graph_get_nNodes(), graph_pc_isPcMw(), graph_typeIsSpgLike(), initPropgraph(), initRedcostdata(), Is_term, GRAPH::maxdeg, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPchgVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), GRAPH::source, STP_BRMWCSP, STP_DCSTP, GRAPH::stp_type, GRAPH::term, TRUE, and useRedcostdata().

Referenced by SCIP_DECL_PROPEXEC().

◆ applyLastVertexBranch()

static SCIP_RETCODE applyLastVertexBranch	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_VAR **	vars,
		SCIP_PROPDATA *	propdata
	)

static

applies vertex branching changes. NOTE: this is necessary, because SCIP is crazy slow in propagating constraints, so we do it ourselves

Parameters

scip	SCIP data structure
graph	graph structure to use for the update
vars	variables
propdata	propagator data

Definition at line 2167 of file prop_stp.c.

References EAT_LAST, FALSE, fixEdgeVar(), flipedge, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetCurrentNode(), SCIPnodeGetDepth(), SCIPStpBranchruleGetVertexChgLast(), and SCIPStpBranchruleIsActive().

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 2205 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 2220 of file prop_stp.c.

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

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecStp )

static

reduced cost propagation method for an LP solution

Definition at line 2240 of file prop_stp.c.

References applyLastVertexBranch(), blockEdgesWithGlobalFixings(), FALSE, fixVarsDualcost(), fixVarsRedbased(), fixVarsRedbasedIsPromising(), initPropAtFirstCall(), NULL, redcosts_forLPareAvailable(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPdebugMessage, SCIPgetCurrentNode(), SCIPgetLPObjval(), SCIPgetNLPIterations(), SCIPgetNPseudoBranchCands(), SCIPgetProbData(), SCIPgetStage(), SCIPnodeGetDepth(), SCIPnodeGetNumber(), SCIPprobdataGetGraph(), SCIPprobdataGetVars(), SCIPpropGetData(), and SCIPStpPropCheckForInfeas().

◆ 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 2354 of file prop_stp.c.

References FALSE, NULL, REDUCTION_WAIT_RATIO_INITIAL, 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 2388 of file prop_stp.c.

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

◆ SCIPStpFixEdgeVarTo0()

SCIP_RETCODE SCIPStpFixEdgeVarTo0	(	SCIP *	scip,
		SCIP_VAR *	edgevar,
		SCIP_Bool *	success
	)

fix a variable (corresponding to an edge) to 0

Parameters

scip	SCIP data structure
edgevar	the variable to be fixed
success	could variable be fixed?

Definition at line 2419 of file prop_stp.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPchgVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by reduce_boundHopRc(), and subsolFixOrgEdges().

◆ SCIPStpFixEdgeVarTo1()

SCIP_RETCODE SCIPStpFixEdgeVarTo1	(	SCIP *	scip,
		SCIP_VAR *	edgevar,
		SCIP_Bool *	success
	)

fix a variable (corresponding to an edge) to 1

Parameters

scip	SCIP data structure
edgevar	the variable to be fixed
success	could variable be fixed?

Definition at line 2443 of file prop_stp.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPchgVarLb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by subsolFixOrgEdges().

◆ 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 2467 of file prop_stp.c.

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

Referenced by abortSlackPruneEarly(), and SCIP_DECL_HEUREXEC().

◆ SCIPStpPropCheckForInfeas()

SCIP_RETCODE SCIPStpPropCheckForInfeas	(	SCIP *	scip,
		SCIP_Bool *	probisinfeas
	)

checks whether problem has become infeasible at current node NOTE: we basically check whether all terminals (at given B&B node) are reachable from root, taking bound changes into account

Parameters

scip	SCIP data structure
probisinfeas	is infeasible?

Definition at line 2488 of file prop_stp.c.

References FALSE, getGraphStatesDirected(), graph_get_nEdges(), graph_get_nNodes(), nnodes, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPprobdataGetGraph2(), and trailGraphWithStates().

Referenced by SCIP_DECL_PROPEXEC().

◆ SCIPStpPropGetGraph()

SCIP_RETCODE SCIPStpPropGetGraph	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Longint *	graphnodenumber,
		SCIP_Bool *	probisinfeas,
		SCIP_Real *	offset
	)

gives propagator graph

Parameters

scip	SCIP data structure
graph	graph data
graphnodenumber	point to b&b node for which graph is valid
probisinfeas	infeasible problem?
offset	needed for PC/MW

Definition at line 2521 of file prop_stp.c.

References FALSE, graph_get_nEdges(), graph_get_nNodes(), graph_path_exit(), graph_valid(), initPropgraph(), nnodes, NULL, propgraphApplyBoundchanges(), propgraphPruneUnconnected(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindProp(), SCIPfreeBufferArray, SCIPprobdataGetGraph2(), SCIPprobdataGetVars(), SCIPpropGetData(), TRUE, and updatePropgraph().

Referenced by SCIP_DECL_RELAXEXEC().

◆ SCIPStpPropGet2BoundedArr()

const SCIP_Bool* SCIPStpPropGet2BoundedArr ( SCIP * scip )

gives array indicating which nodes are degree-2 bounded

Parameters

scip	SCIP data structure

Definition at line 2593 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 2610 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, SCIPcreateRandom(), SCIPincludePropBasic(), SCIPsetPropCopy(), SCIPsetPropExitsol(), SCIPsetPropFree(), SCIPsetPropInitsol(), and TRUE.

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

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

◆ PROP_STP_REDCOST_LEVELS

◆ DEFAULT_MAXNWAITINGROUNDS

◆ REDUCTION_WAIT_RATIO_INITIAL

◆ REDUCTION_WAIT_FACTOR

Function Documentation

◆ fixEdgeVar()

◆ getCutoffbound()

◆ getBoundchangesPcMW()

◆ getBoundchanges()

◆ getGraphStatesDirected()

◆ trailGraphWithStates()

◆ getRedCost2ndNextDistances()

◆ mark0FixedArcs()

◆ validateEdgestate()

◆ setEdgestate()

◆ fixEdgestate()

◆ applyEdgestateToProb()

◆ updateEdgestateFromRed()

◆ updateEdgestateFromRedPcmw()

◆ updateEdgeLurkingBounds()

◆ updateDeg2LurkingBounds()

◆ propgraphFixNode()

◆ propgraphDeleteNode()

◆ propgraphFixEdge()

◆ propgraphDeleteEdge()

◆ propgraphMarkFixedTermsPcMw()

◆ propgraphApplyStates()

◆ propgraphApplyImplicationsPcMw()

◆ propgraphPruneUnconnected()

◆ propgraphApplyBoundchanges()

◆ initPropgraph()

◆ useRedcostdata()

◆ writeRedcostdata()

◆ initRedcostdata()

◆ updateRedcostdata()

◆ updatePropgraph()

◆ fixVarsDualcostLurking()

◆ fixVarsDualcost()

◆ fixVarsExtendedRed()

◆ fixVarsRedbased()

◆ fixVarsRedbasedIsPromising()

◆ blockEdgesWithGlobalFixings()

◆ initPropAtFirstCall()

◆ applyLastVertexBranch()

◆ SCIP_DECL_PROPCOPY()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPINITSOL()

◆ SCIP_DECL_PROPEXITSOL()

◆ SCIPStpFixEdgeVarTo0()

◆ SCIPStpFixEdgeVarTo1()

◆ SCIPStpNfixedEdges()

◆ SCIPStpPropCheckForInfeas()

◆ SCIPStpPropGetGraph()

◆ SCIPStpPropGet2BoundedArr()

◆ SCIPincludePropStp()