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