Scippy

SCIP

Solving Constraint Integer Programs

stptest_heurlocal.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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file stptest_heurlocal.c
17  * @brief tests for Steiner tree heuristics
18  * @author Daniel Rehfeldt
19  *
20  * This file implements tests for Steiner problem local search heuristics.
21  *
22  * A list of all interface methods can be found in stptest.h.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include <stdio.h>
29 #include <assert.h>
30 #include "stptest.h"
31 #include "graph.h"
32 #include "solstp.h"
33 #include "heur_local.h"
34 #include "heur_tm.h"
35 
36 
37 /** test key path exchange */
38 static
39 SCIP_RETCODE localKeyPathExchange(
40  SCIP* scip /**< SCIP data structure */
41 )
42 {
43  GRAPH* graph;
44  int* steinertree;
45  int nnodes = 6;
46  int nedges = 6;
47 
48  assert(scip);
49 
50  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
51 
52  for( int i = 0; i < nnodes; i++ )
53  graph_knot_add(graph, -1);
54 
55  graph_knot_chg(graph, 0, 0);
56  graph_knot_chg(graph, 2, 0);
57  graph_knot_chg(graph, 3, 0);
58  graph_knot_chg(graph, 4, 0);
59  graph->source = 0;
60 
61  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
62  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
63  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
64  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
65  graph_edge_add(scip, graph, 4, 5, 1.0, 1.0);
66  graph_edge_add(scip, graph, 5, 0, 2.0, 2.0); // 10,11
67 
68  SCIP_CALL(graph_initHistory(scip, graph));
69  SCIP_CALL(graph_path_init(scip, graph));
70 
71  graph_mark(graph);
72 
73  nnodes = graph->knots;
74  nedges = graph->edges;
75 
76  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
77 
78  for( int i = 0; i < nedges; i++ )
79  steinertree[i] = UNKNOWN;
80 
81  steinertree[0] = CONNECT;
82  steinertree[2] = CONNECT;
83  steinertree[4] = CONNECT;
84  steinertree[6] = CONNECT;
85 
86  assert(solstp_isValid(scip, graph, steinertree));
87 
88  /* actual test */
89  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
90 
91  assert(steinertree[11] == CONNECT && steinertree[9] == CONNECT);
92  assert(steinertree[0] == UNKNOWN && steinertree[2] == UNKNOWN);
93 
94  graph_path_exit(scip, graph);
95  graph_free(scip, &graph, TRUE);
96 
97  SCIPfreeMemoryArray(scip, &steinertree);
98 
99  return SCIP_OKAY;
100 }
101 
102 
103 /** test key path exchange */
104 static
105 SCIP_RETCODE localKeyPathExchangePc(
106  SCIP* scip /**< SCIP data structure */
107 )
108 {
109  GRAPH* graph;
110  int* steinertree;
111  STP_Bool* steinertree_nodes;
112  int nnodes = 6;
113  int nedges = 6;
114 
115  assert(scip);
116 
117  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
118 
119  for( int i = 0; i < nnodes; i++ )
120  graph_knot_add(graph, -1);
121 
122  graph->source = 0;
123 
124  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
125  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
126  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
127  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
128  graph_edge_add(scip, graph, 4, 5, 2.0, 2.0);
129  graph_edge_add(scip, graph, 5, 0, 3.0, 3.0); // 10,11
130 
131  nnodes = graph->knots;
132  nedges = graph->edges;
133 
134  graph_pc_initPrizes(scip, graph, nnodes);
135 
136  for( int i = 0; i < nnodes; i++ )
137  graph->prize[i] = 0.0;
138 
139  graph->prize[0] = 5.0;
140  graph->prize[2] = 3.0;
141  graph->prize[3] = 3.1;
142  graph->prize[4] = 3.1;
143  graph->prize[5] = 3;
144 
145  graph_knot_chg(graph, 0, 0);
146  graph_knot_chg(graph, 2, 0);
147  graph_knot_chg(graph, 3, 0);
148  graph_knot_chg(graph, 4, 0);
149  graph_knot_chg(graph, 5, 0);
150 
151  SCIP_CALL(graph_transPc(scip, graph));
152 
153  nnodes = graph->knots;
154  nedges = graph->edges;
155 
156  SCIP_CALL(graph_initHistory(scip, graph));
157  SCIP_CALL(graph_path_init(scip, graph));
158 
159  graph_mark(graph);
160 
161  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
162  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
163 
164  for( int i = 0; i < nedges; i++ )
165  steinertree[i] = UNKNOWN;
166 
167  for( int i = 0; i < nnodes; i++ )
168  steinertree_nodes[i] = FALSE;
169 
170  steinertree_nodes[0] = TRUE;
171  steinertree_nodes[1] = TRUE;
172  steinertree_nodes[2] = TRUE;
173  steinertree_nodes[3] = TRUE;
174  steinertree_nodes[4] = TRUE;
175 
176  // 4 is the implicit root
177 
178  SCIP_CALL( solstp_prune(scip, graph, steinertree, steinertree_nodes) );
179 
180  assert(solstp_isValid(scip, graph, steinertree));
181 
182  /* actual test */
183  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
184 
185  // 5 is the implicit root
186 
187  assert(steinertree[9] == CONNECT && steinertree[10] == CONNECT);
188  assert(steinertree[0] == UNKNOWN && steinertree[2] == UNKNOWN);
189 
190  graph_path_exit(scip, graph);
191  graph_free(scip, &graph, TRUE);
192 
193  SCIPfreeMemoryArray(scip, &steinertree_nodes);
194  SCIPfreeMemoryArray(scip, &steinertree);
195 
196  return SCIP_OKAY;
197 }
198 
199 
200 /** test key path exchange */
201 static
202 SCIP_RETCODE localKeyPathExchangePc2(
203  SCIP* scip /**< SCIP data structure */
204 )
205 {
206  GRAPH* graph;
207  int* steinertree;
208  STP_Bool* steinertree_nodes;
209  int nnodes = 7;
210  int nedges = 7;
211  SCIP_Real cost0;
212  SCIP_Real cost1;
213 
214  assert(scip);
215 
216  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
217 
218  for( int i = 0; i < nnodes; i++ )
219  graph_knot_add(graph, -1);
220 
221  graph->source = 0;
222 
223  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
224  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
225  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
226  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
227  graph_edge_add(scip, graph, 4, 5, 2.0, 2.0);
228  graph_edge_add(scip, graph, 5, 6, 1.0, 1.0); // 10,11
229  graph_edge_add(scip, graph, 6, 0, 2.0, 2.0); // 12,13
230 
231  nnodes = graph->knots;
232  nedges = graph->edges;
233 
234  graph_pc_initPrizes(scip, graph, nnodes);
235 
236  for( int i = 0; i < nnodes; i++ )
237  graph->prize[i] = 0.0;
238 
239  graph->prize[0] = 5.0;
240  graph->prize[2] = 3.0;
241  graph->prize[3] = 3.1;
242  graph->prize[4] = 3.1;
243  graph->prize[5] = 1.0;
244  graph->prize[6] = 1.0;
245 
246 
247  graph_knot_chg(graph, 0, 0);
248  graph_knot_chg(graph, 2, 0);
249  graph_knot_chg(graph, 3, 0);
250  graph_knot_chg(graph, 4, 0);
251  graph_knot_chg(graph, 5, 0);
252  graph_knot_chg(graph, 6, 0);
253 
254  SCIP_CALL(graph_transPc(scip, graph));
255 
256  nnodes = graph->knots;
257  nedges = graph->edges;
258 
259  SCIP_CALL(graph_initHistory(scip, graph));
260  SCIP_CALL(graph_path_init(scip, graph));
261 
262  graph_mark(graph);
263 
264  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
265  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
266 
267  for( int i = 0; i < nedges; i++ )
268  steinertree[i] = UNKNOWN;
269 
270  for( int i = 0; i < nnodes; i++ )
271  steinertree_nodes[i] = FALSE;
272 
273  steinertree_nodes[0] = TRUE;
274  steinertree_nodes[1] = TRUE;
275  steinertree_nodes[2] = TRUE;
276  steinertree_nodes[3] = TRUE;
277  steinertree_nodes[4] = TRUE;
278 
279  // 4 is the implicit root
280 
281  SCIP_CALL( solstp_prune(scip, graph, steinertree, steinertree_nodes) );
282 
283  assert(solstp_isValid(scip, graph, steinertree));
284 
285  cost0 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
286 
287  /* actual test */
288  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
289 
290  // 5 is the implicit root
291 
292  cost1 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
293 
294  if( !SCIPisEQ(scip, cost1 + 1.0, cost0) )
295  return SCIP_ERROR;
296 
297  graph_path_exit(scip, graph);
298  graph_free(scip, &graph, TRUE);
299 
300  SCIPfreeMemoryArray(scip, &steinertree_nodes);
301  SCIPfreeMemoryArray(scip, &steinertree);
302 
303  return SCIP_OKAY;
304 }
305 
306 
307 /** test key path exchange */
308 static
309 SCIP_RETCODE localKeyPathExchangeMw(
310  SCIP* scip /**< SCIP data structure */
311 )
312 {
313  GRAPH* graph;
314  int* steinertree;
315  STP_Bool* steinertree_nodes;
316  int nnodes = 8;
317  int nedges = 8;
318  SCIP_Real cost0;
319  SCIP_Real cost1;
320 
321  assert(scip);
322 
323  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
324 
325  for( int i = 0; i < nnodes; i++ )
326  graph_knot_add(graph, -1);
327 
328  graph->source = 0;
329 
330  graph_edge_add(scip, graph, 0, 1, 0.0, 0.0); // 0,1
331  graph_edge_add(scip, graph, 1, 2, 0.0, 0.0); // 2,3
332  graph_edge_add(scip, graph, 2, 3, 0.0, 0.0);
333  graph_edge_add(scip, graph, 2, 4, 0.0, 0.0);
334  graph_edge_add(scip, graph, 4, 5, 0.0, 0.0);
335  graph_edge_add(scip, graph, 5, 6, 0.0, 0.0); // 10,11
336  graph_edge_add(scip, graph, 6, 7, 0.0, 0.0);
337  graph_edge_add(scip, graph, 7, 0, 0.0, 0.0); // 14,15
338 
339  nnodes = graph->knots;
340  nedges = graph->edges;
341 
342  graph_pc_initPrizes(scip, graph, nnodes);
343 
344 
345  graph->prize[0] = 5.0;
346  graph->prize[1] = -2.0;
347  graph->prize[2] = -2.0;
348  graph->prize[3] = 3.0;
349  graph->prize[4] = 3.0;
350  graph->prize[5] = -1.0;
351  graph->prize[6] = 0.5;
352  graph->prize[7] = -1.0;
353 
354  SCIP_CALL(graph_transMw(scip, graph));
355 
356  nnodes = graph->knots;
357  nedges = graph->edges;
358 
359  SCIP_CALL(graph_initHistory(scip, graph));
360  SCIP_CALL(graph_path_init(scip, graph));
361 
362  graph_mark(graph);
363 
364  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
365  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
366 
367  for( int i = 0; i < nedges; i++ )
368  steinertree[i] = UNKNOWN;
369 
370  for( int i = 0; i < nnodes; i++ )
371  steinertree_nodes[i] = FALSE;
372 
373  steinertree_nodes[0] = TRUE;
374  steinertree_nodes[1] = TRUE;
375  steinertree_nodes[2] = TRUE;
376  steinertree_nodes[3] = TRUE;
377  steinertree_nodes[4] = TRUE;
378 
379  // 4 is the implicit root
380 
381  SCIP_CALL( solstp_prune(scip, graph, steinertree, steinertree_nodes) );
382 
383  assert(solstp_isValid(scip, graph, steinertree));
384 
385  cost0 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
386 
387  /* actual test */
388  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
389 
390  // 5 is the implicit root
391 
392  cost1 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
393 
394  if( !SCIPisEQ(scip, cost1 + 0.5, cost0) )
395  return SCIP_ERROR;
396 
397  graph_path_exit(scip, graph);
398  graph_free(scip, &graph, TRUE);
399 
400  SCIPfreeMemoryArray(scip, &steinertree_nodes);
401  SCIPfreeMemoryArray(scip, &steinertree);
402 
403  return SCIP_OKAY;
404 }
405 
406 
407 /** test key vertex elimination */
408 static
409 SCIP_RETCODE localKeyVertex(
410  SCIP* scip /**< SCIP data structure */
411 )
412 {
413  GRAPH* graph;
414  int* steinertree;
415  STP_Bool* steinertree_nodes;
416  int nnodes = 7;
417  int nedges = 8;
418  SCIP_Real cost0;
419  SCIP_Real cost1;
420 
421  assert(scip);
422 
423  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
424 
425  for( int i = 0; i < nnodes; i++ )
426  graph_knot_add(graph, -1);
427 
428  graph->source = 0;
429 
430  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
431  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
432  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
433  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
434  graph_edge_add(scip, graph, 4, 5, 2.0, 2.0);
435  graph_edge_add(scip, graph, 5, 0, 3.0, 3.0); // 10,11
436  graph_edge_add(scip, graph, 6, 3, 1.0, 1.0); // 12,13
437  graph_edge_add(scip, graph, 6, 4, 1.0, 1.0); // 14,15
438 
439  nnodes = graph->knots;
440  nedges = graph->edges;
441 
442  graph_knot_chg(graph, 0, 0);
443  graph_knot_chg(graph, 3, 0);
444  graph_knot_chg(graph, 4, 0);
445 
446  SCIP_CALL(graph_initHistory(scip, graph));
447  SCIP_CALL(graph_path_init(scip, graph));
448 
449  graph_mark(graph);
450 
451  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
452  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
453 
454  for( int i = 0; i < nedges; i++ )
455  steinertree[i] = UNKNOWN;
456 
457  for( int i = 0; i < nnodes; i++ )
458  steinertree_nodes[i] = FALSE;
459 
460  steinertree_nodes[0] = TRUE;
461  steinertree_nodes[1] = TRUE;
462  steinertree_nodes[2] = TRUE;
463  steinertree_nodes[3] = TRUE;
464  steinertree_nodes[4] = TRUE;
465 
466  // 4 is the implicit root
467 
468  SCIP_CALL( solstp_prune(scip, graph, steinertree, steinertree_nodes) );
469  assert(solstp_isValid(scip, graph, steinertree));
470 
471  cost0 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
472 
473  assert(steinertree[12] != CONNECT && steinertree[15] != CONNECT);
474  assert(steinertree[0] == CONNECT && steinertree[2] == CONNECT);
475 
476  /* actual test */
477  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
478 
479  // 5 is the implicit root
480 
481  cost1 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
482  if( !SCIPisEQ(scip, cost1 + 1.0, cost0) )
483  return SCIP_ERROR;
484 
485  assert(steinertree[12] == CONNECT && steinertree[15] == CONNECT);
486  assert(steinertree[0] == UNKNOWN && steinertree[2] == UNKNOWN);
487 
488  graph_path_exit(scip, graph);
489  graph_free(scip, &graph, TRUE);
490 
491  SCIPfreeMemoryArray(scip, &steinertree_nodes);
492  SCIPfreeMemoryArray(scip, &steinertree);
493 
494  return SCIP_OKAY;
495 }
496 
497 
498 /** test key vertex elimination */
499 static
500 SCIP_RETCODE localKeyVertexPc(
501  SCIP* scip /**< SCIP data structure */
502 )
503 {
504  GRAPH* graph;
505  int* steinertree;
506  STP_Bool* steinertree_nodes;
507  int nnodes = 7;
508  int nedges = 8;
509  SCIP_Real cost0;
510  SCIP_Real cost1;
511 
512  assert(scip);
513 
514  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
515 
516  for( int i = 0; i < nnodes; i++ )
517  graph_knot_add(graph, -1);
518 
519  graph->source = 0;
520 
521  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
522  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
523  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
524  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
525  graph_edge_add(scip, graph, 4, 5, 3.0, 3.0);
526  graph_edge_add(scip, graph, 5, 0, 3.0, 3.0); // 10,11
527  graph_edge_add(scip, graph, 6, 3, 2.0, 2.0); // 12,13
528  graph_edge_add(scip, graph, 6, 4, 2.0, 2.0); // 14,15
529 
530  nnodes = graph->knots;
531  nedges = graph->edges;
532 
533  graph_pc_initPrizes(scip, graph, nnodes);
534 
535  for( int i = 0; i < nnodes; i++ )
536  graph->prize[i] = 0.0;
537 
538  graph->prize[0] = 5.0;
539  // graph->prize[2] = 3.0; // todo
540  graph->prize[3] = 3.0;
541  graph->prize[4] = 3.0;
542  graph->prize[5] = 1.5;
543  graph->prize[6] = 1.0;
544 
545 
546  graph_knot_chg(graph, 0, 0);
547  // graph_knot_chg(graph, 2, 0); todo activate again as non-leaf later
548  graph_knot_chg(graph, 3, 0);
549  graph_knot_chg(graph, 4, 0);
550  graph_knot_chg(graph, 5, 0);
551  graph_knot_chg(graph, 6, 0);
552 
553  SCIP_CALL(graph_transPc(scip, graph));
554 
555  nnodes = graph->knots;
556  nedges = graph->edges;
557 
558  SCIP_CALL(graph_initHistory(scip, graph));
559  SCIP_CALL(graph_path_init(scip, graph));
560 
561  graph_mark(graph);
562 
563  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
564  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
565 
566  for( int i = 0; i < nedges; i++ )
567  steinertree[i] = UNKNOWN;
568 
569  for( int i = 0; i < nnodes; i++ )
570  steinertree_nodes[i] = FALSE;
571 
572  steinertree_nodes[0] = TRUE;
573  steinertree_nodes[1] = TRUE;
574  steinertree_nodes[2] = TRUE;
575  steinertree_nodes[3] = TRUE;
576  steinertree_nodes[4] = TRUE;
577 
578  // 4 is the implicit root
579 
580  SCIP_CALL( solstp_prune(scip, graph, steinertree, steinertree_nodes) );
581  assert(solstp_isValid(scip, graph, steinertree));
582 
583  cost0 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
584 
585  assert(steinertree[12] != CONNECT && steinertree[15] != CONNECT);
586  assert(steinertree[1] == CONNECT && steinertree[3] == CONNECT);
587 
588  /* actual test */
589  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
590 
591 
592  cost1 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
593  if( !SCIPisEQ(scip, cost1 + 0.5, cost0) )
594  return SCIP_ERROR;
595 
596  assert(steinertree[0] == UNKNOWN && steinertree[2] == UNKNOWN);
597 
598  graph_path_exit(scip, graph);
599  graph_free(scip, &graph, TRUE);
600 
601  SCIPfreeMemoryArray(scip, &steinertree_nodes);
602  SCIPfreeMemoryArray(scip, &steinertree);
603 
604  return SCIP_OKAY;
605 }
606 
607 
608 /** test key vertex elimination */
609 static
610 SCIP_RETCODE localKeyVertexPc2(
611  SCIP* scip /**< SCIP data structure */
612 )
613 {
614  GRAPH* graph;
615  int* steinertree;
616  STP_Bool* steinertree_nodes;
617  int nnodes = 9;
618  int nedges = 10;
619  SCIP_Real cost0;
620  SCIP_Real cost1;
621 
622  assert(scip);
623 
624  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
625 
626  for( int i = 0; i < nnodes; i++ )
627  graph_knot_add(graph, -1);
628 
629  graph->source = 0;
630 
631  /* the solution */
632  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
633  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
634  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
635  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
636 
637  /* the right part */
638  graph_edge_add(scip, graph, 4, 5, 2.0, 2.0);
639  graph_edge_add(scip, graph, 5, 6, 1.0, 1.0); // 10,11
640  graph_edge_add(scip, graph, 6, 7, 1.0, 1.0); // 12,13
641  graph_edge_add(scip, graph, 7, 0, 2.0, 2.0); // 14,15
642 
643  /* the hat */
644  graph_edge_add(scip, graph, 8, 3, 2.0, 2.0); // 16,17
645  graph_edge_add(scip, graph, 8, 4, 2.0, 2.0); // 18,19
646 
647  nnodes = graph->knots;
648  nedges = graph->edges;
649 
650  graph_pc_initPrizes(scip, graph, nnodes);
651 
652  for( int i = 0; i < nnodes; i++ )
653  graph->prize[i] = 0.0;
654 
655  graph->prize[0] = 5.0;
656  // graph->prize[2] = 3.0; // todo
657  graph->prize[3] = 3.0;
658  graph->prize[4] = 3.0;
659  graph->prize[6] = 1.5;
660  graph->prize[8] = 1.0;
661 
662 
663  graph_knot_chg(graph, 0, 0);
664  // graph_knot_chg(graph, 2, 0); todo activate again as non-leaf later
665  graph_knot_chg(graph, 3, 0);
666  graph_knot_chg(graph, 4, 0);
667  graph_knot_chg(graph, 6, 0);
668  graph_knot_chg(graph, 8, 0);
669 
670 
671  SCIP_CALL(graph_transPc(scip, graph));
672 
673  nnodes = graph->knots;
674  nedges = graph->edges;
675 
676  SCIP_CALL(graph_initHistory(scip, graph));
677  SCIP_CALL(graph_path_init(scip, graph));
678 
679  graph_mark(graph);
680 
681  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
682  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
683 
684  for( int i = 0; i < nedges; i++ )
685  steinertree[i] = UNKNOWN;
686 
687  for( int i = 0; i < nnodes; i++ )
688  steinertree_nodes[i] = FALSE;
689 
690  steinertree_nodes[0] = TRUE;
691  steinertree_nodes[1] = TRUE;
692  steinertree_nodes[2] = TRUE;
693  steinertree_nodes[3] = TRUE;
694  steinertree_nodes[4] = TRUE;
695 
696  // 4 is the implicit root
697 
698  SCIP_CALL( solstp_prune(scip, graph, steinertree, steinertree_nodes) );
699  assert(solstp_isValid(scip, graph, steinertree));
700 
701  cost0 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
702 
703  assert(steinertree[16] == UNKNOWN && steinertree[18] == UNKNOWN);
704  assert(steinertree[1] == CONNECT && steinertree[3] == CONNECT);
705 
706  /* actual test */
707  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
708 
709  // 6 is the implicit root
710 
711  cost1 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
712  if( !SCIPisEQ(scip, cost1 + 0.5, cost0) )
713  return SCIP_ERROR;
714 
715  assert(steinertree[0] == UNKNOWN && steinertree[2] == UNKNOWN);
716 
717  graph_path_exit(scip, graph);
718  graph_free(scip, &graph, TRUE);
719 
720  SCIPfreeMemoryArray(scip, &steinertree_nodes);
721  SCIPfreeMemoryArray(scip, &steinertree);
722 
723  return SCIP_OKAY;
724 }
725 
726 
727 /** extension test */
728 static
729 SCIP_RETCODE localExtendPc(
730  SCIP* scip /**< SCIP data structure */
731 )
732 {
733  GRAPH* graph;
734  int* steinertree;
735  STP_Bool* steinertree_nodes;
736  int nnodes = 9;
737  int nedges = 9;
738  SCIP_Real cost0;
739  SCIP_Real cost1;
740 
741  assert(scip);
742 
743  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
744 
745  for( int i = 0; i < nnodes; i++ )
746  graph_knot_add(graph, -1);
747 
748  graph->source = 0;
749 
750  /* the solution */
751  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
752  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
753  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
754  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
755 
756  /* the right part */
757  graph_edge_add(scip, graph, 4, 5, 1.0, 1.0);
758  graph_edge_add(scip, graph, 5, 6, 1.0, 1.0); // 10,11
759  graph_edge_add(scip, graph, 6, 7, 1.0, 1.0); // 12,13
760 
761  /* dummy part */
762  graph_edge_add(scip, graph, 7, 8, 5.0, 5.0); // 16,17
763  graph_edge_add(scip, graph, 8, 1, 5.0, 5.0); // 18,19
764 
765  nnodes = graph->knots;
766  nedges = graph->edges;
767 
768  graph_pc_initPrizes(scip, graph, nnodes);
769 
770  for( int i = 0; i < nnodes; i++ )
771  graph->prize[i] = 0.0;
772 
773  graph->prize[0] = 5.0;
774  // graph->prize[2] = 3.0; // todo
775  graph->prize[3] = 3.0;
776  graph->prize[4] = 3.0;
777  graph->prize[6] = 1.0;
778  graph->prize[7] = 2.5;
779 
780  graph->prize[8] = 0.5;
781 
782 
783  graph_knot_chg(graph, 0, 0);
784  // graph_knot_chg(graph, 2, 0); todo activate again as non-leaf later
785  graph_knot_chg(graph, 3, 0);
786  graph_knot_chg(graph, 4, 0);
787  graph_knot_chg(graph, 6, 0);
788  graph_knot_chg(graph, 7, 0);
789  graph_knot_chg(graph, 8, 0);
790 
791 
792  SCIP_CALL(graph_transPc(scip, graph));
793 
794  nnodes = graph->knots;
795  nedges = graph->edges;
796 
797  SCIP_CALL(graph_initHistory(scip, graph));
798  SCIP_CALL(graph_path_init(scip, graph));
799 
800  graph_mark(graph);
801 
802  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
803  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
804 
805  for( int i = 0; i < nedges; i++ )
806  steinertree[i] = UNKNOWN;
807 
808  for( int i = 0; i < nnodes; i++ )
809  steinertree_nodes[i] = FALSE;
810 
811  steinertree_nodes[0] = TRUE;
812  steinertree_nodes[1] = TRUE;
813  steinertree_nodes[2] = TRUE;
814  steinertree_nodes[3] = TRUE;
815  steinertree_nodes[4] = TRUE;
816 
817  SCIP_CALL( solstp_prune(scip, graph, steinertree, steinertree_nodes) );
818  assert(solstp_isValid(scip, graph, steinertree));
819 
820  cost0 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
821 
822  /* actual test */
823  SCIP_CALL( SCIPStpHeurLocalExtendPcMw(scip, graph, graph->cost, steinertree, steinertree_nodes) );
824 
825  cost1 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
826  if( !SCIPisEQ(scip, cost1 + 0.5, cost0) )
827  return SCIP_ERROR;
828 
829  graph_path_exit(scip, graph);
830  graph_free(scip, &graph, TRUE);
831 
832  SCIPfreeMemoryArray(scip, &steinertree_nodes);
833  SCIPfreeMemoryArray(scip, &steinertree);
834 
835  return SCIP_OKAY;
836 }
837 
838 /** test insertion */
839 static
840 SCIP_RETCODE localInsertion(
841  SCIP* scip /**< SCIP data structure */
842 )
843 {
844  GRAPH* graph;
845  int* steinertree;
846  int nnodes = 6;
847  int nedges = 7;
848  SCIP_Real cost0;
849  SCIP_Real cost1;
850 
851  assert(scip);
852 
853  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
854 
855  graph->stp_type = STP_SPG;
856 
857  for( int i = 0; i < nnodes; i++ )
858  graph_knot_add(graph, -1);
859 
860  graph_knot_chg(graph, 0, 0);
861  graph_knot_chg(graph, 2, 0);
862  graph_knot_chg(graph, 3, 0);
863  graph_knot_chg(graph, 4, 0);
864  graph->source = 0;
865 
866  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
867  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
868  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
869  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
870 
871  graph_edge_add(scip, graph, 5, 1, 1.0, 1.0);
872  graph_edge_add(scip, graph, 5, 3, 1.0, 1.0); // 10,11
873  graph_edge_add(scip, graph, 5, 4, 1.0, 1.0); // 12,13
874 
875  SCIP_CALL(graph_initHistory(scip, graph));
876  SCIP_CALL(graph_path_init(scip, graph));
877 
878  graph_mark(graph);
879 
880  nnodes = graph->knots;
881  nedges = graph->edges;
882 
883  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
884 
885  for( int i = 0; i < nedges; i++ )
886  steinertree[i] = UNKNOWN;
887 
888  steinertree[0] = CONNECT;
889  steinertree[2] = CONNECT;
890  steinertree[4] = CONNECT;
891  steinertree[6] = CONNECT;
892 
893  assert(solstp_isValid(scip, graph, steinertree));
894 
895  cost0 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
896 
897 
898  /* actual test */
899  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
900 
901  cost1 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
902 
903  if( !SCIPisEQ(scip, cost1 + 1.0, cost0) )
904  return SCIP_ERROR;
905 
906  graph_path_exit(scip, graph);
907  graph_free(scip, &graph, TRUE);
908 
909  SCIPfreeMemoryArray(scip, &steinertree);
910 
911  return SCIP_OKAY;
912 }
913 
914 
915 /** test insertion */
916 static
917 SCIP_RETCODE localInsertion2(
918  SCIP* scip /**< SCIP data structure */
919 )
920 {
921  GRAPH* graph;
922  int* steinertree;
923  int nnodes = 6;
924  int nedges = 7;
925  SCIP_Real cost0;
926  SCIP_Real cost1;
927 
928  assert(scip);
929 
930  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
931 
932  graph->stp_type = STP_SPG;
933 
934  for( int i = 0; i < nnodes; i++ )
935  graph_knot_add(graph, -1);
936 
937  graph_knot_chg(graph, 0, 0);
938  graph_knot_chg(graph, 2, 0);
939  graph_knot_chg(graph, 3, 0);
940  graph_knot_chg(graph, 4, 0);
941  graph->source = 0;
942 
943  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
944  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
945  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
946  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
947 
948  graph_edge_add(scip, graph, 5, 0, 1.5, 1.5);
949  graph_edge_add(scip, graph, 5, 3, 1.5, 1.5); // 10,11
950  graph_edge_add(scip, graph, 5, 4, 1.5, 1.5); // 12,13
951 
952  SCIP_CALL(graph_initHistory(scip, graph));
953  SCIP_CALL(graph_path_init(scip, graph));
954 
955  graph_mark(graph);
956 
957  nnodes = graph->knots;
958  nedges = graph->edges;
959 
960  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
961 
962  for( int i = 0; i < nedges; i++ )
963  steinertree[i] = UNKNOWN;
964 
965  steinertree[0] = CONNECT;
966  steinertree[2] = CONNECT;
967  steinertree[4] = CONNECT;
968  steinertree[6] = CONNECT;
969 
970  assert(solstp_isValid(scip, graph, steinertree));
971 
972  cost0 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
973 
974 
975  /* actual test */
976  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
977 
978  cost1 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
979 
980  if( !SCIPisEQ(scip, cost1 + 1.5, cost0) )
981  {
982  printf("localInsertion2 unit test failed \n");
983  printf("cost1=%f, cost0=%f \n", cost1, cost0);
984 
985  return SCIP_ERROR;
986  }
987 
988  graph_path_exit(scip, graph);
989  graph_free(scip, &graph, TRUE);
990 
991  SCIPfreeMemoryArray(scip, &steinertree);
992 
993  return SCIP_OKAY;
994 }
995 
996 
997 /** test insertion */
998 static
999 SCIP_RETCODE localInsertion2pc(
1000  SCIP* scip /**< SCIP data structure */
1001 )
1002 {
1003  GRAPH* graph;
1004  int* steinertree;
1005  STP_Bool* steinertree_nodes;
1006  int nnodes = 6;
1007  int nedges = 7;
1008  SCIP_Real cost0;
1009  SCIP_Real cost1;
1010 
1011  assert(scip);
1012 
1013  SCIP_CALL(graph_init(scip, &graph, nnodes, 2 * nedges, 1));
1014 
1015  graph->stp_type = STP_SPG;
1016 
1017  for( int i = 0; i < nnodes; i++ )
1018  graph_knot_add(graph, -1);
1019 
1020 
1021  graph->source = 0;
1022 
1023  graph_edge_add(scip, graph, 0, 1, 2.0, 2.0); // 0,1
1024  graph_edge_add(scip, graph, 1, 2, 2.0, 2.0); // 2,3
1025  graph_edge_add(scip, graph, 2, 3, 2.0, 2.0);
1026  graph_edge_add(scip, graph, 2, 4, 2.0, 2.0);
1027 
1028  graph_edge_add(scip, graph, 5, 0, 1.5, 1.5);
1029  graph_edge_add(scip, graph, 5, 3, 1.5, 1.5); // 10,11
1030  graph_edge_add(scip, graph, 5, 4, 1.5, 1.5); // 12,13
1031 
1032  nnodes = graph->knots;
1033  nedges = graph->edges;
1034 
1035  graph_pc_initPrizes(scip, graph, nnodes);
1036 
1037  for( int i = 0; i < nnodes; i++ )
1038  graph->prize[i] = 0.0;
1039 
1040  graph->prize[0] = 5.0;
1041  graph->prize[1] = 0.75;
1042  graph->prize[2] = 2.1;
1043  graph->prize[3] = 4.0;
1044  graph->prize[4] = 4.0;
1045 
1046  graph_knot_chg(graph, 0, 0);
1047  graph_knot_chg(graph, 1, 0);
1048  graph_knot_chg(graph, 2, 0);
1049  graph_knot_chg(graph, 3, 0);
1050  graph_knot_chg(graph, 4, 0);
1051 
1052  SCIP_CALL(graph_transPc(scip, graph));
1053 
1054  nnodes = graph->knots;
1055  nedges = graph->edges;
1056 
1057  SCIP_CALL(graph_initHistory(scip, graph));
1058  SCIP_CALL(graph_path_init(scip, graph));
1059 
1060  graph_mark(graph);
1061 
1062  nnodes = graph->knots;
1063  nedges = graph->edges;
1064 
1065  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
1066  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree, nedges));
1067 
1068  for( int i = 0; i < nedges; i++ )
1069  steinertree[i] = UNKNOWN;
1070 
1071  for( int i = 0; i < nnodes; i++ )
1072  steinertree_nodes[i] = FALSE;
1073 
1074  steinertree_nodes[0] = TRUE;
1075  steinertree_nodes[1] = TRUE;
1076  steinertree_nodes[2] = TRUE;
1077  steinertree_nodes[3] = TRUE;
1078  steinertree_nodes[4] = TRUE;
1079 
1080  SCIP_CALL( solstp_prune(scip, graph, steinertree, steinertree_nodes) );
1081 
1082  cost0 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
1083 
1084  /* actual test */
1085  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, steinertree) );
1086 
1087  cost1 = solstp_getObjBounded(graph, steinertree, 0.0, nedges);
1088 
1089  if( !SCIPisEQ(scip, cost1 + 0.75, cost0) )
1090  {
1091  printf("localInsertion2pc unit test failed \n");
1092  printf("obj: new=%f, old=%f \n", cost1, cost0);
1093 
1094  return SCIP_ERROR;
1095  }
1096 
1097  graph_path_exit(scip, graph);
1098  graph_free(scip, &graph, TRUE);
1099 
1100  SCIPfreeMemoryArray(scip, &steinertree);
1101  SCIPfreeMemoryArray(scip, &steinertree_nodes);
1102 
1103  return SCIP_OKAY;
1104 }
1105 
1106 
1107 /** test local search heuristics */
1108 SCIP_RETCODE stptest_testHeurLocal(
1109  SCIP* scip /**< SCIP data structure */
1110 )
1111 {
1112  SCIP_CALL( localInsertion(scip) );
1113  SCIP_CALL( localInsertion2(scip) );
1114  SCIP_CALL( localInsertion2pc(scip) );
1115  SCIP_CALL( localKeyPathExchangeMw(scip) );
1116  SCIP_CALL( localKeyVertexPc2(scip) );
1117  SCIP_CALL( localKeyVertex(scip) );
1118  SCIP_CALL( localKeyVertexPc(scip) );
1119  SCIP_CALL( localKeyPathExchangePc2(scip) );
1120  SCIP_CALL( localKeyPathExchangePc(scip) );
1121  SCIP_CALL( localKeyPathExchange(scip) );
1122 
1123  SCIP_CALL( localExtendPc(scip) );
1124 
1125  printf("stptest_heur_local: all ok \n");
1126 
1127  return SCIP_OKAY;
1128 }
localKeyVertexPc
static SCIP_RETCODE localKeyVertexPc(SCIP *scip)
Definition: stptest_heurlocal.c:500
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
localInsertion
static SCIP_RETCODE localInsertion(SCIP *scip)
Definition: stptest_heurlocal.c:840
GRAPH::source
int source
Definition: graphdefs.h:195
SCIPfreeMemoryArray
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIPallocMemoryArray
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
graph_mark
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
solstp.h
includes methods for Steiner tree problem solutions
graph_free
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
graph_path_init
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
FALSE
#define FALSE
Definition: def.h:87
TRUE
#define TRUE
Definition: def.h:86
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
graph.h
includes various files containing graph methods used for Steiner tree problems
localKeyPathExchangePc
static SCIP_RETCODE localKeyPathExchangePc(SCIP *scip)
Definition: stptest_heurlocal.c:105
STP_SPG
#define STP_SPG
Definition: graphdefs.h:42
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
localKeyVertexPc2
static SCIP_RETCODE localKeyVertexPc2(SCIP *scip)
Definition: stptest_heurlocal.c:610
graph_pc_initPrizes
SCIP_RETCODE graph_pc_initPrizes(SCIP *, GRAPH *, int)
Definition: graph_pcbase.c:741
localExtendPc
static SCIP_RETCODE localExtendPc(SCIP *scip)
Definition: stptest_heurlocal.c:729
graph_transMw
SCIP_RETCODE graph_transMw(SCIP *, GRAPH *)
Definition: graph_trans.c:632
localKeyVertex
static SCIP_RETCODE localKeyVertex(SCIP *scip)
Definition: stptest_heurlocal.c:409
GRAPH::stp_type
int stp_type
Definition: graphdefs.h:264
graph_transPc
SCIP_RETCODE graph_transPc(SCIP *, GRAPH *)
Definition: graph_trans.c:154
GRAPH::prize
SCIP_Real * prize
Definition: graphdefs.h:210
graph_initHistory
SCIP_RETCODE graph_initHistory(SCIP *, GRAPH *)
Definition: graph_base.c:695
graph_edge_add
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
graph_knot_add
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
SCIPStpHeurLocalRun
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
SCIP_OKAY
Definition: type_retcode.h:33
GRAPH::knots
int knots
Definition: graphdefs.h:190
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:384
heur_local.h
Improvement heuristic for Steiner problems.
STP_Bool
unsigned char STP_Bool
Definition: portab.h:34
SCIP_ERROR
Definition: type_retcode.h:34
solstp_getObjBounded
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
localKeyPathExchange
static SCIP_RETCODE localKeyPathExchange(SCIP *scip)
Definition: stptest_heurlocal.c:39
localKeyPathExchangePc2
static SCIP_RETCODE localKeyPathExchangePc2(SCIP *scip)
Definition: stptest_heurlocal.c:202
stptest_testHeurLocal
SCIP_RETCODE stptest_testHeurLocal(SCIP *scip)
Definition: stptest_heurlocal.c:1108
graph_path_exit
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
CONNECT
#define CONNECT
Definition: graphdefs.h:87
stptest.h
includes various testing methods for Steiner tree problems
GRAPH::cost
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Real
#define SCIP_Real
Definition: def.h:177
localInsertion2
static SCIP_RETCODE localInsertion2(SCIP *scip)
Definition: stptest_heurlocal.c:917
heur_tm.h
shortest paths based primal heuristics for Steiner problems
GRAPH::edges
int edges
Definition: graphdefs.h:219
SCIPStpHeurLocalExtendPcMw
SCIP_RETCODE SCIPStpHeurLocalExtendPcMw(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, int *stedge, STP_Bool *stvertex)
Definition: heur_local.c:3991
UNKNOWN
#define UNKNOWN
Definition: sepa_mcf.c:4095
nnodes
#define nnodes
Definition: gastrans.c:65
graph_init
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
solstp_isValid
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
solstp_prune
SCIP_RETCODE solstp_prune(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:1366
localKeyPathExchangeMw
static SCIP_RETCODE localKeyPathExchangeMw(SCIP *scip)
Definition: stptest_heurlocal.c:309
localInsertion2pc
static SCIP_RETCODE localInsertion2pc(SCIP *scip)
Definition: stptest_heurlocal.c:999