SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
presol_gateextraction.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 presol_gateextraction.c
26 * @ingroup DEFPLUGINS_PRESOL
27 * @brief gateextraction presolver
28 * @author Michael Winkler
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/cons_and.h"
35#include "scip/cons_logicor.h"
36#include "scip/cons_setppc.h"
38#include "scip/pub_cons.h"
39#include "scip/pub_message.h"
40#include "scip/pub_misc.h"
41#include "scip/pub_misc_sort.h"
42#include "scip/pub_presol.h"
43#include "scip/pub_var.h"
44#include "scip/scip_cons.h"
45#include "scip/scip_general.h"
46#include "scip/scip_mem.h"
47#include "scip/scip_message.h"
48#include "scip/scip_param.h"
49#include "scip/scip_presol.h"
50#include "scip/scip_prob.h"
51#include "scip/scip_var.h"
52#include <string.h>
53
54#define PRESOL_NAME "gateextraction"
55#define PRESOL_DESC "presolver extracting gate(and)-constraints"
56#define PRESOL_PRIORITY 1000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators */
57#define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
58#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
59
60#define HASHSIZE_LOGICORCONS 500 /**< minimal size of hash table in logicor constraint tables */
61#define HASHSIZE_SETPPCCONS 500 /**< minimal size of hash table in setppc constraint tables */
62
63#define DEFAULT_ONLYSETPART FALSE /**< should only set-partitioning constraints be extracted and no and-constraints */
64#define DEFAULT_SEARCHEQUATIONS TRUE /**< should we try to extract set-partitioning constraint out of one logicor
65 * and one corresponding set-packing constraint
66 */
67#define DEFAULT_SORTING 1 /**< order logicor contraints to extract big-gates before smaller ones (-1), do
68 * not order them (0) or order them to extract smaller gates at first (1)
69 */
70
71
72/* This presolver tries to extract gate-constraints meaning and-constraints and set-partitioning constraints (and could
73 * be expanded to find xor-constraints too). This is done by detecting linearizations or systems of inequalities which
74 * form an and-constraint or a set-partitioning constraint. An example:
75 *
76 * we have a logicor constraint of the form: x + y + z >= 1
77 *
78 * and we also have the following set-packing constraints: (x + y <= 1 and x + z <= 1) <=> (~x + ~y >= 1 and ~x + ~z >= 1)
79 *
80 * - these three constraints form an and-constraint: x = ~y * ~z (x = AND(~y,~z))
81 *
82 * if an additional set-packing constraint exists: y + z <= 1
83 *
84 * - these four constraints form a set-partitioning cons.: x + y + z = 1
85 *
86 * some information can be found:
87 *
88 * http://www.cs.ubc.ca/~hutter/earg/papers07/cnf-structure.pdf
89 * http://www.cadence.com/cn/cadence/cadence_labs/Documents/niklas_SAT_2005_Effective.pdf
90 *
91 * We also do some check for logicor and set-packing/-partitioning constraint with the same variables to upgrade these
92 * both constraints into one. For example:
93 *
94 * x + y + z >= 1 and x + y + z <= 1 form x + y + z = 1
95 *
96 */
97
98
99/*
100 * Data structures
101 */
102
103
104/** data object to compare constraint easier */
106{
107 SCIP_CONS* cons; /**< pointer the the corresponding constraint */
108 SCIP_VAR** vars; /**< constraint variables used for hash comparison */
109 int nvars; /**< number of variables */
110};
111typedef struct HashData HASHDATA;
112
113
114/** presolver data */
115struct SCIP_PresolData
116{
117 HASHDATA* setppchashdatas; /**< setppc-hashdata storage */
118 SCIP_HASHTABLE* hashdatatable; /**< setppc-hashdata hashtable for usable setppc constraints */
119 SCIP_HASHTABLE* setppchashtable; /**< setppc hashtable for usable setppc constraints */
120 SCIP_HASHTABLE* logicorhashtable; /**< logicor hashtable for usable logicor constraints */
121 SCIP_CONS** usefullogicor; /**< array for usable logicors */
122 int nusefullogicor; /**< number of usable logicors */
123 int susefullogicor; /**< size of array for usable logicor constraints */
124 int nsetppchashdatas; /**< number of setppchashdata elements added to the hashtable */
125 int ssetppchashdatas; /**< size of setppchashdata elements added to the hashtable */
126 int ngates; /**< number of found gates in presolving */
127 int firstchangedlogicor;/**< position of the first new/changed logicor constraint in the
128 * usefullogicor array
129 */
130 int maxnvarslogicor; /**< maximal number of variables a logicor constraint has */
131 int sorting; /**< integer parameter how to sort logicor constraints for extracting gates */
132 SCIP_Bool usefulsetppcexist; /**< did we find usable set-packing constraints for gate extraction */
133 SCIP_Bool usefullogicorexist; /**< did we find usable logicor constraints for gate extraction */
134 SCIP_Bool newsetppchashdatas; /**< flag indicating whether we found new set-packing constraint with two
135 * variables since the last presolving round
136 */
137 SCIP_Bool initialized; /**< was data alredy be initialized */
138 SCIP_Bool onlysetpart; /**< boolean parameter whetehr we only want to extract linear gates */
139 SCIP_Bool searchequations; /**< boolean parameter whetehr we want to search for equations arising from
140 * logicor and setppc constraints
141 */
142};
143
144
145/*
146 * Local methods
147 */
148
149
150/** returns TRUE iff both keys are equal; two constraints are equal if they have the same pointer */
151static
153{
154#ifndef NDEBUG
155 SCIP* scip;
156#endif
159 int v;
160
161 hashdata1 = (HASHDATA*)key1;
162 hashdata2 = (HASHDATA*)key2;
163#ifndef NDEBUG
164 scip = (SCIP*)userptr;
165 assert(scip != NULL);
166#endif
167
168 /* check data structure */
169 assert(hashdata1->nvars == 2);
170 assert(hashdata2->nvars == 2);
171 /* at least one data object needs to be have a real set packing constraint */
172 /* TODO why does this assert fail on one instance when problem is freed
173 * using the new hashing: assert(hashdata1->cons != NULL || hashdata2->cons != NULL);
174 */
175
176 for( v = 1; v >= 0; --v )
177 {
178 /* tests if variables are equal */
179 if( hashdata1->vars[v] != hashdata2->vars[v] )
180 return FALSE;
181
182 assert(SCIPvarCompare(hashdata1->vars[v], hashdata2->vars[v]) == 0);
183 }
184
185 /* a hashdata object is only equal if it has the same constraint pointer, or one has no constraint pointer, latter
186 * means that this hashdata object is derived from a logicor constraint
187 */
188 if( hashdata1->cons == NULL || hashdata2->cons == NULL || hashdata1->cons == hashdata2->cons )
189 return TRUE;
190 else
191 return FALSE;
192}
193
194/** returns the hash value of the key */
195static
197{ /*lint --e{715}*/
199 unsigned int hashval;
200
201 hashdata = (HASHDATA*)key;
202 assert(hashdata != NULL);
203 assert(hashdata->vars != NULL);
204 assert(hashdata->nvars == 2);
205
206 /* if we have only two variables we store at each 16 bits of the hash value the index of a variable */
207 hashval = ((unsigned int)SCIPvarGetIndex(hashdata->vars[1]) << 16) + (unsigned int) SCIPvarGetIndex(hashdata->vars[0]); /*lint !e701*/
208
209 return hashval;
210}
211
212
213/** returns TRUE iff both keys are equal; two constraints are equal if they have the same pointer */
214static
216{
217#ifndef NDEBUG
218 SCIP* scip;
219#endif
222 int v;
223
224 hashdata1 = (HASHDATA*)key1;
225 hashdata2 = (HASHDATA*)key2;
226#ifndef NDEBUG
227 scip = (SCIP*)userptr;
228 assert(scip != NULL);
229#endif
230
231 /* check data structure */
232 assert(hashdata1->nvars >= 2);
233 assert(hashdata2->nvars >= 2);
234 /* at least one data object needs to be have a real set-packing/partitioning constraint */
235 assert(hashdata1->cons != NULL || hashdata2->cons != NULL);
236
237 if( hashdata1->nvars != hashdata2->nvars )
238 return FALSE;
239
240 for( v = hashdata1->nvars - 1; v >= 0; --v )
241 {
242 /* tests if variables are equal */
243 if( hashdata1->vars[v] != hashdata2->vars[v] )
244 return FALSE;
245
246 assert(SCIPvarCompare(hashdata1->vars[v], hashdata2->vars[v]) == 0);
247 }
248
249 /* a hashdata object is only equal if it has the same constraint pointer, or one has no constraint pointer, latter
250 * means that this hashdata object is derived from a logicor constraint
251 */
252 if( hashdata1->cons == NULL || hashdata2->cons == NULL || hashdata1->cons == hashdata2->cons )
253 return TRUE;
254 else
255 return FALSE;
256}
257
258/** returns the hash value of the key */
259static
261{ /*lint --e{715}*/
263
264 hashdata = (HASHDATA*)key;
265 assert(hashdata != NULL);
266 assert(hashdata->vars != NULL);
267 assert(hashdata->nvars >= 2);
268
269 return SCIPhashFour(hashdata->nvars, SCIPvarGetIndex(hashdata->vars[0]), \
270 SCIPvarGetIndex(hashdata->vars[hashdata->nvars/2]), \
271 SCIPvarGetIndex(hashdata->vars[hashdata->nvars-1]));
272}
273
274/** initialize gateextraction presolver data */
275static
277 SCIP_PRESOLDATA* presoldata /**< data object of presolver */
278 )
279{
280 assert(presoldata != NULL);
281
282 presoldata->usefullogicor = NULL;
283 presoldata->nusefullogicor = 0;
284 presoldata->susefullogicor = 0;
285 presoldata->firstchangedlogicor = -1;
286 presoldata->maxnvarslogicor = 0;;
287 presoldata->nsetppchashdatas = 0;
288 presoldata->ssetppchashdatas = 0;
289 presoldata->ngates = 0;
290 presoldata->usefulsetppcexist = FALSE;
291 presoldata->usefullogicorexist = FALSE;
292 presoldata->newsetppchashdatas = FALSE;
293 presoldata->initialized = FALSE;
294
295 presoldata->hashdatatable = NULL;
296 presoldata->setppchashtable = NULL;
297 presoldata->logicorhashtable = NULL;
298}
299
300/** initialize gateextraction hashtables */
301static
303 SCIP* scip, /**< SCIP data structure */
304 SCIP_PRESOLDATA* presoldata /**< data object of presolver */
305 )
306{
307 assert(scip != NULL);
308 assert(presoldata != NULL);
309
310 assert(presoldata->nusefullogicor == 0);
311 assert(presoldata->susefullogicor == 0);
312 assert(presoldata->nsetppchashdatas == 0);
313 assert(presoldata->ssetppchashdatas == 0);
314 assert(presoldata->firstchangedlogicor == -1);
315 assert(presoldata->ngates == 0);
316 assert(presoldata->usefullogicorexist == FALSE);
317 assert(presoldata->usefulsetppcexist == FALSE);
318 assert(presoldata->newsetppchashdatas == FALSE);
319 assert(presoldata->initialized == FALSE);
320
321 assert(presoldata->hashdatatable == NULL);
322 assert(presoldata->setppchashtable == NULL);
323 assert(presoldata->logicorhashtable == NULL);
324
325 /* create hashtables */
326 SCIP_CALL( SCIPhashtableCreate(&(presoldata->hashdatatable), SCIPblkmem(scip), HASHSIZE_SETPPCCONS,
328 SCIP_CALL( SCIPhashtableCreate(&(presoldata->setppchashtable), SCIPblkmem(scip), HASHSIZE_SETPPCCONS,
330 SCIP_CALL( SCIPhashtableCreate(&(presoldata->logicorhashtable), SCIPblkmem(scip), HASHSIZE_LOGICORCONS,
332
333 return SCIP_OKAY;
334}
335
336
337/** create useful set-packing information by adding new set-packing constraints with two variables */
338static
340 SCIP* scip, /**< SCIP data structure */
341 SCIP_PRESOLDATA* presoldata, /**< data object of presolver */
342 SCIP_CONS** setppcs, /**< active setppc constraints */
343 int nsetppcs, /**< number of active setppc constraints */
344 SCIP_CONS** logicors, /**< active logicor constraints */
345 int nlogicors /**< number of active logicor constraints */
346 )
347{
349 int nusefulconss = 0;
350 int size;
351 int c;
352
353 assert(scip != NULL);
354 assert(presoldata != NULL);
355 assert(setppcs != NULL);
356 assert(nsetppcs > 0);
357 assert(logicors != NULL);
358 assert(nlogicors > 0);
359 assert(presoldata->setppchashtable != NULL);
360 assert(presoldata->logicorhashtable != NULL);
361
362 presoldata->initialized = TRUE;
363
364 size = MAX(nsetppcs, nlogicors);
365
366 /* temporary memory for collecting set-packing constraints */
368
369 if( !presoldata->usefulsetppcexist )
370 {
371 /* find set-packing constraints with exactly two variables */
372 for( c = 0; c < nsetppcs; ++c )
373 {
375
377 {
378 /* insert new element in hashtable */
379 SCIP_CALL( SCIPhashtableInsert(presoldata->setppchashtable, (void*) setppcs[c]) );
380
382 ++nusefulconss;
383 }
384 }
385
386 /* add usefulconss constraints to hashdata elements */
387 if( nusefulconss > 0 )
388 {
389 SCIP_Bool negated[2];
390 int h;
391
392 presoldata->usefulsetppcexist = TRUE;
393 presoldata->ssetppchashdatas = nusefulconss;
394
395 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(presoldata->setppchashdatas), nusefulconss) );
396
397 h = 0;
398 for( c = 0; c < nusefulconss; ++c )
399 {
403
404 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(presoldata->setppchashdatas[h].vars), setppcvars, 2) );
405
406 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[h].vars[0], &(presoldata->setppchashdatas[h].vars[0]), &(negated[0])) );
407 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[h].vars[1], &(presoldata->setppchashdatas[h].vars[1]), &(negated[1])) );
408
409 if( SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[0]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[0]) == SCIP_VARSTATUS_MULTAGGR
410 || SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[1]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[1]) == SCIP_VARSTATUS_MULTAGGR )
411 {
412 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[h].vars), 2);
413 continue;
414 }
415
416 presoldata->setppchashdatas[h].nvars = 2;
417
418 /* capture variables */
419 SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[h].vars[0]) );
420 SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[h].vars[1]) );
421
422 /* order the variables after their index */
423 if( SCIPvarGetIndex(presoldata->setppchashdatas[h].vars[0]) > SCIPvarGetIndex(presoldata->setppchashdatas[h].vars[1]) )
424 {
425 SCIP_VAR* tmp = presoldata->setppchashdatas[h].vars[0];
426 presoldata->setppchashdatas[h].vars[0] = presoldata->setppchashdatas[h].vars[1];
427 presoldata->setppchashdatas[h].vars[1] = tmp;
428 }
429
430 presoldata->setppchashdatas[h].cons = usefulconss[c];
431
432 SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[h]) );
434
435 ++h;
436 }
437 presoldata->nsetppchashdatas = h;
438
439 if( presoldata->nsetppchashdatas > 0 )
440 presoldata->newsetppchashdatas = TRUE;
441 }
442 }
443
444 nusefulconss = 0;
445
446 if( !presoldata->usefullogicorexist )
447 {
448 /* capture all logicor constraints */
449 for( c = 0; c < nlogicors; ++c )
450 {
452
454 {
455 /* insert new element in hashtable */
456 SCIP_CALL( SCIPhashtableInsert(presoldata->logicorhashtable, (void*) logicors[c]) );
458
460 ++nusefulconss;
461
462 /* update maximal entries in a logicor constraint */
463 if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, logicors[c]) )
464 presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, logicors[c]);
465 }
466 }
467
468 /* no usefulconss constraints */
469 if( nusefulconss > 0 )
470 {
471 presoldata->firstchangedlogicor = 0;
472 presoldata->usefullogicorexist = TRUE;
473 presoldata->susefullogicor = nusefulconss;
474 presoldata->nusefullogicor = nusefulconss;
475 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &presoldata->usefullogicor, usefulconss, presoldata->susefullogicor) );
476 }
477 }
478
479 /* free temporary memory */
481
482 return SCIP_OKAY;
483}
484
485
486/** remove old setppchashdatas objects, so that the allocated memory will stay low */
487static
489 SCIP* scip, /**< SCIP data structure */
490 SCIP_PRESOLDATA* presoldata /**< data object of presolver */
491 )
492{
493 assert(scip != NULL);
494 assert(presoldata != NULL);
495
496 if( presoldata->usefulsetppcexist )
497 {
498 int c;
499
500 assert(presoldata->setppchashdatas != NULL || presoldata->nsetppchashdatas == 0);
501
502 for( c = presoldata->nsetppchashdatas - 1; c >= 0; --c )
503 {
504 SCIP_Bool removeentry = FALSE;
505
506 assert(presoldata->setppchashdatas[c].cons != NULL);
507
508 if( SCIPconsIsDeleted(presoldata->setppchashdatas[c].cons) || SCIPconsIsModifiable(presoldata->setppchashdatas[c].cons)
509 || SCIPgetTypeSetppc(scip, presoldata->setppchashdatas[c].cons) != SCIP_SETPPCTYPE_PACKING || SCIPgetNVarsSetppc(scip, presoldata->setppchashdatas[c].cons) != 2 )
510 {
512 }
513 else
514 {
515 SCIP_VAR* vars[2];
516 SCIP_Bool negated[2];
517
518 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[c].vars[0], &(vars[0]), &(negated[0])) );
519 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[c].vars[1], &(vars[1]), &(negated[1])) );
520
523 || presoldata->setppchashdatas[c].vars[0] != vars[0] || presoldata->setppchashdatas[c].vars[1] != vars[1] )
524 {
526 }
527 }
528
529 if( removeentry )
530 {
531 /* remove constraint from setppc-hashtable */
532 assert(SCIPhashtableExists(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons));
533 SCIP_CALL( SCIPhashtableRemove(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons) );
534
535 /* remove hashdata entry from hashtable */
536 SCIP_CALL( SCIPhashtableRemove(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]) );
537
538 /* release old constraints */
539 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->setppchashdatas[c].cons)) );
540
541 /* release variables */
542 SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[0])) );
543 SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[1])) );
544
545 /* free memory for variables */
546 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[c].vars), 2);
547
548 if( c < presoldata->nsetppchashdatas - 1 )
549 {
550 /* remove old hashdata entry from hashtable */
551 SCIP_CALL( SCIPhashtableRemove(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1]) );
552 }
553
554 /* move last content to free position */
555 presoldata->setppchashdatas[c].cons = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].cons;
556 presoldata->setppchashdatas[c].vars = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].vars;
557 presoldata->setppchashdatas[c].nvars = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].nvars;
558
559 if( c < presoldata->nsetppchashdatas - 1 )
560 {
561 /* add new hashdata entry from hashtable */
562 SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]) );
563 }
564 --(presoldata->nsetppchashdatas);
565 }
566 }
567
568#ifndef NDEBUG
569 for( c = presoldata->nsetppchashdatas - 1; c >= 0; --c )
570 {
571 assert(presoldata->setppchashdatas[c].nvars == 2);
572 assert(presoldata->setppchashdatas[c].vars != NULL);
573 assert(presoldata->setppchashdatas[c].vars[0] != NULL);
574 assert(presoldata->setppchashdatas[c].vars[1] != NULL);
575 assert(presoldata->setppchashdatas[c].cons != NULL);
576 assert(SCIPconsIsActive(presoldata->setppchashdatas[c].cons));
577 assert(SCIPhashtableExists(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]));
578 assert(SCIPhashtableExists(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons));
579 }
580#endif
581 }
582
583 return SCIP_OKAY;
584}
585
586/** refresh useful set-packing information, delete redundant constraints and add new constraints */
587static
589 SCIP* scip, /**< SCIP data structure */
590 SCIP_PRESOLDATA* presoldata, /**< data object of presolver */
591 SCIP_CONS** setppcs, /**< active setppc constraints */
592 int nsetppcs, /**< number of active setppc constraints */
593 SCIP_CONS** logicors, /**< active setppc constraints */
594 int nlogicors /**< number of active setppc constraints */
595 )
596{
598 int c;
599
600 assert(scip != NULL);
601 assert(presoldata != NULL);
602 assert(setppcs != NULL);
603 assert(nsetppcs > 0);
604 assert(logicors != NULL);
605 assert(nlogicors > 0);
606 assert(presoldata->initialized);
607 assert(presoldata->setppchashtable != NULL);
608 assert(presoldata->logicorhashtable != NULL);
609
610 /* check if there already exist some set-packing and some logicor constraints with the right amount of variables */
611 if( !presoldata->usefulsetppcexist || !presoldata->usefullogicorexist )
612 {
613 SCIP_Bool usefullogicorexisted = presoldata->usefullogicorexist;
614
616
617 /* if we already had useful logicor constraints but did not find any useful setppc constraint, the maximal number
618 * of variables appearing in a logicor constraint was not updated, so we do it here
619 */
620 if( usefullogicorexisted && !presoldata->usefulsetppcexist )
621 {
622 /* correct maximal number of varables in logicor constraints */
623 for( c = nlogicors - 1; c >= 0; --c )
624 {
626
627 /* update maximal entries in a logicor constraint */
628 if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, logicors[c]) )
629 presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, logicors[c]);
630 }
631 }
632
633 /* no correct logicor or set-packing constraints available, so abort */
634 if( !presoldata->usefulsetppcexist || !presoldata->usefullogicorexist )
635 return SCIP_OKAY;
636 }
637
638 /* correct old data */
639 SCIP_CALL( cleanupHashDatas(scip, presoldata) );
640
641 oldnsetppchashdatas = presoldata->nsetppchashdatas;
642
643 /* first update setppc part */
644 /* add new setppc constraints */
645 for( c = nsetppcs - 1; c >= 0; --c )
646 {
648
650 {
651 /* check if constraint is new, and correct array size if necessary */
652 if( !SCIPhashtableExists(presoldata->setppchashtable, (void*) setppcs[c]) )
653 {
655 SCIP_Bool negated[2];
656
657 /* resize array if necessary */
658 if( presoldata->nsetppchashdatas == presoldata->ssetppchashdatas )
659 {
660 int newsize;
661 int d;
662
663 newsize = SCIPcalcMemGrowSize(scip, presoldata->nsetppchashdatas + 1);
664
665 /* array already at maximal size */
666 if( newsize <= presoldata->ssetppchashdatas )
667 return SCIP_NOMEMORY;
668
669 /* correct hashtable, remove old elements */
670 SCIPhashtableRemoveAll(presoldata->hashdatatable);
671
672 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(presoldata->setppchashdatas), presoldata->ssetppchashdatas, newsize) );
673 presoldata->ssetppchashdatas = newsize;
674
675 /* add all elements to the hashtable again */
676 for( d = presoldata->nsetppchashdatas - 1; d >= 0; --d )
677 {
678 SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[d]) );
679 }
680 }
681
682 /* insert new element in hashtable */
683 SCIP_CALL( SCIPhashtableInsert(presoldata->setppchashtable, (void*) setppcs[c]) );
684
687
688 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars), setppcvars, 2) );
689 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0], &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]), &(negated[0])) );
690 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1], &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]), &(negated[1])) );
691
692 if( SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) == SCIP_VARSTATUS_MULTAGGR
693 || SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) == SCIP_VARSTATUS_MULTAGGR )
694 {
695 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars), 2);
696 continue;
697 }
698
699 presoldata->setppchashdatas[presoldata->nsetppchashdatas].nvars = 2;
700
701 /* capture variables */
702 SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) );
703 SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) );
704
705 /* order the variables after their index */
706 if( SCIPvarGetIndex(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) > SCIPvarGetIndex(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) )
707 {
708 SCIP_VAR* tmp = presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0];
709 presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0] = presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1];
710 presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1] = tmp;
711 }
712
713 presoldata->setppchashdatas[presoldata->nsetppchashdatas].cons = setppcs[c];
714
715 SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[presoldata->nsetppchashdatas]) );
717
718 ++(presoldata->nsetppchashdatas);
719 }
720 }
721 }
722
723 /* if we found new set-packing constraints, we want to check against all logicors */
724 if( oldnsetppchashdatas < presoldata->nsetppchashdatas )
725 presoldata->newsetppchashdatas = TRUE;
726
727 /* now logicor part */
728 /* removed last deleted logicor constraints from local presolver data */
729 while( presoldata->nusefullogicor > 0 && !SCIPconsIsActive(presoldata->usefullogicor[presoldata->nusefullogicor - 1]) )
730 {
731 SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) presoldata->usefullogicor[presoldata->nusefullogicor - 1]) );
732 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->usefullogicor[presoldata->nusefullogicor - 1])) );
733
734 --(presoldata->nusefullogicor);
735 }
736
737 /* remove old inactive logicor constraints */
738 for( c = presoldata->nusefullogicor - 1; c >= 0; --c )
739 {
740 /* update maximal entries in a logicor constraint */
741 if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]) )
742 presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]);
743
744 if( !SCIPconsIsActive(presoldata->usefullogicor[c]) || SCIPconsIsModifiable(presoldata->usefullogicor[c]) || SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]) < 3 )
745 {
746 SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) presoldata->usefullogicor[c]) );
747 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->usefullogicor[c])) );
748
749 presoldata->usefullogicor[c] = presoldata->usefullogicor[presoldata->nusefullogicor - 1];
750 --(presoldata->nusefullogicor);
751 }
752 }
753
754 presoldata->firstchangedlogicor = presoldata->nusefullogicor;
755 assert(presoldata->firstchangedlogicor >= 0);
756
757 /* add new logicor constraints */
758 for( c = nlogicors - 1; c >= 0; --c )
759 {
761
763 {
764 /* check if constraint is new, and correct array size if necessary */
765 if( !SCIPhashtableExists(presoldata->logicorhashtable, (void*) logicors[c]) )
766 {
767 /* resize array if necessary */
768 if( presoldata->nusefullogicor == presoldata->susefullogicor )
769 {
770 int newsize;
771
772 newsize = SCIPcalcMemGrowSize(scip, presoldata->nusefullogicor + 1);
773
774 /* array already at maximal size */
775 if( newsize <= presoldata->susefullogicor )
776 return SCIP_NOMEMORY;
777
778 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(presoldata->usefullogicor), presoldata->susefullogicor, newsize) );
779 presoldata->susefullogicor = newsize;
780 }
781
782 /* insert new element in hashtable */
783 SCIP_CALL( SCIPhashtableInsert(presoldata->logicorhashtable, (void*) logicors[c]) );
785
786 presoldata->usefullogicor[presoldata->nusefullogicor] = logicors[c];
787 ++(presoldata->nusefullogicor);
788
789 /* update maximal entries in a logicor constraint */
790 if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, logicors[c]) )
791 presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, logicors[c]);
792 }
793 }
794 }
795
796 return SCIP_OKAY;
797}
798
799
800/** extract and-constraints and set-partitioning constraints */
801static
803 SCIP* scip, /**< SCIP data structure */
804 SCIP_PRESOLDATA* presoldata, /**< data object of presolver */
805 int pos, /**< position of logicor in usefullogicor array to presolve */
806 SCIP_HASHMAP* varmap, /**< variable map mapping inactive variables to their active representation */
807 SCIP_CONS** gateconss, /**< allocated memory for all gate-constraints */
808 SCIP_VAR** activevars, /**< allocated memory for active variables */
809 SCIP_VAR** posresultants, /**< allocated memory for all possible resultant variables */
810 HASHDATA* hashdata, /**< allocated memory for a hashdata object */
811 int* ndelconss, /**< pointer to store number of deleted constraints */
812 int* naddconss /**< pointer to store number of added constraints */
813 )
814{
818 SCIP_Bool negated;
819 int ngateconss;
820 int nlogicorvars;
821 int nposresultants;
822 int d;
823 int v;
824
825 assert(scip != NULL);
826 assert(presoldata != NULL);
827 assert(0 <= pos && pos < presoldata->nusefullogicor);
831 assert(hashdata != NULL);
832 assert(hashdata->vars != NULL);
833 assert(hashdata->nvars == 2);
834 assert(hashdata->cons == NULL);
835 assert(ndelconss != NULL);
836 assert(naddconss != NULL);
837
838 assert(presoldata->usefullogicor != NULL);
839 logicor = presoldata->usefullogicor[pos];
840 assert(logicor != NULL);
841
843 return SCIP_OKAY;
844
846
848 assert(nlogicorvars >= 3 && nlogicorvars <= presoldata->maxnvarslogicor);
849
852
853 nposresultants = 0;
854
855 /* get active logicor variables and determine all possible resultants */
856 for( d = nlogicorvars - 1; d >= 0; --d )
857 {
858 /* do not work with fixed variables */
860 return SCIP_OKAY;
861
863
864 if( activevars[d] == NULL )
865 {
868 }
869
870 /* determine possible resultants a check if the other variables can appear in a set-packing constraint */
872 {
874
876 {
879 }
881 return SCIP_OKAY;
882 }
883 else
884 {
886
888 {
891 }
893 return SCIP_OKAY;
894 }
895 }
896
897 if( nposresultants == 0 )
898 return SCIP_OKAY;
899
900 /* sort variables after indices */
902
903 /* check that we have really different variables, if not remove the constraint from the hashmap and the data
904 * storage
905 */
906 for( d = nlogicorvars - 1; d > 0; --d )
907 {
909 {
910 assert(presoldata->usefullogicor[pos] == logicor);
911
912 SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) logicor) );
914
915 presoldata->usefullogicor[pos] = presoldata->usefullogicor[presoldata->nusefullogicor - 1];
916 --(presoldata->nusefullogicor);
917
918 return SCIP_OKAY;
919 }
920 }
921
922 ngateconss = 0;
923
924 for( d = nposresultants - 1; d >= 0; --d )
925 {
926 ngateconss = 0;
927
928 for( v = nlogicorvars - 1; v >= 0; --v )
929 {
930 if( activevars[v] == posresultants[d] )
931 continue;
932
933 /* variables need to be sorted */
935 {
936 hashdata->vars[0] = activevars[v];
937 hashdata->vars[1] = posresultants[d];
938 }
939 else
940 {
941 hashdata->vars[0] = posresultants[d];
942 hashdata->vars[1] = activevars[v];
943 }
944
945 hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(presoldata->hashdatatable, (void*) hashdata);
946
948 {
950 ++ngateconss;
951 }
952 else
953 break;
954 }
955 if( ngateconss == nlogicorvars - 1 )
956 break;
957 }
958
959 /* @todo, check for clique of all variables except the resultant */
960 /* check if we have a set-partitioning 'gate' */
961 if( ngateconss == nlogicorvars - 1 && nlogicorvars == 3 )
962 {
963 assert(d >= 0 && d < nposresultants);
964 assert(ngateconss >= 2);
965
966 if( activevars[0] == posresultants[d] )
967 {
968 hashdata->vars[0] = activevars[1];
969 hashdata->vars[1] = activevars[2];
970 }
971 else if( activevars[1] == posresultants[d] )
972 {
973 hashdata->vars[0] = activevars[0];
974 hashdata->vars[1] = activevars[2];
975 }
976 else
977 {
979 hashdata->vars[0] = activevars[0];
980 hashdata->vars[1] = activevars[1];
981 }
982
983 hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(presoldata->hashdatatable, (void*) hashdata);
985
987 {
989 ++ngateconss;
990 }
991 }
992
993 /* did we find enough (>= number of variables in logicor - 1) set-packing constraints for an upgrade to either
994 * an and-constraint or even a set-partitioning constraint
995 */
996 if( ngateconss == nlogicorvars || (ngateconss >= nlogicorvars - 1 && !presoldata->onlysetpart))
997 {
999 char name[SCIP_MAXSTRLEN];
1000 SCIP_Bool initial;
1001 SCIP_Bool separate;
1002 SCIP_Bool enforce;
1003 SCIP_Bool check;
1004 SCIP_Bool propagate;
1005 SCIP_Bool local;
1006 SCIP_Bool modifiable;
1007 SCIP_Bool dynamic;
1008 SCIP_Bool removable;
1009 SCIP_Bool stickingatnode;
1010 int i;
1011
1013 assert(d >= 0 && d < nposresultants);
1014
1015 initial = SCIPconsIsInitial(logicor);
1016 separate = SCIPconsIsSeparated(logicor);
1017 enforce = SCIPconsIsEnforced(logicor);
1018 check = SCIPconsIsChecked(logicor);
1020 local = SCIPconsIsLocal(logicor);
1021 modifiable = SCIPconsIsModifiable(logicor);
1022 dynamic = SCIPconsIsDynamic(logicor);
1023 removable = SCIPconsIsRemovable(logicor);
1024 stickingatnode = SCIPconsIsStickingAtNode(logicor);
1025
1026#ifdef SCIP_DEBUG
1027 if( ngateconss == nlogicorvars )
1028 {
1029 SCIPdebugMsg(scip, "Following constraints form a set-partitioning constraint.\n");
1030 }
1031 else
1032 {
1033 SCIPdebugMsg(scip, "Following constraints form an and-constraint.\n");
1034 }
1035#endif
1036
1037 for( v = ngateconss - 1; v >= 0; --v )
1038 {
1039 assert(gateconss[v] != NULL);
1040
1041 initial |= SCIPconsIsInitial(gateconss[v]);
1042 separate |= SCIPconsIsSeparated(gateconss[v]);
1043 enforce |= SCIPconsIsEnforced(gateconss[v]);
1044 check |= SCIPconsIsChecked(gateconss[v]);
1046 local &= SCIPconsIsLocal(gateconss[v]);
1047 modifiable &= SCIPconsIsModifiable(gateconss[v]);
1048 dynamic &= SCIPconsIsDynamic(gateconss[v]);
1049 removable &= SCIPconsIsRemovable(gateconss[v]);
1050 stickingatnode &= SCIPconsIsStickingAtNode(gateconss[v]);
1051
1053
1055 ++(*ndelconss);
1056 }
1057
1059
1060 if( ngateconss == nlogicorvars - 1 )
1061 {
1062 SCIP_VAR** consvars;
1063
1064 assert(!presoldata->onlysetpart);
1065
1067 i = 0;
1068
1069 /* determine and operands */
1070 for( v = nlogicorvars - 1; v >= 0; --v )
1071 {
1072 if( activevars[v] == posresultants[d] )
1073 continue;
1074
1075 SCIP_CALL( SCIPgetNegatedVar(scip, activevars[v], &consvars[i]) );
1076 ++i;
1077 }
1078 assert(i == ngateconss);
1079
1080 /* create and add "and" constraint for the extracted gate */
1081 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "andgate_%d", presoldata->ngates);
1083 initial, separate, enforce, check, propagate,
1084 local, modifiable, dynamic, removable, stickingatnode) );
1085
1087 SCIPdebugMsg(scip, "-------------->\n");
1089
1090 ++(*naddconss);
1091 ++(presoldata->ngates);
1092
1094 ++(*ndelconss);
1095
1097
1098 SCIPfreeBufferArray(scip, &consvars);
1099 }
1100 else
1101 {
1103
1104 /* create and add set-partitioning constraint */
1105 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "setpart_%d", presoldata->ngates);
1107 initial, separate, enforce, check, propagate,
1108 local, modifiable, dynamic, removable, stickingatnode) );
1109
1111 SCIPdebugMsg(scip, "-------------->\n");
1113
1114 ++(*naddconss);
1115 ++(presoldata->ngates);
1116
1118 ++(*ndelconss);
1119
1121 }
1122 }
1123
1124 return SCIP_OKAY;
1125}
1126
1127
1128/*
1129 * Callback methods of presolver
1130 */
1131
1132
1133/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1134static
1136{ /*lint --e{715}*/
1137 assert(scip != NULL);
1138 assert(presol != NULL);
1140
1141 /* call inclusion method of presolver */
1143
1144 return SCIP_OKAY;
1145}
1146
1147
1148/** destructor of presolver to free user data (called when SCIP is exiting) */
1149static
1151{ /*lint --e{715}*/
1152 SCIP_PRESOLDATA* presoldata;
1153
1154 /* free presolver data */
1155 presoldata = SCIPpresolGetData(presol);
1156 assert(presoldata != NULL);
1157
1158 if( presoldata->hashdatatable != NULL )
1159 {
1160 assert(presoldata->setppchashtable != NULL);
1161 assert(presoldata->logicorhashtable != NULL);
1162
1163 SCIPhashtableFree(&(presoldata->logicorhashtable));
1164 SCIPhashtableFree(&(presoldata->setppchashtable));
1165 SCIPhashtableFree(&(presoldata->hashdatatable));
1166 }
1167
1168 SCIPfreeBlockMemory(scip, &presoldata);
1170
1171 return SCIP_OKAY;
1172}
1173
1174
1175/** deinitialization method of presolver (called before transformed problem is freed) */
1176static
1178{ /*lint --e{715}*/
1179 SCIP_PRESOLDATA* presoldata;
1180 int c;
1181
1182 /* free presolver data */
1183 presoldata = SCIPpresolGetData(presol);
1184 assert(presoldata != NULL);
1185
1186 /* release old constraints */
1187 for( c = presoldata->nusefullogicor - 1; c >= 0; --c )
1188 {
1189 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->usefullogicor[c])) );
1190 }
1191
1192 if( presoldata->usefullogicorexist )
1193 {
1194 SCIPfreeBlockMemoryArray(scip, &presoldata->usefullogicor, presoldata->susefullogicor);
1195 }
1196
1197 if( presoldata->usefulsetppcexist )
1198 {
1199 assert(presoldata->setppchashdatas != NULL || presoldata->nsetppchashdatas == 0);
1200 for( c = presoldata->nsetppchashdatas - 1; c >= 0; --c )
1201 {
1202 assert(presoldata->setppchashdatas[c].cons != NULL);
1203 assert(presoldata->setppchashdatas[c].vars != NULL);
1204
1205 /* remove constraint from setppc-hashtable */
1206 assert(SCIPhashtableExists(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons));
1207 SCIP_CALL( SCIPhashtableRemove(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons) );
1208
1209 /* remove hashdata entry from hashtable */
1210 SCIP_CALL( SCIPhashtableRemove(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]) );
1211
1212 /* release old constraints */
1213 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->setppchashdatas[c].cons)) );
1214
1215 /* release variables */
1216 SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[0])) );
1217 SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[1])) );
1218
1219 /* free memory for variables */
1220 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[c].vars), 2);
1221 }
1222
1223 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas), presoldata->ssetppchashdatas);
1224 }
1225
1226 if( presoldata->hashdatatable != NULL )
1227 {
1228 assert(presoldata->setppchashtable != NULL);
1229 assert(presoldata->logicorhashtable != NULL);
1230
1231 /* clear old hashtable entries */
1232 SCIPhashtableRemoveAll(presoldata->hashdatatable);
1233 SCIPhashtableRemoveAll(presoldata->setppchashtable);
1234 SCIPhashtableRemoveAll(presoldata->logicorhashtable);
1235 }
1236
1237 presoldata->nusefullogicor = 0;
1238 presoldata->susefullogicor = 0;
1239 presoldata->nsetppchashdatas = 0;
1240 presoldata->ssetppchashdatas = 0;
1241 presoldata->firstchangedlogicor = -1;
1242 presoldata->ngates = 0;
1243 presoldata->usefullogicorexist = FALSE;
1244 presoldata->usefulsetppcexist = FALSE;
1245 presoldata->newsetppchashdatas = FALSE;
1246 presoldata->initialized = FALSE;
1247
1248 return SCIP_OKAY;
1249}
1250
1251
1252/** presolving initialization method of presolver (called when presolving is about to begin) */
1253static
1255{ /*lint --e{715}*/
1256 return SCIP_OKAY;
1257}
1258
1259
1260/** presolving deinitialization method of presolver (called after presolving has been finished) */
1261static
1263{ /*lint --e{715}*/
1264 return SCIP_OKAY;
1265}
1266
1267
1268/** execution method of presolver */
1269static
1271{ /*lint --e{715}*/
1272 SCIP_PRESOLDATA* presoldata;
1273 SCIP_HASHMAP* varmap;
1275 SCIP_VAR* tmpvars[2];
1276 SCIP_CONSHDLR* conshdlrsetppc;
1281 int nsetppcconss;
1282 int nlogicorconss;
1283 int size;
1284 int c;
1285 SCIP_Bool paramvalue;
1286
1287 assert(scip != NULL);
1288 assert(presol != NULL);
1290 assert(result != NULL);
1291
1293
1294#if 0 /* need to include cons_knapsack on top of this file */
1295 /* check for possible knapsacks that form with a logicor a weak relaxation of an and-constraint
1296 *
1297 * the weak relaxation of an and-constraint looks like:
1298 * - row1: resvar - v1 - ... - vn >= 1-n
1299 * - row2: n*resvar - v1 - ... - vn <= 0.0
1300 *
1301 * which look like the following contraints
1302 * - logicor: resvar + ~v1 + ... + ~vn >= 1
1303 * - knapsack: n*resvar + ~v1 + ... + ~vn <= n
1304 */
1305 {
1308 int nknapsackconss;
1309 SCIP_VAR** vars;
1310 SCIP_Longint* vals;
1311 SCIP_Longint capacity;
1312 int nvars;
1313
1314 conshdlrknapsack = SCIPfindConshdlr(scip, "knapsack");
1315
1316 /* get number of active constraints */
1319 assert(nknapsackconss >= 0);
1321
1322 for( c = nknapsackconss - 1; c >= 0; --c )
1323 {
1324 /* not implemented in master branch, but the constraint may be already sorted */
1325 /*SCIPsortKnapsack(scip, knapsackconss[c]);*/
1326
1331
1332 if( nvars > 1 && capacity == nvars - 1 && vals[0] == capacity && vals[1] == 1 )
1333 {
1334 printf("possible knapsack for gate extraction\n");
1335 }
1336 }
1337 }
1338#endif
1339
1340 /* get necessary constraint handlers */
1341 conshdlrsetppc = SCIPfindConshdlr(scip, "setppc");
1343
1344 if( conshdlrsetppc == NULL || conshdlrlogicor == NULL )
1345 return SCIP_OKAY;
1346
1347 /* get number of active constraints */
1348 nsetppcconss = SCIPconshdlrGetNActiveConss(conshdlrsetppc);
1349 assert(nsetppcconss >= 0);
1351 assert(nlogicorconss >= 0);
1352
1353 if( nsetppcconss == 0 || nlogicorconss == 0 )
1354 return SCIP_OKAY;
1355
1356 /* get presolver data */
1357 presoldata = SCIPpresolGetData(presol);
1358 assert(presoldata != NULL);
1359
1361
1362 /* need and-constraint handler to extract and-gates */
1363 if( conshdlrand == NULL )
1364 {
1365 /* nothing to do when we cannot extract anything */
1366 if( !presoldata->searchequations )
1367 return SCIP_OKAY;
1368 else
1369 {
1370 /* make sure that we correct the parameter for only extrating set-partitioning constraints */
1371 if( SCIPisParamFixed(scip, "presolving/" PRESOL_NAME "/onlysetpart") )
1372 {
1373 SCIPwarningMessage(scip, "unfixing parameter <presolving/" PRESOL_NAME "/onlysetpart> in gate extration presolver\n");
1374 SCIP_CALL( SCIPunfixParam(scip, "presolving/" PRESOL_NAME "/onlysetpart") );
1375 }
1376 SCIP_CALL( SCIPsetBoolParam(scip, "presolving/" PRESOL_NAME "/onlysetpart", TRUE) );
1377 assert(presoldata->onlysetpart);
1378 }
1379 }
1380
1381 paramvalue = FALSE;
1382 if( conshdlrand != NULL && SCIPgetBoolParam(scip, "constraints/and/linearize", &paramvalue) == SCIP_OKAY )
1383 {
1384 if( paramvalue )
1385 {
1386 SCIPwarningMessage(scip, "Gate-presolving is the 'counterpart' of linearizing all and-constraints, so enabling both presolving steps simultaneously does not make sense.\n");
1387 }
1388 }
1390
1391 /* get active constraints */
1393
1397
1398 /* first we need to initialized the hashtables if not yet done */
1399 if( presoldata->hashdatatable == NULL )
1400 {
1401 SCIP_CALL( presoldataInitHashtables(scip, presoldata) );
1402 }
1403 assert(presoldata->hashdatatable != NULL);
1404 assert(presoldata->setppchashtable != NULL);
1405 assert(presoldata->logicorhashtable != NULL);
1406
1407 presoldata->newsetppchashdatas = FALSE;
1408
1409 if( !presoldata->initialized )
1410 {
1411 assert(presoldata->usefullogicor == NULL);
1412
1413 /* create useful set-packing information by adding new set-packing constraints with two variables */
1415 }
1416 else
1417 {
1418 /* refresh useful set-packing information, delete redundant constraints and add new constraints */
1420 }
1421 assert(presoldata->initialized);
1422
1423 if( presoldata->nusefullogicor == 0 )
1424 goto TERMINATE;
1425
1426 /* move the biggate extraction to front or back by sort the logicors after number of variables */
1427
1428 if( presoldata->sorting != 0 )
1429 {
1430 int* lengths;
1431
1432 SCIP_CALL( SCIPallocBufferArray(scip, &lengths, presoldata->nusefullogicor) );
1433
1434 for( c = presoldata->nusefullogicor - 1; c >= 0; --c )
1435 {
1436 lengths[c] = SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]);
1437 }
1438
1439 if( presoldata->sorting == -1 )
1440 SCIPsortDownIntPtr(lengths, (void**)presoldata->usefullogicor, presoldata->nusefullogicor);
1441 else
1442 SCIPsortIntPtr(lengths, (void**)presoldata->usefullogicor, presoldata->nusefullogicor);
1443
1445 }
1446
1447 /* maximal number of binary variables */
1449
1450 /* create the variable mapping hash map */
1451 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), size) );
1452
1453 /* search for set-partitioning constraints arising from a logicor and a set-packing constraints with equal variables */
1454 if( presoldata->searchequations && !SCIPisStopped(scip) )
1455 {
1457 HASHDATA** setppchashdatas;
1466 SCIP_Bool negated;
1467 int nsetppchashdatas;
1468 int nlogicorvars;
1469 int nsetppcvars;
1470 int d;
1471 int v;
1472
1473 assert(nsetppcconss > 0);
1474
1475 /* create local hashtable */
1477
1478 /* maximal number of binary variables */
1479 size = presoldata->maxnvarslogicor;
1480 assert(size >= 3);
1481
1482 /* get temporary memory */
1487
1488 hashdata.cons = NULL;
1489
1490 nsetppchashdatas = 0;
1491
1492 /* collect all set-packing/-partitioning constraints and corresponding data to be able to search faster */
1493 for( d = nsetppcconss - 1; d >= 0; --d )
1494 {
1495 setppc = setppcconss[d];
1496 assert(setppc != NULL);
1497
1499 continue;
1500
1501 /* @todo if of interest could also be implemented for set-covering constraints */
1502#if 1
1504 continue;
1505#endif
1506
1508
1509 if( nsetppcvars < 2 )
1510 continue;
1511
1513 continue;
1514
1515 /* to big setppc constraints are picked out */
1516 if( nsetppcvars > size )
1517 continue;
1518
1521
1522 /* get active setppc variables */
1523 for( v = nsetppcvars - 1; v >= 0; --v )
1524 {
1525 /* do not work with fixed variables */
1526 if( SCIPvarGetLbLocal(setppcvars[v]) > 0.5 || SCIPvarGetUbLocal(setppcvars[v]) < 0.5 )
1527 break;
1528
1530
1531 if( activevarssetppc[v] == NULL )
1532 {
1535 }
1536 }
1537
1538 /* if we found a fixed variable we want disregard this constraint */
1539 if( v >= 0 )
1540 continue;
1541
1542 /* variables need to be sorted after indices to be able to do a fast comparison */
1544
1545 setppchashdatas[nsetppchashdatas] = &(setppchashdatastore[nsetppchashdatas]);
1546
1547 /* memorize set-packing data */
1548 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(setppchashdatas[nsetppchashdatas]->vars), activevarssetppc, nsetppcvars) );
1549
1550 setppchashdatas[nsetppchashdatas]->nvars = nsetppcvars;
1551 setppchashdatas[nsetppchashdatas]->cons = setppc;
1552 /* need to capture this constraint, because it might get deleted during the process */
1554
1555 /* add entry to local hashtable */
1556 SCIP_CALL( SCIPhashtableInsert(setppchashdatatable, (void*) setppchashdatas[nsetppchashdatas]) );
1557 ++nsetppchashdatas;
1558 }
1559
1560 /* check all (new) logicors against all collected set-packing/-partitioning constraints */
1561 for( c = nlogicorconss - 1; c >= 0 && !SCIPisStopped(scip); --c )
1562 {
1564 assert(logicor != NULL);
1565
1567 continue;
1568
1570
1571 if( nlogicorvars < 2 )
1572 continue;
1573
1575 continue;
1576
1577 assert(nlogicorvars <= size);
1578
1581
1582 /* get active logicor variables */
1583 for( v = nlogicorvars - 1; v >= 0; --v )
1584 {
1585 /* do not work with fixed variables */
1586 if( SCIPvarGetLbLocal(logicorvars[v]) > 0.5 || SCIPvarGetUbLocal(logicorvars[v]) < 0.5 )
1587 break;
1588
1590
1591 /* if image does not exist, then there is no corresponding set-packing constraint */
1592 if( activevarslogicor[v] == NULL )
1593 break;
1594 }
1595
1596 if( v == -1 )
1597 {
1598 /* need sorting to be able to find the correct hashdata element */
1600
1601 hashdata.nvars = nlogicorvars;
1603
1606
1608 {
1609 SCIP_Bool initial;
1610 SCIP_Bool separate;
1611 SCIP_Bool enforce;
1612 SCIP_Bool check;
1613 SCIP_Bool propagate;
1614 SCIP_Bool local;
1615 SCIP_Bool modifiable;
1616 SCIP_Bool dynamic;
1617 SCIP_Bool removable;
1618 SCIP_Bool stickingatnode;
1619
1620 setppc = hashmaphashdata->cons;
1622
1633
1634 /* check if logicor is redundant against a set-partitioning constraint */
1636 {
1643 SCIP_CALL( SCIPsetConsModifiable(scip, setppc, modifiable) );
1645 SCIP_CALL( SCIPsetConsRemovable(scip, setppc, removable) );
1646 SCIP_CALL( SCIPsetConsStickingAtNode(scip, setppc, stickingatnode) );
1647
1648 SCIPdebugMsg(scip, "Following logicor is redundant to the set-partitioning constraint.\n");
1651 }
1652 else
1653 {
1655 char name[SCIP_MAXSTRLEN];
1656
1658
1659 SCIPdebugMsg(scip, "Following logicor and set-packing constraints form a set-partitioning constraint.\n");
1662
1663 /* create and add set-partitioning constraint */
1664 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "setpart_%d", presoldata->ngates);
1666 initial, separate, enforce, check, propagate,
1667 local, modifiable, dynamic, removable, stickingatnode) );
1668
1670 SCIPdebugMsg(scip, "-------------->\n");
1672
1673 ++(*naddconss);
1674 ++(presoldata->ngates);
1675
1676 /* delete redundant set-packing constraint */
1678 ++(*ndelconss);
1679
1681 }
1682
1683 /* delete redundant logicor constraint */
1685 ++(*ndelconss);
1686 }
1687 }
1688 }
1689
1690 /* need to clear/release parts of hashdata objects */
1691 for( d = nsetppchashdatas - 1; d >= 0; --d )
1692 {
1693 /* need to release captured constraint */
1694 SCIP_CALL( SCIPreleaseCons(scip, &(setppchashdatas[d]->cons)) );
1695 /* need to free copied memory */
1696 SCIPfreeBlockMemoryArray(scip, &(setppchashdatas[d]->vars), setppchashdatas[d]->nvars);
1697 }
1698
1699 /* delete local hashtable */
1701
1702 /* free all temporary memory */
1705 SCIPfreeBlockMemoryArray(scip, &setppchashdatas, nsetppcconss);
1707 }
1708
1709 /* we do not have any useful set-packing or logicor constraint, or since last run did not get any new constraints, so abort */
1710 if( presoldata->nsetppchashdatas == 0 || (presoldata->firstchangedlogicor == presoldata->nusefullogicor && !presoldata->newsetppchashdatas) )
1711 {
1712 SCIPhashmapFree(&varmap);
1713 goto TERMINATE;
1714 }
1715
1716 assert(presoldata->usefullogicor != NULL);
1717 assert(presoldata->nusefullogicor > 0);
1718 assert(presoldata->firstchangedlogicor >= 0);
1719 assert(presoldata->nsetppchashdatas > 0);
1720
1721 /* search for gates */
1722 if( presoldata->nsetppchashdatas > 0 && !SCIPisStopped(scip) )
1723 {
1727 int endloop;
1728
1729 /* if we found new setppcs we want to check all logicors again */
1730 if( presoldata->newsetppchashdatas )
1731 endloop = 0;
1732 else
1733 endloop = MAX(presoldata->firstchangedlogicor, 0);
1734
1735 assert(presoldata->maxnvarslogicor >= 3);
1736 SCIP_CALL( SCIPallocBufferArray(scip, &gateconss, presoldata->maxnvarslogicor) );
1737 SCIP_CALL( SCIPallocBufferArray(scip, &activevars, presoldata->maxnvarslogicor) );
1738 SCIP_CALL( SCIPallocBufferArray(scip, &posresultants, presoldata->maxnvarslogicor) );
1739
1740 hashdata.nvars = 2;
1741 hashdata.cons = NULL;
1742 /* assign array of two variables as temporary storage to hashdata */
1743 hashdata.vars = tmpvars;
1744
1745 /* check all (new) logicors against all set-packing constraints, to extract and-constraints with two or more
1746 * operands or set-partitioning constraints three or more variables
1747 */
1748 for( c = presoldata->nusefullogicor - 1; c >= endloop && !SCIPisStopped(scip); --c )
1749 {
1750 assert(presoldata->usefullogicor[c] != NULL);
1751
1752 /* logicor constraint has the form: x + y + z >= 1
1753 *
1754 * find set-packing constraints: (~x + ~y >= 1 and ~x + ~z >= 1) <=> (x + y <= 1 and x + z <= 1)
1755 *
1756 * - these three constraints are equivalent to: x = ~y * ~z (x = AND(~y,~z))
1757 *
1758 * if an additional set-packing constraint exists: y + z <= 1
1759 *
1760 * - these four constraints are equivalent to: x + y + z = 1
1761 */
1762 SCIP_CALL( extractGates(scip, presoldata, c, varmap, gateconss, activevars, posresultants, &hashdata, ndelconss, naddconss) );
1763 }
1764
1768 }
1769
1770 SCIPhashmapFree(&varmap);
1771
1772 TERMINATE:
1774
1775 /* remove old setppchashdatas objects */
1776 SCIP_CALL( cleanupHashDatas(scip, presoldata) );
1777
1778 return SCIP_OKAY;
1779}
1780
1781
1782/*
1783 * presolver specific interface methods
1784 */
1785
1786/** creates the gateextraction presolver and includes it in SCIP */
1788 SCIP* scip /**< SCIP data structure */
1789 )
1790{
1791 SCIP_PRESOLDATA* presoldata;
1793
1794 /* alloc presolve data object */
1795 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
1796
1797 /* initialize gateextraction presolver data */
1798 presoldataInit(presoldata);
1799
1800 /* include presolver */
1803
1809
1810 /* add gateextraction presolver parameters */
1812 "presolving/" PRESOL_NAME "/onlysetpart",
1813 "should we only try to extract set-partitioning constraints and no and-constraints",
1814 &presoldata->onlysetpart, TRUE, DEFAULT_ONLYSETPART, NULL, NULL) );
1815
1816 /* add gateextraction presolver parameters */
1818 "presolving/" PRESOL_NAME "/searchequations",
1819 "should we try to extract set-partitioning constraint out of one logicor and one corresponding set-packing constraint",
1820 &presoldata->searchequations, TRUE, DEFAULT_SEARCHEQUATIONS, NULL, NULL) );
1821
1822 /* add gateextraction presolver parameters */
1824 "presolving/" PRESOL_NAME "/sorting",
1825 "order logicor contraints to extract big-gates before smaller ones (-1), do not order them (0) or order them to extract smaller gates at first (1)",
1826 &presoldata->sorting, TRUE, DEFAULT_SORTING, -1, 1, NULL, NULL) );
1827
1828 return SCIP_OKAY;
1829}
SCIP_VAR * h
Constraint handler for AND constraints, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Constraint handler for the set partitioning / packing / covering constraints .
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#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
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition cons_and.c:5076
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
@ SCIP_SETPPCTYPE_PARTITIONING
Definition cons_setppc.h:87
@ SCIP_SETPPCTYPE_COVERING
Definition cons_setppc.h:89
@ SCIP_SETPPCTYPE_PACKING
Definition cons_setppc.h:88
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
Definition scip_prob.c:2127
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2843
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition misc.c:3156
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3074
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition misc.c:2346
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition misc.c:2659
#define SCIPhashFour(a, b, c, d)
Definition pub_misc.h:556
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition misc.c:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition misc.c:2608
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition misc.c:2755
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition misc.c:2677
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition misc.c:2547
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition scip_param.c:250
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition scip_param.c:219
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 SCIPunfixParam(SCIP *scip, const char *name)
Definition scip_param.c:385
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition scip_param.c:429
SCIP_RETCODE SCIPincludePresolGateextraction(SCIP *scip)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4670
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4593
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8473
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8234
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8383
SCIP_RETCODE SCIPsetConsStickingAtNode(SCIP *scip, SCIP_CONS *cons, SCIP_Bool stickingatnode)
Definition scip_cons.c:1500
SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate)
Definition scip_cons.c:1297
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8413
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition cons.c:8343
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition scip_cons.c:1450
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
Definition scip_cons.c:1272
SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce)
Definition scip_cons.c:1322
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8403
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition cons.c:8275
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition cons.c:8433
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition cons.c:8453
SCIP_RETCODE SCIPsetConsModifiable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool modifiable)
Definition scip_cons.c:1425
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition scip_cons.c:1475
SCIP_RETCODE SCIPsetConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_Bool local)
Definition scip_cons.c:1399
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition cons.c:8463
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition cons.c:8493
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
SCIP_RETCODE SCIPsetConsPropagated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool propagate)
Definition scip_cons.c:1372
SCIP_RETCODE SCIPsetConsChecked(SCIP *scip, SCIP_CONS *cons, SCIP_Bool check)
Definition scip_cons.c:1347
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8393
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1139
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8483
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition scip_mem.h:132
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:105
SCIP_RETCODE SCIPsetPresolExit(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPsetPresolExitpre(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition presol.c:522
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition presol.c:512
SCIP_RETCODE SCIPsetPresolInitpre(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition presol.c:599
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition var.c:17894
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:17748
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17538
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
int SCIPvarGetIndex(SCIP_VAR *var)
Definition var.c:17758
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1250
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition scip_var.c:1529
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition var.c:17574
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition var.c:11942
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition scip_var.c:1599
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3295
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1216
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownIntPtr(int *intarray, void **ptrarray, int len)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
return SCIP_OKAY
int c
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
static SCIP_Bool propagate
static SCIP_VAR ** vars
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
static SCIP_RETCODE cleanupHashDatas(SCIP *scip, SCIP_PRESOLDATA *presoldata)
#define PRESOL_NAME
#define DEFAULT_ONLYSETPART
static SCIP_RETCODE extractGates(SCIP *scip, SCIP_PRESOLDATA *presoldata, int pos, SCIP_HASHMAP *varmap, SCIP_CONS **gateconss, SCIP_VAR **activevars, SCIP_VAR **posresultants, HASHDATA *hashdata, int *ndelconss, int *naddconss)
#define HASHSIZE_SETPPCCONS
static SCIP_RETCODE presoldataInitHashtables(SCIP *scip, SCIP_PRESOLDATA *presoldata)
static SCIP_RETCODE createPresoldata(SCIP *scip, SCIP_PRESOLDATA *presoldata, SCIP_CONS **setppcs, int nsetppcs, SCIP_CONS **logicors, int nlogicors)
#define PRESOL_PRIORITY
#define HASHSIZE_LOGICORCONS
static void presoldataInit(SCIP_PRESOLDATA *presoldata)
static SCIP_RETCODE correctPresoldata(SCIP *scip, SCIP_PRESOLDATA *presoldata, SCIP_CONS **setppcs, int nsetppcs, SCIP_CONS **logicors, int nlogicors)
#define PRESOL_MAXROUNDS
#define DEFAULT_SORTING
#define PRESOL_TIMING
#define DEFAULT_SEARCHEQUATIONS
#define PRESOL_DESC
gateextraction presolver
public methods for managing constraints
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for presolvers
public methods for problem variables
public methods for constraint handler plugins and constraints
general public methods
public methods for memory management
public methods for message handling
public methods for SCIP parameter handling
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for SCIP variables
#define SCIP_DECL_HASHKEYEQ(x)
Definition type_misc.h:194
#define SCIP_DECL_HASHKEYVAL(x)
Definition type_misc.h:197
#define SCIP_DECL_PRESOLCOPY(x)
Definition type_presol.h:60
struct SCIP_PresolData SCIP_PRESOLDATA
Definition type_presol.h:51
#define SCIP_DECL_PRESOLFREE(x)
Definition type_presol.h:68
#define SCIP_DECL_PRESOLINITPRE(x)
Definition type_presol.h:98
#define SCIP_DECL_PRESOLEXITPRE(x)
#define SCIP_DECL_PRESOLEXIT(x)
Definition type_presol.h:84
#define SCIP_DECL_PRESOLEXEC(x)
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_NOMEMORY
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARSTATUS_FIXED
Definition type_var.h:52
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:54
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97