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