Solving Constraint Integer Programs

extreduce_extmstbiased.c File Reference

Detailed Description

extended-reduction specific biased bottleneck distance MST algorithms for Steiner tree problems

Daniel Rehfeldt

This file implements MST algorithms for extended reduction techniques for Steiner problems, using the implied bottleneck Steiner distance Furthermore, one can check for tree bottlenecks.

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

Definition in file extreduce_extmstbiased.c.

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

Go to the source code of this file.


Local methods
static SCIP_Bool mst3StarNeighborRuleOut (SCIP *scip, const SCIP_Real dists_def[3], const SCIP_Real dists_bias[3], SCIP_Real starcost, SCIP_Bool allowEquality)
static void mst3LeafTreeGetSds (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Real sds_def[3], SCIP_Real sds_bias[3])
Interface methods
SCIP_Bool extreduce_mstbiased3LeafTreeRuleOut (SCIP *scip, const GRAPH *graph, SCIP_Real tree_cost, EXTDATA *extdata)
SCIP_RETCODE extreduce_mstbiasedCheck3NodeSimple (SCIP *scip, const GRAPH *graph, int node, DISTDATA *distdata_default, DISTDATA *distdata_biased, SCIP_Bool *isPseudoDeletable)

Function Documentation

◆ mst3StarNeighborRuleOut()

static SCIP_Bool mst3StarNeighborRuleOut ( SCIP scip,
const SCIP_Real  dists_def[3],
const SCIP_Real  dists_bias[3],
SCIP_Real  starcost,
SCIP_Bool  allowEquality 

Can we (peripherally) rule out simple star of degree 3? Works by using biased distance

scipSCIP data structure
dists_defdistances between adjacent nodes
dists_biasbiased distances between adjacent nodes
starcostcost of the star
allowEqualityallow equality?

Definition at line 55 of file extreduce_extmstbiased.c.

References FALSE, SCIPisLE(), SCIPisLT(), and TRUE.

Referenced by extreduce_mstbiased3LeafTreeRuleOut(), and extreduce_mstbiasedCheck3NodeSimple().

◆ mst3LeafTreeGetSds()

static void mst3LeafTreeGetSds ( SCIP scip,
const GRAPH graph,
EXTDATA extdata,
SCIP_Real  sds_def[3],
SCIP_Real  sds_bias[3] 

◆ extreduce_mstbiased3LeafTreeRuleOut()

SCIP_Bool extreduce_mstbiased3LeafTreeRuleOut ( SCIP scip,
const GRAPH graph,
SCIP_Real  tree_cost,
EXTDATA extdata 

can current 3-leaf tree be ruled-out?

graphgraph data structure
tree_costtree cost
extdataextension data

Definition at line 182 of file extreduce_extmstbiased.c.

References extension_data::distdata, extension_data::distdata_biased, EQ, extreduce_distDataGetSdDouble(), FALSE, GE, mst3LeafTreeGetSds(), mst3StarNeighborRuleOut(), ruledOut(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by mstCompRuleOut().

◆ extreduce_mstbiasedCheck3NodeSimple()

SCIP_RETCODE extreduce_mstbiasedCheck3NodeSimple ( SCIP scip,
const GRAPH graph,
int  node,
DISTDATA distdata_default,
DISTDATA distdata_biased,
SCIP_Bool isPseudoDeletable 

checks node of degree 3 for possible pseudo-elimination by using bias bottleneck Steiner distance

scipSCIP data structure
graphgraph data structure
nodethe node
distdata_defaultdata for distance computations
distdata_biaseddata for distance computations
isPseudoDeletableis node pseudo-deletable?

Definition at line 226 of file extreduce_extmstbiased.c.

References GRAPH::cost, EAT_LAST, EQ, extreduce_distDataGetSdDouble(), FALSE, flipedge, GRAPH::grad, graph_knot_isInRange(), graph_pc_isPcMw(), GRAPH::head, Is_term, mst3StarNeighborRuleOut(), GRAPH::oeat, GRAPH::outbeg, reduce_sdprofitGetProfit(), SCIP_OKAY, SCIP_Real, distance_data::sdistdata, special_distance_storage::sdprofit, GRAPH::term, and TRUE.

Referenced by pseudodeleteExecute(), and testNode3PseudoDeletedBySdBiasedSimple().