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