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