Scippy

SCIP

Solving Constraint Integer Programs

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