1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 heuristic.c
17 * @brief unit test for testing packing heuristic
18 * @author Benjamin Mueller
19 */
20
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22
23 #include "scip/scip.h"
24
25 #include "probdata_rpa.h"
26
27 #include "include/scip_test.h"
28
29 static SCIP* scip;
30
31 /** setup of test run */
32 static
setup(void)33 void setup(void)
34 {
35 /* initialize SCIP */
36 SCIP_CALL( SCIPcreate(&scip) );
37 }
38
39 /** deinitialization method */
40 static
teardown(void)41 void teardown(void)
42 {
43 /* free SCIP */
44 SCIP_CALL( SCIPfree(&scip) );
45
46 cr_assert_null(scip);
47 cr_assert_eq(BMSgetMemoryUsed(), 0, "There is a memory leak!!");
48 }
49
50 /* test suite */
51 TestSuite(heuristic, .init = setup, .fini = teardown);
52
53 /* tests heuristic for a single circle */
Test(heuristic,single)54 Test(heuristic, single)
55 {
56 SCIP_Real rext = 1.0;
57 SCIP_Bool ispacked;
58 SCIP_Real x;
59 SCIP_Real y;
60 int elements = 0;
61 int npacked;
62
63 /* pack element into rectangle */
64 SCIPpackCirclesGreedy(scip, &rext, &x, &y, -1.0, 2.0, 2.0, &ispacked, &elements, 1,
65 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
66 cr_expect(npacked == 1);
67 cr_expect(ispacked);
68 cr_expect(x == 1.0);
69 cr_expect(y == 1.0);
70
71 /* pack element into ring */
72 SCIPpackCirclesGreedy(scip, &rext, &x, &y, 2.0, -1.0, -1.0, &ispacked, &elements, 1,
73 SCIP_PATTERNTYPE_CIRCULAR, &npacked, 0);
74 cr_expect(npacked == 1);
75 cr_expect(ispacked);
76 cr_expect(x == -1.0);
77 cr_expect(y == 0.0);
78 }
79
80 /* packs two different circle types into a rectangle */
Test(heuristic,rectangle_two_types)81 Test(heuristic, rectangle_two_types)
82 {
83 SCIP_Real rexts[2] = {3.0, 0.45};
84 SCIP_Real xs[5];
85 SCIP_Real ys[5];
86 SCIP_Bool ispacked[5];
87 int elements[5] = {0, 1, 1, 1, 1};
88 int npacked;
89 int k;
90
91 SCIPpackCirclesGreedy(scip, rexts, xs, ys, -1.0, 6.0, 6.0, ispacked, elements, 5,
92 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
93 cr_expect(npacked == 5);
94
95 for( k = 0; k < 5; ++k )
96 cr_expect(ispacked[k]);
97 }
98
99 /* test optimal packing with two identical circles */
Test(heuristic,opt_two)100 Test(heuristic, opt_two)
101 {
102 SCIP_Real rext = 1.0;
103 SCIP_Real xs[2];
104 SCIP_Real ys[2];
105 SCIP_Bool ispacked[2];
106 int elements[2] = {0, 0};
107 int npacked;
108
109 /* pack into a ring */
110 SCIPpackCirclesGreedy(scip, &rext, xs, ys, 2.0, -1.0, -1.0, ispacked, elements, 2,
111 SCIP_PATTERNTYPE_CIRCULAR, &npacked, 0);
112 cr_expect(npacked == 2);
113
114 /* pack into a square */
115 SCIPpackCirclesGreedy(scip, &rext, xs, ys, -1.0, 3.414213562373095, 3.414213562373095, ispacked, elements, 2,
116 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
117 cr_expect(npacked == 2);
118 }
119
120 /* test optimal packing with three identical circles */
Test(heuristic,opt_three)121 Test(heuristic, opt_three)
122 {
123 SCIP_Real rext = 1.0;
124 SCIP_Real xs[3];
125 SCIP_Real ys[3];
126 SCIP_Bool ispacked[3];
127 int elements[3] = {0, 0, 0};
128 int npacked;
129
130 /* pack into a ring */
131 SCIPpackCirclesGreedy(scip, &rext, xs, ys, 2.1547005383792515, -1.0, -1.0, ispacked, elements, 3,
132 SCIP_PATTERNTYPE_CIRCULAR, &npacked, 0);
133 cr_expect(npacked == 3);
134
135 /* pack into a square */
136 SCIPpackCirclesGreedy(scip, &rext, xs, ys, -1.0, 3.9318516525781364, 3.9318516525781364, ispacked, elements, 3,
137 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
138 cr_expect(npacked == 3);
139 }
140
141 /* test optimal packing with four identical circles */
Test(heuristic,opt_four)142 Test(heuristic, opt_four)
143 {
144 SCIP_Real rext = 1.0;
145 SCIP_Real xs[4];
146 SCIP_Real ys[4];
147 SCIP_Bool ispacked[4];
148 int elements[4] = {0, 0, 0, 0};
149 int npacked;
150
151 /* pack into a ring */
152 SCIPpackCirclesGreedy(scip, &rext, xs, ys, 2.414213562373095, -1.0, -1.0, ispacked, elements, 4,
153 SCIP_PATTERNTYPE_CIRCULAR, &npacked, 0);
154 cr_expect(npacked == 4);
155
156 /* pack into a square */
157 SCIPpackCirclesGreedy(scip, &rext, xs, ys, -1.0, 4.0, 4.0, ispacked, elements, 4,
158 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
159 cr_expect(npacked >= 3); /* note that greedy fails for this example */
160 }
161
162 /* test optimal packing with five identical circles */
Test(heuristic,opt_five)163 Test(heuristic, opt_five)
164 {
165 SCIP_Real rext = 1.0;
166 SCIP_Real xs[5];
167 SCIP_Real ys[5];
168 SCIP_Bool ispacked[5];
169 int elements[5] = {0, 0, 0, 0, 0};
170 int npacked;
171
172 /* pack into a ring */
173 SCIPpackCirclesGreedy(scip, &rext, xs, ys, 2.7013016167040798, -1.0, -1.0, ispacked, elements, 5,
174 SCIP_PATTERNTYPE_CIRCULAR, &npacked, 0);
175 cr_expect(npacked >= 4); /* note that the greedy packing fails for the case of 5 circles */
176
177 /* pack into a square */
178 SCIPpackCirclesGreedy(scip, &rext, xs, ys, -1.0, 4.82842712474619, 4.82842712474619, ispacked, elements, 5,
179 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
180 cr_expect(npacked >= 4); /* note that greedy fails for this example */
181 }
182
183 /* test optimal packing with fix identical circles */
Test(heuristic,opt_six)184 Test(heuristic, opt_six)
185 {
186 SCIP_Real rext = 1.0;
187 SCIP_Real xs[6];
188 SCIP_Real ys[6];
189 SCIP_Bool ispacked[6];
190 int elements[6] = {0, 0, 0, 0, 0, 0};
191 int npacked;
192
193 /* pack into a ring */
194 SCIPpackCirclesGreedy(scip, &rext, xs, ys, 3.0, -1.0, -1.0, ispacked, elements, 6,
195 SCIP_PATTERNTYPE_CIRCULAR, &npacked, 0);
196 cr_expect(npacked == 6);
197
198 /* pack into a square */
199 SCIPpackCirclesGreedy(scip, &rext, xs, ys, -1.0, 5.328201177351374, 5.328201177351374, ispacked, elements, 6,
200 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
201 cr_expect(npacked >= 5); /* note that greedy fails for this example */
202 }
203
204 /* test optimal packing with seven identical circles */
Test(heuristic,opt_seven)205 Test(heuristic, opt_seven)
206 {
207 SCIP_Real rext = 1.0;
208 SCIP_Real xs[7];
209 SCIP_Real ys[7];
210 SCIP_Bool ispacked[7];
211 int elements[7] = {0, 0, 0, 0, 0, 0, 0};
212 int npacked;
213
214 /* pack into a ring */
215 SCIPpackCirclesGreedy(scip, &rext, xs, ys, 3.0, -1.0, -1.0, ispacked, elements, 7,
216 SCIP_PATTERNTYPE_CIRCULAR, &npacked, 0);
217 cr_expect(npacked == 7);
218
219 /* pack into a square */
220 SCIPpackCirclesGreedy(scip, &rext, xs, ys, -1.0, 5.732050807568877, 5.732050807568877, ispacked, elements, 7,
221 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
222 cr_expect(npacked >= 6); /* note that greedy fails for this example */
223 }
224
225 /* test optimal packing with seven identical circles */
Test(heuristic,opt_twenty)226 Test(heuristic, opt_twenty)
227 {
228 SCIP_Real rext = 1.0;
229 SCIP_Real xs[20];
230 SCIP_Real ys[20];
231 SCIP_Bool ispacked[20];
232 int elements[20] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
233 int npacked;
234
235 /* pack into a ring */
236 SCIPpackCirclesGreedy(scip, &rext, xs, ys, 5.123, -1.0, -1.0, ispacked, elements, 20,
237 SCIP_PATTERNTYPE_CIRCULAR, &npacked, 0);
238 cr_expect(npacked >= 18);
239
240 /* pack into a square */
241 SCIPpackCirclesGreedy(scip, &rext, xs, ys, -1.0, 8.978083352821738, 8.978083352821738, ispacked, elements, 20,
242 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
243 cr_expect(npacked >= 18); /* note that greedy fails for this example */
244 }
245
246 /* tests a more complicated example */
Test(heuristic,complex_1)247 Test(heuristic, complex_1)
248 {
249 SCIP_Real rexts[3] = {2.0, 1.0, 0.3};
250 SCIP_Real xs[24];
251 SCIP_Real ys[24];
252 SCIP_Bool ispacked[24];
253 int elements[24] = {0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2};
254 int npacked;
255
256 /* pack into a ring */
257 SCIPpackCirclesGreedy(scip, rexts, xs, ys, 4.0, -1.0, -1.0, ispacked, elements, 24,
258 SCIP_PATTERNTYPE_CIRCULAR, &npacked, 0);
259 cr_expect(npacked >= 24);
260
261 /* pack into a square */
262 SCIPpackCirclesGreedy(scip, rexts, xs, ys, -1.0, 7.7, 7.7, ispacked, elements, 24,
263 SCIP_PATTERNTYPE_RECTANGULAR, &npacked, 0);
264 cr_expect(npacked >= 24);
265 }
266