Scippy

SCIP

Solving Constraint Integer Programs

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
152SCIP_DECL_HASHKEYEQ(hashdataKeyEqCons)
153{
154#ifndef NDEBUG
155 SCIP* scip;
156#endif
157 HASHDATA* hashdata1;
158 HASHDATA* hashdata2;
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
196SCIP_DECL_HASHKEYVAL(hashdataKeyValCons)
197{ /*lint --e{715}*/
198 HASHDATA* hashdata;
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
215SCIP_DECL_HASHKEYEQ(setppcHashdataKeyEqCons)
216{
217#ifndef NDEBUG
218 SCIP* scip;
219#endif
220 HASHDATA* hashdata1;
221 HASHDATA* hashdata2;
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
260SCIP_DECL_HASHKEYVAL(setppcHashdataKeyValCons)
261{ /*lint --e{715}*/
262 HASHDATA* hashdata;
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,
327 SCIPhashGetKeyStandard, hashdataKeyEqCons, hashdataKeyValCons, (void*) scip) );
328 SCIP_CALL( SCIPhashtableCreate(&(presoldata->setppchashtable), SCIPblkmem(scip), HASHSIZE_SETPPCCONS,
329 SCIPhashGetKeyStandard, SCIPhashKeyEqPtr, SCIPhashKeyValPtr, (void*) scip) );
330 SCIP_CALL( SCIPhashtableCreate(&(presoldata->logicorhashtable), SCIPblkmem(scip), HASHSIZE_LOGICORCONS,
331 SCIPhashGetKeyStandard, SCIPhashKeyEqPtr, SCIPhashKeyValPtr, (void*) scip) );
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{
348 SCIP_CONS** usefulconss;
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 */
367 SCIP_CALL( SCIPallocBufferArray(scip, &usefulconss, size) );
368
369 if( !presoldata->usefulsetppcexist )
370 {
371 /* find set-packing constraints with exactly two variables */
372 for( c = 0; c < nsetppcs; ++c )
373 {
374 assert(SCIPconsIsActive(setppcs[c]));
375
376 if( SCIPgetTypeSetppc(scip, setppcs[c]) == SCIP_SETPPCTYPE_PACKING && SCIPgetNVarsSetppc(scip, setppcs[c]) == 2 && !SCIPconsIsModifiable(setppcs[c]) )
377 {
378 /* insert new element in hashtable */
379 SCIP_CALL( SCIPhashtableInsert(presoldata->setppchashtable, (void*) setppcs[c]) );
380
381 usefulconss[nusefulconss] = setppcs[c];
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 {
400 SCIP_VAR** setppcvars = SCIPgetVarsSetppc(scip, usefulconss[c]);
401 assert(SCIPconsIsActive(usefulconss[c]));
402 assert(SCIPgetNVarsSetppc(scip, usefulconss[c]) == 2);
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]) );
433 SCIP_CALL( SCIPcaptureCons(scip, usefulconss[c]) );
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 {
451 assert(SCIPconsIsActive(logicors[c]));
452
453 if( !SCIPconsIsModifiable(logicors[c]) && SCIPgetNVarsLogicor(scip, logicors[c]) >= 3 )
454 {
455 /* insert new element in hashtable */
456 SCIP_CALL( SCIPhashtableInsert(presoldata->logicorhashtable, (void*) logicors[c]) );
457 SCIP_CALL( SCIPcaptureCons(scip, logicors[c]) );
458
459 usefulconss[nusefulconss] = logicors[c];
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 */
480 SCIPfreeBufferArray(scip, &usefulconss);
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 {
511 removeentry = TRUE;
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 {
525 removeentry = TRUE;
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{
597 int oldnsetppchashdatas;
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
615 SCIP_CALL( createPresoldata(scip, presoldata, setppcs, nsetppcs, logicors, nlogicors) );
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 {
625 assert(SCIPconsIsActive(logicors[c]));
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 {
647 assert(SCIPconsIsActive(setppcs[c]));
648
649 if( SCIPgetTypeSetppc(scip, setppcs[c]) == SCIP_SETPPCTYPE_PACKING && SCIPgetNVarsSetppc(scip, setppcs[c]) == 2 && !SCIPconsIsModifiable(setppcs[c]) )
650 {
651 /* check if constraint is new, and correct array size if necessary */
652 if( !SCIPhashtableExists(presoldata->setppchashtable, (void*) setppcs[c]) )
653 {
654 SCIP_VAR** setppcvars;
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
685 assert(SCIPgetNVarsSetppc(scip, setppcs[c]) == 2);
686 setppcvars = SCIPgetVarsSetppc(scip, setppcs[c]);
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]) );
716 SCIP_CALL( SCIPcaptureCons(scip, setppcs[c]) );
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 {
760 assert(SCIPconsIsActive(logicors[c]));
761
762 if( !SCIPconsIsModifiable(logicors[c]) && SCIPgetNVarsLogicor(scip, logicors[c]) >= 3 )
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]) );
784 SCIP_CALL( SCIPcaptureCons(scip, 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{
815 SCIP_VAR** logicorvars;
816 HASHDATA* hashmaphashdata;
817 SCIP_CONS* logicor;
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);
828 assert(gateconss != NULL);
829 assert(activevars != NULL);
830 assert(posresultants != NULL);
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
842 if( !SCIPconsIsActive(logicor) )
843 return SCIP_OKAY;
844
845 assert(!SCIPconsIsModifiable(logicor));
846
847 nlogicorvars = SCIPgetNVarsLogicor(scip, logicor);
848 assert(nlogicorvars >= 3 && nlogicorvars <= presoldata->maxnvarslogicor);
849
850 logicorvars = SCIPgetVarsLogicor(scip, logicor);
851 assert(logicorvars != NULL);
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 */
859 if( SCIPvarGetLbLocal(logicorvars[d]) > 0.5 || SCIPvarGetUbLocal(logicorvars[d]) < 0.5 )
860 return SCIP_OKAY;
861
862 activevars[d] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, logicorvars[d]);
863
864 if( activevars[d] == NULL )
865 {
866 SCIP_CALL( SCIPgetBinvarRepresentative(scip, logicorvars[d], &(activevars[d]), &negated) );
867 SCIP_CALL( SCIPhashmapInsert(varmap, logicorvars[d], activevars[d]) );
868 }
869
870 /* determine possible resultants a check if the other variables can appear in a set-packing constraint */
871 if( SCIPvarIsNegated(activevars[d]) )
872 {
873 assert(SCIPvarIsActive(SCIPvarGetNegatedVar(activevars[d])));
874
875 if( SCIPvarGetNLocksDownType(SCIPvarGetNegatedVar(activevars[d]), SCIP_LOCKTYPE_MODEL) >= nlogicorvars - 1 )
876 {
877 posresultants[nposresultants] = activevars[d];
878 ++nposresultants;
879 }
881 return SCIP_OKAY;
882 }
883 else
884 {
885 assert(SCIPvarIsActive(activevars[d]));
886
887 if( SCIPvarGetNLocksUpType(activevars[d], SCIP_LOCKTYPE_MODEL) >= nlogicorvars - 1 )
888 {
889 posresultants[nposresultants] = activevars[d];
890 ++nposresultants;
891 }
892 else if( SCIPvarGetNLocksUpType(activevars[d], SCIP_LOCKTYPE_MODEL) == 0 )
893 return SCIP_OKAY;
894 }
895 }
896
897 if( nposresultants == 0 )
898 return SCIP_OKAY;
899
900 /* sort variables after indices */
901 SCIPsortPtr((void**)activevars, SCIPvarComp, nlogicorvars);
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 {
908 if( SCIPvarGetIndex(activevars[d]) == SCIPvarGetIndex(activevars[d - 1]) )
909 {
910 assert(presoldata->usefullogicor[pos] == logicor);
911
912 SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) logicor) );
913 SCIP_CALL( SCIPreleaseCons(scip, &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 */
934 if( SCIPvarCompare(posresultants[d], activevars[v]) > 0 )
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
947 if( hashmaphashdata != NULL && SCIPconsIsActive(hashmaphashdata->cons) )
948 {
949 gateconss[ngateconss] = hashmaphashdata->cons;
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 {
978 assert(activevars[2] == posresultants[d]);
979 hashdata->vars[0] = activevars[0];
980 hashdata->vars[1] = activevars[1];
981 }
982
983 hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(presoldata->hashdatatable, (void*) hashdata);
984 assert(hashmaphashdata == NULL || hashmaphashdata->cons != NULL);
985
986 if( hashmaphashdata != NULL && SCIPconsIsActive(hashmaphashdata->cons) )
987 {
988 gateconss[ngateconss] = hashmaphashdata->cons;
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 {
998 SCIP_CONS* newcons;
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
1012 assert(ngateconss <= nlogicorvars);
1013 assert(d >= 0 && d < nposresultants);
1014
1015 initial = SCIPconsIsInitial(logicor);
1016 separate = SCIPconsIsSeparated(logicor);
1017 enforce = SCIPconsIsEnforced(logicor);
1018 check = SCIPconsIsChecked(logicor);
1019 propagate = SCIPconsIsPropagated(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]);
1045 propagate |= SCIPconsIsPropagated(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
1052 SCIPdebugPrintCons(scip, gateconss[v], NULL);
1053
1054 SCIP_CALL( SCIPdelCons(scip, gateconss[v]) );
1055 ++(*ndelconss);
1056 }
1057
1058 SCIPdebugPrintCons(scip, logicor, NULL);
1059
1060 if( ngateconss == nlogicorvars - 1 )
1061 {
1062 SCIP_VAR** consvars;
1063
1064 assert(!presoldata->onlysetpart);
1065
1066 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, ngateconss) );
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);
1082 SCIP_CALL( SCIPcreateConsAnd(scip, &newcons, name, posresultants[d], ngateconss, consvars,
1083 initial, separate, enforce, check, propagate,
1084 local, modifiable, dynamic, removable, stickingatnode) );
1085
1086 SCIP_CALL( SCIPaddCons(scip, newcons) );
1087 SCIPdebugMsg(scip, "-------------->\n");
1088 SCIPdebugPrintCons(scip, newcons, NULL);
1089
1090 ++(*naddconss);
1091 ++(presoldata->ngates);
1092
1093 SCIP_CALL( SCIPdelCons(scip, logicor) );
1094 ++(*ndelconss);
1095
1096 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1097
1098 SCIPfreeBufferArray(scip, &consvars);
1099 }
1100 else
1101 {
1102 assert(ngateconss == nlogicorvars);
1103
1104 /* create and add set-partitioning constraint */
1105 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "setpart_%d", presoldata->ngates);
1106 SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, name, nlogicorvars, activevars,
1107 initial, separate, enforce, check, propagate,
1108 local, modifiable, dynamic, removable, stickingatnode) );
1109
1110 SCIP_CALL( SCIPaddCons(scip, newcons) );
1111 SCIPdebugMsg(scip, "-------------->\n");
1112 SCIPdebugPrintCons(scip, newcons, NULL);
1113
1114 ++(*naddconss);
1115 ++(presoldata->ngates);
1116
1117 SCIP_CALL( SCIPdelCons(scip, logicor) );
1118 ++(*ndelconss);
1119
1120 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
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
1135SCIP_DECL_PRESOLCOPY(presolCopyGateextraction)
1136{ /*lint --e{715}*/
1137 assert(scip != NULL);
1138 assert(presol != NULL);
1139 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
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
1150SCIP_DECL_PRESOLFREE(presolFreeGateextraction)
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);
1169 SCIPpresolSetData(presol, NULL);
1170
1171 return SCIP_OKAY;
1172}
1173
1174
1175/** deinitialization method of presolver (called before transformed problem is freed) */
1176static
1177SCIP_DECL_PRESOLEXIT(presolExitGateextraction)
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
1254SCIP_DECL_PRESOLINITPRE(presolInitpreGateextraction)
1255{ /*lint --e{715}*/
1256 return SCIP_OKAY;
1257}
1258
1259
1260/** presolving deinitialization method of presolver (called after presolving has been finished) */
1261static
1262SCIP_DECL_PRESOLEXITPRE(presolExitpreGateextraction)
1263{ /*lint --e{715}*/
1264 return SCIP_OKAY;
1265}
1266
1267
1268/** execution method of presolver */
1269static
1270SCIP_DECL_PRESOLEXEC(presolExecGateextraction)
1271{ /*lint --e{715}*/
1272 SCIP_PRESOLDATA* presoldata;
1273 SCIP_HASHMAP* varmap;
1274 HASHDATA hashdata;
1275 SCIP_VAR* tmpvars[2];
1276 SCIP_CONSHDLR* conshdlrsetppc;
1277 SCIP_CONSHDLR* conshdlrlogicor;
1278 SCIP_CONSHDLR* conshdlrand;
1279 SCIP_CONS** setppcconss;
1280 SCIP_CONS** logicorconss;
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);
1289 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1290 assert(result != NULL);
1291
1292 *result = SCIP_DIDNOTRUN;
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 {
1306 SCIP_CONSHDLR* conshdlrknapsack;
1307 SCIP_CONS** knapsackconss;
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 */
1317 knapsackconss = SCIPconshdlrGetConss(conshdlrknapsack);
1318 nknapsackconss = SCIPconshdlrGetNActiveConss(conshdlrknapsack);
1319 assert(nknapsackconss >= 0);
1320 assert(knapsackconss != NULL || 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
1327 nvars = SCIPgetNVarsKnapsack(scip, knapsackconss[c]);
1328 vals = SCIPgetWeightsKnapsack(scip, knapsackconss[c]);
1329 vars = SCIPgetVarsKnapsack(scip, knapsackconss[c]);
1330 capacity = SCIPgetCapacityKnapsack(scip, knapsackconss[c]);
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");
1342 conshdlrlogicor = SCIPfindConshdlr(scip, "logicor");
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);
1350 nlogicorconss = SCIPconshdlrGetNActiveConss(conshdlrlogicor);
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
1360 conshdlrand = SCIPfindConshdlr(scip, "and");
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 }
1389 *result = SCIP_DIDNOTFIND;
1390
1391 /* get active constraints */
1392 SCIP_CALL( SCIPduplicateBufferArray(scip, &setppcconss, SCIPconshdlrGetConss(conshdlrsetppc), nsetppcconss) ); /*lint !e666*/
1393
1394 assert(setppcconss != NULL);
1395 logicorconss = SCIPconshdlrGetConss(conshdlrlogicor);
1396 assert(logicorconss != NULL);
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 */
1414 SCIP_CALL( createPresoldata(scip, presoldata, setppcconss, nsetppcconss, logicorconss, nlogicorconss) );
1415 }
1416 else
1417 {
1418 /* refresh useful set-packing information, delete redundant constraints and add new constraints */
1419 SCIP_CALL( correctPresoldata(scip, presoldata, setppcconss, nsetppcconss, logicorconss, nlogicorconss) );
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
1444 SCIPfreeBufferArray(scip, &lengths);
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 {
1456 SCIP_HASHTABLE* setppchashdatatable;
1457 HASHDATA** setppchashdatas;
1458 HASHDATA* setppchashdatastore;
1459 HASHDATA* hashmaphashdata;
1460 SCIP_CONS* logicor;
1461 SCIP_CONS* setppc;
1462 SCIP_VAR** logicorvars;
1463 SCIP_VAR** setppcvars;
1464 SCIP_VAR** activevarslogicor;
1465 SCIP_VAR** activevarssetppc;
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 */
1476 SCIP_CALL( SCIPhashtableCreate(&setppchashdatatable, SCIPblkmem(scip), nsetppcconss, SCIPhashGetKeyStandard, setppcHashdataKeyEqCons, setppcHashdataKeyValCons, (void*) scip) );
1477
1478 /* maximal number of binary variables */
1479 size = presoldata->maxnvarslogicor;
1480 assert(size >= 3);
1481
1482 /* get temporary memory */
1483 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &setppchashdatastore, nsetppcconss) );
1484 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &setppchashdatas, nsetppcconss) );
1485 SCIP_CALL( SCIPallocBufferArray(scip, &activevarssetppc, size) );
1486 SCIP_CALL( SCIPallocBufferArray(scip, &activevarslogicor, size) );
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
1498 if( SCIPconsIsDeleted(setppc) )
1499 continue;
1500
1501 /* @todo if of interest could also be implemented for set-covering constraints */
1502#if 1
1504 continue;
1505#endif
1506
1507 nsetppcvars = SCIPgetNVarsSetppc(scip, setppc);
1508
1509 if( nsetppcvars < 2 )
1510 continue;
1511
1512 if( SCIPconsIsModifiable(setppc) )
1513 continue;
1514
1515 /* to big setppc constraints are picked out */
1516 if( nsetppcvars > size )
1517 continue;
1518
1519 setppcvars = SCIPgetVarsSetppc(scip, setppc);
1520 assert(setppcvars != NULL);
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
1529 activevarssetppc[v] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, setppcvars[v]);
1530
1531 if( activevarssetppc[v] == NULL )
1532 {
1533 SCIP_CALL( SCIPgetBinvarRepresentative(scip, setppcvars[v], &(activevarssetppc[v]), &negated) );
1534 SCIP_CALL( SCIPhashmapInsert(varmap, setppcvars[v], activevarssetppc[v]) );
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 */
1543 SCIPsortPtr((void**)activevarssetppc, SCIPvarComp, nsetppcvars);
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 */
1553 SCIP_CALL( SCIPcaptureCons(scip, setppc) );
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 {
1563 logicor = logicorconss[c];
1564 assert(logicor != NULL);
1565
1566 if( SCIPconsIsDeleted(logicor) )
1567 continue;
1568
1569 nlogicorvars = SCIPgetNVarsLogicor(scip, logicor);
1570
1571 if( nlogicorvars < 2 )
1572 continue;
1573
1574 if( SCIPconsIsModifiable(logicor) )
1575 continue;
1576
1577 assert(nlogicorvars <= size);
1578
1579 logicorvars = SCIPgetVarsLogicor(scip, logicor);
1580 assert(logicorvars != NULL);
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
1589 activevarslogicor[v] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, logicorvars[v]);
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 */
1599 SCIPsortPtr((void**)activevarslogicor, SCIPvarComp, nlogicorvars);
1600
1601 hashdata.nvars = nlogicorvars;
1602 hashdata.vars = activevarslogicor;
1603
1604 hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(setppchashdatatable, (void*) &hashdata);
1605 assert(hashmaphashdata == NULL || hashmaphashdata->cons != NULL);
1606
1607 if( hashmaphashdata != NULL && !SCIPconsIsDeleted(hashmaphashdata->cons) )
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;
1621 assert(SCIPconsGetHdlr(setppc) == SCIPfindConshdlr(scip, "setppc"));
1622
1623 initial = SCIPconsIsInitial(logicor) || SCIPconsIsInitial(setppc);
1624 separate = SCIPconsIsSeparated(logicor) || SCIPconsIsSeparated(setppc);
1625 enforce = SCIPconsIsEnforced(logicor) || SCIPconsIsEnforced(setppc);
1626 check = SCIPconsIsChecked(logicor) || SCIPconsIsChecked(setppc);
1627 propagate = SCIPconsIsPropagated(logicor) || SCIPconsIsPropagated(setppc);
1628 local = SCIPconsIsLocal(logicor) && SCIPconsIsLocal(setppc);
1629 modifiable = SCIPconsIsModifiable(logicor) && SCIPconsIsModifiable(setppc);
1630 dynamic = SCIPconsIsDynamic(logicor) && SCIPconsIsDynamic(setppc);
1631 removable = SCIPconsIsRemovable(logicor) && SCIPconsIsRemovable(setppc);
1632 stickingatnode = SCIPconsIsStickingAtNode(logicor) && SCIPconsIsStickingAtNode(setppc);
1633
1634 /* check if logicor is redundant against a set-partitioning constraint */
1636 {
1637 SCIP_CALL( SCIPsetConsInitial(scip, setppc, initial) );
1638 SCIP_CALL( SCIPsetConsSeparated(scip, setppc, separate) );
1639 SCIP_CALL( SCIPsetConsEnforced(scip, setppc, enforce) );
1640 SCIP_CALL( SCIPsetConsChecked(scip, setppc, check) );
1641 SCIP_CALL( SCIPsetConsPropagated(scip, setppc, propagate) );
1642 SCIP_CALL( SCIPsetConsLocal(scip, setppc, local) );
1643 SCIP_CALL( SCIPsetConsModifiable(scip, setppc, modifiable) );
1644 SCIP_CALL( SCIPsetConsDynamic(scip, setppc, dynamic) );
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");
1649 SCIPdebugPrintCons(scip, logicor, NULL);
1650 SCIPdebugPrintCons(scip, setppc, NULL);
1651 }
1652 else
1653 {
1654 SCIP_CONS* newcons;
1655 char name[SCIP_MAXSTRLEN];
1656
1658
1659 SCIPdebugMsg(scip, "Following logicor and set-packing constraints form a set-partitioning constraint.\n");
1660 SCIPdebugPrintCons(scip, logicor, NULL);
1661 SCIPdebugPrintCons(scip, setppc, NULL);
1662
1663 /* create and add set-partitioning constraint */
1664 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "setpart_%d", presoldata->ngates);
1665 SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, name, nlogicorvars, activevarslogicor,
1666 initial, separate, enforce, check, propagate,
1667 local, modifiable, dynamic, removable, stickingatnode) );
1668
1669 SCIP_CALL( SCIPaddCons(scip, newcons) );
1670 SCIPdebugMsg(scip, "-------------->\n");
1671 SCIPdebugPrintCons(scip, newcons, NULL);
1672
1673 ++(*naddconss);
1674 ++(presoldata->ngates);
1675
1676 /* delete redundant set-packing constraint */
1677 SCIP_CALL( SCIPdelCons(scip, setppc) );
1678 ++(*ndelconss);
1679
1680 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1681 }
1682
1683 /* delete redundant logicor constraint */
1684 SCIP_CALL( SCIPdelCons(scip, logicor) );
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 */
1700 SCIPhashtableFree(&setppchashdatatable);
1701
1702 /* free all temporary memory */
1703 SCIPfreeBufferArray(scip, &activevarslogicor);
1704 SCIPfreeBufferArray(scip, &activevarssetppc);
1705 SCIPfreeBlockMemoryArray(scip, &setppchashdatas, nsetppcconss);
1706 SCIPfreeBlockMemoryArray(scip, &setppchashdatastore, 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 {
1724 SCIP_CONS** gateconss;
1725 SCIP_VAR** activevars;
1726 SCIP_VAR** posresultants;
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
1765 SCIPfreeBufferArray(scip, &posresultants);
1766 SCIPfreeBufferArray(scip, &activevars);
1767 SCIPfreeBufferArray(scip, &gateconss);
1768 }
1769
1770 SCIPhashmapFree(&varmap);
1771
1772 TERMINATE:
1773 SCIPfreeBufferArray(scip, &setppcconss);
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;
1792 SCIP_PRESOL* presol;
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 */
1802 PRESOL_TIMING, presolExecGateextraction, presoldata) );
1803
1804 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyGateextraction) );
1805 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeGateextraction) );
1806 SCIP_CALL( SCIPsetPresolExit(scip, presol, presolExitGateextraction) );
1807 SCIP_CALL( SCIPsetPresolInitpre(scip, presol, presolInitpreGateextraction) );
1808 SCIP_CALL( SCIPsetPresolExitpre(scip, presol, presolExitpreGateextraction) );
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
Definition: circlepacking.c:68
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 SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#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:5070
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9545
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9568
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9591
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)
Definition: cons_setppc.c:9351
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)
Definition: scip_general.c:724
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
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:522
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:512
SCIP_RETCODE SCIPsetPresolExitpre(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXITPRE((*presolexitpre)))
Definition: scip_presol.c:220
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:156
SCIP_RETCODE SCIPsetPresolExit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXIT((*presolexit)))
Definition: scip_presol.c:188
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
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)
Definition: scip_presol.c:105
SCIP_RETCODE SCIPsetPresolInitpre(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINITPRE((*presolinitpre)))
Definition: scip_presol.c:204
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:1248
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
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:1597
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
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
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)
static SCIP_DECL_PRESOLCOPY(presolCopyGateextraction)
static SCIP_DECL_HASHKEYEQ(hashdataKeyEqCons)
#define HASHSIZE_SETPPCCONS
static SCIP_DECL_HASHKEYVAL(hashdataKeyValCons)
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)
static SCIP_DECL_PRESOLFREE(presolFreeGateextraction)
#define PRESOL_PRIORITY
#define HASHSIZE_LOGICORCONS
static SCIP_DECL_PRESOLEXIT(presolExitGateextraction)
static SCIP_DECL_PRESOLINITPRE(presolInitpreGateextraction)
static SCIP_DECL_PRESOLEXITPRE(presolExitpreGateextraction)
static SCIP_DECL_PRESOLEXEC(presolExecGateextraction)
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)
Definition: pub_message.h:102
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
SCIP_VAR ** vars
SCIP_CONS * cons
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:51
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_NOMEMORY
Definition: type_retcode.h:44
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARSTATUS_FIXED
Definition: type_var.h:52
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97