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