Scippy

SCIP

Solving Constraint Integer Programs

probdata_stp.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-2020 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 probdata_stp.c
17  * @brief Problem data for Steiner problems
18  * @author Gerald Gamrath
19  * @author Thorsten Koch
20  * @author Michael Winkler
21  * @author Daniel Rehfeldt
22  *
23  * This file implements the problem data for Steiner problems. For more details see \ref STP_PROBLEMDATA page.
24  *
25  * @page STP_PROBLEMDATA Main problem data
26  *
27  * The problem data is accessible in all plugins.
28  *
29  * The problem data contains the (preprocessed) graph, several constraints and further information.
30  *
31  * The function SCIPprobdataCreate(), which is called in the \ref reader_stp.c "reader plugin", parses the input file
32  * reduces the graph, initializes the problem data structure and creates the problem in the SCIP environment.
33  * See the body of the function SCIPprobdataCreate() for more details.
34  *
35  * A list of all interface methods can be found in probdata_stp.h.
36  */
37 
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39 
40 #include <string.h>
41 #include "probdata_stp.h"
42 #include <stdio.h>
43 #include "scip/scip.h"
44 #include "cons_stp.h"
45 #include "grph.h"
46 #include "scip/cons_linear.h"
47 #include "scip/cons_setppc.h"
48 #include "scip/misc.h"
49 #include "scip/struct_misc.h"
50 #include "branch_stp.h"
51 
52 
53 #define STP_AGG_SYM
54 #define CENTER_OK 0 /**< do nothing */
55 #define CENTER_DEG 1 /**< find maximum degree */
56 #define CENTER_SUM 2 /**< find the minimum distance sum */
57 #define CENTER_MIN 3 /**< find the minimum largest distance */
58 #define CENTER_ALL 4 /**< find the minimum distance sum to all knots */
59 
60 #define MODE_CUT 0 /**< branch and cut */
61 #define MODE_FLOW 1 /**< use flow model */
62 #define MODE_PRICE 2 /**< branch and price */
63 
64 #define CONS_ALWAYS 1 /**< always use (respective) constraints */
65 #define CONS_SPECIFIC 2 /**< use (respective) constraints depending on the problem instance */
66 
67 #define FLOWB FALSE
68 #define USEOFFSETVAR TRUE
69 
70 #define SYM_CONS_LIMIT 20000 /**< maximum number of symmetry inequalities for MWCSP and PCSPG */
71 #define CYC_CONS_LIMIT 15000 /**< maximum number of symmetry inequalities for PCSPG */
72 
73 #define CUT_MAXNTERMINALS 500
74 #define CUT_MAXNEDGES 10000
75 #define CUT_MAXTOTNEDGES 50000
76 
77 
78 
79 #ifdef WITH_UG
80 const char*
81 getBranchLinearConsName(const char* names, int i);
82 
83 const char*
84 getBranchSetppcConsName(const char* names, int i);
85 #endif
86 
87 
88 /** @brief Problem data which is accessible in all places
89  *
90  * This problem data is used to store the graph of the Steiner tree problem
91  */
92 struct SCIP_ProbData
93 {
94  int mode; /**< solving mode selected by the user (Cut, Price, Flow) */
95  SCIP_Bool bigt; /**< stores whether the 'T' model is being used (not relevant in Cut mode) */
96  GRAPH* graph; /**< the graph */
97 #ifdef WITH_UG
98  GRAPH* orggraph; /**< copy of presolved graph needed for UG */
99 #endif
100  SCIP_CONS** degcons; /**< array of (node) degree constraints */
101  SCIP_CONS** edgecons; /**< array of constraints */
102  SCIP_CONS** pathcons; /**< array of path constraints (needed only in the Price mode) */
103 #if FLOWB
104  SCIP_CONS** flowbcons; /**< flow balance constraints */
105 #endif
106  SCIP_CONS** prizesymcons; /**< prize-collecting symmetry constraints (to improve LP) */
107  SCIP_CONS** prizecyclecons; /**< prize-collecting cycle constraints (to improve LP) */
108  SCIP_CONS* hopcons; /**< hop constraint */
109  SCIP_CONS* prizecons; /**< prize constraint */
110  SCIP_VAR** edgevars; /**< array of edge variables */
111  SCIP_VAR** flowvars; /**< array of edge variables (needed only in the Flow mode) */
112 #if USEOFFSETVAR
113  SCIP_VAR* offsetvar; /**< variable to model the objective offset */
114 #endif
115  SCIP_Real offset; /**< offset of the problem, computed during the presolving */
116  SCIP_Real* xval; /**< values of the edge variables */
117  SCIP_Longint lastlpiters; /**< Branch and Cut */
118  int* realterms; /**< array of all terminals except the root */
119  int nedges; /**< number of edges */
120  int norgedges; /**< number of original edges of the model */
121  int nterms; /**< number of terminals */
122  int realnterms; /**< number of terminals except the root */
123  int nlayers; /**< number of layers */
124  int nnodes; /**< number of nodes */
125  int nnonterms; /**< number of nodes */
126  int nvars; /**< number of variables */
127  int stp_type; /**< Steiner problem type */
128  int minelims; /**< minimal number of eliminations per reduction method */
129  SCIP_Bool emitgraph; /**< emitgraph */
130  SCIP_Bool copy; /**< is this the problem data of a copy/sub-MIP? */
131  SCIP_Bool usecyclecons; /**< use 2-cycle inequalities for (R)PCSPG? */
132  SCIP_Bool usesymcons; /**< use symmetry inequalities for PCSPG and MWCSP? */
133  FILE* logfile; /**< logfile for DIMACS challenge */
134  FILE** origlogfile; /**< pointer to original problem data logfile pointer */
135  FILE* intlogfile; /**< logfile printing all intermediate solutions for DIMACS challenge */
136  FILE** origintlogfile; /**< pointer to original problem data intlogfile pointer */
137 
138  /** for FiberSCIP **/
139  SCIP_Bool ug; /**< indicates if this ug dual bound is set or not */
140  int nSolvers; /**< the number of solvers */
141  SCIP_Real ugDual; /**< dual bound set by ug */
142 };
143 
144 /**@name Local methods
145  *
146  * @{
147  */
148 
149 
150 static
151 void updateorgsol(
152  GRAPH* graph, /**< graph data structure */
153  IDX* curr, /**< head of solution edge list */
154  STP_Bool* orgnodes, /**< array to mark whether a node is part of the original solution */
155  STP_Bool* orgedges, /**< array to mark whether an edge is part of the original solution */
156  int* nsolnodes, /**< pointer to store the number of nodes in the original solution */
157  int* nsoledges /**< pointer to store the number of edges in the original solution */
158 )
159 {
160  int i;
161  int e = 0;
162  int k = 0;
163 
164  while( curr != NULL )
165  {
166  i = curr->index;
167 
168  if( orgedges[i] == FALSE )
169  {
170  orgedges[i] = TRUE;
171  e++;
172  }
173 
174  if( !(orgnodes[graph->orgtail[i]]) )
175  {
176  k++;
177  orgnodes[graph->orgtail[i]] = TRUE;;
178  }
179 
180  if( !(orgnodes[graph->orghead[i]]) )
181  {
182  k++;
183  orgnodes[graph->orghead[i]] = TRUE;
184  }
185 
186  curr = curr->parent;
187  }
188 
189  (*nsolnodes) += k;
190  (*nsoledges) += e;
191 }
192 
193 /*
194  * distinguishes a terminal as the root; with centertype
195  * = CENTER_OK : Do nothing
196  * = CENTER_DEG : find maximum degree
197  * = CENTER_SUM : find the minimum distance sum
198  * = CENTER_MIN : find the minimum largest distance
199  * = CENTER_ALL : find the minimum distance sum to all knots
200  */
201 static
202 SCIP_RETCODE central_terminal(
203  SCIP* scip, /**< SCIP data structure */
204  GRAPH* g, /**< graph data structure */
205  int* central_term, /**< pointer to store the selected (terminal) vertex */
206  int centertype /**< type of root selection */
207  )
208 {
209  PATH* path;
210  double* cost;
211  int i;
212  int k;
213  int center = -1;
214  int degree = 0;
215  double sum;
216  double max;
217  double minimum = FARAWAY;
218  double maximum = 0.0;
219  double oldval = 0.0;
220 
221  assert(g != NULL);
222  assert(g->layers == 1);
223 
224  *central_term = g->source;
225 
226  if( centertype == CENTER_OK )
227  return SCIP_OKAY;
228 
229  /* Find knot of maximum degree.
230  */
231  if( centertype == CENTER_DEG )
232  {
233  degree = 0;
234 
235  for( i = 0; i < g->knots; i++ )
236  {
237  if( Is_term(g->term[i]) && (g->grad[i] > degree) )
238  {
239  degree = g->grad[i];
240  center = i;
241  }
242  }
243  assert(degree > 0);
244  *central_term = center;
245  return SCIP_OKAY;
246  }
247 
248  /* For the other methods we need the shortest paths */
249  SCIP_CALL( SCIPallocBufferArray(scip, &path, g->knots) );
250  SCIP_CALL( SCIPallocBufferArray(scip, &cost, g->edges) );
251 
252  assert(path != NULL);
253  assert(cost != NULL);
254 
255  for( i = 0; i < g->knots; i++ )
256  g->mark[i] = TRUE;
257 
258  for( i = 0; i < g->edges; i++ )
259  cost[i] = 1.0;
260 
261  for( i = 0; i < g->knots; i++ )
262  {
263  if (!Is_term(g->term[i]))
264  continue;
265 
266  graph_path_exec(scip, g, FSP_MODE, i, cost, path);
267 
268  sum = 0.0;
269  max = 0.0;
270 
271  for( k = 0; k < g->knots; k++ )
272  {
273  assert((path[k].edge >= 0) || (k == i));
274  assert((path[k].edge >= 0) || (path[k].dist == 0));
275 
276  if( Is_term(g->term[k]) || (centertype == CENTER_ALL) )
277  {
278  sum += path[k].dist;
279 
280  if( path[k].dist > max )
281  max = path[k].dist;
282  }
283  }
284 
285  if( (centertype == CENTER_SUM) || (centertype == CENTER_ALL) )
286  {
287  if( sum < minimum )
288  {
289  minimum = sum;
290  center = i;
291  }
292  if( sum > maximum )
293  maximum = sum;
294 
295  if( i == g->source )
296  oldval = sum;
297  }
298  else
299  {
300  assert(centertype == CENTER_MIN);
301 
302  /* If the maximum distance to terminal ist shorter or if
303  * it is of the same length but the degree of the knot is
304  * higher, we change the center.
305  */
306  if( SCIPisLT(scip, max, minimum) || (SCIPisEQ(scip, max, minimum) && (g->grad[i] > degree)) )
307  {
308  minimum = max;
309  center = i;
310  degree = g->grad[i];
311  }
312  if( max > maximum )
313  maximum = max;
314 
315  if( i == g->source )
316  oldval = max;
317  }
318  }
319  assert(center >= 0);
320  assert(Is_term(g->term[center]));
321 
322  SCIPfreeBufferArray(scip, &cost);
323  SCIPfreeBufferArray(scip, &path);
324 
325  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Central Terminal is %d (min=%g, max=%g, old=%g)\n",
326  center, minimum, maximum, oldval);
327 
328  *central_term = center;
329  return SCIP_OKAY;
330 }
331 
332 /** creates problem data */
333 static
334 SCIP_RETCODE probdataCreate(
335  SCIP* scip, /**< SCIP data structure */
336  SCIP_PROBDATA** probdata, /**< pointer to problem data */
337  GRAPH* graph /**< graph data structure */
338  )
339 {
340  assert(scip != NULL);
341  assert(probdata != NULL);
342 
343  /* allocate memory */
344  SCIP_CALL( SCIPallocMemory(scip, probdata) );
345 
346  (*probdata)->graph = graph;
347  (*probdata)->xval = NULL;
348  (*probdata)->lastlpiters = -1;
349  if( graph != NULL )
350  (*probdata)->stp_type = graph->stp_type;
351  else
352  (*probdata)->stp_type = STP_SPG;
353  (*probdata)->copy = FALSE;
354  (*probdata)->logfile = NULL;
355  (*probdata)->origlogfile = NULL;
356  (*probdata)->intlogfile = NULL;
357  (*probdata)->origintlogfile = NULL;
358 
359  (*probdata)->ug = FALSE;
360  (*probdata)->nSolvers = 0;
361  (*probdata)->ugDual = 0.0;
362 
363  return SCIP_OKAY;
364 }
365 
366 /** frees the memory of the given problem data */
367 static
368 SCIP_RETCODE probdataFree(
369  SCIP* scip, /**< SCIP data structure */
370  SCIP_PROBDATA** probdata /**< pointer to problem data */
371  )
372 {
373  int e;
374  int t;
375  SCIPdebugMessage("probdataFree \n");
376  assert(scip != NULL);
377  assert(probdata != NULL);
378 
379  /* release variables */
380  for( e = 0; e < (*probdata)->nvars; ++e )
381  {
382  SCIP_CALL( SCIPreleaseVar(scip, &(*probdata)->edgevars[e]) );
383  }
384  SCIPfreeMemoryArrayNull(scip, &(*probdata)->edgevars);
385 
386 #if USEOFFSETVAR
387  if( (*probdata)->offsetvar != NULL )
388  {
389  SCIP_CALL( SCIPreleaseVar(scip, &(*probdata)->offsetvar) );
390  }
391 #endif
392  /* Degree-Constrained STP? */
393  if( (*probdata)->stp_type == STP_DCSTP )
394  {
395  assert((*probdata)->mode == MODE_CUT);
396 
397  /* release degree constraints */
398  for( t = 0; t < (*probdata)->nnodes; ++t)
399  {
400  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->degcons[t])) );
401  }
402  SCIPfreeMemoryArrayNull(scip, &((*probdata)->degcons));
403  }
404 
405  /* PC variant STP? */
406  if( (*probdata)->stp_type == STP_PCSPG || (*probdata)->stp_type == STP_RPCSPG || (*probdata)->stp_type == STP_MWCSP )
407  {
408  assert((*probdata)->mode == MODE_CUT);
409 #if FLOWB
410  for( e = 0; e < (*probdata)->nnonterms; e++ )
411  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->flowbcons[e])) );
412 
413  SCIPfreeMemoryArrayNull(scip, &((*probdata)->flowbcons));
414 #endif
415 
416  if( (*probdata)->usecyclecons && (*probdata)->stp_type == STP_PCSPG )
417  {
418  /* release degree constraints */
419  for( e = 0; e < (*probdata)->nedges; e++ )
420  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->prizecyclecons[e])) );
421 
422  SCIPfreeMemoryArrayNull(scip, &((*probdata)->prizecyclecons));
423  }
424 
425  if( (*probdata)->stp_type != STP_RPCSPG )
426  {
427  if( (*probdata)->usesymcons )
428  {
429 #ifdef STP_AGG_SYM
430  e = (*probdata)->realnterms - 1;
431  for( t = 0; t < e; ++t )
432  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->prizesymcons[t])) );
433 #else
434  e = (((*probdata)->realnterms - 1) * (*probdata)->realnterms) / 2;
435  for( t = 0; t < e; ++t )
436  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->prizesymcons[t])) );
437 #endif
438 
439  SCIPfreeMemoryArrayNull(scip, &((*probdata)->prizesymcons));
440  }
441  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->prizecons)) );
442  }
443  }
444 
445  /* release path constraints */
446  if( (*probdata)->mode == MODE_PRICE )
447  {
448  for( t = 0; t < (*probdata)->realnterms; ++t )
449  {
450  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->pathcons[t])) );
451  }
452  }
453  else if( (*probdata)->mode == MODE_FLOW )
454  {
455  for( t = 0; t < (*probdata)->realnterms; ++t )
456  {
457  /* release constraints and variables */
458  for( e = 0; e < (*probdata)->nnodes - 1; ++e )
459  {
460  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->pathcons[t * ((*probdata)->nnodes - 1 ) + e])) );
461  }
462  for( e = 0; e < (*probdata)->nedges; ++e )
463  {
464  SCIP_CALL( SCIPreleaseVar(scip, &(*probdata)->flowvars[t * (*probdata)->nedges + e]) );
465  }
466  if( (*probdata)->bigt )
467  break;
468  }
469  SCIPfreeMemoryArrayNull(scip, &(*probdata)->flowvars);
470  }
471  /* release edge constraints (Price or Flow) */
472  if( (*probdata)->mode != MODE_CUT )
473  {
474  for( t = 0; t < (*probdata)->realnterms; ++t )
475  {
476  for( e = 0; e < (*probdata)->nedges; ++e )
477  {
478  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->edgecons[t * (*probdata)->nedges + e])) );
479  }
480  if( (*probdata)->bigt )
481  break;
482 
483  }
484  SCIPfreeMemoryArrayNull(scip, &((*probdata)->edgecons));
485  SCIPfreeMemoryArrayNull(scip, &((*probdata)->pathcons));
486  }
487 
488  SCIPfreeMemoryArrayNull(scip, &(*probdata)->xval);
489  SCIPfreeMemoryArrayNull(scip, &(*probdata)->realterms);
490 
491  /* free probdata */
492  SCIPfreeMemory(scip, probdata);
493 
494  return SCIP_OKAY;
495 }
496 
497 /** print graph (in undirected form) in GML format */
498 static
499 SCIP_RETCODE probdataPrintGraph(
500  GRAPH* graph, /**< Graph to be printed */
501  const char* filename, /**< Name of the output file */
502  SCIP_Bool* edgemark /**< Array of (undirected) edges to highlight */
503  )
504 {
505  char label[SCIP_MAXSTRLEN];
506  FILE* file;
507  int e;
508  int n;
509  int m;
510 
511  assert(graph != NULL);
512  file = fopen((filename != NULL) ? filename : "stpgraph.gml", "w");
513 
514 #ifndef NDEBUG
515  for( e = 0; e < graph->edges; e += 2 )
516  {
517  assert(graph->tail[e] == graph->head[e + 1]);
518  assert(graph->tail[e + 1] == graph->head[e]);
519  }
520 #endif
521 
522  /* write GML format opening, undirected */
523  SCIPgmlWriteOpening(file, FALSE);
524 
525  /* write all nodes, discriminate between root, terminals and the other nodes */
526  e = 0;
527  m = 0;
528  for( n = 0; n < graph->knots; n++ )
529  {
530 
531  if( n == graph->source )
532  {
533  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Root", n);
534  SCIPgmlWriteNode(file, (unsigned int) n, label, "rectangle", "#666666", NULL);
535  m = 1;
536  }
537  else if( graph->term[n] == 0 )
538  {
539  (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Terminal %d", n, e + 1);
540  SCIPgmlWriteNode(file, (unsigned int) n, label, "circle", "#ff0000", NULL);
541  e += 1;
542  }
543  else
544  {
545  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Node %d", n, n + 1 - e - m);
546  SCIPgmlWriteNode(file, (unsigned int)n, label, "circle", "#336699", NULL);
547  }
548  }
549 
550  /* write all edges (undirected) */
551  for( e = 0; e < graph->edges; e += 2 )
552  {
553 
554  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "%8.2f", graph->cost[e]);
555 
556  if( edgemark != NULL && edgemark[e / 2] )
557  SCIPgmlWriteEdge(file, (unsigned int)graph->tail[e], (unsigned int)graph->head[e], label, "#ff0000");
558  else
559  SCIPgmlWriteEdge(file, (unsigned int)graph->tail[e], (unsigned int)graph->head[e], label, NULL);
560  }
561 
562  /* write GML format closing */
563  SCIPgmlWriteClosing(file);
564 
565  return SCIP_OKAY;
566 }
567 
568 /** create (edge-) HOP constraint (cut mode only) */
569 static
570 SCIP_RETCODE createHopConstraint(
571  SCIP* scip, /**< SCIP data structure */
572  SCIP_PROBDATA* probdata /**< problem data */
573  )
574 {
575  GRAPH* graph;
576  SCIP_Real rhs;
577  assert(scip != NULL);
578  assert(probdata != NULL);
579 
580  SCIPdebugMessage("createHopeConstraint \n");
581  graph = probdata->graph;
582  assert(graph != NULL);
583  rhs = graph->hoplimit;
584  SCIPdebugMessage("Hop limit: %f \n ", rhs);
585 
586  /* @todo with presolving contractions enabled one might set rhs = rhs - (number of fixed edges) */
587  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->hopcons), "HopConstraint", 0, NULL, NULL,
588  -SCIPinfinity(scip), rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
589 
590  SCIP_CALL( SCIPaddCons(scip, probdata->hopcons) );
591 
592  return SCIP_OKAY;
593 }
594 
595 
596 /** create (node-) degree constraints (cut mode only) */
597 static
598 SCIP_RETCODE createDegreeConstraints(
599  SCIP* scip, /**< SCIP data structure */
600  SCIP_PROBDATA* probdata /**< problem data */
601  )
602 
603 {
604  GRAPH* graph;
605  char consname[SCIP_MAXSTRLEN];
606  int k;
607  int nnodes;
608 
609  assert(scip != NULL);
610  assert(probdata != NULL);
611 
612  SCIPdebugMessage("createDegreeConstraints \n");
613  graph = probdata->graph;
614  nnodes = probdata->nnodes;
615 
616  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->degcons), nnodes ) );
617 
618  for( k = 0; k < nnodes; ++k )
619  {
620  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "DegreeConstraint%d", k);
621  SCIP_CALL( SCIPcreateConsLinear(scip, &(probdata->degcons[k]), consname, 0, NULL, NULL,
622  -SCIPinfinity(scip), (SCIP_Real)graph->maxdeg[k], TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
623 
624  SCIP_CALL( SCIPaddCons(scip, probdata->degcons[k]) );
625  }
626 
627  return SCIP_OKAY;
628 }
629 
630 
631 /** create Prize constraints (cut mode only) */
632 static
633 SCIP_RETCODE createPrizeConstraints(
634  SCIP* scip, /**< SCIP data structure */
635  SCIP_PROBDATA* probdata /**< problem data */
636  )
637 
638 {
639  GRAPH* graph;
640  int r;
641  int ro2;
642  int root;
643  int nedges;
644  int realnterms;
645  char consname[SCIP_MAXSTRLEN];
646 
647  assert(scip != NULL);
648  assert(probdata != NULL);
649 
650  graph = probdata->graph;
651  realnterms = probdata->realnterms;
652 
653  assert(graph != NULL);
654 
655  root = graph->source;
656  nedges = graph->edges;
657 
658  SCIPdebugMessage("createPrizeConstraints \n");
659 
660  if( probdata->usesymcons && graph->stp_type != STP_RPCSPG )
661  {
662 #ifdef STP_AGG_SYM
663  ro2 = realnterms - 1;
664 #else
665  ro2 = (realnterms * (realnterms - 1)) / 2;
666 #endif
667  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->prizesymcons), ro2) );
668 
669  for( r = 0; r < ro2; r++ )
670  {
671  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PrizeSymConstraint%d", r);
672 
673  SCIP_CALL( SCIPcreateConsSetpack(scip, &(probdata->prizesymcons[r]), consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ));
674 
675  SCIP_CALL(SCIPaddCons(scip, probdata->prizesymcons[r]));
676  }
677  }
678 
679  if( graph->stp_type != STP_RPCSPG )
680  {
681  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PrizeConstraint");
682  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizecons), consname, 0, NULL, NULL,
683  1.0, 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
684  SCIP_CALL( SCIPaddCons(scip, probdata->prizecons) );
685  }
686 
687  if( probdata->usecyclecons && graph->stp_type == STP_PCSPG )
688  {
689  ro2 = 0;
690  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->prizecyclecons), nedges) );
691  for( r = 0; r < nedges; r++ )
692  {
693  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PrizeLPConstraint%d", ro2);
694  if( root == graph->head[r] )
695  {
696  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizecyclecons[ro2]), consname, 0, NULL, NULL,
697  -SCIPinfinity(scip), 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
698  }
699  else
700  {
701  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizecyclecons[ro2]), consname, 0, NULL, NULL,
702  -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
703  }
704  SCIP_CALL( SCIPaddCons(scip, probdata->prizecyclecons[ro2++]) );
705  }
706  }
707 
708  return SCIP_OKAY;
709 }
710 
711 
712 #if FLOWB
713 /** create Flow Balance constraints (cut mode only) */
714 static
715 SCIP_RETCODE createFlowBalanceConstraints(
716  SCIP* scip, /**< SCIP data structure */
717  SCIP_PROBDATA* probdata /**< problem data */
718  )
719 
720 {
721  GRAPH* graph;
722  int r;
723  int nnonterms;
724  char consname[SCIP_MAXSTRLEN];
725 
726  assert(scip != NULL);
727  assert(probdata != NULL);
728 
729  graph = probdata->graph;
730 
731  assert(graph != NULL);
732 
733  if( graph->stp_type == STP_RPCSPG )
734  nnonterms = graph->knots - graph->terms;
735  else
736  nnonterms = graph->knots - graph->terms;
737 
738  probdata->nnonterms = nnonterms;
739 
740  SCIPdebugMessage("createFlowBalanceConstraints \n");
741 
742 
743  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->flowbcons), nnonterms) );
744  for( r = 0; r < nnonterms; r++ )
745  {
746  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "FlowBalanceConstraint%d", r);
747  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->flowbcons[r]), consname, 0, NULL, NULL,
748  -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
749  SCIP_CALL( SCIPaddCons(scip, probdata->flowbcons[r]) );
750  }
751 
752  return SCIP_OKAY;
753 }
754 
755 #endif
756 
757 /** create constraints (in Flow or Price Mode) */
758 static
759 SCIP_RETCODE createConstraints(
760  SCIP* scip, /**< SCIP data structure */
761  SCIP_PROBDATA* probdata /**< problem data */
762  )
763 {
764  GRAPH* graph;
765  char consname[SCIP_MAXSTRLEN];
766  int t;
767  int e;
768  int k;
769  int k2;
770  int realnterms;
771  int nedges;
772  int nnodes;
773 
774  assert(scip != NULL);
775  assert(probdata != NULL);
776  assert(probdata->mode != MODE_CUT);
777 
778  SCIPdebugMessage("createConstraints \n");
779  graph = probdata->graph;
780  nedges = probdata->nedges;
781  nnodes = probdata->nnodes;
782  realnterms = probdata->realnterms;
783 
784  /* create edge constraints (used by both Flow and Price) */
785  if( !probdata->bigt )
786  {
787  /* create |T \ {root}|*|E| edge constraints (disaggregated) */
788  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->edgecons), (realnterms) * (nedges)) );
789  for( t = 0; t < realnterms; ++t )
790  {
791  for( e = 0; e < nedges; ++e )
792  {
793  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "EdgeConstraint%d_%d", t, e);
794  SCIP_CALL( SCIPcreateConsLinear ( scip, &( probdata->edgecons[t * nedges + e] ), consname, 0, NULL, NULL,
795  -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, probdata->mode == MODE_PRICE, FALSE, FALSE, FALSE) );
796  SCIP_CALL( SCIPaddCons(scip, probdata->edgecons[t * nedges + e]) );
797  }
798  }
799  }
800  else
801  {
802  /* create |E| edge constraints (aggregated) */
803  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->edgecons), nedges) );
804  for( e = 0; e < nedges; ++e )
805  {
806  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "EdgeConstraintT%d", e);
807  SCIP_CALL( SCIPcreateConsLinear ( scip, &( probdata->edgecons[e] ), consname,
808  0, NULL, NULL, -SCIPinfinity(scip), 0.0,
809  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, probdata->mode == MODE_PRICE, FALSE, FALSE, FALSE) );
810  SCIP_CALL( SCIPaddCons(scip, probdata->edgecons[e]) );
811  }
812  }
813 
814  /* Branch and Price mode */
815  if( probdata->mode == MODE_PRICE )
816  {
817  /* create |T \ {root}| path constraints */
818  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->pathcons), realnterms) );
819 
820  for( t = 0; t < realnterms; ++t )
821  {
822  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraint%d", t);
823  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->pathcons[t]), consname, 0, NULL, NULL, 1.0, SCIPinfinity(scip),
824  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE) );
825 
826  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[t]) );
827  }
828  }
829  /* Flow mode */
830  else if( probdata->mode == MODE_FLOW )
831  {
832  /* create path constraints */
833  if( !probdata->bigt )
834  {
835  /* not in 'T' mode, so create |T \ {root} |*|V \ {root}| path constraints */
836  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->pathcons), realnterms * (nnodes - 1)) );
837  for( t = 0; t < realnterms; ++t )
838  {
839  k2 = 0;
840  for( k = 0; k < nnodes; ++k )
841  {
842  /* if node k is not the root */
843  if( k != graph->source)
844  {
845  /* if node k is not the t-th terminal, set RHS = 0 */
846  if( k != probdata->realterms[t] )
847  {
848  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraint%d_%d", t, k2);
849  SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[t * (nnodes - 1) + k2] ), consname,
850  0, NULL, NULL, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
851  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[t * (nnodes - 1) + k2]) );
852  }
853 
854  /* if node k is the t-th terminal, set RHS = 1 */
855  else
856  {
857  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraint%d_%d", t, k2);
858  SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[t * (nnodes - 1) + k2] ), consname,
859  0, NULL, NULL, 1.0, 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
860  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[t * (nnodes - 1) + k2]) );
861  }
862 
863  k2 += 1;
864  }
865  }
866  }
867  }
868  else
869  {
870  /* in 'T' mode, so create |V \ {root}| path constraints */
871  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->pathcons), (nnodes - 1)) );
872  k2 = 0;
873  for( k = 0; k < nnodes; ++k )
874  {
875  /* if node k is not the root */
876  if( k != graph->source)
877  {
878  /* if node k is not a terminal, set RHS = 0 */
879  if( graph->term[k] != 0 )
880  {
881  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraintT%d", k2);
882  SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[k2] ), consname,
883  0, NULL, NULL, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
884  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[k2]) );
885  }
886  /* if node k is a terminal, set RHS = 1 */
887  else
888  {
889  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraintT%d", k2);
890  SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[k2] ), consname,
891  0, NULL, NULL, 1.0, 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
892  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[k2]) );
893  }
894  k2 += 1;
895  }
896  }
897  }
898  }
899 
900  return SCIP_OKAY;
901 }
902 
903 /** create initial columns */
904 static
905 SCIP_RETCODE createVariables(
906  SCIP* scip, /**< SCIP data structure */
907  SCIP_PROBDATA* probdata, /**< problem data */
908  SCIP_Real offset /**< offset computed during the presolving */
909  )
910 {
911  GRAPH* graph;
912  SCIP_VAR* var;
913  SCIP_Real* edgecost;
914  int e;
915  int t;
916  int k;
917  int k2;
918  int tail;
919  char varname[SCIP_MAXSTRLEN];
920 
921  assert(scip != NULL);
922  assert(probdata != NULL);
923 
924  t = 0;
925  k2 = 0;
926  graph = probdata->graph;
927  SCIPdebugMessage("createVariables \n");
928 
929  /* if the graph reduction solved the whole problem, NULL is returned */
930  if( graph != NULL )
931  {
932  int nedges = probdata->nedges;
933  int nvars = probdata->nvars;
934  int realnterms = probdata->realnterms;
935  int root = graph->source;
936  int nnodes = graph->knots;
937  SCIP_Bool objint = SCIPisIntegral(scip, offset);
938 
939  assert(nedges == graph->edges);
940 
941  SCIP_CALL( SCIPallocMemoryArray(scip, &probdata->xval, nvars) );
942  SCIP_CALL( SCIPallocMemoryArray(scip, &probdata->edgevars, nvars) );
943 
944  /* cut mode */
945  if( probdata->mode == MODE_CUT )
946  {
947  int a;
948  assert(probdata->nlayers == 1);
949 
950  for( e = 0; e < nedges; ++e )
951  {
952  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "x_%d_%d", graph->tail[e], graph->head[e]);
953  SCIP_CALL( SCIPcreateVarBasic(scip, &probdata->edgevars[e], varname, 0.0, 1.0, graph->cost[e], SCIP_VARTYPE_BINARY) );
954  SCIP_CALL( SCIPaddVar(scip, probdata->edgevars[e]) );
955  objint = objint && SCIPisIntegral(scip, graph->cost[e]);
956  }
957 
958  /* Hop-Constrained STP */
959  if( graph->stp_type == STP_DHCSTP )
960  {
961  SCIP_Real hopfactor;
962  for( e = 0; e < nedges; ++e )
963  {
964  /* @note: When contractions are used in presolving: modify */
965  hopfactor = 1.0;
966  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->hopcons, probdata->edgevars[e], hopfactor) );
967  }
968  }
969 
970  /* Degree-Constrained STP */
971  if( graph->stp_type == STP_DCSTP )
972  {
973  for( k = 0; k < nnodes; ++k )
974  {
975  for( e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
976  {
977  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->degcons[k], probdata->edgevars[e], 1.0) );
978  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->degcons[k], probdata->edgevars[flipedge(e)], 1.0) );
979  }
980  }
981  }
982 
983 #if FLOWB
984  k2 = 0;
985 
986  for( k = 0; k < nnodes; k++ )
987  {
988  if( !Is_term(graph->term[k]) )
989  {
990  /* incoming arcs */
991  for( a = graph->inpbeg[k]; a != EAT_LAST; a = graph->ieat[a] )
992  {
993  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->flowbcons[k2], probdata->edgevars[a], 1.0) );
994  }
995  /* outgoing arcs */
996  for( a = graph->outbeg[k]; a != EAT_LAST; a = graph->oeat[a] )
997  {
998  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->flowbcons[k2], probdata->edgevars[a], -1.0) );
999  }
1000  k2++;
1001  }
1002  }
1003 #endif
1004 
1005  /* PRIZECOLLECTING STP */
1006  if( graph->stp_type == STP_PCSPG || graph->stp_type == STP_MWCSP )
1007  {
1008  int* pseudoterms;
1009 
1010  assert(graph->extended);
1011 
1012  pseudoterms = NULL;
1013 
1014  if( probdata->usesymcons )
1015  {
1016  SCIP_CALL( SCIPallocBufferArray(scip, &pseudoterms, probdata->realnterms) );
1017  t = 0;
1018  k2 = 0;
1019  }
1020 
1021  if( probdata->usecyclecons && graph->stp_type == STP_PCSPG )
1022  {
1023  for( e = 0; e < nedges; e++ )
1024  {
1025  const int head = graph->head[e];
1026  SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizecyclecons[e], probdata->edgevars[e], 1.0));
1027  SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizecyclecons[e], probdata->edgevars[flipedge(e)], 1.0));
1028  if( root != head )
1029  {
1030  for( a = graph->inpbeg[head]; a != EAT_LAST; a = graph->ieat[a] )
1031  {
1032  SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizecyclecons[e], probdata->edgevars[a], -1.0));
1033  }
1034  }
1035  }
1036  }
1037 
1038  for( e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
1039  {
1040  const int head = graph->head[e];
1041  if( !Is_term(graph->term[head]) )
1042  {
1043  SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizecons, probdata->edgevars[e], 1.0));
1044 
1045  assert(graph->prize != NULL);
1046 
1047  /* variables are preferred to be branched on */
1048  SCIP_CALL( SCIPchgVarBranchPriority(scip, probdata->edgevars[e], 10 + (int)(10.0 * graph->prize[head])) );
1049 
1050  if( probdata->usesymcons )
1051  {
1052  assert(pseudoterms != NULL);
1053 
1054  pseudoterms[t] = head;
1055 #ifdef STP_AGG_SYM
1056  /* skip the last term */
1057  if( t == graph->terms - 2 )
1058  {
1059  assert(t == probdata->realnterms - 1);
1060  continue;
1061  }
1062 
1063  for( a = graph->inpbeg[head]; a != EAT_LAST; a = graph->ieat[a] )
1064  SCIP_CALL( SCIPaddCoefSetppc(scip, probdata->prizesymcons[t], probdata->edgevars[a]) );
1065 
1066  for( int prev = 0; prev < t; prev++ )
1067  SCIP_CALL( SCIPaddCoefSetppc(scip, probdata->prizesymcons[prev], probdata->edgevars[e]) );
1068 
1069 #else
1070  for( k = 0; k < t; k++ )
1071  {
1072  for( a = graph->inpbeg[pseudoterms[k]]; a != EAT_LAST; a = graph->ieat[a] )
1073  {
1074  SCIP_CALL(SCIPaddCoefSetppc(scip, probdata->prizesymcons[k2], probdata->edgevars[a]));
1075  }
1076 
1077  SCIP_CALL(SCIPaddCoefSetppc(scip, probdata->prizesymcons[k2], probdata->edgevars[e]));
1078  k2++;
1079  }
1080 #endif
1081  t++;
1082  }
1083  }
1084  }
1085  if( probdata->usesymcons )
1086  SCIPfreeBufferArray(scip, &pseudoterms);
1087  }
1088  }
1089  /* Price or Flow mode */
1090  else
1091  {
1092  /* create and add the edge variables */
1093  for( e = 0; e < nedges; ++e )
1094  {
1095  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "EdgeVar%d_%d", graph->tail[e], graph->head[e]);
1096  var = NULL;
1097  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, 1.0, graph->cost[e], SCIP_VARTYPE_BINARY) );
1098  objint = objint && SCIPisIntegral(scip, graph->cost[e]);
1099  SCIP_CALL( SCIPaddVar(scip, var) );
1100  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
1101 
1102  if( !probdata->bigt )
1103  {
1104  for( t = 0; t < realnterms; ++t )
1105  {
1106  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + e], var, -1.0) );
1107  }
1108  }
1109  else
1110  {
1111  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[e], var, (double ) -realnterms));
1112  }
1113  probdata->edgevars[e] = var;
1114  }
1115  }
1116 
1117  /* Price mode */
1118  if( probdata->mode == MODE_PRICE )
1119  {
1120  PATH* path;
1121 
1122  /* the flow variables are not used in the Price mode */
1123  probdata->flowvars = NULL;
1124 
1125  /* compute shortest paths to the root */
1126  SCIP_CALL(SCIPallocBufferArray(scip, &path, graph->knots));
1127  SCIP_CALL(SCIPallocBufferArray(scip, &edgecost, nedges));
1128  for (e = 0; e < nedges; ++e)
1129  edgecost[e] = graph->cost[e];
1130 
1131  for (e = 0; e < graph->knots; e++)
1132  graph->mark[e] = 1;
1133 
1134  graph_path_exec(scip, graph, FSP_MODE, root, edgecost, path);
1135 
1136  /* create and add initial path variables (one for each real terminal) */
1137  for( t = 0; t < realnterms; ++t )
1138  {
1139  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "PathVar%d_0", t);
1140  var = NULL;
1141  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1142  SCIP_CALL( SCIPaddVar(scip, var) );
1143  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
1144  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t], var, 1.0) );
1145  tail = probdata->realterms[t];
1146  while( tail != root )
1147  {
1148  if( !probdata->bigt )
1149  {
1150  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + path[tail].edge], var, 1.0));
1151  }
1152  else
1153  {
1154  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[path[tail].edge], var, 1.0));
1155  }
1156 
1157  tail = graph->tail[path[tail].edge];
1158  }
1159  }
1160 
1161  /* free local arrays */
1162  SCIPfreeBufferArray(scip, &edgecost);
1163  SCIPfreeBufferArray(scip, &path);
1164  }
1165  /* Flow mode */
1166  else if( probdata->mode == MODE_FLOW )
1167  {
1168  /* store the number of disparate flows (commodities) in nflows */
1169  int nflows;
1170  if ( !probdata->bigt )
1171  nflows = realnterms;
1172  else
1173  nflows = 1;
1174 
1175  SCIP_CALL( SCIPallocMemoryArray(scip, &probdata->flowvars, nflows * nedges) );
1176 
1177  /* create and add the flow variables */
1178  for( e = 0; e < nedges; ++e )
1179  {
1180  for( t = 0; t < nflows; ++t )
1181  {
1182  var = NULL;
1183  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "FlowVar%d.%d_%d", t, graph->tail[e], graph->head[e]);
1184  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1185  SCIP_CALL( SCIPaddVar(scip, var) );
1186  probdata->flowvars[t * nedges + e] = var;
1187  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + e], probdata->flowvars[t * nedges + e], 1.0) );
1188  }
1189  }
1190 
1191  /* add the flow variables to the corresponding path constraints */
1192  for( t = 0; t < nflows; ++t )
1193  {
1194  k2 = 0;
1195  for( k = 0; k < nnodes; ++k )
1196  {
1197  if( k != root )
1198  {
1199  e = graph->inpbeg[k];
1200  while( e >= 0 )
1201  {
1202  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t * (nnodes - 1) + k2], probdata->flowvars[t * nedges + e], 1.0) );
1203  e = graph->ieat[e];
1204  }
1205  e = graph->outbeg[k];
1206  while( e >= 0 )
1207  {
1208  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t * (nnodes - 1) + k2], probdata->flowvars[t * nedges + e], -1.0) );
1209  e = graph->oeat[e];
1210  }
1211  k2 += 1;
1212  }
1213  }
1214  }
1215  }
1216 
1217  /* if all edge costs and the offset are integral, tell SCIP the objective will be integral */
1218  if( objint )
1219  SCIP_CALL( SCIPsetObjIntegral(scip) );
1220  }
1221  else
1222  {
1223  probdata->edgevars = NULL;
1224  probdata->flowvars = NULL;
1225  }
1226 #if USEOFFSETVAR
1227  /* add offset */
1228  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "OFFSET");
1229  SCIP_CALL( SCIPcreateVarBasic(scip, &probdata->offsetvar, varname, 1.0, 1.0, offset, SCIP_VARTYPE_INTEGER) );
1230  SCIP_CALL( SCIPaddVar(scip, probdata->offsetvar) );
1231 #else
1232  SCIP_CALL( SCIPaddOrigObjoffset(scip, offset) );
1233 #endif
1234 
1235  return SCIP_OKAY;
1236 }
1237 
1238 
1239 /**@} */
1240 
1241 /**@name Callback methods of problem data
1242  *
1243  * @{
1244  */
1245 
1246 /** copies user data of source SCIP for the target SCIP */
1247 static
1248 SCIP_DECL_PROBCOPY(probcopyStp)
1249 {
1250  GRAPH* graphcopy;
1251 
1252  SCIPdebugMessage("########################## probcopy ###########################\n");
1253 
1254  SCIP_CALL( graph_copy(scip, sourcedata->graph, &graphcopy) );
1255  SCIP_CALL( graph_path_init(scip, graphcopy) );
1256 
1257  if( sourcedata->mode == MODE_CUT )
1258  SCIP_CALL( graph_mincut_init(scip, graphcopy) );
1259 
1260  SCIP_CALL( probdataCreate(scip, targetdata, graphcopy) );
1261 
1262 #ifdef WITH_UG
1263  {
1264  GRAPH* orggraphcopy;
1265  SCIP_CALL( graph_copy(scip, sourcedata->orggraph, &orggraphcopy) );
1266  SCIP_CALL( graph_path_init(scip, orggraphcopy) );
1267  (*targetdata)->orggraph = orggraphcopy;
1268  }
1269 #endif
1270 
1271  (*targetdata)->minelims = sourcedata->minelims;
1272  (*targetdata)->offset = sourcedata->offset;
1273  (*targetdata)->norgedges = sourcedata->norgedges;
1274  (*targetdata)->mode = sourcedata->mode;
1275  (*targetdata)->bigt = sourcedata->bigt;
1276  (*targetdata)->nlayers = sourcedata->nlayers;
1277  (*targetdata)->nedges = sourcedata->nedges;
1278  (*targetdata)->nnodes = sourcedata->nnodes;
1279  (*targetdata)->nterms = sourcedata->nterms;
1280  (*targetdata)->nnonterms = sourcedata->nnonterms;
1281  (*targetdata)->realnterms = sourcedata->realnterms;
1282  (*targetdata)->emitgraph = sourcedata->emitgraph;
1283  (*targetdata)->usesymcons = sourcedata->usesymcons;
1284  (*targetdata)->usecyclecons = sourcedata->usecyclecons;
1285  (*targetdata)->nvars = sourcedata->nvars;
1286  (*targetdata)->copy = TRUE;
1287 #if USEOFFSETVAR
1288  (*targetdata)->offsetvar = NULL;
1289 
1290  if( sourcedata->offsetvar != NULL && SCIPvarIsActive(sourcedata->offsetvar) )
1291  {
1292  SCIP_Bool success;
1293 
1294  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->offsetvar, &((*targetdata)->offsetvar), varmap, consmap, global, &success) );
1295  assert(success);
1296 
1297  SCIP_CALL( SCIPcaptureVar(scip, (*targetdata)->offsetvar) );
1298  }
1299 #endif
1300  if( sourcedata->nedges > 0 )
1301  {
1302  SCIP_Bool success;
1303  int v;
1304  int c;
1305  int i;
1306 
1307  /* transform variables */
1308  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->xval, sourcedata->nvars) );
1309  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->edgevars, sourcedata->nvars) );
1310 
1311  for( v = sourcedata->nvars - 1; v >= 0; --v )
1312  {
1313  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->edgevars[v], &((*targetdata)->edgevars[v]), varmap, consmap, global, &success) );
1314  assert(success);
1315 
1316  SCIP_CALL( SCIPcaptureVar(scip, (*targetdata)->edgevars[v]) );
1317  }
1318 
1319  /* cut mode */
1320  if( sourcedata->mode == MODE_CUT )
1321  {
1322  (*targetdata)->edgecons = NULL;
1323  (*targetdata)->pathcons = NULL;
1324  if( sourcedata->stp_type == STP_DCSTP )
1325  {
1326  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->degcons, sourcedata->nnodes) );
1327  for( c = sourcedata->nnodes - 1; c >= 0; --c )
1328  {
1329  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->degcons[c], &((*targetdata)->degcons[c]),
1330  SCIPconsGetHdlr(sourcedata->degcons[c]), varmap, consmap,
1331  SCIPconsGetName(sourcedata->degcons[c]),
1332  SCIPconsIsInitial(sourcedata->degcons[c]),
1333  SCIPconsIsSeparated(sourcedata->degcons[c]),
1334  SCIPconsIsEnforced(sourcedata->degcons[c]),
1335  SCIPconsIsChecked(sourcedata->degcons[c]),
1336  SCIPconsIsPropagated(sourcedata->degcons[c]),
1337  SCIPconsIsLocal(sourcedata->degcons[c]),
1338  SCIPconsIsModifiable(sourcedata->degcons[c]),
1339  SCIPconsIsDynamic(sourcedata->degcons[c]),
1340  SCIPconsIsRemovable(sourcedata->degcons[c]),
1341  SCIPconsIsStickingAtNode(sourcedata->degcons[c]),
1342  global, &success) );
1343  assert(success);
1344 
1345  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->degcons[c]) );
1346  }
1347  }
1348 
1349  if( sourcedata->stp_type == STP_PCSPG || sourcedata->stp_type == STP_RPCSPG || sourcedata->stp_type == STP_MWCSP )
1350  {
1351 #if FLOWB
1352  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->flowbcons, sourcedata->nnonterms) );
1353  for( c = sourcedata->nnonterms - 1; c >= 0; --c )
1354  {
1355  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->flowbcons[c], &((*targetdata)->flowbcons[c]),
1356  SCIPconsGetHdlr(sourcedata->flowbcons[c]), varmap, consmap,
1357  SCIPconsGetName(sourcedata->flowbcons[c]),
1358  SCIPconsIsInitial(sourcedata->flowbcons[c]),
1359  SCIPconsIsSeparated(sourcedata->flowbcons[c]),
1360  SCIPconsIsEnforced(sourcedata->flowbcons[c]),
1361  SCIPconsIsChecked(sourcedata->flowbcons[c]),
1362  SCIPconsIsPropagated(sourcedata->flowbcons[c]),
1363  SCIPconsIsLocal(sourcedata->flowbcons[c]),
1364  SCIPconsIsModifiable(sourcedata->flowbcons[c]),
1365  SCIPconsIsDynamic(sourcedata->flowbcons[c]),
1366  SCIPconsIsRemovable(sourcedata->flowbcons[c]),
1367  SCIPconsIsStickingAtNode(sourcedata->flowbcons[c]),
1368  global, &success) );
1369  assert(success);
1370 
1371  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->flowbcons[c]) );
1372  }
1373 #endif
1374 
1375  if( sourcedata->usecyclecons && sourcedata->stp_type == STP_PCSPG )
1376  {
1377  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->prizecyclecons, sourcedata->nedges) );
1378  for( c = sourcedata->nedges - 1; c >= 0; --c )
1379  {
1380  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->prizecyclecons[c], &((*targetdata)->prizecyclecons[c]),
1381  SCIPconsGetHdlr(sourcedata->prizecyclecons[c]), varmap, consmap,
1382  SCIPconsGetName(sourcedata->prizecyclecons[c]),
1383  SCIPconsIsInitial(sourcedata->prizecyclecons[c]),
1384  SCIPconsIsSeparated(sourcedata->prizecyclecons[c]),
1385  SCIPconsIsEnforced(sourcedata->prizecyclecons[c]),
1386  SCIPconsIsChecked(sourcedata->prizecyclecons[c]),
1387  SCIPconsIsPropagated(sourcedata->prizecyclecons[c]),
1388  SCIPconsIsLocal(sourcedata->prizecyclecons[c]),
1389  SCIPconsIsModifiable(sourcedata->prizecyclecons[c]),
1390  SCIPconsIsDynamic(sourcedata->prizecyclecons[c]),
1391  SCIPconsIsRemovable(sourcedata->prizecyclecons[c]),
1392  SCIPconsIsStickingAtNode(sourcedata->prizecyclecons[c]),
1393  global, &success) );
1394  assert(success);
1395 
1396  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->prizecyclecons[c]) );
1397  }
1398  }
1399 
1400  if( sourcedata->usesymcons && sourcedata->stp_type != STP_RPCSPG )
1401  {
1402 #ifdef STP_AGG_SYM
1403  v = sourcedata->realnterms - 1;
1404 #else
1405  v = ((sourcedata->realnterms - 1) * sourcedata->realnterms ) / 2;
1406 #endif
1407  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->prizesymcons, v) );
1408  for( c = v - 1; c >= 0; --c )
1409  {
1410  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->prizesymcons[c], &((*targetdata)->prizesymcons[c]),
1411  SCIPconsGetHdlr(sourcedata->prizesymcons[c]), varmap, consmap,
1412  SCIPconsGetName(sourcedata->prizesymcons[c]),
1413  SCIPconsIsInitial(sourcedata->prizesymcons[c]),
1414  SCIPconsIsSeparated(sourcedata->prizesymcons[c]),
1415  SCIPconsIsEnforced(sourcedata->prizesymcons[c]),
1416  SCIPconsIsChecked(sourcedata->prizesymcons[c]),
1417  SCIPconsIsPropagated(sourcedata->prizesymcons[c]),
1418  SCIPconsIsLocal(sourcedata->prizesymcons[c]),
1419  SCIPconsIsModifiable(sourcedata->prizesymcons[c]),
1420  SCIPconsIsDynamic(sourcedata->prizesymcons[c]),
1421  SCIPconsIsRemovable(sourcedata->prizesymcons[c]),
1422  SCIPconsIsStickingAtNode(sourcedata->prizesymcons[c]),
1423  global, &success) );
1424  assert(success);
1425 
1426  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->prizesymcons[c]) );
1427  }
1428  }
1429 
1430  if( sourcedata->stp_type != STP_RPCSPG )
1431  {
1432  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->prizecons, &((*targetdata)->prizecons),
1433  SCIPconsGetHdlr(sourcedata->prizecons), varmap, consmap,
1434  SCIPconsGetName(sourcedata->prizecons),
1435  SCIPconsIsInitial(sourcedata->prizecons),
1436  SCIPconsIsSeparated(sourcedata->prizecons),
1437  SCIPconsIsEnforced(sourcedata->prizecons),
1438  SCIPconsIsChecked(sourcedata->prizecons),
1439  SCIPconsIsPropagated(sourcedata->prizecons),
1440  SCIPconsIsLocal(sourcedata->prizecons),
1441  SCIPconsIsModifiable(sourcedata->prizecons),
1442  SCIPconsIsDynamic(sourcedata->prizecons),
1443  SCIPconsIsRemovable(sourcedata->prizecons),
1444  SCIPconsIsStickingAtNode(sourcedata->prizecons),
1445  global, &success) );
1446  assert(success);
1447 
1448  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->prizecons) );
1449  }
1450  }
1451  }
1452  /* Price or Flow mode */
1453  else
1454  {
1455  /* transform edge constraints */
1456  if( sourcedata->bigt )
1457  {
1458  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->nedges) );
1459 
1460  for( c = sourcedata->nedges - 1; c >= 0; --c )
1461  {
1462  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->edgecons[c], &((*targetdata)->edgecons[c]),
1463  SCIPconsGetHdlr(sourcedata->edgecons[c]), varmap, consmap,
1464  SCIPconsGetName(sourcedata->edgecons[c]),
1465  SCIPconsIsInitial(sourcedata->edgecons[c]),
1466  SCIPconsIsSeparated(sourcedata->edgecons[c]),
1467  SCIPconsIsEnforced(sourcedata->edgecons[c]),
1468  SCIPconsIsChecked(sourcedata->edgecons[c]),
1469  SCIPconsIsPropagated(sourcedata->edgecons[c]),
1470  SCIPconsIsLocal(sourcedata->edgecons[c]),
1471  SCIPconsIsModifiable(sourcedata->edgecons[c]),
1472  SCIPconsIsDynamic(sourcedata->edgecons[c]),
1473  SCIPconsIsRemovable(sourcedata->edgecons[c]),
1474  SCIPconsIsStickingAtNode(sourcedata->edgecons[c]),
1475  global, &success) );
1476  assert(success);
1477 
1478  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->edgecons[c]) );
1479  }
1480  }
1481  else
1482  {
1483  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->realnterms * sourcedata->nedges) );
1484  for( c = sourcedata->realnterms * sourcedata->nedges - 1; c >= 0; --c )
1485  {
1486  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->edgecons[c], &((*targetdata)->edgecons[c]),
1487  SCIPconsGetHdlr(sourcedata->edgecons[c]), varmap, consmap,
1488  SCIPconsGetName(sourcedata->edgecons[c]),
1489  SCIPconsIsInitial(sourcedata->edgecons[c]),
1490  SCIPconsIsSeparated(sourcedata->edgecons[c]),
1491  SCIPconsIsEnforced(sourcedata->edgecons[c]),
1492  SCIPconsIsChecked(sourcedata->edgecons[c]),
1493  SCIPconsIsPropagated(sourcedata->edgecons[c]),
1494  SCIPconsIsLocal(sourcedata->edgecons[c]),
1495  SCIPconsIsModifiable(sourcedata->edgecons[c]),
1496  SCIPconsIsDynamic(sourcedata->edgecons[c]),
1497  SCIPconsIsRemovable(sourcedata->edgecons[c]),
1498  SCIPconsIsStickingAtNode(sourcedata->edgecons[c]),
1499  global, &success) );
1500  assert(success);
1501 
1502  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->edgecons[c]) );
1503  }
1504  }
1505 
1506  /* transform constraints */
1507  if( sourcedata->mode == MODE_PRICE )
1508  {
1509  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms) );
1510  for( c = sourcedata->realnterms - 1; c >= 0; --c )
1511  {
1512  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->pathcons[c], &((*targetdata)->pathcons[c]),
1513  SCIPconsGetHdlr(sourcedata->pathcons[c]), varmap, consmap,
1514  SCIPconsGetName(sourcedata->pathcons[c]),
1515  SCIPconsIsInitial(sourcedata->pathcons[c]),
1516  SCIPconsIsSeparated(sourcedata->pathcons[c]),
1517  SCIPconsIsEnforced(sourcedata->pathcons[c]),
1518  SCIPconsIsChecked(sourcedata->pathcons[c]),
1519  SCIPconsIsPropagated(sourcedata->pathcons[c]),
1520  SCIPconsIsLocal(sourcedata->pathcons[c]),
1521  SCIPconsIsModifiable(sourcedata->pathcons[c]),
1522  SCIPconsIsDynamic(sourcedata->pathcons[c]),
1523  SCIPconsIsRemovable(sourcedata->pathcons[c]),
1524  SCIPconsIsStickingAtNode(sourcedata->pathcons[c]),
1525  global, &success) );
1526  assert(success);
1527 
1528  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->pathcons[c]) );
1529  }
1530  }
1531  /* transform constraints and variables */
1532  else if( sourcedata->mode == MODE_FLOW )
1533  {
1534  if( sourcedata->bigt )
1535  {
1536  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->nedges) );
1537  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, (sourcedata->nnodes - 1)) );
1538  for( c = sourcedata->nnodes - 2; c >= 0; --c )
1539  {
1540  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->pathcons[c], &((*targetdata)->pathcons[c]),
1541  SCIPconsGetHdlr(sourcedata->pathcons[c]), varmap, consmap,
1542  SCIPconsGetName(sourcedata->pathcons[c]),
1543  SCIPconsIsInitial(sourcedata->pathcons[c]),
1544  SCIPconsIsSeparated(sourcedata->pathcons[c]),
1545  SCIPconsIsEnforced(sourcedata->pathcons[c]),
1546  SCIPconsIsChecked(sourcedata->pathcons[c]),
1547  SCIPconsIsPropagated(sourcedata->pathcons[c]),
1548  SCIPconsIsLocal(sourcedata->pathcons[c]),
1549  SCIPconsIsModifiable(sourcedata->pathcons[c]),
1550  SCIPconsIsDynamic(sourcedata->pathcons[c]),
1551  SCIPconsIsRemovable(sourcedata->pathcons[c]),
1552  SCIPconsIsStickingAtNode(sourcedata->pathcons[c]),
1553  global, &success) );
1554  assert(success);
1555 
1556  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->pathcons[c]) );
1557  }
1558 
1559  for( v = (*targetdata)->nedges - 1; v >= 0; --v )
1560  {
1561  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->flowvars[v], &((*targetdata)->flowvars[v]), varmap, consmap, global, &success) );
1562  assert(success);
1563 
1564  SCIP_CALL( SCIPcaptureVar(scip, (*targetdata)->flowvars[v]) );
1565  }
1566  }
1567  else
1568  {
1569  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->realnterms * sourcedata->nedges) );
1570  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms * (sourcedata->nnodes - 1)) );
1571  for( c = sourcedata->realnterms * (sourcedata->nnodes - 1) - 1; c >= 0; --c )
1572  {
1573  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->pathcons[c], &((*targetdata)->pathcons[c]),
1574  SCIPconsGetHdlr(sourcedata->pathcons[c]), varmap, consmap,
1575  SCIPconsGetName(sourcedata->pathcons[c]),
1576  SCIPconsIsInitial(sourcedata->pathcons[c]),
1577  SCIPconsIsSeparated(sourcedata->pathcons[c]),
1578  SCIPconsIsEnforced(sourcedata->pathcons[c]),
1579  SCIPconsIsChecked(sourcedata->pathcons[c]),
1580  SCIPconsIsPropagated(sourcedata->pathcons[c]),
1581  SCIPconsIsLocal(sourcedata->pathcons[c]),
1582  SCIPconsIsModifiable(sourcedata->pathcons[c]),
1583  SCIPconsIsDynamic(sourcedata->pathcons[c]),
1584  SCIPconsIsRemovable(sourcedata->pathcons[c]),
1585  SCIPconsIsStickingAtNode(sourcedata->pathcons[c]),
1586  global, &success) );
1587  assert(success);
1588 
1589  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->pathcons[c]) );
1590  }
1591 
1592  for( v = sourcedata->nedges * sourcedata->realnterms - 1; v >= 0; --v )
1593  {
1594  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->flowvars[v], &((*targetdata)->flowvars[v]), varmap, consmap, global, &success) );
1595  assert(success);
1596 
1597  SCIP_CALL( SCIPcaptureVar(scip, (*targetdata)->flowvars[v]) );
1598  }
1599  }
1600  }
1601  }
1602 
1603  /* transform array of (real) terminals */
1604  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->realterms, sourcedata->realnterms) );
1605  for( i = 0; i < sourcedata->realnterms; ++i )
1606  {
1607  (*targetdata)->realterms[i] = sourcedata->realterms[i];
1608  }
1609  }
1610  else
1611  {
1612  (*targetdata)->edgevars = NULL;
1613  (*targetdata)->xval = NULL;
1614  (*targetdata)->realterms = NULL;
1615  (*targetdata)->edgecons = NULL;
1616  (*targetdata)->pathcons = NULL;
1617  (*targetdata)->flowvars = NULL;
1618  }
1619 
1620  *result = SCIP_SUCCESS;
1621 
1622  return SCIP_OKAY;
1623 }
1624 
1625 
1626 /** frees user data of original problem (called when the original problem is freed) */
1627 static
1628 SCIP_DECL_PROBDELORIG(probdelorigStp)
1629 {
1630  SCIPdebugMessage("probdelorigStp \n");
1631 
1632  SCIPdebugMessage("free original problem data\n");
1633 
1634  if( (*probdata)->graph != NULL )
1635  {
1636  if ( (*probdata)->mode == MODE_CUT )
1637  graph_mincut_exit(scip, (*probdata)->graph);
1638 
1639  graph_path_exit(scip, (*probdata)->graph);
1640  graph_free(scip, &((*probdata)->graph), TRUE);
1641  }
1642 
1643 #ifdef WITH_UG
1644  if( (*probdata)->orggraph != NULL )
1645  {
1646  graph_path_exit(scip, (*probdata)->orggraph);
1647  graph_free(scip, &((*probdata)->orggraph), TRUE);
1648  }
1649 #endif
1650  /* free the (original) probdata */
1651  SCIP_CALL( probdataFree(scip, probdata) );
1652 
1653  return SCIP_OKAY;
1654 }
1655 
1656 /** creates user data of transformed problem by transforming the original user problem data
1657  * (called after problem was transformed) */
1658 static
1659 SCIP_DECL_PROBTRANS(probtransStp)
1660 {
1661  SCIP_Real timelimit;
1662  SCIP_Bool update;
1663 
1664  SCIPdebugMessage("probtransStp \n");
1665 
1666  SCIP_CALL( SCIPgetBoolParam(scip, "stp/countpresoltime", &update) );
1667 
1668  /* adjust time limit to take into account reading time */
1669  if( update )
1670  {
1671  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1672  timelimit -= SCIPgetReadingTime(scip);
1673  timelimit = MAX(0.0,timelimit);
1674  SCIP_CALL( SCIPsetRealParam(scip, "limits/time", timelimit) );
1675  }
1676 
1677  /* create transform probdata */
1678  SCIP_CALL( probdataCreate(scip, targetdata, sourcedata->graph) );
1679 #ifdef WITH_UG
1680  (*targetdata)->orggraph = sourcedata->orggraph;
1681 #endif
1682  (*targetdata)->nlayers = sourcedata->nlayers;
1683  (*targetdata)->nedges = sourcedata->nedges;
1684  (*targetdata)->nnodes = sourcedata->nnodes;
1685  (*targetdata)->nterms = sourcedata->nterms;
1686  (*targetdata)->realnterms = sourcedata->realnterms;
1687  (*targetdata)->nnonterms = sourcedata->nnonterms;
1688  (*targetdata)->emitgraph = sourcedata->emitgraph;
1689  (*targetdata)->usesymcons = sourcedata->usesymcons;
1690  (*targetdata)->usecyclecons = sourcedata->usecyclecons;
1691  (*targetdata)->nvars = sourcedata->nvars;
1692  (*targetdata)->mode = sourcedata->mode;
1693  (*targetdata)->offset = sourcedata->offset;
1694  (*targetdata)->norgedges = sourcedata->norgedges;
1695  (*targetdata)->minelims = sourcedata->minelims;
1696  (*targetdata)->bigt = sourcedata->bigt;
1697  (*targetdata)->logfile = sourcedata->logfile;
1698  (*targetdata)->origlogfile = &(sourcedata->logfile);
1699  (*targetdata)->intlogfile = sourcedata->intlogfile;
1700  (*targetdata)->origintlogfile = &(sourcedata->intlogfile);
1701 #if USEOFFSETVAR
1702  if( sourcedata->offsetvar != NULL )
1703  {
1704  SCIP_CALL( SCIPtransformVar(scip, sourcedata->offsetvar, &(*targetdata)->offsetvar) );
1705  }
1706  else
1707  (*targetdata)->offsetvar = NULL;
1708 #endif
1709  if( sourcedata->nedges > 0 )
1710  {
1711  int i;
1712 
1713  /* transform variables */
1714  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->xval, sourcedata->nvars) );
1715  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->edgevars, sourcedata->nvars) );
1716  SCIP_CALL( SCIPtransformVars(scip, sourcedata->nvars, sourcedata->edgevars, (*targetdata)->edgevars) );
1717 
1718  /* cut mode */
1719  if( sourcedata->mode == MODE_CUT )
1720  {
1721  (*targetdata)->edgecons = NULL;
1722  (*targetdata)->pathcons = NULL;
1723 
1724  if( sourcedata->stp_type == STP_DCSTP )
1725  {
1726  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->degcons, sourcedata->nnodes) );
1727  SCIP_CALL( SCIPtransformConss(scip, sourcedata->nnodes, sourcedata->degcons, (*targetdata)->degcons) );
1728  }
1729 
1730  if( sourcedata->stp_type == STP_PCSPG || sourcedata->stp_type == STP_MWCSP )
1731  {
1732 #if FLOWB
1733  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->flowbcons, sourcedata->nnonterms) );
1734  SCIP_CALL( SCIPtransformConss(scip, sourcedata->nnonterms, sourcedata->flowbcons, (*targetdata)->flowbcons) );
1735 #endif
1736 
1737  if( sourcedata->usecyclecons && sourcedata->stp_type == STP_PCSPG )
1738  {
1739  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->prizecyclecons, sourcedata->nedges) );
1740  SCIP_CALL( SCIPtransformConss(scip, sourcedata->nedges, sourcedata->prizecyclecons, (*targetdata)->prizecyclecons) );
1741  }
1742 
1743  if( sourcedata->usesymcons )
1744  {
1745 #ifdef STP_AGG_SYM
1746  i = sourcedata->realnterms - 1;
1747 #else
1748  i = ((sourcedata->realnterms - 1) * (sourcedata->realnterms)) / 2;
1749 #endif
1750  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->prizesymcons, i) );
1751  SCIP_CALL( SCIPtransformConss(scip, i, sourcedata->prizesymcons, (*targetdata)->prizesymcons) );
1752  }
1753  SCIP_CALL( SCIPtransformCons(scip, sourcedata->prizecons, &(*targetdata)->prizecons) );
1754  }
1755 
1756  }
1757  /* Price or Flow mode */
1758  else
1759  {
1760  /* transform edge constraints */
1761  if( sourcedata->bigt )
1762  {
1763  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->nedges));
1764  SCIP_CALL(SCIPtransformConss(scip, sourcedata->nedges, sourcedata->edgecons, (*targetdata)->edgecons));
1765  }
1766  else
1767  {
1768  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->realnterms * sourcedata->nedges));
1769  SCIP_CALL(SCIPtransformConss(scip, sourcedata->realnterms * sourcedata->nedges, sourcedata->edgecons, (*targetdata)->edgecons));
1770  }
1771 
1772  /* transform constraints */
1773  if( sourcedata->mode == MODE_PRICE )
1774  {
1775  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms));
1776  SCIP_CALL(SCIPtransformConss(scip, sourcedata->realnterms, sourcedata->pathcons, (*targetdata)->pathcons));
1777  }
1778  /* transform constraints and variables*/
1779  else if( sourcedata->mode == MODE_FLOW )
1780  {
1781  if( sourcedata->bigt )
1782  {
1783  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->nedges));
1784  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, (sourcedata->nnodes - 1)));
1785  SCIP_CALL(SCIPtransformConss(scip, (sourcedata->nnodes - 1), sourcedata->pathcons, (*targetdata)->pathcons));
1786  SCIP_CALL(SCIPtransformVars(scip, sourcedata->nedges, sourcedata->flowvars, (*targetdata)->flowvars));
1787  }
1788  else
1789  {
1790  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->realnterms * sourcedata->nedges));
1791  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms * (sourcedata->nnodes - 1)));
1792  SCIP_CALL(SCIPtransformConss(scip, sourcedata->realnterms * (sourcedata->nnodes - 1), sourcedata->pathcons, (*targetdata)->pathcons));
1793  SCIP_CALL(SCIPtransformVars(scip, sourcedata->nedges * sourcedata->realnterms, sourcedata->flowvars, (*targetdata)->flowvars));
1794  }
1795  }
1796  }
1797 
1798  /* transform array of (real) terminals */
1799  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->realterms, sourcedata->realnterms) );
1800  for( i = 0; i < sourcedata->realnterms; ++i )
1801  {
1802  (*targetdata)->realterms[i] = sourcedata->realterms[i];
1803  }
1804  }
1805  else
1806  {
1807  (*targetdata)->edgevars = NULL;
1808  (*targetdata)->xval = NULL;
1809  (*targetdata)->realterms = NULL;
1810  (*targetdata)->edgecons = NULL;
1811  (*targetdata)->pathcons = NULL;
1812  (*targetdata)->flowvars = NULL;
1813  }
1814 
1815  return SCIP_OKAY;
1816 }
1817 
1818 static
1819 SCIP_DECL_PROBINITSOL(probinitsolStp)
1820 { /*lint --e{715}*/
1821  assert(scip != NULL);
1822  assert(probdata != NULL);
1823 
1824  return SCIP_OKAY;
1825 }
1826 
1827 static
1828 SCIP_DECL_PROBEXITSOL(probexitsolStp)
1829 { /*lint --e{715}*/
1830  assert(scip != NULL);
1831  assert(probdata != NULL);
1832 
1833  if( probdata->logfile != NULL )
1834  {
1835  int success;
1836  SCIP_Real factor = 1.0;
1837 
1838  if( probdata->stp_type == STP_MWCSP || probdata->stp_type == STP_RMWCSP )
1839  factor = -1.0;
1840 
1841  SCIPprobdataWriteLogLine(scip, "End\n");
1842  SCIPprobdataWriteLogLine(scip, "\n");
1843  SCIPprobdataWriteLogLine(scip, "SECTION Run\n");
1844  if( probdata->ug )
1845  {
1846  SCIPprobdataWriteLogLine(scip, "Threads %d\n", probdata->nSolvers);
1847  SCIPprobdataWriteLogLine(scip, "Time %.1f\n", SCIPgetTotalTime(scip));
1848  SCIPprobdataWriteLogLine(scip, "Dual %16.9f\n", factor * probdata->ugDual);
1849  }
1850  else
1851  {
1852  SCIPprobdataWriteLogLine(scip, "Threads 1\n");
1853  SCIPprobdataWriteLogLine(scip, "Time %.1f\n", SCIPgetTotalTime(scip));
1854  SCIPprobdataWriteLogLine(scip, "Dual %16.9f\n", factor * SCIPgetDualbound(scip));
1855  }
1856  SCIPprobdataWriteLogLine(scip, "Primal %16.9f\n", factor * SCIPgetPrimalbound(scip));
1857  SCIPprobdataWriteLogLine(scip, "End\n");
1858 
1859  if( SCIPgetNSols(scip) > 0 )
1860  {
1861  SCIPprobdataWriteLogLine(scip, "\n");
1862  SCIPprobdataWriteLogLine(scip, "SECTION Finalsolution\n");
1863 
1864  SCIP_CALL( SCIPprobdataWriteSolution(scip, probdata->logfile) );
1865  SCIPprobdataWriteLogLine(scip, "End\n");
1866  }
1867 
1868  success = fclose(probdata->logfile);
1869  if( success != 0 )
1870  {
1871  SCIPerrorMessage("An error occurred while closing file <%s>\n", probdata->logfile);
1872  return SCIP_FILECREATEERROR;
1873  }
1874 
1875  probdata->logfile = NULL;
1876  *(probdata->origlogfile) = NULL;
1877  }
1878 
1879  if( probdata->intlogfile != NULL )
1880  {
1881  int success = fclose(probdata->intlogfile);
1882  if( success != 0 )
1883  {
1884  SCIPerrorMessage("An error occurred while closing file <%s>\n", probdata->intlogfile);
1885  return SCIP_FILECREATEERROR;
1886  }
1887 
1888  probdata->intlogfile = NULL;
1889  *(probdata->origintlogfile) = NULL;
1890  }
1891 
1892  return SCIP_OKAY;
1893 }
1894 
1895 /** frees user data of transformed problem (called when the transformed problem is freed) */
1896 static
1897 SCIP_DECL_PROBDELTRANS(probdeltransStp)
1898 {
1899  SCIPdebugMessage("free transformed problem data\n");
1900 
1901  SCIP_CALL( probdataFree(scip, probdata) );
1902 
1903  return SCIP_OKAY;
1904 }
1905 
1906 /**@} */
1907 
1908 
1909 /**@name Interface methods
1910  *
1911  * @{
1912  */
1913 
1914 /** sets up the problem data */
1915 SCIP_RETCODE SCIPprobdataCreate(
1916  SCIP* scip, /**< SCIP data structure */
1917  const char* filename /**< file name */
1918  )
1919 {
1920  SCIP_PROBDATA* probdata;
1921  SCIP_CONS* cons;
1922  SCIP_Real offset;
1923  SCIP_Real oldtimelimit;
1924  SCIP_Real presoltimelimit;
1925  PRESOL presolinfo;
1926  GRAPH* graph;
1927  GRAPH* packedgraph;
1928  SCIP_Bool pc;
1929  SCIP_Bool mw;
1930  SCIP_Bool rpc;
1931  SCIP_Bool print;
1932  int nedges;
1933  int nnodes;
1934  int symcons;
1935  int cyclecons;
1936  int reduction;
1937  int realnterms;
1938  int compcentral;
1939  char mode;
1940  char probtype[16];
1941  char* intlogfilename;
1942  char* logfilename;
1943  char tmpfilename[SCIP_MAXSTRLEN];
1944  char* probname;
1945 
1946  assert(scip != NULL);
1947 
1948  presolinfo.fixed = 0;
1949 
1950  /* create graph */
1951  SCIP_CALL( graph_load(scip, &graph, filename, &presolinfo) );
1952 
1953  SCIPdebugMessage("load type :: %d \n\n", graph->stp_type);
1954  SCIPdebugMessage("fixed: %f \n\n", presolinfo.fixed );
1955 
1956  mw = (graph->stp_type == STP_MWCSP);
1957  pc = (graph->stp_type == STP_PCSPG);
1958  rpc = (graph->stp_type == STP_RPCSPG);
1959 
1960  /* create problem data */
1961  SCIP_CALL( probdataCreate(scip, &probdata, graph) );
1962 
1963  /* get parameters */
1964  SCIP_CALL( SCIPgetCharParam(scip, "stp/mode", &mode) );
1965  SCIP_CALL( SCIPgetIntParam(scip, "stp/compcentral", &compcentral) );
1966  SCIP_CALL( SCIPgetIntParam(scip, "stp/reduction", &reduction) );
1967  SCIP_CALL( SCIPgetIntParam(scip, "stp/usesymcons", &(symcons)) );
1968  SCIP_CALL( SCIPgetIntParam(scip, "stp/usecyclecons", &(cyclecons)) );
1969  SCIP_CALL( SCIPgetIntParam(scip, "stp/minelims", &(probdata->minelims)) );
1970  SCIP_CALL( SCIPgetBoolParam(scip, "stp/emitgraph", &(probdata->emitgraph)) );
1971  SCIP_CALL( SCIPgetBoolParam(scip, "stp/bigt", &(probdata->bigt)) );
1972  SCIP_CALL( SCIPgetBoolParam(scip, "stp/printGraph", &print) );
1973  SCIP_CALL( SCIPgetStringParam(scip, "stp/logfile", &logfilename) );
1974  SCIP_CALL( SCIPgetStringParam(scip, "stp/intlogfile", &intlogfilename) );
1975 
1976  /* copy filename */
1977  (void) SCIPsnprintf(tmpfilename, SCIP_MAXSTRLEN, "%s", filename);
1978  SCIPsplitFilename(tmpfilename, NULL, &probname, NULL, NULL);
1979 
1980  if( logfilename != NULL && logfilename[0] != '\0' )
1981  {
1982  char finalfilename[SCIP_MAXSTRLEN];;
1983 
1984  if( strcmp("use_probname", logfilename) == 0 )
1985  (void) SCIPsnprintf(finalfilename, SCIP_MAXSTRLEN, "%s.stplog", probname);
1986  else
1987  (void) SCIPsnprintf(finalfilename, SCIP_MAXSTRLEN, "%s", logfilename);
1988 
1989  probdata->logfile = fopen(finalfilename, "w");
1990 
1991  if( probdata->logfile == NULL )
1992  {
1993  SCIPerrorMessage("cannot create file <%s> for writing\n", finalfilename);
1994  SCIPprintSysError(finalfilename);
1995  return SCIP_FILECREATEERROR;
1996  }
1997  }
1998 
1999  if( intlogfilename != NULL && intlogfilename[0] != '\0' )
2000  {
2001  char finalfilename[SCIP_MAXSTRLEN];
2002 
2003  if( strcmp("use_probname", intlogfilename) == 0 )
2004  (void) SCIPsnprintf(finalfilename, SCIP_MAXSTRLEN, "%s_int.stplog", probname);
2005  else
2006  (void) SCIPsnprintf(finalfilename, SCIP_MAXSTRLEN, "%s", intlogfilename);
2007 
2008  probdata->intlogfile = fopen(finalfilename, "w");
2009 
2010  if( probdata->intlogfile == NULL )
2011  {
2012  SCIPerrorMessage("cannot create file <%s> for writing\n", finalfilename);
2013  SCIPprintSysError(finalfilename);
2014  return SCIP_FILECREATEERROR;
2015  }
2016  }
2017 
2018  /* create a problem in SCIP and add non-NULL callbacks via setter functions */
2019  SCIP_CALL( SCIPcreateProbBasic(scip, probname) );
2020  SCIP_CALL( SCIPsetProbDelorig(scip, probdelorigStp) );
2021  SCIP_CALL( SCIPsetProbTrans(scip, probtransStp) );
2022  SCIP_CALL( SCIPsetProbDeltrans(scip, probdeltransStp) );
2023  SCIP_CALL( SCIPsetProbInitsol(scip, probinitsolStp) );
2024  SCIP_CALL( SCIPsetProbExitsol(scip, probexitsolStp) );
2025  SCIP_CALL( SCIPsetProbCopy(scip, probcopyStp) );
2026 
2027  /* set objective sense */
2028  SCIP_CALL( SCIPsetObjsense(scip, SCIP_OBJSENSE_MINIMIZE) );
2029 
2030  /* set user problem data */
2031  SCIP_CALL( SCIPsetProbData(scip, probdata) );
2032 
2033  if( graph->stp_type == STP_DHCSTP )
2034  {
2035  SCIP_CALL(SCIPsetIntParam(scip, "constraints/knapsack/propfreq", -1));
2036  SCIP_CALL(SCIPsetIntParam(scip, "constraints/logicor/propfreq", -1));
2037  SCIP_CALL(SCIPsetIntParam(scip, "separating/flowcover/freq", -1));
2038  SCIP_CALL(SCIPsetIntParam(scip, "heuristics/locks/freq", -1));
2039  SCIP_CALL(SCIPsetIntParam(scip, "heuristics/rounding/freq", -1));
2040  }
2041 
2042  SCIPprobdataWriteLogLine(scip, "SECTION Comment\n");
2043  SCIPprobdataWriteLogLine(scip, "Name %s\n", filename);
2044 
2045  switch( graph->stp_type )
2046  {
2047  case STP_SPG:
2048  strcpy(probtype, "SPG");
2049  break;
2050  case STP_SAP:
2051  strcpy(probtype, "SAP");
2052  break;
2053 
2054  case STP_PCSPG:
2055  strcpy(probtype, "PCSPG");
2056  break;
2057 
2058  case STP_RPCSPG:
2059  strcpy(probtype, "RPCST");
2060  break;
2061 
2062  case STP_NWSPG:
2063  strcpy(probtype, "NWSPG");
2064  break;
2065 
2066  case STP_DCSTP:
2067  strcpy(probtype, "DCST");
2068  break;
2069 
2070  case STP_RSMT:
2071  strcpy(probtype, "RSMT");
2072  break;
2073 
2074  case STP_OARSMT:
2075  strcpy(probtype, "OARSMT");
2076  break;
2077 
2078  case STP_MWCSP:
2079  strcpy(probtype, "MWCS");
2080  break;
2081 
2082  case STP_RMWCSP:
2083  strcpy(probtype, "RMWCS");
2084  break;
2085 
2086  case STP_DHCSTP:
2087  strcpy(probtype, "HCDST");
2088  break;
2089 
2090  default:
2091  strcpy(probtype, "UNKNOWN");
2092  }
2093  SCIPprobdataWriteLogLine(scip, "Problem %s\n", probtype);
2094  SCIPprobdataWriteLogLine(scip, "Program SCIP-Jack\n");
2095  SCIPprobdataWriteLogLine(scip, "Version %s\n", VERSION_SCIPJACK);
2096  SCIPprobdataWriteLogLine(scip, "End\n");
2097  SCIPprobdataWriteLogLine(scip, "\n");
2098  SCIPprobdataWriteLogLine(scip, "SECTION Solutions\n");
2099 
2100  /* set solving mode */
2101  if( !(graph->stp_type == STP_SPG) )
2102  {
2103  probdata->mode = MODE_CUT;
2104  }
2105  if( mode == 'f' )
2106  {
2107  assert(graph->stp_type == STP_SPG);
2108  probdata->mode = MODE_FLOW;
2109  }
2110  else if( mode == 'p' )
2111  {
2112  assert(graph->stp_type == STP_SPG);
2113  probdata->mode = MODE_PRICE;
2114  }
2115  else
2116  {
2117  assert(mode == 'c');
2118  probdata->mode = MODE_CUT;
2119  }
2120 
2121  assert(graph != NULL );
2122 
2123  /* select a root node */
2124  if( compcentral != CENTER_DEG && !pc && !mw && !rpc && graph->stp_type != STP_DHCSTP && graph->stp_type != STP_SAP && graph->stp_type != STP_RMWCSP )
2125  SCIP_CALL( central_terminal(scip, graph, &(graph->source), compcentral) );
2126 
2127  /* print the graph */
2128  if( print )
2129  {
2130  SCIP_CALL( probdataPrintGraph(graph, "OriginalGraph.gml", NULL) );
2131  }
2132 
2133  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &oldtimelimit) );
2134  SCIP_CALL( SCIPgetRealParam(scip, "stp/pretimelimit", &presoltimelimit) );
2135 
2136  if( presoltimelimit > -0.5 )
2137  {
2138  SCIP_CALL( SCIPsetRealParam(scip, "limits/time", presoltimelimit) );
2139  }
2140 
2141  /* save original root */
2142  graph->orgsource = graph->source;
2143 
2144  probdata->norgedges = graph->edges;
2145 
2146  /* presolving */
2147  SCIP_CALL( reduce(scip, &graph, &offset, reduction, probdata->minelims, TRUE) );
2148  SCIP_CALL( graph_pack(scip, graph, &packedgraph, TRUE) );
2149 
2150  graph = packedgraph;
2151  probdata->stp_type = graph->stp_type;
2152 
2153 #ifdef WITH_UG
2154  {
2155  GRAPH* newgraph;
2156  graph_copy(scip, graph, &(newgraph));
2157  probdata->orggraph = graph;
2158  graph = newgraph;
2159  }
2160 #endif
2161 
2162  probdata->graph = graph;
2163 
2164 #ifndef WITH_UG
2165  if( (graph->edges > CUT_MAXTOTNEDGES) || ((graph->edges > CUT_MAXNEDGES) && (graph->terms > CUT_MAXNTERMINALS)) )
2166  {
2167  SCIP_CALL(SCIPsetIntParam(scip, "separating/aggregation/maxroundsroot", 3));
2168  SCIP_CALL(SCIPsetIntParam(scip, "separating/strongcg/maxroundsroot", 3));
2169  SCIP_CALL(SCIPsetIntParam(scip, "separating/gomory/maxroundsroot", 3));
2170  SCIP_CALL(SCIPsetIntParam(scip, "separating/zerohalf/maxroundsroot", 3));
2171  }
2172 #endif
2173 
2174  SCIP_CALL(SCIPsetIntParam(scip, "separating/clique/freq", -1));
2175 
2176  if( mw )
2177  {
2178  SCIP_CALL(SCIPsetIntParam(scip, "heuristics/rounding/freq", -1));
2179  SCIP_CALL(SCIPsetIntParam(scip, "heuristics/trivial/freq", -1));
2180  }
2181  SCIP_CALL( SCIPsetRealParam(scip, "limits/time", oldtimelimit) );
2182 
2183  if( pc )
2184  {
2185  SCIP_CALL(SCIPsetIntParam(scip, "constraints/logicor/presoltiming", 4));
2186  }
2187 
2188  /* update type for MWCSP (might be RMWCSP now) */
2189  mw = (graph->stp_type == STP_MWCSP);
2190 
2191  probdata->usesymcons = FALSE;
2192  probdata->usecyclecons = FALSE;
2193 
2194  if( pc || mw )
2195  {
2196  if( cyclecons == CONS_ALWAYS || (cyclecons == CONS_SPECIFIC && graph->edges <= CYC_CONS_LIMIT) )
2197  probdata->usecyclecons = TRUE;
2198 
2199  if( symcons == CONS_ALWAYS || (symcons == CONS_SPECIFIC && graph->terms <= SYM_CONS_LIMIT) )
2200  probdata->usesymcons = TRUE;
2201 
2202  if( probdata->usesymcons )
2203  SCIPdebugMessage("USE SYM CONS: %d \n", graph->terms);
2204  else
2205  SCIPdebugMessage("NO SYM CONS: \n");
2206  }
2207 
2208  /* create model */
2209  if( graph != NULL )
2210  {
2211  int t;
2212  int k;
2213 
2214  /* init shortest path algorithm (needed for creating path variables) */
2215  SCIP_CALL( graph_path_init(scip, graph) );
2216 
2217 #ifdef WITH_UG
2218  SCIP_CALL( graph_path_init(scip, probdata->orggraph) );
2219 #endif
2220 
2221  if( probdata->mode == MODE_CUT )
2222  {
2223  SCIP_CALL( graph_mincut_init(scip, graph) );
2224  }
2225 
2226  if( print )
2227  {
2228  SCIP_CALL( probdataPrintGraph(graph, "ReducedGraph.gml", NULL) );
2229  }
2230 
2231  nedges = graph->edges;
2232  nnodes = graph->knots;
2233  probdata->nvars = nedges;
2234  probdata->nnodes = nnodes;
2235  probdata->nedges = nedges;
2236  probdata->nterms = graph->terms;
2237  probdata->nlayers = graph->layers;
2238 
2239  assert(Is_term(graph->term[graph->source]));
2240 
2241  /* compute the real number of terminals (nterm-1 iff root is a terminal) */
2242  realnterms = graph->terms - 1;
2243  probdata->realnterms = realnterms;
2244 
2245  /* set up array of terminals (except for the root) */
2246  SCIP_CALL( SCIPallocMemoryArray(scip, &probdata->realterms, realnterms) );
2247  t = 0;
2248  for( k = 0; k < nnodes; ++k )
2249  {
2250  if( graph->term[k] == 0 && k != graph->source )
2251  {
2252  probdata->realterms[t] = k;
2253  SCIPdebugMessage("realterms[%d] = %d \n ", t, probdata->realterms[t]);
2254  t += 1;
2255  }
2256  }
2257 
2258  if( probdata->mode == MODE_CUT )
2259  {
2260  /* create and add constraint for Branch and Cut */
2261  SCIP_CALL( SCIPcreateConsStp(scip, &cons, "stpcons", probdata->graph) );
2262  SCIP_CALL( SCIPaddCons(scip, cons) );
2263  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2264 
2265  /* if the problem is a HOP-Constrained-STP, an additional constraint is required */
2266  if( graph->stp_type == STP_DHCSTP )
2267  {
2268  SCIP_CALL( createHopConstraint(scip, probdata) );
2269  }
2270 
2271  /* if the problem is a Degree-Constrained-STP, additional constraints are required */
2272  if( graph->stp_type == STP_DCSTP )
2273  {
2274  SCIP_CALL( createDegreeConstraints(scip, probdata) );
2275  }
2276 
2277  /* if the problem is a Prize-Collecting-STP or a Maximum Weight Connected Subgraph Problem, additional constraints are required */
2278  if( pc || rpc || mw )
2279  {
2280  SCIP_CALL( createPrizeConstraints(scip, probdata) );
2281  }
2282 #if FLOWB
2283  SCIP_CALL( createFlowBalanceConstraints(scip, probdata) );
2284 #endif
2285  }
2286  else
2287  {
2288  /* create and add constraints for Flow or Branch and Price */
2289  SCIP_CALL( createConstraints(scip, probdata) );
2290  }
2291  }
2292  /* graph reduction solved the whole problem, set vars to zero or NULL */
2293  else
2294  {
2295  probdata->pathcons = NULL;
2296  probdata->edgecons = NULL;
2297  probdata->nlayers = 0;
2298  probdata->nnodes = 0;
2299  probdata->nedges = 0;
2300  probdata->nterms = 0;
2301  probdata->nnonterms = 0;
2302  probdata->realnterms = 0;
2303  probdata->nedges = 0;
2304  probdata->nvars = 0;
2305  probdata->realterms = NULL;
2306  probdata->xval = NULL;
2307  }
2308 
2309  /* setting the offset to the fixed value given in the input file plus the fixings given by the reduction techniques */
2310  probdata->offset = presolinfo.fixed + offset;
2311 
2312  /* create and add initial variables */
2313  SCIP_CALL( createVariables(scip, probdata, probdata->offset ) );
2314 
2315  assert(probdata->edgevars != NULL);
2316 #ifdef PRINT_PRESOL
2317  (void)SCIPsnprintf(presolvefilename, SCIP_MAXSTRLEN, "presol/%s-presolve.stp", probname);
2318  SCIP_CALL( SCIPwriteOrigProblem(scip, presolvefilename, NULL, FALSE) );
2319 #endif
2320 
2321  if( graph != NULL && probdata->mode == MODE_CUT )
2322  {
2323  SCIP_Real lpobjval;
2324 
2325  if( pc || mw )
2326  {
2327  SCIP_CALL( SCIPStpDualAscentPcMw(scip, graph, NULL, &lpobjval, TRUE, TRUE, 1) );
2328  }
2329  else
2330  {
2331  if( graph->stp_type != STP_RPCSPG && graph->stp_type != STP_SPG && graph->stp_type != STP_RSMT && graph->stp_type != STP_OARSMT && graph->stp_type != STP_GSTP )
2332  {
2333  SCIP_CALL( SCIPStpDualAscent(scip, graph, NULL, NULL, &lpobjval, TRUE, FALSE, NULL, NULL, NULL, NULL, graph->source, FALSE, -1.0, NULL) );
2334  }
2335  else
2336  {
2337  SCIP_CALL( SCIPStpDualAscent(scip, graph, NULL, NULL, &lpobjval, TRUE, TRUE, NULL, NULL, NULL, NULL, graph->source, FALSE, -1.0, NULL) );
2338  }
2339  }
2340  }
2341  return SCIP_OKAY;
2342 }
2343 
2344 /** sets the probdata graph */
2345 void SCIPprobdataSetGraph(
2346  SCIP_PROBDATA* probdata, /**< problem data */
2347  GRAPH* graph /**< graph data structure */
2348  )
2349 {
2350  assert(probdata != NULL);
2351 
2352  probdata->graph = graph;
2353 }
2354 
2355 
2356 /** returns the graph */
2357 GRAPH* SCIPprobdataGetGraph(
2358  SCIP_PROBDATA* probdata /**< problem data */
2359  )
2360 {
2361  assert(probdata != NULL);
2362 
2363  return probdata->graph;
2364 }
2365 
2366 /** returns the graph */
2367 GRAPH* SCIPprobdataGetGraph2(
2368  SCIP* scip /**< problem data */
2369  )
2370 {
2371  SCIP_PROBDATA* probdata;
2372 
2373  assert(scip != NULL);
2374 
2375  probdata = SCIPgetProbData(scip);
2376  assert(probdata != NULL);
2377 
2378  return probdata->graph;
2379 }
2380 
2381 /** sets the offset */
2382 void SCIPprobdataSetOffset(
2383  SCIP_PROBDATA* probdata, /**< problem data */
2384  SCIP_Real offset /**< the offset value */
2385  )
2386 {
2387  assert(probdata != NULL);
2388 
2389  probdata->offset = offset;
2390 }
2391 
2392 
2393 /** returns the number of variables */
2394 int SCIPprobdataGetNVars(
2395  SCIP* scip /**< SCIP data structure */
2396  )
2397 {
2398  SCIP_PROBDATA* probdata;
2399 
2400  assert(scip != NULL);
2401 
2402  probdata = SCIPgetProbData(scip);
2403  assert(probdata != NULL);
2404 
2405  return probdata->nvars;
2406 }
2407 
2408 /** returns the array with all variables */
2409 SCIP_VAR** SCIPprobdataGetVars(
2410  SCIP* scip /**< SCIP data structure */
2411  )
2412 {
2413  SCIP_PROBDATA* probdata;
2414 
2415  assert(scip != NULL);
2416 
2417  probdata = SCIPgetProbData(scip);
2418  assert(probdata != NULL);
2419 
2420  return probdata->edgevars;
2421 }
2422 
2423 /** returns the number of layers */
2424 int SCIPprobdataGetNLayers(
2425  SCIP* scip /**< SCIP data structure */
2426  )
2427 {
2428  SCIP_PROBDATA* probdata;
2429 
2430  assert(scip != NULL);
2431 
2432  probdata = SCIPgetProbData(scip);
2433  assert(probdata != NULL);
2434 
2435  return probdata->nlayers;
2436 }
2437 
2438 /** returns the number of edges */
2439 int SCIPprobdataGetNEdges(
2440  SCIP* scip /**< SCIP data structure */
2441  )
2442 {
2443  SCIP_PROBDATA* probdata;
2444 
2445  assert(scip != NULL);
2446 
2447  probdata = SCIPgetProbData(scip);
2448  assert(probdata != NULL);
2449 
2450  return probdata->nedges;
2451 }
2452 
2453 /** returns the number of terminals */
2454 int SCIPprobdataGetNTerms(
2455  SCIP* scip /**< SCIP data structure */
2456  )
2457 {
2458  SCIP_PROBDATA* probdata;
2459 
2460  assert(scip != NULL);
2461 
2462  probdata = SCIPgetProbData(scip);
2463  assert(probdata != NULL);
2464 
2465  return probdata->nterms;
2466 }
2467 
2468 /** returns the number of terminals without the root node */
2469 int SCIPprobdataGetRNTerms(
2470  SCIP* scip /**< SCIP data structure */
2471  )
2472 {
2473  SCIP_PROBDATA* probdata;
2474 
2475  assert(scip != NULL);
2476 
2477  probdata = SCIPgetProbData(scip);
2478  assert(probdata != NULL);
2479 
2480  return probdata->realnterms;
2481 }
2482 
2483 /** returns root */
2484 int SCIPprobdataGetRoot(
2485  SCIP* scip /**< SCIP data structure */
2486  )
2487 {
2488  SCIP_PROBDATA* probdata;
2489  GRAPH* graph;
2490 
2491  assert(scip != NULL);
2492 
2493  probdata = SCIPgetProbData(scip);
2494  assert(probdata != NULL);
2495 
2496  graph = probdata->graph;
2497  assert(graph != NULL);
2498 
2499  return graph->source;
2500 }
2501 
2502 /** returns numer of original edges */
2503 int SCIPprobdataGetNorgEdges(
2504  SCIP* scip /**< SCIP data structure */
2505  )
2506 {
2507  SCIP_PROBDATA* probdata;
2508 
2509  assert(scip != NULL);
2510 
2511  probdata = SCIPgetProbData(scip);
2512  assert(probdata != NULL);
2513 
2514  return probdata->norgedges;
2515 }
2516 
2517 /** returns offset of the problem */
2518 SCIP_Real SCIPprobdataGetOffset(
2519  SCIP* scip /**< SCIP data structure */
2520  )
2521 {
2522  SCIP_PROBDATA* probdata;
2523 
2524  assert(scip != NULL);
2525 
2526  probdata = SCIPgetProbData(scip);
2527  assert(probdata != NULL);
2528 
2529  return probdata->offset;
2530 }
2531 
2532 
2533 /** returns the variable for a given index */
2534 SCIP_VAR* SCIPprobdataGetedgeVarByIndex(
2535  SCIP* scip, /**< SCIP data structure */
2536  int idx /**< index of the edge */
2537  )
2538 {
2539  SCIP_PROBDATA* probdata;
2540 
2541  assert(scip != NULL);
2542 
2543  probdata = SCIPgetProbData(scip);
2544  assert(probdata != NULL);
2545 
2546  return probdata->edgevars[idx];
2547 }
2548 
2549 
2550 /** returns the LP solution values */
2551 SCIP_Real* SCIPprobdataGetXval(
2552  SCIP* scip, /**< SCIP data structure */
2553  SCIP_SOL* sol /**< solution to get values from */
2554  )
2555 {
2556  SCIP_PROBDATA* probdata;
2557  SCIP_Real* vals;
2558  int e;
2559  int nedges;
2560  assert(scip != NULL);
2561 
2562  probdata = SCIPgetProbData(scip);
2563  assert(probdata != NULL);
2564  vals = probdata->xval;
2565 
2566  nedges = probdata->nedges;
2567  assert(nedges >= 0);
2568 
2569  SCIP_CALL_ABORT( SCIPgetSolVals(scip, sol, nedges, probdata->edgevars, vals) );
2570 
2571  for( e = 0; e < nedges; e++ )
2572  vals[e] = fmax(0.0, fmin(vals[e], 1.0));
2573 
2574  return vals;
2575 }
2576 
2577 
2578 /** returns all edge constraints */
2579 SCIP_CONS** SCIPprobdataGetEdgeConstraints(
2580  SCIP* scip /**< SCIP data structure */
2581  )
2582 {
2583  SCIP_PROBDATA* probdata;
2584 
2585  assert(scip != NULL);
2586  probdata = SCIPgetProbData(scip);
2587  assert(probdata != NULL);
2588 
2589  return probdata->edgecons;
2590 }
2591 
2592 /** returns all path constraints */
2593 SCIP_CONS** SCIPprobdataGetPathConstraints(
2594  SCIP* scip /**< SCIP data structure */
2595  )
2596 {
2597  SCIP_PROBDATA* probdata;
2598 
2599  assert(scip != NULL);
2600  probdata = SCIPgetProbData(scip);
2601  assert(probdata != NULL);
2602 
2603  return probdata->pathcons;
2604 }
2605 
2606 
2607 /** returns the array with all variables */
2608 int* SCIPprobdataGetRTerms(
2609  SCIP* scip /**< SCIP data structure */
2610  )
2611 {
2612  SCIP_PROBDATA* probdata;
2613 
2614  assert(scip != NULL);
2615 
2616  probdata = SCIPgetProbData(scip);
2617  assert(probdata != NULL);
2618 
2619  return probdata->realterms;
2620 }
2621 
2622 /** returns the array with all edge variables */
2623 SCIP_VAR** SCIPprobdataGetEdgeVars(
2624  SCIP* scip /**< SCIP data structure */
2625  )
2626 {
2627  SCIP_PROBDATA* probdata;
2628 
2629  assert(scip != NULL);
2630 
2631  probdata = SCIPgetProbData(scip);
2632  assert(probdata != NULL);
2633 
2634  return probdata->edgevars;
2635 }
2636 
2637 /* returns if 'T' model is being used */
2638 SCIP_Bool SCIPprobdataIsBigt(
2639  SCIP* scip /**< SCIP data structure */
2640  )
2641 {
2642  SCIP_PROBDATA* probdata;
2643 
2644  assert(scip != NULL);
2645 
2646  probdata = SCIPgetProbData(scip);
2647  assert(probdata != NULL);
2648 
2649  return probdata->bigt;
2650 }
2651 
2652 /** print (undirected) graph in GML format */
2653 SCIP_RETCODE SCIPprobdataPrintGraph(
2654  SCIP* scip, /**< SCIP data structure */
2655  const char* filename, /**< name of the output file */
2656  SCIP_SOL* sol, /**< solution to be printed; or NULL for LP solution */
2657  SCIP_Bool printsol /**< should solution be printed? */
2658  )
2659 {
2660  SCIP_PROBDATA* probdata;
2661  SCIP_VAR** edgevars;
2662  SCIP_Bool* edgemark;
2663  int e;
2664 
2665  assert(scip != NULL);
2666  probdata = SCIPgetProbData(scip);
2667  assert(probdata != NULL);
2668 
2669  if( !printsol )
2670  {
2671  /* print the graph without highlighting a solution */
2672  SCIP_CALL( probdataPrintGraph( probdata->graph, filename, NULL) );
2673  }
2674  else
2675  {
2676  edgevars = probdata->edgevars;
2677  SCIP_CALL( SCIPallocBufferArray(scip, &edgemark, probdata->nedges / 2) );
2678 
2679  /* mark the edges used in the current solution */
2680  for( e = 0; e < probdata->graph->edges; e += 2 )
2681  if( !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e])) || !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e + 1])) )
2682  edgemark[e / 2] = TRUE;
2683  else
2684  edgemark[e / 2] = FALSE;
2685 
2686  /* print the graph highlighting a solution */
2687  SCIP_CALL( probdataPrintGraph( probdata->graph, filename, edgemark) );
2688 
2689  SCIPfreeBufferArray(scip, &edgemark);
2690  }
2691 
2692  return SCIP_OKAY;
2693 }
2694 
2695 
2696 /** writes the best solution to the intermediate solution file */
2697 SCIP_RETCODE SCIPprobdataWriteIntermediateSolution(
2698  SCIP* scip /**< SCIP data structure */
2699  )
2700 {
2701  SCIP_PROBDATA* probdata;
2702  probdata = SCIPgetProbData(scip);
2703 
2704  if( probdata->intlogfile != NULL )
2705  {
2706  SCIP_CALL( SCIPprobdataWriteSolution(scip, probdata->intlogfile) );
2707  }
2708 
2709  return SCIP_OKAY;
2710 }
2711 
2712 /** writes SPG (no variant!) to a file */
2713 void SCIPprobdataWriteStp(
2714  SCIP* scip, /**< SCIP data structure */
2715  const GRAPH* graph, /**< graph data structure */
2716  const char* filename /**< file name */
2717  )
2718 {
2719  FILE *fptr;
2720 
2721  assert(scip != NULL);
2722  assert(graph != NULL);
2723 
2724  fptr = fopen(filename, "w");
2725  assert(fptr != NULL);
2726 
2727  fprintf(fptr, "33D32945 STP File, STP Format Version 1.0\n");
2728  fprintf(fptr, "SECTION Comment\n");
2729  fprintf(fptr, "END\n\n");
2730  fprintf(fptr, "SECTION Graph\n");
2731  fprintf(fptr, "Nodes %d\n", graph->knots);
2732  fprintf(fptr, "Edges %d\n", graph->edges);
2733 
2734  for( int e = 0; e < graph->edges; e += 2 )
2735  fprintf(fptr, "E %d %d %f\n", graph->tail[e] + 1, graph->head[e] + 1, graph->cost[e]);
2736  fprintf(fptr, "END\n\n");
2737 
2738  fprintf(fptr, "SECTION Terminals\n");
2739  fprintf(fptr, "Terminals %d\n", graph->terms);
2740 
2741  for( int k = 0; k < graph->knots; k++ )
2742  if( Is_term(graph->term[k]) )
2743  fprintf(fptr, "T %d\n", k + 1);
2744 
2745  fprintf(fptr, "END\n\n");
2746 
2747  fprintf(fptr, "EOF\n");
2748 
2749  fclose(fptr);
2750 }
2751 
2752 /** writes the best solution to a file */
2753 SCIP_RETCODE SCIPprobdataWriteSolution(
2754  SCIP* scip, /**< SCIP data structure */
2755  FILE* file /**< file to write best solution to; or NULL, to write to stdout */
2756  )
2757 {
2758  SCIP_SOL* sol;
2759  SCIP_VAR** edgevars;
2760  GRAPH* graph;
2761  IDX** ancestors;
2762  IDX* curr;
2763  SCIP_PROBDATA* probdata;
2764  int e;
2765  int k;
2766  int norgedges;
2767  int norgnodes;
2768  int nsolnodes;
2769  int nsoledges;
2770  STP_Bool* orgedges;
2771  STP_Bool* orgnodes;
2772 
2773  assert(scip != NULL);
2774 
2775  probdata = SCIPgetProbData(scip);
2776 
2777  assert(probdata != NULL);
2778 
2779  edgevars = probdata->edgevars;
2780 #ifdef WITH_UG
2781  graph = probdata->orggraph;
2782 #else
2783  graph = probdata->graph;
2784 #endif
2785 
2786  assert(graph != NULL);
2787 
2788  sol = SCIPgetBestSol(scip);
2789 
2790  nsolnodes = 0;
2791  nsoledges = 0;
2792  norgedges = graph->orgedges;
2793  norgnodes = graph->orgknots;
2794 
2795  assert(norgedges >= 0);
2796  assert(norgnodes >= 1);
2797 
2798  SCIP_CALL( SCIPallocBufferArray(scip, &orgedges, norgedges) );
2799  SCIP_CALL( SCIPallocBufferArray(scip, &orgnodes, norgnodes) );
2800 
2801  for( e = 0; e < norgedges; e++ )
2802  orgedges[e] = FALSE;
2803  for( k = 0; k < norgnodes; k++ )
2804  orgnodes[k] = FALSE;
2805 
2806  ancestors = graph->ancestors;
2807 
2808  if( graph->stp_type == STP_SPG || graph->stp_type == STP_SAP ||graph->stp_type == STP_DCSTP
2809  || graph->stp_type == STP_NWSPG || graph->stp_type == STP_DHCSTP || graph->stp_type == STP_GSTP || graph->stp_type == STP_RSMT )
2810  {
2811  GRAPH* solgraph;
2812  SCIP_QUEUE* queue;
2813  int* nodechild;
2814  int* edgeancestor;
2815  int* pnode;
2816  int tail;
2817  int head;
2818 
2819  /* iterate through the list of fixed edges */
2820  updateorgsol(graph, graph->fixedges, orgnodes, orgedges, &nsolnodes, &nsoledges);
2821 
2822  for( e = 0; e < graph->edges; e++ )
2823  if( !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e])) )
2824  /* iterate through the list of ancestors */
2825  updateorgsol(graph, ancestors[e], orgnodes, orgedges, &nsolnodes, &nsoledges);
2826 
2827 #if 1
2828  SCIP_CALL( SCIPallocBufferArray(scip, &nodechild, norgnodes) );
2829  SCIP_CALL( SCIPallocBufferArray(scip, &edgeancestor, 2 * nsoledges) );
2830 
2831  /* initialize new graph */
2832  SCIP_CALL( graph_init(scip, &solgraph, nsolnodes, 2 * nsoledges, 1) );
2833 
2834  /* add vertices to new graph */
2835  for( k = 0; k < norgnodes; k++ )
2836  {
2837  if( orgnodes[k] )
2838  {
2839  nodechild[k] = solgraph->knots;
2840  graph_knot_add(solgraph, -1);
2841  }
2842  else
2843  {
2844  nodechild[k] = -1;
2845  }
2846  }
2847 
2848  assert(nsolnodes == solgraph->knots);
2849  assert(nodechild[graph->orgsource] >= 0);
2850 
2851  /* set root of new graph */
2852  solgraph->source = nodechild[graph->orgsource];
2853 
2854  /* add edges to new graph */
2855  for( e = 0; e < norgedges; e++ )
2856  {
2857  if( !orgedges[e] )
2858  continue;
2859 
2860  tail = nodechild[graph->orgtail[e]];
2861  head = nodechild[graph->orghead[e]];
2862 
2863  assert(tail >= 0);
2864  assert(head >= 0);
2865 
2866  edgeancestor[solgraph->edges] = e;
2867  edgeancestor[solgraph->edges + 1] = flipedge(e);
2868  graph_edge_add(scip, solgraph, tail, head, 1.0, 1.0);
2869  }
2870 
2871  for( e = 0; e < norgedges; e++ )
2872  orgedges[e] = FALSE;
2873 
2874  for( k = 0; k < norgnodes; k++ )
2875  orgnodes[k] = FALSE;
2876 
2877  SCIP_CALL( SCIPqueueCreate(&queue, nsolnodes, 1.1) );
2878  SCIP_CALL( SCIPqueueInsert(queue, &(solgraph->source)) );
2879  solgraph->mark[solgraph->source] = FALSE;
2880 
2881  nsolnodes = 1;
2882 
2883  /* BFS from root */
2884  while( !SCIPqueueIsEmpty(queue) )
2885  {
2886  pnode = (SCIPqueueRemove(queue));
2887  k = *pnode;
2888 
2889  /* traverse outgoing arcs */
2890  for( e = solgraph->outbeg[k]; e != EAT_LAST; e = solgraph->oeat[e] )
2891  {
2892  head = solgraph->head[e];
2893 
2894  /* vertex not labeled yet? */
2895  if( solgraph->mark[head] )
2896  {
2897  orgedges[edgeancestor[e]] = TRUE;
2898  solgraph->mark[head] = FALSE;
2899  nsolnodes++;
2900  SCIP_CALL(SCIPqueueInsert(queue, &(solgraph->head[e])));
2901  }
2902  }
2903  }
2904 
2905  nsoledges = nsolnodes - 1;
2906 
2907  SCIPqueueFree(&queue);
2908 
2909  graph_free(scip, &solgraph, TRUE);
2910 
2911  for( e = 0; e < norgedges; e++ )
2912  {
2913  if( orgedges[e] )
2914  {
2915  orgnodes[graph->orgtail[e]] = TRUE;
2916  orgnodes[graph->orghead[e]] = TRUE;
2917  }
2918  }
2919 
2920  SCIPfreeBufferArray(scip, &edgeancestor);
2921  SCIPfreeBufferArray(scip, &nodechild);
2922 #endif
2923  if( graph->stp_type == STP_GSTP )
2924  {
2925  norgnodes -= graph->terms;
2926  nsolnodes -= graph->terms;
2927  nsoledges -= graph->terms;
2928  assert(nsolnodes >= 0);
2929  assert(nsoledges >= 1);
2930  }
2931 
2932  SCIPprobdataWriteLogLine(scip, "Vertices %d\n", nsolnodes);
2933 
2934  for( k = 0; k < norgnodes; k++ )
2935  if( orgnodes[k] == TRUE )
2936  SCIPinfoMessage(scip, file, "V %d\n", k + 1);
2937 
2938  SCIPprobdataWriteLogLine(scip, "Edges %d\n", nsoledges);
2939 
2940  if( graph->stp_type == STP_DHCSTP )
2941  {
2942  for( e = 0; e < norgedges; e++ )
2943  if( orgedges[e] == TRUE )
2944  SCIPinfoMessage(scip, file, "E %d %d\n", graph->orgtail[e] + 1, graph->orghead[e] + 1);
2945  }
2946  else
2947  {
2948  for( e = 0; e < norgedges; e += 2 )
2949  {
2950  if( graph->stp_type == STP_GSTP && (Is_term(graph->term[graph->orgtail[e]]) || Is_term(graph->term[graph->orghead[e]])) )
2951  continue;
2952  if( orgedges[e] == TRUE || orgedges[e + 1] == TRUE )
2953  SCIPinfoMessage(scip, file, "E %d %d\n", graph->orgtail[e] + 1, graph->orghead[e] + 1);
2954  }
2955  }
2956  }
2957  else if( graph->stp_type == STP_RSMT )
2958  {
2959  int** coords;
2960  int* ncoords;
2961  int* nodecoords;
2962  int* nodenumber;
2963  int i;
2964  int nodecount;
2965  int grid_dim;
2966  char strdim[256];
2967  coords = graph->grid_coordinates;
2968  assert(coords != NULL);
2969  ncoords = graph->grid_ncoords;
2970  nodecoords = NULL;
2971  grid_dim = graph->grid_dim;
2972  assert(grid_dim > 1);
2973  assert(grid_dim < 256);
2974  SCIP_CALL( SCIPallocBufferArray(scip, &nodenumber, norgnodes) );
2975  strcpy(strdim, "P");
2976  for( i = 1; i < grid_dim; i++ )
2977  strcat(strdim, "P");
2978 
2979  assert(ncoords != NULL);
2980 
2981  /* mark solution nodes and edges */
2982  for( e = 0; e < norgedges; e++ )
2983  {
2984  if( !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e])) )
2985  {
2986  nsoledges++;
2987  assert(orgedges[e] == FALSE);
2988  orgedges[e] = TRUE;
2989  if( orgnodes[graph->tail[e]] == FALSE )
2990  {
2991  orgnodes[graph->tail[e]] = TRUE;
2992  nsolnodes++;
2993  }
2994  if( orgnodes[graph->head[e]] == FALSE )
2995  {
2996  orgnodes[graph->head[e]] = TRUE;
2997  nsolnodes++;
2998  }
2999  }
3000  }
3001 
3002  SCIPprobdataWriteLogLine(scip, "Edges %d\n", nsoledges);
3003  SCIPprobdataWriteLogLine(scip, "Points %d\n", nsolnodes);
3004  nodecount = 0;
3005  for( k = 0; k < norgnodes; k++ )
3006  {
3007  if( orgnodes[k] == TRUE )
3008  {
3009  nodenumber[k] = nodecount++;
3010  SCIPprobdataWriteLogLine(scip, "%s ", strdim);
3011  SCIP_CALL( graph_grid_coordinates(scip, coords, &nodecoords, ncoords, k, grid_dim) );
3012  for( i = 0; i < grid_dim; i++ )
3013  {
3014  SCIPprobdataWriteLogLine(scip, "%d ", nodecoords[i]);
3015  }
3016  SCIPprobdataWriteLogLine(scip, "\n");
3017  }
3018  }
3019  assert(nodecount == nsolnodes);
3020  for( e = 0; e < norgedges; e += 2 )
3021  {
3022  if( orgedges[e] == TRUE || orgedges[e + 1] == TRUE )
3023  SCIPinfoMessage(scip, file, "E %d %d\n", nodenumber[graph->orgtail[e]] + 1, nodenumber[graph->orghead[e]] + 1);
3024  }
3025  SCIPfreeBufferArray(scip, &nodenumber);
3026  }
3027  else if( graph->stp_type == STP_PCSPG || graph->stp_type == STP_MWCSP || graph->stp_type == STP_RMWCSP
3028  || graph->stp_type == STP_RPCSPG )
3029  {
3030  int* solnodequeue;
3031  int root;
3032  root = graph->source;
3033  assert(root >= 0 && nsolnodes == 0);
3034 
3035  SCIP_CALL( SCIPallocBufferArray(scip, &solnodequeue, norgnodes) );
3036 
3037  for( e = 0; e <= graph->edges; e++ )
3038  {
3039  if( e == graph->edges || !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e])) )
3040  {
3041  /* iterate through the list of ancestors/fixed edges */
3042  if( e < graph->edges )
3043  curr = ancestors[e];
3044  else
3045  curr = graph->fixedges;
3046  while (curr != NULL)
3047  {
3048  const int ancestoredge = curr->index;
3049  if( e < graph->edges && (graph->stp_type == STP_MWCSP || graph->stp_type == STP_RMWCSP) )
3050  {
3051  if( !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[flipedge(e)])) )
3052  {
3053  curr = curr->parent;
3054  continue;
3055  }
3056  }
3057 
3058  if( ancestoredge < graph->norgmodeledges )
3059  {
3060  if( !orgedges[ancestoredge] )
3061  {
3062  orgedges[ancestoredge] = TRUE;
3063  nsoledges++;
3064  }
3065  if( !orgnodes[graph->orgtail[ancestoredge]] )
3066  {
3067  orgnodes[graph->orgtail[ancestoredge]] = TRUE;
3068  solnodequeue[nsolnodes++] = graph->orgtail[ancestoredge];
3069  }
3070  if( !orgnodes[graph->orghead[ancestoredge]] )
3071  {
3072  orgnodes[graph->orghead[ancestoredge]] = TRUE;
3073  solnodequeue[nsolnodes++] = graph->orghead[ancestoredge];
3074  }
3075  }
3076  else if( graph->orghead[ancestoredge] < graph->norgmodelknots )
3077  {
3078  if( !orgnodes[graph->orghead[ancestoredge]])
3079  {
3080  orgnodes[graph->orghead[ancestoredge]] = TRUE;
3081  solnodequeue[nsolnodes++] = graph->orghead[ancestoredge];
3082  }
3083  }
3084  curr = curr->parent;
3085  }
3086  }
3087  }
3088  /* cover RPCSPG/RMWCSP with single node solution */
3089  if( (graph->stp_type == STP_RPCSPG || graph->stp_type == STP_RMWCSP) && !orgnodes[root] )
3090  {
3091  assert(nsolnodes == 0);
3092 
3093  solnodequeue[0] = root;
3094  nsolnodes = 1;
3095  }
3096 
3097  SCIP_CALL( graph_sol_markPcancestors(scip, graph->pcancestors, graph->orgtail, graph->orghead, norgnodes,
3098  orgnodes, orgedges, solnodequeue, &nsolnodes, &nsoledges ) );
3099 
3100  SCIPprobdataWriteLogLine(scip, "Vertices %d\n", nsolnodes);
3101 
3102  for( k = 0; k < norgnodes; k++ )
3103  if( orgnodes[k] == TRUE )
3104 
3105  SCIPinfoMessage(scip, file, "V %d\n", k + 1);
3106 
3107  SCIPprobdataWriteLogLine(scip, "Edges %d\n", nsoledges);
3108 
3109  for( e = 0; e < norgedges; e += 2 )
3110  if( orgedges[e] == TRUE || orgedges[e + 1] == TRUE )
3111  SCIPinfoMessage(scip, file, "E %d %d\n", graph->orgtail[e] + 1, graph->orghead[e] + 1);
3112 
3113  SCIPfreeBufferArray(scip, &solnodequeue);
3114  }
3115 
3116  SCIPfreeBufferArray(scip, &orgnodes);
3117  SCIPfreeBufferArray(scip, &orgedges);
3118 
3119  return SCIP_OKAY;
3120 }
3121 
3122 
3123 /** writes a line to the log file */
3124 void SCIPprobdataWriteLogLine(
3125  SCIP* scip, /**< SCIP data structure */
3126  const char* formatstr, /**< format string like in printf() function */
3127  ... /**< format arguments line in printf() function */
3128  )
3129 {
3130  SCIP_PROBDATA* probdata;
3131  va_list ap;
3132 
3133  assert(scip != NULL);
3134 
3135  probdata = SCIPgetProbData(scip);
3136  assert(probdata != NULL);
3137 
3138  if( probdata->logfile != NULL )
3139  {
3140  va_start(ap, formatstr); /*lint !e826*/
3141  SCIPmessageVFPrintInfo(SCIPgetMessagehdlr(scip), probdata->logfile, formatstr, ap);
3142  va_end(ap);
3143  }
3144  if( probdata->intlogfile != NULL )
3145  {
3146  va_start(ap, formatstr); /*lint !e826*/
3147  SCIPmessageVFPrintInfo(SCIPgetMessagehdlr(scip), probdata->intlogfile, formatstr, ap);
3148  va_end(ap);
3149  }
3150 }
3151 
3152 /** add new solution */
3153 SCIP_RETCODE SCIPprobdataAddNewSol(
3154  SCIP* scip, /**< SCIP data structure */
3155  SCIP_Real* nval, /**< array [0..nvars], nval[v] = 1 if node v is in the solution, nval[v] = 0 if not */
3156  SCIP_SOL* sol, /**< the new solution */
3157  SCIP_HEUR* heur, /**< heuristic data */
3158  SCIP_Bool* success /**< denotes whether the new solution has been successfully added */
3159  )
3160 {
3161  SCIP_PROBDATA* probdata;
3162  SCIP_VAR** edgevars;
3163  GRAPH* graph;
3164 
3165  assert(scip != NULL);
3166 
3167  probdata = SCIPgetProbData(scip);
3168  edgevars = probdata->edgevars;
3169 
3170  graph = probdata->graph;
3171  assert(graph != NULL);
3172  assert(edgevars != NULL);
3173 
3174  /* create a new primal solution (initialized to zero) */
3175  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
3176 
3177  /* create path variables (Price mode) or set the flow vars (Flow mode) corresponding to the new solution */
3178  if( probdata->mode != MODE_CUT )
3179  {
3180  SCIP_Real* edgecost;
3181  SCIP_Real* flowvals;
3182  PATH* path;
3183  SCIP_VAR** pathvars;
3184  SCIP_VAR* var = NULL;
3185  char varname[SCIP_MAXSTRLEN];
3186  int realnterms = probdata->realnterms;
3187  int tail;
3188  int nedges = probdata->nedges;
3189  int e;
3190  int t;
3191 
3192  assert(nedges > 0);
3193 
3194  /* allocate memory for the values of the flow variables */
3195  SCIP_CALL( SCIPallocMemoryArray(scip, &flowvals, nedges * (probdata->bigt ? 1 : realnterms)) );
3196  BMSclearMemoryArray(flowvals, nedges * (probdata->bigt ? 1 : realnterms));
3197 
3198  /* allocate memory for the edgecost and the path array (both used for computing shortest paths) */
3199  SCIP_CALL( SCIPallocMemoryArray(scip, &edgecost, nedges) );
3200  SCIP_CALL( SCIPallocMemoryArray(scip, &path, graph->knots) );
3201 
3202  /* Flow mode */
3203  if ( probdata->mode == MODE_FLOW )
3204  {
3205  pathvars = NULL;
3206  }
3207  /* Price mode */
3208  else
3209  {
3210  SCIP_CALL( SCIPallocMemoryArray(scip, &pathvars, realnterms) );
3211  }
3212 
3213  /* mark the tree generated by nvals */
3214  for( e = 0; e < nedges; e++ )
3215  {
3216  if( SCIPisEQ(scip, nval[e], 1.0) )
3217  edgecost[e] = graph->cost[e] / nedges;
3218  else
3219  edgecost[e] = SCIPinfinity(scip);
3220  }
3221 
3222  for( e = 0; e < graph->knots; e++ )
3223  graph->mark[e] = 1;
3224  graph_path_exec(scip, graph, FSP_MODE, graph->source, edgecost, path);
3225 
3226  /* create and add path variables (Price mode) or set the flow variables (Flow mode) */
3227  for( t = 0; t < realnterms; ++t )
3228  {
3229  if( probdata->mode == MODE_PRICE )
3230  {
3231  /* create a new path variable */
3232  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "PathVar%d_X", t);
3233  var = NULL;
3234  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
3235  SCIP_CALL( SCIPaddVar(scip, var) );
3236  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t], var, 1.0) );
3237  SCIP_CALL( SCIPsetSolVal(scip, sol, var, 1.0) );
3238  assert(var != NULL);
3239  assert(pathvars != NULL);
3240  pathvars[t] = var;
3241  }
3242  tail = probdata->realterms[t];
3243 
3244  /* walk from terminal t to the root */
3245  while( tail != graph->source )
3246  {
3247  if( !probdata->bigt )
3248  {
3249  if( probdata->mode == MODE_PRICE )
3250  {
3251  /* add the new path variable to the constraints corresponding to the current edge */
3252  assert(var != NULL);
3253  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + path[tail].edge], var, 1.0) );
3254  }
3255  else
3256  {
3257  /* set the flow variable corresponding to the current edge */
3258  flowvals[t * nedges + path[tail].edge] = 1.0;
3259  }
3260  }
3261  else
3262  {
3263  if( probdata->mode == MODE_PRICE )
3264  {
3265  assert(var != NULL);
3266  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[path[tail].edge], var, 1.0) );
3267  }
3268  else
3269  {
3270  /* increment the flow variable corresponding to the current edge */
3271  flowvals[path[tail].edge] += 1.0;
3272  }
3273  }
3274  tail = graph->tail[path[tail].edge];
3275  }
3276  if( probdata->mode == MODE_PRICE )
3277  {
3278  assert(var != NULL);
3279  SCIP_CALL( SCIPreleaseVar(scip, &var) );
3280  }
3281  }
3282 
3283  /* store the new solution value */
3284  SCIP_CALL( SCIPsetSolVals(scip, sol, probdata->nvars, edgevars, nval) );
3285  if( probdata->mode == MODE_FLOW )
3286  {
3287  SCIP_CALL( SCIPsetSolVals(scip, sol, nedges * (probdata->bigt ? 1 : realnterms) , probdata->flowvars, flowvals) );
3288  }
3289 
3290  /* try to add new solution to scip and free it immediately */
3291  SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, FALSE, TRUE, TRUE, TRUE, success) );
3292 
3293  /* free local arrays */
3294  SCIPfreeMemoryArrayNull(scip, &flowvals);
3295  SCIPfreeMemoryArrayNull(scip, &edgecost);
3296  SCIPfreeMemoryArrayNull(scip, &path);
3297  SCIPfreeMemoryArrayNull(scip, &pathvars);
3298  }
3299  /* cut mode */
3300  else
3301  {
3302  SCIP_Bool feasible;
3303  int e;
3304  int nvars = probdata->nvars;
3305 
3306  /* check whether the new solution is valid with respect to the original bounds */
3307  for( e = 0; e < nvars; e++ )
3308  {
3309  if( SCIPisGT(scip, nval[e], SCIPvarGetUbGlobal(edgevars[e])) || SCIPisGT(scip, SCIPvarGetLbGlobal(edgevars[e]), nval[e]) )
3310  {
3311  SCIPdebugMessage("solution not valid wrt to global bounds: %d %d nval %f ub: %f \n",
3312  graph->tail[e], graph->head[e], nval[e], SCIPvarGetUbGlobal(edgevars[e]) );
3313  *success = FALSE;
3314  SCIP_CALL( SCIPfreeSol(scip, &sol) );
3315  return SCIP_OKAY;
3316  }
3317  }
3318 
3319  /* post-processing of solution for MWCS and PCSPG */
3320  if( graph->stp_type == STP_PCSPG || graph->stp_type == STP_MWCSP )
3321  {
3322  int k;
3323 
3324  for( k = 0; k < graph->knots; ++k )
3325  {
3326  /* is the kth node a terminal other than the root? */
3327  if( Is_term(graph->term[k]) && k != graph->source )
3328  {
3329  int origterm;
3330  int edge1 = graph->inpbeg[k];
3331  int edge2 = graph->ieat[edge1];
3332 
3333  assert(graph->ieat[edge2] == EAT_LAST);
3334 
3335  if( !SCIPisZero(scip, graph->cost[edge2]) )
3336  {
3337  int tmp = edge1;
3338  edge1 = edge2;
3339  edge2 = tmp;
3340  }
3341  assert(SCIPisZero(scip, graph->cost[edge2]));
3342 
3343  if( nval[edge2] > 0.5 )
3344  {
3345  assert(nval[edge1] < 0.5);
3346  continue;
3347  }
3348  assert(nval[edge1] > 0.5);
3349  assert(nval[edge2] < 0.5);
3350 
3351  origterm = graph->tail[edge2];
3352 
3353  for( e = graph->inpbeg[origterm]; e != EAT_LAST; e = graph->ieat[e] )
3354  {
3355  if( nval[e] > 0.5 )
3356  {
3357  nval[edge1] = 0;
3358  nval[edge2] = 1;
3359  break;
3360  }
3361  }
3362  }
3363  }
3364  }
3365 
3366  /* store the new solution value */
3367  SCIP_CALL( SCIPsetSolVals(scip, sol, nvars, edgevars, nval) );
3368 #if USEOFFSETVAR
3369  if( probdata->offsetvar != NULL && SCIPvarIsActive(probdata->offsetvar) )
3370  {
3371  SCIP_CALL( SCIPsetSolVal(scip, sol, probdata->offsetvar, 1.0) );
3372  }
3373 #endif
3374  SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, &feasible) );
3375 
3376  SCIPdebugMessage("checked sol: feasible=%u\n", feasible);
3377 
3378  /* check solution for feasibility in original problem space */
3379  if( !feasible )
3380  {
3381  SCIP_CALL( SCIPcheckSolOrig(scip, sol, &feasible, TRUE, TRUE) );
3382  SCIPdebugMessage("checked sol org: feasible=%u\n", feasible);
3383 
3384  if( feasible )
3385  {
3386  SCIP_SOL* newsol;
3387  SCIP_VAR** origvars;
3388  SCIP_VAR* var;
3389  int norigvars;
3390  int v;
3391 
3392  SCIP_CALL( SCIPcreateOrigSol(scip, &newsol, SCIPsolGetHeur(sol)) );
3393  origvars = SCIPgetOrigVars(scip);
3394  norigvars = SCIPgetNOrigVars(scip);
3395 
3396  for( v = 0; v < norigvars; ++v )
3397  {
3398  var = origvars[v];
3399  SCIP_CALL( SCIPsetSolVal(scip, newsol, var, SCIPgetSolVal(scip, sol, var)) );
3400  }
3401 
3402  SCIP_CALL( SCIPfreeSol(scip, &sol) );
3403  sol = newsol;
3404  }
3405  }
3406 
3407  /* try to add new solution to scip and free it immediately */
3408  if( feasible )
3409  {
3410 #ifndef NDEBUG
3411  SCIP_CALL( SCIPcheckSol(scip, sol, TRUE, FALSE, TRUE, TRUE, TRUE, &feasible) );
3412  assert(feasible);
3413 #endif
3414 
3415  SCIP_CALL( SCIPaddSolFree(scip, &sol, success) );
3416  }
3417  else
3418  {
3419  SCIP_CALL( SCIPfreeSol(scip, &sol) );
3420  *success = FALSE;
3421  }
3422 
3423  }
3424 
3425  return SCIP_OKAY;
3426 }
3427 
3428 /** print graph (in undirected form) in GML format with given edges highlighted */
3429 SCIP_RETCODE SCIPprobdataPrintGraph2(
3430  const GRAPH* graph, /**< Graph to be printed */
3431  const char* filename, /**< Name of the output file */
3432  SCIP_Bool* edgemark /**< Array of (undirected) edges to highlight */
3433  )
3434 {
3435  char label[SCIP_MAXSTRLEN];
3436  FILE* file;
3437  int e;
3438  int n;
3439  int m;
3440 
3441  assert(graph != NULL);
3442  file = fopen((filename != NULL) ? filename : "graphX.gml", "w");
3443 
3444  for( e = 0; e < graph->edges; e += 2 )
3445  {
3446  assert(graph->tail[e] == graph->head[e + 1]);
3447  assert(graph->tail[e + 1] == graph->head[e]);
3448  }
3449 
3450  /* write GML format opening, undirected */
3451  SCIPgmlWriteOpening(file, FALSE);
3452 
3453  /* write all nodes, discriminate between root, terminals and the other nodes */
3454  e = 0;
3455  m = 0;
3456  for( n = 0; n < graph->knots; ++n )
3457  {
3458  if( n == graph->source )
3459  {
3460  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Root", n);
3461  SCIPgmlWriteNode(file, (unsigned int)n, label, "rectangle", "#666666", NULL);
3462  m = 1;
3463  }
3464  else if( graph->term[n] == 0 )
3465  {
3466  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Terminal %d", n, e + 1);
3467  SCIPgmlWriteNode(file, (unsigned int)n, label, "circle", "#ff0000", NULL);
3468  e += 1;
3469  }
3470  else
3471  {
3472  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Node %d", n, n + 1 - e - m);
3473  SCIPgmlWriteNode(file, (unsigned int)n, label, "circle", "#336699", NULL);
3474  }
3475  }
3476 
3477  /* write all edges (undirected) */
3478  for( e = 0; e < graph->edges; e += 2 )
3479  {
3480  if( graph->oeat[e] == EAT_FREE )
3481  continue;
3482  if( !graph->mark[graph->head[e]] || !graph->mark[graph->tail[e]] )
3483  continue;
3484  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "%8.2f", graph->cost[e]);
3485  if( edgemark != NULL && edgemark[e / 2] == TRUE )
3486  SCIPgmlWriteEdge(file, (unsigned int)graph->tail[e], (unsigned int)graph->head[e], label, "#ff0000");
3487  else
3488  SCIPgmlWriteEdge(file, (unsigned int)graph->tail[e], (unsigned int)graph->head[e], label, NULL);
3489  }
3490 
3491 
3492  /* write GML format closing */
3493  SCIPgmlWriteClosing(file);
3494 
3495  return SCIP_OKAY;
3496 }
3497 
3498 /** returns problem type */
3499 int SCIPprobdataGetType(
3500  SCIP* scip /**< SCIP data structure */
3501  )
3502 {
3503  SCIP_PROBDATA* probdata;
3504 
3505  assert(scip != NULL);
3506 
3507  probdata = SCIPgetProbData(scip);
3508  assert(probdata != NULL);
3509 
3510  return probdata->stp_type;
3511 }
3512 
3513 /** writes end of log file */
3514 SCIP_RETCODE SCIPprobdataWriteLogfileEnd(
3515  SCIP* scip /**< SCIP data structure */
3516  )
3517 {
3518  SCIP_PROBDATA* probdata;
3519 
3520  assert(scip != NULL);
3521 
3522  probdata = SCIPgetProbData(scip);
3523  assert(probdata != NULL);
3524 
3525  if( probdata->logfile != NULL )
3526  {
3527  int success;
3528  SCIP_Real factor = 1.0;
3529 
3530  if( probdata->stp_type == STP_MWCSP || probdata->stp_type == STP_RMWCSP )
3531  factor = -1.0;
3532 
3533  SCIPprobdataWriteLogLine(scip, "End\n");
3534  SCIPprobdataWriteLogLine(scip, "\n");
3535  SCIPprobdataWriteLogLine(scip, "SECTION Run\n");
3536  if( probdata->ug )
3537  {
3538  SCIPprobdataWriteLogLine(scip, "Threads %d\n", probdata->nSolvers);
3539  SCIPprobdataWriteLogLine(scip, "Time %.1f\n", SCIPgetTotalTime(scip));
3540  SCIPprobdataWriteLogLine(scip, "Dual %16.9f\n", factor * probdata->ugDual);
3541  }
3542  else
3543  {
3544  SCIPprobdataWriteLogLine(scip, "Threads 1\n");
3545  SCIPprobdataWriteLogLine(scip, "Time %.1f\n", SCIPgetTotalTime(scip));
3546  SCIPprobdataWriteLogLine(scip, "Dual %16.9f\n", factor * SCIPgetDualbound(scip));
3547  }
3548  SCIPprobdataWriteLogLine(scip, "Primal %16.9f\n", factor * SCIPgetPrimalbound(scip));
3549  SCIPprobdataWriteLogLine(scip, "End\n");
3550 
3551  if( SCIPgetNSols(scip) > 0 )
3552  {
3553  SCIPprobdataWriteLogLine(scip, "\n");
3554  SCIPprobdataWriteLogLine(scip, "SECTION Finalsolution\n");
3555 
3556  SCIP_CALL( SCIPprobdataWriteSolution(scip, probdata->logfile) );
3557  SCIPprobdataWriteLogLine(scip, "End\n");
3558  }
3559 
3560  success = fclose(probdata->logfile);
3561  if( success != 0 )
3562  {
3563  SCIPerrorMessage("An error occurred while closing file <%s>\n", probdata->logfile);
3564  return SCIP_FILECREATEERROR;
3565  }
3566 
3567  probdata->logfile = NULL;
3568  }
3569 
3570 
3571  return SCIP_OKAY;
3572 }
3573 
3574 /** writes end of log file */
3575 void SCIPprobdataSetDualBound(
3576  SCIP* scip, /**< SCIP data structure */
3577  SCIP_Real dual /**< dual bound */
3578  )
3579 {
3580  SCIP_PROBDATA* probdata;
3581 
3582  assert(scip != NULL);
3583 
3584  probdata = SCIPgetProbData(scip);
3585  probdata->ug = TRUE;
3586  probdata->ugDual = dual;
3587 }
3588 
3589 /** writes end of log file */
3590 void SCIPprobdataSetNSolvers(
3591  SCIP* scip, /**< SCIP data structure */
3592  int nSolvers /**< the number of solvers */
3593  )
3594 {
3595  SCIP_PROBDATA* probdata;
3596 
3597  assert(scip != NULL);
3598 
3599  probdata = SCIPgetProbData(scip);
3600  probdata->nSolvers = nSolvers;
3601 }
3602 
3603 /** branching information from UG */
3604 void initReceivedSubproblem(
3605  SCIP* scip, /**< SCIP data structure */
3606  const int lLinearConsNames, /**< number of linear constraints */
3607  const char* linearConsNames, /**< linear constraints string */
3608  const int lSetppcConsNames, /**< number of setppc constraints */
3609  const char* setppcConsNames /**< number of setppc constraints */
3610  )
3611 {
3612 
3613 #ifdef WITH_UG
3614  SCIP_PROBDATA* probdata;
3615  GRAPH* graph;
3616  int* nodestate;
3617  int nnodes;
3618 
3619  assert(scip != NULL);
3620  probdata = SCIPgetProbData(scip);
3621 
3622  graph = SCIPprobdataGetGraph(probdata);
3623  assert(graph != NULL);
3624  assert(probdata->orggraph != NULL);
3625 
3626  graph_mincut_exit(scip, graph);
3627  graph_path_exit(scip, graph);
3628  graph_free(scip, &graph, TRUE);
3629  graph_copy(scip, probdata->orggraph, &graph);
3630 
3631  probdata->graph = graph;
3632 
3633  assert(graph != NULL && probdata->mode == MODE_CUT);
3634 
3635  nnodes = graph->knots;
3636  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &nodestate, nnodes) );
3637  SCIPStpBranchruleInitNodeState(graph, nodestate);
3638 
3639  for( int i = 0; i < lLinearConsNames; i++ )
3640  {
3641  const char* consname = getBranchLinearConsName(linearConsNames, i);
3642  SCIPdebugMessage("add lin cons %s \n", consname);
3643  if( consname != NULL)
3644  SCIP_CALL_ABORT( STPStpBranchruleParseConsname(scip, nodestate, NULL, consname, FALSE) );
3645  }
3646 
3647  for( int i = 0; i < lSetppcConsNames; i++ )
3648  {
3649  const char* consname = getBranchSetppcConsName(setppcConsNames, i);
3650  SCIPdebugMessage("add ppc cons %s \n", consname);
3651  if( consname != NULL)
3652  SCIP_CALL_ABORT( STPStpBranchruleParseConsname(scip, nodestate, NULL, consname, FALSE) );
3653  }
3654 
3655  for( int k = 0; k < nnodes; k++ )
3656  {
3657  if( nodestate[k] == BRANCH_STP_VERTEX_TERM && !Is_term(graph->term[k]) )
3658  {
3659  SCIPdebugMessage("UG make term: %d \n", k);
3660  graph_knot_chg(graph, k, 0);
3661  }
3662  else if( nodestate[k] == BRANCH_STP_VERTEX_KILLED )
3663  {
3664  for( int e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
3665  {
3666  if( graph->cost[e] < BLOCKED )
3667  graph->cost[e] = BLOCKED;
3668 
3669  if( graph->cost[flipedge(e)] < BLOCKED )
3670  graph->cost[flipedge(e)] = BLOCKED;
3671  }
3672  }
3673  }
3674 
3675  SCIPfreeBufferArray(scip, &nodestate);
3676 
3677  SCIP_CALL_ABORT( graph_init_history(scip, graph) );
3678  SCIP_CALL_ABORT( graph_path_init(scip, graph) );
3679  SCIP_CALL_ABORT( graph_mincut_init(scip, graph) );
3680 
3681 #else
3682  assert(0 && "only call me when using UG");
3683 #endif
3684 }
3685 /**@} */
graph_path_init
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: grphpath.c:444
SCIPprobdataWriteStp
void SCIPprobdataWriteStp(SCIP *scip, const GRAPH *graph, const char *filename)
Definition: probdata_stp.c:2713
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
presolve_info
Definition: grph.h:133
Int_List_Node
Definition: misc_stp.h:73
SCIPcreateOrigSol
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:557
SCIPcreateConsLinear
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_linear.c:17744
nterms
static volatile int nterms
Definition: interrupt.c:38
SCIPfreeSol
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
SCIPgmlWriteEdge
void SCIPgmlWriteEdge(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:584
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:587
createVariables
static SCIP_RETCODE createVariables(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real offset)
Definition: probdata_stp.c:905
CENTER_MIN
#define CENTER_MIN
Definition: probdata_stp.c:57
SCIPsetSolVal
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
GRAPH::head
int *RESTRICT head
Definition: grph.h:96
GRAPH::orgtail
int *RESTRICT orgtail
Definition: grph.h:97
GRAPH
Definition: grph.h:57
GRAPH::source
int source
Definition: grph.h:67
central_terminal
static SCIP_RETCODE central_terminal(SCIP *scip, GRAPH *g, int *central_term, int centertype)
Definition: probdata_stp.c:202
SCIPprobdataGetNTerms
int SCIPprobdataGetNTerms(SCIP *scip)
Definition: probdata_stp.c:2454
SCIPfreeMemoryArrayNull
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:70
SCIP_DECL_PROBEXITSOL
static SCIP_DECL_PROBEXITSOL(probexitsolStp)
Definition: probdata_stp.c:1828
SCIPconsIsLocal
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8328
SCIP_DECL_PROBTRANS
static SCIP_DECL_PROBTRANS(probtransStp)
Definition: probdata_stp.c:1659
STP_GSTP
#define STP_GSTP
Definition: grph.h:49
SCIPprobdataGetEdgeConstraints
SCIP_CONS ** SCIPprobdataGetEdgeConstraints(SCIP *scip)
Definition: probdata_stp.c:2579
cons_stp.h
Constraint handler for Steiner problems.
SCIPconsIsChecked
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8288
shortest_path::edge
signed int edge
Definition: grph.h:146
SCIPgetStringParam
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:336
SCIPprobdataSetOffset
void SCIPprobdataSetOffset(SCIP_PROBDATA *probdata, SCIP_Real offset)
Definition: probdata_stp.c:2382
SCIPqueueInsert
SCIP_RETCODE SCIPqueueInsert(SCIP_QUEUE *queue, void *elem)
Definition: misc.c:1019
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:273
updateorgsol
static void updateorgsol(GRAPH *graph, IDX *curr, STP_Bool *orgnodes, STP_Bool *orgedges, int *nsolnodes, int *nsoledges)
Definition: probdata_stp.c:151
SCIPsetObjsense
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1240
GRAPH::terms
int terms
Definition: grph.h:64
SCIP_SUCCESS
Definition: type_result.h:49
SCIPprobdataGetVars
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
Definition: probdata_stp.c:2409
graph_copy
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: grphbase.c:3900
graph_init_history
SCIP_RETCODE graph_init_history(SCIP *, GRAPH *)
Definition: grphbase.c:3573
SCIPcaptureVar
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1218
SCIPallocMemoryArray
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:53
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
SCIPaddCoefSetppc
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9226
SCIPaddCoefLinear
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18085
SCIP_Var
Definition: struct_var.h:198
SCIPStpDualAscentPcMw
SCIP_RETCODE SCIPStpDualAscentPcMw(SCIP *scip, GRAPH *g, SCIP_Real *redcost, SCIP_Real *objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, int nruns)
Definition: cons_stp.c:2268
GRAPH::maxdeg
int *RESTRICT maxdeg
Definition: grph.h:78
SCIPgetConsCopy
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1534
EAT_LAST
#define EAT_LAST
Definition: grph.h:31
SCIPgetBoolParam
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
SCIPcreateVarBasic
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
SCIPgetReadingTime
SCIP_Real SCIPgetReadingTime(SCIP *scip)
Definition: scip_timing.c:387
BLOCKED
#define BLOCKED
Definition: grph.h:157
SCIP_VERBLEVEL_HIGH
Definition: type_message.h:45
SCIPqueueRemove
void * SCIPqueueRemove(SCIP_QUEUE *queue)
Definition: misc.c:1070
SCIPverbMessage
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
FALSE
#define FALSE
Definition: def.h:73
SCIPprobdataGetNEdges
int SCIPprobdataGetNEdges(SCIP *scip)
Definition: probdata_stp.c:2439
SCIPprobdataWriteIntermediateSolution
SCIP_RETCODE SCIPprobdataWriteIntermediateSolution(SCIP *scip)
Definition: probdata_stp.c:2697
graph_mincut_init
SCIP_RETCODE graph_mincut_init(SCIP *, GRAPH *)
Definition: grphmcut.c:275
GRAPH::inpbeg
int *RESTRICT inpbeg
Definition: grph.h:74
probdataCreate
static SCIP_RETCODE probdataCreate(SCIP *scip, SCIP_PROBDATA **probdata, GRAPH *graph)
Definition: probdata_stp.c:334
SCIPsolGetHeur
SCIP_EXPORT SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2604
CENTER_SUM
#define CENTER_SUM
Definition: probdata_stp.c:56
SCIPStpBranchruleInitNodeState
void SCIPStpBranchruleInitNodeState(const GRAPH *g, int *nodestate)
Definition: branch_stp.c:683
STP_RMWCSP
#define STP_RMWCSP
Definition: grph.h:50
struct_misc.h
miscellaneous datastructures
graph_free
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: grphbase.c:3678
probdata_stp.h
Problem data for stp problem.
TRUE
#define TRUE
Definition: def.h:72
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_VARTYPE_BINARY
Definition: type_var.h:53
graph_path_exit
void graph_path_exit(SCIP *, GRAPH *)
Definition: grphpath.c:466
STP_DHCSTP
#define STP_DHCSTP
Definition: grph.h:48
shortest_path
Definition: grph.h:143
SCIPconsIsInitial
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8258
SCIPgetProbData
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
SCIPprobdataGetNVars
int SCIPprobdataGetNVars(SCIP *scip)
Definition: probdata_stp.c:2394
CYC_CONS_LIMIT
#define CYC_CONS_LIMIT
Definition: probdata_stp.c:71
probdataPrintGraph
static SCIP_RETCODE probdataPrintGraph(GRAPH *graph, const char *filename, SCIP_Bool *edgemark)
Definition: probdata_stp.c:499
SCIPvarIsActive
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17335
STP_PCSPG
#define STP_PCSPG
Definition: grph.h:40
SCIPdebugMessage
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIPchgVarUbLazy
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5150
createConstraints
static SCIP_RETCODE createConstraints(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:759
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
cons_setppc.h
Constraint handler for the set partitioning / packing / covering constraints .
GRAPH::orghead
int *RESTRICT orghead
Definition: grph.h:98
CUT_MAXNTERMINALS
#define CUT_MAXNTERMINALS
Definition: probdata_stp.c:73
SCIPprobdataGetNLayers
int SCIPprobdataGetNLayers(SCIP *scip)
Definition: probdata_stp.c:2424
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: grphbase.c:2222
SCIPprobdataWriteLogfileEnd
SCIP_RETCODE SCIPprobdataWriteLogfileEnd(SCIP *scip)
Definition: probdata_stp.c:3514
SCIPprobdataGetGraph
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:2357
SCIPStpDualAscent
SCIP_RETCODE SCIPStpDualAscent(SCIP *scip, const GRAPH *g, SCIP_Real *RESTRICT redcost, SCIP_Real *RESTRICT nodearrreal, SCIP_Real *objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, GNODE **gnodearrterms, const int *result, int *RESTRICT edgearrint, int *RESTRICT nodearrint, int root, SCIP_Bool is_pseudoroot, SCIP_Real damaxdeviation, STP_Bool *RESTRICT nodearrchar)
Definition: cons_stp.c:1687
GRAPH::mark
int *RESTRICT mark
Definition: grph.h:70
SCIPgetCharParam
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:317
SCIPgmlWriteOpening
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
Definition: misc.c:672
SCIPcreateSol
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
GRAPH::fixedges
IDX * fixedges
Definition: grph.h:85
SCIP_Sol
Definition: struct_sol.h:64
SCIPgetNSols
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2206
SCIPsetRealParam
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:613
SCIPgetVarCopy
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:697
SCIPaddOrigObjoffset
SCIP_RETCODE SCIPaddOrigObjoffset(SCIP *scip, SCIP_Real addval)
Definition: scip_prob.c:1288
SCIPprobdataWriteLogLine
void SCIPprobdataWriteLogLine(SCIP *scip, const char *formatstr,...)
Definition: probdata_stp.c:3124
graph_pack
SCIP_RETCODE graph_pack(SCIP *, GRAPH *, GRAPH **, SCIP_Bool)
Definition: grphbase.c:3988
SCIPqueueIsEmpty
SCIP_Bool SCIPqueueIsEmpty(SCIP_QUEUE *queue)
Definition: misc.c:1174
CENTER_OK
#define CENTER_OK
Definition: probdata_stp.c:54
SCIPprobdataGetRTerms
int * SCIPprobdataGetRTerms(SCIP *scip)
Definition: probdata_stp.c:2608
GRAPH::oeat
int *RESTRICT oeat
Definition: grph.h:103
SCIPprobdataWriteSolution
SCIP_RETCODE SCIPprobdataWriteSolution(SCIP *scip, FILE *file)
Definition: probdata_stp.c:2753
Int_List_Node::index
int index
Definition: misc_stp.h:75
CONS_SPECIFIC
#define CONS_SPECIFIC
Definition: probdata_stp.c:65
probdataFree
static SCIP_RETCODE probdataFree(SCIP *scip, SCIP_PROBDATA **probdata)
Definition: probdata_stp.c:368
SCIPsetProbData
SCIP_RETCODE SCIPsetProbData(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: scip_prob.c:1012
SCIPprobdataSetNSolvers
void SCIPprobdataSetNSolvers(SCIP *scip, int nSolvers)
Definition: probdata_stp.c:3590
SCIPprobdataGetPathConstraints
SCIP_CONS ** SCIPprobdataGetPathConstraints(SCIP *scip)
Definition: probdata_stp.c:2593
GRAPH::extended
SCIP_Bool extended
Definition: grph.h:128
STP_SAP
#define STP_SAP
Definition: grph.h:39
GRAPH::stp_type
int stp_type
Definition: grph.h:127
GRAPH::ancestors
IDX ** ancestors
Definition: grph.h:86
GRAPH::orgedges
int orgedges
Definition: grph.h:93
SCIP_Cons
Definition: struct_cons.h:37
MODE_PRICE
#define MODE_PRICE
Definition: probdata_stp.c:62
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:55
VERSION_SCIPJACK
#define VERSION_SCIPJACK
Definition: grph.h:173
STPStpBranchruleParseConsname
SCIP_RETCODE STPStpBranchruleParseConsname(SCIP *scip, int *vertexchgs, GRAPH *graph, const char *consname, SCIP_Bool deletehistory)
Definition: branch_stp.c:604
SCIPprobdataGetRNTerms
int SCIPprobdataGetRNTerms(SCIP *scip)
Definition: probdata_stp.c:2469
STP_Bool
unsigned char STP_Bool
Definition: grph.h:52
SCIPprobdataIsBigt
SCIP_Bool SCIPprobdataIsBigt(SCIP *scip)
Definition: probdata_stp.c:2638
SCIPprobdataAddNewSol
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_SOL *sol, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: probdata_stp.c:3153
SCIPchgVarBranchPriority
SCIP_RETCODE SCIPchgVarBranchPriority(SCIP *scip, SCIP_VAR *var, int branchpriority)
Definition: scip_var.c:7961
SCIPprobdataPrintGraph
SCIP_RETCODE SCIPprobdataPrintGraph(SCIP *scip, const char *filename, SCIP_SOL *sol, SCIP_Bool printsol)
Definition: probdata_stp.c:2653
SCIPprobdataGetOffset
SCIP_Real SCIPprobdataGetOffset(SCIP *scip)
Definition: probdata_stp.c:2518
CENTER_DEG
#define CENTER_DEG
Definition: probdata_stp.c:55
STP_DCSTP
#define STP_DCSTP
Definition: grph.h:43
GRAPH::prize
SCIP_Real * prize
Definition: grph.h:82
SCIP_Queue
Definition: struct_misc.h:51
shortest_path::dist
SCIP_Real dist
Definition: grph.h:145
GRAPH::grad
int *RESTRICT grad
Definition: grph.h:73
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:551
polyscip::global::print
void print(const Container &container, const std::string &prefix="", const std::string &suffix="", std::ostream &os=std::cout, bool negate=false, int prec=6)
Definition: global_functions.h:95
SCIP_DECL_PROBINITSOL
static SCIP_DECL_PROBINITSOL(probinitsolStp)
Definition: probdata_stp.c:1819
misc.h
internal miscellaneous methods
FSP_MODE
#define FSP_MODE
Definition: grph.h:163
NULL
#define NULL
Definition: lpi_spx1.cpp:155
graph_grid_coordinates
SCIP_RETCODE graph_grid_coordinates(SCIP *, int **, int **, int *, int, int)
Definition: grphbase.c:730
graph_path_exec
void graph_path_exec(SCIP *, const GRAPH *, const int, int, const SCIP_Real *, PATH *)
Definition: grphpath.c:491
SCIP_OKAY
Definition: type_retcode.h:33
GRAPH::knots
int knots
Definition: grph.h:62
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:364
SCIPsplitFilename
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
Definition: misc.c:10809
GRAPH::pcancestors
IDX ** pcancestors
Definition: grph.h:87
STP_NWSPG
#define STP_NWSPG
Definition: grph.h:42
SCIPprobdataPrintGraph2
SCIP_RETCODE SCIPprobdataPrintGraph2(const GRAPH *graph, const char *filename, SCIP_Bool *edgemark)
Definition: probdata_stp.c:3429
SCIPqueueCreate
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition: misc.c:933
SCIPgetNOrigVars
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2426
GRAPH::orgknots
int orgknots
Definition: grph.h:63
SCIP_Heur
Definition: struct_heur.h:88
SCIPcaptureCons
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1075
SCIPprobdataCreate
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *filename)
Definition: probdata_stp.c:1915
CUT_MAXNEDGES
#define CUT_MAXNEDGES
Definition: probdata_stp.c:74
FARAWAY
#define FARAWAY
Definition: grph.h:156
SCIPprobdataGetType
int SCIPprobdataGetType(SCIP *scip)
Definition: probdata_stp.c:3499
SCIPgetIntParam
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
SCIPsetProbDelorig
SCIP_RETCODE SCIPsetProbDelorig(SCIP *scip, SCIP_DECL_PROBDELORIG((*probdelorig)))
Definition: scip_prob.c:190
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
SCIPconsIsRemovable
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8358
STP_SPG
#define STP_SPG
Definition: grph.h:38
SCIPwriteOrigProblem
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:599
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:503
SCIPsetSolVals
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1255
SCIP_Bool
#define SCIP_Bool
Definition: def.h:70
SCIPgetTotalTime
SCIP_Real SCIPgetTotalTime(SCIP *scip)
Definition: scip_timing.c:333
GRAPH::ieat
int *RESTRICT ieat
Definition: grph.h:102
SCIPaddSolFree
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:3015
SCIPprobdataSetGraph
void SCIPprobdataSetGraph(SCIP_PROBDATA *probdata, GRAPH *graph)
Definition: probdata_stp.c:2345
SCIPtransformVar
SCIP_RETCODE SCIPtransformVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1353
STP_MWCSP
#define STP_MWCSP
Definition: grph.h:47
SCIPvarGetUbGlobal
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17672
GRAPH::tail
int *RESTRICT tail
Definition: grph.h:95
SCIP_VARTYPE_INTEGER
Definition: type_var.h:54
BRANCH_STP_VERTEX_TERM
#define BRANCH_STP_VERTEX_TERM
Definition: branch_stp.h:38
SCIPprobdataGetEdgeVars
SCIP_VAR ** SCIPprobdataGetEdgeVars(SCIP *scip)
Definition: probdata_stp.c:2623
SCIPsetProbInitsol
SCIP_RETCODE SCIPsetProbInitsol(SCIP *scip, SCIP_DECL_PROBINITSOL((*probinitsol)))
Definition: scip_prob.c:253
SCIPgetMessagehdlr
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:91
MAX
#define MAX(x, y)
Definition: tclique_def.h:83
graph_mincut_exit
void graph_mincut_exit(SCIP *, GRAPH *)
Definition: grphmcut.c:305
SCIPgetOrigVars
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2399
SCIPgmlWriteClosing
void SCIPgmlWriteClosing(FILE *file)
Definition: misc.c:688
graph_sol_markPcancestors
SCIP_RETCODE graph_sol_markPcancestors(SCIP *, IDX **, const int *, const int *, int, STP_Bool *, STP_Bool *, int *, int *, int *)
Definition: grphbase.c:3292
SCIPprobdataSetDualBound
void SCIPprobdataSetDualBound(SCIP *scip, SCIP_Real dual)
Definition: probdata_stp.c:3575
CONS_ALWAYS
#define CONS_ALWAYS
Definition: probdata_stp.c:64
GRAPH::term
int *RESTRICT term
Definition: grph.h:68
SCIPconsIsSeparated
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8268
cons_linear.h
Constraint handler for linear constraints in their most general form, .
SCIPaddVar
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
SCIPprobdataGetRoot
int SCIPprobdataGetRoot(SCIP *scip)
Definition: probdata_stp.c:2484
SCIPconsIsDynamic
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8348
GRAPH::grid_dim
int grid_dim
Definition: grph.h:122
SCIPcreateConsStp
SCIP_RETCODE SCIPcreateConsStp(SCIP *scip, SCIP_CONS **cons, const char *name, GRAPH *graph)
Definition: cons_stp.c:1636
grph.h
includes various files containing graph methods used for Steiner tree problems
BRANCH_STP_VERTEX_KILLED
#define BRANCH_STP_VERTEX_KILLED
Definition: branch_stp.h:36
SCIPsetProbTrans
SCIP_RETCODE SCIPsetProbTrans(SCIP *scip, SCIP_DECL_PROBTRANS((*probtrans)))
Definition: scip_prob.c:211
SCIPcheckSolOrig
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3497
GRAPH::grid_coordinates
int ** grid_coordinates
Definition: grph.h:124
SCIP_FILECREATEERROR
Definition: type_retcode.h:39
SCIPsetProbExitsol
SCIP_RETCODE SCIPsetProbExitsol(SCIP *scip, SCIP_DECL_PROBEXITSOL((*probexitsol)))
Definition: scip_prob.c:275
SCIPsetProbCopy
SCIP_RETCODE SCIPsetProbCopy(SCIP *scip, SCIP_DECL_PROBCOPY((*probcopy)))
Definition: scip_prob.c:296
GRAPH::layers
int layers
Definition: grph.h:65
SCIPfreeMemory
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:67
r
SCIP_Real * r
Definition: circlepacking.c:50
SCIPgetSolVals
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1390
branch_stp.h
Steiner vertex branching rule.
SCIP_DECL_PROBDELTRANS
static SCIP_DECL_PROBDELTRANS(probdeltransStp)
Definition: probdata_stp.c:1897
Is_term
#define Is_term(a)
Definition: grph.h:168
EAT_FREE
#define EAT_FREE
Definition: grph.h:30
SCIPprobdataGetNorgEdges
int SCIPprobdataGetNorgEdges(SCIP *scip)
Definition: probdata_stp.c:2503
SCIP_PROBDATA
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIPmessageVFPrintInfo
void SCIPmessageVFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr, va_list ap)
Definition: message.c:624
SCIPconsIsEnforced
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8278
SCIPtransformConss
SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
Definition: scip_cons.c:1562
GRAPH::cost
SCIP_Real * cost
Definition: grph.h:94
SCIPvarGetLbGlobal
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17662
graph_load
SCIP_RETCODE graph_load(SCIP *, GRAPH **, const char *, PRESOL *)
Definition: grphload.c:821
a
SCIP_VAR * a
Definition: circlepacking.c:57
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10590
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8089
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1252
SCIPsetObjIntegral
SCIP_RETCODE SCIPsetObjIntegral(SCIP *scip)
Definition: scip_prob.c:1517
SCIP_Real
#define SCIP_Real
Definition: def.h:163
CENTER_ALL
#define CENTER_ALL
Definition: probdata_stp.c:58
SCIP_DECL_PROBCOPY
static SCIP_DECL_PROBCOPY(probcopyStp)
Definition: probdata_stp.c:1248
SCIPconsGetHdlr
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8109
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIPprobdataGetXval
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
Definition: probdata_stp.c:2551
GRAPH::outbeg
int *RESTRICT outbeg
Definition: grph.h:76
SCIPprobdataGetedgeVarByIndex
SCIP_VAR * SCIPprobdataGetedgeVarByIndex(SCIP *scip, int idx)
Definition: probdata_stp.c:2534
SCIPgetPrimalbound
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
Definition: scip_solvingstats.c:1511
SCIP_Messagehdlr::logfile
FILE * logfile
Definition: struct_message.h:43
SCIPprintSysError
void SCIPprintSysError(const char *message)
Definition: misc.c:10499
SCIP_Longint
#define SCIP_Longint
Definition: def.h:148
SCIPconsIsStickingAtNode
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8368
GRAPH::edges
int edges
Definition: grph.h:92
initReceivedSubproblem
void initReceivedSubproblem(SCIP *scip, const int lLinearConsNames, const char *linearConsNames, const int lSetppcConsNames, const char *setppcConsNames)
Definition: probdata_stp.c:3604
GRAPH::grid_ncoords
int * grid_ncoords
Definition: grph.h:123
flipedge
#define flipedge(edge)
Definition: grph.h:150
graph_knot_add
void graph_knot_add(GRAPH *, int)
Definition: grphbase.c:2200
SYM_CONS_LIMIT
#define SYM_CONS_LIMIT
Definition: probdata_stp.c:70
reduce
SCIP_RETCODE reduce(SCIP *, GRAPH **, SCIP_Real *, int, int, SCIP_Bool)
Definition: reduce.c:1675
createHopConstraint
static SCIP_RETCODE createHopConstraint(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:570
presolve_info::fixed
SCIP_Real fixed
Definition: grph.h:135
SCIPallocMemory
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIPaddCons
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2764
MODE_CUT
#define MODE_CUT
Definition: probdata_stp.c:60
STP_RSMT
#define STP_RSMT
Definition: grph.h:45
nnodes
#define nnodes
Definition: gastrans.c:65
STP_OARSMT
#define STP_OARSMT
Definition: grph.h:46
createPrizeConstraints
static SCIP_RETCODE createPrizeConstraints(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:633
CUT_MAXTOTNEDGES
#define CUT_MAXTOTNEDGES
Definition: probdata_stp.c:75
SCIPqueueFree
void SCIPqueueFree(SCIP_QUEUE **queue)
Definition: misc.c:957
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
SCIPcreateConsSetpack
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9113
SCIPinfoMessage
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_OBJSENSE_MINIMIZE
Definition: type_prob.h:39
Int_List_Node::parent
struct Int_List_Node * parent
Definition: misc_stp.h:76
createDegreeConstraints
static SCIP_RETCODE createDegreeConstraints(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:598
SCIP_CALL_ABORT
#define SCIP_CALL_ABORT(x)
Definition: def.h:343
SCIPreleaseCons
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIPgmlWriteNode
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:486
MODE_FLOW
#define MODE_FLOW
Definition: probdata_stp.c:61
SCIPtrySolFree
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3231
SCIPgetDualbound
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip_solvingstats.c:1335
GRAPH::hoplimit
int hoplimit
Definition: grph.h:89
SCIPsetProbDeltrans
SCIP_RETCODE SCIPsetProbDeltrans(SCIP *scip, SCIP_DECL_PROBDELTRANS((*probdeltrans)))
Definition: scip_prob.c:232
graph_edge_add
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
STP_RPCSPG
#define STP_RPCSPG
Definition: grph.h:41
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2305
SCIPprobdataGetGraph2
GRAPH * SCIPprobdataGetGraph2(SCIP *scip)
Definition: probdata_stp.c:2367
SCIPconsIsPropagated
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8308
SCIPsetIntParam
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
SCIPcheckSol
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip_sol.c:3440
SCIP_DECL_PROBDELORIG
static SCIP_DECL_PROBDELORIG(probdelorigStp)
Definition: probdata_stp.c:1628
SCIPcreateProbBasic
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:170
scip.h
SCIP callable library.
graph_init
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: grphbase.c:3495
SCIPconsIsModifiable
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8338
GRAPH::norgmodelknots
int norgmodelknots
Definition: grph.h:60
GRAPH::orgsource
int orgsource
Definition: grph.h:66
SCIPtransformVars
SCIP_RETCODE SCIPtransformVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1393
SCIPtransformCons
SCIP_RETCODE SCIPtransformCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: scip_cons.c:1521
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58