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