# SCIP

Solving Constraint Integer Programs

graph_trans.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 graph_trans.c
17  * @brief Transformation algorithms for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This includes method for transformations (or reductions) between the different Steiner problem classes.
21  *
22  * A list of all interface methods can be found in graph.h.
23  *
24  *
25  */
26
27 //#define SCIP_DEBUG
28
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <assert.h>
32 #include "portab.h"
33 #include "graph.h"
34
35 #define TRANS_MAXPRIZESUM 1e09
36
37
38 /** initializes cost_org_pc array (call right after transformation to extended has been performed) */
39 static
41  SCIP* scip, /**< SCIP */
42  GRAPH* g /**< the graph */
43 )
44 {
45  const int nedges = g->edges;
46  SCIP_Real* const cost = g->cost;
47
48  assert(!g->cost_org_pc);
49  assert(graph_pc_isPc(g));
50  assert(g->extended);
51
52  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->cost_org_pc), nedges) );
53  BMScopyMemoryArray(g->cost_org_pc, cost, nedges);
54
55  return SCIP_OKAY;
56 }
57
58
59 /** is vertex a non-leaf (call before graph transformation was performed) */
60 static inline
62  SCIP* scip, /**< SCIP */
63  const GRAPH* g, /**< the graph */
64  int vertex /**< node check */
65 )
66 {
67  const SCIP_Real prize = g->prize[vertex];
68  const SCIP_Real* const cost = g->cost;
69
70  for( int e = g->inpbeg[vertex]; e != EAT_LAST; e = g->ieat[e] )
71  {
72  if( SCIPisGT(scip, prize, cost[e]) )
73  return FALSE;
74  }
75
76  return TRUE;
77 }
78
79
80
81 /** remove non-leaf terminals by edge weight shifting (call before graph transformation was performed,
82  * call only from graph transformation method!) */
83 static
85  SCIP* scip, /**< SCIP */
86  GRAPH* g /**< the graph */
87 )
88 {
89  const int nnodes = g->knots;
90
91  for( int k = 0; k < nnodes; k++ )
92  {
93  if( !Is_term(g->term[k]) )
94  continue;
95
96  if( isNonLeaf_pretransPc(scip, g, k) )
97  {
99  }
100  }
101 }
102
103
104 /** sets root */
105 static
107  GRAPH* g /**< the graph */
108 )
109 {
110  const int nnodes = graph_get_nNodes(g);
111
112  assert(g->source == UNKNOWN);
113  assert(g->stp_type == STP_NWPTSPG);
114
115  if( g->terms <= 2 )
116  {
117  for( int i = 0; i < nnodes; i++ )
118  {
119  if( Is_term(g->term[i]) )
120  {
121  g->source = i;
122  break;
123  }
124  }
125  }
126  else
127  {
128  const int* const grad = g->grad;
129
130  for( int i = 0; i < nnodes; i++ )
131  {
132  if( Is_term(g->term[i]) && ((g->source < 0) || (grad[i] > grad[g->source])) )
133  {
134  if( graph_knotIsNWLeaf(g, i) )
135  continue;
136
137  g->source = i;
138  }
139  }
140  }
141
142  assert(g->source != UNKNOWN);
143  assert(Is_term(g->term[g->source]));
144 }
145
146
147
148 /*
149  * Interface methods
150  */
151
152
153 /** alters the graph for prize collecting problems */
155  SCIP* scip, /**< SCIP data structure */
156  GRAPH* graph /**< the graph */
157  )
158 {
159  int root;
160  const int nnodes = graph->knots;
161  int termscount;
162
163  assert(scip && graph->prize);
164  assert(!graph->extended);
165  assert(graph->edges == graph->esize && nnodes == graph->ksize);
166
167  graph->norgmodeledges = graph->edges;
168  graph->norgmodelknots = nnodes;
169
170  /* for PC remove terminal property from non-leaves and reduce terminal count */
171  if( graph->stp_type != STP_MWCSP )
172  markNonLeafTerms_pretransPc(scip, graph);
173
174  /* for each proper terminal, except for the root, one node and three edges (i.e. six arcs) are to be added */
175  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + graph->terms + 1), (graph->esize + graph->terms * 6) , -1) );
176
177  /* add future terminals */
178  for( int k = 0; k < graph->terms; ++k )
179  graph_knot_add(graph, -1);
180
181  /* add new root */
182  root = graph->knots;
183  graph_knot_add(graph, 0);
184  graph->prize[root] = 0.0;
185
186  SCIP_CALL( graph_pc_initTerm2Edge(scip, graph, graph->knots) );
187
188  graph->term2edge[root] = TERM2EDGE_FIXEDTERM;
189
190  termscount = 0;
191  for( int k = 0; k < nnodes; ++k )
192  {
193  if( Is_nonleafTerm(graph->term[k]) )
194  {
195  assert(graph->stp_type != STP_MWCSP);
196  graph->term2edge[k] = TERM2EDGE_NONLEAFTERM;
197
198  continue;
199  }
200
201  if( Is_term(graph->term[k]) )
202  {
203  /* get the new terminal */
204  const int node = nnodes + termscount;
205  termscount++;
206
207  assert(node != root && k != root);
208
209  /* switch the terminal property, mark k */
210  graph_knot_chg(graph, k, STP_TERM_PSEUDO);
211  graph_knot_chg(graph, node, STP_TERM);
212  graph->prize[node] = 0.0;
213  assert(SCIPisGE(scip, graph->prize[k], 0.0));
214
215  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
216  graph_edge_add(scip, graph, root, k, 0.0, FARAWAY);
217  graph_edge_add(scip, graph, root, node, graph->prize[k], FARAWAY);
218
219  graph->term2edge[k] = graph->edges;
220  graph->term2edge[node] = graph->edges + 1;
221  assert(graph->edges + 1 == flipedge(graph->edges));
222
223  graph_edge_add(scip, graph, k, node, 0.0, FARAWAY);
224
225  assert(graph->head[graph->term2edge[k]] == node);
226  assert(graph->head[graph->term2edge[node]] == k);
227  }
228  else if( graph->stp_type != STP_MWCSP )
229  {
230  graph->prize[k] = 0.0;
231  }
232  }
233
234  assert((termscount + 1) == graph->terms);
235
236  graph->source = root;
237  graph->extended = TRUE;
238
239  if( graph->stp_type != STP_MWCSP )
240  {
241  graph->stp_type = STP_PCSPG;
242
243  SCIP_CALL( initCostOrgPc(scip, graph) );
244  graph_pc_shiftNonLeafCosts(scip, graph);
245  SCIPdebugMessage("Transformed to PC \n");
246  }
247
248  assert(graph_pc_term2edgeIsConsistent(scip, graph));
249  assert(graph_valid(scip, graph));
250  assert(graph->orgsource == -1);
251
252  return SCIP_OKAY;
253 }
254
255
256 /** alters the graph for prize collecting problems and transforms it to an SPG */
258  SCIP* scip, /**< SCIP data structure */
259  PRESOL* presol, /**< presolving struct */
260  GRAPH* graph /**< the graph */
261  )
262 {
263  SCIP_Real baseprize = FARAWAY;
264  int root;
265  int baseterm = -1;
266  int termscount;
267  const int nnodes_org = graph->knots;
268  SCIP_Real prizesum;
269  int naddedarcs;
270  int naddednodes;
271  const int nterms_org = graph->terms;
272
273  assert(graph && graph->prize);
274  assert(graph->edges == graph->esize);
275  assert(graph->knots == graph->ksize);
276  assert(!graph->extended);
277  assert(nterms_org > 0);
278
279  prizesum = 1.0;
280  for( int i = 0; i < nnodes_org; i++ )
281  {
282  if( graph->prize[i] > 0.0 && SCIPisLT(scip, graph->prize[i], FARAWAY) )
283  {
284  prizesum += graph->prize[i];
285  }
286  }
287
288  printf("prizesum=%f \n", prizesum);
289  assert(prizesum < BLOCKED);
290
291  presol->fixed -= prizesum * (nterms_org + 1);
292
293  printf("fixed=%f \n", prizesum * (nterms_org + 1));
294
295  naddednodes = nterms_org + 1;
296  naddedarcs = 4 * nterms_org + 4 * (nterms_org - 1);
297
298  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + naddednodes), (graph->esize + naddedarcs) , -1) );
299
300  /* create new nodes corresponding to potential terminals */
301  for( int k = 0; k < nterms_org; ++k )
303
304  /* add new root */
305  root = graph->knots;
306  graph_knot_add(graph, STP_TERM);
307
308  graph->source = root;
309
310  /* select the base term */
311  termscount = 0;
312  for( int k = 0; k < nnodes_org; ++k )
313  {
314  if( Is_term(graph->term[k]) )
315  {
316  if( graph->prize[k] < baseprize )
317  {
318  baseterm = nnodes_org + termscount;
319  baseprize = graph->prize[k];
320  }
321
322  termscount++;
323  }
324  }
325  assert(termscount == nterms_org);
326  assert(baseterm >= 0);
327
328  termscount = 0;
329  for( int k = 0; k < nnodes_org; ++k )
330  {
331  /* is the kth node a potential terminal? */
332  if( Is_term(graph->term[k]) )
333  {
334  /* the future terminal */
335  const int newterm = nnodes_org + termscount;
336  termscount++;
337
338  assert(k != root && newterm != root);
339  assert(!Is_term(graph->term[newterm]));
340
341  if( baseterm == newterm )
342  {
343  assert(EQ(graph->prize[k], baseprize));
344  }
345  else
346  {
347  graph_edge_addBi(scip, graph, k, baseterm, prizesum + baseprize);
348  graph_edge_addBi(scip, graph, newterm, baseterm, prizesum + graph->prize[k]);
349  }
350
351  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
352  graph_edge_addBi(scip, graph, root, k, prizesum);
353  graph_edge_addBi(scip, graph, k, newterm, prizesum);
354
355  /* switch the terminal property, mark k as former terminal */
356  graph_knot_chg(graph, k, STP_TERM_NONE);
357  graph_knot_chg(graph, newterm, STP_TERM);
358  assert(SCIPisGE(scip, graph->prize[k], 0.0));
359  }
360  }
361
362  SCIPfreeMemoryArrayNull(scip, &(graph->prize));
363  SCIPfreeMemoryArrayNull(scip, &(graph->term2edge));
364
365  assert(termscount == nterms_org);
366  graph->stp_type = STP_SPG;
367  graph->extended = FALSE;
368
369  return SCIP_OKAY;
370 }
371
372 /** alters the graph for rooted prize collecting problems */
374  SCIP* scip, /**< SCIP data structure */
375  GRAPH* graph /**< the graph */
376  )
377 {
378  const int root = graph->source;
379  const int nnodes = graph->knots;
380  int nterms;
381  int nfixterms;
382  int npotterms;
383
384  assert(graph && graph->prize);
385  assert(graph->edges == graph->esize);
386  assert(graph->knots == graph->ksize);
387  assert(!graph->extended);
388  assert(root >= 0 && root < graph->knots) ;
389
390  graph->norgmodeledges = graph->edges;
391  graph->norgmodelknots = nnodes;
392  nfixterms = 0;
393  npotterms = 0;
394
395  /* remove terminal property from non-leaves and reduce terminal count */
396  markNonLeafTerms_pretransPc(scip, graph);
397
398  /* count number of fixed and potential terminals and adapt prizes */
399  for( int i = 0; i < nnodes; i++ )
400  {
401  if( Is_nonleafTerm(graph->term[i]) )
402  continue;
403
404  if( !Is_term(graph->term[i]) )
405  {
406  graph->prize[i] = 0.0;
407  assert(graph->term[i] == STP_TERM_NONE);
408  }
409  else if( SCIPisGE(scip, graph->prize[i], FARAWAY) )
410  {
411  assert(SCIPisEQ(scip, graph->prize[i], FARAWAY));
412  nfixterms++;
413  }
414  else if( SCIPisGT(scip, graph->prize[i], 0.0) )
415  {
416  assert(i != root);
417  assert(Is_term(graph->term[i]));
418  npotterms++;
419  }
420  else
421  {
422  assert(i != root);
423  assert(SCIPisEQ(scip, graph->prize[i], 0.0));
424  graph->prize[i] = 0.0;
425  graph_knot_chg(graph, i, STP_TERM_NONE);
426  }
427  }
428
429  assert(npotterms + nfixterms == graph->terms);
430
431  /* for each terminal, except for the root, one node and two edges (i.e. four arcs) are to be added */
432  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + npotterms), (graph->esize + npotterms * 4) , -1) );
433
434  /* create new nodes corresponding to potential terminals */
435  for( int k = 0; k < npotterms; ++k )
437
438  SCIP_CALL( graph_pc_initTerm2Edge(scip, graph, graph->knots) );
439
440  nterms = 0;
441
442  for( int k = 0; k < nnodes; ++k )
443  {
444  if( Is_nonleafTerm(graph->term[k]) )
445  {
446  graph->term2edge[k] = TERM2EDGE_NONLEAFTERM;
447  continue;
448  }
449
450  /* is the kth node a potential terminal? */
451  if( Is_term(graph->term[k]) && SCIPisLT(scip, graph->prize[k], FARAWAY) )
452  {
453  /* the future terminal */
454  const int node = nnodes + nterms;
455  nterms++;
456
457  assert(k != root && node != root);
458
459  /* switch the terminal property, mark k as former terminal */
460  graph_knot_chg(graph, k, STP_TERM_PSEUDO);
461  graph_knot_chg(graph, node, STP_TERM);
462  assert(SCIPisGE(scip, graph->prize[k], 0.0));
463  graph->prize[node] = 0.0;
464
465  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
466  graph_edge_add(scip, graph, root, node, graph->prize[k], FARAWAY);
467
468  graph->term2edge[k] = graph->edges;
469  graph->term2edge[node] = graph->edges + 1;
470  assert(graph->edges + 1 == flipedge(graph->edges));
471
472  graph_edge_add(scip, graph, k, node, 0.0, FARAWAY);
473
474  assert(graph->head[graph->term2edge[k]] == node);
475  assert(graph->head[graph->term2edge[node]] == k);
476  }
477  else if( Is_term(graph->term[k]) )
478  {
479  assert(EQ(graph->prize[k], FARAWAY));
481  }
482  else
483  {
484  assert(EQ(graph->prize[k], 0.0));
485  }
486  }
487
488  graph->stp_type = STP_RPCSPG;
489  graph->orgsource = graph->source;
490  graph->extended = TRUE;
491
492  SCIP_CALL( initCostOrgPc(scip, graph) );
493  graph_pc_shiftNonLeafCosts(scip, graph);
494
495  assert(nterms == npotterms);
496  assert(graph->prize[graph->source] == FARAWAY);
497  SCIPdebugMessage("Transformed problem to (RPC) SAP \n");
498
499  return SCIP_OKAY;
500 }
501
502
503 /** alters the graph from rooted prize collecting problems to SPG if there are not potential terminals.
504  * NOTE: deletes some PC data, but keeps history, in order to be able to reconstruct original optimal solution. */
506  SCIP* scip, /**< SCIP data structure */
507  GRAPH* g /**< the graph */
508  )
509 {
510  assert(scip && g);
511  assert(g->stp_type == STP_RPCSPG);
512
514  {
515  SCIPerrorMessage("tried invalid transformation from RPC to SPG \n");
516  return SCIP_ERROR;
517  }
518
519  graph_pc_2orgcheck(scip, g);
520  SCIPfreeMemoryArrayNull(scip, &(g->prize));
521  SCIPfreeMemoryArrayNull(scip, &(g->costbudget));
522  SCIPfreeMemoryArrayNull(scip, &(g->term2edge));
523
524  g->stp_type = STP_SPG;
525
526  return SCIP_OKAY;
527 }
528
529
530 /** changes the graph for rooted prize collecting problems such that no proper potential terminal are fixed */
532  SCIP* scip, /**< SCIP data structure */
533  PRESOL* presol, /**< presolving struct */
534  GRAPH* graph /**< the graph */
535  )
536 {
537  const int root = graph->source;
538  const int nnodes = graph->knots;
539  SCIP_Real prizesum;
540  int nterms;
541  int nfixterms = 0;
542  int npropterms = 0;
543
544  assert(graph && graph->prize);
545  assert(graph->edges == graph->esize);
546  assert(graph->knots == graph->ksize);
547  assert(!graph->extended);
548
549  /* count number of fixed and potential terminals */
550  for( int i = 0; i < nnodes; i++ )
551  {
552  if( isNonLeaf_pretransPc(scip, graph, i) )
553  continue;
554
555  if( SCIPisGE(scip, graph->prize[i], FARAWAY) )
556  {
557  assert(SCIPisEQ(scip, graph->prize[i], FARAWAY));
558  nfixterms++;
559  }
560  else if( SCIPisGT(scip, graph->prize[i], 0.0) )
561  {
562  assert(i != root);
563  assert(Is_term(graph->term[i]));
564  npropterms++;
565  }
566  }
567
568  prizesum = 0.0;
569  for( int i = 0; i < nnodes; i++ )
570  {
571  if( graph->prize[i] > 0.0 && SCIPisLT(scip, graph->prize[i], FARAWAY) )
572  {
573  prizesum += graph->prize[i];
574  }
575  }
576
577  printf("prizesum=%f \n", prizesum);
578  assert(prizesum < BLOCKED);
579
580  presol->fixed -= prizesum * npropterms;
581
582  printf("number of proper potential terminals %d \n", npropterms);
583  printf("fixed=%f \n", prizesum * npropterms);
584
585  /* for each terminal, except for the root, one node and two edges (i.e. four arcs) are to be added */
586  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + npropterms), (graph->esize + npropterms * 4) , -1) );
587
588  /* create new nodes corresponding to potential terminals */
589  for( int k = 0; k < npropterms; ++k )
591
592  nterms = 0;
593
594  for( int k = 0; k < nnodes; ++k )
595  {
596  if( isNonLeaf_pretransPc(scip, graph, k) )
597  continue;
598
599  /* is the kth node a potential terminal? */
600  if( Is_term(graph->term[k]) && SCIPisLT(scip, graph->prize[k], FARAWAY) )
601  {
602  /* the future terminal */
603  const int newterm = nnodes + nterms;
604  nterms++;
605
606  assert(k != root && newterm != root);
607  assert(!Is_term(graph->term[newterm]));
608
609  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
610  graph_edge_addBi(scip, graph, root, newterm, prizesum + graph->prize[k]);
611  graph_edge_addBi(scip, graph, k, newterm, prizesum);
612
613  /* switch the terminal property, mark k as former terminal */
614  graph_knot_chg(graph, k, STP_TERM_NONE);
615  graph_knot_chg(graph, newterm, STP_TERM);
616  assert(SCIPisGE(scip, graph->prize[k], 0.0));
617  graph->prize[k] = 0.0;
618  graph->prize[newterm] = FARAWAY;
619  }
620  }
621
622  assert(nterms == npropterms);
623  assert(graph->prize[root] == FARAWAY);
624
625  SCIP_CALL( graph_transRpc(scip, graph) );
626
627  return SCIP_OKAY;
628 }
629
630
631 /** alters the graph for MWCS problems */
633  SCIP* scip, /**< SCIP data structure */
634  GRAPH* graph /**< the graph */
635  )
636 {
637  int nterms = 0;
638  const int nnodes = graph_get_nNodes(graph);
639  SCIP_Real* const maxweights = graph->prize;
640
641  assert(maxweights != NULL);
642  assert(scip != NULL);
643  assert(graph->cost != NULL);
644  assert(graph->terms == 0);
645
646  /* count number of terminals, modify incoming edges for non-terminals */
647  for( int i = 0; i < nnodes; i++ )
648  {
649  if( SCIPisLT(scip, maxweights[i], 0.0) )
650  {
651  for( int e = graph->inpbeg[i]; e != EAT_LAST; e = graph->ieat[e] )
652  graph->cost[e] -= maxweights[i];
653  }
654  else if( SCIPisGT(scip, maxweights[i], 0.0) )
655  {
656  graph_knot_chg(graph, i, 0);
657  nterms++;
658  }
659  }
660  nterms = 0;
661  for( int i = 0; i < nnodes; i++ )
662  {
663  if( Is_term(graph->term[i]) )
664  {
665  assert(SCIPisGE(scip, maxweights[i], 0.0));
666  nterms++;
667  }
668  else
669  {
670  assert(SCIPisLE(scip, maxweights[i], 0.0));
671  }
672  }
673  assert(nterms == graph->terms);
674  graph->stp_type = STP_MWCSP;
675
676  SCIP_CALL( graph_transPc(scip, graph) );
677  assert(graph->stp_type == STP_MWCSP);
678
679  SCIPdebugMessage("Transformed to MW \n");
680
681  return SCIP_OKAY;
682 }
683
684
685
686 /** alters the graph for RMWCS problems */
688  SCIP* scip, /**< SCIP data structure */
689  GRAPH* graph /**< the graph */
690  )
691 {
692  SCIP_Real* maxweights;
693  int i;
694  int root;
695  int nnodes;
696  int npterms;
697  int nrterms;
698  int maxgrad;
699
700  assert(scip != NULL);
701  assert(graph != NULL);
702  assert(graph->cost != NULL);
703
704  root = -1;
705  maxgrad = -1;
706  npterms = 0;
707  nrterms = 0;
708  nnodes = graph->knots;
709  maxweights = graph->prize;
710
711  assert(maxweights != NULL);
712
713  /* count number of terminals, modify incoming edges for non-terminals */
714  for( i = 0; i < nnodes; i++ )
715  {
716  if( SCIPisLT(scip, maxweights[i], 0.0) )
717  {
718  for( int e = graph->inpbeg[i]; e != EAT_LAST; e = graph->ieat[e] )
719  graph->cost[e] = -maxweights[i];
720  }
721  else if( SCIPisGE(scip, maxweights[i], FARAWAY) )
722  {
723  assert(Is_term(graph->term[i]));
724  if( graph->grad[i] > maxgrad )
725  {
726  root = i;
727  maxgrad = graph->grad[i];
728  }
729
730  nrterms++;
731  }
732  else if( SCIPisGT(scip, maxweights[i], 0.0) )
733  {
734  graph_knot_chg(graph, i, STP_TERM);
735  npterms++;
736  }
737  }
738
739  assert(root >= 0);
740  assert(graph->terms == (npterms + nrterms));
741
742  graph->norgmodeledges = graph->edges;
743  graph->norgmodelknots = nnodes;
744  graph->source = root;
745
746  /* for each terminal, except for the root, one node and three edges (i.e. six arcs) are to be added */
747  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + npterms), (graph->esize + npterms * 4) , -1) );
748  maxweights = graph->prize;
749
750  /* create new nodes */
751  for( int k = 0; k < npterms; k++ )
752  graph_knot_add(graph, -1);
753
754  SCIP_CALL( graph_pc_initTerm2Edge(scip, graph, graph->knots) );
755
756  i = 0;
757  for( int k = 0; k < nnodes; ++k )
758  {
759  /* is the kth node a non-fixed terminal */
760  if( Is_term(graph->term[k]) && SCIPisLT(scip, maxweights[k], FARAWAY) )
761  {
762  /* the copied node */
763  const int node = nnodes + i;
764  i++;
765
766  /* switch the terminal property, mark k */
767  graph_knot_chg(graph, k, -2);
768  graph_knot_chg(graph, node, 0);
769  graph->prize[node] = 0.0;
770  assert(SCIPisGE(scip, maxweights[k], 0.0));
771
772  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
773  graph_edge_add(scip, graph, root, node, maxweights[k], FARAWAY);
774
775  graph->term2edge[k] = graph->edges;
776  graph->term2edge[node] = graph->edges + 1;
777  assert(graph->edges + 1 == flipedge(graph->edges));
778
779  graph_edge_add(scip, graph, k, node, 0.0, FARAWAY);
780
781  assert(graph->head[graph->term2edge[k]] == node);
782  assert(graph->head[graph->term2edge[node]] == k);
783  }
784  else if( Is_term(graph->term[k]) )
785  {
786  assert(EQ(graph->prize[k], FARAWAY));
788  }
789  else
790  {
791  assert(LE(graph->prize[k], 0.0));
792  }
793  }
794
795  graph->extended = TRUE;
796  graph->stp_type = STP_RMWCSP;
797  graph->orgsource = graph->source;
798
799  assert(i == npterms);
800  assert(graph_valid(scip, graph));
801
802  SCIPdebugMessage("Transformed to RMW \n");
803
804  return SCIP_OKAY;
805 }
806
807
808 /** transforms PCSPG or MWCSP to RPCSPG or RMWCSP if possible */
810  SCIP* scip, /**< SCIP data structure */
811  GRAPH* graph, /**< the graph */
812  SCIP_Real fixprize, /**< prize at which to make terminals */
813  SCIP_Bool verbose /**< be verbose? */
814  )
815 {
816  int e;
817  int newroot;
818  int maxgrad;
819  int nfixedterms;
820  const int orgnterms = graph->terms;
821  const int root = graph->source;
822  const int pc = (graph->stp_type == STP_PCSPG);
823
824  assert(scip != NULL);
825  assert(graph != NULL);
826  assert(graph->term2edge != NULL);
827  assert(!graph->extended);
828  assert(pc || graph->stp_type == STP_MWCSP);
829
830  newroot = -1;
831  maxgrad = -1;
832
833  if( verbose )
834  printf("attempt transformation to rooted problem \n");
835
836  nfixedterms = 0;
837  e = graph->outbeg[root];
838  while( e != EAT_LAST )
839  {
840  const int enext = graph->oeat[e];
841  if( SCIPisGE(scip, graph->cost[e], fixprize) )
842  {
843  const int dummyterm = graph->head[e];
844  const int pseudoterm = graph_pc_getTwinTerm(graph, dummyterm);
845
846  assert(Is_pseudoTerm(graph->term[dummyterm]));
847  assert(graph->grad[dummyterm] == 2);
848  assert(Is_term(graph->term[pseudoterm]));
849  assert(SCIPisGE(scip, graph->prize[pseudoterm], fixprize));
850
851  graph_pc_knotToNonTermProperty(graph, dummyterm);
852
853  graph_knot_del(scip, graph, dummyterm, TRUE);
854
855  graph_pc_knotToFixedTermProperty(graph, pseudoterm);
856
857  SCIPdebugMessage("fix terminal %d (delete %d)\n", pseudoterm, dummyterm);
858
859  if( graph->grad[pseudoterm] > maxgrad )
860  {
861  newroot = pseudoterm;
862  maxgrad = graph->grad[pseudoterm];
863  }
864
865  nfixedterms++;
866  }
867  e = enext;
868  }
869
870  /* is there a new root? */
871  if( newroot >= 0 )
872  {
873  graph->source = newroot;
874
875  if( graph->rootedgeprevs != NULL )
876  graph_pc_presolExit(scip, graph);
877
878  e = graph->outbeg[root];
879  while( e != EAT_LAST )
880  {
881  const int enext = graph->oeat[e];
882  const int k = graph->head[e];
883
884  if( Is_pseudoTerm(graph->term[k]) )
885  {
886  (void) graph_edge_redirect(scip, graph, e, newroot, k, graph->cost[e], TRUE, TRUE);
887  graph->cost[flipedge(e)] = FARAWAY;
888  }
889  e = enext;
890  }
891
892  /* delete old root (cannot use default function) */
893  graph_knot_chg(graph, root, STP_TERM_NONE);
894  graph->term2edge[root] = TERM2EDGE_NOTERM;
895  graph->prize[root] = 0.0;
896  graph_knot_del(scip, graph, root, TRUE);
897
898  if( pc )
899  graph->stp_type = STP_RPCSPG;
900  else
901  graph->stp_type = STP_RMWCSP;
902
903  assert(graph_valid(scip, graph));
904
905  if( verbose )
906  {
907  if( pc )
908  printf("...transformed PC to RPC; fixed %d out of %d terminals \n", nfixedterms, orgnterms - 1);
909  else
910  printf("...transformed MW to RMW; fixed %d out of %d terminals \n", nfixedterms, orgnterms - 1);
911  }
912
913  assert(orgnterms - 1 == graph->terms);
914  }
915
916  if( verbose )
917  {
918  if( !graph_pc_isRootedPcMw(graph) )
919  printf("...failed \n");
920  }
921
922  assert(graph_valid(scip, graph));
923
924  return SCIP_OKAY;
925 }
926
927
928
929
930 /** obtains an SAP from prize collecting problems */
932  SCIP* scip, /**< SCIP data structure */
933  GRAPH* graph, /**< the graph */
934  GRAPH** newgraph, /**< the new graph */
935  SCIP_Real* offset /**< offset (in/out) */
936  )
937 {
938  SCIP_Real prizesum = 0.0;
939  int e;
940  int maxpvert;
941  const int root = graph->source;
942  const int nnodes = graph->knots;
943  const int nterms = graph->terms;
944  const int stp_type = graph->stp_type;
945  int pseudoroot;
946
947  assert(scip && graph && graph->prize && offset);
948  assert(graph->knots == graph->ksize);
949  assert(graph->edges == graph->esize);
950  assert(graph->extended);
951  assert(*offset >= 0.0);
952
953  if( graph_pc_isPc(graph) )
954  {
955  *offset += graph_pc_getNonLeafTermOffset(scip, graph);
956  }
957
958  graph->stp_type = STP_SAP;
959  SCIP_CALL( graph_copy(scip, graph, newgraph) );
960  graph->stp_type = stp_type;
961
962  /* for each terminal, except for the root, three edges (i.e. six arcs) are to be added */
963  SCIP_CALL( graph_resize(scip, (*newgraph), ((*newgraph)->ksize + 1), ((*newgraph)->esize + 2 * (nterms - 1)) , -1) );
964
965  assert((*newgraph)->source == root);
966
967  /* new pseudo-root */
968  pseudoroot = (*newgraph)->knots;
969  graph_knot_add((*newgraph), -1);
970
971  maxpvert = -1;
972
973  for( int k = 0; k < nnodes; k++ )
974  {
975  if( Is_pseudoTerm(graph->term[k]) && (maxpvert == -1 || graph->prize[k] > graph->prize[maxpvert]) )
976  maxpvert = k;
977  }
978
979  /* compute upper bound on best prize sum */
980  for( int k = 0; k < nnodes; k++ )
981  {
982  if( Is_pseudoTerm(graph->term[k]) )
983  {
984  prizesum += graph->prize[k];
985
986  if( stp_type == STP_PCSPG && k != maxpvert )
987  {
988  SCIP_Real minin = FARAWAY;
989  for( e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
990  if( !graph_pc_knotIsDummyTerm(graph, graph->tail[e]) && graph->cost[e] < minin )
991  minin = graph->cost[e];
992
993  assert(!SCIPisZero(scip, minin));
994
995  prizesum -= MIN(minin, graph->prize[k]);
996  }
997  }
998  }
999
1000  assert(SCIPisLT(scip, prizesum, FARAWAY));
1001
1002  *offset -= prizesum;
1003  SCIP_CALL( graph_pc_presolInit(scip, *newgraph) );
1004
1005  e = (*newgraph)->outbeg[root];
1006
1007  while( e != EAT_LAST )
1008  {
1009  const int enext = (*newgraph)->oeat[e];
1010  const int head = (*newgraph)->head[e];
1011
1012  if( Is_term((*newgraph)->term[head]) )
1013  {
1014  (void) graph_edge_redirect(scip, (*newgraph), e, pseudoroot, head, graph->cost[e], TRUE, FALSE);
1015  (*newgraph)->cost[flipedge(e)] = FARAWAY;
1016  assert((*newgraph)->head[e] == head);
1017  assert((*newgraph)->tail[e] == pseudoroot);
1018  }
1019  else
1020  {
1021  (*newgraph)->cost[e] = prizesum;
1022  }
1023
1024  e = enext;
1025  }
1026
1027  graph_pc_presolExit(scip, *newgraph);
1028
1029  for( int k = 0; k < nnodes; k++ )
1030  {
1031  /* is the kth node a terminal other than the root? */
1032  if( Is_pseudoTerm((*newgraph)->term[k]) )
1033  graph_edge_add(scip, (*newgraph), k, pseudoroot, 0.0, FARAWAY);
1034  }
1035
1036  return SCIP_OKAY;
1037 }
1038
1039
1040
1041
1042 /** builds new rooted SAP graph for prize-collecting problems (with given root for SAP) */
1044  SCIP* scip, /**< SCIP data structure */
1045  GRAPH* graph, /**< the graph */
1046  GRAPH** newgraph, /**< the new graph */
1047  const int* rootcands, /**< array containing all vertices that could be used as root */
1048  int nrootcands, /**< number of all vertices that could be used as root */
1049  int saproot /**< the root of the new SAP */
1050  )
1051 {
1052  GRAPH* p;
1053  int twinterm;
1054  int nnodes;
1055  const int oldroot = graph->source;
1056  const int stp_type = graph->stp_type;
1057
1058  assert(scip && graph && graph->prize && rootcands);
1059  assert(graph->knots == graph->ksize);
1060  assert(graph->edges == graph->esize);
1061  assert(graph_pc_isPcMw(graph) && !graph_pc_isRootedPcMw(graph));
1062
1063  graph_pc_2transcheck(scip, graph);
1064
1065  assert(Is_pseudoTerm(graph->term[saproot]));
1066
1067  /* copy graph to obtain an SAP */
1068  graph->stp_type = STP_SAP;
1069  SCIP_CALL( graph_copy(scip, graph, newgraph) );
1070  graph->stp_type = stp_type;
1071
1072  p = *newgraph;
1073  twinterm = -1;
1074
1075  for( int e = p->outbeg[saproot]; e != EAT_LAST; e = p->oeat[e] )
1076  {
1077  const int head = p->head[e];
1078  if( Is_term(p->term[head]) && head != oldroot )
1079  {
1080  graph_knot_chg(p, head, STP_TERM_NONE);
1081  twinterm = head;
1082  graph_edge_del(scip, p, e, FALSE);
1083  break;
1084  }
1085  }
1086
1087  assert(twinterm >= 0);
1088
1089  SCIP_CALL( graph_pc_presolInit(scip, p) );
1090
1091  for( int e = graph->outbeg[oldroot]; e != EAT_LAST; e = graph->oeat[e] )
1092  {
1093  const int head = graph->head[e];
1094
1095  assert(graph->head[e] == p->head[e]);
1096  assert(graph->tail[e] == p->tail[e]);
1097
1098  if( Is_term(graph->term[head]) && head != twinterm )
1099  {
1100  assert(Is_term(p->term[head]));
1101
1102  (void) graph_edge_redirect(scip, p, e, saproot, head, graph->cost[e], TRUE, FALSE);
1103  p->cost[flipedge(e)] = FARAWAY;
1104
1105 #ifndef NDEBUG
1106  assert(p->grad[head] == 2);
1107  for( int e2 = p->outbeg[head]; e2 != EAT_LAST; e2 = p->oeat[e2] )
1108  assert(p->head[e2] == saproot || Is_pseudoTerm(p->term[p->head[e2]]));
1109 #endif
1110  }
1111  else
1112  {
1113  graph_edge_del(scip, p, e, FALSE);
1114  }
1115  }
1116
1117  assert(p->grad[twinterm] == 0 && p->grad[oldroot] == 0);
1118
1119  graph_pc_presolExit(scip, p);
1120
1121  nnodes = p->knots;
1122  p->source = saproot;
1123  graph_knot_chg(p, saproot, STP_TERM);
1124
1125  for( int k = 0; k < nnodes; k++ )
1126  p->mark[k] = (p->grad[k] > 0);
1127
1128  SCIP_CALL( graph_pc_initPrizes(scip, p, nnodes) );
1129  SCIP_CALL( graph_pc_initTerm2Edge(scip, p, nnodes) );
1130
1131  for( int k = 0; k < nnodes; k++)
1132  {
1133  p->term2edge[k] = graph->term2edge[k];
1134  if( k < graph->norgmodelknots )
1135  p->prize[k] = graph->prize[k];
1136  else
1137  p->prize[k] = 0.0;
1138  }
1139
1140  p->term2edge[saproot] = TERM2EDGE_FIXEDTERM;
1141  p->term2edge[twinterm] = TERM2EDGE_NOTERM;
1142
1143  assert(p->stp_type == STP_SAP);
1144
1145  if( nrootcands > 0 )
1146  {
1147  SCIP_CALL( graph_pc_presolInit(scip, p) );
1148  for( int k = 0; k < nrootcands; k++ )
1149  {
1150  int e;
1151  int head = -1;
1152  const int rootcand = rootcands[k];
1153
1154  if( rootcand == saproot )
1155  continue;
1156
1157  assert(Is_pseudoTerm(p->term[rootcand]));
1158
1159  for( e = p->outbeg[rootcand]; e != EAT_LAST; e = p->oeat[e] )
1160  {
1161  head = p->head[e];
1162
1163  if( Is_term(p->term[head]) && p->term2edge[head] >= 0 )
1164  {
1165  assert(p->grad[head] == 2 && head != saproot);
1166
1167  graph_knot_chg(p, head, STP_TERM_NONE);
1168  p->term2edge[head] = TERM2EDGE_NOTERM;
1169  graph_knot_del(scip, p, head, FALSE);
1170  break;
1171  }
1172  }
1173  assert(e != EAT_LAST && head >= 0);
1174
1175  graph_pc_knotToFixedTermProperty(p, rootcand);
1176  }
1177  graph_pc_presolExit(scip, p);
1178  }
1179
1180  graph_knot_chg(p, oldroot, STP_TERM_NONE);
1181  p->prize[saproot] = 0.0;
1182
1183  return SCIP_OKAY;
1184 }
1185
1186
1187 /** is a transformation stable? */
1189  const GRAPH* graph, /**< the graph */
1190  SCIP_Real primalbound /**< primal bound for graph */
1191
1192  )
1193 {
1194  SCIP_Real prizesum = 1.0;
1195  const int nnodes = graph_get_nNodes(graph);
1196
1197  assert(graph->stp_type == STP_RPCSPG);
1198  assert(graph->prize);
1199  assert(GE(primalbound, 0.0));
1200
1201  if( GT(primalbound, TRANS_MAXPRIZESUM) )
1202  return FALSE;
1203
1204  for( int k = 0; k < nnodes; k++ )
1205  {
1206  if( GT(graph->prize[k], 0.0) && LT(graph->prize[k], FARAWAY) )
1207  {
1208  prizesum += graph->prize[k];
1209  }
1210  }
1211
1212  return (LE(prizesum, TRANS_MAXPRIZESUM));
1213 }
1214
1215
1216 /** constructs equivalent SPG for given RPC */
1218  SCIP* scip, /**< SCIP data structure */
1219  const GRAPH* graph, /**< the graph */
1220  SCIP_Real primalbound, /**< primal bound for graph */
1221  SCIP_Real* offset, /**< offset (in/out) */
1222  int** edgemap_new2org, /**< maps edges */
1223  GRAPH** newgraph /**< the new graph */
1224  )
1225 {
1226  GRAPH* graph_new;
1227  int* nodes_org2new;
1228  int* edges_new2org;
1229  int termscount;
1230  const int nnodes_org = graph_get_nNodes(graph);
1231  int firstdummy = 0;
1232  int nnodes_new = 0;
1233  int nedges_new = 0;
1234  int ndummyterms = 0;
1235  SCIP_Real prizesum;
1236
1237  assert(scip && offset);
1238  assert(graph && graph->prize);
1239  assert(graph_transRpcToSpgIsStable(graph, primalbound));
1240  assert(!graph->extended);
1241  assert(graph_isMarked(graph));
1242
1243  prizesum = 1.0;
1244  for( int k = 0; k < nnodes_org; k++ )
1245  {
1246  nedges_new += graph->grad[k];
1247
1248  if( !graph->mark[k] )
1249  continue;
1250
1251  nnodes_new++;
1252
1253  if( graph_pc_knotIsNonLeafTerm(graph, k) )
1254  {
1255  assert(GT(graph->prize[k], 0.0) && LT(graph->prize[k], FARAWAY));
1256
1257  /* NOTE: dummy edges and terminals for non-proper potential terminals are counted here */
1258  nedges_new += 4;
1259  }
1260
1261  if( GT(graph->prize[k], 0.0) && LT(graph->prize[k], FARAWAY) )
1262  {
1263  assert(Is_term(graph->term[k]));
1264
1265  prizesum += graph->prize[k];
1266  ndummyterms++;
1267  nnodes_new++;
1268  }
1269  }
1270
1271  SCIP_CALL( SCIPallocMemoryArray(scip, &nodes_org2new, nnodes_org) );
1272  SCIP_CALL( SCIPallocMemoryArray(scip, edgemap_new2org, nedges_new) );
1273  edges_new2org = *edgemap_new2org;
1274
1275  assert(ndummyterms == graph_pc_nProperPotentialTerms(graph) + graph_pc_nNonLeafTerms(graph));
1276
1277  prizesum = MAX(prizesum, primalbound);
1278  prizesum = floor(prizesum);
1279
1280  SCIPdebugMessage("prizesum=%f \n", prizesum);
1281  assert(LT(prizesum, BLOCKED));
1282
1283  *offset -= prizesum * (ndummyterms);
1284
1285  SCIPdebugMessage("fixed=%f \n", prizesum * ndummyterms);
1286  SCIPdebugMessage("number of dummy terminals: %d \n", ndummyterms);
1287
1288  SCIP_CALL( graph_init(scip, newgraph, nnodes_new, nedges_new, 1) );
1289  graph_new = *newgraph;
1290
1291  /* add nodes */
1292  for( int k = 0; k < nnodes_org; ++k )
1293  {
1294  if( !graph->mark[k] )
1295  {
1296  nodes_org2new[k] = -1;
1297  continue;
1298  }
1299
1300  nodes_org2new[k] = graph_new->knots;
1301
1302  if( graph_pc_knotIsFixedTerm(graph, k) )
1303  graph_knot_add(graph_new, STP_TERM);
1304  else
1305  graph_knot_add(graph_new, STP_TERM_NONE);
1306  }
1307
1308  firstdummy = graph_new->knots;
1309
1310  for( int k = 0; k < ndummyterms; k++ )
1311  graph_knot_add(graph_new, STP_TERM);
1312
1313  graph_new->source = nodes_org2new[graph->source];
1314  assert(graph_knot_isInRange(graph_new, graph_new->source));
1315
1316  /* add default edges */
1317  for( int k = 0; k < nnodes_org; ++k )
1318  {
1319  if( !graph->mark[k] )
1320  continue;
1321
1322  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
1323  {
1324  const int head = graph->head[e];
1325
1326  if( head < k || !graph->mark[head] )
1327  continue;
1328
1329  assert(EQ(graph->cost[e], graph->cost[flipedge(e)]));
1330  assert(graph_knot_isInRange(graph_new, nodes_org2new[k]));
1331  assert(graph_knot_isInRange(graph_new, nodes_org2new[head]));
1332
1333  edges_new2org[graph_new->edges] = e;
1334  edges_new2org[graph_new->edges + 1] = flipedge(e);
1335  graph_edge_addBi(scip, graph_new, nodes_org2new[k], nodes_org2new[head], graph->cost[e]);
1336  }
1337  }
1338
1339  /* add dummy edges */
1340  termscount = 0;
1341  for( int k = 0; k < nnodes_org; ++k )
1342  {
1343  if( GT(graph->prize[k], 0.0) && LT(graph->prize[k], FARAWAY) )
1344  {
1345  /* the future terminal */
1346  const int oldterm = nodes_org2new[k];
1347  const int newterm = firstdummy + termscount;
1348  termscount++;
1349
1350  assert(graph_knot_isInRange(graph_new, oldterm));
1351  assert(graph_knot_isInRange(graph_new, newterm));
1352  assert(Is_term(graph_new->term[newterm]));
1353  assert(graph_new->grad[newterm] == 0);
1354
1355 #ifdef SCIP_DEBUG
1356  SCIPdebugMessage("adding dummy terminal for original node %d: \n", k);
1357  graph_knot_printInfo(graph, k);
1358 #endif
1359
1360  for( int j = 0 ; j < 4; j++ )
1361  edges_new2org[graph_new->edges + j] = -1;
1362
1363  graph_edge_addBi(scip, graph_new, graph_new->source, newterm, prizesum + graph->prize[k]);
1364  graph_edge_addBi(scip, graph_new, oldterm, newterm, prizesum);
1365  }
1366  }
1367
1368  SCIPfreeMemoryArray(scip, &(nodes_org2new));
1369
1370  assert(nedges_new == graph_new->edges);
1371  assert(termscount == ndummyterms);
1372  graph_new->stp_type = STP_SPG;
1373
1374  return SCIP_OKAY;
1375 }
1376
1377
1378 /** cleans up GSTP after transformation
1379  * todo also compute a better big M than just the trivial one, e.g. by building an SAP and computing bound
1380  * todo move the whole transformation here from graph_load, quite hacky at the moment */
1382  PRESOL* presol, /**< presolving struct */
1383  GRAPH* graph /**< the graph */
1384  )
1385 {
1386  SCIP_Real costsum = 0.0;
1387  const int nedges = graph_get_nEdges(graph);
1388
1389  assert(presol);
1390  assert(graph->stp_type == STP_GSTP);
1391
1392  for( int e = 0; e < nedges; e += 2 )
1393  {
1394  assert(LE(graph->cost[e], BLOCKED));
1395
1396  if( !EQ(graph->cost[e], BLOCKED) )
1397  costsum += graph->cost[e];
1398  }
1399
1400  presol->fixed -= (costsum * graph->terms);
1401
1402  for( int e = 0; e < nedges; e += 2 )
1403  {
1404  if( EQ(graph->cost[e], BLOCKED) )
1405  {
1406  assert(EQ(graph->cost[e + 1], BLOCKED));
1407  assert(Is_term(graph->term[graph->tail[e]]) || Is_term(graph->term[graph->head[e]]));
1408
1409  graph->cost[e] = costsum;
1410  graph->cost[e + 1] = costsum;
1411  }
1412  }
1413
1414  graph->norgmodelknots = graph->knots - graph->terms;
1415  graph->norgmodelterms = graph->terms;
1416 }
1417
1418
1419 /** alters the graph for node-weighted Steiner tree problems */
1421  SCIP* scip, /**< SCIP data structure */
1422  PRESOL* presol, /**< presolving struct */
1423  GRAPH* g /**< the graph */
1424  )
1425 {
1426  SCIP_Real maxweight = 0.0;
1427  const int nnodes = graph_get_nNodes(g);
1428  const int nedges = graph_get_nEdges(g);
1429  const int nterms_org = g->terms;
1430
1431  assert(scip && presol);
1432  assert(g->prize);
1433
1434  for( int k = 0; k < nnodes; k++ )
1435  {
1436  if( maxweight < g->prize[k] )
1437  maxweight = g->prize[k];
1438  }
1439
1440  assert(LT(maxweight, BLOCKED));
1441
1442  for( int k = 0; k < nnodes; k++ )
1443  {
1444  if( Is_term(g->term[k]) )
1445  {
1446  presol->fixed += g->prize[k];
1447  g->prize[k] = FARAWAY;
1448  g->source = k;
1449  }
1450  else
1451  {
1452  g->prize[k] = maxweight - g->prize[k];
1453
1454  assert(GE(g->prize[k], 0.0));
1455
1456  if( GT(g->prize[k], 0.0) )
1457  graph_knot_chg(g, k, STP_TERM);
1458  }
1459  }
1460
1461  SCIPdebugMessage("maxweight=%f \n", maxweight);
1462
1463  for( int e = 0; e < nedges; e++ )
1464  {
1465  g->cost[e] += maxweight;
1466  }
1467
1468  assert(nterms_org >= 1);
1469
1470  presol->fixed -= (nterms_org - 1) * maxweight;
1471
1472  for( int k = 0; k < nnodes; k++ )
1473  {
1474  if( !EQ(g->prize[k], FARAWAY) )
1475  presol->fixed -= g->prize[k];
1476  }
1477
1478  SCIPdebugMessage("presol->fixed=%f \n", presol->fixed);
1479
1480  SCIP_CALL( graph_transRpc(scip, g) );
1481
1482  return SCIP_OKAY;
1483 }
1484
1485
1486 /** alters the graph for node-weighted Steiner tree problems */
1488  SCIP* scip, /**< SCIP data structure */
1489  PRESOL* presol, /**< presolving struct */
1490  GRAPH* g /**< the graph */
1491  )
1492 {
1493  const int nnodes = graph_get_nNodes(g);
1494
1495  assert(scip && presol);
1496  assert(g->prize);
1497
1498  for( int k = 0; k < nnodes; k++ )
1499  {
1500  const SCIP_Real nodeweight = g->prize[k];
1501
1502  if( Is_term(g->term[k]) )
1503  {
1504  presol->fixed += nodeweight;
1505  }
1506  else
1507  {
1508  /* add node-weight to edge-weights of all incoming edges */
1509  for( int i = g->inpbeg[k]; i != EAT_LAST; i = g->ieat[i] )
1510  g->cost[i] += nodeweight;
1511  }
1512  }
1513
1514  return SCIP_OKAY;
1515 }
1516
1517
1518 /** alters the graph for node-weighted Steiner tree problems */
1520  SCIP* scip, /**< SCIP data structure */
1521  PRESOL* presol, /**< presolving struct */
1522  GRAPH* g /**< the graph */
1523  )
1524 {
1525 #ifdef NW_TRANS_SIMPLE
1526  SCIP_CALL( graph_transNw2sap(scip, presol, g) );
1527 #else
1528  if( g->stp_type == STP_NWPTSPG )
1529  {
1530  SCIP_CALL( graph_transNw2sap(scip, presol, g) );
1531  assert(g->stp_type == STP_NWPTSPG);
1532
1533  nwptstpSetRoot(g);
1534  }
1535  else
1536  {
1537  SCIP_CALL( graph_transNw2pc(scip, presol, g) );
1538  }
1539 #endif
1540
1541  return SCIP_OKAY;
1542 }
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
static volatile int nterms
Definition: interrupt.c:38
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
SCIP_RETCODE graph_transMw(SCIP *scip, GRAPH *graph)
Definition: graph_trans.c:632
int source
Definition: graphdefs.h:195
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
#define Is_term(a)
Definition: graphdefs.h:102
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
void graph_edge_addBi(SCIP *, GRAPH *, int, int, double)
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
SCIP_RETCODE graph_pc_presolInit(SCIP *, GRAPH *)
Definition: graph_pcbase.c:815
int terms
Definition: graphdefs.h:192
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int norgmodeledges
Definition: graphdefs.h:215
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 TERM2EDGE_NONLEAFTERM
Definition: graphdefs.h:74
#define TERM2EDGE_NOTERM
Definition: graphdefs.h:72
#define FALSE
Definition: def.h:87
int *RESTRICT inpbeg
Definition: graphdefs.h:202
static SCIP_Bool isNonLeaf_pretransPc(SCIP *scip, const GRAPH *g, int vertex)
Definition: graph_trans.c:61
#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
#define STP_SAP
Definition: graphdefs.h:43
SCIP_RETCODE graph_transPcmw2rooted(SCIP *scip, GRAPH *graph, SCIP_Real fixprize, SCIP_Bool verbose)
Definition: graph_trans.c:809
static SCIP_RETCODE initCostOrgPc(SCIP *scip, GRAPH *g)
Definition: graph_trans.c:40
#define EAT_LAST
Definition: graphdefs.h:58
#define STP_SPG
Definition: graphdefs.h:42
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Real graph_pc_getNonLeafTermOffset(SCIP *, const GRAPH *)
SCIP_Real * costbudget
Definition: graphdefs.h:211
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void markNonLeafTerms_pretransPc(SCIP *scip, GRAPH *g)
Definition: graph_trans.c:84
#define Is_nonleafTerm(a)
Definition: graphdefs.h:104
SCIP_Real * cost_org_pc
Definition: graphdefs.h:222
SCIP_RETCODE graph_resize(SCIP *, GRAPH *, int, int, int)
Definition: graph_base.c:744
#define STP_TERM_NONE
Definition: graphdefs.h:62
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_RETCODE graph_pc_initPrizes(SCIP *, GRAPH *, int)
Definition: graph_pcbase.c:741
SCIP_RETCODE graph_transRpc2SpgTrivial(SCIP *scip, GRAPH *g)
Definition: graph_trans.c:505
SCIP_Bool graph_knotIsNWLeaf(const GRAPH *, int)
Definition: graph_node.c:35
#define TRANS_MAXPRIZESUM
Definition: graph_trans.c:35
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_RETCODE graph_pc_initTerm2Edge(SCIP *, GRAPH *, int)
Definition: graph_pcbase.c:721
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void graph_pc_shiftNonLeafCosts(SCIP *, GRAPH *)
Definition: graph_pcbase.c:671
void graph_pc_2transcheck(SCIP *, GRAPH *)
SCIP_RETCODE graph_transPc2Spg(SCIP *scip, PRESOL *presol, GRAPH *graph)
Definition: graph_trans.c:257
SCIP_Real * prize
Definition: graphdefs.h:210
#define TERM2EDGE_FIXEDTERM
Definition: graphdefs.h:73
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
SCIP_RETCODE graph_transPcGetSap(SCIP *scip, GRAPH *graph, GRAPH **newgraph, SCIP_Real *offset)
Definition: graph_trans.c:931
int *RESTRICT grad
Definition: graphdefs.h:201
SCIP_RETCODE graph_transNw2pc(SCIP *scip, PRESOL *presol, GRAPH *g)
Definition: graph_trans.c:1420
void graph_pc_knotToFixedTermProperty(GRAPH *, int)
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
#define NULL
Definition: lpi_spx1.cpp:155
void graph_pc_knotToNonTermProperty(GRAPH *, int)
#define STP_RMWCSP
Definition: graphdefs.h:54
#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
int * term2edge
Definition: graphdefs.h:208
#define STP_PCSPG
Definition: graphdefs.h:44
#define LT(a, b)
Definition: portab.h:81
SCIP_RETCODE graph_transNw(SCIP *scip, PRESOL *presol, GRAPH *g)
Definition: graph_trans.c:1519
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
#define STP_TERM_NONLEAF
Definition: graphdefs.h:64
int *RESTRICT ieat
Definition: graphdefs.h:230
#define STP_NWPTSPG
Definition: graphdefs.h:48
SCIP_Bool graph_isMarked(const GRAPH *)
Definition: graph_base.c:1165
int *RESTRICT tail
Definition: graphdefs.h:223
SCIP_RETCODE graph_transRmw(SCIP *scip, GRAPH *graph)
Definition: graph_trans.c:687
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
#define STP_TERM
Definition: graphdefs.h:61
int graph_pc_nProperPotentialTerms(const GRAPH *)
SCIP_RETCODE graph_transPcGetRsap(SCIP *scip, GRAPH *graph, GRAPH **newgraph, const int *rootcands, int nrootcands, int saproot)
Definition: graph_trans.c:1043
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
SCIP_Bool graph_pc_isPc(const GRAPH *)
Portable definitions.
int graph_pc_nNonLeafTerms(const GRAPH *)
SCIP_RETCODE graph_transNw2sap(SCIP *scip, PRESOL *presol, GRAPH *g)
Definition: graph_trans.c:1487
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void graph_transGstpClean(PRESOL *presol, GRAPH *graph)
Definition: graph_trans.c:1381
void graph_pc_2orgcheck(SCIP *, GRAPH *)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
#define STP_TERM_PSEUDO
Definition: graphdefs.h:63
int *RESTRICT rootedgeprevs
Definition: graphdefs.h:227
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
#define SCIP_Real
Definition: def.h:177
#define BLOCKED
Definition: graphdefs.h:90
int esize
Definition: graphdefs.h:218
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_RETCODE graph_transRpc2FixedProper(SCIP *scip, PRESOL *presol, GRAPH *graph)
Definition: graph_trans.c:531
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: graph_base.c:939
SCIP_RETCODE graph_transRpcGetSpg(SCIP *scip, const GRAPH *graph, SCIP_Real primalbound, SCIP_Real *offset, int **edgemap_new2org, GRAPH **newgraph)
Definition: graph_trans.c:1217
int edges
Definition: graphdefs.h:219
SCIP_Bool graph_transRpcToSpgIsStable(const GRAPH *graph, SCIP_Real primalbound)
Definition: graph_trans.c:1188
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define STP_GSTP
Definition: graphdefs.h:53
SCIP_Real fixed
Definition: graphdefs.h:276
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
static void nwptstpSetRoot(GRAPH *g)
Definition: graph_trans.c:106
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int ksize
Definition: graphdefs.h:189
SCIP_RETCODE graph_transPc(SCIP *scip, GRAPH *graph)
Definition: graph_trans.c:154
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 graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
int norgmodelterms
Definition: graphdefs.h:188
SCIP_RETCODE graph_transRpc(SCIP *scip, GRAPH *graph)
Definition: graph_trans.c:373
#define STP_RPCSPG
Definition: graphdefs.h:45
#define STP_MWCSP
Definition: graphdefs.h:51
void graph_pc_presolExit(SCIP *, GRAPH *)
Definition: graph_pcbase.c:858
int graph_pc_getTwinTerm(const GRAPH *, int)
int norgmodelknots
Definition: graphdefs.h:187
int orgsource
Definition: graphdefs.h:194