Scippy

SCIP

Solving Constraint Integer Programs

heur_rec.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_rec.c
17  * @brief Primal recombination heuristic for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements a recombination heuristic for Steiner problems, see
21  * "SCIP-Jack - A solver for STP and variants with parallelization extensions" (2017) by
22  * Gamrath, Koch, Maher, Rehfeldt and Shinano
23  *
24  * A list of all interface methods can be found in heur_rec.h
25  *
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 #include <assert.h>
31 #include <string.h>
32 #include <stdio.h>
33 #include "scip/scip.h"
34 #include "scip/scipdefplugins.h"
35 #include "scip/cons_linear.h"
36 #include "heur_rec.h"
37 #include "heur_prune.h"
38 #include "heur_slackprune.h"
39 #include "heur_local.h"
40 #include "graph.h"
41 #include "reduce.h"
42 #include "heur_tm.h"
43 #include "cons_stp.h"
44 #include "scip/pub_misc.h"
45 #include "probdata_stp.h"
46 #include "solstp.h"
47 #include "math.h"
48 
49 #define HEUR_NAME "rec"
50 #define HEUR_DESC "recombination heuristic for Steiner problems"
51 #define HEUR_DISPCHAR 'R'
52 #define HEUR_PRIORITY 100
53 #define HEUR_FREQ 1
54 #define HEUR_FREQOFS 0
55 #define HEUR_MAXDEPTH -1
56 #define HEUR_TIMING (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_MAXFREQREC FALSE /**< executions of the rec heuristic at maximum frequency? */
60 #define DEFAULT_MAXNSOLS 15 /**< default maximum number of (good) solutions be regarded in the subproblem */
61 #define DEFAULT_NUSEDSOLS 4 /**< number of solutions that will be taken into account */
62 #define DEFAULT_RANDSEED 1984 /**< random seed */
63 #define DEFAULT_NTMRUNS 100 /**< number of runs in TM heuristic */
64 #define DEFAULT_NWAITINGSOLS 4 /**< max number of new solutions to be available before executing the heuristic again */
65 
66 #define BOUND_MAXNTERMINALS 1000
67 #define BOUND_MAXNEDGES 20000
68 #define RUNS_RESTRICTED 3
69 #define RUNS_NORMAL 10
70 #define CYCLES_PER_RUN 3
71 #define REC_MAX_FAILS 4
72 #define REC_MIN_NSOLS 4
73 #define REC_ADDEDGE_FACTOR 1.0
74 
75 #define COST_MAX_POLY_x0 500
76 #define COST_MIN_POLY_x0 100
77 
78 #ifdef WITH_UG
79 int getUgRank(void);
80 #endif
81 
82 
83 
84 /*
85  * Data structures
86  */
87 
88 /** primal heuristic data */
89 struct SCIP_HeurData
90 {
91  int lastsolindex;
92  int bestsolindex; /**< best solution during the previous run */
93  int maxnsols; /**< maximum number of (good) solutions be regarded in the subproblem */
94  SCIP_Longint ncalls; /**< number of calls */
95  SCIP_Longint nlastsols; /**< number of solutions during the last run */
96  int ntmruns; /**< number of runs in TM heuristic */
97  int nusedsols; /**< number of solutions that will be taken into account */
98  int nselectedsols; /**< number of solutions actually selected */
99  int nwaitingsols; /**< number of new solutions before executing the heuristic again */
100  int nfailures; /**< number of failures since last successful call */
101  unsigned int randseed; /**< seed value for random number generator */
102  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
103  SCIP_Bool maxfreq; /**< should the heuristic be called at maximum frequency? */
104 };
105 
106 
107 /*
108  * Local methods
109  */
110 
111 /** information method for a parameter change of random seed */
112 static
113 SCIP_DECL_PARAMCHGD(paramChgdRandomseed)
114 { /*lint --e{715}*/
115  SCIP_HEURDATA* heurdata;
116  int newrandseed;
117 
118  newrandseed = SCIPparamGetInt(param);
119 
120  heurdata = (SCIP_HEURDATA*)SCIPparamGetData(param);
121  assert(heurdata != NULL);
122 
123  heurdata->randseed = (int) newrandseed;
124 
125  return SCIP_OKAY;
126 }
127 
128 
129 /** edge cost multiplier */
130 static
132  SCIP* scip, /**< SCIP data structure */
133  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
134  SCIP_Real avg /**< number of solutions containing this edge */
135  )
136 {
137  SCIP_Real normed;
138  int maxpolyx0;
139  int minpolyx0;
140 
141  int upper;
142  int lower;
143  int factor;
144 
145  /* if STP, then avg >= 2.0 */
146  assert(SCIPisGE(scip, avg, 1.0));
147  assert(heurdata->nusedsols >= 2);
148 
149  maxpolyx0 = COST_MAX_POLY_x0 * (heurdata->nusedsols - 1);
150  minpolyx0 = COST_MIN_POLY_x0 * (heurdata->nusedsols - 1);
151 
152  /* norm to [0,1] (STP) or [-1,1] and evaluate polynomials */
153  normed = (avg - 2.0) / ((double) heurdata->nusedsols - 1.0);
154  upper = (int) (maxpolyx0 - 2 * maxpolyx0 * normed + maxpolyx0 * (normed * normed));
155  lower = (int) (minpolyx0 - 2 * minpolyx0 * normed + minpolyx0 * (normed * normed));
156 
157  assert(SCIPisGE(scip, normed, -1.0) && SCIPisLE(scip, normed, 1.0));
158 
159  lower = MAX(0, lower);
160  upper = MAX(0, upper);
161 
162  factor = SCIPrandomGetInt(heurdata->randnumgen, lower, upper);
163  factor++;
164 
165  assert(factor <= COST_MAX_POLY_x0 * 3 + 1 || avg <= 2.0);
166  assert(factor >= 1);
167 
168  return factor;
169 }
170 
171 
172 static inline
174  const GRAPH* g,
175  IDX* curr,
176  const int* unodemap,
177  STP_Bool* RESTRICT stvertex
178  )
179 {
180  while( curr != NULL )
181  {
182  const int i = curr->index;
183 
184  stvertex[unodemap[g->orghead[i]]] = TRUE;
185  stvertex[unodemap[g->orgtail[i]]] = TRUE;
186 
187  curr = curr->parent;
188  }
189 }
190 
191 
192 static
194  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
195  int nsols, /**< number of solutions */
196  SCIP_Bool restrictheur /**< restrict heuristic? */
197 )
198 {
199  int randn;
200 
201  if( restrictheur )
202  randn = SCIPrandomGetInt(heurdata->randnumgen, 0, 3);
203  else
204  randn = SCIPrandomGetInt(heurdata->randnumgen, 0, 6);
205 
206  if( (randn <= 2) || (nsols < 3) )
207  heurdata->nusedsols = 2;
208  else if( (randn <= 4) || (nsols < 4) )
209  heurdata->nusedsols = 3;
210  else
211  heurdata->nusedsols = 4;
212 }
213 
214 
215 /** compute (heuristic) solution on reduced (and merged) problem */
216 static
218  SCIP* scip, /**< SCIP data structure */
219  const GRAPH* graph, /**< graph data */
220  const GRAPH* solgraph, /**< graph data */
221  const int* edgeancestor, /**< ancestor to edge */
222  const int* soledges, /**< old solution edges */
223  int* newsoledges, /**< new solution edges */
224  STP_Bool* stnodes /**< new solution nodes */
225 )
226 {
227  STP_Bool* solnodes;
228  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
229  const int nedges = graph->edges;
230  const int nnodes = graph->knots;
231 
232  for( int i = 0; i < nedges; i++ )
233  newsoledges[i] = UNKNOWN;
234 
235  for( int i = 0; i < nnodes; i++ )
236  stnodes[i] = FALSE;
237 
238  if( pcmw )
239  {
240  SCIP_CALL( SCIPallocBufferArray(scip, &solnodes, solgraph->orgknots) );
241 
242  for( int i = 0; i < solgraph->orgknots; i++ )
243  solnodes[i] = FALSE;
244  }
245 
246  if( solgraph->terms > 1 )
247  {
248  assert(soledges != NULL);
249  for( int e = 0; e < solgraph->edges; e++ )
250  {
251  if( soledges[e] == CONNECT )
252  {
253  /* iterate through list of ancestors */
254  if( graph->stp_type != STP_DCSTP )
255  {
256  IDX* curr = graph_edge_getAncestors(solgraph, e);
257 
258  while( curr != NULL )
259  {
260  const int i = edgeancestor[curr->index];
261 
262  stnodes[graph->head[i]] = TRUE;
263  stnodes[graph->tail[i]] = TRUE;
264 
265  if( pcmw )
266  {
267  assert(solgraph->orghead[curr->index] < solgraph->orgknots);
268  assert(solgraph->orgtail[curr->index] < solgraph->orgknots);
269 
270  solnodes[solgraph->orghead[curr->index]] = TRUE;
271  solnodes[solgraph->orgtail[curr->index]] = TRUE;
272  }
273 
274  curr = curr->parent;
275  }
276  }
277  else
278  {
279  IDX* curr = graph_edge_getAncestors(solgraph, e);
280  while( curr != NULL )
281  {
282  int i = edgeancestor[curr->index];
283  newsoledges[i] = CONNECT;
284 
285  curr = curr->parent;
286  }
287  }
288  }
289  }
290  } /* if( solgraph->terms > 1 ) */
291 
292  /* retransform edges fixed during graph reduction */
293  if( graph->stp_type != STP_DCSTP )
294  {
295  IDX* curr = graph_getFixedges(solgraph);
296 
297  while( curr != NULL )
298  {
299  const int i = edgeancestor[curr->index];
300 
301  stnodes[graph->head[i]] = TRUE;
302  stnodes[graph->tail[i]] = TRUE;
303  if( pcmw )
304  {
305  assert(solgraph->orghead[curr->index] < solgraph->orgknots);
306  assert(solgraph->orgtail[curr->index] < solgraph->orgknots);
307 
308  solnodes[solgraph->orghead[curr->index]] = TRUE;
309  solnodes[solgraph->orgtail[curr->index]] = TRUE;
310  }
311 
312  curr = curr->parent;
313  }
314  }
315  else
316  {
317  IDX* curr = graph_getFixedges(solgraph);
318 
319  while( curr != NULL )
320  {
321  const int i = edgeancestor[curr->index];
322  newsoledges[i] = CONNECT;
323  }
324  }
325 
326  if( pcmw )
327  {
328  STP_Bool* pcancestoredges;
329  SCIP_CALL(SCIPallocBufferArray(scip, &pcancestoredges, solgraph->orgedges));
330 
331  for( int k = 0; k < solgraph->orgedges; k++ )
332  pcancestoredges[k] = FALSE;
333 
334  SCIP_CALL(
335  solstp_markPcancestors(scip, solgraph->pcancestors, solgraph->orgtail, solgraph->orghead, solgraph->orgknots, solnodes, pcancestoredges, NULL, NULL, NULL ));
336 
337  for( int k = 0; k < solgraph->orgedges; k++ )
338  if( pcancestoredges[k] )
339  {
340  const int i = edgeancestor[k];
341  stnodes[graph->tail[i]] = TRUE;
342  stnodes[graph->head[i]] = TRUE;
343  }
344 
345  SCIPfreeBufferArray(scip, &pcancestoredges);
346  SCIPfreeBufferArrayNull(scip, &solnodes);
347  }
348 
349  return SCIP_OKAY;
350 }
351 
352 
353 /** compute (heuristic) solution on reduced (and merged) problem */
354 static
356  SCIP* scip, /**< SCIP data structure */
357  SCIP_HEURDATA* heurdata, /**< heuristic data */
358  const GRAPH* graph, /**< graph data */
359  GRAPH* solgraph, /**< graph data */
360  const int* edgeweight, /**< for each edge: number of solution that contain this edge */
361  const int* edgeancestor, /**< ancestor to edge edge */
362  SCIP_VAR** vars, /**< variables or NULL */
363  SCIP_Bool usestppool, /**< using STP pool? */
364  int* soledges, /**< solution edges */
365  SCIP_Bool* success /**< success? */
366 )
367 {
368  SCIP_Real* cost;
369  SCIP_Real* costrev;
370  SCIP_Real* prize = NULL;
371  SCIP_Real* nodepriority;
372  const int nsolnodes = solgraph->knots;
373  const int nsoledges = solgraph->edges;
374  const int probtype = graph->stp_type;
375  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
376 
377  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nsoledges) );
378  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nsoledges) );
379  SCIP_CALL( SCIPallocBufferArray(scip, &nodepriority, nsolnodes) );
380 
381  for( int i = 0; i < nsolnodes; i++ )
382  nodepriority[i] = 0.0;
383 
384  BMScopyMemoryArray(cost, solgraph->cost, nsoledges);
385 
386  for( int e = 0; e < nsoledges; e++ )
387  {
388  IDX* curr = graph_edge_getAncestors(solgraph, e);
389  SCIP_Real avg = 0.0;
390  int i = 0;
391  SCIP_Bool fixed = FALSE;
392 
393  while( curr != NULL )
394  {
395  i++;
396  avg += edgeweight[curr->index];
397  if( !usestppool && SCIPvarGetUbGlobal(vars[edgeancestor[curr->index]] ) < 0.5
398  && SCIPvarGetUbGlobal(vars[flipedge(edgeancestor[curr->index])] ) < 0.5 )
399  fixed = TRUE;
400 
401  curr = curr->parent;
402  }
403 
404  if( i > 0 )
405  {
406  avg /= (double) i;
407  assert(avg >= 1.0);
408  }
409 
410  /* is an ancestor edge fixed? */
411  if( fixed )
412  {
413  cost[e] = MAX(cost[e], BLOCKED);
414 
415  nodepriority[solgraph->head[e]] /= 2.0;
416  nodepriority[solgraph->tail[e]] /= 2.0;
417  }
418 
419  nodepriority[solgraph->head[e]] += avg - 1.0;
420  nodepriority[solgraph->tail[e]] += avg - 1.0;
421 
422  cost[e] *= edgecostmultiplier(scip, heurdata, avg);
423  }
424 
425  /* adapted prizes */
426  if( pcmw )
427  {
428  assert(solgraph->extended);
429 
430  SCIP_CALL( SCIPallocBufferArray(scip, &prize, nsolnodes) );
431 
432  for( int k = 0; k < nsolnodes; k++ )
433  {
434  if( Is_pseudoTerm(solgraph->term[k]) )
435  {
436  const int term = graph_pc_getTwinTerm(solgraph, k);
437  const int root2termedge = graph_pc_getRoot2PtermEdge(solgraph, term);
438 
439  assert(term >= 0 && root2termedge >= 0);
440  assert(solgraph->source != k);
441  assert(Is_term(solgraph->term[term]));
442  assert(solgraph->cost[root2termedge] > 0.0);
443 
444  prize[k] = cost[root2termedge];
445  }
446  else
447  {
448  prize[k] = solgraph->prize[k];
449  }
450  }
451  }
452 
453  for( int e = 0; e < nsoledges; e++ )
454  {
455  costrev[e] = cost[flipedge(e)];
456  soledges[e] = UNKNOWN;
457  }
458 
459  {
460  SCIP_Real hopfactor = 0.1;
461 
462  SCIP_CALL( SCIPStpHeurTMRun(scip, pcmode_fromheurdata, solgraph, NULL, prize, soledges, heurdata->ntmruns,
463  solgraph->source, cost, costrev, &hopfactor, nodepriority, success) );
464 
465  assert(*success || probtype == STP_DHCSTP || probtype == STP_DCSTP || SCIPisStopped(scip));
466  assert(*success == FALSE || solstp_isValid(scip, solgraph, soledges));
467  }
468 
469  SCIPfreeBufferArrayNull(scip, &prize);
470 
471  /* run local heuristic with original costs! */
472  if( !SCIPisStopped(scip) && probtype != STP_DHCSTP && probtype != STP_DCSTP
473  && probtype != STP_SAP && probtype != STP_NWSPG && probtype != STP_NWPTSPG )
474  {
475  SCIP_CALL( SCIPStpHeurLocalRun(scip, solgraph, soledges) );
476  assert(solstp_isValid(scip, solgraph, soledges));
477  }
478 
479  SCIPfreeBufferArray(scip, &nodepriority);
480  SCIPfreeBufferArray(scip, &costrev);
481  SCIPfreeBufferArray(scip, &cost);
482 
483  return SCIP_OKAY;
484 }
485 
486 
487 /** compute (heuristic) solution on reduced (and merged) problem */
488 static
490  SCIP* scip, /**< SCIP data structure */
491  SCIP_HEURDATA* heurdata, /**< heuristic data */
492  const GRAPH* graph, /**< graph data */
493  GRAPH* solgraph, /**< graph data */
494  REDSOL* redsol, /**< reduction solution */
495  const int* edgeweight, /**< for each edge: number of solution that contain this edge */
496  const int* edgeancestor, /**< ancestor to edge edge */
497  SCIP_VAR** vars, /**< variables or NULL */
498  SCIP_Bool usestppool, /**< using STP pool? */
499  int* soledges, /**< solution edges */
500  SCIP_Bool* success /**< success? */
501 )
502 {
503  assert(soledges != NULL);
504  assert(graph_valid(scip, solgraph));
505 
506  SCIPdebugMessage("REC: graph not completely reduced, nodes: %d, edges: %d, terminals: %d \n",
507  solgraph->knots, solgraph->edges, solgraph->terms);
508 
509  SCIP_CALL( graph_path_init(scip, solgraph) );
510 
511  SCIP_CALL( computeReducedProbSolutionBiased(scip, heurdata, graph, solgraph, edgeweight,
512  edgeancestor, vars, usestppool, soledges, success) );
513 
514  if( reduce_solUsesNodesol(redsol) )
515  {
516  SCIP_Real solval_red;
517  int* soledges_red;
518  SCIP_CALL(SCIPallocBufferArray(scip, &soledges_red, solgraph->edges));
519  SCIP_CALL(reduce_solGetEdgesol(scip, solgraph, redsol, &solval_red, soledges_red));
520 
521  SCIPdebugMessage("solval_red=%f solval_bias=%f\n", solval_red, solstp_getObj(solgraph, soledges, 0.0));
522 
523  if( LT(solval_red, FARAWAY) )
524  {
525  const SCIP_Real solval_bias = solstp_getObj(solgraph, soledges, 0.0);
526  assert(solstp_isValid(scip, solgraph, soledges_red));
527  assert(EQ(solval_red, solstp_getObj(solgraph, soledges_red, 0.0)));
528 
529  if( LT(solval_red, solval_bias) )
530  {
531  assert(LT(solstp_getObj(solgraph, soledges_red, 0.0), solstp_getObj(solgraph, soledges, 0.0)));
532 
533  BMScopyMemoryArray(soledges, soledges_red, solgraph->edges);
534  SCIPdebugMessage("updating best solution value: %f->%f \n", solval_bias, solval_red);
535  }
536  }
537 
538  SCIPfreeBufferArray(scip, &soledges_red);
539  }
540  else
541  {
542  assert(!graph_typeIsSpgLike(graph));
543  assert(!graph_pc_isPcMw(graph) || graph->stp_type == STP_RMWCSP);
544  }
545 
546  graph_path_exit(scip, solgraph);
547 
548  return SCIP_OKAY;
549 }
550 
551 
552 /** initialize solution vector and objective of incumbent */
553 static
555  SCIP* scip, /**< SCIP data structure */
556  const STPSOLPOOL* pool, /**< solution pool or NULL */
557  const GRAPH* graph, /**< graph data structure */
558  SCIP_VAR** vars, /**< problem variables */
559  int nsols, /**< number of solutions in pool (SCIP or STP) */
560  int newsolindex, /**< index of new solution */
561  double* incumentobj, /**< pointer to incumbent value */
562  int* incumbentedges /**< edges of solution to be used as recombination root */
563 )
564 {
565  const STP_Bool usestppool = (pool != NULL);
566  const int nedges = graph->edges;
567 
568  if( usestppool )
569  {
570  int i;
571  STPSOL** poolsols = pool->sols;
572 
573  assert(pool->nedges == graph->edges);
574 
575  for( i = 0; i < nsols; i++ )
576  if( newsolindex == poolsols[i]->index )
577  break;
578  assert(i < nsols);
579 
580  BMScopyMemoryArray(incumbentedges, poolsols[i]->soledges, nedges);
581  }
582  else
583  {
584  SCIP_SOL* newsol;
585  SCIP_SOL** sols = SCIPgetSols(scip);
586  int i;
587 
588  assert(sols != NULL);
589 
590  for( i = 0; i < nsols; i++ )
591  if( newsolindex == SCIPsolGetIndex(sols[i]) )
592  break;
593  assert(i < nsols);
594 
595  newsol = sols[i];
596 
597  for( int e = 0; e < nedges; e++ )
598  if( SCIPisEQ(scip, SCIPgetSolVal(scip, newsol, vars[e]), 1.0) )
599  incumbentedges[e] = CONNECT;
600  else
601  incumbentedges[e] = UNKNOWN;
602  }
603 
604  /* get objective value of incumbent */
605  *incumentobj = solstp_getObjBounded(graph, incumbentedges, 0.0, nedges);
606 }
607 
608 
609 #ifndef NDEBUG
610 /** any edge of given solution deleted? */
611 static
613  const GRAPH* graph, /**< graph structure */
614  const int solindex, /**< the index */
615  const STPSOLPOOL* pool /**< the pool */
616 )
617 {
618  const int nedges = graph->edges;
619  STPSOL* const poolsol = pool->sols[solindex];
620 
621  assert(pool);
622  assert(solindex >= 0 && solindex < pool->size);
623 
624  for( int i = 0; i < nedges; i += 2 )
625  {
626  if( graph->oeat[i] != EAT_FREE )
627  continue;
628 
629  if( (poolsol->soledges[i] == CONNECT || poolsol->soledges[i + 1] == CONNECT) )
630  return FALSE;
631  }
632 
633  return TRUE;
634 }
635 #endif
636 
637 
638 /** store solution in (SCIP or STP) pool */
639 static
641  SCIP* scip, /**< SCIP data structure */
642  STPSOLPOOL* pool, /**< STP solution pool or NULL */
643  SCIP_HEUR* heur, /**< heuristic or NULL */
644  const SCIP_Real incumentobj, /**< objective of solution to be added */
645  const int* incumbentedges, /**< edge array of solution to be added */
646  int nedges, /**< nedges */
647  int* newsolindex, /**< index of new solution */
648  SCIP_Bool* soladded /**< solution added? */
649 )
650 {
651  SCIPdebugMessage("REC: better solution found ... ");
652 
653  if( pool != NULL )
654  {
655  const int maxindex = pool->maxindex;
656  SCIP_CALL( solpool_addSol(scip, incumentobj, incumbentedges, pool, soladded) );
657 
658  if( *soladded )
659  {
660  assert(pool->maxindex == maxindex + 1);
661  *newsolindex = maxindex + 1;
662  SCIPdebugMessage("and added! \n");
663  }
664  else
665  {
666  *newsolindex = -1;
667  }
668  }
669  else
670  {
671  SCIP_Real* nval = NULL;
672 
673  SCIP_CALL( SCIPallocBufferArray(scip, &nval, nedges) );
674 
675  for( int e = 0; e < nedges; e++ )
676  {
677  if( incumbentedges[e] == CONNECT )
678  nval[e] = 1.0;
679  else
680  nval[e] = 0.0;
681  }
682 
683  SCIP_CALL( SCIPprobdataAddNewSol(scip, nval, heur, soladded) );
684 
685  if( *soladded )
686  {
687  SCIP_SOL** sols = SCIPgetSols(scip);
688  const int nsols = SCIPgetNSols(scip);
689  int idx = -1;
690 
691  SCIPdebugMessage("and added! \n");
692 
693  assert(nsols > 0);
694 
695  for( int i = 1; i < nsols; i++ )
696  if( SCIPsolGetIndex(sols[i]) > idx )
697  idx = SCIPsolGetIndex(sols[i]);
698 
699  assert(idx >= 0);
700  *newsolindex = idx;
701  }
702  SCIPfreeBufferArray(scip, &nval);
703 
704  }
705  return SCIP_OKAY;
706 }
707 
708 
709 /** select solutions to be merged */
710 static
712  SCIP* scip, /**< SCIP data structure */
713  const STPSOLPOOL* pool, /**< solution pool or NULL */
714  const GRAPH* graph, /**< graph data structure */
715  SCIP_HEURDATA* heurdata, /**< SCIP data structure */
716  SCIP_VAR** vars, /**< problem variables */
717  const int* incumbentedges, /**< edges of solution to be used as recombination root */
718  int* incumbentindex, /**< index of ancestor of incumbent solution */
719  int* selection, /**< selected solutions */
720  SCIP_Bool* success /**< could at least two solutions be selected? */
721  )
722 {
723  SCIP_SOL** sols = NULL;
724  STPSOL** poolsols = NULL;
725  int* perm;
726  int* soledgestmp;
727  STP_Bool* solselected;
728  STP_Bool* soledges;
729  int pos;
730  int nsols;
731  int maxnsols = heurdata->maxnsols;
732  int nselectedsols = 0;
733  const int nedges = graph->edges;
734  const int nusedsols = heurdata->nusedsols;
735  const SCIP_Bool usestppool = (pool != NULL);
736  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
737 
738  assert(selection != NULL);
739  assert(graph != NULL);
740 
741  if( !usestppool )
742  {
743  assert(vars != NULL);
744 
745  /* get solution data */
746  sols = SCIPgetSols(scip);
747  nsols = SCIPgetNSols(scip);
748  }
749  else
750  {
751  poolsols = pool->sols;
752  nsols = pool->size;
753  assert(nsols > 1);
754  }
755 
756  assert(nusedsols > 1);
757  assert(nsols >= nusedsols);
758 
759  /* allocate memory */
760  SCIP_CALL( SCIPallocBufferArray(scip, &solselected, nsols) );
761  SCIP_CALL( SCIPallocBufferArray(scip, &perm, nsols) );
762  SCIP_CALL( SCIPallocBufferArray(scip, &soledges, nedges / 2) );
763  SCIP_CALL( SCIPallocBufferArray(scip, &soledgestmp, nedges / 2) );
764 
765  for( int i = 0; i < nsols; i++ )
766  {
767  perm[i] = i;
768  solselected[i] = FALSE;
769  }
770 
771  if( usestppool )
772  {
773  for( pos = 0; pos < nsols; pos++ )
774  if( *incumbentindex == poolsols[pos]->index )
775  break;
776  }
777  else
778  {
779  for( pos = 0; pos < nsols; pos++ )
780  if( *incumbentindex == SCIPsolGetIndex(sols[pos]) )
781  break;
782  }
783  assert(pos < nsols);
784  solselected[pos] = TRUE;
785  selection[nselectedsols++] = pos;
786 
787  // mark current solution
788  for( int e = 0; e < nedges; e += 2 )
789  soledges[e / 2] = (incumbentedges[e] == CONNECT
790  || incumbentedges[e + 1] == CONNECT);
791 
792  maxnsols = MIN(nsols, maxnsols);
793 
794  if( !usestppool )
795  {
796  const int sqrtnallsols = (int) sqrt((double) nsols);
797 
798  if( sqrtnallsols >= REC_MIN_NSOLS && sqrtnallsols < maxnsols )
799  maxnsols = sqrtnallsols;
800  }
801 
802  SCIPrandomPermuteIntArray(heurdata->randnumgen, perm, 0, maxnsols);
803 
804  // check solutions to be merged
805  for( int i = 0; i < nsols; i++ )
806  {
807  if( solselected[perm[i]] == FALSE )
808  {
809  int eqnedges = 0;
810  int diffnedges = 0;
811  const int k = perm[i];
812  SCIP_SOL* solk = NULL;
813  const int* solKedges = NULL;
814 
815  if( usestppool )
816  solKedges = poolsols[k]->soledges;
817  else
818  solk = sols[k];
819 
820  for( int e = 0; e < nedges; e += 2 )
821  {
822  SCIP_Bool hit;
823 
824  if( usestppool )
825  hit = (solKedges[e] == CONNECT || solKedges[e + 1] == CONNECT);
826  else
827  hit = SCIPisEQ(scip, SCIPgetSolVal(scip, solk, vars[e]), 1.0)
828  || SCIPisEQ(scip, SCIPgetSolVal(scip, solk, vars[e + 1]), 1.0);
829 
830  if( hit )
831  {
832  if( soledges[e / 2] == FALSE )
833  soledgestmp[diffnedges++] = e / 2;
834  else
835  {
836  const int tail = graph->tail[e];
837  const int head = graph->head[e];
838 
839  /* no edge between root and dummy terminal? */
840  if( !pcmw || !(Is_term(graph->term[tail]) && Is_term(graph->term[head])) )
841  eqnedges++;
842  }
843  }
844  }
845 
846  /* enough similarities and differences with new solution? */
847  if( diffnedges > 5 && eqnedges > 0 )
848  {
849  SCIPdebugMessage("REC: different edges: %d same edges: %d \n", diffnedges, eqnedges);
850  selection[nselectedsols++] = k;
851  solselected[k] = TRUE;
852  *success = TRUE;
853 
854  for( int j = 0; j < diffnedges; j++ )
855  soledges[soledgestmp[j]] = TRUE;
856 
857  if( nselectedsols >= nusedsols )
858  break;
859  }
860  }
861  }
862 
863  assert(nselectedsols <= nusedsols);
864 
865  heurdata->nselectedsols = nselectedsols;
866 
867  SCIPdebugMessage("REC: selected %d sols \n", nselectedsols);
868 
869  /* free memory */
870  SCIPfreeBufferArray(scip, &soledgestmp);
871  SCIPfreeBufferArray(scip, &soledges);
872  SCIPfreeBufferArray(scip, &perm);
873  SCIPfreeBufferArray(scip, &solselected);
874 
875  return SCIP_OKAY;
876 }
877 
878 /** select solutions to be merged */
879 static
881  SCIP* scip, /**< SCIP data structure */
882  const STPSOLPOOL* pool, /**< solution pool or NULL */
883  SCIP_HEURDATA* heurdata, /**< SCIP data structure */
884  int* incumbentindex, /**< index of ancestor of incumbent solution */
885  int* selection, /**< selected solutions */
886  SCIP_Bool randomize /**< select solutions randomly? */
887  )
888 {
889  SCIP_SOL** sols = NULL; /* array of all solutions found so far */
890  STPSOL** poolsols = NULL;
891  int* perm;
892  STP_Bool* solselected;
893  int i;
894  int nsols; /* number of all available solutions */
895  int maxnsols;
896  int nusedsols; /* number of solutions to use in rec */
897  int nselectedsols;
898 
899  const SCIP_Bool usestppool = (pool != NULL);
900  assert(selection != NULL);
901 
902  if( usestppool )
903  {
904  poolsols = pool->sols;
905  nsols = pool->size;
906  assert(nsols > 1);
907  }
908  else
909  {
910  /* get solution data */
911  sols = SCIPgetSols(scip);
912  nsols = SCIPgetNSols(scip);
913  }
914 
915  maxnsols = heurdata->maxnsols;
916  nusedsols = heurdata->nusedsols;
917  assert(nusedsols <= nsols);
918  nselectedsols = 0;
919 
920  assert(nusedsols > 1);
921  assert(nsols >= nusedsols);
922 
923  /* allocate memory */
924  SCIP_CALL( SCIPallocBufferArray(scip, &solselected, nsols) );
925  SCIP_CALL( SCIPallocBufferArray(scip, &perm, nsols) );
926 
927  for( i = 0; i < nsols; i++ )
928  {
929  perm[i] = i;
930  solselected[i] = FALSE;
931  }
932 
933  if( usestppool )
934  {
935  for( i = 0; i < nsols; i++ )
936  if( *incumbentindex == poolsols[i]->index )
937  break;
938  }
939  else
940  {
941  for( i = 0; i < nsols; i++ )
942  if( *incumbentindex == SCIPsolGetIndex(sols[i]) )
943  break;
944  }
945 
946  assert(i < nsols);
947  solselected[i] = TRUE;
948  selection[nselectedsols++] = i;
949 
950  if( !randomize )
951  {
952  const int end = SCIPrandomGetInt(heurdata->randnumgen, 1, nusedsols - 1);
953  int shift = SCIPrandomGetInt(heurdata->randnumgen, end, 2 * nusedsols - 1);
954 
955  if( shift > nsols )
956  shift = nsols;
957 
958  SCIPrandomPermuteIntArray(heurdata->randnumgen, perm, 0, shift);
959 
960  for( i = 0; i < end; i++ )
961  {
962  if( solselected[perm[i]] == FALSE )
963  {
964  selection[nselectedsols++] = perm[i];
965  solselected[perm[i]] = TRUE;
966  }
967  }
968  }
969 
970  maxnsols = MIN(nsols, maxnsols);
971 
972  if( !usestppool )
973  {
974  const int sqrtnallsols = (int) sqrt(nsols);
975 
976  if( sqrtnallsols >= REC_MIN_NSOLS && sqrtnallsols < maxnsols )
977  maxnsols = sqrtnallsols;
978  }
979 
980  SCIPdebugMessage("maxnsols in REC %d \n", maxnsols);
981 
982  if( nselectedsols < nusedsols )
983  {
984  SCIPrandomPermuteIntArray(heurdata->randnumgen, perm, 0, maxnsols);
985  for( i = 0; i < maxnsols; i++ )
986  {
987  if( solselected[perm[i]] == FALSE )
988  {
989  selection[nselectedsols++] = perm[i];
990  if( nselectedsols >= nusedsols )
991  break;
992  }
993  }
994  }
995 
996  assert(nselectedsols <= nusedsols);
997 
998  SCIPdebugMessage("REC: selected %d sols \n", nselectedsols);
999 
1000  heurdata->nselectedsols = nselectedsols;
1001  SCIPfreeBufferArray(scip, &perm);
1002  SCIPfreeBufferArray(scip, &solselected);
1003 
1004  return SCIP_OKAY;
1005 }
1006 
1007 
1008 /** adapt merged solution graph for PC/MW */
1009 static
1011  const GRAPH* graph, /**< graph structure */
1012  STP_Bool* solnode, /**< solution nodes array */
1013  int* nsolnodes, /**< number of nodes pointer */
1014  STP_Bool* soledge, /**< solution edges array */
1015  int* nsoledges /**< number of edges pointer */
1016  )
1017 {
1018  const int rpcmw = graph_pc_isRootedPcMw(graph);
1019  const int oldroot = graph->source;
1020  const int nnodes = graph->knots;
1021 
1022  assert(solnode && soledge && nsolnodes && nsoledges);
1023  assert(graph->extended);
1024  assert(solnode[oldroot]);
1025 
1026  /* remove unnecessary dummy edges and add necessary ones */
1027  for( int k = 0; k < nnodes; k++ )
1028  {
1029  /* dummy terminal other than the root? */
1030  if( solnode[k] && graph_pc_knotIsDummyTerm(graph, k) && k != oldroot )
1031  {
1032  const int edgeroot = graph_pc_getRoot2PtermEdge(graph, k);
1033  const int edge2pterm = graph->term2edge[k];
1034  const int pterm = graph->head[edge2pterm];
1035 
1036  assert(graph->grad[k] == 2 && edge2pterm >= 0 && Is_pseudoTerm(graph->term[pterm]));
1037 
1038  if( !solnode[pterm] )
1039  {
1040  assert(soledge[edgeroot / 2]);
1041  assert(!soledge[edge2pterm / 2]);
1042 
1043  soledge[edgeroot / 2] = FALSE;
1044  solnode[k] = FALSE;
1045  (*nsoledges)--;
1046  (*nsolnodes)--;
1047  }
1048  else if( !soledge[edgeroot / 2] )
1049  {
1050  soledge[edgeroot / 2] = TRUE;
1051  (*nsoledges)++;
1052  }
1053  }
1054 
1055  /* pseudo terminal? */
1056  if( solnode[k] && Is_pseudoTerm(graph->term[k]) )
1057  {
1058  const int edge2term = graph->term2edge[k];
1059  const int term = graph->head[edge2term];
1060 
1061  if( !rpcmw )
1062  {
1063  const int edgeroot = graph_pc_getRoot2PtermEdge(graph, k);
1064 
1065  if( !soledge[edgeroot / 2] )
1066  {
1067  soledge[edgeroot / 2] = TRUE;
1068  (*nsoledges)++;
1069  }
1070  }
1071 
1072  if( !solnode[term] )
1073  {
1074  const int edgeroot2term = graph_pc_getRoot2PtermEdge(graph, term);
1075 
1076  solnode[term] = TRUE;
1077  (*nsolnodes)++;
1078 
1079  assert(!soledge[edge2term / 2]);
1080  assert(!soledge[edgeroot2term / 2]);
1081 
1082  soledge[edge2term / 2] = TRUE;
1083  soledge[edgeroot2term / 2] = TRUE;
1084  (*nsoledges) += 2;
1085  }
1086  }
1087  }
1088 
1089  assert(*nsolnodes >= 1);
1090  assert(*nsoledges >= 0);
1091 }
1092 
1093 
1094 /** adapt merged solution graph for DCSTP */
1095 static
1097  const GRAPH* graph, /**< graph structure */
1098  const STP_Bool* solnode, /**< solution nodes array */
1099  STP_Bool* soledge, /**< solution edges array */
1100  int* nsoledges /**< number of edges pointer */
1101  )
1102 {
1103  const int nnodes = graph->knots;
1104 
1105 
1106  for( int k = 0; k < nnodes; k++ )
1107  {
1108  if( Is_term(graph->term[k]) )
1109  {
1110  assert(solnode[k]);
1111  for( int i = graph->outbeg[k]; i != EAT_LAST; i = graph->oeat[i] )
1112  {
1113  if( solnode[graph->head[i]] && !soledge[i / 2] )
1114  {
1115  soledge[i / 2] = TRUE;
1116  (*nsoledges)++;
1117  }
1118  }
1119  }
1120  }
1121 }
1122 
1123 
1124 
1125 /** add additional edges to solution graph */
1126 static
1128  SCIP_HEURDATA* heurdata, /**< SCIP data structure */
1129  const GRAPH* graph, /**< graph structure */
1130  const STP_Bool* solnode, /**< solution nodes array */
1131  STP_Bool* soledge, /**< solution edges array */
1132  int* nsoledges /**< number of edges pointer */
1133  )
1134 {
1135  const int nedges = graph->edges;
1136 
1137  int naddedges = 0;
1138  const int offset = SCIPrandomGetInt(heurdata->randnumgen, 0, nedges - 1);
1139 
1140  for( int e = 0; e < nedges && naddedges <= (int)(REC_ADDEDGE_FACTOR * (*nsoledges)); e += 2 )
1141  {
1142  const int newedge = (e + offset) % nedges;
1143  int tail;
1144  int head;
1145 
1146  if( soledge[newedge / 2] )
1147  continue;
1148 
1149  // todo if fixed to zero, continue?
1150  if( graph->oeat[newedge] == EAT_FREE )
1151  continue;
1152 
1153  tail = graph->tail[newedge];
1154  head = graph->head[newedge];
1155 
1156  if( solnode[tail] && solnode[head] )
1157  {
1158  soledge[newedge / 2] = TRUE;
1159  naddedges++;
1160  }
1161  }
1162  SCIPdebugMessage("additional edges %d (orig: %d )\n", naddedges, *nsoledges);
1163 
1164  (*nsoledges) += naddedges;
1165 }
1166 
1167 
1168 /** merge selected solutions to a new graph */
1169 static
1171  SCIP* scip, /**< SCIP data structure */
1172  const STPSOLPOOL* pool, /**< solution pool or NULL */
1173  SCIP_HEURDATA* heurdata, /**< SCIP data structure */
1174  const GRAPH* graph, /**< graph structure */
1175  GRAPH** solgraph, /**< pointer to store new graph */
1176  const int* incumbentedges, /**< edges of solution to be used as recombination root */
1177  int* incumbentindex, /**< index of ancestor of incumbent solution */
1178  int** edgeancestor, /**< ancestor to edge edge */
1179  int** edgeweight, /**< for each edge: number of solution that contain this edge */
1180  SCIP_Bool* success, /**< new graph constructed? */
1181  SCIP_Bool randomize, /**< select solution randomly? */
1182  SCIP_Bool addedges /**< add additional edges between solution vertices? */
1183  )
1184 {
1185  GRAPH* newgraph = NULL;
1186  SCIP_SOL** sols = NULL;
1187  STPSOL** poolsols = NULL;
1188  SCIP_VAR** vars = NULL;
1189  int* solselection;
1190  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
1191  const SCIP_Bool usestppool = (pool != NULL);
1192 
1193  assert(scip != NULL);
1194  assert(graph != NULL);
1195 
1196  if( !usestppool )
1197  {
1198  sols = SCIPgetSols(scip);
1199  vars = SCIPprobdataGetEdgeVars(scip);
1200  assert(vars != NULL);
1201  assert(sols != NULL);
1202  }
1203  else
1204  {
1205  poolsols = pool->sols;
1206  }
1207 
1208  *success = TRUE;
1209  *edgeweight = NULL;
1210  *edgeancestor = NULL;
1211 
1212  /* allocate memory */
1213  SCIP_CALL( SCIPallocBufferArray(scip, &solselection, heurdata->nusedsols) );
1214 
1215  /* select solutions to be merged */
1216  if( pcmw || graph->stp_type == STP_DCSTP )
1217  SCIP_CALL( solgraphSelectSolsDiff(scip, pool, graph, heurdata, vars, incumbentedges, incumbentindex, solselection, success) );
1218  else
1219  SCIP_CALL( solgraphSelectSols(scip, pool, heurdata, incumbentindex, solselection, randomize) );
1220 
1221  if( *success )
1222  {
1223  int* dnodemap;
1224  STP_Bool* solnode; /* marks nodes contained in at least one solution */
1225  STP_Bool* soledge; /* marks edges contained in at least one solution */
1226  int j;
1227  int nsoledges = 0;
1228  int nsolnodes = 0;
1229  const int nedges = graph->edges;
1230  const int nnodes = graph->knots;
1231  const int selectedsols = heurdata->nselectedsols;
1232 
1233  SCIPdebugMessage("REC: successfully selected new solutions \n");
1234 
1235  assert(selectedsols > 0);
1236 
1237  SCIP_CALL( SCIPallocBufferArray(scip, &solnode, nnodes) );
1238  SCIP_CALL( SCIPallocBufferArray(scip, &dnodemap, nnodes) );
1239  SCIP_CALL( SCIPallocBufferArray(scip, &soledge, nedges / 2) );
1240 
1241  for( int i = 0; i < nnodes; i++ )
1242  {
1243  solnode[i] = FALSE;
1244  dnodemap[i] = UNKNOWN;
1245  }
1246 
1247  /* count and mark selected nodes and edges */
1248  for( int i = 0; i < nedges; i += 2 )
1249  {
1250  const int ihalf = i / 2;
1251  soledge[ihalf] = FALSE;
1252 
1253  if( graph->oeat[i] == EAT_FREE )
1254  continue;
1255 
1256  for( j = 0; j < selectedsols; j++ )
1257  {
1258  SCIP_Bool hit;
1259 
1260  if( j == 0 )
1261  {
1262  hit = (incumbentedges[i] == CONNECT
1263  || incumbentedges[i + 1] == CONNECT);
1264  }
1265  else if( usestppool )
1266  hit = (poolsols[solselection[j]]->soledges[i] == CONNECT
1267  || poolsols[solselection[j]]->soledges[i + 1] == CONNECT);
1268  else
1269  hit = (SCIPisEQ(scip, SCIPgetSolVal(scip, sols[solselection[j]], vars[i]), 1.0)
1270  || SCIPisEQ(scip, SCIPgetSolVal(scip, sols[solselection[j]], vars[i + 1]), 1.0));
1271 
1272  if( hit )
1273  {
1274  nsoledges++;
1275  soledge[ihalf] = TRUE;
1276  if( !solnode[graph->tail[i]] )
1277  {
1278  solnode[graph->tail[i]] = TRUE;
1279  nsolnodes++;
1280  }
1281  if( !solnode[graph->head[i]] )
1282  {
1283  solnode[graph->head[i]] = TRUE;
1284  nsolnodes++;
1285  }
1286  break;
1287  }
1288  }
1289  }
1290 
1291  /* need to adapt solution graph for PC/MW? */
1292  if( pcmw )
1293  {
1294  solgraphAdaptForPcMw(graph, solnode, &nsolnodes, soledge, &nsoledges);
1295  }
1296 
1297  /* add additional edges? */
1298  if( addedges )
1299  {
1300  solgraphAddEdges(heurdata, graph, solnode, soledge, &nsoledges);
1301  }
1302 
1303  if( graph->stp_type == STP_GSTP )
1304  {
1305  solgraphAdaptForDCSTP(graph, solnode, soledge, &nsoledges);
1306  }
1307 
1308  /* initialize new graph */
1309  SCIP_CALL( graph_init(scip, &newgraph, nsolnodes, 2 * nsoledges, 1) );
1310 
1311  if( graph->stp_type == STP_RSMT || graph->stp_type == STP_OARSMT || graph->stp_type == STP_GSTP )
1312  newgraph->stp_type = STP_SPG;
1313  else
1314  newgraph->stp_type = graph->stp_type;
1315 
1316  if( pcmw )
1317  {
1318  SCIP_CALL( graph_pc_initSubgraph(scip, newgraph) );
1319  }
1320 
1321  newgraph->hoplimit = graph->hoplimit;
1322  j = 0;
1323  for( int i = 0; i < nnodes; i++ )
1324  {
1325  if( solnode[i] )
1326  {
1327  if( pcmw )
1328  {
1329  assert(graph->extended);
1330 
1331  newgraph->prize[j] = graph->prize[i];
1332 #ifndef NDEBUG
1333  if( graph_pc_knotIsDummyTerm(graph, i) && i != graph->source )
1334  assert(0.0 == newgraph->prize[j]);
1335 #endif
1336  }
1337 
1338  graph_knot_add(newgraph, graph->term[i]);
1339  dnodemap[i] = j++;
1340  }
1341  }
1342 
1343  if( pcmw )
1344  {
1345  newgraph->extended = TRUE;
1346  newgraph->norgmodelknots = newgraph->knots - newgraph->terms;
1347 
1348  if( graph_pc_isRootedPcMw(graph) )
1349  newgraph->norgmodelknots += graph_pc_nFixedTerms(graph);
1350  }
1351 
1352  SCIPdebugMessage("REC: sol graph with nodes: %d, edges: %d, terminals: %d \n", nsolnodes, 2 * nsoledges, newgraph->terms);
1353 
1354  /* set root */
1355  newgraph->source = dnodemap[graph->source];
1356 
1357  assert(newgraph->source >= 0);
1358  assert(!graph_pc_isRootedPcMw(graph) || newgraph->prize[newgraph->source] == FARAWAY);
1359 
1360  /* copy max degrees*/
1361  if( graph->stp_type == STP_DCSTP )
1362  {
1363  SCIP_CALL( SCIPallocMemoryArray(scip, &(newgraph->maxdeg), nsolnodes) );
1364  for( int i = 0; i < nnodes; i++ )
1365  if( solnode[i] )
1366  newgraph->maxdeg[dnodemap[i]] = graph->maxdeg[i];
1367  }
1368  /* allocate memory */
1369  SCIP_CALL( SCIPallocMemoryArray(scip, edgeancestor, 2 * nsoledges) );
1370  SCIP_CALL( SCIPallocMemoryArray(scip, edgeweight, 2 * nsoledges) );
1371 
1372  for( int i = 0; i < 2 * nsoledges; i++ )
1373  (*edgeweight)[i] = 1;
1374 
1375  /* store original ID of each new edge (i.e. edge in the merged graph) */
1376  j = 0;
1377  assert(selectedsols == heurdata->nselectedsols);
1378  for( int i = 0; i < nedges; i += 2 )
1379  {
1380  if( soledge[i / 2] )
1381  {
1382  (*edgeancestor)[j++] = i;
1383  (*edgeancestor)[j++] = i + 1;
1384 
1385  graph_edge_addSubgraph(scip, graph, dnodemap, i, newgraph);
1386 
1387  /* (*edgeweight)[e]: number of solutions containing edge e */
1388  for( int k = 0; k < selectedsols; k++ )
1389  {
1390  SCIP_Bool hit;
1391 
1392  if( k == 0 )
1393  {
1394  hit = (incumbentedges[i] == CONNECT
1395  || incumbentedges[i + 1] == CONNECT);
1396  }
1397  else if( usestppool )
1398  hit = (poolsols[solselection[k]]->soledges[i] == CONNECT
1399  || poolsols[solselection[k]]->soledges[i + 1] == CONNECT);
1400  else
1401  hit = (SCIPisEQ(scip, SCIPgetSolVal(scip, sols[solselection[k]], vars[i]), 1.0)
1402  || SCIPisEQ(scip, SCIPgetSolVal(scip, sols[solselection[k]], vars[i + 1]), 1.0));
1403 
1404  /* is edge i or reversed edge in current solution? */
1405  if( hit )
1406  {
1407  (*edgeweight)[j - 2]++;
1408  (*edgeweight)[j - 1]++;
1409  }
1410  }
1411  }
1412  }
1413 
1414  assert(j == 2 * nsoledges);
1415 
1416  SCIP_CALL( graph_pc_finalizeSubgraph(scip, newgraph) );
1417 
1418  SCIPfreeBufferArray(scip, &soledge);
1419  SCIPfreeBufferArray(scip, &dnodemap);
1420  SCIPfreeBufferArray(scip, &solnode);
1421 
1422  if( !graph_valid(scip, newgraph) )
1423  {
1424  assert(usestppool);
1425 
1426  for( int k = 1; k < selectedsols; k++ )
1427  {
1428  assert(!poolSolIsUnreduced(graph, solselection[k], pool));
1429  }
1430 
1431  graph_free(scip, &newgraph, TRUE);
1432 
1433  *success = FALSE;
1434  }
1435 
1436  assert(!pcmw || graph_pc_nFixedTerms(graph) == graph_pc_nFixedTerms(newgraph));
1437  }
1438 
1439  SCIPfreeBufferArray(scip, &solselection);
1440 
1441  assert(*success || newgraph == NULL);
1442 
1443  *solgraph = newgraph;
1444 
1445  return SCIP_OKAY;
1446 }
1447 
1448 
1449 /*
1450  * primal heuristic specific interface methods
1451  */
1452 
1453 
1454 /** runs STP recombination heuristic */
1456  SCIP* scip, /**< SCIP data structure */
1457  STPSOLPOOL* pool, /**< STP solution pool or NULL */
1458  SCIP_HEUR* heur, /**< heuristic or NULL */
1459  SCIP_HEURDATA* heurdata, /**< heuristic data or NULL */
1460  const GRAPH* graph, /**< graph data */
1461  SCIP_VAR** vars, /**< variables or NULL */
1462  int* newsolindex, /**< index of new solution */
1463  int runs, /**< number of runs */
1464  int nsols, /**< number of solutions in pool (SCIP or STP) */
1465  SCIP_Bool restrictheur, /**< use restricted version of heuristic? */
1466  SCIP_Bool* solfound /**< new solution found? */
1467 )
1468 {
1469  int* newsoledges;
1470  int* incumbentedges;
1471  SCIP_Real incumentobj;
1472 
1473  const STP_Bool usestppool = (pool != NULL);
1474  const int nnodes = graph->knots;
1475  const int nedges = graph->edges;
1476  const int probtype = graph->stp_type;
1477  STP_Bool* stnodes;
1478 
1479  assert(runs >= 0);
1480  assert(graph != NULL);
1481  assert(scip != NULL);
1482  assert(*newsolindex >= 0);
1483 
1484  SCIPdebugMessage("REC: start \n");
1485 
1486  *solfound = FALSE;
1487 
1488  SCIP_CALL( SCIPallocBufferArray(scip, &newsoledges, nedges) );
1489  SCIP_CALL( SCIPallocBufferArray(scip, &incumbentedges, nedges) );
1490  SCIP_CALL( SCIPallocBufferArray(scip, &stnodes, nnodes) );
1491 
1492  /* initialize solution vector (edges) and objective of incumbent */
1493  initializeIncumbent(scip, pool, graph, vars, nsols, *newsolindex, &incumentobj, incumbentedges);
1494  SCIPdebugMessage("REC: incumbent obj: %f \n", incumentobj);
1495 
1496  if( heur == NULL )
1497  {
1498  heur = SCIPfindHeur(scip, "rec");
1499  assert(heur != NULL);
1500  heurdata = SCIPheurGetData(heur);
1501  assert(heurdata != NULL);
1502  }
1503 
1504  /* main loop (for recombination) */
1505  for( int v = 0, failcount = 0; v < CYCLES_PER_RUN * runs && !SCIPisStopped(scip); v++ )
1506  {
1507  GRAPH* solgraph = NULL;
1508  int* edgeweight;
1509  int* edgeancestor;
1510  SCIP_Bool success;
1511  const SCIP_Bool randomize = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 1);
1512  const SCIP_Bool addmoreedges = (SCIPrandomGetInt(heurdata->randnumgen, 0, 2) == 1);
1513 
1514  /* compute number of solutions to merge (and save in heurdata->nsols) */
1515  setHeurdataNUsedSols(heurdata, nsols, restrictheur);
1516  SCIPdebugMessage("REC: merge %d solutions \n", heurdata->nusedsols);
1517 
1518  /* build a new graph, consisting of several solutions */
1519  SCIP_CALL( buildsolgraph(scip, pool, heurdata, graph, &solgraph, incumbentedges, newsolindex,
1520  &edgeancestor, &edgeweight, &success, randomize, addmoreedges) );
1521 
1522  /* valid graph built? */
1523  if( success )
1524  {
1525  REDSOL* redsol = NULL;
1526  GRAPH* psolgraph;
1527  int* soledges = NULL;
1528  SCIP_Real pobj;
1529 
1530  SCIPdebugMessage("REC: solution successfully built \n");
1531  assert(graph_valid(scip, solgraph));
1532 
1533  /* reduce new graph */
1534  /* NOTE for MW the reductions seem to be quite expensive */
1535  if( !graph_typeIsUndirected(solgraph) || probtype == STP_DCSTP
1536  || probtype == STP_RMWCSP )
1537  {
1538  SCIP_CALL( reduce_solInit(scip, solgraph, FALSE, &redsol) );
1539  SCIP_CALL( reduce_exec(scip, solgraph, redsol, 0, 5, FALSE) );
1540  }
1541  else
1542  {
1543  const int minnreds = 5;
1544  SCIP_CALL( reduce_solInit(scip, solgraph, TRUE, &redsol) );
1545  SCIP_CALL( reduce_exec(scip, solgraph, redsol,
1546  STP_REDUCTION_ADVANCED, minnreds, FALSE) );
1547  }
1548 
1549  SCIP_CALL( graph_pack(scip, solgraph, &psolgraph, redsol, FALSE) );
1550 
1551  solgraph = psolgraph;
1552 
1553  /* if graph reduction solved the whole problem, solgraph has only one terminal */
1554  if( solgraph->terms > 1 )
1555  {
1556  SCIP_CALL( SCIPallocBufferArray(scip, &soledges, solgraph->edges) );
1557 
1558  SCIP_CALL( computeReducedProbSolution(scip, heurdata, graph, solgraph, redsol, edgeweight,
1559  edgeancestor, vars, usestppool, soledges, &success) );
1560  }
1561  assert(success || probtype == STP_DHCSTP || probtype == STP_DCSTP || SCIPisStopped(scip));
1562 
1563  reduce_solFree(scip, &redsol);
1564 
1565  /* retransform solution (soledges or single vertex) found above */
1566  if( success )
1567  SCIP_CALL( retransformReducedProbSolution(scip, graph, solgraph, edgeancestor, soledges, newsoledges, stnodes) );
1568 
1569  SCIPfreeBufferArrayNull(scip, &soledges);
1570  SCIPfreeMemoryArray(scip, &edgeancestor);
1571 
1572  graph_free(scip, &solgraph, TRUE);
1573 
1574  if( success )
1575  {
1576  /* prune solution (in the original graph) */
1577  if( probtype == STP_DCSTP )
1578  SCIP_CALL( SCIPStpHeurTMBuildTreeDc(scip, graph, newsoledges, stnodes) );
1579  else
1580  SCIP_CALL( solstp_prune(scip, graph, newsoledges, stnodes) );
1581 
1582  assert(solstp_isValid(scip, graph, newsoledges) || SCIPisStopped(scip));
1583  pobj = solstp_getObjBounded(graph, newsoledges, 0.0, nedges);
1584  }
1585  else
1586  {
1587  assert(probtype == STP_DHCSTP || SCIPisStopped(scip) || probtype == STP_DCSTP);
1588  pobj = FARAWAY;
1589  }
1590 
1591  SCIPdebugMessage("REC: new obj: %f \n", pobj);
1592 
1593  /* new solution better than incumbent? */
1594  if( !SCIPisStopped(scip) && SCIPisLT(scip, pobj, incumentobj) )
1595  {
1596  SCIPdebugMessage("...is better! \n");
1597  incumentobj = pobj;
1598  BMScopyMemoryArray(incumbentedges, newsoledges, nedges);
1599 
1600  if( (!restrictheur && failcount >= 1) || !(*solfound) )
1601  failcount--;
1602 
1603  *solfound = TRUE;
1604  }
1605  else
1606  {
1607  failcount++;
1608  }
1609  }
1610  else // no new graph could be built
1611  {
1612  assert(solgraph == NULL);
1613  failcount++;
1614  SCIPdebugMessage("REC: no new graph could be build \n");
1615  }
1616 
1617  SCIPfreeMemoryArray(scip, &edgeweight);
1618 
1619  /* too many fails? */
1620  if( failcount >= REC_MAX_FAILS )
1621  {
1622  SCIPdebugMessage("REC: too many fails, exit! \n");
1623  break;
1624  }
1625  } /* main recombination loop */
1626 
1627 
1628  /* improving solution found? */
1629  if( *solfound )
1630  {
1631  SCIP_CALL( poolAddSol(scip, pool, heur, incumentobj, incumbentedges, nedges, newsolindex, solfound) );
1632  }
1633  else
1634  {
1635  *newsolindex = -1;
1636  }
1637 
1638  SCIPdebugMessage("incumbentobj=%f newsolobj=%f \n", solstp_getObjBounded(graph, incumbentedges, 0.0, nedges), solstp_getObjBounded(graph, newsoledges, 0.0, nedges));
1639  SCIPdebugMessage("incumentobj=%f \n", incumentobj);
1640 
1641  SCIPfreeBufferArray(scip, &stnodes);
1642  SCIPfreeBufferArray(scip, &incumbentedges);
1643  SCIPfreeBufferArray(scip, &newsoledges);
1644 
1645  return SCIP_OKAY;
1646 }
1647 
1648 /** heuristic to exclude vertices or edges from a given solution (and inserting other edges) to improve objective */
1650  SCIP* scip, /**< SCIP data structure */
1651  const GRAPH* graph, /**< graph structure */
1652  const int* result, /**< edge solution array (UNKNOWN/CONNECT) */
1653  int* newresult, /**< new edge solution array (UNKNOWN/CONNECT) */
1654  int* dnodemap, /**< node array for internal use */
1655  STP_Bool* stvertex, /**< node array for internally marking solution vertices */
1656  SCIP_Bool* success /**< solution improved? */
1657  )
1658 {
1659  REDSOL* redsol;
1660  GRAPH* newgraph;
1661  int* unodemap;
1662  STP_Bool* solnodes;
1663  int j;
1664  int nsolterms;
1665  int nsoledges;
1666  int nsolnodes;
1667  const int root = graph->source;
1668  const int nedges = graph->edges;
1669  const int nnodes = graph->knots;
1670 
1671  assert(scip != NULL);
1672  assert(graph != NULL);
1673  assert(result != NULL);
1674  assert(stvertex != NULL);
1675  assert(success != NULL);
1676  assert(dnodemap != NULL);
1677  assert(newresult != NULL);
1678 
1679  *success = FALSE;
1680  assert(graph->stp_type == STP_MWCSP);
1681  assert(graph_valid(scip, graph));
1682 
1683  /* killed solution edge? */
1684  for( int e = 0; e < nedges; e++ )
1685  if( result[e] == CONNECT && graph->oeat[e] == EAT_FREE )
1686  return SCIP_OKAY;
1687 
1688  /*** 1. step: for solution S and original graph (V,E) initialize new graph (V[S], (V[S] X V[S]) \cup E) ***/
1689 
1690  BMSclearMemoryArray(stvertex, nnodes);
1691 
1692  nsolnodes = 1;
1693  nsolterms = 0;
1694  stvertex[root] = 1;
1695 
1696  /* mark nodes in solution */
1697  for( int e = 0; e < nedges; e++ )
1698  {
1699  if( result[e] == CONNECT )
1700  {
1701  int tail = graph->tail[e];
1702  int head = graph->head[e];
1703 
1704  if( tail == root )
1705  {
1706  /* there might be only one node */
1707  if( Is_pseudoTerm(graph->term[head]) )
1708  {
1709  stvertex[head] = 1;
1710  nsolterms++;
1711  nsolnodes++;
1712  }
1713 
1714  continue;
1715  }
1716 
1717  assert(!stvertex[head] );
1718  stvertex[head] = 1;
1719 
1720  if( Is_pseudoTerm(graph->term[head]) )
1721  nsolterms++;
1722  nsolnodes++;
1723  }
1724  }
1725 
1726  assert(nsolterms > 0);
1727 
1728  nsoledges = 0;
1729 
1730  /* count edges of new graph */
1731  for( int i = 0; i < nedges; i += 2 )
1732  if( stvertex[graph->tail[i]] && stvertex[graph->head[i]] && graph->oeat[i] != EAT_FREE )
1733  nsoledges++;
1734 
1735  nsoledges *= 2;
1736 
1737  /* create new graph */
1738  SCIP_CALL( graph_init(scip, &newgraph, nsolnodes, nsoledges, 1) );
1739 
1740  newgraph->stp_type = graph->stp_type;
1741  newgraph->extended = TRUE;
1742 
1743  SCIP_CALL( SCIPallocBufferArray(scip, &unodemap, nsolnodes) );
1744  SCIP_CALL( graph_pc_initSubgraph(scip, newgraph) );
1745 
1746  j = 0;
1747  for( int i = 0; i < nnodes; i++ )
1748  {
1749  if( stvertex[i] )
1750  {
1751  if( (!Is_term(graph->term[i])) )
1752  newgraph->prize[j] = graph->prize[i];
1753  else
1754  {
1755  assert(SCIPisZero(scip, graph->prize[i]));
1756 
1757  newgraph->prize[j] = 0.0;
1758  }
1759 
1760  graph_knot_add(newgraph, graph->term[i]);
1761  unodemap[j] = i;
1762  dnodemap[i] = j++;
1763  }
1764  else
1765  {
1766  dnodemap[i] = -1;
1767  }
1768  }
1769 
1770  assert(j == nsolnodes);
1771 
1772  /* set root */
1773  newgraph->source = dnodemap[root];
1774  assert(newgraph->source >= 0 && newgraph->source < nsolnodes);
1775 
1776  /* add edges */
1777  for( int i = 0; i < nedges; i += 2 )
1778  if( stvertex[graph->tail[i]] && stvertex[graph->head[i]] && graph->oeat[i] != EAT_FREE )
1779  graph_edge_addSubgraph(scip, graph, dnodemap, i, newgraph);
1780 
1781  assert(newgraph->edges == nsoledges);
1782 
1783  SCIP_CALL( graph_pc_finalizeSubgraph(scip, newgraph) );
1784 
1785 
1786  /*** step 2: presolve ***/
1787 
1788  newgraph->norgmodelknots = nsolnodes;
1789 
1790  SCIP_CALL( reduce_solInit(scip, newgraph, FALSE, &redsol) );
1791 
1792  SCIP_CALL( reduce_exec(scip, newgraph, redsol, 1, 5, FALSE) );
1793 
1794  reduce_solFree(scip, &redsol);
1795 
1796 
1797  /*** step 3: compute solution on new graph ***/
1798 
1799  SCIP_CALL( graph_path_init(scip, newgraph) );
1800 
1801  /* compute Steiner tree to obtain upper bound */
1803  newgraph, NULL, NULL, newresult, MIN(50, nsolterms), newgraph->source, newgraph->cost, newgraph->cost, NULL, NULL, success) );
1804 
1805  graph_path_exit(scip, newgraph);
1806 
1807  assert(*success);
1808  assert(solstp_isValid(scip, newgraph, newresult));
1809 
1810 
1811  /*** step 4: retransform solution to original graph ***/
1812 
1813 
1814  BMSclearMemoryArray(stvertex, nnodes);
1815 
1816  for( int e = 0; e < nsoledges; e++ )
1817  if( newresult[e] == CONNECT )
1818  marksolverts(newgraph, graph_edge_getAncestors(newgraph, e), unodemap, stvertex);
1819 
1820  /* retransform edges fixed during graph reduction */
1821  marksolverts(newgraph, graph_getFixedges(newgraph), unodemap, stvertex);
1822 
1823  for( int k = 0; k < nsolnodes; k++ )
1824  if( stvertex[unodemap[k]] )
1825  marksolverts(newgraph, newgraph->pcancestors[k], unodemap, stvertex);
1826 
1827  SCIP_CALL(SCIPallocBufferArray(scip, &solnodes, nsolnodes));
1828 
1829  for( int k = 0; k < nsolnodes; k++ )
1830  solnodes[k] = FALSE;
1831 
1832  for( int k = 0; k < nnodes; k++ )
1833  if( stvertex[k] )
1834  {
1835  assert(dnodemap[k] < nsolnodes);
1836  solnodes[dnodemap[k]] = TRUE;
1837  }
1838 
1839  SCIP_CALL( solstp_markPcancestors(scip, newgraph->pcancestors, newgraph->orgtail, newgraph->orghead, nsolnodes, solnodes, NULL, NULL, NULL, NULL ) );
1840 
1841  for( int k = 0; k < nsolnodes; k++ )
1842  if( solnodes[k] )
1843  stvertex[unodemap[k]] = TRUE;
1844 
1845  SCIPfreeBufferArray(scip, &solnodes);
1846 
1847  assert(graph_pc_isPcMw(graph));
1848 
1849  SCIP_CALL( solstp_prune(scip, graph, newresult, stvertex) );
1850 
1851  /* solution better than original one? */
1852 
1853  if( SCIPisLT(scip, solstp_getObjBounded(graph, newresult, 0.0, nedges),
1854  solstp_getObjBounded(graph, result, 0.0, nedges)) )
1855  {
1856  *success = TRUE;
1857  SCIPdebugMessage("success %f < %f \n", solstp_getObjBounded(graph, newresult, 0.0, nedges), solstp_getObjBounded(graph, result, 0.0, nedges));
1858  }
1859  else
1860  {
1861  SCIPdebugMessage("no improvements %f >= %f \n", solstp_getObjBounded(graph, newresult, 0.0, nedges), solstp_getObjBounded(graph, result, 0.0, nedges));
1862  *success = FALSE;
1863  }
1864 
1865  assert(solstp_isValid(scip, graph, newresult));
1866 
1867  if( !solstp_isValid(scip, graph, newresult) )
1868  *success = FALSE;
1869 
1870  SCIPfreeBufferArray(scip, &unodemap);
1871  graph_free(scip, &newgraph, TRUE);
1872 
1873  return SCIP_OKAY;
1874 }
1875 
1876 
1877 
1878 
1879 /*
1880  * Callback methods of primal heuristic
1881  */
1882 
1883 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1884 static
1886 {
1887  SCIP_HEURDATA* heurdata;
1888 
1889  heurdata = SCIPheurGetData(heur);
1890  assert(heurdata != NULL);
1891 
1892  SCIPheurSetData(heur, heurdata);
1893 
1894  return SCIP_OKAY;
1895 }
1896 
1897 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1898 static
1900 { /*lint --e{715}*/
1901  assert(scip != NULL);
1902  assert(heur != NULL);
1903  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1904 
1905  /* call inclusion method of primal heuristic */
1907 
1908  return SCIP_OKAY;
1909 }
1910 
1911 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1912 static
1914 { /*lint --e{715}*/
1915  SCIP_HEURDATA* heurdata;
1916 
1917  assert(heur != NULL);
1918  assert(scip != NULL);
1919 
1920  /* get heuristic data */
1921  heurdata = SCIPheurGetData(heur);
1922  assert(heurdata != NULL);
1923 
1924  /* free random number generator */
1925  SCIPfreeRandom(scip, &heurdata->randnumgen);
1926 
1927  /* free heuristic data */
1928  SCIPfreeMemory(scip, &heurdata);
1929  SCIPheurSetData(heur, NULL);
1930 
1931  return SCIP_OKAY;
1932 }
1933 
1934 /** initialization method of primal heuristic (called after problem was transformed) */
1935 static
1937 { /*lint --e{715}*/
1938 
1939  assert(heur != NULL);
1940  assert(scip != NULL);
1941 
1942  return SCIP_OKAY;
1943 }
1944 
1945 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
1946 static
1947 SCIP_DECL_HEURINITSOL(heurInitsolRec)
1948 { /*lint --e{715}*/
1949  SCIP_HEURDATA* heurdata;
1950 
1951  assert(heur != NULL);
1952  assert(scip != NULL);
1953 
1954  heurdata = SCIPheurGetData(heur);
1955  assert(heurdata != NULL);
1956 
1957  /* initialize data */
1958  heurdata->nselectedsols = 0;
1959  heurdata->nusedsols = DEFAULT_NUSEDSOLS;
1960  heurdata->randseed = DEFAULT_RANDSEED;
1961  heurdata->nselectedsols = 0;
1962  heurdata->ncalls = 0;
1963  heurdata->nlastsols = 0;
1964  heurdata->lastsolindex = -1;
1965  heurdata->bestsolindex = -1;
1966  heurdata->nfailures = 0;
1967 
1968 #ifdef WITH_UG
1969  heurdata->randseed += getUgRank();
1970 #endif
1971 
1972  return SCIP_OKAY;
1973 }
1974 
1975 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
1976 static
1977 SCIP_DECL_HEUREXITSOL(heurExitsolRec)
1978 { /*lint --e{715}*/
1979 
1980  return SCIP_OKAY;
1981 }
1982 
1983 /** execution method of primal heuristic */
1984 static
1986 { /*lint --e{715}*/
1987  SCIP_HEURDATA* heurdata;
1988  SCIP_PROBDATA* probdata;
1989  SCIP_VAR** vars;
1990  SCIP_SOL** sols;
1991  GRAPH* graph;
1992  SCIP_Longint nallsols;
1993  SCIP_Bool pcmw;
1994  SCIP_Bool solfound;
1995  SCIP_Bool restrictheur;
1996 
1997  int runs;
1998  int nsols;
1999  int solposition;
2000  int probtype;
2001  int newsolindex;
2002  int nreadysols;
2003  int bestsolindex;
2004  int nwaitingsols;
2005 
2006  assert(heur != NULL);
2007  assert(scip != NULL);
2008  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2009  assert(result != NULL);
2010 
2011  /* get heuristic data */
2012  heurdata = SCIPheurGetData(heur);
2013  assert(heurdata != NULL);
2014 
2015  /* get problem data */
2016  probdata = SCIPgetProbData(scip);
2017  assert(probdata != NULL);
2018 
2019  /* get graph */
2020  graph = SCIPprobdataGetGraph(probdata);
2021  assert(graph != NULL);
2022 
2023  probtype = graph->stp_type;
2024  *result = SCIP_DIDNOTRUN;
2025 
2026  if( probtype == STP_BRMWCSP )
2027  return SCIP_OKAY;
2028 
2029  SCIPdebugMessage("REC: checking ... \n");
2030 
2031  pcmw = graph_pc_isPcMw(graph);
2032  nallsols = SCIPgetNSolsFound(scip);
2033  nreadysols = SCIPgetNSols(scip);
2034 
2035  /* only call heuristic if sufficiently many solutions are available */
2036  if( nreadysols < DEFAULT_NUSEDSOLS )
2037  return SCIP_OKAY;
2038 
2039  if( probtype == STP_DCSTP )
2040  return SCIP_OKAY;
2041 
2042  nwaitingsols = heurdata->nwaitingsols;
2043 
2045  {
2046  nwaitingsols--;
2047  }
2048 
2049  /* suspend heuristic?
2050  * todo case distinction not really needed anymore... */
2051  if( pcmw || probtype == STP_DHCSTP )
2052  {
2053  int i;
2054  if( heurdata->ncalls == 0 )
2055  i = 0;
2056  else if( heurdata->maxfreq )
2057  i = 1;
2058  else
2059  i = MIN(nwaitingsols, heurdata->nfailures);
2060 
2061  if( nallsols <= heurdata->nlastsols + i )
2062  return SCIP_OKAY;
2063  }
2064  else
2065  {
2066  int i;
2067  if( heurdata->maxfreq )
2068  i = 1;
2069  else
2070  i = MIN(nwaitingsols, heurdata->nfailures);
2071 
2072  if( nallsols <= heurdata->nlastsols + i && heurdata->bestsolindex == SCIPsolGetIndex(SCIPgetBestSol(scip)) )
2073  return SCIP_OKAY;
2074  }
2075 
2076  /* get edge variables */
2077  vars = SCIPprobdataGetVars(scip);
2078  assert(vars != NULL);
2079  assert(vars[0] != NULL);
2080 
2081  *result = SCIP_DIDNOTFIND;
2082  heurdata->ncalls++;
2083 
2084  restrictheur = (graph->terms > BOUND_MAXNTERMINALS && graph->edges > BOUND_MAXNEDGES);
2085 
2086  if( restrictheur )
2087  runs = RUNS_RESTRICTED;
2088  else
2089  runs = RUNS_NORMAL;
2090 
2091  if( runs > nreadysols )
2092  runs = nreadysols;
2093 
2094  assert(runs > 0);
2095 
2096  sols = SCIPgetSols(scip);
2097  assert(sols != NULL);
2098 
2099  bestsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip));
2100 
2101  /* first run or exotic variant? */
2102  if( heurdata->lastsolindex == -1 || probtype == STP_DHCSTP || probtype == STP_DCSTP )
2103  newsolindex = bestsolindex;
2104  else
2105  {
2106  /* get best new solution */
2107 
2108  SCIP_Real minobj = FARAWAY;
2109  const int lastindex = heurdata->lastsolindex;
2110 
2111  newsolindex = -1;
2112  assert(lastindex >= 0);
2113 
2114  for( int i = 0; i < nreadysols; i++ )
2115  {
2116  const int currindex = SCIPsolGetIndex(sols[i]);
2117  if( currindex > lastindex && SCIPisLT(scip, SCIPgetSolOrigObj(scip, sols[i]), minobj) )
2118  {
2119  newsolindex = currindex;
2120  minobj = SCIPgetSolOrigObj(scip, sols[i]);
2121  SCIPdebugMessage("REC: better start solution, obj: %f \n", minobj);
2122  }
2123  }
2124  if( newsolindex == -1 )
2125  {
2126  SCIPdebugMessage("REC: random start solution\n");
2127  newsolindex = SCIPsolGetIndex(sols[SCIPrandomGetInt(heurdata->randnumgen, 0, nreadysols - 1)]);
2128  }
2129  }
2130 
2131  /* run the actual heuristic */
2132  SCIP_CALL( SCIPStpHeurRecRun(scip, NULL, heur, heurdata, graph, vars, &newsolindex, runs, nreadysols, restrictheur, &solfound) );
2133 
2134  /* save latest solution index */
2135  solposition = 0;
2136  nsols = SCIPgetNSols(scip);
2137  assert(nsols > 0);
2138  sols = SCIPgetSols(scip);
2139 
2140  for( int i = 1; i < nsols; i++ )
2141  if( SCIPsolGetIndex(sols[i]) > SCIPsolGetIndex(sols[solposition]) )
2142  solposition = i;
2143 
2144  if( solfound )
2145  *result = SCIP_FOUNDSOL;
2146 
2147  if( SCIPsolGetIndex(SCIPgetBestSol(scip)) == bestsolindex )
2148  heurdata->nfailures++;
2149  else
2150  heurdata->nfailures = 0;
2151 
2152  heurdata->lastsolindex = SCIPsolGetIndex(sols[solposition]);
2153  heurdata->bestsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip));
2154  heurdata->nlastsols = SCIPgetNSolsFound(scip);
2155 
2156  return SCIP_OKAY;
2157 }
2158 
2159 
2160 /** creates the rec primal heuristic and includes it in SCIP */
2162  SCIP* scip /**< SCIP data structure */
2163  )
2164 {
2165  SCIP_HEURDATA* heurdata;
2166  SCIP_HEUR* heur;
2167 
2168  /* create Rec primal heuristic data */
2169  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
2170 
2171  /* include primal heuristic */
2172  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
2174  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRec, heurdata) );
2175 
2176  assert(heur != NULL);
2177 
2178  /* set non-NULL pointers to callback methods */
2179  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRec) );
2180  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRec) );
2181  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRec) );
2182  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRec) );
2183  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolRec) );
2184  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolRec) );
2185 
2186  /* add rec primal heuristic parameters */
2187  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/nwaitingsols",
2188  "number of solution findings to be in abeyance",
2189  &heurdata->nwaitingsols, FALSE, DEFAULT_NWAITINGSOLS, 1, INT_MAX, NULL, NULL) );
2190 
2191  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/randseed",
2192  "random seed for heuristic",
2193  NULL, FALSE, DEFAULT_RANDSEED, 1, INT_MAX, paramChgdRandomseed, (SCIP_PARAMDATA*)heurdata) );
2194 
2195  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/maxnsols",
2196  "max size of solution pool for heuristic",
2197  &heurdata->maxnsols, FALSE, DEFAULT_MAXNSOLS, 5, INT_MAX, NULL, NULL) );
2198 
2199  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/ntmruns",
2200  "number of runs in TM",
2201  &heurdata->ntmruns, FALSE, DEFAULT_NTMRUNS, 1, INT_MAX, NULL, NULL) );
2202 
2203  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/maxfreq",
2204  "should the heuristic be executed at maximum frequeny?",
2205  &heurdata->maxfreq, FALSE, DEFAULT_MAXFREQREC, NULL, NULL) );
2206 
2207  heurdata->nusedsols = DEFAULT_NUSEDSOLS;
2208  heurdata->randseed = DEFAULT_RANDSEED;
2209 
2210 #ifdef WITH_UG
2211  heurdata->randseed += getUgRank();
2212 #endif
2213 
2214  /* create random number generator */
2215  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, heurdata->randseed, TRUE) );
2216 
2217  return SCIP_OKAY;
2218 }
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
#define BOUND_MAXNEDGES
Definition: heur_rec.c:67
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define REC_MAX_FAILS
Definition: heur_rec.c:71
static void solgraphAdaptForPcMw(const GRAPH *graph, STP_Bool *solnode, int *nsolnodes, STP_Bool *soledge, int *nsoledges)
Definition: heur_rec.c:1010
#define HEUR_FREQ
Definition: heur_rec.c:53
int *RESTRICT head
Definition: graphdefs.h:224
int *RESTRICT orgtail
Definition: graphdefs.h:225
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_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define COST_MIN_POLY_x0
Definition: heur_rec.c:76
#define Is_term(a)
Definition: graphdefs.h:102
static int edgecostmultiplier(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real avg)
Definition: heur_rec.c:131
Constraint handler for Steiner problems.
SCIP_RETCODE reduce_solGetEdgesol(SCIP *, GRAPH *, REDSOL *, SCIP_Real *, int *)
Definition: reduce_sol.c:1197
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:670
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
int terms
Definition: graphdefs.h:192
static SCIP_RETCODE retransformReducedProbSolution(SCIP *scip, const GRAPH *graph, const GRAPH *solgraph, const int *edgeancestor, const int *soledges, int *newsoledges, STP_Bool *stnodes)
Definition: heur_rec.c:217
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
#define DEFAULT_NTMRUNS
Definition: heur_rec.c:63
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:78
int graph_pc_nFixedTerms(const GRAPH *)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define REC_MIN_NSOLS
Definition: heur_rec.c:72
SCIP_RETCODE solstp_markPcancestors(SCIP *scip, IDX **pcancestors, const int *tails, const int *heads, int orgnnodes, STP_Bool *solnodemark, STP_Bool *soledgemark, int *solnodequeue, int *nsolnodes, int *nsoledges)
Definition: solstp.c:2200
includes methods for Steiner tree problem solutions
int *RESTRICT maxdeg
Definition: graphdefs.h:206
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
dual-ascent and reduction based primal heuristic for Steiner problems
static SCIP_RETCODE computeReducedProbSolutionBiased(SCIP *scip, SCIP_HEURDATA *heurdata, const GRAPH *graph, GRAPH *solgraph, const int *edgeweight, const int *edgeancestor, SCIP_VAR **vars, SCIP_Bool usestppool, int *soledges, SCIP_Bool *success)
Definition: heur_rec.c:355
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
#define EAT_FREE
Definition: graphdefs.h:57
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2254
#define FALSE
Definition: def.h:87
#define HEUR_PRIORITY
Definition: heur_rec.c:52
static SCIP_DECL_PARAMCHGD(paramChgdRandomseed)
Definition: heur_rec.c:113
static SCIP_DECL_HEURCOPY(heurCopyRec)
Definition: heur_rec.c:1899
Problem data for stp problem.
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
#define STP_SAP
Definition: graphdefs.h:43
#define STP_DCSTP
Definition: graphdefs.h:47
SCIP_RETCODE SCIPStpIncludeHeurRec(SCIP *scip)
Definition: heur_rec.c:2161
SCIP_Bool reduce_solUsesNodesol(const REDSOL *)
Definition: reduce_sol.c:1236
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
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
#define SCIPdebugMessage
Definition: pub_message.h:87
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10003
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE graph_pack(SCIP *, GRAPH *, GRAPH **, REDSOL *, SCIP_Bool)
Definition: graph_base.c:1324
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
int *RESTRICT orghead
Definition: graphdefs.h:226
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
static SCIP_DECL_HEUREXEC(heurExecRec)
Definition: heur_rec.c:1985
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
#define DEFAULT_MAXNSOLS
Definition: heur_rec.c:60
SCIP_RETCODE graph_pc_initSubgraph(SCIP *, GRAPH *)
Definition: graph_pcbase.c:763
static void initializeIncumbent(SCIP *scip, const STPSOLPOOL *pool, const GRAPH *graph, SCIP_VAR **vars, int nsols, int newsolindex, double *incumentobj, int *incumbentedges)
Definition: heur_rec.c:554
#define RUNS_NORMAL
Definition: heur_rec.c:69
STPSOL ** sols
Definition: solpool.h:48
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
#define STP_RSMT
Definition: graphdefs.h:49
int *RESTRICT oeat
Definition: graphdefs.h:231
int graph_pc_getRoot2PtermEdge(const GRAPH *, int)
#define STP_REDUCTION_ADVANCED
Definition: reducedefs.h:41
static SCIP_RETCODE buildsolgraph(SCIP *scip, const STPSOLPOOL *pool, SCIP_HEURDATA *heurdata, const GRAPH *graph, GRAPH **solgraph, const int *incumbentedges, int *incumbentindex, int **edgeancestor, int **edgeweight, SCIP_Bool *success, SCIP_Bool randomize, SCIP_Bool addedges)
Definition: heur_rec.c:1170
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
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
int orgedges
Definition: graphdefs.h:220
SCIP_RETCODE reduce_exec(SCIP *, GRAPH *, REDSOL *, int, int, SCIP_Bool)
Definition: reduce_base.c:2192
SCIP_RETCODE solpool_addSol(SCIP *scip, const SCIP_Real obj, const int *soledges, STPSOLPOOL *pool, SCIP_Bool *success)
Definition: solpool.c:183
#define CYCLES_PER_RUN
Definition: heur_rec.c:70
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_Bool poolSolIsUnreduced(const GRAPH *graph, const int solindex, const STPSOLPOOL *pool)
Definition: heur_rec.c:612
void graph_edge_addSubgraph(SCIP *, const GRAPH *, const int *, int, GRAPH *)
Definition: graph_edge.c:341
#define HEUR_FREQOFS
Definition: heur_rec.c:54
SCIP_Bool SCIPprobdataProbIsAdversarial(SCIP *scip)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * prize
Definition: graphdefs.h:210
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
#define RUNS_RESTRICTED
Definition: heur_rec.c:68
int *RESTRICT grad
Definition: graphdefs.h:201
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_DHCSTP
Definition: graphdefs.h:52
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
#define STP_RMWCSP
Definition: graphdefs.h:54
SCIP_RETCODE SCIPStpHeurRecExclude(SCIP *scip, const GRAPH *graph, const int *result, int *newresult, int *dnodemap, STP_Bool *stvertex, SCIP_Bool *success)
Definition: heur_rec.c:1649
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
static void setHeurdataNUsedSols(SCIP_HEURDATA *heurdata, int nsols, SCIP_Bool restrictheur)
Definition: heur_rec.c:193
int * term2edge
Definition: graphdefs.h:208
IDX ** pcancestors
Definition: graphdefs.h:235
void reduce_solFree(SCIP *, REDSOL **)
Definition: reduce_sol.c:818
#define DEFAULT_NUSEDSOLS
Definition: heur_rec.c:61
#define LT(a, b)
Definition: portab.h:81
#define STP_OARSMT
Definition: graphdefs.h:50
int orgknots
Definition: graphdefs.h:191
Improvement heuristic for Steiner problems.
unsigned char STP_Bool
Definition: portab.h:34
reduction-based primal heuristic for Steiner problems
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
static SCIP_DECL_HEURFREE(heurFreeRec)
Definition: heur_rec.c:1913
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
static SCIP_DECL_HEURINIT(heurInitRec)
Definition: heur_rec.c:1936
public data structures and miscellaneous methods
#define DEFAULT_NWAITINGSOLS
Definition: heur_rec.c:64
SCIP_RETCODE graph_pc_finalizeSubgraph(SCIP *, GRAPH *)
Definition: graph_pcbase.c:795
#define SCIP_Bool
Definition: def.h:84
#define STP_NWPTSPG
Definition: graphdefs.h:48
static SCIP_RETCODE poolAddSol(SCIP *scip, STPSOLPOOL *pool, SCIP_HEUR *heur, const SCIP_Real incumentobj, const int *incumbentedges, int nedges, int *newsolindex, SCIP_Bool *soladded)
Definition: heur_rec.c:640
int *RESTRICT tail
Definition: graphdefs.h:223
static void solgraphAddEdges(SCIP_HEURDATA *heurdata, const GRAPH *graph, const STP_Bool *solnode, STP_Bool *soledge, int *nsoledges)
Definition: heur_rec.c:1127
static SCIP_DECL_HEUREXITSOL(heurExitsolRec)
Definition: heur_rec.c:1977
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10044
SCIP_VAR ** SCIPprobdataGetEdgeVars(SCIP *scip)
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
#define HEUR_USESSUBSCIP
Definition: heur_rec.c:57
#define HEUR_DESC
Definition: heur_rec.c:50
#define DEFAULT_MAXFREQREC
Definition: heur_rec.c:59
IDX * graph_getFixedges(const GRAPH *)
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
#define HEUR_DISPCHAR
Definition: heur_rec.c:51
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
Constraint handler for linear constraints in their most general form, .
#define DEFAULT_RANDSEED
Definition: heur_rec.c:62
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
SCIP_Bool graph_typeIsUndirected(const GRAPH *)
Definition: graph_stats.c:69
int SCIPparamGetInt(SCIP_PARAM *param)
Definition: paramset.c:725
static void solgraphAdaptForDCSTP(const GRAPH *graph, const STP_Bool *solnode, STP_Bool *soledge, int *nsoledges)
Definition: heur_rec.c:1096
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
#define STP_NWSPG
Definition: graphdefs.h:46
int * soledges
Definition: solpool.h:41
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
#define REC_ADDEDGE_FACTOR
Definition: heur_rec.c:73
#define HEUR_MAXDEPTH
Definition: heur_rec.c:55
SCIP_RETCODE SCIPStpHeurRecRun(SCIP *scip, STPSOLPOOL *pool, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, const GRAPH *graph, SCIP_VAR **vars, int *newsolindex, int runs, int nsols, SCIP_Bool restrictheur, SCIP_Bool *solfound)
Definition: heur_rec.c:1455
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
static void marksolverts(const GRAPH *g, IDX *curr, const int *unodemap, STP_Bool *RESTRICT stvertex)
Definition: heur_rec.c:173
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:963
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
#define COST_MAX_POLY_x0
Definition: heur_rec.c:75
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
static SCIP_DECL_HEUREXIT(heurExitRec)
Definition: heur_rec.c:1885
#define SCIP_Real
Definition: def.h:177
#define BLOCKED
Definition: graphdefs.h:90
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
Primal recombination heuristic for Steiner problems.
int *RESTRICT outbeg
Definition: graphdefs.h:204
static SCIP_RETCODE solgraphSelectSols(SCIP *scip, const STPSOLPOOL *pool, SCIP_HEURDATA *heurdata, int *incumbentindex, int *selection, SCIP_Bool randomize)
Definition: heur_rec.c:880
#define STP_BRMWCSP
Definition: graphdefs.h:55
shortest paths based primal heuristics for Steiner problems
#define SCIP_Longint
Definition: def.h:162
static SCIP_RETCODE computeReducedProbSolution(SCIP *scip, SCIP_HEURDATA *heurdata, const GRAPH *graph, GRAPH *solgraph, REDSOL *redsol, const int *edgeweight, const int *edgeancestor, SCIP_VAR **vars, SCIP_Bool usestppool, int *soledges, SCIP_Bool *success)
Definition: heur_rec.c:489
int edges
Definition: graphdefs.h:219
#define STP_GSTP
Definition: graphdefs.h:53
#define BOUND_MAXNTERMINALS
Definition: heur_rec.c:66
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
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
#define nnodes
Definition: gastrans.c:65
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
struct Int_List_Node * parent
Definition: misc_stp.h:91
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
SCIP_RETCODE solstp_prune(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:1366
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
static SCIP_RETCODE solgraphSelectSolsDiff(SCIP *scip, const STPSOLPOOL *pool, const GRAPH *graph, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, const int *incumbentedges, int *incumbentindex, int *selection, SCIP_Bool *success)
Definition: heur_rec.c:711
int hoplimit
Definition: graphdefs.h:216
includes various reduction methods for Steiner tree problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
default SCIP plugins
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
#define STP_MWCSP
Definition: graphdefs.h:51
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2635
#define HEUR_TIMING
Definition: heur_rec.c:56
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
IDX * graph_edge_getAncestors(const GRAPH *, int)
int graph_pc_getTwinTerm(const GRAPH *, int)
int norgmodelknots
Definition: graphdefs.h:187
static SCIP_DECL_HEURINITSOL(heurInitsolRec)
Definition: heur_rec.c:1947
#define HEUR_NAME
Definition: heur_rec.c:49