Scippy

SCIP

Solving Constraint Integer Programs

heur_tm.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 heur_tm.c
17  * @brief Shortest paths based primal heuristics for Steiner problems
18  * @author Gerald Gamrath
19  * @author Thorsten Koch
20  * @author Daniel Rehfeldt
21  * @author Michael Winkler
22  *
23  * This file implements several shortest paths based primal heuristics for Steiner problems, see
24  * "SCIP-Jack - A solver for STP and variants with parallelization extensions" by
25  * Gamrath, Koch, Maher, Rehfeldt and Shinano
26  * and
27  * "Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the
28  * Maximum-Weight Connected Subgraph Problem" by
29  * Rehfeldt and Koch
30  *
31  * A list of all interface methods can be found in heur_tm.h
32  *
33  */
34 
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 //#define SCIP_DEBUG
37 #include <assert.h>
38 #include <string.h>
39 #include "heur_tm.h"
40 #include "relax_stp.h"
41 #include "probdata_stp.h"
42 #include "portab.h"
43 #include "solstp.h"
44 #include "scip/misc.h"
45 #include "shortestpath.h"
46 #include "reduce.h"
47 #include <math.h>
48 
49 #define HEUR_NAME "TM"
50 #define HEUR_DESC "shortest path based primal heuristics for Steiner trees"
51 #define HEUR_DISPCHAR '+'
52 #define HEUR_PRIORITY 10000000
53 #define HEUR_FREQ 1
54 #define HEUR_FREQOFS 0
55 #define HEUR_MAXDEPTH -1
56 #define HEUR_TIMING (SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
57 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
58 
59 #define DEFAULT_EVALRUNS 20 /**< number of runs */
60 #define DEFAULT_INITRUNS 100 /**< number of initial runs */
61 #define DEFAULT_LEAFRUNS 25 /**< number of runs at leafs */
62 #define DEFAULT_HARD_RUNSMULT 1.75 /**< multiplier */
63 #define DEFAULT_ROOTRUNS 50 /**< number of runs at the root */
64 #define DEFAULT_DURINGLPFREQ 5 /**< frequency during LP solving */
65 #define DEFAULT_TYPE 0 /**< heuristic to execute */
66 #define DEFAULT_PCMODE 4 /**< solving mode for PC/MW */
67 
68 #define DEFAULT_RANDSEED 5 /**< seed for pseudo-random functions */
69 
70 #define TM_HARD_MAXNEDGES 15000
71 
72 #define AUTO 0
73 #define TM_SP 1
74 #define TM_VORONOI 2
75 #define TM_DIJKSTRA 3
76 
77 #define TM_USE_CSR
78 #define TM_USE_CSR_PCMW
79 
80 
81 #ifdef WITH_UG
82 int getUgRank(void);
83 #endif
84 
85 /*
86  * Data structures
87  */
88 
89 
90 typedef
91 struct TM_base_data
92 {
93  int* heap_position; /**< heap position array or */
94  DENTRY* heap_entries; /**< entries array or NULL */
95  SDPROFIT* sdprofit1st; /**< profit or NULL */
96  CSR* csr; /**< CSR with possible biased costs.
97  NOTE: shares memory with csr_orgcosts! */
98  CSR* csr_orgcosts; /**< CSR with original costs.
99  NOTE: shares memory with csr! */
100  DHEAP* dheap; /**< Dijkstra heap */
101  const SCIP_Real* cost; /**< arc costs */
102  const SCIP_Real* costrev; /**< reversed arc costs */
103  SCIP_Real* nodes_dist; /**< distance values for each node */
104  int* nodes_pred; /**< predecessor for each node */
105  int* startnodes; /**< array containing start vertices (NULL to not provide any) */
106  int* result; /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
107  int* best_result; /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
108  STP_Bool* connected; /**< array indicating whether a node is part of solution (TRUE/FALSE) */
109  SCIP_Real best_obj; /**< objective */
110  int best_start; /**< start node */
111  int nruns; /**< number of runs */
112 } TMBASE;
113 
114 
115 /** All shortest paths data
116  * NOTE: DEPRECATED */
117 typedef
118 struct TM_all_shortestpath
119 {
120  int** pathedge; /**< node predecessors for each terminal */
121  SCIP_Real** pathdist; /**< node distances for each terminal */
122 } TMALLSP;
123 
124 
125 /** Voronoi TM heuristic data
126  * NOTE: DEPRECATED */
127 typedef
128 struct TM_voronoi
129 {
134  int** node_base;
135  int** node_edge;
136 } TMVNOI;
137 
138 
139 /** primal heuristic data */
140 struct SCIP_HeurData
141 {
142  SCIP_Longint nlpiterations; /**< number of total LP iterations*/
143  SCIP_Longint ncalls; /**< number of total calls (of TM) */
144  SCIP_Longint nexecs; /**< number of total executions (of TM) */
145  SCIP_Real hopfactor; /**< edge multiplication factor for hop constrained problems */
146  SCIP_Real hardrunsmult; /**< multiplier */
147  int stp_type; /**< problem type */
148  int evalruns; /**< number of runs */
149  int initruns; /**< number of initial runs */
150  int leafruns; /**< number of runs at leafs */
151  int rootruns; /**< number of runs at the root */
152  int duringlpfreq; /**< frequency during LP solving */
153  int type; /**< Heuristic type: 0 automatic, 1 TM_SP, 2 TM_VORONOI, 3 TM_DIJKSTRA */
154  int beststartnode; /**< start node of the so far best found solution */
155  unsigned int randseed; /**< seed value for random number generator */
156  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
157  unsigned int timing; /**< timing for timing mask */
158  enum PCMW_TmMode pcmw_mode; /**< solving mode for PCMW */
159 };
160 
161 /*
162  * Static methods
163  */
164 
165 #if defined(TM_USE_CSR_PCMW) && !defined(NDEBUG)
166 /** debug method; checks whether CSR solution objective is actually computed correctly */
167 static
169  SCIP* scip, /**< SCIP data structure */
170  const GRAPH* graph, /**< graph data structure */
171  const TMBASE* tmbase /**< data */
172 )
173 {
174  const int *const result_csr = tmbase->result;
175  const STP_Bool *const connected = tmbase->connected;
176  const SCIP_Real obj = solstp_pcGetObjCsr(graph, tmbase->csr_orgcosts, result_csr, connected);
177  const int nedges = graph_get_nEdges(graph);
178  const int nnodes = graph_get_nNodes(graph);
179  int *result_dummy;
180  STP_Bool *connected_dummy;
181  SCIP_Real obj_dummy;
182  SCIP_CALL_ABORT(SCIPallocMemoryArray(scip, &result_dummy, nedges));
183  SCIP_CALL_ABORT(SCIPallocMemoryArray(scip, &connected_dummy, nnodes));
184  BMScopyMemoryArray(connected_dummy, connected, nnodes);
185 
186  solstp_convertCsrToGraph(scip, graph, tmbase->csr_orgcosts, result_csr, connected_dummy, result_dummy);
187 
188  assert(!stpsol_pruningIsPossible(graph, result_dummy, connected_dummy));
189 
190  obj_dummy = solstp_getObjBounded(graph, result_dummy, 0.0, nedges);
191 
192  if( graph_pc_isPc(graph) )
193  obj_dummy += graph_pc_getNonLeafTermOffset(scip, graph);
194 
195  SCIPfreeMemoryArray(scip, &connected_dummy);
196  SCIPfreeMemoryArray(scip, &result_dummy);
197 
198  return SCIPisEQ(scip, obj_dummy, obj);
199 }
200 #endif
201 
202 /** information method for a parameter change of random seed */
203 static
204 SCIP_DECL_PARAMCHGD(paramChgdRandomseed)
205 { /*lint --e{715}*/
206  SCIP_HEURDATA* heurdata;
207  int newrandseed;
208 
209  newrandseed = SCIPparamGetInt(param);
210 
211  heurdata = (SCIP_HEURDATA*)SCIPparamGetData(param);
212  assert(heurdata != NULL);
213 
214  heurdata->randseed = (unsigned int)newrandseed;
215 
216  return SCIP_OKAY;
217 }
218 
219 
220 /*
221  * local functions
222  */
223 
224 /** initializes */
225 static
227  SCIP* scip, /**< SCIP data structure */
228  const GRAPH* graph, /**< graph structure */
229  TMBASE* tmbase /**< data */
230 )
231 {
232 #ifdef TM_USE_CSR
233  SCIP_Real* costorg_csr;
234 #endif
235  const int nnodes = graph_get_nNodes(graph);
236  const int nedges = graph_get_nEdges(graph);
237 
238  assert(tmbase && scip);
239  assert(tmbase->nodes_dist == NULL);
240  assert(tmbase->nodes_pred == NULL);
241  assert(tmbase->startnodes == NULL);
242  assert(tmbase->connected == NULL);
243  assert(tmbase->result == NULL);
244  assert(tmbase->cost);
245 
246  if( tmbase->nruns < 1 )
247  tmbase->nruns = 1;
248 
249  SCIP_CALL( SCIPallocBufferArray(scip, &(tmbase->startnodes), MIN(tmbase->nruns, nnodes)) );
250  SCIP_CALL( SCIPallocBufferArray(scip, &(tmbase->result), nedges) );
251  SCIP_CALL( SCIPallocBufferArray(scip, &(tmbase->nodes_dist), nnodes) );
252  SCIP_CALL( SCIPallocBufferArray(scip, &(tmbase->nodes_pred), nnodes) );
253  SCIP_CALL( SCIPallocBufferArray(scip, &(tmbase->connected), nnodes) );
254  tmbase->sdprofit1st = NULL;
255 
256 #ifdef TM_USE_CSR
257  SCIP_CALL( SCIPallocBufferArray(scip, &(tmbase->heap_position), nnodes) );
258  SCIP_CALL( SCIPallocBufferArray(scip, &(tmbase->heap_entries), nnodes + 2) );
259  SCIP_CALL( graph_heap_create(scip, nnodes, tmbase->heap_position, tmbase->heap_entries, &(tmbase->dheap)) );
260  SCIP_CALL( graph_csr_allocWithEdgeId(scip, nnodes, nedges, &(tmbase->csr)) );
261  graph_csr_build(graph, tmbase->cost, tmbase->csr);
262 
263  /* build the original cost CSR.
264  * NOTE: it consists mostly of alias, except for the edge costs */
265  SCIP_CALL( SCIPallocBufferArray(scip, &(costorg_csr), nedges) );
266  SCIP_CALL( SCIPallocMemory(scip, &(tmbase->csr_orgcosts)) );
267  *(tmbase->csr_orgcosts) = *(tmbase->csr);
268  tmbase->csr_orgcosts->cost = costorg_csr;
269 
270  if( graph_pc_isPc(graph) )
271  {
272  graph_pc_getOrgCostsCsr(scip, graph, tmbase->csr_orgcosts);
273  }
274  else
275  {
276  graph_csr_buildCosts(graph, tmbase->csr_orgcosts, graph->cost, costorg_csr);
277  }
278 
279  if( graph_typeIsSpgLike(graph) )
280  {
281  SCIP_CALL( reduce_sdprofitInit1stOnly(scip, graph, tmbase->cost, &(tmbase->sdprofit1st)));
282  }
283 
284 #else
285  tmbase->heap_position = NULL;
286  tmbase->heap_entries = NULL;
287  tmbase->dheap = NULL;
288  tmbase->csr = NULL;
289  tmbase->csr_orgcosts = NULL;
290 #endif
291 
292  return SCIP_OKAY;
293 }
294 
295 
296 /** frees */
297 static
299  SCIP* scip, /**< SCIP data structure */
300  const GRAPH* graph, /**< graph structure */
301  TMBASE* tmbase /**< data */
302 )
303 {
304 #ifdef TM_USE_CSR
305  SCIPfreeBufferArray(scip, &(tmbase->csr_orgcosts->cost));
306  SCIPfreeMemory(scip, &(tmbase->csr_orgcosts));
307  graph_csr_free(scip, &(tmbase->csr));
308  graph_heap_free(scip, FALSE, FALSE, &(tmbase->dheap));
309  SCIPfreeBufferArray(scip, &(tmbase->heap_entries));
310  SCIPfreeBufferArray(scip, &(tmbase->heap_position));
311 #endif
312 
313  if( tmbase->sdprofit1st )
314  {
315  reduce_sdprofitFree(scip, &(tmbase->sdprofit1st));
316  }
317 
318  assert(tmbase->dheap == NULL);
319  assert(tmbase->csr == NULL);
320  assert(tmbase->heap_position == NULL);
321  assert(tmbase->heap_entries == NULL);
322  SCIPfreeBufferArray(scip, &(tmbase->connected));
323  SCIPfreeBufferArray(scip, &(tmbase->nodes_pred));
324  SCIPfreeBufferArray(scip, &(tmbase->nodes_dist));
325  SCIPfreeBufferArray(scip, &(tmbase->result));
326  SCIPfreeBufferArray(scip, &(tmbase->startnodes));
327 }
328 
329 
330 /** initializes */
331 static
333  SCIP* scip, /**< SCIP data structure */
334  const GRAPH* graph, /**< graph structure */
335  TMALLSP* tmallsp /**< data */
336 )
337 {
338  const int nnodes = graph_get_nNodes(graph);
339 
340  SCIP_CALL(SCIPallocBufferArray(scip, &(tmallsp->pathdist), nnodes));
341  SCIP_CALL(SCIPallocBufferArray(scip, &(tmallsp->pathedge), nnodes));
342  BMSclearMemoryArray((tmallsp->pathdist), nnodes);
343  BMSclearMemoryArray((tmallsp->pathedge), nnodes);
344 
345  for( int k = 0; k < nnodes; k++ )
346  {
347  graph->mark[k] = (graph->grad[k] > 0);
348 
349  if( Is_term(graph->term[k]) )
350  {
351  SCIP_CALL(SCIPallocBufferArray(scip, &((tmallsp->pathdist[k])), nnodes)); /*lint !e866*/
352  SCIP_CALL(SCIPallocBufferArray(scip, &((tmallsp->pathedge[k])), nnodes)); /*lint !e866*/
353  }
354  else
355  {
356  tmallsp->pathdist[k] = NULL;
357  tmallsp->pathedge[k] = NULL;
358  }
359  }
360 
361  return SCIP_OKAY;
362 }
363 
364 
365 /** frees */
366 static
368  SCIP* scip, /**< SCIP data structure */
369  const GRAPH* graph, /**< graph structure */
370  TMALLSP* tmallsp /**< data */
371 )
372 {
373  const int nnodes = graph_get_nNodes(graph);
374 
375  assert(tmallsp->pathedge);
376  assert(tmallsp->pathdist);
377 
378  for( int k = nnodes - 1; k >= 0; k-- )
379  {
380  SCIPfreeBufferArrayNull(scip, &(tmallsp->pathedge[k]));
381  SCIPfreeBufferArrayNull(scip, &(tmallsp->pathdist[k]));
382  }
383 
384  SCIPfreeBufferArray(scip, &(tmallsp->pathedge));
385  SCIPfreeBufferArray(scip, &(tmallsp->pathdist));
386 }
387 
388 
389 /** initializes */
390 static
392  SCIP* scip, /**< SCIP data structure */
393  const GRAPH* graph, /**< graph structure */
394  TMVNOI* tmvnoi /**< data */
395 )
396 {
397  const int nnodes = graph_get_nNodes(graph);
398  const int nterms = graph->terms;
399 
400  assert(nnodes > 0 && nterms > 0);
401 
402  SCIP_CALL( SCIPallocBufferArray(scip, &(tmvnoi->nodenterms), nnodes) );
403  SCIP_CALL( SCIPallocBufferArray(scip, &(tmvnoi->gnodearr), nnodes) );
404  SCIP_CALL( SCIPallocBufferArray(scip, &(tmvnoi->node_base), nnodes) );
405  SCIP_CALL( SCIPallocBufferArray(scip, &(tmvnoi->node_dist), nnodes) );
406  SCIP_CALL( SCIPallocBufferArray(scip, &(tmvnoi->node_edge), nnodes) );
407 
408  for( int k = 0; k < nnodes; k++ )
409  {
410  SCIP_CALL( SCIPallocBuffer(scip, &(tmvnoi->gnodearr[k])) ); /*lint !e866*/
411  SCIP_CALL( SCIPallocBufferArray(scip, &(tmvnoi->node_base[k]), nterms) ); /*lint !e866*/
412  SCIP_CALL( SCIPallocBufferArray(scip, &(tmvnoi->node_dist[k]), nterms) ); /*lint !e866*/
413  SCIP_CALL( SCIPallocBufferArray(scip, &(tmvnoi->node_edge[k]), nterms) ); /*lint !e866*/
414  }
415 
416  SCIP_CALL( SCIPpqueueCreate( &(tmvnoi->pqueue), nnodes, 2.0, GNODECmpByDist, NULL) );
417 
418  return SCIP_OKAY;
419 }
420 
421 
422 /** frees */
423 static
425  SCIP* scip, /**< SCIP data structure */
426  const GRAPH* graph, /**< graph structure */
427  TMVNOI* tmvnoi /**< data */
428 )
429 {
430  const int nnodes = graph_get_nNodes(graph);
431 
432  SCIPpqueueFree(&(tmvnoi->pqueue));
433 
434  assert(tmvnoi->node_edge != NULL);
435  assert(tmvnoi->node_dist != NULL);
436  assert(tmvnoi->node_base != NULL);
437  assert(tmvnoi->gnodearr != NULL);
438 
439  for( int k = nnodes - 1; k >= 0; k-- )
440  {
441  SCIPfreeBufferArray(scip, &(tmvnoi->node_edge[k]));
442  SCIPfreeBufferArray(scip, &(tmvnoi->node_dist[k]));
443  SCIPfreeBufferArray(scip, &(tmvnoi->node_base[k]));
444  SCIPfreeBuffer(scip, &(tmvnoi->gnodearr[k]));
445  }
446 
447  SCIPfreeBufferArray(scip, &(tmvnoi->node_edge));
448  SCIPfreeBufferArray(scip, &(tmvnoi->node_dist));
449  SCIPfreeBufferArray(scip, &(tmvnoi->node_base));
450  SCIPfreeBufferArray(scip, &(tmvnoi->gnodearr));
451  SCIPfreeBufferArray(scip, &(tmvnoi->nodenterms));
452 }
453 
454 
455 /** returns TM heur data */
456 static inline
458  SCIP* scip /**< SCIP data structure */
459 )
460 {
461  SCIP_HEURDATA* heurdata;
462 
463  assert(scip);
464 
465  heurdata = SCIPheurGetData(SCIPfindHeur(scip, "TM"));
466  assert(heurdata);
467 
468  return heurdata;
469 }
470 
471 
472 /** returns offset for edge costs */
473 static
475  SCIP* scip, /**< SCIP data structure */
476  const GRAPH* graph /**< graph data structure */
477 )
478 {
479  const SCIP_Real eps = SCIPepsilon(scip);
480 
481  return (2.0 * eps);
482 }
483 
484 
485 
486 /** returns whether TM SP type */
487 static
489  const GRAPH* graph /**< graph data structure */
490 )
491 {
492  const int type = graph->stp_type;
493 
494  return (type == STP_DHCSTP || type == STP_DCSTP);
495 }
496 
497 /** returns mode */
498 static
500  SCIP_HEURDATA* heurdata, /**< SCIP data structure */
501  const GRAPH* graph /**< graph data structure */
502 )
503 {
504  /* get user parameter */
505  int mode = heurdata->type;
506  assert(mode == AUTO || mode == TM_SP || mode == TM_VORONOI || mode == TM_DIJKSTRA);
507 
508  if( graph_pc_isPcMw(graph) )
509  {
510  mode = TM_DIJKSTRA;
511  }
512  else if( isTMSpType(graph) )
513  {
514  mode = TM_SP;
515  }
516  else
517  {
518  if( mode == AUTO )
519  mode = TM_DIJKSTRA;
520  }
521 
522  return mode;
523 }
524 
525 
526 
527 /** updates best (non PC/MW) solution if possible */
528 static inline
530  SCIP* scip, /**< SCIP data structure */
531  const GRAPH* graph, /**< graph data structure */
532  int startnode, /**< start vertex */
533  SCIP_Bool solfound, /**< solution found in this run? */
534  TMBASE* tmbase, /**< data */
535  SCIP_Bool* success /**< pointer to store whether a solution could be found */
536 )
537 {
538  SCIP_Bool useCsr = !isTMSpType(graph);
539 
540 #ifndef TM_USE_CSR
541  useCsr = FALSE;
542 #endif
543 
544  if( useCsr )
545  {
546  const int* const result_csr = tmbase->result;
547  STP_Bool* const connected = tmbase->connected;
548 
549  /* compute objective value w.r.t. original costs! */
550  const SCIP_Real obj = solstp_getObjCsr(graph, tmbase->csr_orgcosts, result_csr, connected);
551 
552  SCIPdebugMessage("new obj=%f (start=%d)\n ", obj, startnode);
553 
554  if( LT(obj, tmbase->best_obj) )
555  {
556  SCIPdebugMessage("\n improved obj=%f \n ", obj);
557 
558  tmbase->best_obj = obj;
559  tmbase->best_start = startnode;
560  solstp_convertCsrToGraph(scip, graph, tmbase->csr_orgcosts, result_csr, connected, tmbase->best_result);
561 
562  (*success) = TRUE;
563  assert(solstp_isValid(scip, graph, tmbase->best_result));
564  }
565  }
566  else
567  {
568  /* here another measure than in the TM heuristics is being used */
569  const int nedges = graph_get_nEdges(graph);
570  const int* const result = tmbase->result;
571  const SCIP_Real obj = solstp_getObjBounded(graph, result, 0.0, nedges);
572 
573  assert(!graph_typeIsSpgLike(graph) && "test");
574 
575  if( SCIPisLT(scip, obj, tmbase->best_obj) && (graph->stp_type != STP_DCSTP || solfound) )
576  {
577 #ifdef SCIP_DEBUG
578  if( graph->stp_type == STP_DHCSTP )
579  SCIPdebugMessage("edges vs hop-limit: %d, %d \n", solstp_getNedges(graph, result), graph->hoplimit);
580 
581 #endif
582  if( graph->stp_type != STP_DHCSTP || solstp_getNedges(graph, result) <= graph->hoplimit )
583  {
584  SCIPdebugMessage("improved obj=%.12e\n", obj);
585 
586  tmbase->best_obj = obj;
587  BMScopyMemoryArray(tmbase->best_result, result, nedges);
588  (*success) = TRUE;
589  }
590  }
591  }
592 }
593 
594 
595 /** updates best PC/MW solution if possible */
596 static inline
598  SCIP* scip, /**< SCIP data structure */
599  const GRAPH* graph, /**< graph data structure */
600  TMBASE* tmbase, /**< data */
601  SCIP_Bool* success /**< pointer to store whether a solution could be found */
602 )
603 {
604 #ifdef TM_USE_CSR_PCMW
605  const int* const result_csr = tmbase->result;
606  STP_Bool* const connected = tmbase->connected;
607  /* compute objective value w.r.t. original costs! */
608  const SCIP_Real obj = solstp_pcGetObjCsr(graph, tmbase->csr_orgcosts, result_csr, connected);
609 
610  assert(pcmwUpdateBestSol_csrInSync(scip, graph, tmbase));
611 
612  if( LT(obj, tmbase->best_obj) )
613  {
614  SCIPdebugMessage("\n improved obj=%f ", obj);
615 
616  tmbase->best_obj = obj;
617  solstp_convertCsrToGraph(scip, graph, tmbase->csr_orgcosts, result_csr, connected, tmbase->best_result);
618 
619  (*success) = TRUE;
620  }
621 
622 #else
623  const int nedges = graph_get_nEdges(graph);
624  const SCIP_Real obj = solstp_getObjBounded(graph, tmbase->result, 0.0, nedges);
625 
626  if( LT(obj, tmbase->best_obj) )
627  {
628  SCIPdebugMessage("\n improved obj=%f ", obj);
629 
630  tmbase->best_obj = obj;
631  BMScopyMemoryArray(tmbase->best_result, tmbase->result, nedges);
632  (*success) = TRUE;
633  }
634 #endif
635 }
636 
637 
638 /** submethod for SCIPStpHeurTMRun in PC or MW mode */
639 static
641  SCIP_HEURDATA* heurdata, /**< heurdata */
642  const GRAPH* graph, /**< graph data structure */
643  int maxtmruns, /**< number of TM runs */
644  int bestincstart, /**< best incumbent start vertex */
645  int* terminalperm /**< terminal permutation */
646  )
647 {
648  const int nnodes = graph_get_nNodes(graph);
649 
650  assert(maxtmruns <= graph->terms);
651 
652  if( maxtmruns > 0 && bestincstart >= 0 && bestincstart < nnodes && Is_pseudoTerm(graph->term[bestincstart])
653  && SCIPrandomGetInt(heurdata->randnumgen, 0, 2) == 1 )
654  {
655  int r;
656  for( r = 0; r < maxtmruns; r++ )
657  if( terminalperm[r] == bestincstart )
658  break;
659 
660  if( r == maxtmruns )
661  {
662  assert(maxtmruns > 1);
663  terminalperm[1] = bestincstart;
664  }
665  }
666 }
667 
668 
669 /** submethod for runPCMW */
670 static
672  SCIP* scip, /**< SCIP data structure */
673  const SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
674  int maxtmruns, /**< number of TM runs */
675  int bestincstart, /**< best incumbent start vertex */
676  GRAPH* graph, /**< graph data structure */
677  int* terminalperm /**< terminal permutation */
678  )
679 {
680  SCIP_HEURDATA* heurdata = getTMheurData(scip);
681  SCIP_Real *terminalprio; /**< terminal priority */
682  const int root = graph->source;
683  const int nnodes = graph->knots;
684  const int nterms = graph->terms;
685  int termcount = 0;
686 
687  assert(scip && heurdata && terminalperm);
688  assert(graph->extended);
689 
690  SCIP_CALL( SCIPallocBufferArray(scip, &terminalprio, nterms) );
691 
692  for( int k = 0; k < nnodes; k++ )
693  {
694  if( Is_pseudoTerm(graph->term[k]) && graph->grad[k] != 0 )
695  {
696  assert(!nodepriority || nodepriority[k] >= 0.0);
697  assert(graph->term2edge[k] < 0 || SCIPisGT(scip, graph->prize[k], 0.0));
698  terminalperm[termcount] = k;
699 
700  if( nodepriority == NULL )
701  terminalprio[termcount++] = -SCIPrandomGetReal(heurdata->randnumgen, 0.0, graph->prize[k]);
702  else
703  terminalprio[termcount++] = -SCIPrandomGetReal(heurdata->randnumgen, nodepriority[k] / 2.0, nodepriority[k]);
704  }
705  }
706 
707  if( graph_pc_isRootedPcMw(graph) )
708  {
709  SCIP_Real minprio = 0.0;
710 
711  for( int k = 0; k < termcount; k++ )
712  minprio = MIN(terminalprio[k], minprio);
713 
714  // todo why only marking for this case???
715  graph_pc_markOrgGraph(graph);
716 
717  graph->mark[graph->source] = TRUE;
718 
719  for( int k = 0; k < nnodes; k++ )
720  {
721  if( graph_pc_knotIsFixedTerm(graph, k) )
722  {
723  assert(graph->mark[k]);
724 
725  if( k == root )
726  terminalprio[termcount] = -FARAWAY;
727 
728  terminalperm[termcount] = k;
729  terminalprio[termcount++] = -SCIPrandomGetReal(heurdata->randnumgen, 0.0,
730  fabs(minprio) * (1.0 + (SCIP_Real) graph->grad[k] / (SCIP_Real) nnodes));
731  }
732  /* isolated vertex? */
733  else if( Is_term(graph->term[k]) && graph->grad[k] == 1 )
734  terminalprio[termcount] = FARAWAY;
735  }
736 
737  assert(nterms == termcount);
738  SCIPsortRealInt(terminalprio, terminalperm, nterms);
739  }
740  else
741  {
742  SCIPsortRealInt(terminalprio, terminalperm, nterms - 1);
743  }
744 
745  SCIPfreeBufferArray(scip, &terminalprio);
746 
747  pcmwAdaptStarts(heurdata, graph, maxtmruns, bestincstart, terminalperm);
748 
749  return SCIP_OKAY;
750 }
751 
752 
753 /** submethod for SCIPStpHeurTMRun in PC or MW mode */
754 static
756  const GRAPH* graph, /**< graph data structure */
757  const SCIP_Real* cost, /**< arc costs */
758  const SCIP_Real* costorg, /**< arc costs */
759  const SCIP_Real* costfullbiased, /**< arc costs */
760  enum PCMW_TmMode pcmwmode, /**< mode */
761  TMBASE* tmbase /**< data */
762 )
763 {
764  if( pcmwmode == pcmode_biasfull )
765  {
766  tmbase->cost = costfullbiased;
767  }
768  else if( pcmwmode == pcmode_simple )
769  {
770  assert(graph_pc_isPc(graph));
771  tmbase->cost = costorg;
772  }
773  else
774  {
775  assert(pcmwmode == pcmode_bias || pcmwmode == pcmode_fulltree);
776  tmbase->cost = cost;
777  }
778 
779  assert(tmbase->cost);
780 
781  graph_csr_chgCosts(graph, tmbase->cost, tmbase->csr);
782 }
783 
784 
785 /* compute starting vertices and number of runs */
786 static
788  SCIP* scip, /**< SCIP data structure */
789  const GRAPH* graph, /**< graph structure */
790  const int* orgstarts, /**< original start vertices */
791  SCIP_Bool startsgiven, /**< start vertices given? */
792  SCIP_Real* nodepriority, /**< nodepriority */
793  TMBASE* tmbase, /**< data */
794  int* bestp /**< pointer to best start vertex */
795  )
796 {
797  SCIP_HEURDATA* heurdata = getTMheurData(scip);
798  int runs = tmbase->nruns;
799  const int root = graph->source;
800  const int nnodes = graph->knots;
801  const int nterms = graph->terms;
802  const SCIP_Real* cost = tmbase->cost;
803  int* const start = tmbase->startnodes;
804  int* const dijkedge = tmbase->nodes_pred;
805  SCIP_Real* const dijkdist = tmbase->nodes_dist;
806 
807  /* compute number of iterations and starting points for SPH */
808  if( graph_pc_isPcMw(graph) )
809  {
810  if( runs > (nterms - 1) && !graph_pc_isRootedPcMw(graph) )
811  runs = nterms - 1;
812  else if( runs > (nterms) && graph_pc_isRootedPcMw(graph) )
813  runs = nterms;
814  }
815  else if( graph->stp_type == STP_NWPTSPG )
816  {
817  int count = 0;
818  const int shift = SCIPrandomGetInt(heurdata->randnumgen, 0, nnodes);
819 
820  assert(!startsgiven);
821 
822  start[count++] = graph->source;
823 
824  /* add terminals */
825  for( int k = 0; k < nnodes && count < runs; k++ )
826  {
827  const int v = (k + shift) % nnodes;
828  if( !Is_term(graph->term[v]) || graph_knotIsNWLeaf(graph, v) )
829  continue;
830  start[count++] = v;
831  }
832 
833  /* add non-terminals */
834  for( int k = 0; k < nnodes && count < runs; k++ )
835  {
836  const int v = (k + shift) % nnodes;
837  if( Is_term(graph->term[v]) )
838  continue;
839  start[count++] = v;
840  }
841  runs = count;
842  }
843  else if( startsgiven )
844  {
845  for( int k = 0; k < MIN(runs, nnodes); k++ )
846  start[k] = orgstarts[k];
847  }
848  else if( runs < nnodes || graph->stp_type == STP_DHCSTP )
849  {
850  int r = 0;
851  int* perm;
852 
853  if( *bestp < 0 )
854  {
855  *bestp = root;
856  }
857  else
858  {
859  const int randint = SCIPrandomGetInt(heurdata->randnumgen, 0, 2);
860  if( randint == 0 )
861  *bestp = -1;
862  else if( randint == 1 )
863  *bestp = root;
864  }
865 
866  if( graph->stp_type == STP_DHCSTP )
867  graph_path_execX(scip, graph, root, cost, dijkdist, dijkedge);
868 
869  SCIP_CALL( SCIPallocBufferArray(scip, &perm, nnodes) );
870 
871  /* are there no nodes are to be prioritized a priori? */
872  if( nodepriority == NULL )
873  {
874  for( int k = 0; k < nnodes; k++ )
875  perm[k] = k;
876  SCIPrandomPermuteIntArray(heurdata->randnumgen, perm, 0, nnodes);
877 
878  /* use terminals (randomly permutated) as starting points for TM heuristic */
879  for( int k = 0; k < nnodes; k++ )
880  {
881  if( r >= runs || r >= nterms )
882  break;
883 
884  if( Is_term(graph->term[perm[k]]) )
885  start[r++] = perm[k];
886  }
887 
888  /* fill empty slots */
889  for( int k = 0; k < nnodes && r < runs; k++ )
890  {
891  if( graph->stp_type == STP_DHCSTP )
892  {
893  assert(dijkdist != NULL);
894  if( SCIPisGE(scip, dijkdist[perm[k]], BLOCKED) )
895  continue;
896  }
897  if( !Is_term(graph->term[perm[k]]) && graph->mark[k] )
898  start[r++] = perm[k];
899  }
900  }
901  else
902  {
903  SCIP_Real max = 0.0;
904  const int bbound = runs - runs / 3;
905 
906  for( int k = 0; k < nnodes; k++ )
907  {
908  perm[k] = k;
909  if( SCIPisLT(scip, max, nodepriority[k]) && Is_term(graph->term[k]) )
910  max = nodepriority[k];
911  }
912  for( int k = 0; k < nnodes; k++ )
913  {
914  if( Is_term(graph->term[k]) )
915  nodepriority[k] += SCIPrandomGetReal(heurdata->randnumgen, 0.0, max);
916  else if( SCIPisLE(scip, 1.0, nodepriority[k]) )
917  nodepriority[k] = nodepriority[k] * SCIPrandomGetReal(heurdata->randnumgen, 1.0, 2.0);
918  }
919 
920  SCIPsortRealInt(nodepriority, perm, nnodes);
921 
922  for( int k = nnodes - 1; k >= 0; k-- )
923  {
924  if( r >= nterms || r >= bbound )
925  break;
926 
927  if( Is_term(graph->term[perm[k]]) )
928  {
929  start[r++] = perm[k];
930  perm[k] = -1;
931  }
932  }
933 
934  /* fill empty slots */
935  for( int k = nnodes - 1; k >= 0 && r < runs; k-- )
936  {
937  if( perm[k] == -1 )
938  continue;
939  if( graph->stp_type == STP_DHCSTP )
940  {
941  assert(dijkdist != NULL);
942  if( SCIPisGE(scip, dijkdist[perm[k]], BLOCKED) )
943  continue;
944  }
945  if( graph->mark[k] )
946  start[r++] = perm[k];
947  }
948  }
949  /* not all slots filled? */
950  if( r < runs )
951  runs = r;
952 
953  if( *bestp >= 0 )
954  {
955  /* check whether we have a already selected the best starting node */
956  for( r = 0; r < runs; r++ )
957  if( start[r] == *bestp )
958  break;
959 
960  /* no, we still have to */
961  if( r == runs && runs > 0 )
962  start[(int) heurdata->nexecs % runs] = *bestp;
963  }
964 
965  SCIPfreeBufferArray(scip, &perm);
966  } /* runs < nnodes || STP_DHCSTP */
967  else
968  {
969  runs = nnodes;
970  for( int k = 0; k < nnodes; k++ )
971  start[k] = k;
972  } /* runs > nnodes */
973 
974  tmbase->nruns = runs;
975 
976  return SCIP_OKAY;
977 }
978 
979 
980 #ifdef TM_USE_CSR
981 /** set terminals */
982 static inline
984  SCIP* scip, /**< SCIP data structure */
985  const int* soledge, /**< solution edges */
986  GRAPH* g, /**< graph structure (in/out) */
987  int* solnodes_degree /**< degree in solution (out) */
988 )
989 {
990  const int nnodes = graph_get_nNodes(g);
991  const int nedges = graph_get_nEdges(g);
992 
993  assert(solnodes_degree);
994  assert(solstp_isValid(scip, g, soledge));
995 
996  for( int i = 0; i < nnodes; i++ )
997  solnodes_degree[i] = 0;
998 
999  for( int e = 0; e < nedges; e++ )
1000  {
1001  if( soledge[e] == CONNECT )
1002  {
1003  solnodes_degree[g->tail[e]]++;
1004  solnodes_degree[g->head[e]]++;
1005  }
1006  }
1007 
1008  for( int i = 0; i < nnodes; i++ )
1009  {
1010  if( solnodes_degree[i] >= 3 && !Is_term(g->term[i]) )
1011  {
1012  solnodes_degree[i] *= -1;
1013  graph_knot_chg(g, i, STP_TERM);
1014 
1015  SCIPdebugMessage("make term: %d \n", i);
1016  }
1017  }
1018 }
1019 
1020 /** reset terminals */
1021 static inline
1023  const int* solnodes_degree, /**< degree in solution (in) */
1024  GRAPH* g /**< graph structure */
1025 )
1026 {
1027  const int nnodes = graph_get_nNodes(g);
1028  assert(solnodes_degree);
1029 
1030  for( int i = 0; i < nnodes; i++ )
1031  {
1032  if( solnodes_degree[i] < 0 )
1033  {
1034  assert(-solnodes_degree[i] <= g->grad[i]);
1035  assert(Is_term(g->term[i]));
1036 
1038 
1039  SCIPdebugMessage("reset term: %d \n", i);
1040  }
1041  }
1042 }
1043 
1044 
1045 /** CSR based shortest paths heuristic */
1046 static inline
1048  SCIP* scip, /**< SCIP data structure */
1049  const GRAPH* g, /**< graph structure */
1050  int startnode, /**< start vertex*/
1051  TMBASE* tmbase /**< (in/out) */
1052 )
1053 {
1054  int* RESTRICT result = tmbase->result;
1055  SPATHS spaths = { .csr = tmbase->csr, .csr_orgcosts = tmbase->csr_orgcosts, .nodes_dist = tmbase->nodes_dist,
1056  .nodes_pred = tmbase->nodes_pred, .dheap = tmbase->dheap, .nodes_isConnected = tmbase->connected,
1057  .edgecost_zeroOffset = getTmEdgeCostZeroOffset(scip, g) };
1058 
1059  assert(g->stp_type != STP_DHCSTP);
1060 
1061  if( graph_typeIsDirected(g) )
1062  shortestpath_computeSteinerTreeDirected(scip, g, startnode, &spaths);
1063  else if( tmbase->sdprofit1st )
1064  shortestpath_computeSteinerTreeBiased(g, tmbase->sdprofit1st, startnode, &spaths);
1065  else
1066  shortestpath_computeSteinerTree(g, startnode, &spaths);
1067 
1068  SCIP_CALL( solstp_pruneFromTmHeur_csr(scip, g, &spaths, result));
1069 
1070  return SCIP_OKAY;
1071 }
1072 
1073 
1074 /** CSR based shortest paths heuristic that exploits key nodes of best solution */
1075 static inline
1077  SCIP* scip, /**< SCIP data structure */
1078  GRAPH* g, /**< graph structure */
1079  int startnode, /**< start vertex*/
1080  TMBASE* tmbase /**< (in/out) */
1081 )
1082 {
1083  SPATHS spaths = { .csr = tmbase->csr, .csr_orgcosts = tmbase->csr_orgcosts, .nodes_dist = tmbase->nodes_dist,
1084  .nodes_pred = tmbase->nodes_pred, .dheap = tmbase->dheap, .nodes_isConnected = tmbase->connected,
1085  .edgecost_zeroOffset = getTmEdgeCostZeroOffset(scip, g) };
1086  int* solnodes_degree;
1087 #ifndef NDEBUG
1088  const int nterms = g->terms;
1089 #endif
1090 
1091  assert(graph_typeIsSpgLike(g));
1092  assert(g->stp_type != STP_DHCSTP);
1093 
1094  SCIP_CALL( SCIPallocBufferArray(scip, &solnodes_degree, g->knots) );
1095  keyNodesSetTerms(scip, tmbase->best_result, g, solnodes_degree);
1096 
1097  if( tmbase->sdprofit1st )
1098  shortestpath_computeSteinerTreeBiased(g, tmbase->sdprofit1st, startnode, &spaths);
1099  else
1100  shortestpath_computeSteinerTree(g, startnode, &spaths);
1101 
1102  keyNodesResetTerms(solnodes_degree, g);
1103  SCIPfreeBuffer(scip, &solnodes_degree);
1104 
1105  SCIP_CALL( solstp_pruneFromTmHeur_csr(scip, g, &spaths, tmbase->result));
1106 
1107  assert(nterms == g->terms);
1108 
1109  return SCIP_OKAY;
1110 }
1111 #endif
1112 
1113 
1114 /** Dijkstra based shortest paths heuristic */
1115 static inline
1117  SCIP* scip, /**< SCIP data structure */
1118  GRAPH* g, /**< graph structure */
1119  int start, /**< start vertex */
1120  TMBASE* tmbase /**< (in/out) */
1121  )
1122 {
1123  const SCIP_Real* cost = tmbase->cost;
1124  int* dijkedge = tmbase->nodes_pred;
1125  SCIP_Real* dijkdist = tmbase->nodes_dist;
1126  int* RESTRICT result = tmbase->result;
1127 
1128  assert(!graph_pc_isPcMw(g));
1129 
1130  graph_mark(g);
1131 
1132  graph_path_st(g, cost, dijkdist, dijkedge, start, tmbase->connected);
1133 
1134  /* cost will actually only be used for hop-constrained problem */
1135  SCIP_CALL( solstp_pruneFromTmHeur(scip, g, cost, result, tmbase->connected) );
1136 
1137  return SCIP_OKAY;
1138 }
1139 
1140 
1141 /** Dijkstra based shortest paths heuristic for PCSTP and MWCSP */
1142 static
1144  SCIP* scip, /**< SCIP data structure */
1145  GRAPH* g, /**< graph structure */
1146  const SCIP_Real* cost_org, /**< (un-biased) edge costs, only needed for PC/RPC */
1147  const SCIP_Real* prize, /**< (possibly biased) vertex prizes */
1148  int start, /**< start vertex */
1149  TMBASE* tmbase, /**< data */
1150  SCIP_Bool* solfound /**< solution found? (OUT) */
1151  )
1152 {
1153  assert(g->stp_type == STP_BRMWCSP);
1154  *solfound = TRUE;
1155 
1156  SCIP_CALL( graph_path_st_brmwcs(scip, g, prize, tmbase->nodes_dist, tmbase->nodes_pred, start,
1157  tmbase->connected, solfound) );
1158 
1159  if( *solfound )
1160  SCIP_CALL( solstp_pruneFromTmHeur(scip, g, cost_org, tmbase->result, tmbase->connected));
1161 
1162  return SCIP_OKAY;
1163 }
1164 
1165 
1166 /** Dijkstra based shortest paths heuristic for PCSTP and MWCSP */
1167 static
1169  SCIP* scip, /**< SCIP data structure */
1170  GRAPH* g, /**< graph structure */
1171  const SCIP_Real* cost_org, /**< (un-biased) edge costs, only needed for PC/RPC */
1172  const SCIP_Real* prize, /**< (possibly biased) vertex prizes */
1173  SCIP_Bool costsAreBiased, /**< biased? */
1174  int start, /**< start vertex */
1175  SPATHSPC* sppc, /**< PC/MW shortest path data */
1176  TMBASE* tmbase /**< data */
1177  )
1178 {
1179 #ifdef TM_USE_CSR_PCMW
1180  SPATHS spaths = { .csr = tmbase->csr, .csr_orgcosts = tmbase->csr_orgcosts, .nodes_dist = tmbase->nodes_dist,
1181  .nodes_pred = tmbase->nodes_pred, .dheap = tmbase->dheap, .nodes_isConnected = tmbase->connected,
1182  .edgecost_zeroOffset = getTmEdgeCostZeroOffset(scip, g) };
1183 
1184  assert(graph_pc_isPcMw(g));
1185 
1186  if( g->stp_type == STP_RPCSPG || g->stp_type == STP_RMWCSP )
1187  {
1188  shortestpath_computeSteinerTreeRpcMw(g, start, prize, sppc, &spaths);
1189  }
1190  else
1191  {
1192  shortestpath_computeSteinerTreePcMw(g, start, prize, costsAreBiased, sppc, &spaths);
1193  }
1194 
1195  SCIP_CALL( solstp_pruneFromTmHeur_csr(scip, g, &spaths, tmbase->result));
1196 
1197 #else
1198  assert(graph_pc_isPcMw(g));
1199 
1200  if( g->stp_type == STP_RPCSPG || g->stp_type == STP_RMWCSP )
1201  {
1203  tmbase->cost, prize, tmbase->nodes_dist, tmbase->nodes_pred, start, tmbase->connected);
1204  }
1205  else
1206  {
1208  tmbase->cost, prize, costsAreBiased, tmbase->nodes_dist, tmbase->nodes_pred, start, tmbase->connected);
1209  }
1210 
1211  SCIP_CALL( solstp_pruneFromTmHeur(scip, g, cost_org, tmbase->result, tmbase->connected));
1212 
1213 #endif
1214 
1215 
1216  return SCIP_OKAY;
1217 }
1218 
1219 
1220 
1221 /** Dijkstra based shortest paths heuristic for PCSTP and MWCSP that computes tree spanning all positive
1222  * vertex weights and subsequently prunes this tree */
1223 static
1225  SCIP* scip, /**< SCIP data structure */
1226  GRAPH* g, /**< graph structure */
1227  const SCIP_Real* cost_org, /**< (un-biased) edge costs, only needed for PC/RPC */
1228  int start, /**< start vertex */
1229  TMBASE* tmbase /**< data */
1230  )
1231 {
1232 #ifdef TM_USE_CSR_PCMW
1233  SPATHS spaths = { .csr = tmbase->csr, .csr_orgcosts = tmbase->csr_orgcosts, .nodes_dist = tmbase->nodes_dist,
1234  .nodes_pred = tmbase->nodes_pred,
1235  .dheap = tmbase->dheap, .nodes_isConnected = tmbase->connected,
1236  .edgecost_zeroOffset = getTmEdgeCostZeroOffset(scip, g) };
1237 
1238  shortestpath_computeSteinerTreePcMwFull(g, start, &spaths);
1239 
1240  SCIP_CALL( solstp_pruneFromTmHeur_csr(scip, g, &spaths, tmbase->result));
1241 #else
1242  graph_path_st_pcmw_full(g, tmbase->cost, tmbase->nodes_dist, tmbase->nodes_pred, start, tmbase->connected);
1243  SCIP_CALL( solstp_pruneFromTmHeur(scip, g, cost_org, tmbase->result, tmbase->connected) );
1244 #endif
1245 
1246  return SCIP_OKAY;
1247 }
1248 
1249 
1250 /** shortest paths based heuristic
1251  * NOTE: DEPRECATED */
1252 static
1254  SCIP* scip, /**< SCIP data structure */
1255  const GRAPH* g, /**< graph structure */
1256  const SCIP_Real* cost, /**< edge costs */
1257  const SCIP_Real* costrev, /**< reversed edge costs */
1258  int start, /**< start vertex */
1259  int* result, /**< solution array (on edges) */
1260  TMALLSP* tmallsp, /**< all SP */
1261  STP_Bool* connected, /**< array marking all solution vertices */
1262  SCIP_RANDNUMGEN* randnumgen /**< random number generator */
1263  )
1264 {
1265  SCIP_Real min;
1266  SCIP_Bool directed = (g->stp_type == STP_SAP || g->stp_type == STP_DHCSTP || g->stp_type == STP_NWPTSPG);
1267  int* perm = NULL;
1268  int* cluster = NULL;
1269  int k;
1270  int e;
1271  int j;
1272  int z;
1273  int old;
1274  int root;
1275  int csize;
1276  int newval;
1277  int nnodes;
1278  int nterms;
1279  SCIP_Real** pathdist = tmallsp->pathdist;
1280  int** pathedge = tmallsp->pathedge;
1281 
1282  assert(scip != NULL);
1283  assert(g != NULL);
1284  assert(result != NULL);
1285  assert(connected != NULL);
1286  assert(cost != NULL);
1287  assert(costrev != NULL);
1288  assert(pathdist != NULL);
1289  assert(pathedge != NULL);
1290 
1291  root = g->source;
1292  csize = 0;
1293  nnodes = g->knots;
1294 
1295  assert(0 <= start && start < nnodes);
1296 
1297  SCIPdebugMessage("TM heuristic Start=%d \n", start);
1298 
1299  SCIP_CALL( SCIPallocBufferArray(scip, &cluster, nnodes) );
1300  SCIP_CALL( SCIPallocBufferArray(scip, &perm, g->terms) );
1301 
1302  cluster[csize++] = start;
1303 
1304  for( e = 0; e < g->edges; e++ )
1305  result[e] = UNKNOWN;
1306 
1307  nterms = 0;
1308  for( int i = 0; i < nnodes; i++ )
1309  {
1310  g->mark[i] = (g->grad[i] > 0);
1311  connected[i] = FALSE;
1312  if( Is_term(g->term[i]) )
1313  perm[nterms++] = i;
1314  }
1315 
1316  assert(nterms == g->terms);
1317 
1318  connected[start] = TRUE;
1319 
1320  SCIPrandomPermuteIntArray(randnumgen, perm, 0, g->terms - 1);
1321 
1322  assert(graph_valid(scip, g));
1323 
1324  /* CONSTCOND */
1325  for( ;; )
1326  {
1327  /* Find a terminal with minimal distance to current ST */
1328  min = FARAWAY;
1329  old = -1;
1330  newval = -1;
1331 
1332  /* time limit exceeded? */
1333  if( SCIPisStopped(scip) )
1334  break;
1335 
1336  z = SCIPrandomGetInt(randnumgen, 0, nnodes - 1);
1337 
1338  /* find shortest path from current tree to unconnected terminal */
1339  for( int q = nterms - 1; q >= 0; --q )
1340  {
1341  const int term = perm[q];
1342  if( connected[term] || !g->mark[term] || (directed && !connected[root] && term != root) )
1343  continue;
1344 
1345  assert(Is_term(g->term[term]));
1346 
1347  for( k = csize - 1; k >= 0; k-- )
1348  {
1349  j = cluster[(k + z) % csize];
1350  assert(term != j);
1351  assert(connected[j]);
1352 
1353  if( LT(pathdist[term][j], min) )
1354  {
1355  min = pathdist[term][j];
1356  newval = term;
1357  old = j;
1358  }
1359  }
1360  }
1361 
1362  /* no new path found? */
1363  if( newval == -1 )
1364  break;
1365 
1366  /* mark the new path */
1367  assert(old > -1);
1368  assert(newval > -1);
1369  assert(pathdist[newval] != NULL);
1370  assert(pathdist[newval][old] < FARAWAY);
1371  assert(g->term[newval] == 0);
1372  assert(!connected[newval]);
1373  assert(connected[old]);
1374 
1375  /* start from current tree */
1376  k = old;
1377 
1378  while( k != newval )
1379  {
1380  e = pathedge[newval][k];
1381  k = g->tail[e];
1382  if (!connected[k])
1383  {
1384  connected[k] = TRUE;
1385  cluster[csize++] = k;
1386  }
1387  }
1388  }
1389 
1390  for( int i = 0; i < nnodes; i++ )
1391  {
1392  if( Is_term(g->term[i]) )
1393  assert(connected[i]);
1394  }
1395 
1396  /* prune the tree */
1397  SCIP_CALL( solstp_pruneFromTmHeur(scip, g, cost, result, connected) );
1398 
1399  SCIPfreeBufferArrayNull(scip, &perm);
1400  SCIPfreeBufferArray(scip, &cluster);
1401 
1402  return SCIP_OKAY;
1403 }
1404 
1405 /** cumputes single node Steiner tree; only for rooted PC/MW */
1406 static inline
1408  const GRAPH* graph, /**< graph data structure */
1409  int node, /**< the nodes */
1410  TMBASE* tmbase, /**< data */
1411  SCIP_Bool* success /**< telling name */
1412 )
1413 {
1414  assert(graph_pc_isPcMw(graph));
1415 
1416  /* only root remaining? */
1417  if( node == graph->source )
1418  {
1419  const int nedges = graph_get_nEdges(graph);
1420  int *RESTRICT best_result = tmbase->best_result;
1421  assert(graph_pc_isRootedPcMw(graph));
1422 
1423  for( int e = 0; e < nedges; e++ )
1424  best_result[e] = UNKNOWN;
1425 
1426  (*success) = TRUE;
1427  }
1428 }
1429 
1430 
1431 /** heuristic for degree constrained STPs
1432  * NOTE: DEPRECATED */
1433 static
1435  SCIP* scip, /**< SCIP data structure */
1436  const GRAPH* g, /**< graph data structure */
1437  const SCIP_Real* cost, /**< edge costs */
1438  const SCIP_Real* costrev, /**< reversed edge costs */
1439  int start, /**< start vertex */
1440  int* result, /**< array to indicate whether an edge is in the solution */
1441  TMALLSP* tmallsp, /**< all SP */
1442  SCIP_RANDNUMGEN* randnumgen, /**< random number generator */
1443  STP_Bool* connected, /**< array to indicate whether a vertex is in the solution */
1444  STP_Bool* solfound /**< pointer to store whether a solution has been found */
1445  )
1446 {
1447  SCIP_Real min;
1448  int csize = 0;
1449  int k;
1450  int e;
1451  int l;
1452  int i;
1453  int j;
1454  int t;
1455  int u;
1456  int z;
1457  int n;
1458  int old;
1459  int tldegcount;
1460  int degcount;
1461  int mindegsum;
1462  int degmax;
1463  int newval;
1464  int nnodes;
1465  int nterms;
1466  int termcount;
1467  int* degs;
1468  int* maxdegs;
1469  int* cluster;
1470  int* perm;
1471  SCIP_Real** pathdist = tmallsp->pathdist;
1472  int** pathedge = tmallsp->pathedge;
1473 
1474  assert(scip != NULL);
1475  assert(g != NULL);
1476  assert(g->maxdeg != NULL);
1477  assert(result != NULL);
1478  assert(connected != NULL);
1479  assert(cost != NULL);
1480  assert(costrev != NULL);
1481  assert(pathdist != NULL);
1482  assert(pathedge != NULL);
1483 
1484  z = 0;
1485  nterms = g->terms;
1486  nnodes = g->knots;
1487  mindegsum = 2;
1488  maxdegs = g->maxdeg;
1489 
1490  SCIPdebugMessage("Heuristic: Start=%d \n ", start);
1491 
1492  SCIP_CALL( SCIPallocBufferArray(scip, &degs, nnodes) );
1493  SCIP_CALL( SCIPallocBufferArray(scip, &cluster, nnodes) );
1494  SCIP_CALL( SCIPallocBufferArray(scip, &perm, nnodes) );
1495 
1496  cluster[csize++] = start;
1497 
1498  for( i = 0; i < nnodes; i++ )
1499  {
1500  degs[i] = 0;
1501  g->mark[i] = (g->grad[i] > 0);
1502  connected[i] = FALSE;
1503  perm[i] = i;
1504  }
1505 
1506  for( e = 0; e < g->edges; e++ )
1507  {
1508  assert(SCIPisGT(scip, cost[e], 0.0));
1509  result[e] = UNKNOWN;
1510  }
1511  connected[start] = TRUE;
1512  tldegcount = MIN(g->grad[start], maxdegs[start]);
1513  SCIPrandomPermuteIntArray(randnumgen, perm, 0, nnodes - 1);
1514 
1515  if( Is_term(g->term[start]) )
1516  termcount = 1;
1517  else
1518  termcount = 0;
1519 
1520  for( n = 0; n < nnodes; n++ )
1521  {
1522  /* Find a terminal with minimal distance to the current ST */
1523  min = FARAWAY - 1;
1524  /* is the free degree sum at most one and are we not connecting the last terminal? */
1525  if( tldegcount <= 1 && termcount < nterms - 1)
1526  degmax = 1;
1527  else
1528  degmax = 0;
1529  old = -1;
1530  newval = -1;
1531  for( t = 0; t < nnodes; t++ )
1532  {
1533  i = perm[t];
1534  if( !Is_term(g->term[i]) || connected[i] || g->grad[i] == 0 )
1535  continue;
1536 
1537  z = SCIPrandomGetInt(randnumgen, 0, nnodes - 1);
1538 
1539  for( k = 0; k < csize; k++ )
1540  {
1541  j = cluster[(k + z) % csize];
1542  assert(i != j);
1543  assert(connected[j]);
1544 
1545  if( SCIPisLE(scip, pathdist[i][j], min) && degs[j] < maxdegs[j])
1546  {
1547  u = j;
1548  degcount = 1;
1549  while( u != i )
1550  {
1551  u = g->tail[pathedge[i][u]];
1552  if( !connected[u] )
1553  {
1554  if( (MIN(g->grad[u], maxdegs[u]) < 2 || Is_term(g->term[u])) && u != i )
1555  {
1556  degcount = -2;
1557  break;
1558  }
1559  degcount += MIN(g->grad[u] - 2, maxdegs[u] - 2);
1560  }
1561  else
1562  {
1563  assert(u != i);
1564  l = g->tail[pathedge[i][u]];
1565  if( !connected[l] && degs[u] >= maxdegs[u] )
1566  {
1567  degcount = -2;
1568  break;
1569  }
1570  }
1571  }
1572  if( degcount >= degmax || (degcount >= mindegsum && SCIPisLT(scip, pathdist[i][j], min)) )
1573  {
1574  degmax = degcount;
1575  min = pathdist[i][j];
1576  newval = i;
1577  old = j;
1578  }
1579  }
1580  }
1581  }
1582 
1583  if( newval == -1 )
1584  {
1585  j = UNKNOWN;
1586  for( k = 0; k < csize; k++ )
1587  {
1588  j = cluster[(k + z) % csize];
1589  if( degs[j] < maxdegs[j] )
1590  break;
1591  }
1592  if( j != UNKNOWN )
1593  {
1594  assert(k != csize);
1595 
1596  min = FARAWAY + 1;
1597  newval = UNKNOWN;
1598  for( e = g->outbeg[j]; e != EAT_LAST; e = g->oeat[e] )
1599  {
1600  u = g->head[e];
1601  if( !Is_term(g->term[u]) && !connected[u] && SCIPisGE(scip, min, cost[e]) )
1602  {
1603  min = cost[e];
1604  k = e;
1605  newval = u;
1606  }
1607  }
1608  if( newval != UNKNOWN )
1609  {
1610  result[flipedge(k)] = CONNECT;
1611  degs[newval]++;
1612  degs[j]++;
1613  connected[newval] = TRUE;
1614  cluster[csize++] = newval;
1615  tldegcount += MIN(maxdegs[newval], g->grad[newval]) - 2;
1616  continue;
1617  }
1618 
1619  }
1620  }
1621  tldegcount += degmax - 1;
1622  /* break? */
1623  if( newval == -1 )
1624  break;
1625  /* Weg setzten
1626  */
1627  assert(old > -1);
1628  assert(newval > -1);
1629  assert(pathdist[newval] != NULL);
1630  assert(g->term[newval] == 0);
1631  assert(!connected[newval]);
1632  assert(connected[old]);
1633 
1634  /* mark new tree nodes/edges */
1635  k = old;
1636  if( Is_term(g->term[newval]) )
1637  termcount++;
1638 
1639  while(k != newval)
1640  {
1641  e = pathedge[newval][k];
1642  u = k;
1643  k = g->tail[e];
1644 
1645  if( !connected[k])
1646  {
1647  result[flipedge(e)] = CONNECT;
1648  degs[u]++;
1649  degs[k]++;
1650  connected[k] = TRUE;
1651  cluster[csize++] = k;
1652  if( k != newval )
1653  assert(!Is_term(g->term[k]));
1654  }
1655  }
1656  if( termcount == nterms )
1657  break;
1658  assert(degs[newval] == 1);
1659  }
1660 
1661  *solfound = TRUE;
1662 
1663  for( i = 0; i < nnodes; i++ )
1664  {
1665  if( Is_term(g->term[i]) && !connected[i] )
1666  {
1667  *solfound = FALSE;
1668  SCIPdebugMessage("invalid solution, not connected: %d \n", i);
1669  break;
1670  }
1671  }
1672 
1673  if( *solfound )
1674  {
1675  /* prune the solution */
1676  SCIP_CALL( SCIPStpHeurTMBuildTreeDc(scip, g, result, connected) );
1677 
1678  for( t = 0; t < nnodes; t++ )
1679  {
1680  if( degs[t] > maxdegs[t] )
1681  {
1682  *solfound = FALSE;
1683  SCIPdebugMessage("invalid solution, wrong degree: %d \n", i);
1684  break;
1685  }
1686  }
1687  }
1688  SCIPfreeBufferArray(scip, &perm);
1689  SCIPfreeBufferArray(scip, &cluster);
1690  SCIPfreeBufferArray(scip, &degs);
1691  return SCIP_OKAY;
1692 }
1693 
1694 /** Voronoi based shortest path heuristic.
1695  * NOTE: DEPRECATED */
1696 static
1698  SCIP* scip, /**< SCIP data structure */
1699  const GRAPH* g, /**< graph structure */
1700  const SCIP_Real* cost, /**< edge costs */
1701  const SCIP_Real* costrev, /**< reversed edge costs */
1702  int start, /**< start vertex */
1703  STP_Bool firstrun, /**< method called for the first time? (during one heuristic round) */
1704  TMVNOI* tmvnoi, /**< TM data */
1705  int* result, /**< array to indicate whether an edge is in the solution */
1706  STP_Bool* connected /**< array to indicate whether a vertex is in the solution */
1707  )
1708 {
1709  int *vcount;
1710  int k;
1711  int i;
1712  int j;
1713  int best;
1714  int term;
1715  int count;
1716  int nnodes;
1717  int nterms;
1718  SCIP_Real **node_dist = tmvnoi->node_dist;
1719  SCIP_PQUEUE *pqueue = tmvnoi->pqueue;
1720  GNODE **gnodearr = tmvnoi->gnodearr;
1721  int *nodenterms = tmvnoi->nodenterms;
1722  int **node_base = tmvnoi->node_base;
1723  int **node_edge = tmvnoi->node_edge;
1724 
1725  assert(scip != NULL);
1726  assert(g != NULL);
1727  assert(result != NULL);
1728  assert(connected != NULL);
1729  assert(cost != NULL);
1730  assert(costrev != NULL);
1731  nnodes = g->knots;
1732  nterms = g->terms;
1733 
1734  SCIP_CALL( SCIPallocBufferArray(scip, &vcount, nnodes) );
1735 
1736  SCIPdebugMessage("TM_Polzin Heuristic: Start=%5d ", start);
1737 
1738  /* if the heuristic is called for the first time several data structures have to be set up */
1739  if( firstrun )
1740  {
1741  PATH* vnoi;
1742  SCIP_Real* vcost;
1743  int old;
1744  int oedge;
1745  int root = g->source;
1746  int ntovisit;
1747  int nneighbnodes;
1748  int nneighbterms;
1749  int nreachednodes;
1750  int* state;
1751  int* vbase;
1752  int* terms;
1753  int* tovisit;
1754  int* reachednodes;
1755  STP_Bool* termsmark;
1756  STP_Bool* visited;
1757  int e;
1758  /* PHASE I: */
1759  for( i = 0; i < nnodes; i++ )
1760  g->mark[i] = (g->grad[i] > 0);
1761 
1762  /* allocate memory needed in PHASE I */
1763  SCIP_CALL( SCIPallocBufferArray(scip, &terms, nterms) );
1764  SCIP_CALL( SCIPallocBufferArray(scip, &termsmark, nnodes) );
1765  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, nnodes) );
1766  SCIP_CALL( SCIPallocBufferArray(scip, &visited, nnodes) );
1767  SCIP_CALL( SCIPallocBufferArray(scip, &reachednodes, nnodes) );
1768  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, nnodes) );
1769  SCIP_CALL( SCIPallocBufferArray(scip, &tovisit, nnodes) );
1770  SCIP_CALL( SCIPallocBufferArray(scip, &vcost, nnodes) );
1771 
1772  j = 0;
1773  for( i = 0; i < nnodes; i++ )
1774  {
1775  visited[i] = FALSE;
1776  if( Is_term(g->term[i]) )
1777  {
1778  termsmark[i] = TRUE;
1779  terms[j++] = i;
1780  }
1781  else
1782  {
1783  termsmark[i] = FALSE;
1784  }
1785  }
1786 
1787  for( e = 0; e < g->edges; e++)
1788  {
1789  assert(SCIPisGE(scip, cost[e], 0.0));
1790  assert(SCIPisGE(scip, costrev[e], 0.0));
1791  }
1792 
1793  assert(j == nterms);
1794  graph_voronoi(g, cost, costrev, termsmark, vbase, vnoi);
1795  state = g->path_state;
1796 
1797  for( i = 0; i < nnodes; i++ )
1798  if( Is_term(g->term[i]) )
1799  assert(vbase[i] == i);
1800 
1801  for( k = 0; k < nnodes; k++ )
1802  {
1803  connected[k] = FALSE;
1804  vcount[k] = 0;
1805  gnodearr[k]->number = k;
1806  if( !Is_term(g->term[k]) )
1807  {
1808  node_dist[k][0] = vnoi[k].dist;
1809  node_edge[k][0] = vnoi[k].edge;
1810  node_base[k][0] = vbase[k];
1811  nodenterms[k] = 1;
1812  }
1813  else
1814  {
1815  nodenterms[k] = 0;
1816  node_edge[k][0] = UNKNOWN;
1817  termsmark[k] = FALSE;
1818  }
1819  state[k] = UNKNOWN;
1820  vcost[k] = vnoi[k].dist;
1821  vnoi[k].dist = FARAWAY;
1822  }
1823 
1824  /* for each terminal: extend the voronoi regions until all neighbouring terminals have been visited */
1825  for( i = 0; i < nterms; i++ )
1826  {
1827  term = terms[i];
1828  nneighbterms = 0;
1829  nneighbnodes = 0;
1830  nreachednodes = 0;
1831  for( k = 0; k < nnodes; k++ )
1832  assert(termsmark[k] == FALSE);
1833  /* DFS (starting from terminal i) until the entire voronoi region has been visited */
1834  tovisit[0] = term;
1835  ntovisit = 1;
1836  visited[term] = TRUE;
1837  state[term] = CONNECT;
1838  while( ntovisit > 0 )
1839  {
1840  /* iterate all incident edges */
1841  old = tovisit[--ntovisit];
1842 
1843  for( oedge = g->outbeg[old]; oedge != EAT_LAST; oedge = g->oeat[oedge] )
1844  {
1845  k = g->head[oedge];
1846 
1847  /* is node k in the voronoi region of the i-th terminal ? */
1848  if( vbase[k] == term )
1849  {
1850  if( !visited[k] )
1851  {
1852  state[k] = CONNECT;
1853  assert(nnodes - (nneighbnodes + 1) > ntovisit);
1854  tovisit[ntovisit++] = k;
1855  visited[k] = TRUE;
1856  reachednodes[nreachednodes++] = k;
1857  }
1858  }
1859  else
1860  {
1861  if( !visited[k] )
1862  {
1863  visited[k] = TRUE;
1864  vnoi[k].dist = vcost[old] + ((vbase[k] == root)? cost[oedge] : costrev[oedge]);
1865  vnoi[k].edge = oedge;
1866 
1867  if( termsmark[vbase[k]] == FALSE )
1868  {
1869  termsmark[vbase[k]] = TRUE;
1870  nneighbterms++;
1871  }
1872  assert(nnodes - (nneighbnodes + 1) > ntovisit - 1);
1873  tovisit[nnodes - (++nneighbnodes)] = k;
1874  }
1875  else
1876  {
1877  /* if edge 'oedge' allows a shorter connection of node k, update */
1878  if( SCIPisGT(scip, vnoi[k].dist, vcost[old] + ((vbase[k] == root)? cost[oedge] : costrev[oedge])) )
1879  {
1880  vnoi[k].dist = vcost[old] + ((vbase[k] == root)? cost[oedge] : costrev[oedge]);
1881  vnoi[k].edge = oedge;
1882  }
1883  }
1884  }
1885  }
1886  }
1887 
1888  count = 0;
1889  for( j = 0; j < nneighbnodes; j++ )
1890  {
1891  assert(termsmark[vbase[tovisit[nnodes - j - 1]]]);
1892  graph_pathHeapAdd(vnoi, tovisit[nnodes - j - 1], g->path_heap, state, &count);
1893  }
1894  SCIP_CALL( graph_voronoiExtend(scip, g, ((term == root)? cost : costrev), vnoi, node_dist, node_base, node_edge, termsmark, reachednodes, &nreachednodes, nodenterms,
1895  nneighbterms, term, nneighbnodes) );
1896 
1897  reachednodes[nreachednodes++] = term;
1898 
1899  for( j = 0; j < nreachednodes; j++ )
1900  {
1901  vnoi[reachednodes[j]].dist = FARAWAY;
1902  state[reachednodes[j]] = UNKNOWN;
1903  visited[reachednodes[j]] = FALSE;
1904  }
1905 
1906  for( j = 0; j < nneighbnodes; j++ )
1907  {
1908  vnoi[tovisit[nnodes - j - 1]].dist = FARAWAY;
1909  state[tovisit[nnodes - j - 1]] = UNKNOWN;
1910  visited[tovisit[nnodes - j - 1]] = FALSE;
1911  }
1912  }
1913 
1914  /* for each node v: sort the terminal arrays according to their distance to v */
1915  for( i = 0; i < nnodes && !SCIPisStopped(scip); i++ )
1916  SCIPsortRealIntInt(node_dist[i], node_base[i], node_edge[i], nodenterms[i]);
1917 
1918  /* free memory */
1919  SCIPfreeBufferArray(scip, &vcost);
1920  SCIPfreeBufferArray(scip, &tovisit);
1921  SCIPfreeBufferArray(scip, &vbase);
1922  SCIPfreeBufferArray(scip, &reachednodes);
1923  SCIPfreeBufferArray(scip, &visited);
1924  SCIPfreeBufferArray(scip, &vnoi);
1925  SCIPfreeBufferArray(scip, &termsmark);
1926  SCIPfreeBufferArray(scip, &terms);
1927  }
1928 
1929  /* PHASE II */
1930  else
1931  {
1932  for( k = 0; k < nnodes; k++ )
1933  {
1934  connected[k] = FALSE;
1935  vcount[k] = 0;
1936  }
1937  }
1938 
1939  connected[start] = TRUE;
1940  gnodearr[start]->dist = node_dist[start][0];
1941  SCIP_CALL( SCIPpqueueInsert(pqueue, gnodearr[start]) );
1942 
1943  while( SCIPpqueueNElems(pqueue) > 0 && !SCIPisStopped(scip) )
1944  {
1945  best = ((GNODE*) SCIPpqueueRemove(pqueue))->number;
1946 
1947  term = node_base[best][vcount[best]];
1948  assert( Is_term(g->term[term]) );
1949  /* has the terminal already been connected? */
1950  if( !connected[term] )
1951  {
1952  /* connect the terminal */
1953  k = g->tail[node_edge[best][vcount[best]]];
1954  while( k != term )
1955  {
1956  j = 0;
1957 
1958  while( node_base[k][vcount[k] + j] != term )
1959  j++;
1960 
1961  assert(vcount[k] + j < nodenterms[k]);
1962 
1963  if( !connected[k] )
1964  {
1965  assert(vcount[k] == 0);
1966 
1967  connected[k] = TRUE;
1968  while( vcount[k] < nodenterms[k] && connected[node_base[k][vcount[k]]] )
1969  {
1970  vcount[k]++;
1971  j--;
1972  }
1973 
1974  if( vcount[k] < nodenterms[k] )
1975  {
1976  gnodearr[k]->dist = node_dist[k][vcount[k]];
1977  SCIP_CALL( SCIPpqueueInsert(pqueue, gnodearr[k]) );
1978  }
1979  }
1980 
1981  assert( vcount[k] + j < nodenterms[k] );
1982  assert(node_base[k][vcount[k] + j] == term);
1983  k = g->tail[node_edge[k][vcount[k] + j]];
1984  }
1985 
1986  /* finally, connected the terminal */
1987  assert( k == term );
1988  assert( !connected[k] );
1989  connected[k] = TRUE;
1990 
1991  assert( vcount[k] == 0 );
1992  while( vcount[k] < nodenterms[k] && connected[node_base[k][vcount[k]]] )
1993  {
1994  vcount[k]++;
1995  }
1996  if( vcount[k] < nodenterms[k] )
1997  {
1998  gnodearr[k]->dist = node_dist[k][vcount[k]];
1999  SCIP_CALL( SCIPpqueueInsert(pqueue, gnodearr[k]) );
2000  }
2001  }
2002 
2003  while( vcount[best] + 1 < nodenterms[best] )
2004  {
2005  if( !connected[node_base[best][++vcount[best]]] )
2006  {
2007  gnodearr[best]->dist = node_dist[best][vcount[best]];
2008  SCIP_CALL( SCIPpqueueInsert(pqueue, gnodearr[best]) );
2009  break;
2010  }
2011  }
2012  }
2013 
2014  /* prune the ST, so that all leaves are terminals */
2015  SCIP_CALL( solstp_pruneFromTmHeur(scip, g, cost, result, connected) );
2016 
2017  SCIPfreeBufferArray(scip, &vcount);
2018 
2019  return SCIP_OKAY;
2020 }
2021 
2022 
2023 /** initialize edge costs, vertex prizes, and start node priorities */
2024 static
2026  SCIP* scip, /**< SCIP data structure */
2027  SCIP_HEURDATA* heurdata, /**< heurdata */
2028  const GRAPH* graph, /**< graph data structure */
2029  SCIP_Bool* partrand, /**< use partial randomization? (OUT) */
2030  SCIP_Bool* totalrand /**< use total randomization? (OUT) */
2031 )
2032 {
2033  *partrand = FALSE;
2034  *totalrand = FALSE;
2035 
2036  if( (heurdata->nlpiterations == SCIPgetNLPIterations(scip) && SCIPrandomGetInt(heurdata->randnumgen, 0, 5) != 1)
2037  || SCIPrandomGetInt(heurdata->randnumgen, 0, 15) == 5 )
2038  *partrand = TRUE;
2039 
2040  if( !(*partrand) && (heurdata->nlpiterations == SCIPgetNLPIterations(scip)) )
2041  *totalrand = TRUE;
2042  else if( graph->stp_type == STP_DCSTP && heurdata->ncalls != 1 && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 1
2043  && (graph->maxdeg[graph->source] == 1 || SCIPrandomGetInt(heurdata->randnumgen, 0, 5) == 5) )
2044  {
2045  *totalrand = TRUE;
2046  *partrand = FALSE;
2047  }
2048 }
2049 
2050 
2051 /** initialize edge costs, vertex prizes, and start node priorities */
2052 static
2054  SCIP* scip, /**< SCIP data structure */
2055  SCIP_HEURDATA* heurdata, /**< heurdata */
2056  SCIP_VAR** vars, /**< variables */
2057  const GRAPH* graph, /**< graph data structure */
2058  SCIP_Real randupper, /**< random value bound */
2059  SCIP_Real randlower, /**< random value bound */
2060  const SCIP_Real* xval, /**< xval */
2061  SCIP_Real* RESTRICT nodepriority, /**< node priority (uninitialized) */
2062  SCIP_Real* RESTRICT prize, /**< prize (uninitialized) or NULL */
2063  SCIP_Real* RESTRICT cost /**< arc costs (uninitialized) */
2064 )
2065 {
2066  const SCIP_Real* const gCost = graph->cost;
2067  const int* const gHead = graph->head;
2068  const int* const gTail = graph->tail;
2069  SCIP_Bool partrand = FALSE;
2070  SCIP_Bool totalrand = FALSE;
2071  const int nedges = graph->edges;
2072  const int nnodes = graph->knots;
2073 
2074  tmLpGetEdgeRandomizations(scip, heurdata, graph, &partrand, &totalrand);
2075 
2076  for( int k = 0; k < nnodes; k++ )
2077  nodepriority[k] = 0.0;
2078 
2079  if( !graph_pc_isMw(graph) )
2080  {
2081  for( int e = 0; e < nedges; e++ )
2082  {
2083  assert(graph->oeat[e] != EAT_FREE);
2084  nodepriority[gHead[e]] += xval[e];
2085  nodepriority[gTail[e]] += xval[e];
2086  }
2087  }
2088 
2089  if( graph->stp_type == STP_DHCSTP )
2090  {
2091  for( int e = 0; e < nedges; e++ )
2092  {
2093  if( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[flipedge_Uint(e)]) < 0.5 )
2094  {
2095  cost[e] = BLOCKED;
2096  }
2097  else
2098  {
2099  if( totalrand )
2100  {
2101  const SCIP_Real randval = SCIPrandomGetReal(heurdata->randnumgen, randlower, randupper);
2102  cost[e] = gCost[e] * randval;
2103  }
2104  else
2105  {
2106  cost[e] = ((1.0 - xval[e]) * gCost[e]);
2107  }
2108  }
2109  if( partrand )
2110  {
2111  const SCIP_Real randval = SCIPrandomGetReal(heurdata->randnumgen, randlower, randupper);
2112  cost[e] = cost[e] * randval;
2113  }
2114 
2115  assert(SCIPisGE(scip, cost[e], 0.0));
2116  }
2117  }
2118  else
2119  {
2120  /* swap costs; set a high cost if the variable is fixed to 0 */
2121  if( graph_pc_isMw(graph) )
2122  {
2123  for( int e = 0; e < nedges; e++ )
2124  nodepriority[gHead[e]] += xval[e];
2125 
2126  for( int e = 0; e < nedges; e++ )
2127  {
2128  if( GE(gCost[e], FARAWAY) )
2129  cost[e] = gCost[e];
2130  else if( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[flipedge_Uint(e)]) < 0.5 )
2131  cost[e] = MAX(gCost[e], BLOCKED);
2132  else if( LT(gCost[e], FARAWAY ) && GE(gCost[flipedge_Uint(e)], FARAWAY) )
2133  cost[e] = (1.0 - xval[e]) * gCost[e];
2134  else
2135  cost[e] = gCost[e] * (1.0 - MIN(1.0, nodepriority[gHead[e]]));
2136  }
2137 
2138  for( int e = 0; e < nedges; e++ )
2139  nodepriority[gTail[e]] += xval[e];
2140  }
2141  else
2142  {
2143  for( int e = 0; e < nedges; e++ )
2144  {
2145  SCIP_Real randval = 1.0;
2146  if( totalrand || partrand )
2147  randval = SCIPrandomGetReal(heurdata->randnumgen, randlower, randupper);
2148 
2149  if( SCIPvarGetUbLocal(vars[e]) < 0.5 && SCIPvarGetUbLocal(vars[flipedge_Uint(e)]) < 0.5 )
2150  {
2151  cost[e] = MAX(gCost[e], BLOCKED);
2152  continue;
2153  }
2154 
2155  if( totalrand )
2156  cost[e] = gCost[e] * randval;
2157  else
2158  cost[e] = ((1.0 - xval[e]) * gCost[e]);
2159 
2160  if( partrand )
2161  cost[e] = cost[e] * randval;
2162  }
2163  }
2164  } /* graph->stp_type != STP_DHCSTP */
2165 
2166  if( graph_pc_isPcMw(graph) && prize )
2167  {
2168  assert(graph->extended);
2169 
2170  for( int k = 0; k < nnodes; k++ )
2171  prize[k] = graph->prize[k];
2172 
2173  for( int k = 0; k < nnodes; k++ )
2174  {
2175  if( Is_pseudoTerm(graph->term[k]) )
2176  {
2177  const int term = graph_pc_getTwinTerm(graph, k);
2178  const int rootedge = graph_pc_getRoot2PtermEdge(graph, term);
2179 
2180  prize[k] = cost[rootedge];
2181 
2182  assert(prize[k] >= 0.0);
2183  }
2184  }
2185  }
2186 }
2187 
2188 
2189 /** initializes for TM SP runs (computes shortest paths from all terminals) */
2190 static
2192  SCIP* scip, /**< SCIP data structure */
2193  const GRAPH* graph, /**< graph data structure */
2194  const SCIP_Real* cost, /**< arc costs */
2195  const SCIP_Real* costrev, /**< reversed arc costs */
2196  TMALLSP* tmallsp /**< TM data */
2197 )
2198 {
2199  SCIP_Real** pathdist = tmallsp->pathdist;
2200  int** pathedge = tmallsp->pathedge;
2201  const int nnodes = graph_get_nNodes(graph);
2202  const int root = graph->source;
2203 
2204  assert(pathdist != NULL);
2205  assert(pathedge != NULL);
2206 
2207  for( int k = 0; k < nnodes; k++ )
2208  graph->mark[k] = (graph->grad[k] > 0);
2209 
2210  /* initialize shortest paths from all terminals */
2211  for( int k = 0; k < nnodes; k++ )
2212  {
2213  if( Is_term(graph->term[k]) )
2214  {
2215  if( root == k )
2216  graph_path_execX(scip, graph, k, cost, pathdist[k], pathedge[k]);
2217  else
2218  graph_path_execX(scip, graph, k, costrev, pathdist[k], pathedge[k]);
2219  }
2220  }
2221 }
2222 
2223 /** initial runs for DHCSTP to figure out a good hop factor */
2224 static
2226  SCIP* scip, /**< SCIP data structure */
2227  GRAPH* graph, /**< graph data structure */
2228  SCIP_Real* cost, /**< hacky */
2229  SCIP_Real* costrev, /**< hacky */
2230  SCIP_Real* hopfactor, /**< (in/out) */
2231  TMBASE* tmbase, /**< (in/out) */
2232  SCIP_Bool* success /**< success? */
2233 )
2234 {
2236  SCIP_Real* RESTRICT orgcost;
2237  int* RESTRICT result = tmbase->result;
2238  int* RESTRICT best_result = tmbase->best_result;
2239  SCIP_Real hopfactor_local;
2240  SCIP_Real hopfactor_best = -1.0;
2241  SCIP_Real maxcost = 0.0;
2242  const int nedges = graph_get_nEdges(graph);
2243  const int root = graph->source;
2244  const int nnodes = graph_get_nNodes(graph);
2245  const int maxnrounds = 10;
2246 
2247  assert(hopfactor && success);
2248  assert(*success == FALSE);
2249  assert(graph->stp_type == STP_DHCSTP);
2250 
2251  if( LE(*hopfactor, 0.0 ) )
2252  *hopfactor = DEFAULT_HOPFACTOR;
2253 
2254  SCIP_CALL( SCIPallocBufferArray(scip, &connected, nnodes) );
2255  SCIP_CALL( SCIPallocBufferArray(scip, &orgcost, nedges) );
2256 
2257  for( int e = 0; e < nedges; e++ )
2258  {
2259  if( GT(cost[e], maxcost) && LT(cost[e], BLOCKED) )
2260  maxcost = cost[e];
2261  }
2262 
2263  assert(GT(maxcost, 0.0));
2264 
2265  hopfactor_local = *hopfactor;
2266 
2267  BMScopyMemoryArray(orgcost, cost, nedges);
2268 
2269  /* do a warm-up run */
2270  for( int r = 0; r < maxnrounds; r++ )
2271  {
2272  SCIP_Real gap_relative;
2273  const SCIP_Real* const gcost = graph->cost;
2274  SCIP_Real obj = 0.0;
2275  int edgecount = 0;
2276  SCIP_Bool lsuccess = FALSE;
2277 
2278  assert(GT(hopfactor_local, 0.0));
2279 
2280  SCIPdebugMessage("warm-up run %d with hopfactor=%f \n", r, hopfactor_local);
2281 
2282  for( int e = 0; e < nedges; e++ )
2283  {
2284  if( LT(cost[e], BLOCKED) )
2285  cost[e] = 1.0 + orgcost[e] / (hopfactor_local * maxcost);
2286 
2287  result[e] = UNKNOWN;
2288  }
2289 
2290  SCIP_CALL( computeSteinerTreeDijk(scip, graph, root, tmbase) );
2291 
2292  for( int e = 0; e < nedges; e++)
2293  {
2294  if( result[e] == CONNECT )
2295  {
2296  obj += gcost[e];
2297  edgecount++;
2298  }
2299  }
2300 
2301  SCIPdebugMessage("edgecount=%d graph->hoplimit=%d \n", edgecount, graph->hoplimit);
2302 
2303  if( SCIPisLT(scip, obj, tmbase->best_obj) && edgecount <= graph->hoplimit )
2304  {
2305  tmbase->best_obj = obj;
2306 
2307  for( int e = 0; e < nedges; e++ )
2308  best_result[e] = result[e];
2309 
2310  (*success) = TRUE;
2311  lsuccess = TRUE;
2312  hopfactor_best = hopfactor_local;
2313  }
2314 
2315  gap_relative = fabs((double) edgecount - graph->hoplimit) / (double) graph->hoplimit;
2316  assert(GE(gap_relative, 0.0));
2317 
2318  if( !lsuccess || gap_relative > 0.05 )
2319  {
2320  if( !lsuccess )
2321  {
2322 
2323  if( (*success) )
2324  {
2325  hopfactor_local *= (1.0 + gap_relative);
2326  }
2327  else
2328  {
2329  hopfactor_local *= (1.0 + 3.0 * gap_relative);
2330  hopfactor_best = hopfactor_local;
2331  }
2332  }
2333  else
2334  {
2335  hopfactor_local /= (1.0 + gap_relative);
2336  }
2337 
2338  assert(SCIPisGT(scip, hopfactor_local, 0.0));
2339  }
2340  else
2341  {
2342  break;
2343  }
2344  }
2345 
2346  assert(SCIPisGT(scip, hopfactor_best, 0.0));
2347 
2348  (*hopfactor) = hopfactor_best;
2349 
2350  for( int e = 0; e < nedges; e++ )
2351  if( (LT(cost[e], BLOCKED) ) )
2352  cost[e] = 1.0 + orgcost[e] / (hopfactor_best * maxcost);
2353 
2354  for( int e = 0; e < nedges; e++)
2355  costrev[e] = cost[flipedge(e)];
2356 
2357  SCIPfreeBufferArray(scip, &orgcost);
2358  SCIPfreeBufferArray(scip, &connected);
2359 
2360  return SCIP_OKAY;
2361 }
2362 
2363 
2364 /** submethod for SCIPStpHeurTMRun */
2365 static
2367  SCIP* scip, /**< SCIP data structure */
2368  GRAPH* graph, /**< graph data structure */
2369  TMBASE* tmbase, /**< TM base data */
2370  TMALLSP* tmallsp, /**< TM data */
2371  TMVNOI* tmvnoi, /**< TM data */
2372  SCIP_Bool* success /**< pointer to store whether a solution could be found */
2373 )
2374 {
2375  SCIP_HEURDATA* heurdata = getTMheurData(scip);
2376  const int* const start = tmbase->startnodes;
2377  int* const result = tmbase->result;
2378  const SCIP_Real* cost = tmbase->cost;
2379  const SCIP_Real* costrev = tmbase->costrev;
2380  const int mode = getTmMode(heurdata, graph);
2381  const int runs = tmbase->nruns;
2382  STP_Bool solfound = FALSE;
2383 
2384  assert(!graph_pc_isPcMw(graph));
2385  assert(runs >= 1);
2386 
2387  if( graph->stp_type == STP_DCSTP || mode == TM_SP )
2388  {
2389  buildTmAllSp(scip, graph, cost, costrev, tmallsp);
2390  }
2391 
2392  /* loop over start nodes and call TM heuristic */
2393  for( int r = 0; r < runs; r++ )
2394  {
2395  assert(start[r] >= 0 && start[r] < graph->knots);
2396  assert(graph->stp_type != STP_NWPTSPG || !graph_knotIsNWLeaf(graph, start[r]));
2397 
2398  if( graph->stp_type == STP_DCSTP )
2399  {
2400  SCIP_CALL( computeDegConsTree(scip, graph, cost, costrev, start[r], result, tmallsp, heurdata->randnumgen, tmbase->connected, &solfound) );
2401  }
2402  else if( mode == TM_DIJKSTRA )
2403  {
2404 #ifdef TM_USE_CSR
2405  SCIP_CALL( computeSteinerTreeCsr(scip, graph, start[r], tmbase) );
2406 #else
2407  SCIP_CALL( computeSteinerTreeDijk(scip, graph, start[r], tmbase) );
2408 #endif
2409  }
2410  else if( mode == TM_SP )
2411  {
2412  SCIP_CALL( computeSteinerTree(scip, graph, cost, costrev, start[r], result, tmallsp, tmbase->connected, heurdata->randnumgen) );
2413  }
2414  else
2415  {
2416  SCIP_CALL( computeSteinerTreeVnoi(scip, graph, cost, costrev, start[r], (r == 0), tmvnoi, result, tmbase->connected) );
2417  }
2418 
2419  /* check whether best solution can be improved, and if so, replace */
2420  updateBestSol(scip, graph, start[r], solfound, tmbase, success);
2421 
2422  /* stop early? */
2423  if( SCIPisStopped(scip) )
2424  break;
2425  }
2426 
2427 #ifdef TM_USE_CSR
2428  if( !SCIPisStopped(scip) && mode == TM_DIJKSTRA && graph_typeIsSpgLike(graph) && 0 )
2429  {
2430  SCIP_CALL( computeSteinerTreeKeyNodesCsr(scip, graph, tmbase->best_start, tmbase) );
2431 
2432  // const SCIP_Real obj = solstp_getObjCsr(graph, tmbase->csr_orgcosts, tmbase->result, tmbase->connected);
2433 //printf("%f < %f? \n", obj, tmbase->best_obj);
2434 
2435  updateBestSol(scip, graph, tmbase->best_start, solfound, tmbase, success);
2436  }
2437 #endif
2438 
2439 
2440  return SCIP_OKAY;
2441 }
2442 
2443 
2444 /** submethod for SCIPStpHeurTMRun in PC or MW mode */
2445 static
2447  SCIP* scip, /**< SCIP data structure */
2448  GRAPH* graph, /**< graph data structure */
2449  const SCIP_Real* cost, /**< arc costs */
2450  const SCIP_Real* prize, /**< prizes (for PCMW) or NULL */
2451  enum PCMW_TmMode pcmwmode, /**< mode */
2452  int bestincstart, /**< best incumbent start vertex */
2453  SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
2454  TMBASE* tmbase, /**< data */
2455  SCIP_Bool* success /**< pointer to store whether a solution could be found */
2456 )
2457 {
2458  SPATHSPC* sppc;
2459  SCIP_Real* costorg = NULL;
2460  SCIP_Real* costfullbiased = NULL;
2461  SCIP_Real* prizefullbiased = NULL;
2462  const SCIP_Real* const prize_in = (prize) ? prize : graph->prize;
2463  int* startnodes = NULL;
2464  const int nnodes = graph->knots;
2465  const int nedges = graph->edges;
2466  int maxruns = tmbase->nruns;
2467 
2468  assert(graph->extended);
2469  assert(pcmwmode != pcmode_all);
2470  assert(graph_valid(scip, graph));
2471 
2472  if( graph_pc_isPc(graph) )
2473  {
2474  SCIP_CALL( SCIPallocBufferArray(scip, &costorg, nedges) );
2475  graph_pc_getOrgCosts(scip, graph, costorg);
2476 
2477 #ifdef TM_USE_CSR_PCMW
2478  assert(graph_csr_costsAreInSync(graph, tmbase->csr_orgcosts, costorg));
2479 #endif
2480  }
2481 
2482  if( pcmwmode == pcmode_biasfull )
2483  {
2484  SCIP_CALL( SCIPallocBufferArray(scip, &costfullbiased, nedges) );
2485  SCIP_CALL( SCIPallocBufferArray(scip, &prizefullbiased, nnodes) );
2486  graph_pc_getBiased(graph, costfullbiased, prizefullbiased);
2487  SCIP_CALL( shortestpath_pcInit(scip, graph, costfullbiased, prizefullbiased, &sppc) );
2488  }
2489  else
2490  {
2491  SCIP_CALL( shortestpath_pcInit(scip, graph, NULL, prize_in, &sppc) );
2492  }
2493 
2494  SCIP_CALL( SCIPallocBufferArray(scip, &startnodes, graph->terms) );
2495  pcmwGetStartNodes(scip, nodepriority, maxruns, bestincstart, graph, startnodes);
2496 
2497  if( graph->stp_type == STP_BRMWCSP )
2498  startnodes[0] = graph->source;
2499 
2500  pcmwSetEdgeCosts(graph, cost, costorg, costfullbiased, pcmwmode, tmbase);
2501 
2502  /* main loop */
2503  for( int r = 0; r < maxruns; r++ )
2504  {
2505  const int start = startnodes[r];
2506  SCIPdebugMessage("TM run=%d start=%d\n", r, start);
2507 
2508  if( graph->stp_type == STP_BRMWCSP && !graph_pc_knotIsFixedTerm(graph, start) )
2509  continue;
2510 
2511  if( graph->grad[start] == 0 )
2512  {
2513  computeSteinerTreeSingleNode(graph, start, tmbase, success);
2514  continue;
2515  }
2516  else if( graph->grad[start] == 1 )
2517  {
2518  if( !graph_pc_isRootedPcMw(graph) || !graph_pc_knotIsFixedTerm(graph, start) )
2519  continue;
2520  }
2521 
2522  // todo do that properly...
2523  if( graph->stp_type == STP_BRMWCSP )
2524  {
2525  SCIP_Bool solfound = FALSE;
2526  SCIP_CALL( computeSteinerTreeDijkBMw(scip, graph, costorg, prize_in, start, tmbase, &solfound) );
2527 
2528  if( solfound )
2529  {
2530  const SCIP_Real obj = solstp_getObjBounded(graph, tmbase->result, 0.0, nedges);
2531  *success = TRUE;
2532 
2533  if( LT(obj, tmbase->best_obj) )
2534  {
2535  tmbase->best_obj = obj;
2536  BMScopyMemoryArray(tmbase->best_result, tmbase->result, nedges);
2537  (*success) = TRUE;
2538  }
2539  }
2540 
2541  continue;
2542  }
2543  else if( pcmwmode == pcmode_fulltree )
2544  {
2545  SCIP_CALL( computeSteinerTreeDijkPcMwFull(scip, graph, costorg, start, tmbase) );
2546  }
2547  else if( pcmwmode == pcmode_biasfull )
2548  {
2550  costorg, prizefullbiased, TRUE, start, sppc, tmbase) );
2551  }
2552  else if( pcmwmode == pcmode_simple )
2553  {
2554  assert(graph_pc_isPc(graph));
2556  costorg, prize_in, FALSE, start, sppc, tmbase) );
2557  }
2558  else
2559  {
2560  assert(pcmwmode == pcmode_bias);
2562  costorg, prize_in, TRUE, start, sppc, tmbase) );
2563  }
2564 
2565  /* update the best known solution if possible */
2566  pcmwUpdateBestSol(scip, graph, tmbase, success);
2567 
2568  if( SCIPisStopped(scip) )
2569  break;
2570  }
2571 
2572  shortestpath_pcFree(scip, &sppc);
2573 
2575  SCIPfreeBufferArrayNull(scip, &prizefullbiased);
2576  SCIPfreeBufferArrayNull(scip, &costfullbiased);
2577  SCIPfreeBufferArrayNull(scip, &costorg);
2578 
2579  return SCIP_OKAY;
2580 }
2581 
2582 
2583 /** SCIPStpHeurTMRun in PC or MW mode */
2584 static inline
2586  SCIP* scip, /**< SCIP data structure */
2587  GRAPH* graph, /**< graph data structure */
2588  const SCIP_Real* cost, /**< arc costs */
2589  const SCIP_Real* prize, /**< prizes (for PCMW) or NULL */
2590  enum PCMW_TmMode pcmw_tmmode, /**< mode */
2591  int beststart, /**< best incumbent start vertex */
2592  SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
2593  TMBASE* tmbase, /**< data */
2594  SCIP_Bool* success /**< pointer to store whether a solution could be found */
2595 )
2596 {
2597  SCIP_HEURDATA* heurdata = getTMheurData(scip);
2598  enum PCMW_TmMode pcmw_mode = (pcmw_tmmode == pcmode_fromheurdata) ? heurdata->pcmw_mode : pcmw_tmmode;
2599  SCIP_Bool run_all = (pcmw_mode == pcmode_all);
2600 
2601  // todo do that properly
2602  if( graph->stp_type == STP_BRMWCSP )
2603  {
2604  pcmw_mode = pcmode_bias;
2605  run_all = FALSE;
2606  }
2607 
2608  assert(graph_pc_isPcMw(graph));
2609  assert(graph_pc_isPc(graph) || pcmw_mode != pcmode_simple);
2610  assert(pcmw_mode != pcmode_fromheurdata);
2611 
2612  if( graph_pc_isPc(graph) && (pcmw_mode == pcmode_simple || run_all) )
2613  {
2614  SCIP_CALL( runTmPcMW_mode(scip, graph, cost, prize, pcmode_simple, beststart, nodepriority, tmbase, success));
2615  }
2616  if( pcmw_mode == pcmode_bias || pcmw_mode == pcmode_biasAndFulltree || run_all )
2617  {
2618  SCIP_CALL( runTmPcMW_mode(scip, graph, cost, prize, pcmode_bias, beststart, nodepriority, tmbase, success));
2619  }
2620  if( pcmw_mode == pcmode_biasfull || run_all )
2621  {
2622  SCIP_CALL( runTmPcMW_mode(scip, graph, cost, prize, pcmode_biasfull, beststart, nodepriority, tmbase, success));
2623  }
2624  if( pcmw_mode == pcmode_fulltree || pcmw_mode == pcmode_biasAndFulltree || run_all )
2625  {
2626  SCIP_CALL( runTmPcMW_mode(scip, graph, cost, prize, pcmode_fulltree, beststart, nodepriority, tmbase, success));
2627  }
2628 
2629  return SCIP_OKAY;
2630 }
2631 
2632 
2633 /** submethod for SCIPStpHeurTMRun */
2634 static
2636  SCIP* scip, /**< SCIP data structure */
2637  GRAPH* graph, /**< graph data structure */
2638  TMBASE* tmbase, /**< TM base data */
2639  TMALLSP* tmallsp, /**< TM data */
2640  TMVNOI* tmvnoi, /**< TM data */
2641  SCIP_Real* hopfactor, /**< hopfactor */
2642  SCIP_Bool* success /**< pointer to store whether a solution could be found */
2643 )
2644 {
2645  SCIP_Real* cost;
2646  SCIP_Real* costrev;
2647  const SCIP_Real* cost_org;
2648  const SCIP_Real* costrev_org;
2649  const int nedges = graph_get_nEdges(graph);
2650 
2651  assert(graph->stp_type == STP_DHCSTP);
2652 
2653  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
2654  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
2655  BMScopyMemoryArray(cost, tmbase->cost, nedges);
2656  BMScopyMemoryArray(costrev, tmbase->costrev, nedges);
2657 
2658  cost_org = tmbase->cost;
2659  costrev_org = tmbase->costrev;
2660  tmbase->cost = cost;
2661  tmbase->costrev = costrev;
2662 
2663  SCIP_CALL( dhcstpWarmUp(scip, graph, cost, costrev, hopfactor, tmbase, success) );
2664  SCIP_CALL( runTm(scip, graph, tmbase, tmallsp, tmvnoi, success) );
2665 
2666  tmbase->cost = cost_org;
2667  tmbase->costrev = costrev_org;
2668  SCIPfreeBufferArray(scip, &costrev);
2669  SCIPfreeBufferArray(scip, &cost);
2670 
2671  return SCIP_OKAY;
2672 }
2673 
2674 
2675 /*
2676  * Callback methods of primal heuristic
2677  */
2678 
2679 
2680 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
2681 static
2683 { /*lint --e{715}*/
2684  assert(scip != NULL);
2685  assert(heur != NULL);
2686  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2687 
2688  /* call inclusion method of primal heuristic */
2690 
2691  return SCIP_OKAY;
2692 }
2693 
2694 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2695 static
2697 { /*lint --e{715}*/
2698  SCIP_HEURDATA* heurdata;
2699 
2700  assert(heur != NULL);
2701  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2702  assert(scip != NULL);
2703 
2704  heurdata = SCIPheurGetData(heur);
2705  assert(heurdata != NULL);
2706 
2707  SCIPfreeRandom(scip, &heurdata->randnumgen);
2708 
2709  /* free heuristic data */
2710  SCIPfreeMemory(scip, &heurdata);
2711  SCIPheurSetData(heur, NULL);
2712 
2713  return SCIP_OKAY;
2714 }
2715 
2716 
2717 /** initialization method of primal heuristic (called after problem was transformed) */
2718 static
2720 { /*lint --e{715}*/
2721  SCIP_HEURDATA* heurdata;
2722  SCIP_PROBDATA* probdata;
2723  GRAPH* graph;
2724  int pcmwmode;
2725 
2726  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2727 
2728  heurdata = SCIPheurGetData(heur);
2729  assert(heurdata != NULL);
2730 
2731  probdata = SCIPgetProbData(scip);
2732  assert(probdata != NULL);
2733 
2734  graph = SCIPprobdataGetGraph(probdata);
2735  if( graph == NULL )
2736  {
2737  heurdata->stp_type = STP_SPG;
2738  return SCIP_OKAY;
2739  }
2740  heurdata->stp_type = graph->stp_type;
2741  heurdata->beststartnode = -1;
2742  heurdata->ncalls = 0;
2743  heurdata->nlpiterations = -1;
2744  heurdata->nexecs = 0;
2745 
2746  SCIP_CALL( SCIPgetIntParam(scip, "heuristics/TM/pcmwmode", &(pcmwmode)) );
2747  heurdata->pcmw_mode = pcmwmode;
2748 
2749  return SCIP_OKAY;
2750 }
2751 
2752 /** execution method of primal heuristic */
2753 static
2755 { /*lint --e{715}*/
2756  SCIP_VAR** vars;
2757  SCIP_PROBDATA* probdata;
2758  SCIP_HEURDATA* heurdata;
2759  GRAPH* graph;
2760  int* soledges;
2761  int runs;
2762  SCIP_Bool success = FALSE;
2763  SCIP_Bool isSpg;
2764  SCIP_Bool isPcMw;
2765 
2766  assert(scip != NULL);
2767  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2768  assert(result != NULL);
2769 
2771 
2772  /* get heuristic data */
2773  heurdata = SCIPheurGetData(heur);
2774  assert(heurdata != NULL);
2775 
2776  probdata = SCIPgetProbData(scip);
2777  assert(probdata != NULL);
2778 
2779  graph = SCIPprobdataGetGraph(probdata);
2780  assert(graph != NULL);
2781 
2782  runs = 0;
2783  isSpg = graph_typeIsSpgLike(graph);
2784  isPcMw = graph_pc_isPcMw(graph);
2785 
2786  /* set the runs, i.e. number of different starting points for the heuristic */
2787  if( heurtiming & SCIP_HEURTIMING_BEFORENODE )
2788  {
2789  if( SCIPgetDepth(scip) > 0 )
2790  return SCIP_OKAY;
2791 
2792  runs = heurdata->initruns;
2793  }
2794  else if( ((heurtiming & SCIP_HEURTIMING_DURINGLPLOOP) && (heurdata->ncalls % heurdata->duringlpfreq == 0)) || (heurtiming & SCIP_HEURTIMING_AFTERLPLOOP) )
2795  {
2796  runs = heurdata->evalruns;
2797 
2798  if( isPcMw )
2799  runs *= 2;
2800  }
2801  else if( heurtiming & SCIP_HEURTIMING_AFTERNODE )
2802  {
2803  if( SCIPgetDepth(scip) == 0 )
2804  runs = heurdata->rootruns;
2805  else
2806  runs = heurdata->leafruns;
2807 
2808  if( graph->stp_type == STP_DCSTP )
2809  runs = 0;
2810  }
2811 
2812  if( (isPcMw || isSpg) && graph->edges < TM_HARD_MAXNEDGES && SCIPprobdataProbIsAdversarial(scip) )
2813  {
2814  assert(heurdata->hardrunsmult >= 1.0);
2815  if( !(heurtiming & SCIP_HEURTIMING_BEFORENODE) )
2816  {
2817  runs *= heurdata->hardrunsmult;
2818  }
2819  }
2820 
2821  /* increase counter for number of (TM) calls */
2822  heurdata->ncalls++;
2823 
2824  if( runs == 0 )
2825  return SCIP_OKAY;
2826 
2827  // todo solution should anyway come from the branching rule
2829  return SCIP_OKAY;
2830 
2831  if( graph->stp_type == STP_DCSTP )
2832  runs = 1;
2833 
2834  heurdata->nexecs++;
2835 
2836  SCIPdebugMessage("Heuristic Start\n");
2837 
2838  /* get all variables (corresponding to the edges) */
2839  vars = SCIPprobdataGetVars(scip);
2840  if( vars == NULL )
2841  return SCIP_OKAY;
2842 
2843  assert(vars[0] != NULL);
2844  SCIP_CALL(SCIPallocBufferArray(scip, &soledges, graph->edges));
2845 
2847 
2848  /* call the actual heuristic */
2849  SCIP_CALL( SCIPStpHeurTMRunLP(scip, graph, heur, soledges, runs, &success) );
2850 
2851  if( success )
2852  {
2853  SCIP_CALL( solstp_addSolToProb(scip, graph, soledges, heur, &success) );
2854 
2855  if( success )
2856  {
2857  SCIPdebugMessage("TM solution added, value %f \n", solstp_getObj(graph, soledges, SCIPprobdataGetOffset(scip)));
2858  *result = SCIP_FOUNDSOL;
2859  }
2860  else
2861  {
2862  SCIPdebugMessage("TM solution not added \n");
2863  }
2864  }
2865 
2866  heurdata->nlpiterations = SCIPgetNLPIterations(scip);
2867  SCIPfreeBufferArray(scip, &soledges);
2868 
2869  return SCIP_OKAY;
2870 }
2871 
2872 /*
2873  * primal heuristic specific interface methods
2874  */
2875 
2876 
2877 
2878 /** compute starting points among marked (w.r.t. g->mark) vertices for constructive heuristics */
2880  GRAPH* graph, /**< graph data structure */
2881  int* starts, /**< starting points array */
2882  int* runs /**< pointer to number of runs */
2883  )
2884 {
2885  int r;
2886  int l;
2887  int root;
2888  int nruns;
2889  int nnodes;
2890  int nterms;
2891  int randval;
2892 
2893  assert(runs != NULL);
2894  assert(graph != NULL);
2895  assert(starts != NULL);
2896 
2897  nruns = *runs;
2898  root = graph->source;
2899  nnodes = graph->knots;
2900  nterms = graph->terms;
2901 
2902  r = 0;
2903  if( graph->mark[root] && nruns > 0 )
2904  starts[r++] = root;
2905 
2906  randval = nnodes - nterms;
2907 
2908  /* use non-isolated terminals as starting points for TM heuristic */
2909  for( int k = 0; k < nnodes; k++ )
2910  {
2911  if( r >= nruns || r >= nterms )
2912  break;
2913 
2914  l = (k + randval) % nnodes;
2915  if( Is_term(graph->term[l]) && graph->mark[l] && l != root )
2916  starts[r++] = l;
2917  }
2918 
2919  /* fill empty slots randomly */
2920  for( int k = 0; k < nnodes && r < nruns; k++ )
2921  {
2922  l = (k + randval) % nnodes;
2923  if( !Is_term(graph->term[l]) && graph->mark[l] )
2924  starts[r++] = l;
2925  }
2926 
2927  *runs = r;
2928 }
2929 
2930 
2931 /** build Steiner tree in such a way that all leaves are terminals */
2933  SCIP* scip, /**< SCIP data structure */
2934  GRAPH* g, /**< graph structure */
2935  PATH* mst, /**< path data structure array */
2936  const SCIP_Real* cost, /**< edge costs */
2937  SCIP_Real* objresult, /**< pointer to store objective value of result */
2938  int* connected /**< CONNECT/UNKNOWN */
2939  )
2940 {
2941  SCIP_Real obj;
2942  int i;
2943  int j;
2944  int e1;
2945  int root;
2946  int count;
2947  int nnodes;
2948 
2949  assert(g != NULL);
2950  assert(mst != NULL);
2951  assert(scip != NULL);
2952  assert(cost != NULL);
2953  assert(connected != NULL);
2954  assert(!graph_pc_isPcMw(g));
2955 
2956  obj = 0.0;
2957  root = g->source;
2958  nnodes = g->knots;
2959 
2960  /* compute the MST */
2961  for( i = nnodes - 1; i >= 0; --i )
2962  g->mark[i] = (connected[i] == CONNECT);
2963 
2964  graph_path_exec(scip, g, MST_MODE, root, cost, mst);
2965 
2966  /* prune */
2967  do
2968  {
2969  count = 0;
2970 
2971  for( i = nnodes - 1; i >= 0; --i )
2972  {
2973  if( !g->mark[i] || Is_term(g->term[i]) )
2974  continue;
2975 
2976  for( j = g->outbeg[i]; j != EAT_LAST; j = g->oeat[j] )
2977  {
2978  e1 = mst[g->head[j]].edge;
2979  if( e1 == j )
2980  break;
2981  }
2982 
2983  if( j == EAT_LAST )
2984  {
2985  mst[i].edge = UNKNOWN;
2986  g->mark[i] = FALSE;
2987  connected[i] = UNKNOWN;
2988  count++;
2989  break;
2990  }
2991  }
2992  }
2993  while( count > 0 );
2994 
2995  for( i = nnodes - 1; i >= 0; --i )
2996  {
2997  if( mst[i].edge >= 0 )
2998  obj += cost[mst[i].edge];
2999  else if( Is_term(g->term[i]) && i != root )
3000  {
3001  obj = FARAWAY;
3002  break;
3003  }
3004  }
3005 
3006  *objresult = obj;
3007 }
3008 
3009 
3010 
3011 /** build (rooted) prize collecting Steiner tree in such a way that all leaves are terminals; objresult is set FARAWAY if infeasible */
3013  SCIP* scip, /**< SCIP data structure */
3014  const GRAPH* g, /**< graph structure */
3015  SCIP_Bool useRootSym, /**< use? */
3016  PATH* mst, /**< path data structure array */
3017  const SCIP_Real* cost, /**< edge costs */
3018  SCIP_Real* objresult, /**< pointer to store objective value of result */
3019  int* connected /**< CONNECT/UNKNOWN */
3020  )
3021 {
3022  SCIP_Real obj;
3023  int mstroot;
3024  int count;
3025  const int nnodes = g->knots;
3026  const int orgroot = g->source;
3027  const SCIP_Bool isrooted = graph_pc_isRootedPcMw(g);
3028 
3029  assert(g != NULL);
3030  assert(mst != NULL);
3031  assert(scip != NULL);
3032  assert(cost != NULL);
3033  assert(connected != NULL);
3034  assert(g->extended);
3035 
3036  obj = 0.0;
3037 
3038  /* unmark all dummy terminals and unconnected nodes */
3039  for( int i = nnodes - 1; i >= 0; --i )
3040  {
3041  if( connected[i] == CONNECT && !Is_term(g->term[i]) )
3042  g->mark[i] = TRUE;
3043  else
3044  g->mark[i] = FALSE;
3045 
3046  if( isrooted && graph_pc_knotIsFixedTerm(g, i) )
3047  g->mark[i] = TRUE;
3048  }
3049 
3050  if( isrooted )
3051  {
3052  mstroot = orgroot;
3053  assert(g->mark[mstroot]);
3054  }
3055  else
3056  {
3057  int a;
3058  int i;
3059  for( a = g->outbeg[orgroot]; a != EAT_LAST; a = g->oeat[a] )
3060  {
3061  i = g->head[a];
3062  if( g->mark[i] )
3063  {
3064  assert(Is_pseudoTerm(g->term[i]) && connected[i] == CONNECT);
3065  break;
3066  }
3067  }
3068 
3069  /* trivial solution? */
3070  if( a == EAT_LAST )
3071  {
3072  for( int k = 0; k < nnodes; k++ )
3073  mst[k].edge = UNKNOWN;
3074 
3075  SCIPdebugMessage("trivial solution in buildPcMwTree \n");
3076  for( a = g->outbeg[orgroot]; a != EAT_LAST; a = g->oeat[a] )
3077  {
3078  const int head = g->head[a];
3079  if( Is_term(g->term[head]) )
3080  {
3081  obj += cost[a];
3082  mst[head].edge = a;
3083  }
3084  }
3085  (*objresult) = obj;
3086  return SCIP_OKAY;
3087  }
3088 
3089  assert(g->mark[i]);
3090  mstroot = i;
3091 
3092  if( useRootSym && graph_pc_isUnrootedPcMw(g) )
3093  {
3094  /* todo remove this hack... */
3095  if( SCIPprobdataGetNTerms(scip) == g->terms && SCIPprobdataGetNNodes(scip) == nnodes )
3096  {
3097  int min = nnodes;
3098  const int* termsorder = SCIPprobdataGetPctermsorder(scip);
3099  assert(termsorder);
3100 
3101  for( int k = 0; k < nnodes; k++ )
3102  {
3103  if( termsorder[k] < min && connected[k] == CONNECT )
3104  {
3105  assert(Is_pseudoTerm(g->term[k]));
3106 
3107  min = termsorder[k];
3108  mstroot = k;
3109  }
3110  }
3111  }
3112  }
3113  }
3114  assert(mstroot >= 0);
3115  assert(mstroot < nnodes);
3116 
3117  graph_path_exec(scip, g, MST_MODE, mstroot, cost, mst);
3118 
3119  assert(g->extended);
3120 
3121  /* connect all potential terminals */
3122  for( int i = nnodes - 1; i >= 0; --i )
3123  {
3124  if( graph_pc_knotIsDummyTerm(g, i) && i != orgroot )
3125  {
3126  int k1;
3127  int k2;
3128  const int e1 = g->inpbeg[i];
3129  const int e2 = g->ieat[e1];
3130 
3131  assert(e1 >= 0);
3132  assert(e2 != EAT_LAST);
3133 
3134  k1 = g->tail[e1];
3135  k2 = g->tail[e2];
3136 
3137  assert(e2 >= 0);
3138  assert(g->ieat[e2] == EAT_LAST);
3139  assert(k1 == orgroot || k2 == orgroot);
3140 
3141  if( k1 != orgroot && g->path_state[k1] == CONNECT )
3142  {
3143  mst[i].edge = e1;
3144  }
3145  else if( k2 != orgroot && g->path_state[k2] == CONNECT )
3146  {
3147  mst[i].edge = e2;
3148  }
3149  else if( k1 == orgroot )
3150  {
3151  mst[i].edge = e1;
3152  }
3153  else if( k2 == orgroot )
3154  {
3155  mst[i].edge = e2;
3156  }
3157  else
3158  {
3159  assert(0 && "should not happen");
3160  }
3161  }
3162  } /* connect all potential terminals */
3163 
3164  if( !isrooted )
3165  {
3166  int e1;
3167  for( e1 = g->inpbeg[mstroot]; e1 != EAT_LAST; e1 = g->ieat[e1] )
3168  if( g->tail[e1] == orgroot )
3169  break;
3170  assert(e1 != EAT_LAST);
3171  mst[mstroot].edge = e1;
3172  }
3173 
3174  /* prune */
3175  do
3176  {
3177  int j;
3178  count = 0;
3179 
3180  for( int i = nnodes - 1; i >= 0; --i )
3181  {
3182  if( !g->mark[i] || g->path_state[i] != CONNECT || Is_term(g->term[i]) )
3183  continue;
3184 
3185  for( j = g->outbeg[i]; j != EAT_LAST; j = g->oeat[j] )
3186  {
3187  const int e1 = mst[g->head[j]].edge;
3188  if( e1 == j )
3189  break;
3190  }
3191 
3192  if( j == EAT_LAST )
3193  {
3194  assert(!Is_pseudoTerm(g->term[i]));
3195  mst[i].edge = UNKNOWN;
3196  g->mark[i] = FALSE;
3197  connected[i] = UNKNOWN;
3198  count++;
3199  break;
3200  }
3201  }
3202  }
3203  while( count > 0 );
3204 
3205  if( isrooted )
3206  {
3207  /* check for feasibility */
3208  for( int i = 0; i < nnodes; i++ )
3209  if( graph_pc_knotIsFixedTerm(g, i) && i != orgroot && mst[i].edge == UNKNOWN )
3210  {
3211  *objresult = FARAWAY;
3212  return SCIP_OKAY;
3213  }
3214  }
3215 
3216  for( int i = nnodes - 1; i >= 0; --i )
3217  if( mst[i].edge >= 0 )
3218  obj += cost[mst[i].edge];
3219 
3220  *objresult = obj;
3221  return SCIP_OKAY;
3222 }
3223 
3224 
3225 /** prune a degree constrained Steiner tree in such a way that all leaves are terminals */
3227  SCIP* scip, /**< SCIP data structure */
3228  const GRAPH* g, /**< graph structure */
3229  int* result, /**< ST edges */
3230  STP_Bool* connected /**< ST nodes (to be set) */
3231  )
3232 {
3233  int* queue;
3234  int i;
3235  int j;
3236  int qsize;
3237  int count;
3238  int nnodes;
3239  assert(scip != NULL);
3240  assert(g != NULL);
3241  assert(result != NULL);
3242  assert(connected != NULL);
3243 
3244  nnodes = g->knots;
3245 
3246  /*
3247  * DFS until all terminals are reached
3248  */
3249 
3250  for( i = 0; i < nnodes; i++ )
3251  connected[i] = FALSE;
3252 
3253  SCIP_CALL( SCIPallocBufferArray(scip, &queue, nnodes) );
3254 
3255  qsize = 0;
3256  queue[qsize++] = g->source;
3257  connected[g->source] = TRUE;
3258 
3259  while( qsize )
3260  {
3261  const int node = queue[--qsize];
3262  for( int e = g->outbeg[node]; e != EAT_LAST; e = g->oeat[e] )
3263  {
3264  if( (result[e] == CONNECT || result[flipedge(e)] == CONNECT) && !(connected[g->head[e]]) )
3265  {
3266  i = g->head[e];
3267  result[e] = CONNECT;
3268  result[flipedge(e)] = UNKNOWN;
3269  connected[i] = TRUE;
3270  queue[qsize++] = i;
3271  }
3272  }
3273  }
3274 
3275  SCIPfreeBufferArray(scip, &queue);
3276 
3277  /* prune */
3278  do
3279  {
3280  SCIPdebug(fputc('C', stdout));
3281  SCIPdebug(fflush(stdout));
3282 
3283  count = 0;
3284 
3285  for( i = 0; i < nnodes; i++ )
3286  {
3287  if( !connected[i] )
3288  continue;
3289 
3290  if( Is_term(g->term[i]) )
3291  continue;
3292 
3293  for( j = g->outbeg[i]; j != EAT_LAST; j = g->oeat[j] )
3294  if( result[j] == CONNECT )
3295  break;
3296 
3297  if( j == EAT_LAST )
3298  {
3299  /* there has to be exactly one incoming edge
3300  */
3301  for( j = g->inpbeg[i]; j != EAT_LAST; j = g->ieat[j] )
3302  {
3303  if( result[j] == CONNECT )
3304  {
3305  result[j] = UNKNOWN;
3306  connected[i] = FALSE;
3307  count++;
3308  break;
3309  }
3310  }
3311  assert(j != EAT_LAST);
3312  }
3313  }
3314  }
3315  while( count > 0 );
3316 
3317  // todo extra method!
3318  if( 0 )
3319  {
3320  const int* const maxdeg = g->maxdeg;
3321  int* deg1inedge;
3322  SCIP_Bool hasDeg1 = FALSE;
3323 
3324  SCIP_CALL( SCIPallocBufferArray(scip, &deg1inedge, nnodes) );
3325 
3326  for( i = 0; i < nnodes; i++ )
3327  {
3328  if( maxdeg[i] == 1 && connected[i] && i != g->source )
3329  {
3330  int e;
3331 
3332  assert(Is_term(g->term[i]));
3333 
3334  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
3335  {
3336  if( result[e] == CONNECT )
3337  break;
3338  }
3339  assert(e != EAT_LAST);
3340 
3341  deg1inedge[i] = e;
3342  hasDeg1 = TRUE;
3343  }
3344  else
3345  {
3346  deg1inedge[i] = -1;
3347  }
3348  }
3349 
3350  if( !hasDeg1 )
3351  {
3352  SCIPfreeBufferArray(scip, &deg1inedge);
3353  return SCIP_OKAY;
3354  }
3355 
3356  for( i = 0; i < nnodes; i++ )
3357  {
3358  if( connected[i] && maxdeg[i] > 1 )
3359  {
3360  int soldegree = 0;
3361 
3362  if( i != g->source )
3363  soldegree++;
3364 
3365  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
3366  {
3367  if( result[e] == CONNECT )
3368  soldegree++;
3369  }
3370 
3371 #ifndef NDEBUG
3372  {
3373  int degree_dbg = 0;
3374  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
3375  {
3376  if( result[e] == CONNECT || result[flipedge(e)] == CONNECT )
3377  degree_dbg++;
3378  }
3379  assert(degree_dbg == soldegree);
3380  }
3381 #endif
3382  assert(soldegree <= maxdeg[i]);
3383 
3384  if( soldegree < maxdeg[i] )
3385  {
3386  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
3387  {
3388  const int head = g->head[e];
3389  const int deg1edge = deg1inedge[head];
3390 
3391  if( deg1edge == -1 )
3392  continue;
3393 
3394  if( LT(g->cost[e], g->cost[deg1edge] ) )
3395  {
3396  assert(result[e] == UNKNOWN);
3397  assert(result[deg1edge] == CONNECT);
3398 
3399  // printf("switching! %f vs %f \n", g->cost[e], g->cost[deg1edge]);
3400  result[e] = CONNECT;
3401  result[deg1edge] = UNKNOWN;
3402  deg1inedge[head] = e;
3403  break;
3404  }
3405  }
3406  }
3407  }
3408  }
3409 
3410  SCIPfreeBufferArray(scip, &deg1inedge);
3411  }
3412 
3413  return SCIP_OKAY;
3414 }
3415 
3416 
3417 /** execute shortest paths heuristic to obtain a Steiner tree */
3419  SCIP* scip, /**< SCIP data structure */
3420  enum PCMW_TmMode pcmw_tmmode, /**< mode for PC/MW */
3421  GRAPH* graph, /**< graph data structure */
3422  int* starts, /**< array containing start vertices (NULL to not provide any) */
3423  const SCIP_Real* prize, /**< prizes (for PCMW) or NULL */
3424  int* best_result, /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
3425  int runs, /**< number of runs */
3426  int bestincstart, /**< best incumbent start vertex */
3427  SCIP_Real* cost, /**< arc costs */
3428  SCIP_Real* costrev, /**< reversed arc costs */
3429  SCIP_Real* hopfactor, /**< edge cost multiplicator for HC problems */
3430  SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
3431  SCIP_Bool* success /**< pointer to store whether a solution could be found */
3432  )
3433 {
3434  int beststart;
3435  const int mode = getTmMode(getTMheurData(scip), graph);
3436  const SCIP_Bool startsgiven = (runs >= 1 && (starts != NULL));
3437  TMBASE tmbase = { .dheap = NULL, .cost = cost, .costrev = costrev, .nodes_dist = NULL, .sdprofit1st = NULL,
3438  .startnodes = NULL, .result = NULL, .best_result = best_result,
3439  .nodes_pred = NULL, .connected = NULL,
3440  .best_obj = FARAWAY, .best_start = -1, .nruns = runs };
3441  TMVNOI tmvnoi = {NULL, NULL, NULL, NULL, NULL, NULL};
3442  TMALLSP tmallsp = {NULL, NULL};
3443 
3444 #ifndef NDEBUG
3445  {
3446  const int nedges = graph_get_nEdges(graph);
3447  assert(scip && cost && costrev && best_result);
3448  assert(graph->source >= 0 && nedges > 0);
3449  for( int e = 0; e < nedges; e++) assert(SCIPisGE(scip, cost[e], 0.0) && SCIPisGE(scip, costrev[e], 0.0));
3450  }
3451 #endif
3452 
3453  beststart = bestincstart;
3454  (*success) = FALSE;
3455 
3456 #ifdef SCIP_DEBUG
3457  SCIPdebugMessage("executing TM for graph (reduced info) \n");
3458  graph_printInfoReduced(graph);
3459 #endif
3460 
3461  if( graph_pc_isPcMw(graph) )
3462  graph_pc_2transcheck(scip, graph);
3463 
3464  SCIP_CALL( tmBaseInit(scip, graph, &tmbase) );
3465 
3466  if( mode == TM_VORONOI )
3467  {
3468  SCIP_CALL( tmVnoiInit(scip, graph, &tmvnoi) );
3469  }
3470  else if( mode == TM_SP )
3471  {
3472  SCIP_CALL( tmAllspInit(scip, graph, &tmallsp) );
3473  }
3474 
3475  SCIP_CALL( computeStarts(scip, graph, starts, startsgiven, nodepriority, &tmbase, &beststart) );
3476 
3477  /* call the main routines for SPH computations, differentiate between STP variants */
3478  if( graph_pc_isPcMw(graph) )
3479  {
3480  SCIP_CALL( runTmPcMW(scip, graph, cost, prize, pcmw_tmmode, beststart, nodepriority, &tmbase, success));
3481  }
3482  else if( graph->stp_type == STP_DHCSTP )
3483  {
3484  SCIP_CALL( runTmDhcstp(scip, graph, &tmbase, &tmallsp, &tmvnoi, hopfactor, success) );
3485  }
3486  else
3487  {
3488  SCIP_CALL( runTm(scip, graph, &tmbase, &tmallsp, &tmvnoi, success) );
3489  }
3490 
3491  if( mode == TM_SP )
3492  {
3493  tmAllspFree(scip, graph, &tmallsp);
3494  }
3495  else if( mode == TM_VORONOI )
3496  {
3497  tmVnoiFree(scip, graph, &tmvnoi);
3498  }
3499 
3500  tmBaseFree(scip, graph, &tmbase);
3501 
3502  if( *success )
3503  SCIPdebugMessage("final objective: %f \n", solstp_getObj(graph, tmbase.best_result, 0.0));
3504 
3505  return SCIP_OKAY;
3506 }
3507 
3508 /** run shortest path heuristic, but bias edge costs towards best current LP solution */
3510  SCIP* scip, /**< SCIP data structure */
3511  GRAPH* graph, /**< graph data structure */
3512  SCIP_HEUR* heur, /**< heuristic or NULL */
3513  int* result, /**< (uninitialized) array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
3514  int runs, /**< number of runs */
3515  SCIP_Bool* success /**< pointer to store whether a solution could be found */
3516  )
3517 {
3518  SCIP_VAR** vars = NULL;
3519  SCIP_HEURDATA* heurdata = NULL;
3520  SCIP_Real* xval = NULL;
3521  SCIP_Real* nodepriority = NULL;
3522  SCIP_Real* prize = NULL;
3523  SCIP_Real* cost = NULL;
3524  SCIP_Real* costrev = NULL;
3525  SCIP_Real randupper;
3526  SCIP_Real randlower;
3527  const int nnodes = graph_get_nNodes(graph);
3528  const int nedges = graph_get_nEdges(graph);
3529 
3530  assert(scip != NULL);
3531  assert(result != NULL);
3532  assert(success != NULL);
3533 
3534  assert(SCIPfindHeur(scip, "TM") != NULL);
3535  heurdata = SCIPheurGetData(SCIPfindHeur(scip, "TM"));
3536 
3537  vars = SCIPprobdataGetVars(scip);
3538  assert(vars != NULL);
3539 
3540  randupper = SCIPrandomGetReal(heurdata->randnumgen, 1.1, 2.5);
3541  randlower = SCIPrandomGetReal(heurdata->randnumgen, 1.1, randupper);
3542 
3543  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
3544  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
3545 
3546  /* LP was not solved */
3548  {
3549  xval = NULL;
3550  }
3551  else
3552  {
3553  SCIP_SOL* sol = NULL;
3554  SCIP_CALL(SCIPcreateSol(scip, &sol, heur));
3555 
3556  /* copy the current LP solution to the working solution */
3557  SCIP_CALL(SCIPlinkLPSol(scip, sol));
3558 
3559  xval = SCIPprobdataGetXval(scip, sol);
3560 
3561  SCIP_CALL(SCIPfreeSol(scip, &sol));
3562  }
3563 
3564  /* no LP solution? */
3565  if( xval == NULL )
3566  {
3567  BMScopyMemoryArray(cost, graph->cost, nedges);
3568 
3569  /* hop constraint problem? */
3570  if( graph->stp_type == STP_DHCSTP )
3571  {
3572  for( int e = 0; e < nedges; e++ )
3573  {
3574  if( SCIPvarGetUbGlobal(vars[e]) < 0.5 && SCIPvarGetUbGlobal(vars[flipedge_Uint(e)]) < 0.5 )
3575  cost[e] = BLOCKED;
3576  }
3577  }
3578  else
3579  {
3580  if( !graph_pc_isPcMw(graph) )
3581  {
3582  SCIP_CALL(SCIPallocBufferArray(scip, &nodepriority, nnodes));
3583 
3584  for( int k = 0; k < nnodes; k++ )
3585  {
3586  if( Is_term(graph->term[k]) )
3587  nodepriority[k] = (SCIP_Real) graph->grad[k];
3588  else
3589  nodepriority[k] = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
3590  }
3591  }
3592 
3593  for( int e = 0; e < nedges; e++ )
3594  if( SCIPvarGetUbGlobal(vars[e]) < 0.5 && SCIPvarGetUbGlobal(vars[flipedge_Uint(e)]) < 0.5 )
3595  cost[e] = MAX(cost[e], BLOCKED);
3596  }
3597  }
3598  else /* with LP solution */
3599  {
3600  /* NOTE does not seem to work well with other PC/MW variants to to bias the prizes... */
3601  if( graph->stp_type == STP_BRMWCSP )
3602  SCIP_CALL(SCIPallocBufferArray(scip, &prize, nnodes));
3603 
3604  SCIP_CALL(SCIPallocBufferArray(scip, &nodepriority, nnodes));
3605  initCostsAndPrioLP(scip, heurdata, vars, graph, randupper, randlower, xval, nodepriority, prize, cost);
3606  }
3607 
3608 
3609  /* set 0 edge costs to small epsilon (to keep some invariants valid) */
3610  {
3611  const SCIP_Real eps = SCIPepsilon(scip);
3612  const SCIP_Real tm_eps = getTmEdgeCostZeroOffset(scip, graph);
3613  assert(LE(eps, tm_eps));
3614 
3615  for( int e = 0; e < nedges; e++ )
3616  {
3617  assert(cost[e] >= -eps);
3618 
3619  if( cost[e] <= eps )
3620  {
3621  assert(SCIPisZero(scip, cost[e]));
3622 
3623  cost[e] = tm_eps;
3624  }
3625 
3626  assert(!SCIPisZero(scip, cost[e]));
3627  }
3628  }
3629 
3630  for( int e = 0; e < nedges; e++ )
3631  costrev[e] = cost[flipedge_Uint(e)];
3632 
3633  /* set (edge) result array to default */
3634  for( int e = 0; e < nedges; e++ )
3635  result[e] = UNKNOWN;
3636 
3637  /* build a Steiner tree */
3639  graph, NULL, prize, result, runs, heurdata->beststartnode, cost, costrev, &(heurdata->hopfactor), nodepriority, success));
3640 
3641 
3642  // todo test and move to extra method or remove
3643 #ifdef SCIP_DISABLED
3644  // todo extra method etc. just a test currently
3645  if( xval && graph_typeIsSpgLike(graph) )
3646  {
3647  int* termorg;
3648  int* soledges;
3649  SCIP_Real* nodes_inflow;
3650  const SCIP_Real termbound = SCIPrandomGetReal(heurdata->randnumgen, 0.95, 1.0);
3651  SCIP_Bool solFound = FALSE;
3652 
3653  SCIP_CALL(SCIPallocBufferArray(scip, &soledges, nedges));
3654  SCIP_CALL(SCIPallocBufferArray(scip, &termorg, nnodes));
3655  SCIP_CALL(SCIPallocBufferArray(scip, &nodes_inflow, nnodes));
3656  BMScopyMemoryArray(termorg, graph->term, nnodes);
3657 
3658  for( int k = 0; k < nnodes; k++ )
3659  nodes_inflow[k] = 0.0;
3660 
3661  for( int e = 0; e < nedges; e++ )
3662  {
3663  const int head = graph->head[e];
3664  nodes_inflow[head] += xval[e];
3665  }
3666 
3667  for( int e = 0; e < nedges; e++ )
3668  soledges[e] = UNKNOWN;
3669 
3670  for( int k = 0; k < nnodes; k++ )
3671  {
3672  if( !Is_term(graph->term[k]) && nodes_inflow[k] > termbound )
3673  graph_knot_chg(graph, k, STP_TERM);
3674  }
3675 
3677  graph, &(graph->source), prize, soledges, 1, heurdata->beststartnode, cost, costrev, &(heurdata->hopfactor),
3678  nodepriority, &solFound));
3679 
3680  for( int k = 0; k < nnodes; k++ )
3681  {
3682  if( graph->term[k] != termorg[k] )
3683  graph_knot_chg(graph, k, termorg[k]);
3684  }
3685 
3686  SCIP_CALL( solstp_pruneFromEdges(scip, graph, soledges) );
3687  SCIP_CALL( solstp_addSolToProb(scip, graph, soledges, heur, &solFound) );
3688 
3689  // printf("termbound=%f \n", termbound);
3690  // printf("success2=%d \n", solFound);
3691  // printf("obj1=%f obj2=%f \n", solstp_getObj(graph, result, SCIPprobdataGetOffset(scip)),
3692  // solstp_getObj(graph, soledges, SCIPprobdataGetOffset(scip)));
3693 
3694  SCIPfreeBufferArray(scip, &nodes_inflow);
3695  SCIPfreeBufferArray(scip, &termorg);
3696  SCIPfreeBufferArray(scip, &soledges);
3697  }
3698 #endif
3699 
3700  SCIPfreeBufferArrayNull(scip, &prize);
3701  SCIPfreeBufferArrayNull(scip, &nodepriority);
3702 
3703  SCIPfreeBufferArray(scip, &costrev);
3704  SCIPfreeBufferArray(scip, &cost);
3705 
3706  return SCIP_OKAY;
3707 }
3708 
3709 
3710 /** creates the TM primal heuristic and includes it in SCIP */
3712  SCIP* scip /**< SCIP data structure */
3713  )
3714 {
3715  SCIP_HEURDATA* heurdata;
3716  SCIP_HEUR* heur;
3717  char paramdesc[SCIP_MAXSTRLEN];
3718 
3719  /* create TM primal heuristic data */
3720  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
3721  heur = NULL;
3722 
3723  /* include primal heuristic */
3724  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
3726  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTM, heurdata) );
3727 
3728  assert(heur != NULL);
3729 
3730  /* set non fundamental callbacks via setter functions */
3731  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTM) );
3732  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeTM) );
3733  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitTM) );
3734 
3735 
3736  heurdata->ncalls = 0;
3737  heurdata->nlpiterations = -1;
3738  heurdata->nexecs = 0;
3739  heurdata->randseed = DEFAULT_RANDSEED;
3740 
3741 #ifdef WITH_UG
3742  heurdata->randseed += getUgRank();
3743 #endif
3744 
3745  /* add TM primal heuristic parameters */
3746  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/evalruns",
3747  "number of runs for eval",
3748  &heurdata->evalruns, FALSE, DEFAULT_EVALRUNS, -1, INT_MAX, NULL, NULL) );
3749  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/randseed",
3750  "random seed for heuristic",
3751  NULL, FALSE, DEFAULT_RANDSEED, 1, INT_MAX, paramChgdRandomseed, (SCIP_PARAMDATA*)heurdata) );
3752  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/initruns",
3753  "number of runs for init",
3754  &heurdata->initruns, FALSE, DEFAULT_INITRUNS, -1, INT_MAX, NULL, NULL) );
3755  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/leafruns",
3756  "number of runs for leaf",
3757  &heurdata->leafruns, FALSE, DEFAULT_LEAFRUNS, -1, INT_MAX, NULL, NULL) );
3758  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/rootruns",
3759  "number of runs for root",
3760  &heurdata->rootruns, FALSE, DEFAULT_ROOTRUNS, -1, INT_MAX, NULL, NULL) );
3761  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/duringlpfreq",
3762  "frequency for calling heuristic during LP loop",
3763  &heurdata->duringlpfreq, FALSE, DEFAULT_DURINGLPFREQ, 1, INT_MAX, NULL, NULL) );
3764  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/type",
3765  "Heuristic: 0 automatic, 1 TM_SP, 2 TM_VORONOI, 3 TM_DIJKSTRA",
3766  &heurdata->type, FALSE, DEFAULT_TYPE, 0, 3, NULL, NULL) );
3767  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/pcmwmode",
3768  "PC/MW solving mode: 0 simple, 1 bias, 2 full bias, 3 full tree, 4 all, 5 bias and full tree",
3769  NULL, FALSE, DEFAULT_PCMODE, 0, 4, NULL, NULL) );
3770  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/hardrunsmult",
3771  "multiplier of run for hard instances",
3772  &heurdata->hardrunsmult, FALSE, DEFAULT_HARD_RUNSMULT, 1.0, 100.0, NULL, NULL) );
3773 
3774  heurdata->hopfactor = DEFAULT_HOPFACTOR;
3775  heurdata->pcmw_mode = DEFAULT_PCMODE;
3776 
3777  /* create random number generator */
3778  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, heurdata->randseed, TRUE) );
3779 
3780  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "timing when heuristic should be called (%u:BEFORENODE, %u:DURINGLPLOOP, %u:AFTERLPLOOP, %u:AFTERNODE)", SCIP_HEURTIMING_BEFORENODE, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_HEURTIMING_AFTERLPLOOP, SCIP_HEURTIMING_AFTERNODE);
3781  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/timing", paramdesc,
3782  (int*) &heurdata->timing, TRUE, (int) HEUR_TIMING, (int) SCIP_HEURTIMING_BEFORENODE, 2 * (int) SCIP_HEURTIMING_AFTERPSEUDONODE - 1, NULL, NULL) ); /*lint !e713*/
3783 
3784  return SCIP_OKAY;
3785 }
Steiner tree relaxator.
#define HEUR_TIMING
Definition: heur_tm.c:56
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
static SCIP_RETCODE runTm(SCIP *scip, GRAPH *graph, TMBASE *tmbase, TMALLSP *tmallsp, TMVNOI *tmvnoi, SCIP_Bool *success)
Definition: heur_tm.c:2366
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_RETCODE reduce_sdprofitInit1stOnly(SCIP *, const GRAPH *, const SCIP_Real *, SDPROFIT **)
#define HEUR_FREQ
Definition: heur_tm.c:53
void graph_path_st(const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: graph_path.c:1199
static SCIP_DECL_HEURFREE(heurFreeTM)
Definition: heur_tm.c:2696
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
#define SCIP_HEURTIMING_DURINGLPLOOP
Definition: type_timing.h:71
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1468
int ** node_edge
Definition: heur_tm.c:135
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
static volatile int nterms
Definition: interrupt.c:38
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1017
static SCIP_RETCODE runTmDhcstp(SCIP *scip, GRAPH *graph, TMBASE *tmbase, TMALLSP *tmallsp, TMVNOI *tmvnoi, SCIP_Real *hopfactor, SCIP_Bool *success)
Definition: heur_tm.c:2635
static SCIP_RETCODE pcmwGetStartNodes(SCIP *scip, const SCIP_Real *nodepriority, int maxtmruns, int bestincstart, GRAPH *graph, int *terminalperm)
Definition: heur_tm.c:671
void graph_pc_getBiased(const GRAPH *, SCIP_Real *RESTRICT, SCIP_Real *RESTRICT)
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
void shortestpath_computeSteinerTreePcMw(const GRAPH *g, int startnode, const SCIP_Real *prize, SCIP_Bool costIsBiased, SPATHSPC *spaths_pc, SPATHS *spaths)
int *RESTRICT head
Definition: graphdefs.h:224
int * nodes_pred
Definition: heur_tm.c:104
SCIP_Bool graph_typeIsDirected(const GRAPH *)
Definition: graph_stats.c:83
struct TM_base_data TMBASE
SCIP_RETCODE SCIPStpHeurTMBuildTreeDc(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: heur_tm.c:3226
int source
Definition: graphdefs.h:195
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
int SCIPprobdataGetNTerms(SCIP *scip)
int ** node_base
Definition: heur_tm.c:134
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Bool graph_csr_costsAreInSync(const GRAPH *, const CSR *, const SCIP_Real *)
Definition: graph_util.c:1448
SCIP_RETCODE shortestpath_pcInit(SCIP *scip, const GRAPH *graph, const SCIP_Real *costs, const SCIP_Real *prizes, SPATHSPC **sppc)
Definition: shortestpath.c:893
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:670
signed int edge
Definition: graphdefs.h:287
#define DEFAULT_HOPFACTOR
Definition: heur_tm.h:42
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
Shortest path based algorithms for Steiner problems.
SCIP_RETCODE SCIPStpIncludeHeurTM(SCIP *scip)
Definition: heur_tm.c:3711
#define SCIP_MAXSTRLEN
Definition: def.h:293
CSR * csr
Definition: heur_tm.c:96
int terms
Definition: graphdefs.h:192
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
static SCIP_RETCODE computeSteinerTreeKeyNodesCsr(SCIP *scip, GRAPH *g, int startnode, TMBASE *tmbase)
Definition: heur_tm.c:1076
static SCIP_DECL_HEURINIT(heurInitTM)
Definition: heur_tm.c:2719
static SCIP_RETCODE computeSteinerTree(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, int start, int *result, TMALLSP *tmallsp, STP_Bool *connected, SCIP_RANDNUMGEN *randnumgen)
Definition: heur_tm.c:1253
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:78
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
#define SCIP_HEURTIMING_BEFORENODE
Definition: type_timing.h:70
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
const CSR * csr
Definition: shortestpath.h:50
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
Definition: graph_path.c:541
void graph_csr_build(const GRAPH *, const SCIP_Real *, CSR *)
Definition: graph_util.c:1351
static SCIP_Bool isTMSpType(const GRAPH *graph)
Definition: heur_tm.c:488
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
#define HEUR_DISPCHAR
Definition: heur_tm.c:51
SCIP_Real ** node_dist
Definition: heur_tm.c:131
includes methods for Steiner tree problem solutions
int *RESTRICT maxdeg
Definition: graphdefs.h:206
static void tmAllspFree(SCIP *scip, const GRAPH *graph, TMALLSP *tmallsp)
Definition: heur_tm.c:367
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
static void keyNodesResetTerms(const int *solnodes_degree, GRAPH *g)
Definition: heur_tm.c:1022
static SCIP_DECL_HEUREXEC(heurExecTM)
Definition: heur_tm.c:2754
SCIP_RETCODE SCIPStpHeurTMRunLP(SCIP *scip, GRAPH *graph, SCIP_HEUR *heur, int *result, int runs, SCIP_Bool *success)
Definition: heur_tm.c:3509
#define DEFAULT_LEAFRUNS
Definition: heur_tm.c:61
#define EAT_FREE
Definition: graphdefs.h:57
#define FALSE
Definition: def.h:87
void shortestpath_computeSteinerTreePcMwFull(const GRAPH *g, int startnode, SPATHS *spaths)
static void pcmwAdaptStarts(SCIP_HEURDATA *heurdata, const GRAPH *graph, int maxtmruns, int bestincstart, int *terminalperm)
Definition: heur_tm.c:640
int *RESTRICT inpbeg
Definition: graphdefs.h:202
SCIP_Real * cost
Definition: graphdefs.h:142
int *RESTRICT path_state
Definition: graphdefs.h:256
void graph_pathHeapAdd(const PATH *, int, int *RESTRICT, int *RESTRICT, int *)
static void buildTmAllSp(SCIP *scip, const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *costrev, TMALLSP *tmallsp)
Definition: heur_tm.c:2191
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
int * nodenterms
Definition: heur_tm.c:133
Problem data for stp problem.
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define SCIP_HEURTIMING_AFTERNODE
Definition: type_timing.h:92
#define STP_SAP
Definition: graphdefs.h:43
#define STP_DCSTP
Definition: graphdefs.h:47
#define SCIP_HEURTIMING_AFTERLPLOOP
Definition: type_timing.h:72
void solstp_convertCsrToGraph(SCIP *scip, const GRAPH *g, const CSR *csr, const int *soledge_csr, STP_Bool *RESTRICT solnode, int *RESTRICT soledge_g)
Definition: solstp.c:1976
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
SCIP_RETCODE solstp_pruneFromTmHeur(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *RESTRICT result, STP_Bool *RESTRICT connected)
Definition: solstp.c:1474
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
#define EAT_LAST
Definition: graphdefs.h:58
#define STP_SPG
Definition: graphdefs.h:42
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition: misc.c:1263
static SCIP_RETCODE computeSteinerTreeVnoi(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, int start, STP_Bool firstrun, TMVNOI *tmvnoi, int *result, STP_Bool *connected)
Definition: heur_tm.c:1697
#define SCIPdebugMessage
Definition: pub_message.h:87
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10003
DHEAP * dheap
Definition: heur_tm.c:100
static SCIP_Real getTmEdgeCostZeroOffset(SCIP *scip, const GRAPH *graph)
Definition: heur_tm.c:474
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Real graph_pc_getNonLeafTermOffset(SCIP *, const GRAPH *)
void shortestpath_computeSteinerTreeDirected(SCIP *scip, const GRAPH *g, int startnode, SPATHS *spaths)
SCIP_Real solstp_pcGetObjCsr(const GRAPH *g, const CSR *csr, const int *soledge_csr, const STP_Bool *solnode)
Definition: solstp.c:1872
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
int number
Definition: misc_stp.h:55
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
static SCIP_RETCODE computeSteinerTreeCsr(SCIP *scip, const GRAPH *g, int startnode, TMBASE *tmbase)
Definition: heur_tm.c:1047
STP_Bool * connected
Definition: heur_tm.c:108
static void pcmwSetEdgeCosts(const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *costorg, const SCIP_Real *costfullbiased, enum PCMW_TmMode pcmwmode, TMBASE *tmbase)
Definition: heur_tm.c:755
DENTRY * heap_entries
Definition: heur_tm.c:94
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
SCIP_Real SCIPepsilon(SCIP *scip)
void graph_csr_chgCosts(const GRAPH *, const SCIP_Real *, CSR *)
Definition: graph_util.c:1298
#define STP_TERM_NONE
Definition: graphdefs.h:62
real eps
int *RESTRICT mark
Definition: graphdefs.h:198
#define HEUR_DESC
Definition: heur_tm.c:50
static void initCostsAndPrioLP(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, const GRAPH *graph, SCIP_Real randupper, SCIP_Real randlower, const SCIP_Real *xval, SCIP_Real *RESTRICT nodepriority, SCIP_Real *RESTRICT prize, SCIP_Real *RESTRICT cost)
Definition: heur_tm.c:2053
SCIP_Bool graph_knotIsNWLeaf(const GRAPH *, int)
Definition: graph_node.c:35
static void pcmwUpdateBestSol(SCIP *scip, const GRAPH *graph, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:597
static SCIP_DECL_PARAMCHGD(paramChgdRandomseed)
Definition: heur_tm.c:204
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
static SCIP_RETCODE computeSteinerTreeDijk(SCIP *scip, GRAPH *g, int start, TMBASE *tmbase)
Definition: heur_tm.c:1116
#define HEUR_FREQOFS
Definition: heur_tm.c:54
int *RESTRICT oeat
Definition: graphdefs.h:231
void graph_path_st_pcmw(GRAPH *, SCIP_Real *, int *, const SCIP_Real *, const SCIP_Real *, SCIP_Bool, SCIP_Real *, int *, int, STP_Bool *)
Definition: graph_path.c:1430
int graph_pc_getRoot2PtermEdge(const GRAPH *, int)
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
static SCIP_RETCODE tmAllspInit(SCIP *scip, const GRAPH *graph, TMALLSP *tmallsp)
Definition: heur_tm.c:332
static void tmLpGetEdgeRandomizations(SCIP *scip, SCIP_HEURDATA *heurdata, const GRAPH *graph, SCIP_Bool *partrand, SCIP_Bool *totalrand)
Definition: heur_tm.c:2025
static SCIP_RETCODE computeSteinerTreeDijkBMw(SCIP *scip, GRAPH *g, const SCIP_Real *cost_org, const SCIP_Real *prize, int start, TMBASE *tmbase, SCIP_Bool *solfound)
Definition: heur_tm.c:1143
void SCIPsortRealIntInt(SCIP_Real *realarray, int *intarray1, int *intarray2, int len)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_Bool extended
Definition: graphdefs.h:267
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
int stp_type
Definition: graphdefs.h:264
SCIP_RETCODE graph_csr_allocWithEdgeId(SCIP *, int, int, CSR **)
Definition: graph_util.c:1270
int * best_result
Definition: heur_tm.c:107
void shortestpath_pcFree(SCIP *scip, SPATHSPC **sppc)
Definition: shortestpath.c:964
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
int * heap_position
Definition: heur_tm.c:93
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE runTmPcMW_mode(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *prize, enum PCMW_TmMode pcmwmode, int bestincstart, SCIP_Real *nodepriority, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:2446
void graph_pc_2transcheck(SCIP *, GRAPH *)
#define DEFAULT_DURINGLPFREQ
Definition: heur_tm.c:64
SCIP_Real SCIPprobdataGetOffset(SCIP *scip)
#define SCIPallocBuffer(scip, ptr)
Definition: scip_mem.h:113
SCIP_Bool SCIPprobdataProbIsAdversarial(SCIP *scip)
static void keyNodesSetTerms(SCIP *scip, const int *soledge, GRAPH *g, int *solnodes_degree)
Definition: heur_tm.c:983
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:2879
Definition: graphdefs.h:294
GNODE ** gnodearr
Definition: heur_tm.c:132
SCIP_Real dist
Definition: misc_stp.h:56
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * prize
Definition: graphdefs.h:210
static SCIP_RETCODE computeDegConsTree(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, int start, int *result, TMALLSP *tmallsp, SCIP_RANDNUMGEN *randnumgen, STP_Bool *connected, STP_Bool *solfound)
Definition: heur_tm.c:1434
SDPROFIT * sdprofit1st
Definition: heur_tm.c:95
static SCIP_RETCODE dhcstpWarmUp(SCIP *scip, GRAPH *graph, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:2225
SCIP_Real dist
Definition: graphdefs.h:286
int *RESTRICT grad
Definition: graphdefs.h:201
PCMW_TmMode
Definition: heur_tm.h:47
struct TM_all_shortestpath TMALLSP
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
#define DEFAULT_PCMODE
Definition: heur_tm.c:66
#define STP_DHCSTP
Definition: graphdefs.h:52
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
#define STP_RMWCSP
Definition: graphdefs.h:54
static SCIP_DECL_HEURCOPY(heurCopyTM)
Definition: heur_tm.c:2682
void reduce_sdprofitFree(SCIP *, SDPROFIT **)
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
int * term2edge
Definition: graphdefs.h:208
void shortestpath_computeSteinerTreeBiased(const GRAPH *g, const SDPROFIT *sdprofit, int startnode, SPATHS *spaths)
#define MST_MODE
Definition: graphdefs.h:98
#define DEFAULT_TYPE
Definition: heur_tm.c:65
static void computeSteinerTreeSingleNode(const GRAPH *graph, int node, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:1407
SCIP_Real solstp_getObjCsr(const GRAPH *g, const CSR *csr, const int *soledge_csr, const STP_Bool *solnode)
Definition: solstp.c:1921
#define LT(a, b)
Definition: portab.h:81
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
Definition: misc.c:1434
#define AUTO
Definition: heur_tm.c:72
unsigned char STP_Bool
Definition: portab.h:34
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
int GNODECmpByDist(void *first_arg, void *second_arg)
int SCIPprobdataGetNNodes(SCIP *scip)
SCIP_RETCODE solstp_pruneFromEdges(SCIP *scip, const GRAPH *g, int *result)
Definition: solstp.c:1432
void SCIPStpHeurTMBuildTree(SCIP *scip, GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:2932
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
void graph_path_st_rpcmw(GRAPH *, SCIP_Real *, int *, const SCIP_Real *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: graph_path.c:1988
void graph_heap_free(SCIP *, SCIP_Bool, SCIP_Bool, DHEAP **)
Definition: graph_util.c:1034
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
int *RESTRICT ieat
Definition: graphdefs.h:230
int *RESTRICT path_heap
Definition: graphdefs.h:255
#define STP_NWPTSPG
Definition: graphdefs.h:48
int best_start
Definition: heur_tm.c:110
SCIP_RETCODE graph_path_st_brmwcs(SCIP *, GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *, SCIP_Bool *)
Definition: graph_path.c:2146
SCIP_Real ** pathdist
Definition: heur_tm.c:121
static SCIP_RETCODE computeSteinerTreeDijkPcMw(SCIP *scip, GRAPH *g, const SCIP_Real *cost_org, const SCIP_Real *prize, SCIP_Bool costsAreBiased, int start, SPATHSPC *sppc, TMBASE *tmbase)
Definition: heur_tm.c:1168
int *RESTRICT tail
Definition: graphdefs.h:223
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
const SCIP_Real * cost
Definition: heur_tm.c:101
SCIP_Real best_obj
Definition: heur_tm.c:109
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10044
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_Bool stpsol_pruningIsPossible(const GRAPH *g, const int *result, const STP_Bool *connected)
Definition: solstp.c:1307
#define STP_TERM
Definition: graphdefs.h:61
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
#define flipedge_Uint(edge)
Definition: graphdefs.h:85
void graph_pc_markOrgGraph(GRAPH *)
struct TM_voronoi TMVNOI
static SCIP_RETCODE tmVnoiInit(SCIP *scip, const GRAPH *graph, TMVNOI *tmvnoi)
Definition: heur_tm.c:391
static SCIP_RETCODE tmBaseInit(SCIP *scip, const GRAPH *graph, TMBASE *tmbase)
Definition: heur_tm.c:226
static long * number
static SCIP_RETCODE runTmPcMW(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *prize, enum PCMW_TmMode pcmw_tmmode, int beststart, SCIP_Real *nodepriority, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:2585
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
Portable definitions.
int SCIPparamGetInt(SCIP_PARAM *param)
Definition: paramset.c:725
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1236
SCIP_Real * r
Definition: circlepacking.c:50
void shortestpath_computeSteinerTreeRpcMw(const GRAPH *g, int startnode, const SCIP_Real *prize, SPATHSPC *spaths_pc, SPATHS *spaths)
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
SCIP_Real * nodes_dist
Definition: heur_tm.c:103
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:125
#define TM_HARD_MAXNEDGES
Definition: heur_tm.c:70
int * startnodes
Definition: heur_tm.c:105
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
int * result
Definition: heur_tm.c:106
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
static SCIP_RETCODE computeSteinerTreeDijkPcMwFull(SCIP *scip, GRAPH *g, const SCIP_Real *cost_org, int start, TMBASE *tmbase)
Definition: heur_tm.c:1224
void graph_path_st_pcmw_full(GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: graph_path.c:1608
SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw(SCIP *scip, const GRAPH *g, SCIP_Bool useRootSym, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:3012
SCIP_Bool SCIPStpRelaxIsActive(SCIP *scip)
Definition: relax_stp.c:318
SCIP_Bool graph_pc_isUnrootedPcMw(const GRAPH *)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
void graph_csr_free(SCIP *, CSR **)
Definition: graph_util.c:1554
SCIP_RETCODE graph_heap_create(SCIP *, int, int *, DENTRY *, DHEAP **)
Definition: graph_util.c:992
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_VAR * a
Definition: circlepacking.c:57
#define TM_DIJKSTRA
Definition: heur_tm.c:75
SCIP_PQUEUE * pqueue
Definition: heur_tm.c:130
#define SCIP_HEURTIMING_AFTERPSEUDONODE
Definition: type_timing.h:76
#define SCIP_Real
Definition: def.h:177
#define BLOCKED
Definition: graphdefs.h:90
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
void shortestpath_computeSteinerTree(const GRAPH *g, int startnode, SPATHS *spaths)
#define DEFAULT_HARD_RUNSMULT
Definition: heur_tm.c:62
void graph_voronoi(const GRAPH *, const SCIP_Real *, const SCIP_Real *, const STP_Bool *, int *, PATH *)
Definition: graph_vnoi.c:333
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
int *RESTRICT outbeg
Definition: graphdefs.h:204
#define STP_BRMWCSP
Definition: graphdefs.h:55
#define HEUR_PRIORITY
Definition: heur_tm.c:52
shortest paths based primal heuristics for Steiner problems
static SCIP_HEURDATA * getTMheurData(SCIP *scip)
Definition: heur_tm.c:457
#define SCIP_Longint
Definition: def.h:162
int edges
Definition: graphdefs.h:219
void graph_pc_getOrgCostsCsr(SCIP *, const GRAPH *, CSR *)
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
void graph_pc_getOrgCosts(SCIP *, const GRAPH *, SCIP_Real *)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define HEUR_USESSUBSCIP
Definition: heur_tm.c:57
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE computeStarts(SCIP *scip, const GRAPH *graph, const int *orgstarts, SCIP_Bool startsgiven, SCIP_Real *nodepriority, TMBASE *tmbase, int *bestp)
Definition: heur_tm.c:787
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define UNKNOWN
Definition: sepa_mcf.c:4095
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define nnodes
Definition: gastrans.c:65
int solstp_getNedges(const GRAPH *g, const int *soledge)
Definition: solstp.c:2040
int * SCIPprobdataGetPctermsorder(SCIP *scip)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
#define TM_VORONOI
Definition: heur_tm.c:74
#define DEFAULT_EVALRUNS
Definition: heur_tm.c:59
const SCIP_Real * costrev
Definition: heur_tm.c:102
static SCIP_Bool pcmwUpdateBestSol_csrInSync(SCIP *scip, const GRAPH *graph, const TMBASE *tmbase)
Definition: heur_tm.c:168
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
static void updateBestSol(SCIP *scip, const GRAPH *graph, int startnode, SCIP_Bool solfound, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:529
#define DEFAULT_INITRUNS
Definition: heur_tm.c:60
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
static void tmVnoiFree(SCIP *scip, const GRAPH *graph, TMVNOI *tmvnoi)
Definition: heur_tm.c:424
int hoplimit
Definition: graphdefs.h:216
static int getTmMode(SCIP_HEURDATA *heurdata, const GRAPH *graph)
Definition: heur_tm.c:499
#define HEUR_NAME
Definition: heur_tm.c:49
includes various reduction methods for Steiner tree problems
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
#define STP_RPCSPG
Definition: graphdefs.h:45
void graph_printInfoReduced(const GRAPH *)
Definition: graph_stats.c:375
#define TM_SP
Definition: heur_tm.c:73
#define HEUR_MAXDEPTH
Definition: heur_tm.c:55
void graph_csr_buildCosts(const GRAPH *, const CSR *, const SCIP_Real *, SCIP_Real *RESTRICT)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
static void tmBaseFree(SCIP *scip, const GRAPH *graph, TMBASE *tmbase)
Definition: heur_tm.c:298
SCIP_RETCODE graph_voronoiExtend(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, SCIP_Real **, int **, int **, STP_Bool *, int *, int *, int *, int, int, int)
Definition: graph_vnoi.c:253
#define DEFAULT_ROOTRUNS
Definition: heur_tm.c:63
int graph_pc_getTwinTerm(const GRAPH *, int)
#define DEFAULT_RANDSEED
Definition: heur_tm.c:68
SCIP_RETCODE solstp_pruneFromTmHeur_csr(SCIP *scip, const GRAPH *g, SPATHS *spaths, int *RESTRICT result)
Definition: solstp.c:1515
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
CSR * csr_orgcosts
Definition: heur_tm.c:98