# 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 /* */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
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? */
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? */
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);
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) );
424  }
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;
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;
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
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
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
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  {
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 )
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
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
1303  for( v = 0; v < consdata->nvars; ++v )
1304  {
1305  assert(SCIPvarGetLbLocal(consdata->vars[v]) > 0.5);
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  {
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);
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);
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);
2008  for( i = 0; i < nvars; ++i )
2009  {
2010  if( vars[i] != infervar )
2011  {
2012  assert(SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5);
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 */
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);
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
2609  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
2610  }
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 */
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);
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);
2901  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
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);
3052  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
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;
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
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  {
3268  break;
3269  }
3270  }
3271  }
3272
3273  /* all variables are in a clique, so upgrade thi AND-constraint */
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);
3313  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
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
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
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
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
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
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
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  {
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  }
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  }
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;
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  {
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;
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';
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 */
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);
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) );
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  {
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
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
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
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)
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: