Scippy

SCIP

Solving Constraint Integer Programs

cons_pseudoboolean.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 cons_pseudoboolean.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief constraint handler for pseudo Boolean constraints
28 * @author Gerald Gamrath
29 * @author Stefan Heinz
30 * @author Michael Winkler
31 * @author Dominik Kamp
32 *
33 * The constraint handler deals with pseudo Boolean constraints. These are constraints of the form
34 * \f[
35 * \mbox{lhs} \leq \sum_{k=0}^m c_k \cdot x_k + \sum_{i=0}^n c_i \cdot \prod_{j \in I_i} x_j \leq \mbox{rhs}
36 * \f]
37 * where all x are binary and all c are integer
38 *
39 * @todo Add eventhandling.
40 */
41
42/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43
45#include "scip/cons_and.h"
46#include "scip/cons_indicator.h"
47#include "scip/cons_knapsack.h"
48#include "scip/cons_linear.h"
49#include "scip/cons_logicor.h"
51#include "scip/cons_setppc.h"
52#include "scip/cons_xor.h"
53#include "scip/debug.h"
54#include "scip/pub_cons.h"
55#include "scip/pub_message.h"
56#include "scip/pub_misc.h"
57#include "scip/pub_misc_sort.h"
58#include "scip/pub_var.h"
59#include "scip/scip_cons.h"
60#include "scip/scip_copy.h"
61#include "scip/scip_general.h"
62#include "scip/scip_mem.h"
63#include "scip/scip_message.h"
64#include "scip/scip_numerics.h"
65#include "scip/scip_param.h"
66#include "scip/scip_prob.h"
67#include "scip/scip_sol.h"
68#include "scip/scip_var.h"
69#include "scip/symmetry_graph.h"
70#include <string.h>
71
72#ifdef WITHEQKNAPSACK
73#include "scip/cons_eqknapsack.h"
74#endif
75
76/* constraint handler properties */
77#define CONSHDLR_NAME "pseudoboolean"
78#define CONSHDLR_DESC "constraint handler dealing with pseudo Boolean constraints"
79#define CONSHDLR_ENFOPRIORITY -1000000 /**< priority of the constraint handler for constraint enforcing */
80#define CONSHDLR_CHECKPRIORITY -5000000 /**< priority of the constraint handler for checking feasibility */
81#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
82 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
83#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
84#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
85
86#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
87
88#define DEFAULT_DECOMPOSENORMALPBCONS FALSE /**< decompose all normal pseudo boolean constraint into a "linear" constraint and "and" constraints */
89#define DEFAULT_DECOMPOSEINDICATORPBCONS TRUE /**< decompose all indicator pseudo boolean constraint into a "linear" constraint and "and" constraints */
90
91#define DEFAULT_SEPARATENONLINEAR TRUE /**< if decomposed, should the nonlinear constraints be separated during LP processing */
92#define DEFAULT_PROPAGATENONLINEAR TRUE /**< if decomposed, should the nonlinear constraints be propagated during node processing */
93#define DEFAULT_REMOVABLENONLINEAR TRUE /**< if decomposed, should the nonlinear constraints be removable */
94#define USEINDICATOR TRUE
95#define NONLINCONSUPGD_PRIORITY 60000 /**< priority of upgrading nonlinear constraints */
96
97/* remove this line to compile the upgrade from nonlinear to pseudoboolean constraints */
98#undef NONLINCONSUPGD_PRIORITY /*lint !e750*/
99
100/*
101 * Data structures
102 */
103#define HASHSIZE_PSEUDOBOOLEANNONLINEARTERMS 500 /**< minimal size of hash table in and constraint tables */
104
105
106/* - create special linear(knapsack, setppc, logicor, (eqknapsack)) and and-constraints with check flags FALSE, to
107 * get smaller amount of locks on the term variables, do all presolving ...?! in these constraint handlers
108 *
109 * - do the checking here, lock and-resultants in both directions and all and-variables according to their
110 * coefficients and sides of the constraint,
111 * @note this only works if the and-resultant has no objective cofficient, otherwise we need to lock variables also in both directions
112 *
113 * - need to keep and constraint pointer for special propagations like if two ands are due to their variables in
114 * one clique, add this cliques of and-resultants
115 *
116 * - do special presolving like on instance :
117 * check/IP/PseudoBoolean/normalized-PB07/OPT-SMALLINT-NLC/submittedPB07/manquinho/bsg/normalized-bsg_1000_25_1.opb.gz
118 *
119 * there exist constraint like: 1 x1 x2 + 1 x1 x3 + 1 x1 x4 + 1 x1 x5 <= 1 ;
120 * which "equals" a linear constraint: 3 x1 + x2 + x3 + x4 + x5 <= 4 ;
121 *
122 * in more general terms: 1 x1 x2 x3 x4 + 1 x1 x2 x5 x6 x7 + 1 x1 x2 x8 x9 <= 1 ;
123 * which "equals" a pseudoboolean constraint: 2 x1 + 2 x2 + 1 x3 x4 + 1 x5 x6 x7 + 1 x8 x9 <= 5 ;
124 *
125 * in an even more general terms: 5 x1 x2 x3 x4 + 1 x1 x2 x5 x6 x7 + 1 x1 x2 x8 x9 <= 6 ;
126 * equals(should the knapsack do) 1 x1 x2 x3 x4 + 1 x1 x2 x5 x6 x7 + 1 x1 x2 x8 x9 <= 2 ;
127 * which "equals" a pseudoboolean constraint: 2 x1 + 2 x2 + 1 x3 x4 + 1 x5 x6 x7 + 1 x8 x9 <= 6 ;
128 * ( without knapsack 7 x1 + 7 x2 + 5 x3 x4 + 1 x5 x6 x7 + 1 x8 x9 <= 20 ; )
129 *
130 * another special case : 1 x1 x2 x3 + 1 x1 x2 x4 + 1 x5 x6 <= 1 ;
131 * which "equals" a pseudoboolean constraint: 2 x1 + 2 x2 + 1 x3 + 1 x4 + 1 x5 x6 <= 5 ;
132 * which "equals" a pseudoboolean constraint: 4 x1 + 4 x2 + 2 x3 + 2 x4 + 1 x5 + 1 x6 <= 10 ;
133 *
134 * another special case : 1 x1 x2 + 1 x1 x3 + 2 x4 x5 <= 3 ;
135 * which "equals" a pseudoboolean constraint: 2 x1 + 1 x2 + 1 x3 + 2 x4 x5 <= 5 ;
136 * which "equals" a pseudoboolean constraint: 2 x1 + 1 x2 + 1 x3 + 1 x4 + 1 x5 <= 5 ;
137 */
138/* @todo - in and-constraint better count nfixed zeros in both directions and maybe nfixedones for better propagation
139 *
140 * - do better conflict analysis by choosing the earliest fixed variable which led to a conflict instead of maybe
141 * best coefficient or create more conflicts by using all to zero fixed variables one by one
142 *
143 * - how to make sure that we aggregate in a right way, when aggregating a resultant and a "normal" variable,
144 * maybe add in SCIPaggregateVars a check for original variables, to prefer them if the variable type is the
145 * same; probably it would be better too if we would aggregate two resultants that the one with less variables
146 * inside the and-constraint will stay active
147 *
148 * @note since product resultants are artificial, we do not care for their solution value, but this can lead to fixation
149 * of the resultant not representing the product, in 'optimization mode' we do not care, but this might make
150 * solution debugging complicated
151 */
152
153/** and-constraint data object */
155{
156 SCIP_CONS* cons; /**< pointer to the and-constraint of this 'term' of variables */
157 SCIP_CONS* origcons; /**< pointer to the original and-constraint of this 'term' of variables
158 * only after problem was transformed, NULL otherwise */
159 SCIP_VAR** vars; /**< all and-constraint variables */
160 int nvars; /**< number of all and-constraint variables */
161 int svars; /**< size for all and-constraint variables */
162 SCIP_VAR** newvars; /**< new variables in this presolving round */
163 int nnewvars; /**< number of new variables in this presolving round */
164 int snewvars; /**< size of new variables in this presolving round */
165 int noriguses; /**< how often is this data in used by original constraints */
166 int nuses; /**< how often is this data in used by transformed constraints */
167 unsigned int istransformed:1; /**< is transformed data active */
168 unsigned int isoriginal:1; /**< is original data active */
169};
171
172/** constraint data for pseudoboolean constraints */
173struct SCIP_ConsData
174{
175 SCIP_Real lhs; /**< left hand side of constraint */
176 SCIP_Real rhs; /**< right hand side of constraint */
177
178 SCIP_CONS* lincons; /**< linear constraint which represents this pseudoboolean constraint */
179 SCIP_LINEARCONSTYPE linconstype; /**< type of linear constraint which represents this pseudoboolean constraint */
180 int nlinvars; /**< number of linear variables (without and-resultants) */
181
182 CONSANDDATA** consanddatas; /**< array of and-constraints-data-objects sorted after problem index of
183 * and-resultant of corresponding and-constraint */
184 SCIP_Real* andcoefs; /**< array of coefficients for and-constraints of
185 * and-constraints-data-objects
186 * (changes during presolving, needs to be updated in every presolving
187 * round) */
188 SCIP_Bool* andnegs; /**< array of negation status for and-constraints of
189 * and-constraints-data-objects
190 * (changes during presolving, needs to be updated in every presolving
191 * round) */
192 int nconsanddatas; /**< number of and-constraints-data-objects */
193 int sconsanddatas; /**< size of and-constraints-data-objects array */
194
195 SCIP_VAR* intvar; /**< a artificial variable which was added only for the objective function,
196 * if this variable is not NULL this constraint (without this integer
197 * variable) describes the objective function */
198
199 SCIP_VAR* indvar; /**< indicator variable if it's a soft constraint, or NULL */
200 SCIP_Real weight; /**< weight of the soft constraint, if it is one */
201
202 unsigned int issoftcons:1; /**< is this a soft constraint */
203 unsigned int changed:1; /**< was constraint changed? */
204 unsigned int propagated:1; /**< is constraint already propagated? */
205 unsigned int presolved:1; /**< is constraint already presolved? */
206 unsigned int cliquesadded:1; /**< were the cliques of the constraint already extracted? */
207 unsigned int upgradetried:1; /**< was constraint upgrading already tried */
208};
209
210/** constraint handler data */
211struct SCIP_ConshdlrData
212{
213 CONSANDDATA** allconsanddatas; /**< array of all and-constraint data objects inside the whole problem,
214 * created via this constraint handler */
215 int nallconsanddatas; /**< number of all and-constraint data objects inside the whole problem,
216 * created via this constraint handler */
217 int sallconsanddatas; /**< size of all and-constraint data objects inside the whole problem,
218 * created via this constraint handler */
219 SCIP_HASHTABLE* hashtable; /**< hash table for all and-constraint data objects */
220 int hashtablesize; /**< size for hash table for all and-constraint data objects */
221
222 SCIP_HASHMAP* hashmap; /**< hash map for mapping all resultant to and-constraint */
223 int hashmapsize; /**< size for hash map for mapping all resultant to and-constraint */
224
225 SCIP_Bool decomposenormalpbcons;/**< decompose the pseudo boolean constraint into a "linear" constraint and "and" constraints */
226 SCIP_Bool decomposeindicatorpbcons;/**< decompose the indicator pseudo boolean constraint into a "linear" constraint and "and" constraints */
227 SCIP_Bool inithashmapandtable;/**< flag to store if the hashmap and -table is initialized */
228 int nlinconss; /**< for counting number of created linear constraints */
229 int noriguses; /**< how many consanddata objects are used by original constraints */
230};
231
232
233/*
234 * Local methods
235 */
236
237/** comparison method for sorting and-resultants according to their problem index, which is used instead of the
238 * original index because the implicit resultants are shuffled when creating the constraints that otherwise results in
239 * shuffled problem copies,
240 * if an and-resultant is deleted, it will be put in front with respect to its original index while sorting
241 */
242static
244{
245 int varind1 = SCIPvarGetProbindex((SCIP_VAR*)elem1);
246 int varind2 = SCIPvarGetProbindex((SCIP_VAR*)elem2);
247
248 if( varind1 < varind2 )
249 return -1;
250 else if( varind1 > varind2 )
251 return +1;
252 else if( varind1 != -1 )
253 {
254 assert(elem1 == elem2);
255 return 0;
256 }
257
258 return SCIPvarComp(elem1, elem2);
259}
260
261/** comparison method for sorting consanddatas according to the problem index of their corresponding and-resultants,
262 * if a consanddata object is deleted, it is handled like it has an inactive resultant, so this will be put
263 * in front while sorting
264 */
265static
266SCIP_DECL_SORTPTRCOMP(resvarCompWithInactive)
267{
268 CONSANDDATA* consanddata1 = (CONSANDDATA*)elem1;
269 CONSANDDATA* consanddata2 = (CONSANDDATA*)elem2;
270
271 assert(consanddata1 != NULL);
272 assert(consanddata2 != NULL);
273
274 /* consider that constraint data object can be only original */
275 if( consanddata1->istransformed != consanddata2->istransformed )
276 return consanddata1->istransformed ? +1 : -1;
277
278 SCIP_CONS* consand1;
279 SCIP_CONS* consand2;
280
281 if( consanddata1->istransformed )
282 {
283 consand1 = consanddata1->cons;
284 consand2 = consanddata2->cons;
285 }
286 else
287 {
288 consand1 = consanddata1->origcons;
289 consand2 = consanddata2->origcons;
290 }
291
292 /* check if and-constraint is still active */
293 if( SCIPconsIsDeleted(consand1) )
294 {
295 if( SCIPconsIsDeleted(consand2) )
296 return 0;
297 else
298 return -1;
299 }
300 else if( SCIPconsIsDeleted(consand2) )
301 return +1;
302
303 /* hack with setting the scip pointer to NULL */
304 return resvarComp((void*)SCIPgetResultantAnd(NULL, consand1), (void*)SCIPgetResultantAnd(NULL, consand2));
305}
306
307/** gets the key of the given element */
308static
309SCIP_DECL_HASHGETKEY(hashGetKeyAndConsDatas)
310{ /*lint --e{715}*/
311 /* the key is the element itself */
312 return elem;
313}
314
315/** returns TRUE iff both keys are equal; two non-linear terms are equal if they have the same variables */
316static
317SCIP_DECL_HASHKEYEQ(hashKeyEqAndConsDatas)
318{
319#ifndef NDEBUG
320 SCIP* scip;
321#endif
322 CONSANDDATA* cdata1;
323 CONSANDDATA* cdata2;
324 int v;
325
326 cdata1 = (CONSANDDATA*)key1;
327 cdata2 = (CONSANDDATA*)key2;
328
329#ifndef NDEBUG
330 scip = (SCIP*)userptr;
331#endif
332 assert(scip != NULL);
333 assert(cdata1 != NULL);
334 assert(cdata2 != NULL);
335 assert(cdata1->vars != NULL);
336 assert(cdata1->nvars > 1);
337 assert(cdata2->vars != NULL);
338 assert(cdata2->nvars > 1);
339
340#ifndef NDEBUG
341 /* check that cdata1 variables are sorted */
342 for( v = cdata1->nvars - 1; v > 0; --v )
343 assert(SCIPvarGetIndex(cdata1->vars[v]) >= SCIPvarGetIndex(cdata1->vars[v - 1]));
344 /* check that cdata2 variables are sorted */
345 for( v = cdata2->nvars - 1; v > 0; --v )
346 assert(SCIPvarGetIndex(cdata2->vars[v]) >= SCIPvarGetIndex(cdata2->vars[v - 1]));
347#endif
348
349 /* checks trivial case */
350 if( cdata1->nvars != cdata2->nvars )
351 return FALSE;
352
353 /* checks trivial case */
354 if( cdata1->cons != NULL && cdata2->cons != NULL && cdata1->cons != cdata2->cons )
355 return FALSE;
356
357 /* check each variable in both cdatas for equality */
358 for( v = cdata1->nvars - 1; v >= 0; --v )
359 {
360 assert(cdata1->vars[v] != NULL);
361 assert(cdata2->vars[v] != NULL);
362
363 /* tests if variables are equal */
364 if( cdata1->vars[v] != cdata2->vars[v] )
365 {
366 assert(SCIPvarCompare(cdata1->vars[v], cdata2->vars[v]) == 1 ||
367 SCIPvarCompare(cdata1->vars[v], cdata2->vars[v]) == -1);
368 return FALSE;
369 }
370 assert(SCIPvarCompare(cdata1->vars[v], cdata2->vars[v]) == 0);
371 }
372
373 return TRUE;
374}
375
376/** returns the hash value of the key */
377static
378SCIP_DECL_HASHKEYVAL(hashKeyValAndConsDatas)
379{ /*lint --e{715}*/
380 CONSANDDATA* cdata;
381 int minidx;
382 int mididx;
383 int maxidx;
384
385 cdata = (CONSANDDATA*)key;
386
387 assert(cdata != NULL);
388 assert(cdata->vars != NULL);
389 assert(cdata->nvars > 1);
390#ifndef NDEBUG
391 {
392 /* check that these variables are sorted */
393 int v;
394 for( v = cdata->nvars - 1; v > 0; --v )
395 assert(SCIPvarGetIndex(cdata->vars[v]) >= SCIPvarGetIndex(cdata->vars[v - 1]));
396 }
397#endif
398
399 minidx = SCIPvarGetIndex(cdata->vars[0]);
400 mididx = SCIPvarGetIndex(cdata->vars[cdata->nvars / 2]);
401 maxidx = SCIPvarGetIndex(cdata->vars[cdata->nvars - 1]);
402 assert(minidx >= 0 && minidx <= maxidx);
403
404 return SCIPhashFour(cdata->nvars, minidx, mididx, maxidx);
405}
406
407/** initializes the hashmap and -table used in this constraint handler data for artificial variables and specific
408 * and-constraint data objects
409 */
410static
412 SCIP*const scip, /**< SCIP data structure */
413 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to store the constraint handler data */
414 )
415{
416 if( ((*conshdlrdata)->inithashmapandtable) )
417 {
418 assert((*conshdlrdata)->hashtable != NULL);
419 assert((*conshdlrdata)->hashmap != NULL);
420
421 return SCIP_OKAY;
422 }
423
424 assert((*conshdlrdata)->hashtable == NULL);
425 assert((*conshdlrdata)->hashmap == NULL);
426
427 /* create a hash table for and-constraint data objects */
428 (*conshdlrdata)->hashtablesize = HASHSIZE_PSEUDOBOOLEANNONLINEARTERMS;
429 SCIP_CALL( SCIPhashtableCreate(&((*conshdlrdata)->hashtable), SCIPblkmem(scip), (*conshdlrdata)->hashtablesize,
430 hashGetKeyAndConsDatas, hashKeyEqAndConsDatas, hashKeyValAndConsDatas, (void*) scip) );
431
432 /* create a hash table for and-resultant to and-constraint data objects */
433 (*conshdlrdata)->hashmapsize = HASHSIZE_PSEUDOBOOLEANNONLINEARTERMS;
434 SCIP_CALL( SCIPhashmapCreate(&((*conshdlrdata)->hashmap), SCIPblkmem(scip), (*conshdlrdata)->hashmapsize) );
435
436 (*conshdlrdata)->inithashmapandtable = TRUE;
437
438 return SCIP_OKAY;
439}
440
441/** creates constraint handler data for pseudo boolean constraint handler */
442static
444 SCIP*const scip, /**< SCIP data structure */
445 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to store the constraint handler data */
446 )
447{
448 assert(scip != NULL);
449 assert(conshdlrdata != NULL);
450
451 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
452
453 (*conshdlrdata)->allconsanddatas = NULL;
454 (*conshdlrdata)->nallconsanddatas = 0;
455 (*conshdlrdata)->sallconsanddatas = 10;
456
457 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*conshdlrdata)->allconsanddatas), (*conshdlrdata)->sallconsanddatas ) );
458
459 /* set hashmap and -table to NULL, mark them as uninitialized */
460 (*conshdlrdata)->inithashmapandtable = FALSE;
461 (*conshdlrdata)->hashtable = NULL;
462 (*conshdlrdata)->hashtablesize = 0;
463 (*conshdlrdata)->hashmap = NULL;
464 (*conshdlrdata)->hashmapsize = 0;
465
466 /* for constraint names count number of created constraints */
467 (*conshdlrdata)->nlinconss = 0;
468
469 /* initializes how many consanddata objects are used by original constraints */
470 (*conshdlrdata)->noriguses = 0;
471
472 return SCIP_OKAY;
473}
474
475
476/** frees constraint handler data for pseudo boolean constraint handler */
477static
479 SCIP*const scip, /**< SCIP data structure */
480 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
481 )
482{
483 assert(scip != NULL);
484 assert(conshdlrdata != NULL);
485 assert(*conshdlrdata != NULL);
486 assert((*conshdlrdata)->nallconsanddatas == 0);
487
488 /* free hash table if necessary */
489 if( (*conshdlrdata)->inithashmapandtable )
490 {
491 SCIPhashmapFree(&((*conshdlrdata)->hashmap));
492 (*conshdlrdata)->hashmapsize = 0;
493 SCIPhashtableFree(&((*conshdlrdata)->hashtable));
494 (*conshdlrdata)->hashtablesize = 0;
495 }
496 else
497 {
498 assert((*conshdlrdata)->hashmap == NULL);
499 assert((*conshdlrdata)->hashtable == NULL);
500 }
501 (*conshdlrdata)->inithashmapandtable = FALSE;
502
503 /* clear array for all consanddata objects */
504 SCIPfreeBlockMemoryArray(scip, &((*conshdlrdata)->allconsanddatas), (*conshdlrdata)->sallconsanddatas );
505
506 (*conshdlrdata)->allconsanddatas = NULL;
507 (*conshdlrdata)->nallconsanddatas = 0;
508 (*conshdlrdata)->sallconsanddatas = 0;
509
510 SCIPfreeBlockMemory(scip, conshdlrdata);
511
512 return SCIP_OKAY;
513}
514
515/** gets number of variables in linear constraint */
516static
518 SCIP*const scip, /**< SCIP data structure */
519 SCIP_CONS*const cons, /**< linear constraint */
520 SCIP_LINEARCONSTYPE const constype, /**< linear constraint type */
521 int*const nvars /**< pointer to store number variables of linear constraint */
522 )
523{
524 assert(scip != NULL);
525 assert(cons != NULL);
526 assert(nvars != NULL);
527
528 /* determine for each special linear constranit all variables and coefficients */
529 switch( constype )
530 {
532 *nvars = SCIPgetNVarsLinear(scip, cons);
533 break;
535 *nvars = SCIPgetNVarsLogicor(scip, cons);
536 break;
538 *nvars = SCIPgetNVarsKnapsack(scip, cons);
539 break;
541 *nvars = SCIPgetNVarsSetppc(scip, cons);
542 break;
543#ifdef WITHEQKNAPSACK
544 case SCIP_LINEARCONSTYPE_EQKNAPSACK:
545 *nvars = SCIPgetNVarsEQKnapsack(scip, cons);
546 break;
547#endif
549 default:
550 SCIPerrorMessage("unknown linear constraint type\n");
551 return SCIP_INVALIDDATA;
552 }
553
554 return SCIP_OKAY;
555}
556
557
558/** gets sides of linear constraint */
559static
561 SCIP*const scip, /**< SCIP data structure */
562 SCIP_CONS*const cons, /**< linear constraint */
563 SCIP_LINEARCONSTYPE const constype, /**< linear constraint type */
564 SCIP_Real*const lhs, /**< pointer to store left hand side of linear constraint */
565 SCIP_Real*const rhs /**< pointer to store right hand side of linear constraint */
566 )
567{
568 SCIP_SETPPCTYPE type;
569
570 switch( constype )
571 {
573 *lhs = SCIPgetLhsLinear(scip, cons);
574 *rhs = SCIPgetRhsLinear(scip, cons);
575 break;
577 *lhs = 1.0;
578 *rhs = SCIPinfinity(scip);
579 break;
581 *lhs = -SCIPinfinity(scip);
582 *rhs = SCIPgetCapacityKnapsack(scip, cons);
583 break;
585 type = SCIPgetTypeSetppc(scip, cons);
586
587 switch( type )
588 {
590 *lhs = 1.0;
591 *rhs = 1.0;
592 break;
594 *lhs = -SCIPinfinity(scip);
595 *rhs = 1.0;
596 break;
598 *lhs = 1.0;
599 *rhs = SCIPinfinity(scip);
600 break;
601 default:
602 SCIPerrorMessage("unknown setppc type\n");
603 return SCIP_INVALIDDATA;
604 }
605 break;
606#ifdef WITHEQKNAPSACK
607 case SCIP_LINEARCONSTYPE_EQKNAPSACK:
608 *lhs = SCIPgetCapacityEQKnapsack(scip, cons);
609 *rhs = *lhs;
610 break;
611#endif
613 default:
614 SCIPerrorMessage("unknown linear constraint type\n");
615 return SCIP_INVALIDDATA;
616 }
617
618 return SCIP_OKAY;
619}
620
621/** gets variables and coefficients of linear constraint */
622static
624 SCIP*const scip, /**< SCIP data structure */
625 SCIP_CONS*const cons, /**< linear constraint */
626 SCIP_LINEARCONSTYPE const constype, /**< linear constraint type */
627 SCIP_VAR**const vars, /**< array to store variables of linear constraint */
628 SCIP_Real*const coefs, /**< array to store coefficient of linear constraint, or NULL */
629 int*const nvars /**< pointer to store number variables of linear constraint */
630 )
631{
632 SCIP_VAR** linvars;
633 int v;
634
635 assert(scip != NULL);
636 assert(cons != NULL);
637 assert(vars != NULL);
638 assert(nvars != NULL);
639
640 /* determine for each special linear constrait all variables and coefficients */
641 switch( constype )
642 {
644 {
645 SCIP_Real* lincoefs;
646
647 *nvars = SCIPgetNVarsLinear(scip, cons);
648 linvars = SCIPgetVarsLinear(scip, cons);
649
650 if( coefs != NULL )
651 {
652 lincoefs = SCIPgetValsLinear(scip, cons);
653
654 for( v = 0; v < *nvars; ++v )
655 {
656 vars[v] = linvars[v];
657 coefs[v] = lincoefs[v];
658 }
659 }
660 else
661 {
662 for( v = 0; v < *nvars; ++v )
663 vars[v] = linvars[v];
664 }
665
666 break;
667 }
669 *nvars = SCIPgetNVarsLogicor(scip, cons);
670 linvars = SCIPgetVarsLogicor(scip, cons);
671 assert( linvars != NULL );
672
673 if( coefs != NULL )
674 {
675 for( v = 0; v < *nvars; ++v )
676 {
677 vars[v] = linvars[v];
678 coefs[v] = 1.0;
679 }
680 }
681 else
682 {
683 for( v = 0; v < *nvars; ++v )
684 vars[v] = linvars[v];
685 }
686
687 break;
689 {
690 SCIP_Longint* weights;
691
692 *nvars = SCIPgetNVarsKnapsack(scip, cons);
693 linvars = SCIPgetVarsKnapsack(scip, cons);
694 assert( linvars != NULL );
695
696 if( coefs != NULL )
697 {
698 weights = SCIPgetWeightsKnapsack(scip, cons);
699
700 for( v = 0; v < *nvars; ++v )
701 {
702 vars[v] = linvars[v];
703 coefs[v] = (SCIP_Real) weights[v];
704 }
705 }
706 else
707 {
708 for( v = 0; v < *nvars; ++v )
709 vars[v] = linvars[v];
710 }
711
712 break;
713 }
715 *nvars = SCIPgetNVarsSetppc(scip, cons);
716 linvars = SCIPgetVarsSetppc(scip, cons);
717 assert( linvars != NULL );
718
719 if( coefs != NULL )
720 {
721 for( v = 0; v < *nvars; ++v )
722 {
723 vars[v] = linvars[v];
724 coefs[v] = 1.0;
725 }
726 }
727 else
728 {
729 for( v = 0; v < *nvars; ++v )
730 vars[v] = linvars[v];
731 }
732
733 break;
734#ifdef WITHEQKNAPSACK
735 case SCIP_LINEARCONSTYPE_EQKNAPSACK:
736 {
737 SCIP_Longint* weights;
738
739 *nvars = SCIPgetNVarsEQKnapsack(scip, cons);
740 linvars = SCIPgetVarsEQKnapsack(scip, cons);
741 assert( linvars != NULL );
742
743 if( coefs != NULL )
744 {
745 weights = SCIPgetWeightsEQKnapsack(scip, cons);
746
747 for( v = 0; v < *nvars; ++v )
748 {
749 vars[v] = linvars[v];
750 coefs[v] = (SCIP_Real) weights[v];
751 }
752 }
753 else
754 {
755 for( v = 0; v < *nvars; ++v )
756 vars[v] = linvars[v];
757 }
758
759 break;
760 }
761#endif
763 default:
764 SCIPerrorMessage("unknown linear constraint type\n");
765 return SCIP_INVALIDDATA;
766 }
767
768 return SCIP_OKAY;
769}
770
771/** splits up into original linear variables and artificial and-resultants */
772static
774 SCIP*const scip, /**< SCIP data structure */
775 SCIP_CONS*const cons, /**< pseudoboolean constraint */
776 SCIP_VAR**const vars, /**< all variables of linear constraint */
777 SCIP_Real*const coefs, /**< all coefficients of linear constraint, or NULL */
778 int const nvars, /**< number of all variables of linear constraint */
779 SCIP_VAR**const linvars, /**< array to store not and-resultant variables of linear constraint, or NULL */
780 SCIP_Real*const lincoefs, /**< array to store coefficients of not and-resultant variables of linear
781 * constraint, or NULL */
782 int*const nlinvars, /**< pointer to store number of not and-resultant variables, or NULL */
783 SCIP_VAR**const andress, /**< array to store and-resultant variables of linear constraint, or NULL */
784 SCIP_Real*const andcoefs, /**< array to store coefficients of and-resultant variables of linear
785 * constraint, or NULL */
786 SCIP_Bool*const andnegs, /**< array to store negation status of and-resultant variables of linear
787 * constraint, or NULL */
788 int*const nandress /**< pointer to store number of and-resultant variables, or NULL */
789 )
790{
791 SCIP_CONSHDLR* conshdlr;
792 SCIP_CONSHDLRDATA* conshdlrdata;
793 int v;
794
795 assert(scip != NULL);
796 assert(cons != NULL);
797 assert(vars != NULL);
798 assert((linvars != NULL) == (nlinvars != NULL));
799 assert((andress == NULL) || (nandress != NULL));
800 assert((andcoefs != NULL) == (andnegs != NULL));
801 assert((coefs != NULL) == ((lincoefs != NULL) || (andcoefs != NULL)));
802 assert(linvars != NULL || andress != NULL);
803
804 if( nlinvars != NULL )
805 *nlinvars = 0;
806 if( nandress != NULL )
807 *nandress = 0;
808
809 conshdlr = SCIPconsGetHdlr(cons);
810 assert(conshdlr != NULL);
811 conshdlrdata = SCIPconshdlrGetData(conshdlr);
812 assert(conshdlrdata != NULL);
813 assert(conshdlrdata->hashmap != NULL);
814
815 /* split variables into original and artificial variables */
816 for( v = 0; v < nvars; ++v )
817 {
818 SCIP_Bool hashmapentryexists;
819 SCIP_VAR* hashmapvar;
820
821 assert(vars[v] != NULL);
822
823 hashmapentryexists = SCIPhashmapExists(conshdlrdata->hashmap, (void*)(vars[v]));
824
825 if( !hashmapentryexists && SCIPvarIsNegated(vars[v]) )
826 {
827 hashmapvar = SCIPvarGetNegationVar(vars[v]);
828 hashmapentryexists = SCIPhashmapExists(conshdlrdata->hashmap, (void*)(hashmapvar));
829 }
830 else
831 hashmapvar = vars[v];
832
833 /* if and resultant is not a resultant anymore (meaning the corresponding and-constraint was deleted/upgraded),
834 * correct the flag and count this variable as normal linear variable
835 */
836 if( hashmapentryexists )
837 {
838 if( !SCIPconsIsOriginal(cons) )
839 {
840 CONSANDDATA* consanddata = (CONSANDDATA*) SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)(hashmapvar));
841 assert(consanddata != NULL);
842
843 hashmapentryexists = (consanddata->istransformed);
844
845 if( hashmapentryexists )
846 {
847 assert(consanddata->cons != NULL);
848 hashmapentryexists = !SCIPconsIsDeleted(consanddata->cons);
849 }
850 }
851 }
852
853 if( !hashmapentryexists && linvars != NULL && nlinvars != NULL )
854 {
855 linvars[*nlinvars] = vars[v];
856 if( lincoefs != NULL )
857 {
858 assert(coefs != NULL);
859 lincoefs[*nlinvars] = coefs[v];
860 }
861 ++(*nlinvars);
862 }
863 else if( hashmapentryexists && nandress != NULL )
864 {
865 if( andress != NULL )
866 {
867 andress[*nandress] = hashmapvar;
868
869 if( andcoefs != NULL )
870 {
871 assert(andnegs != NULL);
872 assert(coefs != NULL);
873 andcoefs[*nandress] = coefs[v];
874 andnegs[*nandress] = (vars[v] != hashmapvar);
875 }
876 }
877 ++(*nandress);
878 }
879 }
880
881 return SCIP_OKAY;
882}
883
884
885#ifdef CHECK_CONSISTENCY
886/** check constraint consistency */
887static
889 SCIP*const scip, /**< SCIP data structure */
890 SCIP_CONS*const cons /**< pseudoboolean constraint */
891 )
892{
893 SCIP_CONSDATA* consdata;
894 SCIP_VAR** vars;
895 SCIP_Real* coefs;
896 int nvars;
897 SCIP_VAR** linvars;
898 SCIP_Real* lincoefs;
899 int nlinvars;
900 SCIP_VAR** andress;
901 SCIP_Real* andcoefs;
902 SCIP_Bool* andnegs;
903 int nandress;
904 SCIP_Bool* alreadyfound;
905 SCIP_VAR* res;
906 int c;
907 int v;
908 SCIP_Real newlhs;
909 SCIP_Real newrhs;
910
911 assert(scip != NULL);
912 assert(cons != NULL);
913
915 return;
916
917 consdata = SCIPconsGetData(cons);
918 assert(consdata != NULL);
919
920 /* check standard pointers and sizes */
921 assert(consdata->lincons != NULL);
922 assert(!SCIPconsIsDeleted(consdata->lincons));
923 assert(consdata->linconstype > SCIP_LINEARCONSTYPE_INVALIDCONS);
924 assert(consdata->consanddatas != NULL);
925 assert(consdata->nconsanddatas > 0);
926 assert(consdata->nconsanddatas <= consdata->sconsanddatas);
927
928 /* get sides of linear constraint */
929 SCIP_CALL_ABORT( getLinearConsSides(scip, consdata->lincons, consdata->linconstype, &newlhs, &newrhs) );
930 assert(!SCIPisInfinity(scip, newlhs));
931 assert(!SCIPisInfinity(scip, -newrhs));
932 assert(SCIPisLE(scip, newlhs, newrhs));
933 assert(SCIPisEQ(scip, newrhs, consdata->rhs) || SCIPisEQ(scip, newrhs, -consdata->lhs));
934 assert(SCIPisEQ(scip, newlhs, consdata->lhs) || SCIPisEQ(scip, newlhs, -consdata->rhs));
935
936 /* check number of linear variables */
937 SCIP_CALL_ABORT( getLinearConsNVars(scip, consdata->lincons, consdata->linconstype, &nvars) );
938 assert(nvars == consdata->nlinvars + consdata->nconsanddatas);
939
940 /* get temporary memory */
941 SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &vars, nvars) );
942 SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &coefs, nvars) );
943 SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &linvars, nvars) );
944 SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &lincoefs, nvars) );
945 SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &andress, nvars) );
946 SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &andcoefs, nvars) );
947 SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &andnegs, nvars) );
948 SCIP_CALL_ABORT( SCIPallocClearBufferArray(scip, &alreadyfound, nvars) );
949
950 /* get variables and coefficients */
951 SCIP_CALL_ABORT( getLinearConsVarsData(scip, consdata->lincons, consdata->linconstype, vars, coefs, &nvars) );
952 assert(nvars == 0 || (coefs != NULL));
953
954 /* calculate all not artificial linear variables and all artificial and-resultants */
955 SCIP_CALL_ABORT( getLinVarsAndAndRess(scip, cons, vars, coefs, nvars, linvars, lincoefs, &nlinvars,
956 andress, andcoefs, andnegs, &nandress) );
957 assert(nlinvars == consdata->nlinvars);
958 assert(nandress == consdata->nconsanddatas);
959
960 for( v = nandress - 1; v >= 0; --v )
961 {
962 SCIP_VAR* andresultant = andress[v];
963 int nfound = 0;
964
965 for( c = consdata->nconsanddatas - 1; c >= 0; --c )
966 {
967 assert(consdata->consanddatas[c] != NULL);
968 if( consdata->consanddatas[c]->cons != NULL )
969 {
970 res = SCIPgetResultantAnd(scip, consdata->consanddatas[c]->cons);
971 assert(res != NULL);
972
973 if( res == andresultant && consdata->andnegs[c] == andnegs[v] && consdata->andcoefs[c] == andcoefs[v] )
974 {
975 /* resultant should be either active or a negated variable of an active one */
977 assert(!alreadyfound[c]);
978
979 /* all and-resultants should be merged, so it is only allowed that each variable exists one time */
980 alreadyfound[c] = TRUE;
981 ++nfound;
982 break;
983 }
984 }
985 }
986 assert(nfound == 1);
987 }
988
989 for( c = consdata->nconsanddatas - 1; c >= 0; --c )
990 {
991 assert(alreadyfound[c]);
992 }
993
994 /* free temporary memory */
995 SCIPfreeBufferArray(scip, &alreadyfound);
996 SCIPfreeBufferArray(scip, &andnegs);
997 SCIPfreeBufferArray(scip, &andcoefs);
998 SCIPfreeBufferArray(scip, &andress);
999 SCIPfreeBufferArray(scip, &lincoefs);
1000 SCIPfreeBufferArray(scip, &linvars);
1001 SCIPfreeBufferArray(scip, &coefs);
1002 SCIPfreeBufferArray(scip, &vars);
1003}
1004#else
1005#define checkConsConsistency(scip, cons) /**/
1006#endif
1007
1008
1009/** transforming transformed consanddata object back to original space, if an corresponding original constraint exists,
1010 * also clearing all transformed data, i.e. releasing transformed variables
1011 */
1012static
1014 SCIP*const scip, /**< SCIP data structure */
1015 CONSANDDATA* consanddata, /**< consanddata object */
1016 SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */
1017 )
1018{
1019 SCIP_VAR** tmpvars;
1020 SCIP_Bool origdata;
1021 int ntmpvars;
1022 int v;
1023
1024 assert(scip != NULL);
1025 assert(consanddata != NULL);
1026 assert(conshdlrdata != NULL);
1027
1028 origdata = TRUE;
1029
1030 tmpvars = consanddata->vars;
1031 ntmpvars = consanddata->nvars;
1032
1033 /* release all transformed variables */
1034 for( v = ntmpvars - 1; v >= 0; --v )
1035 {
1036 assert(tmpvars[v] != NULL);
1037 if( SCIPvarIsTransformed(tmpvars[v]) )
1038 {
1039 SCIP_CALL( SCIPreleaseVar(scip, &tmpvars[v]) );
1040 origdata = FALSE;
1041 }
1042 }
1043
1044 tmpvars = consanddata->newvars;
1045 ntmpvars = consanddata->nnewvars;
1046
1047 /* release all variables */
1048 for( v = ntmpvars - 1; v >= 0; --v )
1049 {
1050 assert(tmpvars[v] != NULL);
1051 if( SCIPvarIsTransformed(tmpvars[v]) )
1052 {
1053 SCIP_CALL( SCIPreleaseVar(scip, &tmpvars[v]) );
1054 origdata = FALSE;
1055 }
1056 }
1057
1058 /* reinstall original data */
1059 if( !origdata || consanddata->nvars == 0 )
1060 {
1061 SCIPfreeBlockMemoryArrayNull(scip, &(consanddata->vars), consanddata->svars);
1062 SCIPfreeBlockMemoryArrayNull(scip, &(consanddata->newvars), consanddata->snewvars);
1063
1064 consanddata->nuses = 0;
1065 consanddata->nvars = 0;
1066 consanddata->svars = 0;
1067 consanddata->nnewvars = 0;
1068 consanddata->snewvars = 0;
1069 consanddata->istransformed = FALSE;
1070
1071 if( consanddata->noriguses > 0 )
1072 {
1073 assert(consanddata->origcons != NULL);
1074 assert(consanddata->isoriginal);
1075
1076 assert(SCIPgetNVarsAnd(scip, consanddata->origcons) > 0);
1077 assert(SCIPgetVarsAnd(scip, consanddata->origcons) != NULL);
1078 consanddata->nvars = SCIPgetNVarsAnd(scip, consanddata->origcons);
1079 consanddata->svars = consanddata->nvars;
1080
1081 if( consanddata->nvars > 0 )
1082 {
1083 SCIP_VAR** andvars = SCIPgetVarsAnd(scip, consanddata->origcons);
1084
1085 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(consanddata->vars), andvars, consanddata->nvars) );
1086
1087 /* sort variables */
1088 SCIPsortPtr((void**)(consanddata->vars), SCIPvarComp, consanddata->nvars);
1089 }
1090
1091 /* check that the hash map and tabkle are still having all information */
1092 if( conshdlrdata->inithashmapandtable )
1093 {
1094 assert(conshdlrdata->hashmap != NULL);
1095 assert(conshdlrdata->hashtable != NULL);
1096 assert(SCIPgetResultantAnd(scip, consanddata->origcons) != NULL);
1097 assert(SCIPhashtableExists(conshdlrdata->hashtable, (void*)consanddata));
1098 assert(consanddata == (CONSANDDATA*)(SCIPhashtableRetrieve(conshdlrdata->hashtable, (void*)consanddata)));
1099 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddata->origcons)));
1100 assert(consanddata == (CONSANDDATA*)(SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddata->origcons))));
1101 }
1102 }
1103 else
1104 assert(consanddata->origcons == NULL);
1105 }
1106 else
1107 {
1108 assert(consanddata->nuses == 0);
1109 assert(consanddata->nnewvars == 0);
1110 assert(consanddata->snewvars == 0);
1111 assert(consanddata->newvars == NULL);
1112
1113 consanddata->istransformed = FALSE;
1114
1115 if( consanddata->noriguses > 0 )
1116 {
1117 assert(consanddata->origcons != NULL);
1118 assert(consanddata->nvars > 0);
1119 assert(consanddata->svars > 0);
1120 assert(consanddata->vars != NULL);
1121 assert(consanddata->isoriginal);
1122
1123 /* check that the hash map and tabkle are still having all information */
1124 if( conshdlrdata->inithashmapandtable )
1125 {
1126 assert(conshdlrdata->hashmap != NULL);
1127 assert(conshdlrdata->hashtable != NULL);
1128 assert(SCIPgetResultantAnd(scip, consanddata->origcons) != NULL);
1129 assert(SCIPhashtableExists(conshdlrdata->hashtable, (void*)consanddata));
1130 assert(consanddata == (CONSANDDATA*)(SCIPhashtableRetrieve(conshdlrdata->hashtable, (void*)consanddata)));
1131 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddata->origcons)));
1132 assert(consanddata == (CONSANDDATA*)(SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddata->origcons))));
1133 }
1134 }
1135 }
1136
1137 return SCIP_OKAY;
1138}
1139
1140
1141
1142/** creates a pseudo boolean constraint data */
1143static
1145 SCIP*const scip, /**< SCIP data structure */
1146 SCIP_CONSHDLR*const conshdlr, /**< pseudoboolean constraint handler */
1147 SCIP_CONSDATA** consdata, /**< pointer to linear constraint data */
1148 SCIP_CONS*const lincons, /**< linear constraint with artificial and-resultants representing this pseudoboolean constraint */
1149 SCIP_LINEARCONSTYPE const linconstype, /**< type of linear constraint */
1150 SCIP_CONS**const andconss, /**< array of and-constraints which occur in this pseudoboolean constraint */
1151 SCIP_Real*const andcoefs, /**< coefficients of and-constraints */
1152 SCIP_Bool*const andnegs, /**< negation status of and-constraints (or NULL, if no negated resultants) */
1153 int const nandconss, /**< number of and-constraints */
1154 SCIP_VAR*const indvar, /**< indicator variable if it's a soft constraint, or NULL */
1155 SCIP_Real const weight, /**< weight of the soft constraint, if it is one */
1156 SCIP_Bool const issoftcons, /**< is this a soft constraint */
1157 SCIP_VAR* const intvar, /**< a artificial variable which was added only for the objective function,
1158 * if this variable is not NULL this constraint (without this integer
1159 * variable) describes the objective function */
1160 SCIP_Real lhs, /**< left hand side of row */
1161 SCIP_Real rhs, /**< right hand side of row */
1162 SCIP_Bool check, /**< is the new constraint a check constraint? */
1163 SCIP_Bool transforming /**< are we called by CONSTRANS */
1164 )
1165{
1166 SCIP_Bool transformed;
1167 int nvars;
1168
1169 assert(scip != NULL);
1170 assert(conshdlr != NULL);
1171 assert(consdata != NULL);
1172 assert(lincons != NULL && linconstype > SCIP_LINEARCONSTYPE_INVALIDCONS);
1173 assert(nandconss == 0 || (andconss != NULL && andcoefs != NULL));
1174 assert(!issoftcons || (!SCIPisZero(scip, weight) && indvar != NULL));
1175
1176 /* adjust right hand side */
1177 if( SCIPisInfinity(scip, rhs) )
1178 rhs = SCIPinfinity(scip);
1179 else if( SCIPisInfinity(scip, -rhs) )
1180 rhs = -SCIPinfinity(scip);
1181
1182 /* adjust left hand side */
1183 if( SCIPisInfinity(scip, -lhs) )
1184 lhs = -SCIPinfinity(scip);
1185 else if( SCIPisInfinity(scip, lhs) )
1186 lhs = SCIPinfinity(scip);
1187
1188 /* check left and right side */
1189 if( SCIPisGT(scip, lhs, rhs) )
1190 {
1191 SCIPerrorMessage("left hand side of pseudo boolean constraint greater than right hand side\n");
1192 SCIPerrorMessage(" -> lhs=%g, rhs=%g\n", lhs, rhs);
1193 return SCIP_INVALIDDATA;
1194 }
1195
1196 transformed = SCIPisTransformed(scip);
1197
1198 /* allocate memory for the constraint data */
1199 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
1200
1201 /* initialize the weights for soft constraints */
1202 (*consdata)->issoftcons = issoftcons;
1203 if( issoftcons )
1204 {
1205 (*consdata)->weight = weight;
1206 if( transformed )
1207 {
1208 SCIP_CALL( SCIPgetTransformedVar(scip, indvar, &((*consdata)->indvar)) );
1209 }
1210 else
1211 (*consdata)->indvar = indvar;
1212 }
1213 else
1214 (*consdata)->indvar = NULL;
1215
1216 /* copy artificial integer variable if it exist */
1217 if( intvar != NULL )
1218 {
1219 if( transformed )
1220 {
1221 SCIP_CALL( SCIPgetTransformedVar(scip, intvar, &((*consdata)->intvar)) );
1222 }
1223 else
1224 (*consdata)->intvar = intvar;
1225 }
1226 else
1227 (*consdata)->intvar = NULL;
1228
1229 /* copy linear constraint */
1230 (*consdata)->lincons = lincons;
1231 (*consdata)->linconstype = linconstype;
1232
1233 /* get transformed linear constraint and capture it if necessary */
1234 if( transforming )
1235 {
1236 /* do not capture the and constraint when scip is in transformed mode; this automatically happens in
1237 * SCIPtransformCons()
1238 */
1239 SCIP_CALL( SCIPtransformCons(scip, (*consdata)->lincons, &((*consdata)->lincons)) );
1240 assert((*consdata)->lincons != NULL);
1241 }
1242
1243 if( transforming || transformed )
1244 {
1245 assert(SCIPconsIsTransformed((*consdata)->lincons));
1246
1247 /* we want to check all necessary transformed linear constraints */
1248 SCIP_CALL( SCIPsetConsChecked(scip, (*consdata)->lincons, check) );
1249 }
1250
1251 /* get number of non-linear terms in pseudoboolean constraint */
1252 SCIP_CALL( getLinearConsNVars(scip, (*consdata)->lincons, (*consdata)->linconstype, &nvars) );
1253 (*consdata)->nlinvars = nvars - nandconss;
1254
1255 /* copy and-constraints */
1256 if( nandconss > 0 )
1257 {
1258 SCIP_CONSHDLRDATA* conshdlrdata;
1259 SCIP_VAR** andress;
1260 int c;
1261
1262 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*consdata)->consanddatas), nandconss) );
1263 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &((*consdata)->andcoefs), andcoefs, nandconss) );
1264 if( andnegs != NULL )
1265 {
1266 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &((*consdata)->andnegs), andnegs, nandconss) );
1267 }
1268 else
1269 {
1270 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &((*consdata)->andnegs), nandconss) );
1271 }
1272 (*consdata)->nconsanddatas = nandconss;
1273 (*consdata)->sconsanddatas = nandconss;
1274
1275 /* allocate temporary memory */
1276 SCIP_CALL( SCIPallocBufferArray(scip, &andress, nandconss) );
1277
1278 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1279 assert(conshdlrdata != NULL);
1280 assert(conshdlrdata->hashmap != NULL);
1281
1282 /* get all and-resultants for sorting */
1283 for( c = nandconss - 1; c >= 0; --c )
1284 {
1285 assert(andconss[c] != NULL);
1286
1287 andress[c] = SCIPgetResultantAnd(scip, andconss[c]);
1288 assert(andress[c] != NULL);
1289
1290 (*consdata)->consanddatas[c] = (CONSANDDATA*) SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)andress[c]);
1291 assert((*consdata)->consanddatas[c] != NULL);
1292 assert((*consdata)->consanddatas[c]->origcons == andconss[c] || (*consdata)->consanddatas[c]->cons == andconss[c]);
1293
1294 if( transforming )
1295 {
1296 /* if we perform a new transformation, we need to capture the transformed constraint */
1297 if( (*consdata)->consanddatas[c]->origcons != NULL && (*consdata)->consanddatas[c]->cons == NULL )
1298 {
1299 SCIP_VAR** vars;
1300 int ncvars;
1301 int v;
1302
1303 /* do not capture the and constraint when scip is in transformed mode; this automatically happens in
1304 * SCIPtransformCons()
1305 */
1306 SCIP_CALL( SCIPtransformCons(scip, (*consdata)->consanddatas[c]->origcons, &((*consdata)->consanddatas[c]->cons)) );
1307 assert((*consdata)->consanddatas[c]->cons != NULL);
1308 assert((*consdata)->consanddatas[c]->newvars == NULL);
1309 assert((*consdata)->consanddatas[c]->isoriginal);
1310
1311 (*consdata)->consanddatas[c]->istransformed = TRUE;
1312
1313 vars = (*consdata)->consanddatas[c]->vars;
1314 ncvars = (*consdata)->consanddatas[c]->nvars;
1315 assert(vars != NULL || ncvars == 0);
1316
1317 /* get transformed variables */
1318 SCIP_CALL( SCIPgetTransformedVars(scip, ncvars, vars, vars) );
1319
1320 /* resort variables in transformed problem, because the order might change while tranforming */
1321 SCIPsortPtr((void**)vars, SCIPvarComp, ncvars);
1322
1323 /* capture all transformed variables */
1324 for( v = ncvars - 1; v >= 0; --v )
1325 {
1326 SCIP_CALL( SCIPcaptureVar(scip, vars[v]) ); /*lint !e613*/
1327 }
1328 }
1329 else if( (*consdata)->consanddatas[c]->cons != NULL )
1330 assert((*consdata)->consanddatas[c]->istransformed);
1331
1332 ++((*consdata)->consanddatas[c]->nuses);
1333 }
1334 else if( transformed )
1335 {
1336 assert((*consdata)->consanddatas[c]->cons == andconss[c]);
1337 assert(SCIPconsIsTransformed(andconss[c]));
1338 assert((*consdata)->consanddatas[c]->istransformed);
1339 }
1340 }
1341
1342 /* sort and-constraints after problem indices of corresponding and-resultants */
1343 SCIPsortPtrPtrRealBool((void**)andress, (void**)((*consdata)->consanddatas), (*consdata)->andcoefs, (*consdata)->andnegs, resvarComp, nandconss);
1344
1345 /* free temporary memory */
1346 SCIPfreeBufferArray(scip, &andress);
1347 }
1348 else
1349 {
1350 (*consdata)->consanddatas = NULL;
1351 (*consdata)->andcoefs = NULL;
1352 (*consdata)->andnegs = NULL;
1353 (*consdata)->nconsanddatas = 0;
1354 (*consdata)->sconsanddatas = 0;
1355 }
1356
1357 /* copy left and right hand side */
1358 (*consdata)->lhs = lhs;
1359 (*consdata)->rhs = rhs;
1360
1361 (*consdata)->changed = TRUE;
1362 (*consdata)->propagated = FALSE;
1363 (*consdata)->presolved = FALSE;
1364 (*consdata)->cliquesadded = FALSE;
1365 (*consdata)->upgradetried = TRUE;
1366
1367 /* count number of used consanddata objects in original problem */
1369 {
1370 SCIP_CONSHDLRDATA* conshdlrdata;
1371 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1372 assert(conshdlrdata != NULL);
1373
1374 conshdlrdata->noriguses += (*consdata)->nconsanddatas;
1375 }
1376
1377 return SCIP_OKAY;
1378}
1379
1380/** free a pseudo boolean constraint data */
1381static
1383 SCIP*const scip, /**< SCIP data structure */
1384 SCIP_CONSDATA** consdata, /**< pointer to linear constraint data */
1385 SCIP_Bool isorig, /**< are we freeing an original constraint? */
1386 SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */
1387 )
1388{
1389 CONSANDDATA** consanddatas;
1390 int nconsanddatas;
1391 int c;
1392
1393 assert(scip != NULL);
1394 assert(consdata != NULL);
1395 assert(*consdata != NULL);
1396 assert((*consdata)->nconsanddatas == 0 || (*consdata)->consanddatas != NULL);
1397 assert(conshdlrdata != NULL);
1398
1399 /* release linear constraint */
1400 if( (*consdata)->lincons != NULL )
1401 {
1402 SCIP_CALL( SCIPreleaseCons(scip, &((*consdata)->lincons)) );
1403 }
1404
1405 nconsanddatas = (*consdata)->nconsanddatas;
1406 consanddatas = (*consdata)->consanddatas;
1407
1408 /* count down uses and if necessary release constraints and delete data from hashtable and -map */
1409 for( c = nconsanddatas - 1; c >= 0; --c )
1410 {
1411 assert((consanddatas[c]->origcons == NULL) == (consanddatas[c]->noriguses == 0));
1412 assert((consanddatas[c]->cons == NULL) == (consanddatas[c]->nuses == 0));
1413 assert(consanddatas[c]->nuses >= 0);
1414 assert(consanddatas[c]->noriguses >= 0);
1415 assert(isorig ? consanddatas[c]->cons == NULL : TRUE);
1416
1417 /* are we deleteing a transformed constraint */
1418 if( !isorig && consanddatas[c]->cons != NULL )
1419 {
1420 assert(!SCIPconsIsOriginal(consanddatas[c]->cons));
1421
1422 --(consanddatas[c]->nuses);
1423
1424 /* if the consanddata is not used anymore, release the constraint and clear the hashmap- and table */
1425 if( consanddatas[c]->nuses == 0 )
1426 {
1427 if( conshdlrdata->inithashmapandtable )
1428 {
1429 assert(conshdlrdata->hashmap != NULL);
1430 assert(conshdlrdata->hashtable != NULL);
1431
1432 /* remove consanddata from hashtable, if it existed only in transformed space */
1433 if( consanddatas[c]->origcons == NULL )
1434 {
1435 assert(SCIPhashtableExists(conshdlrdata->hashtable, (void*)consanddatas[c]));
1436 SCIP_CALL( SCIPhashtableRemove(conshdlrdata->hashtable, (void*)consanddatas[c]) );
1437 }
1438 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddatas[c]->cons)));
1439 SCIP_CALL( SCIPhashmapRemove(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddatas[c]->cons)) );
1440 }
1441
1442 SCIP_CALL( SCIPreleaseCons(scip, &(consanddatas[c]->cons)) );
1443
1444 /* if the consanddata object was only used in transformed space, delete the memory block */
1445 if( consanddatas[c]->origcons == NULL )
1446 {
1447 int d;
1448
1449 assert(conshdlrdata->nallconsanddatas > 0);
1450
1451 for( d = conshdlrdata->nallconsanddatas - 1; d >= 0; --d )
1452 {
1453 if( conshdlrdata->allconsanddatas[d] == consanddatas[c] )
1454 {
1455 --conshdlrdata->nallconsanddatas;
1456
1457 SCIPfreeBlockMemory(scip, &(conshdlrdata->allconsanddatas[d])); /*lint !e866*/
1458
1459 conshdlrdata->allconsanddatas[d] = conshdlrdata->allconsanddatas[conshdlrdata->nallconsanddatas];
1460 break;
1461 }
1462 }
1463 assert(d >= 0);
1464 continue;
1465 }
1466 }
1467 }
1468 /* are we deleteing an original constraint */
1469 else if( isorig && consanddatas[c]->origcons != NULL )
1470 {
1471 assert(SCIPconsIsOriginal(consanddatas[c]->origcons));
1472 assert(consanddatas[c]->nuses == 0);
1473 assert(consanddatas[c]->nnewvars == 0);
1474 assert(consanddatas[c]->snewvars == 0);
1475 assert(consanddatas[c]->newvars == NULL);
1476
1477 --(consanddatas[c]->noriguses);
1478
1479 /* if the consanddata is not used anymore, release the constraint and clear the hashmap- and table */
1480 if( consanddatas[c]->noriguses == 0 )
1481 {
1482 int d;
1483
1484 if( conshdlrdata->inithashmapandtable )
1485 {
1486 assert(conshdlrdata->hashmap != NULL);
1487 assert(conshdlrdata->hashtable != NULL);
1488
1489 assert(SCIPhashtableExists(conshdlrdata->hashtable, (void*)consanddatas[c]));
1490 SCIP_CALL( SCIPhashtableRemove(conshdlrdata->hashtable, (void*)consanddatas[c]) );
1491
1492 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddatas[c]->origcons)));
1493 SCIP_CALL( SCIPhashmapRemove(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddatas[c]->origcons)) );
1494 }
1495
1496 if( consanddatas[c]->vars != NULL )
1497 {
1498 assert(consanddatas[c]->nvars > 0);
1499 assert(consanddatas[c]->svars > 0);
1500 assert(consanddatas[c]->svars >= consanddatas[c]->nvars);
1501
1502 SCIPfreeBlockMemoryArrayNull(scip, &(consanddatas[c]->vars), consanddatas[c]->svars);
1503 consanddatas[c]->nvars = 0;
1504 consanddatas[c]->svars = 0;
1505 }
1506 else
1507 {
1508 assert(consanddatas[c]->nvars == 0);
1509 assert(consanddatas[c]->svars == 0);
1510 }
1511
1512 SCIP_CALL( SCIPreleaseCons(scip, &(consanddatas[c]->origcons)) );
1513 assert(consanddatas[c]->origcons == NULL);
1514
1515 /* delete consanddata object */
1516 assert(conshdlrdata->nallconsanddatas > 0);
1517 for( d = conshdlrdata->nallconsanddatas - 1; d >= 0; --d )
1518 {
1519 if( conshdlrdata->allconsanddatas[d] == consanddatas[c] )
1520 {
1521 --conshdlrdata->nallconsanddatas;
1522
1523 SCIPfreeBlockMemory(scip, &(conshdlrdata->allconsanddatas[d])); /*lint !e866*/
1524
1525 conshdlrdata->allconsanddatas[d] = conshdlrdata->allconsanddatas[conshdlrdata->nallconsanddatas];
1526 break;
1527 }
1528 }
1529 assert(d >= 0);
1530
1531 continue;
1532 }
1533 }
1534 else
1535 {
1536 assert(!consanddatas[c]->istransformed);
1537 assert(consanddatas[c]->cons == NULL);
1538 }
1539
1540 /* clear and remove capture of transformed consanddata */
1541 if( consanddatas[c]->nuses == 0 && consanddatas[c]->istransformed )
1542 {
1543 SCIP_CALL( transformToOrig(scip, consanddatas[c], conshdlrdata) );
1544 }
1545#ifndef NDEBUG
1546 else if( consanddatas[c]->nuses == 0 )
1547 {
1548 SCIP_VAR** tmpvars;
1549 int ntmpvars;
1550 int v;
1551
1552 assert(consanddatas[c]->nnewvars == 0);
1553 assert(consanddatas[c]->snewvars == 0);
1554 assert(consanddatas[c]->newvars == NULL);
1555
1556 tmpvars = consanddatas[c]->vars;
1557 ntmpvars = consanddatas[c]->nvars;
1558
1559 /* release all variables */
1560 for( v = ntmpvars - 1; v >= 0; --v )
1561 {
1562 assert(tmpvars[v] != NULL);
1563 assert(SCIPvarIsOriginal(tmpvars[v]));
1564 }
1565 }
1566#endif
1567
1568 /* restore original data */
1569 if( !consanddatas[c]->istransformed && consanddatas[c]->noriguses > 0 )
1570 {
1571 assert(consanddatas[c]->origcons != NULL);
1572 assert(consanddatas[c]->nuses == 0);
1573 assert(consanddatas[c]->nnewvars == 0);
1574 assert(consanddatas[c]->snewvars == 0);
1575 assert(consanddatas[c]->newvars == NULL);
1576 assert(consanddatas[c]->nvars > 0);
1577 assert(consanddatas[c]->svars > 0);
1578 assert(consanddatas[c]->svars >= consanddatas[c]->nvars);
1579 assert(consanddatas[c]->vars != NULL);
1580 assert(consanddatas[c]->isoriginal);
1581
1582 assert(consanddatas[c]->nvars == SCIPgetNVarsAnd(scip, consanddatas[c]->origcons));
1583 assert(SCIPgetVarsAnd(scip, consanddatas[c]->origcons) != NULL);
1584
1585 /* check that the hash map and tabkle are still having all information */
1586 if( conshdlrdata->inithashmapandtable )
1587 {
1588 assert(conshdlrdata->hashmap != NULL);
1589 assert(conshdlrdata->hashtable != NULL);
1590 assert(SCIPgetResultantAnd(scip, consanddatas[c]->origcons) != NULL);
1591 assert(SCIPhashtableExists(conshdlrdata->hashtable, (void*)consanddatas[c]));
1592 assert(consanddatas[c] == (CONSANDDATA*)(SCIPhashtableRetrieve(conshdlrdata->hashtable, (void*)consanddatas[c])));
1593 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddatas[c]->origcons)));
1594 assert(consanddatas[c] == (CONSANDDATA*)(SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddatas[c]->origcons))));
1595 }
1596 }
1597 }
1598
1599 /* free array of and-constraints */
1600 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->andnegs), (*consdata)->sconsanddatas);
1601 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->andcoefs), (*consdata)->sconsanddatas);
1602 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->consanddatas), (*consdata)->sconsanddatas);
1603
1604 SCIPfreeBlockMemory(scip, consdata);
1605
1606 return SCIP_OKAY;
1607}
1608
1609/** check the locks of an AND resultant and removes it from all global structures if the resultant is not locked anymore */
1610static
1612 SCIP*const scip, /**< SCIP data structure */
1613 SCIP_VAR* res /**< resultant of AND constraint */
1614 )
1615{
1616 assert(scip != NULL);
1617 assert(res != NULL);
1618
1619 /* the resultant has no locks left and might be dual fixed now, we need to delete all its cliques */
1622 {
1624 }
1625
1626 return SCIP_OKAY;
1627}
1628
1629/** installs rounding locks for the given and-constraint associated with given coefficient */
1630static
1632 SCIP*const scip, /**< SCIP data structure */
1633 SCIP_CONS*const cons, /**< pseudoboolean constraint */
1634 CONSANDDATA*const consanddata, /**< CONSANDDATA object for which we want to add the locks */
1635 SCIP_Real const coef, /**< coefficient which led to old locks */
1636 SCIP_Real const lhs, /**< left hand side */
1637 SCIP_Real const rhs /**< right hand side */
1638 )
1639{
1640 SCIP_VAR** vars;
1641 int nvars;
1642 SCIP_VAR* res;
1643 SCIP_Bool haslhs;
1644 SCIP_Bool hasrhs;
1645 int v;
1646
1647 assert(scip != NULL);
1648 assert(cons != NULL);
1650 assert(consanddata != NULL);
1651 assert(!SCIPisInfinity(scip, coef) && !SCIPisInfinity(scip, -coef));
1652 assert(!SCIPisInfinity(scip, lhs));
1653 assert(!SCIPisInfinity(scip, -rhs));
1654 assert(SCIPisLE(scip, lhs, rhs));
1655
1656 /* choose correct variable array to add locks for, we only add locks for now valid variables */
1657 if( consanddata->nnewvars > 0 )
1658 {
1659 vars = consanddata->newvars;
1660 nvars = consanddata->nnewvars;
1661 }
1662 else
1663 {
1664 vars = consanddata->vars;
1665 nvars = consanddata->nvars;
1666 }
1667
1668 res = SCIPgetResultantAnd(scip, consanddata->cons);
1669 assert(nvars == 0 || (vars != NULL && res != NULL));
1670
1671 /* check which sites are infinity */
1672 haslhs = !SCIPisInfinity(scip, -lhs);
1673 hasrhs = !SCIPisInfinity(scip, rhs);
1674
1675 if( SCIPconsIsLocked(cons) )
1676 {
1677 /* locking variables */
1678 if( SCIPisPositive(scip, coef) )
1679 {
1680 for( v = nvars - 1; v >= 0; --v )
1681 {
1682 SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, haslhs, hasrhs) );
1683 }
1684 }
1685 else
1686 {
1687 for( v = nvars - 1; v >= 0; --v )
1688 {
1689 SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, hasrhs, haslhs) );
1690 }
1691 }
1692 SCIP_CALL( SCIPlockVarCons(scip, res, cons, TRUE, TRUE) );
1693 }
1694
1695 return SCIP_OKAY;
1696}
1697
1698/** removes rounding locks for the given and-constraint associated with given coefficient */
1699static
1701 SCIP*const scip, /**< SCIP data structure */
1702 SCIP_CONS*const cons, /**< pseudoboolean constraint */
1703 CONSANDDATA*const consanddata, /**< CONSANDDATA object for which we want to delete the locks */
1704 SCIP_Real const coef, /**< coefficient which led to old locks */
1705 SCIP_Real const lhs, /**< left hand side which led to old locks */
1706 SCIP_Real const rhs /**< right hand side which led to old locks */
1707 )
1708{
1709 SCIP_VAR** vars;
1710 int nvars;
1711 SCIP_VAR* res;
1712 SCIP_Bool haslhs;
1713 SCIP_Bool hasrhs;
1714 int v;
1715
1716 assert(scip != NULL);
1717 assert(cons != NULL);
1719 assert(consanddata != NULL);
1720 assert(!SCIPisInfinity(scip, coef) && !SCIPisInfinity(scip, -coef));
1721 assert(!SCIPisInfinity(scip, lhs));
1722 assert(!SCIPisInfinity(scip, -rhs));
1723 assert(SCIPisLE(scip, lhs, rhs));
1724
1725 vars = consanddata->vars;
1726 nvars = consanddata->nvars;
1727
1728 if( consanddata->cons != NULL )
1729 res = SCIPgetResultantAnd(scip, consanddata->cons);
1730 else
1731 res = NULL;
1732 assert(nvars == 0 || vars != NULL);
1733
1734 /* check which sites are infinity */
1735 haslhs = !SCIPisInfinity(scip, -lhs);
1736 hasrhs = !SCIPisInfinity(scip, rhs);
1737
1738 if( SCIPconsIsLocked(cons) )
1739 {
1740 /* unlock variables */
1741 if( SCIPisPositive(scip, coef) )
1742 {
1743 for( v = nvars - 1; v >= 0; --v )
1744 {
1745 SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, haslhs, hasrhs) );
1746 }
1747 }
1748 else
1749 {
1750 for( v = nvars - 1; v >= 0; --v )
1751 {
1752 SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, hasrhs, haslhs) );
1753 }
1754 }
1755
1756 if( res != NULL )
1757 {
1758 SCIP_CALL( SCIPunlockVarCons(scip, res, cons, TRUE, TRUE) );
1759
1761 }
1762 }
1763
1764 return SCIP_OKAY;
1765}
1766
1767/** prints pseudoboolean constraint in CIP format to file stream */
1768static
1770 SCIP*const scip, /**< SCIP data structure */
1771 SCIP_CONS*const cons, /**< pseudoboolean constraint */
1772 FILE*const file /**< output file (or NULL for standard output) */
1773 )
1774{
1775 SCIP_CONSHDLR* conshdlr;
1776 SCIP_CONSHDLRDATA* conshdlrdata;
1777 SCIP_CONSDATA* consdata;
1778 SCIP_VAR** vars;
1779 SCIP_Real* coefs;
1780 SCIP_Real lhs;
1781 SCIP_Real rhs;
1782 SCIP_Bool printed;
1783 int nvars;
1784 int v;
1785
1786 assert(scip != NULL);
1787 assert(cons != NULL);
1788
1789#ifdef WITHEQKNAPSACK
1790 if( SCIPconsIsDeleted(cons) )
1791 return SCIP_OKAY;
1792#endif
1793
1794 consdata = SCIPconsGetData(cons);
1795 assert(consdata != NULL);
1796 assert(consdata->lincons != NULL);
1797 /* more than one and-constraint is needed, otherwise this pseudoboolean constraint should be upgraded to a linear constraint */
1798 assert(consdata->nconsanddatas >= 0);
1799
1800 /* gets number of variables in linear constraint */
1801 SCIP_CALL( getLinearConsNVars(scip, consdata->lincons, consdata->linconstype, &nvars) );
1802
1803 /* allocate temporary memory */
1804 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1805 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
1806
1807 /* get sides of linear constraint */
1808 SCIP_CALL( getLinearConsSides(scip, consdata->lincons, consdata->linconstype, &lhs, &rhs) );
1809 assert(!SCIPisInfinity(scip, lhs));
1810 assert(!SCIPisInfinity(scip, -rhs));
1811 assert(SCIPisLE(scip, lhs, rhs));
1812
1813 /* get variables and coefficient of linear constraint */
1814 SCIP_CALL( getLinearConsVarsData(scip, consdata->lincons, consdata->linconstype, vars, coefs, &nvars) );
1815 assert(nvars == 0 || (coefs != NULL));
1816
1817 /* number of variables should be consistent, number of 'real' linear variables plus number of and-constraints should
1818 * have to be equal to the number of variables in the linear constraint
1819 */
1820 assert(consdata->nlinvars + consdata->nconsanddatas == nvars);
1821
1822 /* print left hand side for ranged rows */
1823 if( !SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, rhs) && !SCIPisEQ(scip, lhs, rhs) )
1824 SCIPinfoMessage(scip, file, "%.15g <= ", lhs);
1825
1826 conshdlr = SCIPconsGetHdlr(cons);
1827 assert(conshdlr != NULL);
1828
1829 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1830 assert(conshdlrdata != NULL);
1831 assert(conshdlrdata->hashmap != NULL);
1832
1833 printed = FALSE;
1834
1835 /* print all terms */
1836 for( v = 0; v < nvars; ++v )
1837 {
1838 CONSANDDATA* consanddata = NULL;
1839 SCIP_VAR** andvars = NULL;
1840 SCIP_VAR* var = vars[v];
1841 int nandvars = 0;
1842
1843 assert(SCIPvarIsBinary(var));
1844
1845 if( !SCIPconsIsOriginal(cons) )
1846 {
1847 /* if the and resultant was fixed we print a constant */
1849 {
1850 if( SCIPvarGetLbGlobal(var) > 0.5 )
1851 {
1852 printed = TRUE;
1853 SCIPinfoMessage(scip, file, " %+.15g ", coefs[v]);
1854 }
1855 continue;
1856 }
1858 {
1859 SCIP_VAR* aggrvar;
1860 SCIP_Bool negated;
1861
1862 SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &aggrvar, &negated) );
1863 assert(aggrvar != NULL);
1864 assert(SCIPvarGetType(aggrvar) == SCIP_VARTYPE_BINARY);
1865
1866 printed = TRUE;
1867 SCIPinfoMessage(scip, file, " %+.15g %s<%s>[B]", coefs[v], negated ? "~" : "", SCIPvarGetName(aggrvar));
1868
1869 continue;
1870 }
1871 }
1872
1873 /* find and-constraint to standard or negated and-resultant */
1874 do
1875 {
1876 consanddata = (CONSANDDATA*)SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)var);
1877
1878 if( consanddata != NULL )
1879 {
1880 SCIP_CONS* andcons;
1881
1882 if( SCIPconsIsOriginal(cons) )
1883 andcons = consanddata->origcons;
1884 else
1885 andcons = consanddata->cons;
1886 assert(andcons != NULL);
1887
1888 andvars = SCIPgetVarsAnd(scip, andcons);
1889 nandvars = SCIPgetNVarsAnd(scip, andcons);
1890 assert(nandvars == 0 || andvars != NULL);
1891
1892 break;
1893 }
1894
1895 if( var == vars[v] )
1896 var = SCIPvarGetNegatedVar(var);
1897 else
1898 var = vars[v];
1899 }
1900 while( var != vars[v] );
1901
1902 /* print general coefficient */
1903 if( consanddata != NULL && nandvars == 0 )
1904 {
1905 if( var == vars[v] )
1906 {
1907 printed = TRUE;
1908 SCIPinfoMessage(scip, file, " %+.15g ", coefs[v]);
1909 }
1910 continue;
1911 }
1912 else if( coefs[v] == 1.0 )
1913 {
1914 if( v > 0 )
1915 SCIPinfoMessage(scip, file, " +");
1916 }
1917 else if( coefs[v] == -1.0 )
1918 SCIPinfoMessage(scip, file, " -");
1919 else
1920 SCIPinfoMessage(scip, file, " %+.15g", coefs[v]);
1921
1922 printed = TRUE;
1923
1924 /* print linear term */
1925 if( consanddata == NULL )
1926 {
1927 SCIP_CALL( SCIPwriteVarName(scip, file, var, TRUE) );
1928 }
1929 /* print non-linear term */
1930 else
1931 {
1932 SCIPinfoMessage(scip, file, "%s(", var == vars[v] ? "" : "~");
1933
1934 /* @todo: better write new method SCIPwriteProduct */
1935 /* print variable list */
1936 SCIP_CALL( SCIPwriteVarsList(scip, file, andvars, nandvars, TRUE, '*') );
1937
1938 SCIPinfoMessage(scip, file, ")");
1939 }
1940 }
1941
1942 /* print zero value */
1943 if( !printed )
1944 {
1945 SCIPinfoMessage(scip, file, " 0 ");
1946 }
1947
1948 /* free temporary memory */
1949 SCIPfreeBufferArray(scip, &coefs);
1950 SCIPfreeBufferArray(scip, &vars);
1951
1952 /* print right hand side */
1953 if( SCIPisEQ(scip, lhs, rhs) )
1954 SCIPinfoMessage(scip, file, " == %.15g", rhs);
1955 else if( !SCIPisInfinity(scip, rhs) )
1956 SCIPinfoMessage(scip, file, " <= %.15g", rhs);
1957 else if( !SCIPisInfinity(scip, -lhs) )
1958 SCIPinfoMessage(scip, file, " >= %.15g", lhs);
1959 else
1960 SCIPinfoMessage(scip, file, " [free]");
1961
1962 return SCIP_OKAY;
1963}
1964
1965/** creates and/or adds the resultant for a given term */
1966static
1968 SCIP*const scip, /**< SCIP data structure */
1969 SCIP_CONSHDLR*const conshdlr, /**< pseudoboolean constraint handler */
1970 SCIP_VAR**const vars, /**< array of variables to get and-constraints for */
1971 int const nvars, /**< number of variables to get and-constraints for */
1972 SCIP_Bool const initial, /**< should the LP relaxation of constraint be in the initial LP?
1973 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1974 SCIP_Bool const enforce, /**< should the constraint be enforced during node processing?
1975 * TRUE for model constraints, FALSE for additional, redundant
1976 * constraints. */
1977 SCIP_Bool const check, /**< should the constraint be checked for feasibility?
1978 * TRUE for model constraints, FALSE for additional, redundant
1979 * constraints. */
1980 SCIP_Bool const local, /**< is constraint only valid locally?
1981 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching
1982 * constraints. */
1983 SCIP_Bool const modifiable, /**< is constraint modifiable (subject to column generation)?
1984 * Usually set to FALSE. In column generation applications, set to TRUE
1985 * if pricing adds coefficients to this constraint. */
1986 SCIP_Bool const dynamic, /**< is constraint subject to aging?
1987 * Usually set to FALSE. Set to TRUE for own cuts which
1988 * are seperated as constraints. */
1989 SCIP_Bool const stickingatnode, /**< should the constraint always be kept at the node where it was added, even
1990 * if it may be moved to a more global node?
1991 * Usually set to FALSE. Set to TRUE to for constraints that represent
1992 * node data. */
1993 SCIP_CONS**const andcons /**< pointer to store and-constraint */
1994 )
1995{
1996 CONSANDDATA* newdata;
1997 CONSANDDATA* tmpdata;
1998 SCIP_CONSHDLRDATA* conshdlrdata;
1999 char name[SCIP_MAXSTRLEN];
2000 SCIP_Bool separate;
2001 SCIP_Bool propagate;
2002 SCIP_Bool removable;
2003 SCIP_Bool transformed;
2004
2005 assert(scip != NULL);
2006 assert(conshdlr != NULL);
2007 assert(vars != NULL);
2008 assert(nvars > 0);
2009 assert(andcons != NULL);
2010
2011 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2012 assert(conshdlrdata != NULL);
2013 assert(conshdlrdata->hashtable != NULL);
2014
2015 transformed = SCIPisTransformed(scip);
2016
2017 /* allocate memory for a possible new consanddata object */
2018 SCIP_CALL( SCIPallocBlockMemory(scip, &newdata) );
2019 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(newdata->vars), vars, nvars) );
2020 newdata->nvars = nvars;
2021 newdata->svars = nvars;
2022 newdata->newvars = NULL;
2023 newdata->nnewvars = 0;
2024 newdata->snewvars = 0;
2025 newdata->noriguses = 0;
2026 newdata->nuses = 0;
2027 newdata->istransformed = transformed;
2028 newdata->isoriginal = !transformed;
2029 newdata->cons = NULL;
2030 newdata->origcons = NULL;
2031
2032 /* sort variables */
2033 SCIPsortPtr((void**)(newdata->vars), SCIPvarComp, nvars);
2034
2035 /* get constraint from current hash table with same variables as cons0 */
2036 tmpdata = (CONSANDDATA*)(SCIPhashtableRetrieve(conshdlrdata->hashtable, (void*)newdata));
2037
2038 /* if there is already the same and constraint created use this resultant */
2039 if( tmpdata != NULL )
2040 {
2041#ifndef NDEBUG
2042 SCIP_VAR* res;
2043#endif
2044 if( transformed )
2045 {
2046 assert(tmpdata->cons != NULL);
2047 *andcons = tmpdata->cons;
2048
2049 assert(tmpdata->nuses > 0);
2050 /* increase usage of data object */
2051 ++(tmpdata->nuses);
2052 }
2053 else
2054 {
2055 assert(tmpdata->origcons != NULL);
2056 *andcons = tmpdata->origcons;
2057
2058 assert(tmpdata->noriguses > 0);
2059 /* increase usage of data object */
2060 ++(tmpdata->noriguses);
2061 }
2062 assert(*andcons != NULL);
2063
2064#ifndef NDEBUG
2065 res = SCIPgetResultantAnd(scip, *andcons);
2066 assert(res != NULL);
2067
2068 /* check that we already have added this resultant to and-constraint entry */
2069 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)res));
2070#endif
2071 }
2072 else
2073 {
2074 /* create new and-constraint */
2075 SCIP_CONS* newcons;
2076 SCIP_VAR* resultant;
2077
2078 /* create auxiliary variable */
2079 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, ARTIFICIALVARNAMEPREFIX"%d", conshdlrdata->nallconsanddatas);
2080 SCIP_CALL( SCIPcreateVar(scip, &resultant, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
2081 TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) );
2082
2083#if 1 /* @todo: check whether we want to branch on artificial variables, the test results show that it is of advantage */
2084 /* change branching priority of artificial variable to -1 */
2085 SCIP_CALL( SCIPchgVarBranchPriority(scip, resultant, -1) );
2086#endif
2087
2088 /* add auxiliary variable to the problem */
2089 SCIP_CALL( SCIPaddVar(scip, resultant) );
2090
2091#if 0 /* does not work for since the value of artificial resultants must not be equal to the value computed by their
2092 * product, since these variables are irrelevant */
2093#ifdef WITH_DEBUG_SOLUTION
2094 if( SCIPdebugIsMainscip(scip) )
2095 {
2096 SCIP_Real val;
2097 SCIP_Real debugsolval;
2098 int v;
2099
2100 for( v = nvars - 1; v >= 0; --v )
2101 {
2102 SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &val) );
2103 assert(SCIPisFeasZero(scip, val) || SCIPisFeasEQ(scip, val, 1.0));
2104
2105 if( val < 0.5 )
2106 break;
2107 }
2108 val = ((val < 0.5) ? 0.0 : 1.0);
2109
2110 SCIP_CALL( SCIPdebugGetSolVal(scip, resultant, &debugsolval) );
2111 if( (SCIPvarIsOriginal(resultant) || SCIPvarIsTransformedOrigvar(resultant)) && !SCIPisFeasEQ(scip, debugsolval, val) )
2112 {
2113 SCIPerrorMessage("computed solution value %g for resultant <%s> violates debug solution value %g\n", val, SCIPvarGetName(resultant), debugsolval);
2114 SCIPABORT();
2115 return SCIP_ERROR; /*lint !e527*/
2116 }
2117 else if( !SCIPvarIsOriginal(resultant) && !SCIPvarIsTransformedOrigvar(resultant) )
2118 {
2119 SCIP_CALL( SCIPdebugAddSolVal(scip, resultant, val) );
2120 }
2121 }
2122#endif
2123#endif
2124
2125 SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/nlcseparate", &separate) );
2126 SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/nlcpropagate", &propagate) );
2127 SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/nlcremovable", &removable) );
2128
2129 /* we do not want to check the and constraints, so the check flag will be FALSE */
2130
2131 /* create and add "and" constraint for the multiplication of the binary variables */
2132 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "andcons_%d", conshdlrdata->nallconsanddatas);
2133 SCIP_CALL( SCIPcreateConsAnd(scip, &newcons, name, resultant, newdata->nvars, newdata->vars,
2134 initial, separate, enforce, check && FALSE, propagate,
2135 local, modifiable, dynamic, removable, stickingatnode) ); /*lint !e506*/
2136 SCIP_CALL( SCIPaddCons(scip, newcons) );
2137 SCIPdebugPrintCons(scip, newcons, NULL);
2138
2139 /* force all deriving constraint from this and constraint to be checked and not removable */
2142
2143 *andcons = newcons;
2144 assert(*andcons != NULL);
2145
2146 /* resize data for all and-constraints if necessary */
2147 if( conshdlrdata->nallconsanddatas == conshdlrdata->sallconsanddatas )
2148 {
2149 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &(conshdlrdata->allconsanddatas), &(conshdlrdata->sallconsanddatas), SCIPcalcMemGrowSize(scip, conshdlrdata->sallconsanddatas + 1)) );
2150 }
2151
2152 /* add new data object to global hash table */
2153 conshdlrdata->allconsanddatas[conshdlrdata->nallconsanddatas] = newdata;
2154 ++(conshdlrdata->nallconsanddatas);
2155
2156 if( transformed )
2157 {
2158 int v;
2159
2160 newdata->cons = newcons;
2161 SCIP_CALL( SCIPcaptureCons(scip, newdata->cons) );
2162
2163 /* initialize usage of data object */
2164 newdata->nuses = 1;
2165
2166 /* capture all variables */
2167 for( v = newdata->nvars - 1; v >= 0; --v )
2168 {
2169 SCIP_CALL( SCIPcaptureVar(scip, newdata->vars[v]) ); /*lint !e613*/
2170 }
2171 }
2172 else
2173 {
2174 newdata->origcons = newcons;
2175 SCIP_CALL( SCIPcaptureCons(scip, newdata->origcons) );
2176
2177 /* initialize usage of data object */
2178 newdata->noriguses = 1;
2179 }
2180
2181 /* no such and-constraint in current hash table: insert the new object into hash table */
2182 SCIP_CALL( SCIPhashtableInsert(conshdlrdata->hashtable, (void*)newdata) );
2183
2184 /* insert new mapping */
2185 assert(!SCIPhashmapExists(conshdlrdata->hashmap, (void*)resultant));
2186 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->hashmap, (void*)resultant, (void*)newdata) );
2187
2188 /* release and-resultant and -constraint */
2189 SCIP_CALL( SCIPreleaseVar(scip, &resultant) );
2190 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
2191
2192 return SCIP_OKAY;
2193 }
2194
2195 /* free memory */
2196 SCIPfreeBlockMemoryArray(scip, &(newdata->vars), newdata->svars);
2197 SCIPfreeBlockMemory(scip, &newdata);
2198
2199 return SCIP_OKAY;
2200}
2201
2202/** adds a term to the given pseudoboolean constraint */
2203static
2205 SCIP*const scip, /**< SCIP data structure */
2206 SCIP_CONS*const cons, /**< pseudoboolean constraint */
2207 SCIP_VAR**const vars, /**< variables of the nonlinear term */
2208 int const nvars, /**< number of variables of the nonlinear term */
2209 SCIP_Real const val /**< coefficient of constraint entry */
2210 )
2211{
2212 SCIP_CONSHDLR* conshdlr;
2213 SCIP_CONSHDLRDATA* conshdlrdata;
2214 SCIP_CONS* andcons;
2215 SCIP_CONSDATA* consdata;
2216 SCIP_VAR* res;
2217
2218 assert(scip != NULL);
2219 assert(cons != NULL);
2220 assert(nvars == 0 || vars != NULL);
2221
2222 if( nvars == 0 || SCIPisZero(scip, val) )
2223 return SCIP_OKAY;
2224
2225 consdata = SCIPconsGetData(cons);
2226 assert(consdata != NULL);
2227
2228 conshdlr = SCIPconsGetHdlr(cons);
2229 assert(conshdlr != NULL);
2230
2231 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2232 assert(conshdlrdata != NULL);
2233
2234 /* create (and add) and-constraint */
2235 SCIP_CALL( createAndAddAndCons(scip, conshdlr, vars, nvars,
2238 &andcons) );
2239 assert(andcons != NULL);
2240
2241 /* ensure memory size */
2242 if( consdata->nconsanddatas == consdata->sconsanddatas )
2243 {
2244 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &(consdata->consanddatas), &(consdata->sconsanddatas), consdata->sconsanddatas + 1) );
2245 }
2246
2247 res = SCIPgetResultantAnd(scip, andcons);
2248 assert(res != NULL);
2249 assert(SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)res) != NULL);
2250
2251 consdata->consanddatas[consdata->nconsanddatas] = (CONSANDDATA*) SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)res);
2252 ++(consdata->nconsanddatas);
2253
2254 /* add auxiliary variables to linear constraint */
2255 switch( consdata->linconstype )
2256 {
2258 SCIP_CALL( SCIPaddCoefLinear(scip, consdata->lincons, res, val) );
2259 break;
2261 if( !SCIPisEQ(scip, val, 1.0) )
2262 return SCIP_INVALIDDATA;
2263
2264 SCIP_CALL( SCIPaddCoefLogicor(scip, consdata->lincons, res) );
2265 break;
2267 if( !SCIPisIntegral(scip, val) || !SCIPisPositive(scip, val) )
2268 return SCIP_INVALIDDATA;
2269
2270 SCIP_CALL( SCIPaddCoefKnapsack(scip, consdata->lincons, res, (SCIP_Longint) val) );
2271 break;
2273 if( !SCIPisEQ(scip, val, 1.0) )
2274 return SCIP_INVALIDDATA;
2275
2276 SCIP_CALL( SCIPaddCoefSetppc(scip, consdata->lincons, res) );
2277 break;
2278#ifdef WITHEQKNAPSACK
2279 case SCIP_LINEARCONSTYPE_EQKNAPSACK:
2280 if( !SCIPisIntegral(scip, val) || !SCIPisPositive(scip, val) )
2281 return SCIP_INVALIDDATA;
2282
2283 SCIP_CALL( SCIPaddCoefEQKnapsack(scip, consdata->lincons, res, (SCIP_Longint) val) );
2284 break;
2285#endif
2287 default:
2288 SCIPerrorMessage("unknown linear constraint type\n");
2289 return SCIP_INVALIDDATA;
2290 }
2291
2292 /* install rounding locks for all new variable */
2293 SCIP_CALL( lockRoundingAndCons(scip, cons, consdata->consanddatas[consdata->nconsanddatas - 1], val, consdata->lhs, consdata->rhs) );
2294
2295 /* change flags */
2296 consdata->changed = TRUE;
2297 consdata->propagated = FALSE;
2298 consdata->presolved = FALSE;
2299 consdata->cliquesadded = FALSE;
2300 consdata->upgradetried = FALSE;
2301
2302 return SCIP_OKAY;
2303}
2304
2305/** changes left hand side of linear constraint */
2306static
2308 SCIP*const scip, /**< SCIP data structure */
2309 SCIP_CONS*const cons, /**< linear constraint */
2310 SCIP_LINEARCONSTYPE const constype, /**< linear constraint type */
2311 SCIP_Real const lhs /**< new left hand side of linear constraint */
2312 )
2313{
2314 switch( constype )
2315 {
2317 SCIP_CALL( SCIPchgLhsLinear(scip, cons, lhs) );
2318 break;
2322 SCIPerrorMessage("changing left hand side only allowed on standard lienar constraint \n");
2323 return SCIP_INVALIDDATA;
2324#ifdef WITHEQKNAPSACK
2325 case SCIP_LINEARCONSTYPE_EQKNAPSACK:
2326#endif
2328 default:
2329 SCIPerrorMessage("unknown linear constraint type\n");
2330 return SCIP_INVALIDDATA;
2331 }
2332
2333 return SCIP_OKAY;
2334}
2335
2336/** changes right hand side of linear constraint */
2337static
2339 SCIP*const scip, /**< SCIP data structure */
2340 SCIP_CONS*const cons, /**< linear constraint */
2341 SCIP_LINEARCONSTYPE const constype, /**< linear constraint type */
2342 SCIP_Real const rhs /**< new right hand side of linear constraint */
2343 )
2344{
2345 switch( constype )
2346 {
2348 SCIP_CALL( SCIPchgRhsLinear(scip, cons, rhs) );
2349 break;
2353 SCIPerrorMessage("changing left hand side only allowed on standard lienar constraint \n");
2354 return SCIP_INVALIDDATA;
2355#ifdef WITHEQKNAPSACK
2356 case SCIP_LINEARCONSTYPE_EQKNAPSACK:
2357#endif
2359 default:
2360 SCIPerrorMessage("unknown linear constraint type\n");
2361 return SCIP_INVALIDDATA;
2362 }
2363
2364 return SCIP_OKAY;
2365}
2366
2367/** sets left hand side of linear constraint */
2368static
2370 SCIP*const scip, /**< SCIP data structure */
2371 SCIP_CONS*const cons, /**< linear constraint */
2372 SCIP_Real lhs /**< new left hand side */
2373 )
2374{
2375 SCIP_CONSDATA* consdata;
2376 SCIP_VAR** vars;
2377 SCIP_Real* coefs;
2378 int nvars;
2379 SCIP_VAR** linvars;
2380 SCIP_Real* lincoefs;
2381 int nlinvars;
2382 SCIP_VAR** andress;
2383 SCIP_Real* andcoefs;
2384 SCIP_Bool* andnegs;
2385 int nandress;
2386 SCIP_Real oldlhs;
2387 SCIP_Real oldrhs;
2388
2389 assert(scip != NULL);
2390 assert(cons != NULL);
2392 assert(!SCIPisInfinity(scip, lhs));
2393
2394 /* adjust value to not be smaller than -inf */
2395 if ( SCIPisInfinity(scip, -lhs) )
2396 lhs = -SCIPinfinity(scip);
2397
2398 consdata = SCIPconsGetData(cons);
2399 assert(consdata != NULL);
2400
2401 /* get sides of linear constraint */
2402 SCIP_CALL( getLinearConsSides(scip, consdata->lincons, consdata->linconstype, &oldlhs, &oldrhs) );
2403 assert(!SCIPisInfinity(scip, oldlhs));
2404 assert(!SCIPisInfinity(scip, -oldrhs));
2405 assert(SCIPisLE(scip, oldlhs, oldrhs));
2406
2407 /* check whether the side is not changed */
2408 if( SCIPisEQ(scip, oldlhs, lhs) )
2409 return SCIP_OKAY;
2410
2411 /* gets number of variables in linear constraint */
2412 SCIP_CALL( getLinearConsNVars(scip, consdata->lincons, consdata->linconstype, &nvars) );
2413
2414 /* allocate temporary memory */
2415 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2416 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
2417 SCIP_CALL( SCIPallocBufferArray(scip, &linvars, nvars) );
2418 SCIP_CALL( SCIPallocBufferArray(scip, &lincoefs, nvars) );
2419 SCIP_CALL( SCIPallocBufferArray(scip, &andress, nvars) );
2420 SCIP_CALL( SCIPallocBufferArray(scip, &andcoefs, nvars) );
2421 SCIP_CALL( SCIPallocBufferArray(scip, &andnegs, nvars) );
2422
2423 /* get variables and coefficient of linear constraint */
2424 SCIP_CALL( getLinearConsVarsData(scip, consdata->lincons, consdata->linconstype, vars, coefs, &nvars) );
2425 assert(nvars == 0 || (coefs != NULL));
2426
2427 /* calculate all not artificial linear variables and all artificial and-resultants */
2428 SCIP_CALL( getLinVarsAndAndRess(scip, cons, vars, coefs, nvars, linvars, lincoefs, &nlinvars, andress, andcoefs, andnegs, &nandress) );
2429 assert(consdata->nconsanddatas == nandress);
2430
2431 /* if necessary, update the rounding locks of variables */
2432 if( SCIPconsIsLocked(cons) )
2433 {
2434 SCIP_VAR** andvars;
2435 int nandvars;
2436 SCIP_Real val;
2437 int v;
2438 int c;
2439
2440 assert(SCIPconsIsTransformed(cons));
2441
2442 if( SCIPisInfinity(scip, -oldlhs) && !SCIPisInfinity(scip, -lhs) )
2443 {
2444 /* non-linear part */
2445 for( c = consdata->nconsanddatas - 1; c >= 0; --c )
2446 {
2447 CONSANDDATA* consanddata;
2448 SCIP_CONS* andcons;
2449
2450 consanddata = consdata->consanddatas[c];
2451 assert(consanddata != NULL);
2452
2453 andcons = consanddata->cons;
2454 assert(andcons != NULL);
2455
2456 andvars = SCIPgetVarsAnd(scip, andcons);
2457 nandvars = SCIPgetNVarsAnd(scip, andcons);
2458 val = andnegs[c] ? -andcoefs[c] : andcoefs[c];
2459
2460 /* lock variables */
2461 if( SCIPisPositive(scip, val) )
2462 {
2463 for( v = nandvars - 1; v >= 0; --v )
2464 {
2465 SCIP_CALL( SCIPlockVarCons(scip, andvars[v], cons, TRUE, FALSE) );
2466 }
2467 }
2468 else
2469 {
2470 for( v = nandvars - 1; v >= 0; --v )
2471 {
2472 SCIP_CALL( SCIPlockVarCons(scip, andvars[v], cons, FALSE, TRUE) );
2473 }
2474 }
2475 }
2476 }
2477 else if( !SCIPisInfinity(scip, -oldlhs) && SCIPisInfinity(scip, -lhs) )
2478 {
2479 /* non-linear part */
2480 for( c = consdata->nconsanddatas - 1; c >= 0; --c )
2481 {
2482 CONSANDDATA* consanddata;
2483 SCIP_CONS* andcons;
2484
2485 consanddata = consdata->consanddatas[c];
2486 assert(consanddata != NULL);
2487
2488 andcons = consanddata->cons;
2489 assert(andcons != NULL);
2490
2491 andvars = SCIPgetVarsAnd(scip, andcons);
2492 nandvars = SCIPgetNVarsAnd(scip, andcons);
2493 val = andnegs[c] ? -andcoefs[c] : andcoefs[c];
2494
2495 /* lock variables */
2496 if( SCIPisPositive(scip, val) )
2497 {
2498 for( v = nandvars - 1; v >= 0; --v )
2499 {
2500 SCIP_CALL( SCIPunlockVarCons(scip, andvars[v], cons, TRUE, FALSE) );
2501 }
2502 }
2503 else
2504 {
2505 for( v = nandvars - 1; v >= 0; --v )
2506 {
2507 SCIP_CALL( SCIPunlockVarCons(scip, andvars[v], cons, FALSE, TRUE) );
2508 }
2509 }
2510 }
2511 }
2512 }
2513
2514 /* check whether the left hand side is increased, if and only if that's the case we maybe can propagate, tighten and add more cliques */
2515 if( SCIPisLT(scip, oldlhs, lhs) )
2516 {
2517 consdata->propagated = FALSE;
2518 }
2519
2520 /* set new left hand side and update constraint data */
2521 SCIP_CALL( chgLhsLinearCons(scip, consdata->lincons, consdata->linconstype, lhs) );
2522 consdata->lhs = lhs;
2523 consdata->presolved = FALSE;
2524 consdata->changed = TRUE;
2525
2526 /* free temporary memory */
2527 SCIPfreeBufferArray(scip, &andnegs);
2528 SCIPfreeBufferArray(scip, &andcoefs);
2529 SCIPfreeBufferArray(scip, &andress);
2530 SCIPfreeBufferArray(scip, &lincoefs);
2531 SCIPfreeBufferArray(scip, &linvars);
2532 SCIPfreeBufferArray(scip, &coefs);
2533 SCIPfreeBufferArray(scip, &vars);
2534
2535 return SCIP_OKAY;
2536}
2537
2538/** sets right hand side of pseudoboolean constraint */
2539static
2541 SCIP*const scip, /**< SCIP data structure */
2542 SCIP_CONS*const cons, /**< linear constraint */
2543 SCIP_Real rhs /**< new right hand side */
2544 )
2545{
2546 SCIP_CONSDATA* consdata;
2547 SCIP_VAR** vars;
2548 SCIP_Real* coefs;
2549 int nvars;
2550 SCIP_VAR** linvars;
2551 SCIP_Real* lincoefs;
2552 int nlinvars;
2553 SCIP_VAR** andress;
2554 SCIP_Real* andcoefs;
2555 SCIP_Bool* andnegs;
2556 int nandress;
2557 SCIP_Real oldlhs;
2558 SCIP_Real oldrhs;
2559
2560 assert(scip != NULL);
2561 assert(cons != NULL);
2563 assert(!SCIPisInfinity(scip, -rhs));
2564
2565 /* adjust value to not be larger than inf */
2566 if( SCIPisInfinity(scip, rhs) )
2567 rhs = SCIPinfinity(scip);
2568
2569 consdata = SCIPconsGetData(cons);
2570 assert(consdata != NULL);
2571
2572 /* get sides of linear constraint */
2573 SCIP_CALL( getLinearConsSides(scip, consdata->lincons, consdata->linconstype, &oldlhs, &oldrhs) );
2574 assert(!SCIPisInfinity(scip, oldlhs));
2575 assert(!SCIPisInfinity(scip, -oldrhs));
2576 assert(SCIPisLE(scip, oldlhs, oldrhs));
2577
2578 /* check whether the side is not changed */
2579 if( SCIPisEQ(scip, oldrhs, rhs) )
2580 return SCIP_OKAY;
2581
2582 /* gets number of variables in linear constraint */
2583 SCIP_CALL( getLinearConsNVars(scip, consdata->lincons, consdata->linconstype, &nvars) );
2584
2585 /* allocate temporary memory */
2586 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2587 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
2588 SCIP_CALL( SCIPallocBufferArray(scip, &linvars, nvars) );
2589 SCIP_CALL( SCIPallocBufferArray(scip, &lincoefs, nvars) );
2590 SCIP_CALL( SCIPallocBufferArray(scip, &andress, nvars) );
2591 SCIP_CALL( SCIPallocBufferArray(scip, &andcoefs, nvars) );
2592 SCIP_CALL( SCIPallocBufferArray(scip, &andnegs, nvars) );
2593
2594 /* get variables and coefficient of linear constraint */
2595 SCIP_CALL( getLinearConsVarsData(scip, consdata->lincons, consdata->linconstype, vars, coefs, &nvars) );
2596 assert(nvars == 0 || (coefs != NULL));
2597
2598 /* calculate all not artificial linear variables and all artificial and-resultants */
2599 SCIP_CALL( getLinVarsAndAndRess(scip, cons, vars, coefs, nvars, linvars, lincoefs, &nlinvars, andress, andcoefs, andnegs, &nandress) );
2600 assert(consdata->nconsanddatas == nandress);
2601
2602 /* if necessary, update the rounding locks of variables */
2603 if( SCIPconsIsLocked(cons) )
2604 {
2605 SCIP_VAR** andvars;
2606 int nandvars;
2607 SCIP_Real val;
2608 int v;
2609 int c;
2610
2611 assert(SCIPconsIsTransformed(cons));
2612
2613 if( SCIPisInfinity(scip, oldrhs) && !SCIPisInfinity(scip, rhs) )
2614 {
2615 /* non-linear part */
2616 for( c = consdata->nconsanddatas - 1; c >= 0; --c )
2617 {
2618 CONSANDDATA* consanddata;
2619 SCIP_CONS* andcons;
2620
2621 consanddata = consdata->consanddatas[c];
2622 assert(consanddata != NULL);
2623
2624 andcons = consanddata->cons;
2625 assert(andcons != NULL);
2626
2627 andvars = SCIPgetVarsAnd(scip, andcons);
2628 nandvars = SCIPgetNVarsAnd(scip, andcons);
2629 val = andnegs[c] ? -andcoefs[c] : andcoefs[c];
2630
2631 /* lock variables */
2632 if( SCIPisPositive(scip, val) )
2633 {
2634 for( v = nandvars - 1; v >= 0; --v )
2635 {
2636 SCIP_CALL( SCIPlockVarCons(scip, andvars[v], cons, FALSE, TRUE) );
2637 }
2638 }
2639 else
2640 {
2641 for( v = nandvars - 1; v >= 0; --v )
2642 {
2643 SCIP_CALL( SCIPlockVarCons(scip, andvars[v], cons, TRUE, FALSE) );
2644 }
2645 }
2646 }
2647 }
2648 else if( !SCIPisInfinity(scip, oldrhs) && SCIPisInfinity(scip, rhs) )
2649 {
2650 /* non-linear part */
2651 for( c = consdata->nconsanddatas - 1; c >= 0; --c )
2652 {
2653 CONSANDDATA* consanddata;
2654 SCIP_CONS* andcons;
2655
2656 consanddata = consdata->consanddatas[c];
2657 assert(consanddata != NULL);
2658
2659 andcons = consanddata->cons;
2660 assert(andcons != NULL);
2661
2662 andvars = SCIPgetVarsAnd(scip, andcons);
2663 nandvars = SCIPgetNVarsAnd(scip, andcons);
2664 val = andnegs[c] ? -andcoefs[c] : andcoefs[c];
2665
2666 /* lock variables */
2667 if( SCIPisPositive(scip, val) )
2668 {
2669 for( v = nandvars - 1; v >= 0; --v )
2670 {
2671 SCIP_CALL( SCIPunlockVarCons(scip, andvars[v], cons, FALSE, TRUE) );
2672 }
2673 }
2674 else
2675 {
2676 for( v = nandvars - 1; v >= 0; --v )
2677 {
2678 SCIP_CALL( SCIPunlockVarCons(scip, andvars[v], cons, TRUE, FALSE) );
2679 }
2680 }
2681 }
2682 }
2683 }
2684
2685 /* check whether the right hand side is decreased, if and only if that's the case we maybe can propagate, tighten and add more cliques */
2686 if( SCIPisGT(scip, oldrhs, rhs) )
2687 {
2688 consdata->propagated = FALSE;
2689 }
2690
2691 /* set new right hand side and update constraint data */
2692 SCIP_CALL( chgRhsLinearCons(scip, consdata->lincons, consdata->linconstype, rhs) );
2693 consdata->rhs = rhs;
2694 consdata->presolved = FALSE;
2695 consdata->changed = TRUE;
2696
2697 /* free temporary memory */
2698 SCIPfreeBufferArray(scip, &andnegs);
2699 SCIPfreeBufferArray(scip, &andcoefs);
2700 SCIPfreeBufferArray(scip, &andress);
2701 SCIPfreeBufferArray(scip, &lincoefs);
2702 SCIPfreeBufferArray(scip, &linvars);
2703 SCIPfreeBufferArray(scip, &coefs);
2704 SCIPfreeBufferArray(scip, &vars);
2705
2706 return SCIP_OKAY;
2707}
2708
2709/** create and-constraints and get all and-resultants */
2710static
2712 SCIP*const scip, /**< SCIP data structure */
2713 SCIP_CONSHDLR*const conshdlr, /**< pseudoboolean constraint handler */
2714 SCIP_VAR**const*const terms, /**< array of term variables to get and-constraints for */
2715 SCIP_Real*const termcoefs, /**< array of coefficients for and-constraints */
2716 int const nterms, /**< number of terms to get and-constraints for */
2717 int const*const ntermvars, /**< array of number of variable in each term */
2718 SCIP_Bool const initial, /**< should the LP relaxation of constraint be in the initial LP?
2719 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2720 SCIP_Bool const enforce, /**< should the constraint be enforced during node processing?
2721 * TRUE for model constraints, FALSE for additional, redundant
2722 * constraints. */
2723 SCIP_Bool const check, /**< should the constraint be checked for feasibility?
2724 * TRUE for model constraints, FALSE for additional, redundant
2725 * constraints. */
2726 SCIP_Bool const local, /**< is constraint only valid locally?
2727 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching
2728 * constraints. */
2729 SCIP_Bool const modifiable, /**< is constraint modifiable (subject to column generation)?
2730 * Usually set to FALSE. In column generation applications, set to TRUE
2731 * if pricing adds coefficients to this constraint. */
2732 SCIP_Bool const dynamic, /**< is constraint subject to aging?
2733 * Usually set to FALSE. Set to TRUE for own cuts which
2734 * are seperated as constraints. */
2735 SCIP_Bool const stickingatnode, /**< should the constraint always be kept at the node where it was added, even
2736 * if it may be moved to a more global node?
2737 * Usually set to FALSE. Set to TRUE to for constraints that represent
2738 * node data. */
2739 SCIP_CONS**const andconss, /**< array to store all created and-constraints for given terms */
2740 SCIP_Real*const andvals, /**< array to store all coefficients of and-constraints */
2741 SCIP_Bool*const andnegs, /**< array to store negation status of and-constraints */
2742 int*const nandconss /**< number of created and constraints */
2743 )
2744{
2745 int t;
2746
2747 assert(scip != NULL);
2748 assert(conshdlr != NULL);
2749 assert(nterms == 0 || (terms != NULL && ntermvars != NULL));
2750 assert(andconss != NULL);
2751 assert(andvals != NULL);
2752 assert(nandconss != NULL);
2753
2754 (*nandconss) = 0;
2755
2756 if( nterms == 0 )
2757 return SCIP_OKAY;
2758
2759 /* loop over all terms and create/get all and constraints */
2760 for( t = 0; t < nterms; ++t )
2761 {
2762 if( !SCIPisZero(scip, termcoefs[t]) && ntermvars[t] > 0 )
2763 {
2764 SCIP_CALL( createAndAddAndCons(scip, conshdlr, terms[t], ntermvars[t],
2765 initial, enforce, check, local, modifiable, dynamic, stickingatnode,
2766 &(andconss[*nandconss])) );
2767 assert(andconss[*nandconss] != NULL);
2768 andvals[*nandconss] = termcoefs[t];
2769 andnegs[*nandconss] = FALSE;
2770 ++(*nandconss);
2771 }
2772 }
2773
2774 return SCIP_OKAY;
2775}
2776
2777/** created linear constraint of pseudo boolean constraint */
2778static
2780 SCIP*const scip, /**< SCIP data structure */
2781 SCIP_CONSHDLR*const conshdlr, /**< pseudoboolean constraint handler */
2782 SCIP_VAR**const linvars, /**< linear variables */
2783 int const nlinvars, /**< number of linear variables */
2784 SCIP_Real*const linvals, /**< linear coefficients */
2785 SCIP_VAR**const andress, /**< and-resultant variables */
2786 int const nandress, /**< number of and-resultant variables */
2787 SCIP_Real const*const andvals, /**< and-resultant coefficients */
2788 SCIP_Bool*const andnegs, /**< and-resultant negation status */
2789 SCIP_Real*const lhs, /**< pointer to left hand side of linear constraint */
2790 SCIP_Real*const rhs, /**< pointer to right hand side of linear constraint */
2791 SCIP_Bool const initial, /**< should the LP relaxation of constraint be in the initial LP?
2792 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2793 SCIP_Bool const separate, /**< should the constraint be separated during LP processing?
2794 * Usually set to TRUE. */
2795 SCIP_Bool const enforce, /**< should the constraint be enforced during node processing?
2796 * TRUE for model constraints, FALSE for additional, redundant
2797 * constraints. */
2798 SCIP_Bool const check, /**< should the constraint be checked for feasibility?
2799 * TRUE for model constraints, FALSE for additional, redundant
2800 * constraints. */
2801 SCIP_Bool const propagate, /**< should the constraint be propagated during node processing?
2802 * Usually set to TRUE. */
2803 SCIP_Bool const local, /**< is constraint only valid locally?
2804 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching
2805 * constraints. */
2806 SCIP_Bool const modifiable, /**< is constraint modifiable (subject to column generation)?
2807 * Usually set to FALSE. In column generation applications, set to TRUE
2808 * if pricing adds coefficients to this constraint. */
2809 SCIP_Bool const dynamic, /**< is constraint subject to aging?
2810 * Usually set to FALSE. Set to TRUE for own cuts which
2811 * are seperated as constraints. */
2812 SCIP_Bool const removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2813 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user
2814 * cuts'. */
2815 SCIP_Bool const stickingatnode, /**< should the constraint always be kept at the node where it was added, even
2816 * if it may be moved to a more global node?
2817 * Usually set to FALSE. Set to TRUE to for constraints that represent
2818 * node data. */
2819 SCIP_CONS**const lincons, /**< pointer to store created linear constraint */
2820 SCIP_LINEARCONSTYPE*const linconstype /**< pointer to store the type of the linear constraint */
2821 )
2822{
2823 SCIP_CONSHDLRDATA* conshdlrdata;
2824 SCIP_CONSHDLR* upgrconshdlr;
2825 SCIP_CONS* cons;
2826 char name[SCIP_MAXSTRLEN];
2827 int v;
2828 SCIP_Bool created;
2829 SCIP_Bool integral;
2830 int nzero;
2831 int ncoeffspone;
2832 int ncoeffsnone;
2833 int ncoeffspint;
2834 int ncoeffsnint;
2835
2836 assert(scip != NULL);
2837 assert(conshdlr != NULL);
2838 assert(nlinvars == 0 || (linvars != NULL && linvals != NULL));
2839 assert(nandress == 0 || (andress != NULL && andvals != NULL));
2840 assert(lhs != NULL);
2841 assert(rhs != NULL);
2842 assert(lincons != NULL);
2843 assert(linconstype != NULL);
2844 assert(nlinvars > 0 || nandress > 0);
2845
2846 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2847 assert(conshdlrdata != NULL);
2848
2849 (*linconstype) = SCIP_LINEARCONSTYPE_INVALIDCONS;
2850 (*lincons) = NULL;
2851 cons = NULL;
2852
2853 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "pseudoboolean_linear%d", conshdlrdata->nlinconss);
2854 ++(conshdlrdata->nlinconss);
2855
2856 created = FALSE;
2857
2858 if( !modifiable )
2859 {
2860 SCIP_Real val;
2861 int nvars;
2862
2863 /* calculate some statistics for upgrading on linear constraint */
2864 nzero = 0;
2865 ncoeffspone = 0;
2866 ncoeffsnone = 0;
2867 ncoeffspint = 0;
2868 ncoeffsnint = 0;
2869 integral = TRUE;
2870 nvars = nlinvars + nandress;
2871
2872 /* calculate information over linear part */
2873 for( v = nlinvars - 1; v >= 0; --v )
2874 {
2875 val = linvals[v];
2876
2877 if( SCIPisZero(scip, val) )
2878 {
2879 ++nzero;
2880 continue;
2881 }
2882 if( SCIPisEQ(scip, val, 1.0) )
2883 ++ncoeffspone;
2884 else if( SCIPisEQ(scip, val, -1.0) )
2885 ++ncoeffsnone;
2886 else if( SCIPisIntegral(scip, val) )
2887 {
2888 if( SCIPisPositive(scip, val) )
2889 ++ncoeffspint;
2890 else
2891 ++ncoeffsnint;
2892 }
2893 else
2894 {
2895 integral = FALSE;
2896 break;
2897 }
2898 }
2899
2900 if( integral )
2901 {
2902 /* calculate information over and-resultants */
2903 for( v = nandress - 1; v >= 0; --v )
2904 {
2905 val = andvals[v];
2906
2907 if( SCIPisZero(scip, val) )
2908 {
2909 ++nzero;
2910 continue;
2911 }
2912 if( SCIPisEQ(scip, val, 1.0) )
2913 ++ncoeffspone;
2914 else if( SCIPisEQ(scip, val, -1.0) )
2915 ++ncoeffsnone;
2916 else if( SCIPisIntegral(scip, val) )
2917 {
2918 if( SCIPisPositive(scip, val) )
2919 ++ncoeffspint;
2920 else
2921 ++ncoeffsnint;
2922 }
2923 else
2924 {
2925 integral = FALSE;
2926 break;
2927 }
2928 }
2929 }
2930
2931 SCIPdebugMsg(scip, "While creating the linear constraint of the pseudoboolean constraint we found %d zero coefficients that were removed\n", nzero);
2932
2933 /* try to upgrade to a special linear constraint */
2934 if( integral )
2935 {
2936 upgrconshdlr = SCIPfindConshdlr(scip, "logicor");
2937
2938 /* check, if linear constraint can be upgraded to logic or constraint
2939 * - logic or constraints consist only of binary variables with a
2940 * coefficient of +1.0 or -1.0 (variables with -1.0 coefficients can be negated):
2941 * lhs <= x1 + ... + xp - y1 - ... - yn <= rhs
2942 * - negating all variables y = (1-Y) with negative coefficients gives:
2943 * lhs + n <= x1 + ... + xp + Y1 + ... + Yn <= rhs + n
2944 * - negating all variables x = (1-X) with positive coefficients and multiplying with -1 gives:
2945 * p - rhs <= X1 + ... + Xp + y1 + ... + yn <= p - lhs
2946 * - logic or constraints have left hand side of +1.0, and right hand side of +infinity: x(S) >= 1.0
2947 * -> without negations: (lhs == 1 - n and rhs == +inf) or (lhs == -inf and rhs = p - 1)
2948 */
2949 if( upgrconshdlr != NULL && nvars > 2 && ncoeffspone + ncoeffsnone == nvars
2950 && ((SCIPisEQ(scip, *lhs, 1.0 - ncoeffsnone) && SCIPisInfinity(scip, *rhs))
2951 || (SCIPisInfinity(scip, -*lhs) && SCIPisEQ(scip, *rhs, ncoeffspone - 1.0))) )
2952 {
2953 SCIP_VAR** transvars;
2954 int mult;
2955
2956 SCIPdebugMsg(scip, "linear constraint will be logic-or constraint\n");
2957
2958 /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
2959 mult = SCIPisInfinity(scip, *rhs) ? +1 : -1;
2960
2961 /* get temporary memory */
2962 SCIP_CALL( SCIPallocBufferArray(scip, &transvars, nvars) );
2963
2964 /* negate positive or negative variables */
2965 for( v = 0; v < nlinvars; ++v )
2966 {
2967 if( mult * linvals[v] > 0.0 )
2968 transvars[v] = linvars[v];
2969 else
2970 {
2971 SCIP_CALL( SCIPgetNegatedVar(scip, linvars[v], &transvars[v]) );
2972 }
2973 assert(transvars[v] != NULL);
2974 }
2975
2976 /* negate positive or negative variables */
2977 for( v = 0; v < nandress; ++v )
2978 {
2979 if( mult * andvals[v] > 0.0 )
2980 transvars[nlinvars + v] = andress[v];
2981 else
2982 {
2983 SCIP_CALL( SCIPgetNegatedVar(scip, andress[v], &transvars[nlinvars + v]) );
2984 andnegs[v] = TRUE;
2985 }
2986 assert(transvars[nlinvars + v] != NULL);
2987 }
2988
2989 assert(!modifiable);
2990 /* create the constraint */
2991 SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, nvars, transvars,
2992 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2993
2994 created = TRUE;
2995 (*linconstype) = SCIP_LINEARCONSTYPE_LOGICOR;
2996
2997 /* free temporary memory */
2998 SCIPfreeBufferArray(scip, &transvars);
2999
3000 *lhs = 1.0;
3001 *rhs = SCIPinfinity(scip);
3002 }
3003
3004 upgrconshdlr = SCIPfindConshdlr(scip, "setppc");
3005
3006 /* check, if linear constraint can be upgraded to set partitioning, packing, or covering constraint
3007 * - all set partitioning / packing / covering constraints consist only of binary variables with a
3008 * coefficient of +1.0 or -1.0 (variables with -1.0 coefficients can be negated):
3009 * lhs <= x1 + ... + xp - y1 - ... - yn <= rhs
3010 * - negating all variables y = (1-Y) with negative coefficients gives:
3011 * lhs + n <= x1 + ... + xp + Y1 + ... + Yn <= rhs + n
3012 * - negating all variables x = (1-X) with positive coefficients and multiplying with -1 gives:
3013 * p - rhs <= X1 + ... + Xp + y1 + ... + yn <= p - lhs
3014 * - a set partitioning constraint has left hand side of +1.0, and right hand side of +1.0 : x(S) == 1.0
3015 * -> without negations: lhs == rhs == 1 - n or lhs == rhs == p - 1
3016 * - a set packing constraint has left hand side of -infinity, and right hand side of +1.0 : x(S) <= 1.0
3017 * -> without negations: (lhs == -inf and rhs == 1 - n) or (lhs == p - 1 and rhs = +inf)
3018 * - a set covering constraint has left hand side of +1.0, and right hand side of +infinity: x(S) >= 1.0
3019 * -> without negations: (lhs == 1 - n and rhs == +inf) or (lhs == -inf and rhs = p - 1)
3020 */
3021 if( upgrconshdlr != NULL && !created && ncoeffspone + ncoeffsnone == nvars )
3022 {
3023 SCIP_VAR** transvars;
3024 int mult;
3025
3026 if( SCIPisEQ(scip, *lhs, *rhs) && (SCIPisEQ(scip, *lhs, 1.0 - ncoeffsnone) || SCIPisEQ(scip, *lhs, ncoeffspone - 1.0)) )
3027 {
3028 SCIPdebugMsg(scip, "linear pseudoboolean constraint will be a set partitioning constraint\n");
3029
3030 /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
3031 mult = SCIPisEQ(scip, *lhs, 1.0 - ncoeffsnone) ? +1 : -1;
3032
3033 /* get temporary memory */
3034 SCIP_CALL( SCIPallocBufferArray(scip, &transvars, nvars) );
3035
3036 /* negate positive or negative variables for linear variables */
3037 for( v = 0; v < nlinvars; ++v )
3038 {
3039 if( mult * linvals[v] > 0.0 )
3040 transvars[v] = linvars[v];
3041 else
3042 {
3043 SCIP_CALL( SCIPgetNegatedVar(scip, linvars[v], &transvars[v]) );
3044 }
3045 assert(transvars[v] != NULL);
3046 }
3047
3048 /* negate positive or negative variables for and-resultants */
3049 for( v = 0; v < nandress; ++v )
3050 {
3051 if( mult * andvals[v] > 0.0 )
3052 transvars[nlinvars + v] = andress[v];
3053 else
3054 {
3055 SCIP_CALL( SCIPgetNegatedVar(scip, andress[v], &transvars[nlinvars + v]) );
3056 andnegs[v] = TRUE;
3057 }
3058 assert(transvars[nlinvars + v] != NULL);
3059 }
3060
3061 /* create the constraint */
3062 assert(!modifiable);
3063 SCIP_CALL( SCIPcreateConsSetpart(scip, &cons, name, nvars, transvars,
3064 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3065
3066 created = TRUE;
3067 (*linconstype) = SCIP_LINEARCONSTYPE_SETPPC;
3068
3069 /* release temporary memory */
3070 SCIPfreeBufferArray(scip, &transvars);
3071
3072 *lhs = 1.0;
3073 *rhs = 1.0;
3074 }
3075 else if( (SCIPisInfinity(scip, -*lhs) && SCIPisEQ(scip, *rhs, 1.0 - ncoeffsnone))
3076 || (SCIPisEQ(scip, *lhs, ncoeffspone - 1.0) && SCIPisInfinity(scip, *rhs)) )
3077 {
3078 SCIPdebugMsg(scip, "linear pseudoboolean constraint will be a set packing constraint\n");
3079
3080 /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
3081 mult = SCIPisInfinity(scip, -*lhs) ? +1 : -1;
3082
3083 /* get temporary memory */
3084 SCIP_CALL( SCIPallocBufferArray(scip, &transvars, nvars) );
3085
3086 /* negate positive or negative variables for linear variables */
3087 for( v = 0; v < nlinvars; ++v )
3088 {
3089 if( mult * linvals[v] > 0.0 )
3090 transvars[v] = linvars[v];
3091 else
3092 {
3093 SCIP_CALL( SCIPgetNegatedVar(scip, linvars[v], &transvars[v]) );
3094 }
3095 assert(transvars[v] != NULL);
3096 }
3097
3098 /* negate positive or negative variables for and-resultants*/
3099 for( v = 0; v < nandress; ++v )
3100 {
3101 if( mult * andvals[v] > 0.0 )
3102 transvars[nlinvars + v] = andress[v];
3103 else
3104 {
3105 SCIP_CALL( SCIPgetNegatedVar(scip, andress[v], &transvars[nlinvars + v]) );
3106 andnegs[v] = TRUE;
3107 }
3108 assert(transvars[nlinvars + v] != NULL);
3109 }
3110
3111 /* create the constraint */
3112 assert(!modifiable);
3113 SCIP_CALL( SCIPcreateConsSetpack(scip, &cons, name, nvars, transvars,
3114 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3115
3116 created = TRUE;
3117 (*linconstype) = SCIP_LINEARCONSTYPE_SETPPC;
3118
3119 /* release temporary memory */
3120 SCIPfreeBufferArray(scip, &transvars);
3121
3122 *lhs = -SCIPinfinity(scip);
3123 *rhs = 1.0;
3124 }
3125 else if( (SCIPisEQ(scip, *lhs, 1.0 - ncoeffsnone) && SCIPisInfinity(scip, *rhs))
3126 || (SCIPisInfinity(scip, -*lhs) && SCIPisEQ(scip, *rhs, ncoeffspone - 1.0)) )
3127 {
3128 if( nvars != 1 )
3129 {
3130 if( nvars == 2 )
3131 {
3132 SCIPwarningMessage(scip, "Does not expect this, because this constraint should be a set packing constraint.\n");
3133 }
3134 else
3135 {
3136 SCIPwarningMessage(scip, "Does not expect this, because this constraint should be a logicor constraint.\n");
3137 }
3138 }
3139 SCIPdebugMsg(scip, "linear pseudoboolean constraint will be a set covering constraint\n");
3140
3141 /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
3142 mult = SCIPisInfinity(scip, *rhs) ? +1 : -1;
3143
3144 /* get temporary memory */
3145 SCIP_CALL( SCIPallocBufferArray(scip, &transvars, nvars) );
3146
3147 /* negate positive or negative variables for linear variables */
3148 for( v = 0; v < nlinvars; ++v )
3149 {
3150 if( mult * linvals[v] > 0.0 )
3151 transvars[v] = linvars[v];
3152 else
3153 {
3154 SCIP_CALL( SCIPgetNegatedVar(scip, linvars[v], &transvars[v]) );
3155 }
3156 assert(transvars[v] != NULL);
3157 }
3158
3159 /* negate positive or negative variables for and-resultants*/
3160 for( v = 0; v < nandress; ++v )
3161 {
3162 if( mult * andvals[v] > 0.0 )
3163 transvars[nlinvars + v] = andress[v];
3164 else
3165 {
3166 SCIP_CALL( SCIPgetNegatedVar(scip, andress[v], &transvars[nlinvars + v]) );
3167 andnegs[v] = TRUE;
3168 }
3169 assert(transvars[nlinvars + v] != NULL);
3170 }
3171
3172 /* create the constraint */
3173 assert(!modifiable);
3174 SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, name, nvars, transvars,
3175 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3176
3177 created = TRUE;
3178 (*linconstype) = SCIP_LINEARCONSTYPE_SETPPC;
3179
3180 /* release temporary memory */
3181 SCIPfreeBufferArray(scip, &transvars);
3182
3183 *lhs = 1.0;
3184 *rhs = SCIPinfinity(scip);
3185 }
3186 }
3187
3188 upgrconshdlr = SCIPfindConshdlr(scip, "knapsack");
3189
3190 /* check, if linear constraint can be upgraded to a knapsack constraint
3191 * - all variables must be binary
3192 * - all coefficients must be integral
3193 * - exactly one of the sides must be infinite
3194 */
3195 if( upgrconshdlr != NULL && !created && (ncoeffspone + ncoeffsnone + ncoeffspint + ncoeffsnint == nvars) && (SCIPisInfinity(scip, -*lhs) != SCIPisInfinity(scip, *rhs)) )
3196 {
3197 SCIP_VAR** transvars;
3198 SCIP_Longint* weights;
3199 SCIP_Longint capacity;
3200 SCIP_Longint weight;
3201 int mult;
3202
3203 SCIPdebugMsg(scip, "linear pseudoboolean constraint will be a knapsack constraint\n");
3204
3205 /* get temporary memory */
3206 SCIP_CALL( SCIPallocBufferArray(scip, &transvars, nvars) );
3207 SCIP_CALL( SCIPallocBufferArray(scip, &weights, nvars) );
3208
3209 /* if the right hand side is non-infinite, we have to negate all variables with negative coefficient;
3210 * otherwise, we have to negate all variables with positive coefficient and multiply the row with -1
3211 */
3212 if( SCIPisInfinity(scip, *rhs) )
3213 {
3214 mult = -1;
3215 capacity = (SCIP_Longint)SCIPfeasFloor(scip, -*lhs);
3216 }
3217 else
3218 {
3219 mult = +1;
3220 capacity = (SCIP_Longint)SCIPfeasFloor(scip, *rhs);
3221 }
3222
3223 /* negate positive or negative variables for linear variables */
3224 for( v = 0; v < nlinvars; ++v )
3225 {
3226 assert(SCIPisFeasIntegral(scip, linvals[v]));
3227 weight = mult * (SCIP_Longint)SCIPfeasFloor(scip, linvals[v]);
3228 if( weight > 0 )
3229 {
3230 transvars[v] = linvars[v];
3231 weights[v] = weight;
3232 }
3233 else
3234 {
3235 SCIP_CALL( SCIPgetNegatedVar(scip, linvars[v], &transvars[v]) );
3236 weights[v] = -weight;
3237 capacity -= weight;
3238 }
3239 assert(transvars[v] != NULL);
3240 }
3241 /* negate positive or negative variables for and-resultants */
3242 for( v = 0; v < nandress; ++v )
3243 {
3244 assert(SCIPisFeasIntegral(scip, andvals[v]));
3245 weight = mult * (SCIP_Longint)SCIPfeasFloor(scip, andvals[v]);
3246 if( weight > 0 )
3247 {
3248 transvars[nlinvars + v] = andress[v];
3249 weights[nlinvars + v] = weight;
3250 }
3251 else
3252 {
3253 SCIP_CALL( SCIPgetNegatedVar(scip, andress[v], &transvars[nlinvars + v]) );
3254 andnegs[v] = TRUE;
3255 weights[nlinvars + v] = -weight;
3256 capacity -= weight;
3257 }
3258 assert(transvars[nlinvars + v] != NULL);
3259 }
3260
3261 /* create the constraint */
3262 SCIP_CALL( SCIPcreateConsKnapsack(scip, &cons, name, nvars, transvars, weights, capacity,
3263 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3264
3265 created = TRUE;
3266 (*linconstype) = SCIP_LINEARCONSTYPE_KNAPSACK;
3267
3268 /* free temporary memory */
3269 SCIPfreeBufferArray(scip, &weights);
3270 SCIPfreeBufferArray(scip, &transvars);
3271
3272 *lhs = -SCIPinfinity(scip);
3273 *rhs = capacity;
3274 }
3275#ifdef WITHEQKNAPSACK
3276
3277 upgrconshdlr = SCIPfindConshdlr(scip, "eqknapsack");
3278
3279 /* check, if linear constraint can be upgraded to a knapsack constraint
3280 * - all variables must be binary
3281 * - all coefficients must be integral
3282 * - both sides must be infinite
3283 */
3284 if( upgrconshdlr != NULL && !created && (ncoeffspone + ncoeffsnone + ncoeffspint + ncoeffsnint == nvars) && SCIPisEQ(scip, *lhs, *rhs) )
3285 {
3286 SCIP_VAR** transvars;
3287 SCIP_Longint* weights;
3288 SCIP_Longint capacity;
3289 SCIP_Longint weight;
3290 int mult;
3291
3292 assert(!SCIPisInfinity(scip, *rhs));
3293
3294 SCIPdebugMsg(scip, "linear pseudoboolean constraint will be a equality-knapsack constraint\n");
3295
3296 /* get temporary memory */
3297 SCIP_CALL( SCIPallocBufferArray(scip, &transvars, nvars) );
3298 SCIP_CALL( SCIPallocBufferArray(scip, &weights, nvars) );
3299
3300 if( SCIPisPositive(scip, *rhs) )
3301 {
3302 mult = +1;
3303 capacity = (SCIP_Longint)SCIPfeasFloor(scip, *rhs);
3304 }
3305 else
3306 {
3307 mult = -1;
3308 capacity = (SCIP_Longint)SCIPfeasFloor(scip, -*rhs);
3309 }
3310
3311 /* negate positive or negative variables for linear variables */
3312 for( v = 0; v < nlinvars; ++v )
3313 {
3314 assert(SCIPisFeasIntegral(scip, linvals[v]));
3315 weight = mult * (SCIP_Longint)SCIPfeasFloor(scip, linvals[v]);
3316 if( weight > 0 )
3317 {
3318 transvars[v] = linvars[v];
3319 weights[v] = weight;
3320 }
3321 else
3322 {
3323 SCIP_CALL( SCIPgetNegatedVar(scip, linvars[v], &transvars[v]) );
3324 weights[v] = -weight;
3325 capacity -= weight;
3326 }
3327 assert(transvars[v] != NULL);
3328 }
3329 /* negate positive or negative variables for and-resultants */
3330 for( v = 0; v < nandress; ++v )
3331 {
3332 assert(SCIPisFeasIntegral(scip, andvals[v]));
3333 weight = mult * (SCIP_Longint)SCIPfeasFloor(scip, andvals[v]);
3334 if( weight > 0 )
3335 {
3336 transvars[nlinvars + v] = andress[v];
3337 weights[nlinvars + v] = weight;
3338 }
3339 else
3340 {
3341 SCIP_CALL( SCIPgetNegatedVar(scip, andress[v], &transvars[nlinvars + v]) );
3342 andnegs[v] = TRUE;
3343 weights[nlinvars + v] = -weight;
3344 capacity -= weight;
3345 }
3346 assert(transvars[nlinvars + v] != NULL);
3347 }
3348
3349 /* create the constraint */
3350 SCIP_CALL( SCIPcreateConsEqKnapsack(scip, &cons, name, nvars, transvars, weights, capacity,
3351 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3352
3353 created = TRUE;
3354 (*linconstype) = SCIP_LINEARCONSTYPE_EQKNAPSACK;
3355
3356 /* free temporary memory */
3357 SCIPfreeBufferArray(scip, &weights);
3358 SCIPfreeBufferArray(scip, &transvars);
3359
3360 *lhs = capacity;
3361 *rhs = capacity;
3362 }
3363#endif
3364 }
3365 }
3366
3367 upgrconshdlr = SCIPfindConshdlr(scip, "linear");
3368 assert(created || upgrconshdlr != NULL);
3369
3370 if( !created )
3371 {
3372 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nlinvars, linvars, linvals, *lhs, *rhs,
3373 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3374
3375 (*linconstype) = SCIP_LINEARCONSTYPE_LINEAR;
3376
3377 /* add all and-resultants */
3378 for( v = 0; v < nandress; ++v )
3379 {
3380 assert(andress[v] != NULL);
3381
3382 /* add auxiliary variables to linear constraint */
3383 SCIP_CALL( SCIPaddCoefLinear(scip, cons, andress[v], andvals[v]) );
3384 }
3385 }
3386
3387 assert(cons != NULL && *linconstype > SCIP_LINEARCONSTYPE_INVALIDCONS);
3388
3389 SCIP_CALL( SCIPaddCons(scip, cons) );
3391
3392 *lincons = cons;
3393 SCIP_CALL( SCIPcaptureCons(scip, *lincons) );
3394
3395 /* mark linear constraint not to be upgraded - otherwise we loose control over it */
3396 SCIPconsAddUpgradeLocks(cons, 1);
3397
3398 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3399
3400 return SCIP_OKAY;
3401}
3402
3403/** checks one original pseudoboolean constraint for feasibility of given solution */
3404static
3406 SCIP*const scip, /**< SCIP data structure */
3407 SCIP_CONS*const cons, /**< pseudo boolean constraint */
3408 SCIP_SOL*const sol, /**< solution to be checked, or NULL for current solution */
3409 SCIP_Bool*const violated, /**< pointer to store whether the constraint is violated */
3410 SCIP_Bool const printreason /**< should violation of constraint be printed */
3411 )
3412{
3413 SCIP_CONSDATA* consdata;
3414 SCIP_CONSHDLR* conshdlr;
3415 SCIP_CONSHDLRDATA* conshdlrdata;
3416
3417 SCIP_VAR** vars;
3418 SCIP_Real* coefs;
3419 SCIP_Real lhs;
3420 SCIP_Real rhs;
3421 SCIP_Real activity;
3422 int nvars;
3423 int v;
3424
3425 SCIP_Real lhsviol;
3426 SCIP_Real rhsviol;
3427 SCIP_Real absviol;
3428 SCIP_Real relviol;
3429
3430 assert(scip != NULL);
3431 assert(cons != NULL);
3432 assert(SCIPconsIsOriginal(cons));
3433 assert(violated != NULL);
3434
3435 *violated = FALSE;
3436
3437 SCIPdebugMsg(scip, "checking original pseudo boolean constraint <%s>\n", SCIPconsGetName(cons));
3439
3440 consdata = SCIPconsGetData(cons);
3441 assert(consdata != NULL);
3442 assert(consdata->lincons != NULL);
3443 assert(consdata->linconstype > SCIP_LINEARCONSTYPE_INVALIDCONS);
3444 assert(SCIPconsIsOriginal(consdata->lincons));
3445
3446 /* gets number of variables in linear constraint */
3447 SCIP_CALL( getLinearConsNVars(scip, consdata->lincons, consdata->linconstype, &nvars) );
3448
3449 /* allocate temporary memory */
3450 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
3451 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
3452
3453 /* get sides of linear constraint */
3454 SCIP_CALL( getLinearConsSides(scip, consdata->lincons, consdata->linconstype, &lhs, &rhs) );
3455 assert(!SCIPisInfinity(scip, lhs));
3456 assert(!SCIPisInfinity(scip, -rhs));
3457 assert(SCIPisLE(scip, lhs, rhs));
3458
3459 /* get variables and coefficient of linear constraint */
3460 SCIP_CALL( getLinearConsVarsData(scip, consdata->lincons, consdata->linconstype, vars, coefs, &nvars) );
3461 assert(nvars == 0 || (coefs != NULL));
3462
3463 /* number of variables should be consistent, number of 'real' linear variables plus number of and-constraints should
3464 * have to be equal to the number of variables in the linear constraint
3465 */
3466 assert(consdata->nlinvars + consdata->nconsanddatas == nvars);
3467
3468 conshdlr = SCIPconsGetHdlr(cons);
3469 assert(conshdlr != NULL);
3470
3471 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3472 assert(conshdlrdata != NULL);
3473 assert(conshdlrdata->hashmap != NULL);
3474
3475 activity = 0.0;
3476
3477 /* compute pseudoboolean activity */
3478 for( v = 0; v < nvars; ++v )
3479 {
3480 CONSANDDATA* consanddata = NULL;
3481 SCIP_VAR* var = vars[v];
3482 SCIP_Real solval;
3483
3484 /* find and-constraint to standard or negated and-resultant */
3485 do
3486 {
3487 consanddata = (CONSANDDATA*)SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)var);
3488
3489 if( consanddata != NULL )
3490 break;
3491
3492 if( var == vars[v] )
3493 var = SCIPvarGetNegatedVar(var);
3494 else
3495 var = vars[v];
3496 }
3497 while( var != vars[v] );
3498
3499 /* get linear solution */
3500 if( consanddata == NULL )
3501 solval = SCIPgetSolVal(scip, sol, vars[v]);
3502 /* get term solution */
3503 else
3504 {
3505 SCIP_CONS* andcons = consanddata->origcons;
3506 SCIP_VAR** andvars;
3507 int nandvars;
3508 int i;
3509
3510 /* use transformed constraint if no original constraint exists */
3511 if( andcons == NULL )
3512 andcons = consanddata->cons;
3513
3514 assert(SCIPgetResultantAnd(scip, andcons) == var);
3515
3516 andvars = SCIPgetVarsAnd(scip, andcons);
3517 nandvars = SCIPgetNVarsAnd(scip, andcons);
3518 assert(nandvars == 0 || andvars != NULL);
3519
3520 solval = 1.0;
3521
3522 for( i = 0; i < nandvars; ++i )
3523 solval *= SCIPgetSolVal(scip, sol, andvars[i]);
3524
3525 if( var != vars[v] )
3526 solval = 1.0 - solval;
3527 }
3528
3529 /* add activity contribution */
3530 activity += coefs[v] * solval;
3531 }
3532
3533 SCIPdebugMsg(scip, "lhs = %g, activity = %g, rhs = %g\n", lhs, activity, rhs);
3534
3535 /* calculate absolute and relative violation */
3536 lhsviol = lhs - activity;
3537 rhsviol = activity - rhs;
3538
3539 if(lhsviol > rhsviol)
3540 {
3541 absviol = lhsviol;
3542 relviol = SCIPrelDiff(lhs, activity);
3543 }
3544 else
3545 {
3546 absviol = rhsviol;
3547 relviol = SCIPrelDiff(activity, rhs);
3548 }
3549
3550 /* update absolute and relative violation of the solution */
3551 if( sol != NULL )
3552 SCIPupdateSolConsViolation(scip, sol, absviol, relviol);
3553
3554 /* check left hand side for violation */
3555 if( SCIPisFeasLT(scip, activity, lhs) )
3556 {
3557 if( printreason )
3558 {
3559 SCIP_CALL( SCIPprintCons(scip, cons, NULL ) );
3560 SCIPinfoMessage(scip, NULL, ";\n");
3561 SCIPinfoMessage(scip, NULL, "violation: left hand side is violated by %.15g\n", lhs - activity);
3562
3563 /* print linear constraint in SCIP_DEBUG mode too */
3564 SCIPdebugPrintCons(scip, SCIPconsGetData(cons)->lincons, NULL);
3565 }
3566
3567 *violated = TRUE;
3568 }
3569
3570 /* check right hand side for violation */
3571 if( SCIPisFeasGT(scip, activity, rhs) )
3572 {
3573 if( printreason )
3574 {
3575 SCIP_CALL( SCIPprintCons(scip, cons, NULL ) );
3576 SCIPinfoMessage(scip, NULL, ";\n");
3577 SCIPinfoMessage(scip, NULL, "violation: right hand side is violated by %.15g\n", activity - rhs);
3578 }
3579
3580 *violated = TRUE;
3581 }
3582
3583 /* free temporary memory */
3584 SCIPfreeBufferArray(scip, &coefs);
3585 SCIPfreeBufferArray(scip, &vars);
3586
3587 return SCIP_OKAY;
3588}
3589
3590/** checks all and-constraints inside the pseudoboolean constraint handler for feasibility of given solution or current
3591 * solution
3592 */
3593static
3595 SCIP*const scip, /**< SCIP data structure */
3596 SCIP_CONSHDLR*const conshdlr, /**< pseudo boolean constraint handler */
3597 SCIP_SOL*const sol, /**< solution to be checked, or NULL for current solution */
3598 SCIP_Bool*const violated /**< pointer to store whether the constraint is violated */
3599 )
3600{
3601 SCIP_CONSHDLRDATA* conshdlrdata;
3602 SCIP_CONS* andcons;
3603 SCIP_VAR** vars;
3604 SCIP_VAR* res;
3605 int nvars;
3606 int c;
3607 int v;
3608
3609 assert(scip != NULL);
3610 assert(conshdlr != NULL);
3611 assert(violated != NULL);
3612
3613 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3614 assert(conshdlrdata != NULL);
3615
3616 *violated = FALSE;
3617
3618 for( c = conshdlrdata->nallconsanddatas - 1; c >= 0; --c )
3619 {
3620 SCIP_Real solval;
3621 SCIP_Real minsolval;
3622 SCIP_Real sumsolval;
3623 SCIP_Real viol;
3624
3625 if( !conshdlrdata->allconsanddatas[c]->istransformed )
3626 continue;
3627
3628 andcons = conshdlrdata->allconsanddatas[c]->cons;
3629
3630 /* need to check even locally deleted constraints */
3631 if( andcons == NULL ) /*|| !SCIPconsIsActive(andcons) )*/
3632 continue;
3633
3634 vars = SCIPgetVarsAnd(scip, andcons);
3635 nvars = SCIPgetNVarsAnd(scip, andcons);
3636 res = SCIPgetResultantAnd(scip, andcons);
3637 assert(nvars == 0 || (vars != NULL && res != NULL));
3638
3639 /* check if the and-constraint is violated */
3640 minsolval = 1.0;
3641 sumsolval = 0.0;
3642 for( v = nvars - 1; v >= 0; --v )
3643 {
3644 solval = SCIPgetSolVal(scip, sol, vars[v]);
3645
3646 if( solval < minsolval )
3647 minsolval = solval;
3648
3649 sumsolval += solval;
3650 }
3651
3652 /* the resultant must be at most as large as every operator
3653 * and at least as large as one minus the sum of negated operators
3654 */
3655 solval = SCIPgetSolVal(scip, sol, res);
3656 viol = MAX3(0.0, solval - minsolval, sumsolval - (nvars - 1.0 + solval));
3657
3658 if( SCIPisFeasPositive(scip, viol) )
3659 {
3660 /* only reset constraint age if we are in enforcement */
3661 if( sol == NULL )
3662 {
3663 SCIP_CALL( SCIPresetConsAge(scip, andcons) );
3664 }
3665
3666 *violated = TRUE;
3667 break;
3668 }
3669 else if( sol == NULL )
3670 {
3671 SCIP_CALL( SCIPincConsAge(scip, andcons) );
3672 }
3673 }
3674
3675 return SCIP_OKAY;
3676}
3677
3678/** creates by copying and captures a linear constraint */
3679static
3681 SCIP*const targetscip, /**< target SCIP data structure */
3682 SCIP_CONS** targetcons, /**< pointer to store the created target constraint */
3683 SCIP*const sourcescip, /**< source SCIP data structure */
3684 SCIP_CONS*const sourcecons, /**< source constraint which will be copied */
3685 const char* name, /**< name of constraint */
3686 SCIP_HASHMAP*const varmap, /**< a SCIP_HASHMAP mapping variables of the source SCIP to corresponding
3687 * variables of the target SCIP */
3688 SCIP_HASHMAP*const consmap, /**< a hashmap to store the mapping of source constraints to the corresponding
3689 * target constraints */
3690 SCIP_Bool const initial, /**< should the LP relaxation of constraint be in the initial LP? */
3691 SCIP_Bool const separate, /**< should the constraint be separated during LP processing? */
3692 SCIP_Bool const enforce, /**< should the constraint be enforced during node processing? */
3693 SCIP_Bool const check, /**< should the constraint be checked for feasibility? */
3694 SCIP_Bool const propagate, /**< should the constraint be propagated during node processing? */
3695 SCIP_Bool const local, /**< is constraint only valid locally? */
3696 SCIP_Bool const modifiable, /**< is constraint modifiable (subject to column generation)? */
3697 SCIP_Bool const dynamic, /**< is constraint subject to aging? */
3698 SCIP_Bool const removable, /**< should the relaxation be removed from the LP due to aging or cleanup? */
3699 SCIP_Bool const stickingatnode, /**< should the constraint always be kept at the node where it was added, even
3700 * if it may be moved to a more global node? */
3701 SCIP_Bool const global, /**< create a global or a local copy? */
3702 SCIP_Bool*const valid /**< pointer to store if the copying was valid */
3703 )
3704{
3705 SCIP_CONSDATA* sourceconsdata;
3706 SCIP_CONS* sourcelincons;
3707
3708 assert(targetscip != NULL);
3709 assert(targetcons != NULL);
3710 assert(sourcescip != NULL);
3711 assert(sourcecons != NULL);
3712 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)), CONSHDLR_NAME) == 0);
3713 assert(valid != NULL);
3714
3715 *valid = TRUE;
3716
3717 sourceconsdata = SCIPconsGetData(sourcecons);
3718 assert(sourceconsdata != NULL);
3719
3720 /* get linear constraint */
3721 sourcelincons = sourceconsdata->lincons;
3722 assert(sourcelincons != NULL);
3723
3724 /* get copied version of linear constraint */
3725 if( !SCIPconsIsDeleted(sourcelincons) )
3726 {
3727 SCIP_CONSHDLR* conshdlrlinear;
3728 SCIP_CONS* targetlincons;
3729 SCIP_CONS** targetandconss;
3730 SCIP_Real* targetandcoefs;
3731 int ntargetandconss;
3732 SCIP_LINEARCONSTYPE targetlinconstype;
3733
3734 targetlinconstype = sourceconsdata->linconstype;
3735
3736 switch( targetlinconstype )
3737 {
3739 conshdlrlinear = SCIPfindConshdlr(sourcescip, "linear");
3740 assert(conshdlrlinear != NULL);
3741 break;
3743 conshdlrlinear = SCIPfindConshdlr(sourcescip, "logicor");
3744 assert(conshdlrlinear != NULL);
3745 break;
3747 conshdlrlinear = SCIPfindConshdlr(sourcescip, "knapsack");
3748 assert(conshdlrlinear != NULL);
3749 break;
3751 conshdlrlinear = SCIPfindConshdlr(sourcescip, "setppc");
3752 assert(conshdlrlinear != NULL);
3753 break;
3754#ifdef WITHEQKNAPSACK
3755 case SCIP_LINEARCONSTYPE_EQKNAPSACK:
3756 conshdlrlinear = SCIPfindConshdlr(sourcescip, "eqknapsack");
3757 assert(conshdlrlinear != NULL);
3758 break;
3759#endif
3761 default:
3762 SCIPerrorMessage("unknown linear constraint type\n");
3763 return SCIP_INVALIDDATA;
3764 }
3765
3766 if( conshdlrlinear == NULL ) /*lint !e774*/
3767 {
3768 SCIPerrorMessage("linear constraint handler not found\n");
3769 return SCIP_INVALIDDATA;
3770 }
3771
3772 targetlincons = NULL;
3773
3774 /* copy linear constraint */
3775 SCIP_CALL( SCIPgetConsCopy(sourcescip, targetscip, sourcelincons, &targetlincons, conshdlrlinear, varmap, consmap, SCIPconsGetName(sourcelincons),
3776 SCIPconsIsInitial(sourcelincons), SCIPconsIsSeparated(sourcelincons), SCIPconsIsEnforced(sourcelincons), SCIPconsIsChecked(sourcelincons),
3777 SCIPconsIsPropagated(sourcelincons), SCIPconsIsLocal(sourcelincons), SCIPconsIsModifiable(sourcelincons), SCIPconsIsDynamic(sourcelincons),
3778 SCIPconsIsRemovable(sourcelincons), SCIPconsIsStickingAtNode(sourcelincons), global, valid) );
3779
3780 if( *valid )
3781 {
3782 assert(targetlincons != NULL);
3783 assert(SCIPconsGetHdlr(targetlincons) != NULL);
3784 /* @note due to copying special linear constraints, now leads only to simple linear constraints, we check that
3785 * our target constraint handler is the same as our source constraint handler of the linear constraint,
3786 * if copying was not valid
3787 */
3788 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(targetlincons)), "linear") == 0 )
3789 targetlinconstype = SCIP_LINEARCONSTYPE_LINEAR;
3790 }
3791
3792 targetandconss = NULL;
3793 targetandcoefs = NULL;
3794 ntargetandconss = 0;
3795
3796 if( *valid )
3797 {
3798 SCIP_CONSHDLR* conshdlrand;
3799 int c;
3800 int nsourceandconss;
3801 SCIP_HASHTABLE* linconsvarsmap;
3802 SCIP_VAR** targetlinvars;
3803 SCIP_Real* targetlincoefs;
3804 int ntargetlinvars;
3805
3806 conshdlrand = SCIPfindConshdlr(sourcescip, "and");
3807 assert(conshdlrand != NULL);
3808
3809 nsourceandconss = sourceconsdata->nconsanddatas;
3810
3811 /* allocate temporary memory */
3812 SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetandconss, nsourceandconss) );
3813 SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetandcoefs, nsourceandconss) );
3814
3815 /* get the number of vars in the copied linear constraint and allocate buffers
3816 * for the variables and the coefficients
3817 */
3818 SCIP_CALL( getLinearConsNVars(targetscip, targetlincons, targetlinconstype, &ntargetlinvars) );
3819 SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetlinvars, ntargetlinvars) );
3820 SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetlincoefs, ntargetlinvars) );
3821
3822 /* retrieve the variables of the copied linear constraint */
3823 SCIP_CALL( getLinearConsVarsData(targetscip, targetlincons, targetlinconstype,
3824 targetlinvars, targetlincoefs, &ntargetlinvars) );
3825
3826 /* now create a hashtable and insert the variables into it, so that it
3827 * can be checked in constant time if a variable was removed due to
3828 * compressed copying when looping over the and resultants
3829 */
3830 SCIP_CALL( SCIPhashtableCreate(&linconsvarsmap, SCIPblkmem(targetscip), ntargetlinvars, SCIPvarGetHashkey,
3831 SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) );
3832
3833 for( c = 0 ; c < ntargetlinvars; ++c )
3834 {
3835 SCIP_CALL( SCIPhashtableInsert(linconsvarsmap, targetlinvars[c]) );
3836 }
3837
3838 /* free the buffer arrays that were only required for building the hastable */
3839 SCIPfreeBufferArray(sourcescip, &targetlincoefs);
3840 SCIPfreeBufferArray(sourcescip, &targetlinvars);
3841
3842 for( c = 0 ; c < nsourceandconss; ++c )
3843 {
3844 CONSANDDATA* consanddata;
3845 SCIP_CONS* oldcons;
3846 SCIP_VAR* targetandresultant;
3847 SCIP_Bool validand;
3848
3849 consanddata = sourceconsdata->consanddatas[c];
3850 assert(consanddata != NULL);
3851
3852 oldcons = consanddata->istransformed ? consanddata->cons : consanddata->origcons;
3853 assert(oldcons != NULL);
3854
3855 targetandresultant = (SCIP_VAR*) SCIPhashmapGetImage(varmap, SCIPgetResultantAnd(sourcescip, oldcons));
3856 assert(targetandresultant != NULL);
3857
3858 /* if compressed copying is active, the resultant might not have been copied by the linear
3859 * constraint and we don't need to add it to the pseudo boolean constraint in this case
3860 */
3861 if( !SCIPhashtableExists(linconsvarsmap, targetandresultant) )
3862 continue;
3863
3864 validand = TRUE;
3865
3866 targetandconss[ntargetandconss] = NULL;
3867
3868 /* copy and-constraints */
3869 SCIP_CALL( SCIPgetConsCopy(sourcescip, targetscip, oldcons, &targetandconss[ntargetandconss], conshdlrand, varmap, consmap, SCIPconsGetName(oldcons),
3870 SCIPconsIsInitial(oldcons), SCIPconsIsSeparated(oldcons), SCIPconsIsEnforced(oldcons), SCIPconsIsChecked(oldcons),
3871 SCIPconsIsPropagated(oldcons), SCIPconsIsLocal(oldcons), SCIPconsIsModifiable(oldcons), SCIPconsIsDynamic(oldcons),
3872 SCIPconsIsRemovable(oldcons), SCIPconsIsStickingAtNode(oldcons), global, &validand) );
3873
3874 *valid &= validand;
3875
3876 if( validand )
3877 {
3878 targetandcoefs[ntargetandconss] = sourceconsdata->andcoefs[c];
3879 ++ntargetandconss;
3880 }
3881 }
3882
3883 SCIPhashtableFree(&linconsvarsmap);
3884 assert(ntargetandconss <= ntargetlinvars);
3885 }
3886
3887 if( *valid )
3888 {
3889 SCIP_Real targetrhs;
3890 SCIP_Real targetlhs;
3891
3892 SCIP_VAR* intvar;
3893 SCIP_VAR* indvar;
3894 const char* consname;
3895
3896 /* third the indicator and artificial integer variable part */
3897 assert(sourceconsdata->issoftcons == (sourceconsdata->indvar != NULL));
3898 indvar = sourceconsdata->indvar;
3899 intvar = sourceconsdata->intvar;
3900
3901 /* copy indicator variable */
3902 if( indvar != NULL )
3903 {
3904 assert(*valid);
3905 SCIP_CALL( SCIPgetVarCopy(sourcescip, targetscip, indvar, &indvar, varmap, consmap, global, valid) );
3906 assert(!(*valid) || indvar != NULL);
3907 }
3908 /* copy artificial integer variable */
3909 if( intvar != NULL && *valid )
3910 {
3911 SCIP_CALL( SCIPgetVarCopy(sourcescip, targetscip, intvar, &intvar, varmap, consmap, global, valid) );
3912 assert(!(*valid) || intvar != NULL);
3913 }
3914
3915 if( *valid )
3916 {
3917 if( name != NULL )
3918 consname = name;
3919 else
3920 consname = SCIPconsGetName(sourcecons);
3921
3922 /* get new left and right hand sides of copied linear constraint since
3923 * they might have changed if compressed copying is used
3924 */
3925 SCIP_CALL( getLinearConsSides(targetscip, targetlincons, targetlinconstype, &targetlhs, &targetrhs) );
3926
3927 /* create new pseudoboolean constraint */
3928 /* coverity[var_deref_op] */
3929 /* coverity[var_deref_model] */
3930 /* Note that due to compression the and constraints might have disappeared in which case ntargetandconss == 0. */
3931 SCIP_CALL( SCIPcreateConsPseudobooleanWithConss(targetscip, targetcons, consname,
3932 targetlincons, targetlinconstype, targetandconss, targetandcoefs, ntargetandconss,
3933 indvar, sourceconsdata->weight, sourceconsdata->issoftcons, intvar, targetlhs, targetrhs,
3934 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3935 }
3936 }
3937
3938 if( !(*valid) && !SCIPisConsCompressionEnabled(sourcescip) )
3939 {
3940 SCIPverbMessage(sourcescip, SCIP_VERBLEVEL_MINIMAL, NULL, "could not copy constraint <%s>\n", SCIPconsGetName(sourcecons));
3941 }
3942
3943 /* release copied linear constraint */
3944 if( targetlincons != NULL )
3945 {
3946 SCIP_CALL( SCIPreleaseCons(targetscip, &targetlincons) );
3947 }
3948
3949 /* release copied and constraint */
3950 if( targetandconss != NULL )
3951 {
3952 int c;
3953
3954 assert(ntargetandconss <= sourceconsdata->nconsanddatas);
3955
3956 for( c = 0 ; c < ntargetandconss; ++c )
3957 {
3958 if( targetandconss[c] != NULL )
3959 {
3960 SCIP_CALL( SCIPreleaseCons(targetscip, &targetandconss[c]) );
3961 }
3962 }
3963 }
3964
3965 /* free temporary memory */
3966 SCIPfreeBufferArrayNull(sourcescip, &targetandcoefs);
3967 SCIPfreeBufferArrayNull(sourcescip, &targetandconss);
3968 }
3969 else
3970 *valid = FALSE;
3971
3972 return SCIP_OKAY;
3973}
3974
3975/** compute all changes in consanddatas array */
3976static
3978 SCIP*const scip, /**< SCIP data structure */
3979 SCIP_CONSHDLRDATA*const conshdlrdata /**< pseudoboolean constraint handler data */
3980 )
3981{
3982 CONSANDDATA** allconsanddatas;
3983 CONSANDDATA* consanddata;
3984 int c;
3985
3986 assert(scip != NULL);
3987 assert(conshdlrdata != NULL);
3988
3989 allconsanddatas = conshdlrdata->allconsanddatas;
3990 assert(allconsanddatas != NULL);
3991 assert(conshdlrdata->nallconsanddatas > 0);
3992 assert(conshdlrdata->nallconsanddatas <= conshdlrdata->sallconsanddatas);
3993
3994 for( c = conshdlrdata->nallconsanddatas - 1; c >= 0; --c )
3995 {
3996 SCIP_CONS* cons;
3997 SCIP_VAR** vars;
3998 int nvars;
3999 SCIP_VAR** newvars;
4000 int nnewvars;
4001 int v;
4002
4003 consanddata = allconsanddatas[c];
4004
4005 if( !consanddata->istransformed )
4006 continue;
4007
4008 if( consanddata->nuses == 0 )
4009 continue;
4010
4011 vars = consanddata->vars;
4012 nvars = consanddata->nvars;
4013 assert(nvars == 0 || vars != NULL);
4014 assert(consanddata->nnewvars == 0 && ((consanddata->snewvars > 0) == (consanddata->newvars != NULL)));
4015
4016 if( nvars == 0 )
4017 {
4018#ifndef NDEBUG
4019 /* if an old consanddata-object has no variables left there should be no new variables */
4020 if( consanddata->cons != NULL )
4021 assert(SCIPgetNVarsAnd(scip, consanddata->cons) == 0);
4022#endif
4023 continue;
4024 }
4025
4026 cons = consanddata->cons;
4027 assert(cons != NULL);
4028
4029 if( SCIPconsIsDeleted(cons) )
4030 continue;
4031
4032 /* sort and-variables */
4033 if( !SCIPisAndConsSorted(scip, consanddata->cons) )
4034 {
4035 SCIP_CALL( SCIPsortAndCons(scip, consanddata->cons) );
4036 assert(SCIPisAndConsSorted(scip, consanddata->cons));
4037 }
4038
4039 /* get new and-variables */
4040 nnewvars = SCIPgetNVarsAnd(scip, consanddata->cons);
4041 newvars = SCIPgetVarsAnd(scip, consanddata->cons);
4042
4043 /* stop if the constraint has no variables or there was an error (coverity issue) */
4044 if( nnewvars <= 0 )
4045 continue;
4046
4047#ifndef NDEBUG
4048 /* check that old variables are sorted */
4049 for( v = nvars - 1; v > 0; --v )
4050 assert(SCIPvarGetIndex(vars[v]) >= SCIPvarGetIndex(vars[v - 1]));
4051 /* check that new variables are sorted */
4052 for( v = nnewvars - 1; v > 0; --v )
4053 assert(SCIPvarGetIndex(newvars[v]) >= SCIPvarGetIndex(newvars[v - 1]));
4054#endif
4055
4056 /* check for changings, if and-constraint did not change we do not need to copy all variables */
4057 if( nvars == nnewvars )
4058 {
4059 SCIP_Bool changed;
4060
4061 changed = FALSE;
4062
4063 /* check each variable */
4064 for( v = nvars - 1; v >= 0; --v )
4065 {
4066 if( vars[v] != newvars[v] )
4067 {
4068 changed = TRUE;
4069 break;
4070 }
4071 }
4072
4073 if( !changed )
4074 continue;
4075 }
4076
4077 /* resize newvars array if necessary */
4078 if( nnewvars > consanddata->snewvars )
4079 {
4080 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &(consanddata->newvars), &(consanddata->snewvars), nnewvars) );
4081 }
4082
4083 /* copy all variables */
4084 BMScopyMemoryArray(consanddata->newvars, newvars, nnewvars);
4085 consanddata->nnewvars = nnewvars;
4086
4087 /* capture all variables */
4088 for( v = consanddata->nnewvars - 1; v >= 0; --v )
4089 {
4090 /* in original problem the variables was already deleted */
4091 assert(consanddata->newvars[v] != NULL);
4092 SCIP_CALL( SCIPcaptureVar(scip, consanddata->newvars[v]) );
4093 }
4094 }
4095
4096 return SCIP_OKAY;
4097}
4098
4099/** remove old locks */
4100static
4102 SCIP*const scip, /**< SCIP data structure */
4103 SCIP_CONS*const cons, /**< pseudoboolean constraint */
4104 CONSANDDATA*const consanddata, /**< CONSANDDATA object for which we want to delete the locks and the
4105 * capture of the corresponding and-constraint */
4106 SCIP_Real const coef, /**< coefficient which led to old locks */
4107 SCIP_Real const lhs, /**< left hand side which led to old locks */
4108 SCIP_Real const rhs /**< right hand side which led to old locks */
4109 )
4110{
4111 assert(scip != NULL);
4112 assert(cons != NULL);
4113 assert(consanddata != NULL);
4114 assert(!SCIPisInfinity(scip, coef) && !SCIPisInfinity(scip, -coef));
4115 assert(!SCIPisInfinity(scip, lhs));
4116 assert(!SCIPisInfinity(scip, -rhs));
4117 assert(SCIPisLE(scip, lhs, rhs));
4118
4119 /* remove rounding locks */
4120 SCIP_CALL( unlockRoundingAndCons(scip, cons, consanddata, coef, lhs, rhs) );
4121
4122 assert(consanddata->cons != NULL);
4123
4124 return SCIP_OKAY;
4125}
4126
4127/** add new locks */
4128static
4130 SCIP*const scip, /**< SCIP data structure */
4131 SCIP_CONS*const cons, /**< pseudoboolean constraint */
4132 CONSANDDATA*const consanddata, /**< CONSANDDATA object for which we want to delete the locks and the
4133 * capture of the corresponding and-constraint */
4134 SCIP_Real const coef, /**< coefficient which lead to new locks */
4135 SCIP_Real const lhs, /**< left hand side which lead to new locks */
4136 SCIP_Real const rhs /**< right hand side which lead to new locks */
4137 )
4138{
4139 assert(scip != NULL);
4140 assert(cons != NULL);
4141 assert(consanddata != NULL);
4142 assert(!SCIPisInfinity(scip, coef) && !SCIPisInfinity(scip, -coef));
4143 assert(!SCIPisInfinity(scip, lhs));
4144 assert(!SCIPisInfinity(scip, -rhs));
4145 assert(SCIPisLE(scip, lhs, rhs));
4146
4147 /* add rounding locks due to old variables in consanddata object */
4148 SCIP_CALL( lockRoundingAndCons(scip, cons, consanddata, coef, lhs, rhs) );
4149
4150 assert(consanddata->cons != NULL);
4151
4152 return SCIP_OKAY;
4153}
4154
4155/** update all locks inside this constraint and all captures on all and-constraints */
4156static
4158 SCIP*const scip, /**< SCIP data structure */
4159 SCIP_CONS*const cons, /**< pseudoboolean constraint */
4160 SCIP_CONSHDLRDATA*const conshdlrdata, /**< pseudoboolean constraint handler data */
4161 SCIP_Real const newlhs, /**< new left hand side of pseudoboolean constraint */
4162 SCIP_Real const newrhs, /**< new right hand side of pseudoboolean constraint */
4163 SCIP_VAR**const andress, /**< new and-resultants in pseudoboolean constraint */
4164 SCIP_Real*const andcoefs, /**< new and-resultants-coeffcients in pseudoboolean constraint */
4165 SCIP_Bool*const andnegs, /**< new negation status of and-resultants in pseudoboolean constraint */
4166 int const nandress /**< number of current and-resultants in pseudoboolean constraint */
4167 )
4168{
4169 CONSANDDATA** newconsanddatas;
4170 int nnewconsanddatas;
4171 int snewconsanddatas;
4172 SCIP_Real* newandcoefs;
4173 SCIP_Real* oldandcoefs;
4174 SCIP_Bool* newandnegs;
4175 SCIP_Bool* oldandnegs;
4176 CONSANDDATA** consanddatas;
4177 int nconsanddatas;
4178 SCIP_CONSDATA* consdata;
4179 int oldnvars;
4180 int c;
4181 int c1;
4182
4183 assert(scip != NULL);
4184 assert(cons != NULL);
4185 assert(conshdlrdata != NULL);
4186 assert(conshdlrdata->hashmap != NULL);
4187 assert(nandress == 0 || (andress != NULL && andcoefs != NULL));
4188 assert(!SCIPisInfinity(scip, newlhs));
4189 assert(!SCIPisInfinity(scip, -newrhs));
4190 assert(SCIPisLE(scip, newlhs, newrhs));
4191
4192 consdata = SCIPconsGetData(cons);
4193 assert(consdata != NULL);
4194
4195 /* sort and-constraints by the problem indices of corresponding and-resultants */
4196 SCIPsortPtrRealBool((void**)(consdata->consanddatas), consdata->andcoefs, consdata->andnegs, resvarCompWithInactive, consdata->nconsanddatas);
4197
4198 /* sort and-resultants by their problem indices */
4199 SCIPsortPtrRealBool((void**)andress, andcoefs, andnegs, resvarComp, nandress);
4200
4201 consanddatas = consdata->consanddatas;
4202 oldandcoefs = consdata->andcoefs;
4203 oldandnegs = consdata->andnegs;
4204 nconsanddatas = consdata->nconsanddatas;
4205 assert(nconsanddatas == 0 || (consanddatas != NULL && oldandcoefs != NULL));
4206
4207 snewconsanddatas = nconsanddatas + nandress;
4208
4209 /* allocate new block memory arrays */
4210 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newconsanddatas, snewconsanddatas) );
4211 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newandcoefs, snewconsanddatas) );
4212 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newandnegs, snewconsanddatas) );
4213
4214 nnewconsanddatas = 0;
4215
4216 /* collect new consanddata objects and update locks and captures */
4217 for( c = 0, c1 = 0; c < nconsanddatas && c1 < nandress; )
4218 {
4219 SCIP_CONS* andcons;
4220 SCIP_VAR* res1;
4221 SCIP_VAR* res2;
4222
4223 assert(consanddatas[c] != NULL);
4224
4225 /* consanddata object could have been deleted in the last presolving round */
4226 if( !consanddatas[c]->istransformed )
4227 {
4228 ++c;
4229 consdata->changed = TRUE;
4230 consdata->upgradetried = FALSE;
4231 continue;
4232 }
4233
4234 andcons = consanddatas[c]->cons;
4235 assert(andcons != NULL);
4236
4237 if( andcons == NULL ) /*lint !e774*/
4238 {
4239 ++c;
4240 consdata->changed = TRUE;
4241 consdata->upgradetried = FALSE;
4242 continue;
4243 }
4244 else if( SCIPconsIsDeleted(andcons) )
4245 {
4246 /* remove rounding locks, because the and constraint was deleted */
4247 SCIP_CALL( unlockRoundingAndCons(scip, cons, consanddatas[c],
4248 oldandnegs[c] ? -oldandcoefs[c] : oldandcoefs[c], consdata->lhs, consdata->rhs) );
4249 ++c;
4250 consdata->changed = TRUE;
4251 consdata->upgradetried = FALSE;
4252 continue;
4253 }
4254 assert(andcons != NULL);
4255
4256 /* get and-resultants of consanddata object in constraint data */
4257 res1 = SCIPgetResultantAnd(scip, andcons);
4258 assert(res1 != NULL);
4259 assert(SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)res1) == consanddatas[c]);
4260
4261 /* get and-resultants in new corresponding linear constraint */
4262 res2 = andress[c1];
4263 assert(res2 != NULL);
4264 assert(SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)res2) != NULL);
4265
4266 /* collect new consanddata objects sorted with respect to the problem index of corresponding and-resultants */
4267 if( SCIPvarGetProbindex(res1) < SCIPvarGetProbindex(res2) )
4268 {
4269 assert(!SCIPisZero(scip, oldandcoefs[c]));
4270 assert(consanddatas[c]->nuses > 0);
4271 --(consanddatas[c]->nuses);
4272
4273 /* remove old locks */
4274 SCIP_CALL( removeOldLocks(scip, cons, consanddatas[c], oldandnegs[c] ? -oldandcoefs[c] : oldandcoefs[c],
4275 consdata->lhs, consdata->rhs) );
4276 ++c;
4277 consdata->changed = TRUE;
4278 consdata->upgradetried = FALSE;
4279 consdata->propagated = FALSE;
4280 consdata->presolved = FALSE;
4281 }
4282 else if( SCIPvarGetProbindex(res1) > SCIPvarGetProbindex(res2) )
4283 {
4284 assert(!SCIPisZero(scip, andcoefs[c1]));
4285 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)res2));
4286 newconsanddatas[nnewconsanddatas] = (CONSANDDATA*) SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)res2);
4287 newandcoefs[nnewconsanddatas] = andcoefs[c1];
4288 newandnegs[nnewconsanddatas] = andnegs[c1];
4289 ++(newconsanddatas[nnewconsanddatas]->nuses);
4290
4291 /* add new locks */
4292 SCIP_CALL( addNewLocks(scip, cons, newconsanddatas[nnewconsanddatas], newandnegs[nnewconsanddatas] ?
4293 -newandcoefs[nnewconsanddatas] : newandcoefs[nnewconsanddatas], newlhs, newrhs) );
4294 ++c1;
4295 consdata->changed = TRUE;
4296 consdata->upgradetried = FALSE;
4297 consdata->cliquesadded = FALSE;
4298 consdata->propagated = FALSE;
4299 consdata->presolved = FALSE;
4300
4301 ++nnewconsanddatas;
4302 }
4303 else
4304 {
4305 SCIP_Bool coefsignchanged;
4306 SCIP_Bool lhschanged;
4307 SCIP_Bool rhschanged;
4308
4309 assert(!SCIPisZero(scip, oldandcoefs[c]));
4310 assert(!SCIPisZero(scip, andcoefs[c1]));
4311 assert(SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)res2) == consanddatas[c]);
4312
4313 /* copy old consanddata object and new coefficent */
4314 newconsanddatas[nnewconsanddatas] = consanddatas[c];
4315
4316 newandcoefs[nnewconsanddatas] = andcoefs[c1];
4317 newandnegs[nnewconsanddatas] = andnegs[c1];
4318
4319 if( ((oldandnegs[c] == andnegs[c1]) && !SCIPisEQ(scip, oldandcoefs[c], newandcoefs[c1]))
4320 || ((oldandnegs[c] != newandnegs[c1]) && !SCIPisEQ(scip, oldandcoefs[c], -newandcoefs[c1])) )
4321 consdata->upgradetried = FALSE;
4322
4323 coefsignchanged = (oldandnegs[c] == andnegs[c1]) &&
4324 ((oldandcoefs[c] < 0 && andcoefs[c1] > 0) || (oldandcoefs[c] > 0 && andcoefs[c1] < 0));
4325 coefsignchanged = coefsignchanged || ((oldandnegs[c] != andnegs[c1]) &&
4326 ((oldandcoefs[c] < 0 && andcoefs[c1] < 0) || (oldandcoefs[c] > 0 && andcoefs[c1] > 0)));
4327 lhschanged = (SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, -newlhs)) || (!SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -newlhs))
4328 || (consdata->lhs < 0 && newlhs > 0) || (consdata->lhs > 0 && newlhs < 0);
4329 rhschanged = (SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, newrhs)) || (!SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, newrhs))
4330 || (consdata->rhs < 0 && newrhs > 0) || (consdata->rhs > 0 && newrhs < 0);
4331
4332 /* update or renew locks */
4333 if( coefsignchanged || lhschanged || rhschanged || newconsanddatas[nnewconsanddatas]->nnewvars > 0)
4334 {
4335 /* renew locks */
4336 SCIP_CALL( removeOldLocks(scip, cons, newconsanddatas[nnewconsanddatas], oldandnegs[c] ?
4337 -oldandcoefs[c] : oldandcoefs[c], consdata->lhs, consdata->rhs) );
4338 SCIP_CALL( addNewLocks(scip, cons, newconsanddatas[nnewconsanddatas], newandnegs[nnewconsanddatas] ?
4339 -newandcoefs[nnewconsanddatas] : newandcoefs[nnewconsanddatas], newlhs, newrhs) );
4340
4341 consdata->changed = TRUE;
4342 consdata->upgradetried = FALSE;
4343 consdata->cliquesadded = FALSE;
4344 consdata->propagated = FALSE;
4345 consdata->presolved = FALSE;
4346 }
4347
4348 ++c;
4349 ++c1;
4350 ++nnewconsanddatas;
4351 }
4352 }
4353
4354 /* add all remaining consanddatas and update locks and captures */
4355 if( c < nconsanddatas )
4356 {
4357 assert(c1 == nandress);
4358
4359 for( ; c < nconsanddatas; ++c )
4360 {
4361 SCIP_CONS* andcons;
4362#ifndef NDEBUG
4363 SCIP_VAR* res1;
4364
4365 assert(consanddatas[c] != NULL);
4366#endif
4367 andcons = consanddatas[c]->cons;
4368#ifndef NDEBUG
4369 if( andcons != NULL )
4370 {
4371 res1 = SCIPgetResultantAnd(scip, andcons);
4372 assert(res1 != NULL);
4373 assert(SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)res1) == consanddatas[c]);
4374 }
4375#endif
4376 if( andcons == NULL )
4377 {
4378 consdata->changed = TRUE;
4379 consdata->upgradetried = FALSE;
4380 continue;
4381 }
4382
4383 assert(consanddatas[c]->nuses > 0);
4384 --(consanddatas[c]->nuses);
4385
4386 /* remove old locks */
4387 SCIP_CALL( removeOldLocks(scip, cons, consanddatas[c], oldandnegs[c] ? -oldandcoefs[c] : oldandcoefs[c],
4388 consdata->lhs, consdata->rhs) );
4389 consdata->changed = TRUE;
4390 consdata->upgradetried = FALSE;
4391 consdata->propagated = FALSE;
4392 consdata->presolved = FALSE;
4393 }
4394 }
4395 else if( c1 < nandress )
4396 {
4397 for( ; c1 < nandress; ++c1 )
4398 {
4399 SCIP_VAR* res2;
4400
4401 res2 = andress[c1];
4402 assert(res2 != NULL);
4403 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)res2));
4404 newconsanddatas[nnewconsanddatas] = (CONSANDDATA*) SCIPhashmapGetImage(conshdlrdata->hashmap, (void*)res2);
4405 newandcoefs[nnewconsanddatas] = andcoefs[c1];
4406 newandnegs[nnewconsanddatas] = andnegs[c1];
4407 ++(newconsanddatas[nnewconsanddatas]->nuses);
4408
4409 /* add new locks */
4410 SCIP_CALL( addNewLocks(scip, cons, newconsanddatas[nnewconsanddatas], newandnegs[nnewconsanddatas] ?
4411 -newandcoefs[nnewconsanddatas] : newandcoefs[nnewconsanddatas], newlhs, newrhs) );
4412
4413 ++nnewconsanddatas;
4414 consdata->changed = TRUE;
4415 consdata->upgradetried = FALSE;
4416 consdata->cliquesadded = FALSE;
4417 consdata->propagated = FALSE;
4418 consdata->presolved = FALSE;
4419 }
4420 }
4421 assert(c == nconsanddatas && c1 == nandress);
4422
4423 /* delete old and-coefficients and consanddata objects */
4424 SCIPfreeBlockMemoryArray(scip, &(consdata->andcoefs), consdata->sconsanddatas);
4425 SCIPfreeBlockMemoryArray(scip, &(consdata->andnegs), consdata->sconsanddatas);
4426 SCIPfreeBlockMemoryArray(scip, &(consdata->consanddatas), consdata->sconsanddatas);
4427
4428 if( !SCIPisEQ(scip, consdata->lhs, newlhs) || !SCIPisEQ(scip, consdata->rhs, newrhs) )
4429 {
4430 consdata->upgradetried = FALSE;
4431 consdata->lhs = newlhs;
4432 consdata->rhs = newrhs;
4433 }
4434
4435 consdata->consanddatas = newconsanddatas;
4436 consdata->andcoefs = newandcoefs;
4437 consdata->andnegs = newandnegs;
4438 consdata->nconsanddatas = nnewconsanddatas;
4439 consdata->sconsanddatas = snewconsanddatas;
4440
4441 oldnvars = consdata->nlinvars;
4442 /* update number of linear variables without and-resultants */
4443 SCIP_CALL( getLinearConsNVars(scip, consdata->lincons, consdata->linconstype, &(consdata->nlinvars)) );
4444 consdata->nlinvars -= nnewconsanddatas;
4445
4446 if( oldnvars != consdata->nlinvars )
4447 {
4448 consdata->changed = TRUE;
4449 consdata->upgradetried = FALSE;
4450 consdata->cliquesadded = FALSE;
4451 consdata->propagated = FALSE;
4452 consdata->presolved = FALSE;
4453 }
4454
4455#ifndef NDEBUG
4456 consanddatas = consdata->consanddatas;
4457 nconsanddatas = consdata->nconsanddatas;
4458 assert(nconsanddatas == 0 || consanddatas != NULL);
4459
4460 /* check that consanddata objects are sorted with respect to the problem index of the corresponding resultants */
4461 for( c = nconsanddatas - 1; c > 0; --c )
4462 {
4463 SCIP_VAR* res1;
4464 SCIP_VAR* res2;
4465
4466 assert(consanddatas[c] != NULL);
4467 assert(consanddatas[c]->cons != NULL);
4468 res1 = SCIPgetResultantAnd(scip, consanddatas[c]->cons);
4469 assert(res1 != NULL);
4470 assert(consanddatas[c - 1] != NULL);
4471 assert(consanddatas[c - 1]->cons != NULL);
4472 res2 = SCIPgetResultantAnd(scip, consanddatas[c - 1]->cons);
4473 assert(res2 != NULL);
4474
4475 assert(SCIPvarGetProbindex(res1) > SCIPvarGetProbindex(res2));
4476 }
4477#endif
4478
4479 return SCIP_OKAY;
4480}
4481
4482/** adds cliques of the pseudoboolean constraint to the global clique table */
4483static
4485 SCIP*const scip, /**< SCIP data structure */
4486 SCIP_CONS*const cons, /**< pseudoboolean constraint */
4487 SCIP_Bool*const cutoff, /**< pointer to store whether the node can be cut off */
4488 int*const naggrvars, /**< pointer to count the number of aggregated variables */
4489 int*const nchgbds /**< pointer to count the number of performed bound changes */
4490 )
4491{
4492 SCIP_CONSDATA* consdata;
4493 SCIP_VAR** vars;
4494 int nvars;
4495 SCIP_VAR** linvars;
4496 SCIP_VAR* andres;
4497 SCIP_VAR* andres2;
4498 int nlinvars;
4499 int nandress;
4500 int c;
4501 int v2;
4502 int v1;
4503 int nchgbdslocal;
4504
4505 assert(scip != NULL);
4506 assert(cons != NULL);
4507 assert(cutoff != NULL);
4508 assert(naggrvars != NULL);
4509 assert(nchgbds != NULL);
4510 assert(SCIPconsIsActive(cons));
4511
4512 *cutoff = FALSE;
4513
4514 consdata = SCIPconsGetData(cons);
4515 assert(consdata != NULL);
4516 /* if we have no and-constraints left, we should not be here and this constraint should be deleted (only the linaer should survive) */
4517 assert(consdata->nconsanddatas > 0);
4518
4519 /* check whether the cliques have already been added */
4520 if( consdata->cliquesadded )
4521 return SCIP_OKAY;
4522
4523 consdata->cliquesadded = TRUE;
4524
4526
4527 /* check standard pointers and sizes */
4528 assert(consdata->lincons != NULL);
4529 assert(SCIPconsIsActive(consdata->lincons));
4530 assert(consdata->linconstype > SCIP_LINEARCONSTYPE_INVALIDCONS);
4531 assert(consdata->consanddatas != NULL);
4532 assert(consdata->nconsanddatas > 0);
4533 assert(consdata->nconsanddatas <= consdata->sconsanddatas);
4534
4535 /* check number of linear variables */
4536 SCIP_CALL( getLinearConsNVars(scip, consdata->lincons, consdata->linconstype, &nvars) );
4537 assert(nvars == consdata->nlinvars + consdata->nconsanddatas);
4538
4539 /* get temporary memory */
4540 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4541 SCIP_CALL( SCIPallocBufferArray(scip, &linvars, nvars) );
4542
4543 /* get variables and coefficients */
4544 SCIP_CALL( getLinearConsVarsData(scip, consdata->lincons, consdata->linconstype, vars, NULL, &nvars) );
4545
4546 /* calculate all not artificial linear variables and all artificial and-resultants
4547 * @todo should we take into accout the negation status of the cliques?
4548 */
4549 SCIP_CALL( getLinVarsAndAndRess(scip, cons, vars, NULL, nvars, linvars, NULL, &nlinvars,
4550 NULL, NULL, NULL, &nandress) );
4551
4552 assert(nandress == consdata->nconsanddatas);
4553 assert(consdata->consanddatas != NULL);
4554
4555 /* find cliques from linear variable to and-resultant */
4556 for( c = nandress - 1; c >= 0; --c )
4557 {
4558 CONSANDDATA* consanddata;
4559 SCIP_VAR** andvars;
4560 int nandvars;
4561
4562 consanddata = consdata->consanddatas[c];
4563 assert(consanddata != NULL);
4564
4565 andres = SCIPgetResultantAnd(scip, consanddata->cons);
4566
4567 /* choose correct variable array */
4568 if( consanddata->nnewvars > 0 )
4569 {
4570 andvars = consanddata->newvars;
4571 nandvars = consanddata->nnewvars;
4572 }
4573 else
4574 {
4575 andvars = consanddata->vars;
4576 nandvars = consanddata->nvars;
4577 }
4578
4579 for( v1 = nandvars - 1; v1 >= 0; --v1 )
4580 {
4581 SCIP_VAR* var1;
4582 SCIP_Bool values[2];
4583
4584 var1 = andvars[v1];
4585 if( !SCIPvarIsActive(var1) && (!SCIPvarIsNegated(var1) || !SCIPvarIsActive(SCIPvarGetNegationVar(var1))) )
4586 continue;
4587
4588 /* get active counterpart to check for common cliques */
4590 {
4591 var1 = SCIPvarGetNegationVar(var1);
4592 values[0] = FALSE;
4593 }
4594 else
4595 values[0] = TRUE;
4596
4597 for( v2 = nlinvars - 1; v2 >= 0; --v2 )
4598 {
4599 SCIP_VAR* var2;
4600
4601 var2 = linvars[v2];
4602 if( !SCIPvarIsActive(var2) && (!SCIPvarIsNegated(var2) || !SCIPvarIsActive(SCIPvarGetNegationVar(var2))) )
4603 continue;
4604
4605 /* get active counterpart to check for common cliques */
4607 {
4608 var2 = SCIPvarGetNegationVar(var2);
4609 values[1] = FALSE;
4610 }
4611 else
4612 values[1] = TRUE;
4613
4614 /* if variable in and-constraint1 is the negated variable of a normal linear variable, than we can add a
4615 * clique between the and-resultant and the normal linear variable, negated variables are not save in
4616 * cliquetables
4617 *
4618 * set r_1 = var1 * z; (z is some product)
4619 * var1 == ~var2
4620 *
4621 * if:
4622 * var1 + ~var1 <= 1; r_1
4623 * 0 + 1 <= 1 0 \
4624 * 1 + 0 <= 1 ==> 1 or 0 > ==> r_1 + var2 <= 1
4625 * 0 + 0 <= 1 0 /
4626 */
4627 if( values[0] != values[1] && var1 == var2 )
4628 {
4629 SCIP_CONS* newcons;
4630 SCIP_VAR* clqvars[2];
4631 char consname[SCIP_MAXSTRLEN];
4632
4633 clqvars[0] = andres;
4634 clqvars[1] = values[1] ? var2 : SCIPvarGetNegatedVar(var2);
4635 assert(clqvars[1] != NULL);
4636
4637 /* @todo: check whether it is better to only add the clique or to add the setppc constraint or do both */
4638
4639 /* add clique */
4640 SCIP_CALL( SCIPaddClique(scip, clqvars, NULL, 2, FALSE, cutoff, &nchgbdslocal) );
4641 if( *cutoff )
4642 goto TERMINATE;
4643
4644 *nchgbds += nchgbdslocal;
4645
4646 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_clq_%s_%s", SCIPconsGetName(cons), SCIPvarGetName(clqvars[0]), SCIPvarGetName(clqvars[1]) );
4647 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, consname, 2, clqvars,
4652
4653 SCIP_CALL( SCIPaddCons(scip, newcons) );
4654 SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
4655 SCIPdebugPrintCons(scip, newcons, NULL);
4656
4657 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4658 }
4659 /* if a variable in an and-constraint is in a clique with another normal linear variable, we can add the
4660 * clique between the linear variable and the and-resultant
4661 *
4662 * set r_1 = var1 * z; (z is some product)
4663 *
4664 * if:
4665 * var1 + var2 <= 1; r_1
4666 * 0 + 1 <= 1 0 \
4667 * 1 + 0 <= 1 ==> 1 or 0 > ==> r_1 + var2 <= 1
4668 * 0 + 0 <= 1 0 /
4669 */
4670 if( (var1 != var2) && SCIPvarsHaveCommonClique(var1, values[0], var2, values[1], TRUE) )
4671 {
4672 SCIP_CONS* newcons;
4673 SCIP_VAR* clqvars[2];
4674 char consname[SCIP_MAXSTRLEN];
4675
4676 clqvars[0] = andres;
4677 clqvars[1] = values[1] ? var2 : SCIPvarGetNegatedVar(var2);
4678 assert(clqvars[1] != NULL);
4679
4680 /* @todo: check whether it is better to only add the clique or to add the setppc constraint or do both */
4681
4682 /* add clique */
4683 SCIP_CALL( SCIPaddClique(scip, clqvars, NULL, 2, FALSE, cutoff, &nchgbdslocal) );
4684 if( *cutoff )
4685 goto TERMINATE;
4686
4687 *nchgbds += nchgbdslocal;
4688
4689 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_clq_%s_%s", SCIPconsGetName(cons), SCIPvarGetName(clqvars[0]), SCIPvarGetName(clqvars[1]) );
4690 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, consname, 2, clqvars,
4695
4696 SCIP_CALL( SCIPaddCons(scip, newcons) );
4697 SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
4698 SCIPdebugPrintCons(scip, newcons, NULL);
4699
4700 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4701 }
4702 }
4703 }
4704 }
4705
4706 /* find cliques over variables which are in different and-constraints */
4707 for( c = nandress - 1; c > 0; --c )
4708 {
4709 CONSANDDATA* consanddata1;
4710 CONSANDDATA* consanddata2;
4711 SCIP_VAR** andvars1;
4712 int nandvars1;
4713 SCIP_VAR** andvars2;
4714 int nandvars2;
4715
4716 consanddata1 = consdata->consanddatas[c];
4717 assert(consanddata1 != NULL);
4718 consanddata2 = consdata->consanddatas[c - 1];
4719 assert(consanddata2 != NULL);
4720
4721 andres = SCIPgetResultantAnd(scip, consanddata1->cons);
4722 andres2 = SCIPgetResultantAnd(scip, consanddata2->cons);
4723
4724 /* choose correct variable array of consanddata object 1 */
4725 if( consanddata1->nnewvars > 0 )
4726 {
4727 andvars1 = consanddata1->newvars;
4728 nandvars1 = consanddata1->nnewvars;
4729 }
4730 else
4731 {
4732 andvars1 = consanddata1->vars;
4733 nandvars1 = consanddata1->nvars;
4734 }
4735
4736 /* choose correct variable array of consanddata object 2 */
4737 if( consanddata2->nnewvars > 0 )
4738 {
4739 andvars2 = consanddata2->newvars;
4740 nandvars2 = consanddata2->nnewvars;
4741 }
4742 else
4743 {
4744 andvars2 = consanddata2->vars;
4745 nandvars2 = consanddata2->nvars;
4746 }
4747
4748 /* compare both terms for finding new aggregated variables and new cliques */
4749 for( v1 = nandvars1 - 1; v1 >= 0; --v1 )
4750 {
4751 SCIP_VAR* var1;
4752 SCIP_Bool values[2];
4753
4754 var1 = andvars1[v1];
4755 if( !SCIPvarIsActive(var1) && (!SCIPvarIsNegated(var1) || !SCIPvarIsActive(SCIPvarGetNegationVar(var1))) )
4756 continue;
4757
4758 /* get active counterpart to check for common cliques */
4760 {
4761 var1 = SCIPvarGetNegationVar(var1);
4762 values[0] = FALSE;
4763 }
4764 else
4765 values[0] = TRUE;
4766
4767 for( v2 = nandvars2 - 1; v2 >= 0; --v2 )
4768 {
4769 SCIP_VAR* var2;
4770
4771 var2 = andvars2[v2];
4772 if( !SCIPvarIsActive(var2) && (!SCIPvarIsNegated(var2) || !SCIPvarIsActive(SCIPvarGetNegationVar(var2))) )
4773 continue;
4774
4775 /* get active counterpart to check for common cliques */
4777 {
4778 var2 = SCIPvarGetNegationVar(var2);
4779 values[1] = FALSE;
4780 }
4781 else
4782 values[1] = TRUE;
4783
4784 /* if a variable in and-constraint1 is the negated variable of a variable in and-constraint2, than we can
4785 * add a clique between both and-resultants, negated variables are not save in cliquetables
4786 *
4787 * set r_1 = var1 * z_1; (z_1 is some product)
4788 * set r_2 = var2 * z_2; (z_2 is some product)
4789 * var1 == ~var2
4790 *
4791 * if:
4792 * var1 + ~var1 <= 1; r_1 r_2
4793 * 0 + 1 <= 1 0 1 or 0 \
4794 * 1 + 0 <= 1 ==> 1 or 0 0 > ==> r_1 + r_2 <= 1
4795 * 0 + 0 <= 1 0 0 /
4796 */
4797 if( values[0] != values[1] && var1 == var2 )
4798 {
4799 SCIP_CONS* newcons;
4800 SCIP_VAR* clqvars[2];
4801 char consname[SCIP_MAXSTRLEN];
4802
4803 clqvars[0] = andres;
4804 clqvars[1] = andres2;
4805
4806 /* @todo: check whether it is better to only add the clique or to add the setppc constraint or do both */
4807
4808 /* add clique */
4809 SCIP_CALL( SCIPaddClique(scip, clqvars, NULL, 2, FALSE, cutoff, &nchgbdslocal) );
4810 if( *cutoff )
4811 goto TERMINATE;
4812
4813 *nchgbds += nchgbdslocal;
4814
4815 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_clq_%s_%s", SCIPconsGetName(cons), SCIPvarGetName(clqvars[0]), SCIPvarGetName(clqvars[1]) );
4816 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, consname, 2, clqvars,
4821
4822 SCIP_CALL( SCIPaddCons(scip, newcons) );
4823 SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
4824 SCIPdebugPrintCons(scip, newcons, NULL);
4825
4826 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4827 }
4828 /* if a variable in an and-constraint is in a clique with a variable in another and-constraint, we can add
4829 * the clique between both and-resultant
4830 *
4831 * let r_1 = var1 * z_1; (z_1 is some product)
4832 * let r_2 = var2 * z_2; (z_2 is some product)
4833 *
4834 * if:
4835 * var1 + var2 <= 1; r_1 r_2
4836 * 0 + 1 <= 1 0 1 or 0 \
4837 * 1 + 0 <= 1 ==> 1 or 0 0 > ==> r_1 + r_2 <= 1
4838 * 0 + 0 <= 1 0 0 /
4839 */
4840 else if( SCIPvarsHaveCommonClique(var1, values[0], var2, values[1], TRUE) && (var1 != var2) )
4841 {
4842 SCIP_CONS* newcons;
4843 SCIP_VAR* clqvars[2];
4844 char consname[SCIP_MAXSTRLEN];
4845
4846 clqvars[0] = andres;
4847 clqvars[1] = values[1] ? var2 : SCIPvarGetNegatedVar(var2);
4848 assert(clqvars[1] != NULL);
4849
4850 /* @todo: check whether it is better to only add the clique or to add the setppc constraint or do both */
4851
4852 /* add clique */
4853 SCIP_CALL( SCIPaddClique(scip, clqvars, NULL, 2, FALSE, cutoff, &nchgbdslocal) );
4854 if( *cutoff )
4855 goto TERMINATE;
4856
4857 *nchgbds += nchgbdslocal;
4858
4859 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_clq_%s_%s", SCIPconsGetName(cons), SCIPvarGetName(clqvars[0]), SCIPvarGetName(clqvars[1]) );
4860 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, consname, 2, clqvars,
4865
4866 SCIP_CALL( SCIPaddCons(scip, newcons) );
4867 SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
4868 SCIPdebugPrintCons(scip, newcons, NULL);
4869
4870 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4871 }
4872 }
4873 }
4874 }
4875
4876 TERMINATE:
4877 /* free temporary memory */
4878 SCIPfreeBufferArray(scip, &linvars);
4879 SCIPfreeBufferArray(scip, &vars);
4880
4881 return SCIP_OKAY;
4882}
4883
4884/** propagation method for pseudoboolean constraints */
4885static
4887 SCIP*const scip, /**< SCIP data structure */
4888 SCIP_CONS*const cons, /**< knapsack constraint */
4889 SCIP_Bool*const cutoff, /**< pointer to store whether the node can be cut off */
4890 int*const ndelconss /**< pointer to count number of deleted constraints */
4891 )
4892{
4893 SCIP_CONSDATA* consdata;
4894
4895 assert(scip != NULL);
4896 assert(cons != NULL);
4897 assert(cutoff != NULL);
4898 assert(ndelconss != NULL);
4899
4900 *cutoff = FALSE;
4901
4902 consdata = SCIPconsGetData(cons);
4903 assert(consdata != NULL);
4904 assert(consdata->lincons != NULL);
4905
4906 /* if linear constraint is redundant, than pseudoboolean constraint is redundant too */
4907 if( SCIPconsIsDeleted(consdata->lincons) )
4908 {
4910 ++(*ndelconss);
4911 }
4912
4913 /* check if the constraint was already propagated */
4914 if( consdata->propagated )
4915 return SCIP_OKAY;
4916
4917 /* mark the constraint propagated */
4918 consdata->propagated = TRUE;
4919
4920 return SCIP_OKAY;
4921}
4922
4923/** update and-constraint flags due to pseudoboolean constraint flags */
4924static
4926 SCIP*const scip, /**< SCIP data structure */
4927 SCIP_CONS*const cons /**< pseudoboolean constraint */
4928 )
4929{
4930 CONSANDDATA** consanddatas;
4931 int nconsanddatas;
4932 SCIP_CONSDATA* consdata;
4933 int c;
4934
4935 assert(scip != NULL);
4936 assert(cons != NULL);
4937
4938 consdata = SCIPconsGetData(cons);
4939 assert(consdata != NULL);
4940
4941 consanddatas = consdata->consanddatas;
4942 nconsanddatas = consdata->nconsanddatas;
4943 assert(nconsanddatas == 0 || consanddatas != NULL);
4944
4945 if( !SCIPconsIsActive(cons) )
4946 return SCIP_OKAY;
4947
4948 /* release and-constraints and change check flag of and-constraint */
4949 for( c = nconsanddatas - 1; c >= 0; --c )
4950 {
4951 SCIP_CONS* andcons;
4952
4953 assert(consanddatas[c] != NULL);
4954
4955 if( !consanddatas[c]->istransformed )
4956 continue;
4957
4958 andcons = consanddatas[c]->cons;
4959 assert(andcons != NULL);
4960
4962 }
4963
4964 return SCIP_OKAY;
4965}
4966
4967/** delete unused information in constraint handler data */
4968static
4970 SCIP*const scip, /**< SCIP data structure */
4971 SCIP_CONSHDLRDATA*const conshdlrdata, /**< pseudoboolean constraint handler data */
4972 int*const ndelconss /**< pointer to count number of deleted constraints */
4973 )
4974{
4975 CONSANDDATA** allconsanddatas;
4976 CONSANDDATA* consanddata;
4977 SCIP_VAR** fixedvars = SCIPgetFixedVars(scip);
4978 SCIP_VAR** activevars;
4979 SCIP_Real* activescalars;
4980 SCIP_Real activeconstant;
4981 int nvars = SCIPgetNVars(scip);
4982 int nfixedvars = SCIPgetNFixedVars(scip);
4983 int c;
4984
4985 assert(scip != NULL);
4986 assert(conshdlrdata != NULL);
4987 assert(ndelconss != NULL);
4988
4989 allconsanddatas = conshdlrdata->allconsanddatas;
4990 assert(allconsanddatas != NULL);
4991 assert(conshdlrdata->nallconsanddatas >= 1);
4992 assert(conshdlrdata->nallconsanddatas <= conshdlrdata->sallconsanddatas);
4993
4994 if( nfixedvars >= 1 && nvars >= 1 )
4995 {
4996 SCIP_CALL( SCIPallocBufferArray(scip, &activevars, nvars) );
4997 SCIP_CALL( SCIPallocBufferArray(scip, &activescalars, nvars) );
4998 }
4999 else
5000 {
5001 activevars = NULL;
5002 activescalars = NULL;
5003 }
5004
5005 for( c = conshdlrdata->nallconsanddatas - 1; c >= 0; --c )
5006 {
5007 SCIP_VAR** tmpvars;
5008 int stmpvars;
5009 SCIP_CONS* cons;
5010 int v;
5011
5012 consanddata = allconsanddatas[c];
5013
5014 assert(consanddata->nvars == 0 || (consanddata->vars != NULL && consanddata->svars > 0));
5015 assert(consanddata->nnewvars == 0 || (consanddata->newvars != NULL && consanddata->snewvars > 0));
5016
5017 if( !consanddata->istransformed )
5018 {
5019 assert(consanddata->vars == NULL || consanddata->origcons != NULL);
5020 assert(consanddata->nvars == 0 || consanddata->origcons != NULL);
5021 assert(consanddata->svars == 0 || consanddata->origcons != NULL);
5022 assert(consanddata->newvars == NULL);
5023 assert(consanddata->nnewvars == 0);
5024 assert(consanddata->snewvars == 0);
5025
5026 continue;
5027 }
5028
5029 /* if no variables are left, delete variables arrays */
5030 if( consanddata->nvars == 0 )
5031 {
5032 SCIP_VAR* resvar = SCIPgetResultantAnd(scip, consanddata->cons);
5033
5034 /* if we have no old variables, than also no new variables */
5035 assert(consanddata->nnewvars == 0);
5036 assert(consanddata->nuses > 0);
5037 assert(resvar != NULL);
5038
5039 /* delete and-constraint */
5040 SCIP_CALL( SCIPdelCons(scip, consanddata->cons) );
5041 ++(*ndelconss);
5042
5043 SCIP_CALL( transformToOrig(scip, consanddata, conshdlrdata) );
5044
5045 /* release and-constraint */
5046 SCIP_CALL( SCIPreleaseCons(scip, &consanddata->cons) );
5047 consanddata->nuses = 0;
5048
5049 /* remove consanddata from hashtable, if it existed only in transformed space */
5050 if( consanddata->origcons == NULL )
5051 {
5052 assert(SCIPhashtableExists(conshdlrdata->hashtable, (void*)consanddata));
5053 SCIP_CALL( SCIPhashtableRemove(conshdlrdata->hashtable, (void*)consanddata) );
5054 }
5055 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)resvar));
5056 SCIP_CALL( SCIPhashmapRemove(conshdlrdata->hashmap, (void*)resvar) );
5057
5058 continue;
5059 }
5060
5061 /* the consanddata object is not used anymore, so extract the and constraint and delete other data */
5062 if( consanddata->nuses == 0 )
5063 {
5064 SCIP_Bool looseorcolumn;
5065 SCIP_VARSTATUS varstatus;
5066
5067 if( consanddata->cons == NULL )
5068 {
5069 assert(!consanddata->istransformed || consanddata->noriguses > 0);
5070 assert((consanddata->noriguses > 0) == (consanddata->origcons != NULL));
5071 assert(consanddata->vars == NULL || consanddata->origcons != NULL);
5072 assert(consanddata->nvars == 0 || consanddata->origcons != NULL);
5073 assert(consanddata->svars == 0 || consanddata->origcons != NULL);
5074 assert(consanddata->newvars == NULL);
5075 assert(consanddata->nnewvars == 0);
5076 assert(consanddata->snewvars == 0);
5077
5078 continue;
5079 }
5080
5081 SCIP_CALL( transformToOrig(scip, consanddata, conshdlrdata) );
5082
5083 varstatus = SCIPvarGetStatus(SCIPgetResultantAnd(scip, consanddata->cons));
5084 looseorcolumn = (varstatus == SCIP_VARSTATUS_LOOSE || varstatus == SCIP_VARSTATUS_COLUMN);
5085
5086 /* @note due to aggregations or fixings the resultant may need to be propagated later on, so we can only
5087 * delete the and-constraint if the resultant is of column or loose status
5088 * and is not an active variable of another (multi-)aggregated/negated variable
5089 */
5090 if( looseorcolumn )
5091 {
5092 SCIP_VAR* resvar = SCIPgetResultantAnd(scip, consanddata->cons);
5093 SCIP_Bool del = TRUE;
5094 int w;
5095
5096 assert(nvars >= 1);
5097
5098 /* we need to check all active representatives */
5099 for( w = 0; w < nfixedvars && del; ++w )
5100 {
5101 int nactivevars;
5102 int requiredsize;
5103 int i;
5104
5105 assert(fixedvars != NULL);
5106 assert(activevars != NULL);
5107 assert(activescalars != NULL);
5108 activevars[0] = fixedvars[w];
5109 activescalars[0] = 1.0;
5110 activeconstant = 0.0;
5111 nactivevars = 1;
5112 SCIP_CALL( SCIPgetProbvarLinearSum(scip, activevars, activescalars, &nactivevars, nvars,
5113 &activeconstant, &requiredsize, TRUE) );
5114 assert(requiredsize <= nvars);
5115
5116 for( i = 0; i < nactivevars && del; ++i )
5117 {
5118 assert(SCIPvarGetStatus(activevars[i]) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(activevars[i]) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(activevars[i]) == SCIP_VARSTATUS_FIXED);
5119
5120 if( activevars[i] == resvar )
5121 del = FALSE;
5122 }
5123 }
5124
5125 if( del )
5126 {
5127 SCIP_CALL( SCIPdelCons(scip, consanddata->cons) );
5128 }
5129 }
5130
5131 if( !SCIPconsIsDeleted(consanddata->cons) )
5132 {
5133 /* change flags */
5134 if( !looseorcolumn )
5135 {
5136 SCIP_CALL( SCIPsetConsInitial(scip, consanddata->cons, FALSE) );
5137#if 0
5138 SCIP_CALL( SCIPsetConsSeparated(scip, consanddata->cons, FALSE) );
5139#endif
5140 }
5141 SCIP_CALL( SCIPsetConsChecked(scip, consanddata->cons, TRUE) );
5142 }
5143
5144 /* remove consanddata from hashtable, if it existed only in transformed space */
5145 if( consanddata->origcons == NULL )
5146 {
5147 assert(SCIPhashtableExists(conshdlrdata->hashtable, (void*)consanddata));
5148 SCIP_CALL( SCIPhashtableRemove(conshdlrdata->hashtable, (void*)consanddata) );
5149 }
5150 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddata->cons)));
5151 SCIP_CALL( SCIPhashmapRemove(conshdlrdata->hashmap, (void*)SCIPgetResultantAnd(scip, consanddata->cons)) );
5152
5153 SCIP_CALL( SCIPreleaseCons(scip, &(consanddata->cons)) );
5154 ++(*ndelconss);
5155
5156 continue;
5157 }
5158
5159 cons = consanddata->cons;
5160 assert(cons != NULL);
5161
5162 /* if and-constraint is deleted, delete variables arrays */
5163 if( SCIPconsIsDeleted(cons) )
5164 {
5165 SCIP_VAR* resvar = SCIPgetResultantAnd(scip, consanddata->cons);
5166
5167 assert(consanddata->nuses > 0);
5168 assert(resvar != NULL);
5169
5170 SCIP_CALL( transformToOrig(scip, consanddata, conshdlrdata) );
5171
5172 /* release and-constraint */
5173 SCIP_CALL( SCIPreleaseCons(scip, &consanddata->cons) );
5174 consanddata->nuses = 0;
5175
5176 /* remove consanddata from hashtable, if it existed only in transformed space */
5177 if( consanddata->origcons == NULL )
5178 {
5179 assert(SCIPhashtableExists(conshdlrdata->hashtable, (void*)consanddata));
5180 SCIP_CALL( SCIPhashtableRemove(conshdlrdata->hashtable, (void*)consanddata) );
5181 }
5182 assert(SCIPhashmapExists(conshdlrdata->hashmap, (void*)resvar));
5183 SCIP_CALL( SCIPhashmapRemove(conshdlrdata->hashmap, (void*)resvar) );
5184
5185 continue;
5186 }
5187
5188 /* if no new variables exist, we do not need to do anything here */
5189 if( consanddata->nnewvars == 0 )
5190 continue;
5191
5192 tmpvars = consanddata->vars;