Scippy

SCIP

Solving Constraint Integer Programs

reduce_bnd.c File Reference

Detailed Description

bound based reductions for Steiner tree problems

Author
Daniel Rehfeldt

This file implements bound-based reduction techniques for several Steiner problems. All tests can be found in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.

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

Definition in file reduce_bnd.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "scip/scip.h"
#include "grph.h"
#include "heur_tm.h"
#include "heur_ascendprune.h"
#include "cons_stp.h"
#include "heur_local.h"
#include "misc_stp.h"
#include "prop_stp.h"
#include "probdata_stp.h"
#include "heur_rec.h"
#include "heur_slackprune.h"

Go to the source code of this file.

Macros

#define DEFAULT_HEURRUNS   100
 
#define DEFAULT_DARUNS   7
 
#define DEFAULT_NMAXROOTS   8
 
#define PERTUBATION_RATIO   0.05
 
#define PERTUBATION_RATIO_PC   0.005
 
#define SOLPOOL_SIZE   20
 
#define STP_RED_MINBNDTERMS   750
 
#define STP_DABD_MAXDEGREE   5
 
#define STP_DABD_MAXDNEDGES   10
 
#define STP_DAEX_MAXDFSDEPTH   6
 
#define STP_DAEX_MINDFSDEPTH   4
 
#define STP_DAEX_MAXGRAD   8
 
#define STP_DAEX_MINGRAD   6
 
#define STP_DAEX_EDGELIMIT   50000
 
#define DAMAXDEVIATION_RANDOM_LOWER   0.15
 
#define DAMAXDEVIATION_RANDOM_UPPER   0.30
 
#define DAMAXDEVIATION_FAST   0.75
 
#define EXEDGE_FREE   0
 
#define EXEDGE_FIXED   1
 
#define EXEDGE_KILLED   2
 

Functions

static SCIP_Bool markAncestorsConflict (const GRAPH *graph, int edge, int *ancestormark)
 
static void markAncestors (const GRAPH *graph, int edge, int *ancestormark)
 
static void unmarkAncestorsConflict (const GRAPH *graph, int edge, int *ancestormark)
 
static void unmarkAncestors (const GRAPH *graph, int edge, int *ancestormark)
 
static void finalizeSubtree (const GRAPH *graph, const int *edgeends, const int *treeedges, int dfsdepth, SCIP_Bool stopped, SCIP_Real localbound, SCIP_Real *globalbound, SCIP_Bool *ruleout, int *nodepos, int *ancestormark)
 
static SCIP_Bool truncateSubtree (const GRAPH *graph, SCIP_Real extendedcost, int root, int currhead, int maxgrad, int dfsdepth, int maxdfsdepth, SCIP_Real *minbound, SCIP_Bool *stopped)
 
static SCIP_Real shortenSubtree (SCIP *scip, const GRAPH *graph, const SCIP_Real *redcost, const int *treeedges, SCIP_Real treecostold, SCIP_Real treecostoffset, int dfsdepth, int lastnode, int *nodepos, int *ancestormark, unsigned int *nstallrounds)
 
static int extendSubtreeHead (SCIP *scip, const GRAPH *graph, const SCIP_Real *redcost, int curredge, int currhead, int dfsdepth, int nadded_edges, SCIP_Real *treecost, SCIP_Real *treecosts, int *nodepos, int *treeedges, int *edgestack, int *ancestormark)
 
static int extendSubtreeTail (const GRAPH *graph, const SCIP_Real *redcost, int curredge, int currtail, int dfsdepth, int nadded_edges, SCIP_Real *treecost, SCIP_Real *treecosts, int *nodepos, int *treeedges, int *edgestack, int *ancestormark)
 
static void updateEqArrays (int edge, unsigned int *eqstack, int *eqstack_size, SCIP_Bool *eqmark)
 
static SCIP_Bool bottleneckRuleOut (SCIP *scip, const GRAPH *graph, const SCIP_Real *treecosts, const SCIP_Real *basebottlenecks, const int *nodepos, const int *treeedges, SCIP_Real orgedgecost, SCIP_Real extedgecost, int orgedge, int extedge, int dfsdepth, SCIP_Bool allow_eq, unsigned int *eqstack, int *eqstack_size, SCIP_Bool *eqmark)
 
static SCIP_Bool ruleOutSubtree (SCIP *scip, const GRAPH *graph, const SCIP_Real *treecosts, const SCIP_Real *basebottlenecks, const int *nodepos, const int *treeedges, SCIP_Real cutoff, SCIP_Real extendedcost, int dfsdepth, int curredge, SCIP_Bool allowequality, const int *ancestormark, unsigned int *eqstack, int *eqstack_size, SCIP_Bool *eqmark)
 
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, SCIP_Real *replacebounds, const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *pathdist, const PATH *vnoi, const int *vbase, int *nodearrint, SCIP_Real lpobjval, SCIP_Real upperbound, int root, 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 reduceWithNodeReplaceBounds (SCIP *scip, GRAPH *graph, const PATH *vnoi, const SCIP_Real *pathdist, const SCIP_Real *cost, const SCIP_Real *replacebounds, int *nodetouched, SCIP_Real lpobjval, SCIP_Real upperbound)
 
static int reduceWithEdgeFixingBounds (SCIP *scip, GRAPH *graph, GRAPH *transgraph, const SCIP_Real *fixingbounds, const int *result, SCIP_Real upperbound)
 
static void findDaRoots (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_Real prizesum, SCIP_Bool rerun, SCIP_Bool probrooted, PATH *vnoi, int *state, int *pathedge, int *vbase, STP_Bool *nodearrchar, int *roots, int *rootscount)
 
static void markPcMwRoots (SCIP *scip, const int *roots, int nrootsold, int nrootsnew, SCIP_Real prizesum, GRAPH *graph, SCIP_Bool *userec, STPSOLPOOL **solpool)
 
static SCIP_Bool dualCostIsValid (SCIP *scip, GRAPH *transgraph, const SCIP_Real *cost, int *nodearrint, STP_Bool *nodearrbool)
 
static void pertubateEdgeCosts (SCIP *scip, const GRAPH *graph, GRAPH *transgraph, const int *result, STP_Bool *nodearrchar, int randomize)
 
static SCIP_RETCODE orderDaRoots (SCIP *scip, const GRAPH *graph, int *terms, int nterms, SCIP_Bool randomize, SCIP_RANDNUMGEN *randnumgen)
 
static SCIP_RETCODE computeDaSolPcMw (SCIP *scip, GRAPH *graph, STPSOLPOOL *pool, PATH *vnoi, const SCIP_Real *cost, SCIP_Real *pathdist, SCIP_Real *upperbound, int *result1, int *result2, int *vbase, int *pathedge, STP_Bool *nodearrchar, SCIP_Bool *apsol)
 
static SCIP_RETCODE computePertubedSol (SCIP *scip, GRAPH *graph, GRAPH *transgraph, STPSOLPOOL *pool, PATH *vnoi, GNODE **gnodearr, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *bestcost, SCIP_Real *pathdist, int *state, int *vbase, 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, int pertubation)
 
static void computeTransVoronoi (SCIP *scip, GRAPH *transgraph, PATH *vnoi, const SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *vbase, int *pathedge)
 
static int reduceSPG (SCIP *scip, GRAPH *graph, SCIP_Real *offset, STP_Bool *marked, STP_Bool *nodearrchar, const PATH *vnoi, const SCIP_Real *cost, const SCIP_Real *pathdist, const int *result, SCIP_Real minpathcost, int root, SCIP_Bool solgiven)
 
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)
 
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_RETCODE reduceCheckEdge (SCIP *scip, const GRAPH *graph, int root, const SCIP_Real *redcost, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real cutoff, int edge, SCIP_Bool equality, int *edgestack, SCIP_Bool *deletable, unsigned int *eqstack, int *eqstack_size, SCIP_Bool *eqmark)
 
SCIP_RETCODE reduce_deleteConflictEdges (SCIP *scip, GRAPH *g)
 
SCIP_RETCODE reduce_check3Tree (SCIP *scip, const GRAPH *graph, int root, const SCIP_Real *redcost, const SCIP_Real *pathdist, const PATH *vnoi, const int *vbase, SCIP_Real cutoff, const int *outedges, int inedge, int *edgestack, SCIP_Real *treebound, SCIP_Bool *ruleout, unsigned int *eqstack, int *eqstack_size, SCIP_Bool *eqmark)
 
int reduce_extendedEdge (SCIP *scip, GRAPH *graph, const PATH *vnoi, const SCIP_Real *cost, const SCIP_Real *pathdist, const int *result, SCIP_Real minpathcost, int root, int *nodearr, STP_Bool *marked)
 
SCIP_RETCODE reduce_da (SCIP *scip, GRAPH *graph, PATH *vnoi, GNODE **gnodearr, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, SCIP_Real *ub, SCIP_Real *offset, int *edgearrint, int *vbase, int *state, int *pathedge, int *nodearrint, int *heursources, STP_Bool *nodearrchar, int *nelims, int prevrounds, SCIP_RANDNUMGEN *randnumgen, SCIP_Bool userec, SCIP_Bool extended)
 
SCIP_RETCODE reduce_daSlackPrune (SCIP *scip, SCIP_VAR **vars, GRAPH *graph, PATH *vnoi, GNODE **gnodearr, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, SCIP_Real *upperbound, int *edgearrint, int *edgearrint2, int *vbase, int *pathedge, int *state, int *solnode, STP_Bool *nodearrchar, STP_Bool *edgearrchar, int *nelims, int minelims, SCIP_Bool solgiven)
 
SCIP_RETCODE reduce_daPcMw (SCIP *scip, GRAPH *graph, PATH *vnoi, GNODE **gnodearr, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *vbase, int *pathedge, int *edgearrint, int *state, STP_Bool *nodearrchar, int *nelims, SCIP_Bool solbasedda, SCIP_Bool varyroot, SCIP_Bool markroots, SCIP_Bool userec, SCIP_Bool fastmode, SCIP_RANDNUMGEN *randnumgen, SCIP_Real prizesum)
 
SCIP_RETCODE reduce_daSlackPruneMw (SCIP *scip, GRAPH *graph, PATH *vnoi, GNODE **gnodearr, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *vbase, int *pathedge, int *soledge, int *state, int *solnode, STP_Bool *nodearrchar, int *nelims, int minelims, SCIP_Bool solgiven)
 
SCIP_RETCODE reduce_bound (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *prize, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, SCIP_Real *upperbound, int *heap, int *state, int *vbase, int *nelims)
 
SCIP_RETCODE reduce_boundMw (SCIP *scip, GRAPH *graph, PATH *vnoi, PATH *path, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, int *heap, int *state, int *vbase, int *result, int *nelims)
 
SCIP_RETCODE reduce_boundPrune (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, int *heap, int *state, int *vbase, const int *solnode, const int *soledge, int *nelims, int minelims)
 
SCIP_RETCODE reduce_boundHop (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, int *heap, int *state, int *vbase, int *nelims)
 
SCIP_RETCODE reduce_boundHopR (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *heap, int *state, int *vbase, int *nelims, int *pathedge)
 
SCIP_RETCODE reduce_boundHopRc (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, SCIP_Real objval, int *heap, int *state, int *vbase, int *nelims, int *pathedge, SCIP_Bool fix)
 

Macro Definition Documentation

◆ DEFAULT_HEURRUNS

#define DEFAULT_HEURRUNS   100

number of runs of constructive heuristic

Definition at line 44 of file reduce_bnd.c.

Referenced by reduce_bound(), reduce_da(), reduce_daPcMw(), and reduce_daSlackPruneMw().

◆ DEFAULT_DARUNS

#define DEFAULT_DARUNS   7

number of runs for dual ascent heuristic

Definition at line 45 of file reduce_bnd.c.

Referenced by reduce_da().

◆ DEFAULT_NMAXROOTS

#define DEFAULT_NMAXROOTS   8

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

Definition at line 46 of file reduce_bnd.c.

Referenced by reduce_daPcMw().

◆ PERTUBATION_RATIO

#define PERTUBATION_RATIO   0.05

pertubation ratio for dual-ascent primal bound computation

Definition at line 47 of file reduce_bnd.c.

Referenced by pertubateEdgeCosts().

◆ PERTUBATION_RATIO_PC

#define PERTUBATION_RATIO_PC   0.005

pertubation ratio for dual-ascent primal bound computation

Definition at line 48 of file reduce_bnd.c.

Referenced by pertubateEdgeCosts().

◆ SOLPOOL_SIZE

#define SOLPOOL_SIZE   20

size of presolving solution pool

Definition at line 49 of file reduce_bnd.c.

Referenced by reduce_da(), and reduce_daPcMw().

◆ STP_RED_MINBNDTERMS

#define STP_RED_MINBNDTERMS   750

Definition at line 50 of file reduce_bnd.c.

Referenced by reduce_daPcMw().

◆ STP_DABD_MAXDEGREE

#define STP_DABD_MAXDEGREE   5

Definition at line 51 of file reduce_bnd.c.

Referenced by reduceWithNodeReplaceBounds(), and updateNodeReplaceBounds().

◆ STP_DABD_MAXDNEDGES

#define STP_DABD_MAXDNEDGES   10

Definition at line 52 of file reduce_bnd.c.

Referenced by reduceWithNodeReplaceBounds().

◆ STP_DAEX_MAXDFSDEPTH

#define STP_DAEX_MAXDFSDEPTH   6

Definition at line 53 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ STP_DAEX_MINDFSDEPTH

#define STP_DAEX_MINDFSDEPTH   4

Definition at line 54 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ STP_DAEX_MAXGRAD

#define STP_DAEX_MAXGRAD   8

Definition at line 55 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), reduceCheckEdge(), ruleOutSubtree(), and truncateSubtree().

◆ STP_DAEX_MINGRAD

#define STP_DAEX_MINGRAD   6

Definition at line 56 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ STP_DAEX_EDGELIMIT

#define STP_DAEX_EDGELIMIT   50000

Definition at line 57 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ DAMAXDEVIATION_RANDOM_LOWER

#define DAMAXDEVIATION_RANDOM_LOWER   0.15

random upper bound for max deviation for dual ascent

Definition at line 58 of file reduce_bnd.c.

Referenced by reduce_da().

◆ DAMAXDEVIATION_RANDOM_UPPER

#define DAMAXDEVIATION_RANDOM_UPPER   0.30

random upper bound for max deviation for dual ascent

Definition at line 59 of file reduce_bnd.c.

Referenced by reduce_da().

◆ DAMAXDEVIATION_FAST

#define DAMAXDEVIATION_FAST   0.75

Definition at line 60 of file reduce_bnd.c.

Referenced by reduce_daPcMw().

◆ EXEDGE_FREE

#define EXEDGE_FREE   0

Definition at line 62 of file reduce_bnd.c.

Referenced by truncateSubtree().

◆ EXEDGE_FIXED

#define EXEDGE_FIXED   1

Definition at line 63 of file reduce_bnd.c.

Referenced by truncateSubtree().

◆ EXEDGE_KILLED

#define EXEDGE_KILLED   2

Definition at line 64 of file reduce_bnd.c.

Referenced by truncateSubtree().

Function Documentation

◆ markAncestorsConflict()

static SCIP_Bool markAncestorsConflict ( const GRAPH graph,
int  edge,
int *  ancestormark 
)
static

mark ancestors of given edge

Parameters
graphgraph data structure
edgeedge to use
ancestormarkancestor mark array

Definition at line 69 of file reduce_bnd.c.

References GRAPH::ancestors, GRAPH::edges, FALSE, MAX, NULL, GRAPH::orgedges, and TRUE.

Referenced by reduce_check3Tree(), and reduce_deleteConflictEdges().

◆ markAncestors()

static void markAncestors ( const GRAPH graph,
int  edge,
int *  ancestormark 
)
static

mark ancestors of given edge

Parameters
graphgraph data structure
edgeedge to use
ancestormarkancestor mark array

Definition at line 96 of file reduce_bnd.c.

References GRAPH::ancestors, GRAPH::edges, MAX, NULL, and GRAPH::orgedges.

Referenced by extendSubtreeHead(), extendSubtreeTail(), and reduceCheckEdge().

◆ unmarkAncestorsConflict()

static void unmarkAncestorsConflict ( const GRAPH graph,
int  edge,
int *  ancestormark 
)
static

unmark ancestors of given edge

Parameters
graphgraph data structure
edgeedge to use
ancestormarkancestor mark array

Definition at line 116 of file reduce_bnd.c.

References GRAPH::ancestors, GRAPH::edges, MAX, NULL, and GRAPH::orgedges.

Referenced by reduce_check3Tree(), and reduce_deleteConflictEdges().

◆ unmarkAncestors()

static void unmarkAncestors ( const GRAPH graph,
int  edge,
int *  ancestormark 
)
static

unmark ancestors of given edge

Parameters
graphgraph data structure
edgeedge to use
ancestormarkancestor mark array

Definition at line 134 of file reduce_bnd.c.

References GRAPH::ancestors, GRAPH::edges, MAX, NULL, and GRAPH::orgedges.

Referenced by finalizeSubtree(), reduceCheckEdge(), and shortenSubtree().

◆ finalizeSubtree()

static void finalizeSubtree ( const GRAPH graph,
const int *  edgeends,
const int *  treeedges,
int  dfsdepth,
SCIP_Bool  stopped,
SCIP_Real  localbound,
SCIP_Real globalbound,
SCIP_Bool ruleout,
int *  nodepos,
int *  ancestormark 
)
static

finalize subtree computations (clean up, update global bound)

Parameters
graphgraph data structure
edgeendsheads or tail of edge
treeedgestree edges
dfsdepthdfs depth
stoppedhas extension been stopped?
localboundlocal bound
globalboundpoints to global bound
ruleoutrule out?
nodeposnode position in tree
ancestormarkancestor mark array

Definition at line 157 of file reduce_bnd.c.

References TRUE, and unmarkAncestors().

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ truncateSubtree()

static SCIP_Bool truncateSubtree ( const GRAPH graph,
SCIP_Real  extendedcost,
int  root,
int  currhead,
int  maxgrad,
int  dfsdepth,
int  maxdfsdepth,
SCIP_Real minbound,
SCIP_Bool stopped 
)
static

should we truncate subtree?

Parameters
graphgraph data structure
extendedcostcost of subtree
rootDA root
currheadlatest node
maxgradmaximum allowed degree
dfsdepthdfs depth
maxdfsdepthmax dfs depth
minboundbound
stoppedreal truncation?

Definition at line 195 of file reduce_bnd.c.

References GRAPH::cost, EAT_LAST, EXEDGE_FIXED, EXEDGE_FREE, EXEDGE_KILLED, FALSE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPisLT(), STP_DAEX_MAXGRAD, GRAPH::term, and TRUE.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ shortenSubtree()

static SCIP_Real shortenSubtree ( SCIP scip,
const GRAPH graph,
const SCIP_Real redcost,
const int *  treeedges,
SCIP_Real  treecostold,
SCIP_Real  treecostoffset,
int  dfsdepth,
int  lastnode,
int *  nodepos,
int *  ancestormark,
unsigned int *  nstallrounds 
)
static

remove latest edge from subtree and returns new tree cost

Parameters
scipSCIP
graphgraph data structure
redcostreduced costs
treeedgesedges of tree
treecostoldold tree cost
treecostoffsettree cost offset
dfsdepthDFS depth
lastnodelast node
nodeposarray to mark node position
ancestormarkancestor mark array
nstallroundsrounds since latest update

Definition at line 334 of file reduce_bnd.c.

References SCIP_Real, SCIPisEQ(), SCIPisGE(), and unmarkAncestors().

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ extendSubtreeHead()

static int extendSubtreeHead ( SCIP scip,
const GRAPH graph,
const SCIP_Real redcost,
int  curredge,
int  currhead,
int  dfsdepth,
int  nadded_edges,
SCIP_Real treecost,
SCIP_Real treecosts,
int *  nodepos,
int *  treeedges,
int *  edgestack,
int *  ancestormark 
)
static

extend subtree and return new nadded_edges

Parameters
scipSCIP
graphgraph data structure
redcostreduced costs
curredgeadded edges
currheadlatest node
dfsdepthDFS depth
nadded_edgesadded edges
treecostpointer to treecost
treecostsedge costs of tree
nodeposnode position in tree
treeedgesedges of tree
edgestackstack
ancestormarkancestor mark array

Definition at line 383 of file reduce_bnd.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, markAncestors(), GRAPH::oeat, and GRAPH::outbeg.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ extendSubtreeTail()

static int extendSubtreeTail ( const GRAPH graph,
const SCIP_Real redcost,
int  curredge,
int  currtail,
int  dfsdepth,
int  nadded_edges,
SCIP_Real treecost,
SCIP_Real treecosts,
int *  nodepos,
int *  treeedges,
int *  edgestack,
int *  ancestormark 
)
static

extend subtree and return new nadded_edges

Parameters
graphgraph data structure
redcostreduced costs
curredgeadded edges
currtaillatest node
dfsdepthDFS depth
nadded_edgesadded edges
treecostpointer to treecost
treecostsedge costs of tree
nodeposnode position in tree
treeedgesedges of tree
edgestackstack
ancestormarkancestor mark array

Definition at line 416 of file reduce_bnd.c.

References GRAPH::cost, EAT_LAST, GRAPH::ieat, GRAPH::inpbeg, markAncestors(), and GRAPH::tail.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ updateEqArrays()

static void updateEqArrays ( int  edge,
unsigned int *  eqstack,
int *  eqstack_size,
SCIP_Bool eqmark 
)
static

small helper

Parameters
edgethe edge
eqstackstores edges that were used for equality comparison
eqstack_sizepointer to size of eqstack
eqmarkmarks edges that were used for equality comparison

Definition at line 449 of file reduce_bnd.c.

References TRUE.

Referenced by bottleneckRuleOut().

◆ bottleneckRuleOut()

static SCIP_Bool bottleneckRuleOut ( SCIP scip,
const GRAPH graph,
const SCIP_Real treecosts,
const SCIP_Real basebottlenecks,
const int *  nodepos,
const int *  treeedges,
SCIP_Real  orgedgecost,
SCIP_Real  extedgecost,
int  orgedge,
int  extedge,
int  dfsdepth,
SCIP_Bool  allow_eq,
unsigned int *  eqstack,
int *  eqstack_size,
SCIP_Bool eqmark 
)
static

compare with tree bottleneck

Parameters
scipSCIP
graphgraph data structure
treecostscosts of edges of the tree
basebottlenecksbottleneck costs for innode and basenode
nodeposnode position in tree
treeedgesedges in tree (corresponding to treecosts)
orgedgecostcost of original edge
extedgecostcost of short-cut edge
orgedgeoriginal edge
extedgeshort-cut edge
dfsdepthdfs depth
allow_eqtest for equality?
eqstackstores edges that were used for equality comparison
eqstack_sizepointer to size of eqstack
eqmarkmarks edges that were used for equality comparison

Definition at line 472 of file reduce_bnd.c.

References FALSE, GRAPH::knots, NULL, SCIPisEQ(), SCIPisLE(), SCIPisLT(), GRAPH::tail, TRUE, and updateEqArrays().

Referenced by ruleOutSubtree().

◆ ruleOutSubtree()

static SCIP_Bool ruleOutSubtree ( SCIP scip,
const GRAPH graph,
const SCIP_Real treecosts,
const SCIP_Real basebottlenecks,
const int *  nodepos,
const int *  treeedges,
SCIP_Real  cutoff,
SCIP_Real  extendedcost,
int  dfsdepth,
int  curredge,
SCIP_Bool  allowequality,
const int *  ancestormark,
unsigned int *  eqstack,
int *  eqstack_size,
SCIP_Bool eqmark 
)
static

can subtree be ruled out?

Parameters
scipSCIP
graphgraph data structure
treecostscosts of edges of the tree
basebottlenecksbottleneck costs for innode and basenode
nodeposnode position in tree
treeedgesedges in tree (corresponding to treecosts)
cutoffcut-off bound
extendedcostcost of subtree
dfsdepthdfs depth
curredgelatest edge
allowequalityrule out also in case of equality
ancestormarkancestor mark array
eqstackstores edges that were used for equality comparison
eqstack_sizepointer to size of eqstack
eqmarkmarks edges that were used for equality comparison

Definition at line 552 of file reduce_bnd.c.

References GRAPH::ancestors, bottleneckRuleOut(), GRAPH::cost, EAT_LAST, GRAPH::edges, FALSE, flipedge, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, MAX, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPisGT(), STP_DAEX_MAXGRAD, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ 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
fixingboundsfixing bounds
graphgraph data structure
pathdistshortest path distances
vnoiVoronoi paths
lpobjvalLP objective
initializeinitialize fixing bounds?

Definition at line 654 of file reduce_bnd.c.

References shortest_path::dist, GRAPH::extended, FARAWAY, Is_pterm, 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,
SCIP_Real replacebounds,
const GRAPH graph,
const SCIP_Real cost,
const SCIP_Real pathdist,
const PATH vnoi,
const int *  vbase,
int *  nodearrint,
SCIP_Real  lpobjval,
SCIP_Real  upperbound,
int  root,
SCIP_Bool  initialize,
SCIP_Bool  extendedsearch 
)
static

updates node bounds for reduced cost replacement

Parameters
scipSCIP
replaceboundsreplacement bounds
graphgraph data structure
costreduced costs
pathdistshortest path distances
vnoiVoronoi paths
vbasebases to Voronoi paths
nodearrintfor internal computations
lpobjvalLP objective
upperboundupper bound
rootDA root
initializeinitialize fixing bounds?
extendedsearchperform extended searching?

Definition at line 689 of file reduce_bnd.c.

References shortest_path::dist, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, GRAPH::head, Is_gterm, Is_pterm, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_check3Tree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), STP_DABD_MAXDEGREE, STP_RSMT, STP_SPG, GRAPH::stp_type, and GRAPH::term.

Referenced by 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
fixingboundsfixing bounds
graphgraph data structure
costreduced costs
pathdistshortest path distances
vnoiVoronoi paths
lpobjvalLP objective
extnedgesnumber of edges for extended problem
initializeinitialize fixing bounds?
undirectedonly consider undirected edges

Definition at line 859 of file reduce_bnd.c.

References shortest_path::dist, EAT_LAST, GRAPH::extended, FARAWAY, flipedge, GRAPH::head, Is_pterm, 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
scipSCIP data structure
graphgraph data structure
transgraphgraph data structure or NULL
fixingboundsfixing bounds
upperboundbest upperbound

Definition at line 930 of file reduce_bnd.c.

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

Referenced by reduce_da(), and reduce_daPcMw().

◆ reduceWithNodeReplaceBounds()

static int reduceWithNodeReplaceBounds ( SCIP scip,
GRAPH graph,
const PATH vnoi,
const SCIP_Real pathdist,
const SCIP_Real cost,
const SCIP_Real replacebounds,
int *  nodetouched,
SCIP_Real  lpobjval,
SCIP_Real  upperbound 
)
static
Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
pathdistdistance array from shortest path calculations
costdual ascent costs
replaceboundsreplacement bounds
nodetouchednode array for internal computations
lpobjvallower bound corresponding to pathdist and vnoi
upperboundbest upperbound

Definition at line 963 of file reduce_bnd.c.

References shortest_path::dist, EAT_LAST, GRAPH::grad, graph_knot_delPseudo(), GRAPH::head, Is_gterm, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPisLT(), STP_DABD_MAXDEGREE, STP_DABD_MAXDNEDGES, and GRAPH::term.

Referenced by reduce_da().

◆ 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
scipSCIP data structure
graphgraph data structure
transgraphgraph data structure or NULL
fixingboundsfixing bounds
resultsolution
upperboundbest upperbound

Definition at line 1050 of file reduce_bnd.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, flipedge, graph_edge_del(), graph_sol_valid(), GRAPH::head, Is_pterm, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIPdebugMessage, SCIPisLT(), STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_da(), and reduce_daPcMw().

◆ findDaRoots()

static void findDaRoots ( 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_Real  prizesum,
SCIP_Bool  rerun,
SCIP_Bool  probrooted,
PATH vnoi,
int *  state,
int *  pathedge,
int *  vbase,
STP_Bool nodearrchar,
int *  roots,
int *  rootscount 
)
static

find roots for PC and MW during DA reduction

Parameters
scipSCIP data structure
graphgraph data structure
transgraphgraph data structure
costda reduced cost
bestcostbest incumbent da reduced cost
lpobjvalda lower bound
bestlpobjvalbest da lower bound
upperboundda upper bound
prizesumsum of positive prizes
rerunnot the first run?
probrootedis transgraph a rooted RMW or RPC?
vnoiSP array
statearray
pathedgearray
vbasearray
nodearrcharbool array
rootsroot array
rootscountnumber of roots

Definition at line 1110 of file reduce_bnd.c.

References BMSclearMemoryArray, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::extended, FARAWAY, GRAPH::grad, graph_pc_2org(), graph_pc_2trans(), graph_sdPaths(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPisEQ(), SCIPisGT(), SCIPisPositive(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reduce_daPcMw().

◆ markPcMwRoots()

static void markPcMwRoots ( 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
scipSCIP data structure
rootsroot array
nrootsoldold number of roots
nrootsnewnew number of roots
prizesumsum of positive prizes
graphgraph data structure
userecrecombination?
solpoolsolution pool

Definition at line 1312 of file reduce_bnd.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, graph_pc_2org(), graph_pc_2trans(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, NULL, GRAPH::prize, SCIP_Bool, SCIPisEQ(), SCIPisPositive(), SCIPStpHeurRecFreePool(), GRAPH::source, GRAPH::tail, GRAPH::term, and GRAPH::term2edge.

Referenced by reduce_daPcMw().

◆ dualCostIsValid()

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

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

Parameters
scipSCIP data structure
transgraphgraph data structure
costdual ascent costs
nodearrintint array
nodearrboolbool array

Definition at line 1369 of file reduce_bnd.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().

◆ pertubateEdgeCosts()

static void pertubateEdgeCosts ( SCIP scip,
const GRAPH graph,
GRAPH transgraph,
const int *  result,
STP_Bool nodearrchar,
int  randomize 
)
static

◆ orderDaRoots()

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

order roots

Parameters
scipSCIP data structure
graphgraph structure
termssol int array corresponding to upper bound
ntermsnumber of terminals
randomizerandomize
randnumgenrandom number generator

Definition at line 1564 of file reduce_bnd.c.

References GRAPH::grad, nterms, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPrandomGetInt(), and SCIPsortIntInt().

Referenced by reduce_da(), and reduce_daPcMw().

◆ computeDaSolPcMw()

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

compute primal solution during dual-ascent routine for PCSTP or MWCSP

Parameters
scipSCIP data structure
graphgraph data structure
poolsolution pool
vnoiVoronoi data structure
costdual ascent costs
pathdistdistance array from shortest path calculations
upperboundupperbound pointer
result1sol int array corresponding to upper bound
result2sol int array
vbaseint array
pathedgeint array
nodearrcharnode array storing solution vertices
apsolascend-prune sol?

Definition at line 1606 of file reduce_bnd.c.

References BMScopyMemoryArray, GRAPH::cost, GRAPH::edges, FALSE, graph_sol_getObj(), graph_sol_valid(), stp_solution_pool::maxindex, NULL, stp_solution::obj, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), SCIPisLT(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurRecSolfromIdx(), stp_solution_pool::size, stp_solution::soledges, stp_solution_pool::sols, STP_MWCSP, GRAPH::stp_type, and TRUE.

Referenced by computePertubedSol(), and reduce_daPcMw().

◆ computePertubedSol()

static SCIP_RETCODE computePertubedSol ( SCIP scip,
GRAPH graph,
GRAPH transgraph,
STPSOLPOOL pool,
PATH vnoi,
GNODE **  gnodearr,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real bestcost,
SCIP_Real pathdist,
int *  state,
int *  vbase,
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,
int  pertubation 
)
static

◆ 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

◆ reduceSPG()

static int reduceSPG ( SCIP scip,
GRAPH graph,
SCIP_Real offset,
STP_Bool marked,
STP_Bool nodearrchar,
const PATH vnoi,
const SCIP_Real cost,
const SCIP_Real pathdist,
const int *  result,
SCIP_Real  minpathcost,
int  root,
SCIP_Bool  solgiven 
)
static

reduce SPG graph based on information from dual ascent and given upper bound

Parameters
scipSCIP data structure
graphgraph data structure
offsetoffset pointer
markededge array to mark which (directed) edge can be removed
nodearrcharnode array storing solution vertices
vnoiVoronoi data structure
costdual ascent costs
pathdistdistance array from shortest path calculations
resultsol int array
minpathcostthe required reduced path cost to be surpassed
rootthe root
solgivenis sol given?

Definition at line 1902 of file reduce_bnd.c.

References CONNECT, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_del(), graph_pc_2org(), graph_pc_deleteTerm(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisEQ(), SCIPisGT(), SCIPisZero(), STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by 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 
)
static

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

Parameters
scipSCIP data structure
graphgraph data structure
transgraphgraph data structure
vnoiVoronoi data structure
costdual ascent costs
pathdistdistance array from shortest path calculations
minpathcostthe required reduced path cost to be surpassed
resultsol int array
markededge array to mark which (directed) edge can be removed
nodearrcharnode array storing solution vertices
solgivenis sol given?

Definition at line 2010 of file reduce_bnd.c.

References CONNECT, shortest_path::dist, EAT_FREE, EAT_LAST, GRAPH::edges, FALSE, flipedge, GRAPH::grad, graph_edge_del(), graph_pc_2orgcheck(), graph_sol_valid(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisZero(), GRAPH::source, GRAPH::tail, 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
scipSCIP data structure
graphgraph data structure
transgraphgraph data structure
vnoiVoronoi data structure
costdual ascent costs
costrevSCIP_Real array
bestcostbest dual ascent costs
pathdistdistance array from shortest path calculations
upperboundupper bound
lpobjvalreduced cost value
bestlpobjvalbest reduced cost value
minpathcostthe required reduced path cost to be surpassed
oldupperboundold upper bound
resultsol int array
vbasearray for Voronoi bases
stateint 4 * nnodes array for internal computations
pathedgearray for predecessor edge on a path
markededge array to mark which (directed) edge can be removed
nodearrcharnode array storing solution vertices
solgivenis sol given?
extnedgesnumber of edges for transgraph

Definition at line 2159 of file reduce_bnd.c.

References BMScopyMemoryArray, computeTransVoronoi(), dualCostIsValid(), graph_sol_unreduced(), graph_sol_valid(), reducePcMw(), SCIP_Bool, SCIPisGE(), SCIPisGT(), and SCIPisLT().

Referenced by reduce_daPcMw().

◆ reduceCheckEdge()

static SCIP_RETCODE reduceCheckEdge ( SCIP scip,
const GRAPH graph,
int  root,
const SCIP_Real redcost,
const SCIP_Real pathdist,
const PATH vnoi,
SCIP_Real  cutoff,
int  edge,
SCIP_Bool  equality,
int *  edgestack,
SCIP_Bool deletable,
unsigned int *  eqstack,
int *  eqstack_size,
SCIP_Bool eqmark 
)
static

check (directed) edge

Parameters
scipSCIP data structure
graphgraph data structure
rootgraph root from dual ascent
redcostreduced costs
pathdistshortest path distances
vnoiVoronoi paths
cutoffcutoff value
edge(directed) edge to be checked
equalityallow equality?
edgestackarray of size nodes for internal computations
deletableis edge deletable?
eqstackstores edges that were used for equality comparison
eqstack_sizepointer to size of eqstack
eqmarkmarks edges that were used for equality comparison

Definition at line 2211 of file reduce_bnd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, extendSubtreeHead(), extendSubtreeTail(), FALSE, FARAWAY, finalizeSubtree(), flipedge, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, markAncestors(), MAX, nnodes, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, ruleOutSubtree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPisEQ(), SCIPisGE(), SCIPisGT(), shortenSubtree(), STP_DAEX_EDGELIMIT, STP_DAEX_MAXDFSDEPTH, STP_DAEX_MAXGRAD, STP_DAEX_MINDFSDEPTH, STP_DAEX_MINGRAD, GRAPH::tail, GRAPH::term, TRUE, truncateSubtree(), and unmarkAncestors().

Referenced by reduce_extendedEdge().

◆ reduce_deleteConflictEdges()

SCIP_RETCODE reduce_deleteConflictEdges ( SCIP scip,
GRAPH g 
)

todo don't use this function, but check for conflicts in misc_stp.c and handle them

Parameters
scipSCIP data structure
gthe graph

Definition at line 2421 of file reduce_bnd.c.

References GRAPH::ancestors, EAT_FREE, GRAPH::edges, FALSE, graph_edge_del(), markAncestorsConflict(), MAX, NULL, GRAPH::oeat, GRAPH::orgedges, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, TRUE, and unmarkAncestorsConflict().

Referenced by redLoopStp(), and reduce_da().

◆ reduce_check3Tree()

SCIP_RETCODE reduce_check3Tree ( SCIP scip,
const GRAPH graph,
int  root,
const SCIP_Real redcost,
const SCIP_Real pathdist,
const PATH vnoi,
const int *  vbase,
SCIP_Real  cutoff,
const int *  outedges,
int  inedge,
int *  edgestack,
SCIP_Real treebound,
SCIP_Bool ruleout,
unsigned int *  eqstack,
int *  eqstack_size,
SCIP_Bool eqmark 
)

check 3-tree

Parameters
scipSCIP data structure
graphgraph data structure
rootgraph root from dual ascent
redcostreduced costs
pathdistshortest path distances
vnoiVoronoi paths
vbasebases to Voronoi paths
cutoffcutoff value
outedgestwo outgoing edge
inedgeincoming edge
edgestackarray of size nodes for internal computations
treeboundto store a lower bound for the tree
ruleoutcould tree be ruled out?
eqstackstores edges that were used for equality comparison
eqstack_sizepointer to size of eqstack
eqmarkmarks edges that were used for equality comparison

Definition at line 2464 of file reduce_bnd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, extendSubtreeHead(), extendSubtreeTail(), FALSE, FARAWAY, finalizeSubtree(), flipedge, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, markAncestorsConflict(), MAX, nnodes, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, ruleOutSubtree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPisGE(), SCIPisGT(), shortenSubtree(), STP_DAEX_EDGELIMIT, STP_DAEX_MAXDFSDEPTH, STP_DAEX_MAXGRAD, STP_DAEX_MINDFSDEPTH, STP_DAEX_MINGRAD, GRAPH::tail, GRAPH::term, TRUE, truncateSubtree(), and unmarkAncestorsConflict().

Referenced by updateNodeReplaceBounds().

◆ reduce_extendedEdge()

int reduce_extendedEdge ( SCIP scip,
GRAPH graph,
const PATH vnoi,
const SCIP_Real cost,
const SCIP_Real pathdist,
const int *  result,
SCIP_Real  minpathcost,
int  root,
int *  nodearr,
STP_Bool marked 
)

reduce SPG graph based on reduced cost information and given upper bound

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
costdual ascent costs
pathdistdistance array from shortest path calculations
resultsol int array
minpathcostthe required reduced path cost to be surpassed
rootthe root
nodearrfor internal stuff
markededge array to mark which (directed) edge can be removed

Definition at line 2774 of file reduce_bnd.c.

References CONNECT, EAT_FREE, GRAPH::edges, FALSE, GRAPH::grad, graph_edge_del(), graph_pc_2orgcheck(), GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, reduceCheckEdge(), SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisZero(), STP_RPCSPG, GRAPH::stp_type, and TRUE.

Referenced by reduce_da(), and reduceRedcostExtended().

◆ reduce_da()

SCIP_RETCODE reduce_da ( SCIP scip,
GRAPH graph,
PATH vnoi,
GNODE **  gnodearr,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
SCIP_Real ub,
SCIP_Real offset,
int *  edgearrint,
int *  vbase,
int *  state,
int *  pathedge,
int *  nodearrint,
int *  heursources,
STP_Bool nodearrchar,
int *  nelims,
int  prevrounds,
SCIP_RANDNUMGEN randnumgen,
SCIP_Bool  userec,
SCIP_Bool  extended 
)

dual ascent based reductions

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
gnodearrGNODE* terminals array for internal computations or NULL
costedge costs
costrevreverse edge costs
pathdistdistance array for shortest path calculations
ubpointer to provide upper bound and return upper bound found during ascent and prune (if better)
offsetpointer to store offset
edgearrintint edges array for internal computations or NULL
vbasearray for Voronoi bases
stateint 4 * nnodes array for internal computations
pathedgearray for predecessor edge on a path
nodearrintint nnodes array for internal computations
heursourcesarray to store starting points of TM heuristic
nodearrcharSTP_Bool node array for internal computations
nelimspointer to store number of reduced edges
prevroundsnumber of reduction rounds that have been performed already
randnumgenrandom number generator
userecuse recombination heuristic?
extendeduse extended tests?

Definition at line 2861 of file reduce_bnd.c.

References BMScopyMemoryArray, GRAPH::cost, DAMAXDEVIATION_RANDOM_LOWER, DAMAXDEVIATION_RANDOM_UPPER, DEFAULT_DARUNS, DEFAULT_HEURRUNS, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_get4nextTerms(), graph_path_execX(), graph_pc_2org(), graph_pc_2trans(), graph_pc_2transcheck(), graph_sol_getObj(), graph_sol_reroot(), graph_sol_valid(), graph_valid(), graph_voronoiTerms(), Is_term, GRAPH::knots, level0(), GRAPH::mark, stp_solution_pool::maxindex, nnodes, nterms, NULL, stp_solution::obj, GRAPH::oeat, orderDaRoots(), GRAPH::outbeg, GRAPH::path_heap, reduce_deleteConflictEdges(), reduce_extendedEdge(), reduceSPG(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), reduceWithNodeReplaceBounds(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPisZero(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurRecFreePool(), SCIPStpHeurRecInitPool(), SCIPStpHeurRecRun(), SCIPStpHeurRecSolfromIdx(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), stp_solution_pool::size, stp_solution::soledges, SOLPOOL_SIZE, GRAPH::source, STP_NWSPG, STP_RPCSPG, STP_RSMT, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, updateEdgeFixingBounds(), updateNodeFixingBounds(), and updateNodeReplaceBounds().

Referenced by redLoopPc(), redLoopStp(), reduceNw(), and reduceSap().

◆ reduce_daSlackPrune()

SCIP_RETCODE reduce_daSlackPrune ( SCIP scip,
SCIP_VAR **  vars,
GRAPH graph,
PATH vnoi,
GNODE **  gnodearr,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
SCIP_Real upperbound,
int *  edgearrint,
int *  edgearrint2,
int *  vbase,
int *  pathedge,
int *  state,
int *  solnode,
STP_Bool nodearrchar,
STP_Bool edgearrchar,
int *  nelims,
int  minelims,
SCIP_Bool  solgiven 
)

dual ascent reduction for slack-and-prune heuristic

Parameters
scipSCIP data structure
varsproblem variables or NULL
graphgraph data structure
vnoiVoronoi data structure
gnodearrGNODE* terminals array for internal computations or NULL
costarray to store reduced costs
costrevreverse edge costs
pathdistdistance array for shortest path calculations
upperboundpointer to store new upper bound
edgearrintint edges array to store solution value
edgearrint2int edges array for internal computations
vbasearray for Voronoi bases
pathedgearray for predecessor edge on a path
stateint 4 * nnodes array for internal computations
solnodearray of nodes of current solution that is not to be destroyed
nodearrcharSTP_Bool node array for internal computations
edgearrcharSTP_Bool edge array for internal computations
nelimspointer to store number of reduced edges
minelimsminimum number of edges to eliminate
solgivensolution provided?

Definition at line 3279 of file reduce_bnd.c.

References a, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_get4nextTerms(), graph_path_exec(), graph_path_execX(), graph_pc_2org(), graph_pc_2trans(), graph_sol_getObj(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPintListNodeFree(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), SCIPsortReal(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurSlackPruneRun().

◆ reduce_daPcMw()

SCIP_RETCODE reduce_daPcMw ( SCIP scip,
GRAPH graph,
PATH vnoi,
GNODE **  gnodearr,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
int *  vbase,
int *  pathedge,
int *  edgearrint,
int *  state,
STP_Bool nodearrchar,
int *  nelims,
SCIP_Bool  solbasedda,
SCIP_Bool  varyroot,
SCIP_Bool  markroots,
SCIP_Bool  userec,
SCIP_Bool  fastmode,
SCIP_RANDNUMGEN randnumgen,
SCIP_Real  prizesum 
)

dual ascent based reductions for PCSPG and MWCSP

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure array
gnodearrGNODE* terminals array for internal computations or NULL
costreduced edge costs
costrevreduced reverse edge costs
pathdistdistance array for shortest path calculations
vbaseVoronoi base array
pathedgeshortest path incoming edge array for shortest path calculations
edgearrintint edges array for internal computations or NULL
stateint 4 * vertices array
nodearrcharSTP_Bool node array for internal computations
nelimspointer to store number of reduced edges
solbaseddarerun Da based on best primal solution
varyrootvary root for DA if possible
markrootsshould terminals proven to be part of an opt. sol. be marked as such?
userecuse recombination heuristic?
fastmoderun heuristic in fast mode?
randnumgenrandom number generator
prizesumsum of positive prizes

Definition at line 3801 of file reduce_bnd.c.

References BMScopyMemoryArray, computeDaSolPcMw(), computePertubedSol(), computeTransVoronoi(), GRAPH::cost, DAMAXDEVIATION_FAST, DEFAULT_HEURRUNS, DEFAULT_NMAXROOTS, dualCostIsValid(), EAT_LAST, GRAPH::edges, FALSE, FARAWAY, findDaRoots(), flipedge, GRAPH::grad, graph_free(), graph_get2next(), graph_init_history(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_getRsap(), graph_pc_getSap(), graph_sol_getObj(), graph_sol_reroot(), graph_sol_unreduced(), graph_sol_valid(), graph_valid(), graph_voronoiTerms(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, markPcMwRoots(), nnodes, nterms, NULL, stp_solution::obj, GRAPH::oeat, orderDaRoots(), GRAPH::outbeg, GRAPH::path_heap, GRAPH::prize, reducePcMw(), reducePcMwTryBest(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), roots, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPisGT(), SCIPStpDualAscent(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurRecFreePool(), SCIPStpHeurRecInitPool(), SCIPStpHeurTMRun(), SOLPOOL_SIZE, stp_solution_pool::sols, GRAPH::source, STP_MWCSP, STP_RED_MINBNDTERMS, STP_RPCSPG, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, updateEdgeFixingBounds(), and updateNodeFixingBounds().

Referenced by redLoopMw(), and redLoopPc().

◆ reduce_daSlackPruneMw()

SCIP_RETCODE reduce_daSlackPruneMw ( SCIP scip,
GRAPH graph,
PATH vnoi,
GNODE **  gnodearr,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
int *  vbase,
int *  pathedge,
int *  soledge,
int *  state,
int *  solnode,
STP_Bool nodearrchar,
int *  nelims,
int  minelims,
SCIP_Bool  solgiven 
)

dual ascent based heuristic reductions for MWCSP

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure array
gnodearrGNODE* terminals array for internal computations or NULL
costedge costs
costrevreverse edge costs
pathdistdistance array for shortest path calculations
vbaseVoronoi base array
pathedgeshortest path incoming edge array for shortest path calculations
soledgeedge solution array (CONNECT/UNKNOWN) or NULL; needs to contain solution if solgiven == TRUE
stateint 4 * vertices array
solnodearray of nodes of current solution that is not to be destroyed
nodearrcharSTP_Bool node array for internal computations
nelimspointer to store number of reduced edges
minelimsminimum number of edges to eliminate
solgivensolution provided?

Definition at line 4237 of file reduce_bnd.c.

References CONNECT, GRAPH::cost, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_init_history(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_getSap(), graph_sol_getObj(), graph_sol_valid(), graph_voronoiTerms(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfindHeur(), SCIPfreeBufferArray, SCIPheurGetData(), SCIPintListNodeFree(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPprobdataGetOffset(), SCIPsortReal(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurSlackPruneRunPcMw().

◆ reduce_bound()

SCIP_RETCODE reduce_bound ( SCIP scip,
GRAPH graph,
PATH vnoi,
SCIP_Real cost,
SCIP_Real prize,
SCIP_Real radius,
SCIP_Real costrev,
SCIP_Real offset,
SCIP_Real upperbound,
int *  heap,
int *  state,
int *  vbase,
int *  nelims 
)

bound-based reductions for the (R)PCSTP, the MWCSP and the STP

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
costedge cost array
prizeprize (nodes) array
radiusradius array
costrevreversed edge cost array
offsetpointer to the offset
upperboundpointer to an upper bound
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
nelimspointer to store number of eliminated edges

Definition at line 4653 of file reduce_bnd.c.

References BLOCKED, bound, CONNECT, GRAPH::cost, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_get2next(), graph_get3next(), graph_get4next(), graph_get4nextTTerms(), graph_init(), graph_knot_chg(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_deleteTerm(), graph_valid(), graph_voronoiWithRadius(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::prize, r, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPheurGetData(), SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPsortReal(), SCIPsortRealInt(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by redLoopPc(), redLoopStp(), and reduceHc().

◆ reduce_boundMw()

SCIP_RETCODE reduce_boundMw ( SCIP scip,
GRAPH graph,
PATH vnoi,
PATH path,
SCIP_Real cost,
SCIP_Real radius,
SCIP_Real costrev,
SCIP_Real offset,
int *  heap,
int *  state,
int *  vbase,
int *  result,
int *  nelims 
)

Bound-based reduction method for the MWCSP . The reduction method tries to eliminate nodes and vertices by checking whether an upper bound for each solution that contains them is smaller than the best known solution value. The essence of the approach is a decomposition of the graph such that this upper bound is minimized.

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure (size 3 * nnodes)
pathshortest path data structure (size nnodes)
costedge cost array
radiusradius array
costrevreversed edge cost array
offsetpointer to the offset
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
resultsolution array or NULL
nelimspointer to store number of eliminated edges

Definition at line 5243 of file reduce_bnd.c.

References bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_get2next(), graph_voronoiMw(), graph_voronoiWithRadiusMw(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::outbeg, GRAPH::prize, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsortReal(), GRAPH::source, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by redLoopMw().

◆ reduce_boundPrune()

SCIP_RETCODE reduce_boundPrune ( SCIP scip,
GRAPH graph,
PATH vnoi,
SCIP_Real cost,
SCIP_Real radius,
SCIP_Real costrev,
SCIP_Real offset,
int *  heap,
int *  state,
int *  vbase,
const int *  solnode,
const int *  soledge,
int *  nelims,
int  minelims 
)

bound-based reductions for the (R)PCSTP, the MWCSP and the STP; used by prune heuristic

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
costedge cost array
radiusradius array
costrevreversed edge cost array
offsetpointer to the offset
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
solnodearray of nodes of current solution that is not to be destroyed
soledgearray of edges of current solution that is not to be destroyed
nelimspointer to store number of eliminated edges
minelimsminimum number of edges to be eliminated

Definition at line 5415 of file reduce_bnd.c.

References BLOCKED, bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_get2next(), graph_get3next(), graph_init(), graph_knot_chg(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), graph_voronoiMw(), graph_voronoiWithRadius(), GRAPH::head, Is_gterm, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPsortReal(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by SCIPStpHeurPruneRun().

◆ reduce_boundHop()

◆ reduce_boundHopR()

SCIP_RETCODE reduce_boundHopR ( SCIP scip,
GRAPH graph,
PATH vnoi,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
int *  heap,
int *  state,
int *  vbase,
int *  nelims,
int *  pathedge 
)

◆ reduce_boundHopRc()