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