Scippy

SCIP

Solving Constraint Integer Programs

reduce.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-2020 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 reduce.c
17  * @brief Reduction tests for Steiner problems
18  * @author Gerald Gamrath
19  * @author Thorsten Koch
20  * @author Stephen Maher
21  * @author Daniel Rehfeldt
22  *
23  * This file includes several packages of reduction techniques for different Steiner problem variants.
24  *
25  * A list of all interface methods can be found in grph.h.
26  *
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 /*lint -esym(750,REDUCE_C) -esym(766,stdlib.h) -esym(766,string.h) */
31 #define REDUCE_C
32 #define STP_RED_SDSPBOUND 200 /**< visited edges bound for SDSP test */
33 #define STP_RED_SDSPBOUND2 600 /**< visited edges bound for SDSP test */
34 #define STP_RED_BD3BOUND 500 /**< visited edges bound for BD3 test */
35 #define STP_RED_EXTENSIVE FALSE
36 #define STP_RED_MWTERMBOUND 400
37 #define STP_RED_MAXNROUNDS 15
38 #define STP_RED_EXFACTOR 2
39 
40 
41 #include <stdio.h>
42 #include <stdlib.h>
43 #include <string.h>
44 #include <assert.h>
45 #include "grph.h"
46 #include "heur_tm.h"
47 #include "misc_stp.h"
48 #include "scip/scip.h"
49 #include "probdata_stp.h"
50 #include "prop_stp.h"
51 
52 
53 /** print reduction information */
54 static
57  const char* method,
58  int nelims
59 )
60 {
61  assert(nelims >= 0);
62 
63 #ifdef STP_PRINT_STATS
64  if( print )
65  printf("%s: %d \n", method, nelims);
66 #endif
67 
68 }
69 
70 /** iterate NV and SL test while at least minelims many contractions are being performed */
71 static
73  SCIP* scip,
74  GRAPH* g,
75  PATH* vnoi,
76  SCIP_Real* nodearrreal,
77  SCIP_Real* fixed,
78  int* edgearrint,
79  int* heap,
80  int* state,
81  int* vbase,
82  int* neighb,
83  int* distnode,
84  int* solnode,
85  STP_Bool* visited,
86  int* nelims,
87  int minelims
88  )
89 {
90  int elims;
91  int nvelims;
92  int slelims;
93  int degelims;
94  int totalelims;
95 
96  assert(g != NULL);
97  assert(heap != NULL);
98  assert(state != NULL);
99  assert(vbase != NULL);
100  assert(vnoi != NULL);
101  assert(nodearrreal != NULL);
102  assert(visited != NULL);
103  assert(minelims >= 0);
104 
105  *nelims = 0;
106  totalelims = 0;
107 
108  do
109  {
110  elims = 0;
111  degelims = 0;
112 
113  /* NV-reduction */
114  SCIP_CALL( reduce_nvAdv(scip, g, vnoi, nodearrreal, fixed, edgearrint, heap, state, vbase, neighb, distnode, solnode, &nvelims) );
115  elims += nvelims;
116 
117  SCIPdebugMessage("NV-reduction (in NVSL): %d \n", nvelims);
118 
119  /* SL-reduction */
120  SCIP_CALL( reduce_sl(scip, g, vnoi, fixed, heap, state, vbase, neighb, visited, solnode, &slelims) );
121  elims += slelims;
122 
123  SCIPdebugMessage("SL-reduction (in NVSL): %d \n", slelims);
124 
125  /* trivial reductions */
126  if( elims > 0 )
127  {
128  if( g->stp_type == STP_PCSPG || g->stp_type == STP_RPCSPG )
129  SCIP_CALL( reduce_simple_pc(scip, g, fixed, &degelims, solnode, FALSE) );
130  else
131  SCIP_CALL( reduce_simple(scip, g, fixed, solnode, &degelims, NULL) );
132  }
133  else
134  {
135  degelims = 0;
136  }
137 
138  elims += degelims;
139 
140  SCIPdebugMessage("Degree Test-reduction (in NVSL): %d \n", degelims);
141 
142  totalelims += elims;
143  }while( elims > minelims );
144 
145  *nelims = totalelims;
146 
147  assert(graph_valid(g));
148 
149  return SCIP_OKAY;
150 }
151 
152 /* remove unconnected vertices, overwrites g->mark */
154  SCIP* scip, /**< SCIP data structure */
155  GRAPH* g /**< graph data structure */
156 )
157 {
158  int k;
159  int nnodes;
160 
161  assert(scip != NULL);
162  assert(g != NULL);
163 
164  nnodes = g->knots;
165 
166  for( k = nnodes - 1; k >= 0 ; k-- )
167  g->mark[k] = FALSE;
168 
169  SCIP_CALL( graph_trail_arr(scip, g, g->source) );
170 
171  for( k = nnodes - 1; k >= 0 ; k-- )
172  {
173  if( !g->mark[k] && (g->grad[k] > 0) )
174  {
175  assert(!Is_term(g->term[k]));
176 
177  while( g->inpbeg[k] != EAT_LAST )
178  graph_edge_del(scip, g, g->inpbeg[k], TRUE);
179  }
180  }
181  return SCIP_OKAY;
182 }
183 
184 /* remove unconnected vertices, keep g->mark */
186  SCIP* scip, /**< SCIP data structure */
187  GRAPH* g /**< graph data structure */
188 )
189 {
190  int* savemark;
191  const int nnodes = g->knots;
192 
193  assert(scip != NULL);
194  assert(g != NULL);
195 
196  SCIP_CALL( SCIPallocBufferArray(scip, &savemark, nnodes) );
197  BMScopyMemoryArray(savemark, g->mark, nnodes);
198 
199  for( int k = nnodes - 1; k >= 0; k-- )
200  g->mark[k] = FALSE;
201 
202  SCIP_CALL( graph_trail_arr(scip, g, g->source) );
203 
204  for( int k = nnodes - 1; k >= 0 ; k-- )
205  {
206  if( !g->mark[k] && (g->grad[k] > 0) )
207  {
208  assert(!Is_term(g->term[k]));
209 
210  while( g->inpbeg[k] != EAT_LAST )
211  graph_edge_del(scip, g, g->inpbeg[k], TRUE);
212  }
213  }
214 
215  BMScopyMemoryArray(g->mark, savemark, nnodes);
216 
217  SCIPfreeBufferArray(scip, &savemark);
218 
219  return SCIP_OKAY;
220 }
221 
222 /** basic reduction package for the STP */
224  SCIP* scip, /**< SCIP data structure */
225  GRAPH** graph, /**< graph data structure */
226  SCIP_Real* fixed, /**< pointer to store the offset value */
227  int minelims, /**< minimal number of edges to be eliminated in order to reiterate reductions */
228  SCIP_Bool dualascent, /**< perform dual-ascent reductions? */
229  SCIP_Bool nodereplacing, /**< should node replacement (by edges) be performed? */
230  SCIP_Bool userec /**< use recombination heuristic? */
231  )
232 {
233  PATH* vnoi;
234  PATH* path;
235  GRAPH* g;
236  GNODE** gnodearr;
237  SCIP_Real* nodearrreal;
238  SCIP_Real* edgearrreal;
239  SCIP_Real* edgearrreal2;
240  int* heap;
241  int* state;
242  int* vbase;
243  int* nodearrint;
244  int* edgearrint;
245  int* nodearrint2;
246  int i;
247  int nnodes;
248  int nedges;
249  int nterms;
250  int reductbound;
251  STP_Bool* nodearrchar;
252 
253  SCIP_Bool bred = FALSE;
254 
255  assert(scip != NULL);
256  assert(graph != NULL);
257  assert(*graph != NULL);
258  assert(minelims >= 0);
259 
260  g = *graph;
261 
262  nterms = g->terms;
263  nnodes = g->knots;
264  nedges = g->edges;
265 
266  if( SCIPisLE(scip, (double) nterms / (double) nnodes, 0.03) )
267  bred = TRUE;
268 
269  if( dualascent )
270  {
271  SCIP_CALL( SCIPallocBufferArray(scip, &gnodearr, nterms - 1) );
272  for( i = 0; i < nterms - 1; i++ )
273  {
274  SCIP_CALL( SCIPallocBlockMemory(scip, &gnodearr[i]) ); /*lint !e866*/
275  }
276  }
277  else
278  {
279  gnodearr = NULL;
280  }
281 
282  /* allocate memory */
283  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, nedges) );
284  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes) );
285  SCIP_CALL( SCIPallocBufferArray(scip, &heap, nnodes + 1) );
286  SCIP_CALL( SCIPallocBufferArray(scip, &state, 4 * nnodes) );
287  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal, nnodes) );
288  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrreal, nedges) );
289  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 4 * nnodes) );
290  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes) );
291  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint2, nnodes) );
292  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 4 * nnodes) );
293  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes) );
294 
295  if( bred || dualascent )
296  {
297  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrreal2, nedges) );
298  }
299  else
300  {
301  edgearrreal2 = NULL;
302  }
303 
304  reductbound = MAX(nedges / 1000, minelims);
305 
306  /* reduction loop */
307  SCIP_CALL( redLoopStp(scip, g, vnoi, path, gnodearr, nodearrreal, edgearrreal, edgearrreal2, heap, state,
308  vbase, nodearrint, edgearrint, nodearrint2, NULL, nodearrchar, fixed, -1.0, dualascent, bred, nodereplacing, reductbound, userec, (dualascent && userec)) );
309 
310  SCIPdebugMessage("Reduction Level 1: Fixed Cost = %.12e\n", *fixed);
311 
312  /* free memory */
313  SCIPfreeBufferArrayNull(scip, &edgearrreal2);
314  SCIPfreeBufferArray(scip, &path);
315  SCIPfreeBufferArray(scip, &vnoi);
316  SCIPfreeBufferArray(scip, &nodearrint2);
317  SCIPfreeBufferArray(scip, &nodearrint);
318  SCIPfreeBufferArray(scip, &vbase);
319  SCIPfreeBufferArray(scip, &edgearrreal);
320  SCIPfreeBufferArray(scip, &nodearrreal);
321  SCIPfreeBufferArray(scip, &state);
322  SCIPfreeBufferArray(scip, &heap);
323  SCIPfreeBufferArray(scip, &nodearrchar);
324  SCIPfreeBufferArray(scip, &edgearrint);
325 
326  if( gnodearr != NULL )
327  {
328  for( i = nterms - 2; i >= 0; i-- )
329  SCIPfreeBlockMemory(scip, &gnodearr[i]);
330  SCIPfreeBufferArray(scip, &gnodearr);
331  }
332 
333  return SCIP_OKAY;
334 }
335 
336 /** basic reduction package for the (R)PCSTP */
337 static
339  SCIP* scip, /**< SCIP data structure */
340  GRAPH** graph, /**< graph data structure */
341  SCIP_Real* fixed, /**< pointer to store the offset value */
342  int minelims, /**< minimal number of edges to be eliminated in order to reiterate reductions */
343  STP_Bool dualascent, /**< perform dual ascent reductions? */
344  SCIP_Bool userec /**< use recombination heuristic? */
345  )
346 {
347  PATH* vnoi;
348  PATH* path;
349  GRAPH* g = *graph;
350  GNODE** gnodearr;
351  SCIP_Real* exedgearrreal;
352  SCIP_Real* nodearrreal;
353  SCIP_Real* exedgearrreal2;
354  SCIP_Real timelimit;
355  int* heap;
356  int* state;
357  int* vbase;
358  int* nodearrint;
359  int* edgearrint;
360  int* nodearrint2;
361  int i;
362  int nnodes;
363  int nterms;
364  int nedges;
365  int extnedges;
366  int reductbound;
367  STP_Bool* nodearrchar;
368  SCIP_Bool bred = FALSE;
369 
370  assert(scip != NULL);
371  assert(g != NULL);
372  assert(minelims >= 0);
373 
374  nterms = g->terms;
375  nnodes = g->knots;
376  nedges = g->edges;
377 
378  /* for PCSPG more memory is necessary */
379  if( g->stp_type == STP_RPCSPG || !dualascent )
380  extnedges = nedges;
381  else
382  extnedges = nedges + 2 * (g->terms - 1);
383 
384  /* get timelimit parameter*/
385  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
386 
387  /* allocate memory */
388  SCIP_CALL( SCIPallocBufferArray(scip, &heap, nnodes + 1) );
389  SCIP_CALL( SCIPallocBufferArray(scip, &state, 4 * nnodes) );
390  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal, nnodes + 2) );
391  SCIP_CALL( SCIPallocBufferArray(scip, &exedgearrreal, extnedges ) );
392  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 4 * nnodes) );
393  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 4 * nnodes) );
394  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes + 1) );
395  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes + 1) );
396  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint2, nnodes + 1) );
397  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes + 1) );
398 
399  if( SCIPisLE(scip, (double) nterms / (double) nnodes, 0.03) )
400  bred = TRUE;
401 
402  if( bred || dualascent )
403  {
404  SCIP_CALL( SCIPallocBufferArray(scip, &exedgearrreal2, extnedges) );
405  }
406  else
407  {
408  exedgearrreal2 = NULL;
409  }
410 
411  if( dualascent )
412  {
413  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, extnedges) );
414  SCIP_CALL( SCIPallocBufferArray(scip, &gnodearr, nterms - 1) );
415  for( i = 0; i < nterms - 1; i++ )
416  {
417  SCIP_CALL( SCIPallocBlockMemory(scip, &gnodearr[i]) ); /*lint !e866*/
418  }
419  }
420  else
421  {
422  gnodearr = NULL;
423  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, nedges) );
424  }
425 
426  /* define minimal number of edge/node eliminations for a reduction test to be continued */
427  reductbound = MAX(nnodes / 1000, minelims);
428 
429  /* reduction loop */
430  SCIP_CALL( redLoopPc(scip, g, vnoi, path, gnodearr, nodearrreal, exedgearrreal, exedgearrreal2, heap, state,
431  vbase, nodearrint, edgearrint, nodearrint2, NULL, nodearrchar, fixed, dualascent, bred, reductbound, userec) );
432 
433  /* free memory */
434 
435  if( gnodearr != NULL )
436  {
437  for( i = nterms - 2; i >= 0; i-- )
438  SCIPfreeBlockMemory(scip, &gnodearr[i]);
439  SCIPfreeBufferArray(scip, &gnodearr);
440  }
441  SCIPfreeBufferArray(scip, &edgearrint);
442  SCIPfreeBufferArrayNull(scip, &exedgearrreal2);
443  SCIPfreeBufferArray(scip, &nodearrchar);
444  SCIPfreeBufferArray(scip, &nodearrint2);
445  SCIPfreeBufferArray(scip, &nodearrint);
446  SCIPfreeBufferArray(scip, &path);
447  SCIPfreeBufferArray(scip, &vnoi);
448  SCIPfreeBufferArray(scip, &vbase);
449  SCIPfreeBufferArray(scip, &exedgearrreal);
450  SCIPfreeBufferArray(scip, &nodearrreal);
451  SCIPfreeBufferArray(scip, &state);
452  SCIPfreeBufferArray(scip, &heap);
453 
454  return SCIP_OKAY;
455 }
456 
457 /** reduction package for the MWCSP */
458 static
460  SCIP* scip, /**< SCIP data structure */
461  GRAPH** graph, /**< graph data structure */
462  SCIP_Real* fixed, /**< pointer to store the offset value */
463  int minelims, /**< minimal number of edges to be eliminated in order to reiterate reductions */
464  STP_Bool advanced, /**< perform advanced reductions? */
465  SCIP_Bool userec /**< use recombination heuristic? */
466  )
467 {
468  GRAPH* g = *graph;
469  PATH* vnoi;
470  PATH* path;
471  GNODE** gnodearr;
472  SCIP_Real* nodearrreal;
473  SCIP_Real* edgearrreal;
474  SCIP_Real* edgearrreal2;
475  int* state;
476  int* vbase;
477  int* edgearrint;
478  int* nodearrint;
479  int* nodearrint2;
480  int* nodearrint3;
481  int i;
482  int nterms;
483  int nnodes;
484  int nedges;
485  int redbound;
486  int extnedges;
487  STP_Bool* nodearrchar;
488  STP_Bool bred = FALSE;
489 
490  assert(scip != NULL);
491  assert(g != NULL);
492  assert(fixed != NULL);
493  nnodes = g->knots;
494  nedges = g->edges;
495  nterms = g->terms;
496  redbound = MAX(nnodes / 1000, minelims);
497 
498  if( SCIPisLE(scip, (double) nterms / (double) nnodes, 0.1) )
499  bred = TRUE;
500 
501  if( advanced )
502  {
503  extnedges = nedges + 2 * (g->terms - 1);
504 
505  SCIP_CALL( SCIPallocBufferArray(scip, &gnodearr, nterms - 1) );
506  for( i = 0; i < nterms - 1; i++ )
507  {
508  SCIP_CALL( SCIPallocBlockMemory(scip, &gnodearr[i]) ); /*lint !e866*/
509  }
510  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, extnedges) );
511  }
512  else
513  {
514  extnedges = nedges;
515  edgearrint = NULL;
516  gnodearr = NULL;
517  }
518 
519  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes + 1) );
520  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint2, nnodes + 1) );
521  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint3, nnodes + 1) );
522  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes + 1) );
523  SCIP_CALL( SCIPallocBufferArray(scip, &state, 3 * nnodes) );
524  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 3 * nnodes) );
525  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 3 * nnodes) );
526  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes + 1) );
527 
528  if( bred || advanced )
529  {
530  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal, nnodes + 2) );
531  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrreal, extnedges) );
532  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrreal2, extnedges) );
533  }
534  else
535  {
536  nodearrreal = NULL;
537  edgearrreal = NULL;
538  edgearrreal2 = NULL;
539  }
540 
541  /* reduction loop */
542  SCIP_CALL( redLoopMw(scip, g, vnoi, path, gnodearr, nodearrreal, edgearrreal, edgearrreal2, state,
543  vbase, nodearrint, edgearrint, nodearrint2, nodearrint3, NULL, nodearrchar, fixed, advanced, bred, advanced, redbound, userec) );
544 
545  /* free memory */
546  SCIPfreeBufferArrayNull(scip, &edgearrreal2);
547  SCIPfreeBufferArrayNull(scip, &edgearrreal);
548  SCIPfreeBufferArrayNull(scip, &nodearrreal);
549  SCIPfreeBufferArray(scip, &path);
550  SCIPfreeBufferArray(scip, &vnoi);
551  SCIPfreeBufferArray(scip, &vbase);
552  SCIPfreeBufferArray(scip, &state);
553  SCIPfreeBufferArray(scip, &nodearrchar);
554  SCIPfreeBufferArray(scip, &nodearrint3);
555  SCIPfreeBufferArray(scip, &nodearrint2);
556  SCIPfreeBufferArray(scip, &nodearrint);
557  SCIPfreeBufferArrayNull(scip, &edgearrint);
558 
559  if( gnodearr != NULL )
560  {
561  for( i = nterms - 2; i >= 0; i-- )
562  SCIPfreeBlockMemory(scip, &gnodearr[i]);
563  SCIPfreeBufferArray(scip, &gnodearr);
564  }
565 
566  return SCIP_OKAY;
567 }
568 
569 /** basic reduction package for the HCDSTP */
570 static
572  SCIP* scip, /**< SCIP data structure */
573  GRAPH** graph, /**< graph data structure */
574  SCIP_Real* fixed, /**< pointer to store the offset value */
575  int minelims /**< minimal number of edges to be eliminated in order to reiterate reductions */
576  )
577 {
578  GRAPH* g = *graph;
579  PATH* vnoi;
580  SCIP_Real* cost;
581  SCIP_Real* radius;
582  SCIP_Real* costrev;
583  SCIP_Real timelimit;
584  SCIP_Real upperbound;
585  int* heap;
586  int* state;
587  int* vbase;
588  int* pathedge;
589  int nnodes;
590  int nedges;
591  int redbound;
592 #if 0
593  int danelims;
594 #endif
595  int degnelims;
596  int brednelims;
597  int hbrednelims;
598  int hcrnelims;
599  int hcrcnelims;
600  STP_Bool* nodearrchar;
601 #if 0
602  DOES NOT WORK for HC!
603  STP_Bool da = !TRUE;
604 #endif
605  STP_Bool bred = TRUE;
606  STP_Bool hbred = TRUE;
607  STP_Bool rbred = TRUE;
608  STP_Bool rcbred = TRUE;
609 
610  assert(scip != NULL);
611  assert(g != NULL);
612  assert(minelims >= 0);
613 
614  nnodes = g->knots;
615  nedges = g->edges;
616  degnelims = 0;
617  upperbound = -1.0;
618  redbound = MAX(g->knots / 1000, minelims);
619  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
620 
621  /* allocate memory */
622  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes) );
623  SCIP_CALL( SCIPallocBufferArray(scip, &heap, nnodes + 1) );
624  SCIP_CALL( SCIPallocBufferArray(scip, &state, 3 * nnodes) );
625  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
626  SCIP_CALL( SCIPallocBufferArray(scip, &radius, nnodes) );
627  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
628  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 3 * nnodes) );
629  SCIP_CALL( SCIPallocBufferArray(scip, &pathedge, nnodes) );
630  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 3 * nnodes) );
631 
632  SCIP_CALL( reduce_simple_hc(scip, g, fixed, &degnelims) );
633 
634  while( (bred || hbred || rbred || rcbred) && !SCIPisStopped(scip) )
635  {
636  if( SCIPgetTotalTime(scip) > timelimit )
637  break;
638 
639  upperbound = -1.0;
640 
641  if( rbred )
642  {
643  SCIP_CALL( reduce_boundHopR(scip, g, vnoi, cost, costrev, radius, heap, state, vbase, &hcrnelims, pathedge) );
644  if( hcrnelims <= redbound )
645  rbred = FALSE;
646  }
647 
648  if( rcbred )
649  {
650  SCIP_CALL( reduce_boundHopRc(scip, g, vnoi, cost, costrev, radius, -1.0, heap, state, vbase, &hcrcnelims, pathedge, FALSE) );
651  if( hcrcnelims <= redbound )
652  rcbred = FALSE;
653  }
654 
655  if( bred )
656  {
657  SCIP_CALL( reduce_bound(scip, g, vnoi, cost, NULL, radius, costrev, fixed, &upperbound, heap, state, vbase, &brednelims) );
658  if( brednelims <= redbound )
659  bred = FALSE;
660  }
661 
662  if( SCIPgetTotalTime(scip) > timelimit )
663  break;
664 
665  if( hbred )
666  {
667  SCIP_CALL( reduce_boundHop(scip, g, vnoi, cost, radius, costrev, heap, state, vbase, &hbrednelims) );
668  if( hbrednelims <= redbound )
669  hbred = FALSE;
670  if( SCIPgetTotalTime(scip) > timelimit )
671  break;
672  }
673  }
674 
675  /* free memory */
676  SCIPfreeBufferArray(scip, &vnoi);
677  SCIPfreeBufferArray(scip, &pathedge);
678  SCIPfreeBufferArray(scip, &vbase);
679  SCIPfreeBufferArray(scip, &costrev);
680  SCIPfreeBufferArray(scip, &radius);
681  SCIPfreeBufferArray(scip, &cost);
682  SCIPfreeBufferArray(scip, &state);
683  SCIPfreeBufferArray(scip, &heap);
684  SCIPfreeBufferArray(scip, &nodearrchar);
685 
686  return SCIP_OKAY;
687 }
688 
689 /** basic reduction package for the SAP */
690 static
692  SCIP* scip, /**< SCIP data structure */
693  GRAPH** graph, /**< graph data structure */
694  SCIP_Real* fixed, /**< pointer to store the offset value */
695  int minelims /**< minimal number of edges to be eliminated in order to reiterate reductions */
696  )
697 {
698  PATH* vnoi;
699  PATH* path;
700  SCIP_Real ub = FARAWAY;
701  SCIP_Real timelimit;
702  SCIP_Real* nodearrreal;
703  SCIP_Real* edgearrreal;
704  SCIP_Real* edgearrreal2;
705  GRAPH* g = *graph;
706  GNODE** gnodearr;
707  int* heap;
708  int* state;
709  int* vbase;
710  int* nodearrint;
711  int* edgearrint;
712  int* nodearrint2;
713  int e;
714  int i;
715  int nnodes;
716  int nedges;
717  int nterms;
718  int degtnelims;
719  int redbound;
720  STP_Bool da = TRUE;
721  STP_Bool sd = !TRUE;
722  STP_Bool* nodearrchar;
723  STP_Bool rpt = TRUE;
724  SCIP_RANDNUMGEN* randnumgen;
725 
726  /* create random number generator */
727  SCIP_CALL( SCIPcreateRandom(scip, &randnumgen, 1, TRUE) );
728 
729  nnodes = g->knots;
730  nedges = g->edges;
731  nterms = g->terms;
732 
733  redbound = MAX(nnodes / 1000, minelims);
734  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
735 
736  SCIP_CALL( SCIPallocBufferArray(scip, &gnodearr, nterms - 1) );
737  for( i = 0; i < nterms - 1; i++ )
738  {
739  SCIP_CALL( SCIPallocBlockMemory(scip, &gnodearr[i]) ); /*lint !e866*/
740  }
741 
742  /* allocate memory */
743  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, nedges) );
744  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes) );
745  SCIP_CALL( SCIPallocBufferArray(scip, &heap, nnodes + 1) );
746  SCIP_CALL( SCIPallocBufferArray(scip, &state, nnodes) );
747  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal, nnodes) );
748  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrreal, nedges) );
749  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, nnodes) );
750  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes) );
751  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint2, nnodes) );
752  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, nnodes) );
753  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes) );
754  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrreal2, nedges) );
755 
756  /* @todo change .stp file format for SAP! */
757  for( e = 0; e < g->edges; e++ )
758  if( SCIPisEQ(scip, g->cost[e], 20000.0) )
759  g->cost[e] = FARAWAY;
760 
761  SCIP_CALL( reduce_simple_sap(scip, g, fixed, &degtnelims) );
762 
763  /* main loop */
764  while( (sd || rpt || da) && !SCIPisStopped(scip) )
765  {
766  int danelims = 0;
767  int sdnelims = 0;
768  int rptnelims = 0;
769 
770  if( SCIPgetTotalTime(scip) > timelimit )
771  break;
772 
773  if( sd )
774  {
775  SCIP_CALL( reduce_sdspSap(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &sdnelims, 300) );
776  if( sdnelims <= redbound )
777  sd = FALSE;
778  }
779 
780  if( rpt )
781  {
782  SCIP_CALL( reduce_rpt(scip, g, fixed, &rptnelims) );
783  if( rptnelims <= redbound )
784  rpt = FALSE;
785  }
786 
787  SCIP_CALL( reduce_simple_sap(scip, g, fixed, &degtnelims) );
788 
789  if( da )
790  {
791  SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, &ub, fixed, edgearrint, vbase, state, heap, nodearrint,
792  nodearrint2, nodearrchar, &danelims, 0, randnumgen, FALSE, FALSE) );
793 
794  if( danelims <= 2 * redbound )
795  da = FALSE;
796  }
797  }
798 
799  SCIP_CALL( reduce_simple_sap(scip, g, fixed, &degtnelims) );
800 
801  SCIPfreeBufferArray(scip, &edgearrreal2);
802  SCIPfreeBufferArray(scip, &path);
803  SCIPfreeBufferArray(scip, &vnoi);
804  SCIPfreeBufferArray(scip, &nodearrint2);
805  SCIPfreeBufferArray(scip, &nodearrint);
806  SCIPfreeBufferArray(scip, &vbase);
807  SCIPfreeBufferArray(scip, &edgearrreal);
808  SCIPfreeBufferArray(scip, &nodearrreal);
809  SCIPfreeBufferArray(scip, &state);
810  SCIPfreeBufferArray(scip, &heap);
811  SCIPfreeBufferArray(scip, &nodearrchar);
812  SCIPfreeBufferArray(scip, &edgearrint);
813 
814  for( i = nterms - 2; i >= 0; i-- )
815  SCIPfreeBlockMemory(scip, &gnodearr[i]);
816  SCIPfreeBufferArray(scip, &gnodearr);
817 
818  /* free random number generator */
819  SCIPfreeRandom(scip, &randnumgen);
820 
821  return SCIP_OKAY;
822 }
823 
824 
825 static
827  SCIP* scip, /**< SCIP data structure */
828  GRAPH** graph, /**< graph data structure */
829  SCIP_Real* fixed, /**< pointer to store the offset value */
830  int minelims /**< minimal number of edges to be eliminated in order to reiterate reductions */
831  )
832 {
833  PATH* vnoi;
834  SCIP_Real* nodearrreal;
835  SCIP_Real* edgearrreal;
836  SCIP_Real* edgearrreal2;
837  SCIP_Real ub = FARAWAY;
838  SCIP_Real timelimit;
839  GRAPH* g = *graph;
840  GNODE** gnodearr;
841  int* heap;
842  int* state;
843  int* vbase;
844  int* nodearrint;
845  int* edgearrint;
846  int* nodearrint2;
847  int i;
848  int nnodes;
849  int nedges;
850  int nterms;
851  int redbound;
852 
853  STP_Bool* nodearrchar;
854  STP_Bool da = TRUE;
855  SCIP_RANDNUMGEN* randnumgen;
856 
857  /* create random number generator */
858  SCIP_CALL( SCIPcreateRandom(scip, &randnumgen, 1, TRUE) );
859 
860  nnodes = g->knots;
861  nedges = g->edges;
862  nterms = g->terms;
863 
864  redbound = MAX(nnodes / 1000, minelims);
865  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
866 
867  SCIP_CALL( SCIPallocBufferArray(scip, &gnodearr, nterms - 1) );
868  for( i = 0; i < nterms - 1; i++ )
869  {
870  SCIP_CALL( SCIPallocBlockMemory(scip, &gnodearr[i]) ); /*lint !e866*/
871  }
872 
873  /* allocate memory */
874  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint, nedges) );
875  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes) );
876  SCIP_CALL( SCIPallocBufferArray(scip, &heap, nnodes + 1) );
877  SCIP_CALL( SCIPallocBufferArray(scip, &state, nnodes) );
878  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrreal, nnodes) );
879  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrreal, nedges) );
880  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, nnodes) );
881  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint, nnodes) );
882  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrint2, nnodes) );
883  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, nnodes) );
884  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrreal2, nedges) );
885 
886  while( (da) && !SCIPisStopped(scip) )
887  {
888  int danelims = 0;
889 
890  if( SCIPgetTotalTime(scip) > timelimit )
891  break;
892 
893  SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, &ub, fixed, edgearrint, vbase, state, heap, nodearrint,
894  nodearrint2, nodearrchar, &danelims, 0, randnumgen, FALSE, FALSE) );
895 
896  if( danelims <= 2 * redbound )
897  da = FALSE;
898  }
899 
900  SCIPfreeBufferArray(scip, &edgearrreal2);
901  SCIPfreeBufferArray(scip, &vnoi);
902  SCIPfreeBufferArray(scip, &nodearrint2);
903  SCIPfreeBufferArray(scip, &nodearrint);
904  SCIPfreeBufferArray(scip, &vbase);
905  SCIPfreeBufferArray(scip, &edgearrreal);
906  SCIPfreeBufferArray(scip, &nodearrreal);
907  SCIPfreeBufferArray(scip, &state);
908  SCIPfreeBufferArray(scip, &heap);
909  SCIPfreeBufferArray(scip, &nodearrchar);
910  SCIPfreeBufferArray(scip, &edgearrint);
911 
912  for( i = nterms - 2; i >= 0; i-- )
913  SCIPfreeBlockMemory(scip, &gnodearr[i]);
914  SCIPfreeBufferArray(scip, &gnodearr);
915 
916  /* free random number generator */
917  SCIPfreeRandom(scip, &randnumgen);
918 
919  return SCIP_OKAY;
920 }
921 
922 /** MWCS loop */
924  SCIP* scip, /**< SCIP data structure */
925  GRAPH* g, /**< graph data structure */
926  PATH* vnoi, /**< Voronoi data structure */
927  PATH* path, /**< path data structure */
928  GNODE** gnodearr, /**< nodes-sized array */
929  SCIP_Real* nodearrreal, /**< nodes-sized array */
930  SCIP_Real* edgearrreal, /**< edges-sized array */
931  SCIP_Real* edgearrreal2, /**< edges-sized array */
932  int* state, /**< shortest path array */
933  int* vbase, /**< voronoi base array */
934  int* nodearrint, /**< nodes-sized array */
935  int* edgearrint, /**< edges-sized array */
936  int* nodearrint2, /**< nodes-sized array */
937  int* nodearrint3, /**< nodes-sized array */
938  int* solnode, /**< array to indicate whether a node is part of the current solution (==CONNECT) */
939  STP_Bool* nodearrchar, /**< nodes-sized array */
940  SCIP_Real* fixed, /**< pointer to store the offset value */
941  STP_Bool advanced, /**< do advanced reduction? */
942  STP_Bool bred, /**< do bound-based reduction? */
943  STP_Bool tryrmw, /**< try to convert problem to RMWCSP? Only possible if advanced = TRUE and userec = TRUE */
944  int redbound, /**< minimal number of edges to be eliminated in order to reiterate reductions */
945  SCIP_Bool userec /**< use recombination heuristic? */
946  )
947 {
948  SCIP_Real timelimit;
949  int daelims;
950  int anselims;
951  int nnpelims;
952  int degelims;
953  int npvelims;
954  int bredelims;
955  int ansadelims;
956  int ansad2elims;
957  int chain2elims;
958 
959  STP_Bool da = advanced;
960  STP_Bool ans = TRUE;
961  STP_Bool nnp = TRUE;
962  STP_Bool npv = TRUE;
963  STP_Bool rerun = TRUE;
964  STP_Bool ansad = TRUE;
965  STP_Bool ansad2 = TRUE;
966  STP_Bool chain2 = TRUE;
967  STP_Bool extensive = STP_RED_EXTENSIVE;
968  SCIP_RANDNUMGEN* randnumgen;
969  SCIP_Real prizesum;
970 
971  assert(scip != NULL);
972  assert(g != NULL);
973  assert(fixed != NULL);
974  assert(advanced || !tryrmw);
975 
976  tryrmw = tryrmw && userec;
977 
978  /* create random number generator */
979  SCIP_CALL( SCIPcreateRandom(scip, &randnumgen, 1, TRUE) );
980 
981  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
982 
983  graph_pc_2org(g);
984 
985  degelims = 0;
986 
987  SCIP_CALL( reduce_simple_mw(scip, g, solnode, fixed, &degelims) );
988  assert(graph_pc_term2edgeConsistent(g));
989 
990  prizesum = graph_pc_getPosPrizeSum(scip, g);
991 
992  for( int rounds = 0; rounds < STP_RED_MAXNROUNDS && !SCIPisStopped(scip) && rerun; rounds++ )
993  {
994  daelims = 0;
995  anselims = 0;
996  nnpelims = 0;
997  degelims = 0;
998  npvelims = 0;
999  bredelims = 0;
1000  ansadelims = 0;
1001  ansad2elims = 0;
1002  chain2elims = 0;
1003 
1004  if( SCIPgetTotalTime(scip) > timelimit )
1005  break;
1006 
1007  if( ans || extensive )
1008  {
1009  reduce_ans(scip, g, nodearrint2, &anselims);
1010 
1011  if( anselims <= redbound )
1012  ans = FALSE;
1013 
1014  SCIPdebugMessage("ans deleted: %d \n", anselims);
1015  }
1016 
1017  if( ansad || extensive )
1018  {
1019  reduce_ansAdv(scip, g, nodearrint2, &ansadelims, FALSE);
1020 
1021  if( ansadelims <= redbound )
1022  ansad = FALSE;
1023 
1024  SCIPdebugMessage("ans advanced deleted: %d \n", ansadelims);
1025  }
1026 
1027  if( ans || ansad || nnp || npv || extensive )
1028  SCIP_CALL( reduce_simple_mw(scip, g, solnode, fixed, &degelims) );
1029 
1030  if( (da || (advanced && extensive)) )
1031  {
1032  SCIP_CALL( reduce_daPcMw(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, vbase, nodearrint, edgearrint,
1033  state, nodearrchar, &daelims, TRUE, FALSE, FALSE, userec, (rounds == 0), randnumgen, prizesum) );
1034 
1035  if( daelims <= 2 * redbound )
1036  da = FALSE;
1037  else
1038  SCIP_CALL( reduce_simple_mw(scip, g, solnode, fixed, &degelims) );
1039 
1040  SCIPdebugMessage("Dual-Ascent Elims: %d \n", daelims);
1041  }
1042 
1043  if( nnp )
1044  {
1045  reduce_nnp(scip, g, nodearrint2, &nnpelims);
1046 
1047  if( nnpelims <= redbound )
1048  nnp = FALSE;
1049 
1050  SCIPdebugMessage("nnp deleted: %d \n", nnpelims);
1051  }
1052 
1053  if( nnp || extensive )
1054  {
1055  SCIP_CALL(reduce_chain2(scip, g, vnoi, path, state, vbase, nodearrint, nodearrint2, nodearrint3, &chain2elims, 500));
1056 
1057  if( chain2elims <= redbound )
1058  chain2 = FALSE;
1059 
1060  SCIPdebugMessage("chain2 delete: %d \n", chain2elims);
1061 
1062  if( SCIPgetTotalTime(scip) > timelimit )
1063  break;
1064  }
1065 
1066  if( npv || extensive )
1067  {
1068  SCIP_CALL(reduce_npv(scip, g, vnoi, path, state, vbase, nodearrint, nodearrint2, nodearrint3, &npvelims, 400));
1069 
1070  if( npvelims <= redbound )
1071  npv = FALSE;
1072 
1073  SCIPdebugMessage("npv delete: %d \n", npvelims);
1074  }
1075 
1076  if( chain2 || extensive )
1077  {
1078  SCIP_CALL(reduce_chain2(scip, g, vnoi, path, state, vbase, nodearrint, nodearrint2, nodearrint3, &chain2elims, 300));
1079 
1080  if( chain2elims <= redbound )
1081  chain2 = FALSE;
1082 
1083  SCIPdebugMessage("chain2 delete: %d \n", chain2elims);
1084  }
1085 
1086  SCIP_CALL( reduce_simple_mw(scip, g, solnode, fixed, &degelims) );
1087 
1088  if( ansad2 || extensive )
1089  {
1090  reduce_ansAdv2(scip, g, nodearrint2, &ansad2elims);
1091 
1092  if( ansad2elims <= redbound )
1093  ansad2 = FALSE;
1094  else
1095  SCIP_CALL( reduce_simple_mw(scip, g, solnode, fixed, &ansad2elims) );
1096 
1097  SCIPdebugMessage("ans advanced 2 deleted: %d (da? %d ) \n", ansad2elims, da);
1098  }
1099 
1100  if( bred )
1101  {
1102  SCIP_CALL( reduce_boundMw(scip, g, vnoi, path, edgearrreal, nodearrreal, edgearrreal2, fixed, nodearrint, state, vbase, NULL, &bredelims) );
1103 
1104  if( bredelims <= redbound )
1105  bred = FALSE;
1106 
1107 
1108  SCIPdebugMessage("reduce_bound: %d \n", bredelims);
1109  }
1110 
1111  if( anselims + nnpelims + chain2elims + bredelims + npvelims + ansadelims + ansad2elims + daelims <= redbound )
1112  rerun = FALSE;
1113 
1114  if( !rerun && advanced && g->terms > 2 )
1115  {
1116  int cnsadvelims = 0;
1117 
1118  SCIP_CALL( reduce_simple_mw(scip, g, solnode, fixed, &degelims) );
1119 
1120  SCIP_CALL( reduce_daPcMw(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, vbase, nodearrint, edgearrint,
1121  state, nodearrchar, &daelims, TRUE, (g->terms > STP_RED_MWTERMBOUND), tryrmw, userec, FALSE, randnumgen, prizesum) );
1122 
1123  userec = FALSE;
1124 
1125  if( cnsadvelims + daelims >= redbound || (extensive && (cnsadvelims + daelims > 0)) )
1126  {
1127  ans = TRUE;
1128  nnp = TRUE;
1129  npv = TRUE;
1130  ansad = TRUE;
1131  ansad2 = TRUE;
1132  chain2 = TRUE;
1133  rerun = TRUE;
1134  advanced = FALSE;
1135 
1136  SCIP_CALL( reduce_simple_mw(scip, g, solnode, fixed, &degelims) );
1137  SCIPdebugMessage("Restarting reduction loop! (%d eliminations) \n\n ", cnsadvelims + daelims);
1138  if( extensive )
1139  advanced = TRUE;
1140  }
1141  }
1142  }
1143 
1144  SCIP_CALL( reduce_simple_mw(scip, g, solnode, fixed, &degelims) );
1145 
1146  /* go back to the extended graph */
1147  graph_pc_2trans(g);
1148 
1149  SCIP_CALL( level0(scip, g) );
1150 
1151  if( tryrmw && g->terms > 2 )
1152  SCIP_CALL( graph_pc_mw2rmw(scip, g, prizesum) );
1153 
1154  SCIPfreeRandom(scip, &randnumgen);
1155 
1156  return SCIP_OKAY;
1157 }
1158 
1159 /** (R)PC loop */
1161  SCIP* scip, /**< SCIP data structure */
1162  GRAPH* g, /**< graph data structure */
1163  PATH* vnoi, /**< Voronoi data structure */
1164  PATH* path, /**< path data structure */
1165  GNODE** gnodearr, /**< nodes-sized array */
1166  SCIP_Real* nodearrreal, /**< nodes-sized array */
1167  SCIP_Real* exedgearrreal, /**< edges-sized array */
1168  SCIP_Real* exedgearrreal2, /**< edges-sized array */
1169  int* heap, /**< shortest path array */
1170  int* state, /**< voronoi base array */
1171  int* vbase, /**< nodes-sized array */
1172  int* nodearrint, /**< edges-sized array */
1173  int* edgearrint, /**< nodes-sized array */
1174  int* nodearrint2, /**< nodes-sized array */
1175  int* solnode, /**< solution nodes array (or NULL) */
1176  STP_Bool* nodearrchar, /**< nodes-sized array */
1177  SCIP_Real* fixed, /**< pointer to store the offset value */
1178  SCIP_Bool dualascent, /**< do dual-ascent reduction? */
1179  SCIP_Bool bred, /**< do bound-based reduction? */
1180  int reductbound, /**< minimal number of edges to be eliminated in order to reiterate reductions */
1181  SCIP_Bool userec /**< use recombination heuristic? */
1182  )
1183 {
1184  SCIP_Real ub;
1185  SCIP_Real fix;
1186  SCIP_Real timelimit;
1187  SCIP_Real rootprize = 0.0;
1188  const SCIP_Bool rpc = (g->stp_type == STP_RPCSPG);
1189  int nelims;
1190  int danelims;
1191  int sdnelims;
1192  int sdcnelims;
1193  int bd3nelims;
1194  int degnelims;
1195  int nvslnelims;
1196  int brednelims;
1197  SCIP_Bool da = dualascent;
1198  SCIP_Bool sd = TRUE;
1199  SCIP_Bool sdc = TRUE;
1200  SCIP_Bool bd3 = TRUE;
1201  SCIP_Bool nvsl = TRUE;
1202  SCIP_Bool rerun = TRUE;
1203  SCIP_Bool extensive = STP_RED_EXTENSIVE;
1204  SCIP_Bool advancedrun = dualascent;
1205  SCIP_Real prizesum;
1206  SCIP_RANDNUMGEN* randnumgen;
1207 
1208  if( g->grad[g->source] == 0 )
1209  return SCIP_OKAY;
1210 
1211  /* create random number generator */
1212  SCIP_CALL( SCIPcreateRandom(scip, &randnumgen, 1, TRUE) );
1213 
1214  if( rpc )
1215  {
1216  rootprize = g->prize[g->source];
1217  g->prize[g->source] = FARAWAY;
1218  }
1219 
1220  ub = -1.0;
1221  fix = 0.0;
1222 
1223  graph_pc_2org(g);
1224  assert(graph_pc_term2edgeConsistent(g));
1225 
1226  SCIP_CALL( graph_pc_presolInit(scip, g) );
1227 
1228  SCIP_CALL( reduce_simple_pc(scip, g, &fix, &degnelims, solnode, FALSE) );
1229  assert(graph_pc_term2edgeConsistent(g));
1230 
1231  prizesum = graph_pc_getPosPrizeSum(scip, g);
1232 
1233  /* get timelimit parameter */
1234  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1235 
1236  for( int rounds = 0; rounds < STP_RED_MAXNROUNDS && !SCIPisStopped(scip) && rerun; rounds++ )
1237  {
1238  if( SCIPgetTotalTime(scip) > timelimit )
1239  break;
1240 
1241  nelims = 0;
1242  danelims = 0;
1243  sdnelims = 0;
1244  sdcnelims = 0;
1245  bd3nelims = 0;
1246  nvslnelims = 0;
1247  degnelims = 0;
1248  brednelims = 0;
1249 
1250  if( sd || extensive )
1251  {
1252  SCIP_CALL( reduce_sdPc(scip, g, vnoi, heap, state, vbase, nodearrint, nodearrint2, &sdnelims) );
1253 
1254  if( sdnelims <= reductbound )
1255  sd = FALSE;
1256 
1257  SCIPdebugMessage("SDpc: %d \n", sdnelims);
1258  if( SCIPgetTotalTime(scip) > timelimit )
1259  break;
1260  }
1261 
1262  if( sdc || extensive )
1263  {
1264  SCIP_CALL( reduce_sdsp(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &sdcnelims,
1265  ((rounds > 0) ? STP_RED_SDSPBOUND2 : STP_RED_SDSPBOUND), NULL) );
1266 
1267  if( sdcnelims <= reductbound )
1268  sdc = FALSE;
1269 
1270  SCIPdebugMessage("SDsp: %d \n", sdcnelims);
1271  if( SCIPgetTotalTime(scip) > timelimit )
1272  break;
1273  }
1274 
1275  SCIP_CALL( reduce_simple_pc(scip, g, &fix, &nelims, solnode, FALSE) );
1276 
1277  degnelims += nelims;
1278 
1279  if( bd3 && dualascent )
1280  {
1281  SCIP_CALL( reduce_bd34(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &bd3nelims, STP_RED_BD3BOUND) );
1282  if( bd3nelims <= reductbound )
1283  {
1284  bd3 = FALSE;
1285  }
1286  else if( !rpc )
1287  {
1288  SCIP_CALL( reduce_sdPc(scip, g, vnoi, heap, state, vbase, nodearrint, nodearrint2, &sdnelims) );
1289  SCIP_CALL( reduce_sdsp(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &sdcnelims, ((rounds > 0) ? STP_RED_SDSPBOUND2 : STP_RED_SDSPBOUND), NULL) );
1290  }
1291 
1292  SCIPdebugMessage("bd3: %d \n", bd3nelims);
1293  if( SCIPgetTotalTime(scip) > timelimit )
1294  break;
1295  }
1296 
1297  if( nvsl || extensive )
1298  {
1299  SCIP_CALL( nvreduce_sl(scip, g, vnoi, nodearrreal, &fix, edgearrint, heap, state, vbase, nodearrint, nodearrint2, solnode, nodearrchar, &nvslnelims, reductbound) );
1300 
1301  if( nvslnelims <= 0.5 * reductbound )
1302  nvsl = FALSE;
1303 
1304  SCIPdebugMessage("nvsl: %d \n", nvslnelims);
1305  if( SCIPgetTotalTime(scip) > timelimit )
1306  break;
1307  }
1308 
1309  if( bred )
1310  {
1311  ub = -1.0;
1312  SCIP_CALL( reduce_bound(scip, g, vnoi, exedgearrreal, g->prize, nodearrreal, exedgearrreal2, &fix, &ub, heap, state, vbase, &brednelims) );
1313  if( brednelims <= reductbound )
1314  bred = FALSE;
1315 
1316  SCIPdebugMessage("bndelims %d \n", brednelims);
1317  if( SCIPgetTotalTime(scip) > timelimit )
1318  break;
1319  }
1320 
1321  ub = -1.0;
1322 
1323  assert(graph_pc_term2edgeConsistent(g));
1324 
1325  if( da || (dualascent && extensive) )
1326  {
1327  SCIP_CALL( reduce_simple_pc(scip, g, &fix, &degnelims, solnode, TRUE) );
1328 
1329  if( rpc )
1330  SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, exedgearrreal, exedgearrreal2, nodearrreal, &ub, &fix, edgearrint, vbase, state, heap,
1331  nodearrint, nodearrint2, nodearrchar, &danelims, 0, randnumgen, FALSE, FALSE) );
1332  else
1333  SCIP_CALL( reduce_daPcMw(scip, g, vnoi, gnodearr, exedgearrreal, exedgearrreal2, nodearrreal, vbase, heap, edgearrint,
1334  state, nodearrchar, &danelims, TRUE, FALSE, FALSE, userec, (rounds == 0), randnumgen, prizesum) );
1335 
1336  if( danelims <= reductbound )
1337  da = FALSE;
1338 
1339  SCIPdebugMessage("da: %d \n", danelims);
1340  }
1341 
1342  SCIP_CALL( reduce_simple_pc(scip, g, &fix, &degnelims, solnode, TRUE) );
1343 
1344  if( ub >= 0 )
1345  {
1346  SCIP_CALL( reduce_bound(scip, g, vnoi, exedgearrreal, g->prize, nodearrreal, exedgearrreal2, &fix, &ub, heap, state, vbase, &brednelims) );
1347  if( brednelims <= reductbound )
1348  bred = FALSE;
1349 
1350  SCIPdebugMessage("bndelims %d \n", brednelims);
1351  if( SCIPgetTotalTime(scip) > timelimit )
1352  break;
1353  }
1354 
1355  if( degnelims + sdnelims + sdcnelims + bd3nelims + danelims + brednelims + nvslnelims <= reductbound )
1356  rerun = FALSE;
1357 
1358  if( !rerun && advancedrun && g->terms > 2 )
1359  {
1360  rerun = TRUE;
1361  danelims = 0;
1362  degnelims = 0;
1363  advancedrun = FALSE;
1364  if( rpc )
1365  {
1366  SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, exedgearrreal, exedgearrreal2, nodearrreal, &ub, &fix, edgearrint, vbase, state, heap,
1367  nodearrint, nodearrint2, nodearrchar, &danelims, 0, randnumgen, FALSE, FALSE) );
1368  }
1369  else
1370  {
1371  SCIP_CALL( reduce_daPcMw(scip, g, vnoi, gnodearr, exedgearrreal, exedgearrreal2, nodearrreal, vbase, heap, edgearrint,
1372  state, nodearrchar, &danelims, TRUE, TRUE, TRUE, userec, FALSE, randnumgen, prizesum) );
1373  }
1374  SCIP_CALL( reduce_simple_pc(scip, g, &fix, &degnelims, solnode, TRUE) );
1375  if( danelims + degnelims > reductbound || (extensive && (danelims + degnelims > 0)) )
1376  {
1377  da = dualascent;
1378  sd = TRUE;
1379  sdc = TRUE;
1380  bd3 = TRUE;
1381  nvsl = TRUE;
1382  if( extensive )
1383  advancedrun = TRUE;
1384  }
1385  else
1386  {
1387  rerun = FALSE;
1388  }
1389  }
1390  }
1391  SCIP_CALL( reduce_simple_pc(scip, g, &fix, &degnelims, solnode, TRUE) );
1392 
1393  if( rpc )
1394  g->prize[g->source] = rootprize;
1395 
1396  assert(graph_pc_term2edgeConsistent(g));
1397  graph_pc_2trans(g);
1398 
1399  graph_pc_presolExit(scip, g);
1400 
1401  /* free random number generator */
1402  SCIPfreeRandom(scip, &randnumgen);
1403 
1404  *fixed += fix;
1405 
1406  SCIPdebugMessage("Reduction Level PC 1: Fixed Cost = %.12e\n", *fixed);
1407  return SCIP_OKAY;
1408 }
1409 
1410 /** STP loop */
1412  SCIP* scip, /**< SCIP data structure */
1413  GRAPH* g, /**< graph data structure */
1414  PATH* vnoi, /**< Voronoi data structure */
1415  PATH* path, /**< path data structure */
1416  GNODE** gnodearr, /**< nodes-sized array */
1417  SCIP_Real* nodearrreal, /**< nodes-sized array */
1418  SCIP_Real* edgearrreal, /**< edges-sized array */
1419  SCIP_Real* edgearrreal2, /**< edges-sized array */
1420  int* heap, /**< heap array */
1421  int* state, /**< shortest path array */
1422  int* vbase, /**< Voronoi base array */
1423  int* nodearrint, /**< edges-sized array */
1424  int* edgearrint, /**< nodes-sized array */
1425  int* nodearrint2, /**< nodes-sized array */
1426  int* solnode, /**< solution nodes array (or NULL) */
1427  STP_Bool* nodearrchar, /**< nodes-sized array */
1428  SCIP_Real* fixed, /**< pointer to store the offset value */
1429  SCIP_Real upperbound, /**< upper bound */
1430  SCIP_Bool dualascent, /**< do dual-ascent reduction? */
1431  SCIP_Bool boundreduce, /**< do bound-based reduction? */
1432  SCIP_Bool nodereplacing, /**< should node replacement (by edges) be performed? */
1433  int reductbound, /**< minimal number of edges to be eliminated in order to reiterate reductions */
1434  SCIP_Bool userec, /**< use recombination heuristic? */
1435  SCIP_Bool fullreduce /**< use full reductions? (including extended techniques) */
1436  )
1437 {
1438  SCIP_Real ub;
1439  SCIP_Real fix;
1440  SCIP_Real timelimit;
1441  SCIP_Bool le = TRUE;
1442  SCIP_Bool sd = TRUE;
1443  SCIP_Bool da = dualascent;
1444  SCIP_Bool sdc = TRUE;
1445  SCIP_Bool bd3 = nodereplacing;
1446  SCIP_Bool bred = boundreduce;
1447  SCIP_Bool nvsl = nodereplacing;
1448  SCIP_Bool rerun = TRUE;
1449 
1450  const SCIP_Bool extensive = STP_RED_EXTENSIVE;
1451  int i = 0;
1452 
1453  SCIP_RANDNUMGEN* randnumgen;
1454 
1455  assert(reductbound > 0);
1456  assert(graph_valid(g));
1457 
1458  /* create random number generator */
1459  SCIP_CALL( SCIPcreateRandom(scip, &randnumgen, 1, TRUE) );
1460 
1461  ub = upperbound;
1462  fix = 0.0;
1463 
1465  SCIP_CALL( reduce_simple(scip, g, &fix, solnode, &i, NULL) );
1466 
1467  /* get timelimit parameter */
1468  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1469 
1470  do
1471  {
1472  int inner_rounds = 0;
1473  int inner_restarts = 0;
1474 
1475  /* inner reduction loop */
1476  while( rerun && !SCIPisStopped(scip) )
1477  {
1478  int danelims = 0;
1479  int lenelims = 0;
1480  int sdnelims = 0;
1481  int sdcnelims = 0;
1482  int bd3nelims = 0;
1483  int nvslnelims = 0;
1484  int brednelims = 0;
1485  int degtnelims = 0;
1486 
1487  if( SCIPgetTotalTime(scip) > timelimit )
1488  break;
1489 
1490  if( le || extensive )
1491  {
1492  SCIP_CALL(reduce_ledge(scip, g, vnoi, heap, state, vbase, &lenelims, NULL));
1493 
1494  if( lenelims <= reductbound )
1495  le = FALSE;
1496  else
1497  SCIP_CALL(reduce_simple(scip, g, &fix, solnode, &degtnelims, NULL));
1498 
1499  reduceStatsPrint(fullreduce, "le", lenelims);
1500  SCIPdebugMessage("le: %d \n", lenelims);
1501 
1502  if( SCIPgetTotalTime(scip) > timelimit )
1503  break;
1504  }
1505 
1506  if( sd || extensive )
1507  {
1508  SCIP_CALL(
1509  reduce_sd(scip, g, vnoi, edgearrreal, nodearrreal, heap, state, vbase, nodearrint, nodearrint2, edgearrint, &sdnelims,
1510  nodereplacing, NULL));
1511 
1512  if( sdnelims <= reductbound )
1513  sd = FALSE;
1514 
1515  reduceStatsPrint(fullreduce, "sd", sdnelims);
1516  SCIPdebugMessage("sd: %d, \n", sdnelims);
1517 
1518  if( SCIPgetTotalTime(scip) > timelimit )
1519  break;
1520  }
1521 
1522  if( sdc || extensive )
1523  {
1524  SCIP_CALL(
1525  reduce_sdsp(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &sdcnelims, ((inner_rounds > 0) ? (STP_RED_SDSPBOUND2 / 2) : (STP_RED_SDSPBOUND / 2)), NULL));
1526 
1527  if( sdcnelims <= reductbound )
1528  sdc = FALSE;
1529 
1530  reduceStatsPrint(fullreduce, "sdsp", sdcnelims);
1531  SCIPdebugMessage("sdsp: %d \n", sdcnelims);
1532 
1533  if( SCIPgetTotalTime(scip) > timelimit )
1534  break;
1535  }
1536 
1537  if( sd || sdc )
1538  SCIP_CALL(reduce_simple(scip, g, &fix, solnode, &degtnelims, NULL));
1539 
1540  if( bd3 || extensive )
1541  {
1542  SCIP_CALL(reduce_bd34(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &bd3nelims, STP_RED_BD3BOUND));
1543  if( bd3nelims <= reductbound )
1544  bd3 = FALSE;
1545  else
1546  SCIP_CALL(reduce_simple(scip, g, &fix, solnode, &degtnelims, NULL));
1547 
1548  reduceStatsPrint(fullreduce, "bd3", bd3nelims);
1549  SCIPdebugMessage("bd3: %d \n", bd3nelims);
1550 
1551  if( SCIPgetTotalTime(scip) > timelimit )
1552  break;
1553  }
1554 
1555  if( nvsl || extensive )
1556  {
1557  SCIP_CALL(
1558  nvreduce_sl(scip, g, vnoi, nodearrreal, &fix, edgearrint, heap, state, vbase, nodearrint, NULL, solnode, nodearrchar, &nvslnelims, reductbound));
1559 
1560  if( nvslnelims <= reductbound )
1561  nvsl = FALSE;
1562 
1563  reduceStatsPrint(fullreduce, "nvsl", nvslnelims);
1564  SCIPdebugMessage("nvsl: %d \n", nvslnelims);
1565 
1566  if( SCIPgetTotalTime(scip) > timelimit )
1567  break;
1568  }
1569 
1570  ub = -1.0;
1571 
1572  if( da )
1573  {
1574  SCIP_CALL(
1575  reduce_da(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, &ub, &fix, edgearrint, vbase, state, heap, nodearrint,
1576  nodearrint2, nodearrchar, &danelims, inner_rounds, randnumgen, userec, FALSE));
1577 
1578  if( danelims <= STP_RED_EXFACTOR * reductbound )
1579  da = FALSE;
1580 
1581  reduceStatsPrint(fullreduce, "da", danelims);
1582  SCIPdebugMessage("da: %d \n", danelims);
1583 
1584  if( SCIPgetTotalTime(scip) > timelimit )
1585  break;
1586  }
1587 
1588  if( bred && nodereplacing )
1589  {
1590  SCIP_CALL(reduce_bound(scip, g, vnoi, edgearrreal, NULL, nodearrreal, edgearrreal2, &fix, &ub, heap, state, vbase, &brednelims));
1591 
1592  SCIP_CALL(level0(scip, g));
1593 
1594  if( brednelims <= reductbound )
1595  bred = FALSE;
1596 
1597  reduceStatsPrint(fullreduce, "bnd", brednelims);
1598  SCIPdebugMessage("bnd: %d \n\n", brednelims);
1599 
1600  if( SCIPgetTotalTime(scip) > timelimit )
1601  break;
1602  }
1603  SCIP_CALL(level0(scip, g));
1604  SCIP_CALL(reduce_simple(scip, g, &fix, solnode, &degtnelims, NULL));
1605 
1606  if( (danelims + sdnelims + bd3nelims + nvslnelims + lenelims + brednelims + sdcnelims) <= 2 * reductbound )
1607  {
1608  // at least one successful round and full reduce and no inner_restarts yet?
1609  if( inner_rounds > 0 && fullreduce && inner_restarts == 0 )
1610  {
1611  inner_restarts++;
1612  le = TRUE;
1613  sd = TRUE;
1614  sdc = TRUE;
1615  da = TRUE;
1616  bd3 = nodereplacing;
1617  nvsl = nodereplacing;
1618 
1619 #ifdef STP_PRINT_STATS
1620  printf("RESTART reductions (restart %d) \n", inner_restarts);
1621 #endif
1622  }
1623  else
1624  rerun = FALSE;
1625  }
1626 
1627  if( extensive && (danelims + sdnelims + bd3nelims + nvslnelims + lenelims + brednelims + sdcnelims) > 0 )
1628  rerun = TRUE;
1629 
1630  inner_rounds++;
1631  } /* inner reduction loop */
1632 
1633  if( fullreduce && !SCIPisStopped(scip) )
1634  {
1635  int extendedelims = 0;
1636 
1637  assert(!rerun);
1638 
1639  SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, &ub, &fix, edgearrint, vbase, state, heap, nodearrint,
1640  nodearrint2, nodearrchar, &extendedelims, inner_rounds, randnumgen, userec, TRUE));
1641 
1642  reduceStatsPrint(fullreduce, "ext", extendedelims);
1643 
1644  SCIP_CALL(reduce_simple(scip, g, &fix, solnode, &extendedelims, NULL));
1645 
1646  if( extendedelims > STP_RED_EXFACTOR * reductbound )
1647  {
1648  le = TRUE;
1649  sd = TRUE;
1650  sdc = TRUE;
1651  da = TRUE;
1652  bd3 = nodereplacing;
1653  nvsl = nodereplacing;
1654  rerun = TRUE;
1655  }
1656  }
1657  }
1658  while( rerun && !SCIPisStopped(scip) ); /* extensive reduction loop*/
1659 
1660  if( fullreduce )
1661  {
1663  }
1664 
1665  /* free random number generator */
1666  SCIPfreeRandom(scip, &randnumgen);
1667 
1668  *fixed += fix;
1669 
1670  return SCIP_OKAY;
1671 }
1672 
1673 
1674 /** reduces the graph */
1676  SCIP* scip, /**< SCIP data structure */
1677  GRAPH** graph, /**< graph structure */
1678  SCIP_Real* offset, /**< pointer to store offset generated by reductions */
1679  int level, /**< reduction level 0: none, 1: basic, 2: advanced */
1680  int minelims, /**< minimal amount of reductions to reiterate reduction methods */
1681  SCIP_Bool userec /**< use recombination heuristic? */
1682  )
1683 {
1684  int stp_type;
1685 
1686  assert((*graph) != NULL);
1687  assert((*graph)->fixedges == NULL);
1688  assert(level >= 0 && level <= 2);
1689  assert(minelims >= 0);
1690  assert((*graph)->layers == 1);
1691 
1692  *offset = 0.0;
1693 
1694  stp_type = (*graph)->stp_type;
1695 
1696  /* initialize ancestor list for each edge */
1697  SCIP_CALL( graph_init_history(scip, (*graph)) );
1698 
1699  /* initialize shortest path algorithms */
1700  SCIP_CALL( graph_path_init(scip, (*graph)) );
1701 
1702  SCIP_CALL( level0(scip, (*graph)) );
1703 
1704  /* if no reduction methods available, return */
1705  if( (*graph)->stp_type == STP_DCSTP || (*graph)->stp_type == STP_RMWCSP )
1706  {
1707  graph_path_exit(scip, (*graph));
1708  return SCIP_OKAY;
1709  }
1710 
1711  if( level == 1 )
1712  {
1713  if( stp_type == STP_PCSPG || stp_type == STP_RPCSPG )
1714  {
1715  SCIP_CALL( reducePc(scip, (graph), offset, minelims, FALSE, FALSE) );
1716  }
1717  else if( stp_type == STP_MWCSP )
1718  {
1719  SCIP_CALL( reduceMw(scip, (graph), offset, minelims, FALSE, FALSE) );
1720  }
1721  else if( stp_type == STP_DHCSTP )
1722  {
1723  SCIP_CALL( reduceHc(scip, (graph), offset, minelims) );
1724  }
1725  else if( stp_type == STP_SAP )
1726  {
1727  SCIP_CALL( reduceSap(scip, (graph), offset, minelims) );
1728  }
1729  else if( stp_type == STP_NWSPG )
1730  {
1731  SCIP_CALL( reduceNw(scip, (graph), offset, minelims) );
1732  }
1733  else
1734  {
1735  SCIP_CALL( reduceStp(scip, (graph), offset, minelims, FALSE, TRUE, FALSE) );
1736  }
1737  }
1738  else if( level == 2 )
1739  {
1740  if( stp_type == STP_PCSPG || stp_type == STP_RPCSPG )
1741  {
1742  SCIP_CALL( reducePc(scip, (graph), offset, minelims, TRUE, userec) );
1743  }
1744  else if( stp_type == STP_MWCSP )
1745  {
1746  SCIP_CALL( reduceMw(scip, (graph), offset, minelims, TRUE, userec) );
1747  }
1748  else if( stp_type == STP_DHCSTP )
1749  {
1750  SCIP_CALL( reduceHc(scip, (graph), offset, minelims) );
1751  }
1752  else if( stp_type == STP_SAP )
1753  {
1754  SCIP_CALL( reduceSap(scip, (graph), offset, minelims) );
1755  }
1756  else if( stp_type == STP_NWSPG )
1757  {
1758  SCIP_CALL( reduceNw(scip, (graph), offset, minelims) );
1759  }
1760  else
1761  {
1762  SCIP_CALL( reduceStp(scip, (graph), offset, minelims, TRUE, TRUE, userec) );
1763  }
1764  }
1765  SCIPdebugMessage("offset : %f \n", *offset);
1766 
1767  SCIP_CALL( level0(scip, (*graph)) );
1768 
1769  assert(graph_valid(*graph));
1770 
1771  graph_path_exit(scip, (*graph));
1772 
1773  return SCIP_OKAY;
1774 }
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: grphpath.c:444
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void reduce_nnp(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:5450
static volatile int nterms
Definition: interrupt.c:38
SCIP_RETCODE level0(SCIP *scip, GRAPH *g)
Definition: reduce.c:153
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
static SCIP_RETCODE reducePc(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims, STP_Bool dualascent, SCIP_Bool userec)
Definition: reduce.c:338
Definition: grph.h:57
int source
Definition: grph.h:67
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_RETCODE graph_trail_arr(SCIP *, const GRAPH *, int)
Definition: grphbase.c:4242
void reduce_ans(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:4447
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4328
int terms
Definition: grph.h:64
SCIP_RETCODE reduce_rpt(SCIP *, GRAPH *, SCIP_Real *, int *)
SCIP_RETCODE reduceStp(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims, SCIP_Bool dualascent, SCIP_Bool nodereplacing, SCIP_Bool userec)
Definition: reduce.c:223
SCIP_RETCODE graph_init_history(SCIP *, GRAPH *)
Definition: grphbase.c:3573
#define EAT_LAST
Definition: grph.h:31
SCIP_RETCODE reduce_boundMw(SCIP *, GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
Definition: reduce_bnd.c:5243
SCIP_RETCODE level0save(SCIP *scip, GRAPH *g)
Definition: reduce.c:185
SCIP_RETCODE graph_pc_presolInit(SCIP *, GRAPH *)
Definition: grphbase.c:794
#define FALSE
Definition: def.h:73
SCIP_RETCODE reduce_contractZeroEdges(SCIP *, GRAPH *, SCIP_Bool)
int *RESTRICT inpbeg
Definition: grph.h:74
SCIP_RETCODE graph_pc_mw2rmw(SCIP *, GRAPH *, SCIP_Real)
Definition: grphbase.c:1850
#define STP_RMWCSP
Definition: grph.h:50
Problem data for stp problem.
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE reduce_boundHopRc(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, SCIP_Bool)
Definition: reduce_bnd.c:6226
void graph_path_exit(SCIP *, GRAPH *)
Definition: grphpath.c:466
#define STP_DHCSTP
Definition: grph.h:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
#define STP_PCSPG
Definition: grph.h:40
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_RETCODE redLoopMw(SCIP *scip, GRAPH *g, PATH *vnoi, PATH *path, GNODE **gnodearr, SCIP_Real *nodearrreal, SCIP_Real *edgearrreal, SCIP_Real *edgearrreal2, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, int *nodearrint3, int *solnode, STP_Bool *nodearrchar, SCIP_Real *fixed, STP_Bool advanced, STP_Bool bred, STP_Bool tryrmw, int redbound, SCIP_Bool userec)
Definition: reduce.c:923
static SCIP_RETCODE nvreduce_sl(SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *nodearrreal, SCIP_Real *fixed, int *edgearrint, int *heap, int *state, int *vbase, int *neighb, int *distnode, int *solnode, STP_Bool *visited, int *nelims, int minelims)
Definition: reduce.c:72
static SCIP_RETCODE reduceNw(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims)
Definition: reduce.c:826
#define STP_RED_BD3BOUND
Definition: reduce.c:34
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_RETCODE reduce_daPcMw(SCIP *, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, STP_Bool *, int *, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_RANDNUMGEN *, SCIP_Real)
Definition: reduce_bnd.c:3801
SCIP_RETCODE reduce_simple(SCIP *, GRAPH *, SCIP_Real *, int *, int *, int *)
#define STP_RED_MAXNROUNDS
Definition: reduce.c:37
#define STP_RED_SDSPBOUND2
Definition: reduce.c:33
int *RESTRICT mark
Definition: grph.h:70
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define STP_RED_EXTENSIVE
Definition: reduce.c:35
SCIP_Bool graph_pc_term2edgeConsistent(const GRAPH *)
Definition: grphbase.c:853
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE reduce_boundHopR(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
Definition: reduce_bnd.c:6098
void graph_pc_2org(GRAPH *)
Definition: grphbase.c:964
static SCIP_RETCODE reduceHc(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims)
Definition: reduce.c:571
SCIP_RETCODE reduce_simple_mw(SCIP *, GRAPH *, int *, SCIP_Real *, int *)
miscellaneous methods used for solving Steiner problems
#define STP_SAP
Definition: grph.h:39
int stp_type
Definition: grph.h:127
SCIP_RETCODE reduce_deleteConflictEdges(SCIP *, GRAPH *)
Definition: reduce_bnd.c:2421
SCIP_RETCODE reduce_sd(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, int *, SCIP_Bool, int *)
Definition: reduce_alt.c:1105
SCIP_RETCODE reduce_da(SCIP *, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, STP_Bool *, int *, int, SCIP_RANDNUMGEN *, SCIP_Bool, SCIP_Bool)
Definition: reduce_bnd.c:2861
void graph_pc_2trans(GRAPH *)
Definition: grphbase.c:1002
SCIP_RETCODE redLoopPc(SCIP *scip, GRAPH *g, PATH *vnoi, PATH *path, GNODE **gnodearr, SCIP_Real *nodearrreal, SCIP_Real *exedgearrreal, SCIP_Real *exedgearrreal2, int *heap, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, int *solnode, STP_Bool *nodearrchar, SCIP_Real *fixed, SCIP_Bool dualascent, SCIP_Bool bred, int reductbound, SCIP_Bool userec)
Definition: reduce.c:1160
unsigned char STP_Bool
Definition: grph.h:52
#define STP_DCSTP
Definition: grph.h:43
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
SCIP_Real * prize
Definition: grph.h:82
SCIP_RETCODE reduce_simple_sap(SCIP *, GRAPH *, SCIP_Real *, int *)
int *RESTRICT grad
Definition: grph.h:73
void print(const Container &container, const std::string &prefix="", const std::string &suffix="", std::ostream &os=std::cout, bool negate=false, int prec=6)
void graph_pc_presolExit(SCIP *, GRAPH *)
Definition: grphbase.c:837
#define NULL
Definition: lpi_spx1.cpp:155
int knots
Definition: grph.h:62
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE reduce_bd34(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2964
SCIP_RETCODE reduce_nvAdv(SCIP *, GRAPH *, PATH *, SCIP_Real *, double *, int *, int *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:3903
#define STP_NWSPG
Definition: grph.h:42
SCIP_Real graph_pc_getPosPrizeSum(SCIP *, const GRAPH *)
Definition: grphbase.c:1054
SCIP_RETCODE reduce_simple_hc(SCIP *, GRAPH *, SCIP_Real *, int *)
#define FARAWAY
Definition: grph.h:156
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
propagator for Steiner tree problems, using the LP reduced costs
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
void reduce_ansAdv2(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:4621
void reduce_ansAdv(SCIP *, GRAPH *, int *, int *, SCIP_Bool)
Definition: reduce_alt.c:4515
SCIP_RETCODE reduce(SCIP *scip, GRAPH **graph, SCIP_Real *offset, int level, int minelims, SCIP_Bool userec)
Definition: reduce.c:1675
SCIP_RETCODE reduce_simple_pc(SCIP *, GRAPH *, SCIP_Real *, int *, int *, SCIP_Bool)
#define SCIP_Bool
Definition: def.h:70
SCIP_Real SCIPgetTotalTime(SCIP *scip)
Definition: scip_timing.c:333
SCIP_RETCODE reduce_boundHop(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *)
Definition: reduce_bnd.c:5904
#define STP_MWCSP
Definition: grph.h:47
static SCIP_RETCODE reduceSap(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims)
Definition: reduce.c:691
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE reduce_sl(SCIP *, GRAPH *, PATH *, double *, int *, int *, int *, int *, STP_Bool *, int *, int *)
Definition: reduce_alt.c:3483
#define STP_RED_MWTERMBOUND
Definition: reduce.c:36
int *RESTRICT term
Definition: grph.h:68
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: grphbase.c:2841
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:126
SCIP_RETCODE reduce_ledge(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:4143
SCIP_RETCODE reduce_sdPc(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:1499
SCIP_RETCODE redLoopStp(SCIP *scip, GRAPH *g, PATH *vnoi, PATH *path, GNODE **gnodearr, SCIP_Real *nodearrreal, SCIP_Real *edgearrreal, SCIP_Real *edgearrreal2, int *heap, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, int *solnode, STP_Bool *nodearrchar, SCIP_Real *fixed, SCIP_Real upperbound, SCIP_Bool dualascent, SCIP_Bool boundreduce, SCIP_Bool nodereplacing, int reductbound, SCIP_Bool userec, SCIP_Bool fullreduce)
Definition: reduce.c:1411
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE reduce_bound(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *)
Definition: reduce_bnd.c:4653
#define Is_term(a)
Definition: grph.h:168
SCIP_Real * cost
Definition: grph.h:94
SCIP_RETCODE reduce_sdspSap(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2308
#define SCIP_Real
Definition: def.h:163
static SCIP_RETCODE reduceMw(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims, STP_Bool advanced, SCIP_Bool userec)
Definition: reduce.c:459
shortest paths based primal heuristics for Steiner problems
#define STP_RED_SDSPBOUND
Definition: reduce.c:32
int edges
Definition: grph.h:92
static void reduceStatsPrint(SCIP_Bool print, const char *method, int nelims)
Definition: reduce.c:55
#define nnodes
Definition: gastrans.c:65
SCIP_RETCODE reduce_npv(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:5024
#define STP_RPCSPG
Definition: grph.h:41
SCIP_RETCODE reduce_sdsp(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int, int *)
Definition: reduce_alt.c:2459
SCIP callable library.
SCIP_RETCODE reduce_chain2(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:5367
#define STP_RED_EXFACTOR
Definition: reduce.c:38