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_largestrepr.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  largestrepr tree compression
28   	 * @author Jakob Witzig
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "blockmemshell/memory.h"
34   	#include "scip/compr_largestrepr.h"
35   	#include "scip/pub_compr.h"
36   	#include "scip/pub_message.h"
37   	#include "scip/pub_misc.h"
38   	#include "scip/pub_reopt.h"
39   	#include "scip/pub_var.h"
40   	#include "scip/scip_compr.h"
41   	#include "scip/scip_general.h"
42   	#include "scip/scip_mem.h"
43   	#include "scip/scip_message.h"
44   	#include "scip/scip_numerics.h"
45   	#include "scip/scip_param.h"
46   	#include "scip/scip_prob.h"
47   	#include "scip/scip_reopt.h"
48   	#include <string.h>
49   	
50   	#define COMPR_NAME             "largestrepr"
51   	#define COMPR_DESC             "heuristic searching for large common representatives"
52   	#define COMPR_PRIORITY         2000
53   	#define COMPR_MINNNODES        20
54   	
55   	#define DEFAUL_MEM_REPR        10
56   	#define DEFAULT_ITERS           5
57   	#define DEFAULT_MINCOMMONVARS   3
58   	
59   	/*
60   	 * Data structures
61   	 */
62   	
63   	/** tree compression data */
64   	struct SCIP_ComprData
65   	{
66   	   /* representative data */
67   	   SCIP_REOPTNODE**      representatives;    /**< list of representatives */
68   	   int                   nrepresentatives;   /**< number of representatives */
69   	   int                   representativessize;/**< allocated memory for representatives */
70   	   SCIP_Bool             initialized;        /**< was compressor data initialized? */
71   	
72   	   /* statictics */
73   	   SCIP_Real             rate;               /**< rate of compression */
74   	   SCIP_Real             score;              /**< score of the best representation found */
75   	   int                   nnodes;             /**< number of nodes after compressing */
76   	
77   	   /* parameters */
78   	   int                   mincomvars;         /**< minimal number of common variables */
79   	   int                   niters;             /**< number of runs in the constrained part */
80   	};
81   	
82   	
83   	/*
84   	 * Local methods
85   	 */
86   	
87   	/** calculate a bit signature of variables fixed to 0 and 1 on the basis of SCIPvarGetProbindex()
88   	 */
89   	static
90   	void calcSignature(
91   	   SCIP_VAR**            vars,               /**< variable array */
92   	   SCIP_Real*            vals,               /**< value array */
93   	   int                   nvars,              /**< number of variables */
94   	   uint64_t*             signature0,         /**< pointer to store the signatures of variables fixed to 0 */
95   	   uint64_t*             signature1          /**< pointer to store the signatures of variables fixed to 1 */
96   	   )
97   	{
98   	   uint64_t varsignature;
99   	   int v;
100  	
101  	   (*signature0) = 0;
102  	   (*signature1) = 0;
103  	
104  	   for( v = nvars - 1; v >= 0; --v )
105  	   {
106  	      varsignature = SCIPhashSignature64(SCIPvarGetProbindex(vars[v]));
107  	      if( vals[v] < 0.5 )
108  	         (*signature0) |= varsignature;
109  	      else
110  	         (*signature1) |= varsignature;
111  	   }
112  	
113  	   return;
114  	}
115  	
116  	/** try to find a representation of the current search frontier.
117  	 *
118  	 *  We use the signatures of variables fixed to 0 and 1 to decide if there is
119  	 *  definitely no intersection or if the intersection is potentially non-empty.
120  	 *
121  	 *  To find a good representation we start the procedure with a node and choose the best one.
122  	 *  the heuristic tries to find a representation of size 2 in each iteration, i.e., runs in the
123  	 *  constrained part.
124  	 */
125  	static
126  	SCIP_RETCODE constructCompression(
127  	   SCIP*                 scip,               /**< SCIP data structure */
128  	   SCIP_COMPR*           compr,              /**< compression method */
129  	   SCIP_COMPRDATA*       comprdata,          /**< compression data */
130  	   SCIP_RESULT*          result              /**< result pointer */
131  	   )
132  	{
133  	   SCIP_NODE* currentnode;
134  	   SCIP_VAR*** repvars;
135  	   SCIP_Real** repvals;
136  	   int* nrepvars;
137  	   SCIP_VAR*** vars;
138  	   SCIP_Real** vals;
139  	   SCIP_BOUNDTYPE** bounds;
140  	   SCIP_Real* lowerbounds;
141  	   SCIP_Bool* covered;
142  	   const char** varnames;
143  	   SCIP_Real score;
144  	   int nreps;
145  	   uint64_t* signature0;
146  	   uint64_t* signature1;
147  	   int* common_vars;
148  	   unsigned int* leaveids;
149  	   int* nvars;
150  	   int nids;
151  	   int nleaveids;
152  	   int k;
153  	   int current_id;
154  	   int start_id;
155  	
156  	   assert(scip != NULL);
157  	   assert(comprdata != NULL);
158  	
159  	   *result = SCIP_DIDNOTRUN;
160  	
161  	   assert(SCIPgetStage(scip) <= SCIP_STAGE_PRESOLVED);
162  	
163  	   currentnode = NULL;
164  	   nleaveids = SCIPgetNReoptLeaves(scip, currentnode);
165  	
166  	   SCIPdebugMsg(scip, ">> start <%s> (nleaves: %d)\n", COMPR_NAME, nleaveids);
167  	
168  	   if( SCIPcomprGetMinNodes(compr) > nleaveids )
169  	   {
170  	      SCIPdebugMsg(scip, "-> skip compression (min. leaves = %d)\n", SCIPcomprGetMinNodes(compr));
171  	      return SCIP_OKAY;
172  	   }
173  	
174  	   *result = SCIP_DIDNOTFIND;
175  	
176  	   SCIPdebugMsg(scip, "-> try compression with %d node(s)\n", nleaveids);
177  	
178  	   /* collect the nodes to compress */
179  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &leaveids, nleaveids) );
180  	
181  	   SCIP_CALL( SCIPgetReoptLeaveIDs(scip, currentnode, leaveids, nleaveids, &nids) );
182  	   assert(nids == nleaveids);
183  	
184  	   /* allocate memory to store the old tree */
185  	   SCIP_CALL( SCIPallocBufferArray(scip, &vars, nleaveids) );
186  	   SCIP_CALL( SCIPallocBufferArray(scip, &vals, nleaveids) );
187  	   SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nleaveids) );
188  	   SCIP_CALL( SCIPallocBufferArray(scip, &nvars, nleaveids) );
189  	   SCIP_CALL( SCIPallocBufferArray(scip, &lowerbounds, nleaveids) );
190  	   SCIP_CALL( SCIPallocBufferArray(scip, &varnames, SCIPgetNOrigVars(scip)) );
191  	
192  	   /* allocate memory to store the signatures */
193  	   SCIP_CALL( SCIPallocBufferArray(scip, &signature0, nleaveids) );
194  	   SCIP_CALL( SCIPallocBufferArray(scip, &signature1, nleaveids) );
195  	
196  	   /* get data of nodes */
197  	   for( k = 0; k < nleaveids; k++ )
198  	   {
199  	      SCIP_REOPTNODE* reoptnode;
200  	      int mem_vars;
201  	      int nvars2;
202  	      int nafterdualvars;
203  	
204  	      mem_vars = SCIPgetNBinVars(scip);
205  	
206  	      /* allocate memory */
207  	      SCIP_CALL( SCIPallocBufferArray(scip, &vars[k], mem_vars) ); /*lint !e866*/
208  	      SCIP_CALL( SCIPallocBufferArray(scip, &vals[k], mem_vars) ); /*lint !e866*/
209  	      SCIP_CALL( SCIPallocBufferArray(scip, &bounds[k], mem_vars) ); /*lint !e866*/
210  	
211  	      /* get the branching path */
212  	      reoptnode = SCIPgetReoptnode(scip, leaveids[k]);
213  	      SCIPgetReoptnodePath(scip, reoptnode, vars[k], vals[k], bounds[k], mem_vars, &nvars2, &nafterdualvars);
214  	      lowerbounds[k] = SCIPreoptnodeGetLowerbound(reoptnode);
215  	      nvars[k] = nvars2 + nafterdualvars;
216  	
217  	      /* calculate the signature*/
218  	      calcSignature(vars[k], vals[k], nvars[k], &signature0[k], &signature1[k]);
219  	   }
220  	
221  	   for( start_id = 0; start_id < nleaveids; start_id++ )
222  	   {
223  	      nreps = -1;
224  	      score = 0.0;
225  	
226  	      /* we want to find an intersection that merges at least 3 nodes */
227  	      if( nvars[start_id] <= comprdata->mincomvars + 1 )
228  	         continue;
229  	
230  	      /* initialize the covered-array with FALSE */
231  	      SCIP_CALL( SCIPallocClearBufferArray(scip, &covered, nleaveids) );
232  	
233  	      current_id = start_id;
234  	
235  	      /* initialize storage for representatives */
236  	      SCIP_CALL( SCIPallocBufferArray(scip, &repvars, 2+comprdata->niters) );
237  	      SCIP_CALL( SCIPallocBufferArray(scip, &repvals, 2+comprdata->niters) );
238  	      SCIP_CALL( SCIPallocBufferArray(scip, &nrepvars, 2+comprdata->niters) );
239  	
240  	      SCIPdebugMsg(scip, "+---+ start round %d +---+\n", start_id + 1);
241  	
242  	      /* try to find common representatives */
243  	      while( nreps-1 <= comprdata->niters && (nreps == -1 || (current_id % nleaveids) != start_id) )
244  	      {
245  	         int* idx_common_vars;
246  	         int* idx_non_zero;
247  	         int* covered_ids;
248  	         int ncovered;
249  	         int ncommon_vars;
250  	         int nnon_zero_vars;
251  	         int next_id;
252  	         int nnemptyinters;
253  	         int v;
254  	
255  	         /* find the first id which is not covered */
256  	         while( covered[current_id % nleaveids] && (nreps == -1 || (current_id % nleaveids) != start_id) )
257  	            current_id++;
258  	
259  	         current_id %= nleaveids;
260  	
261  	         if( nreps > 0 && current_id == start_id )
262  	            goto TERMINATE;
263  	
264  	         /* if the this is the fist round with a new start_id we set the number of representatives to 0 */
265  	         nreps = MAX(0, nreps);
266  	
267  	         nnemptyinters = 0;
268  	
269  	         /* mark the node as covered */
270  	         covered[current_id] = TRUE;
271  	
272  	         /* find the next not covered id */
273  	         next_id = (current_id + 1) % nleaveids ;
274  	         while( covered[next_id] && next_id != current_id )
275  	            next_id = (next_id + 1) % nleaveids;
276  	
277  	         if( next_id == current_id )
278  	            goto TERMINATE;
279  	
280  	         /* we want to find an intersection that merges at least 3 nodes */
281  	         if( nvars[next_id] <= comprdata->mincomvars + 1 )
282  	            continue;
283  	
284  	         /* get a clear array of size SCIPgetNOrigVars */
285  	         SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &common_vars, SCIPgetNOrigVars(scip)) );
286  	
287  	         /* allocate buffer */
288  	         nnon_zero_vars = 0;
289  	         SCIP_CALL( SCIPallocBufferArray(scip, &idx_common_vars, nvars[current_id]) );
290  	         SCIP_CALL( SCIPallocBufferArray(scip, &idx_non_zero, nvars[current_id]) );
291  	         SCIP_CALL( SCIPallocBufferArray(scip, &covered_ids, nleaveids) );
292  	         ncovered = 0;
293  	
294  	         /* initialize common vars:
295  	          *   vars[i] = 0 -> variable with idx i is not fixed
296  	          *   vars[i] = 1 -> variable with idx i is fixed to zero
297  	          *   vars[i] = 2 -> variable with idx i is fixed to one */
298  	         for( v = 0; v < nvars[current_id]; v++ )
299  	         {
300  	            if( SCIPisFeasEQ(scip, vals[current_id][v], 0.0) )
301  	               common_vars[SCIPvarGetProbindex(vars[current_id][v])] = 1;
302  	            else
303  	            {
304  	               assert(SCIPisFeasEQ(scip, vals[current_id][v], 1.0));
305  	               common_vars[SCIPvarGetProbindex(vars[current_id][v])] = 2;
306  	            }
307  	
308  	            varnames[SCIPvarGetProbindex(vars[current_id][v])] = SCIPvarGetName(vars[current_id][v]);
309  	
310  	            idx_non_zero[nnon_zero_vars] = SCIPvarGetProbindex(vars[current_id][v]);
311  	            nnon_zero_vars++;
312  	         }
313  	
314  	         SCIPdebugMsg(scip, "start with ID %u, %d fixed variables\n", leaveids[current_id], nnon_zero_vars);
315  	
316  	         covered_ids[ncovered] = current_id;
317  	         ncovered++;
318  	
319  	         while( nnon_zero_vars >= comprdata->mincomvars )
320  	         {
321  	            /* find the next id which is not covered */
322  	            while( covered[next_id % nleaveids] && (next_id % nleaveids) != current_id )
323  	            {
324  	               /* go to the next node if the intersection is empty */
325  	               if( (signature0[current_id] & signature0[next_id % nleaveids]) == 0
326  	                  && (signature1[current_id] & signature1[next_id % nleaveids]) == 0 )
327  	                  next_id++;
328  	               else
329  	                  break;
330  	            }
331  	
332  	            if( (next_id % nleaveids) == current_id )
333  	               break;
334  	
335  	            next_id %= nleaveids;
336  	
337  	            if( covered[next_id] )
338  	               goto EMPTY;
339  	
340  	            ncommon_vars = 0;
341  	
342  	            /* calculate the intersection */
343  	            for( v = 0; v < nvars[next_id]; v++ )
344  	            {
345  	               if( common_vars[SCIPvarGetProbindex(vars[next_id][v])] == (vals[next_id][v] == 0 ? 1 : 2) )
346  	               {
347  	                  idx_common_vars[ncommon_vars] = SCIPvarGetProbindex(vars[next_id][v]);
348  	                  ncommon_vars++;
349  	               }
350  	            }
351  	
352  	            /* the number of common variables should be at least mincomvars */
353  	            if( ncommon_vars < comprdata->mincomvars )
354  	               goto EMPTY;
355  	
356  	            /* clear all non-zero entries which are not part of the intersection */
357  	            for( v = 0; v < nnon_zero_vars; )
358  	            {
359  	               int v2;
360  	               for( v2 = 0; v2 < ncommon_vars; v2++ )
361  	               {
362  	                  if( idx_non_zero[v] == idx_common_vars[v2] )
363  	                     break;
364  	               }
365  	
366  	               /* the variable is not part of the intersection */
367  	               if( v2 == ncommon_vars )
368  	               {
369  	                  common_vars[idx_non_zero[v]] = 0;
370  	
371  	                  /* replace the idx with the last */
372  	                  idx_non_zero[v] = idx_non_zero[nnon_zero_vars-1];
373  	                  nnon_zero_vars--;
374  	               }
375  	               else
376  	                  v++;
377  	            }
378  	
379  	            /* mark the node as covered */
380  	            if( nnon_zero_vars > 0 )
381  	            {
382  	               covered[next_id] = TRUE;
383  	               nnemptyinters++;
384  	
385  	               SCIPdebugMessage("-> found intersection with ID %u, %d/%d common variables\n", leaveids[next_id],
386  	                     nnon_zero_vars, MAX(nvars[current_id], nvars[next_id]));
387  	
388  	               covered_ids[ncovered] = next_id;
389  	               ncovered++;
390  	            }
391  	
392  	           EMPTY:
393  	            next_id++;
394  	
395  	            if( next_id % nleaveids == (current_id-1) % nleaveids )
396  	               break;
397  	         }
398  	
399  	         if( nnemptyinters > 0 )
400  	         {
401  	            /* increase the number of representatives */
402  	            if( nreps == 0 )
403  	               nreps += 2;
404  	            else
405  	               nreps++;
406  	
407  	            SCIP_CALL( SCIPallocBufferArray(scip, &repvars[nreps-2], nnon_zero_vars) ); /*lint !e866*/
408  	            SCIP_CALL( SCIPallocBufferArray(scip, &repvals[nreps-2], nnon_zero_vars) ); /*lint !e866*/
409  	            nrepvars[nreps-2] = nnon_zero_vars;
410  	
411  	            /* set the common variables and bounds (use non-zero idx)*/
412  	            for( k = 0; k < nnon_zero_vars; k++ )
413  	            {
414  	               repvars[nreps-2][k] = SCIPfindVar(scip, varnames[idx_non_zero[k]]);
415  	               repvals[nreps-2][k] = common_vars[idx_non_zero[k]] - 1;
416  	               assert(repvals[nreps-2][k] == 0 || repvals[nreps-2][k] == 1);
417  	            }
418  	         }
419  	         else
420  	         {
421  	            SCIPdebugMsg(scip, "-> did not found a intersection larger than %d\n", comprdata->mincomvars);
422  	            covered[current_id] = FALSE;
423  	         }
424  	
425  	         /* calculate the score */
426  	         score += (SCIP_Real) ncovered * nnon_zero_vars;
427  	
428  	         SCIPdebugMessage("-> current representation is of size %d with score = %.1f\n", nreps, score);
429  	
430  	         current_id = (current_id + 1) % nleaveids;
431  	
432  	         /* free memory */
433  	         SCIPfreeBlockMemoryArray(scip, &common_vars, SCIPgetNOrigVars(scip));
434  	
435  	         SCIPfreeBufferArray(scip, &covered_ids);
436  	         SCIPfreeBufferArray(scip, &idx_non_zero);
437  	         SCIPfreeBufferArray(scip, &idx_common_vars);
438  	      }
439  	
440  	     TERMINATE:
441  	
442  	      /* add the number of variables of uncovered nodes to the loss of information */
443  	      SCIPdebugMessage("-> final representation is of size %d with score = %.1f\n", nreps, score);
444  	
445  	      /* We found a better representation, i.e., with less loss of information.
446  	       * 1. reset the previous represenation
447  	       * 2. check if we need to reallocate the memory
448  	       * 3. set the new representation
449  	       */
450  	      if( nreps > 0 && SCIPisSumGT(scip, score, comprdata->score) )
451  	      {
452  	         /* reset the current representation */
453  	         SCIP_CALL( SCIPresetRepresentation(scip, comprdata->representatives, comprdata->nrepresentatives) );
454  	
455  	         /* ensure that enough memory is allocated */
456  	         if( comprdata->representativessize < nreps )
457  	         {
458  	            /* free the representatoin */
459  	            SCIP_CALL( SCIPfreeRepresentation(scip, comprdata->representatives, comprdata->nrepresentatives) );
460  	
461  	            /* reallocate memory */
462  	            SCIP_CALL( SCIPreallocMemoryArray(scip, &comprdata->representatives, nreps) );
463  	            comprdata->representativessize = nreps;
464  	
465  	            /* initialize the representation */
466  	            SCIP_CALL( SCIPinitRepresentation(scip, comprdata->representatives, comprdata->representativessize) );
467  	         }
468  	
469  	         /* set the new representation
470  	          *
471  	          * copy the new representation. we skip the last representative because it is implicitly given by the union of
472  	          * the logic-or constraints of all previous representatives.
473  	          */
474  	         comprdata->score = score;
475  	         comprdata->nrepresentatives = nreps;
476  	
477  	         for( k = 0; k < nreps-1; k++ )
478  	         {
479  	            int v;
480  	
481  	            for( v = 0; v < nrepvars[k]; v++ )
482  	            {
483  	               SCIP_CALL( SCIPaddReoptnodeBndchg(scip, comprdata->representatives[k], repvars[k][v],
484  	                     repvals[k][v], repvals[k][v] == 0 ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER) );
485  	            }
486  	         }
487  	
488  	         *result = SCIP_SUCCESS;
489  	      }
490  	
491  	      /* free representatives storage */
492  	      for( k = 0; k <= nreps-2; k++ )
493  	      {
494  	         SCIPfreeBufferArray(scip, &repvals[k]);
495  	         SCIPfreeBufferArray(scip, &repvars[k]);
496  	      }
497  	
498  	      SCIPfreeBufferArray(scip, &nrepvars);
499  	      SCIPfreeBufferArray(scip, &repvals);
500  	      SCIPfreeBufferArray(scip, &repvars);
501  	
502  	      /* free covered array */
503  	      SCIPfreeBufferArray(scip, &covered);
504  	   }
505  	
506  	   /* check if we have found a representation and construct the missing constraints */
507  	   if( comprdata->nrepresentatives > 0 )
508  	   {
509  	      SCIPdebugMessage("best representation found has %d leaf nodes and score = %g\n", comprdata->nrepresentatives, comprdata->score);
510  	
511  	      /* iterate over all representatives */
512  	      for( k = 0; k < comprdata->nrepresentatives-1; k++ )
513  	      {
514  	         int r;
515  	
516  	         /* add a constraint (corresponding to the branching path of k) to all representatives
517  	          * in the subtree induced by the sibling of k
518  	          */
519  	         for( r = k + 1; r < comprdata->nrepresentatives; r++ )
520  	         {
521  	            SCIP_VAR** pathvars;
522  	            SCIP_Real* pathvals;
523  	            SCIP_BOUNDTYPE* pathboundtypes;
524  	            SCIP_Real lhs;
525  	            SCIP_Bool linear;
526  	            int pathvarssize;
527  	            int npathvars;
528  	            int npathafterdualvars;
529  	            int i;
530  	
531  	            pathvarssize = SCIPreoptnodeGetNVars(comprdata->representatives[k]);
532  	
533  	            /* allocate buffer */
534  	            SCIP_CALL( SCIPallocBufferArray(scip, &pathvars, pathvarssize) );
535  	            SCIP_CALL( SCIPallocBufferArray(scip, &pathvals, pathvarssize) );
536  	            SCIP_CALL( SCIPallocBufferArray(scip, &pathboundtypes, pathvarssize) );
537  	
538  	            /* get the stored path */
539  	            SCIPgetReoptnodePath(scip, comprdata->representatives[k], pathvars, pathvals, pathboundtypes, pathvarssize,
540  	                  &npathvars, &npathafterdualvars);
541  	
542  	            lhs = 1.0;
543  	            linear = TRUE; /* todo: we have to adapt the compression to handle integer variables */
544  	
545  	            /* negate the branching path */
546  	            for( i = 0; i < npathvars; i++ )
547  	            {
548  	               assert(SCIPvarIsOriginal(pathvars[i]));
549  	
550  	               /* we have to construct a linear constraint that can be upgraded to a logic-or constraint
551  	                *
552  	                * each variable i with pathvals[i] == 0 and pathboundtypes[i] == SCIP_BOUNDTYPE_UPPER needs a coefficient
553  	                * of 1.0, all remaining variables (i.e., pathvals[i] == 1 and pathboundtypes[i] == SCIP_BOUNDTYPE_LOWER)
554  	                * need a -1.0 and we have to reduce the lhs by -1.0.
555  	                *
556  	                *        sum_{i : pathvals[i] == 0.0} x_i + sum_{j : pathvals[j] == 1.0} (1.0-x_{j}) >= 1.0
557  	                *  <==>  sum_{i : pathvals[i] == 0.0} x_i + sum_{j : pathvals[j] == 1.0}     -x_{j}  >= 1.0 - sum_{j : pathvals[j] == 1.0} 1.0
558  	                */
559  	               if( SCIPisEQ(scip, pathvals[i], 0.0) )
560  	               {
561  	                  assert(pathboundtypes[i] == SCIP_BOUNDTYPE_UPPER);
562  	
563  	                  pathvals[i] = 1.0;
564  	               }
565  	               else
566  	               {
567  	                  assert(SCIPisEQ(scip, pathvals[i], 1.0));
568  	                  assert(pathboundtypes[i] == SCIP_BOUNDTYPE_LOWER);
569  	
570  	                  pathvals[i] = -1.0;
571  	                  lhs -= 1.0;
572  	               }
573  	            }
574  	
575  	            SCIP_CALL( SCIPaddReoptnodeCons(scip, comprdata->representatives[r], pathvars, pathvals, NULL, lhs,
576  	                  SCIPinfinity(scip), npathvars, REOPT_CONSTYPE_DUALREDS, linear) );
577  	
578  	            /* free buffer */
579  	            SCIPfreeBufferArray(scip, &pathboundtypes);
580  	            SCIPfreeBufferArray(scip, &pathvals);
581  	            SCIPfreeBufferArray(scip, &pathvars);
582  	         }
583  	      }
584  	   }
585  	
586  	   /* free memory */
587  	   for( k = nleaveids-1; k >= 0; k-- )
588  	   {
589  	      SCIPfreeBufferArray(scip, &bounds[k]);
590  	      SCIPfreeBufferArray(scip, &vals[k]);
591  	      SCIPfreeBufferArray(scip, &vars[k]);
592  	   }
593  	
594  	   SCIPfreeBufferArray(scip, &signature1);
595  	   SCIPfreeBufferArray(scip, &signature0);
596  	
597  	   SCIPfreeBufferArray(scip, &varnames);
598  	   SCIPfreeBufferArray(scip, &lowerbounds);
599  	   SCIPfreeBufferArray(scip, &nvars);
600  	   SCIPfreeBufferArray(scip, &bounds);
601  	   SCIPfreeBufferArray(scip, &vals);
602  	   SCIPfreeBufferArray(scip, &vars);
603  	
604  	   SCIPfreeBlockMemoryArray(scip, &leaveids, nleaveids);
605  	
606  	   return SCIP_OKAY;
607  	}
608  	
609  	/** apply the found representation to the reopttree. */
610  	static
611  	SCIP_RETCODE applyCompression(
612  	   SCIP*                 scip,               /**< SCIP data structure */
613  	   SCIP_COMPR*           compr,              /**< compression method */
614  	   SCIP_COMPRDATA*       comprdata,          /**< compression data */
615  	   SCIP_RESULT*          result              /**< result pointer */
616  	   )
617  	{
618  	   SCIP_Bool success;
619  	   int r;
620  	
621  	   assert(scip != NULL);
622  	   assert(compr != NULL);
623  	   assert(comprdata != NULL);
624  	
625  	   *result = SCIP_DIDNOTRUN;
626  	
627  	   if( comprdata->nrepresentatives == 0 )
628  	      return SCIP_OKAY;
629  	
630  	   /* set references to the root node */
631  	   for( r = 0; r < comprdata->nrepresentatives; r++ )
632  	      SCIPreoptnodeSetParentID(comprdata->representatives[r], 0);
633  	
634  	   success = FALSE;
635  	   SCIP_CALL( SCIPsetReoptCompression(scip, comprdata->representatives, comprdata->nrepresentatives, &success) );
636  	
637  	   SCIP_CALL( SCIPfreeRepresentation(scip, comprdata->representatives, comprdata->representativessize) );
638  	
639  	   if( success )
640  	      *result = SCIP_SUCCESS;
641  	
642  	   return SCIP_OKAY;
643  	}
644  	
645  	/*
646  	 * Callback methods of tree compression
647  	 */
648  	
649  	/** copy method for tree compression plugins (called when SCIP copies plugins) */
650  	static
651  	SCIP_DECL_COMPRCOPY(comprCopyLargestrepr)
652  	{  /*lint --e{715}*/
653  	   assert(scip != NULL);
654  	   assert(compr != NULL);
655  	   assert(strcmp(SCIPcomprGetName(compr), COMPR_NAME) == 0);
656  	
657  	   /* call inclusion method of primal heuristic */
658  	   SCIP_CALL( SCIPincludeComprLargestrepr(scip) );
659  	
660  	   return SCIP_OKAY;
661  	}
662  	
663  	/** destructor of tree compression to free user data (called when SCIP is exiting) */
664  	static
665  	SCIP_DECL_COMPRFREE(comprFreeLargestrepr)
666  	{
667  	   SCIP_COMPRDATA* comprdata;
668  	
669  	   assert(scip != NULL);
670  	   assert(compr != NULL);
671  	
672  	   comprdata = SCIPcomprGetData(compr);
673  	   assert(comprdata != NULL);
674  	
675  	   SCIPfreeBlockMemory(scip, &comprdata);
676  	   SCIPcomprSetData(compr, NULL);
677  	
678  	   return SCIP_OKAY;
679  	}
680  	
681  	/** deinitialization method of tree compression (called before transformed problem is freed) */
682  	static
683  	SCIP_DECL_COMPREXIT(comprExitLargestrepr)
684  	{
685  	   SCIP_COMPRDATA* comprdata;
686  	
687  	   assert(scip != NULL);
688  	   assert(compr != NULL);
689  	
690  	   comprdata = SCIPcomprGetData(compr);
691  	   assert(comprdata != NULL);
692  	
693  	   if( comprdata->initialized )
694  	   {
695  	      if( comprdata->representativessize > 0 )
696  	      {
697  	         SCIPfreeMemoryArray(scip, &comprdata->representatives);
698  	      }
699  	
700  	      comprdata->representatives = NULL;
701  	      comprdata->representativessize = 0;
702  	      comprdata->nrepresentatives = 0;
703  	      comprdata->initialized = FALSE;
704  	   }
705  	
706  	   return SCIP_OKAY;
707  	}
708  	
709  	/** execution method of tree compression */
710  	static
711  	SCIP_DECL_COMPREXEC(comprExecLargestrepr)
712  	{
713  	   SCIP_COMPRDATA* comprdata;
714  	
715  	   comprdata = SCIPcomprGetData(compr);
716  	   assert(comprdata != NULL);
717  	
718  	   if( !comprdata->initialized )
719  	   {
720  	      SCIPdebugMsg(scip, ">> initializing <%s>\n", COMPR_NAME);
721  	
722  	      comprdata->representativessize = DEFAUL_MEM_REPR;
723  	      comprdata->nrepresentatives = 0;
724  	      comprdata->rate = 0.0;
725  	      comprdata->score = 0.0;
726  	      comprdata->nnodes = 0;
727  	      SCIP_CALL( SCIPallocClearMemoryArray(scip, &comprdata->representatives, comprdata->representativessize) );
728  	
729  	      /* initialize the representation */
730  	      SCIP_CALL( SCIPinitRepresentation(scip, comprdata->representatives, comprdata->representativessize) );
731  	
732  	      comprdata->initialized = TRUE;
733  	   }
734  	
735  	   *result = SCIP_DIDNOTRUN;
736  	
737  	   /* try to find a representation */
738  	   SCIP_CALL( constructCompression(scip, compr, comprdata, result) );
739  	
740  	   assert(*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND || *result == SCIP_SUCCESS);
741  	
742  	   /* apply the representation, if some was found */
743  	   if( *result == SCIP_SUCCESS )
744  	   {
745  	      SCIP_CALL( applyCompression(scip, compr, comprdata, result) );
746  	      assert(*result == SCIP_DIDNOTRUN || *result == SCIP_SUCCESS);
747  	
748  	      SCIPdebugMsg(scip, "->%s apply compression.\n", *result == SCIP_DIDNOTRUN ? " did not" : "");
749  	   }
750  	   else
751  	   {
752  	      SCIP_CALL( SCIPfreeRepresentation(scip, comprdata->representatives, comprdata->representativessize) );
753  	   }
754  	
755  	   return SCIP_OKAY;
756  	}
757  	
758  	/*
759  	 * tree compression specific interface methods
760  	 */
761  	
762  	/** creates the largestrepr tree compression and includes it in SCIP */
763  	SCIP_RETCODE SCIPincludeComprLargestrepr(
764  	   SCIP*                 scip                /**< SCIP data structure */
765  	   )
766  	{
767  	   SCIP_COMPRDATA* comprdata;
768  	   SCIP_COMPR* compr;
769  	
770  	   /* create largestrepr tree compression data */
771  	   SCIP_CALL( SCIPallocBlockMemory(scip, &comprdata) );
772  	   assert(comprdata != NULL);
773  	   comprdata->initialized = FALSE;
774  	
775  	   /* include tree compression */
776  	   SCIP_CALL( SCIPincludeComprBasic(scip, &compr, COMPR_NAME, COMPR_DESC, COMPR_PRIORITY, COMPR_MINNNODES,
777  	         comprExecLargestrepr, comprdata) );
778  	
779  	   assert(compr != NULL);
780  	
781  	   /* set non fundamental callbacks via setter functions */
782  	   SCIP_CALL( SCIPsetComprCopy(scip, compr, comprCopyLargestrepr) );
783  	   SCIP_CALL( SCIPsetComprExit(scip, compr, comprExitLargestrepr) );
784  	   SCIP_CALL( SCIPsetComprFree(scip, compr, comprFreeLargestrepr) );
785  	
786  	   /* add largestrepr tree compression parameters */
787  	   SCIP_CALL( SCIPaddIntParam(scip, "compression/" COMPR_NAME "/iterations", "number of runs in the constrained part.",
788  	         &comprdata->niters, FALSE, DEFAULT_ITERS, 1, INT_MAX, NULL, NULL) );
789  	   SCIP_CALL( SCIPaddIntParam(scip, "compression/" COMPR_NAME "/mincommonvars", "minimal number of common variables.",
790  	         &comprdata->mincomvars, FALSE, DEFAULT_MINCOMMONVARS, 1, INT_MAX, NULL, NULL) );
791  	
792  	   return SCIP_OKAY;
793  	}
794