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-2019 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  /* coverity[swapped_arguments] */
1992  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
1993 
1994  /* delete consdel */
1995  SCIP_CALL( SCIPdelCons(scip, cons0) );
1996  (*ndelconss)++;
1997 
1998  /* update the first changed constraint to begin the next aggregation round with */
1999  if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
2000  *firstchange = SCIPconsGetPos(cons1);
2001 
2002  assert(SCIPconsIsActive(cons1));
2003  }
2004  else
2005  {
2006  /* no such constraint in current hash table: insert cons0 into hash table */
2007  SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
2008  }
2009  }
2010 
2011  /* free hash table */
2012  SCIPhashtableFree(&hashtable);
2013 
2014  return SCIP_OKAY;
2015 }
2016 
2017 /** removes the redundant second constraint and updates the flags of the first one */
2018 static
2020  SCIP* scip, /**< SCIP data structure */
2021  SCIP_CONS* cons0, /**< constraint that should stay */
2022  SCIP_CONS* cons1, /**< constraint that should be deleted */
2023  int* ndelconss /**< pointer to count number of deleted constraints */
2024  )
2025 {
2026  assert(ndelconss != NULL);
2027 
2028  SCIPdebugMsg(scip, " -> removing logicor constraint <%s> which is redundant to <%s>\n",
2029  SCIPconsGetName(cons1), SCIPconsGetName(cons0));
2030  SCIPdebugPrintCons(scip, cons0, NULL);
2031  SCIPdebugPrintCons(scip, cons1, NULL);
2032 
2033  /* update flags of cons0 */
2034  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
2035 
2036  /* delete cons1 */
2037  SCIP_CALL( SCIPdelCons(scip, cons1) );
2038  (*ndelconss)++;
2039 
2040  return SCIP_OKAY;
2041 }
2042 
2043 
2044 /** compute and return a signature for given variables */
2045 static
2046 unsigned int calcSignature(
2047  SCIP_VAR** vars, /**< variables to calculate the signature for */
2048  int nvars /**< number of variables to calculate the signature for */
2049  )
2050 {
2051  unsigned int signature = 0;
2052  int v;
2053 
2054  assert(vars != NULL);
2055  assert(nvars >= 1);
2056 
2057  for( v = nvars - 1; v >= 0; --v )
2058  {
2059  signature |= ((unsigned int)1 << ((unsigned int)SCIPvarGetIndex(vars[v]) % (sizeof(unsigned int) * 8)));
2060  }
2061 
2062  return signature;
2063 }
2064 
2065 /** compute the constraint signature which is used to detect constraints, that contain potentially the same set of
2066  * variables
2067  */
2068 static
2070  SCIP_CONSDATA* consdata /**< logicor constraint data */
2071  )
2072 {
2073  if( consdata->validsignature )
2074  return;
2075 
2076  consdata->signature = calcSignature(consdata->vars, consdata->nvars);
2077  consdata->validsignature = TRUE;
2078 }
2079 
2080 /** remove a constraint from the column representation */
2081 static
2083  SCIP_CONS* cons, /**< logicor constraint */
2084  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2085  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2086  int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2087  int occurlistlength /**< number of columns in the occurlist */
2088  )
2089 {
2090  SCIP_VAR** vars;
2091  SCIP_VAR* var;
2092  SCIP_CONSDATA* consdata;
2093  int nvars;
2094  int pos;
2095  int v;
2096  int l;
2097 
2098  assert(cons != NULL);
2099  assert(SCIPconsIsActive(cons));
2100  assert(varstopos != NULL);
2101  assert(occurlist != NULL);
2102  assert(noccurlistentries != NULL);
2103 
2104  consdata = SCIPconsGetData(cons);
2105  assert(consdata != NULL);
2106 
2107  nvars = consdata->nvars;
2108  assert(nvars >= 1);
2109  vars = consdata->vars;
2110  assert(vars != NULL);
2111 
2112  /* remove constraint from list */
2113  for( v = nvars - 1; v >= 0; --v )
2114  {
2115  var = vars[v];
2116 
2117  assert(SCIPhashmapExists(varstopos, (void*) var));
2118 
2119  pos = SCIPhashmapGetImageInt(varstopos, (void*)var);
2120  assert(0 < pos && pos <= occurlistlength);
2121 
2122  --pos;
2123 
2124  /* remove for each variable one corresponding entry */
2125  for( l = noccurlistentries[pos] - 1; l >= 0; --l )
2126  {
2127  if( occurlist[pos][l] == cons )
2128  {
2129  --noccurlistentries[pos];
2130  assert(noccurlistentries[pos] >= 0);
2131 
2132  occurlist[pos][l] = occurlist[pos][noccurlistentries[pos]];
2133  break;
2134  }
2135  }
2136  assert(l >= 0);
2137  }
2138 }
2139 
2140 /** determine shortest constraint list in column representation */
2141 static
2143  SCIP_VAR** vars, /**< variables to find the shortestlist for */
2144  int nvars, /**< number of variables */
2145  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2146  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2147  int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2148  int occurlistlength, /**< number of columns in the occurlist */
2149  int* nentries, /**< pointer to store the number of entries in the shortest list */
2150  SCIP_CONS*** shortestlist /**< pointer to store smallest array with constraints */
2151  )
2152 {
2153  SCIP_VAR* var;
2154  int pos;
2155  int v;
2156 
2157  assert(vars != 0);
2158  assert(nvars >= 1);
2159  assert(varstopos != NULL);
2160  assert(occurlist != NULL);
2161  assert(noccurlistentries != NULL);
2162  assert(nentries != NULL);
2163  assert(shortestlist != NULL);
2164 
2165  *nentries = INT_MAX;
2166  *shortestlist = NULL;
2167 
2168  /* find the shortest list */
2169  for( v = nvars - 1; v >= 0; --v )
2170  {
2171  var = vars[v];
2172  assert(var != NULL);
2173 
2174  /* it might be that a variable is not yet put into the occurlist, then this constraint cannot cover another */
2175  if( !SCIPhashmapExists(varstopos, (void*) var) )
2176  {
2177  *nentries = 0;
2178  return;
2179  }
2180 
2181  pos = SCIPhashmapGetImageInt(varstopos, (void*)var);
2182  assert(0 < pos && pos <= occurlistlength);
2183 
2184  --pos;
2185 
2186  /* remember the shortest list */
2187  if( noccurlistentries[pos] < *nentries )
2188  {
2189  *nentries = noccurlistentries[pos];
2190  *shortestlist = occurlist[pos];
2191  }
2192  }
2193 }
2194 
2195 /** run a pairwise comparison for detecting subset-constraints of other constraint while using a signature */
2196 static
2198  SCIP* scip, /**< SCIP data structure */
2199  SCIP_CONS* cons, /**< logicor constraint to check if it covers another */
2200  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2201  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2202  int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2203  int occurlistlength, /**< number of columns in the occurlist */
2204  int* ndelconss /**< pointer to store the number of deleted constraints */
2205  )
2206 {
2207  SCIP_CONS** shortestlist;
2208  SCIP_VAR** vars;
2209  SCIP_CONS* cons1;
2210  SCIP_VAR* var;
2211  SCIP_CONSDATA* consdata;
2212  int nentries;
2213  int c;
2214  int v;
2215 
2216  assert(scip != NULL);
2217  assert(cons != NULL);
2218  assert(SCIPconsIsActive(cons));
2219  assert(!SCIPconsIsModifiable(cons));
2220  assert(varstopos != NULL);
2221  assert(occurlist != NULL);
2222  assert(noccurlistentries != NULL);
2223  assert(ndelconss != NULL);
2224 
2225  consdata = SCIPconsGetData(cons);
2226  assert(consdata != NULL);
2227  assert(consdata->nvars > 1);
2228  assert(consdata->validsignature);
2229  assert(consdata->sorted);
2230 
2231  vars = consdata->vars;
2232  assert(vars != NULL);
2233 
2234  /* determine shortest column */
2235  findShortestOccurlist(vars, consdata->nvars, varstopos, occurlist, noccurlistentries, occurlistlength, &nentries, &shortestlist);
2236 
2237  /* one variable which does not appear in the column representation anymore */
2238  if( nentries == 0 )
2239  return SCIP_OKAY;
2240 
2241  assert(shortestlist != NULL);
2242  assert(0 < nentries);
2243 
2244  /* check all constraints in the shortest list for coverage */
2245  for( c = nentries - 1; c >= 0; --c )
2246  {
2247  cons1 = shortestlist[c];
2248  assert(cons1 != NULL);
2249  assert(!SCIPconsIsModifiable(cons1));
2250  assert(SCIPconsIsActive(cons1));
2251 
2252  if( cons != cons1 )
2253  {
2254  SCIP_CONSDATA* consdata1 = SCIPconsGetData(cons1);
2255  assert(consdata1 != NULL);
2256  assert(consdata1->nvars >= consdata->nvars);
2257 
2258  /* constraints with the same length cannot be covered and same constraints are removed in
2259  * detectRedundantConstraints()
2260  */
2261  if( consdata1->nvars == consdata->nvars )
2262  continue;
2263 
2264  assert(consdata->validsignature);
2265  assert(consdata->sorted);
2266  assert(consdata1->validsignature);
2267  assert(consdata1->sorted);
2268 
2269  if( (consdata->signature & (~consdata1->signature)) == 0 )
2270  {
2271  SCIP_VAR* var1;
2272  int v1;
2273 
2274  v = 0;
2275  v1 = 0;
2276 
2277  while( v < consdata->nvars && v1 < consdata1->nvars )
2278  {
2279  int comp;
2280 
2281  var = vars[v];
2282  var1 = consdata1->vars[v1];
2283 
2284  comp = SCIPvarCompare(var, var1);
2285 
2286  if( comp == 0 )
2287  {
2288  ++v;
2289  ++v1;
2290  }
2291  else if( comp > 0 )
2292  ++v1;
2293  else
2294  break;
2295  }
2296 
2297  /* cons1 is covered by cons */
2298  if( v == consdata->nvars )
2299  {
2300  /* remove cons1 from columns representation */
2301  removeConsFromOccurList(cons1, varstopos, occurlist, noccurlistentries, occurlistlength);
2302 
2303  /* delete redundant constraint and update constraint flags if necessary */
2304  SCIP_CALL( removeRedundantCons(scip, cons, cons1, ndelconss) );
2305  }
2306  }
2307  }
2308  }
2309 
2310  return SCIP_OKAY;
2311 }
2312 
2313 /** compararer for sorting constraints after their number of variables */
2314 static
2315 SCIP_DECL_SORTPTRCOMP(conssLogicorComp)
2316 {
2317  SCIP_CONSDATA* consdata1;
2318  SCIP_CONSDATA* consdata2;
2319 
2320  assert(elem1 != NULL);
2321  assert(elem2 != NULL);
2322 
2323  consdata1 = SCIPconsGetData((SCIP_CONS*) elem1);
2324  consdata2 = SCIPconsGetData((SCIP_CONS*) elem2);
2325 
2326  assert(consdata1 != NULL);
2327  assert(consdata2 != NULL);
2328 
2329  return consdata1->nvars - consdata2->nvars;
2330 }
2331 
2332 /** add a constraint to the column representation */
2333 static
2335  SCIP* scip, /**< SCIP data structure */
2336  SCIP_CONS* cons, /**< logicor constraint */
2337  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2338  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2339  int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2340  int* occurlistsizes, /**< array of sizes for each variable in the occurlist */
2341  int* occurlistlength, /**< number of columns in the occurlist */
2342  int occurlistsize /**< size of occurlist */
2343  )
2344 {
2345  SCIP_VAR** vars;
2346  SCIP_VAR* var;
2347  SCIP_CONSDATA* consdata;
2348  int pos;
2349  int v;
2350 
2351  assert(scip != NULL);
2352  assert(cons != NULL);
2353  assert(SCIPconsIsActive(cons));
2354  assert(varstopos != NULL);
2355  assert(occurlist != NULL);
2356  assert(noccurlistentries != NULL);
2357  assert(occurlistsizes != NULL);
2358  assert(occurlistlength != NULL);
2359  assert(*occurlistlength <= occurlistsize);
2360 
2361  consdata = SCIPconsGetData(cons);
2362  assert(consdata != NULL);
2363  assert(consdata->nvars > 1);
2364 
2365  vars = consdata->vars;
2366  assert(vars != NULL);
2367 
2368  for( v = consdata->nvars - 1; v >= 0; --v )
2369  {
2370  var = vars[v];
2371  assert(var != NULL);
2373 
2374  /* check if the variable is not yet put into the occurlist */
2375  if( !SCIPhashmapExists(varstopos, (void*) var) )
2376  {
2377  pos = *occurlistlength;
2378  assert(pos <= occurlistsize);
2379 
2380  /* occurlist values need to be clear */
2381  assert(occurlist[pos] == NULL);
2382  assert(noccurlistentries[pos] == 0);
2383  assert(occurlistsizes[pos] == 0);
2384 
2385  /* allocate memory */
2387  occurlistsizes[pos] = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) + 1;
2388  SCIP_CALL( SCIPallocBufferArray(scip, &(occurlist[pos]), occurlistsizes[pos]) ); /*lint !e866*/
2389 
2390  /* put constraint in list of current variable */
2391  occurlist[pos][noccurlistentries[pos]] = cons;
2392  ++(noccurlistentries[pos]);
2393 
2394  /* add new variable to map */
2395  SCIP_CALL( SCIPhashmapInsertInt(varstopos, var, pos + 1) );
2396 
2397  ++(*occurlistlength);
2398  }
2399  else
2400  {
2401  pos = SCIPhashmapGetImageInt(varstopos, (void*)var);
2402  assert(0 < pos && pos <= *occurlistlength);
2403 
2404  --pos;
2405 
2406  assert(occurlist[pos] != NULL);
2407  assert(occurlistsizes[pos] > 0);
2408 
2409  /* do we need to resize the array */
2410  if( noccurlistentries[pos] == occurlistsizes[pos] )
2411  {
2412  occurlistsizes[pos] = SCIPcalcMemGrowSize(scip, occurlistsizes[pos] + 1);
2413  assert(occurlistsizes[pos] > noccurlistentries[pos] && occurlistsizes[pos] < INT_MAX);
2414 
2415  /* resize occurlist for current variable */
2416  SCIP_CALL( SCIPreallocBufferArray(scip, &(occurlist[pos]), occurlistsizes[pos]) ); /*lint !e866*/
2417  }
2418  assert(noccurlistentries[pos] < occurlistsizes[pos]);
2419 
2420  /* put constraint in list of current variable */
2421  occurlist[pos][noccurlistentries[pos]] = cons;
2422  ++(noccurlistentries[pos]);
2423  }
2424  }
2425 
2426  return SCIP_OKAY;
2427 }
2428 
2429 /** run a pairwise comparison for the given variables against all constraits to detect redundant non-zeros in these
2430  * constraints
2431  */
2432 static
2434  SCIP* scip, /**< SCIP data structure */
2435  SCIP_CONS* cons, /**< logicor constraint to check if it covers another */
2436  SCIP_VAR* artvar, /**< artificial negated variable of constraint */
2437  int artpos, /**< position to replace constraint variable with artvar */
2438  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2439  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2440  int* noccurlistentries, /**< number of constraints for each variable in the occurlist */
2441  int occurlistlength, /**< number of columns in the occurlist */
2442  SCIP_EVENTHDLR* eventhdlr, /**< event handler */
2443  int* nchgcoefs, /**< pointer to store the number of deleted non-zeros */
2444  SCIP_Bool* deleted /**< pointer to store if cons will be deleted */
2445  )
2446 {
2447  SCIP_CONS** shortestlist;
2448  SCIP_VAR** vars;
2449  SCIP_CONS* cons1;
2450  SCIP_VAR* oldvar;
2451  SCIP_VAR* var;
2452  SCIP_CONSDATA* consdata;
2453  unsigned int signature;
2454  int nentries;
2455  int nvars;
2456  int c;
2457  int v;
2458  int pos;
2459 
2460  assert(scip != NULL);
2461  assert(cons != NULL);
2462  assert(artvar != NULL);
2463  assert(SCIPconsIsActive(cons));
2464  assert(!SCIPconsIsModifiable(cons));
2465  assert(varstopos != NULL);
2466  assert(SCIPhashmapExists(varstopos, (void*) artvar));
2467  assert(occurlist != NULL);
2468  assert(noccurlistentries != NULL);
2469  assert(nchgcoefs != NULL);
2470  assert(deleted != NULL);
2471 
2472  consdata = SCIPconsGetData(cons);
2473  assert(consdata != NULL);
2474  assert(consdata->sorted);
2475 
2476  nvars = consdata->nvars;
2477  assert(nvars > 1);
2478  assert(0 <= artpos && artpos < nvars);
2479 
2480  vars = consdata->vars;
2481  assert(vars != NULL);
2482 
2483  *deleted = FALSE;
2484 
2485  /* temporary exchange the variable for finding the shortest list */
2486  oldvar = vars[artpos];
2487  assert(oldvar == SCIPvarGetNegatedVar(artvar));
2488  vars[artpos] = artvar;
2489 
2490  /* determine shortest column */
2491  findShortestOccurlist(vars, nvars, varstopos, occurlist, noccurlistentries, occurlistlength, &nentries, &shortestlist);
2492 
2493  /* correct exchanged variable with constraint variables */
2494  vars[artpos] = oldvar;
2495 
2496  /* one variable which does not appear in the column representation anymore */
2497  if( nentries == 0 )
2498  return SCIP_OKAY;
2499 
2500  assert(shortestlist != NULL);
2501  assert(0 < nentries);
2502 
2503  /* temporary exchange the variable for calculating a valid signature */
2504  oldvar = vars[artpos];
2505  vars[artpos] = artvar;
2506  signature = calcSignature(vars, nvars);
2507 
2508  /* correct exchanged variable with constraint variables */
2509  vars[artpos] = oldvar;
2510 
2511  /* check all constraints in the shortest list for coverage */
2512  for( c = nentries - 1; c >= 0; --c )
2513  {
2514  cons1 = shortestlist[c];
2515  assert(cons1 != NULL);
2516  assert(!SCIPconsIsModifiable(cons1));
2517 
2518  if( !SCIPconsIsActive(cons1) )
2519  continue;
2520 
2521  if( cons != cons1 )
2522  {
2523  SCIP_CONSDATA* consdata1 = SCIPconsGetData(cons1);
2524  assert(consdata1 != NULL);
2525 
2526  /* constraints with the less variables cannot be covered */
2527  if( consdata1->nvars < nvars )
2528  continue;
2529 
2530  pos = -1;
2531 
2532  assert(consdata->sorted);
2533  assert(consdata->merged);
2534  assert(consdata1->validsignature);
2535  assert(consdata1->sorted);
2536  assert(consdata1->merged);
2537 
2538  if( (signature & (~consdata1->signature)) == 0 )
2539  {
2540  SCIP_VAR* var1;
2541  int v1;
2542 
2543  v = 0;
2544  v1 = 0;
2545 
2546  while( v < nvars && v1 < consdata1->nvars )
2547  {
2548  int comp;
2549 
2550  /* skip position of artificial variable */
2551  if( artpos == v )
2552  {
2553  ++v;
2554  continue;
2555  }
2556 
2557  var1 = consdata1->vars[v1];
2558 
2559  /* did we find the artificial variable in cons1 */
2560  if( artvar == var1 )
2561  {
2562  /* remember of possible redundant variable */
2563  assert(pos == -1);
2564  pos = v1;
2565 
2566  ++v1;
2567  continue;
2568  }
2569 
2570  var = vars[v];
2571  comp = SCIPvarCompare(var, var1);
2572 
2573  /* check if the cons1 can still be covered */
2574  if( comp == 0 )
2575  {
2576  ++v;
2577  ++v1;
2578  }
2579  else if( comp > 0 )
2580  ++v1;
2581  else
2582  break;
2583  }
2584 
2585  /* cons1 is might be covered by the changed constraints cons, meaning that we might remove the artvar from
2586  * cons1
2587  */
2588  if( v == nvars )
2589  {
2590  int l;
2591 
2592  /* if the artificial variable was not yet found, search over the rear variables in constraint cons1 */
2593  if( pos == -1 )
2594  {
2595  while( v1 < consdata1->nvars )
2596  {
2597  if( artvar == consdata1->vars[v1] )
2598  {
2599  /* remember of possible redundant variable */
2600  pos = v1;
2601  break;
2602  }
2603  ++v1;
2604  }
2605  }
2606 
2607  if( pos >= 0 )
2608  {
2609  int conspos;
2610 
2611  assert(pos < consdata1->nvars);
2612  assert(artvar == consdata1->vars[pos]);
2613 
2614  /* remove redudant entry in cons1 */
2615  SCIPdebugMsg(scip, "variable %s in logicor constraint <%s> is redundant and will be removed (used constraint %s)\n",
2616  SCIPvarGetName(artvar), SCIPconsGetName(cons1), SCIPconsGetName(cons));
2617  SCIPdebugPrintCons(scip, cons1, NULL);
2618  conspos = pos;
2619 
2620  if( consdata1->nvars > nvars )
2621  {
2622  pos = SCIPhashmapGetImageInt(varstopos, (void*)artvar);
2623  assert(0 < pos && pos <= occurlistlength);
2624 
2625  --pos;
2626 
2627  /* remove corresponding entry in column representation */
2628  for( l = noccurlistentries[pos] - 1; l >= 0; --l )
2629  {
2630  if( occurlist[pos][l] == cons1 )
2631  {
2632  --noccurlistentries[pos];
2633  assert(noccurlistentries[pos] >= 0);
2634 
2635  occurlist[pos][l] = occurlist[pos][noccurlistentries[pos]];
2636  break;
2637  }
2638  }
2639  assert(l >= 0);
2640  }
2641  else
2642  {
2643  assert(consdata1->nvars == nvars);
2644 
2645  /* delete cons */
2646  SCIPdebugMsg(scip, "logicor constraint <%s> is redundant due to constraint <%s> after removing variable <%s>\n",
2647  SCIPconsGetName(cons), SCIPconsGetName(cons1), SCIPvarGetName(artvar));
2648 
2649  /* remove cons from columns representation */
2650  removeConsFromOccurList(cons, varstopos, occurlist, noccurlistentries, occurlistlength);
2651 
2652  /* update flags of cons1 */
2653  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons) );
2654 
2655  SCIP_CALL( SCIPdelCons(scip, cons) );
2656  *deleted = TRUE;
2657  }
2658 
2659  /* remove variable */
2660  SCIP_CALL( delCoefPos(scip, cons1, eventhdlr, conspos) );
2661  ++(*nchgcoefs);
2662  consdataSort(consdata1);
2663  consdataCalcSignature(consdata1);
2664 
2665  if( *deleted )
2666  return SCIP_OKAY;
2667  }
2668  }
2669  }
2670  }
2671  }
2672 
2673  return SCIP_OKAY;
2674 }
2675 
2676 /** find and remove redundant non-zero entries */
2677 static
2679  SCIP* scip, /**< SCIP data structure */
2680  SCIP_CONS** conss, /**< sorted array of logicor constraint */
2681  int nconss, /**< number of sorted constraints */
2682  SCIP_HASHMAP* varstopos, /**< map for mapping variables to positions in the occurlist */
2683  SCIP_CONS*** occurlist, /**< column representation of logicor constraints */
2684  int* noccurlistentries, /**< number of constraints for each variable in the occurlist */
2685  int occurlistlength, /**< number of columns in the occurlist */
2686  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2687  int* ndelconss, /**< pointer to store the number of deleted constraints */
2688  int* nchgcoefs /**< pointer to store the number of remove coefficients */
2689  )
2690 {
2691  SCIP_VAR** vars;
2692  SCIP_CONSDATA* consdata;
2693  SCIP_CONS* cons;
2694  SCIP_VAR* artvar;
2695  int nvars;
2696  int c;
2697  int v;
2698 
2699  assert(scip != NULL);
2700  assert(conss != NULL || nconss == 0);
2701  assert(varstopos != NULL);
2702  assert(occurlist != NULL);
2703  assert(noccurlistentries != NULL);
2704  assert(eventhdlr != NULL);
2705  assert(ndelconss != NULL);
2706  assert(nchgcoefs != NULL);
2707 
2708  if( nconss == 0 )
2709  return SCIP_OKAY;
2710 
2711  assert(conss != NULL);
2712 
2713  for( c = 0; c < nconss; ++c )
2714  {
2715  cons = conss[c];
2716  assert(cons != NULL);
2717  assert(!SCIPconsIsModifiable(cons));
2718 
2719  if( !SCIPconsIsActive(cons) )
2720  continue;
2721 
2722  consdata = SCIPconsGetData(cons);
2723  assert(consdata != NULL);
2724 
2725  nvars = consdata->nvars;
2726  assert(nvars >= 1);
2727 
2728  if( nvars == 1 )
2729  continue;
2730 
2731  vars = consdata->vars;
2732  assert(vars != NULL);
2733 
2734  for( v = nvars - 1; v >= 0; --v )
2735  {
2736  artvar = SCIPvarGetNegatedVar(vars[v]);
2737 
2738  if( artvar != NULL && SCIPhashmapExists(varstopos, (void*) artvar) )
2739  {
2740  SCIP_Bool deleted;
2741 
2742  /* detect and remove redundant non-zero entries */
2743  /* @todo: improve this algorithm by using the information that a constraint variables does not appaer in any
2744  * other constraint, which means that only this variable needs to be negated to check for redundant
2745  * non-zeros, therefor change also findShortestOccurlist() to return the corresponding
2746  * variable/position
2747  */
2748  SCIP_CALL( removeRedundantNonZeros(scip, cons, artvar, v, varstopos, occurlist, noccurlistentries,
2749  occurlistlength, eventhdlr, nchgcoefs, &deleted) );
2750 
2751  if( deleted )
2752  {
2753  assert(SCIPconsIsDeleted(cons));
2754  ++(*ndelconss);
2755  break;
2756  }
2757  else
2758  assert(SCIPconsIsActive(cons));
2759  }
2760  }
2761  }
2762 
2763  return SCIP_OKAY;
2764 }
2765 
2766 
2767 /** prepares a constraint by removing fixings and merge it */
2768 static
2770  SCIP* scip, /**< SCIP data structure */
2771  SCIP_CONS* cons, /**< logic or constraint */
2772  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2773  unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
2774  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
2775  SCIP_Bool* redundant, /**< returns whether a variable fixed to one exists in the constraint */
2776  int* nfixedvars, /**< pointer to count number of fixings */
2777  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
2778  int* ndelconss, /**< pointer to count number of deleted constraints */
2779  SCIP_Bool* cutoff /**< pointer to store, if cut off appeared */
2780  )
2781 {
2782  SCIP_CONSDATA* consdata;
2783 
2784  assert(scip != NULL);
2785  assert(cons != NULL);
2786  assert(!SCIPconsIsDeleted(cons));
2787  assert(eventhdlr != NULL);
2788  assert(*entries != NULL);
2789  assert(nentries != NULL);
2790  assert(redundant != NULL);
2791  assert(nfixedvars != NULL);
2792  assert(nchgcoefs != NULL);
2793  assert(ndelconss != NULL);
2794  assert(redundant != NULL);
2795 
2796  consdata = SCIPconsGetData(cons);
2797  assert(consdata != NULL);
2798  assert(consdata->nvars > 0);
2799 
2800  *redundant = FALSE;
2801 
2802  /* remove old fixings */
2803  if( !consdata->presolved )
2804  {
2805  /* remove all variables that are fixed to zero, check redundancy due to fixed-to-one variable */
2806  SCIP_CALL( applyFixings(scip, cons, eventhdlr, redundant, nchgcoefs, NULL, NULL) );
2807  }
2808 
2809  if( !*redundant )
2810  {
2811  /* merge constraint */
2812  SCIP_CALL( mergeMultiples(scip, cons, eventhdlr, entries, nentries, redundant, nchgcoefs) );
2813  }
2814 
2815  if( *redundant )
2816  {
2817  SCIP_CALL( SCIPdelCons(scip, cons) );
2818  ++(*ndelconss);
2819 
2820  return SCIP_OKAY;
2821  }
2822 
2823  if( consdata->nvars == 0 )
2824  {
2825  *cutoff = TRUE;
2826  }
2827  else if( consdata->nvars == 1 )
2828  {
2829  SCIP_Bool infeasible;
2830  SCIP_Bool fixed;
2831 
2832  SCIPdebugMsg(scip, " -> fix last remaining variable and delete constraint\n");
2833 
2834  SCIP_CALL( SCIPfixVar(scip, consdata->vars[0], 1.0, &infeasible, &fixed) );
2835  assert(!infeasible);
2836  assert(fixed);
2837  ++(*nfixedvars);
2838 
2839  SCIP_CALL( SCIPdelCons(scip, cons) );
2840  ++(*ndelconss);
2841 
2842  *redundant = TRUE;
2843  }
2844  consdata->presolved = TRUE;
2845 
2846  return SCIP_OKAY;
2847 }
2848 
2849 
2850 /** find covered/subsumed constraints and redundant non-zero entries
2851  *
2852  * covered:
2853  * e.g.: c1: x1 + x2 + x3 >= 1
2854  * c2: x1 + x2 + x3 + x4 >= 1
2855  *
2856  * strengthen:
2857  * e.g.: c1: x1 + x2 + x3 >= 1
2858  * c2: x1 + x2 + ~x3 + x4 >= 1
2859  *
2860  * => c2: x1 + x2 + x4 >= 1
2861  *
2862  * @see "Effective Preprocessing in SAT through Variable and Clause Elimination" by Niklas En and Armin Biere
2863  */
2864 static
2866  SCIP* scip, /**< SCIP data structure */
2867  SCIP_CONS** conss, /**< array of logicor constraints */
2868  int nconss, /**< number of logicor constraints */
2869  unsigned char** entries, /**< array to store whether two positions in constraints represent the same
2870  * variable */
2871  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
2872  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2873  SCIP_Bool usestrengthening, /**< should we try to strengthen constraints by removing superflous
2874  * non-zeros? */
2875  int* firstchange, /**< pointer to store first changed constraint */
2876  int* nfixedvars, /**< pointer to count number of fixings */
2877  int* ndelconss, /**< pointer to store the number of deleted constraints */
2878  int* nchgcoefs, /**< pointer to store the number of deleted coefficients */
2879  SCIP_Bool* cutoff /**< pointer to store, if cut off appeared */
2880  )
2881 {
2882  SCIP_CONS*** occurlist;
2883  SCIP_CONS** myconss;
2884  SCIP_HASHMAP* varstopos;
2885  SCIP_CONS* cons;
2886  SCIP_CONSDATA* consdata;
2887  int* noccurlistentries;
2888  int* occurlistsizes;
2889  SCIP_Bool redundant;
2890  SCIP_Bool conschanged;
2891  int nbinvars;
2892  int occurlistlength;
2893  int occurlistsize;
2894  int nmyconss;
2895  int nmaxvars;
2896  int c;
2897 
2898  assert(scip != NULL);
2899  assert(conss != NULL || nconss == 0);
2900  assert(entries != NULL);
2901  assert(*entries != NULL);
2902  assert(nentries != NULL);
2903  assert(eventhdlr != NULL);
2904  assert(firstchange != NULL);
2905  assert(0 <= *firstchange);
2906  assert(nfixedvars != NULL);
2907  assert(ndelconss != NULL);
2908  assert(nchgcoefs != NULL);
2909 
2910  if( *firstchange > nconss || nconss < 2 )
2911  return SCIP_OKAY;
2912 
2913  SCIPdebugMsg(scip, "starting removeRedundantConssAndNonzeros(), pairwise comparison to detect covered logicor constraints\n");
2914 
2915  /* copy constraints to re-order them */
2916  SCIP_CALL( SCIPduplicateBufferArray(scip, &myconss, conss, nconss) );
2917 
2918  nmyconss = nconss;
2919  for( c = nconss - 1; c >= 0; --c )
2920  {
2921  cons = myconss[c];
2922  assert(cons != NULL);
2923 
2924  if( SCIPconsIsDeleted(cons) || SCIPconsIsModifiable(cons) )
2925  {
2926  myconss[c] = myconss[nmyconss - 1];
2927  --nmyconss;
2928 
2929  continue;
2930  }
2931 
2932  /* prepare constraint by removing fixings and merge it */
2933  SCIP_CALL( prepareCons(scip, cons, eventhdlr, entries, nentries, &redundant, nfixedvars, nchgcoefs, ndelconss, cutoff) );
2934 
2935  if( redundant )
2936  {
2937  assert(SCIPconsIsDeleted(cons));
2938 
2939  myconss[c] = myconss[nmyconss - 1];
2940  --nmyconss;
2941  }
2942 
2943  if( *cutoff )
2944  {
2945  SCIPfreeBufferArray(scip, &myconss);
2946 
2947  return SCIP_OKAY;
2948  }
2949 
2950  consdata = SCIPconsGetData(cons);
2951 
2952  /* sort the constraint */
2953  consdataSort(consdata);
2954 
2955  assert(consdata->nvars >= 2);
2956  }
2957 
2958  SCIPsortPtr((void**)myconss, conssLogicorComp, nmyconss);
2959  assert(myconss[0] != NULL && myconss[nmyconss - 1] != NULL);
2960  assert(SCIPconsGetData(myconss[0]) != NULL && SCIPconsGetData(myconss[nmyconss - 1]) != NULL);
2961  assert(SCIPconsGetData(myconss[0])->nvars <= SCIPconsGetData(myconss[nmyconss - 1])->nvars);
2962 
2963  /* we can stop if strengthening is disabled and all constraints have the same amount of variables */
2964  if( !usestrengthening && SCIPconsGetData(myconss[0])->nvars == SCIPconsGetData(myconss[nmyconss - 1])->nvars )
2965  {
2966  SCIPfreeBufferArray(scip, &myconss);
2967 
2968  return SCIP_OKAY;
2969  }
2970 
2971  /* @note: in the following we have at least number of nonzeros in logicor constraints + three times two the number of
2972  * binary variables memory consumption + a map for variables to positions, we need this to get a column base
2973  * representation
2974  */
2975 
2976  /* get number of all possible(incl. implcit) binary variables and their negation */
2977  nbinvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
2978  occurlistsize = 2 * nbinvars;
2979 
2980  /* allocate memory for the column representation for each variable */
2981  SCIP_CALL( SCIPallocBufferArray(scip, &occurlist, occurlistsize) );
2982  BMSclearMemoryArray(occurlist, occurlistsize);
2983  SCIP_CALL( SCIPallocBufferArray(scip, &noccurlistentries, occurlistsize) );
2984  BMSclearMemoryArray(noccurlistentries, occurlistsize);
2985  SCIP_CALL( SCIPallocBufferArray(scip, &occurlistsizes, occurlistsize) );
2986  BMSclearMemoryArray(occurlistsizes, occurlistsize);
2987 
2988  /* create hashmap to map all occuring variables to a position in the list */
2989  SCIP_CALL( SCIPhashmapCreate(&varstopos, SCIPblkmem(scip), nmyconss) );
2990 
2991  /* get maximal number of variables over all logicor constraints */
2992  c = nmyconss - 1;
2993  cons = myconss[c];
2994  assert(cons != NULL);
2995  assert(SCIPconsIsActive(cons));
2996  consdata = SCIPconsGetData(cons);
2997  assert(consdata != NULL);
2998  nmaxvars = consdata->nvars;
2999 
3000  occurlistlength = 0;
3001  conschanged = FALSE;
3002 
3003  /* determine all constraints with the maximal number of variables and add them to the column representation */
3004  do
3005  {
3006  /* calculate hash-signature */
3007  consdataCalcSignature(consdata);
3008  assert(consdata->validsignature);
3009  conschanged = conschanged || consdata->changed;
3010  consdata->changed = FALSE;
3011 
3012  /* add constraint to column data structure */
3013  SCIP_CALL( addConsToOccurList(scip, cons, varstopos, occurlist, noccurlistentries, occurlistsizes, &occurlistlength, occurlistsize) );
3014 
3015  --c;
3016  if( c < 0 )
3017  break;
3018 
3019  cons = myconss[c];
3020  assert(cons != NULL);
3021  assert(SCIPconsIsActive(cons));
3022  consdata = SCIPconsGetData(cons);
3023  assert(consdata != NULL);
3024  }
3025  while( consdata->nvars == nmaxvars );
3026 
3027  /* remove covered constraints and left over constraints to the column representation */
3028  while( c >= 0 )
3029  {
3030  cons = myconss[c];
3031  assert(cons != NULL);
3032  assert(SCIPconsIsActive(cons));
3033  consdata = SCIPconsGetData(cons);
3034  assert(consdata != NULL);
3035 
3036  /* calculate hash-signature */
3037  consdataCalcSignature(consdata);
3038  assert(consdata->validsignature);
3039 
3040  /* search for covered constraints */
3041  if( conschanged || consdata->changed )
3042  {
3043  /* detect covered constraints
3044  *
3045  * e.g.: c1: x1 + x2 + x3 >= 1
3046  * c2: x1 + x2 + x3 + x4 >= 1
3047  *
3048  * => delete c2
3049  */
3050  SCIP_CALL( removeRedundantConss(scip, cons, varstopos, occurlist, noccurlistentries, occurlistlength, ndelconss) );
3051  assert(SCIPconsIsActive(cons));
3052 
3053  consdata->changed = FALSE;
3054  conschanged = TRUE;
3055  }
3056 
3057  /* add constraint to column data structure */
3058  SCIP_CALL( addConsToOccurList(scip, cons, varstopos, occurlist, noccurlistentries, occurlistsizes, &occurlistlength, occurlistsize) );
3059 
3060  --c;
3061  }
3062 
3063  /* strengthen constraint while removing non-zeros
3064  *
3065  * e.g.: c1: x1 + x2 + x3 >= 1
3066  * c2: x1 + x2 + ~x3 + x4 >= 1
3067  *
3068  * => c2: x1 + x2 + x4 >= 1
3069  *
3070  * special case:
3071  *
3072  * e.g.: c1: x1 + x2 + x3 >= 1
3073  * c2: x1 + x2 + ~x3 >= 1
3074  *
3075  * => delete c1; c2: x1 + x2 >= 1
3076  *
3077  */
3078  SCIP_CALL( strengthenConss(scip, myconss, nmyconss, varstopos, occurlist, noccurlistentries, occurlistlength, eventhdlr, ndelconss, nchgcoefs) );
3079 
3080  /* delete temporary memory in occurlist */
3081  for( --occurlistsize ; occurlistsize >= 0; --occurlistsize )
3082  {
3083  assert((occurlistsizes[occurlistsize] == 0) == (occurlist[occurlistsize] == NULL));
3084  SCIPfreeBufferArrayNull(scip, &(occurlist[occurlistsize]));
3085  }
3086 
3087  /* delete temporary memory */
3088  SCIPhashmapFree(&varstopos);
3089  SCIPfreeBufferArray(scip, &occurlistsizes);
3090  SCIPfreeBufferArray(scip, &noccurlistentries);
3091  SCIPfreeBufferArray(scip, &occurlist);
3092  SCIPfreeBufferArray(scip, &myconss);
3093 
3094  return SCIP_OKAY;
3095 }
3096 
3097 #define MAX_CONSLENGTH 200
3098 
3099 /** try to tighten constraints by reducing the number of variables in the constraints using implications and cliques,
3100  * also derive fixations through them, @see SCIPshrinkDisjunctiveVarSet()
3101  */
3102 static
3104  SCIP* scip, /**< SCIP data structure */
3105  SCIP_CONSHDLRDATA* conshdlrdata, /**< logic or constraint handler data */
3106  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
3107  SCIP_CONS** conss, /**< all constraints */
3108  int nconss, /**< number of constraints */
3109  unsigned char** entries, /**< array to store whether two positions in constraints represent the same
3110  * variable */
3111  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
3112  int* nfixedvars, /**< pointer to count number of fixings */
3113  int* ndelconss, /**< pointer to count number of deleted constraints */
3114  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
3115  SCIP_Bool* cutoff /**< pointer to store, if cut off appeared */
3116  )
3117 {
3118  SCIP_VAR** probvars;
3119  SCIP_VAR* var;
3120  SCIP_Real* bounds;
3121  SCIP_Bool* boundtypes;
3122  SCIP_Bool* redundants;
3123  int nbinprobvars;
3124  int nredvars;
3125  int c;
3126  int v;
3127 
3128  assert(scip != NULL);
3129  assert(eventhdlr != NULL);
3130  assert(conss != NULL || nconss == 0);
3131  assert(entries != NULL);
3132  assert(*entries != NULL);
3133  assert(nentries != NULL);
3134  assert(nfixedvars != NULL);
3135  assert(ndelconss != NULL);
3136  assert(nchgcoefs != NULL);
3137 
3138  if( nconss == 0 )
3139  return SCIP_OKAY;
3140 
3141  assert(conss != NULL);
3142 
3143  if( SCIPgetNCliques(scip) == conshdlrdata->nlastcliquesshorten
3144  && SCIPgetNImplications(scip) == conshdlrdata->nlastimplsshorten )
3145  return SCIP_OKAY;
3146 
3147  conshdlrdata->nlastcliquesshorten = SCIPgetNCliques(scip);
3148  conshdlrdata->nlastimplsshorten = SCIPgetNImplications(scip);
3149 
3150  nbinprobvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
3151 
3152  /* allocate temporary memory */
3153  SCIP_CALL( SCIPallocBufferArray(scip, &probvars, nbinprobvars) );
3154  SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nbinprobvars) );
3155  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nbinprobvars) );
3156  SCIP_CALL( SCIPallocCleanBufferArray(scip, &redundants, nbinprobvars) );
3157 
3158  for( c = nconss - 1; c >= 0; --c )
3159  {
3160  SCIP_Bool redundant = FALSE;
3161  SCIP_Bool glbinfeas = FALSE;
3162  SCIP_CONS* cons = conss[c];
3163  SCIP_CONSDATA* consdata;
3164 
3165  assert(cons != NULL);
3166 
3167  if( SCIPconsIsDeleted(cons) )
3168  continue;
3169 
3170  consdata = SCIPconsGetData(cons);
3171  assert(consdata != NULL);
3172 
3173  /* prepare constraint by removing fixings and merge it */
3174  SCIP_CALL( prepareCons(scip, cons, eventhdlr, entries, nentries, &redundant, nfixedvars, nchgcoefs, ndelconss, cutoff) );
3175 
3176  if( redundant )
3177  {
3178  assert(SCIPconsIsDeleted(cons));
3179  continue;
3180  }
3181 
3182  if( *cutoff )
3183  goto TERMINATE;
3184 
3185  assert(consdata->nvars >= 2);
3186 
3187  /* do not try to shorten too long constraints */
3188  if( consdata->nvars > MAX_CONSLENGTH )
3189  continue;
3190 
3191  /* form necessary data */
3192  for( v = consdata->nvars - 1; v >= 0; --v)
3193  {
3194  var = consdata->vars[v];
3195  assert(var != NULL);
3197 
3198  if( SCIPvarIsActive(var) )
3199  {
3200  probvars[v] = var;
3201  bounds[v] = 1.0;
3202  boundtypes[v] = FALSE;
3203  }
3204  else
3205  {
3206  probvars[v] = SCIPvarGetNegationVar(var);
3207  bounds[v] = 0.0;
3208  boundtypes[v] = TRUE;
3209  }
3210  }
3211 
3212  SCIP_CALL( SCIPcleanupCliques(scip, cutoff) );
3213 
3214  if( *cutoff )
3215  goto TERMINATE;
3216 
3217  /* use implications and cliques to derive global fixings and to shrink the number of variables in this constraints */
3218  SCIP_CALL( SCIPshrinkDisjunctiveVarSet(scip, probvars, bounds, boundtypes, redundants, consdata->nvars, &nredvars,
3219  nfixedvars, &redundant, &glbinfeas, TRUE) );
3220 
3221  if( glbinfeas )
3222  goto TERMINATE;
3223 
3224  /* remove redundant constraint */
3225  if( redundant )
3226  {
3227  SCIP_CALL( SCIPdelCons(scip, cons) );
3228  ++(*ndelconss);
3229 
3230  /* reset redundants array to FALSE */
3231 #if 1
3232  BMSclearMemoryArray(redundants, consdata->nvars);
3233 #else
3234  if( nredvars > 0 )
3235  {
3236  for( v = consdata->nvars - 1; v >= 0; --v )
3237  {
3238  if( redundants[v] )
3239  {
3240  redundants[v] = FALSE;
3241  }
3242  }
3243  }
3244 #endif
3245  continue;
3246  }
3247 
3248  /* remove redundant variables */
3249  if( nredvars > 0 )
3250  {
3251  for( v = consdata->nvars - 1; v >= 0; --v )
3252  {
3253  if( redundants[v] )
3254  {
3255  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
3256 
3257  /* reset entry to FALSE */
3258  redundants[v] = FALSE;
3259  }
3260  }
3261  *nchgcoefs += nredvars;
3262 
3263  /* if only one variable is left over fix it */
3264  if( consdata->nvars == 1 )
3265  {
3266  SCIP_Bool infeasible;
3267  SCIP_Bool fixed;
3268 
3269  SCIPdebugMsg(scip, " -> fix last remaining variable and delete constraint\n");
3270 
3271  SCIP_CALL( SCIPfixVar(scip, consdata->vars[0], 1.0, &infeasible, &fixed) );
3272  assert(!infeasible);
3273  assert(fixed);
3274  ++(*nfixedvars);
3275 
3276  SCIP_CALL( SCIPdelCons(scip, cons) );
3277  ++(*ndelconss);
3278  }
3279  /* @todo might also upgrade a two variable constraint to a set-packing constraint */
3280  }
3281  }
3282 
3283  TERMINATE:
3284  /* free temporary memory */
3285  SCIPfreeCleanBufferArray(scip, &redundants);
3286  SCIPfreeBufferArray(scip, &boundtypes);
3287  SCIPfreeBufferArray(scip, &bounds);
3288  SCIPfreeBufferArray(scip, &probvars);
3289 
3290  return SCIP_OKAY;
3291 }
3292 
3293 #define MAXCOMPARISONS 1000000
3294 
3295 /** try to find a negated clique in a constraint which makes this constraint redundant but we need to keep the negated
3296  * clique information alive, so we create a corresponding set-packing constraint
3297  */
3298 static
3300  SCIP* scip, /**< SCIP data structure */
3301  SCIP_CONSHDLR* conshdlr, /**< logicor constraint handler */
3302  SCIP_CONSHDLR* conshdlrsetppc, /**< setppc constraint handler, or NULL */
3303  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
3304  SCIP_CONS** conss, /**< all constraints */
3305  int nconss, /**< number of constraints */
3306  unsigned char** entries, /**< array to store whether two positions in constraints represent the same
3307  * variable */
3308  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
3309  int* nfixedvars, /**< pointer to count number of fixings */
3310  int* ndelconss, /**< pointer to count number of deleted constraints */
3311  int* nupgdconss, /**< pointer to count number of upgraded constraints */
3312  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
3313  SCIP_Bool* cutoff /**< pointer to store, if cut off appeared */
3314  )
3315 {
3316  SCIP_CONSHDLRDATA* conshdlrdata;
3317  SCIP_CONS* cons;
3318  SCIP_CONSDATA* consdata;
3319  SCIP_VAR** repvars;
3320  SCIP_Bool* negated;
3321  SCIP_VAR* var1;
3322  SCIP_Bool redundant;
3323  int c;
3324  int size;
3325  int maxcomppercons;
3326  int comppercons;
3327 
3328  assert(scip != NULL);
3329  assert(conshdlr != NULL);
3330  assert(eventhdlr != NULL);
3331  assert(conss != NULL || nconss == 0);
3332  assert(entries != NULL);
3333  assert(*entries != NULL);
3334  assert(nentries != NULL);
3335  assert(nfixedvars != NULL);
3336  assert(ndelconss != NULL);
3337  assert(nupgdconss != NULL);
3338  assert(nchgcoefs != NULL);
3339  assert(cutoff != NULL);
3340 
3341  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3342  assert(conshdlrdata != NULL);
3343 
3344  if( nconss == 0 )
3345  return SCIP_OKAY;
3346 
3347  if( SCIPgetNCliques(scip) == conshdlrdata->nlastcliquesneg && SCIPgetNImplications(scip) == conshdlrdata->nlastimplsneg )
3348  return SCIP_OKAY;
3349 
3350  conshdlrdata->nlastcliquesneg = SCIPgetNCliques(scip);
3351  conshdlrdata->nlastimplsneg = SCIPgetNImplications(scip);
3352 
3353  /* estimate the maximal number of variables in a logicor constraint */
3354  size = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
3355  if( size <= 0 )
3356  return SCIP_OKAY;
3357 
3358  /* temporary memory for active/negation of active variables */
3359  SCIP_CALL( SCIPallocBufferArray(scip, &repvars, size) );
3360  SCIP_CALL( SCIPallocBufferArray(scip, &negated, size) );
3361 
3362  /* iterate over all constraints and try to find negated cliques in logicors */
3363  for( c = nconss - 1; c >= 0; --c )
3364  {
3365  int v;
3366 
3367  assert(conss != NULL); /* for flexelint */
3368 
3369  cons = conss[c];
3370  assert(cons != NULL);
3371 
3372  if( !SCIPconsIsActive(cons) )
3373  continue;
3374 
3375  /* prepare constraint by removing fixings and merge it */
3376  SCIP_CALL( prepareCons(scip, cons, eventhdlr, entries, nentries, &redundant, nfixedvars, nchgcoefs, ndelconss, cutoff) );
3377 
3378  if( redundant )
3379  {
3380  assert(SCIPconsIsDeleted(cons));
3381  continue;
3382  }
3383 
3384  if( *cutoff )
3385  goto TERMINATE;
3386 
3387  consdata = SCIPconsGetData(cons);
3388  assert(consdata != NULL);
3389  assert(consdata->nvars >= 2);
3390  assert(consdata->nvars <= size);
3391  assert(consdata->presolved);
3392 
3393  if( SCIPconsIsModifiable(cons) && consdata->nvars == 2 )
3394  continue;
3395 
3396  if( c % 100 == 0 && SCIPisStopped(scip) )
3397  break;
3398 
3399  maxcomppercons = MAXCOMPARISONS / nconss;
3400  comppercons = 0;
3401 
3402  BMScopyMemoryArray(repvars, consdata->vars, consdata->nvars);
3403 
3404  /* all variables should be active or negative active variables, otherwise something went wrong with applyFixings()
3405  * called before mergeMultiples()
3406  */
3407  for( v = consdata->nvars - 1; v >= 0; --v )
3408  {
3409  assert(SCIPvarIsActive(repvars[v]) || (SCIPvarGetStatus(repvars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(repvars[v]))));
3410  negated[v] = SCIPvarIsNegated(repvars[v]);
3411  }
3412 
3413  for( v = consdata->nvars - 1; v > 0; --v )
3414  {
3415  SCIP_Bool breakloop;
3416  SCIP_Bool neg1;
3417  int w;
3418 
3419  var1 = repvars[v];
3420 
3421  /* if there is no negated variable, there can't be a negated clique */
3422  if( SCIPvarGetNegatedVar(var1) == NULL )
3423  continue;
3424 
3425  /* get active counterpart to check for common cliques */
3427  {
3428  var1 = SCIPvarGetNegatedVar(var1);
3429  neg1 = TRUE;
3430  }
3431  else
3432  neg1 = FALSE;
3433 
3434  if( !SCIPvarIsActive(var1) )
3435  continue;
3436 
3437  /* no cliques available */
3438  if( SCIPvarGetNCliques(var1, neg1) == 0 && SCIPvarGetNImpls(var1, neg1) == 0 )
3439  continue;
3440 
3441  comppercons += (v - 1);
3442 
3443  breakloop = FALSE;
3444 
3445  for( w = v - 1; w >= 0; --w )
3446  {
3447  SCIP_VAR* var2;
3448  SCIP_Bool neg2;
3449 
3450  var2 = repvars[w];
3451 
3452  /* if there is no negated variable, there can't be a negated clique */
3453  if( SCIPvarGetNegatedVar(var2) == NULL )
3454  continue;
3455 
3457  {
3458  var2 = SCIPvarGetNegatedVar(var2);
3459  neg2 = TRUE;
3460  }
3461  else
3462  neg2 = FALSE;
3463 
3464  if( !SCIPvarIsActive(var2) )
3465  continue;
3466 
3467  /* no cliques available */
3468  if( SCIPvarGetNCliques(var2, neg2) == 0 && SCIPvarGetNImpls(var2, neg2) == 0 )
3469  continue;
3470 
3471  /* check if both active variable are the same */
3472  if( var1 == var2 )
3473  {
3474  if( neg1 != neg2 )
3475  {
3476  SCIPdebugMsg(scip, "logicor constraint <%s> is redundant, because variable <%s> and its negation <%s> exist\n",
3477  SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2));
3478 
3479  SCIP_CALL( SCIPdelCons(scip, cons) );
3480 
3481  breakloop = TRUE;
3482  }
3483  else
3484  {
3485  #ifndef NDEBUG
3486  SCIP_VAR* lastvar = consdata->vars[consdata->nvars - 1];
3487  #endif
3488  SCIPdebugMsg(scip, "in logicor constraint <%s>, active variable of <%s> and active variable of <%s> are the same, removing the first\n",
3489  SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(consdata->vars[w]));
3490 
3491  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
3492 
3493  if( v < consdata->nvars )
3494  {
3495  /* delCoefPos replaces the variable on position v with the last one, so w also need to correct the
3496  * negated array the same way, and because of deletion the number of variables is already decreased
3497  */
3498  assert(consdata->vars[v] == lastvar);
3499  negated[v] = negated[consdata->nvars];
3500  }
3501  ++(*nchgcoefs);
3502  }
3503  break;
3504  }
3505 
3506  if( SCIPvarsHaveCommonClique(var1, neg1, var2, neg2, TRUE) && conshdlrsetppc != NULL )
3507  {
3508  SCIP_CONS* newcons;
3509  SCIP_VAR* vars[2];
3510 
3511  /* this negated clique information could be created out of this logicor constraint even if there are more
3512  * than two variables left (, for example by probing), we need to keep this information by creating a
3513  * setppc constraint instead
3514  */
3515 
3516  /* get correct variables */
3517  if( !neg1 )
3518  vars[0] = SCIPvarGetNegatedVar(var1);
3519  else
3520  vars[0] = var1;
3521 
3522  if( !neg2 )
3523  vars[1] = SCIPvarGetNegatedVar(var2);
3524  else
3525  vars[1] = var2;
3526 
3527  SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), 2, vars,
3530  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
3532 
3533  SCIP_CALL( SCIPaddCons(scip, newcons) );
3534  SCIPdebugPrintCons(scip, newcons, NULL);
3535 
3536  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3537 
3538  SCIPdebugMsg(scip, "logicor constraint <%s> is redundant due to negated clique information and will be replaced by a setppc constraint \n",
3539  SCIPconsGetName(cons));
3540  SCIPdebugMsg(scip, "variable <%s> and variable <%s> are in a negated clique\n", SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(consdata->vars[w]));
3541 
3542  SCIP_CALL( SCIPdelCons(scip, cons) );
3543  ++(*nupgdconss);
3544 
3545  breakloop = TRUE;
3546  break;
3547  }
3548  }
3549  if( breakloop )
3550  break;
3551 
3552  /* do not do to many comparisons */
3553  if( comppercons > maxcomppercons )
3554  break;
3555  }
3556  }
3557 
3558  TERMINATE:
3559  /* free temporary memory */
3560  SCIPfreeBufferArray(scip, &negated);
3561  SCIPfreeBufferArray(scip, &repvars);
3562 
3563  return SCIP_OKAY;
3564 }
3565 
3566 /** handle all cases with less than three variables in a logicor constraint
3567  *
3568  * in case a constraint has zero variables left, we detected infeasibility
3569  * in case a constraint has one variables left, we will fix it to one
3570  * in case a constraint has two variables left, we will add the implication and upgrade it to a set-packing constraint
3571  */
3572 static
3574  SCIP* scip, /**< SCIP data structure */
3575  SCIP_CONS* cons, /**< logic or constraint */
3576  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
3577  SCIP_CONSHDLR* conshdlrlinear, /**< linear constraint handler, or NULL */
3578  SCIP_CONSHDLR* conshdlrsetppc, /**< setppc constraint handler, or NULL */
3579  int* nfixedvars, /**< pointer to count number of fixings */
3580  int* nchgbds, /**< pointer to count number of tightened bounds */
3581  int* nchgcoefs, /**< pointer to count number of changed/deleted coefficients */
3582  int* ndelconss, /**< pointer to count number of deleted constraints */
3583  int* naddconss, /**< pointer to count number of added constraints */
3584  int* nupgdconss, /**< pointer to count number of upgraded constraints */
3585  SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
3586  )
3587 {
3588  SCIP_CONSDATA* consdata;
3589  SCIP_Bool infeasible;
3590  SCIP_Bool fixed;
3591 
3592  assert(scip != NULL);
3593  assert(cons != NULL);
3594  assert(eventhdlr != NULL);
3595  assert(nfixedvars != NULL);
3596  assert(nchgbds != NULL);
3597  assert(nchgcoefs != NULL);
3598  assert(ndelconss != NULL);
3599  assert(naddconss != NULL);
3600  assert(nupgdconss != NULL);
3601  assert(cutoff != NULL);
3602 
3603  *cutoff = FALSE;
3604 
3605  if( SCIPconsIsModifiable(cons) )
3606  return SCIP_OKAY;
3607 
3608  consdata = SCIPconsGetData(cons);
3609  assert(consdata != NULL);
3610 
3611  /* if an unmodifiable logicor constraint has only two variables, we can add an implication and we will upgrade this
3612  * constraint to a set-packing constraint
3613  */
3614  if( consdata->nvars == 2 )
3615  {
3616  /* add implication if not yet done */
3617  if( !consdata->impladded )
3618  {
3619  SCIP_Bool implinfeasible;
3620  int nimplbdchgs;
3621  SCIP_Bool values[2];
3622 
3623  values[0] = FALSE;
3624  values[1] = FALSE;
3625  /* a two-variable logicor constraint x + y >= 1 yields the implication x == 0 -> y == 1, and is represented
3626  * by the clique inequality ~x + ~y <= 1
3627  */
3628  SCIP_CALL( SCIPaddClique(scip, consdata->vars, values, consdata->nvars, FALSE, &implinfeasible, &nimplbdchgs) );
3629  *nchgbds += nimplbdchgs;
3630  if( implinfeasible )
3631  {
3632  *cutoff = TRUE;
3633  return SCIP_OKAY;
3634  }
3635 
3636  /* adding the above implication could lead to fixings, which render the constraint redundant */
3637  if ( nimplbdchgs > 0 )
3638  {
3639  SCIP_Bool redundant;
3640 
3641  /* remove all variables that are fixed to zero, check redundancy due to fixed-to-one variable */
3642  SCIP_CALL( applyFixings(scip, cons, eventhdlr, &redundant, nchgcoefs, naddconss, ndelconss) );
3643  assert(!SCIPconsIsDeleted(cons));
3644 
3645  if( redundant )
3646  {
3647  SCIPdebugMsg(scip, "logic or constraint <%s> is redundant\n", SCIPconsGetName(cons));
3648 
3649  SCIP_CALL( SCIPdelCons(scip, cons) );
3650  (*ndelconss)++;
3651 
3652  return SCIP_OKAY;
3653  }
3654  }
3655  consdata->impladded = TRUE;
3656  }
3657 
3658  /* still we have two variables left, we will upgrade this constraint */
3659  if( consdata->nvars == 2 && conshdlrsetppc != NULL )
3660  {
3661  SCIP_CONS* newcons;
3662  SCIP_VAR* vars[2];
3663 
3664  /* get correct variables */
3665  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[0], &vars[0]) );
3666  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[1], &vars[1]) );
3667 
3668  SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), 2, vars,
3673 
3674  SCIP_CALL( SCIPaddCons(scip, newcons) );
3675  SCIPdebugPrintCons(scip, newcons, NULL);
3676 
3677  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3678 
3679  SCIPdebugMsg(scip, "logicor constraint <%s> was upgraded to a set-packing constraint\n", SCIPconsGetName(cons));
3680 
3681  SCIP_CALL( SCIPdelCons(scip, cons) );
3682  ++(*nupgdconss);
3683  }
3684  }
3685 
3686  /* if unmodifiable constraint has no variables, it is infeasible,
3687  * if unmodifiable constraint has only one variable, this one can be fixed and the constraint deleted
3688  */
3689  if( consdata->nvars == 0 )
3690  {
3691  SCIPdebugMsg(scip, "logic or constraint <%s> is infeasible\n", SCIPconsGetName(cons));
3692 
3693  *cutoff = TRUE;
3694  }
3695  else if( consdata->nvars == 1 )
3696  {
3697  SCIPdebugMsg(scip, "logic or constraint <%s> has only one variable not fixed to 0.0\n",
3698  SCIPconsGetName(cons));
3699 
3700  assert(consdata->vars != NULL);
3701  assert(consdata->vars[0] != NULL);
3702 
3703  if( SCIPvarGetStatus(consdata->vars[0]) != SCIP_VARSTATUS_MULTAGGR )
3704  {
3705  SCIPdebugMsg(scip, " -> fix variable and delete constraint\n");
3706 
3707  SCIP_CALL( SCIPfixVar(scip, consdata->vars[0], 1.0, &infeasible, &fixed) );
3708  if( infeasible )
3709  {
3710  SCIPdebugMsg(scip, " -> infeasible fixing\n");
3711 
3712  *cutoff = TRUE;
3713  return SCIP_OKAY;
3714  }
3715  if( fixed )
3716  (*nfixedvars)++;
3717 
3718  SCIP_CALL( SCIPdelCons(scip, cons) );
3719  (*ndelconss)++;
3720  }
3721  else if( conshdlrlinear != NULL )
3722  {
3723  SCIP_Real coef;
3724  SCIP_CONS* conslinear;
3725  char consname[SCIP_MAXSTRLEN];
3726 
3727  SCIPdebugMsg(scip, " -> variable is multi-aggregated, upgrade to linear constraint <%s> == 1 \n",
3728  SCIPvarGetName(consdata->vars[0]));
3729 
3730  coef = 1.0;
3731  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "fixmaggr_%s_%s", SCIPconsGetName(cons),SCIPvarGetName(consdata->vars[0]) );
3732  SCIP_CALL( SCIPcreateConsLinear(scip, &conslinear, consname, 1, consdata->vars, &coef, 1.0, 1.0,
3736  SCIPconsIsStickingAtNode(cons)) );
3737 
3738  /* add constraint */
3739  SCIP_CALL( SCIPaddCons(scip, conslinear) );
3740  SCIP_CALL( SCIPreleaseCons(scip, &conslinear) );
3741  SCIP_CALL( SCIPdelCons(scip, cons) );
3742 
3743  (*ndelconss)++;
3744  (*naddconss)++;
3745  }
3746  }
3747 
3748  return SCIP_OKAY;
3749 }
3750 
3751 
3752 /*
3753  * upgrading of linear constraints
3754  */
3755 
3756 /** creates and captures a normalized (with all coefficients +1) logic or constraint */
3757 static
3759  SCIP* scip, /**< SCIP data structure */
3760  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3761  const char* name, /**< name of constraint */
3762  int nvars, /**< number of variables in the constraint */
3763  SCIP_VAR** vars, /**< array with variables of constraint entries */
3764  SCIP_Real* vals, /**< array with coefficients (+1.0 or -1.0) */
3765  int mult, /**< multiplier on the coefficients(+1 or -1) */
3766  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3767  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3768  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3769  * Usually set to TRUE. */
3770  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3771  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3772  SCIP_Bool check, /**< should the constraint be checked for feasibility?
3773  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3774  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3775  * Usually set to TRUE. */
3776  SCIP_Bool local, /**< is constraint only valid locally?
3777  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3778  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3779  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3780  * adds coefficients to this constraint. */
3781  SCIP_Bool dynamic, /**< is constraint subject to aging?
3782  * Usually set to FALSE. Set to TRUE for own cuts which
3783  * are separated as constraints. */
3784  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3785  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3786  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3787  * if it may be moved to a more global node?
3788  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3789  )
3790 {
3791  SCIP_VAR** transvars;
3792  int v;
3793 
3794  assert(nvars == 0 || vars != NULL);
3795  assert(nvars == 0 || vals != NULL);
3796  assert(mult == +1 || mult == -1);
3797 
3798  /* get temporary memory */
3799  SCIP_CALL( SCIPallocBufferArray(scip, &transvars, nvars) );
3800 
3801  /* negate positive or negative variables */
3802  for( v = 0; v < nvars; ++v )
3803  {
3804  if( mult * vals[v] > 0.0 )
3805  transvars[v] = vars[v];
3806  else
3807  {
3808  SCIP_CALL( SCIPgetNegatedVar(scip, vars[v], &transvars[v]) );
3809  }
3810  assert(transvars[v] != NULL);
3811  }
3812 
3813  /* create the constraint */
3814  SCIP_CALL( SCIPcreateConsLogicor(scip, cons, name, nvars, transvars,
3815  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3816 
3817  /* free temporary memory */
3818  SCIPfreeBufferArray(scip, &transvars);
3819 
3820  return SCIP_OKAY;
3821 }
3822 
3823 static
3824 SCIP_DECL_LINCONSUPGD(linconsUpgdLogicor)
3825 { /*lint --e{715}*/
3826  assert(upgdcons != NULL);
3827 
3828  /* check, if linear constraint can be upgraded to logic or constraint
3829  * - logic or constraints consist only of binary variables with a
3830  * coefficient of +1.0 or -1.0 (variables with -1.0 coefficients can be negated):
3831  * lhs <= x1 + ... + xp - y1 - ... - yn <= rhs
3832  * - negating all variables y = (1-Y) with negative coefficients gives:
3833  * lhs + n <= x1 + ... + xp + Y1 + ... + Yn <= rhs + n
3834  * - negating all variables x = (1-X) with positive coefficients and multiplying with -1 gives:
3835  * p - rhs <= X1 + ... + Xp + y1 + ... + yn <= p - lhs
3836  * - logic or constraints have left hand side of +1.0, and right hand side of +infinity: x(S) >= 1.0
3837  * -> without negations: (lhs == 1 - n and rhs == +inf) or (lhs == -inf and rhs = p - 1)
3838  */
3839  if( nvars > 2 && nposbin + nnegbin + nposimplbin + nnegimplbin == nvars && ncoeffspone + ncoeffsnone == nvars
3840  && ((SCIPisEQ(scip, lhs, 1.0 - ncoeffsnone) && SCIPisInfinity(scip, rhs))
3841  || (SCIPisInfinity(scip, -lhs) && SCIPisEQ(scip, rhs, ncoeffspone - 1.0))) )
3842  {
3843  int mult;
3844 
3845  SCIPdebugMsg(scip, "upgrading constraint <%s> to logic or constraint\n", SCIPconsGetName(cons));
3846 
3847  /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
3848  mult = SCIPisInfinity(scip, rhs) ? +1 : -1;
3849 
3850  /* create the logic or constraint (an automatically upgraded constraint is always unmodifiable) */
3851  assert(!SCIPconsIsModifiable(cons));
3852  SCIP_CALL( createNormalizedLogicor(scip, upgdcons, SCIPconsGetName(cons), nvars, vars, vals, mult,
3857  }
3858 
3859  return SCIP_OKAY;
3860 }
3861 
3862 /** helper function to enforce constraints */
3863 static
3865  SCIP* scip, /**< SCIP data structure */
3866  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3867  SCIP_CONS** conss, /**< constraints to process */
3868  int nconss, /**< number of constraints */
3869  int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
3870  SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
3871  SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
3872  )
3873 {
3874  SCIP_CONSHDLRDATA* conshdlrdata;
3875  SCIP_Bool cutoff;
3876  SCIP_Bool separated;
3877  SCIP_Bool reduceddom;
3878  int c;
3879 
3880  assert(conshdlr != NULL);
3881  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3882  assert(nconss == 0 || conss != NULL);
3883  assert(result != NULL);
3884 
3885  SCIPdebugMsg(scip, "Enforcing %d logic or constraints for %s solution\n", nconss, sol == NULL ? "LP" : "relaxation");
3886 
3887  *result = SCIP_FEASIBLE;
3888 
3889  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3890  assert(conshdlrdata != NULL);
3891 
3892  cutoff = FALSE;
3893  separated = FALSE;
3894  reduceddom = FALSE;
3895 
3896  /* check all useful logic or constraints for feasibility */
3897  for( c = 0; c < nusefulconss && !cutoff && !reduceddom; ++c )
3898  {
3899  SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
3900  }
3901 
3902  /* check all obsolete logic or constraints for feasibility */
3903  for( c = nusefulconss; c < nconss && !cutoff && !separated && !reduceddom; ++c )
3904  {
3905  SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
3906  }
3907 
3908  /* return the correct result */
3909  if( cutoff )
3910  *result = SCIP_CUTOFF;
3911  else if( separated )
3912  *result = SCIP_SEPARATED;
3913  else if( reduceddom )
3914  *result = SCIP_REDUCEDDOM;
3915 
3916  return SCIP_OKAY;
3917 }
3918 
3919 
3920 /*
3921  * Callback methods of constraint handler
3922  */
3923 
3924 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
3925 static
3926 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLogicor)
3927 { /*lint --e{715}*/
3928  assert(scip != NULL);
3929  assert(conshdlr != NULL);
3930  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3931 
3932  /* call inclusion method of constraint handler */
3934 
3935  *valid = TRUE;
3936 
3937  return SCIP_OKAY;
3938 }
3939 
3940 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
3941 static
3942 SCIP_DECL_CONSFREE(consFreeLogicor)
3943 { /*lint --e{715}*/
3944  SCIP_CONSHDLRDATA* conshdlrdata;
3945 
3946  assert(conshdlr != NULL);
3947  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3948  assert(scip != NULL);
3949 
3950  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3951  assert(conshdlrdata != NULL);
3952 
3953  /* free constraint handler data */
3954  SCIP_CALL( conshdlrdataFree(scip, &conshdlrdata) );
3955 
3956  SCIPconshdlrSetData(conshdlr, NULL);
3957 
3958  return SCIP_OKAY;
3959 }
3960 
3961 
3962 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
3963 static
3964 SCIP_DECL_CONSINITPRE(consInitpreLogicor)
3965 { /*lint --e{715}*/
3966  SCIP_CONSHDLRDATA* conshdlrdata;
3967  SCIP_CONSDATA* consdata;
3968  int c;
3969  int v;
3970 
3971  assert(conshdlr != NULL);
3972  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3973  assert(conshdlrdata != NULL);
3974 
3975  conshdlrdata->nlastcliquesneg = 0;
3976  conshdlrdata->nlastimplsneg = 0;
3977  conshdlrdata->nlastcliquesshorten = 0;
3978  conshdlrdata->nlastimplsshorten = 0;
3979 
3980  /* catch all variable event for deleted variables, which is only used in presolving */
3981  for( c = nconss - 1; c >= 0; --c )
3982  {
3983  consdata = SCIPconsGetData(conss[c]);
3984  assert(consdata != NULL);
3985 
3986  for( v = consdata->nvars - 1; v >= 0; --v )
3987  {
3988  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
3989  (SCIP_EVENTDATA*)conss[c], NULL) );
3990  }
3991  }
3992 
3993  return SCIP_OKAY;
3994 }
3995 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
3996 static
3997 SCIP_DECL_CONSEXITPRE(consExitpreLogicor)
3998 { /*lint --e{715}*/
3999  SCIP_CONSHDLRDATA* conshdlrdata;
4000  SCIP_CONSDATA* consdata;
4001  SCIP_Bool redundant;
4002  int nchgcoefs = 0;
4003  int c;
4004  int v;
4005 
4006  assert(conshdlr != NULL);
4007  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4008  assert(conshdlrdata != NULL);
4009 
4010  /* drop all variable event for deleted variables, which was only used in presolving */
4011  for( c = 0; c < nconss; ++c )
4012  {
4013  consdata = SCIPconsGetData(conss[c]);
4014  assert(consdata != NULL);
4015 
4016  for( v = 0; v < consdata->nvars; ++v )
4017  {
4018  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4019  (SCIP_EVENTDATA*)conss[c], -1) );
4020  }
4021 
4022  if( !SCIPconsIsDeleted(conss[c]) && !consdata->presolved )
4023  {
4024  /* we are not allowed to detect infeasibility in the exitpre stage */
4025  SCIP_CALL( applyFixings(scip, conss[c], conshdlrdata->eventhdlr, &redundant, &nchgcoefs, NULL, NULL) );
4026  }
4027  }
4028 
4029  return SCIP_OKAY;
4030 }
4031 
4032 
4033 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4034 static
4035 SCIP_DECL_CONSEXITSOL(consExitsolLogicor)
4036 { /*lint --e{715}*/
4037  SCIP_CONSDATA* consdata;
4038  int c;
4039 
4040  /* release the rows of all constraints */
4041  for( c = 0; c < nconss; ++c )
4042  {
4043  consdata = SCIPconsGetData(conss[c]);
4044  assert(consdata != NULL);
4045 
4046  if( consdata->row != NULL )
4047  {
4048  SCIP_CALL( SCIPreleaseRow(scip, &consdata->row) );
4049  }
4050  }
4051 
4052  return SCIP_OKAY;
4053 }
4054 
4055 
4056 /** frees specific constraint data */
4057 static
4058 SCIP_DECL_CONSDELETE(consDeleteLogicor)
4059 { /*lint --e{715}*/
4060  assert(conshdlr != NULL);
4061  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4062  assert(consdata != NULL);
4063  assert(*consdata != NULL);
4064 
4066  {
4067  SCIP_CONSHDLRDATA* conshdlrdata;
4068  int v;
4069 
4070  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4071  assert(conshdlrdata != NULL);
4072 
4073  for( v = (*consdata)->nvars - 1; v >= 0; --v )
4074  {
4075  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4076  (SCIP_EVENTDATA*)cons, -1) );
4077  }
4078  }
4079 
4080  /* free LP row and logic or constraint */
4081  SCIP_CALL( consdataFree(scip, consdata) );
4082 
4083  return SCIP_OKAY;
4084 }
4085 
4086 
4087 /** transforms constraint data into data belonging to the transformed problem */
4088 static
4089 SCIP_DECL_CONSTRANS(consTransLogicor)
4090 { /*lint --e{715}*/
4091  SCIP_CONSDATA* sourcedata;
4092  SCIP_CONSDATA* targetdata;
4093 
4094  /*debugMsg(scip, "Trans method of logic or constraints\n");*/
4095 
4096  assert(conshdlr != NULL);
4097  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4098  assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
4099  assert(sourcecons != NULL);
4100  assert(targetcons != NULL);
4101 
4102  sourcedata = SCIPconsGetData(sourcecons);
4103  assert(sourcedata != NULL);
4104  assert(sourcedata->row == NULL); /* in original problem, there cannot be LP rows */
4105 
4106  /* create constraint data for target constraint */
4107  SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->nvars, sourcedata->vars) );
4108 
4109  /* create target constraint */
4110  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4111  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4112  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4113  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4114  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4115 
4116  return SCIP_OKAY;
4117 }
4118 
4119 
4120 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4121 static
4122 SCIP_DECL_CONSINITLP(consInitlpLogicor)
4123 { /*lint --e{715}*/
4124  int c;
4125 
4126  *infeasible = FALSE;
4127 
4128  for( c = 0; c < nconss && !(*infeasible); ++c )
4129  {
4130  assert(SCIPconsIsInitial(conss[c]));
4131  SCIP_CALL( addCut(scip, conss[c], infeasible) );
4132  }
4133 
4134  return SCIP_OKAY;
4135 }
4136 
4137 
4138 /** separation method of constraint handler for LP solutions */
4139 static
4140 SCIP_DECL_CONSSEPALP(consSepalpLogicor)
4141 { /*lint --e{715}*/
4142  SCIP_CONSHDLRDATA* conshdlrdata;
4143  SCIP_Bool cutoff;
4144  SCIP_Bool separated;
4145  SCIP_Bool reduceddom;
4146  int c;
4147 
4148  assert(conshdlr != NULL);
4149  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4150  assert(nconss == 0 || conss != NULL);
4151  assert(result != NULL);
4152 
4153  SCIPdebugMsg(scip, "separating %d/%d logic or constraints\n", nusefulconss, nconss);
4154 
4155  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4156  assert(conshdlrdata != NULL);
4157 
4158  cutoff = FALSE;
4159  separated = FALSE;
4160  reduceddom = FALSE;
4161 
4162  /* check all useful logic or constraints for feasibility */
4163  for( c = 0; c < nusefulconss && !cutoff; ++c )
4164  {
4165  SCIP_CALL( separateCons(scip, conss[c], NULL, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
4166  }
4167 
4168  /* combine logic or constraints to get more cuts */
4169  /**@todo further cuts of logic or constraints */
4170 
4171  /* return the correct result */
4172  if( cutoff )
4173  *result = SCIP_CUTOFF;
4174  else if( reduceddom )
4175  *result = SCIP_REDUCEDDOM;
4176  else if( separated )
4177  *result = SCIP_SEPARATED;
4178  else
4179  *result = SCIP_DIDNOTFIND;
4180 
4181  return SCIP_OKAY;
4182 }
4183 
4184 
4185 /** separation method of constraint handler for arbitrary primal solutions */
4186 static
4187 SCIP_DECL_CONSSEPASOL(consSepasolLogicor)
4188 { /*lint --e{715}*/
4189  SCIP_CONSHDLRDATA* conshdlrdata;
4190  SCIP_Bool cutoff;
4191  SCIP_Bool separated;
4192  SCIP_Bool reduceddom;
4193  int c;
4194 
4195  assert(conshdlr != NULL);
4196  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4197  assert(nconss == 0 || conss != NULL);
4198  assert(result != NULL);
4199 
4200  SCIPdebugMsg(scip, "separating %d/%d logic or constraints\n", nusefulconss, nconss);
4201 
4202  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4203  assert(conshdlrdata != NULL);
4204 
4205  cutoff = FALSE;
4206  separated = FALSE;
4207  reduceddom = FALSE;
4208 
4209  /* check all useful logic or constraints for feasibility */
4210  for( c = 0; c < nusefulconss && !cutoff; ++c )
4211  {
4212  SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
4213  }
4214 
4215  /* combine logic or constraints to get more cuts */
4216  /**@todo further cuts of logic or constraints */
4217 
4218  /* return the correct result */
4219  if( cutoff )
4220  *result = SCIP_CUTOFF;
4221  else if( reduceddom )
4222  *result = SCIP_REDUCEDDOM;
4223  else if( separated )
4224  *result = SCIP_SEPARATED;
4225  else
4226  *result = SCIP_DIDNOTFIND;
4227 
4228  return SCIP_OKAY;
4229 }
4230 
4231 
4232 /** constraint enforcing method of constraint handler for LP solutions */
4233 static
4234 SCIP_DECL_CONSENFOLP(consEnfolpLogicor)
4235 { /*lint --e{715}*/
4236  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) );
4237 
4238  return SCIP_OKAY;
4239 }
4240 
4241 
4242 /** constraint enforcing method of constraint handler for relaxation solutions */
4243 static
4244 SCIP_DECL_CONSENFORELAX(consEnforelaxLogicor)
4245 { /*lint --e{715}*/
4246  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, sol, result) );
4247 
4248  return SCIP_OKAY;
4249 }
4250 
4251 
4252 /** constraint enforcing method of constraint handler for pseudo solutions */
4253 static
4254 SCIP_DECL_CONSENFOPS(consEnfopsLogicor)
4255 { /*lint --e{715}*/
4256  SCIP_CONSHDLRDATA* conshdlrdata;
4257  SCIP_Bool cutoff;
4258  SCIP_Bool infeasible;
4259  SCIP_Bool reduceddom;
4260  SCIP_Bool solvelp;
4261  int c;
4262 
4263  assert(conshdlr != NULL);
4264  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4265  assert(nconss == 0 || conss != NULL);
4266  assert(result != NULL);
4267 
4268  SCIPdebugMsg(scip, "pseudo enforcing %d logic or constraints\n", nconss);
4269 
4270  *result = SCIP_FEASIBLE;
4271 
4272  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4273  assert(conshdlrdata != NULL);
4274 
4275  cutoff = FALSE;
4276  infeasible = FALSE;
4277  reduceddom = FALSE;
4278  solvelp = FALSE;
4279 
4280  /* check all logic or constraints for feasibility */
4281  for( c = 0; c < nconss && !cutoff && !reduceddom && !solvelp; ++c )
4282  {
4283  SCIP_CALL( enforcePseudo(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &infeasible, &reduceddom, &solvelp) );
4284  }
4285 
4286  if( cutoff )
4287  *result = SCIP_CUTOFF;
4288  else if( reduceddom )
4289  *result = SCIP_REDUCEDDOM;
4290  else if( solvelp )
4291  *result = SCIP_SOLVELP;
4292  else if( infeasible )
4293  *result = SCIP_INFEASIBLE;
4294 
4295  return SCIP_OKAY;
4296 }
4297 
4298 
4299 /** feasibility check method of constraint handler for integral solutions */
4300 static
4301 SCIP_DECL_CONSCHECK(consCheckLogicor)
4302 { /*lint --e{715}*/
4303  SCIP_CONS* cons;
4304  SCIP_CONSDATA* consdata;
4305  int c;
4306 
4307  assert(conshdlr != NULL);
4308  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4309  assert(nconss == 0 || conss != NULL);
4310  assert(result != NULL);
4311 
4312  *result = SCIP_FEASIBLE;
4313 
4314  /* check all logic or constraints for feasibility */
4315  for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
4316  {
4317  cons = conss[c];
4318  consdata = SCIPconsGetData(cons);
4319  assert(consdata != NULL);
4320  if( checklprows || consdata->row == NULL || !SCIProwIsInLP(consdata->row) )
4321  {
4322  SCIP_Bool violated;
4323 
4324  SCIP_CALL( checkCons(scip, cons, sol, &violated) );
4325  if( violated )
4326  {
4327  /* constraint is violated */
4328  *result = SCIP_INFEASIBLE;
4329 
4330  if( printreason )
4331  {
4332 #ifndef NDEBUG
4333  int v;
4334  for( v = 0; v < consdata->nvars; ++v )
4335  {
4336  assert( consdata->vars[v] != NULL);
4337  assert( SCIPvarIsBinary(consdata->vars[v]) );
4338  assert( SCIPisFeasLT(scip, SCIPgetSolVal(scip, sol, consdata->vars[v]), 1.0) );
4339  }
4340 #endif
4341  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
4342  SCIPinfoMessage(scip, NULL, ";\n");
4343  SCIPinfoMessage(scip, NULL, "violation: all variables are set to zero\n");
4344  }
4345  }
4346  }
4347  }
4348 
4349  return SCIP_OKAY;
4350 }
4351 
4352 
4353 /** domain propagation method of constraint handler */
4354 static
4355 SCIP_DECL_CONSPROP(consPropLogicor)
4356 { /*lint --e{715}*/
4357  SCIP_CONSHDLRDATA* conshdlrdata;
4358  SCIP_Bool cutoff;
4359  SCIP_Bool reduceddom;
4360  SCIP_Bool addcut;
4361  SCIP_Bool mustcheck;
4362  int c;
4363 #ifndef NDEBUG
4364  SCIP_Bool inpresolve = (SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE);
4365 #endif
4366 
4367  assert(conshdlr != NULL);
4368  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4369  assert(nconss == 0 || conss != NULL);
4370  assert(result != NULL);
4371 
4372  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4373  assert(conshdlrdata != NULL);
4374 
4375  cutoff = FALSE;
4376  reduceddom = FALSE;
4377 
4378  /* propagate all useful logic or constraints */
4379  for( c = 0; c < nusefulconss && !cutoff; ++c )
4380  {
4381  assert(inpresolve || !(SCIPconsGetData(conss[c])->existmultaggr));
4382 
4383  SCIPdebugMsg(scip, " propagate constraint %s\n", SCIPconsGetName(conss[c]));
4384  SCIP_CALL( processWatchedVars(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &reduceddom, &addcut, &mustcheck) );
4385  }
4386 
4387  /* return the correct result */
4388  if( cutoff )
4389  *result = SCIP_CUTOFF;
4390  else if( reduceddom )
4391  *result = SCIP_REDUCEDDOM;
4392  else
4393  *result = SCIP_DIDNOTFIND;
4394 
4395  return SCIP_OKAY;
4396 }
4397 
4398 /** presolving method of constraint handler */
4399 static
4400 SCIP_DECL_CONSPRESOL(consPresolLogicor)
4401 { /*lint --e{715}*/
4402  SCIP_CONSHDLRDATA* conshdlrdata;
4403  SCIP_CONS* cons;
4404  SCIP_CONSDATA* consdata;
4405  unsigned char* entries;
4406  SCIP_Bool redundant;
4407  int c;
4408  int firstchange;
4409  int nentries;
4410  int oldnfixedvars;
4411  int oldnchgbds;
4412  int oldndelconss;
4413  int oldnupgdconss;
4414  int oldnchgcoefs;
4415 
4416  assert(conshdlr != NULL);
4417  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4418  assert(scip != NULL);
4419  assert(result != NULL);
4420 
4421  *result = SCIP_DIDNOTFIND;
4422 
4423  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4424  assert(conshdlrdata != NULL);
4425 
4426  nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
4427 
4428  oldnfixedvars = *nfixedvars;
4429  oldnchgbds = *nchgbds;
4430  oldndelconss = *ndelconss;
4431  oldnupgdconss = *nupgdconss;
4432  oldnchgcoefs = *nchgcoefs;
4433 
4434  firstchange = INT_MAX;
4435 
4436  SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
4437 
4438  /* process constraints */
4439  for( c = 0; c < nconss && *result != SCIP_CUTOFF && !SCIPisStopped(scip); ++c )
4440  {
4441  cons = conss[c];
4442  assert(cons != NULL);
4443  consdata = SCIPconsGetData(cons);
4444  assert(consdata != NULL);
4445 
4446  SCIPdebugMsg(scip, "presolving logic or constraint <%s>\n", SCIPconsGetName(cons));
4447 
4448  /* force presolving the constraint in the initial round */
4449  if( nrounds == 0 )
4450  {
4451  SCIP_CALL( SCIPenableConsPropagation(scip, cons) );
4452  }
4453 
4454  redundant = FALSE;
4455  if( !consdata->presolved )
4456  {
4457  /* remove all variables that are fixed to zero, check redundancy due to fixed-to-one variable */
4458  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, &redundant, nchgcoefs, naddconss, ndelconss) );
4459  }
4460 
4461  if( SCIPconsIsDeleted(cons) )
4462  continue;
4463 
4464  /* find pairs of negated variables in constraint: constraint is redundant */
4465  /* find sets of equal variables in constraint: multiple entries of variable can be replaced by single entry */
4466  if( !redundant )
4467  {
4468  SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, &redundant, nchgcoefs) );
4469  }
4470 
4471  if( redundant )
4472  {
4473  SCIPdebugMsg(scip, "logic or constraint <%s> is redundant\n", SCIPconsGetName(cons));
4474  SCIP_CALL( SCIPdelCons(scip, cons) );
4475  (*ndelconss)++;
4476  *result = SCIP_SUCCESS;
4477  continue;
4478  }
4479  else if( !SCIPconsIsModifiable(cons) )
4480  {
4481  if( consdata->nvars <= 2 )
4482  {
4483  SCIP_Bool cutoff;
4484 
4485  /* handle all cases with less than three variables in a logicor constraint */
4486  SCIP_CALL( fixDeleteOrUpgradeCons(scip, cons, conshdlrdata->eventhdlr, conshdlrdata->conshdlrlinear,
4487  conshdlrdata->conshdlrsetppc, nfixedvars, nchgbds, nchgcoefs, ndelconss, naddconss, nupgdconss, &cutoff) );
4488 
4489  if( cutoff )
4490  {
4491  *result = SCIP_CUTOFF;
4492  goto TERMINATE;
4493  }
4494  else if( *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds || *nchgcoefs > oldnchgcoefs
4495  || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4496  *result = SCIP_SUCCESS;
4497 
4498  if( SCIPconsIsDeleted(cons) )
4499  continue;
4500  }
4501  }
4502 
4503  /* perform dual reductions */
4504  if( conshdlrdata->dualpresolving && SCIPallowDualReds(scip) )
4505  {
4506  SCIP_CALL( dualPresolving(scip, cons, conshdlrdata->eventhdlr, nfixedvars, ndelconss, nchgcoefs, result) );
4507 
4508  /* if dual reduction deleted the constraint we take the next */
4509  if( !SCIPconsIsActive(cons) )
4510  continue;
4511 
4512  /* in dualpresolving we may have removed variables, so we need to take care of special cases */
4513  if( consdata->nvars <= 2 )
4514  {
4515  SCIP_Bool cutoff;
4516 
4517  /* handle all cases with less than three variables in a logicor constraint */
4518  SCIP_CALL( fixDeleteOrUpgradeCons(scip, cons, conshdlrdata->eventhdlr, conshdlrdata->conshdlrlinear,
4519  conshdlrdata->conshdlrsetppc, nfixedvars, nchgbds, nchgcoefs, ndelconss, naddconss, nupgdconss, &cutoff) );
4520 
4521  if( cutoff )
4522  {
4523  *result = SCIP_CUTOFF;
4524  goto TERMINATE;
4525  }
4526  else if( *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds || *nchgcoefs > oldnchgcoefs
4527  || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4528  *result = SCIP_SUCCESS;
4529 
4530  if( SCIPconsIsDeleted(cons) )
4531  continue;
4532  }
4533  }
4534 
4535  /* remember the first changed constraint to begin the next redundancy round with */
4536  if( firstchange == INT_MAX && consdata->changed )
4537  firstchange = c;
4538 
4539  assert(consdata->nvars >= 2 || SCIPconsIsModifiable(cons));
4540  }
4541 
4542  assert(*result != SCIP_CUTOFF);
4543 
4544  /* fast preprocessing of pairs of logic or constraints, used for equal constraints */
4545  if( firstchange < nconss && conshdlrdata->presolusehashing )
4546  {
4547  /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
4548  SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, ndelconss) );
4549  }
4550 
4551  /* preprocess pairs of logic or constraints and apply negated clique presolving */
4552  if( SCIPisPresolveFinished(scip) )
4553  {
4554  SCIP_Bool cutoff = FALSE;
4555 
4556  /* check constraints for redundancy */
4557  if( conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4558  {
4559  SCIP_CALL( removeRedundantConssAndNonzeros(scip, conss, nconss, &entries, &nentries, conshdlrdata->eventhdlr,
4560  conshdlrdata->usestrengthening, &firstchange, nfixedvars, ndelconss, nchgcoefs, &cutoff) );
4561 
4562  if( cutoff )
4563  {
4564  *result = SCIP_CUTOFF;
4565  goto TERMINATE;
4566  }
4567  }
4568 
4569  if( SCIPisPresolveFinished(scip) )
4570  {
4571  /* try to tighten constraints by reducing the number of variables in the constraints using implications and
4572  * cliques, also derive fixations through them, @see SCIPshrinkDisjunctiveVarSet()
4573  */
4574  if( conshdlrdata->useimplications && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4575  {
4576  SCIP_CALL( shortenConss(scip, conshdlrdata, conshdlrdata->eventhdlr, conss, nconss,
4577  &entries, &nentries, nfixedvars, ndelconss, nchgcoefs, &cutoff) );
4578 
4579  if( cutoff )
4580  {
4581  *result = SCIP_CUTOFF;
4582  goto TERMINATE;
4583  }
4584  }
4585 
4586  /* check for redundant constraints due to negated clique information */
4587  if( conshdlrdata->usenegatedclique && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
4588  {
4589  SCIP_CALL( removeConstraintsDueToNegCliques(scip, conshdlr, conshdlrdata->conshdlrsetppc,
4590  conshdlrdata->eventhdlr, conss, nconss, &entries, &nentries, nfixedvars, ndelconss,
4591  nupgdconss, nchgcoefs, &cutoff) );
4592 
4593  if( cutoff )
4594  {
4595  *result = SCIP_CUTOFF;
4596  goto TERMINATE;
4597  }
4598  }
4599  }
4600  }
4601 
4602  TERMINATE:
4603 
4604  SCIPfreeBufferArray(scip, &entries);
4605 
4606  return SCIP_OKAY;
4607 }
4608 
4609 
4610 /** propagation conflict resolving method of constraint handler */
4611 static
4612 SCIP_DECL_CONSRESPROP(consRespropLogicor)
4613 { /*lint --e{715}*/
4614  SCIP_CONSDATA* consdata;
4615 #ifndef NDEBUG
4616  SCIP_Bool infervarfound;
4617 #endif
4618  int v;
4619 
4620  assert(conshdlr != NULL);
4621  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4622  assert(cons != NULL);
4623  assert(infervar != NULL);
4624  assert(result != NULL);
4625 
4626  consdata = SCIPconsGetData(cons);
4627  assert(consdata != NULL);
4628 
4629  SCIPdebugMsg(scip, "conflict resolving method of logic or constraint handler\n");
4630 
4631  /* the only deductions are variables infered to 1.0 on logic or constraints where all other variables
4632  * are assigned to zero
4633  */
4634  assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5); /* the inference variable must be assigned to one */
4635 
4636 #ifndef NDEBUG
4637  infervarfound = FALSE;
4638 #endif
4639  for( v = 0; v < consdata->nvars; ++v )
4640  {
4641  if( consdata->vars[v] != infervar )
4642  {
4643  /* the reason variable must have been assigned to zero */
4644  assert(SCIPgetVarUbAtIndex(scip, consdata->vars[v], bdchgidx, FALSE) < 0.5);
4645  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
4646  }
4647 #ifndef NDEBUG
4648  else
4649  {
4650  assert(!infervarfound);
4651  infervarfound = TRUE;
4652  }
4653 #endif
4654  }
4655  assert(infervarfound);
4656 
4657  *result = SCIP_SUCCESS;
4658 
4659  return SCIP_OKAY;
4660 }
4661 
4662 
4663 /** variable rounding lock method of constraint handler */
4664 static
4665 SCIP_DECL_CONSLOCK(consLockLogicor)
4666 { /*lint --e{715}*/
4667  SCIP_CONSDATA* consdata;
4668  int i;
4669 
4670  consdata = SCIPconsGetData(cons);
4671  assert(consdata != NULL);
4672 
4673  /* lock every single coefficient */
4674  for( i = 0; i < consdata->nvars; ++i )
4675  {
4676  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos, nlocksneg) );
4677  }
4678 
4679  return SCIP_OKAY;
4680 }
4681 
4682 
4683 /** constraint activation notification method of constraint handler */
4684 static
4685 SCIP_DECL_CONSACTIVE(consActiveLogicor)
4686 { /*lint --e{715}*/
4687  SCIP_CONSHDLRDATA* conshdlrdata;
4688  SCIP_CONSDATA* consdata;
4689 
4690  assert(conshdlr != NULL);
4691  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4692  assert(cons != NULL);
4693  assert(SCIPconsIsTransformed(cons));
4694 
4695  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4696  assert(conshdlrdata != NULL);
4697  consdata = SCIPconsGetData(cons);
4698  assert(consdata != NULL);
4699  assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
4700 
4701  SCIPdebugMsg(scip, "activating information for logic or constraint <%s>\n", SCIPconsGetName(cons));
4702  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
4703 
4704  /* catch events on watched variables */
4705  if( consdata->watchedvar1 != -1 )
4706  {
4707  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[consdata->watchedvar1],
4708  SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4709  &consdata->filterpos1) );
4710  }
4711  if( consdata->watchedvar2 != -1 )
4712  {
4713  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[consdata->watchedvar2],
4714  SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4715  &consdata->filterpos2) );
4716  }
4717 
4718  return SCIP_OKAY;
4719 }
4720 
4721 
4722 /** constraint deactivation notification method of constraint handler */
4723 static
4724 SCIP_DECL_CONSDEACTIVE(consDeactiveLogicor)
4725 { /*lint --e{715}*/
4726  SCIP_CONSHDLRDATA* conshdlrdata;
4727  SCIP_CONSDATA* consdata;
4728 
4729  assert(conshdlr != NULL);
4730  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4731  assert(cons != NULL);
4732  assert(SCIPconsIsTransformed(cons));
4733 
4734  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4735  assert(conshdlrdata != NULL);
4736  consdata = SCIPconsGetData(cons);
4737  assert(consdata != NULL);
4738  assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
4739 
4740  SCIPdebugMsg(scip, "deactivating information for logic or constraint <%s>\n", SCIPconsGetName(cons));
4741  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
4742 
4743  /* drop events on watched variables */
4744  if( consdata->watchedvar1 != -1 )
4745  {
4746  assert(consdata->filterpos1 != -1);
4747  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar1],
4748  SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4749  consdata->filterpos1) );
4750  }
4751  if( consdata->watchedvar2 != -1 )
4752  {
4753  assert(consdata->filterpos2 != -1);
4754  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar2],
4755  SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4756  consdata->filterpos2) );
4757  }
4758 
4759  return SCIP_OKAY;
4760 }
4761 
4762 
4763 /** constraint display method of constraint handler */
4764 static
4765 SCIP_DECL_CONSPRINT(consPrintLogicor)
4766 { /*lint --e{715}*/
4767  assert( scip != NULL );
4768  assert( conshdlr != NULL );
4769  assert( cons != NULL );
4770 
4771  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file, FALSE) );
4772 
4773  return SCIP_OKAY;
4774 }
4775 
4776 /** constraint copying method of constraint handler */
4777 static
4778 SCIP_DECL_CONSCOPY(consCopyLogicor)
4779 { /*lint --e{715}*/
4780  SCIP_VAR** sourcevars;
4781  const char* consname;
4782  int nvars;
4783 
4784  /* get variables and coefficients of the source constraint */
4785  sourcevars = SCIPgetVarsLogicor(sourcescip, sourcecons);
4786  nvars = SCIPgetNVarsLogicor(sourcescip, sourcecons);
4787 
4788  if( name != NULL )
4789  consname = name;
4790  else
4791  consname = SCIPconsGetName(sourcecons);
4792 
4793  /* copy the logic using the linear constraint copy method */
4794  SCIP_CALL( SCIPcopyConsLinear(scip, cons, sourcescip, consname, nvars, sourcevars, NULL,
4795  1.0, SCIPinfinity(scip), varmap, consmap,
4796  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
4797  assert(cons != NULL);
4798 
4799  return SCIP_OKAY;
4800 }
4801 
4802 /** constraint parsing method of constraint handler */
4803 static
4804 SCIP_DECL_CONSPARSE(consParseLogicor)
4805 { /*lint --e{715}*/
4806  SCIP_VAR** vars;
4807  char* strcopy;
4808  char* endptr;
4809  char* startptr;
4810  int requiredsize;
4811  int varssize;
4812  int nvars;
4813 
4814  SCIPdebugMsg(scip, "parse <%s> as logicor constraint\n", str);
4815 
4816  *success = FALSE;
4817 
4818  /* cutoff "logicor" from the constraint string */
4819  startptr = strchr((char*)str, '(');
4820 
4821  if( startptr == NULL )
4822  {
4823  SCIPerrorMessage("missing starting character '(' parsing logicor\n");
4824  return SCIP_OKAY;
4825  }
4826 
4827  /* skip '(' */
4828  ++startptr;
4829 
4830  /* find end character ')' */
4831  endptr = strrchr(startptr, ')');
4832 
4833  if( endptr == NULL )
4834  {
4835  SCIPerrorMessage("missing ending character ')' parsing logicor\n");
4836  return SCIP_OKAY;
4837  }
4838  assert(endptr >= startptr);
4839 
4840  if( endptr > startptr )
4841  {
4842  /* copy string for parsing */
4843  SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, startptr, (int)(endptr-startptr)) );
4844 
4845  varssize = 100;
4846  nvars = 0;
4847 
4848  /* allocate buffer array for variables */
4849  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
4850 
4851  /* parse string */
4852  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4853 
4854  if( *success )
4855  {
4856  /* check if the size of the variable array was great enough */
4857  if( varssize < requiredsize )
4858  {
4859  /* reallocate memory */
4860  varssize = requiredsize;
4861  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
4862 
4863  /* parse string again with the correct size of the variable array */
4864  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4865  }
4866 
4867  assert(*success);
4868  assert(varssize >= requiredsize);
4869 
4870  /* create logicor constraint */
4871  SCIP_CALL( SCIPcreateConsLogicor(scip, cons, name, nvars, vars,
4872  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4873  }
4874 
4875  /* free buffers */
4876  SCIPfreeBufferArray(scip, &vars);
4877  SCIPfreeBufferArray(scip, &strcopy);
4878  }
4879  else
4880  {
4881  if( !modifiable )
4882  {
4883  SCIPerrorMessage("cannot create empty logicor constraint\n");
4884  return SCIP_OKAY;
4885  }
4886 
4887  /* create empty logicor constraint */
4888  SCIP_CALL( SCIPcreateConsLogicor(scip, cons, name, 0, NULL,
4889  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4890 
4891  *success = TRUE;
4892  }
4893 
4894  return SCIP_OKAY;
4895 }
4896 
4897 /** constraint method of constraint handler which returns the variables (if possible) */
4898 static
4899 SCIP_DECL_CONSGETVARS(consGetVarsLogicor)
4900 { /*lint --e{715}*/
4901  SCIP_CONSDATA* consdata;
4902 
4903  consdata = SCIPconsGetData(cons);
4904  assert(consdata != NULL);
4905 
4906  if( varssize < consdata->nvars )
4907  (*success) = FALSE;
4908  else
4909  {
4910  assert(vars != NULL);
4911 
4912  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
4913  (*success) = TRUE;
4914  }
4915 
4916  return SCIP_OKAY;
4917 }
4918 
4919 /** constraint method of constraint handler which returns the number of variables (if possible) */
4920 static
4921 SCIP_DECL_CONSGETNVARS(consGetNVarsLogicor)
4922 { /*lint --e{715}*/
4923  SCIP_CONSDATA* consdata;
4924 
4925  consdata = SCIPconsGetData(cons);
4926  assert(consdata != NULL);
4927 
4928  (*nvars) = consdata->nvars;
4929  (*success) = TRUE;
4930 
4931  return SCIP_OKAY;
4932 }
4933 
4934 /*
4935  * Callback methods of event handler
4936  */
4937 
4938 static
4939 SCIP_DECL_EVENTEXEC(eventExecLogicor)
4940 { /*lint --e{715}*/
4941  assert(eventhdlr != NULL);
4942  assert(eventdata != NULL);
4943  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
4944  assert(event != NULL);
4945 
4946  SCIPdebugMsg(scip, "exec method of event handler for logic or constraints\n");
4947 
4949  {
4950  SCIPdebugMsg(scip, "enabling constraint cons <%s> at depth %d\n", SCIPconsGetName((SCIP_CONS*)eventdata), SCIPgetDepth(scip));
4951 
4952  SCIP_CALL( SCIPenableCons(scip, (SCIP_CONS*)eventdata) );
4953  SCIP_CALL( SCIPenableConsPropagation(scip, (SCIP_CONS*)eventdata) );
4954  }
4955  else if( SCIPeventGetType(event) == SCIP_EVENTTYPE_UBTIGHTENED )
4956  {
4957  SCIP_CALL( SCIPenableConsPropagation(scip, (SCIP_CONS*)eventdata) );
4958  }
4959 
4961  {
4962  SCIP_VAR* var = SCIPeventGetVar(event);
4963  SCIP_CONS* cons = (SCIP_CONS*)eventdata;
4964  SCIP_CONSDATA* consdata;
4965 
4966  assert(cons != NULL);
4967  consdata = SCIPconsGetData(cons);
4968  assert(consdata != NULL);
4969 
4970  /* we only catch this event in presolving stage */
4971  assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING);
4972  assert(var != NULL);
4973 
4974  consdata->presolved = FALSE;
4975 
4977  {
4978  if( SCIPconsIsActive(cons) )
4979  {
4980  if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 )
4981  consdata->merged = FALSE;
4982 
4983  if( !consdata->existmultaggr )
4984  {
4986  consdata->existmultaggr = TRUE;
4987  }
4988  }
4989  }
4990  }
4991 
4992  return SCIP_OKAY;
4993 }
4994 
4995 
4996 /*
4997  * Callback methods of conflict handler
4998  */
4999 
5000 static
5001 SCIP_DECL_CONFLICTEXEC(conflictExecLogicor)
5002 { /*lint --e{715}*/
5003  SCIP_VAR** vars;
5004  int i;
5005 
5006  assert(conflicthdlr != NULL);
5007  assert(strcmp(SCIPconflicthdlrGetName(conflicthdlr), CONFLICTHDLR_NAME) == 0);
5008  assert(bdchginfos != NULL || nbdchginfos == 0);
5009  assert(result != NULL);
5010 
5011  *result = SCIP_DIDNOTRUN;
5012 
5013  /* don't process already resolved conflicts */
5014  if( resolved )
5015  return SCIP_OKAY;
5016 
5017  /* if the conflict consists of only two (binary) variables, it will be handled by the setppc conflict handler */
5018  if( nbdchginfos == 2 )
5019  return SCIP_OKAY;
5020 
5021  *result = SCIP_DIDNOTFIND;
5022 
5023  /* create array of variables in conflict constraint */
5024  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nbdchginfos) );
5025  for( i = 0; i < nbdchginfos; ++i )
5026  {
5027  assert(bdchginfos != NULL); /* for flexelint */
5028  assert(bdchginfos[i] != NULL);
5029 
5030  vars[i] = SCIPbdchginfoGetVar(bdchginfos[i]);
5031 
5032  /* we can only treat binary variables */
5033  if( !SCIPvarIsBinary(vars[i]) )
5034  break;
5035 
5036  /* if the variable is fixed to one in the conflict set, we have to use its negation */
5037  if( SCIPbdchginfoGetNewbound(bdchginfos[i]) > 0.5 )
5038  {
5039  SCIP_CALL( SCIPgetNegatedVar(scip, vars[i], &vars[i]) );
5040  }
5041  }
5042 
5043  if( i == nbdchginfos )
5044  {
5045  SCIP_CONS* cons;
5046  char consname[SCIP_MAXSTRLEN];
5047 
5048  /* create a constraint out of the conflict set */
5050  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, consname, nbdchginfos, vars,
5051  FALSE, separate, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
5052 
5053  /* add conflict to SCIP */
5054  SCIP_CALL( SCIPaddConflict(scip, node, cons, validnode, conftype, cutoffinvolved) );
5055 
5056  *result = SCIP_CONSADDED;
5057  }
5058 
5059  /* free temporary memory */
5060  SCIPfreeBufferArray(scip, &vars);
5061 
5062  return SCIP_OKAY;
5063 }
5064 
5065 
5066 /*
5067  * constraint specific interface methods
5068  */
5069 
5070 /** creates the handler for logic or constraints and includes it in SCIP */
5072  SCIP* scip /**< SCIP data structure */
5073  )
5074 {
5075  SCIP_CONSHDLRDATA* conshdlrdata;
5076  SCIP_CONSHDLR* conshdlr;
5077  SCIP_CONFLICTHDLR* conflicthdlr;
5078  SCIP_EVENTHDLR* eventhdlr;
5079 
5080  /* create event handler for events on watched variables */
5082  eventExecLogicor, NULL) );
5083 
5084  /* create conflict handler for logic or constraints */
5086  conflictExecLogicor, NULL) );
5087 
5088  /* create constraint handler data */
5089  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
5090 
5091  /* include constraint handler */
5094  consEnfolpLogicor, consEnfopsLogicor, consCheckLogicor, consLockLogicor,
5095  conshdlrdata) );
5096  assert(conshdlr != NULL);
5097 
5098  /* set non-fundamental callbacks via specific setter functions */
5099  SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveLogicor) );
5100  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyLogicor, consCopyLogicor) );
5101  SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveLogicor) );
5102  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteLogicor) );
5103  SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreLogicor) );
5104  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolLogicor) );
5105  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeLogicor) );
5106  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsLogicor) );
5107  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsLogicor) );
5108  SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreLogicor) );
5109  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpLogicor) );
5110  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseLogicor) );
5111  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolLogicor,CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
5112  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintLogicor) );
5113  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropLogicor, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
5115  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropLogicor) );
5116  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpLogicor, consSepasolLogicor, CONSHDLR_SEPAFREQ,
5118  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransLogicor) );
5119  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxLogicor) );
5120 
5121  conshdlrdata->conshdlrlinear = SCIPfindConshdlr(scip, "linear");
5122  conshdlrdata->conshdlrsetppc = SCIPfindConshdlr(scip, "setppc");
5123 
5124  if( conshdlrdata->conshdlrlinear != NULL )
5125  {
5126  /* include the linear constraint to logicor constraint upgrade in the linear constraint handler */
5128  }
5129 
5130  /* logic or constraint handler parameters */
5132  "constraints/logicor/presolpairwise",
5133  "should pairwise constraint comparison be performed in presolving?",
5134  &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
5136  "constraints/logicor/presolusehashing",
5137  "should hash table be used for detecting redundant constraints in advance",
5138  &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
5140  "constraints/logicor/dualpresolving",
5141  "should dual presolving steps be performed?",
5142  &conshdlrdata->dualpresolving, TRUE, DEFAULT_DUALPRESOLVING, NULL, NULL) );
5144  "constraints/logicor/negatedclique",
5145  "should negated clique information be used in presolving",
5146  &conshdlrdata->usenegatedclique, TRUE, DEFAULT_NEGATEDCLIQUE, NULL, NULL) );
5148  "constraints/logicor/implications",
5149  "should implications/cliques be used in presolving",
5150  &conshdlrdata->useimplications, TRUE, DEFAULT_IMPLICATIONS, NULL, NULL) );
5152  "constraints/logicor/strengthen",
5153  "should pairwise constraint comparison try to strengthen constraints by removing superflous non-zeros?",
5154  &conshdlrdata->usestrengthening, TRUE, DEFAULT_STRENGTHEN, NULL, NULL) );
5155 
5156  return SCIP_OKAY;
5157 }
5158 
5159 
5160 /** creates and captures a logic or constraint
5161  *
5162  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5163  */
5165  SCIP* scip, /**< SCIP data structure */
5166  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5167  const char* name, /**< name of constraint */
5168  int nvars, /**< number of variables in the constraint */
5169  SCIP_VAR** vars, /**< array with variables of constraint entries */
5170  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5171  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5172  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5173  * Usually set to TRUE. */
5174  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5175  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5176  SCIP_Bool check, /**< should the constraint be checked for feasibility?
5177  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5178  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5179  * Usually set to TRUE. */
5180  SCIP_Bool local, /**< is constraint only valid locally?
5181  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5182  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5183  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5184  * adds coefficients to this constraint. */
5185  SCIP_Bool dynamic, /**< is constraint subject to aging?
5186  * Usually set to FALSE. Set to TRUE for own cuts which
5187  * are separated as constraints. */
5188  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5189  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5190  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5191  * if it may be moved to a more global node?
5192  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5193  )
5194 {
5195  SCIP_CONSHDLR* conshdlr;
5196  SCIP_CONSDATA* consdata;
5197 
5198  assert(scip != NULL);
5199 
5200  /* find the logicor constraint handler */
5201  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5202  if( conshdlr == NULL )
5203  {
5204  SCIPerrorMessage("logic or constraint handler not found\n");
5205  return SCIP_INVALIDCALL;
5206  }
5207 
5208  /* create the constraint specific data */
5209  SCIP_CALL( consdataCreate(scip, &consdata, nvars, vars) );
5210 
5211  /* create constraint */
5212  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5213  local, modifiable, dynamic, removable, stickingatnode) );
5214 
5215  if( SCIPisTransformed(scip) && SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
5216  {
5217  SCIP_CONSHDLRDATA* conshdlrdata;
5218  int v;
5219 
5220  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5221  assert(conshdlrdata != NULL);
5222 
5223  for( v = consdata->nvars - 1; v >= 0; --v )
5224  {
5225  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
5226  (SCIP_EVENTDATA*)(*cons), NULL) );
5227  }
5228  }
5229 
5230  return SCIP_OKAY;
5231 }
5232 
5233 /** creates and captures a logicor constraint
5234  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
5235  * method SCIPcreateConsLogicor(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
5236  *
5237  * @see SCIPcreateConsLogicor() for information about the basic constraint flag configuration
5238  *
5239  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5240  */
5242  SCIP* scip, /**< SCIP data structure */
5243  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5244  const char* name, /**< name of constraint */
5245  int nvars, /**< number of variables in the constraint */
5246  SCIP_VAR** vars /**< array with variables of constraint entries */
5247  )
5248 {
5249  assert(scip != NULL);
5250 
5251  SCIP_CALL( SCIPcreateConsLogicor(scip, cons, name, nvars, vars,
5252  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
5253 
5254  return SCIP_OKAY;
5255 }
5256 
5257 /** adds coefficient in logic or constraint */
5259  SCIP* scip, /**< SCIP data structure */
5260  SCIP_CONS* cons, /**< logicor constraint */
5261  SCIP_VAR* var /**< variable to add to the constraint */
5262  )
5263 {
5264  assert(var != NULL);
5265 
5266  /*debugMsg(scip, "adding variable <%s> to logicor constraint <%s>\n",
5267  SCIPvarGetName(var), SCIPconsGetName(cons));*/
5268 
5269  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5270  {
5271  SCIPerrorMessage("constraint is not a logic or constraint\n");
5272  return SCIP_INVALIDDATA;
5273  }
5274 
5275  SCIP_CALL( addCoef(scip, cons, var) );
5276 
5277  return SCIP_OKAY;
5278 }
5279 
5280 /** gets number of variables in logic or constraint */
5282  SCIP* scip, /**< SCIP data structure */
5283  SCIP_CONS* cons /**< constraint data */
5284  )
5285 {
5286  SCIP_CONSDATA* consdata;
5287 
5288  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5289  {
5290  SCIPerrorMessage("constraint is not a logic or constraint\n");
5291  SCIPABORT();
5292  return -1; /*lint !e527*/
5293  }
5294 
5295  consdata = SCIPconsGetData(cons);
5296  assert(consdata != NULL);
5297 
5298  return consdata->nvars;
5299 }
5300 
5301 /** gets array of variables in logic or constraint */
5303  SCIP* scip, /**< SCIP data structure */
5304  SCIP_CONS* cons /**< constraint data */
5305  )
5306 {
5307  SCIP_CONSDATA* consdata;
5308 
5309  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5310  {
5311  SCIPerrorMessage("constraint is not a logic or constraint\n");
5312  SCIPABORT();
5313  return NULL; /*lint !e527*/
5314  }
5315 
5316  consdata = SCIPconsGetData(cons);
5317  assert(consdata != NULL);
5318 
5319  return consdata->vars;
5320 }
5321 
5322 /** gets the dual solution of the logic or constraint in the current LP */
5324  SCIP* scip, /**< SCIP data structure */
5325  SCIP_CONS* cons /**< constraint data */
5326  )
5327 {
5328  SCIP_CONSDATA* consdata;
5329 
5330  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5331  {
5332  SCIPerrorMessage("constraint is not a logic or constraint\n");
5333  SCIPABORT();
5334  return SCIP_INVALID; /*lint !e527*/
5335  }
5336 
5337  consdata = SCIPconsGetData(cons);
5338  assert(consdata != NULL);
5339 
5340  if( consdata->row != NULL )
5341  return SCIProwGetDualsol(consdata->row);
5342  else
5343  return 0.0;
5344 }
5345 
5346 /** gets the dual Farkas value of the logic or constraint in the current infeasible LP */
5348  SCIP* scip, /**< SCIP data structure */
5349  SCIP_CONS* cons /**< constraint data */
5350  )
5351 {
5352  SCIP_CONSDATA* consdata;
5353 
5354  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5355  {
5356  SCIPerrorMessage("constraint is not a logic or constraint\n");
5357  SCIPABORT();
5358  return SCIP_INVALID; /*lint !e527*/
5359  }
5360 
5361  consdata = SCIPconsGetData(cons);
5362  assert(consdata != NULL);
5363 
5364  if( consdata->row != NULL )
5365  return SCIProwGetDualfarkas(consdata->row);
5366  else
5367  return 0.0;
5368 }
5369 
5370 /** returns the linear relaxation of the given logic or constraint; may return NULL if no LP row was yet created;
5371  * the user must not modify the row!
5372  */
5374  SCIP* scip, /**< SCIP data structure */
5375  SCIP_CONS* cons /**< constraint data */
5376  )
5377 {
5378  SCIP_CONSDATA* consdata;
5379 
5380  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5381  {
5382  SCIPerrorMessage("constraint is not a logic or constraint\n");
5383  SCIPABORT();
5384  return NULL; /*lint !e527*/
5385  }
5386 
5387  consdata = SCIPconsGetData(cons);
5388  assert(consdata != NULL);
5389 
5390  return consdata->row;
5391 }
5392 
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPconsGetPos(SCIP_CONS *cons)
Definition: cons.c:8086
static SCIP_DECL_CONSCHECK(consCheckLogicor)
SCIP_RETCODE SCIPdisableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1807
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4221
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
static SCIP_DECL_CONSPRESOL(consPresolLogicor)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2167
#define DEFAULT_PRESOLUSEHASHING
Definition: cons_logicor.c:88
SCIP_EXPORT SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:16880
static SCIP_RETCODE removeRedundantCons(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1, int *ndelconss)
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
#define NULL
Definition: def.h:253
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:686
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:585
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2364
SCIP_EXPORT SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16893
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:876
#define DEFAULT_PRESOLPAIRWISE
Definition: cons_logicor.c:84
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:16986
#define CONSHDLR_DELAYSEPA
Definition: cons_logicor.c:68
public methods for SCIP parameter handling
#define SCIP_EVENTTYPE_VARFIXED
Definition: type_event.h:58
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1994
static SCIP_DECL_CONSINITLP(consInitlpLogicor)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:452
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7442
SCIP_Bool SCIPisGE(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_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:933
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8315
SCIP_EXPORT int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3241
public methods for memory management
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:307
SCIP_RETCODE SCIPshrinkDisjunctiveVarSet(SCIP *scip, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Bool *redundants, int nvars, int *nredvars, int *nglobalred, SCIP_Bool *setredundant, SCIP_Bool *glbinfeas, SCIP_Bool fullshortening)
Definition: presolve.c:975
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_EXPORT SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
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:165
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4200
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:654
#define SCIP_MAXSTRLEN
Definition: def.h:274
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1483
public methods for conflict handler plugins and conflict analysis
static SCIP_DECL_CONSEXITPRE(consExitpreLogicor)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:122
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5637
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2425
static SCIP_DECL_CONSPRINT(consPrintLogicor)
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:815
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
Definition: cons_logicor.c:323
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1217
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
int SCIPconsGetValidDepth(SCIP_CONS *cons)
Definition: cons.c:8159
static SCIP_DECL_CONFLICTEXEC(conflictExecLogicor)
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 SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:769
SCIP_Bool SCIPconsIsAdded(SCIP_CONS *cons)
Definition: cons.c:8505
static SCIP_RETCODE disableCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPparseVarsList(SCIP *scip, const char *str, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize, char **endptr, char delimiter, SCIP_Bool *success)
Definition: scip_var.c:600
static SCIP_DECL_CONSDEACTIVE(consDeactiveLogicor)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3009
static SCIP_DECL_EVENTEXEC(eventExecLogicor)
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16918
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_logicor.c:521
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:314
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1987
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8137
#define CONSHDLR_DELAYPROP
Definition: cons_logicor.c:69
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17200
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16903
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#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)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8245
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:276
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:562
static SCIP_DECL_CONSEXITSOL(consExitsolLogicor)
static SCIP_DECL_CONSSEPALP(consSepalpLogicor)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2122
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17025
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 SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:47
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16857
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
#define CONSHDLR_NAME
Definition: cons_logicor.c:57
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:524
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:150
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:838
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
public methods for SCIP variables
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
Definition: scip_cons.c:500
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4291
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:558
static SCIP_DECL_HASHGETKEY(hashGetKeyLogicorcons)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:356
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:73
static SCIP_RETCODE switchWatchedvars(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
Definition: cons_logicor.c:380
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip_cons.c:1460
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
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2077
public methods for numerical tolerances
SCIP_Real SCIPgetDualsolLogicor(SCIP *scip, SCIP_CONS *cons)
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:2113
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2838
static SCIP_RETCODE conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_logicor.c:216
public methods for querying solving statistics
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17177
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:64
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3098
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)
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:129
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1530
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3240
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:92
static SCIP_DECL_HASHKEYVAL(hashKeyValLogicorcons)
public methods for managing constraints
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10571
#define DEFAULT_DUALPRESOLVING
Definition: cons_logicor.c:89
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
static SCIP_DECL_CONSACTIVE(consActiveLogicor)
SCIP_RETCODE SCIPaddCoefLogicor(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
#define SCIP_PRESOLTIMING_MEDIUM
Definition: type_timing.h:44
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
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)
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_EXPORT SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17168
#define CONSHDLR_ENFOPRIORITY
Definition: cons_logicor.c:60
static SCIP_DECL_CONSTRANS(consTransLogicor)
SCIP_EXPORT int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17630
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1406
public methods for event handler plugins and event handlers
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
Definition: scip_general.c:595
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_Bool SCIPconsIsPropagationEnabled(SCIP_CONS *cons)
Definition: cons.c:8194
SCIP_RETCODE SCIPaddConflict(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_prob.c:3223
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1442
static SCIP_DECL_CONSRESPROP(consRespropLogicor)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
SCIP_EXPORT SCIP_RETCODE SCIPvarGetAggregatedObj(SCIP_VAR *var, SCIP_Real *aggrobj)
Definition: var.c:17222
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:47
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:87
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)
#define EVENTHDLR_NAME
Definition: cons_logicor.c:77
SCIP_RETCODE SCIPwriteVarsList(SCIP *scip, FILE *file, SCIP_VAR **vars, int nvars, SCIP_Bool type, char delimiter)
Definition: scip_var.c:282
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_logicor.c:178
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7485
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 SCIPdisableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1917
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:476
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8106
#define SCIP_CALL(x)
Definition: def.h:365
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:493
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:631
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
#define CONFLICTHDLR_NAME
Definition: cons_logicor.c:80
SCIP_RETCODE SCIPgetBinvarRepresentatives(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **repvars, SCIP_Bool *negated)
Definition: scip_var.c:1647
Definition: grphload.c:88
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
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:51
SCIP_EXPORT void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
public methods for constraint handler plugins and constraints
methods commonly used for presolving
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1748
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8345
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
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:111
SCIP_Real SCIProwGetDualfarkas(SCIP_ROW *row)
Definition: lp.c:16999
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 SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:129
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:219
public data structures and miscellaneous methods
static SCIP_DECL_CONSGETVARS(consGetVarsLogicor)
SCIP_EXPORT SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17178
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4376
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2163
#define CONFLICTHDLR_DESC
Definition: cons_logicor.c:81
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:637
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition: scip_lp.c:1611
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:390
SCIP_Real SCIPgetDualfarkasLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2891
SCIP_EXPORT SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11712
static SCIP_DECL_CONSENFOLP(consEnfolpLogicor)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:331
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_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17362
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2472
static void consdataSort(SCIP_CONSDATA *consdata)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4211
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip_var.c:8506
#define CONSHDLR_MAXPREROUNDS
Definition: cons_logicor.c:67
#define MAX_CONSLENGTH
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:1268
public methods for LP management
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8385
public methods for cuts and aggregation rows
SCIP_EXPORT SCIP_Longint SCIPvarGetNBranchingsCurrentRun(SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: var.c:15232
#define MAXCOMPARISONS
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
static SCIP_DECL_CONSCOPY(consCopyLogicor)
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:124
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8255
const char * SCIPconflicthdlrGetName(SCIP_CONFLICTHDLR *conflicthdlr)
Definition: conflict.c:761
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8180
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:65
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPenableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1773
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8335
static SCIP_RETCODE strengthenConss(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_HASHMAP *varstopos, SCIP_CONS ***occurlist, int *noccurlistentries, int occurlistlength, SCIP_EVENTHDLR *eventhdlr, int *ndelconss, int *nchgcoefs)
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17408
SCIP_RETCODE SCIPaddConsAge(SCIP *scip, SCIP_CONS *cons, SCIP_Real deltaage)
Definition: scip_cons.c:1691
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:94
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_logicor.c:191
static SCIP_DECL_CONSFREE(consFreeLogicor)
public methods for the LP relaxation, rows and columns
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2130
SCIP_EXPORT int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3184
static SCIP_RETCODE createRow(SCIP *scip, SCIP_CONS *cons)
#define DEFAULT_NEGATEDCLIQUE
Definition: cons_logicor.c:90
#define HASHSIZE_LOGICORCONS
Definition: cons_logicor.c:87
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars)
Definition: cons_logicor.c:255
SCIP_RETCODE SCIPenableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1887
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17418
methods for sorting joint arrays of various types
#define SCIP_LONGINT_FORMAT
Definition: def.h:156
static SCIP_DECL_CONSENFORELAX(consEnforelaxLogicor)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:220
static SCIP_RETCODE processWatchedVars(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, SCIP_Bool *reduceddom, SCIP_Bool *addcut, SCIP_Bool *mustcheck)
#define CONSHDLR_PRESOLTIMING
Definition: cons_logicor.c:72
public methods for managing events
general public methods
SCIP_EXPORT SCIP_VAR * SCIPbdchginfoGetVar(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:17954
#define MAX(x, y)
Definition: def.h:222
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLogicor)
#define CONSHDLR_DESC
Definition: cons_logicor.c:58
#define CONSHDLR_PROPFREQ
Definition: cons_logicor.c:63
static SCIP_DECL_CONSPARSE(consParseLogicor)
#define CONSHDLR_EAGERFREQ
Definition: cons_logicor.c:64
public methods for solutions
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8265
SCIP_RETCODE SCIPincludeConshdlrLogicor(SCIP *scip)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
public methods for conflict analysis handlers
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17352
public methods for the probing mode
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_logicor.c:165
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:677
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1539
static SCIP_DECL_CONSINITPRE(consInitpreLogicor)
static SCIP_RETCODE removeRedundantConss(SCIP *scip, SCIP_CONS *cons, SCIP_HASHMAP *varstopos, SCIP_CONS ***occurlist, int *noccurlistentries, int occurlistlength, int *ndelconss)
public methods for message output
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:6831
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10263
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2925
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8076
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
static SCIP_DECL_CONSPROP(consPropLogicor)
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8205
#define SCIP_Real
Definition: def.h:164
SCIP_RETCODE SCIPcreateConsBasicLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:133
SCIP_RETCODE SCIPincludeConflicthdlrBasic(SCIP *scip, SCIP_CONFLICTHDLR **conflicthdlrptr, const char *name, const char *desc, int priority, SCIP_DECL_CONFLICTEXEC((*conflictexec)), SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
Definition: scip_conflict.c:98
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8096
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_CONSGETNVARS(consGetNVarsLogicor)
public methods for message handling
#define CONSHDLR_SEPAPRIORITY
Definition: cons_logicor.c:59
#define SCIP_INVALID
Definition: def.h:184
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1848
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
#define SCIP_Longint
Definition: def.h:149
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8355
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
SCIP_EXPORT SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:10972
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2032
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:344
SCIP_ROW * SCIPgetRowLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1018
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17045
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2765
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:50
SCIP_EXPORT SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:11804
#define CONSHDLR_PROP_TIMING
Definition: cons_logicor.c:73
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
static SCIP_RETCODE dualPresolving(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int *nfixedvars, int *ndelconss, int *nchgcoefs, SCIP_RESULT *result)
Definition: cons_logicor.c:603
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:120
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:9119
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:198
#define CONSHDLR_CHECKPRIORITY
Definition: cons_logicor.c:61
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:427
SCIP_EXPORT int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17704
int SCIPgetNImplications(SCIP *scip)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1109
SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:355
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_logicor.c:451
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:792
static SCIP_DECL_CONSSEPASOL(consSepasolLogicor)
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:265
#define SCIPcombineTwoInt(a, b)
Definition: pub_misc.h:499
#define SCIPABORT()
Definition: def.h:337
public methods for global and local (sub)problems
#define CONFLICTHDLR_PRIORITY
Definition: cons_logicor.c:82
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8295
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, SCIP_Bool *separated, SCIP_Bool *reduceddom)
SCIP_EXPORT SCIP_Real SCIPbdchginfoGetNewbound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:17944
SCIP_Longint SCIPgetNConflictConssApplied(SCIP *scip)
static void findShortestOccurlist(SCIP_VAR **vars, int nvars, SCIP_HASHMAP *varstopos, SCIP_CONS ***occurlist, int *noccurlistentries, int occurlistlength, int *nentries, SCIP_CONS ***shortestlist)
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:608
static SCIP_RETCODE removeRedundantNonZeros(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *artvar, int artpos, SCIP_HASHMAP *varstopos, SCIP_CONS ***occurlist, int *noccurlistentries, int occurlistlength, SCIP_EVENTHDLR *eventhdlr, int *nchgcoefs, SCIP_Bool *deleted)
SCIP_EXPORT int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17035
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8325
#define DEFAULT_STRENGTHEN
Definition: cons_logicor.c:85
#define DEFAULT_IMPLICATIONS
Definition: cons_logicor.c:91
static SCIP_RETCODE mergeMultiples(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, unsigned char **entries, int *nentries, SCIP_Bool *redundant, int *nchgcoefs)
SCIP_EXPORT int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11436
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
int SCIPgetNRuns(SCIP *scip)
memory allocation routines