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