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