Scippy

SCIP

Solving Constraint Integer Programs

cons_logicor.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-2018 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_logicor.c
17  * @brief Constraint handler for logic or constraints \f$1^T x \ge 1\f$
18  * (equivalent to set covering, but algorithms are suited for depth first search).
19  * @author Tobias Achterberg
20  * @author Michael Winkler
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include "blockmemshell/memory.h"
26 #include "scip/cons_linear.h"
27 #include "scip/cons_logicor.h"
28 #include "scip/cons_setppc.h"
29 #include "scip/presolve.h"
30 #include "scip/pub_conflict.h"
31 #include "scip/pub_cons.h"
32 #include "scip/pub_event.h"
33 #include "scip/pub_lp.h"
34 #include "scip/pub_message.h"
35 #include "scip/pub_misc.h"
36 #include "scip/pub_misc_sort.h"
37 #include "scip/pub_var.h"
38 #include "scip/scip_conflict.h"
39 #include "scip/scip_cons.h"
40 #include "scip/scip_cut.h"
41 #include "scip/scip_event.h"
42 #include "scip/scip_general.h"
43 #include "scip/scip_lp.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 <string.h>
55 
56 
57 #define CONSHDLR_NAME "logicor"
58 #define CONSHDLR_DESC "logic or constraints"
59 #define CONSHDLR_SEPAPRIORITY +10000 /**< priority of the constraint handler for separation */
60 #define CONSHDLR_ENFOPRIORITY -2000000 /**< priority of the constraint handler for constraint enforcing */
61 #define CONSHDLR_CHECKPRIORITY -2000000 /**< priority of the constraint handler for checking feasibility */
62 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
63 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
64 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
65  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
66 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
67 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
68 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
69 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
70 
71 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
72 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
73 
74 #define LINCONSUPGD_PRIORITY +800000 /**< priority of the constraint handler for upgrading of linear constraints */
75 
76 #define EVENTHDLR_NAME "logicor"
77 #define EVENTHDLR_DESC "event handler for logic or constraints"
78 
79 #define CONFLICTHDLR_NAME "logicor"
80 #define CONFLICTHDLR_DESC "conflict handler creating logic or constraints"
81 #define CONFLICTHDLR_PRIORITY LINCONSUPGD_PRIORITY
82 
83 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
84 #define DEFAULT_STRENGTHEN TRUE /**< should pairwise constraint comparison try to strengthen constraints by removing superflous non-zeros? */
85 
86 #define HASHSIZE_LOGICORCONS 500 /**< minimal size of hash table in logicor constraint tables */
87 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
88 #define DEFAULT_DUALPRESOLVING TRUE /**< should dual presolving steps be performed? */
89 #define DEFAULT_NEGATEDCLIQUE TRUE /**< should negated clique information be used in presolving */
90 #define DEFAULT_IMPLICATIONS TRUE /**< should we try to shrink the variables and derive global boundchanges by
91  * using cliques and implications */
92 
93 /* @todo make this a parameter setting */
94 #if 1 /* @todo test which AGEINCREASE formula is better! */
95 #define AGEINCREASE(n) (1.0 + 0.2 * (n))
96 #else
97 #define AGEINCREASE(n) (0.1 * (n))
98 #endif
99 
100 
101 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
102 
103 /*
104  * Data structures
105  */
106 
107 /** constraint handler data */
108 struct SCIP_ConshdlrData
109 {
110  SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */
111  SCIP_CONSHDLR* conshdlrlinear; /**< pointer to linear constraint handler or NULL if not included */
112  SCIP_CONSHDLR* conshdlrsetppc; /**< pointer to setppc constraint handler or NULL if not included */
113  SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
114  SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in
115  * advance */
116  SCIP_Bool dualpresolving; /**< should dual presolving steps be performed? */
117  SCIP_Bool usenegatedclique; /**< should negated clique information be used in presolving */
118  SCIP_Bool useimplications; /**< should we try to shrink the variables and derive global boundchanges
119  * by using clique and implications */
120  SCIP_Bool usestrengthening; /**< should pairwise constraint comparison try to strengthen constraints by
121  * removing superflous non-zeros? */
122  int nlastcliquesneg; /**< number of cliques after last negated clique presolving round */
123  int nlastimplsneg; /**< number of implications after last negated clique presolving round */
124  int nlastcliquesshorten;/**< number of cliques after last shortening of constraints */
125  int nlastimplsshorten; /**< number of implications after last shortening of constraints */
126 };
127 
128 /* @todo it might speed up exit-presolve to remember all positions for variables when catching the varfixed event, or we
129  * change catching and dropping the events like it is done in cons_setppc, which probably makes the code more
130  * clear
131  */
132 
133 /** logic or constraint data */
134 struct SCIP_ConsData
135 {
136  SCIP_ROW* row; /**< LP row, if constraint is already stored in LP row format */
137  SCIP_VAR** vars; /**< variables of the constraint */
138  int varssize; /**< size of vars array */
139  int nvars; /**< number of variables in the constraint */
140  int watchedvar1; /**< position of the first watched variable */
141  int watchedvar2; /**< position of the second watched variable */
142  int filterpos1; /**< event filter position of first watched variable */
143  int filterpos2; /**< event filter position of second watched variable */
144  unsigned int signature; /**< constraint signature which is need for pairwise comparison */
145  unsigned int presolved:1; /**< flag indicates if we have some fixed, aggregated or multi-aggregated
146  * variables
147  */
148  unsigned int impladded:1; /**< was the 2-variable logic or constraint already added as implication? */
149  unsigned int sorted:1; /**< are the constraint's variables sorted? */
150  unsigned int changed:1; /**< was constraint changed since last redundancy round in preprocessing? */
151  unsigned int merged:1; /**< are the constraint's equal/negated variables already merged? */
152  unsigned int existmultaggr:1; /**< does this constraint contain aggregations */
153  unsigned int validsignature:1; /**< is the signature valid */
154 };
155 
156 
157 /*
158  * Local methods
159  */
160 
161 /** installs rounding locks for the given variable in the given logic or constraint */
162 static
164  SCIP* scip, /**< SCIP data structure */
165  SCIP_CONS* cons, /**< logic or constraint */
166  SCIP_VAR* var /**< variable of constraint entry */
167  )
168 {
169  SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, FALSE) );
170 
171  return SCIP_OKAY;
172 }
173 
174 /** removes rounding locks for the given variable in the given logic or constraint */
175 static
177  SCIP* scip, /**< SCIP data structure */
178  SCIP_CONS* cons, /**< logic or constraint */
179  SCIP_VAR* var /**< variable of constraint entry */
180  )
181 {
182  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, FALSE) );
183 
184  return SCIP_OKAY;
185 }
186 
187 /** creates constraint handler data for logic or constraint handler */
188 static
190  SCIP* scip, /**< SCIP data structure */
191  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
192  SCIP_EVENTHDLR* eventhdlr /**< event handler */
193  )
194 {
195  assert(scip != NULL);
196  assert(conshdlrdata != NULL);
197  assert(eventhdlr != NULL);
198 
199  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
200 
201  (*conshdlrdata)->nlastcliquesneg = 0;
202  (*conshdlrdata)->nlastimplsneg = 0;
203  (*conshdlrdata)->nlastcliquesshorten = 0;
204  (*conshdlrdata)->nlastimplsshorten = 0;
205 
206  /* set event handler for catching events on watched variables */
207  (*conshdlrdata)->eventhdlr = eventhdlr;
208 
209  return SCIP_OKAY;
210 }
211 
212 /** frees constraint handler data for logic or constraint handler */
213 static
215  SCIP* scip, /**< SCIP data structure */
216  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
217  )
218 {
219  assert(conshdlrdata != NULL);
220  assert(*conshdlrdata != NULL);
221 
222  SCIPfreeBlockMemory(scip, conshdlrdata);
223 
224  return SCIP_OKAY;
225 }
226 
227 /** ensures, that the vars array can store at least num entries */
228 static
230  SCIP* scip, /**< SCIP data structure */
231  SCIP_CONSDATA* consdata, /**< logicor constraint data */
232  int num /**< minimum number of entries to store */
233  )
234 {
235  assert(consdata != NULL);
236  assert(consdata->nvars <= consdata->varssize);
237 
238  if( num > consdata->varssize )
239  {
240  int newsize;
241 
242  newsize = SCIPcalcMemGrowSize(scip, num);
243  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
244  consdata->varssize = newsize;
245  }
246  assert(num <= consdata->varssize);
247 
248  return SCIP_OKAY;
249 }
250 
251 /** creates a logic or constraint data object */
252 static
254  SCIP* scip, /**< SCIP data structure */
255  SCIP_CONSDATA** consdata, /**< pointer to store the logic or constraint data */
256  int nvars, /**< number of variables in the constraint */
257  SCIP_VAR** vars /**< variables of the constraint */
258  )
259 {
260  int v;
261 
262  assert(consdata != NULL);
263  assert(nvars == 0 || vars != NULL);
264 
265  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
266 
267  (*consdata)->row = NULL;
268  if( nvars > 0 )
269  {
270  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
271  (*consdata)->varssize = nvars;
272  (*consdata)->nvars = nvars;
273  }
274  else
275  {
276  (*consdata)->vars = NULL;
277  (*consdata)->varssize = 0;
278  (*consdata)->nvars = 0;
279  }
280  (*consdata)->watchedvar1 = -1;
281  (*consdata)->watchedvar2 = -1;
282  (*consdata)->filterpos1 = -1;
283  (*consdata)->filterpos2 = -1;
284  (*consdata)->presolved = FALSE;
285  (*consdata)->impladded = FALSE;
286  (*consdata)->changed = TRUE;
287  (*consdata)->sorted = (nvars <= 1);
288  (*consdata)->merged = (nvars <= 1);
289  (*consdata)->existmultaggr = FALSE;
290  (*consdata)->validsignature = FALSE;
291 
292  /* get transformed variables, if we are in the transformed problem */
293  if( SCIPisTransformed(scip) )
294  {
295  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
296 
297  /* check for multi-aggregations and capture variables */
298  for( v = 0; v < (*consdata)->nvars; v++ )
299  {
300  SCIP_VAR* var = SCIPvarGetProbvar((*consdata)->vars[v]);
301  assert(var != NULL);
302  (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
303  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
304  }
305  }
306  else
307  {
308  /* capture variables */
309  for( v = 0; v < (*consdata)->nvars; v++ )
310  {
311  assert((*consdata)->vars[v] != NULL);
312  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
313  }
314  }
315 
316  return SCIP_OKAY;
317 }
318 
319 /** frees a logic or constraint data */
320 static
322  SCIP* scip, /**< SCIP data structure */
323  SCIP_CONSDATA** consdata /**< pointer to the logic or constraint */
324  )
325 {
326  int v;
327 
328  assert(consdata != NULL);
329  assert(*consdata != NULL);
330 
331  /* release the row */
332  if( (*consdata)->row != NULL )
333  {
334  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
335  }
336 
337  /* release variables */
338  for( v = 0; v < (*consdata)->nvars; v++ )
339  {
340  assert((*consdata)->vars[v] != NULL);
341  SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
342  }
343 
344  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
345  SCIPfreeBlockMemory(scip, consdata);
346 
347  return SCIP_OKAY;
348 }
349 
350 /** prints logic or constraint to file stream */
351 static
353  SCIP* scip, /**< SCIP data structure */
354  SCIP_CONSDATA* consdata, /**< logic or constraint data */
355  FILE* file, /**< output file (or NULL for standard output) */
356  SCIP_Bool endline /**< should an endline be set? */
357  )
358 {
359  assert(consdata != NULL);
360 
361  /* print constraint type */
362  SCIPinfoMessage(scip, file, "logicor(");
363 
364  /* print variable list */
365  SCIP_CALL( SCIPwriteVarsList(scip, file, consdata->vars, consdata->nvars, TRUE, ',') );
366 
367  /* close bracket */
368  SCIPinfoMessage(scip, file, ")");
369 
370  if( endline )
371  SCIPinfoMessage(scip, file, "\n");
372 
373  return SCIP_OKAY;
374 }
375 
376 /** stores the given variable numbers as watched variables, and updates the event processing */
377 static
379  SCIP* scip, /**< SCIP data structure */
380  SCIP_CONS* cons, /**< logic or constraint */
381  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
382  int watchedvar1, /**< new first watched variable */
383  int watchedvar2 /**< new second watched variable */
384  )
385 {
386  SCIP_CONSDATA* consdata;
387 
388  consdata = SCIPconsGetData(cons);
389  assert(consdata != NULL);
390  assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
391  assert(watchedvar1 != -1 || watchedvar2 == -1);
392  assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
393  assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
394 
395  /* if one watched variable is equal to the old other watched variable, just switch positions */
396  if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
397  {
398  int tmp;
399 
400  tmp = consdata->watchedvar1;
401  consdata->watchedvar1 = consdata->watchedvar2;
402  consdata->watchedvar2 = tmp;
403  tmp = consdata->filterpos1;
404  consdata->filterpos1 = consdata->filterpos2;
405  consdata->filterpos2 = tmp;
406  }
407  assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
408  assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
409 
410  /* drop events on old watched variables */
411  if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
412  {
413  assert(consdata->filterpos1 != -1);
414  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar1],
416  consdata->filterpos1) );
417  }
418  if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
419  {
420  assert(consdata->filterpos2 != -1);
421  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar2],
423  consdata->filterpos2) );
424  }
425 
426  /* catch events on new watched variables */
427  if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
428  {
429  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[watchedvar1],
431  &consdata->filterpos1) );
432  }
433  if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
434  {
435  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[watchedvar2],
437  &consdata->filterpos2) );
438  }
439 
440  /* set the new watched variables */
441  consdata->watchedvar1 = watchedvar1;
442  consdata->watchedvar2 = watchedvar2;
443 
444  return SCIP_OKAY;
445 }
446 
447 /** adds coefficient in logicor constraint */
448 static
450  SCIP* scip, /**< SCIP data structure */
451  SCIP_CONS* cons, /**< logicor constraint */
452  SCIP_VAR* var /**< variable to add to the constraint */
453  )
454 {
455  SCIP_CONSDATA* consdata;
456  SCIP_Bool transformed;
457 
458  assert(var != NULL);
459 
460  consdata = SCIPconsGetData(cons);
461  assert(consdata != NULL);
462 
463  /* are we in the transformed problem? */
464  transformed = SCIPconsIsTransformed(cons);
465 
466  /* always use transformed variables in transformed constraints */
467  if( transformed )
468  {
469  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
470 
471  if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR )
472  consdata->existmultaggr = TRUE;
473 
474  consdata->presolved = FALSE;
475  }
476  assert(var != NULL);
477  assert(transformed == SCIPvarIsTransformed(var));
478 
479  SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars + 1) );
480  consdata->vars[consdata->nvars] = var;
481  SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[consdata->nvars]) );
482  consdata->nvars++;
483 
484  /* we only catch this event in presolving stage */
486  {
487  SCIP_CONSHDLRDATA* conshdlrdata;
488  SCIP_CONSHDLR* conshdlr;
489 
490  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
491  assert(conshdlr != NULL);
492  conshdlrdata = SCIPconshdlrGetData(conshdlr);
493  assert(conshdlrdata != NULL);
494 
495  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
496  (SCIP_EVENTDATA*)cons, NULL) );
497  }
498 
499  consdata->sorted = (consdata->nvars == 1);
500  consdata->changed = TRUE;
501  consdata->validsignature = FALSE;
502 
503  /* install the rounding locks for the new variable */
504  SCIP_CALL( lockRounding(scip, cons, var) );
505 
506  /* add the new coefficient to the LP row */
507  if( consdata->row != NULL )
508  {
509  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, 1.0) );
510  }
511 
512  consdata->merged = FALSE;
513 
514  return SCIP_OKAY;
515 }
516 
517 /** deletes coefficient at given position from logic or constraint data */
518 static
520  SCIP* scip, /**< SCIP data structure */
521  SCIP_CONS* cons, /**< logic or constraint */
522  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
523  int pos /**< position of coefficient to delete */
524  )
525 {
526  SCIP_CONSDATA* consdata;
527 
528  assert(eventhdlr != NULL);
529 
530  consdata = SCIPconsGetData(cons);
531  assert(consdata != NULL);
532  assert(0 <= pos && pos < consdata->nvars);
533  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
534 
535  /* remove the rounding locks of variable */
536  SCIP_CALL( unlockRounding(scip, cons, consdata->vars[pos]) );
537 
538  /* we only catch this event in presolving stage, so we need to only drop it there */
540  {
541  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_VARFIXED, eventhdlr,
542  (SCIP_EVENTDATA*)cons, -1) );
543  }
544 
545  if( SCIPconsIsTransformed(cons) )
546  {
547  /* if the position is watched, stop watching the position */
548  if( consdata->watchedvar1 == pos )
549  {
550  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar2, -1) );
551  }
552  if( consdata->watchedvar2 == pos )
553  {
554  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, -1) );
555  }
556  }
557  assert(pos != consdata->watchedvar1);
558  assert(pos != consdata->watchedvar2);
559 
560  /* release variable */
561  SCIP_CALL( SCIPreleaseVar(scip, &consdata->vars[pos]) );
562 
563  /* move the last variable to the free slot */
564  if( pos != consdata->nvars - 1 )
565  {
566  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
567  consdata->sorted = FALSE;
568  }
569  consdata->nvars--;
570 
571  /* if the last variable (that moved) was watched, update the watched position */
572  if( consdata->watchedvar1 == consdata->nvars )
573  consdata->watchedvar1 = pos;
574  if( consdata->watchedvar2 == consdata->nvars )
575  consdata->watchedvar2 = pos;
576 
577  consdata->changed = TRUE;
578  consdata->validsignature = FALSE;
579 
580  SCIP_CALL( SCIPenableConsPropagation(scip, cons) );
581 
582  return SCIP_OKAY;
583 }
584 
585 /** in case a part (more than one variable) in the logic or constraint is independent of every else, we can perform dual
586  * reductions;
587  * - fix the variable with the smallest object coefficient to one if the constraint is not modifiable and all
588  * variable are independant
589  * - fix all independant variables with negative object coefficient to one
590  * - fix all remaining independant variables to zero
591  *
592  * also added the special case were exactly one variable is locked by this constraint and another variable without any
593  * uplocks has a better objective value than this single variable
594  * - here we fix the variable to 0.0 (if the objective contribution is non-negative)
595  *
596  * Note: the following dual reduction for logic or constraints is already performed by the presolver "dualfix"
597  * - if a variable in a set covering constraint is only locked by that constraint and has negative or zero
598  * objective coefficient than it can be fixed to one
599  */
600 static
602  SCIP* scip, /**< SCIP data structure */
603  SCIP_CONS* cons, /**< setppc constraint */
604  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
605  int* nfixedvars, /**< pointer to count number of fixings */
606  int* ndelconss, /**< pointer to count number of deleted constraints */
607  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
608  SCIP_RESULT* result /**< pointer to store the result SCIP_SUCCESS, if presolving was performed */
609  )
610 {
611  SCIP_CONSDATA* consdata;
612  SCIP_VAR** vars;
613  SCIP_VAR* var;
614  SCIP_VAR* activevar;
615  SCIP_Real bestobjval;
616  SCIP_Real bestobjvalnouplocks;
617  SCIP_Real objval;
618  SCIP_Real fixval;
619  SCIP_Bool infeasible;
620  SCIP_Bool fixed;
621  SCIP_Bool negated;
622  int nfixables;
623  int nvars;
624  int idx;
625  int idxnouplocks;
626  int v;
627 
628  assert(scip != NULL);
629  assert(cons != NULL);
630  assert(eventhdlr != NULL);
631  assert(nfixedvars != NULL);
632  assert(ndelconss != NULL);
633  assert(nchgcoefs != NULL);
634  assert(result != NULL);
635 
636  /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
637  * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are
638  * added to the problems have the check flag set to FALSE
639  */
640  if( !SCIPconsIsChecked(cons) )
641  return SCIP_OKAY;
642 
643  assert(SCIPconsIsActive(cons));
644 
645  consdata = SCIPconsGetData(cons);
646  assert(consdata != NULL);
647 
648  nvars = consdata->nvars;
649 
650  /* we don't want to consider small constraints (note that the constraints can be modifiable, so we can't delete this
651  * constraint)
652  */
653  if( nvars < 2 )
654  return SCIP_OKAY;
655 
656  vars = consdata->vars;
657  idx = -1;
658  idxnouplocks = -1;
659  bestobjval = SCIP_INVALID;
660  bestobjvalnouplocks = SCIP_INVALID;
661 
662  nfixables = 0;
663 
664  /* check if we can apply the dual reduction; therefore count the number of variables where the logic or has the only
665  * locks on
666  */
667  for( v = nvars - 1; v >= 0; --v )
668  {
669  var = vars[v];
670  assert(var != NULL);
671 
672  /* variables with varstatus not equal to SCIP_VARSTATUS_FIXED can also have fixed bounds, but were not removed yet */
673  if( SCIPvarGetUbGlobal(var) < 0.5 )
674  {
675 #ifndef NDEBUG
676  SCIP_VAR* bestvar = NULL;
677 #endif
678  if( idx == consdata->nvars - 1 )
679  {
680 #ifndef NDEBUG
681  bestvar = consdata->vars[idx];
682 #endif
683  idx = v;
684  }
685 
686  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
687  ++(*nchgcoefs);
688 
689  assert(bestvar == NULL || bestvar == consdata->vars[v]);
690 
691  continue;
692  }
693  if( SCIPvarGetLbGlobal(var) > 0.5 )
694  {
695  /* remove constraint since it is redundant */
696  SCIP_CALL( SCIPdelCons(scip, cons) );
697  ++(*ndelconss);
698 
699  return SCIP_OKAY;
700  }
701 
702  /* remember best variable with no uplocks, this variable dominates all other with exactly one downlock */
705  {
706  SCIP_CALL( SCIPvarGetAggregatedObj(var, &objval) );
707 
708  /* check if the current variable has a smaller objective coefficient then the best one */
709  if( SCIPisLT(scip, objval, bestobjval) )
710  {
711  idxnouplocks = v;
712  bestobjvalnouplocks = objval;
713  }
714  }
715 
716  /* in case an other constraints has also locks on that variable we cannot perform a dual reduction on these
717  * variables
718  */
721  continue;
722 
723  ++nfixables;
724  negated = FALSE;
725 
726  /* get the active variable */
727  SCIP_CALL( SCIPvarGetProbvarBinary(&var, &negated) );
728  assert(SCIPvarIsActive(var));
729 
730  if( negated )
731  objval = -SCIPvarGetObj(var);
732  else
733  objval = SCIPvarGetObj(var);
734 
735  /* check if the current variable has a smaller objective coefficient */
736  if( SCIPisLT(scip, objval, bestobjval) )
737  {
738  idx = v;
739  bestobjval = objval;
740  }
741  }
742 
743  nvars = consdata->nvars;
744 
745  /* check if we have a single variable dominated by another */
746  if( nfixables == 1 && idxnouplocks >= 0 )
747  {
748  assert(bestobjvalnouplocks != SCIP_INVALID); /*lint !e777*/
749 
750  for( v = nvars - 1; v >= 0; --v )
751  {
752  var = vars[v];
753  assert(var != NULL);
754 
755  /* check if a variable only appearing in this constraint is dominated by another */
758  {
759  assert(idxnouplocks != v);
760 
761  SCIP_CALL( SCIPvarGetAggregatedObj(var, &objval) );
762 
763  if( SCIPisGE(scip, objval, bestobjvalnouplocks) && !SCIPisNegative(scip, objval) )
764  {
765  SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
766  assert(!infeasible);
767  assert(fixed);
768 
769  SCIPdebugMsg(scip, " -> dual fixing <%s> == 0.0\n", SCIPvarGetName(var));
770  ++(*nfixedvars);
771  }
772 
773  break;
774  }
775  }
776  }
777 
778  if( nfixables < 2 )
779  return SCIP_OKAY;
780 
781  nvars = consdata->nvars;
782 
783  assert(idx >= 0 && idx < nvars);
784  assert(bestobjval < SCIPinfinity(scip));
785 
786  *result = SCIP_SUCCESS;
787 
788  /* fix all redundant variables to their best bound */
789 
790  /* first part of all variables */
791  for( v = 0; v < nvars; ++v )
792  {
793  var = vars[v];
794  assert(var != NULL);
795 
796  /* in case an other constraints has also locks on that variable we cannot perform a dual reduction on these
797  * variables
798  */
801  continue;
802 
803  if( v == idx )
804  continue;
805 
806  activevar = var;
807  negated = FALSE;
808 
809  /* get the active variable */
810  SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
811  assert(SCIPvarIsActive(activevar));
812 
813  if( negated )
814  objval = -SCIPvarGetObj(activevar);
815  else
816  objval = SCIPvarGetObj(activevar);
817 
818  if( objval > 0.0 )
819  fixval = 0.0;
820  else
821  fixval = 1.0;
822 
823  SCIP_CALL( SCIPfixVar(scip, var, fixval, &infeasible, &fixed) );
824  assert(!infeasible);
825  assert(fixed);
826 
827  SCIPdebugMsg(scip, " -> dual fixing <%s> == %g\n", SCIPvarGetName(var), fixval);
828  ++(*nfixedvars);
829  }
830 
831  /* if all variable have our appreciated number of locks and the constraint is not modifiable, or if the bestobjval is
832  * less than or equal to zero, we can fix the variable with the smallest objective coefficient to one and the
833  * constraint gets redundant
834  */
835  if( (nfixables == nvars && !SCIPconsIsModifiable(cons)) || bestobjval <= 0.0 )
836  {
837  SCIP_CALL( SCIPfixVar(scip, vars[idx], 1.0, &infeasible, &fixed) );
838  assert(!infeasible);
839  assert(fixed);
840 
841  SCIPdebugMsg(scip, " -> fixed <%s> == 1.0\n", SCIPvarGetName(vars[idx]));
842  ++(*nfixedvars);
843 
844  /* remove constraint since it is now redundant */
845  SCIP_CALL( SCIPdelCons(scip, cons) );
846  ++(*ndelconss);
847  }
848 
849  return SCIP_OKAY;
850 }
851 
852 /** deletes all zero-fixed variables, checks for variables fixed to one, replace all variables which are not active or
853  * not a negation of an active variable by there active or negation of an active counterpart
854  */
855 static
857  SCIP* scip, /**< SCIP data structure */
858  SCIP_CONS* cons, /**< logic or constraint */
859  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
860  SCIP_Bool* redundant, /**< returns whether a variable fixed to one exists in the constraint */
861  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
862  int* naddconss, /**< pointer to count number of added constraints, or NULL indicating we
863  * can not resolve multi-aggregations
864  */
865  int* ndelconss /**< pointer to count number of deleted constraints, or NULL indicating we
866  * can not resolve multi-aggregations
867  */
868  )
869 {
870  SCIP_CONSDATA* consdata;
871  SCIP_VAR* var;
872  int v;
873  SCIP_VAR** vars;
874  SCIP_Bool* negarray;
875  int nvars;
876 
877  assert(eventhdlr != NULL);
878  assert(redundant != NULL);
879 
880  consdata = SCIPconsGetData(cons);
881  assert(consdata != NULL);
882  assert(consdata->nvars == 0 || consdata->vars != NULL);
883 
884  *redundant = FALSE;
885  v = 0;
886 
887  /* all multi-aggregations should be resolved */
888  consdata->existmultaggr = FALSE;
889  consdata->presolved = TRUE;
890 
891  /* remove zeros and mark constraint redundant when found one variable fixed to one */
892  while( v < consdata->nvars )
893  {
894  var = consdata->vars[v];
895  assert(SCIPvarIsBinary(var));
896 
897  if( SCIPvarGetLbGlobal(var) > 0.5 )
898  {
899  assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), 1.0));
900  *redundant = TRUE;
901 
902  return SCIP_OKAY;
903  }
904  else if( SCIPvarGetUbGlobal(var) < 0.5 )
905  {
906  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), 0.0));
907  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
908  ++(*nchgcoefs);
909  }
910  else
911  ++v;
912  }
913 
914  if( consdata->nvars == 0 )
915  return SCIP_OKAY;
916 
917  nvars = consdata->nvars;
918 
919  /* allocate temporary memory */
920  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
921  SCIP_CALL( SCIPallocBufferArray(scip, &negarray, nvars) );
922 
923  /* get active or negation of active variables */
924  SCIP_CALL( SCIPgetBinvarRepresentatives(scip, nvars, consdata->vars, vars, negarray) );
925 
926  /* renew all variables, important that we do a backwards loop because deletion only affect rear items */
927  for( v = nvars - 1; v >= 0; --v )
928  {
929  var = vars[v];
930 
931  /* resolve multi-aggregation */
933  {
934  SCIP_VAR** consvars;
935  SCIP_Real* consvals;
936  SCIP_Real constant = 0.0;
937  SCIP_Bool easycase;
938  int nconsvars;
939  int requiredsize;
940  int v2;
941 
942  nconsvars = 1;
943  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 1) );
944  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 1) );
945  consvars[0] = var;
946  consvals[0] = 1.0;
947 
948  /* get active variables for new constraint */
949  SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, nconsvars, &constant, &requiredsize, TRUE) );
950  /* if space was not enough we need to resize the buffers */
951  if( requiredsize > nconsvars )
952  {
953  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, requiredsize) );
954  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, requiredsize) );
955 
956  SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
957  assert(requiredsize <= nconsvars);
958  }
959 
960  easycase = FALSE;
961 
962  if( SCIPisZero(scip, constant) )
963  {
964  /* add active representation */
965  for( v2 = nconsvars - 1; v2 >= 0; --v2 )
966  {
967  if( !SCIPvarIsBinary(consvars[v2]) )
968  {
969  break;
970 #if 0
971  SCIPerrorMessage("try to resolve a multi-aggregation with a non-binary variable <%s>\n", consvars[v2]);
972  return SCIP_ERROR;
973 #endif
974  }
975 
976  if( !SCIPisEQ(scip, consvals[v2], 1.0) )
977  break;
978  }
979 
980  if( v2 < 0 )
981  easycase = TRUE;
982  }
983 
984  /* we can easily add the coefficients and still have a logicor constraint */
985  if( easycase )
986  {
987  /* delete old (multi-aggregated) variable */
988  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
989  ++(*nchgcoefs);
990 
991  /* add active representation */
992  for( v2 = nconsvars - 1; v2 >= 0; --v2 )
993  {
994  assert(SCIPvarIsBinary(consvars[v2]));
995  assert(SCIPvarIsActive(consvars[v2]) || (SCIPvarGetStatus(consvars[v2]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(consvars[v2]))));
996 
997  SCIP_CALL( addCoef(scip, cons, consvars[v2]) );
998  ++(*nchgcoefs);
999  }
1000  }
1001  /* we need to degrade this logicor constraint to a linear constraint*/
1002  else if( (ndelconss != NULL && naddconss != NULL) || SCIPconsIsAdded(cons) )
1003  {
1004  char name[SCIP_MAXSTRLEN];
1005  SCIP_CONS* newcons;
1006  SCIP_Real lhs;
1007  SCIP_Real rhs;
1008  int size;
1009  int k;
1010 
1011  /* it might happen that there are more than one multi-aggregated variable, so we need to get the whole probvar sum over all variables */
1012 
1013  size = MAX(nconsvars, 1) + nvars - 1;
1014 
1015  /* memory needed is at least old number of variables - 1 + number of variables in first multi-aggregation */
1016  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, size) );
1017  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, size) );
1018 
1019  nconsvars = nvars;
1020 
1021  /* add constraint variables to new linear variables */
1022  for( k = nvars - 1; k >= 0; --k )
1023  {
1024  consvars[k] = vars[k];
1025  consvals[k] = 1.0;
1026  }
1027 
1028  constant = 0.0;
1029 
1030  /* get active variables for new constraint */
1031  SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, size, &constant, &requiredsize, TRUE) );
1032 
1033  /* if space was not enough(we found another multi-aggregation), we need to resize the buffers */
1034  if( requiredsize > nconsvars )
1035  {
1036  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, requiredsize) );
1037  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, requiredsize) );
1038 
1039  SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1040  assert(requiredsize <= nconsvars);
1041  }
1042 
1043  lhs = 1.0 - constant;
1044  rhs = SCIPinfinity(scip);
1045 
1046  /* create linear constraint */
1047  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPconsGetName(cons));
1048  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, nconsvars, consvars, consvals, lhs, rhs,
1049  SCIPconsIsInitial(cons),
1053  SCIP_CALL( SCIPaddCons(scip, newcons) );
1054 
1055  SCIPdebugMsg(scip, "added linear constraint: ");
1056  SCIPdebugPrintCons(scip, newcons, NULL);
1057  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1058 
1059  SCIPfreeBufferArray(scip, &consvals);
1060  SCIPfreeBufferArray(scip, &consvars);
1061 
1062  /* delete old constraint */
1063  SCIP_CALL( SCIPdelCons(scip, cons) );
1064  if( ndelconss != NULL && naddconss != NULL )
1065  {
1066  ++(*ndelconss);
1067  ++(*naddconss);
1068  }
1069 
1070  goto TERMINATE;
1071  }
1072  /* we need to degrade this logicor constraint to a linear constraint*/
1073  else
1074  {
1075  if( var != consdata->vars[v] )
1076  {
1077  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1078  SCIP_CALL( addCoef(scip, cons, var) );
1079  }
1080 
1081  SCIPwarningMessage(scip, "logicor constraint <%s> has a multi-aggregated variable, which was not resolved and therefore could lead to aborts\n", SCIPconsGetName(cons));
1082  }
1083 
1084  SCIPfreeBufferArray(scip, &consvals);
1085  SCIPfreeBufferArray(scip, &consvars);
1086  }
1087  else if( var != consdata->vars[v] )
1088  {
1089  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1090  SCIP_CALL( addCoef(scip, cons, var) );
1091  }
1092  }
1093 
1094  SCIPdebugMsg(scip, "after fixings: ");
1095  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
1096 
1097  TERMINATE:
1098  /* free temporary memory */
1099  SCIPfreeBufferArray(scip, &negarray);
1100  SCIPfreeBufferArray(scip, &vars);
1101 
1102  consdata->presolved = TRUE;
1103 
1104  return SCIP_OKAY;
1105 }
1106 
1107 /** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */
1108 static
1110  SCIP* scip, /**< SCIP data structure */
1111  SCIP_CONS* cons /**< logic or constraint that detected the conflict */
1112  )
1113 {
1114  SCIP_CONSDATA* consdata;
1115  int v;
1116 
1117  /* conflict analysis can only be applied in solving stage and if it is applicable */
1119  return SCIP_OKAY;
1120 
1121  consdata = SCIPconsGetData(cons);
1122  assert(consdata != NULL);
1123 
1124  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1126 
1127  for( v = 0; v < consdata->nvars; ++v )
1128  {
1129  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
1130  }
1131 
1132  /* analyze the conflict */
1133  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1134 
1135  return SCIP_OKAY;
1136 }
1137 
1138 /** disables or deletes the given constraint, depending on the current depth */
1139 static
1141  SCIP* scip, /**< SCIP data structure */
1142  SCIP_CONS* cons /**< bound disjunction constraint to be disabled */
1143  )
1144 {
1145  assert(SCIPconsGetValidDepth(cons) <= SCIPgetDepth(scip));
1146 
1147  /* in case the logic or constraint is satisfied in the depth where it is also valid, we can delete it */
1148  if( SCIPgetDepth(scip) == SCIPconsGetValidDepth(cons) )
1149  {
1150  SCIP_CALL( SCIPdelCons(scip, cons) );
1151  }
1152  else
1153  {
1154  SCIPdebugMsg(scip, "disabling constraint cons <%s> at depth %d\n", SCIPconsGetName(cons), SCIPgetDepth(scip));
1155  SCIP_CALL( SCIPdisableCons(scip, cons) );
1156  }
1157 
1158  return SCIP_OKAY;
1159 }
1160 
1161 /** find pairs of negated variables in constraint: constraint is redundant */
1162 /** find sets of equal variables in constraint: multiple entries of variable can be replaced by single entry */
1163 static
1165  SCIP* scip, /**< SCIP data structure */
1166  SCIP_CONS* cons, /**< logic or constraint */
1167  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1168  unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
1169  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
1170  SCIP_Bool* redundant, /**< returns whether a variable fixed to one exists in the constraint */
1171  int* nchgcoefs /**< pointer to count number of changed/deleted coefficients */
1172  )
1173 {
1174  SCIP_CONSDATA* consdata;
1175  SCIP_VAR** vars;
1176  int nvars;
1177  SCIP_Bool* negarray;
1178  SCIP_VAR* var;
1179  int v;
1180  int pos;
1181 #ifndef NDEBUG
1182  int nbinvars;
1183  int nintvars;
1184  int nimplvars;
1185 #endif
1186 
1187  assert(scip != NULL);
1188  assert(cons != NULL);
1189  assert(eventhdlr != NULL);
1190  assert(*entries != NULL);
1191  assert(nentries != NULL);
1192  assert(redundant != NULL);
1193  assert(nchgcoefs != NULL);
1194 
1195  consdata = SCIPconsGetData(cons);
1196  assert(consdata != NULL);
1197 
1198  nvars = consdata->nvars;
1199 
1200  *redundant = FALSE;
1201 
1202  if( consdata->merged )
1203  return SCIP_OKAY;
1204 
1205  if( consdata->nvars <= 1 )
1206  {
1207  consdata->merged = TRUE;
1208  return SCIP_OKAY;
1209  }
1210 
1211  assert(consdata->vars != NULL && nvars > 0);
1212 
1213 #ifndef NDEBUG
1214  nbinvars = SCIPgetNBinVars(scip);
1215  nintvars = SCIPgetNIntVars(scip);
1216  nimplvars = SCIPgetNImplVars(scip);
1217  assert(*nentries >= nbinvars + nintvars + nimplvars);
1218 
1219  /* all variables should be active or negative active variables, otherwise something went wrong with applyFixings()
1220  * called before mergeMultiples()
1221  */
1222  assert(consdata->presolved);
1223 #endif
1224 
1225  /* allocate temporary memory */
1226  SCIP_CALL( SCIPallocBufferArray(scip, &negarray, nvars) );
1227 
1228  vars = consdata->vars;
1229 
1230  /* initialize entries array */
1231  for( v = nvars - 1; v >= 0; --v )
1232  {
1233  /* all variables should be active or negative active variables, otherwise something went wrong with applyFixings()
1234  * called before mergeMultiples()
1235  */
1236  assert(SCIPvarIsActive(vars[v]) ||
1238  negarray[v] = SCIPvarIsNegated(vars[v]);
1239  var = negarray[v] ? SCIPvarGetNegationVar(vars[v]) : vars[v];
1240  assert(SCIPvarIsActive(var));
1241 
1242  pos = SCIPvarGetProbindex(var);
1243 
1244  /* check variable type, either pure binary or an integer/implicit integer variable with 0/1 bounds */
1245  assert((pos < nbinvars && SCIPvarGetType(var) == SCIP_VARTYPE_BINARY)
1246  || (SCIPvarIsBinary(var) &&
1247  ((pos >= nbinvars && pos < nbinvars + nintvars && SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER) ||
1248  (pos >= nbinvars + nintvars && pos < nbinvars + nintvars + nimplvars &&
1250 
1251  /* var is not active yet */
1252  (*entries)[pos] = 0;
1253  }
1254 
1255  /* check all vars for multiple entries, do necessary backwards loop because deletion only affect rear items */
1256  for( v = nvars - 1; v >= 0; --v )
1257  {
1258  var = negarray[v] ? SCIPvarGetNegationVar(vars[v]) : vars[v];
1259  assert(SCIPvarIsActive(var));
1260 
1261  pos = SCIPvarGetProbindex(var);
1262 
1263  /* if var occurs first time in constraint init entries array */
1264  if( (*entries)[pos] == 0 )
1265  (*entries)[pos] = negarray[v] ? 2 : 1;
1266  /* if var occurs second time in constraint, first time it was not negated */
1267  else if( (*entries)[pos] == 1 )
1268  {
1269  if( negarray[v] )
1270  {
1271  SCIPdebugMsg(scip, "logicor constraint <%s> redundant: variable <%s> and its negation are present\n",
1272  SCIPconsGetName(cons), SCIPvarGetName(var));
1273 
1274  *redundant = TRUE;
1275  goto TERMINATE;
1276  }
1277  else
1278  {
1279  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1280  ++(*nchgcoefs);
1281  }
1282  }
1283  /* if var occurs second time in constraint, first time it was negated */
1284  else
1285  {
1286  if( !negarray[v] )
1287  {
1288  SCIPdebugMsg(scip, "logicor constraint <%s> redundant: variable <%s> and its negation are present\n",
1289  SCIPconsGetName(cons), SCIPvarGetName(var));
1290 
1291  *redundant = TRUE;
1292  goto TERMINATE;
1293  }
1294  else
1295  {
1296  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1297  ++(*nchgcoefs);
1298  }
1299  }
1300  }
1301 
1302  TERMINATE:
1303  /* free temporary memory */
1304  SCIPfreeBufferArray(scip, &negarray);
1305 
1306  consdata->merged = TRUE;
1307 
1308  return SCIP_OKAY;
1309 }
1310 
1311 /** checks constraint for violation only looking at the watched variables, applies fixings if possible */
1312 static
1314  SCIP* scip, /**< SCIP data structure */
1315  SCIP_CONS* cons, /**< logic or constraint to be processed */
1316  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1317  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1318  SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
1319  SCIP_Bool* addcut, /**< pointer to store whether this constraint must be added as a cut */
1320  SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
1321  )
1322 {
1323  SCIP_CONSDATA* consdata;
1324  SCIP_VAR** vars;
1325  SCIP_Longint nbranchings1;
1326  SCIP_Longint nbranchings2;
1327  int nvars;
1328  int watchedvar1;
1329  int watchedvar2;
1330 
1331  assert(cons != NULL);
1332  assert(SCIPconsGetHdlr(cons) != NULL);
1333  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1334  assert(cutoff != NULL);
1335  assert(reduceddom != NULL);
1336  assert(addcut != NULL);
1337  assert(mustcheck != NULL);
1338 
1339  consdata = SCIPconsGetData(cons);
1340  assert(consdata != NULL);
1341  assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
1342 
1343  *addcut = FALSE;
1344  *mustcheck = FALSE;
1345 
1346  SCIPdebugMsg(scip, "processing watched variables of constraint <%s>\n", SCIPconsGetName(cons));
1347 
1348  vars = consdata->vars;
1349  nvars = consdata->nvars;
1350  assert(nvars == 0 || vars != NULL);
1351 
1352  /* check watched variables if they are fixed to one */
1353  if( consdata->watchedvar1 >= 0 && SCIPvarGetLbLocal(vars[consdata->watchedvar1]) > 0.5 )
1354  {
1355  /* the variable is fixed to one, making the constraint redundant -> disable the constraint */
1356  SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar1 fixed to 1.0)\n", SCIPconsGetName(cons));
1357  SCIP_CALL( disableCons(scip, cons) );
1358  return SCIP_OKAY;
1359  }
1360  if( consdata->watchedvar2 >= 0 && SCIPvarGetLbLocal(vars[consdata->watchedvar2]) > 0.5 )
1361  {
1362  /* the variable is fixed to one, making the constraint redundant -> disable the constraint */
1363  SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar2 fixed to 1.0)\n", SCIPconsGetName(cons));
1364  SCIP_CALL( disableCons(scip, cons) );
1365  return SCIP_OKAY;
1366  }
1367 
1368  /* check if watched variables are still unfixed */
1369  watchedvar1 = -1;
1370  watchedvar2 = -1;
1371  nbranchings1 = SCIP_LONGINT_MAX;
1372  nbranchings2 = SCIP_LONGINT_MAX;
1373  if( consdata->watchedvar1 >= 0 && SCIPvarGetUbLocal(vars[consdata->watchedvar1]) > 0.5 )
1374  {
1375  watchedvar1 = consdata->watchedvar1;
1376  nbranchings1 = -1; /* prefer keeping the watched variable */
1377  }
1378  if( consdata->watchedvar2 >= 0 && SCIPvarGetUbLocal(vars[consdata->watchedvar2]) > 0.5 )
1379  {
1380  if( watchedvar1 == -1 )
1381  {
1382  watchedvar1 = consdata->watchedvar2;
1383  nbranchings1 = -1; /* prefer keeping the watched variable */
1384  }
1385  else
1386  {
1387  watchedvar2 = consdata->watchedvar2;
1388  nbranchings2 = -1; /* prefer keeping the watched variable */
1389  }
1390  }
1391  assert(watchedvar1 >= 0 || watchedvar2 == -1);
1392  assert(nbranchings1 <= nbranchings2);
1393 
1394  /* search for new watched variables */
1395  if( watchedvar2 == -1 )
1396  {
1397  int v;
1398 
1399  for( v = 0; v < nvars; ++v )
1400  {
1401  SCIP_Longint nbranchings;
1402 
1403  /* don't process the watched variables again */
1404  if( v == consdata->watchedvar1 || v == consdata->watchedvar2 )
1405  continue;
1406 
1407  /* check, if the variable is fixed */
1408  if( SCIPvarGetUbLocal(vars[v]) < 0.5 )
1409  continue;
1410 
1411  /* check, if the literal is satisfied */
1412  if( SCIPvarGetLbLocal(vars[v]) > 0.5 )
1413  {
1414  assert(v != consdata->watchedvar1);
1415  assert(v != consdata->watchedvar2);
1416 
1417  /* the variable is fixed to one, making the constraint redundant;
1418  * make sure, the feasible variable is watched and disable the constraint
1419  */
1420  SCIPdebugMsg(scip, " -> disabling constraint <%s> (variable <%s> fixed to 1.0)\n",
1421  SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
1422  if( consdata->watchedvar1 != -1 )
1423  {
1424  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, v) );
1425  }
1426  else
1427  {
1428  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, v, consdata->watchedvar2) );
1429  }
1430  SCIP_CALL( disableCons(scip, cons) );
1431  return SCIP_OKAY;
1432  }
1433 
1434  /* the variable is unfixed and can be used as watched variable */
1436  assert(nbranchings >= 0);
1437  if( nbranchings < nbranchings2 )
1438  {
1439  if( nbranchings < nbranchings1 )
1440  {
1441  watchedvar2 = watchedvar1;
1442  nbranchings2 = nbranchings1;
1443  watchedvar1 = v;
1444  nbranchings1 = nbranchings;
1445  }
1446  else
1447  {
1448  watchedvar2 = v;
1449  nbranchings2 = nbranchings;
1450  }
1451  }
1452  }
1453  }
1454  assert(nbranchings1 <= nbranchings2);
1455  assert(watchedvar1 >= 0 || watchedvar2 == -1);
1456 
1457  if( watchedvar1 == -1 )
1458  {
1459  /* there is no unfixed variable left -> the constraint is infeasible
1460  * - a modifiable constraint must be added as a cut and further pricing must be performed in the LP solving loop
1461  * - an unmodifiable constraint is infeasible and the node can be cut off
1462  */
1463  assert(watchedvar2 == -1);
1464 
1465  SCIPdebugMsg(scip, " -> constraint <%s> is infeasible\n", SCIPconsGetName(cons));
1466 
1467  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1468  if( SCIPconsIsModifiable(cons) )
1469  *addcut = TRUE;
1470  else
1471  {
1472  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1473  SCIP_CALL( analyzeConflict(scip, cons) );
1474 
1475  /* mark the node to be cut off */
1476  *cutoff = TRUE;
1477  }
1478  }
1479  else if( watchedvar2 == -1 )
1480  {
1481  /* there is only one unfixed variable:
1482  * - a modifiable constraint must be checked manually
1483  * - an unmodifiable constraint is feasible and can be disabled after the remaining variable is fixed to one
1484  */
1485  assert(0 <= watchedvar1 && watchedvar1 < nvars);
1486  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[watchedvar1]), 0.0));
1487  assert(SCIPisFeasEQ(scip, SCIPvarGetUbLocal(vars[watchedvar1]), 1.0));
1488  if( SCIPconsIsModifiable(cons) )
1489  *mustcheck = TRUE;
1490  else
1491  {
1492  SCIP_Bool infbdchg;
1493 
1494  /* fixed remaining variable to one and disable constraint; make sure, the fixed-to-one variable is watched */
1495  SCIPdebugMsg(scip, " -> single-literal constraint <%s> (fix <%s> to 1.0) at depth %d\n",
1496  SCIPconsGetName(cons), SCIPvarGetName(vars[watchedvar1]), SCIPgetDepth(scip));
1497  SCIP_CALL( SCIPinferBinvarCons(scip, vars[watchedvar1], TRUE, cons, 0, &infbdchg, NULL) );
1498  assert(!infbdchg);
1499  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1500  if( watchedvar1 != consdata->watchedvar1 ) /* keep one of the watched variables */
1501  {
1502  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, consdata->watchedvar1) );
1503  }
1504  SCIP_CALL( disableCons(scip, cons) );
1505  *reduceddom = TRUE;
1506  }
1507  }
1508  else
1509  {
1510  SCIPdebugMsg(scip, " -> new watched variables <%s> and <%s> of constraint <%s> are still unfixed\n",
1511  SCIPvarGetName(vars[watchedvar1]), SCIPvarGetName(vars[watchedvar2]), SCIPconsGetName(cons));
1512 
1513  /* switch to the new watched variables */
1514  SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, watchedvar2) );
1515 
1516  /* there are at least two unfixed variables -> the constraint must be checked manually */
1517  *mustcheck = TRUE;
1518 
1519  /* disable propagation of constraint until a watched variable gets fixed */
1520  SCIP_CALL( SCIPdisableConsPropagation(scip, cons) );
1521 
1522  /* increase aging counter */
1523  SCIP_CALL( SCIPaddConsAge(scip, cons, AGEINCREASE(consdata->nvars)) );
1524  }
1525 
1526  return SCIP_OKAY;
1527 }
1528 
1529 /** checks constraint for violation, returns TRUE iff constraint is feasible */
1530 static
1532  SCIP* scip, /**< SCIP data structure */
1533  SCIP_CONS* cons, /**< logic or constraint to be checked */
1534  SCIP_SOL* sol, /**< primal CIP solution */
1535  SCIP_Bool* violated /**< pointer to store whether the given solution violates the constraint */
1536  )
1537 {
1538  SCIP_CONSDATA* consdata;
1539  SCIP_VAR** vars;
1540  SCIP_Real solval;
1541  SCIP_Real sum;
1542  int nvars;
1543  int v;
1544 
1545  assert(violated != NULL);
1546 
1547  *violated = FALSE;
1548  consdata = SCIPconsGetData(cons);
1549  assert(consdata != NULL);
1550 
1551  vars = consdata->vars;
1552  nvars = consdata->nvars;
1553 
1554  /* calculate the constraint's activity */
1555  sum = 0.0;
1556  for( v = 0; v < nvars && sum < 1.0; ++v )
1557  {
1558  assert(SCIPvarIsBinary(vars[v]));
1559 
1560  solval = SCIPgetSolVal(scip, sol, vars[v]);
1561  assert(SCIPisFeasGE(scip, solval, 0.0) && SCIPisFeasLE(scip, solval, 1.0));
1562 
1563  sum += solval;
1564  }
1565 
1566  *violated = SCIPisFeasLT(scip, sum, 1.0);
1567 
1568  /* calculate constraint violation and update it in solution */
1569  if( sol != NULL ){
1570  SCIP_Real absviol = 1.0 - sum;
1571  SCIP_Real relviol = SCIPrelDiff(1.0, sum);
1572  SCIPupdateSolLPConsViolation(scip, sol, absviol, relviol);
1573  }
1574 
1575  return SCIP_OKAY;
1576 }
1577 
1578 /** creates an LP row in a logic or constraint data object */
1579 static
1581  SCIP* scip, /**< SCIP data structure */
1582  SCIP_CONS* cons /**< logic or constraint */
1583  )
1584 {
1585  SCIP_CONSDATA* consdata;
1586 
1587  consdata = SCIPconsGetData(cons);
1588  assert(consdata != NULL);
1589  assert(consdata->row == NULL);
1590 
1591  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, SCIPconsGetHdlr(cons), SCIPconsGetName(cons), 1.0, SCIPinfinity(scip),
1593 
1594  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row, consdata->nvars, consdata->vars, 1.0) );
1595 
1596  return SCIP_OKAY;
1597 }
1598 
1599 /** adds logic or constraint as cut to the LP */
1600 static
1602  SCIP* scip, /**< SCIP data structure */
1603  SCIP_CONS* cons, /**< logic or constraint */
1604  SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1605  )
1606 {
1607  SCIP_CONSDATA* consdata;
1608 
1609  assert( cutoff != NULL );
1610  *cutoff = FALSE;
1611 
1612  consdata = SCIPconsGetData(cons);
1613  assert(consdata != NULL);
1614 
1615  if( consdata->row == NULL )
1616  {
1617  /* convert logic or constraint data into LP row */
1618  SCIP_CALL( createRow(scip, cons) );
1619  }
1620  assert(consdata->row != NULL);
1621 
1622  /* insert LP row as cut */
1623  if( !SCIProwIsInLP(consdata->row) )
1624  {
1625  SCIPdebugMsg(scip, "adding constraint <%s> as cut to the LP\n", SCIPconsGetName(cons));
1626  SCIP_CALL( SCIPaddRow(scip, consdata->row, FALSE, cutoff) );
1627  }
1628 
1629  return SCIP_OKAY;
1630 }
1631 
1632 /** checks constraint for violation, and adds it as a cut if possible */
1633 static
1635  SCIP* scip, /**< SCIP data structure */
1636  SCIP_CONS* cons, /**< logic or constraint to be separated */
1637  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1638  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1639  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1640  SCIP_Bool* separated, /**< pointer to store TRUE, if a cut was found */
1641  SCIP_Bool* reduceddom /**< pointer to store TRUE, if a domain reduction was found */
1642  )
1643 {
1644  SCIP_Bool addcut;
1645  SCIP_Bool mustcheck;
1646 
1647  assert(cons != NULL);
1648  assert(SCIPconsGetHdlr(cons) != NULL);
1649  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1650  assert(cutoff != NULL);
1651  assert(separated != NULL);
1652  assert(reduceddom != NULL);
1653 
1654  *cutoff = FALSE;
1655  SCIPdebugMsg(scip, "separating constraint <%s>\n", SCIPconsGetName(cons));
1656 
1657  /* update and check the watched variables, if they were changed since last processing */
1658  if( sol == NULL && SCIPconsIsPropagationEnabled(cons) )
1659  {
1660  SCIP_CALL( processWatchedVars(scip, cons, eventhdlr, cutoff, reduceddom, &addcut, &mustcheck) );
1661  }
1662  else
1663  {
1664  addcut = FALSE;
1665  mustcheck = TRUE;
1666  }
1667 
1668  if( mustcheck )
1669  {
1670  SCIP_CONSDATA* consdata;
1671 
1672  assert(!addcut);
1673 
1674  consdata = SCIPconsGetData(cons);
1675  assert(consdata != NULL);
1676 
1677  /* variable's fixings didn't give us any information -> we have to check the constraint */
1678  if( sol == NULL && consdata->row != NULL )
1679  {
1680  /* skip constraints already in the LP */
1681  if( SCIProwIsInLP(consdata->row) )
1682  return SCIP_OKAY;
1683  else
1684  {
1685  SCIP_Real feasibility;
1686 
1687  assert(!SCIProwIsInLP(consdata->row));
1688  feasibility = SCIPgetRowLPFeasibility(scip, consdata->row);
1689  addcut = SCIPisFeasNegative(scip, feasibility);
1690  }
1691  }
1692  else
1693  {
1694  SCIP_CALL( checkCons(scip, cons, sol, &addcut) );
1695  }
1696  }
1697 
1698  if( addcut )
1699  {
1700  /* insert LP row as cut */
1701  SCIP_CALL( addCut(scip, cons, cutoff) );
1702  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1703  *separated = TRUE;
1704  }
1705 
1706  return SCIP_OKAY;
1707 }
1708 
1709 /** enforces the pseudo solution on the given constraint */
1710 static
1712  SCIP* scip, /**< SCIP data structure */
1713  SCIP_CONS* cons, /**< logic or constraint to be separated */
1714  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1715  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1716  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */
1717  SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
1718  SCIP_Bool* solvelp /**< pointer to store TRUE, if the LP has to be solved */
1719  )
1720 {
1721  SCIP_Bool addcut;
1722  SCIP_Bool mustcheck;
1723 
1724  assert(!SCIPhasCurrentNodeLP(scip));
1725  assert(cons != NULL);
1726  assert(SCIPconsGetHdlr(cons) != NULL);
1727  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1728  assert(cutoff != NULL);
1729  assert(infeasible != NULL);
1730  assert(reduceddom != NULL);
1731  assert(solvelp != NULL);
1732 
1733  /* update and check the watched variables, if they were changed since last processing */
1734  if( SCIPconsIsPropagationEnabled(cons) )
1735  {
1736  SCIP_CALL( processWatchedVars(scip, cons, eventhdlr, cutoff, reduceddom, &addcut, &mustcheck) );
1737  }
1738  else
1739  {
1740  addcut = FALSE;
1741  mustcheck = TRUE;
1742  }
1743 
1744  if( mustcheck )
1745  {
1746  SCIP_Bool violated;
1747 
1748  assert(!addcut);
1749 
1750  SCIP_CALL( checkCons(scip, cons, NULL, &violated) );
1751  if( violated )
1752  {
1753  /* constraint was infeasible -> reset age */
1754  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1755  *infeasible = TRUE;
1756  }
1757  }
1758  else if( addcut )
1759  {
1760  /* a cut must be added to the LP -> we have to solve the LP immediately */
1761  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1762  *solvelp = TRUE;
1763  }
1764 
1765  return SCIP_OKAY;
1766 }
1767 
1768 /** sorts logicor constraint's variables by non-decreasing variable index */
1769 static
1770 void consdataSort(
1771  SCIP_CONSDATA* consdata /**< linear constraint data */
1772  )
1773 {
1774  assert(consdata != NULL);
1775 
1776  if( !consdata->sorted )
1777  {
1778  if( consdata->nvars <= 1 )
1779  consdata->sorted = TRUE;
1780  else
1781  {
1782  SCIP_VAR* var1 = NULL;
1783  SCIP_VAR* var2 = NULL;
1784 
1785  /* remember watch variables */
1786  if( consdata->watchedvar1 != -1 )
1787  {
1788  var1 = consdata->vars[consdata->watchedvar1];
1789  assert(var1 != NULL);
1790  consdata->watchedvar1 = -1;
1791  if( consdata->watchedvar2 != -1 )
1792  {
1793  var2 = consdata->vars[consdata->watchedvar2];
1794  assert(var2 != NULL);
1795  consdata->watchedvar2 = -1;
1796  }
1797  }
1798  assert(consdata->watchedvar1 == -1);
1799  assert(consdata->watchedvar2 == -1);
1800  assert(var1 != NULL || var2 == NULL);
1801 
1802  /* sort variables after index */
1803  SCIPsortPtr((void**)consdata->vars, SCIPvarComp, consdata->nvars);
1804  consdata->sorted = TRUE;
1805 
1806  /* correct watched variables */
1807  if( var1 != NULL )
1808  {
1809  int pos;
1810 #ifndef NDEBUG
1811  SCIP_Bool found;
1812 
1813  found = SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var1, consdata->nvars, &pos);
1814  assert(found);
1815 #else
1816  SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var1, consdata->nvars, &pos);
1817 #endif
1818  assert(pos >= 0 && pos < consdata->nvars);
1819  consdata->watchedvar1 = pos;
1820 
1821  if( var2 != NULL )
1822  {
1823 #ifndef NDEBUG
1824  found = SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var2, consdata->nvars, &pos);
1825  assert(found);
1826 #else
1827  SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var2, consdata->nvars, &pos);
1828 #endif
1829  assert(pos >= 0 && pos < consdata->nvars);
1830  consdata->watchedvar2 = pos;
1831  }
1832  }
1833  }
1834  }
1835 
1836 #ifdef SCIP_DEBUG
1837  /* check sorting */
1838  {
1839  int v;
1840 
1841  for( v = consdata->nvars - 1; v > 0; --v )
1842  {
1843  assert(SCIPvarCompare(consdata->vars[v], consdata->vars[v - 1]) >= 0);
1844  }
1845  }
1846 #endif
1847 }
1848 
1849 /** gets the key of the given element */
1850 static
1851 SCIP_DECL_HASHGETKEY(hashGetKeyLogicorcons)
1852 { /*lint --e{715}*/
1853  /* the key is the element itself */
1854  return elem;
1855 }
1856 
1857 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
1858 static
1859 SCIP_DECL_HASHKEYEQ(hashKeyEqLogicorcons)
1860 {
1861  SCIP_CONSDATA* consdata1;
1862  SCIP_CONSDATA* consdata2;
1863  SCIP_Bool coefsequal;
1864  int i;
1865 #ifndef NDEBUG
1866  SCIP* scip;
1867 
1868  scip = (SCIP*)userptr;
1869  assert(scip != NULL);
1870 #endif
1871 
1872  consdata1 = SCIPconsGetData((SCIP_CONS*)key1);
1873  consdata2 = SCIPconsGetData((SCIP_CONS*)key2);
1874 
1875  /* checks trivial case */
1876  if( consdata1->nvars != consdata2->nvars )
1877  return FALSE;
1878 
1879  /* sorts the constraints */
1880  consdataSort(consdata1);
1881  consdataSort(consdata2);
1882  assert(consdata1->sorted);
1883  assert(consdata2->sorted);
1884 
1885  coefsequal = TRUE;
1886 
1887  for( i = 0; i < consdata1->nvars ; ++i )
1888  {
1889  /* tests if variables are equal */
1890  if( consdata1->vars[i] != consdata2->vars[i] )
1891  {
1892  assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
1893  SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
1894  coefsequal = FALSE;
1895  break;
1896  }
1897  assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
1898  }
1899 
1900  return coefsequal;
1901 }
1902 
1903 /** returns the hash value of the key */
1904 static
1905 SCIP_DECL_HASHKEYVAL(hashKeyValLogicorcons)
1906 { /*lint --e{715}*/
1907  SCIP_CONSDATA* consdata;
1908  int minidx;
1909  int mididx;
1910  int maxidx;
1911 
1912  consdata = SCIPconsGetData((SCIP_CONS*)key);
1913  assert(consdata != NULL);
1914  assert(consdata->sorted);
1915  assert(consdata->nvars > 0);
1916 
1917  minidx = SCIPvarGetIndex(consdata->vars[0]);
1918  mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
1919  maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
1920  assert(minidx >= 0 && minidx <= maxidx);
1921 
1922  return SCIPhashTwo(SCIPcombineTwoInt(consdata->nvars, minidx),
1923  SCIPcombineTwoInt(mididx, maxidx));
1924 }
1925 
1926 /** compares each constraint with all other constraints for a possible duplication and removes duplicates using a hash
1927  * table; also @see removeRedundantConssAndNonzeros()
1928  */
1929 static
1931  SCIP* scip, /**< SCIP data structure */
1932  BMS_BLKMEM* blkmem, /**< block memory */
1933  SCIP_CONS** conss, /**< constraint set */
1934  int nconss, /**< number of constraints in constraint set */
1935  int* firstchange, /**< pointer to store first changed constraint */
1936  int* ndelconss /**< pointer to count number of deleted constraints */
1937  )
1938 {
1939  SCIP_HASHTABLE* hashtable;
1940  int hashtablesize;
1941  int c;
1942 
1943  assert(conss != NULL);
1944  assert(ndelconss != NULL);
1945 
1946  /* create a hash table for the constraint set */
1947  hashtablesize = nconss;
1948  hashtablesize = MAX(hashtablesize, HASHSIZE_LOGICORCONS);
1949  SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
1950  hashGetKeyLogicorcons, hashKeyEqLogicorcons, hashKeyValLogicorcons, (void*) scip) );
1951 
1952  /* check all constraints in the given set for redundancy */
1953  for( c = 0; c < nconss; ++c )
1954  {
1955  SCIP_CONS* cons0;
1956  SCIP_CONS* cons1;
1957  SCIP_CONSDATA* consdata0;
1958 
1959  cons0 = conss[c];
1960 
1961  if( !SCIPconsIsActive(cons0) || SCIPconsIsModifiable(cons0) )
1962  continue;
1963 
1964  consdata0 = SCIPconsGetData(cons0);
1965  /* sort the constraint */
1966  consdataSort(consdata0);
1967  assert(consdata0->sorted);
1968 
1969  /* get constraint from current hash table with same variables as cons0 */
1970  cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
1971 
1972  if( cons1 != NULL )
1973  {
1974 #ifndef NDEBUG
1975  SCIP_CONSDATA* consdata1;
1976 #endif
1977 
1978  assert(SCIPconsIsActive(cons1));
1979  assert(!SCIPconsIsModifiable(cons1));
1980 
1981 #ifndef NDEBUG
1982  consdata1 = SCIPconsGetData(cons1);
1983 #endif
1984  assert(consdata1 != NULL);
1985  assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
1986 
1987  assert(consdata0->sorted && consdata1->sorted);
1988  assert(consdata0->vars[0] == consdata1->vars[0]);
1989 
1990  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
1991  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
1992 
1993  /* delete consdel */
1994  SCIP_CALL( SCIPdelCons(scip, cons0) );
1995  (*ndelconss)++;
1996 
1997  /* update the first changed constraint to begin the next aggregation round with */
1998  if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
1999  *firstchange = SCIPconsGetPos(cons1);
2000 
2001  assert(SCIPconsIsActive(cons1));
2002  }
2003  else
2004  {
2005  /* no such constraint in current hash table: insert cons0 into hash table */
2006  SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
2007  }
2008  }
2009 
2010  /* free hash table */
2011  SCIPhashtableFree(&hashtable);
2012 
2013  return SCIP_OKAY;
2014 }
2015 
2016 /** removes the redundant second constraint and updates the flags of the first one */
2017 static
2019  SCIP* scip, /**< SCIP data structure */
2020  SCIP_CONS* cons0, /**< constraint that should stay */
2021  SCIP_CONS* cons1, /**< constraint that should be deleted */
2022  int* ndelconss /**< pointer to count number of deleted constraints */
2023  )
2024 {
2025  assert(ndelconss != NULL);
2026 
2027  SCIPdebugMsg(scip, " -> removing logicor constraint <%s> which is redundant to <%s>\n",
2028  SCIPconsGetName(cons1), SCIPconsGetName(cons0));
2029  SCIPdebugPrintCons(scip, cons0, NULL);
2030  SCIPdebugPrintCons(scip, cons1, NULL);
2031 
2032  /* update flags of cons0 */
2033  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
2034 
2035  /* delete cons1 */
2036  SCIP_CALL( SCIPdelCons(scip, cons1) );
2037  (*ndelconss)++;
2038 
2039  return SCIP_OKAY;
2040 }
2041 
2042 
2043 /** compute and return a signature for given variables */
2044 static
2045 unsigned int calcSignature(
2046  SCIP_VAR** vars, /**< variables to calculate the signature for */
2047  int nvars /**< number of variables to calculate the signature for */
2048  )
2049 {
2050  unsigned int signature = 0;
2051  int v;
2052 
2053  assert(vars != NULL);
2054  assert(nvars >= 1);
2055 
2056  for( v = nvars - 1; v >= 0; --v )
2057  {
2058  signature |= ((unsigned int)1 << ((unsigned int)SCIPvarGetIndex(vars[v]) % (sizeof(unsigned int) * 8)));
2059  }
2060 
2061  return signature;
2062 }
2063 
2064 /** compute the constraint signature which is used to detect constraints, that contain potentially the same set of
2065  * variables
2066  */
2067 static
2069  SCIP_CONSDATA* consdata /**< logicor constraint data */
2070  )
2071 {
2072  if( consdata->validsignature )
2073  return;
2074 
2075  consdata->signature = calcSignature(consdata->vars, consdata->nvars);
2076  consdata->validsignature = TRUE;
2077 }
2078 
2079 /** remove a constraint from the column representation */
2080 static
2082  SCIP_CONS* cons, /**< logicor constraint */
2083  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2084  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2085  int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2086  int occurlistlength /**< number of columns in the occurlist */
2087  )
2088 {
2089  SCIP_VAR** vars;
2090  SCIP_VAR* var;
2091  SCIP_CONSDATA* consdata;
2092  int nvars;
2093  int pos;
2094  int v;
2095  int l;
2096 
2097  assert(cons != NULL);
2098  assert(SCIPconsIsActive(cons));
2099  assert(varstopos != NULL);
2100  assert(occurlist != NULL);
2101  assert(noccurlistentries != NULL);
2102 
2103  consdata = SCIPconsGetData(cons);
2104  assert(consdata != NULL);
2105 
2106  nvars = consdata->nvars;
2107  assert(nvars >= 1);
2108  vars = consdata->vars;
2109  assert(vars != NULL);
2110 
2111  /* remove constraint from list */
2112  for( v = nvars - 1; v >= 0; --v )
2113  {
2114  var = vars[v];
2115 
2116  assert(SCIPhashmapExists(varstopos, (void*) var));
2117 
2118  pos = (int) (size_t) SCIPhashmapGetImage(varstopos, (void*)var);
2119  assert(0 < pos && pos <= occurlistlength);
2120 
2121  --pos;
2122 
2123  /* remove for each variable one corresponding entry */
2124  for( l = noccurlistentries[pos] - 1; l >= 0; --l )
2125  {
2126  if( occurlist[pos][l] == cons )
2127  {
2128  --noccurlistentries[pos];
2129  assert(noccurlistentries[pos] >= 0);
2130 
2131  occurlist[pos][l] = occurlist[pos][noccurlistentries[pos]];
2132  break;
2133  }
2134  }
2135  assert(l >= 0);
2136  }
2137 }
2138 
2139 /** determine shortest constraint list in column representation */
2140 static
2142  SCIP_VAR** vars, /**< variables to find the shortestlist for */
2143  int nvars, /**< number of variables */
2144  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2145  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2146  int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2147  int occurlistlength, /**< number of columns in the occurlist */
2148  int* nentries, /**< pointer to store the number of entries in the shortest list */
2149  SCIP_CONS*** shortestlist /**< pointer to store smallest array with constraints */
2150  )
2151 {
2152  SCIP_VAR* var;
2153  int pos;
2154  int v;
2155 
2156  assert(vars != 0);
2157  assert(nvars >= 1);
2158  assert(varstopos != NULL);
2159  assert(occurlist != NULL);
2160  assert(noccurlistentries != NULL);
2161  assert(nentries != NULL);
2162  assert(shortestlist != NULL);
2163 
2164  *nentries = INT_MAX;
2165  *shortestlist = NULL;
2166 
2167  /* find the shortest list */
2168  for( v = nvars - 1; v >= 0; --v )
2169  {
2170  var = vars[v];
2171  assert(var != NULL);
2172 
2173  /* it might be that a variable is not yet put into the occurlist, then this constraint cannot cover another */
2174  if( !SCIPhashmapExists(varstopos, (void*) var) )
2175  {
2176  *nentries = 0;
2177  return;
2178  }
2179 
2180  pos = (int) (size_t) SCIPhashmapGetImage(varstopos, (void*)var);
2181  assert(0 < pos && pos <= occurlistlength);
2182 
2183  --pos;
2184 
2185  /* remember the shortest list */
2186  if( noccurlistentries[pos] < *nentries )
2187  {
2188  *nentries = noccurlistentries[pos];
2189  *shortestlist = occurlist[pos];
2190  }
2191  }
2192 }
2193 
2194 /** run a pairwise comparison for detecting subset-constraints of other constraint while using a signature */
2195 static
2197  SCIP* scip, /**< SCIP data structure */
2198  SCIP_CONS* cons, /**< logicor constraint to check if it covers another */
2199  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2200  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2201  int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2202  int occurlistlength, /**< number of columns in the occurlist */
2203  int* ndelconss /**< pointer to store the number of deleted constraints */
2204  )
2205 {
2206  SCIP_CONS** shortestlist;
2207  SCIP_VAR** vars;
2208  SCIP_CONS* cons1;
2209  SCIP_VAR* var;
2210  SCIP_CONSDATA* consdata;
2211  int nentries;
2212  int c;
2213  int v;
2214 
2215  assert(scip != NULL);
2216  assert(cons != NULL);
2217  assert(SCIPconsIsActive(cons));
2218  assert(!SCIPconsIsModifiable(cons));
2219  assert(varstopos != NULL);
2220  assert(occurlist != NULL);
2221  assert(noccurlistentries != NULL);
2222  assert(ndelconss != NULL);
2223 
2224  consdata = SCIPconsGetData(cons);
2225  assert(consdata != NULL);
2226  assert(consdata->nvars > 1);
2227  assert(consdata->validsignature);
2228  assert(consdata->sorted);
2229 
2230  vars = consdata->vars;
2231  assert(vars != NULL);
2232 
2233  /* determine shortest column */
2234  findShortestOccurlist(vars, consdata->nvars, varstopos, occurlist, noccurlistentries, occurlistlength, &nentries, &shortestlist);
2235 
2236  /* one variable which does not appear in the column representation anymore */
2237  if( nentries == 0 )
2238  return SCIP_OKAY;
2239 
2240  assert(shortestlist != NULL);
2241  assert(0 < nentries);
2242 
2243  /* check all constraints in the shortest list for coverage */
2244  for( c = nentries - 1; c >= 0; --c )
2245  {
2246  cons1 = shortestlist[c];
2247  assert(cons1 != NULL);
2248  assert(!SCIPconsIsModifiable(cons1));
2249  assert(SCIPconsIsActive(cons1));
2250 
2251  if( cons != cons1 )
2252  {
2253  SCIP_CONSDATA* consdata1 = SCIPconsGetData(cons1);
2254  assert(consdata1 != NULL);
2255  assert(consdata1->nvars >= consdata->nvars);
2256 
2257  /* constraints with the same length cannot be covered and same constraints are removed in
2258  * detectRedundantConstraints()
2259  */
2260  if( consdata1->nvars == consdata->nvars )
2261  continue;
2262 
2263  assert(consdata->validsignature);
2264  assert(consdata->sorted);
2265  assert(consdata1->validsignature);
2266  assert(consdata1->sorted);
2267 
2268  if( (consdata->signature & (~consdata1->signature)) == 0 )
2269  {
2270  SCIP_VAR* var1;
2271  int v1;
2272 
2273  v = 0;
2274  v1 = 0;
2275 
2276  while( v < consdata->nvars && v1 < consdata1->nvars )
2277  {
2278  int comp;
2279 
2280  var = vars[v];
2281  var1 = consdata1->vars[v1];
2282 
2283  comp = SCIPvarCompare(var, var1);
2284 
2285  if( comp == 0 )
2286  {
2287  ++v;
2288  ++v1;
2289  }
2290  else if( comp > 0 )
2291  ++v1;
2292  else
2293  break;
2294  }
2295 
2296  /* cons1 is covered by cons */
2297  if( v == consdata->nvars )
2298  {
2299  /* remove cons1 from columns representation */
2300  removeConsFromOccurList(cons1, varstopos, occurlist, noccurlistentries, occurlistlength);
2301 
2302  /* delete redundant constraint and update constraint flags if necessary */
2303  SCIP_CALL( removeRedundantCons(scip, cons, cons1, ndelconss) );
2304  }
2305  }
2306  }
2307  }
2308 
2309  return SCIP_OKAY;
2310 }
2311 
2312 /** compararer for sorting constraints after their number of variables */
2313 static
2314 SCIP_DECL_SORTPTRCOMP(conssLogicorComp)
2315 {
2316  SCIP_CONSDATA* consdata1;
2317  SCIP_CONSDATA* consdata2;
2318 
2319  assert(elem1 != NULL);
2320  assert(elem2 != NULL);
2321 
2322  consdata1 = SCIPconsGetData((SCIP_CONS*) elem1);
2323  consdata2 = SCIPconsGetData((SCIP_CONS*) elem2);
2324 
2325  assert(consdata1 != NULL);
2326  assert(consdata2 != NULL);
2327 
2328  return consdata1->nvars - consdata2->nvars;
2329 }
2330 
2331 /** add a constraint to the column representation */
2332 static
2334  SCIP* scip, /**< SCIP data structure */
2335  SCIP_CONS* cons, /**< logicor constraint */
2336  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2337  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2338  int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2339  int* occurlistsizes, /**< array of sizes for each variable in the occurlist */
2340  int* occurlistlength, /**< number of columns in the occurlist */
2341  int occurlistsize /**< size of occurlist */
2342  )
2343 {
2344  SCIP_VAR** vars;
2345  SCIP_VAR* var;
2346  SCIP_CONSDATA* consdata;
2347  int pos;
2348  int v;
2349 
2350  assert(scip != NULL);
2351  assert(cons != NULL);
2352  assert(SCIPconsIsActive(cons));
2353  assert(varstopos != NULL);
2354  assert(occurlist != NULL);
2355  assert(noccurlistentries != NULL);
2356  assert(occurlistsizes != NULL);
2357  assert(occurlistlength != NULL);
2358  assert(*occurlistlength <= occurlistsize);
2359 
2360  consdata = SCIPconsGetData(cons);
2361  assert(consdata != NULL);
2362  assert(consdata->nvars > 1);
2363 
2364  vars = consdata->vars;
2365  assert(vars != NULL);
2366 
2367  for( v = consdata->nvars - 1; v >= 0; --v )
2368  {
2369  var = vars[v];
2370  assert(var != NULL);
2372 
2373  /* check if the variable is not yet put into the occurlist */
2374  if( !SCIPhashmapExists(varstopos, (void*) var) )
2375  {
2376  pos = *occurlistlength;
2377  assert(pos <= occurlistsize);
2378 
2379  /* occurlist values need to be clear */
2380  assert(occurlist[pos] == NULL);
2381  assert(noccurlistentries[pos] == 0);
2382  assert(occurlistsizes[pos] == 0);
2383 
2384  /* allocate memory */
2386  occurlistsizes[pos] = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) + 1;
2387  SCIP_CALL( SCIPallocBufferArray(scip, &(occurlist[pos]), occurlistsizes[pos]) ); /*lint !e866*/
2388 
2389  /* put constraint in list of current variable */
2390  occurlist[pos][noccurlistentries[pos]] = cons;
2391  ++(noccurlistentries[pos]);
2392 
2393  /* add new variable to map */
2394  SCIP_CALL( SCIPhashmapInsert(varstopos, var, (void*) (size_t) (pos + 1)) );
2395 
2396  ++(*occurlistlength);
2397  }
2398  else
2399  {
2400  pos = (int) (size_t) SCIPhashmapGetImage(varstopos, (void*)var);
2401  assert(0 < pos && pos <= *occurlistlength);
2402 
2403  --pos;
2404 
2405  assert(occurlist[pos] != NULL);
2406  assert(occurlistsizes[pos] > 0);
2407 
2408  /* do we need to resize the array */
2409  if( noccurlistentries[pos] == occurlistsizes[pos] )
2410  {
2411  occurlistsizes[pos] = SCIPcalcMemGrowSize(scip, occurlistsizes[pos] + 1);
2412  assert(occurlistsizes[pos] > noccurlistentries[pos] && occurlistsizes[pos] < INT_MAX);
2413 
2414  /* resize occurlist for current variable */
2415  SCIP_CALL( SCIPreallocBufferArray(scip, &(occurlist[pos]), occurlistsizes[pos]) ); /*lint !e866*/
2416  }
2417  assert(noccurlistentries[pos] < occurlistsizes[pos]);
2418 
2419  /* put constraint in list of current variable */
2420  occurlist[pos][noccurlistentries[pos]] = cons;
2421  ++(noccurlistentries[pos]);
2422  }
2423  }
2424 
2425  return SCIP_OKAY;
2426 }
2427 
2428 /** run a pairwise comparison for the given variables against all constraits to detect redundant non-zeros in these
2429  * constraints
2430  */
2431 static
2433  SCIP* scip, /**< SCIP data structure */
2434  SCIP_CONS* cons, /**< logicor constraint to check if it covers another */
2435  SCIP_VAR* artvar, /**< artificial negated variable of constraint */
2436  int artpos, /**< position to replace constraint variable with artvar */
2437  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2438  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2439  int* noccurlistentries, /**< number of constraints for each variable in the occurlist */
2440  int occurlistlength, /**< number of columns in the occurlist */
2441  SCIP_EVENTHDLR* eventhdlr, /**< event handler */
2442  int* nchgcoefs, /**< pointer to store the number of deleted non-zeros */
2443  SCIP_Bool* deleted /**< pointer to store if cons will be deleted */
2444  )
2445 {
2446  SCIP_CONS** shortestlist;
2447  SCIP_VAR** vars;
2448  SCIP_CONS* cons1;
2449  SCIP_VAR* oldvar;
2450  SCIP_VAR* var;
2451  SCIP_CONSDATA* consdata;
2452  unsigned int signature;
2453  int nentries;
2454  int nvars;
2455  int c;
2456  int v;
2457  int pos;
2458 
2459  assert(scip != NULL);
2460  assert(cons != NULL);
2461  assert(artvar != NULL);
2462  assert(SCIPconsIsActive(cons));
2463  assert(!SCIPconsIsModifiable(cons));
2464  assert(varstopos != NULL);
2465  assert(SCIPhashmapExists(varstopos, (void*) artvar));
2466  assert(occurlist != NULL);
2467  assert(noccurlistentries != NULL);
2468  assert(nchgcoefs != NULL);
2469  assert(deleted != NULL);
2470 
2471  consdata = SCIPconsGetData(cons);
2472  assert(consdata != NULL);
2473  assert(consdata->sorted);
2474 
2475  nvars = consdata->nvars;
2476  assert(nvars > 1);
2477  assert(0 <= artpos && artpos < nvars);
2478 
2479  vars = consdata->vars;
2480  assert(vars != NULL);
2481 
2482  *deleted = FALSE;
2483 
2484  /* temporary exchange the variable for finding the shortest list */
2485  oldvar = vars[artpos];
2486  assert(oldvar == SCIPvarGetNegatedVar(artvar));
2487  vars[artpos] = artvar;
2488 
2489  /* determine shortest column */
2490  findShortestOccurlist(vars, nvars, varstopos, occurlist, noccurlistentries, occurlistlength, &nentries, &shortestlist);
2491 
2492  /* correct exchanged variable with constraint variables */
2493  vars[artpos] = oldvar;
2494 
2495  /* one variable which does not appear in the column representation anymore */
2496  if( nentries == 0 )
2497  return SCIP_OKAY;
2498 
2499  assert(shortestlist != NULL);
2500  assert(0 < nentries);
2501 
2502  /* temporary exchange the variable for calculating a valid signature */
2503  oldvar = vars[artpos];
2504  vars[artpos] = artvar;
2505  signature = calcSignature(vars, nvars);
2506 
2507  /* correct exchanged variable with constraint variables */
2508  vars[artpos] = oldvar;
2509 
2510  /* check all constraints in the shortest list for coverage */
2511  for( c = nentries - 1; c >= 0; --c )
2512  {
2513  cons1 = shortestlist[c];
2514  assert(cons1 != NULL);
2515  assert(!SCIPconsIsModifiable(cons1));
2516 
2517  if( !SCIPconsIsActive(cons1) )
2518  continue;
2519 
2520  if( cons != cons1 )
2521  {
2522  SCIP_CONSDATA* consdata1 = SCIPconsGetData(cons1);
2523  assert(consdata1 != NULL);
2524 
2525  /* constraints with the less variables cannot be covered */
2526  if( consdata1->nvars < nvars )
2527  continue;
2528 
2529  pos = -1;
2530 
2531  assert(consdata->sorted);
2532  assert(consdata->merged);
2533  assert(consdata1->validsignature);
2534  assert(consdata1->sorted);
2535  assert(consdata1->merged);
2536 
2537  if( (signature & (~consdata1->signature)) == 0 )
2538  {
2539  SCIP_VAR* var1;
2540  int v1;
2541 
2542  v = 0;
2543  v1 = 0;
2544 
2545  while( v < nvars && v1 < consdata1->nvars )
2546  {
2547  int comp;
2548 
2549  /* skip position of artificial variable */
2550  if( artpos == v )
2551  {
2552  ++v;
2553  continue;
2554  }
2555 
2556  var1 = consdata1->vars[v1];
2557 
2558  /* did we find the artificial variable in cons1 */
2559  if( artvar == var1 )
2560  {
2561  /* remember of possible redundant variable */
2562  assert(pos == -1);
2563  pos = v1;
2564 
2565  ++v1;
2566  continue;
2567  }
2568 
2569  var = vars[v];
2570  comp = SCIPvarCompare(var, var1);
2571 
2572  /* check if the cons1 can still be covered */
2573  if( comp == 0 )
2574  {
2575  ++v;
2576  ++v1;
2577  }
2578  else if( comp > 0 )
2579  ++v1;
2580  else
2581  break;
2582  }
2583 
2584  /* cons1 is might be covered by the changed constraints cons, meaning that we might remove the artvar from
2585  * cons1
2586  */
2587  if( v == nvars )
2588  {
2589  int l;
2590 
2591  /* if the artificial variable was not yet found, search over the rear variables in constraint cons1 */
2592  if( pos == -1 )
2593  {
2594  while( v1 < consdata1->nvars )
2595  {
2596  if( artvar == consdata1->vars[v1] )
2597  {
2598  /* remember of possible redundant variable */
2599  pos = v1;
2600  break;
2601  }
2602  ++v1;
2603  }
2604  }
2605 
2606  if( pos >= 0 )
2607  {
2608  int conspos;
2609 
2610  assert(pos < consdata1->nvars);
2611  assert(artvar == consdata1->vars[pos]);
2612 
2613  /* remove redudant entry in cons1 */
2614  SCIPdebugMsg(scip, "variable %s in logicor constraint <%s> is redundant and will be removed (used constraint %s)\n",
2615  SCIPvarGetName(artvar), SCIPconsGetName(cons1), SCIPconsGetName(cons));
2616  SCIPdebugPrintCons(scip, cons1, NULL);
2617  conspos = pos;
2618 
2619  if( consdata1->nvars > nvars )
2620  {
2621  pos = (int) (size_t) SCIPhashmapGetImage(varstopos, (void*)artvar);
2622  assert(0 < pos && pos <= occurlistlength);
2623 
2624  --pos;
2625 
2626  /* remove corresponding entry in column representation */
2627  for( l = noccurlistentries[pos] - 1; l >= 0; --l )
2628  {
2629  if( occurlist[pos][l] == cons1 )
2630  {
2631  --noccurlistentries[pos];
2632  assert(noccurlistentries[pos] >= 0);
2633 
2634  occurlist[pos][l] = occurlist[pos][noccurlistentries[pos]];
2635  break;
2636  }
2637  }
2638  assert(l >= 0);
2639  }
2640  else
2641  {
2642  assert(consdata1->nvars == nvars);
2643 
2644  /* delete cons */
2645  SCIPdebugMsg(scip, "logicor constraint <%s> is redundant due to constraint <%s> after removing variable <%s>\n",
2646  SCIPconsGetName(cons), SCIPconsGetName(cons1), SCIPvarGetName(artvar));
2647 
2648  /* remove cons from columns representation */
2649  removeConsFromOccurList(cons, varstopos, occurlist, noccurlistentries, occurlistlength);
2650 
2651  /* update flags of cons1 */
2652  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons) );
2653 
2654  SCIP_CALL( SCIPdelCons(scip, cons) );
2655  *deleted = TRUE;
2656  }
2657 
2658  /* remove variable */
2659  SCIP_CALL( delCoefPos(scip, cons1, eventhdlr, conspos) );
2660  ++(*nchgcoefs);
2661  consdataSort(consdata1);
2662  consdataCalcSignature(consdata1);
2663 
2664  if( *deleted )
2665  return SCIP_OKAY;
2666  }
2667  }
2668  }
2669  }
2670  }
2671 
2672  return SCIP_OKAY;
2673 }
2674 
2675 /** find and remove redundant non-zero entries */
2676 static
2678  SCIP* scip, /**< SCIP data structure */
2679  SCIP_CONS** conss, /**< sorted array of logicor constraint */
2680  int nconss, /**< number of sorted constraints */
2681  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2682  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2683  int* noccurlistentries, /**< number of constraints for each variable in the occurlist */
2684  int occurlistlength, /**< number of columns in the occurlist */
2685  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2686  int* ndelconss, /**< pointer to store the number of deleted constraints */
2687  int* nchgcoefs /**< pointer to store the number of remove coefficients */
2688  )
2689 {
2690  SCIP_VAR** vars;
2691  SCIP_CONSDATA* consdata;
2692  SCIP_CONS* cons;
2693  SCIP_VAR* artvar;
2694  int nvars;
2695  int c;
2696  int v;
2697 
2698  assert(scip != NULL);
2699  assert(conss != NULL || nconss == 0);
2700  assert(varstopos != NULL);
2701  assert(occurlist != NULL);
2702  assert(noccurlistentries != NULL);
2703  assert(eventhdlr != NULL);
2704  assert(ndelconss != NULL);
2705  assert(nchgcoefs != NULL);
2706 
2707  if( nconss == 0 )
2708  return SCIP_OKAY;
2709 
2710  assert(conss != NULL);
2711 
2712  for( c = 0; c < nconss; ++c )
2713  {
2714  cons = conss[c];
2715  assert(cons != NULL);
2716  assert(!SCIPconsIsModifiable(cons));
2717 
2718  if( !SCIPconsIsActive(cons) )
2719  continue;
2720 
2721  consdata = SCIPconsGetData(cons);
2722  assert(consdata != NULL);
2723 
2724  nvars = consdata->nvars;
2725  assert(nvars >= 1);
2726 
2727  if( nvars == 1 )
2728  continue;
2729 
2730  vars = consdata->vars;
2731  assert(vars != NULL);
2732 
2733  for( v = nvars - 1; v >= 0; --v )
2734  {
2735  artvar = SCIPvarGetNegatedVar(vars[v]);
2736 
2737  if( artvar != NULL && SCIPhashmapExists(varstopos, (void*) artvar) )
2738  {
2739  SCIP_Bool deleted;
2740 
2741  /* detect and remove redundant non-zero entries */
2742  /* @todo: improve this algorithm by using the information that a constraint variables does not appaer in any
2743  * other constraint, which means that only this variable needs to be negated to check for redundant
2744  * non-zeros, therefor change also findShortestOccurlist() to return the corresponding
2745  * variable/position
2746  */
2747  SCIP_CALL( removeRedundantNonZeros(scip, cons, artvar, v, varstopos, occurlist, noccurlistentries,
2748  occurlistlength, eventhdlr, nchgcoefs, &deleted) );
2749 
2750  if( deleted )
2751  {
2752  assert(SCIPconsIsDeleted(cons));
2753  ++(*ndelconss);
2754  break;
2755  }
2756  else
2757  assert(SCIPconsIsActive(cons));
2758  }
2759  }
2760  }
2761 
2762  return SCIP_OKAY;
2763 }
2764 
2765 
2766 /** prepares a constraint by removing fixings and merge it */
2767 static
2769  SCIP* scip, /**< SCIP data structure */
2770  SCIP_CONS* cons, /**< logic or constraint */
2771  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2772  unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
2773  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
2774  SCIP_Bool* redundant, /**< returns whether a variable fixed to one exists in the constraint */
2775  int* nfixedvars, /**< pointer to count number of fixings */
2776  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
2777  int* ndelconss, /**< pointer to count number of deleted constraints */
2778  SCIP_Bool* cutoff /**< pointer to store, if cut off appeared */
2779  )
2780 {
2781  SCIP_CONSDATA* consdata;
2782 
2783  assert(scip != NULL);
2784  assert(cons != NULL);
2785  assert(!SCIPconsIsDeleted(cons));
2786  assert(eventhdlr != NULL);
2787  assert(*entries != NULL);
2788  assert(nentries != NULL);
2789  assert(redundant != NULL);
2790  assert(nfixedvars != NULL);
2791  assert(nchgcoefs != NULL);
2792  assert(ndelconss != NULL);
2793  assert(redundant != NULL);
2794 
2795  consdata = SCIPconsGetData(cons);
2796  assert(consdata != NULL);
2797  assert(consdata->nvars > 0);
2798 
2799  *redundant = FALSE;
2800 
2801  /* remove old fixings */
2802  if( !consdata->presolved )
2803  {
2804  /* remove all variables that are fixed to zero, check redundancy due to fixed-to-one variable */
2805  SCIP_CALL( applyFixings(scip, cons, eventhdlr, redundant, nchgcoefs, NULL, NULL) );
2806  }
2807 
2808  if( !*redundant )
2809  {
2810  /* merge constraint */
2811  SCIP_CALL( mergeMultiples(scip, cons, eventhdlr, entries, nentries, redundant, nchgcoefs) );
2812  }
2813 
2814  if( *redundant )
2815  {
2816  SCIP_CALL( SCIPdelCons(scip, cons) );
2817  ++(*ndelconss);
2818 
2819  return SCIP_OKAY;
2820  }
2821 
2822  if( consdata->nvars == 0 )
2823  {
2824  *cutoff = TRUE;
2825  }
2826  else if( consdata->nvars == 1 )
2827  {
2828  SCIP_Bool infeasible;
2829  SCIP_Bool fixed;
2830 
2831  SCIPdebugMsg(scip, " -> fix last remaining variable and delete constraint\n");
2832 
2833  SCIP_CALL( SCIPfixVar(scip, consdata->vars[0], 1.0, &infeasible, &fixed) );
2834  assert(!infeasible);
2835  assert(fixed);
2836  ++(*nfixedvars);
2837 
2838  SCIP_CALL( SCIPdelCons(scip, cons) );
2839  ++(*ndelconss);
2840 
2841  *redundant = TRUE;
2842  }
2843  consdata->presolved = TRUE;
2844 
2845  return SCIP_OKAY;
2846 }
2847 
2848 
2849 /** find covered/subsumed constraints and redundant non-zero entries
2850  *
2851  * covered:
2852  * e.g.: c1: x1 + x2 + x3 >= 1
2853  * c2: x1 + x2 + x3 + x4 >= 1
2854  *
2855  * strengthen:
2856  * e.g.: c1: x1 + x2 + x3 >= 1
2857  * c2: x1 + x2 + ~x3 + x4 >= 1
2858  *
2859  * => c2: x1 + x2 + x4 >= 1
2860  *
2861  * @see "Effective Preprocessing in SAT through Variable and Clause Elimination" by Niklas En and Armin Biere
2862  */
2863 static
2865  SCIP* scip, /**< SCIP data structure */
2866  SCIP_CONS** conss, /**< array of logicor constraints */
2867  int nconss, /**< number of logicor constraints */
2868  unsigned char** entries, /**< array to store whether two positions in constraints represent the same
2869  * variable */
2870  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
2871  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2872  SCIP_Bool usestrengthening, /**< should we try to strengthen constraints by removing superflous
2873  * non-zeros? */
2874  int* firstchange, /**< pointer to store first changed constraint */
2875  int* nfixedvars, /**< pointer to count number of fixings */
2876  int* ndelconss, /**< pointer to store the number of deleted constraints */
2877  int* nchgcoefs, /**< pointer to store the number of deleted coefficients */
2878  SCIP_Bool* cutoff /**< pointer to store, if cut off appeared */
2879  )
2880 {
2881  SCIP_CONS*** occurlist;
2882  SCIP_CONS** myconss;
2883  SCIP_HASHMAP* varstopos;
2884  SCIP_CONS* cons;
2885  SCIP_CONSDATA* consdata;
2886  int* noccurlistentries;
2887  int* occurlistsizes;
2888  SCIP_Bool redundant;
2889  SCIP_Bool conschanged;
2890  int nbinvars;
2891  int occurlistlength;
2892  int occurlistsize;
2893  int nmyconss;
2894  int nmaxvars;
2895  int c;
2896 
2897  assert(scip != NULL);
2898  assert(conss != NULL || nconss == 0);
2899  assert(entries != NULL);
2900  assert(*entries != NULL);
2901  assert(nentries != NULL);
2902  assert(eventhdlr != NULL);
2903  assert(firstchange != NULL);
2904  assert(0 <= *firstchange);
2905  assert(nfixedvars != NULL);
2906  assert(ndelconss != NULL);
2907  assert(nchgcoefs != NULL);
2908 
2909  if( *firstchange > nconss || nconss < 2 )
2910  return SCIP_OKAY;
2911 
2912  SCIPdebugMsg(scip, "starting removeRedundantConssAndNonzeros(), pairwise comparison to detect covered logicor constraints\n");
2913 
2914  /* copy constraints to re-order them */
2915  SCIP_CALL( SCIPduplicateBufferArray(scip, &myconss, conss, nconss) );
2916 
2917  nmyconss = nconss;
2918  for( c = nconss - 1; c >= 0; --c )
2919  {
2920  cons = myconss[c];
2921  assert(cons != NULL);
2922 
2923  if( SCIPconsIsDeleted(cons) || SCIPconsIsModifiable(cons) )
2924  {
2925  myconss[c] = myconss[nmyconss - 1];
2926  --nmyconss;
2927 
2928  continue;
2929  }
2930 
2931  /* prepare constraint by removing fixings and merge it */
2932  SCIP_CALL( prepareCons(scip, cons, eventhdlr, entries, nentries, &redundant, nfixedvars, nchgcoefs, ndelconss, cutoff) );
2933 
2934  if( redundant )
2935  {
2936  assert(SCIPconsIsDeleted(cons));
2937 
2938  myconss[c] = myconss[nmyconss - 1];
2939  --nmyconss;
2940  }
2941 
2942  if( *cutoff )
2943  {
2944  SCIPfreeBufferArray(scip, &myconss);
2945 
2946  return SCIP_OKAY;
2947  }
2948 
2949  consdata = SCIPconsGetData(cons);
2950 
2951  /* sort the constraint */
2952  consdataSort(consdata);
2953 
2954  assert(consdata->nvars >= 2);
2955  }
2956 
2957  SCIPsortPtr((void**)myconss, conssLogicorComp, nmyconss);
2958  assert(myconss[0] != NULL && myconss[nmyconss - 1] != NULL);
2959  assert(SCIPconsGetData(myconss[0]) != NULL && SCIPconsGetData(myconss[nmyconss - 1]) != NULL);
2960  assert(SCIPconsGetData(myconss[0])->nvars <= SCIPconsGetData(myconss[nmyconss - 1])->nvars);
2961 
2962  /* we can stop if strengthening is disabled and all constraints have the same amount of variables */
2963  if( !usestrengthening && SCIPconsGetData(myconss[0])->nvars == SCIPconsGetData(myconss[nmyconss - 1])->nvars )
2964  {
2965  SCIPfreeBufferArray(scip, &myconss);
2966 
2967  return SCIP_OKAY;
2968  }
2969 
2970  /* @note: in the following we have at least number of nonzeros in logicor constraints + three times two the number of
2971  * binary variables memory consumption + a map for variables to positions, we need this to get a column base
2972  * representation
2973  */
2974 
2975  /* get number of all possible(incl. implcit) binary variables and their negation */
2976  nbinvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
2977  occurlistsize = 2 * nbinvars;
2978 
2979  /* allocate memory for the column representation for each variable */
2980  SCIP_CALL( SCIPallocBufferArray(scip, &occurlist, occurlistsize) );
2981  BMSclearMemoryArray(occurlist, occurlistsize);
2982  SCIP_CALL( SCIPallocBufferArray(scip, &noccurlistentries, occurlistsize) );
2983  BMSclearMemoryArray(noccurlistentries, occurlistsize);
2984  SCIP_CALL( SCIPallocBufferArray(scip, &occurlistsizes, occurlistsize) );
2985  BMSclearMemoryArray(occurlistsizes, occurlistsize);
2986 
2987  /* create hashmap to map all occuring variables to a position in the list */
2988  SCIP_CALL( SCIPhashmapCreate(&varstopos, SCIPblkmem(scip), nmyconss) );
2989 
2990  /* get maximal number of variables over all logicor constraints */
2991  c = nmyconss - 1;
2992  cons = myconss[c];
2993  assert(cons != NULL);
2994  assert(SCIPconsIsActive(cons));
2995  consdata = SCIPconsGetData(cons);
2996  assert(consdata != NULL);
2997  nmaxvars = consdata->nvars;
2998 
2999  occurlistlength = 0;
3000  conschanged = FALSE;
3001 
3002  /* determine all constraints with the maximal number of variables and add them to the column representation */
3003  do
3004  {
3005  /* calculate hash-signature */
3006  consdataCalcSignature(consdata);
3007  assert(consdata->validsignature);
3008  conschanged = conschanged || consdata->changed;
3009  consdata->changed = FALSE;
3010 
3011  /* add constraint to column data structure */
3012  SCIP_CALL( addConsToOccurList(scip, cons, varstopos, occurlist, noccurlistentries, occurlistsizes, &occurlistlength, occurlistsize) );
3013 
3014  --c;
3015  if( c < 0 )
3016  break;
3017 
3018  cons = myconss[c];
3019  assert(cons != NULL);
3020  assert(SCIPconsIsActive(cons));
3021  consdata = SCIPconsGetData(cons);
3022  assert(consdata != NULL);
3023  }
3024  while( consdata->nvars == nmaxvars );
3025 
3026  /* remove covered constraints and left over constraints to the column representation */
3027  while( c >= 0 )
3028  {
3029  cons = myconss[c];
3030  assert(cons != NULL);
3031  assert(SCIPconsIsActive(cons));
3032  consdata = SCIPconsGetData(cons);
3033  assert(consdata != NULL);
3034 
3035  /* calculate hash-signature */
3036  consdataCalcSignature(consdata);
3037  assert(consdata->validsignature);
3038 
3039  /* search for covered constraints */
3040  if( conschanged || consdata->changed )
3041  {
3042  /* detect covered constraints
3043  *
3044  * e.g.: c1: x1 + x2 + x3 >= 1
3045  * c2: x1 + x2 + x3 + x4 >= 1
3046  *
3047  * => delete c2
3048  */
3049  SCIP_CALL( removeRedundantConss(scip, cons, varstopos, occurlist, noccurlistentries, occurlistlength, ndelconss) );
3050  assert(SCIPconsIsActive(cons));
3051 
3052  consdata->changed = FALSE;
3053  conschanged = TRUE;
3054  }
3055 
3056  /* add constraint to column data structure */
3057  SCIP_CALL( addConsToOccurList(scip, cons, varstopos, occurlist, noccurlistentries, occurlistsizes, &occurlistlength, occurlistsize) );
3058 
3059  --c;
3060  }
3061 
3062  /* strengthen constraint while removing non-zeros
3063  *
3064  * e.g.: c1: x1 + x2 + x3 >= 1
3065  * c2: x1 + x2 + ~x3 + x4 >= 1
3066  *
3067  * => c2: x1 + x2 + x4 >= 1
3068  *
3069  * special case:
3070  *
3071  * e.g.: c1: x1 + x2 + x3 >= 1
3072  * c2: x1 + x2 + ~x3 >= 1
3073  *
3074  * => delete c1; c2: x1 + x2 >= 1
3075  *
3076  */
3077  SCIP_CALL( strengthenConss(scip, myconss, nmyconss, varstopos, occurlist, noccurlistentries, occurlistlength, eventhdlr, ndelconss, nchgcoefs) );
3078 
3079  /* delete temporary memory in occurlist */
3080  for( --occurlistsize ; occurlistsize >= 0; --occurlistsize )
3081  {
3082  assert((occurlistsizes[occurlistsize] == 0) == (occurlist[occurlistsize] == NULL));
3083  SCIPfreeBufferArrayNull(scip, &(occurlist[occurlistsize]));
3084  }
3085 
3086  /* delete temporary memory */
3087  SCIPhashmapFree(&varstopos);
3088  SCIPfreeBufferArray(scip, &occurlistsizes);
3089  SCIPfreeBufferArray(scip, &noccurlistentries);
3090  SCIPfreeBufferArray(scip, &occurlist);
3091  SCIPfreeBufferArray(scip, &myconss);
3092 
3093  return SCIP_OKAY;
3094 }
3095 
3096 #define MAX_CONSLENGTH 200
3097 
3098 /** try to tighten constraints by reducing the number of variables in the constraints using implications and cliques,
3099  * also derive fixations through them, @see SCIPshrinkDisjunctiveVarSet()
3100  */
3101 static
3103  SCIP* scip, /**< SCIP data structure */
3104  SCIP_CONSHDLRDATA* conshdlrdata, /**< logic or constraint handler data */
3105  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
3106  SCIP_CONS** conss, /**< all constraints */
3107  int nconss, /**< number of constraints */
3108  unsigned char** entries, /**< array to store whether two positions in constraints represent the same
3109  * variable */
3110  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
3111  int* nfixedvars, /**< pointer to count number of fixings */
3112  int* ndelconss, /**< pointer to count number of deleted constraints */
3113  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
3114  SCIP_Bool* cutoff /**< pointer to store, if cut off appeared */
3115  )
3116 {
3117  SCIP_VAR** probvars;
3118  SCIP_VAR* var;
3119  SCIP_Real* bounds;
3120  SCIP_Bool* boundtypes;
3121  SCIP_Bool* redundants;
3122  int nbinprobvars;
3123  int nredvars;
3124  int c;
3125  int v;
3126 
3127  assert(scip != NULL);
3128  assert(eventhdlr != NULL);
3129  assert(conss != NULL || nconss == 0);
3130  assert(entries != NULL);
3131  assert(*entries != NULL);
3132  assert(nentries != NULL);
3133  assert(nfixedvars != NULL);
3134  assert(ndelconss != NULL);
3135  assert(nchgcoefs != NULL);
3136 
3137  if( nconss == 0 )
3138  return SCIP_OKAY;
3139 
3140  assert(conss != NULL);
3141 
3142  if( SCIPgetNCliques(scip) == conshdlrdata->nlastcliquesshorten
3143  && SCIPgetNImplications(scip) == conshdlrdata->nlastimplsshorten )
3144  return SCIP_OKAY;
3145 
3146  conshdlrdata->nlastcliquesshorten = SCIPgetNCliques(scip);
3147  conshdlrdata->nlastimplsshorten = SCIPgetNImplications(scip);
3148 
3149  nbinprobvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
3150 
3151  /* allocate temporary memory */
3152  SCIP_CALL( SCIPallocBufferArray(scip, &probvars, nbinprobvars) );
3153  SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nbinprobvars) );
3154  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nbinprobvars) );
3155  SCIP_CALL( SCIPallocCleanBufferArray(scip, &redundants, nbinprobvars) );
3156 
3157  for( c = nconss - 1; c >= 0; --c )
3158  {
3159  SCIP_Bool redundant = FALSE;
3160  SCIP_Bool glbinfeas = FALSE;
3161  SCIP_CONS* cons = conss[c];
3162  SCIP_CONSDATA* consdata;
3163 
3164  assert(cons != NULL);
3165 
3166  if( SCIPconsIsDeleted(cons) )
3167  continue;
3168 
3169  consdata = SCIPconsGetData(cons);
3170  assert(consdata != NULL);
3171 
3172  /* prepare constraint by removing fixings and merge it */
3173  SCIP_CALL( prepareCons(scip, cons, eventhdlr, entries, nentries, &redundant, nfixedvars, nchgcoefs, ndelconss, cutoff) );
3174 
3175  if( redundant )
3176  {
3177  assert(SCIPconsIsDeleted(cons));
3178  continue;
3179  }
3180 
3181  if( *cutoff )
3182  goto TERMINATE;
3183 
3184  assert(consdata->nvars >= 2);
3185 
3186  /* do not try to shorten too long constraints */
3187  if( consdata->nvars > MAX_CONSLENGTH )
3188  continue;
3189 
3190  /* form necessary data */
3191  for( v = consdata->nvars - 1; v >= 0; --v)
3192  {
3193  var = consdata->vars[v];
3194  assert(var != NULL);
3196 
3197  if( SCIPvarIsActive(var) )
3198  {
3199  probvars[v] = var;
3200  bounds[v] = 1.0;
3201  boundtypes[v] = FALSE;
3202  }
3203  else
3204  {
3205  probvars[v] = SCIPvarGetNegationVar(var);
3206  bounds[v] = 0.0;
3207  boundtypes[v] = TRUE;
3208  }
3209  }
3210 
3211  SCIP_CALL( SCIPcleanupCliques(scip, cutoff) );
3212 
3213  if( *cutoff )
3214  goto TERMINATE;
3215 
3216  /* use implications and cliques to derive global fixings and to shrink the number of variables in this constraints */
3217  SCIP_CALL( SCIPshrinkDisjunctiveVarSet(scip, probvars, bounds, boundtypes, redundants, consdata->nvars, &nredvars,
3218  nfixedvars, &redundant, &glbinfeas, TRUE) );
3219 
3220  if( glbinfeas )
3221  goto TERMINATE;
3222 
3223  /* remove redundant constraint */
3224  if( redundant )
3225  {
3226  SCIP_CALL( SCIPdelCons(scip, cons) );
3227  ++(*ndelconss);
3228 
3229  /* reset redundants array to FALSE */
3230 #if 1
3231  BMSclearMemoryArray(redundants, consdata->nvars);
3232 #else
3233  if( nredvars > 0 )
3234  {
3235  for( v = consdata->nvars - 1; v >= 0; --v )
3236  {
3237  if( redundants[v] )
3238  {
3239  redundants[v] = FALSE;
3240  }
3241  }
3242  }
3243 #endif
3244  continue;
3245  }
3246 
3247  /* remove redundant variables */
3248  if( nredvars > 0 )
3249  {
3250  for( v = consdata->nvars - 1; v >= 0; --v )
3251  {
3252  if( redundants[v] )
3253  {
3254  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
3255 
3256  /* reset entry to FALSE */
3257  redundants[v] = FALSE;
3258  }
3259  }
3260  *nchgcoefs += nredvars;
3261 
3262  /* if only one variable is left over fix it */
3263  if( consdata->nvars == 1 )
3264  {
3265  SCIP_Bool infeasible;
3266  SCIP_Bool fixed;
3267 
3268  SCIPdebugMsg(scip, " -> fix last remaining variable and delete constraint\n");
3269 
3270  SCIP_CALL( SCIPfixVar(scip, consdata->vars[0], 1.0, &infeasible, &fixed) );
3271  assert(!infeasible);
3272  assert(fixed);
3273  ++(*nfixedvars);
3274 
3275  SCIP_CALL( SCIPdelCons(scip, cons) );
3276  ++(*ndelconss);
3277  }
3278  /* @todo might also upgrade a two variable constraint to a set-packing constraint */
3279  }
3280  }
3281 
3282  TERMINATE:
3283  /* free temporary memory */
3284  SCIPfreeCleanBufferArray(scip, &redundants);
3285  SCIPfreeBufferArray(scip, &boundtypes);
3286  SCIPfreeBufferArray(scip, &bounds);
3287  SCIPfreeBufferArray(scip, &probvars);
3288 
3289  return SCIP_OKAY;
3290 }
3291 
3292 #define MAXCOMPARISONS 1000000
3293 
3294 /** try to find a negated clique in a constraint which makes this constraint redundant but we need to keep the negated
3295  * clique information alive, so we create a corresponding set-packing constraint
3296  */
3297 static
3299  SCIP* scip, /**< SCIP data structure */
3300  SCIP_CONSHDLR* conshdlr, /**< logicor constraint handler */
3301  SCIP_CONSHDLR* conshdlrsetppc, /**< setppc constraint handler, or NULL */
3302  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
3303  SCIP_CONS** conss, /**< all constraints */
3304  int nconss, /**< number of constraints */
3305  unsigned char** entries, /**< array to store whether two positions in constraints represent the same
3306  * variable */
3307  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
3308  int* nfixedvars, /**< pointer to count number of fixings */
3309  int* ndelconss, /**< pointer to count number of deleted constraints */
3310  int* nupgdconss, /**< pointer to count number of upgraded constraints */
3311  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
3312  SCIP_Bool* cutoff /**< pointer to store, if cut off appeared */
3313  )
3314 {
3315  SCIP_CONSHDLRDATA* conshdlrdata;
3316  SCIP_CONS* cons;
3317  SCIP_CONSDATA* consdata;
3318  SCIP_VAR** repvars;
3319  SCIP_Bool* negated;
3320  SCIP_VAR* var1;
3321  SCIP_Bool redundant;
3322  int c;
3323  int size;
3324  int maxcomppercons;
3325  int comppercons;
3326 
3327  assert(scip != NULL);
3328  assert(conshdlr != NULL);
3329  assert(eventhdlr != NULL);
3330  assert(conss != NULL || nconss == 0);
3331  assert(entries != NULL);
3332  assert(*entries != NULL);
3333  assert(nentries != NULL);
3334  assert(nfixedvars != NULL);
3335  assert(ndelconss != NULL);
3336  assert(nupgdconss != NULL);
3337  assert(nchgcoefs != NULL);
3338  assert(cutoff != NULL);
3339 
3340  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3341  assert(conshdlrdata != NULL);
3342 
3343  if( nconss == 0 )
3344  return SCIP_OKAY;
3345 
3346  if( SCIPgetNCliques(scip) == conshdlrdata->nlastcliquesneg && SCIPgetNImplications(scip) == conshdlrdata->nlastimplsneg )
3347  return SCIP_OKAY;
3348 
3349  conshdlrdata->nlastcliquesneg = SCIPgetNCliques(scip);
3350  conshdlrdata->nlastimplsneg = SCIPgetNImplications(scip);
3351 
3352  /* estimate the maximal number of variables in a logicor constraint */
3353  size = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
3354  if( size <= 0 )
3355  return SCIP_OKAY;
3356 
3357  /* temporary memory for active/negation of active variables */
3358  SCIP_CALL( SCIPallocBufferArray(scip, &repvars, size) );
3359  SCIP_CALL( SCIPallocBufferArray(scip, &negated, size) );
3360 
3361  /* iterate over all constraints and try to find negated cliques in logicors */
3362  for( c = nconss - 1; c >= 0; --c )
3363  {
3364  int v;
3365 
3366  assert(conss != NULL); /* for flexelint */
3367 
3368  cons = conss[c];
3369  assert(cons != NULL);
3370 
3371  if( !SCIPconsIsActive(cons) )
3372  continue;
3373 
3374  /* prepare constraint by removing fixings and merge it */
3375  SCIP_CALL( prepareCons(scip, cons, eventhdlr, entries, nentries, &redundant, nfixedvars, nchgcoefs, ndelconss, cutoff) );
3376 
3377  if( redundant )
3378  {
3379  assert(SCIPconsIsDeleted(cons));
3380  continue;
3381  }
3382 
3383  if( *cutoff )
3384  goto TERMINATE;
3385 
3386  consdata = SCIPconsGetData(cons);
3387  assert(consdata != NULL);
3388  assert(consdata->nvars >= 2);
3389  assert(consdata->nvars <= size);
3390  assert(consdata->presolved);
3391 
3392  if( SCIPconsIsModifiable(cons) && consdata->nvars == 2 )
3393  continue;
3394 
3395  if( c % 100 == 0 && SCIPisStopped(scip) )
3396  break;
3397 
3398  maxcomppercons = MAXCOMPARISONS / nconss;
3399  comppercons = 0;
3400 
3401  BMScopyMemoryArray(repvars, consdata->vars, consdata->nvars);
3402 
3403  /* all variables should be active or negative active variables, otherwise something went wrong with applyFixings()
3404  * called before mergeMultiples()
3405  */
3406  for( v = consdata->nvars - 1; v >= 0; --v )
3407  {
3408  assert(SCIPvarIsActive(repvars[v]) || (SCIPvarGetStatus(repvars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(repvars[v]))));
3409  negated[v] = SCIPvarIsNegated(repvars[v]);
3410  }
3411 
3412  for( v = consdata->nvars - 1; v > 0; --v )
3413  {
3414  SCIP_Bool breakloop;
3415  SCIP_Bool neg1;
3416  int w;
3417 
3418  var1 = repvars[v];
3419 
3420  /* if there is no negated variable, there can't be a negated clique */
3421  if( SCIPvarGetNegatedVar(var1) == NULL )
3422  continue;
3423 
3424  /* get active counterpart to check for common cliques */
3426  {
3427  var1 = SCIPvarGetNegatedVar(var1);
3428  neg1 = TRUE;
3429  }
3430  else
3431  neg1 = FALSE;
3432 
3433  if( !SCIPvarIsActive(var1) )
3434  continue;
3435 
3436  /* no cliques available */
3437  if( SCIPvarGetNCliques(var1, neg1) == 0 && SCIPvarGetNImpls(var1, neg1) == 0 )
3438  continue;
3439 
3440  comppercons += (v - 1);
3441 
3442  breakloop = FALSE;
3443 
3444  for( w = v - 1; w >= 0; --w )
3445  {
3446  SCIP_VAR* var2;
3447  SCIP_Bool neg2;
3448 
3449  var2 = repvars[w];
3450 
3451  /* if there is no negated variable, there can't be a negated clique */
3452  if( SCIPvarGetNegatedVar(var2) == NULL )
3453  continue;
3454 
3456  {
3457  var2 = SCIPvarGetNegatedVar(var2);
3458  neg2 = TRUE;
3459  }
3460  else
3461  neg2 = FALSE;
3462 
3463  if( !SCIPvarIsActive(var2) )
3464  continue;
3465 
3466  /* no cliques available */
3467  if( SCIPvarGetNCliques(var2, neg2) == 0 && SCIPvarGetNImpls(var2, neg2) == 0 )
3468  continue;
3469 
3470  /* check if both active variable are the same */
3471  if( var1 == var2 )
3472  {
3473  if( neg1 != neg2 )
3474  {
3475  SCIPdebugMsg(scip, "logicor constraint <%s> is redundant, because variable <%s> and its negation <%s> exist\n",
3476  SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2));
3477 
3478  SCIP_CALL( SCIPdelCons(scip, cons) );
3479 
3480  breakloop = TRUE;
3481  }
3482  else
3483  {
3484  #ifndef NDEBUG
3485  SCIP_VAR* lastvar = consdata->vars[consdata->nvars - 1];
3486  #endif
3487  SCIPdebugMsg(scip, "in logicor constraint <%s>, active variable of <%s> and active variable of <%s> are the same, removing the first\n",
3488  SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(consdata->vars[w]));
3489 
3490  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
3491 
3492  if( v < consdata->nvars )
3493  {
3494  /* delCoefPos replaces the variable on position v with the last one, so w also need to correct the
3495  * negated array the same way, and because of deletion the number of variables is already decreased
3496  */
3497  assert(consdata->vars[v] == lastvar);
3498  negated[v] = negated[consdata->nvars];
3499  }
3500  ++(*nchgcoefs);
3501  }
3502  break;
3503  }
3504 
3505  if( SCIPvarsHaveCommonClique(var1, neg1, var2, neg2, TRUE) && conshdlrsetppc != NULL )
3506  {
3507  SCIP_CONS* newcons;
3508  SCIP_VAR* vars[2];
3509 
3510  /* this negated clique information could be created out of this logicor constraint even if there are more
3511  * than two variables left (, for example by probing), we need to keep this information by creating a
3512  * setppc constraint instead
3513  */
3514 
3515  /* get correct variables */
3516  if( !neg1 )
3517  vars[0] = SCIPvarGetNegatedVar(var1);
3518  else
3519  vars[0] = var1;
3520 
3521  if( !neg2 )
3522  vars[1] = SCIPvarGetNegatedVar(var2);
3523  else
3524  vars[1] = var2;
3525 
3526  SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), 2, vars,
3529  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
3531 
3532  SCIP_CALL( SCIPaddCons(scip, newcons) );
3533  SCIPdebugPrintCons(scip, newcons, NULL);
3534 
3535  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3536 
3537  SCIPdebugMsg(scip, "logicor constraint <%s> is redundant due to negated clique information and will be replaced by a setppc constraint \n",
3538  SCIPconsGetName(cons));
3539  SCIPdebugMsg(scip, "variable <%s> and variable <%s> are in a negated clique\n", SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(consdata->vars[w]));
3540 
3541  SCIP_CALL( SCIPdelCons(scip, cons) );
3542  ++(*nupgdconss);
3543 
3544  breakloop = TRUE;
3545  break;
3546  }
3547  }
3548  if( breakloop )
3549  break;
3550 
3551  /* do not do to many comparisons */
3552  if( comppercons > maxcomppercons )
3553  break;
3554  }
3555  }
3556 
3557  TERMINATE:
3558  /* free temporary memory */
3559  SCIPfreeBufferArray(scip, &negated);
3560  SCIPfreeBufferArray(scip, &repvars);
3561 
3562  return SCIP_OKAY;
3563 }
3564 
3565 /** handle all cases with less than three variables in a logicor constraint
3566  *
3567  * in case a constraint has zero variables left, we detected infeasibility
3568  * in case a constraint has one variables left, we will fix it to one
3569  * in case a constraint has two variables left, we will add the implication and upgrade it to a set-packing constraint
3570  */
3571 static
3573  SCIP* scip, /**< SCIP data structure */
3574  SCIP_CONS* cons, /**< logic or constraint */
3575  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
3576  SCIP_CONSHDLR* conshdlrlinear, /**< linear constraint handler, or NULL */
3577  SCIP_CONSHDLR* conshdlrsetppc, /**< setppc constraint handler, or NULL */
3578  int* nfixedvars, /**< pointer to count number of fixings */
3579  int* nchgbds, /**< pointer to count number of tightened bounds */
3580  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
3581  int* ndelconss, /**< pointer to count number of deleted constraints */
3582  int* naddconss, /**< pointer to count number of added constraints */
3583  int* nupgdconss, /**< pointer to count number of upgraded constraints */
3584  SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
3585  )
3586 {
3587  SCIP_CONSDATA* consdata;
3588  SCIP_Bool infeasible;
3589  SCIP_Bool fixed;
3590 
3591  assert(scip != NULL);
3592  assert(cons != NULL);
3593  assert(eventhdlr != NULL);
3594  assert(nfixedvars != NULL);
3595  assert(nchgbds != NULL);
3596  assert(nchgcoefs != NULL);
3597  assert(ndelconss != NULL);
3598  assert(naddconss != NULL);
3599  assert(nupgdconss != NULL);
3600  assert(cutoff != NULL);
3601 
3602  *cutoff = FALSE;
3603 
3604  if( SCIPconsIsModifiable(cons) )
3605  return SCIP_OKAY;
3606 
3607  consdata = SCIPconsGetData(cons);
3608  assert(consdata != NULL);
3609 
3610  /* if an unmodifiable logicor constraint has only two variables, we can add an implication and we will upgrade this
3611  * constraint to a set-packing constraint
3612  */
3613  if( consdata->nvars == 2 )
3614  {
3615  /* add implication if not yet done */
3616  if( !consdata->impladded )
3617  {
3618  SCIP_Bool implinfeasible;
3619  int nimplbdchgs;
3620  SCIP_Bool values[2];
3621 
3622  values[0] = FALSE;
3623  values[1] = FALSE;
3624  /* a two-variable logicor constraint x + y >= 1 yields the implication x == 0 -> y == 1, and is represented
3625  * by the clique inequality ~x + ~y <= 1
3626  */
3627  SCIP_CALL( SCIPaddClique(scip, consdata->vars, values, consdata->nvars, FALSE, &implinfeasible, &nimplbdchgs) );
3628  *nchgbds += nimplbdchgs;
3629  if( implinfeasible )
3630  {
3631  *cutoff = TRUE;
3632  return SCIP_OKAY;
3633  }
3634 
3635  /* adding the above implication could lead to fixings, which render the constraint redundant */
3636  if ( nimplbdchgs > 0 )
3637  {
3638  SCIP_Bool redundant;
3639 
3640  /* remove all variables that are fixed to zero, check redundancy due to fixed-to-one variable */
3641  SCIP_CALL( applyFixings(scip, cons, eventhdlr, &redundant, nchgcoefs, naddconss, ndelconss) );
3642  assert(!SCIPconsIsDeleted(cons));
3643 
3644  if( redundant )
3645  {
3646  SCIPdebugMsg(scip, "logic or constraint <%s> is redundant\n", SCIPconsGetName(cons));
3647 
3648  SCIP_CALL( SCIPdelCons(scip, cons) );
3649  (*ndelconss)++;
3650 
3651  return SCIP_OKAY;
3652  }
3653  }
3654  consdata->impladded = TRUE;
3655  }
3656 
3657  /* still we have two variables left, we will upgrade this constraint */
3658  if( consdata->nvars == 2 && conshdlrsetppc != NULL )
3659  {
3660  SCIP_CONS* newcons;
3661  SCIP_VAR* vars[2];
3662 
3663  /* get correct variables */
3664  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[0], &vars[0]) );
3665  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[1], &vars[1]) );
3666 
3667  SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), 2, vars,
3672 
3673  SCIP_CALL( SCIPaddCons(scip, newcons) );
3674  SCIPdebugPrintCons(scip, newcons, NULL);
3675 
3676  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3677 
3678  SCIPdebugMsg(scip, "logicor constraint <%s> was upgraded to a set-packing constraint\n", SCIPconsGetName(cons));
3679 
3680  SCIP_CALL( SCIPdelCons(scip, cons) );
3681  ++(*nupgdconss);
3682  }
3683  }
3684 
3685  /* if unmodifiable constraint has no variables, it is infeasible,
3686  * if unmodifiable constraint has only one variable, this one can be fixed and the constraint deleted
3687  */
3688  if( consdata->nvars == 0 )
3689  {
3690  SCIPdebugMsg(scip, "logic or constraint <%s> is infeasible\n", SCIPconsGetName(cons));
3691 
3692  *cutoff = TRUE;
3693  }
3694  else if( consdata->nvars == 1 )
3695  {
3696  SCIPdebugMsg(scip, "logic or constraint <%s> has only one variable not fixed to 0.0\n",
3697  SCIPconsGetName(cons));
3698 
3699  assert(consdata->vars != NULL);
3700  assert(consdata->vars[0] != NULL);
3701 
3702  if( SCIPvarGetStatus(consdata->vars[0]) != SCIP_VARSTATUS_MULTAGGR )
3703  {
3704  SCIPdebugMsg(scip, " -> fix variable and delete constraint\n");
3705 
3706  SCIP_CALL( SCIPfixVar(scip, consdata->vars[0], 1.0, &infeasible, &fixed) );
3707  if( infeasible )
3708  {
3709  SCIPdebugMsg(scip, " -> infeasible fixing\n");
3710 
3711  *cutoff = TRUE;
3712  return SCIP_OKAY;
3713  }
3714  if( fixed )
3715  (*nfixedvars)++;
3716 
3717  SCIP_CALL( SCIPdelCons(scip, cons) );
3718  (*ndelconss)++;
3719  }
3720  else if( conshdlrlinear != NULL )
3721  {
3722  SCIP_Real coef;
3723  SCIP_CONS* conslinear;
3724  char consname[SCIP_MAXSTRLEN];
3725 
3726  SCIPdebugMsg(scip, " -> variable is multi-aggregated, upgrade to linear constraint <%s> == 1 \n",
3727  SCIPvarGetName(consdata->vars[0]));
3728 
3729  coef = 1.0;
3730  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "fixmaggr_%s_%s", SCIPconsGetName(cons),SCIPvarGetName(consdata->vars[0]) );
3731  SCIP_CALL( SCIPcreateConsLinear(scip, &conslinear, consname, 1, consdata->vars, &coef, 1.0, 1.0,
3735  SCIPconsIsStickingAtNode(cons)) );
3736 
3737  /* add constraint */
3738  SCIP_CALL( SCIPaddCons(scip, conslinear) );
3739  SCIP_CALL( SCIPreleaseCons(scip, &conslinear) );
3740  SCIP_CALL( SCIPdelCons(scip, cons) );
3741 
3742  (*ndelconss)++;
3743  (*naddconss)++;
3744  }
3745  }
3746 
3747  return SCIP_OKAY;
3748 }
3749 
3750 
3751 /*
3752  * upgrading of linear constraints
3753  */
3754 
3755 /** creates and captures a normalized (with all coefficients +1) logic or constraint */
3756 static
3758  SCIP* scip, /**< SCIP data structure */
3759  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3760  const char* name, /**< name of constraint */
3761  int nvars, /**< number of variables in the constraint */
3762  SCIP_VAR** vars, /**< array with variables of constraint entries */
3763  SCIP_Real* vals, /**< array with coefficients (+1.0 or -1.0) */
3764  int mult, /**< multiplier on the coefficients(+1 or -1) */
3765  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3766  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3767  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3768  * Usually set to TRUE. */
3769  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3770  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3771  SCIP_Bool check, /**< should the constraint be checked for feasibility?
3772  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3773  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3774  * Usually set to TRUE. */
3775  SCIP_Bool local, /**< is constraint only valid locally?
3776  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3777  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3778  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3779  * adds coefficients to this constraint. */
3780  SCIP_Bool dynamic, /**< is constraint subject to aging?
3781  * Usually set to FALSE. Set to TRUE for own cuts which
3782  * are separated as constraints. */
3783  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3784  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3785  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3786  * if it may be moved to a more global node?
3787  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3788  )
3789 {
3790  SCIP_VAR** transvars;
3791  int v;
3792 
3793  assert(nvars == 0 || vars != NULL);
3794  assert(nvars == 0 || vals != NULL);
3795  assert(mult == +1 || mult == -1);
3796 
3797  /* get temporary memory */
3798  SCIP_CALL( SCIPallocBufferArray(scip, &transvars, nvars) );
3799 
3800  /* negate positive or negative variables */
3801  for( v = 0; v < nvars; ++v )
3802  {
3803  if( mult * vals[v] > 0.0 )
3804  transvars[v] = vars[v];
3805  else
3806  {
3807  SCIP_CALL( SCIPgetNegatedVar(scip, vars[v], &transvars[v]) );
3808  }
3809  assert(transvars[v] != NULL);
3810  }
3811 
3812  /* create the constraint */
3813  SCIP_CALL( SCIPcreateConsLogicor(scip, cons, name, nvars, transvars,
3814  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3815 
3816  /* free temporary memory */
3817  SCIPfreeBufferArray(scip, &transvars);
3818 
3819  return SCIP_OKAY;
3820 }
3821 
3822 static
3823 SCIP_DECL_LINCONSUPGD(linconsUpgdLogicor)
3824 { /*lint --e{715}*/
3825  assert(upgdcons != NULL);
3826 
3827  /* check, if linear constraint can be upgraded to logic or constraint
3828  * - logic or constraints consist only of binary variables with a
3829  * coefficient of +1.0 or -1.0 (variables with -1.0 coefficients can be negated):
3830  * lhs <= x1 + ... + xp - y1 - ... - yn <= rhs
3831  * - negating all variables y = (1-Y) with negative coefficients gives:
3832  * lhs + n <= x1 + ... + xp + Y1 + ... + Yn <= rhs + n
3833  * - negating all variables x = (1-X) with positive coefficients and multiplying with -1 gives:
3834  * p - rhs <= X1 + ... + Xp + y1 + ... + yn <= p - lhs
3835  * - logic or constraints have left hand side of +1.0, and right hand side of +infinity: x(S) >= 1.0
3836  * -> without negations: (lhs == 1 - n and rhs == +inf) or (lhs == -inf and rhs = p - 1)
3837  */
3838  if( nvars > 2 && nposbin + nnegbin + nposimplbin + nnegimplbin == nvars && ncoeffspone + ncoeffsnone == nvars
3839  && ((SCIPisEQ(scip, lhs, 1.0 - ncoeffsnone) && SCIPisInfinity(scip, rhs))
3840  || (SCIPisInfinity(scip, -lhs) && SCIPisEQ(scip, rhs, ncoeffspone - 1.0))) )
3841  {
3842  int mult;
3843 
3844  SCIPdebugMsg(scip, "upgrading constraint <%s> to logic or constraint\n", SCIPconsGetName(cons));
3845 
3846  /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
3847  mult = SCIPisInfinity(scip, rhs) ? +1 : -1;
3848 
3849  /* create the logic or constraint (an automatically upgraded constraint is always unmodifiable) */
3850  assert(!SCIPconsIsModifiable(cons));
3851  SCIP_CALL( createNormalizedLogicor(scip, upgdcons, SCIPconsGetName(cons), nvars, vars, vals, mult,
3856  }
3857 
3858  return SCIP_OKAY;
3859 }
3860 
3861 /** helper function to enforce constraints */
3862 static
3864  SCIP* scip, /**< SCIP data structure */
3865  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3866  SCIP_CONS** conss, /**< constraints to process */
3867  int nconss, /**< number of constraints */
3868  int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
3869  SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
3870  SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
3871  )
3872 {
3873  SCIP_CONSHDLRDATA* conshdlrdata;
3874  SCIP_Bool cutoff;
3875  SCIP_Bool separated;
3876  SCIP_Bool reduceddom;
3877  int c;
3878 
3879  assert(conshdlr != NULL);
3880  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3881  assert(nconss == 0 || conss != NULL);
3882  assert(result != NULL);
3883 
3884  SCIPdebugMsg(scip, "Enforcing %d logic or constraints for %s solution\n", nconss, sol == NULL ? "LP" : "relaxation");
3885 
3886  *result = SCIP_FEASIBLE;
3887 
3888  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3889  assert(conshdlrdata != NULL);
3890 
3891  cutoff = FALSE;
3892  separated = FALSE;
3893  reduceddom = FALSE;
3894 
3895  /* check all useful logic or constraints for feasibility */
3896  for( c = 0; c < nusefulconss && !cutoff && !reduceddom; ++c )
3897  {
3898  SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
3899  }
3900 
3901  /* check all obsolete logic or constraints for feasibility */
3902  for( c = nusefulconss; c < nconss && !cutoff && !separated && !reduceddom; ++c )
3903  {
3904  SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
3905  }
3906 
3907  /* return the correct result */
3908  if( cutoff )
3909  *result = SCIP_CUTOFF;
3910  else if( separated )
3911  *result = SCIP_SEPARATED;
3912  else if( reduceddom )
3913  *result = SCIP_REDUCEDDOM;
3914 
3915  return SCIP_OKAY;
3916 }
3917 
3918 
3919 /*
3920  * Callback methods of constraint handler
3921  */
3922 
3923 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
3924 static
3925 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLogicor)
3926 { /*lint --e{715}*/
3927  assert(scip != NULL);
3928  assert(conshdlr != NULL);
3929  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3930 
3931  /* call inclusion method of constraint handler */
3933 
3934  *valid = TRUE;
3935 
3936  return SCIP_OKAY;
3937 }
3938 
3939 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
3940 static
3941 SCIP_DECL_CONSFREE(consFreeLogicor)
3942 { /*lint --e{715}*/
3943  SCIP_CONSHDLRDATA* conshdlrdata;
3944 
3945  assert(conshdlr != NULL);
3946  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3947  assert(scip != NULL);
3948 
3949  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3950  assert(conshdlrdata != NULL);
3951 
3952  /* free constraint handler data */
3953  SCIP_CALL( conshdlrdataFree(scip, &conshdlrdata) );
3954 
3955  SCIPconshdlrSetData(conshdlr, NULL);
3956 
3957  return SCIP_OKAY;
3958 }
3959 
3960 
3961 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
3962 static
3963 SCIP_DECL_CONSINITPRE(consInitpreLogicor)
3964 { /*lint --e{715}*/
3965  SCIP_CONSHDLRDATA* conshdlrdata;
3966  SCIP_CONSDATA* consdata;
3967  int c;
3968  int v;
3969 
3970  assert(conshdlr != NULL);
3971  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3972  assert(conshdlrdata != NULL);
3973 
3974  conshdlrdata->nlastcliquesneg = 0;
3975  conshdlrdata->nlastimplsneg = 0;
3976  conshdlrdata->nlastcliquesshorten = 0;
3977  conshdlrdata->nlastimplsshorten = 0;
3978 
3979  /* catch all variable event for deleted variables, which is only used in presolving */
3980  for( c = nconss - 1; c >= 0; --c )
3981  {
3982  consdata = SCIPconsGetData(conss[c]);
3983  assert(consdata != NULL);
3984 
3985  for( v = consdata->nvars - 1; v >= 0; --v )
3986  {
3987  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
3988  (SCIP_EVENTDATA*)conss[c], NULL) );
3989  }
3990  }
3991 
3992  return SCIP_OKAY;
3993 }
3994 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
3995 static
3996 SCIP_DECL_CONSEXITPRE(consExitpreLogicor)
3997 { /*lint --e{715}*/
3998  SCIP_CONSHDLRDATA* conshdlrdata;
3999  SCIP_CONSDATA* consdata;
4000  SCIP_Bool redundant;
4001  int nchgcoefs = 0;
4002  int c;
4003  int v;
4004 
4005  assert(conshdlr != NULL);
4006  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4007  assert(conshdlrdata != NULL);
4008 
4009  /* drop all variable event for deleted variables, which was only used in presolving */
4010  for( c = 0; c < nconss; ++c )
4011  {
4012  consdata = SCIPconsGetData(conss[c]);
4013  assert(consdata != NULL);
4014 
4015  for( v = 0; v < consdata->nvars; ++v )
4016  {
4017  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4018  (SCIP_EVENTDATA*)conss[c], -1) );
4019  }
4020 
4021  if( !SCIPconsIsDeleted(conss[c]) && !consdata->presolved )
4022  {
4023  /* we are not allowed to detect infeasibility in the exitpre stage */
4024  SCIP_CALL( applyFixings(scip, conss[c], conshdlrdata->eventhdlr, &redundant, &nchgcoefs, NULL, NULL) );
4025  }
4026  }
4027 
4028  return SCIP_OKAY;
4029 }
4030 
4031 
4032 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4033 static
4034 SCIP_DECL_CONSEXITSOL(consExitsolLogicor)
4035 { /*lint --e{715}*/
4036  SCIP_CONSDATA* consdata;
4037  int c;
4038 
4039  /* release the rows of all constraints */
4040  for( c = 0; c < nconss; ++c )
4041  {
4042  consdata = SCIPconsGetData(conss[c]);
4043  assert(consdata != NULL);
4044 
4045  if( consdata->row != NULL )
4046  {
4047  SCIP_CALL( SCIPreleaseRow(scip, &consdata->row) );
4048  }
4049  }
4050 
4051  return SCIP_OKAY;
4052 }
4053 
4054 
4055 /** frees specific constraint data */
4056 static
4057 SCIP_DECL_CONSDELETE(consDeleteLogicor)
4058 { /*lint --e{715}*/
4059  assert(conshdlr != NULL);
4060  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4061  assert(consdata != NULL);
4062  assert(*consdata != NULL);
4063 
4065  {
4066  SCIP_CONSHDLRDATA* conshdlrdata;
4067  int v;
4068 
4069  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4070  assert(conshdlrdata != NULL);
4071 
4072  for( v = (*consdata)->nvars - 1; v >= 0; --v )
4073  {
4074  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4075  (SCIP_EVENTDATA*)cons, -1) );
4076  }
4077  }
4078 
4079  /* free LP row and logic or constraint */
4080  SCIP_CALL( consdataFree(scip, consdata) );
4081 
4082  return SCIP_OKAY;
4083 }
4084 
4085 
4086 /** transforms constraint data into data belonging to the transformed problem */
4087 static
4088 SCIP_DECL_CONSTRANS(consTransLogicor)
4089 { /*lint --e{715}*/
4090  SCIP_CONSDATA* sourcedata;
4091  SCIP_CONSDATA* targetdata;
4092 
4093  /*debugMsg(scip, "Trans method of logic or constraints\n");*/
4094 
4095  assert(conshdlr != NULL);
4096  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4097  assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
4098  assert(sourcecons != NULL);
4099  assert(targetcons != NULL);
4100 
4101  sourcedata = SCIPconsGetData(sourcecons);
4102  assert(sourcedata != NULL);
4103  assert(sourcedata->row == NULL); /* in original problem, there cannot be LP rows */
4104 
4105  /* create constraint data for target constraint */
4106  SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->nvars, sourcedata->vars) );
4107 
4108  /* create target constraint */
4109  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4110  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4111  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4112  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4113  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4114 
4115  return SCIP_OKAY;
4116 }
4117 
4118 
4119 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4120 static
4121 SCIP_DECL_CONSINITLP(consInitlpLogicor)
4122 { /*lint --e{715}*/
4123  int c;
4124 
4125  *infeasible = FALSE;
4126 
4127  for( c = 0; c < nconss && !(*infeasible); ++c )
4128  {
4129  assert(SCIPconsIsInitial(conss[c]));
4130  SCIP_CALL( addCut(scip, conss[c], infeasible) );
4131  }
4132 
4133  return SCIP_OKAY;
4134 }
4135 
4136 
4137 /** separation method of constraint handler for LP solutions */
4138 static
4139 SCIP_DECL_CONSSEPALP(consSepalpLogicor)
4140 { /*lint --e{715}*/
4141  SCIP_CONSHDLRDATA* conshdlrdata;
4142  SCIP_Bool cutoff;
4143  SCIP_Bool separated;
4144  SCIP_Bool reduceddom;
4145  int c;
4146 
4147  assert(conshdlr != NULL);
4148  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4149  assert(nconss == 0 || conss != NULL);
4150  assert(result != NULL);
4151 
4152  SCIPdebugMsg(scip, "separating %d/%d logic or constraints\n", nusefulconss, nconss);
4153 
4154  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4155  assert(conshdlrdata != NULL);
4156 
4157  cutoff = FALSE;
4158  separated = FALSE;
4159  reduceddom = FALSE;
4160 
4161  /* check all useful logic or constraints for feasibility */
4162  for( c = 0; c < nusefulconss && !cutoff; ++c )
4163  {
4164  SCIP_CALL( separateCons(scip, conss[c], NULL, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
4165  }
4166 
4167  /* combine logic or constraints to get more cuts */
4168  /**@todo further cuts of logic or constraints */
4169 
4170  /* return the correct result */
4171  if( cutoff )
4172  *result = SCIP_CUTOFF;
4173  else if( reduceddom )
4174  *result = SCIP_REDUCEDDOM;
4175  else if( separated )
4176  *result = SCIP_SEPARATED;
4177  else
4178  *result = SCIP_DIDNOTFIND;
4179 
4180  return SCIP_OKAY;
4181 }
4182 
4183 
4184 /** separation method of constraint handler for arbitrary primal solutions */
4185 static
4186 SCIP_DECL_CONSSEPASOL(consSepasolLogicor)
4187 { /*lint --e{715}*/
4188  SCIP_CONSHDLRDATA* conshdlrdata;
4189  SCIP_Bool cutoff;
4190  SCIP_Bool separated;
4191  SCIP_Bool reduceddom;
4192  int c;
4193 
4194  assert(conshdlr != NULL);
4195  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4196  assert(nconss == 0 || conss != NULL);
4197  assert(result != NULL);
4198 
4199  SCIPdebugMsg(scip, "separating %d/%d logic or constraints\n", nusefulconss, nconss);
4200 
4201  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4202  assert(conshdlrdata != NULL);
4203 
4204  cutoff = FALSE;
4205  separated = FALSE;
4206  reduceddom = FALSE;
4207 
4208  /* check all useful logic or constraints for feasibility */
4209  for( c = 0; c < nusefulconss && !cutoff; ++c )
4210  {
4211  SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
4212  }
4213 
4214  /* combine logic or constraints to get more cuts */
4215  /**@todo further cuts of logic or constraints */
4216 
4217  /* return the correct result */
4218  if( cutoff )
4219  *result = SCIP_CUTOFF;
4220  else if( reduceddom )
4221  *result = SCIP_REDUCEDDOM;
4222  else if( separated )
4223  *result = SCIP_SEPARATED;
4224  else
4225  *result = SCIP_DIDNOTFIND;
4226 
4227  return SCIP_OKAY;
4228 }
4229 
4230 
4231 /** constraint enforcing method of constraint handler for LP solutions */
4232 static
4233 SCIP_DECL_CONSENFOLP(consEnfolpLogicor)
4234 { /*lint --e{715}*/
4235  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) );
4236 
4237  return SCIP_OKAY;
4238 }
4239 
4240 
4241 /** constraint enforcing method of constraint handler for relaxation solutions */
4242 static
4243 SCIP_DECL_CONSENFORELAX(consEnforelaxLogicor)
4244 { /*lint --e{715}*/
4245  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, sol, result) );
4246 
4247  return SCIP_OKAY;
4248 }
4249 
4250 
4251 /** constraint enforcing method of constraint handler for pseudo solutions */
4252 static
4253 SCIP_DECL_CONSENFOPS(consEnfopsLogicor)
4254 { /*lint --e{715}*/
4255  SCIP_CONSHDLRDATA* conshdlrdata;
4256  SCIP_Bool cutoff;
4257  SCIP_Bool infeasible;
4258  SCIP_Bool reduceddom;
4259  SCIP_Bool solvelp;
4260  int c;
4261 
4262  assert(conshdlr != NULL);
4263  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4264  assert(nconss == 0 || conss != NULL);
4265  assert(result != NULL);
4266 
4267  SCIPdebugMsg(scip, "pseudo enforcing %d logic or constraints\n", nconss);
4268 
4269  *result = SCIP_FEASIBLE;
4270 
4271  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4272  assert(conshdlrdata != NULL);
4273 
4274  cutoff = FALSE;
4275  infeasible = FALSE;
4276  reduceddom = FALSE;
4277  solvelp = FALSE;
4278 
4279  /* check all logic or constraints for feasibility */
4280  for( c = 0; c < nconss && !cutoff && !reduceddom && !solvelp; ++c )
4281  {
4282  SCIP_CALL( enforcePseudo(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &infeasible, &reduceddom, &solvelp) );
4283  }
4284 
4285  if( cutoff )
4286  *result = SCIP_CUTOFF;
4287  else if( reduceddom )
4288  *result = SCIP_REDUCEDDOM;
4289  else if( solvelp )
4290  *result = SCIP_SOLVELP;
4291  else if( infeasible )
4292  *result = SCIP_INFEASIBLE;
4293 
4294  return SCIP_OKAY;
4295 }
4296 
4297 
4298 /** feasibility check method of constraint handler for integral solutions */
4299 static
4300 SCIP_DECL_CONSCHECK(consCheckLogicor)
4301 { /*lint --e{715}*/
4302  SCIP_CONS* cons;
4303  SCIP_CONSDATA* consdata;
4304  int c;
4305 
4306  assert(conshdlr != NULL);
4307  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4308  assert(nconss == 0 || conss != NULL);
4309  assert(result != NULL);
4310 
4311  *result = SCIP_FEASIBLE;
4312 
4313  /* check all logic or constraints for feasibility */
4314  for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
4315  {
4316  cons = conss[c];
4317  consdata = SCIPconsGetData(cons);
4318  assert(consdata != NULL);
4319  if( checklprows || consdata->row == NULL || !SCIProwIsInLP(consdata->row) )
4320  {
4321  SCIP_Bool violated;
4322 
4323  SCIP_CALL( checkCons(scip, cons, sol, &violated) );
4324  if( violated )
4325  {
4326  /* constraint is violated */
4327  *result = SCIP_INFEASIBLE;
4328 
4329  if( printreason )
4330  {
4331 #ifndef NDEBUG
4332  int v;
4333  for( v = 0; v < consdata->nvars; ++v )
4334  {
4335  assert( consdata->vars[v] != NULL);
4336  assert( SCIPvarIsBinary(consdata->vars[v]) );
4337  assert( SCIPisFeasLT(scip, SCIPgetSolVal(scip, sol, consdata->vars[v]), 1.0) );
4338  }
4339 #endif
4340  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
4341  SCIPinfoMessage(scip, NULL, ";\n");
4342  SCIPinfoMessage(scip, NULL, "violation: all variables are set to zero\n");
4343  }
4344  }
4345  }
4346  }
4347 
4348  return SCIP_OKAY;
4349 }
4350 
4351 
4352 /** domain propagation method of constraint handler */
4353 static
4354 SCIP_DECL_CONSPROP(consPropLogicor)
4355 { /*lint --e{715}*/
4356  SCIP_CONSHDLRDATA* conshdlrdata;
4357  SCIP_Bool cutoff;
4358  SCIP_Bool reduceddom;
4359  SCIP_Bool addcut;
4360  SCIP_Bool mustcheck;
4361  int c;
4362 #ifndef NDEBUG
4363  SCIP_Bool inpresolve = (SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE);
4364 #endif
4365 
4366  assert(conshdlr != NULL);
4367  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4368  assert(nconss == 0 || conss != NULL);
4369  assert(result != NULL);
4370 
4371  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4372  assert(conshdlrdata != NULL);
4373 
4374  cutoff = FALSE;
4375  reduceddom = FALSE;
4376 
4377  /* propagate all useful logic or constraints */
4378  for( c = 0; c < nusefulconss && !cutoff; ++c )
4379  {
4380  assert(inpresolve || !(SCIPconsGetData(conss[c])->existmultaggr));
4381 
4382  SCIPdebugMsg(scip, " propagate constraint %s\n", SCIPconsGetName(conss[c]));
4383  SCIP_CALL( processWatchedVars(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &reduceddom, &addcut, &mustcheck) );
4384  }
4385 
4386  /* return the correct result */
4387  if( cutoff )
4388  *result = SCIP_CUTOFF;
4389  else if( reduceddom )
4390  *result = SCIP_REDUCEDDOM;
4391  else
4392  *result = SCIP_DIDNOTFIND;
4393 
4394  return SCIP_OKAY;
4395 }
4396 
4397 /** presolving method of constraint handler */
4398 static
4399 SCIP_DECL_CONSPRESOL(consPresolLogicor)
4400 { /*lint --e{715}*/
4401  SCIP_CONSHDLRDATA* conshdlrdata;
4402  SCIP_CONS* cons;
4403  SCIP_CONSDATA* consdata;
4404  unsigned char* entries;
4405  SCIP_Bool redundant;
4406  int c;
4407  int firstchange;
4408  int nentries;
4409  int oldnfixedvars;
4410  int oldnchgbds;
4411  int oldndelconss;
4412  int oldnupgdconss;
4413  int oldnchgcoefs;
4414 
4415  assert(conshdlr != NULL);
4416  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4417  assert(scip != NULL);
4418  assert(result != NULL);
4419 
4420  *result = SCIP_DIDNOTFIND;
4421 
4422  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4423  assert(conshdlrdata != NULL);
4424 
4425  nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
4426 
4427  oldnfixedvars = *nfixedvars;
4428  oldnchgbds = *nchgbds;
4429  oldndelconss = *ndelconss;
4430  oldnupgdconss = *nupgdconss;
4431  oldnchgcoefs = *nchgcoefs;
4432 
4433  firstchange = INT_MAX;
4434 
4435  SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
4436 
4437  /* process constraints */
4438  for( c = 0; c < nconss && *result != SCIP_CUTOFF && !SCIPisStopped(scip); ++c )
4439  {
4440  cons = conss[c];
4441  assert(cons != NULL);
4442  consdata = SCIPconsGetData(cons);
4443  assert(consdata != NULL);
4444 
4445  SCIPdebugMsg(scip, "presolving logic or constraint <%s>\n", SCIPconsGetName(cons));
4446 
4447  /* force presolving the constraint in the initial round */
4448  if( nrounds == 0 )
4449  {
4450  SCIP_CALL( SCIPenableConsPropagation(scip, cons) );
4451  }
4452 
4453  redundant = FALSE;
4454  if( !consdata->presolved )
4455  {
4456  /* remove all variables that are fixed to zero, check redundancy due to fixed-to-one variable */
4457  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, &redundant, nchgcoefs, naddconss, ndelconss) );
4458  }
4459 
4460  if( SCIPconsIsDeleted(cons) )
4461  continue;
4462 
4463  /* find pairs of negated variables in constraint: constraint is redundant */
4464  /* find sets of equal variables in constraint: multiple entries of variable can be replaced by single entry */
4465  if( !redundant )
4466  {
4467  SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, &redundant, nchgcoefs) );
4468  }
4469 
4470  if( redundant )
4471  {
4472  SCIPdebugMsg(scip, "logic or constraint <%s> is redundant\n", SCIPconsGetName(cons));
4473  SCIP_CALL( SCIPdelCons(scip, cons) );
4474  (*ndelconss)++;
4475  *result = SCIP_SUCCESS;
4476  continue;
4477  }
4478  else if( !SCIPconsIsModifiable(cons) )
4479  {
4480  if( consdata->nvars <= 2 )
4481  {
4482  SCIP_Bool cutoff;
4483 
4484  /* handle all cases with less than three variables in a logicor constraint */
4485  SCIP_CALL( fixDeleteOrUpgradeCons(scip, cons, conshdlrdata->eventhdlr, conshdlrdata->conshdlrlinear,
4486  conshdlrdata->conshdlrsetppc, nfixedvars, nchgbds, nchgcoefs, ndelconss, naddconss, nupgdconss, &cutoff) );
4487 
4488  if( cutoff )
4489  {
4490  *result = SCIP_CUTOFF;
4491  goto TERMINATE;
4492  }
4493  else if( *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds || *nchgcoefs > oldnchgcoefs
4494  || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4495  *result = SCIP_SUCCESS;
4496 
4497  if( SCIPconsIsDeleted(cons) )
4498  continue;
4499  }
4500  }
4501 
4502  /* perform dual reductions */
4503  if( conshdlrdata->dualpresolving && SCIPallowDualReds(scip) )
4504  {
4505  SCIP_CALL( dualPresolving(scip, cons, conshdlrdata->eventhdlr, nfixedvars, ndelconss, nchgcoefs, result) );
4506 
4507  /* if dual reduction deleted the constraint we take the next */
4508  if( !SCIPconsIsActive(cons) )
4509  continue;
4510 
4511  /* in dualpresolving we may have removed variables, so we need to take care of special cases */
4512  if( consdata->nvars <= 2 )
4513  {
4514  SCIP_Bool cutoff;
4515 
4516  /* handle all cases with less than three variables in a logicor constraint */
4517  SCIP_CALL( fixDeleteOrUpgradeCons(scip, cons, conshdlrdata->eventhdlr, conshdlrdata->conshdlrlinear,
4518  conshdlrdata->conshdlrsetppc, nfixedvars, nchgbds, nchgcoefs, ndelconss, naddconss, nupgdconss, &cutoff) );
4519 
4520  if( cutoff )
4521  {
4522  *result = SCIP_CUTOFF;
4523  goto TERMINATE;
4524  }
4525  else if( *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds || *nchgcoefs > oldnchgcoefs
4526  || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4527  *result = SCIP_SUCCESS;
4528 
4529  if( SCIPconsIsDeleted(cons) )
4530  continue;
4531  }
4532  }
4533 
4534  /* remember the first changed constraint to begin the next redundancy round with */
4535  if( firstchange == INT_MAX && consdata->changed )
4536  firstchange = c;
4537 
4538  assert(consdata->nvars >= 2 || SCIPconsIsModifiable(cons));
4539  }
4540 
4541  assert(*result != SCIP_CUTOFF);
4542 
4543  /* fast preprocessing of pairs of logic or constraints, used for equal constraints */
4544  if( firstchange < nconss && conshdlrdata->presolusehashing )
4545  {
4546  /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
4547  SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, ndelconss) );
4548  }
4549 
4550  /* preprocess pairs of logic or constraints and apply negated clique presolving */
4551  if( SCIPisPresolveFinished(scip) )
4552  {
4553  SCIP_Bool cutoff = FALSE;
4554 
4555  /* check constraints for redundancy */
4556  if( conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4557  {
4558  SCIP_CALL( removeRedundantConssAndNonzeros(scip, conss, nconss, &entries, &nentries, conshdlrdata->eventhdlr,
4559  conshdlrdata->usestrengthening, &firstchange, nfixedvars, ndelconss, nchgcoefs, &cutoff) );
4560 
4561  if( cutoff )
4562  {
4563  *result = SCIP_CUTOFF;
4564  goto TERMINATE;
4565  }
4566  }
4567 
4568  if( SCIPisPresolveFinished(scip) )
4569  {
4570  /* try to tighten constraints by reducing the number of variables in the constraints using implications and
4571  * cliques, also derive fixations through them, @see SCIPshrinkDisjunctiveVarSet()
4572  */
4573  if( conshdlrdata->useimplications && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4574  {
4575  SCIP_CALL( shortenConss(scip, conshdlrdata, conshdlrdata->eventhdlr, conss, nconss,
4576  &entries, &nentries, nfixedvars, ndelconss, nchgcoefs, &cutoff) );
4577 
4578  if( cutoff )
4579  {
4580  *result = SCIP_CUTOFF;
4581  goto TERMINATE;
4582  }
4583  }
4584 
4585  /* check for redundant constraints due to negated clique information */
4586  if( conshdlrdata->usenegatedclique && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
4587  {
4588  SCIP_CALL( removeConstraintsDueToNegCliques(scip, conshdlr, conshdlrdata->conshdlrsetppc,
4589  conshdlrdata->eventhdlr, conss, nconss, &entries, &nentries, nfixedvars, ndelconss,
4590  nupgdconss, nchgcoefs, &cutoff) );
4591 
4592  if( cutoff )
4593  {
4594  *result = SCIP_CUTOFF;
4595  goto TERMINATE;
4596  }
4597  }
4598  }
4599  }
4600 
4601  TERMINATE:
4602 
4603  SCIPfreeBufferArray(scip, &entries);
4604 
4605  return SCIP_OKAY;
4606 }
4607 
4608 
4609 /** propagation conflict resolving method of constraint handler */
4610 static
4611 SCIP_DECL_CONSRESPROP(consRespropLogicor)
4612 { /*lint --e{715}*/
4613  SCIP_CONSDATA* consdata;
4614 #ifndef NDEBUG
4615  SCIP_Bool infervarfound;
4616 #endif
4617  int v;
4618 
4619  assert(conshdlr != NULL);
4620  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4621  assert(cons != NULL);
4622  assert(infervar != NULL);
4623  assert(result != NULL);
4624 
4625  consdata = SCIPconsGetData(cons);
4626  assert(consdata != NULL);
4627 
4628  SCIPdebugMsg(scip, "conflict resolving method of logic or constraint handler\n");
4629 
4630  /* the only deductions are variables infered to 1.0 on logic or constraints where all other variables
4631  * are assigned to zero
4632  */
4633  assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5); /* the inference variable must be assigned to one */
4634 
4635 #ifndef NDEBUG
4636  infervarfound = FALSE;
4637 #endif
4638  for( v = 0; v < consdata->nvars; ++v )
4639  {
4640  if( consdata->vars[v] != infervar )
4641  {
4642  /* the reason variable must have been assigned to zero */
4643  assert(SCIPgetVarUbAtIndex(scip, consdata->vars[v], bdchgidx, FALSE) < 0.5);
4644  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
4645  }
4646 #ifndef NDEBUG
4647  else
4648  {
4649  assert(!infervarfound);
4650  infervarfound = TRUE;
4651  }
4652 #endif
4653  }
4654  assert(infervarfound);
4655 
4656  *result = SCIP_SUCCESS;
4657 
4658  return SCIP_OKAY;
4659 }
4660 
4661 
4662 /** variable rounding lock method of constraint handler */
4663 static
4664 SCIP_DECL_CONSLOCK(consLockLogicor)
4665 { /*lint --e{715}*/
4666  SCIP_CONSDATA* consdata;
4667  int i;
4668 
4669  consdata = SCIPconsGetData(cons);
4670  assert(consdata != NULL);
4671 
4672  /* lock every single coefficient */
4673  for( i = 0; i < consdata->nvars; ++i )
4674  {
4675  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos, nlocksneg) );
4676  }
4677 
4678  return SCIP_OKAY;
4679 }
4680 
4681 
4682 /** constraint activation notification method of constraint handler */
4683 static
4684 SCIP_DECL_CONSACTIVE(consActiveLogicor)
4685 { /*lint --e{715}*/
4686  SCIP_CONSHDLRDATA* conshdlrdata;
4687  SCIP_CONSDATA* consdata;
4688 
4689  assert(conshdlr != NULL);
4690  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4691  assert(cons != NULL);
4692  assert(SCIPconsIsTransformed(cons));
4693 
4694  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4695  assert(conshdlrdata != NULL);
4696  consdata = SCIPconsGetData(cons);
4697  assert(consdata != NULL);
4698  assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
4699 
4700  SCIPdebugMsg(scip, "activating information for logic or constraint <%s>\n", SCIPconsGetName(cons));
4701  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
4702 
4703  /* catch events on watched variables */
4704  if( consdata->watchedvar1 != -1 )
4705  {
4706  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[consdata->watchedvar1],
4707  SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4708  &consdata->filterpos1) );
4709  }
4710  if( consdata->watchedvar2 != -1 )
4711  {
4712  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[consdata->watchedvar2],
4713  SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4714  &consdata->filterpos2) );
4715  }
4716 
4717  return SCIP_OKAY;
4718 }
4719 
4720 
4721 /** constraint deactivation notification method of constraint handler */
4722 static
4723 SCIP_DECL_CONSDEACTIVE(consDeactiveLogicor)
4724 { /*lint --e{715}*/
4725  SCIP_CONSHDLRDATA* conshdlrdata;
4726  SCIP_CONSDATA* consdata;
4727 
4728  assert(conshdlr != NULL);
4729  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4730  assert(cons != NULL);
4731  assert(SCIPconsIsTransformed(cons));
4732 
4733  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4734  assert(conshdlrdata != NULL);
4735  consdata = SCIPconsGetData(cons);
4736  assert(consdata != NULL);
4737  assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
4738 
4739  SCIPdebugMsg(scip, "deactivating information for logic or constraint <%s>\n", SCIPconsGetName(cons));
4740  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
4741 
4742  /* drop events on watched variables */
4743  if( consdata->watchedvar1 != -1 )
4744  {
4745  assert(consdata->filterpos1 != -1);
4746  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar1],
4747  SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4748  consdata->filterpos1) );
4749  }
4750  if( consdata->watchedvar2 != -1 )
4751  {
4752  assert(consdata->filterpos2 != -1);
4753  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar2],
4754  SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4755  consdata->filterpos2) );
4756  }
4757 
4758  return SCIP_OKAY;
4759 }
4760 
4761 
4762 /** constraint display method of constraint handler */
4763 static
4764 SCIP_DECL_CONSPRINT(consPrintLogicor)
4765 { /*lint --e{715}*/
4766  assert( scip != NULL );
4767  assert( conshdlr != NULL );
4768  assert( cons != NULL );
4769 
4770  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file, FALSE) );
4771 
4772  return SCIP_OKAY;
4773 }
4774 
4775 /** constraint copying method of constraint handler */
4776 static
4777 SCIP_DECL_CONSCOPY(consCopyLogicor)
4778 { /*lint --e{715}*/
4779  SCIP_VAR** sourcevars;
4780  const char* consname;
4781  int nvars;
4782 
4783  /* get variables and coefficients of the source constraint */
4784  sourcevars = SCIPgetVarsLogicor(sourcescip, sourcecons);
4785  nvars = SCIPgetNVarsLogicor(sourcescip, sourcecons);
4786 
4787  if( name != NULL )
4788  consname = name;
4789  else
4790  consname = SCIPconsGetName(sourcecons);
4791 
4792  /* copy the logic using the linear constraint copy method */
4793  SCIP_CALL( SCIPcopyConsLinear(scip, cons, sourcescip, consname, nvars, sourcevars, NULL,
4794  1.0, SCIPinfinity(scip), varmap, consmap,
4795  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
4796  assert(cons != NULL);
4797 
4798  return SCIP_OKAY;
4799 }
4800 
4801 /** constraint parsing method of constraint handler */
4802 static
4803 SCIP_DECL_CONSPARSE(consParseLogicor)
4804 { /*lint --e{715}*/
4805  SCIP_VAR** vars;
4806  char* strcopy;
4807  char* endptr;
4808  char* startptr;
4809  int requiredsize;
4810  int varssize;
4811  int nvars;
4812 
4813  SCIPdebugMsg(scip, "parse <%s> as logicor constraint\n", str);
4814 
4815  *success = FALSE;
4816 
4817  /* cutoff "logicor" from the constraint string */
4818  startptr = strchr((char*)str, '(');
4819 
4820  if( startptr == NULL )
4821  {
4822  SCIPerrorMessage("missing starting character '(' parsing logicor\n");
4823  return SCIP_OKAY;
4824  }
4825 
4826  /* skip '(' */
4827  ++startptr;
4828 
4829  /* find end character ')' */
4830  endptr = strrchr(startptr, ')');
4831 
4832  if( endptr == NULL )
4833  {
4834  SCIPerrorMessage("missing ending character ')' parsing logicor\n");
4835  return SCIP_OKAY;
4836  }
4837  assert(endptr >= startptr);
4838 
4839  if( endptr > startptr )
4840  {
4841  /* copy string for parsing */
4842  SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, startptr, (int)(endptr-startptr)) );
4843 
4844  varssize = 100;
4845  nvars = 0;
4846 
4847  /* allocate buffer array for variables */
4848  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
4849 
4850  /* parse string */
4851  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4852 
4853  if( *success )
4854  {
4855  /* check if the size of the variable array was great enough */
4856  if( varssize < requiredsize )
4857  {
4858  /* reallocate memory */
4859  varssize = requiredsize;
4860  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
4861 
4862  /* parse string again with the correct size of the variable array */
4863  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4864  }
4865 
4866  assert(*success);
4867  assert(varssize >= requiredsize);
4868 
4869  /* create logicor constraint */
4870  SCIP_CALL( SCIPcreateConsLogicor(scip, cons, name, nvars, vars,
4871  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4872  }
4873 
4874  /* free buffers */
4875  SCIPfreeBufferArray(scip, &vars);
4876  SCIPfreeBufferArray(scip, &strcopy);
4877  }
4878  else
4879  {
4880  if( !modifiable )
4881  {
4882  SCIPerrorMessage("cannot create empty logicor constraint\n");
4883  return SCIP_OKAY;
4884  }
4885 
4886  /* create empty logicor constraint */
4887  SCIP_CALL( SCIPcreateConsLogicor(scip, cons, name, 0, NULL,
4888  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4889 
4890  *success = TRUE;
4891  }
4892 
4893  return SCIP_OKAY;
4894 }
4895 
4896 /** constraint method of constraint handler which returns the variables (if possible) */
4897 static
4898 SCIP_DECL_CONSGETVARS(consGetVarsLogicor)
4899 { /*lint --e{715}*/
4900  SCIP_CONSDATA* consdata;
4901 
4902  consdata = SCIPconsGetData(cons);
4903  assert(consdata != NULL);
4904 
4905  if( varssize < consdata->nvars )
4906  (*success) = FALSE;
4907  else
4908  {
4909  assert(vars != NULL);
4910 
4911  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
4912  (*success) = TRUE;
4913  }
4914 
4915  return SCIP_OKAY;
4916 }
4917 
4918 /** constraint method of constraint handler which returns the number of variables (if possible) */
4919 static
4920 SCIP_DECL_CONSGETNVARS(consGetNVarsLogicor)
4921 { /*lint --e{715}*/
4922  SCIP_CONSDATA* consdata;
4923 
4924  consdata = SCIPconsGetData(cons);
4925  assert(consdata != NULL);
4926 
4927  (*nvars) = consdata->nvars;
4928  (*success) = TRUE;
4929 
4930  return SCIP_OKAY;
4931 }
4932 
4933 /*
4934  * Callback methods of event handler
4935  */
4936 
4937 static
4938 SCIP_DECL_EVENTEXEC(eventExecLogicor)
4939 { /*lint --e{715}*/
4940  assert(eventhdlr != NULL);
4941  assert(eventdata != NULL);
4942  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
4943  assert(event != NULL);
4944 
4945  SCIPdebugMsg(scip, "exec method of event handler for logic or constraints\n");
4946 
4948  {
4949  SCIPdebugMsg(scip, "enabling constraint cons <%s> at depth %d\n", SCIPconsGetName((SCIP_CONS*)eventdata), SCIPgetDepth(scip));
4950 
4951  SCIP_CALL( SCIPenableCons(scip, (SCIP_CONS*)eventdata) );
4952  SCIP_CALL( SCIPenableConsPropagation(scip, (SCIP_CONS*)eventdata) );
4953  }
4954  else if( SCIPeventGetType(event) == SCIP_EVENTTYPE_UBTIGHTENED )
4955  {
4956  SCIP_CALL( SCIPenableConsPropagation(scip, (SCIP_CONS*)eventdata) );
4957  }
4958 
4960  {
4961  SCIP_VAR* var = SCIPeventGetVar(event);
4962  SCIP_CONS* cons = (SCIP_CONS*)eventdata;
4963  SCIP_CONSDATA* consdata;
4964 
4965  assert(cons != NULL);
4966  consdata = SCIPconsGetData(cons);
4967  assert(consdata != NULL);
4968 
4969  /* we only catch this event in presolving stage */
4970  assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING);
4971  assert(var != NULL);
4972 
4973  consdata->presolved = FALSE;
4974 
4976  {
4977  if( SCIPconsIsActive(cons) )
4978  {
4979  if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 )
4980  consdata->merged = FALSE;
4981 
4982  if( !consdata->existmultaggr )
4983  {
4985  consdata->existmultaggr = TRUE;
4986  }
4987  }
4988  }
4989  }
4990 
4991  return SCIP_OKAY;
4992 }
4993 
4994 
4995 /*
4996  * Callback methods of conflict handler
4997  */
4998 
4999 static
5000 SCIP_DECL_CONFLICTEXEC(conflictExecLogicor)
5001 { /*lint --e{715}*/
5002  SCIP_VAR** vars;
5003  int i;
5004 
5005  assert(conflicthdlr != NULL);
5006  assert(strcmp(SCIPconflicthdlrGetName(conflicthdlr), CONFLICTHDLR_NAME) == 0);
5007  assert(bdchginfos != NULL || nbdchginfos == 0);
5008  assert(result != NULL);
5009 
5010  *result = SCIP_DIDNOTRUN;
5011 
5012  /* don't process already resolved conflicts */
5013  if( resolved )
5014  return SCIP_OKAY;
5015 
5016  /* if the conflict consists of only two (binary) variables, it will be handled by the setppc conflict handler */
5017  if( nbdchginfos == 2 )
5018  return SCIP_OKAY;
5019 
5020  *result = SCIP_DIDNOTFIND;
5021 
5022  /* create array of variables in conflict constraint */
5023  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nbdchginfos) );
5024  for( i = 0; i < nbdchginfos; ++i )
5025  {
5026  assert(bdchginfos != NULL); /* for flexelint */
5027  assert(bdchginfos[i] != NULL);
5028 
5029  vars[i] = SCIPbdchginfoGetVar(bdchginfos[i]);
5030 
5031  /* we can only treat binary variables */
5032  if( !SCIPvarIsBinary(vars[i]) )
5033  break;
5034 
5035  /* if the variable is fixed to one in the conflict set, we have to use its negation */
5036  if( SCIPbdchginfoGetNewbound(bdchginfos[i]) > 0.5 )
5037  {
5038  SCIP_CALL( SCIPgetNegatedVar(scip, vars[i], &vars[i]) );
5039  }
5040  }
5041 
5042  if( i == nbdchginfos )
5043  {
5044  SCIP_CONS* cons;
5045  char consname[SCIP_MAXSTRLEN];
5046 
5047  /* create a constraint out of the conflict set */
5049  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, consname, nbdchginfos, vars,
5050  FALSE, separate, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
5051 
5052  /* add conflict to SCIP */
5053  SCIP_CALL( SCIPaddConflict(scip, node, cons, validnode, conftype, cutoffinvolved) );
5054 
5055  *result = SCIP_CONSADDED;
5056  }
5057 
5058  /* free temporary memory */
5059  SCIPfreeBufferArray(scip, &vars);
5060 
5061  return SCIP_OKAY;
5062 }
5063 
5064 
5065 /*
5066  * constraint specific interface methods
5067  */
5068 
5069 /** creates the handler for logic or constraints and includes it in SCIP */
5071  SCIP* scip /**< SCIP data structure */
5072  )
5073 {
5074  SCIP_CONSHDLRDATA* conshdlrdata;
5075  SCIP_CONSHDLR* conshdlr;
5076  SCIP_CONFLICTHDLR* conflicthdlr;
5077  SCIP_EVENTHDLR* eventhdlr;
5078 
5079  /* create event handler for events on watched variables */
5081  eventExecLogicor, NULL) );
5082 
5083  /* create conflict handler for logic or constraints */
5085  conflictExecLogicor, NULL) );
5086 
5087  /* create constraint handler data */
5088  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
5089 
5090  /* include constraint handler */
5093  consEnfolpLogicor, consEnfopsLogicor, consCheckLogicor, consLockLogicor,
5094  conshdlrdata) );
5095  assert(conshdlr != NULL);
5096 
5097  /* set non-fundamental callbacks via specific setter functions */
5098  SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveLogicor) );
5099  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyLogicor, consCopyLogicor) );
5100  SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveLogicor) );
5101  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteLogicor) );
5102  SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreLogicor) );
5103  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolLogicor) );
5104  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeLogicor) );
5105  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsLogicor) );
5106  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsLogicor) );
5107  SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreLogicor) );
5108  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpLogicor) );
5109  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseLogicor) );
5110  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolLogicor,CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
5111  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintLogicor) );
5112  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropLogicor, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
5114  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropLogicor) );
5115  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpLogicor, consSepasolLogicor, CONSHDLR_SEPAFREQ,
5117  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransLogicor) );
5118  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxLogicor) );
5119 
5120  conshdlrdata->conshdlrlinear = SCIPfindConshdlr(scip, "linear");
5121  conshdlrdata->conshdlrsetppc = SCIPfindConshdlr(scip, "setppc");
5122 
5123  if( conshdlrdata->conshdlrlinear != NULL )
5124  {
5125  /* include the linear constraint to logicor constraint upgrade in the linear constraint handler */
5127  }
5128 
5129  /* logic or constraint handler parameters */
5131  "constraints/logicor/presolpairwise",
5132  "should pairwise constraint comparison be performed in presolving?",
5133  &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
5135  "constraints/logicor/presolusehashing",
5136  "should hash table be used for detecting redundant constraints in advance",
5137  &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
5139  "constraints/logicor/dualpresolving",
5140  "should dual presolving steps be performed?",
5141  &conshdlrdata->dualpresolving, TRUE, DEFAULT_DUALPRESOLVING, NULL, NULL) );
5143  "constraints/logicor/negatedclique",
5144  "should negated clique information be used in presolving",
5145  &conshdlrdata->usenegatedclique, TRUE, DEFAULT_NEGATEDCLIQUE, NULL, NULL) );
5147  "constraints/logicor/implications",
5148  "should implications/cliques be used in presolving",
5149  &conshdlrdata->useimplications, TRUE, DEFAULT_IMPLICATIONS, NULL, NULL) );
5151  "constraints/logicor/strengthen",
5152  "should pairwise constraint comparison try to strengthen constraints by removing superflous non-zeros?",
5153  &conshdlrdata->usestrengthening, TRUE, DEFAULT_STRENGTHEN, NULL, NULL) );
5154 
5155  return SCIP_OKAY;
5156 }
5157 
5158 
5159 /** creates and captures a logic or constraint
5160  *
5161  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5162  */
5164  SCIP* scip, /**< SCIP data structure */
5165  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5166  const char* name, /**< name of constraint */
5167  int nvars, /**< number of variables in the constraint */
5168  SCIP_VAR** vars, /**< array with variables of constraint entries */
5169  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5170  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5171  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5172  * Usually set to TRUE. */
5173  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5174  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5175  SCIP_Bool check, /**< should the constraint be checked for feasibility?
5176  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5177  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5178  * Usually set to TRUE. */
5179  SCIP_Bool local, /**< is constraint only valid locally?
5180  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5181  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5182  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5183  * adds coefficients to this constraint. */
5184  SCIP_Bool dynamic, /**< is constraint subject to aging?
5185  * Usually set to FALSE. Set to TRUE for own cuts which
5186  * are separated as constraints. */
5187  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5188  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5189  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5190  * if it may be moved to a more global node?
5191  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5192  )
5193 {
5194  SCIP_CONSHDLR* conshdlr;
5195  SCIP_CONSDATA* consdata;
5196 
5197  assert(scip != NULL);
5198 
5199  /* find the logicor constraint handler */
5200  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5201  if( conshdlr == NULL )
5202  {
5203  SCIPerrorMessage("logic or constraint handler not found\n");
5204  return SCIP_INVALIDCALL;
5205  }
5206 
5207  /* create the constraint specific data */
5208  SCIP_CALL( consdataCreate(scip, &consdata, nvars, vars) );
5209 
5210  /* create constraint */
5211  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5212  local, modifiable, dynamic, removable, stickingatnode) );
5213 
5214  if( SCIPisTransformed(scip) && SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
5215  {
5216  SCIP_CONSHDLRDATA* conshdlrdata;
5217  int v;
5218 
5219  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5220  assert(conshdlrdata != NULL);
5221 
5222  for( v = consdata->nvars - 1; v >= 0; --v )
5223  {
5224  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
5225  (SCIP_EVENTDATA*)(*cons), NULL) );
5226  }
5227  }
5228 
5229  return SCIP_OKAY;
5230 }
5231 
5232 /** creates and captures a logicor constraint
5233  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
5234  * method SCIPcreateConsLogicor(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
5235  *
5236  * @see SCIPcreateConsLogicor() for information about the basic constraint flag configuration
5237  *
5238  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5239  */
5241  SCIP* scip, /**< SCIP data structure */
5242  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5243  const char* name, /**< name of constraint */
5244  int nvars, /**< number of variables in the constraint */
5245  SCIP_VAR** vars /**< array with variables of constraint entries */
5246  )
5247 {
5248  assert(scip != NULL);
5249 
5250  SCIP_CALL( SCIPcreateConsLogicor(scip, cons, name, nvars, vars,
5251  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
5252 
5253  return SCIP_OKAY;
5254 }
5255 
5256 /** adds coefficient in logic or constraint */
5258  SCIP* scip, /**< SCIP data structure */
5259  SCIP_CONS* cons, /**< logicor constraint */
5260  SCIP_VAR* var /**< variable to add to the constraint */
5261  )
5262 {
5263  assert(var != NULL);
5264 
5265  /*debugMsg(scip, "adding variable <%s> to logicor constraint <%s>\n",
5266  SCIPvarGetName(var), SCIPconsGetName(cons));*/
5267 
5268  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5269  {
5270  SCIPerrorMessage("constraint is not a logic or constraint\n");
5271  return SCIP_INVALIDDATA;
5272  }
5273 
5274  SCIP_CALL( addCoef(scip, cons, var) );
5275 
5276  return SCIP_OKAY;
5277 }
5278 
5279 /** gets number of variables in logic or constraint */
5281  SCIP* scip, /**< SCIP data structure */
5282  SCIP_CONS* cons /**< constraint data */
5283  )
5284 {
5285  SCIP_CONSDATA* consdata;
5286 
5287  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5288  {
5289  SCIPerrorMessage("constraint is not a logic or constraint\n");
5290  SCIPABORT();
5291  return -1; /*lint !e527*/
5292  }
5293 
5294  consdata = SCIPconsGetData(cons);
5295  assert(consdata != NULL);
5296 
5297  return consdata->nvars;
5298 }
5299 
5300 /** gets array of variables in logic or constraint */
5302  SCIP* scip, /**< SCIP data structure */
5303  SCIP_CONS* cons /**< constraint data */
5304  )
5305 {
5306  SCIP_CONSDATA* consdata;
5307 
5308  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5309  {
5310  SCIPerrorMessage("constraint is not a logic or constraint\n");
5311  SCIPABORT();
5312  return NULL; /*lint !e527*/
5313  }
5314 
5315  consdata = SCIPconsGetData(cons);
5316  assert(consdata != NULL);
5317 
5318  return consdata->vars;
5319 }
5320 
5321 /** gets the dual solution of the logic or constraint in the current LP */
5323  SCIP* scip, /**< SCIP data structure */
5324  SCIP_CONS* cons /**< constraint data */
5325  )
5326 {
5327  SCIP_CONSDATA* consdata;
5328 
5329  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5330  {
5331  SCIPerrorMessage("constraint is not a logic or constraint\n");
5332  SCIPABORT();
5333  return SCIP_INVALID; /*lint !e527*/
5334  }
5335 
5336  consdata = SCIPconsGetData(cons);
5337  assert(consdata != NULL);
5338 
5339  if( consdata->row != NULL )
5340  return SCIProwGetDualsol(consdata->row);
5341  else
5342  return 0.0;
5343 }
5344 
5345 /** gets the dual Farkas value of the logic or constraint in the current infeasible LP */
5347  SCIP* scip, /**< SCIP data structure */
5348  SCIP_CONS* cons /**< constraint data */
5349  )
5350 {
5351  SCIP_CONSDATA* consdata;
5352 
5353  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5354  {
5355  SCIPerrorMessage("constraint is not a logic or constraint\n");
5356  SCIPABORT();
5357  return SCIP_INVALID; /*lint !e527*/
5358  }
5359 
5360  consdata = SCIPconsGetData(cons);
5361  assert(consdata != NULL);
5362 
5363  if( consdata->row != NULL )
5364  return SCIProwGetDualfarkas(consdata->row);
5365  else
5366  return 0.0;
5367 }
5368 
5369 /** returns the linear relaxation of the given logic or constraint; may return NULL if no LP row was yet created;
5370  * the user must not modify the row!
5371  */
5373  SCIP* scip, /**< SCIP data structure */
5374  SCIP_CONS* cons /**< constraint data */
5375  )
5376 {
5377  SCIP_CONSDATA* consdata;
5378 
5379  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5380  {
5381  SCIPerrorMessage("constraint is not a logic or constraint\n");
5382  SCIPABORT();
5383  return NULL; /*lint !e527*/
5384  }
5385 
5386  consdata = SCIPconsGetData(cons);
5387  assert(consdata != NULL);
5388 
5389  return consdata->row;
5390 }
5391 
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition: scip_lp.c:1674
SCIP_RETCODE SCIPaddCoefLogicor(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4221
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2134
static SCIP_DECL_CONSCHECK(consCheckLogicor)
SCIP_RETCODE SCIPaddConsAge(SCIP *scip, SCIP_CONS *cons, SCIP_Real deltaage)
Definition: scip_cons.c:1769
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:105
static SCIP_DECL_CONSPRESOL(consPresolLogicor)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:640
#define DEFAULT_PRESOLUSEHASHING
Definition: cons_logicor.c:88
static SCIP_RETCODE removeRedundantCons(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1, int *ndelconss)
#define NULL
Definition: def.h:239
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:10958
#define DEFAULT_PRESOLPAIRWISE
Definition: cons_logicor.c:84
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2130
#define CONSHDLR_DELAYSEPA
Definition: cons_logicor.c:68
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3176
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:412
#define SCIP_EVENTTYPE_VARFIXED
Definition: type_event.h:58
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8335
static SCIP_DECL_CONSINITLP(consInitlpLogicor)
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:663
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE enforcePseudo(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, SCIP_Bool *infeasible, SCIP_Bool *reduceddom, SCIP_Bool *solvelp)
#define CONSHDLR_NEEDSCONS
Definition: cons_logicor.c:70
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1994
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2265
int SCIPconsGetValidDepth(SCIP_CONS *cons)
Definition: cons.c:8159
public methods for memory management
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:422
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:954
SCIP_VAR * SCIPbdchginfoGetVar(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:17945
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:893
SCIP_RETCODE SCIPcopyConsLinear(SCIP *scip, SCIP_CONS **cons, SCIP *sourcescip, const char *name, int nvars, SCIP_VAR **sourcevars, SCIP_Real *sourcecoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, 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_Bool global, SCIP_Bool *valid)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:11789
#define SCIP_MAXSTRLEN
Definition: def.h:260
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3233
public methods for conflict handler plugins and conflict analysis
static SCIP_DECL_CONSEXITPRE(consExitpreLogicor)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:385
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1826
static SCIP_DECL_CONSPRINT(consPrintLogicor)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2895
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:210
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1602
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
Definition: cons_logicor.c:323
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_CONFLICTEXEC(conflictExecLogicor)
SCIP_RETCODE SCIPdisableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1995
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:755
SCIP_Bool SCIPconsIsAdded(SCIP_CONS *cons)
Definition: cons.c:8505
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:172
static SCIP_RETCODE removeConstraintsDueToNegCliques(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLR *conshdlrsetppc, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS **conss, int nconss, unsigned char **entries, int *nentries, int *nfixedvars, int *ndelconss, int *nupgdconss, int *nchgcoefs, SCIP_Bool *cutoff)
static SCIP_DECL_SORTPTRCOMP(conssLogicorComp)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1442
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip_cons.c:1538
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16909
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:554
static SCIP_RETCODE disableCons(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
static SCIP_DECL_CONSDEACTIVE(consDeactiveLogicor)
static SCIP_DECL_EVENTEXEC(eventExecLogicor)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_logicor.c:521
#define CONSHDLR_DELAYPROP
Definition: cons_logicor.c:69
#define FALSE
Definition: def.h:65
int SCIPconsGetPos(SCIP_CONS *cons)
Definition: cons.c:8086
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:314
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10325
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:243
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:64
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8355
#define SCIP_PRESOLTIMING_EXHAUSTIVE
Definition: type_timing.h:45
#define LINCONSUPGD_PRIORITY
Definition: cons_logicor.c:75
static unsigned int calcSignature(SCIP_VAR **vars, int nvars)
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17036
static SCIP_DECL_CONSEXITSOL(consExitsolLogicor)
static SCIP_DECL_CONSSEPALP(consSepalpLogicor)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8385
public methods for problem variables
#define CONSHDLR_SEPAFREQ
Definition: cons_logicor.c:62
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
SCIP_RETCODE SCIPenableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1965
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:297
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
#define CONSHDLR_NAME
Definition: cons_logicor.c:57
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, int *firstchange, int *ndelconss)
#define SCIP_LONGINT_MAX
Definition: def.h:136
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
SCIP_Longint SCIPvarGetNBranchingsCurrentRun(SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: var.c:15217
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:611
public methods for SCIP variables
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17169
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8345
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:686
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:16889
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:203
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1483
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:870
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8137
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17695
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2224
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:1011
static SCIP_DECL_HASHGETKEY(hashGetKeyLogicorcons)
static SCIP_RETCODE switchWatchedvars(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
Definition: cons_logicor.c:380
static SCIP_RETCODE addCut(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
static void consdataCalcSignature(SCIP_CONSDATA *consdata)
#define AGEINCREASE(n)
Definition: cons_logicor.c:97
public methods for numerical tolerances
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2014
static SCIP_RETCODE conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_logicor.c:216
public methods for querying solving statistics
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17159
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17080
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3025
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4199
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:64
static SCIP_RETCODE shortenConss(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS **conss, int nconss, unsigned char **entries, int *nentries, int *nfixedvars, int *ndelconss, int *nchgcoefs, SCIP_Bool *cutoff)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons)
public methods for the branch-and-bound tree
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:148
SCIP_RETCODE SCIPenableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1851
SCIP_Real SCIPgetDualsolLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddClique(SCIP *scip, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6819
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17353
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11697
static void removeConsFromOccurList(SCIP_CONS *cons, SCIP_HASHMAP *varstopos, SCIP_CONS ***occurlist, int *noccurlistentries, int occurlistlength)
SCIP_VAR * w
Definition: circlepacking.c:58
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:111
static SCIP_DECL_HASHKEYVAL(hashKeyValLogicorcons)
public methods for managing constraints
SCIP_RETCODE SCIPparseVarsList(SCIP *scip, const char *str, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize, char **endptr, char delimiter, SCIP_Bool *success)
Definition: scip_var.c:600
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
Definition: scip_general.c:648
#define DEFAULT_DUALPRESOLVING
Definition: cons_logicor.c:89
static SCIP_DECL_CONSACTIVE(consActiveLogicor)
#define SCIP_PRESOLTIMING_MEDIUM
Definition: type_timing.h:44
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:409
static SCIP_DECL_CONSDELETE(consDeleteLogicor)
#define EVENTHDLR_DESC
Definition: cons_logicor.c:78
static SCIP_RETCODE prepareCons(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, unsigned char **entries, int *nentries, SCIP_Bool *redundant, int *nfixedvars, int *nchgcoefs, int *ndelconss, SCIP_Bool *cutoff)
static SCIP_DECL_CONSLOCK(consLockLogicor)
static SCIP_DECL_LINCONSUPGD(linconsUpgdLogicor)
SCIP_RETCODE SCIPgetBinvarRepresentatives(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **repvars, SCIP_Bool *negated)
Definition: scip_var.c:1647
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_ENFOPRIORITY
Definition: cons_logicor.c:60
static SCIP_DECL_CONSTRANS(consTransLogicor)
public methods for event handler plugins and event handlers
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
static SCIP_DECL_CONSRESPROP(consRespropLogicor)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:143
static SCIP_DECL_HASHKEYEQ(hashKeyEqLogicorcons)
static SCIP_RETCODE fixDeleteOrUpgradeCons(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_CONSHDLR *conshdlrlinear, SCIP_CONSHDLR *conshdlrsetppc, int *nfixedvars, int *nchgbds, int *nchgcoefs, int *ndelconss, int *naddconss, int *nupgdconss, SCIP_Bool *cutoff)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:128
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4375
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8076
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8295
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
static SCIP_RETCODE removeRedundantConssAndNonzeros(SCIP *scip, SCIP_CONS **conss, int nconss, unsigned char **entries, int *nentries, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool usestrengthening, int *firstchange, int *nfixedvars, int *ndelconss, int *nchgcoefs, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:434
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
#define EVENTHDLR_NAME
Definition: cons_logicor.c:77
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4211
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_logicor.c:178
static SCIP_RETCODE addConsToOccurList(SCIP *scip, SCIP_CONS *cons, SCIP_HASHMAP *varstopos, SCIP_CONS ***occurlist, int *noccurlistentries, int *occurlistsizes, int *occurlistlength, int occurlistsize)
SCIP_RETCODE SCIPcreateConsBasicLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPvarGetAggregatedObj(SCIP_VAR *var, SCIP_Real *aggrobj)
Definition: var.c:17213
#define SCIP_CALL(x)
Definition: def.h:351
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:474
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1740
#define CONFLICTHDLR_NAME
Definition: cons_logicor.c:80
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:334
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_ROW * SCIPgetRowLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: grphload.c:88
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8315
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num)
Definition: cons_logicor.c:231
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *redundant, int *nchgcoefs, int *naddconss, int *ndelconss)
Definition: cons_logicor.c:858
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:294
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:709
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:51
SCIP_RETCODE SCIPdisableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1885
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:141
public methods for constraint handler plugins and constraints
methods commonly used for presolving
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:9114
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file, SCIP_Bool endline)
Definition: cons_logicor.c:354
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
public data structures and miscellaneous methods
static SCIP_DECL_CONSGETVARS(consGetVarsLogicor)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1018
#define CONFLICTHDLR_DESC
Definition: cons_logicor.c:81
#define SCIP_Bool
Definition: def.h:62
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2179
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
static SCIP_DECL_CONSENFOLP(consEnfolpLogicor)
static SCIP_RETCODE createNormalizedLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, int mult, 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_DECL_CONSENFOPS(consEnfopsLogicor)
SCIP_Bool SCIPconsIsPropagationEnabled(SCIP_CONS *cons)
Definition: cons.c:8194
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1336
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:715
static void consdataSort(SCIP_CONSDATA *consdata)
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17621
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2550
#define CONSHDLR_MAXPREROUNDS
Definition: cons_logicor.c:67
#define MAX_CONSLENGTH
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8096
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11422
public methods for LP management
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8205
public methods for cuts and aggregation rows
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8245
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17191
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:468
SCIP_Real SCIPbdchginfoGetNewbound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:17935
#define MAXCOMPARISONS
static SCIP_DECL_CONSCOPY(consCopyLogicor)
Definition:<