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