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-2020 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  probdata->nrpatterns);
751 
752  /* create initial rectangular patterns */
753  for( t = 0; t < ntypes; ++t )
754  {
755  SCIP_PATTERN* pattern;
756 
757  /* create a pattern containing a single circle of type t; set position of the circle to the left-bottom */
758  SCIP_CALL( SCIPpatternCreateRectangular(scip, &pattern) );
759  SCIP_CALL( SCIPpatternAddElement(pattern, t, rexts[t], rexts[t]) );
761 
762  /* add and release pattern */
763  SCIP_CALL( SCIPprobdataAddVar(scip, probdata, pattern, NULL) );
764  SCIPpatternRelease(scip, &pattern);
765  }
766 
767  /* create variables for all existing patterns */
768  SCIP_CALL( createPatternVars(scip, probdata) );
769 
770  /* create demand constraints */
771  for( t = 0; t < ntypes; ++t )
772  {
773  SCIP_CONS* cons;
774 
775  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "demand_%d", t);
776  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name, 0, NULL, NULL, (SCIP_Real)demands[t], SCIPinfinity(scip) ) );
777 
778  for( p = 0; p < probdata->ncpatterns; ++p )
779  {
780  SCIP_PATTERN* pattern;
781  SCIP_VAR* var;
782 
783  pattern = probdata->cpatterns[p];
784  assert(pattern != NULL);
786 
787  var = probdata->cvars[p];
788  assert(var != NULL);
789 
790  /* add coefficient to the pattern if the pattern is of type t */
791  if(SCIPpatternGetCircleType(pattern) == t )
792  {
793  SCIP_CALL( SCIPaddCoefLinear(scip, cons, var, 1.0) );
794  }
795  }
796 
797  /* add and release constraint */
798  SCIP_CALL( SCIPaddCons(scip, cons) );
799  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
800  }
801 
802  /* create pattern constraints */
803  for( t = 0; t < ntypes; ++t )
804  {
805  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "patterncons_%d", t);
806  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &probdata->patternconss[t], name, 0, NULL, NULL, 0.0,
807  SCIPinfinity(scip) ) );
808 
809  /* declare constraint modifiable for adding variables during pricing */
810  SCIP_CALL( SCIPsetConsModifiable(scip, probdata->patternconss[t], TRUE) );
811  SCIP_CALL( SCIPaddCons(scip, probdata->patternconss[t]) );
812  }
813 
814  /* add coefficients for circular patterns */
815  for( p = 0; p < probdata->ncpatterns; ++p )
816  {
817  SCIP_PATTERN* pattern = probdata->cpatterns[p];
818  SCIP_VAR* var = probdata->cvars[p];
819  int type;
820 
821  assert(pattern != NULL);
823  assert(var != NULL);
824 
825  type = SCIPpatternGetCircleType(pattern);
826  assert(type >= 0 && type < ntypes);
827 
828  /* - z_C */
829  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->patternconss[type], var, -1.0) );
830 
831  for( t = 0; t < ntypes; ++t )
832  {
833  int nelems = SCIPpatternCountElements(pattern, t);
834 
835  if( nelems > 0 )
836  {
837  /* + P_t z_C */
838  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->patternconss[t], var, (SCIP_Real)nelems) );
839  }
840  }
841  }
842 
843  /* add coefficients for rectangular patterns */
844  for( p = 0; p < probdata->nrpatterns; ++p )
845  {
846  SCIP_PATTERN* pattern = probdata->rpatterns[p];
847  SCIP_VAR* var = probdata->rvars[p];
848 
849  assert(pattern != NULL);
851  assert(var != NULL);
852 
853  for( t = 0; t < ntypes; ++t )
854  {
855  int nelems = SCIPpatternCountElements(pattern, t);
856 
857  if( nelems > 0 )
858  {
859  /* + P_t z_P */
860  SCIP_CALL( SCIPaddCoefLinear(scip, probdata->patternconss[t], var, (SCIP_Real)nelems) );
861  }
862  }
863  }
864 
865  /* compute an initial dual bound by considering the volume of all rings */
866  minrext = rexts[ntypes-1];
867  volume = 0.0;
868  for( t = 0; t < ntypes; ++t )
869  {
870  SCIP_Real vol;
871 
872  /* consider ring as circle if there is no ring with a smaller radius than than inner one */
873  if( SCIPisFeasLT(scip, rints[t], minrext) )
874  vol = M_PI * SQR(rexts[t]);
875  else
876  vol = M_PI * (SQR(rexts[t]) - SQR(rints[t]));
877 
878  volume += vol * demands[t];
879  }
880 
881  /* update initial dual bound */
882  dualbound = SCIPfeasCeil(scip, volume / (SCIPprobdataGetWidth(probdata) * SCIPprobdataGetHeight(probdata)));
883  SCIP_CALL( SCIPupdateLocalDualbound(scip, dualbound) );
884  SCIPinfoMessage(scip, NULL, "+++++++++++++ volume-based bound = ceil(%g / %g) = %g\n", volume,
885  SCIPprobdataGetWidth(probdata) * SCIPprobdataGetHeight(probdata), dualbound);
886  SCIPprobdataUpdateDualbound(scip, probdata, dualbound);
887 
888  return SCIP_OKAY;
889 }
890 
891 /** output method of statistics table to output file stream 'file' */
892 static
893 SCIP_DECL_TABLEOUTPUT(tableOutputRpa)
894 { /*lint --e{715}*/
895  SCIP_PROBDATA* probdata;
896  SCIP_Real* rexts;
897  SCIP_Real* rints;
898  SCIP_Real dualbound;
899  SCIP_Real maxrint;
900  SCIP_Real minrext;
901  int* demands;
902  int ntypes;
903  int nrings;
904  int t;
905 
906  probdata = SCIPgetProbData(scip);
907  assert(probdata != NULL);
908 
909  ntypes = SCIPprobdataGetNTypes(probdata);
910  demands = SCIPprobdataGetDemands(probdata);
911  rexts = SCIPprobdataGetRexts(probdata);
912  rints = SCIPprobdataGetRints(probdata);
913  nrings = 0;
914  maxrint = 0.0;
915  minrext = SCIPinfinity(scip);
916 
917  /* use global dual bound if it is still valid */
918  if( !probdata->isdualinvalid )
919  {
920  assert(SCIPisGE(scip, SCIPgetDualbound(scip), probdata->dualbound));
921  dualbound = SCIPgetDualbound(scip);
922  }
923  else
924  dualbound = probdata->dualbound;
925 
926  /* count the number of rings */
927  for( t = 0; t < ntypes; ++t )
928  {
929  nrings += demands[t];
930  maxrint = MAX(maxrint, rints[t]);
931  minrext = MIN(minrext, rexts[t]);
932  }
933 
934  SCIPinfoMessage(scip, file, "Ringpacking : %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s\n",
935  "dual", "ntypes", "nrings", "width", "height", "CP", "CP_unk", "CP_unk_end" ,"CP_infeas", "RP", "enumtime", "radiiratio");
936 
937  SCIPinfoMessage(scip, file, " %-17s:", "");
938  SCIPinfoMessage(scip, file, " %10.2f", dualbound);
939  SCIPinfoMessage(scip, file, " %10d", ntypes);
940  SCIPinfoMessage(scip, file, " %10d", nrings);
941  SCIPinfoMessage(scip, file, " %10.2f", SCIPprobdataGetWidth(probdata));
942  SCIPinfoMessage(scip, file, " %10.2f", SCIPprobdataGetHeight(probdata));
943  SCIPinfoMessage(scip, file, " %10d", probdata->ncpatterns);
944  SCIPinfoMessage(scip, file, " %10d", probdata->ncppatternsunknownbeg);
945  SCIPinfoMessage(scip, file, " %10d", getNCPatterns(scip, probdata, SCIP_PACKABLE_UNKNOWN));
946  SCIPinfoMessage(scip, file, " %10d", getNCPatterns(scip, probdata, SCIP_PACKABLE_NO));
947  SCIPinfoMessage(scip, file, " %10d", probdata->nrpatterns);
948  SCIPinfoMessage(scip, file, " %10.2f", probdata->enumtime);
949  SCIPinfoMessage(scip, file, " %10.1f", maxrint / minrext);
950  SCIPinfoMessage(scip, file, "\n");
951 
952  return SCIP_OKAY;
953 }
954 
955 /** auxiliary function to update the best known candidate */
956 static
958  SCIP* scip, /**< SCIP data structure */
959  SCIP_Real* xs, /**< x-coordinates of packed elements */
960  SCIP_Real* ys, /**< y-coordinates of packed elements */
961  SCIP_Real* rexts, /**< radii of packed elements */
962  SCIP_Real rext, /**< radii of element that should be packed */
963  SCIP_Real rbounding, /**< inner radius of bounding circle (ignored for rectangular patterns) */
964  SCIP_Real wbounding, /**< width of bounding rectangular (ignored for circular patterns) */
965  SCIP_Real hbounding, /**< height of bounding rectangular (ignored for circular patterns) */
966  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
967  SCIP_PATTERNTYPE patterntype, /**< pattern type */
968  SCIP_Bool* ispacked, /**< array indicating which elements are already packed */
969  int* elements, /**< the order of the elements in the pattern */
970  int nelements, /**< the total number of elements */
971  SCIP_Real* bestx, /**< buffer to update best x-coordinate */
972  SCIP_Real* besty, /**< buffer to update best y-coordinate */
973  SCIP_Real x, /**< x-coordinate of a candidate point */
974  SCIP_Real y, /**< y-coordinate of a candidate point */
975  int ncalls /**< total number of calls of the packing heuristic */
976  )
977 {
978  SCIP_Real threshold;
979  SCIP_Bool isoverthreshold;
980  int i;
981 
982  /* candidate is not valid -> skip */
983  if( x == SCIP_INVALID || y == SCIP_INVALID ) /*lint !e777*/
984  return;
985 
986  /* check whether there is an intersection with the boundary */
987  if( patterntype == SCIP_PATTERNTYPE_CIRCULAR )
988  {
989  if( SCIPisGT(scip, x*x + y*y, SQR(rbounding - rext)) )
990  return;
991  }
992  else
993  {
994  if( SCIPisLT(scip, x, rext) || SCIPisGT(scip, x, wbounding - rext)
995  || SCIPisLT(scip, y, rext) || SCIPisGT(scip, y, hbounding - rext) )
996  return;
997  }
998 
999  /* check whether circle intersects other circles */
1000  for( i = 0; i < nelements; ++i )
1001  {
1002  SCIP_Real dist;
1003 
1004  /* only consider packed elements */
1005  if( !ispacked[i] )
1006  continue;
1007 
1008  dist = SQR(x - xs[i]) + SQR(y - ys[i]);
1009 
1010  /* check if the distance between mid points is smaller than the sum of the radii */
1011  if( SCIPisLT(scip, dist, SQR(rext + rexts[elements[i]])) )
1012  return;
1013  }
1014 
1015  threshold = (patterntype == SCIP_PATTERNTYPE_RECTANGULAR ? wbounding - 2.0*rmax - rext : rbounding - 2.0*rmax - rext);
1016  isoverthreshold = (ncalls % 2) == 1 && SCIPisGT(scip, *bestx, threshold) && SCIPisGT(scip, x, threshold);
1017 
1018  /* check whether the candidate is better than the best known candidate */
1019  if( *bestx == SCIP_INVALID || *besty == SCIP_INVALID
1020  || ((!isoverthreshold || SCIPisEQ(scip, y, *besty)) && SCIPisLT(scip, x, *bestx)) /*lint !e777*/
1021  || ((isoverthreshold || SCIPisEQ(scip, x, *bestx)) && SCIPisLT(scip, y, *besty)) ) /*lint !e777*/
1022  {
1023  *bestx = x;
1024  *besty = y;
1025  }
1026 }
1027 
1028 /** auxiliary function for computing a candidate position between a circle and the outer ring */
1029 static
1031  SCIP* scip, /**< SCIP data structure */
1032  int* elements, /**< types of elements that have been packed */
1033  int nelements, /**< the total number of elements */
1034  SCIP_Real* rexts, /**< external radii */
1035  SCIP_Real* xs, /**< x-coordinate of circle */
1036  SCIP_Real* ys, /**< y-coordinate of circle */
1037  int pos, /**< position of element in the elements array */
1038  SCIP_Bool* ispacked, /**< array indicating whether an element has been packed already */
1039  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
1040  SCIP_Real rbound, /**< radius of bounding circle */
1041  SCIP_Real* bestx, /**< pointer to store the best x-coordinate */
1042  SCIP_Real* besty, /**< pointer to store the best y-coordinate */
1043  int ncalls /**< total number of calls of the packing heuristic */
1044  )
1045 {
1046  int i;
1047 
1048  /* consider already packed patterns */
1049  for( i = 0; i < nelements; ++i )
1050  {
1051  SCIP_Real alpha, a, b, c, h, u, v, n1, n2;
1052 
1053  /* only consider packed elements */
1054  if( !ispacked[i] )
1055  continue;
1056 
1057  c = SQRT(xs[i]*xs[i] + ys[i]*ys[i]);
1058 
1059  /* inner ring is too far away from boundary or both rings can not fit */
1060  if( !SCIPisGE(scip, c + rexts[elements[i]] + 2.0*rexts[elements[pos]], rbound)
1061  || SCIPisGT(scip, rexts[elements[pos]] + rexts[elements[i]], rbound) )
1062  continue;
1063 
1064  a = rexts[elements[pos]] + rexts[elements[i]];
1065  b = rbound - rexts[elements[pos]];
1066 
1067  /* if a ring is in the center than there are infinitely many solutions; take an arbitrary point */
1068  if( SCIPisZero(scip, c) )
1069  {
1070  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, -1.0, -1.0, rmax, SCIP_PATTERNTYPE_CIRCULAR,
1071  ispacked, elements, nelements, bestx, besty, -rbound + rexts[elements[pos]], 0.0, ncalls);
1072  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, -1.0, -1.0, rmax, SCIP_PATTERNTYPE_CIRCULAR,
1073  ispacked, elements, nelements, bestx, besty, +rbound - rexts[elements[pos]], 0.0, ncalls);
1074  }
1075  else
1076  {
1077  assert(c != 0.0);
1078  alpha = (c*c - b*b + a*a) / (2*c);
1079 
1080  if( a*a >= alpha*alpha )
1081  {
1082  h = SQRT(a*a - alpha*alpha);
1083  u = (c - alpha) * xs[i] / c;
1084  v = (c - alpha) * ys[i] / c;
1085 
1086  n1 = SCIPisZero(scip, v) ? 0.0 : h * (v / SQRT(v*v + u*u));
1087  n2 = SCIPisZero(scip, u) ? 0.0 : h * (-u / SQRT(v*v + u*u));
1088 
1089  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, -1.0, -1.0, rmax, SCIP_PATTERNTYPE_CIRCULAR,
1090  ispacked, elements, nelements, bestx, besty, u + n1, v + n2, ncalls);
1091  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, -1.0, -1.0, rmax, SCIP_PATTERNTYPE_CIRCULAR,
1092  ispacked, elements, nelements, bestx, besty, u - n1, v - n2, ncalls);
1093  }
1094  }
1095  }
1096 }
1097 
1098 /** auxiliary function for computing trivial candidate positions */
1099 static
1101  SCIP* scip, /**< SCIP data structure */
1102  int* elements, /**< types of elements that have been packed */
1103  int nelements, /**< the total number of elements */
1104  SCIP_Real* rexts, /**< external radii */
1105  SCIP_Real* xs, /**< x-coordinate of circle */
1106  SCIP_Real* ys, /**< y-coordinate of circle */
1107  int pos, /**< position of element in the elements array */
1108  SCIP_Bool* ispacked, /**< array indicating whether an element has been packed already */
1109  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
1110  SCIP_Real rbound, /**< radius of bounding circle */
1111  SCIP_Real width, /**< width of the rectangle */
1112  SCIP_Real height, /**< height of the rectangle */
1113  SCIP_PATTERNTYPE patterntype, /**< the pattern type (rectangular or circular) */
1114  SCIP_Real* bestx, /**< pointer to store the best x-coordinate */
1115  SCIP_Real* besty, /**< pointer to store the best y-coordinate */
1116  int ncalls /**< total number of calls of the packing heuristic */
1117  )
1118 {
1119  SCIP_Real rext = rexts[elements[pos]];
1120  int i;
1121 
1122  if( patterntype == SCIP_PATTERNTYPE_CIRCULAR )
1123  {
1124  SCIP_Real xcands[4] = {-rbound + rext, +rbound - rext, 0.0, 0.0};
1125  SCIP_Real ycands[4] = {0.0, 0.0, -rbound + rext, +rbound - rext};
1126 
1127  for( i = 0; i < 4; ++i )
1128  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, width, height, rmax, patterntype,
1129  ispacked, elements, nelements, bestx, besty, xcands[i], ycands[i], ncalls);
1130  }
1131  else
1132  {
1133  SCIP_Real xcands[4] = {rext, width - rext, rext, width - rext};
1134  SCIP_Real ycands[4] = {rext, rext, height - rext, height - rext};
1135 
1136  for( i = 0; i < 4; ++i )
1137  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], rbound, width, height, rmax, patterntype,
1138  ispacked, elements, nelements, bestx, besty, xcands[i], ycands[i], ncalls);
1139  }
1140 }
1141 
1142 /** auxiliary function for computing a candidate position between a circle and the rectangle */
1143 static
1145  SCIP* scip, /**< SCIP data structure */
1146  int* elements, /**< types of elements that have been packed */
1147  int nelements, /**< the total number of elements */
1148  SCIP_Real* rexts, /**< external radii */
1149  SCIP_Real* xs, /**< x-coordinate of circle */
1150  SCIP_Real* ys, /**< y-coordinate of circle */
1151  int pos, /**< position of element in the elements array */
1152  SCIP_Bool* ispacked, /**< array indicating whether an element has been packed already */
1153  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
1154  SCIP_Real width, /**< width of the rectangle */
1155  SCIP_Real height, /**< height of the rectangle */
1156  SCIP_Real* bestx, /**< pointer to store the best x-coordinate */
1157  SCIP_Real* besty, /**< pointer to store the best y-coordinate */
1158  int ncalls /**< total number of calls of the packing heuristic */
1159  )
1160 {
1161  SCIP_Real rext;
1162  int i;
1163 
1164  rext = rexts[elements[pos]];
1165 
1166  for( i = 0; i < nelements; ++i )
1167  {
1168  SCIP_Real xfix[2] = {rext, width - rext};
1169  SCIP_Real yfix[2] = {rext, height - rext};
1170  SCIP_Real Ri;
1171  int k;
1172 
1173  if( !ispacked[i] )
1174  continue;
1175 
1176  Ri = rexts[elements[i]];
1177 
1178  /* fix x */
1179  for( k = 0; k < 2; ++k )
1180  {
1181  SCIP_Real alpha = SQR(rext + Ri) - SQR(xfix[k] - xs[i]);
1182 
1183  if( alpha < 0.0 )
1184  continue;
1185 
1186  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], -1.0, width, height, rmax,
1187  SCIP_PATTERNTYPE_RECTANGULAR, ispacked, elements, nelements, bestx, besty, xfix[k], ys[i] + SQRT(alpha), ncalls);
1188 
1189  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], -1.0, width, height, rmax,
1190  SCIP_PATTERNTYPE_RECTANGULAR, ispacked, elements, nelements, bestx, besty, xfix[k], ys[i] - SQRT(alpha), ncalls);
1191  }
1192 
1193  /* fix y */
1194  for( k = 0; k < 2; ++k )
1195  {
1196  SCIP_Real alpha = SQR(rext + Ri) - SQR(yfix[k] - ys[i]);
1197 
1198  if( alpha < 0.0 )
1199  continue;
1200 
1201  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], -1.0, width, height, rmax,
1202  SCIP_PATTERNTYPE_RECTANGULAR, ispacked, elements, nelements, bestx, besty, xs[i] + SQRT(alpha), yfix[k], ncalls);
1203 
1204  updateBestCandidate(scip, xs, ys, rexts, rexts[elements[pos]], -1.0, width, height, rmax,
1205  SCIP_PATTERNTYPE_RECTANGULAR, ispacked, elements, nelements, bestx, besty, xs[i] - SQRT(alpha), yfix[k], ncalls);
1206  }
1207  }
1208 }
1209 
1210 /** auxiliary function for computing a candidate position between two circles */
1211 static
1213  SCIP* scip, /**< SCIP data structure */
1214  int* elements, /**< types of elements that have been packed */
1215  int nelements, /**< the total number of elements */
1216  SCIP_Real* rexts, /**< external radii */
1217  SCIP_Real* xs, /**< x-coordinate of circle */
1218  SCIP_Real* ys, /**< y-coordinate of circle */
1219  int pos, /**< position of element in the elements array */
1220  SCIP_Bool* ispacked, /**< array indicating whether an element has been packed already */
1221  SCIP_Real rmax, /**< maximum radius of elements in the pattern */
1222  SCIP_Real rbound, /**< radius of bounding circle */
1223  SCIP_Real width, /**< width of the rectangle */
1224  SCIP_Real height, /**< height of the rectangle */
1225  SCIP_PATTERNTYPE patterntype, /**< the pattern type (rectangular or circular) */
1226  SCIP_Real* bestx, /**< pointer to store the best x-coordinate */
1227  SCIP_Real* besty, /**< pointer to store the best y-coordinate */
1228  int ncalls /**< total number of calls of the packing heuristic */
1229  )
1230 {
1231  SCIP_Real rext;
1232  int i;
1233 
1234  rext = rexts[elements[pos]];
1235 
1236  /* consider all pairs of already packed circles */
1237  for( i = 0; i < nelements - 1; ++i )
1238  {
1239  SCIP_Real alpha, a, b, h, u, v, n1, n2;
1240  SCIP_Real Ri;
1241  int j;
1242 
1243  if( !ispacked[i] )
1244  continue;
1245 
1246  Ri = rexts[elements[i]];
1247 
1248  for( j = i + 1; j < nelements; ++j )
1249  {
1250  SCIP_Real Rj;
1251  SCIP_Real dist;
1252 
1253  if( !ispacked[j] )
1254  continue;
1255 
1256  Rj = rexts[elements[j]];
1257  dist = SQRT(SQR(xs[i] - xs[j]) + SQR(ys[i] - ys[j]));
1258 
1259  /* circles are too far away */
1260  if( SCIPisGE(scip, dist, Ri + Rj + 2.0 * rext) )
1261  continue;
1262 
1263  a = Ri + rext;
1264  b = Rj + rext;
1265  assert(dist != 0.0);
1266  alpha = (dist*dist - b*b + a*a) / (2.0*dist);
1267  h = SQRT(a*a - alpha*alpha);
1268  u = xs[i] + (alpha / dist) * (xs[j] - xs[i]);
1269  v = ys[i] + (alpha / dist) * (ys[j] - ys[i]);
1270  n1 = h * ((ys[j] - ys[i]) / dist);
1271  n2 = h * ((xs[i] - xs[j]) / dist);
1272  assert(n1*n1 + n2*n2 > 0.0);
1273 
1274  updateBestCandidate(scip, xs, ys, rexts, rext, rbound, width, height, rmax, patterntype, ispacked, elements,
1275  nelements, bestx, besty, u + n1, v + n2, ncalls);
1276  updateBestCandidate(scip, xs, ys, rexts, rext, rbound, width, height, rmax, patterntype, ispacked, elements,
1277  nelements, bestx, besty, u - n1, v - n2, ncalls);
1278  }
1279  }
1280 }
1281 
1282 /** array to compute the score of each element */
1283 static
1285  SCIP* scip, /**< SCIP data structure */
1286  SCIP_PROBDATA* probdata, /**< problem data */
1287  int* elements, /**< type of each element */
1288  int nelements, /**< total number of elements */
1289  SCIP_Real* scores, /**< array to store the score of each element */
1290  int iter /**< iteration round */
1291  )
1292 {
1293  SCIP_Real* rexts;
1294  int i;
1295 
1296  rexts = SCIPprobdataGetRexts(probdata);
1297  assert(rexts != NULL);
1298 
1299  for( i = 0; i < nelements; ++i )
1300  {
1301  SCIP_Real rext = rexts[elements[i]];
1302  /* use largest elements first */
1303  if( iter == 0 )
1304  scores[i] = rext;
1305 
1306  /* use smallest elements first */
1307  else if( iter == 1 )
1308  scores[i] = -rext;
1309 
1310  /* use [0,1] * radius */
1311  else if( iter <= 10 )
1312  scores[i] = SCIPrandomGetReal(probdata->randnumgen, 0.0, 1.0) * rext;
1313 
1314  /* use [-1,0] * radius */
1315  else if( iter <= 20 )
1316  scores[i] = SCIPrandomGetReal(probdata->randnumgen, -1.0, 0.0) * rext;
1317 
1318  /* use a random order */
1319  else
1320  scores[i] = SCIPrandomGetReal(probdata->randnumgen, 0.0, 1.0);
1321  }
1322 }
1323 
1324 /**@} */
1325 
1326 /**@name Callback methods of problem data
1327  *
1328  * @{
1329  */
1330 
1331 /** frees user data of original problem (called when the original problem is freed) */
1332 static
1333 SCIP_DECL_PROBDELORIG(probdelorigRingpacking)
1334 {
1335  SCIPdebugMessage("free original problem data\n");
1336  SCIP_CALL( probdataFree(scip, probdata) );
1337 
1338  return SCIP_OKAY;
1339 }
1340 
1341 /** frees user data of transformed problem (called when the transformed problem is freed) */
1342 static
1343 SCIP_DECL_PROBDELTRANS(probdeltransRingpacking)
1344 {
1345  SCIPdebugMessage("free transformed problem data\n");
1346  SCIP_CALL( probdataFree(scip, probdata) );
1347 
1348  return SCIP_OKAY;
1349 }
1350 
1351 /** creates user data of transformed problem by transforming the original user problem data
1352  * (called after problem was transformed) */
1353 static
1354 SCIP_DECL_PROBTRANS(probtransRingpacking)
1355 { /*lint --e{715}*/
1356  /* create transformed problem data */
1357  SCIP_CALL( probdataCreate(scip, targetdata, sourcedata->patternconss, sourcedata->cpatterns, sourcedata->cvars,
1358  sourcedata->ncpatterns, sourcedata->rpatterns, sourcedata->rvars, sourcedata->nrpatterns,
1359  sourcedata->demands, sourcedata->rints, sourcedata->rexts, sourcedata->ntypes,
1360  sourcedata->width, sourcedata->height) );
1361 
1362  /* transform pattern constraints */
1363  SCIP_CALL( SCIPtransformConss(scip, (*targetdata)->ntypes, (*targetdata)->patternconss,
1364  (*targetdata)->patternconss) );
1365 
1366  /* transform all variables */
1367  SCIP_CALL( SCIPtransformVars(scip, (*targetdata)->ncpatterns, (*targetdata)->cvars, (*targetdata)->cvars) );
1368  SCIP_CALL( SCIPtransformVars(scip, (*targetdata)->nrpatterns, (*targetdata)->rvars, (*targetdata)->rvars) );
1369 
1370  /* copy statistics to transformed problem data */
1371  (*targetdata)->ncppatternsunknownbeg = sourcedata->ncppatternsunknownbeg;
1372  (*targetdata)->enumtime = sourcedata->enumtime;
1373  (*targetdata)->dualbound = sourcedata->dualbound;
1374  (*targetdata)->isdualinvalid = sourcedata->isdualinvalid;
1375 
1376  return SCIP_OKAY;
1377 }
1378 
1379 /**@} */
1380 
1381 /**@name Interface methods
1382  *
1383  * @{
1384  */
1385 
1386 /** sets up the problem data */
1388  SCIP* scip, /**< SCIP data structure */
1389  const char* probname, /**< problem name */
1390  int* demands, /**< array containing the demands */
1391  SCIP_Real* rints, /**< internal radii of each ring */
1392  SCIP_Real* rexts, /**< external radii of each ring (assumed to be sorted) */
1393  int ntypes, /**< number of different types */
1394  SCIP_Real width, /**< width of each rectangle */
1395  SCIP_Real height /**< height of each rectangle */
1396  )
1397 {
1398  SCIP_PROBDATA* probdata;
1399 
1400 #ifndef NDEBUG
1401  {
1402  int t;
1403 
1404  for( t = 0; t < ntypes -1; ++t )
1405  assert(rexts[t] >= rexts[t+1]);
1406  }
1407 #endif
1408 
1409  /* create SCIP problem */
1410  SCIP_CALL( SCIPcreateProbBasic(scip, probname) );
1411 
1412  /* create and set problem data */
1413  SCIP_CALL( probdataCreate(scip, &probdata, NULL, NULL, NULL, 0, NULL, NULL, 0, demands, rints, rexts, ntypes, width,
1414  height) );
1415  SCIP_CALL( SCIPsetProbData(scip, probdata) );
1416 
1417  SCIP_CALL( SCIPsetProbDelorig(scip, probdelorigRingpacking) );
1418  SCIP_CALL( SCIPsetProbTrans(scip, probtransRingpacking) );
1419  SCIP_CALL( SCIPsetProbDeltrans(scip, probdeltransRingpacking) );
1420 
1421  /* activate pricer */
1423 
1424  /* add table output */
1425  assert(SCIPfindTable(scip, TABLE_NAME_RPA) == NULL);
1427  NULL, NULL, NULL, NULL, NULL, NULL, tableOutputRpa,
1429 
1430  return SCIP_OKAY;
1431 }
1432 
1433 /** enumerates circular patterns and creates restricted master problem */
1435  SCIP* scip /**< SCIP data structure */
1436  )
1437 {
1438  SCIP_PROBDATA* probdata = SCIPgetProbData(scip);
1439  assert(probdata != NULL);
1440 
1441  /* collect parameters for verification */
1442  SCIP_CALL( SCIPgetRealParam(scip, "ringpacking/verification/nlptilimsoft", &probdata->nlptilimsoft) );
1443  SCIP_CALL( SCIPgetRealParam(scip, "ringpacking/verification/heurtilimsoft", &probdata->heurtilimsoft) );
1444  SCIP_CALL( SCIPgetLongintParam(scip, "ringpacking/verification/nlpnodelimsoft", &probdata->nlpnodelimsoft) );
1445  SCIP_CALL( SCIPgetIntParam(scip, "ringpacking/verification/heuriterlimsoft", &probdata->heuriterlimsoft) );
1446  SCIP_CALL( SCIPgetRealParam(scip, "ringpacking/verification/totaltilimsoft", &probdata->totaltilimsoft) );
1447 
1448  SCIP_CALL( setupProblem(scip, probdata) );
1449 
1450  return SCIP_OKAY;
1451 }
1452 
1453 /** enumerate all non-dominated circular patterns */
1455  SCIP* scip, /**< SCIP data structure */
1456  SCIP_PROBDATA* probdata, /**< problem data */
1457  SCIP_Real nlptilim, /**< time limit for each NLP verification */
1458  SCIP_Real heurtilim, /**< time limit for each call of the heuristics */
1459  SCIP_Real totaltilim, /**< total time limit for enumeration */
1460  SCIP_Longint nlpnodelim, /**< node limit for each NLP verification */
1461  int heuriterlim /**< iteration limit for each call of the heuristics */
1462  )
1463 {
1464  SCIP_PATTERN* pattern;
1465  int* ms;
1466  int* nselected;
1467  SCIP_Real timeleft;
1468  int ntypes;
1469  int t;
1470 
1471  assert(probdata != NULL);
1472  ntypes = SCIPprobdataGetNTypes(probdata);
1473  assert(ntypes > 0);
1474 
1475  /* create data that is used for the whole enumeration algorithm */
1476  SCIP_CALL( SCIPpatternCreateCircular(scip, &pattern, 0) );
1477  SCIP_CALL( SCIPallocBufferArray(scip, &ms, ntypes) );
1478  SCIP_CALL( SCIPallocBufferArray(scip, &nselected, ntypes) );
1479  BMSclearMemoryArray(nselected, ntypes);
1480  BMSclearMemoryArray(ms, ntypes);
1481 
1482  /* compute time limit */
1483  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timeleft) );
1484  timeleft = MAX(0.0, MIN(timeleft - SCIPgetTotalTime(scip), totaltilim)); /*lint !e666*/
1485 
1486  /* find all circlular patterns of each type separately */
1487  for( t = 0; t < ntypes; ++t )
1488  {
1489  int k;
1490 
1491  for( k = t+1; k < ntypes; ++k )
1492  ms[k] = maxCircles(scip, probdata, t, k);
1493 
1494  SCIPpatternSetType(pattern, t);
1495  SCIP_CALL( enumeratePatterns(scip, probdata, pattern, ms, nselected, nlptilim, heurtilim, nlpnodelim,
1496  heuriterlim, &timeleft) );
1497  }
1498 
1499  /* release memory */
1500  SCIPfreeBufferArray(scip, &nselected);
1501  SCIPfreeBufferArray(scip, &ms);
1502  SCIPpatternRelease(scip, &pattern);
1503 
1504  /* filter circular patterns */
1505  SCIP_CALL( filterPatterns(scip, probdata) );
1506 
1507  return SCIP_OKAY;
1508 }
1509 
1510 /** returns number of different types */
1512  SCIP_PROBDATA* probdata /**< problem data */
1513  )
1514 {
1515  assert(probdata != NULL);
1516 
1517  return probdata->ntypes;
1518 }
1519 
1520 /** returns all external radii */
1522  SCIP_PROBDATA* probdata /**< problem data */
1523  )
1524 {
1525  assert(probdata != NULL);
1526 
1527  return probdata->rexts;
1528 }
1529 
1530 /** returns all internal radii */
1532  SCIP_PROBDATA* probdata /**< problem data */
1533  )
1534 {
1535  assert(probdata != NULL);
1536 
1537  return probdata->rints;
1538 }
1539 
1540 /** returns all demands */
1542  SCIP_PROBDATA* probdata /**< problem data */
1543  )
1544 {
1545  assert(probdata != NULL);
1546 
1547  return probdata->demands;
1548 }
1549 
1550 /** returns the width of each rectangle */
1552  SCIP_PROBDATA* probdata /**< problem data */
1553  )
1554 {
1555  assert(probdata != NULL);
1556 
1557  return probdata->width;
1558 }
1559 
1560 
1561 /** returns the height of each rectangle */
1563  SCIP_PROBDATA* probdata /**< problem data */
1564  )
1565 {
1566  assert(probdata != NULL);
1567 
1568  return probdata->height;
1569 }
1570 
1571 /** returns all information about circular patterns */
1573  SCIP_PROBDATA* probdata, /**< problem data */
1574  SCIP_PATTERN*** cpatterns, /**< pointer to store the circular patterns (might be NULL) */
1575  SCIP_VAR*** cvars, /**< pointer to store the variables corresponding circular patterns (might be NULL) */
1576  int* ncpatterns /**< pointer to store the number of circular patterns (might be NULL) */
1577  )
1578 {
1579  assert(probdata != NULL);
1580 
1581  if( cpatterns != NULL )
1582  *cpatterns = probdata->cpatterns;
1583  if( cvars != NULL )
1584  *cvars= probdata->cvars;
1585  if( ncpatterns != NULL )
1586  *ncpatterns = probdata->ncpatterns;
1587 }
1588 
1589 /** returns all information about rectangular patterns */
1591  SCIP_PROBDATA* probdata, /**< problem data */
1592  SCIP_PATTERN*** rpatterns, /**< pointer to store the rectangular patterns (might be NULL) */
1593  SCIP_VAR*** rvars, /**< pointer to store the variables corresponding rectangular patterns (might be NULL) */
1594  int* nrpatterns /**< pointer to store the number of rectangular patterns (might be NULL) */
1595  )
1596 {
1597  assert(probdata != NULL);
1598 
1599  if( rpatterns != NULL )
1600  *rpatterns = probdata->rpatterns;
1601  if( rvars != NULL )
1602  *rvars= probdata->rvars;
1603  if( nrpatterns != NULL )
1604  *nrpatterns = probdata->nrpatterns;
1605 }
1606 
1607 /** returns array of set pattern constraints */
1609  SCIP_PROBDATA* probdata /**< problem data */
1610  )
1611 {
1612  assert(probdata != NULL);
1613 
1614  return probdata->patternconss;
1615 }
1616 
1617 /** adds given variable to the problem data */
1619  SCIP* scip, /**< SCIP data structure */
1620  SCIP_PROBDATA* probdata, /**< problem data */
1621  SCIP_PATTERN* pattern, /**< pattern */
1622  SCIP_VAR* var /**< variables to add */
1623  )
1624 {
1625  SCIP_PATTERN* copy;
1626 
1627  assert(probdata != NULL);
1628  assert(pattern != NULL);
1629  assert(SCIPpatternGetPackableStatus(pattern) != SCIP_PACKABLE_NO);
1630 
1631  /* copy pattern */
1632  SCIP_CALL( SCIPpatternCopy(scip, pattern, &copy) );
1633  SCIPcheckPattern(scip, probdata, copy);
1634 
1636  {
1637  SCIP_CALL( ensureSize(scip, probdata, SCIP_PATTERNTYPE_CIRCULAR, probdata->ncpatterns + 1) );
1638  probdata->cpatterns[probdata->ncpatterns] = copy;
1639  probdata->cvars[probdata->ncpatterns] = var;
1640  ++(probdata->ncpatterns);
1641  }
1642  else
1643  {
1644  SCIP_CALL( ensureSize(scip, probdata, SCIP_PATTERNTYPE_RECTANGULAR, probdata->nrpatterns + 1) );
1645  probdata->rpatterns[probdata->nrpatterns] = copy;
1646  probdata->rvars[probdata->nrpatterns] = var;
1647  ++(probdata->nrpatterns);
1648  }
1649 
1650  /* capture variable and pattern */
1651  if( var != NULL )
1652  {
1653  SCIP_CALL( SCIPcaptureVar(scip, var) );
1654  }
1655 
1656  return SCIP_OKAY;
1657 }
1658 
1659 /** updates the dual bound */
1661  SCIP* scip, /**< SCIP data structure */
1662  SCIP_PROBDATA* probdata, /**< problem data */
1663  SCIP_Real dualbound /**< new dual bound */
1664  )
1665 {
1666  assert(probdata != NULL);
1667 
1668  if( !probdata->isdualinvalid && SCIPisFeasLT(scip, probdata->dualbound, dualbound) )
1669  {
1670  SCIPinfoMessage(scip, NULL, "+++++++++++++ update dual bound to %g\n", dualbound);
1671  probdata->dualbound = dualbound;
1672  }
1673 }
1674 
1675 /** marks that further reported dual bounds are not valid */
1677  SCIP* scip, /**< SCIP data structure */
1678  SCIP_PROBDATA* probdata /**< problem data */
1679  )
1680 {
1681  assert(probdata != NULL);
1682 
1683  if( !probdata->isdualinvalid )
1684  {
1685  SCIPinfoMessage(scip, NULL, "+++++++++++++ invalidate dual bound\n");
1686  probdata->isdualinvalid = TRUE;
1687  }
1688 }
1689 
1690 /** returns whether dual bound is marked to be invalid */
1692  SCIP_PROBDATA* probdata /**< problem data */
1693  )
1694 {
1695  assert(probdata != NULL);
1696 
1697  return probdata->isdualinvalid;
1698 }
1699 
1700 /** Tries to pack a list of elements into a specified boundary circle by using a simple left-first bottom-second
1701  * heuristic. Returns the number of elements that could be stored and indicated which ones these are in the buffer
1702  * parameter ispacked. This auxiliary method can be used both to find such a packing or to verify a certain pattern.
1703  */
1705  SCIP* scip, /**< SCIP data structure */
1706  SCIP_Real* rexts, /**< outer radii of elements (in original order of probdata) */
1707  SCIP_Real* xs, /**< buffer to store the resulting x-coordinates */
1708  SCIP_Real* ys, /**< buffer to store the resulting y-coordinates */
1709  SCIP_Real rbounding, /**< inner radius of bounding circle (ignored for rectangular patterns) */
1710  SCIP_Real width, /**< width of the rectangle */
1711  SCIP_Real height, /**< height of the rectangle */
1712  SCIP_Bool* ispacked, /**< buffer to store which elements could be packed */
1713  int* elements, /**< the order of the elements in the pattern */
1714  int nelements, /**< number of elements in the pattern */
1715  SCIP_PATTERNTYPE patterntype, /**< the pattern type (rectangular or circular) */
1716  int* npacked, /**< pointer to store the number of packed elements */
1717  int ncalls /**< total number of calls of the packing heuristic */
1718  )
1719 {
1720  SCIP_Real rmax;
1721  SCIP_Bool added;
1722  int i;
1723 
1724  assert(rexts != NULL);
1725  assert(xs != NULL);
1726  assert(ys != NULL);
1727  assert(ispacked != NULL);
1728  assert(elements != NULL);
1729  assert(nelements > 0);
1730  assert(npacked != NULL);
1731 
1732  /* no element packed so far */
1733  BMSclearMemoryArray(ispacked, nelements);
1734 
1735  /* place first element at left-most position */
1736  if( patterntype == SCIP_PATTERNTYPE_CIRCULAR )
1737  {
1738  assert(rexts[elements[0]] <= rbounding);
1739  xs[0] = rexts[elements[0]] - rbounding;
1740  ys[0] = 0.0;
1741  }
1742  else
1743  {
1744  assert(2.0 * rexts[elements[0]] <= width);
1745  assert(2.0 * rexts[elements[0]] <= height);
1746  xs[0] = rexts[elements[0]];
1747  ys[0] = rexts[elements[0]];
1748  }
1749 
1750  /* initialize results */
1751  (*npacked) = 1;
1752  ispacked[0] = TRUE;
1753  added = TRUE;
1754 
1755  /* find max radius */
1756  rmax = rexts[elements[0]];
1757  for( i = 1; i < nelements; ++i )
1758  {
1759  if( rexts[elements[i]] > rmax )
1760  rmax = rexts[elements[i]];
1761  }
1762 
1763  /* iterate over all elements and try to pack them */
1764  while( added )
1765  {
1766  added = FALSE;
1767 
1768  for( i = 1; i < nelements; ++i )
1769  {
1770  SCIP_Real bestx = SCIP_INVALID;
1771  SCIP_Real besty = SCIP_INVALID;
1772 
1773  /* skip packed elements */
1774  if( ispacked[i] )
1775  continue;
1776 
1777  /* use trivial candidates */
1778  computePosTrivial(scip, elements, nelements, rexts, xs, ys, i, ispacked, rmax, rbounding, width, height,
1779  patterntype, &bestx, &besty, ncalls);
1780 
1781  /* consider circles intersection a previous circle and the boundary ring */
1782  if( patterntype == SCIP_PATTERNTYPE_CIRCULAR )
1783  computePosRingCircle(scip, elements, nelements, rexts, xs, ys, i, ispacked, rmax, rbounding, &bestx,
1784  &besty, ncalls);
1785  else
1786  computePosRectangleCircle(scip, elements, nelements, rexts, xs, ys, i, ispacked, rmax, width, height, &bestx,
1787  &besty, ncalls);
1788 
1789  /* consider circles that have been packed already */
1790  computePosCircleCircle(scip, elements, nelements, rexts, xs, ys, i, ispacked, rmax, rbounding, width, height,
1791  patterntype, &bestx, &besty, ncalls);
1792 
1793  /* pack circle if a possible position has been found */
1794  if( bestx != SCIP_INVALID && besty != SCIP_INVALID ) /*lint !e777*/
1795  {
1796  assert(!ispacked[i]);
1797  ispacked[i] = TRUE;
1798  xs[i] = bestx;
1799  ys[i] = besty;
1800  ++(*npacked);
1801  added = TRUE;
1802  }
1803  }
1804  }
1805 
1806  return;
1807 }
1808 
1809 /** verifies a circular pattern heuristically */
1811  SCIP* scip, /**< SCIP data structure */
1812  SCIP_PROBDATA* probdata, /**< problem data */
1813  SCIP_PATTERN* pattern, /**< pattern */
1814  SCIP_Real timelim, /**< time limit */
1815  int iterlim /**< iteration limit */
1816  )
1817 {
1818  SCIP_Real* rexts;
1819  SCIP_Real* rints;
1820  SCIP_Real* scores;
1821  SCIP_Real* xs;
1822  SCIP_Real* ys;
1823  SCIP_Bool* ispacked;
1824  int* elements;
1825  int* pos;
1826  SCIP_Real timestart;
1827  int nelements;
1828  int niters;
1829  int type;
1830  int i;
1831 
1832  assert(probdata != NULL);
1833  assert(pattern != NULL);
1834  assert(iterlim > 0);
1837  assert(SCIPpatternGetCircleType(pattern) < SCIPprobdataGetNTypes(probdata));
1838 
1839  /* check whether there is any time left */
1840  if( timelim <= 0.0 )
1841  return SCIP_OKAY;
1842 
1843  rexts = SCIPprobdataGetRexts(probdata);
1844  rints = SCIPprobdataGetRints(probdata);
1845  nelements = SCIPpatternGetNElemens(pattern);
1846  type = SCIPpatternGetCircleType(pattern);
1847  assert(type >= 0 && type < SCIPprobdataGetNTypes(probdata));
1848 
1849  /* pattern is empty -> set status to packable */
1850  if( SCIPpatternGetNElemens(pattern) == 0 )
1851  {
1853  SCIPcheckPattern(scip, probdata, pattern);
1854  return SCIP_OKAY;
1855  }
1856 
1857  /* pattern contains only one element -> compare radii */
1858  if( SCIPpatternGetNElemens(pattern) == 1 )
1859  {
1860  int elemtype;
1861 
1862  elemtype = SCIPpatternGetElementType(pattern, 0);
1863  assert(elemtype >= 0 && elemtype < SCIPprobdataGetNTypes(probdata));
1864 
1865  /* check whether element fits into the circular pattern */
1866  if( SCIPisGE(scip, rints[type], rexts[elemtype]) )
1867  {
1868  SCIPpatternSetElementPos(pattern, 0, rexts[elemtype]-rints[type], 0.0);
1870  }
1871  else
1873 
1874  SCIPcheckPattern(scip, probdata, pattern);
1875  return SCIP_OKAY;
1876  }
1877 
1878  timestart = SCIPgetTotalTime(scip);
1879  niters = 0;
1880 
1881  /* store elements in a separate array; remember positions of elements in the pattern */
1882  SCIP_CALL( SCIPallocBufferArray(scip, &pos, nelements) );
1883  SCIP_CALL( SCIPallocBufferArray(scip, &scores, nelements) );
1884  SCIP_CALL( SCIPallocBufferArray(scip, &ispacked, nelements) );
1885  SCIP_CALL( SCIPallocBufferArray(scip, &elements, nelements) );
1886  SCIP_CALL( SCIPallocBufferArray(scip, &xs, nelements) );
1887  SCIP_CALL( SCIPallocBufferArray(scip, &ys, nelements) );
1888  for( i = 0; i < nelements; ++i )
1889  {
1890  elements[i] = SCIPpatternGetElementType(pattern, i);
1891  ispacked[i] = FALSE;
1892  pos[i] = i;
1893  }
1894 
1895  /* main loop for calling heuristic verification */
1897  && niters < iterlim
1898  && SCIPgetTotalTime(scip) - timestart <= timelim )
1899  {
1900  int npacked;
1901 
1902  /* compute scores depending on iteration counter */
1903  computeScores(scip, probdata, elements, nelements, scores, niters);
1904 
1905  /* sort elements in non-increasing order */
1906  SCIPsortDownRealIntInt(scores, elements, pos, nelements);
1907 
1908  /* call heuristic */
1909  SCIPpackCirclesGreedy(scip, rexts, xs, ys, rints[type], SCIPprobdataGetWidth(probdata),
1910  SCIPprobdataGetHeight(probdata), ispacked, elements, nelements, SCIP_PATTERNTYPE_CIRCULAR, &npacked, niters);
1911 
1912  /* check whether all elements could have been packed */
1913  if( npacked == nelements )
1914  {
1915  for( i = 0; i < nelements; ++i )
1916  {
1917  assert(elements[i] == SCIPpatternGetElementType(pattern, pos[i]));
1918  SCIPpatternSetElementPos(pattern, pos[i], xs[i], ys[i]);
1919  }
1921 
1922  SCIPdebugMsg(scip, "heuristic verified pattern after %d iterations\n", niters + 1);
1923  }
1924 
1925  ++niters;
1926  }
1927 
1928  SCIPcheckPattern(scip, probdata, pattern);
1929 
1930  /* free memory */
1931  SCIPfreeBufferArray(scip, &ys);
1932  SCIPfreeBufferArray(scip, &xs);
1933  SCIPfreeBufferArray(scip, &elements);
1934  SCIPfreeBufferArray(scip, &ispacked);
1935  SCIPfreeBufferArray(scip, &scores);
1936  SCIPfreeBufferArray(scip, &pos);
1937 
1938  return SCIP_OKAY;
1939 }
1940 
1941 /** verifies a circular pattern via a verification NLP */
1943  SCIP* scip, /**< SCIP data structure */
1944  SCIP_PROBDATA* probdata, /**< problem data */
1945  SCIP_PATTERN* pattern, /**< pattern */
1946  SCIP_Real timelim, /**< time limit */
1947  SCIP_Longint nodelim /**< node limit */
1948  )
1949 {
1950  SCIP* subscip;
1951  SCIP_CONS* cons;
1952  SCIP_VAR** xvars;
1953  SCIP_VAR** yvars;
1954  SCIP_VAR* quadvars1[6];
1955  SCIP_VAR* quadvars2[6];
1956  SCIP_Real quadcoefs[6];
1957  SCIP_Real* rexts;
1958  SCIP_Real* rints;
1959  char name[SCIP_MAXSTRLEN];
1960  int nelems;
1961  int type;
1962  int k;
1963 
1964  assert(probdata != NULL);
1965  assert(pattern != NULL);
1968 
1969  /* check whether there is any time left */
1970  if( timelim <= 0.0 )
1971  return SCIP_OKAY;
1972 
1973  rexts = SCIPprobdataGetRexts(probdata);
1974  rints = SCIPprobdataGetRints(probdata);
1975  type = SCIPpatternGetCircleType(pattern);
1976  nelems = SCIPpatternGetNElemens(pattern);
1977 
1978  /* set up the sub-SCIP */
1979  SCIP_CALL( SCIPcreate(&subscip) );
1980  SCIP_CALL( SCIPcreateProbBasic(subscip, "verify") );
1982 
1983  /* allocate memory for (x,y) variables */
1984  SCIP_CALL( SCIPallocBufferArray(scip, &xvars, nelems) );
1985  SCIP_CALL( SCIPallocBufferArray(scip, &yvars, nelems) );
1986 
1987  /* set feasibility emphasis settings */
1989 
1990  /* set working limit */
1991  SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
1992  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelim) );
1993  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelim) );
1994 
1995 #ifndef SCIP_DEBUG
1996  SCIPsetMessagehdlrQuiet(subscip, TRUE);
1997 #endif
1998 
1999  /* create (x,y) variables */
2000  for( k = 0; k < nelems; ++k )
2001  {
2002  int elemtype;
2003 
2004  elemtype = SCIPpatternGetElementType(pattern, k);
2005  assert(elemtype >= 0 && elemtype < SCIPprobdataGetNTypes(probdata));
2006 
2007  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "x_%d", k);
2008  SCIP_CALL( SCIPcreateVarBasic(subscip, &xvars[k], name, rexts[elemtype] - rints[type],
2009  rints[type] - rexts[elemtype], 0.0, SCIP_VARTYPE_CONTINUOUS) );
2010  SCIP_CALL( SCIPaddVar(subscip, xvars[k]) );
2011 
2012  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "y_%d", k);
2013  SCIP_CALL( SCIPcreateVarBasic(subscip, &yvars[k], name, rexts[elemtype] - rints[type],
2014  rints[type] - rexts[elemtype], 1.0, SCIP_VARTYPE_CONTINUOUS) );
2015  SCIP_CALL( SCIPaddVar(subscip, yvars[k]) );
2016  }
2017 
2018  /* create non-overlapping constraints */
2019  for( k = 0; k < nelems; ++k )
2020  {
2021  int elemtype1;
2022  int l;
2023 
2024  elemtype1 = SCIPpatternGetElementType(pattern, k);
2025  assert(elemtype1 >= 0 && elemtype1 < SCIPprobdataGetNTypes(probdata));
2026 
2027  for( l = k + 1; l < nelems; ++l )
2028  {
2029  int elemtype2;
2030 
2031  elemtype2 = SCIPpatternGetElementType(pattern, l);
2032  assert(elemtype2 >= 0 && elemtype2 < SCIPprobdataGetNTypes(probdata));
2033 
2034  quadvars1[0] = xvars[k]; quadvars2[0] = xvars[k]; quadcoefs[0] = 1.0;
2035  quadvars1[1] = xvars[k]; quadvars2[1] = xvars[l]; quadcoefs[1] = -2.0;
2036  quadvars1[2] = xvars[l]; quadvars2[2] = xvars[l]; quadcoefs[2] = 1.0;
2037  quadvars1[3] = yvars[k]; quadvars2[3] = yvars[k]; quadcoefs[3] = 1.0;
2038  quadvars1[4] = yvars[k]; quadvars2[4] = yvars[l]; quadcoefs[4] = -2.0;
2039  quadvars1[5] = yvars[l]; quadvars2[5] = yvars[l]; quadcoefs[5] = 1.0;
2040 
2041  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "over_%d_%d", k, l);
2042  SCIP_CALL( SCIPcreateConsBasicQuadratic(subscip, &cons, name, 0, NULL, NULL, 6, quadvars1, quadvars2,
2043  quadcoefs, SQR(rexts[elemtype1] + rexts[elemtype2]), SCIPinfinity(subscip)) );
2044 
2045  SCIP_CALL( SCIPaddCons(subscip, cons) );
2046  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
2047  }
2048  }
2049 
2050  /* create non-overlapping constraints with outer ring */
2051  for( k = 0; k < nelems; ++k )
2052  {
2053  int elemtype;
2054 
2055  elemtype = SCIPpatternGetElementType(pattern, k);
2056  assert(elemtype >= 0 && elemtype < SCIPprobdataGetNTypes(probdata));
2057 
2058  quadvars1[0] = xvars[k]; quadvars2[0] = xvars[k]; quadcoefs[0] = 1.0;
2059  quadvars1[1] = yvars[k]; quadvars2[1] = yvars[k]; quadcoefs[1] = 1.0;
2060 
2061  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "bound_%d", k);
2062  SCIP_CALL( SCIPcreateConsBasicQuadratic(subscip, &cons, name, 0, NULL, NULL, 2, quadvars1, quadvars2, quadcoefs,
2063  0.0, SQR(rints[type] - rexts[elemtype])) );
2064 
2065  SCIP_CALL( SCIPaddCons(subscip, cons) );
2066  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
2067  }
2068 
2069  /* sort circles in x direction if they have the same type */
2070  for( k = 0; k < nelems - 1; ++k )
2071  {
2072  int elemtype1;
2073  int l;
2074 
2075  elemtype1 = SCIPpatternGetElementType(pattern, k);
2076  assert(elemtype1 >= 0 && elemtype1 < SCIPprobdataGetNTypes(probdata));
2077 
2078  for( l = k + 1; l < nelems; ++l )
2079  {
2080  int elemtype2;
2081 
2082  elemtype2 = SCIPpatternGetElementType(pattern, k+1);
2083  assert(elemtype2 >= 0 && elemtype2 < SCIPprobdataGetNTypes(probdata));
2084 
2085  if( elemtype1 != elemtype2 )
2086  continue;
2087 
2088  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sortx_%d_%d", k, l);
2089  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &cons, name, 0, NULL, NULL, -SCIPinfinity(subscip), 0.0) );
2090  SCIP_CALL( SCIPaddCoefLinear(subscip, cons, xvars[k], 1.0) );
2091  SCIP_CALL( SCIPaddCoefLinear(subscip, cons, xvars[l], -1.0) );
2092 
2093  SCIP_CALL( SCIPaddCons(subscip, cons) );
2094  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
2095  }
2096  }
2097 
2098  /* solve verification NLP */
2099  SCIPdebugMsg(scip, "--------------------- SOLVE VERIFICATION NLP -------------------\n");
2100  SCIP_CALL( SCIPsolve(subscip) );
2101  SCIPdebugMsg(scip, "----------------------------------------------------------------\n");
2102 
2103  SCIPdebugMsg(scip, "result of verification NLP: nsols=%d solstat=%d\n",
2104  SCIPgetNSols(subscip), SCIPgetStatus(subscip));
2105 
2106  /* check whether a solution could be found or whether the problem is proven to be infeasible */
2107  if( SCIPgetNSols(subscip) > 0 )
2108  {
2110 
2111  for( k = 0; k < nelems; ++k )
2112  {
2113  SCIP_Real solx = SCIPgetSolVal(subscip, SCIPgetBestSol(subscip), xvars[k]);
2114  SCIP_Real soly = SCIPgetSolVal(subscip, SCIPgetBestSol(subscip), yvars[k]);
2115 
2116  SCIPpatternSetElementPos(pattern, k, solx, soly);
2117  }
2118 
2119  SCIPcheckPattern(scip, probdata, pattern);
2120  }
2121  else if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE )
2123 
2124  /* free all variables */
2125  for( k = 0; k < nelems; ++k )
2126  {
2127  SCIP_CALL( SCIPreleaseVar(subscip, &yvars[k]) );
2128  SCIP_CALL( SCIPreleaseVar(subscip, &xvars[k]) );
2129  }
2130 
2131  /* free memory */
2132  SCIPfreeBufferArray(scip, &yvars);
2133  SCIPfreeBufferArray(scip, &xvars);
2134  SCIP_CALL( SCIPfree(&subscip) );
2135 
2136  return SCIP_OKAY;
2137 }
2138 
2139 /** check a pattern for consistency */
2141  SCIP* scip, /**< SCIP data structure */
2142  SCIP_PROBDATA* probdata, /**< problem data */
2143  SCIP_PATTERN* pattern /**< pattern */
2144  )
2145 { /*lint --e{715}*/
2146 #ifndef NDEBUG
2147  SCIP_Real* rexts;
2148  SCIP_Real* rints;
2149  SCIP_Real width;
2150  SCIP_Real height;
2151  int i;
2152 
2153  assert(probdata != NULL);
2154  assert(pattern != NULL);
2155 
2156  rexts = SCIPprobdataGetRexts(probdata);
2157  rints = SCIPprobdataGetRints(probdata);
2158  width = SCIPprobdataGetWidth(probdata);
2159  height = SCIPprobdataGetHeight(probdata);
2160 
2161  /* check types */
2162  for( i = 0; i < SCIPpatternGetNElemens(pattern); ++i )
2163  {
2164  int type = SCIPpatternGetElementType(pattern, i);
2165 
2166  assert(type >= 0);
2167  assert(type < SCIPprobdataGetNTypes(probdata));
2168  }
2169 
2170  /* check positions iff packable */
2172  return;
2173 
2174  for( i = 0; i < SCIPpatternGetNElemens(pattern); ++i )
2175  {
2176  SCIP_Real xi = SCIPpatternGetElementPosX(pattern, i);
2177  SCIP_Real yi = SCIPpatternGetElementPosY(pattern, i);
2178  int typei = SCIPpatternGetElementType(pattern, i);
2179  int j;
2180 
2181  /* check distance between circles */
2182  for( j = i + 1; j < SCIPpatternGetNElemens(pattern); ++j )
2183  {
2184  SCIP_Real xj = SCIPpatternGetElementPosX(pattern, j);
2185  SCIP_Real yj = SCIPpatternGetElementPosY(pattern, j);
2186  int typej = SCIPpatternGetElementType(pattern, j);
2187 
2188  assert(SCIPisFeasGE(scip, SQRT(SQR(xi - xj) + SQR(yi - yj)), rexts[typei] + rexts[typej]));
2189  }
2190 
2191  /* check distance to boundary */
2193  {
2194  SCIP_Real distance = SQRT(SQR(xi) + SQR(yi));
2195  int patterntype = SCIPpatternGetCircleType(pattern);
2196 
2197  assert(patterntype >= 0);
2198  assert(patterntype < SCIPprobdataGetNTypes(probdata));
2199  assert(SCIPisFeasLE(scip, distance, rints[patterntype] - rexts[typei]));
2200  }
2201  else
2202  {
2203  assert(SCIPisFeasGE(scip, xi, rexts[typei]));
2204  assert(SCIPisFeasLE(scip, xi, width - rexts[typei]));
2205  assert(SCIPisFeasGE(scip, yi, rexts[typei]));
2206  assert(SCIPisFeasLE(scip, yi, height - rexts[typei]));
2207  }
2208  }
2209 #endif
2210 }
2211 
2212 /**@} */
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:273
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:1218
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:9967
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:2527
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:613
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:364
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:871
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:555
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:957
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:10590
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:1252
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:497
static SCIP_DECL_TABLEOUTPUT(tableOutputRpa)
Definition: probdata_rpa.c:893
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:1393