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-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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file reduce_simple.c
17  * @brief several basic reductions for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements simple reduction techniques for several Steiner problems.
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 //#define SCIP_DEBUG
29 
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <string.h>
33 #include <assert.h>
34 #include "graph.h"
35 #include "reduce.h"
36 #include "portab.h"
37 #include "scip/scip.h"
38 
39 
40 #ifdef SCIP_DISABLED
41 /** deletes entire graph */
42 static
43 void deleteAllEdges(
44  SCIP* scip, /**< SCIP data structure */
45  GRAPH* g /**< graph data structure */
46 )
47 {
48  const int nedges = graph_get_nEdges(g);
49 
50  for( int e = 0; e < nedges; e += 2 )
51  {
52  if( g->oeat[e] != EAT_FREE )
53  graph_edge_del(scip, g, e, TRUE);
54  }
55 }
56 #endif
57 
58 
59 /** prune */
60 static
62  SCIP* scip, /**< SCIP data structure */
63  int start, /**< the node to start from */
64  int end, /**< note to ignore */
65  int cutedge, /**< the edge */
66  GRAPH* g /**< graph data structure */
67 )
68 {
69  if( Is_term(g->term[start]) )
70  {
71  int e = g->outbeg[start];
72 
73  while( e >= 0 )
74  {
75  const int enext = g->oeat[e];
76  const int head = g->head[e];
77  if( head != end )
78  {
79  assert(!Is_term(g->term[head]));
80  graph_edge_del(scip, g, e, TRUE);
81  }
82 
83  e = enext;
84  }
85  }
86  else
87  {
88  graph_edge_del(scip, g, cutedge, TRUE);
89  }
90 
91  SCIP_CALL( reduce_unconnected(scip, g) );
92 
93  return SCIP_OKAY;
94 }
95 
96 
97 /** probe */
98 static
100  SCIP* scip, /**< SCIP data structure */
101  const GRAPH* g, /**< graph data structure */
102  int start, /**< the node to start from */
103  int end, /**< note to ignore */
104  SCIP_Bool* RESTRICT nodes_visited, /**< marks for each node whether visited or not */
105  SCIP_Bool* terminalFound /**< found? */
106 )
107 {
108  int* RESTRICT stackarr;
109  int stacksize = 0;
110  const int nnodes = graph_get_nNodes(g);
111  *terminalFound = FALSE;
112 
113  SCIP_CALL( SCIPallocBufferArray(scip, &stackarr, nnodes) );
114 
115  nodes_visited[start] = TRUE;
116  nodes_visited[end] = TRUE;
117  stackarr[stacksize++] = start;
118 
119  while( stacksize > 0 )
120  {
121  const int node = stackarr[--stacksize];
122 
123  for( int e = g->outbeg[node]; e != EAT_LAST; e = g->oeat[e] )
124  {
125  const int head = g->head[e];
126 
127  if( !nodes_visited[head] )
128  {
129  if( Is_term(g->term[head]) )
130  {
131  *terminalFound = TRUE;
132  stacksize = 0;
133  break;
134  }
135 
136  nodes_visited[head] = TRUE;
137  stackarr[stacksize++] = head;
138  }
139  }
140  }
141 
142  SCIPfreeBuffer(scip, &stackarr)
143 
144  return SCIP_OKAY;
145 }
146 
147 
148 /** removes nodes of degree one and unmarks */
150  SCIP* scip, /**< SCIP */
151  GRAPH* graph /**< graph data structure (in/out) */
152 )
153 {
154  const int nnodes = graph_get_nNodes(graph);
155  SCIP_Bool rerun = TRUE;
156 
157  while( rerun )
158  {
159  rerun = FALSE;
160  for( int i = 0; i < nnodes; ++i )
161  {
162  if( graph->grad[i] == 1 && !Is_term(graph->term[i]) )
163  {
164  const int sibling = graph->head[graph->outbeg[i]];
165  assert(graph_knot_isInRange(graph, sibling));
166 
167  graph_knot_del(scip, graph, i, TRUE);
168  graph->mark[i] = FALSE;
169 
170  if( Is_term(graph->term[sibling]) )
171  continue;
172 
173  if( graph->grad[sibling] == 0 )
174  graph->mark[sibling] = FALSE;
175  else if( graph->grad[sibling] == 1 )
176  rerun = TRUE;
177  }
178  }
179  }
180 }
181 
182 
183 /** basic reduction tests for the STP */
185  SCIP* scip, /**< SCIP data structure */
186  GRAPH* g, /**< graph data structure */
187  SCIP_Real* fixed, /**< pointer to offset value */
188  int* solnode, /**< node array to mark whether an node is part of a given solution (CONNECT),
189  or NULL */
190  int* nelims, /**< pointer to number of reductions */
191  int* edgestate /**< array to store status of (directed) edge (for propagation, can otherwise be set to NULL) */
192  )
193 {
194  SCIP_Bool rerun = TRUE;
195  int elimscount = 0;
196  const int nnodes = g->knots;
197  const SCIP_Bool checkstate = (edgestate != NULL);
198  SCIP_Bool replaceConflict = FALSE;
199 
200  assert(scip && g && fixed && nelims);
201 
202  SCIPdebugMessage("Degree Test: ");
203 
204  /* main loop */
205  while( rerun )
206  {
207  rerun = FALSE;
208 
209  for( int i = 0; i < nnodes; i++ )
210  {
211  assert(g->grad[i] >= 0);
212 
213  if( g->grad[i] == 1 && g->terms > 1 )
214  {
215  const int e1 = g->outbeg[i];
216  const int i1 = g->head[e1];
217 
218  assert(e1 >= 0);
219  assert(e1 == Edge_anti(g->inpbeg[i]));
220  assert(g->oeat[e1] == EAT_LAST);
221  assert(g->ieat[g->inpbeg[i]] == EAT_LAST);
222 
223  if( checkstate )
224  {
225  if( edgestate[e1] == EDGE_BLOCKED || Is_term(g->term[i]) )
226  continue;
227  else
228  {
229  SCIPdebugMessage("delete degree 1 node: %d \n", i);
230  graph_edge_del(scip, g, e1, TRUE);
231  }
232  }
233  else
234  {
235  if( Is_term(g->term[i]) )
236  {
237  *fixed += g->cost[e1];
238  SCIP_CALL( graph_fixed_addEdge(scip, e1, g) );
239  }
240 
241  SCIPdebugMessage("contract degree 1 terminal: %d \n", i);
242  SCIP_CALL( graph_knot_contract(scip, g, solnode, i1, i) );
243  }
244  elimscount++;
245 
246  assert(g->grad[i] == 0);
247 
248  /* the last node in the graph? */
249  if( g->grad[i1] == 0 )
250  {
251  rerun = FALSE;
252  break;
253  }
254  if( (i1 < i) && (g->grad[i1] < 3) )
255  rerun = TRUE;
256 
257  continue;
258  }
259 
260  if( g->grad[i] == 2 && !checkstate )
261  {
262  const int e1 = g->outbeg[i];
263  const int e2 = g->oeat[e1];
264  const int i1 = g->head[e1];
265  const int i2 = g->head[e2];
266  SCIP_Bool eliminationDone = TRUE;
267 
268  assert(e1 >= 0);
269  assert(e2 >= 0);
270 
271  do
272  {
273  if( !Is_term(g->term[i]) )
274  {
275  SCIP_Bool conflict;
276  SCIPdebugMessage("replace degree 2 node: %d \n", i);
277  SCIP_CALL( graph_knot_replaceDeg2(scip, i, g->cost[e1] + g->cost[e2], -1, g, &conflict) );
278 
279  if( conflict)
280  replaceConflict = TRUE;
281 
282  elimscount++;
283 
284  break;
285  }
286  assert(Is_term(g->term[i]));
287 
288  if( Is_term(g->term[i1]) && Is_term(g->term[i2]) )
289  {
290  SCIPdebugMessage("contract degree 2 terminal (with terminal neighbors): %d \n", i);
291 
292  if( SCIPisLT(scip, g->cost[e1], g->cost[e2]) )
293  {
294  *fixed += g->cost[e1];
295 
296  SCIP_CALL( graph_fixed_addEdge(scip, e1, g) );
297  SCIP_CALL( graph_knot_contract(scip, g, solnode, i1, i) );
298  }
299  else
300  {
301  *fixed += g->cost[e2];
302 
303  SCIP_CALL( graph_fixed_addEdge(scip, e2, g) );
304  SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
305  }
306  elimscount++;
307 
308  break;
309  }
310  if( Is_term(g->term[i1]) && !Is_term(g->term[i2]) && SCIPisLE(scip, g->cost[e1], g->cost[e2]) )
311  {
312  SCIPdebugMessage("contract degree 2 terminal (with one terminal neighbor): %d \n", i);
313 
314  *fixed += g->cost[e1];
315 
316  SCIP_CALL( graph_fixed_addEdge(scip, e1, g) );
317  SCIP_CALL( graph_knot_contract(scip, g, solnode, i1, i) );
318  elimscount++;
319  break;
320  }
321  if( Is_term(g->term[i2]) && !Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e2], g->cost[e1]) )
322  {
323  SCIPdebugMessage("contract degree 2 terminal (with one terminal neighbor): %d \n", i);
324 
325  *fixed += g->cost[e2];
326 
327  SCIP_CALL( graph_fixed_addEdge(scip, e2, g) );
328  SCIP_CALL( graph_knot_contract(scip, g, solnode, i2, i) );
329  elimscount++;
330  break;
331  }
332  eliminationDone = FALSE;
333  }
334  while( FALSE );
335 
336  if( eliminationDone && (((i1 < i) && (g->grad[i1] < 3)) || ((i2 < i) && (g->grad[i2] < 3))) )
337  rerun = TRUE;
338  }
339 
340  if( Is_term(g->term[i]) && g->grad[i] > 2 && !checkstate )
341  {
342  SCIP_Real mincost = FARAWAY;
343  int ett = UNKNOWN;
344  for( int e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
345  {
346  const int i1 = g->head[e1];
347 
348  if( SCIPisLT(scip, g->cost[e1], mincost) )
349  {
350  mincost = g->cost[e1];
351  if( Is_term(g->term[i1]) )
352  ett = e1;
353  }
354  else if( Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e1], mincost) )
355  {
356  ett = e1;
357  }
358  }
359  if( ett != UNKNOWN && SCIPisLE(scip, g->cost[ett], mincost) )
360  {
361  SCIPdebugMessage("contract terminal into terminal: %d \n", i);
362 
363  *fixed += g->cost[ett];
364 
365  SCIP_CALL( graph_fixed_addEdge(scip, ett, g) );
366  SCIP_CALL( graph_knot_contractLowdeg2High(scip, g, solnode, i, g->head[ett]) );
367 
368  rerun = TRUE;
369  }
370  }
371  }
372  }
373 
374  /* NOTE: in this case we might have made the graph unconnected... */
375  if( replaceConflict )
376  {
377  SCIP_CALL( reduce_unconnected(scip, g) );
378  }
379 
380  /* todo: seems to hurt performance in ascend-prune, not sure why.... */
381 #ifdef SCIP_DISABLED
382  if( g->terms == 1 )
383  {
384  deleteAllEdges(scip, g);
385  }
386 #endif
387 
388  SCIPdebugMessage(" %d Knots deleted\n", elimscount);
389  assert(graph_valid(scip, g));
390 
391  *nelims += elimscount;
392  return SCIP_OKAY;
393 }
394 
395 
396 /** basic reduction tests for the SAP */
398  SCIP* scip, /**< SCIP data structure */
399  GRAPH* g, /**< graph data structure */
400  SCIP_Real* fixed, /**< pointer to offfset value */
401  int* count /**< pointer to number of reductions */
402  )
403 {
404  SCIP_QUEUE* queue;
405  int e;
406  int i1;
407  int i2;
408  int e1;
409  int e2;
410  const int nnodes = graph_get_nNodes(g);
411  char rerun;
412 
413  assert(g != NULL);
414  assert(fixed != NULL);
415  assert(count != NULL);
416 
417  rerun = TRUE;
418  *count = 0;
419 
420  SCIPdebugMessage("Degree Test: \n");
421 
422  /* main loop */
423  while( rerun )
424  {
425  rerun = FALSE;
426 
427  for( int i = 0; i < nnodes; i++ )
428  {
429  assert(g->grad[i] >= 0);
430 
431  if( g->grad[i] == 1 )
432  {
433  e1 = g->inpbeg[i];
434  i1 = g->tail[e1];
435 
436  assert(e1 >= 0);
437  assert(e1 == Edge_anti(g->outbeg[i]));
438  assert(g->ieat[e1] == EAT_LAST);
439  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
440 
441  if( Is_term(g->term[i]) )
442  {
443  if( g->terms == 1 )
444  continue;
445 
446  if( i == g->source )
447  {
448  e2 = flipedge(e1);
449  *fixed += g->cost[e2];
450 
451  SCIPdebugMessage("contract grad-1 terminal (source) \n");
452  SCIP_CALL( graph_knot_contractFixed(scip, g, NULL, e2, i1, i) );
453  }
454  else
455  {
456  *fixed += g->cost[e1];
457 #ifdef SCIP_DEBUG
458  SCIPdebugMessage("contract grad-1 terminal ");
459  graph_knot_printInfo(g, i);
460  SCIPdebugMessage("with edge ");
461  graph_edge_printInfo(g, e1);
462  SCIPdebugMessage("into ");
463  graph_knot_printInfo(g, i1);
464 #endif
465 
466  SCIP_CALL( graph_knot_contractFixed(scip, g, NULL, e1, i1, i) );
467  }
468  }
469  else
470  {
471  graph_edge_del(scip, g, e1, TRUE);
472  SCIPdebugMessage("delete grad-1 node \n");
473  }
474 
475  assert(g->grad[i] == 0);
476 
477  if ((i1 < i) && (g->grad[i1] < 3))
478  rerun = TRUE;
479 
480  (*count)++;
481 
482  continue;
483  }
484 
485  if( g->grad[i] == 2 )
486  {
487  e1 = g->outbeg[i];
488  e2 = g->oeat[e1];
489  i1 = g->head[e1];
490  i2 = g->head[e2];
491 
492  assert(e1 >= 0);
493  assert(e2 >= 0);
494 
495  if( !Is_term(g->term[i]) )
496  {
497  if( (!Is_term(g->term[i2]) && !Is_term(g->term[i1])) )
498  {
499  g->cost[e1] += g->cost[Edge_anti(e2)];
500  g->cost[Edge_anti(e1)] += g->cost[e2];
501 
504 
505  if( SCIPisGT(scip, g->cost[e1], FARAWAY) )
506  g->cost[e1] = FARAWAY;
507  if( SCIPisGT(scip, g->cost[Edge_anti(e1)], FARAWAY) )
508  g->cost[Edge_anti(e1)] = FARAWAY;
509 
510  SCIP_CALL( graph_knot_contract(scip, g, NULL, i2, i) );
511 
512  SCIPdebugMessage("replace grad-2 node %d \n", i);
513 
514  (*count)++;
515  if( ((i1 < i) && (g->grad[i1] < 3))
516  || ((i2 < i) && (g->grad[i2] < 3)) )
517  rerun = TRUE;
518  }
519  }
520  /* CONSTCOND */
521  /*lint -save -e717 */
522  /*lint -restore */
523  }
524  }
525  }
526 
527  /* delete all arcs in \delta^-(root) */
528  for( e = g->inpbeg[g->source]; e != EAT_LAST; e = g->ieat[e] )
529  g->cost[e] = FARAWAY;
530 
531  /* delete all nodes not reachable from the root by forward arcs */
532 
533  /* BFS */
534  SCIP_CALL(SCIPqueueCreate(&queue, nnodes, 1.1));
535 
536  for (int i = 0; i < nnodes; i++)
537  g->mark[i] = FALSE;
538 
539  g->mark[g->source] = TRUE;
540  SCIP_CALL(SCIPqueueInsert(queue, &(g->source)));
541 
542  while (!SCIPqueueIsEmpty(queue))
543  {
544  int* pnode = (SCIPqueueRemove(queue));
545  for (e = g->outbeg[*pnode]; e != EAT_LAST; e = g->oeat[e])
546  {
547  if( !g->mark[g->head[e]] && LT(g->cost[e], FARAWAY) )
548  {
549  g->mark[g->head[e]] = TRUE;
550  SCIP_CALL(SCIPqueueInsert(queue, &(g->head[e])));
551  }
552  }
553  }
554 
555  for( int i = 0; i < nnodes; i++ )
556  {
557  if( !g->mark[i] && g->grad[i] > 0 )
558  {
559  assert(!Is_term(g->term[i]));
560  SCIPdebugMessage("deleting unreachable (forward) node %d \n", i);
561  graph_knot_del(scip, g, i, TRUE);
562  }
563  }
564 
565  /* delete all nodes that cannot reach a terminal other than the root by forward arcs (not using the root) */
566 
567  /* BFS */
568 
569  assert(SCIPqueueIsEmpty(queue));
570 
571  for( int i = 0; i < nnodes; i++ )
572  {
573  if( Is_term(g->term[i]) && i != g->source )
574  {
575  g->mark[i] = TRUE;
576  SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[g->outbeg[i]])) );
577  }
578  else
579  {
580  g->mark[i] = FALSE;
581  }
582  }
583 
584  g->mark[g->source] = TRUE;
585 
586  while( !SCIPqueueIsEmpty(queue) )
587  {
588  int* pnode = (SCIPqueueRemove(queue));
589  for( e = g->inpbeg[*pnode]; e != EAT_LAST; e = g->ieat[e] )
590  {
591  if( !g->mark[g->tail[e]] && LT(g->cost[e], FARAWAY) )
592  {
593  g->mark[g->tail[e]] = TRUE;
594  SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[e])) );
595  }
596  }
597  }
598 
599  SCIPqueueFree(&queue);
600 
601  for( int i = 0; i < nnodes; i++ )
602  {
603  if( !g->mark[i] && g->grad[i] > 0 )
604  {
605  assert(!Is_term(g->term[i]));
606  SCIPdebugMessage("deleting unreachable (backward) node %d \n", i);
607  graph_knot_del(scip, g, i, TRUE);
608  }
609  }
610 
611  SCIPdebugMessage("dirdeg %d Knots deleted\n", *count);
612  assert(graph_valid(scip, g));
613 
614  return SCIP_OKAY;
615 }
616 
617 
618 /** basic reduction tests for the DCSTP...call only once! */
620  SCIP* scip, /**< SCIP data structure */
621  GRAPH* g /**< graph data structure */
622  )
623 {
624  const int nnodes = graph_get_nNodes(g);
625  const int* const maxdeg = g->maxdeg;
626 
627  assert(g->stp_type == STP_DCSTP);
628  assert(scip);
629  assert(g->maxdeg);
630 
631  if( g->terms <= 2 )
632  return;
633 
634  for( int i = 0; i < nnodes; i++ )
635  {
636  int enext;
637 
638  if( maxdeg[i] != 1 )
639  continue;
640 
641  for( int e = g->outbeg[i]; e != EAT_LAST; e = enext )
642  {
643  const int head = g->head[e];
644  enext = g->oeat[e];
645  if( maxdeg[head] == 1 )
646  {
647  graph_edge_del(scip, g, e, TRUE);
648  }
649  }
650  }
651 }
652 
653 
654 /** basic reduction tests for the HCDSTP */
656  SCIP* scip, /**< SCIP data structure */
657  GRAPH* g, /**< graph data structure */
658  SCIP_Real* fixed, /**< pointer to offfset value */
659  int* count /**< pointer to number of reductions */
660  )
661 {
662  int i;
663  int e;
664  int e2;
665  int nnodes;
666  SCIP_Bool rerun = TRUE;
667 
668  assert(g != NULL);
669  assert(fixed != NULL);
670  assert(count != NULL);
671  assert(g->stp_type == STP_DHCSTP);
672 
673  nnodes = g->knots;
674 
675  SCIPdebugMessage("basic HC test: \n");
676 
677  /* main loop */
678  while( rerun )
679  {
680  rerun = FALSE;
681 
682  /* delete incoming arcs of the root */
683  e = g->inpbeg[g->source];
684  while( e != EAT_LAST )
685  {
686  e2 = g->ieat[e];
687 
688  if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
689  {
690  SCIPdebugMessage("delete incoming root arc \n");
691  (*count)++;
692  graph_edge_del(scip, g, e, TRUE);
693  }
694  else if( SCIPisLT(scip, g->cost[e], FARAWAY) )
695  {
696  SCIPdebugMessage("delete anti-parallel root arcs \n");
697  g->cost[e] = FARAWAY;
698  }
699 
700  e = e2;
701  }
702 
703  /* delete outgoing arcs of the terminals (other than the root) */
704  for( i = 0; i < nnodes; i++ )
705  {
706  if( Is_term(g->term[i]) && i != g->source )
707  {
708  e = g->outbeg[i];
709  while( e != EAT_LAST )
710  {
711  e2 = g->oeat[e];
712 
713  if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
714  {
715  SCIPdebugMessage("delete anti-parallel terminal arcs \n");
716  (*count)++;
717  graph_edge_del(scip, g, e, TRUE);
718  }
719 
720  e = e2;
721  }
722  }
723  }
724  }
725 
726  SCIPdebugMessage("HC basic reduction package has deleted %d edges\n", *count);
727 
728  return SCIP_OKAY;
729 }
730 
731 
732 /** contract edges of weight zero */
734  SCIP* scip, /**< SCIP data structure */
735  GRAPH* g, /**< graph data structure */
736  int* solnode, /**< solution node mark or NULL */
737  SCIP_Bool savehistory /**< save the history? */
738  )
739 {
740  int count;
741  int nedges;
742 
743  assert(g != NULL);
744  assert(scip != NULL);
745 
746  nedges = g->edges;
747 
748  do
749  {
750  count = 0;
751  for( int e = 0; e < nedges; e += 2 )
752  {
753  if( g->oeat[e] != EAT_FREE && SCIPisZero(scip, g->cost[e]) && SCIPisZero(scip, g->cost[flipedge(e)]) )
754  {
755  if( savehistory )
756  {
757  if( graph_pc_isPcMw(g) )
758  {
759  IDX* ans = graph_edge_getAncestors(g, e);
760  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->pcancestors[g->head[e]]), ans, NULL) );
761  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->pcancestors[g->tail[e]]), ans, NULL) );
762  assert(0 && "currently not implemented");
763  }
764  else
765  {
766  SCIP_CALL( graph_fixed_addEdge(scip, e, g) );
767  }
768 
769  }
770 
771  SCIP_CALL( graph_knot_contract(scip, g, solnode, g->tail[e], g->head[e]) );
772  count++;
773  }
774  }
775  } while( count > 0 );
776 
777  return SCIP_OKAY;
778 }
779 
780 
781 /* removes parallel edges */
783  SCIP* scip, /**< SCIP data structure */
784  GRAPH* g /**< graph data structure */
785 )
786 {
787  const int nnodes = g->knots;
788  int* count;
789 
790  assert(scip != NULL);
791  assert(g != NULL);
792 
793  SCIP_CALL( SCIPallocBufferArray(scip, &count, nnodes) );
794 
795  for( int k = 0; k < nnodes; k++ )
796  count[k] = 0;
797 
798  for( int k = 0; k < nnodes; k++ )
799  {
800  int enext;
801  for( int e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
802  {
803  const int head = g->head[e];
804  count[head]++;
805  }
806 
807  for( int e = g->outbeg[k]; e != EAT_LAST; e = enext )
808  {
809  const int head = g->head[e];
810  enext = g->oeat[e];
811 
812  if( count[head] > 1 )
813  {
814  graph_edge_del(scip, g, e, TRUE);
815  return SCIP_ERROR;
816  }
817  count[head]--;
818 
819  }
820 
821  for( int e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
822  assert(count[g->head[e]] == 0);
823  }
824 
825  SCIPfreeBufferArray(scip, &count);
826 
827  return SCIP_OKAY;
828 }
829 
830 
831 /** basic reductions */
833  SCIP* scip, /**< SCIP data structure */
834  const int* edgestate, /**< for propagation or NULL */
835  GRAPH* g, /**< graph data structure */
836  int* countnew /**< pointer to number of new reductions (will be initially set to 0) */
837  )
838 {
839  int* hasharr;
840  const int* fixednodes = graph_getFixpseudonodes(scip, g);
841  const int nedges = graph_get_nEdges(g);
843  const int nfixednodes = graph_getNfixpseudonodes(g);
844 
845  *countnew = 0;
846 
847  assert(scip && g && g->pseudoancestors);
848 
849  if( nfixednodes == 0 )
850  return SCIP_OKAY;
851 
852  if( g->is_packed )
853  return SCIP_OKAY;
854 
855  assert(fixednodes);
856 
857  SCIP_CALL( SCIPallocCleanBufferArray(scip, &hasharr, arrsize) );
858 
859  /* hash fixed nodes */
860  for( int k = 0; k < nfixednodes; k++ )
861  {
862  const int node = fixednodes[k];
863  assert(node >= 0 && node < arrsize);
864  assert(hasharr[node] == 0 );
865 
866  hasharr[node] = 1;
867  }
868 
869  for( int e = 0; e < nedges; e += 2 )
870  {
871  if( edgestate && edgestate[e] == EDGE_BLOCKED )
872  continue;
873 
874  if( g->oeat[e] != EAT_FREE )
875  {
876  const int* pseudoancestors = graph_edge_getPseudoAncestors(g, e);
877  const int nPseudoancestors = graph_edge_nPseudoAncestors(g, e);
878 
879  assert(g->oeat[e + 1] != EAT_FREE);
880  assert(nPseudoancestors == 0 || pseudoancestors != NULL);
881 
882  for( int k = 0; k < nPseudoancestors; k++ )
883  {
884  const int ancestor = pseudoancestors[k];
885  assert(ancestor >= 0 && ancestor < arrsize);
886 
887  if( hasharr[ancestor] != 0 )
888  {
889  graph_edge_del(scip, g, e, TRUE);
890  (*countnew)++;
891 
892  SCIPdebugMessage("conflict deleted edge %d \n", e);
893  break;
894  }
895  }
896  }
897  }
898 
899  /* unhash fixed nodes */
900  for( int k = 0; k < nfixednodes; k++ )
901  {
902  const int node = fixednodes[k];
903  assert(hasharr[node] == 1 );
904 
905  hasharr[node] = 0;
906  }
907 
908  SCIPfreeCleanBufferArray(scip, &hasharr);
909 
910 
911  return SCIP_OKAY;
912 }
913 
914 
915 /** root proximity terminal test (SAP) */
917  SCIP* scip, /**< SCIP data structure */
918  GRAPH* g, /**< graph data structure */
919  SCIP_Real* fixed, /**< pointer to offset value */
920  int* count /**< pointer to number of reductions */
921  )
922 {
923  STP_Bool* nodes_isForbidden;
924  SCIP_Real* dijkdist;
925  const int nnodes = graph_get_nNodes(g);
926  int* dijkedge;
927 
928  assert(scip != NULL);
929  assert(g != NULL);
930  assert(fixed != NULL);
931  assert(count != NULL);
932  assert(!graph_typeIsUndirected(g));
933  assert(g->stp_type != STP_NWPTSPG || !graph_knotIsNWLeaf(g, g->source) || g->terms == 1);
934 
935  *count = 0;
936 
937  SCIP_CALL( SCIPallocBufferArray(scip, &nodes_isForbidden, nnodes) );
938  SCIP_CALL( SCIPallocBufferArray(scip, &dijkdist, nnodes) );
939  SCIP_CALL( SCIPallocBufferArray(scip, &dijkedge, nnodes) );
940 
941  graph_path_execX(scip, g, g->source, g->cost, dijkdist, dijkedge);
942 
943  for( int i = 0; i < nnodes; i++ )
944  nodes_isForbidden[i] = FALSE;
945 
946  for( int i = 0; i < nnodes; i++ )
947  {
948  if( Is_term(g->term[i]) && i != g->source && g->grad[i] > 0 && !nodes_isForbidden[i] )
949  {
950  int e;
951  const int e1 = dijkedge[i];
952  const SCIP_Real pathcost = dijkdist[i];
953 
954  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
955  {
956  if( e == e1 )
957  continue;
958 
959  if( GT(pathcost, g->cost[e]) )
960  break;
961  }
962 
963  if( e == EAT_LAST )
964  {
965  const int i1 = g->tail[e1];
966  const int old = g->grad[i] + g->grad[i1] - 1;
967 
968  *fixed += g->cost[e1];
969 
970  assert(g->grad[i1] > 0);
971 
972  for( int e2 = g->outbeg[i]; e2 != EAT_LAST; e2 = g->oeat[e2] )
973  nodes_isForbidden[g->head[e2]] = TRUE;
974 
975 #ifdef SCIP_DEBUG
976  SCIPdebugMessage("contracting (a) -> (b) with (a) root-dist=%f \n", pathcost);
977  graph_edge_printInfo(g, e1);
978  graph_knot_printInfo(g, i);
979  graph_knot_printInfo(g, i1);
980 #endif
981 
982  SCIP_CALL( graph_knot_contractFixed(scip, g, NULL, e1, i1, i) );
983 
984  *count += old - g->grad[i1];
985  SCIPdebugMessage("contract degree=%d\n", old - g->grad[i] - g->grad[i1]);
986  assert(old - g->grad[i1] > 0);
987  }
988 
989  }
990  }
991 
992  SCIPfreeBufferArray(scip, &dijkedge);
993  SCIPfreeBufferArray(scip, &dijkdist);
994  SCIPfreeBufferArray(scip, &nodes_isForbidden);
995 
996  return SCIP_OKAY;
997 }
998 
999 
1000 /** try to remove cute edge and prune one side of the graph */
1002  SCIP* scip, /**< SCIP data structure */
1003  int cutedge, /**< the edge */
1004  GRAPH* g, /**< graph data structure */
1005  SCIP_Bool* success /**< could we prune the edge? */
1006 )
1007 {
1008  SCIP_Bool* RESTRICT nodes_visited;
1009  const int nnodes = graph_get_nNodes(g);
1010  SCIP_Bool terminalFound;
1011  const int tail = g->tail[cutedge];
1012  const int head = g->head[cutedge];
1013 
1014  assert(scip && success);
1015  assert(graph_edge_isInRange(g, cutedge));
1016 
1017  SCIP_CALL( SCIPallocBufferArray(scip, &nodes_visited, nnodes) );
1018 
1019  for( int i = 0; i < nnodes; i++ )
1020  nodes_visited[i] = FALSE;
1021 
1022  *success = FALSE;
1023 
1024  /* first side */
1025  SCIP_CALL( cutEdgeProbe(scip, g, tail, head, nodes_visited, &terminalFound) );
1026  if( !terminalFound )
1027  {
1028  SCIP_CALL( cutEdgePrune(scip, tail, head, cutedge, g) );
1029  assert(g->grad[tail] == 0 || Is_term(g->term[tail]));
1030  *success = TRUE;
1031  }
1032 
1033  /* try second side? */
1034  if( !(*success) )
1035  {
1036  SCIP_CALL( cutEdgeProbe(scip, g, head, tail, nodes_visited, &terminalFound) );
1037  if( !terminalFound )
1038  {
1039  SCIP_CALL( cutEdgePrune(scip, head, tail, cutedge, g) );
1040  assert(g->grad[head] == 0 || Is_term(g->term[head]));
1041  *success = TRUE;
1042  }
1043  }
1044 
1045  SCIPfreeBufferArray(scip, &nodes_visited);
1046 
1047  return SCIP_OKAY;
1048 }
1049 
1050 
1051 /** identify non-leaf terminals and remove extensions */
1053  SCIP* scip, /**< SCIP data structure */
1054  GRAPH* g /**< graph data structure */
1055 )
1056 {
1057  const int nnodes = graph_get_nNodes(g);
1058 
1059  assert(scip && g);
1060  assert(graph_pc_isPc(g));
1061  assert(!g->extended);
1062  assert(g->prize && g->term2edge);
1063  assert(graph_valid(scip, g));
1064  assert(graph_pc_term2edgeIsConsistent(scip, g));
1065 
1066  /* make sure to not delete the last terminal connected to the root */
1067  if( g->stp_type == STP_PCSPG && g->grad[g->source] <= 2 )
1068  {
1069  return;
1070  }
1071 
1072  for( int k = 0; k < nnodes; ++k )
1073  {
1074  if( Is_term(g->term[k]) && !graph_pc_knotIsFixedTerm(g, k) && !graph_pc_termIsNonLeafTerm(g, k) )
1075  {
1076  assert(SCIPisGE(scip, g->prize[k], 0.0));
1077  assert(k != g->source);
1078 
1079  if( graph_pc_evalTermIsNonLeaf(scip, g, k) )
1080  {
1081  SCIPdebugMessage("transform term %d to non-leaf term \n", k);
1082 
1083  graph_pc_termToNonLeafTerm(scip, g, k, FALSE);
1084 
1085  assert(Is_term(g->term[k]));
1086  assert(graph_pc_knotIsNonLeafTerm(g, k));
1087  }
1088  }
1089  }
1090 
1091  assert(graph_pc_term2edgeIsConsistent(scip, g));
1092 }
1093 
1094 
1095 
1096 /* remove unconnected vertices */
1098  SCIP* scip, /**< SCIP data structure */
1099  GRAPH* g /**< graph data structure */
1100 )
1101 {
1102  const int nnodes = g->knots;
1103  SCIP_Bool* nodevisited;
1104 
1105  assert(scip && g);
1106 
1107  SCIP_CALL( SCIPallocBufferArray(scip, &nodevisited, nnodes) );
1108 
1109  SCIP_CALL( graph_trail_arr(scip, g, g->source, nodevisited) );
1110 
1111  for( int k = nnodes - 1; k >= 0 ; k-- )
1112  {
1113  if( !nodevisited[k] && (g->grad[k] > 0) )
1114  {
1115  if( Is_term(g->term[k]) )
1116  {
1117  assert(graph_pc_isPc(g));
1118  assert(graph_pc_termIsNonLeafTerm(g, k));
1119 
1120  continue;
1121  }
1122 
1123  graph_knot_del(scip, g, k, TRUE);
1124  }
1125  }
1126 
1127  SCIPfreeBufferArray(scip, &nodevisited);
1128 
1129  return SCIP_OKAY;
1130 }
1131 
1132 
1133 /* remove unconnected vertices for directed problems */
1135  SCIP* scip, /**< SCIP data structure */
1136  GRAPH* g /**< graph data structure */
1137 )
1138 {
1139  const int nnodes = graph_get_nNodes(g);
1140  SCIP_Bool* nodevisited;
1141 
1142  assert(scip && g);
1143  assert(!graph_typeIsUndirected(g));
1144 
1145  SCIP_CALL( SCIPallocBufferArray(scip, &nodevisited, nnodes) );
1146  SCIP_CALL( graph_trail_costAware(scip, g, g->source, nodevisited) );
1147 
1148  for( int k = 0; k < nnodes; k++ )
1149  {
1150  if( !nodevisited[k] && (g->grad[k] > 0) )
1151  {
1152  assert(!Is_term(g->term[k]));
1153  graph_knot_del(scip, g, k, TRUE);
1154  }
1155  }
1156 
1157  SCIPfreeBufferArray(scip, &nodevisited);
1158 
1159  return SCIP_OKAY;
1160 }
1161 
1162 
1163 /** remove unconnected vertices and checks whether problem is infeasible */
1165  SCIP* scip, /**< SCIP data structure */
1166  SCIP_Bool beVerbose, /**< be verbose? */
1167  GRAPH* g, /**< graph data structure */
1168  SCIP_Bool* infeas /**< is problem infeasible? */
1169 )
1170 {
1171  const int nnodes = graph_get_nNodes(g);
1172  SCIP_Bool* nodevisited;
1173 
1174  assert(scip && g && infeas);
1175 
1176  SCIP_CALL( SCIPallocBufferArray(scip, &nodevisited, nnodes) );
1177 
1178  *infeas = FALSE;
1179 
1180  SCIP_CALL( graph_trail_arr(scip, g, g->source, nodevisited) );
1181 
1182  for( int k = 0; k < nnodes; k++ )
1183  if( !nodevisited[k] && Is_term(g->term[k]) )
1184  {
1185  assert(k != g->source);
1186  *infeas = TRUE;
1187  if( beVerbose )
1188  {
1189  printf("terminal node %d (original index %d) lies in separate connected component \n", k, k + 1);
1190  }
1191 
1192  break;
1193  }
1194 
1195  for( int k = 0; k < nnodes; k++ )
1196  {
1197  if( !nodevisited[k] && (g->grad[k] > 0) )
1198  {
1199  while( g->inpbeg[k] != EAT_LAST )
1200  graph_edge_del(scip, g, g->inpbeg[k], TRUE);
1201  }
1202  }
1203 
1204  SCIPfreeBufferArray(scip, &nodevisited);
1205 
1206  return SCIP_OKAY;
1207 }
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
int graph_edge_nPseudoAncestors(const GRAPH *, int)
SCIP_RETCODE reduce_simple(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *solnode, int *nelims, int *edgestate)
SCIP_RETCODE reduce_fixedConflicts(SCIP *scip, const int *edgestate, GRAPH *g, int *countnew)
int *RESTRICT head
Definition: graphdefs.h:224
void reduce_nodesDeg1(SCIP *scip, GRAPH *graph)
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
SCIP_RETCODE graph_knot_contractFixed(SCIP *, GRAPH *, int *, int, int, int)
Definition: graph_node.c:521
int source
Definition: graphdefs.h:195
SCIP_RETCODE graph_fixed_addEdge(SCIP *, int, GRAPH *)
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
int terms
Definition: graphdefs.h:192
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPqueueInsert(SCIP_QUEUE *queue, void *elem)
Definition: misc.c:1020
int graph_pseudoAncestorsGetHashArraySize(const PSEUDOANS *)
int *RESTRICT maxdeg
Definition: graphdefs.h:206
SCIP_Bool graph_pc_term2edgeIsConsistent(SCIP *, const GRAPH *)
Definition: graph_pcbase.c:874
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
#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
#define STP_DCSTP
Definition: graphdefs.h:47
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
SCIP_RETCODE reduce_unconnectedInfeas(SCIP *scip, SCIP_Bool beVerbose, GRAPH *g, SCIP_Bool *infeas)
#define FARAWAY
Definition: graphdefs.h:89
void graph_pc_termToNonLeafTerm(SCIP *, GRAPH *, int, SCIP_Bool)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_Bool SCIPqueueIsEmpty(SCIP_QUEUE *queue)
Definition: misc.c:1175
static SCIP_RETCODE cutEdgePrune(SCIP *scip, int start, int end, int cutedge, GRAPH *g)
Definition: reduce_simple.c:61
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
void reduce_identifyNonLeafTerms(SCIP *scip, GRAPH *g)
SCIP_Bool graph_knotIsNWLeaf(const GRAPH *, int)
Definition: graph_node.c:35
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
SCIP_RETCODE reduce_rpt(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_RETCODE reduce_unconnected(SCIP *scip, GRAPH *g)
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
int graph_getNfixpseudonodes(const GRAPH *)
IDX ** ancestors
Definition: graphdefs.h:234
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
PSEUDOANS * pseudoancestors
Definition: graphdefs.h:236
SCIP_Real * prize
Definition: graphdefs.h:210
int *RESTRICT grad
Definition: graphdefs.h:201
SCIP_RETCODE graph_knot_contractLowdeg2High(SCIP *, GRAPH *, int *, int, int)
Definition: graph_node.c:539
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_DHCSTP
Definition: graphdefs.h:52
#define Edge_anti(a)
Definition: graphdefs.h:106
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
int * term2edge
Definition: graphdefs.h:208
IDX ** pcancestors
Definition: graphdefs.h:235
#define STP_PCSPG
Definition: graphdefs.h:44
#define LT(a, b)
Definition: portab.h:81
void SCIPqueueFree(SCIP_QUEUE **queue)
Definition: misc.c:958
unsigned char STP_Bool
Definition: portab.h:34
SCIP_RETCODE reduce_cutEdgeTryPrune(SCIP *scip, int cutedge, GRAPH *g, SCIP_Bool *success)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
#define STP_NWPTSPG
Definition: graphdefs.h:48
SCIP_RETCODE reduce_contract0Edges(SCIP *scip, GRAPH *g, int *solnode, SCIP_Bool savehistory)
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
const int * graph_edge_getPseudoAncestors(const GRAPH *, int)
int *RESTRICT term
Definition: graphdefs.h:196
void graph_edge_printInfo(const GRAPH *, int)
Definition: graph_stats.c:133
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
#define EDGE_BLOCKED
Definition: graphdefs.h:95
SCIP_RETCODE graph_trail_costAware(SCIP *, const GRAPH *, int, SCIP_Bool *)
Definition: graph_util.c:353
SCIP_Bool graph_pc_isPc(const GRAPH *)
Portable definitions.
SCIP_Bool graph_typeIsUndirected(const GRAPH *)
Definition: graph_stats.c:69
SCIP_RETCODE graph_trail_arr(SCIP *, const GRAPH *, int, SCIP_Bool *)
Definition: graph_util.c:336
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:125
SCIP_RETCODE reduce_deleteMultiedges(SCIP *scip, GRAPH *g)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition: misc.c:934
SCIP_RETCODE reduce_simple_sap(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
static SCIP_RETCODE cutEdgeProbe(SCIP *scip, const GRAPH *g, int start, int end, SCIP_Bool *RESTRICT nodes_visited, SCIP_Bool *terminalFound)
Definition: reduce_simple.c:99
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
#define SCIP_Real
Definition: def.h:177
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:137
SCIP_RETCODE reduce_simple_hc(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
int *RESTRICT outbeg
Definition: graphdefs.h:204
void reduce_simple_dc(SCIP *scip, GRAPH *g)
const int * graph_getFixpseudonodes(SCIP *, const GRAPH *)
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
SCIP_RETCODE reduce_unconnectedForDirected(SCIP *scip, GRAPH *g)
void * SCIPqueueRemove(SCIP_QUEUE *queue)
Definition: misc.c:1071
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
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_Bool graph_pc_evalTermIsNonLeaf(SCIP *, const GRAPH *, int)
SCIP_Bool is_packed
Definition: graphdefs.h:265
includes various reduction methods for Steiner tree problems
SCIP callable library.
IDX * graph_edge_getAncestors(const GRAPH *, int)