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