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