Scippy

SCIP

Solving Constraint Integer Programs

probdata_rpa.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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file probdata_rpa.c
26  * @brief Problem data for ringpacking problem
27  * @author Benjamin Mueller
28  *
29  * This file handles the main problem data used in that project. For more details see \ref RINGPACKING_PROBLEMDATA page.
30  *
31  * @page RINGPACKING_PROBLEMDATA Main problem data
32  *
33  * The problem data is accessible in all plugins. The function SCIPgetProbData() returns the pointer to that
34  * structure. We use this data structure to store all the information of the ringpacking problem. Since this structure is
35  * not visible in the other plugins, we implemented setter and getter functions to access most data.
36  *
37  * The function SCIPprobdataCreate(), which is called in the \ref reader_bpa.c "reader plugin" after the input file was
38  * parsed, initializes the problem data structure. Afterwards, the problem is setup in SCIPprobdataSetupProblem. For this,
39  * it enumerates all dominating circular patterns, selects a set of initial rectangular patterns and creates the
40  * corresponding variables and constraints. Note that the pattern constraints have to have the
41  * <code>modifiable</code>-flag set to TRUE. This is necessary to tell the solver that these constraints are not
42  * completed yet. This means, during the search new variables/patterns might be added. The solver needs this information
43  * because certain reductions are not allowed.
44  *
45  * A list of all interface methods can be found in probdata_binpacking.h.
46  */
47 
48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49 
50 #include "scip/scip.h"
51 #include "scip/scipdefplugins.h"
52 #include "probdata_rpa.h"
53 #include "pricer_rpa.h"
54 
55 #include <string.h>
56 #include <math.h>
57 
58 /* properties of the ringpacking statistics table */
59 #define TABLE_NAME_RPA "ringpacking"
60 #define TABLE_DESC_RPA "ringpacking statistics"
61 #define TABLE_POSITION_RPA 12500 /**< the position of the statistics table */
62 #define TABLE_EARLIEST_STAGE_RPA SCIP_STAGE_TRANSFORMED /**< output of the statistics table is only printed from this stage onwards */
63 
64 #ifndef M_PI
65 #define M_PI 3.141592653589793238462643
66 #endif
67 
68 /** @brief Problem data which is accessible in all places
69  *
70  * This problem data is used to store the input of the ringpacking, all variables which are created, and all
71  * constraints.
72  */
73 struct SCIP_ProbData
74 {
75  int* demands; /**< array of demands */
76  SCIP_Real* rints; /**< internal radii of each ring */
77  SCIP_Real* rexts; /**< external radii of each ring */
78  int ntypes; /**< number of different types */
79 
80  SCIP_Real width; /**< height of each rectangle */
81  SCIP_Real height; /**< width of each rectangle */
82 
83  SCIP_CONS** patternconss; /**< pattern constraints for each type */
84 
85  /* circular pattern data */
86  SCIP_PATTERN** cpatterns; /**< array containing all circular patterns */
87  SCIP_VAR** cvars; /**< variables corresponding to circular patterns */
88  int ncpatterns; /**< total number of circular patterns */
89  int cpatternsize; /**< size of cpatterns and cvars array */
90 
91  /* rectangular pattern data */
92  SCIP_PATTERN** rpatterns; /**< array containing all rectangular patterns */
93  SCIP_VAR** rvars; /**< variables corresponding to rectangular patterns */
94  int nrpatterns; /**< total number of rectangular patterns */
95  int rpatternsize; /**< size of rpatterns and rvars array */
96 
97  /* variables for statistics */
98  int ncppatternsunknownbeg;/**< number of unknown circular patterns after enumeration step */
99  SCIP_Real enumtime; /**< time spend for enumerating circular patterns */
100  SCIP_Bool isdualinvalid; /**< whether the following reported dual bounds are valid */
101  SCIP_Real dualbound; /**< valid dual bound for RCPP instance */
102 
103  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
104 
105 
106  /* parameters */
107  SCIP_Real nlptilimsoft; /**< soft time limit for verification NLP */
108  SCIP_Real heurtilimsoft; /**< soft time limit for verification heuristic */
109  SCIP_Real totaltilimsoft; /**< soft time limit for enumerating circular patterns */
110  SCIP_Longint nlpnodelimsoft; /**< soft node limit for verification NLP */
111  int heuriterlimsoft; /**< soft iteration limit for verification heuristic */
112 };
113 
114 
115 /**@name Local methods
116  *
117  * @{
118  */
119 
120 /** auxiliary function to create problem data;
121  *
122  * @note captures patterns and corresponding variables
123  */
124 static
126  SCIP* scip, /**< SCIP data structure */
127  SCIP_PROBDATA** probdata, /**< pointer to problem data */
128  SCIP_CONS** patternconss, /**< pattern constraints */
129  SCIP_PATTERN** cpatterns, /**< circular patterns */
130  SCIP_VAR** cvars, /**< variables corresponding to circular patterns */
131  int ncpatterns, /**< total number of circular patterns */
132  SCIP_PATTERN** rpatterns, /**< rectangular patterns */
133  SCIP_VAR** rvars, /**< variables corresponding to rectangular patterns */
134  int nrpatterns, /**< total number of rectangular patterns */
135  int* demands, /**< array containing the demands */
136  SCIP_Real* rints, /**< interal radii of each ring */
137  SCIP_Real* rexts, /**< external radii of each ring */
138  int ntypes, /**< number of different types */
139  SCIP_Real width, /**< width of each rectangle */
140  SCIP_Real height /**< height of each rectangle */
141  )
142 {
143  int i;
144 
145  assert(probdata != NULL);
146  assert(demands != NULL);
147  assert(rints != NULL);
148  assert(rexts != NULL);
149  assert(ntypes > 0);
150  assert(height > 0.0);
151  assert(width >= height);
152 
153  /* allocate memory */
154  SCIP_CALL( SCIPallocBlockMemory(scip, probdata) );
155  BMSclearMemory(*probdata);
156 
157  if( ncpatterns > 0 )
158  {
159  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->cvars, cvars, ncpatterns) );
160  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->cpatterns, cpatterns, ncpatterns) );
161  (*probdata)->ncpatterns = ncpatterns;
162  (*probdata)->cpatternsize = ncpatterns;
163 
164  /* capture circular patterns */
165  for( i = 0; i < ncpatterns; ++i )
166  SCIPpatternCapture(cpatterns[i]);
167  }
168 
169  if( nrpatterns > 0 )
170  {
171  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->rvars, rvars, nrpatterns) );
172  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->rpatterns, rpatterns, nrpatterns) );
173  (*probdata)->nrpatterns = nrpatterns;
174  (*probdata)->rpatternsize = nrpatterns;
175 
176  /* capture rectangular patterns */
177  for( i = 0; i < nrpatterns; ++i )
178  SCIPpatternCapture(rpatterns[i]);
179  }
180 
181  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->demands, demands, ntypes) );
182  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->rints, rints, ntypes) );
183  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->rexts, rexts, ntypes) );
184 
185  /* copy pattern constraints if available, otherwise allocate enough memory */
186  if( patternconss != NULL )
187  {
188  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*probdata)->patternconss, patternconss, ntypes) );
189  }
190  else
191  {
192  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*probdata)->patternconss, ntypes) );
193  BMSclearMemoryArray((*probdata)->patternconss, ntypes);
194  }
195 
196  /* create random number generator */
197  SCIP_CALL( SCIPcreateRandom(scip, &(*probdata)->randnumgen, 0, TRUE) );
198 
199  (*probdata)->ntypes = ntypes;
200  (*probdata)->width = width;
201  (*probdata)->height = height;
202 
203  return SCIP_OKAY;
204 }
205 
206 /** auxiliary function to free problem data */
207 static
209  SCIP* scip, /**< SCIP data structure */
210  SCIP_PROBDATA** probdata /**< pointer to release the probdata */
211  )
212 {
213  int i;
214 
215  assert(scip != NULL);
216  assert(probdata != NULL);
217  assert(*probdata != NULL);
218 
219  /* free random number generator */
220  if( (*probdata)->randnumgen != NULL )
221  {
222  SCIPfreeRandom(scip, &(*probdata)->randnumgen);
223  }
224 
225  /* release pattern constraints */
226  if( (*probdata)->patternconss != NULL )
227  {
228  for( i = 0; i < SCIPprobdataGetNTypes(*probdata); ++i )
229  {
230  if( (*probdata)->patternconss[i] != NULL )
231  {
232  SCIP_CALL( SCIPreleaseCons(scip, &(*probdata)->patternconss[i]));
233  }
234  }
235  SCIPfreeBlockMemoryArray(scip, &(*probdata)->patternconss, (*probdata)->ntypes);
236  }
237 
238  /* release circular patterns */
239  for( i = 0; i < (*probdata)->ncpatterns; ++i )
240  {
241  assert((*probdata)->cpatterns[i] != NULL);
242 
243  if( (*probdata)->cvars[i] != NULL )
244  {
245  SCIP_CALL( SCIPreleaseVar(scip, &(*probdata)->cvars[i]) );
246  }
247 
248  SCIPpatternRelease(scip, &(*probdata)->cpatterns[i]);
249  }
250 
251  SCIPfreeBlockMemoryArrayNull(scip, &(*probdata)->cpatterns, (*probdata)->cpatternsize);
252  SCIPfreeBlockMemoryArrayNull(scip, &(*probdata)->cvars, (*probdata)->cpatternsize);
253 
254  /* release rectangular patterns */
255  for( i = 0; i < (*probdata)->nrpatterns; ++i )
256  {
257  assert((*probdata)->rpatterns[i] != NULL);
258  assert((*probdata)->rvars[i] != NULL);
259 
260  if( (*probdata)->rvars[i] != NULL )
261  {
262  SCIP_CALL( SCIPreleaseVar(scip, &(*probdata)->rvars[i]) );
263  }
264 
265  SCIPpatternRelease(scip, &(*probdata)->rpatterns[i]);
266  }
267 
268  SCIPfreeBlockMemoryArrayNull(scip, &(*probdata)->rpatterns, (*probdata)->rpatternsize);
269  SCIPfreeBlockMemoryArrayNull(scip, &(*probdata)->rvars, (*probdata)->rpatternsize);
270 
271  SCIPfreeBlockMemoryArray(scip, &(*probdata)->rexts, (*probdata)->ntypes);
272  SCIPfreeBlockMemoryArray(scip, &(*probdata)->rints, (*probdata)->ntypes);
273  SCIPfreeBlockMemoryArray(scip, &(*probdata)->demands, (*probdata)->ntypes);
274 
275  SCIPfreeBlockMemory(scip, probdata);
276  SCIP_CALL( SCIPsetProbData(scip, NULL) );
277 
278  return SCIP_OKAY;
279 }
280 
281 /** counts the number of circular patterns with a given packable status */
282 static
284  SCIP* scip, /**< SCIP data structure */
285  SCIP_PROBDATA* probdata, /**< problem data */
286  SCIP_PACKABLE status /**< packable status */
287  )
288 {
289  int count = 0;
290  int p;
291 
292  assert(probdata != NULL);
293 
294  for( p = 0; p < probdata->ncpatterns; ++p )
295  {
296  if( SCIPpatternGetPackableStatus(probdata->cpatterns[p]) == status )
297  ++count;
298  }
299 
300  return count;
301 }
302 
303 /** ensures a minimum size of the pattern and variable arrays */
304 static
306  SCIP* scip, /**< SCIP data structure */
307  SCIP_PROBDATA* probdata, /**< problem data */
308  SCIP_PATTERNTYPE type, /**< pattern type */
309  int size /**< required size */
310  )
311 {
312  int newsize;
313 
314  assert(probdata != NULL);
315  assert(size > 0);
316 
317  if( type == SCIP_PATTERNTYPE_CIRCULAR && size > probdata->cpatternsize )
318  {
319  newsize = MAX(size, 2 * probdata->cpatternsize);
320 
321  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &probdata->cpatterns, probdata->cpatternsize, newsize) );
322  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &probdata->cvars, probdata->cpatternsize, newsize) );
323  probdata->cpatternsize = newsize;
324  }
325  else if( type == SCIP_PATTERNTYPE_RECTANGULAR && size > probdata->rpatternsize )
326  {
327  newsize = MAX(size, 2 * probdata->rpatternsize);
328 
329  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &probdata->rpatterns, probdata->rpatternsize, newsize) );
330  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &probdata->rvars, probdata->rpatternsize, newsize) );
331  probdata->rpatternsize = newsize;
332  }
333 
334  return SCIP_OKAY;
335 }
336 
337 /** create variables for all existing circular and rectangular patterns */
338 static
340  SCIP* scip, /**< SCIP data structure */
341  SCIP_PROBDATA* probdata /**< problem data */
342  )
343 {
344  SCIP_VAR* var;
345  SCIP_PATTERN* pattern;
346  char name[SCIP_MAXSTRLEN];
347  int k;
348 
349  assert(probdata != NULL);
350  assert(probdata->ncpatterns > 0);
351  assert(probdata->nrpatterns > 0);
352 
353  /* create variables for circular patterns */
354  for( k = 0; k < probdata->ncpatterns; ++k )
355  {
356  SCIP_Real ub;
357  int type;
358  int i;
359 
360  pattern = probdata->cpatterns[k];
361  assert(pattern != NULL);
362 
363  type = SCIPpatternGetCircleType(pattern);
364  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "c%d", type);
365  ub = (SCIP_Real)SCIPprobdataGetDemands(probdata)[type];
366 
367  /* create variable name */
368  for( i = 0; i < SCIPpatternGetNElemens(pattern); ++i )
369  {
370  char strtmp[SCIP_MAXSTRLEN];
371  int elemtype = SCIPpatternGetElementType(pattern, i);
372  (void) SCIPsnprintf(strtmp, SCIP_MAXSTRLEN, "_%d", elemtype);
373  (void) strcat(name, strtmp);
374  }
375 
376  /* create variable */
377  SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, ub, 0.0, SCIP_VARTYPE_INTEGER) );
378  SCIP_CALL( SCIPaddVar(scip, var) );
379 
380  /* store variables in problem data */
381  probdata->cvars[k] = var;
382  }
383 
384  /* create variables for rectangular patterns */
385  for( k = 0; k < probdata->nrpatterns; ++k )
386  {
387  int i;
388 
389  pattern = probdata->rpatterns[k];
390  assert(pattern != NULL);
391 
392  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "r");
393 
394  /* create variable name */
395  for( i = 0; i < SCIPpatternGetNElemens(pattern); ++i )
396  {
397  char strtmp[SCIP_MAXSTRLEN];
398  int elemtype = SCIPpatternGetElementType(pattern, i);
399  (void) SCIPsnprintf(strtmp, SCIP_MAXSTRLEN, "_%d", elemtype);
400  (void) strcat(name, strtmp);
401  }
402 
403  /* create variable */
404  SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, SCIPinfinity(scip), 1.0, SCIP_VARTYPE_INTEGER) );
405  SCIP_CALL( SCIPaddVar(scip, var) );
406 
407  /* store variables in problem data */
408  probdata->rvars[k] = var;
409  }
410 
411  return SCIP_OKAY;
412 }
413 
414 /** upper bound on the number of circles of a single type that fit into a circular pattern of a given type */
415 static
417  SCIP* scip, /**< SCIP data structure */
418  SCIP_PROBDATA* probdata, /**< problem data */
419  int type, /**< type of the circular pattern */
420  int elemtype /**< type of element to pack */
421  )
422 {
423  SCIP_Real _rint;
424  SCIP_Real rext;
425  SCIP_Real rintscaled;
426  int demand;
427  int n;
428 
429  assert(type >= 0 && type < SCIPprobdataGetNTypes(probdata));
430  assert(elemtype >= 0 && elemtype < SCIPprobdataGetNTypes(probdata));
431 
432  _rint = SCIPprobdataGetRints(probdata)[type];
433  rext = SCIPprobdataGetRexts(probdata)[elemtype];
434  demand = SCIPprobdataGetDemands(probdata)[elemtype];
435 
436  /* volume-bsaed bound */
437  n = MIN(demand, (int) SCIPceil(scip, SQR(_rint) / SQR(rext)));
438 
439  if( n <= 1 )
440  return 1;
441 
442  /* use proven bounds on the density */
443  rintscaled = _rint / rext;
444  assert(rintscaled >= 1.0);
445 
446  if( SCIPisLT(scip, rintscaled, 2.0) )
447  return MIN(1, n);
448  else if( SCIPisLT(scip, rintscaled, 2.1547005383792515) )
449  return MIN(2, n);
450  else if( SCIPisLT(scip, rintscaled, 2.414213562373095) )
451  return MIN(3, n);
452  else if( SCIPisLT(scip, rintscaled, 2.7013016167040798) )
453  return MIN(4, n);
454  else if( SCIPisLT(scip, rintscaled, 3.0) )
455  return MIN(5, n);
456  else if( SCIPisLT(scip, rintscaled, 3.3047648709624866) )
457  return MIN(7, n); /* note that here is a jump and 7 is correct */
458  else if( SCIPisLT(scip, rintscaled, 3.613125929752753) )
459  return MIN(8, n);
460 
461  return n;
462 }
463 
464 /** helper function to compare two patterns; returns
465  *
466  * -1 if p dominates q
467  * +1 if q dominates p
468  * 0 otherwise
469  */
470 static
472  SCIP_PATTERN* p, /**< pattern */
473  SCIP_PATTERN* q, /**< pattern */
474  int* count, /**< array for counting elements of patterns */
475  int ntypes /**< total number of types */
476  )
477 {
478  SCIP_Bool pdomq;
479  SCIP_Bool qdomp;
480  int i;
481 
482  /* patterns can only dominate each other if they have the same type */
484  return 0;
485 
486  /* reset count array */
487  BMSclearMemoryArray(count, ntypes);
488 
489  /* increase array entry for each element in p */
490  for( i = 0; i < SCIPpatternGetNElemens(p); ++i )
491  {
492  int t = SCIPpatternGetElementType(p, i);
493  count[t] += 1;
494  }
495 
496  /* decrease array entry for each element in q */
497  for( i = 0; i < SCIPpatternGetNElemens(q); ++i )
498  {
499  int t = SCIPpatternGetElementType(q, i);
500  count[t] -= 1;
501  }
502 
503  pdomq = TRUE;
504  qdomp = TRUE;
505 
506  for( i = 0; i < ntypes && (pdomq || qdomp); ++i )
507  {
508  if( count[i] < 0 )
509  pdomq = FALSE;
510  else if( count[i] > 0 )
511  qdomp = FALSE;
512  }
513 
515  return -1;
517  return 1;
518  return 0;
519 }
520 
521 /** filter dominated patterns */
522 static
524  SCIP* scip, /**< SCIP data structure */
525  SCIP_PROBDATA* probdata /**< problem data */
526  )
527 {
528  SCIP_PATTERN** cpatterns;
529  SCIP_Bool* deleted;
530  int* count;
531  int ncpatterns;
532  int i;
533 
534  SCIP_CALL( SCIPallocBufferArray(scip, &count, SCIPprobdataGetNTypes(probdata)) );
535  SCIP_CALL( SCIPallocBufferArray(scip, &cpatterns, probdata->ncpatterns) );
536  SCIP_CALL( SCIPallocBufferArray(scip, &deleted, probdata->ncpatterns) );
537  BMSclearMemoryArray(deleted, probdata->ncpatterns);
538 
539  for( i = 0; i < probdata->ncpatterns - 1; ++i )
540  {
541  SCIP_PATTERN* p = probdata->cpatterns[i];
542  int j;
543 
544  if( deleted[i] )
545  continue;
546 
547  for( j = i + 1; j < probdata->ncpatterns; ++j )
548  {
549  SCIP_PATTERN* q = probdata->cpatterns[j];
550  int res;
551 
552  if( deleted[j] )
553  continue;
554 
555  res = isPatternDominating(p, q, count, SCIPprobdataGetNTypes(probdata));
556 
557  /* p dominates q */
558  if( res == -1 )
559  deleted[j] = TRUE;
560  else if( res == 1 ) /* q dominates p */
561  deleted[i] = TRUE;
562  }
563  }
564 
565  /* remove filtered patterns */
566  ncpatterns = 0;
567  for( i = 0; i < probdata->ncpatterns; ++i )
568  {
569  if( deleted[i] )
570  {
571  SCIPpatternRelease(scip, &probdata->cpatterns[i]);
572  }
573  else
574  {
575  cpatterns[ncpatterns] = probdata->cpatterns[i];
576  ++ncpatterns;
577  }
578  }
579  assert(ncpatterns > 0);
580 
581  BMScopyMemoryArray(probdata->cpatterns, cpatterns, ncpatterns);
582  probdata->ncpatterns = ncpatterns;
583 
584  /* free memory */
585  SCIPfreeBufferArray(scip, &deleted);
586  SCIPfreeBufferArray(scip, &cpatterns);
587  SCIPfreeBufferArray(scip, &count);
588 
589  return SCIP_OKAY;
590 }
591 
592 /** enumerates all circular patterns for a given type */
593 static
595  SCIP* scip, /**< SCIP data structure */
596  SCIP_PROBDATA* probdata, /**< problem data */
597  SCIP_PATTERN* pattern, /**< pattern (passed for performance reasons) */
598  int* ms, /**< maximum number of elements for each type (passed for performance reasons) */
599  int* nselected, /**< number of selected elements for each type (passed for performance reasons) */
600  SCIP_Real nlptilim, /**< time limit for each NLP verification */
601  SCIP_Real heurtilim, /**< time limit for each call of the heuristics */
602  SCIP_Longint nlpnodelim, /**< node limit for each NLP verification */
603  int heuriterlim, /**< iteration limit for each call of the heuristics */
604  SCIP_Real* timeleft /**< pointer to update the remaining time for the enumeration */
605  )
606 {
607  SCIP_Real* rexts;
608  SCIP_Real* _rints;
609  SCIP_Real maxvolume;
610  SCIP_Real volume;
611  int ntypes;
612  int type;
613  int lasttype;
614 
615  assert(ms != NULL);
616  assert(pattern != NULL);
617  assert(timeleft != NULL);
618 
619  type = SCIPpatternGetCircleType(pattern);
620  assert(type >= 0 && type < SCIPprobdataGetNTypes(probdata));
621 
622  /* get problem data */
623  rexts = SCIPprobdataGetRexts(probdata);
624  _rints = SCIPprobdataGetRints(probdata);
625  ntypes = SCIPprobdataGetNTypes(probdata);
626  lasttype = ntypes -1;
627  volume = 0.0;
628  maxvolume = SQR(_rints[SCIPpatternGetCircleType(pattern)]) * M_PI; /*lint !e666*/
629 
630  /* main loop */
631  while( TRUE )
632  {
633  SCIP_Real timelim;
634  int t = lasttype;
635 
636  /* reset packable status */
638 
639  SCIPdebugMsg(scip, "volume = %g <= %g\n", volume, maxvolume);
640 
641  {
642  int j;
643  SCIPdebugMsg(scip, "verify c%d", type);
644 
645  for( j = 0; j < SCIPpatternGetNElemens(pattern); ++j )
646  SCIPdebugMsgPrint(scip, "_%d", SCIPpatternGetElementType(pattern, j));
647  SCIPdebugMsgPrint(scip, "\n");
648  }
649 
650  /* check volume */
651  if( SCIPisLE(scip, volume, maxvolume) )
652  {
653  /*
654  * try to verify with heuristic
655  */
656 
657  /* compute time limit */
658  timelim = MIN(heurtilim, *timeleft);
659 
660  /* verify pattern */
661  *timeleft += SCIPgetTotalTime(scip);
662  SCIP_CALL( SCIPverifyCircularPatternHeuristic(scip, probdata, pattern, timelim, heuriterlim) );
663  *timeleft -= SCIPgetTotalTime(scip);
664 
665  /*
666  * try to verify with NLP
667  */
669  {
670  /* compute time limit */
671  timelim = MIN(*timeleft, nlptilim);
672 
673  /* verify pattern */
674  *timeleft += SCIPgetTotalTime(scip);
675  SCIP_CALL( SCIPverifyCircularPatternNLP(scip, probdata, pattern, timelim, nlpnodelim) );
676  *timeleft -= SCIPgetTotalTime(scip);
677  }
678 
679  /* pattern is not packable -> don't add more elements */
681  {
682  SCIPpatternRemoveLastElements(pattern, nselected[t]);
683  volume -= SQR(rexts[t]) * M_PI * nselected[t];
684  nselected[t] = 0;
685  --t;
686  }
687  /* otherwise add the pattern (and hope for filtering) */
688  else
689  {
690  SCIP_CALL( SCIPprobdataAddVar(scip, probdata, pattern, NULL) );
691  }
692  }
693 
694  /* update selection */
695  while( t > type && (nselected[t] == ms[t] || SCIPisGT(scip, volume, maxvolume)) )
696  {
697  SCIPpatternRemoveLastElements(pattern, nselected[t]);
698  volume -= SQR(rexts[t]) * M_PI * nselected[t];
699  nselected[t] = 0;
700  t--;
701  }
702 
703  /* check termination criterion */
704  if( t == type )
705  break;
706 
707  /* add element of type i to the pattern */
708  assert(nselected[t] < ms[t]);
709  ++(nselected[t]);
710  volume += SQR(rexts[t]) * M_PI;
712  }
713 
714  assert(SCIPpatternGetNElemens(pattern) == 0);
715  assert(SCIPisZero(scip, volume));
716 
717  return SCIP_OKAY;
718 }
719 
720 /** auxiliary function to setup the master problem */
721 static
723  SCIP* scip, /**< SCIP data structure */
724  SCIP_PROBDATA* probdata /**< problem data */
725  )
726 {
727  char name[SCIP_MAXSTRLEN];
728  SCIP_Real* rexts;
729  SCIP_Real* rints;
730  int* demands;
731  SCIP_Real dualbound;
732  SCIP_Real minrext;
733  SCIP_Real volume;
734  int ntypes;
735  int p;
736  int t;
737 
738  assert(probdata != NULL);
739  assert(SCIPprobdataGetNTypes(probdata) > 0);
740 
741  /* set objective sense; tell SCIP that the objective will be always integral */
743  SCIP_CALL( SCIPsetObjIntegral(scip) );
744 
745  /* get problem data */
746  ntypes = SCIPprobdataGetNTypes(probdata);
747  rexts = SCIPprobdataGetRexts(probdata);
748  rints = SCIPprobdataGetRints(probdata);
749  demands = SCIPprobdataGetDemands(probdata);
750 
751  /* compute all non-dominated circular patterns */
752  probdata->enumtime -= SCIPgetTotalTime(scip);
753  SCIP_CALL( SCIPprobdataEnumeratePatterns(scip, probdata, probdata->nlptilimsoft, probdata->heurtilimsoft,
754  probdata->totaltilimsoft, probdata->nlpnodelimsoft, probdata->heuriterlimsoft) );
755  probdata->enumtime += SCIPgetTotalTime(scip);
756  probdata->ncppatternsunknownbeg = getNCPatterns(scip, probdata, SCIP_PACKABLE_UNKNOWN);
757 
758  SCIPinfoMessage(scip, NULL, "+++++++++++++ starting with |CP|=%d\n", probdata->ncpatterns);
759 
760  /* create initial rectangular patterns */
761  for( t = 0; t < ntypes; ++t )
762  {
763  SCIP_PATTERN* pattern;
764 
765  /* create a pattern containing a single circle of type t; set position of the circle to the left-bottom */
766  SCIP_CALL( SCIPpatternCreateRectangular(scip, &pattern) );
767  SCIP_CALL( SCIPpatternAddElement(pattern, t, rexts[t], rexts[t]) );
769 
770  /* add and release pattern */
771  SCIP_CALL( SCIPprobdataAddVar(scip, probdata, pattern, NULL) );
772  SCIPpatternRelease(scip, &pattern);
773  }
774 
775  /* create variables for all existing patterns */
776  SCIP_CALL( createPatternVars(scip, probdata) );
777 
778  /* create demand constraints */
779  for( t = 0; t < ntypes; ++t )
780  {
781  SCIP_CONS* cons;
782 
783  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "demand_%d", t);
784  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name, 0, NULL, NULL, (SCIP_Real)demands[t], SCIPinfinity(scip) ) );
785 
786  for( p = 0; p < probdata->ncpatterns; ++p )
787  {
788  SCIP_PATTERN* pattern;
789  SCIP_VAR* var;
790 
791  pattern = probdata->cpatterns[p];
792  assert(pattern != NULL);
794 
795  var = probdata->cvars[p];
796  assert(var != NULL);
797 
798  /* add coefficient to the pattern if the pattern is of type t */
799  if(SCIPpatternGetCircleType(pattern) == t )
800  {
801  SCIP_CALL( SCIPaddCoefLinear(scip, cons, var, 1.0) );
802  }
803  }
804 
805  /* add and release constraint */
806  SCIP_CALL( SCIPaddCons(scip, cons) );
807  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
808  }
809 
810  /* create pattern constraints */
811  for( t = 0; t < ntypes; ++t )
812  {
813  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "patterncons_%d", t);
814  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &probdata->patternconss[t], name, 0, NULL, NULL, 0.0,
815  SCIPinfinity(scip) ) );
816 
817  /* declare constraint modifiable for adding variables during pricing */
818  SCIP_CALL( SCIPsetConsModifiable(scip, probdata->patternconss[t], TRUE) );
819  SCIP_CALL( SCIPaddCons(scip, probdata->patternconss[t]) );
820  }
821 
822  /* add coefficients for circular patterns */
823  for( p = 0; p < probdata->ncpatterns; ++p )
824  {
825  SCIP_PATTERN* pattern = probdata->cpatterns[p];
826  SCIP_VAR* var = probdata->cvars[p];
827  int type;
828 
829  assert(pattern != NULL);
831  assert(var != NULL);
832 
833  type = SCIPpatternGetCircleType(pattern);
834  assert(type >= 0 && type < ntypes);
835 
836  /* - z_C */
837  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->patternconss[type], var, -1.0) );
838 
839  for( t = 0; t < ntypes; ++t )
840  {
841  int nelems = SCIPpatternCountElements(pattern, t);
842 
843  if( nelems > 0 )
844  {
845  /* + P_t z_C */
846  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->patternconss[t], var, (SCIP_Real)nelems) );
847  }
848  }
849  }
850 
851  /* add coefficients for rectangular patterns */
852  for( p = 0; p < probdata->nrpatterns; ++p )
853  {
854  SCIP_PATTERN* pattern = probdata->rpatterns[p];
855  SCIP_VAR* var = probdata->rvars[p];
856 
857  assert(pattern != NULL);
859  assert(var != NULL);
860 
861  for( t = 0; t < ntypes; ++t )
862  {
863  int nelems = SCIPpatternCountElements(pattern, t);
864 
865  if( nelems > 0 )
866  {
867  /* + P_t z_P */
868  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->patternconss[t], var, (SCIP_Real)nelems) );
869  }
870  }
871  }
872 
873  /* compute an initial dual bound by considering the volume of all rings */
874  minrext = rexts[ntypes-1];
875  volume = 0.0;
876  for( t = 0; t < ntypes; ++t )
877  {
878  SCIP_Real vol;
879 
880  /* consider ring as circle if there is no ring with a smaller radius than than inner one */
881  if( SCIPisFeasLT(scip, rints[t], minrext) )
882  vol = M_PI * SQR(rexts[t]);
883  else
884  vol = M_PI * (SQR(rexts[t]) - SQR(rints[t]));
885 
886  volume += vol * demands[t];
887  }
888 
889  /* update initial dual bound */
890  dualbound = SCIPfeasCeil(scip, volume / (SCIPprobdataGetWidth(probdata) * SCIPprobdataGetHeight(probdata)));
891  SCIP_CALL( SCIPupdateLocalDualbound(scip, dualbound) );
892  SCIPinfoMessage(scip, NULL, "+++++++++++++ volume-based bound = ceil(%g / %g) = %g\n", volume,
893  SCIPprobdataGetWidth(probdata) * SCIPprobdataGetHeight(probdata), dualbound);
894  SCIPprobdataUpdateDualbound(scip, probdata, dualbound);
895 
896  return SCIP_OKAY;
897 }
898 
899 /** output method of statistics table to output file stream 'file' */
900 static
901 SCIP_DECL_TABLEOUTPUT(tableOutputRpa)
902 { /*lint --e{715}*/
903  SCIP_PROBDATA* probdata;
904  SCIP_Real* rexts;
905  SCIP_Real* rints;
906  SCIP_Real dualbound;
907  SCIP_Real maxrint;
908  SCIP_Real minrext;
909  int* demands;
910  int ntypes;
911  int nrings;
912  int t;
913 
914  probdata = SCIPgetProbData(scip);
915  assert(probdata != NULL);
916 
917  ntypes = SCIPprobdataGetNTypes(probdata);
918  demands = SCIPprobdataGetDemands(probdata);
919  rexts = SCIPprobdataGetRexts(probdata);
920  rints = SCIPprobdataGetRints(probdata);
921  nrings = 0;
922  maxrint = 0.0;
923  minrext = SCIPinfinity(scip);
924 
925  /* use global dual bound if it is still valid */
926  if( !probdata->isdualinvalid )
927  {
928  assert(SCIPisGE(scip, SCIPgetDualbound(scip), probdata->dualbound));
929  dualbound = SCIPgetDualbound(scip);
930  }
931  else
932  dualbound = probdata->dualbound;
933 
934  /* count the number of rings */
935  for( t = 0; t < ntypes; ++t )
936  {
937  nrings += demands[t];
938  maxrint = MAX(maxrint, rints[t]);
939  minrext = MIN(minrext, rexts[t]);
940  }
941 
942  SCIPinfoMessage(scip, file, "Ringpacking : %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s\n",
943  "dual", "ntypes", "nrings", "width", "height", "CP", "CP_unk", "CP_unk_end" ,"CP_infeas", "RP", "enumtime", "radiiratio");
944 
945  SCIPinfoMessage(scip, file, " %-17s:", "");
946  SCIPinfoMessage(scip, file, " %10.2f", dualbound);
947  SCIPinfoMessage(scip, file, " %10d", ntypes);
948  SCIPinfoMessage(scip, file, " %10d", nrings);
949  SCIPinfoMessage(scip, file, " %10.2f", SCIPprobdataGetWidth(probdata));
950  SCIPinfoMessage(scip, file, " %10.2f", SCIPprobdataGetHeight(probdata));
951  SCIPinfoMessage(scip, file, " %10d", probdata->ncpatterns);
952  SCIPinfoMessage(scip, file, " %10d", probdata->ncppatternsunknownbeg);
953  SCIPinfoMessage(scip, file, " %10d", getNCPatterns(scip, probdata, SCIP_PACKABLE_UNKNOWN));
954  SCIPinfoMessage(scip, file, " %10d", getNCPatterns(scip, probdata, SCIP_PACKABLE_NO));
955  SCIPinfoMessage(scip, file, " %10d", probdata->nrpatterns);
956  SCIPinfoMessage(scip, file, " %10.2f", probdata->enumtime);
957  SCIPinfoMessage(scip, file, " %10.1f", maxrint / minrext);
958  SCIPinfoMessage(scip, file, "\n");
959 
960  return SCIP_OKAY;
961 }
962 
963 /** auxiliary function to update the best known candidate */
964 static
966  SCIP* scip, /**< SCIP data structure */
967  SCIP_Real* xs, /**< x-coordinates of packed elements */
968  SCIP_Real* ys, /**< y-coordinates of packed elements */
969  SCIP_Real* rexts, /**< radii of packed elements */
970  SCIP_Real rext, /**< radii of element that should be packed */
971  SCIP_Real rbounding, /**< inner radius of bounding circle (ignored for rectangular patterns) */
972  SCIP_Real wbounding, /**< width of bounding rectangular (ignored for circular patterns) */
973  SCIP_Real hbounding, /**< height of bounding rectangular (ignored for circular patterns) */
974  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
975  SCIP_PATTERNTYPE patterntype, /**< pattern type */
976  SCIP_Bool* ispacked, /**< array indicating which elements are already packed */
977  int* elements, /**< the order of the elements in the pattern */
978  int nelements, /**< the total number of elements */
979  SCIP_Real* bestx, /**< buffer to update best x-coordinate */
980  SCIP_Real* besty, /**< buffer to update best y-coordinate */
981  SCIP_Real x, /**< x-coordinate of a candidate point */
982  SCIP_Real y, /**< y-coordinate of a candidate point */
983  int ncalls /**< total number of calls of the packing heuristic */
984  )
985 {
986  SCIP_Real threshold;
987  SCIP_Bool isoverthreshold;
988  int i;
989 
990  /* candidate is not valid -> skip */
991  if( x == SCIP_INVALID || y == SCIP_INVALID ) /*lint !e777*/
992  return;
993 
994  /* check whether there is an intersection with the boundary */
995  if( patterntype == SCIP_PATTERNTYPE_CIRCULAR )
996  {
997  if( SCIPisGT(scip, x*x + y*y, SQR(rbounding - rext)) )
998  return;
999  }
1000  else
1001  {
1002  if( SCIPisLT(scip, x, rext) || SCIPisGT(scip, x, wbounding - rext)
1003  || SCIPisLT(scip, y, rext) || SCIPisGT(scip, y, hbounding - rext) )
1004  return;
1005  }
1006 
1007  /* check whether circle intersects other circles */
1008  for( i = 0; i < nelements; ++i )
1009  {
1010  SCIP_Real dist;
1011 
1012  /* only consider packed elements */
1013  if( !ispacked[i] )
1014  continue;
1015 
1016  dist = SQR(x - xs[i]) + SQR(y - ys[i]);
1017 
1018  /* check if the distance between mid points is smaller than the sum of the radii */
1019  if( SCIPisLT(scip, dist, SQR(rext + rexts[elements[i]])) )
1020  return;
1021  }
1022 
1023  threshold = (patterntype == SCIP_PATTERNTYPE_RECTANGULAR ? wbounding - 2.0*rmax - rext : rbounding - 2.0*rmax - rext);
1024  isoverthreshold = (ncalls % 2) == 1 && SCIPisGT(scip, *bestx, threshold) && SCIPisGT(scip, x, threshold);
1025 
1026  /* check whether the candidate is better than the best known candidate */
1027  if( *bestx == SCIP_INVALID || *besty == SCIP_INVALID
1028  || ((!isoverthreshold || SCIPisEQ(scip, y, *besty)) && SCIPisLT(scip, x, *bestx)) /*lint !e777*/
1029  || ((isoverthreshold || SCIPisEQ(scip, x, *bestx)) && SCIPisLT(scip, y, *besty)) ) /*lint !e777*/
1030  {
1031  *bestx = x;
1032  *besty = y;
1033  }
1034 }
1035 
1036 /** auxiliary function for computing a candidate position between a circle and the outer ring */
1037 static
1039  SCIP* scip, /**< SCIP data structure */
1040  int* elements, /**< types of elements that have been packed */
1041  int nelements, /**< the total number of elements */
1042  SCIP_Real* rexts, /**< external radii */
1043  SCIP_Real* xs, /**< x-coordinate of circle */
1044  SCIP_Real* ys, /**< y-coordinate of circle */
1045  int pos, /**< position of element in the elements array */
1046  SCIP_Bool* ispacked, /**< array indicating whether an element has been packed already */
1047  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
1048  SCIP_Real rbound, /**< radius of bounding circle */
1049  SCIP_Real* bestx, /**< pointer to store the best x-coordinate */
1050  SCIP_Real* besty, /**< pointer to store the best y-coordinate */
1051  int ncalls /**< total number of calls of the packing heuristic */
1052  )
1053 {
1054  int i;
1055 
1056  /* consider already packed patterns */
1057  for( i = 0; i < nelements; ++i )
1058  {
1059  SCIP_Real alpha, a, b, c, h, u, v, n1, n2;
1060 
1061  /* only consider packed elements */
1062  if( !ispacked[i] )
1063  continue;
1064 
1065  c = sqrt(xs[i]*xs[i] + ys[i]*ys[i]);
1066 
1067  /* inner ring is too far away from boundary or both rings can not fit */
1068  if( !SCIPisGE(scip, c + rexts[elements[i]] + 2.0*rexts[elements[pos]], rbound)
1069  || SCIPisGT(scip, rexts[elements[pos]] + rexts[elements[i]], rbound) )
1070  continue;
1071 
1072  a = rexts[elements[pos]] + rexts[elements[i]];
1073  b = rbound - rexts[elements[pos]];
1074 
1075  /* if a ring is in the center than there are infinitely many solutions; take an arbitrary point */
1076  if( SCIPisZero(scip, c) )
1077  {
1078  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, -1.0, -1.0, rmax, SCIP_PATTERNTYPE_CIRCULAR,
1079  ispacked, elements, nelements, bestx, besty, -rbound + rexts[elements[pos]], 0.0, ncalls);
1080  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, -1.0, -1.0, rmax, SCIP_PATTERNTYPE_CIRCULAR,
1081  ispacked, elements, nelements, bestx, besty, +rbound - rexts[elements[pos]], 0.0, ncalls);
1082  }
1083  else
1084  {
1085  assert(c != 0.0);
1086  alpha = (c*c - b*b + a*a) / (2*c);
1087 
1088  if( a*a >= alpha*alpha )
1089  {
1090  h = sqrt(MAX(a*a - alpha*alpha, 0.0));
1091  u = (c - alpha) * xs[i] / c;
1092  v = (c - alpha) * ys[i] / c;
1093 
1094  n1 = SCIPisZero(scip, v) ? 0.0 : h * (v / sqrt(v*v + u*u));
1095  n2 = SCIPisZero(scip, u) ? 0.0 : h * (-u / sqrt(v*v + u*u));
1096 
1097  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, -1.0, -1.0, rmax, SCIP_PATTERNTYPE_CIRCULAR,
1098  ispacked, elements, nelements, bestx, besty, u + n1, v + n2, ncalls);
1099  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, -1.0, -1.0, rmax, SCIP_PATTERNTYPE_CIRCULAR,
1100  ispacked, elements, nelements, bestx, besty, u - n1, v - n2, ncalls);
1101  }
1102  }
1103  }
1104 }
1105 
1106 /** auxiliary function for computing trivial candidate positions */
1107 static
1109  SCIP* scip, /**< SCIP data structure */
1110  int* elements, /**< types of elements that have been packed */
1111  int nelements, /**< the total number of elements */
1112  SCIP_Real* rexts, /**< external radii */
1113  SCIP_Real* xs, /**< x-coordinate of circle */
1114  SCIP_Real* ys, /**< y-coordinate of circle */
1115  int pos, /**< position of element in the elements array */
1116  SCIP_Bool* ispacked, /**< array indicating whether an element has been packed already */
1117  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
1118  SCIP_Real rbound, /**< radius of bounding circle */
1119  SCIP_Real width, /**< width of the rectangle */
1120  SCIP_Real height, /**< height of the rectangle */
1121  SCIP_PATTERNTYPE patterntype, /**< the pattern type (rectangular or circular) */
1122  SCIP_Real* bestx, /**< pointer to store the best x-coordinate */
1123  SCIP_Real* besty, /**< pointer to store the best y-coordinate */
1124  int ncalls /**< total number of calls of the packing heuristic */
1125  )
1126 {
1127  SCIP_Real rext = rexts[elements[pos]];
1128  int i;
1129 
1130  if( patterntype == SCIP_PATTERNTYPE_CIRCULAR )
1131  {
1132  SCIP_Real xcands[4] = {-rbound + rext, +rbound - rext, 0.0, 0.0};
1133  SCIP_Real ycands[4] = {0.0, 0.0, -rbound + rext, +rbound - rext};
1134 
1135  for( i = 0; i < 4; ++i )
1136  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, width, height, rmax, patterntype,
1137  ispacked, elements, nelements, bestx, besty, xcands[i], ycands[i], ncalls);
1138  }
1139  else
1140  {
1141  SCIP_Real xcands[4] = {rext, width - rext, rext, width - rext};
1142  SCIP_Real ycands[4] = {rext, rext, height - rext, height - rext};
1143 
1144  for( i = 0; i < 4; ++i )
1145  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, width, height, rmax, patterntype,
1146  ispacked, elements, nelements, bestx, besty, xcands[i], ycands[i], ncalls);
1147  }
1148 }
1149 
1150 /** auxiliary function for computing a candidate position between a circle and the rectangle */
1151 static
1153  SCIP* scip, /**< SCIP data structure */
1154  int* elements, /**< types of elements that have been packed */
1155  int nelements, /**< the total number of elements */
1156  SCIP_Real* rexts, /**< external radii */
1157  SCIP_Real* xs, /**< x-coordinate of circle */
1158  SCIP_Real* ys, /**< y-coordinate of circle */
1159  int pos, /**< position of element in the elements array */
1160  SCIP_Bool* ispacked, /**< array indicating whether an element has been packed already */
1161  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
1162  SCIP_Real width, /**< width of the rectangle */
1163  SCIP_Real height, /**< height of the rectangle */
1164  SCIP_Real* bestx, /**< pointer to store the best x-coordinate */
1165  SCIP_Real* besty, /**< pointer to store the best y-coordinate */
1166  int ncalls /**< total number of calls of the packing heuristic */
1167  )
1168 {
1169  SCIP_Real rext;
1170  int i;
1171 
1172  rext = rexts[elements[pos]];
1173 
1174  for( i = 0; i < nelements; ++i )
1175  {
1176  SCIP_Real xfix[2] = {rext, width - rext};
1177  SCIP_Real yfix[2] = {rext, height - rext};
1178  SCIP_Real Ri;
1179  int k;
1180 
1181  if( !ispacked[i] )
1182  continue;
1183 
1184  Ri = rexts[elements[i]];
1185 
1186  /* fix x */
1187  for( k = 0; k < 2; ++k )
1188  {
1189  SCIP_Real alpha = SQR(rext + Ri) - SQR(xfix[k] - xs[i]);
1190 
1191  if( alpha < 0.0 )
1192  continue;
1193 
1194  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], -1.0, width, height, rmax,
1195  SCIP_PATTERNTYPE_RECTANGULAR, ispacked, elements, nelements, bestx, besty, xfix[k], ys[i] + sqrt(alpha), ncalls);
1196 
1197  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], -1.0, width, height, rmax,
1198  SCIP_PATTERNTYPE_RECTANGULAR, ispacked, elements, nelements, bestx, besty, xfix[k], ys[i] - sqrt(alpha), ncalls);
1199  }
1200 
1201  /* fix y */
1202  for( k = 0; k < 2; ++k )
1203  {
1204  SCIP_Real alpha = SQR(rext + Ri) - SQR(yfix[k] - ys[i]);
1205 
1206  if( alpha < 0.0 )
1207  continue;
1208 
1209  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], -1.0, width, height, rmax,
1210  SCIP_PATTERNTYPE_RECTANGULAR, ispacked, elements, nelements, bestx, besty, xs[i] + sqrt(alpha), yfix[k], ncalls);
1211 
1212  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], -1.0, width, height, rmax,
1213  SCIP_PATTERNTYPE_RECTANGULAR, ispacked, elements, nelements, bestx, besty, xs[i] - sqrt(alpha), yfix[k], ncalls);
1214  }
1215  }
1216 }
1217 
1218 /** auxiliary function for computing a candidate position between two circles */
1219 static
1221  SCIP* scip, /**< SCIP data structure */
1222  int* elements, /**< types of elements that have been packed */
1223  int nelements, /**< the total number of elements */
1224  SCIP_Real* rexts, /**< external radii */
1225  SCIP_Real* xs, /**< x-coordinate of circle */
1226  SCIP_Real* ys, /**< y-coordinate of circle */
1227  int pos, /**< position of element in the elements array */
1228  SCIP_Bool* ispacked, /**< array indicating whether an element has been packed already */
1229  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
1230  SCIP_Real rbound, /**< radius of bounding circle */
1231  SCIP_Real width, /**< width of the rectangle */
1232  SCIP_Real height, /**< height of the rectangle */
1233  SCIP_PATTERNTYPE patterntype, /**< the pattern type (rectangular or circular) */
1234  SCIP_Real* bestx, /**< pointer to store the best x-coordinate */
1235  SCIP_Real* besty, /**< pointer to store the best y-coordinate */
1236  int ncalls /**< total number of calls of the packing heuristic */
1237  )
1238 {
1239  SCIP_Real rext;
1240  int i;
1241 
1242  rext = rexts[elements[pos]];
1243 
1244  /* consider all pairs of already packed circles */
1245  for( i = 0; i < nelements - 1; ++i )
1246  {
1247  SCIP_Real alpha, a, b, h, u, v, n1, n2;
1248  SCIP_Real Ri;
1249  int j;
1250 
1251  if( !ispacked[i] )
1252  continue;
1253 
1254  Ri = rexts[elements[i]];
1255 
1256  for( j = i + 1; j < nelements; ++j )
1257  {
1258  SCIP_Real Rj;
1259  SCIP_Real dist;
1260 
1261  if( !ispacked[j] )
1262  continue;
1263 
1264  Rj = rexts[elements[j]];
1265  dist = sqrt(SQR(xs[i] - xs[j]) + SQR(ys[i] - ys[j]));
1266 
1267  /* circles are too far away */
1268  if( SCIPisGE(scip, dist, Ri + Rj + 2.0 * rext) )
1269  continue;
1270 
1271  a = Ri + rext;
1272  b = Rj + rext;
1273  assert(dist != 0.0);
1274  alpha = (dist*dist - b*b + a*a) / (2.0*dist);
1275  assert(a*a >= alpha*alpha);
1276  h = sqrt(MAX(a*a - alpha*alpha, 0.0));
1277  u = xs[i] + (alpha / dist) * (xs[j] - xs[i]);
1278  v = ys[i] + (alpha / dist) * (ys[j] - ys[i]);
1279  n1 = h * ((ys[j] - ys[i]) / dist);
1280  n2 = h * ((xs[i] - xs[j]) / dist);
1281  assert(n1*n1 + n2*n2 > 0.0);
1282 
1283  updateBestCandidate(scip, xs, ys, rexts, rext, rbound, width, height, rmax, patterntype, ispacked, elements,
1284  nelements, bestx, besty, u + n1, v + n2, ncalls);
1285  updateBestCandidate(scip, xs, ys, rexts, rext, rbound, width, height, rmax, patterntype, ispacked, elements,
1286  nelements, bestx, besty, u - n1, v - n2, ncalls);
1287  }
1288  }
1289 }
1290 
1291 /** array to compute the score of each element */
1292 static
1294  SCIP* scip, /**< SCIP data structure */
1295  SCIP_PROBDATA* probdata, /**< problem data */
1296  int* elements, /**< type of each element */
1297  int nelements, /**< total number of elements */
1298  SCIP_Real* scores, /**< array to store the score of each element */
1299  int iter /**< iteration round */
1300  )
1301 {
1302  SCIP_Real* rexts;
1303  int i;
1304 
1305  rexts = SCIPprobdataGetRexts(probdata);
1306  assert(rexts != NULL);
1307 
1308  for( i = 0; i < nelements; ++i )
1309  {
1310  SCIP_Real rext = rexts[elements[i]];
1311  /* use largest elements first */
1312  if( iter == 0 )
1313  scores[i] = rext;
1314 
1315  /* use smallest elements first */
1316  else if( iter == 1 )
1317  scores[i] = -rext;
1318 
1319  /* use [0,1] * radius */
1320  else if( iter <= 10 )
1321  scores[i] = SCIPrandomGetReal(probdata->randnumgen, 0.0, 1.0) * rext;
1322 
1323  /* use [-1,0] * radius */
1324  else if( iter <= 20 )
1325  scores[i] = SCIPrandomGetReal(probdata->randnumgen, -1.0, 0.0) * rext;
1326 
1327  /* use a random order */
1328  else
1329  scores[i] = SCIPrandomGetReal(probdata->randnumgen, 0.0, 1.0);
1330  }
1331 }
1332 
1333 /**@} */
1334 
1335 /**@name Callback methods of problem data
1336  *
1337  * @{
1338  */
1339 
1340 /** frees user data of original problem (called when the original problem is freed) */
1341 static
1342 SCIP_DECL_PROBDELORIG(probdelorigRingpacking)
1343 {
1344  SCIPdebugMessage("free original problem data\n");
1345  SCIP_CALL( probdataFree(scip, probdata) );
1346 
1347  return SCIP_OKAY;
1348 }
1349 
1350 /** frees user data of transformed problem (called when the transformed problem is freed) */
1351 static
1352 SCIP_DECL_PROBDELTRANS(probdeltransRingpacking)
1353 {
1354  SCIPdebugMessage("free transformed problem data\n");
1355  SCIP_CALL( probdataFree(scip, probdata) );
1356 
1357  return SCIP_OKAY;
1358 }
1359 
1360 /** creates user data of transformed problem by transforming the original user problem data
1361  * (called after problem was transformed) */
1362 static
1363 SCIP_DECL_PROBTRANS(probtransRingpacking)
1364 { /*lint --e{715}*/
1365  /* create transformed problem data */
1366  SCIP_CALL( probdataCreate(scip, targetdata, sourcedata->patternconss, sourcedata->cpatterns, sourcedata->cvars,
1367  sourcedata->ncpatterns, sourcedata->rpatterns, sourcedata->rvars, sourcedata->nrpatterns,
1368  sourcedata->demands, sourcedata->rints, sourcedata->rexts, sourcedata->ntypes,
1369  sourcedata->width, sourcedata->height) );
1370 
1371  /* transform pattern constraints */
1372  SCIP_CALL( SCIPtransformConss(scip, (*targetdata)->ntypes, (*targetdata)->patternconss,
1373  (*targetdata)->patternconss) );
1374 
1375  /* transform all variables */
1376  SCIP_CALL( SCIPtransformVars(scip, (*targetdata)->ncpatterns, (*targetdata)->cvars, (*targetdata)->cvars) );
1377  SCIP_CALL( SCIPtransformVars(scip, (*targetdata)->nrpatterns, (*targetdata)->rvars, (*targetdata)->rvars) );
1378 
1379  /* copy statistics to transformed problem data */
1380  (*targetdata)->ncppatternsunknownbeg = sourcedata->ncppatternsunknownbeg;
1381  (*targetdata)->enumtime = sourcedata->enumtime;
1382  (*targetdata)->dualbound = sourcedata->dualbound;
1383  (*targetdata)->isdualinvalid = sourcedata->isdualinvalid;
1384 
1385  return SCIP_OKAY;
1386 }
1387 
1388 /**@} */
1389 
1390 /**@name Interface methods
1391  *
1392  * @{
1393  */
1394 
1395 /** sets up the problem data */
1397  SCIP* scip, /**< SCIP data structure */
1398  const char* probname, /**< problem name */
1399  int* demands, /**< array containing the demands */
1400  SCIP_Real* rints, /**< internal radii of each ring */
1401  SCIP_Real* rexts, /**< external radii of each ring (assumed to be sorted) */
1402  int ntypes, /**< number of different types */
1403  SCIP_Real width, /**< width of each rectangle */
1404  SCIP_Real height /**< height of each rectangle */
1405  )
1406 {
1407  SCIP_PROBDATA* probdata;
1408 
1409 #ifndef NDEBUG
1410  {
1411  int t;
1412 
1413  for( t = 0; t < ntypes -1; ++t )
1414  assert(rexts[t] >= rexts[t+1]);
1415  }
1416 #endif
1417 
1418  /* create SCIP problem */
1419  SCIP_CALL( SCIPcreateProbBasic(scip, probname) );
1420 
1421  /* create and set problem data */
1422  SCIP_CALL( probdataCreate(scip, &probdata, NULL, NULL, NULL, 0, NULL, NULL, 0, demands, rints, rexts, ntypes, width,
1423  height) );
1424  SCIP_CALL( SCIPsetProbData(scip, probdata) );
1425 
1426  SCIP_CALL( SCIPsetProbDelorig(scip, probdelorigRingpacking) );
1427  SCIP_CALL( SCIPsetProbTrans(scip, probtransRingpacking) );
1428  SCIP_CALL( SCIPsetProbDeltrans(scip, probdeltransRingpacking) );
1429 
1430  /* activate pricer */
1432 
1433  /* add table output */
1434  assert(SCIPfindTable(scip, TABLE_NAME_RPA) == NULL);
1436  NULL, NULL, NULL, NULL, NULL, NULL, tableOutputRpa,
1438 
1439  return SCIP_OKAY;
1440 }
1441 
1442 /** enumerates circular patterns and creates restricted master problem */
1444  SCIP* scip /**< SCIP data structure */
1445  )
1446 {
1447  SCIP_PROBDATA* probdata = SCIPgetProbData(scip);
1448  assert(probdata != NULL);
1449 
1450  /* collect parameters for verification */
1451  SCIP_CALL( SCIPgetRealParam(scip, "ringpacking/verification/nlptilimsoft", &probdata->nlptilimsoft) );
1452  SCIP_CALL( SCIPgetRealParam(scip, "ringpacking/verification/heurtilimsoft", &probdata->heurtilimsoft) );
1453  SCIP_CALL( SCIPgetLongintParam(scip, "ringpacking/verification/nlpnodelimsoft", &probdata->nlpnodelimsoft) );
1454  SCIP_CALL( SCIPgetIntParam(scip, "ringpacking/verification/heuriterlimsoft", &probdata->heuriterlimsoft) );
1455  SCIP_CALL( SCIPgetRealParam(scip, "ringpacking/verification/totaltilimsoft", &probdata->totaltilimsoft) );
1456 
1457  SCIP_CALL( setupProblem(scip, probdata) );
1458 
1459  return SCIP_OKAY;
1460 }
1461 
1462 /** enumerate all non-dominated circular patterns */
1464  SCIP* scip, /**< SCIP data structure */
1465  SCIP_PROBDATA* probdata, /**< problem data */
1466  SCIP_Real nlptilim, /**< time limit for each NLP verification */
1467  SCIP_Real heurtilim, /**< time limit for each call of the heuristics */
1468  SCIP_Real totaltilim, /**< total time limit for enumeration */
1469  SCIP_Longint nlpnodelim, /**< node limit for each NLP verification */
1470  int heuriterlim /**< iteration limit for each call of the heuristics */
1471  )
1472 {
1473  SCIP_PATTERN* pattern;
1474  int* ms;
1475  int* nselected;
1476  SCIP_Real timeleft;
1477  int ntypes;
1478  int t;
1479 
1480  assert(probdata != NULL);
1481  ntypes = SCIPprobdataGetNTypes(probdata);
1482  assert(ntypes > 0);
1483 
1484  /* create data that is used for the whole enumeration algorithm */
1485  SCIP_CALL( SCIPpatternCreateCircular(scip, &pattern, 0) );
1486  SCIP_CALL( SCIPallocBufferArray(scip, &ms, ntypes) );
1487  SCIP_CALL( SCIPallocBufferArray(scip, &nselected, ntypes) );
1488  BMSclearMemoryArray(nselected, ntypes);
1489  BMSclearMemoryArray(ms, ntypes);
1490 
1491  /* compute time limit */
1492  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timeleft) );
1493  timeleft = MAX(0.0, MIN(timeleft - SCIPgetTotalTime(scip), totaltilim)); /*lint !e666*/
1494 
1495  /* find all circlular patterns of each type separately */
1496  for( t = 0; t < ntypes; ++t )
1497  {
1498  int k;
1499 
1500  for( k = t+1; k < ntypes; ++k )
1501  ms[k] = maxCircles(scip, probdata, t, k);
1502 
1503  SCIPpatternSetType(pattern, t);
1504  SCIP_CALL( enumeratePatterns(scip, probdata, pattern, ms, nselected, nlptilim, heurtilim, nlpnodelim,
1505  heuriterlim, &timeleft) );
1506  }
1507 
1508  /* release memory */
1509  SCIPfreeBufferArray(scip, &nselected);
1510  SCIPfreeBufferArray(scip, &ms);
1511  SCIPpatternRelease(scip, &pattern);
1512 
1513  /* filter circular patterns */
1514  SCIP_CALL( filterPatterns(scip, probdata) );
1515 
1516  return SCIP_OKAY;
1517 }
1518 
1519 /** returns number of different types */
1521  SCIP_PROBDATA* probdata /**< problem data */
1522  )
1523 {
1524  assert(probdata != NULL);
1525 
1526  return probdata->ntypes;
1527 }
1528 
1529 /** returns all external radii */
1531  SCIP_PROBDATA* probdata /**< problem data */
1532  )
1533 {
1534  assert(probdata != NULL);
1535 
1536  return probdata->rexts;
1537 }
1538 
1539 /** returns all internal radii */
1541  SCIP_PROBDATA* probdata /**< problem data */
1542  )
1543 {
1544  assert(probdata != NULL);
1545 
1546  return probdata->rints;
1547 }
1548 
1549 /** returns all demands */
1551  SCIP_PROBDATA* probdata /**< problem data */
1552  )
1553 {
1554  assert(probdata != NULL);
1555 
1556  return probdata->demands;
1557 }
1558 
1559 /** returns the width of each rectangle */
1561  SCIP_PROBDATA* probdata /**< problem data */
1562  )
1563 {
1564  assert(probdata != NULL);
1565 
1566  return probdata->width;
1567 }
1568 
1569 
1570 /** returns the height of each rectangle */
1572  SCIP_PROBDATA* probdata /**< problem data */
1573  )
1574 {
1575  assert(probdata != NULL);
1576 
1577  return probdata->height;
1578 }
1579 
1580 /** returns all information about circular patterns */
1582  SCIP_PROBDATA* probdata, /**< problem data */
1583  SCIP_PATTERN*** cpatterns, /**< pointer to store the circular patterns (might be NULL) */
1584  SCIP_VAR*** cvars, /**< pointer to store the variables corresponding circular patterns (might be NULL) */
1585  int* ncpatterns /**< pointer to store the number of circular patterns (might be NULL) */
1586  )
1587 {
1588  assert(probdata != NULL);
1589 
1590  if( cpatterns != NULL )
1591  *cpatterns = probdata->cpatterns;
1592  if( cvars != NULL )
1593  *cvars= probdata->cvars;
1594  if( ncpatterns != NULL )
1595  *ncpatterns = probdata->ncpatterns;
1596 }
1597 
1598 /** returns all information about rectangular patterns */
1600  SCIP_PROBDATA* probdata, /**< problem data */
1601  SCIP_PATTERN*** rpatterns, /**< pointer to store the rectangular patterns (might be NULL) */
1602  SCIP_VAR*** rvars, /**< pointer to store the variables corresponding rectangular patterns (might be NULL) */
1603  int* nrpatterns /**< pointer to store the number of rectangular patterns (might be NULL) */
1604  )
1605 {
1606  assert(probdata != NULL);
1607 
1608  if( rpatterns != NULL )
1609  *rpatterns = probdata->rpatterns;
1610  if( rvars != NULL )
1611  *rvars= probdata->rvars;
1612  if( nrpatterns != NULL )
1613  *nrpatterns = probdata->nrpatterns;
1614 }
1615 
1616 /** returns array of set pattern constraints */
1618  SCIP_PROBDATA* probdata /**< problem data */
1619  )
1620 {
1621  assert(probdata != NULL);
1622 
1623  return probdata->patternconss;
1624 }
1625 
1626 /** adds given variable to the problem data */
1628  SCIP* scip, /**< SCIP data structure */
1629  SCIP_PROBDATA* probdata, /**< problem data */
1630  SCIP_PATTERN* pattern, /**< pattern */
1631  SCIP_VAR* var /**< variables to add */
1632  )
1633 {
1634  SCIP_PATTERN* copy;
1635 
1636  assert(probdata != NULL);
1637  assert(pattern != NULL);
1638  assert(SCIPpatternGetPackableStatus(pattern) != SCIP_PACKABLE_NO);
1639 
1640  /* copy pattern */
1641  SCIP_CALL( SCIPpatternCopy(scip, pattern, &copy) );
1642  SCIPcheckPattern(scip, probdata, copy);
1643 
1645  {
1646  SCIP_CALL( ensureSize(scip, probdata, SCIP_PATTERNTYPE_CIRCULAR, probdata->ncpatterns + 1) );
1647  probdata->cpatterns[probdata->ncpatterns] = copy;
1648  probdata->cvars[probdata->ncpatterns] = var;
1649  ++(probdata->ncpatterns);
1650  }
1651  else
1652  {
1653  SCIP_CALL( ensureSize(scip, probdata, SCIP_PATTERNTYPE_RECTANGULAR, probdata->nrpatterns + 1) );
1654  probdata->rpatterns[probdata->nrpatterns] = copy;
1655  probdata->rvars[probdata->nrpatterns] = var;
1656  ++(probdata->nrpatterns);
1657  }
1658 
1659  /* capture variable and pattern */
1660  if( var != NULL )
1661  {
1662  SCIP_CALL( SCIPcaptureVar(scip, var) );
1663  }
1664 
1665  return SCIP_OKAY;
1666 }
1667 
1668 /** updates the dual bound */
1670  SCIP* scip, /**< SCIP data structure */
1671  SCIP_PROBDATA* probdata, /**< problem data */
1672  SCIP_Real dualbound /**< new dual bound */
1673  )
1674 {
1675  assert(probdata != NULL);
1676 
1677  if( !probdata->isdualinvalid && SCIPisFeasLT(scip, probdata->dualbound, dualbound) )
1678  {
1679  SCIPinfoMessage(scip, NULL, "+++++++++++++ update dual bound to %g\n", dualbound);
1680  probdata->dualbound = dualbound;
1681  }
1682 }
1683 
1684 /** marks that further reported dual bounds are not valid */
1686  SCIP* scip, /**< SCIP data structure */
1687  SCIP_PROBDATA* probdata /**< problem data */
1688  )
1689 {
1690  assert(probdata != NULL);
1691 
1692  if( !probdata->isdualinvalid )
1693  {
1694  SCIPinfoMessage(scip, NULL, "+++++++++++++ invalidate dual bound\n");
1695  probdata->isdualinvalid = TRUE;
1696  }
1697 }
1698 
1699 /** returns whether dual bound is marked to be invalid */
1701  SCIP_PROBDATA* probdata /**< problem data */
1702  )
1703 {
1704  assert(probdata != NULL);
1705 
1706  return probdata->isdualinvalid;
1707 }
1708 
1709 /** Tries to pack a list of elements into a specified boundary circle by using a simple left-first bottom-second
1710  * heuristic. Returns the number of elements that could be stored and indicated which ones these are in the buffer
1711  * parameter ispacked. This auxiliary method can be used both to find such a packing or to verify a certain pattern.
1712  */
1714  SCIP* scip, /**< SCIP data structure */
1715  SCIP_Real* rexts, /**< outer radii of elements (in original order of probdata) */
1716  SCIP_Real* xs, /**< buffer to store the resulting x-coordinates */
1717  SCIP_Real* ys, /**< buffer to store the resulting y-coordinates */
1718  SCIP_Real rbounding, /**< inner radius of bounding circle (ignored for rectangular patterns) */
1719  SCIP_Real width, /**< width of the rectangle */
1720  SCIP_Real height, /**< height of the rectangle */
1721  SCIP_Bool* ispacked, /**< buffer to store which elements could be packed */
1722  int* elements, /**< the order of the elements in the pattern */
1723  int nelements, /**< number of elements in the pattern */
1724  SCIP_PATTERNTYPE patterntype, /**< the pattern type (rectangular or circular) */
1725  int* npacked, /**< pointer to store the number of packed elements */
1726  int ncalls /**< total number of calls of the packing heuristic */
1727  )
1728 {
1729  SCIP_Real rmax;
1730  SCIP_Bool added;
1731  int i;
1732 
1733  assert(rexts != NULL);
1734  assert(xs != NULL);
1735  assert(ys != NULL);
1736  assert(ispacked != NULL);
1737  assert(elements != NULL);
1738  assert(nelements > 0);
1739  assert(npacked != NULL);
1740 
1741  /* no element packed so far */
1742  BMSclearMemoryArray(ispacked, nelements);
1743 
1744  /* place first element at left-most position */
1745  if( patterntype == SCIP_PATTERNTYPE_CIRCULAR )
1746  {
1747  assert(rexts[elements[0]] <= rbounding);
1748  xs[0] = rexts[elements[0]] - rbounding;
1749  ys[0] = 0.0;
1750  }
1751  else
1752  {
1753  assert(2.0 * rexts[elements[0]] <= width);
1754  assert(2.0 * rexts[elements[0]] <= height);
1755  xs[0] = rexts[elements[0]];
1756  ys[0] = rexts[elements[0]];
1757  }
1758 
1759  /* initialize results */
1760  (*npacked) = 1;
1761  ispacked[0] = TRUE;
1762  added = TRUE;
1763 
1764  /* find max radius */
1765  rmax = rexts[elements[0]];
1766  for( i = 1; i < nelements; ++i )
1767  {
1768  if( rexts[elements[i]] > rmax )
1769  rmax = rexts[elements[i]];
1770  }
1771 
1772  /* iterate over all elements and try to pack them */
1773  while( added )
1774  {
1775  added = FALSE;
1776 
1777  for( i = 1; i < nelements; ++i )
1778  {
1779  SCIP_Real bestx = SCIP_INVALID;
1780  SCIP_Real besty = SCIP_INVALID;
1781 
1782  /* skip packed elements */
1783  if( ispacked[i] )
1784  continue;
1785 
1786  /* use trivial candidates */
1787  computePosTrivial(scip, elements, nelements, rexts, xs, ys, i, ispacked, rmax, rbounding, width, height,
1788  patterntype, &bestx, &besty, ncalls);
1789 
1790  /* consider circles intersection a previous circle and the boundary ring */
1791  if( patterntype == SCIP_PATTERNTYPE_CIRCULAR )
1792  computePosRingCircle(scip, elements, nelements, rexts, xs, ys, i, ispacked, rmax, rbounding, &bestx,
1793  &besty, ncalls);
1794  else
1795  computePosRectangleCircle(scip, elements, nelements, rexts, xs, ys, i, ispacked, rmax, width, height, &bestx,
1796  &besty, ncalls);
1797 
1798  /* consider circles that have been packed already */
1799  computePosCircleCircle(scip, elements, nelements, rexts, xs, ys, i, ispacked, rmax, rbounding, width, height,
1800  patterntype, &bestx, &besty, ncalls);
1801 
1802  /* pack circle if a possible position has been found */
1803  if( bestx != SCIP_INVALID && besty != SCIP_INVALID ) /*lint !e777*/
1804  {
1805  assert(!ispacked[i]);
1806  ispacked[i] = TRUE;
1807  xs[i] = bestx;
1808  ys[i] = besty;
1809  ++(*npacked);
1810  added = TRUE;
1811  }
1812  }
1813  }
1814 
1815  return;
1816 }
1817 
1818 /** verifies a circular pattern heuristically */
1820  SCIP* scip, /**< SCIP data structure */
1821  SCIP_PROBDATA* probdata, /**< problem data */
1822  SCIP_PATTERN* pattern, /**< pattern */
1823  SCIP_Real timelim, /**< time limit */
1824  int iterlim /**< iteration limit */
1825  )
1826 {
1827  SCIP_Real* rexts;
1828  SCIP_Real* rints;
1829  SCIP_Real* scores;
1830  SCIP_Real* xs;
1831  SCIP_Real* ys;
1832  SCIP_Bool* ispacked;
1833  int* elements;
1834  int* pos;
1835  SCIP_Real timestart;
1836  int nelements;
1837  int niters;
1838  int type;
1839  int i;
1840 
1841  assert(probdata != NULL);
1842  assert(pattern != NULL);
1843  assert(iterlim > 0);
1846  assert(SCIPpatternGetCircleType(pattern) < SCIPprobdataGetNTypes(probdata));
1847 
1848  /* check whether there is any time left */
1849  if( timelim <= 0.0 )
1850  return SCIP_OKAY;
1851 
1852  rexts = SCIPprobdataGetRexts(probdata);
1853  rints = SCIPprobdataGetRints(probdata);
1854  nelements = SCIPpatternGetNElemens(pattern);
1855  type = SCIPpatternGetCircleType(pattern);
1856  assert(type >= 0 && type < SCIPprobdataGetNTypes(probdata));
1857 
1858  /* pattern is empty -> set status to packable */
1859  if( SCIPpatternGetNElemens(pattern) == 0 )
1860  {
1862  SCIPcheckPattern(scip, probdata, pattern);
1863  return SCIP_OKAY;
1864  }
1865 
1866  /* pattern contains only one element -> compare radii */
1867  if( SCIPpatternGetNElemens(pattern) == 1 )
1868  {
1869  int elemtype;
1870 
1871  elemtype = SCIPpatternGetElementType(pattern, 0);
1872  assert(elemtype >= 0 && elemtype < SCIPprobdataGetNTypes(probdata));
1873 
1874  /* check whether element fits into the circular pattern */
1875  if( SCIPisGE(scip, rints[type], rexts[elemtype]) )
1876  {
1877  SCIPpatternSetElementPos(pattern, 0, rexts[elemtype]-rints[type], 0.0);
1879  }
1880  else
1882 
1883  SCIPcheckPattern(scip, probdata, pattern);
1884  return SCIP_OKAY;
1885  }
1886 
1887  timestart = SCIPgetTotalTime(scip);
1888  niters = 0;
1889 
1890  /* store elements in a separate array; remember positions of elements in the pattern */
1891  SCIP_CALL( SCIPallocBufferArray(scip, &pos, nelements) );
1892  SCIP_CALL( SCIPallocBufferArray(scip, &scores, nelements) );
1893  SCIP_CALL( SCIPallocBufferArray(scip, &ispacked, nelements) );
1894  SCIP_CALL( SCIPallocBufferArray(scip, &elements, nelements) );
1895  SCIP_CALL( SCIPallocBufferArray(scip, &xs, nelements) );
1896  SCIP_CALL( SCIPallocBufferArray(scip, &ys, nelements) );
1897  for( i = 0; i < nelements; ++i )
1898  {
1899  elements[i] = SCIPpatternGetElementType(pattern, i);
1900  ispacked[i] = FALSE;
1901  pos[i] = i;
1902  }
1903 
1904  /* main loop for calling heuristic verification */
1906  && niters < iterlim
1907  && SCIPgetTotalTime(scip) - timestart <= timelim )
1908  {
1909  int npacked;
1910 
1911  /* compute scores depending on iteration counter */
1912  computeScores(scip, probdata, elements, nelements, scores, niters);
1913 
1914  /* sort elements in non-increasing order */
1915  SCIPsortDownRealIntInt(scores, elements, pos, nelements);
1916 
1917  /* call heuristic */
1918  SCIPpackCirclesGreedy(scip, rexts, xs, ys, rints[type], SCIPprobdataGetWidth(probdata),
1919  SCIPprobdataGetHeight(probdata), ispacked, elements, nelements, SCIP_PATTERNTYPE_CIRCULAR, &npacked, niters);
1920 
1921  /* check whether all elements could have been packed */
1922  if( npacked == nelements )
1923  {
1924  for( i = 0; i < nelements; ++i )
1925  {
1926  assert(elements[i] == SCIPpatternGetElementType(pattern, pos[i]));
1927  SCIPpatternSetElementPos(pattern, pos[i], xs[i], ys[i]);
1928  }
1930 
1931  SCIPdebugMsg(scip, "heuristic verified pattern after %d iterations\n", niters + 1);
1932  }
1933 
1934  ++niters;
1935  }
1936 
1937  SCIPcheckPattern(scip, probdata, pattern);
1938 
1939  /* free memory */
1940  SCIPfreeBufferArray(scip, &ys);
1941  SCIPfreeBufferArray(scip, &xs);
1942  SCIPfreeBufferArray(scip, &elements);
1943  SCIPfreeBufferArray(scip, &ispacked);
1944  SCIPfreeBufferArray(scip, &scores);
1945  SCIPfreeBufferArray(scip, &pos);
1946 
1947  return SCIP_OKAY;
1948 }
1949 
1950 /** verifies a circular pattern via a verification NLP */
1952  SCIP* scip, /**< SCIP data structure */
1953  SCIP_PROBDATA* probdata, /**< problem data */
1954  SCIP_PATTERN* pattern, /**< pattern */
1955  SCIP_Real timelim, /**< time limit */
1956  SCIP_Longint nodelim /**< node limit */
1957  )
1958 {
1959  SCIP* subscip;
1960  SCIP_CONS* cons;
1961  SCIP_VAR** xvars;
1962  SCIP_VAR** yvars;
1963  SCIP_VAR* quadvars1[6];
1964  SCIP_VAR* quadvars2[6];
1965  SCIP_Real quadcoefs[6];
1966  SCIP_Real* rexts;
1967  SCIP_Real* rints;
1968  char name[SCIP_MAXSTRLEN];
1969  int nelems;
1970  int type;
1971  int k;
1972 
1973  assert(probdata != NULL);
1974  assert(pattern != NULL);
1977 
1978  /* check whether there is any time left */
1979  if( timelim <= 0.0 )
1980  return SCIP_OKAY;
1981 
1982  rexts = SCIPprobdataGetRexts(probdata);
1983  rints = SCIPprobdataGetRints(probdata);
1984  type = SCIPpatternGetCircleType(pattern);
1985  nelems = SCIPpatternGetNElemens(pattern);
1986 
1987  /* set up the sub-SCIP */
1988  SCIP_CALL( SCIPcreate(&subscip) );
1989  SCIP_CALL( SCIPcreateProbBasic(subscip, "verify") );
1991 
1992  /* allocate memory for (x,y) variables */
1993  SCIP_CALL( SCIPallocBufferArray(scip, &xvars, nelems) );
1994  SCIP_CALL( SCIPallocBufferArray(scip, &yvars, nelems) );
1995 
1996  /* set feasibility emphasis settings */
1998 
1999  /* set working limit */
2000  SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
2001  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelim) );
2002  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelim) );
2003 
2004 #ifndef SCIP_DEBUG
2005  SCIPsetMessagehdlrQuiet(subscip, TRUE);
2006 #endif
2007 
2008  /* create (x,y) variables */
2009  for( k = 0; k < nelems; ++k )
2010  {
2011  int elemtype;
2012 
2013  elemtype = SCIPpatternGetElementType(pattern, k);
2014  assert(elemtype >= 0 && elemtype < SCIPprobdataGetNTypes(probdata));
2015 
2016  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "x_%d", k);
2017  SCIP_CALL( SCIPcreateVarBasic(subscip, &xvars[k], name, rexts[elemtype] - rints[type],
2018  rints[type] - rexts[elemtype], 0.0, SCIP_VARTYPE_CONTINUOUS) );
2019  SCIP_CALL( SCIPaddVar(subscip, xvars[k]) );
2020 
2021  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "y_%d", k);
2022  SCIP_CALL( SCIPcreateVarBasic(subscip, &yvars[k], name, rexts[elemtype] - rints[type],
2023  rints[type] - rexts[elemtype], 1.0, SCIP_VARTYPE_CONTINUOUS) );
2024  SCIP_CALL( SCIPaddVar(subscip, yvars[k]) );
2025  }
2026 
2027  /* create non-overlapping constraints */
2028  for( k = 0; k < nelems; ++k )
2029  {
2030  int elemtype1;
2031  int l;
2032 
2033  elemtype1 = SCIPpatternGetElementType(pattern, k);
2034  assert(elemtype1 >= 0 && elemtype1 < SCIPprobdataGetNTypes(probdata));
2035 
2036  for( l = k + 1; l < nelems; ++l )
2037  {
2038  int elemtype2;
2039 
2040  elemtype2 = SCIPpatternGetElementType(pattern, l);
2041  assert(elemtype2 >= 0 && elemtype2 < SCIPprobdataGetNTypes(probdata));
2042 
2043  quadvars1[0] = xvars[k]; quadvars2[0] = xvars[k]; quadcoefs[0] = 1.0;
2044  quadvars1[1] = xvars[k]; quadvars2[1] = xvars[l]; quadcoefs[1] = -2.0;
2045  quadvars1[2] = xvars[l]; quadvars2[2] = xvars[l]; quadcoefs[2] = 1.0;
2046  quadvars1[3] = yvars[k]; quadvars2[3] = yvars[k]; quadcoefs[3] = 1.0;
2047  quadvars1[4] = yvars[k]; quadvars2[4] = yvars[l]; quadcoefs[4] = -2.0;
2048  quadvars1[5] = yvars[l]; quadvars2[5] = yvars[l]; quadcoefs[5] = 1.0;
2049 
2050  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "over_%d_%d", k, l);
2051  SCIP_CALL( SCIPcreateConsQuadraticNonlinear(subscip, &cons, name, 0, NULL, NULL, 6, quadvars1, quadvars2,
2052  quadcoefs, SQR(rexts[elemtype1] + rexts[elemtype2]), SCIPinfinity(subscip),
2053  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
2054 
2055  SCIP_CALL( SCIPaddCons(subscip, cons) );
2056  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
2057  }
2058  }
2059 
2060  /* create non-overlapping constraints with outer ring */
2061  for( k = 0; k < nelems; ++k )
2062  {
2063  int elemtype;
2064 
2065  elemtype = SCIPpatternGetElementType(pattern, k);
2066  assert(elemtype >= 0 && elemtype < SCIPprobdataGetNTypes(probdata));
2067 
2068  quadvars1[0] = xvars[k]; quadvars2[0] = xvars[k]; quadcoefs[0] = 1.0;
2069  quadvars1[1] = yvars[k]; quadvars2[1] = yvars[k]; quadcoefs[1] = 1.0;
2070 
2071  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "bound_%d", k);
2072  SCIP_CALL( SCIPcreateConsQuadraticNonlinear(subscip, &cons, name, 0, NULL, NULL, 2, quadvars1, quadvars2, quadcoefs,
2073  0.0, SQR(rints[type] - rexts[elemtype]),
2074  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
2075 
2076  SCIP_CALL( SCIPaddCons(subscip, cons) );
2077  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
2078  }
2079 
2080  /* sort circles in x direction if they have the same type */
2081  for( k = 0; k < nelems - 1; ++k )
2082  {
2083  int elemtype1;
2084  int l;
2085 
2086  elemtype1 = SCIPpatternGetElementType(pattern, k);
2087  assert(elemtype1 >= 0 && elemtype1 < SCIPprobdataGetNTypes(probdata));
2088 
2089  for( l = k + 1; l < nelems; ++l )
2090  {
2091  int elemtype2;
2092 
2093  elemtype2 = SCIPpatternGetElementType(pattern, k+1);
2094  assert(elemtype2 >= 0 && elemtype2 < SCIPprobdataGetNTypes(probdata));
2095 
2096  if( elemtype1 != elemtype2 )
2097  continue;
2098 
2099  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sortx_%d_%d", k, l);
2100  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &cons, name, 0, NULL, NULL, -SCIPinfinity(subscip), 0.0) );
2101  SCIP_CALL( SCIPaddCoefLinear(subscip, cons, xvars[k], 1.0) );
2102  SCIP_CALL( SCIPaddCoefLinear(subscip, cons, xvars[l], -1.0) );
2103 
2104  SCIP_CALL( SCIPaddCons(subscip, cons) );
2105  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
2106  }
2107  }
2108 
2109  /* solve verification NLP */
2110  SCIPdebugMsg(scip, "--------------------- SOLVE VERIFICATION NLP -------------------\n");
2111  SCIP_CALL( SCIPsolve(subscip) );
2112  SCIPdebugMsg(scip, "----------------------------------------------------------------\n");
2113 
2114  SCIPdebugMsg(scip, "result of verification NLP: nsols=%d solstat=%d\n",
2115  SCIPgetNSols(subscip), SCIPgetStatus(subscip));
2116 
2117  /* check whether a solution could be found or whether the problem is proven to be infeasible */
2118  if( SCIPgetNSols(subscip) > 0 )
2119  {
2121 
2122  for( k = 0; k < nelems; ++k )
2123  {
2124  SCIP_Real solx = SCIPgetSolVal(subscip, SCIPgetBestSol(subscip), xvars[k]);
2125  SCIP_Real soly = SCIPgetSolVal(subscip, SCIPgetBestSol(subscip), yvars[k]);
2126 
2127  SCIPpatternSetElementPos(pattern, k, solx, soly);
2128  }
2129 
2130  SCIPcheckPattern(scip, probdata, pattern);
2131  }
2132  else if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE )
2134 
2135  /* free all variables */
2136  for( k = 0; k < nelems; ++k )
2137  {
2138  SCIP_CALL( SCIPreleaseVar(subscip, &yvars[k]) );
2139  SCIP_CALL( SCIPreleaseVar(subscip, &xvars[k]) );
2140  }
2141 
2142  /* free memory */
2143  SCIPfreeBufferArray(scip, &yvars);
2144  SCIPfreeBufferArray(scip, &xvars);
2145  SCIP_CALL( SCIPfree(&subscip) );
2146 
2147  return SCIP_OKAY;
2148 }
2149 
2150 /** check a pattern for consistency */
2152  SCIP* scip, /**< SCIP data structure */
2153  SCIP_PROBDATA* probdata, /**< problem data */
2154  SCIP_PATTERN* pattern /**< pattern */
2155  )
2156 { /*lint --e{715}*/
2157 #ifndef NDEBUG
2158  SCIP_Real* rexts;
2159  SCIP_Real* rints;
2160  SCIP_Real width;
2161  SCIP_Real height;
2162  int i;
2163 
2164  assert(probdata != NULL);
2165  assert(pattern != NULL);
2166 
2167  rexts = SCIPprobdataGetRexts(probdata);
2168  rints = SCIPprobdataGetRints(probdata);
2169  width = SCIPprobdataGetWidth(probdata);
2170  height = SCIPprobdataGetHeight(probdata);
2171 
2172  /* check types */
2173  for( i = 0; i < SCIPpatternGetNElemens(pattern); ++i )
2174  {
2175  int type = SCIPpatternGetElementType(pattern, i);
2176 
2177  assert(type >= 0);
2178  assert(type < SCIPprobdataGetNTypes(probdata));
2179  }
2180 
2181  /* check positions iff packable */
2183  return;
2184 
2185  for( i = 0; i < SCIPpatternGetNElemens(pattern); ++i )
2186  {
2187  SCIP_Real xi = SCIPpatternGetElementPosX(pattern, i);
2188  SCIP_Real yi = SCIPpatternGetElementPosY(pattern, i);
2189  int typei = SCIPpatternGetElementType(pattern, i);
2190  int j;
2191 
2192  /* check distance between circles */
2193  for( j = i + 1; j < SCIPpatternGetNElemens(pattern); ++j )
2194  {
2195  SCIP_Real xj = SCIPpatternGetElementPosX(pattern, j);
2196  SCIP_Real yj = SCIPpatternGetElementPosY(pattern, j);
2197  int typej = SCIPpatternGetElementType(pattern, j);
2198 
2199  assert(SCIPisFeasGE(scip, sqrt(SQR(xi - xj) + SQR(yi - yj)), rexts[typei] + rexts[typej]));
2200  }
2201 
2202  /* check distance to boundary */
2204  {
2205  SCIP_Real distance = sqrt(SQR(xi) + SQR(yi));
2206  int patterntype = SCIPpatternGetCircleType(pattern);
2207 
2208  assert(patterntype >= 0);
2209  assert(patterntype < SCIPprobdataGetNTypes(probdata));
2210  assert(SCIPisFeasLE(scip, distance, rints[patterntype] - rexts[typei]));
2211  }
2212  else
2213  {
2214  assert(SCIPisFeasGE(scip, xi, rexts[typei]));
2215  assert(SCIPisFeasLE(scip, xi, width - rexts[typei]));
2216  assert(SCIPisFeasGE(scip, yi, rexts[typei]));
2217  assert(SCIPisFeasLE(scip, yi, height - rexts[typei]));
2218  }
2219  }
2220 #endif
2221 }
2222 
2223 /**@} */
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define TABLE_NAME_RPA
Definition: probdata_rpa.c:59
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_RETCODE SCIPpatternAddElement(SCIP_PATTERN *pattern, int type, SCIP_Real x, SCIP_Real y)
Definition: pattern.c:182
void SCIPsortDownRealIntInt(SCIP_Real *realarray, int *intarray1, int *intarray2, int len)
SCIP_RETCODE SCIPincludeTable(SCIP *scip, const char *name, const char *desc, SCIP_Bool active, SCIP_DECL_TABLECOPY((*tablecopy)), SCIP_DECL_TABLEFREE((*tablefree)), SCIP_DECL_TABLEINIT((*tableinit)), SCIP_DECL_TABLEEXIT((*tableexit)), SCIP_DECL_TABLEINITSOL((*tableinitsol)), SCIP_DECL_TABLEEXITSOL((*tableexitsol)), SCIP_DECL_TABLEOUTPUT((*tableoutput)), SCIP_TABLEDATA *tabledata, int position, SCIP_STAGE earlieststage)
Definition: scip_table.c:56
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPpatternCopy(SCIP *scip, SCIP_PATTERN *pattern, SCIP_PATTERN **copy)
Definition: pattern.c:152
#define TABLE_DESC_RPA
Definition: probdata_rpa.c:60
static void computePosRingCircle(SCIP *scip, int *elements, int nelements, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, int pos, SCIP_Bool *ispacked, SCIP_Real rmax, SCIP_Real rbound, SCIP_Real *bestx, SCIP_Real *besty, int ncalls)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
#define SCIP_MAXSTRLEN
Definition: def.h:288
void SCIPcheckPattern(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
#define SQR(x)
Definition: def.h:214
static SCIP_DECL_PROBDELTRANS(probdeltransRingpacking)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Problem data for ringpacking problem.
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1250
SCIP_TABLE * SCIPfindTable(SCIP *scip, const char *name)
Definition: scip_table.c:94
SCIP_RETCODE SCIPpricerRpaActivate(SCIP *scip)
Definition: pricer_rpa.c:969
enum SCIP_Packable SCIP_PACKABLE
Definition: pattern.h:47
enum SCIP_Patterntype SCIP_PATTERNTYPE
Definition: pattern.h:54
SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
Definition: scip_cons.c:1626
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define M_PI
Definition: probdata_rpa.c:65
int * SCIPprobdataGetDemands(SCIP_PROBDATA *probdata)
#define FALSE
Definition: def.h:94
void SCIPprobdataInvalidateDualbound(SCIP *scip, SCIP_PROBDATA *probdata)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
int SCIPpatternGetCircleType(SCIP_PATTERN *pattern)
Definition: pattern.c:309
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_RETCODE SCIPsetProbData(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: scip_prob.c:1014
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:194
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPdebugMessage
Definition: pub_message.h:96
static SCIP_DECL_PROBDELORIG(probdelorigRingpacking)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPpatternGetNElemens(SCIP_PATTERN *pattern)
Definition: pattern.c:215
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *probname, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int ntypes, SCIP_Real width, SCIP_Real height)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_VAR ** x
Definition: circlepacking.c:63
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
static void computePosCircleCircle(SCIP *scip, int *elements, int nelements, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, int pos, SCIP_Bool *ispacked, SCIP_Real rmax, SCIP_Real rbound, SCIP_Real width, SCIP_Real height, SCIP_PATTERNTYPE patterntype, SCIP_Real *bestx, SCIP_Real *besty, int ncalls)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:180
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPtransformVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1391
SCIP_Bool SCIPprobdataIsDualboundInvalid(SCIP_PROBDATA *probdata)
static void computePosRectangleCircle(SCIP *scip, int *elements, int nelements, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, int pos, SCIP_Bool *ispacked, SCIP_Real rmax, SCIP_Real width, SCIP_Real height, SCIP_Real *bestx, SCIP_Real *besty, int ncalls)
void SCIPpatternCapture(SCIP_PATTERN *pattern)
Definition: pattern.c:116
int SCIPpatternCountElements(SCIP_PATTERN *pattern, int type)
Definition: pattern.c:237
void SCIPpatternRemoveLastElements(SCIP_PATTERN *pattern, int k)
Definition: pattern.c:203
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_PACKABLE SCIPpatternGetPackableStatus(SCIP_PATTERN *pattern)
Definition: pattern.c:335
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1242
void SCIPprobdataGetRInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***rpatterns, SCIP_VAR ***rvars, int *nrpatterns)
static int isPatternDominating(SCIP_PATTERN *p, SCIP_PATTERN *q, int *count, int ntypes)
Definition: probdata_rpa.c:471
void SCIPpackCirclesGreedy(SCIP *scip, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real rbounding, SCIP_Real width, SCIP_Real height, SCIP_Bool *ispacked, int *elements, int nelements, SCIP_PATTERNTYPE patterntype, int *npacked, int ncalls)
SCIP_RETCODE SCIPsetObjIntegral(SCIP *scip)
Definition: scip_prob.c:1519
int SCIPprobdataGetNTypes(SCIP_PROBDATA *probdata)
SCIP_Real SCIPprobdataGetHeight(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2486
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPverifyCircularPatternHeuristic(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, int iterlim)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
SCIP_RETCODE SCIPcreateConsQuadraticNonlinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)
SCIP_CONS ** SCIPprobdataGetPatternConss(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
#define SCIP_CALL(x)
Definition: def.h:380
int SCIPpatternGetElementType(SCIP_PATTERN *pattern, int i)
Definition: pattern.c:225
SCIP_VAR * h
Definition: circlepacking.c:68
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip_param.c:882
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void computeScores(SCIP *scip, SCIP_PROBDATA *probdata, int *elements, int nelements, SCIP_Real *scores, int iter)
SCIP_RETCODE SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
Definition: scip_param.c:288
void SCIPpatternSetElementPos(SCIP_PATTERN *pattern, int elem, SCIP_Real x, SCIP_Real y)
Definition: pattern.c:281
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
static SCIP_RETCODE setupProblem(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:722
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPsetProbTrans(SCIP *scip, SCIP_DECL_PROBTRANS((*probtrans)))
Definition: scip_prob.c:221
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
SCIP_Real SCIPpatternGetElementPosX(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:257
void SCIPsetMessagehdlrQuiet(SCIP *scip, SCIP_Bool quiet)
Definition: scip_message.c:108
static SCIP_RETCODE probdataCreate(SCIP *scip, SCIP_PROBDATA **probdata, SCIP_CONS **patternconss, SCIP_PATTERN **cpatterns, SCIP_VAR **cvars, int ncpatterns, SCIP_PATTERN **rpatterns, SCIP_VAR **rvars, int nrpatterns, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int ntypes, SCIP_Real width, SCIP_Real height)
Definition: probdata_rpa.c:125
#define MIN(x, y)
Definition: def.h:243
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_RETCODE SCIPupdateLocalDualbound(SCIP *scip, SCIP_Real newbound)
Definition: scip_prob.c:3646
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
SCIP_RETCODE SCIPpatternCreateRectangular(SCIP *scip, SCIP_PATTERN **pattern)
Definition: pattern.c:107
SCIP_Real SCIPprobdataGetWidth(SCIP_PROBDATA *probdata)
static SCIP_RETCODE createPatternVars(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:339
#define BMSclearMemory(ptr)
Definition: memory.h:129
static SCIP_RETCODE enumeratePatterns(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, int *ms, int *nselected, SCIP_Real nlptilim, SCIP_Real heurtilim, SCIP_Longint nlpnodelim, int heuriterlim, SCIP_Real *timeleft)
Definition: probdata_rpa.c:594
static void computePosTrivial(SCIP *scip, int *elements, int nelements, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, int pos, SCIP_Bool *ispacked, SCIP_Real rmax, SCIP_Real rbound, SCIP_Real width, SCIP_Real height, SCIP_PATTERNTYPE patterntype, SCIP_Real *bestx, SCIP_Real *besty, int ncalls)
SCIP_PATTERNTYPE SCIPpatternGetPatternType(SCIP_PATTERN *pattern)
Definition: pattern.c:296
void SCIPprobdataGetCInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***cpatterns, SCIP_VAR ***cvars, int *ncpatterns)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
#define TABLE_POSITION_RPA
Definition: probdata_rpa.c:61
SCIP_Real SCIPpatternGetElementPosY(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:269
SCIP_VAR ** b
Definition: circlepacking.c:65
#define MAX(x, y)
Definition: def.h:239
SCIP_RETCODE SCIPverifyCircularPatternNLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, SCIP_Longint nodelim)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void updateBestCandidate(SCIP *scip, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real *rexts, SCIP_Real rext, SCIP_Real rbounding, SCIP_Real wbounding, SCIP_Real hbounding, SCIP_Real rmax, SCIP_PATTERNTYPE patterntype, SCIP_Bool *ispacked, int *elements, int nelements, SCIP_Real *bestx, SCIP_Real *besty, SCIP_Real x, SCIP_Real y, int ncalls)
Definition: probdata_rpa.c:965
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:53
void SCIPprobdataUpdateDualbound(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real dualbound)
SCIP_RETCODE SCIPpatternCreateCircular(SCIP *scip, SCIP_PATTERN **pattern, int type)
Definition: pattern.c:97
void SCIPpatternRelease(SCIP *scip, SCIP_PATTERN **pattern)
Definition: pattern.c:126
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:964
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
#define TABLE_EARLIEST_STAGE_RPA
Definition: probdata_rpa.c:62
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1216
#define SCIP_Real
Definition: def.h:173
static SCIP_RETCODE probdataFree(SCIP *scip, SCIP_PROBDATA **probdata)
Definition: probdata_rpa.c:208
SCIP_VAR ** y
Definition: circlepacking.c:64
SCIP_RETCODE SCIPprobdataEnumeratePatterns(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real nlptilim, SCIP_Real heurtilim, SCIP_Real totaltilim, SCIP_Longint nlpnodelim, int heuriterlim)
void SCIPpatternSetPackableStatus(SCIP_PATTERN *pattern, SCIP_PACKABLE packable)
Definition: pattern.c:345
static int getNCPatterns(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PACKABLE status)
Definition: probdata_rpa.c:283
#define SCIP_INVALID
Definition: def.h:193
SCIP_RETCODE SCIPsetConsModifiable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool modifiable)
Definition: scip_cons.c:1425
static SCIP_RETCODE ensureSize(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERNTYPE type, int size)
Definition: probdata_rpa.c:305
#define SCIP_Longint
Definition: def.h:158
void SCIPpatternSetType(SCIP_PATTERN *pattern, int type)
Definition: pattern.c:323
SCIP_Real SCIPgetTotalTime(SCIP *scip)
Definition: scip_timing.c:351
static SCIP_RETCODE filterPatterns(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:523
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetProbDeltrans(SCIP *scip, SCIP_DECL_PROBDELTRANS((*probdeltrans)))
Definition: scip_prob.c:242
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
static SCIP_DECL_PROBTRANS(probtransRingpacking)
SCIP_RETCODE SCIPsetProbDelorig(SCIP *scip, SCIP_DECL_PROBDELORIG((*probdelorig)))
Definition: scip_prob.c:200
Ringpacking variable pricer.
SCIP_RETCODE SCIPprobdataSetupProblem(SCIP *scip)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPprobdataAddVar(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_VAR *var)
SCIP_Real * SCIPprobdataGetRints(SCIP_PROBDATA *probdata)
static int maxCircles(SCIP *scip, SCIP_PROBDATA *probdata, int type, int elemtype)
Definition: probdata_rpa.c:416
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
default SCIP plugins
static SCIP_DECL_TABLEOUTPUT(tableOutputRpa)
Definition: probdata_rpa.c:901
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP callable library.
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339