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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file probdata_stp.c
17  * @brief Problem data for Steiner problems
18  * @author Gerald Gamrath
19  * @author Thorsten Koch
20  * @author Michael Winkler
21  * @author Daniel Rehfeldt
22  *
23  * This file implements the problem data for Steiner problems. For more details see \ref STP_PROBLEMDATA page.
24  *
25  * @page STP_PROBLEMDATA Main problem data
26  *
27  * The problem data is accessible in all plugins.
28  *
29  * The problem data contains the (preprocessed) graph, several constraints and further information.
30  *
31  * The function SCIPprobdataCreate(), which is called in the \ref reader_stp.c "reader plugin", parses the input file
32  * reduces the graph, initializes the problem data structure and creates the problem in the SCIP environment.
33  * See the body of the function SCIPprobdataCreate() for more details.
34  *
35  * A list of all interface methods can be found in probdata_stp.h.
36  */
37 
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39 
40 #include <string.h>
41 #include "probdata_stp.h"
42 #include <stdio.h>
43 #include "cons_stp.h"
44 #include "dualascent.h"
45 #include "graph.h"
46 #include "reduce.h"
47 #include "stptest.h"
48 #include "solstp.h"
49 #include "solpool.h"
50 #include "solhistory.h"
51 #include "cons_stpcomponents.h"
52 #include "scip/cons_linear.h"
53 #include "scip/cons_setppc.h"
54 #include "scip/misc.h"
55 #include "scip/struct_misc.h"
56 #ifdef WITH_UG
57 #include "branch_stp.h"
58 #endif
59 
60 #include "heur_tm.h"
61 #include "heur_slackprune.h"
62 #include "relax_stpdp.h"
63 
64 
65 #define VERSION_SCIPJACK "2.0"
66 
67 #define STP_SYM_PRIZE
68 #define STP_AGG_SYM
69 
70 #define FLOWB FALSE
71 #define USEOFFSETVAR FALSE
72 
73 #define SYM_CONS_LIMIT 20000 /**< maximum number of symmetry inequalities for MWCSP and PCSPG */
74 #define CYC_CONS_LIMIT 10000 /**< maximum number of symmetry inequalities for PCSPG */
75 
76 #define CUT_MINREDUCTION_RATIO 0.95
77 #define MINREDUCTION_RATIO_STP 0.90
78 #define MINREDUCTION_RATIO_PCMW 0.85
79 #define CUT_MAXNTERMINALS 500
80 #define CUT_MAXNEDGES 10000
81 #define CUT_MAXTOTNEDGES 50000
82 #define CUT_MINTOTNEDGES 12000
83 
84 #ifdef WITH_UG
85 const char*
86 getBranchLinearConsName(const char* names, int i);
87 
88 const char*
89 getBranchSetppcConsName(const char* names, int i);
90 
91 extern
92 int getUgRank(void);
93 #endif
94 
95 
96 /** @brief Problem data which is accessible in all places
97  *
98  * This problem data is used to store the graph of the Steiner tree problem
99  */
100 struct SCIP_ProbData
101 {
102  int mode; /**< solving mode selected by the user (Cut, Price, Flow) */
103  SCIP_Bool bigt; /**< stores whether the 'T' model is being used (not relevant in Cut mode) */
104  GRAPH* graph; /**< the graph */
105 #ifdef WITH_UG
106  GRAPH* orggraph; /**< copy of presolved graph needed for UG */
107 #endif
108  SCIP_CONS** degcons; /**< array of (node) degree constraints */
109  SCIP_CONS** edgecons; /**< array of constraints */
110  SCIP_CONS** pathcons; /**< array of path constraints (needed only in the Price mode) */
111 #if FLOWB
112  SCIP_CONS** flowbcons; /**< flow balance constraints */
113 #endif
114  SCIP_CONS** prizesymcons; /**< prize-collecting symmetry constraints (to improve LP) */
115  SCIP_CONS** prizecyclecons; /**< prize-collecting cycle constraints (to improve LP) */
116  SCIP_CONS* hopcons; /**< hop constraint */
117  SCIP_CONS* budgetcons; /**< budget constraint */
118  SCIP_CONS* prizecons; /**< prize constraint */
119  SCIP_VAR** edgevars; /**< array of edge variables */
120  SCIP_VAR** flowvars; /**< array of edge variables (needed only in the Flow mode) */
121 #if USEOFFSETVAR
122  SCIP_VAR* offsetvar; /**< variable to model the objective offset */
123 #endif
124  SCIP_Real presolub; /**< presolve upper bound */
125  SCIP_Real offset; /**< offset of the problem, computed during the presolving */
126  SCIP_Real* xval; /**< values of the edge variables */
127  SCIP_Longint lastlpiters; /**< Branch and Cut */
128  int* pctermsorder; /**< terminal order for PCSPG/MWCSP */
129  int* realterms; /**< array of all terminals except the root */
130  int nedges; /**< number of edges */
131  int norgedges; /**< number of original edges of the model */
132  int nterms; /**< number of terminals */
133  int realnterms; /**< number of terminals except the root */
134  int nlayers; /**< number of layers */
135  int nnodes; /**< number of nodes */
136  int nnonterms; /**< number of nodes */
137  int nvars; /**< number of variables */
138  int stp_type; /**< Steiner problem type */
139  int minelims; /**< minimal number of eliminations per reduction method */
140  SCIP_Bool emitgraph; /**< emitgraph */
141  SCIP_Bool copy; /**< is this the problem data of a copy/sub-MIP? */
142  SCIP_Bool usecyclecons; /**< use 2-cycle inequalities for (R)PCSPG? */
143  SCIP_Bool usesymcons; /**< use symmetry inequalities for PCSPG and MWCSP? */
144  SCIP_Bool graphHasVanished; /**< has the graph vanished? */
145  SCIP_Bool objIsInt; /**< is objective always integral? */
146  SCIP_Bool isSubProb; /**< are we in a subproblem? */
147  FILE* logfile; /**< logfile for DIMACS challenge */
148  FILE** origlogfile; /**< pointer to original problem data logfile pointer */
149  FILE* intlogfile; /**< logfile printing all intermediate solutions for DIMACS challenge */
150  FILE** origintlogfile; /**< pointer to original problem data intlogfile pointer */
151 
152  /** for FiberSCIP **/
153  SCIP_Bool ug; /**< indicates if this ug dual bound is set or not */
154  int nSolvers; /**< the number of solvers */
155  SCIP_Real ugDual; /**< dual bound set by ug */
156 };
157 
158 /**@name Local methods
159  *
160  * @{
161  */
162 
163 static
165  SCIP* scip, /**< SCIP data structure */
166  GRAPH* graph, /**< graph data structure */
167  const char* filename /**< problem file name */
168 )
169 {
170  char probtype[16];
171 
172  SCIPprobdataWriteLogLine(scip, "SECTION Comment\n");
173  SCIPprobdataWriteLogLine(scip, "Name %s\n", filename);
174 
175  switch( graph->stp_type )
176  {
177  case STP_SPG:
178  strcpy(probtype, "SPG");
179  break;
180  case STP_SAP:
181  strcpy(probtype, "SAP");
182  break;
183 
184  case STP_PCSPG:
185  strcpy(probtype, "PCSPG");
186  break;
187 
188  case STP_RPCSPG:
189  strcpy(probtype, "RPCST");
190  break;
191 
192  case STP_NWSPG:
193  strcpy(probtype, "NWSPG");
194  break;
195 
196  case STP_DCSTP:
197  strcpy(probtype, "DCST");
198  break;
199 
200  case STP_RSMT:
201  strcpy(probtype, "RSMT");
202  break;
203 
204  case STP_OARSMT:
205  strcpy(probtype, "OARSMT");
206  break;
207 
208  case STP_MWCSP:
209  strcpy(probtype, "MWCS");
210  break;
211 
212  case STP_RMWCSP:
213  strcpy(probtype, "RMWCS");
214  break;
215 
216  case STP_BRMWCSP:
217  strcpy(probtype, "BRMWCS");
218  break;
219 
220  case STP_DHCSTP:
221  strcpy(probtype, "HCDST");
222  break;
223 
224  default:
225  strcpy(probtype, "UNKNOWN");
226  }
227  SCIPprobdataWriteLogLine(scip, "Problem %s\n", probtype);
228  SCIPprobdataWriteLogLine(scip, "Program SCIP-Jack\n");
229  SCIPprobdataWriteLogLine(scip, "Version %s\n", VERSION_SCIPJACK);
230  SCIPprobdataWriteLogLine(scip, "End\n");
231  SCIPprobdataWriteLogLine(scip, "\n");
232  SCIPprobdataWriteLogLine(scip, "SECTION Solutions\n");
233 }
234 
235 
236 /** creates problem data */
237 static
239  SCIP* scip, /**< SCIP data structure */
240  SCIP_PROBDATA** probdata, /**< pointer to problem data */
241  GRAPH* graph /**< graph data structure */
242  )
243 {
244  assert(scip != NULL);
245  assert(probdata != NULL);
246 
247  /* allocate memory */
248  SCIP_CALL( SCIPallocMemory(scip, probdata) );
249 
250  (*probdata)->graph = graph;
251  (*probdata)->xval = NULL;
252  (*probdata)->lastlpiters = -1;
253  if( graph != NULL )
254  (*probdata)->stp_type = graph->stp_type;
255  else
256  (*probdata)->stp_type = STP_SPG;
257  (*probdata)->copy = FALSE;
258  (*probdata)->logfile = NULL;
259  (*probdata)->origlogfile = NULL;
260  (*probdata)->intlogfile = NULL;
261  (*probdata)->origintlogfile = NULL;
262  (*probdata)->nedges = -1;
263  (*probdata)->nnodes = -1;
264  (*probdata)->nterms = -1;
265  (*probdata)->presolub = FARAWAY;
266  (*probdata)->objIsInt = FALSE;
267  (*probdata)->isSubProb = FALSE;
268 
269 
270  (*probdata)->ug = FALSE;
271  (*probdata)->nSolvers = 0;
272  (*probdata)->ugDual = 0.0;
273 
274  return SCIP_OKAY;
275 }
276 
277 
278 /** sets STP solving mode */
279 static
281  SCIP* scip, /**< SCIP data structure */
282  SCIP_PROBDATA* probdata /**< pointer to problem data */
283 )
284 {
285  char mode;
286 
287  SCIP_CALL( SCIPgetCharParam(scip, "stp/mode", &mode) );
288 
289  /* set STP solving mode */
290  probdata->mode = STP_MODE_CUT;
291  assert(mode != 'p' && "pricing mode currently not supported\n");
292 
293  if( mode == 'f' )
294  probdata->mode = STP_MODE_FLOW;
295  else
296  assert(mode == 'c');
297 
298  return SCIP_OKAY;
299 }
300 
301 
302 /** adds solution obtained during reduction...if existent */
303 static
305  SCIP* scip, /**< SCIP data structure */
306  SCIP_PROBDATA* probdata, /**< pointer to problem data */
307  REDSOL* redsol /**< solution storage for r */
308 )
309 {
310  GRAPH* graph = probdata->graph;
311  assert(graph && redsol);
312 
313  if( probdata->mode != STP_MODE_CUT )
314  {
315  return SCIP_OKAY;
316  }
317 
318  if( graph->terms == 1 )
319  {
320  return SCIP_OKAY;
321  }
322 
323  if( !graph_typeIsSpgLike(graph) && !graph_pc_isPcMw(graph) )
324  {
325  return SCIP_OKAY;
326  }
327  else
328  {
329  int* result;
330  SCIP_Real solval;
331  SCIP_Bool success;
332 
333  SCIP_CALL( SCIPallocBufferArray(scip, &result, graph->edges));
334 
335  SCIP_CALL( reduce_solGetEdgesol(scip, graph, redsol, &solval, result));
336 
337  if( LT(solval, FARAWAY ) )
338  {
339  assert(solstp_isValid(scip, graph, result));
340  SCIP_CALL( solpool_addSolToScip(scip, NULL, graph, result, &success) );
341  SCIPdebugMessage("try to add reduction solution with obj=%f, success=%d \n", solval + probdata->offset, success);
342  }
343 
344  SCIPfreeBufferArray(scip, &result);
345  }
346 
347  return SCIP_OKAY;
348 }
349 
350 
351 /** presolves STP */
352 static
354  SCIP* scip, /**< SCIP data structure */
355  SCIP_PROBDATA* probdata, /**< pointer to problem data */
356  REDSOL* redsol /**< solution storage for r */
357 )
358 {
359  GRAPH* packedgraph;
360  GRAPH* graph = probdata->graph;
361  SCIP_Real oldtimelimit;
362  SCIP_Real presoltimelimit;
363  int reduction;
364 
365  assert(graph);
366  assert(redsol);
367 
368  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &oldtimelimit) );
369  SCIP_CALL( SCIPgetRealParam(scip, "stp/pretimelimit", &presoltimelimit) );
370  SCIP_CALL( SCIPgetIntParam(scip, "stp/reduction", &reduction) );
371 
372  if( presoltimelimit > -0.5 )
373  SCIP_CALL( SCIPsetRealParam(scip, "limits/time", presoltimelimit) );
374 
375  /* save original root */
376  if( !graph_pc_isPcMw(graph) )
377  graph->orgsource = graph->source;
378 
379  probdata->norgedges = graph->edges;
380 
381 #ifdef UNIT_TEST_STP
382  SCIP_CALL( stptest_testAll(scip) );
383 #endif
384 
385 #ifdef STP_WRITE_RED_STATS
386  static int wasCalled = 0;
387  if( wasCalled == 0 )
388  {
389  wasCalled = 1;
391  exit(1);
392  }
393 #endif
394 
395  /* the actual presolving; NOTE: we always want to have userec=TRUE */
396  SCIP_CALL( reduce_exec(scip, graph, redsol, reduction, probdata->minelims, TRUE) );
397 
398  probdata->presolub = reduce_solGetUpperBoundWithOffset(redsol);
399  SCIPdebugMessage("presol ub: %f \n", probdata->presolub);
400 
401  {
402  int verblvl = 0;
403 #ifndef WITH_UG
404  SCIPgetIntParam(scip, "display/verblevel", &verblvl);
405 #endif
406  SCIP_CALL( graph_pack(scip, graph, &packedgraph, redsol, (verblvl > 0)) );
407  }
408 
409  graph = packedgraph;
410  assert(graph);
411 
412  probdata->stp_type = graph->stp_type;
413  probdata->graph = graph;
414 
415  SCIP_CALL( SCIPsetRealParam(scip, "limits/time", oldtimelimit) );
416 
417  return SCIP_OKAY;
418 }
419 
420 
421 /** frees the constraints of CUT model */
422 static
424  SCIP* scip, /**< SCIP data structure */
425  SCIP_PROBDATA* probdata /**< pointer to problem data */
426  )
427 {
428  assert(probdata->mode == STP_MODE_CUT);
429 
430  /* Degree-Constrained STP? */
431  if( probdata->stp_type == STP_DCSTP )
432  {
433  /* release degree constraints */
434  for( int t = 0; t < probdata->nnodes; ++t)
435  SCIP_CALL( SCIPreleaseCons(scip, &(probdata->degcons[t])) );
436 
437  SCIPfreeMemoryArrayNull(scip, &(probdata->degcons));
438  }
439 
440  if( probdata->graphHasVanished )
441  return SCIP_OKAY;
442 
443  /* PC variant STP? */
444  if( probdata->stp_type == STP_PCSPG || probdata->stp_type == STP_RPCSPG || probdata->stp_type == STP_MWCSP )
445  {
446 #if FLOWB
447  for( int e = 0; e < probdata->nnonterms; e++ )
448  SCIP_CALL( SCIPreleaseCons(scip, &(probdata->flowbcons[e])) );
449 
450  SCIPfreeMemoryArrayNull(scip, &(probdata->flowbcons));
451 #endif
452 
453  if( probdata->usecyclecons && probdata->stp_type == STP_PCSPG )
454  {
455  /* release degree constraints */
456  for( int e = 0; e < probdata->nedges; e++ )
457  SCIP_CALL( SCIPreleaseCons(scip, &(probdata->prizecyclecons[e])) );
458 
459  SCIPfreeMemoryArrayNull(scip, &(probdata->prizecyclecons));
460  }
461 
462  if( probdata->stp_type != STP_RPCSPG )
463  {
464  if( probdata->usesymcons )
465  {
466 #ifdef STP_AGG_SYM
467  const int e = probdata->realnterms - 1;
468 
469  for( int t = 0; t < e; ++t )
470  SCIP_CALL( SCIPreleaseCons(scip, &(probdata->prizesymcons[t])) );
471 #else
472  const int e = ((probdata->realnterms - 1) * probdata->realnterms) / 2;
473 
474  for( int t = 0; t < e; ++t )
475  SCIP_CALL( SCIPreleaseCons(scip, &(probdata->prizesymcons[t])) );
476 #endif
477 
478  SCIPfreeMemoryArrayNull(scip, &(probdata->prizesymcons));
479  }
480  SCIP_CALL( SCIPreleaseCons(scip, &(probdata->prizecons)) );
481  }
482  }
483 
484  return SCIP_OKAY;
485 }
486 
487 
488 /** frees the constraints of non-CUT model */
489 static
491  SCIP* scip, /**< SCIP data structure */
492  SCIP_PROBDATA* probdata /**< pointer to problem data */
493  )
494 {
495  assert(probdata->mode != STP_MODE_CUT);
496 
497  /* release path constraints */
498  if( probdata->mode == STP_MODE_PRICE )
499  {
500  for( int t = 0; t < probdata->realnterms; ++t )
501  SCIP_CALL( SCIPreleaseCons(scip, &(probdata->pathcons[t])) );
502  }
503  else
504  {
505  assert(probdata->mode == STP_MODE_FLOW);
506 
507  for( int t = 0; t < probdata->realnterms; ++t )
508  {
509  /* release constraints and variables */
510  for( int e = 0; e < probdata->nnodes - 1; ++e )
511  SCIP_CALL( SCIPreleaseCons(scip, &(probdata->pathcons[t * (probdata->nnodes - 1 ) + e])) );
512 
513  for( int e = 0; e < probdata->nedges; ++e )
514  SCIP_CALL( SCIPreleaseVar(scip, &probdata->flowvars[t * probdata->nedges + e]) );
515 
516  if( probdata->bigt )
517  break;
518  }
519 
520  SCIPfreeMemoryArrayNull(scip, &probdata->flowvars);
521  }
522 
523  /* release edge constraints of both Price and Flow */
524  for( int t = 0; t < probdata->realnterms; ++t )
525  {
526  for( int e = 0; e < probdata->nedges; ++e )
527  SCIP_CALL( SCIPreleaseCons(scip, &(probdata->edgecons[t * probdata->nedges + e])));
528 
529  if( probdata->bigt )
530  break;
531  }
532 
533  SCIPfreeMemoryArrayNull(scip, &(probdata->edgecons));
534  SCIPfreeMemoryArrayNull(scip, &(probdata->pathcons));
535 
536  return SCIP_OKAY;
537 }
538 
539 
540 /** frees the memory of the given problem data */
541 static
543  SCIP* scip, /**< SCIP data structure */
544  SCIP_PROBDATA** probdata /**< pointer to problem data */
545  )
546 {
547  SCIPdebugMessage("probdataFree \n");
548 
549  assert(scip != NULL);
550  assert(probdata != NULL);
551 
552  for( int e = 0; e < (*probdata)->nvars; ++e )
553  SCIP_CALL( SCIPreleaseVar(scip, &(*probdata)->edgevars[e]) );
554 
555  SCIPfreeMemoryArrayNull(scip, &(*probdata)->edgevars);
556 
557 #if USEOFFSETVAR
558  if( (*probdata)->offsetvar != NULL )
559  SCIP_CALL( SCIPreleaseVar(scip, &(*probdata)->offsetvar) );
560 #endif
561 
562  if( (*probdata)->mode == STP_MODE_CUT )
563  {
564  SCIP_CALL( freeConstraintsCutModel(scip, *probdata) );
565  }
566  else
567  {
568  SCIP_CALL( freeConstraintsNonCutModel(scip, *probdata) );
569  }
570 
571  if( (*probdata)->stp_type == STP_DHCSTP )
572  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->hopcons)) );
573 
574  if( (*probdata)->stp_type == STP_BRMWCSP )
575  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->budgetcons)) );
576 
577  SCIPfreeMemoryArrayNull(scip, &(*probdata)->xval);
578  SCIPfreeMemoryArrayNull(scip, &(*probdata)->realterms);
579  SCIPfreeMemoryArrayNull(scip, &(*probdata)->pctermsorder);
580 
581  /* free probdata */
582  SCIPfreeMemory(scip, probdata);
583 
584  return SCIP_OKAY;
585 }
586 
587 
588 /** create (edge-) HOP constraint (cut mode only) */
589 static
591  SCIP* scip, /**< SCIP data structure */
592  SCIP_PROBDATA* probdata /**< problem data */
593  )
594 {
595  GRAPH* graph;
596  SCIP_Real rhs;
597  assert(scip != NULL);
598  assert(probdata != NULL);
599 
600  SCIPdebugMessage("createHopeConstraint \n");
601  graph = probdata->graph;
602  assert(graph != NULL);
603  rhs = graph->hoplimit;
604  SCIPdebugMessage("Hop limit: %f \n ", rhs);
605 
606  /* @todo with presolving contractions enabled one might set rhs = rhs - (number of fixed edges) */
607  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->hopcons), "HopConstraint", 0, NULL, NULL,
608  -SCIPinfinity(scip), rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
609 
610  SCIP_CALL( SCIPaddCons(scip, probdata->hopcons) );
611 
612  return SCIP_OKAY;
613 }
614 
615 
616 static
618  SCIP* scip, /**< SCIP data structure */
619  SCIP_PROBDATA* probdata /**< problem data */
620  )
621 {
622  GRAPH* graph;
623  assert(scip != NULL);
624  assert(probdata != NULL);
625 
626  SCIPdebugMessage("create Budget constraint \n");
627  graph = probdata->graph;
628  assert(graph != NULL);
629  assert(graph->budget > 0.0);
630 
631  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->budgetcons), "BudgetConstraint", 0, NULL, NULL,
632  -SCIPinfinity(scip), graph->budget, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
633 
634  SCIP_CALL( SCIPaddCons(scip, probdata->budgetcons) );
635 
636  return SCIP_OKAY;
637 }
638 
639 /** create (node-) degree constraints (cut mode only) */
640 static
642  SCIP* scip, /**< SCIP data structure */
643  SCIP_PROBDATA* probdata /**< problem data */
644  )
645 
646 {
647  GRAPH* graph;
648  char consname[SCIP_MAXSTRLEN];
649  int k;
650  int nnodes;
651 
652  assert(scip != NULL);
653  assert(probdata != NULL);
654 
655  SCIPdebugMessage("createDegreeConstraints \n");
656  graph = probdata->graph;
657  nnodes = probdata->nnodes;
658 
659  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->degcons), nnodes ) );
660 
661  for( k = 0; k < nnodes; ++k )
662  {
663  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "DegreeConstraint%d", k);
664  SCIP_CALL( SCIPcreateConsLinear(scip, &(probdata->degcons[k]), consname, 0, NULL, NULL,
665  -SCIPinfinity(scip), (SCIP_Real)graph->maxdeg[k], TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
666 
667  SCIP_CALL( SCIPaddCons(scip, probdata->degcons[k]) );
668  }
669 
670  return SCIP_OKAY;
671 }
672 
673 
674 /** create Prize constraints (cut mode only) */
675 static
677  SCIP* scip, /**< SCIP data structure */
678  SCIP_PROBDATA* probdata /**< problem data */
679  )
680 
681 {
682  GRAPH* graph;
683  int r;
684  int ro2;
685  int root;
686  int nedges;
687  int realnterms;
688  char consname[SCIP_MAXSTRLEN];
689 
690  assert(scip != NULL);
691  assert(probdata != NULL);
692 
693  graph = probdata->graph;
694  realnterms = probdata->realnterms;
695 
696  assert(graph != NULL);
697  assert(graph->stp_type != STP_RPCSPG);
698 
699  root = graph->source;
700  nedges = graph->edges;
701 
702  SCIPdebugMessage("createPrizeConstraints \n");
703 
704  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PrizeConstraint");
705  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizecons), consname, 0, NULL, NULL, 1.0, 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE));
706  SCIP_CALL( SCIPaddCons(scip, probdata->prizecons) );
707 
708  if( probdata->usesymcons )
709  {
710 #ifdef STP_AGG_SYM
711  ro2 = realnterms - 1;
712 #else
713  ro2 = (realnterms * (realnterms - 1)) / 2;
714 #endif
715  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->prizesymcons), ro2) );
716 
717  for( r = 0; r < ro2; r++ )
718  {
719  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PrizeSymConstraint%d", r);
720 #ifndef STP_SYM_PRIZE
721  SCIP_CALL( SCIPcreateConsSetpack(scip, &(probdata->prizesymcons[r]), consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ));
722 #else
723  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizesymcons[r]), consname, 0, NULL, NULL,
724  -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
725 #endif
726 
727  SCIP_CALL(SCIPaddCons(scip, probdata->prizesymcons[r]));
728  }
729  }
730 
731  if( probdata->usecyclecons && graph->stp_type == STP_PCSPG )
732  {
733  ro2 = 0;
734  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->prizecyclecons), nedges) );
735  for( r = 0; r < nedges; r++ )
736  {
737  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PrizeLPConstraint%d", ro2);
738  if( root == graph->head[r] )
739  {
740  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizecyclecons[ro2]), consname, 0, NULL, NULL,
741  -SCIPinfinity(scip), 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
742  }
743  else
744  {
745  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizecyclecons[ro2]), consname, 0, NULL, NULL,
746  -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
747  }
748  SCIP_CALL( SCIPaddCons(scip, probdata->prizecyclecons[ro2++]) );
749  }
750  }
751 
752  return SCIP_OKAY;
753 }
754 
755 
756 #if FLOWB
757 /** create Flow Balance constraints (cut mode only) */
758 static
759 SCIP_RETCODE createFlowBalanceConstraints(
760  SCIP* scip, /**< SCIP data structure */
761  SCIP_PROBDATA* probdata /**< problem data */
762  )
763 
764 {
765  GRAPH* graph;
766  int r;
767  int nnonterms;
768  char consname[SCIP_MAXSTRLEN];
769 
770  assert(scip != NULL);
771  assert(probdata != NULL);
772 
773  graph = probdata->graph;
774 
775  assert(graph != NULL);
776 
777  if( graph->stp_type == STP_RPCSPG )
778  nnonterms = graph->knots - graph->terms;
779  else
780  nnonterms = graph->knots - graph->terms;
781 
782  probdata->nnonterms = nnonterms;
783 
784  SCIPdebugMessage("createFlowBalanceConstraints \n");
785 
786 
787  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->flowbcons), nnonterms) );
788  for( r = 0; r < nnonterms; r++ )
789  {
790  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "FlowBalanceConstraint%d", r);
791  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->flowbcons[r]), consname, 0, NULL, NULL,
792  -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
793  SCIP_CALL( SCIPaddCons(scip, probdata->flowbcons[r]) );
794  }
795 
796  return SCIP_OKAY;
797 }
798 
799 #endif
800 
801 #if 0
802 /** create constraints (in Flow or Price Mode) */
803 static
804 SCIP_RETCODE createC4Cuts(
805  SCIP* scip, /**< SCIP data structure */
806  SCIP_PROBDATA* probdata /**< problem data */
807  )
808 {
809  const GRAPH* graph = probdata->graph;
810  int* nodes_mark;
811  const int nnodes = graph_get_nNodes(graph);
812  const int nedges = graph_get_nEdges(graph);
813  int c4nodes[4];
814 
815  SCIP_CALL( SCIPallocBufferArray(scip, &nodes_mark, nnodes) );
816 
817  for( int i = 0; i < nnodes; ++i )
818  {
819  nodes_mark[i] = 0;
820  }
821 
822  for( int basenode = 0; basenode < nnodes; basenode++ )
823  {
824  if( Is_term(graph->term[basenode]) )
825  continue;
826 
827  c4nodes[0] = basenode;
828  nodes_mark[basenode] = -nedges - 1;
829 
830  // mark neighbors
831  for( int e = graph->outbeg[basenode]; e != EAT_LAST; e = graph->oeat[e] )
832  {
833  const int neighbor = graph->head[e];
834  nodes_mark[neighbor] = -e - 1;
835  }
836 
837  // look for cycles
838  for( int e = graph->outbeg[basenode]; e != EAT_LAST; e = graph->oeat[e] )
839  {
840  const int neighbor = graph->head[e];
841  if( Is_term(graph->term[neighbor]) )
842  continue;
843 
844  for( int e2 = graph->outbeg[neighbor]; e2 != EAT_LAST; e2 = graph->oeat[e2] )
845  {
846  const int neighbor2 = graph->head[e2];
847  if( Is_term(graph->term[neighbor2]) )
848  continue;
849 
850  // not visited yet?
851  if( nodes_mark[neighbor2] == 0 )
852  {
853  nodes_mark[neighbor2] = e2 + 1;
854  }
855  // cycle closed?
856  else if( nodes_mark[neighbor2] > 0 )
857  {
859 
860  const int e3 = nodes_mark[neighbor2] - 1;
861  const int neighbor_alt = graph->tail[e3];
862  int e4;
863 
864  assert(nodes_mark[neighbor_alt] < 0);
865 
866  e4 = -nodes_mark[neighbor_alt] - 1;
867  assert(graph_edge_isInRange(graph, e3));
868  assert(graph_edge_isInRange(graph, e4));
869  assert(graph->tail[e4] == basenode);
870  assert(neighbor != neighbor_alt);
871 
872  c4nodes[1] = neighbor;
873  c4nodes[2] = neighbor2;
874  c4nodes[3] = neighbor_alt;
875 
876  addCut = FALSE;
877  for( int q = 0; q < 4; q++ )
878  if( Is_pseudoTerm(graph->term[c4nodes[q]]) )
879  addCut = TRUE;
880 
881  for( int q = 1; q < 4; q++ )
882  {
883  const int node = c4nodes[q];
884  if( node < basenode )
885  {
886  addCut = FALSE;
887  break;
888  }
889  }
890 
891 
892 
893  if( addCut )
894  {
895  int c4edges[4] = { e, e2, e3, e4 };
896  for( int i = 0; i < 4; ++i )
897  {
898  SCIP_CONS* cons = NULL;
899 
900  const int node_i = c4nodes[i];
901 
902  SCIP_CALL( SCIPcreateConsLinear(scip, &cons, "c4", 0, NULL, NULL,
903  -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
904 
905  // add cycle edges
906  for( int q = 0; q < 4; q++ )
907  {
908  const int edge = c4edges[q];
909  SCIP_CALL( SCIPaddCoefLinear(scip, cons, probdata->edgevars[edge], 1.0) );
910  SCIP_CALL( SCIPaddCoefLinear(scip, cons, probdata->edgevars[flipedge(edge)], 1.0) );
911  }
912 
913  // add in-edges
914  for( int j = 0; j < 4; j++ )
915  {
916  const int node_j = c4nodes[j];
917  if( i == j )
918  continue;
919 
920  for( int inedge_j = graph->inpbeg[node_j]; inedge_j != EAT_LAST; inedge_j = graph->ieat[inedge_j] )
921  {
922  SCIP_CALL( SCIPaddCoefLinear(scip, cons, probdata->edgevars[inedge_j], -1.0) );
923  }
924  }
925 
926  graph_knot_printInfo(graph, node_i);
927 
928  SCIP_CALL( SCIPaddCons(scip, cons) );
929  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
930  }
931 
932  }
933  }
934  }
935  }
936 
937 
938  // nodes_mark[basenode] = 0;
939  for( int i = 0; i < nnodes; ++i )
940  {
941  nodes_mark[i] = 0;
942  }
943 
944  }
945 
946  SCIPfreeBuffer(scip, &nodes_mark);
947 
948  return SCIP_OKAY;
949 }
950 #endif
951 
952 /** create constraints (in Flow or Price Mode) */
953 static
955  SCIP* scip, /**< SCIP data structure */
956  SCIP_PROBDATA* probdata /**< problem data */
957  )
958 {
959  GRAPH* graph;
960  char consname[SCIP_MAXSTRLEN];
961  int t;
962  int e;
963  int k;
964  int k2;
965  int realnterms;
966  int nedges;
967  int nnodes;
968 
969  assert(scip != NULL);
970  assert(probdata != NULL);
971  assert(probdata->mode != STP_MODE_CUT);
972 
973  SCIPdebugMessage("createConstraints \n");
974  graph = probdata->graph;
975  nedges = probdata->nedges;
976  nnodes = probdata->nnodes;
977  realnterms = probdata->realnterms;
978 
979  /* create edge constraints (used by both Flow and Price) */
980  if( !probdata->bigt )
981  {
982  /* create |T \ {root}|*|E| edge constraints (disaggregated) */
983  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->edgecons), (realnterms) * (nedges)) );
984  for( t = 0; t < realnterms; ++t )
985  {
986  for( e = 0; e < nedges; ++e )
987  {
988  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "EdgeConstraint%d_%d", t, e);
989  SCIP_CALL( SCIPcreateConsLinear ( scip, &( probdata->edgecons[t * nedges + e] ), consname, 0, NULL, NULL,
990  -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, probdata->mode == STP_MODE_PRICE, FALSE, FALSE, FALSE) );
991  SCIP_CALL( SCIPaddCons(scip, probdata->edgecons[t * nedges + e]) );
992  }
993  }
994  }
995  else
996  {
997  /* create |E| edge constraints (aggregated) */
998  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->edgecons), nedges) );
999  for( e = 0; e < nedges; ++e )
1000  {
1001  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "EdgeConstraintT%d", e);
1002  SCIP_CALL( SCIPcreateConsLinear ( scip, &( probdata->edgecons[e] ), consname,
1003  0, NULL, NULL, -SCIPinfinity(scip), 0.0,
1004  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, probdata->mode == STP_MODE_PRICE, FALSE, FALSE, FALSE) );
1005  SCIP_CALL( SCIPaddCons(scip, probdata->edgecons[e]) );
1006  }
1007  }
1008 
1009  /* Branch and Price mode */
1010  if( probdata->mode == STP_MODE_PRICE )
1011  {
1012  /* create |T \ {root}| path constraints */
1013  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->pathcons), realnterms) );
1014 
1015  for( t = 0; t < realnterms; ++t )
1016  {
1017  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraint%d", t);
1018  SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->pathcons[t]), consname, 0, NULL, NULL, 1.0, SCIPinfinity(scip),
1019  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE) );
1020 
1021  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[t]) );
1022  }
1023  }
1024  /* Flow mode */
1025  else if( probdata->mode == STP_MODE_FLOW )
1026  {
1027  /* create path constraints */
1028  if( !probdata->bigt )
1029  {
1030  /* not in 'T' mode, so create |T \ {root} |*|V \ {root}| path constraints */
1031  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->pathcons), realnterms * (nnodes - 1)) );
1032  for( t = 0; t < realnterms; ++t )
1033  {
1034  k2 = 0;
1035  for( k = 0; k < nnodes; ++k )
1036  {
1037  /* if node k is not the root */
1038  if( k != graph->source)
1039  {
1040  /* if node k is not the t-th terminal, set RHS = 0 */
1041  if( k != probdata->realterms[t] )
1042  {
1043  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraint%d_%d", t, k2);
1044  SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[t * (nnodes - 1) + k2] ), consname,
1045  0, NULL, NULL, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1046  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[t * (nnodes - 1) + k2]) );
1047  }
1048 
1049  /* if node k is the t-th terminal, set RHS = 1 */
1050  else
1051  {
1052  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraint%d_%d", t, k2);
1053  SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[t * (nnodes - 1) + k2] ), consname,
1054  0, NULL, NULL, 1.0, 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1055  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[t * (nnodes - 1) + k2]) );
1056  }
1057 
1058  k2 += 1;
1059  }
1060  }
1061  }
1062  }
1063  else
1064  {
1065  /* in 'T' mode, so create |V \ {root}| path constraints */
1066  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->pathcons), (nnodes - 1)) );
1067  k2 = 0;
1068  for( k = 0; k < nnodes; ++k )
1069  {
1070  /* if node k is not the root */
1071  if( k != graph->source)
1072  {
1073  /* if node k is not a terminal, set RHS = 0 */
1074  if( graph->term[k] != 0 )
1075  {
1076  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraintT%d", k2);
1077  SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[k2] ), consname,
1078  0, NULL, NULL, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1079  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[k2]) );
1080  }
1081  /* if node k is a terminal, set RHS = 1 */
1082  else
1083  {
1084  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "PathConstraintT%d", k2);
1085  SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[k2] ), consname,
1086  0, NULL, NULL, 1.0, 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1087  SCIP_CALL( SCIPaddCons(scip, probdata->pathcons[k2]) );
1088  }
1089  k2 += 1;
1090  }
1091  }
1092  }
1093  }
1094 
1095  return SCIP_OKAY;
1096 }
1097 
1098 /** create initial columns */
1099 static
1101  SCIP* scip, /**< SCIP data structure */
1102  SCIP_PROBDATA* probdata, /**< problem data */
1103  SCIP_Real offset /**< offset computed during the presolving */
1104  )
1105 {
1106  GRAPH* graph;
1107  SCIP_VAR* var;
1108  SCIP_Real* edgecost;
1109  int e;
1110  int t;
1111  int k;
1112  int k2;
1113  int tail;
1114  char varname[SCIP_MAXSTRLEN];
1115  SCIP_Bool objint = SCIPisIntegral(scip, offset);
1116 
1117  assert(scip != NULL);
1118  assert(probdata != NULL);
1119 
1120  t = 0;
1121  graph = probdata->graph;
1122  SCIPdebugMessage("create Variables \n");
1123 
1124  /* nontrivial problem? */
1125  if( !probdata->graphHasVanished )
1126  {
1127  int nedges = probdata->nedges;
1128  int nvars = probdata->nvars;
1129  int realnterms = probdata->realnterms;
1130  int root = graph->source;
1131  int nnodes = graph->knots;
1132 
1133  assert(nedges == graph->edges);
1134  assert(realnterms >= 0);
1135 
1136  SCIP_CALL( SCIPallocMemoryArray(scip, &probdata->xval, nvars) );
1137  SCIP_CALL( SCIPallocMemoryArray(scip, &probdata->edgevars, nvars) );
1138 
1139  /* cut mode */
1140  if( probdata->mode == STP_MODE_CUT )
1141  {
1142  int a;
1143  assert(probdata->nlayers == 1);
1144 
1145  for( e = 0; e < nedges; ++e )
1146  {
1147  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "x_%d_%d", graph->tail[e], graph->head[e]);
1148  SCIP_CALL( SCIPcreateVarBasic(scip, &probdata->edgevars[e], varname, 0.0, 1.0, graph->cost[e], SCIP_VARTYPE_BINARY) );
1149  SCIP_CALL( SCIPaddVar(scip, probdata->edgevars[e]) );
1150  objint = objint && SCIPisIntegral(scip, graph->cost[e]);
1151  }
1152 
1153  /* Hop-Constrained STP */
1154  if( graph->stp_type == STP_DHCSTP )
1155  {
1156  SCIP_Real hopfactor;
1157  for( e = 0; e < nedges; ++e )
1158  {
1159  /* @note: When contractions are used in presolving: modify */
1160  hopfactor = 1.0;
1161  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->hopcons, probdata->edgevars[e], hopfactor) );
1162  }
1163  }
1164 
1165  if( graph->stp_type == STP_BRMWCSP )
1166  {
1167  for( k = 0; k < nnodes; ++k )
1168  {
1169  const SCIP_Real kbudget = graph->costbudget[k];
1170  assert(kbudget >= 0.0);
1171  assert(graph->extended);
1172 
1173  if( graph_pc_knotIsDummyTerm(graph, k) )
1174  continue;
1175 
1176  if( SCIPisZero(scip, kbudget) )
1177  continue;
1178 
1179  for( e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
1180  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->budgetcons, probdata->edgevars[e], kbudget) );
1181  }
1182  }
1183 
1184  /* Degree-Constrained STP */
1185  if( graph->stp_type == STP_DCSTP )
1186  {
1187  for( k = 0; k < nnodes; ++k )
1188  {
1189  for( e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
1190  {
1191  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->degcons[k], probdata->edgevars[e], 1.0) );
1192  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->degcons[k], probdata->edgevars[flipedge(e)], 1.0) );
1193  }
1194  }
1195  }
1196 
1197 #if FLOWB
1198  k2 = 0;
1199 
1200  for( k = 0; k < nnodes; k++ )
1201  {
1202  if( !Is_term(graph->term[k]) )
1203  {
1204  /* incoming arcs */
1205  for( a = graph->inpbeg[k]; a != EAT_LAST; a = graph->ieat[a] )
1206  {
1207  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->flowbcons[k2], probdata->edgevars[a], 1.0) );
1208  }
1209  /* outgoing arcs */
1210  for( a = graph->outbeg[k]; a != EAT_LAST; a = graph->oeat[a] )
1211  {
1212  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->flowbcons[k2], probdata->edgevars[a], -1.0) );
1213  }
1214  k2++;
1215  }
1216  }
1217 #endif
1218 
1219  if( graph_pc_isPcMw(graph) )
1220  {
1221  for( e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
1222  {
1223  const int head = graph->head[e];
1224  if( Is_term(graph->term[head]) && !graph_pc_knotIsFixedTerm(graph, head) )
1225  {
1226  assert(graph->grad[head] == 2);
1227  assert(graph->prize != NULL);
1228 
1229  /* variables are preferred to be branched on */
1230  SCIP_CALL(SCIPchgVarBranchPriority(scip, probdata->edgevars[e], 100 + (int)(100.0 * graph->prize[head])));
1231  }
1232  }
1233  }
1234 
1235  if( graph->stp_type == STP_PCSPG || graph->stp_type == STP_MWCSP )
1236  {
1237  int* pseudoterms = NULL;
1238 
1239  assert(graph->extended);
1240  assert(nnodes == probdata->nnodes);
1241 
1242  SCIP_CALL( SCIPallocMemoryArray(scip, &(probdata->pctermsorder), nnodes) );
1243 
1244  t = 0;
1245  for( int v = 0; v < nnodes; v++ )
1246  {
1247  if( Is_pseudoTerm(graph->term[v]) )
1248  probdata->pctermsorder[v] = t++;
1249  else
1250  probdata->pctermsorder[v] = nnodes;
1251  }
1252  assert(t == probdata->realnterms);
1253 
1254  if( probdata->usesymcons )
1255  SCIP_CALL( SCIPallocBufferArray(scip, &pseudoterms, probdata->realnterms) );
1256 
1257  if( probdata->usecyclecons && graph->stp_type == STP_PCSPG )
1258  {
1259  for( e = 0; e < nedges; e++ )
1260  {
1261  const int head = graph->head[e];
1262  SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizecyclecons[e], probdata->edgevars[e], 1.0));
1263  SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizecyclecons[e], probdata->edgevars[flipedge(e)], 1.0));
1264  if( root != head )
1265  {
1266  for( a = graph->inpbeg[head]; a != EAT_LAST; a = graph->ieat[a] )
1267  {
1268  SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizecyclecons[e], probdata->edgevars[a], -1.0));
1269  }
1270  }
1271  }
1272  }
1273 
1274  t = 0;
1275  k2 = 0;
1276  for( e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
1277  {
1278  const int head = graph->head[e];
1279  if( !Is_term(graph->term[head]) )
1280  {
1281  SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizecons, probdata->edgevars[e], 1.0));
1282 
1283  assert(graph->prize != NULL);
1284  if( probdata->usesymcons )
1285  {
1286  assert(pseudoterms != NULL);
1287 
1288  pseudoterms[t] = head;
1289 #ifdef STP_AGG_SYM
1290 #ifndef STP_SYM_PRIZE
1291  for( int prev = 0; prev < t; prev++ )
1292  SCIP_CALL( SCIPaddCoefSetppc(scip, probdata->prizesymcons[prev], probdata->edgevars[e]) );
1293 
1294  /* skip the last term */
1295  if( t == graph->terms - 2 )
1296  {
1297  assert(t == probdata->realnterms - 1);
1298  continue;
1299  }
1300 
1301  for( a = graph->inpbeg[head]; a != EAT_LAST; a = graph->ieat[a] )
1302  SCIP_CALL( SCIPaddCoefSetppc(scip, probdata->prizesymcons[t], probdata->edgevars[a]) );
1303 #endif
1304 #else
1305  for( k = 0; k < t; k++ )
1306  {
1307  for( a = graph->inpbeg[pseudoterms[k]]; a != EAT_LAST; a = graph->ieat[a] )
1308  {
1309  SCIP_CALL(SCIPaddCoefSetppc(scip, probdata->prizesymcons[k2], probdata->edgevars[a]));
1310  }
1311 
1312  SCIP_CALL(SCIPaddCoefSetppc(scip, probdata->prizesymcons[k2], probdata->edgevars[e]));
1313  k2++;
1314  }
1315 #endif
1316  t++;
1317  }
1318  }
1319  }
1320 
1321  if( probdata->usesymcons )
1322  {
1323 #ifdef STP_SYM_PRIZE
1324  SCIP_Real* termprizes = NULL;
1325 
1326  if( probdata->realnterms > 0 )
1327  SCIP_CALL( SCIPallocBufferArray(scip, &termprizes, probdata->realnterms) );
1328 
1329  assert(t == graph->terms - 1);
1330  assert(probdata->realnterms == t);
1331 
1332  for( int s = 0; s < probdata->realnterms; s++ )
1333  {
1334  const int pterm = pseudoterms[s];
1335  assert(Is_pseudoTerm(graph->term[pterm]));
1336  assert(graph->prize[pterm] > 0.0);
1337 
1338  termprizes[s] = graph->prize[pterm];
1339  }
1340  SCIPsortRealInt(termprizes, pseudoterms, probdata->realnterms);
1341 #ifndef NDEBUG
1342  for( int s = 1; s < probdata->realnterms; s++ )
1343  assert(graph->prize[pseudoterms[s - 1]] <= graph->prize[pseudoterms[s]]);
1344 #endif
1345 
1346  for( int s = 0; s < probdata->realnterms; s++ )
1347  {
1348  const int pterm = pseudoterms[s];
1349  const int twin = graph_pc_getTwinTerm(graph, pterm);
1350  const int twinrootedge = graph_pc_getRoot2PtermEdge(graph, twin);
1351  const int prootedge = graph_pc_getRoot2PtermEdge(graph, pterm);
1352 
1353  assert(graph->prize[pterm] == graph->cost[twinrootedge]);
1354  assert(graph->cost[prootedge] == 0.0);
1355 
1356  for( int prev = 0; prev < s; prev++ )
1357  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->prizesymcons[prev], probdata->edgevars[prootedge], 1.0) );
1358 
1359  if( s == probdata->realnterms - 1 )
1360  break;
1361 
1362  SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizesymcons[s], probdata->edgevars[twinrootedge], -1.0));
1363 #if 0
1364  for( a = graph->inpbeg[pterm]; a != EAT_LAST; a = graph->ieat[a] )
1365  SCIP_CALL( SCIPaddCoefSetppc(scip, probdata->prizesymcons[s], probdata->edgevars[a]) );
1366 #endif
1367  }
1368 
1369  for( int p = 0; p < probdata->realnterms; p++ )
1370  {
1371  const int index = pseudoterms[p];
1372  assert(probdata->pctermsorder[index] >= 0);
1373 
1374  probdata->pctermsorder[index] = p;
1375  }
1376 
1377  SCIPfreeBufferArray(scip, &termprizes);
1378 #endif
1379  SCIPfreeBufferArrayNull(scip, &pseudoterms);
1380  }
1381  }
1382  }
1383  /* Price or Flow mode */
1384  else
1385  {
1386  /* create and add the edge variables */
1387  for( e = 0; e < nedges; ++e )
1388  {
1389  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "EdgeVar%d_%d", graph->tail[e], graph->head[e]);
1390  var = NULL;
1391  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, 1.0, graph->cost[e], SCIP_VARTYPE_BINARY) );
1392  objint = objint && SCIPisIntegral(scip, graph->cost[e]);
1393  SCIP_CALL( SCIPaddVar(scip, var) );
1394  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
1395 
1396  if( !probdata->bigt )
1397  {
1398  for( t = 0; t < realnterms; ++t )
1399  {
1400  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + e], var, -1.0) );
1401  }
1402  }
1403  else
1404  {
1405  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[e], var, (double ) -realnterms));
1406  }
1407  probdata->edgevars[e] = var;
1408  }
1409  }
1410 
1411  /* Price mode */
1412  if( probdata->mode == STP_MODE_PRICE )
1413  {
1414  PATH* path;
1415 
1416  /* the flow variables are not used in the Price mode */
1417  probdata->flowvars = NULL;
1418 
1419  /* compute shortest paths to the root */
1420  SCIP_CALL(SCIPallocBufferArray(scip, &path, graph->knots));
1421  SCIP_CALL(SCIPallocBufferArray(scip, &edgecost, nedges));
1422  for (e = 0; e < nedges; ++e)
1423  edgecost[e] = graph->cost[e];
1424 
1425  for (e = 0; e < graph->knots; e++)
1426  graph->mark[e] = 1;
1427 
1428  graph_path_exec(scip, graph, FSP_MODE, root, edgecost, path);
1429 
1430  /* create and add initial path variables (one for each real terminal) */
1431  for( t = 0; t < realnterms; ++t )
1432  {
1433  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "PathVar%d_0", t);
1434  var = NULL;
1435  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1436  SCIP_CALL( SCIPaddVar(scip, var) );
1437  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
1438  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t], var, 1.0) );
1439  tail = probdata->realterms[t];
1440  while( tail != root )
1441  {
1442  if( !probdata->bigt )
1443  {
1444  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + path[tail].edge], var, 1.0));
1445  }
1446  else
1447  {
1448  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[path[tail].edge], var, 1.0));
1449  }
1450 
1451  tail = graph->tail[path[tail].edge];
1452  }
1453  }
1454 
1455  /* free local arrays */
1456  SCIPfreeBufferArray(scip, &edgecost);
1457  SCIPfreeBufferArray(scip, &path);
1458  }
1459  /* Flow mode */
1460  else if( probdata->mode == STP_MODE_FLOW )
1461  {
1462  /* store the number of disparate flows (commodities) in nflows */
1463  int nflows;
1464  if ( !probdata->bigt )
1465  nflows = realnterms;
1466  else
1467  nflows = 1;
1468 
1469  SCIP_CALL( SCIPallocMemoryArray(scip, &probdata->flowvars, nflows * nedges) );
1470 
1471  /* create and add the flow variables */
1472  for( e = 0; e < nedges; ++e )
1473  {
1474  for( t = 0; t < nflows; ++t )
1475  {
1476  var = NULL;
1477  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "FlowVar%d.%d_%d", t, graph->tail[e], graph->head[e]);
1478  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1479  SCIP_CALL( SCIPaddVar(scip, var) );
1480  probdata->flowvars[t * nedges + e] = var;
1481  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + e], probdata->flowvars[t * nedges + e], 1.0) );
1482  }
1483  }
1484 
1485  /* add the flow variables to the corresponding path constraints */
1486  for( t = 0; t < nflows; ++t )
1487  {
1488  k2 = 0;
1489  for( k = 0; k < nnodes; ++k )
1490  {
1491  if( k != root )
1492  {
1493  e = graph->inpbeg[k];
1494  while( e >= 0 )
1495  {
1496  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t * (nnodes - 1) + k2], probdata->flowvars[t * nedges + e], 1.0) );
1497  e = graph->ieat[e];
1498  }
1499  e = graph->outbeg[k];
1500  while( e >= 0 )
1501  {
1502  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t * (nnodes - 1) + k2], probdata->flowvars[t * nedges + e], -1.0) );
1503  e = graph->oeat[e];
1504  }
1505  k2 += 1;
1506  }
1507  }
1508  }
1509  }
1510 
1511  /* if all edge costs and the offset are integral, tell SCIP the objective will be integral */
1512  if( objint )
1513  SCIP_CALL( SCIPsetObjIntegral(scip) );
1514  }
1515  else
1516  {
1517  probdata->edgevars = NULL;
1518  probdata->flowvars = NULL;
1519  }
1520 
1521  probdata->objIsInt = objint;
1522 
1523 #if USEOFFSETVAR
1524  /* add offset */
1525  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "OFFSET");
1526  SCIP_CALL( SCIPcreateVarBasic(scip, &probdata->offsetvar, varname, 1.0, 1.0, offset, SCIP_VARTYPE_INTEGER) );
1527  SCIP_CALL( SCIPaddVar(scip, probdata->offsetvar) );
1528 #else
1529  SCIP_CALL( SCIPaddOrigObjoffset(scip, offset) );
1530 #endif
1531 
1532  return SCIP_OKAY;
1533 }
1534 
1535 
1536 /** creates the actual MIP/IP model */
1537 static
1539  SCIP* scip, /**< SCIP data structure */
1540  SCIP_PROBDATA* probdata /**< problem data */
1541  )
1542 {
1543  assert(probdata);
1544 
1545  if( !probdata->graphHasVanished )
1546  {
1547  GRAPH* const graph = probdata->graph;
1548 
1549  const int nnodes = graph_get_nNodes(graph);
1550  const int nedges = graph_get_nEdges(graph);
1551  /* compute the real number of terminals (basically nterms - 1) */
1552  const int realnterms = graph->terms - 1;
1553  const SCIP_Bool mw = (graph->stp_type == STP_MWCSP);
1554  const SCIP_Bool pc = (graph->stp_type == STP_PCSPG);
1555 
1556  assert(graph->terms >= 1);
1557 
1558  SCIP_CALL(graph_path_init(scip, graph));
1559 #ifdef WITH_UG
1560  SCIP_CALL( graph_path_init(scip, probdata->orggraph) );
1561  #endif
1562 
1563  if( probdata->mode == STP_MODE_CUT )
1564  {
1565  SCIP_CALL(graph_mincut_init(scip, graph));
1566  }
1567 
1568  probdata->nvars = nedges;
1569  probdata->nnodes = nnodes;
1570  probdata->nedges = nedges;
1571  probdata->nterms = graph->terms;
1572  probdata->nlayers = graph->layers;
1573  probdata->realnterms = realnterms;
1574 
1575  assert(Is_term(graph->term[graph->source]));
1576 
1577  SCIP_CALL(SCIPallocMemoryArray(scip, &probdata->realterms, realnterms));
1578 
1579  for( int k = 0, t = 0; k < nnodes; ++k )
1580  {
1581  if( graph->term[k] == 0 && k != graph->source )
1582  {
1583  probdata->realterms[t] = k;
1584  SCIPdebugMessage("realterms[%d] = %d \n ", t, probdata->realterms[t]);
1585  t++;
1586  }
1587  }
1588 
1589  if( probdata->mode == STP_MODE_CUT )
1590  {
1591  SCIP_CONS* cons;
1592 
1593  /* create and add constraint for Branch and Cut */
1594  SCIP_CALL(SCIPcreateConsStp(scip, &cons, "stpcons", probdata->graph));
1595  SCIP_CALL(SCIPaddCons(scip, cons));
1596  SCIP_CALL(SCIPreleaseCons(scip, &cons));
1597 
1598  /* if the problem is a HOP-Constrained-STP, an additional constraint is required */
1599  if( graph->stp_type == STP_DHCSTP )
1600  {
1601  SCIP_CALL(createHopConstraint(scip, probdata));
1602  }
1603 
1604  /* if the problem is a Degree-Constrained-STP, additional constraints are required */
1605  if( graph->stp_type == STP_DCSTP )
1606  {
1607  SCIP_CALL(createDegreeConstraints(scip, probdata));
1608  }
1609 
1610  if( graph->stp_type == STP_BRMWCSP )
1611  {
1612  SCIP_CALL(createBudgetConstraint(scip, probdata));
1613  }
1614 
1615  /* if the problem is a Prize-Collecting-STP or a Maximum Weight Connected Subgraph Problem, additional constraints are required */
1616  if( pc || mw )
1617  {
1618  SCIP_CALL(createPrizeConstraints(scip, probdata));
1619  }
1620 #if FLOWB
1621  SCIP_CALL( createFlowBalanceConstraints(scip, probdata) );
1622  #endif
1623  }
1624  else
1625  {
1626  /* create and add constraints for Flow or Branch and Price */
1627  SCIP_CALL(createConstraints(scip, probdata));
1628  }
1629  }
1630  /* graph reduction solved the whole problem, set vars to zero or NULL */
1631  else
1632  {
1633  probdata->pathcons = NULL;
1634  probdata->edgecons = NULL;
1635  probdata->nlayers = 0;
1636  probdata->nnodes = 1;
1637  probdata->nedges = 0;
1638  probdata->nterms = 1;
1639  probdata->nnonterms = 0;
1640  probdata->realnterms = 0;
1641  probdata->nedges = 0;
1642  probdata->nvars = 0;
1643  probdata->realterms = NULL;
1644  probdata->xval = NULL;
1645  }
1646  probdata->pctermsorder = NULL;
1647 
1648  /* create and add initial variables */
1649  SCIP_CALL( createVariables(scip, probdata, probdata->offset) );
1650 
1651  return SCIP_OKAY;
1652 }
1653 
1654 
1655 /** creates a log file */
1656 static
1658  SCIP* scip, /**< SCIP data structure */
1659  SCIP_PROBDATA* probdata, /**< problem data */
1660  const char* intlogfilename, /**< user parameter */
1661  const char* logfilename, /**< user parameter */
1662  const char* filename, /**< file name */
1663  const char* probname /**< problem name */
1664  )
1665 {
1666 
1667 #ifdef WITH_UG
1668  if( getUgRank() != 0 )
1669  {
1670  logfilename = NULL;
1671  intlogfilename = NULL;
1672  }
1673 #endif
1674 
1675  if( logfilename != NULL && logfilename[0] != '\0' )
1676  {
1677  char finalfilename[SCIP_MAXSTRLEN];
1678 
1679  if( strcmp("use_probname", logfilename) == 0 )
1680  (void) SCIPsnprintf(finalfilename, SCIP_MAXSTRLEN, "%s.stplog", probname);
1681  else
1682  (void) SCIPsnprintf(finalfilename, SCIP_MAXSTRLEN, "%s", logfilename);
1683 
1684  probdata->logfile = fopen(finalfilename, "w");
1685 
1686  if( probdata->logfile == NULL )
1687  {
1688  SCIPerrorMessage("cannot create file <%s> for writing\n", finalfilename);
1689  SCIPprintSysError(finalfilename);
1690  return SCIP_FILECREATEERROR;
1691  }
1692  }
1693 
1694  if( intlogfilename != NULL && intlogfilename[0] != '\0' )
1695  {
1696  char finalfilename[SCIP_MAXSTRLEN];
1697 
1698  if( strcmp("use_probname", intlogfilename) == 0 )
1699  (void) SCIPsnprintf(finalfilename, SCIP_MAXSTRLEN, "%s_int.stplog", probname);
1700  else
1701  (void) SCIPsnprintf(finalfilename, SCIP_MAXSTRLEN, "%s", intlogfilename);
1702 
1703  probdata->intlogfile = fopen(finalfilename, "w");
1704 
1705  if( probdata->intlogfile == NULL )
1706  {
1707  SCIPerrorMessage("cannot create file <%s> for writing\n", finalfilename);
1708  SCIPprintSysError(finalfilename);
1709  return SCIP_FILECREATEERROR;
1710  }
1711  }
1712 
1713  return SCIP_OKAY;
1714 }
1715 
1716 /** creates initial cuts for SCIP*/
1717 static
1719  SCIP* scip, /**< SCIP data structure */
1720  SCIP_PROBDATA* probdata /**< problem data */
1721  )
1722 {
1723  GRAPH* graph = probdata->graph;
1724  SCIP_Real lpobjval;
1725  const SCIP_Bool mw = (graph->stp_type == STP_MWCSP);
1726  const SCIP_Bool pc = (graph->stp_type == STP_PCSPG);
1727 
1728  assert(STP_MODE_CUT == probdata->mode);
1729  assert(graph->terms - 1 == probdata->realnterms);
1730 
1731  if( probdata->realnterms == 0 )
1732  return SCIP_OKAY;
1733 
1734  if( pc || mw )
1735  {
1736  SCIP_CALL( dualascent_execPcMw(scip, graph, NULL, &lpobjval, TRUE, TRUE, 1) );
1737  }
1738  else if( graph->stp_type != STP_BRMWCSP )
1739  {
1740  const SCIP_Bool doAscendPrune = (graph->stp_type == STP_DCSTP ||
1742  DAPARAMS daparams = { .addcuts = TRUE, .ascendandprune = doAscendPrune, .root = graph->source,
1743  .is_pseudoroot = FALSE, .damaxdeviation = 0.1 };
1744 
1745 #if 0
1746  if( (graph_typeIsSpgLike(graph) || graph_pc_isRootedPcMw(graph)) )
1747  {
1748  int* soledge;
1749  SCIP_Bool success;
1750  SCIP_CALL( SCIPallocBufferArray(scip, &soledge, graph->edges) );
1751 
1753  graph, NULL, NULL, soledge, 32, graph->source, graph->cost, graph->cost, NULL, NULL, &success));
1754  SCIP_CALL( SCIPStpHeurSlackPruneRun(scip, NULL, graph, soledge, &success, FALSE, FALSE) );
1755  SCIP_CALL( solstp_addSolToProb(scip, graph, soledge, &success) );
1756  assert(success);
1757  SCIP_CALL( dualascent_exec(scip, graph, soledge, &daparams, NULL, &lpobjval) );
1758 
1759  SCIPfreeBufferArray(scip, &soledge);
1760  }
1761  else
1762  {
1763  SCIP_CALL( dualascent_exec(scip, graph, NULL, &daparams, NULL, &lpobjval) );
1764  }
1765 #endif
1766  if( graph->stp_type == STP_DCSTP )
1767  {
1768  SCIP_CALL( dualascent_execDegCons(scip, graph, NULL, &daparams, NULL, &lpobjval) );
1769  }
1770  else
1771  {
1772  SCIP_CALL( dualascent_exec(scip, graph, NULL, &daparams, NULL, &lpobjval) );
1773  }
1774  }
1775 
1776  return SCIP_OKAY;
1777 }
1778 
1779 
1780 
1781 /** ratio of remaining edges */
1782 static
1784  SCIP_PROBDATA* probdata, /**< problem data */
1785  const GRAPH* graph /**< the graph */
1786 )
1787 {
1788  SCIP_Real ratio;
1789  assert(graph);
1790  assert(graph->knots >= 1);
1791 
1792  if( graph_pc_isPcMw(graph) )
1793  {
1794  SCIP_Real ratio_nodes;
1795  graph_pc_getReductionRatios(graph, &ratio_nodes, &ratio);
1796  }
1797  else
1798  {
1799  ratio = (SCIP_Real) graph->edges / (SCIP_Real) probdata->norgedges;
1800  }
1801 
1802  assert(GE(ratio, 0.0));
1803  assert(LE(ratio, 1.0));
1804 
1805  return ratio;
1806 }
1807 
1808 
1809 /** helper */
1810 static
1812  SCIP_PROBDATA* probdata /**< problem data */
1813  )
1814 {
1815 #ifndef WITH_UG
1816  GRAPH* const graph = probdata->graph;
1817  const SCIP_Bool tooBig = (graph->edges > CUT_MAXTOTNEDGES)
1818  || ((graph->edges > CUT_MAXNEDGES) && (graph->terms > CUT_MAXNTERMINALS));
1819  const SCIP_Bool tooSmall = (graph->edges < CUT_MINTOTNEDGES);
1820 
1821  if( tooBig || tooSmall )
1822  {
1823  const SCIP_Real redratio = getEdgeReductionRatio(probdata, graph);
1824 
1825  if( redratio < CUT_MINREDUCTION_RATIO )
1826  {
1827  return TRUE;
1828  }
1829  else
1830  {
1831  if( probdata->isSubProb )
1832  {
1833  return TRUE;
1834  }
1835  }
1836  }
1837 
1838 #endif
1839  return FALSE;
1840 }
1841 
1842 /** helper */
1843 static
1845  const GRAPH* g /**< graph data structure */
1846 )
1847 {
1848  const int nterms = g->terms;
1849  int nrounds = nterms / 5;
1850 
1851  if( nrounds < 10 )
1852  nrounds = 10;
1853  else if( nrounds > 50 )
1854  nrounds = 50;
1855  // 20 // 50
1856  return nrounds;
1857 }
1858 
1859 
1860 /** set parameters */
1861 static
1863  SCIP* scip, /**< SCIP data structure */
1864  SCIP_PROBDATA* probdata, /**< problem data */
1865  int symcons, /**< user parameter */
1866  int cyclecons /**< user parameter */
1867  )
1868 {
1869  GRAPH* const graph = probdata->graph;
1870  const SCIP_Bool mw = (graph->stp_type == STP_MWCSP);
1871  const SCIP_Bool pc = (graph->stp_type == STP_PCSPG);
1872 
1873  if( setParamsSepaIsBad(probdata) )
1874  {
1875  const int zerhalf_nrounds = sepaBadGetZeroHalfMaxrounds(graph);
1876  SCIP_CALL(SCIPsetBoolParam(scip, "separating/aggregation/delay", TRUE));
1877  SCIP_CALL(SCIPsetBoolParam(scip, "separating/strongcg/delay", TRUE));
1878  SCIP_CALL(SCIPsetBoolParam(scip, "separating/gomory/delay", TRUE));
1879  SCIP_CALL(SCIPsetIntParam(scip, "separating/zerohalf/maxroundsroot", zerhalf_nrounds));
1880  }
1881  else
1882  {
1883  SCIP_CALL(SCIPsetIntParam(scip, "separating/zerohalf/maxroundsroot", 50)); // default is 20
1884 
1885  // todo tune
1886  SCIP_CALL( SCIPsetRealParam(scip, "separating/minefficacyroot", 0.01) );
1887  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/minorthoroot", 0.4) );
1888  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/minortho", 0.4) );
1889  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/objparalweight", 0.01) );
1890  }
1891 
1892  SCIP_CALL(SCIPsetIntParam(scip, "separating/zerohalf/freq", 3)); // default is 10
1893 
1894  //SCIP_CALL(SCIPsetIntParam(scip, "separating/aggregation/maxroundsroot", 0));
1895  //SCIP_CALL(SCIPsetIntParam(scip, "separating/aggregation/maxrounds", 0));
1896  SCIP_CALL(SCIPsetIntParam(scip, "separating/clique/freq", -1));
1897  SCIP_CALL( SCIPsetCharParam(scip, "lp/resolvealgorithm", 'd') );
1898 
1899  if( graph->stp_type == STP_DHCSTP )
1900  {
1901  SCIP_CALL(SCIPsetIntParam(scip, "constraints/knapsack/propfreq", -1));
1902  SCIP_CALL(SCIPsetIntParam(scip, "constraints/logicor/propfreq", -1));
1903  SCIP_CALL(SCIPsetIntParam(scip, "separating/flowcover/freq", -1));
1904  SCIP_CALL(SCIPsetIntParam(scip, "heuristics/locks/freq", -1));
1905  SCIP_CALL(SCIPsetIntParam(scip, "heuristics/rounding/freq", -1));
1906  }
1907 
1908  if( graph_typeIsSpgLike(graph) || graph_pc_isPcMw(graph) )
1909  {
1910  SCIP_CALL(SCIPsetIntParam(scip, "heuristics/rounding/freq", -1));
1911  SCIP_CALL(SCIPsetIntParam(scip, "heuristics/simplerounding/freq", -1));
1912  }
1913 
1914  probdata->usesymcons = FALSE;
1915  probdata->usecyclecons = FALSE;
1916 
1917  if( pc || mw )
1918  {
1919  SCIP_CALL(SCIPsetIntParam(scip, "constraints/logicor/presoltiming", 4));
1920 
1921  if( cyclecons == STP_CONS_ALWAYS || (cyclecons == STP_CONS_AUTOMATIC && graph->edges <= CYC_CONS_LIMIT) )
1922  probdata->usecyclecons = TRUE;
1923 
1924  if( symcons == STP_CONS_ALWAYS || (symcons == STP_CONS_AUTOMATIC && graph->terms <= SYM_CONS_LIMIT) )
1925  probdata->usesymcons = TRUE;
1926 
1927  if( probdata->usesymcons )
1928  SCIPdebugMessage("USE SYM CONS: %d \n", graph->terms);
1929  else
1930  SCIPdebugMessage("NO SYM CONS: \n");
1931 
1932  SCIP_CALL(SCIPsetIntParam(scip, "heuristics/trivial/freq", -1));
1933  }
1934 
1935  if( graph->knots > 1 )
1936  {
1937  assert(graph->terms >= 1);
1938 
1939  probdata->graphHasVanished = FALSE;
1940  }
1941  else
1942  {
1943  assert(1 == graph->knots);
1944  assert(1 == graph->terms);
1945  assert(0 == graph->edges);
1946 
1947  probdata->graphHasVanished = TRUE;
1948  }
1949 
1950  return SCIP_OKAY;
1951 }
1952 
1953 /**@} */
1954 
1955 /**@name Callback methods of problem data
1956  *
1957  * @{
1958  */
1959 
1960 /** copies user data of source SCIP for the target SCIP */
1961 static
1963 {
1964  GRAPH* graphcopy;
1965 
1966  SCIPdebugMessage("########################## probcopy ###########################\n");
1967 
1968  SCIP_CALL( graph_copy(scip, sourcedata->graph, &graphcopy) );
1969  SCIP_CALL( graph_path_init(scip, graphcopy) );
1970 
1971  if( sourcedata->mode == STP_MODE_CUT )
1972  SCIP_CALL( graph_mincut_init(scip, graphcopy) );
1973 
1974  SCIP_CALL( probdataCreate(scip, targetdata, graphcopy) );
1975 
1976 #ifdef WITH_UG
1977  {
1978  GRAPH* orggraphcopy;
1979  SCIP_CALL( graph_copy(scip, sourcedata->orggraph, &orggraphcopy) );
1980  SCIP_CALL( graph_path_init(scip, orggraphcopy) );
1981  if( orggraphcopy->knots > 1 )
1982  {
1983  SCIP_CALL( graph_initPseudoAncestors(scip, orggraphcopy) );
1984  SCIP_CALL( graph_copyPseudoAncestors(scip, sourcedata->orggraph, orggraphcopy) );
1985  }
1986  (*targetdata)->orggraph = orggraphcopy;
1987  }
1988 #endif
1989  (*targetdata)->minelims = sourcedata->minelims;
1990  (*targetdata)->presolub = sourcedata->presolub;
1991  (*targetdata)->objIsInt = sourcedata->objIsInt;
1992  (*targetdata)->isSubProb = sourcedata->isSubProb;
1993  (*targetdata)->offset = sourcedata->offset;
1994  (*targetdata)->norgedges = sourcedata->norgedges;
1995  (*targetdata)->mode = sourcedata->mode;
1996  (*targetdata)->bigt = sourcedata->bigt;
1997  (*targetdata)->nlayers = sourcedata->nlayers;
1998  (*targetdata)->nedges = sourcedata->nedges;
1999  (*targetdata)->nnodes = sourcedata->nnodes;
2000  (*targetdata)->nterms = sourcedata->nterms;
2001  (*targetdata)->nnonterms = sourcedata->nnonterms;
2002  (*targetdata)->realnterms = sourcedata->realnterms;
2003  (*targetdata)->emitgraph = sourcedata->emitgraph;
2004  (*targetdata)->usesymcons = sourcedata->usesymcons;
2005  (*targetdata)->graphHasVanished = sourcedata->graphHasVanished;
2006  (*targetdata)->usecyclecons = sourcedata->usecyclecons;
2007  (*targetdata)->nvars = sourcedata->nvars;
2008  (*targetdata)->copy = TRUE;
2009 #if USEOFFSETVAR
2010  (*targetdata)->offsetvar = NULL;
2011 
2012  if( sourcedata->offsetvar != NULL && SCIPvarIsActive(sourcedata->offsetvar) )
2013  {
2014  SCIP_Bool success;
2015 
2016  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->offsetvar, &((*targetdata)->offsetvar), varmap, consmap, global, &success) );
2017  assert(success);
2018 
2019  SCIP_CALL( SCIPcaptureVar(scip, (*targetdata)->offsetvar) );
2020  }
2021 #endif
2022  if( sourcedata->nedges > 0 )
2023  {
2024  SCIP_Bool success;
2025  int v;
2026  int c;
2027 
2028  /* transform variables */
2029  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->xval, sourcedata->nvars) );
2030  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->edgevars, sourcedata->nvars) );
2031 
2032  for( v = 0; v < sourcedata->nvars; v++ )
2033  {
2034  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->edgevars[v], &((*targetdata)->edgevars[v]), varmap, consmap, global, &success) );
2035  assert(success);
2036 
2037  SCIP_CALL( SCIPcaptureVar(scip, (*targetdata)->edgevars[v]) );
2038  }
2039 
2040  /* cut mode */
2041  if( sourcedata->mode == STP_MODE_CUT )
2042  {
2043  (*targetdata)->edgecons = NULL;
2044  (*targetdata)->pathcons = NULL;
2045  if( sourcedata->stp_type == STP_DCSTP )
2046  {
2047  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->degcons, sourcedata->nnodes));
2048  for( c = sourcedata->nnodes - 1; c >= 0; --c )
2049  {
2050  SCIP_CALL(
2051  SCIPgetConsCopy(sourcescip, scip, sourcedata->degcons[c], &((*targetdata)->degcons[c]), SCIPconsGetHdlr(sourcedata->degcons[c]),
2052  varmap, consmap, SCIPconsGetName(sourcedata->degcons[c]), SCIPconsIsInitial(sourcedata->degcons[c]),
2053  SCIPconsIsSeparated(sourcedata->degcons[c]), SCIPconsIsEnforced(sourcedata->degcons[c]),
2054  SCIPconsIsChecked(sourcedata->degcons[c]), SCIPconsIsPropagated(sourcedata->degcons[c]),
2055  SCIPconsIsLocal(sourcedata->degcons[c]), SCIPconsIsModifiable(sourcedata->degcons[c]),
2056  SCIPconsIsDynamic(sourcedata->degcons[c]), SCIPconsIsRemovable(sourcedata->degcons[c]),
2057  SCIPconsIsStickingAtNode(sourcedata->degcons[c]), global, &success));
2058  assert(success);
2059 
2060  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->degcons[c]));
2061  }
2062  }
2063 
2064  if( sourcedata->stp_type == STP_PCSPG || sourcedata->stp_type == STP_RPCSPG || sourcedata->stp_type == STP_MWCSP )
2065  {
2066 #if FLOWB
2067  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->flowbcons, sourcedata->nnonterms) );
2068  for( c = sourcedata->nnonterms - 1; c >= 0; --c )
2069  {
2070  SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->flowbcons[c], &((*targetdata)->flowbcons[c]),
2071  SCIPconsGetHdlr(sourcedata->flowbcons[c]), varmap, consmap,
2072  SCIPconsGetName(sourcedata->flowbcons[c]),
2073  SCIPconsIsInitial(sourcedata->flowbcons[c]),
2074  SCIPconsIsSeparated(sourcedata->flowbcons[c]),
2075  SCIPconsIsEnforced(sourcedata->flowbcons[c]),
2076  SCIPconsIsChecked(sourcedata->flowbcons[c]),
2077  SCIPconsIsPropagated(sourcedata->flowbcons[c]),
2078  SCIPconsIsLocal(sourcedata->flowbcons[c]),
2079  SCIPconsIsModifiable(sourcedata->flowbcons[c]),
2080  SCIPconsIsDynamic(sourcedata->flowbcons[c]),
2081  SCIPconsIsRemovable(sourcedata->flowbcons[c]),
2082  SCIPconsIsStickingAtNode(sourcedata->flowbcons[c]),
2083  global, &success) );
2084  assert(success);
2085 
2086  SCIP_CALL( SCIPcaptureCons(scip, (*targetdata)->flowbcons[c]) );
2087  }
2088 #endif
2089 
2090  if( sourcedata->usecyclecons && sourcedata->stp_type == STP_PCSPG )
2091  {
2092  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->prizecyclecons, sourcedata->nedges));
2093  for( c = sourcedata->nedges - 1; c >= 0; --c )
2094  {
2095  SCIP_CALL(
2096  SCIPgetConsCopy(sourcescip, scip, sourcedata->prizecyclecons[c], &((*targetdata)->prizecyclecons[c]),
2097  SCIPconsGetHdlr(sourcedata->prizecyclecons[c]), varmap, consmap, SCIPconsGetName(sourcedata->prizecyclecons[c]),
2098  SCIPconsIsInitial(sourcedata->prizecyclecons[c]), SCIPconsIsSeparated(sourcedata->prizecyclecons[c]),
2099  SCIPconsIsEnforced(sourcedata->prizecyclecons[c]), SCIPconsIsChecked(sourcedata->prizecyclecons[c]),
2100  SCIPconsIsPropagated(sourcedata->prizecyclecons[c]), SCIPconsIsLocal(sourcedata->prizecyclecons[c]),
2101  SCIPconsIsModifiable(sourcedata->prizecyclecons[c]), SCIPconsIsDynamic(sourcedata->prizecyclecons[c]),
2102  SCIPconsIsRemovable(sourcedata->prizecyclecons[c]), SCIPconsIsStickingAtNode(sourcedata->prizecyclecons[c]), global,
2103  &success));
2104  assert(success);
2105 
2106  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->prizecyclecons[c]));
2107  }
2108  }
2109 
2110  if( sourcedata->usesymcons && sourcedata->stp_type != STP_RPCSPG )
2111  {
2112 #ifdef STP_AGG_SYM
2113  v = sourcedata->realnterms - 1;
2114 #else
2115  v = ((sourcedata->realnterms - 1) * sourcedata->realnterms ) / 2;
2116 #endif
2117  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->prizesymcons, v));
2118  for( c = v - 1; c >= 0; --c )
2119  {
2120  SCIP_CALL(
2121  SCIPgetConsCopy(sourcescip, scip, sourcedata->prizesymcons[c], &((*targetdata)->prizesymcons[c]),
2122  SCIPconsGetHdlr(sourcedata->prizesymcons[c]), varmap, consmap, SCIPconsGetName(sourcedata->prizesymcons[c]),
2123  SCIPconsIsInitial(sourcedata->prizesymcons[c]), SCIPconsIsSeparated(sourcedata->prizesymcons[c]),
2124  SCIPconsIsEnforced(sourcedata->prizesymcons[c]), SCIPconsIsChecked(sourcedata->prizesymcons[c]),
2125  SCIPconsIsPropagated(sourcedata->prizesymcons[c]), SCIPconsIsLocal(sourcedata->prizesymcons[c]),
2126  SCIPconsIsModifiable(sourcedata->prizesymcons[c]), SCIPconsIsDynamic(sourcedata->prizesymcons[c]),
2127  SCIPconsIsRemovable(sourcedata->prizesymcons[c]), SCIPconsIsStickingAtNode(sourcedata->prizesymcons[c]), global,
2128  &success));
2129  assert(success);
2130 
2131  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->prizesymcons[c]));
2132  }
2133  }
2134 
2135  if( sourcedata->stp_type != STP_RPCSPG )
2136  {
2137  SCIP_CALL(
2138  SCIPgetConsCopy(sourcescip, scip, sourcedata->prizecons, &((*targetdata)->prizecons), SCIPconsGetHdlr(sourcedata->prizecons),
2139  varmap, consmap, SCIPconsGetName(sourcedata->prizecons), SCIPconsIsInitial(sourcedata->prizecons),
2140  SCIPconsIsSeparated(sourcedata->prizecons), SCIPconsIsEnforced(sourcedata->prizecons),
2141  SCIPconsIsChecked(sourcedata->prizecons), SCIPconsIsPropagated(sourcedata->prizecons),
2142  SCIPconsIsLocal(sourcedata->prizecons), SCIPconsIsModifiable(sourcedata->prizecons),
2143  SCIPconsIsDynamic(sourcedata->prizecons), SCIPconsIsRemovable(sourcedata->prizecons),
2144  SCIPconsIsStickingAtNode(sourcedata->prizecons), global, &success));
2145  assert(success);
2146 
2147  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->prizecons));
2148  }
2149  }
2150 
2151  if( sourcedata->stp_type == STP_DHCSTP )
2152  {
2153  SCIP_CALL(
2154  SCIPgetConsCopy(sourcescip, scip, sourcedata->hopcons, &((*targetdata)->hopcons), SCIPconsGetHdlr(sourcedata->hopcons),
2155  varmap, consmap, SCIPconsGetName(sourcedata->hopcons), SCIPconsIsInitial(sourcedata->hopcons),
2156  SCIPconsIsSeparated(sourcedata->hopcons), SCIPconsIsEnforced(sourcedata->hopcons),
2157  SCIPconsIsChecked(sourcedata->hopcons), SCIPconsIsPropagated(sourcedata->hopcons),
2158  SCIPconsIsLocal(sourcedata->hopcons), SCIPconsIsModifiable(sourcedata->hopcons),
2159  SCIPconsIsDynamic(sourcedata->hopcons), SCIPconsIsRemovable(sourcedata->hopcons),
2160  SCIPconsIsStickingAtNode(sourcedata->hopcons), global, &success));
2161  assert(success);
2162 
2163  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->hopcons));
2164  }
2165 
2166  if( sourcedata->stp_type == STP_BRMWCSP )
2167  {
2168  SCIP_CALL(
2169  SCIPgetConsCopy(sourcescip, scip, sourcedata->budgetcons, &((*targetdata)->budgetcons), SCIPconsGetHdlr(sourcedata->budgetcons),
2170  varmap, consmap, SCIPconsGetName(sourcedata->budgetcons), SCIPconsIsInitial(sourcedata->budgetcons),
2171  SCIPconsIsSeparated(sourcedata->budgetcons), SCIPconsIsEnforced(sourcedata->budgetcons),
2172  SCIPconsIsChecked(sourcedata->budgetcons), SCIPconsIsPropagated(sourcedata->budgetcons),
2173  SCIPconsIsLocal(sourcedata->budgetcons), SCIPconsIsModifiable(sourcedata->budgetcons),
2174  SCIPconsIsDynamic(sourcedata->budgetcons), SCIPconsIsRemovable(sourcedata->budgetcons),
2175  SCIPconsIsStickingAtNode(sourcedata->budgetcons), global, &success));
2176  assert(success);
2177 
2178  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->budgetcons));
2179  }
2180 
2181  }
2182  /* Price or Flow mode */
2183  else
2184  {
2185  /* transform edge constraints */
2186  if( sourcedata->bigt )
2187  {
2188  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->nedges));
2189 
2190  for( c = sourcedata->nedges - 1; c >= 0; --c )
2191  {
2192  SCIP_CALL(
2193  SCIPgetConsCopy(sourcescip, scip, sourcedata->edgecons[c], &((*targetdata)->edgecons[c]),
2194  SCIPconsGetHdlr(sourcedata->edgecons[c]), varmap, consmap, SCIPconsGetName(sourcedata->edgecons[c]),
2195  SCIPconsIsInitial(sourcedata->edgecons[c]), SCIPconsIsSeparated(sourcedata->edgecons[c]),
2196  SCIPconsIsEnforced(sourcedata->edgecons[c]), SCIPconsIsChecked(sourcedata->edgecons[c]),
2197  SCIPconsIsPropagated(sourcedata->edgecons[c]), SCIPconsIsLocal(sourcedata->edgecons[c]),
2198  SCIPconsIsModifiable(sourcedata->edgecons[c]), SCIPconsIsDynamic(sourcedata->edgecons[c]),
2199  SCIPconsIsRemovable(sourcedata->edgecons[c]), SCIPconsIsStickingAtNode(sourcedata->edgecons[c]), global, &success));
2200  assert(success);
2201 
2202  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->edgecons[c]));
2203  }
2204  }
2205  else
2206  {
2207  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->realnterms * sourcedata->nedges));
2208  for( c = sourcedata->realnterms * sourcedata->nedges - 1; c >= 0; --c )
2209  {
2210  SCIP_CALL(
2211  SCIPgetConsCopy(sourcescip, scip, sourcedata->edgecons[c], &((*targetdata)->edgecons[c]),
2212  SCIPconsGetHdlr(sourcedata->edgecons[c]), varmap, consmap, SCIPconsGetName(sourcedata->edgecons[c]),
2213  SCIPconsIsInitial(sourcedata->edgecons[c]), SCIPconsIsSeparated(sourcedata->edgecons[c]),
2214  SCIPconsIsEnforced(sourcedata->edgecons[c]), SCIPconsIsChecked(sourcedata->edgecons[c]),
2215  SCIPconsIsPropagated(sourcedata->edgecons[c]), SCIPconsIsLocal(sourcedata->edgecons[c]),
2216  SCIPconsIsModifiable(sourcedata->edgecons[c]), SCIPconsIsDynamic(sourcedata->edgecons[c]),
2217  SCIPconsIsRemovable(sourcedata->edgecons[c]), SCIPconsIsStickingAtNode(sourcedata->edgecons[c]), global, &success));
2218  assert(success);
2219 
2220  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->edgecons[c]));
2221  }
2222  }
2223 
2224  /* transform constraints */
2225  if( sourcedata->mode == STP_MODE_PRICE )
2226  {
2227  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms));
2228  for( c = sourcedata->realnterms - 1; c >= 0; --c )
2229  {
2230  SCIP_CALL(
2231  SCIPgetConsCopy(sourcescip, scip, sourcedata->pathcons[c], &((*targetdata)->pathcons[c]),
2232  SCIPconsGetHdlr(sourcedata->pathcons[c]), varmap, consmap, SCIPconsGetName(sourcedata->pathcons[c]),
2233  SCIPconsIsInitial(sourcedata->pathcons[c]), SCIPconsIsSeparated(sourcedata->pathcons[c]),
2234  SCIPconsIsEnforced(sourcedata->pathcons[c]), SCIPconsIsChecked(sourcedata->pathcons[c]),
2235  SCIPconsIsPropagated(sourcedata->pathcons[c]), SCIPconsIsLocal(sourcedata->pathcons[c]),
2236  SCIPconsIsModifiable(sourcedata->pathcons[c]), SCIPconsIsDynamic(sourcedata->pathcons[c]),
2237  SCIPconsIsRemovable(sourcedata->pathcons[c]), SCIPconsIsStickingAtNode(sourcedata->pathcons[c]), global, &success));
2238  assert(success);
2239 
2240  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->pathcons[c]));
2241  }
2242  }
2243  /* transform constraints and variables */
2244  else if( sourcedata->mode == STP_MODE_FLOW )
2245  {
2246  if( sourcedata->bigt )
2247  {
2248  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->nedges));
2249  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, (sourcedata->nnodes - 1)));
2250  for( c = sourcedata->nnodes - 2; c >= 0; --c )
2251  {
2252  SCIP_CALL(
2253  SCIPgetConsCopy(sourcescip, scip, sourcedata->pathcons[c], &((*targetdata)->pathcons[c]),
2254  SCIPconsGetHdlr(sourcedata->pathcons[c]), varmap, consmap, SCIPconsGetName(sourcedata->pathcons[c]),
2255  SCIPconsIsInitial(sourcedata->pathcons[c]), SCIPconsIsSeparated(sourcedata->pathcons[c]),
2256  SCIPconsIsEnforced(sourcedata->pathcons[c]), SCIPconsIsChecked(sourcedata->pathcons[c]),
2257  SCIPconsIsPropagated(sourcedata->pathcons[c]), SCIPconsIsLocal(sourcedata->pathcons[c]),
2258  SCIPconsIsModifiable(sourcedata->pathcons[c]), SCIPconsIsDynamic(sourcedata->pathcons[c]),
2259  SCIPconsIsRemovable(sourcedata->pathcons[c]), SCIPconsIsStickingAtNode(sourcedata->pathcons[c]), global, &success));
2260  assert(success);
2261 
2262  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->pathcons[c]));
2263  }
2264 
2265  for( v = (*targetdata)->nedges - 1; v >= 0; --v )
2266  {
2267  SCIP_CALL(
2268  SCIPgetVarCopy(sourcescip, scip, sourcedata->flowvars[v], &((*targetdata)->flowvars[v]), varmap, consmap, global, &success));
2269  assert(success);
2270 
2271  SCIP_CALL(SCIPcaptureVar(scip, (*targetdata)->flowvars[v]));
2272  }
2273  }
2274  else
2275  {
2276  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->realnterms * sourcedata->nedges));
2277  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms * (sourcedata->nnodes - 1)));
2278  for( c = sourcedata->realnterms * (sourcedata->nnodes - 1) - 1; c >= 0; --c )
2279  {
2280  SCIP_CALL(
2281  SCIPgetConsCopy(sourcescip, scip, sourcedata->pathcons[c], &((*targetdata)->pathcons[c]),
2282  SCIPconsGetHdlr(sourcedata->pathcons[c]), varmap, consmap, SCIPconsGetName(sourcedata->pathcons[c]),
2283  SCIPconsIsInitial(sourcedata->pathcons[c]), SCIPconsIsSeparated(sourcedata->pathcons[c]),
2284  SCIPconsIsEnforced(sourcedata->pathcons[c]), SCIPconsIsChecked(sourcedata->pathcons[c]),
2285  SCIPconsIsPropagated(sourcedata->pathcons[c]), SCIPconsIsLocal(sourcedata->pathcons[c]),
2286  SCIPconsIsModifiable(sourcedata->pathcons[c]), SCIPconsIsDynamic(sourcedata->pathcons[c]),
2287  SCIPconsIsRemovable(sourcedata->pathcons[c]), SCIPconsIsStickingAtNode(sourcedata->pathcons[c]), global, &success));
2288  assert(success);
2289 
2290  SCIP_CALL(SCIPcaptureCons(scip, (*targetdata)->pathcons[c]));
2291  }
2292 
2293  for( v = sourcedata->nedges * sourcedata->realnterms - 1; v >= 0; --v )
2294  {
2295  SCIP_CALL(
2296  SCIPgetVarCopy(sourcescip, scip, sourcedata->flowvars[v], &((*targetdata)->flowvars[v]), varmap, consmap, global, &success));
2297  assert(success);
2298 
2299  SCIP_CALL(SCIPcaptureVar(scip, (*targetdata)->flowvars[v]));
2300  }
2301  }
2302  }
2303  }
2304 
2305  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->realterms, sourcedata->realnterms) );
2306  BMScopyMemoryArray((*targetdata)->realterms, sourcedata->realterms, sourcedata->realnterms);
2307 
2308  if( sourcedata->pctermsorder != NULL )
2309  {
2310  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->pctermsorder, sourcedata->nnodes) );
2311  BMScopyMemoryArray((*targetdata)->pctermsorder, sourcedata->pctermsorder, sourcedata->nnodes);
2312  }
2313  else
2314  (*targetdata)->pctermsorder = NULL;
2315  }
2316  else
2317  {
2318  (*targetdata)->edgevars = NULL;
2319  (*targetdata)->xval = NULL;
2320  (*targetdata)->realterms = NULL;
2321  (*targetdata)->pctermsorder = NULL;
2322  (*targetdata)->edgecons = NULL;
2323  (*targetdata)->pathcons = NULL;
2324  (*targetdata)->flowvars = NULL;
2325  }
2326 
2327  *result = SCIP_SUCCESS;
2328 
2329  return SCIP_OKAY;
2330 }
2331 
2332 
2333 /** frees user data of original problem (called when the original problem is freed) */
2334 static
2335 SCIP_DECL_PROBDELORIG(probdelorigStp)
2336 {
2337  SCIPdebugMessage("probdelorigStp \n");
2338 
2339  SCIPdebugMessage("free original problem data\n");
2340 
2341  if( !(*probdata)->graphHasVanished )
2342  {
2343  if ( (*probdata)->mode == STP_MODE_CUT )
2344  graph_mincut_exit(scip, (*probdata)->graph);
2345 
2346  graph_path_exit(scip, (*probdata)->graph);
2347  }
2348 
2349  graph_free(scip, &((*probdata)->graph), TRUE);
2350 
2351 #ifdef WITH_UG
2352  if( (*probdata)->orggraph != NULL )
2353  {
2354  graph_path_exit(scip, (*probdata)->orggraph);
2355  graph_free(scip, &((*probdata)->orggraph), TRUE);
2356  }
2357 #endif
2358  /* free the (original) probdata */
2359  SCIP_CALL( probdataFree(scip, probdata) );
2360 
2361  return SCIP_OKAY;
2362 }
2363 
2364 /** creates user data of transformed problem by transforming the original user problem data
2365  * (called after problem was transformed) */
2366 static
2367 SCIP_DECL_PROBTRANS(probtransStp)
2368 {
2369  SCIP_Real timelimit;
2370  SCIP_Bool update;
2371 
2372  SCIPdebugMessage("probtransStp \n");
2373 
2374  SCIP_CALL( SCIPgetBoolParam(scip, "stp/countpresoltime", &update) );
2375 
2376  /* adjust time limit to take into account reading time */
2377  if( update )
2378  {
2379  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
2380  timelimit -= SCIPgetReadingTime(scip);
2381  timelimit = MAX(0.0,timelimit);
2382  SCIP_CALL( SCIPsetRealParam(scip, "limits/time", timelimit) );
2383  }
2384 
2385  /* create transform probdata */
2386  SCIP_CALL( probdataCreate(scip, targetdata, sourcedata->graph) );
2387 #ifdef WITH_UG
2388  (*targetdata)->orggraph = sourcedata->orggraph;
2389 #endif
2390  (*targetdata)->nlayers = sourcedata->nlayers;
2391  (*targetdata)->nedges = sourcedata->nedges;
2392  (*targetdata)->nnodes = sourcedata->nnodes;
2393  (*targetdata)->nterms = sourcedata->nterms;
2394  (*targetdata)->realnterms = sourcedata->realnterms;
2395  (*targetdata)->nnonterms = sourcedata->nnonterms;
2396  (*targetdata)->emitgraph = sourcedata->emitgraph;
2397  (*targetdata)->usesymcons = sourcedata->usesymcons;
2398  (*targetdata)->graphHasVanished = sourcedata->graphHasVanished;
2399  (*targetdata)->usecyclecons = sourcedata->usecyclecons;
2400  (*targetdata)->nvars = sourcedata->nvars;
2401  (*targetdata)->mode = sourcedata->mode;
2402  (*targetdata)->offset = sourcedata->offset;
2403  (*targetdata)->presolub = sourcedata->presolub;
2404  (*targetdata)->objIsInt = sourcedata->objIsInt;
2405  (*targetdata)->isSubProb = sourcedata->isSubProb;
2406  (*targetdata)->norgedges = sourcedata->norgedges;
2407  (*targetdata)->minelims = sourcedata->minelims;
2408  (*targetdata)->bigt = sourcedata->bigt;
2409  (*targetdata)->logfile = sourcedata->logfile;
2410  (*targetdata)->origlogfile = &(sourcedata->logfile);
2411  (*targetdata)->intlogfile = sourcedata->intlogfile;
2412  (*targetdata)->origintlogfile = &(sourcedata->intlogfile);
2413 #if USEOFFSETVAR
2414  if( sourcedata->offsetvar != NULL )
2415  {
2416  SCIP_CALL( SCIPtransformVar(scip, sourcedata->offsetvar, &(*targetdata)->offsetvar) );
2417  }
2418  else
2419  (*targetdata)->offsetvar = NULL;
2420 #endif
2421  if( sourcedata->nedges > 0 )
2422  {
2423  int i;
2424 
2425  /* transform variables */
2426  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->xval, sourcedata->nvars) );
2427  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->edgevars, sourcedata->nvars) );
2428  SCIP_CALL( SCIPtransformVars(scip, sourcedata->nvars, sourcedata->edgevars, (*targetdata)->edgevars) );
2429 
2430  /* cut mode */
2431  if( sourcedata->mode == STP_MODE_CUT )
2432  {
2433  (*targetdata)->edgecons = NULL;
2434  (*targetdata)->pathcons = NULL;
2435 
2436  if( sourcedata->stp_type == STP_DCSTP )
2437  {
2438  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->degcons, sourcedata->nnodes) );
2439  SCIP_CALL( SCIPtransformConss(scip, sourcedata->nnodes, sourcedata->degcons, (*targetdata)->degcons) );
2440  }
2441 
2442 #if FLOWB
2443  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->flowbcons, sourcedata->nnonterms) );
2444  SCIP_CALL( SCIPtransformConss(scip, sourcedata->nnonterms, sourcedata->flowbcons, (*targetdata)->flowbcons) );
2445 #endif
2446 
2447  if( sourcedata->stp_type == STP_PCSPG || sourcedata->stp_type == STP_MWCSP )
2448  {
2449  if( sourcedata->usecyclecons && sourcedata->stp_type == STP_PCSPG )
2450  {
2451  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->prizecyclecons, sourcedata->nedges) );
2452  SCIP_CALL( SCIPtransformConss(scip, sourcedata->nedges, sourcedata->prizecyclecons, (*targetdata)->prizecyclecons) );
2453  }
2454 
2455  if( sourcedata->usesymcons )
2456  {
2457 #ifdef STP_AGG_SYM
2458  i = sourcedata->realnterms - 1;
2459 #else
2460  i = ((sourcedata->realnterms - 1) * (sourcedata->realnterms)) / 2;
2461 #endif
2462  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->prizesymcons, i) );
2463  SCIP_CALL( SCIPtransformConss(scip, i, sourcedata->prizesymcons, (*targetdata)->prizesymcons) );
2464  }
2465  SCIP_CALL( SCIPtransformCons(scip, sourcedata->prizecons, &(*targetdata)->prizecons) );
2466  }
2467 
2468  if( sourcedata->stp_type == STP_DHCSTP )
2469  SCIP_CALL( SCIPtransformCons(scip, sourcedata->hopcons, &(*targetdata)->hopcons) );
2470 
2471  if( sourcedata->stp_type == STP_BRMWCSP )
2472  SCIP_CALL( SCIPtransformCons(scip, sourcedata->budgetcons, &(*targetdata)->budgetcons) );
2473  }
2474  /* Price or Flow mode */
2475  else
2476  {
2477  /* transform edge constraints */
2478  if( sourcedata->bigt )
2479  {
2480  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->nedges));
2481  SCIP_CALL(SCIPtransformConss(scip, sourcedata->nedges, sourcedata->edgecons, (*targetdata)->edgecons));
2482  }
2483  else
2484  {
2485  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->realnterms * sourcedata->nedges));
2486  SCIP_CALL(SCIPtransformConss(scip, sourcedata->realnterms * sourcedata->nedges, sourcedata->edgecons, (*targetdata)->edgecons));
2487  }
2488 
2489  /* transform constraints */
2490  if( sourcedata->mode == STP_MODE_PRICE )
2491  {
2492  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms));
2493  SCIP_CALL(SCIPtransformConss(scip, sourcedata->realnterms, sourcedata->pathcons, (*targetdata)->pathcons));
2494  }
2495  /* transform constraints and variables*/
2496  else if( sourcedata->mode == STP_MODE_FLOW )
2497  {
2498  if( sourcedata->bigt )
2499  {
2500  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->nedges));
2501  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, (sourcedata->nnodes - 1)));
2502  SCIP_CALL(SCIPtransformConss(scip, (sourcedata->nnodes - 1), sourcedata->pathcons, (*targetdata)->pathcons));
2503  SCIP_CALL(SCIPtransformVars(scip, sourcedata->nedges, sourcedata->flowvars, (*targetdata)->flowvars));
2504  }
2505  else
2506  {
2507  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->realnterms * sourcedata->nedges));
2508  SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms * (sourcedata->nnodes - 1)));
2509  SCIP_CALL(SCIPtransformConss(scip, sourcedata->realnterms * (sourcedata->nnodes - 1), sourcedata->pathcons, (*targetdata)->pathcons));
2510  SCIP_CALL(SCIPtransformVars(scip, sourcedata->nedges * sourcedata->realnterms, sourcedata->flowvars, (*targetdata)->flowvars));
2511  }
2512  }
2513  }
2514  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->realterms, sourcedata->realnterms) );
2515  BMScopyMemoryArray((*targetdata)->realterms, sourcedata->realterms, sourcedata->realnterms);
2516 
2517  if( sourcedata->pctermsorder != NULL )
2518  {
2519  SCIP_CALL( SCIPallocMemoryArray(scip, &(*targetdata)->pctermsorder, sourcedata->nnodes) );
2520  BMScopyMemoryArray((*targetdata)->pctermsorder, sourcedata->pctermsorder, sourcedata->nnodes);
2521  }
2522  else
2523  (*targetdata)->pctermsorder = NULL;
2524  }
2525  else
2526  {
2527  (*targetdata)->edgevars = NULL;
2528  (*targetdata)->xval = NULL;
2529  (*targetdata)->realterms = NULL;
2530  (*targetdata)->pctermsorder = NULL;
2531  (*targetdata)->edgecons = NULL;
2532  (*targetdata)->pathcons = NULL;
2533  (*targetdata)->flowvars = NULL;
2534  }
2535 
2536  return SCIP_OKAY;
2537 }
2538 
2539 static
2540 SCIP_DECL_PROBINITSOL(probinitsolStp)
2541 { /*lint --e{715}*/
2542  assert(scip != NULL);
2543  assert(probdata != NULL);
2544 
2545  return SCIP_OKAY;
2546 }
2547 
2548 static
2549 SCIP_DECL_PROBEXITSOL(probexitsolStp)
2550 { /*lint --e{715}*/
2551  assert(scip != NULL);
2552  assert(probdata != NULL);
2553 
2554  if( probdata->logfile != NULL )
2555  {
2556  int success;
2557  SCIP_Real factor = 1.0;
2558 
2559 #ifdef WITH_UG
2560  if( getUgRank() != 0 )
2561  return SCIP_ERROR;
2562 #endif
2563 
2564  if( probdata->stp_type == STP_MWCSP || probdata->stp_type == STP_RMWCSP || probdata->stp_type == STP_BRMWCSP )
2565  factor = -1.0;
2566 
2567  SCIPprobdataWriteLogLine(scip, "End\n");
2568  SCIPprobdataWriteLogLine(scip, "\n");
2569  SCIPprobdataWriteLogLine(scip, "SECTION Run\n");
2570  if( probdata->ug )
2571  {
2572  SCIPprobdataWriteLogLine(scip, "Threads %d\n", probdata->nSolvers);
2573  SCIPprobdataWriteLogLine(scip, "Time %.1f\n", SCIPgetTotalTime(scip));
2574  }
2575  else
2576  {
2577  SCIPprobdataWriteLogLine(scip, "Threads 1\n");
2578  SCIPprobdataWriteLogLine(scip, "Time %.1f\n", SCIPgetTotalTime(scip));
2579  }
2580  SCIPprobdataWriteLogLine(scip, "Primal %16.9f\n", factor * SCIPgetPrimalbound(scip));
2581  SCIPprobdataWriteLogLine(scip, "End\n");
2582 
2583  if( SCIPgetNSols(scip) > 0 )
2584  {
2585  SCIPprobdataWriteLogLine(scip, "\n");
2586  SCIPprobdataWriteLogLine(scip, "SECTION Finalsolution\n");
2587 
2588  SCIP_CALL( SCIPprobdataWriteSolution(scip, probdata->logfile) );
2589  SCIPprobdataWriteLogLine(scip, "End\n");
2590  }
2591 
2592  success = fclose(probdata->logfile);
2593  if( success != 0 )
2594  {
2595  SCIPerrorMessage("An error occurred while closing logfile\n");
2596  return SCIP_FILECREATEERROR;
2597  }
2598 
2599  probdata->logfile = NULL;
2600  *(probdata->origlogfile) = NULL;
2601  }
2602 
2603  if( probdata->intlogfile != NULL )
2604  {
2605  const int success = fclose(probdata->intlogfile);
2606 
2607 #ifdef WITH_UG
2608  if( getUgRank() != 0 )
2609  return SCIP_ERROR;
2610 #endif
2611 
2612  if( success != 0 )
2613  {
2614  SCIPerrorMessage("An error occurred while closing intlogfile\n");
2615  return SCIP_FILECREATEERROR;
2616  }
2617 
2618  probdata->intlogfile = NULL;
2619  *(probdata->origintlogfile) = NULL;
2620  }
2621 
2622  return SCIP_OKAY;
2623 }
2624 
2625 /** frees user data of transformed problem (called when the transformed problem is freed) */
2626 static
2627 SCIP_DECL_PROBDELTRANS(probdeltransStp)
2628 {
2629  SCIPdebugMessage("free transformed problem data\n");
2630 
2631  SCIP_CALL( probdataFree(scip, probdata) );
2632 
2633  return SCIP_OKAY;
2634 }
2635 
2636 /**@} */
2637 
2638 
2639 /**@name Interface methods
2640  *
2641  * @{
2642  */
2643 
2644 /** sets up the problem data */
2646  SCIP* scip /**< SCIP data structure */
2647 )
2648 {
2649  const char* lpsolvername = SCIPlpiGetSolverName();
2650  SCIP_CALL( SCIPsetSubscipsOff(scip, TRUE) );
2651 
2652  /* set STP-specific default parameters */
2653  SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
2654  SCIP_CALL( SCIPsetIntParam(scip, "display/freq", 1) );
2655  SCIP_CALL( SCIPsetIntParam(scip, "limits/maxsol", 400) );
2656  SCIP_CALL( SCIPsetIntParam(scip, "lp/rowagelimit", 10) );
2657  SCIP_CALL( SCIPsetIntParam(scip, "separating/maxroundsroot", -1) );
2658  SCIP_CALL( SCIPsetIntParam(scip, "separating/maxrounds", -1) );
2659  SCIP_CALL( SCIPsetIntParam(scip, "separating/maxstallroundsroot", -1) );
2660  SCIP_CALL( SCIPsetIntParam(scip, "separating/maxcutsroot", 100000) );
2661  SCIP_CALL( SCIPsetIntParam(scip, "separating/maxcuts", 1000) ); // todo tune
2662 
2663  if( strncmp(lpsolvername, "SoPlex", 6) == 0 )
2664  {
2665  printf("\n using SoPlex specific parameters (use of commercial LP solver is recommended!) \n\n");
2666 
2667  SCIP_CALL( SCIPsetRealParam(scip, "separating/minefficacyroot", 0.01) );
2668  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/minorthoroot", 0.8) );
2669  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/minortho", 0.8) );
2670  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/objparalweight", 0.01) );
2671 
2672  }
2673  else
2674  {
2675  SCIP_CALL( SCIPsetRealParam(scip, "separating/minefficacyroot", 0.01) ); // todo tune
2676  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/minorthoroot", 0.4) ); // todo tune > 0.4
2677  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/minortho", 0.4) ); // todo tune > 0.4
2678  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/objparalweight", 0.01) );
2679  }
2680 
2681  SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/intsupportweight", 0.0) );
2682  SCIP_CALL( SCIPsetIntParam(scip, "branching/relpscost/maxproprounds", 0) );
2683  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/alns/freq", -1) );
2684  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/coefdiving/freq", -1) );
2685  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/feaspump/freq", -1) );
2686  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/fracdiving/freq", -1) );
2687  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/farkasdiving/freq", -1) );
2688  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/guideddiving/freq", -1) );
2689  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/linesearchdiving/freq", -1) );
2690  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/nlpdiving/freq", -1) );
2691  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/objpscostdiving/freq", -1) );
2692  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/pscostdiving/freq", -1) );
2693  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/randrounding/freq", -1) );
2694  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/rootsoldiving/freq", -1) );
2695  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/shiftandpropagate/freq", -1) );
2696  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/shifting/freq", -1) );
2697  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/subnlp/freq", -1) );
2698  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/undercover/freq", -1) );
2699  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/veclendiving/freq", -1) );
2700  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/zirounding/freq", -1) );
2701  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/oneopt/freq", -1) );
2702  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/locks/freq", -1) );
2703  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/distributiondiving/freq", -1) );
2704  SCIP_CALL( SCIPsetIntParam(scip, "propagating/probing/maxprerounds", 0) );
2705  SCIP_CALL( SCIPsetIntParam(scip, "propagating/pseudoobj/timingmask", 5) );
2706  SCIP_CALL( SCIPsetIntParam(scip, "propagating/redcost/freq", -1) );
2707  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/freq", -1) );
2708  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/maxprerounds", 0) );
2709  SCIP_CALL( SCIPsetRealParam(scip, "branching/relpscost/maxreliable", 1.0) );
2710 
2711  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) );
2712  SCIP_CALL( SCIPsetBoolParam(scip, "misc/allowstrongdualreds", FALSE) );
2713 
2714  SCIP_CALL( SCIPsetBoolParam(scip, "timing/reading", TRUE) );
2715 
2716 
2717 
2718  // todo test properly; normal dfs?
2719  SCIP_CALL( SCIPsetIntParam(scip, "nodeselection/restartdfs/stdpriority", 400000) );
2720 
2721  SCIP_CALL( SCIPsetCharParam(scip, "estimation/restarts/restartpolicy", 'n') );
2722  //SCIP_CALL( SCIPsetCharParam(scip, "estimation/method", 'o') );
2723 
2724  return SCIP_OKAY;
2725 }
2726 
2727 /** sets up the problem data */
2729  SCIP* scip, /**< SCIP data structure */
2730  const char* filename /**< file name */
2731  )
2732 {
2733  SCIP_RETCODE redcode;
2734  PRESOL presolinfo;
2735  SCIP_PROBDATA* probdata;
2736  GRAPH* graph;
2737  char* intlogfilename;
2738  char* logfilename;
2739  char* probname;
2740  char tmpfilename[SCIP_MAXSTRLEN];
2741 
2742  assert(scip != NULL);
2743 
2744  presolinfo.fixed = 0.0;
2745 
2746  /* read graph from file */
2747  redcode = graph_load(scip, &graph, filename, &presolinfo);
2748 
2749  if( redcode != SCIP_OKAY )
2750  {
2751  SCIPerrorMessage("error while loading graph, aborting \n");
2752  abort();
2753  }
2754 
2755  SCIPdebugMessage("load type :: %d \n\n", graph->stp_type);
2756  SCIPdebugMessage("fixed: %f \n\n", presolinfo.fixed );
2757 
2758  SCIP_CALL( SCIPgetStringParam(scip, "stp/logfile", &logfilename) );
2759  SCIP_CALL( SCIPgetStringParam(scip, "stp/intlogfile", &intlogfilename) );
2760 
2761  /* copy filename */
2762  (void) SCIPsnprintf(tmpfilename, SCIP_MAXSTRLEN, "%s", filename);
2763  SCIPsplitFilename(tmpfilename, NULL, &probname, NULL, NULL);
2764 
2765  /* NOTE: graph will be moved! */
2766  SCIP_CALL( SCIPprobdataCreateFromGraph(scip, presolinfo.fixed, probname, FALSE, graph) );
2767 
2768  probdata = SCIPgetProbData(scip);
2769  assert(probdata && probdata->graph);
2770 
2771  SCIP_CALL( createLogfile(scip, probdata, intlogfilename, logfilename, filename, probname) );
2772  writeCommentSection(scip, probdata->graph, filename);
2773 
2774 #ifdef PRINT_PRESOL
2775  (void)SCIPsnprintf(presolvefilename, SCIP_MAXSTRLEN, "presol/%s-presolve.stp", probname);
2776  SCIP_CALL( SCIPwriteOrigProblem(scip, presolvefilename, NULL, FALSE) );
2777 #endif
2778 
2779  return SCIP_OKAY;
2780 }
2781 
2782 
2783 /** sets up the problem data, given a graph */
2785  SCIP* scip, /**< SCIP data structure */
2786  SCIP_Real offset, /**< offset */
2787  const char* probname, /**< problem name */
2788  SCIP_Bool isSubProb, /**< is this a subproblem? */
2789  GRAPH* graph_move /**< graph; will be moved to probdata and pointer invalidated! */
2790  )
2791 {
2792  REDSOL* redsol = NULL;
2793  SCIP_PROBDATA* probdata;
2794  GRAPH* graph = graph_move;
2795  SCIP_Bool printGraph;
2796  SCIP_Bool useNodeSol = FALSE;
2797  int symcons;
2798  int cyclecons;
2799  int usedacuts;
2800  int usedp;
2801  int compcentral;
2802 
2803  assert(scip && probname && graph);
2804 
2805  /* create problem data */
2806  SCIP_CALL( probdataCreate(scip, &probdata, graph) );
2807  probdata->isSubProb = isSubProb;
2808 
2809  /* get parameters */
2810  SCIP_CALL( SCIPgetIntParam(scip, "stp/compcentral", &compcentral) );
2811  SCIP_CALL( SCIPgetIntParam(scip, "stp/usesymcons", &(symcons)) );
2812  SCIP_CALL( SCIPgetIntParam(scip, "stp/usecyclecons", &(cyclecons)) );
2813  SCIP_CALL( SCIPgetIntParam(scip, "stp/usedacuts", &(usedacuts)) );
2814  SCIP_CALL( SCIPgetIntParam(scip, "stp/usedp", &(usedp)) );
2815  SCIP_CALL( SCIPgetIntParam(scip, "stp/minelims", &(probdata->minelims)) );
2816  SCIP_CALL( SCIPgetBoolParam(scip, "stp/emitgraph", &(probdata->emitgraph)) );
2817  SCIP_CALL( SCIPgetBoolParam(scip, "stp/bigt", &(probdata->bigt)) );
2818  SCIP_CALL( SCIPgetBoolParam(scip, "stp/printGraph", &printGraph) );
2819 
2820  /* create a problem in SCIP and add non-NULL callbacks via setter functions */
2821  SCIP_CALL( SCIPcreateProbBasic(scip, probname) );
2822  SCIP_CALL( SCIPsetProbDelorig(scip, probdelorigStp) );
2823  SCIP_CALL( SCIPsetProbTrans(scip, probtransStp) );
2824  SCIP_CALL( SCIPsetProbDeltrans(scip, probdeltransStp) );
2825  SCIP_CALL( SCIPsetProbInitsol(scip, probinitsolStp) );
2826  SCIP_CALL( SCIPsetProbExitsol(scip, probexitsolStp) );
2827  SCIP_CALL( SCIPsetProbCopy(scip, probcopyStp) );
2828 
2830 
2831  /* set user problem data */
2832  SCIP_CALL( SCIPsetProbData(scip, probdata) );
2833 
2834  setStpSolvingMode(scip, probdata);
2835 
2836  if( printGraph )
2837  {
2838  SCIP_CALL( graph_writeGml(graph, "OriginalGraph.gml", NULL) );
2839  }
2840 
2841  probdata->graph = graph;
2842 
2843  // todo extra method
2844  {
2845  int reduction;
2846  SCIP_CALL( SCIPgetIntParam(scip, "stp/reduction", &reduction) );
2847  useNodeSol = (graph_pc_isPcMw(graph) || graph_typeIsSpgLike(graph)) && (reduction != STP_REDUCTION_NONE);
2848  SCIP_CALL( reduce_solInit(scip, graph, useNodeSol, &redsol) );
2849  }
2850 
2851  /* reduce the graph (and do some house-holding) */
2852  SCIP_CALL( presolveStp(scip, probdata, redsol) );
2853  graph = probdata->graph;
2854 
2855  if( printGraph )
2856  {
2857  SCIP_CALL( graph_writeGml(graph, "ReducedGraph.gml", NULL) );
2858  }
2859 
2860  /* select a root node */
2861  if( graph_typeIsSpgLike(graph) || graph->stp_type == STP_NWSPG )
2862  {
2863  SCIP_CALL( graph_findCentralTerminal(scip, graph, compcentral, &(graph->source)) );
2864  }
2865 
2866 #ifdef WITH_UG
2867  {
2868  GRAPH* newgraph;
2869  graph_copy(scip, graph, &(newgraph));
2870  probdata->orggraph = graph;
2871  graph = newgraph;
2872  probdata->graph = newgraph;
2873  if( newgraph->knots > 1 )
2874  {
2875  SCIP_CALL( graph_initPseudoAncestors(scip, probdata->graph) );
2876  SCIP_CALL( graph_copyPseudoAncestors(scip, probdata->orggraph, probdata->graph) );
2877  }
2878  }
2879 #endif
2880 
2881  SCIP_CALL( setParams(scip, probdata, symcons, cyclecons) );
2882 
2883  /* setting the offset to the fixed value given in the input file plus the fixings
2884  * given by the reduction techniques */
2885  probdata->offset = offset + reduce_solGetOffset(redsol);
2886  probdata->presolub += offset;
2887 
2888  SCIP_CALL( createModel(scip, probdata) );
2889 
2890 #ifndef WITH_UG
2891  if( graph_typeIsSpgLike(graph) && probdata->mode == STP_MODE_CUT )
2892  {
2893  SCIP_Bool useDecompose = FALSE;
2894  if( !isSubProb )
2895  {
2896  /* NOTE: for performance reasons we already set the decomposition data up...to be able to skip
2897  * cut generation if possible */
2898  SCIP_CALL( SCIPStpcomponentsSetUp(scip, graph) );
2899 
2901  {
2902  useDecompose = TRUE;
2903  usedacuts = STP_CONS_NEVER;
2904  }
2905  }
2906 
2907  if( !useDecompose && usedp != STP_USEDP_NEVER )
2908  {
2909  assert(usedp == STP_USEDP_ALWAYS || usedp == STP_USEDP_AUTOMATIC);
2910 
2911  if( (usedp == STP_USEDP_ALWAYS || SCIPStpDpRelaxIsPromising(scip, graph)) && graph->terms > 1 )
2912  {
2914  usedacuts = STP_CONS_NEVER;
2915  }
2916  }
2917  }
2918 #endif
2919 
2920  if( probdata->mode == STP_MODE_CUT && usedacuts != STP_CONS_NEVER )
2921  {
2922  assert(usedacuts == STP_CONS_ALWAYS || usedacuts == STP_CONS_AUTOMATIC);
2923  SCIP_CALL( createInitialCuts(scip, probdata) );
2924  }
2925 
2926  if( useNodeSol )
2927  SCIP_CALL( addRedsol(scip, probdata, redsol) );
2928 
2929  reduce_solFree(scip, &redsol);
2930 
2931  return SCIP_OKAY;
2932 }
2933 
2934 
2935 /** sets the probdata graph */
2937  SCIP_PROBDATA* probdata, /**< problem data */
2938  GRAPH* graph /**< graph data structure */
2939  )
2940 {
2941  assert(probdata != NULL);
2942 
2943  probdata->graph = graph;
2944 }
2945 
2946 
2947 /** returns the graph */
2949  SCIP_PROBDATA* probdata /**< problem data */
2950  )
2951 {
2952  assert(probdata != NULL);
2953 
2954  return probdata->graph;
2955 }
2956 
2957 /** returns the graph */
2959  SCIP* scip /**< problem data */
2960  )
2961 {
2962  SCIP_PROBDATA* probdata;
2963 
2964  assert(scip != NULL);
2965 
2966  probdata = SCIPgetProbData(scip);
2967  assert(probdata != NULL);
2968 
2969  return probdata->graph;
2970 }
2971 
2972 /** sets the offset */
2974  SCIP_PROBDATA* probdata, /**< problem data */
2975  SCIP_Real offset /**< the offset value */
2976  )
2977 {
2978  assert(probdata != NULL);
2979 
2980  probdata->offset = offset;
2981 }
2982 
2983 
2984 /** returns the number of variables */
2986  SCIP* scip /**< SCIP data structure */
2987  )
2988 {
2989  SCIP_PROBDATA* probdata;
2990 
2991  assert(scip != NULL);
2992 
2993  probdata = SCIPgetProbData(scip);
2994  assert(probdata != NULL);
2995 
2996  return probdata->nvars;
2997 }
2998 
2999 /** returns the array with all variables */
3001  SCIP* scip /**< SCIP data structure */
3002  )
3003 {
3004  SCIP_PROBDATA* probdata;
3005 
3006  assert(scip != NULL);
3007 
3008  probdata = SCIPgetProbData(scip);
3009  assert(probdata != NULL);
3010 
3011  return probdata->edgevars;
3012 }
3013 
3014 /** returns the number of layers */
3016  SCIP* scip /**< SCIP data structure */
3017  )
3018 {
3019  SCIP_PROBDATA* probdata;
3020 
3021  assert(scip != NULL);
3022 
3023  probdata = SCIPgetProbData(scip);
3024  assert(probdata != NULL);
3025 
3026  return probdata->nlayers;
3027 }
3028 
3029 /** returns the number of edges */
3031  SCIP* scip /**< SCIP data structure */
3032  )
3033 {
3034  SCIP_PROBDATA* probdata;
3035 
3036  assert(scip != NULL);
3037 
3038  probdata = SCIPgetProbData(scip);
3039  assert(probdata != NULL);
3040 
3041  return probdata->nedges;
3042 }
3043 
3044 /** returns the number of nodes */
3046  SCIP* scip /**< SCIP data structure */
3047  )
3048 {
3049  SCIP_PROBDATA* probdata;
3050 
3051  assert(scip != NULL);
3052 
3053  probdata = SCIPgetProbData(scip);
3054  assert(probdata != NULL);
3055 
3056  return probdata->nnodes;
3057 }
3058 
3059 /** returns the number of terminals */
3061  SCIP* scip /**< SCIP data structure */
3062  )
3063 {
3064  SCIP_PROBDATA* probdata;
3065 
3066  assert(scip != NULL);
3067 
3068  probdata = SCIPgetProbData(scip);
3069  assert(probdata != NULL);
3070 
3071  return probdata->nterms;
3072 }
3073 
3074 /** returns the number of terminals without the root node */
3076  SCIP* scip /**< SCIP data structure */
3077  )
3078 {
3079  SCIP_PROBDATA* probdata;
3080 
3081  assert(scip != NULL);
3082 
3083  probdata = SCIPgetProbData(scip);
3084  assert(probdata != NULL);
3085 
3086  return probdata->realnterms;
3087 }
3088 
3089 /** returns root */
3091  SCIP* scip /**< SCIP data structure */
3092  )
3093 {
3094  SCIP_PROBDATA* probdata;
3095  GRAPH* graph;
3096 
3097  assert(scip != NULL);
3098 
3099  probdata = SCIPgetProbData(scip);
3100  assert(probdata != NULL);
3101 
3102  graph = probdata->graph;
3103  assert(graph != NULL);
3104 
3105  return graph->source;
3106 }
3107 
3108 /** returns numer of original edges */
3110  SCIP* scip /**< SCIP data structure */
3111  )
3112 {
3113  SCIP_PROBDATA* probdata;
3114 
3115  assert(scip != NULL);
3116 
3117  probdata = SCIPgetProbData(scip);
3118  assert(probdata != NULL);
3119 
3120  return probdata->norgedges;
3121 }
3122 
3123 /** returns offset of the problem */
3125  SCIP* scip /**< SCIP data structure */
3126  )
3127 {
3128  SCIP_PROBDATA* probdata;
3129 
3130  assert(scip != NULL);
3131 
3132  probdata = SCIPgetProbData(scip);
3133  assert(probdata != NULL);
3134 
3135  return probdata->offset;
3136 }
3137 
3138 
3139 /** returns upper bound from presolving
3140 * NOTE: Mind to call the method in transformed stage! */
3142  SCIP* scip /**< SCIP data structure */
3143  )
3144 {
3145  SCIP_PROBDATA* probdata;
3146  const SCIP_Real scale = SCIPgetTransObjscale(scip);
3147 
3148  probdata = SCIPgetProbData(scip);
3149  assert(probdata != NULL);
3150  assert(GT(scale, 0.0));
3151 
3152  return probdata->presolub / scale - SCIPgetTransObjoffset(scip);
3153 }
3154 
3155 
3156 /** returns upper bound from presolving */
3158  SCIP* scip /**< SCIP data structure */
3159  )
3160 {
3161  SCIP_PROBDATA* probdata;
3162 
3163  assert(scip != NULL);
3164 
3165  probdata = SCIPgetProbData(scip);
3166  assert(probdata != NULL);
3167 
3168  return probdata->presolub;
3169 }
3170 
3171 
3172 /** returns the variable for a given index */
3174  SCIP* scip, /**< SCIP data structure */
3175  int idx /**< index of the edge */
3176  )
3177 {
3178  SCIP_PROBDATA* probdata;
3179 
3180  assert(scip != NULL);
3181 
3182  probdata = SCIPgetProbData(scip);
3183  assert(probdata != NULL);
3184 
3185  return probdata->edgevars[idx];
3186 }
3187 
3188 
3189 /** returns the LP solution values */
3191  SCIP* scip, /**< SCIP data structure */
3192  SCIP_SOL* sol /**< solution to get values from */
3193  )
3194 {
3195  SCIP_PROBDATA* probdata;
3196  SCIP_Real* vals;
3197  int e;
3198  int nedges;
3199  assert(scip != NULL);
3200 
3201  probdata = SCIPgetProbData(scip);
3202  assert(probdata != NULL);
3203  vals = probdata->xval;
3204 
3205  nedges = probdata->nedges;
3206  assert(nedges >= 0);
3207 
3208  SCIP_CALL_ABORT( SCIPgetSolVals(scip, sol, nedges, probdata->edgevars, vals) );
3209 
3210  for( e = 0; e < nedges; e++ )
3211  vals[e] = fmax(0.0, fmin(vals[e], 1.0));
3212 
3213  return vals;
3214 }
3215 
3216 
3217 /** returns all edge constraints */
3219  SCIP* scip /**< SCIP data structure */
3220  )
3221 {
3222  SCIP_PROBDATA* probdata;
3223 
3224  assert(scip != NULL);
3225  probdata = SCIPgetProbData(scip);
3226  assert(probdata != NULL);
3227 
3228  return probdata->edgecons;
3229 }
3230 
3231 /** returns all path constraints */
3233  SCIP* scip /**< SCIP data structure */
3234  )
3235 {
3236  SCIP_PROBDATA* probdata;
3237 
3238  assert(scip != NULL);
3239  probdata = SCIPgetProbData(scip);
3240  assert(probdata != NULL);
3241 
3242  return probdata->pathcons;
3243 }
3244 
3245 
3246 /** returns the array with all variables */
3248  SCIP* scip /**< SCIP data structure */
3249  )
3250 {
3251  SCIP_PROBDATA* probdata;
3252 
3253  assert(scip != NULL);
3254 
3255  probdata = SCIPgetProbData(scip);
3256  assert(probdata != NULL);
3257 
3258  return probdata->realterms;
3259 }
3260 
3261 /** returns array */
3263  SCIP* scip /**< SCIP data structure */
3264  )
3265 {
3266  SCIP_PROBDATA* probdata;
3267 
3268  assert(scip != NULL);
3269 
3270  probdata = SCIPgetProbData(scip);
3271  assert(probdata != NULL);
3272 
3273  return probdata->pctermsorder;
3274 }
3275 
3276 /** returns the array with all edge variables */
3278  SCIP* scip /**< SCIP data structure */
3279  )
3280 {
3281  SCIP_PROBDATA* probdata;
3282 
3283  assert(scip != NULL);
3284 
3285  probdata = SCIPgetProbData(scip);
3286  assert(probdata != NULL);
3287 
3288  return probdata->edgevars;
3289 }
3290 
3291 /** returns if 'T' model is being used */
3293  SCIP* scip /**< SCIP data structure */
3294  )
3295 {
3296  SCIP_PROBDATA* probdata;
3297 
3298  assert(scip != NULL);
3299 
3300  probdata = SCIPgetProbData(scip);
3301  assert(probdata != NULL);
3302 
3303  return probdata->bigt;
3304 }
3305 
3306 
3307 /* returns if objective is known to be integral */
3309  SCIP* scip /**< SCIP data structure */
3310  )
3311 {
3312  SCIP_PROBDATA* probdata;
3313 
3314  assert(scip != NULL);
3315 
3316  probdata = SCIPgetProbData(scip);
3317  assert(probdata != NULL);
3318 
3319  return probdata->objIsInt;
3320 }
3321 
3322 
3323 /** returns whether problem seems very hard */
3325  SCIP* scip /**< SCIP data structure */
3326  )
3327 {
3328  SCIP_Real redratio;
3329  GRAPH* graph;
3330  SCIP_PROBDATA* probdata;
3331 
3332  probdata = SCIPgetProbData(scip);
3333  assert(probdata);
3334 
3335  if( probdata->isSubProb )
3336  return FALSE;
3337 
3338  graph = probdata->graph;
3339  assert(graph);
3340 
3341  redratio = getEdgeReductionRatio(probdata, graph);
3342 
3343  if( graph_pc_isPcMw(graph) )
3344  {
3345  if( GT(redratio, MINREDUCTION_RATIO_PCMW) )
3346  return TRUE;
3347  }
3348  else
3349  {
3350  if( GT(redratio, MINREDUCTION_RATIO_STP) )
3351  return TRUE;
3352  }
3353 
3354  return FALSE;
3355 }
3356 
3357 
3358 /** returns if in subproblem */
3360  SCIP* scip /**< SCIP data structure */
3361  )
3362 {
3363  SCIP_PROBDATA* probdata;
3364 
3365  assert(scip != NULL);
3366 
3367  probdata = SCIPgetProbData(scip);
3368  assert(probdata != NULL);
3369 
3370  return probdata->isSubProb;
3371 }
3372 
3373 
3374 /** print (undirected) graph in GML format */
3376  SCIP* scip, /**< SCIP data structure */
3377  const char* filename, /**< name of the output file */
3378  SCIP_SOL* sol, /**< solution to be printed; or NULL for LP solution */
3379  SCIP_Bool printsol /**< should solution be printed? */
3380  )
3381 {
3382  SCIP_PROBDATA* probdata;
3383  SCIP_VAR** edgevars;
3384  SCIP_Bool* edgemark;
3385  int e;
3386 
3387  assert(scip != NULL);
3388  probdata = SCIPgetProbData(scip);
3389  assert(probdata != NULL);
3390 
3391  if( !printsol )
3392  {
3393  /* print the graph without highlighting a solution */
3394  SCIP_CALL( graph_writeGml( probdata->graph, filename, NULL) );
3395  }
3396  else
3397  {
3398  edgevars = probdata->edgevars;
3399  SCIP_CALL( SCIPallocBufferArray(scip, &edgemark, probdata->nedges / 2) );
3400 
3401  /* mark the edges used in the current solution */
3402  for( e = 0; e < probdata->graph->edges; e += 2 )
3403  if( !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e])) || !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e + 1])) )
3404  edgemark[e / 2] = TRUE;
3405  else
3406  edgemark[e / 2] = FALSE;
3407 
3408  /* print the graph highlighting a solution */
3409  SCIP_CALL( graph_writeGml( probdata->graph, filename, edgemark) );
3410 
3411  SCIPfreeBufferArray(scip, &edgemark);
3412  }
3413 
3414  return SCIP_OKAY;
3415 }
3416 
3417 
3418 /** writes the best solution to the intermediate solution file */
3420  SCIP* scip /**< SCIP data structure */
3421  )
3422 {
3423  SCIP_PROBDATA* probdata;
3424  probdata = SCIPgetProbData(scip);
3425 
3426  if( probdata->intlogfile != NULL )
3427  {
3428  SCIP_CALL( SCIPprobdataWriteSolution(scip, probdata->intlogfile) );
3429  }
3430 
3431  return SCIP_OKAY;
3432 }
3433 
3434 /** writes the best solution to a file */
3436  SCIP* scip, /**< SCIP data structure */
3437  FILE* file /**< file to write best solution to; or NULL, to write to stdout */
3438  )
3439 {
3440  SCIP_SOL* sol;
3441  int e;
3442  int k;
3443  GRAPH* graph;
3444  SCIP_PROBDATA* probdata = SCIPgetProbData(scip);
3445  int norgedges;
3446  int norgnodes;
3447  int nsolnodes;
3448  int nsoledges;
3449  STP_Bool* orgedges;
3450  STP_Bool* orgnodes;
3451  int stp_type;
3452 
3453 #ifdef WITH_UG
3454  if( getUgRank() != 0 )
3455  return SCIP_OKAY;
3456 #endif
3457 
3458  assert(probdata != NULL);
3459 
3460 #ifdef WITH_UG
3461  graph = probdata->orggraph;
3462 #else
3463  graph = probdata->graph;
3464 #endif
3465 
3466  assert(graph != NULL);
3467  sol = SCIPgetBestSol(scip);
3468  assert(sol);
3469 
3470  stp_type = graph->stp_type;
3471  if( graph->stp_type == STP_SPG && graph->pcancestors != NULL )
3472  graph->stp_type = STP_RPCSPG;
3473 
3474  if( graph->stp_type == STP_SPG || graph->stp_type == STP_SAP ||graph->stp_type == STP_DCSTP
3475  || graph->stp_type == STP_NWSPG || graph->stp_type == STP_DHCSTP || graph->stp_type == STP_GSTP
3476  || graph->stp_type == STP_RSMT || graph->stp_type == STP_NWPTSPG )
3477  {
3478  SOLHISTORY* solhistory;
3479  SCIP_CALL( solhistory_init(scip, graph, &solhistory) );
3480  SCIP_CALL( solhistory_computeHistory(scip, sol, graph, solhistory) );
3481 
3482  norgnodes = solhistory->norgnodes;
3483  norgedges = solhistory->norgedges;
3484  nsolnodes = solhistory->nsolnodes;
3485  nsoledges = solhistory->nsoledges;
3486  orgnodes = solhistory->orgnodes_isInSol;
3487  orgedges = solhistory->orgedges_isInSol;
3488 
3489  SCIPprobdataWriteLogLine(scip, "Vertices %d\n", nsolnodes);
3490 
3491  for( k = 0; k < norgnodes; k++ )
3492  {
3493  if( orgnodes[k] == TRUE )
3494  SCIPinfoMessage(scip, file, "V %d\n", k + 1);
3495  }
3496 
3497  SCIPprobdataWriteLogLine(scip, "Edges %d\n", nsoledges);
3498 
3499  if( graph->stp_type == STP_DHCSTP )
3500  {
3501  for( e = 0; e < norgedges; e++ )
3502  if( orgedges[e] == TRUE )
3503  SCIPinfoMessage(scip, file, "E %d %d\n", graph->orgtail[e] + 1, graph->orghead[e] + 1);
3504  }
3505  else
3506  {
3507  for( e = 0; e < norgedges; e += 2 )
3508  {
3509  if( graph->stp_type == STP_GSTP )
3510  {
3511  assert(graph->norgmodelknots > 0);
3512 
3513  if( graph->orgtail[e] >= graph->norgmodelknots )
3514  continue;
3515 
3516  if( graph->orghead[e] >= graph->norgmodelknots )
3517  continue;
3518  }
3519 
3520  if( orgedges[e] == TRUE || orgedges[e + 1] == TRUE )
3521  SCIPinfoMessage(scip, file, "E %d %d\n", graph->orgtail[e] + 1, graph->orghead[e] + 1);
3522  }
3523  }
3524 
3525  solhistory_free(scip, &solhistory);
3526  }
3527  else if( graph->stp_type == STP_RSMT )
3528  {
3529  SCIP_VAR** edgevars;
3530  int** coords;
3531  int* ncoords;
3532  int* nodecoords;
3533  int* nodenumber;
3534  int i;
3535  int nodecount;
3536  int grid_dim;
3537  char strdim[256];
3538 
3539  edgevars = probdata->edgevars;
3540  coords = graph->grid_coordinates;
3541  assert(coords != NULL);
3542  ncoords = graph->grid_ncoords;
3543  nodecoords = NULL;
3544  grid_dim = graph->grid_dim;
3545  assert(grid_dim > 1);
3546  assert(grid_dim < 256);
3547  strcpy(strdim, "P");
3548  for( i = 1; i < grid_dim; i++ )
3549  strcat(strdim, "P");
3550 
3551  assert(ncoords != NULL);
3552 
3553  nsolnodes = 0;
3554  nsoledges = 0;
3555  norgedges = graph->orgedges;
3556  norgnodes = graph->orgknots;
3557 
3558  assert(norgedges >= 0);
3559  assert(norgnodes >= 1);
3560 
3561  SCIP_CALL( SCIPallocBufferArray(scip, &nodenumber, norgnodes) );
3562 
3563  SCIP_CALL( SCIPallocBufferArray(scip, &orgedges, norgedges) );
3564  SCIP_CALL( SCIPallocBufferArray(scip, &orgnodes, norgnodes) );
3565 
3566  for( e = 0; e < norgedges; e++ )
3567  orgedges[e] = FALSE;
3568  for( k = 0; k < norgnodes; k++ )
3569  orgnodes[k] = FALSE;
3570 
3571  /* mark solution nodes and edges */
3572  for( e = 0; e < norgedges; e++ )
3573  {
3574  if( !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e])) )
3575  {
3576  nsoledges++;
3577  assert(orgedges[e] == FALSE);
3578  orgedges[e] = TRUE;
3579  if( orgnodes[graph->tail[e]] == FALSE )
3580  {
3581  orgnodes[graph->tail[e]] = TRUE;
3582  nsolnodes++;
3583  }
3584  if( orgnodes[graph->head[e]] == FALSE )
3585  {
3586  orgnodes[graph->head[e]] = TRUE;
3587  nsolnodes++;
3588  }
3589  }
3590  }
3591 
3592  SCIPprobdataWriteLogLine(scip, "Edges %d\n", nsoledges);
3593  SCIPprobdataWriteLogLine(scip, "Points %d\n", nsolnodes);
3594  nodecount = 0;
3595  for( k = 0; k < norgnodes; k++ )
3596  {
3597  if( orgnodes[k] == TRUE )
3598  {
3599  nodenumber[k] = nodecount++;
3600  SCIPprobdataWriteLogLine(scip, "%s ", strdim);
3601  SCIP_CALL( graph_grid_coordinates(scip, coords, &nodecoords, ncoords, k, grid_dim) );
3602  for( i = 0; i < grid_dim; i++ )
3603  {
3604  SCIPprobdataWriteLogLine(scip, "%d ", nodecoords[i]);
3605  }
3606  SCIPprobdataWriteLogLine(scip, "\n");
3607  }
3608  }
3609  assert(nodecount == nsolnodes);
3610  for( e = 0; e < norgedges; e += 2 )
3611  {
3612  if( orgedges[e] == TRUE || orgedges[e + 1] == TRUE )
3613  SCIPinfoMessage(scip, file, "E %d %d\n", nodenumber[graph->orgtail[e]] + 1, nodenumber[graph->orghead[e]] + 1);
3614  }
3615 
3616  SCIPfreeBufferArray(scip, &nodenumber);
3617  SCIPfreeBufferArray(scip, &orgnodes);
3618  SCIPfreeBufferArray(scip, &orgedges);
3619  }
3620  else if( graph_pc_isPcMw(graph))
3621  {
3622  SOLHISTORY* solhistory;
3623  SCIP_CALL( solhistory_init(scip, graph, &solhistory) );
3624  SCIP_CALL( solhistory_computeHistory(scip, sol, graph, solhistory) );
3625 
3626  norgnodes = solhistory->norgnodes;
3627  norgedges = solhistory->norgedges;
3628  nsolnodes = solhistory->nsolnodes;
3629  nsoledges = solhistory->nsoledges;
3630  orgnodes = solhistory->orgnodes_isInSol;
3631  orgedges = solhistory->orgedges_isInSol;
3632 
3633  SCIPprobdataWriteLogLine(scip, "Vertices %d\n", nsolnodes);
3634 
3635  for( k = 0; k < norgnodes; k++ )
3636  {
3637  if( orgnodes[k] == TRUE )
3638  SCIPinfoMessage(scip, file, "V %d\n", k + 1);
3639  }
3640 
3641  SCIPprobdataWriteLogLine(scip, "Edges %d\n", nsoledges);
3642 
3643  for( e = 0; e < norgedges; e += 2 )
3644  {
3645  if( orgedges[e] == TRUE || orgedges[e + 1] == TRUE )
3646  SCIPinfoMessage(scip, file, "E %d %d\n", graph->orgtail[e] + 1, graph->orghead[e] + 1);
3647  }
3648 
3649  solhistory_free(scip, &solhistory);
3650  }
3651 
3652  graph->stp_type = stp_type;
3653 
3654  return SCIP_OKAY;
3655 }
3656 
3657 
3658 /** writes a line to the log file */
3660  SCIP* scip, /**< SCIP data structure */
3661  const char* formatstr, /**< format string like in printf() function */
3662  ... /**< format arguments line in printf() function */
3663  )
3664 {
3665  SCIP_PROBDATA* probdata;
3666  va_list ap;
3667 
3668  assert(scip != NULL);
3669 
3670 #ifdef WITH_UG
3671  if( getUgRank() != 0 )
3672  return;
3673 #endif
3674 
3675  probdata = SCIPgetProbData(scip);
3676  assert(probdata != NULL);
3677 
3678  if( probdata->logfile != NULL )
3679  {
3680  va_start(ap, formatstr); /*lint !e826*/
3681  SCIPmessageVFPrintInfo(SCIPgetMessagehdlr(scip), probdata->logfile, formatstr, ap);
3682  va_end(ap);
3683  }
3684  if( probdata->intlogfile != NULL )
3685  {
3686  va_start(ap, formatstr); /*lint !e826*/
3687  SCIPmessageVFPrintInfo(SCIPgetMessagehdlr(scip), probdata->intlogfile, formatstr, ap);
3688  va_end(ap);
3689  }
3690 }
3691 
3692 /** add new solution */
3694  SCIP* scip, /**< SCIP data structure */
3695  SCIP_Real* nval, /**< array [0..nvars], nval[v] = 1 if node v is in the solution, nval[v] = 0 if not */
3696  SCIP_HEUR* heur, /**< heuristic data */
3697  SCIP_Bool* success /**< denotes whether the new solution has been successfully added */
3698  )
3699 {
3700  SCIP_SOL* sol = NULL;
3701  SCIP_PROBDATA* probdata;
3702  SCIP_VAR** edgevars;
3703  GRAPH* graph;
3704 
3705  assert(scip != NULL);
3706 
3707  probdata = SCIPgetProbData(scip);
3708  edgevars = probdata->edgevars;
3709 
3710  graph = probdata->graph;
3711  assert(graph != NULL);
3712  assert(edgevars != NULL);
3713 
3714  *success = FALSE;
3715 
3716  /* create a new primal solution (initialized to zero) */
3717  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
3718 
3719  /* create path variables (Price mode) or set the flow vars (Flow mode) corresponding to the new solution */
3720  if( probdata->mode != STP_MODE_CUT )
3721  {
3722  SCIP_Real* edgecost;
3723  SCIP_Real* flowvals;
3724  PATH* path;
3725  SCIP_VAR** pathvars;
3726  SCIP_VAR* var = NULL;
3727  char varname[SCIP_MAXSTRLEN];
3728  int realnterms = probdata->realnterms;
3729  int tail;
3730  int nedges = probdata->nedges;
3731  int e;
3732  int t;
3733 
3734  assert(nedges > 0);
3735 
3736  /* allocate memory for the values of the flow variables */
3737  SCIP_CALL( SCIPallocMemoryArray(scip, &flowvals, nedges * (probdata->bigt ? 1 : realnterms)) );
3738  BMSclearMemoryArray(flowvals, nedges * (probdata->bigt ? 1 : realnterms));
3739 
3740  /* allocate memory for the edgecost and the path array (both used for computing shortest paths) */
3741  SCIP_CALL( SCIPallocMemoryArray(scip, &edgecost, nedges) );
3742  SCIP_CALL( SCIPallocMemoryArray(scip, &path, graph->knots) );
3743 
3744  /* Flow mode */
3745  if ( probdata->mode == STP_MODE_FLOW )
3746  {
3747  pathvars = NULL;
3748  }
3749  /* Price mode */
3750  else
3751  {
3752  SCIP_CALL( SCIPallocMemoryArray(scip, &pathvars, realnterms) );
3753  }
3754 
3755  /* mark the tree generated by nvals */
3756  for( e = 0; e < nedges; e++ )
3757  {
3758  if( SCIPisEQ(scip, nval[e], 1.0) )
3759  edgecost[e] = graph->cost[e] / nedges;
3760  else
3761  edgecost[e] = SCIPinfinity(scip);
3762  }
3763 
3764  for( e = 0; e < graph->knots; e++ )
3765  graph->mark[e] = 1;
3766  graph_path_exec(scip, graph, FSP_MODE, graph->source, edgecost, path);
3767 
3768  /* create and add path variables (Price mode) or set the flow variables (Flow mode) */
3769  for( t = 0; t < realnterms; ++t )
3770  {
3771  if( probdata->mode == STP_MODE_PRICE )
3772  {
3773  /* create a new path variable */
3774  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "PathVar%d_X", t);
3775  var = NULL;
3776  SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
3777  SCIP_CALL( SCIPaddVar(scip, var) );
3778  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t], var, 1.0) );
3779  SCIP_CALL( SCIPsetSolVal(scip, sol, var, 1.0) );
3780  assert(var != NULL);
3781  assert(pathvars != NULL);
3782  pathvars[t] = var;
3783  }
3784  tail = probdata->realterms[t];
3785 
3786  /* walk from terminal t to the root */
3787  while( tail != graph->source )
3788  {
3789  if( !probdata->bigt )
3790  {
3791  if( probdata->mode == STP_MODE_PRICE )
3792  {
3793  /* add the new path variable to the constraints corresponding to the current edge */
3794  assert(var != NULL);
3795  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + path[tail].edge], var, 1.0) );
3796  }
3797  else
3798  {
3799  /* set the flow variable corresponding to the current edge */
3800  flowvals[t * nedges + path[tail].edge] = 1.0;
3801  }
3802  }
3803  else
3804  {
3805  if( probdata->mode == STP_MODE_PRICE )
3806  {
3807  assert(var != NULL);
3808  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[path[tail].edge], var, 1.0) );
3809  }
3810  else
3811  {
3812  /* increment the flow variable corresponding to the current edge */
3813  flowvals[path[tail].edge] += 1.0;
3814  }
3815  }
3816  tail = graph->tail[path[tail].edge];
3817  }
3818  if( probdata->mode == STP_MODE_PRICE )
3819  {
3820  assert(var != NULL);
3821  SCIP_CALL( SCIPreleaseVar(scip, &var) );
3822  }
3823  }
3824 
3825  /* store the new solution value */
3826  SCIP_CALL( SCIPsetSolVals(scip, sol, probdata->nvars, edgevars, nval) );
3827  if( probdata->mode == STP_MODE_FLOW )
3828  {
3829  SCIP_CALL( SCIPsetSolVals(scip, sol, nedges * (probdata->bigt ? 1 : realnterms) , probdata->flowvars, flowvals) );
3830  }
3831 
3832  /* try to add new solution to scip and free it immediately */
3833  SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, FALSE, TRUE, TRUE, TRUE, success) );
3834 
3835  /* free local arrays */
3836  SCIPfreeMemoryArrayNull(scip, &flowvals);
3837  SCIPfreeMemoryArrayNull(scip, &edgecost);
3838  SCIPfreeMemoryArrayNull(scip, &path);
3839  SCIPfreeMemoryArrayNull(scip, &pathvars);
3840  }
3841  /* cut mode */
3842  else
3843  {
3844  SCIP_Bool feasible;
3845  int e;
3846  int nvars = probdata->nvars;
3847 
3848  /* check whether the new solution is valid with respect to the original bounds */
3849  for( e = 0; e < nvars; e++ )
3850  {
3851  if( SCIPisGT(scip, nval[e], SCIPvarGetUbGlobal(edgevars[e])) || SCIPisGT(scip, SCIPvarGetLbGlobal(edgevars[e]), nval[e]) )
3852  {
3853  SCIPdebugMessage("solution not valid wrt to global bounds: %d %d nval %f ub: %f \n",
3854  graph->tail[e], graph->head[e], nval[e], SCIPvarGetUbGlobal(edgevars[e]) );
3855  *success = FALSE;
3856  SCIP_CALL( SCIPfreeSol(scip, &sol) );
3857  return SCIP_OKAY;
3858  }
3859  }
3860 
3861  /* post-processing of solution for MWCS and PCSPG */
3862  if( graph->stp_type == STP_PCSPG || graph->stp_type == STP_MWCSP )
3863  {
3864  int k;
3865 
3866  for( k = 0; k < graph->knots; ++k )
3867  {
3868  /* is the kth node a terminal other than the root? */
3869  if( Is_term(graph->term[k]) && k != graph->source )
3870  {
3871  int origterm;
3872  int edge1 = graph->inpbeg[k];
3873  int edge2 = graph->ieat[edge1];
3874 
3875  assert(graph->ieat[edge2] == EAT_LAST);
3876 
3877  if( !SCIPisZero(scip, graph->cost[edge2]) )
3878  {
3879  int tmp = edge1;
3880  edge1 = edge2;
3881  edge2 = tmp;
3882  }
3883  assert(SCIPisZero(scip, graph->cost[edge2]));
3884 
3885  if( nval[edge2] > 0.5 )
3886  {
3887  assert(nval[edge1] < 0.5);
3888  continue;
3889  }
3890  assert(nval[edge1] > 0.5);
3891  assert(nval[edge2] < 0.5);
3892 
3893  origterm = graph->tail[edge2];
3894 
3895  for( e = graph->inpbeg[origterm]; e != EAT_LAST; e = graph->ieat[e] )
3896  {
3897  if( nval[e] > 0.5 )
3898  {
3899  nval[edge1] = 0;
3900  nval[edge2] = 1;
3901  break;
3902  }
3903  }
3904  }
3905  }
3906  }
3907 
3908  /* store the new solution value */
3909  SCIP_CALL( SCIPsetSolVals(scip, sol, nvars, edgevars, nval) );
3910 #if USEOFFSETVAR
3911  if( probdata->offsetvar != NULL && SCIPvarIsActive(probdata->offsetvar) )
3912  {
3913  SCIP_CALL( SCIPsetSolVal(scip, sol, probdata->offsetvar, 1.0) );
3914  }
3915 #endif
3916  SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, &feasible) );
3917 
3918  SCIPdebugMessage("checked sol: feasible=%u\n", feasible);
3919 
3920  /* check solution for feasibility in original problem space */
3921  if( !feasible )
3922  {
3923  SCIP_CALL( SCIPcheckSolOrig(scip, sol, &feasible, TRUE, TRUE) );
3924  SCIPdebugMessage("checked sol org: feasible=%u\n", feasible);
3925 
3926  if( feasible )
3927  {
3928  SCIP_SOL* newsol;
3929  SCIP_VAR** origvars;
3930  SCIP_VAR* var;
3931  int norigvars;
3932  int v;
3933 
3934  SCIP_CALL( SCIPcreateOrigSol(scip, &newsol, SCIPsolGetHeur(sol)) );
3935  origvars = SCIPgetOrigVars(scip);
3936  norigvars = SCIPgetNOrigVars(scip);
3937 
3938  for( v = 0; v < norigvars; ++v )
3939  {
3940  var = origvars[v];
3941  SCIP_CALL( SCIPsetSolVal(scip, newsol, var, SCIPgetSolVal(scip, sol, var)) );
3942  }
3943 
3944  SCIP_CALL( SCIPfreeSol(scip, &sol) );
3945  sol = newsol;
3946  }
3947  }
3948 
3949  /* try to add new solution to scip and free it immediately */
3950  if( feasible )
3951  {
3952 #ifndef NDEBUG
3953  SCIP_CALL( SCIPcheckSol(scip, sol, TRUE, FALSE, TRUE, TRUE, TRUE, &feasible) );
3954  assert(feasible);
3955 #endif
3956 
3957  SCIP_CALL( SCIPaddSolFree(scip, &sol, success) );
3958  }
3959  else
3960  {
3961  SCIP_CALL( SCIPfreeSol(scip, &sol) );
3962  *success = FALSE;
3963  }
3964 
3965  }
3966 
3967  return SCIP_OKAY;
3968 }
3969 
3970 
3971 /** returns problem type */
3973  SCIP* scip /**< SCIP data structure */
3974  )
3975 {
3976  SCIP_PROBDATA* probdata;
3977 
3978  assert(scip != NULL);
3979 
3980  probdata = SCIPgetProbData(scip);
3981  assert(probdata != NULL);
3982 
3983  return probdata->stp_type;
3984 }
3985 
3986 /** writes end of log file */
3988  SCIP* scip /**< SCIP data structure */
3989  )
3990 {
3991  SCIP_PROBDATA* probdata;
3992 
3993  assert(scip != NULL);
3994 
3995  probdata = SCIPgetProbData(scip);
3996  assert(probdata != NULL);
3997 
3998  if( probdata->logfile != NULL )
3999  {
4000  int success;
4001  SCIP_Real factor = 1.0;
4002 
4003  if( probdata->stp_type == STP_MWCSP || probdata->stp_type == STP_RMWCSP || probdata->stp_type == STP_BRMWCSP )
4004  factor = -1.0;
4005 
4006  SCIPprobdataWriteLogLine(scip, "End\n");
4007  SCIPprobdataWriteLogLine(scip, "\n");
4008  SCIPprobdataWriteLogLine(scip, "SECTION Run\n");
4009  if( probdata->ug )
4010  {
4011  SCIPprobdataWriteLogLine(scip, "Threads %d\n", probdata->nSolvers);
4012  SCIPprobdataWriteLogLine(scip, "Time %.1f\n", SCIPgetTotalTime(scip));
4013  SCIPprobdataWriteLogLine(scip, "Dual %16.9f\n", factor * probdata->ugDual);
4014  }
4015  else
4016  {
4017  SCIPprobdataWriteLogLine(scip, "Threads 1\n");
4018  SCIPprobdataWriteLogLine(scip, "Time %.1f\n", SCIPgetTotalTime(scip));
4019  SCIPprobdataWriteLogLine(scip, "Dual %16.9f\n", factor * SCIPgetDualbound(scip));
4020  }
4021  SCIPprobdataWriteLogLine(scip, "Primal %16.9f\n", factor * SCIPgetPrimalbound(scip));
4022  SCIPprobdataWriteLogLine(scip, "End\n");
4023 
4024  if( SCIPgetNSols(scip) > 0 )
4025  {
4026  SCIPprobdataWriteLogLine(scip, "\n");
4027  SCIPprobdataWriteLogLine(scip, "SECTION Finalsolution\n");
4028 
4029  SCIP_CALL( SCIPprobdataWriteSolution(scip, probdata->logfile) );
4030  SCIPprobdataWriteLogLine(scip, "End\n");
4031  }
4032 
4033  success = fclose(probdata->logfile);
4034  if( success != 0 )
4035  {
4036  SCIPerrorMessage("An error occurred while closing logfile\n");
4037  return SCIP_FILECREATEERROR;
4038  }
4039 
4040  probdata->logfile = NULL;
4041  }
4042 
4043 
4044  return SCIP_OKAY;
4045 }
4046 
4047 /** writes end of log file */
4049  SCIP* scip, /**< SCIP data structure */
4050  SCIP_Real dual /**< dual bound */
4051  )
4052 {
4053  SCIP_PROBDATA* probdata;
4054 
4055  assert(scip != NULL);
4056 
4057  probdata = SCIPgetProbData(scip);
4058  probdata->ug = TRUE;
4059  probdata->ugDual = dual;
4060 }
4061 
4062 /** writes end of log file */
4064  SCIP* scip, /**< SCIP data structure */
4065  int nSolvers /**< the number of solvers */
4066  )
4067 {
4068  SCIP_PROBDATA* probdata;
4069 
4070  assert(scip != NULL);
4071 
4072  probdata = SCIPgetProbData(scip);
4073  probdata->nSolvers = nSolvers;
4074 }
4075 
4076 /** branching information from UG */
4078  SCIP* scip, /**< SCIP data structure */
4079  const int lLinearConsNames, /**< number of linear constraints */
4080  const char* linearConsNames, /**< linear constraints string */
4081  const int lSetppcConsNames, /**< number of setppc constraints */
4082  const char* setppcConsNames /**< number of setppc constraints */
4083  )
4084 {
4085 
4086 #ifdef WITH_UG
4087  SCIP_PROBDATA* probdata;
4088  GRAPH* graph;
4089  int* nodestate;
4090  int nnodes;
4091 
4092  assert(scip != NULL);
4093 
4095 
4096  probdata = SCIPgetProbData(scip);
4097 
4098  graph = SCIPprobdataGetGraph(probdata);
4099  assert(graph != NULL);
4100  assert(probdata->orggraph != NULL);
4101 
4102  graph_mincut_exit(scip, graph);
4103  graph_path_exit(scip, graph);
4104  assert(graph->ancestors == NULL);
4105 
4106  graph_free(scip, &graph, TRUE);
4107  graph_copy(scip, probdata->orggraph, &graph);
4108 
4109  probdata->graph = graph;
4110 
4111  assert(graph != NULL && probdata->mode == STP_MODE_CUT);
4112 
4113  nnodes = graph->knots;
4114  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &nodestate, nnodes) );
4115  SCIPStpBranchruleInitNodeState(graph, nodestate);
4116 
4117  for( int i = 0; i < lLinearConsNames; i++ )
4118  {
4119  SCIP_Bool conflict = FALSE;
4120  const char* consname = getBranchLinearConsName(linearConsNames, i);
4121  SCIPdebugMessage("add lin cons %s \n", consname);
4122  if( consname != NULL)
4123  SCIP_CALL_ABORT( STPStpBranchruleParseConsname(nodestate, consname, &conflict) );
4124  }
4125 
4126  for( int i = 0; i < lSetppcConsNames; i++ )
4127  {
4128  SCIP_Bool conflict = FALSE;
4129  const char* consname = getBranchSetppcConsName(setppcConsNames, i);
4130  SCIPdebugMessage("add ppc cons %s \n", consname);
4131  if( consname != NULL)
4132  SCIP_CALL_ABORT( STPStpBranchruleParseConsname(nodestate, consname, &conflict) );
4133  }
4134 
4135  for( int k = 0; k < nnodes; k++ )
4136  {
4137  if( nodestate[k] == BRANCH_STP_VERTEX_TERM && !Is_term(graph->term[k]) )
4138  {
4139  SCIPdebugMessage("UG make term: %d \n", k);
4140 
4141  if( graph_pc_isPcMw(graph) )
4142  {
4143  if( graph_pc_isMw(graph) && !Is_anyTerm(graph->term[k]) )
4144  continue;
4145 
4146  graph_pc_enforceNode(scip, graph, k, NULL);
4147  }
4148  else
4149  {
4150  graph_knot_chg(graph, k, 0);
4151  }
4152  }
4153  else if( nodestate[k] == BRANCH_STP_VERTEX_KILLED )
4154  {
4155  assert(!Is_term(graph->term[k]));
4156 
4157  for( int e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
4158  {
4159  if( graph->cost[e] < BLOCKED )
4160  graph->cost[e] = BLOCKED;
4161 
4162  if( graph->cost[flipedge(e)] < BLOCKED )
4163  graph->cost[flipedge(e)] = BLOCKED;
4164  }
4165 
4166  if( Is_pseudoTerm(graph->term[k]) )
4167  {
4168  const int twinterm = graph_pc_getTwinTerm(graph, k);
4169  const int k2twin = graph->term2edge[k];
4170 #ifndef NDEBUG
4171  const int root2twin = graph_pc_getRoot2PtermEdge(graph, twinterm);
4172 #endif
4173 
4174  assert(graph_pc_isPcMw(graph));
4175  assert(k2twin >= 0 && graph->tail[k2twin] == k && graph->head[k2twin] == twinterm);
4176  assert(root2twin >= 0 && graph->head[root2twin] == twinterm);
4177  assert(SCIPisEQ(scip, graph->cost[root2twin], graph->prize[k]));
4178 
4179  graph->cost[k2twin] = 0.0;
4180 
4181  if( !graph_pc_isRootedPcMw(graph) )
4182  {
4183  const int root2k = graph_pc_getRoot2PtermEdge(graph, twinterm);
4184  assert(graph->tail[root2k] == graph->source && graph->head[root2k] == k);
4185 
4186  graph->cost[root2k] = 0.0;
4187  }
4188  }
4189  }
4190  } /* for k = 0 : nnnodes */
4191 
4192  SCIPfreeBufferArray(scip, &nodestate);
4193 
4194  SCIP_CALL_ABORT( graph_path_init(scip, graph) );
4195  SCIP_CALL_ABORT( graph_mincut_init(scip, graph) );
4196 
4197 #else
4198  assert(0 && "only call me when using UG");
4199 #endif
4200 }
4201 /**@} */
static SCIP_RETCODE createInitialCuts(SCIP *scip, SCIP_PROBDATA *probdata)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:336
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:317
static volatile int nterms
Definition: interrupt.c:38
SCIP_Bool graph_pc_isMw(const GRAPH *)
SCIP_RETCODE solstp_addSolToProb(SCIP *scip, const GRAPH *g, const int *soledge, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: solstp.c:1279
static SCIP_RETCODE createVariables(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real offset)
int *RESTRICT head
Definition: graphdefs.h:224
SCIP_Bool graph_typeIsDirected(const GRAPH *)
Definition: graph_stats.c:83
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9371
SCIP_Bool SCIPprobdataObjIsIntegral(SCIP *scip)
int *RESTRICT orgtail
Definition: graphdefs.h:225
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8344
int source
Definition: graphdefs.h:195
#define FSP_MODE
Definition: graphdefs.h:99
int SCIPprobdataGetNTerms(SCIP *scip)
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
static SCIP_DECL_PROBEXITSOL(probexitsolStp)
SCIP_RETCODE dualascent_execDegCons(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1256
#define Is_term(a)
Definition: graphdefs.h:102
static SCIP_DECL_PROBTRANS(probtransStp)
SCIP_RETCODE SCIPaddOrigObjoffset(SCIP *scip, SCIP_Real addval)
Definition: scip_prob.c:1288
SCIP_Real SCIPgetReadingTime(SCIP *scip)
Definition: scip_timing.c:396
SCIP_CONS ** SCIPprobdataGetEdgeConstraints(SCIP *scip)
static SCIP_RETCODE setStpSolvingMode(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:280
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
Constraint handler for Steiner problems.
SCIP_RETCODE reduce_solGetEdgesol(SCIP *, GRAPH *, REDSOL *, SCIP_Real *, int *)
Definition: reduce_sol.c:1197
signed int edge
Definition: graphdefs.h:287
static SCIP_RETCODE freeConstraintsNonCutModel(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:490
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
void SCIPprobdataSetOffset(SCIP_PROBDATA *probdata, SCIP_Real offset)
#define STP_USEDP_AUTOMATIC
Definition: probdata_stp.h:49
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
SCIP_RETCODE SCIPsetProbCopy(SCIP *scip, SCIP_DECL_PROBCOPY((*probcopy)))
Definition: scip_prob.c:296
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:3015
int terms
Definition: graphdefs.h:192
static SCIP_RETCODE createModel(SCIP *scip, SCIP_PROBDATA *probdata)
SCIP_RETCODE graph_findCentralTerminal(SCIP *, const GRAPH *, int, int *)
Definition: graph_util.c:410
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
#define STP_USEDP_NEVER
Definition: probdata_stp.h:47
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2430
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
Definition: graph_path.c:541
SCIP_RETCODE SCIPprobdataCreateFromGraph(SCIP *scip, SCIP_Real offset, const char *probname, SCIP_Bool isSubProb, GRAPH *graph_move)
#define CUT_MINREDUCTION_RATIO
Definition: probdata_stp.c:76
#define STP_MODE_CUT
Definition: probdata_stp.h:39
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
Definition: misc.c:10974
includes methods for Steiner tree problem solutions
int *RESTRICT maxdeg
Definition: graphdefs.h:206
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
static SCIP_RETCODE createBudgetConstraint(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:617
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, enum PCMW_TmMode pcmw_tmmode, GRAPH *graph, int *starts, const SCIP_Real *prize, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Bool *success)
Definition: heur_tm.c:3418
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5161
dual-ascent and reduction based primal heuristic for Steiner problems
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
Definition: scip_cons.c:1562
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
SCIP_RETCODE SCIPsetProbExitsol(SCIP *scip, SCIP_DECL_PROBEXITSOL((*probexitsol)))
Definition: scip_prob.c:275
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
#define FALSE
Definition: def.h:87
int SCIPprobdataGetNEdges(SCIP *scip)
SCIP_RETCODE SCIPprobdataWriteIntermediateSolution(SCIP *scip)
Includes dual-ascent for classic Steiner tree and some variants.
int *RESTRICT inpbeg
Definition: graphdefs.h:202
static SCIP_RETCODE probdataCreate(SCIP *scip, SCIP_PROBDATA **probdata, GRAPH *graph)
Definition: probdata_stp.c:238
void SCIPStpBranchruleInitNodeState(const GRAPH *g, int *nodestate)
Definition: branch_stp.c:954
SCIP_Real SCIPinfinity(SCIP *scip)
miscellaneous datastructures
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
Problem data for stp problem.
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE graph_grid_coordinates(SCIP *, int **, int **, int *, int, int)
Definition: graph_grid.c:486
includes various files containing graph methods used for Steiner tree problems
#define STP_SAP
Definition: graphdefs.h:43
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8364
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:599
SCIP_RETCODE SCIPsetProbData(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: scip_prob.c:1012
#define STP_DCSTP
Definition: graphdefs.h:47
int SCIPprobdataGetNVars(SCIP *scip)
#define CYC_CONS_LIMIT
Definition: probdata_stp.c:74
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2403
#define CUT_MINTOTNEDGES
Definition: probdata_stp.c:82
#define VERSION_SCIPJACK
Definition: probdata_stp.c:65
#define EAT_LAST
Definition: graphdefs.h:58
#define STP_SPG
Definition: graphdefs.h:42
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:79
SCIP_RETCODE graph_mincut_init(SCIP *, GRAPH *)
Definition: graph_mcut.c:1105
SCIP_Real * costbudget
Definition: graphdefs.h:211
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define STP_CONS_NEVER
Definition: probdata_stp.h:43
#define STP_MODE_PRICE
Definition: probdata_stp.h:41
SCIP_Bool SCIPStpcomponentsAllowsDecomposition(SCIP *scip)
#define MINREDUCTION_RATIO_PCMW
Definition: probdata_stp.c:78
SCIP_RETCODE graph_pack(SCIP *, GRAPH *, GRAPH **, REDSOL *, SCIP_Bool)
Definition: graph_base.c:1324
static SCIP_RETCODE createConstraints(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:954
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
Constraint handler for the set partitioning / packing / covering constraints .
int *RESTRICT orghead
Definition: graphdefs.h:226
#define CUT_MAXNTERMINALS
Definition: probdata_stp.c:79
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:594
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8354
int SCIPprobdataGetNLayers(SCIP *scip)
SCIP_Real reduce_solGetUpperBoundWithOffset(const REDSOL *)
Definition: reduce_sol.c:1263
SCIP_Bool SCIPStpDpRelaxIsPromising(SCIP *scip, GRAPH *graph)
Definition: relax_stpdp.c:239
SCIP_RETCODE SCIPprobdataWriteLogfileEnd(SCIP *scip)
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:170
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:556
SCIP_RETCODE dualascent_exec(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1191
static SCIP_RETCODE addCut(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_RETCODE SCIPtransformVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1386
Components constraint handler for Steiner problems.
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1065
SCIP_RETCODE STPStpBranchruleParseConsname(int *vertexchgs, const char *consname, SCIP_Bool *conflictFound)
Definition: branch_stp.c:902
void SCIPprobdataWriteLogLine(SCIP *scip, const char *formatstr,...)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
int * SCIPprobdataGetRTerms(SCIP *scip)
#define STP_RSMT
Definition: graphdefs.h:49
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_RETCODE SCIPprobdataWriteSolution(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1240
int graph_pc_getRoot2PtermEdge(const GRAPH *, int)
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
SCIP_RETCODE solhistory_init(SCIP *scip, const GRAPH *graph, SOLHISTORY **solhistory)
Definition: solhistory.c:389
includes methods working on the (reduction) history of solutions to Steiner tree problems ...
static SCIP_RETCODE probdataFree(SCIP *scip, SCIP_PROBDATA **probdata)
Definition: probdata_stp.c:542
SCIP_RETCODE SCIPsetObjIntegral(SCIP *scip)
Definition: scip_prob.c:1517
void SCIPprobdataSetNSolvers(SCIP *scip, int nSolvers)
SCIP_CONS ** SCIPprobdataGetPathConstraints(SCIP *scip)
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
IDX ** ancestors
Definition: graphdefs.h:234
int orgedges
Definition: graphdefs.h:220
SCIP_RETCODE reduce_exec(SCIP *, GRAPH *, REDSOL *, int, int, SCIP_Bool)
Definition: reduce_base.c:2192
SCIP_Real SCIPprobdataGetPresolUpperBound(SCIP *scip)
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2768
int SCIPprobdataGetRNTerms(SCIP *scip)
SCIP_Real budget
Definition: graphdefs.h:212
SCIP_Bool SCIPprobdataIsBigt(SCIP *scip)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1389
STP_Bool * orgnodes_isInSol
Definition: solhistory.h:42
SCIP_RETCODE SCIPprobdataPrintGraph(SCIP *scip, const char *filename, SCIP_SOL *sol, SCIP_Bool printsol)
SCIP_Real SCIPprobdataGetOffset(SCIP *scip)
SCIP_Bool SCIPprobdataProbIsAdversarial(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * prize
Definition: graphdefs.h:210
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
#define MINREDUCTION_RATIO_STP
Definition: probdata_stp.c:77
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3497
int *RESTRICT grad
Definition: graphdefs.h:201
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8304
static SCIP_DECL_PROBINITSOL(probinitsolStp)
static void writeCommentSection(SCIP *scip, GRAPH *graph, const char *filename)
Definition: probdata_stp.c:164
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE graph_initPseudoAncestors(SCIP *, GRAPH *)
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2604
#define STP_DHCSTP
Definition: graphdefs.h:52
SCIP_Real reduce_solGetOffset(const REDSOL *)
Definition: reduce_sol.c:1137
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
#define STP_RMWCSP
Definition: graphdefs.h:54
SCIP_RETCODE SCIPtransformCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: scip_cons.c:1521
static int sepaBadGetZeroHalfMaxrounds(const GRAPH *g)
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
int * term2edge
Definition: graphdefs.h:208
IDX ** pcancestors
Definition: graphdefs.h:235
SCIP_RETCODE graph_writeReductionRatioStatsLive(SCIP *, GRAPH *, const char *)
Definition: graph_save.c:316
void reduce_solFree(SCIP *, REDSOL **)
Definition: reduce_sol.c:818
#define STP_PCSPG
Definition: graphdefs.h:44
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8324
#define LT(a, b)
Definition: portab.h:81
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1075
#define STP_OARSMT
Definition: graphdefs.h:50
int orgknots
Definition: graphdefs.h:191
includes solution pool for Steiner tree problems
unsigned char STP_Bool
Definition: portab.h:34
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *filename)
#define CUT_MAXNEDGES
Definition: probdata_stp.c:80
int SCIPprobdataGetType(SCIP *scip)
static SCIP_Bool setParamsSepaIsBad(SCIP_PROBDATA *probdata)
int SCIPprobdataGetNNodes(SCIP *scip)
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1577
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9258
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
SCIP_RETCODE solhistory_computeHistory(SCIP *scip, SCIP_SOL *scipsol, const GRAPH *g, SOLHISTORY *solhistory)
Definition: solhistory.c:437
#define GT(a, b)
Definition: portab.h:84
void graph_pc_getReductionRatios(const GRAPH *, SCIP_Real *, SCIP_Real *)
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip_sol.c:3440
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPsetProbTrans(SCIP *scip, SCIP_DECL_PROBTRANS((*probtrans)))
Definition: scip_prob.c:211
SCIP_RETCODE SCIPprobdataSetDefaultParams(SCIP *scip)
int *RESTRICT ieat
Definition: graphdefs.h:230
#define STP_NWPTSPG
Definition: graphdefs.h:48
void SCIPprobdataSetGraph(SCIP_PROBDATA *probdata, GRAPH *graph)
void SCIPprintSysError(const char *message)
Definition: misc.c:10664
void graph_mincut_exit(SCIP *, GRAPH *)
Definition: graph_mcut.c:1175
int *RESTRICT tail
Definition: graphdefs.h:223
#define BRANCH_STP_VERTEX_TERM
Definition: branch_stp.h:39
SCIP_VAR ** SCIPprobdataGetEdgeVars(SCIP *scip)
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3231
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8105
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_RETCODE SCIPStpHeurSlackPruneRun(SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool initialreduce, SCIP_Bool fullreduce)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8284
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8254
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
void SCIPprobdataSetDualBound(SCIP *scip, SCIP_Real dual)
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_RETCODE SCIPchgVarBranchPriority(SCIP *scip, SCIP_VAR *var, int branchpriority)
Definition: scip_var.c:7977
SCIP_Real SCIPprobdataGetPresolUpperBoundWithOffset(SCIP *scip)
SCIP_RETCODE graph_copyPseudoAncestors(SCIP *, const GRAPH *, GRAPH *)
Definition: graph_base.c:1088
STP_Bool * orgedges_isInSol
Definition: solhistory.h:43
Constraint handler for linear constraints in their most general form, .
static SCIP_RETCODE presolveStp(SCIP *scip, SCIP_PROBDATA *probdata, REDSOL *redsol)
Definition: probdata_stp.c:353
int SCIPprobdataGetRoot(SCIP *scip)
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
int grid_dim
Definition: graphdefs.h:259
SCIP_RETCODE SCIPcreateConsStp(SCIP *scip, SCIP_CONS **cons, const char *name, GRAPH *graph)
Definition: cons_stp.c:1135
SCIP_Bool SCIPprobdataIsSubproblem(SCIP *scip)
#define BRANCH_STP_VERTEX_KILLED
Definition: branch_stp.h:37
SCIP_Real SCIPgetTransObjscale(SCIP *scip)
Definition: scip_prob.c:1388
int ** grid_coordinates
Definition: graphdefs.h:261
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:652
int layers
Definition: graphdefs.h:193
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
#define STP_NWSPG
Definition: graphdefs.h:46
void graph_pc_enforceNode(SCIP *, GRAPH *, int, SCIP_Real *)
SCIP_Real * r
Definition: circlepacking.c:50
Steiner vertex branching rule.
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
Definition: scip_prob.c:1365
SCIP_RETCODE SCIPsetProbInitsol(SCIP *scip, SCIP_DECL_PROBINITSOL((*probinitsol)))
Definition: scip_prob.c:253
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
static SCIP_DECL_PROBDELTRANS(probdeltransStp)
static SCIP_RETCODE setParams(SCIP *scip, SCIP_PROBDATA *probdata, int symcons, int cyclecons)
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:125
#define STP_CONS_AUTOMATIC
Definition: probdata_stp.h:45
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPprobdataGetNorgEdges(SCIP *scip)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE freeConstraintsCutModel(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:423
static SCIP_RETCODE createLogfile(SCIP *scip, SCIP_PROBDATA *probdata, const char *intlogfilename, const char *logfilename, const char *filename, const char *probname)
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:702
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
includes various testing methods for Steiner tree problems
void SCIPmessageVFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr, va_list ap)
Definition: message.c:624
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
#define STP_REDUCTION_NONE
Definition: reducedefs.h:39
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_VAR * a
Definition: circlepacking.c:57
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1211
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8334
#define BLOCKED
Definition: graphdefs.h:90
static SCIP_DECL_PROBCOPY(probcopyStp)
#define STP_MODE_FLOW
Definition: probdata_stp.h:40
SCIP_RETCODE SCIPStpDpRelaxActivate(SCIP *scip)
Definition: relax_stpdp.c:272
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8274
SCIP_RETCODE graph_load(SCIP *, GRAPH **, const char *, PRESOL *)
Definition: graph_load.c:885
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_RETCODE SCIPtransformVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1346
SCIP_VAR * SCIPprobdataGetedgeVarByIndex(SCIP *scip, int idx)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8264
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: graph_base.c:939
#define STP_BRMWCSP
Definition: graphdefs.h:55
shortest paths based primal heuristics for Steiner problems
#define STP_CONS_ALWAYS
Definition: probdata_stp.h:44
#define SCIP_Longint
Definition: def.h:162
int edges
Definition: graphdefs.h:219
void initReceivedSubproblem(SCIP *scip, const int lLinearConsNames, const char *linearConsNames, const int lSetppcConsNames, const char *setppcConsNames)
SCIP_Real SCIPgetTotalTime(SCIP *scip)
Definition: scip_timing.c:342
int * grid_ncoords
Definition: graphdefs.h:260
SCIP_RETCODE dualascent_execPcMw(SCIP *scip, GRAPH *g, SCIP_Real *redcost, SCIP_Real *objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, int nruns)
Definition: dualascent.c:1319
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define STP_GSTP
Definition: graphdefs.h:53
#define SYM_CONS_LIMIT
Definition: probdata_stp.c:73
static SCIP_RETCODE createHopConstraint(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:590
SCIP_Real fixed
Definition: graphdefs.h:276
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetProbDeltrans(SCIP *scip, SCIP_DECL_PROBDELTRANS((*probdeltrans)))
Definition: scip_prob.c:232
#define nnodes
Definition: gastrans.c:65
static SCIP_RETCODE createPrizeConstraints(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:676
#define CUT_MAXTOTNEDGES
Definition: probdata_stp.c:81
int * SCIPprobdataGetPctermsorder(SCIP *scip)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIP_RETCODE SCIPsetProbDelorig(SCIP *scip, SCIP_DECL_PROBDELORIG((*probdelorig)))
Definition: scip_prob.c:190
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
static SCIP_Real getEdgeReductionRatio(SCIP_PROBDATA *probdata, const GRAPH *graph)
static SCIP_RETCODE createDegreeConstraints(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:641
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
#define Is_anyTerm(a)
Definition: graphdefs.h:105
#define STP_USEDP_ALWAYS
Definition: probdata_stp.h:48
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
SCIP_RETCODE graph_writeGml(const GRAPH *, const char *, const SCIP_Bool *)
Definition: graph_save.c:441
const char * SCIPlpiGetSolverName(void)
Definition: lpi_clp.cpp:445
int hoplimit
Definition: graphdefs.h:216
SCIP_RETCODE solpool_addSolToScip(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const int *result, SCIP_Bool *success)
Definition: solpool.c:150
includes various reduction methods for Steiner tree problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
SCIP_RETCODE stptest_testAll(SCIP *)
Definition: stptest_base.c:34
#define STP_RPCSPG
Definition: graphdefs.h:45
#define STP_MWCSP
Definition: graphdefs.h:51
GRAPH * SCIPprobdataGetGraph2(SCIP *scip)
void solhistory_free(SCIP *scip, SOLHISTORY **solhistory)
Definition: solhistory.c:419
Steiner tree dynamic programming relaxator.
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:874
static SCIP_DECL_PROBDELORIG(probdelorigStp)
int graph_pc_getTwinTerm(const GRAPH *, int)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17580
int norgmodelknots
Definition: graphdefs.h:187
SCIP_RETCODE SCIPStpcomponentsSetUp(SCIP *scip, GRAPH *graph)
int orgsource
Definition: graphdefs.h:194
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
static SCIP_RETCODE addRedsol(SCIP *scip, SCIP_PROBDATA *probdata, REDSOL *redsol)
Definition: probdata_stp.c:304