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