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-2019 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 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 root;
699  int nnodes;
700  int* pnode;
701  char rerun;
702 
703  assert(g != NULL);
704  assert(fixed != NULL);
705  assert(count != NULL);
706 
707  root = g->source;
708  rerun = TRUE;
709  nnodes = g->knots;
710 
711  *count = 0;
712  SCIPdebugMessage("Degree Test: ");
713 
714  /* main loop */
715  while( rerun )
716  {
717  rerun = FALSE;
718 
719  for( i = 0; i < nnodes; i++ )
720  {
721  assert(g->grad[i] >= 0);
722 
723  if( g->grad[i] == 1 )
724  {
725  e1 = g->inpbeg[i];
726  i1 = g->tail[e1];
727 
728  assert(e1 >= 0);
729  assert(e1 == Edge_anti(g->outbeg[i]));
730  assert(g->ieat[e1] == EAT_LAST);
731  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
732 
733  if( Is_term(g->term[i]) )
734  {
735  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL) );
736  *fixed += g->cost[e1];
737  SCIP_CALL( graph_knot_contract(scip, g, NULL, i1, i) );
738  }
739  else
740  {
741  graph_edge_del(scip, g, e1, TRUE);
742  }
743 
744  assert(g->grad[i] == 0);
745 
746  if ((i1 < i) && (g->grad[i1] < 3))
747  rerun = TRUE;
748 
749  (*count)++;
750 
751  continue;
752  }
753 
754  if( g->grad[i] == 2 )
755  {
756  e1 = g->outbeg[i];
757  e2 = g->oeat[e1];
758  i1 = g->head[e1];
759  i2 = g->head[e2];
760 
761  assert(e1 >= 0);
762  assert(e2 >= 0);
763 
764  if( !Is_term(g->term[i]) )
765  {
766  if( (!Is_term(g->term[i2]) && !Is_term(g->term[i1])) )
767  {
768  g->cost[e1] += g->cost[Edge_anti(e2)];
769  g->cost[Edge_anti(e1)] += g->cost[e2];
770 
771  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), g->ancestors[Edge_anti(e2)], NULL) );
772  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(e1)]), g->ancestors[e2], NULL) );
773 
774  if( SCIPisGT(scip, g->cost[e1], FARAWAY) )
775  g->cost[e1] = FARAWAY;
776  if( SCIPisGT(scip, g->cost[Edge_anti(e1)], FARAWAY) )
777  g->cost[Edge_anti(e1)] = FARAWAY;
778 
779  SCIP_CALL( graph_knot_contract(scip, g, NULL, i2, i) );
780 
781  (*count)++;
782  if( ((i1 < i) && (g->grad[i1] < 3))
783  || ((i2 < i) && (g->grad[i2] < 3)) )
784  rerun = TRUE;
785  }
786  }
787  /* CONSTCOND */
788  /*lint -save -e717 */
789  /*lint -restore */
790  }
791  }
792  }
793 
794  /* delete all arcs in \delta^-(root) */
795  for( e = g->inpbeg[root]; e != EAT_LAST; e = g->ieat[e] )
796  g->cost[e] = FARAWAY;
797 
798  /* delete all nodes not reachable from the root by forward arcs */
799 
800  /* BFS */
801  SCIP_CALL(SCIPqueueCreate(&queue, nnodes, 1.1));
802 
803  for (i = 0; i < nnodes; i++)
804  g->mark[i] = FALSE;
805 
806  g->mark[root] = TRUE;
807  SCIP_CALL(SCIPqueueInsert(queue, &(root)));
808 
809  while (!SCIPqueueIsEmpty(queue))
810  {
811  pnode = (SCIPqueueRemove(queue));
812  for (e = g->outbeg[*pnode]; e != EAT_LAST; e = g->oeat[e])
813  {
814  if( !g->mark[g->head[e]] && SCIPisLT(scip, g->cost[e], FARAWAY) )
815  {
816  g->mark[g->head[e]] = TRUE;
817  SCIP_CALL(SCIPqueueInsert(queue, &(g->head[e])));
818  }
819  }
820  }
821 
822  for (i = 0; i < nnodes; i++)
823  if( !g->mark[i] )
824  while (g->inpbeg[i] != EAT_LAST)
825  graph_edge_del(scip, g, g->inpbeg[i], TRUE);
826 
827  /* delete all nodes that cannot reach a terminal other than the root by forward arcs (not using the root) */
828 
829  /* BFS */
830 
831  assert(SCIPqueueIsEmpty(queue));
832 
833  for( i = 0; i < nnodes; i++ )
834  {
835  if( Is_term(g->term[i]) && i != root )
836  {
837  g->mark[i] = TRUE;
838  SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[g->outbeg[i]])) );
839  }
840  else
841  {
842  g->mark[i] = FALSE;
843  }
844  }
845 
846  g->mark[root] = TRUE;
847 
848  while( !SCIPqueueIsEmpty(queue) )
849  {
850  pnode = (SCIPqueueRemove(queue));
851  for( e = g->inpbeg[*pnode]; e != EAT_LAST; e = g->ieat[e] )
852  {
853  if( !g->mark[g->tail[e]] && SCIPisLT(scip, g->cost[e], FARAWAY) )
854  {
855  g->mark[g->tail[e]] = TRUE;
856  SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[e])) );
857  }
858  }
859  }
860 
861  SCIPqueueFree(&queue);
862 
863  for( i = 0; i < nnodes; i++ )
864  if( !g->mark[i] )
865  while( g->inpbeg[i] != EAT_LAST )
866  graph_edge_del(scip, g, g->inpbeg[i], TRUE);
867 
868  SCIPdebugMessage("dirdeg %d Knots deleted\n", *count);
869  assert(graph_valid(g));
870 
871  return SCIP_OKAY;
872 }
873 
874 
875 /** root proximity terminal test (SAP) */
876 SCIP_RETCODE reduce_rpt(
877  SCIP* scip, /**< SCIP data structure */
878  GRAPH* g, /**< graph data structure */
879  SCIP_Real* fixed, /**< pointer to offset value */
880  int* count /**< pointer to number of reductions */
881  )
882 {
883  SCIP_Real pathcost;
884  SCIP_Real* dijkdist;
885  int i;
886  int e;
887  int i1;
888  int e1;
889  int old;
890  int root;
891  int nnodes;
892  int* dijkedge;
893 
894  assert(scip != NULL);
895  assert(g != NULL);
896  assert(fixed != NULL);
897  assert(count != NULL);
898 
899  root = g->source;
900  nnodes = g->knots;
901  *count = 0;
902 
903  SCIP_CALL( SCIPallocBufferArray(scip, &dijkdist, nnodes) );
904  SCIP_CALL( SCIPallocBufferArray(scip, &dijkedge, nnodes) );
905 
906  graph_path_execX(scip, g, root, g->cost, dijkdist, dijkedge);
907 
908  for( i = 0; i < nnodes; i++ )
909  {
910  if( Is_term(g->term[i]) && i != root && g->grad[i] > 0 )
911  {
912  e1 = dijkedge[i];
913  pathcost = dijkdist[i];
914 
915  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
916  {
917  if( e == e1 )
918  continue;
919 
920  if( SCIPisGT(scip, pathcost, g->cost[e]) )
921  break;
922  }
923  if( e == EAT_LAST )
924  {
925  i1 = g->tail[e1];
926  old = g->grad[i] + g->grad[i1] - 1;
927 
928  SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1], NULL));
929  *fixed += g->cost[e1];
930  SCIP_CALL(graph_knot_contract(scip, g, NULL, i1, i));
931 
932  assert(old - g->grad[i1] > 0);
933  *count += old - g->grad[i1];
934  SCIPdebugMessage("contract %d\n", old - g->grad[i] - g->grad[i1]);
935  }
936 
937  }
938  }
939 
940  SCIPfreeBufferArray(scip, &dijkedge);
941  SCIPfreeBufferArray(scip, &dijkdist);
942 
943  return SCIP_OKAY;
944 }
945 
946 /** basic reduction tests for the MWCS problem */
947 SCIP_RETCODE reduce_simple_mw(
948  SCIP* scip, /**< SCIP data structure */
949  GRAPH* g, /**< graph data structure */
950  int* solnode, /**< array to indicate whether a node is part of the current solution (==CONNECT) */
951  SCIP_Real* fixed, /**< pointer to offset value */
952  int* count /**< pointer to number of reductions */
953  )
954 {
955  SCIP_Real maxprize = -1.0;
956  const int root = g->source;
957  const int nnodes = g->knots;
958  int localcount = 0;
959 
960  SCIP_Bool rerun;
961  SCIP_Bool contracted;
962 
963  assert(g != NULL);
964  assert(fixed != NULL);
965  assert(count != NULL);
966  assert(g->stp_type == STP_MWCSP);
967 
968  SCIPdebugMessage("MW degree test: \n");
969 
970  contracted = TRUE;
971  while( contracted )
972  {
973  contracted = FALSE;
974 
975  /* contract adjacent positive vertices */
976  for( int i = 0; i < nnodes; i++ )
977  {
978  int i1 = -1;
979  int grad;
980  SCIP_Bool hit;
981 
982  if( !Is_term(g->term[i]) || !(g->mark[i]) )
983  continue;
984 
985  grad = g->grad[i];
986  hit = FALSE;
987 
988  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
989  {
990  const int head = g->head[e];
991 
992  if( Is_term(g->term[head]) && head != root )
993  {
994  assert(g->mark[head]);
995 
996  if( (g->grad[head] <= grad) )
997  {
998  grad = g->grad[head];
999  i1 = head;
1000  }
1001  else if( head < i )
1002  {
1003  hit = TRUE;
1004  }
1005  }
1006  }
1007 
1008  while( i1 >= 0 )
1009  {
1010  int i2 = -1;
1011 
1012  assert(g->mark[i1]);
1013  assert(g->grad[i1] > 0);
1014  assert(Is_term(g->term[i1]));
1015 
1016  grad = g->grad[i];
1017  hit = FALSE;
1018  for( int e = g->outbeg[i1]; e != EAT_LAST; e = g->oeat[e] )
1019  {
1020  const int head = g->head[e];
1021  if( Is_term(g->term[head]) && head != i && head != root )
1022  {
1023  assert(g->mark[head]);
1024 
1025  if( (g->grad[head] <= grad) )
1026  {
1027  i2 = head;
1028  grad = g->grad[head];
1029  }
1030  else if( head < i )
1031  {
1032  hit = TRUE;
1033  }
1034  }
1035  }
1036 
1037  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i, i1, i));
1038 
1039  localcount++;
1040 
1041  i1 = i2;
1042  }
1043  if( hit )
1044  contracted = TRUE;
1045  }
1046  }
1047 
1048  /* contract adjacent 0 vertices */
1049  for( int i = 0; i < nnodes; i++ )
1050  {
1051  if( !(g->mark[i]) || !SCIPisZero(scip, g->prize[i]) )
1052  continue;
1053 
1054  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1055  {
1056  const int i2 = g->head[e];
1057 
1058  if( g->mark[i2] && SCIPisGE(scip, g->prize[i2], 0.0) )
1059  {
1060  if( Is_term(g->term[i2]) )
1061  {
1062  SCIP_CALL(graph_pc_contractEdge(scip, g, solnode, i2, i, i2));
1063  }
1064  else
1065  {
1066  SCIP_CALL( graph_pc_contractEdgeAncestors(scip, g, i2, i, flipedge_Uint(e)) );
1067  SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
1068  }
1069 
1070  localcount++;
1071  break;
1072  }
1073  }
1074  }
1075 
1076  SCIPdebugMessage("chains before: %d \n", nchains(g));
1077 
1078  rerun = TRUE;
1079 
1080  /* main loop */
1081  while( rerun )
1082  {
1083  rerun = FALSE;
1084 
1085  /* main loop for remaining tests */
1086  for( int i = 0; i < nnodes; i++ )
1087  {
1088  assert(g->grad[i] >= 0);
1089  if( !g->mark[i] || g->grad[i] == 0 )
1090  continue;
1091 
1092  assert(!Is_pterm(g->term[i]));
1093 
1094  /* non-positive vertex? */
1095  if( !Is_term(g->term[i]) )
1096  {
1097  if( g->grad[i] == 1 )
1098  {
1099  const int e1 = g->inpbeg[i];
1100  const int i1 = g->tail[e1];
1101 
1102  assert(e1 >= 0);
1103  assert(e1 == Edge_anti(g->outbeg[i]));
1104  assert(g->ieat[e1] == EAT_LAST);
1105  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
1106  assert(SCIPisLE(scip, g->prize[i], 0.0));
1107 
1108  graph_edge_del(scip, g, e1, TRUE);
1109  SCIPdebugMessage("delete negative vertex of degree 1 (%d)\n ", i);
1110  assert(g->grad[i] == 0);
1111 
1112  if( (i1 < i) && (g->grad[i1] < 3 || (g->grad[i1] == 3 && Is_term(g->term[i1]))) )
1113  rerun = TRUE;
1114 
1115  localcount++;
1116  continue;
1117  }
1118 
1119  /* contract non-positive chains */
1120  if( g->grad[i] == 2 )
1121  {
1122  int f1 = -1;
1123  int f2 = -1;
1124  int length = 0;
1125 
1126  const int e1 = g->outbeg[i];
1127  const int e2 = g->oeat[e1];
1128  const int i1 = g->head[e1];
1129  const int i2 = g->head[e2];
1130 
1131  assert(e1 >= 0);
1132  assert(e2 >= 0);
1133  assert(i1 != i2);
1134  assert(g->mark[i1]);
1135  assert(g->mark[i2]);
1136 
1137  SCIP_CALL( traverseChain(scip, g, &length, &f1, i, i1, i2, e1) );
1138  SCIP_CALL( traverseChain(scip, g, &length, &f2, i, i2, i1, e2) );
1139 
1140  if( f1 == f2 )
1141  {
1142  while( g->outbeg[i] != EAT_LAST )
1143  graph_edge_del(scip, g, g->outbeg[i], TRUE);
1144  }
1145  else if( length > 0 )
1146  {
1147  assert(g->grad[i] <= 2);
1148 
1149  for( int e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
1150  g->cost[e] = -g->prize[i];
1151 
1152  localcount += length;
1153  }
1154  }
1155  continue;
1156  }
1157 
1158  /* node i is of positive weight (terminal): */
1159 
1160  /* terminal of 0-prize? */
1161  if( SCIPisLE(scip, g->prize[i], 0.0) )
1162  {
1163  adjust0term(scip, g, i);
1164  localcount += 2;
1165  continue;
1166  }
1167 
1168  /* terminal of (real) degree 0? */
1169  if( g->grad[i] == 2 )
1170  {
1171  /* if terminal node i is not the one with the highest prize, delete */
1172  if( !is_maxprize(scip, g, i, &maxprize) )
1173  {
1174  SCIPdebugMessage("delete degree 0 term %d prize: %f count:%d\n ", i, g->prize[i], localcount);
1175  (*fixed) += g->prize[i];
1176  localcount += graph_pc_deleteTerm(scip, g, i);
1177  }
1178  }
1179  /* terminal of (real) degree 1? */
1180  else if( g->grad[i] == 3 )
1181  {
1182  int e;
1183  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1184  if( g->mark[g->head[e]] )
1185  break;
1186 
1187  assert(e != EAT_LAST);
1188  assert(g->head[e] != g->source);
1189 
1190  if( !Is_term(g->term[g->head[e]]) )
1191  {
1192  SCIP_CALL( trydg1edgepc(scip, g, fixed, NULL, count, i, e, &rerun, &maxprize) );
1193  continue;
1194  }
1195  }
1196  }
1197  }
1198 
1199  /* contract adjacent positive vertices */
1200  for( int i = 0; i < nnodes; i++ )
1201  {
1202  int i1;
1203 
1204  if( !(g->mark[i]) || !Is_term(g->term[i]) )
1205  continue;
1206 
1207  i1 = i;
1208 
1209  do
1210  {
1211  assert(g->mark[i1]);
1212  assert(g->grad[i1] > 0);
1213  assert(Is_term(g->term[i1]));
1214 
1215  contracted = FALSE;
1216 
1217  for( int e = g->outbeg[i1]; e != EAT_LAST; e = g->oeat[e] )
1218  {
1219  const int i2 = g->head[e];
1220  if( g->mark[i2] && Is_term(g->term[i2]) )
1221  {
1222  SCIPdebugMessage("contract tt after (local) main loop %d->%d\n ", i1, i2);
1223  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i1, i2, i1) );
1224  localcount++;
1225  contracted = TRUE;
1226  break;
1227  }
1228  }
1229  }
1230  while( contracted );
1231  }
1232 
1233  (*count) += localcount;
1234  SCIPdebugMessage("MW basic reduction package has deleted %d edges\n", *count);
1235 
1236  SCIPdebugMessage("chains after: %d \n", nchains(g));
1237  assert(!adjterms(g));
1238 
1239  assert(graph_valid(g));
1240 
1241  SCIP_CALL( level0save(scip, g) );
1242 
1243  return SCIP_OKAY;
1244 }
1245 
1246 /** basic reduction tests for the HCDSTP */
1247 SCIP_RETCODE reduce_simple_hc(
1248  SCIP* scip, /**< SCIP data structure */
1249  GRAPH* g, /**< graph data structure */
1250  SCIP_Real* fixed, /**< pointer to offfset value */
1251  int* count /**< pointer to number of reductions */
1252  )
1253 {
1254  int i;
1255  int e;
1256  int e2;
1257  int root;
1258  int nnodes;
1259  SCIP_Bool rerun = TRUE;
1260 
1261  assert(g != NULL);
1262  assert(fixed != NULL);
1263  assert(count != NULL);
1264  assert(g->stp_type == STP_DHCSTP);
1265 
1266  nnodes = g->knots;
1267  root = g->source;
1268 
1269  SCIPdebugMessage("basic HC test: \n");
1270 
1271  /* main loop */
1272  while( rerun )
1273  {
1274  rerun = FALSE;
1275 
1276  /* delete incoming arcs of the root */
1277  e = g->inpbeg[root];
1278  while( e != EAT_LAST )
1279  {
1280  e2 = g->ieat[e];
1281 
1282  if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
1283  {
1284  SCIPdebugMessage("delete incoming root arc \n");
1285  (*count)++;
1286  graph_edge_del(scip, g, e, TRUE);
1287  }
1288  else if( SCIPisLT(scip, g->cost[e], FARAWAY) )
1289  {
1290  SCIPdebugMessage("delete anti-parallel root arcs \n");
1291  g->cost[e] = FARAWAY;
1292  }
1293 
1294  e = e2;
1295  }
1296 
1297  /* delete outgoing arcs of the terminals (other than the root) */
1298  for( i = 0; i < nnodes; i++ )
1299  {
1300  if( Is_term(g->term[i]) && i != root )
1301  {
1302  e = g->outbeg[i];
1303  while( e != EAT_LAST )
1304  {
1305  e2 = g->oeat[e];
1306 
1307  if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
1308  {
1309  SCIPdebugMessage("delete anti-parallel terminal arcs \n");
1310  (*count)++;
1311  graph_edge_del(scip, g, e, TRUE);
1312  }
1313 
1314  e = e2;
1315  }
1316  }
1317  }
1318  }
1319 
1320  SCIPdebugMessage("HC basic reduction package has deleted %d edges\n", *count);
1321 
1322  return SCIP_OKAY;
1323 }
1324 
1325 
1326 /** basic reductions for RPCSTP and PCSPG */
1327 SCIP_RETCODE reduce_simple_pc(
1328  SCIP* scip, /**< SCIP data structure */
1329  GRAPH* g, /**< graph data structure */
1330  SCIP_Real* fixed, /**< pointer to offset value */
1331  int* count, /**< pointer to number of reductions */
1332  int* solnode, /**< solution nodes */
1333  SCIP_Bool contractroot /**< contract vertices into root (for rooted prize-collecting) */
1334  )
1335 {
1336  int edges2[2];
1337  int nodes2[2];
1338  SCIP_Real maxprize = -1.0;
1339  const int root = g->source;
1340  const int nnodes = g->knots;
1341  const SCIP_Bool pc = (g->stp_type == STP_PCSPG);
1342  SCIP_Bool rerun = TRUE;
1343 
1344  assert(g != NULL);
1345  assert(fixed != NULL);
1346  assert(count != NULL);
1347  assert(g->stp_type == STP_PCSPG || g->stp_type == STP_RPCSPG);
1348  assert(!g->extended);
1349 
1350  *count = 0;
1351 
1352  SCIPdebugMessage("Degree Test: ");
1353 
1354  if( !pc )
1355  g->mark[root] = FALSE;
1356 
1357  /* main loop */
1358  while( rerun )
1359  {
1360  rerun = FALSE;
1361 
1362  for( int i = 0; i < nnodes; i++ )
1363  {
1364  assert(g->grad[i] >= 0);
1365  assert(!(g->mark[i] && Is_pterm(g->term[i])));
1366 
1367  /* last condition should never be true, but just in case ... */
1368  if( !g->mark[i] || g->grad[i] == 0 || Is_pterm(g->term[i]) )
1369  continue;
1370 
1371  if( !Is_term(g->term[i]) )
1372  {
1373  assert(SCIPisZero(scip, g->prize[i]));
1374 
1375  if( g->grad[i] == 1 )
1376  {
1377  const int e1 = g->inpbeg[i];
1378  const int i1 = g->tail[e1];
1379 
1380  assert(e1 >= 0);
1381  assert(e1 == Edge_anti(g->outbeg[i]));
1382  assert(g->ieat[e1] == EAT_LAST);
1383  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
1384 
1385  graph_edge_del(scip, g, e1, TRUE);
1386  SCIPdebugMessage("delete non-terminal of degree 1 %d\n ", i);
1387  (*count)++;
1388 
1389  assert(g->grad[i] == 0);
1390 
1391  /* the last node? */
1392  if( g->grad[i1] == 0 )
1393  {
1394  rerun = FALSE;
1395  break;
1396  }
1397  if( (i1 < i) && (g->grad[i1] < 3 || Is_term(g->term[i1])) )
1398  rerun = TRUE;
1399 
1400  continue;
1401  }
1402 
1403  /* contract non terminals of degree 2 */
1404  if( g->grad[i] == 2 )
1405  {
1406  const int e1 = g->outbeg[i];
1407  const int e2 = g->oeat[e1];
1408  const int i1 = g->head[e1];
1409  const int i2 = g->head[e2];
1410 
1411  assert(e1 >= 0);
1412  assert(e2 >= 0);
1413 
1414  assert(g->mark[i1] || i1 == g->source);
1415  assert(g->mark[i2] || i2 == g->source);
1416  assert(SCIPisEQ(scip, g->cost[e2], g->cost[flipedge(e2)]));
1417 
1418  g->cost[e1] += g->cost[e2];
1419  g->cost[flipedge(e1)] += g->cost[e2];
1420 
1421  SCIPdebugMessage("contract non-terminals %d %d \n ", i2, i);
1422  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), g->ancestors[flipedge(e2)], NULL) );
1423  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(e1)]), g->ancestors[e2], NULL) );
1424 
1425  SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
1426  (*count)++;
1427 
1428  if( (Is_term(g->term[i2]) && (i2 < i)) || (Is_term(g->term[i1]) && (i1 < i)) )
1429  rerun = TRUE;
1430  }
1431  continue;
1432  }
1433 
1434  /*
1435  * node i is a terminal:
1436  */
1437 
1438  /* terminal of 0-prize? */
1439  if( SCIPisLE(scip, g->prize[i], 0.0) && i != root )
1440  {
1441  adjust0term(scip, g, i);
1442  (*count) += 2;
1443  continue;
1444  }
1445 
1446  assert(Is_term(g->term[i]));
1447 
1448  /* terminal of (real) degree 0? */
1449  if( ( (g->grad[i] == 2 && pc) || (g->grad[i] == 1 && !pc) ) )
1450  {
1451  /* if terminal node i is node the one with the highest prize, delete */
1452  if( !is_maxprize(scip, g, i, &maxprize) )
1453  {
1454  SCIPdebugMessage("delete 0 term %d prize: %f count:%d\n ", i, g->prize[i], *count);
1455  (*fixed) += g->prize[i];
1456  (*count) += graph_pc_deleteTerm(scip, g, i);
1457  }
1458  }
1459  /* terminal of (real) degree 1? */
1460  else if( ( (g->grad[i] == 3 && pc) || (g->grad[i] == 2 && !pc) ) )
1461  {
1462  int e;
1463  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1464  if( g->mark[g->head[e]] || (!pc && g->head[e] == root) )
1465  break;
1466 
1467  assert(e != EAT_LAST);
1468  assert(g->head[e] != root || !pc);
1469 
1470  SCIP_CALL( trydg1edgepc(scip, g, fixed, solnode, count, i, e, &rerun, &maxprize) );
1471  }
1472  /* terminal of (real) degree 2? */
1473  else if( ( (g->grad[i] == 4 && pc) || (g->grad[i] == 3 && !pc) ) )
1474  {
1475  if( !is_maxprize(scip, g, i, &maxprize) )
1476  {
1477  int i2 = 0;
1478  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1479  {
1480  const int i1 = g->head[e];
1481  if( g->mark[i1] || (!pc && i1 == root) )
1482  {
1483  assert(i2 < 2);
1484 
1485  edges2[i2] = e;
1486  nodes2[i2++] = i1;
1487  }
1488  }
1489 
1490  assert(i2 >= 2);
1491  if( SCIPisLE(scip, g->prize[i], g->cost[edges2[0]]) && SCIPisLE(scip, g->prize[i], g->cost[edges2[1]]) )
1492  {
1493  IDX* ancestors = NULL;
1494  IDX* revancestors = NULL;
1495  int n1;
1496  const int e = edges2[0];
1497  const int e1 = edges2[1];
1498 
1499  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e], NULL) );
1500  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[Edge_anti(e1)], NULL) );
1501  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[Edge_anti(e)], NULL) );
1502  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[e1], NULL) );
1503  SCIPdebugMessage("delete - term - %d\n ", i);
1504 
1505  /* contract edge */
1506  n1 = graph_edge_redirect(scip, g, e, nodes2[1], nodes2[0], g->cost[e] + g->cost[e1] - g->prize[i], TRUE);
1507 
1508  /* new edge inserted? */
1509  if( n1 >= 0)
1510  {
1511  /* add ancestors */
1512  SCIPintListNodeFree(scip, &(g->ancestors[n1]));
1513  SCIPintListNodeFree(scip, &(g->ancestors[Edge_anti(n1)]));
1514  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[n1]), ancestors, NULL) );
1515  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(n1)]), revancestors, NULL) );
1516  }
1517  (*count) += graph_pc_deleteTerm(scip, g, i);
1518  (*fixed) += g->prize[i];
1519  SCIPintListNodeFree(scip, &(ancestors));
1520  SCIPintListNodeFree(scip, &(revancestors));
1521  }
1522  }
1523  }
1524 
1525  /* try to contract adjacent terminals */
1526  if( g->grad[i] > 0 )
1527  {
1528  SCIP_Real mincost = FARAWAY;
1529  int ett = UNKNOWN;
1530 
1531  for( int e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
1532  {
1533  const int i1 = g->head[e1];
1534 
1535  if( !g->mark[i1] && (pc || i1 != root || !contractroot) )
1536  continue;
1537 
1538  if( SCIPisLT(scip, g->cost[e1], mincost) )
1539  {
1540  mincost = g->cost[e1];
1541  if( Is_term(g->term[i1]) )
1542  ett = e1;
1543  }
1544  else if( Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e1], mincost) )
1545  {
1546  assert(SCIPisLT(scip, g->cost[e1], FARAWAY));
1547  assert(SCIPisEQ(scip, g->cost[e1], mincost));
1548  ett = e1;
1549  }
1550  }
1551 
1552  if( ett != UNKNOWN && SCIPisLE(scip, g->cost[ett], mincost) && SCIPisLE(scip, g->cost[ett], g->prize[i])
1553  && SCIPisLE(scip, g->cost[ett], g->prize[g->head[ett]]) )
1554  {
1555  const int i1 = g->head[ett];
1556  SCIPdebugMessage("contract tt %d->%d\n ", i, i1);
1557  assert(SCIPisLT(scip, mincost, FARAWAY));
1558  *fixed += g->cost[ett];
1559  (*count)++;
1560 
1561  if( i1 == root )
1562  {
1563  int j;
1564  int e;
1565 
1566  /* get edge from i to its artificial terminal */
1567  for (e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e])
1568  if( Is_pterm(g->term[g->head[e]]) && g->head[e] != root )
1569  break;
1570 
1571  assert(e != EAT_LAST);
1572  SCIPdebugMessage("contract rt %d->%d \n", i, i1);
1573 
1574  if( g->pcancestors[i] != NULL )
1575  {
1576  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->pcancestors[i], NULL));
1577  SCIPintListNodeFree(scip, &(g->pcancestors[i]));
1578  }
1579  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[ett], NULL));
1580 
1581  /* artificial terminal to i */
1582  j = g->head[e];
1583  assert(!g->mark[j]);
1584 
1585  /* delete edge and unmark artificial terminal */
1586  graph_pc_knot2nonTerm(g, j);
1587  graph_edge_del(scip, g, e, TRUE);
1588 
1589  /* delete remaining incident edge of artificial terminal */
1590  e = g->inpbeg[j];
1591 
1592  assert(e != EAT_LAST);
1593  assert(g->source == g->tail[e] || g->source == j);
1594  assert(SCIPisEQ(scip, g->prize[i], g->cost[e]));
1595 
1596  graph_edge_del(scip, g, e, TRUE);
1597 
1598  assert(g->inpbeg[j] == EAT_LAST);
1599 
1600  SCIP_CALL(graph_knot_contract(scip, g, solnode, i1, i));
1601  graph_pc_knot2nonTerm(g, i);
1602  } /* i1 == root */
1603  else
1604  {
1605  if( g->grad[i] >= g->grad[i1] )
1606  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i, i1, i) );
1607  else
1608  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, i1, i, i1) );
1609  }
1610 
1611  rerun = TRUE;
1612  }
1613  } /* contract adjacent terminals */
1614  } /* for i = 1, ..., nnodes */
1615  } /* main loops */
1616 
1617  if( !pc )
1618  g->mark[root] = TRUE;
1619  SCIPdebugMessage("degree test pc: %d nodes deleted\n", *count);
1620 
1621  assert(graph_valid(g));
1622 
1623  SCIP_CALL( level0save(scip, g) );
1624 
1625  return SCIP_OKAY;
1626 }
level0save
SCIP_RETCODE level0save(SCIP *, GRAPH *)
Definition: reduce.c:185
Int_List_Node
Definition: misc_stp.h:74
reduce_simple
SCIP_RETCODE reduce_simple(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *solnode, int *nelims, int *edgestate)
Definition: reduce_simple.c:489
NULL
#define NULL
Definition: def.h:246
GRAPH::head
int *RESTRICT head
Definition: grph.h:96
GRAPH
Definition: grph.h:57
GRAPH::source
int source
Definition: grph.h:67
graph_valid
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4324
graph_pc_deleteTerm
int graph_pc_deleteTerm(SCIP *, GRAPH *, int)
Definition: grphbase.c:1941
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:568
SCIPqueueInsert
SCIP_RETCODE SCIPqueueInsert(SCIP_QUEUE *queue, void *elem)
Definition: misc.c:1018
EAT_LAST
#define EAT_LAST
Definition: grph.h:31
Edge_anti
#define Edge_anti(a)
Definition: grph.h:171
FALSE
#define FALSE
Definition: def.h:72
GRAPH::inpbeg
int *RESTRICT inpbeg
Definition: grph.h:74
TRUE
#define TRUE
Definition: def.h:71
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
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:1327
graph_pc_contractEdgeAncestors
SCIP_RETCODE graph_pc_contractEdgeAncestors(SCIP *, GRAPH *, int, int, int)
Definition: grphbase.c:2075
STP_PCSPG
#define STP_PCSPG
Definition: grph.h:40
SCIPdebugMessage
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:516
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
SCIPqueueIsEmpty
SCIP_Bool SCIPqueueIsEmpty(SCIP_QUEUE *queue)
Definition: misc.c:1173
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:2101
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
reduce_rpt
SCIP_RETCODE reduce_rpt(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:876
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:2662
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
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:529
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
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:358
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
SCIPqueueFree
void SCIPqueueFree(SCIP_QUEUE **queue)
Definition: misc.c:956
FARAWAY
#define FARAWAY
Definition: grph.h:156
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_Bool
#define SCIP_Bool
Definition: def.h:69
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:947
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:2837
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
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:555
SCIPqueueCreate
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition: misc.c:932
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:157
reduce_simple_hc
SCIP_RETCODE reduce_simple_hc(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:1247
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
SCIPqueueRemove
void * SCIPqueueRemove(SCIP_QUEUE *queue)
Definition: misc.c:1069
graph_knot_contract
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
Definition: grphbase.c:2429
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:629
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:542
UNKNOWN
#define UNKNOWN
Definition: sepa_mcf.c:4081
nnodes
#define nnodes
Definition: gastrans.c:65
adjust0term
static void adjust0term(SCIP *scip, GRAPH *g, int i)
Definition: reduce_simple.c:402
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:2681
STP_RPCSPG
#define STP_RPCSPG
Definition: grph.h:41
scip.h
SCIP callable library.