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