Scippy

SCIP

Solving Constraint Integer Programs

cons_xor.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_xor.c
17  * @brief Constraint handler for "xor" constraints, \f$rhs = x_1 \oplus x_2 \oplus \dots \oplus x_n\f$
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  * @author Marc Pfetsch
21  * @author Michael Winkler
22  *
23  * This constraint handler deals with "xor" constraint. These are constraint of the form:
24  *
25  * \f[
26  * rhs = x_1 \oplus x_2 \oplus \dots \oplus x_n
27  * \f]
28  *
29  * where \f$x_i\f$ is a binary variable for all \f$i\f$ and \f$rhs\f$ is bool. The variables \f$x\f$'s are called
30  * operators. This constraint is satisfied if \f$rhs\f$ is TRUE and an odd number of the operators are TRUE or if the
31  * \f$rhs\f$ is FALSE and a even number of operators are TRUE. Hence, if the sum of \f$rhs\f$ and operators is even.
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 #include <string.h>
38 
39 #include "scip/pub_misc.h"
40 #include "scip/cons_xor.h"
41 #include "scip/cons_setppc.h"
42 #include "scip/cons_linear.h"
43 #include "scip/heur_trysol.h"
44 #include "scip/debug.h"
45 
46 
47 /* constraint handler properties */
48 #define CONSHDLR_NAME "xor"
49 #define CONSHDLR_DESC "constraint handler for xor constraints: r = xor(x1, ..., xn)"
50 #define CONSHDLR_SEPAPRIORITY +850200 /**< priority of the constraint handler for separation */
51 #define CONSHDLR_ENFOPRIORITY -850200 /**< priority of the constraint handler for constraint enforcing */
52 #define CONSHDLR_CHECKPRIORITY -850200 /**< priority of the constraint handler for checking feasibility */
53 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
54 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
55 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
56  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
57 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
58 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
59 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
60 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
61 
62 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
63 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
64 
65 #define EVENTHDLR_NAME "xor"
66 #define EVENTHDLR_DESC "event handler for xor constraints"
67 
68 #define LINCONSUPGD_PRIORITY +600000 /**< priority of the constraint handler for upgrading of linear constraints */
69 
70 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
71 #define DEFAULT_ADDEXTENDEDFORM FALSE /**< should the extended formulation be added in presolving? */
72 #define DEFAULT_ADDFLOWEXTENDED FALSE /**< should the extended flow formulation be added (nonsymmetric formulation otherwise)? */
73 #define DEFAULT_SEPARATEPARITY FALSE /**< should parity inequalities be separated? */
74 #define DEFAULT_GAUSSPROPFREQ 5 /**< frequency for applying the Gauss propagator */
75 #define HASHSIZE_XORCONS 500 /**< minimal size of hash table in logicor constraint tables */
76 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
77 #define NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
78 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
79 #define MAXXORCONSSSYSTEM 1000 /**< maximal number of active constraints for which checking the system over GF2 is performed */
80 #define MAXXORVARSSYSTEM 1000 /**< maximal number of variables in xor constraints for which checking the system over GF2 is performed */
81 
82 #define NROWS 5
83 
84 
85 /*
86  * Data structures
87  */
88 
89 /** type used for matrix entries in function checkGauss() */
90 typedef unsigned short Type;
91 
92 /** constraint data for xor constraints */
93 struct SCIP_ConsData
94 {
95  SCIP_VAR** vars; /**< variables in the xor operation */
96  SCIP_VAR* intvar; /**< internal variable for LP relaxation */
97  SCIP_VAR** extvars; /**< variables in extended (flow|asymmetric) formulation (order for flow formulation: nn, ns, sn, ss) */
98  SCIP_ROW* rows[NROWS]; /**< rows for linear relaxation of xor constraint */
99  int nvars; /**< number of variables in xor operation */
100  int nextvars; /**< number of variables in extended flow formulation */
101  int varssize; /**< size of vars array */
102  int extvarssize; /**< size of extvars array */
103  int watchedvar1; /**< position of first watched operator variable */
104  int watchedvar2; /**< position of second watched operator variable */
105  int filterpos1; /**< event filter position of first watched operator variable */
106  int filterpos2; /**< event filter position of second watched operator variable */
107  SCIP_Bool rhs; /**< right hand side of the constraint */
108  unsigned int deleteintvar:1; /**< should artificial variable be deleted */
109  unsigned int propagated:1; /**< is constraint already preprocessed/propagated? */
110  unsigned int sorted:1; /**< are the constraint's variables sorted? */
111  unsigned int changed:1; /**< was constraint changed since last pair preprocessing round? */
112 };
113 
114 /** constraint handler data */
115 struct SCIP_ConshdlrData
116 {
117  SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */
118  SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
119  SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance? */
120  SCIP_Bool addextendedform; /**< should the extended formulation be added in presolving? */
121  SCIP_Bool addflowextended; /**< should the extended flow formulation be added (nonsymmetric formulation otherwise)? */
122  SCIP_Bool separateparity; /**< should parity inequalities be separated? */
123  int gausspropfreq; /**< frequency for applying the Gauss propagator */
124 };
125 
126 
127 /*
128  * Propagation rules
129  */
130 
131 enum Proprule
132 {
133  PROPRULE_0, /**< all variables are fixed => fix integral variable */
134  PROPRULE_1, /**< all except one variable fixed => fix remaining variable */
135  PROPRULE_INTLB, /**< lower bound propagation of integral variable */
136  PROPRULE_INTUB, /**< upper bound propagation of integral variable */
137  PROPRULE_INVALID /**< propagation was applied without a specific propagation rule */
138 };
139 typedef enum Proprule PROPRULE;
141 
142 /*
143  * Local methods
144  */
145 
146 /** installs rounding locks for the given variable in the given xor constraint */
147 static
149  SCIP* scip, /**< SCIP data structure */
150  SCIP_CONS* cons, /**< xor constraint */
151  SCIP_VAR* var /**< variable of constraint entry */
152  )
153 {
154  /* rounding in both directions may violate the constraint */
155  SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
156 
157  return SCIP_OKAY;
158 }
159 
160 /** removes rounding locks for the given variable in the given xor constraint */
161 static
163  SCIP* scip, /**< SCIP data structure */
164  SCIP_CONS* cons, /**< xor constraint */
165  SCIP_VAR* var /**< variable of constraint entry */
166  )
167 {
168  /* rounding in both directions may violate the constraint */
169  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
170 
171  return SCIP_OKAY;
172 }
173 
174 /** creates constraint handler data */
175 static
177  SCIP* scip, /**< SCIP data structure */
178  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
179  SCIP_EVENTHDLR* eventhdlr /**< event handler */
180  )
181 {
182  assert(scip != NULL);
183  assert(conshdlrdata != NULL);
184  assert(eventhdlr != NULL);
185 
186  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
187 
188  /* set event handler for catching events on watched variables */
189  (*conshdlrdata)->eventhdlr = eventhdlr;
190 
191  return SCIP_OKAY;
192 }
193 
194 /** frees constraint handler data */
195 static
197  SCIP* scip, /**< SCIP data structure */
198  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
199  )
200 {
201  assert(conshdlrdata != NULL);
202  assert(*conshdlrdata != NULL);
203 
204  SCIPfreeBlockMemory(scip, conshdlrdata);
205 
206  return SCIP_OKAY;
207 }
208 
209 /** stores the given variable numbers as watched variables, and updates the event processing */
210 static
212  SCIP* scip, /**< SCIP data structure */
213  SCIP_CONSDATA* consdata, /**< xor constraint data */
214  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
215  int watchedvar1, /**< new first watched variable */
216  int watchedvar2 /**< new second watched variable */
217  )
218 {
219  assert(consdata != NULL);
220  assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
221  assert(watchedvar1 != -1 || watchedvar2 == -1);
222  assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
223  assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
224 
225  /* if one watched variable is equal to the old other watched variable, just switch positions */
226  if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
227  {
228  int tmp;
229 
230  tmp = consdata->watchedvar1;
231  consdata->watchedvar1 = consdata->watchedvar2;
232  consdata->watchedvar2 = tmp;
233  tmp = consdata->filterpos1;
234  consdata->filterpos1 = consdata->filterpos2;
235  consdata->filterpos2 = tmp;
236  }
237  assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
238  assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
239 
240  /* drop events on old watched variables */
241  if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
242  {
243  assert(consdata->filterpos1 != -1);
244  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar1], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
245  (SCIP_EVENTDATA*)consdata, consdata->filterpos1) );
246  }
247  if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
248  {
249  assert(consdata->filterpos2 != -1);
250  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar2], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
251  (SCIP_EVENTDATA*)consdata, consdata->filterpos2) );
252  }
253 
254  /* catch events on new watched variables */
255  if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
256  {
257  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[watchedvar1], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
258  (SCIP_EVENTDATA*)consdata, &consdata->filterpos1) );
259  }
260  if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
261  {
262  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[watchedvar2], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
263  (SCIP_EVENTDATA*)consdata, &consdata->filterpos2) );
264  }
265 
266  /* set the new watched variables */
267  consdata->watchedvar1 = watchedvar1;
268  consdata->watchedvar2 = watchedvar2;
269 
270  return SCIP_OKAY;
271 }
272 
273 /** ensures, that the vars array can store at least num entries */
274 static
276  SCIP* scip, /**< SCIP data structure */
277  SCIP_CONSDATA* consdata, /**< linear constraint data */
278  int num /**< minimum number of entries to store */
279  )
280 {
281  assert(consdata != NULL);
282  assert(consdata->nvars <= consdata->varssize);
283 
284  if( num > consdata->varssize )
285  {
286  int newsize;
287 
288  newsize = SCIPcalcMemGrowSize(scip, num);
289  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
290  consdata->varssize = newsize;
291  }
292  assert(num <= consdata->varssize);
293 
294  return SCIP_OKAY;
295 }
296 
297 /** creates constraint data for xor constraint */
298 static
300  SCIP* scip, /**< SCIP data structure */
301  SCIP_CONSDATA** consdata, /**< pointer to store the constraint data */
302  SCIP_Bool rhs, /**< right hand side of the constraint */
303  int nvars, /**< number of variables in the xor operation */
304  SCIP_VAR** vars, /**< variables in xor operation */
305  SCIP_VAR* intvar /**< artificial integer variable for linear relaxation */
306  )
307 {
308  int r;
309 
310  assert(consdata != NULL);
311  assert(nvars == 0 || vars != NULL);
312 
313  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
314  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
315 
316  (*consdata)->rhs = rhs;
317  (*consdata)->intvar = intvar;
318  for( r = 0; r < NROWS; ++r )
319  (*consdata)->rows[r] = NULL;
320  (*consdata)->nvars = nvars;
321  (*consdata)->varssize = nvars;
322  (*consdata)->watchedvar1 = -1;
323  (*consdata)->watchedvar2 = -1;
324  (*consdata)->filterpos1 = -1;
325  (*consdata)->filterpos2 = -1;
326  (*consdata)->deleteintvar = (intvar == NULL);
327  (*consdata)->propagated = FALSE;
328  (*consdata)->sorted = FALSE;
329  (*consdata)->changed = TRUE;
330  (*consdata)->extvars = NULL;
331  (*consdata)->nextvars = 0;
332  (*consdata)->extvarssize = 0;
333 
334  /* get transformed variables, if we are in the transformed problem */
335  if( SCIPisTransformed(scip) )
336  {
337  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
338 
339  if( (*consdata)->intvar != NULL )
340  {
341  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->intvar, &((*consdata)->intvar)) );
342  }
343 
344  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
345  {
346  SCIP_CONSHDLRDATA* conshdlrdata;
347  SCIP_CONSHDLR* conshdlr;
348  int v;
349 
350  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
351  assert(conshdlr != NULL);
352  conshdlrdata = SCIPconshdlrGetData(conshdlr);
353  assert(conshdlrdata != NULL);
354 
355  for( v = (*consdata)->nvars - 1; v >= 0; --v )
356  {
357  SCIP_CALL( SCIPcatchVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
358  (SCIP_EVENTDATA*)(*consdata), NULL) );
359  }
360  }
361  }
362 
363  if( (*consdata)->intvar != NULL )
364  {
365  /* capture artificial variable */
366  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->intvar) );
367  }
368 
369  return SCIP_OKAY;
370 }
371 
372 /** releases LP row of constraint data */
373 static
375  SCIP* scip, /**< SCIP data structure */
376  SCIP_CONSDATA* consdata /**< constraint data */
377  )
378 {
379  int r;
380 
381  assert(consdata != NULL);
382 
383  for( r = 0; r < NROWS; ++r )
384  {
385  if( consdata->rows[r] != NULL )
386  {
387  SCIP_CALL( SCIPreleaseRow(scip, &consdata->rows[r]) );
388  }
389  }
390 
391  return SCIP_OKAY;
392 }
393 
394 /** frees constraint data for xor constraint */
395 static
397  SCIP* scip, /**< SCIP data structure */
398  SCIP_CONSDATA** consdata, /**< pointer to the constraint data */
399  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
400  )
401 {
402  assert(consdata != NULL);
403  assert(*consdata != NULL);
404 
405  if( SCIPisTransformed(scip) )
406  {
407  int j;
408 
409  /* drop events for watched variables */
410  SCIP_CALL( consdataSwitchWatchedvars(scip, *consdata, eventhdlr, -1, -1) );
411 
412  /* release flow variables */
413  if ( (*consdata)->nextvars > 0 )
414  {
415  assert( (*consdata)->extvars != NULL );
416  for (j = 0; j < (*consdata)->extvarssize; ++j)
417  {
418  if ( (*consdata)->extvars[j] != NULL )
419  {
420  SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->extvars[j])) );
421  }
422  }
423 
424  SCIPfreeBlockMemoryArray(scip, &((*consdata)->extvars), (*consdata)->extvarssize);
425  (*consdata)->nextvars = 0;
426  (*consdata)->extvarssize = 0;
427  }
428  }
429  else
430  {
431  assert((*consdata)->watchedvar1 == -1);
432  assert((*consdata)->watchedvar2 == -1);
433  }
434 
435  /* release LP row */
436  SCIP_CALL( consdataFreeRows(scip, *consdata) );
437 
438  /* release internal variable */
439  if( (*consdata)->intvar != NULL )
440  {
441  /* if the constraint is deleted and the integral variable is present, it should be fixed */
442  assert( SCIPisEQ(scip, SCIPvarGetLbGlobal((*consdata)->intvar), SCIPvarGetLbGlobal((*consdata)->intvar)) );
443 
444  /* We do not delete the integral variable, but leave the handling to SCIP, because it might happen that the
445  integral variable is stored in some basis information somewhere. */
446  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->intvar) );
447  }
448 
449  SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->varssize);
450  SCIPfreeBlockMemory(scip, consdata);
451 
452  return SCIP_OKAY;
453 }
454 
455 /** prints xor constraint to file stream */
456 static
458  SCIP* scip, /**< SCIP data structure */
459  SCIP_CONSDATA* consdata, /**< xor constraint data */
460  FILE* file, /**< output file (or NULL for standard output) */
461  SCIP_Bool endline /**< should an endline be set? */
462  )
463 {
464  assert(consdata != NULL);
465 
466  /* start variable list */
467  SCIPinfoMessage(scip, file, "xor(");
468 
469  /* print variable list */
470  SCIP_CALL( SCIPwriteVarsList(scip, file, consdata->vars, consdata->nvars, TRUE, ',') );
471 
472  /* close variable list and write right hand side */
473  SCIPinfoMessage(scip, file, ") = %d", consdata->rhs);
474 
475  /* write integer variable if it exists */
476  if( consdata->intvar != NULL )
477  {
478  SCIPinfoMessage(scip, file, " (intvar = ");
479  SCIP_CALL( SCIPwriteVarName(scip, file, consdata->intvar, TRUE) );
480  SCIPinfoMessage(scip, file, ")");
481  }
482 
483  if( endline )
484  SCIPinfoMessage(scip, file, "\n");
485 
486  return SCIP_OKAY;
487 }
488 
489 /** sets intvar of an xor constraint */
490 static
492  SCIP* scip, /**< SCIP data structure */
493  SCIP_CONS* cons, /**< xor constraint */
494  SCIP_VAR* var /**< variable to add to the constraint */
495  )
496 {
497  SCIP_CONSDATA* consdata;
498  SCIP_Bool transformed;
499 
500  assert(var != NULL);
501 
502  consdata = SCIPconsGetData(cons);
503  assert(consdata != NULL);
504  assert(consdata->rows[0] == NULL);
505 
506  /* are we in the transformed problem? */
507  transformed = SCIPconsIsTransformed(cons);
508 
509  /* always use transformed variables in transformed constraints */
510  if( transformed )
511  {
512  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
513  }
514  assert(var != NULL);
515  assert(transformed == SCIPvarIsTransformed(var));
516 
517  /* remove the rounding locks for the old variable and release it */
518  if( consdata->intvar != NULL )
519  {
520  SCIP_CALL( unlockRounding(scip, cons, consdata->intvar) );
521  SCIP_CALL( SCIPreleaseVar(scip, &(consdata->intvar)) );
522  }
523 
524  consdata->intvar = var;
525  consdata->changed = TRUE;
526 
527  /* install the rounding locks for the new variable and capture it */
528  SCIP_CALL( lockRounding(scip, cons, consdata->intvar) );
529  SCIP_CALL( SCIPcaptureVar(scip, consdata->intvar) );
530 
531  /**@todo update LP rows */
532  if( consdata->rows[0] != NULL )
533  {
534  SCIPerrorMessage("cannot change intvar of xor constraint after LP relaxation was created\n");
535  return SCIP_INVALIDCALL;
536  }
537 
538  return SCIP_OKAY;
539 }
540 
541 /** adds coefficient to xor constraint */
542 static
544  SCIP* scip, /**< SCIP data structure */
545  SCIP_CONS* cons, /**< xor constraint */
546  SCIP_VAR* var /**< variable to add to the constraint */
547  )
548 {
549  SCIP_CONSDATA* consdata;
550  SCIP_Bool transformed;
551 
552  assert(var != NULL);
553 
554  consdata = SCIPconsGetData(cons);
555  assert(consdata != NULL);
556  assert(consdata->rows[0] == NULL);
557 
558  /* are we in the transformed problem? */
559  transformed = SCIPconsIsTransformed(cons);
560 
561  /* always use transformed variables in transformed constraints */
562  if( transformed )
563  {
564  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
565  }
566  assert(var != NULL);
567  assert(transformed == SCIPvarIsTransformed(var));
568 
569  SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
570  consdata->vars[consdata->nvars] = var;
571  consdata->nvars++;
572  consdata->sorted = (consdata->nvars == 1);
573  consdata->changed = TRUE;
574 
575  /* install the rounding locks for the new variable */
576  SCIP_CALL( lockRounding(scip, cons, var) );
577 
578  /* we only catch this event in presolving stages
579  * we need to catch this event also during exiting presolving because we call applyFixings to clean up the constraint
580  * and this can lead to an insertion of a replacement of variables for which we will try to drop the VARFIXED event.
581  */
584  {
585  SCIP_CONSHDLRDATA* conshdlrdata;
586  SCIP_CONSHDLR* conshdlr;
587 
588  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
589  assert(conshdlr != NULL);
590  conshdlrdata = SCIPconshdlrGetData(conshdlr);
591  assert(conshdlrdata != NULL);
592 
593  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
594  (SCIP_EVENTDATA*)consdata, NULL) );
595  }
596 
597  /**@todo update LP rows */
598  if( consdata->rows[0] != NULL )
599  {
600  SCIPerrorMessage("cannot add coefficients to xor constraint after LP relaxation was created\n");
601  return SCIP_INVALIDCALL;
602  }
603 
604  return SCIP_OKAY;
605 }
606 
607 /** deletes coefficient at given position from xor constraint data */
608 static
610  SCIP* scip, /**< SCIP data structure */
611  SCIP_CONS* cons, /**< xor constraint */
612  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
613  int pos /**< position of coefficient to delete */
614  )
615 {
616  SCIP_CONSDATA* consdata;
617 
618  assert(eventhdlr != NULL);
619 
620  consdata = SCIPconsGetData(cons);
621  assert(consdata != NULL);
622  assert(0 <= pos && pos < consdata->nvars);
623  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
624 
625  /* remove the rounding locks of the deleted variable */
626  SCIP_CALL( unlockRounding(scip, cons, consdata->vars[pos]) );
627 
628  /* we only catch this event in presolving stage, so we need to only drop it there */
631  {
632  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_VARFIXED, eventhdlr,
633  (SCIP_EVENTDATA*)consdata, -1) );
634  }
635 
636  if( SCIPconsIsTransformed(cons) )
637  {
638  /* if the position is watched, stop watching the position */
639  if( consdata->watchedvar1 == pos )
640  {
641  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar2, -1) );
642  }
643  if( consdata->watchedvar2 == pos )
644  {
645  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar1, -1) );
646  }
647  }
648  assert(pos != consdata->watchedvar1);
649  assert(pos != consdata->watchedvar2);
650 
651  /* move the last variable to the free slot */
652  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
653  consdata->nvars--;
654 
655  /* if the last variable (that moved) was watched, update the watched position */
656  if( consdata->watchedvar1 == consdata->nvars )
657  consdata->watchedvar1 = pos;
658  if( consdata->watchedvar2 == consdata->nvars )
659  consdata->watchedvar2 = pos;
660 
661  consdata->propagated = FALSE;
662  consdata->sorted = FALSE;
663  consdata->changed = TRUE;
664 
665  return SCIP_OKAY;
666 }
667 
668 /** sorts and constraint's variables by non-decreasing variable index */
669 static
670 void consdataSort(
671  SCIP_CONSDATA* consdata /**< constraint data */
672  )
673 {
674  assert(consdata != NULL);
675 
676  if( !consdata->sorted )
677  {
678  if( consdata->nvars <= 1 )
679  consdata->sorted = TRUE;
680  else
681  {
682  SCIP_VAR* var1 = NULL;
683  SCIP_VAR* var2 = NULL;
684 
685  /* remember watch variables */
686  if( consdata->watchedvar1 != -1 )
687  {
688  var1 = consdata->vars[consdata->watchedvar1];
689  assert(var1 != NULL);
690  consdata->watchedvar1 = -1;
691  if( consdata->watchedvar2 != -1 )
692  {
693  var2 = consdata->vars[consdata->watchedvar2];
694  assert(var2 != NULL);
695  consdata->watchedvar2 = -1;
696  }
697  }
698  assert(consdata->watchedvar1 == -1);
699  assert(consdata->watchedvar2 == -1);
700  assert(var1 != NULL || var2 == NULL);
701 
702  /* sort variables after index */
703  SCIPsortPtr((void**)consdata->vars, SCIPvarCompActiveAndNegated, consdata->nvars);
704  consdata->sorted = TRUE;
705 
706  /* correct watched variables */
707  if( var1 != NULL )
708  {
709  int v;
710 
711  /* since negated variables exist, we need to loop over all variables to find the old variable and cannot use
712  * SCIPsortedvecFindPtr()
713  */
714  for( v = consdata->nvars - 1; v >= 0; --v )
715  {
716  if( consdata->vars[v] == var1 )
717  {
718  consdata->watchedvar1 = v;
719  if( var2 == NULL || consdata->watchedvar2 != -1 )
720  break;
721  }
722  else if( consdata->vars[v] == var2 )
723  {
724  assert(consdata->vars[v] != NULL);
725  consdata->watchedvar2 = v;
726  if( consdata->watchedvar1 != -1 )
727  break;
728  }
729  }
730  assert(consdata->watchedvar1 != -1);
731  assert(consdata->watchedvar2 != -1 || var2 == NULL);
732  assert(consdata->watchedvar1 < consdata->nvars);
733  assert(consdata->watchedvar2 < consdata->nvars);
734  }
735  }
736  }
737 
738 #ifdef SCIP_DEBUG
739  /* check sorting */
740  {
741  int v;
742 
743  for( v = 0; v < consdata->nvars; ++v )
744  {
745  assert(v == consdata->nvars-1 || SCIPvarCompareActiveAndNegated(consdata->vars[v], consdata->vars[v+1]) <= 0);
746  }
747  }
748 #endif
749 }
750 
751 
752 /** gets the key of the given element */
753 static
754 SCIP_DECL_HASHGETKEY(hashGetKeyXorcons)
755 { /*lint --e{715}*/
756  /* the key is the element itself */
757  return elem;
758 }
759 
760 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
761 static
762 SCIP_DECL_HASHKEYEQ(hashKeyEqXorcons)
763 {
764  SCIP_CONSDATA* consdata1;
765  SCIP_CONSDATA* consdata2;
766  int i;
767 #ifndef NDEBUG
768  SCIP* scip;
769 
770  scip = (SCIP*)userptr;
771  assert(scip != NULL);
772 #endif
773 
774  consdata1 = SCIPconsGetData((SCIP_CONS*)key1);
775  consdata2 = SCIPconsGetData((SCIP_CONS*)key2);
776 
777  /* checks trivial case */
778  if( consdata1->nvars != consdata2->nvars )
779  return FALSE;
780 
781  /* sorts the constraints */
782  consdataSort(consdata1);
783  consdataSort(consdata2);
784  assert(consdata1->sorted);
785  assert(consdata2->sorted);
786 
787  for( i = 0; i < consdata1->nvars ; ++i )
788  {
789  /* tests if variables are equal */
790  if( consdata1->vars[i] != consdata2->vars[i] )
791  {
792  assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
793  SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
794  return FALSE;
795  }
796  assert(SCIPvarCompareActiveAndNegated(consdata1->vars[i], consdata2->vars[i]) == 0);
797  }
798 
799  return TRUE;
800 }
801 
802 /** returns the hash value of the key */
803 static
804 SCIP_DECL_HASHKEYVAL(hashKeyValXorcons)
805 { /*lint --e{715}*/
806  SCIP_CONSDATA* consdata;
807  int minidx;
808  int mididx;
809  int maxidx;
810 
811  consdata = SCIPconsGetData((SCIP_CONS*)key);
812  assert(consdata != NULL);
813  assert(consdata->sorted);
814  assert(consdata->nvars > 0);
815 
816  /* only active, fixed or negated variables are allowed */
817  assert(consdata->vars[0] != NULL);
818  assert(consdata->vars[consdata->nvars / 2] != NULL);
819  assert(consdata->vars[consdata->nvars - 1] != NULL);
820  assert(SCIPvarIsActive(consdata->vars[0]) || SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_FIXED);
821  assert(SCIPvarIsActive(consdata->vars[consdata->nvars / 2]) || SCIPvarGetStatus(consdata->vars[consdata->nvars / 2]) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(consdata->vars[consdata->nvars / 2]) == SCIP_VARSTATUS_FIXED);
822  assert(SCIPvarIsActive(consdata->vars[consdata->nvars - 1]) || SCIPvarGetStatus(consdata->vars[consdata->nvars - 1]) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(consdata->vars[consdata->nvars - 1]) == SCIP_VARSTATUS_FIXED);
823 
824  minidx = SCIPvarGetIndex(consdata->vars[0]);
825  mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
826  maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
827  /* note that for all indices it does not hold that they are sorted, because variables are sorted with
828  * SCIPvarCompareActiveAndNegated (see var.c)
829  */
830 
831  return SCIPhashTwo(SCIPcombineTwoInt(consdata->nvars, minidx),
832  SCIPcombineTwoInt(mididx, maxidx));
833 }
834 
835 /** deletes all fixed variables and all pairs of equal variables */
836 static
838  SCIP* scip, /**< SCIP data structure */
839  SCIP_CONS* cons, /**< xor constraint */
840  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
841  int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
842  int* naggrvars, /**< pointer to add up the number of aggregated variables */
843  int* naddconss, /**< pointer to add up the number of added constraints */
844  SCIP_Bool* cutoff /**< whether a cutoff has been detected */
845  )
846 {
847  SCIP_CONSDATA* consdata;
848  int v;
849 
850  consdata = SCIPconsGetData(cons);
851  assert(consdata != NULL);
852  assert(consdata->nvars == 0 || consdata->vars != NULL);
853  assert(nchgcoefs != NULL);
854 
855  SCIPdebugMsg(scip, "before fixings: ");
856  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
857 
858  v = 0;
859  while( v < consdata->nvars )
860  {
861  SCIP_VAR* var;
862 
863  var = consdata->vars[v];
864  assert(SCIPvarIsBinary(var));
865 
866  if( SCIPvarGetUbGlobal(var) < 0.5 )
867  {
868  assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(var), 0.0));
869  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
870  (*nchgcoefs)++;
871  }
872  else if( SCIPvarGetLbGlobal(var) > 0.5 && consdata->deleteintvar )
873  {
874  assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(var), 1.0));
875  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
876  consdata->rhs = !consdata->rhs;
877  (*nchgcoefs)++;
878  }
879  else
880  {
881  SCIP_VAR* repvar;
882  SCIP_Bool negated;
883 
884  /* get binary representative of variable */
885  SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
886 
887  /* remove all negations by replacing them with the active variable
888  * it holds that xor(x1, ~x2) = 0 <=> xor(x1, x2) = 1
889  * @note this can only be done if the integer variable does not exist
890  */
891  if( negated && consdata->intvar == NULL )
892  {
893  assert(SCIPvarIsNegated(repvar));
894 
895  repvar = SCIPvarGetNegationVar(repvar);
896  consdata->rhs = !consdata->rhs;
897  }
898 
899  /* check, if the variable should be replaced with the representative */
900  if( repvar != var )
901  {
902  /* delete old (aggregated) variable */
903  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
904 
905  /* add representative instead */
906  SCIP_CALL( addCoef(scip, cons, repvar) );
907  }
908  else
909  ++v;
910  }
911  }
912 
913  /* sort the variables in the constraint */
914  consdataSort(consdata);
915  assert(consdata->sorted);
916 
917  SCIPdebugMsg(scip, "after sort : ");
918  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
919 
920  /* delete pairs of equal or negated variables; scan from back to front because deletion doesn't affect the
921  * order of the front variables
922  */
923  v = consdata->nvars-2;
924  while ( v >= 0 )
925  {
926  if( consdata->vars[v] == consdata->vars[v+1] ) /*lint !e679*/
927  {
928  SCIP_VAR* newvars[3];
929  SCIP_Real vals[3];
930 
931  newvars[2] = consdata->vars[v];
932  vals[2] = 1.0;
933 
934  /* delete both variables */
935  SCIPdebugMsg(scip, "xor constraint <%s>: deleting pair of equal variables <%s>\n",
936  SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v]));
937  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v+1) );
938  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
939  (*nchgcoefs) += 2;
940  v = MIN(v, consdata->nvars-1);
941 
942  /* need to update integer variable, consider the following case:
943  * xor(x1, x2, x3, x4, x5) = 0 (and x1 == x2) was change above to
944  * xor( x3, x4, x5) = 0
945  * assuming we have an integer variable y it needs to be replaced by z with y = x1 + z and z in [lb_y, ub_y]
946  */
947  if( consdata->intvar != NULL )
948  {
949  SCIP_CONS* newcons;
950  SCIP_Real lb;
951  SCIP_Real ub;
952  SCIP_VARTYPE vartype;
953  char varname[SCIP_MAXSTRLEN];
954  char consname[SCIP_MAXSTRLEN];
955 
956  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "agg_%s", SCIPvarGetName(consdata->intvar));
957  lb = SCIPvarGetLbGlobal(consdata->intvar);
958  ub = SCIPvarGetUbGlobal(consdata->intvar);
959  vartype = SCIPvarGetType(consdata->intvar);
960 
961  SCIP_CALL( SCIPcreateVar(scip, &newvars[0], varname, lb, ub, 0.0, vartype,
962  SCIPvarIsInitial(consdata->intvar), SCIPvarIsRemovable(consdata->intvar),
963  NULL, NULL, NULL, NULL, NULL) );
964  SCIP_CALL( SCIPaddVar(scip, newvars[0]) );
965  vals[0] = 1.0;
966 
967  newvars[1] = consdata->intvar;
968  vals[1] = -1.0;
969 
970  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons));
971 
972  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 3, newvars, vals, 0.0, 0.0,
973  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), TRUE, /*SCIPconsIsEnforced(cons),*/
974  TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
977 
978  SCIP_CALL( SCIPaddCons(scip, newcons) );
979  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
980  ++(*naddconss);
981 
982  SCIP_CALL( setIntvar(scip, cons, newvars[0]) );
983  SCIP_CALL( SCIPreleaseVar(scip, &newvars[0]) );
984  }
985  }
986  else if( consdata->vars[v] == SCIPvarGetNegatedVar(consdata->vars[v+1]) ) /*lint !e679*/
987  {
988  /* delete both variables and negate the rhs */
989  SCIPdebugMsg(scip, "xor constraint <%s>: deleting pair of negated variables <%s> and <%s>\n",
990  SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(consdata->vars[v+1])); /*lint !e679*/
991  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v+1) );
992  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
993  (*nchgcoefs) += 2;
994  consdata->rhs = !consdata->rhs;
995  v = MIN(v, consdata->nvars-1);
996 
997  /* need to update integer variable, consider the following case:
998  * xor(x1, x2, x3, x4, x5) = 0 (and x1 = ~x2) was change above to
999  * xor( x3, x4, x5) = 1
1000  * assuming we have an integer variable y it needs to be replaced by z with y = 1 + z and z in [lb_y, ub_y - 1]
1001  */
1002  if( consdata->rhs && consdata->intvar != NULL )
1003  {
1004  SCIP_VAR* newvar;
1005  SCIP_Real lb;
1006  SCIP_Real ub;
1007  SCIP_VARTYPE vartype;
1008  char varname[SCIP_MAXSTRLEN];
1009  SCIP_Bool aggregated;
1010  SCIP_Bool infeasible;
1011  SCIP_Bool redundant;
1012 
1013  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "agg_%s", SCIPvarGetName(consdata->intvar));
1014  ub = SCIPvarGetUbGlobal(consdata->intvar) - 1;
1015  lb = MIN(ub, SCIPvarGetLbGlobal(consdata->intvar)); /*lint !e666*/
1016  vartype = (lb == 0 && ub == 1) ? SCIP_VARTYPE_BINARY : SCIPvarGetType(consdata->intvar);
1017 
1018  SCIP_CALL( SCIPcreateVar(scip, &newvar, varname, lb, ub, 0.0, vartype,
1019  SCIPvarIsInitial(consdata->intvar), SCIPvarIsRemovable(consdata->intvar),
1020  NULL, NULL, NULL, NULL, NULL) );
1021  SCIP_CALL( SCIPaddVar(scip, newvar) );
1022 
1023  SCIP_CALL( SCIPaggregateVars(scip, consdata->intvar, newvar, 1.0, -1.0, 1.0, &infeasible, &redundant, &aggregated) );
1024  assert(infeasible || redundant || SCIPdoNotAggr(scip));
1025 
1026  if( infeasible )
1027  {
1028  *cutoff = TRUE;
1029  break;
1030  }
1031 
1032  if( aggregated )
1033  {
1034  (*naggrvars)++;
1035 
1036  if( SCIPvarIsActive(newvar) )
1037  {
1038  SCIP_CALL( setIntvar(scip, cons, newvar) );
1039  SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
1040  }
1041  /* the new variable should only by inactive if it was fixed due to the aggregation, so also the old variable
1042  * should be fixed now.
1043  *
1044  * @todo if newvar is not active we may want to transform the xor into a linear constraint
1045  */
1046  else
1047  {
1048  assert(SCIPvarGetStatus(newvar) == SCIP_VARSTATUS_FIXED);
1049  assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->intvar), SCIPvarGetUbGlobal(consdata->intvar)));
1050 
1051  SCIP_CALL( setIntvar(scip, cons, newvar) );
1052  SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
1053  }
1054  }
1055  else
1056  {
1057  SCIP_CONS* newcons;
1058  char consname[SCIP_MAXSTRLEN];
1059  SCIP_VAR* newvars[2];
1060  SCIP_Real vals[2];
1061 
1062  newvars[0] = consdata->intvar;
1063  vals[0] = 1.0;
1064  newvars[1] = newvar;
1065  vals[1] = -1.0;
1066 
1067  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons));
1068 
1069  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, newvars, vals, 1.0, 1.0,
1070  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), TRUE, /*SCIPconsIsEnforced(cons),*/
1071  TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
1074 
1075  SCIP_CALL( SCIPaddCons(scip, newcons) );
1076  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1077  ++(*naddconss);
1078 
1079  SCIP_CALL( setIntvar(scip, cons, newvar) );
1080  SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
1081  }
1082  }
1083  }
1084  else
1085  assert(SCIPvarGetProbvar(consdata->vars[v]) != SCIPvarGetProbvar(consdata->vars[v+1])); /*lint !e679*/
1086  --v;
1087  }
1088 
1089  SCIPdebugMsg(scip, "after fixings : ");
1090  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
1091 
1092  return SCIP_OKAY;
1093 }
1094 
1095 /** adds extended flow formulation
1096  *
1097  * The extended flow formulation is built as follows: Let \f$x_1, \dots, x_k\f$ be the variables contained in the given
1098  * XOR constraint. We construct a two layered flow network. The upper layer is called the north layer and the lower is
1099  * called the south layer. For each \f$x_i,\; i = 2, \ldots, k-1\f$, we add arcs that stay in the north and south layer
1100  * (denoted by 'nn' and 'ss', respectively), as well as arcs that change the layers (denoted by 'ns' and 'sn'). For
1101  * \f$x_1\f$, we only add two arcs from the source to the two layers. The source is located on the north layer. For
1102  * \f$x_k\f$, we add two arcs connecting the two layers to the sink. Depending on the rhs of the constraint the sink is
1103  * located on the north or south layer. A change in the layers corresponds to a parity change, i.e., the corresponding
1104  * variable \f$x_i\f$ is 1 (and 0 otherwise).
1105  */
1106 static
1108  SCIP* scip, /**< SCIP data structure */
1109  SCIP_CONS* cons, /**< constraint to check */
1110  int* naddedconss /**< number of added constraints */
1111  )
1112 {
1113  char name[SCIP_MAXSTRLEN];
1114  SCIP_CONSDATA* consdata;
1115  SCIP_VAR* varprevnn = NULL;
1116  SCIP_VAR* varprevns = NULL;
1117  SCIP_VAR* varprevsn = NULL;
1118  SCIP_VAR* varprevss = NULL;
1119  SCIP_VAR* vars[4];
1120  SCIP_Real vals[4];
1121  int i;
1122 
1123  assert( scip != NULL );
1124  assert( cons != NULL );
1125  assert( naddedconss != NULL );
1126  *naddedconss = 0;
1127 
1128  /* exit if contraints is modifiable */
1129  if ( SCIPconsIsModifiable(cons) )
1130  return SCIP_OKAY;
1131 
1132  consdata = SCIPconsGetData(cons);
1133  assert( consdata != NULL );
1134 
1135  /* exit if extended formulation has been added already */
1136  if ( consdata->extvars != NULL )
1137  return SCIP_OKAY;
1138 
1139  /* xor constraints with at most 3 variables are handled directly through rows for the convex hull */
1140  if ( consdata->nvars <= 3 )
1141  return SCIP_OKAY;
1142 
1143  SCIPdebugMsg(scip, "Add extended formulation for xor constraint <%s> ...\n", SCIPconsGetName(cons));
1144  assert( consdata->extvars == NULL );
1145  assert( consdata->nextvars == 0 );
1146  assert( consdata->extvarssize == 0 );
1147 
1148  /* get storage for auxiliary variables */
1149  consdata->extvarssize = 4 * (consdata->nvars);
1150  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->extvars), consdata->extvarssize) );
1151 
1152  /* pass through components */
1153  for (i = 0; i < consdata->nvars; ++i)
1154  {
1155  /* variables: n - north, s - south */
1156  SCIP_VAR* varnn = NULL;
1157  SCIP_VAR* varns = NULL;
1158  SCIP_VAR* varsn = NULL;
1159  SCIP_VAR* varss = NULL;
1160  SCIP_CONS* newcons;
1161  SCIP_Real rhs = 0.0;
1162  SCIP_Bool infeasible = FALSE;
1163  SCIP_Bool redundant = FALSE;
1164  SCIP_Bool aggregated = FALSE;
1165  int cnt = 0;
1166 
1167  /* create variables */
1168  if ( i == 0 )
1169  {
1170  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_nn", SCIPconsGetName(cons), i);
1171  SCIP_CALL( SCIPcreateVar(scip, &varnn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1172  SCIP_CALL( SCIPaddVar(scip, varnn) );
1173 
1174  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ns", SCIPconsGetName(cons), i);
1175  SCIP_CALL( SCIPcreateVar(scip, &varns, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1176  SCIP_CALL( SCIPaddVar(scip, varns) );
1177 
1178  /* need to lock variables, because we aggregate them */
1179  SCIP_CALL( SCIPlockVarCons(scip, varnn, cons, TRUE, TRUE) );
1180  SCIP_CALL( SCIPlockVarCons(scip, varns, cons, TRUE, TRUE) );
1181 
1182  /* aggregate ns variable with original variable */
1183  SCIP_CALL( SCIPaggregateVars(scip, varns, consdata->vars[0], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1184  assert( ! infeasible );
1185  assert( redundant );
1186  assert( aggregated );
1187  }
1188  else
1189  {
1190  if ( i == consdata->nvars-1 )
1191  {
1192  if ( consdata->rhs )
1193  {
1194  /* if the rhs is 1 (true) the flow goes to the bottom level */
1195  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ns", SCIPconsGetName(cons), i);
1196  SCIP_CALL( SCIPcreateVar(scip, &varns, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1197  SCIP_CALL( SCIPaddVar(scip, varns) );
1198 
1199  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ss", SCIPconsGetName(cons), i);
1200  SCIP_CALL( SCIPcreateVar(scip, &varss, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1201  SCIP_CALL( SCIPaddVar(scip, varss) );
1202 
1203  /* need to lock variables, because we aggregate them */
1204  SCIP_CALL( SCIPlockVarCons(scip, varns, cons, TRUE, TRUE) );
1205  SCIP_CALL( SCIPlockVarCons(scip, varss, cons, TRUE, TRUE) );
1206 
1207  /* aggregate ns variable with original variable */
1208  SCIP_CALL( SCIPaggregateVars(scip, varns, consdata->vars[i], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1209  assert( ! infeasible );
1210  assert( redundant );
1211  assert( aggregated );
1212  }
1213  else
1214  {
1215  /* if the rhs is 0 (false) the flow stays on the top level */
1216  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_nn", SCIPconsGetName(cons), i);
1217  SCIP_CALL( SCIPcreateVar(scip, &varnn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1218  SCIP_CALL( SCIPaddVar(scip, varnn) );
1219 
1220  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_sn", SCIPconsGetName(cons), i);
1221  SCIP_CALL( SCIPcreateVar(scip, &varsn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1222  SCIP_CALL( SCIPaddVar(scip, varsn) );
1223 
1224  /* need to lock variables, because we aggregate them */
1225  SCIP_CALL( SCIPlockVarCons(scip, varnn, cons, TRUE, TRUE) );
1226  SCIP_CALL( SCIPlockVarCons(scip, varsn, cons, TRUE, TRUE) );
1227 
1228  /* aggregate sn variable with original variable */
1229  SCIP_CALL( SCIPaggregateVars(scip, varsn, consdata->vars[i], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1230  assert( ! infeasible );
1231  assert( redundant );
1232  assert( aggregated );
1233  }
1234  }
1235  else
1236  {
1237  /* add the four flow variables */
1238  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_nn", SCIPconsGetName(cons), i);
1239  SCIP_CALL( SCIPcreateVar(scip, &varnn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1240  SCIP_CALL( SCIPaddVar(scip, varnn) );
1241 
1242  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ns", SCIPconsGetName(cons), i);
1243  SCIP_CALL( SCIPcreateVar(scip, &varns, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1244  SCIP_CALL( SCIPaddVar(scip, varns) );
1245 
1246  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_sn", SCIPconsGetName(cons), i);
1247  SCIP_CALL( SCIPcreateVar(scip, &varsn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1248  SCIP_CALL( SCIPaddVar(scip, varsn) );
1249 
1250  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ss", SCIPconsGetName(cons), i);
1251  SCIP_CALL( SCIPcreateVar(scip, &varss, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1252  SCIP_CALL( SCIPaddVar(scip, varss) );
1253 
1254  SCIP_CALL( SCIPlockVarCons(scip, varnn, cons, TRUE, TRUE) );
1255  SCIP_CALL( SCIPlockVarCons(scip, varns, cons, TRUE, TRUE) );
1256  SCIP_CALL( SCIPlockVarCons(scip, varsn, cons, TRUE, TRUE) );
1257  SCIP_CALL( SCIPlockVarCons(scip, varss, cons, TRUE, TRUE) );
1258 
1259  /* add coupling constraint */
1260  cnt = 0;
1261  if ( varns != NULL )
1262  {
1263  vars[cnt] = varns;
1264  vals[cnt++] = 1.0;
1265  }
1266  if ( varsn != NULL )
1267  {
1268  vars[cnt] = varsn;
1269  vals[cnt++] = 1.0;
1270  }
1271  assert( SCIPvarIsTransformed(consdata->vars[i]) );
1272  vars[cnt] = consdata->vars[i];
1273  vals[cnt++] = -1.0;
1274 
1275  assert( cnt >= 2 );
1276  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_couple", SCIPconsGetName(cons));
1277  /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1278  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, cnt, vars, vals, 0.0, 0.0,
1280  SCIP_CALL( SCIPaddCons(scip, newcons) );
1281  SCIPdebugPrintCons(scip, newcons, NULL);
1282  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1283  ++(*naddedconss);
1284  }
1285 
1286  /* add south flow conservation constraint */
1287 
1288  /* incoming variables */
1289  cnt = 0;
1290  if ( varprevss != NULL )
1291  {
1292  vars[cnt] = varprevss;
1293  vals[cnt++] = 1.0;
1294  }
1295  if ( varprevns != NULL )
1296  {
1297  vars[cnt] = varprevns;
1298  vals[cnt++] = 1.0;
1299  }
1300 
1301  /* outgoing variables */
1302  if ( varss != NULL )
1303  {
1304  vars[cnt] = varss;
1305  vals[cnt++] = -1.0;
1306  }
1307  if ( varsn != NULL )
1308  {
1309  vars[cnt] = varsn;
1310  vals[cnt++] = -1.0;
1311  }
1312 
1313  assert( cnt >= 2 );
1314  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_south", SCIPconsGetName(cons));
1315  /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1316  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, cnt, vars, vals, 0.0, 0.0,
1318  SCIP_CALL( SCIPaddCons(scip, newcons) );
1319  SCIPdebugPrintCons(scip, newcons, NULL);
1320  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1321  ++(*naddedconss);
1322  }
1323 
1324  /* add north flow conservation constraint */
1325 
1326  /* incoming variables */
1327  cnt = 0;
1328  if ( varprevnn != NULL )
1329  {
1330  vars[cnt] = varprevnn;
1331  vals[cnt++] = 1.0;
1332  }
1333  if ( varprevsn != NULL )
1334  {
1335  vars[cnt] = varprevsn;
1336  vals[cnt++] = 1.0;
1337  }
1338 
1339  /* outgoing variables */
1340  if ( varnn != NULL )
1341  {
1342  vars[cnt] = varnn;
1343  vals[cnt++] = -1.0;
1344  }
1345  if ( varns != NULL )
1346  {
1347  vars[cnt] = varns;
1348  vals[cnt++] = -1.0;
1349  }
1350 
1351  assert( cnt >= 2 );
1352  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_north", SCIPconsGetName(cons));
1353  if ( i == 0 )
1354  rhs = -1.0;
1355  else
1356  rhs = 0.0;
1357 
1358  /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1359  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, cnt, vars, vals, rhs, rhs,
1361  SCIP_CALL( SCIPaddCons(scip, newcons) );
1362  SCIPdebugPrintCons(scip, newcons, NULL);
1363  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1364  ++(*naddedconss);
1365 
1366  /* store variables */
1367  consdata->extvars[4*i] = varnn; /*lint !e679*/
1368  consdata->extvars[4*i + 1] = varns; /*lint !e679*/
1369  consdata->extvars[4*i + 2] = varsn; /*lint !e679*/
1370  consdata->extvars[4*i + 3] = varss; /*lint !e679*/
1371 
1372  if ( varnn != NULL )
1373  ++(consdata->nextvars);
1374  if ( varns != NULL )
1375  ++(consdata->nextvars);
1376  if ( varsn != NULL )
1377  ++(consdata->nextvars);
1378  if ( varss != NULL )
1379  ++(consdata->nextvars);
1380 
1381  /* store previous variables */
1382  varprevnn = varnn;
1383  varprevns = varns;
1384  varprevsn = varsn;
1385  varprevss = varss;
1386  }
1387 
1388  return SCIP_OKAY;
1389 }
1390 
1391 /** adds extended asymmetric formulation
1392  *
1393  * The extended asymmetric formulation is constructed as follows: Let \f$x_1, \dots, x_k\f$ be the variables contained
1394  * in the given XOR constraint. We introduce variables \f$p_1, \ldots, p_k\f$ with the following constraints: \f$p_1 =
1395  * x_1\f$, \f$p_k = 1\f$, and for \f$i = 2, \ldots, k-1\f$:
1396  * \f[
1397  * \begin{array}{ll}
1398  * p_i & \leq p_{i-1} + x_i\\
1399  * p_i & \leq 2 - (p_{i-1} + x_i)\\
1400  * p_i & \geq p_{i-1} - x_i\\
1401  * p_i & \geq x_i - p_{i-1}.
1402  * \end{array}
1403  * \f]
1404  * This formulation is described in
1405  *
1406  * Robert D. Carr and Goran Konjevod@n
1407  * Polyhedral combinatorics@n
1408  * In Harvey Greenberg, editor, Tutorials on emerging methodologies and applications in Operations Research,@n
1409  * Chapter 2, pages (2-1)-(2-48). Springer, 2004.
1410  */
1411 static
1413  SCIP* scip, /**< SCIP data structure */
1414  SCIP_CONS* cons, /**< constraint to check */
1415  int* naddedconss /**< number of added constraints */
1416  )
1417 {
1418  char name[SCIP_MAXSTRLEN];
1419  SCIP_CONSDATA* consdata;
1420  SCIP_VAR* vars[3];
1421  SCIP_Real vals[3];
1422  SCIP_VAR* prevvar = NULL;
1423  int i;
1424 
1425  assert( scip != NULL );
1426  assert( cons != NULL );
1427  assert( naddedconss != NULL );
1428  *naddedconss = 0;
1429 
1430  /* exit if contraints is modifiable */
1431  if ( SCIPconsIsModifiable(cons) )
1432  return SCIP_OKAY;
1433 
1434  consdata = SCIPconsGetData(cons);
1435  assert( consdata != NULL );
1436 
1437  /* exit if extended formulation has been added already */
1438  if ( consdata->extvars != NULL )
1439  return SCIP_OKAY;
1440 
1441  /* xor constraints with at most 3 variables are handled directly through rows for the convex hull */
1442  if ( consdata->nvars <= 3 )
1443  return SCIP_OKAY;
1444 
1445  SCIPdebugMsg(scip, "Add extended formulation for xor constraint <%s> ...\n", SCIPconsGetName(cons));
1446  assert( consdata->extvars == NULL );
1447  assert( consdata->nextvars == 0 );
1448 
1449  /* get storage for auxiliary variables */
1450  consdata->extvarssize = consdata->nvars;
1451  consdata->nextvars = consdata->nvars;
1452  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->extvars), consdata->extvarssize ) );
1453 
1454  /* pass through components */
1455  for (i = 0; i < consdata->nvars; ++i)
1456  {
1457  SCIP_Bool infeasible = FALSE;
1458  SCIP_Bool redundant = FALSE;
1459  SCIP_Bool aggregated = FALSE;
1460  SCIP_CONS* newcons;
1461  SCIP_VAR* artvar = NULL;
1462  SCIP_Real lb = 0.0;
1463  SCIP_Real ub = 1.0;
1464 
1465  /* determine fixing for last variables */
1466  if ( i == consdata->nvars-1 )
1467  {
1468  if ( consdata->rhs )
1469  {
1470  lb = 1.0;
1471  ub = 1.0;
1472  }
1473  else
1474  {
1475  lb = 0.0;
1476  ub = 0.0;
1477  }
1478  }
1479 
1480  /* create variable */
1481  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "p_%s_%d", SCIPconsGetName(cons), i);
1482  SCIP_CALL( SCIPcreateVar(scip, &artvar, name, lb, ub, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1483  SCIP_CALL( SCIPaddVar(scip, artvar) );
1484  SCIP_CALL( SCIPlockVarCons(scip, artvar, cons, TRUE, TRUE) );
1485 
1486  /* create constraints */
1487  if ( i == 0 )
1488  {
1489  /* aggregate artificial variable with original variable */
1490  SCIP_CALL( SCIPaggregateVars(scip, artvar, consdata->vars[0], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1491  assert( ! infeasible );
1492  assert( redundant );
1493  assert( aggregated );
1494  }
1495  else
1496  {
1497  assert( SCIPvarIsTransformed(consdata->vars[i]) );
1498 
1499  /* add first constraint */
1500  vars[0] = artvar;
1501  vals[0] = 1.0;
1502  vars[1] = prevvar;
1503  vals[1] = -1.0;
1504  vars[2] = consdata->vars[i];
1505  vals[2] = -1.0;
1506 
1507  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_1", SCIPconsGetName(cons), i);
1508  /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1509  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 0.0,
1511  SCIP_CALL( SCIPaddCons(scip, newcons) );
1512  SCIPdebugPrintCons(scip, newcons, NULL);
1513  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1514  ++(*naddedconss);
1515 
1516  /* add second constraint */
1517  vars[0] = artvar;
1518  vals[0] = 1.0;
1519  vars[1] = prevvar;
1520  vals[1] = 1.0;
1521  vars[2] = consdata->vars[i];
1522  vals[2] = 1.0;
1523 
1524  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_2", SCIPconsGetName(cons), i);
1525  /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1526  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 2.0,
1528  SCIP_CALL( SCIPaddCons(scip, newcons) );
1529  SCIPdebugPrintCons(scip, newcons, NULL);
1530  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1531  ++(*naddedconss);
1532 
1533  /* add third constraint */
1534  vars[0] = artvar;
1535  vals[0] = -1.0;
1536  vars[1] = prevvar;
1537  vals[1] = 1.0;
1538  vars[2] = consdata->vars[i];
1539  vals[2] = -1.0;
1540 
1541  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_3", SCIPconsGetName(cons), i);
1542  /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1543  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 0.0,
1545  SCIP_CALL( SCIPaddCons(scip, newcons) );
1546  SCIPdebugPrintCons(scip, newcons, NULL);
1547  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1548  ++(*naddedconss);
1549 
1550  /* add fourth constraint */
1551  vars[0] = artvar;
1552  vals[0] = -1.0;
1553  vars[1] = prevvar;
1554  vals[1] = -1.0;
1555  vars[2] = consdata->vars[i];
1556  vals[2] = 1.0;
1557 
1558  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_4", SCIPconsGetName(cons), i);
1559  /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1560  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 0.0,
1562  SCIP_CALL( SCIPaddCons(scip, newcons) );
1563  SCIPdebugPrintCons(scip, newcons, NULL);
1564  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1565  ++(*naddedconss);
1566  }
1567 
1568  /* store variable */
1569  consdata->extvars[i] = artvar;
1570  prevvar = artvar;
1571  }
1572 
1573  return SCIP_OKAY;
1574 }
1575 
1576 /** creates LP row corresponding to xor constraint:
1577  * x1 + ... + xn - 2q == rhs
1578  * with internal integer variable q;
1579  * in the special case of 3 variables and c = 0, the following linear system is created:
1580  * + x - y - z <= 0
1581  * - x + y - z <= 0
1582  * - x - y + z <= 0
1583  * + x + y + z <= 2
1584  * in the special case of 3 variables and c = 1, the following linear system is created:
1585  * - x + y + z <= 1
1586  * + x - y + z <= 1
1587  * + x + y - z <= 1
1588  * - x - y - z <= -1
1589  */
1590 static
1592  SCIP* scip, /**< SCIP data structure */
1593  SCIP_CONS* cons /**< constraint to check */
1594  )
1595 {
1596  SCIP_CONSDATA* consdata;
1597  char varname[SCIP_MAXSTRLEN];
1598 
1599  consdata = SCIPconsGetData(cons);
1600  assert(consdata != NULL);
1601  assert(consdata->rows[0] == NULL);
1602 
1603  if( SCIPconsIsModifiable(cons) || consdata->nvars != 3 )
1604  {
1605  SCIP_Real rhsval;
1606 
1607  /* create internal variable, if not yet existing */
1608  if( consdata->intvar == NULL )
1609  {
1610  int ub;
1611 
1612  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "XOR_artificial_%s_int", SCIPconsGetName(cons));
1613  ub = consdata->nvars/2;
1614  SCIP_CALL( SCIPcreateVar(scip, &consdata->intvar, varname, 0.0, (SCIP_Real)ub, 0.0,
1615  consdata->nvars >= 4 ? SCIP_VARTYPE_INTEGER : SCIP_VARTYPE_BINARY,
1617  SCIP_CALL( SCIPaddVar(scip, consdata->intvar) );
1618 
1619 #ifdef SCIP_DEBUG_SOLUTION
1620  if( SCIPdebugIsMainscip(scip) )
1621  {
1622  SCIP_Real solval;
1623  int count = 0;
1624  int v;
1625 
1626  for( v = consdata->nvars - 1; v >= 0; --v )
1627  {
1628  SCIP_CALL( SCIPdebugGetSolVal(scip, consdata->vars[v], &solval) );
1629  count += (solval > 0.5 ? 1 : 0);
1630  }
1631  assert((count - consdata->rhs) % 2 == 0);
1632  solval = (SCIP_Real) ((count - consdata->rhs) / 2);
1633 
1634  /* store debug sol value of artificial integer variable */
1635  SCIP_CALL( SCIPdebugAddSolVal(scip, consdata->intvar, solval) );
1636  }
1637 #endif
1638 
1639  /* install the rounding locks for the internal variable */
1640  SCIP_CALL( lockRounding(scip, cons, consdata->intvar) );
1641  }
1642 
1643  /* create LP row */
1644  rhsval = (consdata->rhs ? 1.0 : 0.0);
1645  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[0], SCIPconsGetHdlr(cons), SCIPconsGetName(cons), rhsval, rhsval,
1647  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[0], consdata->intvar, -2.0) );
1648  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[0], consdata->nvars, consdata->vars, 1.0) );
1649  }
1650  else if( !consdata->rhs )
1651  {
1652  char rowname[SCIP_MAXSTRLEN];
1653  int r;
1654 
1655  /* create the <= 0 rows with one positive sign */
1656  for( r = 0; r < 3; ++r )
1657  {
1658  int v;
1659 
1660  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), r);
1661  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[r], SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), 0.0,
1663  for( v = 0; v < 3; ++v )
1664  {
1665  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[r], consdata->vars[v], v == r ? +1.0 : -1.0) );
1666  }
1667  }
1668 
1669  /* create the <= 2 row with all positive signs */
1670  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_3", SCIPconsGetName(cons));
1671  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[3], SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), 2.0,
1673  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[3], consdata->nvars, consdata->vars, 1.0) );
1674 
1675  /* create extra LP row if integer variable exists */
1676  if( consdata->intvar != NULL )
1677  {
1678  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[4], SCIPconsGetHdlr(cons), SCIPconsGetName(cons), 0.0, 0.0,
1680  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[4], consdata->intvar, -2.0) );
1681  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[4], consdata->nvars, consdata->vars, 1.0) );
1682  }
1683  }
1684  else
1685  {
1686  char rowname[SCIP_MAXSTRLEN];
1687  int r;
1688 
1689  /* create the <= 1 rows with one negative sign */
1690  for( r = 0; r < 3; ++r )
1691  {
1692  int v;
1693 
1694  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), r);
1695  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[r], SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), 1.0,
1697  for( v = 0; v < 3; ++v )
1698  {
1699  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[r], consdata->vars[v], v == r ? -1.0 : +1.0) );
1700  }
1701  }
1702 
1703  /* create the <= -1 row with all negative signs */
1704  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_3", SCIPconsGetName(cons));
1705  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[3], SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), -1.0,
1707  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[3], consdata->nvars, consdata->vars, -1.0) );
1708 
1709  /* create extra LP row if integer variable exists */
1710  if( consdata->intvar != NULL )
1711  {
1712  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[4], SCIPconsGetHdlr(cons), SCIPconsGetName(cons), 1.0, 1.0,
1714  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[4], consdata->intvar, -2.0) );
1715  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[4], consdata->nvars, consdata->vars, 1.0) );
1716  }
1717  }
1718 
1719  return SCIP_OKAY;
1720 }
1721 
1722 /** adds linear relaxation of or constraint to the LP */
1723 static
1725  SCIP* scip, /**< SCIP data structure */
1726  SCIP_CONS* cons, /**< constraint to check */
1727  SCIP_Bool* infeasible /**< pointer to store whether infeasibility was detected */
1728  )
1729 {
1730  SCIP_CONSDATA* consdata;
1731  int r;
1732 
1733  consdata = SCIPconsGetData(cons);
1734  assert(consdata != NULL);
1735  assert(infeasible != NULL);
1736  assert(!(*infeasible));
1737 
1738  if( consdata->rows[0] == NULL )
1739  {
1740  SCIP_CALL( createRelaxation(scip, cons) );
1741  }
1742  assert(consdata->rows[0] != NULL);
1743  for( r = 0; r < NROWS && !(*infeasible); ++r )
1744  {
1745  if( consdata->rows[r] != NULL && !SCIProwIsInLP(consdata->rows[r]) )
1746  {
1747  SCIP_CALL( SCIPaddCut(scip, NULL, consdata->rows[r], FALSE, infeasible) );
1748  }
1749  }
1750 
1751  return SCIP_OKAY;
1752 }
1753 
1754 /** returns whether all rows of the LP relaxation are in the current LP */
1755 static
1757  SCIP_CONSDATA* consdata /**< constraint data */
1758  )
1759 {
1760  assert(consdata != NULL);
1761 
1762  if( consdata->rows[0] == NULL ) /* LP relaxation does not exist */
1763  return FALSE;
1764  else
1765  {
1766  int r;
1767  for( r = 0; r < NROWS; ++r )
1768  {
1769  if( consdata->rows[r] != NULL && !SCIProwIsInLP(consdata->rows[r]) )
1770  return FALSE;
1771  }
1772  return TRUE;
1773  }
1774 }
1775 
1776 /** checks xor constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
1777 static
1779  SCIP* scip, /**< SCIP data structure */
1780  SCIP_CONS* cons, /**< constraint to check */
1781  SCIP_SOL* sol, /**< solution to check, NULL for current solution */
1782  SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
1783  SCIP_Bool* violated /**< pointer to store whether the constraint is violated */
1784  )
1785 {
1786  SCIP_CONSDATA* consdata;
1787 
1788  assert(violated != NULL);
1789 
1790  consdata = SCIPconsGetData(cons);
1791  assert(consdata != NULL);
1792 
1793  *violated = FALSE;
1794 
1795  /* check feasibility of constraint if necessary */
1796  if( checklprows || !allRowsInLP(consdata) )
1797  {
1798  SCIP_Real solval;
1799  SCIP_Bool odd;
1800  int ones;
1801  int i;
1802 
1803  /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
1804  * enforcement
1805  */
1806  if( sol == NULL )
1807  {
1808  SCIP_CALL( SCIPincConsAge(scip, cons) );
1809  }
1810 
1811  /* check, if all variables and the rhs sum up to an even value */
1812  odd = consdata->rhs;
1813  ones = 0;
1814  for( i = 0; i < consdata->nvars; ++i )
1815  {
1816  solval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
1817  assert(SCIPisFeasIntegral(scip, solval));
1818  odd = (odd != (solval > 0.5));
1819 
1820  if( solval > 0.5 )
1821  ++ones;
1822  }
1823  if( odd )
1824  {
1825  *violated = TRUE;
1826 
1827  /* only reset constraint age if we are in enforcement */
1828  if( sol == NULL )
1829  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1830  }
1831  else if( consdata->intvar != NULL )
1832  {
1833  solval = SCIPgetSolVal(scip, sol, consdata->intvar);
1834  assert(SCIPisFeasIntegral(scip, solval));
1835 
1836  if( !SCIPisFeasEQ(scip, ones - 2 * solval, (SCIP_Real) consdata->rhs) )
1837  *violated = TRUE;
1838  }
1839 
1840  /* only reset constraint age if we are in enforcement */
1841  if( *violated && sol == NULL )
1842  {
1843  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1844  }
1845  }
1846 
1847  return SCIP_OKAY;
1848 }
1849 
1850 /** separates current LP solution
1851  *
1852  * Consider a XOR-constraint
1853  * \f[
1854  * x_1 \oplus x_2 \oplus \dots \oplus x_n = b
1855  * \f]
1856  * with \f$b \in \{0,1\}\f$ and a solution \f$x^*\f$ to be cut off. Small XOR constraints are handled by adding the
1857  * inequalities of the convex hull.
1858  *
1859  * The separation of larger XOR constraints has been described by @n
1860  * Xiaojie Zhang and Paul H. Siegel@n
1861  * "Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes"@n
1862  * IEEE Transactions on Information Theory, vol. 58, no. 10, 2012
1863  *
1864  * We separate the inequalities
1865  * \f[
1866  * \sum_{j \in S} (1 - x_j) + \sum_{j \notin S} x_j \geq 1
1867  * \f]
1868  * with \f$|S| \equiv (b+1) \mbox{ mod } 2\f$ as follows. That these inequalities are valid can be seen as follows: Let
1869  * \f$x\f$ be a feasible solution and suppose that the inequality is violated for some \f$S\f$. Then \f$x_j = 1\f$ for
1870  * all \f$j \in S\f$ and \f$x_j = 0\f$ for all \f$j \notin S\f$. Thus we should have
1871  * \f[
1872  * \oplus_{j \in S} x_j = |S| \mbox{ mod } 2 = b+1 \mbox{ mod } 2,
1873  * \f]
1874  * which is not equal to \f$b\f$ as required by the XOR-constraint.
1875  *
1876  * Let \f$L= \{j \;:\; x^*_j > \frac{1}{2}\}\f$. Suppose that \f$|L|\f$ has @em not the same parity as \f$b\f$ rhs. Then
1877  * \f[
1878  * \sum_{j \in L} (1 - x_j) + \sum_{j \notin L} x_j \geq 1
1879  * \f]
1880  * is the only inequality that can be violated. We rewrite the inequality as
1881  * \f[
1882  * \sum_{j \in L} x_j - \sum_{j \notin L} x_j \leq |L| - 1.
1883  * \f]
1884  * These inequalities are added.
1885  *
1886  * Otherwise let \f$k = \mbox{argmin}\{x^*_j \;:\; j \in L\}\f$ and check the inequality for \f$L \setminus \{k\}\f$
1887  * and similarly for \f$k = \mbox{argmax}\{x^*_j \;:\; j \in L\}\f$.
1888  */
1889 static
1891  SCIP* scip, /**< SCIP data structure */
1892  SCIP_CONS* cons, /**< constraint to check */
1893  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1894  SCIP_Bool separateparity, /**< should parity inequalities be separated? */
1895  SCIP_Bool* separated, /**< pointer to store whether a cut was found */
1896  SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1897  )
1898 {
1899  SCIP_CONSDATA* consdata;
1900  SCIP_Real feasibility;
1901  int r;
1902 
1903  assert( separated != NULL );
1904  assert( cutoff != NULL );
1905  *cutoff = FALSE;
1906 
1907  consdata = SCIPconsGetData(cons);
1908  assert(consdata != NULL);
1909 
1910  *separated = FALSE;
1911 
1912  /* create row for the linear relaxation */
1913  if( consdata->rows[0] == NULL )
1914  {
1915  SCIP_CALL( createRelaxation(scip, cons) );
1916  }
1917  assert(consdata->rows[0] != NULL);
1918 
1919  /* test rows for feasibility and add it, if it is infeasible */
1920  for( r = 0; r < NROWS; ++r )
1921  {
1922  if( consdata->rows[r] != NULL && !SCIProwIsInLP(consdata->rows[r]) )
1923  {
1924  feasibility = SCIPgetRowSolFeasibility(scip, consdata->rows[r], sol);
1925  if( SCIPisFeasNegative(scip, feasibility) )
1926  {
1927  SCIP_CALL( SCIPaddCut(scip, sol, consdata->rows[r], FALSE, cutoff) );
1928  if ( *cutoff )
1929  return SCIP_OKAY;
1930  *separated = TRUE;
1931  }
1932  }
1933  }
1934 
1935  /* separate parity inequalities if required */
1936  if ( separateparity && consdata->nvars > 3 )
1937  {
1938  char name[SCIP_MAXSTRLEN];
1939  SCIP_Real maxval = -1.0;
1940  SCIP_Real minval = 2.0;
1941  SCIP_Real sum = 0.0;
1942  int maxidx = -1;
1943  int minidx = -1;
1944  int ngen = 0;
1945  int cnt = 0;
1946  int j;
1947 
1948  SCIPdebugMsg(scip, "separating parity inequalities ...\n");
1949 
1950  /* compute value */
1951  for (j = 0; j < consdata->nvars; ++j)
1952  {
1953  SCIP_Real val;
1954 
1955  val = SCIPgetSolVal(scip, sol, consdata->vars[j]);
1956  if ( SCIPisFeasGT(scip, val, 0.5) )
1957  {
1958  if ( val < minval )
1959  {
1960  minval = val;
1961  minidx = j;
1962  }
1963  ++cnt;
1964  sum += (1.0 - val);
1965  }
1966  else
1967  {
1968  if ( val > maxval )
1969  {
1970  maxval = val;
1971  maxidx = j;
1972  }
1973  sum += val;
1974  }
1975  }
1976 
1977  /* if size of set does not have the same parity as rhs (e.g., size is odd if rhs is 0) */
1978  if ( (cnt - consdata->rhs) % 2 == 1 )
1979  {
1980  if ( SCIPisEfficacious(scip, 1.0 - sum) )
1981  {
1982  SCIP_ROW* row;
1983 
1984  SCIPdebugMsg(scip, "found violated parity cut (efficiacy: %f)\n", 1.0 - sum);
1985 
1986  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "parity#%s", SCIPconsGetName(cons));
1987  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real) (cnt - 1), FALSE, FALSE, TRUE) );
1988  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
1989 
1990  /* fill in row */
1991  for (j = 0; j < consdata->nvars; ++j)
1992  {
1993  if ( SCIPisFeasGT(scip, SCIPgetSolVal(scip, sol, consdata->vars[j]), 0.5) )
1994  {
1995  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
1996  }
1997  else
1998  {
1999  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2000  }
2001  }
2002  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
2003  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
2004  SCIP_CALL( SCIPaddCut(scip, NULL, row, FALSE, cutoff) );
2005  assert( SCIPisGT(scip, SCIPgetRowLPActivity(scip, row), (SCIP_Real) (cnt-1)) );
2006  SCIP_CALL( SCIPreleaseRow(scip, &row) );
2007  ++ngen;
2008  }
2009  }
2010  else
2011  {
2012  /* If the parity is equal: check removing the element with smallest value from the set and adding the
2013  * element with largest value to the set. If we remove the element with smallest value, we have to subtract (1
2014  * - minval) and add minval to correct the sum. */
2015  if ( SCIPisEfficacious(scip, 1.0 - (sum - 1.0 + 2.0 * minval)) )
2016  {
2017  SCIP_ROW* row;
2018 
2019  SCIPdebugMsg(scip, "found violated parity cut (efficiacy: %f, minval: %f)\n", 1.0 - (sum - 1.0 + 2.0 * minval), minval);
2020 
2021  /* the rhs of the inequality is the corrected set size minus 1 */
2022  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "parity#%s", SCIPconsGetName(cons));
2023  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real) (cnt - 2), FALSE, FALSE, TRUE) );
2024  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
2025 
2026  /* fill in row */
2027  for (j = 0; j < consdata->nvars; ++j)
2028  {
2029  if ( SCIPisFeasGT(scip, SCIPgetSolVal(scip, sol, consdata->vars[j]), 0.5) )
2030  {
2031  /* if the index corresponds to the smallest element, we reverse the sign */
2032  if ( j == minidx )
2033  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2034  else
2035  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2036  }
2037  else
2038  {
2039  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2040  }
2041  }
2042  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
2043  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
2044  SCIP_CALL( SCIPaddCut(scip, NULL, row, FALSE, cutoff) );
2045  assert( SCIPisGT(scip, SCIPgetRowLPActivity(scip, row), (SCIP_Real) (cnt-2)) );
2046  SCIP_CALL( SCIPreleaseRow(scip, &row) );
2047  ++ngen;
2048  }
2049 
2050  /* If we add the element with largest value, we have to add (1 - maxval) and subtract maxval to get the correct sum. */
2051  if ( SCIPisEfficacious(scip, 1.0 - (sum + 1.0 - 2.0 * maxval)) )
2052  {
2053  SCIP_ROW* row;
2054 
2055  SCIPdebugMsg(scip, "found violated parity cut (efficiacy: %f, maxval: %f)\n", 1.0 - (sum + 1.0 - 2.0 * maxval), maxval);
2056 
2057  /* the rhs of the inequality is the size of the corrected set */
2058  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "parity#%s", SCIPconsGetName(cons));
2059  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real) cnt, FALSE, FALSE, TRUE) );
2060  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
2061 
2062  /* fill in row */
2063  for (j = 0; j < consdata->nvars; ++j)
2064  {
2065  if ( SCIPisFeasGT(scip, SCIPgetSolVal(scip, sol, consdata->vars[j]), 0.5) )
2066  {
2067  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2068  }
2069  else
2070  {
2071  /* if the index corresponds to the largest element, we reverse the sign */
2072  if ( j == maxidx )
2073  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2074  else
2075  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2076  }
2077  }
2078  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
2079  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
2080  SCIP_CALL( SCIPaddCut(scip, NULL, row, FALSE, cutoff) );
2081  assert( *cutoff || SCIPisGT(scip, SCIPgetRowLPActivity(scip, row), (SCIP_Real)(j-1)) );
2082  SCIP_CALL( SCIPreleaseRow(scip, &row) );
2083  ++ngen;
2084  }
2085  }
2086 
2087  SCIPdebugMsg(scip, "separated parity inequalites: %d\n", ngen);
2088  if ( ngen > 0 )
2089  *separated = TRUE;
2090  }
2091 
2092  return SCIP_OKAY;
2093 }
2094 
2095 /** Transform linear system \f$A x = b\f$ into row echolon form via the Gauss algorithm with row pivoting over GF2
2096  * @returns the rank of @p A
2097  *
2098  * Here, \f$A \in R^{m \times n},\; b \in R^m\f$. On exit, the vector @p p contains a permutation of the row indices
2099  * used for pivoting and the function returns the rank @p r of @p A. For each row \f$i = 1, \ldots, r\f$, the entry @p
2100  * s[i] contains the column index of the first nonzero in row @p i.
2101  */
2102 static
2104  SCIP* scip, /**< SCIP data structure */
2105  int m, /**< number of rows */
2106  int n, /**< number of columns */
2107  int* p, /**< row permutation */
2108  int* s, /**< steps indicators of the row echolon form */
2109  Type** A, /**< matrix */
2110  Type* b /**< rhs */
2111  )
2112 {
2113  int pi;
2114  int i;
2115  int j;
2116  int k;
2117 
2118  assert( A != NULL );
2119  assert( b != NULL );
2120  assert( p != NULL );
2121  assert( s != NULL );
2122 
2123  /* init permutation and step indicators */
2124  for (i = 0; i < m; ++i)
2125  {
2126  p[i] = i;
2127  s[i] = i;
2128  }
2129 
2130  /* loop through possible steps in echolon form (stop at min {n, m}) */
2131  for (i = 0; i < m && i < n; ++i)
2132  {
2133  assert( s[i] == i );
2134 
2135  /* init starting column */
2136  if ( i == 0 )
2137  j = 0;
2138  else
2139  j = s[i-1] + 1;
2140 
2141  /* find pivot row (i.e., first nonzero entry), if all entries in current row are 0 we search the next column */
2142  do
2143  {
2144  /* search in current column j */
2145  k = i;
2146  while ( k < m && A[p[k]][j] == 0 )
2147  ++k;
2148 
2149  /* found pivot */
2150  if ( k < m )
2151  break;
2152 
2153  /* otherwise search next column */
2154  ++j;
2155  }
2156  while ( j < n );
2157 
2158  /* if not pivot entry was found (checked all columns), the rank of A is equal to the current index i; in this case
2159  * all entries in and below row i are 0 */
2160  if ( j >= n )
2161  return i;
2162 
2163  /* at this place: we have found a pivot entry (p[k], j) */
2164  assert( k < m );
2165 
2166  /* store step index */
2167  s[i] = j;
2168  assert( A[p[k]][j] != 0 );
2169 
2170  /* swap row indices */
2171  if ( k != i )
2172  {
2173  int h = p[i];
2174  p[i] = p[k];
2175  p[k] = h;
2176  }
2177  pi = p[i];
2178  assert( A[pi][s[i]] != 0 );
2179 
2180  /* do elimination */
2181  for (k = i+1; k < m; ++k)
2182  {
2183  int pk = p[k];
2184  /* if entry in leading column is nonzero (otherwise we already have a 0) */
2185  if ( A[pk][s[i]] != 0 )
2186  {
2187  for (j = s[i]; j < n; ++j)
2188  A[pk][j] = A[pk][j] ^ A[pi][j];
2189  b[pk] = b[pk] ^ b[pi];
2190  }
2191  }
2192 
2193  /* check stopped (only every 100 rows in order to save time */
2194  if ( i % 100 == 99 )
2195  {
2196  if ( SCIPisStopped(scip) )
2197  return -1;
2198  }
2199  }
2200 
2201  /* at this point we have treated all rows in which a step can occur; the rank is the minimum of the number of rows or
2202  * columns min {n,m}. */
2203  if ( n <= m )
2204  return n;
2205  return m;
2206 }
2207 
2208 /** Construct solution from matrix in row echolon form over GF2
2209  *
2210  * Compute solution of \f$A x = b\f$, which is already in row echolon form (@see computeRowEcholonGF2()) */
2211 static
2212 void solveRowEcholonGF2(
2213  int m, /**< number of rows */
2214  int n, /**< number of columns */
2215  int r, /**< rank of matrix */
2216  int* p, /**< row permutation */
2217  int* s, /**< steps indicators of the row echolon form */
2218  Type** A, /**< matrix */
2219  Type* b, /**< rhs */
2220  Type* x /**< solution vector on exit */
2221  )
2222 {
2223  int i;
2224  int k;
2225 
2226  assert( A != NULL );
2227  assert( b != NULL );
2228  assert( s != NULL );
2229  assert( p != NULL );
2230  assert( x != NULL );
2231  assert( r <= m && r <= n );
2232 
2233  /* init solution vector to 0 */
2234  for (k = 0; k < n; ++k)
2235  x[k] = 0;
2236 
2237  /* init last entry */
2238  x[s[r-1]] = b[p[r-1]];
2239 
2240  /* loop backwards through solution vector */
2241  for (i = r-2; i >= 0; --i)
2242  {
2243  Type val;
2244 
2245  assert( i <= s[i] && s[i] <= n );
2246 
2247  /* init val with rhs and then add the contributions of the components of x already computed */
2248  val = b[p[i]];
2249  for (k = i+1; k < r; ++k)
2250  {
2251  assert( i <= s[k] && s[k] <= n );
2252  if ( A[p[i]][s[k]] != 0 )
2253  val = val ^ x[s[k]];
2254  }
2255 
2256  /* store solution */
2257  x[s[i]] = val;
2258  }
2259 }
2260 
2261 /** solve equation system over GF 2 by Gauss algorithm and create solution out of it or return cutoff
2262  *
2263  * Collect all information in xor constraints into a linear system over GF2. Then solve the system by computing a row
2264  * echolon form. If the system is infeasible, the current node is infeasible. Otherwise, we can compute a solution for
2265  * the xor constraints given. We check whether this gives a solution for the whole problem.
2266  *
2267  * We sort the columns with respect to the product of the objective coefficients and 1 minus the current LP solution
2268  * value. The idea is that columns that are likely to provide the steps in the row echolon form should appear towards
2269  * the front of the matrix. The smaller the product, the more it makes sense to set the variable to 1 (because the
2270  * solution value is already close to 1 and the objective function is small).
2271  *
2272  * Note that this function is called from propagation where usually no solution is available. However, the solution is
2273  * only used for sorting the columns. Thus, the procedure stays correct even with nonsense solutions.
2274  */
2275 static
2277  SCIP* scip, /**< SCIP data structure */
2278  SCIP_CONS** conss, /**< xor constraints */
2279  int nconss, /**< number of xor constraints */
2280  SCIP_SOL* currentsol, /**< current solution (maybe NULL) */
2281  SCIP_RESULT* result /**< result of propagation (possibly cutoff, no change if primal solution has been tried) */
2282  )
2283 {
2284  SCIP_CONSDATA* consdata;
2285  SCIP_HASHMAP* varhash;
2286  SCIP_Bool* xoractive;
2287  SCIP_Real* xorvals;
2288  SCIP_VAR** xorvars;
2289  SCIP_Bool noaggr = TRUE;
2290  Type** A;
2291  Type* b;
2292  int* s;
2293  int* p;
2294  int* xoridx;
2295  int* xorbackidx;
2296  int nconssactive = 0;
2297  int nconssmat = 0;
2298  int nvarsmat = 0;
2299  int nvars;
2300  int rank;
2301  int i;
2302  int j;
2303 
2304  assert( scip != NULL );
2305  assert( conss != NULL );
2306  assert( result != NULL );
2307 
2308  if ( *result == SCIP_CUTOFF )
2309  return SCIP_OKAY;
2310 
2311  SCIPdebugMsg(scip, "Checking feasibility via the linear equation system over GF2 using Gauss.\n");
2312 
2313  nvars = SCIPgetNVars(scip);
2314 
2315  /* set up hash map from variable to column index */
2316  SCIP_CALL( SCIPhashmapCreate(&varhash, SCIPblkmem(scip), nvars) );
2317  SCIP_CALL( SCIPallocBufferArray(scip, &xoractive, nconss) );
2318  SCIP_CALL( SCIPallocBufferArray(scip, &xorvars, nvars) );
2319  SCIP_CALL( SCIPallocBufferArray(scip, &xoridx, nvars) );
2320  SCIP_CALL( SCIPallocBufferArray(scip, &xorvals, nvars) );
2321 
2322  /* collect variables */
2323  for (i = 0; i < nconss; ++i)
2324  {
2325  int cnt = 0;
2326 
2327  xoractive[i] = FALSE;
2328 
2329  assert( conss[i] != NULL );
2330  consdata = SCIPconsGetData(conss[i]);
2331  assert( consdata != NULL );
2332 
2333  /* count nonfixed variables in constraint */
2334  for (j = 0; j < consdata->nvars; ++j)
2335  {
2336  SCIP_VAR* var;
2337 
2338  var = consdata->vars[j];
2339  assert( var != NULL );
2340  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
2341 
2342  /* replace negated variables */
2343  if ( SCIPvarIsNegated(var) )
2344  var = SCIPvarGetNegatedVar(var);
2345  assert( var != NULL );
2346 
2347  /* consider nonfixed variables */
2348  if ( SCIPcomputeVarLbLocal(scip, var) < 0.5 && SCIPcomputeVarUbLocal(scip, var) > 0.5 )
2349  {
2350  /* consider active variables and collect only new ones */
2351  if ( SCIPvarIsActive(var) && ! SCIPhashmapExists(varhash, var) )
2352  {
2353  /* add variable in map */
2354  SCIP_CALL( SCIPhashmapInsert(varhash, var, (void*) (size_t) nvarsmat) );
2355  assert( nvarsmat == (int) (size_t) SCIPhashmapGetImage(varhash, var) );
2356  xorvals[nvarsmat] = SCIPvarGetObj(var) * (1.0 - SCIPgetSolVal(scip, currentsol, var));
2357  xorvars[nvarsmat++] = var;
2358  }
2359  ++cnt;
2360  }
2361  }
2362 
2363  if ( cnt > 0 )
2364  {
2365  xoractive[i] = TRUE;
2366  ++nconssactive;
2367  }
2368 #ifdef SCIP_DISABLED_CODE
2369  /* The following can save time, if there are constraints with all variables fixed that are infeasible; this
2370  * should, however, be detected somewhere else, e.g., in propagateCons(). */
2371  else
2372  {
2373  /* all variables are fixed - check whether constraint is feasible (could be that the constraint is not propagated) */
2374  assert( cnt == 0 );
2375  for (j = 0; j < consdata->nvars; ++j)
2376  {
2377  /* count variables fixed to 1 */
2378  if ( SCIPcomputeVarLbLocal(scip, consdata->vars[j]) > 0.5 )
2379  ++cnt;
2380  else
2381  assert( SCIPcomputeVarUbLocal(scip, consdata->vars[j]) < 0.5 );
2382  }
2383  if ( ( cnt - consdata->rhs ) % 2 != 0 )
2384  {
2385  SCIPdebugMsg(scip, "constraint <%s> with all variables fixed is violated.\n", SCIPconsGetName(conss[i]));
2386  *result = SCIP_CUTOFF;
2387  break;
2388  }
2389  }
2390 #endif
2391  }
2392  assert( nvarsmat <= nvars );
2393  assert( nconssactive <= nconss );
2394 
2395  if ( nconssactive > MAXXORCONSSSYSTEM || nvarsmat > MAXXORVARSSYSTEM || *result == SCIP_CUTOFF )
2396  {
2397  SCIPdebugMsg(scip, "Skip checking the xor system over GF2 (%d conss, %d vars).\n", nconssactive, nvarsmat);
2398  SCIPfreeBufferArray(scip, &xorvals);
2399  SCIPfreeBufferArray(scip, &xoridx);
2400  SCIPfreeBufferArray(scip, &xorvars);
2401  SCIPfreeBufferArray(scip, &xoractive);
2402  SCIPhashmapFree(&varhash);
2403  return SCIP_OKAY;
2404  }
2405 
2406  /* init index */
2407  for (j = 0; j < nvarsmat; ++j)
2408  xoridx[j] = j;
2409 
2410  /* Sort variables non-decreasingly with respect to product of objective and 1 minus the current solution value: the
2411  * smaller the value the better it would be to set the variable to 1. This is more likely if the variable appears
2412  * towards the front of the matrix, because only the entries on the steps in the row echolon form will have the
2413  * chance to be nonzero.
2414  */
2415  SCIPsortRealIntPtr(xorvals, xoridx, (void**) xorvars, nvarsmat);
2416  SCIPfreeBufferArray(scip, &xorvals);
2417 
2418  /* build back index */
2419  SCIP_CALL( SCIPallocBufferArray(scip, &xorbackidx, nvarsmat) );
2420  for (j = 0; j < nvarsmat; ++j)
2421  {
2422  assert( 0 <= xoridx[j] && xoridx[j] < nvarsmat );
2423  xorbackidx[xoridx[j]] = j;
2424  }
2425 
2426  /* init matrix and rhs */
2427  SCIP_CALL( SCIPallocBufferArray(scip, &b, nconssactive) );
2428  SCIP_CALL( SCIPallocBufferArray(scip, &A, nconssactive) );
2429  for (i = 0; i < nconss; ++i)
2430  {
2431  if ( ! xoractive[i] )
2432  continue;
2433 
2434  assert( conss[i] != NULL );
2435  consdata = SCIPconsGetData(conss[i]);
2436  assert( consdata != NULL );
2437  assert( consdata->nvars > 0 );
2438 
2439  SCIP_CALL( SCIPallocBufferArray(scip, &(A[nconssmat]), nvarsmat) ); /*lint !e866*/
2440  BMSclearMemoryArray(A[nconssmat], nvarsmat); /*lint !e866*/
2441 
2442  /* correct rhs w.r.t. to fixed variables and count nonfixed variables in constraint */
2443  b[nconssmat] = (Type) consdata->rhs;
2444  for (j = 0; j < consdata->nvars; ++j)
2445  {
2446  SCIP_VAR* var;
2447  int idx;
2448 
2449  var = consdata->vars[j];
2450  assert( var != NULL );
2451 
2452  /* replace negated variables */
2453  if ( SCIPvarIsNegated(var) )
2454  {
2455  var = SCIPvarGetNegatedVar(var);
2456  assert( var != NULL );
2457  b[nconssmat] = ! b[nconssmat];
2458  }
2459 
2460 
2461  /* replace aggregated variables */
2463  {
2464  SCIP_Real scalar;
2465  SCIP_Real constant;
2466 
2467  scalar = SCIPvarGetAggrScalar(var);
2468  constant = SCIPvarGetAggrConstant(var);
2469 
2470  /* the variable resolves to a constant, we just update the rhs */
2471  if( SCIPisEQ(scip, scalar, 0.0) )
2472  {
2473  assert(SCIPisEQ(scip, constant, 0.0) || SCIPisEQ(scip, constant, 1.0));
2474  if( SCIPisEQ(scip, constant, 1.0) )
2475  b[nconssmat] = ! b[nconssmat];
2476  var = NULL;
2477  break;
2478  }
2479  /* replace aggregated variable by active variable and update rhs, if needed */
2480  else
2481  {
2482  assert(SCIPisEQ(scip, scalar, 1.0) || SCIPisEQ(scip, scalar, -1.0));
2483  if( SCIPisEQ(scip, constant, 1.0) )
2484  b[nconssmat] = ! b[nconssmat];
2485 
2486  var = SCIPvarGetAggrVar(var);
2487  assert(var != NULL);
2488  }
2489  }
2490  /* variable resolved to a constant */
2491  if( var == NULL )
2492  continue;
2493 
2494  /* If the constraint contains multiaggregated variables, the solution might not be valid, since the
2495  * implications are not represented in the matrix.
2496  */
2498  noaggr = FALSE;
2499 
2500  if ( SCIPcomputeVarLbLocal(scip, var) > 0.5 )
2501  {
2502  /* variable is fixed to 1, invert rhs */
2503  b[nconssmat] = ! b[nconssmat];
2504  assert( ! SCIPhashmapExists(varhash, var) );
2505  }
2506  else
2507  {
2510  if ( SCIPvarIsActive(var) && SCIPcomputeVarUbLocal(scip, var) > 0.5 )
2511  {
2512  assert( SCIPhashmapExists(varhash, var) );
2513  idx = (int) (size_t) SCIPhashmapGetImage(varhash, var);
2514  assert( idx < nvarsmat );
2515  assert( 0 <= xorbackidx[idx] && xorbackidx[idx] < nvarsmat );
2516  A[nconssmat][xorbackidx[idx]] = 1;
2517  }
2518  }
2519  }
2520  ++nconssmat;
2521  }
2522  SCIPdebugMsg(scip, "Found %d non-fixed variables in %d nonempty xor constraints.\n", nvarsmat, nconssmat);
2523  assert( nconssmat == nconssactive );
2524 
2525  /* perform Gauss algorithm */
2526  SCIP_CALL( SCIPallocBufferArray(scip, &p, nconssmat) );
2527  SCIP_CALL( SCIPallocBufferArray(scip, &s, nconssmat) );
2528 
2529 #ifdef SCIP_OUTPUT
2530  SCIPinfoMessage(scip, NULL, "Matrix before Gauss (size: %d x %d):\n", nconssmat, nvarsmat);
2531  for (i = 0; i < nconssmat; ++i)
2532  {
2533  for (j = 0; j < nvarsmat; ++j)
2534  SCIPinfoMessage(scip, NULL, "%d ", A[i][j]);
2535  SCIPinfoMessage(scip, NULL, " = %d\n", b[i]);
2536  }
2537  SCIPinfoMessage(scip, NULL, "\n");
2538 #endif
2539 
2540  rank = -1;
2541  if ( ! SCIPisStopped(scip) )
2542  {
2543  rank = computeRowEcholonGF2(scip, nconssmat, nvarsmat, p, s, A, b);
2544  assert( rank <= nconssmat && rank <= nvarsmat );
2545  }
2546 
2547  /* rank is < 0 if the solution process has been stopped */
2548  if ( rank >= 0 )
2549  {
2550 #ifdef SCIP_OUTPUT
2551  SCIPinfoMessage(scip, NULL, "Matrix after Gauss (rank: %d):\n", rank);
2552  for (i = 0; i < nconssmat; ++i)
2553  {
2554  for (j = 0; j < nvarsmat; ++j)
2555  SCIPinfoMessage(scip, NULL, "%d ", A[p[i]][j]);
2556  SCIPinfoMessage(scip, NULL, " = %d\n", b[p[i]]);
2557  }
2558  SCIPinfoMessage(scip, NULL, "\n");
2559 #endif
2560 
2561  /* check whether system is feasible */
2562  for (i = rank; i < nconssmat; ++i)
2563  {
2564  if ( b[p[i]] != 0 )
2565  break;
2566  }
2567 
2568  /* did not find nonzero entry in b -> equation system is feasible */
2569  if ( i >= nconssmat )
2570  {
2571  SCIPdebugMsg(scip, "System feasible with rank %d (nconss=%d)\n", rank, nconssmat);
2572 
2573  /* matrix has full rank, solution is unique */
2574  if( rank == nvarsmat && noaggr )
2575  {
2576  SCIP_Bool tightened;
2577  SCIP_Bool infeasible;
2578  Type* x;
2579 
2580  SCIPdebugMsg(scip, "Found unique solution.\n");
2581 
2582  /* construct solution */
2583  SCIP_CALL( SCIPallocBufferArray(scip, &x, nvarsmat) );
2584  solveRowEcholonGF2(nconssmat, nvarsmat, rank, p, s, A, b, x);
2585 
2586 #ifdef SCIP_OUTPUT
2587  SCIPinfoMessage(scip, NULL, "Solution:\n");
2588  for (j = 0; j < nvarsmat; ++j)
2589  SCIPinfoMessage(scip, NULL, "%d ", x[j]);
2590  SCIPinfoMessage(scip, NULL, "\n");
2591 #endif
2592 
2593  /* fix variables according to computed unique solution */
2594  for( j = 0; j < nvarsmat; ++j )
2595  {
2596  assert( (int) (size_t) SCIPhashmapGetImage(varhash, xorvars[j]) < nvars );
2597  assert( xorbackidx[(int) (size_t) SCIPhashmapGetImage(varhash, xorvars[j])] == j );
2598  assert( SCIPcomputeVarLbLocal(scip, xorvars[j]) < 0.5 );
2599  if( x[j] == 0 )
2600  {
2601  SCIP_CALL( SCIPtightenVarUb(scip, xorvars[j], 0.0, FALSE, &infeasible, &tightened) );
2602  assert(tightened);
2603  assert(!infeasible);
2604  }
2605  else
2606  {
2607  assert(x[j] == 1);
2608  SCIP_CALL( SCIPtightenVarLb(scip, xorvars[j], 1.0, FALSE, &infeasible, &tightened) );
2609  assert(tightened);
2610  assert(!infeasible);
2611  }
2612  }
2613  SCIPfreeBufferArray(scip, &x);
2614  }
2615  /* matrix does not have full rank, we add the solution, but cannot derive fixings */
2616  else
2617  {
2618  SCIP_HEUR* heurtrysol;
2619 
2620  SCIPdebugMsg(scip, "Found solution.\n");
2621 
2622  /* try solution */
2623  heurtrysol = SCIPfindHeur(scip, "trysol");
2624 
2625  if ( heurtrysol != NULL )
2626  {
2627  SCIP_Bool success;
2628  SCIP_VAR** vars;
2629  SCIP_SOL* sol;
2630  Type* x;
2631 
2632  /* construct solution */
2633  SCIP_CALL( SCIPallocBufferArray(scip, &x, nvarsmat) );
2634  solveRowEcholonGF2(nconssmat, nvarsmat, rank, p, s, A, b, x);
2635 
2636 #ifdef SCIP_OUTPUT
2637  SCIPinfoMessage(scip, NULL, "Solution:\n");
2638  for (j = 0; j < nvarsmat; ++j)
2639  SCIPinfoMessage(scip, NULL, "%d ", x[j]);
2640  SCIPinfoMessage(scip, NULL, "\n");
2641 #endif
2642 
2643  /* create solution */
2644  SCIP_CALL( SCIPcreateSol(scip, &sol, heurtrysol) );
2645 
2646  /* transfer solution */
2647  for (j = 0; j < nvarsmat; ++j)
2648  {
2649  if ( x[j] != 0 )
2650  {
2651  assert( (int) (size_t) SCIPhashmapGetImage(varhash, xorvars[j]) < nvars );
2652  assert( xorbackidx[(int) (size_t) SCIPhashmapGetImage(varhash, xorvars[j])] == j );
2653  assert( SCIPcomputeVarLbLocal(scip, xorvars[j]) < 0.5 );
2654  SCIP_CALL( SCIPsetSolVal(scip, sol, xorvars[j], 1.0) );
2655  }
2656  }
2657  SCIPfreeBufferArray(scip, &x);
2658 
2659  /* add *all* variables fixed to 1 */
2660  vars = SCIPgetVars(scip);
2661  for (j = 0; j < nvars; ++j)
2662  {
2663  if ( SCIPcomputeVarLbLocal(scip, vars[j]) > 0.5 )
2664  {
2665  SCIP_CALL( SCIPsetSolVal(scip, sol, vars[j], 1.0) );
2666  SCIPdebugMsg(scip, "Added fixed variable <%s>.\n", SCIPvarGetName(vars[j]));
2667  }
2668  }
2669 
2670  /* correct integral variables if necessary */
2671  for (i = 0; i < nconss; ++i)
2672  {
2673  consdata = SCIPconsGetData(conss[i]);
2674  assert(consdata != NULL);
2675 
2676  if ( xoractive[i] && consdata->intvar != NULL )
2677  {
2678  SCIP_Real val;
2679  int nones = 0;
2680 
2681  for (j = 0; j < consdata->nvars; ++j)
2682  {
2683  if ( SCIPgetSolVal(scip, sol, consdata->vars[j]) > 0.5 )
2684  ++nones;
2685  }
2686  /* if there are aggregated variables, the solution might not be feasible */
2687  assert( ! noaggr || nones % 2 == (int) consdata->rhs );
2688  if ( (unsigned int) nones != consdata->rhs )
2689  {
2690  val = (SCIP_Real) (nones - consdata->rhs)/2;
2691  if ( SCIPisGE(scip, val, SCIPvarGetLbGlobal(consdata->intvar)) && SCIPisLE(scip, val, SCIPvarGetUbGlobal(consdata->intvar)) )
2692  {
2693  SCIP_CALL( SCIPsetSolVal(scip, sol, consdata->intvar, val) );
2694  }
2695  }
2696  }
2697  }
2698  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ) );
2699 
2700  /* check feasibility of new solution and pass it to trysol heuristic */
2701  SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
2702  if ( success )
2703  {
2704  SCIP_CALL( SCIPheurPassSolAddSol(scip, heurtrysol, sol) );
2705  SCIPdebugMsg(scip, "Creating solution was successful.\n");
2706  }
2707 #ifdef SCIP_DEBUG
2708  else
2709  {
2710  /* the solution might not be feasible, because of additional constraints */
2711  SCIPdebugMsg(scip, "Creating solution was not successful.\n");
2712  }
2713 #endif
2714  SCIP_CALL( SCIPfreeSol(scip, &sol) );
2715  }
2716  }
2717  }
2718  else
2719  {
2720  *result = SCIP_CUTOFF;
2721  SCIPdebugMsg(scip, "System not feasible.\n");
2722  }
2723  }
2724 
2725  /* free storage */
2726  SCIPfreeBufferArray(scip, &s);
2727  SCIPfreeBufferArray(scip, &p);
2728  j = nconssmat - 1;
2729  for (i = nconss - 1; i >= 0 ; --i)
2730  {
2731  consdata = SCIPconsGetData(conss[i]);
2732  assert(consdata != NULL);
2733 
2734  if ( consdata->nvars == 0 )
2735  continue;
2736 
2737  if( !xoractive[i] )
2738  continue;
2739 
2740  SCIPfreeBufferArray(scip, &(A[j]));
2741  --j;
2742  }
2743  SCIPfreeBufferArray(scip, &A);
2744  SCIPfreeBufferArray(scip, &b);
2745  SCIPfreeBufferArray(scip, &xorbackidx);
2746  SCIPfreeBufferArray(scip, &xoridx);
2747  SCIPfreeBufferArray(scip, &xorvars);
2748  SCIPfreeBufferArray(scip, &xoractive);
2749  SCIPhashmapFree(&varhash);
2750 
2751  return SCIP_OKAY;
2752 }
2753 
2754 /** for each variable in the xor constraint, add it to conflict set; for integral variable add corresponding bound */
2755 static
2757  SCIP* scip, /**< SCIP data structure */
2758  SCIP_CONS* cons, /**< constraint that inferred the bound change */
2759  SCIP_VAR* infervar, /**< variable that was deduced, or NULL (not equal to integral variable) */
2760  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
2761  PROPRULE proprule /**< propagation rule */
2762  )
2763 {
2764  SCIP_CONSDATA* consdata;
2765  SCIP_VAR** vars;
2766  int nvars;
2767  int i;
2768 
2769  assert( cons != NULL );
2770 
2771  consdata = SCIPconsGetData(cons);
2772  assert(consdata != NULL);
2773  vars = consdata->vars;
2774  nvars = consdata->nvars;
2775 
2776  switch( proprule )
2777  {
2778  case PROPRULE_0:
2779  assert( infervar == NULL || infervar == consdata->intvar );
2780 
2781  /* the integral variable was fixed, because all variables were fixed */
2782  for (i = 0; i < nvars; ++i)
2783  {
2784  assert( SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE)) );
2785  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2786  }
2787  break;
2788 
2789  case PROPRULE_1:
2790  /* the variable was inferred, because all other variables were fixed */
2791  for (i = 0; i < nvars; ++i)
2792  {
2793  /* add variables that were fixed to 1 before */
2794  if ( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5 )
2795  {
2796  assert( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE) > 0.5 );
2797  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2798  }
2799  /* add variables that were fixed to 0 */
2800  else if ( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
2801  {
2802  assert( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE) < 0.5 );
2803  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2804  }
2805  else
2806  {
2807  /* check changed variable (changed variable is 0 or 1 afterwards) */
2808  assert( vars[i] == infervar );
2809  }
2810  }
2811  break;
2812 
2813  case PROPRULE_INTLB:
2814  assert( consdata->intvar != NULL );
2815 
2816  if( infervar != consdata->intvar )
2817  {
2818  /* the variable was fixed, because of the lower bound of the integral variable */
2819  SCIP_CALL( SCIPaddConflictLb(scip, consdata->intvar, NULL) );
2820  }
2821  /* to many and the other fixed variables */
2822  for (i = 0; i < nvars; ++i)
2823  {
2824  /* add variables that were fixed to 0 */
2825  if ( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
2826  {
2827  assert( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE) < 0.5 );
2828  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2829  }
2830  }
2831  break;
2832 
2833  case PROPRULE_INTUB:
2834  assert( consdata->intvar != NULL );
2835 
2836  if( infervar != consdata->intvar )
2837  {
2838  /* the variable was fixed, because of upper bound of the integral variable and the other fixed variables */
2839  SCIP_CALL( SCIPaddConflictUb(scip, consdata->intvar, NULL) );
2840  }
2841  for (i = 0; i < nvars; ++i)
2842  {
2843  /* add variables that were fixed to 1 */
2844  if ( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5 )
2845  {
2846  assert( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE) > 0.5 );
2847  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2848  }
2849  }
2850  break;
2851 
2852  case PROPRULE_INVALID:
2853  default:
2854  SCIPerrorMessage("invalid inference information %d in xor constraint <%s>\n", proprule, SCIPconsGetName(cons));
2855  SCIPABORT();
2856  return SCIP_INVALIDDATA; /*lint !e527*/
2857  }
2858 
2859  return SCIP_OKAY;
2860 }
2861 
2862 /** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */
2863 static
2865  SCIP* scip, /**< SCIP data structure */
2866  SCIP_CONS* cons, /**< xor constraint that detected the conflict */
2867  SCIP_VAR* infervar, /**< variable that was deduced, or NULL (not equal to integral variable) */
2868  PROPRULE proprule /**< propagation rule */
2869  )
2870 {
2871  /* conflict analysis can only be applied in solving stage and if it is applicable */
2873  return SCIP_OKAY;
2874 
2875  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
2877 
2878  /* add bound changes */
2879  SCIP_CALL( addConflictBounds(scip, cons, infervar, NULL, proprule) );
2880 
2881  /* analyze the conflict */
2882  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
2883 
2884  return SCIP_OKAY;
2885 }
2886 
2887 /** propagates constraint with the following rules:
2888  * (0) all variables are fixed => can fix integral variable
2889  * (1) all except one variable fixed => fix remaining variable and integral variable
2890  * (2) depending on the amount of fixed binary variables we can tighten the integral variable
2891  * (3) depending on the lower bound of the integral variable one can fix variables to 1
2892  * (4) depending on the upper bound of the integral variable one can fix variables to 0
2893  */
2894 static
2896  SCIP* scip, /**< SCIP data structure */
2897  SCIP_CONS* cons, /**< xor constraint to be processed */
2898  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2899  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2900  int* nfixedvars, /**< pointer to add up the number of fixed variables */
2901  int* nchgbds /**< pointer to add up the number of found domain reductions */
2902  )
2903 {
2904  SCIP_CONSDATA* consdata;
2905  SCIP_VAR** vars;
2906  SCIP_Bool infeasible;
2907  SCIP_Bool tightened;
2908  SCIP_Bool odd;
2909  int nvars;
2910  int nfixedones;
2911  int nfixedzeros;
2912  int watchedvar1;
2913  int watchedvar2;
2914  int i;
2915 
2916  assert(scip != NULL);
2917  assert(cons != NULL);
2918  assert(eventhdlr != NULL);
2919  assert(cutoff != NULL);
2920  assert(nfixedvars != NULL);
2921  assert(nchgbds != NULL);
2922 
2923  /* propagation can only be applied, if we know all operator variables */
2924  if( SCIPconsIsModifiable(cons) )
2925  return SCIP_OKAY;
2926 
2927  consdata = SCIPconsGetData(cons);
2928  assert(consdata != NULL);
2929 
2930  vars = consdata->vars;
2931  nvars = consdata->nvars;
2932 
2933  /* don't process the constraint, if the watched variables weren't fixed to any value since last propagation call */
2934  if( consdata->propagated )
2935  return SCIP_OKAY;
2936 
2937  /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
2938  if( !SCIPinRepropagation(scip) )
2939  {
2940  SCIP_CALL( SCIPincConsAge(scip, cons) );
2941  }
2942 
2943  /* propagation cannot be applied, if we have at least two unfixed variables left;
2944  * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
2945  * if these ones get fixed
2946  */
2947  watchedvar1 = consdata->watchedvar1;
2948  watchedvar2 = consdata->watchedvar2;
2949 
2950  /* check, if watched variables are still unfixed */
2951  if( watchedvar1 != -1 )
2952  {
2953  if( SCIPvarGetLbLocal(vars[watchedvar1]) > 0.5 || SCIPvarGetUbLocal(vars[watchedvar1]) < 0.5 )
2954  watchedvar1 = -1;
2955  }
2956  if( watchedvar2 != -1 )
2957  {
2958  if( SCIPvarGetLbLocal(vars[watchedvar2]) > 0.5 || SCIPvarGetUbLocal(vars[watchedvar2]) < 0.5 )
2959  watchedvar2 = -1;
2960  }
2961 
2962  /* if only one watched variable is still unfixed, make it the first one */
2963  if( watchedvar1 == -1 )
2964  {
2965  watchedvar1 = watchedvar2;
2966  watchedvar2 = -1;
2967  }
2968  assert(watchedvar1 != -1 || watchedvar2 == -1);
2969 
2970  /* if the watched variables are invalid (fixed), find new ones if existing; count the parity */
2971  odd = consdata->rhs;
2972  nfixedones = 0;
2973  nfixedzeros = 0;
2974  if( watchedvar2 == -1 )
2975  {
2976  for( i = 0; i < nvars; ++i )
2977  {
2978  if( SCIPvarGetLbLocal(vars[i]) > 0.5 )
2979  {
2980  odd = !odd;
2981  ++nfixedones;
2982  }
2983  else if( SCIPvarGetUbLocal(vars[i]) > 0.5 )
2984  {
2985  if( watchedvar1 == -1 )
2986  {
2987  assert(watchedvar2 == -1);
2988  watchedvar1 = i;
2989  }
2990  else if( watchedvar1 != i )
2991  {
2992  watchedvar2 = i;
2993  break;
2994  }
2995  }
2996  else if ( SCIPvarGetUbLocal(vars[i]) < 0.5 )
2997  ++nfixedzeros;
2998  }
2999  }
3000  assert(watchedvar1 != -1 || watchedvar2 == -1);
3001 
3002  /* if all variables are fixed, we can decide the feasibility of the constraint */
3003  if( watchedvar1 == -1 )
3004  {
3005  assert(watchedvar2 == -1);
3006 
3007  if( odd )
3008  {
3009  SCIPdebugMsg(scip, "constraint <%s>: all vars fixed, constraint is infeasible\n", SCIPconsGetName(cons));
3010 
3011  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
3012  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_0) );
3013  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3014 
3015  *cutoff = TRUE;
3016  }
3017  else
3018  {
3019  /* fix integral variable if present */
3020  if ( consdata->intvar != NULL && !consdata->deleteintvar )
3021  {
3022  int fixval;
3023 
3024  assert( ! *cutoff );
3025  assert( (nfixedones - consdata->rhs) % 2 == 0 );
3026 
3027  fixval = (nfixedones - consdata->rhs)/2; /*lint !e713*/
3028 
3029  SCIPdebugMsg(scip, "fix integral variable <%s> to %d\n", SCIPvarGetName(consdata->intvar), fixval);
3030 
3031  /* check whether value to fix is outside bounds */
3032  if ( fixval + 0.5 < SCIPvarGetLbLocal(consdata->intvar) )
3033  {
3034  /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3035  SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3036  fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3037 
3038  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTLB) );
3039  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3040 
3041  *cutoff = TRUE;
3042  }
3043  else if ( fixval - 0.5 > SCIPvarGetUbLocal(consdata->intvar) )
3044  {
3045  /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3046  SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3047  fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3048 
3049  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTUB) );
3050  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3051 
3052  *cutoff = TRUE;
3053  }
3054  else
3055  {
3056  if ( ! SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->intvar), (SCIP_Real) fixval) )
3057  {
3058  SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_0, FALSE, &infeasible, &tightened) );
3059  assert( tightened );
3060  assert( ! infeasible );
3061  }
3062 
3063  if ( ! SCIPisEQ(scip, SCIPvarGetUbLocal(consdata->intvar), (SCIP_Real) fixval) )
3064  {
3065  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_0, FALSE, &infeasible, &tightened) );
3066  assert( tightened );
3067  assert( ! infeasible );
3068  }
3069 
3070  ++(*nfixedvars);
3071  }
3072  }
3073  else
3074  {
3075  SCIPdebugMsg(scip, "constraint <%s>: all vars fixed, constraint is feasible\n", SCIPconsGetName(cons));
3076  }
3077  }
3078  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3079 
3080  return SCIP_OKAY;
3081  }
3082 
3083  /* if only one variable is not fixed, this variable can be deduced */
3084  if( watchedvar2 == -1 )
3085  {
3086  assert(watchedvar1 != -1);
3087 
3088  SCIPdebugMsg(scip, "constraint <%s>: only one unfixed variable -> fix <%s> to %u\n",
3089  SCIPconsGetName(cons), SCIPvarGetName(vars[watchedvar1]), odd);
3090 
3091  SCIP_CALL( SCIPinferBinvarCons(scip, vars[watchedvar1], odd, cons, (int)PROPRULE_1, &infeasible, &tightened) );
3092  assert(!infeasible);
3093  assert(tightened);
3094 
3095  (*nfixedvars)++;
3096 
3097  /* fix integral variable if present */
3098  if ( consdata->intvar != NULL && !consdata->deleteintvar )
3099  {
3100  int fixval;
3101 
3102  /* if variable has been fixed to 1, adjust number of fixed variables */
3103  if ( odd )
3104  ++nfixedones;
3105 
3106  assert( (nfixedones - consdata->rhs) % 2 == 0 );
3107 
3108  fixval = (nfixedones - consdata->rhs)/2; /*lint !e713*/
3109  SCIPdebugMsg(scip, "should fix integral variable <%s> to %d\n", SCIPvarGetName(consdata->intvar), fixval);
3110 
3111  /* check whether value to fix is outside bounds */
3112  if ( fixval + 0.5 < SCIPvarGetLbLocal(consdata->intvar) )
3113  {
3114  /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3115  SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3116  fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3117 
3118  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTLB) );
3119  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3120 
3121  *cutoff = TRUE;
3122  }
3123  else if ( fixval - 0.5 > SCIPvarGetUbLocal(consdata->intvar) )
3124  {
3125  /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3126  SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3127  fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3128 
3129  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTUB) );
3130  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3131 
3132  *cutoff = TRUE;
3133  }
3134  else
3135  {
3136  if( SCIPvarGetLbLocal(consdata->intvar) + 0.5 < (SCIP_Real) fixval )
3137  {
3138  SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_1, TRUE, &infeasible, &tightened) );
3139  assert( tightened );
3140  assert( ! infeasible );
3141  }
3142 
3143  if( SCIPvarGetUbLocal(consdata->intvar) - 0.5 > (SCIP_Real) fixval )
3144  {
3145  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_1, TRUE, &infeasible, &tightened) );
3146  assert( tightened );
3147  assert( ! infeasible );
3148  }
3149  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar)));
3150 
3151  ++(*nfixedvars);
3152  }
3153  }
3154 
3155  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3156  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3157 
3158  return SCIP_OKAY;
3159  }
3160 
3161  /* propagate w.r.t. integral variable */
3162  if ( consdata->intvar != NULL && !consdata->deleteintvar )
3163  {
3164  SCIP_Real newlb;
3165  SCIP_Real newub;
3166  int nonesmin;
3167  int nonesmax;
3168 
3169  assert( nfixedones + nfixedzeros < nvars );
3170 
3171  assert( SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(consdata->intvar)) );
3172  assert( SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(consdata->intvar)) );
3173 
3174  nonesmin = 2 * (int)(SCIPvarGetLbLocal(consdata->intvar) + 0.5) + consdata->rhs; /*lint !e713*/
3175  nonesmax = 2 * (int)(SCIPvarGetUbLocal(consdata->intvar) + 0.5) + consdata->rhs; /*lint !e713*/
3176 
3177  /* the number of possible variables that can get value 1 is less than the minimum bound */
3178  if ( nvars - nfixedzeros < nonesmin )
3179  {
3180  SCIPdebugMsg(scip, "constraint <%s>: at most %d variables can take value 1, but there should be at least %d.\n", SCIPconsGetName(cons), nvars - nfixedones, nonesmin);
3181 
3182  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTLB) );
3183  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3184 
3185  *cutoff = TRUE;
3186 
3187  return SCIP_OKAY;
3188  }
3189 
3190  /* the number of variables that are fixed to 1 is larger than the maximum bound */
3191  if ( nfixedones > nonesmax )
3192  {
3193  SCIPdebugMsg(scip, "constraint <%s>: at least %d variables are fixed to 1, but there should be at most %d.\n", SCIPconsGetName(cons), nfixedones, nonesmax);
3194 
3195  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTUB) );
3196  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3197 
3198  *cutoff = TRUE;
3199 
3200  return SCIP_OKAY;
3201  }
3202 
3203  /* compute new bounds on the integral variable */
3204  newlb = (SCIP_Real)((nfixedones + 1 - consdata->rhs) / 2); /*lint !e653*/
3205  newub = (SCIP_Real)((nvars - nfixedzeros - consdata->rhs) / 2); /*lint !e653*/
3206 
3207  /* new lower bound is better */
3208  if( newlb > SCIPvarGetLbLocal(consdata->intvar) + 0.5 )
3209  {
3210  SCIPdebugMsg(scip, "constraint <%s>: propagated lower bound of integral variable <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(consdata->intvar), newlb);
3211  SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, newlb, cons, (int)PROPRULE_INTUB, TRUE, &infeasible, &tightened) );
3212  assert(tightened);
3213  assert(!infeasible);
3214 
3215  ++(*nchgbds);
3216 
3217  nonesmin = 2 * (int)(SCIPvarGetLbLocal(consdata->intvar) + 0.5) + consdata->rhs; /*lint !e713*/
3218  }
3219 
3220  /* new upper bound is better */
3221  if( newub < SCIPvarGetUbLocal(consdata->intvar) - 0.5 )
3222  {
3223  SCIPdebugMsg(scip, "constraint <%s>: propagated upper bound of integral variable <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(consdata->intvar), newub);
3224  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, newub, cons, (int)PROPRULE_INTLB, TRUE, &infeasible, &tightened) );
3225  assert(tightened);
3226  assert(!infeasible);
3227 
3228  ++(*nchgbds);
3229 
3230  nonesmax = 2 * (int)(SCIPvarGetUbLocal(consdata->intvar) + 0.5) + consdata->rhs; /*lint !e713*/
3231  }
3232 
3233  assert(nvars - nfixedzeros >= nonesmin);
3234  assert(nfixedones <= nonesmax);
3235 
3236  /* the number of variables that are free or fixed to 1 is exactly the minimum required -> fix free variables to 1 */
3237  if ( nvars - nfixedzeros == nonesmin )
3238  {
3239  SCIPdebugMsg(scip, "constraint <%s>: fix %d free variables to 1 to reach lower bound of %d\n", SCIPconsGetName(cons), nvars - nfixedzeros - nfixedones, nonesmin);
3240 
3241  for (i = 0; i < nvars; ++i)
3242  {
3243  if ( SCIPvarGetLbLocal(vars[i]) < 0.5 && SCIPvarGetUbLocal(vars[i]) > 0.5 )
3244  {
3245  SCIP_CALL( SCIPinferBinvarCons(scip, vars[i], TRUE, cons, (int)PROPRULE_INTLB, &infeasible, &tightened) );
3246  assert( !infeasible );
3247  assert( tightened );
3248 
3249  ++(*nfixedvars);
3250  }
3251  }
3252  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3253  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3254 
3255  return SCIP_OKAY;
3256  }
3257 
3258  /* the number of variables that are fixed to 1 is exactly the maximum required -> fix free variables to 0 */
3259  if ( nfixedones == nonesmax )
3260  {
3261  SCIPdebugMsg(scip, "constraint <%s>: fix %d free variables to 0 to guarantee upper bound of %d\n", SCIPconsGetName(cons), nvars - nfixedzeros - nfixedones, nonesmax);
3262 
3263  for (i = 0; i < nvars; ++i)
3264  {
3265  if ( SCIPvarGetLbLocal(vars[i]) < 0.5 && SCIPvarGetUbLocal(vars[i]) > 0.5 )
3266  {
3267  SCIP_CALL( SCIPinferBinvarCons(scip, vars[i], FALSE, cons, (int)PROPRULE_INTUB, &infeasible, &tightened) );
3268  assert(!infeasible);
3269  assert(tightened);
3270  ++(*nfixedvars);
3271  }
3272  }
3273  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3274  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3275 
3276  return SCIP_OKAY;
3277  }
3278  }
3279 
3280  /* switch to the new watched variables */
3281  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
3282 
3283  /* mark the constraint propagated */
3284  consdata->propagated = TRUE;
3285 
3286  return SCIP_OKAY;
3287 }
3288 
3289 /** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
3290  * propagation rules (see propagateCons())
3291  */
3292 static
3294  SCIP* scip, /**< SCIP data structure */
3295  SCIP_CONS* cons, /**< constraint that inferred the bound change */
3296  SCIP_VAR* infervar, /**< variable that was deduced */
3297  PROPRULE proprule, /**< propagation rule that deduced the value */
3298  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
3299  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
3300  )
3301 {
3302  assert(result != NULL);
3303 
3304  SCIPdebugMsg(scip, "resolving fixations according to rule %d\n", (int) proprule);
3305 
3306  SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, proprule) );
3307  *result = SCIP_SUCCESS;
3308 
3309  return SCIP_OKAY;
3310 }
3311 
3312 /** try to use clique information to delete a part of the xor constraint or even fix variables */
3313 static
3315  SCIP* scip, /**< SCIP data structure */
3316  SCIP_CONS* cons, /**< constraint that inferred the bound change */
3317  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3318  int* nchgcoefs, /**< pointer to add up the number of deleted entries */
3319  int* ndelconss, /**< pointer to add up the number of deleted constraints */
3320  int* naddconss, /**< pointer to add up the number of added constraints */
3321  SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
3322  )
3323 {
3324  SCIP_CONSDATA* consdata;
3325  SCIP_VAR** vars;
3326  int nvars;
3327  SCIP_Bool breaked;
3328  SCIP_Bool restart;
3329  int posnotinclq1;
3330  int posnotinclq2;
3331  int v;
3332  int v1;
3333 
3334  assert(scip != NULL);
3335  assert(cons != NULL);
3336  assert(nfixedvars != NULL);
3337  assert(nchgcoefs != NULL);
3338  assert(ndelconss != NULL);
3339  assert(naddconss != NULL);
3340  assert(cutoff != NULL);
3341 
3342  /* propagation can only be applied, if we know all operator variables */
3343  if( SCIPconsIsModifiable(cons) )
3344  return SCIP_OKAY;
3345 
3346  consdata = SCIPconsGetData(cons);
3347  assert(consdata != NULL);
3348 
3349  vars = consdata->vars;
3350  nvars = consdata->nvars;
3351 
3352  if( nvars < 3 )
3353  return SCIP_OKAY;
3354 
3355  /* we cannot perform this steps if the integer variables in not artificial */
3356  if( !consdata->deleteintvar )
3357  return SCIP_OKAY;
3358 
3359 #if 0 /* try to evaluate if clique presolving should only be done multiple times when the constraint changed */
3360  if( !consdata->changed )
3361  return SCIP_OKAY;
3362 #endif
3363 
3364  /* @todo: if clique information would have saved the type of the clique, like <= 1, or == 1 we could do more
3365  * presolving like:
3366  *
3367  * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2) == 1) => xor(x3,x4) = 0
3368  * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2,x3) == 1) => (x4 = 0 and delete xor constraint)
3369  */
3370 
3371  /* 1. we have only clique information "<=", so we can check if all variables are in the same clique
3372  *
3373  * (xor(x1,x2,x3) = 1 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 = 1 and delete old
3374  * xor-constraint)
3375  *
3376  * (xor(x1,x2,x3) = 0 and clique(x1,x2,x3) <= 1) => (fix all variables x1 = x2 = x3 = 0 and delete old xor-
3377  * constraint)
3378  */
3379 
3380  /* 2. we have only clique information "<=", so we can check if all but one variable are in the same clique
3381  *
3382  * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 + x4 = 1 and
3383  * delete old xor constraint)
3384  *
3385  * (xor(x1,x2,x3,x4) = 0 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 + ~x4 = 1 and
3386  * delete old xor constraint)
3387  */
3388 
3389  posnotinclq1 = -1; /* index of variable that is possible not in the clique */
3390  posnotinclq2 = -1; /* index of variable that is possible not in the clique */
3391  breaked = FALSE;
3392  restart = FALSE;
3393 
3394  v = nvars - 2;
3395  while( v >= 0 )
3396  {
3397  SCIP_VAR* var;
3398  SCIP_VAR* var1;
3399  SCIP_Bool value;
3400  SCIP_Bool value1;
3401 
3402  assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
3403 
3404  value = SCIPvarIsActive(vars[v]);
3405 
3406  if( !value )
3407  var = SCIPvarGetNegationVar(vars[v]);
3408  else
3409  var = vars[v];
3410 
3411  if( posnotinclq1 == v )
3412  {
3413  --v;
3414  continue;
3415  }
3416 
3417  for( v1 = v+1; v1 < nvars; ++v1 )
3418  {
3419  if( posnotinclq1 == v1 )
3420  continue;
3421 
3422  value1 = SCIPvarIsActive(vars[v1]);
3423 
3424  if( !value1 )
3425  var1 = SCIPvarGetNegationVar(vars[v1]);
3426  else
3427  var1 = vars[v1];
3428 
3429  if( !SCIPvarsHaveCommonClique(var, value, var1, value1, TRUE) )
3430  {
3431  /* if the position of the variable which is not in the clique with all other variables is not yet
3432  * initialized, than do now, one of both variables does not fit
3433  */
3434  if( posnotinclq1 == -1 )
3435  {
3436  posnotinclq1 = v;
3437  posnotinclq2 = v1;
3438  }
3439  else
3440  {
3441  /* no clique with exactly nvars-1 variables */
3442  if( restart || (posnotinclq2 != v && posnotinclq2 != v1) )
3443  {
3444  breaked = TRUE;
3445  break;
3446  }
3447 
3448  /* check the second variables for not fitting into the clique of (nvars - 1) variables */
3449  posnotinclq1 = posnotinclq2;
3450  restart = TRUE;
3451  v = nvars - 1;
3452  }
3453 
3454  break;
3455  }
3456  else
3457  assert(vars[v] != vars[v1]);
3458  }
3459 
3460  if( breaked )
3461  break;
3462 
3463  --v;
3464  }
3465 
3466  /* at least nvars-1 variables are in one clique */
3467  if( !breaked )
3468  {
3469  /* all variables are in one clique, case 1 */
3470  if( posnotinclq1 == -1 )
3471  {
3472  /* all variables of xor constraints <%s> (with rhs == 1) are in one clique, so create a setpartitioning
3473  * constraint with all variables and delete this xor-constraint */
3474  if( consdata->rhs )
3475  {
3476  SCIP_CONS* newcons;
3477  char consname[SCIP_MAXSTRLEN];
3478 
3479  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_complete_clq", SCIPconsGetName(cons));
3480  SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, consname, nvars, vars,
3485 
3486  SCIP_CALL( SCIPaddCons(scip, newcons) );
3487  SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
3488  SCIPdebug( SCIP_CALL( SCIPprintCons(scip, newcons, NULL) ) );
3489  ++(*naddconss);
3490 
3491  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3492  }
3493  /* all variables of xor constraints <%s> (with rhs == 0) are in one clique, so fixed all variables to 0 */
3494  else
3495  {
3496  SCIP_Bool infeasible;
3497  SCIP_Bool fixed;
3498 
3499  SCIPdebugMsg(scip, "all variables of xor constraints <%s> are in one clique, so fixed all variables to 0\n",
3500  SCIPconsGetName(cons));
3501  SCIPdebug( SCIP_CALL( SCIPprintCons(scip, cons, NULL) ) );
3502 
3503  for( v = nvars - 1; v >= 0; --v )
3504  {
3505  SCIPdebugMsg(scip, "fixing variable <%s> to 0\n", SCIPvarGetName(vars[v]));
3506  SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, &infeasible, &fixed) );
3507 
3508  assert(infeasible || fixed);
3509 
3510  if( infeasible )
3511  {
3512  *cutoff = infeasible;
3513 
3514  return SCIP_OKAY;
3515  }
3516  else
3517  ++(*nfixedvars);
3518  }
3519  }
3520  }
3521  /* all but one variable are in one clique, case 2 */
3522  else
3523  {
3524  SCIP_CONS* newcons;
3525  char consname[SCIP_MAXSTRLEN];
3526 
3527  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_completed_clq", SCIPconsGetName(cons));
3528 
3529  /* complete clique by creating a set partioning constraint over all variables */
3530 
3531  /* if rhs == FALSE we need to exchange the variable not appaering in the clique with the negated variables */
3532  if( !consdata->rhs )
3533  {
3534  SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, consname, 0, NULL,
3539 
3540  for( v = 0; v < nvars; ++v )
3541  {
3542  if( v == posnotinclq1 )
3543  {
3544  SCIP_VAR* var;
3545 
3546  SCIP_CALL( SCIPgetNegatedVar(scip, vars[v], &var) );
3547  assert(var != NULL);
3548 
3549  SCIP_CALL( SCIPaddCoefSetppc(scip, newcons, var) );
3550  }
3551  else
3552  {
3553  SCIP_CALL( SCIPaddCoefSetppc(scip, newcons, vars[v]) );
3554  }
3555  }
3556  }
3557  /* if rhs == TRUE we can add all variables to the clique constraint directly */
3558  else
3559  {
3560  SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, consname, nvars, vars,
3565  }
3566 
3567  SCIP_CALL( SCIPaddCons(scip, newcons) );
3568  SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
3569  SCIPdebug( SCIP_CALL( SCIPprintCons(scip, newcons, NULL) ) );
3570  ++(*naddconss);
3571 
3572  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3573  }
3574 
3575  /* fix integer variable if it exists */
3576  if( consdata->intvar != NULL )
3577  {
3578  SCIP_Bool infeasible;
3579  SCIP_Bool fixed;
3580 
3581  SCIPdebugMsg(scip, "also fix the integer variable <%s> to 0\n", SCIPvarGetName(consdata->intvar));
3582  SCIP_CALL( SCIPfixVar(scip, consdata->intvar, 0.0, &infeasible, &fixed) );
3583 
3584  assert(infeasible || fixed || SCIPvarGetStatus(consdata->intvar) == SCIP_VARSTATUS_FIXED);
3585 
3586  if( infeasible )
3587  {
3588  *cutoff = infeasible;
3589  return SCIP_OKAY;
3590  }
3591  else if( fixed )
3592  ++(*nfixedvars);
3593  }
3594 
3595  /* delete old redundant xor-constraint */
3596  SCIP_CALL( SCIPdelCons(scip, cons) );
3597  ++(*ndelconss);
3598  }
3599 
3600  return SCIP_OKAY;
3601 }
3602 
3603 /** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
3604  * accordingly; in contrast to preprocessConstraintPairs(), it uses a hash table
3605  */
3606 static
3608  SCIP* scip, /**< SCIP data structure */
3609  BMS_BLKMEM* blkmem, /**< block memory */
3610  SCIP_CONS** conss, /**< constraint set */
3611  int nconss, /**< number of constraints in constraint set */
3612  int* firstchange, /**< pointer to store first changed constraint */
3613  int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
3614  int* naggrvars, /**< pointer to add up the number of aggregated variables */
3615  int* ndelconss, /**< pointer to count number of deleted constraints */
3616  int* naddconss, /**< pointer to count number of added constraints */
3617  SCIP_Bool* cutoff /**< pointer to store TRUE, if a cutoff was found */
3618  )
3619 {
3620  SCIP_HASHTABLE* hashtable;
3621  int hashtablesize;
3622  int c;
3623 
3624  assert(conss != NULL);
3625  assert(ndelconss != NULL);
3626 
3627  /* create a hash table for the constraint set */
3628  hashtablesize = nconss;
3629  hashtablesize = MAX(hashtablesize, HASHSIZE_XORCONS);
3630 
3631  SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
3632  hashGetKeyXorcons, hashKeyEqXorcons, hashKeyValXorcons, (void*) scip) );
3633 
3634  /* check all constraints in the given set for redundancy */
3635  for( c = 0; c < nconss; ++c )
3636  {
3637  SCIP_CONS* cons0;
3638  SCIP_CONS* cons1;
3639  SCIP_CONSDATA* consdata0;
3640  SCIP_CONSHDLR* conshdlr;
3641  SCIP_CONSHDLRDATA* conshdlrdata;
3642 
3643  cons0 = conss[c];
3644 
3645  if( !SCIPconsIsActive(cons0) || SCIPconsIsModifiable(cons0) )
3646  continue;
3647 
3648  /* get constraint handler data */
3649  conshdlr = SCIPconsGetHdlr(cons0);
3650  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3651  assert(conshdlrdata != NULL);
3652 
3653  /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3654  * variables inside so we need to remove them for sorting
3655  */
3656  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3657  * merge multiple entries of the same or negated variables
3658  */
3659  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3660  if( *cutoff )
3661  goto TERMINATE;
3662 
3663  consdata0 = SCIPconsGetData(cons0);
3664 
3665  assert(consdata0 != NULL);
3666 
3667  /* sort the constraint */
3668  consdataSort(consdata0);
3669  assert(consdata0->sorted);
3670 
3671  /* get constraint from current hash table with same variables as cons0 */
3672  cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
3673 
3674  if( cons1 != NULL )
3675  {
3676  SCIP_CONSDATA* consdata1;
3677 
3678  assert(SCIPconsIsActive(cons1));
3679  assert(!SCIPconsIsModifiable(cons1));
3680 
3681  consdata1 = SCIPconsGetData(cons1);
3682 
3683  assert(consdata1 != NULL);
3684  assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
3685 
3686  assert(consdata0->sorted && consdata1->sorted);
3687  assert(consdata0->vars[0] == consdata1->vars[0]);
3688 
3689  if( consdata0->rhs != consdata1->rhs )
3690  {
3691  *cutoff = TRUE;
3692  goto TERMINATE;
3693  }
3694 
3695  /* delete cons0 and update flags of cons1 s.t. nonredundant information doesn't get lost */
3696  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
3697  SCIP_CALL( SCIPdelCons(scip, cons0) );
3698  (*ndelconss)++;
3699 
3700  /* update the first changed constraint to begin the next aggregation round with */
3701  if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
3702  *firstchange = SCIPconsGetPos(cons1);
3703 
3704  assert(SCIPconsIsActive(cons1));
3705  }
3706  else
3707  {
3708  /* no such constraint in current hash table: insert cons0 into hash table */
3709  SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
3710  }
3711  }
3712 
3713  TERMINATE:
3714  /* free hash table */
3715  SCIPhashtableFree(&hashtable);
3716 
3717  return SCIP_OKAY;
3718 }
3719 
3720 /** compares constraint with all prior constraints for possible redundancy or aggregation,
3721  * and removes or changes constraint accordingly
3722  */
3723 static
3725  SCIP* scip, /**< SCIP data structure */
3726  SCIP_CONS** conss, /**< constraint set */
3727  int firstchange, /**< first constraint that changed since last pair preprocessing round */
3728  int chkind, /**< index of constraint to check against all prior indices upto startind */
3729  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3730  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3731  int* naggrvars, /**< pointer to count number of aggregated variables */
3732  int* ndelconss, /**< pointer to count number of deleted constraints */
3733  int* naddconss, /**< pointer to count number of added constraints */
3734  int* nchgcoefs /**< pointer to add up the number of changed coefficients */
3735  )
3736 {
3737  SCIP_CONSHDLR* conshdlr;
3738  SCIP_CONSHDLRDATA* conshdlrdata;
3739  SCIP_CONS* cons0;
3740  SCIP_CONSDATA* consdata0;
3741  SCIP_Bool cons0changed;
3742  int c;
3743 
3744  assert(conss != NULL);
3745  assert(firstchange <= chkind);
3746  assert(cutoff != NULL);
3747  assert(nfixedvars != NULL);
3748  assert(naggrvars != NULL);
3749  assert(ndelconss != NULL);
3750  assert(nchgcoefs != NULL);
3751 
3752  /* get the constraint to be checked against all prior constraints */
3753  cons0 = conss[chkind];
3754  assert(SCIPconsIsActive(cons0));
3755  assert(!SCIPconsIsModifiable(cons0));
3756 
3757  consdata0 = SCIPconsGetData(cons0);
3758  assert(consdata0 != NULL);
3759  assert(consdata0->nvars >= 1);
3760 
3761  /* get constraint handler data */
3762  conshdlr = SCIPconsGetHdlr(cons0);
3763  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3764  assert(conshdlrdata != NULL);
3765 
3766  /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3767  * variables inside so we need to remove them for sorting
3768  */
3769  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3770  * merge multiple entries of the same or negated variables
3771  */
3772  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3773  if( *cutoff )
3774  return SCIP_OKAY;
3775 
3776  /* sort cons0 */
3777  consdataSort(consdata0);
3778  assert(consdata0->sorted);
3779 
3780  /* check constraint against all prior constraints */
3781  cons0changed = consdata0->changed;
3782  consdata0->changed = FALSE;
3783  for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff) && SCIPconsIsActive(cons0) && !SCIPisStopped(scip); ++c )
3784  {
3785  SCIP_CONS* cons1;
3786  SCIP_CONSDATA* consdata1;
3787  SCIP_VAR* singlevar0;
3788  SCIP_VAR* singlevar1;
3789  SCIP_Bool parity;
3790  SCIP_Bool cons0hastwoothervars;
3791  SCIP_Bool cons1hastwoothervars;
3792  SCIP_Bool aborted;
3793  SCIP_Bool infeasible;
3794  SCIP_Bool fixed;
3795  SCIP_Bool redundant;
3796  SCIP_Bool aggregated;
3797  int v0;
3798  int v1;
3799 
3800  cons1 = conss[c];
3801 
3802  /* ignore inactive and modifiable constraints */
3803  if( !SCIPconsIsActive(cons1) || SCIPconsIsModifiable(cons1) )
3804  continue;
3805 
3806  consdata1 = SCIPconsGetData(cons1);
3807  assert(consdata1 != NULL);
3808 
3809  if( !consdata1->deleteintvar )
3810  continue;
3811 
3812  /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3813  * variables inside so we need to remove them for sorting
3814  */
3815  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3816  * merge multiple entries of the same or negated variables
3817  */
3818  SCIP_CALL( applyFixings(scip, cons1, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3819  assert(consdata1 == SCIPconsGetData(cons1));
3820  if( *cutoff )
3821  return SCIP_OKAY;
3822 
3823  SCIPdebugMsg(scip, "preprocess xor constraint pair <%s>[chg:%u] and <%s>[chg:%u]\n",
3824  SCIPconsGetName(cons0), cons0changed, SCIPconsGetName(cons1), consdata1->changed);
3825 
3826  /* if both constraints were not changed since last round, we can ignore the pair */
3827  if( !cons0changed && !consdata1->changed )
3828  continue;
3829 
3830  /* applyFixings() led to an empty constraint */
3831  if( consdata1->nvars == 0 )
3832  {
3833  if( consdata1->rhs )
3834  {
3835  *cutoff = TRUE;
3836  break;
3837  }
3838  else
3839  {
3840  /* delete empty constraint */
3841  SCIP_CALL( SCIPdelCons(scip, cons1) );
3842  ++(*ndelconss);
3843 
3844  continue;
3845  }
3846  }
3847  else if( consdata1->nvars == 1 )
3848  {
3849  /* fix remaining variable */
3850  SCIP_CALL( SCIPfixVar(scip, consdata1->vars[0], (SCIP_Real) consdata1->rhs, &infeasible, &fixed) );
3851  assert(!infeasible);
3852 
3853  if( fixed )
3854  ++(*nfixedvars);
3855 
3856  SCIP_CALL( SCIPdelCons(scip, cons1) );
3857  ++(*ndelconss);
3858 
3859  /* check for fixed variable in cons0 and remove it */
3860  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3861  assert(!(*cutoff));
3862 
3863  /* sort cons0 */
3864  consdataSort(consdata0);
3865  assert(consdata0->sorted);
3866 
3867  continue;
3868  }
3869  else if( consdata1->nvars == 2 )
3870  {
3871  if( !(consdata1->rhs) )
3872  {
3873  /* aggregate var0 == var1 */
3874  SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->vars[1], 1.0, -1.0, 0.0,
3875  &infeasible, &redundant, &aggregated) );
3876  }
3877  else
3878  {
3879  /* aggregate var0 == 1 - var1 */
3880  SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->vars[1], 1.0, 1.0, 1.0,
3881  &infeasible, &redundant, &aggregated) );
3882  }
3883  assert(!infeasible);
3884  assert(redundant || SCIPdoNotAggr(scip));
3885 
3886  if( aggregated )
3887  {
3888  ++(*naggrvars);
3889 
3890  /* check for aggregated variable in cons0 and remove it */
3891  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3892  if( *cutoff )
3893  return SCIP_OKAY;
3894 
3895  /* sort cons0 */
3896  consdataSort(consdata0);
3897  assert(consdata0->sorted);
3898  }
3899 
3900  if( redundant )
3901  {
3902  SCIP_CALL( SCIPdelCons(scip, cons1) );
3903  ++(*ndelconss);
3904  }
3905 
3906  continue;
3907  }
3908  assert(consdata0->sorted);
3909 
3910  /* sort cons1 */
3911  consdataSort(consdata1);
3912  assert(consdata1->sorted);
3913 
3914  /* check whether
3915  * (a) one problem variable set is a subset of the other, or
3916  * (b) the problem variable sets are almost equal with only one variable in each constraint that is not
3917  * member of the other
3918  */
3919  aborted = FALSE;
3920  parity = (consdata0->rhs ^ consdata1->rhs);
3921  cons0hastwoothervars = FALSE;
3922  cons1hastwoothervars = FALSE;
3923  singlevar0 = NULL;
3924  singlevar1 = NULL;
3925  v0 = 0;
3926  v1 = 0;
3927  while( (v0 < consdata0->nvars || v1 < consdata1->nvars) && !aborted )
3928  {
3929  int cmp;
3930 
3931  assert(v0 <= consdata0->nvars);
3932  assert(v1 <= consdata1->nvars);
3933 
3934  if( v0 == consdata0->nvars )
3935  cmp = +1;
3936  else if( v1 == consdata1->nvars )
3937  cmp = -1;
3938  else
3939  cmp = SCIPvarCompareActiveAndNegated(consdata0->vars[v0], consdata1->vars[v1]);
3940 
3941  switch( cmp )
3942  {
3943  case -1:
3944  /* variable doesn't appear in cons1 */
3945  assert(v0 < consdata0->nvars);
3946  if( singlevar0 == NULL )
3947  {
3948  singlevar0 = consdata0->vars[v0];
3949  if( cons1hastwoothervars )
3950  aborted = TRUE;
3951  }
3952  else
3953  {
3954  cons0hastwoothervars = TRUE;
3955  if( singlevar1 != NULL )
3956  aborted = TRUE;
3957  }
3958  v0++;
3959  break;
3960 
3961  case +1:
3962  /* variable doesn't appear in cons0 */
3963  assert(v1 < consdata1->nvars);
3964  if( singlevar1 == NULL )
3965  {
3966  singlevar1 = consdata1->vars[v1];
3967  if( cons0hastwoothervars )
3968  aborted = TRUE;
3969  }
3970  else
3971  {
3972  cons1hastwoothervars = TRUE;
3973  if( singlevar0 != NULL )
3974  aborted = TRUE;
3975  }
3976  v1++;
3977  break;
3978 
3979  case 0:
3980  /* variable appears in both constraints */
3981  assert(v0 < consdata0->nvars);
3982  assert(v1 < consdata1->nvars);
3983  assert(SCIPvarGetProbvar(consdata0->vars[v0]) == SCIPvarGetProbvar(consdata1->vars[v1]));
3984  if( consdata0->vars[v0] != consdata1->vars[v1] )
3985  {
3986  assert(SCIPvarGetNegatedVar(consdata0->vars[v0]) == consdata1->vars[v1]);
3987  parity = !parity;
3988  }
3989  v0++;
3990  v1++;
3991  break;
3992 
3993  default:
3994  SCIPerrorMessage("invalid comparison result\n");
3995  SCIPABORT();
3996  return SCIP_INVALIDDATA; /*lint !e527*/
3997  }
3998  }
3999 
4000  /* check if a useful presolving is possible */
4001  if( (cons0hastwoothervars && singlevar1 != NULL) || (cons1hastwoothervars && singlevar0 != NULL) )
4002  continue;
4003 
4004  /* check if one problem variable set is a subset of the other */
4005  if( singlevar0 == NULL && singlevar1 == NULL )
4006  {
4007  /* both constraints are equal */
4008  if( !parity )
4009  {
4010  /* even parity: constraints are redundant */
4011  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> are redundant: delete <%s>\n",
4012  SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPconsGetName(cons1));
4013  SCIPdebugPrintCons(scip, cons0, NULL);
4014  SCIPdebugPrintCons(scip, cons1, NULL);
4015 
4016  /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4017  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4018  SCIP_CALL( SCIPdelCons(scip, cons1) );
4019  (*ndelconss)++;
4020 
4021  if( consdata1->intvar != NULL )
4022  {
4023  /* need to update integer variable, consider the following case:
4024  * c1: xor(x1, x2, x3) = 1 (intvar1 = y1)
4025  * c2: xor(x1, x2, x3) = 1 (intvar0 = NULL or intvar0 = y0)
4026  *
4027  * if intvar0 = NULL we have to assign intvar0 = y1. otherwise, we have to ensure that y1 = y0 holds.
4028  * if aggregation is allowed, we can aggregate both variables. otherwise, we have to add a linear
4029  * constraint y1 - y0 = 0.
4030  */
4031  if( consdata0->intvar == NULL )
4032  {
4033  SCIP_CALL( setIntvar(scip, cons0, consdata1->intvar) );
4034  }
4035  else
4036  {
4037  /* aggregate integer variables */
4038  SCIP_CALL( SCIPaggregateVars(scip, consdata1->intvar, consdata0->intvar, 1.0, -1.0, 0.0,
4039  &infeasible, &redundant, &aggregated) );
4040 
4041  *cutoff = *cutoff || infeasible;
4042 
4043  if( aggregated )
4044  {
4045  (*naggrvars)++;
4046  assert(SCIPvarIsActive(consdata0->intvar));
4047  }
4048  else
4049  {
4050  SCIP_CONS* newcons;
4051  char consname[SCIP_MAXSTRLEN];
4052  SCIP_VAR* newvars[2];
4053  SCIP_Real vals[2];
4054 
4055  newvars[0] = consdata1->intvar;
4056  vals[0] = 1.0;
4057  newvars[1] = consdata0->intvar;
4058  vals[1] = -1.0;
4059 
4060  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons1));
4061 
4062  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, newvars, vals, 0.0, 0.0,
4063  SCIPconsIsInitial(cons1), SCIPconsIsSeparated(cons1), TRUE, /*SCIPconsIsEnforced(cons),*/
4064  TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
4065  SCIPconsIsLocal(cons1), SCIPconsIsModifiable(cons1),
4067 
4068  SCIP_CALL( SCIPaddCons(scip, newcons) );
4069  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4070  ++(*naddconss);
4071  }
4072  }
4073  }
4074  }
4075  else
4076  {
4077  /* odd parity: constraints are contradicting */
4078  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> are contradicting\n",
4079  SCIPconsGetName(cons0), SCIPconsGetName(cons1));
4080  SCIPdebugPrintCons(scip, cons0, NULL);
4081  SCIPdebugPrintCons(scip, cons1, NULL);
4082  *cutoff = TRUE;
4083  }
4084  }
4085  else if( singlevar1 == NULL )
4086  {
4087  /* cons1 is a subset of cons0 */
4088  if( !cons0hastwoothervars )
4089  {
4090  /* only one additional variable in cons0: fix this variable according to the parity */
4091  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == <%s>\n",
4092  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity, SCIPvarGetName(singlevar0));
4093  SCIPdebugPrintCons(scip, cons0, NULL);
4094  SCIPdebugPrintCons(scip, cons1, NULL);
4095  SCIP_CALL( SCIPfixVar(scip, singlevar0, parity ? 1.0 : 0.0, &infeasible, &fixed) );
4096  *cutoff = *cutoff || infeasible;
4097  if ( fixed )
4098  (*nfixedvars)++;
4099 
4100  /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4101  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4102  SCIP_CALL( SCIPdelCons(scip, cons1) );
4103  (*ndelconss)++;
4104  }
4105  else
4106  {
4107  int v;
4108 
4109  /* more than one additional variable in cons0: add cons1 to cons0, thus eliminating the equal variables */
4110  SCIPdebugMsg(scip, "xor constraint <%s> is superset of <%s> with parity %u\n",
4111  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity);
4112  SCIPdebugPrintCons(scip, cons0, NULL);
4113  SCIPdebugPrintCons(scip, cons1, NULL);
4114  for( v = 0; v < consdata1->nvars; ++v )
4115  {
4116  SCIP_CALL( addCoef(scip, cons0, consdata1->vars[v]) );
4117  }
4118 
4119  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4120  assert(SCIPconsGetData(cons0) == consdata0);
4121  assert(consdata0->nvars >= 2); /* at least the two "other" variables should remain in the constraint */
4122  }
4123 
4124  if( *cutoff )
4125  return SCIP_OKAY;
4126 
4127  consdataSort(consdata0);
4128  assert(consdata0->sorted);
4129  }
4130  else if( singlevar0 == NULL )
4131  {
4132  /* cons0 is a subset of cons1 */
4133  if( !cons1hastwoothervars )
4134  {
4135  /* only one additional variable in cons1: fix this variable according to the parity */
4136  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == <%s>\n",
4137  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity, SCIPvarGetName(singlevar1));
4138  SCIPdebugPrintCons(scip, cons0, NULL);
4139  SCIPdebugPrintCons(scip, cons1, NULL);
4140  SCIP_CALL( SCIPfixVar(scip, singlevar1, parity ? 1.0 : 0.0, &infeasible, &fixed) );
4141  assert(infeasible || fixed);
4142  *cutoff = *cutoff || infeasible;
4143  (*nfixedvars)++;
4144 
4145  /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4146  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4147  SCIP_CALL( SCIPdelCons(scip, cons1) );
4148  (*ndelconss)++;
4149  }
4150  else
4151  {
4152  int v;
4153 
4154  /* more than one additional variable in cons1: add cons0 to cons1, thus eliminating the equal variables */
4155  SCIPdebugMsg(scip, "xor constraint <%s> is subset of <%s> with parity %u\n",
4156  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity);
4157  SCIPdebugPrintCons(scip, cons0, NULL);
4158  SCIPdebugPrintCons(scip, cons1, NULL);
4159  for( v = 0; v < consdata0->nvars; ++v )
4160  {
4161  SCIP_CALL( addCoef(scip, cons1, consdata0->vars[v]) );
4162  }
4163  SCIP_CALL( applyFixings(scip, cons1, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4164  assert(SCIPconsGetData(cons1) == consdata1);
4165  assert(consdata1->nvars >= 2); /* at least the two "other" variables should remain in the constraint */
4166 
4167  if( *cutoff )
4168  return SCIP_OKAY;
4169 
4170  consdataSort(consdata1);
4171  assert(consdata1->sorted);
4172  }
4173  }
4174  else
4175  {
4176  assert(!cons0hastwoothervars);
4177  assert(!cons1hastwoothervars);
4178 
4179  /* sum of constraints is parity == singlevar0 xor singlevar1: aggregate variables and delete cons1 */
4180  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == xor(<%s>,<%s>)\n",
4181  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity, SCIPvarGetName(singlevar0),
4182  SCIPvarGetName(singlevar1));
4183  if( !parity )
4184  {
4185  /* aggregate singlevar0 == singlevar1 */
4186  SCIP_CALL( SCIPaggregateVars(scip, singlevar1, singlevar0, 1.0, -1.0, 0.0,
4187  &infeasible, &redundant, &aggregated) );
4188  }
4189  else
4190  {
4191  /* aggregate singlevar0 == 1-singlevar1 */
4192  SCIP_CALL( SCIPaggregateVars(scip, singlevar1, singlevar0, 1.0, 1.0, 1.0,
4193  &infeasible, &redundant, &aggregated) );
4194  }
4195  assert(infeasible || redundant || SCIPdoNotAggr(scip));
4196 
4197  *cutoff = *cutoff || infeasible;
4198  if( aggregated )
4199  (*naggrvars)++;
4200 
4201  if( redundant )
4202  {
4203  /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4204  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4205  SCIP_CALL( SCIPdelCons(scip, cons1) );
4206  (*ndelconss)++;
4207 
4208  if( consdata1->intvar != NULL )
4209  {
4210  if( consdata0->intvar == NULL )
4211  {
4212  SCIP_CALL( setIntvar(scip, cons0, consdata0->intvar) );
4213  }
4214  else
4215  {
4216  /* aggregate integer variables */
4217  SCIP_CALL( SCIPaggregateVars(scip, consdata1->intvar, consdata0->intvar, 1.0, -1.0, 0.0,
4218  &infeasible, &redundant, &aggregated) );
4219 
4220  *cutoff = *cutoff || infeasible;
4221  if( aggregated )
4222  (*naggrvars)++;
4223  }
4224  }
4225  }
4226 
4227  if( !consdata0->sorted )
4228  consdataSort(consdata0);
4229  assert(consdata0->sorted);
4230 
4231 #if 0
4232  /* if aggregation in the core of SCIP is not changed we do not need to call applyFixing, this would be the correct
4233  * way
4234  */
4235  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
4236  * merge multiple entries of the same or negated variables
4237  */
4238  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4239 
4240  if( *cutoff )
4241  return SCIP_OKAY;
4242 #endif
4243 
4244  }
4245  }
4246 
4247  return SCIP_OKAY;
4248 }
4249 
4250 /** creates and captures a xor constraint x_0 xor ... xor x_{k-1} = rhs with a given artificial integer variable for the
4251  * linear relaxation
4252  *
4253  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
4254  */
4255 static
4257  SCIP* scip, /**< SCIP data structure */
4258  SCIP_CONS** cons, /**< pointer to hold the created constraint */
4259  const char* name, /**< name of constraint */
4260  SCIP_Bool rhs, /**< right hand side of the constraint */
4261  int nvars, /**< number of operator variables in the constraint */
4262  SCIP_VAR** vars, /**< array with operator variables of constraint */
4263  SCIP_VAR* intvar, /**< artificial integer variable for linear relaxation */
4264  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
4265  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
4266  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
4267  * Usually set to TRUE. */
4268  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
4269  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4270  SCIP_Bool check, /**< should the constraint be checked for feasibility?
4271  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4272  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
4273  * Usually set to TRUE. */
4274  SCIP_Bool local, /**< is constraint only valid locally?
4275  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
4276  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
4277  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
4278  * adds coefficients to this constraint. */
4279  SCIP_Bool dynamic, /**< is constraint subject to aging?
4280  * Usually set to FALSE. Set to TRUE for own cuts which
4281  * are separated as constraints. */
4282  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
4283  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
4284  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
4285  * if it may be moved to a more global node?
4286  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
4287  )
4288 {
4289  SCIP_CONSHDLR* conshdlr;
4290  SCIP_CONSDATA* consdata;
4291 
4292  /* find the xor constraint handler */
4293  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
4294  if( conshdlr == NULL )
4295  {
4296  SCIPerrorMessage("xor constraint handler not found\n");
4297  return SCIP_PLUGINNOTFOUND;
4298  }
4299 
4300  /* create constraint data */
4301  SCIP_CALL( consdataCreate(scip, &consdata, rhs, nvars, vars, intvar) );
4302 
4303  /* create constraint */
4304  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
4305  local, modifiable, dynamic, removable, stickingatnode) );
4306 
4307  return SCIP_OKAY;
4308 }
4309 
4310 
4311 
4312 /*
4313  * Linear constraint upgrading
4314  */
4315 
4316 /** tries to upgrade a linear constraint into an xor constraint
4317  *
4318  * Assuming the only coefficients with an absolute value unequal to one is two in absolute value we can transform:
4319  * \f[
4320  * \begin{array}{ll}
4321  * & -\sum_{i \in I} x_i + \sum_{j \in J} x_j + a \cdot z = rhs \\
4322  * \Leftrightarrow & \sum_{i \in I} ~x_i + \sum_j x_{j \in J} + a \cdot z = rhs + |I| \\
4323  * \Leftrightarrow & \sum_{i \in I} ~x_i + \sum_j x_{j \in J} - 2 \cdot y = (rhs + |I|) mod 2 \\
4324  * & z \in [lb_z,ub_z] \Rightarrow y \in (\left\lfloor \frac{rhs + |I|}{2} \right\rfloor + (a = -2\; ?\; lb_z : -ub_z), \left\lfloor \frac{rhs + |I|}{2} \right\rfloor + (a = -2\; ?\; ub_z : -lb_z) ) \\
4325  * & z = (a = -2\; ?\; y - \left\lfloor \frac{rhs + |I|}{2} \right\rfloor\; :\; -y + \left\lfloor \frac{rhs + |I|}{2} \right\rfloor)
4326  * \end{array}
4327  * \f]
4328  */
4329 static
4330 SCIP_DECL_LINCONSUPGD(linconsUpgdXor)
4331 { /*lint --e{715}*/
4332  assert( upgdcons != NULL );
4333  assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0 );
4334  assert( ! SCIPconsIsModifiable(cons) );
4335 
4336  /* check, if linear constraint can be upgraded to xor constraint */
4337  /* @todo also applicable if the integer variable has a coefficient different from 2, e.g. a coefficient like 0.5 then
4338  * we could generate a new integer variable aggregated to the old one, possibly the constraint was then
4339  * normalized and all binary variables have coefficients of 2.0, if the coefficient is 4 then we need holes ...
4340  */
4341  if( integral && nposcont + nnegcont == 0 && nposbin + nnegbin + nposimplbin + nnegimplbin >= nvars-1 && ncoeffspone + ncoeffsnone == nvars-1 && ncoeffspint + ncoeffsnint == 1 )
4342  {
4343  assert( ncoeffspfrac + ncoeffsnfrac == 0 );
4344 
4345  if ( SCIPisEQ(scip, lhs, rhs) && SCIPisIntegral(scip, lhs) )
4346  {
4347  SCIP_VAR** xorvars;
4348  SCIP_VAR* parityvar = NULL;
4349  SCIP_Bool postwo = FALSE;
4350  int cnt = 0;
4351  int j;
4352 
4353  SCIP_CALL( SCIPallocBufferArray(scip, &xorvars, nvars) );
4354 
4355  /* check parity of constraints */
4356  for( j = nvars - 1; j >= 0; --j )
4357  {
4358  if( SCIPisEQ(scip, REALABS(vals[j]), 2.0) )
4359  {
4360  parityvar = vars[j];
4361  postwo = (vals[j] > 0.0);
4362  }
4363  else if( !SCIPisEQ(scip, REALABS(vals[j]), 1.0) )
4364  break;
4365  else
4366  {
4367  /* exit if variable is not binary or implicit binary */
4368  if ( ! SCIPvarIsBinary(vars[j]) )
4369  {
4370  parityvar = NULL;
4371  break;
4372  }
4373 
4374  /* need negated variables for correct propagation to the integer variable */
4375  if( vals[j] < 0.0 )
4376  {
4377  SCIP_CALL( SCIPgetNegatedVar(scip, vars[j], &(xorvars[cnt])) );
4378  assert(xorvars[cnt] != NULL);
4379  }
4380  else
4381  xorvars[cnt] = vars[j];
4382  ++cnt;
4383  }
4384  }
4385 
4386  if( parityvar != NULL )
4387  {
4388  assert(cnt == nvars - 1);
4389 
4390  /* check whether parity variable is present only in this constraint */
4391  if ( SCIPvarGetNLocksDown(parityvar) <= 1 && SCIPvarGetNLocksUp(parityvar) <= 1 )
4392  {
4393  SCIP_VAR* intvar;
4394  SCIP_Bool rhsparity;
4395  SCIP_Bool neednew;
4396  int intrhs;
4397 
4398  SCIPdebugMsg(scip, "upgrading constraint <%s> to an XOR constraint\n", SCIPconsGetName(cons));
4399 
4400  /* adjust the side, since we negated all binary variables with -1.0 as a coefficient */
4401  rhs += ncoeffsnone;
4402 
4403  intrhs = (int) SCIPfloor(scip, rhs);
4404  rhsparity = ((SCIP_Bool) (intrhs % 2)); /*lint !e571*/
4405  neednew = (intrhs != 1 && intrhs != 0);
4406 
4407  /* check if we can use the parity variable as integer variable of the XOR constraint or do we need to
4408  * create a new variable
4409  */
4410  if( neednew )
4411  {
4412  char varname[SCIP_MAXSTRLEN];
4413  SCIP_Real lb;
4414  SCIP_Real ub;
4415  SCIP_Bool isbinary;
4416  SCIP_Bool infeasible;
4417  SCIP_Bool redundant;
4418  SCIP_Bool aggregated;
4419  int intrhshalfed;
4420 
4421  intrhshalfed = intrhs / 2;
4422 
4423  if( postwo )
4424  {
4425  lb = intrhshalfed - SCIPvarGetUbGlobal(parityvar);
4426  ub = intrhshalfed - SCIPvarGetLbGlobal(parityvar);
4427  }
4428  else
4429  {
4430  lb = intrhshalfed + SCIPvarGetLbGlobal(parityvar);
4431  ub = intrhshalfed + SCIPvarGetUbGlobal(parityvar);
4432  }
4433  assert(SCIPisFeasLE(scip, lb, ub));
4434  assert(SCIPisFeasIntegral(scip, lb));
4435  assert(SCIPisFeasIntegral(scip, ub));
4436 
4437  /* adjust bounds to be more integral */
4438  lb = SCIPfeasFloor(scip, lb);
4439  ub = SCIPfeasFloor(scip, ub);
4440 
4441  isbinary = (SCIPisZero(scip, lb) && SCIPisEQ(scip, ub, 1.0));
4442 
4443  /* you must not create an artificial integer variable if parity variable is already binary */
4444  if( SCIPvarIsBinary(parityvar) && !isbinary )
4445  {
4446  SCIPfreeBufferArray(scip, &xorvars);
4447  return SCIP_OKAY;
4448  }
4449 
4450  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_xor_upgr", SCIPvarGetName(parityvar));
4451  SCIP_CALL( SCIPcreateVar(scip, &intvar, varname, lb, ub, 0.0,
4453  SCIPvarIsInitial(parityvar), SCIPvarIsRemovable(parityvar), NULL, NULL, NULL, NULL, NULL) );
4454  SCIP_CALL( SCIPaddVar(scip, intvar) );
4455 
4456  SCIPdebugMsg(scip, "created new variable for aggregation:");
4457  SCIPdebug( SCIPprintVar(scip, intvar, NULL) );
4458 
4459  SCIP_CALL( SCIPaggregateVars(scip, parityvar, intvar, 1.0, postwo ? 1.0 : -1.0,
4460  (SCIP_Real) (postwo ? intrhshalfed : -intrhshalfed), &infeasible, &redundant, &aggregated) );
4461  assert(!infeasible);
4462 
4463  /* maybe aggregation was forbidden, than we cannot upgrade this constraint */
4464  if( !aggregated )
4465  {
4466  SCIPfreeBufferArray(scip, &xorvars);
4467  return SCIP_OKAY;
4468  }
4469 
4470  assert(redundant);
4471  assert(SCIPvarIsActive(intvar));
4472 
4473  SCIPdebugMsg(scip, "aggregated: %s = %g * %s + %g\n", SCIPvarGetName(parityvar),
4474  SCIPvarGetAggrScalar(parityvar), SCIPvarGetName(SCIPvarGetAggrVar(parityvar)),
4475  SCIPvarGetAggrConstant(parityvar));
4476  }
4477  else
4478  intvar = parityvar;
4479 
4480  assert(intvar != NULL);
4481 
4482  SCIPdebugMsg(scip, "upgrading constraint <%s> to XOR constraint\n", SCIPconsGetName(cons));
4483 
4484  SCIP_CALL( createConsXorIntvar(scip, upgdcons, SCIPconsGetName(cons), rhsparity, nvars - 1, xorvars, intvar,
4489 
4490  SCIPdebugPrintCons(scip, *upgdcons, NULL);
4491 
4492  if( neednew )
4493  {
4494  assert(intvar != parityvar);
4495  SCIP_CALL( SCIPreleaseVar(scip, &intvar) );
4496  }
4497  }
4498  }
4499 
4500  SCIPfreeBufferArray(scip, &xorvars);
4501  }
4502  }
4503 
4504  return SCIP_OKAY;
4505 }
4506 
4507 
4508 /*
4509  * Callback methods of constraint handler
4510  */
4511 
4512 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
4513 static
4514 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyXor)
4515 { /*lint --e{715}*/
4516  assert(scip != NULL);
4517  assert(conshdlr != NULL);
4518  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4519 
4520  /* call inclusion method of constraint handler */
4522 
4523  *valid = TRUE;
4524 
4525  return SCIP_OKAY;
4526 }
4527 
4528 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
4529 static
4530 SCIP_DECL_CONSFREE(consFreeXor)
4531 { /*lint --e{715}*/
4532  SCIP_CONSHDLRDATA* conshdlrdata;
4533 
4534  /* free constraint handler data */
4535  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4536  assert(conshdlrdata != NULL);
4537 
4538  SCIP_CALL( conshdlrdataFree(scip, &conshdlrdata) );
4539 
4540  SCIPconshdlrSetData(conshdlr, NULL);
4541 
4542  return SCIP_OKAY;
4543 }
4544 
4545 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4546 static
4547 SCIP_DECL_CONSEXITSOL(consExitsolXor)
4548 { /*lint --e{715}*/
4549  SCIP_CONSDATA* consdata;
4550  int c;
4551 
4552  /* release and free the rows of all constraints */
4553  for( c = 0; c < nconss; ++c )
4554  {
4555  consdata = SCIPconsGetData(conss[c]);
4556  SCIP_CALL( consdataFreeRows(scip, consdata) );
4557  }
4558 
4559  return SCIP_OKAY;
4560 }
4561 
4562 
4563 /** frees specific constraint data */
4564 static
4565 SCIP_DECL_CONSDELETE(consDeleteXor)
4566 { /*lint --e{715}*/
4567  SCIP_CONSHDLRDATA* conshdlrdata;
4568 
4569  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4570  assert(conshdlrdata != NULL);
4571 
4573  {
4574  int v;
4575 
4576  for( v = (*consdata)->nvars - 1; v >= 0; --v )
4577  {
4578  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4579  (SCIP_EVENTDATA*)(*consdata), -1) );
4580  }
4581  }
4582 
4583  SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4584 
4585  return SCIP_OKAY;
4586 }
4587 
4588 
4589 /** transforms constraint data into data belonging to the transformed problem */
4590 static
4591 SCIP_DECL_CONSTRANS(consTransXor)
4592 { /*lint --e{715}*/
4593  SCIP_CONSDATA* sourcedata;
4594  SCIP_CONSDATA* targetdata;
4595 
4596  sourcedata = SCIPconsGetData(sourcecons);
4597  assert(sourcedata != NULL);
4598  assert(sourcedata->nvars >= 1);
4599  assert(sourcedata->vars != NULL);
4600 
4601  /* create target constraint data */
4602  SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->rhs, sourcedata->nvars, sourcedata->vars, sourcedata->intvar) );
4603 
4604  /* create target constraint */
4605  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4606  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4607  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4608  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4609  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4610 
4611  return SCIP_OKAY;
4612 }
4613 
4614 
4615 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4616 static
4617 SCIP_DECL_CONSINITLP(consInitlpXor)
4618 { /*lint --e{715}*/
4619  int i;
4620 
4621  assert(infeasible != NULL);
4622 
4623  *infeasible = FALSE;
4624 
4625  for( i = 0; i < nconss && !(*infeasible); i++ )
4626  {
4627  assert(SCIPconsIsInitial(conss[i]));
4628  SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4629  }
4630 
4631  return SCIP_OKAY;
4632 }
4633 
4634 
4635 /** separation method of constraint handler for LP solutions */
4636 static
4637 SCIP_DECL_CONSSEPALP(consSepalpXor)
4638 { /*lint --e{715}*/
4639  SCIP_CONSHDLRDATA* conshdlrdata;
4640  SCIP_Bool separated;
4641  SCIP_Bool cutoff;
4642  int c;
4643 
4644  *result = SCIP_DIDNOTFIND;
4645 
4646  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4647  assert( conshdlrdata != NULL );
4648 
4649  /* separate all useful constraints */
4650  for( c = 0; c < nusefulconss; ++c )
4651  {
4652  SCIP_CALL( separateCons(scip, conss[c], NULL, conshdlrdata->separateparity, &separated, &cutoff) );
4653  if ( cutoff )
4654  *result = SCIP_CUTOFF;
4655  else if ( separated )
4656  *result = SCIP_SEPARATED;
4657  }
4658 
4659  /* combine constraints to get more cuts */
4660  /**@todo combine constraints to get further cuts */
4661 
4662  return SCIP_OKAY;
4663 }
4664 
4665 
4666 /** separation method of constraint handler for arbitrary primal solutions */
4667 static
4668 SCIP_DECL_CONSSEPASOL(consSepasolXor)
4669 { /*lint --e{715}*/
4670  SCIP_CONSHDLRDATA* conshdlrdata;
4671  SCIP_Bool separated;
4672  SCIP_Bool cutoff;
4673  int c;
4674 
4675  *result = SCIP_DIDNOTFIND;
4676 
4677  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4678  assert( conshdlrdata != NULL );
4679 
4680  /* separate all useful constraints */
4681  for( c = 0; c < nusefulconss; ++c )
4682  {
4683  SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->separateparity, &separated, &cutoff) );
4684  if ( cutoff )
4685  *result = SCIP_CUTOFF;
4686  else if ( separated )
4687  *result = SCIP_SEPARATED;
4688  }
4689 
4690  /* combine constraints to get more cuts */
4691  /**@todo combine constraints to get further cuts */
4692 
4693  return SCIP_OKAY;
4694 }
4695 
4696 
4697 /** constraint enforcing method of constraint handler for LP solutions */
4698 static
4699 SCIP_DECL_CONSENFOLP(consEnfolpXor)
4700 { /*lint --e{715}*/
4701  SCIP_CONSHDLRDATA* conshdlrdata;
4702  SCIP_Bool violated;
4703  SCIP_Bool cutoff;
4704  int i;
4705 
4706  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4707  assert( conshdlrdata != NULL );
4708 
4709  /* method is called only for integral solutions, because the enforcing priority is negative */
4710  for( i = 0; i < nconss; i++ )
4711  {
4712  SCIP_CALL( checkCons(scip, conss[i], NULL, FALSE, &violated) );
4713  if( violated )
4714  {
4715  SCIP_Bool separated;
4716 
4717  SCIP_CALL( separateCons(scip, conss[i], NULL, conshdlrdata->separateparity, &separated, &cutoff) );
4718  if ( cutoff )
4719  *result = SCIP_CUTOFF;
4720  else
4721  {
4722  assert(separated); /* because the solution is integral, the separation always finds a cut */
4723  *result = SCIP_SEPARATED;
4724  }
4725  return SCIP_OKAY;
4726  }
4727  }
4728  *result = SCIP_FEASIBLE;
4729 
4730  return SCIP_OKAY;
4731 }
4732 
4733 
4734 /** constraint enforcing method of constraint handler for relaxation solutions */
4735 static
4736 SCIP_DECL_CONSENFORELAX(consEnforelaxXor)
4737 { /*lint --e{715}*/
4738  SCIP_CONSHDLRDATA* conshdlrdata;
4739  SCIP_Bool violated;
4740  SCIP_Bool cutoff;
4741  int i;
4742 
4743  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4744  assert( conshdlrdata != NULL );
4745 
4746  /* method is called only for integral solutions, because the enforcing priority is negative */
4747  for( i = 0; i < nconss; i++ )
4748  {
4749  SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, &violated) );
4750  if( violated )
4751  {
4752  SCIP_Bool separated;
4753 
4754  SCIP_CALL( separateCons(scip, conss[i], sol, conshdlrdata->separateparity, &separated, &cutoff) );
4755  if ( cutoff )
4756  *result = SCIP_CUTOFF;
4757  else
4758  {
4759  assert(separated); /* because the solution is integral, the separation always finds a cut */
4760  *result = SCIP_SEPARATED;
4761  }
4762  return SCIP_OKAY;
4763  }
4764  }
4765  *result = SCIP_FEASIBLE;
4766 
4767  return SCIP_OKAY;
4768 }
4769 
4770 
4771 /** constraint enforcing method of constraint handler for pseudo solutions */
4772 static
4773 SCIP_DECL_CONSENFOPS(consEnfopsXor)
4774 { /*lint --e{715}*/
4775  SCIP_Bool violated;
4776  int i;
4777 
4778  /* method is called only for integral solutions, because the enforcing priority is negative */
4779  for( i = 0; i < nconss; i++ )
4780  {
4781  SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, &violated) );
4782  if( violated )
4783  {
4784  *result = SCIP_INFEASIBLE;
4785  return SCIP_OKAY;
4786  }
4787  }
4788  *result = SCIP_FEASIBLE;
4789 
4790  return SCIP_OKAY;
4791 }
4792 
4793 
4794 /** feasibility check method of constraint handler for integral solutions */
4795 static
4796 SCIP_DECL_CONSCHECK(consCheckXor)
4797 { /*lint --e{715}*/
4798  SCIP_Bool violated;
4799  int i;
4800 
4801  *result = SCIP_FEASIBLE;
4802 
4803  /* method is called only for integral solutions, because the enforcing priority is negative */
4804  for( i = 0; i < nconss && (*result == SCIP_FEASIBLE || completely); i++ )
4805  {
4806  SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, &violated) );
4807  if( violated )
4808  {
4809  *result = SCIP_INFEASIBLE;
4810 
4811  if( printreason )
4812  {
4813  int v;
4814  int sum = 0;
4815  SCIP_CONSDATA* consdata;
4816 
4817  consdata = SCIPconsGetData(conss[i]);
4818  assert( consdata != NULL );
4819 
4820  SCIP_CALL( SCIPprintCons(scip, conss[i], NULL) );
4821 
4822  for( v = 0; v < consdata->nvars; ++v )
4823  {
4824  if( SCIPgetSolVal(scip, sol, consdata->vars[v]) > 0.5 )
4825  sum++;
4826  }
4827 
4828  if( consdata->intvar != NULL )
4829  {
4830  SCIPinfoMessage(scip, NULL, ";\nviolation: %d operands are set to TRUE but integer variable has value of %g\n", SCIPgetSolVal(scip, sol, consdata->intvar));
4831  }
4832  else
4833  {
4834  SCIPinfoMessage(scip, NULL, ";\nviolation: %d operands are set to TRUE\n", sum );
4835  }
4836  }
4837  }
4838  }
4839 
4840  return SCIP_OKAY;
4841 }
4842 
4843 
4844 /** domain propagation method of constraint handler */
4845 static
4846 SCIP_DECL_CONSPROP(consPropXor)
4847 { /*lint --e{715}*/
4848  SCIP_CONSHDLRDATA* conshdlrdata;
4849  SCIP_Bool cutoff;
4850  int nfixedvars;
4851  int nchgbds;
4852  int c;
4853 
4854  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4855  assert(conshdlrdata != NULL);
4856 
4857  cutoff = FALSE;
4858  nfixedvars = 0;
4859  nchgbds = 0;
4860 
4861  /* propagate all useful constraints */
4862  for( c = 0; c < nusefulconss && !cutoff; ++c )
4863  {
4864  SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars, &nchgbds) );
4865  }
4866 
4867  /* return the correct result */
4868  if( cutoff )
4869  *result = SCIP_CUTOFF;
4870  else if( nfixedvars > 0 || nchgbds > 0 )
4871  *result = SCIP_REDUCEDDOM;
4872  else
4873  {
4874  *result = SCIP_DIDNOTFIND;
4875  if ( ! SCIPinProbing(scip) )
4876  {
4877  int depth;
4878  int freq;
4879 
4880  depth = SCIPgetDepth(scip);
4881  freq = conshdlrdata->gausspropfreq;
4882  if ( (depth == 0 && freq == 0) || (freq > 0 && depth % freq == 0) )
4883  {
4884  /* take useful constraints only - might improve success rate to take all */
4885  SCIP_CALL( checkSystemGF2(scip, conss, nusefulconss, NULL, result) );
4886  }
4887  }
4888  }
4889 
4890  return SCIP_OKAY;
4891 }
4892 
4893 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
4894 static
4895 SCIP_DECL_CONSINITPRE(consInitpreXor)
4896 { /*lint --e{715}*/
4897  SCIP_CONSHDLRDATA* conshdlrdata;
4898  SCIP_CONSDATA* consdata;
4899  int c;
4900  int v;
4901 
4902  assert(conshdlr != NULL);
4903  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4904  assert(conshdlrdata != NULL);
4905 
4906  /* catch all variable event for deleted variables, which is only used in presolving */
4907  for( c = nconss - 1; c >= 0; --c )
4908  {
4909  consdata = SCIPconsGetData(conss[c]);
4910  assert(consdata != NULL);
4911 
4912  for( v = consdata->nvars - 1; v >= 0; --v )
4913  {
4914  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4915  (SCIP_EVENTDATA*)consdata, NULL) );
4916  }
4917  }
4918 
4919  return SCIP_OKAY;
4920 }
4921 
4922 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
4923 static
4924 SCIP_DECL_CONSEXITPRE(consExitpreXor)
4925 { /*lint --e{715}*/
4926  SCIP_CONSHDLRDATA* conshdlrdata;
4927  SCIP_CONSDATA* consdata;
4928  int c;
4929  int v;
4930 
4931  assert(conshdlr != NULL);
4932  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4933  assert(conshdlrdata != NULL);
4934 
4935  /* drop all variable event for deleted variables, which was only used in presolving */
4936  for( c = 0; c < nconss; ++c )
4937  {
4938  consdata = SCIPconsGetData(conss[c]);
4939  assert(consdata != NULL);
4940 
4941  if( !SCIPconsIsDeleted(conss[c]) )
4942  {
4943  for( v = 0; v < consdata->nvars; ++v )
4944  {
4945  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4946  (SCIP_EVENTDATA*)consdata, -1) );
4947  }
4948  }
4949  }
4950 
4951  return SCIP_OKAY;
4952 }
4953 
4954 /** presolving method of constraint handler */
4955 static
4956 SCIP_DECL_CONSPRESOL(consPresolXor)
4957 { /*lint --e{715}*/
4958  SCIP_CONSHDLRDATA* conshdlrdata;
4959  SCIP_CONS* cons;
4960  SCIP_CONSDATA* consdata;
4961  SCIP_Bool cutoff;
4962  SCIP_Bool redundant;
4963  SCIP_Bool aggregated;
4964  int oldnfixedvars;
4965  int oldnchgbds;
4966  int oldnaggrvars;
4967  int oldndelconss;
4968  int oldnchgcoefs;
4969  int firstchange;
4970  int c;
4971 
4972  assert(result != NULL);
4973 
4974  oldnfixedvars = *nfixedvars;
4975  oldnchgbds = *nchgbds;
4976  oldnaggrvars = *naggrvars;
4977  oldndelconss = *ndelconss;
4978  oldnchgcoefs = *nchgcoefs;
4979 
4980  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4981  assert(conshdlrdata != NULL);
4982 
4983  /* process constraints */
4984  cutoff = FALSE;
4985  firstchange = INT_MAX;
4986  for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4987  {
4988  cons = conss[c];
4989  assert(cons != NULL);
4990  consdata = SCIPconsGetData(cons);
4991  assert(consdata != NULL);
4992 
4993  /* force presolving the constraint in the initial round */
4994  if( nrounds == 0 )
4995  consdata->propagated = FALSE;
4996 
4997  /* remember the first changed constraint to begin the next aggregation round with */
4998  if( firstchange == INT_MAX && consdata->changed )
4999  firstchange = c;
5000 
5001  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
5002  * merge multiple entries of the same or negated variables
5003  */
5004  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, &cutoff) );
5005 
5006  if( cutoff )
5007  break;
5008 
5009  /* propagate constraint */
5010  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nchgbds) );
5011 
5012  if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
5013  {
5014  assert(consdata->nvars >= 2); /* otherwise, propagateCons() has deleted the constraint */
5015 
5016  /* if only two variables are left, both have to be equal or opposite, depending on the rhs */
5017  if( consdata->nvars == 2 )
5018  {
5019  SCIPdebugMsg(scip, "xor constraint <%s> has only two unfixed variables, rhs=%u\n",
5020  SCIPconsGetName(cons), consdata->rhs);
5021 
5022  assert(consdata->vars != NULL);
5023  assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
5024  assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
5025  assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->vars[1]), 0.0));
5026  assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(consdata->vars[1]), 1.0));
5027 
5028  if( !consdata->rhs )
5029  {
5030  /* aggregate variables: vars[0] - vars[1] == 0 */
5031  SCIPdebugMsg(scip, " -> aggregate <%s> == <%s>\n", SCIPvarGetName(consdata->vars[0]),
5032  SCIPvarGetName(consdata->vars[1]));
5033  SCIP_CALL( SCIPaggregateVars(scip, consdata->vars[0], consdata->vars[1], 1.0, -1.0, 0.0,
5034  &cutoff, &redundant, &aggregated) );
5035  }
5036  else
5037  {
5038  /* aggregate variables: vars[0] + vars[1] == 1 */
5039  SCIPdebugMsg(scip, " -> aggregate <%s> == 1 - <%s>\n", SCIPvarGetName(consdata->vars[0]),
5040  SCIPvarGetName(consdata->vars[1]));
5041  SCIP_CALL( SCIPaggregateVars(scip, consdata->vars[0], consdata->vars[1], 1.0, 1.0, 1.0,
5042  &cutoff, &redundant, &aggregated) );
5043  }
5044  assert(redundant || SCIPdoNotAggr(scip));
5045 
5046  if( aggregated )
5047  {
5048  assert(redundant);
5049  (*naggrvars)++;
5050  }
5051 
5052  /* the constraint can be deleted if the intvar is fixed or NULL */
5053  if( redundant )
5054  {
5055  SCIP_Bool fixedintvar;
5056 
5057  fixedintvar = consdata->intvar == NULL ? TRUE : SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->intvar), SCIPvarGetUbGlobal(consdata->intvar));
5058 
5059  if( fixedintvar )
5060  {
5061  /* if the integer variable is an original variable, i.e.,
5062  * consdata->deleteintvar == FALSE then the following
5063  * must hold:
5064  *
5065  * if consdata->rhs == 1 then the integer variable needs
5066  * to be fixed to zero, otherwise the constraint is
5067  * infeasible,
5068  *
5069  * if consdata->rhs == 0 then the integer variable needs
5070  * to be aggregated to one of the binary variables
5071  */
5072  assert(consdata->deleteintvar || (consdata->rhs && SCIPvarGetLbGlobal(consdata->intvar) < 0.5));
5073 
5074  /* delete constraint */
5075  SCIP_CALL( SCIPdelCons(scip, cons) );
5076  (*ndelconss)++;
5077  }
5078  }
5079  }
5080  else if( (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
5081  {
5082  /* try to use clique information to upgrade the constraint to a set-partitioning constraint or fix
5083  * variables
5084  */
5085  SCIP_CALL( cliquePresolve(scip, cons, nfixedvars, nchgcoefs, ndelconss, naddconss, &cutoff) );
5086  }
5087  }
5088  }
5089 
5090  /* process pairs of constraints: check them for equal operands;
5091  * only apply this expensive procedure, if the single constraint preprocessing did not find any reductions
5092  */
5093  if( !cutoff && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 && SCIPisPresolveFinished(scip) )
5094  {
5095  if( firstchange < nconss && conshdlrdata->presolusehashing )
5096  {
5097  /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
5098  SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, nchgcoefs, naggrvars, ndelconss, naddconss, &cutoff) );
5099  }
5100  if( conshdlrdata->presolpairwise )
5101  {
5102  SCIP_Longint npaircomparisons;
5103  int lastndelconss;
5104  npaircomparisons = 0;
5105  lastndelconss = *ndelconss;
5106 
5107  for( c = firstchange; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
5108  {
5109  if( SCIPconsIsActive(conss[c]) && !SCIPconsIsModifiable(conss[c]) )
5110  {
5111  npaircomparisons += (SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange);
5112 
5113  SCIP_CALL( preprocessConstraintPairs(scip, conss, firstchange, c,
5114  &cutoff, nfixedvars, naggrvars, ndelconss, naddconss, nchgcoefs) );
5115 
5116  if( npaircomparisons > NMINCOMPARISONS )
5117  {
5118  if( ((SCIP_Real) (*ndelconss - lastndelconss)) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
5119  break;
5120  lastndelconss = *ndelconss;
5121  npaircomparisons = 0;
5122  }
5123  }
5124  }
5125  }
5126  }
5127 
5128  /* return the correct result code */
5129  if( cutoff )
5130  *result = SCIP_CUTOFF;
5131  else if( *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds || *naggrvars > oldnaggrvars
5132  || *ndelconss > oldndelconss || *nchgcoefs > oldnchgcoefs )
5133  *result = SCIP_SUCCESS;
5134  else
5135  *result = SCIP_DIDNOTFIND;
5136 
5137  /* add extended formulation at the end of presolving if required */
5138  if ( conshdlrdata->addextendedform && *result == SCIP_DIDNOTFIND && SCIPisPresolveFinished(scip) )
5139  {
5140  for (c = 0; c < nconss && ! SCIPisStopped(scip); ++c)
5141  {
5142  int naddedconss = 0;
5143 
5144  cons = conss[c];
5145  assert(cons != NULL);
5146  consdata = SCIPconsGetData(cons);
5147  assert(consdata != NULL);
5148 
5149  if ( consdata->extvars != NULL )
5150  break;
5151 
5152  if ( conshdlrdata->addflowextended )
5153  {
5154  SCIP_CALL( addExtendedFlowFormulation(scip, cons, &naddedconss) );
5155  }
5156  else
5157  {
5158  SCIP_CALL( addExtendedAsymmetricFormulation(scip, cons, &naddedconss) );
5159  }
5160  (*naddconss) += naddedconss;
5161  }
5162  }
5163 
5164  return SCIP_OKAY;
5165 }
5166 
5167 
5168 /** propagation conflict resolving method of constraint handler */
5169 static
5170 SCIP_DECL_CONSRESPROP(consRespropXor)
5171 { /*lint --e{715}*/
5172  SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
5173 
5174  return SCIP_OKAY;
5175 }
5176 
5177 
5178 /** variable rounding lock method of constraint handler */
5179 static
5180 SCIP_DECL_CONSLOCK(consLockXor)
5181 { /*lint --e{715}*/
5182  SCIP_CONSDATA* consdata;
5183  int i;
5184 
5185  consdata = SCIPconsGetData(cons);
5186  assert(consdata != NULL);
5187 
5188  /* external variables */
5189  for( i = 0; i < consdata->nvars; ++i )
5190  {
5191  SCIP_CALL( SCIPaddVarLocks(scip, consdata->vars[i], nlockspos + nlocksneg, nlockspos + nlocksneg) );
5192  }
5193 
5194  /* internal variable */
5195  if( consdata->intvar != NULL )
5196  {
5197  SCIP_CALL( SCIPaddVarLocks(scip, consdata->intvar, nlockspos + nlocksneg, nlockspos + nlocksneg) );
5198  }
5199 
5200  return SCIP_OKAY;
5201 }
5202 
5203 
5204 /** constraint display method of constraint handler */
5205 static
5206 SCIP_DECL_CONSPRINT(consPrintXor)
5207 { /*lint --e{715}*/
5208  assert( scip != NULL );
5209  assert( conshdlr != NULL );
5210  assert( cons != NULL );
5211 
5212  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file, FALSE) );
5213 
5214  return SCIP_OKAY;
5215 }
5216 
5217 /** constraint copying method of constraint handler */
5218 static
5219 SCIP_DECL_CONSCOPY(consCopyXor)
5220 { /*lint --e{715}*/
5221  SCIP_CONSDATA* sourceconsdata;
5222  SCIP_VAR** sourcevars;
5223  SCIP_VAR** targetvars;
5224  SCIP_VAR* intvar;
5225  SCIP_VAR* targetintvar;
5226  const char* consname;
5227  int nvars;
5228  int v;
5229 
5230  assert(scip != NULL);
5231  assert(sourcescip != NULL);
5232  assert(sourcecons != NULL);
5233 
5234  (*valid) = TRUE;
5235 
5236  sourceconsdata = SCIPconsGetData(sourcecons);
5237  assert(sourceconsdata != NULL);
5238 
5239  /* get variables and coefficients of the source constraint */
5240  sourcevars = sourceconsdata->vars;
5241  nvars = sourceconsdata->nvars;
5242  intvar = sourceconsdata->intvar;
5243  targetintvar = NULL;
5244 
5245  if( name != NULL )
5246  consname = name;
5247  else
5248  consname = SCIPconsGetName(sourcecons);
5249 
5250  if( nvars == 0 )
5251  {
5252  if( intvar != NULL )
5253  {
5254  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, intvar, &targetintvar, varmap, consmap, global, valid) );
5255  assert(!(*valid) || targetintvar != NULL);
5256 
5257  SCIPdebugMsg(scip, "Copied integral variable <%s> (bounds: [%g,%g])\n", SCIPvarGetName(targetintvar),
5258  global ? SCIPvarGetLbGlobal(intvar) : SCIPvarGetLbLocal(intvar),
5259  global ? SCIPvarGetUbGlobal(intvar) : SCIPvarGetUbLocal(intvar));
5260  }
5261 
5262  if( *valid )
5263  {
5264  SCIP_CALL( createConsXorIntvar(scip, cons, consname, SCIPgetRhsXor(sourcescip, sourcecons), 0, NULL,
5265  targetintvar, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable,
5266  stickingatnode) );
5267  }
5268 
5269  return SCIP_OKAY;
5270  }
5271 
5272  /* duplicate variable array */
5273  SCIP_CALL( SCIPallocBufferArray(scip, &targetvars, nvars) );
5274 
5275  /* map variables of the source constraint to variables of the target SCIP */
5276  for( v = 0; v < nvars && *valid; ++v )
5277  {
5278  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &targetvars[v], varmap, consmap, global, valid) );
5279  assert(!(*valid) || targetvars[v] != NULL);
5280  }
5281 
5282  /* map artificial relaxation variable of the source constraint to variable of the target SCIP */
5283  if( *valid && intvar != NULL )
5284  {
5285  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, intvar, &targetintvar, varmap, consmap, global, valid) );
5286  assert(!(*valid) || targetintvar != NULL);
5287 
5288  SCIPdebugMsg(scip, "Copied integral variable <%s> (bounds: [%g,%g])\n", SCIPvarGetName(targetintvar),
5289  global ? SCIPvarGetLbGlobal(intvar) : SCIPvarGetLbLocal(intvar),
5290  global ? SCIPvarGetUbGlobal(intvar) : SCIPvarGetUbLocal(intvar));
5291  }
5292 
5293  /* only create the target constraints, if all variables could be copied */
5294  if( *valid )
5295  {
5296  SCIP_CALL( createConsXorIntvar(scip, cons, consname, SCIPgetRhsXor(sourcescip, sourcecons), nvars, targetvars,
5297  targetintvar, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable,
5298  stickingatnode) );
5299  }
5300 
5301  /* free buffer array */
5302  SCIPfreeBufferArray(scip, &targetvars);
5303 
5304  return SCIP_OKAY;
5305 }
5306 
5307 
5308 /** constraint parsing method of constraint handler */
5309 static
5310 SCIP_DECL_CONSPARSE(consParseXor)
5311 { /*lint --e{715}*/
5312  SCIP_VAR** vars;
5313  char* endptr;
5314  int requiredsize;
5315  int varssize;
5316  int nvars;
5317 
5318  SCIPdebugMsg(scip, "parse <%s> as xor constraint\n", str);
5319 
5320  varssize = 100;
5321  nvars = 0;
5322 
5323  /* allocate buffer array for variables */
5324  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
5325 
5326  /* parse string */
5327  SCIP_CALL( SCIPparseVarsList(scip, str, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
5328 
5329  if( *success )
5330  {
5331  SCIP_Real rhs;
5332 
5333  /* check if the size of the variable array was big enough */
5334  if( varssize < requiredsize )
5335  {
5336  /* reallocate memory */
5337  varssize = requiredsize;
5338  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
5339 
5340  /* parse string again with the correct size of the variable array */
5341  SCIP_CALL( SCIPparseVarsList(scip, str, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
5342  }
5343 
5344  assert(*success);
5345  assert(varssize >= requiredsize);
5346 
5347  SCIPdebugMsg(scip, "successfully parsed %d variables\n", nvars);
5348 
5349  str = endptr;
5350 
5351  /* search for the equal symbol */
5352  while( *str != '=' && *str != '\0' )
5353  str++;
5354 
5355  /* if the string end has been reached without finding the '=' */
5356  if ( *str == '\0' )
5357  {
5358  SCIPerrorMessage("Could not find terminating '='.\n");
5359  *success = FALSE;
5360  }
5361  else
5362  {
5363  /* skip '=' character */
5364  ++str;
5365 
5366  if( SCIPstrToRealValue(str, &rhs, &endptr) )
5367  {
5368  SCIP_VAR* intvar = NULL;
5369 
5370  assert(SCIPisZero(scip, rhs) || SCIPisEQ(scip, rhs, 1.0));
5371 
5372  str = endptr;
5373 
5374  /* skip white spaces */
5375  while( *str == ' ' || *str == '\t' )
5376  str++;
5377 
5378  /* check for integer variable, should look like (intvar = var) */
5379  if( *str == '(' )
5380  {
5381  str++;
5382  while( *str != '=' && *str != '\0' )
5383  str++;
5384 
5385  if( *str != '=' )
5386  {
5387  SCIPerrorMessage("Parsing integer variable of XOR constraint\n");
5388  *success = FALSE;
5389  goto TERMINATE;
5390  }
5391 
5392  str++;
5393  /* skip white spaces */
5394  while( *str == ' ' || *str == '\t' )
5395  str++;
5396 
5397  /* parse variable name */
5398  SCIP_CALL( SCIPparseVarName(scip, str, &intvar, &endptr) );
5399 
5400  if( intvar == NULL )
5401  {
5402  SCIPdebugMsg(scip, "variable with name <%s> does not exist\n", SCIPvarGetName(intvar));
5403  (*success) = FALSE;
5404  goto TERMINATE;
5405  }
5406  str = endptr;
5407 
5408  /* skip last ')' */
5409  while( *str != ')' && *str != '\0' )
5410  str++;
5411  }
5412 
5413  if( intvar != NULL )
5414  {
5415  /* create or constraint */
5416  SCIP_CALL( createConsXorIntvar(scip, cons, name, (rhs > 0.5 ? TRUE : FALSE), nvars, vars, intvar,
5417  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5418  }
5419  else
5420  {
5421  /* create or constraint */
5422  SCIP_CALL( SCIPcreateConsXor(scip, cons, name, (rhs > 0.5 ? TRUE : FALSE), nvars, vars,
5423  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5424  }
5425 
5426  SCIPdebugPrintCons(scip, *cons, NULL);
5427  }
5428  else
5429  *success = FALSE;
5430  }
5431  }
5432 
5433  TERMINATE:
5434  /* free variable buffer */
5435  SCIPfreeBufferArray(scip, &vars);
5436 
5437  return SCIP_OKAY;
5438 }
5439 
5440 /** constraint method of constraint handler which returns the variables (if possible) */
5441 static
5442 SCIP_DECL_CONSGETVARS(consGetVarsXor)
5443 { /*lint --e{715}*/
5444  SCIP_CONSDATA* consdata;
5445  int nintvar = 0;
5446  int cnt;
5447  int j;
5448 
5449  consdata = SCIPconsGetData(cons);
5450  assert(consdata != NULL);
5451 
5452  if ( consdata->intvar != NULL )
5453  nintvar = 1;
5454 
5455  if ( varssize < consdata->nvars + nintvar + consdata->nextvars )
5456  (*success) = FALSE;
5457  else
5458  {
5459  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
5460 
5461  if ( consdata->intvar != NULL )
5462  vars[consdata->nvars] = consdata->intvar;
5463 
5464  if ( consdata->nextvars > 0 )
5465  {
5466  assert( consdata->extvars != NULL );
5467  cnt = consdata->nvars + nintvar;
5468  for (j = 0; j < consdata->extvarssize; ++j)
5469  {
5470  if ( consdata->extvars[j] != NULL )
5471  vars[cnt++] = consdata->extvars[j];
5472  }
5473  assert( cnt == consdata->nvars + nintvar + consdata->nextvars );
5474  }
5475 
5476  (*success) = TRUE;
5477  }
5478 
5479  return SCIP_OKAY;
5480 }
5481 
5482 /** constraint method of constraint handler which returns the number of variable (if possible) */
5483 static
5484 SCIP_DECL_CONSGETNVARS(consGetNVarsXor)
5485 { /*lint --e{715}*/
5486  SCIP_CONSDATA* consdata;
5487 
5488  assert(cons != NULL);
5489 
5490  consdata = SCIPconsGetData(cons);
5491  assert(consdata != NULL);
5492 
5493  if( consdata->intvar == NULL )
5494  (*nvars) = consdata->nvars + consdata->nextvars;
5495  else
5496  (*nvars) = consdata->nvars + 1 + consdata->nextvars;
5497 
5498  (*success) = TRUE;
5499 
5500  return SCIP_OKAY;
5501 }
5502 
5503 /*
5504  * Callback methods of event handler
5505  */
5506 
5507 static
5508 SCIP_DECL_EVENTEXEC(eventExecXor)
5509 { /*lint --e{715}*/
5510  SCIP_CONSDATA* consdata;
5511 
5512  assert(eventhdlr != NULL);
5513  assert(eventdata != NULL);
5514  assert(event != NULL);
5515 
5516  consdata = (SCIP_CONSDATA*)eventdata;
5517  assert(consdata != NULL);
5518 
5520  {
5521  /* we only catch this event in presolving stage */
5522  assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING);
5523  assert(SCIPeventGetVar(event) != NULL);
5524 
5525  consdata->sorted = FALSE;
5526  }
5527 
5528  consdata->propagated = FALSE;
5529 
5530  return SCIP_OKAY;
5531 }
5532 
5533 
5534 /*
5535  * constraint specific interface methods
5536  */
5537 
5538 /** creates the handler for xor constraints and includes it in SCIP */
5540  SCIP* scip /**< SCIP data structure */
5541  )
5542 {
5543  SCIP_CONSHDLRDATA* conshdlrdata;
5544  SCIP_CONSHDLR* conshdlr;
5545  SCIP_EVENTHDLR* eventhdlr;
5546 
5547  /* create event handler for events on variables */
5549  eventExecXor, NULL) );
5550 
5551  /* create constraint handler data */
5552  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
5553 
5554  /* include constraint handler */
5557  consEnfolpXor, consEnfopsXor, consCheckXor, consLockXor,
5558  conshdlrdata) );
5559  assert(conshdlr != NULL);
5560 
5561  /* set non-fundamental callbacks via specific setter functions */
5562  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyXor, consCopyXor) );
5563  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteXor) );
5564  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolXor) );
5565  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeXor) );
5566  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsXor) );
5567  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsXor) );
5568  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpXor) );
5569  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseXor) );
5570  SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreXor) );
5571  SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreXor) );
5572  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolXor, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
5573  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintXor) );
5574  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropXor, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
5576  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropXor) );
5577  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpXor, consSepasolXor, CONSHDLR_SEPAFREQ,
5579  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransXor) );
5580  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxXor) );
5581 
5582  if ( SCIPfindConshdlr(scip, "linear") != NULL )
5583  {
5584  /* include the linear constraint upgrade in the linear constraint handler */
5586  }
5587 
5588  /* add xor constraint handler parameters */
5590  "constraints/xor/presolpairwise",
5591  "should pairwise constraint comparison be performed in presolving?",
5592  &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
5593 
5595  "constraints/xor/presolusehashing",
5596  "should hash table be used for detecting redundant constraints in advance?",
5597  &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
5598 
5600  "constraints/xor/addextendedform",
5601  "should the extended formulation be added in presolving?",
5602  &conshdlrdata->addextendedform, TRUE, DEFAULT_ADDEXTENDEDFORM, NULL, NULL) );
5603 
5605  "constraints/xor/addflowextended",
5606  "should the extended flow formulation be added (nonsymmetric formulation otherwise)?",
5607  &conshdlrdata->addflowextended, TRUE, DEFAULT_ADDFLOWEXTENDED, NULL, NULL) );
5608 
5610  "constraints/xor/separateparity",
5611  "should parity inequalities be separated?",
5612  &conshdlrdata->separateparity, TRUE, DEFAULT_SEPARATEPARITY, NULL, NULL) );
5613 
5614  SCIP_CALL( SCIPaddIntParam(scip,
5615  "constraints/xor/gausspropfreq",
5616  "frequency for applying the Gauss propagator",
5617  &conshdlrdata->gausspropfreq, TRUE, DEFAULT_GAUSSPROPFREQ, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
5618 
5619  return SCIP_OKAY;
5620 }
5621 
5622 /** creates and captures a xor constraint x_0 xor ... xor x_{k-1} = rhs
5623  *
5624  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5625  */
5627  SCIP* scip, /**< SCIP data structure */
5628  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5629  const char* name, /**< name of constraint */
5630  SCIP_Bool rhs, /**< right hand side of the constraint */
5631  int nvars, /**< number of operator variables in the constraint */
5632  SCIP_VAR** vars, /**< array with operator variables of constraint */
5633  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5634  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5635  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5636  * Usually set to TRUE. */
5637  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5638  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5639  SCIP_Bool check, /**< should the constraint be checked for feasibility?
5640  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5641  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5642  * Usually set to TRUE. */
5643  SCIP_Bool local, /**< is constraint only valid locally?
5644  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5645  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5646  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5647  * adds coefficients to this constraint. */
5648  SCIP_Bool dynamic, /**< is constraint subject to aging?
5649  * Usually set to FALSE. Set to TRUE for own cuts which
5650  * are separated as constraints. */
5651  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5652  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5653  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5654  * if it may be moved to a more global node?
5655  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5656  )
5657 {
5658  SCIP_CONSHDLR* conshdlr;
5659  SCIP_CONSDATA* consdata;
5660 
5661  /* find the xor constraint handler */
5662  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5663  if( conshdlr == NULL )
5664  {
5665  SCIPerrorMessage("xor constraint handler not found\n");
5666  return SCIP_PLUGINNOTFOUND;
5667  }
5668 
5669  /* create constraint data */
5670  SCIP_CALL( consdataCreate(scip, &consdata, rhs, nvars, vars, NULL) );
5671 
5672  /* create constraint */
5673  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5674  local, modifiable, dynamic, removable, stickingatnode) );
5675 
5676  return SCIP_OKAY;
5677 }
5678 
5679 /** creates and captures a xor constraint x_0 xor ... xor x_{k-1} = rhs
5680  * with all constraint flags set to their default values
5681  *
5682  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5683  */
5685  SCIP* scip, /**< SCIP data structure */
5686  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5687  const char* name, /**< name of constraint */
5688  SCIP_Bool rhs, /**< right hand side of the constraint */
5689  int nvars, /**< number of operator variables in the constraint */
5690  SCIP_VAR** vars /**< array with operator variables of constraint */
5691  )
5692 {
5693  SCIP_CALL( SCIPcreateConsXor(scip,cons, name, rhs, nvars, vars,
5694  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
5695 
5696  return SCIP_OKAY;
5697 }
5698 
5699 /** gets number of variables in xor constraint */
5700 int SCIPgetNVarsXor(
5701  SCIP* scip, /**< SCIP data structure */
5702  SCIP_CONS* cons /**< constraint data */
5703  )
5704 {
5705  SCIP_CONSDATA* consdata;
5706 
5707  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5708  {
5709  SCIPerrorMessage("constraint is not an xor constraint\n");
5710  SCIPABORT();
5711  return -1; /*lint !e527*/
5712  }
5713 
5714  consdata = SCIPconsGetData(cons);
5715  assert(consdata != NULL);
5716 
5717  return consdata->nvars;
5718 }
5719 
5720 /** gets array of variables in xor constraint */
5722  SCIP* scip, /**< SCIP data structure */
5723  SCIP_CONS* cons /**< constraint data */
5724  )
5725 {
5726  SCIP_CONSDATA* consdata;
5727 
5728  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5729  {
5730  SCIPerrorMessage("constraint is not an xor constraint\n");
5731  SCIPABORT();
5732  return NULL; /*lint !e527*/
5733  }
5734 
5735  consdata = SCIPconsGetData(cons);
5736  assert(consdata != NULL);
5737 
5738  return consdata->vars;
5739 }
5740 
5741 /** gets integer variable in xor constraint */
5743  SCIP* scip, /**< SCIP data structure */
5744  SCIP_CONS* cons /**< constraint data */
5745  )
5746 {
5747  SCIP_CONSDATA* consdata;
5748 
5749  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )