Scippy

SCIP

Solving Constraint Integer Programs

reduce_simple.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-2020 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file reduce_simple.c
17  * @brief several basic reductions for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements basic reduction techniques for several Steiner problems.
21  * All tests are described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.
22  *
23  * A list of all interface methods can be found in grph.h.
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <assert.h>
32 #include "grph.h"
33 #include "portab.h"
34 #include "scip/scip.h"
35 
36 #ifndef NDEBUG
37 /** check whether problem has adjacent terminals */
38 static
39 SCIP_Bool adjterms(
40  const GRAPH* g /**< graph data structure */
41 )
42 {
43  for( int e = 0; e < g->edges; e++ )
44  {
45  if( g->oeat[e] != EAT_FREE )
46  {
47  const int tail = g->tail[e];
48  const int head = g->head[e];
49  if( Is_term(g->term[tail]) && Is_term(g->term[head]) && g->mark[head] && g->mark[tail] )
50  return TRUE;
51  }
52  }
53 
54  return FALSE;
55 }
56 #endif
57 
58 /** count numbers of chains */
59 static
60 unsigned nchains(
61  const GRAPH* g /**< graph data structure */
62  )
63 {
64  unsigned ccount = 0;
65  for( int e = 0; e < g->edges; e++ )
66  {
67  if( g->oeat[e] != EAT_FREE )
68  {
69  const int tail = g->tail[e];
70  const int head = g->head[e];
71  if( !Is_term(g->term[tail]) && !Is_term(g->term[head]) && g->grad[head] == 2 && g->grad[tail] == 2 )
72  ccount++;
73  }
74  }
75  return ccount;
76 }
77 
78 /** is there no vertex of higher prize? */
79 static
80 SCIP_Bool is_maxprize(
81  SCIP* scip, /**< SCIP data structure */
82  const GRAPH* g, /**< graph data structure */
83  int i, /**< the terminal to be checked */
84  SCIP_Real* maxprize /**< stores incumbent prize (can be updated) */
85  )
86 {
87  int t = -1;
88  SCIP_Real max;
89 
90  assert(i >= 0 && Is_term(g->term[i]) && g->prize[i] > 0.0);
91 
92  if( g->stp_type == STP_RPCSPG && i != g->source )
93  return FALSE;
94  else if( g->stp_type == STP_RPCSPG && i == g->source )
95  return TRUE;
96 
97  max = *maxprize;
98 
99  if( max > g->prize[i] )
100  return FALSE;
101 
102  max = -1.0;
103 
104  for( int k = 0; k < g->knots; k++ )
105  {
106  if( Is_term(g->term[k]) && g->mark[k] && g->grad[k] > 0 )
107  {
108  assert(k != g->source);
109  if( g->prize[k] > max )
110  {
111  max = g->prize[k];
112  t = k;
113  }
114  else if( t == i && g->prize[k] >= max )
115  {
116  t = k;
117  }
118  }
119  }
120 
121  *maxprize = max;
122 
123  SCIPdebugMessage("maxprize: %f (from %d) \n", g->prize[t], t );
124  return (t == i);
125 }
126 
127 /** try to eliminate a terminal of degree one */
128 static
129 SCIP_RETCODE trydg1edgepc(
130  SCIP* scip, /**< SCIP data structure */
131  GRAPH* g, /**< graph data structure */
132  SCIP_Real* offset, /**< pointer to store the offset */
133  int* solnode, /**< solution nodes or NULL */
134  int* count, /**< pointer storing number of eliminated edges */
135  int i, /**< the terminal to be checked */
136  int iout, /**< outgoing arc */
137  SCIP_Bool* rerun, /**< further eliminations possible? */
138  SCIP_Real* maxprize /**< stores incumbent prize (can be updated) */
139  )
140 {
141  int i1;
142  int degsum;
143 
144  assert(scip != NULL);
145  assert(g != NULL);
146  assert(count != NULL);
147  assert(Is_term(g->term[i]));
148 
149  if( is_maxprize(scip, g, i, maxprize) )
150  return SCIP_OKAY;
151 
152  i1 = g->head[iout];
153 
154  if( SCIPisLE(scip, g->prize[i], g->cost[iout]) && g->stp_type != STP_MWCSP )
155  {
156  /* delete terminal */
157 
158  if( (i1 < i) && (Is_term(g->term[i1]) || g->grad[i1] == 2 || g->grad[i1] == 3) )
159  (*rerun) = TRUE;
160  SCIPdebugMessage("Delete (degree 1) terminal %d \n", i);
161  (*offset) += g->prize[i];
162  (*count) += graph_pc_deleteTerm(scip, g, i);
163  }
164  else
165  {
166  /* contract terminal */
167 
168  (*rerun) = TRUE;
169  assert(SCIPisGT(scip, g->prize[i], 0.0 ));
170 
171  if( g->stp_type == STP_MWCSP )
172  {
173  if( SCIPisLE(scip, g->prize[i], -g->prize[i1]) )
174  *offset += g->prize[i];
175  else
176  *offset -= g->prize[i1];
177  }
178  else
179  {
180  *offset += g->cost[iout];
181  }
182 
183  if( g->source == i1 )
184  {
185  assert(g->stp_type == STP_RPCSPG );
186 
187  if( g->pcancestors[i] != NULL )
188  {
189  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->pcancestors[i], NULL) );
190  SCIPintListNodeFree(scip, &(g->pcancestors[i]));
191  }
192  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[iout], NULL) );
193  (*count) += graph_pc_deleteTerm(scip, g, i);
194  return SCIP_OKAY;
195  }
196 
197  degsum = g->grad[i] + g->grad[i1];
198 
199  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i, i1, i) );
200 
201  degsum -= g->grad[i];
202 
203  assert(degsum >= 1);
204 
205  if( g->stp_type == STP_MWCSP )
206  {
207  int e;
208  int t = UNKNOWN;
209  int e2 = UNKNOWN;
210  if( SCIPisLE(scip, g->prize[i], 0.0) )
211  {
212  for (e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e])
213  {
214  i1 = g->head[e];
215  if( Is_pterm(g->term[i1]) && g->source != i1 )
216  t = i1;
217  else if( g->source == i1 )
218  e2 = e;
219  }
220 
221  assert(t != UNKNOWN);
222  assert(e2 != UNKNOWN);
223 
224  /* delete artificial terminal */
225  graph_pc_knot2nonTerm(g, t);
226  while (g->outbeg[t] != EAT_LAST)
227  {
228  e = g->outbeg[t];
229  g->cost[e] = 0.0;
230  g->cost[flipedge(e)] = 0.0;
231  graph_edge_del(scip, g, e, TRUE);
232  (*count)++;
233  }
234 
235  assert(g->grad[t] == 0);
236 
237  /* i is not a terminal anymore */
238  graph_pc_knot2nonTerm(g, i);
239  graph_edge_del(scip, g, e2, TRUE);
240 
241  for (e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e])
242  if( g->mark[g->tail[e]] )
243  g->cost[e] = -g->prize[i];
244 
245  for (e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e])
246  {
247  i1 = g->head[e];
248  if( g->mark[i1] )
249  {
250  if( !Is_term(g->term[i1]) )
251  {
252  g->cost[e] = -g->prize[i1];
253  }
254  else
255  {
256  g->cost[e] = 0.0;
257  }
258  }
259  }
260  }
261  else
262  {
263  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
264  if( g->mark[g->tail[e]] )
265  g->cost[e] = 0.0;
266 
267  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
268  {
269  i1 = g->head[e];
270  if( g->mark[i1] )
271  {
272  if( !Is_term(g->term[i1]) )
273  {
274  assert(SCIPisLE(scip, g->prize[i1], 0.0));
275  g->cost[e] = -g->prize[i1];
276  }
277  else
278  {
279  assert(SCIPisGE(scip, g->prize[i1], 0.0));
280  g->cost[e] = 0.0;
281  }
282  }
283  else if( Is_pterm(g->term[i1]) && g->source != i1 )
284  {
285  t = i1;
286  }
287 
288  }
289  assert(t != UNKNOWN);
290 
291  for (e = g->inpbeg[t]; e != EAT_LAST; e = g->ieat[e])
292  if( g->tail[e] == g->source )
293  break;
294  assert(e != EAT_LAST);
295  g->cost[e] = g->prize[i];
296  }
297  }
298  (*count) += degsum;
299  }
300  return SCIP_OKAY;
301 }
302 
303 
304 /** traverse one side of a chain (MWCSP) */
305 static
306 SCIP_RETCODE traverseChain(
307  SCIP* scip, /**< SCIP data structure */
308  GRAPH* g, /**< graph data structure */
309  int* length, /**< pointer to store length of chain */
310  int* final, /**< pointer to store final vertex */
311  int i, /**< start vertex */
312  int i1, /**< first vertex */
313  int i2, /**< last vertex */
314  int e1 /**< first edge */
315  )
316 {
317  IDX* ancestors = NULL;
318  IDX* revancestors = NULL;
319  SCIP_Real sum;
320  int k;
321  int e;
322 
323  assert(g != NULL);
324  assert(scip != NULL);
325  assert(length != NULL);
326 
327  k = i1;
328  e = e1;
329  sum = 0.0;
330 
331  while( g->grad[k] == 2 && !Is_term(g->term[k]) && k != i2 )
332  {
333  assert(g->mark[k]);
334 
335  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e], NULL) );
336  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[flipedge(e)], NULL) );
337 
338  if( e != e1 )
339  graph_edge_del(scip, g, e, TRUE);
340 
341  e = g->outbeg[k];
342  sum += g->prize[k];
343  (*length)++;
344 
345  if( e == flipedge(e1) )
346  e = g->oeat[e];
347 
348  assert(e != EAT_LAST);
349  assert(SCIPisLE(scip, g->prize[k], 0.0));
350 
351  k = g->head[e];
352  }
353  if( k != i1 )
354  {
355  int ne;
356 
357  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e], NULL) );
358  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[flipedge(e)], NULL) );
359 
360  graph_edge_del(scip, g, e, TRUE);
361 
362  g->prize[i] += sum;
363  ne = graph_edge_redirect(scip, g, e1, i, k, 1.0, TRUE);
364 
365  if( ne != -1 )
366  {
367  e1 = ne;
368 
369  SCIPintListNodeFree(scip, &(g->ancestors[e1]));
370  SCIPintListNodeFree(scip, &(g->ancestors[flipedge(e1)]));
371 
372  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), ancestors, NULL) );
373  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(e1)]), revancestors, NULL) );
374 
375  }
376  else
377  {
378  for( e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
379  if( g->head[e1] == k )
380  break;
381  assert(e1 != EAT_LAST);
382  }
383 
384  SCIPintListNodeFree(scip, &(ancestors));
385  SCIPintListNodeFree(scip, &(revancestors));
386 
387  if( SCIPisGE(scip, g->prize[k], 0.0) )
388  g->cost[e1] = 0.0;
389  else
390  g->cost[e1] = -g->prize[k];
391  assert(SCIPisLE(scip, g->prize[i], 0.0) );
392  }
393 
394  *final = k;
395 
396  return SCIP_OKAY;
397 }
398 
399 
400 /** adjust for a (rooted) PC or MW problem */
401 static
402 void adjust0term(
403  SCIP* scip, /**< SCIP data structure */
404  GRAPH* g, /**< graph data structure */
405  int i /**< index of the terminal */
406  )
407 {
408  int t;
409  int e2;
410 
411  assert(Is_term(g->term[i]));
412  assert(g->source != i);
413  assert(SCIPisZero(scip, g->prize[i]));
414 
415  t = UNKNOWN;
416  e2 = UNKNOWN;
417 
418  if( !Is_term(g->term[i]) || SCIPisGT(scip, g->prize[i], 0.0) )
419  return;
420 
421  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
422  {
423  const int i1 = g->head[e];
424  if( Is_pterm(g->term[i1]) && g->source != i1 )
425  t = i1;
426  else if( g->source == i1 )
427  e2 = e;
428  }
429 
430  assert(t != UNKNOWN);
431  assert(g->head[g->term2edge[i]] == t);
432 
433  /* i is not a terminal anymore */
434  graph_pc_knot2nonTerm(g, i);
435 
436  if( g->stp_type != STP_RPCSPG )
437  {
438  assert(e2 != UNKNOWN);
439  graph_edge_del(scip, g, e2, TRUE);
440  }
441 
442  /* delete artificial terminal */
443  graph_pc_knot2nonTerm(g, t);
444 
445  while( g->outbeg[t] != EAT_LAST )
446  graph_edge_del(scip, g, g->outbeg[t], TRUE);
447 
448  assert(g->grad[t] == 0);
449 }
450 
451 
452 /** contract edges of weight zero */
453 SCIP_RETCODE reduce_contractZeroEdges(
454  SCIP* scip, /**< SCIP data structure */
455  GRAPH* g, /**< graph data structure */
456  SCIP_Bool savehistory /**< save the history? */
457  )
458 {
459  int count;
460  int nedges;
461 
462  assert(g != NULL);
463  assert(scip != NULL);
464 
465  nedges = g->edges;
466 
467  do
468  {
469  count = 0;
470  for( int e = 0; e < nedges; e += 2 )
471  {
472  if( g->oeat[e] != EAT_FREE && SCIPisZero(scip, g->cost[e]) && SCIPisZero(scip, g->cost[flipedge(e)]) )
473  {
474  if( savehistory )
475  {
476  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e], NULL) );
477  }
478  SCIP_CALL( graph_knot_contract(scip, g, NULL, g->tail[e], g->head[e]) );
479  count++;
480  }
481  }
482  } while( count > 0 );
483 
484  return SCIP_OKAY;
485 }
486 
487 
488 /** basic reduction tests for the STP */
489 SCIP_RETCODE reduce_simple(
490  SCIP* scip, /**< SCIP data structure */
491  GRAPH* g, /**< graph data structure */
492  SCIP_Real* fixed, /**< pointer to offset value */
493  int* solnode, /**< node array to mark whether an node is part of a given solution (CONNECT),
494  or NULL */
495  int* nelims, /**< pointer to number of reductions */
496  int* edgestate /**< array to store status of (directed) edge (for propagation, can otherwise be set to NULL) */
497  )
498 {
499  int i;
500  int i1;
501  int i2;
502  int e1;
503  int e2;
504  int nnodes;
505  int rerun = TRUE;
506  int done = TRUE;
507  int count = 0;
508  SCIP_Bool checkstate = (edgestate != NULL);
509 
510  assert(g != NULL);
511  assert(fixed != NULL);
512  assert(nelims != NULL);
513 
514  nnodes = g->knots;
515 
516  SCIPdebugMessage("Degree Test: ");
517 
518  /* main loop */
519  while( rerun )
520  {
521  rerun = FALSE;
522 
523  for( i = 0; i < nnodes; i++ )
524  {
525  assert(g->grad[i] >= 0);
526 
527  if( g->grad[i] == 1 )
528  {
529  e1 = g->outbeg[i];
530  i1 = g->head[e1];
531 
532  assert(e1 >= 0);
533  assert(e1 == Edge_anti(g->inpbeg[i]));
534  assert(g->oeat[e1] == EAT_LAST);
535  assert(g->ieat[g->inpbeg[i]] == EAT_LAST);
536 
537  if( checkstate )
538  {
539  if( edgestate[e1] == EDGE_BLOCKED || Is_term(g->term[i]) )
540  continue;
541  else
542  graph_edge_del(scip, g, e1, TRUE);
543  }
544  else
545  {
546  if( Is_term(g->term[i]) )
547  {
548  *fixed += g->cost[e1];
549  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL) );
550  }
551 
552  SCIP_CALL( graph_knot_contract(scip, g, solnode, i1, i) );
553  }
554  count++;
555 
556  assert(g->grad[i] == 0);
557 
558  /* the last node in the graph? */
559  if( g->grad[i1] == 0 )
560  {
561  rerun = FALSE;
562  break;
563  }
564  if( (i1 < i) && (g->grad[i1] < 3) )
565  rerun = TRUE;
566 
567  continue;
568  }
569  if( g->grad[i] == 2 && !checkstate )
570  {
571  e1 = g->outbeg[i];
572  e2 = g->oeat[e1];
573  i1 = g->head[e1];
574  i2 = g->head[e2];
575 
576  assert(e1 >= 0);
577  assert(e2 >= 0);
578 
579  do
580  {
581  done = TRUE;
582 
583  if( !Is_term(g->term[i]) )
584  {
585  assert(EQ(g->cost[e2], g->cost[Edge_anti(e2)]));
586 
587  g->cost[e1] += g->cost[e2];
588  g->cost[Edge_anti(e1)] += g->cost[e2];
589 
590  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), g->ancestors[flipedge(e2)], NULL) );
591  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(e1)]), g->ancestors[e2], NULL) );
592 
593  SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
594  count++;
595 
596  break;
597  }
598  assert(Is_term(g->term[i]));
599 
600  if( Is_term(g->term[i1]) && Is_term(g->term[i2]) )
601  {
602 
603  if( SCIPisLT(scip, g->cost[e1], g->cost[e2]) )
604  {
605  *fixed += g->cost[e1];
606  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL) );
607  SCIP_CALL( graph_knot_contract(scip, g, solnode, i1, i) );
608  }
609  else
610  {
611  *fixed += g->cost[e2];
612  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e2], NULL) );
613  SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
614  }
615  count++;
616 
617  break;
618  }
619  if( Is_term(g->term[i1]) && !Is_term(g->term[i2]) && SCIPisLE(scip, g->cost[e1], g->cost[e2]) )
620  {
621  *fixed += g->cost[e1];
622  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL) );
623  SCIP_CALL( graph_knot_contract(scip, g, solnode, i1, i) );
624  count++;
625  break;
626  }
627  if( Is_term(g->term[i2]) && !Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e2], g->cost[e1]) )
628  {
629  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e2], NULL) );
630  *fixed += g->cost[e2];
631  SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
632  count++;
633  break;
634  }
635  done = FALSE;
636  }
637  while( FALSE );
638 
639  if (done
640  && (((i1 < i) && (g->grad[i1] < 3))
641  || ((i2 < i) && (g->grad[i2] < 3))))
642  rerun = TRUE;
643  }
644  if( Is_term(g->term[i]) && g->grad[i] > 2 && !checkstate )
645  {
646  SCIP_Real mincost = FARAWAY;
647  int ett = UNKNOWN;
648  for( e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
649  {
650  i1 = g->head[e1];
651 
652  if( SCIPisLT(scip, g->cost[e1], mincost) )
653  {
654  mincost = g->cost[e1];
655  if( Is_term(g->term[i1]) )
656  ett = e1;
657  }
658  else if( Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e1], mincost) )
659  {
660  ett = e1;
661  }
662  }
663  if( ett != UNKNOWN && SCIPisLE(scip, g->cost[ett], mincost) )
664  {
665  *fixed += g->cost[ett];
666  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[ett], NULL) );
667  SCIP_CALL( graph_knot_contractLowdeg2High(scip, g, solnode, i, g->head[ett]) );
668 
669  rerun = TRUE;
670  }
671  }
672  }
673  }
674  SCIPdebugMessage(" %d Knots deleted\n", count);
675  assert(graph_valid(g));
676 
677  *nelims += count;
678  return SCIP_OKAY;
679 }
680 
681 
682 
683 /** basic reduction tests for the SAP */
684 SCIP_RETCODE reduce_simple_sap(
685  SCIP* scip, /**< SCIP data structure */
686  GRAPH* g, /**< graph data structure */
687  SCIP_Real* fixed, /**< pointer to offfset value */
688  int* count /**< pointer to number of reductions */
689  )
690 {
691  SCIP_QUEUE* queue;
692  int i;
693  int e;
694  int i1;
695  int i2;
696  int e1;
697  int e2;
698  int nnodes;
699  int* pnode;
700  char rerun;
701 
702  assert(g != NULL);
703  assert(fixed != NULL);
704  assert(count != NULL);
705 
706  rerun = TRUE;
707  nnodes = g->knots;
708 
709  *count = 0;
710  SCIPdebugMessage("Degree Test: ");
711 
712  /* main loop */
713  while( rerun )
714  {
715  rerun = FALSE;
716 
717  for( i = 0; i < nnodes; i++ )
718  {
719  assert(g->grad[i] >= 0);
720 
721  if( g->grad[i] == 1 )
722  {
723  e1 = g->inpbeg[i];
724  i1 = g->tail[e1];
725 
726  assert(e1 >= 0);
727  assert(e1 == Edge_anti(g->outbeg[i]));
728  assert(g->ieat[e1] == EAT_LAST);
729  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
730 
731  if( Is_term(g->term[i]) )
732  {
733  if( i == g->source )
734  {
735  e2 = flipedge(e1);
736  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e2], NULL) );
737  *fixed += g->cost[e2];
738  SCIP_CALL( graph_knot_contract(scip, g, NULL, i1, i) );
739  }
740  else
741  {
742  SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL));
743  *fixed += g->cost[e1];
744  SCIP_CALL(graph_knot_contract(scip, g, NULL, i1, i));
745  }
746  }
747  else
748  {
749  graph_edge_del(scip, g, e1, TRUE);
750  }
751 
752  assert(g->grad[i] == 0);
753 
754  if ((i1 < i) && (g->grad[i1] < 3))
755  rerun = TRUE;
756 
757  (*count)++;
758 
759  continue;
760  }
761 
762  if( g->grad[i] == 2 )
763  {
764  e1 = g->outbeg[i];
765  e2 = g->oeat[e1];
766  i1 = g->head[e1];
767  i2 = g->head[e2];
768 
769  assert(e1 >= 0);
770  assert(e2 >= 0);
771 
772  if( !Is_term(g->term[i]) )
773  {
774  if( (!Is_term(g->term[i2]) && !Is_term(g->term[i1])) )
775  {
776  g->cost[e1] += g->cost[Edge_anti(e2)];
777  g->cost[Edge_anti(e1)] += g->cost[e2];
778 
779  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), g->ancestors[Edge_anti(e2)], NULL) );
780  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(e1)]), g->ancestors[e2], NULL) );
781 
782  if( SCIPisGT(scip, g->cost[e1], FARAWAY) )
783  g->cost[e1] = FARAWAY;
784  if( SCIPisGT(scip, g->cost[Edge_anti(e1)], FARAWAY) )
785  g->cost[Edge_anti(e1)] = FARAWAY;
786 
787  SCIP_CALL( graph_knot_contract(scip, g, NULL, i2, i) );
788 
789  (*count)++;
790  if( ((i1 < i) && (g->grad[i1] < 3))
791  || ((i2 < i) && (g->grad[i2] < 3)) )
792  rerun = TRUE;
793  }
794  }
795  /* CONSTCOND */
796  /*lint -save -e717 */
797  /*lint -restore */
798  }
799  }
800  }
801 
802  /* delete all arcs in \delta^-(root) */
803  for( e = g->inpbeg[g->source]; e != EAT_LAST; e = g->ieat[e] )
804  g->cost[e] = FARAWAY;
805 
806  /* delete all nodes not reachable from the root by forward arcs */
807 
808  /* BFS */
809  SCIP_CALL(SCIPqueueCreate(&queue, nnodes, 1.1));
810 
811  for (i = 0; i < nnodes; i++)
812  g->mark[i] = FALSE;
813 
814  g->mark[g->source] = TRUE;
815  SCIP_CALL(SCIPqueueInsert(queue, &(g->source)));
816 
817  while (!SCIPqueueIsEmpty(queue))
818  {
819  pnode = (SCIPqueueRemove(queue));
820  for (e = g->outbeg[*pnode]; e != EAT_LAST; e = g->oeat[e])
821  {
822  if( !g->mark[g->head[e]] && SCIPisLT(scip, g->cost[e], FARAWAY) )
823  {
824  g->mark[g->head[e]] = TRUE;
825  SCIP_CALL(SCIPqueueInsert(queue, &(g->head[e])));
826  }
827  }
828  }
829 
830  for (i = 0; i < nnodes; i++)
831  if( !g->mark[i] )
832  while (g->inpbeg[i] != EAT_LAST)
833  graph_edge_del(scip, g, g->inpbeg[i], TRUE);
834 
835  /* delete all nodes that cannot reach a terminal other than the root by forward arcs (not using the root) */
836 
837  /* BFS */
838 
839  assert(SCIPqueueIsEmpty(queue));
840 
841  for( i = 0; i < nnodes; i++ )
842  {
843  if( Is_term(g->term[i]) && i != g->source )
844  {
845  g->mark[i] = TRUE;
846  SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[g->outbeg[i]])) );
847  }
848  else
849  {
850  g->mark[i] = FALSE;
851  }
852  }
853 
854  g->mark[g->source] = TRUE;
855 
856  while( !SCIPqueueIsEmpty(queue) )
857  {
858  pnode = (SCIPqueueRemove(queue));
859  for( e = g->inpbeg[*pnode]; e != EAT_LAST; e = g->ieat[e] )
860  {
861  if( !g->mark[g->tail[e]] && SCIPisLT(scip, g->cost[e], FARAWAY) )
862  {
863  g->mark[g->tail[e]] = TRUE;
864  SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[e])) );
865  }
866  }
867  }
868 
869  SCIPqueueFree(&queue);
870 
871  for( i = 0; i < nnodes; i++ )
872  if( !g->mark[i] )
873  while( g->inpbeg[i] != EAT_LAST )
874  graph_edge_del(scip, g, g->inpbeg[i], TRUE);
875 
876  SCIPdebugMessage("dirdeg %d Knots deleted\n", *count);
877  assert(graph_valid(g));
878 
879  return SCIP_OKAY;
880 }
881 
882 
883 /** root proximity terminal test (SAP) */
884 SCIP_RETCODE reduce_rpt(
885  SCIP* scip, /**< SCIP data structure */
886  GRAPH* g, /**< graph data structure */
887  SCIP_Real* fixed, /**< pointer to offset value */
888  int* count /**< pointer to number of reductions */
889  )
890 {
891  SCIP_Real pathcost;
892  SCIP_Real* dijkdist;
893  int i;
894  int e;
895  int i1;
896  int e1;
897  int old;
898  int nnodes;
899  int* dijkedge;
900 
901  assert(scip != NULL);
902  assert(g != NULL);
903  assert(fixed != NULL);
904  assert(count != NULL);
905 
906  nnodes = g->knots;
907  *count = 0;
908 
909  SCIP_CALL( SCIPallocBufferArray(scip, &dijkdist, nnodes) );
910  SCIP_CALL( SCIPallocBufferArray(scip, &dijkedge, nnodes) );
911 
912  graph_path_execX(scip, g, g->source, g->cost, dijkdist, dijkedge);
913 
914  for( i = 0; i < nnodes; i++ )
915  {
916  if( Is_term(g->term[i]) && i != g->source && g->grad[i] > 0 )
917  {
918  e1 = dijkedge[i];
919  pathcost = dijkdist[i];
920 
921  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
922  {
923  if( e == e1 )
924  continue;
925 
926  if( SCIPisGT(scip, pathcost, g->cost[e]) )
927  break;
928  }
929  if( e == EAT_LAST )
930  {
931  i1 = g->tail[e1];
932  old = g->grad[i] + g->grad[i1] - 1;
933 
934  SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL));
935  *fixed += g->cost[e1];
936  SCIP_CALL(graph_knot_contract(scip, g, NULL, i1, i));
937 
938  assert(old - g->grad[i1] > 0);
939  *count += old - g->grad[i1];
940  SCIPdebugMessage("contract %d\n", old - g->grad[i] - g->grad[i1]);
941  }
942 
943  }
944  }
945 
946  SCIPfreeBufferArray(scip, &dijkedge);
947  SCIPfreeBufferArray(scip, &dijkdist);
948 
949  return SCIP_OKAY;
950 }
951 
952 /** basic reduction tests for the MWCS problem */
953 SCIP_RETCODE reduce_simple_mw(
954  SCIP* scip, /**< SCIP data structure */
955  GRAPH* g, /**< graph data structure */
956  int* solnode, /**< array to indicate whether a node is part of the current solution (==CONNECT) */
957  SCIP_Real* fixed, /**< pointer to offset value */
958  int* count /**< pointer to number of reductions */
959  )
960 {
961  SCIP_Real maxprize = -1.0;
962  const int nnodes = g->knots;
963  int localcount = 0;
964 
965  SCIP_Bool rerun;
966  SCIP_Bool contracted;
967 
968  assert(g != NULL);
969  assert(fixed != NULL);
970  assert(count != NULL);
971  assert(g->stp_type == STP_MWCSP);
972 
973  SCIPdebugMessage("MW degree test: \n");
974 
975  contracted = TRUE;
976  while( contracted )
977  {
978  contracted = FALSE;
979 
980  /* contract adjacent positive vertices */
981  for( int i = 0; i < nnodes; i++ )
982  {
983  int i1 = -1;
984  int grad;
985  SCIP_Bool hit;
986 
987  if( !Is_term(g->term[i]) || !(g->mark[i]) )
988  continue;
989 
990  grad = g->grad[i];
991  hit = FALSE;
992 
993  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
994  {
995  const int head = g->head[e];
996 
997  if( Is_term(g->term[head]) && head != g->source )
998  {
999  assert(g->mark[head]);
1000 
1001  if( (g->grad[head] <= grad) )
1002  {
1003  grad = g->grad[head];
1004  i1 = head;
1005  }
1006  else if( head < i )
1007  {
1008  hit = TRUE;
1009  }
1010  }
1011  }
1012 
1013  while( i1 >= 0 )
1014  {
1015  int i2 = -1;
1016 
1017  assert(g->mark[i1]);
1018  assert(g->grad[i1] > 0);
1019  assert(Is_term(g->term[i1]));
1020 
1021  grad = g->grad[i];
1022  hit = FALSE;
1023  for( int e = g->outbeg[i1]; e != EAT_LAST; e = g->oeat[e] )
1024  {
1025  const int head = g->head[e];
1026  if( Is_term(g->term[head]) && head != i && head != g->source )
1027  {
1028  assert(g->mark[head]);
1029 
1030  if( (g->grad[head] <= grad) )
1031  {
1032  i2 = head;
1033  grad = g->grad[head];
1034  }
1035  else if( head < i )
1036  {
1037  hit = TRUE;
1038  }
1039  }
1040  }
1041 
1042  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i, i1, i));
1043 
1044  localcount++;
1045 
1046  i1 = i2;
1047  }
1048  if( hit )
1049  contracted = TRUE;
1050  }
1051  }
1052 
1053  /* contract adjacent 0 vertices */
1054  for( int i = 0; i < nnodes; i++ )
1055  {
1056  if( !(g->mark[i]) || !SCIPisZero(scip, g->prize[i]) )
1057  continue;
1058 
1059  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1060  {
1061  const int i2 = g->head[e];
1062 
1063  if( g->mark[i2] && SCIPisGE(scip, g->prize[i2], 0.0) )
1064  {
1065  if( Is_term(g->term[i2]) )
1066  {
1067  SCIP_CALL(graph_pc_contractEdge(scip, g, solnode, i2, i, i2));
1068  }
1069  else
1070  {
1071  SCIP_CALL( graph_pc_contractEdgeAncestors(scip, g, i2, i, flipedge_Uint(e)) );
1072  SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
1073  }
1074 
1075  localcount++;
1076  break;
1077  }
1078  }
1079  }
1080 
1081  SCIPdebugMessage("chains before: %d \n", nchains(g));
1082 
1083  rerun = TRUE;
1084 
1085  /* main loop */
1086  while( rerun )
1087  {
1088  rerun = FALSE;
1089 
1090  /* main loop for remaining tests */
1091  for( int i = 0; i < nnodes; i++ )
1092  {
1093  assert(g->grad[i] >= 0);
1094  if( !g->mark[i] || g->grad[i] == 0 )
1095  continue;
1096 
1097  assert(!Is_pterm(g->term[i]));
1098 
1099  /* non-positive vertex? */
1100  if( !Is_term(g->term[i]) )
1101  {
1102  if( g->grad[i] == 1 )
1103  {
1104  const int e1 = g->inpbeg[i];
1105  const int i1 = g->tail[e1];
1106 
1107  assert(e1 >= 0);
1108  assert(e1 == Edge_anti(g->outbeg[i]));
1109  assert(g->ieat[e1] == EAT_LAST);
1110  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
1111  assert(SCIPisLE(scip, g->prize[i], 0.0));
1112 
1113  graph_edge_del(scip, g, e1, TRUE);
1114  SCIPdebugMessage("delete negative vertex of degree 1 (%d)\n ", i);
1115  assert(g->grad[i] == 0);
1116 
1117  if( (i1 < i) && (g->grad[i1] < 3 || (g->grad[i1] == 3 && Is_term(g->term[i1]))) )
1118  rerun = TRUE;
1119 
1120  localcount++;
1121  continue;
1122  }
1123 
1124  /* contract non-positive chains */
1125  if( g->grad[i] == 2 )
1126  {
1127  int f1 = -1;
1128  int f2 = -1;
1129  int length = 0;
1130 
1131  const int e1 = g->outbeg[i];
1132  const int e2 = g->oeat[e1];
1133  const int i1 = g->head[e1];
1134  const int i2 = g->head[e2];
1135 
1136  assert(e1 >= 0);
1137  assert(e2 >= 0);
1138  assert(i1 != i2);
1139  assert(g->mark[i1]);
1140  assert(g->mark[i2]);
1141 
1142  SCIP_CALL( traverseChain(scip, g, &length, &f1, i, i1, i2, e1) );
1143  SCIP_CALL( traverseChain(scip, g, &length, &f2, i, i2, i1, e2) );
1144 
1145  if( f1 == f2 )
1146  {
1147  while( g->outbeg[i] != EAT_LAST )
1148  graph_edge_del(scip, g, g->outbeg[i], TRUE);
1149  }
1150  else if( length > 0 )
1151  {
1152  assert(g->grad[i] <= 2);
1153 
1154  for( int e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
1155  g->cost[e] = -g->prize[i];
1156 
1157  localcount += length;
1158  }
1159  }
1160  continue;
1161  }
1162 
1163  /* node i is of positive weight (terminal): */
1164 
1165  /* terminal of 0-prize? */
1166  if( SCIPisLE(scip, g->prize[i], 0.0) )
1167  {
1168  adjust0term(scip, g, i);
1169  localcount += 2;
1170  continue;
1171  }
1172 
1173  /* terminal of (real) degree 0? */
1174  if( g->grad[i] == 2 )
1175  {
1176  /* if terminal node i is not the one with the highest prize, delete */
1177  if( !is_maxprize(scip, g, i, &maxprize) )
1178  {
1179  SCIPdebugMessage("delete degree 0 term %d prize: %f count:%d\n ", i, g->prize[i], localcount);
1180  (*fixed) += g->prize[i];
1181  localcount += graph_pc_deleteTerm(scip, g, i);
1182  }
1183  }
1184  /* terminal of (real) degree 1? */
1185  else if( g->grad[i] == 3 )
1186  {
1187  int e;
1188  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1189  if( g->mark[g->head[e]] )
1190  break;
1191 
1192  assert(e != EAT_LAST);
1193  assert(g->head[e] != g->source);
1194 
1195  if( !Is_term(g->term[g->head[e]]) )
1196  {
1197  SCIP_CALL( trydg1edgepc(scip, g, fixed, NULL, count, i, e, &rerun, &maxprize) );
1198  continue;
1199  }
1200  }
1201  }
1202  }
1203 
1204  /* contract adjacent positive vertices */
1205  for( int i = 0; i < nnodes; i++ )
1206  {
1207  int i1;
1208 
1209  if( !(g->mark[i]) || !Is_term(g->term[i]) )
1210  continue;
1211 
1212  i1 = i;
1213 
1214  do
1215  {
1216  assert(g->mark[i1]);
1217  assert(g->grad[i1] > 0);
1218  assert(Is_term(g->term[i1]));
1219 
1220  contracted = FALSE;
1221 
1222  for( int e = g->outbeg[i1]; e != EAT_LAST; e = g->oeat[e] )
1223  {
1224  const int i2 = g->head[e];
1225  if( g->mark[i2] && Is_term(g->term[i2]) )
1226  {
1227  SCIPdebugMessage("contract tt after (local) main loop %d->%d\n ", i1, i2);
1228  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i1, i2, i1) );
1229  localcount++;
1230  contracted = TRUE;
1231  break;
1232  }
1233  }
1234  }
1235  while( contracted );
1236  }
1237 
1238  (*count) += localcount;
1239  SCIPdebugMessage("MW basic reduction package has deleted %d edges\n", *count);
1240 
1241  SCIPdebugMessage("chains after: %d \n", nchains(g));
1242  assert(!adjterms(g));
1243 
1244  assert(graph_valid(g));
1245 
1246  SCIP_CALL( level0save(scip, g) );
1247 
1248  return SCIP_OKAY;
1249 }
1250 
1251 /** basic reduction tests for the HCDSTP */
1252 SCIP_RETCODE reduce_simple_hc(
1253  SCIP* scip, /**< SCIP data structure */
1254  GRAPH* g, /**< graph data structure */
1255  SCIP_Real* fixed, /**< pointer to offfset value */
1256  int* count /**< pointer to number of reductions */
1257  )
1258 {
1259  int i;
1260  int e;
1261  int e2;
1262  int nnodes;
1263  SCIP_Bool rerun = TRUE;
1264 
1265  assert(g != NULL);
1266  assert(fixed != NULL);
1267  assert(count != NULL);
1268  assert(g->stp_type == STP_DHCSTP);
1269 
1270  nnodes = g->knots;
1271 
1272  SCIPdebugMessage("basic HC test: \n");
1273 
1274  /* main loop */
1275  while( rerun )
1276  {
1277  rerun = FALSE;
1278 
1279  /* delete incoming arcs of the root */
1280  e = g->inpbeg[g->source];
1281  while( e != EAT_LAST )
1282  {
1283  e2 = g->ieat[e];
1284 
1285  if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
1286  {
1287  SCIPdebugMessage("delete incoming root arc \n");
1288  (*count)++;
1289  graph_edge_del(scip, g, e, TRUE);
1290  }
1291  else if( SCIPisLT(scip, g->cost[e], FARAWAY) )
1292  {
1293  SCIPdebugMessage("delete anti-parallel root arcs \n");
1294  g->cost[e] = FARAWAY;
1295  }
1296 
1297  e = e2;
1298  }
1299 
1300  /* delete outgoing arcs of the terminals (other than the root) */
1301  for( i = 0; i < nnodes; i++ )
1302  {
1303  if( Is_term(g->term[i]) && i != g->source )
1304  {
1305  e = g->outbeg[i];
1306  while( e != EAT_LAST )
1307  {
1308  e2 = g->oeat[e];
1309 
1310  if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
1311  {
1312  SCIPdebugMessage("delete anti-parallel terminal arcs \n");
1313  (*count)++;
1314  graph_edge_del(scip, g, e, TRUE);
1315  }
1316 
1317  e = e2;
1318  }
1319  }
1320  }
1321  }
1322 
1323  SCIPdebugMessage("HC basic reduction package has deleted %d edges\n", *count);
1324 
1325  return SCIP_OKAY;
1326 }
1327 
1328 
1329 /** basic reductions for RPCSTP and PCSPG */
1330 SCIP_RETCODE reduce_simple_pc(
1331  SCIP* scip, /**< SCIP data structure */
1332  GRAPH* g, /**< graph data structure */
1333  SCIP_Real* fixed, /**< pointer to offset value */
1334  int* count, /**< pointer to number of reductions */
1335  int* solnode, /**< solution nodes */
1336  SCIP_Bool contractroot /**< contract vertices into root (for rooted prize-collecting) */
1337  )
1338 {
1339  int edges2[2];
1340  int nodes2[2];
1341  SCIP_Real maxprize = -1.0;
1342  const int nnodes = g->knots;
1343  const SCIP_Bool pc = (g->stp_type == STP_PCSPG);
1344  SCIP_Bool rerun = TRUE;
1345 
1346  assert(g != NULL);
1347  assert(fixed != NULL);
1348  assert(count != NULL);
1349  assert(g->stp_type == STP_PCSPG || g->stp_type == STP_RPCSPG);
1350  assert(!g->extended);
1351 
1352  *count = 0;
1353 
1354  SCIPdebugMessage("Degree Test: ");
1355 
1356  if( !pc )
1357  g->mark[g->source] = FALSE;
1358 
1359  /* main loop */
1360  while( rerun )
1361  {
1362  rerun = FALSE;
1363 
1364  for( int i = 0; i < nnodes; i++ )
1365  {
1366  assert(g->grad[i] >= 0);
1367  assert(!(g->mark[i] && Is_pterm(g->term[i])));
1368 
1369  /* last condition should never be true, but just in case ... */
1370  if( !g->mark[i] || g->grad[i] == 0 || Is_pterm(g->term[i]) )
1371  continue;
1372 
1373  if( !Is_term(g->term[i]) )
1374  {
1375  assert(SCIPisZero(scip, g->prize[i]));
1376 
1377  if( g->grad[i] == 1 )
1378  {
1379  const int e1 = g->inpbeg[i];
1380  const int i1 = g->tail[e1];
1381 
1382  assert(e1 >= 0);
1383  assert(e1 == Edge_anti(g->outbeg[i]));
1384  assert(g->ieat[e1] == EAT_LAST);
1385  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
1386 
1387  graph_edge_del(scip, g, e1, TRUE);
1388  SCIPdebugMessage("delete non-terminal of degree 1 %d\n ", i);
1389  (*count)++;
1390 
1391  assert(g->grad[i] == 0);
1392 
1393  /* the last node? */
1394  if( g->grad[i1] == 0 )
1395  {
1396  rerun = FALSE;
1397  break;
1398  }
1399  if( (i1 < i) && (g->grad[i1] < 3 || Is_term(g->term[i1])) )
1400  rerun = TRUE;
1401 
1402  continue;
1403  }
1404 
1405  /* contract non terminals of degree 2 */
1406  if( g->grad[i] == 2 )
1407  {
1408  const int e1 = g->outbeg[i];
1409  const int e2 = g->oeat[e1];
1410  const int i1 = g->head[e1];
1411  const int i2 = g->head[e2];
1412 
1413  assert(e1 >= 0);
1414  assert(e2 >= 0);
1415 
1416  assert(g->mark[i1] || i1 == g->source);
1417  assert(g->mark[i2] || i2 == g->source);
1418  assert(SCIPisEQ(scip, g->cost[e2], g->cost[flipedge(e2)]));
1419 
1420  g->cost[e1] += g->cost[e2];
1421  g->cost[flipedge(e1)] += g->cost[e2];
1422 
1423  SCIPdebugMessage("contract non-terminals %d %d \n ", i2, i);
1424  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), g->ancestors[flipedge(e2)], NULL) );
1425  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(e1)]), g->ancestors[e2], NULL) );
1426 
1427  SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
1428  (*count)++;
1429 
1430  if( (Is_term(g->term[i2]) && (i2 < i)) || (Is_term(g->term[i1]) && (i1 < i)) )
1431  rerun = TRUE;
1432  }
1433  continue;
1434  }
1435 
1436  /*
1437  * node i is a terminal:
1438  */
1439 
1440  /* terminal of 0-prize? */
1441  if( SCIPisLE(scip, g->prize[i], 0.0) && i != g->source )
1442  {
1443  adjust0term(scip, g, i);
1444  (*count) += 2;
1445  continue;
1446  }
1447 
1448  assert(Is_term(g->term[i]));
1449 
1450  /* terminal of (real) degree 0? */
1451  if( ( (g->grad[i] == 2 && pc) || (g->grad[i] == 1 && !pc) ) )
1452  {
1453  /* if terminal node i is node the one with the highest prize, delete */
1454  if( !is_maxprize(scip, g, i, &maxprize) )
1455  {
1456  SCIPdebugMessage("delete 0 term %d prize: %f count:%d\n ", i, g->prize[i], *count);
1457  (*fixed) += g->prize[i];
1458  (*count) += graph_pc_deleteTerm(scip, g, i);
1459  }
1460  }
1461  /* terminal of (real) degree 1? */
1462  else if( ( (g->grad[i] == 3 && pc) || (g->grad[i] == 2 && !pc) ) )
1463  {
1464  int e;
1465  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1466  if( g->mark[g->head[e]] || (!pc && g->head[e] == g->source) )
1467  break;
1468 
1469  assert(e != EAT_LAST);
1470  assert(g->head[e] != g->source || !pc);
1471 
1472  SCIP_CALL( trydg1edgepc(scip, g, fixed, solnode, count, i, e, &rerun, &maxprize) );
1473  }
1474  /* terminal of (real) degree 2? */
1475  else if( ( (g->grad[i] == 4 && pc) || (g->grad[i] == 3 && !pc) ) )
1476  {
1477  if( !is_maxprize(scip, g, i, &maxprize) )
1478  {
1479  int i2 = 0;
1480  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1481  {
1482  const int i1 = g->head[e];
1483  if( g->mark[i1] || (!pc && i1 == g->source) )
1484  {
1485  assert(i2 < 2);
1486 
1487  edges2[i2] = e;
1488  nodes2[i2++] = i1;
1489  }
1490  }
1491 
1492  assert(i2 >= 2);
1493  if( SCIPisLE(scip, g->prize[i], g->cost[edges2[0]]) && SCIPisLE(scip, g->prize[i], g->cost[edges2[1]]) )
1494  {
1495  IDX* ancestors = NULL;
1496  IDX* revancestors = NULL;
1497  int n1;
1498  const int e = edges2[0];
1499  const int e1 = edges2[1];
1500 
1501  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e], NULL) );
1502  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[Edge_anti(e1)], NULL) );
1503  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[Edge_anti(e)], NULL) );
1504  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[e1], NULL) );
1505  SCIPdebugMessage("delete - term - %d\n ", i);
1506 
1507  /* contract edge */
1508  n1 = graph_edge_redirect(scip, g, e, nodes2[1], nodes2[0], g->cost[e] + g->cost[e1] - g->prize[i], TRUE);
1509 
1510  /* new edge inserted? */
1511  if( n1 >= 0)
1512  {
1513  /* add ancestors */
1514  SCIPintListNodeFree(scip, &(g->ancestors[n1]));
1515  SCIPintListNodeFree(scip, &(g->ancestors[Edge_anti(n1)]));
1516  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[n1]), ancestors, NULL) );
1517  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(n1)]), revancestors, NULL) );
1518  }
1519  (*count) += graph_pc_deleteTerm(scip, g, i);
1520  (*fixed) += g->prize[i];
1521  SCIPintListNodeFree(scip, &(ancestors));
1522  SCIPintListNodeFree(scip, &(revancestors));
1523  }
1524  }
1525  }
1526 
1527  /* try to contract adjacent terminals */
1528  if( g->grad[i] > 0 )
1529  {
1530  SCIP_Real mincost = FARAWAY;
1531  int ett = UNKNOWN;
1532 
1533  for( int e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
1534  {
1535  const int i1 = g->head[e1];
1536 
1537  if( !g->mark[i1] && (pc || i1 != g->source || !contractroot) )
1538  continue;
1539 
1540  if( SCIPisLT(scip, g->cost[e1], mincost) )
1541  {
1542  mincost = g->cost[e1];
1543  if( Is_term(g->term[i1]) )
1544  ett = e1;
1545  }
1546  else if( Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e1], mincost) )
1547  {
1548  assert(SCIPisLT(scip, g->cost[e1], FARAWAY));
1549  assert(SCIPisEQ(scip, g->cost[e1], mincost));
1550  ett = e1;
1551  }
1552  }
1553 
1554  if( ett != UNKNOWN && SCIPisLE(scip, g->cost[ett], mincost) && SCIPisLE(scip, g->cost[ett], g->prize[i])
1555  && SCIPisLE(scip, g->cost[ett], g->prize[g->head[ett]]) )
1556  {
1557  const int i1 = g->head[ett];
1558  SCIPdebugMessage("contract tt %d->%d\n ", i, i1);
1559  assert(SCIPisLT(scip, mincost, FARAWAY));
1560  *fixed += g->cost[ett];
1561  (*count)++;
1562 
1563  if( i1 == g->source )
1564  {
1565  int j;
1566  int e;
1567 
1568  /* get edge from i to its artificial terminal */
1569  for (e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e])
1570  if( Is_pterm(g->term[g->head[e]]) && g->head[e] != g->source )
1571  break;
1572 
1573  assert(e != EAT_LAST);
1574  SCIPdebugMessage("contract rt %d->%d \n", i, i1);
1575 
1576  if( g->pcancestors[i] != NULL )
1577  {
1578  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->pcancestors[i], NULL));
1579  SCIPintListNodeFree(scip, &(g->pcancestors[i]));
1580  }
1581  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[ett], NULL));
1582 
1583  /* artificial terminal to i */
1584  j = g->head[e];
1585  assert(!g->mark[j]);
1586 
1587  /* delete edge and unmark artificial terminal */
1588  graph_pc_knot2nonTerm(g, j);
1589  graph_edge_del(scip, g, e, TRUE);
1590 
1591  /* delete remaining incident edge of artificial terminal */
1592  e = g->inpbeg[j];
1593 
1594  assert(e != EAT_LAST);
1595  assert(g->source == g->tail[e] || g->source == j);
1596  assert(SCIPisEQ(scip, g->prize[i], g->cost[e]));
1597 
1598  graph_edge_del(scip, g, e, TRUE);
1599 
1600  assert(g->inpbeg[j] == EAT_LAST);
1601 
1602  SCIP_CALL(graph_knot_contract(scip, g, solnode, i1, i));
1603  graph_pc_knot2nonTerm(g, i);
1604  } /* i1 == root */
1605  else
1606  {
1607  if( g->grad[i] >= g->grad[i1] )
1608  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i, i1, i) );
1609  else
1610  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i1, i, i1) );
1611  }
1612 
1613  rerun = TRUE;
1614  }
1615  } /* contract adjacent terminals */
1616  } /* for i = 1, ..., nnodes */
1617  } /* main loops */
1618 
1619  if( !pc )
1620  g->mark[g->source] = TRUE;
1621  SCIPdebugMessage("degree test pc: %d nodes deleted\n", *count);
1622 
1623  assert(graph_valid(g));
1624 
1625  SCIP_CALL( level0save(scip, g) );
1626 
1627  return SCIP_OKAY;
1628 }
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
level0save
SCIP_RETCODE level0save(SCIP *, GRAPH *)
Definition: reduce.c:185
Int_List_Node
Definition: misc_stp.h:73
reduce_simple
SCIP_RETCODE reduce_simple(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *solnode, int *nelims, int *edgestate)
Definition: reduce_simple.c:489
GRAPH::head
int *RESTRICT head
Definition: grph.h:96
GRAPH
Definition: grph.h:57
GRAPH::source
int source
Definition: grph.h:67
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
SCIPqueueInsert
SCIP_RETCODE SCIPqueueInsert(SCIP_QUEUE *queue, void *elem)
Definition: misc.c:1019
graph_valid
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4328
graph_pc_deleteTerm
int graph_pc_deleteTerm(SCIP *, GRAPH *, int)
Definition: grphbase.c:1945
EAT_LAST
#define EAT_LAST
Definition: grph.h:31
Edge_anti
#define Edge_anti(a)
Definition: grph.h:171
SCIPqueueRemove
void * SCIPqueueRemove(SCIP_QUEUE *queue)
Definition: misc.c:1070
FALSE
#define FALSE
Definition: def.h:73
GRAPH::inpbeg
int *RESTRICT inpbeg
Definition: grph.h:74
TRUE
#define TRUE
Definition: def.h:72
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
STP_DHCSTP
#define STP_DHCSTP
Definition: grph.h:48
reduce_simple_pc
SCIP_RETCODE reduce_simple_pc(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count, int *solnode, SCIP_Bool contractroot)
Definition: reduce_simple.c:1330
graph_pc_contractEdgeAncestors
SCIP_RETCODE graph_pc_contractEdgeAncestors(SCIP *, GRAPH *, int, int, int)
Definition: grphbase.c:2079
STP_PCSPG
#define STP_PCSPG
Definition: grph.h:40
SCIPdebugMessage
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
flipedge_Uint
#define flipedge_Uint(edge)
Definition: grph.h:151
reduce_contractZeroEdges
SCIP_RETCODE reduce_contractZeroEdges(SCIP *scip, GRAPH *g, SCIP_Bool savehistory)
Definition: reduce_simple.c:453
GRAPH::mark
int *RESTRICT mark
Definition: grph.h:70
GRAPH::fixedges
IDX * fixedges
Definition: grph.h:85
graph_pc_contractEdge
SCIP_RETCODE graph_pc_contractEdge(SCIP *, GRAPH *, int *, int, int, int)
Definition: grphbase.c:2105
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIPintListNodeFree
void SCIPintListNodeFree(SCIP *scip, IDX **node)
Definition: misc_stp.c:205
graph_path_execX
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: grphpath.c:781
SCIPqueueIsEmpty
SCIP_Bool SCIPqueueIsEmpty(SCIP_QUEUE *queue)
Definition: misc.c:1174
reduce_rpt
SCIP_RETCODE reduce_rpt(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:884
GRAPH::oeat
int *RESTRICT oeat
Definition: grph.h:103
SCIPintListNodeAppendCopy
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:94
graph_knot_contractLowdeg2High
SCIP_RETCODE graph_knot_contractLowdeg2High(SCIP *, GRAPH *, int *, int, int)
Definition: grphbase.c:2666
GRAPH::extended
SCIP_Bool extended
Definition: grph.h:128
GRAPH::stp_type
int stp_type
Definition: grph.h:127
GRAPH::ancestors
IDX ** ancestors
Definition: grph.h:86
traverseChain
static SCIP_RETCODE traverseChain(SCIP *scip, GRAPH *g, int *length, int *final, int i, int i1, int i2, int e1)
Definition: reduce_simple.c:306
is_maxprize
static SCIP_Bool is_maxprize(SCIP *scip, const GRAPH *g, int i, SCIP_Real *maxprize)
Definition: reduce_simple.c:80
Is_pterm
#define Is_pterm(a)
Definition: grph.h:169
GRAPH::prize
SCIP_Real * prize
Definition: grph.h:82
SCIP_Queue
Definition: struct_misc.h:51
adjterms
static SCIP_Bool adjterms(const GRAPH *g)
Definition: reduce_simple.c:39
GRAPH::grad
int *RESTRICT grad
Definition: grph.h:73
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:551
NULL
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_OKAY
Definition: type_retcode.h:33
EQ
#define EQ(a, b)
Definition: portab.h:62
GRAPH::knots
int knots
Definition: grph.h:62
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:364
trydg1edgepc
static SCIP_RETCODE trydg1edgepc(SCIP *scip, GRAPH *g, SCIP_Real *offset, int *solnode, int *count, int i, int iout, SCIP_Bool *rerun, SCIP_Real *maxprize)
Definition: reduce_simple.c:129
GRAPH::term2edge
int * term2edge
Definition: grph.h:80
GRAPH::pcancestors
IDX ** pcancestors
Definition: grph.h:87
SCIPqueueCreate
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition: misc.c:933
FARAWAY
#define FARAWAY
Definition: grph.h:156
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool
#define SCIP_Bool
Definition: def.h:70
GRAPH::ieat
int *RESTRICT ieat
Definition: grph.h:102
STP_MWCSP
#define STP_MWCSP
Definition: grph.h:47
GRAPH::tail
int *RESTRICT tail
Definition: grph.h:95
reduce_simple_mw
SCIP_RETCODE reduce_simple_mw(SCIP *scip, GRAPH *g, int *solnode, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:953
nchains
static unsigned nchains(const GRAPH *g)
Definition: reduce_simple.c:60
GRAPH::term
int *RESTRICT term
Definition: grph.h:68
graph_edge_del
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: grphbase.c:2841
grph.h
includes various files containing graph methods used for Steiner tree problems
portab.h
Portable defintions.
Is_term
#define Is_term(a)
Definition: grph.h:168
EDGE_BLOCKED
#define EDGE_BLOCKED
Definition: grph.h:159
EAT_FREE
#define EAT_FREE
Definition: grph.h:30
reduce_simple_sap
SCIP_RETCODE reduce_simple_sap(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:684
GRAPH::cost
SCIP_Real * cost
Definition: grph.h:94
SCIP_Real
#define SCIP_Real
Definition: def.h:163
reduce_simple_hc
SCIP_RETCODE reduce_simple_hc(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:1252
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
GRAPH::outbeg
int *RESTRICT outbeg
Definition: grph.h:76
GRAPH::edges
int edges
Definition: grph.h:92
flipedge
#define flipedge(edge)
Definition: grph.h:150
graph_knot_contract
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
Definition: grphbase.c:2433
UNKNOWN
#define UNKNOWN
Definition: sepa_mcf.c:4094
nnodes
#define nnodes
Definition: gastrans.c:65
adjust0term
static void adjust0term(SCIP *scip, GRAPH *g, int i)
Definition: reduce_simple.c:402
SCIPqueueFree
void SCIPqueueFree(SCIP_QUEUE **queue)
Definition: misc.c:957
graph_pc_knot2nonTerm
void graph_pc_knot2nonTerm(GRAPH *, int)
Definition: grphbase.c:909
graph_edge_redirect
int graph_edge_redirect(SCIP *, GRAPH *, int, int, int, SCIP_Real, SCIP_Bool)
Definition: grphbase.c:2685
STP_RPCSPG
#define STP_RPCSPG
Definition: grph.h:41
scip.h
SCIP callable library.