Scippy

SCIP

Solving Constraint Integer Programs

cons_and.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-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_and.c
17  * @brief Constraint handler for AND-constraints, \f$r = x_1 \wedge x_2 \wedge \dots \wedge x_n\f$
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  * @author Michael Winkler
21  *
22  * This constraint handler deals with AND-constraints. These are constraint of the form:
23  *
24  * \f[
25  * r = x_1 \wedge x_2 \wedge \dots \wedge x_n
26  * \f]
27  *
28  * where \f$x_i\f$ is a binary variable for all \f$i\f$. Hence, \f$r\f$ is also of binary type. The variable \f$r\f$ is
29  * called resultant and the \f$x\f$'s operators.
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include <assert.h>
35 #include <string.h>
36 
37 #include "scip/cons_and.h"
38 #include "scip/cons_linear.h"
39 #include "scip/cons_logicor.h"
40 #include "scip/cons_setppc.h"
41 #include "scip/cons_nonlinear.h"
42 #include "scip/cons_setppc.h"
44 #include "scip/pub_misc.h"
45 #include "scip/debug.h"
46 
47 
48 /* constraint handler properties */
49 #define CONSHDLR_NAME "and"
50 #define CONSHDLR_DESC "constraint handler for AND-constraints: r = and(x1, ..., xn)"
51 #define CONSHDLR_SEPAPRIORITY +850100 /**< priority of the constraint handler for separation */
52 #define CONSHDLR_ENFOPRIORITY -850100 /**< priority of the constraint handler for constraint enforcing */
53 #define CONSHDLR_CHECKPRIORITY -850100 /**< priority of the constraint handler for checking feasibility */
54 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
55 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
56 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
57  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
58 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
59 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
60 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
61 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
62 
63 #define CONSHDLR_PRESOLTIMING (SCIP_PRESOLTIMING_FAST | SCIP_PRESOLTIMING_EXHAUSTIVE)
64 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
65 
66 #define EVENTHDLR_NAME "and"
67 #define EVENTHDLR_DESC "bound change event handler for AND-constraints"
68 
69 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
70 #define DEFAULT_LINEARIZE FALSE /**< should constraint get linearized and removed? */
71 #define DEFAULT_ENFORCECUTS TRUE /**< should cuts be separated during LP enforcing? */
72 #define DEFAULT_AGGRLINEARIZATION FALSE /**< should an aggregated linearization be used? */
73 #define DEFAULT_UPGRRESULTANT TRUE /**< should all binary resultant variables be upgraded to implicit binary variables */
74 #define DEFAULT_DUALPRESOLVING TRUE /**< should dual presolving be performed? */
75 
76 #define HASHSIZE_ANDCONS 500 /**< minimal size of hash table in and constraint tables */
77 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
78 #define NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
79 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
80 #define EXPRGRAPHREFORM_PRIORITY 100000 /**< priority of expression graph node reformulation method */
81 
82 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
83 
84 /*
85  * Data structures
86  */
87 
88 /** constraint data for AND-constraints */
89 struct SCIP_ConsData
90 {
91  SCIP_VAR** vars; /**< variables in the AND-constraint */
92  SCIP_VAR* resvar; /**< resultant variable */
93  SCIP_ROW** rows; /**< rows for linear relaxation of AND-constraint */
94  SCIP_ROW* aggrrow; /**< aggregated row for linear relaxation of AND-constraint */
95  int nvars; /**< number of variables in AND-constraint */
96  int varssize; /**< size of vars array */
97  int nrows; /**< number of rows for linear relaxation of AND-constraint */
98  int watchedvar1; /**< position of first watched operator variable */
99  int watchedvar2; /**< position of second watched operator variable */
100  int filterpos1; /**< event filter position of first watched operator variable */
101  int filterpos2; /**< event filter position of second watched operator variable */
102  unsigned int propagated:1; /**< is constraint already preprocessed/propagated? */
103  unsigned int nofixedzero:1; /**< is none of the operator variables fixed to FALSE? */
104  unsigned int impladded:1; /**< were the implications of the constraint already added? */
105  unsigned int opimpladded:1; /**< was the implication for 2 operands with fixed resultant added? */
106  unsigned int sorted:1; /**< are the constraint's variables sorted? */
107  unsigned int changed:1; /**< was constraint changed since last pair preprocessing round? */
108  unsigned int merged:1; /**< are the constraint's equal variables already merged? */
109  unsigned int checkwhenupgr:1; /**< if AND-constraint is upgraded to an logicor constraint or the and-
110  * constraint is linearized, should the check flag be set to true, even
111  * if the AND-constraint has a check flag set to false? */
112  unsigned int notremovablewhenupgr:1;/**< if AND-constraint is upgraded to an logicor constraint or the and-
113  * constraint is linearized, should the removable flag be set to false,
114  * even if the AND-constraint has a removable flag set to true? */
115 };
116 
117 /** constraint handler data */
118 struct SCIP_ConshdlrData
119 {
120  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events on watched variables */
121  SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
122  SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
123  SCIP_Bool linearize; /**< should constraint get linearized and removed? */
124  SCIP_Bool enforcecuts; /**< should cuts be separated during LP enforcing? */
125  SCIP_Bool aggrlinearization; /**< should an aggregated linearization be used? */
126  SCIP_Bool upgrresultant; /**< upgrade binary resultant variable to an implicit binary variable */
127  SCIP_Bool dualpresolving; /**< should dual presolving be performed? */
128 };
129 
130 
131 /*
132  * Propagation rules
133  */
134 
135 enum Proprule
136 {
137  PROPRULE_INVALID = 0, /**< propagation was applied without a specific propagation rule */
138  PROPRULE_1 = 1, /**< v_i = FALSE => r = FALSE */
139  PROPRULE_2 = 2, /**< r = TRUE => v_i = TRUE for all i */
140  PROPRULE_3 = 3, /**< v_i = TRUE for all i => r = TRUE */
141  PROPRULE_4 = 4 /**< r = FALSE, v_i = TRUE for all i except j => v_j = FALSE */
142 };
143 typedef enum Proprule PROPRULE;
145 
146 /*
147  * Local methods
148  */
149 
150 /** installs rounding locks for the given variable in the given AND-constraint */
151 static
153  SCIP* scip, /**< SCIP data structure */
154  SCIP_CONS* cons, /**< constraint data */
155  SCIP_VAR* var /**< variable of constraint entry */
156  )
157 {
158  /* rounding in both directions may violate the constraint */
159  SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
160 
161  return SCIP_OKAY;
162 }
163 
164 /** removes rounding locks for the given variable in the given AND-constraint */
165 static
167  SCIP* scip, /**< SCIP data structure */
168  SCIP_CONS* cons, /**< constraint data */
169  SCIP_VAR* var /**< variable of constraint entry */
170  )
171 {
172  /* rounding in both directions may violate the constraint */
173  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
174 
175  return SCIP_OKAY;
176 }
177 
178 /** creates constraint handler data */
179 static
181  SCIP* scip, /**< SCIP data structure */
182  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
183  SCIP_EVENTHDLR* eventhdlr /**< event handler */
184  )
185 {
186  assert(scip != NULL);
187  assert(conshdlrdata != NULL);
188  assert(eventhdlr != NULL);
189 
190  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
191 
192  /* set event handler for catching bound change events on variables */
193  (*conshdlrdata)->eventhdlr = eventhdlr;
194 
195  return SCIP_OKAY;
196 }
197 
198 /** frees constraint handler data */
199 static
201  SCIP* scip, /**< SCIP data structure */
202  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
203  )
204 {
205  assert(conshdlrdata != NULL);
206  assert(*conshdlrdata != NULL);
207 
208  SCIPfreeBlockMemory(scip, conshdlrdata);
209 
210  return SCIP_OKAY;
211 }
212 
213 /** catches events for the watched variable at given position */
214 static
216  SCIP* scip, /**< SCIP data structure */
217  SCIP_CONSDATA* consdata, /**< AND-constraint data */
218  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
219  int pos, /**< array position of variable to catch bound change events for */
220  int* filterpos /**< pointer to store position of event filter entry */
221  )
222 {
223  assert(consdata != NULL);
224  assert(consdata->vars != NULL);
225  assert(eventhdlr != NULL);
226  assert(0 <= pos && pos < consdata->nvars);
227  assert(filterpos != NULL);
228 
229  /* catch tightening events for lower bound and relaxed events for upper bounds on watched variable */
231  eventhdlr, (SCIP_EVENTDATA*)consdata, filterpos) );
232 
233  return SCIP_OKAY;
234 }
235 
236 
237 /** drops events for the watched variable at given position */
238 static
240  SCIP* scip, /**< SCIP data structure */
241  SCIP_CONSDATA* consdata, /**< AND-constraint data */
242  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
243  int pos, /**< array position of watched variable to drop bound change events for */
244  int filterpos /**< position of event filter entry */
245  )
246 {
247  assert(consdata != NULL);
248  assert(consdata->vars != NULL);
249  assert(eventhdlr != NULL);
250  assert(0 <= pos && pos < consdata->nvars);
251  assert(filterpos >= 0);
252 
253  /* drop tightening events for lower bound and relaxed events for upper bounds on watched variable */
255  eventhdlr, (SCIP_EVENTDATA*)consdata, filterpos) );
256 
257  return SCIP_OKAY;
258 }
259 
260 /** catches needed events on all variables of constraint, except the special ones for watched variables */
261 static
263  SCIP* scip, /**< SCIP data structure */
264  SCIP_CONSDATA* consdata, /**< AND-constraint data */
265  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
266  )
267 {
268  int i;
269 
270  assert(consdata != NULL);
271 
272  /* catch bound change events for both bounds on resultant variable */
273  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->resvar, SCIP_EVENTTYPE_BOUNDCHANGED,
274  eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
275 
276  /* catch tightening events for upper bound and relaxed events for lower bounds on operator variables */
277  for( i = 0; i < consdata->nvars; ++i )
278  {
280  eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
281  }
282 
283  return SCIP_OKAY;
284 }
285 
286 /** drops events on all variables of constraint, except the special ones for watched variables */
287 static
289  SCIP* scip, /**< SCIP data structure */
290  SCIP_CONSDATA* consdata, /**< AND-constraint data */
291  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
292  )
293 {
294  int i;
295 
296  assert(consdata != NULL);
297 
298  /* drop bound change events for both bounds on resultant variable */
299  SCIP_CALL( SCIPdropVarEvent(scip, consdata->resvar, SCIP_EVENTTYPE_BOUNDCHANGED,
300  eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
301 
302  /* drop tightening events for upper bound and relaxed events for lower bounds on operator variables */
303  for( i = 0; i < consdata->nvars; ++i )
304  {
306  eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
307  }
308 
309  return SCIP_OKAY;
310 }
311 
312 /** stores the given variable numbers as watched variables, and updates the event processing */
313 static
315  SCIP* scip, /**< SCIP data structure */
316  SCIP_CONSDATA* consdata, /**< AND-constraint data */
317  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
318  int watchedvar1, /**< new first watched variable */
319  int watchedvar2 /**< new second watched variable */
320  )
321 {
322  assert(consdata != NULL);
323  assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
324  assert(watchedvar1 != -1 || watchedvar2 == -1);
325  assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
326  assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
327 
328  /* if one watched variable is equal to the old other watched variable, just switch positions */
329  if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
330  {
331  int tmp;
332 
333  tmp = consdata->watchedvar1;
334  consdata->watchedvar1 = consdata->watchedvar2;
335  consdata->watchedvar2 = tmp;
336  tmp = consdata->filterpos1;
337  consdata->filterpos1 = consdata->filterpos2;
338  consdata->filterpos2 = tmp;
339  }
340  assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
341  assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
342 
343  /* drop events on old watched variables */
344  if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
345  {
346  assert(consdata->filterpos1 != -1);
347  SCIP_CALL( consdataDropWatchedEvents(scip, consdata, eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
348  }
349  if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
350  {
351  assert(consdata->filterpos2 != -1);
352  SCIP_CALL( consdataDropWatchedEvents(scip, consdata, eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
353  }
354 
355  /* catch events on new watched variables */
356  if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
357  {
358  SCIP_CALL( consdataCatchWatchedEvents(scip, consdata, eventhdlr, watchedvar1, &consdata->filterpos1) );
359  }
360  if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
361  {
362  SCIP_CALL( consdataCatchWatchedEvents(scip, consdata, eventhdlr, watchedvar2, &consdata->filterpos2) );
363  }
364 
365  /* set the new watched variables */
366  consdata->watchedvar1 = watchedvar1;
367  consdata->watchedvar2 = watchedvar2;
368 
369  return SCIP_OKAY;
370 }
371 
372 /** ensures, that the vars array can store at least num entries */
373 static
375  SCIP* scip, /**< SCIP data structure */
376  SCIP_CONSDATA* consdata, /**< linear constraint data */
377  int num /**< minimum number of entries to store */
378  )
379 {
380  assert(consdata != NULL);
381  assert(consdata->nvars <= consdata->varssize);
382 
383  if( num > consdata->varssize )
384  {
385  int newsize;
386 
387  newsize = SCIPcalcMemGrowSize(scip, num);
388  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
389  consdata->varssize = newsize;
390  }
391  assert(num <= consdata->varssize);
392 
393  return SCIP_OKAY;
394 }
395 
396 /** creates constraint data for AND-constraint */
397 static
399  SCIP* scip, /**< SCIP data structure */
400  SCIP_CONSDATA** consdata, /**< pointer to store the constraint data */
401  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
402  int nvars, /**< number of variables in the AND-constraint */
403  SCIP_VAR** vars, /**< variables in AND-constraint */
404  SCIP_VAR* resvar, /**< resultant variable */
405  SCIP_Bool checkwhenupgr, /**< should an upgraded constraint be checked despite the fact that this
406  * AND-constraint will not be checked
407  */
408  SCIP_Bool notremovablewhenupgr/**< should an upgraded constraint be despite the fact that this
409  * AND-constraint will not be checked
410  */
411  )
412 {
413  int v;
414 
415  assert(consdata != NULL);
416  assert(nvars == 0 || vars != NULL);
417  assert(resvar != NULL);
418 
419  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
420  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
421  (*consdata)->resvar = resvar;
422  (*consdata)->rows = NULL;
423  (*consdata)->aggrrow = NULL;
424  (*consdata)->nvars = nvars;
425  (*consdata)->varssize = nvars;
426  (*consdata)->nrows = 0;
427  (*consdata)->watchedvar1 = -1;
428  (*consdata)->watchedvar2 = -1;
429  (*consdata)->filterpos1 = -1;
430  (*consdata)->filterpos2 = -1;
431  (*consdata)->propagated = FALSE;
432  (*consdata)->nofixedzero = FALSE;
433  (*consdata)->impladded = FALSE;
434  (*consdata)->opimpladded = FALSE;
435  (*consdata)->sorted = FALSE;
436  (*consdata)->changed = TRUE;
437  (*consdata)->merged = FALSE;
438  (*consdata)->checkwhenupgr = checkwhenupgr;
439  (*consdata)->notremovablewhenupgr = notremovablewhenupgr;
440 
441  /* get transformed variables, if we are in the transformed problem */
442  if( SCIPisTransformed(scip) )
443  {
444  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
445  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->resvar, &(*consdata)->resvar) );
446 
447  /* catch needed events on variables */
448  SCIP_CALL( consdataCatchEvents(scip, *consdata, eventhdlr) );
449  }
450 
451  assert(SCIPvarIsBinary((*consdata)->resvar));
452 
453  /* note: currently, this constraint handler does not handle multiaggregations (e.g. during propagation), hence we forbid
454  * multiaggregation from the beginning for the involved variables
455  */
457  {
458  for( v = 0; v < (*consdata)->nvars; ++v )
459  {
460  assert((*consdata)->vars[v] != NULL);
461  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[v]) );
462  }
463  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->resvar) );
464  }
465 
466  /* capture vars */
467  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->resvar) );
468  for( v = 0; v < (*consdata)->nvars; v++ )
469  {
470  assert((*consdata)->vars[v] != NULL);
471  assert(SCIPvarIsBinary((*consdata)->vars[v]));
472  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
473  }
474 
475 
476  return SCIP_OKAY;
477 }
478 
479 /** releases LP rows of constraint data and frees rows array */
480 static
482  SCIP* scip, /**< SCIP data structure */
483  SCIP_CONSDATA* consdata /**< constraint data */
484  )
485 {
486  int r;
487 
488  assert(consdata != NULL);
489 
490  if( consdata->rows != NULL )
491  {
492  for( r = 0; r < consdata->nrows; ++r )
493  {
494  SCIP_CALL( SCIPreleaseRow(scip, &consdata->rows[r]) );
495  }
496  SCIPfreeBlockMemoryArray(scip, &consdata->rows, consdata->nrows);
497 
498  consdata->nrows = 0;
499  }
500 
501  if( consdata->aggrrow != NULL )
502  {
503  SCIP_CALL( SCIPreleaseRow(scip, &consdata->aggrrow) );
504  consdata->aggrrow = NULL;
505  }
506 
507  return SCIP_OKAY;
508 }
509 
510 /** frees constraint data for AND-constraint */
511 static
513  SCIP* scip, /**< SCIP data structure */
514  SCIP_CONSDATA** consdata, /**< pointer to the constraint data */
515  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
516  )
517 {
518  int v;
519 
520  assert(consdata != NULL);
521  assert(*consdata != NULL);
522 
523  if( SCIPisTransformed(scip) )
524  {
525  /* drop events for watched variables */
526  SCIP_CALL( consdataSwitchWatchedvars(scip, *consdata, eventhdlr, -1, -1) );
527 
528  /* drop all other events on variables */
529  SCIP_CALL( consdataDropEvents(scip, *consdata, eventhdlr) );
530  }
531  else
532  {
533  assert((*consdata)->watchedvar1 == -1);
534  assert((*consdata)->watchedvar2 == -1);
535  }
536 
537  /* release and free the rows */
538  SCIP_CALL( consdataFreeRows(scip, *consdata) );
539 
540  /* release vars */
541  for( v = 0; v < (*consdata)->nvars; v++ )
542  {
543  assert((*consdata)->vars[v] != NULL);
544  SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
545  }
546  SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->resvar)) );
547 
548 
549  SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->varssize);
550  SCIPfreeBlockMemory(scip, consdata);
551 
552  return SCIP_OKAY;
553 }
554 
555 /** prints AND-constraint to file stream */
556 static
558  SCIP* scip, /**< SCIP data structure */
559  SCIP_CONSDATA* consdata, /**< AND-constraint data */
560  FILE* file /**< output file (or NULL for standard output) */
561  )
562 {
563  assert(consdata != NULL);
564 
565  /* print resultant */
566  SCIP_CALL( SCIPwriteVarName(scip, file, consdata->resvar, TRUE) );
567 
568  /* start the variable list */
569  SCIPinfoMessage(scip, file, " == and(");
570 
571  /* print variable list */
572  SCIP_CALL( SCIPwriteVarsList(scip, file, consdata->vars, consdata->nvars, TRUE, ',') );
573 
574  /* close the variable list */
575  SCIPinfoMessage(scip, file, ")");
576 
577  return SCIP_OKAY;
578 }
579 
580 /** adds coefficient to AND-constraint */
581 static
583  SCIP* scip, /**< SCIP data structure */
584  SCIP_CONS* cons, /**< linear constraint */
585  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
586  SCIP_VAR* var /**< variable to add to the constraint */
587  )
588 {
589  SCIP_CONSDATA* consdata;
590  SCIP_Bool transformed;
591 
592  assert(var != NULL);
593 
594  consdata = SCIPconsGetData(cons);
595  assert(consdata != NULL);
596  assert(consdata->rows == NULL);
597 
598  /* are we in the transformed problem? */
599  transformed = SCIPconsIsTransformed(cons);
600 
601  /* always use transformed variables in transformed constraints */
602  if( transformed )
603  {
604  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
605  }
606  assert(var != NULL);
607  assert(transformed == SCIPvarIsTransformed(var));
608 
609  SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
610  consdata->vars[consdata->nvars] = var;
611  consdata->nvars++;
612  consdata->sorted = (consdata->nvars == 1);
613  consdata->changed = TRUE;
614  consdata->merged = FALSE;
615 
616  /* capture variable */
617  SCIP_CALL( SCIPcaptureVar(scip, var) );
618 
619  /* if we are in transformed problem, catch the variable's events */
620  if( transformed )
621  {
622  /* catch bound change events of variable */
624  eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
625  }
626 
627  /* install the rounding locks for the new variable */
628  SCIP_CALL( lockRounding(scip, cons, var) );
629 
630  /**@todo update LP rows */
631  if( consdata->rows != NULL )
632  {
633  SCIPerrorMessage("cannot add coefficients to AND-constraint after LP relaxation was created\n");
634  return SCIP_INVALIDCALL;
635  }
636 
637  return SCIP_OKAY;
638 }
639 
640 /** deletes coefficient at given position from AND-constraint data */
641 static
643  SCIP* scip, /**< SCIP data structure */
644  SCIP_CONS* cons, /**< AND-constraint */
645  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
646  int pos /**< position of coefficient to delete */
647  )
648 {
649  SCIP_CONSDATA* consdata;
650 
651  assert(eventhdlr != NULL);
652 
653  consdata = SCIPconsGetData(cons);
654  assert(consdata != NULL);
655  assert(0 <= pos && pos < consdata->nvars);
656  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
657 
658  /* remove the rounding locks of the variable */
659  SCIP_CALL( unlockRounding(scip, cons, consdata->vars[pos]) );
660 
661  if( SCIPconsIsTransformed(cons) )
662  {
663  /* drop bound change events of variable */
665  eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
666  }
667 
668  if( SCIPconsIsTransformed(cons) )
669  {
670  /* if the position is watched, stop watching the position */
671  if( consdata->watchedvar1 == pos )
672  {
673  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar2, -1) );
674  }
675  if( consdata->watchedvar2 == pos )
676  {
677  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar1, -1) );
678  }
679  }
680  assert(pos != consdata->watchedvar1);
681  assert(pos != consdata->watchedvar2);
682 
683  /* release variable */
684  SCIP_CALL( SCIPreleaseVar(scip, &(consdata->vars[pos])) );
685 
686  /* move the last variable to the free slot */
687  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
688  consdata->nvars--;
689 
690  /* if the last variable (that moved) was watched, update the watched position */
691  if( consdata->watchedvar1 == consdata->nvars )
692  consdata->watchedvar1 = pos;
693  if( consdata->watchedvar2 == consdata->nvars )
694  consdata->watchedvar2 = pos;
695 
696  consdata->propagated = FALSE;
697  consdata->sorted = FALSE;
698  consdata->changed = TRUE;
699 
700  return SCIP_OKAY;
701 }
702 
703 /** sorts AND-constraint's variables by non-decreasing variable index */
704 static
705 void consdataSort(
706  SCIP_CONSDATA* consdata /**< constraint data */
707  )
708 {
709  assert(consdata != NULL);
710 
711  if( !consdata->sorted )
712  {
713  if( consdata->nvars <= 1 )
714  consdata->sorted = TRUE;
715  else
716  {
717  SCIP_VAR* var1 = NULL;
718  SCIP_VAR* var2 = NULL;
719 
720  /* remember watch variables */
721  if( consdata->watchedvar1 != -1 )
722  {
723  var1 = consdata->vars[consdata->watchedvar1];
724  assert(var1 != NULL);
725  consdata->watchedvar1 = -1;
726  if( consdata->watchedvar2 != -1 )
727  {
728  var2 = consdata->vars[consdata->watchedvar2];
729  assert(var2 != NULL);
730  consdata->watchedvar2 = -1;
731  }
732  }
733  assert(consdata->watchedvar1 == -1);
734  assert(consdata->watchedvar2 == -1);
735  assert(var1 != NULL || var2 == NULL);
736 
737  /* sort variables after index */
738  SCIPsortPtr((void**)consdata->vars, SCIPvarComp, consdata->nvars);
739  consdata->sorted = TRUE;
740 
741  /* correct watched variables */
742  if( var1 != NULL )
743  {
744  int pos;
745 #ifndef NDEBUG
746  SCIP_Bool found;
747 
748  found = SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var1, consdata->nvars, &pos);
749  assert(found);
750 #else
751  SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var1, consdata->nvars, &pos);
752 #endif
753  assert(pos >= 0 && pos < consdata->nvars);
754  consdata->watchedvar1 = pos;
755 
756  if( var2 != NULL )
757  {
758 #ifndef NDEBUG
759  found = SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var2, consdata->nvars, &pos);
760  assert(found);
761 #else
762  SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var2, consdata->nvars, &pos);
763 #endif
764  assert(pos >= 0 && pos < consdata->nvars);
765  consdata->watchedvar2 = pos;
766  }
767  }
768  }
769  }
770 
771 #ifdef SCIP_DEBUG
772  /* check sorting */
773  {
774  int v;
775 
776  for( v = 0; v < consdata->nvars; ++v )
777  {
778  assert(v == consdata->nvars-1 || SCIPvarCompare(consdata->vars[v], consdata->vars[v+1]) <= 0);
779  }
780  }
781 #endif
782 }
783 
784 /** deletes all one-fixed variables */
785 static
787  SCIP* scip, /**< SCIP data structure */
788  SCIP_CONS* cons, /**< AND-constraint */
789  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
790  int* nchgcoefs /**< pointer to add up the number of changed coefficients */
791  )
792 {
793  SCIP_CONSDATA* consdata;
794  SCIP_VAR* var;
795  int v;
796 
797  assert(scip != NULL);
798  assert(cons != NULL);
799  assert(eventhdlr != NULL);
800  assert(nchgcoefs != NULL);
801 
802  consdata = SCIPconsGetData(cons);
803  assert(consdata != NULL);
804  assert(consdata->nvars == 0 || consdata->vars != NULL);
805 
806  v = 0;
807  while( v < consdata->nvars )
808  {
809  var = consdata->vars[v];
810  assert(SCIPvarIsBinary(var));
811 
812  if( SCIPvarGetLbGlobal(var) > 0.5 )
813  {
814  assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), 1.0));
815  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
816  (*nchgcoefs)++;
817  }
818  else
819  {
820  SCIP_VAR* repvar;
821  SCIP_Bool negated;
822 
823  /* get binary representative of variable */
824  SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
825 
826  /* check, if the variable should be replaced with the representative */
827  if( repvar != var )
828  {
829  /* delete old (aggregated) variable */
830  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
831 
832  /* add representative instead */
833  SCIP_CALL( addCoef(scip, cons, eventhdlr, repvar) );
834  }
835  else
836  ++v;
837  }
838  }
839 
840 #ifdef SCIP_DISABLED_CODE /* does not work with pseudoboolean constraint handler, need to be fixed */
841  /* check, if the resultant should be replaced with the active representative */
842  if( !SCIPvarIsActive(consdata->resvar) )
843  {
844  SCIP_VAR* repvar;
845  SCIP_Bool negated;
846 
847  /* get binary representative of variable */
848  SCIP_CALL( SCIPgetBinvarRepresentative(scip, consdata->resvar, &repvar, &negated) );
849  assert(SCIPvarIsBinary(repvar));
850 
851  /* check, if the variable should be replaced with the representative */
852  if( repvar != consdata->resvar )
853  {
854  if( SCIPconsIsTransformed(cons) )
855  {
856  /* drop bound change events of old resultant */
857  SCIP_CALL( SCIPdropVarEvent(scip, consdata->resvar, SCIP_EVENTTYPE_BOUNDCHANGED,
858  eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
859 
860  /* catch bound change events of new resultant */
862  eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
863  }
864 
865  /* release old resultant */
866  SCIP_CALL( SCIPreleaseVar(scip, &(consdata->resvar)) );
867 
868  /* capture new resultant */
869  SCIP_CALL( SCIPcaptureVar(scip, repvar) );
870 
871  consdata->resvar = repvar;
872  consdata->changed = TRUE;
873  }
874  }
875 #endif
876 
877  SCIPdebugMsg(scip, "after fixings: ");
878  SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL)) );
879  SCIPdebugMsgPrint(scip, "\n");
880 
881  return SCIP_OKAY;
882 }
883 
884 /** creates a linearization of the AND-constraint */
885 static
887  SCIP* scip, /**< SCIP data structure */
888  SCIP_CONS* cons /**< constraint to check */
889  )
890 {
891  SCIP_CONSDATA* consdata;
892  char rowname[SCIP_MAXSTRLEN];
893  int nvars;
894  int i;
895 
896  consdata = SCIPconsGetData(cons);
897  assert(consdata != NULL);
898  assert(consdata->rows == NULL);
899 
900  nvars = consdata->nvars;
901 
902  /* get memory for rows */
903  consdata->nrows = nvars + 1;
904  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->rows, consdata->nrows) );
905 
906  /* creates LP rows corresponding to AND-constraint:
907  * - one additional row: resvar - v1 - ... - vn >= 1-n
908  * - for each operator variable vi: resvar - vi <= 0
909  */
910 
911  /* create additional row */
912  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_add", SCIPconsGetName(cons));
913  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[0], SCIPconsGetHdlr(cons), rowname, -consdata->nvars + 1.0, SCIPinfinity(scip),
915  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[0], consdata->resvar, 1.0) );
916  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[0], nvars, consdata->vars, -1.0) );
917 
918  /* create operator rows */
919  for( i = 0; i < nvars; ++i )
920  {
921  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), i);
922  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[i+1], SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), 0.0,
924  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[i+1], consdata->resvar, 1.0) );
925  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[i+1], consdata->vars[i], -1.0) );
926  }
927 
928  return SCIP_OKAY;
929 }
930 
931 /** adds linear relaxation of AND-constraint to the LP */
932 static
934  SCIP* scip, /**< SCIP data structure */
935  SCIP_CONS* cons, /**< constraint to check */
936  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
937  )
938 {
939  SCIP_CONSDATA* consdata;
940 
941  /* in the root LP we only add the weaker relaxation which consists of two rows:
942  * - one additional row: resvar - v1 - ... - vn >= 1-n
943  * - aggregated row: n*resvar - v1 - ... - vn <= 0.0
944  *
945  * during separation we separate the stronger relaxation which consists of n+1 row:
946  * - one additional row: resvar - v1 - ... - vn >= 1-n
947  * - for each operator variable vi: resvar - vi <= 0.0
948  */
949 
950  consdata = SCIPconsGetData(cons);
951  assert(consdata != NULL);
952 
953  /* create the aggregated row */
954  if( consdata->aggrrow == NULL )
955  {
956  char rowname[SCIP_MAXSTRLEN];
957 
958  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_operators", SCIPconsGetName(cons));
959  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->aggrrow, SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), 0.0,
961  SCIP_CALL( SCIPaddVarToRow(scip, consdata->aggrrow, consdata->resvar, (SCIP_Real) consdata->nvars) );
962  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->aggrrow, consdata->nvars, consdata->vars, -1.0) );
963  }
964 
965  /* insert aggregated LP row as cut */
966  if( !SCIProwIsInLP(consdata->aggrrow) )
967  {
968  SCIP_CALL( SCIPaddRow(scip, consdata->aggrrow, FALSE, infeasible) );
969  }
970 
971  if( !(*infeasible) )
972  {
973  if( consdata->rows == NULL )
974  {
975  /* create the n+1 row relaxation */
976  SCIP_CALL( createRelaxation(scip, cons) );
977  }
978 
979  assert(consdata->rows != NULL);
980 
981  /* add additional row */
982  if( !SCIProwIsInLP(consdata->rows[0]) )
983  {
984  SCIP_CALL( SCIPaddRow(scip, consdata->rows[0], FALSE, infeasible) );
985  }
986  }
987 
988  return SCIP_OKAY;
989 }
990 
991 /** checks AND-constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
992 static
994  SCIP* scip, /**< SCIP data structure */
995  SCIP_CONS* cons, /**< constraint to check */
996  SCIP_SOL* sol, /**< solution to check, NULL for current solution */
997  SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
998  SCIP_Bool printreason, /**< Should the reason for the violation be printed? */
999  SCIP_Bool* violated /**< pointer to store whether the constraint is violated */
1000  )
1001 {
1002  SCIP_CONSDATA* consdata;
1003  SCIP_Bool mustcheck;
1004  int r;
1005 
1006  assert(violated != NULL);
1007 
1008  consdata = SCIPconsGetData(cons);
1009  assert(consdata != NULL);
1010 
1011  *violated = FALSE;
1012 
1013  /* check whether we can skip this feasibility check, because all rows are in the LP and do not have to be checked */
1014  mustcheck = checklprows;
1015  mustcheck = mustcheck || (consdata->rows == NULL);
1016  if( !mustcheck )
1017  {
1018  assert(consdata->rows != NULL);
1019 
1020  for( r = 0; r < consdata->nrows; ++r )
1021  {
1022  mustcheck = !SCIProwIsInLP(consdata->rows[r]);
1023  if( mustcheck )
1024  break;
1025  }
1026  }
1027 
1028  /* check feasibility of constraint if necessary */
1029  if( mustcheck )
1030  {
1031  SCIP_Real solval;
1032  SCIP_Real viol;
1033  SCIP_Real absviol;
1034  SCIP_Real relviol;
1035  int i;
1036 
1037  /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
1038  * enforcement
1039  */
1040  if( sol == NULL )
1041  {
1042  SCIP_CALL( SCIPincConsAge(scip, cons) );
1043  }
1044 
1045  absviol = 0.0;
1046  relviol = 0.0;
1047 
1048  /* check, if all operator variables are TRUE */
1049  for( i = 0; i < consdata->nvars; ++i )
1050  {
1051  solval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
1052 
1053  viol = REALABS(1 - solval);
1054  if( absviol < viol )
1055  {
1056  absviol = viol;
1057  relviol = SCIPrelDiff(solval, 1.0);
1058  }
1059 
1060  /* @todo If "upgraded resultants to varstatus implicit" is fully allowed, than the following assert does not hold
1061  * anymore, therefor we need to stop the check and return with the status not violated, because the
1062  * integrality condition of this violated operand needs to be enforced by another constraint.
1063  *
1064  * The above should be asserted by marking the constraint handler, for which the result needs to be
1065  * SCIP_SEPARATED if the origin was the CONSENFOPS or the CONSENFOLP callback or SCIP_INFEASIBLE if the
1066  * origin was CONSCHECK callback.
1067  *
1068  */
1069  assert(SCIPisFeasIntegral(scip, solval));
1070  if( solval < 0.5 )
1071  break;
1072  }
1073 
1074  /* if all operator variables are TRUE, the resultant has to be TRUE, otherwise, the resultant has to be FALSE;
1075  * in case of an implicit integer resultant variable, we need to ensure the integrality of the solution value
1076  */
1077  solval = SCIPgetSolVal(scip, sol, consdata->resvar);
1078  assert(SCIPvarGetType(consdata->resvar) == SCIP_VARTYPE_IMPLINT || SCIPisFeasIntegral(scip, solval));
1079 
1080  if( !SCIPisFeasIntegral(scip, solval) || (i == consdata->nvars) != (solval > 0.5) )
1081  {
1082  *violated = TRUE;
1083  absviol = 1.0;
1084  relviol = 1.0;
1085 
1086  /* only reset constraint age if we are in enforcement */
1087  if( sol == NULL )
1088  {
1089  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1090  }
1091 
1092  if( printreason )
1093  {
1094  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
1095  SCIPinfoMessage(scip, NULL, ";\n");
1096  SCIPinfoMessage(scip, NULL, "violation:");
1097  if( !SCIPisFeasIntegral(scip, solval) )
1098  {
1099  SCIPinfoMessage(scip, NULL, " resultant variable <%s> has fractional solution value %" SCIP_REAL_FORMAT "\n",
1100  SCIPvarGetName(consdata->resvar), solval);
1101  }
1102  else if( i == consdata->nvars )
1103  {
1104  SCIPinfoMessage(scip, NULL, " all operands are TRUE and resultant <%s> = FALSE\n",
1105  SCIPvarGetName(consdata->resvar));
1106  }
1107  else
1108  {
1109  SCIPinfoMessage(scip, NULL, " operand <%s> = FALSE and resultant <%s> = TRUE\n",
1110  SCIPvarGetName(consdata->vars[i]), SCIPvarGetName(consdata->resvar));
1111  }
1112  }
1113  }
1114  if( sol != NULL )
1115  SCIPupdateSolConsViolation(scip, sol, absviol, relviol);
1116  }
1117 
1118  return SCIP_OKAY;
1119 }
1120 
1121 /** separates given primal solution */
1122 static
1124  SCIP* scip, /**< SCIP data structure */
1125  SCIP_CONS* cons, /**< constraint to check */
1126  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1127  SCIP_Bool* separated, /**< pointer to store whether a cut was found */
1128  SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1129  )
1130 {
1131  SCIP_CONSDATA* consdata;
1132  SCIP_Real feasibility;
1133  int r;
1134 
1135  assert(separated != NULL);
1136  assert(cutoff != NULL);
1137 
1138  *separated = FALSE;
1139  *cutoff = FALSE;
1140 
1141  consdata = SCIPconsGetData(cons);
1142  assert(consdata != NULL);
1143 
1144  /* create all necessary rows for the linear relaxation */
1145  if( consdata->rows == NULL )
1146  {
1147  SCIP_CALL( createRelaxation(scip, cons) );
1148  }
1149  assert(consdata->rows != NULL);
1150 
1151  /* test all rows for feasibility and add infeasible rows */
1152  for( r = 0; r < consdata->nrows; ++r )
1153  {
1154  if( !SCIProwIsInLP(consdata->rows[r]) )
1155  {
1156  feasibility = SCIPgetRowSolFeasibility(scip, consdata->rows[r], sol);
1157  if( SCIPisFeasNegative(scip, feasibility) )
1158  {
1159  SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, cutoff) );
1160  if ( *cutoff )
1161  return SCIP_OKAY;
1162  *separated = TRUE;
1163  }
1164  }
1165  }
1166 
1167  return SCIP_OKAY;
1168 }
1169 
1170 /** analyzes conflicting TRUE assignment to resultant of given constraint, and adds conflict constraint to problem */
1171 static
1173  SCIP* scip, /**< SCIP data structure */
1174  SCIP_CONS* cons, /**< AND-constraint that detected the conflict */
1175  int falsepos /**< position of operand that is fixed to FALSE */
1176  )
1177 {
1178  SCIP_CONSDATA* consdata;
1179 
1180  /* conflict analysis can only be applied in solving stage and if it turned on */
1182  return SCIP_OKAY;
1183 
1184  consdata = SCIPconsGetData(cons);
1185  assert(consdata != NULL);
1186  assert(SCIPvarGetLbLocal(consdata->resvar) > 0.5);
1187  assert(0 <= falsepos && falsepos < consdata->nvars);
1188  assert(SCIPvarGetUbLocal(consdata->vars[falsepos]) < 0.5);
1189 
1190  /* initialize conflict analysis, and add resultant and single operand variable to conflict candidate queue */
1192 
1193  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1194  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[falsepos]) );
1195 
1196  /* analyze the conflict */
1197  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1198 
1199  return SCIP_OKAY;
1200 }
1201 
1202 /** analyzes conflicting FALSE assignment to resultant of given constraint, and adds conflict constraint to problem */
1203 static
1205  SCIP* scip, /**< SCIP data structure */
1206  SCIP_CONS* cons /**< or constraint that detected the conflict */
1207  )
1208 {
1209  SCIP_CONSDATA* consdata;
1210  int v;
1211 
1212  assert(!SCIPconsIsModifiable(cons));
1213 
1214  /* conflict analysis can only be applied in solving stage and if it is applicable */
1216  return SCIP_OKAY;
1217 
1218  consdata = SCIPconsGetData(cons);
1219  assert(consdata != NULL);
1220  assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
1221 
1222  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1224 
1225  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1226  for( v = 0; v < consdata->nvars; ++v )
1227  {
1228  assert(SCIPvarGetLbLocal(consdata->vars[v]) > 0.5);
1229  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
1230  }
1231 
1232  /* analyze the conflict */
1233  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1234 
1235  return SCIP_OKAY;
1236 }
1237 
1238 /** tries to fix the given resultant to zero */
1239 static
1241  SCIP* scip, /**< SCIP data structure */
1242  SCIP_CONS* cons, /**< AND-constraint to be processed */
1243  SCIP_VAR* resvar, /**< resultant variable to fix to zero */
1244  int pos, /**< position of operand that is fixed to FALSE */
1245  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1246  int* nfixedvars /**< pointer to add up the number of found domain reductions */
1247  )
1248 {
1249  SCIP_Bool infeasible;
1250  SCIP_Bool tightened;
1251 
1252  SCIPdebugMsg(scip, "constraint <%s>: operator %d fixed to 0.0 -> fix resultant <%s> to 0.0\n",
1253  SCIPconsGetName(cons), pos, SCIPvarGetName(resvar));
1254 
1255  SCIP_CALL( SCIPinferBinvarCons(scip, resvar, FALSE, cons, (int)PROPRULE_1, &infeasible, &tightened) );
1256 
1257  if( infeasible )
1258  {
1259  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1260  SCIP_CALL( analyzeConflictOne(scip, cons, pos) );
1261  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1262  (*cutoff) = TRUE;
1263  }
1264  else
1265  {
1266  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1267  if( tightened )
1268  {
1269  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1270  (*nfixedvars)++;
1271  }
1272  }
1273 
1274  return SCIP_OKAY;
1275 }
1276 
1277 /** fix all operands to one */
1278 static
1280  SCIP* scip, /**< SCIP data structure */
1281  SCIP_CONS* cons, /**< AND-constraint to be processed */
1282  SCIP_VAR** vars, /**< array of operands */
1283  int nvars, /**< number of operands */
1284  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1285  int* nfixedvars /**< pointer to add up the number of found domain reductions */
1286  )
1287 {
1288  SCIP_Bool infeasible;
1289  SCIP_Bool tightened;
1290  int v;
1291 
1292  for( v = 0; v < nvars && !(*cutoff); ++v )
1293  {
1294  SCIPdebugMsg(scip, "constraint <%s>: resultant fixed to 1.0 -> fix operator var <%s> to 1.0\n",
1295  SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
1296 
1297  SCIP_CALL( SCIPinferBinvarCons(scip, vars[v], TRUE, cons, (int)PROPRULE_2, &infeasible, &tightened) );
1298 
1299  if( infeasible )
1300  {
1301  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1302  SCIP_CALL( analyzeConflictOne(scip, cons, v) );
1303  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1304  (*cutoff) = TRUE;
1305  }
1306  else if( tightened )
1307  {
1308  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1309  (*nfixedvars)++;
1310  }
1311  }
1312 
1313  if( !(*cutoff) )
1314  {
1315  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1316  }
1317 
1318  return SCIP_OKAY;
1319 }
1320 
1321 /** linearize AND-constraint due to a globally to zero fixed resultant; that is, creates, adds, and releases a logicor
1322  * constraint and remove the AND-constraint globally.
1323  *
1324  * Since the resultant is fixed to zero the AND-constraint collapses to linear constraint of the form:
1325  *
1326  * - \f$\sum_{i=0}^{n-1} v_i \leq n-1\f$
1327  *
1328  * This can be transformed into a logicor constraint of the form
1329  *
1330  * - \f$\sum_{i=0}^{n-1} ~v_i \geq 1\f$
1331  */
1332 static
1334  SCIP* scip, /**< SCIP data structure */
1335  SCIP_CONS* cons, /**< AND-constraint to linearize */
1336  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1337  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1338  int* nupgdconss /**< pointer to add up the number of upgraded constraints */
1339  )
1340 {
1341  SCIP_CONSDATA* consdata;
1342  SCIP_VAR** vars;
1343  SCIP_CONS* lincons;
1344  SCIP_Bool conscreated;
1345  int nvars;
1346 
1347  consdata = SCIPconsGetData(cons);
1348  assert(consdata != NULL);
1349 
1350  assert(!(*cutoff));
1351  assert(SCIPvarGetUbGlobal(consdata->resvar) < 0.5);
1352 
1353  nvars = consdata->nvars;
1354  conscreated = FALSE;
1355 
1356  /* allocate memory for variables for updated constraint */
1357  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1358 
1359  /* if we only have two variables, we prefer a set packing constraint instead of a logicor constraint */
1360  if( nvars == 2 && !SCIPconsIsModifiable(cons) )
1361  {
1362  SCIP_Bool* negated;
1363  SCIP_Bool infeasible;
1364  SCIP_Bool tightened;
1365 
1366  /* get active representation */
1367  SCIP_CALL( SCIPallocBufferArray(scip, &negated, nvars) );
1368  SCIP_CALL( SCIPgetBinvarRepresentatives(scip, nvars, consdata->vars, vars, negated) );
1369  SCIPfreeBufferArray(scip, &negated);
1370 
1371  /* if one of the two operators is globally fixed to one it follows that the other has to be zero */
1372  if( SCIPvarGetLbGlobal(vars[0]) > 0.5 )
1373  {
1374  SCIP_CALL( SCIPfixVar(scip, vars[1], 0.0, &infeasible, &tightened) );
1375 
1376  if( infeasible )
1377  *cutoff = TRUE;
1378  else if( tightened )
1379  ++(*nfixedvars);
1380  }
1381  else if( SCIPvarGetLbGlobal(vars[1]) > 0.5 )
1382  {
1383  SCIP_CALL( SCIPfixVar(scip, vars[0], 0.0, &infeasible, &tightened) );
1384 
1385  if( infeasible )
1386  *cutoff = TRUE;
1387  else if( tightened )
1388  ++(*nfixedvars);
1389  }
1390  else if( SCIPvarGetUbGlobal(vars[0]) > 0.5 && SCIPvarGetUbGlobal(vars[1]) > 0.5 )
1391  {
1392  /* create, add, and release the setppc constraint */
1393  SCIP_CALL( SCIPcreateConsSetpack(scip, &lincons, SCIPconsGetName(cons), nvars, vars,
1395  consdata->checkwhenupgr || SCIPconsIsChecked(cons),
1397  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1398 
1399  conscreated = TRUE;
1400  }
1401  }
1402  else
1403  {
1404  int v;
1405 
1406  /* collect negated variables */
1407  for( v = 0; v < nvars; ++v )
1408  {
1409  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &vars[v]) );
1410  }
1411 
1412  /* create, add, and release the logicor constraint */
1413  SCIP_CALL( SCIPcreateConsLogicor(scip, &lincons, SCIPconsGetName(cons), nvars, vars,
1415  consdata->checkwhenupgr || SCIPconsIsChecked(cons),
1417  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1418 
1419  conscreated = TRUE;
1420  }
1421 
1422  if( conscreated )
1423  {
1424  /* add and release new constraint */
1425  SCIPdebugPrintCons(scip, lincons, NULL); /*lint !e644*/
1426  SCIP_CALL( SCIPaddCons(scip, lincons) ); /*lint !e644*/
1427  SCIP_CALL( SCIPreleaseCons(scip, &lincons) ); /*lint !e644*/
1428 
1429  ++(*nupgdconss);
1430  }
1431 
1432  /* remove the AND-constraint globally */
1433  SCIP_CALL( SCIPdelCons(scip, cons) );
1434 
1435  /* delete temporary memory */
1436  SCIPfreeBufferArray(scip, &vars);
1437 
1438  return SCIP_OKAY;
1439 }
1440 
1441 /** the resultant is fixed to zero; in case all except one operator are fixed to TRUE the last operator has to fixed to FALSE */
1442 /** @note consdata->watchedvars might not be the same to the watchedvar parameters, because the update was not yet done */
1443 static
1445  SCIP* scip, /**< SCIP data structure */
1446  SCIP_CONS* cons, /**< AND-constraint to be processed */
1447  int watchedvar1, /**< maybe last unfixed variable position */
1448  int watchedvar2, /**< second watched position */
1449  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1450  int* nfixedvars /**< pointer to add up the number of found domain reductions */
1451  )
1452 {
1453  SCIP_CONSDATA* consdata;
1454 
1455  consdata = SCIPconsGetData(cons);
1456  assert(consdata != NULL);
1457  assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
1458 
1459  if( watchedvar2 == -1 )
1460  {
1461  SCIP_Bool infeasible;
1462  SCIP_Bool tightened;
1463 
1464  assert(watchedvar1 != -1);
1465 
1466 #ifndef NDEBUG
1467  /* check that all variables regardless of wathcedvar1 are fixed to 1 */
1468  {
1469  int v;
1470 
1471  for( v = consdata->nvars - 1; v >= 0; --v )
1472  if( v != watchedvar1 )
1473  assert(SCIPvarGetLbLocal(consdata->vars[v]) > 0.5);
1474  }
1475 #endif
1476 
1477  SCIPdebugMsg(scip, "constraint <%s>: resultant <%s> fixed to 0.0, only one unfixed operand -> fix operand <%s> to 0.0\n",
1478  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar), SCIPvarGetName(consdata->vars[watchedvar1]));
1479 
1480  SCIP_CALL( SCIPinferBinvarCons(scip, consdata->vars[watchedvar1], FALSE, cons, (int)PROPRULE_4, &infeasible, &tightened) );
1481 
1482  if( infeasible )
1483  {
1484  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1485  SCIP_CALL( analyzeConflictZero(scip, cons) );
1486  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1487  *cutoff = TRUE;
1488  }
1489  else
1490  {
1491  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1492  if( tightened )
1493  {
1494  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1495  (*nfixedvars)++;
1496  }
1497  }
1498  }
1499 
1500  return SCIP_OKAY;
1501 }
1502 
1503 /** replaces multiple occurrences of variables */
1504 static
1506  SCIP* scip, /**< SCIP data structure */
1507  SCIP_CONS* cons, /**< AND-constraint */
1508  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1509  unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
1510  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
1511  int* nfixedvars, /**< pointer to store number of fixed variables */
1512  int* nchgcoefs, /**< pointer to store number of changed coefficients */
1513  int* ndelconss /**< pointer to store number of deleted constraints */
1514  )
1515 {
1516  SCIP_CONSDATA* consdata;
1517  SCIP_VAR** vars;
1518  SCIP_VAR* var;
1519  SCIP_VAR* probvar;
1520  int probidx;
1521  int nvars;
1522  int v;
1523 #ifndef NDEBUG
1524  int nbinvars;
1525  int nintvars;
1526  int nimplvars;
1527 #endif
1528 
1529  assert(scip != NULL);
1530  assert(cons != NULL);
1531  assert(eventhdlr != NULL);
1532  assert(*entries != NULL);
1533  assert(nentries != NULL);
1534  assert(nfixedvars != NULL);
1535  assert(nchgcoefs != NULL);
1536  assert(ndelconss != NULL);
1537 
1538  consdata = SCIPconsGetData(cons);
1539  assert(consdata != NULL);
1540 
1541  if( consdata->merged )
1542  return SCIP_OKAY;
1543 
1544  /* nothing to merge */
1545  if( consdata->nvars <= 1 )
1546  {
1547  consdata->merged = TRUE;
1548  return SCIP_OKAY;
1549  }
1550 
1551  vars = consdata->vars;
1552  nvars = consdata->nvars;
1553 
1554  assert(vars != NULL);
1555  assert(nvars >= 2);
1556 
1557 #ifndef NDEBUG
1558  nbinvars = SCIPgetNBinVars(scip);
1559  nintvars = SCIPgetNIntVars(scip);
1560  nimplvars = SCIPgetNImplVars(scip);
1561  assert(*nentries >= nbinvars + nintvars + nimplvars);
1562 #endif
1563 
1564  /* initialize entries array */
1565  for( v = nvars - 1; v >= 0; --v )
1566  {
1567  var = vars[v];
1568  assert(var != NULL);
1569  assert(SCIPvarIsActive(var) || (SCIPvarIsNegated(var) && SCIPvarIsActive(SCIPvarGetNegatedVar(var))));
1570 
1571  probvar = (SCIPvarIsActive(var) ? var : SCIPvarGetNegatedVar(var));
1572  assert(probvar != NULL);
1573 
1574  probidx = SCIPvarGetProbindex(probvar);
1575  assert(0 <= probidx);
1576 
1577  /* check variable type, either pure binary or an integer/implicit integer variable with 0/1 bounds */
1578  assert((probidx < nbinvars && SCIPvarGetType(probvar) == SCIP_VARTYPE_BINARY)
1579  || (SCIPvarIsBinary(probvar) &&
1580  ((probidx >= nbinvars && probidx < nbinvars + nintvars && SCIPvarGetType(probvar) == SCIP_VARTYPE_INTEGER) ||
1581  (probidx >= nbinvars + nintvars && probidx < nbinvars + nintvars + nimplvars &&
1582  SCIPvarGetType(probvar) == SCIP_VARTYPE_IMPLINT))));
1583 
1584  /* var is not active yet */
1585  (*entries)[probidx] = 0;
1586  }
1587 
1588  /* search for multiple variables; scan from back to front because deletion doesn't affect the order of the front
1589  * variables
1590  * @note don't reorder variables because we would loose the watched variables and filter position inforamtion
1591  */
1592  for( v = nvars - 1; v >= 0; --v )
1593  {
1594  var = vars[v];
1595  assert(var != NULL);
1596  assert(SCIPvarIsActive(var) || (SCIPvarIsNegated(var) && SCIPvarIsActive(SCIPvarGetNegatedVar(var))));
1597 
1598  probvar = (SCIPvarIsActive(var) ? var : SCIPvarGetNegatedVar(var));
1599  assert(probvar != NULL);
1600 
1601  probidx = SCIPvarGetProbindex(probvar);
1602  assert(0 <= probidx && probidx < *nentries);
1603 
1604  /* if var occurs first time in constraint init entries array */
1605  if( (*entries)[probidx] == 0 )
1606  {
1607  (*entries)[probidx] = (SCIPvarIsActive(var) ? 1 : 2);
1608  }
1609  /* if var occurs second time in constraint, first time it was not negated */
1610  else if( ((*entries)[probidx] == 1 && SCIPvarIsActive(var)) || ((*entries)[probidx] == 2 && !SCIPvarIsActive(var)) )
1611  {
1612  /* delete the multiple variable */
1613  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1614  ++(*nchgcoefs);
1615  }
1616  else
1617  {
1618  SCIP_Bool infeasible;
1619  SCIP_Bool fixed;
1620 
1621  assert(((*entries)[probidx] == 1 && !SCIPvarIsActive(var)) || ((*entries)[probidx] == 2 && SCIPvarIsActive(var)));
1622 
1623  SCIPdebugMsg(scip, "AND-constraint <%s> is redundant: variable <%s> and its negation are present -> fix resultant <%s> = 0\n",
1624  SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetName(consdata->resvar));
1625 
1626  /* negation of the variable is already present in the constraint: fix resultant to zero */
1627 #ifndef NDEBUG
1628  {
1629  int i;
1630  for( i = consdata->nvars - 1; i > v && var != SCIPvarGetNegatedVar(vars[i]); --i )
1631  {}
1632  assert(i > v);
1633  }
1634 #endif
1635 
1636  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
1637  assert(!infeasible);
1638  if( fixed )
1639  ++(*nfixedvars);
1640 
1641  SCIP_CALL( SCIPdelCons(scip, cons) );
1642  break;
1643  }
1644  }
1645 
1646  consdata->merged = TRUE;
1647 
1648  return SCIP_OKAY;
1649 }
1650 
1651 /** propagates constraint with the following rules:
1652  * (1) v_i = FALSE => r = FALSE
1653  * (2) r = TRUE => v_i = TRUE for all i
1654  * (3) v_i = TRUE for all i => r = TRUE
1655  * (4) r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
1656  *
1657  * additional if the resultant is fixed to zero during presolving or in the root node (globally), then the
1658  * AND-constraint is collapsed to a linear (logicor) constraint of the form
1659  * -> sum_{i=0}^{n-1} ~v_i >= 1
1660  */
1661 static
1663  SCIP* scip, /**< SCIP data structure */
1664  SCIP_CONS* cons, /**< AND-constraint to be processed */
1665  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1666  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1667  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1668  int* nupgdconss /**< pointer to add up the number of upgraded constraints */
1669  )
1670 {
1671  SCIP_CONSDATA* consdata;
1672  SCIP_VAR* resvar;
1673  SCIP_VAR** vars;
1674  int nvars;
1675  int watchedvar1;
1676  int watchedvar2;
1677  int i;
1678  SCIP_Bool infeasible;
1679  SCIP_Bool tightened;
1680 
1681  assert(cutoff != NULL);
1682  assert(nfixedvars != NULL);
1683 
1684  consdata = SCIPconsGetData(cons);
1685  assert(consdata != NULL);
1686 
1687  resvar = consdata->resvar;
1688  vars = consdata->vars;
1689  nvars = consdata->nvars;
1690 
1691  /* don't process the constraint, if none of the operator variables was fixed to FALSE, and if the watched variables
1692  * and the resultant weren't fixed to any value since last propagation call
1693  */
1694  if( consdata->propagated )
1695  {
1696  assert(consdata->nofixedzero);
1697  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(resvar), 0.0));
1698  return SCIP_OKAY;
1699  }
1700 
1701  /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
1702  if( !SCIPinRepropagation(scip) )
1703  {
1704  SCIP_CALL( SCIPincConsAge(scip, cons) );
1705  }
1706 
1707  /* if one of the operator variables was fixed to FALSE, the resultant can be fixed to FALSE (rule (1)) */
1708  if( !consdata->nofixedzero )
1709  {
1710  for( i = 0; i < nvars && SCIPvarGetUbLocal(vars[i]) > 0.5; ++i ) /* search for operator fixed to zero */
1711  {}
1712  if( i < nvars )
1713  {
1714  /* fix resultant to zero */
1715  SCIP_CALL( consdataFixResultantZero(scip, cons, resvar, i, cutoff, nfixedvars) );
1716  }
1717  else
1718  consdata->nofixedzero = TRUE;
1719  }
1720 
1721  /* check if resultant variables is globally fixed to zero */
1722  if( !SCIPinProbing(scip) && SCIPvarGetUbGlobal(resvar) < 0.5 )
1723  {
1724  SCIP_CALL( consdataLinearize(scip, cons, cutoff, nfixedvars, nupgdconss) );
1725 
1726  if( *cutoff && SCIPgetDepth(scip) > 0 )
1727  {
1728  /* we are done with solving since a global bound change was infeasible */
1729  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
1730  }
1731 
1732  return SCIP_OKAY;
1733  }
1734 
1735  /* if the resultant and at least one operand are locally fixed to zero, the constraint is locally redundant */
1736  if( SCIPvarGetUbLocal(resvar) < 0.5 && !consdata->nofixedzero )
1737  {
1738  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1739  return SCIP_OKAY;
1740  }
1741 
1742  /* if resultant is fixed to TRUE, all operator variables can be fixed to TRUE (rule (2)) */
1743  if( SCIPvarGetLbLocal(resvar) > 0.5 )
1744  {
1745  /* fix operands to one */
1746  SCIP_CALL( consdataFixOperandsOne(scip, cons, vars, nvars, cutoff, nfixedvars) );
1747 
1748  return SCIP_OKAY;
1749  }
1750 
1751  /* rules (3) and (4) can only be applied, if we know all operator variables */
1752  if( SCIPconsIsModifiable(cons) )
1753  return SCIP_OKAY;
1754 
1755  /* rules (3) and (4) cannot be applied, if we have at least two unfixed variables left;
1756  * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
1757  * if these ones get fixed
1758  */
1759  watchedvar1 = consdata->watchedvar1;
1760  watchedvar2 = consdata->watchedvar2;
1761 
1762  /* check, if watched variables are still unfixed */
1763  if( watchedvar1 != -1 )
1764  {
1765  assert(SCIPvarGetUbLocal(vars[watchedvar1]) > 0.5); /* otherwise, rule (1) could be applied */
1766  if( SCIPvarGetLbLocal(vars[watchedvar1]) > 0.5 )
1767  watchedvar1 = -1;
1768  }
1769  if( watchedvar2 != -1 )
1770  {
1771  assert(SCIPvarGetUbLocal(vars[watchedvar2]) > 0.5); /* otherwise, rule (1) could be applied */
1772  if( SCIPvarGetLbLocal(vars[watchedvar2]) > 0.5 )
1773  watchedvar2 = -1;
1774  }
1775 
1776  /* if only one watched variable is still unfixed, make it the first one */
1777  if( watchedvar1 == -1 )
1778  {
1779  watchedvar1 = watchedvar2;
1780  watchedvar2 = -1;
1781  }
1782  assert(watchedvar1 != -1 || watchedvar2 == -1);
1783 
1784  /* if the watched variables are invalid (fixed), find new ones if existing */
1785  if( watchedvar2 == -1 )
1786  {
1787  for( i = 0; i < nvars; ++i )
1788  {
1789  assert(SCIPvarGetUbLocal(vars[i]) > 0.5); /* otherwise, rule (1) could be applied */
1790  if( SCIPvarGetLbLocal(vars[i]) < 0.5 )
1791  {
1792  if( watchedvar1 == -1 )
1793  {
1794  assert(watchedvar2 == -1);
1795  watchedvar1 = i;
1796  }
1797  else if( watchedvar1 != i )
1798  {
1799  watchedvar2 = i;
1800  break;
1801  }
1802  }
1803  }
1804  }
1805  assert(watchedvar1 != -1 || watchedvar2 == -1);
1806 
1807  /* if all variables are fixed to TRUE, the resultant can also be fixed to TRUE (rule (3)) */
1808  if( watchedvar1 == -1 )
1809  {
1810  assert(watchedvar2 == -1);
1811 
1812  SCIPdebugMsg(scip, "constraint <%s>: all operator vars fixed to 1.0 -> fix resultant <%s> to 1.0\n",
1813  SCIPconsGetName(cons), SCIPvarGetName(resvar));
1814  SCIP_CALL( SCIPinferBinvarCons(scip, resvar, TRUE, cons, (int)PROPRULE_3, &infeasible, &tightened) );
1815 
1816  if( infeasible )
1817  {
1818  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1819  SCIP_CALL( analyzeConflictZero(scip, cons) );
1820  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1821  *cutoff = TRUE;
1822  }
1823  else
1824  {
1825  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1826  if( tightened )
1827  {
1828  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1829  (*nfixedvars)++;
1830  }
1831  }
1832 
1833  return SCIP_OKAY;
1834  }
1835 
1836  /* if resultant is fixed to FALSE, and only one operator variable is not fixed to TRUE, this operator variable
1837  * can be fixed to FALSE (rule (4))
1838  */
1839  if( watchedvar2 == -1 && SCIPvarGetUbLocal(resvar) < 0.5 )
1840  {
1841  assert(watchedvar1 != -1);
1842 
1843  SCIP_CALL( analyzeZeroResultant(scip, cons, watchedvar1, watchedvar2, cutoff, nfixedvars) );
1844 
1845  return SCIP_OKAY;
1846  }
1847 
1848  /* switch to the new watched variables */
1849  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
1850 
1851  /* mark the constraint propagated if we have an unfixed resultant or are not in probing, it is necessary that a fixed
1852  * resulting in probing mode does not lead to a propagated constraint, because the constraint upgrade needs to be performed
1853  */
1854  consdata->propagated = (!SCIPinProbing(scip) || (SCIPvarGetLbLocal(consdata->resvar) < 0.5 && SCIPvarGetUbLocal(consdata->resvar) > 0.5));
1855 
1856  return SCIP_OKAY;
1857 }
1858 
1859 /** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
1860  * propagation rule (see propagateCons()):
1861  * (1) v_i = FALSE => r = FALSE
1862  * (2) r = TRUE => v_i = TRUE for all i
1863  * (3) v_i = TRUE for all i => r = TRUE
1864  * (4) r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
1865  */
1866 static
1868  SCIP* scip, /**< SCIP data structure */
1869  SCIP_CONS* cons, /**< constraint that inferred the bound change */
1870  SCIP_VAR* infervar, /**< variable that was deduced */
1871  PROPRULE proprule, /**< propagation rule that deduced the value */
1872  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1873  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1874  )
1875 {
1876  SCIP_CONSDATA* consdata;
1877  SCIP_VAR** vars;
1878  int nvars;
1879  int i;
1880 
1881  assert(result != NULL);
1882 
1883  consdata = SCIPconsGetData(cons);
1884  assert(consdata != NULL);
1885  vars = consdata->vars;
1886  nvars = consdata->nvars;
1887 
1888  switch( proprule )
1889  {
1890  case PROPRULE_1:
1891  /* the resultant was infered to FALSE, because one operand variable was FALSE */
1892  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
1893  assert(infervar == consdata->resvar);
1894  for( i = 0; i < nvars; ++i )
1895  {
1896  if( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
1897  {
1898  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
1899  break;
1900  }
1901  }
1902  assert(i < nvars);
1903  *result = SCIP_SUCCESS;
1904  break;
1905 
1906  case PROPRULE_2:
1907  /* the operand variable was infered to TRUE, because the resultant was TRUE */
1908  assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1909  assert(SCIPgetVarLbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) > 0.5);
1910  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1911  *result = SCIP_SUCCESS;
1912  break;
1913 
1914  case PROPRULE_3:
1915  /* the resultant was infered to TRUE, because all operand variables were TRUE */
1916  assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1917  assert(infervar == consdata->resvar);
1918  for( i = 0; i < nvars; ++i )
1919  {
1920  assert(SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5);
1921  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
1922  }
1923  *result = SCIP_SUCCESS;
1924  break;
1925 
1926  case PROPRULE_4:
1927  /* the operand variable was infered to FALSE, because the resultant was FALSE and all other operands were TRUE */
1928  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
1929  assert(SCIPgetVarUbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) < 0.5);
1930  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1931  for( i = 0; i < nvars; ++i )
1932  {
1933  if( vars[i] != infervar )
1934  {
1935  assert(SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5);
1936  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
1937  }
1938  }
1939  *result = SCIP_SUCCESS;
1940  break;
1941 
1942  case PROPRULE_INVALID:
1943  default:
1944  SCIPerrorMessage("invalid inference information %d in AND-constraint <%s>\n", proprule, SCIPconsGetName(cons));
1945  return SCIP_INVALIDDATA;
1946  }
1947 
1948  return SCIP_OKAY;
1949 }
1950 
1951 /** perform dual presolving on AND-constraints */
1952 static
1954  SCIP* scip, /**< SCIP data structure */
1955  SCIP_CONS** conss, /**< AND-constraints to perform dual presolving on */
1956  int nconss, /**< number of AND-constraints */
1957  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1958  unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
1959  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
1960  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1961  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1962  int* naggrvars, /**< pointer to add up the number of aggregated variables */
1963  int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
1964  int* ndelconss, /**< pointer to add up the number of deleted constraints */
1965  int* nupgdconss, /**< pointer to add up the number of upgraded constraints */
1966  int* naddconss /**< pointer to add up the number of added constraints */
1967  )
1968 {
1969  SCIP_CONS* cons;
1970  SCIP_CONSDATA* consdata;
1971  SCIP_VAR** impoperands;
1972  SCIP_VAR** vars;
1973  SCIP_VAR* resvar;
1974  SCIP_VAR* var;
1975  int nimpoperands;
1976  int nvars;
1977  int size;
1978  int v;
1979  int c;
1980  SCIP_Bool infeasible;
1981  SCIP_Bool fixed;
1982 
1983  assert(scip != NULL);
1984  assert(conss != NULL || nconss == 0);
1985  assert(eventhdlr != NULL);
1986  assert(*entries != NULL);
1987  assert(nentries != NULL);
1988  assert(cutoff != NULL);
1989  assert(nfixedvars != NULL);
1990  assert(naggrvars != NULL);
1991  assert(nchgcoefs != NULL);
1992  assert(ndelconss != NULL);
1993  assert(nupgdconss != NULL);
1994  assert(naddconss != NULL);
1995 
1996  if( nconss == 0 )
1997  return SCIP_OKAY;
1998 
1999  assert(conss != NULL);
2000 
2001  size = 2 * (SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip));
2002 
2003  SCIP_CALL( SCIPallocBufferArray(scip, &impoperands, size) );
2004 
2005  for( c = nconss - 1; c >= 0 && !(*cutoff); --c )
2006  {
2007  cons = conss[c];
2008  assert(cons != NULL);
2009 
2010  if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsModifiable(cons) )
2011  continue;
2012 
2013  /* propagate constraint */
2014  SCIP_CALL( propagateCons(scip, cons, eventhdlr, cutoff, nfixedvars, nupgdconss) );
2015 
2016  if( !SCIPconsIsActive(cons) )
2017  continue;
2018 
2019  if( *cutoff )
2020  break;
2021 
2022  SCIP_CALL( applyFixings(scip, cons, eventhdlr, nchgcoefs) );
2023 
2024  /* merge multiple occurances of variables or variables with their negated variables */
2025  SCIP_CALL( mergeMultiples(scip, cons, eventhdlr, entries, nentries, nfixedvars, nchgcoefs, ndelconss) );
2026 
2027  if( !SCIPconsIsActive(cons) )
2028  continue;
2029 
2030  consdata = SCIPconsGetData(cons);
2031  assert(consdata != NULL);
2032 
2033  vars = consdata->vars;
2034  nvars = consdata->nvars;
2035  assert(vars != NULL || nvars == 0);
2036 
2037  if( nvars == 0 )
2038  continue;
2039 
2040  assert(vars != NULL);
2041 
2042  resvar = consdata->resvar;
2043  assert(resvar != NULL);
2044  /* a fixed resultant needs to be removed, otherwise we might fix operands to a wrong value later on */
2045  assert(SCIPvarGetLbGlobal(resvar) < 0.5 && SCIPvarGetUbGlobal(resvar) > 0.5);
2046  assert(SCIPvarGetNLocksUp(resvar) >= 1 && SCIPvarGetNLocksDown(resvar) >= 1);
2047 
2048  if( SCIPvarGetNLocksUp(resvar) == 1 && SCIPvarGetNLocksDown(resvar) == 1 )
2049  {
2050  SCIP_Real resobj;
2051  SCIP_Real obj;
2052  SCIP_Real posobjsum = 0;
2053  SCIP_Real maxobj = -SCIPinfinity(scip);
2054  int maxpos = -1;
2055  int oldnfixedvars = *nfixedvars;
2056  int oldnaggrvars = *naggrvars;
2057 
2058  nimpoperands = 0;
2059 
2060  /* collect important operands */
2061  for( v = nvars - 1; v >= 0; --v )
2062  {
2063  var = vars[v];
2064  assert(var != NULL);
2065  assert(SCIPvarGetNLocksUp(var) >= 1 && SCIPvarGetNLocksDown(var) >= 1);
2066 
2067  if( SCIPvarGetNLocksUp(var) == 1 && SCIPvarGetNLocksDown(var) == 1 )
2068  {
2069  impoperands[nimpoperands] = var;
2070  ++nimpoperands;
2071 
2072  /* get aggregated objective value of active variable */
2073  SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2074 
2075  /* add up all positive objective values of operands which have exactly one lock in both directions */
2076  if( obj > 0 )
2077  posobjsum += obj;
2078 
2079  /* memorize maximal objective value of operands and its position */
2080  if( obj > maxobj )
2081  {
2082  maxpos = nimpoperands - 1;
2083  maxobj = obj;
2084  }
2085  }
2086  }
2087  assert(nimpoperands >= 0 && nimpoperands <= nvars);
2088 
2089  /* no dual fixable variables found */
2090  if( nimpoperands == 0 )
2091  continue;
2092 
2093  /* get aggregated objective value of active variable */
2094  SCIP_CALL( SCIPvarGetAggregatedObj(resvar, &resobj) );
2095 
2096  /* resultant contributes to the objective with a negative value */
2097  if( SCIPisLE(scip, resobj, 0.0) )
2098  {
2099  SCIP_Bool poscontissmall = SCIPisLE(scip, posobjsum, REALABS(resobj));
2100 
2101  /* if all variables are only locked by this constraint and the resultants contribution more then compensates
2102  * the positive contribution, we can fix all variables to 1
2103  */
2104  if( nimpoperands == nvars && poscontissmall )
2105  {
2106  SCIPdebugMsg(scip, "dual-fixing all variables in constraint <%s> to 1\n", SCIPconsGetName(cons));
2107 
2108  SCIP_CALL( SCIPfixVar(scip, resvar, 1.0, &infeasible, &fixed) );
2109 
2110  *cutoff = *cutoff || infeasible;
2111  if( fixed )
2112  ++(*nfixedvars);
2113 
2114 
2115  for( v = nvars - 1; v >= 0 && !(*cutoff); --v )
2116  {
2117  SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, &infeasible, &fixed) );
2118 
2119  *cutoff = *cutoff || infeasible;
2120  if( fixed )
2121  ++(*nfixedvars);
2122  }
2123 
2124  SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are fixed to one\n", SCIPconsGetName(cons));
2125 
2126  SCIP_CALL( SCIPdelCons(scip, cons) );
2127  ++(*ndelconss);
2128  }
2129  else
2130  {
2131  SCIP_Bool aggregationperformed = FALSE;
2132  SCIP_Bool zerofix = FALSE;
2133 
2134  assert(nimpoperands > 0);
2135 
2136  SCIPdebugMsg(scip, "dual-fixing all variables in constraint <%s> with positive contribution (when together exceeding the negative contribution of the resultant) to 0 and with negative contribution to 1\n", SCIPconsGetName(cons));
2137 
2138  for( v = nimpoperands - 1; v >= 0 && !(*cutoff); --v )
2139  {
2140  /* get aggregated objective value of active variable */
2141  SCIP_CALL( SCIPvarGetAggregatedObj(impoperands[v], &obj) );
2142 
2143  if( SCIPisLE(scip, obj, 0.0) )
2144  {
2145  SCIP_CALL( SCIPfixVar(scip, impoperands[v], 1.0, &infeasible, &fixed) );
2146 
2147  *cutoff = *cutoff || infeasible;
2148  if( fixed )
2149  ++(*nfixedvars);
2150  }
2151  else if( !poscontissmall )
2152  {
2153  SCIP_CALL( SCIPfixVar(scip, impoperands[v], 0.0, &infeasible, &fixed) );
2154  assert(!infeasible);
2155  assert(fixed);
2156 
2157  ++(*nfixedvars);
2158  zerofix = TRUE;
2159  }
2160  else
2161  {
2162  SCIP_Bool redundant;
2163  SCIP_Bool aggregated;
2164 
2165  /* aggregate resultant to operand */
2166  SCIP_CALL( SCIPaggregateVars(scip, resvar, impoperands[v], 1.0, -1.0, 0.0,
2167  &infeasible, &redundant, &aggregated) );
2168  assert(!infeasible);
2169 
2170  if( aggregated )
2171  {
2172  /* note that we cannot remove the aggregated operand because we do not know the position */
2173  ++(*naggrvars);
2174 
2175  aggregationperformed = TRUE;
2176 
2177  SCIPdebugMsg(scip, "dual aggregating operand <%s> with 1 up- and downlock to the resultant <%s> in constraint <%s>\n", SCIPvarGetName(impoperands[v]), SCIPvarGetName(resvar), SCIPconsGetName(cons));
2178  }
2179  }
2180  }
2181  assert(*nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars <= nimpoperands);
2182 
2183  /* did we aggregate the resultant, then we can decide the value to fix it on the (aggregated) objective
2184  * value since it was a independant variable
2185  */
2186  if( aggregationperformed || zerofix )
2187  {
2188  SCIP_Real fixval;
2189 
2190  if( zerofix )
2191  fixval = 0.0;
2192  else
2193  {
2194  /* get aggregated objective value of active variable, that might be changed */
2195  SCIP_CALL( SCIPvarGetAggregatedObj(resvar, &obj) );
2196  assert(!SCIPisPositive(scip, obj));
2197 
2198  fixval = (SCIPisNegative(scip, obj) ? 1.0 : 0.0);
2199  }
2200 
2201  if( fixval < 0.5 || *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars == nvars )
2202  {
2203  SCIPdebugMsg(scip, "constraint <%s> we can fix the resultant <%s> to %g, because the AND-constraint will alwys be fulfilled\n", SCIPconsGetName(cons), SCIPvarGetName(resvar), fixval);
2204 
2205  SCIP_CALL( SCIPfixVar(scip, resvar, fixval, &infeasible, &fixed) );
2206  assert(!infeasible);
2207  assert(fixed);
2208 
2209  ++(*nfixedvars);
2210 
2211  SCIPdebugMsg(scip, "deleting constraint <%s> because \n", SCIPconsGetName(cons));
2212 
2213  SCIP_CALL( SCIPdelCons(scip, cons) );
2214  ++(*ndelconss);
2215  }
2216  }
2217  }
2218  }
2219  /* resultant contributes to the objective with a positive value */
2220  else
2221  {
2222  SCIP_Bool zerofix = FALSE;
2223 #ifndef NDEBUG
2224  SCIP_Real tmpobj;
2225 
2226  assert(nimpoperands > 0);
2227  assert(maxpos >= 0 && maxpos <= consdata->nvars);
2228  assert(!SCIPisInfinity(scip, -maxobj));
2229  SCIP_CALL( SCIPvarGetAggregatedObj(impoperands[maxpos], &tmpobj) );
2230  assert(SCIPisEQ(scip, tmpobj, maxobj));
2231 #endif
2232 
2233  /* if the smallest possible contribution is negative, but does not compensate the positive contribution of
2234  * the resultant we need to fix this variable to 0
2235  */
2236  if( nimpoperands == nvars && SCIPisLE(scip, maxobj, 0.0) )
2237  {
2238  SCIP_Real fixval = (SCIPisLE(scip, REALABS(maxobj), resobj) ? 0.0 : 1.0);
2239 
2240  SCIPdebugMsg(scip, "dual-fixing variable <%s> in constraint <%s> to %g, because the contribution is%s enough to nullify/exceed the contribution of the resultant \n", SCIPvarGetName(impoperands[maxpos]), SCIPconsGetName(cons), fixval, (fixval < 0.5) ? " not" : "");
2241 
2242  SCIP_CALL( SCIPfixVar(scip, impoperands[maxpos], fixval, &infeasible, &fixed) );
2243  zerofix = (fixval < 0.5);
2244 
2245  *cutoff = *cutoff || infeasible;
2246  if( fixed )
2247  ++(*nfixedvars);
2248  }
2249 
2250  SCIPdebugMsg(scip, "dual-fixing all variables, except the variable with the highest contribution to the objective, in constraint <%s> with positive contribution to 0 and with negative contribution to 1\n", SCIPconsGetName(cons));
2251 
2252  for( v = nimpoperands - 1; v >= 0 && !(*cutoff); --v )
2253  {
2254  /* get aggregated objective value of active variable */
2255  SCIP_CALL( SCIPvarGetAggregatedObj(impoperands[v], &obj) );
2256 
2257  if( SCIPisLE(scip, obj, 0.0) )
2258  {
2259  if( v == maxpos )
2260  continue;
2261 
2262  SCIP_CALL( SCIPfixVar(scip, impoperands[v], 1.0, &infeasible, &fixed) );
2263  }
2264  else
2265  {
2266  SCIP_CALL( SCIPfixVar(scip, impoperands[v], 0.0, &infeasible, &fixed) );
2267  zerofix = TRUE;
2268  }
2269 
2270  *cutoff = *cutoff || infeasible;
2271  if( fixed )
2272  ++(*nfixedvars);
2273  }
2274  assert(*nfixedvars - oldnfixedvars <= nimpoperands);
2275  /* iff we have fixed all variables, all variables needed to be stored in the impoperands array */
2276  assert((*nfixedvars - oldnfixedvars == nvars) == (nimpoperands == nvars));
2277 
2278  if( *nfixedvars - oldnfixedvars == nvars )
2279  {
2280  SCIPdebugMsg(scip, "all operands are fixed in constraint <%s> => fix resultant <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(resvar), (zerofix ? 0.0 : 1.0));
2281 
2282  SCIP_CALL( SCIPfixVar(scip, resvar, zerofix ? 0.0 : 1.0, &infeasible, &fixed) );
2283 
2284  *cutoff = *cutoff || infeasible;
2285  if( fixed )
2286  ++(*nfixedvars);
2287 
2288  SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are fixed\n", SCIPconsGetName(cons));
2289 
2290  SCIP_CALL( SCIPdelCons(scip, cons) );
2291  ++(*ndelconss);
2292  }
2293  }
2294  }
2295  /* resultant is lock by another constraint (handler), check for operands with only one down- and uplock */
2296  else
2297  {
2298  SCIP_Real maxobj = -SCIPinfinity(scip);
2299  SCIP_Real resobj;
2300  SCIP_Real obj;
2301  SCIP_Bool redundant;
2302  SCIP_Bool aggregated;
2303  SCIP_Bool resobjispos;
2304  SCIP_Bool linearize = FALSE;
2305  SCIP_Bool zerofix = FALSE;
2306 #ifndef NDEBUG
2307  int oldnchgcoefs = *nchgcoefs;
2308  int oldnfixedvars = *nfixedvars;
2309 #endif
2310 
2311  /* get aggregated objective value of active variable */
2312  SCIP_CALL( SCIPvarGetAggregatedObj(resvar, &resobj) );
2313 
2314  resobjispos = SCIPisGT(scip, resobj, 0.0);
2315 
2316  /* we can only aggregate when the objective contribution of the resultant is less or equal to 0 */
2317  if( !resobjispos )
2318  {
2319  SCIP_Bool goodvarsfound = FALSE;
2320 
2321  for( v = nvars - 1; v >= 0; --v )
2322  {
2323  var = vars[v];
2324  assert(var != NULL);
2325  assert(SCIPvarGetNLocksUp(var) >= 1 && SCIPvarGetNLocksDown(var) >= 1);
2326 
2327  /* get aggregated objective value of active variable */
2328  SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2329 
2330  /* all operands which are only locked by this constraint, the objective contribution is greater or equal
2331  * to 0 can be aggregated to the resultant
2332  */
2333  if( SCIPvarGetNLocksUp(var) == 1 && SCIPvarGetNLocksDown(var) == 1 )
2334  {
2335  if( !SCIPisNegative(scip, obj) )
2336  {
2337  /* aggregate resultant to operand */
2338  SCIP_CALL( SCIPaggregateVars(scip, resvar, var, 1.0, -1.0, 0.0,
2339  &infeasible, &redundant, &aggregated) );
2340 
2341  if( aggregated )
2342  {
2343  ++(*naggrvars);
2344 
2345  linearize = TRUE;
2346 
2347  /* delete redundant entry from constraint */
2348  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
2349  ++(*nchgcoefs);
2350 
2351  SCIPdebugMsg(scip, "dual aggregating operand <%s> with 1 up- and downlock to the resultant <%s> in constraint <%s>\n", SCIPvarGetName(var), SCIPvarGetName(resvar), SCIPconsGetName(cons));
2352  }
2353 
2354  *cutoff = *cutoff || infeasible;
2355  }
2356  else
2357  goodvarsfound = TRUE;
2358  }
2359  }
2360  assert(*nchgcoefs - oldnchgcoefs <= nvars);
2361 
2362  /* if we aggregated an operands with the resultant we can also fix "good" independant operands to 1, since
2363  * the correctness of "resultant = 0 => at least one operand = 0" in enforced by that aggregation
2364  * without an aggregation we cannot fix these variables since it might lead to infeasibility, e.g.
2365  *
2366  * obj(x3) = -1
2367  * r = x1 * x2 * x3
2368  * r = 0
2369  * x1 = 1
2370  * x2 = 1
2371  */
2372  if( !*cutoff && goodvarsfound && linearize )
2373  {
2374  /* fix good variables to 1 */
2375  for( v = consdata->nvars - 1; v >= 0; --v )
2376  {
2377  var = vars[v];
2378  assert(var != NULL);
2379 
2380  if( SCIPvarGetNLocksUp(var) == 1 && SCIPvarGetNLocksDown(var) == 1 )
2381  {
2382 #ifndef NDEBUG
2383  /* aggregated objective value of active variable need to be negative */
2384  SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2385  assert(SCIPisNegative(scip, obj));
2386 #endif
2387  SCIPdebugMsg(scip, "dual-fixing variable <%s> in constraint <%s> to 1, because the contribution is negative\n", SCIPvarGetName(var), SCIPconsGetName(cons));
2388 
2389  SCIP_CALL( SCIPfixVar(scip, var, 1.0, &infeasible, &fixed) );
2390 
2391  assert(!infeasible);
2392  if( fixed )
2393  ++(*nfixedvars);
2394  }
2395  }
2396  assert(*nfixedvars - oldnfixedvars <= consdata->nvars);
2397  }
2398  assert(*nchgcoefs - oldnchgcoefs + *nfixedvars - oldnfixedvars <= nvars);
2399  }
2400  /* if the downlocks of the resultant are only from this constraint and the objective contribution is positive,
2401  * we can try to fix operands
2402  */
2403  else if( SCIPvarGetNLocksDown(resvar) == 1 )
2404  {
2405  SCIP_Bool locksareone = TRUE;
2406  int maxpos = -1;
2407 
2408  for( v = nvars - 1; v >= 0; --v )
2409  {
2410  var = vars[v];
2411  assert(var != NULL);
2412  assert(SCIPvarGetNLocksUp(var) >= 1 && SCIPvarGetNLocksDown(var) >= 1);
2413 
2414  /* check if all resultants are only locked by this constraint */
2415  locksareone = locksareone && (SCIPvarGetNLocksUp(var) == 1 && SCIPvarGetNLocksDown(var) == 1);
2416 
2417  /* get aggregated objective value of active variable */
2418  SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2419 
2420  /* memorize maximal objective value of operands and its position */
2421  if( obj > maxobj )
2422  {
2423  maxpos = v;
2424  maxobj = obj;
2425  }
2426 
2427  /* all operands which are only locked by this constraint, the objective contribution is greater or equal
2428  * to 0, and the absolute value of the contribution of the resultant exceeds can be eliminated and
2429  * aggregated to the resultant
2430  */
2431  if( SCIPvarGetNLocksUp(var) == 1 && SCIPvarGetNLocksDown(var) == 1 && SCIPisGE(scip, obj, 0.0) )
2432  {
2433  SCIPdebugMsg(scip, "dualfix operand <%s> in constraint <%s> to 0\n", SCIPvarGetName(var), SCIPconsGetName(cons));
2434 
2435  SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
2436 
2437  *cutoff = *cutoff || infeasible;
2438  if( fixed )
2439  ++(*nfixedvars);
2440 
2441  zerofix = TRUE;
2442  }
2443  }
2444  assert(*nchgcoefs - oldnchgcoefs <= nvars);
2445 
2446  /* if constraint is still active and all operands are only lock by this constraint, we check if we can fix
2447  * the worst (in objective contribution) operand to zero
2448  */
2449  if( !zerofix && locksareone && SCIPisGE(scip, resobj, REALABS(maxobj)) )
2450  {
2451  assert(!zerofix);
2452  /* objective contribution needs to be negative, otherwise, the variable should already be fixed to 0 */
2453  assert(SCIPisLT(scip, maxobj, 0.0));
2454 
2455  SCIPdebugMsg(scip, "dualfix operand <%s> with worst contribution in constraint <%s> to 0\n", SCIPvarGetName(vars[maxpos]), SCIPconsGetName(cons));
2456 
2457  SCIP_CALL( SCIPfixVar(scip, vars[maxpos], 0.0, &infeasible, &fixed) );
2458 
2459  *cutoff = *cutoff || infeasible;
2460  if( fixed )
2461  ++(*nfixedvars);
2462 
2463  zerofix = TRUE;
2464  }
2465 
2466  /* fix the resultant if one operand was fixed to zero and delete the constraint */
2467  if( zerofix )
2468  {
2469  SCIPdebugMsg(scip, "fix resultant <%s> in constraint <%s> to 0\n", SCIPvarGetName(resvar), SCIPconsGetName(cons));
2470 
2471  SCIP_CALL( SCIPfixVar(scip, resvar, 0.0, &infeasible, &fixed) );
2472 
2473  *cutoff = *cutoff || infeasible;
2474  if( fixed )
2475  ++(*nfixedvars);
2476 
2477  SCIPdebugMsg(scip, "deleting constraint <%s> because at least one operand and the resultant is fixed to zero\n", SCIPconsGetName(cons));
2478 
2479  SCIP_CALL( SCIPdelCons(scip, cons) );
2480  ++(*ndelconss);
2481  }
2482  }
2483 
2484  /* we have to linearize the constraint, otherwise we might get wrong propagations, since due to aggregations a
2485  * resultant fixed to zero is already fulfilling the constraint, and we must not ensure that some remaining
2486  * operand needs to be 0
2487  */
2488  if( linearize )
2489  {
2490  SCIP_CONS* newcons;
2491  char consname[SCIP_MAXSTRLEN];
2492  SCIP_VAR* consvars[2];
2493  SCIP_Real vals[2];
2494 
2495  assert(SCIPconsIsActive(cons));
2496 
2497  consvars[0] = consdata->resvar;
2498  vals[0] = 1.0;
2499  vals[1] = -1.0;
2500 
2501  /* create operator linear constraints */
2502  for( v = consdata->nvars - 1; v >= 0; --v )
2503  {
2504  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), v);
2505  consvars[1] = consdata->vars[v];
2506 
2507  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, consvars, vals, -SCIPinfinity(scip), 0.0,
2511  SCIPconsIsStickingAtNode(cons)) );
2512 
2513  /* add constraint */
2514  SCIP_CALL( SCIPaddCons(scip, newcons) );
2515  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
2516  }
2517  (*naddconss) += consdata->nvars;
2518 
2519  SCIPdebugMsg(scip, "deleting constraint <%s> because it was linearized\n", SCIPconsGetName(cons));
2520 
2521  SCIP_CALL( SCIPdelCons(scip, cons) );
2522  ++(*ndelconss);
2523  }
2524  /* if only one operand is leftover, aggregate it to the resultant */
2525  else if( consdata->nvars == 1 )
2526  {
2527  SCIPdebugMsg(scip, "aggregating last operand <%s> to the resultant <%s> in constraint <%s>\n", SCIPvarGetName(consdata->vars[0]), SCIPvarGetName(resvar), SCIPconsGetName(cons));
2528 
2529  /* aggregate resultant to operand */
2530  SCIP_CALL( SCIPaggregateVars(scip, resvar, consdata->vars[0], 1.0, -1.0, 0.0,
2531  &infeasible, &redundant, &aggregated) );
2532 
2533  if( aggregated )
2534  ++(*naggrvars);
2535 
2536  *cutoff = *cutoff || infeasible;
2537 
2538  SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are removed\n", SCIPconsGetName(cons));
2539 
2540  SCIP_CALL( SCIPdelCons(scip, cons) );
2541  ++(*ndelconss);
2542  }
2543 
2544  /* if no operand is leftover delete the constraint */
2545  if( SCIPconsIsActive(cons) && consdata->nvars == 0 )
2546  {
2547  SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are removed\n", SCIPconsGetName(cons));
2548 
2549  SCIP_CALL( SCIPdelCons(scip, cons) );
2550  ++(*ndelconss);
2551  }
2552  }
2553  }
2554 
2555  SCIPfreeBufferArray(scip, &impoperands);
2556 
2557  return SCIP_OKAY;
2558 }
2559 
2560 /** 1. check if at least two operands or one operand and the resultant are in one clique, if so, we can fix the
2561  * resultant to zero and in the former case we can also delete this constraint but we need to extract the clique
2562  * information as constraint
2563  *
2564  * x == AND(y, z) and clique(y,z) => x = 0, delete constraint and create y + z <= 1
2565  * x == AND(y, z) and clique(x,y) => x = 0
2566  *
2567  * special handled cases are:
2568  * - if the resultant is a negation of an operand, in that case we fix the resultant to 0
2569  * - if the resultant is equal to an operand, we will linearize this constraint by adding all necessary
2570  * set-packing constraints like resultant + ~operand <= 1 and delete the old constraint
2571  *
2572  * x == AND(~x, y) => x = 0
2573  * x == AND(x, y) => add x + ~y <= 1 and delete the constraint
2574  *
2575  * 2. check if one operand is in a clique with the negation of all other operands, this means we can aggregate this
2576  * operand to the resultant
2577  *
2578  * r == AND(x,y,z) and clique(x,~y) and clique(x,~z) => r == x
2579  *
2580  * 3. check if the resultant and the negations of all operands are in a clique
2581  *
2582  * r == AND(x,y) and clique(r, ~x,~y) => upgrade the constraint to a set-partitioning constraint r + ~x + ~y = 1
2583  *
2584  * @note We removed also fixed variables and propagate them, and if only one operand is remaining due to removal, we
2585  * will aggregate the resultant with this operand
2586  */
2587 static
2589  SCIP* scip, /**< SCIP data structure */
2590  SCIP_CONS* cons, /**< constraint to process */
2591  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2592  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2593  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
2594  int* naggrvars, /**< pointer to add up the number of aggregated variables */
2595  int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
2596  int* ndelconss, /**< pointer to add up the number of deleted constraints */
2597  int* naddconss /**< pointer to add up the number of added constraints */
2598  )
2599 {
2600  SCIP_CONSDATA* consdata;
2601  SCIP_VAR** vars;
2602  SCIP_VAR* var1;
2603  SCIP_VAR* var2;
2604  int nvars;
2605  int vstart;
2606  int vend;
2607  int v;
2608  int v2;
2609  SCIP_Bool negated;
2610  SCIP_Bool value1;
2611  SCIP_Bool value2;
2612  SCIP_Bool infeasible;
2613  SCIP_Bool fixed;
2614  SCIP_Bool allnegoperandsexist;
2615 
2616  assert(scip != NULL);
2617  assert(cons != NULL);
2618  assert(eventhdlr != NULL);
2619  assert(cutoff != NULL);
2620  assert(nfixedvars != NULL);
2621  assert(naggrvars != NULL);
2622  assert(nchgcoefs != NULL);
2623  assert(ndelconss != NULL);
2624  assert(naddconss != NULL);
2625 
2626  consdata = SCIPconsGetData(cons);
2627  assert(consdata != NULL);
2628 
2629  if( !SCIPconsIsActive(cons) || SCIPconsIsModifiable(cons) )
2630  return SCIP_OKAY;
2631 
2632  vars = consdata->vars;
2633  nvars = consdata->nvars;
2634  assert(vars != NULL || nvars == 0);
2635 
2636  /* remove fixed variables to be able to ask for cliques
2637  *
2638  * if an operand is fixed to 0 fix the resultant to 0 and delete the constraint
2639  * if an operand is fixed to 1 remove it from the constraint
2640  */
2641  for( v = nvars - 1; v >= 0; --v )
2642  {
2643  assert(vars != NULL);
2644 
2645  if( SCIPvarGetLbGlobal(vars[v]) > 0.5 )
2646  {
2647  SCIPdebugMsg(scip, "In constraint <%s> the operand <%s> is fixed to 1 so remove it from the constraint\n",
2648  SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
2649 
2650  /* because we loop from back to front we can delete the entry in the consdata structure */
2651  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
2652  ++(*nchgcoefs);
2653 
2654  assert(consdata->vars == vars);
2655 
2656  continue;
2657  }
2658  else if( SCIPvarGetUbGlobal(vars[v]) < 0.5 )
2659  {
2660  SCIPdebugMsg(scip, "constraint <%s> redundant: because operand <%s> is fixed to zero so we can fix the resultant <%s> to 0\n",
2661  SCIPconsGetName(cons), SCIPvarGetName(vars[v]), SCIPvarGetName(consdata->resvar));
2662 
2663  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2664  *cutoff = *cutoff || infeasible;
2665  if( fixed )
2666  ++(*nfixedvars);
2667 
2668  SCIP_CALL( SCIPdelCons(scip, cons) );
2669  ++(*ndelconss);
2670 
2671  return SCIP_OKAY;
2672  }
2673  }
2674 
2675  /* if we deleted some operands constraint might be redundant */
2676  if( consdata->nvars < nvars )
2677  {
2678  assert(vars == consdata->vars);
2679 
2680  /* all operands fixed to one were removed, so if no operand is left this means we can fix the resultant to 1
2681  * too
2682  */
2683  if( consdata->nvars == 0 )
2684  {
2685  SCIPdebugMsg(scip, "All operand in constraint <%s> were deleted, so the resultant needs to be fixed to 1\n",
2686  SCIPconsGetName(cons));
2687 
2688  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 1.0, &infeasible, &fixed) );
2689  *cutoff = *cutoff || infeasible;
2690  if( fixed )
2691  ++(*nfixedvars);
2692 
2693  SCIP_CALL( SCIPdelCons(scip, cons) );
2694  ++(*ndelconss);
2695 
2696  return SCIP_OKAY;
2697  }
2698  /* if only one not fixed operand is left, we can aggregate it to the resultant */
2699  else if( consdata->nvars == 1 )
2700  {
2701  SCIP_Bool redundant;
2702  SCIP_Bool aggregated;
2703 
2704  /* aggregate resultant to last operand */
2705  SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
2706  &infeasible, &redundant, &aggregated) );
2707 
2708  if( aggregated )
2709  ++(*naggrvars);
2710 
2711  SCIP_CALL( SCIPdelCons(scip, cons) );
2712  ++(*ndelconss);
2713 
2714  *cutoff = *cutoff || infeasible;
2715 
2716  return SCIP_OKAY;
2717  }
2718 
2719  nvars = consdata->nvars;
2720  }
2721 
2722  /* @todo when cliques are improved, we only need to collect all clique-ids for all variables and check for doubled
2723  * entries
2724  */
2725  /* case 1 first part */
2726  /* check if two operands are in a clique */
2727  for( v = nvars - 1; v > 0; --v )
2728  {
2729  assert(vars != NULL);
2730 
2731  var1 = vars[v];
2732  assert(var1 != NULL);
2733  negated = FALSE;
2734 
2735  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
2736  assert(var1 != NULL);
2737 
2738  if( negated )
2739  value1 = FALSE;
2740  else
2741  value1 = TRUE;
2742 
2743  assert(SCIPvarGetStatus(var1) != SCIP_VARSTATUS_FIXED);
2744 
2745  for( v2 = v - 1; v2 >= 0; --v2 )
2746  {
2747  var2 = vars[v2];
2748  assert(var2 != NULL);
2749 
2750  negated = FALSE;
2751  SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
2752  assert(var2 != NULL);
2753 
2754  if( negated )
2755  value2 = FALSE;
2756  else
2757  value2 = TRUE;
2758 
2759  assert(SCIPvarGetStatus(var2) != SCIP_VARSTATUS_FIXED);
2760 
2761  /* if both variables are negated of each other or the same, this will be handled in applyFixings();
2762  * @note if both variables are the same, then SCIPvarsHaveCommonClique() will return TRUE, so we better
2763  * continue
2764  */
2765  if( var1 == var2 )
2766  continue;
2767 
2768  if( SCIPvarsHaveCommonClique(var1, value1, var2, value2, TRUE) )
2769  {
2770  SCIP_CONS* cliquecons;
2771  SCIP_VAR* consvars[2];
2772  char name[SCIP_MAXSTRLEN];
2773 
2774  SCIPdebugMsg(scip, "constraint <%s> redundant: because variable <%s> and variable <%s> are in a clique, the resultant <%s> can be fixed to 0\n",
2775  SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2), SCIPvarGetName(consdata->resvar));
2776 
2777  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2778  *cutoff = *cutoff || infeasible;
2779  if( fixed )
2780  ++(*nfixedvars);
2781 
2782 
2783  /* create clique constraint which lead to the last fixing */
2784  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq", SCIPconsGetName(cons), v2);
2785 
2786  if( value1 )
2787  consvars[0] = var1;
2788  else
2789  {
2790  SCIP_CALL( SCIPgetNegatedVar(scip, var1, &(consvars[0])) );
2791  }
2792 
2793  if( value2 )
2794  consvars[1] = var2;
2795  else
2796  {
2797  SCIP_CALL( SCIPgetNegatedVar(scip, var2, &(consvars[1])) );
2798  }
2799 
2800  SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 2, consvars,
2802  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2804  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
2805  SCIPdebugMsg(scip, " -> adding clique constraint: ");
2806  SCIPdebugPrintCons(scip, cliquecons, NULL);
2807  SCIP_CALL( SCIPaddCons(scip, cliquecons) );
2808  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2809  ++(*naddconss);
2810 
2811  SCIP_CALL( SCIPdelCons(scip, cons) );
2812  ++(*ndelconss);
2813 
2814  return SCIP_OKAY;
2815  }
2816  }
2817  }
2818 
2819  var1 = consdata->resvar;
2820  assert(var1 != NULL);
2821 
2822  negated = FALSE;
2823  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
2824  assert(var1 != NULL);
2825 
2826  /* it may appear that we have a fixed resultant */
2827  if( SCIPvarGetStatus(var1) == SCIP_VARSTATUS_FIXED )
2828  {
2829  /* resultant is fixed to 1, so fix all operands to 1 */
2830  if( SCIPvarGetLbGlobal(consdata->resvar) > 0.5 )
2831  {
2832  SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> is fixed to 1 so fix all operands to 1\n",
2833  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
2834 
2835  /* fix all operands to 1 */
2836  for( v = nvars - 1; v >= 0 && !(*cutoff); --v )
2837  {
2838  assert(vars != NULL);
2839 
2840  SCIPdebugMsg(scip, "Fixing operand <%s> to 1.\n", SCIPvarGetName(vars[v]));
2841 
2842  SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, &infeasible, &fixed) );
2843  *cutoff = *cutoff || infeasible;
2844 
2845  if( fixed )
2846  ++(*nfixedvars);
2847  }
2848 
2849  SCIP_CALL( SCIPdelCons(scip, cons) );
2850  ++(*ndelconss);
2851  }
2852  /* the upgrade to a linear constraint because of the to 0 fixed resultant we do in propagateCons() */
2853  else
2854  assert(SCIPvarGetUbGlobal(consdata->resvar) < 0.5);
2855 
2856  return SCIP_OKAY;
2857  }
2858 
2859  if( negated )
2860  value1 = FALSE;
2861  else
2862  value1 = TRUE;
2863 
2864  /* case 1 second part */
2865  /* check if one operands is in a clique with the resultant */
2866  for( v = nvars - 1; v >= 0; --v )
2867  {
2868  assert(vars != NULL);
2869 
2870  var2 = vars[v];
2871  assert(var2 != NULL);
2872 
2873  negated = FALSE;
2874  SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
2875  assert(var2 != NULL);
2876 
2877  if( negated )
2878  value2 = FALSE;
2879  else
2880  value2 = TRUE;
2881 
2882  /* if both variables are negated of each other or the same, this will be handled in applyFixings();
2883  * @note if both variables are the same, then SCIPvarsHaveCommonClique() will return TRUE, so we better continue
2884  */
2885  if( var1 == var2 )
2886  {
2887  /* x1 == AND(~x1, x2 ...) => x1 = 0 */
2888  if( value1 != value2 )
2889  {
2890  SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> can be fixed to 0 because the negation of it is an operand.\n",
2891  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
2892 
2893  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2894  *cutoff = *cutoff || infeasible;
2895 
2896  if( fixed )
2897  ++(*nfixedvars);
2898 
2899  return SCIP_OKAY;
2900  }
2901  /* x1 == AND(x1, x2 ...) => delete constraint and create all set-packing constraints x1 + ~x2 <= 1, x1 + ~... <= 1 */
2902  else
2903  {
2904  SCIP_CONS* cliquecons;
2905  SCIP_VAR* consvars[2];
2906  char name[SCIP_MAXSTRLEN];
2907 
2908  assert(value1 == value2);
2909 
2910  consvars[0] = consdata->resvar;
2911 
2912  for( v2 = nvars - 1; v2 >= 0; --v2 )
2913  {
2914  var2 = vars[v2];
2915  negated = FALSE;
2916  SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
2917 
2918  /* if the active representations of the resultant and an operand are different then we need to extract
2919  * this as a clique constraint
2920  *
2921  * if the active representations of the resultant and an operand are equal then the clique constraint
2922  * would look like x1 + ~x1 <= 1, which is redundant
2923  *
2924  * if the active representations of the resultant and an operand are negated of each other then the
2925  * clique constraint would look like x1 + x1 <= 1, which will lead to a fixation of the resultant later
2926  * on
2927  */
2928  if( var1 == var2 )
2929  {
2930  if( value1 == negated )
2931  {
2932  SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> can be fixed to 0 because the negation of it is an operand.\n",
2933  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
2934 
2935  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2936  *cutoff = *cutoff || infeasible;
2937 
2938  if( fixed )
2939  ++(*nfixedvars);
2940 
2941  break;
2942  }
2943  }
2944  else
2945  {
2946  SCIP_CALL( SCIPgetNegatedVar(scip, vars[v2], &consvars[1]) );
2947  assert(consvars[1] != NULL);
2948 
2949  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%d", SCIPconsGetName(cons), v2);
2950 
2951  SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 2, consvars,
2953  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
2955  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
2956  SCIPdebugMsg(scip, " -> adding clique constraint: ");
2957  SCIPdebugPrintCons(scip, cliquecons, NULL);
2958  SCIP_CALL( SCIPaddCons(scip, cliquecons) );
2959  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2960  ++(*naddconss);
2961  }
2962  }
2963 
2964  /* delete old constraint */
2965  SCIP_CALL( SCIPdelCons(scip, cons) );
2966  ++(*ndelconss);
2967 
2968  return SCIP_OKAY;
2969  }
2970  }
2971 
2972  /* due to SCIPvarsHaveCommonClique() returns on two same variables that they are in a clique, we need to handle
2973  * it explicitly
2974  */
2975  if( var1 == var2 && value1 == value2 )
2976  continue;
2977 
2978  /* due to SCIPvarsHaveCommonClique() returns on two negated variables that they are not in a clique, we need to
2979  * handle it explicitly
2980  */
2981  if( (var1 == var2 && value1 != value2) || SCIPvarsHaveCommonClique(var1, value1, var2, value2, TRUE) )
2982  {
2983  SCIPdebugMsg(scip, "in constraint <%s> the resultant <%s> can be fixed to 0 because it is in a clique with operand <%s>\n",
2984  SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2));
2985 
2986  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2987  *cutoff = *cutoff || infeasible;
2988  if( fixed )
2989  ++(*nfixedvars);
2990 
2991  return SCIP_OKAY;
2992  }
2993  }
2994 
2995  if( !SCIPconsIsActive(cons) )
2996  return SCIP_OKAY;
2997 
2998  v2 = -1;
2999  /* check which operands have a negated variable */
3000  for( v = nvars - 1; v >= 0; --v )
3001  {
3002  assert(vars != NULL);
3003 
3004  var1 = vars[v];
3005  assert(var1 != NULL);
3006 
3007  negated = FALSE;
3008  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
3009  assert(var1 != NULL);
3010 
3011  if( SCIPvarGetNegatedVar(var1) == NULL )
3012  {
3013  if( v2 >= 0 )
3014  break;
3015  v2 = v;
3016  }
3017  }
3018 
3019  allnegoperandsexist = FALSE;
3020 
3021  /* all operands have a negated variable, so we will check for all possible negated ciques */
3022  if( v2 == -1 )
3023  {
3024  allnegoperandsexist = TRUE;
3025  vstart = nvars - 1;
3026  vend = 0;
3027  }
3028  /* exactly one operands has no negated variable, so only this variable can be in a clique with all other negations */
3029  else if( v2 >= 0 && v == -1 )
3030  {
3031  vstart = v2;
3032  vend = v2;
3033  }
3034  /* at least two operands have no negated variable, so there is no possible clique with negated variables */
3035  else
3036  {
3037  vstart = -1;
3038  vend = 0;
3039  }
3040 
3041  /* case 2 */
3042  /* check for negated cliques in the operands */
3043  for( v = vstart; v >= vend; --v )
3044  {
3045  assert(vars != NULL);
3046 
3047  var1 = vars[v];
3048  assert(var1 != NULL);
3049 
3050  negated = FALSE;
3051  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
3052  assert(var1 != NULL);
3053 
3054  if( negated )
3055  value1 = FALSE;
3056  else
3057  value1 = TRUE;
3058 
3059  for( v2 = nvars - 1; v2 >= 0; --v2 )
3060  {
3061  if( v2 == v )
3062  continue;
3063 
3064  var2 = vars[v2];
3065  assert(var2 != NULL);
3066 
3067  negated = FALSE;
3068  SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
3069  assert(var2 != NULL);
3070 
3071  if( negated )
3072  value2 = FALSE;
3073  else
3074  value2 = TRUE;
3075 
3076  assert(SCIPvarGetNegatedVar(var2) != NULL);
3077 
3078  /* invert flag, because we want to check var 1 against all negations of the other variables */
3079  value2 = !value2;
3080 
3081  /* due to SCIPvarsHaveCommonClique() returns on two same variables that they are in a clique, we need to handle
3082  * it explicitly
3083  */
3084  if( var1 == var2 && value1 == value2 )
3085  {
3086  SCIPdebugMsg(scip, "in constraint <%s> the resultant <%s> can be fixed to 0 because two operands are negated of each other\n",
3087  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
3088 
3089  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3090  *cutoff = *cutoff || infeasible;
3091  if( fixed )
3092  ++(*nfixedvars);
3093 
3094  return SCIP_OKAY;
3095  }
3096 
3097  /* due to SCIPvarsHaveCommonClique() returns on two negated variables that they are not in a clique, we need to
3098  * handle it explicitly
3099  */
3100  if( var1 == var2 && value1 != value2 )
3101  continue;
3102 
3103  if( !SCIPvarsHaveCommonClique(var1, value1, var2, value2, TRUE) )
3104  break;
3105  }
3106 
3107  if( v2 == -1 )
3108  {
3109  SCIP_Bool redundant;
3110  SCIP_Bool aggregated;
3111 
3112  SCIPdebugMsg(scip, "In constraint <%s> the operand <%s> is in a negated clique with all other operands, so we can aggregated this operand to the resultant <%s>.\n",
3113  SCIPconsGetName(cons), SCIPvarGetName(vars[v]), SCIPvarGetName(consdata->resvar));
3114 
3115  SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, vars[v], 1.0, -1.0, 0.0,
3116  &infeasible, &redundant, &aggregated) );
3117  *cutoff = *cutoff || infeasible;
3118 
3119  if( aggregated )
3120  ++(*naggrvars);
3121 
3122  return SCIP_OKAY;
3123  }
3124  }
3125 
3126  /* case 3 */
3127  /* check if the resultant and the negations of the operands are in a clique, then we can upgrade this constraint to a
3128  * set-partitioning constraint
3129  */
3130  if( allnegoperandsexist && SCIPconsIsActive(cons) )
3131  {
3132  SCIP_VAR** newvars;
3133  SCIP_Bool* negations;
3134  SCIP_Bool upgrade;
3135 
3136  SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars + 1) );
3137  SCIP_CALL( SCIPallocBufferArray(scip, &negations, nvars + 1) );
3138  BMSclearMemoryArray(negations, nvars + 1);
3139 
3140  var1 = consdata->resvar;
3141  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negations[nvars]) );
3142  assert(var1 != NULL);
3143  assert(SCIPvarGetStatus(var1) != SCIP_VARSTATUS_FIXED);
3144 
3145  newvars[nvars] = var1;
3146 
3147  /* get active variables */
3148  for( v = nvars - 1; v >= 0; --v )
3149  {
3150  assert(vars != NULL);
3151 
3152  var1 = vars[v];
3153  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negations[v]) );
3154  assert(var1 != NULL);
3155  assert(SCIPvarGetStatus(var1) != SCIP_VARSTATUS_FIXED);
3156 
3157  newvars[v] = var1;
3158 
3159  /* there should be no variable left that is equal or negated to the resultant */
3160  assert(newvars[v] != newvars[nvars]);
3161  }
3162 
3163  upgrade = TRUE;
3164 
3165  /* the resultant is in a clique with the negations of all operands, due to this AND-constraint */
3166  /* only check if the negations of all operands are in a clique */
3167  for( v = nvars - 1; v >= 0 && upgrade; --v )
3168  {
3169  for( v2 = v - 1; v2 >= 0; --v2 )
3170  {
3171  /* the resultant need to be in a clique with the negations of all operands */
3172  if( !SCIPvarsHaveCommonClique(newvars[v], negations[v], newvars[v2], negations[v2], TRUE) )
3173  {
3174  upgrade = FALSE;
3175  break;
3176  }
3177  }
3178  }
3179 
3180  /* all variables are in a clique, so upgrade thi AND-constraint */
3181  if( upgrade )
3182  {
3183  SCIP_CONS* cliquecons;
3184  char name[SCIP_MAXSTRLEN];
3185 
3186  /* get new constraint variables */
3187  if( negations[nvars] )
3188  {
3189  /* negation does not need to be existing, so SCIPvarGetNegatedVar() cannot be called
3190  * (e.g. resultant = ~x = 1 - x and x = y = newvars[nvars] and negations[nvars] = TRUE,
3191  * then y does not need to have a negated variable, yet)
3192  */
3193  SCIP_CALL( SCIPgetNegatedVar(scip, newvars[nvars], &(newvars[nvars])) );
3194  }
3195  assert(newvars[nvars] != NULL);
3196 
3197  for( v = nvars - 1; v >= 0; --v )
3198  {
3199  if( !negations[v] )
3200  {
3201  /* negation does not need to be existing, so SCIPvarGetNegatedVar() cannot be called
3202  * (e.g. vars[v] = ~x = 1 - x and x = y = newvars[v] and negations[v] = TRUE,
3203  * then y does not need to have a negated variable, yet)
3204  */
3205  SCIP_CALL( SCIPgetNegatedVar(scip, newvars[v], &(newvars[v])) );
3206  }
3207  assert(newvars[v] != NULL);
3208  }
3209 
3210  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clqeq", SCIPconsGetName(cons));
3211 
3212  SCIP_CALL( SCIPcreateConsSetpart(scip, &cliquecons, name, nvars + 1, newvars,
3214  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3216  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3217  SCIPdebugMsg(scip, " -> upgrading AND-constraint <%s> with use of clique information to a set-partitioning constraint: \n", SCIPconsGetName(cons));
3218  SCIPdebugPrintCons(scip, cliquecons, NULL);
3219  SCIP_CALL( SCIPaddCons(scip, cliquecons) );
3220  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
3221  ++(*naddconss);
3222 
3223  /* delete old constraint */
3224  SCIP_CALL( SCIPdelCons(scip, cons) );
3225  ++(*ndelconss);
3226  }
3227 
3228  SCIPfreeBufferArray(scip, &negations);
3229  SCIPfreeBufferArray(scip, &newvars);
3230  }
3231 
3232  return SCIP_OKAY;
3233 }
3234 
3235 /** gets the key of the given element */
3236 static
3237 SCIP_DECL_HASHGETKEY(hashGetKeyAndcons)
3238 { /*lint --e{715}*/
3239  /* the key is the element itself */
3240  return elem;
3241 }
3242 
3243 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
3244 static
3245 SCIP_DECL_HASHKEYEQ(hashKeyEqAndcons)
3247  SCIP_CONSDATA* consdata1;
3248  SCIP_CONSDATA* consdata2;
3249  SCIP_Bool coefsequal;
3250  int i;
3251 #ifndef NDEBUG
3252  SCIP* scip;
3253 
3254  scip = (SCIP*)userptr;
3255  assert(scip != NULL);
3256 #endif
3257 
3258  consdata1 = SCIPconsGetData((SCIP_CONS*)key1);
3259  consdata2 = SCIPconsGetData((SCIP_CONS*)key2);
3260 
3261  /* checks trivial case */
3262  if( consdata1->nvars != consdata2->nvars )
3263  return FALSE;
3264 
3265  /* sorts the constraints */
3266  consdataSort(consdata1);
3267  consdataSort(consdata2);
3268  assert(consdata1->sorted);
3269  assert(consdata2->sorted);
3270 
3271  coefsequal = TRUE;
3272 
3273  for( i = 0; i < consdata1->nvars ; ++i )
3274  {
3275  /* tests if variables are equal */
3276  if( consdata1->vars[i] != consdata2->vars[i] )
3277  {
3278  assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
3279  SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
3280  coefsequal = FALSE;
3281  break;
3282  }
3283  assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
3284  }
3285 
3286  return coefsequal;
3287 }
3288 
3289 /** returns the hash value of the key */
3290 static
3291 SCIP_DECL_HASHKEYVAL(hashKeyValAndcons)
3292 { /*lint --e{715}*/
3293  SCIP_CONSDATA* consdata;
3294  int minidx;
3295  int mididx;
3296  int maxidx;
3297 
3298  consdata = SCIPconsGetData((SCIP_CONS*)key);
3299  assert(consdata != NULL);
3300  assert(consdata->sorted);
3301  assert(consdata->nvars > 0);
3302 
3303  minidx = SCIPvarGetIndex(consdata->vars[0]);
3304  mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
3305  maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
3306  assert(minidx >= 0 && minidx <= maxidx);
3307 
3308  return SCIPhashTwo(SCIPcombineTwoInt(consdata->nvars, minidx),
3309  SCIPcombineTwoInt(mididx, maxidx));
3310 }
3311 
3312 /** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
3313  * accordingly; in contrast to removeRedundantConstraints(), it uses a hash table
3314  */
3315 static
3317  SCIP* scip, /**< SCIP data structure */
3318  BMS_BLKMEM* blkmem, /**< block memory */
3319  SCIP_CONS** conss, /**< constraint set */
3320  int nconss, /**< number of constraints in constraint set */
3321  int* firstchange, /**< pointer to store first changed constraint */
3322  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3323  int* naggrvars, /**< pointer to count number of aggregated variables */
3324  int* ndelconss /**< pointer to count number of deleted constraints */
3325  )
3326 {
3327  SCIP_HASHTABLE* hashtable;
3328  int hashtablesize;
3329  int c;
3330 
3331  assert(conss != NULL);
3332  assert(ndelconss != NULL);
3333 
3334  /* create a hash table for the constraint set */
3335  hashtablesize = nconss;
3336  hashtablesize = MAX(hashtablesize, HASHSIZE_ANDCONS);
3337  SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
3338  hashGetKeyAndcons, hashKeyEqAndcons, hashKeyValAndcons, (void*) scip) );
3339 
3340  *cutoff = FALSE;
3341 
3342  /* check all constraints in the given set for redundancy */
3343  for( c = 0; c < nconss; ++c )
3344  {
3345  SCIP_CONS* cons0;
3346  SCIP_CONS* cons1;
3347  SCIP_CONSDATA* consdata0;
3348 
3349  cons0 = conss[c];
3350 
3351  if( !SCIPconsIsActive(cons0) || SCIPconsIsModifiable(cons0) )
3352  continue;
3353 
3354  consdata0 = SCIPconsGetData(cons0);
3355 
3356  /* sort the constraint */
3357  consdataSort(consdata0);
3358  assert(consdata0->sorted);
3359 
3360  /* get constraint from current hash table with same variables as cons0 */
3361  cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
3362 
3363  if( cons1 != NULL )
3364  {
3365  SCIP_CONSDATA* consdata1;
3366  SCIP_Bool redundant;
3367 
3368  assert(SCIPconsIsActive(cons1));
3369  assert(!SCIPconsIsModifiable(cons1));
3370 
3371  consdata1 = SCIPconsGetData(cons1);
3372 
3373  assert(consdata1 != NULL);
3374  assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
3375 
3376  assert(consdata0->sorted && consdata1->sorted);
3377  assert(consdata0->vars[0] == consdata1->vars[0]);
3378 
3379  redundant = FALSE;
3380 
3381  if( consdata0->resvar != consdata1->resvar )
3382  {
3383  SCIP_Bool aggregated;
3384 
3385  assert(SCIPvarCompare(consdata0->resvar, consdata1->resvar) != 0);
3386 
3387  /* aggregate resultants */
3388  SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3389  cutoff, &redundant, &aggregated) );
3390  assert(redundant || SCIPdoNotAggr(scip));
3391 
3392  if( aggregated )
3393  ++(*naggrvars);
3394  if( *cutoff )
3395  goto TERMINATE;
3396  }
3397  else
3398  redundant = TRUE;
3399 
3400  /* delete consdel */
3401  if( redundant )
3402  {
3403  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
3404  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
3405 
3406  /* also take the check when upgrade flag over if necessary */
3407  consdata1->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3408  consdata1->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3409 
3410  SCIP_CALL( SCIPdelCons(scip, cons0) );
3411  (*ndelconss)++;
3412  }
3413 
3414  /* update the first changed constraint to begin the next aggregation round with */
3415  if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
3416  *firstchange = SCIPconsGetPos(cons1);
3417 
3418  assert(SCIPconsIsActive(cons1));
3419  }
3420  else
3421  {
3422  /* no such constraint in current hash table: insert cons0 into hash table */
3423  SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
3424  }
3425  }
3426  TERMINATE:
3427  /* free hash table */
3428  SCIPhashtableFree(&hashtable);
3429 
3430  return SCIP_OKAY;
3431 }
3432 
3433 /** helper function to enforce constraints */
3434 static
3436  SCIP* scip, /**< SCIP data structure */
3437  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3438  SCIP_CONS** conss, /**< constraints to process */
3439  int nconss, /**< number of constraints */
3440  SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
3441  SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
3442  )
3443 {
3444  SCIP_CONSHDLRDATA* conshdlrdata;
3445  SCIP_Bool separated;
3446  SCIP_Bool violated;
3447  SCIP_Bool cutoff;
3448  int i;
3449 
3450  separated = FALSE;
3451 
3452  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3453  assert(conshdlrdata != NULL);
3454 
3455  /* method is called only for integral solutions, because the enforcing priority is negative */
3456  for( i = 0; i < nconss; i++ )
3457  {
3458  SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, FALSE, &violated) );
3459  if( violated )
3460  {
3461  if( conshdlrdata->enforcecuts )
3462  {
3463  SCIP_Bool consseparated;
3464 
3465  SCIP_CALL( separateCons(scip, conss[i], sol, &consseparated, &cutoff) );
3466  if ( cutoff )
3467  {
3468  *result = SCIP_CUTOFF;
3469  return SCIP_OKAY;
3470  }
3471  separated = separated || consseparated;
3472 
3473  /* following assert is wrong in the case some variables were not in relaxation (dynamic columns),
3474  *
3475  * e.g. the resultant, which has a negative objective value, is in the relaxation solution on its upper bound
3476  * (variables with status loose are in an relaxation solution on it's best bound), but already creating a
3477  * row, and thereby creating the column, changes the solution value (variable than has status column, and the
3478  * initialization sets the relaxation solution value) to 0.0, and this already could lead to no violation of
3479  * the rows, which then are not seperated into the lp
3480  */
3481 #ifdef SCIP_DISABLED_CODE
3482  assert(consseparated); /* because the solution is integral, the separation always finds a cut */
3483 #endif
3484  }
3485  else
3486  {
3487  *result = SCIP_INFEASIBLE;
3488  return SCIP_OKAY;
3489  }
3490  }
3491  }
3492 
3493  if( separated )
3494  *result = SCIP_SEPARATED;
3495  else
3496  *result = SCIP_FEASIBLE;
3497 
3498  return SCIP_OKAY;
3499 }
3500 
3501 
3502 /** compares constraint with all prior constraints for possible redundancy or aggregation,
3503  * and removes or changes constraint accordingly
3504  */
3505 static
3507  SCIP* scip, /**< SCIP data structure */
3508  SCIP_CONS** conss, /**< constraint set */
3509  int firstchange, /**< first constraint that changed since last pair preprocessing round */
3510  int chkind, /**< index of constraint to check against all prior indices upto startind */
3511  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3512  int* naggrvars, /**< pointer to count number of aggregated variables */
3513  int* nbdchgs, /**< pointer to count the number of performed bound changes, or NULL */
3514  int* ndelconss /**< pointer to count number of deleted constraints */
3515  )
3516 {
3517  SCIP_CONS* cons0;
3518  SCIP_CONSDATA* consdata0;
3519  SCIP_Bool cons0changed;
3520  int c;
3521 
3522  assert(conss != NULL);
3523  assert(firstchange <= chkind);
3524  assert(cutoff != NULL);
3525  assert(naggrvars != NULL);
3526  assert(nbdchgs != NULL);
3527  assert(ndelconss != NULL);
3528 
3529  /* get the constraint to be checked against all prior constraints */
3530  cons0 = conss[chkind];
3531  assert(SCIPconsIsActive(cons0));
3532  assert(!SCIPconsIsModifiable(cons0));
3533 
3534  consdata0 = SCIPconsGetData(cons0);
3535 
3536  /* sort the constraint */
3537  consdataSort(consdata0);
3538 
3539  assert(consdata0->nvars >= 1);
3540  assert(consdata0->sorted);
3541 
3542  /* check constraint against all prior constraints */
3543  cons0changed = consdata0->changed;
3544 
3545  if( SCIPconsIsActive(cons0) )
3546  {
3547  for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff); ++c )
3548  {
3549  SCIP_CONS* cons1;
3550  SCIP_CONSDATA* consdata1;
3551  SCIP_Bool cons0superset;
3552  SCIP_Bool cons1superset;
3553  int v0;
3554  int v1;
3555 
3556  if( c % 1000 == 0 && SCIPisStopped(scip) )
3557  break;
3558 
3559  cons1 = conss[c];
3560 
3561  /* ignore inactive and modifiable constraints */
3562  if( !SCIPconsIsActive(cons1) || SCIPconsIsModifiable(cons1) )
3563  continue;
3564 
3565  consdata1 = SCIPconsGetData(cons1);
3566  assert(consdata1 != NULL);
3567 
3568 #ifdef SCIP_DISABLED_CODE
3569  SCIPdebugMsg(scip, "preprocess AND-constraint pair <%s>[chg:%d] and <%s>[chg:%d]\n",
3570  SCIPconsGetName(cons0), cons0changed, SCIPconsGetName(cons1), consdata1->changed);
3571 #endif
3572 
3573  /* if both constraints were not changed since last round, we can ignore the pair */
3574  if( !cons0changed && !consdata1->changed )
3575  continue;
3576 
3577  assert(consdata1->nvars >= 1);
3578 
3579  /* sort the constraint */
3580  consdataSort(consdata1);
3581  assert(consdata1->sorted);
3582 
3583  /* check consdata0 against consdata1:
3584  * - if they consist of the same operands, the resultants can be aggregated
3585  * - if one operand list is a subset of the other, add implication r0 = 1 -> r1 = 1, or r1 = 1 -> r0 = 1
3586  */
3587  v0 = 0;
3588  v1 = 0;
3589  cons0superset = TRUE;
3590  cons1superset = TRUE;
3591  while( (v0 < consdata0->nvars || v1 < consdata1->nvars) && (cons0superset || cons1superset) )
3592  {
3593  int varcmp;
3594 
3595  /* test, if variable appears in only one or in both constraints */
3596  if( v0 < consdata0->nvars && v1 < consdata1->nvars )
3597  varcmp = SCIPvarCompare(consdata0->vars[v0], consdata1->vars[v1]);
3598  else if( v0 < consdata0->nvars )
3599  varcmp = -1;
3600  else
3601  varcmp = +1;
3602 
3603  switch( varcmp )
3604  {
3605  case -1:
3606  /* variable doesn't appear in consdata1 */
3607  cons1superset = FALSE;
3608  v0++;
3609  break;
3610 
3611  case +1:
3612  /* variable doesn't appear in consdata0 */
3613  cons0superset = FALSE;
3614  v1++;
3615  break;
3616 
3617  case 0:
3618  /* variable appears in both constraints */
3619  v0++;
3620  v1++;
3621  break;
3622 
3623  default:
3624  SCIPerrorMessage("invalid comparison result\n");
3625  SCIPABORT();
3626  return SCIP_INVALIDDATA; /*lint !e527*/
3627  }
3628  }
3629 
3630  /* check for equivalence and domination */
3631  if( cons0superset && cons1superset )
3632  {
3633  SCIP_Bool infeasible;
3634  SCIP_Bool redundant;
3635  SCIP_Bool aggregated;
3636 
3637  /* constraints are equivalent */
3638  SCIPdebugMsg(scip, "equivalent AND-constraints <%s> and <%s>: aggregate resultants <%s> == <%s>\n",
3639  SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPvarGetName(consdata0->resvar),
3640  SCIPvarGetName(consdata1->resvar));
3641 
3642  /* aggregate resultants */
3643  SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3644  &infeasible, &redundant, &aggregated) );
3645  assert(redundant || SCIPdoNotAggr(scip));
3646 
3647  if( aggregated )
3648  {
3649  assert(redundant);
3650  (*naggrvars)++;
3651  }
3652 
3653  if( redundant )
3654  {
3655  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
3656  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
3657 
3658  /* also take the check when upgrade flag over if necessary */
3659  consdata0->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3660  consdata0->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3661 
3662  /* delete constraint */
3663  SCIP_CALL( SCIPdelCons(scip, cons1) );
3664  (*ndelconss)++;
3665  }
3666 
3667  *cutoff = *cutoff || infeasible;
3668  }
3669  else if( cons0superset )
3670  {
3671  SCIP_Bool infeasible;
3672  int nboundchgs;
3673 
3674  /* the conjunction of cons0 is a superset of the conjunction of cons1 */
3675  SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3676  SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPvarGetName(consdata0->resvar),
3677  SCIPvarGetName(consdata1->resvar));
3678 
3679  /* add implication */
3680  SCIP_CALL( SCIPaddVarImplication(scip, consdata0->resvar, TRUE, consdata1->resvar, SCIP_BOUNDTYPE_LOWER, 1.0,
3681  &infeasible, &nboundchgs) );
3682  *cutoff = *cutoff || infeasible;
3683  (*nbdchgs) += nboundchgs;
3684  }
3685  else if( cons1superset )
3686  {
3687  SCIP_Bool infeasible;
3688  int nboundchgs;
3689 
3690  /* the conjunction of cons1 is a superset of the conjunction of cons0 */
3691  SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3692  SCIPconsGetName(cons1), SCIPconsGetName(cons0), SCIPvarGetName(consdata1->resvar),
3693  SCIPvarGetName(consdata0->resvar));
3694 
3695  /* add implication */
3696  SCIP_CALL( SCIPaddVarImplication(scip, consdata1->resvar, TRUE, consdata0->resvar, SCIP_BOUNDTYPE_LOWER, 1.0,
3697  &infeasible, &nboundchgs) );
3698  *cutoff = *cutoff || infeasible;
3699  (*nbdchgs) += nboundchgs;
3700  }
3701  }
3702  }
3703  consdata0->changed = FALSE;
3704 
3705  return SCIP_OKAY;
3706 }
3707 
3708 /** tries to reformulate an expression graph node that is a product of binary variables via introducing an AND-constraint */
3709 static
3710 SCIP_DECL_EXPRGRAPHNODEREFORM(exprgraphnodeReformAnd)
3712  SCIP_EXPRGRAPHNODE* child;
3713  char name[SCIP_MAXSTRLEN];
3714  int nchildren;
3715  SCIP_CONS* cons;
3716  SCIP_VAR** vars;
3717  SCIP_VAR* var;
3718  int c;
3719 
3720  assert(scip != NULL);
3721  assert(exprgraph != NULL);
3722  assert(node != NULL);
3723  assert(naddcons != NULL);
3724  assert(reformnode != NULL);
3725 
3726  *reformnode = NULL;
3727 
3728  /* allow only products given as EXPR_PRODUCT or EXPR_POLYNOMIAL with only 1 monomial */
3731  )
3732  return SCIP_OKAY;
3733 
3734  nchildren = SCIPexprgraphGetNodeNChildren(node);
3735 
3736  /* for a polynomial with only one monomial, all children should appear as factors in the monomial
3737  * since we assume that the factors have been merged, this means that the number of factors in the monomial should equal the number of children of the node
3738  */
3740 
3741  /* check only products with at least 3 variables (2 variables are taken of by cons_quadratic) */
3742  if( nchildren <= 2 )
3743  return SCIP_OKAY;
3744 
3745  /* check if all factors correspond to binary variables, and if so, setup vars array */
3746  for( c = 0; c < nchildren; ++c )
3747  {
3748  child = SCIPexprgraphGetNodeChildren(node)[c];
3749 
3751  return SCIP_OKAY;
3752 
3753  var = (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, child);
3754  if( !SCIPvarIsBinary(var) )
3755  return SCIP_OKAY;
3756  }
3757 
3758  /* node corresponds to product of binary variables (maybe with coefficient and constant, if polynomial) */
3759  SCIPdebugMsg(scip, "reformulate node %p via AND-constraint\n", (void*)node);
3760 
3761  /* collect variables in product */
3762  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nchildren) );
3763  for( c = 0; c < nchildren; ++c )
3764  {
3765  child = SCIPexprgraphGetNodeChildren(node)[c];
3766  vars[c] = (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, child);
3767  }
3768 
3769  /* create variable for resultant
3770  * cons_and wants to add implications for resultant, which is only possible for binary variables currently
3771  * so choose binary as vartype, even though implicit integer had been sufficient
3772  */
3773  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "nlreform%dand", *naddcons);
3774  SCIP_CALL( SCIPcreateVar(scip, &var, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
3775  TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) );
3776  SCIP_CALL( SCIPaddVar(scip, var) );
3777 
3778 #ifdef WITH_DEBUG_SOLUTION
3779  if( SCIPdebugIsMainscip(scip) )
3780  {
3781  SCIP_Bool debugval;
3782  SCIP_Real varval;
3783 
3784  debugval = TRUE;
3785  for( c = 0; c < nchildren; ++c )
3786  {
3787  SCIP_CALL( SCIPdebugGetSolVal(scip, vars[c], &varval) );
3788  debugval = debugval && (varval > 0.5);
3789  }
3790  SCIP_CALL( SCIPdebugAddSolVal(scip, var, debugval ? 1.0 : 0.0) );
3791  }
3792 #endif
3793 
3794  /* create AND-constraint */
3795  SCIP_CALL( SCIPcreateConsAnd(scip, &cons, name, var, nchildren, vars,
3796  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
3797  SCIP_CALL( SCIPaddCons(scip, cons) );
3798  SCIPdebugPrintCons(scip, cons, NULL);
3799  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3800  ++*naddcons;
3801 
3802  SCIPfreeBufferArray(scip, &vars);
3803 
3804  /* add var to exprgraph */
3805  SCIP_CALL( SCIPexprgraphAddVars(exprgraph, 1, (void**)&var, reformnode) );
3806  SCIP_CALL( SCIPreleaseVar(scip, &var) );
3807 
3808  /* if we have coefficient and constant, then replace reformnode by linear expression in reformnode */
3810  {
3811  SCIP_Real coef;
3812  SCIP_Real constant;
3813 
3815  constant = SCIPexprgraphGetNodePolynomialConstant(node);
3816 
3817  if( coef != 1.0 || constant != 0.0 )
3818  {
3819  SCIP_EXPRGRAPHNODE* linnode;
3820  SCIP_CALL( SCIPexprgraphCreateNodeLinear(SCIPblkmem(scip), &linnode, 1, &coef, constant) );
3821  SCIP_CALL( SCIPexprgraphAddNode(exprgraph, linnode, -1, 1, reformnode) );
3822  *reformnode = linnode;
3823  }
3824  }
3825 
3826  return SCIP_OKAY;
3827 }
3828 
3829 /*
3830  * Callback methods of constraint handler
3831  */
3832 
3833 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
3834 static
3835 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyAnd)
3836 { /*lint --e{715}*/
3837  assert(scip != NULL);
3838  assert(conshdlr != NULL);
3839  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3840 
3841  /* call inclusion method of constraint handler */
3843 
3844  *valid = TRUE;
3845 
3846  return SCIP_OKAY;
3847 }
3848 
3849 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
3850 static
3851 SCIP_DECL_CONSFREE(consFreeAnd)
3852 { /*lint --e{715}*/
3853  SCIP_CONSHDLRDATA* conshdlrdata;
3854 
3855  /* free constraint handler data */
3856  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3857  assert(conshdlrdata != NULL);
3858 
3859  SCIP_CALL( conshdlrdataFree(scip, &conshdlrdata) );
3860 
3861  SCIPconshdlrSetData(conshdlr, NULL);
3862 
3863  return SCIP_OKAY;
3864 }
3865 
3866 
3867 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
3868 static
3869 SCIP_DECL_CONSINITPRE(consInitpreAnd)
3870 { /*lint --e{715}*/
3871  SCIP_CONSHDLRDATA* conshdlrdata;
3872 
3873  assert( scip != NULL );
3874  assert( conshdlr != NULL );
3875  assert( nconss == 0 || conss != NULL );
3876 
3877  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3878  assert(conshdlrdata != NULL);
3879 
3880  if( conshdlrdata->linearize )
3881  {
3882  /* linearize all AND-constraints and remove the AND-constraints */
3883  SCIP_CONS* newcons;
3884  SCIP_CONS* cons;
3885  SCIP_CONSDATA* consdata;
3886  char consname[SCIP_MAXSTRLEN];
3887 
3888  SCIP_VAR** vars;
3889  SCIP_Real* vals;
3890 
3891  int nvars;
3892  int c, v;
3893 
3894  /* allocate buffer array */
3895  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
3896  SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
3897 
3898  for( c = 0; c < nconss; ++c )
3899  {
3900  cons = conss[c];
3901  assert( cons != NULL );
3902 
3903  /* only added constraints can be upgraded */
3904  if( !SCIPconsIsAdded(cons) )
3905  continue;
3906 
3907  consdata = SCIPconsGetData(cons);
3908  assert( consdata != NULL );
3909  assert( consdata->resvar != NULL );
3910 
3911  nvars = consdata->nvars;
3912 
3913  if( !conshdlrdata->aggrlinearization )
3914  {
3915  vars[0] = consdata->resvar;
3916  vals[0] = 1.0;
3917  vals[1] = -1.0;
3918 
3919  /* create operator linear constraints */
3920  for( v = 0; v < nvars; ++v )
3921  {
3922  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), v);
3923  vars[1] = consdata->vars[v];
3924 
3925  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, vars, vals, -SCIPinfinity(scip), 0.0,
3927  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3929  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3930 
3931 
3932  /* add constraint */
3933  SCIP_CALL( SCIPaddCons(scip, newcons) );
3934  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3935  }
3936  }
3937 
3938  /* reallocate buffer array */
3939  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, nvars + 1) );
3940  SCIP_CALL( SCIPreallocBufferArray(scip, &vals, nvars + 1) );
3941 
3942  for( v = 0; v < nvars; ++v )
3943  {
3944  vars[v] = consdata->vars[v];
3945  vals[v] = -1.0;
3946  }
3947 
3948  vars[nvars] = consdata->resvar;
3949 
3950  if( conshdlrdata->aggrlinearization )
3951  {
3952  /* create additional linear constraint */
3953  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_operators", SCIPconsGetName(cons));
3954 
3955  vals[nvars] = (SCIP_Real) nvars;
3956 
3957  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -SCIPinfinity(scip), 0.0,
3959  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3961  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3962 
3963  /* add constraint */
3964  SCIP_CALL( SCIPaddCons(scip, newcons) );
3965  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3966  }
3967 
3968  /* create additional linear constraint */
3969  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_add", SCIPconsGetName(cons));
3970 
3971  vals[nvars] = 1.0;
3972 
3973  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -nvars + 1.0, SCIPinfinity(scip),
3975  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3977  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3978 
3979  /* add constraint */
3980  SCIP_CALL( SCIPaddCons(scip, newcons) );
3981  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3982 
3983  /* delete constraint */
3984  SCIP_CALL( SCIPdelCons(scip, cons) );
3985  }
3986 
3987  /* free buffer array */
3988  SCIPfreeBufferArray(scip, &vars);
3989  SCIPfreeBufferArray(scip, &vals);
3990  }
3991 
3992  return SCIP_OKAY;
3993 }
3994 
3995 
3996 #ifdef GMLGATEPRINTING
3997 
3998 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
3999 static
4000 SCIP_DECL_CONSEXITPRE(consExitpreAnd)
4001 { /*lint --e{715}*/
4002  SCIP_HASHMAP* hashmap;
4003  FILE* gmlfile;
4004  char fname[SCIP_MAXSTRLEN];
4005  SCIP_CONS* cons;
4006  SCIP_CONSDATA* consdata;
4007  SCIP_VAR** activeconsvars;
4008  SCIP_VAR* activevar;
4009  int* varnodeids;
4010  SCIP_VAR** vars;
4011  int nvars;
4012  int nbinvars;
4013  int nintvars;
4014  int nimplvars;
4015  int ncontvars;
4016  int v;
4017  int c;
4018  unsigned int resid;
4019  unsigned int varid;
4020  unsigned int id = 1;
4021 
4022  /* no AND-constraints available */
4023  if( nconss == 0 )
4024  return SCIP_OKAY;
4025 
4026  nvars = SCIPgetNVars(scip);
4027 
4028  /* no variables left anymore */
4029  if( nvars == 0 )
4030  return SCIP_OKAY;
4031 
4032  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4033  SCIP_CALL( SCIPallocBufferArray(scip, &varnodeids, nvars) );
4034  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, &nimplvars, &ncontvars) );
4035 
4036  /* open gml file */
4037  (void) SCIPsnprintf(fname, SCIP_MAXSTRLEN, "and-gates%p.gml", scip);
4038  gmlfile = fopen(fname, "w");
4039 
4040  if( gmlfile == NULL )
4041  {
4042  SCIPerrorMessage("cannot open graph file <%s>\n", fname);
4043  SCIPABORT();
4044  return SCIP_WRITEERROR; /*lint !e527*/
4045  }
4046 
4047  /* create the variable mapping hash map */
4048  SCIP_CALL_FINALLY( SCIPhashmapCreate(&hashmap, SCIPblkmem(scip), nvars), fclose(gmlfile) );
4049 
4050  /* write starting of gml file */
4051  SCIPgmlWriteOpening(gmlfile, TRUE);
4052 
4053  /* walk over all AND-constraints */
4054  for( c = nconss - 1; c >= 0; --c )
4055  {
4056  cons = conss[c];
4057 
4058  /* only handle active constraints */
4059  if( !SCIPconsIsActive(cons) )
4060  continue;
4061 
4062  consdata = SCIPconsGetData(cons);
4063  assert(consdata != NULL);
4064 
4065  /* only handle constraints which have operands */
4066  if( consdata->nvars == 0 )
4067  continue;
4068 
4069  assert(consdata->vars != NULL);
4070  assert(consdata->resvar != NULL);
4071 
4072  /* get active variable of resultant */
4073  activevar = SCIPvarGetProbvar(consdata->resvar);
4074 
4075  /* check if we already found this variables */
4076  resid = (unsigned int)(size_t) SCIPhashmapGetImage(hashmap, activevar);
4077  if( resid == 0 )
4078  {
4079  resid = id;
4080  ++id;
4081  SCIP_CALL( SCIPhashmapInsert(hashmap, (void*)activevar, (void*)(size_t)resid) );
4082 
4083  /* write new gml node for new resultant */
4084  SCIPgmlWriteNode(gmlfile, resid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4085  }
4086 
4087  /* copy operands to get problem variables for */
4088  SCIP_CALL( SCIPduplicateBufferArray(scip, &activeconsvars, consdata->vars, consdata->nvars) );
4089 
4090  /* get problem variables of operands */
4091  SCIPvarsGetProbvar(activeconsvars, consdata->nvars);
4092 
4093  for( v = consdata->nvars - 1; v >= 0; --v )
4094  {
4095  /* check if we already found this variables */
4096  varid = (unsigned int)(size_t) SCIPhashmapGetImage(hashmap, activeconsvars[v]);
4097  if( varid == 0 )
4098  {
4099  varid = id;
4100  ++id;
4101  SCIP_CALL( SCIPhashmapInsert(hashmap, (void*)activeconsvars[v], (void*)(size_t)varid) );
4102 
4103  /* write new gml node for new operand */
4104  SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activeconsvars[v]), NULL, NULL, NULL);
4105  }
4106  /* write gml arc between resultant and operand */
4107  SCIPgmlWriteArc(gmlfile, resid, varid, NULL, NULL);
4108  }
4109 
4110  /* free temporary memory for active constraint variables */
4111  SCIPfreeBufferArray(scip, &activeconsvars);
4112  }
4113 
4114  /* write all remaining variables as nodes */
4115 #ifdef SCIP_DISABLED_CODE
4116  for( v = nvars - 1; v >= 0; --v )
4117  {
4118  activevar = SCIPvarGetProbvar(vars[v]);
4119 
4120  varid = (unsigned int)(size_t) SCIPhashmapGetImage(hashmap, activevar);
4121  if( varid == 0 )
4122  {
4123  varid = id;
4124  ++id;
4125  SCIP_CALL( SCIPhashmapInsert(hashmap, (void*)activeconsvars[v], (void*)(size_t)varid) );
4126 
4127  /* write new gml node for new operand */
4128  SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4129  }
4130  }
4131 #endif
4132 
4133  /* free the variable mapping hash map */
4134  SCIPhashmapFree(&hashmap);
4135 
4136  SCIPgmlWriteClosing(gmlfile);
4137 
4138  fclose(gmlfile);
4139 
4140  SCIPfreeBufferArray(scip, &varnodeids);
4141  SCIPfreeBufferArray(scip, &vars);
4142 
4143  return SCIP_OKAY;
4144 }
4145 #endif
4146 
4147 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4148 static
4149 SCIP_DECL_CONSEXITSOL(consExitsolAnd)
4150 { /*lint --e{715}*/
4151  SCIP_CONSDATA* consdata;
4152  int c;
4153 
4154  /* release and free the rows of all constraints */
4155  for( c = 0; c < nconss; ++c )
4156  {
4157  consdata = SCIPconsGetData(conss[c]);
4158  assert(consdata != NULL);
4159 
4160  SCIP_CALL( consdataFreeRows(scip, consdata) );
4161  }
4162 
4163  return SCIP_OKAY;
4164 }
4165 
4166 
4167 /** frees specific constraint data */
4168 static
4169 SCIP_DECL_CONSDELETE(consDeleteAnd)
4170 { /*lint --e{715}*/
4171  SCIP_CONSHDLRDATA* conshdlrdata;
4172 
4173  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4174  assert(conshdlrdata != NULL);
4175 
4176  SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4177 
4178  return SCIP_OKAY;
4179 }
4180 
4181 
4182 /** transforms constraint data into data belonging to the transformed problem */
4183 static
4184 SCIP_DECL_CONSTRANS(consTransAnd)
4185 { /*lint --e{715}*/
4186  SCIP_CONSHDLRDATA* conshdlrdata;
4187  SCIP_CONSDATA* sourcedata;
4188  SCIP_CONSDATA* targetdata;
4189 
4190  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4191  assert(conshdlrdata != NULL);
4192 
4193  sourcedata = SCIPconsGetData(sourcecons);
4194  assert(sourcedata != NULL);
4195 
4196  /* create target constraint data */
4197  SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr,
4198  sourcedata->nvars, sourcedata->vars, sourcedata->resvar, sourcedata->checkwhenupgr,
4199  sourcedata->notremovablewhenupgr) );
4200 
4201  /* create target constraint */
4202  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4203  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4204  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4205  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4206  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4207 
4208  return SCIP_OKAY;
4209 }
4210 
4211 
4212 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4213 static
4214 SCIP_DECL_CONSINITLP(consInitlpAnd)
4215 { /*lint --e{715}*/
4216  int i;
4217 
4218  *infeasible = FALSE;
4219 
4220  for( i = 0; i < nconss && !(*infeasible); i++ )
4221  {
4222  assert(SCIPconsIsInitial(conss[i]));
4223  SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4224  }
4225 
4226  return SCIP_OKAY;
4227 }
4228 
4229 
4230 /** separation method of constraint handler for LP solutions */
4231 static
4232 SCIP_DECL_CONSSEPALP(consSepalpAnd)
4233 { /*lint --e{715}*/
4234  SCIP_Bool separated;
4235  SCIP_Bool cutoff;
4236  int c;
4237 
4238  *result = SCIP_DIDNOTFIND;
4239 
4240  /* separate all useful constraints */
4241  for( c = 0; c < nusefulconss; ++c )
4242  {
4243  SCIP_CALL( separateCons(scip, conss[c], NULL, &separated, &cutoff) );
4244  if ( cutoff )
4245  *result = SCIP_CUTOFF;
4246  else if ( separated )
4247  *result = SCIP_SEPARATED;
4248  }
4249 
4250  /* combine constraints to get more cuts */
4251  /**@todo combine constraints to get further cuts */
4252 
4253  return SCIP_OKAY;
4254 }
4255 
4256 
4257 /** separation method of constraint handler for arbitrary primal solutions */
4258 static
4259 SCIP_DECL_CONSSEPASOL(consSepasolAnd)
4260 { /*lint --e{715}*/
4261  SCIP_Bool separated;
4262  SCIP_Bool cutoff;
4263  int c;
4264 
4265  *result = SCIP_DIDNOTFIND;
4266 
4267  /* separate all useful constraints */
4268  for( c = 0; c < nusefulconss; ++c )
4269  {
4270  SCIP_CALL( separateCons(scip, conss[c], sol, &separated, &cutoff) );
4271  if ( cutoff )
4272  *result = SCIP_CUTOFF;
4273  else if ( separated )
4274  *result = SCIP_SEPARATED;
4275  }
4276 
4277  /* combine constraints to get more cuts */
4278  /**@todo combine constraints to get further cuts */
4279 
4280  return SCIP_OKAY;
4281 }
4282 
4283 
4284 /** constraint enforcing method of constraint handler for LP solutions */
4285 static
4286 SCIP_DECL_CONSENFOLP(consEnfolpAnd)
4287 { /*lint --e{715}*/
4288  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) );
4289 
4290  return SCIP_OKAY;
4291 }
4292 
4293 /** constraint enforcing method of constraint handler for relaxation solutions */
4294 static
4295 SCIP_DECL_CONSENFORELAX(consEnforelaxAnd)
4296 { /*lint --e{715}*/
4297  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) );
4298 
4299  return SCIP_OKAY;
4300 }
4301 
4302 /** constraint enforcing method of constraint handler for pseudo solutions */
4303 static
4304 SCIP_DECL_CONSENFOPS(consEnfopsAnd)
4305 { /*lint --e{715}*/
4306  SCIP_Bool violated;
4307  int i;
4308 
4309  /* method is called only for integral solutions, because the enforcing priority is negative */
4310  for( i = 0; i < nconss; i++ )
4311  {
4312  SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
4313  if( violated )
4314  {
4315  *result = SCIP_INFEASIBLE;
4316  return SCIP_OKAY;
4317  }
4318  }
4319  *result = SCIP_FEASIBLE;
4320 
4321  return SCIP_OKAY;
4322 }
4323 
4324 
4325 /** feasibility check method of constraint handler for integral solutions */
4326 static
4327 SCIP_DECL_CONSCHECK(consCheckAnd)
4328 { /*lint --e{715}*/
4329  SCIP_Bool violated;
4330  int i;
4331 
4332  *result = SCIP_FEASIBLE;
4333 
4334  /* method is called only for integral solutions, because the enforcing priority is negative */
4335  for( i = 0; i < nconss && (*result == SCIP_FEASIBLE || completely); i++ )
4336  {
4337  SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, printreason, &violated) );
4338  if( violated )
4339  *result = SCIP_INFEASIBLE;
4340  }
4341 
4342  return SCIP_OKAY;
4343 }
4344 
4345 
4346 /** domain propagation method of constraint handler */
4347 static
4348 SCIP_DECL_CONSPROP(consPropAnd)
4349 { /*lint --e{715}*/
4350  SCIP_CONSHDLRDATA* conshdlrdata;
4351  SCIP_Bool cutoff;
4352  int nfixedvars;
4353  int nupgdconss;
4354  int c;
4355 
4356  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4357  assert(conshdlrdata != NULL);
4358 
4359  cutoff = FALSE;
4360  nfixedvars = 0;
4361  nupgdconss = 0;
4362 
4363  /* propagate all useful constraints */
4364  for( c = 0; c < nusefulconss && !cutoff; ++c )
4365  {
4366  SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars, &nupgdconss) );
4367  }
4368 
4369  /* return the correct result */
4370  if( cutoff )
4371  *result = SCIP_CUTOFF;
4372  else if( nfixedvars > 0 || nupgdconss > 0 )
4373  *result = SCIP_REDUCEDDOM;
4374  else
4375  *result = SCIP_DIDNOTFIND;
4376 
4377  return SCIP_OKAY;
4378 }
4379 
4380 
4381 /** presolving method of constraint handler */
4382 static
4383 SCIP_DECL_CONSPRESOL(consPresolAnd)
4384 { /*lint --e{715}*/
4385  SCIP_CONSHDLRDATA* conshdlrdata;
4386  SCIP_CONS* cons;
4387  SCIP_CONSDATA* consdata;
4388  unsigned char* entries;
4389  SCIP_Bool cutoff;
4390  int oldnfixedvars;
4391  int oldnaggrvars;
4392  int oldnchgbds;
4393  int oldndelconss;
4394  int oldnupgdconss;
4395  int firstchange;
4396  int nentries;
4397  int c;
4398 
4399  assert(result != NULL);
4400 
4401  oldnfixedvars = *nfixedvars;
4402  oldnaggrvars = *naggrvars;
4403  oldnchgbds = *nchgbds;
4404  oldndelconss = *ndelconss;
4405  oldnupgdconss = *nupgdconss;
4406 
4407  nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
4408  SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
4409 
4410  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4411  assert(conshdlrdata != NULL);
4412 
4413  /* process constraints */
4414  cutoff = FALSE;
4415  firstchange = INT_MAX;
4416  for( c = 0; c < nconss && !cutoff && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
4417  {
4418  cons = conss[c];
4419  assert(cons != NULL);
4420  consdata = SCIPconsGetData(cons);
4421  assert(consdata != NULL);
4422 
4423  /* force presolving the constraint in the initial round */
4424  if( nrounds == 0 )
4425  consdata->propagated = FALSE;
4426 
4427  /* remember the first changed constraint to begin the next aggregation round with */
4428  if( firstchange == INT_MAX && consdata->changed )
4429  firstchange = c;
4430 
4431  /* propagate constraint */
4432  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nupgdconss) );
4433 
4434  /* remove all variables that are fixed to one; merge multiple entries of the same variable;
4435  * fix resultant to zero if a pair of negated variables is contained in the operand variables
4436  */
4437  if( !cutoff && !SCIPconsIsDeleted(cons) )
4438  {
4439  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs) );
4440 
4441  /* merge multiple occurances of variables or variables with their negated variables */
4442  SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, nfixedvars, nchgcoefs, ndelconss) );
4443  }
4444 
4445  if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
4446  {
4447  assert(consdata->nvars >= 1); /* otherwise, propagateCons() has deleted the constraint */
4448 
4449  /* if only one variable is left, the resultant has to be equal to this single variable */
4450  if( consdata->nvars == 1 )
4451  {
4452  SCIP_Bool redundant;
4453  SCIP_Bool aggregated;
4454 
4455  SCIPdebugMsg(scip, "AND-constraint <%s> has only one variable not fixed to 1.0\n", SCIPconsGetName(cons));
4456 
4457  assert(consdata->vars != NULL);
4458  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
4459  assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
4460 
4461  /* aggregate variables: resultant - operand == 0 */
4462  SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
4463  &cutoff, &redundant, &aggregated) );
4464  assert(redundant || SCIPdoNotAggr(scip));
4465 
4466  if( aggregated )
4467  {
4468  assert(redundant);
4469  (*naggrvars)++;
4470  }
4471 
4472  if( redundant )
4473  {
4474  /* delete constraint */
4475  SCIP_CALL( SCIPdelCons(scip, cons) );
4476  (*ndelconss)++;
4477  }
4478  }
4479  else if( !consdata->impladded )
4480  {
4481  int i;
4482 
4483  /* add implications: resultant == 1 -> all operands == 1 */
4484  for( i = 0; i < consdata->nvars && !cutoff; ++i )
4485  {
4486  int nimplbdchgs;
4487 
4488  SCIP_CALL( SCIPaddVarImplication(scip, consdata->resvar, TRUE, consdata->vars[i],
4489  SCIP_BOUNDTYPE_LOWER, 1.0, &cutoff, &nimplbdchgs) );
4490  (*nchgbds) += nimplbdchgs;
4491  }
4492  consdata->impladded = TRUE;
4493  }
4494 
4495  /* if in r = x and y, the resultant is fixed to zero, add implication x = 1 -> y = 0 */
4496  if( !cutoff && SCIPconsIsActive(cons) && consdata->nvars == 2 && !consdata->opimpladded
4497  && SCIPvarGetUbGlobal(consdata->resvar) < 0.5 )
4498  {
4499  int nimplbdchgs;
4500 
4501  SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], TRUE, consdata->vars[1],
4502  SCIP_BOUNDTYPE_UPPER, 0.0, &cutoff, &nimplbdchgs) );
4503  (*nchgbds) += nimplbdchgs;
4504  consdata->opimpladded = TRUE;
4505  }
4506  }
4507  }
4508 
4509  /* perform dual presolving on AND-constraints */
4510  if( conshdlrdata->dualpresolving && !cutoff && !SCIPisStopped(scip) && SCIPallowDualReds(scip))
4511  {
4512  SCIP_CALL( dualPresolve(scip, conss, nconss, conshdlrdata->eventhdlr, &entries, &nentries, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, nupgdconss, naddconss) );
4513  }
4514 
4515  /* check for cliques inside the AND constraint */
4516  if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4517  {
4518  for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4519  {
4520  if( SCIPconsIsActive(conss[c]) )
4521  {
4522  /* check if at least two operands are in one clique */
4523  SCIP_CALL( cliquePresolve(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, naddconss) );
4524  }
4525  }
4526  }
4527 
4528  /* process pairs of constraints: check them for equal operands in order to aggregate resultants;
4529  * only apply this expensive procedure, if the single constraint preprocessing did not find any reductions
4530  * (otherwise, we delay the presolving to be called again next time)
4531  */
4532  if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4533  {
4534  if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4535  {
4536  if( firstchange < nconss )
4537  {
4538  /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
4539  SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, &cutoff, naggrvars, ndelconss) );
4540  oldnaggrvars = *naggrvars;
4541  }
4542  }
4543  }
4544 
4545  if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4546  {
4547  if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4548  {
4549  SCIP_Longint npaircomparisons;
4550  npaircomparisons = 0;
4551  oldndelconss = *ndelconss;
4552 
4553  for( c = firstchange; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4554  {
4555  if( SCIPconsIsActive(conss[c]) && !SCIPconsIsModifiable(conss[c]) )
4556  {
4557  npaircomparisons += ((SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange));
4558 
4559  SCIP_CALL( preprocessConstraintPairs(scip, conss, firstchange, c, &cutoff, naggrvars, nchgbds,
4560  ndelconss) );
4561 
4562  if( npaircomparisons > NMINCOMPARISONS )
4563  {
4564  if( ((*ndelconss - oldndelconss) + (*naggrvars - oldnaggrvars) + (*nchgbds - oldnchgbds)/2.0) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
4565  break;
4566  oldndelconss = *ndelconss;
4567  oldnaggrvars = *naggrvars;
4568  oldnchgbds = *nchgbds;
4569 
4570  npaircomparisons = 0;
4571  }
4572  }
4573  }
4574  }
4575  }
4576 
4577  SCIPfreeBufferArray(scip, &entries);
4578 
4579  /* return the correct result code */
4580  if( cutoff )
4581  *result = SCIP_CUTOFF;
4582  else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds
4583  || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4584  *result = SCIP_SUCCESS;
4585  else
4586  *result = SCIP_DIDNOTFIND;
4587 
4588  return SCIP_OKAY;
4589 }
4590 
4591 
4592 /** propagation conflict resolving method of constraint handler */
4593 static
4594 SCIP_DECL_CONSRESPROP(consRespropAnd)
4595 { /*lint --e{715}*/
4596  SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
4597 
4598  return SCIP_OKAY;
4599 }
4600 
4601 
4602 /** variable rounding lock method of constraint handler */
4603 static
4604 SCIP_DECL_CONSLOCK(consLockAnd)
4605 { /*lint --e{715}*/
4606  SCIP_CONSDATA* consdata;
4607  int i;
4608 
4609  consdata = SCIPconsGetData(cons);
4610  assert(consdata != NULL);
4611 
4612  /* resultant variable */
4613  SCIP_CALL( SCIPaddVarLocks(scip, consdata->resvar, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4614 
4615  /* operand variables */
4616  for( i = 0; i < consdata->nvars; ++i )
4617  {
4618  SCIP_CALL( SCIPaddVarLocks(scip, consdata->vars[i], nlockspos + nlocksneg, nlockspos + nlocksneg) );
4619  }
4620 
4621  return SCIP_OKAY;
4622 }
4623 
4624 
4625 /** constraint display method of constraint handler */
4626 static
4627 SCIP_DECL_CONSPRINT(consPrintAnd)
4628 { /*lint --e{715}*/
4629 
4630  assert( scip != NULL );
4631  assert( conshdlr != NULL );
4632  assert( cons != NULL );
4633 
4634  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file) );
4635 
4636  return SCIP_OKAY;
4637 }
4638 
4639 /** constraint copying method of constraint handler */
4640 static
4641 SCIP_DECL_CONSCOPY(consCopyAnd)
4642 { /*lint --e{715}*/
4643  SCIP_VAR** sourcevars;
4644  SCIP_VAR** vars;
4645  SCIP_VAR* sourceresvar;
4646  SCIP_VAR* resvar;
4647  const char* consname;
4648  int nvars;
4649  int v;
4650 
4651  assert(valid != NULL);
4652  (*valid) = TRUE;
4653 
4654  sourceresvar = SCIPgetResultantAnd(sourcescip, sourcecons);
4655 
4656  /* map resultant to active variable of the target SCIP */
4657  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceresvar, &resvar, varmap, consmap, global, valid) );
4658  assert(!(*valid) || resvar != NULL);
4659 
4660  /* we do not copy, if a variable is missing */
4661  if( !(*valid) )
4662  return SCIP_OKAY;
4663 
4664  /* map operand variables to active variables of the target SCIP */
4665  sourcevars = SCIPgetVarsAnd(sourcescip, sourcecons);
4666  nvars = SCIPgetNVarsAnd(sourcescip, sourcecons);
4667 
4668  if( nvars == -1 )
4669  return SCIP_INVALIDCALL;
4670 
4671  /* allocate buffer array */
4672  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4673 
4674  for( v = 0; v < nvars; ++v )
4675  {
4676  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
4677  assert(!(*valid) || vars[v] != NULL);
4678 
4679  /* we do not copy, if a variable is missing */
4680  if( !(*valid) )
4681  goto TERMINATE;
4682  }
4683 
4684  if( name != NULL )
4685  consname = name;
4686  else
4687  consname = SCIPconsGetName(sourcecons);
4688 
4689  /* creates and captures a AND-constraint */
4690  SCIP_CALL( SCIPcreateConsAnd(scip, cons, consname, resvar, nvars, vars,
4691  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4692 
4693  TERMINATE:
4694  /* free buffer array */
4695  SCIPfreeBufferArray(scip, &vars);
4696 
4697  return SCIP_OKAY;
4698 }
4699 
4700 /** constraint parsing method of constraint handler */
4701 static
4702 SCIP_DECL_CONSPARSE(consParseAnd)
4703 { /*lint --e{715}*/
4704  SCIP_VAR** vars;
4705  SCIP_VAR* resvar;
4706  char* endptr;
4707  int requiredsize;
4708  int varssize;
4709  int nvars;
4710 
4711  SCIPdebugMsg(scip, "parse <%s> as AND-constraint\n", str);
4712 
4713  *success = FALSE;
4714 
4715  /* parse variable name of resultant */
4716  SCIP_CALL( SCIPparseVarName(scip, str, &resvar, &endptr) );
4717  str = endptr;
4718 
4719  if( resvar == NULL )
4720  {
4721  SCIPdebugMsg(scip, "resultant variable does not exist \n");
4722  }
4723  else
4724  {
4725  char* strcopy = NULL;
4726  char* startptr;
4727 
4728  /* cutoff "== and(" form the constraint string */
4729  startptr = strchr((char*)str, '(');
4730 
4731  if( startptr == NULL )
4732  {
4733  SCIPerrorMessage("missing starting character '(' parsing AND-constraint\n");
4734  return SCIP_OKAY;
4735  }
4736 
4737  /* skip '(' */
4738  ++startptr;
4739 
4740  /* find end character ')' */
4741  endptr = strrchr(startptr, ')');
4742 
4743  if( endptr == NULL )
4744  {
4745  SCIPerrorMessage("missing ending character ')' parsing AND-constraint\n");
4746  return SCIP_OKAY;
4747  }
4748  assert(endptr >= startptr);
4749 
4750  if( endptr > startptr )
4751  {
4752  /* copy string for parsing */
4753  SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, startptr, (int)(endptr-startptr)) );
4754 
4755  varssize = 100;
4756  nvars = 0;
4757 
4758  /* allocate buffer array for variables */
4759  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
4760 
4761  /* parse string */
4762  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4763 
4764  if( *success )
4765  {
4766  /* check if the size of the variable array was great enough */
4767  if( varssize < requiredsize )
4768  {
4769  /* reallocate memory */
4770  varssize = requiredsize;
4771  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
4772 
4773  /* parse string again with the correct size of the variable array */
4774  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4775  }
4776 
4777  assert(*success);
4778  assert(varssize >= requiredsize);
4779 
4780  /* create AND-constraint */
4781  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
4782  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4783  }
4784 
4785  /* free variable buffer */
4786  SCIPfreeBufferArray(scip, &vars);
4787  SCIPfreeBufferArray(scip, &strcopy);
4788  }
4789  else
4790  {
4791  if( !modifiable )
4792  {
4793  SCIPerrorMessage("cannot create empty AND-constraint\n");
4794  return SCIP_OKAY;
4795  }
4796 
4797  /* create empty AND-constraint */
4798  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, 0, NULL,
4799  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4800 
4801  *success = TRUE;
4802  }
4803  }
4804 
4805  return SCIP_OKAY;
4806 }
4807 
4808 /** constraint method of constraint handler which returns the variables (if possible) */
4809 static
4810 SCIP_DECL_CONSGETVARS(consGetVarsAnd)
4811 { /*lint --e{715}*/
4812  SCIP_CONSDATA* consdata;
4813 
4814  consdata = SCIPconsGetData(cons);
4815  assert(consdata != NULL);
4816 
4817  if( varssize < consdata->nvars + 1 )
4818  (*success) = FALSE;
4819  else
4820  {
4821  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
4822  vars[consdata->nvars] = consdata->resvar;
4823  (*success) = TRUE;
4824  }
4825 
4826  return SCIP_OKAY;
4827 }
4828 
4829 /** constraint method of constraint handler which returns the number of variable (if possible) */
4830 static
4831 SCIP_DECL_CONSGETNVARS(consGetNVarsAnd)
4832 { /*lint --e{715}*/
4833  SCIP_CONSDATA* consdata;
4834 
4835  assert(cons != NULL);
4836 
4837  consdata = SCIPconsGetData(cons);
4838  assert(consdata != NULL);
4839 
4840  (*nvars) = consdata->nvars + 1;
4841  (*success) = TRUE;
4842 
4843  return SCIP_OKAY;
4844 }
4845 
4846 
4847 /*
4848  * Callback methods of event handler
4849  */
4850 
4851 static
4852 SCIP_DECL_EVENTEXEC(eventExecAnd)
4853 { /*lint --e{715}*/
4854  SCIP_CONSDATA* consdata;
4855 
4856  assert(eventhdlr != NULL);
4857  assert(eventdata != NULL);
4858  assert(event != NULL);
4859 
4860  consdata = (SCIP_CONSDATA*)eventdata;
4861  assert(consdata != NULL);
4862 
4863  /* check, if the variable was fixed to zero */
4865  consdata->nofixedzero = FALSE;
4866 
4867  consdata->propagated = FALSE;
4868 
4869  return SCIP_OKAY;
4870 }
4871 
4872 
4873 /*
4874  * constraint specific interface methods
4875  */
4876 
4877 /** creates the handler for AND-constraints and includes it in SCIP */
4879  SCIP* scip /**< SCIP data structure */
4880  )
4881 {
4882  SCIP_CONSHDLRDATA* conshdlrdata;
4883  SCIP_CONSHDLR* conshdlr;
4884  SCIP_EVENTHDLR* eventhdlr;
4885 
4886  /* create event handler for events on variables */
4888  eventExecAnd, NULL) );
4889 
4890  /* create constraint handler data */
4891  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
4892 
4893  /* include constraint handler */
4896  consEnfolpAnd, consEnfopsAnd, consCheckAnd, consLockAnd,
4897  conshdlrdata) );
4898 
4899  assert(conshdlr != NULL);
4900 
4901  /* set non-fundamental callbacks via specific setter functions */
4902  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyAnd, consCopyAnd) );
4903  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteAnd) );
4904 #ifdef GMLGATEPRINTING
4905  SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreAnd) );
4906 #endif
4907  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolAnd) );
4908  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeAnd) );
4909  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsAnd) );
4910  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsAnd) );
4911  SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreAnd) );
4912  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpAnd) );
4913  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseAnd) );
4914  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolAnd, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
4915  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintAnd) );
4916  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropAnd, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
4918  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropAnd) );
4919  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpAnd, consSepasolAnd, CONSHDLR_SEPAFREQ,
4921  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransAnd) );
4922  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxAnd) );
4923 
4924  /* add AND-constraint handler parameters */
4926  "constraints/" CONSHDLR_NAME "/presolpairwise",
4927  "should pairwise constraint comparison be performed in presolving?",
4928  &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
4930  "constraints/and/presolusehashing",
4931  "should hash table be used for detecting redundant constraints in advance",
4932  &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
4934  "constraints/" CONSHDLR_NAME "/linearize",
4935  "should the AND-constraint get linearized and removed (in presolving)?",
4936  &conshdlrdata->linearize, TRUE, DEFAULT_LINEARIZE, NULL, NULL) );
4938  "constraints/" CONSHDLR_NAME "/enforcecuts",
4939  "should cuts be separated during LP enforcing?",
4940  &conshdlrdata->enforcecuts, TRUE, DEFAULT_ENFORCECUTS, NULL, NULL) );
4942  "constraints/" CONSHDLR_NAME "/aggrlinearization",
4943  "should an aggregated linearization be used?",
4944  &conshdlrdata->aggrlinearization, TRUE, DEFAULT_AGGRLINEARIZATION, NULL, NULL) );
4946  "constraints/" CONSHDLR_NAME "/upgraderesultant",
4947  "should all binary resultant variables be upgraded to implicit binary variables?",
4948  &conshdlrdata->upgrresultant, TRUE, DEFAULT_UPGRRESULTANT, NULL, NULL) );
4950  "constraints/" CONSHDLR_NAME "/dualpresolving",
4951  "should dual presolving be performed?",
4952  &conshdlrdata->dualpresolving, TRUE, DEFAULT_DUALPRESOLVING, NULL, NULL) );
4953 
4954  if( SCIPfindConshdlr(scip, "nonlinear") != NULL )
4955  {
4956  /* include the AND-constraint upgrade in the nonlinear constraint handler */
4957  SCIP_CALL( SCIPincludeNonlinconsUpgrade(scip, NULL, exprgraphnodeReformAnd, EXPRGRAPHREFORM_PRIORITY, TRUE, CONSHDLR_NAME) );
4958  }
4959 
4960  return SCIP_OKAY;
4961 }
4962 
4963 /** creates and captures a AND-constraint
4964  *
4965  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
4966  */
4968  SCIP* scip, /**< SCIP data structure */
4969  SCIP_CONS** cons, /**< pointer to hold the created constraint */
4970  const char* name, /**< name of constraint */
4971  SCIP_VAR* resvar, /**< resultant variable of the operation */
4972  int nvars, /**< number of operator variables in the constraint */
4973  SCIP_VAR** vars, /**< array with operator variables of constraint */
4974  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
4975  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
4976  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
4977  * Usually set to TRUE. */
4978  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
4979  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4980  SCIP_Bool check, /**< should the constraint be checked for feasibility?
4981  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4982  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
4983  * Usually set to TRUE. */
4984  SCIP_Bool local, /**< is constraint only valid locally?
4985  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
4986  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
4987  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
4988  * adds coefficients to this constraint. */
4989  SCIP_Bool dynamic, /**< is constraint subject to aging?
4990  * Usually set to FALSE. Set to TRUE for own cuts which
4991  * are separated as constraints. */
4992  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
4993  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
4994  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
4995  * if it may be moved to a more global node?
4996  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
4997  )
4998 {
4999  SCIP_CONSHDLR* conshdlr;
5000  SCIP_CONSHDLRDATA* conshdlrdata;
5001  SCIP_CONSDATA* consdata;
5002  SCIP_Bool infeasible;
5003 
5004  /* find the AND-constraint handler */
5005  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5006  if( conshdlr == NULL )
5007  {
5008  SCIPerrorMessage("AND-constraint handler not found\n");
5009  return SCIP_PLUGINNOTFOUND;
5010  }
5011 
5012  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5013  assert(conshdlrdata != NULL);
5014 
5015  /* upgrade binary resultant variable to an implicit binary variable */
5016  /* @todo add implicit upgrade in presolving, improve decision making for upgrade by creating an implication graph */
5017  if( conshdlrdata->upgrresultant && SCIPvarGetType(resvar) == SCIP_VARTYPE_BINARY
5018 #if 1 /* todo delete following hack,
5019  * the following avoids upgrading not artificial variables, for example and-resultants which are generated
5020  * from the gate presolver, it seems better to not upgrade these variables
5021  */
5022  && strlen(SCIPvarGetName(resvar)) > strlen(ARTIFICIALVARNAMEPREFIX) && strncmp(SCIPvarGetName(resvar), ARTIFICIALVARNAMEPREFIX, strlen(ARTIFICIALVARNAMEPREFIX)) == 0 )
5023 #else
5024  )
5025 #endif
5026  {
5027  SCIP_VAR* activeresvar;
5028  SCIP_VAR* activevar;
5029  int v;
5030 
5031  if( SCIPisTransformed(scip) )
5032  activeresvar = SCIPvarGetProbvar(resvar);
5033  else
5034  activeresvar = resvar;
5035 
5036  if( SCIPvarGetType(activeresvar) == SCIP_VARTYPE_BINARY )
5037  {
5038  /* check if we can upgrade the variable type of the resultant */
5039  for( v = nvars - 1; v >= 0; --v )
5040  {
5041  if( SCIPisTransformed(scip) )
5042  activevar = SCIPvarGetProbvar(vars[v]);
5043  else
5044  activevar = vars[v];
5045 
5046  if( activevar == activeresvar || SCIPvarGetType(activevar) == SCIP_VARTYPE_IMPLINT )
5047  break;
5048  }
5049 
5050  /* upgrade the type of the resultant */
5051  if( v < 0 )
5052  {
5053  SCIP_CALL( SCIPchgVarType(scip, resvar, SCIP_VARTYPE_IMPLINT, &infeasible) );
5054  assert(!infeasible);
5055  }
5056  }
5057  }
5058 
5059  /* create constraint data */
5060  SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, resvar, FALSE, FALSE) );
5061 
5062  /* create constraint */
5063  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5064  local, modifiable, dynamic, removable, stickingatnode) );
5065 
5066  return SCIP_OKAY;
5067 }
5068 
5069 /** creates and captures an AND-constraint
5070  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
5071  * method SCIPcreateConsAnd(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
5072  *
5073  * @see SCIPcreateConsAnd() for information about the basic constraint flag configuration
5074  *
5075  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5076  */
5078  SCIP* scip, /**< SCIP data structure */
5079  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5080  const char* name, /**< name of constraint */
5081  SCIP_VAR* resvar, /**< resultant variable of the operation */
5082  int nvars, /**< number of operator variables in the constraint */
5083  SCIP_VAR** vars /**< array with operator variables of constraint */
5084  )
5085 {
5086  assert(scip != NULL);
5087 
5088  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
5089  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
5090 
5091  return SCIP_OKAY;
5092 }
5093 
5094 
5095 /** gets number of variables in AND-constraint */
5096 int SCIPgetNVarsAnd(
5097  SCIP* scip, /**< SCIP data structure */
5098  SCIP_CONS* cons /**< constraint data */
5099  )
5100 {
5101  SCIP_CONSDATA* consdata;
5102 
5103  assert(scip != NULL);
5104  assert(cons != NULL);
5105 
5106  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5107  {
5108  SCIPerrorMessage("constraint is not an AND-constraint\n");
5109  SCIPABORT();
5110  return -1; /*lint !e527*/
5111  }
5112 
5113  consdata = SCIPconsGetData(cons);
5114  assert(consdata != NULL);
5115 
5116  return consdata->nvars;
5117 }
5118 
5119 /** gets array of variables in AND-constraint */
5121  SCIP* scip, /**< SCIP data structure */
5122  SCIP_CONS* cons /**< constraint data */
5123  )
5124 {
5125  SCIP_CONSDATA* consdata;
5126 
5127  assert(scip != NULL);
5128  assert(cons != NULL);
5129 
5130  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5131  {
5132  SCIPerrorMessage("constraint is not an AND-constraint\n");
5133  SCIPABORT();
5134  return NULL; /*lint !e527*/
5135  }
5136 
5137  consdata = SCIPconsGetData(cons);
5138  assert(consdata != NULL);
5139 
5140  return consdata->vars;
5141 }
5142 
5143 
5144 /** gets the resultant variable in AND-constraint */
5146  SCIP* scip, /**< SCIP data structure */
5147  SCIP_CONS* cons /**< constraint data */
5148  )
5149 {
5150  SCIP_CONSDATA* consdata;
5151 
5152  assert(cons != NULL);
5153 
5154  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5155  {
5156  SCIPerrorMessage("constraint is not an AND-constraint\n");
5157  SCIPABORT();
5158  return NULL; /*lint !e527*/
5159  }
5160 
5161  consdata = SCIPconsGetData(cons);
5162  assert(consdata != NULL);
5163 
5164  return consdata->resvar;
5165 }
5166 
5167 /** return if the variables of the AND-constraint are sorted with respect to their indices */
5169  SCIP* scip, /**< SCIP data structure */
5170  SCIP_CONS* cons /**< constraint data */
5171  )
5172 {
5173  SCIP_CONSDATA* consdata;
5174 
5175  assert(scip != NULL);
5176  assert(cons != NULL);
5177 
5178  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5179  {
5180  SCIPerrorMessage("constraint is not an AND-constraint\n");
5181  SCIPABORT();
5182  return FALSE; /*lint !e527*/
5183  }
5184 
5185  consdata = SCIPconsGetData(cons);
5186  assert(consdata != NULL);
5187 
5188  return consdata->sorted;
5189 }
5190 
5191 /** sort the variables of the AND-constraint with respect to their indices */
5193  SCIP* scip, /**< SCIP data structure */
5194  SCIP_CONS* cons /**< constraint data */
5195  )
5196 {
5197  SCIP_CONSDATA* consdata;
5198 
5199  assert(scip != NULL);
5200  assert(cons != NULL);
5201 
5202  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5203  {
5204  SCIPerrorMessage("constraint is not an AND-constraint\n");
5205  SCIPABORT();
5206  return SCIP_INVALIDDATA; /*lint !e527*/
5207  }
5208 
5209  consdata = SCIPconsGetData(cons);
5210  assert(consdata != NULL);
5211 
5212  consdataSort(consdata);
5213  assert(consdata->sorted);
5214 
5215  return SCIP_OKAY;
5216 }
5217 
5218 /** when 'upgrading' the given AND-constraint, should the check flag for the upgraded constraint be set to TRUE, even if
5219  * the check flag of this AND-constraint is set to FALSE?
5220  */
5222  SCIP* scip, /**< SCIP data structure */
5223  SCIP_CONS* cons, /**< constraint data */
5224  SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be checked,
5225  * even if the check flag of the AND-constraint is set to FALSE
5226  */
5227  )
5228 {
5229  SCIP_CONSDATA* consdata;
5230 
5231  assert(scip != NULL);
5232  assert(cons != NULL);
5233 
5234  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5235  {
5236  SCIPerrorMessage("constraint is not an AND-constraint\n");
5237  SCIPABORT();
5238  return SCIP_INVALIDDATA; /*lint !e527*/
5239  }
5240 
5241  consdata = SCIPconsGetData(cons);
5242  assert(consdata != NULL);
5243 
5244  consdata->checkwhenupgr = flag;
5245 
5246  return SCIP_OKAY;
5247 }
5248 
5249 /** when 'upgrading' the given AND-constraint, should the removable flag for the upgraded constraint be set to FALSE,
5250  * even if the removable flag of this AND-constraint is set to TRUE?
5251  */
5253  SCIP* scip, /**< SCIP data structure */
5254  SCIP_CONS* cons, /**< constraint data */
5255  SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be not
5256  * removable, even if the removable flag of the AND-constraint is set to
5257  * TRUE
5258  */
5259  )
5260 {
5261  SCIP_CONSDATA* consdata;
5262 
5263  assert(scip != NULL);
5264  assert(cons != NULL);
5265 
5266  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5267  {
5268  SCIPerrorMessage("constraint is not an AND-constraint\n");
5269  SCIPABORT();
5270  return SCIP_INVALIDDATA; /*lint !e527*/
5271  }
5272 
5273  consdata = SCIPconsGetData(cons);
5274  assert(consdata != NULL);
5275 
5276  consdata->notremovablewhenupgr = flag;
5277 
5278  return SCIP_OKAY;
5279 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition: scip.c:30740
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:181
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4143
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11902
static SCIP_RETCODE consdataFixResultantZero(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *resvar, int pos, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1241
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:28372
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:22593
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
Definition: cons_and.c:1868
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip.c:6291
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip.c:41459
#define ARTIFICIALVARNAMEPREFIX
SCIP_RETCODE SCIPincludeNonlinconsUpgrade(SCIP *scip, SCIP_DECL_NONLINCONSUPGD((*nonlinconsupgd)), SCIP_DECL_EXPRGRAPHNODEREFORM((*nodereform)), int priority, SCIP_Bool active, const char *conshdlrname)
static SCIP_DECL_CONSSEPASOL(consSepasolAnd)
Definition: cons_and.c:4260
SCIP_RETCODE SCIPexprgraphAddNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int mindepth, int nchildren, SCIP_EXPRGRAPHNODE **children)
Definition: expr.c:15153
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:10889
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
static SCIP_RETCODE cliquePresolve(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars, int *naggrvars, int *nchgcoefs, int *ndelconss, int *naddconss)
Definition: cons_and.c:2589
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19649
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47298
SCIP_RETCODE SCIPexprgraphAddVars(SCIP_EXPRGRAPH *exprgraph, int nvars, void **vars, SCIP_EXPRGRAPHNODE **varnodes)
Definition: expr.c:15237
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8245
#define CONSHDLR_SEPAPRIORITY
Definition: cons_and.c:51
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip.c:6314
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip.c:19115
static SCIP_DECL_EVENTEXEC(eventExecAnd)
Definition: cons_and.c:4853
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19509
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2265
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:41226
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
int SCIPexprgraphGetNodeNChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12947
SCIP_RETCODE SCIPsortAndCons(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5193
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
static SCIP_DECL_CONSENFORELAX(consEnforelaxAnd)
Definition: cons_and.c:4296
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip.c:6544
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:11720
#define SCIP_MAXSTRLEN
Definition: def.h:259
static SCIP_RETCODE mergeMultiples(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, unsigned char **entries, int *nentries, int *nfixedvars, int *nchgcoefs, int *ndelconss)
Definition: cons_and.c:1506
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:627
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip.c:6036
static SCIP_RETCODE analyzeConflictZero(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:1205
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:28400
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12663
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:46813
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30668
static SCIP_RETCODE consdataSwitchWatchedvars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
Definition: cons_and.c:315
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47088
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:392
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:27388
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47015
SCIP_Bool SCIPconsIsAdded(SCIP_CONS *cons)
Definition: cons.c:8355
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8611
static SCIP_DECL_HASHKEYEQ(hashKeyEqAndcons)
Definition: cons_and.c:3246
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:485
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip.c:18957
static SCIP_DECL_CONSPARSE(consParseAnd)
Definition: cons_and.c:4703
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip.c:28112
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip.c:18038
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18766
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip.c:6205
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47387
void SCIPgmlWriteClosing(FILE *file)
Definition: misc.c:687
static SCIP_RETCODE consdataFixOperandsOne(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1280
static SCIP_RETCODE consdataFreeRows(SCIP *scip, SCIP_CONSDATA *consdata)
Definition: cons_and.c:482
#define DEFAULT_PRESOLUSEHASHING
Definition: cons_and.c:78
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11686
#define FALSE
Definition: def.h:64
int SCIPconsGetPos(SCIP_CONS *cons)
Definition: cons.c:7996
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
SCIP_RETCODE SCIPincludeConshdlrAnd(SCIP *scip)
Definition: cons_and.c:4879
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10289
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip.c:5894
#define CONSHDLR_CHECKPRIORITY
Definition: cons_and.c:53
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:41747
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47028
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47100
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
enum Proprule PROPRULE
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
Definition: scip.c:21660
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8265
static SCIP_DECL_CONSPROP(consPropAnd)
Definition: cons_and.c:4349
#define SCIP_PRESOLTIMING_EXHAUSTIVE
Definition: type_timing.h:45
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
Definition: cons_and.c:558
#define CONSHDLR_NAME
Definition: cons_and.c:49
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8295
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip.c:27155
static SCIP_RETCODE consdataLinearize(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nfixedvars, int *nupgdconss)
Definition: cons_and.c:1334
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip.c:5948
Constraint handler for AND constraints, .
static SCIP_DECL_CONSINITPRE(consInitpreAnd)
Definition: cons_and.c:3870
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:22628
#define DEFAULT_ENFORCECUTS
Definition: cons_and.c:72
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_and.c:167
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46963
static SCIP_DECL_CONSPRINT(consPrintAnd)
Definition: cons_and.c:4628
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip.c:1017
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num)
Definition: cons_and.c:375
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8255
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition: type_event.h:108
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip.c:6337
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip.c:41423
#define SCIPdebugMsgPrint
Definition: scip.h:456
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip.c:18998
static SCIP_RETCODE consdataDropWatchedEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int filterpos)
Definition: cons_and.c:240
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip.c:6521
static SCIP_DECL_CONSEXITSOL(consExitsolAnd)
Definition: cons_and.c:4150
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8047
#define EVENTHDLR_DESC
Definition: cons_and.c:68
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1343
#define DEFAULT_PRESOLPAIRWISE
Definition: cons_and.c:70
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:11992
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip.c:27584
int SCIPexprgraphGetNodePolynomialNMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13170
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:2014
#define SCIP_REAL_FORMAT
Definition: def.h:152
static SCIP_RETCODE dualPresolve(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_EVENTHDLR *eventhdlr, unsigned char **entries, int *nentries, SCIP_Bool *cutoff, int *nfixedvars, int *naggrvars, int *nchgcoefs, int *ndelconss, int *nupgdconss, int *naddconss)
Definition: cons_and.c:1954
SCIP_Bool SCIPisAndConsSorted(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5169
static SCIP_DECL_CONSENFOPS(consEnfopsAnd)
Definition: cons_and.c:4305
int SCIPexprGetMonomialNFactors(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5910
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17092
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:16695
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:64
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip.c:27133
SCIP_EXPROP SCIPexprgraphGetNodeOperator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13007
SCIP_EXPRDATA_MONOMIAL ** SCIPexprgraphGetNodePolynomialMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13158
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip.c:25479
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11628
static SCIP_DECL_CONSFREE(consFreeAnd)
Definition: cons_and.c:3852
#define EVENTHDLR_NAME
Definition: cons_and.c:67
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:22599
static SCIP_DECL_CONSPRESOL(consPresolAnd)
Definition: cons_and.c:4384
SCIP_RETCODE SCIPparseVarsList(SCIP *scip, const char *str, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize, char **endptr, char delimiter, SCIP_Bool *success)
Definition: scip.c:18115
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5121
SCIP_Real SCIPexprgraphGetNodePolynomialConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13182
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip.c:6060
#define CONSHDLR_PRESOLTIMING
Definition: cons_and.c:64
SCIP_RETCODE SCIPgetBinvarRepresentatives(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **repvars, SCIP_Bool *negated)
Definition: scip.c:19162
static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, int *firstchange, SCIP_Bool *cutoff, int *naggrvars, int *ndelconss)
Definition: cons_and.c:3317
SCIP_RETCODE SCIPcreateConsAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_and.c:4968
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12591
#define CONSHDLR_PROP_TIMING
Definition: cons_and.c:65
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5146
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46976
static SCIP_RETCODE preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, SCIP_Bool *cutoff, int *naggrvars, int *nbdchgs, int *ndelconss)
Definition: cons_and.c:3507
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:13297
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_and.c:643
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_RETCODE SCIPaddVarImplication(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype, SCIP_Real implbound, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip.c:24094
static SCIP_DECL_CONSDELETE(consDeleteAnd)
Definition: cons_and.c:4170
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46731
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip.c:21788
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7986
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_Bool *violated)
Definition: cons_and.c:994
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:25932
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8205
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIP_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9034
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip.c:6085
SCIP_RETCODE SCIPcreateConsBasicAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars)
Definition: cons_and.c:5078
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4133
static SCIP_DECL_CONSTRANS(consTransAnd)
Definition: cons_and.c:4185
#define REALABS(x)
Definition: def.h:173
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible)
Definition: cons_and.c:934
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:66
SCIP_RETCODE SCIPexprgraphCreateNodeLinear(BMS_BLKMEM *blkmem, SCIP_EXPRGRAPHNODE **node, int ncoefs, SCIP_Real *coefs, SCIP_Real constant)
Definition: expr.c:13414
#define DEFAULT_LINEARIZE
Definition: cons_and.c:71
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPvarGetAggregatedObj(SCIP_VAR *var, SCIP_Real *aggrobj)
Definition: var.c:17146
#define SCIP_CALL(x)
Definition: def.h:350
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:473
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:63
enum Proprule PROPRULE
Definition: cons_and.c:144
SCIP_RETCODE SCIPchgAndConsRemovableFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition: cons_and.c:5253
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip.c:27535
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars, int *nupgdconss)
Definition: cons_and.c:1663
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8225
#define EXPRGRAPHREFORM_PRIORITY
Definition: cons_and.c:81
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:34661
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip.c:6360
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:262
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:50
static SCIP_DECL_CONSINITLP(consInitlpAnd)
Definition: cons_and.c:4215
static SCIP_RETCODE conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_and.c:201
static SCIP_DECL_CONSGETVARS(consGetVarsAnd)
Definition: cons_and.c:4811
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:513
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9092
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
public data structures and miscellaneous methods
SCIP_RETCODE SCIPchgAndConsCheckFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition: cons_and.c:5222
#define SCIP_Bool
Definition: def.h:61
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
Definition: cons_and.c:583
int SCIPgetNImplVars(SCIP *scip)
Definition: scip.c:11947
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:959
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_and.c:3436
#define CONSHDLR_NEEDSCONS
Definition: cons_and.c:62
static SCIP_DECL_CONSCOPY(consCopyAnd)
Definition: cons_and.c:4642
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip.c:30402
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr, int nvars, SCIP_VAR **vars, SCIP_VAR *resvar, SCIP_Bool checkwhenupgr, SCIP_Bool notremovablewhenupgr)
Definition: cons_and.c:399
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43045
constraint handler for nonlinear constraints
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip.c:29091
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
#define SCIP_DECL_CONSEXITPRE(x)
Definition: type_cons.h:164
#define MAX(x, y)
Definition: tclique_def.h:75
#define NMINCOMPARISONS
Definition: cons_and.c:79
static SCIP_DECL_HASHGETKEY(hashGetKeyAndcons)
Definition: cons_and.c:3238
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8006
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11353
methods for debugging
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8115
#define HASHSIZE_ANDCONS
Definition: cons_and.c:77
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8185
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8155
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_and.c:153
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:41272
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyAnd)
Definition: cons_and.c:3836
#define CONSHDLR_MAXPREROUNDS
Definition: cons_and.c:59
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip.c:17619
#define DEFAULT_UPGRRESULTANT
Definition: cons_and.c:74
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25575
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:116
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip.c:21714
#define DEFAULT_DUALPRESOLVING
Definition: cons_and.c:75
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip.c:6498
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:65
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2326
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47039
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIPexprGetMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5900
#define CONSHDLR_DELAYPROP
Definition: cons_and.c:61
Proprule
void * SCIPexprgraphGetNodeVar(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13039
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11857
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35836
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2064
static SCIP_DECL_CONSENFOLP(consEnfolpAnd)
Definition: cons_and.c:4287
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11812
#define CONSHDLR_EAGERFREQ
Definition: cons_and.c:56
#define CONSHDLR_PROPFREQ
Definition: cons_and.c:55
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
Definition: scip.c:6229
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30540
SCIP_RETCODE SCIPwriteVarsList(SCIP *scip, FILE *file, SCIP_VAR **vars, int nvars, SCIP_Bool type, char delimiter)
Definition: scip.c:17797
static SCIP_RETCODE analyzeZeroResultant(SCIP *scip, SCIP_CONS *cons, int watchedvar1, int watchedvar2, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1445
static SCIP_DECL_EXPRGRAPHNODEREFORM(exprgraphnodeReformAnd)
Definition: cons_and.c:3711
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
static SCIP_RETCODE consdataCatchEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:263
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47002
static SCIP_DECL_CONSSEPALP(consSepalpAnd)
Definition: cons_and.c:4233
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip.c:1920
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:11492
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8016
#define DEFAULT_AGGRLINEARIZATION
Definition: cons_and.c:73
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:887
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27761
#define MINGAINPERNMINCOMPARISONS
Definition: cons_and.c:80
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip.c:25885
#define CONSHDLR_DELAYSEPA
Definition: cons_and.c:60
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:6253
static SCIP_RETCODE consdataCatchWatchedEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int *filterpos)
Definition: cons_and.c:216
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip.c:13790
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16781
static SCIP_RETCODE consdataDropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:289
#define CONSHDLR_SEPAFREQ
Definition: cons_and.c:54
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip.c:25684
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:18732
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8235
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip.c:6567
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5097
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8175
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip.c:25848
static SCIP_DECL_HASHKEYVAL(hashKeyValAndcons)
Definition: cons_and.c:3292
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12957
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8165
void SCIPvarsGetProbvar(SCIP_VAR **vars, int nvars)
Definition: var.c:11608
static void consdataSort(SCIP_CONSDATA *consdata)
Definition: cons_and.c:706
#define SCIP_Longint
Definition: def.h:134
static SCIP_DECL_CONSGETNVARS(consGetNVarsAnd)
Definition: cons_and.c:4832
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:16959
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip.c:31134
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:261
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
static SCIP_DECL_CONSRESPROP(consRespropAnd)
Definition: cons_and.c:4595
constraint handler for pseudoboolean constraints
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46989
static SCIP_DECL_CONSCHECK(consCheckAnd)
Definition: cons_and.c:4328
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:49
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
Definition: misc.c:671
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47399
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:16804
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2874
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:419
#define CONSHDLR_DESC
Definition: cons_and.c:50
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip.c:6181
#define SCIPcombineTwoInt(a, b)
Definition: pub_misc.h:479
#define SCIPABORT()
Definition: def.h:322
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip.c:17735
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38911
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
Definition: cons_and.c:1124
#define CONSHDLR_ENFOPRIORITY
Definition: cons_and.c:52
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23039
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int *nchgcoefs)
Definition: cons_and.c:787
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip.c:19045
static SCIP_RETCODE analyzeConflictOne(SCIP *scip, SCIP_CONS *cons, int falsepos)
Definition: cons_and.c:1173
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4239
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16817
static SCIP_DECL_CONSLOCK(consLockAnd)
Definition: cons_and.c:4605
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:22624
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip.c:5994