Scippy

SCIP

Solving Constraint Integer Programs

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