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