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