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