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-2024 Zuse Institute Berlin (ZIB) */
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
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 */
64struct 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 */
89static
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 */
125static
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
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) );
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 */
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 */
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);
603
604 SCIPfreeBlockMemoryArray(scip, &leaveids, nleaveids);
605
606 return SCIP_OKAY;
607}
608
609/** apply the found representation to the reopttree. */
610static
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) */
650static
651SCIP_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) */
664static
665SCIP_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) */
682static
683SCIP_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 */
710static
711SCIP_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}
SCIP_Real * r
Definition: circlepacking.c:59
#define DEFAULT_ITERS
#define COMPR_PRIORITY
#define DEFAUL_MEM_REPR
static SCIP_DECL_COMPREXIT(comprExitLargestrepr)
static SCIP_RETCODE constructCompression(SCIP *scip, SCIP_COMPR *compr, SCIP_COMPRDATA *comprdata, SCIP_RESULT *result)
static SCIP_DECL_COMPRFREE(comprFreeLargestrepr)
static void calcSignature(SCIP_VAR **vars, SCIP_Real *vals, int nvars, uint64_t *signature0, uint64_t *signature1)
#define COMPR_DESC
static SCIP_DECL_COMPRCOPY(comprCopyLargestrepr)
SCIP_RETCODE SCIPincludeComprLargestrepr(SCIP *scip)
#define COMPR_MINNNODES
#define COMPR_NAME
static SCIP_DECL_COMPREXEC(comprExecLargestrepr)
static SCIP_RETCODE applyCompression(SCIP *scip, SCIP_COMPR *compr, SCIP_COMPRDATA *comprdata, SCIP_RESULT *result)
#define DEFAULT_MINCOMMONVARS
largestrepr tree compression
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2432
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition: scip_prob.c:2685
#define SCIPhashSignature64(a)
Definition: pub_misc.h:549
#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
SCIP_RETCODE SCIPsetComprExit(SCIP *scip, SCIP_COMPR *compr, SCIP_DECL_COMPREXIT((*comprexit)))
Definition: scip_compr.c:189
SCIP_RETCODE SCIPsetComprCopy(SCIP *scip, SCIP_COMPR *compr, SCIP_DECL_COMPRCOPY((*comprcopy)))
Definition: scip_compr.c:141
SCIP_RETCODE SCIPsetComprFree(SCIP *scip, SCIP_COMPR *compr, SCIP_DECL_COMPRFREE((*comprfree)))
Definition: scip_compr.c:157
void SCIPcomprSetData(SCIP_COMPR *compr, SCIP_COMPRDATA *comprdata)
Definition: compr.c:363
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
SCIP_COMPRDATA * SCIPcomprGetData(SCIP_COMPR *compr)
Definition: compr.c:353
const char * SCIPcomprGetName(SCIP_COMPR *compr)
Definition: compr.c:456
int SCIPcomprGetMinNodes(SCIP_COMPR *compr)
Definition: compr.c:500
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:70
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:66
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:80
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
int SCIPgetNReoptLeaves(SCIP *scip, SCIP_NODE *node)
Definition: scip_reopt.c:141
SCIP_RETCODE SCIPaddReoptnodeBndchg(SCIP *scip, SCIP_REOPTNODE *reoptnode, SCIP_VAR *var, SCIP_Real bound, SCIP_BOUNDTYPE boundtype)
Definition: scip_reopt.c:176
SCIP_REOPTNODE * SCIPgetReoptnode(SCIP *scip, unsigned int id)
Definition: scip_reopt.c:154
SCIP_RETCODE SCIPinitRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
Definition: scip_reopt.c:289
SCIP_RETCODE SCIPsetReoptCompression(SCIP *scip, SCIP_REOPTNODE **representation, int nrepresentatives, SCIP_Bool *success)
Definition: scip_reopt.c:204
SCIP_RETCODE SCIPgetReoptLeaveIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int idssize, int *nids)
Definition: scip_reopt.c:101
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
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
SCIP_RETCODE SCIPfreeRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
Definition: scip_reopt.c:348
SCIP_RETCODE SCIPresetRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
Definition: scip_reopt.c:319
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisSumGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Bool SCIPvarIsOriginal(SCIP_VAR *var)
Definition: var.c:17548
memory allocation routines
public methods for tree compressions
public methods for message output
#define SCIPdebugMessage
Definition: pub_message.h:96
public data structures and miscellaneous methods
public methods for reoptimization
SCIP_Real SCIPreoptnodeGetLowerbound(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5864
void SCIPreoptnodeSetParentID(SCIP_REOPTNODE *reoptnode, unsigned int parentid)
Definition: reopt.c:5919
int SCIPreoptnodeGetNVars(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5821
public methods for problem variables
public methods for compression plugins
general public methods
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for reoptimization
struct SCIP_ComprData SCIP_COMPRDATA
Definition: type_compr.h:49
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ REOPT_CONSTYPE_DUALREDS
Definition: type_reopt.h:72
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_PRESOLVED
Definition: type_set.h:51