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