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