Detailed Description

reduced cost routines for extended reduction techniques for Steiner tree problems

Author: Daniel Rehfeldt

This file implements methods for using reduced costs in extended reduction techniques.

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

Definition in file extreduce_redcosts.c.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "graph.h"
#include "portab.h"
#include "extreduce.h"

Go to the source code of this file.

Functions
static SCIP_Real	getTreeRedcosts_dbg (const GRAPH graph, int redcostlevel, const EXTDATA extdata, int root)

static void	sortDescendingIntRealReal (int RESTRICT keyArr, SCIP_Real RESTRICT dataArr1, SCIP_Real *RESTRICT dataArr2, int nentries)

static SCIP_Real	getMinDistCombination (const SCIP_Real firstTermDist, const SCIP_Real secondTermDist, int nentries)

static SCIP_Real	extTreeGetDirectedRedcostProper (const GRAPH graph, int redcostlevel, const EXTDATA extdata, int root)

static SCIP_Real	extTreeGetDirectedRedcost (const GRAPH graph, int redcostlevel, const EXTDATA extdata, const REDDATA *reddata, int root)

static SCIP_Bool	extTreeRedcostCutoff (const GRAPH graph, int redcostlevel, const EXTDATA extdata, const REDDATA *reddata)

void	extreduce_redcostTreeRecompute (SCIP scip, const GRAPH graph, EXTDATA *extdata)

void	extreduce_redcostInitExpansion (const GRAPH graph, EXTDATA extdata)

void	extreduce_redcostAddEdge (const GRAPH graph, int edge, REDDATA reddata, EXTDATA *extdata)

void	extreduce_redcostRemoveEdge (int edge, const REDDATA reddata, EXTDATA extdata)

SCIP_Bool	extreduce_redcostRuleOutPeriph (const GRAPH graph, EXTDATA extdata)

Function Documentation

◆ getTreeRedcosts_dbg()

static SCIP_Real getTreeRedcosts_dbg	(	const GRAPH *	graph,
		int	redcostlevel,
		const EXTDATA *	extdata,
		int	root
	)

static

recomputes simple reduced costs for current tree

Parameters

graph	graph data structure
redcostlevel	the reduced costs level
extdata	extension data
root	the root for the orientation

Definition at line 41 of file extreduce_redcosts.c.

References shortest_path::dist, EAT_LAST, FARAWAY, flipedge, graph_knot_isInRange(), GRAPH::head, LT, GRAPH::oeat, GRAPH::outbeg, extension_data::redcostdata, redcosts_getEdgeCosts(), redcosts_getNodeToTermsPaths(), redcosts_getRootToNodeDist(), SCIP_Real, extension_data::tree_edges, extension_data::tree_leaves, extension_data::tree_nedges, extension_data::tree_nleaves, extension_data::tree_parentNode, and extension_data::tree_root.

Referenced by extTreeRedcostCutoff().

◆ sortDescendingIntRealReal()

static void sortDescendingIntRealReal	(	int *RESTRICT	keyArr,
		SCIP_Real *RESTRICT	dataArr1,
		SCIP_Real *RESTRICT	dataArr2,
		int	nentries
	)

inlinestatic

insertion sort; keyArr has sentinel value at position -1 : do something special: maybe sort index array

Parameters

keyArr	key array of size 'nentries'
dataArr1	array of size 'nentries'
dataArr2	array of size 'nentries'
nentries	number of entries

Definition at line 105 of file extreduce_redcosts.c.

References SCIP_Real.

Referenced by extTreeGetDirectedRedcostProper().

◆ getMinDistCombination()

static SCIP_Real getMinDistCombination	(	const SCIP_Real *	firstTermDist,
		const SCIP_Real *	secondTermDist,
		int	nentries
	)

inlinestatic

helper for rooted tree reduced cost computation

Parameters

firstTermDist	array of size 'nentries'
secondTermDist	array of size 'nentries'
nentries	number of entries to check

Definition at line 175 of file extreduce_redcosts.c.

References EQ, FARAWAY, LE, LT, and SCIP_Real.

Referenced by extTreeGetDirectedRedcostProper().

◆ extTreeGetDirectedRedcostProper()

static SCIP_Real extTreeGetDirectedRedcostProper	(	const GRAPH *	graph,
		int	redcostlevel,
		const EXTDATA *	extdata,
		int	root
	)

inlinestatic

gets reduced cost of current tree rooted at leave 'root'

Parameters

graph	graph data structure
redcostlevel	the reduced costs level
extdata	extension data
root	the root for the orientation

Definition at line 245 of file extreduce_redcosts.c.

References shortest_path::dist, EQ, FARAWAY, GE, getMinDistCombination(), graph_knot_isInRange(), graph_pc_isPcMw(), Is_pseudoTerm, Is_term, GRAPH::knots, LE, LT, nnodes, extension_data::node_isterm, reduction_data::redcost_treecosts, reduction_data::redcost_treenodeswaps, extension_data::redcostdata, redcosts_getNodeToTermsBases(), redcosts_getNodeToTermsPaths(), redcosts_getRootToNodeDist(), extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPdebugMessage, sortDescendingIntRealReal(), STP_EXTTREE_MAXNLEAVES_GUARD, GRAPH::term, extension_data::tree_deg, extension_data::tree_leaves, extension_data::tree_nleaves, and UNKNOWN.

Referenced by extTreeGetDirectedRedcost().

◆ extTreeGetDirectedRedcost()

static SCIP_Real extTreeGetDirectedRedcost	(	const GRAPH *	graph,
		int	redcostlevel,
		const EXTDATA *	extdata,
		const REDDATA *	reddata,
		int	root
	)

inlinestatic

gets reduced cost of current tree rooted at leave 'root'

Parameters

graph	graph data structure
redcostlevel	the reduced costs level
extdata	extension data
reddata	reduction data
root	the root for the orientation

Definition at line 406 of file extreduce_redcosts.c.

References extTreeGetDirectedRedcostProper(), FARAWAY, graph_knot_isInRange(), GRAPH::knots, LT, reduction_data::redcost_treenodeswaps, SCIP_Real, SCIPdebugMessage, STP_EXTTREE_MAXNLEAVES_GUARD, extension_data::tree_leaves, extension_data::tree_nDelUpArcs, extension_data::tree_nleaves, and extension_data::tree_root.

Referenced by extTreeRedcostCutoff().

◆ extTreeRedcostCutoff()

static SCIP_Bool extTreeRedcostCutoff	(	const GRAPH *	graph,
		int	redcostlevel,
		const EXTDATA *	extdata,
		const REDDATA *	reddata
	)

inlinestatic

checks for reduced-cost cutoff of current tree

Parameters

graph	graph data structure
redcostlevel	level
extdata	extension data
reddata	reduction data

Definition at line 446 of file extreduce_redcosts.c.

References EPS_ZERO_HARD, extTreeGetDirectedRedcost(), FALSE, FARAWAY, GE_FEAS_EPS, getTreeRedcosts_dbg(), LE, LT, reduction_data::redcost_allowEquality, extension_data::redcostdata, redcosts_getCutoff(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by extreduce_redcostRuleOutPeriph().

◆ extreduce_redcostTreeRecompute()

void extreduce_redcostTreeRecompute	(	SCIP *	scip,
		const GRAPH *	graph,
		EXTDATA *	extdata
	)

recomputes reduced cost tree information

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 495 of file extreduce_redcosts.c.

References reduction_data::edgedeleted, GRAPH::edges, extreduce_treeIsFlawed(), FARAWAY, graph_edge_isInRange(), LT, reduction_data::redcost_nlevels, reduction_data::redcost_treecosts, extension_data::redcostdata, redcosts_getEdgeCosts(), redcosts_getNedges(), extension_data::reddata, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPallocBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPisEQ(), extension_data::tree_edges, and extension_data::tree_nedges.

Referenced by extreduce_treeRecompCosts().

◆ extreduce_redcostInitExpansion()

void extreduce_redcostInitExpansion	(	const GRAPH *	graph,
		EXTDATA *	extdata
	)

NOTE: call before adding edges for new expansion!

Parameters

graph	graph data structure
extdata	extension data

Definition at line 548 of file extreduce_redcosts.c.

References extStackGetTopRoot(), FARAWAY, GE, GRAPH::knots, nnodes, reduction_data::redcost_nlevels, reduction_data::redcost_noReversedTree, reduction_data::redcost_treenodeswaps, extension_data::redcostdata, redcosts_getRoot(), extension_data::reddata, SCIP_Bool, SCIP_Real, and extension_data::tree_root.

Referenced by extTreeStackTopAdd().

◆ extreduce_redcostAddEdge()

void extreduce_redcostAddEdge	(	const GRAPH *	graph,
		int	edge,
		REDDATA *	reddata,
		EXTDATA *	extdata
	)

Updates reduced cost for added edge. NOTE: call extreduce_redcostInitExpansion before each new expansion!

Parameters

graph	graph data structure
edge	edge to be added
reddata	reduction data
extdata	extension data

Definition at line 571 of file extreduce_redcosts.c.

References reduction_data::edgedeleted, GRAPH::edges, extIsAtInitialGenStar(), extIsAtInitialStar(), FARAWAY, flipedge, GRAPH::head, GRAPH::knots, LT, nnodes, reduction_data::redcost_nlevels, reduction_data::redcost_noReversedTree, reduction_data::redcost_treecosts, reduction_data::redcost_treenodeswaps, extension_data::redcostdata, redcosts_getEdgeCosts(), redcosts_getNedges(), redcosts_getNnodes(), SCIP_Bool, SCIP_Real, GRAPH::tail, extension_data::tree_nDelUpArcs, extension_data::tree_starcenter, and TRUE.

Referenced by extTreeStackTopAdd().

◆ extreduce_redcostRemoveEdge()

void extreduce_redcostRemoveEdge	(	int	edge,
		const REDDATA *	reddata,
		EXTDATA *	extdata
	)

update reduced cost for removed edge

Parameters

edge	edge to be added
reddata	reduction data
extdata	extension data

Definition at line 635 of file extreduce_redcosts.c.

References reduction_data::edgedeleted, FARAWAY, LT, reduction_data::redcost_nlevels, reduction_data::redcost_treecosts, extension_data::redcostdata, redcosts_getEdgeCosts(), redcosts_getNedges(), SCIP_Bool, SCIP_Real, and extension_data::tree_nDelUpArcs.

Referenced by extTreeStackTopRemove().

◆ extreduce_redcostRuleOutPeriph()

SCIP_Bool extreduce_redcostRuleOutPeriph	(	const GRAPH *	graph,
		EXTDATA *	extdata
	)

Can current tree be peripherally ruled out by using reduced costs arguments?

Parameters

graph	graph data structure
extdata	extension data

Definition at line 665 of file extreduce_redcosts.c.

References extTreeRedcostCutoff(), FALSE, reduction_data::redcost_nlevels, extension_data::reddata, extension_data::tree_leaves, extension_data::tree_nleaves, extension_data::tree_root, and TRUE.

Referenced by extTreeRuleOutPeriph().

SCIP

Detailed Description

Functions

Function Documentation

◆ getTreeRedcosts_dbg()

◆ sortDescendingIntRealReal()

◆ getMinDistCombination()

◆ extTreeGetDirectedRedcostProper()

◆ extTreeGetDirectedRedcost()

◆ extTreeRedcostCutoff()

◆ extreduce_redcostTreeRecompute()

◆ extreduce_redcostInitExpansion()

◆ extreduce_redcostAddEdge()

◆ extreduce_redcostRemoveEdge()

◆ extreduce_redcostRuleOutPeriph()