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