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-2019 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  /* coverity[swapped_arguments] */
3440  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
3441 
3442  /* also take the check when upgrade flag over if necessary */
3443  consdata1->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3444  consdata1->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3445 
3446  SCIP_CALL( SCIPdelCons(scip, cons0) );
3447  (*ndelconss)++;
3448  }
3449 
3450  /* update the first changed constraint to begin the next aggregation round with */
3451  if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
3452  *firstchange = SCIPconsGetPos(cons1);
3453 
3454  assert(SCIPconsIsActive(cons1));
3455  }
3456  else
3457  {
3458  /* no such constraint in current hash table: insert cons0 into hash table */
3459  SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
3460  }
3461  }
3462  TERMINATE:
3463  /* free hash table */
3464  SCIPhashtableFree(&hashtable);
3465 
3466  return SCIP_OKAY;
3467 }
3468 
3469 /** helper function to enforce constraints */
3470 static
3472  SCIP* scip, /**< SCIP data structure */
3473  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3474  SCIP_CONS** conss, /**< constraints to process */
3475  int nconss, /**< number of constraints */
3476  SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
3477  SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
3478  )
3479 {
3480  SCIP_CONSHDLRDATA* conshdlrdata;
3481  SCIP_Bool separated;
3482  SCIP_Bool violated;
3483  SCIP_Bool cutoff;
3484  int i;
3485 
3486  separated = FALSE;
3487 
3488  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3489  assert(conshdlrdata != NULL);
3490 
3491  /* method is called only for integral solutions, because the enforcing priority is negative */
3492  for( i = 0; i < nconss; i++ )
3493  {
3494  SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, FALSE, &violated) );
3495  if( violated )
3496  {
3497  if( conshdlrdata->enforcecuts )
3498  {
3499  SCIP_Bool consseparated;
3500 
3501  SCIP_CALL( separateCons(scip, conss[i], sol, &consseparated, &cutoff) );
3502  if ( cutoff )
3503  {
3504  *result = SCIP_CUTOFF;
3505  return SCIP_OKAY;
3506  }
3507  separated = separated || consseparated;
3508 
3509  /* following assert is wrong in the case some variables were not in relaxation (dynamic columns),
3510  *
3511  * e.g. the resultant, which has a negative objective value, is in the relaxation solution on its upper bound
3512  * (variables with status loose are in an relaxation solution on it's best bound), but already creating a
3513  * row, and thereby creating the column, changes the solution value (variable than has status column, and the
3514  * initialization sets the relaxation solution value) to 0.0, and this already could lead to no violation of
3515  * the rows, which then are not seperated into the lp
3516  */
3517 #ifdef SCIP_DISABLED_CODE
3518  assert(consseparated); /* because the solution is integral, the separation always finds a cut */
3519 #endif
3520  }
3521  else
3522  {
3523  *result = SCIP_INFEASIBLE;
3524  return SCIP_OKAY;
3525  }
3526  }
3527  }
3528 
3529  if( separated )
3530  *result = SCIP_SEPARATED;
3531  else
3532  *result = SCIP_FEASIBLE;
3533 
3534  return SCIP_OKAY;
3535 }
3536 
3537 
3538 /** compares constraint with all prior constraints for possible redundancy or aggregation,
3539  * and removes or changes constraint accordingly
3540  */
3541 static
3543  SCIP* scip, /**< SCIP data structure */
3544  SCIP_CONS** conss, /**< constraint set */
3545  int firstchange, /**< first constraint that changed since last pair preprocessing round */
3546  int chkind, /**< index of constraint to check against all prior indices upto startind */
3547  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3548  int* naggrvars, /**< pointer to count number of aggregated variables */
3549  int* nbdchgs, /**< pointer to count the number of performed bound changes, or NULL */
3550  int* ndelconss /**< pointer to count number of deleted constraints */
3551  )
3552 {
3553  SCIP_CONS* cons0;
3554  SCIP_CONSDATA* consdata0;
3555  SCIP_Bool cons0changed;
3556  int c;
3557 
3558  assert(conss != NULL);
3559  assert(firstchange <= chkind);
3560  assert(cutoff != NULL);
3561  assert(naggrvars != NULL);
3562  assert(nbdchgs != NULL);
3563  assert(ndelconss != NULL);
3564 
3565  /* get the constraint to be checked against all prior constraints */
3566  cons0 = conss[chkind];
3567  assert(SCIPconsIsActive(cons0));
3568  assert(!SCIPconsIsModifiable(cons0));
3569 
3570  consdata0 = SCIPconsGetData(cons0);
3571 
3572  /* sort the constraint */
3573  consdataSort(consdata0);
3574 
3575  assert(consdata0->nvars >= 1);
3576  assert(consdata0->sorted);
3577 
3578  /* check constraint against all prior constraints */
3579  cons0changed = consdata0->changed;
3580 
3581  if( SCIPconsIsActive(cons0) )
3582  {
3583  for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff); ++c )
3584  {
3585  SCIP_CONS* cons1;
3586  SCIP_CONSDATA* consdata1;
3587  SCIP_Bool cons0superset;
3588  SCIP_Bool cons1superset;
3589  int v0;
3590  int v1;
3591 
3592  if( c % 1000 == 0 && SCIPisStopped(scip) )
3593  break;
3594 
3595  cons1 = conss[c];
3596 
3597  /* ignore inactive and modifiable constraints */
3598  if( !SCIPconsIsActive(cons1) || SCIPconsIsModifiable(cons1) )
3599  continue;
3600 
3601  consdata1 = SCIPconsGetData(cons1);
3602  assert(consdata1 != NULL);
3603 
3604 #ifdef SCIP_DISABLED_CODE
3605  SCIPdebugMsg(scip, "preprocess AND-constraint pair <%s>[chg:%d] and <%s>[chg:%d]\n",
3606  SCIPconsGetName(cons0), cons0changed, SCIPconsGetName(cons1), consdata1->changed);
3607 #endif
3608 
3609  /* if both constraints were not changed since last round, we can ignore the pair */
3610  if( !cons0changed && !consdata1->changed )
3611  continue;
3612 
3613  assert(consdata1->nvars >= 1);
3614 
3615  /* sort the constraint */
3616  consdataSort(consdata1);
3617  assert(consdata1->sorted);
3618 
3619  /* check consdata0 against consdata1:
3620  * - if they consist of the same operands, the resultants can be aggregated
3621  * - if one operand list is a subset of the other, add implication r0 = 1 -> r1 = 1, or r1 = 1 -> r0 = 1
3622  */
3623  v0 = 0;
3624  v1 = 0;
3625  cons0superset = TRUE;
3626  cons1superset = TRUE;
3627  while( (v0 < consdata0->nvars || v1 < consdata1->nvars) && (cons0superset || cons1superset) )
3628  {
3629  int varcmp;
3630 
3631  /* test, if variable appears in only one or in both constraints */
3632  if( v0 < consdata0->nvars && v1 < consdata1->nvars )
3633  varcmp = SCIPvarCompare(consdata0->vars[v0], consdata1->vars[v1]);
3634  else if( v0 < consdata0->nvars )
3635  varcmp = -1;
3636  else
3637  varcmp = +1;
3638 
3639  switch( varcmp )
3640  {
3641  case -1:
3642  /* variable doesn't appear in consdata1 */
3643  cons1superset = FALSE;
3644  v0++;
3645  break;
3646 
3647  case +1:
3648  /* variable doesn't appear in consdata0 */
3649  cons0superset = FALSE;
3650  v1++;
3651  break;
3652 
3653  case 0:
3654  /* variable appears in both constraints */
3655  v0++;
3656  v1++;
3657  break;
3658 
3659  default:
3660  SCIPerrorMessage("invalid comparison result\n");
3661  SCIPABORT();
3662  return SCIP_INVALIDDATA; /*lint !e527*/
3663  }
3664  }
3665 
3666  /* check for equivalence and domination */
3667  if( cons0superset && cons1superset )
3668  {
3669  SCIP_Bool infeasible;
3670  SCIP_Bool redundant;
3671  SCIP_Bool aggregated;
3672 
3673  /* constraints are equivalent */
3674  SCIPdebugMsg(scip, "equivalent AND-constraints <%s> and <%s>: aggregate resultants <%s> == <%s>\n",
3675  SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPvarGetName(consdata0->resvar),
3676  SCIPvarGetName(consdata1->resvar));
3677 
3678  /* aggregate resultants */
3679  SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3680  &infeasible, &redundant, &aggregated) );
3681  assert(redundant || SCIPdoNotAggr(scip));
3682 
3683  if( aggregated )
3684  {
3685  assert(redundant);
3686  (*naggrvars)++;
3687  }
3688 
3689  if( redundant )
3690  {
3691  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
3692  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
3693 
3694  /* also take the check when upgrade flag over if necessary */
3695  consdata0->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3696  consdata0->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3697 
3698  /* delete constraint */
3699  SCIP_CALL( SCIPdelCons(scip, cons1) );
3700  (*ndelconss)++;
3701  }
3702 
3703  *cutoff = *cutoff || infeasible;
3704  }
3705  else if( cons0superset )
3706  {
3707  SCIP_Bool infeasible;
3708  int nboundchgs;
3709 
3710  /* the conjunction of cons0 is a superset of the conjunction of cons1 */
3711  SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3712  SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPvarGetName(consdata0->resvar),
3713  SCIPvarGetName(consdata1->resvar));
3714 
3715  /* add implication */
3716  SCIP_CALL( SCIPaddVarImplication(scip, consdata0->resvar, TRUE, consdata1->resvar, SCIP_BOUNDTYPE_LOWER, 1.0,
3717  &infeasible, &nboundchgs) );
3718  *cutoff = *cutoff || infeasible;
3719  (*nbdchgs) += nboundchgs;
3720  }
3721  else if( cons1superset )
3722  {
3723  SCIP_Bool infeasible;
3724  int nboundchgs;
3725 
3726  /* the conjunction of cons1 is a superset of the conjunction of cons0 */
3727  SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3728  SCIPconsGetName(cons1), SCIPconsGetName(cons0), SCIPvarGetName(consdata1->resvar),
3729  SCIPvarGetName(consdata0->resvar));
3730 
3731  /* add implication */
3732  SCIP_CALL( SCIPaddVarImplication(scip, consdata1->resvar, TRUE, consdata0->resvar, SCIP_BOUNDTYPE_LOWER, 1.0,
3733  &infeasible, &nboundchgs) );
3734  *cutoff = *cutoff || infeasible;
3735  (*nbdchgs) += nboundchgs;
3736  }
3737  }
3738  }
3739  consdata0->changed = FALSE;
3740 
3741  return SCIP_OKAY;
3742 }
3743 
3744 /** tries to reformulate an expression graph node that is a product of binary variables via introducing an AND-constraint */
3745 static
3746 SCIP_DECL_EXPRGRAPHNODEREFORM(exprgraphnodeReformAnd)
3748  SCIP_EXPRGRAPHNODE* child;
3749  char name[SCIP_MAXSTRLEN];
3750  int nchildren;
3751  SCIP_CONS* cons;
3752  SCIP_VAR** vars;
3753  SCIP_VAR* var;
3754  int c;
3755 
3756  assert(scip != NULL);
3757  assert(exprgraph != NULL);
3758  assert(node != NULL);
3759  assert(naddcons != NULL);
3760  assert(reformnode != NULL);
3761 
3762  *reformnode = NULL;
3763 
3764  /* allow only products given as EXPR_PRODUCT or EXPR_POLYNOMIAL with only 1 monomial */
3767  )
3768  return SCIP_OKAY;
3769 
3770  nchildren = SCIPexprgraphGetNodeNChildren(node);
3771 
3772  /* for a polynomial with only one monomial, all children should appear as factors in the monomial
3773  * 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
3774  */
3776 
3777  /* check only products with at least 3 variables (2 variables are taken of by cons_quadratic) */
3778  if( nchildren <= 2 )
3779  return SCIP_OKAY;
3780 
3781  /* check if all factors correspond to binary variables, and if so, setup vars array */
3782  for( c = 0; c < nchildren; ++c )
3783  {
3784  child = SCIPexprgraphGetNodeChildren(node)[c];
3785 
3787  return SCIP_OKAY;
3788 
3789  var = (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, child);
3790  if( !SCIPvarIsBinary(var) )
3791  return SCIP_OKAY;
3792  }
3793 
3794  /* node corresponds to product of binary variables (maybe with coefficient and constant, if polynomial) */
3795  SCIPdebugMsg(scip, "reformulate node %p via AND-constraint\n", (void*)node);
3796 
3797  /* collect variables in product */
3798  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nchildren) );
3799  for( c = 0; c < nchildren; ++c )
3800  {
3801  child = SCIPexprgraphGetNodeChildren(node)[c];
3802  vars[c] = (SCIP_VAR*)SCIPexprgraphGetNodeVar(exprgraph, child);
3803  }
3804 
3805  /* create variable for resultant
3806  * cons_and wants to add implications for resultant, which is only possible for binary variables currently
3807  * so choose binary as vartype, even though implicit integer had been sufficient
3808  */
3809  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "nlreform%dand", *naddcons);
3810  SCIP_CALL( SCIPcreateVar(scip, &var, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
3811  TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) );
3812  SCIP_CALL( SCIPaddVar(scip, var) );
3813 
3814 #ifdef WITH_DEBUG_SOLUTION
3815  if( SCIPdebugIsMainscip(scip) )
3816  {
3817  SCIP_Bool debugval;
3818  SCIP_Real varval;
3819 
3820  debugval = TRUE;
3821  for( c = 0; c < nchildren; ++c )
3822  {
3823  SCIP_CALL( SCIPdebugGetSolVal(scip, vars[c], &varval) );
3824  debugval = debugval && (varval > 0.5);
3825  }
3826  SCIP_CALL( SCIPdebugAddSolVal(scip, var, debugval ? 1.0 : 0.0) );
3827  }
3828 #endif
3829 
3830  /* create AND-constraint */
3831  SCIP_CALL( SCIPcreateConsAnd(scip, &cons, name, var, nchildren, vars,
3832  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
3833  SCIP_CALL( SCIPaddCons(scip, cons) );
3834  SCIPdebugPrintCons(scip, cons, NULL);
3835  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3836  ++*naddcons;
3837 
3838  SCIPfreeBufferArray(scip, &vars);
3839 
3840  /* add var to exprgraph */
3841  SCIP_CALL( SCIPexprgraphAddVars(exprgraph, 1, (void**)&var, reformnode) );
3842  SCIP_CALL( SCIPreleaseVar(scip, &var) );
3843 
3844  /* if we have coefficient and constant, then replace reformnode by linear expression in reformnode */
3846  {
3847  SCIP_Real coef;
3848  SCIP_Real constant;
3849 
3851  constant = SCIPexprgraphGetNodePolynomialConstant(node);
3852 
3853  if( coef != 1.0 || constant != 0.0 )
3854  {
3855  SCIP_EXPRGRAPHNODE* linnode;
3856  SCIP_CALL( SCIPexprgraphCreateNodeLinear(SCIPblkmem(scip), &linnode, 1, &coef, constant) );
3857  SCIP_CALL( SCIPexprgraphAddNode(exprgraph, linnode, -1, 1, reformnode) );
3858  *reformnode = linnode;
3859  }
3860  }
3861 
3862  return SCIP_OKAY;
3863 }
3864 
3865 /*
3866  * Callback methods of constraint handler
3867  */
3868 
3869 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
3870 static
3871 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyAnd)
3872 { /*lint --e{715}*/
3873  assert(scip != NULL);
3874  assert(conshdlr != NULL);
3875  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3876 
3877  /* call inclusion method of constraint handler */
3879 
3880  *valid = TRUE;
3881 
3882  return SCIP_OKAY;
3883 }
3884 
3885 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
3886 static
3887 SCIP_DECL_CONSFREE(consFreeAnd)
3888 { /*lint --e{715}*/
3889  SCIP_CONSHDLRDATA* conshdlrdata;
3890 
3891  /* free constraint handler data */
3892  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3893  assert(conshdlrdata != NULL);
3894 
3895  SCIP_CALL( conshdlrdataFree(scip, &conshdlrdata) );
3896 
3897  SCIPconshdlrSetData(conshdlr, NULL);
3898 
3899  return SCIP_OKAY;
3900 }
3901 
3902 
3903 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
3904 static
3905 SCIP_DECL_CONSINITPRE(consInitpreAnd)
3906 { /*lint --e{715}*/
3907  SCIP_CONSHDLRDATA* conshdlrdata;
3908 
3909  assert( scip != NULL );
3910  assert( conshdlr != NULL );
3911  assert( nconss == 0 || conss != NULL );
3912 
3913  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3914  assert(conshdlrdata != NULL);
3915 
3916  if( conshdlrdata->linearize )
3917  {
3918  /* linearize all AND-constraints and remove the AND-constraints */
3919  SCIP_CONS* newcons;
3920  SCIP_CONS* cons;
3921  SCIP_CONSDATA* consdata;
3922  char consname[SCIP_MAXSTRLEN];
3923 
3924  SCIP_VAR** vars;
3925  SCIP_Real* vals;
3926 
3927  int nvars;
3928  int c, v;
3929 
3930  /* allocate buffer array */
3931  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
3932  SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
3933 
3934  for( c = 0; c < nconss; ++c )
3935  {
3936  cons = conss[c];
3937  assert( cons != NULL );
3938 
3939  /* only added constraints can be upgraded */
3940  if( !SCIPconsIsAdded(cons) )
3941  continue;
3942 
3943  consdata = SCIPconsGetData(cons);
3944  assert( consdata != NULL );
3945  assert( consdata->resvar != NULL );
3946 
3947  nvars = consdata->nvars;
3948 
3949  if( !conshdlrdata->aggrlinearization )
3950  {
3951  vars[0] = consdata->resvar;
3952  vals[0] = 1.0;
3953  vals[1] = -1.0;
3954 
3955  /* create operator linear constraints */
3956  for( v = 0; v < nvars; ++v )
3957  {
3958  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), v);
3959  vars[1] = consdata->vars[v];
3960 
3961  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, vars, vals, -SCIPinfinity(scip), 0.0,
3963  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3965  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3966 
3967  /* add constraint */
3968  SCIP_CALL( SCIPaddCons(scip, newcons) );
3969  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3970  }
3971  }
3972 
3973  /* reallocate buffer array */
3974  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, nvars + 1) );
3975  SCIP_CALL( SCIPreallocBufferArray(scip, &vals, nvars + 1) );
3976 
3977  for( v = 0; v < nvars; ++v )
3978  {
3979  vars[v] = consdata->vars[v];
3980  vals[v] = -1.0;
3981  }
3982 
3983  vars[nvars] = consdata->resvar;
3984 
3985  if( conshdlrdata->aggrlinearization )
3986  {
3987  /* create additional linear constraint */
3988  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_operators", SCIPconsGetName(cons));
3989 
3990  vals[nvars] = (SCIP_Real) nvars;
3991 
3992  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -SCIPinfinity(scip), 0.0,
3994  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3996  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3997 
3998  /* add constraint */
3999  SCIP_CALL( SCIPaddCons(scip, newcons) );
4000  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4001  }
4002 
4003  /* create additional linear constraint */
4004  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_add", SCIPconsGetName(cons));
4005 
4006  vals[nvars] = 1.0;
4007 
4008  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -nvars + 1.0, SCIPinfinity(scip),
4010  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
4012  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
4013 
4014  /* add constraint */
4015  SCIP_CALL( SCIPaddCons(scip, newcons) );
4016  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4017 
4018  /* delete constraint */
4019  SCIP_CALL( SCIPdelCons(scip, cons) );
4020  }
4021 
4022  /* free buffer array */
4023  SCIPfreeBufferArray(scip, &vars);
4024  SCIPfreeBufferArray(scip, &vals);
4025  }
4026 
4027  return SCIP_OKAY;
4028 }
4029 
4030 
4031 #ifdef GMLGATEPRINTING
4032 
4033 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
4034 static
4035 SCIP_DECL_CONSEXITPRE(consExitpreAnd)
4036 { /*lint --e{715}*/
4037  SCIP_HASHMAP* hashmap;
4038  FILE* gmlfile;
4039  char fname[SCIP_MAXSTRLEN];
4040  SCIP_CONS* cons;
4041  SCIP_CONSDATA* consdata;
4042  SCIP_VAR** activeconsvars;
4043  SCIP_VAR* activevar;
4044  int* varnodeids;
4045  SCIP_VAR** vars;
4046  int nvars;
4047  int nbinvars;
4048  int nintvars;
4049  int nimplvars;
4050  int ncontvars;
4051  int v;
4052  int c;
4053  int resid;
4054  int varid;
4055  int id = 1;
4056 
4057  /* no AND-constraints available */
4058  if( nconss == 0 )
4059  return SCIP_OKAY;
4060 
4061  nvars = SCIPgetNVars(scip);
4062 
4063  /* no variables left anymore */
4064  if( nvars == 0 )
4065  return SCIP_OKAY;
4066 
4067  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4068  SCIP_CALL( SCIPallocBufferArray(scip, &varnodeids, nvars) );
4069  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, &nimplvars, &ncontvars) );
4070 
4071  /* open gml file */
4072  (void) SCIPsnprintf(fname, SCIP_MAXSTRLEN, "and-gates%p.gml", scip);
4073  gmlfile = fopen(fname, "w");
4074 
4075  if( gmlfile == NULL )
4076  {
4077  SCIPerrorMessage("cannot open graph file <%s>\n", fname);
4078  SCIPABORT();
4079  return SCIP_WRITEERROR; /*lint !e527*/
4080  }
4081 
4082  /* create the variable mapping hash map */
4083  SCIP_CALL_FINALLY( SCIPhashmapCreate(&hashmap, SCIPblkmem(scip), nvars), fclose(gmlfile) );
4084 
4085  /* write starting of gml file */
4086  SCIPgmlWriteOpening(gmlfile, TRUE);
4087 
4088  /* walk over all AND-constraints */
4089  for( c = nconss - 1; c >= 0; --c )
4090  {
4091  cons = conss[c];
4092 
4093  /* only handle active constraints */
4094  if( !SCIPconsIsActive(cons) )
4095  continue;
4096 
4097  consdata = SCIPconsGetData(cons);
4098  assert(consdata != NULL);
4099 
4100  /* only handle constraints which have operands */
4101  if( consdata->nvars == 0 )
4102  continue;
4103 
4104  assert(consdata->vars != NULL);
4105  assert(consdata->resvar != NULL);
4106 
4107  /* get active variable of resultant */
4108  activevar = SCIPvarGetProbvar(consdata->resvar);
4109 
4110  /* check if we already found this variables */
4111  resid = SCIPhashmapGetImageInt(hashmap, activevar);
4112  assert(resid >= 0);
4113 
4114  if( resid == 0 )
4115  {
4116  resid = id;
4117  ++id;
4118  SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activevar, resid) );
4119 
4120  /* write new gml node for new resultant */
4121  SCIPgmlWriteNode(gmlfile, resid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4122  }
4123 
4124  /* copy operands to get problem variables for */
4125  SCIP_CALL( SCIPduplicateBufferArray(scip, &activeconsvars, consdata->vars, consdata->nvars) );
4126 
4127  /* get problem variables of operands */
4128  SCIPvarsGetProbvar(activeconsvars, consdata->nvars);
4129 
4130  for( v = consdata->nvars - 1; v >= 0; --v )
4131  {
4132  /* check if we already found this variables */
4133  varid = SCIPhashmapGetImageInt(hashmap, activeconsvars[v]);
4134  if( varid == 0 )
4135  {
4136  varid = id;
4137  ++id;
4138  SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activeconsvars[v], varid) );
4139 
4140  /* write new gml node for new operand */
4141  SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activeconsvars[v]), NULL, NULL, NULL);
4142  }
4143  /* write gml arc between resultant and operand */
4144  SCIPgmlWriteArc(gmlfile, resid, varid, NULL, NULL);
4145  }
4146 
4147  /* free temporary memory for active constraint variables */
4148  SCIPfreeBufferArray(scip, &activeconsvars);
4149  }
4150 
4151  /* write all remaining variables as nodes */
4152 #ifdef SCIP_DISABLED_CODE
4153  for( v = nvars - 1; v >= 0; --v )
4154  {
4155  activevar = SCIPvarGetProbvar(vars[v]);
4156 
4157  varid = SCIPhashmapGetImageInt(hashmap, activevar);
4158  assert(varid >= 0);
4159 
4160  if( varid == 0 )
4161  {
4162  varid = id;
4163  ++id;
4164  SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activeconsvars[v], varid) );
4165 
4166  /* write new gml node for new operand */
4167  SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4168  }
4169  }
4170 #endif
4171 
4172  /* free the variable mapping hash map */
4173  SCIPhashmapFree(&hashmap);
4174 
4175  SCIPgmlWriteClosing(gmlfile);
4176 
4177  fclose(gmlfile);
4178 
4179  SCIPfreeBufferArray(scip, &varnodeids);
4180  SCIPfreeBufferArray(scip, &vars);
4181 
4182  return SCIP_OKAY;
4183 }
4184 #endif
4185 
4186 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4187 static
4188 SCIP_DECL_CONSEXITSOL(consExitsolAnd)
4189 { /*lint --e{715}*/
4190  SCIP_CONSDATA* consdata;
4191  int c;
4192 
4193  /* release and free the rows of all constraints */
4194  for( c = 0; c < nconss; ++c )
4195  {
4196  consdata = SCIPconsGetData(conss[c]);
4197  assert(consdata != NULL);
4198 
4199  SCIP_CALL( consdataFreeRows(scip, consdata) );
4200  }
4201 
4202  return SCIP_OKAY;
4203 }
4204 
4205 
4206 /** frees specific constraint data */
4207 static
4208 SCIP_DECL_CONSDELETE(consDeleteAnd)
4209 { /*lint --e{715}*/
4210  SCIP_CONSHDLRDATA* conshdlrdata;
4211 
4212  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4213  assert(conshdlrdata != NULL);
4214 
4215  SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4216 
4217  return SCIP_OKAY;
4218 }
4219 
4220 
4221 /** transforms constraint data into data belonging to the transformed problem */
4222 static
4223 SCIP_DECL_CONSTRANS(consTransAnd)
4224 { /*lint --e{715}*/
4225  SCIP_CONSHDLRDATA* conshdlrdata;
4226  SCIP_CONSDATA* sourcedata;
4227  SCIP_CONSDATA* targetdata;
4228 
4229  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4230  assert(conshdlrdata != NULL);
4231 
4232  sourcedata = SCIPconsGetData(sourcecons);
4233  assert(sourcedata != NULL);
4234 
4235  /* create target constraint data */
4236  SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr,
4237  sourcedata->nvars, sourcedata->vars, sourcedata->resvar, sourcedata->checkwhenupgr,
4238  sourcedata->notremovablewhenupgr) );
4239 
4240  /* create target constraint */
4241  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4242  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4243  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4244  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4245  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4246 
4247  return SCIP_OKAY;
4248 }
4249 
4250 
4251 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4252 static
4253 SCIP_DECL_CONSINITLP(consInitlpAnd)
4254 { /*lint --e{715}*/
4255  int i;
4256 
4257  *infeasible = FALSE;
4258 
4259  for( i = 0; i < nconss && !(*infeasible); i++ )
4260  {
4261  assert(SCIPconsIsInitial(conss[i]));
4262  SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4263  }
4264 
4265  return SCIP_OKAY;
4266 }
4267 
4268 
4269 /** separation method of constraint handler for LP solutions */
4270 static
4271 SCIP_DECL_CONSSEPALP(consSepalpAnd)
4272 { /*lint --e{715}*/
4273  SCIP_Bool separated;
4274  SCIP_Bool cutoff;
4275  int c;
4276 
4277  *result = SCIP_DIDNOTFIND;
4278 
4279  /* separate all useful constraints */
4280  for( c = 0; c < nusefulconss; ++c )
4281  {
4282  SCIP_CALL( separateCons(scip, conss[c], NULL, &separated, &cutoff) );
4283  if ( cutoff )
4284  *result = SCIP_CUTOFF;
4285  else if ( separated )
4286  *result = SCIP_SEPARATED;
4287  }
4288 
4289  /* combine constraints to get more cuts */
4290  /**@todo combine constraints to get further cuts */
4291 
4292  return SCIP_OKAY;
4293 }
4294 
4295 
4296 /** separation method of constraint handler for arbitrary primal solutions */
4297 static
4298 SCIP_DECL_CONSSEPASOL(consSepasolAnd)
4299 { /*lint --e{715}*/
4300  SCIP_Bool separated;
4301  SCIP_Bool cutoff;
4302  int c;
4303 
4304  *result = SCIP_DIDNOTFIND;
4305 
4306  /* separate all useful constraints */
4307  for( c = 0; c < nusefulconss; ++c )
4308  {
4309  SCIP_CALL( separateCons(scip, conss[c], sol, &separated, &cutoff) );
4310  if ( cutoff )
4311  *result = SCIP_CUTOFF;
4312  else if ( separated )
4313  *result = SCIP_SEPARATED;
4314  }
4315 
4316  /* combine constraints to get more cuts */
4317  /**@todo combine constraints to get further cuts */
4318 
4319  return SCIP_OKAY;
4320 }
4321 
4322 
4323 /** constraint enforcing method of constraint handler for LP solutions */
4324 static
4325 SCIP_DECL_CONSENFOLP(consEnfolpAnd)
4326 { /*lint --e{715}*/
4327  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) );
4328 
4329  return SCIP_OKAY;
4330 }
4331 
4332 /** constraint enforcing method of constraint handler for relaxation solutions */
4333 static
4334 SCIP_DECL_CONSENFORELAX(consEnforelaxAnd)
4335 { /*lint --e{715}*/
4336  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) );
4337 
4338  return SCIP_OKAY;
4339 }
4340 
4341 /** constraint enforcing method of constraint handler for pseudo solutions */
4342 static
4343 SCIP_DECL_CONSENFOPS(consEnfopsAnd)
4344 { /*lint --e{715}*/
4345  SCIP_Bool violated;
4346  int i;
4347 
4348  /* method is called only for integral solutions, because the enforcing priority is negative */
4349  for( i = 0; i < nconss; i++ )
4350  {
4351  SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
4352  if( violated )
4353  {
4354  *result = SCIP_INFEASIBLE;
4355  return SCIP_OKAY;
4356  }
4357  }
4358  *result = SCIP_FEASIBLE;
4359 
4360  return SCIP_OKAY;
4361 }
4362 
4363 
4364 /** feasibility check method of constraint handler for integral solutions */
4365 static
4366 SCIP_DECL_CONSCHECK(consCheckAnd)
4367 { /*lint --e{715}*/
4368  SCIP_Bool violated;
4369  int i;
4370 
4371  *result = SCIP_FEASIBLE;
4372 
4373  /* method is called only for integral solutions, because the enforcing priority is negative */
4374  for( i = 0; i < nconss && (*result == SCIP_FEASIBLE || completely); i++ )
4375  {
4376  SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, printreason, &violated) );
4377  if( violated )
4378  *result = SCIP_INFEASIBLE;
4379  }
4380 
4381  return SCIP_OKAY;
4382 }
4383 
4384 
4385 /** domain propagation method of constraint handler */
4386 static
4387 SCIP_DECL_CONSPROP(consPropAnd)
4388 { /*lint --e{715}*/
4389  SCIP_CONSHDLRDATA* conshdlrdata;
4390  SCIP_Bool cutoff;
4391  int nfixedvars;
4392  int nupgdconss;
4393  int c;
4394 
4395  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4396  assert(conshdlrdata != NULL);
4397 
4398  cutoff = FALSE;
4399  nfixedvars = 0;
4400  nupgdconss = 0;
4401 
4402  /* propagate all useful constraints */
4403  for( c = 0; c < nusefulconss && !cutoff; ++c )
4404  {
4405  SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars, &nupgdconss) );
4406  }
4407 
4408  /* return the correct result */
4409  if( cutoff )
4410  *result = SCIP_CUTOFF;
4411  else if( nfixedvars > 0 || nupgdconss > 0 )
4412  *result = SCIP_REDUCEDDOM;
4413  else
4414  *result = SCIP_DIDNOTFIND;
4415 
4416  return SCIP_OKAY;
4417 }
4418 
4419 
4420 /** presolving method of constraint handler */
4421 static
4422 SCIP_DECL_CONSPRESOL(consPresolAnd)
4423 { /*lint --e{715}*/
4424  SCIP_CONSHDLRDATA* conshdlrdata;
4425  SCIP_CONS* cons;
4426  SCIP_CONSDATA* consdata;
4427  unsigned char* entries;
4428  SCIP_Bool cutoff;
4429  int oldnfixedvars;
4430  int oldnaggrvars;
4431  int oldnchgbds;
4432  int oldndelconss;
4433  int oldnupgdconss;
4434  int firstchange;
4435  int nentries;
4436  int c;
4437 
4438  assert(result != NULL);
4439 
4440  oldnfixedvars = *nfixedvars;
4441  oldnaggrvars = *naggrvars;
4442  oldnchgbds = *nchgbds;
4443  oldndelconss = *ndelconss;
4444  oldnupgdconss = *nupgdconss;
4445 
4446  nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
4447  SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
4448 
4449  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4450  assert(conshdlrdata != NULL);
4451 
4452  /* process constraints */
4453  cutoff = FALSE;
4454  firstchange = INT_MAX;
4455  for( c = 0; c < nconss && !cutoff && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
4456  {
4457  cons = conss[c];
4458  assert(cons != NULL);
4459  consdata = SCIPconsGetData(cons);
4460  assert(consdata != NULL);
4461 
4462  /* force presolving the constraint in the initial round */
4463  if( nrounds == 0 )
4464  consdata->propagated = FALSE;
4465 
4466  /* remember the first changed constraint to begin the next aggregation round with */
4467  if( firstchange == INT_MAX && consdata->changed )
4468  firstchange = c;
4469 
4470  /* propagate constraint */
4471  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nupgdconss) );
4472 
4473  /* remove all variables that are fixed to one; merge multiple entries of the same variable;
4474  * fix resultant to zero if a pair of negated variables is contained in the operand variables
4475  */
4476  if( !cutoff && !SCIPconsIsDeleted(cons) )
4477  {
4478  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs) );
4479 
4480  /* merge multiple occurances of variables or variables with their negated variables */
4481  SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, nfixedvars, nchgcoefs, ndelconss) );
4482  }
4483 
4484  if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
4485  {
4486  assert(consdata->nvars >= 1); /* otherwise, propagateCons() has deleted the constraint */
4487 
4488  /* if only one variable is left, the resultant has to be equal to this single variable */
4489  if( consdata->nvars == 1 )
4490  {
4491  SCIP_Bool redundant;
4492  SCIP_Bool aggregated;
4493 
4494  SCIPdebugMsg(scip, "AND-constraint <%s> has only one variable not fixed to 1.0\n", SCIPconsGetName(cons));
4495 
4496  assert(consdata->vars != NULL);
4497  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
4498  assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
4499 
4500  /* aggregate variables: resultant - operand == 0 */
4501  SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
4502  &cutoff, &redundant, &aggregated) );
4503  assert(redundant || SCIPdoNotAggr(scip));
4504 
4505  if( aggregated )
4506  {
4507  assert(redundant);
4508  (*naggrvars)++;
4509  }
4510 
4511  if( redundant )
4512  {
4513  /* delete constraint */
4514  SCIP_CALL( SCIPdelCons(scip, cons) );
4515  (*ndelconss)++;
4516  }
4517  }
4518  else if( !consdata->impladded )
4519  {
4520  int i;
4521 
4522  /* add implications: resultant == 1 -> all operands == 1 */
4523  for( i = 0; i < consdata->nvars && !cutoff; ++i )
4524  {
4525  int nimplbdchgs;
4526 
4527  SCIP_CALL( SCIPaddVarImplication(scip, consdata->resvar, TRUE, consdata->vars[i],
4528  SCIP_BOUNDTYPE_LOWER, 1.0, &cutoff, &nimplbdchgs) );
4529  (*nchgbds) += nimplbdchgs;
4530  }
4531  consdata->impladded = TRUE;
4532  }
4533 
4534  /* if in r = x and y, the resultant is fixed to zero, add implication x = 1 -> y = 0 */
4535  if( !cutoff && SCIPconsIsActive(cons) && consdata->nvars == 2 && !consdata->opimpladded
4536  && SCIPvarGetUbGlobal(consdata->resvar) < 0.5 )
4537  {
4538  int nimplbdchgs;
4539 
4540  SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], TRUE, consdata->vars[1],
4541  SCIP_BOUNDTYPE_UPPER, 0.0, &cutoff, &nimplbdchgs) );
4542  (*nchgbds) += nimplbdchgs;
4543  consdata->opimpladded = TRUE;
4544  }
4545  }
4546  }
4547 
4548  /* perform dual presolving on AND-constraints */
4549  if( conshdlrdata->dualpresolving && !cutoff && !SCIPisStopped(scip) && SCIPallowDualReds(scip))
4550  {
4551  SCIP_CALL( dualPresolve(scip, conss, nconss, conshdlrdata->eventhdlr, &entries, &nentries, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, nupgdconss, naddconss) );
4552  }
4553 
4554  /* check for cliques inside the AND constraint */
4555  if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4556  {
4557  for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4558  {
4559  if( SCIPconsIsActive(conss[c]) )
4560  {
4561  /* check if at least two operands are in one clique */
4562  SCIP_CALL( cliquePresolve(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, naddconss) );
4563  }
4564  }
4565  }
4566 
4567  /* process pairs of constraints: check them for equal operands in order to aggregate resultants;
4568  * only apply this expensive procedure, if the single constraint preprocessing did not find any reductions
4569  * (otherwise, we delay the presolving to be called again next time)
4570  */
4571  if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4572  {
4573  if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4574  {
4575  if( firstchange < nconss )
4576  {
4577  /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
4578  SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, &cutoff, naggrvars, ndelconss) );
4579  oldnaggrvars = *naggrvars;
4580  }
4581  }
4582  }
4583 
4584  if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4585  {
4586  if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4587  {
4588  SCIP_Longint npaircomparisons;
4589  npaircomparisons = 0;
4590  oldndelconss = *ndelconss;
4591 
4592  for( c = firstchange; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4593  {
4594  if( SCIPconsIsActive(conss[c]) && !SCIPconsIsModifiable(conss[c]) )
4595  {
4596  npaircomparisons += ((SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange));
4597 
4598  SCIP_CALL( preprocessConstraintPairs(scip, conss, firstchange, c, &cutoff, naggrvars, nchgbds,
4599  ndelconss) );
4600 
4601  if( npaircomparisons > NMINCOMPARISONS )
4602  {
4603  if( ((*ndelconss - oldndelconss) + (*naggrvars - oldnaggrvars) + (*nchgbds - oldnchgbds)/2.0) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
4604  break;
4605  oldndelconss = *ndelconss;
4606  oldnaggrvars = *naggrvars;
4607  oldnchgbds = *nchgbds;
4608 
4609  npaircomparisons = 0;
4610  }
4611  }
4612  }
4613  }
4614  }
4615 
4616  SCIPfreeBufferArray(scip, &entries);
4617 
4618  /* return the correct result code */
4619  if( cutoff )
4620  *result = SCIP_CUTOFF;
4621  else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds
4622  || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4623  *result = SCIP_SUCCESS;
4624  else
4625  *result = SCIP_DIDNOTFIND;
4626 
4627  return SCIP_OKAY;
4628 }
4629 
4630 
4631 /** propagation conflict resolving method of constraint handler */
4632 static
4633 SCIP_DECL_CONSRESPROP(consRespropAnd)
4634 { /*lint --e{715}*/
4635  SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
4636 
4637  return SCIP_OKAY;
4638 }
4639 
4640 
4641 /** variable rounding lock method of constraint handler */
4642 static
4643 SCIP_DECL_CONSLOCK(consLockAnd)
4644 { /*lint --e{715}*/
4645  SCIP_CONSDATA* consdata;
4646  int i;
4647 
4648  assert(locktype == SCIP_LOCKTYPE_MODEL);
4649 
4650  consdata = SCIPconsGetData(cons);
4651  assert(consdata != NULL);
4652 
4653  /* resultant variable */
4654  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->resvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4655 
4656  /* operand variables */
4657  for( i = 0; i < consdata->nvars; ++i )
4658  {
4659  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4660  }
4661 
4662  return SCIP_OKAY;
4663 }
4664 
4665 
4666 /** constraint display method of constraint handler */
4667 static
4668 SCIP_DECL_CONSPRINT(consPrintAnd)
4669 { /*lint --e{715}*/
4670  assert( scip != NULL );
4671  assert( conshdlr != NULL );
4672  assert( cons != NULL );
4673 
4674  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file) );
4675 
4676  return SCIP_OKAY;
4677 }
4678 
4679 /** constraint copying method of constraint handler */
4680 static
4681 SCIP_DECL_CONSCOPY(consCopyAnd)
4682 { /*lint --e{715}*/
4683  SCIP_VAR** sourcevars;
4684  SCIP_VAR** vars;
4685  SCIP_VAR* sourceresvar;
4686  SCIP_VAR* resvar;
4687  const char* consname;
4688  int nvars;
4689  int v;
4690 
4691  assert(valid != NULL);
4692  (*valid) = TRUE;
4693 
4694  sourceresvar = SCIPgetResultantAnd(sourcescip, sourcecons);
4695 
4696  /* map resultant to active variable of the target SCIP */
4697  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceresvar, &resvar, varmap, consmap, global, valid) );
4698  assert(!(*valid) || resvar != NULL);
4699 
4700  /* we do not copy, if a variable is missing */
4701  if( !(*valid) )
4702  return SCIP_OKAY;
4703 
4704  /* map operand variables to active variables of the target SCIP */
4705  sourcevars = SCIPgetVarsAnd(sourcescip, sourcecons);
4706  nvars = SCIPgetNVarsAnd(sourcescip, sourcecons);
4707 
4708  if( nvars == -1 )
4709  return SCIP_INVALIDCALL;
4710 
4711  /* allocate buffer array */
4712  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4713 
4714  for( v = 0; v < nvars; ++v )
4715  {
4716  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
4717  assert(!(*valid) || vars[v] != NULL);
4718 
4719  /* we do not copy, if a variable is missing */
4720  if( !(*valid) )
4721  goto TERMINATE;
4722  }
4723 
4724  if( name != NULL )
4725  consname = name;
4726  else
4727  consname = SCIPconsGetName(sourcecons);
4728 
4729  /* creates and captures a AND-constraint */
4730  SCIP_CALL( SCIPcreateConsAnd(scip, cons, consname, resvar, nvars, vars,
4731  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4732 
4733  TERMINATE:
4734  /* free buffer array */
4735  SCIPfreeBufferArray(scip, &vars);
4736 
4737  return SCIP_OKAY;
4738 }
4739 
4740 /** constraint parsing method of constraint handler */
4741 static
4742 SCIP_DECL_CONSPARSE(consParseAnd)
4743 { /*lint --e{715}*/
4744  SCIP_VAR** vars;
4745  SCIP_VAR* resvar;
4746  char* endptr;
4747  int requiredsize;
4748  int varssize;
4749  int nvars;
4750 
4751  SCIPdebugMsg(scip, "parse <%s> as AND-constraint\n", str);
4752 
4753  *success = FALSE;
4754 
4755  /* parse variable name of resultant */
4756  SCIP_CALL( SCIPparseVarName(scip, str, &resvar, &endptr) );
4757  str = endptr;
4758 
4759  if( resvar == NULL )
4760  {
4761  SCIPdebugMsg(scip, "resultant variable does not exist \n");
4762  }
4763  else
4764  {
4765  char* strcopy = NULL;
4766  char* startptr;
4767 
4768  /* cutoff "== and(" form the constraint string */
4769  startptr = strchr((char*)str, '(');
4770 
4771  if( startptr == NULL )
4772  {
4773  SCIPerrorMessage("missing starting character '(' parsing AND-constraint\n");
4774  return SCIP_OKAY;
4775  }
4776 
4777  /* skip '(' */
4778  ++startptr;
4779 
4780  /* find end character ')' */
4781  endptr = strrchr(startptr, ')');
4782 
4783  if( endptr == NULL )
4784  {
4785  SCIPerrorMessage("missing ending character ')' parsing AND-constraint\n");
4786  return SCIP_OKAY;
4787  }
4788  assert(endptr >= startptr);
4789 
4790  if( endptr > startptr )
4791  {
4792  /* copy string for parsing */
4793  SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, startptr, (int)(endptr-startptr)) );
4794 
4795  varssize = 100;
4796  nvars = 0;
4797 
4798  /* allocate buffer array for variables */
4799  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
4800 
4801  /* parse string */
4802  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4803 
4804  if( *success )
4805  {
4806  /* check if the size of the variable array was great enough */
4807  if( varssize < requiredsize )
4808  {
4809  /* reallocate memory */
4810  varssize = requiredsize;
4811  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
4812 
4813  /* parse string again with the correct size of the variable array */
4814  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4815  }
4816 
4817  assert(*success);
4818  assert(varssize >= requiredsize);
4819 
4820  /* create AND-constraint */
4821  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
4822  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4823  }
4824 
4825  /* free variable buffer */
4826  SCIPfreeBufferArray(scip, &vars);
4827  SCIPfreeBufferArray(scip, &strcopy);
4828  }
4829  else
4830  {
4831  if( !modifiable )
4832  {
4833  SCIPerrorMessage("cannot create empty AND-constraint\n");
4834  return SCIP_OKAY;
4835  }
4836 
4837  /* create empty AND-constraint */
4838  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, 0, NULL,
4839  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4840 
4841  *success = TRUE;
4842  }
4843  }
4844 
4845  return SCIP_OKAY;
4846 }
4847 
4848 /** constraint method of constraint handler which returns the variables (if possible) */
4849 static
4850 SCIP_DECL_CONSGETVARS(consGetVarsAnd)
4851 { /*lint --e{715}*/
4852  SCIP_CONSDATA* consdata;
4853 
4854  consdata = SCIPconsGetData(cons);
4855  assert(consdata != NULL);
4856 
4857  if( varssize < consdata->nvars + 1 )
4858  (*success) = FALSE;
4859  else
4860  {
4861  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
4862  vars[consdata->nvars] = consdata->resvar;
4863  (*success) = TRUE;
4864  }
4865 
4866  return SCIP_OKAY;
4867 }
4868 
4869 /** constraint method of constraint handler which returns the number of variable (if possible) */
4870 static
4871 SCIP_DECL_CONSGETNVARS(consGetNVarsAnd)
4872 { /*lint --e{715}*/
4873  SCIP_CONSDATA* consdata;
4874 
4875  assert(cons != NULL);
4876 
4877  consdata = SCIPconsGetData(cons);
4878  assert(consdata != NULL);
4879 
4880  (*nvars) = consdata->nvars + 1;
4881  (*success) = TRUE;
4882 
4883  return SCIP_OKAY;
4884 }
4885 
4886 
4887 /*
4888  * Callback methods of event handler
4889  */
4890 
4891 static
4892 SCIP_DECL_EVENTEXEC(eventExecAnd)
4893 { /*lint --e{715}*/
4894  SCIP_CONSDATA* consdata;
4895 
4896  assert(eventhdlr != NULL);
4897  assert(eventdata != NULL);
4898  assert(event != NULL);
4899 
4900  consdata = (SCIP_CONSDATA*)eventdata;
4901  assert(consdata != NULL);
4902 
4903  /* check, if the variable was fixed to zero */
4905  consdata->nofixedzero = FALSE;
4906 
4907  consdata->propagated = FALSE;
4908 
4909  return SCIP_OKAY;
4910 }
4911 
4912 
4913 /*
4914  * constraint specific interface methods
4915  */
4916 
4917 /** creates the handler for AND-constraints and includes it in SCIP */
4919  SCIP* scip /**< SCIP data structure */
4920  )
4921 {
4922  SCIP_CONSHDLRDATA* conshdlrdata;
4923  SCIP_CONSHDLR* conshdlr;
4924  SCIP_EVENTHDLR* eventhdlr;
4925 
4926  /* create event handler for events on variables */
4928  eventExecAnd, NULL) );
4929 
4930  /* create constraint handler data */
4931  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
4932 
4933  /* include constraint handler */
4936  consEnfolpAnd, consEnfopsAnd, consCheckAnd, consLockAnd,
4937  conshdlrdata) );
4938 
4939  assert(conshdlr != NULL);
4940 
4941  /* set non-fundamental callbacks via specific setter functions */
4942  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyAnd, consCopyAnd) );
4943  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteAnd) );
4944 #ifdef GMLGATEPRINTING
4945  SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreAnd) );
4946 #endif
4947  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolAnd) );
4948  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeAnd) );
4949  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsAnd) );
4950  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsAnd) );
4951  SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreAnd) );
4952  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpAnd) );
4953  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseAnd) );
4954  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolAnd, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
4955  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintAnd) );
4956  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropAnd, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
4958  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropAnd) );
4959  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpAnd, consSepasolAnd, CONSHDLR_SEPAFREQ,
4961  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransAnd) );
4962  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxAnd) );
4963 
4964  /* add AND-constraint handler parameters */
4966  "constraints/" CONSHDLR_NAME "/presolpairwise",
4967  "should pairwise constraint comparison be performed in presolving?",
4968  &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
4970  "constraints/and/presolusehashing",
4971  "should hash table be used for detecting redundant constraints in advance",
4972  &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
4974  "constraints/" CONSHDLR_NAME "/linearize",
4975  "should the AND-constraint get linearized and removed (in presolving)?",
4976  &conshdlrdata->linearize, TRUE, DEFAULT_LINEARIZE, NULL, NULL) );
4978  "constraints/" CONSHDLR_NAME "/enforcecuts",
4979  "should cuts be separated during LP enforcing?",
4980  &conshdlrdata->enforcecuts, TRUE, DEFAULT_ENFORCECUTS, NULL, NULL) );
4982  "constraints/" CONSHDLR_NAME "/aggrlinearization",
4983  "should an aggregated linearization be used?",
4984  &conshdlrdata->aggrlinearization, TRUE, DEFAULT_AGGRLINEARIZATION, NULL, NULL) );
4986  "constraints/" CONSHDLR_NAME "/upgraderesultant",
4987  "should all binary resultant variables be upgraded to implicit binary variables?",
4988  &conshdlrdata->upgrresultant, TRUE, DEFAULT_UPGRRESULTANT, NULL, NULL) );
4990  "constraints/" CONSHDLR_NAME "/dualpresolving",
4991  "should dual presolving be performed?",
4992  &conshdlrdata->dualpresolving, TRUE, DEFAULT_DUALPRESOLVING, NULL, NULL) );
4993 
4994  if( SCIPfindConshdlr(scip, "nonlinear") != NULL )
4995  {
4996  /* include the AND-constraint upgrade in the nonlinear constraint handler */
4998  }
4999 
5000  return SCIP_OKAY;
5001 }
5002 
5003 /** creates and captures a AND-constraint
5004  *
5005  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5006  */
5008  SCIP* scip, /**< SCIP data structure */
5009  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5010  const char* name, /**< name of constraint */
5011  SCIP_VAR* resvar, /**< resultant variable of the operation */
5012  int nvars, /**< number of operator variables in the constraint */
5013  SCIP_VAR** vars, /**< array with operator variables of constraint */
5014  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5015  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5016  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5017  * Usually set to TRUE. */
5018  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5019  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5020  SCIP_Bool check, /**< should the constraint be checked for feasibility?
5021  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5022  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5023  * Usually set to TRUE. */
5024  SCIP_Bool local, /**< is constraint only valid locally?
5025  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5026  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5027  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5028  * adds coefficients to this constraint. */
5029  SCIP_Bool dynamic, /**< is constraint subject to aging?
5030  * Usually set to FALSE. Set to TRUE for own cuts which
5031  * are separated as constraints. */
5032  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5033  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5034  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5035  * if it may be moved to a more global node?
5036  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5037  )
5038 {
5039  SCIP_CONSHDLR* conshdlr;
5040  SCIP_CONSHDLRDATA* conshdlrdata;
5041  SCIP_CONSDATA* consdata;
5042  SCIP_Bool infeasible;
5043 
5044  /* find the AND-constraint handler */
5045  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5046  if( conshdlr == NULL )
5047  {
5048  SCIPerrorMessage("AND-constraint handler not found\n");
5049  return SCIP_PLUGINNOTFOUND;
5050  }
5051 
5052  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5053  assert(conshdlrdata != NULL);
5054 
5055  /* upgrade binary resultant variable to an implicit binary variable */
5056  /* @todo add implicit upgrade in presolving, improve decision making for upgrade by creating an implication graph */
5057  if( conshdlrdata->upgrresultant && SCIPvarGetType(resvar) == SCIP_VARTYPE_BINARY
5058 #if 1 /* todo delete following hack,
5059  * the following avoids upgrading not artificial variables, for example and-resultants which are generated
5060  * from the gate presolver, it seems better to not upgrade these variables
5061  */
5062  && strlen(SCIPvarGetName(resvar)) > strlen(ARTIFICIALVARNAMEPREFIX) && strncmp(SCIPvarGetName(resvar), ARTIFICIALVARNAMEPREFIX, strlen(ARTIFICIALVARNAMEPREFIX)) == 0 )
5063 #else
5064  )
5065 #endif
5066  {
5067  SCIP_VAR* activeresvar;
5068  SCIP_VAR* activevar;
5069  int v;
5070 
5071  if( SCIPisTransformed(scip) )
5072  activeresvar = SCIPvarGetProbvar(resvar);
5073  else
5074  activeresvar = resvar;
5075 
5076  if( SCIPvarGetType(activeresvar) == SCIP_VARTYPE_BINARY )
5077  {
5078  /* check if we can upgrade the variable type of the resultant */
5079  for( v = nvars - 1; v >= 0; --v )
5080  {
5081  if( SCIPisTransformed(scip) )
5082  activevar = SCIPvarGetProbvar(vars[v]);
5083  else
5084  activevar = vars[v];
5085 
5086  if( activevar == activeresvar || SCIPvarGetType(activevar) == SCIP_VARTYPE_IMPLINT )
5087  break;
5088  }
5089 
5090  /* upgrade the type of the resultant */
5091  if( v < 0 )
5092  {
5093  SCIP_CALL( SCIPchgVarType(scip, resvar, SCIP_VARTYPE_IMPLINT, &infeasible) );
5094  assert(!infeasible);
5095  }
5096  }
5097  }
5098 
5099  /* create constraint data */
5100  SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, resvar, FALSE, FALSE) );
5101 
5102  /* create constraint */
5103  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5104  local, modifiable, dynamic, removable, stickingatnode) );
5105 
5106  return SCIP_OKAY;
5107 }
5108 
5109 /** creates and captures an AND-constraint
5110  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
5111  * method SCIPcreateConsAnd(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
5112  *
5113  * @see SCIPcreateConsAnd() for information about the basic constraint flag configuration
5114  *
5115  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5116  */
5118  SCIP* scip, /**< SCIP data structure */
5119  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5120  const char* name, /**< name of constraint */
5121  SCIP_VAR* resvar, /**< resultant variable of the operation */
5122  int nvars, /**< number of operator variables in the constraint */
5123  SCIP_VAR** vars /**< array with operator variables of constraint */
5124  )
5125 {
5126  assert(scip != NULL);
5127 
5128  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
5129  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
5130 
5131  return SCIP_OKAY;
5132 }
5133 
5134 
5135 /** gets number of variables in AND-constraint */
5136 int SCIPgetNVarsAnd(
5137  SCIP* scip, /**< SCIP data structure */
5138  SCIP_CONS* cons /**< constraint data */
5139  )
5140 {
5141  SCIP_CONSDATA* consdata;
5142 
5143  assert(scip != NULL);
5144  assert(cons != NULL);
5145 
5146  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5147  {
5148  SCIPerrorMessage("constraint is not an AND-constraint\n");
5149  SCIPABORT();
5150  return -1; /*lint !e527*/
5151  }
5152 
5153  consdata = SCIPconsGetData(cons);
5154  assert(consdata != NULL);
5155 
5156  return consdata->nvars;
5157 }
5158 
5159 /** gets array of variables in AND-constraint */
5161  SCIP* scip, /**< SCIP data structure */
5162  SCIP_CONS* cons /**< constraint data */
5163  )
5164 {
5165  SCIP_CONSDATA* consdata;
5166 
5167  assert(scip != NULL);
5168  assert(cons != NULL);
5169 
5170  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5171  {
5172  SCIPerrorMessage("constraint is not an AND-constraint\n");
5173  SCIPABORT();
5174  return NULL; /*lint !e527*/
5175  }
5176 
5177  consdata = SCIPconsGetData(cons);
5178  assert(consdata != NULL);
5179 
5180  return consdata->vars;
5181 }
5182 
5183 
5184 /** gets the resultant variable in AND-constraint */
5186  SCIP* scip, /**< SCIP data structure */
5187  SCIP_CONS* cons /**< constraint data */
5188  )
5189 {
5190  SCIP_CONSDATA* consdata;
5191 
5192  assert(cons != NULL);
5193 
5194  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5195  {
5196  SCIPerrorMessage("constraint is not an AND-constraint\n");
5197  SCIPABORT();
5198  return NULL; /*lint !e527*/
5199  }
5200 
5201  consdata = SCIPconsGetData(cons);
5202  assert(consdata != NULL);
5203 
5204  return consdata->resvar;
5205 }
5206 
5207 /** return if the variables of the AND-constraint are sorted with respect to their indices */
5209  SCIP* scip, /**< SCIP data structure */
5210  SCIP_CONS* cons /**< constraint data */
5211  )
5212 {
5213  SCIP_CONSDATA* consdata;
5214 
5215  assert(scip != NULL);
5216  assert(cons != NULL);
5217 
5218  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5219  {
5220  SCIPerrorMessage("constraint is not an AND-constraint\n");
5221  SCIPABORT();
5222  return FALSE; /*lint !e527*/
5223  }
5224 
5225  consdata = SCIPconsGetData(cons);
5226  assert(consdata != NULL);
5227 
5228  return consdata->sorted;
5229 }
5230 
5231 /** sort the variables of the AND-constraint with respect to their indices */
5233  SCIP* scip, /**< SCIP data structure */
5234  SCIP_CONS* cons /**< constraint data */
5235  )
5236 {
5237  SCIP_CONSDATA* consdata;
5238 
5239  assert(scip != NULL);
5240  assert(cons != NULL);
5241 
5242  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5243  {
5244  SCIPerrorMessage("constraint is not an AND-constraint\n");
5245  SCIPABORT();
5246  return SCIP_INVALIDDATA; /*lint !e527*/
5247  }
5248 
5249  consdata = SCIPconsGetData(cons);
5250  assert(consdata != NULL);
5251 
5252  consdataSort(consdata);
5253  assert(consdata->sorted);
5254 
5255  return SCIP_OKAY;
5256 }
5257 
5258 /** when 'upgrading' the given AND-constraint, should the check flag for the upgraded constraint be set to TRUE, even if
5259  * the check flag of this AND-constraint is set to FALSE?
5260  */
5262  SCIP* scip, /**< SCIP data structure */
5263  SCIP_CONS* cons, /**< constraint data */
5264  SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be checked,
5265  * even if the check flag of the AND-constraint is set to FALSE
5266  */
5267  )
5268 {
5269  SCIP_CONSDATA* consdata;
5270 
5271  assert(scip != NULL);
5272  assert(cons != NULL);
5273 
5274  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5275  {
5276  SCIPerrorMessage("constraint is not an AND-constraint\n");
5277  SCIPABORT();
5278  return SCIP_INVALIDDATA; /*lint !e527*/
5279  }
5280 
5281  consdata = SCIPconsGetData(cons);
5282  assert(consdata != NULL);
5283 
5284  consdata->checkwhenupgr = flag;
5285 
5286  return SCIP_OKAY;
5287 }
5288 
5289 /** when 'upgrading' the given AND-constraint, should the removable flag for the upgraded constraint be set to FALSE,
5290  * even if the removable flag of this AND-constraint is set to TRUE?
5291  */
5293  SCIP* scip, /**< SCIP data structure */
5294  SCIP_CONS* cons, /**< constraint data */
5295  SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be not
5296  * removable, even if the removable flag of the AND-constraint is set to
5297  * TRUE
5298  */
5299  )
5300 {
5301  SCIP_CONSDATA* consdata;
5302 
5303  assert(scip != NULL);
5304  assert(cons != NULL);
5305 
5306  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5307  {
5308  SCIPerrorMessage("constraint is not an AND-constraint\n");
5309  SCIPABORT();
5310  return SCIP_INVALIDDATA; /*lint !e527*/
5311  }
5312 
5313  consdata = SCIPconsGetData(cons);
5314  assert(consdata != NULL);
5315 
5316  consdata->notremovablewhenupgr = flag;
5317 
5318  return SCIP_OKAY;
5319 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
int SCIPconsGetPos(SCIP_CONS *cons)
Definition: cons.c:8086
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:202
static SCIP_RETCODE consdataFixResultantZero(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *resvar, int pos, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1260
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4221
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcreateConsAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_and.c:5008
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2167
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
Definition: cons_and.c:1887
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_EXPORT SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:16880
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define ARTIFICIALVARNAMEPREFIX
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
#define NULL
Definition: def.h:253
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:686
static SCIP_DECL_CONSSEPASOL(consSepasolAnd)
Definition: cons_and.c:4299
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:585
SCIP_RETCODE SCIPexprgraphAddNode(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node, int mindepth, int nchildren, SCIP_EXPRGRAPHNODE **children)
Definition: expr.c:15180
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2364
SCIP_EXPORT SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16893
SCIP_RETCODE SCIPsortAndCons(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5233
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:876
static SCIP_RETCODE cliquePresolve(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars, int *naggrvars, int *nchgcoefs, int *ndelconss, int *naddconss)
Definition: cons_and.c:2625
public methods for SCIP parameter handling
SCIP_RETCODE SCIPexprgraphAddVars(SCIP_EXPRGRAPH *exprgraph, int nvars, void **vars, SCIP_EXPRGRAPHNODE **varnodes)
Definition: expr.c:15264
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1994
#define CONSHDLR_SEPAPRIORITY
Definition: cons_and.c:72
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:220
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:452
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_EVENTEXEC(eventExecAnd)
Definition: cons_and.c:4893
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:933
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8315
SCIP_Bool SCIPisAndConsSorted(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5209
SCIP_EXPORT int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3241
public methods for memory management
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:307
int SCIPexprgraphGetNodeNChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12974
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5161
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_EXPORT SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:165
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4200
static SCIP_DECL_CONSENFORELAX(consEnforelaxAnd)
Definition: cons_and.c:4335
#define SCIP_MAXSTRLEN
Definition: def.h:274
static SCIP_RETCODE mergeMultiples(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, unsigned char **entries, int *nentries, int *nfixedvars, int *nchgcoefs, int *ndelconss)
Definition: cons_and.c:1525
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1483
public methods for conflict handler plugins and conflict analysis
static SCIP_RETCODE analyzeConflictZero(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:1224
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5637
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2425
SCIP_RETCODE SCIPcreateConsBasicAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars)
Definition: cons_and.c:5118
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:815
static SCIP_RETCODE consdataSwitchWatchedvars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
Definition: cons_and.c:336
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip_var.c:1600
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:407
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1217
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
static SCIP_DECL_HASHKEYEQ(hashKeyEqAndcons)
Definition: cons_and.c:3281
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:769
static SCIP_DECL_CONSPARSE(consParseAnd)
Definition: cons_and.c:4743
SCIP_Bool SCIPconsIsAdded(SCIP_CONS *cons)
Definition: cons.c:8505
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPparseVarsList(SCIP *scip, const char *str, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize, char **endptr, char delimiter, SCIP_Bool *success)
Definition: scip_var.c:600
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3009
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_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16918
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1987
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8137
#define FALSE
Definition: def.h:73
#define CONSHDLR_CHECKPRIORITY
Definition: cons_and.c:74
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16903
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
enum Proprule PROPRULE
static SCIP_DECL_CONSPROP(consPropAnd)
Definition: cons_and.c:4388
#define SCIP_PRESOLTIMING_EXHAUSTIVE
Definition: type_timing.h:45
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3470
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:523
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8245
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
Definition: cons_and.c:577
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:423
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:562
#define CONSHDLR_NAME
Definition: cons_and.c:70
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2122
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17025
public methods for problem variables
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:47
static SCIP_RETCODE consdataLinearize(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nfixedvars, int *nupgdconss)
Definition: cons_and.c:1353
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16857
Constraint handler for AND constraints, .
static SCIP_DECL_CONSINITPRE(consInitpreAnd)
Definition: cons_and.c:3906
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
#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
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:524
static SCIP_DECL_CONSPRINT(consPrintAnd)
Definition: cons_and.c:4669
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:135
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:838
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num)
Definition: cons_and.c:396
public methods for SCIP variables
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
Definition: scip_cons.c:500
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition: type_event.h:108
#define SCIPdebugMsgPrint
Definition: scip_message.h:70
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2005
static SCIP_RETCODE consdataDropWatchedEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int filterpos)
Definition: cons_and.c:261
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
static SCIP_DECL_CONSEXITSOL(consExitsolAnd)
Definition: cons_and.c:4189
#define EVENTHDLR_DESC
Definition: cons_and.c:89
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4291
#define DEFAULT_PRESOLPAIRWISE
Definition: cons_and.c:91
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:558
int SCIPexprgraphGetNodePolynomialNMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13197
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:356
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip_cons.c:1460
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5186
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2077
public methods for numerical tolerances
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
Definition: misc.c:671
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:627
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:2113
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:264
public methods for expressions, expression trees, expression graphs, and related stuff ...
#define SCIP_REAL_FORMAT
Definition: def.h:167
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2838
static SCIP_RETCODE dualPresolve(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_EVENTHDLR *eventhdlr, unsigned char **entries, int *nentries, SCIP_Bool *cutoff, int *nfixedvars, int *naggrvars, int *nchgcoefs, int *ndelconss, int *nupgdconss, int *naddconss)
Definition: cons_and.c:1973
static SCIP_DECL_CONSENFOPS(consEnfopsAnd)
Definition: cons_and.c:4344
int SCIPexprGetMonomialNFactors(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5911
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17177
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:64
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3098
public methods for the branch-and-bound tree
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:672
SCIP_EXPROP SCIPexprgraphGetNodeOperator(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13034
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1530
SCIP_EXPRDATA_MONOMIAL ** SCIPexprgraphGetNodePolynomialMonomials(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13185
static SCIP_DECL_CONSFREE(consFreeAnd)
Definition: cons_and.c:3888
#define EVENTHDLR_NAME
Definition: cons_and.c:88
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8542
public methods for managing constraints
static SCIP_DECL_CONSPRESOL(consPresolAnd)
Definition: cons_and.c:4423
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10571
SCIP_Real SCIPexprgraphGetNodePolynomialConstant(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13209
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
#define CONSHDLR_PRESOLTIMING
Definition: cons_and.c:85
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
#define SCIPerrorMessage
Definition: pub_message.h:45
#define CONSHDLR_PROP_TIMING
Definition: cons_and.c:86
SCIP_EXPORT SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17168
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1406
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:3543
public methods for event handler plugins and event handlers
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_and.c:662
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1442
static SCIP_DECL_CONSDELETE(consDeleteAnd)
Definition: cons_and.c:4209
SCIP_EXPORT SCIP_RETCODE SCIPvarGetAggregatedObj(SCIP_VAR *var, SCIP_Real *aggrobj)
Definition: var.c:17222
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:47
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:99
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_Bool *violated)
Definition: cons_and.c:1013
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:87
SCIP_RETCODE SCIPwriteVarsList(SCIP *scip, FILE *file, SCIP_VAR **vars, int nvars, SCIP_Bool type, char delimiter)
Definition: scip_var.c:282
static SCIP_DECL_CONSTRANS(consTransAnd)
Definition: cons_and.c:4224
SCIP_RETCODE SCIPchgAndConsCheckFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition: cons_and.c:5262
#define REALABS(x)
Definition: def.h:188
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:13441
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:476
#define DEFAULT_LINEARIZE
Definition: cons_and.c:92
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8106
#define SCIP_CALL(x)
Definition: def.h:365
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:493
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:63
enum Proprule PROPRULE
Definition: cons_and.c:165
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:631
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars, int *nupgdconss)
Definition: cons_and.c:1682
SCIP_RETCODE SCIPgetBinvarRepresentatives(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **repvars, SCIP_Bool *negated)
Definition: scip_var.c:1647
Definition: grphload.c:88
#define EXPRGRAPHREFORM_PRIORITY
Definition: cons_and.c:102
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:257
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:51
SCIP_EXPORT void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9061
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1748
static SCIP_DECL_CONSINITLP(consInitlpAnd)
Definition: cons_and.c:4254
static SCIP_RETCODE conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_and.c:222
static SCIP_DECL_CONSGETVARS(consGetVarsAnd)
Definition: cons_and.c:4851
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:533
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8345
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:129
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:219
public data structures and miscellaneous methods
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4376
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2163
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:637
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition: scip_lp.c:1611
#define SCIP_Bool
Definition: def.h:70
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
Definition: cons_and.c:602
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:390
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_and.c:3472
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2891
SCIP_EXPORT SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11712
#define CONSHDLR_NEEDSCONS
Definition: cons_and.c:83
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:331
static SCIP_DECL_CONSCOPY(consCopyAnd)
Definition: cons_and.c:4682
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr, int nvars, SCIP_VAR **vars, SCIP_VAR *resvar, SCIP_Bool checkwhenupgr, SCIP_Bool notremovablewhenupgr)
Definition: cons_and.c:420
SCIP_RETCODE SCIPchgAndConsRemovableFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition: cons_and.c:5293
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17362
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2472
constraint handler for nonlinear constraints
#define SCIP_DECL_CONSEXITPRE(x)
Definition: type_cons.h:165
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4211
#define NMINCOMPARISONS
Definition: cons_and.c:100
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip_var.c:8506
static SCIP_DECL_HASHGETKEY(hashGetKeyAndcons)
Definition: cons_and.c:3273
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:104
methods for debugging
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:1268
public methods for LP management
void SCIPgmlWriteClosing(FILE *file)
Definition: misc.c:687
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8385
#define HASHSIZE_ANDCONS
Definition: cons_and.c:98
public methods for cuts and aggregation rows
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_and.c:174
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyAnd)
Definition: cons_and.c:3872
#define CONSHDLR_MAXPREROUNDS
Definition: cons_and.c:80
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5137
#define DEFAULT_UPGRRESULTANT
Definition: cons_and.c:95
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:124
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8255
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8180
#define DEFAULT_DUALPRESOLVING
Definition: cons_and.c:96
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:65
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1667
SCIP_Real SCIPexprGetMonomialCoef(SCIP_EXPRDATA_MONOMIAL *monomial)
Definition: expr.c:5901
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8335
#define CONSHDLR_DELAYPROP
Definition: cons_and.c:82
Proprule
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17408
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:94
void * SCIPexprgraphGetNodeVar(SCIP_EXPRGRAPH *exprgraph, SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:13066
public methods for the LP relaxation, rows and columns
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2130
static SCIP_DECL_CONSENFOLP(consEnfolpAnd)
Definition: cons_and.c:4326
SCIP_EXPORT int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3184
#define CONSHDLR_EAGERFREQ
Definition: cons_and.c:77
#define CONSHDLR_PROPFREQ
Definition: cons_and.c:76
SCIP_Real * r
Definition: circlepacking.c:50
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17418
methods for sorting joint arrays of various types
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:220
static SCIP_RETCODE analyzeZeroResultant(SCIP *scip, SCIP_CONS *cons, int watchedvar1, int watchedvar2, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1464
public methods for managing events
general public methods
#define MAX(x, y)
Definition: def.h:222
static SCIP_DECL_EXPRGRAPHNODEREFORM(exprgraphnodeReformAnd)
Definition: cons_and.c:3747
static SCIP_RETCODE consdataCatchEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:284
static SCIP_DECL_CONSSEPALP(consSepalpAnd)
Definition: cons_and.c:4272
SCIP_RETCODE SCIPincludeNonlinconsUpgrade(SCIP *scip, SCIP_DECL_NONLINCONSUPGD((*nonlinconsupgd)), SCIP_DECL_EXPRGRAPHNODEREFORM((*nodereform)), int priority, SCIP_Bool active, const char *conshdlrname)
public methods for solutions
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8265
#define DEFAULT_AGGRLINEARIZATION
Definition: cons_and.c:94
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17352
public methods for the probing mode
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:906
SCIP_RETCODE SCIPincludeConshdlrAnd(SCIP *scip)
Definition: cons_and.c:4919
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1539
#define MINGAINPERNMINCOMPARISONS
Definition: cons_and.c:101
#define CONSHDLR_DELAYSEPA
Definition: cons_and.c:81
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1861
static SCIP_RETCODE consdataCatchWatchedEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int *filterpos)
Definition: cons_and.c:237
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10263
static SCIP_RETCODE consdataDropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:310
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2925
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8076
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8205
#define CONSHDLR_SEPAFREQ
Definition: cons_and.c:75
#define SCIP_Real
Definition: def.h:164
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8096
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HASHKEYVAL(hashKeyValAndcons)
Definition: cons_and.c:3327
SCIP_EXPRGRAPHNODE ** SCIPexprgraphGetNodeChildren(SCIP_EXPRGRAPHNODE *node)
Definition: expr.c:12984
static void consdataSort(SCIP_CONSDATA *consdata)
Definition: cons_and.c:725
#define SCIP_Longint
Definition: def.h:149
static SCIP_DECL_CONSGETNVARS(consGetNVarsAnd)
Definition: cons_and.c:4872
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8355
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
SCIP_EXPORT SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:10972
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:256
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2032
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:344
static SCIP_DECL_CONSRESPROP(consRespropAnd)
Definition: cons_and.c:4634
constraint handler for pseudoboolean constraints
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17045
static SCIP_DECL_CONSCHECK(consCheckAnd)
Definition: cons_and.c:4367
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2765
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:50
SCIP_EXPORT SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:11804
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1720
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:120
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:9119
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:198
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:427
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:6692
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1109
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8305
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8084
#define CONSHDLR_DESC
Definition: cons_and.c:71
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:485
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:355
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:792
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:265
#define SCIPcombineTwoInt(a, b)
Definition: pub_misc.h:499
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8469
#define SCIPABORT()
Definition: def.h:337
public methods for global and local (sub)problems
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
Definition: cons_and.c:1143
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8295
SCIP_EXPORT void SCIPvarsGetProbvar(SCIP_VAR **vars, int nvars)
Definition: var.c:11692
#define CONSHDLR_ENFOPRIORITY
Definition: cons_and.c:73
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int *nchgcoefs)
Definition: cons_and.c:806
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:608
static SCIP_RETCODE analyzeConflictOne(SCIP *scip, SCIP_CONS *cons, int falsepos)
Definition: cons_and.c:1192
SCIP_EXPORT int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17035
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8325
static SCIP_DECL_CONSLOCK(consLockAnd)
Definition: cons_and.c:4644
SCIP_EXPORT int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11436
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
memory allocation routines