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