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 */
84struct 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 */
107static
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 */
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 */
149static
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 */
204static
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");
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 */
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 */
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 */
315static
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 */
332static
333SCIP_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 {
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) */
497static
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) */
516static
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) */
545static
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 */
572static
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 */
582static
583SCIP_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 */
592static
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 */
602static
604{ /*lint --e{715}*/
606
607 return SCIP_OKAY;
608}
609
610/** variable rounding lock method of constraint handler */
611static
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 */
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}
SCIP_VAR ** y
Definition: circlepacking.c:64
SCIP_VAR ** x
Definition: circlepacking.c:63
static SCIP_DECL_CONSFREE(consFreeRpa)
Definition: cons_rpa.c:498
static SCIP_DECL_CONSLOCK(consLockRpa)
Definition: cons_rpa.c:612
static SCIP_Bool isSolFeasible(SCIP *scip, SCIP_SOL *sol)
Definition: cons_rpa.c:108
#define CONSHDLR_NEEDSCONS
Definition: cons_rpa.c:53
#define CONSHDLR_CHECKPRIORITY
Definition: cons_rpa.c:50
#define DEFAULT_VERIFICATION_HEURTILIM
Definition: cons_rpa.c:75
#define CONSHDLR_DESC
Definition: cons_rpa.c:48
static SCIP_DECL_CONSENFOPS(consEnfopsRpa)
Definition: cons_rpa.c:593
static SCIP_DECL_CONSEXITSOL(consExitsolRpa)
Definition: cons_rpa.c:546
static int getShadingVal(int type, int ntypes)
Definition: cons_rpa.c:316
static SCIP_DECL_CONSCHECK(consCheckRpa)
Definition: cons_rpa.c:603
#define DEFAULT_VERIFICATION_TOTALTILIM
Definition: cons_rpa.c:77
static SCIP_DECL_EVENTEXEC(processNewSolutionEvent)
Definition: cons_rpa.c:333
static SCIP_DECL_CONSENFOLP(consEnfolpRpa)
Definition: cons_rpa.c:573
static SCIP_RETCODE verifyCircularPattern(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
Definition: cons_rpa.c:150
static SCIP_RETCODE enforceSol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_rpa.c:205
#define DEFAULT_VERIFICATION_NLPNODELIM
Definition: cons_rpa.c:74
static SCIP_DECL_CONSINITSOL(consInitsolRpa)
Definition: cons_rpa.c:517
#define DEFAULT_VERIFICATION_NLPTILIM
Definition: cons_rpa.c:73
static SCIP_DECL_CONSENFORELAX(consEnforelaxRpa)
Definition: cons_rpa.c:583
#define DEFAULT_VERIFICATION_HEURITERLIM
Definition: cons_rpa.c:76
#define CONSHDLR_EAGERFREQ
Definition: cons_rpa.c:51
#define EVENTHDLR_DESC
Definition: cons_rpa.c:70
#define CONSHDLR_ENFOPRIORITY
Definition: cons_rpa.c:49
#define CONSHDLR_NAME
Definition: cons_rpa.c:47
#define EVENTHDLR_NAME
Definition: cons_rpa.c:69
constraint handler for ringpacking
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define MIN3(x, y, z)
Definition: def.h:251
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPincludeConshdlrRpa(SCIP *scip)
Definition: cons_rpa.c:686
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:964
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
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 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_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_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:345
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
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
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
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_SOL * SCIPeventGetSol(SCIP_EVENT *event)
Definition: event.c:1337
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:286
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:320
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
#define BMSclearMemory(ptr)
Definition: memory.h:129
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
SCIP_Real SCIPpatternGetElementPosY(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:269
SCIP_Real SCIPpatternGetElementPosX(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:257
SCIP_PATTERNTYPE SCIPpatternGetPatternType(SCIP_PATTERN *pattern)
Definition: pattern.c:296
SCIP_PACKABLE SCIPpatternGetPackableStatus(SCIP_PATTERN *pattern)
Definition: pattern.c:335
int SCIPpatternGetElementType(SCIP_PATTERN *pattern, int i)
Definition: pattern.c:225
int SCIPpatternGetNElemens(SCIP_PATTERN *pattern)
Definition: pattern.c:215
int SCIPpatternGetCircleType(SCIP_PATTERN *pattern)
Definition: pattern.c:309
pattern data for ringpacking problem
@ SCIP_PATTERNTYPE_CIRCULAR
Definition: pattern.h:51
@ SCIP_PACKABLE_NO
Definition: pattern.h:43
@ SCIP_PACKABLE_YES
Definition: pattern.h:44
@ SCIP_PACKABLE_UNKNOWN
Definition: pattern.h:45
SCIP_Real SCIPprobdataGetHeight(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPverifyCircularPatternNLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, SCIP_Longint nodelim)
int * SCIPprobdataGetDemands(SCIP_PROBDATA *probdata)
void SCIPprobdataGetRInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***rpatterns, SCIP_VAR ***rvars, int *nrpatterns)
int SCIPprobdataGetNTypes(SCIP_PROBDATA *probdata)
void SCIPprobdataGetCInfos(SCIP_PROBDATA *probdata, SCIP_PATTERN ***cpatterns, SCIP_VAR ***cvars, int *ncpatterns)
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPverifyCircularPatternHeuristic(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_Real timelim, int iterlim)
SCIP_Real * SCIPprobdataGetRints(SCIP_PROBDATA *probdata)
void SCIPprobdataInvalidateDualbound(SCIP *scip, SCIP_PROBDATA *probdata)
void SCIPcheckPattern(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern)
SCIP_Real SCIPprobdataGetWidth(SCIP_PROBDATA *probdata)
Problem data for ringpacking problem.
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
#define SCIP_EVENTTYPE_BESTSOLFOUND
Definition: type_event.h:105
#define SCIP_EVENTTYPE_SOLFOUND
Definition: type_event.h:144
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:53
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_FEASIBLE
Definition: type_result.h:45
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_INFEASIBLE
Definition: type_result.h:46
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97