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