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