1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file compr.c
17 * @ingroup OTHER_CFILES
18 * @brief methods for tree compressions
19 * @author Jakob Witzig
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include <assert.h>
25 #include <string.h>
26
27 #include "scip/def.h"
28 #include "scip/set.h"
29 #include "scip/clock.h"
30 #include "scip/paramset.h"
31 #include "scip/scip.h"
32 #include "scip/compr.h"
33 #include "scip/reopt.h"
34 #include "scip/pub_message.h"
35 #include "scip/pub_misc.h"
36
37 #include "scip/struct_compr.h"
38
39
40
41 /** compares two compression methods w. r. to their delay positions and their priority */
SCIP_DECL_SORTPTRCOMP(SCIPcomprComp)42 SCIP_DECL_SORTPTRCOMP(SCIPcomprComp)
43 { /*lint --e{715}*/
44 SCIP_COMPR* compr1 = (SCIP_COMPR*)elem1;
45 SCIP_COMPR* compr2 = (SCIP_COMPR*)elem2;
46
47 assert(compr1 != NULL);
48 assert(compr2 != NULL);
49
50 return compr2->priority - compr1->priority; /* prefer higher priorities */
51 }
52
53 /** comparison method for sorting heuristics w.r.t. to their name */
SCIP_DECL_SORTPTRCOMP(SCIPcomprCompName)54 SCIP_DECL_SORTPTRCOMP(SCIPcomprCompName)
55 {
56 return strcmp(SCIPcomprGetName((SCIP_COMPR*)elem1), SCIPcomprGetName((SCIP_COMPR*)elem2));
57 }
58
59 /** method to call, when the priority of a compression was changed */
60 static
SCIP_DECL_PARAMCHGD(paramChgdComprPriority)61 SCIP_DECL_PARAMCHGD(paramChgdComprPriority)
62 { /*lint --e{715}*/
63 SCIP_PARAMDATA* paramdata;
64
65 paramdata = SCIPparamGetData(param);
66 assert(paramdata != NULL);
67
68 /* use SCIPsetComprPriority() to mark the compressions unsorted */
69 SCIP_CALL( SCIPsetComprPriority(scip, (SCIP_COMPR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
70
71 return SCIP_OKAY;
72 }
73
74 /** copies the given tree compression to a new scip */
SCIPcomprCopyInclude(SCIP_COMPR * compr,SCIP_SET * set)75 SCIP_RETCODE SCIPcomprCopyInclude(
76 SCIP_COMPR* compr, /**< tree compression */
77 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
78 )
79 {
80 assert(compr != NULL);
81 assert(set != NULL);
82 assert(set->scip != NULL);
83
84 if( compr->comprcopy != NULL )
85 {
86 SCIPsetDebugMsg(set, "including compr %s in subscip %p\n", SCIPcomprGetName(compr), (void*)set->scip);
87 SCIP_CALL( compr->comprcopy(set->scip, compr) );
88 }
89
90 return SCIP_OKAY;
91 }
92
93 /** internal method for creating a tree compression */
94 static
doComprCreate(SCIP_COMPR ** compr,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,BMS_BLKMEM * blkmem,const char * name,const char * desc,int priority,int minnnodes,SCIP_DECL_COMPRCOPY ((* comprcopy)),SCIP_DECL_COMPRFREE ((* comprfree)),SCIP_DECL_COMPRINIT ((* comprinit)),SCIP_DECL_COMPREXIT ((* comprexit)),SCIP_DECL_COMPRINITSOL ((* comprinitsol)),SCIP_DECL_COMPREXITSOL ((* comprexitsol)),SCIP_DECL_COMPREXEC ((* comprexec)),SCIP_COMPRDATA * comprdata)95 SCIP_RETCODE doComprCreate(
96 SCIP_COMPR** compr, /**< pointer to tree compression data structure */
97 SCIP_SET* set, /**< global SCIP settings */
98 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
99 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
100 const char* name, /**< name of tree compression */
101 const char* desc, /**< description of tree compression */
102 int priority, /**< priority of the tree compression */
103 int minnnodes, /**< minimal number of nodes for calling compression */
104 SCIP_DECL_COMPRCOPY ((*comprcopy)), /**< copy method of tree compression or NULL if you don't want to copy your plugin into sub-SCIPs */
105 SCIP_DECL_COMPRFREE ((*comprfree)), /**< destructor of tree compression */
106 SCIP_DECL_COMPRINIT ((*comprinit)), /**< initialize tree compression */
107 SCIP_DECL_COMPREXIT ((*comprexit)), /**< deinitialize tree compression */
108 SCIP_DECL_COMPRINITSOL ((*comprinitsol)), /**< solving process initialization method of tree compression */
109 SCIP_DECL_COMPREXITSOL ((*comprexitsol)), /**< solving process deinitialization method of tree compression */
110 SCIP_DECL_COMPREXEC ((*comprexec)), /**< execution method of tree compression */
111 SCIP_COMPRDATA* comprdata /**< tree compression data */
112 )
113 {
114 char paramname[SCIP_MAXSTRLEN];
115 char paramdesc[SCIP_MAXSTRLEN];
116
117 assert(compr != NULL);
118 assert(name != NULL);
119 assert(desc != NULL);
120 assert(comprexec != NULL);
121
122 SCIP_ALLOC( BMSallocMemory(compr) );
123 BMSclearMemory(*compr);
124
125 SCIP_ALLOC( BMSduplicateMemoryArray(&(*compr)->name, name, strlen(name)+1) );
126 SCIP_ALLOC( BMSduplicateMemoryArray(&(*compr)->desc, desc, strlen(desc)+1) );
127 (*compr)->priority = priority;
128 (*compr)->minnnodes = minnnodes;
129 (*compr)->comprcopy = comprcopy;
130 (*compr)->comprfree = comprfree;
131 (*compr)->comprinit = comprinit;
132 (*compr)->comprexit = comprexit;
133 (*compr)->comprinitsol = comprinitsol;
134 (*compr)->comprexitsol = comprexitsol;
135 (*compr)->comprexec = comprexec;
136 (*compr)->comprdata = comprdata;
137 SCIP_CALL( SCIPclockCreate(&(*compr)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
138 SCIP_CALL( SCIPclockCreate(&(*compr)->comprclock, SCIP_CLOCKTYPE_DEFAULT) );
139 (*compr)->ncalls = 0;
140 (*compr)->nfound = 0;
141 (*compr)->rate = 0.0;
142 (*compr)->initialized = FALSE;
143 (*compr)->nnodes = 0;
144 (*compr)->loi = 0.0;
145
146 /* add parameters */
147 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "compression/%s/priority", name);
148 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of compression <%s>", name);
149 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
150 &(*compr)->priority, TRUE, priority, INT_MIN/4, INT_MAX/4,
151 paramChgdComprPriority, (SCIP_PARAMDATA*)(*compr)) ); /*lint !e740*/
152 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "compression/%s/minnleaves", name);
153 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "minimal number of leave nodes for calling tree compression <%s>", name);
154 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
155 &(*compr)->minnnodes, FALSE, minnnodes, 1, INT_MAX, NULL, NULL) );
156
157 return SCIP_OKAY;
158 }
159
160 /** creates a tree compression */
SCIPcomprCreate(SCIP_COMPR ** compr,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,BMS_BLKMEM * blkmem,const char * name,const char * desc,int priority,int minnnodes,SCIP_DECL_COMPRCOPY ((* comprcopy)),SCIP_DECL_COMPRFREE ((* comprfree)),SCIP_DECL_COMPRINIT ((* comprinit)),SCIP_DECL_COMPREXIT ((* comprexit)),SCIP_DECL_COMPRINITSOL ((* comprinitsol)),SCIP_DECL_COMPREXITSOL ((* comprexitsol)),SCIP_DECL_COMPREXEC ((* comprexec)),SCIP_COMPRDATA * comprdata)161 SCIP_RETCODE SCIPcomprCreate(
162 SCIP_COMPR** compr, /**< pointer to tree compression data structure */
163 SCIP_SET* set, /**< global SCIP settings */
164 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
165 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
166 const char* name, /**< name of tree compression */
167 const char* desc, /**< description of tree compression */
168 int priority, /**< priority of the tree compression */
169 int minnnodes, /**< minimal number of nodes for calling compression */
170 SCIP_DECL_COMPRCOPY ((*comprcopy)), /**< copy method of tree compression or NULL if you don't want to copy
171 * your plugin into sub-SCIPs */
172 SCIP_DECL_COMPRFREE ((*comprfree)), /**< destructor of tree compression */
173 SCIP_DECL_COMPRINIT ((*comprinit)), /**< initialize tree compression */
174 SCIP_DECL_COMPREXIT ((*comprexit)), /**< deinitialize tree compression */
175 SCIP_DECL_COMPRINITSOL ((*comprinitsol)), /**< solving process initialization method of tree compression */
176 SCIP_DECL_COMPREXITSOL ((*comprexitsol)), /**< solving process deinitialization method of tree compression */
177 SCIP_DECL_COMPREXEC ((*comprexec)), /**< execution method of tree compression */
178 SCIP_COMPRDATA* comprdata /**< tree compression data */
179 )
180 {
181 assert(compr != NULL);
182 assert(name != NULL);
183 assert(desc != NULL);
184 assert(comprexec != NULL);
185
186 SCIP_CALL_FINALLY( doComprCreate(compr, set, messagehdlr, blkmem, name, desc, priority, minnnodes,
187 comprcopy, comprfree, comprinit, comprexit, comprinitsol, comprexitsol, comprexec, comprdata),
188 (void) SCIPcomprFree(compr, set) );
189
190 return SCIP_OKAY;
191 }
192
193 /** calls destructor and frees memory of tree compression */
SCIPcomprFree(SCIP_COMPR ** compr,SCIP_SET * set)194 SCIP_RETCODE SCIPcomprFree(
195 SCIP_COMPR** compr, /**< pointer to tree compression data structure */
196 SCIP_SET* set /**< global SCIP settings */
197 )
198 {
199 assert(compr != NULL);
200 if( *compr == NULL )
201 return SCIP_OKAY;
202 assert(!(*compr)->initialized);
203 assert(set != NULL);
204
205 /* call destructor of tree compression */
206 if( (*compr)->comprfree != NULL )
207 {
208 SCIP_CALL( (*compr)->comprfree(set->scip, *compr) );
209 }
210
211 SCIPclockFree(&(*compr)->comprclock);
212 SCIPclockFree(&(*compr)->setuptime);
213 BMSfreeMemoryArrayNull(&(*compr)->name);
214 BMSfreeMemoryArrayNull(&(*compr)->desc);
215 BMSfreeMemory(compr);
216
217 return SCIP_OKAY;
218 }
219
220 /** initializes tree compression */
SCIPcomprInit(SCIP_COMPR * compr,SCIP_SET * set)221 SCIP_RETCODE SCIPcomprInit(
222 SCIP_COMPR* compr, /**< tree compression */
223 SCIP_SET* set /**< global SCIP settings */
224 )
225 {
226 assert(compr != NULL);
227 assert(set != NULL);
228
229 if( compr->initialized )
230 {
231 SCIPerrorMessage("tree compression <%s> already initialized\n", compr->name);
232 return SCIP_INVALIDCALL;
233 }
234
235 if( set->misc_resetstat && !set->reopt_enable )
236 {
237 SCIPclockReset(compr->setuptime);
238 SCIPclockReset(compr->comprclock);
239
240 compr->ncalls = 0;
241 compr->nfound = 0;
242 }
243
244 if( compr->comprinit != NULL )
245 {
246 /* start timing */
247 SCIPclockStart(compr->setuptime, set);
248
249 SCIP_CALL( compr->comprinit(set->scip, compr) );
250
251 /* stop timing */
252 SCIPclockStop(compr->setuptime, set);
253 }
254 compr->initialized = TRUE;
255
256 return SCIP_OKAY;
257 }
258
259 /** calls exit method of tree compression */
SCIPcomprExit(SCIP_COMPR * compr,SCIP_SET * set)260 SCIP_RETCODE SCIPcomprExit(
261 SCIP_COMPR* compr, /**< tree compression */
262 SCIP_SET* set /**< global SCIP settings */
263 )
264 {
265 assert(compr != NULL);
266 assert(set != NULL);
267
268 if( !compr->initialized )
269 {
270 SCIPerrorMessage("tree compression <%s> not initialized\n", compr->name);
271 return SCIP_INVALIDCALL;
272 }
273
274 if( compr->comprexit != NULL )
275 {
276 /* start timing */
277 SCIPclockStart(compr->setuptime, set);
278
279 SCIP_CALL( compr->comprexit(set->scip, compr) );
280
281 /* stop timing */
282 SCIPclockStop(compr->setuptime, set);
283 }
284 compr->initialized = FALSE;
285
286 return SCIP_OKAY;
287 }
288
289 /** calls execution method of tree compression */
SCIPcomprExec(SCIP_COMPR * compr,SCIP_SET * set,SCIP_REOPT * reopt,SCIP_RESULT * result)290 SCIP_RETCODE SCIPcomprExec(
291 SCIP_COMPR* compr, /**< tree compression */
292 SCIP_SET* set, /**< global SCIP settings */
293 SCIP_REOPT* reopt, /**< reoptimization data structure */
294 SCIP_RESULT* result /**< pointer to store the result of the callback method */
295 )
296 {
297 assert(compr != NULL);
298 assert(compr->comprexec != NULL);
299 assert(set != NULL);
300 assert(set->scip != NULL);
301 assert(result != NULL);
302
303 *result = SCIP_DIDNOTRUN;
304
305 /* do not run if reoptimization data structure is not initialized */
306 if( reopt == NULL )
307 return SCIP_OKAY;
308
309 /* do not run if the reoptimization tree is not large enough */
310 if( SCIPreoptGetNLeaves(reopt, NULL) < compr->minnnodes )
311 return SCIP_OKAY;
312
313 SCIPsetDebugMsg(set, "executing tree compression <%s>\n", compr->name);
314
315 /* start timing */
316 SCIPclockStart(compr->comprclock, set);
317
318 /* call external method */
319 SCIP_CALL( compr->comprexec(set->scip, compr, result) );
320
321 /* stop timing */
322 SCIPclockStop(compr->comprclock, set);
323
324 /* evaluate result */
325 if( *result != SCIP_SUCCESS
326 && *result != SCIP_DIDNOTFIND
327 && *result != SCIP_DIDNOTRUN )
328 {
329 SCIPerrorMessage("execution method of tree compression <%s> returned invalid result <%d>\n",
330 compr->name, *result);
331 return SCIP_INVALIDRESULT;
332 }
333
334 if( *result != SCIP_DIDNOTRUN )
335 compr->ncalls++;
336
337 if( *result == SCIP_SUCCESS )
338 compr->nfound++;
339
340 return SCIP_OKAY;
341 }
342
343 /** gets user data of tree compression */
SCIPcomprGetData(SCIP_COMPR * compr)344 SCIP_COMPRDATA* SCIPcomprGetData(
345 SCIP_COMPR* compr /**< tree compression */
346 )
347 {
348 assert(compr != NULL);
349
350 return compr->comprdata;
351 }
352
353 /** sets user data of tree compression; user has to free old data in advance! */
SCIPcomprSetData(SCIP_COMPR * compr,SCIP_COMPRDATA * comprdata)354 void SCIPcomprSetData(
355 SCIP_COMPR* compr, /**< tree compression */
356 SCIP_COMPRDATA* comprdata /**< new tree compression user data */
357 )
358 {
359 assert(compr != NULL);
360
361 compr->comprdata = comprdata;
362 }
363
364 /* new callback setter methods */
365
366 /** sets copy callback of tree compression */
SCIPcomprSetCopy(SCIP_COMPR * compr,SCIP_DECL_COMPRCOPY ((* comprcopy)))367 void SCIPcomprSetCopy(
368 SCIP_COMPR* compr, /**< tree compression */
369 SCIP_DECL_COMPRCOPY ((*comprcopy)) /**< copy callback of tree compression or NULL if you don't want to copy your plugin into sub-SCIPs */
370 )
371 {
372 assert(compr != NULL);
373
374 compr->comprcopy = comprcopy;
375 }
376
377 /** sets destructor callback of tree compression */
SCIPcomprSetFree(SCIP_COMPR * compr,SCIP_DECL_COMPRFREE ((* comprfree)))378 void SCIPcomprSetFree(
379 SCIP_COMPR* compr, /**< tree compression */
380 SCIP_DECL_COMPRFREE ((*comprfree)) /**< destructor of tree compression */
381 )
382 {
383 assert(compr != NULL);
384
385 compr->comprfree = comprfree;
386 }
387
388 /** sets initialization callback of tree compression */
SCIPcomprSetInit(SCIP_COMPR * compr,SCIP_DECL_COMPRINIT ((* comprinit)))389 void SCIPcomprSetInit(
390 SCIP_COMPR* compr, /**< tree compression */
391 SCIP_DECL_COMPRINIT ((*comprinit)) /**< initialize tree compression */
392 )
393 {
394 assert(compr != NULL);
395
396 compr->comprinit = comprinit;
397 }
398
399 /** sets deinitialization callback of tree compression */
SCIPcomprSetExit(SCIP_COMPR * compr,SCIP_DECL_COMPREXIT ((* comprexit)))400 void SCIPcomprSetExit(
401 SCIP_COMPR* compr, /**< tree compression */
402 SCIP_DECL_COMPREXIT ((*comprexit)) /**< deinitialize tree compression */
403 )
404 {
405 assert(compr != NULL);
406
407 compr->comprexit = comprexit;
408 }
409
410 /** sets solving process initialization callback of tree compression */
SCIPcomprSetInitsol(SCIP_COMPR * compr,SCIP_DECL_COMPRINITSOL ((* comprinitsol)))411 void SCIPcomprSetInitsol(
412 SCIP_COMPR* compr, /**< tree compression */
413 SCIP_DECL_COMPRINITSOL ((*comprinitsol)) /**< solving process initialization callback of tree compression */
414 )
415 {
416 assert(compr != NULL);
417
418 compr->comprinitsol = comprinitsol;
419 }
420
421 /** sets solving process deinitialization callback of tree compression */
SCIPcomprSetExitsol(SCIP_COMPR * compr,SCIP_DECL_COMPREXITSOL ((* comprexitsol)))422 void SCIPcomprSetExitsol(
423 SCIP_COMPR* compr, /**< tree compression */
424 SCIP_DECL_COMPREXITSOL ((*comprexitsol)) /**< solving process deinitialization callback of tree compression */
425 )
426 {
427 assert(compr != NULL);
428
429 compr->comprexitsol = comprexitsol;
430 }
431
432 /** should the compression be executed at the given depth, number of nodes */
SCIPcomprShouldBeExecuted(SCIP_COMPR * compr,int depth,int nnodes)433 SCIP_Bool SCIPcomprShouldBeExecuted(
434 SCIP_COMPR* compr, /**< tree compression */
435 int depth, /**< depth of current node */
436 int nnodes /**< number of open nodes */
437 )
438 {
439 assert(compr != NULL);
440 assert(depth >= 0);
441 assert(nnodes >= 0);
442
443 return nnodes >= compr->minnnodes;
444 }
445
446 /** gets name of tree compression */
SCIPcomprGetName(SCIP_COMPR * compr)447 const char* SCIPcomprGetName(
448 SCIP_COMPR* compr /**< tree compression */
449 )
450 {
451 assert(compr != NULL);
452
453 return compr->name;
454 }
455
456 /** gets description of tree compression */
SCIPcomprGetDesc(SCIP_COMPR * compr)457 const char* SCIPcomprGetDesc(
458 SCIP_COMPR* compr /**< tree compression */
459 )
460 {
461 assert(compr != NULL);
462
463 return compr->desc;
464 }
465
466 /** gets priority of tree compression */
SCIPcomprGetPriority(SCIP_COMPR * compr)467 int SCIPcomprGetPriority(
468 SCIP_COMPR* compr /**< tree compression */
469 )
470 {
471 assert(compr != NULL);
472
473 return compr->priority;
474 }
475
476 /** sets priority of tree compression */
SCIPcomprSetPriority(SCIP_COMPR * compr,SCIP_SET * set,int priority)477 void SCIPcomprSetPriority(
478 SCIP_COMPR* compr, /**< tree compression */
479 SCIP_SET* set, /**< global SCIP settings */
480 int priority /**< new priority of the tree compression */
481 )
482 {
483 assert(compr != NULL);
484 assert(set != NULL);
485
486 compr->priority = priority;
487 set->comprssorted = FALSE;
488 }
489
490 /** gets minimal number of nodes for calling tree compression (returns -1, if no node threshold exists) */
SCIPcomprGetMinNodes(SCIP_COMPR * compr)491 int SCIPcomprGetMinNodes(
492 SCIP_COMPR* compr /**< tree compression */
493 )
494 {
495 assert(compr != NULL);
496
497 return compr->minnnodes;
498 }
499
500 /** gets the number of times, the heuristic was called and tried to find a solution */
SCIPcomprGetNCalls(SCIP_COMPR * compr)501 SCIP_Longint SCIPcomprGetNCalls(
502 SCIP_COMPR* compr /**< tree compression */
503 )
504 {
505 assert(compr != NULL);
506
507 return compr->ncalls;
508 }
509
510 /** gets the number of compressions found by this compression */
SCIPcomprGetNFound(SCIP_COMPR * compr)511 SCIP_Longint SCIPcomprGetNFound(
512 SCIP_COMPR* compr /**< tree compression */
513 )
514 {
515 assert(compr != NULL);
516
517 return compr->nfound;
518 }
519
520 /** is tree compression initialized? */
SCIPcomprIsInitialized(SCIP_COMPR * compr)521 SCIP_Bool SCIPcomprIsInitialized(
522 SCIP_COMPR* compr /**< tree compression */
523 )
524 {
525 assert(compr != NULL);
526
527 return compr->initialized;
528 }
529
530 /** gets time in seconds used in this heuristic for setting up for next stages */
SCIPcomprGetSetupTime(SCIP_COMPR * compr)531 SCIP_Real SCIPcomprGetSetupTime(
532 SCIP_COMPR* compr /**< tree compression */
533 )
534 {
535 assert(compr != NULL);
536
537 return SCIPclockGetTime(compr->setuptime);
538 }
539
540 /** gets time in seconds used in this heuristic */
SCIPcomprGetTime(SCIP_COMPR * compr)541 SCIP_Real SCIPcomprGetTime(
542 SCIP_COMPR* compr /**< tree compression */
543 )
544 {
545 assert(compr != NULL);
546
547 return SCIPclockGetTime(compr->comprclock);
548 }
549