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