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