Scippy

SCIP

Solving Constraint Integer Programs

pricer_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 pricer_rpa.c
26  * @brief Ringpacking variable pricer
27  * @author Benjamin Mueller
28  *
29  * This file implements the variable pricer which checks if variables negative reduced cost exist. See
30  * @ref RINGPACKING_PRICER for more details.
31  *
32  * @page RINGPACKING_PRICER Pricing new variables
33  *
34  * The task of the pricer is to search for new variables with negative reduced costs. For this, the following non-linear
35  * program is solved:
36  *
37  * \f[
38  * \begin{equation}
39  * \min_{P \in \mathcal{RP}} \left\{1 - \sum_{t \in \mathcal{T}} \lambda_t P_t\right\},
40  * \end{equation}
41  * \f]
42  *
43  * where \f$\lambda\f$ is given by the dual solution of the restricted master problem. See the
44  * \ref RINGPACKING_PROBLEM "problem description" for more details.
45  *
46  * This problem is very hard, but can be modeled as a weighted circle packing problem for a single rectangle. Therefore,
47  * we first use a simple greedy heuristic to solve the problem. If the heuristic fails, the MINLP is solved with
48  * conventional methods on a new \SCIP instance and a given time limit. If the problem can be solved and the optimal
49  * value is non-negative, the LP relaxation has been solved to optimality and what remains is ensuring integrality of
50  * the solution by the normal \SCIP framework. If, on the other hand, the best solution found by both methods is negative,
51  * we have found an improving pattern, whose corresponding variable needs to be added to the restricted master problem.
52  * It is possible (and not unlikely) that neither method succeeds in finding a pattern with negative solution value. In
53  * that case, we also exit the pricing loop, just as if we had found an optimal solution, and proceed with enforcing
54  * integrality resulting in a feasible primal solution to the whole problem.
55  *
56  * In case that the pricing problem cannot be solved to optimality, we cannot directly deduce a lower bound for the
57  * master problem. However, the following theorem by Farley shows how a valid dual bound can be computed from the
58  * LP solution and the pricing solution, see
59  * <a href="https://doi.org/10.1287/opre.38.5.922">A Note on Bounding a Class of Linear Programming Problems, Including
60  * Cutting Stock Problems</a> for more details.
61  *
62  */
63 
64 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
65 
66 #include <assert.h>
67 #include <string.h>
68 #include <sys/stat.h>
69 #include <sys/types.h>
70 
71 #include "scip/scipdefplugins.h"
72 #include "scip/scip.h"
73 #include "pricer_rpa.h"
74 #include "probdata_rpa.h"
75 #include "pattern.h"
76 
77 /**@name Pricer properties
78  *
79  * @{
80  */
81 
82 #define PRICER_NAME "ringpacking"
83 #define PRICER_DESC "pricer for ringpacking"
84 #define PRICER_PRIORITY 0
85 #define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */
86 
87 /* default values of pricing parameters */
88 #define DEFAULT_PRICING_NLPTILIM 1e+20 /**< time limit for each pricing NLP */
89 #define DEFAULT_PRICING_NLPNODELIM 1000L /**< node limit for each pricing NLP */
90 #define DEFAULT_PRICING_HEURTILIM 1e+20 /**< time limit for each heuristic pricing */
91 #define DEFAULT_PRICING_HEURITERLIM 1000 /**< iteration limit for each heuristic pricing */
92 #define DEFAULT_PRICING_TOTALTILIM 1e+20 /**< total time limit for all pricing NLPs and heuristic calls */
93 
94 /**@} */
95 
96 #ifndef M_PI
97 #define M_PI 3.141592653589793238462643
98 #endif
99 
100 /*
101  * Data structures
102  */
103 
104 /** @brief Variable pricer data used in the \ref pricer_ringpacking.c "pricer" */
105 struct SCIP_PricerData
106 {
107  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
108  SCIP_Real timeleft; /**< time left for solving pricing problems (with NLP or heuristic) */
109 
110  /* parameters */
111  SCIP_Real nlptilim; /**< time limit for pricing NLP */
112  SCIP_Real heurtilim; /**< time limit for pricing heuristic */
113  SCIP_Longint nlpnodelim; /**< node limit for pricing NLP */
114  int heuriterlim; /**< iteration limit for pricing heuristic */
115 };
116 
117 
118 /**@name Local methods
119  *
120  * @{
121  */
122 
123 /** returns an upper bound on the density for n equal circles in a square (holds also for rectangles); this is a result
124  * of Groemer's formula (see, 'Ueber die Einlagerung von Kreisen in einen konvexen Bereich')
125  */
126 static
128 {
129  assert(n > 0);
130  if( n == 1 )
131  return M_PI / 4.0;
132  return (n * M_PI) / SQR(2.0 - SQRT(3.0) + SQRT(7.0 - M_PI + SQRT(3.0)*(2.0*n - 6.0 + M_PI)) );/*lint !e666*/
133 }
134 
135 /** helper function to count how many circles of a given type are needed */
136 static
138  SCIP* scip, /**< SCIP data structure */
139  SCIP_Real rext, /**< external radius */
140  int demand, /**< demand */
141  SCIP_Real width, /**< width of the rectangle */
142  SCIP_Real height, /**< height of the rectangle */
143  SCIP_Real lambda /**< objective coefficient of each circle of the given type */
144  )
145 {
146  SCIP_Real volrect;
147  SCIP_Real volcircle;
148  int ncircles;
149 
150  assert(!SCIPisFeasNegative(scip, lambda));
151 
152  /* objective coefficient of this circle type is zero -> not needed */
153  if( !SCIPisFeasPositive(scip, lambda) )
154  return 0;
155 
156  volrect = width * height;
157  volcircle = M_PI * SQR(rext);
158  assert(volcircle != 0.0);
159 
160  ncircles = (int)SCIPfeasFloor(scip, (getDensityUb(demand) * volrect) / volcircle);
161 
162  /* special cases where too big circles have a minimum distance to each other (in x direction) */
163  if( SCIPisGT(scip, rext, height / 4.0) )
164  {
165  SCIP_Real c = SQRT(4.0 * rext * height - SQR(height));
166  ncircles = (int)MIN(ncircles, 1 + (int)SCIPfloor(scip, (width - 2.0*rext) / c)); /*lint !e666*/
167  }
168  if( SCIPisGT(scip, rext, height / 6.0) && SCIPisLE(scip, rext, height / 4.0) )
169  {
170  SCIP_Real c = MIN(SQRT(3.0*rext*rext + rext * height - height * height / 4.0),
171  SQRT(8.0 * rext * height - height * height - 12.0 * rext * rext)); /*lint !e666*/
172  SCIP_Real k = SCIPfloor(scip, height / (2.0 * rext)) + 1;
173  SCIP_Real l = (width - 2.0 * rext) / c;
174  ncircles = (int)MIN(ncircles, k + l*(k-1) - 1);
175  }
176  assert(ncircles > 0);
177 
178  return MIN(ncircles, demand);
179 }
180 
181 /** adds a variable to the restricted master problem */
182 static
184  SCIP* scip, /**< SCIP data structure */
185  SCIP_PROBDATA* probdata, /**< problem data */
186  int* types, /**< types of elements */
187  SCIP_Real* xs, /**< x coordinate of each element */
188  SCIP_Real* ys, /**< y coordinate of each element */
189  SCIP_Bool* ispacked, /**< checks whether an element has been packed (might be NULL) */
190  int nelems /**< total number of elements */
191  )
192 {
193  SCIP_CONS** conss;
194  SCIP_PATTERN* pattern;
195  SCIP_VAR* var;
196  char name[SCIP_MAXSTRLEN];
197  char strtmp[SCIP_MAXSTRLEN];
198  int i;
199 
200  assert(probdata != NULL);
201  assert(types != NULL);
202  assert(xs != NULL);
203  assert(ys != NULL);
204  assert(nelems > 0);
205 
206  conss = SCIPprobdataGetPatternConss(probdata);
207  assert(conss != NULL);
208 
209  /* create rectangular pattern */
210  SCIP_CALL( SCIPpatternCreateRectangular(scip, &pattern) );
211 
212  /* create variable name */
213  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "r");
214  for( i = 0; i < nelems; ++i )
215  {
216  if( ispacked == NULL || ispacked[i] )
217  {
218  (void) SCIPsnprintf(strtmp, SCIP_MAXSTRLEN, "_%d", types[i]);
219  (void) strcat(name, strtmp);
220  SCIP_CALL( SCIPpatternAddElement(pattern, types[i], xs[i], ys[i]) );
221  }
222  }
223 
224  /* mark pattern to be packable */
226 
227  /* create and add variable */
228  SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, SCIPinfinity(scip), 1.0, SCIP_VARTYPE_INTEGER) );
232  SCIP_CALL( SCIPaddPricedVar(scip, var, 1.0) );
233  SCIPdebugMsg(scip, "added variable %s\n", name);
234 
235  /* add coefficients */
236  for( i = 0; i < nelems; ++i )
237  {
238  if( ispacked == NULL || ispacked[i] )
239  {
240  assert(types[i] >= 0 && types[i] < SCIPprobdataGetNTypes(probdata));
241  SCIP_CALL( SCIPaddCoefLinear(scip, conss[types[i]], var, 1.0) );
242  }
243  }
244 
245  /* add pattern and variable to the problem data */
246  SCIP_CALL( SCIPprobdataAddVar(scip, probdata, pattern, var) );
247 
248  /* release memory */
249  SCIP_CALL( SCIPreleaseVar(scip, &var) );
250  SCIPpatternRelease(scip, &pattern);
251 
252  return SCIP_OKAY;
253 }
254 
255 /* extracts and adds a variable with (hopefully) negative reduced costs */
256 static
258  SCIP* scip, /**< SCIP data structure */
259  SCIP_PROBDATA* probdata, /**< problem data */
260  SCIP* subscip, /**< sub-SCIP data structure */
261  SCIP_VAR** x, /**< x variables of sub-SCIP */
262  SCIP_VAR** y, /**< y variables of sub-SCIP */
263  SCIP_VAR** w, /**< w variables of sub-SCIP */
264  int* types, /**< type corresponding to each variable */
265  int nvars, /**< number of variables */
266  SCIP_Bool* success /**< pointer to store if we could add at least one variable with negative reduced costs */
267  )
268 {
269  SCIP_SOL* sol;
270  SCIP_Real* xs;
271  SCIP_Real* ys;
272  int* selectedtypes;
273  int nselected;
274  int i;
275 
276  assert(success != NULL);
277 
278  if( SCIPgetNSols(subscip) == 0 )
279  {
280  *success = FALSE;
281  return SCIP_OKAY;
282  }
283 
284  sol = SCIPgetBestSol(subscip);
285  assert(sol != NULL);
286  SCIPdebugMsg(scip, "found column with reduced cost = %f\n", 1.0 + SCIPgetSolOrigObj(subscip, sol));
287 
288  /* reduced cost is non-negative */
289  if( SCIPisFeasGE(subscip, 1.0 + SCIPgetSolOrigObj(subscip, sol), 0.0) )
290  {
291  *success = FALSE;
292  return SCIP_OKAY;
293  }
294  else
295  *success = TRUE;
296 
297  /* allocate memory */
298  SCIP_CALL( SCIPallocBufferArray(scip, &selectedtypes, nvars) );
299  SCIP_CALL( SCIPallocBufferArray(scip, &xs, nvars) );
300  SCIP_CALL( SCIPallocBufferArray(scip, &ys, nvars) );
301 
302  /* scan which circles have been selected */
303  nselected = 0;
304  for( i = 0; i < nvars; ++i )
305  {
306  SCIP_Real solval = SCIPgetSolVal(subscip, sol, w[i]);
307 
308  if( solval >= 0.5 )
309  {
310  selectedtypes[nselected] = types[i];
311  xs[nselected] = SCIPgetSolVal(subscip, sol, x[i]);
312  ys[nselected] = SCIPgetSolVal(subscip, sol, y[i]);
313  ++nselected;
314  }
315  }
316  assert(nselected > 0); /* otherwise the reduced cost can not be negative */
317 
318  /* add variable to main SCIP */
319  SCIP_CALL( addVariable(scip, probdata, selectedtypes, xs, ys, NULL, nselected) );
320 
321  /* free memory */
322  SCIPfreeBufferArray(scip, &ys);
323  SCIPfreeBufferArray(scip, &xs);
324  SCIPfreeBufferArray(scip, &selectedtypes);
325 
326  return SCIP_OKAY;
327 }
328 
329 /** array to compute the score of each element */
330 static
332  SCIP* scip, /**< SCIP data structure */
333  SCIP_Real* rexts, /**< external radii for each type */
334  SCIP_RANDNUMGEN* randnumgen, /**< random number generator */
335  int* elements, /**< type of each element */
336  int nelements, /**< total number of elements */
337  SCIP_Real* lambdas, /**< dual multipliers for each type */
338  SCIP_Real* scores, /**< array to store the score of each element */
339  int iter, /**< iteration round */
340  int iterlim /**< total iteration limit */
341  )
342 {
343  int i;
344 
345  assert(iter < iterlim);
346 
347  for( i = 0; i < nelements; ++i )
348  {
349  int elemtype = elements[i];
350  SCIP_Real rext = rexts[elemtype];
351 
352  /* use items with largest multipliers first */
353  if( iter == 0 )
354  scores[i] = lambdas[elemtype];
355 
356  /* use largest elements first */
357  else if( iter == 1 )
358  scores[i] = rext;
359 
360  /* use smallest elements first */
361  else if( iter == 2 )
362  scores[i] = -rext;
363 
364  /* use [0,1] * radius^2 */
365  else if( iter <= iterlim * 0.1 )
366  scores[i] = SCIPrandomGetReal(randnumgen, 0.0, 1.0) * rext * rext;
367 
368  /* use [0,1] * radius * lambda */
369  else if( iter <= iterlim * 0.4 )
370  scores[i] = SCIPrandomGetReal(randnumgen, 0.0, 1.0) * rext * lambdas[elemtype];
371 
372  /* use [-1,1] * lambda / radius */
373  else if( iter <= iterlim * 0.8 )
374  scores[i] = SCIPrandomGetReal(randnumgen, -1.0, 1.0) * rext * lambdas[elemtype];
375 
376  /* use a random order */
377  else
378  scores[i] = SCIPrandomGetReal(randnumgen, 0.0, 1.0);
379  }
380 }
381 
382 /** tries to find a column with negative reduced cost by using a greedy packing heuristic */
383 static
385  SCIP* scip, /**< SCIP data structure */
386  SCIP_PROBDATA* probdata, /**< problem data */
387  SCIP_PRICERDATA* pricerdata, /**< pricer data */
388  SCIP_Real* lambdas, /**< dual multipliers for pattern constraints */
389  SCIP_Real timelim, /**< time limit */
390  int iterlim, /**< iteration limit */
391  SCIP_Bool* addedvar /**< pointer to store whether a variable with negative reduced cost has been added */
392  )
393 {
394  SCIP_Real* scores;
395  SCIP_Real* rexts;
396  SCIP_Real* xs;
397  SCIP_Real* ys;
398  SCIP_Bool* ispacked;
399  int* demands;
400  int* elements;
401  SCIP_Real width;
402  SCIP_Real height;
403  SCIP_Real timestart;
404  SCIP_Real bestredcosts;
405  SCIP_Real bestvol;
406  int nelements;
407  int ntypes;
408  int npacked;
409  int niters;
410  int t;
411 
412  assert(pricerdata != NULL);
413  assert(addedvar != NULL);
414 
415  *addedvar = FALSE;
416  niters = 0;
417  timestart = SCIPgetTotalTime(scip);
418  bestredcosts = 0.0;
419  bestvol = 0.0;
420 
421  /* get problem data */
422  rexts = SCIPprobdataGetRexts(probdata);
423  demands = SCIPprobdataGetDemands(probdata);
424  width = SCIPprobdataGetWidth(probdata);
425  height = SCIPprobdataGetHeight(probdata);
426  ntypes = SCIPprobdataGetNTypes(probdata);
427 
428  /* compute the total number of elements that need to be considered */
429  nelements = 0;
430  for( t = 0; t < ntypes; ++t )
431  nelements += getNCircles(scip, rexts[t], demands[t], width, height, lambdas[t]);
432 
433  /* allocate enough memory */
434  SCIP_CALL( SCIPallocBufferArray(scip, &elements, nelements) );
435  SCIP_CALL( SCIPallocBufferArray(scip, &xs, nelements) );
436  SCIP_CALL( SCIPallocBufferArray(scip, &ys, nelements) );
437  SCIP_CALL( SCIPallocBufferArray(scip, &scores, nelements) );
438  SCIP_CALL( SCIPallocBufferArray(scip, &ispacked, nelements) );
439 
440  /* create entry for each element */
441  nelements = 0;
442  for( t = 0; t < ntypes; ++t )
443  {
444  int i;
445  int n;
446 
447  n = getNCircles(scip, rexts[t], demands[t], width, height, lambdas[t]);
448 
449  for( i = 0; i < n; ++i )
450  {
451  elements[nelements] = t;
452  ++nelements;
453  }
454  }
455 
456  /* main loop */
457  while( niters < iterlim
458  && SCIPgetTotalTime(scip) - timestart <= timelim
459  && !SCIPisStopped(scip) )
460  {
461  SCIP_Real redcosts = 1.0;
462  SCIP_Real vol = 0.0;
463  int i;
464 
465  /* compute scores */
466  computeScores(scip, rexts, pricerdata->randnumgen, elements, nelements, lambdas, scores, niters, iterlim);
467 
468  /* sort elements in non-increasing order */
469  SCIPsortDownRealInt(scores, elements, nelements);
470 
471  /* call heuristic */
472  SCIPpackCirclesGreedy(scip, rexts, xs, ys, -1.0, width, height, ispacked, elements, nelements,
473  SCIP_PATTERNTYPE_RECTANGULAR, &npacked, niters);
474 
475  /* compute reduced costs */
476  for( i = 0; i < nelements; ++i )
477  {
478  if( ispacked[i] )
479  {
480  redcosts -= lambdas[elements[i]];
481  vol += rexts[elements[i]];
482  }
483  }
484 
485  /* add pattern if reduced costs are negative */
486  if( SCIPisFeasLT(scip, redcosts, bestredcosts) || (SCIPisGT(scip, vol, bestvol) && SCIPisFeasNegative(scip, redcosts)) )
487  {
488  SCIPdebugMsg(scip, "pricing heuristic found column with reduced costs %g and volume %g after %d iterations\n", redcosts, vol, niters + 1);
489 
490  SCIP_CALL( addVariable(scip, probdata, elements, xs, ys, ispacked, nelements) );
491  *addedvar = TRUE;
492  bestredcosts = MIN(bestredcosts, redcosts);
493  bestvol = MAX(bestvol, vol);
494  }
495 
496  ++niters;
497  }
498 
499  /* free memory */
500  SCIPfreeBufferArray(scip, &ispacked);
501  SCIPfreeBufferArray(scip, &scores);
502  SCIPfreeBufferArray(scip, &ys);
503  SCIPfreeBufferArray(scip, &xs);
504  SCIPfreeBufferArray(scip, &elements);
505 
506  return SCIP_OKAY;
507 }
508 
509 /** auxiliary function for solving the pricing problem exactly */
510 static
512  SCIP* scip, /**< SCIP data structure */
513  SCIP_PROBDATA* probdata, /**< problem data */
514  SCIP_Real* lambdas, /**< dual multipliers for pattern constraints */
515  SCIP_Real timelim, /**< time limit */
516  SCIP_Longint nodelim, /**< node limit */
517  SCIP_Bool* addedvar, /**< pointer to store whether a variable with negative reduced cost has been added */
518  SCIP_STATUS* solstat, /**< pointer to store the solution status */
519  SCIP_Real* dualbound /**< pointer to store the dual bound */
520  )
521 {
522  SCIP* subscip;
523  SCIP_VAR** x;
524  SCIP_VAR** y;
525  SCIP_VAR** w;
526  SCIP_VAR* quadvars1[6];
527  SCIP_VAR* quadvars2[6];
528  SCIP_VAR* linvars[2];
529  SCIP_Real quadcoefs[6];
530  SCIP_Real lincoefs[2];
531  char name[SCIP_MAXSTRLEN];
532  SCIP_CONS* cons;
533  SCIP_Real* rexts;
534  SCIP_Real* vols;
535  int* types;
536  int* demands;
537  SCIP_Real width;
538  SCIP_Real height;
539  int nvars;
540  int ntypes;
541  int pos;
542  int t;
543  int i;
544 
545  assert(probdata != NULL);
546  assert(lambdas != NULL);
547  assert(nodelim >= -1L);
548  assert(addedvar != NULL);
549  assert(solstat != NULL);
550  assert(dualbound != NULL);
551 
552  *addedvar = FALSE;
553  *solstat = SCIP_STATUS_UNKNOWN;
554  *dualbound = -SCIPinfinity(scip);
555 
556  /* no time left */
557  if( timelim <= 0.0 )
558  return SCIP_OKAY;
559 
560  width = SCIPprobdataGetWidth(probdata);
561  height = SCIPprobdataGetHeight(probdata);
562  ntypes = SCIPprobdataGetNTypes(probdata);
563  rexts = SCIPprobdataGetRexts(probdata);
564  demands = SCIPprobdataGetDemands(probdata);
565  assert(ntypes > 0);
566 
567  /* create a sub-SCIP */
568  SCIP_CALL( SCIPcreate(&subscip) );
569  SCIP_CALL( SCIPcreateProbBasic(subscip, "pricing problem") );
571 
572  /* set heuristics to aggressive */
574  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/mpec/freq", -1) );
575 
576 #ifndef SCIP_DEBUG
577  SCIPsetMessagehdlrQuiet(subscip, TRUE);
578 #endif
579 
580  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelim) );
581  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelim) );
582 
583  /* count how many variables are needed */
584  nvars = 0;
585  for( t = 0; t < ntypes; ++t )
586  {
587  nvars += getNCircles(scip, rexts[t], demands[t], width, height, lambdas[t]);
588  SCIPdebugMsg(scip, "use %d/%d circles of type %d\n", getNCircles(scip, rexts[t], demands[t], width, height, lambdas[t]), demands[t], t);
589  }
590  assert(nvars > 0);
591 
592  /* allocate enough memory */
593  SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &types, nvars) );
594  SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &vols, nvars) );
595  SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &x, nvars) );
596  SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &y, nvars) );
597  SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &w, nvars) );
598 
599  /* create variables */
600  pos = 0;
601  for( t = 0; t < ntypes; ++t )
602  {
603  SCIP_Real obj = lambdas[t];
604  int ncircles = getNCircles(scip, rexts[t], demands[t], width, height, lambdas[t]);
605  int k;
606 
607  for( k = 0; k < ncircles; ++k )
608  {
609  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "x_%d", pos);
610  SCIP_CALL( SCIPcreateVarBasic(subscip, &x[pos], name, rexts[t], width - rexts[t], 0.0, SCIP_VARTYPE_CONTINUOUS) );
611  SCIP_CALL( SCIPaddVar(subscip, x[pos]) );
612 
613  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "y_%d", pos);
614  SCIP_CALL( SCIPcreateVarBasic(subscip, &y[pos], name, rexts[t], height - rexts[t], 0.0, SCIP_VARTYPE_CONTINUOUS) );
615  SCIP_CALL( SCIPaddVar(subscip, y[pos]) );
616 
617  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "w_%d", pos);
618  SCIP_CALL( SCIPcreateVarBasic(subscip, &w[pos], name, 0.0, 1.0, -obj, SCIP_VARTYPE_BINARY) );
619  SCIP_CALL( SCIPaddVar(subscip, w[pos]) );
620 
621  vols[pos] = SQR(rexts[t]) * M_PI;
622  types[pos] = t;
623  ++pos;
624  }
625  }
626 
627  /* create non-overlapping constraints */
628  for( i = 0; i < nvars; ++i )
629  {
630  int j;
631  int type1;
632 
633  type1 = types[i];
634  assert(type1 >= 0 && type1 < ntypes);
635 
636  for( j = i+1; j < nvars; ++j )
637  {
638  SCIP_Real c;
639  int types2;
640 
641  types2 = types[j];
642  assert(types2 >= 0 && types2 < ntypes);
643 
644  c = (rexts[type1] + rexts[types2]) * (rexts[type1] + rexts[types2]);
645 
646  /* linear part */
647  linvars[0] = w[i]; lincoefs[0] = -c;
648  linvars[1] = w[j]; lincoefs[1] = -c;
649 
650  /* quadratic part */
651  quadvars1[0] = x[i]; quadvars2[0] = x[i]; quadcoefs[0] = 1.0;
652  quadvars1[1] = x[i]; quadvars2[1] = x[j]; quadcoefs[1] = -2.0;
653  quadvars1[2] = x[j]; quadvars2[2] = x[j]; quadcoefs[2] = 1.0;
654  quadvars1[3] = y[i]; quadvars2[3] = y[i]; quadcoefs[3] = 1.0;
655  quadvars1[4] = y[i]; quadvars2[4] = y[j]; quadcoefs[4] = -2.0;
656  quadvars1[5] = y[j]; quadvars2[5] = y[j]; quadcoefs[5] = 1.0;
657 
658  /* create quadratic constraint */
659  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "nonoverlap_%d_%d", i, j);
660  SCIP_CALL( SCIPcreateConsQuadraticNonlinear(subscip, &cons, name, 2, linvars, lincoefs, 6, quadvars1, quadvars2,
661  quadcoefs, -c, SCIPinfinity(subscip), TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
662 
663  /* add and release constraint */
664  SCIP_CALL( SCIPaddCons(subscip, cons) );
665  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
666  }
667  }
668 
669  /* w_i >= w_{i+1} if type(i) == type(i+1) */
670  for( i = 0; i < nvars - 1; ++i )
671  {
672  int type1;
673  int type2;
674 
675  type1 = types[i];
676  type2 = types[i+1];
677 
678  if( type1 != type2 )
679  continue;
680 
681  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cons_w_%d_%d", i, i+1);
682 
683  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &cons, name, 0, NULL, NULL,
684  0.0, SCIPinfinity(subscip)) );
685  SCIP_CALL( SCIPaddCoefLinear(subscip, cons, w[i], 1.0) );
686  SCIP_CALL( SCIPaddCoefLinear(subscip, cons, w[i+1], -1.0) );
687 
688  /* add and release constraint */
689  SCIP_CALL( SCIPaddCons(subscip, cons) );
690  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
691  }
692 
693  /* x_i <= x_{i+1} if type(i) == type(i+1) */
694  for( i = 0; i < nvars - 1; ++i )
695  {
696  int type1;
697  int type2;
698 
699  type1 = types[i];
700  type2 = types[i+1];
701 
702  if( type1 != type2 )
703  continue;
704 
705  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symmetry_%d_%d", i, i+1);
706  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &cons, name, 0, NULL, NULL,
707  0.0, SCIPinfinity(subscip)) );
708  SCIP_CALL( SCIPaddCoefLinear(subscip, cons, x[i], -1.0) );
709  SCIP_CALL( SCIPaddCoefLinear(subscip, cons, x[i+1], 1.0) );
710 
711  /* add and release constraint */
712  SCIP_CALL( SCIPaddCons(subscip, cons) );
713  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
714  }
715 
716  /* sum_{i} vol_i w_i <= W*H */
717  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "volume");
718  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &cons, name, nvars, w, vols, 0.0, width * height) );
719  SCIP_CALL( SCIPaddCons(subscip, cons) );
720  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
721 
722  /* solve the pricing problem */
723  SCIPdebugMsg(scip, "----------------------- solve pricing problem -----------------------\n");
724  SCIP_CALL( SCIPsolve(subscip) );
725  SCIPdebugMsg(scip, "---------------------------------------------------------------------\n");
726 
727  /* check solution status */
728  *dualbound = SCIPgetDualbound(subscip);
729  *solstat = SCIPgetStatus(subscip);
730 
731  /* add variable with negative reduced costs */
732  SCIP_CALL( extractVariablesMINLP(scip, probdata, subscip, x, y, w, types, nvars, addedvar) );
733 
734  /* free variables */
735  for( i = 0; i < nvars; ++i )
736  {
737  SCIP_CALL( SCIPreleaseVar(subscip, &w[i]) );
738  SCIP_CALL( SCIPreleaseVar(subscip, &y[i]) );
739  SCIP_CALL( SCIPreleaseVar(subscip, &x[i]) );
740  }
741 
742  /* free memory */
743  SCIPfreeBlockMemoryArray(subscip, &w, nvars);
744  SCIPfreeBlockMemoryArray(subscip, &y, nvars);
745  SCIPfreeBlockMemoryArray(subscip, &x, nvars);
746  SCIPfreeBlockMemoryArray(subscip, &vols, nvars);
747  SCIPfreeBlockMemoryArray(subscip, &types, nvars);
748  SCIP_CALL( SCIPfree(&subscip) );
749 
750  return SCIP_OKAY;
751 }
752 
753 /**@} */
754 
755 /**name Callback methods
756  *
757  * @{
758  */
759 
760 /** destructor of variable pricer to free user data (called when SCIP is exiting) */
761 static
762 SCIP_DECL_PRICERFREE(pricerFreeRingpacking)
763 { /*lint --e{715}*/
764  SCIP_PRICERDATA* pricerdata;
765 
766  pricerdata = SCIPpricerGetData(pricer);
767  assert(pricerdata->randnumgen == NULL);
768 
769  SCIPfreeBlockMemoryNull(scip, &pricerdata);
770 
771  return SCIP_OKAY;
772 }
773 
774 /** initialization method of variable pricer (called after problem was transformed and pricer is active) */
775 static
776 SCIP_DECL_PRICERINIT(pricerInitRingpacking)
777 { /*lint --e{715}*/
778  SCIP_PRICERDATA* pricerdata = SCIPpricerGetData(pricer);
779  assert(pricerdata != NULL);
780  assert(pricerdata->randnumgen == NULL);
781 
782  /* create random number generator */
783  SCIP_CALL( SCIPcreateRandom(scip, &pricerdata->randnumgen, 0, TRUE) );
784 
785  return SCIP_OKAY;
786 }
787 
788 /** deinitialization method of variable pricer (called before transformed problem is freed and pricer is active) */
789 static
790 SCIP_DECL_PRICEREXIT(pricerExitRingpacking)
791 { /*lint --e{715}*/
792  SCIP_PRICERDATA* pricerdata = SCIPpricerGetData(pricer);
793  assert(pricerdata != NULL);
794  assert(pricerdata->randnumgen != NULL);
795 
796  SCIPfreeRandom(scip, &pricerdata->randnumgen);
797 
798  return SCIP_OKAY;
799 }
800 
801 /** reduced cost pricing method of variable pricer for feasible LPs */
802 static
803 SCIP_DECL_PRICERREDCOST(pricerRedcostRingpacking)
804 { /*lint --e{715}*/
805  SCIP_PRICERDATA* pricerdata;
806  SCIP_PROBDATA* probdata;
807  SCIP_CONS** conss;
808  SCIP_Real* lambdas;
809  SCIP_STATUS solstat;
810  SCIP_Real redcostslb;
811  SCIP_Real nlptimelimit;
812  SCIP_Real heurtimelimit;
813  SCIP_Real totaltilim;
814  SCIP_Bool success;
815  int t;
816 
817  pricerdata = SCIPpricerGetData(pricer);
818  assert(pricerdata != NULL);
819  probdata = SCIPgetProbData(scip);
820  assert(probdata != NULL);
821 
822  /* switch to price-and-price algorithm when dual bound has become invalid */
824 
825  /* only run pricer in the root node */
826  if( SCIPgetDepth(scip) > 0 )
827  {
829  *result = SCIP_SUCCESS;
830  return SCIP_OKAY;
831  }
832 
833  conss = SCIPprobdataGetPatternConss(probdata);
834  assert(conss != NULL);
835 
836  /* collect dual multipliers */
837  SCIP_CALL( SCIPallocBufferArray(scip, &lambdas, SCIPprobdataGetNTypes(probdata)) );
838  for( t = 0; t < SCIPprobdataGetNTypes(probdata); ++t )
839  {
840  assert(conss[t] != NULL);
841  assert( !strncmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[t])), "linear", 6) );
842 
843  lambdas[t] = SCIPgetDualsolLinear(scip, conss[t]);
844  SCIPdebugMsg(scip, "lambda_%d = %g\n", t, lambdas[t]);
845  }
846 
847  /* collect working limits */
848  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &totaltilim) );
849 
850  /* solve pricing problem with heuristic */
851  heurtimelimit = MIN(pricerdata->heurtilim, totaltilim - SCIPgetSolvingTime(scip)); /*lint !e666*/
852  pricerdata->timeleft += SCIPgetSolvingTime(scip);
853  SCIP_CALL( solvePricingHeuristic(scip, probdata, pricerdata, lambdas, heurtimelimit, pricerdata->heuriterlim, &success) );
854  pricerdata->timeleft -= SCIPgetSolvingTime(scip);
855 
856  if( success )
857  {
858  *result = SCIP_SUCCESS;
859  }
860  /* solve pricing problem as MINLP if heuristic was not successful and dual bound is still valid */
861  else if ( !SCIPprobdataIsDualboundInvalid(probdata) )
862  {
863  nlptimelimit = MIN3(pricerdata->timeleft, pricerdata->nlptilim, totaltilim - SCIPgetSolvingTime(scip)); /*lint !e666*/
864  pricerdata->timeleft += SCIPgetSolvingTime(scip);
865  SCIP_CALL( solvePricingMINLP(scip, probdata, lambdas, nlptimelimit, pricerdata->nlpnodelim, &success, &solstat,
866  &redcostslb) );
867  pricerdata->timeleft -= SCIPgetSolvingTime(scip);
868  redcostslb += 1.0;
869  SCIPdebugMsg(scip, "result of pricing MINLP: addedvar=%u soltat=%d\n", success, solstat);
870 
871  /* check whether pricing problem could be solved to optimality */
872  if( SCIPisFeasGE(scip, redcostslb, 0.0) )
873  {
874  *lowerbound = SCIPgetLPObjval(scip);
875  SCIPinfoMessage(scip, NULL, "+++++++++++++ LP(master) = ceil(%g) = %g\n", *lowerbound, SCIPfeasCeil(scip, *lowerbound));
876  }
877  else
878  {
879  /* compute Farley's bound */
880  *lowerbound = SCIPgetLPObjval(scip) / (1.0 - redcostslb);
881  SCIPinfoMessage(scip, NULL, "+++++++++++++ Farley's bound = ceil(%g/%g) = %g\n", SCIPgetLPObjval(scip), 1.0 - redcostslb,
882  SCIPfeasCeil(scip, *lowerbound));
883  }
884  *lowerbound = SCIPfeasCeil(scip, *lowerbound);
885 
886  /* updates dual bound that is stored in the problem data */
887  SCIPprobdataUpdateDualbound(scip, probdata, *lowerbound);
888 
889  /* MINLP found an improving column or pricing problem could have been solved to optimality */
890  if( success || solstat == SCIP_STATUS_OPTIMAL || SCIPisFeasGE(scip, redcostslb, 0.0) )
891  *result = SCIP_SUCCESS;
892  }
893 
894  /* free memory */
895  SCIPfreeBufferArray(scip, &lambdas);
896 
897  return SCIP_OKAY;
898 }
899 
900 /** farkas pricing method of variable pricer for infeasible LPs */
901 static
902 SCIP_DECL_PRICERFARKAS(pricerFarkasRingpacking)
903 { /*lint --e{715}*/
904 
905  /* farkas pricing should not happen */
906  SCIPABORT();
907 
908  return SCIP_OKAY;
909 }
910 
911 /**@} */
912 
913 
914 /**@name Interface methods
915  *
916  * @{
917  */
918 
919 /** creates the ringpacking variable pricer and includes it in SCIP */
921  SCIP* scip /**< SCIP data structure */
922  )
923 {
924  SCIP_PRICERDATA* pricerdata;
925  SCIP_PRICER* pricer;
926 
927  /* create ringpacking variable pricer data */
928  SCIP_CALL( SCIPallocBlockMemory(scip, &pricerdata) );
929  BMSclearMemory(pricerdata);
930 
931  /* include variable pricer */
933  pricerRedcostRingpacking, pricerFarkasRingpacking, pricerdata) );
934 
935  SCIP_CALL( SCIPsetPricerFree(scip, pricer, pricerFreeRingpacking) );
936  SCIP_CALL( SCIPsetPricerInit(scip, pricer, pricerInitRingpacking) );
937  SCIP_CALL( SCIPsetPricerExit(scip, pricer, pricerExitRingpacking) );
938 
939  /* variable pricer parameters */
941  "ringpacking/pricing/nlptilim",
942  "time limit for each pricing NLP",
943  &pricerdata->nlptilim, FALSE, DEFAULT_PRICING_NLPTILIM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
944 
946  "ringpacking/pricing/nlpnodelim",
947  "node limit for each pricing NLP",
948  &pricerdata->nlpnodelim, FALSE, DEFAULT_PRICING_NLPNODELIM, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
949 
951  "ringpacking/pricing/heurtilim",
952  "time limit for each heuristic pricing",
953  &pricerdata->heurtilim, FALSE, DEFAULT_PRICING_HEURTILIM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
954 
956  "ringpacking/pricing/heuriterlim",
957  "iteration limit for each heuristic pricing",
958  &pricerdata->heuriterlim, FALSE, DEFAULT_PRICING_HEURITERLIM, 0, INT_MAX, NULL, NULL) );
959 
961  "ringpacking/pricing/totaltilim",
962  "total time limit for all pricing NLPs and heuristic calls",
963  &pricerdata->timeleft, FALSE, DEFAULT_PRICING_TOTALTILIM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
964 
965  return SCIP_OKAY;
966 }
967 
968 /** added problem specific data to pricer and activates pricer */
970  SCIP* scip /**< SCIP data structure */
971  )
972 {
973  SCIP_PRICER* pricer;
974 
975  assert(scip != NULL);
976 
977  pricer = SCIPfindPricer(scip, PRICER_NAME);
978  assert(pricer != NULL);
979 
980  /* activate pricer */
981  SCIP_CALL( SCIPactivatePricer(scip, pricer) );
982 
983  return SCIP_OKAY;
984 }
985 
986 /**@} */
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
static void computeScores(SCIP *scip, SCIP_Real *rexts, SCIP_RANDNUMGEN *randnumgen, int *elements, int nelements, SCIP_Real *lambdas, SCIP_Real *scores, int iter, int iterlim)
Definition: pricer_rpa.c:331
#define DEFAULT_PRICING_TOTALTILIM
Definition: pricer_rpa.c:92
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
#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
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)
static int getNCircles(SCIP *scip, SCIP_Real rext, int demand, SCIP_Real width, SCIP_Real height, SCIP_Real lambda)
Definition: pricer_rpa.c:137
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
#define SCIP_MAXSTRLEN
Definition: def.h:302
Problem data for ringpacking problem.
#define PRICER_DESC
Definition: pricer_rpa.c:83
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1254
SCIP_RETCODE SCIPpricerRpaActivate(SCIP *scip)
Definition: pricer_rpa.c:969
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:906
int * SCIPprobdataGetDemands(SCIP_PROBDATA *probdata)
#define FALSE
Definition: def.h:96
void SCIPprobdataInvalidateDualbound(SCIP *scip, SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
static SCIP_RETCODE extractVariablesMINLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP *subscip, SCIP_VAR **x, SCIP_VAR **y, SCIP_VAR **w, int *types, int nvars, SCIP_Bool *success)
Definition: pricer_rpa.c:257
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10764
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
Definition: scip_pricer.c:311
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
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 DEFAULT_PRICING_HEURITERLIM
Definition: pricer_rpa.c:91
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
Definition: pricer.c:510
void SCIPvarMarkDeletable(SCIP_VAR *var)
Definition: var.c:17493
SCIP_RETCODE SCIPsetPricerExit(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXIT((*pricerexit)))
Definition: scip_pricer.c:247
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
#define SCIP_LONGINT_MAX
Definition: def.h:172
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:292
#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 SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
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
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:180
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPprobdataIsDualboundInvalid(SCIP_PROBDATA *probdata)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
static SCIP_DECL_PRICERREDCOST(pricerRedcostRingpacking)
Definition: pricer_rpa.c:803
SCIP_VAR * w
Definition: circlepacking.c:67
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)
static SCIP_RETCODE solvePricingHeuristic(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PRICERDATA *pricerdata, SCIP_Real *lambdas, SCIP_Real timelim, int iterlim, SCIP_Bool *addedvar)
Definition: pricer_rpa.c:384
int SCIPprobdataGetNTypes(SCIP_PROBDATA *probdata)
SCIP_Real SCIPprobdataGetHeight(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2622
#define PRICER_NAME
Definition: pricer_rpa.c:82
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4184
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2778
SCIP_Real SCIPgetDualsolLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPincludePricerBasic(SCIP *scip, SCIP_PRICER **pricerptr, const char *name, const char *desc, int priority, SCIP_Bool delay, SCIP_DECL_PRICERREDCOST((*pricerredcost)), SCIP_DECL_PRICERFARKAS((*pricerfarkas)), SCIP_PRICERDATA *pricerdata)
Definition: scip_pricer.c:127
static SCIP_RETCODE addVariable(SCIP *scip, SCIP_PROBDATA *probdata, int *types, SCIP_Real *xs, SCIP_Real *ys, SCIP_Bool *ispacked, int nelems)
Definition: pricer_rpa.c:183
#define PRICER_PRIORITY
Definition: pricer_rpa.c:84
SCIP_Real SCIPgetDualbound(SCIP *scip)
#define DEFAULT_PRICING_NLPNODELIM
Definition: pricer_rpa.c:89
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:483
pattern data for ringpacking problem
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
#define SCIP_CALL(x)
Definition: def.h:393
#define SCIPfreeBlockMemoryNull(scip, ptr)
Definition: scip_mem.h:109
SCIP_RETCODE SCIPsetPricerInit(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINIT((*pricerinit)))
Definition: scip_pricer.c:223
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
Definition: scip_pricer.c:384
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIP_Bool
Definition: def.h:93
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
#define DEFAULT_PRICING_NLPTILIM
Definition: pricer_rpa.c:88
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67
SCIP_RETCODE SCIPincludePricerRpa(SCIP *scip)
Definition: pricer_rpa.c:920
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
static SCIP_DECL_PRICERINIT(pricerInitRingpacking)
Definition: pricer_rpa.c:776
#define MAX(x, y)
Definition: tclique_def.h:92
void SCIPsetMessagehdlrQuiet(SCIP *scip, SCIP_Bool quiet)
Definition: scip_message.c:108
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8114
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:199
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2214
#define PRICER_DELAY
Definition: pricer_rpa.c:85
SCIP_RETCODE SCIPpatternCreateRectangular(SCIP *scip, SCIP_PATTERN **pattern)
Definition: pattern.c:107
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1444
SCIP_Real SCIPprobdataGetWidth(SCIP_PROBDATA *probdata)
#define BMSclearMemory(ptr)
Definition: memory.h:131
static SCIP_DECL_PRICEREXIT(pricerExitRingpacking)
Definition: pricer_rpa.c:790
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10034
#define M_PI
Definition: pricer_rpa.c:97
#define SCIP_REAL_MAX
Definition: def.h:187
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1741
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2313
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:53
void SCIPprobdataUpdateDualbound(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real dualbound)
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
int ncircles
Definition: circlepacking.c:56
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
#define SCIP_Real
Definition: def.h:186
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:703
SCIP_VAR ** y
Definition: circlepacking.c:64
SCIP_RETCODE SCIPvarSetInitial(SCIP_VAR *var, SCIP_Bool initial)
Definition: var.c:17347
#define DEFAULT_PRICING_HEURTILIM
Definition: pricer_rpa.c:90
void SCIPpatternSetPackableStatus(SCIP_PATTERN *pattern, SCIP_PACKABLE packable)
Definition: pattern.c:345
static SCIP_DECL_PRICERFREE(pricerFreeRingpacking)
Definition: pricer_rpa.c:762
#define SCIP_Longint
Definition: def.h:171
SCIP_Real SCIPgetTotalTime(SCIP *scip)
Definition: scip_timing.c:351
struct SCIP_PricerData SCIP_PRICERDATA
Definition: type_pricer.h:45
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE solvePricingMINLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real *lambdas, SCIP_Real timelim, SCIP_Longint nodelim, SCIP_Bool *addedvar, SCIP_STATUS *solstat, SCIP_Real *dualbound)
Definition: pricer_rpa.c:511
SCIP_RETCODE SCIPvarSetRemovable(SCIP_VAR *var, SCIP_Bool removable)
Definition: var.c:17363
Ringpacking variable pricer.
SCIP_RETCODE SCIPprobdataAddVar(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_VAR *var)
#define SCIPABORT()
Definition: def.h:365
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
default SCIP plugins
static SCIP_DECL_PRICERFARKAS(pricerFarkasRingpacking)
Definition: pricer_rpa.c:902
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
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
static SCIP_Real getDensityUb(int n)
Definition: pricer_rpa.c:127