Scippy

SCIP

Solving Constraint Integer Programs

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