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