Scippy

SCIP

Solving Constraint Integer Programs

cons_or.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_or.c
17  * @brief Constraint handler for "or" constraints, \f$r = x_1 \vee x_2 \vee \dots \vee x_n\f$
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  * @author Michael Winkler
21  *
22  * This constraint handler deals with "or" constraint. These are constraint of the form:
23  *
24  * \f[
25  * r = x_1 \vee x_2 \vee \dots \vee x_n
26  * \f]
27  *
28  * where \f$x_i\f$ is a binary variable for all \f$i\f$. Hence, \f$r\f$ is also of binary type. The variable \f$r\f$ is
29  * called resultant and the \f$x\f$'s operators.
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include <assert.h>
35 #include <string.h>
36 
37 #include "scip/cons_or.h"
38 #include "scip/cons_and.h"
39 #include "scip/pub_misc.h"
40 
41 
42 /* constraint handler properties */
43 #define CONSHDLR_NAME "or"
44 #define CONSHDLR_DESC "constraint handler for or constraints: r = or(x1, ..., xn)"
45 #define CONSHDLR_SEPAPRIORITY +850000 /**< priority of the constraint handler for separation */
46 #define CONSHDLR_ENFOPRIORITY -850000 /**< priority of the constraint handler for constraint enforcing */
47 #define CONSHDLR_CHECKPRIORITY -850000 /**< priority of the constraint handler for checking feasibility */
48 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
49 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
50 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
51  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
52 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
53 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
54 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
55 #define CONSHDLR_DELAYPRESOL FALSE /**< should presolving method be delayed, if other presolvers found reductions? */
56 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
57 
58 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
59 
60 #define EVENTHDLR_NAME "or"
61 #define EVENTHDLR_DESC "event handler for or constraints"
62 
63 
64 /*
65  * Data structures
66  */
67 
68 /** constraint data for or constraints */
69 struct SCIP_ConsData
70 {
71  SCIP_VAR** vars; /**< variables in the or operation */
72  SCIP_VAR* resvar; /**< resultant variable */
73  SCIP_ROW** rows; /**< rows for linear relaxation of or constraint */
74  int nvars; /**< number of variables in or operation */
75  int varssize; /**< size of vars array */
76  int rowssize; /**< size of rows array */
77  int watchedvar1; /**< position of first watched operator variable */
78  int watchedvar2; /**< position of second watched operator variable */
79  int filterpos1; /**< event filter position of first watched operator variable */
80  int filterpos2; /**< event filter position of second watched operator variable */
81  unsigned int propagated:1; /**< is constraint already preprocessed/propagated? */
82  unsigned int nofixedone:1; /**< is none of the operator variables fixed to TRUE? */
83  unsigned int impladded:1; /**< were the implications of the constraint already added? */
84  unsigned int opimpladded:1; /**< was the implication for 2 operands with fixed resultant added? */
85 };
86 
87 /** constraint handler data */
88 struct SCIP_ConshdlrData
89 {
90  SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */
91 };
92 
93 
94 /*
95  * Propagation rules
96  */
97 
98 enum Proprule
99 {
100  PROPRULE_1, /**< v_i = TRUE => r = TRUE */
101  PROPRULE_2, /**< r = FALSE => v_i = FALSE for all i */
102  PROPRULE_3, /**< v_i = FALSE for all i => r = FALSE */
103  PROPRULE_4, /**< r = TRUE, v_i = FALSE for all i except j => v_j = TRUE */
104  PROPRULE_INVALID /**< propagation was applied without a specific propagation rule */
105 };
106 typedef enum Proprule PROPRULE;
107 
108 
109 /*
110  * Local methods
111  */
112 
113 /** installs rounding locks for the given variable in the given or constraint */
114 static
115 SCIP_RETCODE lockRounding(
116  SCIP* scip, /**< SCIP data structure */
117  SCIP_CONS* cons, /**< or constraint */
118  SCIP_VAR* var /**< variable of constraint entry */
119  )
120 {
121  /* rounding in both directions may violate the constraint */
122  SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
123 
124  return SCIP_OKAY;
125 }
126 
127 /** removes rounding locks for the given variable in the given or constraint */
128 static
129 SCIP_RETCODE unlockRounding(
130  SCIP* scip, /**< SCIP data structure */
131  SCIP_CONS* cons, /**< or constraint */
132  SCIP_VAR* var /**< variable of constraint entry */
133  )
134 {
135  /* rounding in both directions may violate the constraint */
136  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
137 
138  return SCIP_OKAY;
139 }
140 
141 /** creates constraint handler data */
142 static
143 SCIP_RETCODE conshdlrdataCreate(
144  SCIP* scip, /**< SCIP data structure */
145  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
146  SCIP_EVENTHDLR* eventhdlr /**< event handler */
147  )
148 {
149  assert(scip != NULL);
150  assert(conshdlrdata != NULL);
151  assert(eventhdlr != NULL);
152 
153  SCIP_CALL( SCIPallocMemory(scip, conshdlrdata) );
154 
155  /* set event handler for catching events on watched variables */
156  (*conshdlrdata)->eventhdlr = eventhdlr;
157 
158  return SCIP_OKAY;
159 }
160 
161 /** frees constraint handler data */
162 static
163 SCIP_RETCODE conshdlrdataFree(
164  SCIP* scip, /**< SCIP data structure */
165  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
166  )
167 {
168  assert(conshdlrdata != NULL);
169  assert(*conshdlrdata != NULL);
170 
171  SCIPfreeMemory(scip, conshdlrdata);
172 
173  return SCIP_OKAY;
174 }
175 
176 /** gets number of LP rows needed for the LP relaxation of the constraint */
177 static
178 int consdataGetNRows(
179  SCIP_CONSDATA* consdata /**< constraint data */
180  )
181 {
182  assert(consdata != NULL);
183 
184  return consdata->nvars + 1;
185 }
186 
187 /** catches events for the watched variable at given position */
188 static
189 SCIP_RETCODE consdataCatchWatchedEvents(
190  SCIP* scip, /**< SCIP data structure */
191  SCIP_CONSDATA* consdata, /**< or constraint data */
192  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
193  int pos, /**< array position of variable to catch bound change events for */
194  int* filterpos /**< pointer to store position of event filter entry */
195  )
196 {
197  assert(consdata != NULL);
198  assert(consdata->vars != NULL);
199  assert(eventhdlr != NULL);
200  assert(0 <= pos && pos < consdata->nvars);
201  assert(filterpos != NULL);
202 
203  /* catch tightening events for upper bound and relaxed events for lower bounds on watched variable */
204  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED,
205  eventhdlr, (SCIP_EVENTDATA*)consdata, filterpos) );
206 
207  return SCIP_OKAY;
208 }
209 
210 
211 /** drops events for the watched variable at given position */
212 static
213 SCIP_RETCODE consdataDropWatchedEvents(
214  SCIP* scip, /**< SCIP data structure */
215  SCIP_CONSDATA* consdata, /**< or constraint data */
216  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
217  int pos, /**< array position of watched variable to drop bound change events for */
218  int filterpos /**< position of event filter entry */
219  )
220 {
221  assert(consdata != NULL);
222  assert(consdata->vars != NULL);
223  assert(eventhdlr != NULL);
224  assert(0 <= pos && pos < consdata->nvars);
225  assert(filterpos >= 0);
226 
227  /* drop tightening events for upper bound and relaxed events for lower bounds on watched variable */
228  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED,
229  eventhdlr, (SCIP_EVENTDATA*)consdata, filterpos) );
230 
231  return SCIP_OKAY;
232 }
233 
234 /** catches needed events on all variables of constraint, except the special ones for watched variables */
235 static
236 SCIP_RETCODE consdataCatchEvents(
237  SCIP* scip, /**< SCIP data structure */
238  SCIP_CONSDATA* consdata, /**< or constraint data */
239  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
240  )
241 {
242  int i;
243 
244  assert(consdata != NULL);
245 
246  /* catch bound change events for both bounds on resultant variable */
247  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->resvar, SCIP_EVENTTYPE_BOUNDCHANGED,
248  eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
249 
250  /* catch tightening events for lower bound and relaxed events for upper bounds on operator variables */
251  for( i = 0; i < consdata->nvars; ++i )
252  {
253  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[i], SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_UBRELAXED,
254  eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
255  }
256 
257  return SCIP_OKAY;
258 }
259 
260 /** drops events on all variables of constraint, except the special ones for watched variables */
261 static
262 SCIP_RETCODE consdataDropEvents(
263  SCIP* scip, /**< SCIP data structure */
264  SCIP_CONSDATA* consdata, /**< or constraint data */
265  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
266  )
267 {
268  int i;
269 
270  assert(consdata != NULL);
271 
272  /* drop bound change events for both bounds on resultant variable */
273  SCIP_CALL( SCIPdropVarEvent(scip, consdata->resvar, SCIP_EVENTTYPE_BOUNDCHANGED,
274  eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
275 
276  /* drop tightening events for lower bound and relaxed events for upper bounds on operator variables */
277  for( i = 0; i < consdata->nvars; ++i )
278  {
279  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[i], SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_UBRELAXED,
280  eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
281  }
282 
283  return SCIP_OKAY;
284 }
285 
286 /** stores the given variable numbers as watched variables, and updates the event processing */
287 static
288 SCIP_RETCODE consdataSwitchWatchedvars(
289  SCIP* scip, /**< SCIP data structure */
290  SCIP_CONSDATA* consdata, /**< or constraint data */
291  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
292  int watchedvar1, /**< new first watched variable */
293  int watchedvar2 /**< new second watched variable */
294  )
295 {
296  assert(consdata != NULL);
297  assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
298  assert(watchedvar1 != -1 || watchedvar2 == -1);
299  assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
300  assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
301 
302  /* if one watched variable is equal to the old other watched variable, just switch positions */
303  if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
304  {
305  int tmp;
306 
307  tmp = consdata->watchedvar1;
308  consdata->watchedvar1 = consdata->watchedvar2;
309  consdata->watchedvar2 = tmp;
310  tmp = consdata->filterpos1;
311  consdata->filterpos1 = consdata->filterpos2;
312  consdata->filterpos2 = tmp;
313  }
314  assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
315  assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
316 
317  /* drop events on old watched variables */
318  if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
319  {
320  assert(consdata->filterpos1 != -1);
321  SCIP_CALL( consdataDropWatchedEvents(scip, consdata, eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
322  }
323  if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
324  {
325  assert(consdata->filterpos2 != -1);
326  SCIP_CALL( consdataDropWatchedEvents(scip, consdata, eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
327  }
328 
329  /* catch events on new watched variables */
330  if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
331  {
332  SCIP_CALL( consdataCatchWatchedEvents(scip, consdata, eventhdlr, watchedvar1, &consdata->filterpos1) );
333  }
334  if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
335  {
336  SCIP_CALL( consdataCatchWatchedEvents(scip, consdata, eventhdlr, watchedvar2, &consdata->filterpos2) );
337  }
338 
339  /* set the new watched variables */
340  consdata->watchedvar1 = watchedvar1;
341  consdata->watchedvar2 = watchedvar2;
342 
343  return SCIP_OKAY;
344 }
345 
346 /** ensures, that the vars array can store at least num entries */
347 static
348 SCIP_RETCODE consdataEnsureVarsSize(
349  SCIP* scip, /**< SCIP data structure */
350  SCIP_CONSDATA* consdata, /**< linear constraint data */
351  int num /**< minimum number of entries to store */
352  )
353 {
354  assert(consdata != NULL);
355  assert(consdata->nvars <= consdata->varssize);
356 
357  if( num > consdata->varssize )
358  {
359  int newsize;
360 
361  newsize = SCIPcalcMemGrowSize(scip, num);
362  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
363  consdata->varssize = newsize;
364  }
365  assert(num <= consdata->varssize);
366 
367  return SCIP_OKAY;
368 }
369 
370 /** creates constraint data for or constraint */
371 static
372 SCIP_RETCODE consdataCreate(
373  SCIP* scip, /**< SCIP data structure */
374  SCIP_CONSDATA** consdata, /**< pointer to store the constraint data */
375  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
376  int nvars, /**< number of variables in the or operation */
377  SCIP_VAR** vars, /**< variables in or operation */
378  SCIP_VAR* resvar /**< resultant variable */
379  )
380 {
381  assert(consdata != NULL);
382  assert(nvars == 0 || vars != NULL);
383  assert(resvar != NULL);
384 
385  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
386  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
387  (*consdata)->resvar = resvar;
388  (*consdata)->rows = NULL;
389  (*consdata)->nvars = nvars;
390  (*consdata)->varssize = nvars;
391  (*consdata)->rowssize = 0;
392  (*consdata)->watchedvar1 = -1;
393  (*consdata)->watchedvar2 = -1;
394  (*consdata)->filterpos1 = -1;
395  (*consdata)->filterpos2 = -1;
396  (*consdata)->propagated = FALSE;
397  (*consdata)->nofixedone = FALSE;
398  (*consdata)->impladded = FALSE;
399  (*consdata)->opimpladded = FALSE;
400 
401  /* get transformed variables, if we are in the transformed problem */
402  if( SCIPisTransformed(scip) )
403  {
404  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
405  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->resvar, &(*consdata)->resvar) );
406 
407  /* catch needed events on variables */
408  SCIP_CALL( consdataCatchEvents(scip, *consdata, eventhdlr) );
409  }
410 
411  return SCIP_OKAY;
412 }
413 
414 /** releases LP rows of constraint data and frees rows array */
415 static
416 SCIP_RETCODE consdataFreeRows(
417  SCIP* scip, /**< SCIP data structure */
418  SCIP_CONSDATA* consdata /**< constraint data */
419  )
420 {
421  int r;
422 
423  assert(consdata != NULL);
424 
425  if( consdata->rows != NULL )
426  {
427  int nrows;
428 
429  nrows = consdataGetNRows(consdata);
430 
431  for( r = 0; r < nrows; ++r )
432  {
433  SCIP_CALL( SCIPreleaseRow(scip, &consdata->rows[r]) );
434  }
435  SCIPfreeBlockMemoryArray(scip, &consdata->rows, consdata->rowssize);
436  }
437 
438  return SCIP_OKAY;
439 }
440 
441 /** frees constraint data for or constraint */
442 static
443 SCIP_RETCODE consdataFree(
444  SCIP* scip, /**< SCIP data structure */
445  SCIP_CONSDATA** consdata, /**< pointer to the constraint data */
446  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
447  )
448 {
449  assert(consdata != NULL);
450  assert(*consdata != NULL);
451 
452  if( SCIPisTransformed(scip) )
453  {
454  /* drop events for watched variables */
455  SCIP_CALL( consdataSwitchWatchedvars(scip, *consdata, eventhdlr, -1, -1) );
456 
457  /* drop all other events on variables */
458  SCIP_CALL( consdataDropEvents(scip, *consdata, eventhdlr) );
459  }
460  else
461  {
462  assert((*consdata)->watchedvar1 == -1);
463  assert((*consdata)->watchedvar2 == -1);
464  }
465 
466  /* release and free the rows */
467  SCIP_CALL( consdataFreeRows(scip, *consdata) );
468 
469  SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->varssize);
470  SCIPfreeBlockMemory(scip, consdata);
471 
472  return SCIP_OKAY;
473 }
474 
475 /** prints or constraint to file stream */
476 static
477 SCIP_RETCODE consdataPrint(
478  SCIP* scip, /**< SCIP data structure */
479  SCIP_CONSDATA* consdata, /**< or constraint data */
480  FILE* file /**< output file (or NULL for standard output) */
481  )
482 {
483  assert(consdata != NULL);
484 
485  /* print resultant */
486  SCIP_CALL( SCIPwriteVarName(scip, file, consdata->resvar, TRUE) );
487 
488  /* start the variable list */
489  SCIPinfoMessage(scip, file, " == or(");
490 
491  /* print variable list */
492  SCIP_CALL( SCIPwriteVarsList(scip, file, consdata->vars, consdata->nvars, TRUE, ',') );
493 
494  /* close the variable list */
495  SCIPinfoMessage(scip, file, ")");
496 
497  return SCIP_OKAY;
498 }
499 
500 /** adds coefficient in or constraint */
501 static
502 SCIP_RETCODE addCoef(
503  SCIP* scip, /**< SCIP data structure */
504  SCIP_CONS* cons, /**< linear constraint */
505  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
506  SCIP_VAR* var /**< variable to add to the constraint */
507  )
508 {
509  SCIP_CONSDATA* consdata;
510  SCIP_Bool transformed;
511 
512  assert(var != NULL);
513 
514  consdata = SCIPconsGetData(cons);
515  assert(consdata != NULL);
516  assert(consdata->rows == NULL);
517 
518  /* are we in the transformed problem? */
519  transformed = SCIPconsIsTransformed(cons);
520 
521  /* always use transformed variables in transformed constraints */
522  if( transformed )
523  {
524  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
525  }
526  assert(var != NULL);
527  assert(transformed == SCIPvarIsTransformed(var));
528 
529  SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
530  consdata->vars[consdata->nvars] = var;
531  consdata->nvars++;
532 
533  /* if we are in transformed problem, catch the variable's events */
534  if( transformed )
535  {
536  /* catch bound change events of variable */
537  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_UBRELAXED,
538  eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
539  }
540 
541  /* install the rounding locks for the new variable */
542  SCIP_CALL( lockRounding(scip, cons, var) );
543 
544  /**@todo update LP rows */
545  if( consdata->rows != NULL )
546  {
547  SCIPerrorMessage("cannot add coefficients to or constraint after LP relaxation was created\n");
548  return SCIP_INVALIDCALL;
549  }
550 
551  return SCIP_OKAY;
552 }
553 
554 /** deletes coefficient at given position from or constraint data */
555 static
556 SCIP_RETCODE delCoefPos(
557  SCIP* scip, /**< SCIP data structure */
558  SCIP_CONS* cons, /**< or constraint */
559  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
560  int pos /**< position of coefficient to delete */
561  )
562 {
563  SCIP_CONSDATA* consdata;
564 
565  assert(eventhdlr != NULL);
566 
567  consdata = SCIPconsGetData(cons);
568  assert(consdata != NULL);
569  assert(0 <= pos && pos < consdata->nvars);
570  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
571 
572  /* remove the rounding locks of the variable */
573  SCIP_CALL( unlockRounding(scip, cons, consdata->vars[pos]) );
574 
575  if( SCIPconsIsTransformed(cons) )
576  {
577  /* drop bound change events of variable */
578  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_UBRELAXED,
579  eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
580  }
581 
582  if( SCIPconsIsTransformed(cons) )
583  {
584  /* if the position is watched, stop watching the position */
585  if( consdata->watchedvar1 == pos )
586  {
587  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar2, -1) );
588  }
589  if( consdata->watchedvar2 == pos )
590  {
591  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar1, -1) );
592  }
593  }
594  assert(pos != consdata->watchedvar1);
595  assert(pos != consdata->watchedvar2);
596 
597  /* move the last variable to the free slot */
598  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
599  consdata->nvars--;
600 
601  /* if the last variable (that moved) was watched, update the watched position */
602  if( consdata->watchedvar1 == consdata->nvars )
603  consdata->watchedvar1 = pos;
604  if( consdata->watchedvar2 == consdata->nvars )
605  consdata->watchedvar2 = pos;
606 
607  consdata->propagated = FALSE;
608 
609  return SCIP_OKAY;
610 }
611 
612 /** deletes all zero-fixed variables */
613 static
614 SCIP_RETCODE applyFixings(
615  SCIP* scip, /**< SCIP data structure */
616  SCIP_CONS* cons, /**< or constraint */
617  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
618  )
619 {
620  SCIP_CONSDATA* consdata;
621  SCIP_VAR* var;
622  int v;
623 
624  consdata = SCIPconsGetData(cons);
625  assert(consdata != NULL);
626  assert(consdata->nvars == 0 || consdata->vars != NULL);
627 
628  v = 0;
629  while( v < consdata->nvars )
630  {
631  var = consdata->vars[v];
632  assert(SCIPvarIsBinary(var));
633 
634  if( SCIPvarGetUbGlobal(var) < 0.5 )
635  {
636  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), 0.0));
637  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
638  }
639  else
640  {
641  SCIP_VAR* repvar;
642  SCIP_Bool negated;
643 
644  /* get binary representative of variable */
645  SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
646 
647  /* check, if the variable should be replaced with the representative */
648  if( repvar != var )
649  {
650  /* delete old (aggregated) variable */
651  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
652 
653  /* add representative instead */
654  SCIP_CALL( addCoef(scip, cons, eventhdlr, repvar) );
655  }
656  else
657  ++v;
658  }
659  }
660 
661  SCIPdebugMessage("after fixings: ");
662  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL)) );
663  SCIPdebugPrintf("\n");
664 
665  return SCIP_OKAY;
666 }
667 
668 /** creates LP rows corresponding to or constraint:
669  * - for each operator variable vi: resvar - vi >= 0
670  * - one additional row: resvar - v1 - ... - vn <= 0
671  */
672 static
673 SCIP_RETCODE createRelaxation(
674  SCIP* scip, /**< SCIP data structure */
675  SCIP_CONS* cons /**< constraint to check */
676  )
677 {
678  SCIP_CONSDATA* consdata;
679  char rowname[SCIP_MAXSTRLEN];
680  int nvars;
681  int i;
682 
683  consdata = SCIPconsGetData(cons);
684  assert(consdata != NULL);
685  assert(consdata->rows == NULL);
686 
687  nvars = consdata->nvars;
688 
689  /* get memory for rows */
690  consdata->rowssize = consdataGetNRows(consdata);
691  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->rows, consdata->rowssize) );
692  assert(consdata->rowssize == nvars+1);
693 
694  /* create operator rows */
695  for( i = 0; i < nvars; ++i )
696  {
697  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), i);
698  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[i], SCIPconsGetHdlr(cons), rowname, 0.0, SCIPinfinity(scip),
699  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
700  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[i], consdata->resvar, 1.0) );
701  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[i], consdata->vars[i], -1.0) );
702  }
703 
704  /* create additional row */
705  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_add", SCIPconsGetName(cons));
706  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[nvars], SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), 0.0,
707  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
708  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[nvars], consdata->resvar, 1.0) );
709  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[nvars], nvars, consdata->vars, -1.0) );
710 
711  return SCIP_OKAY;
712 }
713 
714 /** adds linear relaxation of or constraint to the LP */
715 static
716 SCIP_RETCODE addRelaxation(
717  SCIP* scip, /**< SCIP data structure */
718  SCIP_CONS* cons /**< constraint to check */
719  )
720 {
721  SCIP_CONSDATA* consdata;
722  int r;
723  int nrows;
724 
725  consdata = SCIPconsGetData(cons);
726  assert(consdata != NULL);
727 
728  if( consdata->rows == NULL )
729  {
730  SCIP_CALL( createRelaxation(scip, cons) );
731  }
732  assert( consdata->rows != NULL );
733 
734  nrows = consdataGetNRows(consdata);
735 
736  for( r = 0; r < nrows; ++r )
737  {
738  if( !SCIProwIsInLP(consdata->rows[r]) )
739  {
740  SCIP_Bool infeasible;
741  SCIP_CALL( SCIPaddCut(scip, NULL, consdata->rows[r], FALSE, &infeasible) );
742  assert( ! infeasible ); /* this function is only called from initlp -> the cut should be feasible */
743  }
744  }
745 
746  return SCIP_OKAY;
747 }
748 
749 /** checks or constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
750 static
751 SCIP_RETCODE checkCons(
752  SCIP* scip, /**< SCIP data structure */
753  SCIP_CONS* cons, /**< constraint to check */
754  SCIP_SOL* sol, /**< solution to check, NULL for current solution */
755  SCIP_Bool checklprows, /**< should LP rows be checked? */
756  SCIP_Bool printreason, /**< should the reason for the violation be printed? */
757  SCIP_Bool* violated /**< pointer to store whether the constraint is violated */
758  )
759 {
760  SCIP_CONSDATA* consdata;
761  SCIP_Bool mustcheck;
762  int r;
763 
764  assert(violated != NULL);
765 
766  consdata = SCIPconsGetData(cons);
767  assert(consdata != NULL);
768 
769  *violated = FALSE;
770 
771  /* check, if we can skip this feasibility check, because all rows are in the LP and doesn't have to be checked */
772  mustcheck = checklprows;
773  mustcheck = mustcheck || (consdata->rows == NULL);
774  if( !mustcheck )
775  {
776  int nrows;
777 
778  assert(consdata->rows != NULL);
779 
780  nrows = consdataGetNRows(consdata);
781 
782  for( r = 0; r < nrows; ++r )
783  {
784  mustcheck = !SCIProwIsInLP(consdata->rows[r]);
785  if( mustcheck )
786  break;
787  }
788  }
789 
790  /* check feasibility of constraint if necessary */
791  if( mustcheck )
792  {
793  SCIP_Real solval;
794  int i;
795 
796  /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
797  * enforcement
798  */
799  if( sol == NULL )
800  {
801  SCIP_CALL( SCIPincConsAge(scip, cons) );
802  }
803 
804  /* check, if all operator variables are FALSE */
805  for( i = 0; i < consdata->nvars; ++i )
806  {
807  solval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
808  assert(SCIPisFeasIntegral(scip, solval));
809  if( solval > 0.5 )
810  break;
811  }
812 
813  /* if all operator variables are FALSE, the resultant has to be FALSE, otherwise, the resultant has to be TRUE */
814  solval = SCIPgetSolVal(scip, sol, consdata->resvar);
815  assert(SCIPisFeasIntegral(scip, solval));
816 
817  if( (i == consdata->nvars) != (solval < 0.5) )
818  {
819  *violated = TRUE;
820 
821  /* only reset constraint age if we are in enforcement */
822  if( sol == NULL )
823  {
824  SCIP_CALL( SCIPresetConsAge(scip, cons) );
825  }
826 
827  if( printreason )
828  {
829  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
830  SCIPinfoMessage(scip, NULL, ";\nviolation:\n");
831  if( i == consdata->nvars )
832  {
833  SCIPinfoMessage(scip, NULL, " all operands are FALSE and resultant <%s> = TRUE\n",
834  SCIPvarGetName(consdata->resvar));
835  }
836  else
837  {
838  SCIPinfoMessage(scip, NULL, " operand <%s> = TRUE and resultant <%s> = FALSE\n",
839  SCIPvarGetName(consdata->vars[i-1]), SCIPvarGetName(consdata->resvar));
840  }
841  }
842  }
843  }
844 
845  return SCIP_OKAY;
846 }
847 
848 /** separates current LP solution */
849 static
850 SCIP_RETCODE separateCons(
851  SCIP* scip, /**< SCIP data structure */
852  SCIP_CONS* cons, /**< constraint to check */
853  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
854  SCIP_Bool* separated /**< pointer to store whether a cut was found */
855  )
856 {
857  SCIP_CONSDATA* consdata;
858  SCIP_Real feasibility;
859  int r;
860  int nrows;
861 
862  assert(separated != NULL);
863 
864  consdata = SCIPconsGetData(cons);
865  assert(consdata != NULL);
866 
867  *separated = FALSE;
868 
869  /* create all necessary rows for the linear relaxation */
870  if( consdata->rows == NULL )
871  {
872  SCIP_CALL( createRelaxation(scip, cons) );
873  }
874  assert(consdata->rows != NULL);
875 
876  nrows = consdataGetNRows(consdata);
877 
878  /* test all rows for feasibility and add infeasible rows */
879  for( r = 0; r < nrows; ++r )
880  {
881  if( !SCIProwIsInLP(consdata->rows[r]) )
882  {
883  feasibility = SCIPgetRowSolFeasibility(scip, consdata->rows[r], sol);
884  if( SCIPisFeasNegative(scip, feasibility) )
885  {
886  SCIP_Bool infeasible;
887 
888  SCIP_CALL( SCIPaddCut(scip, sol, consdata->rows[r], FALSE, &infeasible) );
889  assert( ! infeasible );
890  *separated = TRUE;
891  }
892  }
893  }
894 
895  return SCIP_OKAY;
896 }
897 
898 /** analyzes conflicting FALSE assignment to resultant of given constraint, and adds conflict constraint to problem */
899 static
900 SCIP_RETCODE analyzeConflictZero(
901  SCIP* scip, /**< SCIP data structure */
902  SCIP_CONS* cons, /**< or constraint that detected the conflict */
903  int truepos /**< position of operand that is fixed to TRUE */
904  )
905 {
906  SCIP_CONSDATA* consdata;
907 
908  /* conflict analysis can only be applied in solving stage and if it is applicable */
909  if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
910  return SCIP_OKAY;
911 
912  consdata = SCIPconsGetData(cons);
913  assert(consdata != NULL);
914  assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
915  assert(0 <= truepos && truepos < consdata->nvars);
916  assert(SCIPvarGetLbLocal(consdata->vars[truepos]) > 0.5);
917 
918  /* initialize conflict analysis, and add resultant and single operand variable to conflict candidate queue */
919  SCIP_CALL( SCIPinitConflictAnalysis(scip) );
920  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
921  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[truepos]) );
922 
923  /* analyze the conflict */
924  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
925 
926  return SCIP_OKAY;
927 }
928 
929 /** analyzes conflicting TRUE assignment to resultant of given constraint, and adds conflict constraint to problem */
930 static
931 SCIP_RETCODE analyzeConflictOne(
932  SCIP* scip, /**< SCIP data structure */
933  SCIP_CONS* cons /**< or constraint that detected the conflict */
934  )
935 {
936  SCIP_CONSDATA* consdata;
937  int v;
938 
939  assert(!SCIPconsIsModifiable(cons));
940 
941  /* conflict analysis can only be applied in solving stage and if it is applicable */
942  if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
943  return SCIP_OKAY;
944 
945  consdata = SCIPconsGetData(cons);
946  assert(consdata != NULL);
947  assert(SCIPvarGetLbLocal(consdata->resvar) > 0.5);
948 
949  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
950  SCIP_CALL( SCIPinitConflictAnalysis(scip) );
951  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
952  for( v = 0; v < consdata->nvars; ++v )
953  {
954  assert(SCIPvarGetUbLocal(consdata->vars[v]) < 0.5);
955  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
956  }
957 
958  /* analyze the conflict */
959  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
960 
961  return SCIP_OKAY;
962 }
963 
964 /** propagates constraint with the following rules:
965  * (1) v_i = TRUE => r = TRUE
966  * (2) r = FALSE => v_i = FALSE for all i
967  * (3) v_i = FALSE for all i => r = FALSE
968  * (4) r = TRUE, v_i = FALSE for all i except j => v_j = TRUE
969  */
970 static
971 SCIP_RETCODE propagateCons(
972  SCIP* scip, /**< SCIP data structure */
973  SCIP_CONS* cons, /**< or constraint to be processed */
974  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
975  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
976  int* nfixedvars /**< pointer to add up the number of found domain reductions */
977  )
978 {
979  SCIP_CONSDATA* consdata;
980  SCIP_VAR* resvar;
981  SCIP_VAR** vars;
982  int nvars;
983  int watchedvar1;
984  int watchedvar2;
985  int i;
986  SCIP_Bool infeasible;
987  SCIP_Bool tightened;
988 
989  assert(cutoff != NULL);
990  assert(nfixedvars != NULL);
991 
992  consdata = SCIPconsGetData(cons);
993  assert(consdata != NULL);
994 
995  resvar = consdata->resvar;
996  vars = consdata->vars;
997  nvars = consdata->nvars;
998 
999  /* don't process the constraint, if none of the operator variables was fixed to TRUE, and if the watched variables
1000  * and the resultant weren't fixed to any value since last propagation call
1001  */
1002  if( consdata->propagated )
1003  {
1004  assert(consdata->nofixedone);
1005  assert(SCIPisFeasEQ(scip, SCIPvarGetUbLocal(resvar), 1.0));
1006  return SCIP_OKAY;
1007  }
1008 
1009  /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
1010  if( !SCIPinRepropagation(scip) )
1011  {
1012  SCIP_CALL( SCIPincConsAge(scip, cons) );
1013  }
1014 
1015  /* if one of the operator variables was fixed to TRUE, the resultant can be fixed to TRUE (rule (1)) */
1016  if( !consdata->nofixedone )
1017  {
1018  for( i = 0; i < nvars && SCIPvarGetLbLocal(vars[i]) < 0.5; ++i ) /* search fixed operator */
1019  {}
1020  if( i < nvars )
1021  {
1022  SCIPdebugMessage("constraint <%s>: operator var <%s> fixed to 1.0 -> fix resultant <%s> to 1.0\n",
1023  SCIPconsGetName(cons), SCIPvarGetName(vars[i]), SCIPvarGetName(resvar));
1024  SCIP_CALL( SCIPinferBinvarCons(scip, resvar, TRUE, cons, (int)PROPRULE_1, &infeasible, &tightened) );
1025  if( infeasible )
1026  {
1027  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1028  SCIP_CALL( analyzeConflictZero(scip, cons, i) );
1029  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1030  *cutoff = TRUE;
1031  }
1032  else
1033  {
1034  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1035  if( tightened )
1036  {
1037  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1038  (*nfixedvars)++;
1039  }
1040  }
1041 
1042  return SCIP_OKAY;
1043  }
1044  else
1045  consdata->nofixedone = TRUE;
1046  }
1047  assert(consdata->nofixedone);
1048 
1049  /* if resultant is fixed to FALSE, all operator variables can be fixed to FALSE (rule (2)) */
1050  if( SCIPvarGetUbLocal(resvar) < 0.5 )
1051  {
1052  for( i = 0; i < nvars && !(*cutoff); ++i )
1053  {
1054  SCIPdebugMessage("constraint <%s>: resultant var <%s> fixed to 0.0 -> fix operator var <%s> to 0.0\n",
1055  SCIPconsGetName(cons), SCIPvarGetName(resvar), SCIPvarGetName(vars[i]));
1056  SCIP_CALL( SCIPinferBinvarCons(scip, vars[i], FALSE, cons, (int)PROPRULE_2, &infeasible, &tightened) );
1057  if( infeasible )
1058  {
1059  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1060  SCIP_CALL( analyzeConflictZero(scip, cons, i) );
1061  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1062  *cutoff = TRUE;
1063  }
1064  else if( tightened )
1065  {
1066  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1067  (*nfixedvars)++;
1068  }
1069  }
1070 
1071  if( !(*cutoff) )
1072  {
1073  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1074  }
1075 
1076  return SCIP_OKAY;
1077  }
1078 
1079  /* rules (3) and (4) can only be applied, if we know all operator variables */
1080  if( SCIPconsIsModifiable(cons) )
1081  return SCIP_OKAY;
1082 
1083  /* rules (3) and (4) cannot be applied, if we have at least two unfixed variables left;
1084  * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
1085  * if these ones get fixed
1086  */
1087  watchedvar1 = consdata->watchedvar1;
1088  watchedvar2 = consdata->watchedvar2;
1089 
1090  /* check, if watched variables are still unfixed */
1091  if( watchedvar1 != -1 )
1092  {
1093  assert(SCIPvarGetLbLocal(vars[watchedvar1]) < 0.5); /* otherwise, rule (1) could be applied */
1094  if( SCIPvarGetUbLocal(vars[watchedvar1]) < 0.5 )
1095  watchedvar1 = -1;
1096  }
1097  if( watchedvar2 != -1 )
1098  {
1099  assert(SCIPvarGetLbLocal(vars[watchedvar2]) < 0.5); /* otherwise, rule (1) could be applied */
1100  if( SCIPvarGetUbLocal(vars[watchedvar2]) < 0.5 )
1101  watchedvar2 = -1;
1102  }
1103 
1104  /* if only one watched variable is still unfixed, make it the first one */
1105  if( watchedvar1 == -1 )
1106  {
1107  watchedvar1 = watchedvar2;
1108  watchedvar2 = -1;
1109  }
1110  assert(watchedvar1 != -1 || watchedvar2 == -1);
1111 
1112  /* if the watched variables are invalid (fixed), find new ones if existing */
1113  if( watchedvar2 == -1 )
1114  {
1115  for( i = 0; i < nvars; ++i )
1116  {
1117  assert(SCIPvarGetLbLocal(vars[i]) < 0.5); /* otherwise, rule (1) could be applied */
1118  if( SCIPvarGetUbLocal(vars[i]) > 0.5 )
1119  {
1120  if( watchedvar1 == -1 )
1121  {
1122  assert(watchedvar2 == -1);
1123  watchedvar1 = i;
1124  }
1125  else if( watchedvar1 != i )
1126  {
1127  watchedvar2 = i;
1128  break;
1129  }
1130  }
1131  }
1132  }
1133  assert(watchedvar1 != -1 || watchedvar2 == -1);
1134 
1135  /* if all variables are fixed to FALSE, the resultant can also be fixed to FALSE (rule (3)) */
1136  if( watchedvar1 == -1 )
1137  {
1138  assert(watchedvar2 == -1);
1139 
1140  SCIPdebugMessage("constraint <%s>: all operator vars fixed to 0.0 -> fix resultant <%s> to 0.0\n",
1141  SCIPconsGetName(cons), SCIPvarGetName(resvar));
1142  SCIP_CALL( SCIPinferBinvarCons(scip, resvar, FALSE, cons, (int)PROPRULE_3, &infeasible, &tightened) );
1143  if( infeasible )
1144  {
1145  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1146  SCIP_CALL( analyzeConflictOne(scip, cons) );
1147  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1148  *cutoff = TRUE;
1149  }
1150  else
1151  {
1152  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1153  if( tightened )
1154  {
1155  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1156  (*nfixedvars)++;
1157  }
1158  }
1159 
1160  return SCIP_OKAY;
1161  }
1162 
1163  /* if resultant is fixed to TRUE, and only one operator variable is not fixed to FALSE, this operator variable
1164  * can be fixed to TRUE (rule (4))
1165  */
1166  if( SCIPvarGetLbLocal(resvar) > 0.5 && watchedvar2 == -1 )
1167  {
1168  assert(watchedvar1 != -1);
1169 
1170  SCIPdebugMessage("constraint <%s>: resultant <%s> fixed to 1.0, only one unfixed operand -> fix operand <%s> to 1.0\n",
1171  SCIPconsGetName(cons), SCIPvarGetName(resvar), SCIPvarGetName(vars[watchedvar1]));
1172  SCIP_CALL( SCIPinferBinvarCons(scip, vars[watchedvar1], TRUE, cons, (int)PROPRULE_4, &infeasible, &tightened) );
1173  if( infeasible )
1174  {
1175  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1176  SCIP_CALL( analyzeConflictOne(scip, cons) );
1177  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1178  *cutoff = TRUE;
1179  }
1180  else
1181  {
1182  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1183  if( tightened )
1184  {
1185  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1186  (*nfixedvars)++;
1187  }
1188  }
1189 
1190  return SCIP_OKAY;
1191  }
1192 
1193  /* switch to the new watched variables */
1194  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
1195 
1196  /* mark the constraint propagated */
1197  consdata->propagated = TRUE;
1198 
1199  return SCIP_OKAY;
1200 }
1201 
1202 /** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
1203  * propagation rule (see propagateCons()):
1204  * (1) v_i = TRUE => r = TRUE
1205  * (2) r = FALSE => v_i = FALSE for all i
1206  * (3) v_i = FALSE for all i => r = FALSE
1207  * (4) r = TRUE, v_i = FALSE for all i except j => v_j = TRUE
1208  */
1209 static
1210 SCIP_RETCODE resolvePropagation(
1211  SCIP* scip, /**< SCIP data structure */
1212  SCIP_CONS* cons, /**< constraint that inferred the bound change */
1213  SCIP_VAR* infervar, /**< variable that was deduced */
1214  PROPRULE proprule, /**< propagation rule that deduced the value */
1215  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1216  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1217  )
1218 {
1219  SCIP_CONSDATA* consdata;
1220  SCIP_VAR** vars;
1221  int nvars;
1222  int i;
1223 
1224  assert(result != NULL);
1225 
1226  consdata = SCIPconsGetData(cons);
1227  assert(consdata != NULL);
1228  vars = consdata->vars;
1229  nvars = consdata->nvars;
1230 
1231  switch( proprule )
1232  {
1233  case PROPRULE_1:
1234  /* the resultant was infered to TRUE, because one operand variable was TRUE */
1235  assert(SCIPvarGetLbAtIndex(infervar, bdchgidx, TRUE) > 0.5);
1236  assert(infervar == consdata->resvar);
1237  for( i = 0; i < nvars; ++i )
1238  {
1239  if( SCIPvarGetLbAtIndex(vars[i], bdchgidx, FALSE) > 0.5 )
1240  {
1241  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
1242  break;
1243  }
1244  }
1245  assert(i < nvars);
1246  *result = SCIP_SUCCESS;
1247  break;
1248 
1249  case PROPRULE_2:
1250  /* the operand variable was infered to FALSE, because the resultant was FALSE */
1251  assert(SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < 0.5);
1252  assert(SCIPvarGetUbAtIndex(consdata->resvar, bdchgidx, FALSE) < 0.5);
1253  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1254  *result = SCIP_SUCCESS;
1255  break;
1256 
1257  case PROPRULE_3:
1258  /* the resultant was infered to FALSE, because all operand variables were FALSE */
1259  assert(SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < 0.5);
1260  assert(infervar == consdata->resvar);
1261  for( i = 0; i < nvars; ++i )
1262  {
1263  assert(SCIPvarGetUbAtIndex(vars[i], bdchgidx, FALSE) < 0.5);
1264  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
1265  }
1266  *result = SCIP_SUCCESS;
1267  break;
1268 
1269  case PROPRULE_4:
1270  /* the operand variable was infered to TRUE, because the resultant was TRUE and all other operands were FALSE */
1271  assert(SCIPvarGetLbAtIndex(infervar, bdchgidx, TRUE) > 0.5);
1272  assert(SCIPvarGetLbAtIndex(consdata->resvar, bdchgidx, FALSE) > 0.5);
1273  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1274  for( i = 0; i < nvars; ++i )
1275  {
1276  if( vars[i] != infervar )
1277  {
1278  assert(SCIPvarGetUbAtIndex(vars[i], bdchgidx, FALSE) < 0.5);
1279  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
1280  }
1281  }
1282  *result = SCIP_SUCCESS;
1283  break;
1284 
1285  case PROPRULE_INVALID:
1286  default:
1287  SCIPerrorMessage("invalid inference information %d in or constraint <%s>\n", proprule, SCIPconsGetName(cons));
1288  return SCIP_INVALIDDATA;
1289  }
1290 
1291  return SCIP_OKAY;
1292 }
1293 
1294 /** upgrades unmodifiable or constraint into an and constraint on negated variables */
1295 static
1296 SCIP_RETCODE upgradeCons(
1297  SCIP* scip, /**< SCIP data structure */
1298  SCIP_CONS* cons, /**< constraint that inferred the bound change */
1299  int* nupgdconss /**< pointer to count the number of constraint upgrades */
1300  )
1301 {
1302  SCIP_CONSDATA* consdata;
1303  SCIP_VAR** negvars;
1304  SCIP_VAR* negresvar;
1305  SCIP_CONS* andcons;
1306  int i;
1307 
1308  assert(nupgdconss != NULL);
1309 
1310  /* we cannot upgrade a modifiable constraint, since we don't know what additional variables to expect */
1311  if( SCIPconsIsModifiable(cons) )
1312  return SCIP_OKAY;
1313 
1314  SCIPdebugMessage("upgrading or constraint <%s> into equivalent and constraint on negated variables\n",
1315  SCIPconsGetName(cons));
1316 
1317  consdata = SCIPconsGetData(cons);
1318  assert(consdata != NULL);
1319 
1320  /* get the negated versions of the variables */
1321  SCIP_CALL( SCIPallocBufferArray(scip, &negvars, consdata->nvars) );
1322  for( i = 0; i < consdata->nvars; ++i )
1323  {
1324  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[i], &negvars[i]) );
1325  }
1326  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->resvar, &negresvar) );
1327 
1328  /* create and add the and constraint */
1329  SCIP_CALL( SCIPcreateConsAnd(scip, &andcons, SCIPconsGetName(cons), negresvar, consdata->nvars, negvars,
1330  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons),
1331  SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
1332  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1333  SCIP_CALL( SCIPaddCons(scip, andcons) );
1334  SCIP_CALL( SCIPreleaseCons(scip, &andcons) );
1335 
1336  /* delete the or constraint */
1337  SCIP_CALL( SCIPdelCons(scip, cons) );
1338 
1339  /* free temporary memory */
1340  SCIPfreeBufferArray(scip, &negvars);
1341 
1342  (*nupgdconss)++;
1343 
1344  return SCIP_OKAY;
1345 }
1346 
1347 
1348 /*
1349  * Callback methods of constraint handler
1350  */
1351 
1352 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1353 static
1354 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOr)
1355 { /*lint --e{715}*/
1356  assert(scip != NULL);
1357  assert(conshdlr != NULL);
1358  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1359 
1360  /* call inclusion method of constraint handler */
1361  SCIP_CALL( SCIPincludeConshdlrOr(scip) );
1362 
1363  *valid = TRUE;
1364 
1365  return SCIP_OKAY;
1366 }
1367 
1368 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
1369 static
1370 SCIP_DECL_CONSFREE(consFreeOr)
1371 { /*lint --e{715}*/
1372  SCIP_CONSHDLRDATA* conshdlrdata;
1373 
1374  /* free constraint handler data */
1375  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1376  assert(conshdlrdata != NULL);
1377 
1378  SCIP_CALL( conshdlrdataFree(scip, &conshdlrdata) );
1379 
1380  SCIPconshdlrSetData(conshdlr, NULL);
1381 
1382  return SCIP_OKAY;
1383 }
1384 
1385 
1386 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
1387 static
1388 SCIP_DECL_CONSEXITSOL(consExitsolOr)
1389 { /*lint --e{715}*/
1390  SCIP_CONSDATA* consdata;
1391  int c;
1392 
1393  /* release and free the rows of all constraints */
1394  for( c = 0; c < nconss; ++c )
1395  {
1396  consdata = SCIPconsGetData(conss[c]);
1397  SCIP_CALL( consdataFreeRows(scip, consdata) );
1398  }
1399 
1400  return SCIP_OKAY;
1401 }
1402 
1403 
1404 /** frees specific constraint data */
1405 static
1406 SCIP_DECL_CONSDELETE(consDeleteOr)
1407 { /*lint --e{715}*/
1408  SCIP_CONSHDLRDATA* conshdlrdata;
1409 
1410  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1411  assert(conshdlrdata != NULL);
1412 
1413  SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
1414 
1415  return SCIP_OKAY;
1416 }
1417 
1418 
1419 /** transforms constraint data into data belonging to the transformed problem */
1420 static
1421 SCIP_DECL_CONSTRANS(consTransOr)
1422 { /*lint --e{715}*/
1423  SCIP_CONSHDLRDATA* conshdlrdata;
1424  SCIP_CONSDATA* sourcedata;
1425  SCIP_CONSDATA* targetdata;
1426 
1427  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1428  assert(conshdlrdata != NULL);
1429 
1430  sourcedata = SCIPconsGetData(sourcecons);
1431  assert(sourcedata != NULL);
1432 
1433  /* create target constraint data */
1434  SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr,
1435  sourcedata->nvars, sourcedata->vars, sourcedata->resvar) );
1436 
1437  /* create target constraint */
1438  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
1439  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
1440  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
1441  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
1442  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1443 
1444  return SCIP_OKAY;
1445 }
1446 
1447 
1448 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1449 static
1450 SCIP_DECL_CONSINITLP(consInitlpOr)
1451 { /*lint --e{715}*/
1452  int i;
1453 
1454  for( i = 0; i < nconss; i++ )
1455  {
1456  assert(SCIPconsIsInitial(conss[i]));
1457  SCIP_CALL( addRelaxation(scip, conss[i]) );
1458  }
1459 
1460  return SCIP_OKAY;
1461 }
1462 
1463 
1464 /** separation method of constraint handler for LP solutions */
1465 static
1466 SCIP_DECL_CONSSEPALP(consSepalpOr)
1467 { /*lint --e{715}*/
1468  SCIP_Bool separated;
1469  int c;
1470 
1471  *result = SCIP_DIDNOTFIND;
1472 
1473  /* separate all useful constraints */
1474  for( c = 0; c < nusefulconss; ++c )
1475  {
1476  SCIP_CALL( separateCons(scip, conss[c], NULL, &separated) );
1477  if( separated )
1478  *result = SCIP_SEPARATED;
1479  }
1480 
1481  /* combine constraints to get more cuts */
1482  /**@todo combine constraints to get further cuts */
1483 
1484  return SCIP_OKAY;
1485 }
1486 
1487 
1488 /** separation method of constraint handler for arbitrary primal solutions */
1489 static
1490 SCIP_DECL_CONSSEPASOL(consSepasolOr)
1491 { /*lint --e{715}*/
1492  SCIP_Bool separated;
1493  int c;
1494 
1495  *result = SCIP_DIDNOTFIND;
1496 
1497  /* separate all useful constraints */
1498  for( c = 0; c < nusefulconss; ++c )
1499  {
1500  SCIP_CALL( separateCons(scip, conss[c], sol, &separated) );
1501  if( separated )
1502  *result = SCIP_SEPARATED;
1503  }
1504 
1505  /* combine constraints to get more cuts */
1506  /**@todo combine constraints to get further cuts */
1507 
1508  return SCIP_OKAY;
1509 }
1510 
1511 
1512 /** constraint enforcing method of constraint handler for LP solutions */
1513 static
1514 SCIP_DECL_CONSENFOLP(consEnfolpOr)
1515 { /*lint --e{715}*/
1516  SCIP_Bool violated;
1517  int i;
1518 
1519  /* method is called only for integral solutions, because the enforcing priority is negative */
1520  for( i = 0; i < nconss; i++ )
1521  {
1522  SCIP_CALL( checkCons(scip, conss[i], NULL, FALSE, FALSE, &violated) );
1523  if( violated )
1524  {
1525  SCIP_Bool separated;
1526 
1527  SCIP_CALL( separateCons(scip, conss[i], NULL, &separated) );
1528  assert(separated); /* because the solution is integral, the separation always finds a cut */
1529  *result = SCIP_SEPARATED;
1530  return SCIP_OKAY;
1531  }
1532  }
1533  *result = SCIP_FEASIBLE;
1534 
1535  return SCIP_OKAY;
1536 }
1537 
1538 
1539 /** constraint enforcing method of constraint handler for pseudo solutions */
1540 static
1541 SCIP_DECL_CONSENFOPS(consEnfopsOr)
1542 { /*lint --e{715}*/
1543  SCIP_Bool violated;
1544  int i;
1545 
1546  /* method is called only for integral solutions, because the enforcing priority is negative */
1547  for( i = 0; i < nconss; i++ )
1548  {
1549  SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
1550  if( violated )
1551  {
1552  *result = SCIP_INFEASIBLE;
1553  return SCIP_OKAY;
1554  }
1555  }
1556  *result = SCIP_FEASIBLE;
1557 
1558  return SCIP_OKAY;
1559 }
1560 
1561 
1562 /** feasibility check method of constraint handler for integral solutions */
1563 static
1564 SCIP_DECL_CONSCHECK(consCheckOr)
1565 { /*lint --e{715}*/
1566  SCIP_Bool violated;
1567  int i;
1568 
1569  /* method is called only for integral solutions, because the enforcing priority is negative */
1570  for( i = 0; i < nconss; i++ )
1571  {
1572  SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, printreason, &violated) );
1573  if( violated )
1574  {
1575  *result = SCIP_INFEASIBLE;
1576  return SCIP_OKAY;
1577  }
1578  }
1579  *result = SCIP_FEASIBLE;
1580 
1581  return SCIP_OKAY;
1582 }
1583 
1584 
1585 /** domain propagation method of constraint handler */
1586 static
1587 SCIP_DECL_CONSPROP(consPropOr)
1588 { /*lint --e{715}*/
1589  SCIP_CONSHDLRDATA* conshdlrdata;
1590  SCIP_Bool cutoff;
1591  int nfixedvars;
1592  int c;
1593 
1594  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1595  assert(conshdlrdata != NULL);
1596 
1597  cutoff = FALSE;
1598  nfixedvars = 0;
1599 
1600  /* propagate all useful constraints */
1601  for( c = 0; c < nusefulconss && !cutoff; ++c )
1602  {
1603  SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars) );
1604  }
1605 
1606  /* return the correct result */
1607  if( cutoff )
1608  *result = SCIP_CUTOFF;
1609  else if( nfixedvars > 0 )
1610  *result = SCIP_REDUCEDDOM;
1611  else
1612  *result = SCIP_DIDNOTFIND;
1613 
1614  return SCIP_OKAY;
1615 }
1616 
1617 
1618 /** presolving method of constraint handler */
1619 static
1620 SCIP_DECL_CONSPRESOL(consPresolOr)
1621 { /*lint --e{715}*/
1622  SCIP_CONSHDLRDATA* conshdlrdata;
1623  SCIP_CONS* cons;
1624  SCIP_CONSDATA* consdata;
1625  SCIP_Bool cutoff;
1626  SCIP_Bool redundant;
1627  SCIP_Bool aggregated;
1628  int oldnfixedvars;
1629  int oldnaggrvars;
1630  int oldnupgdconss;
1631  int c;
1632 
1633  assert(result != NULL);
1634 
1635  *result = SCIP_DIDNOTFIND;
1636  oldnfixedvars = *nfixedvars;
1637  oldnaggrvars = *naggrvars;
1638  oldnupgdconss = *nupgdconss;
1639 
1640  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1641  assert(conshdlrdata != NULL);
1642 
1643  /* process constraints */
1644  cutoff = FALSE;
1645  for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
1646  {
1647  cons = conss[c];
1648  assert(cons != NULL);
1649  consdata = SCIPconsGetData(cons);
1650  assert(consdata != NULL);
1651 
1652  /* force presolving the constraint in the initial round */
1653  if( nrounds == 0 )
1654  consdata->propagated = FALSE;
1655 
1656  /* propagate constraint */
1657  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars) );
1658 
1659  /* remove all variables that are fixed to one */
1660  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr) );
1661 
1662  /* transform or constraints into and constraints on the negated variables in order to improve
1663  * the pairwise constraint presolving possibilities
1664  */
1665  SCIP_CALL( upgradeCons(scip, cons, nupgdconss) );
1666 
1667  if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
1668  {
1669  assert(consdata->nvars >= 1); /* otherwise, propagateCons() has deleted the constraint */
1670 
1671  /* if only one variable is left, the resultant has to be equal to this single variable */
1672  if( consdata->nvars == 1 )
1673  {
1674  SCIPdebugMessage("or constraint <%s> has only one variable not fixed to 0.0\n", SCIPconsGetName(cons));
1675 
1676  assert(consdata->vars != NULL);
1677  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
1678  assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
1679 
1680  /* aggregate variables: resultant - operand == 0 */
1681  SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
1682  &cutoff, &redundant, &aggregated) );
1683  assert(redundant || SCIPdoNotAggr(scip));
1684 
1685  if( aggregated )
1686  {
1687  assert(redundant);
1688  (*naggrvars)++;
1689  }
1690 
1691  if( redundant )
1692  {
1693  /* delete constraint */
1694  SCIP_CALL( SCIPdelCons(scip, cons) );
1695  (*ndelconss)++;
1696  }
1697  }
1698  else if( !consdata->impladded )
1699  {
1700  int i;
1701 
1702  /* add implications: resultant == 0 -> all operands == 0 */
1703  for( i = 0; i < consdata->nvars && !cutoff; ++i )
1704  {
1705  int nimplbdchgs;
1706 
1707  SCIP_CALL( SCIPaddVarImplication(scip, consdata->resvar, FALSE, consdata->vars[i],
1708  SCIP_BOUNDTYPE_UPPER, 0.0, &cutoff, &nimplbdchgs) );
1709  *nchgbds += nimplbdchgs;
1710  }
1711  consdata->impladded = TRUE;
1712  }
1713 
1714  /* if in r = x or y, the resultant is fixed to one, add implication x = 0 -> y = 1 */
1715  if( !cutoff && SCIPconsIsActive(cons) && consdata->nvars == 2 && !consdata->opimpladded
1716  && SCIPvarGetLbGlobal(consdata->resvar) > 0.5 )
1717  {
1718  int nimplbdchgs;
1719 
1720  SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], FALSE, consdata->vars[1],
1721  SCIP_BOUNDTYPE_LOWER, 1.0, &cutoff, &nimplbdchgs) );
1722  (*nchgbds) += nimplbdchgs;
1723  consdata->opimpladded = TRUE;
1724  }
1725  }
1726  }
1727 
1728  /* return the correct result code */
1729  if( cutoff )
1730  *result = SCIP_CUTOFF;
1731  else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nupgdconss > oldnupgdconss )
1732  *result = SCIP_SUCCESS;
1733 
1734  return SCIP_OKAY;
1735 }
1736 
1737 
1738 /** propagation conflict resolving method of constraint handler */
1739 static
1740 SCIP_DECL_CONSRESPROP(consRespropOr)
1741 { /*lint --e{715}*/
1742  SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
1743 
1744  return SCIP_OKAY;
1745 }
1746 
1747 
1748 /** variable rounding lock method of constraint handler */
1749 static
1750 SCIP_DECL_CONSLOCK(consLockOr)
1751 { /*lint --e{715}*/
1752  SCIP_CONSDATA* consdata;
1753  int i;
1754 
1755  consdata = SCIPconsGetData(cons);
1756  assert(consdata != NULL);
1757 
1758  /* lock resultant variable */
1759  SCIP_CALL( SCIPaddVarLocks(scip, consdata->resvar, nlockspos + nlocksneg, nlockspos + nlocksneg) );
1760 
1761  /* lock all operand variables */
1762  for( i = 0; i < consdata->nvars; ++i )
1763  {
1764  SCIP_CALL( SCIPaddVarLocks(scip, consdata->vars[i], nlockspos + nlocksneg, nlockspos + nlocksneg) );
1765  }
1766 
1767  return SCIP_OKAY;
1768 }
1769 
1770 
1771 /** constraint display method of constraint handler */
1772 static
1773 SCIP_DECL_CONSPRINT(consPrintOr)
1774 { /*lint --e{715}*/
1775 
1776  assert( scip != NULL );
1777  assert( conshdlr != NULL );
1778  assert( cons != NULL );
1779 
1780  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file) );
1781 
1782  return SCIP_OKAY;
1783 }
1784 
1785 /** constraint copying method of constraint handler */
1786 static
1787 SCIP_DECL_CONSCOPY(consCopyOr)
1788 { /*lint --e{715}*/
1789  SCIP_VAR** sourcevars;
1790  SCIP_VAR** vars;
1791  SCIP_VAR* sourceresvar;
1792  SCIP_VAR* resvar;
1793  int nvars;
1794  int v;
1795 
1796  assert(valid != NULL);
1797  (*valid) = TRUE;
1798  resvar = NULL;
1799 
1800  /* get variables that need to be copied */
1801  sourceresvar = SCIPgetResultantOr(sourcescip, sourcecons);
1802  sourcevars = SCIPgetVarsOr(sourcescip, sourcecons);
1803  nvars = SCIPgetNVarsOr(sourcescip, sourcecons);
1804 
1805  /* allocate buffer array */
1806  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1807 
1808  /* map operand variables to active variables of the target SCIP */
1809  for( v = 0; v < nvars && *valid; ++v )
1810  {
1811  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
1812  assert(!(*valid) || vars[v] != NULL);
1813  }
1814 
1815  /* map resultant to active variable of the target SCIP */
1816  if( *valid )
1817  {
1818  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceresvar, &resvar, varmap, consmap, global, valid) );
1819  assert(!(*valid) || resvar != NULL);
1820 
1821  if( *valid )
1822  {
1823  assert(resvar != NULL);
1824  SCIP_CALL( SCIPcreateConsOr(scip, cons, SCIPconsGetName(sourcecons), resvar, nvars, vars,
1825  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1826  }
1827  }
1828 
1829  /* free buffer array */
1830  SCIPfreeBufferArray(scip, &vars);
1831 
1832  return SCIP_OKAY;
1833 }
1834 
1835 /** constraint parsing method of constraint handler */
1836 static
1837 SCIP_DECL_CONSPARSE(consParseOr)
1838 { /*lint --e{715}*/
1839  SCIP_VAR** vars;
1840  SCIP_VAR* resvar;
1841  char* strcopy;
1842  char* token;
1843  char* saveptr;
1844  char* endptr;
1845  int requiredsize;
1846  int varssize;
1847  int nvars;
1848 
1849  SCIPdebugMessage("parse <%s> as or constraint\n", str);
1850 
1851  /* copy string for truncating it */
1852  SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, str, (int)(strlen(str)+1)));
1853 
1854  /* cutoff "or" form the constraint string */
1855  token = SCIPstrtok(strcopy, "=", &saveptr );
1856 
1857  /* parse variable name */
1858  SCIP_CALL( SCIPparseVarName(scip, token, &resvar, &endptr) );
1859 
1860  if( resvar == NULL )
1861  {
1862  SCIPdebugMessage("resultant variable %s does not exist \n", token);
1863  *success = FALSE;
1864  }
1865  else
1866  {
1867  /* cutoff "or" form the constraint string */
1868  (void) SCIPstrtok(NULL, "(", &saveptr );
1869 
1870  /* cutoff ")" form the constraint string */
1871  token = SCIPstrtok(NULL, ")", &saveptr );
1872 
1873  varssize = 100;
1874  nvars = 0;
1875 
1876  /* allocate buffer array for variables */
1877  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
1878 
1879  /* parse string */
1880  SCIP_CALL( SCIPparseVarsList(scip, token, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
1881 
1882  if( *success )
1883  {
1884  /* check if the size of the variable array was great enough */
1885  if( varssize < requiredsize )
1886  {
1887  /* reallocate memory */
1888  varssize = requiredsize;
1889  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
1890 
1891  /* parse string again with the correct size of the variable array */
1892  SCIP_CALL( SCIPparseVarsList(scip, token, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
1893  }
1894 
1895  assert(*success);
1896  assert(varssize >= requiredsize);
1897 
1898  /* create and constraint */
1899  SCIP_CALL( SCIPcreateConsOr(scip, cons, name, resvar, nvars, vars,
1900  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1901  }
1902 
1903  /* free variable buffer */
1904  SCIPfreeBufferArray(scip, &vars);
1905  }
1906 
1907  /* free string buffer */
1908  SCIPfreeBufferArray(scip, &strcopy);
1909 
1910  return SCIP_OKAY;
1911 }
1912 
1913 /** constraint method of constraint handler which returns the variables (if possible) */
1914 static
1915 SCIP_DECL_CONSGETVARS(consGetVarsOr)
1916 { /*lint --e{715}*/
1917  SCIP_CONSDATA* consdata;
1918 
1919  consdata = SCIPconsGetData(cons);
1920  assert(consdata != NULL);
1921 
1922  if( varssize < consdata->nvars + 1 )
1923  (*success) = FALSE;
1924  else
1925  {
1926  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
1927  vars[consdata->nvars] = consdata->resvar;
1928  (*success) = TRUE;
1929  }
1930 
1931  return SCIP_OKAY;
1932 }
1933 
1934 /** constraint method of constraint handler which returns the number of variable (if possible) */
1935 static
1936 SCIP_DECL_CONSGETNVARS(consGetNVarsOr)
1937 { /*lint --e{715}*/
1938  SCIP_CONSDATA* consdata;
1939 
1940  assert(cons != NULL);
1941 
1942  consdata = SCIPconsGetData(cons);
1943  assert(consdata != NULL);
1944 
1945  (*nvars) = consdata->nvars + 1;
1946  (*success) = TRUE;
1947 
1948  return SCIP_OKAY;
1949 }
1950 
1951 
1952 /*
1953  * Callback methods of event handler
1954  */
1955 
1956 static
1957 SCIP_DECL_EVENTEXEC(eventExecOr)
1958 { /*lint --e{715}*/
1959  SCIP_CONSDATA* consdata;
1960 
1961  assert(eventhdlr != NULL);
1962  assert(eventdata != NULL);
1963  assert(event != NULL);
1964 
1965  consdata = (SCIP_CONSDATA*)eventdata;
1966  assert(consdata != NULL);
1967 
1968  /* check, if the variable was fixed to one */
1969  if( SCIPeventGetType(event) == SCIP_EVENTTYPE_LBTIGHTENED )
1970  consdata->nofixedone = FALSE;
1971 
1972  consdata->propagated = FALSE;
1973 
1974  return SCIP_OKAY;
1975 }
1976 
1977 
1978 /*
1979  * constraint specific interface methods
1980  */
1981 
1982 /** creates the handler for or constraints and includes it in SCIP */
1983 SCIP_RETCODE SCIPincludeConshdlrOr(
1984  SCIP* scip /**< SCIP data structure */
1985  )
1986 {
1987  SCIP_CONSHDLRDATA* conshdlrdata;
1988  SCIP_CONSHDLR* conshdlr;
1989  SCIP_EVENTHDLR* eventhdlr;
1990 
1991  /* create event handler for events on variables */
1992  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
1993  eventExecOr, NULL) );
1994 
1995  /* create constraint handler data */
1996  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
1997 
1998  /* include constraint handler */
1999  SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2000  CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2001  consEnfolpOr, consEnfopsOr, consCheckOr, consLockOr,
2002  conshdlrdata) );
2003  assert(conshdlr != NULL);
2004 
2005  /* set non-fundamental callbacks via specific setter functions */
2006  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOr, consCopyOr) );
2007  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOr) );
2008  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolOr) );
2009  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOr) );
2010  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOr) );
2011  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOr) );
2012  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpOr) );
2013  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOr) );
2014  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOr, CONSHDLR_MAXPREROUNDS, CONSHDLR_DELAYPRESOL) );
2015  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOr) );
2016  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOr, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
2017  CONSHDLR_PROP_TIMING) );
2018  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOr) );
2019  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOr, consSepasolOr, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY,
2020  CONSHDLR_DELAYSEPA) );
2021  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOr) );
2022 
2023 
2024  return SCIP_OKAY;
2025 }
2026 
2027 /** creates and captures an or constraint
2028  *
2029  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2030  */
2031 SCIP_RETCODE SCIPcreateConsOr(
2032  SCIP* scip, /**< SCIP data structure */
2033  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2034  const char* name, /**< name of constraint */
2035  SCIP_VAR* resvar, /**< resultant variable of the operation */
2036  int nvars, /**< number of operator variables in the constraint */
2037  SCIP_VAR** vars, /**< array with operator variables of constraint */
2038  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2039  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2040  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2041  * Usually set to TRUE. */
2042  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2043  * TRUE for model constraints, FALSE for additional, redundant constraints. */
2044  SCIP_Bool check, /**< should the constraint be checked for feasibility?
2045  * TRUE for model constraints, FALSE for additional, redundant constraints. */
2046  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2047  * Usually set to TRUE. */
2048  SCIP_Bool local, /**< is constraint only valid locally?
2049  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2050  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2051  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2052  * adds coefficients to this constraint. */
2053  SCIP_Bool dynamic, /**< is constraint subject to aging?
2054  * Usually set to FALSE. Set to TRUE for own cuts which
2055  * are separated as constraints. */
2056  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2057  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2058  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2059  * if it may be moved to a more global node?
2060  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2061  )
2062 {
2063  SCIP_CONSHDLR* conshdlr;
2064  SCIP_CONSHDLRDATA* conshdlrdata;
2065  SCIP_CONSDATA* consdata;
2066 
2067  /* find the or constraint handler */
2068  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2069  if( conshdlr == NULL )
2070  {
2071  SCIPerrorMessage("or constraint handler not found\n");
2072  return SCIP_PLUGINNOTFOUND;
2073  }
2074 
2075  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2076  assert(conshdlrdata != NULL);
2077 
2078  /* create constraint data */
2079  SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, resvar) );
2080 
2081  /* create constraint */
2082  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2083  local, modifiable, dynamic, removable, stickingatnode) );
2084 
2085  return SCIP_OKAY;
2086 }
2087 
2088 /** creates and captures an or constraint
2089  * in its most basic variant, i. e., with all constraint flags set to their default values
2090  *
2091  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2092  */
2093 SCIP_RETCODE SCIPcreateConsBasicOr(
2094  SCIP* scip, /**< SCIP data structure */
2095  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2096  const char* name, /**< name of constraint */
2097  SCIP_VAR* resvar, /**< resultant variable of the operation */
2098  int nvars, /**< number of operator variables in the constraint */
2099  SCIP_VAR** vars /**< array with operator variables of constraint */
2100  )
2101 {
2102  SCIP_CALL( SCIPcreateConsOr(scip, cons, name, resvar, nvars, vars, TRUE, TRUE, TRUE, TRUE, TRUE,
2103  FALSE, FALSE, FALSE, FALSE, FALSE) );
2104 
2105  return SCIP_OKAY;
2106 }
2107 
2108 /** gets number of variables in or constraint */
2109 int SCIPgetNVarsOr(
2110  SCIP* scip, /**< SCIP data structure */
2111  SCIP_CONS* cons /**< constraint data */
2112  )
2113 {
2114  SCIP_CONSDATA* consdata;
2115 
2116  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2117  {
2118  SCIPerrorMessage("constraint is not an or constraint\n");
2119  SCIPABORT();
2120  return -1; /*lint !e527*/
2121  }
2122 
2123  consdata = SCIPconsGetData(cons);
2124  assert(consdata != NULL);
2125 
2126  return consdata->nvars;
2127 }
2128 
2129 /** gets array of variables in or constraint */
2130 SCIP_VAR** SCIPgetVarsOr(
2131  SCIP* scip, /**< SCIP data structure */
2132  SCIP_CONS* cons /**< constraint data */
2133  )
2134 {
2135  SCIP_CONSDATA* consdata;
2136 
2137  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2138  {
2139  SCIPerrorMessage("constraint is not an or constraint\n");
2140  SCIPABORT();
2141  return NULL; /*lint !e527*/
2142  }
2143 
2144  consdata = SCIPconsGetData(cons);
2145  assert(consdata != NULL);
2146 
2147  return consdata->vars;
2148 }
2149 
2150 /** gets the resultant variable in or constraint */
2151 SCIP_VAR* SCIPgetResultantOr(
2152  SCIP* scip, /**< SCIP data structure */
2153  SCIP_CONS* cons /**< constraint data */
2154  )
2155 {
2156  SCIP_CONSDATA* consdata;
2157 
2158  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2159  {
2160  SCIPerrorMessage("constraint is not a or constraint\n");
2161  SCIPABORT();
2162  return NULL; /*lint !e527*/
2163  }
2164 
2165  consdata = SCIPconsGetData(cons);
2166  assert(consdata != NULL);
2167 
2168  return consdata->resvar;
2169 }
2170