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