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-2022 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 */
111 
112 #define NROWS 5
113 
114 
115 /*
116  * Data structures
117  */
118 
119 /** type used for matrix entries in function checkGauss() */
120 typedef unsigned short Type;
121 
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;
170 
171 
172 /*
173  * Local methods
174  */
175 
176 /** installs rounding locks for the given variable in the given xor constraint */
177 static
178 SCIP_RETCODE lockRounding(
179  SCIP* scip, /**< SCIP data structure */
180  SCIP_CONS* cons, /**< xor constraint */
181  SCIP_VAR* var /**< variable of constraint entry */
182  )
183 {
184  assert(!SCIPconsIsLockedType(cons, SCIP_LOCKTYPE_CONFLICT));
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
194 SCIP_RETCODE unlockRounding(
195  SCIP* scip, /**< SCIP data structure */
196  SCIP_CONS* cons, /**< xor constraint */
197  SCIP_VAR* var /**< variable of constraint entry */
198  )
199 {
200  assert(!SCIPconsIsLockedType(cons, SCIP_LOCKTYPE_CONFLICT));
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
210 SCIP_RETCODE conshdlrdataCreate(
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
243 SCIP_RETCODE consdataSwitchWatchedvars(
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
307 SCIP_RETCODE consdataEnsureVarsSize(
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
331 SCIP_RETCODE consdataCreate(
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
406 SCIP_RETCODE consdataFreeRows(
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
428 SCIP_RETCODE consdataFree(
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
489 SCIP_RETCODE consdataPrint(
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, ") = %u", 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
523 SCIP_RETCODE setIntvar(
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
575 SCIP_RETCODE addCoef(
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  */
614  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_INITPRESOLVE
615  || SCIPgetStage(scip) == SCIP_STAGE_EXITPRESOLVE )
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
641 SCIP_RETCODE delCoefPos(
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 */
661  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_INITPRESOLVE
662  || SCIPgetStage(scip) == SCIP_STAGE_EXITPRESOLVE )
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
868 SCIP_RETCODE applyFixings(
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),*/
1006  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
1007  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(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),*/
1103  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
1104  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(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
1138 SCIP_RETCODE addExtendedFlowFormulation(
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,
1314  FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
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,
1352  FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
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,
1395  FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
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
1447 SCIP_RETCODE addExtendedAsymmetricFormulation(
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,
1547  FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
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,
1564  FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
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,
1581  FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
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,
1598  FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
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
1628 SCIP_RETCODE createRelaxation(
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,
1653  SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
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,
1683  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
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,
1699  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
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,
1709  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
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,
1716  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
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,
1733  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
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,
1743  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
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,
1750  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
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
1761 SCIP_RETCODE addRelaxation(
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
1793 SCIP_Bool allRowsInLP(
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
1815 SCIP_RETCODE checkCons(
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
1930 SCIP_RETCODE separateCons(
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
2143 int computeRowEcholonGF2(
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
2316 SCIP_RETCODE checkSystemGF2(
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 */
2501  while( SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED )
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  */
2536  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
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  {
2547  assert(SCIPvarIsActive(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED
2548  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
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  /* only try for active constraints and integral variable; hope for the best if they are not active */
2716  if ( xoractive[i] && consdata->intvar != NULL && SCIPvarIsActive(consdata->intvar) )
2717  {
2718  SCIP_Real val;
2719  int nones = 0;
2720 
2721  for (j = 0; j < consdata->nvars; ++j)
2722  {
2723  if ( SCIPgetSolVal(scip, sol, consdata->vars[j]) > 0.5 )
2724  ++nones;
2725  }
2726  /* if there are aggregated variables, the solution might not be feasible */
2727  assert( ! noaggr || nones % 2 == (int) consdata->rhs );
2728  if ( (unsigned int) nones != consdata->rhs )
2729  {
2730  val = (SCIP_Real) (nones - (int) consdata->rhs)/2;
2731  if ( SCIPisGE(scip, val, SCIPvarGetLbGlobal(consdata->intvar)) && SCIPisLE(scip, val, SCIPvarGetUbGlobal(consdata->intvar)) )
2732  {
2733  SCIP_CALL( SCIPsetSolVal(scip, sol, consdata->intvar, val) );
2734  }
2735  }
2736  }
2737  }
2738  SCIPdebug( SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ) );
2739 
2740  /* check feasibility of new solution and pass it to trysol heuristic */
2741  SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
2742  if ( success )
2743  {
2744  SCIP_CALL( SCIPheurPassSolAddSol(scip, heurtrysol, sol) );
2745  SCIPdebugMsg(scip, "Creating solution was successful.\n");
2746  }
2747 #ifdef SCIP_DEBUG
2748  else
2749  {
2750  /* the solution might not be feasible, because of additional constraints */
2751  SCIPdebugMsg(scip, "Creating solution was not successful.\n");
2752  }
2753 #endif
2754  SCIP_CALL( SCIPfreeSol(scip, &sol) );
2755  }
2756  }
2757  }
2758  else
2759  {
2760  *result = SCIP_CUTOFF;
2761  SCIPdebugMsg(scip, "System not feasible.\n");
2762  }
2763  }
2764 
2765  /* free storage */
2766  SCIPfreeBufferArray(scip, &s);
2767  SCIPfreeBufferArray(scip, &p);
2768  j = nconssmat - 1;
2769  for (i = nconss - 1; i >= 0 ; --i)
2770  {
2771  consdata = SCIPconsGetData(conss[i]);
2772  assert(consdata != NULL);
2773 
2774  if ( consdata->nvars == 0 )
2775  continue;
2776 
2777  if( !xoractive[i] )
2778  continue;
2779 
2780  SCIPfreeBufferArray(scip, &(A[j]));
2781  --j;
2782  }
2783  SCIPfreeBufferArray(scip, &A);
2784  SCIPfreeBufferArray(scip, &b);
2785  SCIPfreeBufferArray(scip, &xorbackidx);
2786  SCIPfreeBufferArray(scip, &xoridx);
2787  SCIPfreeBufferArray(scip, &xorvars);
2788  SCIPfreeBufferArray(scip, &xoractive);
2789  SCIPhashmapFree(&varhash);
2790 
2791  return SCIP_OKAY;
2792 }
2793 
2794 /** for each variable in the xor constraint, add it to conflict set; for integral variable add corresponding bound */
2795 static
2796 SCIP_RETCODE addConflictBounds(
2797  SCIP* scip, /**< SCIP data structure */
2798  SCIP_CONS* cons, /**< constraint that inferred the bound change */
2799  SCIP_VAR* infervar, /**< variable that was deduced, or NULL (not equal to integral variable) */
2800  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
2801  PROPRULE proprule /**< propagation rule */
2802  )
2803 {
2804  SCIP_CONSDATA* consdata;
2805  SCIP_VAR** vars;
2806  int nvars;
2807  int i;
2808 
2809  assert( cons != NULL );
2810 
2811  consdata = SCIPconsGetData(cons);
2812  assert(consdata != NULL);
2813  vars = consdata->vars;
2814  nvars = consdata->nvars;
2815 
2816  switch( proprule )
2817  {
2818  case PROPRULE_0:
2819  assert( infervar == NULL || infervar == consdata->intvar );
2820 
2821  /* the integral variable was fixed, because all variables were fixed */
2822  for (i = 0; i < nvars; ++i)
2823  {
2824  assert( SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE)) );
2825  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2826  }
2827  break;
2828 
2829  case PROPRULE_1:
2830  /* the variable was inferred, because all other variables were fixed */
2831  for (i = 0; i < nvars; ++i)
2832  {
2833  /* add variables that were fixed to 1 before */
2834  if ( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5 )
2835  {
2836  assert( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE) > 0.5 );
2837  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2838  }
2839  /* add variables that were fixed to 0 */
2840  else if ( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
2841  {
2842  assert( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE) < 0.5 );
2843  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2844  }
2845  else
2846  {
2847  /* check changed variable (changed variable is 0 or 1 afterwards) */
2848  assert( vars[i] == infervar );
2849  }
2850  }
2851  break;
2852 
2853  case PROPRULE_INTLB:
2854  assert( consdata->intvar != NULL );
2855 
2856  if( infervar != consdata->intvar )
2857  {
2858  /* the variable was fixed, because of the lower bound of the integral variable */
2859  SCIP_CALL( SCIPaddConflictLb(scip, consdata->intvar, NULL) );
2860  }
2861  /* to many and the other fixed variables */
2862  for (i = 0; i < nvars; ++i)
2863  {
2864  /* add variables that were fixed to 0 */
2865  if ( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
2866  {
2867  assert( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE) < 0.5 );
2868  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2869  }
2870  }
2871  break;
2872 
2873  case PROPRULE_INTUB:
2874  assert( consdata->intvar != NULL );
2875 
2876  if( infervar != consdata->intvar )
2877  {
2878  /* the variable was fixed, because of upper bound of the integral variable and the other fixed variables */
2879  SCIP_CALL( SCIPaddConflictUb(scip, consdata->intvar, NULL) );
2880  }
2881  for (i = 0; i < nvars; ++i)
2882  {
2883  /* add variables that were fixed to 1 */
2884  if ( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5 )
2885  {
2886  assert( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE) > 0.5 );
2887  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2888  }
2889  }
2890  break;
2891 
2892  case PROPRULE_INVALID:
2893  default:
2894  SCIPerrorMessage("invalid inference information %d in xor constraint <%s>\n", proprule, SCIPconsGetName(cons));
2895  SCIPABORT();
2896  return SCIP_INVALIDDATA; /*lint !e527*/
2897  }
2898 
2899  return SCIP_OKAY;
2900 }
2901 
2902 /** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */
2903 static
2904 SCIP_RETCODE analyzeConflict(
2905  SCIP* scip, /**< SCIP data structure */
2906  SCIP_CONS* cons, /**< xor constraint that detected the conflict */
2907  SCIP_VAR* infervar, /**< variable that was deduced, or NULL (not equal to integral variable) */
2908  PROPRULE proprule /**< propagation rule */
2909  )
2910 {
2911  /* conflict analysis can only be applied in solving stage and if it is applicable */
2912  if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
2913  return SCIP_OKAY;
2914 
2915  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
2916  SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
2917 
2918  /* add bound changes */
2919  SCIP_CALL( addConflictBounds(scip, cons, infervar, NULL, proprule) );
2920 
2921  /* analyze the conflict */
2922  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
2923 
2924  return SCIP_OKAY;
2925 }
2926 
2927 /** propagates constraint with the following rules:
2928  * (0) all variables are fixed => can fix integral variable
2929  * (1) all except one variable fixed => fix remaining variable and integral variable
2930  * (2) depending on the amount of fixed binary variables we can tighten the integral variable
2931  * (3) depending on the lower bound of the integral variable one can fix variables to 1
2932  * (4) depending on the upper bound of the integral variable one can fix variables to 0
2933  */
2934 static
2935 SCIP_RETCODE propagateCons(
2936  SCIP* scip, /**< SCIP data structure */
2937  SCIP_CONS* cons, /**< xor constraint to be processed */
2938  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2939  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2940  int* nfixedvars, /**< pointer to add up the number of fixed variables */
2941  int* nchgbds /**< pointer to add up the number of found domain reductions */
2942  )
2943 {
2944  SCIP_CONSDATA* consdata;
2945  SCIP_VAR** vars;
2946  SCIP_Bool infeasible;
2947  SCIP_Bool tightened;
2948  SCIP_Bool odd;
2949  int nvars;
2950  int nfixedones;
2951  int nfixedzeros;
2952  int watchedvar1;
2953  int watchedvar2;
2954  int i;
2955 
2956  assert(scip != NULL);
2957  assert(cons != NULL);
2958  assert(eventhdlr != NULL);
2959  assert(cutoff != NULL);
2960  assert(nfixedvars != NULL);
2961  assert(nchgbds != NULL);
2962 
2963  /* propagation can only be applied, if we know all operator variables */
2964  if( SCIPconsIsModifiable(cons) )
2965  return SCIP_OKAY;
2966 
2967  consdata = SCIPconsGetData(cons);
2968  assert(consdata != NULL);
2969 
2970  vars = consdata->vars;
2971  nvars = consdata->nvars;
2972 
2973  /* don't process the constraint, if the watched variables weren't fixed to any value since last propagation call */
2974  if( consdata->propagated )
2975  return SCIP_OKAY;
2976 
2977  /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
2978  if( !SCIPinRepropagation(scip) )
2979  {
2980  SCIP_CALL( SCIPincConsAge(scip, cons) );
2981  }
2982 
2983  /* propagation cannot be applied, if we have at least two unfixed variables left;
2984  * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
2985  * if these ones get fixed
2986  */
2987  watchedvar1 = consdata->watchedvar1;
2988  watchedvar2 = consdata->watchedvar2;
2989 
2990  /* check, if watched variables are still unfixed */
2991  if( watchedvar1 != -1 )
2992  {
2993  if( SCIPvarGetLbLocal(vars[watchedvar1]) > 0.5 || SCIPvarGetUbLocal(vars[watchedvar1]) < 0.5 )
2994  watchedvar1 = -1;
2995  }
2996  if( watchedvar2 != -1 )
2997  {
2998  if( SCIPvarGetLbLocal(vars[watchedvar2]) > 0.5 || SCIPvarGetUbLocal(vars[watchedvar2]) < 0.5 )
2999  watchedvar2 = -1;
3000  }
3001 
3002  /* if only one watched variable is still unfixed, make it the first one */
3003  if( watchedvar1 == -1 )
3004  {
3005  watchedvar1 = watchedvar2;
3006  watchedvar2 = -1;
3007  }
3008  assert(watchedvar1 != -1 || watchedvar2 == -1);
3009 
3010  /* if the watched variables are invalid (fixed), find new ones if existing; count the parity */
3011  odd = consdata->rhs;
3012  nfixedones = 0;
3013  nfixedzeros = 0;
3014  if( watchedvar2 == -1 )
3015  {
3016  for( i = 0; i < nvars; ++i )
3017  {
3018  if( SCIPvarGetLbLocal(vars[i]) > 0.5 )
3019  {
3020  odd = !odd;
3021  ++nfixedones;
3022  }
3023  else if( SCIPvarGetUbLocal(vars[i]) > 0.5 )
3024  {
3025  if( watchedvar1 == -1 )
3026  {
3027  assert(watchedvar2 == -1);
3028  watchedvar1 = i;
3029  }
3030  else if( watchedvar1 != i )
3031  {
3032  watchedvar2 = i;
3033  break;
3034  }
3035  }
3036  else if ( SCIPvarGetUbLocal(vars[i]) < 0.5 )
3037  ++nfixedzeros;
3038  }
3039  }
3040  assert(watchedvar1 != -1 || watchedvar2 == -1);
3041 
3042  /* if all variables are fixed, we can decide the feasibility of the constraint */
3043  if( watchedvar1 == -1 )
3044  {
3045  assert(watchedvar2 == -1);
3046 
3047  if( odd )
3048  {
3049  SCIPdebugMsg(scip, "constraint <%s>: all vars fixed, constraint is infeasible\n", SCIPconsGetName(cons));
3050 
3051  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
3052  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_0) );
3053  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3054 
3055  *cutoff = TRUE;
3056  }
3057  else
3058  {
3059  /* fix integral variable if present */
3060  if ( consdata->intvar != NULL && !consdata->deleteintvar )
3061  {
3062  int fixval;
3063 
3064  assert( ! *cutoff );
3065  assert( (nfixedones - (int) consdata->rhs) % 2 == 0 );
3066 
3067  fixval = (nfixedones - (int) consdata->rhs)/2; /*lint !e713*/
3068 
3069  SCIPdebugMsg(scip, "fix integral variable <%s> to %d\n", SCIPvarGetName(consdata->intvar), fixval);
3070 
3071  /* check whether value to fix is outside bounds */
3072  if ( fixval + 0.5 < SCIPvarGetLbLocal(consdata->intvar) )
3073  {
3074  /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3075  SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3076  fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3077 
3078  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTLB) );
3079  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3080 
3081  *cutoff = TRUE;
3082  }
3083  else if ( fixval - 0.5 > SCIPvarGetUbLocal(consdata->intvar) )
3084  {
3085  /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3086  SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3087  fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3088 
3089  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTUB) );
3090  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3091 
3092  *cutoff = TRUE;
3093  }
3094  else if( SCIPvarGetStatus(consdata->intvar) != SCIP_VARSTATUS_MULTAGGR )
3095  {
3096  if ( ! SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->intvar), (SCIP_Real) fixval) )
3097  {
3098  SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_0, FALSE, &infeasible, &tightened) );
3099  assert( tightened );
3100  assert( ! infeasible );
3101  }
3102 
3103  if ( ! SCIPisEQ(scip, SCIPvarGetUbLocal(consdata->intvar), (SCIP_Real) fixval) )
3104  {
3105  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_0, FALSE, &infeasible, &tightened) );
3106  assert( tightened );
3107  assert( ! infeasible );
3108  }
3109 
3110  ++(*nfixedvars);
3111  }
3112  }
3113  else
3114  {
3115  SCIPdebugMsg(scip, "constraint <%s>: all vars fixed, constraint is feasible\n", SCIPconsGetName(cons));
3116  }
3117  }
3118  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3119 
3120  return SCIP_OKAY;
3121  }
3122 
3123  /* if only one variable is not fixed, this variable can be deduced */
3124  if( watchedvar2 == -1 )
3125  {
3126  assert(watchedvar1 != -1);
3127 
3128  SCIPdebugMsg(scip, "constraint <%s>: only one unfixed variable -> fix <%s> to %u\n",
3129  SCIPconsGetName(cons), SCIPvarGetName(vars[watchedvar1]), odd);
3130 
3131  SCIP_CALL( SCIPinferBinvarCons(scip, vars[watchedvar1], odd, cons, (int)PROPRULE_1, &infeasible, &tightened) );
3132  assert(!infeasible);
3133  assert(tightened);
3134 
3135  (*nfixedvars)++;
3136 
3137  /* fix integral variable if present and not multi-aggregated */
3138  if ( consdata->intvar != NULL && !consdata->deleteintvar && SCIPvarGetStatus(consdata->intvar) != SCIP_VARSTATUS_MULTAGGR )
3139  {
3140  int fixval;
3141 
3142  /* if variable has been fixed to 1, adjust number of fixed variables */
3143  if ( odd )
3144  ++nfixedones;
3145 
3146  assert( (nfixedones - (int) consdata->rhs) % 2 == 0 );
3147 
3148  fixval = (nfixedones - (int) consdata->rhs)/2; /*lint !e713*/
3149  SCIPdebugMsg(scip, "should fix integral variable <%s> to %d\n", SCIPvarGetName(consdata->intvar), fixval);
3150 
3151  /* check whether value to fix is outside bounds */
3152  if ( fixval + 0.5 < SCIPvarGetLbLocal(consdata->intvar) )
3153  {
3154  /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3155  SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3156  fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3157 
3158  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTLB) );
3159  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3160 
3161  *cutoff = TRUE;
3162  }
3163  else if ( fixval - 0.5 > SCIPvarGetUbLocal(consdata->intvar) )
3164  {
3165  /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3166  SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3167  fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3168 
3169  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTUB) );
3170  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3171 
3172  *cutoff = TRUE;
3173  }
3174  else
3175  {
3176  if( SCIPvarGetLbLocal(consdata->intvar) + 0.5 < (SCIP_Real) fixval )
3177  {
3178  SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_1, TRUE, &infeasible, &tightened) );
3179  assert( tightened );
3180  assert( ! infeasible );
3181  }
3182 
3183  if( SCIPvarGetUbLocal(consdata->intvar) - 0.5 > (SCIP_Real) fixval )
3184  {
3185  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_1, TRUE, &infeasible, &tightened) );
3186  assert( tightened );
3187  assert( ! infeasible );
3188  }
3189  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar)));
3190 
3191  ++(*nfixedvars);
3192  }
3193  }
3194 
3195  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3196  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3197 
3198  return SCIP_OKAY;
3199  }
3200 
3201  /* propagate w.r.t. integral variable */
3202  if ( consdata->intvar != NULL && !consdata->deleteintvar )
3203  {
3204  SCIP_Real newlb;
3205  SCIP_Real newub;
3206  int nonesmin;
3207  int nonesmax;
3208 
3209  assert( nfixedones + nfixedzeros < nvars );
3210 
3211  assert( SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(consdata->intvar)) );
3212  assert( SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(consdata->intvar)) );
3213 
3214  nonesmin = 2 * (int)(SCIPvarGetLbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3215  nonesmax = 2 * (int)(SCIPvarGetUbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3216 
3217  /* the number of possible variables that can get value 1 is less than the minimum bound */
3218  if ( nvars - nfixedzeros < nonesmin )
3219  {
3220  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);
3221 
3222  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTLB) );
3223  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3224 
3225  *cutoff = TRUE;
3226 
3227  return SCIP_OKAY;
3228  }
3229 
3230  /* the number of variables that are fixed to 1 is larger than the maximum bound */
3231  if ( nfixedones > nonesmax )
3232  {
3233  SCIPdebugMsg(scip, "constraint <%s>: at least %d variables are fixed to 1, but there should be at most %d.\n", SCIPconsGetName(cons), nfixedones, nonesmax);
3234 
3235  SCIP_CALL( analyzeConflict(scip, cons, NULL, PROPRULE_INTUB) );
3236  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3237 
3238  *cutoff = TRUE;
3239 
3240  return SCIP_OKAY;
3241  }
3242 
3243  if( SCIPvarGetStatus(consdata->intvar) != SCIP_VARSTATUS_MULTAGGR )
3244  {
3245  /* compute new bounds on the integral variable */
3246  newlb = (SCIP_Real)((nfixedones + 1 - (int) consdata->rhs) / 2); /*lint !e653*/
3247  newub = (SCIP_Real)((nvars - nfixedzeros - (int) consdata->rhs) / 2); /*lint !e653*/
3248 
3249  /* new lower bound is better */
3250  if( newlb > SCIPvarGetLbLocal(consdata->intvar) + 0.5 )
3251  {
3252  SCIPdebugMsg(scip, "constraint <%s>: propagated lower bound of integral variable <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(consdata->intvar), newlb);
3253  SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, newlb, cons, (int)PROPRULE_INTUB, TRUE, &infeasible, &tightened) );
3254  assert(tightened);
3255  assert(!infeasible);
3256 
3257  ++(*nchgbds);
3258 
3259  nonesmin = 2 * (int)(SCIPvarGetLbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3260  }
3261 
3262  /* new upper bound is better */
3263  if( newub < SCIPvarGetUbLocal(consdata->intvar) - 0.5 )
3264  {
3265  SCIPdebugMsg(scip, "constraint <%s>: propagated upper bound of integral variable <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(consdata->intvar), newub);
3266  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, newub, cons, (int)PROPRULE_INTLB, TRUE, &infeasible, &tightened) );
3267  assert(tightened);
3268  assert(!infeasible);
3269 
3270  ++(*nchgbds);
3271 
3272  nonesmax = 2 * (int)(SCIPvarGetUbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3273  }
3274 
3275  assert(nvars - nfixedzeros >= nonesmin);
3276  assert(nfixedones <= nonesmax);
3277 
3278  /* the number of variables that are free or fixed to 1 is exactly the minimum required -> fix free variables to 1 */
3279  if ( nvars - nfixedzeros == nonesmin )
3280  {
3281  SCIPdebugMsg(scip, "constraint <%s>: fix %d free variables to 1 to reach lower bound of %d\n", SCIPconsGetName(cons), nvars - nfixedzeros - nfixedones, nonesmin);
3282 
3283  for (i = 0; i < nvars; ++i)
3284  {
3285  if ( SCIPvarGetLbLocal(vars[i]) < 0.5 && SCIPvarGetUbLocal(vars[i]) > 0.5 )
3286  {
3287  SCIP_CALL( SCIPinferBinvarCons(scip, vars[i], TRUE, cons, (int)PROPRULE_INTLB, &infeasible, &tightened) );
3288  assert( !infeasible );
3289  assert( tightened );
3290 
3291  ++(*nfixedvars);
3292  }
3293  }
3294  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3295  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3296 
3297  return SCIP_OKAY;
3298  }
3299 
3300  /* the number of variables that are fixed to 1 is exactly the maximum required -> fix free variables to 0 */
3301  if ( nfixedones == nonesmax )
3302  {
3303  SCIPdebugMsg(scip, "constraint <%s>: fix %d free variables to 0 to guarantee upper bound of %d\n", SCIPconsGetName(cons), nvars - nfixedzeros - nfixedones, nonesmax);
3304 
3305  for (i = 0; i < nvars; ++i)
3306  {
3307  if ( SCIPvarGetLbLocal(vars[i]) < 0.5 && SCIPvarGetUbLocal(vars[i]) > 0.5 )
3308  {
3309  SCIP_CALL( SCIPinferBinvarCons(scip, vars[i], FALSE, cons, (int)PROPRULE_INTUB, &infeasible, &tightened) );
3310  assert(!infeasible);
3311  assert(tightened);
3312  ++(*nfixedvars);
3313  }
3314  }
3315  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3316  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3317 
3318  return SCIP_OKAY;
3319  }
3320  }
3321  }
3322 
3323  /* switch to the new watched variables */
3324  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
3325 
3326  /* mark the constraint propagated */
3327  consdata->propagated = TRUE;
3328 
3329  return SCIP_OKAY;
3330 }
3331 
3332 /** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
3333  * propagation rules (see propagateCons())
3334  */
3335 static
3336 SCIP_RETCODE resolvePropagation(
3337  SCIP* scip, /**< SCIP data structure */
3338  SCIP_CONS* cons, /**< constraint that inferred the bound change */
3339  SCIP_VAR* infervar, /**< variable that was deduced */
3340  PROPRULE proprule, /**< propagation rule that deduced the value */
3341  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
3342  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
3343  )
3344 {
3345  assert(result != NULL);
3346 
3347  SCIPdebugMsg(scip, "resolving fixations according to rule %d\n", (int) proprule);
3348 
3349  SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, proprule) );
3350  *result = SCIP_SUCCESS;
3351 
3352  return SCIP_OKAY;
3353 }
3354 
3355 /** try to use clique information to delete a part of the xor constraint or even fix variables */
3356 static
3357 SCIP_RETCODE cliquePresolve(
3358  SCIP* scip, /**< SCIP data structure */
3359  SCIP_CONS* cons, /**< constraint that inferred the bound change */
3360  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3361  int* nchgcoefs, /**< pointer to add up the number of deleted entries */
3362  int* ndelconss, /**< pointer to add up the number of deleted constraints */
3363  int* naddconss, /**< pointer to add up the number of added constraints */
3364  SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
3365  )
3366 {
3367  SCIP_CONSDATA* consdata;
3368  SCIP_VAR** vars;
3369  int nvars;
3370  SCIP_Bool breaked;
3371  SCIP_Bool restart;
3372  int posnotinclq1;
3373  int posnotinclq2;
3374  int v;
3375  int v1;
3376 
3377  assert(scip != NULL);
3378  assert(cons != NULL);
3379  assert(nfixedvars != NULL);
3380  assert(nchgcoefs != NULL);
3381  assert(ndelconss != NULL);
3382  assert(naddconss != NULL);
3383  assert(cutoff != NULL);
3384 
3385  /* propagation can only be applied, if we know all operator variables */
3386  if( SCIPconsIsModifiable(cons) )
3387  return SCIP_OKAY;
3388 
3389  consdata = SCIPconsGetData(cons);
3390  assert(consdata != NULL);
3391 
3392  vars = consdata->vars;
3393  nvars = consdata->nvars;
3394 
3395  if( nvars < 3 )
3396  return SCIP_OKAY;
3397 
3398  /* we cannot perform this steps if the integer variables in not artificial */
3399  if( !consdata->deleteintvar )
3400  return SCIP_OKAY;
3401 
3402 #if 0 /* try to evaluate if clique presolving should only be done multiple times when the constraint changed */
3403  if( !consdata->changed )
3404  return SCIP_OKAY;
3405 #endif
3406 
3407  /* @todo: if clique information would have saved the type of the clique, like <= 1, or == 1 we could do more
3408  * presolving like:
3409  *
3410  * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2) == 1) => xor(x3,x4) = 0
3411  * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2,x3) == 1) => (x4 = 0 and delete xor constraint)
3412  */
3413 
3414  /* 1. we have only clique information "<=", so we can check if all variables are in the same clique
3415  *
3416  * (xor(x1,x2,x3) = 1 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 = 1 and delete old
3417  * xor-constraint)
3418  *
3419  * (xor(x1,x2,x3) = 0 and clique(x1,x2,x3) <= 1) => (fix all variables x1 = x2 = x3 = 0 and delete old xor-
3420  * constraint)
3421  */
3422 
3423  /* 2. we have only clique information "<=", so we can check if all but one variable are in the same clique
3424  *
3425  * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 + x4 = 1 and
3426  * delete old xor constraint)
3427  *
3428  * (xor(x1,x2,x3,x4) = 0 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 + ~x4 = 1 and
3429  * delete old xor constraint)
3430  */
3431 
3432  posnotinclq1 = -1; /* index of variable that is possible not in the clique */
3433  posnotinclq2 = -1; /* index of variable that is possible not in the clique */
3434  breaked = FALSE;
3435  restart = FALSE;
3436 
3437  v = nvars - 2;
3438  while( v >= 0 )
3439  {
3440  SCIP_VAR* var;
3441  SCIP_VAR* var1;
3442  SCIP_Bool value;
3443  SCIP_Bool value1;
3444 
3445  assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
3446 
3447  value = SCIPvarIsActive(vars[v]);
3448 
3449  if( !value )
3450  var = SCIPvarGetNegationVar(vars[v]);
3451  else
3452  var = vars[v];
3453 
3454  if( posnotinclq1 == v )
3455  {
3456  --v;
3457  continue;
3458  }
3459 
3460  for( v1 = v+1; v1 < nvars; ++v1 )
3461  {
3462  if( posnotinclq1 == v1 )
3463  continue;
3464 
3465  value1 = SCIPvarIsActive(vars[v1]);
3466 
3467  if( !value1 )
3468  var1 = SCIPvarGetNegationVar(vars[v1]);
3469  else
3470  var1 = vars[v1];
3471 
3472  if( !SCIPvarsHaveCommonClique(var, value, var1, value1, TRUE) )
3473  {
3474  /* if the position of the variable which is not in the clique with all other variables is not yet
3475  * initialized, than do now, one of both variables does not fit
3476  */
3477  if( posnotinclq1 == -1 )
3478  {
3479  posnotinclq1 = v;
3480  posnotinclq2 = v1;
3481  }
3482  else
3483  {
3484  /* no clique with exactly nvars-1 variables */
3485  if( restart || (posnotinclq2 != v && posnotinclq2 != v1) )
3486  {
3487  breaked = TRUE;
3488  break;
3489  }
3490 
3491  /* check the second variables for not fitting into the clique of (nvars - 1) variables */
3492  posnotinclq1 = posnotinclq2;
3493  restart = TRUE;
3494  v = nvars - 1;
3495  }
3496 
3497  break;
3498  }
3499  else
3500  assert(vars[v] != vars[v1]);
3501  }
3502 
3503  if( breaked )
3504  break;
3505 
3506  --v;
3507  }
3508 
3509  /* at least nvars-1 variables are in one clique */
3510  if( !breaked ) /*lint !e774*/
3511  {
3512  /* all variables are in one clique, case 1 */
3513  if( posnotinclq1 == -1 )
3514  {
3515  /* all variables of xor constraints <%s> (with rhs == 1) are in one clique, so create a setpartitioning
3516  * constraint with all variables and delete this xor-constraint */
3517  if( consdata->rhs )
3518  {
3519  SCIP_CONS* newcons;
3520  char consname[SCIP_MAXSTRLEN];
3521 
3522  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_complete_clq", SCIPconsGetName(cons));
3523  SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, consname, nvars, vars,
3524  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
3525  SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
3526  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
3527  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3528 
3529  SCIP_CALL( SCIPaddCons(scip, newcons) );
3530  SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
3531  SCIPdebug( SCIP_CALL( SCIPprintCons(scip, newcons, NULL) ) );
3532  ++(*naddconss);
3533 
3534  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3535  }
3536  /* all variables of xor constraints <%s> (with rhs == 0) are in one clique, so fixed all variables to 0 */
3537  else
3538  {
3539  SCIP_Bool infeasible;
3540  SCIP_Bool fixed;
3541 
3542  SCIPdebugMsg(scip, "all variables of xor constraints <%s> are in one clique, so fixed all variables to 0\n",
3543  SCIPconsGetName(cons));
3544  SCIPdebug( SCIP_CALL( SCIPprintCons(scip, cons, NULL) ) );
3545 
3546  for( v = nvars - 1; v >= 0; --v )
3547  {
3548  SCIPdebugMsg(scip, "fixing variable <%s> to 0\n", SCIPvarGetName(vars[v]));
3549  SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, &infeasible, &fixed) );
3550 
3551  assert(infeasible || fixed);
3552 
3553  if( infeasible )
3554  {
3555  *cutoff = infeasible;
3556 
3557  return SCIP_OKAY;
3558  }
3559  else
3560  ++(*nfixedvars);
3561  }
3562  }
3563  }
3564  /* all but one variable are in one clique, case 2 */
3565  else
3566  {
3567  SCIP_CONS* newcons;
3568  char consname[SCIP_MAXSTRLEN];
3569 
3570  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_completed_clq", SCIPconsGetName(cons));
3571 
3572  /* complete clique by creating a set partioning constraint over all variables */
3573 
3574  /* if rhs == FALSE we need to exchange the variable not appaering in the clique with the negated variables */
3575  if( !consdata->rhs )
3576  {
3577  SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, consname, 0, NULL,
3578  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
3579  SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
3580  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
3581  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3582 
3583  for( v = 0; v < nvars; ++v )
3584  {
3585  if( v == posnotinclq1 )
3586  {
3587  SCIP_VAR* var;
3588 
3589  SCIP_CALL( SCIPgetNegatedVar(scip, vars[v], &var) );
3590  assert(var != NULL);
3591 
3592  SCIP_CALL( SCIPaddCoefSetppc(scip, newcons, var) );
3593  }
3594  else
3595  {
3596  SCIP_CALL( SCIPaddCoefSetppc(scip, newcons, vars[v]) );
3597  }
3598  }
3599  }
3600  /* if rhs == TRUE we can add all variables to the clique constraint directly */
3601  else
3602  {
3603  SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, consname, nvars, vars,
3604  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
3605  SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
3606  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
3607  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3608  }
3609 
3610  SCIP_CALL( SCIPaddCons(scip, newcons) );
3611  SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
3612  SCIPdebug( SCIP_CALL( SCIPprintCons(scip, newcons, NULL) ) );
3613  ++(*naddconss);
3614 
3615  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3616  }
3617 
3618  /* fix integer variable if it exists */
3619  if( consdata->intvar != NULL )
3620  {
3621  SCIP_Bool infeasible;
3622  SCIP_Bool fixed;
3623 
3624  SCIPdebugMsg(scip, "also fix the integer variable <%s> to 0\n", SCIPvarGetName(consdata->intvar));
3625  SCIP_CALL( SCIPfixVar(scip, consdata->intvar, 0.0, &infeasible, &fixed) );
3626 
3627  assert(infeasible || fixed || SCIPvarGetStatus(consdata->intvar) == SCIP_VARSTATUS_FIXED);
3628 
3629  if( infeasible )
3630  {
3631  *cutoff = infeasible;
3632  return SCIP_OKAY;
3633  }
3634  else if( fixed )
3635  ++(*nfixedvars);
3636  }
3637 
3638  /* delete old redundant xor-constraint */
3639  SCIP_CALL( SCIPdelCons(scip, cons) );
3640  ++(*ndelconss);
3641  }
3642 
3643  return SCIP_OKAY;
3644 }
3645 
3646 /** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
3647  * accordingly; in contrast to preprocessConstraintPairs(), it uses a hash table
3648  */
3649 static
3650 SCIP_RETCODE detectRedundantConstraints(
3651  SCIP* scip, /**< SCIP data structure */
3652  BMS_BLKMEM* blkmem, /**< block memory */
3653  SCIP_CONS** conss, /**< constraint set */
3654  int nconss, /**< number of constraints in constraint set */
3655  int* firstchange, /**< pointer to store first changed constraint */
3656  int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
3657  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3658  int* naggrvars, /**< pointer to add up the number of aggregated variables */
3659  int* ndelconss, /**< pointer to count number of deleted constraints */
3660  int* naddconss, /**< pointer to count number of added constraints */
3661  SCIP_Bool* cutoff /**< pointer to store TRUE, if a cutoff was found */
3662  )
3663 {
3664  SCIP_HASHTABLE* hashtable;
3665  int hashtablesize;
3666  int c;
3667 
3668  assert(conss != NULL);
3669  assert(ndelconss != NULL);
3670 
3671  /* create a hash table for the constraint set */
3672  hashtablesize = nconss;
3673  hashtablesize = MAX(hashtablesize, HASHSIZE_XORCONS);
3674 
3675  SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
3676  hashGetKeyXorcons, hashKeyEqXorcons, hashKeyValXorcons, (void*) scip) );
3677 
3678  /* check all constraints in the given set for redundancy */
3679  for( c = 0; c < nconss; ++c )
3680  {
3681  SCIP_CONS* cons0;
3682  SCIP_CONS* cons1;
3683  SCIP_CONSDATA* consdata0;
3684  SCIP_CONSHDLR* conshdlr;
3685  SCIP_CONSHDLRDATA* conshdlrdata;
3686 
3687  cons0 = conss[c];
3688 
3689  if( !SCIPconsIsActive(cons0) || SCIPconsIsModifiable(cons0) )
3690  continue;
3691 
3692  /* get constraint handler data */
3693  conshdlr = SCIPconsGetHdlr(cons0);
3694  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3695  assert(conshdlrdata != NULL);
3696 
3697  /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3698  * variables inside so we need to remove them for sorting
3699  */
3700  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3701  * merge multiple entries of the same or negated variables
3702  */
3703  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3704  if( *cutoff )
3705  goto TERMINATE;
3706 
3707  consdata0 = SCIPconsGetData(cons0);
3708 
3709  assert(consdata0 != NULL);
3710 
3711  /* applyFixings() led to an empty or trivial constraint */
3712  if( consdata0->nvars <= 1 )
3713  {
3714  if( consdata0->nvars == 0 )
3715  {
3716  /* the constraints activity cannot match an odd right hand side */
3717  if( consdata0->rhs )
3718  {
3719  *cutoff = TRUE;
3720  break;
3721  }
3722  }
3723  else
3724  {
3725  /* exactly 1 variable left. */
3726  SCIP_Bool infeasible;
3727  SCIP_Bool fixed;
3728 
3729  /* fix remaining variable */
3730  SCIP_CALL( SCIPfixVar(scip, consdata0->vars[0], (SCIP_Real) consdata0->rhs, &infeasible, &fixed) );
3731  assert(!infeasible);
3732 
3733  if( fixed )
3734  ++(*nfixedvars);
3735  }
3736 
3737  /* fix integral variable if present */
3738  if( consdata0->intvar != NULL && !consdata0->deleteintvar )
3739  {
3740  SCIP_Bool infeasible;
3741  SCIP_Bool fixed;
3742 
3743  SCIP_CALL( SCIPfixVar(scip, consdata0->intvar, 0.0, &infeasible, &fixed) );
3744  assert(!infeasible);
3745 
3746  if( fixed )
3747  ++(*nfixedvars);
3748  }
3749 
3750  /* delete empty constraint */
3751  SCIP_CALL( SCIPdelCons(scip, cons0) );
3752  ++(*ndelconss);
3753 
3754  continue;
3755  }
3756 
3757  /* sort the constraint */
3758  consdataSort(consdata0);
3759  assert(consdata0->sorted);
3760 
3761  /* get constraint from current hash table with same variables as cons0 */
3762  cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
3763 
3764  if( cons1 != NULL )
3765  {
3766  SCIP_CONSDATA* consdata1;
3767 
3768  assert(SCIPconsIsActive(cons1));
3769  assert(!SCIPconsIsModifiable(cons1));
3770 
3771  consdata1 = SCIPconsGetData(cons1);
3772 
3773  assert(consdata1 != NULL);
3774  assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
3775 
3776  assert(consdata0->sorted && consdata1->sorted);
3777  assert(consdata0->vars[0] == consdata1->vars[0]);
3778 
3779  if( consdata0->rhs != consdata1->rhs )
3780  {
3781  *cutoff = TRUE;
3782  goto TERMINATE;
3783  }
3784 
3785  /* aggregate parity variables into each other */
3786  if( consdata0->intvar != consdata1->intvar && consdata0->intvar != NULL )
3787  {
3788  if( consdata1->intvar != NULL )
3789  {
3790  SCIP_Bool redundant;
3791  SCIP_Bool aggregated;
3792  SCIP_Bool infeasible;
3793 
3794  SCIP_CALL( SCIPaggregateVars(scip, consdata0->intvar, consdata1->intvar, 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
3795 
3796  if( aggregated )
3797  {
3798  ++(*naggrvars);
3799  }
3800  if( infeasible )
3801  {
3802  *cutoff = TRUE;
3803  goto TERMINATE;
3804  }
3805  }
3806  /* the special case that only cons0 has a parity variable 'intvar' is treated by swapping cons0 and cons1 */
3807  else
3808  {
3809  SCIP_CALL( SCIPhashtableInsert(hashtable, (void *)cons0) );
3810  assert(SCIPhashtableRetrieve(hashtable, (void *)cons1) == cons0);
3811 
3812  SCIPswapPointers((void**)&cons0, (void**)(&cons1));
3813  SCIPswapPointers((void**)&consdata0, (void**)(&consdata1));
3814  }
3815  }
3816 
3817  /* delete cons0 and update flags of cons1 s.t. nonredundant information doesn't get lost */
3818  /* coverity[swapped_arguments] */
3819  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
3820  SCIP_CALL( SCIPdelCons(scip, cons0) );
3821  (*ndelconss)++;
3822 
3823  /* update the first changed constraint to begin the next aggregation round with */
3824  if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
3825  *firstchange = SCIPconsGetPos(cons1);
3826 
3827  assert(SCIPconsIsActive(cons1));
3828  }
3829  else
3830  {
3831  /* no such constraint in current hash table: insert cons0 into hash table */
3832  SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
3833  }
3834  }
3835 
3836  TERMINATE:
3837  /* free hash table */
3838  SCIPhashtableFree(&hashtable);
3839 
3840  return SCIP_OKAY;
3841 }
3842 
3843 /** compares constraint with all prior constraints for possible redundancy or aggregation,
3844  * and removes or changes constraint accordingly
3845  */
3846 static
3847 SCIP_RETCODE preprocessConstraintPairs(
3848  SCIP* scip, /**< SCIP data structure */
3849  SCIP_CONS** conss, /**< constraint set */
3850  int firstchange, /**< first constraint that changed since last pair preprocessing round */
3851  int chkind, /**< index of constraint to check against all prior indices upto startind */
3852  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3853  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3854  int* naggrvars, /**< pointer to count number of aggregated variables */
3855  int* ndelconss, /**< pointer to count number of deleted constraints */
3856  int* naddconss, /**< pointer to count number of added constraints */
3857  int* nchgcoefs /**< pointer to add up the number of changed coefficients */
3858  )
3859 {
3860  SCIP_CONSHDLR* conshdlr;
3861  SCIP_CONSHDLRDATA* conshdlrdata;
3862  SCIP_CONS* cons0;
3863  SCIP_CONSDATA* consdata0;
3864  SCIP_Bool cons0changed;
3865  int c;
3866 
3867  assert(conss != NULL);
3868  assert(firstchange <= chkind);
3869  assert(cutoff != NULL);
3870  assert(nfixedvars != NULL);
3871  assert(naggrvars != NULL);
3872  assert(ndelconss != NULL);
3873  assert(nchgcoefs != NULL);
3874 
3875  /* get the constraint to be checked against all prior constraints */
3876  cons0 = conss[chkind];
3877  assert(SCIPconsIsActive(cons0));
3878  assert(!SCIPconsIsModifiable(cons0));
3879 
3880  consdata0 = SCIPconsGetData(cons0);
3881  assert(consdata0 != NULL);
3882  assert(consdata0->nvars >= 1);
3883 
3884  /* get constraint handler data */
3885  conshdlr = SCIPconsGetHdlr(cons0);
3886  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3887  assert(conshdlrdata != NULL);
3888 
3889  /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3890  * variables inside so we need to remove them for sorting
3891  */
3892  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3893  * merge multiple entries of the same or negated variables
3894  */
3895  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3896  if( *cutoff )
3897  return SCIP_OKAY;
3898 
3899  /* sort cons0 */
3900  consdataSort(consdata0);
3901  assert(consdata0->sorted);
3902 
3903  /* check constraint against all prior constraints */
3904  cons0changed = consdata0->changed;
3905  consdata0->changed = FALSE;
3906  for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff) && SCIPconsIsActive(cons0) && !SCIPisStopped(scip); ++c )
3907  {
3908  SCIP_CONS* cons1;
3909  SCIP_CONSDATA* consdata1;
3910  SCIP_VAR* singlevar0;
3911  SCIP_VAR* singlevar1;
3912  SCIP_Bool parity;
3913  SCIP_Bool cons0hastwoothervars;
3914  SCIP_Bool cons1hastwoothervars;
3915  SCIP_Bool aborted;
3916  SCIP_Bool infeasible;
3917  SCIP_Bool fixed;
3918  SCIP_Bool redundant;
3919  SCIP_Bool aggregated;
3920  int v0;
3921  int v1;
3922 
3923  cons1 = conss[c];
3924 
3925  /* ignore inactive and modifiable constraints */
3926  if( !SCIPconsIsActive(cons1) || SCIPconsIsModifiable(cons1) )
3927  continue;
3928 
3929  consdata1 = SCIPconsGetData(cons1);
3930  assert(consdata1 != NULL);
3931 
3932  if( !consdata1->deleteintvar )
3933  continue;
3934 
3935  /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3936  * variables inside so we need to remove them for sorting
3937  */
3938  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3939  * merge multiple entries of the same or negated variables
3940  */
3941  SCIP_CALL( applyFixings(scip, cons1, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3942  assert(consdata1 == SCIPconsGetData(cons1));
3943  if( *cutoff )
3944  return SCIP_OKAY;
3945 
3946  SCIPdebugMsg(scip, "preprocess xor constraint pair <%s>[chg:%u] and <%s>[chg:%u]\n",
3947  SCIPconsGetName(cons0), cons0changed, SCIPconsGetName(cons1), consdata1->changed);
3948 
3949  /* if both constraints were not changed since last round, we can ignore the pair */
3950  if( !cons0changed && !consdata1->changed )
3951  continue;
3952 
3953  /* applyFixings() led to an empty constraint */
3954  if( consdata1->nvars == 0 )
3955  {
3956  if( consdata1->rhs )
3957  {
3958  *cutoff = TRUE;
3959  break;
3960  }
3961  else
3962  {
3963  /* fix integral variable if present */
3964  if( consdata1->intvar != NULL && !consdata1->deleteintvar )
3965  {
3966  SCIP_CALL( SCIPfixVar(scip, consdata1->intvar, 0.0, &infeasible, &fixed) );
3967  assert(!infeasible);
3968  if( fixed )
3969  ++(*nfixedvars);
3970  }
3971 
3972  /* delete empty constraint */
3973  SCIP_CALL( SCIPdelCons(scip, cons1) );
3974  ++(*ndelconss);
3975 
3976  continue;
3977  }
3978  }
3979  else if( consdata1->nvars == 1 )
3980  {
3981  /* fix remaining variable */
3982  SCIP_CALL( SCIPfixVar(scip, consdata1->vars[0], (SCIP_Real) consdata1->rhs, &infeasible, &fixed) );
3983  assert(!infeasible);
3984 
3985  if( fixed )
3986  ++(*nfixedvars);
3987 
3988  /* fix integral variable if present */
3989  if( consdata1->intvar != NULL && !consdata1->deleteintvar )
3990  {
3991  SCIP_CALL( SCIPfixVar(scip, consdata1->intvar, 0.0, &infeasible, &fixed) );
3992  assert(!infeasible);
3993  if( fixed )
3994  ++(*nfixedvars);
3995  }
3996 
3997  SCIP_CALL( SCIPdelCons(scip, cons1) );
3998  ++(*ndelconss);
3999 
4000  /* check for fixed variable in cons0 and remove it */
4001  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4002  assert(!(*cutoff));
4003 
4004  /* sort cons0 */
4005  consdataSort(consdata0);
4006  assert(consdata0->sorted);
4007 
4008  continue;
4009  }
4010  else if( consdata1->nvars == 2 )
4011  {
4012  if( !(consdata1->rhs) )
4013  {
4014  /* aggregate var0 == var1 */
4015  SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->vars[1], 1.0, -1.0, 0.0,
4016  &infeasible, &redundant, &aggregated) );
4017  }
4018  else
4019  {
4020  /* aggregate var0 == 1 - var1 */
4021  SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->vars[1], 1.0, 1.0, 1.0,
4022  &infeasible, &redundant, &aggregated) );
4023  }
4024  assert(!infeasible);
4025  assert(redundant || SCIPdoNotAggr(scip));
4026 
4027  if( aggregated )
4028  {
4029  ++(*naggrvars);
4030 
4031  /* check for aggregated variable in cons0 and remove it */
4032  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4033  if( *cutoff )
4034  return SCIP_OKAY;
4035 
4036  /* sort cons0 */
4037  consdataSort(consdata0);
4038  assert(consdata0->sorted);
4039  }
4040 
4041  if( redundant )
4042  {
4043  /* fix or aggregate the intvar, if it exists */
4044  if( consdata1->intvar != NULL && !consdata1->deleteintvar )
4045  {
4046  /* we have var0 + var1 - 2 * intvar = 1, and aggregated var1 = 1 - var0,
4047  * thus, intvar is always 0 */
4048  if( consdata1->rhs )
4049  {
4050  SCIP_CALL( SCIPfixVar(scip, consdata1->intvar, 0.0, &infeasible, &fixed) );
4051  assert(!infeasible);
4052  if( fixed )
4053  ++(*nfixedvars);
4054  }
4055  /* we have var0 + var1 - 2 * intvar = 0, and aggregated var1 = var0,
4056  * i.e., 2 * var0 - 2 * intvar = 0, so intvar = var0 holds and we aggregate */
4057  else
4058  {
4059  assert(!consdata1->rhs);
4060 
4061  /* aggregate intvar == var0 */
4062  SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->intvar, 1.0, -1.0, 0.0,
4063  &infeasible, &redundant, &aggregated) );
4064  assert(!infeasible);
4065  assert(redundant || SCIPdoNotAggr(scip));
4066 
4067  if( aggregated )
4068  {
4069  ++(*naggrvars);
4070  }
4071  }
4072  }
4073 
4074  if( redundant )
4075  {
4076  SCIP_CALL( SCIPdelCons(scip, cons1) );
4077  ++(*ndelconss);
4078  }
4079  }
4080 
4081  continue;
4082  }
4083  assert(consdata0->sorted);
4084 
4085  /* sort cons1 */
4086  consdataSort(consdata1);
4087  assert(consdata1->sorted);
4088 
4089  /* check whether
4090  * (a) one problem variable set is a subset of the other, or
4091  * (b) the problem variable sets are almost equal with only one variable in each constraint that is not
4092  * member of the other
4093  */
4094  aborted = FALSE;
4095  parity = (consdata0->rhs ^ consdata1->rhs);
4096  cons0hastwoothervars = FALSE;
4097  cons1hastwoothervars = FALSE;
4098  singlevar0 = NULL;
4099  singlevar1 = NULL;
4100  v0 = 0;
4101  v1 = 0;
4102  while( (v0 < consdata0->nvars || v1 < consdata1->nvars) && !aborted )
4103  {
4104  int cmp;
4105 
4106  assert(v0 <= consdata0->nvars);
4107  assert(v1 <= consdata1->nvars);
4108 
4109  if( v0 == consdata0->nvars )
4110  cmp = +1;
4111  else if( v1 == consdata1->nvars )
4112  cmp = -1;
4113  else
4114  cmp = SCIPvarCompareActiveAndNegated(consdata0->vars[v0], consdata1->vars[v1]);
4115 
4116  switch( cmp )
4117  {
4118  case -1:
4119  /* variable doesn't appear in cons1 */
4120  assert(v0 < consdata0->nvars);
4121  if( singlevar0 == NULL )
4122  {
4123  singlevar0 = consdata0->vars[v0];
4124  if( cons1hastwoothervars )
4125  aborted = TRUE;
4126  }
4127  else
4128  {
4129  cons0hastwoothervars = TRUE;
4130  if( singlevar1 != NULL )
4131  aborted = TRUE;
4132  }
4133  v0++;
4134  break;
4135 
4136  case +1:
4137  /* variable doesn't appear in cons0 */
4138  assert(v1 < consdata1->nvars);
4139  if( singlevar1 == NULL )
4140  {
4141  singlevar1 = consdata1->vars[v1];
4142  if( cons0hastwoothervars )
4143  aborted = TRUE;
4144  }
4145  else
4146  {
4147  cons1hastwoothervars = TRUE;
4148  if( singlevar0 != NULL )
4149  aborted = TRUE;
4150  }
4151  v1++;
4152  break;
4153 
4154  case 0:
4155  /* variable appears in both constraints */
4156  assert(v0 < consdata0->nvars);
4157  assert(v1 < consdata1->nvars);
4158  assert(SCIPvarGetProbvar(consdata0->vars[v0]) == SCIPvarGetProbvar(consdata1->vars[v1]));
4159  if( consdata0->vars[v0] != consdata1->vars[v1] )
4160  {
4161  assert(SCIPvarGetNegatedVar(consdata0->vars[v0]) == consdata1->vars[v1]);
4162  parity = !parity;
4163  }
4164  v0++;
4165  v1++;
4166  break;
4167 
4168  default:
4169  SCIPerrorMessage("invalid comparison result\n");
4170  SCIPABORT();
4171  return SCIP_INVALIDDATA; /*lint !e527*/
4172  }
4173  }
4174 
4175  /* check if a useful presolving is possible */
4176  if( (cons0hastwoothervars && singlevar1 != NULL) || (cons1hastwoothervars && singlevar0 != NULL) )
4177  continue;
4178 
4179  /* check if one problem variable set is a subset of the other */
4180  if( singlevar0 == NULL && singlevar1 == NULL )
4181  {
4182  /* both constraints are equal */
4183  if( !parity )
4184  {
4185  /* even parity: constraints are redundant */
4186  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> are redundant: delete <%s>\n",
4187  SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPconsGetName(cons1));
4188  SCIPdebugPrintCons(scip, cons0, NULL);
4189  SCIPdebugPrintCons(scip, cons1, NULL);
4190 
4191  /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4192  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4193  SCIP_CALL( SCIPdelCons(scip, cons1) );
4194  (*ndelconss)++;
4195 
4196  if( consdata1->intvar != NULL )
4197  {
4198  /* need to update integer variable, consider the following case:
4199  * c1: xor(x1, x2, x3) = 1 (intvar1 = y1)
4200  * c2: xor(x1, x2, x3) = 1 (intvar0 = NULL or intvar0 = y0)
4201  *
4202  * if intvar0 = NULL we have to assign intvar0 = y1. otherwise, we have to ensure that y1 = y0 holds.
4203  * if aggregation is allowed, we can aggregate both variables. otherwise, we have to add a linear
4204  * constraint y1 - y0 = 0.
4205  */
4206  if( consdata0->intvar == NULL )
4207  {
4208  SCIP_CALL( setIntvar(scip, cons0, consdata1->intvar) );
4209  }
4210  else
4211  {
4212  /* aggregate integer variables */
4213  SCIP_CALL( SCIPaggregateVars(scip, consdata1->intvar, consdata0->intvar, 1.0, -1.0, 0.0,
4214  &infeasible, &redundant, &aggregated) );
4215 
4216  *cutoff = *cutoff || infeasible;
4217 
4218  if( aggregated )
4219  {
4220  (*naggrvars)++;
4221  assert(SCIPvarIsActive(consdata0->intvar));
4222  }
4223  else
4224  {
4225  SCIP_CONS* newcons;
4226  char consname[SCIP_MAXSTRLEN];
4227  SCIP_VAR* newvars[2];
4228  SCIP_Real vals[2];
4229 
4230  newvars[0] = consdata1->intvar;
4231  vals[0] = 1.0;
4232  newvars[1] = consdata0->intvar;
4233  vals[1] = -1.0;
4234 
4235  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons1));
4236 
4237  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, newvars, vals, 0.0, 0.0,
4238  SCIPconsIsInitial(cons1), SCIPconsIsSeparated(cons1), TRUE, /*SCIPconsIsEnforced(cons),*/
4239  TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
4240  SCIPconsIsLocal(cons1), SCIPconsIsModifiable(cons1),
4241  SCIPconsIsDynamic(cons1), SCIPconsIsRemovable(cons1), SCIPconsIsStickingAtNode(cons1)) );
4242 
4243  SCIP_CALL( SCIPaddCons(scip, newcons) );
4244  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4245  ++(*naddconss);
4246  }
4247  }
4248  }
4249  }
4250  else
4251  {
4252  /* odd parity: constraints are contradicting */
4253  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> are contradicting\n",
4254  SCIPconsGetName(cons0), SCIPconsGetName(cons1));
4255  SCIPdebugPrintCons(scip, cons0, NULL);
4256  SCIPdebugPrintCons(scip, cons1, NULL);
4257  *cutoff = TRUE;
4258  }
4259  }
4260  else if( singlevar1 == NULL )
4261  {
4262  /* cons1 is a subset of cons0 */
4263  if( !cons0hastwoothervars )
4264  {
4265  /* only one additional variable in cons0: fix this variable according to the parity */
4266  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == <%s>\n",
4267  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity, SCIPvarGetName(singlevar0));
4268  SCIPdebugPrintCons(scip, cons0, NULL);
4269  SCIPdebugPrintCons(scip, cons1, NULL);
4270  SCIP_CALL( SCIPfixVar(scip, singlevar0, parity ? 1.0 : 0.0, &infeasible, &fixed) );
4271  *cutoff = *cutoff || infeasible;
4272  if ( fixed )
4273  (*nfixedvars)++;
4274 
4275  /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4276  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4277  SCIP_CALL( SCIPdelCons(scip, cons1) );
4278  (*ndelconss)++;
4279  }
4280  else
4281  {
4282  int v;
4283 
4284  /* more than one additional variable in cons0: add cons1 to cons0, thus eliminating the equal variables */
4285  SCIPdebugMsg(scip, "xor constraint <%s> is superset of <%s> with parity %u\n",
4286  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity);
4287  SCIPdebugPrintCons(scip, cons0, NULL);
4288  SCIPdebugPrintCons(scip, cons1, NULL);
4289  for( v = 0; v < consdata1->nvars; ++v )
4290  {
4291  SCIP_CALL( addCoef(scip, cons0, consdata1->vars[v]) );
4292  }
4293 
4294  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4295  assert(SCIPconsGetData(cons0) == consdata0);
4296  assert(consdata0->nvars >= 2); /* at least the two "other" variables should remain in the constraint */
4297  }
4298 
4299  if( *cutoff )
4300  return SCIP_OKAY;
4301 
4302  consdataSort(consdata0);
4303  assert(consdata0->sorted);
4304  }
4305  else if( singlevar0 == NULL )
4306  {
4307  /* cons0 is a subset of cons1 */
4308  if( !cons1hastwoothervars )
4309  {
4310  /* only one additional variable in cons1: fix this variable according to the parity */
4311  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == <%s>\n",
4312  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity, SCIPvarGetName(singlevar1));
4313  SCIPdebugPrintCons(scip, cons0, NULL);
4314  SCIPdebugPrintCons(scip, cons1, NULL);
4315  SCIP_CALL( SCIPfixVar(scip, singlevar1, parity ? 1.0 : 0.0, &infeasible, &fixed) );
4316  assert(infeasible || fixed);
4317  *cutoff = *cutoff || infeasible;
4318  (*nfixedvars)++;
4319 
4320  /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4321  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4322  SCIP_CALL( SCIPdelCons(scip, cons1) );
4323  (*ndelconss)++;
4324  }
4325  else
4326  {
4327  int v;
4328 
4329  /* more than one additional variable in cons1: add cons0 to cons1, thus eliminating the equal variables */
4330  SCIPdebugMsg(scip, "xor constraint <%s> is subset of <%s> with parity %u\n",
4331  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity);
4332  SCIPdebugPrintCons(scip, cons0, NULL);
4333  SCIPdebugPrintCons(scip, cons1, NULL);
4334  for( v = 0; v < consdata0->nvars; ++v )
4335  {
4336  SCIP_CALL( addCoef(scip, cons1, consdata0->vars[v]) );
4337  }
4338  SCIP_CALL( applyFixings(scip, cons1, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4339  assert(SCIPconsGetData(cons1) == consdata1);
4340  assert(consdata1->nvars >= 2); /* at least the two "other" variables should remain in the constraint */
4341 
4342  if( *cutoff )
4343  return SCIP_OKAY;
4344 
4345  consdataSort(consdata1);
4346  assert(consdata1->sorted);
4347  }
4348  }
4349  else
4350  {
4351  assert(!cons0hastwoothervars);
4352  assert(!cons1hastwoothervars);
4353 
4354  /* sum of constraints is parity == singlevar0 xor singlevar1: aggregate variables and delete cons1 */
4355  SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == xor(<%s>,<%s>)\n",
4356  SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity, SCIPvarGetName(singlevar0),
4357  SCIPvarGetName(singlevar1));
4358  if( !parity )
4359  {
4360  /* aggregate singlevar0 == singlevar1 */
4361  SCIP_CALL( SCIPaggregateVars(scip, singlevar1, singlevar0, 1.0, -1.0, 0.0,
4362  &infeasible, &redundant, &aggregated) );
4363  }
4364  else
4365  {
4366  /* aggregate singlevar0 == 1-singlevar1 */
4367  SCIP_CALL( SCIPaggregateVars(scip, singlevar1, singlevar0, 1.0, 1.0, 1.0,
4368  &infeasible, &redundant, &aggregated) );
4369  }
4370  assert(infeasible || redundant || SCIPdoNotAggr(scip));
4371 
4372  *cutoff = *cutoff || infeasible;
4373  if( aggregated )
4374  (*naggrvars)++;
4375 
4376  if( redundant )
4377  {
4378  /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4379  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4380  SCIP_CALL( SCIPdelCons(scip, cons1) );
4381  (*ndelconss)++;
4382 
4383  if( consdata1->intvar != NULL )
4384  {
4385  if( consdata0->intvar == NULL )
4386  {
4387  SCIP_CALL( setIntvar(scip, cons0, consdata0->intvar) );
4388  }
4389  else
4390  {
4391  /* aggregate integer variables */
4392  SCIP_CALL( SCIPaggregateVars(scip, consdata1->intvar, consdata0->intvar, 1.0, -1.0, 0.0,
4393  &infeasible, &redundant, &aggregated) );
4394 
4395  *cutoff = *cutoff || infeasible;
4396  if( aggregated )
4397  (*naggrvars)++;
4398  }
4399  }
4400  }
4401 
4402  if( !consdata0->sorted )
4403  consdataSort(consdata0);
4404  assert(consdata0->sorted);
4405 
4406 #if 0
4407  /* if aggregation in the core of SCIP is not changed we do not need to call applyFixing, this would be the correct
4408  * way
4409  */
4410  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
4411  * merge multiple entries of the same or negated variables
4412  */
4413  SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4414 
4415  if( *cutoff )
4416  return SCIP_OKAY;
4417 #endif
4418  }
4419  }
4420 
4421  return SCIP_OKAY;
4422 }
4423 
4424 /** creates and captures a xor constraint x_0 xor ... xor x_{k-1} = rhs with a given artificial integer variable for the
4425  * linear relaxation
4426  *
4427  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
4428  */
4429 static
4430 SCIP_RETCODE createConsXorIntvar(
4431  SCIP* scip, /**< SCIP data structure */
4432  SCIP_CONS** cons, /**< pointer to hold the created constraint */
4433  const char* name, /**< name of constraint */
4434  SCIP_Bool rhs, /**< right hand side of the constraint */
4435  int nvars, /**< number of operator variables in the constraint */
4436  SCIP_VAR** vars, /**< array with operator variables of constraint */
4437  SCIP_VAR* intvar, /**< artificial integer variable for linear relaxation */
4438  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
4439  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
4440  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
4441  * Usually set to TRUE. */
4442  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
4443  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4444  SCIP_Bool check, /**< should the constraint be checked for feasibility?
4445  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4446  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
4447  * Usually set to TRUE. */
4448  SCIP_Bool local, /**< is constraint only valid locally?
4449  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
4450  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
4451  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
4452  * adds coefficients to this constraint. */
4453  SCIP_Bool dynamic, /**< is constraint subject to aging?
4454  * Usually set to FALSE. Set to TRUE for own cuts which
4455  * are separated as constraints. */
4456  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
4457  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
4458  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
4459  * if it may be moved to a more global node?
4460  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
4461  )
4462 {
4463  SCIP_CONSHDLR* conshdlr;
4464  SCIP_CONSDATA* consdata;
4465 
4466  /* find the xor constraint handler */
4467  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
4468  if( conshdlr == NULL )
4469  {
4470  SCIPerrorMessage("xor constraint handler not found\n");
4471  return SCIP_PLUGINNOTFOUND;
4472  }
4473 
4474  /* create constraint data */
4475  SCIP_CALL( consdataCreate(scip, &consdata, rhs, nvars, vars, intvar) );
4476 
4477  /* create constraint */
4478  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
4479  local, modifiable, dynamic, removable, stickingatnode) );
4480 
4481  return SCIP_OKAY;
4482 }
4483 
4484 
4485 
4486 /*
4487  * Linear constraint upgrading
4488  */
4489 
4490 /** tries to upgrade a linear constraint into an xor constraint
4491  *
4492  * Assuming all variables are binary and have coefficients with an absolute value 1, except for an integer (or binary) variable
4493  * \f$z\f$ which has coefficient \f$a \in \{-2,2\}\f$ with absolute value 2 and appears only in this constraint,
4494  * we can transform:
4495  * \f[
4496  * \begin{array}{ll}
4497  * & -\sum_{i \in I} x_i + \sum_{j \in J} x_j + a \cdot z = r \\
4498  * \Leftrightarrow & \sum_{i \in I} \bar{x}_i + \sum_{j \in J} x_j + a \cdot z = r + |I| \\
4499  * \Leftrightarrow & \sum_{i \in I} \bar{x}_i + \sum_{j \in J} x_j - 2 \cdot y = (r + |I|) \text{ mod } 2,
4500  * \end{array}
4501  * \f]
4502  * where
4503  * \f[
4504  * y = \begin{cases}
4505  * \left\lfloor \frac{r + |I|}{2} \right\rfloor + z & \text{if }a = -2\\
4506  * \left\lfloor \frac{r + |I|}{2} \right\rfloor - z & \text{if }a = 2.
4507  * \end{cases}
4508  * \f]
4509  * 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
4510  * \frac{r + |I|}{2} \right\rfloor + \ell_z\f$ and \f$u_y = \left\lfloor \frac{r + |I|}{2} \right\rfloor + u_z\f$.
4511  *
4512  * 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
4513  * \frac{r + |I|}{2} \right\rfloor - \ell_z\f$.
4514  *
4515  * Then consider the resulting XOR-constraint
4516  * \f[
4517  * \bigoplus_{i \in I} \bar{x}_i \oplus \bigoplus_{j \in j} x_j = (r + |I|) \text{ mod } 2.
4518  * \f]
4519  * 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
4520  * transformed constraint, otherwise it is a relaxation because the bounds on the \f$y\f$-variable may disallow
4521  * too many (or too few) operators set to 1. Therefore, the XOR constraint handler verifies in this case that the linear
4522  * equation holds, ie., that the \f$y\f$-variable has the correct value.
4523  */
4524 static
4525 SCIP_DECL_LINCONSUPGD(linconsUpgdXor)
4526 { /*lint --e{715}*/
4527  assert( upgdcons != NULL );
4528  assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0 );
4529  assert( ! SCIPconsIsModifiable(cons) );
4530 
4531  /* check, if linear constraint can be upgraded to xor constraint */
4532  /* @todo also applicable if the integer variable has a coefficient different from 2, e.g. a coefficient like 0.5 then
4533  * we could generate a new integer variable aggregated to the old one, possibly the constraint was then
4534  * normalized and all binary variables have coefficients of 2.0, if the coefficient is 4 then we need holes ...
4535  */
4536  if( integral && nposcont + nnegcont == 0 && nposbin + nnegbin + nposimplbin + nnegimplbin >= nvars-1 && ncoeffspone + ncoeffsnone == nvars-1 && ncoeffspint + ncoeffsnint == 1 )
4537  {
4538  assert( ncoeffspfrac + ncoeffsnfrac == 0 );
4539 
4540  if ( SCIPisEQ(scip, lhs, rhs) && SCIPisIntegral(scip, lhs) )
4541  {
4542  SCIP_VAR** xorvars;
4543  SCIP_VAR* parityvar = NULL;
4544  SCIP_Bool postwo = FALSE;
4545  int cnt = 0;
4546  int j;
4547 
4548  SCIP_CALL( SCIPallocBufferArray(scip, &xorvars, nvars) );
4549 
4550  /* check parity of constraints */
4551  for( j = nvars - 1; j >= 0; --j )
4552  {
4553  if( SCIPisEQ(scip, REALABS(vals[j]), 2.0) )
4554  {
4555  parityvar = vars[j];
4556  postwo = (vals[j] > 0.0);
4557  }
4558  else if( !SCIPisEQ(scip, REALABS(vals[j]), 1.0) )
4559  break;
4560  else
4561  {
4562  /* exit if variable is not binary or implicit binary */
4563  if ( ! SCIPvarIsBinary(vars[j]) )
4564  {
4565  parityvar = NULL;
4566  break;
4567  }
4568 
4569  /* need negated variables for correct propagation to the integer variable */
4570  if( vals[j] < 0.0 )
4571  {
4572  SCIP_CALL( SCIPgetNegatedVar(scip, vars[j], &(xorvars[cnt])) );
4573  assert(xorvars[cnt] != NULL);
4574  }
4575  else
4576  xorvars[cnt] = vars[j];
4577  ++cnt;
4578  }
4579  }
4580 
4581  if( parityvar != NULL )
4582  {
4583  assert(cnt == nvars - 1);
4584 
4585  /* check whether parity variable is present only in this constraint */
4586  if ( SCIPvarGetNLocksDownType(parityvar, SCIP_LOCKTYPE_MODEL) <= 1
4587  && SCIPvarGetNLocksUpType(parityvar, SCIP_LOCKTYPE_MODEL) <= 1 )
4588  {
4589  SCIP_VAR* intvar;
4590  SCIP_Bool rhsparity;
4591  SCIP_Bool neednew;
4592  int intrhs;
4593 
4594  /* adjust the side, since we negated all binary variables with -1.0 as a coefficient */
4595  rhs += ncoeffsnone;
4596 
4597  intrhs = (int) SCIPfloor(scip, rhs);
4598  rhsparity = ((SCIP_Bool) (intrhs % 2)); /*lint !e571*/
4599 
4600  /* we need a new variable if the rhs is not 0 or 1 or if the coefficient was +2, since in these cases, we
4601  * need to aggregate the variables (flipping signs and/or shifting */
4602  if ( (intrhs != 1 && intrhs != 0) || postwo )
4603  neednew = TRUE;
4604  else
4605  neednew = FALSE;
4606 
4607  /* check if we can use the parity variable as integer variable of the XOR constraint or do we need to
4608  * create a new variable and aggregate */
4609  if( neednew )
4610  {
4611  char varname[SCIP_MAXSTRLEN];
4612  SCIP_Real lb;
4613  SCIP_Real ub;
4614  SCIP_Bool isbinary;
4615  SCIP_Bool infeasible;
4616  SCIP_Bool redundant;
4617  SCIP_Bool aggregated;
4618  int intrhshalfed;
4619 
4620  intrhshalfed = intrhs / 2;
4621 
4622  if( postwo )
4623  {
4624  lb = intrhshalfed - SCIPvarGetUbGlobal(parityvar);
4625  ub = intrhshalfed - SCIPvarGetLbGlobal(parityvar);
4626  }
4627  else
4628  {
4629  lb = intrhshalfed + SCIPvarGetLbGlobal(parityvar);
4630  ub = intrhshalfed + SCIPvarGetUbGlobal(parityvar);
4631  }
4632  assert(SCIPisFeasLE(scip, lb, ub));
4633  assert(SCIPisFeasIntegral(scip, lb));
4634  assert(SCIPisFeasIntegral(scip, ub));
4635 
4636  /* adjust bounds to be more integral */
4637  lb = SCIPfeasFloor(scip, lb);
4638  ub = SCIPfeasFloor(scip, ub);
4639 
4640  isbinary = (SCIPisZero(scip, lb) && SCIPisEQ(scip, ub, 1.0));
4641 
4642  /* something is wrong if parity variable is already binary, but artificial variable is not */
4643  if( SCIPvarIsBinary(parityvar) && !isbinary )
4644  {
4645  SCIPfreeBufferArray(scip, &xorvars);
4646  return SCIP_OKAY;
4647  }
4648 
4649  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_xor_upgr", SCIPvarGetName(parityvar));
4650  SCIP_CALL( SCIPcreateVar(scip, &intvar, varname, lb, ub, 0.0,
4651  isbinary ? SCIP_VARTYPE_BINARY : SCIP_VARTYPE_INTEGER,
4652  SCIPvarIsInitial(parityvar), SCIPvarIsRemovable(parityvar), NULL, NULL, NULL, NULL, NULL) );
4653  SCIP_CALL( SCIPaddVar(scip, intvar) );
4654 
4655  SCIPdebugMsg(scip, "created new variable for aggregation:");
4656  SCIPdebug( SCIPprintVar(scip, intvar, NULL) );
4657 
4658  SCIP_CALL( SCIPaggregateVars(scip, parityvar, intvar, 1.0, postwo ? 1.0 : -1.0,
4659  (SCIP_Real) (postwo ? intrhshalfed : -intrhshalfed), &infeasible, &redundant, &aggregated) );
4660  assert(!infeasible);
4661 
4662  /* maybe aggregation was forbidden, than we cannot upgrade this constraint */
4663  if( !aggregated )
4664  {
4665  SCIPfreeBufferArray(scip, &xorvars);
4666  return SCIP_OKAY;
4667  }
4668 
4669  assert(redundant);
4670  assert(SCIPvarIsActive(intvar));
4671 
4672 #ifdef SCIP_DEBUG
4673  if( SCIPvarGetStatus(parityvar) == SCIP_VARSTATUS_AGGREGATED )
4674  {
4675  SCIPdebugMsg(scip, "aggregated: <%s> = %g * <%s> + %g\n", SCIPvarGetName(parityvar),
4676  SCIPvarGetAggrScalar(parityvar), SCIPvarGetName(SCIPvarGetAggrVar(parityvar)),
4677  SCIPvarGetAggrConstant(parityvar));
4678  }
4679  else
4680  {
4681  assert( SCIPvarGetStatus(parityvar) == SCIP_VARSTATUS_NEGATED );
4682  SCIPdebugMsg(scip, "negated: <%s> = 1 - <%s>\n", SCIPvarGetName(parityvar),
4683  SCIPvarGetName(SCIPvarGetNegatedVar(parityvar)));
4684  }
4685 #endif
4686  }
4687  else
4688  intvar = parityvar;
4689 
4690  assert(intvar != NULL);
4691 
4692  SCIP_CALL( createConsXorIntvar(scip, upgdcons, SCIPconsGetName(cons), rhsparity, nvars - 1, xorvars, intvar,
4693  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
4694  SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
4695  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
4696  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
4697 
4698  SCIPdebugMsg(scip, "upgraded constraint <%s> to XOR constraint:\n", SCIPconsGetName(cons));
4699  SCIPdebugPrintCons(scip, *upgdcons, NULL);
4700 
4701  if( neednew )
4702  {
4703  assert(intvar != parityvar);
4704  SCIP_CALL( SCIPreleaseVar(scip, &intvar) );
4705  }
4706  }
4707  }
4708 
4709  SCIPfreeBufferArray(scip, &xorvars);
4710  }
4711  }
4712 
4713  return SCIP_OKAY;
4714 }
4715 
4716 
4717 /*
4718  * Callback methods of constraint handler
4719  */
4720 
4721 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
4722 static
4723 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyXor)
4724 { /*lint --e{715}*/
4725  assert(scip != NULL);
4726  assert(conshdlr != NULL);
4727  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4728 
4729  /* call inclusion method of constraint handler */
4730  SCIP_CALL( SCIPincludeConshdlrXor(scip) );
4731 
4732  *valid = TRUE;
4733 
4734  return SCIP_OKAY;
4735 }
4736 
4737 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
4738 static
4739 SCIP_DECL_CONSFREE(consFreeXor)
4740 { /*lint --e{715}*/
4741  SCIP_CONSHDLRDATA* conshdlrdata;
4742 
4743  /* free constraint handler data */
4744  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4745  assert(conshdlrdata != NULL);
4746 
4747  conshdlrdataFree(scip, &conshdlrdata);
4748 
4749  SCIPconshdlrSetData(conshdlr, NULL);
4750 
4751  return SCIP_OKAY;
4752 }
4753 
4754 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4755 static
4756 SCIP_DECL_CONSEXITSOL(consExitsolXor)
4757 { /*lint --e{715}*/
4758  SCIP_CONSDATA* consdata;
4759  int c;
4760 
4761  /* release and free the rows of all constraints */
4762  for( c = 0; c < nconss; ++c )
4763  {
4764  consdata = SCIPconsGetData(conss[c]);
4765  SCIP_CALL( consdataFreeRows(scip, consdata) );
4766  }
4767 
4768  return SCIP_OKAY;
4769 }
4770 
4771 
4772 /** frees specific constraint data */
4773 static
4774 SCIP_DECL_CONSDELETE(consDeleteXor)
4775 { /*lint --e{715}*/
4776  SCIP_CONSHDLRDATA* conshdlrdata;
4777 
4778  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4779  assert(conshdlrdata != NULL);
4780 
4781  if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_INITPRESOLVE )
4782  {
4783  int v;
4784 
4785  for( v = (*consdata)->nvars - 1; v >= 0; --v )
4786  {
4787  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4788  (SCIP_EVENTDATA*)(*consdata), -1) );
4789  }
4790  }
4791 
4792  SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4793 
4794  return SCIP_OKAY;
4795 }
4796 
4797 
4798 /** transforms constraint data into data belonging to the transformed problem */
4799 static
4800 SCIP_DECL_CONSTRANS(consTransXor)
4801 { /*lint --e{715}*/
4802  SCIP_CONSDATA* sourcedata;
4803  SCIP_CONSDATA* targetdata;
4804 
4805  sourcedata = SCIPconsGetData(sourcecons);
4806  assert(sourcedata != NULL);
4807  assert(sourcedata->nvars >= 1);
4808  assert(sourcedata->vars != NULL);
4809 
4810  /* create target constraint data */
4811  SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->rhs, sourcedata->nvars, sourcedata->vars, sourcedata->intvar) );
4812 
4813  /* create target constraint */
4814  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4815  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4816  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4817  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4818  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4819 
4820  return SCIP_OKAY;
4821 }
4822 
4823 
4824 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4825 static
4826 SCIP_DECL_CONSINITLP(consInitlpXor)
4827 { /*lint --e{715}*/
4828  int i;
4829 
4830  assert(infeasible != NULL);
4831 
4832  *infeasible = FALSE;
4833 
4834  for( i = 0; i < nconss && !(*infeasible); i++ )
4835  {
4836  assert(SCIPconsIsInitial(conss[i]));
4837  SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4838  }
4839 
4840  return SCIP_OKAY;
4841 }
4842 
4843 
4844 /** separation method of constraint handler for LP solutions */
4845 static
4846 SCIP_DECL_CONSSEPALP(consSepalpXor)
4847 { /*lint --e{715}*/
4848  SCIP_CONSHDLRDATA* conshdlrdata;
4849  SCIP_Bool separated;
4850  SCIP_Bool cutoff;
4851  int c;
4852 
4853  *result = SCIP_DIDNOTFIND;
4854 
4855  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4856  assert( conshdlrdata != NULL );
4857 
4858  /* separate all useful constraints */
4859  for( c = 0; c < nusefulconss; ++c )
4860  {
4861  SCIP_CALL( separateCons(scip, conss[c], NULL, conshdlrdata->separateparity, &separated, &cutoff) );
4862  if ( cutoff )
4863  *result = SCIP_CUTOFF;
4864  else if ( separated )
4865  *result = SCIP_SEPARATED;
4866  }
4867 
4868  /* combine constraints to get more cuts */
4869  /**@todo combine constraints to get further cuts */
4870 
4871  return SCIP_OKAY;
4872 }
4873 
4874 
4875 /** separation method of constraint handler for arbitrary primal solutions */
4876 static
4877 SCIP_DECL_CONSSEPASOL(consSepasolXor)
4878 { /*lint --e{715}*/
4879  SCIP_CONSHDLRDATA* conshdlrdata;
4880  SCIP_Bool separated;
4881  SCIP_Bool cutoff;
4882  int c;
4883 
4884  *result = SCIP_DIDNOTFIND;
4885 
4886  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4887  assert( conshdlrdata != NULL );
4888 
4889  /* separate all useful constraints */
4890  for( c = 0; c < nusefulconss; ++c )
4891  {
4892  SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->separateparity, &separated, &cutoff) );
4893  if ( cutoff )
4894  *result = SCIP_CUTOFF;
4895  else if ( separated )
4896  *result = SCIP_SEPARATED;
4897  }
4898 
4899  /* combine constraints to get more cuts */
4900  /**@todo combine constraints to get further cuts */
4901 
4902  return SCIP_OKAY;
4903 }
4904 
4905 
4906 /** constraint enforcing method of constraint handler for LP solutions */
4907 static
4908 SCIP_DECL_CONSENFOLP(consEnfolpXor)
4909 { /*lint --e{715}*/
4910  SCIP_CONSHDLRDATA* conshdlrdata;
4911  SCIP_Bool violated;
4912  SCIP_Bool cutoff;
4913  int i;
4914 
4915  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4916  assert( conshdlrdata != NULL );
4917 
4918  /* method is called only for integral solutions, because the enforcing priority is negative */
4919  for( i = 0; i < nconss; i++ )
4920  {
4921  SCIP_CALL( checkCons(scip, conss[i], NULL, FALSE, &violated) );
4922  if( violated )
4923  {
4924  SCIP_Bool separated;
4925 
4926  SCIP_CALL( separateCons(scip, conss[i], NULL, conshdlrdata->separateparity, &separated, &cutoff) );
4927  if ( cutoff )
4928  *result = SCIP_CUTOFF;
4929  else
4930  {
4931  assert(separated); /* because the solution is integral, the separation always finds a cut */
4932  *result = SCIP_SEPARATED;
4933  }
4934  return SCIP_OKAY;
4935  }
4936  }
4937  *result = SCIP_FEASIBLE;
4938 
4939  return SCIP_OKAY;
4940 }
4941 
4942 
4943 /** constraint enforcing method of constraint handler for relaxation solutions */
4944 static
4945 SCIP_DECL_CONSENFORELAX(consEnforelaxXor)
4946 { /*lint --e{715}*/
4947  SCIP_CONSHDLRDATA* conshdlrdata;
4948  SCIP_Bool violated;
4949  SCIP_Bool cutoff;
4950  int i;
4951 
4952  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4953  assert( conshdlrdata != NULL );
4954 
4955  /* method is called only for integral solutions, because the enforcing priority is negative */
4956  for( i = 0; i < nconss; i++ )
4957  {
4958  SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, &violated) );
4959  if( violated )
4960  {
4961  SCIP_Bool separated;
4962 
4963  SCIP_CALL( separateCons(scip, conss[i], sol, conshdlrdata->separateparity, &separated, &cutoff) );
4964  if ( cutoff )
4965  *result = SCIP_CUTOFF;
4966  else
4967  {
4968  assert(separated); /* because the solution is integral, the separation always finds a cut */
4969  *result = SCIP_SEPARATED;
4970  }
4971  return SCIP_OKAY;
4972  }
4973  }
4974  *result = SCIP_FEASIBLE;
4975 
4976  return SCIP_OKAY;
4977 }
4978 
4979 
4980 /** constraint enforcing method of constraint handler for pseudo solutions */
4981 static
4982 SCIP_DECL_CONSENFOPS(consEnfopsXor)
4983 { /*lint --e{715}*/
4984  SCIP_Bool violated;
4985  int i;
4986 
4987  /* method is called only for integral solutions, because the enforcing priority is negative */
4988  for( i = 0; i < nconss; i++ )
4989  {
4990  SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, &violated) );
4991  if( violated )
4992  {
4993  *result = SCIP_INFEASIBLE;
4994  return SCIP_OKAY;
4995  }
4996  }
4997  *result = SCIP_FEASIBLE;
4998 
4999  return SCIP_OKAY;
5000 }
5001 
5002 
5003 /** feasibility check method of constraint handler for integral solutions */
5004 static
5005 SCIP_DECL_CONSCHECK(consCheckXor)
5006 { /*lint --e{715}*/
5007  SCIP_Bool violated;
5008  int i;
5009 
5010  *result = SCIP_FEASIBLE;
5011 
5012  /* method is called only for integral solutions, because the enforcing priority is negative */
5013  for( i = 0; i < nconss && (*result == SCIP_FEASIBLE || completely); i++ )
5014  {
5015  SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, &violated) );
5016  if( violated )
5017  {
5018  *result = SCIP_INFEASIBLE;
5019 
5020  if( printreason )
5021  {
5022  int v;
5023  int sum = 0;
5024  SCIP_CONSDATA* consdata;
5025 
5026  consdata = SCIPconsGetData(conss[i]);
5027  assert( consdata != NULL );
5028 
5029  SCIP_CALL( SCIPprintCons(scip, conss[i], NULL) );
5030 
5031  for( v = 0; v < consdata->nvars; ++v )
5032  {
5033  if( SCIPgetSolVal(scip, sol, consdata->vars[v]) > 0.5 )
5034  sum++;
5035  }
5036 
5037  if( consdata->intvar != NULL )
5038  {
5039  SCIPinfoMessage(scip, NULL, ";\nviolation: %d operands are set to TRUE but integer variable has value of %g\n", sum, SCIPgetSolVal(scip, sol, consdata->intvar));
5040  }
5041  else
5042  {
5043  SCIPinfoMessage(scip, NULL, ";\nviolation: %d operands are set to TRUE\n", sum );
5044  }
5045  }
5046  }
5047  }
5048 
5049  return SCIP_OKAY;
5050 }
5051 
5052 
5053 /** domain propagation method of constraint handler */
5054 static
5055 SCIP_DECL_CONSPROP(consPropXor)
5056 { /*lint --e{715}*/
5057  SCIP_CONSHDLRDATA* conshdlrdata;
5058  SCIP_Bool cutoff;
5059  int nfixedvars;
5060  int nchgbds;
5061  int c;
5062 
5063  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5064  assert(conshdlrdata != NULL);
5065 
5066  cutoff = FALSE;
5067  nfixedvars = 0;
5068  nchgbds = 0;
5069 
5070  /* propagate all useful constraints */
5071  for( c = 0; c < nusefulconss && !cutoff; ++c )
5072  {
5073  SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars, &nchgbds) );
5074  }
5075 
5076  /* return the correct result */
5077  if( cutoff )
5078  *result = SCIP_CUTOFF;
5079  else if( nfixedvars > 0 || nchgbds > 0 )
5080  *result = SCIP_REDUCEDDOM;
5081  else
5082  {
5083  *result = SCIP_DIDNOTFIND;
5084  if ( ! SCIPinProbing(scip) )
5085  {
5086  int depth;
5087  int freq;
5088 
5089  depth = SCIPgetDepth(scip);
5090  freq = conshdlrdata->gausspropfreq;
5091  if ( (depth == 0 && freq == 0) || (freq > 0 && depth % freq == 0) )
5092  {
5093  /* take useful constraints only - might improve success rate to take all */
5094  SCIP_CALL( checkSystemGF2(scip, conss, nusefulconss, NULL, result) );
5095  }
5096  }
5097  }
5098 
5099  return SCIP_OKAY;
5100 }
5101 
5102 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
5103 static
5104 SCIP_DECL_CONSINITPRE(consInitpreXor)
5105 { /*lint --e{715}*/
5106  SCIP_CONSHDLRDATA* conshdlrdata;
5107  SCIP_CONSDATA* consdata;
5108  int c;
5109  int v;
5110 
5111  assert(conshdlr != NULL);
5112  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5113  assert(conshdlrdata != NULL);
5114 
5115  /* catch all variable event for deleted variables, which is only used in presolving */
5116  for( c = nconss - 1; c >= 0; --c )
5117  {
5118  consdata = SCIPconsGetData(conss[c]);
5119  assert(consdata != NULL);
5120 
5121  for( v = consdata->nvars - 1; v >= 0; --v )
5122  {
5123  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
5124  (SCIP_EVENTDATA*)consdata, NULL) );
5125  }
5126  }
5127 
5128  return SCIP_OKAY;
5129 }
5130 
5131 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
5132 static
5133 SCIP_DECL_CONSEXITPRE(consExitpreXor)
5134 { /*lint --e{715}*/
5135  SCIP_CONSHDLRDATA* conshdlrdata;
5136  SCIP_CONSDATA* consdata;
5137  int c;
5138  int v;
5139 
5140  assert(conshdlr != NULL);
5141  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5142  assert(conshdlrdata != NULL);
5143 
5144  /* drop all variable event for deleted variables, which was only used in presolving */
5145  for( c = 0; c < nconss; ++c )
5146  {
5147  consdata = SCIPconsGetData(conss[c]);
5148  assert(consdata != NULL);
5149 
5150  if( !SCIPconsIsDeleted(conss[c]) )
5151  {
5152  for( v = 0; v < consdata->nvars; ++v )
5153  {
5154  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
5155  (SCIP_EVENTDATA*)consdata, -1) );
5156  }
5157  }
5158  }
5159 
5160  return SCIP_OKAY;
5161 }
5162 
5163 /** presolving method of constraint handler */
5164 static
5165 SCIP_DECL_CONSPRESOL(consPresolXor)
5166 { /*lint --e{715}*/
5167  SCIP_CONSHDLRDATA* conshdlrdata;
5168  SCIP_CONS* cons;
5169  SCIP_CONSDATA* consdata;
5170  SCIP_Bool cutoff;
5171  SCIP_Bool redundant;
5172  SCIP_Bool aggregated;
5173  int oldnfixedvars;
5174  int oldnchgbds;
5175  int oldnaggrvars;
5176  int oldndelconss;
5177  int oldnchgcoefs;
5178  int firstchange;
5179  int c;
5180 
5181  assert(result != NULL);
5182 
5183  oldnfixedvars = *nfixedvars;
5184  oldnchgbds = *nchgbds;
5185  oldnaggrvars = *naggrvars;
5186  oldndelconss = *ndelconss;
5187  oldnchgcoefs = *nchgcoefs;
5188 
5189  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5190  assert(conshdlrdata != NULL);
5191 
5192  /* process constraints */
5193  cutoff = FALSE;
5194  firstchange = INT_MAX;
5195  for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
5196  {
5197  cons = conss[c];
5198  assert(cons != NULL);
5199  consdata = SCIPconsGetData(cons);
5200  assert(consdata != NULL);
5201 
5202  /* force presolving the constraint in the initial round */
5203  if( nrounds == 0 )
5204  consdata->propagated = FALSE;
5205 
5206  /* remember the first changed constraint to begin the next aggregation round with */
5207  if( firstchange == INT_MAX && consdata->changed )
5208  firstchange = c;
5209 
5210  /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
5211  * merge multiple entries of the same or negated variables
5212  */
5213  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, &cutoff) );
5214 
5215  if( cutoff )
5216  break;
5217 
5218  /* propagate constraint */
5219  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nchgbds) );
5220 
5221  if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
5222  {
5223  assert(consdata->nvars >= 2); /* otherwise, propagateCons() has deleted the constraint */
5224 
5225  /* if only two variables are left, both have to be equal or opposite, depending on the rhs */
5226  if( consdata->nvars == 2 )
5227  {
5228  SCIPdebugMsg(scip, "xor constraint <%s> has only two unfixed variables, rhs=%u\n",
5229  SCIPconsGetName(cons), consdata->rhs);
5230 
5231  assert(consdata->vars != NULL);
5232  assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
5233  assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
5234  assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->vars[1]), 0.0));
5235  assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(consdata->vars[1]), 1.0));
5236 
5237  if( !consdata->rhs )
5238  {
5239  /* aggregate variables: vars[0] - vars[1] == 0 */
5240  SCIPdebugMsg(scip, " -> aggregate <%s> == <%s>\n", SCIPvarGetName(consdata->vars[0]),
5241  SCIPvarGetName(consdata->vars[1]));
5242  SCIP_CALL( SCIPaggregateVars(scip, consdata->vars[0], consdata->vars[1], 1.0, -1.0, 0.0,
5243  &cutoff, &redundant, &aggregated) );
5244  }
5245  else
5246  {
5247  /* aggregate variables: vars[0] + vars[1] == 1 */
5248  SCIPdebugMsg(scip, " -> aggregate <%s> == 1 - <%s>\n", SCIPvarGetName(consdata->vars[0]),
5249  SCIPvarGetName(consdata->vars[1]));
5250  SCIP_CALL( SCIPaggregateVars(scip, consdata->vars[0], consdata->vars[1], 1.0, 1.0, 1.0,
5251  &cutoff, &redundant, &aggregated) );
5252  }
5253  assert(redundant || SCIPdoNotAggr(scip));
5254 
5255  if( aggregated )
5256  {
5257  assert(redundant);
5258  (*naggrvars)++;
5259  }
5260 
5261  /* the constraint can be deleted if the intvar is fixed or NULL */
5262  if( redundant )
5263  {
5264  SCIP_Bool fixedintvar;
5265 
5266  fixedintvar = consdata->intvar == NULL ? TRUE : SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->intvar), SCIPvarGetUbGlobal(consdata->intvar));
5267 
5268  if( fixedintvar )
5269  {
5270  /* if the integer variable is an original variable, i.e.,
5271  * consdata->deleteintvar == FALSE then the following
5272  * must hold:
5273  *
5274  * if consdata->rhs == 1 then the integer variable needs
5275  * to be fixed to zero, otherwise the constraint is
5276  * infeasible,
5277  *
5278  * if consdata->rhs == 0 then the integer variable needs
5279  * to be aggregated to one of the binary variables
5280  */
5281  assert(consdata->deleteintvar || (consdata->rhs && SCIPvarGetLbGlobal(consdata->intvar) < 0.5));
5282 
5283  /* delete constraint */
5284  SCIP_CALL( SCIPdelCons(scip, cons) );
5285  (*ndelconss)++;
5286  }
5287  }
5288  }
5289  else if( (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
5290  {
5291  /* try to use clique information to upgrade the constraint to a set-partitioning constraint or fix
5292  * variables
5293  */
5294  SCIP_CALL( cliquePresolve(scip, cons, nfixedvars, nchgcoefs, ndelconss, naddconss, &cutoff) );
5295  }
5296  }
5297  }
5298 
5299  /* process pairs of constraints: check them for equal operands;
5300  * only apply this expensive procedure, if the single constraint preprocessing did not find any reductions
5301  */
5302  if( !cutoff && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 && SCIPisPresolveFinished(scip) )
5303  {
5304  if( firstchange < nconss && conshdlrdata->presolusehashing )
5305  {
5306  /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
5307  SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, nchgcoefs,
5308  nfixedvars, naggrvars, ndelconss, naddconss, &cutoff) );
5309  }
5310  if( conshdlrdata->presolpairwise )
5311  {
5312  SCIP_Longint npaircomparisons;
5313  int lastndelconss;
5314  npaircomparisons = 0;
5315  lastndelconss = *ndelconss;
5316 
5317  for( c = firstchange; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
5318  {
5319  if( SCIPconsIsActive(conss[c]) && !SCIPconsIsModifiable(conss[c]) )
5320  {
5321  npaircomparisons += (SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange);
5322 
5323  SCIP_CALL( preprocessConstraintPairs(scip, conss, firstchange, c,
5324  &cutoff, nfixedvars, naggrvars, ndelconss, naddconss, nchgcoefs) );
5325 
5326  if( npaircomparisons > NMINCOMPARISONS )
5327  {
5328  if( ((SCIP_Real) (*ndelconss - lastndelconss)) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
5329  break;
5330  lastndelconss = *ndelconss;
5331  npaircomparisons = 0;
5332  }
5333  }
5334  }
5335  }
5336  }
5337 
5338  /* return the correct result code */
5339  if( cutoff )
5340  *result = SCIP_CUTOFF;
5341  else if( *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds || *naggrvars > oldnaggrvars
5342  || *ndelconss > oldndelconss || *nchgcoefs > oldnchgcoefs )
5343  *result = SCIP_SUCCESS;
5344  else
5345  *result = SCIP_DIDNOTFIND;
5346 
5347  /* add extended formulation at the end of presolving if required */
5348  if ( conshdlrdata->addextendedform && *result == SCIP_DIDNOTFIND && SCIPisPresolveFinished(scip) )
5349  {
5350  for (c = 0; c < nconss && ! SCIPisStopped(scip); ++c)
5351  {
5352  int naddedconss = 0;
5353 
5354  cons = conss[c];
5355  assert(cons != NULL);
5356  consdata = SCIPconsGetData(cons);
5357  assert(consdata != NULL);
5358 
5359  if ( consdata->extvars != NULL )
5360  break;
5361 
5362  if ( conshdlrdata->addflowextended )
5363  {
5364  SCIP_CALL( addExtendedFlowFormulation(scip, cons, naggrvars, &naddedconss) );
5365  }
5366  else
5367  {
5368  SCIP_CALL( addExtendedAsymmetricFormulation(scip, cons, naggrvars, &naddedconss) );
5369  }
5370  (*naddconss) += naddedconss;
5371  }
5372  }
5373 
5374  return SCIP_OKAY;
5375 }
5376 
5377 
5378 /** propagation conflict resolving method of constraint handler */
5379 static
5380 SCIP_DECL_CONSRESPROP(consRespropXor)
5381 { /*lint --e{715}*/
5382  SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
5383 
5384  return SCIP_OKAY;
5385 }
5386 
5387 
5388 /** variable rounding lock method of constraint handler */
5389 static
5390 SCIP_DECL_CONSLOCK(consLockXor)
5391 { /*lint --e{715}*/
5392  SCIP_CONSDATA* consdata;
5393  int i;
5394 
5395  assert(locktype == SCIP_LOCKTYPE_MODEL);
5396 
5397  consdata = SCIPconsGetData(cons);
5398  assert(consdata != NULL);
5399 
5400  /* external variables */
5401  for( i = 0; i < consdata->nvars; ++i )
5402  {
5403  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
5404  }
5405 
5406  /* internal variable */
5407  if( consdata->intvar != NULL )
5408  {
5409  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->intvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
5410  }
5411 
5412  return SCIP_OKAY;
5413 }
5414 
5415 
5416 /** constraint display method of constraint handler */
5417 static
5418 SCIP_DECL_CONSPRINT(consPrintXor)
5419 { /*lint --e{715}*/
5420  assert( scip != NULL );
5421  assert( conshdlr != NULL );
5422  assert( cons != NULL );
5423 
5424  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file, FALSE) );
5425 
5426  return SCIP_OKAY;
5427 }
5428 
5429 /** constraint copying method of constraint handler */
5430 static
5431 SCIP_DECL_CONSCOPY(consCopyXor)
5432 { /*lint --e{715}*/
5433  SCIP_CONSDATA* sourceconsdata;
5434  SCIP_VAR** sourcevars;
5435  SCIP_VAR** targetvars;
5436  SCIP_VAR* intvar;
5437  SCIP_VAR* targetintvar;
5438  const char* consname;
5439  int nvars;
5440  int v;
5441 
5442  assert(scip != NULL);
5443  assert(sourcescip != NULL);
5444  assert(sourcecons != NULL);
5445 
5446  (*valid) = TRUE;
5447 
5448  sourceconsdata = SCIPconsGetData(sourcecons);
5449  assert(sourceconsdata != NULL);
5450 
5451  /* get variables and coefficients of the source constraint */
5452  sourcevars = sourceconsdata->vars;
5453  nvars = sourceconsdata->nvars;
5454  intvar = sourceconsdata->intvar;
5455  targetintvar = NULL;
5456 
5457  if( name != NULL )
5458  consname = name;
5459  else
5460  consname = SCIPconsGetName(sourcecons);
5461 
5462  if( nvars == 0 )
5463  {
5464  if( intvar != NULL )
5465  {
5466  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, intvar, &targetintvar, varmap, consmap, global, valid) );
5467  assert(!(*valid) || targetintvar != NULL);
5468 
5469  if( targetintvar != NULL )
5470  {
5471  SCIPdebugMsg(scip, "Copied integral variable <%s> (bounds: [%g,%g])\n", SCIPvarGetName(targetintvar),
5472  global ? SCIPvarGetLbGlobal(intvar) : SCIPvarGetLbLocal(intvar),
5473  global ? SCIPvarGetUbGlobal(intvar) : SCIPvarGetUbLocal(intvar));
5474  }
5475  }
5476 
5477  if( *valid )
5478  {
5479  SCIP_CALL( createConsXorIntvar(scip, cons, consname, SCIPgetRhsXor(sourcescip, sourcecons), 0, NULL,
5480  targetintvar, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable,
5481  stickingatnode) );
5482  }
5483 
5484  return SCIP_OKAY;
5485  }
5486 
5487  /* duplicate variable array */
5488  SCIP_CALL( SCIPallocBufferArray(scip, &targetvars, nvars) );
5489 
5490  /* map variables of the source constraint to variables of the target SCIP */
5491  for( v = 0; v < nvars && *valid; ++v )
5492  {
5493  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &targetvars[v], varmap, consmap, global, valid) );
5494  assert(!(*valid) || targetvars[v] != NULL);
5495  }
5496 
5497  /* map artificial relaxation variable of the source constraint to variable of the target SCIP */
5498  if( *valid && intvar != NULL )
5499  {
5500  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, intvar, &targetintvar, varmap, consmap, global, valid) );
5501  assert(!(*valid) || targetintvar != NULL);
5502 
5503  SCIPdebugMsg(scip, "Copied integral variable <%s> (bounds: [%g,%g])\n", SCIPvarGetName(targetintvar),
5504  global ? SCIPvarGetLbGlobal(intvar) : SCIPvarGetLbLocal(intvar),
5505  global ? SCIPvarGetUbGlobal(intvar) : SCIPvarGetUbLocal(intvar));
5506  }
5507 
5508  /* only create the target constraints, if all variables could be copied */
5509  if( *valid )
5510  {
5511  SCIP_CALL( createConsXorIntvar(scip, cons, consname, SCIPgetRhsXor(sourcescip, sourcecons), nvars, targetvars,
5512  targetintvar, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable,
5513  stickingatnode) );
5514  }
5515 
5516  /* free buffer array */
5517  SCIPfreeBufferArray(scip, &targetvars);
5518 
5519  return SCIP_OKAY;
5520 }
5521 
5522 
5523 /** constraint parsing method of constraint handler */
5524 static
5525 SCIP_DECL_CONSPARSE(consParseXor)
5526 { /*lint --e{715}*/
5527  SCIP_VAR** vars;
5528  char* endptr;
5529  int requiredsize;
5530  int varssize;
5531  int nvars;
5532 
5533  SCIPdebugMsg(scip, "parse <%s> as xor constraint\n", str);
5534 
5535  varssize = 100;
5536  nvars = 0;
5537 
5538  /* allocate buffer array for variables */
5539  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
5540 
5541  /* parse string */
5542  SCIP_CALL( SCIPparseVarsList(scip, str, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
5543 
5544  if( *success )
5545  {
5546  SCIP_Real rhs;
5547 
5548  /* check if the size of the variable array was big enough */
5549  if( varssize < requiredsize )
5550  {
5551  /* reallocate memory */
5552  varssize = requiredsize;
5553  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
5554 
5555  /* parse string again with the correct size of the variable array */
5556  SCIP_CALL( SCIPparseVarsList(scip, str, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
5557  }
5558 
5559  assert(*success);
5560  assert(varssize >= requiredsize);
5561 
5562  SCIPdebugMsg(scip, "successfully parsed %d variables\n", nvars);
5563 
5564  str = endptr;
5565 
5566  /* search for the equal symbol */
5567  while( *str != '=' && *str != '\0' )
5568  str++;
5569 
5570  /* if the string end has been reached without finding the '=' */
5571  if ( *str == '\0' )
5572  {
5573  SCIPerrorMessage("Could not find terminating '='.\n");
5574  *success = FALSE;
5575  }
5576  else
5577  {
5578  /* skip '=' character */
5579  ++str;
5580 
5581  if( SCIPstrToRealValue(str, &rhs, &endptr) )
5582  {
5583  SCIP_VAR* intvar = NULL;
5584 
5585  assert(SCIPisZero(scip, rhs) || SCIPisEQ(scip, rhs, 1.0));
5586 
5587  str = endptr;
5588 
5589  /* skip white spaces */
5590  while( *str == ' ' || *str == '\t' )
5591  str++;
5592 
5593  /* check for integer variable, should look like (intvar = var) */
5594  if( *str == '(' )
5595  {
5596  str++;
5597  while( *str != '=' && *str != '\0' )
5598  str++;
5599 
5600  if( *str != '=' )
5601  {
5602  SCIPerrorMessage("Parsing integer variable of XOR constraint\n");
5603  *success = FALSE;
5604  goto TERMINATE;
5605  }
5606 
5607  str++;
5608  /* skip white spaces */
5609  while( *str == ' ' || *str == '\t' )
5610  str++;
5611 
5612  /* parse variable name */
5613  SCIP_CALL( SCIPparseVarName(scip, str, &intvar, &endptr) );
5614 
5615  if( intvar == NULL )
5616  {
5617  SCIPdebugMsg(scip, "variable with name <%s> does not exist\n", SCIPvarGetName(intvar));
5618  (*success) = FALSE;
5619  goto TERMINATE;
5620  }
5621  str = endptr;
5622 
5623  /* skip last ')' */
5624  while( *str != ')' && *str != '\0' )
5625  str++;
5626  }
5627 
5628  if( intvar != NULL )
5629  {
5630  /* create or constraint */
5631  SCIP_CALL( createConsXorIntvar(scip, cons, name, (rhs > 0.5 ? TRUE : FALSE), nvars, vars, intvar,
5632  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5633  }
5634  else
5635  {
5636  /* create or constraint */
5637  SCIP_CALL( SCIPcreateConsXor(scip, cons, name, (rhs > 0.5 ? TRUE : FALSE), nvars, vars,
5638  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5639  }
5640 
5641  SCIPdebugPrintCons(scip, *cons, NULL);
5642  }
5643  else
5644  *success = FALSE;
5645  }
5646  }
5647 
5648  TERMINATE:
5649  /* free variable buffer */
5650  SCIPfreeBufferArray(scip, &vars);
5651 
5652  return SCIP_OKAY;
5653 }
5654 
5655 /** constraint method of constraint handler which returns the variables (if possible) */
5656 static
5657 SCIP_DECL_CONSGETVARS(consGetVarsXor)
5658 { /*lint --e{715}*/
5659  SCIP_CONSDATA* consdata;
5660  int nintvar = 0;
5661  int cnt;
5662  int j;
5663 
5664  consdata = SCIPconsGetData(cons);
5665  assert(consdata != NULL);
5666 
5667  if ( consdata->intvar != NULL )
5668  nintvar = 1;
5669 
5670  if ( varssize < consdata->nvars + nintvar + consdata->nextvars )
5671  (*success) = FALSE;
5672  else
5673  {
5674  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
5675 
5676  if ( consdata->intvar != NULL )
5677  vars[consdata->nvars] = consdata->intvar;
5678 
5679  if ( consdata->nextvars > 0 )
5680  {
5681  assert( consdata->extvars != NULL );
5682  cnt = consdata->nvars + nintvar;
5683  for (j = 0; j < consdata->extvarssize; ++j)
5684  {
5685  if ( consdata->extvars[j] != NULL )
5686  vars[cnt++] = consdata->extvars[j];
5687  }
5688  assert( cnt == consdata->nvars + nintvar + consdata->nextvars );
5689  }
5690 
5691  (*success) = TRUE;
5692  }
5693 
5694  return SCIP_OKAY;
5695 }
5696 
5697 /** constraint method of constraint handler which returns the number of variable (if possible) */
5698 static
5699 SCIP_DECL_CONSGETNVARS(consGetNVarsXor)
5700 { /*lint --e{715}*/
5701  SCIP_CONSDATA* consdata;
5702 
5703  assert(cons != NULL);
5704 
5705  consdata = SCIPconsGetData(cons);
5706  assert(consdata != NULL);
5707 
5708  if( consdata->intvar == NULL )
5709  (*nvars) = consdata->nvars + consdata->nextvars;
5710  else
5711  (*nvars) = consdata->nvars + 1 + consdata->nextvars;
5712 
5713  (*success) = TRUE;
5714 
5715  return SCIP_OKAY;
5716 }
5717 
5718 /*
5719  * Callback methods of event handler
5720  */
5721 
5722 static
5723 SCIP_DECL_EVENTEXEC(eventExecXor)
5724 { /*lint --e{715}*/
5725  SCIP_CONSDATA* consdata;
5726 
5727  assert(eventhdlr != NULL);
5728  assert(eventdata != NULL);
5729  assert(event != NULL);
5730 
5731  consdata = (SCIP_CONSDATA*)eventdata;
5732  assert(consdata != NULL);
5733 
5734  if( SCIPeventGetType(event) == SCIP_EVENTTYPE_VARFIXED )
5735  {
5736  /* we only catch this event in presolving stage */
5737  assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING);
5738  assert(SCIPeventGetVar(event) != NULL);
5739 
5740  consdata->sorted = FALSE;
5741  }
5742 
5743  consdata->propagated = FALSE;
5744 
5745  return SCIP_OKAY;
5746 }
5747 
5748 
5749 /*
5750  * constraint specific interface methods
5751  */
5752 
5753 /** creates the handler for xor constraints and includes it in SCIP */
5754 SCIP_RETCODE SCIPincludeConshdlrXor(
5755  SCIP* scip /**< SCIP data structure */
5756  )
5757 {
5758  SCIP_CONSHDLRDATA* conshdlrdata;
5759  SCIP_CONSHDLR* conshdlr;
5760  SCIP_EVENTHDLR* eventhdlr;
5761 
5762  /* create event handler for events on variables */
5763  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
576