Scippy

SCIP

Solving Constraint Integer Programs

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