Scippy

SCIP

Solving Constraint Integer Programs

extreduce_extspg.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_extspg.c
17  * @brief extended-reduction specific SPG algorithms for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements special distance Steiner tree algorithms for extended reduction techniques for Steiner problems.
21  * Allows one to efficiently compute and store special distance (SD) Steiner trees between the leaves of extension tree.
22  *
23  * A list of all interface methods can be found in extreduce.h.
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 // #define SCIP_DEBUG
29 //#define STP_DEBUG_EXT
30 
31 #include <string.h>
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <assert.h>
35 #include "graph.h"
36 #include "portab.h"
37 #include "extreduce.h"
38 
39 
40 #define STP_EXTSPG_MAXNCHECKS_EQ 8
41 #define STP_EXTSPG_MAXNCHECKS 4
42 
43 
44 /**@name Local methods
45  *
46  * @{
47  */
48 
49 
50 
51 /** ruled out possible by using interior point on path between 'pathstart' and 'pathend'? */
52 static inline
54  SCIP* scip, /**< SCIP */
55  const GRAPH* graph, /**< graph data structure */
56  int node_pathstart, /**< start of path */
57  int node_pathend, /**< end of path */
58  int node_other, /**< other node */
59  SCIP_Real tree_cost, /**< tree cost */
60  int* pathnodes, /**< buffer */
61  EXTDATA* extdata /**< extension data */
62 )
63 {
64  DISTDATA* const distdata = extdata->distdata;
65  const int* const tree_deg = extdata->tree_deg;
66  int npathnodes;
67  const SCIP_Real pathcost
68  = extreduce_distDataGetSp(scip, graph, node_pathstart, node_pathend, pathnodes, &npathnodes, distdata);
69 
70  SCIP_Bool isRuledOut = FALSE;
71 
72  assert(tree_deg[node_pathstart] > 0);
73  assert(tree_deg[node_pathend] > 0);
74  assert(tree_deg[node_other] > 0);
75 
76  if( GE(pathcost, tree_cost) )
77  {
78  return FALSE;
79  }
80 
81  SCIPdebugMessage("%d---%d and %d: number of path nodes: %d (pathcost=%f, tree_cost=%f)\n",
82  node_pathstart, node_pathend, node_other, npathnodes, pathcost, tree_cost);
83 
84  for( int i = 0; i < npathnodes; i++ )
85  {
86  SCIP_Real dist2;
87  const int node_middle = pathnodes[i];
88 
89  assert(GE(pathcost, 0.0));
90 
91  if( tree_deg[node_middle] > 0 )
92  continue;
93 
94  dist2 = extreduce_distDataGetSdDouble(scip, graph, node_middle, node_other, distdata);
95 
96  if( dist2 < -0.5 )
97  {
98  assert(EQ(dist2, -1.0));
99  assert(graph_pc_isPc(graph));
100 
101  continue;
102  }
103 
104  if( LT(pathcost + dist2, tree_cost) )
105  {
106  SCIPdebugMessage("STEINER TREE 3-leaf tree rule-out with %f < %f \n", pathcost + dist2, tree_cost);
107 
108  isRuledOut = TRUE;
109  break;
110  }
111  }
112 
113  return isRuledOut;
114 }
115 
116 
117 
118 /** Can we (peripherally) rule out simple star of degree 3?
119  * Works by using simple Steiner tree */
120 static
122  SCIP* scip, /**< SCIP data structure */
123  const GRAPH* graph, /**< graph data structure */
124  SCIP_Real starcost, /**< cost of the star */
125  int node, /**< the node */
126  SCIP_Bool allowEquality, /**< allow equality? */
127  const int neighbors[3], /**< the neighbors */
128  DISTDATA* distdata /**< data for distance computations */
129 )
130 {
132  const SCIP_Bool isPc = graph_pc_isPc(graph);
133  const int maxnchecks = allowEquality ? STP_EXTSPG_MAXNCHECKS_EQ : STP_EXTSPG_MAXNCHECKS;
134 
135  for( int i = 0; i < 3 && !isPseudoDeletable; i++ )
136  {
137  const int n0 = neighbors[i];
138  const int n1 = neighbors[(i + 1) % 3];
139  const int n2 = neighbors[(i + 2) % 3];
140  int edgecount = 0;
141 
142  assert(n1 != n0 && n2 != n0);
143 
144  for( int e = graph->outbeg[n0]; e != EAT_LAST; e = graph->oeat[e] )
145  {
146  const int head = graph->head[e];
147  SCIP_Real c0;
148  SCIP_Real c1;
149  SCIP_Real c2;
150 
151  if( head == node )
152  continue;
153 
154  if( head == n1 || head == n2 )
155  continue;
156 
157  if( isPc && Is_pseudoTerm(graph->term[head]) )
158  continue;
159 
160  if( edgecount++ > maxnchecks )
161  break;
162 
163  c0 = graph->cost[e];
164  c1 = extreduce_distDataGetSdDouble(scip, graph, head, n1, distdata);
165 
166  if( isPc && c1 < -0.5 )
167  {
168  assert(EQ(c1, -1.0));
169  continue;
170  }
171 
172  if( allowEquality ? GT(c0 + c1, starcost) : GE(c0 + c1, starcost) )
173  continue;
174 
175  c2 = extreduce_distDataGetSdDouble(scip, graph, head, n2, distdata);
176 
177  if( isPc && c2 < -0.5 )
178  {
179  assert(EQ(c2, -1.0));
180  continue;
181  }
182 
183  assert(GE(c1, 0.0) && GE(c2, 0.0));
184 
185  if( allowEquality ? LE(c0 + c1 + c2, starcost) : LT(c0 + c1 + c2, starcost) )
186  {
187  SCIPdebugMessage("STEINER TREE pseudo-delete %d with %f %f \n", node, c0 + c1 + c2, starcost);
188  isPseudoDeletable = TRUE;
189  break;
190  }
191  }
192  }
193 
194  return isPseudoDeletable;
195 }
196 
197 
198 /**@} */
199 
200 /**@name Interface methods
201  *
202  * @{
203  */
204 
205 
206 /** can current 3-leaf tree be ruled-out? */
208  SCIP* scip, /**< SCIP */
209  const GRAPH* graph, /**< graph data structure */
210  SCIP_Real tree_cost, /**< tree cost */
211  EXTDATA* extdata /**< extension data */
212 )
213 {
214  int* pathnodes;
215  const int* const leaves = extdata->tree_leaves;
216 
217  assert(scip && graph && extdata);
218  assert(extdata->tree_nleaves == 3);
219  assert(extInitialCompIsEdge(extdata));
220  assert(GE(tree_cost, 0.0));
221 
222  SCIPdebugMessage("try 3-leaf reduction by SD SPG \n");
223 
224  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &pathnodes, graph->knots) );
225 
226  if( spg4VerticesRuleOut(scip, graph, leaves[0], leaves[1], leaves[2], tree_cost, pathnodes, extdata) )
227  {
228  SCIPfreeBufferArray(scip, &pathnodes);
229  return TRUE;
230  }
231 
232  if( spg4VerticesRuleOut(scip, graph, leaves[0], leaves[2], leaves[1], tree_cost, pathnodes, extdata) )
233  {
234  SCIPfreeBufferArray(scip, &pathnodes);
235  return TRUE;
236  }
237 
238  if( spg4VerticesRuleOut(scip, graph, leaves[1], leaves[2], leaves[0], tree_cost, pathnodes, extdata) )
239  {
240  SCIPfreeBufferArray(scip, &pathnodes);
241  return TRUE;
242  }
243 
244  SCIPfreeBufferArray(scip, &pathnodes);
245 
246  return FALSE;
247 }
248 
249 
250 
251 /** checks component for possible pseudo-elimination by using simple Steiner tree */
253  SCIP* scip, /**< SCIP data structure */
254  const GRAPH* graph, /**< graph data structure */
255  int node, /**< the node */
256  const EXTCOMP* extcomp, /**< component to be checked */
257  SCIP_Bool allowEquality, /**< allow equality? */
258  DISTDATA* distdata, /**< data for distance computations */
259  SCIP_Bool* isPseudoDeletable /**< is component pseudo-deletable? */
260 )
261 {
262  int neighbors[3];
263  SCIP_Real starcost = 0.0;
264 
265  assert(scip && graph && distdata && isPseudoDeletable);
266  assert(*isPseudoDeletable == FALSE);
267  assert(graph_knot_isInRange(graph, node));
268  assert(!Is_term(graph->term[node]) || graph_pc_isPc(graph));
269  /* NOTE: because the component has been reverted... */
270  assert(extcomp->nextleaves == 1);
271  assert(extcomp->ncompedges == 3);
272  assert(graph->head[extcomp->compedges[0]] == node);
273  assert(graph->tail[extcomp->compedges[0]] == extcomp->comproot);
274 
275  neighbors[0] = extcomp->comproot;
276  for( int i = 0; i < 2; i++ )
277  {
278  const int leaf = extcomp->extleaves[i];
279  assert(graph_knot_isInRange(graph, leaf));
280  assert(leaf != neighbors[0]);
281 
282  neighbors[i + 1] = leaf;
283  }
284 
285  for( int i = 0; i < 3; i++ )
286  {
287  const int edge = extcomp->compedges[i];
288  assert(graph_edge_isInRange(graph, edge));
289  assert(EQ(graph->cost[edge], graph->cost[flipedge(edge)]));
290 
291  starcost += graph->cost[edge];
292  }
293 
294  if( graph_pc_isPc(graph) )
295  {
296  assert(GE(graph->prize[node], 0.0));
297  starcost -= graph->prize[node];
298 
299  assert(GE(starcost, 0.0));
300  }
301 
302  *isPseudoDeletable = spg3StarNeighborRuleOut(scip, graph, starcost, node, allowEquality, neighbors, distdata);
303 
304  return SCIP_OKAY;
305 }
306 
307 
308 
309 /** checks node of degree 3 for possible pseudo-elimination by using simple Steiner tree */
311  SCIP* scip, /**< SCIP data structure */
312  const GRAPH* graph, /**< graph data structure */
313  int node, /**< the node */
314  DISTDATA* distdata, /**< data for distance computations */
315  SCIP_Bool* isPseudoDeletable /**< is node pseudo-deletable? */
316 )
317 {
318  int neighbors[3];
319  int edgecount = 0;
320  SCIP_Real starcost = 0.0;
321 
322  assert(scip && graph && distdata && isPseudoDeletable);
323  assert(*isPseudoDeletable == FALSE);
324  assert(graph_knot_isInRange(graph, node));
325  assert(!Is_term(graph->term[node]));
326  assert(graph->grad[node] == 3);
327 
328  for( int e = graph->outbeg[node]; e != EAT_LAST; e = graph->oeat[e] )
329  {
330  assert(EQ(graph->cost[e], graph->cost[flipedge(e)]));
331 
332  neighbors[edgecount++] = graph->head[e];
333  starcost += graph->cost[e];
334  }
335 
336  assert(edgecount == 3);
337 
338  *isPseudoDeletable = spg3StarNeighborRuleOut(scip, graph, starcost, node, TRUE, neighbors, distdata);
339 
340  return SCIP_OKAY;
341 }
342 
343 /**@} */
SCIP_Real extreduce_distDataGetSp(SCIP *, const GRAPH *, int, int, int *, int *, DISTDATA *)
int *RESTRICT head
Definition: graphdefs.h:224
#define STP_EXTSPG_MAXNCHECKS
#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
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
static SCIP_Bool extInitialCompIsEdge(const EXTDATA *extdata)
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
int *const tree_leaves
int *RESTRICT oeat
Definition: graphdefs.h:231
This file implements extended reduction techniques for several Steiner problems.
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
#define STP_EXTSPG_MAXNCHECKS_EQ
SCIP_Real * prize
Definition: graphdefs.h:210
int *RESTRICT grad
Definition: graphdefs.h:201
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define LT(a, b)
Definition: portab.h:81
SCIP_Bool extreduce_spg3LeafTreeRuleOut(SCIP *scip, const GRAPH *graph, SCIP_Real tree_cost, EXTDATA *extdata)
SCIP_RETCODE extreduce_spgCheck3ComponentSimple(SCIP *scip, const GRAPH *graph, int node, const EXTCOMP *extcomp, SCIP_Bool allowEquality, DISTDATA *distdata, SCIP_Bool *isPseudoDeletable)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE extreduce_spgCheck3NodeSimple(SCIP *scip, const GRAPH *graph, int node, DISTDATA *distdata, SCIP_Bool *isPseudoDeletable)
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
static SCIP_Bool spg4VerticesRuleOut(SCIP *scip, const GRAPH *graph, int node_pathstart, int node_pathend, int node_other, SCIP_Real tree_cost, int *pathnodes, EXTDATA *extdata)
int *RESTRICT term
Definition: graphdefs.h:196
SCIP_Bool graph_pc_isPc(const GRAPH *)
Portable definitions.
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
DISTDATA *const distdata
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
#define SCIP_Real
Definition: def.h:177
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
int *const tree_deg
static SCIP_Bool spg3StarNeighborRuleOut(SCIP *scip, const GRAPH *graph, SCIP_Real starcost, int node, SCIP_Bool allowEquality, const int neighbors[3], DISTDATA *distdata)
#define SCIP_CALL_ABORT(x)
Definition: def.h:363