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