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