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