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