Scippy

SCIP

Solving Constraint Integer Programs

stptest_heurtm.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_heurtm.c
17  * @brief tests for Steiner tree TM (shortest path based) heuristics
18  * @author Daniel Rehfeldt
19  *
20  * This file implements tests for Steiner problem TM (shortest path based) 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_tm.h"
34 #include "portab.h"
35 
36 
37 /** runs TM heuristic */
38 static
39 SCIP_RETCODE runTmPcFull(
40  SCIP* scip, /**< SCIP data structure */
41  GRAPH* graph, /**< graph data structure */
42  int* steinertree_edges /**< the tree */
43 )
44 {
45  SCIP_Bool success;
46 
47  SCIP_CALL( SCIPStpHeurTMRun(scip, pcmode_fulltree,
48  graph, NULL, NULL, steinertree_edges, graph->terms - 1, 2, graph->cost, graph->cost, NULL, NULL, &success) );
49 
50  STPTEST_ASSERT(success);
51 
52  return SCIP_OKAY;
53 }
54 
55 
56 /** tests that PC solution is as expected */
57 static
58 SCIP_RETCODE testTmGivesExpectedTreePcFull1(
59  SCIP* scip /**< SCIP data structure */
60 )
61 {
62  GRAPH* graph;
63  int* steinertree_edges;
64  const int nnodes_org = 5;
65  const int nedges_org = 8;
66  int nnodes = -1;
67  int nedges = -1;
68  const SCIP_Real cost_expected = 3.9;
69  SCIP_Real cost_tmfull;
70  SCIP_Real offset;
71 
72  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
73 
74  for( int i = 0; i < nnodes_org; i++ )
75  graph_knot_add(graph, STP_TERM);
76 
77  graph->source = 0;
78 
79  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0,1
80  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2,3
81  graph_edge_addBi(scip, graph, 2, 3, 1.0);
82  graph_edge_addBi(scip, graph, 2, 4, 1.0);
83 
84  graph_pc_initPrizes(scip, graph, nnodes_org);
85  graph->prize[0] = 2.0; /* the pseudo root */
86  graph->prize[1] = 1.0;
87  graph->prize[2] = 1.0;
88  graph->prize[3] = 0.9;
89  graph->prize[4] = 1.0;
90 
91  SCIP_CALL( stptest_graphSetUpPcExtended(scip, graph, &nnodes, &nedges) );
92 
93  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_edges, nedges));
94 
95  /* actual test */
96  SCIP_CALL( runTmPcFull(scip, graph, steinertree_edges) );
97 
98  offset = graph_pc_getNonLeafTermOffset(scip, graph);
99  cost_tmfull = solstp_getObjBounded(graph, steinertree_edges, offset, nedges);
100 
101  STPTEST_ASSERT_MSG_ARGS(EQ(cost_tmfull, cost_expected), "wrong cost: expected=%f, real=%f \n", cost_expected, cost_tmfull);
102 
103  stptest_graphTearDown(scip, graph);
104 
105  SCIPfreeMemoryArray(scip, &steinertree_edges);
106 
107  return SCIP_OKAY;
108 }
109 
110 
111 /** tests that PC solution is as expected */
112 static
113 SCIP_RETCODE testTmGivesExpectedTreePcFull2(
114  SCIP* scip /**< SCIP data structure */
115 )
116 {
117  GRAPH* graph;
118  int* steinertree_edges;
119  const int nnodes_org = 5;
120  const int nedges_org = 12;
121  int nnodes = -1;
122  int nedges = -1;
123  const SCIP_Real cost_expected = 1.8;
124  SCIP_Real cost_tmfull;
125  SCIP_Real offset;
126 
127  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
128 
129  for( int i = 0; i < nnodes_org; i++ )
130  graph_knot_add(graph, STP_TERM);
131 
132  graph->source = 1;
133 
134  graph_knot_chg(graph, 0, STP_TERM_NONE);
135 
136  graph_edge_addBi(scip, graph, 0, 1, 0.6);
137  graph_edge_addBi(scip, graph, 0, 2, 0.6);
138  graph_edge_addBi(scip, graph, 0, 3, 0.6);
139  graph_edge_addBi(scip, graph, 0, 4, 0.6);
140  graph_edge_addBi(scip, graph, 1, 2, 0.3);
141  graph_edge_addBi(scip, graph, 3, 4, 0.3);
142 
143  graph_pc_initPrizes(scip, graph, nnodes_org);
144  graph->prize[0] = 0.0;
145  graph->prize[1] = 1.0;
146  graph->prize[2] = 1.0;
147  graph->prize[3] = 1.0;
148  graph->prize[4] = 1.0;
149 
150  SCIP_CALL( stptest_graphSetUpPcExtended(scip, graph, &nnodes, &nedges) );
151 
152  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_edges, nedges));
153 
154  /* actual test */
155  SCIP_CALL( runTmPcFull(scip, graph, steinertree_edges) );
156 
157  offset = graph_pc_getNonLeafTermOffset(scip, graph);
158  cost_tmfull = solstp_getObjBounded(graph, steinertree_edges, offset, nedges);
159 
160  STPTEST_ASSERT_MSG_ARGS(EQ(cost_tmfull, cost_expected), "wrong cost: expected=%f, real=%f \n", cost_expected, cost_tmfull);
161 
162  stptest_graphTearDown(scip, graph);
163 
164  SCIPfreeMemoryArray(scip, &steinertree_edges);
165 
166  return SCIP_OKAY;
167 }
168 
169 
170 
171 /** tests that PC solution is as expected */
172 static
173 SCIP_RETCODE testTmGivesExpectedTreePcFull3(
174  SCIP* scip /**< SCIP data structure */
175 )
176 {
177  GRAPH* graph;
178  int* steinertree_edges;
179  const int nnodes_org = 8;
180  const int nedges_org = 16;
181  int nnodes = -1;
182  int nedges = -1;
183  const SCIP_Real cost_expected = 6.7;
184  SCIP_Real cost_tmfull;
185  SCIP_Real offset;
186 
187  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
188 
189  for( int i = 0; i < nnodes_org; i++ )
190  graph_knot_add(graph, STP_TERM);
191 
192  graph->source = 1;
193 
194  graph_knot_chg(graph, 3, STP_TERM_NONE);
195 
196  graph_edge_addBi(scip, graph, 0, 1, 1.1);
197  graph_edge_addBi(scip, graph, 1, 2, 1.0);
198  graph_edge_addBi(scip, graph, 2, 3, 1.0);
199  graph_edge_addBi(scip, graph, 2, 5, 1.0);
200  graph_edge_addBi(scip, graph, 3, 4, 1.0);
201  graph_edge_addBi(scip, graph, 5, 6, 1.0);
202  graph_edge_addBi(scip, graph, 6, 7, 1.1);
203  graph_edge_addBi(scip, graph, 4, 7, 2.3);
204 
205  graph_pc_initPrizes(scip, graph, nnodes_org);
206  graph->prize[0] = 2.0;
207  graph->prize[1] = 2.0;
208  graph->prize[2] = 0.1;
209  graph->prize[3] = 0.0;
210  graph->prize[4] = 1.5;
211  graph->prize[5] = 0.1;
212  graph->prize[6] = 2.0;
213  graph->prize[7] = 2.0;
214 
215  SCIP_CALL( stptest_graphSetUpPcExtended(scip, graph, &nnodes, &nedges) );
216 
217  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_edges, nedges));
218 
219  /* actual test */
220  SCIP_CALL( runTmPcFull(scip, graph, steinertree_edges) );
221 
222  offset = graph_pc_getNonLeafTermOffset(scip, graph);
223  cost_tmfull = solstp_getObjBounded(graph, steinertree_edges, offset, nedges);
224 
225  STPTEST_ASSERT_MSG_ARGS(EQ(cost_tmfull, cost_expected), "wrong cost: expected=%f, real=%f \n", cost_expected, cost_tmfull);
226 
227  stptest_graphTearDown(scip, graph);
228 
229  SCIPfreeMemoryArray(scip, &steinertree_edges);
230 
231  return SCIP_OKAY;
232 }
233 
234 
235 /** tests that PC solution is improved by pruning */
236 static
237 SCIP_RETCODE testPrunedSolIsImprovedPc1(
238  SCIP* scip /**< SCIP data structure */
239 )
240 {
241  GRAPH* graph;
242  int* steinertree_edges;
243  STP_Bool* steinertree_nodes;
244  const int nnodes_org = 5;
245  const int nedges_org = 8;
246  int nnodes = -1;
247  int nedges = -1;
248  const SCIP_Real cost_expected = 3.9;
249  SCIP_Real cost_pruned;
250  SCIP_Real offset;
251 
252  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
253 
254  for( int i = 0; i < nnodes_org; i++ )
255  graph_knot_add(graph, STP_TERM);
256 
257  graph->source = 0;
258 
259  graph_edge_addBi(scip, graph, 0, 1, 1.0); // 0,1
260  graph_edge_addBi(scip, graph, 0, 2, 1.0); // 2,3
261  graph_edge_addBi(scip, graph, 2, 3, 1.0);
262  graph_edge_addBi(scip, graph, 2, 4, 1.0);
263 
264  graph_pc_initPrizes(scip, graph, nnodes_org);
265  graph->prize[0] = 2.0; /* the pseudo root */
266  graph->prize[1] = 1.0;
267  graph->prize[2] = 1.0;
268  graph->prize[3] = 0.9;
269  graph->prize[4] = 1.0;
270 
271  SCIP_CALL( stptest_graphSetUpPcExtended(scip, graph, &nnodes, &nedges) );
272 
273  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
274  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_edges, nedges));
275 
276  for( int i = 0; i < nnodes; i++ )
277  steinertree_nodes[i] = TRUE;
278 
279  /* actual test */
280  SCIP_CALL( solstp_prune(scip, graph, steinertree_edges, steinertree_nodes) );
281 
282  offset = graph_pc_getNonLeafTermOffset(scip, graph);
283  cost_pruned = solstp_getObjBounded(graph, steinertree_edges, offset, nedges);
284 
285  STPTEST_ASSERT_MSG_ARGS(EQ(cost_pruned, cost_expected), "wrong cost: expected=%f, real=%f \n", cost_expected, cost_pruned);
286 
287  stptest_graphTearDown(scip, graph);
288 
289  SCIPfreeMemoryArray(scip, &steinertree_edges);
290  SCIPfreeMemoryArray(scip, &steinertree_nodes);
291 
292  return SCIP_OKAY;
293 }
294 
295 
296 
297 /** tests that PC solution is improved by pruning */
298 static
299 SCIP_RETCODE testPrunedSolIsImprovedPc2(
300  SCIP* scip /**< SCIP data structure */
301 )
302 {
303  GRAPH* graph;
304  int* steinertree_edges;
305  STP_Bool* steinertree_nodes;
306  const int nnodes_org = 5;
307  const int nedges_org = 8;
308  int nnodes = -1;
309  int nedges = -1;
310  const SCIP_Real cost_expected = 4.2;
311  SCIP_Real cost_pruned;
312  SCIP_Real offset;
313 
314  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
315 
316  for( int i = 0; i < nnodes_org; i++ )
317  graph_knot_add(graph, STP_TERM);
318 
319  graph->source = 0;
320 
321  graph_edge_addBi(scip, graph, 4, 1, 1.0);
322  graph_edge_addBi(scip, graph, 4, 2, 1.3);
323  graph_edge_addBi(scip, graph, 2, 3, 1.0);
324  graph_edge_addBi(scip, graph, 2, 0, 1.0);
325 
326  graph_pc_initPrizes(scip, graph, nnodes_org);
327  graph->prize[0] = 1.1;
328  graph->prize[1] = 1.0;
329  graph->prize[2] = 1.0;
330  graph->prize[3] = 1.1;
331  graph->prize[4] = 2.0; /* the pseudo-root */
332 
333  SCIP_CALL( stptest_graphSetUpPcExtended(scip, graph, &nnodes, &nedges) );
334 
335  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
336  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_edges, nedges));
337 
338  for( int i = 0; i < nnodes; i++ )
339  steinertree_nodes[i] = FALSE;
340 
341  for( int i = 0; i < nnodes_org; i++ )
342  steinertree_nodes[i] = TRUE;
343 
344  /* actual test */
345  SCIP_CALL( solstp_prune(scip, graph, steinertree_edges, steinertree_nodes) );
346 
347  offset = graph_pc_getNonLeafTermOffset(scip, graph);
348  cost_pruned = solstp_getObjBounded(graph, steinertree_edges, offset, nedges);
349 
350  STPTEST_ASSERT_MSG_ARGS(EQ(cost_pruned, cost_expected), "wrong cost: expected=%f, real=%f \n", cost_expected, cost_pruned);
351 
352  stptest_graphTearDown(scip, graph);
353 
354  SCIPfreeMemoryArray(scip, &steinertree_edges);
355  SCIPfreeMemoryArray(scip, &steinertree_nodes);
356 
357  return SCIP_OKAY;
358 }
359 
360 
361 
362 #if 0
363 /** tests that RMW solution is improved by pruning */
364 static
365 SCIP_RETCODE testPrunedSolIsImprovedRmw1(
366  SCIP* scip /**< SCIP data structure */
367 )
368 {
369  GRAPH* graph;
370  int* steinertree_edges;
371  STP_Bool* steinertree_nodes;
372  const int nnodes_org = 5;
373  const int nedges_org = 8;
374  int nnodes = -1;
375  int nedges = -1;
376  const SCIP_Real cost_expected = 3.8;
377  SCIP_Real cost_pruned;
378 
379  SCIP_CALL( graph_init(scip, &graph, nnodes_org, nedges_org, 1) );
380 
381  for( int i = 0; i < nnodes_org; i++ )
382  graph_knot_add(graph, STP_TERM);
383 
384  graph->source = 0;
385 
386  graph_edge_addBi(scip, graph, 0, 1, 0.0); // 0,1
387  graph_edge_addBi(scip, graph, 0, 2, 0.0); // 2,3
388  graph_edge_addBi(scip, graph, 2, 3, 0.0);
389  graph_edge_addBi(scip, graph, 2, 4, 0.0);
390 
391  graph_pc_initPrizes(scip, graph, nnodes_org);
392  graph->prize[0] = FARAWAY; /* the root */
393  graph->prize[1] = 1.0;
394  graph->prize[2] = 1.0;
395  graph->prize[3] = 0.8;
396  graph->prize[4] = 1.1;
397 
398  SCIP_CALL( stptest_graphSetUpRmwExtended(scip, graph, &nnodes, &nedges) );
399 
400  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_nodes, nnodes));
401  SCIP_CALL(SCIPallocMemoryArray(scip, &steinertree_edges, nedges));
402 
403  for( int i = 0; i < nnodes; i++ )
404  steinertree_nodes[i] = TRUE;
405 
406  /* actual test */
407  SCIP_CALL( solstp_prune(scip, graph, steinertree_edges, steinertree_nodes) );
408 
409  cost_pruned = solstp_getObjBounded(graph, steinertree_edges, 0.0, nedges);
410 
411  STPTEST_ASSERT_MSG_ARGS(EQ(cost_pruned, cost_expected), "wrong cost: expected=%f, real=%f \n", cost_expected, cost_pruned);
412 
413  stptest_graphTearDown(scip, graph);
414 
415  SCIPfreeMemoryArray(scip, &steinertree_edges);
416  SCIPfreeMemoryArray(scip, &steinertree_nodes);
417 
418  return SCIP_OKAY;
419 }
420 #endif
421 
422 /** test pruning of solution */
423 SCIP_RETCODE stptest_testSolPrune(
424  SCIP* scip /**< SCIP data structure */
425 )
426 {
427  assert(scip);
428  // SCIP_CALL(testPrunedSolIsImprovedRmw1(scip));
429  SCIP_CALL(testPrunedSolIsImprovedPc2(scip));
430  SCIP_CALL(testPrunedSolIsImprovedPc1(scip));
431 
432  return SCIP_OKAY;
433 }
434 
435 
436 /** tests TM heuristic */
437 SCIP_RETCODE stptest_testHeurTm(
438  SCIP* scip /**< SCIP data structure */
439 )
440 {
441  assert(scip);
442 
443  SCIP_CALL(testTmGivesExpectedTreePcFull3(scip));
444  SCIP_CALL(testTmGivesExpectedTreePcFull2(scip) );
445  SCIP_CALL(testTmGivesExpectedTreePcFull1(scip) );
446 
447  return SCIP_OKAY;
448 }
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
STPTEST_ASSERT
#define STPTEST_ASSERT(cond)
Definition: stptest.h:63
GRAPH::source
int source
Definition: graphdefs.h:195
pcmode_fulltree
Definition: heur_tm.h:48
SCIPfreeMemoryArray
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
graph_edge_addBi
void graph_edge_addBi(SCIP *, GRAPH *, int, int, double)
GRAPH::terms
int terms
Definition: graphdefs.h:192
stptest_graphSetUpRmwExtended
SCIP_RETCODE stptest_graphSetUpRmwExtended(SCIP *, GRAPH *, int *, int *)
Definition: stptest_graph.c:351
SCIPallocMemoryArray
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
solstp.h
includes methods for Steiner tree problem solutions
SCIPStpHeurTMRun
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, enum PCMW_TmMode pcmw_tmmode, GRAPH *graph, int *starts, const SCIP_Real *prize, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Bool *success)
Definition: heur_tm.c:3418
testTmGivesExpectedTreePcFull3
static SCIP_RETCODE testTmGivesExpectedTreePcFull3(SCIP *scip)
Definition: stptest_heurtm.c:173
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
runTmPcFull
static SCIP_RETCODE runTmPcFull(SCIP *scip, GRAPH *graph, int *steinertree_edges)
Definition: stptest_heurtm.c:39
FARAWAY
#define FARAWAY
Definition: graphdefs.h:89
graph_pc_getNonLeafTermOffset
SCIP_Real graph_pc_getNonLeafTermOffset(SCIP *, const GRAPH *)
Definition: graph_pcbase.c:2209
testPrunedSolIsImprovedPc2
static SCIP_RETCODE testPrunedSolIsImprovedPc2(SCIP *scip)
Definition: stptest_heurtm.c:299
STP_TERM_NONE
#define STP_TERM_NONE
Definition: graphdefs.h:62
graph_pc_initPrizes
SCIP_RETCODE graph_pc_initPrizes(SCIP *, GRAPH *, int)
Definition: graph_pcbase.c:741
GRAPH::prize
SCIP_Real * prize
Definition: graphdefs.h:210
graph_knot_add
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
NULL
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_OKAY
Definition: type_retcode.h:33
EQ
#define EQ(a, b)
Definition: portab.h:79
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:384
testTmGivesExpectedTreePcFull2
static SCIP_RETCODE testTmGivesExpectedTreePcFull2(SCIP *scip)
Definition: stptest_heurtm.c:113
STP_Bool
unsigned char STP_Bool
Definition: portab.h:34
stptest_graphTearDown
void stptest_graphTearDown(SCIP *, GRAPH *)
Definition: stptest_graph.c:274
solstp_getObjBounded
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
SCIP_Bool
#define SCIP_Bool
Definition: def.h:84
STP_TERM
#define STP_TERM
Definition: graphdefs.h:61
testTmGivesExpectedTreePcFull1
static SCIP_RETCODE testTmGivesExpectedTreePcFull1(SCIP *scip)
Definition: stptest_heurtm.c:58
portab.h
Portable definitions.
stptest_testHeurTm
SCIP_RETCODE stptest_testHeurTm(SCIP *scip)
Definition: stptest_heurtm.c:437
testPrunedSolIsImprovedPc1
static SCIP_RETCODE testPrunedSolIsImprovedPc1(SCIP *scip)
Definition: stptest_heurtm.c:237
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
STPTEST_ASSERT_MSG_ARGS
#define STPTEST_ASSERT_MSG_ARGS(cond, msg,...)
Definition: stptest.h:39
heur_tm.h
shortest paths based primal heuristics for Steiner problems
nnodes
#define nnodes
Definition: gastrans.c:65
graph_init
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
stptest_testSolPrune
SCIP_RETCODE stptest_testSolPrune(SCIP *scip)
Definition: stptest_heurtm.c:423
stptest_graphSetUpPcExtended
SCIP_RETCODE stptest_graphSetUpPcExtended(SCIP *, GRAPH *, int *, int *)
Definition: stptest_graph.c:375
solstp_prune
SCIP_RETCODE solstp_prune(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:1366