Scippy

SCIP

Solving Constraint Integer Programs

cons_and.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_and.c
17  * @brief Constraint handler for AND-constraints, \f$r = x_1 \wedge x_2 \wedge \dots \wedge x_n\f$
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  * @author Michael Winkler
21  *
22  * This constraint handler deals with AND-constraints. These are constraint of the form:
23  *
24  * \f[
25  * r = x_1 \wedge x_2 \wedge \dots \wedge x_n
26  * \f]
27  *
28  * where \f$x_i\f$ is a binary variable for all \f$i\f$. Hence, \f$r\f$ is also of binary type. The variable \f$r\f$ is
29  * called resultant and the \f$x\f$'s operators.
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include "blockmemshell/memory.h"
35 #include "nlpi/pub_expr.h"
36 #include "scip/cons_and.h"
37 #include "scip/cons_linear.h"
38 #include "scip/cons_logicor.h"
39 #include "scip/cons_nonlinear.h"
41 #include "scip/cons_setppc.h"
42 #include "scip/debug.h"
43 #include "scip/pub_cons.h"
44 #include "scip/pub_event.h"
45 #include "scip/pub_lp.h"
46 #include "scip/pub_message.h"
47 #include "scip/pub_misc.h"
48 #include "scip/pub_misc_sort.h"
49 #include "scip/pub_var.h"
50 #include "scip/scip_conflict.h"
51 #include "scip/scip_cons.h"
52 #include "scip/scip_copy.h"
53 #include "scip/scip_cut.h"
54 #include "scip/scip_event.h"
55 #include "scip/scip_general.h"
56 #include "scip/scip_lp.h"
57 #include "scip/scip_mem.h"
58 #include "scip/scip_message.h"
59 #include "scip/scip_numerics.h"
60 #include "scip/scip_param.h"
61 #include "scip/scip_prob.h"
62 #include "scip/scip_probing.h"
63 #include "scip/scip_sol.h"
64 #include "scip/scip_tree.h"
65 #include "scip/scip_var.h"
66 #include <string.h>
67 
68 
69 /* constraint handler properties */
70 #define CONSHDLR_NAME "and"
71 #define CONSHDLR_DESC "constraint handler for AND-constraints: r = and(x1, ..., xn)"
72 #define CONSHDLR_SEPAPRIORITY +850100 /**< priority of the constraint handler for separation */
73 #define CONSHDLR_ENFOPRIORITY -850100 /**< priority of the constraint handler for constraint enforcing */
74 #define CONSHDLR_CHECKPRIORITY -850100 /**< priority of the constraint handler for checking feasibility */
75 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
76 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
77 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
78  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
79 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
80 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
81 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
82 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
83 
84 #define CONSHDLR_PRESOLTIMING (SCIP_PRESOLTIMING_FAST | SCIP_PRESOLTIMING_EXHAUSTIVE)
85 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
86 
87 #define EVENTHDLR_NAME "and"
88 #define EVENTHDLR_DESC "bound change event handler for AND-constraints"
89 
90 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
91 #define DEFAULT_LINEARIZE FALSE /**< should constraint get linearized and removed? */
92 #define DEFAULT_ENFORCECUTS TRUE /**< should cuts be separated during LP enforcing? */
93 #define DEFAULT_AGGRLINEARIZATION FALSE /**< should an aggregated linearization be used? */
94 #define DEFAULT_UPGRRESULTANT TRUE /**< should all binary resultant variables be upgraded to implicit binary variables */
95 #define DEFAULT_DUALPRESOLVING TRUE /**< should dual presolving be performed? */
96 
97 #define HASHSIZE_ANDCONS 500 /**< minimal size of hash table in and constraint tables */
98 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
99 #define NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
100 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
101 #define EXPRGRAPHREFORM_PRIORITY 100000 /**< priority of expression graph node reformulation method */
103 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
104 
105 /*
106  * Data structures
107  */
108 
109 /** constraint data for AND-constraints */
110 struct SCIP_ConsData
111 {
112  SCIP_VAR** vars; /**< variables in the AND-constraint */
113  SCIP_VAR* resvar; /**< resultant variable */
114  SCIP_ROW** rows; /**< rows for linear relaxation of AND-constraint */
115  SCIP_ROW* aggrrow; /**< aggregated row for linear relaxation of AND-constraint */
116  int nvars; /**< number of variables in AND-constraint */
117  int varssize; /**< size of vars array */
118  int nrows; /**< number of rows for linear relaxation of AND-constraint */
119  int watchedvar1; /**< position of first watched operator variable */
120  int watchedvar2; /**< position of second watched operator variable */
121  int filterpos1; /**< event filter position of first watched operator variable */
122  int filterpos2; /**< event filter position of second watched operator variable */
123  unsigned int propagated:1; /**< is constraint already preprocessed/propagated? */
124  unsigned int nofixedzero:1; /**< is none of the operator variables fixed to FALSE? */
125  unsigned int impladded:1; /**< were the implications of the constraint already added? */
126  unsigned int opimpladded:1; /**< was the implication for 2 operands with fixed resultant added? */
127  unsigned int sorted:1; /**< are the constraint's variables sorted? */
128  unsigned int changed:1; /**< was constraint changed since last pair preprocessing round? */
129  unsigned int merged:1; /**< are the constraint's equal variables already merged? */
130  unsigned int checkwhenupgr:1; /**< if AND-constraint is upgraded to an logicor constraint or the and-
131  * constraint is linearized, should the check flag be set to true, even
132  * if the AND-constraint has a check flag set to false? */
133  unsigned int notremovablewhenupgr:1;/**< if AND-constraint is upgraded to an logicor constraint or the and-
134  * constraint is linearized, should the removable flag be set to false,
135  * even if the AND-constraint has a removable flag set to true? */
136 };
137 
138 /** constraint handler data */
139 struct SCIP_ConshdlrData
140 {
141  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events on watched variables */
142  SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
143  SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
144  SCIP_Bool linearize; /**< should constraint get linearized and removed? */
145  SCIP_Bool enforcecuts; /**< should cuts be separated during LP enforcing? */
146  SCIP_Bool aggrlinearization; /**< should an aggregated linearization be used? */
147  SCIP_Bool upgrresultant; /**< upgrade binary resultant variable to an implicit binary variable */
148  SCIP_Bool dualpresolving; /**< should dual presolving be performed? */
149 };
150 
151 
152 /*
153  * Propagation rules
154  */
155 
156 enum Proprule
157 {
158  PROPRULE_INVALID = 0, /**< propagation was applied without a specific propagation rule */
159  PROPRULE_1 = 1, /**< v_i = FALSE => r = FALSE */
160  PROPRULE_2 = 2, /**< r = TRUE => v_i = TRUE for all i */
161  PROPRULE_3 = 3, /**< v_i = TRUE for all i => r = TRUE */
162  PROPRULE_4 = 4 /**< r = FALSE, v_i = TRUE for all i except j => v_j = FALSE */
163 };
164 typedef enum Proprule PROPRULE;
166 
167 /*
168  * Local methods
169  */
170 
171 /** installs rounding locks for the given variable in the given AND-constraint */
172 static
174  SCIP* scip, /**< SCIP data structure */
175  SCIP_CONS* cons, /**< constraint data */
176  SCIP_VAR* var /**< variable of constraint entry */
177  )
178 {
179  /* rounding in both directions may violate the constraint */
180  SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
181 
182  return SCIP_OKAY;
183 }
184 
185 /** removes rounding locks for the given variable in the given AND-constraint */
186 static
188  SCIP* scip, /**< SCIP data structure */
189  SCIP_CONS* cons, /**< constraint data */
190  SCIP_VAR* var /**< variable of constraint entry */
191  )
192 {
193  /* rounding in both directions may violate the constraint */
194  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
195 
196  return SCIP_OKAY;
197 }
198 
199 /** creates constraint handler data */
200 static
202  SCIP* scip, /**< SCIP data structure */
203  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
204  SCIP_EVENTHDLR* eventhdlr /**< event handler */
205  )
206 {
207  assert(scip != NULL);
208  assert(conshdlrdata != NULL);
209  assert(eventhdlr != NULL);
210 
211  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
212 
213  /* set event handler for catching bound change events on variables */
214  (*conshdlrdata)->eventhdlr = eventhdlr;
215 
216  return SCIP_OKAY;
217 }
218 
219 /** frees constraint handler data */
220 static
222  SCIP* scip, /**< SCIP data structure */
223  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
224  )
225 {
226  assert(conshdlrdata != NULL);
227  assert(*conshdlrdata != NULL);
228 
229  SCIPfreeBlockMemory(scip, conshdlrdata);
230 
231  return SCIP_OKAY;
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], SCIPconsGetHdlr(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], SCIPconsGetHdlr(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, SCIPconsGetHdlr(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", 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 SCIPhashTwo(SCIPcombineTwoInt(consdata->nvars, minidx),
3344  SCIPcombineTwoInt(mididx, maxidx));
3345 }
3346 
3347 /** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
3348  * accordingly; in contrast to removeRedundantConstraints(), it uses a hash table
3349  */
3350 static
3352  SCIP* scip, /**< SCIP data structure */
3353  BMS_BLKMEM* blkmem, /**< block memory */
3354  SCIP_CONS** conss, /**< constraint set */
3355  int nconss, /**< number of constraints in constraint set */
3356  int* firstchange, /**< pointer to store first changed constraint */
3357  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3358  int* naggrvars, /**< pointer to count number of aggregated variables */
3359  int* ndelconss /**< pointer to count number of deleted constraints */
3360  )
3361 {
3362  SCIP_HASHTABLE* hashtable;
3363  int hashtablesize;
3364  int c;
3365 
3366  assert(conss != NULL);
3367  assert(ndelconss != NULL);
3368 
3369  /* create a hash table for the constraint set */
3370  hashtablesize = nconss;
3371  hashtablesize = MAX(hashtablesize, HASHSIZE_ANDCONS);
3372  SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
3373  hashGetKeyAndcons, hashKeyEqAndcons, hashKeyValAndcons, (void*) scip) );
3374 
3375  *cutoff = FALSE;
3376 
3377  /* check all constraints in the given set for redundancy */
3378  for( c = 0; c < nconss; ++c )
3379  {
3380  SCIP_CONS* cons0;
3381  SCIP_CONS* cons1;
3382  SCIP_CONSDATA* consdata0;
3383 
3384  cons0 = conss[c];
3385 
3386  if( !SCIPconsIsActive(cons0) || SCIPconsIsModifiable(cons0) )
3387  continue;
3388 
3389  consdata0 = SCIPconsGetData(cons0);
3390 
3391  /* sort the constraint */
3392  consdataSort(consdata0);
3393  assert(consdata0->sorted);
3394 
3395  /* get constraint from current hash table with same variables as cons0 */
3396  cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
3397 
3398  if( cons1 != NULL )
3399  {
3400  SCIP_CONSDATA* consdata1;
3401  SCIP_Bool redundant;
3402 
3403  assert(SCIPconsIsActive(cons1));
3404  assert(!SCIPconsIsModifiable(cons1));
3405 
3406  consdata1 = SCIPconsGetData(cons1);
3407 
3408  assert(consdata1 != NULL);
3409  assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
3410 
3411  assert(consdata0->sorted && consdata1->sorted);
3412  assert(consdata0->vars[0] == consdata1->vars[0]);
3413 
3414  redundant = FALSE;
3415 
3416  if( consdata0->resvar != consdata1->resvar )
3417  {
3418  SCIP_Bool aggregated;
3419 
3420  assert(SCIPvarCompare(consdata0->resvar, consdata1->resvar) != 0);
3421 
3422  /* aggregate resultants */
3423  SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3424  cutoff, &redundant, &aggregated) );
3425  assert(redundant || SCIPdoNotAggr(scip));
3426 
3427  if( aggregated )
3428  ++(*naggrvars);
3429  if( *cutoff )
3430  goto TERMINATE;
3431  }
3432  else
3433  redundant = TRUE;
3434 
3435  /* delete consdel */
3436  if( redundant )
3437  {
3438  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
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  SCIP_CALL( 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  unsigned int resid;
4053  unsigned int varid;
4054  unsigned 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 = (unsigned int)(size_t) SCIPhashmapGetImage(hashmap, activevar);
4111  if( resid == 0 )
4112  {
4113  resid = id;
4114  ++id;
4115  SCIP_CALL( SCIPhashmapInsert(hashmap, (void*)activevar, (void*)(size_t)resid) );
4116 
4117  /* write new gml node for new resultant */
4118  SCIPgmlWriteNode(gmlfile, resid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4119  }
4120 
4121  /* copy operands to get problem variables for */
4122  SCIP_CALL( SCIPduplicateBufferArray(scip, &activeconsvars, consdata->vars, consdata->nvars) );
4123 
4124  /* get problem variables of operands */
4125  SCIPvarsGetProbvar(activeconsvars, consdata->nvars);
4126 
4127  for( v = consdata->nvars - 1; v >= 0; --v )
4128  {
4129  /* check if we already found this variables */
4130  varid = (unsigned int)(size_t) SCIPhashmapGetImage(hashmap, activeconsvars[v]);
4131  if( varid == 0 )
4132  {
4133  varid = id;
4134  ++id;
4135  SCIP_CALL( SCIPhashmapInsert(hashmap, (void*)activeconsvars[v], (void*)(size_t)varid) );
4136 
4137  /* write new gml node for new operand */
4138  SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activeconsvars[v]), NULL, NULL, NULL);
4139  }
4140  /* write gml arc between resultant and operand */
4141  SCIPgmlWriteArc(gmlfile, resid, varid, NULL, NULL);
4142  }
4143 
4144  /* free temporary memory for active constraint variables */
4145  SCIPfreeBufferArray(scip, &activeconsvars);
4146  }
4147 
4148  /* write all remaining variables as nodes */
4149 #ifdef SCIP_DISABLED_CODE
4150  for( v = nvars - 1; v >= 0; --v )
4151  {
4152  activevar = SCIPvarGetProbvar(vars[v]);
4153 
4154  varid = (unsigned int)(size_t) SCIPhashmapGetImage(hashmap, activevar);
4155  if( varid == 0 )
4156  {
4157  varid = id;
4158  ++id;
4159  SCIP_CALL( SCIPhashmapInsert(hashmap, (void*)activeconsvars[v], (void*)(size_t)varid) );
4160 
4161  /* write new gml node for new operand */
4162  SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4163  }
4164  }
4165 #endif
4166 
4167  /* free the variable mapping hash map */
4168  SCIPhashmapFree(&hashmap);
4169 
4170  SCIPgmlWriteClosing(gmlfile);
4171 
4172  fclose(gmlfile);
4173 
4174  SCIPfreeBufferArray(scip, &varnodeids);
4175  SCIPfreeBufferArray(scip, &vars);
4176 
4177  return SCIP_OKAY;
4178 }
4179 #endif
4180 
4181 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4182 static
4183 SCIP_DECL_CONSEXITSOL(consExitsolAnd)
4184 { /*lint --e{715}*/
4185  SCIP_CONSDATA* consdata;
4186  int c;
4187 
4188  /* release and free the rows of all constraints */
4189  for( c = 0; c < nconss; ++c )
4190  {
4191  consdata = SCIPconsGetData(conss[c]);
4192  assert(consdata != NULL);
4193 
4194  SCIP_CALL( consdataFreeRows(scip, consdata) );
4195  }
4196 
4197  return SCIP_OKAY;
4198 }
4199 
4200 
4201 /** frees specific constraint data */
4202 static
4203 SCIP_DECL_CONSDELETE(consDeleteAnd)
4204 { /*lint --e{715}*/
4205  SCIP_CONSHDLRDATA* conshdlrdata;
4206 
4207  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4208  assert(conshdlrdata != NULL);
4209 
4210  SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4211 
4212  return SCIP_OKAY;
4213 }
4214 
4215 
4216 /** transforms constraint data into data belonging to the transformed problem */
4217 static
4218 SCIP_DECL_CONSTRANS(consTransAnd)
4219 { /*lint --e{715}*/
4220  SCIP_CONSHDLRDATA* conshdlrdata;
4221  SCIP_CONSDATA* sourcedata;
4222  SCIP_CONSDATA* targetdata;
4223 
4224  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4225  assert(conshdlrdata != NULL);
4226 
4227  sourcedata = SCIPconsGetData(sourcecons);
4228  assert(sourcedata != NULL);
4229 
4230  /* create target constraint data */
4231  SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr,
4232  sourcedata->nvars, sourcedata->vars, sourcedata->resvar, sourcedata->checkwhenupgr,
4233  sourcedata->notremovablewhenupgr) );
4234 
4235  /* create target constraint */
4236  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4237  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4238  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4239  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4240  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4241 
4242  return SCIP_OKAY;
4243 }
4244 
4245 
4246 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4247 static
4248 SCIP_DECL_CONSINITLP(consInitlpAnd)
4249 { /*lint --e{715}*/
4250  int i;
4251 
4252  *infeasible = FALSE;
4253 
4254  for( i = 0; i < nconss && !(*infeasible); i++ )
4255  {
4256  assert(SCIPconsIsInitial(conss[i]));
4257  SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4258  }
4259 
4260  return SCIP_OKAY;
4261 }
4262 
4263 
4264 /** separation method of constraint handler for LP solutions */
4265 static
4266 SCIP_DECL_CONSSEPALP(consSepalpAnd)
4267 { /*lint --e{715}*/
4268  SCIP_Bool separated;
4269  SCIP_Bool cutoff;
4270  int c;
4271 
4272  *result = SCIP_DIDNOTFIND;
4273 
4274  /* separate all useful constraints */
4275  for( c = 0; c < nusefulconss; ++c )
4276  {
4277  SCIP_CALL( separateCons(scip, conss[c], NULL, &separated, &cutoff) );
4278  if ( cutoff )
4279  *result = SCIP_CUTOFF;
4280  else if ( separated )
4281  *result = SCIP_SEPARATED;
4282  }
4283 
4284  /* combine constraints to get more cuts */
4285  /**@todo combine constraints to get further cuts */
4286 
4287  return SCIP_OKAY;
4288 }
4289 
4290 
4291 /** separation method of constraint handler for arbitrary primal solutions */
4292 static
4293 SCIP_DECL_CONSSEPASOL(consSepasolAnd)
4294 { /*lint --e{715}*/
4295  SCIP_Bool separated;
4296  SCIP_Bool cutoff;
4297  int c;
4298 
4299  *result = SCIP_DIDNOTFIND;
4300 
4301  /* separate all useful constraints */
4302  for( c = 0; c < nusefulconss; ++c )
4303  {
4304  SCIP_CALL( separateCons(scip, conss[c], sol, &separated, &cutoff) );
4305  if ( cutoff )
4306  *result = SCIP_CUTOFF;
4307  else if ( separated )
4308  *result = SCIP_SEPARATED;
4309  }
4310 
4311  /* combine constraints to get more cuts */
4312  /**@todo combine constraints to get further cuts */
4313 
4314  return SCIP_OKAY;
4315 }
4316 
4317 
4318 /** constraint enforcing method of constraint handler for LP solutions */
4319 static
4320 SCIP_DECL_CONSENFOLP(consEnfolpAnd)
4321 { /*lint --e{715}*/
4322  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) );
4323 
4324  return SCIP_OKAY;
4325 }
4326 
4327 /** constraint enforcing method of constraint handler for relaxation solutions */
4328 static
4329 SCIP_DECL_CONSENFORELAX(consEnforelaxAnd)
4330 { /*lint --e{715}*/
4331  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) );
4332 
4333  return SCIP_OKAY;
4334 }
4335 
4336 /** constraint enforcing method of constraint handler for pseudo solutions */
4337 static
4338 SCIP_DECL_CONSENFOPS(consEnfopsAnd)
4339 { /*lint --e{715}*/
4340  SCIP_Bool violated;
4341  int i;
4342 
4343  /* method is called only for integral solutions, because the enforcing priority is negative */
4344  for( i = 0; i < nconss; i++ )
4345  {
4346  SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
4347  if( violated )
4348  {
4349  *result = SCIP_INFEASIBLE;
4350  return SCIP_OKAY;
4351  }
4352  }
4353  *result = SCIP_FEASIBLE;
4354 
4355  return SCIP_OKAY;
4356 }
4357 
4358 
4359 /** feasibility check method of constraint handler for integral solutions */
4360 static
4361 SCIP_DECL_CONSCHECK(consCheckAnd)
4362 { /*lint --e{715}*/
4363  SCIP_Bool violated;
4364  int i;
4365 
4366  *result = SCIP_FEASIBLE;
4367 
4368  /* method is called only for integral solutions, because the enforcing priority is negative */
4369  for( i = 0; i < nconss && (*result == SCIP_FEASIBLE || completely); i++ )
4370  {
4371  SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, printreason, &violated) );
4372  if( violated )
4373  *result = SCIP_INFEASIBLE;
4374  }
4375 
4376  return SCIP_OKAY;
4377 }
4378 
4379 
4380 /** domain propagation method of constraint handler */
4381 static
4382 SCIP_DECL_CONSPROP(consPropAnd)
4383 { /*lint --e{715}*/
4384  SCIP_CONSHDLRDATA* conshdlrdata;
4385  SCIP_Bool cutoff;
4386  int nfixedvars;
4387  int nupgdconss;
4388  int c;
4389 
4390  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4391  assert(conshdlrdata != NULL);
4392 
4393  cutoff = FALSE;
4394  nfixedvars = 0;
4395  nupgdconss = 0;
4396 
4397  /* propagate all useful constraints */
4398  for( c = 0; c < nusefulconss && !cutoff; ++c )
4399  {
4400  SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars, &nupgdconss) );
4401  }
4402 
4403  /* return the correct result */
4404  if( cutoff )
4405  *result = SCIP_CUTOFF;
4406  else if( nfixedvars > 0 || nupgdconss > 0 )
4407  *result = SCIP_REDUCEDDOM;
4408  else
4409  *result = SCIP_DIDNOTFIND;
4410 
4411  return SCIP_OKAY;
4412 }
4413 
4414 
4415 /** presolving method of constraint handler */
4416 static
4417 SCIP_DECL_CONSPRESOL(consPresolAnd)
4418 { /*lint --e{715}*/
4419  SCIP_CONSHDLRDATA* conshdlrdata;
4420  SCIP_CONS* cons;
4421  SCIP_CONSDATA* consdata;
4422  unsigned char* entries;
4423  SCIP_Bool cutoff;
4424  int oldnfixedvars;
4425  int oldnaggrvars;
4426  int oldnchgbds;
4427  int oldndelconss;
4428  int oldnupgdconss;
4429  int firstchange;
4430  int nentries;
4431  int c;
4432 
4433  assert(result != NULL);
4434 
4435  oldnfixedvars = *nfixedvars;
4436  oldnaggrvars = *naggrvars;
4437  oldnchgbds = *nchgbds;
4438  oldndelconss = *ndelconss;
4439  oldnupgdconss = *nupgdconss;
4440 
4441  nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
4442  SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
4443 
4444  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4445  assert(conshdlrdata != NULL);
4446 
4447  /* process constraints */
4448  cutoff = FALSE;
4449  firstchange = INT_MAX;
4450  for( c = 0; c < nconss && !cutoff && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
4451  {
4452  cons = conss[c];
4453  assert(cons != NULL);
4454  consdata = SCIPconsGetData(cons);
4455  assert(consdata != NULL);
4456 
4457  /* force presolving the constraint in the initial round */
4458  if( nrounds == 0 )
4459  consdata->propagated = FALSE;
4460 
4461  /* remember the first changed constraint to begin the next aggregation round with */
4462  if( firstchange == INT_MAX && consdata->changed )
4463  firstchange = c;
4464 
4465  /* propagate constraint */
4466  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nupgdconss) );
4467 
4468  /* remove all variables that are fixed to one; merge multiple entries of the same variable;
4469  * fix resultant to zero if a pair of negated variables is contained in the operand variables
4470  */
4471  if( !cutoff && !SCIPconsIsDeleted(cons) )
4472  {
4473  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs) );
4474 
4475  /* merge multiple occurances of variables or variables with their negated variables */
4476  SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, nfixedvars, nchgcoefs, ndelconss) );
4477  }
4478 
4479  if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
4480  {
4481  assert(consdata->nvars >= 1); /* otherwise, propagateCons() has deleted the constraint */
4482 
4483  /* if only one variable is left, the resultant has to be equal to this single variable */
4484  if( consdata->nvars == 1 )
4485  {
4486  SCIP_Bool redundant;
4487  SCIP_Bool aggregated;
4488 
4489  SCIPdebugMsg(scip, "AND-constraint <%s> has only one variable not fixed to 1.0\n", SCIPconsGetName(cons));
4490 
4491  assert(consdata->vars != NULL);
4492  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
4493  assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
4494 
4495  /* aggregate variables: resultant - operand == 0 */
4496  SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
4497  &cutoff, &redundant, &aggregated) );
4498  assert(redundant || SCIPdoNotAggr(scip));
4499 
4500  if( aggregated )
4501  {
4502  assert(redundant);
4503  (*naggrvars)++;
4504  }
4505 
4506  if( redundant )
4507  {
4508  /* delete constraint */
4509  SCIP_CALL( SCIPdelCons(scip, cons) );
4510  (*ndelconss)++;
4511  }
4512  }
4513  else if( !consdata->impladded )
4514  {
4515  int i;
4516 
4517  /* add implications: resultant == 1 -> all operands == 1 */
4518  for( i = 0; i < consdata->nvars && !cutoff; ++i )
4519  {
4520  int nimplbdchgs;
4521 
4522  SCIP_CALL( SCIPaddVarImplication(scip, consdata->resvar, TRUE, consdata->vars[i],
4523  SCIP_BOUNDTYPE_LOWER, 1.0, &cutoff, &nimplbdchgs) );
4524  (*nchgbds) += nimplbdchgs;
4525  }
4526  consdata->impladded = TRUE;
4527  }
4528 
4529  /* if in r = x and y, the resultant is fixed to zero, add implication x = 1 -> y = 0 */
4530  if( !cutoff && SCIPconsIsActive(cons) && consdata->nvars == 2 && !consdata->opimpladded
4531  && SCIPvarGetUbGlobal(consdata->resvar) < 0.5 )
4532  {
4533  int nimplbdchgs;
4534 
4535  SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], TRUE, consdata->vars[1],
4536  SCIP_BOUNDTYPE_UPPER, 0.0, &cutoff, &nimplbdchgs) );
4537  (*nchgbds) += nimplbdchgs;
4538  consdata->opimpladded = TRUE;
4539  }
4540  }
4541  }
4542 
4543  /* perform dual presolving on AND-constraints */
4544  if( conshdlrdata->dualpresolving && !cutoff && !SCIPisStopped(scip) && SCIPallowDualReds(scip))
4545  {
4546  SCIP_CALL( dualPresolve(scip, conss, nconss, conshdlrdata->eventhdlr, &entries, &nentries, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, nupgdconss, naddconss) );
4547  }
4548 
4549  /* check for cliques inside the AND constraint */
4550  if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4551  {
4552  for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4553  {
4554  if( SCIPconsIsActive(conss[c]) )
4555  {
4556  /* check if at least two operands are in one clique */
4557  SCIP_CALL( cliquePresolve(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, naddconss) );
4558  }
4559  }
4560  }
4561 
4562  /* process pairs of constraints: check them for equal operands in order to aggregate resultants;
4563  * only apply this expensive procedure, if the single constraint preprocessing did not find any reductions
4564  * (otherwise, we delay the presolving to be called again next time)
4565  */
4566  if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4567  {
4568  if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4569  {
4570  if( firstchange < nconss )
4571  {
4572  /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
4573  SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, &cutoff, naggrvars, ndelconss) );
4574  oldnaggrvars = *naggrvars;
4575  }
4576  }
4577  }
4578 
4579  if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4580  {
4581  if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4582  {
4583  SCIP_Longint npaircomparisons;
4584  npaircomparisons = 0;
4585  oldndelconss = *ndelconss;
4586 
4587  for( c = firstchange; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4588  {
4589  if( SCIPconsIsActive(conss[c]) && !SCIPconsIsModifiable(conss[c]) )
4590  {
4591  npaircomparisons += ((SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange));
4592 
4593  SCIP_CALL( preprocessConstraintPairs(scip, conss, firstchange, c, &cutoff, naggrvars, nchgbds,
4594  ndelconss) );
4595 
4596  if( npaircomparisons > NMINCOMPARISONS )
4597  {
4598  if( ((*ndelconss - oldndelconss) + (*naggrvars - oldnaggrvars) + (*nchgbds - oldnchgbds)/2.0) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
4599  break;
4600  oldndelconss = *ndelconss;
4601  oldnaggrvars = *naggrvars;
4602  oldnchgbds = *nchgbds;
4603 
4604  npaircomparisons = 0;
4605  }
4606  }
4607  }
4608  }
4609  }
4610 
4611  SCIPfreeBufferArray(scip, &entries);
4612 
4613  /* return the correct result code */
4614  if( cutoff )
4615  *result = SCIP_CUTOFF;
4616  else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds
4617  || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4618  *result = SCIP_SUCCESS;
4619  else
4620  *result = SCIP_DIDNOTFIND;
4621 
4622  return SCIP_OKAY;
4623 }
4624 
4625 
4626 /** propagation conflict resolving method of constraint handler */
4627 static
4628 SCIP_DECL_CONSRESPROP(consRespropAnd)
4629 { /*lint --e{715}*/
4630  SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
4631 
4632  return SCIP_OKAY;
4633 }
4634 
4635 
4636 /** variable rounding lock method of constraint handler */
4637 static
4638 SCIP_DECL_CONSLOCK(consLockAnd)
4639 { /*lint --e{715}*/
4640  SCIP_CONSDATA* consdata;
4641  int i;
4642 
4643  assert(locktype == SCIP_LOCKTYPE_MODEL);
4644 
4645  consdata = SCIPconsGetData(cons);
4646  assert(consdata != NULL);
4647 
4648  /* resultant variable */
4649  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->resvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4650 
4651  /* operand variables */
4652  for( i = 0; i < consdata->nvars; ++i )
4653  {
4654  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4655  }
4656 
4657  return SCIP_OKAY;
4658 }
4659 
4660 
4661 /** constraint display method of constraint handler */
4662 static
4663 SCIP_DECL_CONSPRINT(consPrintAnd)
4664 { /*lint --e{715}*/
4665  assert( scip != NULL );
4666  assert( conshdlr != NULL );
4667  assert( cons != NULL );
4668 
4669  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file) );
4670 
4671  return SCIP_OKAY;
4672 }
4673 
4674 /** constraint copying method of constraint handler */
4675 static
4676 SCIP_DECL_CONSCOPY(consCopyAnd)
4677 { /*lint --e{715}*/
4678  SCIP_VAR** sourcevars;
4679  SCIP_VAR** vars;
4680  SCIP_VAR* sourceresvar;
4681  SCIP_VAR* resvar;
4682  const char* consname;
4683  int nvars;
4684  int v;
4685 
4686  assert(valid != NULL);
4687  (*valid) = TRUE;
4688 
4689  sourceresvar = SCIPgetResultantAnd(sourcescip, sourcecons);
4690 
4691  /* map resultant to active variable of the target SCIP */
4692  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceresvar, &resvar, varmap, consmap, global, valid) );
4693  assert(!(*valid) || resvar != NULL);
4694 
4695  /* we do not copy, if a variable is missing */
4696  if( !(*valid) )
4697  return SCIP_OKAY;
4698 
4699  /* map operand variables to active variables of the target SCIP */
4700  sourcevars = SCIPgetVarsAnd(sourcescip, sourcecons);
4701  nvars = SCIPgetNVarsAnd(sourcescip, sourcecons);
4702 
4703  if( nvars == -1 )
4704  return SCIP_INVALIDCALL;
4705 
4706  /* allocate buffer array */
4707  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4708 
4709  for( v = 0; v < nvars; ++v )
4710  {
4711  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
4712  assert(!(*valid) || vars[v] != NULL);
4713 
4714  /* we do not copy, if a variable is missing */
4715  if( !(*valid) )
4716  goto TERMINATE;
4717  }
4718 
4719  if( name != NULL )
4720  consname = name;
4721  else
4722  consname = SCIPconsGetName(sourcecons);
4723 
4724  /* creates and captures a AND-constraint */
4725  SCIP_CALL( SCIPcreateConsAnd(scip, cons, consname, resvar, nvars, vars,
4726  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4727 
4728  TERMINATE:
4729  /* free buffer array */
4730  SCIPfreeBufferArray(scip, &vars);
4731 
4732  return SCIP_OKAY;
4733 }
4734 
4735 /** constraint parsing method of constraint handler */
4736 static
4737 SCIP_DECL_CONSPARSE(consParseAnd)
4738 { /*lint --e{715}*/
4739  SCIP_VAR** vars;
4740  SCIP_VAR* resvar;
4741  char* endptr;
4742  int requiredsize;
4743  int varssize;
4744  int nvars;
4745 
4746  SCIPdebugMsg(scip, "parse <%s> as AND-constraint\n", str);
4747 
4748  *success = FALSE;
4749 
4750  /* parse variable name of resultant */
4751  SCIP_CALL( SCIPparseVarName(scip, str, &resvar, &endptr) );
4752  str = endptr;
4753 
4754  if( resvar == NULL )
4755  {
4756  SCIPdebugMsg(scip, "resultant variable does not exist \n");
4757  }
4758  else
4759  {
4760  char* strcopy = NULL;
4761  char* startptr;
4762 
4763  /* cutoff "== and(" form the constraint string */
4764  startptr = strchr((char*)str, '(');
4765 
4766  if( startptr == NULL )
4767  {
4768  SCIPerrorMessage("missing starting character '(' parsing AND-constraint\n");
4769  return SCIP_OKAY;
4770  }
4771 
4772  /* skip '(' */
4773  ++startptr;
4774 
4775  /* find end character ')' */
4776  endptr = strrchr(startptr, ')');
4777 
4778  if( endptr == NULL )
4779  {
4780  SCIPerrorMessage("missing ending character ')' parsing AND-constraint\n");
4781  return SCIP_OKAY;
4782  }
4783  assert(endptr >= startptr);
4784 
4785  if( endptr > startptr )
4786  {
4787  /* copy string for parsing */
4788  SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, startptr, (int)(endptr-startptr)) );
4789 
4790  varssize = 100;
4791  nvars = 0;
4792 
4793  /* allocate buffer array for variables */
4794  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
4795 
4796  /* parse string */
4797  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4798 
4799  if( *success )
4800  {
4801  /* check if the size of the variable array was great enough */
4802  if( varssize < requiredsize )
4803  {
4804  /* reallocate memory */
4805  varssize = requiredsize;
4806  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
4807 
4808  /* parse string again with the correct size of the variable array */
4809  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4810  }
4811 
4812  assert(*success);
4813  assert(varssize >= requiredsize);
4814 
4815  /* create AND-constraint */
4816  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
4817  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4818  }
4819 
4820  /* free variable buffer */
4821  SCIPfreeBufferArray(scip, &vars);
4822  SCIPfreeBufferArray(scip, &strcopy);
4823  }
4824  else
4825  {
4826  if( !modifiable )
4827  {
4828  SCIPerrorMessage("cannot create empty AND-constraint\n");
4829  return SCIP_OKAY;
4830  }
4831 
4832  /* create empty AND-constraint */
4833  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, 0, NULL,
4834  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4835 
4836  *success = TRUE;
4837  }
4838  }
4839 
4840  return SCIP_OKAY;
4841 }
4842 
4843 /** constraint method of constraint handler which returns the variables (if possible) */
4844 static
4845 SCIP_DECL_CONSGETVARS(consGetVarsAnd)
4846 { /*lint --e{715}*/
4847  SCIP_CONSDATA* consdata;
4848 
4849  consdata = SCIPconsGetData(cons);
4850  assert(consdata != NULL);
4851 
4852  if( varssize < consdata->nvars + 1 )
4853  (*success) = FALSE;
4854  else
4855  {
4856  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
4857  vars[consdata->nvars] = consdata->resvar;
4858  (*success) = TRUE;
4859  }
4860 
4861  return SCIP_OKAY;
4862 }
4863 
4864 /** constraint method of constraint handler which returns the number of variable (if possible) */
4865 static
4866 SCIP_DECL_CONSGETNVARS(consGetNVarsAnd)
4867 { /*lint --e{715}*/
4868  SCIP_CONSDATA* consdata;
4869 
4870  assert(cons != NULL);
4871 
4872  consdata = SCIPconsGetData(cons);
4873  assert(consdata != NULL);
4874 
4875  (*nvars) = consdata->nvars + 1;
4876  (*success) = TRUE;
4877 
4878  return SCIP_OKAY;
4879 }
4880 
4881 
4882 /*
4883  * Callback methods of event handler
4884  */
4885 
4886 static
4887 SCIP_DECL_EVENTEXEC(eventExecAnd)
4888 { /*lint --e{715}*/
4889  SCIP_CONSDATA* consdata;
4890 
4891  assert(eventhdlr != NULL);
4892  assert(eventdata != NULL);
4893  assert(event != NULL);
4894 
4895  consdata = (SCIP_CONSDATA*)eventdata;
4896  assert(consdata != NULL);
4897 
4898  /* check, if the variable was fixed to zero */
4900  consdata->nofixedzero = FALSE;
4901 
4902  consdata->propagated = FALSE;
4903 
4904  return SCIP_OKAY;
4905 }
4906 
4907 
4908 /*
4909  * constraint specific interface methods
4910  */
4911 
4912 /** creates the handler for AND-constraints and includes it in SCIP */
4914  SCIP* scip /**< SCIP data structure */
4915  )
4916 {
4917  SCIP_CONSHDLRDATA* conshdlrdata;
4918  SCIP_CONSHDLR* conshdlr;
4919  SCIP_EVENTHDLR* eventhdlr;
4920 
4921  /* create event handler for events on variables */
4923  eventExecAnd, NULL) );
4924 
4925  /* create constraint handler data */
4926  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
4927 
4928  /* include constraint handler */
4931  consEnfolpAnd, consEnfopsAnd, consCheckAnd, consLockAnd,
4932  conshdlrdata) );
4933 
4934  assert(conshdlr != NULL);
4935 
4936  /* set non-fundamental callbacks via specific setter functions */
4937  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyAnd, consCopyAnd) );
4938  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteAnd) );
4939 #ifdef GMLGATEPRINTING
4940  SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreAnd) );
4941 #endif
4942  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolAnd) );
4943  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeAnd) );
4944  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsAnd) );
4945  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsAnd) );
4946  SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreAnd) );
4947  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpAnd) );
4948  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseAnd) );
4949  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolAnd, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
4950  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintAnd) );
4951  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropAnd, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
4953  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropAnd) );
4954  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpAnd, consSepasolAnd, CONSHDLR_SEPAFREQ,
4956  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransAnd) );
4957  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxAnd) );
4958 
4959  /* add AND-constraint handler parameters */
4961  "constraints/" CONSHDLR_NAME "/presolpairwise",
4962  "should pairwise constraint comparison be performed in presolving?",
4963  &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
4965  "constraints/and/presolusehashing",
4966  "should hash table be used for detecting redundant constraints in advance",
4967  &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
4969  "constraints/" CONSHDLR_NAME "/linearize",
4970  "should the AND-constraint get linearized and removed (in presolving)?",
4971  &conshdlrdata->linearize, TRUE, DEFAULT_LINEARIZE, NULL, NULL) );
4973  "constraints/" CONSHDLR_NAME "/enforcecuts",
4974  "should cuts be separated during LP enforcing?",
4975  &conshdlrdata->enforcecuts, TRUE, DEFAULT_ENFORCECUTS, NULL, NULL) );
4977  "constraints/" CONSHDLR_NAME "/aggrlinearization",
4978  "should an aggregated linearization be used?",
4979  &conshdlrdata->aggrlinearization, TRUE, DEFAULT_AGGRLINEARIZATION, NULL, NULL) );
4981  "constraints/" CONSHDLR_NAME "/upgraderesultant",
4982  "should all binary resultant variables be upgraded to implicit binary variables?",
4983  &conshdlrdata->upgrresultant, TRUE, DEFAULT_UPGRRESULTANT, NULL, NULL) );
4985  "constraints/" CONSHDLR_NAME "/dualpresolving",
4986  "should dual presolving be performed?",
4987  &conshdlrdata->dualpresolving, TRUE, DEFAULT_DUALPRESOLVING, NULL, NULL) );
4988 
4989  if( SCIPfindConshdlr(scip, "nonlinear") != NULL )
4990  {
4991  /* include the AND-constraint upgrade in the nonlinear constraint handler */
4993  }
4994 
4995  return SCIP_OKAY;
4996 }
4997 
4998 /** creates and captures a AND-constraint
4999  *
5000  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5001  */
5003  SCIP* scip, /**< SCIP data structure */
5004  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5005  const char* name, /**< name of constraint */
5006  SCIP_VAR* resvar, /**< resultant variable of the operation */
5007  int nvars, /**< number of operator variables in the constraint */
5008  SCIP_VAR** vars, /**< array with operator variables of constraint */
5009  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5010  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5011  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5012  * Usually set to TRUE. */
5013  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5014  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5015  SCIP_Bool check, /**< should the constraint be checked for feasibility?
5016  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5017  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5018  * Usually set to TRUE. */
5019  SCIP_Bool local, /**< is constraint only valid locally?
5020  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5021  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5022  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5023  * adds coefficients to this constraint. */
5024  SCIP_Bool dynamic, /**< is constraint subject to aging?
5025  * Usually set to FALSE. Set to TRUE for own cuts which
5026  * are separated as constraints. */
5027  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5028  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5029  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5030  * if it may be moved to a more global node?
5031  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5032  )
5033 {
5034  SCIP_CONSHDLR* conshdlr;
5035  SCIP_CONSHDLRDATA* conshdlrdata;
5036  SCIP_CONSDATA* consdata;
5037  SCIP_Bool infeasible;
5038 
5039  /* find the AND-constraint handler */
5040  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5041  if( conshdlr == NULL )
5042  {
5043  SCIPerrorMessage("AND-constraint handler not found\n");
5044  return SCIP_PLUGINNOTFOUND;
5045  }
5046 
5047  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5048  assert(conshdlrdata != NULL);
5049 
5050  /* upgrade binary resultant variable to an implicit binary variable */
5051  /* @todo add implicit upgrade in presolving, improve decision making for upgrade by creating an implication graph */
5052  if( conshdlrdata->upgrresultant && SCIPvarGetType(resvar) == SCIP_VARTYPE_BINARY
5053 #if 1 /* todo delete following hack,
5054  * the following avoids upgrading not artificial variables, for example and-resultants which are generated
5055  * from the gate presolver, it seems better to not upgrade these variables
5056  */
5057  && strlen(SCIPvarGetName(resvar)) > strlen(ARTIFICIALVARNAMEPREFIX) && strncmp(SCIPvarGetName(resvar), ARTIFICIALVARNAMEPREFIX, strlen(ARTIFICIALVARNAMEPREFIX)) == 0 )
5058 #else
5059  )
5060 #endif
5061  {
5062  SCIP_VAR* activeresvar;
5063  SCIP_VAR* activevar;
5064  int v;
5065 
5066  if( SCIPisTransformed(scip) )
5067  activeresvar = SCIPvarGetProbvar(resvar);
5068  else
5069  activeresvar = resvar;
5070 
5071  if( SCIPvarGetType(activeresvar) == SCIP_VARTYPE_BINARY )
5072  {
5073  /* check if we can upgrade the variable type of the resultant */
5074  for( v = nvars - 1; v >= 0; --v )
5075  {
5076  if( SCIPisTransformed(scip) )
5077  activevar = SCIPvarGetProbvar(vars[v]);
5078  else
5079  activevar = vars[v];
5080 
5081  if( activevar == activeresvar || SCIPvarGetType(activevar) == SCIP_VARTYPE_IMPLINT )
5082  break;
5083  }
5084 
5085  /* upgrade the type of the resultant */
5086  if( v < 0 )
5087  {
5088  SCIP_CALL( SCIPchgVarType(scip, resvar, SCIP_VARTYPE_IMPLINT, &infeasible) );
5089  assert(!infeasible);
5090  }
5091  }
5092  }
5093 
5094  /* create constraint data */
5095  SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, resvar, FALSE, FALSE) );
5096 
5097  /* create constraint */
5098  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5099  local, modifiable, dynamic, removable, stickingatnode) );
5100 
5101  return SCIP_OKAY;
5102 }
5103 
5104 /** creates and captures an AND-constraint
5105  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
5106  * method SCIPcreateConsAnd(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
5107  *
5108  * @see SCIPcreateConsAnd() for information about the basic constraint flag configuration
5109  *
5110  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5111  */
5113  SCIP* scip, /**< SCIP data structure */
5114  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5115  const char* name, /**< name of constraint */
5116  SCIP_VAR* resvar, /**< resultant variable of the operation */
5117  int nvars, /**< number of operator variables in the constraint */
5118  SCIP_VAR** vars /**< array with operator variables of constraint */
5119  )
5120 {
5121  assert(scip != NULL);
5122 
5123  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
5124  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
5125 
5126  return SCIP_OKAY;
5127 }
5128 
5129 
5130 /** gets number of variables in AND-constraint */
5131 int SCIPgetNVarsAnd(
5132  SCIP* scip, /**< SCIP data structure */
5133  SCIP_CONS* cons /**< constraint data */
5134  )
5135 {
5136  SCIP_CONSDATA* consdata;
5137 
5138  assert(scip != NULL);
5139  assert(cons != NULL);
5140 
5141  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5142  {
5143  SCIPerrorMessage("constraint is not an AND-constraint\n");
5144  SCIPABORT();
5145  return -1; /*lint !e527*/
5146  }
5147 
5148  consdata = SCIPconsGetData(cons);
5149  assert(consdata != NULL);
5150 
5151  return consdata->nvars;
5152 }
5153 
5154 /** gets array of variables in AND-constraint */
5156  SCIP* scip, /**< SCIP data structure */
5157  SCIP_CONS* cons /**< constraint data */
5158  )
5159 {
5160  SCIP_CONSDATA* consdata;
5161 
5162  assert(scip != NULL);
5163  assert(cons != NULL);
5164 
5165  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5166  {
5167  SCIPerrorMessage("constraint is not an AND-constraint\n");
5168  SCIPABORT();
5169  return NULL; /*lint !e527*/
5170  }
5171 
5172  consdata = SCIPconsGetData(cons);
5173  assert(consdata != NULL);
5174 
5175  return consdata->vars;
5176 }
5177 
5178 
5179 /** gets the resultant variable in AND-constraint */
5181  SCIP* scip, /**< SCIP data structure */
5182  SCIP_CONS* cons /**< constraint data */
5183  )
5184 {
5185  SCIP_CONSDATA* consdata;
5186 
5187  assert(cons != NULL);
5188 
5189  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5190  {
5191  SCIPerrorMessage("constraint is not an AND-constraint\n");
5192  SCIPABORT();
5193  return NULL; /*lint !e527*/
5194  }
5195 
5196  consdata = SCIPconsGetData(cons);
5197  assert(consdata != NULL);
5198 
5199  return consdata->resvar;
5200 }
5201 
5202 /** return if the variables of the AND-constraint are sorted with respect to their indices */
5204  SCIP* scip, /**< SCIP data structure */
5205  SCIP_CONS* cons /**< constraint data */
5206  )
5207 {
5208  SCIP_CONSDATA* consdata;
5209 
5210  assert(scip != NULL);
5211  assert(cons != NULL);
5212 
5213  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5214  {
5215  SCIPerrorMessage("constraint is not an AND-constraint\n");
5216  SCIPABORT();
5217  return FALSE; /*lint !e527*/
5218  }
5219 
5220  consdata = SCIPconsGetData(cons);
5221  assert(consdata != NULL);
5222 
5223  return consdata->sorted;
5224 }
5225 
5226 /** sort the variables of the AND-constraint with respect to their indices */
5228  SCIP* scip, /**< SCIP data structure */
5229  SCIP_CONS* cons /**< constraint data */
5230  )
5231 {
5232  SCIP_CONSDATA* consdata;
5233 
5234  assert(scip != NULL);
5235  assert(cons != NULL);
5236 
5237  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5238  {
5239  SCIPerrorMessage("constraint is not an AND-constraint\n");
5240  SCIPABORT();
5241  return SCIP_INVALIDDATA; /*lint !e527*/
5242  }
5243 
5244  consdata = SCIPconsGetData(cons);
5245  assert(consdata != NULL);
5246 
5247  consdataSort(consdata);
5248  assert(consdata->sorted);
5249 
5250  return SCIP_OKAY;
5251 }
5252 
5253 /** when 'upgrading' the given AND-constraint, should the check flag for the upgraded constraint be set to TRUE, even if
5254  * the check flag of this AND-constraint is set to FALSE?
5255  */
5257  SCIP* scip, /**< SCIP data structure */
5258  SCIP_CONS* cons, /**< constraint data */
5259  SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be checked,
5260  * even if the check flag of the AND-constraint is set to FALSE
5261  */
5262  )
5263 {
5264  SCIP_CONSDATA* consdata;
5265 
5266  assert(scip != NULL);
5267  assert(cons != NULL);
5268 
5269  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5270  {
5271  SCIPerrorMessage("constraint is not an AND-constraint\n");
5272  SCIPABORT();
5273  return SCIP_INVALIDDATA; /*lint !e527*/
5274  }
5275 
5276  consdata = SCIPconsGetData(cons);
5277  assert(consdata != NULL);
5278 
5279  consdata->checkwhenupgr = flag;
5280 
5281  return SCIP_OKAY;
5282 }
5283 
5284 /** when 'upgrading' the given AND-constraint, should the removable flag for the upgraded constraint be set to FALSE,
5285  * even if the removable flag of this AND-constraint is set to TRUE?
5286  */
5288  SCIP* scip, /**< SCIP data structure */
5289  SCIP_CONS* cons, /**< constraint data */
5290  SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be not
5291  * removable, even if the removable flag of the AND-constraint is set to
5292  * TRUE
5293  */
5294  )
5295 {
5296  SCIP_CONSDATA* consdata;
5297 
5298  assert(scip != NULL);
5299  assert(cons != NULL);
5300 
5301  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5302  {
5303  SCIPerrorMessage("constraint is not an AND-constraint\n");
5304  SCIPABORT();
5305  return SCIP_INVALIDDATA; /*lint !e527*/
5306  }
5307 
5308  consdata = SCIPconsGetData(cons);
5309  assert(consdata != NULL);
5310 
5311  consdata->notremovablewhenupgr = flag;
5312 
5313  return SCIP_OKAY;
5314 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition: scip_lp.c:1674
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:202
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4221
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2134
static SCIP_RETCODE consdataFixResultantZero(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *resvar, int pos, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1260
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1798
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:105
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_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:640
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:213
#define ARTIFICIALVARNAMEPREFIX
SCIP_RETCODE SCIPincludeNonlinconsUpgrade(SCIP *scip, SCIP_DECL_NONLINCONSUPGD((*nonlinconsupgd)), SCIP_DECL_EXPRGRAPHNODEREFORM((*nodereform)), int priority, SCIP_Bool active, const char *conshdlrname)
#define NULL
Definition: def.h:239
static SCIP_DECL_CONSSEPASOL(consSepasolAnd)
Definition: cons_and.c:4294
SCIP_RETCODE SCIPexprgraphAddNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int mindepth, int nchildren, SCIP_EXPRGRAPHNODE **children)
Definition: expr.c:15173
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:10958
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
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
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2130
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3176
SCIP_RETCODE SCIPexprgraphAddVars(SCIP_EXPRGRAPH *exprgraph, int nvars, void **vars, SCIP_EXPRGRAPHNODE **varnodes)
Definition: expr.c:15257
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:412
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8335
#define CONSHDLR_SEPAPRIORITY
Definition: cons_and.c:72
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:663
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip_var.c:1600
static SCIP_DECL_EVENTEXEC(eventExecAnd)
Definition: cons_and.c:4888
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1994
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2265
public methods for memory management
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:422
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:954
int SCIPexprgraphGetNodeNChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12967
SCIP_RETCODE SCIPsortAndCons(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5228
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
static SCIP_DECL_CONSENFORELAX(consEnforelaxAnd)
Definition: cons_and.c:4330
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:893
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:11789
#define SCIP_MAXSTRLEN
Definition: def.h:260
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3233
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
public methods for conflict handler plugins and conflict analysis
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:627
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:385
static SCIP_RETCODE analyzeConflictZero(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:1224
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1826
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2895
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:210
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1602
static SCIP_RETCODE consdataSwitchWatchedvars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
Definition: cons_and.c:336
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:393
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPconsIsAdded(SCIP_CONS *cons)
Definition: cons.c:8505
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:172
static SCIP_DECL_HASHKEYEQ(hashKeyEqAndcons)
Definition: cons_and.c:3281
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:485
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1442
static SCIP_DECL_CONSPARSE(consParseAnd)
Definition: cons_and.c:4738
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip_cons.c:1538
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:523
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16909
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:554
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
void SCIPgmlWriteClosing(FILE *file)
Definition: misc.c:687
static SCIP_RETCODE consdataFixOperandsOne(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1299
static SCIP_RETCODE consdataFreeRows(SCIP *scip, SCIP_CONSDATA *consdata)
Definition: cons_and.c:502
#define DEFAULT_PRESOLUSEHASHING
Definition: cons_and.c:99
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1918
#define FALSE
Definition: def.h:65
int SCIPconsGetPos(SCIP_CONS *cons)
Definition: cons.c:8086
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
SCIP_RETCODE SCIPincludeConshdlrAnd(SCIP *scip)
Definition: cons_and.c:4914
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10325
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:243
#define CONSHDLR_CHECKPRIORITY
Definition: cons_and.c:74
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:501
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:64
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
enum Proprule PROPRULE
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8355
static SCIP_DECL_CONSPROP(consPropAnd)
Definition: cons_and.c:4383
#define SCIP_PRESOLTIMING_EXHAUSTIVE
Definition: type_timing.h:45
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17036
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
Definition: cons_and.c:577
#define CONSHDLR_NAME
Definition: cons_and.c:70
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8385
public methods for problem variables
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
static SCIP_RETCODE consdataLinearize(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nfixedvars, int *nupgdconss)
Definition: cons_and.c:1353
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
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:297
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:138
#define DEFAULT_ENFORCECUTS
Definition: cons_and.c:93
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_and.c:188
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_CONSPRINT(consPrintAnd)
Definition: cons_and.c:4664
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:611
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num)
Definition: cons_and.c:396
public methods for SCIP variables
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8345
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition: type_event.h:108
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:686
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:177
#define SCIPdebugMsgPrint
Definition: scip_message.h:89
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1483
static SCIP_RETCODE consdataDropWatchedEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int filterpos)
Definition: cons_and.c:261
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:870
static SCIP_DECL_CONSEXITSOL(consExitsolAnd)
Definition: cons_and.c:4184
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8137
#define EVENTHDLR_DESC
Definition: cons_and.c:89
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
#define DEFAULT_PRESOLPAIRWISE
Definition: cons_and.c:91
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2224
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:1011
int SCIPexprgraphGetNodePolynomialNMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13190
public methods for numerical tolerances
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2014
public methods for expressions, expression trees, expression graphs, and related stuff ...
#define SCIP_REAL_FORMAT
Definition: def.h:153
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
SCIP_Bool SCIPisAndConsSorted(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5204
static SCIP_DECL_CONSENFOPS(consEnfopsAnd)
Definition: cons_and.c:4339
int SCIPexprGetMonomialNFactors(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5910
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17159
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17080
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4199
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:64
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
public methods for the branch-and-bound tree
SCIP_EXPROP SCIPexprgraphGetNodeOperator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13027
SCIP_EXPRDATA_MONOMIAL ** SCIPexprgraphGetNodePolynomialMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13178
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8072
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17353
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11697
static SCIP_DECL_CONSFREE(consFreeAnd)
Definition: cons_and.c:3887
#define EVENTHDLR_NAME
Definition: cons_and.c:88
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:111
public methods for managing constraints
static SCIP_DECL_CONSPRESOL(consPresolAnd)
Definition: cons_and.c:4418
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:600
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5156
SCIP_Real SCIPexprgraphGetNodePolynomialConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13202
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:409
#define CONSHDLR_PRESOLTIMING
Definition: cons_and.c:85
SCIP_RETCODE SCIPgetBinvarRepresentatives(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **repvars, SCIP_Bool *negated)
Definition: scip_var.c:1647
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:3352
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:5003
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
#define CONSHDLR_PROP_TIMING
Definition: cons_and.c:86
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5181
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3527
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
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_RETCODE SCIPaddVarImplication(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype, SCIP_Real implbound, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6691
static SCIP_DECL_CONSDELETE(consDeleteAnd)
Definition: cons_and.c:4204
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:128
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4375
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8076
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
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8514
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8295
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
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 SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:434
SCIP_RETCODE SCIPcreateConsBasicAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars)
Definition: cons_and.c:5113
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4211
static SCIP_DECL_CONSTRANS(consTransAnd)
Definition: cons_and.c:4219
#define REALABS(x)
Definition: def.h:174
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:66
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:13434
#define DEFAULT_LINEARIZE
Definition: cons_and.c:92
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPvarGetAggregatedObj(SCIP_VAR *var, SCIP_Real *aggrobj)
Definition: var.c:17213
#define SCIP_CALL(x)
Definition: def.h:351
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:474
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:63
enum Proprule PROPRULE
Definition: cons_and.c:165
SCIP_RETCODE SCIPchgAndConsRemovableFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition: cons_and.c:5288
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars, int *nupgdconss)
Definition: cons_and.c:1682
Definition: grphload.c:88
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8315
#define EXPRGRAPHREFORM_PRIORITY
Definition: cons_and.c:102
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:294
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:709
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:268
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:51
public methods for constraint handler plugins and constraints
static SCIP_DECL_CONSINITLP(consInitlpAnd)
Definition: cons_and.c:4249
static SCIP_RETCODE conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_and.c:222
static SCIP_DECL_CONSGETVARS(consGetVarsAnd)
Definition: cons_and.c:4846
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:533
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
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
public data structures and miscellaneous methods
SCIP_RETCODE SCIPchgAndConsCheckFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition: cons_and.c:5257
#define SCIP_Bool
Definition: def.h:62
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
Definition: cons_and.c:602
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2179
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
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
#define CONSHDLR_NEEDSCONS
Definition: cons_and.c:83
static SCIP_DECL_CONSCOPY(consCopyAnd)
Definition: cons_and.c:4677
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1336
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
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:715
constraint handler for nonlinear constraints
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2550