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