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