Scippy

SCIP

Solving Constraint Integer Programs

cons_bounddisjunction.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-2016 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_bounddisjunction.c
17  * @brief constraint handler for bound disjunction constraints \f$(x_1 \{\leq,\geq\} b_1) \vee \ldots \vee (x_n \{\leq,\geq\} b_n)\f$
18  * @author Tobias Achterberg
19  * @author Marc Pfetsch
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 #include <limits.h>
27 #include <ctype.h>
28 
30 #include "scip/cons_quadratic.h"
31 #include "scip/cons_linear.h"
32 #include "scip/cons_logicor.h"
33 #include "scip/cons_setppc.h"
34 #include "scip/pub_misc.h"
35 
36 /**@name Constraint handler properties
37  *
38  * @{
39  */
40 
41 #define CONSHDLR_NAME "bounddisjunction"
42 #define CONSHDLR_DESC "bound disjunction constraints"
43 #define CONSHDLR_ENFOPRIORITY -3000000 /**< priority of the constraint handler for constraint enforcing */
44 #define CONSHDLR_CHECKPRIORITY -3000000 /**< priority of the constraint handler for checking feasibility */
45 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
46 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
47  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
48 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
49 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
50 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
51 
52 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST
53 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
54 
55 #define QUADCONSUPGD_PRIORITY 500000 /**< priority of the constraint handler for upgrading of quadratic constraints */
56 
57 /**@} */
58 
59 /**@name Event handler properties
60  *
61  * @{
62  */
63 
64 #define EVENTHDLR_NAME "bounddisjunction"
65 #define EVENTHDLR_DESC "event handler for bound disjunction constraints"
66 
67 /**@} */
68 
69 /**@name Conflict handler properties
70  *
71  * @{
72  */
73 
74 #define CONFLICTHDLR_NAME "bounddisjunction"
75 #define CONFLICTHDLR_DESC "conflict handler creating bound disjunction constraints"
76 #define CONFLICTHDLR_PRIORITY -3000000
77 
78 /**@} */
79 
80 /**@name Default parameter values
81  *
82  * @{
83  */
84 
85 #define DEFAULT_CONTINUOUSFRAC 0.4 /**< maximal percantage of continuous variables within a conflict */
86 
87 /**@} */
88 
89 /**@name Age increase defines
90  *
91  * @{
92  */
93 
94 /* @todo make this a parameter setting */
95 #if 1 /* @todo test which AGEINCREASE formula is better! */
96 #define AGEINCREASE(n) (1.0 + 0.2*n)
97 #else
98 #define AGEINCREASE(n) (0.1*n)
99 #endif
100 
101 /**@} */
102 
103 
104 /**@name Comparison for two values
105  *
106  * @{
107  */
108 
109 #ifdef SCIP_DISABLED_CODE /* These only work if one also passes integral values in case of integral variables. This is not always the case and not even asserted. */
110 /** use defines for numeric compare methods to be slightly faster for integral values */
111 #define isFeasLT(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val2) - (val1) > 0.5 : SCIPisFeasLT(scip, val1, val2))
112 #define isFeasLE(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val2) - (val1) > -0.5 : SCIPisFeasLE(scip, val1, val2))
113 #define isFeasGT(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val1) - (val2) > 0.5 : SCIPisFeasGT(scip, val1, val2))
114 #define isFeasGE(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val1) - (val2) > -0.5 : SCIPisFeasGE(scip, val1, val2))
115 #else
116 #define isFeasLT(scip, var, val1, val2) SCIPisFeasLT(scip, val1, val2)
117 #define isFeasLE(scip, var, val1, val2) SCIPisFeasLE(scip, val1, val2)
118 #define isFeasGT(scip, var, val1, val2) SCIPisFeasGT(scip, val1, val2)
119 #define isFeasGE(scip, var, val1, val2) SCIPisFeasGE(scip, val1, val2)
120 #endif
121 /**@} */
122 
123 
124 /** constraint handler data */
125 struct SCIP_ConshdlrData
126 {
127  SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */
128 };
129 
130 /** bound disjunction constraint data */
131 struct SCIP_ConsData
132 {
133  SCIP_VAR** vars; /**< variables of the literals in the constraint */
134  SCIP_BOUNDTYPE* boundtypes; /**< types of bounds of the literals (lower or upper bounds) */
135  SCIP_Real* bounds; /**< bounds of the literals */
136  int varssize; /**< size of vars, boundtypes, and bounds arrays */
137  int nvars; /**< number of variables in the constraint */
138  int watchedvar1; /**< position of the first watched variable */
139  int watchedvar2; /**< position of the second watched variable */
140  int filterpos1; /**< event filter position of first watched variable */
141  int filterpos2; /**< event filter position of second watched variable */
142 };
143 
144 /**@name Local methods
145  *
146  */
147 
148 /** adds rounding locks for the given variable in the given bound disjunction constraint */
149 static
151  SCIP* scip, /**< SCIP data structure */
152  SCIP_CONS* cons, /**< bound disjunction constraint */
153  SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
154  int pos /**< position of the variable in the constraint */
155  )
156 {
157  assert(consdata != NULL);
158  assert(0 <= pos && pos < consdata->nvars);
159 
160  if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
161  {
162  /* rounding down may violate the constraint */
163  SCIP_CALL( SCIPlockVarCons(scip, consdata->vars[pos], cons, TRUE, FALSE) );
164  }
165  else
166  {
167  /* rounding up may violate the constraint */
168  SCIP_CALL( SCIPlockVarCons(scip, consdata->vars[pos], cons, FALSE, TRUE) );
169  }
170 
171  return SCIP_OKAY;
172 }
173 
174 /** removes rounding locks for the given variable in the given bound disjunction constraint */
175 static
177  SCIP* scip, /**< SCIP data structure */
178  SCIP_CONS* cons, /**< bound disjunction constraint */
179  SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
180  int pos /**< position of the variable in the constraint */
181  )
182 {
183  assert(consdata != NULL);
184  assert(0 <= pos && pos < consdata->nvars);
185 
186  if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
187  {
188  /* rounding down may violate the constraint */
189  SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, TRUE, FALSE) );
190  }
191  else
192  {
193  /* rounding up may violate the constraint */
194  SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, FALSE, TRUE) );
195  }
196 
197  return SCIP_OKAY;
198 }
199 
200 /** catches the events on a single variable of the bound disjunction constraint */
201 static
203  SCIP* scip, /**< SCIP data structure */
204  SCIP_CONS* cons, /**< bound disjunction constraint */
205  SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
206  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
207  int pos, /**< position of the variable in the constraint */
208  int* filterpos /**< pointer to store position of event filter entry, or NULL */
209  )
210 {
211  assert(consdata != NULL);
212  assert(0 <= pos && pos < consdata->nvars);
213 
214  if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
215  {
217  eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
218  }
219  else
220  {
222  eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
223  }
224 
225  return SCIP_OKAY;
226 }
227 
228 /** drops the events on a single variable of the bound disjunction constraint */
229 static
231  SCIP* scip, /**< SCIP data structure */
232  SCIP_CONS* cons, /**< bound disjunction constraint */
233  SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
234  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
235  int pos, /**< position of the variable in the constraint */
236  int filterpos /**< position of event filter entry returned by SCIPcatchVarEvent(), or -1 */
237  )
238 {
239  assert(consdata != NULL);
240  assert(0 <= pos && pos < consdata->nvars);
241 
242  if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
243  {
245  eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
246  }
247  else
248  {
250  eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
251  }
252 
253  return SCIP_OKAY;
254 }
255 
256 /** creates constraint handler data for bound disjunction constraint handler */
257 static
259  SCIP* scip, /**< SCIP data structure */
260  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
261  SCIP_EVENTHDLR* eventhdlr /**< event handler */
262  )
263 {
264  assert(scip != NULL);
265  assert(conshdlrdata != NULL);
266  assert(eventhdlr != NULL);
267 
268  SCIP_CALL( SCIPallocMemory(scip, conshdlrdata) );
269 
270  /* set event handler for catching events on watched variables */
271  (*conshdlrdata)->eventhdlr = eventhdlr;
272 
273  return SCIP_OKAY;
274 }
275 
276 /** frees constraint handler data for bound disjunction constraint handler */
277 static
279  SCIP* scip, /**< SCIP data structure */
280  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
281  )
282 {
283  assert(conshdlrdata != NULL);
284  assert(*conshdlrdata != NULL);
285 
286  SCIPfreeMemory(scip, conshdlrdata);
287 
288  return SCIP_OKAY;
289 }
290 
291 /** creates a bound disjunction constraint data object */
292 static
294  SCIP* scip, /**< SCIP data structure */
295  SCIP_CONSDATA** consdata, /**< pointer to store the bound disjunction constraint data */
296  int nvars, /**< number of variables in the constraint */
297  SCIP_VAR** vars, /**< variables of the literals in the constraint */
298  SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
299  SCIP_Real* bounds /**< bounds of the literals */
300  )
301 {
302  assert(consdata != NULL);
303  assert(nvars == 0 || vars != NULL);
304  assert(nvars == 0 || boundtypes != NULL);
305  assert(nvars == 0 || bounds != NULL);
306 
307  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
308 
309  if( nvars > 0 )
310  {
311  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
312  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypes, nvars) );
313  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, bounds, nvars) );
314  (*consdata)->varssize = nvars;
315  (*consdata)->nvars = nvars;
316  }
317  else
318  {
319  (*consdata)->vars = NULL;
320  (*consdata)->boundtypes = NULL;
321  (*consdata)->bounds = NULL;
322  (*consdata)->varssize = 0;
323  (*consdata)->nvars = 0;
324  }
325  (*consdata)->watchedvar1 = -1;
326  (*consdata)->watchedvar2 = -1;
327  (*consdata)->filterpos1 = -1;
328  (*consdata)->filterpos2 = -1;
329 
330  /* get transformed variables, if we are in the transformed problem */
331  if( SCIPisTransformed(scip) )
332  {
333  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
334  }
335 
336  return SCIP_OKAY;
337 }
338 
339 /** frees a bound disjunction constraint data */
340 static
342  SCIP* scip, /**< SCIP data structure */
343  SCIP_CONSDATA** consdata /**< pointer to the bound disjunction constraint */
344  )
345 {
346  assert(consdata != NULL);
347  assert(*consdata != NULL);
348 
349  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
350  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->boundtypes, (*consdata)->varssize);
351  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->bounds, (*consdata)->varssize);
352  SCIPfreeBlockMemory(scip, consdata);
353 
354  return SCIP_OKAY;
355 }
356 
357 /** prints bound disjunction constraint to file stream */
358 static
359 void consdataPrint(
360  SCIP* scip, /**< SCIP data structure */
361  SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
362  FILE* file, /**< output file (or NULL for standard output) */
363  SCIP_Bool endline /**< should an endline be set? */
364  )
365 {
366  int v;
367 
368  assert(consdata != NULL);
369 
370  /* print coefficients */
371  SCIPinfoMessage(scip, file, "bounddisjunction(");
372  for( v = 0; v < consdata->nvars; ++v )
373  {
374  assert(consdata->vars[v] != NULL);
375  if( v > 0 )
376  SCIPinfoMessage(scip, file, ", ");
377  SCIPinfoMessage(scip, file, "<%s> %s %.15g", SCIPvarGetName(consdata->vars[v]),
378  consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", consdata->bounds[v]);
379  }
380  SCIPinfoMessage(scip, file, ")");
381 
382  if( endline )
383  SCIPinfoMessage(scip, file, "\n");
384 }
385 
386 /** stores the given variable numbers as watched variables, and updates the event processing */
387 static
389  SCIP* scip, /**< SCIP data structure */
390  SCIP_CONS* cons, /**< bound disjunction constraint */
391  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
392  int watchedvar1, /**< new first watched variable */
393  int watchedvar2 /**< new second watched variable */
394  )
395 {
396  SCIP_CONSDATA* consdata;
397 
398  consdata = SCIPconsGetData(cons);
399  assert(consdata != NULL);
400  assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
401  assert(watchedvar1 != -1 || watchedvar2 == -1);
402  assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
403  assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
404 
405  /* if one watched variable is equal to the old other watched variable, just switch positions */
406  if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
407  {
408  int tmp;
409 
410  tmp = consdata->watchedvar1;
411  consdata->watchedvar1 = consdata->watchedvar2;
412  consdata->watchedvar2 = tmp;
413  tmp = consdata->filterpos1;
414  consdata->filterpos1 = consdata->filterpos2;
415  consdata->filterpos2 = tmp;
416  }
417  assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
418  assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
419 
420  /* drop events on old watched variables */
421  if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
422  {
423  assert(consdata->filterpos1 != -1);
424  SCIP_CALL( dropEvents(scip, cons, consdata, eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
425  }
426  if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
427  {
428  assert(consdata->filterpos2 != -1);
429  SCIP_CALL( dropEvents(scip, cons, consdata, eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
430  }
431 
432  /* catch events on new watched variables */
433  if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
434  {
435  SCIP_CALL( catchEvents(scip, cons, consdata, eventhdlr, watchedvar1, &consdata->filterpos1) );
436  }
437  if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
438  {
439  SCIP_CALL( catchEvents(scip, cons, consdata, eventhdlr, watchedvar2, &consdata->filterpos2) );
440  }
441 
442  /* set the new watched variables */
443  consdata->watchedvar1 = watchedvar1;
444  consdata->watchedvar2 = watchedvar2;
445 
446  return SCIP_OKAY;
447 }
448 
449 /** deletes coefficient at given position from bound disjunction constraint data */
450 static
452  SCIP* scip, /**< SCIP data structure */
453  SCIP_CONS* cons, /**< bound disjunction constraint */
454  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
455  int pos /**< position of coefficient to delete */
456  )
457 {
458  SCIP_CONSDATA* consdata;
459 
460  assert(eventhdlr != NULL);
461 
462  consdata = SCIPconsGetData(cons);
463  assert(consdata != NULL);
464  assert(0 <= pos && pos < consdata->nvars);
465  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
466 
467  /* remove the rounding locks of variable */
468  SCIP_CALL( unlockRounding(scip, cons, consdata, pos) );
469 
470  if( SCIPconsIsTransformed(cons) )
471  {
472  /* if the position is watched, stop watching the position */
473  if( consdata->watchedvar1 == pos )
474  {
475  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar2, -1) );
476  }
477  if( consdata->watchedvar2 == pos )
478  {
479  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, -1) );
480  }
481  }
482  assert(pos != consdata->watchedvar1);
483  assert(pos != consdata->watchedvar2);
484 
485  /* move the last variable to the free slot */
486  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
487  consdata->boundtypes[pos] = consdata->boundtypes[consdata->nvars-1];
488  consdata->bounds[pos] = consdata->bounds[consdata->nvars-1];
489  consdata->nvars--;
490 
491  /* if the last variable (that moved) was watched, update the watched position */
492  if( consdata->watchedvar1 == consdata->nvars )
493  consdata->watchedvar1 = pos;
494  if( consdata->watchedvar2 == consdata->nvars )
495  consdata->watchedvar2 = pos;
496 
497  SCIP_CALL( SCIPenableConsPropagation(scip, cons) );
498 
499  return SCIP_OKAY;
500 }
501 
502 /** adds literal to bound disjunction constraint data */
503 static
505  SCIP* scip, /**< SCIP data structure */
506  SCIP_CONS* cons, /**< bound disjunction constraint */
507  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
508  SCIP_VAR* var, /**< variable in literal */
509  SCIP_BOUNDTYPE boundtype, /**< boundtype of literal */
510  SCIP_Real bound /**< bound of literal */
511  )
512 {
513  SCIP_CONSDATA* consdata;
514 
515  assert(eventhdlr != NULL);
516 
517  consdata = SCIPconsGetData(cons);
518  assert(consdata != NULL);
519  assert(var != NULL);
520  assert(!SCIPisInfinity(scip, REALABS(bound)));
521  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var));
522 
523  /* ensure enough memory in consdata arrays */
524  if( consdata->varssize == consdata->nvars )
525  {
526  int newsize;
527 
528  newsize = SCIPcalcMemGrowSize(scip, consdata->nvars + 1);
529  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
530  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->boundtypes, consdata->varssize, newsize) );
531  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->bounds, consdata->varssize, newsize) );
532  consdata->varssize = newsize;
533  }
534  assert(consdata->varssize > consdata->nvars);
535 
536  /* add the variable to the end of the array */
537  consdata->vars[consdata->nvars] = var;
538  consdata->boundtypes[consdata->nvars] = boundtype;
539  consdata->bounds[consdata->nvars] = bound;
540  consdata->nvars++;
541 
542  if( SCIPconsIsTransformed(cons) )
543  {
544  /* add rounding lock of variable */
545  SCIP_CALL( lockRounding(scip, cons, consdata, consdata->nvars-1) );
546 
547  /* if less than 2 variables are watched, add the new one to the watched variables */
548  if( consdata->watchedvar1 == -1 )
549  {
550  assert(consdata->watchedvar2 == -1);
551  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->nvars-1, -1) );
552  }
553  else if( consdata->watchedvar2 == -1 )
554  {
555  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, consdata->nvars-1) );
556  }
557  }
558 
559  SCIP_CALL( SCIPenableConsPropagation(scip, cons) );
560 
561  return SCIP_OKAY;
562 }
563 
564 /** deletes all variables with global bounds violating the literal, checks for global bounds satisfying the literal */
565 static
567  SCIP* scip, /**< SCIP data structure */
568  SCIP_CONS* cons, /**< bound disjunction constraint */
569  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
570  SCIP_Bool* redundant /**< returns whether a variable fixed to one exists in the constraint */
571  )
572 {
573  SCIP_CONSDATA* consdata;
574  int v;
575  SCIP_Real bnd;
576 
577  assert(eventhdlr != NULL);
578  assert(redundant != NULL);
579 
580  consdata = SCIPconsGetData(cons);
581  assert(consdata != NULL);
582  assert(consdata->nvars == 0 || consdata->vars != NULL);
583 
584  *redundant = FALSE;
585  v = 0;
586  while( v < consdata->nvars )
587  {
588  SCIP_VAR* var;
589 
590  var = consdata->vars[v];
591 
592  if( consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
593  {
594  bnd = SCIPcomputeVarLbGlobal(scip, var);
595  if( isFeasGE(scip, var, bnd, consdata->bounds[v]) )
596  {
597  *redundant = TRUE;
598  return SCIP_OKAY;
599  }
600  else
601  {
602  bnd = SCIPcomputeVarUbGlobal(scip, var);
603  if( isFeasLT(scip, var, bnd, consdata->bounds[v]) )
604  {
605  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
606  }
607  else
608  ++v;
609  }
610  }
611  else
612  {
613  assert(consdata->boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
614  bnd = SCIPcomputeVarUbGlobal(scip, var);
615  if( isFeasLE(scip, var, bnd, consdata->bounds[v]) )
616  {
617  *redundant = TRUE;
618  return SCIP_OKAY;
619  }
620  else
621  {
622  bnd = SCIPcomputeVarLbGlobal(scip, var);
623  if( isFeasGT(scip, var, bnd, consdata->bounds[v]) )
624  {
625  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
626  }
627  else
628  ++v;
629  }
630  }
631  }
632 
633  SCIPdebugMessage("after global bounds: ");
634  SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE));
635 
636  return SCIP_OKAY;
637 }
638 
639 /** returns whether literal at the given position is satisfied in the local bounds */
640 static
642  SCIP* scip, /**< SCIP data structure */
643  SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
644  int pos /**< position of the literal */
645  )
646 {
647  SCIP_Real bnd;
648 
649  assert(consdata != NULL);
650  assert(0 <= pos && pos < consdata->nvars);
651 
652  if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
653  {
654  bnd = SCIPcomputeVarLbLocal(scip, consdata->vars[pos]);
655  return isFeasGE(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
656  }
657  else
658  {
659  bnd = SCIPcomputeVarUbLocal(scip, consdata->vars[pos]);
660  return isFeasLE(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
661  }
662 }
663 
664 /** returns whether literal at the given position is violated in the local bounds */
665 static
667  SCIP* scip, /**< SCIP data structure */
668  SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
669  int pos /**< position of the literal */
670  )
671 {
672  SCIP_Real bnd;
673 
674  assert(consdata != NULL);
675  assert(0 <= pos && pos < consdata->nvars);
676 
677  if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
678  {
679  bnd = SCIPcomputeVarUbLocal(scip, consdata->vars[pos]);
680  return isFeasLT(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
681  }
682  else
683  {
684  bnd = SCIPcomputeVarLbLocal(scip, consdata->vars[pos]);
685  return isFeasGT(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
686  }
687 }
688 
689 /** replace variables by their representative active (or multi-aggregated) variables */
690 static
692  SCIP* scip, /**< SCIP data structure */
693  SCIP_CONS* cons, /**< bound disjunction constraint */
694  SCIP_EVENTHDLR* eventhdlr, /**< event handler */
695  SCIP_Bool* redundant /**< flag to indicate whether constraint has been bound redundant */
696  )
697 {
698  SCIP_CONSDATA* consdata;
699  SCIP_VAR* var;
700  SCIP_BOUNDTYPE boundtype;
701  SCIP_Real bound;
702  int v;
703 
704  assert(scip != NULL);
705  assert(cons != NULL);
706  assert(eventhdlr != NULL);
707 
708  consdata = SCIPconsGetData(cons);
709  assert(consdata != NULL);
710 
711  v = 0;
712  while( v < consdata->nvars )
713  {
714 #ifndef NDEBUG
715  SCIP_VAR* oldvar;
716 #endif
717  var = consdata->vars[v];
718  assert(var != NULL);
719 
720 #ifndef NDEBUG
721  oldvar = var;
722 #endif
723 
725  {
726  /* check whether the literal is satisfied and the constraint is thus redundant */
727  if( isLiteralSatisfied(scip, consdata, v) )
728  {
729  *redundant = TRUE;
730  break;
731  }
732 
733  ++v;
734  continue;
735  }
736 
737  /* get active/fixed/multiaggr equivalent of v'th literal */
738  bound = consdata->bounds[v];
739  boundtype = consdata->boundtypes[v];
740  SCIP_CALL( SCIPvarGetProbvarBound(&var, &bound, &boundtype) );
741  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || oldvar != var);
742 
743  SCIPdebugMessage("in <%s>, replace <%s>[%g,%g] %c= %g by <%s>[%g,%g] %c= %g\n", SCIPconsGetName(cons),
744  SCIPvarGetName(consdata->vars[v]), SCIPvarGetLbGlobal(consdata->vars[v]), SCIPvarGetUbGlobal(consdata->vars[v]), (consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? '>' : '<'), consdata->bounds[v],
745  SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), (boundtype == SCIP_BOUNDTYPE_LOWER ? '>' : '<'), bound);
746 
747  /* if literal is satisfied, then constraint is redundant and we can stop */
748  if( (boundtype == SCIP_BOUNDTYPE_LOWER && isFeasLE(scip, var, bound, SCIPvarGetLbGlobal(var))) || /*lint !e666*/
749  (boundtype == SCIP_BOUNDTYPE_UPPER && isFeasGE(scip, var, bound, SCIPvarGetUbGlobal(var))) ) /*lint !e666*/
750  {
751  *redundant = TRUE;
752  break;
753  }
754 
755  /* if literal is not fixed, replace it */
757  {
758  /* add new literal */
759  SCIP_CALL( addCoef(scip, cons, eventhdlr, var, boundtype, bound) );
760  }
761 
762  /* remove old literal */
763  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
764  }
765 
766  return SCIP_OKAY;
767 }
768 
769 /** try to upgrade the bounddisjunction constraint
770  *
771  * if only binary variables are left, we can upgrade a bounddisjunction to a logicor constraint(, if only two variables
772  * are left, this logicor constraint can be formulated as set-packing constraint as well)
773  *
774  * e.g.: bounddisjunction( x1 >= 1, x2 <= 0; x3 >= 1; x4 <= 0 ) => x1 + ~x2 + x3 + ~x4 >= 1
775  */
776 static
778  SCIP* scip, /**< SCIP data structure */
779  SCIP_CONS* cons, /**< bound disjunction constraint that detected the conflict */
780  int* ndelconss, /**< pointer to store the number of delete constraint */
781  int* naddconss /**< pointer to store the number of added constraint */
782  )
783 {
784  SCIP_CONSDATA* consdata;
785  SCIP_VAR** newvars;
786  SCIP_Bool allbinary;
787  int nvars;
788  int v;
789 
790  assert(scip != NULL);
791  assert(cons != NULL);
792  assert(ndelconss != NULL);
793  assert(naddconss != NULL);
794  assert(naddconss != NULL);
795  assert(!SCIPconsIsModifiable(cons));
796 
797  consdata = SCIPconsGetData(cons);
798  assert(consdata != NULL);
799 
800  nvars = consdata->nvars;
801  assert(nvars >= 2);
802  assert(consdata->vars != NULL);
803 
804  allbinary = TRUE;
805 
806  SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars) );
807 
808  for( v = nvars - 1; v >= 0; --v )
809  {
810  if( !SCIPvarIsBinary(consdata->vars[v]) )
811  {
812  allbinary = FALSE;
813  break;
814  }
815  else
816  {
817  if( consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
818  {
819  assert(SCIPisFeasGT(scip, consdata->bounds[v], 0.0));
820 
821  if( nvars == 2 )
822  {
823  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &(newvars[v])) );
824  }
825  else
826  newvars[v] = consdata->vars[v];
827  }
828  else
829  {
830  assert(consdata->boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
831  assert(SCIPisFeasLT(scip, consdata->bounds[v], 1.0));
832 
833  if( nvars > 2 )
834  {
835  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &(newvars[v])) );
836  }
837  else
838  newvars[v] = consdata->vars[v];
839  }
840  }
841  }
842 
843  if( allbinary )
844  {
845  SCIP_CONS* newcons;
846 
847  if( nvars == 2 )
848  {
849  SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), nvars, newvars,
854  }
855  else
856  {
857  SCIP_CALL( SCIPcreateConsLogicor(scip, &newcons, SCIPconsGetName(cons), nvars, newvars,
862  }
863 
864  SCIPdebugMessage("updated constraint <%s> to the following %s constraint\n", SCIPconsGetName(cons), (nvars == 2 ? "setppc" : "logicor"));
865  SCIPdebugPrintCons(scip, newcons, NULL);
866  SCIP_CALL( SCIPaddCons(scip, newcons) );
867  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
868  ++(*naddconss);
869 
870  SCIP_CALL( SCIPdelCons(scip, cons) );
871  ++(*ndelconss);
872  }
873 
874  SCIPfreeBufferArray(scip, &newvars);
875 
876  return SCIP_OKAY;
877 }
878 
879 /** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */
880 static
882  SCIP* scip, /**< SCIP data structure */
883  SCIP_CONS* cons /**< bound disjunction constraint that detected the conflict */
884  )
885 {
886  SCIP_CONSDATA* consdata;
887  int v;
888 
889  /* conflict analysis can only be applied in solving stage and if it is turned on */
891  return SCIP_OKAY;
892 
893  consdata = SCIPconsGetData(cons);
894  assert(consdata != NULL);
895 
896  /* initialize conflict analysis, and add all bounds of infeasible constraint to conflict candidate queue */
898  for( v = 0; v < consdata->nvars; ++v )
899  {
900  /* the opposite bound is in conflict with this literal */
901  SCIP_CALL( SCIPaddConflictBd(scip, consdata->vars[v], SCIPboundtypeOpposite(consdata->boundtypes[v]), NULL) );
902  }
903 
904  /* analyze the conflict */
905  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
906 
907  return SCIP_OKAY;
908 }
909 
910 /** disables or deletes the given constraint, depending on the current depth */
911 static
913  SCIP* scip, /**< SCIP data structure */
914  SCIP_CONS* cons /**< bound disjunction constraint to be disabled */
915  )
916 {
917  assert(SCIPconsGetValidDepth(cons) <= SCIPgetDepth(scip));
918 
919  if( SCIPgetDepth(scip) == SCIPconsGetValidDepth(cons) )
920  {
921  SCIP_CALL( SCIPdelCons(scip, cons) );
922  }
923  else
924  {
925  SCIP_CALL( SCIPdisableCons(scip, cons) );
926  }
927 
928  return SCIP_OKAY;
929 }
930 
931 /** checks constraint for violation only looking at the watched variables, applies bound changes if possible */
932 static
934  SCIP* scip, /**< SCIP data structure */
935  SCIP_CONS* cons, /**< bound disjunction constraint to be processed */
936  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
937  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
938  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint is infeasible in current bounds */
939  SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
940  SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
941  )
942 {
943  SCIP_CONSDATA* consdata;
944  SCIP_VAR** vars;
945  SCIP_BOUNDTYPE* boundtypes;
946  SCIP_Real* bounds;
947  SCIP_Longint nbranchings1;
948  SCIP_Longint nbranchings2;
949  int nvars;
950  int watchedvar1;
951  int watchedvar2;
952 
953  assert(cons != NULL);
954  assert(SCIPconsGetHdlr(cons) != NULL);
955  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
956  assert(cutoff != NULL);
957  assert(reduceddom != NULL);
958  assert(mustcheck != NULL);
959 
960  consdata = SCIPconsGetData(cons);
961  assert(consdata != NULL);
962  assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
963 
964  /* init bools */
965  *cutoff = FALSE;
966  *infeasible = FALSE;
967  *reduceddom = FALSE;
968  *mustcheck = FALSE;
969 
970  SCIPdebugMessage("processing watched variables of constraint <%s>\n", SCIPconsGetName(cons));
971 
972  nvars = consdata->nvars;
973  vars = consdata->vars;
974  boundtypes = consdata->boundtypes;
975  bounds = consdata->bounds;
976  assert(nvars == 0 || vars != NULL);
977  assert(nvars == 0 || boundtypes != NULL);
978  assert(nvars == 0 || bounds != NULL);
979 
980  /* check watched variables if they are satisfying the literal */
981  if( consdata->watchedvar1 >= 0 && isLiteralSatisfied(scip, consdata, consdata->watchedvar1) )
982  {
983  /* the literal is satisfied, making the constraint redundant */
984  SCIPdebugMessage(" -> disabling constraint <%s> (watchedvar1 satisfied)\n", SCIPconsGetName(cons));
985  SCIP_CALL( disableCons(scip, cons) );
986  return SCIP_OKAY;
987  }
988  if( consdata->watchedvar2 >= 0 && isLiteralSatisfied(scip, consdata, consdata->watchedvar2) )
989  {
990  /* the literal is satisfied, making the constraint redundant */
991  SCIPdebugMessage(" -> disabling constraint <%s> (watchedvar2 satisfied)\n", SCIPconsGetName(cons));
992  SCIP_CALL( disableCons(scip, cons) );
993  return SCIP_OKAY;
994  }
995 
996  /* check if watched variables are still undecided */
997  watchedvar1 = -1;
998  watchedvar2 = -1;
999  nbranchings1 = SCIP_LONGINT_MAX;
1000  nbranchings2 = SCIP_LONGINT_MAX;
1001  if( consdata->watchedvar1 >= 0 && !isLiteralViolated(scip, consdata, consdata->watchedvar1) )
1002  {
1003  watchedvar1 = consdata->watchedvar1;
1004  nbranchings1 = -1; /* prefer keeping the watched variable */
1005  }
1006  if( consdata->watchedvar2 >= 0 && !isLiteralViolated(scip, consdata, consdata->watchedvar2) )
1007  {
1008  if( watchedvar1 == -1 )
1009  {
1010  watchedvar1 = consdata->watchedvar2;
1011  nbranchings1 = -1; /* prefer keeping the watched variable */
1012  }
1013  else
1014  {
1015  watchedvar2 = consdata->watchedvar2;
1016  nbranchings2 = -1; /* prefer keeping the watched variable */
1017  }
1018  }
1019  assert(watchedvar1 >= 0 || watchedvar2 == -1);
1020  assert(nbranchings1 <= nbranchings2);
1021  assert(watchedvar1 != -1 || nbranchings1 == SCIP_LONGINT_MAX);
1022  assert(watchedvar2 != -1 || nbranchings2 == SCIP_LONGINT_MAX);
1023 
1024  /* search for new watched variables */
1025  if( watchedvar2 == -1 )
1026  {
1027  int v;
1028 
1029  for( v = 0; v < nvars; ++v )
1030  {
1031  SCIP_Longint nbranchings;
1032 
1033  /* don't process the watched variables again */
1034  if( v == consdata->watchedvar1 || v == consdata->watchedvar2 )
1035  continue;
1036 
1037  /* check, if the literal is violated */
1038  if( isLiteralViolated(scip, consdata, v) )
1039  continue;
1040 
1041  /* check, if the literal is satisfied */
1042  if( isLiteralSatisfied(scip, consdata, v) )
1043  {
1044  assert(v != consdata->watchedvar1);
1045  assert(v != consdata->watchedvar2);
1046 
1047  /* the literal is satisfied, making the constraint redundant;
1048  * make sure, the feasible variable is watched and disable the constraint
1049  */
1050  SCIPdebugMessage(" -> disabling constraint <%s> (variable <%s> fixed to 1.0)\n",
1051  SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
1052  if( consdata->watchedvar1 != -1 )
1053  {
1054  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, v) );
1055  }
1056  else
1057  {
1058  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, v, consdata->watchedvar2) );
1059  }
1060  SCIP_CALL( disableCons(scip, cons) );
1061  return SCIP_OKAY;
1062  }
1063 
1064  /* the literal is still undecided and can be used as watched variable */
1065  nbranchings = SCIPvarGetNBranchingsCurrentRun(vars[v],
1067  if( nbranchings < nbranchings2 )
1068  {
1069  if( nbranchings < nbranchings1 )
1070  {
1071  watchedvar2 = watchedvar1;
1072  nbranchings2 = nbranchings1;
1073  watchedvar1 = v;
1074  nbranchings1 = nbranchings;
1075  }
1076  else
1077  {
1078  watchedvar2 = v;
1079  nbranchings2 = nbranchings;
1080  }
1081  }
1082  }
1083  }
1084  assert(nbranchings1 <= nbranchings2);
1085  assert(watchedvar1 >= 0 || watchedvar2 == -1);
1086 
1087  if( watchedvar1 == -1 )
1088  {
1089  /* there is no undecided literal left -> the constraint is infeasible
1090  * - a modifiable constraint is infeasible
1091  * - an unmodifiable constraint is infeasible and the node can be cut off
1092  */
1093  assert(watchedvar2 == -1);
1094 
1095  SCIPdebugMessage(" -> constraint <%s> is infeasible\n", SCIPconsGetName(cons));
1096  *infeasible = TRUE;
1097 
1098  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1099  if( !SCIPconsIsModifiable(cons) )
1100  {
1101  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1102  SCIP_CALL( analyzeConflict(scip, cons) );
1103 
1104  /* mark the node to be cut off */
1105  *cutoff = TRUE;
1106  }
1107  }
1108  else if( watchedvar2 == -1 )
1109  {
1110  /* there is only one undecided literal:
1111  * - a modifiable constraint must be checked manually
1112  * - we cannot change bounds of multi-aggregated variables and have to check manually
1113  * - an unmodifiable constraint is feasible and can be disabled after the remaining literal is satisfied
1114  */
1115  assert(0 <= watchedvar1 && watchedvar1 < nvars);
1116  assert(!isLiteralViolated(scip, consdata, watchedvar1));
1117  assert(!isLiteralSatisfied(scip, consdata, watchedvar1));
1118  if( SCIPconsIsModifiable(cons)
1119  || SCIPvarGetStatus(SCIPvarGetProbvar(vars[watchedvar1])) == SCIP_VARSTATUS_MULTAGGR )
1120  *mustcheck = TRUE;
1121  else
1122  {
1123  SCIP_Bool infbdchg;
1124 
1125 #ifndef NDEBUG
1126  int v;
1127 
1128  /* check whether all other literals are violated */
1129  for (v = 0; v < nvars; ++v)
1130  {
1131  if ( v != watchedvar1 )
1132  {
1133  assert( isLiteralViolated(scip, consdata, v) );
1134  }
1135  }
1136 #endif
1137 
1138  /* satisfy remaining literal and disable constraint; make sure, the fixed-to-one variable is watched */
1139  SCIPdebugMessage(" -> single-literal constraint <%s> (change bound <%s> %s %g) at depth %d\n",
1140  SCIPconsGetName(cons), SCIPvarGetName(vars[watchedvar1]),
1141  boundtypes[watchedvar1] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bounds[watchedvar1], SCIPgetDepth(scip));
1142  if( boundtypes[watchedvar1] == SCIP_BOUNDTYPE_LOWER )
1143  {
1144  SCIP_CALL( SCIPinferVarLbCons(scip, vars[watchedvar1], bounds[watchedvar1], cons, watchedvar1, TRUE,
1145  &infbdchg, NULL) );
1146  }
1147  else
1148  {
1149  SCIP_CALL( SCIPinferVarUbCons(scip, vars[watchedvar1], bounds[watchedvar1], cons, watchedvar1, TRUE,
1150  &infbdchg, NULL) );
1151  }
1152  assert(!infbdchg);
1153  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1154  if( watchedvar1 != consdata->watchedvar1 ) /* keep one of the watched variables */
1155  {
1156  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, consdata->watchedvar1) );
1157  }
1158  SCIP_CALL( disableCons(scip, cons) );
1159  *reduceddom = TRUE;
1160  }
1161  }
1162  else
1163  {
1164  SCIPdebugMessage(" -> new watched variables <%s> and <%s> of constraint <%s> are still undecided\n",
1165  SCIPvarGetName(vars[watchedvar1]), SCIPvarGetName(vars[watchedvar2]), SCIPconsGetName(cons));
1166 
1167  /* switch to the new watched variables */
1168  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, watchedvar2) );
1169 
1170  /* there are at least two undecided variables -> the constraint must be checked manually */
1171  *mustcheck = TRUE;
1172 
1173  /* disable propagation of constraint until the corresponding bound of a watched variable changed */
1174  SCIP_CALL( SCIPdisableConsPropagation(scip, cons) );
1175 
1176  /* increase aging counter */
1177  SCIP_CALL( SCIPaddConsAge(scip, cons, AGEINCREASE(consdata->nvars)) );
1178  }
1179 
1180  return SCIP_OKAY;
1181 }
1182 
1183 /** checks constraint for violation, returns TRUE iff constraint is feasible */
1184 static
1186  SCIP* scip, /**< SCIP data structure */
1187  SCIP_CONS* cons, /**< bound disjunction constraint to be checked */
1188  SCIP_SOL* sol, /**< primal CIP solution */
1189  SCIP_Bool* violated /**< pointer to store whether the given solution violates the constraint */
1190  )
1191 {
1192  SCIP_CONSDATA* consdata;
1193  SCIP_VAR** vars;
1194  SCIP_BOUNDTYPE* boundtypes;
1195  SCIP_Real* bounds;
1196  SCIP_Real solval;
1197  int nvars;
1198  int v;
1199 
1200  assert(violated != NULL);
1201 
1202  *violated = FALSE;
1203  consdata = SCIPconsGetData(cons);
1204  assert(consdata != NULL);
1205 
1206  nvars = consdata->nvars;
1207  vars = consdata->vars;
1208  boundtypes = consdata->boundtypes;
1209  bounds = consdata->bounds;
1210  assert(nvars == 0 || vars != NULL);
1211  assert(nvars == 0 || boundtypes != NULL);
1212  assert(nvars == 0 || bounds != NULL);
1213 
1214  /* check the given solution */
1215  *violated = TRUE;
1216  for( v = 0; v < nvars; ++v )
1217  {
1218  solval = SCIPgetSolVal(scip, sol, vars[v]);
1219  if( (boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, vars[v], solval, bounds[v]))
1220  || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, vars[v], solval, bounds[v])) )
1221  {
1222  *violated = FALSE;
1223  break;
1224  }
1225  }
1226  return SCIP_OKAY;
1227 }
1228 
1229 /* registers variables of a constraint as branching candidates
1230  * indicates whether an n-ary branch is necessary to enforce this constraint,
1231  * because all active literals are w.r.t. continuous variables which bound (in the literal) is at the variable's bound
1232  */
1233 static
1235  SCIP* scip, /**< SCIP data structure */
1236  SCIP_CONS* cons, /**< bound disjunction constraint which variables should be registered for branching */
1237  SCIP_Bool* neednarybranch /**< pointer to store TRUE, if n-ary branching is necessary to enforce this constraint */
1238  )
1239 {
1240  SCIP_CONSDATA* consdata;
1241  SCIP_VAR** vars;
1242  SCIP_BOUNDTYPE* boundtypes;
1243  SCIP_Real* bounds;
1244  SCIP_Real violation;
1245  SCIP_Real varlb;
1246  SCIP_Real varub;
1247  int nvars;
1248  int v;
1249 
1250  assert(cons != NULL);
1251  assert(SCIPconsGetHdlr(cons) != NULL);
1252  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1253  assert(neednarybranch != NULL);
1254 
1255  consdata = SCIPconsGetData(cons);
1256  assert(consdata != NULL);
1257  nvars = consdata->nvars;
1258  vars = consdata->vars;
1259  boundtypes = consdata->boundtypes;
1260  bounds = consdata->bounds;
1261  assert(nvars == 0 || vars != NULL);
1262  assert(nvars == 0 || boundtypes != NULL);
1263  assert(nvars == 0 || bounds != NULL);
1264 
1265  *neednarybranch = TRUE;
1266 
1267  for( v = 0; v < nvars; ++v )
1268  {
1269  SCIP_VAR* var;
1270 
1271  var = vars[v];
1272  assert(var != NULL);
1273 
1274  /* constraint should be violated, so all bounds in the constraint have to be violated */
1275  assert( !(boundtypes[v] == SCIP_BOUNDTYPE_LOWER && SCIPisFeasGE(scip, SCIPgetSolVal(scip, NULL, var), bounds[v])) &&
1276  !(boundtypes[v] == SCIP_BOUNDTYPE_UPPER && SCIPisFeasLE(scip, SCIPgetSolVal(scip, NULL, var), bounds[v])) );
1277 
1278  varlb = SCIPcomputeVarLbLocal(scip, var);
1279  varub = SCIPcomputeVarUbLocal(scip, var);
1280 
1281  /* if literal is x >= varlb, but upper bound on x is < varlb, then this literal can never be satisfied,
1282  * thus there is no use for branching
1283  */
1284  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, varub, bounds[v]) )
1285  continue;
1286 
1287  /* if literal is x <= varub, but lower bound on x is > varub, then this literal can never be satisfied,
1288  * thus there is no use for branching
1289  */
1290  if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, varlb, bounds[v]) )
1291  continue;
1292 
1293  /* if literal is always satisfied, then no need to branch on it may happen if propagation is disabled for some
1294  * reason and due to numerics current solution does not satisfy literal, but variable bounds do
1295  */
1296  if( isLiteralSatisfied(scip, consdata, v) )
1297  continue;
1298 
1299  violation = SCIPgetSolVal(scip, NULL, var) - bounds[v];
1300 
1301  /* if variable is continuous, then we cannot branch on one of the variable bounds */
1302  if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS ||
1303  ((SCIPisInfinity(scip, -varlb) || !SCIPisFeasEQ(scip, bounds[v], varlb)) &&
1304  (SCIPisInfinity(scip, varub) || !SCIPisFeasEQ(scip, bounds[v], varub))) )
1305  {
1306  SCIP_CALL( SCIPaddExternBranchCand(scip, var, REALABS(violation), bounds[v]) );
1307  *neednarybranch = FALSE;
1308  }
1309  }
1310 
1311  return SCIP_OKAY;
1312 }
1313 
1314 /** enforces the pseudo or LP solution on the given constraint */
1315 static
1317  SCIP* scip, /**< SCIP data structure */
1318  SCIP_CONS* cons, /**< bound disjunction constraint to be separated */
1319  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1320  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1321  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */
1322  SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
1323  SCIP_Bool* registeredbrcand /**< pointer to store TRUE, if branching variable candidates were registered or was already true */
1324  )
1325 {
1326  SCIP_Bool mustcheck;
1327  SCIP_Bool neednarybranch;
1328 
1329  assert(cons != NULL);
1330  assert(SCIPconsGetHdlr(cons) != NULL);
1331  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1332  assert(cutoff != NULL);
1333  assert(infeasible != NULL);
1334  assert(reduceddom != NULL);
1335  assert(registeredbrcand != NULL);
1336 
1337  SCIPdebugMessage("enforce bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
1338 
1339  /* update and check the watched variables, if they were changed since last processing */
1340  if( SCIPconsIsPropagationEnabled(cons) )
1341  {
1342  SCIP_CALL( processWatchedVars(scip, cons, eventhdlr, cutoff, infeasible, reduceddom, &mustcheck) );
1343  }
1344  else
1345  mustcheck = TRUE;
1346 
1347  if( mustcheck )
1348  {
1349  SCIP_Bool violated;
1350 
1351  SCIP_CALL( checkCons(scip, cons, NULL, &violated) );
1352  if( violated )
1353  {
1354  /* constraint was infeasible -> reset age */
1355  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1356  *infeasible = TRUE;
1357 
1358  /* register branching candidates */
1359  SCIP_CALL( registerBranchingCandidates(scip, cons, &neednarybranch) );
1360 
1361  if( !neednarybranch )
1362  *registeredbrcand = TRUE;
1363  }
1364  }
1365 
1366  return SCIP_OKAY;
1367 }
1368 
1369 /** enforces a constraint by creating an n-ary branch consisting of a set of child nodes, each enforcing one literal
1370  */
1371 static
1373  SCIP* scip, /**< SCIP data structure */
1374  SCIP_CONS* cons /**< bound disjunction constraint to branch on */
1375  )
1376 {
1377  SCIP_CONSDATA* consdata;
1378  SCIP_VAR** vars;
1379  SCIP_BOUNDTYPE* boundtypes;
1380  SCIP_Real* bounds;
1381  SCIP_Real varlb;
1382  SCIP_Real varub;
1383  int nvars;
1384  int v;
1385 
1386  SCIP_Real priority;
1387  SCIP_Real estimate;
1388  SCIP_NODE* node;
1389 
1390  assert(cons != NULL);
1391  assert(SCIPconsGetHdlr(cons) != NULL);
1392  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1393 
1394  consdata = SCIPconsGetData(cons);
1395  assert(consdata != NULL);
1396  nvars = consdata->nvars;
1397  vars = consdata->vars;
1398  boundtypes = consdata->boundtypes;
1399  bounds = consdata->bounds;
1400  assert(nvars == 0 || vars != NULL);
1401  assert(nvars == 0 || boundtypes != NULL);
1402  assert(nvars == 0 || bounds != NULL);
1403 
1404  for( v = 0; v < nvars; ++v )
1405  {
1406  SCIP_VAR* var;
1407 
1408  var = vars[v];
1409  assert(var != NULL);
1410 
1411  /* constraint should be violated, so all bounds in the constraint have to be violated */
1412  assert( !(boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPgetSolVal(scip, NULL, var), bounds[v])) && /*lint !e666*/
1413  !(boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPgetSolVal(scip, NULL, var), bounds[v])) ); /*lint !e666*/
1414 
1415  varlb = SCIPcomputeVarLbLocal(scip, var);
1416  varub = SCIPcomputeVarUbLocal(scip, var);
1417 
1418  /* if literal is x >= varlb, but upper bound on x is < varlb, then this literal can never be satisfied,
1419  * thus there is no use in creating an extra child for it
1420  */
1421  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, varub, bounds[v]) )
1422  continue;
1423  /* if literal is x <= varub, but lower bound on x is > varub, then this literal can never be satisfied,
1424  * thus there is no use in creating an extra child for it
1425  */
1426  if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, varlb, bounds[v]) )
1427  continue;
1428  /* if literal is always satisfied, then no need to branch on it */
1429  if( isLiteralSatisfied(scip, consdata, v) )
1430  continue;
1431 
1432  /* create a child that enforces the current literal */
1433  priority = SCIPcalcNodeselPriority(scip, var, boundtypes[v] == SCIP_BOUNDTYPE_LOWER ?
1435  estimate = SCIPcalcChildEstimate (scip, var, bounds[v]);
1436 
1437  SCIPdebugMessage(" -> creating child to enforce: <%s> %c= %g (priority: %g, estimate: %g)\n",
1438  SCIPvarGetName(vars[v]), boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? '>' : '<', bounds[v], priority, estimate);
1439 
1440  SCIP_CALL( SCIPcreateChild(scip, &node, priority, estimate) );
1441 
1442  /* enforce current literal */
1444  {
1445  SCIP_CONS* brcons;
1446  SCIP_Real one;
1447 
1448  one = 1.0;
1449 
1450  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
1451  {
1452  SCIP_CALL( SCIPcreateConsLinear(scip, &brcons, "bounddisjbranch", 1, &var, &one, bounds[v], SCIPinfinity(scip),
1456  SCIPconsIsStickingAtNode(cons)) );
1457  }
1458  else
1459  {
1460  SCIP_CALL( SCIPcreateConsLinear(scip, &brcons, "bounddisjbranch", 1, &var, &one, -SCIPinfinity(scip), bounds[v],
1464  SCIPconsIsStickingAtNode(cons)) );
1465  }
1466  SCIP_CALL( SCIPaddConsNode(scip, node, brcons, NULL) );
1467  SCIP_CALL( SCIPreleaseCons(scip, &brcons) );
1468  }
1469  else
1470  {
1471  assert(SCIPvarIsActive(var));
1472  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
1473  {
1474  SCIP_CALL( SCIPchgVarLbNode(scip, node, var, bounds[v]) );
1475  }
1476  else
1477  {
1478  SCIP_CALL( SCIPchgVarUbNode(scip, node, var, bounds[v]) );
1479  }
1480  }
1481 
1482  /* delete bound disjunction constraint from child node */
1483  SCIP_CALL( SCIPdelConsNode(scip, node, cons) );
1484  }
1485 
1486  return SCIP_OKAY;
1487 }
1488 
1489 /**@} */
1490 
1491 /**@name Upgrading methods for special quadratic constraint
1492  *
1493  */
1494 
1495 /** upgrades quadratic complementarity constraints into a bounddisjunction constraint
1496  * If constraint is of form (x - a) * (y - b) = 0 with x >= a and y >= b for some a and b,
1497  * then upgrade to bounddisjunction constraint "x <= a or y <= b".
1498  * If constraint is of form (x - a) * (y - b) >= 0,
1499  * then upgrade to bounddisjunction constraints "x >= a or y <= b" and "x <= a or y >= b".
1500  */
1501 static
1502 SCIP_DECL_QUADCONSUPGD(upgradeConsQuadratic)
1503 { /*lint --e{715}*/
1504  char name[SCIP_MAXSTRLEN];
1505  SCIP_BOUNDTYPE boundtypes[2];
1506  SCIP_Real bounds[2];
1507  SCIP_VAR* xy[2];
1508  SCIP_QUADVARTERM* quadvarterms;
1509  SCIP_Real coefxy;
1510  SCIP_Real coefx;
1511  SCIP_Real coefy;
1512  SCIP_Real lhs;
1513  SCIP_Real rhs;
1514  SCIP_Real a;
1515  SCIP_Real b;
1516  SCIP_VAR* x;
1517  SCIP_VAR* y;
1518 
1519  assert(scip != NULL);
1520  assert(cons != NULL);
1521  assert(nupgdconss != NULL);
1522  assert(upgdconss != NULL);
1523 
1524  *nupgdconss = 0;
1525 
1526  SCIPdebugMessage("upgradeConsQuadratic called for constraint <%s>\n", SCIPconsGetName(cons));
1527  SCIPdebugPrintCons(scip, cons, NULL);
1528 
1529  if( SCIPgetNLinearVarsQuadratic(scip, cons) != 0 )
1530  return SCIP_OKAY;
1531  if( SCIPgetNQuadVarTermsQuadratic(scip, cons) != 2 )
1532  return SCIP_OKAY;
1533  if( SCIPgetNBilinTermsQuadratic(scip, cons) != 1 )
1534  return SCIP_OKAY;
1535  /* do not upgrade x*y <=/== rhs with x (or y) binary
1536  * the reformulation for such terms in cons_quadratic should handle this better
1537  */
1538  if( nbinquad > 0 )
1539  return SCIP_OKAY;
1540 
1541  lhs = SCIPgetLhsQuadratic(scip, cons);
1542  rhs = SCIPgetRhsQuadratic(scip, cons);
1543 
1544  /* we don't want a free constraint */
1545  if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
1546  return SCIP_OKAY;
1547 
1548  /* we currently don't want a ranged constraint (could upgrade at most one side) */
1549  if( !SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, rhs) && !SCIPisEQ(scip, lhs, rhs) )
1550  return SCIP_OKAY;
1551 
1552  quadvarterms = SCIPgetQuadVarTermsQuadratic(scip, cons);
1553 
1554  /* we don't want square terms */
1555  if( !SCIPisZero(scip, quadvarterms[0].sqrcoef) || !SCIPisZero(scip, quadvarterms[1].sqrcoef) )
1556  return SCIP_OKAY;
1557 
1558  x = quadvarterms[0].var;
1559  y = quadvarterms[1].var;
1560  assert(x != y);
1561 
1562  coefx = quadvarterms[0].lincoef;
1563  coefy = quadvarterms[1].lincoef;
1564 
1565  coefxy = SCIPgetBilinTermsQuadratic(scip, cons)[0].coef;
1566  assert(SCIPgetBilinTermsQuadratic(scip, cons)[0].var1 == x || SCIPgetBilinTermsQuadratic(scip, cons)[0].var1 == y);
1567  assert(SCIPgetBilinTermsQuadratic(scip, cons)[0].var2 == x || SCIPgetBilinTermsQuadratic(scip, cons)[0].var2 == y);
1568  assert(!SCIPisZero(scip, coefxy));
1569 
1570  /* divide by coefxy */
1571  coefx /= coefxy;
1572  coefy /= coefxy;
1573  if( coefxy > 0.0 )
1574  {
1575  if( !SCIPisInfinity(scip, -lhs) )
1576  lhs /= coefxy;
1577  if( !SCIPisInfinity(scip, rhs) )
1578  rhs /= coefxy;
1579  }
1580  else
1581  {
1582  SCIP_Real tmp;
1583 
1584  if( !SCIPisInfinity(scip, rhs) )
1585  tmp = rhs / coefxy;
1586  else
1587  tmp = -SCIPinfinity(scip);
1588  if( !SCIPisInfinity(scip, -lhs) )
1589  rhs = lhs / coefxy;
1590  else
1591  rhs = SCIPinfinity(scip);
1592  lhs = tmp;
1593  }
1594 
1595  /* now have form lhs <= x*y + coefx x + coefy y <= rhs
1596  * <-> lhs + coefx * coefy <= (x + coefy) * (y + coefx) <= rhs + coefx * coefy
1597  */
1598 
1599  /* handle case (x + coefy) * (y + coefx) == rhs + coefx * coefy */
1600  if( SCIPisEQ(scip, lhs, rhs) )
1601  {
1602  /* check whether rhs + coefx * coefy == 0 */
1603  if( !SCIPisZero(scip, rhs + coefx * coefy) )
1604  return SCIP_OKAY;
1605 
1606  a = -coefy;
1607  b = -coefx;
1608 
1609  /* now have complementarity form x = a or y = b */
1610 
1611  /* we can write this as up to four bounddisjunction constraint:
1612  * (x >= a or y >= b) and (x <= a or y >= b) and (x >= a or y <= b) and (x <= a or y <= b)
1613  *
1614  * count whether we need to create 1, 2, or 4 constraints
1615  */
1616  if( !SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) && !SCIPisLE(scip, SCIPvarGetUbGlobal(x), a) )
1617  *nupgdconss = 2;
1618  else
1619  *nupgdconss = 1;
1620 
1621  if( !SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) && !SCIPisLE(scip, SCIPvarGetUbGlobal(y), b) )
1622  *nupgdconss *= 2;
1623 
1624  if( upgdconsssize < *nupgdconss )
1625  {
1626  /* signal that we need more memory */
1627  *nupgdconss = -*nupgdconss;
1628  return SCIP_OKAY;
1629  }
1630 
1631  xy[0] = x;
1632  xy[1] = y;
1633  bounds[0] = a;
1634  bounds[1] = b;
1635  if( *nupgdconss == 1 )
1636  {
1637  boundtypes[0] = SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER;
1638  boundtypes[1] = SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER;
1639  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], SCIPconsGetName(cons),
1640  2, xy, boundtypes, bounds,
1644  SCIPconsIsStickingAtNode(cons)) );
1645 
1646  SCIPdebugMessage("created bounddisjunction constraint:\n");
1647  SCIPdebugPrintCons(scip, upgdconss[0], NULL);
1648 
1649  return SCIP_OKAY;
1650  }
1651  else if( SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) || SCIPisLE(scip, SCIPvarGetUbGlobal(x), a) )
1652  {
1653  assert(!SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) && !SCIPisLE(scip, SCIPvarGetUbGlobal(y), b));
1654  assert(*nupgdconss == 2);
1655 
1656  boundtypes[0] = SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER;
1657 
1658  /* create constraint with y >= b */
1659  boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
1660  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
1661  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
1662  2, xy, boundtypes, bounds,
1666  SCIPconsIsStickingAtNode(cons)) );
1667 
1668  /* create constraint with y <= b */
1669  boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
1670  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper", SCIPconsGetName(cons));
1671  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
1672  2, xy, boundtypes, bounds,
1676  SCIPconsIsStickingAtNode(cons)) );
1677 
1678  SCIPdebugMessage("created bounddisjunction constraints:\n");
1679  SCIPdebugPrintCons(scip, upgdconss[0], NULL);
1680  SCIPdebugPrintCons(scip, upgdconss[1], NULL);
1681  }
1682  else if( SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) || SCIPisLE(scip, SCIPvarGetUbGlobal(y), b) )
1683  {
1684  assert(!SCIPisEQ(scip, SCIPvarGetLbGlobal(x), a) && !SCIPisEQ(scip, SCIPvarGetUbGlobal(x), a));
1685  assert(*nupgdconss == 2);
1686 
1687  boundtypes[1] = SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER;
1688 
1689  /* create constraint with x >= a */
1690  boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
1691  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
1692  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
1693  2, xy, boundtypes, bounds,
1697  SCIPconsIsStickingAtNode(cons)) );
1698 
1699  /* create constraint with x <= a */
1700  boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
1701  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
1702  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
1703  2, xy, boundtypes, bounds,
1707  SCIPconsIsStickingAtNode(cons)) );
1708 
1709  SCIPdebugMessage("created bounddisjunction constraints:\n");
1710  SCIPdebugPrintCons(scip, upgdconss[0], NULL);
1711  SCIPdebugPrintCons(scip, upgdconss[1], NULL);
1712  }
1713  else
1714  {
1715  assert(!SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) && !SCIPisLE(scip, SCIPvarGetUbGlobal(x), a));
1716  assert(!SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) && !SCIPisLE(scip, SCIPvarGetUbGlobal(y), b));
1717  assert(*nupgdconss == 4);
1718 
1719  /* create constraint x >= a or y >= a */
1720  boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
1721  boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
1722  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower_lower", SCIPconsGetName(cons));
1723  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
1724  2, xy, boundtypes, bounds,
1728  SCIPconsIsStickingAtNode(cons)) );
1729 
1730  /* create constraint x >= a or y <= a */
1731  boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
1732  boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
1733  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower_upper", SCIPconsGetName(cons));
1734  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
1735  2, xy, boundtypes, bounds,
1739  SCIPconsIsStickingAtNode(cons)) );
1740 
1741  /* create constraint x <= a or y >= a */
1742  boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
1743  boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
1744  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper_lower", SCIPconsGetName(cons));
1745  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[2], name,
1746  2, xy, boundtypes, bounds,
1750  SCIPconsIsStickingAtNode(cons)) );
1751 
1752  /* create constraint x <= a or y <= a */
1753  boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
1754  boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
1755  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper_upper", SCIPconsGetName(cons));
1756  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[3], name,
1757  2, xy, boundtypes, bounds,
1761  SCIPconsIsStickingAtNode(cons)) );
1762 
1763  SCIPdebugMessage("created bounddisjunction constraints:\n");
1764  SCIPdebugPrintCons(scip, upgdconss[0], NULL);
1765  SCIPdebugPrintCons(scip, upgdconss[1], NULL);
1766  SCIPdebugPrintCons(scip, upgdconss[2], NULL);
1767  SCIPdebugPrintCons(scip, upgdconss[3], NULL);
1768  }
1769 
1770  return SCIP_OKAY;
1771  }
1772 
1773  /* handle case (x + coefy) * (y + coefx) <= rhs + coefx * coefy */
1774  if( !SCIPisInfinity(scip, rhs) )
1775  {
1776  assert(SCIPisInfinity(scip, -lhs));
1777 
1778  /* check whether rhs + coefx * coefy == 0 */
1779  if( !SCIPisZero(scip, rhs + coefx * coefy) )
1780  return SCIP_OKAY;
1781 
1782  a = -coefy;
1783  b = -coefx;
1784 
1785  /* now have form (x >= a and y <= b) or (x <= a and y >= b)
1786  * which is equivalent to (x >= a or y >= b) and (x <= a or y <= b)
1787  * the latter can be represented as two bound disjunction constraints
1788  */
1789 
1790  if( upgdconsssize < 2 )
1791  {
1792  /* signal that we need more memory */
1793  *nupgdconss = -2;
1794  return SCIP_OKAY;
1795  }
1796 
1797  xy[0] = x;
1798  xy[1] = y;
1799  bounds[0] = a;
1800  bounds[1] = b;
1801 
1802  /* create constraint x >= a or y >= b */
1803  boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
1804  boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
1805  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
1806  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
1807  2, xy, boundtypes, bounds,
1811  SCIPconsIsStickingAtNode(cons)) );
1812 
1813  /* create constraint x <= a or y <= b */
1814  boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
1815  boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
1816  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper", SCIPconsGetName(cons));
1817  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
1818  2, xy, boundtypes, bounds,
1822  SCIPconsIsStickingAtNode(cons)) );
1823 
1824  SCIPdebugMessage("created bounddisjunction constraints:\n");
1825  SCIPdebugPrintCons(scip, upgdconss[0], NULL);
1826  SCIPdebugPrintCons(scip, upgdconss[1], NULL);
1827 
1828  *nupgdconss = 2;
1829 
1830  return SCIP_OKAY;
1831  }
1832 
1833  /* handle remaining case (x + coefy) * (y + coefx) >= lhs + coefx * coefy */
1834  {
1835  assert(!SCIPisInfinity(scip, -lhs));
1836  assert( SCIPisInfinity(scip, rhs));
1837 
1838  /* check whether lhs + coefx * coefy == 0 */
1839  if( !SCIPisZero(scip, lhs + coefx * coefy) )
1840  return SCIP_OKAY;
1841 
1842  a = -coefy;
1843  b = -coefx;
1844 
1845  /* now have form (x >= a and y >= b) or (x <= a and y <= b)
1846  * which is equivalent to (x >= a or y <= b) and (x <= a or y >= b)
1847  * the latter can be represented as two bound disjunction constraints
1848  */
1849 
1850  if( upgdconsssize < 2 )
1851  {
1852  /* signal that we need more memory */
1853  *nupgdconss = -2;
1854  return SCIP_OKAY;
1855  }
1856 
1857  xy[0] = x;
1858  xy[1] = y;
1859  bounds[0] = a;
1860  bounds[1] = b;
1861 
1862  /* create constraint x >= a or y <= b */
1863  boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
1864  boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
1865  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
1866  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
1867  2, xy, boundtypes, bounds,
1871  SCIPconsIsStickingAtNode(cons)) );
1872 
1873  /* create constraint x <= a or y >= b */
1874  boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
1875  boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
1876  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper", SCIPconsGetName(cons));
1877  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
1878  2, xy, boundtypes, bounds,
1882  SCIPconsIsStickingAtNode(cons)) );
1883 
1884  SCIPdebugMessage("created bounddisjunction constraints:\n");
1885  SCIPdebugPrintCons(scip, upgdconss[0], NULL);
1886  SCIPdebugPrintCons(scip, upgdconss[1], NULL);
1887 
1888  *nupgdconss = 2;
1889  }
1890 
1891  return SCIP_OKAY;
1892 }
1893 
1894 /**@} */
1895 
1896 /**@name Callback methods of constraint handler
1897  *
1898  * @{
1899  */
1900 
1901 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1902 static
1903 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBounddisjunction)
1904 { /*lint --e{715}*/
1905  assert(scip != NULL);
1906  assert(conshdlr != NULL);
1907  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1908 
1909  /* call inclusion method of constraint handler */
1911 
1912  *valid = TRUE;
1913 
1914  return SCIP_OKAY;
1915 }
1916 
1917 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
1918 static
1919 SCIP_DECL_CONSFREE(consFreeBounddisjunction)
1920 { /*lint --e{715}*/
1921  SCIP_CONSHDLRDATA* conshdlrdata;
1922 
1923  assert(conshdlr != NULL);
1924  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1925  assert(scip != NULL);
1926 
1927  /* free constraint handler data */
1928  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1929  assert(conshdlrdata != NULL);
1930 
1931  SCIP_CALL( conshdlrdataFree(scip, &conshdlrdata) );
1932 
1933  SCIPconshdlrSetData(conshdlr, NULL);
1934 
1935  return SCIP_OKAY;
1936 }
1937 
1938 
1939 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
1940 static
1941 SCIP_DECL_CONSEXITPRE(consExitpreBounddisjunction)
1942 { /*lint --e{715}*/
1943  SCIP_CONSHDLRDATA* conshdlrdata;
1944  SCIP_CONS* cons;
1945  SCIP_Bool redundant;
1946  int c;
1947 
1948  assert(conshdlr != NULL);
1949  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1950  assert(scip != NULL);
1951 
1952  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1953  assert(conshdlrdata != NULL);
1954 
1955  /* fast processing of constraints, apply global bounds and remove fixed variables */
1956  for( c = 0; c < nconss; ++c )
1957  {
1958  cons = conss[c];
1959  assert(cons != NULL);
1960 
1961  SCIPdebugMessage("exit-presolving bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
1962 
1963  /* remove all literals that are violated in global bounds, check redundancy due to global bounds */
1964  SCIP_CALL( applyGlobalBounds(scip, cons, conshdlrdata->eventhdlr, &redundant) );
1965 
1966  if( !redundant )
1967  {
1968  /* replace variables by their representative active (or multi-aggregated) variables */
1969  SCIP_CALL( removeFixedVariables(scip, cons, conshdlrdata->eventhdlr, &redundant) );
1970  }
1971 
1972  if( redundant && SCIPconsIsAdded(cons) )
1973  {
1974  SCIPdebugMessage("bound disjunction constraint <%s> is redundant\n", SCIPconsGetName(cons));
1975  SCIP_CALL( SCIPdelCons(scip, cons) );
1976  }
1977  }
1978 
1979  return SCIP_OKAY;
1980 }
1981 
1982 
1983 /** frees specific constraint data */
1984 static
1985 SCIP_DECL_CONSDELETE(consDeleteBounddisjunction)
1986 { /*lint --e{715}*/
1987  assert(conshdlr != NULL);
1988  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1989  assert(consdata != NULL);
1990  assert(*consdata != NULL);
1991 
1992  /* free LP row and bound disjunction constraint */
1993  SCIP_CALL( consdataFree(scip, consdata) );
1994 
1995  return SCIP_OKAY;
1996 }
1997 
1998 
1999 /** transforms constraint data into data belonging to the transformed problem */
2000 static
2001 SCIP_DECL_CONSTRANS(consTransBounddisjunction)
2002 { /*lint --e{715}*/
2003  SCIP_CONSDATA* sourcedata;
2004  SCIP_CONSDATA* targetdata;
2005 
2006  /*debugMessage("Trans method of bound disjunction constraints\n");*/
2007 
2008  assert(conshdlr != NULL);
2009  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2010  assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
2011  assert(sourcecons != NULL);
2012  assert(targetcons != NULL);
2013 
2014  sourcedata = SCIPconsGetData(sourcecons);
2015  assert(sourcedata != NULL);
2016 
2017  /* create constraint data for target constraint */
2018  SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->nvars, sourcedata->vars,
2019  sourcedata->boundtypes, sourcedata->bounds) );
2020 
2021  /* create target constraint */
2022  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
2023  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
2024  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
2025  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
2026  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
2027 
2028  return SCIP_OKAY;
2029 }
2030 
2031 
2032 /** constraint enforcing method of constraint handler for LP solutions */
2033 static
2034 SCIP_DECL_CONSENFOLP(consEnfolpBounddisjunction)
2035 { /*lint --e{715}*/
2036  SCIP_CONSHDLRDATA* conshdlrdata;
2037  SCIP_Bool cutoff;
2038  SCIP_Bool infeasible;
2039  SCIP_Bool reduceddom;
2040  SCIP_Bool registeredbrcand;
2041  SCIP_Bool infeasiblecons;
2042  int c;
2043  int nnarybranchconsvars;
2044  SCIP_CONS* narybranchcons; /* constraint that is a candidate for an n-ary branch */
2045 
2046  assert(conshdlr != NULL);
2047  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2048  assert(nconss == 0 || conss != NULL);
2049  assert(result != NULL);
2050 
2051  SCIPdebugMessage("LP enforcing %d bound disjunction constraints\n", nconss);
2052 
2053  *result = SCIP_FEASIBLE;
2054 
2055  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2056  assert(conshdlrdata != NULL);
2057 
2058  cutoff = FALSE;
2059  infeasible = FALSE;
2060  reduceddom = FALSE;
2061  registeredbrcand = FALSE;
2062  narybranchcons = NULL;
2063  nnarybranchconsvars = INT_MAX;
2064 
2065  /* check all bound disjunction constraints for feasibility */
2066  for( c = 0; c < nconss && !cutoff && !reduceddom; ++c )
2067  {
2068  infeasiblecons = FALSE;
2069  SCIP_CALL( enforceCurrentSol(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &infeasiblecons, &reduceddom, &registeredbrcand) );
2070  infeasible |= infeasiblecons;
2071  if( infeasiblecons && !registeredbrcand )
2072  {
2073  /* if cons. c has less literals than the previous candidate for an n-ary branch, then keep cons. c as candidate for n-ary branch */
2074  if( narybranchcons == NULL || SCIPconsGetData(conss[c])->nvars < nnarybranchconsvars )
2075  {
2076  narybranchcons = conss[c];
2077  nnarybranchconsvars = SCIPconsGetData(narybranchcons)->nvars;
2078  assert(nnarybranchconsvars > 0);
2079  }
2080  }
2081  }
2082 
2083  if( cutoff )
2084  *result = SCIP_CUTOFF;
2085  else if( reduceddom )
2086  *result = SCIP_REDUCEDDOM;
2087  else if( infeasible )
2088  {
2089  if( registeredbrcand )
2090  {
2091  *result = SCIP_INFEASIBLE;
2092  }
2093  else
2094  {
2095  SCIP_CALL( createNAryBranch(scip, narybranchcons) );
2096  *result = SCIP_BRANCHED;
2097  }
2098  }
2099 
2100  return SCIP_OKAY;
2101 }
2102 
2103 
2104 /** constraint enforcing method of constraint handler for pseudo solutions */
2105 static
2106 SCIP_DECL_CONSENFOPS(consEnfopsBounddisjunction)
2107 { /*lint --e{715}*/
2108  SCIP_CONSHDLRDATA* conshdlrdata;
2109  SCIP_Bool cutoff;
2110  SCIP_Bool infeasible;
2111  SCIP_Bool reduceddom;
2112  SCIP_Bool registeredbrcand;
2113  int c;
2114  SCIP_CONS* narybranchcons; /* constraint that is a candidate for an n-ary branch */
2115 
2116  assert(conshdlr != NULL);
2117  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2118  assert(nconss == 0 || conss != NULL);
2119  assert(result != NULL);
2120 
2121  SCIPdebugMessage("pseudo enforcing %d bound disjunction constraints\n", nconss);
2122 
2123  *result = SCIP_FEASIBLE;
2124 
2125  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2126  assert(conshdlrdata != NULL);
2127 
2128  cutoff = FALSE;
2129  infeasible = FALSE;
2130  reduceddom = FALSE;
2131  registeredbrcand = FALSE;
2132  narybranchcons = NULL;
2133 
2134  /* check all bound disjunction constraints for feasibility */
2135  for( c = 0; c < nconss && !cutoff && !reduceddom; ++c )
2136  {
2137  SCIP_CALL( enforceCurrentSol(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &infeasible, &reduceddom, &registeredbrcand) );
2138  if( infeasible && !registeredbrcand )
2139  {
2140  /* if cons. c has less literals than the previous candidate for an n-ary branch, then keep cons. c as candidate for n-ary branch */
2141  if( !narybranchcons || SCIPconsGetData(conss[c])->nvars < SCIPconsGetData(narybranchcons)->nvars )
2142  narybranchcons = conss[c];
2143  }
2144  }
2145 
2146  if( cutoff )
2147  *result = SCIP_CUTOFF;
2148  else if( reduceddom )
2149  *result = SCIP_REDUCEDDOM;
2150  else if( infeasible )
2151  {
2152  if( registeredbrcand )
2153  {
2154  *result = SCIP_INFEASIBLE;
2155  }
2156  else
2157  {
2158  SCIP_CALL( createNAryBranch(scip, narybranchcons) );
2159  *result = SCIP_BRANCHED;
2160  }
2161  }
2162 
2163  return SCIP_OKAY;
2164 }
2165 
2166 
2167 /** feasibility check method of constraint handler for integral solutions */
2168 static
2169 SCIP_DECL_CONSCHECK(consCheckBounddisjunction)
2170 { /*lint --e{715}*/
2171  SCIP_CONS* cons;
2172  SCIP_CONSDATA* consdata;
2173  int c;
2174 
2175  assert(conshdlr != NULL);
2176  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2177  assert(nconss == 0 || conss != NULL);
2178  assert(result != NULL);
2179 
2180  *result = SCIP_FEASIBLE;
2181 
2182  /* check all bound disjunction constraints for feasibility */
2183  for( c = 0; c < nconss; ++c )
2184  {
2185  SCIP_Bool violated;
2186 
2187  cons = conss[c];
2188  consdata = SCIPconsGetData(cons);
2189  assert(consdata != NULL);
2190 
2191  SCIP_CALL( checkCons(scip, cons, sol, &violated) );
2192  if( violated )
2193  {
2194  if( printreason )
2195  {
2196  int v;
2197 
2198  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2199  SCIPinfoMessage(scip, NULL, ";\nviolation: ");
2200  for( v = 0; v < consdata->nvars; ++v )
2201  {
2202  assert(consdata->vars[v] != NULL);
2203  if( v > 0 )
2204  SCIPinfoMessage(scip, NULL, ", ");
2205  SCIPinfoMessage(scip, NULL, "<%s> = %.15g",
2206  SCIPvarGetName(consdata->vars[v]), SCIPgetSolVal(scip, sol, consdata->vars[v]));
2207  }
2208  SCIPinfoMessage(scip, NULL, ")\n");
2209  }
2210 
2211  /* constraint is violated */
2212  *result = SCIP_INFEASIBLE;
2213  return SCIP_OKAY;
2214  }
2215  }
2216 
2217  return SCIP_OKAY;
2218 }
2219 
2220 
2221 /** domain propagation method of constraint handler */
2222 static
2223 SCIP_DECL_CONSPROP(consPropBounddisjunction)
2224 { /*lint --e{715}*/
2225  SCIP_CONSHDLRDATA* conshdlrdata;
2226  SCIP_Bool cutoff;
2227  SCIP_Bool infeasible;
2228  SCIP_Bool reduceddom;
2229  SCIP_Bool mustcheck;
2230  SCIP_Bool consreduceddom;
2231  int c;
2232 
2233  assert(conshdlr != NULL);
2234  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2235  assert(nconss == 0 || conss != NULL);
2236  assert(result != NULL);
2237 
2238  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2239  assert(conshdlrdata != NULL);
2240 
2241  cutoff = FALSE;
2242  infeasible = FALSE;
2243  reduceddom = FALSE;
2244 
2245  /* propagate all useful bound disjunction constraints */
2246  for( c = 0; c < nusefulconss && !cutoff; ++c )
2247  {
2248  SCIP_CALL( processWatchedVars(scip, conss[c], conshdlrdata->eventhdlr,
2249  &cutoff, &infeasible, &consreduceddom, &mustcheck) );
2250  reduceddom = reduceddom || consreduceddom;
2251  }
2252 
2253  /* return the correct result */
2254  if( cutoff )
2255  *result = SCIP_CUTOFF;
2256  else if( reduceddom )
2257  *result = SCIP_REDUCEDDOM;
2258  else
2259  *result = SCIP_DIDNOTFIND;
2260 
2261  return SCIP_OKAY;
2262 }
2263 
2264 
2265 /** presolving method of constraint handler */
2266 static
2267 SCIP_DECL_CONSPRESOL(consPresolBounddisjunction)
2268 { /*lint --e{715}*/
2269  SCIP_CONSHDLRDATA* conshdlrdata;
2270  SCIP_CONS* cons;
2271  SCIP_CONSDATA* consdata;
2272  SCIP_Bool infeasible;
2273  SCIP_Bool redundant;
2274  SCIP_Bool tightened;
2275  int c;
2276 
2277  assert(conshdlr != NULL);
2278  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2279  assert(scip != NULL);
2280  assert(result != NULL);
2281 
2282  *result = SCIP_DIDNOTFIND;
2283 
2284  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2285  assert(conshdlrdata != NULL);
2286 
2287  /* process constraints */
2288  for( c = 0; c < nconss && *result != SCIP_CUTOFF && !SCIPisStopped(scip); ++c )
2289  {
2290  cons = conss[c];
2291  assert(cons != NULL);
2292  consdata = SCIPconsGetData(cons);
2293  assert(consdata != NULL);
2294 
2295  SCIPdebugMessage("presolving bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2296 
2297  /* force presolving the constraint in the initial round */
2298  if( nrounds == 0 )
2299  {
2300  SCIP_CALL( SCIPenableConsPropagation(scip, cons) );
2301  }
2302 
2303  /* remove all literals that are violated in global bounds, check redundancy due to global bounds */
2304  SCIP_CALL( applyGlobalBounds(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2305 
2306  if( !redundant )
2307  {
2308  /* replace variables by their representative active (or multi-aggregated) variables */
2309  SCIP_CALL( removeFixedVariables(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2310  }
2311 
2312  /**@todo find pairs of negated variables in constraint: constraint is redundant */
2313  /**@todo find sets of equal variables in constraint: multiple entries of variable can be replaced by single entry */
2314 
2315  if( redundant )
2316  {
2317  SCIPdebugMessage("bound disjunction constraint <%s> is redundant\n", SCIPconsGetName(cons));
2318  SCIP_CALL( SCIPdelCons(scip, cons) );
2319  (*ndelconss)++;
2320  *result = SCIP_SUCCESS;
2321  continue;
2322  }
2323  else if( !SCIPconsIsModifiable(cons) )
2324  {
2325  /* if unmodifiable constraint has no variables, it is infeasible,
2326  * if unmodifiable constraint has only one variable, the literal can be satisfied and the constraint deleted
2327  */
2328  if( consdata->nvars == 0 )
2329  {
2330  SCIPdebugMessage("bound disjunction constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2331  *result = SCIP_CUTOFF;
2332  return SCIP_OKAY;
2333  }
2334  else if( consdata->nvars == 1 )
2335  {
2336  SCIPdebugMessage("bound disjunction constraint <%s> has only one undecided literal\n",
2337  SCIPconsGetName(cons));
2338 
2339  assert(consdata->vars != NULL);
2340  assert(!isLiteralSatisfied(scip, consdata, 0));
2341  assert(!isLiteralViolated(scip, consdata, 0));
2342 
2343  if( SCIPvarIsActive(consdata->vars[0]) )
2344  {
2345  if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER )
2346  {
2347  SCIP_CALL( SCIPtightenVarLb(scip, consdata->vars[0], consdata->bounds[0], TRUE, &infeasible, &tightened) );
2348  }
2349  else
2350  {
2351  SCIP_CALL( SCIPtightenVarUb(scip, consdata->vars[0], consdata->bounds[0], TRUE, &infeasible, &tightened) );
2352  }
2353  if( infeasible )
2354  {
2355  SCIPdebugMessage(" -> infeasible fixing\n");
2356  *result = SCIP_CUTOFF;
2357  return SCIP_OKAY;
2358  }
2359  assert(tightened);
2360  (*nchgbds)++;
2361  }
2362  else
2363  {
2364  /* upgrade to a linear constraint, if vars[0] is multi-aggregated */
2365  SCIP_CONS* lincons;
2366  SCIP_Real one;
2367 
2368  assert(SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_MULTAGGR);
2369 
2370  one = 1.0;
2371  if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER )
2372  {
2373  SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, SCIPconsGetName(cons),
2374  1, &consdata->vars[0], &one, consdata->bounds[0], SCIPinfinity(scip),
2378  SCIPconsIsStickingAtNode(cons)) );
2379  }
2380  else
2381  {
2382  SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, SCIPconsGetName(cons),
2383  1, &consdata->vars[0], &one, -SCIPinfinity(scip), consdata->bounds[0],
2387  SCIPconsIsStickingAtNode(cons)) );
2388  }
2389  SCIP_CALL( SCIPaddCons(scip, lincons) );
2390  SCIP_CALL( SCIPreleaseCons(scip, &lincons) );
2391  (*nupgdconss)++;
2392  }
2393 
2394  SCIP_CALL( SCIPdelCons(scip, cons) );
2395  (*ndelconss)++;
2396  *result = SCIP_SUCCESS;
2397  continue;
2398  }
2399  else
2400  {
2401  /* try to upgrade the bounddisjunction constraint */
2402  SCIP_CALL( upgradeCons(scip, cons, ndelconss, naddconss) );
2403  }
2404  }
2405  }
2406 
2407  /**@todo preprocess pairs of bound disjunction constraints */
2408 
2409  return SCIP_OKAY;
2410 }
2411 
2412 
2413 /** propagation conflict resolving method of constraint handler */
2414 static
2415 SCIP_DECL_CONSRESPROP(consRespropBounddisjunction)
2416 { /*lint --e{715}*/
2417  SCIP_CONSDATA* consdata;
2418  SCIP_VAR** vars;
2419  SCIP_BOUNDTYPE* boundtypes;
2420 #ifndef NDEBUG
2421  SCIP_Real* bounds;
2422 #endif
2423  int v;
2424 
2425  assert(conshdlr != NULL);
2426  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2427  assert(cons != NULL);
2428  assert(infervar != NULL);
2429  assert(result != NULL);
2430 
2431  consdata = SCIPconsGetData(cons);
2432  assert(consdata != NULL);
2433  assert(consdata->vars != NULL);
2434  assert(consdata->nvars > 0);
2435  assert(0 <= inferinfo && inferinfo < consdata->nvars);
2436  assert(consdata->vars[inferinfo] == infervar);
2437 
2438  vars = consdata->vars;
2439  boundtypes = consdata->boundtypes;
2440 #ifndef NDEBUG
2441  bounds = consdata->bounds;
2442  assert(bounds != NULL);
2443 #endif
2444  assert(boundtypes != NULL);
2445 
2446  SCIPdebugMessage("conflict resolving method of bound disjunction constraint handler\n");
2447 
2448  /* the only deductions are bounds tightened to a literal's bound on bound disjunction constraints where all other
2449  * literals are violated
2450  */
2451  assert((boundtypes[inferinfo] == SCIP_BOUNDTYPE_LOWER
2452  && SCIPisFeasGE(scip, SCIPvarGetLbAtIndex(infervar, bdchgidx, TRUE), bounds[inferinfo]))
2453  || (boundtypes[inferinfo] == SCIP_BOUNDTYPE_UPPER
2454  && SCIPisFeasLE(scip, SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE), bounds[inferinfo])));
2455 
2456  for( v = 0; v < consdata->nvars; ++v )
2457  {
2458  if( v != inferinfo )
2459  {
2460  assert(consdata->vars[v] != infervar || consdata->boundtypes[v] != consdata->boundtypes[inferinfo]);
2461 
2462  /* the reason literal must have been violated
2463  * we do not check for multi-aggregated variables, since SCIPvarGetXbAtIndex is not implemented for them */
2464  /* Use a weaker comparison to SCIPvarGetXbAtIndex here (i.e., SCIPisXT instead of SCIPisFeasXT),
2465  * because SCIPvarGetXbAtIndex might differ from the local bound at time bdchgidx by epsilon. */
2466  assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_MULTAGGR
2467  || (boundtypes[v] == SCIP_BOUNDTYPE_LOWER
2468  && SCIPisLT(scip, SCIPvarGetUbAtIndex(vars[v], bdchgidx, TRUE), bounds[v]))
2469  || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER
2470  && SCIPisGT(scip, SCIPvarGetLbAtIndex(vars[v], bdchgidx, TRUE), bounds[v])));
2471  SCIP_CALL( SCIPaddConflictBd(scip, vars[v], SCIPboundtypeOpposite(boundtypes[v]), bdchgidx) );
2472  }
2473  }
2474 
2475  *result = SCIP_SUCCESS;
2476 
2477  return SCIP_OKAY;
2478 }
2479 
2480 
2481 /** variable rounding lock method of constraint handler */
2482 static
2483 SCIP_DECL_CONSLOCK(consLockBounddisjunction)
2484 { /*lint --e{715}*/
2485  SCIP_CONSDATA* consdata;
2486  int i;
2487 
2488  consdata = SCIPconsGetData(cons);
2489  assert(consdata != NULL);
2490 
2491  /* lock every single coefficient */
2492  for( i = 0; i < consdata->nvars; ++i )
2493  {
2494  if( consdata->boundtypes[i] == SCIP_BOUNDTYPE_LOWER )
2495  {
2496  SCIP_CALL( SCIPaddVarLocks(scip, consdata->vars[i], nlockspos, nlocksneg) );
2497  }
2498  else
2499  {
2500  SCIP_CALL( SCIPaddVarLocks(scip, consdata->vars[i], nlocksneg, nlockspos) );
2501  }
2502  }
2503 
2504  return SCIP_OKAY;
2505 }
2506 
2507 
2508 /** constraint activation notification method of constraint handler */
2509 static
2510 SCIP_DECL_CONSACTIVE(consActiveBounddisjunction)
2511 { /*lint --e{715}*/
2512  SCIP_CONSHDLRDATA* conshdlrdata;
2513  SCIP_CONSDATA* consdata;
2514 
2515  assert(conshdlr != NULL);
2516  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2517  assert(cons != NULL);
2518  assert(SCIPconsIsTransformed(cons));
2519 
2520  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2521  assert(conshdlrdata != NULL);
2522  consdata = SCIPconsGetData(cons);
2523  assert(consdata != NULL);
2524  assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
2525 
2526  SCIPdebugMessage("activating information for bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2527  SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE));
2528 
2529  /* catch events on watched variables */
2530  if( consdata->watchedvar1 != -1 )
2531  {
2532  SCIP_CALL( catchEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar1,
2533  &consdata->filterpos1) );
2534  }
2535  if( consdata->watchedvar2 != -1 )
2536  {
2537  SCIP_CALL( catchEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar2,
2538  &consdata->filterpos2) );
2539  }
2540 
2541  return SCIP_OKAY;
2542 }
2543 
2544 
2545 /** constraint deactivation notification method of constraint handler */
2546 static
2547 SCIP_DECL_CONSDEACTIVE(consDeactiveBounddisjunction)
2548 { /*lint --e{715}*/
2549  SCIP_CONSHDLRDATA* conshdlrdata;
2550  SCIP_CONSDATA* consdata;
2551 
2552  assert(conshdlr != NULL);
2553  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2554  assert(cons != NULL);
2555  assert(SCIPconsIsTransformed(cons));
2556 
2557  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2558  assert(conshdlrdata != NULL);
2559  consdata = SCIPconsGetData(cons);
2560  assert(consdata != NULL);
2561  assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
2562 
2563  SCIPdebugMessage("deactivating information for bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2564  SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE));
2565 
2566  /* drop events on watched variables */
2567  if( consdata->watchedvar1 != -1 )
2568  {
2569  assert(consdata->filterpos1 != -1);
2570  SCIP_CALL( dropEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
2571  }
2572  if( consdata->watchedvar2 != -1 )
2573  {
2574  assert(consdata->filterpos2 != -1);
2575  SCIP_CALL( dropEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
2576  }
2577 
2578  return SCIP_OKAY;
2579 }
2580 
2581 
2582 /** constraint display method of constraint handler */
2583 static
2584 SCIP_DECL_CONSPRINT(consPrintBounddisjunction)
2585 { /*lint --e{715}*/
2586 
2587  assert( scip != NULL );
2588  assert( conshdlr != NULL );
2589  assert( cons != NULL );
2590 
2591  consdataPrint(scip, SCIPconsGetData(cons), file, FALSE);
2592 
2593  return SCIP_OKAY;
2594 }
2595 
2596 /** constraint copying method of constraint handler */
2597 static
2598 SCIP_DECL_CONSCOPY(consCopyBounddisjunction)
2599 { /*lint --e{715}*/
2600  SCIP_VAR** sourcevars;
2601  SCIP_VAR** targetvars;
2602  SCIP_BOUNDTYPE* boundtypes;
2603  SCIP_Real* bounds;
2604  int nvars;
2605  int v;
2606 
2607  assert(valid != NULL);
2608 
2609  *valid = TRUE;
2610 
2611  /* get source data */
2612  sourcevars = SCIPgetVarsBounddisjunction(sourcescip, sourcecons);
2613  nvars = SCIPgetNVarsBounddisjunction(sourcescip, sourcecons);
2614  boundtypes = SCIPgetBoundtypesBounddisjunction(sourcescip, sourcecons);
2615  bounds = SCIPgetBoundsBounddisjunction(sourcescip, sourcecons);
2616 
2617  SCIP_CALL( SCIPallocBufferArray(scip, &targetvars, nvars) );
2618 
2619  /* map source variables to active variables of the target SCIP */
2620  for( v = 0; v < nvars && *valid; ++v )
2621  {
2622  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &targetvars[v], varmap, consmap, global, valid) );
2623  assert(!(*valid) || targetvars[v] != NULL);
2624  }
2625 
2626  /* only create the target constraint, if all variables could be copied */
2627  if( *valid )
2628  {
2629  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name ? name : SCIPconsGetName(sourcecons), nvars, targetvars, boundtypes,
2630  bounds, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2631  }
2632 
2633  SCIPfreeBufferArray(scip, &targetvars);
2634 
2635  return SCIP_OKAY;
2636 }
2637 
2638 /** constraint parsing method of constraint handler */
2639 static
2640 SCIP_DECL_CONSPARSE(consParseBounddisjunction)
2641 { /*lint --e{715}*/
2642  SCIP_BOUNDTYPE* boundtypes;
2643  SCIP_Real* bounds;
2644  SCIP_VAR** vars;
2645  char* endptr;
2646  int varssize;
2647  int nvars;
2648 
2649  assert( success != NULL );
2650  *success = TRUE;
2651 
2652  SCIPdebugMessage("parse <%s> as bounddisjunction constraint\n", str);
2653 
2654  /* skip white space */
2655  while( *str != '\0' && isspace((unsigned char)*str) )
2656  ++str;
2657 
2658  /* check for string "bounddisjunction" */
2659  if( strncmp(str, "bounddisjunction(", 16) != 0 )
2660  {
2661  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "error during parsing: expected \"bounddisjunction(\" in <%s>.\n", str);
2662  *success = FALSE;
2663  return SCIP_OKAY;
2664  }
2665 
2666  /* skip "bounddisjunction(" */
2667  str += 17;
2668 
2669  varssize = 100;
2670  nvars = 0;
2671 
2672  /* allocate buffer array for variables */
2673  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
2674  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, varssize) );
2675  SCIP_CALL( SCIPallocBufferArray(scip, &bounds, varssize) );
2676 
2677  /* parse string until ")" */
2678  while( *str != '\0' && *str != ')' )
2679  {
2680  SCIP_VAR* var;
2681 
2682  /* parse variable name */
2683  SCIP_CALL( SCIPparseVarName(scip, str, &var, &endptr) );
2684  str = endptr;
2685 
2686  if( var == NULL )
2687  {
2688  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "variable with name <%s> does not exist\n", SCIPvarGetName(var));
2689  *success = FALSE;
2690  goto TERMINATE;
2691  }
2692 
2693  /* skip white space */
2694  while( *str != '\0' && isspace((unsigned char)*str) && *str != '>' && *str != '<' )
2695  ++str;
2696 
2697  /* parse bound type */
2698  switch( *str )
2699  {
2700  case '<':
2701  boundtypes[nvars] = SCIP_BOUNDTYPE_UPPER;
2702  break;
2703  case '>':
2704  boundtypes[nvars] = SCIP_BOUNDTYPE_LOWER;
2705  break;
2706  default:
2707  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "variable with name <%s> does not exist\n", SCIPvarGetName(var));
2708  *success = FALSE;
2709  goto TERMINATE;
2710  }
2711 
2712  ++str;
2713  if( *str != '=' )
2714  {
2715  SCIPdebugMessage("expected '=': %s\n", str);
2716  *success = FALSE;
2717  goto TERMINATE;
2718  }
2719 
2720  /* skip '=' */
2721  ++str;
2722 
2723  /* skip white space */
2724  while( *str != '\0' && isspace((unsigned char)*str) )
2725  ++str;
2726 
2727  /* parse bound value */
2728  if( !SCIPstrToRealValue(str, &bounds[nvars], &endptr) )
2729  {
2730  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error during parsing of the weight: %s\n", str);
2731  *success = FALSE;
2732  goto TERMINATE;
2733  }
2734 
2735  /* skip white space */
2736  str = endptr;
2737  while( (*str != '\0' && isspace((unsigned char)*str)) || *str == ',' )
2738  ++str;
2739 
2740  /* set variable */
2741  vars[nvars++] = var;
2742 
2743  /* check if the size of the variable array was big enough */
2744  if( nvars > varssize )
2745  {
2746  /* reallocate memory */
2747  varssize *= 2;
2748  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
2749  SCIP_CALL( SCIPreallocBufferArray(scip, &boundtypes, varssize) );
2750  SCIP_CALL( SCIPreallocBufferArray(scip, &bounds, varssize) );
2751  }
2752  }
2753  /* ignore if the string ended without ")" */
2754 
2755  /* add bounddisjunction */
2756  if( *success && nvars > 0 )
2757  {
2758  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name, nvars, vars, boundtypes, bounds,
2759  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2760  }
2761 
2762  TERMINATE:
2763  /* free variable buffer */
2764  SCIPfreeBufferArray(scip, &bounds);
2765  SCIPfreeBufferArray(scip, &boundtypes);
2766  SCIPfreeBufferArray(scip, &vars);
2767 
2768  return SCIP_OKAY;
2769 }
2770 
2771 /** constraint method of constraint handler which returns the variables (if possible) */
2772 static
2773 SCIP_DECL_CONSGETVARS(consGetVarsBounddisjunction)
2774 { /*lint --e{715}*/
2775  SCIP_CONSDATA* consdata;
2776 
2777  assert(cons != NULL);
2778 
2779  consdata = SCIPconsGetData(cons);
2780  assert(consdata != NULL);
2781 
2782  if( varssize < consdata->nvars )
2783  (*success) = FALSE;
2784  else
2785  {
2786  assert(vars != NULL);
2787 
2788  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
2789  (*success) = TRUE;
2790  }
2791 
2792  return SCIP_OKAY;
2793 }
2794 
2795 /** constraint method of constraint handler which returns the number of variables (if possible) */
2796 static
2797 SCIP_DECL_CONSGETNVARS(consGetNVarsBounddisjunction)
2798 { /*lint --e{715}*/
2799  SCIP_CONSDATA* consdata;
2800 
2801  assert(cons != NULL);
2802 
2803  consdata = SCIPconsGetData(cons);
2804  assert(consdata != NULL);
2805 
2806  (*nvars) = consdata->nvars;
2807  (*success) = TRUE;
2808 
2809  return SCIP_OKAY;
2810 }
2811 
2812 /**@} */
2813 
2814 /**@name Callback methods of event handler
2815  *
2816  */
2817 
2818 static
2819 SCIP_DECL_EVENTEXEC(eventExecBounddisjunction)
2820 { /*lint --e{715}*/
2821  assert(eventhdlr != NULL);
2822  assert(eventdata != NULL);
2823  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
2824  assert(event != NULL);
2825 
2826  /*SCIPdebugMessage("exec method of event handler for bound disjunction constraints\n");*/
2827 
2828  if( (SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDRELAXED) != 0 )
2829  {
2830  SCIP_CALL( SCIPenableCons(scip, (SCIP_CONS*)eventdata) );
2831  }
2832  else
2833  assert((SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDTIGHTENED) != 0);
2834 
2835  SCIP_CALL( SCIPenableConsPropagation(scip, (SCIP_CONS*)eventdata) );
2836 
2837  return SCIP_OKAY;
2838 }
2839 
2840 /**@} */
2841 
2842 /**@name Callback methods of conflict handler
2843  *
2844  * @{
2845  */
2846 
2847 /** conflict handler data struct */
2848 struct SCIP_ConflicthdlrData
2849 {
2850  SCIP_Real continuousfrac; /**< maximal percantage of continuous variables within a conflict */
2851 };
2852 
2853 /** conflict processing method of conflict handler (called when conflict was found) */
2854 static
2855 SCIP_DECL_CONFLICTEXEC(conflictExecBounddisjunction)
2856 { /*lint --e{715}*/
2857  SCIP_VAR** vars;
2858  SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
2859  SCIP_BOUNDTYPE* boundtypes;
2860  SCIP_Real* bounds;
2861  SCIP_CONS* cons;
2862  char consname[SCIP_MAXSTRLEN];
2863  int ncontinuous;
2864  int i;
2865 
2866  assert(conflicthdlr != NULL);
2867  assert(strcmp(SCIPconflicthdlrGetName(conflicthdlr), CONFLICTHDLR_NAME) == 0);
2868  assert(bdchginfos != NULL || nbdchginfos == 0);
2869  assert(result != NULL);
2870 
2871  /* don't process already resolved conflicts */
2872  if( resolved )
2873  {
2874  *result = SCIP_DIDNOTRUN;
2875  return SCIP_OKAY;
2876  }
2877 
2878  conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr);
2879  assert(conflicthdlrdata != NULL);
2880 
2881  *result = SCIP_DIDNOTFIND;
2882  ncontinuous = 0;
2883 
2884  /* create array of variables, boundtypes, and bound values in conflict constraint */
2885  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nbdchginfos) );
2886  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nbdchginfos) );
2887  SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nbdchginfos) );
2888 
2889  for( i = 0; i < nbdchginfos; ++i )
2890  {
2891  assert(bdchginfos != NULL);
2892 
2893  vars[i] = SCIPbdchginfoGetVar(bdchginfos[i]);
2894  boundtypes[i] = SCIPboundtypeOpposite(SCIPbdchginfoGetBoundtype(bdchginfos[i]));
2895  bounds[i] = relaxedbds[i];
2896 
2897  /* check if the relaxed bound is really a relaxed bound */
2898  assert(SCIPbdchginfoGetBoundtype(bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER || SCIPisGE(scip, relaxedbds[i], SCIPbdchginfoGetNewbound(bdchginfos[i])));
2899  assert(SCIPbdchginfoGetBoundtype(bdchginfos[i]) == SCIP_BOUNDTYPE_UPPER || SCIPisLE(scip, relaxedbds[i], SCIPbdchginfoGetNewbound(bdchginfos[i])));
2900 
2901  /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
2902  if( SCIPvarIsIntegral(vars[i]) )
2903  {
2904  assert(SCIPisIntegral(scip, bounds[i]));
2905  bounds[i] += (boundtypes[i] == SCIP_BOUNDTYPE_LOWER ? +1.0 : -1.0);
2906  }
2907  else if( (boundtypes[i] == SCIP_BOUNDTYPE_LOWER && SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(vars[i]), bounds[i]))
2908  || (boundtypes[i] == SCIP_BOUNDTYPE_UPPER && SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(vars[i]), bounds[i])) )
2909  {
2910  /* the literal is satisfied in global bounds (may happen due to weak "negation" of continuous variables)
2911  * -> discard the conflict constraint
2912  */
2913  break;
2914  }
2915  else
2916  ncontinuous++;
2917  }
2918 
2919  /* create a constraint out of the conflict set */
2920  if( i == nbdchginfos && ncontinuous < conflicthdlrdata->continuousfrac * nbdchginfos + 0.5 )
2921  {
2922  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cf%d_%"SCIP_LONGINT_FORMAT, SCIPgetNRuns(scip), SCIPgetNConflictConssApplied(scip));
2923  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, consname, nbdchginfos, vars, boundtypes, bounds,
2924  FALSE, FALSE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
2925  SCIP_CALL( SCIPaddConsNode(scip, node, cons, validnode) );
2926  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2927  *result = SCIP_CONSADDED;
2928  }
2929 
2930  /* free temporary memory */
2931  SCIPfreeBufferArray(scip, &bounds);
2932  SCIPfreeBufferArray(scip, &boundtypes);
2933  SCIPfreeBufferArray(scip, &vars);
2934 
2935  return SCIP_OKAY;
2936 }
2937 
2938 /** free method of conflict handler */
2939 static
2940 SCIP_DECL_CONFLICTFREE(conflictFreeBounddisjunction)
2942  SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
2943 
2944  assert(conflicthdlr != NULL);
2945 
2946  /* get conflict handler data */
2947  conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr);
2948  assert(conflicthdlrdata != NULL);
2949 
2950  /* free conflict handler structure */
2951  SCIPfreeMemory(scip, &conflicthdlrdata);
2952 
2953  return SCIP_OKAY;
2954 }
2955 
2956 /**@} */
2957 
2958 /**@name Interface methods
2959  *
2960  * @{
2961  */
2962 
2963 /** creates the handler for bound disjunction constraints and includes it in SCIP */
2965  SCIP* scip /**< SCIP data structure */
2966  )
2967 {
2968  SCIP_CONSHDLRDATA* conshdlrdata;
2969  SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
2970  SCIP_CONFLICTHDLR* conflicthdlr;
2971  SCIP_CONSHDLR* conshdlr;
2972  SCIP_EVENTHDLR* eventhdlr;
2973 
2974  /* create event handler for events on watched variables */
2976  eventExecBounddisjunction, NULL) );
2977 
2978  /* allocate memory for conflict handler data */
2979  SCIP_CALL( SCIPallocMemory(scip, &conflicthdlrdata) );
2980 
2981  /* create conflict handler parameter */
2983  "conflict/" CONSHDLR_NAME "/continuousfrac", "maximal percantage of continuous variables within a conflict",
2984  &conflicthdlrdata->continuousfrac, FALSE, DEFAULT_CONTINUOUSFRAC, 0.0, 1.0, NULL, NULL) );
2985 
2986  /* create conflict handler for bound disjunction constraints */
2988  conflictExecBounddisjunction, conflicthdlrdata) );
2989 
2990  SCIP_CALL( SCIPsetConflicthdlrFree(scip, conflicthdlr, conflictFreeBounddisjunction) );
2991 
2992  /* create constraint handler data */
2993  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
2994 
2995  /* include constraint handler */
2998  consEnfolpBounddisjunction, consEnfopsBounddisjunction, consCheckBounddisjunction, consLockBounddisjunction,
2999  conshdlrdata) );
3000 
3001  assert(conshdlr != NULL);
3002 
3003  /* set non-fundamental callbacks via specific setter functions */
3004  SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveBounddisjunction) );
3005  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBounddisjunction, consCopyBounddisjunction) );
3006  SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveBounddisjunction) );
3007  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteBounddisjunction) );
3008  SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreBounddisjunction) );
3009  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBounddisjunction) );
3010  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsBounddisjunction) );
3011  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsBounddisjunction) );
3012  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseBounddisjunction) );
3013  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBounddisjunction, CONSHDLR_MAXPREROUNDS,
3015  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintBounddisjunction) );
3016  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropBounddisjunction, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3018  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropBounddisjunction) );
3019  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransBounddisjunction) );
3020 
3021  /* register upgrade of quadratic complementarity constraints in cons_quadratic */
3022  if( SCIPfindConshdlr(scip, "quadratic") )
3023  {
3025  }
3026 
3027  return SCIP_OKAY;
3028 }
3029 
3030 
3031 /** creates and captures a bound disjunction constraint
3032  *
3033  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3034  */
3036  SCIP* scip, /**< SCIP data structure */
3037  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3038  const char* name, /**< name of constraint */
3039  int nvars, /**< number of variables in the constraint */
3040  SCIP_VAR** vars, /**< variables of the literals in the constraint */
3041  SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3042  SCIP_Real* bounds, /**< bounds of the literals */
3043  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3044  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3045  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3046  * Usually set to TRUE. */
3047  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3048  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3049  SCIP_Bool check, /**< should the constraint be checked for feasibility?
3050  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3051  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3052  * Usually set to TRUE. */
3053  SCIP_Bool local, /**< is constraint only valid locally?
3054  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3055  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3056  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3057  * adds coefficients to this constraint. */
3058  SCIP_Bool dynamic, /**< is constraint subject to aging?
3059  * Usually set to FALSE. Set to TRUE for own cuts which
3060  * are separated as constraints. */
3061  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3062  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3063  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3064  * if it may be moved to a more global node?
3065  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3066  )
3067 {
3068  SCIP_CONSHDLR* conshdlr;
3069  SCIP_CONSDATA* consdata;
3070 
3071  assert(scip != NULL);
3072 
3073  /* find the bounddisjunction constraint handler */
3074  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3075  if( conshdlr == NULL )
3076  {
3077  SCIPerrorMessage("bound disjunction constraint handler not found\n");
3078  return SCIP_PLUGINNOTFOUND;
3079  }
3080 
3081  /* create the constraint specific data */
3082  SCIP_CALL( consdataCreate(scip, &consdata, nvars, vars, boundtypes, bounds) );
3083 
3084  /* create constraint */
3085  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3086  local, modifiable, dynamic, removable, stickingatnode) );
3087 
3088  return SCIP_OKAY;
3089 }
3090 
3091 /** creates and captures an and constraint
3092  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
3093  * method SCIPcreateConsBounddisjunction(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
3094  *
3095  * @see SCIPcreateConsBounddisjunction() for information about the basic constraint flag configuration
3096  *
3097  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3098  */
3100  SCIP* scip, /**< SCIP data structure */
3101  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3102  const char* name, /**< name of constraint */
3103  int nvars, /**< number of variables in the constraint */
3104  SCIP_VAR** vars, /**< variables of the literals in the constraint */
3105  SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3106  SCIP_Real* bounds /**< bounds of the literals */
3107  )
3108 {
3109  assert(scip != NULL);
3110 
3111  SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name, nvars, vars, boundtypes, bounds,
3112  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
3113 
3114  return SCIP_OKAY;
3115 }
3116 
3117 /** gets number of variables in bound disjunction constraint */
3119  SCIP* scip, /**< SCIP data structure */
3120  SCIP_CONS* cons /**< constraint data */
3121  )
3122 {
3123  SCIP_CONSDATA* consdata;
3124 
3125  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3126  {
3127  SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3128  SCIPABORT();
3129  return 0; /*lint !e527*/
3130  }
3131 
3132  consdata = SCIPconsGetData(cons);
3133  assert(consdata != NULL);
3134 
3135  return consdata->nvars;
3136 }
3137 
3138 /** gets array of variables in bound disjunction constraint */
3140  SCIP* scip, /**< SCIP data structure */
3141  SCIP_CONS* cons /**< constraint data */
3142  )
3143 {
3144  SCIP_CONSDATA* consdata;
3145 
3146  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3147  {
3148  SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3149  SCIPABORT();
3150  return NULL; /*lint !e527*/
3151  }
3152 
3153  consdata = SCIPconsGetData(cons);
3154  assert(consdata != NULL);
3155 
3156  return consdata->vars;
3157 }
3158 
3159 /** gets array of bound types in bound disjunction constraint */
3161  SCIP* scip, /**< SCIP data structure */
3162  SCIP_CONS* cons /**< constraint data */
3163  )
3164 {
3165  SCIP_CONSDATA* consdata;
3166 
3167  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3168  {
3169  SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3170  SCIPABORT();
3171  return NULL; /*lint !e527*/
3172  }
3173 
3174  consdata = SCIPconsGetData(cons);
3175  assert(consdata != NULL);
3176 
3177  return consdata->boundtypes;
3178 }
3179 
3180 /** gets array of bounds in bound disjunction constraint */
3182  SCIP* scip, /**< SCIP data structure */
3183  SCIP_CONS* cons /**< constraint data */
3184  )
3185 {
3186  SCIP_CONSDATA* consdata;
3187 
3188  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3189  {
3190  SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3191  SCIPABORT();
3192  return NULL; /*lint !e527*/
3193  }
3194 
3195  consdata = SCIPconsGetData(cons);
3196  assert(consdata != NULL);
3197 
3198  return consdata->bounds;
3199 }
3200 
3201 /**@} */
static SCIP_DECL_CONSCHECK(consCheckBounddisjunction)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41572
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int filterpos)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:41685
SCIP_RETCODE SCIPcreateConsBasicBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:5878
#define SCIPallocMemory(scip, ptr)
Definition: scip.h:20526
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip.c:5588
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, int pos)
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip.c:5657
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:25588
SCIP_BILINTERM * SCIPgetBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPcomputeVarUbGlobal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21386
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16443
static SCIP_RETCODE conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:20589
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:41648
SCIP_RETCODE SCIPdelConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons)
Definition: scip.c:12030
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
SCIP_QUADVARTERM * SCIPgetQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:11540
static SCIP_DECL_CONSDELETE(consDeleteBounddisjunction)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16623
#define CONSHDLR_PROPFREQ
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41920
#define SCIP_MAXSTRLEN
Definition: def.h:201
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip.c:5634
#define CONSHDLR_NEEDSCONS
SCIP_BOUNDTYPE * SCIPgetBoundtypesBounddisjunction(SCIP *scip, SCIP_CONS *cons)
#define NULL
Definition: lpi_spx.cpp:130
static SCIP_RETCODE applyGlobalBounds(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *redundant)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1125
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:7849
SCIP_Longint SCIPvarGetNBranchingsCurrentRun(SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: var.c:14948
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip.c:5334
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17067
static SCIP_RETCODE disableCons(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip.c:24320
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21407
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip.c:5818
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, 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_setppc.c:8948
#define isFeasGT(scip, var, val1, val2)
static SCIP_DECL_CONSGETVARS(consGetVarsBounddisjunction)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:7909
#define FALSE
Definition: def.h:56
#define isFeasGE(scip, var, val1, val2)
SCIP_RETCODE SCIPenableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:25727
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
#define CONFLICTHDLR_DESC
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:7778
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:8174
#define TRUE
Definition: def.h:55
SCIP_RETCODE SCIPsetConflicthdlrFree(SCIP *scip, SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTFREE((*conflictfree)))
Definition: scip.c:6010
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int *filterpos)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:7640
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip.c:33396
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPbdchginfoGetNewbound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:17648
#define CONSHDLR_PROP_TIMING
SCIP_RETCODE SCIPvarGetProbvarBound(SCIP_VAR **var, SCIP_Real *bound, SCIP_BOUNDTYPE *boundtype)
Definition: var.c:11728
#define CONFLICTHDLR_PRIORITY
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip.c:5795
#define SCIP_CALL(x)
Definition: def.h:266
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:15737
static SCIP_DECL_CONSTRANS(consTransBounddisjunction)
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:34983
#define SCIP_LONGINT_MAX
Definition: def.h:113
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:7839
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:7779
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip.c:26237
Constraint handler for the set partitioning / packing / covering constraints .
static SCIP_DECL_CONSFREE(consFreeBounddisjunction)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:24949
#define CONSHDLR_ENFOPRIORITY
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_Real bound)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:20554
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip.c:5359
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:7769
#define CONSHDLR_DELAYPROP
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:20572
SCIP_Real SCIPcomputeVarLbGlobal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21365
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip.c:24720
static SCIP_Bool isLiteralSatisfied(SCIP *scip, SCIP_CONSDATA *consdata, int pos)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16562
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip.c:16156
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:56
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16634
SCIP_BOUNDTYPE SCIPbdchginfoGetBoundtype(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:17678
#define CONSHDLR_EAGERFREQ
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:3917
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip.c:5680
SCIP_VAR * SCIPbdchginfoGetVar(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:17658
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:36622
#define SCIPfreeMemory(scip, ptr)
Definition: scip.h:20542
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip)
Definition: scip.c:24342
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41585
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:16585
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.c:1781
static SCIP_DECL_QUADCONSUPGD(upgradeConsQuadratic)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:7879
int SCIPgetNLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
#define SCIPerrorMessage
Definition: pub_message.h:45
#define CONSHDLR_NAME
static SCIP_DECL_CONSGETNVARS(consGetNVarsBounddisjunction)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:20574
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip.c:19526
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip.c:33651
#define QUADCONSUPGD_PRIORITY
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:3897
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:15859
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41598
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip.c:17163
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:5527
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7620
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41907
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:146
constraint handler for quadratic constraints
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
Definition: scip.c:5503
static SCIP_DECL_CONSENFOLP(consEnfolpBounddisjunction)
#define CONSHDLR_CHECKPRIORITY
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:20562
SCIP_RETCODE SCIPincludeConflicthdlrBasic(SCIP *scip, SCIP_CONFLICTHDLR **conflicthdlrptr, const char *name, const char *desc, int priority, SCIP_DECL_CONFLICTEXEC((*conflictexec)), SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
Definition: scip.c:5962
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:58
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:41637
struct SCIP_ConflicthdlrData SCIP_CONFLICTHDLRDATA
Definition: type_conflict.h:40
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip.c:5292
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:55
SCIP_Bool SCIPconsIsPropagationEnabled(SCIP_CONS *cons)
Definition: cons.c:7728
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.c:5192
static SCIP_DECL_CONSPARSE(consParseBounddisjunction)
int SCIPconsGetValidDepth(SCIP_CONS *cons)
Definition: cons.c:7693
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:32131
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41946
const char * SCIPconflicthdlrGetName(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict.c:706
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:50
#define SCIP_EVENTTYPE_BOUNDTIGHTENED
Definition: type_event.h:97
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:7650
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip.c:11929
SCIP_RETCODE SCIPcreateConsBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, 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)
#define AGEINCREASE(n)
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip.c:17116
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41611
static SCIP_RETCODE processWatchedVars(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, SCIP_Bool *infeasible, SCIP_Bool *reduceddom, SCIP_Bool *mustcheck)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:20193
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip.c:997
public data structures and miscellaneous methods
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.c:24772
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
#define SCIP_Bool
Definition: def.h:53
#define isFeasLT(scip, var, val1, val2)
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21428
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBounddisjunction)
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:801
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:7859
static SCIP_DECL_CONSACTIVE(consActiveBounddisjunction)
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:8245
static SCIP_RETCODE removeFixedVariables(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *redundant)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:7869
SCIP_Bool SCIPconsIsAdded(SCIP_CONS *cons)
Definition: cons.c:7969
SCIP_Real coef
int SCIPgetNQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_CONSRESPROP(consRespropBounddisjunction)
int SCIPgetNRuns(SCIP *scip)
Definition: scip.c:37318
SCIP_BOUNDTYPE SCIPboundtypeOpposite(SCIP_BOUNDTYPE boundtype)
Definition: lp.c:18826
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:89
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated)
static SCIP_DECL_CONSPRESOL(consPresolBounddisjunction)
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:57
Constraint handler for linear constraints in their most general form, .
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:38140
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1298
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41624
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:19898
static SCIP_Bool isLiteralViolated(SCIP *scip, SCIP_CONSDATA *consdata, int pos)
SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:20469
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:36668
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip.c:5565
#define isFeasLE(scip, var, val1, val2)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:11477
static SCIP_DECL_CONSENFOPS(consEnfopsBounddisjunction)
SCIP_CONFLICTHDLRDATA * SCIPconflicthdlrGetData(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict.c:619
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16608
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:20585
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17057
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip.c:5772
static SCIP_RETCODE upgradeCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss)
SCIP_RETCODE SCIPdisableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:25647
#define EVENTHDLR_DESC
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1281
#define REALABS(x)
Definition: def.h:151
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, int pos)
int SCIPgetNBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:41721
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, 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)
SCIP_RETCODE SCIPaddConsAge(SCIP *scip, SCIP_CONS *cons, SCIP_Real deltaage)
Definition: scip.c:25531
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:278
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41933
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip.c:19453
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:19931
#define SCIP_Real
Definition: def.h:127
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:7799
SCIP_RETCODE SCIPincludeConshdlrBounddisjunction(SCIP *scip)
static SCIP_DECL_CONSPROP(consPropBounddisjunction)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:20299
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41959
SCIP_RETCODE SCIPincludeQuadconsUpgrade(SCIP *scip, SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), int priority, SCIP_Bool active, const char *conshdlrname)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:20568
SCIP_Longint SCIPgetNConflictConssApplied(SCIP *scip)
Definition: scip.c:38114
#define SCIP_Longint
Definition: def.h:112
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:917
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:20571
static void consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file, SCIP_Bool endline)
static SCIP_RETCODE createNAryBranch(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
Definition: scip.c:19399
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds)
SCIP_RETCODE SCIPenableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:25613
static SCIP_RETCODE registerBranchingCandidates(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *neednarybranch)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:49
#define EVENTHDLR_NAME
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:20597
static SCIP_DECL_CONSCOPY(consCopyBounddisjunction)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16730
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip.c:33701
#define SCIPdebug(x)
Definition: pub_message.h:74
static SCIP_DECL_CONSEXITPRE(consExitpreBounddisjunction)
#define CONSHDLR_DESC
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:41422
SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_CONFLICTFREE(conflictFreeBounddisjunction)
static SCIP_DECL_CONFLICTEXEC(conflictExecBounddisjunction)
constraint handler for bound disjunction constraints
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip.c:33678
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:3629
#define CONFLICTHDLR_NAME
static SCIP_DECL_CONSPRINT(consPrintBounddisjunction)
static SCIP_DECL_EVENTEXEC(eventExecBounddisjunction)
#define CONSHDLR_MAXPREROUNDS
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip.c:5841
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, 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)
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11481
#define SCIPABORT()
Definition: def.h:238
SCIP_RETCODE SCIPdisableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:25757
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:7789
#define CONSHDLR_PRESOLTIMING
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:7819
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:3927
SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons)
#define DEFAULT_CONTINUOUSFRAC
static SCIP_RETCODE enforceCurrentSol(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, SCIP_Bool *infeasible, SCIP_Bool *reduceddom, SCIP_Bool *registeredbrcand)
static SCIP_DECL_CONSDEACTIVE(consDeactiveBounddisjunction)
static SCIP_RETCODE switchWatchedvars(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
SCIP_Real * SCIPgetBoundsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddConflictBd(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:24504
static SCIP_DECL_CONSLOCK(consLockBounddisjunction)
#define SCIP_EVENTTYPE_BOUNDRELAXED
Definition: type_event.h:98