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 solval;
1124  SCIP_Real minsolval;
1125  SCIP_Real sumsolval;
1126  SCIP_Real viol;
1127  int minsolind;
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  minsolind = 0;
1139  minsolval = 1.0;
1140  sumsolval = 0.0;
1141 
1142  /* evaluate operator variables */
1143  for( i = 0; i < consdata->nvars; ++i )
1144  {
1145  solval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
1146 
1147  if( solval < minsolval )
1148  {
1149  minsolind = i;
1150  minsolval = solval;
1151  }
1152 
1153  sumsolval += solval;
1154  }
1155 
1156  /* the resultant must be at most as large as every operator
1157  * and at least as large as one minus the sum of negated operators
1158  */
1159  solval = SCIPgetSolVal(scip, sol, consdata->resvar);
1160  viol = MAX3(0.0, solval - minsolval, sumsolval - (consdata->nvars - 1.0 + solval));
1161 
1162  if( SCIPisFeasPositive(scip, viol) )
1163  {
1164  *violated = TRUE;
1165 
1166  /* only reset constraint age if we are in enforcement */
1167  if( sol == NULL )
1168  {
1169  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1170  }
1171 
1172  if( printreason )
1173  {
1174  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
1175  SCIPinfoMessage(scip, NULL, ";\n");
1176  SCIPinfoMessage(scip, NULL, "violation:");
1177 
1178  if( SCIPisFeasPositive(scip, solval - minsolval) )
1179  {
1180  SCIPinfoMessage(scip, NULL, " operand <%s> = FALSE and resultant <%s> = TRUE\n",
1181  SCIPvarGetName(consdata->vars[minsolind]), SCIPvarGetName(consdata->resvar));
1182  }
1183  else
1184  {
1185  SCIPinfoMessage(scip, NULL, " all operands are TRUE and resultant <%s> = FALSE\n",
1186  SCIPvarGetName(consdata->resvar));
1187  }
1188  }
1189  }
1190 
1191  if( sol != NULL )
1192  SCIPupdateSolConsViolation(scip, sol, viol, viol);
1193  }
1194 
1195  return SCIP_OKAY;
1196 }
1197 
1198 /** separates given primal solution */
1199 static
1201  SCIP* scip, /**< SCIP data structure */
1202  SCIP_CONS* cons, /**< constraint to check */
1203  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1204  SCIP_Bool* separated, /**< pointer to store whether a cut was found */
1205  SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1206  )
1207 {
1208  SCIP_CONSDATA* consdata;
1209  SCIP_Real feasibility;
1210  int r;
1211 
1212  assert(separated != NULL);
1213  assert(cutoff != NULL);
1214 
1215  *separated = FALSE;
1216  *cutoff = FALSE;
1217 
1218  consdata = SCIPconsGetData(cons);
1219  assert(consdata != NULL);
1220 
1221  /* create all necessary rows for the linear relaxation */
1222  if( consdata->rows == NULL )
1223  {
1224  SCIP_CALL( createRelaxation(scip, cons) );
1225  }
1226  assert(consdata->rows != NULL);
1227 
1228  /* test all rows for feasibility and add infeasible rows */
1229  for( r = 0; r < consdata->nrows; ++r )
1230  {
1231  if( !SCIProwIsInLP(consdata->rows[r]) )
1232  {
1233  feasibility = SCIPgetRowSolFeasibility(scip, consdata->rows[r], sol);
1234  if( SCIPisFeasNegative(scip, feasibility) )
1235  {
1236  SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, cutoff) );
1237  if ( *cutoff )
1238  return SCIP_OKAY;
1239  *separated = TRUE;
1240  }
1241  }
1242  }
1243 
1244  return SCIP_OKAY;
1245 }
1246 
1247 /** analyzes conflicting TRUE assignment to resultant of given constraint, and adds conflict constraint to problem */
1248 static
1250  SCIP* scip, /**< SCIP data structure */
1251  SCIP_CONS* cons, /**< AND-constraint that detected the conflict */
1252  int falsepos /**< position of operand that is fixed to FALSE */
1253  )
1254 {
1255  SCIP_CONSDATA* consdata;
1256 
1257  /* conflict analysis can only be applied in solving stage and if it turned on */
1259  return SCIP_OKAY;
1260 
1261  consdata = SCIPconsGetData(cons);
1262  assert(consdata != NULL);
1263  assert(SCIPvarGetLbLocal(consdata->resvar) > 0.5);
1264  assert(0 <= falsepos && falsepos < consdata->nvars);
1265  assert(SCIPvarGetUbLocal(consdata->vars[falsepos]) < 0.5);
1266 
1267  /* initialize conflict analysis, and add resultant and single operand variable to conflict candidate queue */
1269 
1270  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1271  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[falsepos]) );
1272 
1273  /* analyze the conflict */
1274  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1275 
1276  return SCIP_OKAY;
1277 }
1278 
1279 /** analyzes conflicting FALSE assignment to resultant of given constraint, and adds conflict constraint to problem */
1280 static
1282  SCIP* scip, /**< SCIP data structure */
1283  SCIP_CONS* cons /**< or constraint that detected the conflict */
1284  )
1285 {
1286  SCIP_CONSDATA* consdata;
1287  int v;
1288 
1289  assert(!SCIPconsIsModifiable(cons));
1290 
1291  /* conflict analysis can only be applied in solving stage and if it is applicable */
1293  return SCIP_OKAY;
1294 
1295  consdata = SCIPconsGetData(cons);
1296  assert(consdata != NULL);
1297  assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
1298 
1299  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1301 
1302  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1303  for( v = 0; v < consdata->nvars; ++v )
1304  {
1305  assert(SCIPvarGetLbLocal(consdata->vars[v]) > 0.5);
1306  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
1307  }
1308 
1309  /* analyze the conflict */
1310  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1311 
1312  return SCIP_OKAY;
1313 }
1314 
1315 /** tries to fix the given resultant to zero */
1316 static
1318  SCIP* scip, /**< SCIP data structure */
1319  SCIP_CONS* cons, /**< AND-constraint to be processed */
1320  SCIP_VAR* resvar, /**< resultant variable to fix to zero */
1321  int pos, /**< position of operand that is fixed to FALSE */
1322  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1323  int* nfixedvars /**< pointer to add up the number of found domain reductions */
1324  )
1325 {
1326  SCIP_Bool infeasible;
1327  SCIP_Bool tightened;
1328 
1329  SCIPdebugMsg(scip, "constraint <%s>: operator %d fixed to 0.0 -> fix resultant <%s> to 0.0\n",
1330  SCIPconsGetName(cons), pos, SCIPvarGetName(resvar));
1331 
1332  SCIP_CALL( SCIPinferBinvarCons(scip, resvar, FALSE, cons, (int)PROPRULE_1, &infeasible, &tightened) );
1333 
1334  if( infeasible )
1335  {
1336  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1337  SCIP_CALL( analyzeConflictOne(scip, cons, pos) );
1338  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1339  (*cutoff) = TRUE;
1340  }
1341  else
1342  {
1343  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1344  if( tightened )
1345  {
1346  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1347  (*nfixedvars)++;
1348  }
1349  }
1350 
1351  return SCIP_OKAY;
1352 }
1353 
1354 /** fix all operands to one */
1355 static
1357  SCIP* scip, /**< SCIP data structure */
1358  SCIP_CONS* cons, /**< AND-constraint to be processed */
1359  SCIP_VAR** vars, /**< array of operands */
1360  int nvars, /**< number of operands */
1361  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1362  int* nfixedvars /**< pointer to add up the number of found domain reductions */
1363  )
1364 {
1365  SCIP_Bool infeasible;
1366  SCIP_Bool tightened;
1367  int v;
1368 
1369  for( v = 0; v < nvars && !(*cutoff); ++v )
1370  {
1371  SCIPdebugMsg(scip, "constraint <%s>: resultant fixed to 1.0 -> fix operator var <%s> to 1.0\n",
1372  SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
1373 
1374  SCIP_CALL( SCIPinferBinvarCons(scip, vars[v], TRUE, cons, (int)PROPRULE_2, &infeasible, &tightened) );
1375 
1376  if( infeasible )
1377  {
1378  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1379  SCIP_CALL( analyzeConflictOne(scip, cons, v) );
1380  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1381  (*cutoff) = TRUE;
1382  }
1383  else if( tightened )
1384  {
1385  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1386  (*nfixedvars)++;
1387  }
1388  }
1389 
1390  if( !(*cutoff) )
1391  {
1392  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1393  }
1394 
1395  return SCIP_OKAY;
1396 }
1397 
1398 /** linearize AND-constraint due to a globally to zero fixed resultant; that is, creates, adds, and releases a logicor
1399  * constraint and remove the AND-constraint globally.
1400  *
1401  * Since the resultant is fixed to zero the AND-constraint collapses to linear constraint of the form:
1402  *
1403  * - \f$\sum_{i=0}^{n-1} v_i \leq n-1\f$
1404  *
1405  * This can be transformed into a logicor constraint of the form
1406  *
1407  * - \f$\sum_{i=0}^{n-1} ~v_i \geq 1\f$
1408  */
1409 static
1411  SCIP* scip, /**< SCIP data structure */
1412  SCIP_CONS* cons, /**< AND-constraint to linearize */
1413  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1414  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1415  int* nupgdconss /**< pointer to add up the number of upgraded constraints */
1416  )
1417 {
1418  SCIP_CONSDATA* consdata;
1419  SCIP_VAR** vars;
1420  SCIP_CONS* lincons;
1421  SCIP_Bool conscreated;
1422  int nvars;
1423 
1424  consdata = SCIPconsGetData(cons);
1425  assert(consdata != NULL);
1426 
1427  assert(!(*cutoff));
1428  assert(SCIPvarGetUbGlobal(consdata->resvar) < 0.5);
1429 
1430  nvars = consdata->nvars;
1431  conscreated = FALSE;
1432 
1433  /* allocate memory for variables for updated constraint */
1434  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1435 
1436  /* if we only have two variables, we prefer a set packing constraint instead of a logicor constraint */
1437  if( nvars == 2 && !SCIPconsIsModifiable(cons) )
1438  {
1439  SCIP_Bool* negated;
1440  SCIP_Bool infeasible;
1441  SCIP_Bool tightened;
1442 
1443  /* get active representation */
1444  SCIP_CALL( SCIPallocBufferArray(scip, &negated, nvars) );
1445  SCIP_CALL( SCIPgetBinvarRepresentatives(scip, nvars, consdata->vars, vars, negated) );
1446  SCIPfreeBufferArray(scip, &negated);
1447 
1448  /* if one of the two operators is globally fixed to one it follows that the other has to be zero */
1449  if( SCIPvarGetLbGlobal(vars[0]) > 0.5 )
1450  {
1451  SCIP_CALL( SCIPfixVar(scip, vars[1], 0.0, &infeasible, &tightened) );
1452 
1453  if( infeasible )
1454  *cutoff = TRUE;
1455  else if( tightened )
1456  ++(*nfixedvars);
1457  }
1458  else if( SCIPvarGetLbGlobal(vars[1]) > 0.5 )
1459  {
1460  SCIP_CALL( SCIPfixVar(scip, vars[0], 0.0, &infeasible, &tightened) );
1461 
1462  if( infeasible )
1463  *cutoff = TRUE;
1464  else if( tightened )
1465  ++(*nfixedvars);
1466  }
1467  else if( SCIPvarGetUbGlobal(vars[0]) > 0.5 && SCIPvarGetUbGlobal(vars[1]) > 0.5 )
1468  {
1469  /* create, add, and release the setppc constraint */
1470  SCIP_CALL( SCIPcreateConsSetpack(scip, &lincons, SCIPconsGetName(cons), nvars, vars,
1472  consdata->checkwhenupgr || SCIPconsIsChecked(cons),
1474  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1475 
1476  conscreated = TRUE;
1477  }
1478  }
1479  else
1480  {
1481  int v;
1482 
1483  /* collect negated variables */
1484  for( v = 0; v < nvars; ++v )
1485  {
1486  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &vars[v]) );
1487  }
1488 
1489  /* create, add, and release the logicor constraint */
1490  SCIP_CALL( SCIPcreateConsLogicor(scip, &lincons, SCIPconsGetName(cons), nvars, vars,
1492  consdata->checkwhenupgr || SCIPconsIsChecked(cons),
1494  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1495 
1496  conscreated = TRUE;
1497  }
1498 
1499  if( conscreated )
1500  {
1501  /* add and release new constraint */
1502  SCIPdebugPrintCons(scip, lincons, NULL); /*lint !e644*/
1503  SCIP_CALL( SCIPaddCons(scip, lincons) ); /*lint !e644*/
1504  SCIP_CALL( SCIPreleaseCons(scip, &lincons) ); /*lint !e644*/
1505 
1506  ++(*nupgdconss);
1507  }
1508 
1509  /* remove the AND-constraint globally */
1510  SCIP_CALL( SCIPdelCons(scip, cons) );
1511 
1512  /* delete temporary memory */
1513  SCIPfreeBufferArray(scip, &vars);
1514 
1515  return SCIP_OKAY;
1516 }
1517 
1518 /** the resultant is fixed to zero; in case all except one operator are fixed to TRUE the last operator has to fixed to FALSE */
1519 /** @note consdata->watchedvars might not be the same to the watchedvar parameters, because the update was not yet done */
1520 static
1522  SCIP* scip, /**< SCIP data structure */
1523  SCIP_CONS* cons, /**< AND-constraint to be processed */
1524  int watchedvar1, /**< maybe last unfixed variable position */
1525  int watchedvar2, /**< second watched position */
1526  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1527  int* nfixedvars /**< pointer to add up the number of found domain reductions */
1528  )
1529 {
1530  SCIP_CONSDATA* consdata;
1531 
1532  consdata = SCIPconsGetData(cons);
1533  assert(consdata != NULL);
1534  assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
1535 
1536  if( watchedvar2 == -1 )
1537  {
1538  SCIP_Bool infeasible;
1539  SCIP_Bool tightened;
1540 
1541  assert(watchedvar1 != -1);
1542 
1543 #ifndef NDEBUG
1544  /* check that all variables regardless of wathcedvar1 are fixed to 1 */
1545  {
1546  int v;
1547 
1548  for( v = consdata->nvars - 1; v >= 0; --v )
1549  if( v != watchedvar1 )
1550  assert(SCIPvarGetLbLocal(consdata->vars[v]) > 0.5);
1551  }
1552 #endif
1553 
1554  SCIPdebugMsg(scip, "constraint <%s>: resultant <%s> fixed to 0.0, only one unfixed operand -> fix operand <%s> to 0.0\n",
1555  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar), SCIPvarGetName(consdata->vars[watchedvar1]));
1556 
1557  SCIP_CALL( SCIPinferBinvarCons(scip, consdata->vars[watchedvar1], FALSE, cons, (int)PROPRULE_4, &infeasible, &tightened) );
1558 
1559  if( infeasible )
1560  {
1561  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1562  SCIP_CALL( analyzeConflictZero(scip, cons) );
1563  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1564  *cutoff = TRUE;
1565  }
1566  else
1567  {
1568  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1569  if( tightened )
1570  {
1571  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1572  (*nfixedvars)++;
1573  }
1574  }
1575  }
1576 
1577  return SCIP_OKAY;
1578 }
1579 
1580 /** replaces multiple occurrences of variables */
1581 static
1583  SCIP* scip, /**< SCIP data structure */
1584  SCIP_CONS* cons, /**< AND-constraint */
1585  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1586  unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
1587  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
1588  int* nfixedvars, /**< pointer to store number of fixed variables */
1589  int* nchgcoefs, /**< pointer to store number of changed coefficients */
1590  int* ndelconss /**< pointer to store number of deleted constraints */
1591  )
1592 {
1593  SCIP_CONSDATA* consdata;
1594  SCIP_VAR** vars;
1595  SCIP_VAR* var;
1596  SCIP_VAR* probvar;
1597  int probidx;
1598  int nvars;
1599  int v;
1600 #ifndef NDEBUG
1601  int nbinvars;
1602  int nintvars;
1603  int nimplvars;
1604 #endif
1605 
1606  assert(scip != NULL);
1607  assert(cons != NULL);
1608  assert(eventhdlr != NULL);
1609  assert(*entries != NULL);
1610  assert(nentries != NULL);
1611  assert(nfixedvars != NULL);
1612  assert(nchgcoefs != NULL);
1613  assert(ndelconss != NULL);
1614 
1615  consdata = SCIPconsGetData(cons);
1616  assert(consdata != NULL);
1617 
1618  if( consdata->merged )
1619  return SCIP_OKAY;
1620 
1621  /* nothing to merge */
1622  if( consdata->nvars <= 1 )
1623  {
1624  consdata->merged = TRUE;
1625  return SCIP_OKAY;
1626  }
1627 
1628  vars = consdata->vars;
1629  nvars = consdata->nvars;
1630 
1631  assert(vars != NULL);
1632  assert(nvars >= 2);
1633 
1634 #ifndef NDEBUG
1635  nbinvars = SCIPgetNBinVars(scip);
1636  nintvars = SCIPgetNIntVars(scip);
1637  nimplvars = SCIPgetNImplVars(scip);
1638  assert(*nentries >= nbinvars + nintvars + nimplvars);
1639 #endif
1640 
1641  /* initialize entries array */
1642  for( v = nvars - 1; v >= 0; --v )
1643  {
1644  var = vars[v];
1645  assert(var != NULL);
1646  assert(SCIPvarIsActive(var) || (SCIPvarIsNegated(var) && SCIPvarIsActive(SCIPvarGetNegatedVar(var))));
1647 
1648  probvar = (SCIPvarIsActive(var) ? var : SCIPvarGetNegatedVar(var));
1649  assert(probvar != NULL);
1650 
1651  probidx = SCIPvarGetProbindex(probvar);
1652  assert(0 <= probidx);
1653 
1654  /* check variable type, either pure binary or an integer/implicit integer variable with 0/1 bounds */
1655  assert((probidx < nbinvars && SCIPvarGetType(probvar) == SCIP_VARTYPE_BINARY)
1656  || (SCIPvarIsBinary(probvar) &&
1657  ((probidx >= nbinvars && probidx < nbinvars + nintvars && SCIPvarGetType(probvar) == SCIP_VARTYPE_INTEGER) ||
1658  (probidx >= nbinvars + nintvars && probidx < nbinvars + nintvars + nimplvars &&
1659  SCIPvarGetType(probvar) == SCIP_VARTYPE_IMPLINT))));
1660 
1661  /* var is not active yet */
1662  (*entries)[probidx] = 0;
1663  }
1664 
1665  /* search for multiple variables; scan from back to front because deletion doesn't affect the order of the front
1666  * variables
1667  * @note don't reorder variables because we would loose the watched variables and filter position inforamtion
1668  */
1669  for( v = nvars - 1; v >= 0; --v )
1670  {
1671  var = vars[v];
1672  assert(var != NULL);
1673  assert(SCIPvarIsActive(var) || (SCIPvarIsNegated(var) && SCIPvarIsActive(SCIPvarGetNegatedVar(var))));
1674 
1675  probvar = (SCIPvarIsActive(var) ? var : SCIPvarGetNegatedVar(var));
1676  assert(probvar != NULL);
1677 
1678  probidx = SCIPvarGetProbindex(probvar);
1679  assert(0 <= probidx && probidx < *nentries);
1680 
1681  /* if var occurs first time in constraint init entries array */
1682  if( (*entries)[probidx] == 0 )
1683  {
1684  (*entries)[probidx] = (SCIPvarIsActive(var) ? 1 : 2);
1685  }
1686  /* if var occurs second time in constraint, first time it was not negated */
1687  else if( ((*entries)[probidx] == 1 && SCIPvarIsActive(var)) || ((*entries)[probidx] == 2 && !SCIPvarIsActive(var)) )
1688  {
1689  /* delete the multiple variable */
1690  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1691  ++(*nchgcoefs);
1692  }
1693  else
1694  {
1695  SCIP_Bool infeasible;
1696  SCIP_Bool fixed;
1697 
1698  assert(((*entries)[probidx] == 1 && !SCIPvarIsActive(var)) || ((*entries)[probidx] == 2 && SCIPvarIsActive(var)));
1699 
1700  SCIPdebugMsg(scip, "AND-constraint <%s> is redundant: variable <%s> and its negation are present -> fix resultant <%s> = 0\n",
1701  SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetName(consdata->resvar));
1702 
1703  /* negation of the variable is already present in the constraint: fix resultant to zero */
1704 #ifndef NDEBUG
1705  {
1706  int i;
1707  for( i = consdata->nvars - 1; i > v && var != SCIPvarGetNegatedVar(vars[i]); --i )
1708  {}
1709  assert(i > v);
1710  }
1711 #endif
1712 
1713  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
1714  assert(!infeasible);
1715  if( fixed )
1716  ++(*nfixedvars);
1717 
1718  SCIP_CALL( SCIPdelCons(scip, cons) );
1719  break;
1720  }
1721  }
1722 
1723  consdata->merged = TRUE;
1724 
1725  return SCIP_OKAY;
1726 }
1727 
1728 /** propagates constraint with the following rules:
1729  * (1) v_i = FALSE => r = FALSE
1730  * (2) r = TRUE => v_i = TRUE for all i
1731  * (3) v_i = TRUE for all i => r = TRUE
1732  * (4) r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
1733  *
1734  * additional if the resultant is fixed to zero during presolving or in the root node (globally), then the
1735  * AND-constraint is collapsed to a linear (logicor) constraint of the form
1736  * -> sum_{i=0}^{n-1} ~v_i >= 1
1737  */
1738 static
1740  SCIP* scip, /**< SCIP data structure */
1741  SCIP_CONS* cons, /**< AND-constraint to be processed */
1742  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1743  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1744  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1745  int* nupgdconss /**< pointer to add up the number of upgraded constraints */
1746  )
1747 {
1748  SCIP_CONSDATA* consdata;
1749  SCIP_VAR* resvar;
1750  SCIP_VAR** vars;
1751  int nvars;
1752  int watchedvar1;
1753  int watchedvar2;
1754  int i;
1755  SCIP_Bool infeasible;
1756  SCIP_Bool tightened;
1757 
1758  assert(cutoff != NULL);
1759  assert(nfixedvars != NULL);
1760 
1761  consdata = SCIPconsGetData(cons);
1762  assert(consdata != NULL);
1763 
1764  resvar = consdata->resvar;
1765  vars = consdata->vars;
1766  nvars = consdata->nvars;
1767 
1768  /* don't process the constraint, if none of the operator variables was fixed to FALSE, and if the watched variables
1769  * and the resultant weren't fixed to any value since last propagation call
1770  */
1771  if( consdata->propagated )
1772  {
1773  assert(consdata->nofixedzero);
1774  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(resvar), 0.0));
1775  return SCIP_OKAY;
1776  }
1777 
1778  /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
1779  if( !SCIPinRepropagation(scip) )
1780  {
1781  SCIP_CALL( SCIPincConsAge(scip, cons) );
1782  }
1783 
1784  /* if one of the operator variables was fixed to FALSE, the resultant can be fixed to FALSE (rule (1)) */
1785  if( !consdata->nofixedzero )
1786  {
1787  for( i = 0; i < nvars && SCIPvarGetUbLocal(vars[i]) > 0.5; ++i ) /* search for operator fixed to zero */
1788  {}
1789  if( i < nvars )
1790  {
1791  /* fix resultant to zero */
1792  SCIP_CALL( consdataFixResultantZero(scip, cons, resvar, i, cutoff, nfixedvars) );
1793  }
1794  else
1795  consdata->nofixedzero = TRUE;
1796  }
1797 
1798  /* check if resultant variables is globally fixed to zero */
1799  if( !SCIPinProbing(scip) && SCIPvarGetUbGlobal(resvar) < 0.5 )
1800  {
1801  SCIP_CALL( consdataLinearize(scip, cons, cutoff, nfixedvars, nupgdconss) );
1802 
1803  if( *cutoff && SCIPgetDepth(scip) > 0 )
1804  {
1805  /* we are done with solving since a global bound change was infeasible */
1806  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
1807  }
1808 
1809  return SCIP_OKAY;
1810  }
1811 
1812  /* if the resultant and at least one operand are locally fixed to zero, the constraint is locally redundant */
1813  if( SCIPvarGetUbLocal(resvar) < 0.5 && !consdata->nofixedzero )
1814  {
1815  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1816  return SCIP_OKAY;
1817  }
1818 
1819  /* if resultant is fixed to TRUE, all operator variables can be fixed to TRUE (rule (2)) */
1820  if( SCIPvarGetLbLocal(resvar) > 0.5 )
1821  {
1822  /* fix operands to one */
1823  SCIP_CALL( consdataFixOperandsOne(scip, cons, vars, nvars, cutoff, nfixedvars) );
1824 
1825  return SCIP_OKAY;
1826  }
1827 
1828  /* rules (3) and (4) can only be applied, if we know all operator variables */
1829  if( SCIPconsIsModifiable(cons) )
1830  return SCIP_OKAY;
1831 
1832  /* rules (3) and (4) cannot be applied, if we have at least two unfixed variables left;
1833  * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
1834  * if these ones get fixed
1835  */
1836  watchedvar1 = consdata->watchedvar1;
1837  watchedvar2 = consdata->watchedvar2;
1838 
1839  /* check, if watched variables are still unfixed */
1840  if( watchedvar1 != -1 )
1841  {
1842  assert(SCIPvarGetUbLocal(vars[watchedvar1]) > 0.5); /* otherwise, rule (1) could be applied */
1843  if( SCIPvarGetLbLocal(vars[watchedvar1]) > 0.5 )
1844  watchedvar1 = -1;
1845  }
1846  if( watchedvar2 != -1 )
1847  {
1848  assert(SCIPvarGetUbLocal(vars[watchedvar2]) > 0.5); /* otherwise, rule (1) could be applied */
1849  if( SCIPvarGetLbLocal(vars[watchedvar2]) > 0.5 )
1850  watchedvar2 = -1;
1851  }
1852 
1853  /* if only one watched variable is still unfixed, make it the first one */
1854  if( watchedvar1 == -1 )
1855  {
1856  watchedvar1 = watchedvar2;
1857  watchedvar2 = -1;
1858  }
1859  assert(watchedvar1 != -1 || watchedvar2 == -1);
1860 
1861  /* if the watched variables are invalid (fixed), find new ones if existing */
1862  if( watchedvar2 == -1 )
1863  {
1864  for( i = 0; i < nvars; ++i )
1865  {
1866  assert(SCIPvarGetUbLocal(vars[i]) > 0.5); /* otherwise, rule (1) could be applied */
1867  if( SCIPvarGetLbLocal(vars[i]) < 0.5 )
1868  {
1869  if( watchedvar1 == -1 )
1870  {
1871  assert(watchedvar2 == -1);
1872  watchedvar1 = i;
1873  }
1874  else if( watchedvar1 != i )
1875  {
1876  watchedvar2 = i;
1877  break;
1878  }
1879  }
1880  }
1881  }
1882  assert(watchedvar1 != -1 || watchedvar2 == -1);
1883 
1884  /* if all variables are fixed to TRUE, the resultant can also be fixed to TRUE (rule (3)) */
1885  if( watchedvar1 == -1 )
1886  {
1887  assert(watchedvar2 == -1);
1888 
1889  SCIPdebugMsg(scip, "constraint <%s>: all operator vars fixed to 1.0 -> fix resultant <%s> to 1.0\n",
1890  SCIPconsGetName(cons), SCIPvarGetName(resvar));
1891  SCIP_CALL( SCIPinferBinvarCons(scip, resvar, TRUE, cons, (int)PROPRULE_3, &infeasible, &tightened) );
1892 
1893  if( infeasible )
1894  {
1895  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1896  SCIP_CALL( analyzeConflictZero(scip, cons) );
1897  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1898  *cutoff = TRUE;
1899  }
1900  else
1901  {
1902  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1903  if( tightened )
1904  {
1905  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1906  (*nfixedvars)++;
1907  }
1908  }
1909 
1910  return SCIP_OKAY;
1911  }
1912 
1913  /* if resultant is fixed to FALSE, and only one operator variable is not fixed to TRUE, this operator variable
1914  * can be fixed to FALSE (rule (4))
1915  */
1916  if( watchedvar2 == -1 && SCIPvarGetUbLocal(resvar) < 0.5 )
1917  {
1918  assert(watchedvar1 != -1);
1919 
1920  SCIP_CALL( analyzeZeroResultant(scip, cons, watchedvar1, watchedvar2, cutoff, nfixedvars) );
1921 
1922  return SCIP_OKAY;
1923  }
1924 
1925  /* switch to the new watched variables */
1926  SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
1927 
1928  /* mark the constraint propagated if we have an unfixed resultant or are not in probing, it is necessary that a fixed
1929  * resulting in probing mode does not lead to a propagated constraint, because the constraint upgrade needs to be performed
1930  */
1931  consdata->propagated = (!SCIPinProbing(scip) || (SCIPvarGetLbLocal(consdata->resvar) < 0.5 && SCIPvarGetUbLocal(consdata->resvar) > 0.5));
1932 
1933  return SCIP_OKAY;
1934 }
1935 
1936 /** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
1937  * propagation rule (see propagateCons()):
1938  * (1) v_i = FALSE => r = FALSE
1939  * (2) r = TRUE => v_i = TRUE for all i
1940  * (3) v_i = TRUE for all i => r = TRUE
1941  * (4) r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
1942  */
1943 static
1945  SCIP* scip, /**< SCIP data structure */
1946  SCIP_CONS* cons, /**< constraint that inferred the bound change */
1947  SCIP_VAR* infervar, /**< variable that was deduced */
1948  PROPRULE proprule, /**< propagation rule that deduced the value */
1949  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1950  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1951  )
1952 {
1953  SCIP_CONSDATA* consdata;
1954  SCIP_VAR** vars;
1955  int nvars;
1956  int i;
1957 
1958  assert(result != NULL);
1959 
1960  consdata = SCIPconsGetData(cons);
1961  assert(consdata != NULL);
1962  vars = consdata->vars;
1963  nvars = consdata->nvars;
1964 
1965  switch( proprule )
1966  {
1967  case PROPRULE_1:
1968  /* the resultant was inferred to FALSE, because one operand variable was FALSE */
1969  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
1970  assert(infervar == consdata->resvar);
1971  for( i = 0; i < nvars; ++i )
1972  {
1973  if( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
1974  {
1975  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
1976  break;
1977  }
1978  }
1979  assert(i < nvars);
1980  *result = SCIP_SUCCESS;
1981  break;
1982 
1983  case PROPRULE_2:
1984  /* the operand variable was inferred to TRUE, because the resultant was TRUE */
1985  assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1986  assert(SCIPgetVarLbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) > 0.5);
1987  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1988  *result = SCIP_SUCCESS;
1989  break;
1990 
1991  case PROPRULE_3:
1992  /* the resultant was inferred to TRUE, because all operand variables were TRUE */
1993  assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1994  assert(infervar == consdata->resvar);
1995  for( i = 0; i < nvars; ++i )
1996  {
1997  assert(SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5);
1998  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
1999  }
2000  *result = SCIP_SUCCESS;
2001  break;
2002 
2003  case PROPRULE_4:
2004  /* the operand variable was inferred to FALSE, because the resultant was FALSE and all other operands were TRUE */
2005  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2006  assert(SCIPgetVarUbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) < 0.5);
2007  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
2008  for( i = 0; i < nvars; ++i )
2009  {
2010  if( vars[i] != infervar )
2011  {
2012  assert(SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5);
2013  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i]) );
2014  }
2015  }
2016  *result = SCIP_SUCCESS;
2017  break;
2018 
2019  case PROPRULE_INVALID:
2020  default:
2021  SCIPerrorMessage("invalid inference information %d in AND-constraint <%s>\n", proprule, SCIPconsGetName(cons));
2022  return SCIP_INVALIDDATA;
2023  }
2024 
2025  return SCIP_OKAY;
2026 }
2027 
2028 /** perform dual presolving on AND-constraints */
2029 static
2031  SCIP* scip, /**< SCIP data structure */
2032  SCIP_CONS** conss, /**< AND-constraints to perform dual presolving on */
2033  int nconss, /**< number of AND-constraints */
2034  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2035  unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
2036  int* nentries, /**< pointer for array size, if array will be to small it's corrected */
2037  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2038  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
2039  int* naggrvars, /**< pointer to add up the number of aggregated variables */
2040  int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
2041  int* ndelconss, /**< pointer to add up the number of deleted constraints */
2042  int* nupgdconss, /**< pointer to add up the number of upgraded constraints */
2043  int* naddconss /**< pointer to add up the number of added constraints */
2044  )
2045 {
2046  SCIP_CONS* cons;
2047  SCIP_CONSDATA* consdata;
2048  SCIP_VAR** impoperands;
2049  SCIP_VAR** vars;
2050  SCIP_VAR* resvar;
2051  SCIP_VAR* var;
2052  int nimpoperands;
2053  int nvars;
2054  int size;
2055  int v;
2056  int c;
2057  SCIP_Bool infeasible;
2058  SCIP_Bool fixed;
2059 
2060  assert(scip != NULL);
2061  assert(conss != NULL || nconss == 0);
2062  assert(eventhdlr != NULL);
2063  assert(*entries != NULL);
2064  assert(nentries != NULL);
2065  assert(cutoff != NULL);
2066  assert(nfixedvars != NULL);
2067  assert(naggrvars != NULL);
2068  assert(nchgcoefs != NULL);
2069  assert(ndelconss != NULL);
2070  assert(nupgdconss != NULL);
2071  assert(naddconss != NULL);
2072 
2073  if( nconss == 0 )
2074  return SCIP_OKAY;
2075 
2076  assert(conss != NULL);
2077 
2078  size = 2 * (SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip));
2079 
2080  SCIP_CALL( SCIPallocBufferArray(scip, &impoperands, size) );
2081 
2082  for( c = nconss - 1; c >= 0 && !(*cutoff); --c )
2083  {
2084  cons = conss[c];
2085  assert(cons != NULL);
2086 
2087  if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsModifiable(cons) )
2088  continue;
2089 
2090  /* propagate constraint */
2091  SCIP_CALL( propagateCons(scip, cons, eventhdlr, cutoff, nfixedvars, nupgdconss) );
2092 
2093  if( !SCIPconsIsActive(cons) )
2094  continue;
2095 
2096  if( *cutoff )
2097  break;
2098 
2099  SCIP_CALL( applyFixings(scip, cons, eventhdlr, nchgcoefs) );
2100 
2101  /* merge multiple occurances of variables or variables with their negated variables */
2102  SCIP_CALL( mergeMultiples(scip, cons, eventhdlr, entries, nentries, nfixedvars, nchgcoefs, ndelconss) );
2103 
2104  if( !SCIPconsIsActive(cons) )
2105  continue;
2106 
2107  consdata = SCIPconsGetData(cons);
2108  assert(consdata != NULL);
2109 
2110  vars = consdata->vars;
2111  nvars = consdata->nvars;
2112  assert(vars != NULL || nvars == 0);
2113 
2114  if( nvars == 0 )
2115  continue;
2116 
2117  assert(vars != NULL);
2118 
2119  resvar = consdata->resvar;
2120  assert(resvar != NULL);
2121  /* a fixed resultant needs to be removed, otherwise we might fix operands to a wrong value later on */
2122  assert(SCIPvarGetLbGlobal(resvar) < 0.5 && SCIPvarGetUbGlobal(resvar) > 0.5);
2123  assert(SCIPvarGetNLocksUpType(resvar, SCIP_LOCKTYPE_MODEL) >= 1
2125 
2128  {
2129  SCIP_Real resobj;
2130  SCIP_Real obj;
2131  SCIP_Real posobjsum = 0;
2132  SCIP_Real maxobj = -SCIPinfinity(scip);
2133  int maxpos = -1;
2134  int oldnfixedvars = *nfixedvars;
2135  int oldnaggrvars = *naggrvars;
2136 
2137  nimpoperands = 0;
2138 
2139  /* collect important operands */
2140  for( v = nvars - 1; v >= 0; --v )
2141  {
2142  var = vars[v];
2143  assert(var != NULL);
2146 
2149  {
2150  impoperands[nimpoperands] = var;
2151  ++nimpoperands;
2152 
2153  /* get aggregated objective value of active variable */
2154  SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2155 
2156  /* add up all positive objective values of operands which have exactly one lock in both directions */
2157  if( obj > 0 )
2158  posobjsum += obj;
2159 
2160  /* memorize maximal objective value of operands and its position */
2161  if( obj > maxobj )
2162  {
2163  maxpos = nimpoperands - 1;
2164  maxobj = obj;
2165  }
2166  }
2167  }
2168  assert(nimpoperands >= 0 && nimpoperands <= nvars);
2169 
2170  /* no dual fixable variables found */
2171  if( nimpoperands == 0 )
2172  continue;
2173 
2174  /* get aggregated objective value of active variable */
2175  SCIP_CALL( SCIPvarGetAggregatedObj(resvar, &resobj) );
2176 
2177  /* resultant contributes to the objective with a negative value */
2178  if( SCIPisLE(scip, resobj, 0.0) )
2179  {
2180  SCIP_Bool poscontissmall = SCIPisLE(scip, posobjsum, REALABS(resobj));
2181 
2182  /* if all variables are only locked by this constraint and the resultants contribution more then compensates
2183  * the positive contribution, we can fix all variables to 1
2184  */
2185  if( nimpoperands == nvars && poscontissmall )
2186  {
2187  SCIPdebugMsg(scip, "dual-fixing all variables in constraint <%s> to 1\n", SCIPconsGetName(cons));
2188 
2189  SCIP_CALL( SCIPfixVar(scip, resvar, 1.0, &infeasible, &fixed) );
2190 
2191  *cutoff = *cutoff || infeasible;
2192  if( fixed )
2193  ++(*nfixedvars);
2194 
2195  for( v = nvars - 1; v >= 0 && !(*cutoff); --v )
2196  {
2197  SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, &infeasible, &fixed) );
2198 
2199  *cutoff = *cutoff || infeasible;
2200  if( fixed )
2201  ++(*nfixedvars);
2202  }
2203 
2204  SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are fixed to one\n", SCIPconsGetName(cons));
2205 
2206  SCIP_CALL( SCIPdelCons(scip, cons) );
2207  ++(*ndelconss);
2208  }
2209  else
2210  {
2211  SCIP_Bool aggregationperformed = FALSE;
2212  SCIP_Bool zerofix = FALSE;
2213 
2214  assert(nimpoperands > 0);
2215 
2216  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));
2217 
2218  for( v = nimpoperands - 1; v >= 0 && !(*cutoff); --v )
2219  {
2220  /* get aggregated objective value of active variable */
2221  SCIP_CALL( SCIPvarGetAggregatedObj(impoperands[v], &obj) );
2222 
2223  if( SCIPisLE(scip, obj, 0.0) )
2224  {
2225  SCIP_CALL( SCIPfixVar(scip, impoperands[v], 1.0, &infeasible, &fixed) );
2226 
2227  *cutoff = *cutoff || infeasible;
2228  if( fixed )
2229  ++(*nfixedvars);
2230  }
2231  else if( !poscontissmall )
2232  {
2233  SCIP_CALL( SCIPfixVar(scip, impoperands[v], 0.0, &infeasible, &fixed) );
2234  assert(!infeasible);
2235  assert(fixed);
2236 
2237  ++(*nfixedvars);
2238  zerofix = TRUE;
2239  }
2240  else
2241  {
2242  SCIP_Bool redundant;
2243  SCIP_Bool aggregated;
2244 
2245  /* aggregate resultant to operand */
2246  SCIP_CALL( SCIPaggregateVars(scip, resvar, impoperands[v], 1.0, -1.0, 0.0,
2247  &infeasible, &redundant, &aggregated) );
2248  assert(!infeasible);
2249 
2250  if( aggregated )
2251  {
2252  /* note that we cannot remove the aggregated operand because we do not know the position */
2253  ++(*naggrvars);
2254 
2255  aggregationperformed = TRUE;
2256 
2257  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));
2258  }
2259  }
2260  }
2261  assert(*nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars <= nimpoperands);
2262 
2263  /* did we aggregate the resultant, then we can decide the value to fix it on the (aggregated) objective
2264  * value since it was a independant variable
2265  */
2266  if( aggregationperformed || zerofix )
2267  {
2268  SCIP_Real fixval;
2269 
2270  if( zerofix )
2271  fixval = 0.0;
2272  else
2273  {
2274  /* get aggregated objective value of active variable, that might be changed */
2275  SCIP_CALL( SCIPvarGetAggregatedObj(resvar, &obj) );
2276  assert(!SCIPisPositive(scip, obj));
2277 
2278  fixval = (SCIPisNegative(scip, obj) ? 1.0 : 0.0);
2279  }
2280 
2281  if( fixval < 0.5 || *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars == nvars )
2282  {
2283  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);
2284 
2285  SCIP_CALL( SCIPfixVar(scip, resvar, fixval, &infeasible, &fixed) );
2286  assert(!infeasible);
2287  assert(fixed);
2288 
2289  ++(*nfixedvars);
2290 
2291  SCIPdebugMsg(scip, "deleting constraint <%s> because \n", SCIPconsGetName(cons));
2292 
2293  SCIP_CALL( SCIPdelCons(scip, cons) );
2294  ++(*ndelconss);
2295  }
2296  }
2297  }
2298  }
2299  /* resultant contributes to the objective with a positive value */
2300  else
2301  {
2302  SCIP_Bool zerofix = FALSE;
2303 #ifndef NDEBUG
2304  SCIP_Real tmpobj;
2305 
2306  assert(nimpoperands > 0);
2307  assert(maxpos >= 0 && maxpos <= consdata->nvars);
2308  assert(!SCIPisInfinity(scip, -maxobj));
2309  SCIP_CALL( SCIPvarGetAggregatedObj(impoperands[maxpos], &tmpobj) );
2310  assert(SCIPisEQ(scip, tmpobj, maxobj));
2311 #endif
2312 
2313  /* if the smallest possible contribution is negative, but does not compensate the positive contribution of
2314  * the resultant we need to fix this variable to 0
2315  */
2316  if( nimpoperands == nvars && SCIPisLE(scip, maxobj, 0.0) )
2317  {
2318  SCIP_Real fixval = (SCIPisLE(scip, REALABS(maxobj), resobj) ? 0.0 : 1.0);
2319 
2320  SCIPdebugMsg(scip, "dual-fixing variable <%s> in constraint <%s> to %g, because the contribution is%s " \
2321  "enough to nullify/exceed the contribution of the resultant \n",
2322  SCIPvarGetName(impoperands[maxpos]), SCIPconsGetName(cons), fixval, (fixval < 0.5) ? " not" : "");
2323 
2324  SCIP_CALL( SCIPfixVar(scip, impoperands[maxpos], fixval, &infeasible, &fixed) );
2325  zerofix = (fixval < 0.5);
2326 
2327  *cutoff = *cutoff || infeasible;
2328  if( fixed )
2329  ++(*nfixedvars);
2330  }
2331 
2332  SCIPdebugMsg(scip, "dual-fixing all variables, except the variable with the highest contribution to " \
2333  "the objective, in constraint <%s> with positive contribution to 0 and with negative contribution to 1\n",
2334  SCIPconsGetName(cons));
2335 
2336  for( v = nimpoperands - 1; v >= 0 && !(*cutoff); --v )
2337  {
2338  /* get aggregated objective value of active variable */
2339  SCIP_CALL( SCIPvarGetAggregatedObj(impoperands[v], &obj) );
2340 
2341  if( SCIPisLE(scip, obj, 0.0) )
2342  {
2343  if( v == maxpos )
2344  continue;
2345 
2346  SCIP_CALL( SCIPfixVar(scip, impoperands[v], 1.0, &infeasible, &fixed) );
2347  }
2348  else
2349  {
2350  SCIP_CALL( SCIPfixVar(scip, impoperands[v], 0.0, &infeasible, &fixed) );
2351  zerofix = TRUE;
2352  }
2353 
2354  *cutoff = *cutoff || infeasible;
2355  if( fixed )
2356  ++(*nfixedvars);
2357  }
2358  assert(*nfixedvars - oldnfixedvars <= nimpoperands);
2359  /* iff we have fixed all variables, all variables needed to be stored in the impoperands array */
2360  assert((*nfixedvars - oldnfixedvars == nvars) == (nimpoperands == nvars));
2361 
2362  if( *nfixedvars - oldnfixedvars == nvars )
2363  {
2364  SCIPdebugMsg(scip, "all operands are fixed in constraint <%s> => fix resultant <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(resvar), (zerofix ? 0.0 : 1.0));
2365 
2366  SCIP_CALL( SCIPfixVar(scip, resvar, zerofix ? 0.0 : 1.0, &infeasible, &fixed) );
2367 
2368  *cutoff = *cutoff || infeasible;
2369  if( fixed )
2370  ++(*nfixedvars);
2371 
2372  SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are fixed\n", SCIPconsGetName(cons));
2373 
2374  SCIP_CALL( SCIPdelCons(scip, cons) );
2375  ++(*ndelconss);
2376  }
2377  }
2378  }
2379  /* resultant is lock by another constraint (handler), check for operands with only one down- and uplock */
2380  else
2381  {
2382  SCIP_Real maxobj = -SCIPinfinity(scip);
2383  SCIP_Real resobj;
2384  SCIP_Real obj;
2385  SCIP_Bool redundant;
2386  SCIP_Bool aggregated;
2387  SCIP_Bool resobjispos;
2388  SCIP_Bool linearize = FALSE;
2389  SCIP_Bool zerofix = FALSE;
2390 #ifndef NDEBUG
2391  int oldnchgcoefs = *nchgcoefs;
2392  int oldnfixedvars = *nfixedvars;
2393 #endif
2394 
2395  /* get aggregated objective value of active variable */
2396  SCIP_CALL( SCIPvarGetAggregatedObj(resvar, &resobj) );
2397 
2398  resobjispos = SCIPisGT(scip, resobj, 0.0);
2399 
2400  /* we can only aggregate when the objective contribution of the resultant is less or equal to 0 */
2401  if( !resobjispos )
2402  {
2403  SCIP_Bool goodvarsfound = FALSE;
2404 
2405  for( v = nvars - 1; v >= 0; --v )
2406  {
2407  var = vars[v];
2408  assert(var != NULL);
2411 
2412  /* get aggregated objective value of active variable */
2413  SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2414 
2415  /* all operands which are only locked by this constraint, the objective contribution is greater or equal
2416  * to 0 can be aggregated to the resultant
2417  */
2420  {
2421  if( !SCIPisNegative(scip, obj) )
2422  {
2423  /* aggregate resultant to operand */
2424  SCIP_CALL( SCIPaggregateVars(scip, resvar, var, 1.0, -1.0, 0.0, &infeasible, &redundant,
2425  &aggregated) );
2426 
2427  if( aggregated )
2428  {
2429  ++(*naggrvars);
2430 
2431  linearize = TRUE;
2432 
2433  /* delete redundant entry from constraint */
2434  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
2435  ++(*nchgcoefs);
2436 
2437  SCIPdebugMsg(scip,
2438  "dual aggregating operand <%s> with 1 up- and downlock to the resultant <%s> in constraint <%s>\n",
2439  SCIPvarGetName(var), SCIPvarGetName(resvar), SCIPconsGetName(cons));
2440  }
2441 
2442  *cutoff = *cutoff || infeasible;
2443  }
2444  else
2445  goodvarsfound = TRUE;
2446  }
2447  }
2448  assert(*nchgcoefs - oldnchgcoefs <= nvars);
2449 
2450  /* if we aggregated an operands with the resultant we can also fix "good" independant operands to 1, since
2451  * the correctness of "resultant = 0 => at least one operand = 0" in enforced by that aggregation
2452  * without an aggregation we cannot fix these variables since it might lead to infeasibility, e.g.
2453  *
2454  * obj(x3) = -1
2455  * r = x1 * x2 * x3
2456  * r = 0
2457  * x1 = 1
2458  * x2 = 1
2459  */
2460  if( !*cutoff && goodvarsfound && linearize )
2461  {
2462  /* fix good variables to 1 */
2463  for( v = consdata->nvars - 1; v >= 0; --v )
2464  {
2465  var = vars[v];
2466  assert(var != NULL);
2467 
2470  {
2471 #ifndef NDEBUG
2472  /* aggregated objective value of active variable need to be negative */
2473  SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2474  assert(SCIPisNegative(scip, obj));
2475 #endif
2476  SCIPdebugMsg(scip,
2477  "dual-fixing variable <%s> in constraint <%s> to 1, because the contribution is negative\n",
2478  SCIPvarGetName(var), SCIPconsGetName(cons));
2479 
2480  SCIP_CALL( SCIPfixVar(scip, var, 1.0, &infeasible, &fixed) );
2481 
2482  assert(!infeasible);
2483  if( fixed )
2484  ++(*nfixedvars);
2485  }
2486  }
2487  assert(*nfixedvars - oldnfixedvars <= consdata->nvars);
2488  }
2489  assert(*nchgcoefs - oldnchgcoefs + *nfixedvars - oldnfixedvars <= nvars);
2490  }
2491  /* if the downlocks of the resultant are only from this constraint and the objective contribution is positive,
2492  * we can try to fix operands
2493  */
2494  else if( SCIPvarGetNLocksDownType(resvar, SCIP_LOCKTYPE_MODEL) == 1 )
2495  {
2496  SCIP_Bool locksareone = TRUE;
2497  int maxpos = -1;
2498 
2499  for( v = nvars - 1; v >= 0; --v )
2500  {
2501  var = vars[v];
2502  assert(var != NULL);
2505 
2506  /* check if all resultants are only locked by this constraint */
2507  locksareone = locksareone && (SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 1
2509 
2510  /* get aggregated objective value of active variable */
2511  SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2512 
2513  /* memorize maximal objective value of operands and its position */
2514  if( obj > maxobj )
2515  {
2516  maxpos = v;
2517  maxobj = obj;
2518  }
2519 
2520  /* all operands which are only locked by this constraint, the objective contribution is greater or equal
2521  * to 0, and the absolute value of the contribution of the resultant exceeds can be eliminated and
2522  * aggregated to the resultant
2523  */
2525  && SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 1 && SCIPisGE(scip, obj, 0.0) )
2526  {
2527  SCIPdebugMsg(scip, "dualfix operand <%s> in constraint <%s> to 0\n", SCIPvarGetName(var), SCIPconsGetName(cons));
2528 
2529  SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
2530 
2531  *cutoff = *cutoff || infeasible;
2532  if( fixed )
2533  ++(*nfixedvars);
2534 
2535  zerofix = TRUE;
2536  }
2537  }
2538  assert(*nchgcoefs - oldnchgcoefs <= nvars);
2539 
2540  /* if constraint is still active and all operands are only lock by this constraint, we check if we can fix
2541  * the worst (in objective contribution) operand to zero
2542  */
2543  if( !zerofix && locksareone && SCIPisGE(scip, resobj, REALABS(maxobj)) )
2544  {
2545  assert(!zerofix);
2546  /* objective contribution needs to be negative, otherwise, the variable should already be fixed to 0 */
2547  assert(SCIPisLT(scip, maxobj, 0.0));
2548 
2549  SCIPdebugMsg(scip, "dualfix operand <%s> with worst contribution in constraint <%s> to 0\n", SCIPvarGetName(vars[maxpos]), SCIPconsGetName(cons));
2550 
2551  SCIP_CALL( SCIPfixVar(scip, vars[maxpos], 0.0, &infeasible, &fixed) );
2552 
2553  *cutoff = *cutoff || infeasible;
2554  if( fixed )
2555  ++(*nfixedvars);
2556 
2557  zerofix = TRUE;
2558  }
2559 
2560  /* fix the resultant if one operand was fixed to zero and delete the constraint */
2561  if( zerofix )
2562  {
2563  SCIPdebugMsg(scip, "fix resultant <%s> in constraint <%s> to 0\n", SCIPvarGetName(resvar), SCIPconsGetName(cons));
2564 
2565  SCIP_CALL( SCIPfixVar(scip, resvar, 0.0, &infeasible, &fixed) );
2566 
2567  *cutoff = *cutoff || infeasible;
2568  if( fixed )
2569  ++(*nfixedvars);
2570 
2571  SCIPdebugMsg(scip, "deleting constraint <%s> because at least one operand and the resultant is fixed to zero\n", SCIPconsGetName(cons));
2572 
2573  SCIP_CALL( SCIPdelCons(scip, cons) );
2574  ++(*ndelconss);
2575  }
2576  }
2577 
2578  /* we have to linearize the constraint, otherwise we might get wrong propagations, since due to aggregations a
2579  * resultant fixed to zero is already fulfilling the constraint, and we must not ensure that some remaining
2580  * operand needs to be 0
2581  */
2582  if( linearize )
2583  {
2584  SCIP_CONS* newcons;
2585  char consname[SCIP_MAXSTRLEN];
2586  SCIP_VAR* consvars[2];
2587  SCIP_Real vals[2];
2588 
2589  assert(SCIPconsIsActive(cons));
2590 
2591  consvars[0] = consdata->resvar;
2592  vals[0] = 1.0;
2593  vals[1] = -1.0;
2594 
2595  /* create operator linear constraints */
2596  for( v = consdata->nvars - 1; v >= 0; --v )
2597  {
2598  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), v);
2599  consvars[1] = consdata->vars[v];
2600 
2601  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, consvars, vals, -SCIPinfinity(scip), 0.0,
2605  SCIPconsIsStickingAtNode(cons)) );
2606 
2607  /* add constraint */
2608  SCIP_CALL( SCIPaddCons(scip, newcons) );
2609  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
2610  }
2611  (*naddconss) += consdata->nvars;
2612 
2613  SCIPdebugMsg(scip, "deleting constraint <%s> because it was linearized\n", SCIPconsGetName(cons));
2614 
2615  SCIP_CALL( SCIPdelCons(scip, cons) );
2616  ++(*ndelconss);
2617  }
2618  /* if only one operand is leftover, aggregate it to the resultant */
2619  else if( consdata->nvars == 1 )
2620  {
2621  SCIPdebugMsg(scip, "aggregating last operand <%s> to the resultant <%s> in constraint <%s>\n", SCIPvarGetName(consdata->vars[0]), SCIPvarGetName(resvar), SCIPconsGetName(cons));
2622 
2623  /* aggregate resultant to operand */
2624  SCIP_CALL( SCIPaggregateVars(scip, resvar, consdata->vars[0], 1.0, -1.0, 0.0,
2625  &infeasible, &redundant, &aggregated) );
2626 
2627  if( aggregated )
2628  ++(*naggrvars);
2629 
2630  *cutoff = *cutoff || infeasible;
2631 
2632  SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are removed\n", SCIPconsGetName(cons));
2633 
2634  SCIP_CALL( SCIPdelCons(scip, cons) );
2635  ++(*ndelconss);
2636  }
2637 
2638  /* if no operand is leftover delete the constraint */
2639  if( SCIPconsIsActive(cons) && consdata->nvars == 0 )
2640  {
2641  SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are removed\n", SCIPconsGetName(cons));
2642 
2643  SCIP_CALL( SCIPdelCons(scip, cons) );
2644  ++(*ndelconss);
2645  }
2646  }
2647  }
2648 
2649  SCIPfreeBufferArray(scip, &impoperands);
2650 
2651  return SCIP_OKAY;
2652 }
2653 
2654 /** 1. check if at least two operands or one operand and the resultant are in one clique, if so, we can fix the
2655  * resultant to zero and in the former case we can also delete this constraint but we need to extract the clique
2656  * information as constraint
2657  *
2658  * x == AND(y, z) and clique(y,z) => x = 0, delete constraint and create y + z <= 1
2659  * x == AND(y, z) and clique(x,y) => x = 0
2660  *
2661  * special handled cases are:
2662  * - if the resultant is a negation of an operand, in that case we fix the resultant to 0
2663  * - if the resultant is equal to an operand, we will linearize this constraint by adding all necessary
2664  * set-packing constraints like resultant + ~operand <= 1 and delete the old constraint
2665  *
2666  * x == AND(~x, y) => x = 0
2667  * x == AND(x, y) => add x + ~y <= 1 and delete the constraint
2668  *
2669  * 2. check if one operand is in a clique with the negation of all other operands, this means we can aggregate this
2670  * operand to the resultant
2671  *
2672  * r == AND(x,y,z) and clique(x,~y) and clique(x,~z) => r == x
2673  *
2674  * 3. check if the resultant and the negations of all operands are in a clique
2675  *
2676  * r == AND(x,y) and clique(r, ~x,~y) => upgrade the constraint to a set-partitioning constraint r + ~x + ~y = 1
2677  *
2678  * @note We removed also fixed variables and propagate them, and if only one operand is remaining due to removal, we
2679  * will aggregate the resultant with this operand
2680  */
2681 static
2683  SCIP* scip, /**< SCIP data structure */
2684  SCIP_CONS* cons, /**< constraint to process */
2685  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2686  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2687  int* nfixedvars, /**< pointer to add up the number of found domain reductions */
2688  int* naggrvars, /**< pointer to add up the number of aggregated variables */
2689  int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
2690  int* ndelconss, /**< pointer to add up the number of deleted constraints */
2691  int* naddconss /**< pointer to add up the number of added constraints */
2692  )
2693 {
2694  SCIP_CONSDATA* consdata;
2695  SCIP_VAR** vars;
2696  SCIP_VAR* var1;
2697  SCIP_VAR* var2;
2698  int nvars;
2699  int vstart;
2700  int vend;
2701  int v;
2702  int v2;
2703  SCIP_Bool negated;
2704  SCIP_Bool value1;
2705  SCIP_Bool value2;
2706  SCIP_Bool infeasible;
2707  SCIP_Bool fixed;
2708  SCIP_Bool allnegoperandsexist;
2709 
2710  assert(scip != NULL);
2711  assert(cons != NULL);
2712  assert(eventhdlr != NULL);
2713  assert(cutoff != NULL);
2714  assert(nfixedvars != NULL);
2715  assert(naggrvars != NULL);
2716  assert(nchgcoefs != NULL);
2717  assert(ndelconss != NULL);
2718  assert(naddconss != NULL);
2719 
2720  consdata = SCIPconsGetData(cons);
2721  assert(consdata != NULL);
2722 
2723  if( !SCIPconsIsActive(cons) || SCIPconsIsModifiable(cons) )
2724  return SCIP_OKAY;
2725 
2726  vars = consdata->vars;
2727  nvars = consdata->nvars;
2728  assert(vars != NULL || nvars == 0);
2729 
2730  /* remove fixed variables to be able to ask for cliques
2731  *
2732  * if an operand is fixed to 0 fix the resultant to 0 and delete the constraint
2733  * if an operand is fixed to 1 remove it from the constraint
2734  */
2735  for( v = nvars - 1; v >= 0; --v )
2736  {
2737  assert(vars != NULL);
2738 
2739  if( SCIPvarGetLbGlobal(vars[v]) > 0.5 )
2740  {
2741  SCIPdebugMsg(scip, "In constraint <%s> the operand <%s> is fixed to 1 so remove it from the constraint\n",
2742  SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
2743 
2744  /* because we loop from back to front we can delete the entry in the consdata structure */
2745  SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
2746  ++(*nchgcoefs);
2747 
2748  assert(consdata->vars == vars);
2749 
2750  continue;
2751  }
2752  else if( SCIPvarGetUbGlobal(vars[v]) < 0.5 )
2753  {
2754  SCIPdebugMsg(scip, "constraint <%s> redundant: because operand <%s> is fixed to zero so we can fix the resultant <%s> to 0\n",
2755  SCIPconsGetName(cons), SCIPvarGetName(vars[v]), SCIPvarGetName(consdata->resvar));
2756 
2757  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2758  *cutoff = *cutoff || infeasible;
2759  if( fixed )
2760  ++(*nfixedvars);
2761 
2762  SCIP_CALL( SCIPdelCons(scip, cons) );
2763  ++(*ndelconss);
2764 
2765  return SCIP_OKAY;
2766  }
2767  }
2768 
2769  /* if we deleted some operands constraint might be redundant */
2770  if( consdata->nvars < nvars )
2771  {
2772  assert(vars == consdata->vars);
2773 
2774  /* all operands fixed to one were removed, so if no operand is left this means we can fix the resultant to 1
2775  * too
2776  */
2777  if( consdata->nvars == 0 )
2778  {
2779  SCIPdebugMsg(scip, "All operand in constraint <%s> were deleted, so the resultant needs to be fixed to 1\n",
2780  SCIPconsGetName(cons));
2781 
2782  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 1.0, &infeasible, &fixed) );
2783  *cutoff = *cutoff || infeasible;
2784  if( fixed )
2785  ++(*nfixedvars);
2786 
2787  SCIP_CALL( SCIPdelCons(scip, cons) );
2788  ++(*ndelconss);
2789 
2790  return SCIP_OKAY;
2791  }
2792  /* if only one not fixed operand is left, we can aggregate it to the resultant */
2793  else if( consdata->nvars == 1 )
2794  {
2795  SCIP_Bool redundant;
2796  SCIP_Bool aggregated;
2797 
2798  /* aggregate resultant to last operand */
2799  SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
2800  &infeasible, &redundant, &aggregated) );
2801 
2802  if( aggregated )
2803  ++(*naggrvars);
2804 
2805  SCIP_CALL( SCIPdelCons(scip, cons) );
2806  ++(*ndelconss);
2807 
2808  *cutoff = *cutoff || infeasible;
2809 
2810  return SCIP_OKAY;
2811  }
2812 
2813  nvars = consdata->nvars;
2814  }
2815 
2816  /* @todo when cliques are improved, we only need to collect all clique-ids for all variables and check for doubled
2817  * entries
2818  */
2819  /* case 1 first part */
2820  /* check if two operands are in a clique */
2821  for( v = nvars - 1; v > 0; --v )
2822  {
2823  assert(vars != NULL);
2824 
2825  var1 = vars[v];
2826  assert(var1 != NULL);
2827  negated = FALSE;
2828 
2829  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
2830  assert(var1 != NULL);
2831 
2832  if( negated )
2833  value1 = FALSE;
2834  else
2835  value1 = TRUE;
2836 
2837  assert(SCIPvarGetStatus(var1) != SCIP_VARSTATUS_FIXED);
2838 
2839  for( v2 = v - 1; v2 >= 0; --v2 )
2840  {
2841  var2 = vars[v2];
2842  assert(var2 != NULL);
2843 
2844  negated = FALSE;
2845  SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
2846  assert(var2 != NULL);
2847 
2848  if( negated )
2849  value2 = FALSE;
2850  else
2851  value2 = TRUE;
2852 
2853  assert(SCIPvarGetStatus(var2) != SCIP_VARSTATUS_FIXED);
2854 
2855  /* if both variables are negated of each other or the same, this will be handled in applyFixings();
2856  * @note if both variables are the same, then SCIPvarsHaveCommonClique() will return TRUE, so we better
2857  * continue
2858  */
2859  if( var1 == var2 )
2860  continue;
2861 
2862  if( SCIPvarsHaveCommonClique(var1, value1, var2, value2, TRUE) )
2863  {
2864  SCIP_CONS* cliquecons;
2865  SCIP_VAR* consvars[2];
2866  char name[SCIP_MAXSTRLEN];
2867 
2868  SCIPdebugMsg(scip, "constraint <%s> redundant: because variable <%s> and variable <%s> are in a clique, the resultant <%s> can be fixed to 0\n",
2869  SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2), SCIPvarGetName(consdata->resvar));
2870 
2871  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2872  *cutoff = *cutoff || infeasible;
2873  if( fixed )
2874  ++(*nfixedvars);
2875 
2876  /* create clique constraint which lead to the last fixing */
2877  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%d", SCIPconsGetName(cons), v2);
2878 
2879  if( value1 )
2880  consvars[0] = var1;
2881  else
2882  {
2883  SCIP_CALL( SCIPgetNegatedVar(scip, var1, &(consvars[0])) );
2884  }
2885 
2886  if( value2 )
2887  consvars[1] = var2;
2888  else
2889  {
2890  SCIP_CALL( SCIPgetNegatedVar(scip, var2, &(consvars[1])) );
2891  }
2892 
2893  SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 2, consvars,
2895  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2897  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
2898  SCIPdebugMsg(scip, " -> adding clique constraint: ");
2899  SCIPdebugPrintCons(scip, cliquecons, NULL);
2900  SCIP_CALL( SCIPaddCons(scip, cliquecons) );
2901  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2902  ++(*naddconss);
2903 
2904  SCIP_CALL( SCIPdelCons(scip, cons) );
2905  ++(*ndelconss);
2906 
2907  return SCIP_OKAY;
2908  }
2909  }
2910  }
2911 
2912  var1 = consdata->resvar;
2913  assert(var1 != NULL);
2914 
2915  negated = FALSE;
2916  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
2917  assert(var1 != NULL);
2918 
2919  /* it may appear that we have a fixed resultant */
2920  if( SCIPvarGetStatus(var1) == SCIP_VARSTATUS_FIXED )
2921  {
2922  /* resultant is fixed to 1, so fix all operands to 1 */
2923  if( SCIPvarGetLbGlobal(consdata->resvar) > 0.5 )
2924  {
2925  SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> is fixed to 1 so fix all operands to 1\n",
2926  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
2927 
2928  /* fix all operands to 1 */
2929  for( v = nvars - 1; v >= 0 && !(*cutoff); --v )
2930  {
2931  assert(vars != NULL);
2932 
2933  SCIPdebugMsg(scip, "Fixing operand <%s> to 1.\n", SCIPvarGetName(vars[v]));
2934 
2935  SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, &infeasible, &fixed) );
2936  *cutoff = *cutoff || infeasible;
2937 
2938  if( fixed )
2939  ++(*nfixedvars);
2940  }
2941 
2942  SCIP_CALL( SCIPdelCons(scip, cons) );
2943  ++(*ndelconss);
2944  }
2945  /* the upgrade to a linear constraint because of the to 0 fixed resultant we do in propagateCons() */
2946  else
2947  assert(SCIPvarGetUbGlobal(consdata->resvar) < 0.5);
2948 
2949  return SCIP_OKAY;
2950  }
2951 
2952  if( negated )
2953  value1 = FALSE;
2954  else
2955  value1 = TRUE;
2956 
2957  /* case 1 second part */
2958  /* check if one operands is in a clique with the resultant */
2959  for( v = nvars - 1; v >= 0; --v )
2960  {
2961  assert(vars != NULL);
2962 
2963  var2 = vars[v];
2964  assert(var2 != NULL);
2965 
2966  negated = FALSE;
2967  SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
2968  assert(var2 != NULL);
2969 
2970  if( negated )
2971  value2 = FALSE;
2972  else
2973  value2 = TRUE;
2974 
2975  /* if both variables are negated of each other or the same, this will be handled in applyFixings();
2976  * @note if both variables are the same, then SCIPvarsHaveCommonClique() will return TRUE, so we better continue
2977  */
2978  if( var1 == var2 )
2979  {
2980  /* x1 == AND(~x1, x2 ...) => x1 = 0 */
2981  if( value1 != value2 )
2982  {
2983  SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> can be fixed to 0 because the negation of it is an operand.\n",
2984  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
2985 
2986  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2987  *cutoff = *cutoff || infeasible;
2988 
2989  if( fixed )
2990  ++(*nfixedvars);
2991 
2992  return SCIP_OKAY;
2993  }
2994  /* x1 == AND(x1, x2 ...) => delete constraint and create all set-packing constraints x1 + ~x2 <= 1, x1 + ~... <= 1 */
2995  else
2996  {
2997  SCIP_CONS* cliquecons;
2998  SCIP_VAR* consvars[2];
2999  char name[SCIP_MAXSTRLEN];
3000 
3001  assert(value1 == value2);
3002 
3003  consvars[0] = consdata->resvar;
3004 
3005  for( v2 = nvars - 1; v2 >= 0; --v2 )
3006  {
3007  var2 = vars[v2];
3008  negated = FALSE;
3009  SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
3010 
3011  /* if the active representations of the resultant and an operand are different then we need to extract
3012  * this as a clique constraint
3013  *
3014  * if the active representations of the resultant and an operand are equal then the clique constraint
3015  * would look like x1 + ~x1 <= 1, which is redundant
3016  *
3017  * if the active representations of the resultant and an operand are negated of each other then the
3018  * clique constraint would look like x1 + x1 <= 1, which will lead to a fixation of the resultant later
3019  * on
3020  */
3021  if( var1 == var2 )
3022  {
3023  if( value1 == negated )
3024  {
3025  SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> can be fixed to 0 because the negation of it is an operand.\n",
3026  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
3027 
3028  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3029  *cutoff = *cutoff || infeasible;
3030 
3031  if( fixed )
3032  ++(*nfixedvars);
3033 
3034  break;
3035  }
3036  }
3037  else
3038  {
3039  SCIP_CALL( SCIPgetNegatedVar(scip, vars[v2], &consvars[1]) );
3040  assert(consvars[1] != NULL);
3041 
3042  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%d", SCIPconsGetName(cons), v2);
3043 
3044  SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 2, consvars,
3046  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
3048  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3049  SCIPdebugMsg(scip, " -> adding clique constraint: ");
3050  SCIPdebugPrintCons(scip, cliquecons, NULL);
3051  SCIP_CALL( SCIPaddCons(scip, cliquecons) );
3052  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
3053  ++(*naddconss);
3054  }
3055  }
3056 
3057  /* delete old constraint */
3058  SCIP_CALL( SCIPdelCons(scip, cons) );
3059  ++(*ndelconss);
3060 
3061  return SCIP_OKAY;
3062  }
3063  }
3064 
3065  /* due to SCIPvarsHaveCommonClique() returns on two same variables that they are in a clique, we need to handle
3066  * it explicitly
3067  */
3068  if( var1 == var2 && value1 == value2 )
3069  continue;
3070 
3071  /* due to SCIPvarsHaveCommonClique() returns on two negated variables that they are not in a clique, we need to
3072  * handle it explicitly
3073  */
3074  if( (var1 == var2 && value1 != value2) || SCIPvarsHaveCommonClique(var1, value1, var2, value2, TRUE) )
3075  {
3076  SCIPdebugMsg(scip, "in constraint <%s> the resultant <%s> can be fixed to 0 because it is in a clique with operand <%s>\n",
3077  SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2));
3078 
3079  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3080  *cutoff = *cutoff || infeasible;
3081  if( fixed )
3082  ++(*nfixedvars);
3083 
3084  return SCIP_OKAY;
3085  }
3086  }
3087 
3088  if( !SCIPconsIsActive(cons) )
3089  return SCIP_OKAY;
3090 
3091  v2 = -1;
3092  /* check which operands have a negated variable */
3093  for( v = nvars - 1; v >= 0; --v )
3094  {
3095  assert(vars != NULL);
3096 
3097  var1 = vars[v];
3098  assert(var1 != NULL);
3099 
3100  negated = FALSE;
3101  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
3102  assert(var1 != NULL);
3103 
3104  if( SCIPvarGetNegatedVar(var1) == NULL )
3105  {
3106  if( v2 >= 0 )
3107  break;
3108  v2 = v;
3109  }
3110  }
3111 
3112  allnegoperandsexist = FALSE;
3113 
3114  /* all operands have a negated variable, so we will check for all possible negated ciques */
3115  if( v2 == -1 )
3116  {
3117  allnegoperandsexist = TRUE;
3118  vstart = nvars - 1;
3119  vend = 0;
3120  }
3121  /* exactly one operands has no negated variable, so only this variable can be in a clique with all other negations */
3122  else if( v2 >= 0 && v == -1 )
3123  {
3124  vstart = v2;
3125  vend = v2;
3126  }
3127  /* at least two operands have no negated variable, so there is no possible clique with negated variables */
3128  else
3129  {
3130  vstart = -1;
3131  vend = 0;
3132  }
3133 
3134  /* case 2 */
3135  /* check for negated cliques in the operands */
3136  for( v = vstart; v >= vend; --v )
3137  {
3138  assert(vars != NULL);
3139 
3140  var1 = vars[v];
3141  assert(var1 != NULL);
3142 
3143  negated = FALSE;
3144  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
3145  assert(var1 != NULL);
3146 
3147  if( negated )
3148  value1 = FALSE;
3149  else
3150  value1 = TRUE;
3151 
3152  for( v2 = nvars - 1; v2 >= 0; --v2 )
3153  {
3154  if( v2 == v )
3155  continue;
3156 
3157  var2 = vars[v2];
3158  assert(var2 != NULL);
3159 
3160  negated = FALSE;
3161  SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
3162  assert(var2 != NULL);
3163 
3164  if( negated )
3165  value2 = FALSE;
3166  else
3167  value2 = TRUE;
3168 
3169  assert(SCIPvarGetNegatedVar(var2) != NULL);
3170 
3171  /* invert flag, because we want to check var 1 against all negations of the other variables */
3172  value2 = !value2;
3173 
3174  /* due to SCIPvarsHaveCommonClique() returns on two same variables that they are in a clique, we need to handle
3175  * it explicitly
3176  */
3177  if( var1 == var2 && value1 == value2 )
3178  {
3179  SCIPdebugMsg(scip, "in constraint <%s> the resultant <%s> can be fixed to 0 because two operands are negated of each other\n",
3180  SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
3181 
3182  SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3183  *cutoff = *cutoff || infeasible;
3184  if( fixed )
3185  ++(*nfixedvars);
3186 
3187  return SCIP_OKAY;
3188  }
3189 
3190  /* due to SCIPvarsHaveCommonClique() returns on two negated variables that they are not in a clique, we need to
3191  * handle it explicitly
3192  */
3193  if( var1 == var2 && value1 != value2 )
3194  continue;
3195 
3196  if( !SCIPvarsHaveCommonClique(var1, value1, var2, value2, TRUE) )
3197  break;
3198  }
3199 
3200  if( v2 == -1 )
3201  {
3202  SCIP_Bool redundant;
3203  SCIP_Bool aggregated;
3204 
3205  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",
3206  SCIPconsGetName(cons), SCIPvarGetName(vars[v]), SCIPvarGetName(consdata->resvar));
3207 
3208  SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, vars[v], 1.0, -1.0, 0.0,
3209  &infeasible, &redundant, &aggregated) );
3210  *cutoff = *cutoff || infeasible;
3211 
3212  if( aggregated )
3213  ++(*naggrvars);
3214 
3215  return SCIP_OKAY;
3216  }
3217  }
3218 
3219  /* case 3 */
3220  /* check if the resultant and the negations of the operands are in a clique, then we can upgrade this constraint to a
3221  * set-partitioning constraint
3222  */
3223  if( allnegoperandsexist && SCIPconsIsActive(cons) )
3224  {
3225  SCIP_VAR** newvars;
3226  SCIP_Bool* negations;
3227  SCIP_Bool upgrade;
3228 
3229  SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars + 1) );
3230  SCIP_CALL( SCIPallocBufferArray(scip, &negations, nvars + 1) );
3231  BMSclearMemoryArray(negations, nvars + 1);
3232 
3233  var1 = consdata->resvar;
3234  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negations[nvars]) );
3235  assert(var1 != NULL);
3236  assert(SCIPvarGetStatus(var1) != SCIP_VARSTATUS_FIXED);
3237 
3238  newvars[nvars] = var1;
3239 
3240  /* get active variables */
3241  for( v = nvars - 1; v >= 0; --v )
3242  {
3243  assert(vars != NULL);
3244 
3245  var1 = vars[v];
3246  SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negations[v]) );
3247  assert(var1 != NULL);
3248  assert(SCIPvarGetStatus(var1) != SCIP_VARSTATUS_FIXED);
3249 
3250  newvars[v] = var1;
3251 
3252  /* there should be no variable left that is equal or negated to the resultant */
3253  assert(newvars[v] != newvars[nvars]);
3254  }
3255 
3256  upgrade = TRUE;
3257 
3258  /* the resultant is in a clique with the negations of all operands, due to this AND-constraint */
3259  /* only check if the negations of all operands are in a clique */
3260  for( v = nvars - 1; v >= 0 && upgrade; --v )
3261  {
3262  for( v2 = v - 1; v2 >= 0; --v2 )
3263  {
3264  /* the resultant need to be in a clique with the negations of all operands */
3265  if( !SCIPvarsHaveCommonClique(newvars[v], negations[v], newvars[v2], negations[v2], TRUE) )
3266  {
3267  upgrade = FALSE;
3268  break;
3269  }
3270  }
3271  }
3272 
3273  /* all variables are in a clique, so upgrade thi AND-constraint */
3274  if( upgrade )
3275  {
3276  SCIP_CONS* cliquecons;
3277  char name[SCIP_MAXSTRLEN];
3278 
3279  /* get new constraint variables */
3280  if( negations[nvars] )
3281  {
3282  /* negation does not need to be existing, so SCIPvarGetNegatedVar() cannot be called
3283  * (e.g. resultant = ~x = 1 - x and x = y = newvars[nvars] and negations[nvars] = TRUE,
3284  * then y does not need to have a negated variable, yet)
3285  */
3286  SCIP_CALL( SCIPgetNegatedVar(scip, newvars[nvars], &(newvars[nvars])) );
3287  }
3288  assert(newvars[nvars] != NULL);
3289 
3290  for( v = nvars - 1; v >= 0; --v )
3291  {
3292  if( !negations[v] )
3293  {
3294  /* negation does not need to be existing, so SCIPvarGetNegatedVar() cannot be called
3295  * (e.g. vars[v] = ~x = 1 - x and x = y = newvars[v] and negations[v] = TRUE,
3296  * then y does not need to have a negated variable, yet)
3297  */
3298  SCIP_CALL( SCIPgetNegatedVar(scip, newvars[v], &(newvars[v])) );
3299  }
3300  assert(newvars[v] != NULL);
3301  }
3302 
3303  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clqeq", SCIPconsGetName(cons));
3304 
3305  SCIP_CALL( SCIPcreateConsSetpart(scip, &cliquecons, name, nvars + 1, newvars,
3307  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3309  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3310  SCIPdebugMsg(scip, " -> upgrading AND-constraint <%s> with use of clique information to a set-partitioning constraint: \n", SCIPconsGetName(cons));
3311  SCIPdebugPrintCons(scip, cliquecons, NULL);
3312  SCIP_CALL( SCIPaddCons(scip, cliquecons) );
3313  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
3314  ++(*naddconss);
3315 
3316  /* delete old constraint */
3317  SCIP_CALL( SCIPdelCons(scip, cons) );
3318  ++(*ndelconss);
3319  }
3320 
3321  SCIPfreeBufferArray(scip, &negations);
3322  SCIPfreeBufferArray(scip, &newvars);
3323  }
3324 
3325  return SCIP_OKAY;
3326 }
3327 
3328 /** gets the key of the given element */
3329 static
3330 SCIP_DECL_HASHGETKEY(hashGetKeyAndcons)
3331 { /*lint --e{715}*/
3332  /* the key is the element itself */
3333  return elem;
3334 }
3335 
3336 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
3337 static
3338 SCIP_DECL_HASHKEYEQ(hashKeyEqAndcons)
3340  SCIP_CONSDATA* consdata1;
3341  SCIP_CONSDATA* consdata2;
3342  SCIP_Bool coefsequal;
3343  int i;
3344 #ifndef NDEBUG
3345  SCIP* scip;
3346 
3347  scip = (SCIP*)userptr;
3348  assert(scip != NULL);
3349 #endif
3350 
3351  consdata1 = SCIPconsGetData((SCIP_CONS*)key1);
3352  consdata2 = SCIPconsGetData((SCIP_CONS*)key2);
3353 
3354  /* checks trivial case */
3355  if( consdata1->nvars != consdata2->nvars )
3356  return FALSE;
3357 
3358  /* sorts the constraints */
3359  consdataSort(consdata1);
3360  consdataSort(consdata2);
3361  assert(consdata1->sorted);
3362  assert(consdata2->sorted);
3363 
3364  coefsequal = TRUE;
3365 
3366  for( i = 0; i < consdata1->nvars ; ++i )
3367  {
3368  /* tests if variables are equal */
3369  if( consdata1->vars[i] != consdata2->vars[i] )
3370  {
3371  assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
3372  SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
3373  coefsequal = FALSE;
3374  break;
3375  }
3376  assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
3377  }
3378 
3379  return coefsequal;
3380 }
3381 
3382 /** returns the hash value of the key */
3383 static
3384 SCIP_DECL_HASHKEYVAL(hashKeyValAndcons)
3385 { /*lint --e{715}*/
3386  SCIP_CONSDATA* consdata;
3387  int minidx;
3388  int mididx;
3389  int maxidx;
3390 
3391  consdata = SCIPconsGetData((SCIP_CONS*)key);
3392  assert(consdata != NULL);
3393  assert(consdata->sorted);
3394  assert(consdata->nvars > 0);
3395 
3396  minidx = SCIPvarGetIndex(consdata->vars[0]);
3397  mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
3398  maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
3399  assert(minidx >= 0 && minidx <= maxidx);
3400 
3401  return SCIPhashFour(consdata->nvars, minidx, mididx, maxidx);
3402 }
3403 
3404 /** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
3405  * accordingly; in contrast to removeRedundantConstraints(), it uses a hash table
3406  */
3407 static
3409  SCIP* scip, /**< SCIP data structure */
3410  BMS_BLKMEM* blkmem, /**< block memory */
3411  SCIP_CONS** conss, /**< constraint set */
3412  int nconss, /**< number of constraints in constraint set */
3413  int* firstchange, /**< pointer to store first changed constraint */
3414  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3415  int* naggrvars, /**< pointer to count number of aggregated variables */
3416  int* ndelconss /**< pointer to count number of deleted constraints */
3417  )
3418 {
3419  SCIP_HASHTABLE* hashtable;
3420  int hashtablesize;
3421  int c;
3422 
3423  assert(conss != NULL);
3424  assert(ndelconss != NULL);
3425 
3426  /* create a hash table for the constraint set */
3427  hashtablesize = nconss;
3428  hashtablesize = MAX(hashtablesize, HASHSIZE_ANDCONS);
3429  SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
3430  hashGetKeyAndcons, hashKeyEqAndcons, hashKeyValAndcons, (void*) scip) );
3431 
3432  *cutoff = FALSE;
3433 
3434  /* check all constraints in the given set for redundancy */
3435  for( c = 0; c < nconss; ++c )
3436  {
3437  SCIP_CONS* cons0;
3438  SCIP_CONS* cons1;
3439  SCIP_CONSDATA* consdata0;
3440 
3441  cons0 = conss[c];
3442 
3443  if( !SCIPconsIsActive(cons0) || SCIPconsIsModifiable(cons0) )
3444  continue;
3445 
3446  consdata0 = SCIPconsGetData(cons0);
3447 
3448  /* sort the constraint */
3449  consdataSort(consdata0);
3450  assert(consdata0->sorted);
3451 
3452  /* get constraint from current hash table with same variables as cons0 */
3453  cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
3454 
3455  if( cons1 != NULL )
3456  {
3457  SCIP_CONSDATA* consdata1;
3458  SCIP_Bool redundant;
3459 
3460  assert(SCIPconsIsActive(cons1));
3461  assert(!SCIPconsIsModifiable(cons1));
3462 
3463  consdata1 = SCIPconsGetData(cons1);
3464 
3465  assert(consdata1 != NULL);
3466  assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
3467 
3468  assert(consdata0->sorted && consdata1->sorted);
3469  assert(consdata0->vars[0] == consdata1->vars[0]);
3470 
3471  redundant = FALSE;
3472 
3473  if( consdata0->resvar != consdata1->resvar )
3474  {
3475  SCIP_Bool aggregated;
3476 
3477  assert(SCIPvarCompare(consdata0->resvar, consdata1->resvar) != 0);
3478 
3479  /* aggregate resultants */
3480  SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3481  cutoff, &redundant, &aggregated) );
3482  assert(redundant || SCIPdoNotAggr(scip));
3483 
3484  if( aggregated )
3485  ++(*naggrvars);
3486  if( *cutoff )
3487  goto TERMINATE;
3488  }
3489  else
3490  redundant = TRUE;
3491 
3492  /* delete consdel */
3493  if( redundant )
3494  {
3495  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
3496  /* coverity[swapped_arguments] */
3497  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
3498 
3499  /* also take the check when upgrade flag over if necessary */
3500  consdata1->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3501  consdata1->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3502 
3503  SCIP_CALL( SCIPdelCons(scip, cons0) );
3504  (*ndelconss)++;
3505  }
3506 
3507  /* update the first changed constraint to begin the next aggregation round with */
3508  if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
3509  *firstchange = SCIPconsGetPos(cons1);
3510 
3511  assert(SCIPconsIsActive(cons1));
3512  }
3513  else
3514  {
3515  /* no such constraint in current hash table: insert cons0 into hash table */
3516  SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
3517  }
3518  }
3519  TERMINATE:
3520  /* free hash table */
3521  SCIPhashtableFree(&hashtable);
3522 
3523  return SCIP_OKAY;
3524 }
3525 
3526 /** helper function to enforce constraints */
3527 static
3529  SCIP* scip, /**< SCIP data structure */
3530  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3531  SCIP_CONS** conss, /**< constraints to process */
3532  int nconss, /**< number of constraints */
3533  SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
3534  SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
3535  )
3536 {
3537  SCIP_CONSHDLRDATA* conshdlrdata;
3538  SCIP_Bool separated;
3539  SCIP_Bool violated;
3540  SCIP_Bool cutoff;
3541  int i;
3542 
3543  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3544  assert(conshdlrdata != NULL);
3545 
3546  *result = SCIP_FEASIBLE;
3547 
3548  /* method is called only for integral solutions, because the enforcing priority is negative */
3549  for( i = 0; i < nconss; i++ )
3550  {
3551  SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, FALSE, &violated) );
3552  if( !violated )
3553  continue;
3554 
3555  if( !conshdlrdata->enforcecuts )
3556  {
3557  *result = SCIP_INFEASIBLE;
3558  return SCIP_OKAY;
3559  }
3560 
3561  SCIP_CALL( separateCons(scip, conss[i], sol, &separated, &cutoff) );
3562  if( cutoff )
3563  {
3564  *result = SCIP_CUTOFF;
3565  return SCIP_OKAY;
3566  }
3567  else if( separated )
3568  {
3569  *result = SCIP_SEPARATED;
3570  }
3571  else if( *result == SCIP_FEASIBLE ) /* do not change result separated to infeasible */
3572  {
3573  *result = SCIP_INFEASIBLE;
3574  }
3575  }
3576 
3577  return SCIP_OKAY;
3578 }
3579 
3580 
3581 /** compares constraint with all prior constraints for possible redundancy or aggregation,
3582  * and removes or changes constraint accordingly
3583  */
3584 static
3586  SCIP* scip, /**< SCIP data structure */
3587  SCIP_CONS** conss, /**< constraint set */
3588  int firstchange, /**< first constraint that changed since last pair preprocessing round */
3589  int chkind, /**< index of constraint to check against all prior indices upto startind */
3590  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3591  int* naggrvars, /**< pointer to count number of aggregated variables */
3592  int* nbdchgs, /**< pointer to count the number of performed bound changes, or NULL */
3593  int* ndelconss /**< pointer to count number of deleted constraints */
3594  )
3595 {
3596  SCIP_CONS* cons0;
3597  SCIP_CONSDATA* consdata0;
3598  SCIP_Bool cons0changed;
3599  int c;
3600 
3601  assert(conss != NULL);
3602  assert(firstchange <= chkind);
3603  assert(cutoff != NULL);
3604  assert(naggrvars != NULL);
3605  assert(nbdchgs != NULL);
3606  assert(ndelconss != NULL);
3607 
3608  /* get the constraint to be checked against all prior constraints */
3609  cons0 = conss[chkind];
3610  assert(SCIPconsIsActive(cons0));
3611  assert(!SCIPconsIsModifiable(cons0));
3612 
3613  consdata0 = SCIPconsGetData(cons0);
3614 
3615  /* sort the constraint */
3616  consdataSort(consdata0);
3617 
3618  assert(consdata0->nvars >= 1);
3619  assert(consdata0->sorted);
3620 
3621  /* check constraint against all prior constraints */
3622  cons0changed = consdata0->changed;
3623 
3624  if( SCIPconsIsActive(cons0) )
3625  {
3626  for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff); ++c )
3627  {
3628  SCIP_CONS* cons1;
3629  SCIP_CONSDATA* consdata1;
3630  SCIP_Bool cons0superset;
3631  SCIP_Bool cons1superset;
3632  int v0;
3633  int v1;
3634 
3635  if( c % 1000 == 0 && SCIPisStopped(scip) )
3636  break;
3637 
3638  cons1 = conss[c];
3639 
3640  /* ignore inactive and modifiable constraints */
3641  if( !SCIPconsIsActive(cons1) || SCIPconsIsModifiable(cons1) )
3642  continue;
3643 
3644  consdata1 = SCIPconsGetData(cons1);
3645  assert(consdata1 != NULL);
3646 
3647 #ifdef SCIP_DISABLED_CODE
3648  SCIPdebugMsg(scip, "preprocess AND-constraint pair <%s>[chg:%d] and <%s>[chg:%d]\n",
3649  SCIPconsGetName(cons0), cons0changed, SCIPconsGetName(cons1), consdata1->changed);
3650 #endif
3651 
3652  /* if both constraints were not changed since last round, we can ignore the pair */
3653  if( !cons0changed && !consdata1->changed )
3654  continue;
3655 
3656  assert(consdata1->nvars >= 1);
3657 
3658  /* sort the constraint */
3659  consdataSort(consdata1);
3660  assert(consdata1->sorted);
3661 
3662  /* check consdata0 against consdata1:
3663  * - if they consist of the same operands, the resultants can be aggregated
3664  * - if one operand list is a subset of the other, add implication r0 = 1 -> r1 = 1, or r1 = 1 -> r0 = 1
3665  */
3666  v0 = 0;
3667  v1 = 0;
3668  cons0superset = TRUE;
3669  cons1superset = TRUE;
3670  while( (v0 < consdata0->nvars || v1 < consdata1->nvars) && (cons0superset || cons1superset) )
3671  {
3672  int varcmp;
3673 
3674  /* test, if variable appears in only one or in both constraints */
3675  if( v0 < consdata0->nvars && v1 < consdata1->nvars )
3676  varcmp = SCIPvarCompare(consdata0->vars[v0], consdata1->vars[v1]);
3677  else if( v0 < consdata0->nvars )
3678  varcmp = -1;
3679  else
3680  varcmp = +1;
3681 
3682  switch( varcmp )
3683  {
3684  case -1:
3685  /* variable doesn't appear in consdata1 */
3686  cons1superset = FALSE;
3687  v0++;
3688  break;
3689 
3690  case +1:
3691  /* variable doesn't appear in consdata0 */
3692  cons0superset = FALSE;
3693  v1++;
3694  break;
3695 
3696  case 0:
3697  /* variable appears in both constraints */
3698  v0++;
3699  v1++;
3700  break;
3701 
3702  default:
3703  SCIPerrorMessage("invalid comparison result\n");
3704  SCIPABORT();
3705  return SCIP_INVALIDDATA; /*lint !e527*/
3706  }
3707  }
3708 
3709  /* check for equivalence and domination */
3710  if( cons0superset && cons1superset )
3711  {
3712  SCIP_Bool infeasible;
3713  SCIP_Bool redundant;
3714  SCIP_Bool aggregated;
3715 
3716  /* constraints are equivalent */
3717  SCIPdebugMsg(scip, "equivalent AND-constraints <%s> and <%s>: aggregate resultants <%s> == <%s>\n",
3718  SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPvarGetName(consdata0->resvar),
3719  SCIPvarGetName(consdata1->resvar));
3720 
3721  /* aggregate resultants */
3722  SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3723  &infeasible, &redundant, &aggregated) );
3724  assert(redundant || SCIPdoNotAggr(scip));
3725 
3726  if( aggregated )
3727  {
3728  assert(redundant);
3729  (*naggrvars)++;
3730  }
3731 
3732  if( redundant )
3733  {
3734  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
3735  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
3736 
3737  /* also take the check when upgrade flag over if necessary */
3738  consdata0->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3739  consdata0->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3740 
3741  /* delete constraint */
3742  SCIP_CALL( SCIPdelCons(scip, cons1) );
3743  (*ndelconss)++;
3744  }
3745 
3746  *cutoff = *cutoff || infeasible;
3747  }
3748  else if( cons0superset )
3749  {
3750  SCIP_Bool infeasible;
3751  int nboundchgs;
3752 
3753  /* the conjunction of cons0 is a superset of the conjunction of cons1 */
3754  SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3755  SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPvarGetName(consdata0->resvar),
3756  SCIPvarGetName(consdata1->resvar));
3757 
3758  /* add implication */
3759  SCIP_CALL( SCIPaddVarImplication(scip, consdata0->resvar, TRUE, consdata1->resvar, SCIP_BOUNDTYPE_LOWER, 1.0,
3760  &infeasible, &nboundchgs) );
3761  *cutoff = *cutoff || infeasible;
3762  (*nbdchgs) += nboundchgs;
3763  }
3764  else if( cons1superset )
3765  {
3766  SCIP_Bool infeasible;
3767  int nboundchgs;
3768 
3769  /* the conjunction of cons1 is a superset of the conjunction of cons0 */
3770  SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3771  SCIPconsGetName(cons1), SCIPconsGetName(cons0), SCIPvarGetName(consdata1->resvar),
3772  SCIPvarGetName(consdata0->resvar));
3773 
3774  /* add implication */
3775  SCIP_CALL( SCIPaddVarImplication(scip, consdata1->resvar, TRUE, consdata0->resvar, SCIP_BOUNDTYPE_LOWER, 1.0,
3776  &infeasible, &nboundchgs) );
3777  *cutoff = *cutoff || infeasible;
3778  (*nbdchgs) += nboundchgs;
3779  }
3780  }
3781  }
3782  consdata0->changed = FALSE;
3783 
3784  return SCIP_OKAY;
3785 }
3786 
3787 /** adds symmetry information of constraint to a symmetry detection graph */
3788 static
3790  SCIP* scip, /**< SCIP pointer */
3791  SYM_SYMTYPE symtype, /**< type of symmetries that need to be added */
3792  SCIP_CONS* cons, /**< constraint */
3793  SYM_GRAPH* graph, /**< symmetry detection graph */
3794  SCIP_Bool* success /**< pointer to store whether symmetry information could be added */
3795  )
3796 {
3797  SCIP_CONSDATA* consdata;
3798  SCIP_VAR** andvars;
3799  SCIP_VAR** vars;
3800  SCIP_Real* vals;
3801  SCIP_Real constant = 0.0;
3802  int nlocvars;
3803  int nvars;
3804  int i;
3805 
3806  assert(scip != NULL);
3807  assert(cons != NULL);
3808  assert(graph != NULL);
3809  assert(success != NULL);
3810 
3811  consdata = SCIPconsGetData(cons);
3812  assert(consdata != NULL);
3813 
3814  /* get active variables of the constraint */
3815  nvars = SCIPgetNVars(scip);
3816  nlocvars = SCIPgetNVarsAnd(scip, cons);
3817 
3818  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
3819  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
3820 
3821  andvars = SCIPgetVarsAnd(scip, cons);
3822  for( i = 0; i < consdata->nvars; ++i )
3823  {
3824  vars[i] = andvars[i];
3825  vals[i] = 1.0;
3826  }
3827 
3828  assert(SCIPgetResultantAnd(scip, cons) != NULL);
3829  vars[nlocvars] = SCIPgetResultantAnd(scip, cons);
3830  vals[nlocvars++] = 2.0;
3831  assert(nlocvars <= nvars);
3832 
3833  SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) );
3834 
3835  SCIP_CALL( SCIPextendPermsymDetectionGraphLinear(scip, graph, vars, vals,
3836  nlocvars, cons, constant, constant, success) );
3837 
3838  SCIPfreeBufferArray(scip, &vals);
3839  SCIPfreeBufferArray(scip, &vars);
3840 
3841  return SCIP_OKAY;
3842 }
3843 
3844 /*
3845  * Callback methods of constraint handler
3846  */
3847 
3848 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
3849 static
3850 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyAnd)
3851 { /*lint --e{715}*/
3852  assert(scip != NULL);
3853  assert(conshdlr != NULL);
3854  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3855 
3856  /* call inclusion method of constraint handler */
3858 
3859  *valid = TRUE;
3860 
3861  return SCIP_OKAY;
3862 }
3863 
3864 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
3865 static
3866 SCIP_DECL_CONSFREE(consFreeAnd)
3867 { /*lint --e{715}*/
3868  SCIP_CONSHDLRDATA* conshdlrdata;
3869 
3870  /* free constraint handler data */
3871  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3872  assert(conshdlrdata != NULL);
3873 
3874  conshdlrdataFree(scip, &conshdlrdata);
3875 
3876  SCIPconshdlrSetData(conshdlr, NULL);
3877 
3878  return SCIP_OKAY;
3879 }
3880 
3881 
3882 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
3883 static
3884 SCIP_DECL_CONSINITPRE(consInitpreAnd)
3885 { /*lint --e{715}*/
3886  SCIP_CONSHDLRDATA* conshdlrdata;
3887 
3888  assert( scip != NULL );
3889  assert( conshdlr != NULL );
3890  assert( nconss == 0 || conss != NULL );
3891 
3892  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3893  assert(conshdlrdata != NULL);
3894 
3895  if( conshdlrdata->linearize )
3896  {
3897  /* linearize all AND-constraints and remove the AND-constraints */
3898  SCIP_CONS* newcons;
3899  SCIP_CONS* cons;
3900  SCIP_CONSDATA* consdata;
3901  char consname[SCIP_MAXSTRLEN];
3902 
3903  SCIP_VAR** vars;
3904  SCIP_Real* vals;
3905 
3906  int nvars;
3907  int c, v;
3908 
3909  /* allocate buffer array */
3910  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
3911  SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
3912 
3913  for( c = 0; c < nconss; ++c )
3914  {
3915  cons = conss[c];
3916  assert( cons != NULL );
3917 
3918  /* only added constraints can be upgraded */
3919  if( !SCIPconsIsAdded(cons) )
3920  continue;
3921 
3922  consdata = SCIPconsGetData(cons);
3923  assert( consdata != NULL );
3924  assert( consdata->resvar != NULL );
3925 
3926  nvars = consdata->nvars;
3927 
3928  if( !conshdlrdata->aggrlinearization )
3929  {
3930  vars[0] = consdata->resvar;
3931  vals[0] = 1.0;
3932  vals[1] = -1.0;
3933 
3934  /* create operator linear constraints */
3935  for( v = 0; v < nvars; ++v )
3936  {
3937  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), v);
3938  vars[1] = consdata->vars[v];
3939 
3940  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, vars, vals, -SCIPinfinity(scip), 0.0,
3942  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3944  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3945 
3946  /* add constraint */
3947  SCIP_CALL( SCIPaddCons(scip, newcons) );
3948  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3949  }
3950  }
3951 
3952  /* reallocate buffer array */
3953  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, nvars + 1) );
3954  SCIP_CALL( SCIPreallocBufferArray(scip, &vals, nvars + 1) );
3955 
3956  for( v = 0; v < nvars; ++v )
3957  {
3958  vars[v] = consdata->vars[v];
3959  vals[v] = -1.0;
3960  }
3961 
3962  vars[nvars] = consdata->resvar;
3963 
3964  if( conshdlrdata->aggrlinearization )
3965  {
3966  /* create additional linear constraint */
3967  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_operators", SCIPconsGetName(cons));
3968 
3969  vals[nvars] = (SCIP_Real) nvars;
3970 
3971  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -SCIPinfinity(scip), 0.0,
3973  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3975  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3976 
3977  /* add constraint */
3978  SCIP_CALL( SCIPaddCons(scip, newcons) );
3979  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3980  }
3981 
3982  /* create additional linear constraint */
3983  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_add", SCIPconsGetName(cons));
3984 
3985  vals[nvars] = 1.0;
3986 
3987  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -nvars + 1.0, SCIPinfinity(scip),
3989  consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3991  !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3992 
3993  /* add constraint */
3994  SCIP_CALL( SCIPaddCons(scip, newcons) );
3995  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3996 
3997  /* delete constraint */
3998  SCIP_CALL( SCIPdelCons(scip, cons) );
3999  }
4000 
4001  /* free buffer array */
4002  SCIPfreeBufferArray(scip, &vars);
4003  SCIPfreeBufferArray(scip, &vals);
4004  }
4005 
4006  return SCIP_OKAY;
4007 }
4008 
4009 
4010 #ifdef GMLGATEPRINTING
4011 
4012 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
4013 static
4014 SCIP_DECL_CONSEXITPRE(consExitpreAnd)
4015 { /*lint --e{715}*/
4016  SCIP_HASHMAP* hashmap;
4017  FILE* gmlfile;
4018  char fname[SCIP_MAXSTRLEN];
4019  SCIP_CONS* cons;
4020  SCIP_CONSDATA* consdata;
4021  SCIP_VAR** activeconsvars;
4022  SCIP_VAR* activevar;
4023  int* varnodeids;
4024  SCIP_VAR** vars;
4025  int nvars;
4026  int nbinvars;
4027  int nintvars;
4028  int nimplvars;
4029  int ncontvars;
4030  int v;
4031  int c;
4032  int resid;
4033  int varid;
4034  int id = 1;
4035 
4036  /* no AND-constraints available */
4037  if( nconss == 0 )
4038  return SCIP_OKAY;
4039 
4040  nvars = SCIPgetNVars(scip);
4041 
4042  /* no variables left anymore */
4043  if( nvars == 0 )
4044  return SCIP_OKAY;
4045 
4046  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4047  SCIP_CALL( SCIPallocBufferArray(scip, &varnodeids, nvars) );
4048  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, &nimplvars, &ncontvars) );
4049 
4050  /* open gml file */
4051  (void) SCIPsnprintf(fname, SCIP_MAXSTRLEN, "and-gates%p.gml", scip);
4052  gmlfile = fopen(fname, "w");
4053 
4054  if( gmlfile == NULL )
4055  {
4056  SCIPerrorMessage("cannot open graph file <%s>\n", fname);
4057  SCIPABORT();
4058  return SCIP_WRITEERROR; /*lint !e527*/
4059  }
4060 
4061  /* create the variable mapping hash map */
4062  SCIP_CALL_FINALLY( SCIPhashmapCreate(&hashmap, SCIPblkmem(scip), nvars), fclose(gmlfile) );
4063 
4064  /* write starting of gml file */
4065  SCIPgmlWriteOpening(gmlfile, TRUE);
4066 
4067  /* walk over all AND-constraints */
4068  for( c = nconss - 1; c >= 0; --c )
4069  {
4070  cons = conss[c];
4071 
4072  /* only handle active constraints */
4073  if( !SCIPconsIsActive(cons) )
4074  continue;
4075 
4076  consdata = SCIPconsGetData(cons);
4077  assert(consdata != NULL);
4078 
4079  /* only handle constraints which have operands */
4080  if( consdata->nvars == 0 )
4081  continue;
4082 
4083  assert(consdata->vars != NULL);
4084  assert(consdata->resvar != NULL);
4085 
4086  /* get active variable of resultant */
4087  activevar = SCIPvarGetProbvar(consdata->resvar);
4088 
4089  /* check if we already found this variables */
4090  resid = SCIPhashmapGetImageInt(hashmap, activevar);
4091  assert(resid >= 0);
4092 
4093  if( resid == 0 )
4094  {
4095  resid = id;
4096  ++id;
4097  SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activevar, resid) );
4098 
4099  /* write new gml node for new resultant */
4100  SCIPgmlWriteNode(gmlfile, resid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4101  }
4102 
4103  /* copy operands to get problem variables for */
4104  SCIP_CALL( SCIPduplicateBufferArray(scip, &activeconsvars, consdata->vars, consdata->nvars) );
4105 
4106  /* get problem variables of operands */
4107  SCIPvarsGetProbvar(activeconsvars, consdata->nvars);
4108 
4109  for( v = consdata->nvars - 1; v >= 0; --v )
4110  {
4111  /* check if we already found this variables */
4112  varid = SCIPhashmapGetImageInt(hashmap, activeconsvars[v]);
4113  if( varid == 0 )
4114  {
4115  varid = id;
4116  ++id;
4117  SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activeconsvars[v], varid) );
4118 
4119  /* write new gml node for new operand */
4120  SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activeconsvars[v]), NULL, NULL, NULL);
4121  }
4122  /* write gml arc between resultant and operand */
4123  SCIPgmlWriteArc(gmlfile, resid, varid, NULL, NULL);
4124  }
4125 
4126  /* free temporary memory for active constraint variables */
4127  SCIPfreeBufferArray(scip, &activeconsvars);
4128  }
4129 
4130  /* write all remaining variables as nodes */
4131 #ifdef SCIP_DISABLED_CODE
4132  for( v = nvars - 1; v >= 0; --v )
4133  {
4134  activevar = SCIPvarGetProbvar(vars[v]);
4135 
4136  varid = SCIPhashmapGetImageInt(hashmap, activevar);
4137  assert(varid >= 0);
4138 
4139  if( varid == 0 )
4140  {
4141  varid = id;
4142  ++id;
4143  SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activeconsvars[v], varid) );
4144 
4145  /* write new gml node for new operand */
4146  SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4147  }
4148  }
4149 #endif
4150 
4151  /* free the variable mapping hash map */
4152  SCIPhashmapFree(&hashmap);
4153 
4154  SCIPgmlWriteClosing(gmlfile);
4155 
4156  fclose(gmlfile);
4157 
4158  SCIPfreeBufferArray(scip, &varnodeids);
4159  SCIPfreeBufferArray(scip, &vars);
4160 
4161  return SCIP_OKAY;
4162 }
4163 #endif
4164 
4165 /** solving process initialization method of constraint handler */
4166 static
4167 SCIP_DECL_CONSINITSOL(consInitsolAnd)
4168 { /*lint --e{715}*/
4169  /* add nlrow representation to NLP, if NLP had been constructed */
4170  if( SCIPisNLPConstructed(scip) )
4171  {
4172  int c;
4173  for( c = 0; c < nconss; ++c )
4174  {
4175  SCIP_CALL( addNlrow(scip, conss[c]) );
4176  }
4177  }
4178 
4179  return SCIP_OKAY;
4180 }
4181 
4182 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4183 static
4184 SCIP_DECL_CONSEXITSOL(consExitsolAnd)
4185 { /*lint --e{715}*/
4186  SCIP_CONSDATA* consdata;
4187  int c;
4188 
4189  /* release and free the rows and nlrow of all constraints */
4190  for( c = 0; c < nconss; ++c )
4191  {
4192  consdata = SCIPconsGetData(conss[c]);
4193  assert(consdata != NULL);
4194 
4195  SCIP_CALL( consdataFreeRows(scip, consdata) );
4196 
4197  if( consdata->nlrow != NULL )
4198  {
4199  SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow) );
4200  }
4201  }
4202 
4203  return SCIP_OKAY;
4204 }
4205 
4206 
4207 /** frees specific constraint data */
4208 static
4209 SCIP_DECL_CONSDELETE(consDeleteAnd)
4210 { /*lint --e{715}*/
4211  SCIP_CONSHDLRDATA* conshdlrdata;
4212 
4213  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4214  assert(conshdlrdata != NULL);
4215 
4216  SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4217 
4218  return SCIP_OKAY;
4219 }
4220 
4221 
4222 /** transforms constraint data into data belonging to the transformed problem */
4223 static
4224 SCIP_DECL_CONSTRANS(consTransAnd)
4225 { /*lint --e{715}*/
4226  SCIP_CONSHDLRDATA* conshdlrdata;
4227  SCIP_CONSDATA* sourcedata;
4228  SCIP_CONSDATA* targetdata;
4229 
4230  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4231  assert(conshdlrdata != NULL);
4232 
4233  sourcedata = SCIPconsGetData(sourcecons);
4234  assert(sourcedata != NULL);
4235 
4236  /* create target constraint data */
4237  SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr,
4238  sourcedata->nvars, sourcedata->vars, sourcedata->resvar, sourcedata->checkwhenupgr,
4239  sourcedata->notremovablewhenupgr) );
4240 
4241  /* create target constraint */
4242  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4243  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4244  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4245  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4246  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4247 
4248  return SCIP_OKAY;
4249 }
4250 
4251 
4252 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4253 static
4254 SCIP_DECL_CONSINITLP(consInitlpAnd)
4255 { /*lint --e{715}*/
4256  int i;
4257 
4258  *infeasible = FALSE;
4259 
4260  for( i = 0; i < nconss && !(*infeasible); i++ )
4261  {
4262  assert(SCIPconsIsInitial(conss[i]));
4263  SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4264  }
4265 
4266  return SCIP_OKAY;
4267 }
4268 
4269 
4270 /** separation method of constraint handler for LP solutions */
4271 static
4272 SCIP_DECL_CONSSEPALP(consSepalpAnd)
4273 { /*lint --e{715}*/
4274  SCIP_Bool separated;
4275  SCIP_Bool cutoff;
4276  int c;
4277 
4278  *result = SCIP_DIDNOTFIND;
4279 
4280  /* separate all useful constraints */
4281  for( c = 0; c < nusefulconss; ++c )
4282  {
4283  SCIP_CALL( separateCons(scip, conss[c], NULL, &separated, &cutoff) );
4284  if ( cutoff )
4285  *result = SCIP_CUTOFF;
4286  else if ( separated )
4287  *result = SCIP_SEPARATED;
4288  }
4289 
4290  /* combine constraints to get more cuts */
4291  /**@todo combine constraints to get further cuts */
4292 
4293  return SCIP_OKAY;
4294 }
4295 
4296 
4297 /** separation method of constraint handler for arbitrary primal solutions */
4298 static
4299 SCIP_DECL_CONSSEPASOL(consSepasolAnd)
4300 { /*lint --e{715}*/
4301  SCIP_Bool separated;
4302  SCIP_Bool cutoff;
4303  int c;
4304 
4305  *result = SCIP_DIDNOTFIND;
4306 
4307  /* separate all useful constraints */
4308  for( c = 0; c < nusefulconss; ++c )
4309  {
4310  SCIP_CALL( separateCons(scip, conss[c], sol, &separated, &cutoff) );
4311  if ( cutoff )
4312  *result = SCIP_CUTOFF;
4313  else if ( separated )
4314  *result = SCIP_SEPARATED;
4315  }
4316 
4317  /* combine constraints to get more cuts */
4318  /**@todo combine constraints to get further cuts */
4319 
4320  return SCIP_OKAY;
4321 }
4322 
4323 
4324 /** constraint enforcing method of constraint handler for LP solutions */
4325 static
4326 SCIP_DECL_CONSENFOLP(consEnfolpAnd)
4327 { /*lint --e{715}*/
4328  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) );
4329 
4330  return SCIP_OKAY;
4331 }
4332 
4333 /** constraint enforcing method of constraint handler for relaxation solutions */
4334 static
4335 SCIP_DECL_CONSENFORELAX(consEnforelaxAnd)
4336 { /*lint --e{715}*/
4337  SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) );
4338 
4339  return SCIP_OKAY;
4340 }
4341 
4342 /** constraint enforcing method of constraint handler for pseudo solutions */
4343 static
4344 SCIP_DECL_CONSENFOPS(consEnfopsAnd)
4345 { /*lint --e{715}*/
4346  SCIP_Bool violated;
4347  int i;
4348 
4349  /* method is called only for integral solutions, because the enforcing priority is negative */
4350  for( i = 0; i < nconss; i++ )
4351  {
4352  SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
4353  if( violated )
4354  {
4355  *result = SCIP_INFEASIBLE;
4356  return SCIP_OKAY;
4357  }
4358  }
4359  *result = SCIP_FEASIBLE;
4360 
4361  return SCIP_OKAY;
4362 }
4363 
4364 
4365 /** feasibility check method of constraint handler for integral solutions */
4366 static
4367 SCIP_DECL_CONSCHECK(consCheckAnd)
4368 { /*lint --e{715}*/
4369  SCIP_Bool violated;
4370  int i;
4371 
4372  *result = SCIP_FEASIBLE;
4373 
4374  /* method is called only for integral solutions, because the enforcing priority is negative */
4375  for( i = 0; i < nconss && (*result == SCIP_FEASIBLE || completely); i++ )
4376  {
4377  SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, printreason, &violated) );
4378  if( violated )
4379  *result = SCIP_INFEASIBLE;
4380  }
4381 
4382  return SCIP_OKAY;
4383 }
4384 
4385 
4386 /** domain propagation method of constraint handler */
4387 static
4388 SCIP_DECL_CONSPROP(consPropAnd)
4389 { /*lint --e{715}*/
4390  SCIP_CONSHDLRDATA* conshdlrdata;
4391  SCIP_Bool cutoff;
4392  int nfixedvars;
4393  int nupgdconss;
4394  int c;
4395 
4396  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4397  assert(conshdlrdata != NULL);
4398 
4399  cutoff = FALSE;
4400  nfixedvars = 0;
4401  nupgdconss = 0;
4402 
4403  /* propagate all useful constraints */
4404  for( c = 0; c < nusefulconss && !cutoff; ++c )
4405  {
4406  SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars, &nupgdconss) );
4407  }
4408 
4409  /* return the correct result */
4410  if( cutoff )
4411  *result = SCIP_CUTOFF;
4412  else if( nfixedvars > 0 || nupgdconss > 0 )
4413  *result = SCIP_REDUCEDDOM;
4414  else
4415  *result = SCIP_DIDNOTFIND;
4416 
4417  return SCIP_OKAY;
4418 }
4419 
4420 
4421 /** presolving method of constraint handler */
4422 static
4423 SCIP_DECL_CONSPRESOL(consPresolAnd)
4424 { /*lint --e{715}*/
4425  SCIP_CONSHDLRDATA* conshdlrdata;
4426  SCIP_CONS* cons;
4427  SCIP_CONSDATA* consdata;
4428  unsigned char* entries;
4429  SCIP_Bool cutoff;
4430  int oldnfixedvars;
4431  int oldnaggrvars;
4432  int oldnchgbds;
4433  int oldndelconss;
4434  int oldnupgdconss;
4435  int firstchange;
4436  int nentries;
4437  int c;
4438 
4439  assert(result != NULL);
4440 
4441  oldnfixedvars = *nfixedvars;
4442  oldnaggrvars = *naggrvars;
4443  oldnchgbds = *nchgbds;
4444  oldndelconss = *ndelconss;
4445  oldnupgdconss = *nupgdconss;
4446 
4447  nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
4448  SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
4449 
4450  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4451  assert(conshdlrdata != NULL);
4452 
4453  /* process constraints */
4454  cutoff = FALSE;
4455  firstchange = INT_MAX;
4456  for( c = 0; c < nconss && !cutoff && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
4457  {
4458  cons = conss[c];
4459  assert(cons != NULL);
4460  consdata = SCIPconsGetData(cons);
4461  assert(consdata != NULL);
4462 
4463  /* force presolving the constraint in the initial round */
4464  if( nrounds == 0 )
4465  consdata->propagated = FALSE;
4466 
4467  /* remember the first changed constraint to begin the next aggregation round with */
4468  if( firstchange == INT_MAX && consdata->changed )
4469  firstchange = c;
4470 
4471  /* propagate constraint */
4472  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nupgdconss) );
4473 
4474  /* remove all variables that are fixed to one; merge multiple entries of the same variable;
4475  * fix resultant to zero if a pair of negated variables is contained in the operand variables
4476  */
4477  if( !cutoff && !SCIPconsIsDeleted(cons) )
4478  {
4479  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs) );
4480 
4481  /* merge multiple occurances of variables or variables with their negated variables */
4482  SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, nfixedvars, nchgcoefs, ndelconss) );
4483  }
4484 
4485  if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
4486  {
4487  assert(consdata->nvars >= 1); /* otherwise, propagateCons() has deleted the constraint */
4488 
4489  /* if only one variable is left, the resultant has to be equal to this single variable */
4490  if( consdata->nvars == 1 )
4491  {
4492  SCIP_Bool redundant;
4493  SCIP_Bool aggregated;
4494 
4495  SCIPdebugMsg(scip, "AND-constraint <%s> has only one variable not fixed to 1.0\n", SCIPconsGetName(cons));
4496 
4497  assert(consdata->vars != NULL);
4498  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
4499  assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
4500 
4501  /* aggregate variables: resultant - operand == 0 */
4502  SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
4503  &cutoff, &redundant, &aggregated) );
4504  assert(redundant || SCIPdoNotAggr(scip));
4505 
4506  if( aggregated )
4507  {
4508  assert(redundant);
4509  (*naggrvars)++;
4510  }
4511 
4512  if( redundant )
4513  {
4514  /* delete constraint */
4515  SCIP_CALL( SCIPdelCons(scip, cons) );
4516  (*ndelconss)++;
4517  }
4518  }
4519  else if( !consdata->impladded )
4520  {
4521  int i;
4522 
4523  /* add implications: resultant == 1 -> all operands == 1 */
4524  for( i = 0; i < consdata->nvars && !cutoff; ++i )
4525  {
4526  int nimplbdchgs;
4527 
4528  SCIP_CALL( SCIPaddVarImplication(scip, consdata->resvar, TRUE, consdata->vars[i],
4529  SCIP_BOUNDTYPE_LOWER, 1.0, &cutoff, &nimplbdchgs) );
4530  (*nchgbds) += nimplbdchgs;
4531  }
4532  consdata->impladded = TRUE;
4533  }
4534 
4535  /* if in r = x and y, the resultant is fixed to zero, add implication x = 1 -> y = 0 */
4536  if( !cutoff && SCIPconsIsActive(cons) && consdata->nvars == 2 && !consdata->opimpladded
4537  && SCIPvarGetUbGlobal(consdata->resvar) < 0.5 )
4538  {
4539  int nimplbdchgs;
4540 
4541  SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], TRUE, consdata->vars[1],
4542  SCIP_BOUNDTYPE_UPPER, 0.0, &cutoff, &nimplbdchgs) );
4543  (*nchgbds) += nimplbdchgs;
4544  consdata->opimpladded = TRUE;
4545  }
4546  }
4547  }
4548 
4549  /* perform dual presolving on AND-constraints */
4550  if( conshdlrdata->dualpresolving && !cutoff && !SCIPisStopped(scip) && SCIPallowStrongDualReds(scip))
4551  {
4552  SCIP_CALL( dualPresolve(scip, conss, nconss, conshdlrdata->eventhdlr, &entries, &nentries, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, nupgdconss, naddconss) );
4553  }
4554 
4555  /* check for cliques inside the AND constraint */
4556  if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4557  {
4558  for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4559  {
4560  cons = conss[c];
4561  assert(cons != NULL);
4562 
4563  if( !SCIPconsIsActive(cons) )
4564  continue;
4565 
4566  /* cliquePresolve() may aggregate variables which need to be removed from other constraints, we also need
4567  * to make sure that we remove fixed variables by calling propagateCons() to make sure that applyFixing()
4568  * and mergeMultiples() work
4569  */
4570  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nupgdconss) );
4571 
4572  if( !cutoff && !SCIPconsIsDeleted(cons) )
4573  {
4574  /* remove all variables that are fixed to one; merge multiple entries of the same variable;
4575  * fix resultant to zero if a pair of negated variables is contained in the operand variables
4576  */
4577  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs) );
4578  SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, nfixedvars, nchgcoefs, ndelconss) );
4579 
4580  /* check if at least two operands are in one clique */
4581  SCIP_CALL( cliquePresolve(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, naddconss) );
4582  }
4583  }
4584  }
4585 
4586  /* process pairs of constraints: check them for equal operands in order to aggregate resultants;
4587  * only apply this expensive procedure, if the single constraint preprocessing did not find any reductions
4588  * (otherwise, we delay the presolving to be called again next time)
4589  */
4590  if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4591  {
4592  if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4593  {
4594  if( firstchange < nconss )
4595  {
4596  /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
4597  SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, &cutoff, naggrvars, ndelconss) );
4598  oldnaggrvars = *naggrvars;
4599  }
4600  }
4601  }
4602 
4603  if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4604  {
4605  if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4606  {
4607  SCIP_Longint npaircomparisons;
4608  npaircomparisons = 0;
4609  oldndelconss = *ndelconss;
4610 
4611  for( c = firstchange; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4612  {
4613  if( SCIPconsIsActive(conss[c]) && !SCIPconsIsModifiable(conss[c]) )
4614  {
4615  npaircomparisons += ((SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange));
4616 
4617  SCIP_CALL( preprocessConstraintPairs(scip, conss, firstchange, c, &cutoff, naggrvars, nchgbds,
4618  ndelconss) );
4619 
4620  if( npaircomparisons > NMINCOMPARISONS )
4621  {
4622  if( ((*ndelconss - oldndelconss) + (*naggrvars - oldnaggrvars) + (*nchgbds - oldnchgbds)/2.0) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
4623  break;
4624  oldndelconss = *ndelconss;
4625  oldnaggrvars = *naggrvars;
4626  oldnchgbds = *nchgbds;
4627 
4628  npaircomparisons = 0;
4629  }
4630  }
4631  }
4632  }
4633  }
4634 
4635  SCIPfreeBufferArray(scip, &entries);
4636 
4637  /* return the correct result code */
4638  if( cutoff )
4639  *result = SCIP_CUTOFF;
4640  else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds
4641  || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4642  *result = SCIP_SUCCESS;
4643  else
4644  *result = SCIP_DIDNOTFIND;
4645 
4646  return SCIP_OKAY;
4647 }
4648 
4649 
4650 /** propagation conflict resolving method of constraint handler */
4651 static
4652 SCIP_DECL_CONSRESPROP(consRespropAnd)
4653 { /*lint --e{715}*/
4654  SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
4655 
4656  return SCIP_OKAY;
4657 }
4658 
4659 
4660 /** variable rounding lock method of constraint handler */
4661 static
4662 SCIP_DECL_CONSLOCK(consLockAnd)
4663 { /*lint --e{715}*/
4664  SCIP_CONSDATA* consdata;
4665  int i;
4666 
4667  assert(locktype == SCIP_LOCKTYPE_MODEL);
4668 
4669  consdata = SCIPconsGetData(cons);
4670  assert(consdata != NULL);
4671 
4672  /* resultant variable */
4673  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->resvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4674 
4675  /* operand variables */
4676  for( i = 0; i < consdata->nvars; ++i )
4677  {
4678  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4679  }
4680 
4681  return SCIP_OKAY;
4682 }
4683 
4684 /** constraint activation notification method of constraint handler */
4685 static
4686 SCIP_DECL_CONSACTIVE(consActiveAnd)
4687 { /*lint --e{715}*/
4688  if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPisNLPConstructed(scip) )
4689  {
4690  SCIP_CALL( addNlrow(scip, cons) );
4691  }
4692 
4693  return SCIP_OKAY;
4694 }
4695 
4696 /** constraint deactivation notification method of constraint handler */
4697 static
4698 SCIP_DECL_CONSDEACTIVE(consDeactiveAnd)
4699 { /*lint --e{715}*/
4700  SCIP_CONSDATA* consdata;
4701 
4702  assert(cons != NULL);
4703 
4704  consdata = SCIPconsGetData(cons);
4705  assert(consdata != NULL);
4706 
4707  /* remove row from NLP, if still in solving
4708  * if we are in exitsolve, the whole NLP will be freed anyway
4709  */
4710  if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && consdata->nlrow != NULL )
4711  {
4712  SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow) );
4713  }
4714 
4715  return SCIP_OKAY;
4716 }
4717 
4718 /** constraint display method of constraint handler */
4719 static
4720 SCIP_DECL_CONSPRINT(consPrintAnd)
4721 { /*lint --e{715}*/
4722  assert( scip != NULL );
4723  assert( conshdlr != NULL );
4724  assert( cons != NULL );
4725 
4726  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file) );
4727 
4728  return SCIP_OKAY;
4729 }
4730 
4731 /** constraint copying method of constraint handler */
4732 static
4733 SCIP_DECL_CONSCOPY(consCopyAnd)
4734 { /*lint --e{715}*/
4735  SCIP_VAR** sourcevars;
4736  SCIP_VAR** vars;
4737  SCIP_VAR* sourceresvar;
4738  SCIP_VAR* resvar;
4739  const char* consname;
4740  int nvars;
4741  int v;
4742 
4743  assert(valid != NULL);
4744  (*valid) = TRUE;
4745 
4746  sourceresvar = SCIPgetResultantAnd(sourcescip, sourcecons);
4747 
4748  /* map resultant to active variable of the target SCIP */
4749  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceresvar, &resvar, varmap, consmap, global, valid) );
4750  assert(!(*valid) || resvar != NULL);
4751 
4752  /* we do not copy, if a variable is missing */
4753  if( !(*valid) )
4754  return SCIP_OKAY;
4755 
4756  /* map operand variables to active variables of the target SCIP */
4757  sourcevars = SCIPgetVarsAnd(sourcescip, sourcecons);
4758  nvars = SCIPgetNVarsAnd(sourcescip, sourcecons);
4759 
4760  if( nvars == -1 )
4761  return SCIP_INVALIDCALL;
4762 
4763  /* allocate buffer array */
4764  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4765 
4766  for( v = 0; v < nvars; ++v )
4767  {
4768  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
4769  assert(!(*valid) || vars[v] != NULL);
4770 
4771  /* we do not copy, if a variable is missing */
4772  if( !(*valid) )
4773  goto TERMINATE;
4774  }
4775 
4776  if( name != NULL )
4777  consname = name;
4778  else
4779  consname = SCIPconsGetName(sourcecons);
4780 
4781  /* creates and captures a AND-constraint */
4782  SCIP_CALL( SCIPcreateConsAnd(scip, cons, consname, resvar, nvars, vars,
4783  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4784 
4785  TERMINATE:
4786  /* free buffer array */
4787  SCIPfreeBufferArray(scip, &vars);
4788 
4789  return SCIP_OKAY;
4790 }
4791 
4792 /** constraint parsing method of constraint handler */
4793 static
4794 SCIP_DECL_CONSPARSE(consParseAnd)
4795 { /*lint --e{715}*/
4796  SCIP_VAR** vars;
4797  SCIP_VAR* resvar;
4798  char* endptr;
4799  int requiredsize;
4800  int varssize;
4801  int nvars;
4802 
4803  SCIPdebugMsg(scip, "parse <%s> as AND-constraint\n", str);
4804 
4805  *success = FALSE;
4806 
4807  /* parse variable name of resultant */
4808  SCIP_CALL( SCIPparseVarName(scip, str, &resvar, &endptr) );
4809 
4810  if( resvar == NULL )
4811  {
4812  SCIPerrorMessage("resultant variable does not exist\n");
4813  }
4814  else
4815  {
4816  char* strcopy = NULL;
4817  char* startptr;
4818 
4819  str = endptr;
4820 
4821  /* cutoff "== and(" form the constraint string */
4822  startptr = strchr((char*)str, '(');
4823 
4824  if( startptr == NULL )
4825  {
4826  SCIPerrorMessage("missing starting character '(' parsing AND-constraint\n");
4827  return SCIP_OKAY;
4828  }
4829 
4830  /* skip '(' */
4831  ++startptr;
4832 
4833  /* find end character ')' */
4834  endptr = strrchr(startptr, ')');
4835 
4836  if( endptr == NULL )
4837  {
4838  SCIPerrorMessage("missing ending character ')' parsing AND-constraint\n");
4839  return SCIP_OKAY;
4840  }
4841  assert(endptr >= startptr);
4842 
4843  if( endptr > startptr )
4844  {
4845  /* copy string for parsing; note that SCIPskipSpace() in SCIPparseVarsList() requires that strcopy ends with '\0' */
4846  SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, startptr, (int)(endptr-startptr+1)) );
4847  strcopy[endptr-startptr] = '\0';
4848  varssize = 100;
4849  nvars = 0;
4850 
4851  /* allocate buffer array for variables */
4852  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
4853 
4854  /* parse string */
4855  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4856 
4857  if( *success )
4858  {
4859  /* check if the size of the variable array was great enough */
4860  if( varssize < requiredsize )
4861  {
4862  /* reallocate memory */
4863  varssize = requiredsize;
4864  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
4865 
4866  /* parse string again with the correct size of the variable array */
4867  SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4868  }
4869 
4870  assert(*success);
4871  assert(varssize >= requiredsize);
4872 
4873  /* create AND-constraint */
4874  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
4875  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4876  }
4877 
4878  /* free variable buffer */
4879  SCIPfreeBufferArray(scip, &vars);
4880  SCIPfreeBufferArray(scip, &strcopy);
4881  }
4882  else
4883  {
4884  if( !modifiable )
4885  {
4886  SCIPerrorMessage("cannot create empty AND-constraint\n");
4887  return SCIP_OKAY;
4888  }
4889 
4890  /* create empty AND-constraint */
4891  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, 0, NULL,
4892  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4893 
4894  *success = TRUE;
4895  }
4896  }
4897 
4898  return SCIP_OKAY;
4899 }
4900 
4901 /** constraint method of constraint handler which returns the variables (if possible) */
4902 static
4903 SCIP_DECL_CONSGETVARS(consGetVarsAnd)
4904 { /*lint --e{715}*/
4905  SCIP_CONSDATA* consdata;
4906 
4907  consdata = SCIPconsGetData(cons);
4908  assert(consdata != NULL);
4909 
4910  if( varssize < consdata->nvars + 1 )
4911  (*success) = FALSE;
4912  else
4913  {
4914  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
4915  vars[consdata->nvars] = consdata->resvar;
4916  (*success) = TRUE;
4917  }
4918 
4919  return SCIP_OKAY;
4920 }
4921 
4922 /** constraint method of constraint handler which returns the number of variable (if possible) */
4923 static
4924 SCIP_DECL_CONSGETNVARS(consGetNVarsAnd)
4925 { /*lint --e{715}*/
4926  SCIP_CONSDATA* consdata;
4927 
4928  assert(cons != NULL);
4929 
4930  consdata = SCIPconsGetData(cons);
4931  assert(consdata != NULL);
4932 
4933  (*nvars) = consdata->nvars + 1;
4934  (*success) = TRUE;
4935 
4936  return SCIP_OKAY;
4937 }
4938 
4939 /** constraint handler method which returns the permutation symmetry detection graph of a constraint */
4940 static
4941 SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphAnd)
4942 { /*lint --e{715}*/
4943  SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_PERM, cons, graph, success) );
4944 
4945  return SCIP_OKAY;
4946 }
4947 
4948 /** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
4949 static
4950 SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphAnd)
4951 { /*lint --e{715}*/
4952  SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_SIGNPERM, cons, graph, success) );
4953 
4954  return SCIP_OKAY;
4955 }
4956 
4957 /*
4958  * Callback methods of event handler
4959  */
4960 
4961 static
4962 SCIP_DECL_EVENTEXEC(eventExecAnd)
4963 { /*lint --e{715}*/
4964  SCIP_CONSDATA* consdata;
4965 
4966  assert(eventhdlr != NULL);
4967  assert(eventdata != NULL);
4968  assert(event != NULL);
4969 
4970  consdata = (SCIP_CONSDATA*)eventdata;
4971  assert(consdata != NULL);
4972 
4973  /* check, if the variable was fixed to zero */
4975  consdata->nofixedzero = FALSE;
4976 
4977  consdata->propagated = FALSE;
4978 
4979  return SCIP_OKAY;
4980 }
4981 
4982 
4983 /*
4984  * constraint specific interface methods
4985  */
4986 
4987 /** creates the handler for AND-constraints and includes it in SCIP */
4989  SCIP* scip /**< SCIP data structure */
4990  )
4991 {
4992  SCIP_CONSHDLRDATA* conshdlrdata;
4993  SCIP_CONSHDLR* conshdlr;
4994  SCIP_EVENTHDLR* eventhdlr;
4995 
4996  /* create event handler for events on variables */
4998  eventExecAnd, NULL) );
4999 
5000  /* create constraint handler data */
5001  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
5002 
5003  /* include constraint handler */
5006  consEnfolpAnd, consEnfopsAnd, consCheckAnd, consLockAnd,
5007  conshdlrdata) );
5008 
5009  assert(conshdlr != NULL);
5010 
5011  /* set non-fundamental callbacks via specific setter functions */
5012  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyAnd, consCopyAnd) );
5013  SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveAnd) );
5014  SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveAnd) );
5015  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteAnd) );
5016 #ifdef GMLGATEPRINTING
5017  SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreAnd) );
5018 #endif
5019  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolAnd) );
5020  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolAnd) );
5021  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeAnd) );
5022  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsAnd) );
5023  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsAnd) );
5024  SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreAnd) );
5025  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpAnd) );
5026  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseAnd) );
5027  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolAnd, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
5028  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintAnd) );
5029  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropAnd, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
5031  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropAnd) );
5032  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpAnd, consSepasolAnd, CONSHDLR_SEPAFREQ,
5034  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransAnd) );
5035  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxAnd) );
5036  SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphAnd) );
5037  SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphAnd) );
5038 
5039  /* add AND-constraint handler parameters */
5041  "constraints/" CONSHDLR_NAME "/presolpairwise",
5042  "should pairwise constraint comparison be performed in presolving?",
5043  &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
5045  "constraints/and/presolusehashing",
5046  "should hash table be used for detecting redundant constraints in advance",
5047  &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
5049  "constraints/" CONSHDLR_NAME "/linearize",
5050  "should the AND-constraint get linearized and removed (in presolving)?",
5051  &conshdlrdata->linearize, TRUE, DEFAULT_LINEARIZE, NULL, NULL) );
5053  "constraints/" CONSHDLR_NAME "/enforcecuts",
5054  "should cuts be separated during LP enforcing?",
5055  &conshdlrdata->enforcecuts, TRUE, DEFAULT_ENFORCECUTS, NULL, NULL) );
5057  "constraints/" CONSHDLR_NAME "/aggrlinearization",
5058  "should an aggregated linearization be used?",
5059  &conshdlrdata->aggrlinearization, TRUE, DEFAULT_AGGRLINEARIZATION, NULL, NULL) );
5061  "constraints/" CONSHDLR_NAME "/upgraderesultant",
5062  "should all binary resultant variables be upgraded to implicit binary variables?",
5063  &conshdlrdata->upgrresultant, TRUE, DEFAULT_UPGRRESULTANT, NULL, NULL) );
5065  "constraints/" CONSHDLR_NAME "/dualpresolving",
5066  "should dual presolving be performed?",
5067  &conshdlrdata->dualpresolving, TRUE, DEFAULT_DUALPRESOLVING, NULL, NULL) );
5068 
5069  return SCIP_OKAY;
5070 }
5071 
5072 /** creates and captures a AND-constraint
5073  *
5074  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5075  */
5077  SCIP* scip, /**< SCIP data structure */
5078  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5079  const char* name, /**< name of constraint */
5080  SCIP_VAR* resvar, /**< resultant variable of the operation */
5081  int nvars, /**< number of operator variables in the constraint */
5082  SCIP_VAR** vars, /**< array with operator variables of constraint */
5083  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5084  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5085  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5086  * Usually set to TRUE. */
5087  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5088  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5089  SCIP_Bool check, /**< should the constraint be checked for feasibility?
5090  * TRUE for model constraints, FALSE for additional, redundant constraints. */
5091  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5092  * Usually set to TRUE. */
5093  SCIP_Bool local, /**< is constraint only valid locally?
5094  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5095  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5096  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5097  * adds coefficients to this constraint. */
5098  SCIP_Bool dynamic, /**< is constraint subject to aging?
5099  * Usually set to FALSE. Set to TRUE for own cuts which
5100  * are separated as constraints. */
5101  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5102  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5103  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5104  * if it may be moved to a more global node?
5105  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5106  )
5107 {
5108  SCIP_CONSHDLR* conshdlr;
5109  SCIP_CONSHDLRDATA* conshdlrdata;
5110  SCIP_CONSDATA* consdata;
5111  SCIP_Bool infeasible;
5112 
5113  /* find the AND-constraint handler */
5114  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5115  if( conshdlr == NULL )
5116  {
5117  SCIPerrorMessage("AND-constraint handler not found\n");
5118  return SCIP_PLUGINNOTFOUND;
5119  }
5120 
5121  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5122  assert(conshdlrdata != NULL);
5123 
5124  /* upgrade binary resultant variable to an implicit binary variable */
5125  /* @todo add implicit upgrade in presolving, improve decision making for upgrade by creating an implication graph */
5126  if( conshdlrdata->upgrresultant && SCIPvarGetType(resvar) == SCIP_VARTYPE_BINARY
5127 #if 1 /* todo delete following hack,
5128  * the following avoids upgrading not artificial variables, for example and-resultants which are generated
5129  * from the gate presolver, it seems better to not upgrade these variables
5130  */
5131  && strlen(SCIPvarGetName(resvar)) > strlen(ARTIFICIALVARNAMEPREFIX) && strncmp(SCIPvarGetName(resvar), ARTIFICIALVARNAMEPREFIX, strlen(ARTIFICIALVARNAMEPREFIX)) == 0 )
5132 #else
5133  )
5134 #endif
5135  {
5136  SCIP_VAR* activeresvar;
5137  SCIP_VAR* activevar;
5138  int v;
5139 
5140  if( SCIPisTransformed(scip) )
5141  activeresvar = SCIPvarGetProbvar(resvar);
5142  else
5143  activeresvar = resvar;
5144 
5145  if( SCIPvarGetType(activeresvar) == SCIP_VARTYPE_BINARY )
5146  {
5147  /* check if we can upgrade the variable type of the resultant */
5148  for( v = nvars - 1; v >= 0; --v )
5149  {
5150  if( SCIPisTransformed(scip) )
5151  activevar = SCIPvarGetProbvar(vars[v]);
5152  else
5153  activevar = vars[v];
5154 
5155  if( activevar == activeresvar || SCIPvarGetType(activevar) == SCIP_VARTYPE_IMPLINT )
5156  break;
5157  }
5158 
5159  /* upgrade the type of the resultant */
5160  if( v < 0 )
5161  {
5162  SCIP_CALL( SCIPchgVarType(scip, resvar, SCIP_VARTYPE_IMPLINT, &infeasible) );
5163  assert(!infeasible);
5164  }
5165  }
5166  }
5167 
5168  /* create constraint data */
5169  SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, resvar, FALSE, FALSE) );
5170 
5171  /* create constraint */
5172  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5173  local, modifiable, dynamic, removable, stickingatnode) );
5174 
5175  return SCIP_OKAY;
5176 }
5177 
5178 /** creates and captures an AND-constraint
5179  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
5180  * method SCIPcreateConsAnd(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
5181  *
5182  * @see SCIPcreateConsAnd() for information about the basic constraint flag configuration
5183  *
5184  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5185  */
5187  SCIP* scip, /**< SCIP data structure */
5188  SCIP_CONS** cons, /**< pointer to hold the created constraint */
5189  const char* name, /**< name of constraint */
5190  SCIP_VAR* resvar, /**< resultant variable of the operation */
5191  int nvars, /**< number of operator variables in the constraint */
5192  SCIP_VAR** vars /**< array with operator variables of constraint */
5193  )
5194 {
5195  assert(scip != NULL);
5196 
5197  SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
5198  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
5199 
5200  return SCIP_OKAY;
5201 }
5202 
5203 
5204 /** gets number of variables in AND-constraint */
5205 int SCIPgetNVarsAnd(
5206  SCIP* scip, /**< SCIP data structure */
5207  SCIP_CONS* cons /**< constraint data */
5208  )
5209 {
5210  SCIP_CONSDATA* consdata;
5211 
5212  assert(scip != NULL);
5213  assert(cons != NULL);
5214 
5215  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5216  {
5217  SCIPerrorMessage("constraint is not an AND-constraint\n");
5218  SCIPABORT();
5219  return -1; /*lint !e527*/
5220  }
5221 
5222  consdata = SCIPconsGetData(cons);
5223  assert(consdata != NULL);
5224 
5225  return consdata->nvars;
5226 }
5227 
5228 /** gets array of variables in AND-constraint */
5230  SCIP* scip, /**< SCIP data structure */
5231  SCIP_CONS* cons /**< constraint data */
5232  )
5233 { /*lint --e{715}*/
5234  SCIP_CONSDATA* consdata;
5235 
5236  assert(scip != NULL);
5237  assert(cons != NULL);
5238 
5239  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5240  {
5241  SCIPerrorMessage("constraint is not an AND-constraint\n");
5242  SCIPABORT();
5243  return NULL; /*lint !e527*/
5244  }
5245 
5246  consdata = SCIPconsGetData(cons);
5247  assert(consdata != NULL);
5248 
5249  return consdata->vars;
5250 }
5251 
5252 
5253 /** gets the resultant variable in AND-constraint */ /*lint -e715*/
5255  SCIP* scip, /**< SCIP data structure */
5256  SCIP_CONS* cons /**< constraint data */
5257  )
5258 {
5259  SCIP_CONSDATA* consdata;
5260 
5261  assert(cons != NULL);
5262 
5263  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5264  {
5265  SCIPerrorMessage("constraint is not an AND-constraint\n");
5266  SCIPABORT();
5267  return NULL; /*lint !e527*/
5268  }
5269 
5270  consdata = SCIPconsGetData(cons);
5271  assert(consdata != NULL);
5272 
5273  return consdata->resvar;
5274 }
5275 
5276 /** return if the variables of the AND-constraint are sorted with respect to their indices */
5278  SCIP* scip, /**< SCIP data structure */
5279  SCIP_CONS* cons /**< constraint data */
5280  )
5281 {
5282  SCIP_CONSDATA* consdata;
5283 
5284  assert(scip != NULL);
5285  assert(cons != NULL);
5286 
5287  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5288  {
5289  SCIPerrorMessage("constraint is not an AND-constraint\n");
5290  SCIPABORT();
5291  return FALSE; /*lint !e527*/
5292  }
5293 
5294  consdata = SCIPconsGetData(cons);
5295  assert(consdata != NULL);
5296 
5297  return consdata->sorted;
5298 }
5299 
5300 /** sort the variables of the AND-constraint with respect to their indices */
5302  SCIP* scip, /**< SCIP data structure */
5303  SCIP_CONS* cons /**< constraint data */
5304  )
5305 {
5306  SCIP_CONSDATA* consdata;
5307 
5308  assert(scip != NULL);
5309  assert(cons != NULL);
5310 
5311  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5312  {
5313  SCIPerrorMessage("constraint is not an AND-constraint\n");
5314  SCIPABORT();
5315  return SCIP_INVALIDDATA; /*lint !e527*/
5316  }
5317 
5318  consdata = SCIPconsGetData(cons);
5319  assert(consdata != NULL);
5320 
5321  consdataSort(consdata);
5322  assert(consdata->sorted);
5323 
5324  return SCIP_OKAY;
5325 }
5326 
5327 /** when 'upgrading' the given AND-constraint, should the check flag for the upgraded constraint be set to TRUE, even if
5328  * the check flag of this AND-constraint is set to FALSE?
5329  */
5331  SCIP* scip, /**< SCIP data structure */
5332  SCIP_CONS* cons, /**< constraint data */
5333  SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be checked,
5334  * even if the check flag of the AND-constraint is set to FALSE
5335  */
5336  )
5337 {
5338  SCIP_CONSDATA* consdata;
5339 
5340  assert(scip != NULL);
5341  assert(cons != NULL);
5342 
5343  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5344  {
5345  SCIPerrorMessage("constraint is not an AND-constraint\n");
5346  SCIPABORT();
5347  return SCIP_INVALIDDATA; /*lint !e527*/
5348  }
5349 
5350  consdata = SCIPconsGetData(cons);
5351  assert(consdata != NULL);
5352 
5353  consdata->checkwhenupgr = flag;
5354 
5355  return SCIP_OKAY;
5356 }
5357 
5358 /** when 'upgrading' the given AND-constraint, should the removable flag for the upgraded constraint be set to FALSE,
5359  * even if the removable flag of this AND-constraint is set to TRUE?
5360  */
5362  SCIP* scip, /**< SCIP data structure */
5363  SCIP_CONS* cons, /**< constraint data */
5364  SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be not
5365  * removable, even if the removable flag of the AND-constraint is set to
5366  * TRUE
5367  */
5368  )
5369 {
5370  SCIP_CONSDATA* consdata;
5371 
5372  assert(scip != NULL);
5373  assert(cons != NULL);
5374 
5375  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5376  {
5377  SCIPerrorMessage("constraint is not an AND-constraint\n");
5378  SCIPABORT();
5379  return SCIP_INVALIDDATA; /*lint !e527*/
5380  }
5381 
5382  consdata = SCIPconsGetData(cons);
5383  assert(consdata != NULL);
5384 
5385  consdata->notremovablewhenupgr = flag;
5386 
5387  return SCIP_OKAY;
5388 }
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:1318
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:1945
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:4300
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:2683
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2130
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c: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:1599
static SCIP_DECL_EVENTEXEC(eventExecAnd)
Definition: cons_and.c:4963
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1994
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c: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:5302
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
static SCIP_DECL_CONSENFORELAX(consEnforelaxAnd)
Definition: cons_and.c:4336
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:1583
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:1282
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:3790
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:3339
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:1441
static SCIP_DECL_CONSPARSE(consParseAnd)
Definition: cons_and.c:4795
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:1250
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:1357
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:4989
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:4389
#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:1411
#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:3885
static SCIP_DECL_CONSDEACTIVE(consDeactiveAnd)
Definition: cons_and.c:4699
#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:4951
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_CONSPRINT(consPrintAnd)
Definition: cons_and.c:4721
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:590
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:1482
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:4185
static SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphAnd)
Definition: cons_and.c:4942
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:2031
SCIP_Bool SCIPisAndConsSorted(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5278
static SCIP_DECL_CONSENFOPS(consEnfopsAnd)
Definition: cons_and.c:4345
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:4261
#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:8178
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:3867
#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:4424
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:5230
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:1646
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:3409
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:5077
#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:5255
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:3586
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:6782
static SCIP_DECL_CONSDELETE(consDeleteAnd)
Definition: cons_and.c:4210
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:4439
#define MAX3(x, y, z)
Definition: def.h:247
static SCIP_DECL_CONSACTIVE(consActiveAnd)
Definition: cons_and.c:4687
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:8717
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:5187
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:4225
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: