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