redcosts.c File Reference

Detailed Description

Reduced cost based routines for Steiner problems.

Author

Daniel Rehfeldt

This file encompasses various routines for reduced costs based computations

Definition in file redcosts.c.

#include "redcosts.h"
#include "graph.h"
#include "portab.h"

Go to the source code of this file.

Data Structures
struct	reduce_costs_data

Functions
Local methods
static SCIP_RETCODE	initFromParams (SCIP *scip, const RCPARAMS *parameters, REDCOST **redcostdata)
static int	getTopLevel (const REDCOST *redcostdata)
static SCIP_Bool	levelIsValid (const REDCOST *redcostdata, int level)
static int	getStartPositionCloseTerms (const REDCOST *redcostdata, int level)
Interface methods
int	redcosts_getNnodes (const REDCOST *redcostdata)
int	redcosts_getNedges (const REDCOST *redcostdata)
SCIP_Real *	redcosts_getEdgeCosts (const REDCOST *redcostdata, int level)
SCIP_Real *	redcosts_getEdgeCostsTop (const REDCOST *redcostdata)
SCIP_Real *	redcosts_getRootToNodeDist (const REDCOST *redcostdata, int level)
SCIP_Real *	redcosts_getRootToNodeDistTop (const REDCOST *redcostdata)
PATH *	redcosts_getNodeToTermsPaths (const REDCOST *redcostdata, int level)
PATH *	redcosts_getNodeToTermsPathsTop (const REDCOST *redcostdata)
int *	redcosts_getNodeToTermsBases (const REDCOST *redcostdata, int level)
int *	redcosts_getNodeToTermsBasesTop (const REDCOST *redcostdata)
SCIP_Real	redcosts_getCutoff (const REDCOST *redcostdata, int level)
SCIP_Real	redcosts_getCutoffTop (const REDCOST *redcostdata)
SCIP_Real	redcosts_getDualBound (int level, const REDCOST *redcostdata)
SCIP_Real	redcosts_getDualBoundTop (const REDCOST *redcostdata)
int	redcosts_getRoot (const REDCOST *redcostdata, int level)
int	redcosts_getRootTop (const REDCOST *redcostdata)
int	redcosts_getLevel (const REDCOST *redcostdata)
int	redcosts_getNlevels (const REDCOST *redcostdata)
void	redcosts_setCutoff (SCIP_Real cutoff, int level, REDCOST *redcostdata)
void	redcosts_setCutoffTop (SCIP_Real cutoff, REDCOST *redcostdata)
void	redcosts_setDualBound (SCIP_Real dualbound, int level, REDCOST *redcostdata)
void	redcosts_setDualBoundTop (SCIP_Real dualbound, REDCOST *redcostdata)
void	redcosts_setRoot (int root, int level, REDCOST *redcostdata)
void	redcosts_setRootTop (int root, REDCOST *redcostdata)
void	redcosts_addLevel (REDCOST *redcostdata)
SCIP_RETCODE	redcosts_initializeDistances (SCIP *scip, int level, GRAPH *g, REDCOST *redcostdata)
SCIP_RETCODE	redcosts_initializeDistancesTop (SCIP *scip, GRAPH *g, REDCOST *redcostdata)
SCIP_RETCODE	redcosts_initFromParams (SCIP *scip, const RCPARAMS *parameters, REDCOST **redcostdata)
SCIP_RETCODE	redcosts_init (SCIP *scip, int nnodes, int nedges, SCIP_Real cutoff, int redCostRoot, REDCOST **redcostdata)
void	redcosts_setAndReturnCutoffFromBoundTop (SCIP_Real upperbound, REDCOST *redcostdata, SCIP_Real *cutoffbound)
void	redcosts_setCutoffFromBound (SCIP_Real upperbound, int level, REDCOST *redcostdata)
void	redcosts_setCutoffFromBoundTop (SCIP_Real upperbound, REDCOST *redcostdata)
void	redcosts_increaseOnDeletedArcs (const GRAPH *graph, const STP_Bool *arcsdeleted, int level, REDCOST *redcostdata)
void	redcosts_unifyBlockedEdgeCosts (const GRAPH *graph, int level, REDCOST *redcostdata)
void	redcosts_increaseOnDeletedArcsTop (const GRAPH *graph, const STP_Bool *arcsdeleted, REDCOST *redcostdata)
void	redcosts_free (SCIP *scip, REDCOST **redcostdata)
SCIP_Bool	redcosts_forLPareAvailable (SCIP *scip)
SCIP_Bool	redcosts_forLPareReliable (SCIP *scip, SCIP_VAR **vars, const GRAPH *graph)
void	redcosts_forLPget (SCIP *scip, SCIP_VAR **vars, const GRAPH *graph, SCIP_Real *redcosts)

Function Documentation

initFromParams()

static SCIP_RETCODE initFromParams ( SCIP *  scip, const RCPARAMS *  parameters, REDCOST **  redcostdata  )

static

initializes reduced costs data structure from given parameter struct

Parameters

scip	SCIP
parameters	parameters for initialization
redcostdata	data to initialize

Definition at line 58 of file redcosts.c.

References reduced_costs_parameters::cutoff, EQ, GE, reduce_costs_data::lvl_cutoff, reduce_costs_data::lvl_dualBound, reduce_costs_data::lvl_nodeToTermsBases, reduce_costs_data::lvl_nodeToTermsPaths, reduce_costs_data::lvl_redCostRoot, reduce_costs_data::lvl_redEdgeCost, reduce_costs_data::lvl_rootToNodeDist, reduce_costs_data::nCloseTerms, reduced_costs_parameters::nCloseTerms, reduce_costs_data::nedges, reduced_costs_parameters::nedges, reduced_costs_parameters::nLevels, reduce_costs_data::nLevelsMax, reduce_costs_data::nnodes, reduced_costs_parameters::nnodes, reduced_costs_parameters::redCostRoot, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemory, SCIPallocMemoryArray, reduce_costs_data::toplevel, and UNKNOWN.

Referenced by redcosts_initFromParams().

getTopLevel()

static int getTopLevel ( const REDCOST *  redcostdata )

inlinestatic

returns top level

Parameters

redcostdata

reduced costs data

Definition at line 113 of file redcosts.c.

References reduce_costs_data::nLevelsMax, and reduce_costs_data::toplevel.

Referenced by levelIsValid(), redcosts_getCutoffTop(), redcosts_getDualBoundTop(), redcosts_getEdgeCostsTop(), redcosts_getLevel(), redcosts_getNlevels(), redcosts_getNodeToTermsBasesTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), redcosts_getRootTop(), redcosts_increaseOnDeletedArcsTop(), redcosts_initializeDistancesTop(), redcosts_setCutoffFromBoundTop(), redcosts_setCutoffTop(), redcosts_setDualBoundTop(), and redcosts_setRootTop().

levelIsValid()

static SCIP_Bool levelIsValid ( const REDCOST *  redcostdata, int  level  )

static

Parameters

redcostdata	reduced costs data
level	the level

Definition at line 126 of file redcosts.c.

References getTopLevel(), and reduce_costs_data::toplevel.

Referenced by getStartPositionCloseTerms(), redcosts_getCutoff(), redcosts_getDualBound(), redcosts_getEdgeCosts(), redcosts_getRoot(), redcosts_getRootToNodeDist(), redcosts_setCutoff(), redcosts_setCutoffFromBound(), redcosts_setDualBound(), and redcosts_setRoot().

getStartPositionCloseTerms()

static int getStartPositionCloseTerms ( const REDCOST *  redcostdata, int  level  )

static

returns start position of given level for lvl_nodeToTermsPaths and lvl_nodeToTermsBases

Parameters

redcostdata	reduced costs data
level	the level

Definition at line 140 of file redcosts.c.

References levelIsValid(), reduce_costs_data::nCloseTerms, and reduce_costs_data::nnodes.

Referenced by redcosts_getNodeToTermsBases(), and redcosts_getNodeToTermsPaths().

redcosts_getNnodes()

int redcosts_getNnodes

(

const REDCOST *

redcostdata

)

returns number of nodes for which reduced costs are stored

Parameters

redcostdata

reduced costs data

Definition at line 165 of file redcosts.c.

References reduce_costs_data::nnodes.

Referenced by extInitRedCostArrays(), and extreduce_redcostAddEdge().

redcosts_getNedges()

int redcosts_getNedges

(

const REDCOST *

redcostdata

)

returns number of edges for which reduced costs are stored

Parameters

redcostdata

reduced costs data

Definition at line 176 of file redcosts.c.

References reduce_costs_data::nedges.

Referenced by extInitRedCostArrays(), extreduce_redcostAddEdge(), extreduce_redcostRemoveEdge(), and extreduce_redcostTreeRecompute().

redcosts_getEdgeCosts()

SCIP_Real* redcosts_getEdgeCosts	(	const REDCOST *	redcostdata,
		int	level
	)

returns reduced costs

Parameters

redcostdata	reduced costs data
level	level to get reduced costs for

Definition at line 187 of file redcosts.c.

References levelIsValid(), reduce_costs_data::lvl_redEdgeCost, and reduce_costs_data::nedges.

Referenced by delPseudoDeleteVertex(), delPseudoInit(), extreduce_redcostAddEdge(), extreduce_redcostRemoveEdge(), extreduce_redcostTreeRecompute(), getTreeRedcosts_dbg(), redcosts_getEdgeCostsTop(), redcosts_increaseOnDeletedArcs(), redcosts_initializeDistances(), redcosts_unifyBlockedEdgeCosts(), and writeRedcostdata().

redcosts_getEdgeCostsTop()

SCIP_Real* redcosts_getEdgeCostsTop

(

const REDCOST *

redcostdata

)

returns top level reduced costs

Parameters

redcostdata

reduced costs data

Definition at line 202 of file redcosts.c.

References getTopLevel(), redcosts_getEdgeCosts(), and reduce_costs_data::toplevel.

Referenced by computeDualSolution(), computeDualSolutionGuided(), computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsDirected(), dapathsFixPotTerms(), extInitRedCostArrays(), extreduce_checkArc(), extreduce_edgeIsValid(), fixVarsExtendedRed(), reduce_applyPseudoDeletions(), reduce_da(), reduce_dapaths(), reduceRootedProb(), replaceEdgeByPath(), termcompDeleteEdges(), termcompReduceWithParams(), testEdgeDeletedByMultiRedCosts(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testNode3PseudoDeletedByRedCosts1(), and updateNodeReplaceBounds().

redcosts_getRootToNodeDist()

SCIP_Real* redcosts_getRootToNodeDist	(	const REDCOST *	redcostdata,
		int	level
	)

returns root to node distances

Parameters

redcostdata	reduced costs data
level	level to get distances for

Definition at line 213 of file redcosts.c.

References levelIsValid(), reduce_costs_data::lvl_rootToNodeDist, and reduce_costs_data::nnodes.

Referenced by extTreeGetDirectedRedcostProper(), getTreeRedcosts_dbg(), redcosts_getRootToNodeDistTop(), and redcosts_initializeDistances().

redcosts_getRootToNodeDistTop()

SCIP_Real* redcosts_getRootToNodeDistTop

(

const REDCOST *

redcostdata

)

returns root to node distances for top level

Parameters

redcostdata

reduced costs data

Definition at line 228 of file redcosts.c.

References getTopLevel(), redcosts_getRootToNodeDist(), and reduce_costs_data::toplevel.

Referenced by extInitRedCostArrays(), extreduce_checkArc(), fixVarsExtendedRed(), reduce_applyPseudoDeletions(), reduce_da(), reduceRootedProb(), termcompDeleteEdges(), termcompMarkPseudoDelNodes(), and updateNodeReplaceBounds().

redcosts_getNodeToTermsPaths()

PATH* redcosts_getNodeToTermsPaths	(	const REDCOST *	redcostdata,
		int	level
	)

returns paths from nodes to closes terms

Parameters

redcostdata	reduced costs data
level	level to get reduced costs for

Definition at line 240 of file redcosts.c.

References getStartPositionCloseTerms(), and reduce_costs_data::lvl_nodeToTermsPaths.

Referenced by extTreeGetDirectedRedcostProper(), getTreeRedcosts_dbg(), redcosts_getNodeToTermsPathsTop(), and redcosts_initializeDistances().

redcosts_getNodeToTermsPathsTop()

PATH* redcosts_getNodeToTermsPathsTop

(

const REDCOST *

redcostdata

)

returns paths from nodes to closes terms for top level

Parameters

redcostdata

reduced costs data

Definition at line 253 of file redcosts.c.

References getTopLevel(), redcosts_getNodeToTermsPaths(), and reduce_costs_data::toplevel.

Referenced by extInitRedCostArrays(), extreduce_checkArc(), fixVarsExtendedRed(), reduce_applyPseudoDeletions(), reduce_da(), reduceRootedProb(), termcompDeleteEdges(), termcompMarkPseudoDelNodes(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletion3_deprecated(), and updateNodeReplaceBounds().

redcosts_getNodeToTermsBases()

int* redcosts_getNodeToTermsBases	(	const REDCOST *	redcostdata,
		int	level
	)

returns closest terminals to nodes

Parameters

redcostdata	reduced costs data
level	level to terminals for

Definition at line 264 of file redcosts.c.

References getStartPositionCloseTerms(), and reduce_costs_data::lvl_nodeToTermsBases.

Referenced by extTreeGetDirectedRedcostProper(), redcosts_getNodeToTermsBasesTop(), and redcosts_initializeDistances().

redcosts_getNodeToTermsBasesTop()

int* redcosts_getNodeToTermsBasesTop

(

const REDCOST *

redcostdata

)

returns closest terms to nodes for top level

Parameters

redcostdata

reduced costs data

Definition at line 277 of file redcosts.c.

References getTopLevel(), redcosts_getNodeToTermsBases(), and reduce_costs_data::toplevel.

Referenced by extInitRedCostArrays(), extInitRedCostArraysPc(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletion3_deprecated(), and updateNodeReplaceBounds().

redcosts_getCutoff()

SCIP_Real redcosts_getCutoff	(	const REDCOST *	redcostdata,
		int	level
	)

returns cutoff

Parameters

redcostdata	reduced costs data
level	level to get cutoff for

Definition at line 288 of file redcosts.c.

References levelIsValid(), and reduce_costs_data::lvl_cutoff.

Referenced by extTreeRedcostCutoff(), fixVarsExtendedRed(), fixVarsRedbased(), redcosts_getCutoffTop(), redcosts_increaseOnDeletedArcs(), redcosts_unifyBlockedEdgeCosts(), and reduceWithEdgeExtReds().

redcosts_getCutoffTop()

SCIP_Real redcosts_getCutoffTop

(

const REDCOST *

redcostdata

)

returns cutoff for top level

Parameters

redcostdata

reduced costs data

Definition at line 300 of file redcosts.c.

References getTopLevel(), redcosts_getCutoff(), and reduce_costs_data::toplevel.

Referenced by dapathsFixPotTerms(), extreduce_checkArc(), extreduce_deleteArcs(), extreduce_deleteEdges(), extreduce_deleteGeneralStars(), extreduce_pseudoDeleteNodes(), fixVarsExtendedRed(), reduce_applyPseudoDeletions(), reduceRootedProb(), termcompDeleteEdges(), and termcompMarkPseudoDelNodes().

redcosts_getDualBound()

SCIP_Real redcosts_getDualBound	(	int	level,
		const REDCOST *	redcostdata
	)

returns dual-bound

Parameters

level	level
redcostdata	reduced costs data

Definition at line 311 of file redcosts.c.

References levelIsValid(), and reduce_costs_data::lvl_dualBound.

Referenced by redcosts_getDualBoundTop(), and redcosts_setCutoffFromBound().

redcosts_getDualBoundTop()

SCIP_Real redcosts_getDualBoundTop

(

const REDCOST *

redcostdata

)

returns dual-bound for top level

Parameters

redcostdata

reduced costs data

Definition at line 324 of file redcosts.c.

References getTopLevel(), redcosts_getDualBound(), and reduce_costs_data::toplevel.

Referenced by redcosts_setAndReturnCutoffFromBoundTop(), reduce_da(), and updateNodeReplaceBounds().

redcosts_getRoot()

int redcosts_getRoot	(	const REDCOST *	redcostdata,
		int	level
	)

returns root used for reduced cost computation

Parameters

redcostdata	reduced costs data
level	level to get root for

Definition at line 335 of file redcosts.c.

References levelIsValid(), and reduce_costs_data::lvl_redCostRoot.

Referenced by extreduce_redcostInitExpansion(), redcosts_getRootTop(), and redcosts_initializeDistances().

redcosts_getRootTop()

int redcosts_getRootTop

(

const REDCOST *

redcostdata

)

returns root used for reduced cost computation for to level

Parameters

redcostdata

reduced costs data

Definition at line 347 of file redcosts.c.

References getTopLevel(), redcosts_getRoot(), and reduce_costs_data::toplevel.

Referenced by computeDualSolution(), computeDualSolutionGuided(), computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsDirected(), extreduce_checkArc(), extreduce_deleteEdges(), extreduce_deleteGeneralStars(), graphmarkIsClean(), and updateNodeReplaceBounds().

redcosts_getLevel()

int redcosts_getLevel

(

const REDCOST *

redcostdata

)

returns current (top) level; 0-indexed

Parameters

redcostdata

reduced costs data

Definition at line 358 of file redcosts.c.

References getTopLevel(), and reduce_costs_data::toplevel.

Referenced by updateRedcostdata().

redcosts_getNlevels()

int redcosts_getNlevels

(

const REDCOST *

redcostdata

)

returns current number of levels

Parameters

redcostdata

reduced costs data

Definition at line 369 of file redcosts.c.

References getTopLevel(), and reduce_costs_data::toplevel.

Referenced by delPseudoDeleteVertex(), delPseudoInit(), extreduce_checkComponent(), fixVarsExtendedRed(), fixVarsRedbased(), reduceWithEdgeExtReds(), and updateRedcostdata().

redcosts_setCutoff()

void redcosts_setCutoff	(	SCIP_Real	cutoff,
		int	level,
		REDCOST *	redcostdata
	)

sets cutoff

Parameters

cutoff	the value
level	level to set cutoff for
redcostdata	reduced costs data

Definition at line 380 of file redcosts.c.

References GE, levelIsValid(), and reduce_costs_data::lvl_cutoff.

Referenced by redcosts_setCutoffFromBound(), redcosts_setCutoffTop(), and writeRedcostdata().

redcosts_setCutoffTop()

void redcosts_setCutoffTop	(	SCIP_Real	cutoff,
		REDCOST *	redcostdata
	)

sets cutoff for top level

Parameters

cutoff	the value
redcostdata	reduced costs data

Definition at line 394 of file redcosts.c.

References getTopLevel(), redcosts_setCutoff(), and reduce_costs_data::toplevel.

Referenced by redcosts_setAndReturnCutoffFromBoundTop(), and testEdgeDeletedByMultiRedCosts().

redcosts_setDualBound()

void redcosts_setDualBound	(	SCIP_Real	dualbound,
		int	level,
		REDCOST *	redcostdata
	)

sets dual-bound

Parameters

dualbound	the value
level	level to set dual bound for
redcostdata	reduced costs data

Definition at line 406 of file redcosts.c.

References GE, levelIsValid(), and reduce_costs_data::lvl_dualBound.

Referenced by redcosts_setDualBoundTop(), and writeRedcostdata().

redcosts_setDualBoundTop()

void redcosts_setDualBoundTop	(	SCIP_Real	dualbound,
		REDCOST *	redcostdata
	)

sets dual-bound

Parameters

dualbound	the value
redcostdata	reduced costs data

Definition at line 420 of file redcosts.c.

References GE, getTopLevel(), redcosts_setDualBound(), and reduce_costs_data::toplevel.

Referenced by computeDualSolution(), computeDualSolutionGuided(), reduce_dapaths(), and termcompReduceWithParams().

redcosts_setRoot()

void redcosts_setRoot	(	int	root,
		int	level,
		REDCOST *	redcostdata
	)

sets root used for reduced cost computation

Parameters

root	the root
level	level to set dual bound for
redcostdata	reduced costs data

Definition at line 433 of file redcosts.c.

References levelIsValid(), and reduce_costs_data::lvl_redCostRoot.

Referenced by redcosts_setRootTop(), and writeRedcostdata().

redcosts_setRootTop()

void redcosts_setRootTop	(	int	root,
		REDCOST *	redcostdata
	)

sets root used for reduced cost computation

Parameters

root	the root
redcostdata	reduced costs data

Definition at line 447 of file redcosts.c.

References getTopLevel(), redcosts_setRoot(), and reduce_costs_data::toplevel.

Referenced by reduce_da(), and testEdgeDeletedByMultiRedCosts().

redcosts_addLevel()

void redcosts_addLevel

(

REDCOST *

redcostdata

)

adds a new level

Parameters

redcostdata

reduced costs data

Definition at line 460 of file redcosts.c.

References reduce_costs_data::nLevelsMax, and reduce_costs_data::toplevel.

Referenced by reduce_da(), testEdgeDeletedByMultiRedCosts(), and updateRedcostdata().

redcosts_initializeDistances()

SCIP_RETCODE redcosts_initializeDistances	(	SCIP *	scip,
		int	level,
		GRAPH *	g,
		REDCOST *	redcostdata
	)

Parameters

scip	SCIP
level	level to inizialize for
g	graph data structure
redcostdata	reduced cost data

Definition at line 473 of file redcosts.c.

References EAT_LAST, GRAPH::extended, FARAWAY, flipedge, graph_add1stTermPaths(), graph_get2nextTermPaths(), graph_get3nextTermPaths(), graph_get_nEdges(), graph_get_nNodes(), graph_isMarked(), graph_mark(), graph_path_execX(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isRootedPcMw(), Is_term, GRAPH::mark, reduce_costs_data::nCloseTerms, reduce_costs_data::nedges, reduce_costs_data::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, redcosts_getEdgeCosts(), redcosts_getNodeToTermsBases(), redcosts_getNodeToTermsPaths(), redcosts_getRoot(), redcosts_getRootToNodeDist(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, STP_NWSPG, STP_SAP, GRAPH::stp_type, and GRAPH::term.

Referenced by fixVarsExtendedRed(), fixVarsRedbased(), and redcosts_initializeDistancesTop().

redcosts_initializeDistancesTop()

SCIP_RETCODE redcosts_initializeDistancesTop	(	SCIP *	scip,
		GRAPH *	g,
		REDCOST *	redcostdata
	)

Parameters

scip	SCIP
g	graph data structure
redcostdata	reduced cost data

Definition at line 573 of file redcosts.c.

References getTopLevel(), redcosts_initializeDistances(), SCIP_CALL, SCIP_OKAY, and reduce_costs_data::toplevel.

Referenced by daRoundInit(), reduce_dapaths(), termcompReduceWithParams(), and testEdgeDeletedByMultiRedCosts().

redcosts_initFromParams()

SCIP_RETCODE redcosts_initFromParams	(	SCIP *	scip,
		const RCPARAMS *	parameters,
		REDCOST **	redcostdata
	)

initializes reduced costs data structure from given parameter struct

Parameters

scip	SCIP
parameters	parameters for initialization
redcostdata	data to initialize

Definition at line 590 of file redcosts.c.

References initFromParams(), SCIP_CALL, and SCIP_OKAY.

Referenced by daRedcostsInit(), initRedcostdata(), redcosts_init(), termcompReduceWithParams(), and testEdgeDeletedByMultiRedCosts().

redcosts_init()

SCIP_RETCODE redcosts_init	(	SCIP *	scip,
		int	nnodes,
		int	nedges,
		SCIP_Real	cutoff,
		int	redCostRoot,
		REDCOST **	redcostdata
	)

initializes reduced costs data structure

Parameters

scip	SCIP
nnodes	number of nodes
nedges	number of edges
cutoff	reduced cost cutoff value or -1.0 if not used
redCostRoot	graph root for reduced cost calculation
redcostdata	data to initialize

Definition at line 605 of file redcosts.c.

References reduced_costs_parameters::cutoff, reduce_costs_data::nedges, reduce_costs_data::nnodes, redcosts_initFromParams(), SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_dapaths(), testEdgeDeletedBy3LeafSpg(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletedByEqBottleneck(), testEdgeDeletedByEqBottleneck2(), testEdgeDeletedByMst1(), testEdgeDeletedByMst2(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testEdgeNotDeleted1(), testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), testGeneralStarDeletedEdge3(), testNode3PseudoDeletedByContraction(), testNode3PseudoDeletedByRedCosts1(), testNode3PseudoDeletedBySd1(), testNode3PseudoDeletedBySd2(), testNode3PseudoDeletedBySd3(), testNode3PseudoDeletedBySdBiased(), testNode3PseudoDeletedBySdBiasedSimple(), testNode4PseudoDeletedBySd1(), testNode4PseudoNotDeletedBySd1(), testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), and testPcNode4PseudoDeletedBySd1().

redcosts_setAndReturnCutoffFromBoundTop()

void redcosts_setAndReturnCutoffFromBoundTop	(	SCIP_Real	upperbound,
		REDCOST *	redcostdata,
		SCIP_Real *	cutoffbound
	)

sets cutoff

Parameters

upperbound	bound
redcostdata	reduced cost data
cutoffbound	cutoff

Definition at line 624 of file redcosts.c.

References EPSILON, GE, GE_FEAS_EPS, redcosts_getDualBoundTop(), and redcosts_setCutoffTop().

Referenced by daRoundInit().

redcosts_setCutoffFromBound()

void redcosts_setCutoffFromBound	(	SCIP_Real	upperbound,
		int	level,
		REDCOST *	redcostdata
	)

sets cutoff

Parameters

upperbound	bound
level	level
redcostdata	reduced cost data

Definition at line 645 of file redcosts.c.

References EPSILON, GE, GE_FEAS_EPS, levelIsValid(), redcosts_getDualBound(), redcosts_setCutoff(), and SCIP_Real.

Referenced by fixVarsExtendedRed(), fixVarsRedbased(), redcosts_setCutoffFromBoundTop(), and reduceWithEdgeExtReds().

redcosts_setCutoffFromBoundTop()

void redcosts_setCutoffFromBoundTop	(	SCIP_Real	upperbound,
		REDCOST *	redcostdata
	)

sets cutoff for top level

Parameters

upperbound	bound
redcostdata	reduced cost data

Definition at line 670 of file redcosts.c.

References getTopLevel(), redcosts_setCutoffFromBound(), and reduce_costs_data::toplevel.

Referenced by reduce_dapaths(), and termcompReduceWithParams().

redcosts_increaseOnDeletedArcs()

void redcosts_increaseOnDeletedArcs	(	const GRAPH *	graph,
		const STP_Bool *	arcsdeleted,
		int	level,
		REDCOST *	redcostdata
	)

increases reduced cost for deleted arcs

Parameters

graph	graph
arcsdeleted	array to mark deleted arcs
level	the level
redcostdata	reduced cost data

Definition at line 682 of file redcosts.c.

References GE, graph_get_nEdges(), reduce_costs_data::nedges, redcosts_getCutoff(), redcosts_getEdgeCosts(), and SCIP_Real.

Referenced by fixVarsExtendedRed(), and redcosts_increaseOnDeletedArcsTop().

redcosts_unifyBlockedEdgeCosts()

void redcosts_unifyBlockedEdgeCosts	(	const GRAPH *	graph,
		int	level,
		REDCOST *	redcostdata
	)

unifies costs

Parameters

graph	graph
level	the level
redcostdata	reduced cost data

Definition at line 705 of file redcosts.c.

References bound, FARAWAY, GE, graph_get_nEdges(), LT, reduce_costs_data::nedges, redcosts_getCutoff(), redcosts_getEdgeCosts(), and SCIP_Real.

Referenced by fixVarsExtendedRed(), and fixVarsRedbased().

redcosts_increaseOnDeletedArcsTop()

void redcosts_increaseOnDeletedArcsTop	(	const GRAPH *	graph,
		const STP_Bool *	arcsdeleted,
		REDCOST *	redcostdata
	)

increases reduced cost for deleted arcs for top level

Parameters

graph	graph
arcsdeleted	array to mark deleted arcs
redcostdata	reduced cost data

Definition at line 728 of file redcosts.c.

References getTopLevel(), redcosts_increaseOnDeletedArcs(), and reduce_costs_data::toplevel.

Referenced by reduce_da().

redcosts_free()

void redcosts_free	(	SCIP *	scip,
		REDCOST **	redcostdata
	)

frees

Parameters

scip	SCIP
redcostdata	data

Definition at line 743 of file redcosts.c.

References reduce_costs_data::lvl_cutoff, reduce_costs_data::lvl_dualBound, reduce_costs_data::lvl_nodeToTermsBases, reduce_costs_data::lvl_nodeToTermsPaths, reduce_costs_data::lvl_redCostRoot, reduce_costs_data::lvl_redEdgeCost, reduce_costs_data::lvl_rootToNodeDist, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by daRedcostsExit(), reduce_dapaths(), SCIP_DECL_PROPEXITSOL(), stptest_extreduceTearDown(), and termcompReduceWithParams().

redcosts_forLPareAvailable()

SCIP_Bool redcosts_forLPareAvailable

(

SCIP *

scip

)

reduced costs available?

Parameters

scip	SCIP structure

Definition at line 767 of file redcosts.c.

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

Referenced by SCIP_DECL_HEUREXEC(), and SCIP_DECL_PROPEXEC().

redcosts_forLPareReliable()

SCIP_Bool redcosts_forLPareReliable	(	SCIP *	scip,
		SCIP_VAR **	vars,
		const GRAPH *	graph
	)

are reduced costs reliable?

Parameters

scip	SCIP structure
vars	variables (in)
graph	graph data

Definition at line 814 of file redcosts.c.

References FALSE, graph_get_nEdges(), reduce_costs_data::nedges, NULL, SCIPgetSolVal(), SCIPgetVarRedcost(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and TRUE.

Referenced by fixVarsDualcost().

redcosts_forLPget()

void redcosts_forLPget	(	SCIP *	scip,
		SCIP_VAR **	vars,
		const GRAPH *	graph,
		SCIP_Real *	redcosts
	)

initialize reduced costs

Parameters

scip	SCIP structure
vars	variables (in)
graph	graph data
redcosts	reduced costs (out)

Definition at line 861 of file redcosts.c.

References GRAPH::cost, EQ, FARAWAY, flipedge, graph_get_nEdges(), graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, reduce_costs_data::nedges, reduce_costs_data::nnodes, NULL, SCIPgetSolVal(), SCIPgetVarRedcost(), SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), GRAPH::source, and GRAPH::term2edge.

Referenced by fixVarsDualcost(), SCIP_DECL_HEUREXEC(), and writeRedcostdata().