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