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