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