Scippy

SCIP

Solving Constraint Integer Programs

extreduce_extmstbiased.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file extreduce_extmstbiased.c
17  * @brief extended-reduction specific biased bottleneck distance MST algorithms for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements MST algorithms for extended reduction techniques for Steiner problems, using
21  * the implied bottleneck Steiner distance
22  * Furthermore, one can check for tree bottlenecks.
23  *
24  *
25  * A list of all interface methods can be found in extreduce.h.
26  *
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 // #define SCIP_DEBUG
31 //#define STP_DEBUG_EXT
32 
33 #include <string.h>
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <assert.h>
37 #include "graph.h"
38 #include "portab.h"
39 #include "extreduce.h"
40 
41 
42 
43 
44 
45 /**@name Local methods
46  *
47  * @{
48  */
49 
50 
51 
52 /** Can we (peripherally) rule out simple star of degree 3?
53  * Works by using biased distance */
54 static
56  SCIP* scip, /**< SCIP data structure */
57  const SCIP_Real dists_def[3], /**< distances between adjacent nodes */
58  const SCIP_Real dists_bias[3], /**< biased distances between adjacent nodes */
59  SCIP_Real starcost, /**< cost of the star */
60  SCIP_Bool allowEquality /**< allow equality? */
61 )
62 {
63  if( allowEquality )
64  {
65  if( SCIPisLE(scip, dists_def[0] + dists_bias[1], starcost) )
66  return TRUE;
67  if( SCIPisLE(scip, dists_def[1] + dists_bias[0], starcost) )
68  return TRUE;
69 
70  if( SCIPisLE(scip, dists_def[0] + dists_bias[2], starcost) )
71  return TRUE;
72  if( SCIPisLE(scip, dists_def[2] + dists_bias[0], starcost) )
73  return TRUE;
74 
75  if( SCIPisLE(scip, dists_def[1] + dists_bias[2], starcost) )
76  return TRUE;
77  if( SCIPisLE(scip, dists_def[2] + dists_bias[1], starcost) )
78  return TRUE;
79  }
80  else
81  {
82  if( SCIPisLT(scip, dists_def[0] + dists_bias[1], starcost) )
83  return TRUE;
84  if( SCIPisLT(scip, dists_def[1] + dists_bias[0], starcost) )
85  return TRUE;
86 
87  if( SCIPisLT(scip, dists_def[0] + dists_bias[2], starcost) )
88  return TRUE;
89  if( SCIPisLT(scip, dists_def[2] + dists_bias[0], starcost) )
90  return TRUE;
91 
92  if( SCIPisLT(scip, dists_def[1] + dists_bias[2], starcost) )
93  return TRUE;
94  if( SCIPisLT(scip, dists_def[2] + dists_bias[1], starcost) )
95  return TRUE;
96  }
97 
98  return FALSE;
99 }
100 
101 
102 /** gets biased SDs between leaves */
103 static inline
105  SCIP* scip, /**< SCIP */
106  const GRAPH* graph, /**< graph data structure */
107  EXTDATA* extdata, /**< extension data */
108  SCIP_Real sds_def[3], /**< array to store the SDs */
109  SCIP_Real sds_bias[3] /**< array to store the SDs */
110  )
111 {
112  const int* const leaves = extdata->tree_leaves;
113  const REDDATA* const reddata = extdata->reddata;
114  const MLDISTS* const sds_vertical = reddata->sds_vertical;
115  const MLDISTS* const sdsbias_vertical = reddata->sdsbias_vertical;
116  const int* const extstack_data = extdata->extstack_data;
117  const int stackpos = extStackGetPosition(extdata);
118  const int topedges_start = extStackGetTopOutEdgesStart(extdata, stackpos);
119  const int topedges_end = extStackGetTopOutEdgesEnd(extdata, stackpos);
120  const int ntopleaves = topedges_end - topedges_start;
121  const int topedge1 = extstack_data[topedges_start];
122  int topsibling1 = graph->head[topedge1];
123 
124  assert(1 <= ntopleaves && ntopleaves <= 2);
125 
126  if( ntopleaves == 2 )
127  {
128  const MLDISTS* const sds_horizontal = reddata->sds_horizontal;
129  const MLDISTS* const sdsbias_horizontal = reddata->sdsbias_horizontal;
130  const int topedge2 = extstack_data[topedges_start + 1];
131  int topsibling2 = graph->head[topedge2];
132 
133  assert(graph->tail[topedge1] == graph->tail[topedge2]);
134  assert(topsibling1 != topsibling2);
135  assert(topsibling1 != leaves[0] && topsibling2 != leaves[0]);
136 
137  if( topsibling1 == leaves[2] )
138  {
139  SWAP_INTS(topsibling1, topsibling2);
140  }
141 
142  assert(topsibling1 == leaves[1] && topsibling2 == leaves[2]);
143 
144  /* SDs from root to siblings */
145  sds_def[0] = extreduce_mldistsTopTargetDists(sds_vertical, topsibling1)[0];
146  sds_bias[0] = extreduce_mldistsTopTargetDists(sdsbias_vertical, topsibling1)[0];
147  sds_def[1] = extreduce_mldistsTopTargetDists(sds_vertical, topsibling2)[0];
148  sds_bias[1] = extreduce_mldistsTopTargetDists(sdsbias_vertical, topsibling2)[0];
149 
150  /* SDs between siblings */
151  sds_def[2] = extreduce_mldistsTopTargetDist(sds_horizontal, topsibling1, topsibling2);
152  sds_bias[2] = extreduce_mldistsTopTargetDist(sdsbias_horizontal, topsibling1, topsibling2);
153  }
154  else
155  {
156  DISTDATA* const distdata_default = extdata->distdata;
157  DISTDATA* const distdata_biased = extdata->distdata_biased;
158  assert(topsibling1 == leaves[2]);
159 
160  sds_def[0] = extreduce_distDataGetSdDouble(scip, graph, leaves[0], leaves[1], distdata_default);
161  sds_bias[0] = extreduce_distDataGetSdDouble(scip, graph, leaves[0], leaves[1], distdata_biased);
162 
163  sds_def[1] = extreduce_mldistsTopTargetDists(sds_vertical, topsibling1)[0];
164  sds_bias[1] = extreduce_mldistsTopTargetDists(sdsbias_vertical, topsibling1)[0];
165 
166  sds_def[2] = extreduce_mldistsTopTargetDists(sds_vertical, topsibling1)[1];
167  sds_bias[2] = extreduce_mldistsTopTargetDists(sdsbias_vertical, topsibling1)[1];
168  }
169 }
170 
171 
172 /**@} */
173 
174 /**@name Interface methods
175  *
176  * @{
177  */
178 
179 
180 
181 /** can current 3-leaf tree be ruled-out? */
183  SCIP* scip, /**< SCIP */
184  const GRAPH* graph, /**< graph data structure */
185  SCIP_Real tree_cost, /**< tree cost */
186  EXTDATA* extdata /**< extension data */
187 )
188 {
190  SCIP_Real dists_def[3];
191  SCIP_Real dists_bias[3];
192 
193  assert(scip && graph && extdata);
194  assert(GE(tree_cost, 0.0));
195  assert(extdata->tree_nleaves == 3);
196 
197  mst3LeafTreeGetSds(scip, graph, extdata, dists_def, dists_bias);
198 
199 #ifndef NDEBUG
200  {
201  DISTDATA* distdata_default = extdata->distdata;
202  DISTDATA* distdata_biased = extdata->distdata_biased;
203  const int* const leaves = extdata->tree_leaves;
204 
205  assert(EQ(dists_def[0], extreduce_distDataGetSdDouble(scip, graph, leaves[0], leaves[1], distdata_default)));
206  assert(EQ(dists_def[1], extreduce_distDataGetSdDouble(scip, graph, leaves[0], leaves[2], distdata_default)));
207  assert(EQ(dists_def[2], extreduce_distDataGetSdDouble(scip, graph, leaves[1], leaves[2], distdata_default)));
208 
209  assert(EQ(dists_bias[0], extreduce_distDataGetSdDouble(scip, graph, leaves[0], leaves[1], distdata_biased)));
210  assert(EQ(dists_bias[1], extreduce_distDataGetSdDouble(scip, graph, leaves[0], leaves[2], distdata_biased)));
211  assert(EQ(dists_bias[2], extreduce_distDataGetSdDouble(scip, graph, leaves[1], leaves[2], distdata_biased)));
212  }
213 #endif
214 
215  if( mst3StarNeighborRuleOut(scip, dists_def, dists_bias, tree_cost, FALSE) )
216  {
217  SCIPdebugMessage("biased 3-leaf MST rule-out \n");
218  ruledOut = TRUE;
219  }
220 
221  return ruledOut;
222 }
223 
224 
225 /** checks node of degree 3 for possible pseudo-elimination by using bias bottleneck Steiner distance */
227  SCIP* scip, /**< SCIP data structure */
228  const GRAPH* graph, /**< graph data structure */
229  int node, /**< the node */
230  DISTDATA* distdata_default, /**< data for distance computations */
231  DISTDATA* distdata_biased, /**< data for distance computations */
232  SCIP_Bool* isPseudoDeletable /**< is node pseudo-deletable? */
233 )
234 {
235  SCIP_Real dists_def[3];
236  SCIP_Real dists_bias[3];
237  int neighbors[3];
238  int edgecount = 0;
239  SCIP_Real starcost = 0.0;
240 
241  assert(scip && graph && distdata_default && distdata_biased && isPseudoDeletable);
242  assert(distdata_biased->sdistdata && distdata_biased->sdistdata->sdprofit);
243  assert(*isPseudoDeletable == FALSE);
244  assert(graph_knot_isInRange(graph, node));
245  assert(!Is_term(graph->term[node]));
246  assert(graph->grad[node] == 3);
247  assert(!graph_pc_isPcMw(graph));
248  assert(EQ(reduce_sdprofitGetProfit(distdata_biased->sdistdata->sdprofit, node, -1, -1), 0.0));
249 
250  for( int e = graph->outbeg[node]; e != EAT_LAST; e = graph->oeat[e] )
251  {
252  assert(EQ(graph->cost[e], graph->cost[flipedge(e)]));
253 
254  neighbors[edgecount++] = graph->head[e];
255  starcost += graph->cost[e];
256  }
257 
258  assert(edgecount == 3);
259 
260  dists_def[0] = extreduce_distDataGetSdDouble(scip, graph, neighbors[0], neighbors[1], distdata_default);
261  dists_def[1] = extreduce_distDataGetSdDouble(scip, graph, neighbors[0], neighbors[2], distdata_default);
262  dists_def[2] = extreduce_distDataGetSdDouble(scip, graph, neighbors[1], neighbors[2], distdata_default);
263 
264  dists_bias[0] = extreduce_distDataGetSdDouble(scip, graph, neighbors[0], neighbors[1], distdata_biased);
265  dists_bias[1] = extreduce_distDataGetSdDouble(scip, graph, neighbors[0], neighbors[2], distdata_biased);
266  dists_bias[2] = extreduce_distDataGetSdDouble(scip, graph, neighbors[1], neighbors[2], distdata_biased);
267 
268  *isPseudoDeletable = mst3StarNeighborRuleOut(scip, dists_def, dists_bias, starcost, TRUE);
269 
270  return SCIP_OKAY;
271 }
272 
273 /**@} */
int *RESTRICT head
Definition: graphdefs.h:224
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Real extreduce_distDataGetSdDouble(SCIP *, const GRAPH *, int, int, DISTDATA *)
static SCIP_Bool isPseudoDeletable(SCIP *scip, const GRAPH *g, const GRAPH *auxg, const SCIP_Real *ecost, const int *edges, int degree)
Definition: reduce_sd.c:1033
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
#define SWAP_INTS(int1, int2)
Definition: misc_stp.h:34
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
int *const extstack_data
static int extStackGetTopOutEdgesStart(const EXTDATA *extdata, int stackpos)
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
static int extStackGetTopOutEdgesEnd(const EXTDATA *extdata, int stackpos)
static int extStackGetPosition(const EXTDATA *extdata)
SCIP_RETCODE extreduce_mstbiasedCheck3NodeSimple(SCIP *scip, const GRAPH *graph, int node, DISTDATA *distdata_default, DISTDATA *distdata_biased, SCIP_Bool *isPseudoDeletable)
REDDATA *const reddata
static SCIP_Bool mst3StarNeighborRuleOut(SCIP *scip, const SCIP_Real dists_def[3], const SCIP_Real dists_bias[3], SCIP_Real starcost, SCIP_Bool allowEquality)
int *const tree_leaves
int *RESTRICT oeat
Definition: graphdefs.h:231
This file implements extended reduction techniques for several Steiner problems.
#define GE(a, b)
Definition: portab.h:85
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int *RESTRICT grad
Definition: graphdefs.h:201
#define EQ(a, b)
Definition: portab.h:79
DISTDATA *const distdata_biased
SCIP_Real extreduce_mldistsTopTargetDist(const MLDISTS *, int, int)
static SCIP_Real reduce_sdprofitGetProfit(const SDPROFIT *sdprofit, int node, int nonsource1, int nonsource2)
Definition: reducedefs.h:178
#define SCIP_Bool
Definition: def.h:84
const SCIP_Real * extreduce_mldistsTopTargetDists(const MLDISTS *, int)
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
SCIP_Bool extreduce_mstbiased3LeafTreeRuleOut(SCIP *scip, const GRAPH *graph, SCIP_Real tree_cost, EXTDATA *extdata)
int *RESTRICT term
Definition: graphdefs.h:196
Portable definitions.
DISTDATA *const distdata
SCIP_Real * cost
Definition: graphdefs.h:221
static SCIP_Bool ruledOut(SCIP *scip, const GRAPH *graph, EXTDATA *extdata)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
#define SCIP_Real
Definition: def.h:177
MLDISTS *const sds_vertical
int *RESTRICT outbeg
Definition: graphdefs.h:204
MLDISTS *const sdsbias_vertical
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
MLDISTS *const sds_horizontal
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
MLDISTS *const sdsbias_horizontal
static void mst3LeafTreeGetSds(SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Real sds_def[3], SCIP_Real sds_bias[3])