reduce_da.c File Reference

Detailed Description

dual-ascent based reductions for Steiner tree problems

Author

Daniel Rehfeldt

This file implements dual-ascent based techniques for several Steiner problems.

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

Definition in file reduce_da.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"
#include "extreduce.h"
#include "heur_tm.h"
#include "heur_ascendprune.h"
#include "heur_lurkprune.h"
#include "heur_slackprune.h"
#include "heur_local.h"
#include "heur_rec.h"
#include "solpool.h"
#include "solstp.h"
#include "dualascent.h"
#include "probdata_stp.h"

Go to the source code of this file.

Macros
#define	BND_TMHEUR_NRUNS   100
#define	BND_TMHEUR_NRUNS_RESTRICT   16
#define	BND_TMHEUR_NRUNS_RPC   16
#define	DEFAULT_DARUNS_DIRECTED   3
#define	DEFAULT_DARUNS   8
#define	DEFAULT_DARUNS_FAST   4
#define	DEFAULT_NMAXROOTS   8
#define	SOLPOOL_SIZE   20
#define	DARUNS_TERMRATIO_LOW   0.05
#define	DARUNS_TERMRATIO_MED   0.075
#define	DARUNS_TERMRATIO_HIGH   0.1
#define	DARUNS_TERMRATIO_HUGE   0.2
#define	STP_RED_MINBNDTERMS   750
#define	STP_DABD_MAXDEGREE   5
#define	STP_DABD_MAXDNEDGES   10
#define	DAMAXDEVIATION_RANDOM_LOWER   0.20
#define	DAMAXDEVIATION_RANDOM_UPPER   0.30
#define	DAMAXDEVIATION_FAST   0.75

Functions
static SCIP_Real	getSolObj (SCIP *scip, const GRAPH *g, const int *soledge)
static SCIP_RETCODE	computeDualSolutionGuided (SCIP *scip, GRAPH *graph, SCIP_Real damaxdeviation, REDCOST *redcostdata, int *result)
static SCIP_RETCODE	computeDualSolution (SCIP *scip, GRAPH *graph, SCIP_Real damaxdeviation, REDCOST *redcostdata)
static SCIP_RETCODE	computeSteinerTreeTM (SCIP *scip, GRAPH *graph, int *result, SCIP_Real *bestobjval, SCIP_Bool *success)
static SCIP_RETCODE	computeSteinerTreeRedCosts (SCIP *scip, GRAPH *graph, const REDCOST *redcostdata, SCIP_Bool useSlackPrune, SCIP_Bool useRec, STPSOLPOOL *pool, int *result, int *bestresult, SCIP_Bool *havebestsol, SCIP_Real *bestobjval)
static SCIP_RETCODE	computeSteinerTreeRedCostsDirected (SCIP *scip, GRAPH *graph, const REDCOST *redcostdata, int *result, int *bestresult, SCIP_Bool *havebestsol, SCIP_Real *bestobjval)
static SCIP_RETCODE	computeSteinerTreeRedCostsPcMw (SCIP *scip, GRAPH *graph, STPSOLPOOL *pool, const SCIP_Real *cost, SCIP_Real *upperbound, int *result1, int *result2, int *pathedge, STP_Bool *nodearrchar, SCIP_Bool *apsol)
static void	collectFixedTerminals (const GRAPH *graph, int *terminals, int *nterms)
static void	updateNodeFixingBounds (SCIP_Real *fixingbounds, const GRAPH *graph, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real lpobjval, SCIP_Bool initialize)
static SCIP_RETCODE	updateNodeReplaceBounds (SCIP *scip, const REDCOST *redcostdata, const GRAPH *graph, SCIP_Real *replacebounds, SCIP_Real upperbound, SCIP_Bool initialize, SCIP_Bool extendedsearch)
static void	updateEdgeFixingBounds (SCIP_Real *fixingbounds, const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real lpobjval, int extnedges, SCIP_Bool initialize, SCIP_Bool undirected)
static int	reduceWithNodeFixingBounds (SCIP *scip, GRAPH *graph, GRAPH *transgraph, const SCIP_Real *fixingbounds, SCIP_Real upperbound)
static int	reduceWithEdgeFixingBounds (SCIP *scip, GRAPH *graph, GRAPH *transgraph, const SCIP_Real *fixingbounds, const int *result, SCIP_Real upperbound)
static SCIP_RETCODE	reduceWithEdgeExtReds (SCIP *scip, SCIP_Real upperbound, EXTPERMA *extperma, GRAPH *graph, int *ndeletions_run)
static void	markPseudoDeletablesFromBounds (SCIP *scip, GRAPH *graph, const SCIP_Real *replacebounds, SCIP_Real upperbound, SCIP_Bool *pseudoDelNodes)
static void	findRootsMark (SCIP *scip, GRAPH *graph, const GRAPH *transgraph, const int *termmark, const SCIP_Real *cost, const SCIP_Real *bestcost, SCIP_Real lpobjval, SCIP_Real bestlpobjval, SCIP_Real upperbound, SCIP_Bool rerun, SCIP_Bool probrooted, int pseudoterm, int pseudoedge, STP_Bool *isfixedterm, int *roots, int *rootscount, int *pathedge, STP_Bool *visited, SCIP_Real *dist)
static void	daRpcmwDeleteTermIncidents (SCIP *scip, const PATH *vnoi, int term, GRAPH *graph, int *incidents, int *nfixedp)
static SCIP_RETCODE	daPcFindRoots (SCIP *scip, GRAPH *graph, const GRAPH *transgraph, const SCIP_Real *cost, const SCIP_Real *bestcost, SCIP_Real lpobjval, SCIP_Real bestlpobjval, SCIP_Real upperbound, SCIP_Bool rerun, SCIP_Bool probrooted, PATH *vnoi, int *pathedge, int *vbase, STP_Bool *isfixedterm, int *roots, int *rootscount)
static SCIP_RETCODE	daPcAddTmSolToPool (SCIP *scip, GRAPH *graph, int *result, STPSOLPOOL *pool)
static void	daPcMarkRoots (SCIP *scip, const int *roots, int nrootsold, int nrootsnew, SCIP_Real prizesum, GRAPH *graph, SCIP_Bool *userec, STPSOLPOOL **solpool)
static SCIP_Bool	daRedCostIsValid (SCIP *scip, GRAPH *transgraph, const SCIP_Real *cost, int *nodearrint, STP_Bool *nodearrbool)
static SCIP_Real	daGetMaxDeviation (const RPDA *paramsda, SCIP_RANDNUMGEN *randnumgen)
static SCIP_Bool	daGuidedIsPromising (const GRAPH *graph, int run, SCIP_RANDNUMGEN *randnumgen)
static SCIP_RETCODE	daOrderRoots (SCIP *scip, const GRAPH *graph, int *terms, int nterms, SCIP_Bool randomize, SCIP_RANDNUMGEN *randnumgen)
static SCIP_RETCODE	daRedcostsInit (SCIP *scip, const GRAPH *graph, const RPDA *paramsda, int nLevels, REDCOST **redcostdata)
static void	daRedcostsExit (SCIP *scip, REDCOST **redcostdata)
static int	daGetNruns (const GRAPH *graph, const RPDA *paramsda, int nterms)
static SCIP_RETCODE	daRoundInit (SCIP *scip, SCIP_Real upperbound, GRAPH *graph, REDCOST *redcostdata, STP_Bool *arcsdeleted, SCIP_Real *cutoffbound)
static void	daRoundExit (SCIP *scip, int ndeletions_run, GRAPH *graph, int *nelims)
static SCIP_RETCODE	computePertubedSol (SCIP *scip, GRAPH *graph, GRAPH *transgraph, STPSOLPOOL *pool, PATH *vnoi, SCIP_Real *cost, SCIP_Real *bestcost, SCIP_Real *pathdist, int *pathedge, int *result, int *result2, int *transresult, STP_Bool *nodearrchar, SCIP_Real *upperbound, SCIP_Real *lpobjval, SCIP_Real *bestlpobjval, SCIP_Real *minpathcost, SCIP_Bool *apsol, SCIP_Real offset, int extnedges)
static void	computeTransVoronoi (SCIP *scip, GRAPH *transgraph, PATH *vnoi, const SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *vbase, int *pathedge)
static SCIP_RETCODE	reduceRootedProb (SCIP *scip, GRAPH *graph, STP_Bool *marked, const REDCOST *redcostdata, const int *result, SCIP_Bool solgiven, int *nfixedp)
static int	reducePcMw (SCIP *scip, GRAPH *graph, GRAPH *transgraph, const PATH *vnoi, const SCIP_Real *cost, const SCIP_Real *pathdist, SCIP_Real minpathcost, const int *result, STP_Bool *marked, STP_Bool *nodearrchar, SCIP_Bool solgiven, SCIP_Bool deleteTransEdges)
static int	reducePcMwTryBest (SCIP *scip, GRAPH *graph, GRAPH *transgraph, PATH *vnoi, const SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *bestcost, SCIP_Real *pathdist, SCIP_Real *upperbound, SCIP_Real *lpobjval, SCIP_Real *bestlpobjval, SCIP_Real *minpathcost, SCIP_Real oldupperbound, const int *result, int *vbase, int *state, int *pathedge, STP_Bool *marked, STP_Bool *nodearrchar, SCIP_Bool *solgiven, int extnedges)
static SCIP_Bool	dapathsIsPromising (const GRAPH *g)
static SCIP_RETCODE	dapathsDeleteEdges (SCIP *scip, const REDCOST *redcostdata, const int *result, GRAPH *g, int *nelims)
static SCIP_RETCODE	dapathsReplaceNodes (SCIP *scip, REDCOST *redcostdata, const int *result, SCIP_Real objbound_upper, GRAPH *g, SCIP_Real *offsetp, int *nelims)
static SCIP_RETCODE	dapathsFixPotTerms (SCIP *scip, const REDCOST *redcostdata, GRAPH *g, SCIP_Real *offsetp, int *nelims)
SCIP_RETCODE	reduce_dapaths (SCIP *scip, GRAPH *g, SCIP_Real *offsetp, int *nelims)
SCIP_RETCODE	reduce_da (SCIP *scip, GRAPH *graph, const RPDA *paramsda, REDSOLLOCAL *redsollocal, SCIP_Real *offsetp, int *nelims, SCIP_RANDNUMGEN *randnumgen)
SCIP_RETCODE	reduce_daSlackPrune (SCIP *scip, GRAPH *graph, int minelims, SCIP_Bool solgiven, int *soledge, int *solnode, int *nelims, SCIP_Real *upperbound, SCIP_Bool *solImproved, SCIP_Bool *solReconstructed)
SCIP_RETCODE	reduce_daPcMw (SCIP *scip, GRAPH *graph, const RPDA *paramsda, REDSOLLOCAL *redprimal, PATH *vnoi, SCIP_Real *pathdist, int *vbase, int *pathedge, int *state, STP_Bool *nodearrchar, int *nelims, SCIP_RANDNUMGEN *randnumgen, SCIP_Real prizesum)

Macro Definition Documentation

BND_TMHEUR_NRUNS

#define BND_TMHEUR_NRUNS   100

number of runs of constructive heuristic

Definition at line 46 of file reduce_da.c.

Referenced by computeSteinerTreeTM().

BND_TMHEUR_NRUNS_RESTRICT

#define BND_TMHEUR_NRUNS_RESTRICT   16

number of runs of constructive heuristic

Definition at line 47 of file reduce_da.c.

Referenced by computeSteinerTreeTM().

BND_TMHEUR_NRUNS_RPC

#define BND_TMHEUR_NRUNS_RPC   16

number of runs for RPC

Definition at line 48 of file reduce_da.c.

Referenced by computeSteinerTreeTM(), and daPcAddTmSolToPool().

DEFAULT_DARUNS_DIRECTED

#define DEFAULT_DARUNS_DIRECTED   3

Definition at line 49 of file reduce_da.c.

Referenced by daGetNruns(), and daGuidedIsPromising().

DEFAULT_DARUNS

#define DEFAULT_DARUNS   8

number of runs for dual ascent heuristic

Definition at line 50 of file reduce_da.c.

Referenced by daGetNruns().

DEFAULT_DARUNS_FAST

#define DEFAULT_DARUNS_FAST   4

number of runs for dual ascent heuristic

Definition at line 51 of file reduce_da.c.

Referenced by daGetNruns().

DEFAULT_NMAXROOTS

#define DEFAULT_NMAXROOTS   8

max number of roots to use for new graph in dual ascent heuristic

Definition at line 52 of file reduce_da.c.

Referenced by reduce_daPcMw().

SOLPOOL_SIZE

#define SOLPOOL_SIZE   20

size of presolving solution pool

Definition at line 53 of file reduce_da.c.

Referenced by reduce_da(), and reduce_daPcMw().

DARUNS_TERMRATIO_LOW

#define DARUNS_TERMRATIO_LOW   0.05

Definition at line 54 of file reduce_da.c.

Referenced by daGetNruns().

DARUNS_TERMRATIO_MED

#define DARUNS_TERMRATIO_MED   0.075

Definition at line 55 of file reduce_da.c.

Referenced by daGetNruns().

DARUNS_TERMRATIO_HIGH

#define DARUNS_TERMRATIO_HIGH   0.1

Definition at line 56 of file reduce_da.c.

Referenced by daGetNruns().

DARUNS_TERMRATIO_HUGE

#define DARUNS_TERMRATIO_HUGE   0.2

Definition at line 57 of file reduce_da.c.

Referenced by daGetNruns().

STP_RED_MINBNDTERMS

#define STP_RED_MINBNDTERMS   750

Definition at line 58 of file reduce_da.c.

Referenced by reduce_daPcMw().

STP_DABD_MAXDEGREE

#define STP_DABD_MAXDEGREE   5

Definition at line 59 of file reduce_da.c.

Referenced by markPseudoDeletablesFromBounds(), and updateNodeReplaceBounds().

STP_DABD_MAXDNEDGES

#define STP_DABD_MAXDNEDGES   10

Definition at line 60 of file reduce_da.c.

DAMAXDEVIATION_RANDOM_LOWER

#define DAMAXDEVIATION_RANDOM_LOWER   0.20

random upper bound for max deviation for dual ascent

Definition at line 61 of file reduce_da.c.

Referenced by daGetMaxDeviation().

DAMAXDEVIATION_RANDOM_UPPER

#define DAMAXDEVIATION_RANDOM_UPPER   0.30

random upper bound for max deviation for dual ascent

Definition at line 62 of file reduce_da.c.

Referenced by daGetMaxDeviation().

DAMAXDEVIATION_FAST

#define DAMAXDEVIATION_FAST   0.75

Definition at line 63 of file reduce_da.c.

Referenced by reduce_daPcMw().

Function Documentation

getSolObj()

static SCIP_Real getSolObj ( SCIP *  scip, const GRAPH *  g, const int *  soledge  )

static

returns solution value for given edge-solution array (CONNECT/UNKNOWN) and offset, takes prizes into account!

Parameters

scip	SCIP data structure
g	the graph
soledge	solution

Definition at line 68 of file reduce_da.c.

References GRAPH::edges, graph_pc_isPcMw(), graph_pc_solGetObj(), SCIP_Real, and solstp_getObjBounded().

Referenced by computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsPcMw(), computeSteinerTreeTM(), daPcAddTmSolToPool(), reduce_daPcMw(), reduce_daSlackPrune(), and reduceWithEdgeFixingBounds().

computeDualSolutionGuided()

static SCIP_RETCODE computeDualSolutionGuided ( SCIP *  scip, GRAPH *  graph, SCIP_Real  damaxdeviation, REDCOST *  redcostdata, int *  result  )

static

computes dual solution with dual-ascent and guided solution (and possibly reroots given solution)

Parameters

scip	SCIP data structure
graph	graph data structure
damaxdeviation	maximum deviation for DA
redcostdata	reduced cost data
result	solution array

Definition at line 86 of file reduce_da.c.

References reduce_cost_parameters::addcuts, dualascent_exec(), dualascent_execDegCons(), FALSE, graph_pc_getNonLeafTermOffset(), graph_typeIsUndirected(), NULL, redcosts_getEdgeCostsTop(), redcosts_getRootTop(), redcosts_setDualBoundTop(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, solstp_isValid(), solstp_reroot(), GRAPH::source, STP_DCSTP, STP_RPCSPG, and GRAPH::stp_type.

Referenced by reduce_da().

computeDualSolution()

static SCIP_RETCODE computeDualSolution ( SCIP *  scip, GRAPH *  graph, SCIP_Real  damaxdeviation, REDCOST *  redcostdata  )

static

computes dual solution with dual-ascent

Parameters

scip	SCIP data structure
graph	graph data structure
damaxdeviation	maximum deviation for DA
redcostdata	reduced cost data

Definition at line 152 of file reduce_da.c.

References reduce_cost_parameters::addcuts, dualascent_exec(), dualascent_execDegCons(), FALSE, graph_pc_getNonLeafTermOffset(), NULL, redcosts_getEdgeCostsTop(), redcosts_getRootTop(), redcosts_setDualBoundTop(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, STP_DCSTP, STP_RPCSPG, and GRAPH::stp_type.

Referenced by reduce_da().

computeSteinerTreeTM()

static SCIP_RETCODE computeSteinerTreeTM ( SCIP *  scip, GRAPH *  graph, int *  result, SCIP_Real *  bestobjval, SCIP_Bool *  success  )

static

computes TM solution

Parameters

scip	SCIP data structure
graph	graph data structure
result	solution array
bestobjval	pointer to the objective value
success	success?

Definition at line 192 of file reduce_da.c.

References BND_TMHEUR_NRUNS, BND_TMHEUR_NRUNS_RESTRICT, BND_TMHEUR_NRUNS_RPC, GRAPH::extended, getSolObj(), graph_get_nEdges(), graph_get_nNodes(), graph_getEdgeCosts(), graph_pc_isRootedPcMw(), graph_typeIsDirected(), nnodes, NULL, pcmode_fromheurdata, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_RPCSPG, and GRAPH::stp_type.

Referenced by computeSteinerTreeRedCostsDirected(), and reduce_dapaths().

computeSteinerTreeRedCosts()

static SCIP_RETCODE computeSteinerTreeRedCosts ( SCIP *  scip, GRAPH *  graph, const REDCOST *  redcostdata, SCIP_Bool  useSlackPrune, SCIP_Bool  useRec, STPSOLPOOL *  pool, int *  result, int *  bestresult, SCIP_Bool *  havebestsol, SCIP_Real *  bestobjval  )

static

computes solution from reduced costs

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data
useSlackPrune	use slack prune?
useRec	use recombination?
pool	solution pool
result	result array
bestresult	result array
havebestsol	could best solution be stored in bestresult?
bestobjval	pointer to the objective value

Definition at line 260 of file reduce_da.c.

References BMScopyMemoryArray, GRAPH::edges, FALSE, getSolObj(), graph_pc_getNonLeafTermOffset(), LT, stp_solution_pool::maxindex, NULL, stp_solution::obj, redcosts_getEdgeCostsTop(), redcosts_getRootTop(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisEQ(), SCIPisLE(), SCIPisLT(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurLocalRunFast(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), stp_solution_pool::size, stp_solution::soledges, solpool_addSol(), solpool_solFromIndex(), solstp_isUnreduced(), solstp_isValid(), STP_RPCSPG, GRAPH::stp_type, and TRUE.

Referenced by reduce_da().

computeSteinerTreeRedCostsDirected()

static SCIP_RETCODE computeSteinerTreeRedCostsDirected ( SCIP *  scip, GRAPH *  graph, const REDCOST *  redcostdata, int *  result, int *  bestresult, SCIP_Bool *  havebestsol, SCIP_Real *  bestobjval  )

static

computes solution from reduced costs for directed graph

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data
result	result array
bestresult	result array
havebestsol	could best solution be stored in bestresult?
bestobjval	pointer to the objective value

Definition at line 369 of file reduce_da.c.

References BMScopyMemoryArray, computeSteinerTreeTM(), GRAPH::edges, FALSE, graph_typeIsDirected(), NULL, redcosts_getEdgeCostsTop(), redcosts_getRootTop(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), SCIPStpHeurAscendPruneRun(), solstp_getObj(), solstp_isUnreduced(), solstp_isValid(), GRAPH::source, STP_DCSTP, STP_DHCSTP, GRAPH::stp_type, and TRUE.

Referenced by reduce_da().

computeSteinerTreeRedCostsPcMw()

static SCIP_RETCODE computeSteinerTreeRedCostsPcMw ( SCIP *  scip, GRAPH *  graph, STPSOLPOOL *  pool, const SCIP_Real *  cost, SCIP_Real *  upperbound, int *  result1, int *  result2, int *  pathedge, STP_Bool *  nodearrchar, SCIP_Bool *  apsol  )

static

compute primal solution during dual-ascent routine for PCSTP or MWCSP based on reduced costs

Parameters

scip	SCIP data structure
graph	graph data structure
pool	solution pool
cost	dual ascent costs
upperbound	upperbound pointer
result1	sol int array corresponding to upper bound
result2	sol int array corresponding to best new solution (might be worse than upper bound)
pathedge	int array
nodearrchar	node array storing solution vertices
apsol	ascend-prune sol?

Definition at line 427 of file reduce_da.c.

References BMScopyMemoryArray, GRAPH::edges, FALSE, getSolObj(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), graph_pc_isPcMw(), stp_solution_pool::maxindex, NULL, stp_solution::obj, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisEQ(), SCIPisLE(), SCIPisLT(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), stp_solution_pool::size, stp_solution::soledges, solpool_addSol(), solpool_solFromIndex(), stp_solution_pool::sols, solstp_isValid(), STP_MWCSP, GRAPH::stp_type, and TRUE.

Referenced by computePertubedSol(), and reduce_daPcMw().

collectFixedTerminals()

static void collectFixedTerminals ( const GRAPH *  graph, int *  terminals, int *  nterms  )

inlinestatic

collected terminals (fixed ones for RPC/RMW)

Parameters

graph	graph data structure
terminals	terminals array (of size graph->terms)
nterms	number of terminals (might differ for RPC)

Definition at line 545 of file reduce_da.c.

References GRAPH::extended, graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), Is_term, GRAPH::knots, GRAPH::mark, nnodes, SCIP_Bool, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by reduce_da().

updateNodeFixingBounds()

static void updateNodeFixingBounds ( SCIP_Real *  fixingbounds, const GRAPH *  graph, const SCIP_Real *  pathdist, const PATH *  vnoi, SCIP_Real  lpobjval, SCIP_Bool  initialize  )

static

updates node bounds for reduced cost fixings

Parameters

fixingbounds	fixing bounds
graph	graph data structure
pathdist	shortest path distances
vnoi	Voronoi paths
lpobjval	LP objective
initialize	initialize fixing bounds?

Definition at line 575 of file reduce_da.c.

References shortest_path::dist, GRAPH::extended, FARAWAY, Is_pseudoTerm, GRAPH::knots, GRAPH::mark, nnodes, SCIP_Real, STP_RSMT, STP_SPG, GRAPH::stp_type, and GRAPH::term.

Referenced by reduce_da(), and reduce_daPcMw().

updateNodeReplaceBounds()

static SCIP_RETCODE updateNodeReplaceBounds ( SCIP *  scip, const REDCOST *  redcostdata, const GRAPH *  graph, SCIP_Real *  replacebounds, SCIP_Real  upperbound, SCIP_Bool  initialize, SCIP_Bool  extendedsearch  )

static

updates node bounds for reduced cost replacement

Parameters

scip	SCIP
redcostdata	reduced cost data
graph	graph data structure
replacebounds	replacement bounds
upperbound	upper bound
initialize	initialize fixing bounds?
extendedsearch	perform extended searching?

Definition at line 612 of file reduce_da.c.

References shortest_path::dist, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_pc_isMw(), GRAPH::head, Is_anyTerm, Is_pseudoTerm, GRAPH::knots, MAX, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, redcosts_getDualBoundTop(), redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsBasesTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), redcosts_getRootTop(), reduce_extendedCheck3Tree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisGE(), SCIPisLE(), STP_DABD_MAXDEGREE, STP_RSMT, STP_SPG, GRAPH::stp_type, and GRAPH::term.

Referenced by dapathsReplaceNodes(), and reduce_da().

updateEdgeFixingBounds()

static void updateEdgeFixingBounds ( SCIP_Real *  fixingbounds, const GRAPH *  graph, const SCIP_Real *  cost, const SCIP_Real *  pathdist, const PATH *  vnoi, SCIP_Real  lpobjval, int  extnedges, SCIP_Bool  initialize, SCIP_Bool  undirected  )

static

updates edge fixing bounds for reduced cost fixings

Parameters

fixingbounds	fixing bounds
graph	graph data structure
cost	reduced costs
pathdist	shortest path distances
vnoi	Voronoi paths
lpobjval	LP objective
extnedges	number of edges for extended problem
initialize	initialize fixing bounds?
undirected	only consider undirected edges

Definition at line 788 of file reduce_da.c.

References shortest_path::dist, EAT_LAST, GRAPH::extended, FARAWAY, flipedge, GRAPH::head, Is_pseudoTerm, GRAPH::knots, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, STP_RSMT, STP_SPG, GRAPH::stp_type, and GRAPH::term.

Referenced by reduce_da(), and reduce_daPcMw().

reduceWithNodeFixingBounds()

static int reduceWithNodeFixingBounds ( SCIP *  scip, GRAPH *  graph, GRAPH *  transgraph, const SCIP_Real *  fixingbounds, SCIP_Real  upperbound  )

static

eliminate nodes by using fixing-bounds and reduced costs

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure or NULL
fixingbounds	fixing bounds
upperbound	best upperbound

Definition at line 859 of file reduce_da.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_knot_del(), graph_mark(), Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIPdebugMessage, SCIPisFeasLT(), STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_da(), and reduce_daPcMw().

reduceWithEdgeFixingBounds()

static int reduceWithEdgeFixingBounds ( SCIP *  scip, GRAPH *  graph, GRAPH *  transgraph, const SCIP_Real *  fixingbounds, const int *  result, SCIP_Real  upperbound  )

static

eliminate edges by using fixing-bounds and reduced costs

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure or NULL
fixingbounds	fixing bounds
result	solution
upperbound	best upperbound

Definition at line 899 of file reduce_da.c.

References CONNECT, GRAPH::cost, deleteEdge(), EAT_LAST, EQ, GRAPH::extended, FALSE, FARAWAY, flipedge, getSolObj(), graph_edge_del(), graph_pc_isMw(), graph_typeIsDirected(), GRAPH::head, Is_pseudoTerm, GRAPH::knots, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIPdebugMessage, SCIPisEQ(), SCIPisFeasLT(), SCIPisLE(), solstp_isValid(), STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_da(), and reduce_daPcMw().

reduceWithEdgeExtReds()

static SCIP_RETCODE reduceWithEdgeExtReds ( SCIP *  scip, SCIP_Real  upperbound, EXTPERMA *  extperma, GRAPH *  graph, int *  ndeletions_run  )

static

eliminate edges with extended reductions

Parameters

scip	SCIP data structure
upperbound	best upperbound
extperma	extension data
graph	graph data structure
ndeletions_run	all deleted edges

Definition at line 979 of file reduce_da.c.

References extreduce_deleteEdges(), extension_data_permanent::redcostdata, redcosts_getCutoff(), redcosts_getNlevels(), redcosts_setCutoffFromBound(), SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPgetProbName().

Referenced by reduce_da().

markPseudoDeletablesFromBounds()

static void markPseudoDeletablesFromBounds ( SCIP *  scip, GRAPH *  graph, const SCIP_Real *  replacebounds, SCIP_Real  upperbound, SCIP_Bool *  pseudoDelNodes  )

static

Parameters

scip	SCIP data structure
graph	graph data structure
replacebounds	replacement bounds
upperbound	best upper bound
pseudoDelNodes	pseudo deletable nodes

Definition at line 1029 of file reduce_da.c.

References FALSE, GRAPH::grad, graph_pc_knotIsNonLeafTerm(), Is_anyTerm, GRAPH::knots, nnodes, SCIP_Bool, SCIPdebugMessage, SCIPisFeasLT(), STP_DABD_MAXDEGREE, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by dapathsReplaceNodes(), and reduce_da().

findRootsMark()

static void findRootsMark ( SCIP *  scip, GRAPH *  graph, const GRAPH *  transgraph, const int *  termmark, const SCIP_Real *  cost, const SCIP_Real *  bestcost, SCIP_Real  lpobjval, SCIP_Real  bestlpobjval, SCIP_Real  upperbound, SCIP_Bool  rerun, SCIP_Bool  probrooted, int  pseudoterm, int  pseudoedge, STP_Bool *  isfixedterm, int *  roots, int *  rootscount, int *  pathedge, STP_Bool *  visited, SCIP_Real *  dist  )

static

submethod for daFindRoots

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure
termmark	terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
cost	da reduced cost
bestcost	best incumbent da reduced cost
lpobjval	da lower bound
bestlpobjval	best da lower bound
upperbound	da upper bound
rerun	not the first run?
probrooted	is transgraph a rooted RMW or RPC?
pseudoterm	pseudo terminal
pseudoedge	pseudo terminal edge
isfixedterm	bool array to indicate fixed terminals
roots	root array
rootscount	number of roots
pathedge	array
visited	stores whether a node has been visited
dist	distances array, initially set to FARAWAY

Definition at line 1068 of file reduce_da.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_knotIsFixedTerm(), graph_pc_termIsNonLeafTerm(), graph_sdWalksConnected(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, MAX, NULL, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisPositive(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by daPcFindRoots().

daRpcmwDeleteTermIncidents()

static void daRpcmwDeleteTermIncidents ( SCIP *  scip, const PATH *  vnoi, int  term, GRAPH *  graph, int *  incidents, int *  nfixedp  )

static

special method for RPC/RMW that deletes incident edges of terminal, but not the terminal and the extension itself

Parameters

scip	SCIP data structure
vnoi	Voronoi data structure
term	the terminal
graph	graph data structure
incidents	int array
nfixedp	number of fixed edges pointer

Definition at line 1187 of file reduce_da.c.

References GRAPH::cost, EAT_LAST, GRAPH::grad, graph_edge_del(), graph_pc_getTwinTerm(), graph_pc_isRootedPcMw(), GRAPH::head, Is_pseudoTerm, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by reduceRootedProb().

daPcFindRoots()

static SCIP_RETCODE daPcFindRoots ( SCIP *  scip, GRAPH *  graph, const GRAPH *  transgraph, const SCIP_Real *  cost, const SCIP_Real *  bestcost, SCIP_Real  lpobjval, SCIP_Real  bestlpobjval, SCIP_Real  upperbound, SCIP_Bool  rerun, SCIP_Bool  probrooted, PATH *  vnoi, int *  pathedge, int *  vbase, STP_Bool *  isfixedterm, int *  roots, int *  rootscount  )

static

find roots for PC and MW during DA reduction

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure
cost	da reduced cost
bestcost	best incumbent da reduced cost
lpobjval	da lower bound
bestlpobjval	best da lower bound
upperbound	da upper bound
rerun	not the first run?
probrooted	is transgraph a rooted RMW or RPC?
vnoi	SP array
pathedge	array
vbase	array
isfixedterm	bool array
roots	roots (fixed terminals) array
rootscount	number of roots

Definition at line 1229 of file reduce_da.c.

References BMSclearMemoryArray, GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, findRootsMark(), GRAPH::grad, graph_pc_2org(), graph_pc_2trans(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_termMarkProper(), graph_sdWalksConnected(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, GRAPH::term2edge, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reduce_daPcMw().

daPcAddTmSolToPool()

static SCIP_RETCODE daPcAddTmSolToPool ( SCIP *  scip, GRAPH *  graph, int *  result, STPSOLPOOL *  pool  )

static

computes TM solution and adds it too pool

Parameters

scip	SCIP data structure
graph	graph data structure
result	solution
pool	the pool

Definition at line 1404 of file reduce_da.c.

References BND_TMHEUR_NRUNS_RPC, GRAPH::cost, getSolObj(), NULL, pcmode_fromheurdata, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPStpHeurLocalRun(), SCIPStpHeurTMRun(), solpool_addSol(), and GRAPH::source.

Referenced by reduce_daPcMw().

daPcMarkRoots()

static void daPcMarkRoots ( SCIP *  scip, const int *  roots, int  nrootsold, int  nrootsnew, SCIP_Real  prizesum, GRAPH *  graph, SCIP_Bool *  userec, STPSOLPOOL **  solpool  )

static

set prize of marked terminals to blocked

Parameters

scip	SCIP data structure
roots	root array
nrootsold	old number of roots
nrootsnew	new number of roots
prizesum	sum of positive prizes
graph	graph data structure
userec	recombination?
solpool	solution pool

Definition at line 1431 of file reduce_da.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, graph_pc_2org(), graph_pc_2trans(), graph_pc_getTwinTerm(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, NULL, GRAPH::prize, SCIP_Bool, SCIPisEQ(), SCIPisPositive(), solpool_free(), GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by reduce_daPcMw().

daRedCostIsValid()

static SCIP_Bool daRedCostIsValid ( SCIP *  scip, GRAPH *  transgraph, const SCIP_Real *  cost, int *  nodearrint, STP_Bool *  nodearrbool  )

static

are the reduced costs still valid, i.e. are there zero cost paths from the root to all terminals?

Parameters

scip	SCIP data structure
transgraph	graph data structure
cost	dual ascent costs
nodearrint	int array
nodearrbool	bool array

Definition at line 1488 of file reduce_da.c.

References a, BMSclearMemoryArray, EAT_LAST, FALSE, GRAPH::head, Is_term, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIPisZero(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_daPcMw(), and reducePcMwTryBest().

daGetMaxDeviation()

static SCIP_Real daGetMaxDeviation ( const RPDA *  paramsda, SCIP_RANDNUMGEN *  randnumgen  )

static

returns maximum allowed deviation for dual-ascent

Parameters

paramsda	parameters
randnumgen	random number generator

Definition at line 1543 of file reduce_da.c.

References DAMAXDEVIATION_RANDOM_LOWER, DAMAXDEVIATION_RANDOM_UPPER, reduce_costs_reduction_parameters::damode, SCIP_Real, and SCIPrandomGetReal().

Referenced by reduce_da().

daGuidedIsPromising()

static SCIP_Bool daGuidedIsPromising ( const GRAPH *  graph, int  run, SCIP_RANDNUMGEN *  randnumgen  )

static

decide whether guided DA is promising

Parameters

graph	graph structure
run	number of current run
randnumgen	random number generator

Definition at line 1567 of file reduce_da.c.

References DEFAULT_DARUNS_DIRECTED, graph_typeIsUndirected(), SCIPrandomGetInt(), and TRUE.

Referenced by reduce_da().

daOrderRoots()

static SCIP_RETCODE daOrderRoots ( SCIP *  scip, const GRAPH *  graph, int *  terms, int  nterms, SCIP_Bool  randomize, SCIP_RANDNUMGEN *  randnumgen  )

static

order roots

Parameters

scip	SCIP data structure
graph	graph structure
terms	sol int array corresponding to upper bound
nterms	number of terminals
randomize	randomize?
randnumgen	random number generator

Definition at line 1587 of file reduce_da.c.

References GRAPH::grad, graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_typeIsDirected(), GRAPH::knots, nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPrandomGetInt(), SCIPsortDownIntInt(), and GRAPH::source.

Referenced by reduce_da(), and reduce_daPcMw().

daRedcostsInit()

static SCIP_RETCODE daRedcostsInit ( SCIP *  scip, const GRAPH *  graph, const RPDA *  paramsda, int  nLevels, REDCOST **  redcostdata  )

static

initializes reduced costs data

Parameters

scip	SCIP data structure
graph	graph data structure
paramsda	parameters
nLevels	number of levels for extended reductions
redcostdata	reduced cost data

Definition at line 1650 of file reduce_da.c.

References reduced_costs_parameters::cutoff, extred_none, reduce_costs_reduction_parameters::extredMode, graph_get_nEdges(), graph_get_nNodes(), reduced_costs_parameters::nLevels, nnodes, redcosts_initFromParams(), SCIP_CALL, SCIP_OKAY, and UNKNOWN.

Referenced by reduce_da().

daRedcostsExit()

static void daRedcostsExit ( SCIP *  scip, REDCOST **  redcostdata  )

static

frees reduced costs data

Parameters

scip	SCIP data structure
redcostdata	reduced cost data

Definition at line 1676 of file reduce_da.c.

References redcosts_free().

Referenced by reduce_da().

daGetNruns()

static int daGetNruns ( const GRAPH *  graph, const RPDA *  paramsda, int  nterms  )

static

number of runs

Parameters

graph	graph structure
paramsda	parameters
nterms	number of terminals

Definition at line 1687 of file reduce_da.c.

References reduce_costs_reduction_parameters::damode, DARUNS_TERMRATIO_HIGH, DARUNS_TERMRATIO_HUGE, DARUNS_TERMRATIO_LOW, DARUNS_TERMRATIO_MED, DEFAULT_DARUNS, DEFAULT_DARUNS_DIRECTED, DEFAULT_DARUNS_FAST, graph_get_nVET(), graph_typeIsSpgLike(), graph_typeIsUndirected(), MAX, nnodes, NULL, SCIP_Real, STP_DAMODE_FAST, STP_DAMODE_HOPS, STP_DHCSTP, GRAPH::stp_type, and GRAPH::terms.

Referenced by reduce_da().

daRoundInit()

static SCIP_RETCODE daRoundInit ( SCIP *  scip, SCIP_Real  upperbound, GRAPH *  graph, REDCOST *  redcostdata, STP_Bool *  arcsdeleted, SCIP_Real *  cutoffbound  )

static

initializes DA round

Parameters

scip	SCIP data structure
upperbound	upper bound
graph	graph structure
redcostdata	reduced cost data
arcsdeleted	array
cutoffbound	cut-off bound

Definition at line 1740 of file reduce_da.c.

References FALSE, graph_get_nEdges(), graph_mark(), graph_pc_2org(), graph_pc_isRootedPcMw(), graph_typeIsUndirected(), redcosts_initializeDistancesTop(), redcosts_setAndReturnCutoffFromBoundTop(), SCIP_Bool, SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_da().

daRoundExit()

static void daRoundExit ( SCIP *  scip, int  ndeletions_run, GRAPH *  graph, int *  nelims  )

static

for exiting DA round

Parameters

scip	SCIP data structure
ndeletions_run	number of deletions
graph	graph structure
nelims	number of eliminations

Definition at line 1776 of file reduce_da.c.

References graph_mark(), graph_pc_2trans(), graph_pc_isRootedPcMw(), graph_typeIsDirected(), graph_valid(), reduce_unconnected(), reduce_unconnectedForDirected(), SCIP_Bool, and SCIPdebugMessage.

Referenced by reduce_da().

computePertubedSol()

static SCIP_RETCODE computePertubedSol ( SCIP *  scip, GRAPH *  graph, GRAPH *  transgraph, STPSOLPOOL *  pool, PATH *  vnoi, SCIP_Real *  cost, SCIP_Real *  bestcost, SCIP_Real *  pathdist, int *  pathedge, int *  result, int *  result2, int *  transresult, STP_Bool *  nodearrchar, SCIP_Real *  upperbound, SCIP_Real *  lpobjval, SCIP_Real *  bestlpobjval, SCIP_Real *  minpathcost, SCIP_Bool *  apsol, SCIP_Real  offset, int  extnedges  )

static

try to improve both dual and primal solution

Definition at line 1810 of file reduce_da.c.

References reduce_cost_parameters::addcuts, BMScopyMemoryArray, computeSteinerTreeRedCostsPcMw(), CONNECT, dualascent_exec(), EAT_LAST, GRAPH::edges, FALSE, graph_pc_2transcheck(), graph_pc_isPcMw(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), solstp_isValid(), GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_daPcMw().

computeTransVoronoi()

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

static

compute Voronoi region for dual-ascent elimination for PC/MW

Definition at line 1915 of file reduce_da.c.

References EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_add1stTermPaths(), graph_path_execX(), Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIPisEQ(), GRAPH::source, and GRAPH::term.

Referenced by reduce_daPcMw(), and reducePcMwTryBest().

reduceRootedProb()

static SCIP_RETCODE reduceRootedProb ( SCIP *  scip, GRAPH *  graph, STP_Bool *  marked, const REDCOST *  redcostdata, const int *  result, SCIP_Bool  solgiven, int *  nfixedp  )

static

reduce graph with non-artificial root (SPG, RPC ...) based on information from dual ascent and given upper bound

Parameters

scip	SCIP data structure
graph	graph data structure
marked	edge array to mark which (directed) edge can be removed
redcostdata	reduced cost data
result	sol int array
solgiven	is sol given?
nfixedp	number of fixed edges pointer

Definition at line 1954 of file reduce_da.c.

References CONNECT, GRAPH::cost, daRpcmwDeleteTermIncidents(), shortest_path::dist, EAT_LAST, GRAPH::extended, FARAWAY, flipedge, GE, GRAPH::grad, graph_edge_del(), graph_knot_del(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_termIsNonLeafTerm(), graph_typeIsUndirected(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, redcosts_getCutoffTop(), redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPisFeasGT(), SCIPisGT(), SCIPisZero(), solstp_setVertexFromEdge(), GRAPH::term, and TRUE.

Referenced by dapathsDeleteEdges(), and reduce_da().

reducePcMw()

static int reducePcMw ( SCIP *  scip, GRAPH *  graph, GRAPH *  transgraph, const PATH *  vnoi, const SCIP_Real *  cost, const SCIP_Real *  pathdist, SCIP_Real  minpathcost, const int *  result, STP_Bool *  marked, STP_Bool *  nodearrchar, SCIP_Bool  solgiven, SCIP_Bool  deleteTransEdges  )

static

reduce PCSTP or MWCS graph based on information from dual ascent and given upper bound

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure
vnoi	Voronoi data structure
cost	dual ascent costs
pathdist	distance array from shortest path calculations
minpathcost	the required reduced path cost to be surpassed
result	sol int array
marked	edge array to mark which (directed) edge can be removed
nodearrchar	node array storing solution vertices
solgiven	is sol given?
deleteTransEdges	delete edges of transformed graph

Definition at line 2071 of file reduce_da.c.

References CONNECT, shortest_path::dist, EAT_FREE, EAT_LAST, FALSE, flipedge, graph_edge_del(), graph_get_nNodes(), graph_pc_2orgcheck(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisZero(), solstp_isValid(), solstp_setVertexFromEdge(), STP_Vectype, StpVecFree, StpVecGetSize, StpVecPushBack, GRAPH::term, and TRUE.

Referenced by reduce_daPcMw(), and reducePcMwTryBest().

reducePcMwTryBest()

static int reducePcMwTryBest ( SCIP *  scip, GRAPH *  graph, GRAPH *  transgraph, PATH *  vnoi, const SCIP_Real *  cost, SCIP_Real *  costrev, SCIP_Real *  bestcost, SCIP_Real *  pathdist, SCIP_Real *  upperbound, SCIP_Real *  lpobjval, SCIP_Real *  bestlpobjval, SCIP_Real *  minpathcost, SCIP_Real  oldupperbound, const int *  result, int *  vbase, int *  state, int *  pathedge, STP_Bool *  marked, STP_Bool *  nodearrchar, SCIP_Bool *  solgiven, int  extnedges  )

static

try to run reduction method for best known reduced costs (if they are valid)

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure
vnoi	Voronoi data structure
cost	dual ascent costs
costrev	SCIP_Real array
bestcost	best dual ascent costs
pathdist	distance array from shortest path calculations
upperbound	upper bound
lpobjval	reduced cost value
bestlpobjval	best reduced cost value
minpathcost	the required reduced path cost to be surpassed
oldupperbound	old upper bound
result	sol int array
vbase	array for Voronoi bases
state	int 4 * nnodes array for internal computations
pathedge	array for predecessor edge on a path
marked	edge array to mark which (directed) edge can be removed
nodearrchar	node array storing solution vertices
solgiven	is sol given?
extnedges	number of edges for transgraph

Definition at line 2212 of file reduce_da.c.

References BMScopyMemoryArray, computeTransVoronoi(), daRedCostIsValid(), reducePcMw(), SCIP_Bool, SCIPisGE(), SCIPisGT(), SCIPisLT(), solstp_isUnreduced(), solstp_isValid(), and TRUE.

Referenced by reduce_daPcMw().

dapathsIsPromising()

static SCIP_Bool dapathsIsPromising ( const GRAPH *  g )

static

promising?

Parameters

g	graph data structure

Definition at line 2263 of file reduce_da.c.

References graph_get_nVET(), nnodes, nterms, NULL, SCIP_Bool, and SCIP_Real.

Referenced by reduce_dapaths().

dapathsDeleteEdges()

static SCIP_RETCODE dapathsDeleteEdges ( SCIP *  scip, const REDCOST *  redcostdata, const int *  result, GRAPH *  g, int *  nelims  )

static

deletes edges

Parameters

scip	SCIP data structure
redcostdata	reduced cost data
result	solution
g	graph data structure
nelims	pointer to store number of reduced edges

Definition at line 2283 of file reduce_da.c.

References BMSclearMemoryArray, graph_get_nEdges(), reduceRootedProb(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by reduce_dapaths().

dapathsReplaceNodes()

static SCIP_RETCODE dapathsReplaceNodes ( SCIP *  scip, REDCOST *  redcostdata, const int *  result, SCIP_Real  objbound_upper, GRAPH *  g, SCIP_Real *  offsetp, int *  nelims  )

static

pseudo-eliminates nodes

Parameters

scip	SCIP data structure
redcostdata	reduced cost data
result	solution
objbound_upper	objective
g	graph data structure
offsetp	pointer to store offset
nelims	pointer to store number of reduced edges

Definition at line 2308 of file reduce_da.c.

References FALSE, GRAPH::knots, markPseudoDeletablesFromBounds(), reduce_applyPseudoDeletions(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, TRUE, and updateNodeReplaceBounds().

Referenced by reduce_dapaths().

dapathsFixPotTerms()

static SCIP_RETCODE dapathsFixPotTerms ( SCIP *  scip, const REDCOST *  redcostdata, GRAPH *  g, SCIP_Real *  offsetp, int *  nelims  )

static

eliminates RPC/RMW potential-terminals

Parameters

scip	SCIP data structure
redcostdata	reduced cost data
g	graph data structure
offsetp	pointer to store offset
nelims	pointer to store number of reduced edges

Definition at line 2339 of file reduce_da.c.

References EAT_LAST, GRAPH::extended, GRAPH::grad, graph_knot_printInfo(), graph_pc_getTwinTerm(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotToFixedTerm(), GT, GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, redcosts_getCutoffTop(), redcosts_getEdgeCostsTop(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and GRAPH::terms.

Referenced by reduce_dapaths().

reduce_dapaths()

SCIP_RETCODE reduce_dapaths	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	offsetp,
		int *	nelims
	)

dual ascent path based reductions

Parameters

scip	SCIP data structure
g	graph data structure
offsetp	pointer to store offset
nelims	pointer to store number of reduced edges

Definition at line 2397 of file reduce_da.c.

References computeSteinerTreeTM(), dapathsDeleteEdges(), dapathsFixPotTerms(), dapathsIsPromising(), dapathsReplaceNodes(), dualascent_paths(), GRAPH::extended, FARAWAY, graph_get_nEdges(), graph_isMarked(), graph_mark(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_valid(), GRAPH::knots, redcosts_free(), redcosts_getEdgeCostsTop(), redcosts_init(), redcosts_initializeDistancesTop(), redcosts_setCutoffFromBoundTop(), redcosts_setDualBoundTop(), reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPStpHeurLocalRun(), solstp_getObj(), solstp_isUnreduced(), GRAPH::source, and GRAPH::terms.

Referenced by redLoopInnerPc().

reduce_da()

SCIP_RETCODE reduce_da	(	SCIP *	scip,
		GRAPH *	graph,
		const RPDA *	paramsda,
		REDSOLLOCAL *	redsollocal,
		SCIP_Real *	offsetp,
		int *	nelims,
		SCIP_RANDNUMGEN *	randnumgen
	)

dual ascent based reductions

Parameters

scip	SCIP data structure
graph	graph data structure
paramsda	parameters
redsollocal	primal bound info or NULL
offsetp	pointer to store offset
nelims	pointer to store number of reduced edges
randnumgen	random number generator

Definition at line 2471 of file reduce_da.c.

References collectFixedTerminals(), computeDualSolution(), computeDualSolutionGuided(), computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsDirected(), GRAPH::cost, daGetMaxDeviation(), daGetNruns(), daGuidedIsPromising(), reduce_costs_reduction_parameters::damode, daOrderRoots(), daRedcostsExit(), daRedcostsInit(), daRoundExit(), daRoundInit(), GRAPH::edges, GRAPH::extended, extred_none, reduce_costs_reduction_parameters::extredMode, extreduce_exit(), extreduce_extPermaAddRandnumgen(), extreduce_init(), extreduce_pseudoDeleteNodes(), FALSE, FARAWAY, GE, GRAPH::grad, graph_mark(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_isMw(), graph_pc_isPc(), graph_pc_isRootedPcMw(), graph_typeIsDirected(), graph_valid(), graph_valid_ancestors(), GRAPH::hoplimit, GRAPH::knots, markPseudoDeletablesFromBounds(), nnodes, reduce_costs_reduction_parameters::nodereplacing, NULL, redcosts_addLevel(), redcosts_getDualBoundTop(), redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), redcosts_increaseOnDeletedArcsTop(), redcosts_setRootTop(), reduce_applyPseudoDeletions(), reduce_identifyNonLeafTerms(), reduce_sollocalGetUpperBound(), reduce_sollocalRebuildTry(), reduce_sollocalSetOffset(), reduce_sollocalUpdateNodesol(), reduce_sollocalUpdateUpperBound(), reduce_sollocalUsesNodesol(), reduceRootedProb(), reduceWithEdgeExtReds(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisFeasGT(), SCIPisZero(), extension_data_permanent::solIsValid, solpool_free(), solpool_init(), SOLPOOL_SIZE, solstp_isUnreduced(), solstp_rerootInfeas(), GRAPH::source, STP_DAMODE_HOPS, STP_DCSTP, STP_DHCSTP, STP_RPCSPG, GRAPH::stp_type, GRAPH::terms, TRUE, updateEdgeFixingBounds(), updateNodeFixingBounds(), updateNodeReplaceBounds(), reduce_costs_reduction_parameters::useRec, and reduce_costs_reduction_parameters::useSlackPrune.

Referenced by redLoopInnerMw(), redLoopInnerPc(), redLoopInnerStp(), reduce_boundHopDa(), reduce_dc(), reduce_hc(), reduce_nw(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), and reduce_sap().

reduce_daSlackPrune()

SCIP_RETCODE reduce_daSlackPrune	(	SCIP *	scip,
		GRAPH *	graph,
		int	minelims,
		SCIP_Bool	solgiven,
		int *	soledge,
		int *	solnode,
		int *	nelims,
		SCIP_Real *	upperbound,
		SCIP_Bool *	solImproved,
		SCIP_Bool *	solReconstructed
	)

dual ascent reduction for slack-and-prune heuristic

Parameters

scip	SCIP data structure
graph	graph data structure
minelims	minimum number of edges to eliminate
solgiven	solution provided?
soledge	solution edges (in/out)
solnode	array of nodes of current solution that is not to be destroyed (in/out)
nelims	pointer to store number of reduced edges
upperbound	pointer to store new upper bound
solImproved	solution improved?
solReconstructed	solution reconstructed?

Definition at line 2741 of file reduce_da.c.

References reduce_cost_parameters::addcuts, CONNECT, GRAPH::cost, shortest_path::dist, dualascent_allTermsReachable(), dualascent_exec(), EAT_LAST, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, flipedge, getSolObj(), GRAPH::grad, graph_edge_del(), graph_get2nextTermPaths(), graph_get_nEdges(), graph_get_nNodes(), graph_knot_del(), graph_mark(), graph_path_exec(), graph_path_execX(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsortReal(), SCIPStpHeurAscendPruneRun(), solstp_isValid(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurSlackPruneRun().

reduce_daPcMw()

SCIP_RETCODE reduce_daPcMw	(	SCIP *	scip,
		GRAPH *	graph,
		const RPDA *	paramsda,
		REDSOLLOCAL *	redprimal,
		PATH *	vnoi,
		SCIP_Real *	pathdist,
		int *	vbase,
		int *	pathedge,
		int *	state,
		STP_Bool *	nodearrchar,
		int *	nelims,
		SCIP_RANDNUMGEN *	randnumgen,
		SCIP_Real	prizesum
	)

dual ascent based reductions for PCSPG and MWCSP

Parameters

scip	SCIP data structure
graph	graph data structure
paramsda	parameters
redprimal	primal bound info or NULL
vnoi	Voronoi data structure array
pathdist	distance array for shortest path calculations
vbase	Voronoi base array
pathedge	shortest path incoming edge array for shortest path calculations
state	int 4 * vertices array
nodearrchar	STP_Bool node array for internal computations
nelims	pointer to store number of reduced edges
randnumgen	random number generator
prizesum	sum of positive prizes

Definition at line 3174 of file reduce_da.c.

References reduce_cost_parameters::addcuts, BMScopyMemoryArray, computePertubedSol(), computeSteinerTreeRedCostsPcMw(), computeTransVoronoi(), reduce_cost_parameters::damaxdeviation, DAMAXDEVIATION_FAST, daOrderRoots(), daPcAddTmSolToPool(), daPcFindRoots(), daPcMarkRoots(), daRedCostIsValid(), DEFAULT_NMAXROOTS, dualascent_allTermsReachable(), dualascent_exec(), dualascent_pathsPcMw(), EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GE, getSolObj(), GRAPH::grad, graph_add1stTermPaths(), graph_add2ndTermPaths(), graph_free(), graph_get_nEdges(), graph_get_nNodes(), graph_mark(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_isPc(), graph_pc_knotIsNonLeafTerm(), graph_transPcGetRsap(), graph_transPcGetSap(), graph_valid(), GRAPH::head, reduce_cost_parameters::is_pseudoroot, Is_pseudoTerm, Is_term, GRAPH::knots, LT, GRAPH::mark, nnodes, NULL, stp_solution::obj, GRAPH::oeat, GRAPH::outbeg, reduce_costs_reduction_parameters::pcmw_fastDa, reduce_costs_reduction_parameters::pcmw_markroots, reduce_costs_reduction_parameters::pcmw_solbasedda, reduce_costs_reduction_parameters::pcmw_useMultRoots, GRAPH::prize, reduce_identifyNonLeafTerms(), reduce_sollocalGetUpperBound(), reduce_sollocalUpdateNodesol(), reduce_sollocalUpdateUpperBound(), reduce_sollocalUsesNodesol(), reducePcMw(), reducePcMwTryBest(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), reduce_cost_parameters::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPisGE(), SCIPisGT(), solpool_free(), solpool_init(), SOLPOOL_SIZE, stp_solution_pool::sols, solstp_isUnreduced(), solstp_isValid(), solstp_reroot(), GRAPH::source, STP_MWCSP, STP_RED_MINBNDTERMS, STP_RPCSPG, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, updateEdgeFixingBounds(), updateNodeFixingBounds(), and reduce_costs_reduction_parameters::useRec.

Referenced by redLoopInnerMw(), redLoopInnerPc(), reduce_redLoopMw(), and reduce_redLoopPc().