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-2015 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file dirreduce.c
17  * @brief several basic reductions for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements basic redution 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 
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <assert.h>
33 #include "grph.h"
34 #include "portab.h"
35 #include "scip/scip.h"
36 
37 
38 /** is there no vertex of higher prize? */
39 static
40 SCIP_Bool maxprize(
41  SCIP* scip, /**< SCIP data structure */
42  GRAPH* g, /**< graph data structure */
43  int i /**< the terminal to be checked */
44  )
45 {
46  int k;
47  int t = -1;
48  SCIP_Real max = -1.0;
49 
50  for( k = 0; k < g->knots; k++ )
51  {
52  if( Is_term(g->term[k]) && g->mark[k] && g->grad[k] > 0 )
53  {
54  assert(k != g->source[0]);
55  if( SCIPisGT(scip, g->prize[k], max) )
56  {
57  max = g->prize[k];
58  t = k;
59  }
60  else if( t == i && SCIPisGE(scip, g->prize[k], max) )
61  {
62  t = k;
63  }
64  }
65  }
66 
67  SCIPdebugMessage("maxprize: %f (from %d) \n", g->prize[t], t );
68  return (t == i);
69 }
70 
71 /** try to eliminate a terminal of degree one */
72 static
73 SCIP_RETCODE trydg1edgepc(
74  SCIP* scip, /**< SCIP data structure */
75  GRAPH* g, /**< graph data structure */
76  SCIP_Real* offset, /**< pointer to store the offset */
77  int* count, /**< pointer storing number of eliminated edges */
78  int i, /**< the terminal to be checked */
79  int iout, /**< outgoing arc */
80  SCIP_Bool* rerun /**< further eliminations possible? */
81  )
82 {
83  int i1;
84  int degsum;
85 
86  assert(scip != NULL);
87  assert(g != NULL);
88  assert(count != NULL);
89  assert(Is_term(g->term[i]));
90 
91  if( maxprize(scip, g, i) )
92  return SCIP_OKAY;
93 
94  i1 = g->head[iout];
95 
96  if( SCIPisLE(scip, g->prize[i], g->cost[iout]) && g->stp_type != STP_MAX_NODE_WEIGHT )
97  {
98  /* delete terminal */
99 
100  if( (i1 < i) && (Is_term(g->term[i1]) || g->grad[i1] == 2 || g->grad[i1] == 3) )
101  (*rerun) = TRUE;
102  SCIPdebugMessage("Delete (degree 1) terminal %d \n", i);
103  (*offset) += g->prize[i];
104  *count += deleteterm(scip, g, i);
105  }
106  else
107  {
108  /* contract terminal */
109 
110  (*rerun) = TRUE;
111  assert(SCIPisGT(scip, g->prize[i], 0.0 ));
112 
113  if( g->stp_type == STP_MAX_NODE_WEIGHT )
114  {
115  if( SCIPisLT(scip, g->prize[i], -g->prize[i1]) )
116  *offset += g->prize[i];
117  else
118  *offset -= g->prize[i1];
119  }
120  else
121  {
122  *offset += g->cost[iout];
123  }
124 
125  if( g->source[0] == i1 )
126  {
127  if( g->pcancestors[i] != NULL )
128  {
129  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->pcancestors[i1]), g->pcancestors[i]) );
130  SCIPintListNodeFree(scip, &(g->pcancestors[i]));
131  }
132  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->pcancestors[i1]), g->ancestors[iout]) );
133  *count += deleteterm(scip, g, i);
134  return SCIP_OKAY;
135  }
136 
137  degsum = g->grad[i] + g->grad[i1];
138 
139  SCIP_CALL( graph_knot_contractpc(scip, g, i, i1, i) );
140 
141  degsum -= g->grad[i];
142 
143  assert(degsum >= 1);
144 
145  if( g->stp_type == STP_MAX_NODE_WEIGHT )
146  {
147  int e;
148  int t = UNKNOWN;
149  int e2 = UNKNOWN;
150 
151  if( SCIPisLT(scip, g->prize[i], 0.0 ) )
152  {
153  i1 = UNKNOWN;
154  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
155  {
156  i1 = g->head[e];
157  if( Is_pterm(g->term[i1]) && g->source[0] != i1 )
158  t = i1;
159  else if( g->source[0] == i1 )
160  e2 = e;
161  }
162 
163  assert(t != UNKNOWN);
164  assert(e2 != UNKNOWN);
165 
166  /* delete artifical terminal */
167  graph_knot_chg(g, t, -1);
168  while( g->outbeg[t] != EAT_LAST )
169  {
170  e = g->outbeg[t];
171  g->cost[e] = 0.0;
172  g->cost[flipedge(e)] = 0.0;
173  graph_edge_del(scip, g, e, TRUE);
174  count++;
175  }
176 
177  assert(g->grad[t] == 0);
178 
179  /* i is not a terminal anymore */
180  graph_knot_chg(g, i, -1);
181  graph_edge_del(scip, g, e2, TRUE);
182 
183  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
184  if( g->mark[g->tail[e]] )
185  g->cost[e] = -g->prize[i];
186 
187  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
188  {
189  i1 = g->head[e];
190  if( g->mark[i1] )
191  {
192  if( !Is_term(g->term[i1]) )
193  {
194  g->cost[e] = -g->prize[i1];
195  }
196  else
197  {
198  g->cost[e] = 0.0;
199  }
200  }
201  }
202  }
203  else
204  {
205  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
206  if( g->mark[g->tail[e]] )
207  g->cost[e] = 0.0;
208 
209  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
210  {
211  i1 = g->head[e];
212  if( g->mark[i1] )
213  {
214  if( !Is_term(g->term[i1]) )
215  {
216  assert(SCIPisLE(scip, g->prize[i1], 0.0 ));
217  g->cost[e] = -g->prize[i1];
218  }
219  else
220  {
221  assert(SCIPisGE(scip, g->prize[i1], 0.0 ));
222  g->cost[e] = 0.0;
223  }
224  }
225  else if( Is_pterm(g->term[i1]) && g->source[0] != i1 )
226  {
227  t = i1;
228  }
229 
230  }
231  assert(t != UNKNOWN);
232 
233  for( e = g->inpbeg[t]; e != EAT_LAST; e = g->ieat[e] )
234  if( g->tail[e] == g->source[0] )
235  break;
236  assert(e != EAT_LAST);
237  g->cost[e] = g->prize[i];
238  }
239  }
240  *count += degsum;
241  }
242  return SCIP_OKAY;
243 }
244 
245 
246 /** traverse one side of a chain (MWCSP) */
247 static
248 SCIP_RETCODE traverseChain(
249  SCIP* scip, /**< SCIP data structure */
250  GRAPH* g, /**< graph data structure */
251  int* length, /**< pointer to store length of chain */
252  int* final, /**< pointer to store final vertex */
253  int i, /**< start vertex */
254  int i1, /**< first vertex */
255  int i2, /**< last vertex */
256  int e1 /**< first edge */
257  )
258 {
259  IDX* ancestors = NULL;
260  IDX* revancestors = NULL;
261  SCIP_Real sum;
262  int k;
263  int e;
264 
265  assert(g != NULL);
266  assert(scip != NULL);
267  assert(length != NULL);
268 
269  k = i1;
270  e = e1;
271  sum = 0.0;
272 
273  while( g->grad[k] == 2 && !Is_term(g->term[k]) && k != i2 )
274  {
275  assert(g->mark[k]);
276 
277  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e]) );
278  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[flipedge(e)]) );
279 
280  if( e != e1 )
281  graph_edge_del(scip, g, e, TRUE);
282 
283  e = g->outbeg[k];
284  sum += g->prize[k];
285  (*length)++;
286 
287  if( e == flipedge(e1) )
288  e = g->oeat[e];
289 
290  assert(e != EAT_LAST);
291  assert(SCIPisLE(scip, g->prize[k], 0.0));
292 
293  k = g->head[e];
294  }
295  if( k != i1 )
296  {
297  int ne;
298 
299  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e]) );
300  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[flipedge(e)]) );
301 
302  graph_edge_del(scip, g, e, TRUE);
303 
304  g->prize[i] += sum;
305  ne = graph_edge_redirect(scip, g, e1, i, k, 1.0);
306 
307  if( ne != -1 )
308  {
309  e1 = ne;
310 
311  SCIPintListNodeFree(scip, &(g->ancestors[e1]));
312  SCIPintListNodeFree(scip, &(g->ancestors[flipedge(e1)]));
313 
314  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[e1]), ancestors) );
315  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(e1)]), revancestors) );
316 
317  }
318  else
319  {
320  for( e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
321  if( g->head[e1] == k )
322  break;
323  assert(e1 != EAT_LAST);
324  }
325 
326  SCIPintListNodeFree(scip, &(ancestors));
327  SCIPintListNodeFree(scip, &(revancestors));
328 
329  if( SCIPisGE(scip, g->prize[k], 0.0) )
330  g->cost[e1] = 0.0;
331  else
332  g->cost[e1] = -g->prize[k];
333  assert(SCIPisLE(scip, g->prize[i], 0.0) );
334  }
335 
336  *final = k;
337 
338  return SCIP_OKAY;
339 }
340 
341 
342 /** delete a terminal for a (rooted) prize-collecting problem */
343 int deleteterm(
344  SCIP* scip, /**< SCIP data structure */
345  GRAPH* g, /**< graph data structure */
346  int i /**< index of the terminal */
347  )
348 {
349  int e;
350  int t;
351  int i1;
352  int count;
353 
354  assert(g != NULL);
355  assert(scip != NULL);
356  assert(Is_term(g->term[i]));
357 
358  t = UNKNOWN;
359  count = g->grad[i] + 2;
360 
361  /* delete terminal */
362 
363  graph_knot_chg(g, i, -1);
364  g->mark[i] = FALSE;
365 
366  while( (e = g->outbeg[i]) != EAT_LAST )
367  {
368  i1 = g->head[e];
369 
370  if( Is_pterm(g->term[i1]) && g->source[0] != i1 )
371  t = g->head[e];
372  graph_edge_del(scip, g, e, TRUE);
373  }
374 
375  assert(t != UNKNOWN);
376 
377  /* delete artifical terminal */
378 
379  graph_knot_chg(g, t, -1);
380 
381  while( g->outbeg[t] != EAT_LAST )
382  graph_edge_del(scip, g, g->outbeg[t], TRUE);
383 
384 
385  return count;
386 }
387 
388 
389 /** basic reduction tests for the STP */
390 SCIP_RETCODE degree_test(
391  SCIP* scip, /**< SCIP data structure */
392  GRAPH* g, /**< graph data structure */
393  SCIP_Real* fixed, /**< pointer to offfset value */
394  int* nelims /**< pointer to number of reductions */
395  )
396 {
397  int i;
398  int i1;
399  int i2;
400  int e1;
401  int e2;
402  int nnodes;
403  int rerun = TRUE;
404  int done = TRUE;
405  int count = 0;
406 
407  assert(g != NULL);
408  assert(fixed != NULL);
409  assert(nelims != NULL);
410 
411  nnodes = g->knots;
412 
413  SCIPdebugMessage("Degree Test: ");
414 
415  /* main loop */
416  while( rerun )
417  {
418  rerun = FALSE;
419 
420  for( i = 0; i < nnodes; i++ )
421  {
422  assert(g->grad[i] >= 0);
423 
424  if( g->grad[i] == 1 )
425  {
426  e1 = g->outbeg[i];
427  i1 = g->head[e1];
428 
429  assert(e1 >= 0);
430  assert(e1 == Edge_anti(g->inpbeg[i]));
431  assert(g->oeat[e1] == EAT_LAST);
432  assert(g->ieat[g->inpbeg[i]] == EAT_LAST);
433 
434  if( Is_term(g->term[i]) )
435  {
436  *fixed += g->cost[e1];
437  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1]) );
438  }
439 
440  SCIP_CALL( graph_knot_contract(scip, g, i1, i) );
441  count++;
442 
443  assert(g->grad[i] == 0);
444 
445  /* the last node in the graph? */
446  if( g->grad[i1] == 0 )
447  {
448  rerun = FALSE;
449  break;
450  }
451  if( (i1 < i) && (g->grad[i1] < 3) )
452  rerun = TRUE;
453 
454  continue;
455  }
456  if( g->grad[i] == 2 )
457  {
458  e1 = g->outbeg[i];
459  e2 = g->oeat[e1];
460  i1 = g->head[e1];
461  i2 = g->head[e2];
462 
463  assert(e1 >= 0);
464  assert(e2 >= 0);
465 
466  do
467  {
468  done = TRUE;
469 
470  if( !Is_term(g->term[i]) )
471  {
472  assert(EQ(g->cost[e2], g->cost[Edge_anti(e2)]));
473 
474  g->cost[e1] += g->cost[e2];
475  g->cost[Edge_anti(e1)] += g->cost[e2];
476  SCIP_CALL( graph_knot_contract(scip, g, i2, i) );
477  count++;
478 
479  break;
480  }
481  assert(Is_term(g->term[i]));
482 
483  if( Is_term(g->term[i1]) && Is_term(g->term[i2]) )
484  {
485 
486  if( SCIPisLT(scip, g->cost[e1], g->cost[e2]) )
487  {
488  *fixed += g->cost[e1];
489  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1]) );
490  SCIP_CALL( graph_knot_contract(scip, g, i1, i) );
491  }
492  else
493  {
494  *fixed += g->cost[e2];
495  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e2]) );
496  SCIP_CALL( graph_knot_contract(scip, g, i2, i) );
497  }
498  count++;
499 
500  break;
501  }
502  if( Is_term(g->term[i1]) && !Is_term(g->term[i2]) && SCIPisLE(scip, g->cost[e1], g->cost[e2]) )
503  {
504  *fixed += g->cost[e1];
505  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1]) );
506  SCIP_CALL( graph_knot_contract(scip, g, i1, i) );
507  count++;
508  break;
509  }
510  if( Is_term(g->term[i2]) && !Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e2], g->cost[e1]) )
511  {
512  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e2]) );
513  *fixed += g->cost[e2];
514  SCIP_CALL( graph_knot_contract(scip, g, i2, i) );
515  count++;
516  break;
517  }
518  done = FALSE;
519  }
520  while( FALSE );
521 
522  if (done
523  && (((i1 < i) && (g->grad[i1] < 3))
524  || ((i2 < i) && (g->grad[i2] < 3))))
525  rerun = TRUE;
526  }
527  if( Is_term(g->term[i]) && g->grad[i] > 2 )
528  {
529  SCIP_Real mincost = FARAWAY;
530  int ett = UNKNOWN;
531  for( e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
532  {
533  i1 = g->head[e1];
534 
535  if( SCIPisLT(scip, g->cost[e1], mincost) )
536  {
537  mincost = g->cost[e1];
538  if( Is_term(g->term[i1]) )
539  ett = e1;
540  }
541  else if( Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e1], mincost) )
542  {
543  ett = e1;
544  }
545  }
546  if( ett != UNKNOWN && SCIPisLE(scip, g->cost[ett], mincost) )
547  {
548  *fixed += g->cost[ett];
549  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[ett]) );
550  SCIP_CALL( graph_knot_contract(scip, g, i, g->head[ett]) );
551  rerun = TRUE;
552  }
553  }
554  }
555  }
556  SCIPdebugMessage(" %d Knots deleted\n", count);
557  assert(graph_valid(g));
558 
559  *nelims += count;
560  return SCIP_OKAY;
561 }
562 
563 
564 
565 /** basic reduction tests for the SAP */
566 SCIP_RETCODE degree_test_sap(
567  SCIP* scip, /**< SCIP data structure */
568  GRAPH* g, /**< graph data structure */
569  SCIP_Real* fixed, /**< pointer to offfset value */
570  int* count /**< pointer to number of reductions */
571  )
572 {
573  SCIP_QUEUE* queue;
574  int i;
575  int e;
576  int i1;
577  int i2;
578  int e1;
579  int e2;
580  int root;
581  int nnodes;
582  int* pnode;
583  char rerun;
584 
585  assert(g != NULL);
586  assert(fixed != NULL);
587  assert(count != NULL);
588 
589  root = g->source[0];
590  rerun = TRUE;
591  nnodes = g->knots;
592 
593  *count = 0;
594  SCIPdebugMessage("Degree Test: ");
595 
596  /* main loop */
597  while( rerun )
598  {
599  rerun = FALSE;
600 
601  for( i = 0; i < nnodes; i++ )
602  {
603  assert(g->grad[i] >= 0);
604 
605  if( g->grad[i] == 1 )
606  {
607  e1 = g->inpbeg[i];
608  i1 = g->tail[e1];
609 
610  assert(e1 >= 0);
611  assert(e1 == Edge_anti(g->outbeg[i]));
612  assert(g->ieat[e1] == EAT_LAST);
613  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
614 
615  if( Is_term(g->term[i]) )
616  {
617  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1]) );
618  *fixed += g->cost[e1];
619  SCIP_CALL( graph_knot_contract(scip, g, i1, i) );
620  }
621  else
622  {
623  graph_edge_del(scip, g, e1, TRUE);
624  }
625 
626  assert(g->grad[i] == 0);
627 
628  if ((i1 < i) && (g->grad[i1] < 3))
629  rerun = TRUE;
630 
631  (*count)++;
632 
633  continue;
634  }
635 
636  if( g->grad[i] == 2 )
637  {
638  e1 = g->outbeg[i];
639  e2 = g->oeat[e1];
640  i1 = g->head[e1];
641  i2 = g->head[e2];
642 
643  assert(e1 >= 0);
644  assert(e2 >= 0);
645 
646  if( !Is_term(g->term[i]) )
647  {
648  if( (!Is_term(g->term[i2]) && !Is_term(g->term[i1])) )
649  {
650  g->cost[e1] += g->cost[Edge_anti(e2)];
651  g->cost[Edge_anti(e1)] += g->cost[e2];
652  if( SCIPisGT(scip, g->cost[e1], FARAWAY) )
653  g->cost[e1] = FARAWAY;
654  if( SCIPisGT(scip, g->cost[Edge_anti(e1)], FARAWAY) )
655  g->cost[Edge_anti(e1)] = FARAWAY;
656  SCIP_CALL( graph_knot_contract(scip, g, i2, i) );
657  (*count)++;
658  if( ((i1 < i) && (g->grad[i1] < 3))
659  || ((i2 < i) && (g->grad[i2] < 3)) )
660  rerun = TRUE;
661  }
662  }
663  /* CONSTCOND */
664  /*lint -save -e717 */
665  /*lint -restore */
666  }
667  }
668  }
669 
670  /* delete all arcs in \delta^-(root) */
671  for( e = g->inpbeg[root]; e != EAT_LAST; e = g->ieat[e] )
672  g->cost[e] = FARAWAY;
673 
674  /* delete all arcs in not connected to a terminal other than the root by forward arcs */
675 
676  /* BFS until all terminals are reached */
677  SCIP_CALL( SCIPqueueCreate(&queue, nnodes, 2.0) );
678 
679  for( i = 0; i < nnodes; i++ )
680  {
681  if( Is_term(g->term[i]) && i != root )
682  {
683  g->mark[i] = TRUE;
684  SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[g->outbeg[i]])) );
685  }
686  else
687  {
688  g->mark[i] = FALSE;
689  }
690  }
691 
692  g->mark[root] = TRUE;
693 
694  while( !SCIPqueueIsEmpty(queue) )
695  {
696  pnode = (SCIPqueueRemove(queue));
697  for( e = g->inpbeg[*pnode]; e != EAT_LAST; e = g->ieat[e] )
698  {
699  if( !g->mark[g->tail[e]] )
700  {
701  g->mark[g->tail[e]] = TRUE;
702  SCIP_CALL( SCIPqueueInsert(queue, &(g->tail[e])) );
703  }
704  }
705  }
706 
707  SCIPqueueFree(&queue);
708 
709  for( i = 0; i < nnodes; i++ )
710  {
711  if( !g->mark[i] )
712  {
713  while( g->inpbeg[i] != EAT_LAST )
714  {
715  SCIPdebugMessage("remove edge to node %d \n", i);
716  graph_edge_del(scip, g, g->inpbeg[i], TRUE);
717  }
718  }
719 #if 0
720  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
721  {
722  if( SCIPisGE(scip, g->cost[e], FARAWAY) && SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
723  {
724  printf("remove high cost edge to node %d \n", i);
725  graph_edge_del(scip, g, e, TRUE);
726  }
727  }
728 #endif
729  }
730 
731  SCIPdebugMessage("dirdeg %d Knots deleted\n", *count);
732  assert(graph_valid(g));
733 
734  return SCIP_OKAY;
735 }
736 
737 
738 /** root proximity terminal test (SAP) */
739 SCIP_RETCODE rptReduction(
740  SCIP* scip, /**< SCIP data structure */
741  GRAPH* g, /**< graph data structure */
742  SCIP_Real* fixed, /**< pointer to offset value */
743  int* count /**< pointer to number of reductions */
744  )
745 {
746  SCIP_Real pathcost;
747  SCIP_Real* dijkdist;
748  int i;
749  int e;
750  int i1;
751  int e1;
752  int old;
753  int root;
754  int nnodes;
755  int* dijkedge;
756 
757  assert(scip != NULL);
758  assert(g != NULL);
759  assert(fixed != NULL);
760  assert(count != NULL);
761 
762  root = g->source[0];
763  nnodes = g->knots;
764  *count = 0;
765 
766  SCIP_CALL( SCIPallocBufferArray(scip, &dijkdist, nnodes) );
767  SCIP_CALL( SCIPallocBufferArray(scip, &dijkedge, nnodes) );
768 
769  graph_path_execX(scip, g, root, g->cost, dijkdist, dijkedge);
770 
771  for( i = 0; i < nnodes; i++ )
772  {
773  if( Is_term(g->term[i]) && i != root && g->grad[i] > 0 )
774  {
775  e1 = dijkedge[i];
776  pathcost = dijkdist[i];
777 
778  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
779  {
780  if( e == e1 )
781  continue;
782 
783  if( SCIPisGT(scip, pathcost, g->cost[e]) )
784  break;
785  }
786  if( e == EAT_LAST )
787  {
788  i1 = g->tail[e1];
789  old = g->grad[i] + g->grad[i1] - 1;
790 
791  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->fixedges), g->ancestors[e1]) );
792  *fixed += g->cost[e1];
793  SCIP_CALL( graph_knot_contract(scip, g, i1, i) );
794 
795  assert(old - g->grad[i1] > 0);
796  *count += old - g->grad[i1];
797  SCIPdebugMessage("contract %d\n", old - g->grad[i] - g->grad[i1]);
798  }
799 
800  }
801  }
802 
803  SCIPfreeBufferArray(scip, &dijkedge);
804  SCIPfreeBufferArray(scip, &dijkdist);
805 
806  return SCIP_OKAY;
807 }
808 
809 
810 /** basic reduction tests for the MWCS problem */
811 SCIP_RETCODE degree_test_mw(
812  SCIP* scip, /**< SCIP data structure */
813  GRAPH* g, /**< graph data structure */
814  SCIP_Real* fixed, /**< pointer to offfset value */
815  int* count /**< pointer to number of reductions */
816  )
817 {
818  int i;
819  int e;
820  int i1;
821  int i2;
822  int e1;
823  int e2;
824  int nnodes;
825  int nedges;
826  SCIP_Bool rerun = TRUE;
827 
828  assert(g != NULL);
829  assert(fixed != NULL);
830  assert(count != NULL);
831  assert(g->stp_type == STP_MAX_NODE_WEIGHT);
832 
833  nnodes = g->knots;
834  nedges = g->edges;
835 
836  SCIPdebugMessage("MW degree test: \n");
837 
838  /* main loop */
839  while( rerun )
840  {
841  rerun = FALSE;
842 
843  /* contract adjacent positive vertices */
844  for( e = 0; e < nedges; e += 2 )
845  {
846  i1 = g->tail[e];
847  i2 = g->head[e];
848  if( g->mark[i1] && g->mark[i2] && Is_term(g->term[i1]) && Is_term(g->term[i2]) )
849  {
850  SCIPdebugMessage("contract tt %d->%d\n ", i1, i2);
851  (*count)++;
852  SCIP_CALL( graph_knot_contractpc(scip, g, i1, i2, i1) );
853  }
854  }
855 
856  /* main loop for remaining tests */
857  for( i = 0; i < nnodes; i++ )
858  {
859  assert(g->grad[i] >= 0);
860  if( !g->mark[i] || g->grad[i] == 0 )
861  continue;
862 
863  assert( !SCIPisEQ(scip, g->prize[i], 0.0) );
864 
865  /* non-positive vertex? */
866  if( !Is_term(g->term[i]) )
867  {
868  if( g->grad[i] == 1 )
869  {
870  e1 = g->inpbeg[i];
871  i1 = g->tail[e1];
872  assert(e1 >= 0);
873  assert(e1 == Edge_anti(g->outbeg[i]));
874  assert(g->ieat[e1] == EAT_LAST);
875  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
876  assert(SCIPisLE(scip, g->prize[i], 0.0));
877 
878  graph_edge_del(scip, g, e1, TRUE);
879  SCIPdebugMessage("delete negative vertex of degree 1 (%d)\n ", i);
880  assert(g->grad[i] == 0);
881 
882  if( (i1 < i) && (g->grad[i1] < 3 || (g->grad[i1] == 3 && Is_term(g->term[i1]))) )
883  rerun = TRUE;
884 
885  (*count)++;
886  continue;
887  }
888 
889  /* contract non-positive chains */
890  if( g->grad[i] == 2 )
891  {
892  int f1 = -1;
893  int f2 = -1;
894  int length = 0;
895 
896  e1 = g->outbeg[i];
897  e2 = g->oeat[e1];
898  i1 = g->head[e1];
899  i2 = g->head[e2];
900 
901  assert(e1 >= 0);
902  assert(e2 >= 0);
903  assert(i1 != i2);
904  assert(g->mark[i1]);
905  assert(g->mark[i2]);
906 
907  SCIP_CALL( traverseChain(scip, g, &length, &f1, i, i1, i2, e1) );
908  SCIP_CALL( traverseChain(scip, g, &length, &f2, i, i2, i1, e2) );
909 
910  if( f1 == f2 )
911  {
912  while( g->outbeg[i] != EAT_LAST )
913  graph_edge_del(scip, g, g->outbeg[i], TRUE);
914  }
915  else if( length > 0 )
916  {
917  assert(g->grad[i] <= 2);
918 
919  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
920  g->cost[e] = -g->prize[i];
921 
922  e1 = g->outbeg[i];
923  e2 = g->oeat[e1];
924 
925  (*count) += length;
926  }
927  }
928  continue;
929  }
930 
931  /* node i is of positive weight (terminal): */
932 
933  /* terminal of (real) degree 0? */
934  if( g->grad[i] == 2 )
935  {
936  /* if terminal node i is not the one with the highest prize, delete */
937  if( !maxprize(scip, g, i) )
938  {
939  SCIPdebugMessage("delete degree 0 term %d prize: %f count:%d\n ", i, g->prize[i], *count);
940  (*fixed) += g->prize[i];
941  (*count) += deleteterm(scip, g, i);
942  }
943  }
944  /* terminal of (real) degree 1? */
945  else if( g->grad[i] == 3 )
946  {
947  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
948  if( g->mark[g->head[e]] )
949  break;
950  assert(e != EAT_LAST);
951  assert(g->head[e] != g->source[0]);
952  if( !Is_term(g->term[g->head[e]]) )
953  {
954  SCIP_CALL( trydg1edgepc(scip, g, fixed, count, i, e, &rerun) );
955  continue;
956  }
957  }
958  }
959  }
960 
961  SCIPdebugMessage("MW basic reduction package has deleted %d edges\n", *count);
962 
963  return SCIP_OKAY;
964 }
965 
966 
967 /** basic reduction tests for the HCDSTP */
968 SCIP_RETCODE degree_test_hc(
969  SCIP* scip, /**< SCIP data structure */
970  GRAPH* g, /**< graph data structure */
971  SCIP_Real* fixed, /**< pointer to offfset value */
972  int* count /**< pointer to number of reductions */
973  )
974 {
975  int i;
976  int e;
977  int e2;
978  int root;
979  int nnodes;
980  SCIP_Bool rerun = TRUE;
981 
982  assert(g != NULL);
983  assert(fixed != NULL);
984  assert(count != NULL);
985  assert(g->stp_type == STP_HOP_CONS);
986 
987  nnodes = g->knots;
988  root = g->source[0];
989 
990  SCIPdebugMessage("basic HC test: \n");
991 
992  /* main loop */
993  while( rerun )
994  {
995  rerun = FALSE;
996 
997  /* delete incoming arcs of the root */
998  e = g->inpbeg[root];
999  while( e != EAT_LAST )
1000  {
1001  e2 = g->ieat[e];
1002 
1003  if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
1004  {
1005  SCIPdebugMessage("delete incoming root arc \n");
1006  (*count)++;
1007  graph_edge_del(scip, g, e, TRUE);
1008  }
1009  else if( SCIPisLT(scip, g->cost[e], FARAWAY) )
1010  {
1011  SCIPdebugMessage("delete anti-parallel root arcs \n");
1012  g->cost[e] = FARAWAY;
1013  }
1014 
1015  e = e2;
1016  }
1017 
1018  /* delete outgoing arcs of the terminals (other than the root) */
1019  for( i = 0; i < nnodes; i++ )
1020  {
1021  if( Is_term(g->term[i]) && i != root )
1022  {
1023  e = g->outbeg[i];
1024  while( e != EAT_LAST )
1025  {
1026  e2 = g->oeat[e];
1027 
1028  if( SCIPisGE(scip, g->cost[flipedge(e)], FARAWAY) )
1029  {
1030  SCIPdebugMessage("delete anti-parallel terminal arcs \n");
1031  (*count)++;
1032  graph_edge_del(scip, g, e, TRUE);
1033  }
1034 
1035  e = e2;
1036  }
1037  }
1038  }
1039  }
1040 
1041  SCIPdebugMessage("HC basic reduction package has deleted %d edges\n", *count);
1042 
1043  return SCIP_OKAY;
1044 }
1045 
1046 
1047 /** basic reductions for RPCSTP and PCSPG */
1048 SCIP_RETCODE degree_test_pc(
1049  SCIP* scip, /**< SCIP data structure */
1050  GRAPH* g, /**< graph data structure */
1051  SCIP_Real* fixed, /**< pointer to offfset value */
1052  int* count /**< pointer to number of reductions */
1053  )
1054 {
1055  int* edges2;
1056  int* nodes2;
1057  int i;
1058  int i1;
1059  int i2;
1060  int e;
1061  int e1;
1062  int e2;
1063  int nnodes;
1064  SCIP_Bool pc;
1065  SCIP_Bool rerun = TRUE;
1066 
1067  assert(g != NULL);
1068  assert(fixed != NULL);
1069  assert(count != NULL);
1070  assert(g->stp_type == STP_PRIZE_COLLECTING || g->stp_type == STP_ROOTED_PRIZE_COLLECTING);
1071 
1072  pc = (g->stp_type == STP_PRIZE_COLLECTING);
1073 
1074  nnodes = g->knots;
1075  *count = 0;
1076 
1077  /* allocate memory */
1078  SCIP_CALL( SCIPallocBufferArray(scip, &edges2, 2) );
1079  SCIP_CALL( SCIPallocBufferArray(scip, &nodes2, 2) );
1080 
1081  SCIPdebugMessage("Degree Test: ");
1082 
1083  if( !pc )
1084  g->mark[g->source[0]] = FALSE;
1085 
1086  /* main loop */
1087  while( rerun )
1088  {
1089  rerun = FALSE;
1090 
1091  for( i = 0; i < nnodes; i++ )
1092  {
1093  assert(g->grad[i] >= 0);
1094  if( !g->mark[i] || g->grad[i] == 0 )
1095  continue;
1096 
1097  if( !Is_term(g->term[i]) )
1098  {
1099  if( g->grad[i] == 1 )
1100  {
1101  e1 = g->inpbeg[i];
1102  i1 = g->tail[e1];
1103  assert(e1 >= 0);
1104  assert(e1 == Edge_anti(g->outbeg[i]));
1105  assert(g->ieat[e1] == EAT_LAST);
1106  assert(g->oeat[g->outbeg[i]] == EAT_LAST);
1107 
1108  graph_edge_del(scip, g, e1, TRUE);
1109  SCIPdebugMessage("delete NT %d\n ", i);
1110  assert(g->grad[i] == 0);
1111 
1112  /* the last node? */
1113  if( g->grad[i1] == 0 )
1114  {
1115  rerun = FALSE;
1116  break;
1117  }
1118  if( (i1 < i) && (g->grad[i1] < 3 || Is_term(g->term[i1])) )
1119  rerun = TRUE;
1120 
1121  (*count)++;
1122  continue;
1123  }
1124 
1125  /* contract non terminals of degree 2 */
1126  if( g->grad[i] == 2 )
1127  {
1128  e1 = g->outbeg[i];
1129  e2 = g->oeat[e1];
1130  i1 = g->head[e1];
1131  i2 = g->head[e2];
1132 
1133  assert(e1 >= 0);
1134  assert(e2 >= 0);
1135  assert(g->mark[i1] || i1 == g->source[0]);
1136  assert(g->mark[i2] || i2 == g->source[0]);
1137  assert(EQ(g->cost[e2], g->cost[Edge_anti(e2)]));
1138 
1139  g->cost[e1] += g->cost[e2];
1140  g->cost[Edge_anti(e1)] += g->cost[e2];
1141 
1142  SCIPdebugMessage("contract NT %d %d \n ", i2, i);
1143  SCIP_CALL( graph_knot_contract(scip, g, i2, i) );
1144  (*count)++;
1145 
1146  if( (Is_term(g->term[i2]) && (i2 < i)) || (Is_term(g->term[i1]) && (i1 < i)) )
1147  rerun = TRUE;
1148  }
1149  continue;
1150  }
1151 
1152  /* node i is a terminal: */
1153 
1154  /* terminal of (real) degree 0? */
1155  if( ( (g->grad[i] == 2 && pc) || (g->grad[i] == 1 && !pc) ) )
1156  {
1157  /* if terminal node i is node the one with the highest prize, delete*/
1158  if( !maxprize(scip, g, i) )
1159  {
1160  SCIPdebugMessage("delete 0 term %d prize: %f count:%d\n ", i, g->prize[i], *count);
1161  (*fixed) += g->prize[i];
1162  (*count) += deleteterm(scip, g, i);
1163  }
1164  }
1165  /* terminal of (real) degree 1? */
1166  else if( ( (g->grad[i] == 3 && pc) || (g->grad[i] == 2 && !pc) ) )
1167  {
1168  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1169  if( g->mark[g->head[e]] || (!pc && g->head[e] == g->source[0]) )
1170  break;
1171  assert(e != EAT_LAST);
1172  assert(g->head[e] != g->source[0] || !pc);
1173 
1174  SCIP_CALL( trydg1edgepc(scip, g, fixed, count, i, e, &rerun) );
1175  }
1176  /* terminal of (real) degree 2? */
1177  else if( ( (g->grad[i] == 4 && pc) || (g->grad[i] == 3 && !pc) ) )
1178  {
1179  if( !maxprize(scip, g, i) )
1180  {
1181  i2 = 0;
1182  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
1183  {
1184  i1 = g->head[e];
1185  if( g->mark[i1] )
1186  {
1187  if( i2 >= 2 )
1188  assert(i2 < 2);
1189  edges2[i2] = e;
1190  nodes2[i2++] = i1;
1191  }
1192  }
1193  if( SCIPisLE(scip, g->prize[i], g->cost[edges2[0]]) && SCIPisLE(scip, g->prize[i], g->cost[edges2[1]]) )
1194  {
1195  int n1;
1196  IDX* ancestors = NULL;
1197  IDX* revancestors = NULL;
1198 
1199  e = edges2[0];
1200  e1 = edges2[1];
1201  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[e]) );
1202  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), g->ancestors[Edge_anti(e1)]) );
1203  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[Edge_anti(e)]) );
1204  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors), g->ancestors[e1]) );
1205  SCIPdebugMessage("delete - term - %d\n ", i);
1206 
1207  /* contract edge */
1208  n1 = graph_edge_redirect(scip, g, e, nodes2[1], nodes2[0], g->cost[e] + g->cost[e1] - g->prize[i]);
1209 
1210  /* new edge inserted? */
1211  if( n1 >= 0)
1212  {
1213  /* add ancestors */
1214  SCIPintListNodeFree(scip, &(g->ancestors[n1]));
1215  SCIPintListNodeFree(scip, &(g->ancestors[Edge_anti(n1)]));
1216  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[n1]), ancestors) );
1217  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(n1)]), revancestors) );
1218  }
1219  (*count) += deleteterm(scip, g, i);
1220  (*fixed) += g->prize[i];
1221  SCIPintListNodeFree(scip, &(ancestors));
1222  SCIPintListNodeFree(scip, &(revancestors));
1223  }
1224  }
1225  }
1226 
1227  /* try to contract adjacent terminals */
1228  if( g->grad[i] > 0 )
1229  {
1230  SCIP_Real mincost = FARAWAY;
1231  int ett = UNKNOWN;
1232 
1233  for( e1 = g->outbeg[i]; e1 != EAT_LAST; e1 = g->oeat[e1] )
1234  {
1235  i1 = g->head[e1];
1236  if( !g->mark[i1] )
1237  continue;
1238  if( SCIPisLT(scip, g->cost[e1], mincost) )
1239  {
1240  mincost = g->cost[e1];
1241  if( Is_term(g->term[i1]) )
1242  ett = e1;
1243  }
1244  else if( Is_term(g->term[i1]) && SCIPisLE(scip, g->cost[e1], mincost) )
1245  {
1246  assert(SCIPisLT(scip, g->cost[e1], FARAWAY));
1247  assert(SCIPisEQ(scip, g->cost[e1], mincost));
1248  ett = e1;
1249  }
1250  }
1251  if( ett != UNKNOWN && SCIPisLE(scip, g->cost[ett], mincost) && SCIPisLE(scip, g->cost[ett], g->prize[i])
1252  && SCIPisLE(scip, g->cost[ett], g->prize[g->head[ett]]) )
1253  {
1254  i1 = g->head[ett];
1255  SCIPdebugMessage("contract tt %d->%d\n ", i, i1);
1256  assert(SCIPisLT(scip, mincost, FARAWAY));
1257  *fixed += g->cost[ett];
1258  (*count)++;
1259  SCIP_CALL( graph_knot_contractpc(scip, g, i, i1, i) );
1260  rerun = TRUE;
1261  }
1262  }
1263  }
1264  }
1265 
1266  if( !pc )
1267  g->mark[g->source[0]] = TRUE;
1268  SCIPdebugMessage("dirdeg %d Knots deleted\n", *count);
1269 
1270  /* free memory */
1271  SCIPfreeBufferArray(scip, &nodes2);
1272  SCIPfreeBufferArray(scip, &edges2);
1273 
1274  return SCIP_OKAY;
1275 }
Is_term
#define Is_term(a)
Definition: grph.h:158
Int_List_Node
Definition: misc_stp.h:66
graph_valid
int graph_valid(const GRAPH *)
Definition: grphbase.c:2532
GRAPH
Definition: grph.h:55
TRUE
#define TRUE
Definition: portab.h:34
STP_HOP_CONS
#define STP_HOP_CONS
Definition: grph.h:48
EAT_LAST
#define EAT_LAST
Definition: grph.h:31
Edge_anti
#define Edge_anti(a)
Definition: grph.h:161
graph_knot_contract
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int, int)
Definition: grphbase.c:1415
maxprize
static SCIP_Bool maxprize(SCIP *scip, GRAPH *g, int i)
Definition: reduce_simple.c:40
GRAPH::oeat
int * oeat
Definition: grph.h:100
graph_edge_redirect
int graph_edge_redirect(SCIP *, GRAPH *, int, int, int, SCIP_Real)
Definition: grphbase.c:1783
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: grphbase.c:1386
GRAPH::head
int * head
Definition: grph.h:94
GRAPH::fixedges
IDX * fixedges
Definition: grph.h:82
trydg1edgepc
static SCIP_RETCODE trydg1edgepc(SCIP *scip, GRAPH *g, SCIP_Real *offset, int *count, int i, int iout, SCIP_Bool *rerun)
Definition: reduce_simple.c:73
FALSE
#define FALSE
Definition: portab.h:37
SCIPintListNodeFree
void SCIPintListNodeFree(SCIP *scip, IDX **node)
Definition: misc_stp.c:140
GRAPH::mark
int * mark
Definition: grph.h:71
graph_path_execX
void graph_path_execX(SCIP *, const GRAPH *, int, SCIP_Real *, SCIP_Real *, int *)
Definition: grphpath.c:639
EQ
#define EQ(a, b)
Definition: portab.h:62
GRAPH::stp_type
int stp_type
Definition: grph.h:123
GRAPH::ancestors
IDX ** ancestors
Definition: grph.h:83
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:248
GRAPH::outbeg
int * outbeg
Definition: grph.h:77
Is_pterm
#define Is_pterm(a)
Definition: grph.h:159
rptReduction
SCIP_RETCODE rptReduction(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:739
degree_test_pc
SCIP_RETCODE degree_test_pc(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:1048
GRAPH::prize
SCIP_Real * prize
Definition: grph.h:92
GRAPH::tail
int * tail
Definition: grph.h:93
GRAPH::term
int * term
Definition: grph.h:69
deleteterm
int deleteterm(SCIP *scip, GRAPH *g, int i)
Definition: reduce_simple.c:343
GRAPH::knots
int knots
Definition: grph.h:61
GRAPH::pcancestors
IDX ** pcancestors
Definition: grph.h:84
degree_test
SCIP_RETCODE degree_test(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *nelims)
Definition: reduce_simple.c:390
STP_MAX_NODE_WEIGHT
#define STP_MAX_NODE_WEIGHT
Definition: grph.h:47
GRAPH::inpbeg
int * inpbeg
Definition: grph.h:75
FARAWAY
#define FARAWAY
Definition: grph.h:149
SCIPintListNodeAppendCopy
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2)
Definition: misc_stp.c:76
UNKNOWN
#define UNKNOWN
Definition: grph.h:148
degree_test_sap
SCIP_RETCODE degree_test_sap(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:566
STP_PRIZE_COLLECTING
#define STP_PRIZE_COLLECTING
Definition: grph.h:40
graph_edge_del
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: grphbase.c:1965
grph.h
includes various files containing graph methods used for Steiner problems
portab.h
Portable defintions.
GRAPH::grad
int * grad
Definition: grph.h:74
GRAPH::cost
SCIP_Real * cost
Definition: grph.h:91
STP_ROOTED_PRIZE_COLLECTING
#define STP_ROOTED_PRIZE_COLLECTING
Definition: grph.h:41
GRAPH::source
int * source
Definition: grph.h:67
graph_knot_contractpc
SCIP_RETCODE graph_knot_contractpc(SCIP *, GRAPH *, int, int, int)
Definition: grphbase.c:1679
GRAPH::edges
int edges
Definition: grph.h:89
flipedge
#define flipedge(edge)
Definition: grph.h:143
GRAPH::ieat
int * ieat
Definition: grph.h:99
degree_test_mw
SCIP_RETCODE degree_test_mw(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:811
degree_test_hc
SCIP_RETCODE degree_test_hc(SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
Definition: reduce_simple.c:968