Scippy

SCIP

Solving Constraint Integer Programs

cons_rpa.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_rpa.c
17  * @brief constraint handler for recursive circle packing
18  * @author Benjamin Mueller
19  *
20  * This constraint handler is used to store information about which (not verified) rectangular patterns have been locked
21  * and which circular patterns have not been tried to be verified yet.
22  *
23  * @todo Is it enough the lock the unverified circular pattern variables only in the positive direction?
24  * @todo remove all unnecessary callbacks and defines
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 
29 #include <assert.h>
30 #include <string.h>
31 
32 #include "cons_rpa.h"
33 #include "probdata_rpa.h"
34 #include "pattern.h"
35 
36 
37 /* fundamental constraint handler properties */
38 #define CONSHDLR_NAME "rpa"
39 #define CONSHDLR_DESC "ringpacking constraint handler"
40 #define CONSHDLR_ENFOPRIORITY 1 /**< priority of the constraint handler for constraint enforcing */
41 #define CONSHDLR_CHECKPRIORITY -1 /**< priority of the constraint handler for checking feasibility */
42 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
43  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
44 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
45 
46 /* optional constraint handler properties */
47 /* TODO: remove properties which are never used because the corresponding routines are not supported */
48 #define CONSHDLR_SEPAPRIORITY 0 /**< priority of the constraint handler for separation */
49 #define CONSHDLR_SEPAFREQ -1 /**< frequency for separating cuts; zero means to separate only in the root node */
50 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
51 
52 #define CONSHDLR_PROPFREQ -1 /**< frequency for propagating domains; zero means only preprocessing propagation */
53 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
54 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler*/
55 
56 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
57 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
58 
59 /* new best solution event handler properties */
60 #define EVENTHDLR_NAME "bestsol"
61 #define EVENTHDLR_DESC "best solution event handler"
62 
63 /* default values of parameters */
64 #define DEFAULT_VERIFICATION_NLPTILIM 10.0 /**< time limit for each verification NLP */
65 #define DEFAULT_VERIFICATION_NLPNODELIM 10000L /**< node limit for each verification NLP */
66 #define DEFAULT_VERIFICATION_HEURTILIM 10.0 /**< time limit for heuristic verification */
67 #define DEFAULT_VERIFICATION_HEURITERLIM 1000 /**< iteration limit for each heuristic verification */
68 #define DEFAULT_VERIFICATION_TOTALTILIM 3600.0 /**< total time limit for all verification problems during the solving process */
69 
70 /*
71  * Data structures
72  */
73 
74 /** constraint handler data */
75 struct SCIP_ConshdlrData
76 {
77  SCIP_EVENTHDLR* eventhdlr; /**< event handler */
78 
79  SCIP_Bool* locked; /**< array to remember which (not verified) patterns have been locked */
80  int lockedsize; /**< size of locked array */
81  SCIP_Bool* tried; /**< array to mark circular patterns that have been tried to be verified */\
82 
83  /* parameter for verification */
84  SCIP_Real timeleft; /**< time left for solving verification problem during the solving process */
85  SCIP_Real nlptilim; /**< hard time limit for verification nlp */
86  SCIP_Real heurtilim; /**< hard time limit for verification heuristic*/
87  SCIP_Longint nlpnodelim; /**< hard node limit for verification nlp */
88  int heuriterlim; /**< hard iteration limit for verification heuristic*/
89 };
90 
91 /*
92  * Local methods
93  */
94 
95 /** auxiliary function to decide whether a proposed solution is feasible; a solution is called feasible if and only if
96  * z*_C = 0 holds for all circular patterns that are either not packable, i.e., SCIP_PACKABLE_NO or SCIP_PACKABLE_UNKNOWN
97  */
98 static
100  SCIP* scip, /**< SCIP data structure */
101  SCIP_SOL* sol /**< solution (NULL for LP solution) */
102  )
103 {
104  SCIP_PROBDATA* probdata;
105  SCIP_PATTERN** cpatterns;
106  SCIP_VAR** cvars;
107  int ncpatterns;
108  int p;
109 
110  probdata = SCIPgetProbData(scip);
111  assert(probdata != NULL);
112 
113  /* get information about circular patterns and their corresponding variables */
114  SCIPprobdataGetCInfos(probdata, &cpatterns, &cvars, &ncpatterns);
115  assert(ncpatterns > 0);
116 
117  for( p = 0; p < ncpatterns; ++p )
118  {
119  assert(cpatterns[p] != NULL);
120  assert(cvars[p] != NULL);
121 
122  /* check only circular patterns which might not be packable */
123  if( SCIPpatternGetPackableStatus(cpatterns[p]) != SCIP_PACKABLE_YES )
124  {
125  SCIP_Real solval = SCIPgetSolVal(scip, sol, cvars[p]);
126 
127  if( !SCIPisFeasZero(scip, solval) )
128  {
129  SCIPdebugMsg(scip, "solution might be infeasible because of circular pattern %d = (%g,%d)\n", p,
130  SCIPgetSolVal(scip, sol, cvars[p]), SCIPpatternGetPackableStatus(cpatterns[p]));
131  return FALSE;
132  }
133  }
134  }
135 
136  return TRUE;
137 }
138 
139 /** tries to verify a circular pattern; it first tries to call heuristic(s) and afterwards uses a verification NLP */
140 static
142  SCIP* scip, /**< SCIP data structure */
143  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
144  SCIP_PROBDATA* probdata, /**< problem data */
145  SCIP_PATTERN* pattern /**< circular pattern */
146  )
147 {
148  SCIP_Real timelimit;
149  SCIP_Real nlptimelimit;
150  SCIP_Real heurtimelimit;
151 
152  assert(probdata != NULL);
153  assert(pattern != NULL);
156 
157  /* get the total time limit */
158  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
159 
160  /* verify heuristically */
161  heurtimelimit = MIN(timelimit - SCIPgetSolvingTime(scip), conshdlrdata->heurtilim); /*lint !e666*/
162 
163  SCIPdebugMsg(scip, "call verification heuristic (%g,%d)\n", heurtimelimit, conshdlrdata->heuriterlim);
164  conshdlrdata->timeleft += SCIPgetSolvingTime(scip);
165  SCIP_CALL( SCIPverifyCircularPatternHeuristic(scip, probdata, pattern, heurtimelimit, conshdlrdata->heuriterlim) );
166  conshdlrdata->timeleft -= SCIPgetSolvingTime(scip);
167 
168  /* use verification NLP if pattern is still not verified */
170  {
171  nlptimelimit = MIN3(conshdlrdata->timeleft, timelimit - SCIPgetSolvingTime(scip), conshdlrdata->nlptilim); /*lint !e666*/
172 
173  SCIPdebugMsg(scip, "call verification NLP (%g,%lld)\n", nlptimelimit, conshdlrdata->nlpnodelim);
174  conshdlrdata->timeleft += SCIPgetSolvingTime(scip);
175  SCIP_CALL( SCIPverifyCircularPatternNLP(scip, probdata, pattern, nlptimelimit, conshdlrdata->nlpnodelim) );
176  conshdlrdata->timeleft -= SCIPgetSolvingTime(scip);
177  }
178 
179  SCIPdebugMsg(scip, "packable status? %d\n", SCIPpatternGetPackableStatus(pattern));
180  SCIPcheckPattern(scip, probdata, pattern);
181 
182  return SCIP_OKAY;
183 }
184 
185 /** auxiliary function for enforcing ringpacking constraint; the function checks whether
186  *
187  * 1. the solution is feasible; if yes -> skip
188  * 2. tries to verify an unverified circular pattern C with z*_c > 0
189  * 2a. case packable or unknown: go to 2.
190  * 2b. case not packable: fix z_C to 0 -> skip
191  * 3. fix all unverified circular patterns to 0
192  *
193  * Note that after step 3. the dual bound is not valid anymore.
194  */
195 static
197  SCIP* scip, /**< SCIP data structure */
198  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
199  SCIP_SOL* sol, /**< solution (NULL for LP solution) */
200  SCIP_RESULT* result /**< pointer to store the result */
201  )
202 {
203  SCIP_CONSHDLRDATA* conshdlrdata;
204  SCIP_PROBDATA* probdata;
205  SCIP_PATTERN** cpatterns;
206  SCIP_VAR** cvars;
207  int ncpatterns;
208  int p;
209 
210 #ifdef SCIP_DEBUG
211  SCIPdebugMsg(scip, "enforce solution:\n");
212  SCIP_CALL( SCIPprintSol(scip, sol, NULL, TRUE) );
213 #endif
214 
215  *result = SCIP_FEASIBLE;
216 
217  /* (1.) check whether the solution is already feasible */
218  if( isSolFeasible(scip, sol) )
219  return SCIP_OKAY;
220 
221  conshdlrdata = SCIPconshdlrGetData(conshdlr);
222  assert(conshdlrdata != NULL);
223  probdata = SCIPgetProbData(scip);
224  assert(probdata != NULL);
225 
226  /* get circular pattern information */
227  SCIPprobdataGetCInfos(probdata, &cpatterns, &cvars, &ncpatterns);
228  assert(cpatterns != NULL);
229  assert(cvars != NULL);
230  assert(ncpatterns > 0);
231 
232  /* (2.) try to verify a pattern */
233  for( p = 0; p < ncpatterns; ++p )
234  {
235  SCIP_Real solval;
236  SCIP_Bool infeasible;
237  SCIP_Bool success;
238 
239  assert(cpatterns[p] != NULL);
240  assert(cvars[p] != NULL);
241 
242  solval = SCIPgetSolVal(scip, sol, cvars[p]);
243 
244  /* skip unused circular patterns */
245  if( SCIPisFeasZero(scip, solval) )
246  continue;
247 
248  /* try to verify an unknown circular pattern */
249  if( SCIPpatternGetPackableStatus(cpatterns[p]) == SCIP_PACKABLE_UNKNOWN && !conshdlrdata->tried[p] )
250  {
251  SCIP_CALL( verifyCircularPattern(scip, conshdlrdata, probdata, cpatterns[p]) );
252  conshdlrdata->tried[p] = TRUE;
253  }
254 
255  /* (2a.) fix corresponding variable to zero if pattern is not packable */
256  if( SCIPpatternGetPackableStatus(cpatterns[p]) == SCIP_PACKABLE_NO )
257  {
258  SCIP_CALL( SCIPfixVar(scip, cvars[p], 0.0, &infeasible, &success) );
259  SCIPdebugMsg(scip, "fix unpackable pattern %d\n", p);
260 
261  if( infeasible )
262  {
263  *result = SCIP_CUTOFF;
264  return SCIP_OKAY;
265  }
266  else if( success )
267  {
268  /* stop since we cutoff the LP solution */
269  *result = SCIP_REDUCEDDOM;
270  return SCIP_OKAY;
271  }
272  }
273  }
274 
275  SCIPdebugMsg(scip, "fix all tested but still unverified circular patterns\n");
276 
277  /* (3.) fix an unverified patterns that is used */
278  for( p = 0; p < ncpatterns; ++p )
279  {
281  {
282  SCIP_Bool infeasible;
283  SCIP_Bool success;
284 
285  SCIP_CALL( SCIPfixVar(scip, cvars[p], 0.0, &infeasible, &success) );
286  SCIPdebugMsg(scip, "fix unknown pattern %d in [%g,%g] (success=%u)\n", p, SCIPvarGetLbLocal(cvars[p]),
287  SCIPvarGetUbLocal(cvars[p]), success);
288 
289  /* dual bound is not valid anymore */
290  SCIPprobdataInvalidateDualbound(scip, probdata);
291 
292  if( infeasible )
293  {
294  *result = SCIP_CUTOFF;
295  return SCIP_OKAY;
296  }
297  else if( success )
298  *result = SCIP_REDUCEDDOM;
299  }
300  }
301 
302  return SCIP_OKAY;
303 }
304 
305 /** get shading of a given pattern type */
306 static
307 int getShadingVal(
308  int type, /**< pattern type */
309  int ntypes /**< total number of patterns */
310  )
311 {
312  assert(type >= 0);
313  assert(type < ntypes);
314 
315  return (int)MIN(100, MAX(ntypes, 100) / (type+1));
316 }
317 
318 /*
319  * Callback methods of event handler
320  */
321 
322 /** processes the event that a new primal solution has been found */
323 static
324 SCIP_DECL_EVENTEXEC(processNewSolutionEvent)
325 { /*lint --e{715}*/
326  SCIP_PATTERN** patterns;
327  SCIP_VAR** vars;
328  SCIP_PROBDATA* probdata;
329  SCIP_SOL* sol;
330  char* filename;
331  int npatterns;
332  int p;
333 
334  assert((SCIPeventGetType(event) & SCIP_EVENTTYPE_SOLFOUND) != 0);
335 
336  probdata = SCIPgetProbData(scip);
337  assert(probdata != NULL);
338 
339  sol = SCIPeventGetSol(event);
340  assert(sol != NULL);
341 
342  /* check whether new solution is indeed feasible */
343 #ifndef NDEBUG
344  {
345  /* check circular patterns */
346  SCIPprobdataGetCInfos(probdata, &patterns, &vars, &npatterns);
347  assert(npatterns > 0);
348 
349  for( p = 0; p < npatterns; ++p )
350  {
351  SCIP_Real val;
352 
353  assert(patterns[p] != NULL);
354  assert(vars[p] != NULL);
355 
356  val = SCIPgetSolVal(scip, sol, vars[p]);
357 
358  /* pattern is either not used or packable */
359  assert(SCIPisFeasZero(scip, val) || SCIPpatternGetPackableStatus(patterns[p]) == SCIP_PACKABLE_YES);
360  SCIPcheckPattern(scip, probdata, patterns[p]);
361  }
362 
363  /* check rectangular patterns */
364  SCIPprobdataGetRInfos(probdata, &patterns, &vars, &npatterns);
365  assert(npatterns > 0);
366 
367  for( p = 0; p < npatterns; ++p )
368  SCIPcheckPattern(scip, probdata, patterns[p]);
369  }
370 #endif
371 
372  /* write best solution information into a tex file */
373  SCIP_CALL( SCIPgetStringParam(scip, "ringpacking/texfilename", &filename) );
374 
375  if( strcmp(filename, "") != 0 )
376  {
377  FILE* file;
378  SCIP_Real* rexts;
379  SCIP_Real* rints;
380  int* demands;
381  SCIP_Real width;
382  SCIP_Real height;
383  int ntypes;
384 
385  rexts = SCIPprobdataGetRexts(probdata);
386  rints = SCIPprobdataGetRints(probdata);
387  demands = SCIPprobdataGetDemands(probdata);
388  width = SCIPprobdataGetWidth(probdata);
389  height = SCIPprobdataGetHeight(probdata);
390  ntypes = SCIPprobdataGetNTypes(probdata);
391 
392  SCIPdebugMsg(scip, "write best solution into %s\n", filename);
393 
394  file = fopen(filename, "w");
395  assert(file != NULL);
396 
397  /* latex header */
398  SCIPinfoMessage(scip, file, "\\documentclass[preview]{standalone}\n");
399  SCIPinfoMessage(scip, file, "\\usepackage{tikz}\n");
400  SCIPinfoMessage(scip, file, "\\usepackage{xstring}\n\n");
401  SCIPinfoMessage(scip, file, "\\begin{document}\n\n");
402 
403  /* circular patterns */
404  SCIPinfoMessage(scip, file, "\\section*{circular patterns}\n\n");
405  SCIPprobdataGetCInfos(probdata, &patterns, &vars, &npatterns);
406  for( p = 0; p < npatterns; ++p )
407  {
408  if( SCIPpatternGetPackableStatus(patterns[p]) == SCIP_PACKABLE_YES )
409  {
410  int type = SCIPpatternGetCircleType(patterns[p]);
411  int i;
412 
413  SCIPinfoMessage(scip, file, "\\StrSubstitute{%s}{_}{-}[\\pname]\n", SCIPvarGetName(vars[p]));
414  SCIPinfoMessage(scip, file, "\\subsection*{\\texttt{\\pname} = %g demand=%d}\n",
415  SCIPgetSolVal(scip, sol, vars[p]), demands[type]);
416  SCIPinfoMessage(scip, file, "\\resizebox{0.3\\textwidth}{!}{\n");
417  SCIPinfoMessage(scip, file, "\\begin{tikzpicture}\n");
418  SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=black!%d!white] (%g,%g) circle (%g);\n",
419  getShadingVal(type, ntypes), 0.0, 0.0, rexts[type]);
420  SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=white] (%g,%g) circle (%g);\n", 0.0, 0.0, rints[type]);
421 
422  for( i = 0; i < SCIPpatternGetNElemens(patterns[p]); ++i )
423  {
424  int elemtype = SCIPpatternGetElementType(patterns[p], i);
425  SCIP_Real x = SCIPpatternGetElementPosX(patterns[p], i);
426  SCIP_Real y = SCIPpatternGetElementPosY(patterns[p], i);
427  SCIP_Real _rext = rexts[elemtype];
428  SCIP_Real _rint = rints[elemtype];
429 
430  SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=black!%d!white] (%g,%g) circle (%g);\n",
431  getShadingVal(elemtype, ntypes), x, y, _rext);
432  SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=white] (%g,%g) circle (%g);\n", x, y, _rint);
433  }
434 
435  SCIPinfoMessage(scip, file, "\\end{tikzpicture}\n");
436  SCIPinfoMessage(scip, file, "}\n\n");
437  }
438  }
439 
440  /* rectangular patterns */
441  SCIPinfoMessage(scip, file, "\\section*{rectangular patterns}\n\n");
442  SCIPprobdataGetRInfos(probdata, &patterns, &vars, &npatterns);
443  for( p = 0; p < npatterns; ++p )
444  {
445  int i;
446 
447  assert(SCIPpatternGetPackableStatus(patterns[p]) == SCIP_PACKABLE_YES);
448 
449  SCIPinfoMessage(scip, file, "\\StrSubstitute{%s}{_}{-}[\\pname]\n", SCIPvarGetName(vars[p]));
450  SCIPinfoMessage(scip, file, "\\subsection*{\\texttt{\\pname} = %g}\n", SCIPgetSolVal(scip, sol, vars[p]));
451  SCIPinfoMessage(scip, file, "\\resizebox{0.3\\textwidth}{!}{\n");
452  SCIPinfoMessage(scip, file, "\\begin{tikzpicture}\n");
453 
454  for( i = 0; i < SCIPpatternGetNElemens(patterns[p]); ++i )
455  {
456  int elemtype = SCIPpatternGetElementType(patterns[p], i);
457  SCIP_Real x = SCIPpatternGetElementPosX(patterns[p], i);
458  SCIP_Real y = SCIPpatternGetElementPosY(patterns[p], i);
459  SCIP_Real _rext = rexts[elemtype];
460 
461  SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=black!%d!white] (%g,%g) circle (%g);\n",
462  getShadingVal(elemtype, ntypes), x, y, _rext);
463  /* SCIPinfoMessage(scip, file, "\\draw[draw=none,fill=white] (%g,%g) circle (%g);\n", x, y, _rint); */
464  }
465 
466  SCIPinfoMessage(scip, file, "\\draw[] (%g,%g) -- (%g,%g) -- (%g,%g) -- (%g,%g) -- cycle;\n",
467  0.0, 0.0, 0.0, height, width, height, width, 0.0);
468 
469  SCIPinfoMessage(scip, file, "\\end{tikzpicture}\n");
470  SCIPinfoMessage(scip, file, "}\n\n");
471  }
472 
473  SCIPinfoMessage(scip, file, "\\end{document}\n");
474 
475  fclose(file);
476  }
477 
478  return SCIP_OKAY;
479 }
480 
481 
482 /*
483  * Callback methods of constraint handler
484  */
485 
486 
487 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
488 static
489 SCIP_DECL_CONSFREE(consFreeRpa)
490 { /*lint --e{715}*/
491  SCIP_CONSHDLRDATA* conshdlrdata = SCIPconshdlrGetData(conshdlr);
492  assert(conshdlrdata != NULL);
493 
494  if( conshdlrdata->locked != NULL )
495  {
496  SCIPfreeBlockMemoryArray(scip, &conshdlrdata->locked, conshdlrdata->lockedsize);
497  conshdlrdata->lockedsize = 0;
498  }
499 
500  SCIPfreeBlockMemory(scip, &conshdlrdata);
501 
502  return SCIP_OKAY;
503 }
504 
505 
506 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
507 static
508 SCIP_DECL_CONSINITSOL(consInitsolRpa)
509 { /*lint --e{715}*/
510  SCIP_CONSHDLRDATA* conshdlrdata;
511  SCIP_PROBDATA* probdata;
512  int ncpatterns;
513 
514  conshdlrdata = SCIPconshdlrGetData(conshdlr);
515  assert(conshdlrdata != NULL);
516  assert(conshdlrdata->tried == NULL);
517 
518  probdata = SCIPgetProbData(scip);
519  assert(probdata != NULL);
520 
521  SCIPprobdataGetCInfos(probdata, NULL, NULL, &ncpatterns);
522  assert(ncpatterns > 0);
523 
524  /* allocate memory to remember which patterns have been tested to be packable */
525  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->tried, ncpatterns) );
526  BMSclearMemoryArray(conshdlrdata->tried, ncpatterns);
527 
528  /* catch events for new solutions */
529  SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, conshdlrdata->eventhdlr, NULL, NULL) );
530 
531  return SCIP_OKAY;
532 }
533 
534 
535 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
536 static
537 SCIP_DECL_CONSEXITSOL(consExitsolRpa)
538 { /*lint --e{715}*/
539  SCIP_CONSHDLRDATA* conshdlrdata;
540  SCIP_PROBDATA* probdata;
541  int ncpatterns;
542 
543  conshdlrdata = SCIPconshdlrGetData(conshdlr);
544  assert(conshdlrdata != NULL);
545  assert(conshdlrdata->tried != NULL);
546 
547  probdata = SCIPgetProbData(scip);
548  assert(probdata != NULL);
549 
550  SCIPprobdataGetCInfos(probdata, NULL, NULL, &ncpatterns);
551  assert(ncpatterns > 0);
552 
553  SCIPfreeBlockMemoryArray(scip, &conshdlrdata->tried, ncpatterns);
554 
555  /* free events for new solutions */
556  SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, conshdlrdata->eventhdlr, NULL, -1) );
557 
558  return SCIP_OKAY;
559 }
560 
561 
562 /** constraint enforcing method of constraint handler for LP solutions */
563 static
564 SCIP_DECL_CONSENFOLP(consEnfolpRpa)
565 { /*lint --e{715}*/
566  SCIP_CALL( enforceSol(scip, conshdlr, NULL, result) );
567 
568  return SCIP_OKAY;
569 }
570 
571 
572 /** constraint enforcing method of constraint handler for relaxation solutions */
573 static
574 SCIP_DECL_CONSENFORELAX(consEnforelaxRpa)
575 { /*lint --e{715}*/
576  SCIP_CALL( enforceSol(scip, conshdlr, sol, result) );
577 
578  return SCIP_OKAY;
579 }
580 
581 
582 /** constraint enforcing method of constraint handler for pseudo solutions */
583 static
584 SCIP_DECL_CONSENFOPS(consEnfopsRpa)
585 { /*lint --e{715}*/
586  SCIP_CALL( enforceSol(scip, conshdlr, NULL, result) );
587 
588  return SCIP_OKAY;
589 }
590 
591 
592 /** feasibility check method of constraint handler for integral solutions */
593 static
594 SCIP_DECL_CONSCHECK(consCheckRpa)
595 { /*lint --e{715}*/
596  *result = isSolFeasible(scip, sol) ? SCIP_FEASIBLE : SCIP_INFEASIBLE;
597 
598  return SCIP_OKAY;
599 }
600 
601 /** variable rounding lock method of constraint handler */
602 static
603 SCIP_DECL_CONSLOCK(consLockRpa)
604 { /*lint --e{715}*/
605  SCIP_CONSHDLRDATA* conshdlrdata;
606  SCIP_PROBDATA* probdata;
607  SCIP_PATTERN** cpatterns;
608  SCIP_VAR** cvars;
609  SCIP_Bool first;
610  int ncpatterns;
611  int p;
612 
613  conshdlrdata = SCIPconshdlrGetData(conshdlr);
614  assert(conshdlrdata != NULL);
615 
616  probdata = SCIPgetProbData(scip);
617  assert(probdata != NULL);
618 
619  /* get circular patterns and corresponding variables */
620  SCIPprobdataGetCInfos(probdata, &cpatterns, &cvars, &ncpatterns);
621  assert(cpatterns != NULL);
622  assert(cvars != NULL);
623  assert(ncpatterns > 0);
624 
625  /* remember whether we have locked the variables for the first time */
626  if( conshdlrdata->locked == NULL )
627  {
628  first = TRUE;
629  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->locked, ncpatterns) );
630  BMSclearMemoryArray(conshdlrdata->locked, ncpatterns);
631  conshdlrdata->lockedsize = ncpatterns;
632  }
633  else
634  first = FALSE;
635 
636  /*
637  * A pattern might change its status during a later verification step and we only need to lock patterns with a
638  * SCIP_PACKABLE_UNKNOWN status. For this reason, we keep track of patterns that have been locked. The CONSLOCK
639  * callback should only be called twice because the constraint handler does not have constraints.
640  */
641  for( p = 0; p < ncpatterns; ++p )
642  {
643  assert(cpatterns[p] != NULL);
644  assert(cvars[p] != NULL);
645 
646  if( first && SCIPpatternGetPackableStatus(cpatterns[p]) == SCIP_PACKABLE_UNKNOWN )
647  {
648  assert(!conshdlrdata->locked[p]);
649  assert(nlocksneg + nlockspos > 0);
650 
651  SCIP_CALL( SCIPaddVarLocksType(scip, cvars[p], SCIP_LOCKTYPE_MODEL, nlocksneg + nlockspos,
652  nlocksneg + nlockspos) );
653  conshdlrdata->locked[p] = TRUE;
654  SCIPdebugMsg(scip, "lock %s\n", SCIPvarGetName(cvars[p]));
655  }
656  else if( !first && conshdlrdata->locked[p] )
657  {
658  assert(nlocksneg + nlockspos < 0);
659 
660  SCIP_CALL( SCIPaddVarLocksType(scip, cvars[p], SCIP_LOCKTYPE_MODEL, nlocksneg + nlockspos,
661  nlocksneg + nlockspos) );
662  conshdlrdata->locked[p] = FALSE;
663  SCIPdebugMsg(scip, "unlock %s\n", SCIPvarGetName(cvars[p]));
664  }
665  }
666 
667  return SCIP_OKAY;
668 }
669 
670 
671 /*
672  * constraint specific interface methods
673  */
674 
675 
676 /** creates the handler for ringpacking */
678  SCIP* scip /**< SCIP data structure */
679  )
680 {
681  SCIP_CONSHDLRDATA* conshdlrdata;
682  SCIP_CONSHDLR* conshdlr = NULL;
683 
684  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
685  BMSclearMemory(conshdlrdata);
686 
687  /* include constraint handler */
690  consEnfolpRpa, consEnfopsRpa, consCheckRpa, consLockRpa,
691  conshdlrdata) );
692  assert(conshdlr != NULL);
693 
694  /* set non-fundamental callbacks via specific setter functions */
695  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolRpa) );
696  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeRpa) );;
697  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolRpa) );
698  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxRpa) );
699 
700  /* add event handler for new solutios */
701  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &conshdlrdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
702  processNewSolutionEvent, NULL) );
703 
704  /* add verification parameters */
706  "ringpacking/verification/nlptilim",
707  "time limit for verification NLP",
708  &conshdlrdata->nlptilim, FALSE, DEFAULT_VERIFICATION_NLPTILIM, -1.0, SCIP_REAL_MAX, NULL, NULL) );
709 
711  "ringpacking/verification/nlpnodelim",
712  "node limit for verification NLP",
713  &conshdlrdata->nlpnodelim, FALSE, DEFAULT_VERIFICATION_NLPNODELIM, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
714 
716  "ringpacking/verification/heurtilim",
717  "time limit for heuristic verification",
718  &conshdlrdata->heurtilim, FALSE, DEFAULT_VERIFICATION_HEURTILIM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
719 
721  "ringpacking/verification/heuriterlim",
722  "iteration limit for heuristic verification",
723  &conshdlrdata->heuriterlim, FALSE, DEFAULT_VERIFICATION_HEURITERLIM, 0, INT_MAX, NULL, NULL) );
724 
726  "ringpacking/verification/totaltilim",
727  "total time limit for all verification problems during the solving process",
728  &conshdlrdata->timeleft, FALSE, DEFAULT_VERIFICATION_TOTALTILIM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
729 
730  return SCIP_OKAY;
731 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:417
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:436
#define NULL
Definition: def.h:246
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
static SCIP_RETCODE verifyCircularPattern(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
Definition: cons_rpa.c:142
#define DEFAULT_VERIFICATION_HEURITERLIM
Definition: cons_rpa.c:68
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:379
void SCIPcheckPattern(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:385
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17400
Problem data for ringpacking problem.
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:172
#define DEFAULT_VERIFICATION_HEURTILIM
Definition: cons_rpa.c:67
static SCIP_Bool isSolFeasible(SCIP *scip, SCIP_SOL *sol)
Definition: cons_rpa.c:100
static SCIP_DECL_CONSENFOLP(consEnfolpRpa)
Definition: cons_rpa.c:565
int * SCIPprobdataGetDemands(SCIP_PROBDATA *probdata)
#define FALSE
Definition: def.h:72
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:183
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:243
static SCIP_DECL_EVENTEXEC(processNewSolutionEvent)
Definition: cons_rpa.c:325
int SCIPpatternGetCircleType(SCIP_PATTERN *pattern)
Definition: pattern.c:300
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define EVENTHDLR_NAME
Definition: cons_rpa.c:61
static int getShadingVal(int type, int ntypes)
Definition: cons_rpa.c:308
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
int SCIPpatternGetNElemens(SCIP_PATTERN *pattern)
Definition: pattern.c:206
#define SCIP_LONGINT_MAX
Definition: def.h:143
#define DEFAULT_VERIFICATION_NLPTILIM
Definition: cons_rpa.c:65
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define SCIPdebugMsg
Definition: scip_message.h:88
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:155
SCIP_VAR ** x
Definition: circlepacking.c:54
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
#define MIN3(x, y, z)
Definition: def.h:221
static SCIP_DECL_CONSINITSOL(consInitsolRpa)
Definition: cons_rpa.c:509
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4198
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:506
SCIP_PACKABLE SCIPpatternGetPackableStatus(SCIP_PATTERN *pattern)
Definition: pattern.c:326
#define SCIP_EVENTTYPE_SOLFOUND
Definition: type_event.h:127
void SCIPprobdataGetRInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***rpatterns, SCIP_VAR ***rvars, int *nrpatterns)
SCIP_RETCODE SCIPincludeConshdlrRpa(SCIP *scip)
Definition: cons_rpa.c:678
int SCIPprobdataGetNTypes(SCIP_PROBDATA *probdata)
SCIP_Real SCIPprobdataGetHeight(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPverifyCircularPatternHeuristic(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, int iterlim)
pattern data for ringpacking problem
#define CONSHDLR_ENFOPRIORITY
Definition: cons_rpa.c:40
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16730
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:434
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4211
#define SCIP_CALL(x)
Definition: def.h:358
int SCIPpatternGetElementType(SCIP_PATTERN *pattern, int i)
Definition: pattern.c:216
static SCIP_DECL_CONSLOCK(consLockRpa)
Definition: cons_rpa.c:604
#define CONSHDLR_NAME
Definition: cons_rpa.c:38
constraint handler for ringpacking
static SCIP_DECL_CONSEXITSOL(consExitsolRpa)
Definition: cons_rpa.c:538
#define SCIP_Bool
Definition: def.h:69
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
static SCIP_RETCODE enforceSol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_rpa.c:197
SCIP_Real SCIPpatternGetElementPosX(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:248
#define CONSHDLR_DESC
Definition: cons_rpa.c:39
#define MIN(x, y)
Definition: def.h:216
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:388
static SCIP_DECL_CONSENFORELAX(consEnforelaxRpa)
Definition: cons_rpa.c:575
#define CONSHDLR_EAGERFREQ
Definition: cons_rpa.c:42
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8178
SCIP_Real SCIPprobdataGetWidth(SCIP_PROBDATA *probdata)
#define BMSclearMemory(ptr)
Definition: memory.h:118
SCIP_PATTERNTYPE SCIPpatternGetPatternType(SCIP_PATTERN *pattern)
Definition: pattern.c:287
void SCIPprobdataGetCInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***cpatterns, SCIP_VAR ***cvars, int *ncpatterns)
#define SCIP_REAL_MAX
Definition: def.h:158
#define CONSHDLR_CHECKPRIORITY
Definition: cons_rpa.c:41
SCIP_Real SCIPpatternGetElementPosY(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:260
#define SCIP_EVENTTYPE_BESTSOLFOUND
Definition: type_event.h:88
#define MAX(x, y)
Definition: def.h:215
SCIP_RETCODE SCIPverifyCircularPatternNLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, SCIP_Longint nodelim)
#define DEFAULT_VERIFICATION_TOTALTILIM
Definition: cons_rpa.c:69
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:1020
static SCIP_DECL_CONSFREE(consFreeRpa)
Definition: cons_rpa.c:490
static SCIP_DECL_CONSENFOPS(consEnfopsRpa)
Definition: cons_rpa.c:585
#define SCIP_Real
Definition: def.h:157
SCIP_VAR ** y
Definition: circlepacking.c:55
#define EVENTHDLR_DESC
Definition: cons_rpa.c:62
#define SCIP_Longint
Definition: def.h:142
#define CONSHDLR_NEEDSCONS
Definition: cons_rpa.c:45
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:50
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17410
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:119
#define DEFAULT_VERIFICATION_NLPNODELIM
Definition: cons_rpa.c:66
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:530
SCIP_Real * SCIPprobdataGetRints(SCIP_PROBDATA *probdata)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
SCIP_SOL * SCIPeventGetSol(SCIP_EVENT *event)
Definition: event.c:1259
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:211
static SCIP_DECL_CONSCHECK(consCheckRpa)
Definition: cons_rpa.c:595
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1824